Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2001-08-14
2004-06-29
Chin, Wellington (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S229000
Reexamination Certificate
active
06757246
ABSTRACT:
CROSS-REFERENCE TO RELATED APPLICATIONS
The present invention is related to following applications: “Method and Apparatus for Parallel, Weighted Arbitration Scheduling for a Switch Fabric” [Attorney Docket-ZGRO 001/00US], and “Method and Apparatus for Arbitration Scheduling with a Penalty for a Switch Fabric” [Attorney Docket-ZGRO 003/000US], both of which are incorporated herein by reference.
BACKGROUND OF THE INVENTION
The present invention relates generally to telecommunication switches. More specifically, the present invention relates to parallel, weighted arbitration scheduling for a switch fabric (e.g., an input-buffered switch fabric).
Known switch fabrics with crossbar architectures exist where data cells received on the multiple input ports of the switch are sent to the various output ports of the switch. Scheduling techniques ensure that the data cells received from different input ports are not sent to the same output port at the same time. These techniques determine the temporary connections between input ports and output ports, via the switch fabric, for a given time slot.
Scheduling techniques can be evaluated based on a number of performance requirements to a broad range of applications. Such performance requirements can include, for example, operating at a high speed, providing a high throughput (i.e., scheduling the routing of as many data cells as possible for each time slot), guaranteeing quality of service (QoS) for specific users, and being easily implemented in hardware. Known scheduling techniques trade one or more performance areas for other performance areas.
For example, U.S. Pat. No. 5,500,858 to McKeown discloses one known scheduling technique for an input-queued switch. This known scheduling technique uses rotating priority iterative matching to schedule the routing of data across the crossbar of the switch fabric. When the data cells are received at the input ports in a uniform manner (i.e., in a uniform traffic pattern), this known scheduler can produce a high throughput of data cells across the switch fabric. When the data cells are received at the input ports, however, in a non-uniform manner more typical of actual data traffic, the throughput from this known scheduling technique substantially decreases.
Thus, a need exists to provide a scheduling technique that can perform effectively for multiple performance requirements, such as for example, operating at a high speed, providing a high throughput, guaranteeing QoS, and being easily implemented in hardware.
SUMMARY OF THE INVENTION
Scheduling is performed for a switch fabric (e.g., an input-buffered switch fabric). A first input port from a set of input ports is selected, for a first output port, based on a weight value uniquely associated with each link from a first set of links. Each link from the first set of links are between the first output port and a unique input port from the set of input ports. A second output port from a set of output ports is selected for a second input port.
REFERENCES:
patent: 5267235 (1993-11-01), Thacker
patent: 5493566 (1996-02-01), Ljungberg et al.
patent: 5495474 (1996-02-01), Olnowich et al.
patent: 5500858 (1996-03-01), McKeown
patent: 5517495 (1996-05-01), Lund et al.
patent: 5581566 (1996-12-01), St. John et al.
patent: 5689508 (1997-11-01), Lyles
patent: 5689644 (1997-11-01), Chou et al.
patent: 5699520 (1997-12-01), Hodgson et al.
patent: 5748629 (1998-05-01), Caldara et al.
patent: 5815489 (1998-09-01), Takatori et al.
patent: 5850399 (1998-12-01), Ganmukhi et al.
patent: 5867705 (1999-02-01), Mano
patent: 5912889 (1999-06-01), Preas et al.
patent: 5923644 (1999-07-01), McKeown et al.
patent: 5923656 (1999-07-01), Duan et al.
patent: 6014367 (2000-01-01), Joffe
patent: 6032218 (2000-02-01), Lewin et al.
patent: 6044061 (2000-03-01), Aybay et al.
patent: 6069893 (2000-05-01), Parruck et al.
patent: 6072772 (2000-06-01), Charny et al.
patent: 6097705 (2000-08-01), Ben-Michael et al.
patent: 6134217 (2000-10-01), Stiliadis et al.
patent: 6185221 (2001-02-01), Aybay
patent: 6188690 (2001-02-01), Holden et al.
patent: 6198723 (2001-03-01), Parruck et al.
patent: 6240102 (2001-05-01), Asano
patent: 6359861 (2002-03-01), Sui et al.
patent: 6442135 (2002-08-01), Ofek
patent: 6563837 (2003-05-01), Krishna et al.
patent: 2328590 (1999-02-01), None
patent: WO 99/14916 (1999-03-01), None
patent: WO 99/35792 (1999-07-01), None
patent: WO 99/43131 (1999-08-01), None
patent: WO 99/66677 (1999-12-01), None
patent: WO 00/38375 (2000-06-01), None
patent: WO 00/38376 (2000-06-01), None
McKeown, Nick, “iSLIP: A Scheduling Algorithm for Input-Queued Switches”,IEEE Transactions on Networking, Vol. 7, No. 2, Apr. 1999, pp. 1-36.
A. C. Kam et al., “Linear complexity algorithms forQoS support in input-queued switches with no speedup”, d'Arbeloff Laboratory for Information Systems and Technology, Massachusetts Institute of Technology, pp. 1-34.
T. E. Anderson et al., “High Speed Switch Scheduling for Local Area Networks”, Digital System Research Center, Palo Alto California, Apr. 26, 1993, pp. 1-37.
A. Mekkittkul et al., “A Practical Scheduling Algorithm to Achieve 100% Throughput in Input-Queued Switches”,IEEE Infocom 98, Vol., 2, pp. 792-799, Apr. 1998, San Francisco, CA.
Alasti Mehdi
Sayrafian-Pour Kamran
Tabatabaee Vahid
Chin Wellington
Martine & Penilla LLP
PTS Corporation
Schultz William
LandOfFree
Method and apparatus for weighted arbitration scheduling... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for weighted arbitration scheduling..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for weighted arbitration scheduling... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3335228