Multiplex communications – Data flow congestion prevention or control
Reexamination Certificate
2002-09-04
2004-08-03
Vanderpuye, Kenneth (Department: 2666)
Multiplex communications
Data flow congestion prevention or control
C370S389000, C370S390000
Reexamination Certificate
active
06771596
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
The invention relates generally to the field of computer networking devices. More particularly, the invention relates to a method and apparatus for providing efficient unicast and multicast scheduling and high throughput for both unicast and multicast traffic. The method and apparatus may be embodied in a network device, such as a router or switch that employs input buffering and a switched backplane architecture.
2. Description of the Related Art
The current trend in high performance routers is away from shared backplanes that allow only a single bus transaction at a time (e.g., the transfer of one packet across the bus) and toward much faster switched backplanes that support multiple bus transactions at once (e.g., the forwarding of packets across the backplane by multiple ports simultaneously). For convenience, typically, packets are transferred across the switched backplane in fixed size “cells.” In this manner, the scheduling of the backplane's input and output ports may be synchronized in fixed size increments of time referred to herein as “time slots,” “cell scheduling cycles,” or “cell cycles.” A scheduling algorithm is employed to determine a “configuration” of the backplane for a particular time slot by identifying non-conflicting pairs of inputs and outputs which may be connected during the time slot. Because efficient scheduling of the backplane is important to the performance of the system as a whole, much time and effort has been spent developing and evaluating various scheduling approaches.
The recently developed ESLIP algorithm is an example of one of the more advanced scheduling approaches. The ESLIP algorithm is an enhanced version of iSLIP, an iterative unicast scheduling algorithm. Recognizing the importance of efficiently supporting multicast traffic, ESLIP combines unicast and multicast scheduling. The implementation of the ESLIP algorithm involves scheduling both unicast and multicast traffic simultaneously in a single scheduler. Consequently, to support multiple classes of service, the ESLIP scheduler needs to choose between competing unicast and multicast cells having the same priority. The ESLIP algorithm resolves contention between unicast and multicast cells of the same priority by alternating its preference between multicast and unicast each cell cycle. In this manner, both multicast and unicast traffic may be transferred across the backplane each cell cycle. During one cell cycle, unicast queues representing a particular priority are chosen to source a cell before multicast queues representing the same priority; and in the subsequent cell cycle, multicast cells are favored over unicast cells of equal priority. A more detailed description of ESLIP can be found in N. McKeown, “Fast Switched Backplane for a Gigabit Switched Router,” Cisco Systems white paper, November 1997.
While the ESLIP algorithm is admirable in terms of its performance, it has some limitations in terms of flexibility, predictability of scheduling delay, and variability of packet delay. With regard to flexibility, notably, there is no mechanism by which the frequency of multicast servicing can be varied. The fixed alternating priority scheme suggested by the ESLIP algorithm schedules both multicast and unicast traffic every time slot. With regard to delay, it is desirable to have guaranteed deterministic and bounded delay for a high priority multicast cell at the head of its queue. Additionally, it is advantageous to minimize the variability of packet delay. For example, output link scheduling can be made more efficient if low packet delay variability across the backplane can be achieved.
In addition, prior art schedulers have various other disadvantages that are overcome by aspects of the present invention, as described in the detailed description which follows.
BRIEF SUMMARY OF THE INVENTION
A method and apparatus for scheduling multicast data in an input-queued network device are described. According to one aspect of the present invention, the head-of-line blocking problem is avoided for multicast queues. A fabric arbiter receives a transmit request associated with multiple input ports. The transmit request identifies those of the output ports to which pending multicast cells are ready to be transmitted, if any. The fabric arbiter receives a backpressure signal from a backpressuring output port. Then, based upon the backpressure signal the fabric arbiter schedules multicast cells for transmission across the fabric. If the size of a multicast queue exceeds a predetermined threshold, then the fabric arbiter ignores the backpressure signal and causes the head-of-line multicast cell from the multicast queue to be transferred to the backpressuring output port. Otherwise, the fabric arbiter prevents multicast cells from being transferred to the backpressuring output port by masking requests destined for the backpressuring output port thereby removing the backpressuring output port from consideration during multicast scheduling.
Other features of the present invention will be apparent from the accompanying drawings and from the detailed description which follows.
REFERENCES:
patent: 5267235 (1993-11-01), Thacker
patent: 5493566 (1996-02-01), Ljungberg et al.
patent: 5500858 (1996-03-01), McKeown
patent: 5577035 (1996-11-01), Hayter et al.
patent: 5724351 (1998-03-01), Chao et al.
patent: 5742606 (1998-04-01), Iliadis et al.
patent: 5835491 (1998-11-01), Davis
patent: 5875190 (1999-02-01), Law
patent: 5978359 (1999-11-01), Caldara et al.
patent: 6141346 (2000-10-01), Caldara et al.
patent: 6157967 (2000-12-01), Horst et al.
patent: 6188690 (2001-02-01), Holden et al.
patent: 6201789 (2001-03-01), Witkowski
patent: 6201792 (2001-03-01), Lahat
patent: 6212182 (2001-04-01), McKeown
patent: 6259698 (2001-07-01), Shin et al.
patent: 6295295 (2001-09-01), Wicklund
patent: 6324165 (2001-11-01), Fan et al.
patent: 0785697 (1997-07-01), None
patent: 0687091 (1997-12-01), None
N. McKeown and T.E. Anderson, “A Quantitative Comparison Of Interative Scheduling Algorithms For Input-Queued Switches”, Internet Draft, pp 1-25.
N. W. McKeown, “Scheduling Algorithms For Input-Queued Cell Switches”, 1995 thesis, Graduate Division University of California at Berkeley, pp 1-119.
N. McKeown, P. Varaiya and J. Walrand, “Scheduling Cells In An Input-Queued Switch”, Internet Draft, Pub. in Electronis Letters, Dec./93, pp 1-4.
B. Prabhakar, N. McKeown and R. Ahuja, “Multicast Scheduling For Input-Queued Switches”, Internet Draft, pp 1-20.
B. Prabhakar, N. McKeown and J. Mairesse, “Teris Models For Multicast Switches”, Internet Draft, 6 pages.
N. McKeown and B. Prabhakar, “Scheduling Multicast Cells In An Input-Queued Switch”, Internet Draft, 8 pages.
A. Mekkittikul and N. McKeown, “A Starvation-Free Algorithm For Achieving 100% Throughput In An Input-Queued Switch”, Internet Draft, 6 pages.
B. Prabhakar and N. McKeown, “Designing A Multicast Switch Scheduler”, Internet Draft, pp 1-10.
N. McKeown, V. Anantharam and J. Warland, “Achieving 100% Throughput In An Input-Queued Switch”, Internet Draft, 7 pages.
N. McKeown, “Fast Switched Backplane For A Gigabit Switched Router”, White Paper, Nov., 1997, pp 1-30.
J.F. Hayes, R. Breault and M.K. Mehmet-Ali, “Performance Analysis Of A Multicase Switch”, IEEE Transactions On Communications, vol. 39, No. 4, Apr., 1991, pp 581-587.
J.Y. Hui and T. Renner, “Queueing Analysis For Multicasr Packet Switching”, IEEE Transactions On Communications, vol. 42, No. 2/3/4, 1994, pp 723-731.
P. Gupta and N. McKeown, “Design And Implementation Of A Fast Crossbar Scheduler”, Internet Draft, 8 pages.
S. Chuang, A. Goel, N. McKeown and B. Prabhakar, “Matching Output Queueing With A Combined Input Output Queued Switch”, Internet Draft, pp 1-25.
B. Prabhakar and N. McKeown, “On the Speedup Required For Combined Input And Output Queued Switching”, pp 1-13.
A. Hung, G Kesidia and N. McKeown, “ATM Input-Buffered Switches With The Guaranteed-Rate Property”, Internet Draft, 5 pages.
A. Mekkittikul and N. McKeown, “A Practical Scheduling
Angle Richard L.
Jagannath Shantigram V.
Ladwig Geoffrey B.
Yin Nanying
Blakely & Sokoloff, Taylor & Zafman
Nortel Networks Limited
Vanderpuye Kenneth
LandOfFree
Backpressure mechanism for a network device does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Backpressure mechanism for a network device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Backpressure mechanism for a network device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3283886