Queuing and Scheduling

1. Queuing and Scheduling

🔍 When network congestion occurs, the exit interface might not be able to send packets fast enough. In such cases, the device temporarily stores excess packets in one or more queues until they can be transmitted. This is known as queuing.

• Scheduling: In more advanced queuing methods, scheduling determines the order in which packets are sent. It allows prioritization of certain types of traffic, which is essential in modern networks.

We’ll now explore the different queuing methods, starting with the simplest: FIFO.

2. FIFO (First In First Out)

🔍 FIFO is the default queuing method used by network devices. It transmits packets in the exact order they were received, without prioritization.

How FIFO Works

In the example below, the router receives four packets and transmits them in the same order they arrived. There’s no distinction between types of traffic; every packet is treated equally.

What Happens During Congestion?

🔍 When congestion occurs, excess packets are stored in a single queue for the interface. The scheduler processes these packets one by one in the order they arrived.

Take this example: two interfaces are receiving traffic that needs to be sent through the same interface, G0/3. If G0/3 becomes congested, the device buffers the packets and transmits them later when the interface becomes available.

Limitations of FIFO

⚠️ While FIFO is straightforward and works well in low-traffic networks, it has a major drawback: no prioritization. Critical traffic, like VoIP or video, is treated the same as less time-sensitive traffic, such as file transfers. This can lead to delays for applications that require low latency.

For more complex networks with diverse traffic needs, advanced queuing methods are necessary to provide prioritization and optimize performance.

📢 Now that we’ve covered FIFO, let’s move on to Priority Queuing (PQ), where traffic can be prioritized based on its importance. This ensures critical packets are transmitted before less urgent ones.

3. PQ (Priority Queuing)

🔍 Priority Queuing (PQ) introduces prioritization by dividing traffic into up to four queues, ranked by priority: High, Medium, Normal, and Low.

Key Components of PQ

At this stage, the queuing system consists of the following elements:

1. Classifier: Assigns packets to specific queues based on their priority.
   
2. Queues: Temporarily hold packets, categorized by priority.
   
3. Scheduler: Determines the transmission order, always prioritizing higher-priority queues.

How PQ Works

1. Classification: Packets are evaluated and placed into one of the four queues based on their priority level.
   
2. Transmission Order: The scheduler processes higher-priority queues first. For example:
   • Packets in the High-priority queue are always transmitted before packets in the Medium-priority queue.
     
3. Lower-Priority Queues: These queues are only serviced when all higher-priority queues are empty.

✅ This ensures that critical traffic, such as voice or video, is transmitted with minimal delay.

Risks of PQ

⚠️ While PQ is excellent for prioritizing important traffic, it has a significant limitation:

• Queue Starvation: Lower-priority queues can remain unprocessed if higher-priority queues are consistently full. For a lower-priority queue to send traffic, the higher-priority queue must first be empty. This can result in unfair bandwidth allocation and degraded performance for non-critical traffic.

Because of this risk, PQ is rarely used alone in modern networks. Instead, it is often combined with other methods to balance prioritization and fairness.

📢 Next, we’ll dive into Class-Based Weighted Fair Queuing (CBWFQ), a queuing method that guarantees fairness while still providing prioritization for different traffic types.

4. Class-Based Weighted Fair Queuing (CBWFQ)

🔍 CBWFQ is an advanced queuing method that builds on weighted round-robin scheduling. To fully understand how CBWFQ works, it’s essential to first grasp the concept of round-robin scheduling, as weighted round-robin builds directly on its foundation.

Understanding Round-Robin Scheduling

🔍 Round-robin scheduling is a simple and fair method where the scheduler cycles through all the queues in order, giving each queue an equal opportunity to send a packet.

Here’s an example:

1. Queue 1 sends packet 3.
2. Queue 2 sends packet 1.
3. Queue 3 sends packet 1.
4. Queue 4 sends packet 5.

This process repeats in a cyclical manner until all packets are transmitted.

However, in real-world networks, traffic isn’t always equally important. For example, delay-sensitive traffic like voice or video might require more bandwidth than file transfers. This is where Weighted Round-Robin (WRR) comes in, allowing you to allocate bandwidth more or less based on the priority of the traffic.

Introducing Weighted Round-Robin

🔍 When some types of traffic require more bandwidth than others, Weighted Round-Robin (WRR) offers a practical solution. It builds on the fairness of round-robin but assigns a weight to each queue, reflecting its bandwidth allocation.

✅ How Weighted Round-Robin Works

1. Weight Assignment: Each queue is given a percentage of the bandwidth based on its importance or traffic needs.
   • Queue 1: 50% of bandwidth
   • Queue 2: 25% of bandwidth
   • Queue 3: 20% of bandwidth
   • Queue 4: 5% of bandwidth
     
2. Proportional Allocation: The scheduler cycles through all queues, servicing them in proportion to their assigned weights. A higher weight means the queue sends more packets during each cycle.

✅ How CBWFQ Works

🔍 CBWFQ (Class-Based Weighted Fair Queuing) enhances traffic management by combining classification, queuing, and scheduling. It uses weighted round-robin scheduling to allocate bandwidth fairly and proportionally based on predefined weights, ensuring all traffic classes are treated appropriately.

📢 Next, we’ll explore LLQ (Low Latency Queuing), which combines CBWFQ with priority queuing for delay-sensitive traffic.

5. LLQ (Low Latency Queuing)

🔍 Low Latency Queuing (LLQ) is a powerful queuing method that combines the benefits of Priority Queuing (PQ) and Class-Based Weighted Fair Queuing (CBWFQ). It ensures both prioritization for delay-sensitive traffic and fairness for other traffic types.

Key Components of LLQ

• Priority Queue (PQ): Dedicated to delay-sensitive traffic like VoIP.
• CBWFQ: Handles all remaining traffic types using weighted round-robin scheduling.

Here’s a visual representation of how LLQ operates:

How LLQ Works

🔍 Priority Queue:

• The scheduler always services the priority queue first.
• Traffic in this queue, such as VoIP packets, is transmitted immediately to minimize latency and jitter.

🔍 CBWFQ Logic:

• After the priority queue is emptied, the scheduler switches to the remaining queues.
• These queues are serviced using CBWFQ logic, ensuring fairness across different traffic classes.

Bandwidth Limitation in LLQ

⚠️ To prevent queue starvation, LLQ applies a bandwidth cap to the priority queue. This ensures that other queues also get serviced.

• If the priority queue is limited to 50% of the interface bandwidth, any traffic exceeding this limit:
  • Dropped: Excess packets are discarded.
  • Re-marked: Packets may be downgraded to a lower-priority queue for processing.

This prevents the priority queue from monopolizing resources, ensuring that fairness is maintained for all traffic types.

✅ By integrating prioritization with fairness, LLQ addresses the challenges of real-time applications while maintaining network efficiency. Next, we’ll summarize the benefits of these queuing methods and when to use them.

6. Conclusion

📢 In this course, we explored various queuing methods:

1. FIFO: Simple but lacks prioritization.
   
2. PQ: Prioritizes traffic but risks starvation for lower-priority queues.
   
3. CBWFQ: Offers fairness with bandwidth guarantees but struggles with delay-sensitive traffic.
   
4. LLQ: Combines prioritization with fairness, ensuring low latency for critical applications.

Each method has its strengths and limitations, and the right choice depends on your network’s specific needs. LLQ is the most comprehensive solution, balancing fairness and low latency for modern networks.

📢 Next Steps: Now that we’ve covered queuing and scheduling, let’s move on to explore shaping and policing, two key techniques for controlling traffic rates and optimizing network performance.