Course: COMP347 Computer Networks (Revision 10) | Textbook: Kurose & Ross, Computer Networking: A Top‑Down Approach (9th ed.)
Upon completion of this tutorial, students should be able to:
In packet‑switched networks, multiple packets often contend for the same output link. Queueing and scheduling are the mechanisms that determine which packets are transmitted next and which are dropped when the buffer is full. These mechanisms directly impact network performance, including latency, jitter, throughput, and fairness. Quality of Service (QoS) refers to the ability of the network to provide different levels of service to different traffic classes, ensuring that critical applications (e.g., VoIP, video conferencing) receive preferential treatment.
This tutorial covers the fundamentals of queueing and buffering, various scheduling algorithms (FIFO, Priority, Round‑Robin, WFQ), active queue management (RED, WRED, ECN), traffic shaping (token bucket, leaky bucket), and QoS architectures (IntServ, DiffServ). We also discuss congestion effects and advanced topics such as bufferbloat and queueing theory.
Routers buffer packets when the arrival rate exceeds the transmission rate. Buffers are finite; when a buffer is full, packets must be dropped. The choice of drop policy (tail drop vs. active queue management) and the size of the buffer significantly affect performance.
Key concepts:
The buffer size is often set to the bandwidth‑delay product (BDP) to absorb bursts.
FIFO is the simplest scheduler: packets are transmitted in the order they arrive. It has no concept of priority or fairness. FIFO is easy to implement but can cause head‑of‑line blocking and does not differentiate between traffic classes. It is suitable for networks with homogeneous traffic and no QoS requirements.
Priority queueing uses multiple queues, each with a different priority level. Higher‑priority queues are served before lower‑priority ones. This ensures that critical traffic (e.g., VoIP) experiences low delay. However, low‑priority traffic can be starved if high‑priority traffic is heavy. Strict priority queueing is often used with rate limiters to prevent starvation.
Round‑Robin serves each queue in a cyclic order, ensuring fairness among flows. Weighted Round‑Robin assigns weights to queues, allowing different bandwidth allocations. For example, a queue with weight 2 gets twice the service of a queue with weight 1. WRR is simple and provides fairness, but it does not guarantee fair allocation for variable‑length packets (unless byte‑based).
WFQ is a more sophisticated algorithm that approximates a "fluid" fairness model. It emulates a bit‑by‑bit round‑robin (BRR) by computing a virtual finish time for each packet. WFQ provides strict fairness, ensuring that each flow gets a share of bandwidth proportional to its weight. It also bounds the delay for each flow. However, WFQ is computationally complex.
Key formula (for a single server): Each packet is assigned a virtual finish time based on its arrival time, size, and weight. Packets are transmitted in increasing order of finish times.
AQM proactively drops (or marks) packets before the buffer is full to signal congestion to TCP senders, avoiding global synchronization.
Traffic shaping controls the rate at which traffic is transmitted, smoothing bursts.
Congestion occurs when the demand exceeds the available capacity. Effects include increased queueing delay, packet loss, and reduced throughput. Congestion control mechanisms (e.g., TCP congestion control, AQM, and rate limiting) work together to manage congestion.
Q1. Which scheduling algorithm provides the simplest implementation but offers no fairness or priority?
C) FIFO
Q2. In Priority Queueing, what is the main risk for low‑priority traffic?
A) Excessive delay or starvation
Q3. Which scheduling algorithm approximates a bit‑by‑bit round‑robin and provides fair bandwidth allocation?
C) WFQ
Q4. What does RED stand for?
B) Random Early Detection
Q5. ECN (Explicit Congestion Notification) works by:
B) Marking packets to indicate congestion
Q6. The Leaky Bucket traffic shaper enforces:
A) A constant output rate
Q7. The Token Bucket allows:
B) Bursts up to the bucket capacity
Q8. Which QoS architecture uses RSVP for per‑flow resource reservation?
B) IntServ
Q9. Differentiated Services (DiffServ) uses which field in the IP header?
B) DSCP
Q10. In WFQ, the weight of a queue determines:
B) The share of bandwidth proportional to weight
Q11. Bufferbloat refers to:
B) Excessively large buffers causing high latency
Q12. The average queue length in an M/M/1 queue is given by:
B) L = ρ/(1‑ρ) where ρ = λ/μ.
Q13. Which of the following is NOT a benefit of AQM?
C) Increasing throughput regardless of congestion
Q14. In WRR, if queue A has weight 3 and queue B has weight 1, what fraction of bandwidth does queue A get?
B) 3/4
Q15. The purpose of the min_th and max_th thresholds in RED is to:
B) Determine the drop probability profile
Q16. In a Token Bucket, the average output rate is determined by:
B) The token generation rate
Q17. Which DiffServ Per‑Hop Behavior (PHB) is typically used for best‑effort traffic?
C) BE
Q18. In IntServ, the service model that provides a guaranteed rate and bounded delay is called:
B) Guaranteed Service
Q19. Head‑of‑line (HOL) blocking is a problem associated with:
B) Input queueing
Q20. Which of the following is a disadvantage of Strict Priority Queueing?
A) It can starve lower‑priority traffic
Q21. In an M/M/1 queue, the utilization (ρ) is defined as:
A) λ / μ
Q22. Which scheduling algorithm provides the fairest allocation of bandwidth among competing flows?
C) WFQ
Q23. The Leaky Bucket is often used for:
A) Policing traffic at the network edge
Q24. ECN uses which bits in the IP header?
B) ECN (bits 6 and 7 of the TOS/TC field)
Q25. In RED, the drop probability increases linearly between min_th and max_th. What is the probability at max_th?
B) 1 (all packets are dropped)
Q26. Which QoS architecture is most scalable for large networks?
B) DiffServ
Q27. The main purpose of traffic shaping is to:
B) Smooth traffic bursts and enforce rate limits
Q28. Which of the following is an example of a Per‑Hop Behavior (PHB) in DiffServ?
B) Expedited Forwarding (EF)
Q29. In WFQ, what is the virtual finish time of a packet?
B) A computed value used to order packets for fair transmission
Q30. Bufferbloat is primarily caused by:
B) Overly large buffers combined with TCP's congestion control
Q31. Explain the difference between tail drop and RED.
Tail drop discards packets only when the buffer is full, causing global synchronization. RED proactively drops packets probabilistically based on average queue length, signaling congestion earlier and reducing synchronization.
Q32. How does WFQ provide fairness among flows?
WFQ emulates a bit‑by‑bit round‑robin by assigning virtual finish times to each packet based on its arrival time, size, and weight. It transmits packets in increasing finish time order, ensuring each flow receives a share of bandwidth proportional to its weight.
Q33. What is the purpose of the token bucket in traffic shaping?
The token bucket allows traffic to have an average rate (determined by token generation) and a maximum burst (determined by bucket size). It provides flexible rate control while allowing bursts within limits.
Q34. Compare and contrast IntServ and DiffServ.
IntServ provides per‑flow QoS with resource reservation (RSVP), offering guaranteed services but lacking scalability. DiffServ aggregates traffic into classes and applies per‑hop behaviors, using DSCP marking; it is scalable but offers coarse‑grained QoS.
Q35. What is bufferbloat and how can it be mitigated?
Bufferbloat is the high latency caused by oversized buffers in network devices. It can be mitigated by using Active Queue Management (RED, CoDel) and by configuring smaller buffer sizes.
Q36. A router uses FIFO with a buffer of 100 packets. Traffic arrives at a rate of 800 packets/sec and is transmitted at 1000 packets/sec. What is the average queue length? Is this stable?
λ = 800, μ = 1000, ρ = 0.8. Average queue length (M/M/1) = ρ/(1‑ρ) = 0.8/0.2 = 4 packets. Stable because ρ < 1.
Q37. An administrator wants to ensure that VoIP traffic gets low latency and data traffic gets the remaining bandwidth. Which scheduling algorithm should they use and why?
Priority Queueing with VoIP in the high‑priority queue and data in a lower‑priority queue. However, to prevent starvation of data, rate limiting on VoIP or using WRR with high weight for VoIP could be used. Alternatively, DiffServ with EF for VoIP and AF for data.
Q38. A RED router has min_th = 30 packets, max_th = 60 packets, and max_p = 0.1. What is the drop probability when the average queue length is 45 packets?
Drop probability = max_p * (avg - min_th) / (max_th - min_th) = 0.1 * (45‑30)/(60‑30) = 0.1 * 15/30 = 0.05 = 5%.
Q39. A token bucket has a token rate of 1 Mbps and a bucket size of 10 KB. A sender wants to transmit a 20 KB file. How long will it take to send the file (assuming burst possible)?
The bucket can hold up to 10 KB, so the first 10 KB can be sent immediately (burst). The remaining 10 KB must wait for tokens at 1 Mbps, which takes 10 KB / 1 Mbps = 10 * 8 kb / 1000 kbps = 0.08 seconds? Actually, 10 KB = 80 kb. 80 kb / 1000 kbps = 0.08 s. Total = initial burst (negligible) + 0.08 s = 0.08 s.
Q40. Why does WFQ require per‑packet state? How does this affect scalability?
WFQ must track the finish time for each packet, which requires maintaining state per flow or per queue. This increases memory and processing overhead, making WFQ less scalable than simpler algorithms like WRR or FIFO for large numbers of flows.
Q41. A router experiences high jitter for VoIP traffic. Which scheduling change could reduce jitter?
Use Priority Queueing for VoIP or ensure that VoIP traffic is assigned to a low‑delay queue (e.g., with EF PHB in DiffServ). Additionally, using WFQ with low weight for other traffic can provide consistent service.
Q42. Explain how ECN helps in avoiding packet loss during congestion.
ECN marks packets (sets CE bit) instead of dropping them. The receiver echoes this to the sender via TCP ECN‑Echo, and the sender reduces its rate. This avoids retransmissions and reduces latency.
Q43. A network uses strict priority queueing. What happens if high‑priority traffic consumes 90% of the link, and low‑priority traffic is heavy?
Low‑priority traffic will be starved (very high delay or dropped). This is a disadvantage of strict priority; rate limiting high‑priority traffic or using WRR could prevent starvation.
Q44. Why is the average queue length used in RED instead of the instantaneous queue length?
Using the average queue length smoothes out transient bursts and avoids dropping packets unnecessarily during short bursts. It provides a more stable indication of persistent congestion.
Q45. In WRR, if queue 1 has weight 2 and queue 2 has weight 3, and both have packets, what is the bandwidth ratio between queue 1 and queue 2?
Queue 1 gets 2/(2+3) = 40%, queue 2 gets 3/(2+3) = 60%. Ratio = 2:3.
Q46. What is the role of policing vs. shaping in traffic management?
Policing drops or marks packets that exceed a rate limit, applied at the ingress. Shaping buffers excess traffic to smooth it out, applied at the egress. Shaping introduces delay but no loss; policing may cause loss.
Q47. How does DiffServ handle traffic classification?
DiffServ marks packets with a DSCP value at the edge. Intermediate routers use the DSCP to select a PHB (e.g., EF, AF) and apply appropriate queueing and scheduling.
Q48. A link has a capacity of 10 Mbps. WFQ is used with three flows: weights 1, 2, and 3. What are the guaranteed rates for each?
Total weight = 1+2+3=6. Rates: 10/6*1 = 1.67 Mbps, 10/6*2 = 3.33 Mbps, 10/6*3 = 5 Mbps.
Q49. What is the difference between the leaky bucket and the token bucket?
The leaky bucket enforces a constant output rate, dropping packets that exceed the buffer. The token bucket allows bursts up to the bucket size and enforces an average rate, but does not drop packets (they wait for tokens).
Q50. Why is WFQ considered to provide better fairness than WRR for variable‑length packets?
WRR (packet‑based) can be unfair because larger packets get more bandwidth than smaller ones in a round. WFQ uses bit‑by‑bit round‑robin (or virtual finish times) to ensure that each flow gets its fair share regardless of packet size.
Calculate the average queue length and average waiting time in an M/M/1 queue with arrival rate λ = 500 packets/sec and service rate μ = 800 packets/sec.
ρ = λ/μ = 500/800 = 0.625. L = ρ/(1‑ρ) = 0.625/0.375 = 1.667 packets. W = 1/(μ‑λ) = 1/(800‑500) = 1/300 = 0.00333 s = 3.33 ms.
A router uses Priority Queueing with 3 classes: High (VoIP), Medium (Video), Low (Data). High has 10% of traffic, Medium 30%, Low 60%. If the link is 100 Mbps, and all queues are full, what is the maximum rate for each class? What is the issue?
Strict priority: High gets up to 100 Mbps, Medium gets nothing if High is busy, Low gets nothing if High or Medium are busy. This can starve Medium and Low. To prevent starvation, rate limiters should be used.
Given RED parameters: min_th = 20, max_th = 40, max_p = 0.2. What is the drop probability when the average queue length is 30?
p = max_p * (avg - min_th) / (max_th - min_th) = 0.2 * (30‑20)/(40‑20) = 0.2 * 10/20 = 0.1 = 10%.
A token bucket has rate r = 2 Mbps, bucket size b = 1 MB. A source sends a file of 5 MB. How long will it take to send the file if the bucket is initially full? What is the average throughput?
Burst = 1 MB at start, remaining 4 MB at 2 Mbps = 4 MB / 2 Mbps = 4*8 Mb / 2 Mbps = 16 seconds. Total time = 1 MB burst (negligible time) + 16 s = 16 s (plus a small burst time). Average throughput = 5 MB / 16 s = 0.3125 MB/s = 2.5 Mbps? Actually 5 MB = 40 Mb, 40 Mb / 16 s = 2.5 Mbps. But the token rate is 2 Mbps, so the average is 2 Mbps. Wait: 5 MB / 16 s = 0.3125 MB/s = 2.5 Mbps, which exceeds 2 Mbps because of the burst. The average over long time is 2 Mbps.
Compare FIFO, Priority Queueing, and WFQ in terms of: (a) Fairness, (b) Implementation complexity, (c) Delay guarantees.
FIFO: no fairness, simple, no guarantees. Priority: unfair (starvation), moderately complex, guarantees low delay for high priority. WFQ: fair, complex, provides bounded delay and rate guarantees.
In WFQ, if there are 4 flows with weights 1, 2, 3, 4, and the link capacity is 10 Mbps, what are the guaranteed bandwidths?
Total weight = 10. Rates: 1/10*10=1 Mbps, 2/10*10=2 Mbps, 3/10*10=3 Mbps, 4/10*10=4 Mbps.
Explain how ECN works in conjunction with RED. What are the benefits?
RED is configured to mark packets instead of dropping when congestion is detected (by setting the CE bit). The receiver echoes this to the sender via TCP ECN‑Echo, and the sender reduces rate. Benefits: no packet loss, less retransmission, lower latency.
A leaky bucket has a capacity of 10 packets and leaks at 1 packet per second. If 20 packets arrive in a burst, how many are dropped? How long does it take to drain?
Bucket capacity 10, so 10 packets are dropped (the excess). The remaining 10 packets leak at 1 packet/s, taking 10 seconds to drain.
Design a DiffServ policy for a network with three traffic classes: Voice (low delay, low jitter), Video (high bandwidth, moderate delay), and Best‑Effort (data). Assign DSCP values and describe PHBs.
Voice: EF (Expedited Forwarding, DSCP 46), Video: AF4 (Assured Forwarding class 4 with low drop precedence), Best‑Effort: default (DSCP 0). Use PQ for EF and WRR for AF classes.
Given an M/M/1 queue with arrival rate 200 pps and service rate 250 pps, what is the probability that the queue has more than 5 packets? (Use formula P(N>n) = ρ^(n+1)).
ρ = 200/250 = 0.8. P(N > 5) = ρ^6 = 0.8^6 = 0.262144.
Compare the leaky bucket and token bucket in terms of burst tolerance.
Leaky bucket: no burst tolerance; constant rate. Token bucket: allows bursts up to bucket size; average rate is token rate.
How does weighted round‑robin differ from strict priority queueing?
WRR provides a weighted share of bandwidth to each queue; no queue is starved. Strict priority gives absolute priority to higher‑priority queues, which can starve lower‑priority ones.
An RED router has min_th=15, max_th=45, max_p=0.15. What is the drop probability at avg=30? At avg=10? At avg=50?
At 30: p = 0.15*(30‑15)/(45‑15)=0.15*15/30=0.075=7.5%. At 10 (below min_th): p=0. At 50 (above max_th): p=1 (all dropped).
IntServ uses RSVP for signaling. What are the advantages and disadvantages of IntServ compared to DiffServ?
Advantages: per‑flow QoS, guaranteed services. Disadvantages: scalability (state per flow), complexity. DiffServ is scalable but coarse.
A network admin wants to limit a particular user's traffic to 1 Mbps average with bursts up to 2 MB. Design a token bucket configuration.
Token rate r = 1 Mbps. Bucket size b = 2 MB = 16 Mb. The bucket can hold 16 Mb, allowing bursts up to 2 MB while average is 1 Mbps.
Research the history of Active Queue Management. Write a 500‑word essay covering RED, ECN, and CoDel.
RED was introduced by Floyd and Jacobson in 1993. ECN (RFC 3168) added marking. CoDel (Controlled Delay) is a newer AQM that uses queuing delay as a metric. Each has contributed to reducing bufferbloat and improving TCP performance.
Explain the concept of "fairness" in queueing. How do WRR and WFQ achieve fairness? What are the trade‑offs?
Fairness means each flow gets an equal or weighted share of bandwidth. WRR achieves fairness by serving queues cyclically with weights, but is packet‑size dependent. WFQ achieves bit‑level fairness using virtual finish times, but is more complex.
Describe the Integrated Services (IntServ) architecture, its components, and the RSVP protocol. Discuss its scalability issues.
IntServ uses RSVP for signaling, providing guaranteed and controlled‑load services. It maintains per‑flow state in routers, which does not scale to large networks.
Compare and contrast DiffServ and IntServ. Which one is more suitable for the Internet core and why?
DiffServ is more suitable for the Internet core because it aggregates traffic and is scalable. IntServ is better suited for enterprise networks with limited flows.
Design a QoS policy for a corporate network with VoIP, video conferencing, web browsing, and file transfers. Justify your scheduling and marking choices.
VoIP: EF, high priority queue (strict priority or high weight). Video: AF4, WRR with moderate weight. Web: AF1. File transfers: Best‑Effort. Use rate limiting on priority queues to prevent starvation.
Explain the concept of "bufferbloat" and describe how AQM techniques like RED and CoDel address it.
Bufferbloat is high latency due to oversized buffers. RED drops early to keep queues small; CoDel uses queuing delay to mark/drop packets, reducing latency.
Calculate the maximum burst size for a token bucket with rate r=2 Mbps and bucket size b=1 MB. If a burst of 1.5 MB arrives, what happens?
Max burst = b = 1 MB. A 1.5 MB burst: first 1 MB is sent immediately, remaining 0.5 MB waits for tokens at 2 Mbps, taking 0.5 MB / 2 Mbps = 4 Mb / 2 Mbps = 2 seconds.
Write a detailed explanation of the Weighted Fair Queueing algorithm, including how virtual finish times are computed.
WFQ uses a fluid model: each flow has a weight. The algorithm computes a virtual time and assigns each packet a finish time = max(virtual arrival time, previous finish time) + packet size / weight. Packets are transmitted in increasing finish time.
Discuss the role of queuing and scheduling in providing Quality of Service. How do they interact with congestion control mechanisms?
Queueing and scheduling determine per‑packet delay and loss. Congestion control (e.g., TCP) reacts to loss/ECN. AQM and scheduling together provide differentiated QoS and signal congestion.
Research the different Per‑Hop Behaviors (PHBs) in DiffServ: EF, AF, and BE. Describe the recommended use cases for each.
EF: low delay, low loss (VoIP). AF: assured bandwidth with drop precedence (video, business data). BE: best effort (web, email).
Explain how ECN interacts with TCP. What are the benefits of using ECN over RED alone?
TCP uses ECN‑Echo and CWR flags. Benefits: avoids loss, reduces retransmissions, lowers latency, and maintains high throughput.
An M/M/1 queue has arrival rate 300 pps and service rate 400 pps. What is the probability that the queue length exceeds 10 packets? What is the average waiting time?
ρ = 0.75. P(N>10) = ρ^11 = 0.75^11 ≈ 0.0422. W = 1/(400‑300) = 0.01 s = 10 ms.
Compare the performance of Strict Priority Queueing and Weighted Fair Queueing in terms of delay for high‑priority traffic and fairness for low‑priority traffic.
Strict priority gives low delay to high‑priority but can starve low‑priority. WFQ provides guaranteed bandwidth and delay bounds for all traffic, but high‑priority traffic may experience slightly higher delay than strict priority.
Describe the leaky bucket algorithm and its applications in policing. What are the limitations?
Leaky bucket enforces constant output rate. Applications: policing traffic at network edge. Limitations: no burst tolerance, drops excessive traffic.
Discuss the future of QoS in the era of SDN and programmable data planes. How can SDN enable more dynamic QoS?
SDN controllers can program flow tables with custom QoS policies, adapt to real‑time traffic conditions, and allocate bandwidth dynamically. P4 can implement custom scheduling algorithms.
This tutorial has provided a comprehensive exploration of queueing, scheduling, and QoS fundamentals. Key takeaways:
Understanding these principles is essential for designing and operating high‑performance networks. In the next tutorial, we will cover data‑plane security and operational considerations.