Pipelined packet scheduler for high speed optical switches

Details Pipelined packet scheduler for high speed optical switches Pipelined packet scheduler for high speed optical switches

2006-06-06

2006-06-06

Pham, Chi (Department: 2668)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S498000

Reexamination Certificate

active

07058063

ABSTRACT:
A pipelined scheduler which allows easy implementation and control and further fair scheduling among input lines of a crossbar high speed switch fabric is discussed. By means of a round-robin communication scheme, a systematically ordered sequence of visits to time slots can be obtained regardless of whether the number of scheduler modules is even or odd by framing the time axis and using a priority matrix to reserve future time slots. Further, a Carry Over Round-robin Pipelined Scheduler (CORPS) achieves scalability to a large number of ports. Moreover, CORPS achieves one scheduling decision per line per slot, by scheduling packets in future slots. It is well suited to the support of Quality of Service traffic, since the choice of the queues to be scheduled is arbitrary. CORPS limits itself to resolve, in a fair way, the contention for output ports.

REFERENCES:
patent: 5241536 (1993-08-01), Grimble et al.
patent: 5255265 (1993-10-01), Eng et al.
patent: 5299190 (1994-03-01), LaMaire et al.
patent: 5301055 (1994-04-01), Bagchi et al.
patent: 5577035 (1996-11-01), Hayter et al.
patent: 5982776 (1999-11-01), Manning et al.
patent: 6359861 (2002-03-01), Sui et al.
patent: 6477169 (2002-11-01), Angle et al.
patent: 6618379 (2003-09-01), Ramamurthy et al.
patent: 2-87745 (1990-03-01), None
patent: 2-237337 (1990-09-01), None
patent: 4-58644 (1992-02-01), None
patent: 4-271546 (1992-09-01), None
patent: 8-223213 (1996-08-01), None
patent: 2000-78148 (2000-03-01), None
patent: 2000-183884 (2000-06-01), None
Chipalkatti et al., “Protocols for Optical Star-Coupler Network Using WDM,”IEEE Journal on Selected Areas in Communications, vol. 11, No. 4, May 1993.
T. Anderson, S. Owicki, J. Saxe, C. Thacker, “High Speed Switch Scheduling for Local Area Networks,”ACM Transactions on Computer Systems, pp. 319-352, Nov. 1993.
Cormen, Leiserson and Rivest, “Introduction to Algorithms”, McGraw-Hill, 1990.
L. Georgiadis, R. Guerin, V. Peris, “Efficient Network QoS Provisioning Based on per Node Traffic Shaping,”Proceedings of INFOCOM96, vol. 1, pp. 102-110, 19996.
J.E. Hopcroft, R.M. Karp, “An n5/2Algorithm for Maximum Matching in Bipartite Graphs”,Society for Industrial and Applied Mathematics J. Comput., 2 (1973), pp. 225-231.
M.J. Karol, M.G. Hluchyj, S.P. Morgan, “Input Versus Output Queueing on a Space Division Packet Switch”,IEEE Transactions on Communications, vol. COM-35, No. 12, pp. 1347-156, Dec. 1987.
A. Mekkittikul, N. McKeown, “A Practical Scheduling Algorithm to Achieve 100% ΛThrough-put in Input-Queued Switches”,Proceedings of Infocom98, Apr. 1998.
N. Mckeown, M. Izzard, A. Mekkittikul, W. Ellersick, M. Horowitz, “The Tiny Tera: A Packet Switch Core”,IEEE Micro, Jan./Feb. 1997, pp. 26-32.
N. McKeown, V. Anantharam, J. Walrand, “Achieving 100% ΛThroughput in an Input-Queued Switch”,Proceedings of Infocom96, San Francisco, Mar. 1996.
N. McKeown, “Scheduling Cells in an Input-Queued Switch”,PhD Thesis, University of California, at Berkeley, 1995.
A. Smiljanic, R. Fan, G. Ramamurth, “RRGS-Round-Robin Greedy Scheduling for Electronic/Optical Terabit Switches”,NEC C&C Research Labratories, Technical Report TR 98-C063-4-5083-2, 1998.
Y. Tamir and H-C Chi, “Symmetric Crossbar Arbiters for VLSI Communication Switches”,IEEE Transactions on Parallel and Distributed Systems, vol. 4, No. 1, pp. 13-27, 1993.
Y. Tamir and G. Frazier, “High Performance Multi-queue Buffers for VLSI Communication Switches”,Proceedings of 15thAnn. Symp. on Comp. Arch., pp. 343-354, Jun. 1988.
R.E. Tarjan, “Data Structures and Network Algorithms”,Society for Industrial and Applied Mathematics, Pennsylvania, Nov. 1983.
J. Turner, “New Directions in Communications, or Which Way to the Information Age?”,IEEE Communication Magazine, vol. 24, pp. 8-15, 1986.
H. Zhang, “Service Disciplines for Guaranteed Performance Service in Packet-Switching Networks”,In Proceedings of IEEE, vol. 83, No. 10, pp. 1374-1396, Oct. 1995.
Pao, D. C. W.: “Scheduling Input-Buffered Multicast ATM Switch”; ATM Workshop Proceedings, 1998 IEEE, Fairfax, VA, USA; May 26-29, 1998; New York, NY, USA, IEEE, US, May 26, 1998; pp. 51-55.
Akata, M., et al.: “An Input Buffering ATM Switch Using a Time-Slot Scheduling Engine”; NEC Research and Development, Nippon Electric Ltd., Tokyo, JP; vol. 33, No. 1, Jan. 1992; pp. 64-71.
Mekkittikul, A., et al.: “A Practical Scheduling Algorithm to Achieve 100% Throughput in Input-Queued Switches”; Infocom '98; Seventeenth Annual Joint Conference of the IEEE Computer and Communications Societies Proceedings, IEEE San Francisco, CA, USA, Mar. 29-Apr. 2, 1998; New York, NY, USA, IEEE, US; vol. 2, Mar. 29, 1998; pp. 792-799.
Smiljanic, A., et al.: “RRGS-Round-Robin Greedy Scheduling for Electronic/Optical Terabit Switches”; 1999 IEEE Global Telecommunications Conference—Globecom '99; Seamless Interconnection for Universal Services, Rio De Janeiro, Brazil, Dec. 5-9, 1999; IEEE Global Telecommunications Conference, New York, NY : IEEE, US; vol. 2, Dec. 5, 1999; pp. 1244-1250.

Affiliated with

Also associated with

Rating

Pipelined packet scheduler for high speed optical 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 Pipelined packet scheduler for high speed optical switches, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pipelined packet scheduler for high speed optical switches will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3650994