Electrical computers and digital processing systems: multicomput – Computer network managing – Network resource allocating
Reexamination Certificate
1997-06-13
2001-02-20
Geckil, Mehmet B. (Department: 2152)
Electrical computers and digital processing systems: multicomput
Computer network managing
Network resource allocating
C709S223000, C709S224000, C709S233000, C709S234000, C709S225000, C709S238000, C709S229000, C370S229000, C370S232000, C370S233000, C370S234000, C370S235000
Reexamination Certificate
active
06192406
ABSTRACT:
FIELD OF THE INVENTION
The invention relates to network management, and more particularly to management of sources which are entering computer and other communication networks.
BACKGROUND OF THE INVENTION
Traffic over current computer and other networks is voluminous, containing many different types and rates of data, and only promises to increase in the future. Future integrated-service networks will support an even wider range of applications with diverse traffic characteristics performance requirements, including by the support of multiple classes of service.
The Available Bit rate (ABR) service defined by the ATM Forum supports data applications and emerging rate-adaptive multimedia applications in Asynchronous Transfer Mode (ATM) networks. Its operation relies on an effective congestion control mechanism. Rate based congestion control has been considered desirable to achieve high performance over high speed networks that are characterized by large bandwidth-delay products. The potential of this scheme to achieve low loss is by maintaining a smooth flow of data with the source rates being adjusted through a feedback mechanism. This allows intermediate systems (switches) to have relatively small buffers while still maintaining high utilizations.
In contrast, although known window flow control has undergone several refinements to also maintain a smooth even flow of data, there are several conditions during which window flow control results in bursty arrivals into the network. The smooth flow of data packets in response to the arrival of acknowledgements is disturbed in cases where there is ack-compression, new flows starting up, or when multiple flows recover from packet loss, and go into slow-start.
Allowing the applications to “fast-start”, that is, to transmit as fast as reasonable upon startup and entry into the network, is desirable for many data applications.
Known rate based congestion control seeks to allocate the source rates so as to achieve high resource utilization, while maintaining feasibility—that is, the capacity of any resource in the network—primarily link bandwidth—is not exceeded at any time. Even a small excess in the source rate, can cause a queue buildup. The ABR service can ensure a particular known notion of fairness—max-min fairness which requires a distributed computation. An incremental computation that scales with the number of connections is described in Kalampoukas, Varma and Ramakrishnan, “An Efficient Rate Allocation Algorithm for ATM Networks Providing Max-Min Fairness”, Proceedings of 6
th
IFIP International Conference on High Performance Networking, HPN 95, Palma De Mallorca, Spain, Sep. 11-15, 1995, incorporated by reference.
The incremental computation of source rates can potentially result in the rates being infeasible for short intervals (often one round-trip time). Varying feedback delays that result in asynchronous updates to source rates make the control of this period of infeasibility difficult to predict. Several other practical situations also make it difficult to ensure feasibility, which include changes in the capacity due to the presence of higher priority traffic, changes in the number of users as they arrive or depart, and the desire of sources to opportunistically utilize available bandwidth.
The desire to make optimum use of bandwidth extends to the desire of data applications to ramp up as fast as possible on startup and entry into the network. All of these causes transient situations that can result in queue buildups, which are sometimes substantial.
One known way to ensure feasibility is to force a source increasing its rate to delay any increase until all other sources have received and implemented their decreases. Thus, the aggregate rate at a given link will never exceed its capacity. This method introduces considerable delay to sources when they start up or when they are asked to increase their rate, thus impacting applications (and user-perceived performance) adversely. It may also lead to underutilization of resources. In addition, when the bandwidth in the network changes, there is a certain time taken to provide feedback to the sources so that they may change their source-rates accordingly. The build-up of the queues during this transient period cannot be avoided even by schemes that are extremely conservative in ensuring feasibility.
Unlike the scheme for instance proposed in Charny, Ramakrishnan and Lauck, “Time Scale Analysis and Scalability Issues for Explicit Rate Allocation in ATM Networks”, IEEE/ACM Transactions on Networking, August 1996, incorporated by reference, in the ATM Forum's ABR service attempts to maintain feasibility and avoid a large queue buildup by picking conservative values for the “increase parameter”, RIF and the initial cell rate ICR (see Sathaye, “ATM Forum Traffic Management Specification Version 4.0”, (Draft), AF-TM 95-0013R10, ATM Forum Traffic Management Working Group, February 1996, incorporated by reference). However, even a small ICR and RIF, can still result in substantial queue buildups.
Overall then, although attempts have been made to control and manage congestion over computer and other networks and particularly upon startup, none can be viewed to operate optimally or near optimally over a wide range of network conditions.
SUMMARY OF THE INVENTION
The invention improving upon these and other aspects of the network art relates to a system and method for startup management, including mechanisms to allow sources entering networks to maintain high resource efficiency and drive link underutilization and other undesirable effects to much reduced levels.
The invention in another aspect relates to a system and method for startup management which drives oscillatory artifacts to lower levels, increasing bandwidth use and efficiency.
The invention in another aspect relates to a system and method for startup management which permits sources to start up aggressively in the network, without disturbing the overall balance of utilizations and flows or affecting overall fairness across the network allocations.
REFERENCES:
patent: 5359593 (1994-10-01), Derby et al.
patent: 5379297 (1995-01-01), Glover et al.
patent: 5432824 (1995-07-01), Zheng et al.
patent: 5488609 (1996-01-01), Hluchyj et al.
patent: 5497375 (1996-03-01), Hluchyj et al.
patent: 5515359 (1996-05-01), Zheng
patent: 5528591 (1996-06-01), Lauer
patent: 5675576 (1997-10-01), Kalampoukas et al.
patent: 5691986 (1997-11-01), Pearlstein
patent: 5701291 (1997-12-01), Roberts
patent: 5737313 (1998-04-01), Kolarov et al.
patent: 5745477 (1998-04-01), Zheng et al.
patent: 5754530 (1998-05-01), Awdeh et al.
patent: 5761438 (1998-06-01), Sasaki
patent: 5777984 (1998-07-01), Gun et al.
patent: 5805577 (1998-09-01), Jain et al.
patent: 5805599 (1998-09-01), Mishra et al.
patent: 5812526 (1998-09-01), Chang et al.
patent: 5812527 (1998-09-01), Kline et al.
patent: 5812528 (1998-09-01), VanDervort
patent: 5864539 (1999-01-01), Yin
patent: 5881245 (1999-03-01), Thompson
patent: 5898669 (1999-04-01), Shimony et al.
patent: 5901138 (1999-09-01), Bader et al.
patent: 5926459 (1999-07-01), Lyles et al.
patent: 5940369 (1999-08-01), Bhagavath et al.
patent: 5940375 (1999-08-01), Soumiya et al.
patent: 5953336 (1999-09-01), Moore et al.
patent: 5987031 (1999-11-01), Miller et al.
patent: 5991268 (1999-11-01), Awdeh et al.
Lampros Kalampoukas et al., An Efficient Rate Allocation Algorithm for Packet-Switched Networks Providing Max-Min Fairness, Feb. 16, 1995.
Danny Tsang and Wales Wong, A New Rate BAsed Switch Algorithm for ABR Traffic to Achieve Max-Min Fairness with Analytical Approximation and Delay Adjustment, 1996.
Article: A Hop by Hop Rate-Based Congestion Control Scheme, Partho P. Mishra and Hemant Kanakia p. 112-123.
Article: An Efficient Rate Allocation Algorithm for Packet-Switched Networks Providing Max-Min Fairness, Lampros Kalampoukas, Anujan Varma and K.K. Ramakrishnan, p. 1-25, Feb. 16, 1995.
Article: Erica Switch Algorithm: A Complete Description, Raj Jain, Shiv Kalyanaraman, Rohit Goyal, Sonia Fahmy, and Ram Viswanathan,
Ma Qingming
Ramakrishnan Kadangode K.
AT&T Corp.
Geckil Mehmet B.
Oliff & Berridge PLC.
Vaughn, Jr. William C.
LandOfFree
Startup management system and method for networks does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Startup management system and method for networks, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Startup management system and method for networks will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2610372