Priority propagation in a multi-level scheduling hierarchy

Details Priority propagation in a multi-level scheduling hierarchy Priority propagation in a multi-level scheduling hierarchy

2004-01-14

2008-08-26

Ngo, Ricky Q. (Department: 2616)

Multiplex communications

Pathfinding or routing

Switching a message which includes an address header

C370S395420, C370S395430

Reexamination Certificate

active

07417999

ABSTRACT:
Priority propagation is achieved in the context of a rate-based scheduling hierarchy. Priority traffic is not delayed by non-priority traffic by more than the duration required for transmission of the maximum packet length at the physical interface speed. Multiple sibling priority levels are supported. To achieve these objectives, the scheduling hierarchy tree is divided into sub-trees corresponding to non-priority traffic and the different levels of priority. At each scheduling decision, a packet is selected from the highest priority non-empty sub-tree. Scheduling decisions within each sub-tree exploit the usual rate-based scheduling method but without priority propagation. When a packet from a priority sub-tree is chosen, scheduling state in the non-priority sub-tree is updated.

REFERENCES:
patent: 5864540 (1999-01-01), Bonomi et al.
patent: 6130878 (2000-10-01), Charny
patent: 6408005 (2002-06-01), Fan et al.
patent: 6412000 (2002-06-01), Riddle et al.
patent: 6560230 (2003-05-01), Li et al.
patent: 6691312 (2004-02-01), Sen et al.
patent: 6836475 (2004-12-01), Chaskar et al.
patent: 7006513 (2006-02-01), Ali et al.
patent: 7283472 (2007-10-01), Widmer et al.
patent: 2003/0179703 (2003-09-01), Levy et al.
patent: 2005/0152374 (2005-07-01), Cohen et al.
patent: 2006/0029079 (2006-02-01), Cohen et al.
patent: 2006/0029080 (2006-02-01), Kappler et al.
patent: 2006/0153243 (2006-07-01), Shoham et al.
Bennett et al.; “Hierarical Packet Fair Queing Algortithms”, Oct. 1997; IEEE/ACM Transaction on Networking, vol. 5 No. 5 pp. 675-689.
Jon C.R. Bennett et al., “Hierarchical Packet Fair Queuing Algorithms”, IEEE ACM Transactions on Networking, 5(5), pp. 675-689, Oct. 1997.
T. Cormen et al., “Introduction to Algorithms”, The MIT Press, Chapter 9, 1990.
J.D. Foley et al., “Computer Graphics: Principles and Practice”, Addison-Wesley, 1990, pp. 74-80.
S.J. Golestani, “A Self-Clocked Fair Queuing Scheme for Broadband Applications”, Proc. INFOCOM'94, pp. 636-646, Apr. 1994.
P. Goyal et al., “Start-time fair queuing: a schedulings algorithm for integrated services packet switching networks”, Proc. Sigcomm, 1996.
Chris Kappler et al., “HQF Implementation Based on Sorting Trees (HIST)”, Cisco Systems, Doc. No. EDCS-273780—rev 3.9, pp. 1-123.
S. Keshav et al., “An Engineering Approach to Computer Networking”, Addison-Wesley, Chapter 9, 1997.
J-Y Leboudec et al., “A Short Tutorial On Network Calculus I: Fundamental Bounds in Communication Networks”, Proceedings ISCAS2000, Geneva, Switzerland, May 2000.
W. Leland et al., “On the Self-Similar Nature of Ethernet Traffic”, SIGCOMM'93, pp. 183-193, 1993.
A.K.J. Parekh, “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks”, Ph.D. thesis, Massachusetts Institute of Technology, Feb. 1992.
M. Roughan et al., “Measuring long-range dependence under changing traffic conditions”, in Proc. IEEE INFOCOM'99, New York, Mar. 1999, pp. 338-341.
Ion Stoica et al., “Earliest Eligible Virtual Deadline First: A Flexible and Accurate Mechanism for Proportional Share Resource Allocation”, Department of Computer Science, Old Dominion University, Norfolk, Virginia, TR-95-22, Jan. 26, 1996, pp. 1-37.
Ion Stoica et al., “An Efficient Packet Service Algorithm for High Speed ATM Switches”, Department of Computer Science, Old Dominion University, Norfolk, Virginia, pp. 1-24.
K. Thompson et al., “Wide-Area Internet Traffic Patterns and Characteristics”, IEEE/ACM Transactions on Networking, pp. 10-23, Nov. 1997.
T. Tuan et al., “Multiple Time Scale Congestion Control for Self-Similar Network Traffic”, Performance Evaluation, 36:359-386, 1999.
Bennett et al., “Hierarchical Packet Fair Queuing 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,”Fourth Int'l 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,” The 21st IEEE Conv., 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 vol. 3, Iss.4, Aug. 1995, pp. 450-458.
Dixit et al., “Traffic Descriptor Mapping and Traffic Control for Frame Relay Over ATM Netowrk,” IEEE/ACM TON, vol. 6, Issue 1, Feb. 1998, pp. 56-70.
Bennett et al., “WF2Q: Worst-case Fair Weighted Fair Queuing,” INFOCOM '96 Fifteenth Annual Joint Conference of the IEEE, Mar. 24-28, 1996, vol. 1, pp. 120-128.
Bennett et al., “High-Speed, Scalable, and Accurate Implementation of Fair Queuing Algorithms in ATM Networks,” ICNP '97,http://www-2.cs.cmu.edu/˜hzhang/papers/ICNP97.pdf, 1997.

Affiliated with

Also associated with

Rating

Priority propagation in a multi-level scheduling hierarchy does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Priority propagation in a multi-level scheduling hierarchy, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Priority propagation in a multi-level scheduling hierarchy will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-4008441