Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1999-05-14
2002-11-05
Kizou, Hassan (Department: 2738)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S395400, C370S395410, C370S395430
Reexamination Certificate
active
06477169
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, a combined schedule is created by pipelined staging of multicast and unicast scheduling. Multicast cells are scheduled for transmission among multiple interfaces of a crossbar by performing a multicast cell scheduling cycle for multiple classes of service that are supported by the network device. Then, unicast cells are scheduled for transmission among the interfaces at a lower priority than the previously scheduled multicast cells by performing a unicast cell scheduling cycle for the multiple classes of service using only those interfaces that remain unmatched after completion of the multicast cell scheduling cycle.
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), Ljungbert 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: 6188690 (2001-02-01), Holden et al.
patent: 6201789 (2001-03-01), Witkowski et al.
patent: 6201792 (2001-03-01), Lahat
patent: 6259698 (2001-07-01), Shin et al.
patent: 6295295 (2001-09-01), Wicklund
patent: 6324165 (2001-11-01), Fan et al.
C. Minkenberg, “Intergrating Unicast and Multicast Traffic Sheduling in a Combined Input-and Output-Queued Packet-Switching System”, IEEE May 2000, p. 127-134.*
T. V. Lakshman, A. Bagchi, and K. Rastani, “A Fast Parallel for Resource Requests Implemented using Optical Devices”, IEEE 1992, p. 169-172.*
W. Y. Tseng and S. Y. Kuo, “A Combinational Media Access Protocol for Multicast Traffic in single-hop WDM LANS”IEEE Sep. 1998, p. 294-299.*
G. Nong and M. Hamdi, “On The Provision of Integrated QoS Guarantees of Unicast and Multicast Traffic Input-Queued Switches”, IEEE Global Telecommunication Conference, May 1999, p. 1742-1746.*
M. Andrews, S. Khanna, and K. Kumaran, “Integrated Scheduling of Unicast and Multicast Traffic in an Input-Queues Switch”, IEEE Jun. 1999, p. 1144-1151.
Angle Richard L.
Jagannath Shantigram V.
Ladwig Geoffrey B.
Yin Nanying
Blakely , Sokoloff, Taylor & Zafman LLP
Hoang Thai
Kizou Hassan
Nortel Networks Limited
LandOfFree
Multicast and unicast 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 Multicast and unicast scheduling for a network device, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Multicast and unicast scheduling for a network device will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2984423