In recent years, queuing schedulers have been widely used in networks to meet performance requirements of real-time applications, such as voice and video transmissions.
A. First-In First-Out (FIFO)
Historically, early communication routers used a First-in First-out (FIFO) queuing procedure at each output port. In FIFO, a single queue is maintained at each output port. When a new packet arrives, it is placed at the end of the queue. As long as the queue is not empty, the router transmits packets from the queue, taking the packet from the beginning of the queue (taking the “oldest” packet). Thus, FIFO provides a simple best-effort service to all applications using the Internet.
Despite the advantages of simplicity and robustness, FIFO may not be the optimum queuing procedure for real time applications, such as voice or video. It is often important to distinguish between communications that require real-time responses (such as voice, video, and other premium services), and communications that do not require real-time responses (such as email and file transfer which may only require a “best-effort” service). In other words, different communication services generally are not equally important, and therefore should be treated differently. The capability to provide service differentiations among application types and/or among users in a network is often referred to as quality of service (QoS).
FIFO has some serious drawbacks, especially in the field of communications. First, a “greedy source” that sends packets at extremely high-speed may crowd out other sources, and obtain more bandwidth than other sources. Second, if a number of shorter packets are behind very long packets, the FIFO scheme results in a longer average delay (per packet) than if the shorter packets were transmitted before the longer packet. Third, under the FIFO scheme, there is no means to give special treatment to high priority sources such as delay-sensitive voice or video packets.
In order to overcome these drawbacks, today's communication routers typically maintain multiple queues for each output port. If there are three classes of services (high, low, and medium), then voice and video packets may be placed in the high-class queue, and packets from the best-effort service can be placed in the medium or low class queue, depending on the importance of data.
When there are multiple queues and/or classes, a system designer must determine how to schedule packets among multiple queues. This has been an active area of research, and some effective scheduling algorithms have been proposed. Today, scheduling algorithms are not only widely used in routers/switches, but also various modems, WiFi access points (APs), base stations, PDSN, and many other networking equipment.
B. Simplest Scheduler: Round Robin Scheduler
The simplest scheduler is a round robin scheduler. A round robin scheduler maintains one queue for each class, and serves each queue in round-robin fashion, taking one packet (of any size) from each non-empty queue in turn. This round robin scheduler prevents a high-speed source from arbitrarily increasing its share of the bandwidth and causing the delay of other sources. In fact, under the round-robin scheme, when a source sends too many packets too fast, it merely increases the length of its own queue (assuming that a single source is constrained to a single queue). Even though the round robin scheme reduces the problem caused by high-speed sources producing many packets, the round robin scheduler does not consider packet size. Note that packet size is sometimes referred to as packet length.
In a round robin scheduler, a source sending long packets generally gets more bandwidth than a source sending short packets. In other words, the round-robin scheme is fair in terms of number of packets per queue, but might not be fair in terms of bandwidth per queue. Furthermore, a round-robin scheduler does not have a means to give more bandwidth to one queue over another queue.
C. Other Schedulers: WFQ, DRR, and WRR
The prior art includes numerous methods for allocating bandwidth among queues. Weighted fair queuing (WFQ), deficit round robin (DRR), and weighted round robin (WRR) are the most widely used methods for IP-based data network schedulers. Schedulers are used in many types of networking equipment, such as: modems, WiFi access points (APs), base stations, packet data serving nodes (PDSNs), routers/switches, etc.
DRR and WRR schedulers serve each queue in round-robin fashion, but a fixed amount of credit is given to each queue. Each queue is allowed to send up to the given credit in each turn. Therefore, fairness in terms of bandwidth among the queues may be obtained.
The credit-based approach is also able to give preference to one queue over the other queues, by assigning different amounts of credit to different queues. For example, if there are three queues, a scheduler may assign a different credit to each queue: a 900 byte credit for the first queue, a 450 byte credit for the second queue, and a 150 byte credit for the third queue (instead of 500 bytes each for all three queues). Packets are sent from each queue unless or until transmission would exceed the credit. Any unused credit may be carried over and added to the new credit for the next cycle. In this example, the bandwidth is effectively allocated (60%, 30% and 10%) among the three queues, thereby differentiating among the queues.
Thus, in credit-based schedulers such as DRR and WRR, a credit or weight is given to each queue in order to achieve a desired bandwidth allocation among the queues. The size of the credit or weight can have a significant impact on the performance of the scheduler, as will be discussed below in connection with the figures. Until now, however, no effective solution exists on how to adjust the size of the credits. Desired are simple and effective methods to dynamically adjust the size of credits for a credit based schedulers, so that the performance of the scheduler is improved.
USPTO Backgrounds
USPTO Backgrounds