Pipeline scheduler including a hierarchy of schedulers and...

Details Pipeline scheduler including a hierarchy of schedulers and... Pipeline scheduler including a hierarchy of schedulers and...

2011-01-25

2011-01-25

Moe, Aung S (Department: 2474)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S408000, C370S412000

Reexamination Certificate

active

07876763

ABSTRACT:
Disclosed is a hierarchy of individual schedulers with multiple scheduling lanes for scheduling items, such as, but not limited to packets or indications thereof, such that different classes of priority items can be propagated through the hierarchy of schedulers accordingly. A pipeline scheduler typically includes a root scheduler and one or more layers of schedulers with each of these layers including at least one scheduler. Each scheduler is configured to maintain items of different scheduling categories received from each of the particular scheduler's immediate children schedulers within the pipeline scheduler if any and from each immediate external source coupled to the particular scheduler if any, and to schedule the sending of the items of the different scheduling categories currently maintained to its parent schedule or external scheduler client. The items may correspond to packets, indications of packets, or any other entity.

REFERENCES:
patent: 5751708 (1998-05-01), Eng et al.
patent: 5850399 (1998-12-01), Ganmukhi et al.
patent: 5864540 (1999-01-01), Bonomi et al.
patent: 5864557 (1999-01-01), Lyons
patent: 5892766 (1999-04-01), Wicki et al.
patent: 6130878 (2000-10-01), Charny
patent: 6337851 (2002-01-01), Charny et al.
patent: 6389019 (2002-05-01), Fan et al.
patent: 6408005 (2002-06-01), Fan et al.
patent: 6412000 (2002-06-01), Riddle et al.
patent: 6430154 (2002-08-01), Hunt et al.
patent: 6438134 (2002-08-01), Chow et al.
patent: 6449650 (2002-09-01), Westfall et al.
patent: 6483839 (2002-11-01), Gemar et al.
patent: 6560230 (2003-05-01), Li et al.
patent: 6643293 (2003-11-01), Carr et al.
patent: 6691312 (2004-02-01), Sen et al.
patent: 6834053 (2004-12-01), Stacey et al.
patent: 6836475 (2004-12-01), Chaskar et al.
patent: 6876952 (2005-04-01), Kappler et al.
patent: 6909691 (2005-06-01), Goyal et al.
patent: 7277448 (2007-10-01), Long et al.
patent: 7336662 (2008-02-01), Hassan-Ali et al.
patent: 7417999 (2008-08-01), Charny et al.
patent: 7522609 (2009-04-01), Cohen et al.
patent: 2001/0001608 (2001-05-01), Parruck et al.
patent: 2003/0123449 (2003-07-01), Kuhl et al.
patent: 2004/0081165 (2004-04-01), Carr et al.
patent: 2004/0177087 (2004-09-01), Wu et al.
patent: 2004/0230675 (2004-11-01), Freimuth et al.
patent: 2005/0047415 (2005-03-01), Channegowda et al.
patent: 2005/0047425 (2005-03-01), Liu et al.
patent: 2005/0152374 (2005-07-01), Cohen et al.
patent: 2005/0163140 (2005-07-01), Dally et al.
patent: 2005/0243853 (2005-11-01), Bitar et al.
patent: 2005/0249220 (2005-11-01), Olsen et al.
patent: 2009/0207846 (2009-08-01), Cohen et al.
patent: 0 981 228 (2000-02-01), None
A. Ioannou & M. Katevenis, Pipelined Heap (Priority Queue) Management for Advanced Scheduling In high-Speed Networks,2001, IEEE, 0-7803-7097,2043-2047.
Varma et al, A general Methodology for Designing Efficient Traffic Scheduling and Shaping Algorithms, 1997, IEEE.
Bennett et al., “Hierarchical Packet Fair Queueing Algorithms,” IEEE/ACM Transactions on Networking (TON), vol. 5, Issue 5, Oct. 1997, pp. 675-689.
Hou et al., “Service Disciplines for Guaranteed Performance Service,” Proceedings-Fourth International Workshop on Real-Time Computing Systems and Applications, Oct. 27-29, 1997, pp. 244-250, Taipei.
Hagai et al., “Multiple Priority, Per Flow, Dual GCRA Rate Controller for ATM Switches,” Electrical and Electronic Engineers in Israel, 2000. The 21st IEEE Convention, Apr. 11-12, 2000, pp. 479-482, Tel-Aviv, Israel.
Kim et al., “Three-level Traffic Shaper and its Application to Source Clock Frequency Recovery for VBR Services in ATM Networks,” IEEE/ACM Transaction on Networking (TON), vol. 3, Issue 4, Aug. 1995, pp. 450-458.
Dixit et al., “Traffic Descriptor Mapping and Traffic Control for Frame Relay Over ATM Network,” IEEE/ACM Transactions on Networking (TON), vol. 6, Issue 1, Feb. 1998, pp. 56-70.
Bennett et al., “WF2Q: Worst-case Fair Weighted Fair Queueing,” INFOCOM '96. Fifteenth Annual Joint Conference of the IEEE Computer Societies Networking the Next Generation. Proceedings IEEE. Mar. 24-28, 1996, vol. 1, pp. 120-128.
Bennett et al., “High-Speed, Scalable, and Accurate Implementation of Fair Queueing Algorithms in ATM Networks,” ICNP '97, http://www-2.cs.cmu.edu/—hzhang/papers/ICNP97.pdf, 1997.
U.S. Appl. No. 10/758,547, filed Jan. 14, 2004, Charny et al.
U.S. Appl. No. 10/422,167, filed Apr. 24, 2003, Kappler et al.
U.S. Appl. No. 11/022,246, filed Dec. 23, 2004, Cohen et al.
U.S. Appl. No. 11/070,932, filed Mar. 3, 2005, Kappler et al.
U.S. Appl. No. 11/022,220, filed Dec. 23, 2004, Shoham et al.
U.S. Appl. No. 12/426,245, filed Apr. 18, 2009, Cohen et al.

Affiliated with

Also associated with

Rating

Pipeline scheduler including a hierarchy of schedulers and... does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Pipeline scheduler including a hierarchy of schedulers and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Pipeline scheduler including a hierarchy of schedulers and... will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2728737