Programmable multicast scheduling for a network device

Details Programmable multicast scheduling for a network device Programmable multicast scheduling for a network device

1999-05-14

2003-09-30

Patel, Ajit (Department: 2664)

Multiplex communications

Pathfinding or routing

Combined circuit switching and packet switching

C370S432000, C370S429000

Reexamination Certificate

active

06628646

ABSTRACT:

COPYRIGHT NOTICE
Contained herein is material that is subject to copyright protection. The copyright owner has no objection to the facsimile reproduction of the patent disclosure by any person as it appears in the Patent and Trademark Office patent files or records, but otherwise reserves all rights to the copyright whatsoever.
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 unicast and multicast data in an input-queued network device are described. According to one aspect of the present invention, multicast scheduling is triggered by a programmable parameter. Each scheduling timeslot of a set of possible scheduling timeslots, unicast cell scheduling is performed. Multicast cell scheduling is performed in parallel with and independent of the unicast cell scheduling during scheduling timeslots in which a programmable multicast scheduling frequency parameter satisfies a predetermined condition.
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 et al.
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), Witkovski et al.
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.
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 Multicast Switch”, IEEE Transactions On Communications, vol. 39, No. 4, Apr., 1991, pp 581-587.
J.Y. Hui and T. Renner, “Queueing Analysis For Multicast 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 Kesidis and N. McKeown, “ATM Input-Buffered Switches With The Guaranteed-Rate Property”, Internet Draft, 5 pages.
A. Mekkittikul and N. McKeown, “A Practical Scheduling Algorithm To Achieve 100% Throughput In Input-Queued Switches”, Internet Draft, 8 pages.
N. McKeown, B. Prabhakar and M. Zhu, “Matching Output Queueing With Combined Input And Output Queueing”, Internet Draft, 9 pages.
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, “Tetris 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. Walrand, “Achieving 100% Throughput In An Input-Queued Switch”, Internet Draft, 7 pages.
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 Swithces”, 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 Electronics Letters, Dec./93, pp 1-4.

Affiliated with

Also associated with

Rating

Programmable multicast scheduling 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 Programmable multicast scheduling for a network device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Programmable multicast scheduling for a network device will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3083265