CprE 458/558: Real-Time SystemsWork-conserving vs. Non work-conservingFair Queuing (FQ) : Byte-by-Byte RR emulationWeighted Fair Queuing (WFQ)Finish time/number expressions (1)Finish time/number expressions (2)Hierarchical Round Robin (HRR)Hierarchical Round Robin – contd.HRR design for a 4Mbps linkHRR – connection allocation exampleReal-Time WAN -- SummaryCprE 458/558: Real-Time Systems (G. Manimaran) 1CprE 458/558: Real-Time SystemsReal-Time Networks – WANPacket scheduling (contd.)CprE 458/558: Real-Time Systems (G. Manimaran) 2Work-conserving vs. Non work-conserving•Work conserving scheduler–Never leaves the link idle if there is a packet to be transmitted–Offers better link utilization–E.g., RR, WRR, WFQ•Non work-conserving scheduler–Associate eligibility time with each packet and transmits packets only when they are eligible–Can provide delay-jitter control, easier implementation–E.g., HRRCprE 458/558: Real-Time Systems (G. Manimaran) 3Fair Queuing (FQ) : Byte-by-Byte RR emulation1 6 11 15 19 202 7 12 163 84 9 13 175 10 14 18ABCDEPacket FinishTimeC 8B 16D 17E 18A 20Earliest Finish Time FQ ScheduleProblem: Gives all the flows the same priorityCprE 458/558: Real-Time Systems (G. Manimaran) 4Weighted Fair Queuing (WFQ)1 2 3 12 13 144 5 15 166 177 8 18 199 10 11 20A (3)B (2)C (1)D (2)E (3)Packet FinishTimeA 14B 16C 17D 19E 20Earliest Finish Time WFQ ScheduleCprE 458/558: Real-Time Systems (G. Manimaran) 5Finish time/number expressions (1)•Round Number [ R(t) ]: number of rounds of service a bit-by-bit round-robin scheduler has completed at a given time.–Eg: round number 3.5 means, three full rounds and fourth round is half-way through•A connection is said to be active if the largest finish number of a packet either in its queue or last served from its queue is larger than the current round number•Thus, the length of a round, that is, the time taken to serve one bit from each active connection, is proportional to the number of active connectionsCprE 458/558: Real-Time Systems (G. Manimaran) 6Finish time/number expressions (2)•Finish time for an inactive connection is:–F(i, k, t) = R(t) + P(i,k,t) * øi–Where F(i, k, t) is the finish number for the kth packet on connection “i’–Where, R(t) is the round number–P(i,k,t) is the size of the kth packet that arrives on connection “i” at time “t”–Where øi is the normalized weight ratio of the connection “i”.•Finish time for an active connection is:–F(i, k, t) = F(i, k-1,t) + P(i,k,t) * øi•The general expression for finish time is:–F(i, k, t) = Max ( F(i, k-1,t) , R(t) ) + P(i,k,t) * øiCprE 458/558: Real-Time Systems (G. Manimaran) 7Hierarchical Round Robin (HRR)•In HRR, there are number of levels, each with a fixed number of slots serviced in a round-robin fashion•A channel is allocated a given number of service slots at a selected level•The scheduler cycles through the slots at each level•The time taken to service all the slots at a given level is called the “frame time” at that level •The total link bandwidth is partitioned in among these levels•The key to HRR lies in its ability to give each level a constant share of the link’s bandwidthCprE 458/558: Real-Time Systems (G. Manimaran) 8Hierarchical Round Robin – contd.•The frame time for level 1, which is the smallest of all the levels, is the basic cycle time•If there are n1 slots in a level 1 frame, then b1 slots are allocated to higher levels, and the remaining (n1 – b1) slots are used for the level 1 connections•The frame time for level-1 = FT1 = n1•The frame time for level-2 = FT2 = (n1 / b1) * n2•Bandwidth allocated for a level i = (ni – bi) / FTiCprE 458/558: Real-Time Systems (G. Manimaran) 9HRR design for a 4Mbps linkLevel i nibiFTiSlot b/w1 4 1 4 1 Mbps2 4 1 16 250 Kbps3 2 0 32 125 KbpsL2 slotL3 slotb1n1Level 1Level 2Level 3b2CprE 458/558: Real-Time Systems (G. Manimaran) 10HRR – connection allocation exampleChannel BandwidthneedLevel Assigned# of slotsC1 2 Mbps 1 2C2 1 Mbps 1 1C3 250 Kbps 2 1C4 500 Kbps 2 2C5 125 Kbps 3 1C6 100 Kbps 3 1Level 3c1 c1 c2 L2c3 c4 c4 L3c5 c6b1n1Level 1Level 2 b2c1 c1 c2 c3 c1 c1 c2 c4 c1 c1 c2 c4 c1 c1 c2 c5HRR Schedule up to 16 slotsCprE 458/558: Real-Time Systems (G. Manimaran) 11Real-Time WAN -- Summary•QoS parameters – bandwidth, delay, delay jitter, packet loss•Traffic types – CBR and VBR•Traffic models – Peak rate model, LBAP•Real-time channel setup–QoS routing and Resource reservation•Data transmission phase–Traffic shaping: Leaky bucket, Token bucket–Packet scheduling: RR, WRR, WFQ,