Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
2004-12-31
2010-10-19
Wilson, Robert W (Department: 2475)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S392000
Reexamination Certificate
active
07817640
ABSTRACT:
A scheduler for use in a computer network system which provides an order 1 level of complexity, while maintaining proportional fairness and a constant normalized worst-case fair index to create short term and long-term fairness among backlogged flows. The scheduler utilizes an intra-class scheduling algorithm to obtain the benefits of a round robin scheduler and an inter-class scheduling algorithm to obtain the benefits of timestamp based scheduler.
REFERENCES:
patent: 5029183 (1991-07-01), Tymes
patent: 6118784 (2000-09-01), Tsuchiya et al.
patent: 6216164 (2001-04-01), Zaremba
patent: 6469982 (2002-10-01), Henrion et al.
patent: 7277446 (2007-10-01), Abi-Nassif et al.
patent: 2004/0114602 (2004-06-01), Ko et al.
patent: 2004/0264472 (2004-12-01), Oliver et al.
Bennett, et al.; “Hierarchical Packet Fair Queueing Algorithms;”ACM SIGCOMM;1996; pp. 1-14.
Bennett, et al.; “WF2Q: Worst Case Fair Weighted Fair Queuing”;IEEE INFOCOM; 1996; pp. 120-128.
Cheung, et al.; “BSFQ: Bin Sort Fair Queuing”;IEEE INFOCOM; 2002; pp. 1640-1649.
Demers, et al.; “Analysis and Simulation of a Fair Queuing Algorithm”;ACM SIGCOMM; 1989; pp. 1-12.
S. Jamaloddin Golestani; “A Self-clocked Fair Queueing Scheme for Broad-band Applications”;IEEE INFOCOM; 1994; pp. 636-646.
Guo Chuanxiong; “SRR, an O(1) Time Complexity Packet Scheduler for Flows in Multi-Service Packet Networks”;ACM SIGCOMM; 2001; pp. 211-222.
Lenzini, et al.; “Aliquem: a Novel DRR Implementation to Achieve Better Latency and Fairness at O(1) Complexity”;IWQoS; 2002; pp. 77-86.
Massoulié, et al.; “Bandwidth Sharing: Objectives and Algorithms”;IEEE/ACM Trans on Networking; vol. 10; No. 3; 2002; pp. 320-328.
“The Network Simulator—ns-2”; website: http://www.isi.edu
snam
s, Aug. 23, 2006 pp. 1-2.
Parekh, et al.; “A Generalized Processor Sharing Approach to Flow Control in Integrated Services Networks: the Single Node Case”;IEEE/ACM Trans on Networking; vol. 1; No. 3; 1993; pp. 344-357.
Ramabhadran, et al.; “Stratified Round Robin: A Low Complexity Packet Scheduler with Bandwidth Fairness and Bounded Delay”;ACM SIGCOMM; 2003; pp. 239-249.
Rexford, et al.; “Hardware-Efficient Fair Queueing Architectures for High-Speed Networks”;IEEE INFOCOM; 1996; pp. 1-11.
Rexford, et al.; “A Scalable Architecture for Fair Leaky-Bucket Shaping”;INFOCOM; 1997; pp. 1056-1064.
Shreedhar, et al.; “Efficient Fair Queuing using Deficit Round Robin”;IEEE/ACM Transactions on Networking; vol. 4, No. 3, Jun. 1996; pp. 375-385.
Stiliadis, et al.; “Design and Analysis of Frame-based Fair Queueing: A New Traffic Scheduling Algorithm for Packet-Switched Networks”;ACM SIGMETRICS; 1996; pp. 1-12.
Suri, et al.; “Leap Forward Virtual Clock: AnO(loglog N) Queuing Scheme with Guaranteed Delays and Throughput Fairness”;IEEE INFOCOM; 1997; pp. 1-21.
Xu, et al.; “On Fundamental Tradeoffs between Delay Bounds and Computational Complexity in Packet Scheduling Algorithms”;ACM SIGCOMM; 2002; pp. 279-292.
Yuan et al.; “FRR: a Proportional and Worst-Case Fair Round Robin Scheduler”;Technical Report, Department of Computer Science, Florida State University; 2004;pp. 1-13; http://www.cs.fsu.edu/˜xyuan/frrtr.pdf.
Lixia Zhang; “Virtual Clock: A New Traffic Control Scheme for Packet Switching Networks”;ACM SIGCOMM; 1990; pp. 19-29.
Duan Zhenhai
Yuan Xin
Ballard Spahr LLP
Florida State University
Wilson Robert W
LandOfFree
Fair round robin scheduler for network systems does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fair round robin scheduler for network systems, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fair round robin scheduler for network systems will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4220813