Scheduling the dispatch of cells in multistage switches...

Details Scheduling the dispatch of cells in multistage switches... Scheduling the dispatch of cells in multistage switches...

2006-09-05

2006-09-05

Phan, Man U. (Department: 2616)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S388000, C370S395430, C370S429000

Reexamination Certificate

active

07103056

ABSTRACT:
A multiple phase cell dispatch scheme, in which each phase uses a simple and fair (e.g., round robin) arbitration methods, is described. VOQs of an input module and outgoing links of the input module are matched in a first phase. An outgoing link of an input module is matched with an outgoing link of a central module in a second phase. The arbiters become desynchronized under stable conditions which contributes to the switch's high throughput characteristic. Using this dispatch scheme, a scalable multiple-stage switch able to operate at high throughput, without needing to resort to speeding up the switching fabric and without needing to use buffers in the second stage, is possible. The cost of speed-up and the cell out-of-sequence problems that may occur when buffers are used in the second stage are therefore avoided. A hierarchical arbitration scheme used in the input modules reduces the time needed for scheduling and reduces connection lines.

REFERENCES:
patent: 5495474 (1996-02-01), Olnowich et al.
patent: 5889775 (1999-03-01), Sawicz et al.
patent: 6125112 (2000-09-01), Koning et al.
patent: 6285679 (2001-09-01), Dally et al.
patent: 6473428 (2002-10-01), Nichols et al.
patent: 6477169 (2002-11-01), Angle et al.
patent: 6563837 (2003-05-01), Krishna et al.
patent: 6657959 (2003-12-01), Chong et al.
patent: 6661773 (2003-12-01), Pelissier et al.
patent: 6747971 (2004-06-01), Hughes et al.
patent: 6816487 (2004-11-01), Roberts et al.
patent: 6940851 (2005-09-01), Oki et al.
patent: 2002/0061020 (2002-05-01), Chao et al.
patent: 2002/0176431 (2002-11-01), Golla et al.
patent: 2002/0181483 (2002-12-01), Oki et al.
patent: 2003/0007498 (2003-01-01), Angle et al.
patent: 2003/0021266 (2003-01-01), Oki et al.
patent: 2005/0053096 (2005-03-01), Yasukawa et al.
patent: 2005/0083939 (2005-04-01), Yasukawa et al.
N. W. McKeown, “Scheduling Algorithms for Input-Queued Cell Switches”, PhD Thesis, University of California at Berkeley, (1995).
C. Y. Lee and A. Y. Oruc, “A Fast Parallel Algorithm for Routing Unicast Assignment in Benes Networks”,IEEE Trans. on Parallel and Distributed Sys.,vol. 6, No. 3, pp. 329-333 (Mar. 1995).
T. T. Lee and S-Y Liew, “Parallel Routing Algorithms in Benes-Clos Networks”,Proc. IEEE INFOCOM '96,pp. 279-286 (1996).
N. McKeown, M. Izzard, A. Mekkittikul, W. Ellersick and M. Horowitz, “Tiny-Tera: A Packet Switch Core”,IEEE Micro.,pp. 26-33 (Jan.-Feb. 1997).
T. Chaney, J. A. Fingerhut, M. Flucke, J. S. Turner, “Design of a Gigabit ATM Switch”,Proc. IEEE INFOCOM '97,pp. 2-11 (Apr. 1997).
F. M. Chiussi, J. G. Kneuer, and V. P. Kumar, “Low-Cost Scalable Switching Solutions for Broadband Networking: The ATLANTA Architecture and Chipset”,IEEE Commun. Mag.,pp. 44-53 (Dec. 1997).
J. Turner and N. Yamanaka, “Architectural Choices in Large Scale ATM Switches”,IEICE Trans. Commun.,vol. E81-B, No. 2, pp. 120-137 (Feb. 1998).
H. J. Chao and J-S Park, “Centralized Contention Resolution Schemes for a Large-Capacity Optical ATM Switch”,Proc. IEEE ATM Workshop '97,(Fairfax, VA, May 1998).
N. McKeown, “The iSLIP Scheduling Algorithm for Input-Queued Switches”,IEEE/ACM Transactions on Networking,vol. 7, No. 2, (Apr. 1999).
N. McKeown, A. Mekkittikul, V. Anantharam, and J. Walrand, “Achieving 100% Throughput in an Input-Queued Switch”,IEEE Trans. on Communications,vol. 47, No. 8, pp. 1260-1267 (Aug. 1999).
E. Oki, N. Yamanaka, Y. Ohtomo, K. Okazaki and R. Kawano, “A 10-Gb/s (1.25 Gb/s×8) 4×2 0.25-μm CMOS/SIMOX ATM Switch Based on Scalable Distributed Arbitration”,IEEE J. of Solid-State Circuits,vol. 34, No. 12, pp. 1921-1934 (Dec. 1999).
J. Chao, “Saturn: A Terabit Packet Switch Using Dual Round-Robin”,IEEE Communications Magazine,pp. 78-84, (Dec. 2000).
E. Oki, Z. Jing, R. Rojas-Cessa, J. Chao, “Concurrent Round-Robin Dispatching Scheme in a Clos-Network Switch”,IEEE ICC 2001,pp. 106-112, (Jun. 2001).

Affiliated with

Also associated with

Rating

Scheduling the dispatch of cells in multistage switches... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Scheduling the dispatch of cells in multistage switches..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Scheduling the dispatch of cells in multistage switches... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3544186