Multiplex communications – Data flow congestion prevention or control – Control of data admission to the network
Reexamination Certificate
2005-06-21
2005-06-21
Nguyen, Brian (Department: 2661)
Multiplex communications
Data flow congestion prevention or control
Control of data admission to the network
C370S235000, C370S412000, C370S428000, C709S226000, C709S229000
Reexamination Certificate
active
06909691
ABSTRACT:
Resource requests from a plurality of schedulable entities are scheduled while limiting the maximum and minimum quality of service allocated to each schedulable entity. The resource scheduler of the present invention requires less memory maintain state information than existing rate-controlling schedulers, and is thus more easily scalable to large numbers of users. The resource scheduler also schedules resources fairly among competing schedulable entities. A fair-share scheduling algorithm is used by a resource scheduler to select resource requests to service. A rate controller checks to ensure that servicing the selected request will not cause the associated user's maximum quality of service to be exceeded. If the maximum quality of service will not be exceeded, the virtual time used in the scheduling algorithm is incremented, and the request is serviced. If the maximum quality of service will be exceeded, the virtual time is still incremented, but the request is not serviced and remains pending.
REFERENCES:
patent: 3377624 (1968-04-01), Nelson et al.
patent: 4177510 (1979-12-01), Appell et al.
patent: 5189667 (1993-02-01), Esaki et al.
patent: 5212793 (1993-05-01), Donica et al.
patent: 5226160 (1993-07-01), Waldron et al.
patent: 5249290 (1993-09-01), Heizer
patent: 5263147 (1993-11-01), Francisco et al.
patent: 5325530 (1994-06-01), Mohrmann
patent: 5437032 (1995-07-01), Wolf et al.
patent: 5528753 (1996-06-01), Fortin
patent: 5572680 (1996-11-01), Ikeda et al.
patent: 5584023 (1996-12-01), Hsu
patent: 5603020 (1997-02-01), Hashimoto et al.
patent: 5623492 (1997-04-01), Teraslinna
patent: 5636371 (1997-06-01), Yu
patent: 5640595 (1997-06-01), Baugher et al.
patent: 5692047 (1997-11-01), McManis
patent: 5706097 (1998-01-01), Schelling et al.
patent: 5706453 (1998-01-01), Cheng et al.
patent: 5708774 (1998-01-01), Boden
patent: 5719854 (1998-02-01), Choudhury et al.
patent: 5727203 (1998-03-01), Hapner et al.
patent: 5748614 (1998-05-01), Wallmeier
patent: 5752003 (1998-05-01), Hart
patent: 5761477 (1998-06-01), Wahbe et al.
patent: 5764889 (1998-06-01), Ault et al.
patent: 5781550 (1998-07-01), Templin et al.
patent: 5799173 (1998-08-01), Gossler et al.
patent: 5809527 (1998-09-01), Cooper et al.
patent: 5828893 (1998-10-01), Weid et al.
patent: 5838686 (1998-11-01), Ozkan
patent: 5838916 (1998-11-01), Domenikos et al.
patent: 5842002 (1998-11-01), Schnurer et al.
patent: 5845129 (1998-12-01), Wendorf et al.
patent: 5850399 (1998-12-01), Ganmukhi et al.
patent: 5860004 (1999-01-01), Fowlow et al.
patent: 5864683 (1999-01-01), Boebert et al.
patent: 5889956 (1999-03-01), Hauser et al.
patent: 5889996 (1999-03-01), Adams
patent: 5892968 (1999-04-01), Iwasaki et al.
patent: 5905730 (1999-05-01), Yang et al.
patent: 5905859 (1999-05-01), Holloway et al.
patent: 5913024 (1999-06-01), Green et al.
patent: 5915085 (1999-06-01), Koved
patent: 5915095 (1999-06-01), Miskowiec
patent: 5918018 (1999-06-01), Gooderum et al.
patent: 5920699 (1999-07-01), Bare
patent: 5933603 (1999-08-01), Vahalia et al.
patent: 5937159 (1999-08-01), Meyers et al.
patent: 5956481 (1999-09-01), Walsh et al.
patent: 5978373 (1999-11-01), Hoff et al.
patent: 5982748 (1999-11-01), Yin et al.
patent: 5987524 (1999-11-01), Yoshida et al.
patent: 5991812 (1999-11-01), Srinivasan
patent: 5999963 (1999-12-01), Bruno et al.
patent: 6016318 (2000-01-01), Tomoike
patent: 6018527 (2000-01-01), Yin et al.
patent: 6023721 (2000-02-01), Cummings
patent: 6038608 (2000-03-01), Katsumata
patent: 6038609 (2000-03-01), Geulen
patent: 6047325 (2000-04-01), Jain et al.
patent: 6055617 (2000-04-01), Kingsbury
patent: 6061349 (2000-05-01), Coile et al.
patent: 6065118 (2000-05-01), Bull et al.
patent: 6075791 (2000-06-01), Chiussi et al.
patent: 6075938 (2000-06-01), Bugnion et al.
patent: 6078929 (2000-06-01), Rao
patent: 6078957 (2000-06-01), Adelman et al.
patent: 6086623 (2000-07-01), Broome et al.
patent: 6092178 (2000-07-01), Jindal et al.
patent: 6094674 (2000-07-01), Hattori et al.
patent: 6101543 (2000-08-01), Alden et al.
patent: 6108701 (2000-08-01), Davies et al.
patent: 6108759 (2000-08-01), Orcutt et al.
patent: 6122673 (2000-09-01), Basak et al.
patent: 6154776 (2000-11-01), Martin
patent: 6154778 (2000-11-01), Koistinen et al.
patent: 6161139 (2000-12-01), Win et al.
patent: 6167520 (2000-12-01), Touboul
patent: 6172981 (2001-01-01), Cox et al.
patent: 6189046 (2001-02-01), Moore et al.
patent: 6192389 (2001-02-01), Ault et al.
patent: 6192512 (2001-02-01), Chess
patent: 6230203 (2001-05-01), Koperda et al.
patent: 6240463 (2001-05-01), Benmohamed et al.
patent: 6247057 (2001-06-01), Barrera
patent: 6259699 (2001-07-01), Opalka et al.
patent: 6266678 (2001-07-01), McDevitt et al.
patent: 6269404 (2001-07-01), Hart et al.
patent: 6279039 (2001-08-01), Bhat et al.
patent: 6279040 (2001-08-01), Ma et al.
patent: 6282581 (2001-08-01), Moore et al.
patent: 6282703 (2001-08-01), Meth et al.
patent: 6286047 (2001-09-01), Ramanathan et al.
patent: 6298479 (2001-10-01), Chessin et al.
patent: 6314558 (2001-11-01), Angel et al.
patent: 6327622 (2001-12-01), Jindal et al.
patent: 6336138 (2002-01-01), Caswell et al.
patent: 6351775 (2002-02-01), Yu
patent: 6353616 (2002-03-01), Elwalid et al.
patent: 6363053 (2002-03-01), Schuster et al.
patent: 6370583 (2002-04-01), Fishler et al.
patent: 6381228 (2002-04-01), Prieto et al.
patent: 6385638 (2002-05-01), Baker-Harvey
patent: 6389448 (2002-05-01), Primak et al.
patent: 6393484 (2002-05-01), Massarani
patent: 6425003 (2002-07-01), Herzog et al.
patent: 6430622 (2002-08-01), Aiken, Jr. et al.
patent: 6434631 (2002-08-01), Bruno et al.
patent: 6434742 (2002-08-01), Koepele, Jr.
patent: 6438134 (2002-08-01), Chow et al.
patent: 6442164 (2002-08-01), Wu
patent: 6457008 (2002-09-01), Rhee et al.
patent: 6463459 (2002-10-01), Orr et al.
patent: 6470398 (2002-10-01), Zargham et al.
patent: 6487578 (2002-11-01), Ranganathan
patent: 6487663 (2002-11-01), Jaisimha et al.
patent: 6490670 (2002-12-01), Collins et al.
patent: 6499137 (2002-12-01), Hunt
patent: 6529950 (2003-03-01), Lumelsky et al.
patent: 6542167 (2003-04-01), Darlet et al.
patent: 6553413 (2003-04-01), Leighton et al.
patent: 6578055 (2003-06-01), Hutchison et al.
patent: 6578068 (2003-06-01), Bowman-Amuah
patent: 6580721 (2003-06-01), Beshai
patent: 6658571 (2003-12-01), O'Brien et al.
patent: 6691312 (2004-02-01), Sen et al.
patent: 2003/0061338 (2003-03-01), Stelliga
patent: WO 99/39261 (1999-08-01), None
“Start-time Fair Queuing: A Scheduling Algorithm for Integrated Services Packet Switching Networks” by Goyal et al.
http://cs.cornell.edu/Info/Courses/Spring-97/CS614/goy.html; ‘Notes on “A Heirarchical CPU Scheduler for Multimedia Operating Systems’” by Pawan Goyal, Xingang Guo and Harrick Vin—written by: Tibor Jánosi (retrieved on May 8, 2000).
‘Packet Scheduling Algorithms for Integrated Services Networks’ by Pawan Goyal, M.S., BTech.; Dissertation . . . presented . . . Doctor of Philosophy @ The University of Texas at Austin; Aug. 1997.
IEEE/ACM Transactions on Networking, vol. 5, No. 5, pp. 690-704 (Oct. 1997).
Plummer, D. C.,An Ethernet Address Resolution Protocol—or—Converting Network Protocol Addresses to 48.bit Ethernet Address for Transmission on Ethernet Hardware,Nov. 1982, [online], [retrieved on Jan. 17, 2000]. Retrieved from the Internet: <URL: http://www.msg.net/kadow/answers/extras/rfc/rfc826.txt>.
Huang, X. W. et al., “The ENTRAPID Protocol Development Environment,”Proceedings of IEEE Infocom'99,Mar. 1999, nine pages.
Duffield, N.G., et al., “A Flexible Model for Resource Management in Virtual Private Networks,”Computer Communication Review Conference, Computer Communication,ACM SIGCOMM '99 Conference, Cambridge, MA, Aug. 30, 1999-Sep. 3, 1999. pp 95-108.
Campbell, A. T. and Keshav, S., “Quality of Service in Distributed Systems,”Computer Communications 21,1998, pp 291-293.
Bach, M. J.,The Design of the Unix® Operating System,New Delhi, Prentice-Hall of India, 198
Goyal Pawan
Keshav Srinivasan
Ensim Corporation
Fenwick & West LLP
Moore Ian N
Nguyen Brian
LandOfFree
Fairly partitioning resources while limiting the maximum... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Fairly partitioning resources while limiting the maximum..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Fairly partitioning resources while limiting the maximum... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3466719