Electrical computers and digital processing systems: multicomput – Computer network managing – Network resource allocating
Reexamination Certificate
1999-09-22
2003-11-11
Harrell, Robert B. (Department: 2142)
Electrical computers and digital processing systems: multicomput
Computer network managing
Network resource allocating
C709S223000, C709S232000, C370S230000, C370S232000, C370S238000, C370S468000
Reexamination Certificate
active
06647419
ABSTRACT:
The present invention relates to the field of system networks, and, more particularly, to a method and apparatus for allocating bandwidth to systems transmitting data over a communication link in a network.
BACKGROUND OF THE INVENTION
In a network, such as the Internet or an Intranet, in which many systems are coupled to each other by communication links, some links may be overused, that is, the demand for bandwidth over a particular link exceeds the bandwidth that is actually available. Often, this demand results from several data flows, possibly originating from multiple sources competing for the available bandwidth. Accordingly, it is desirable to enforce a specific policy for allocating the available bandwidth among the competing sources.
Many prior art mechanisms were developed to facilitate bandwidth allocation. In one method, the routers or switches in the network are given a bandwidth reservation by data transmitting servers, and then enforce the bandwidth allocation policy. This approach requires the implementation of a reservation and/or flow-setup protocol, which may be costly. Examples of this method include “fair queuing”, “weighted fair queuing”, “virtual clock”, etc. These mechanisms are generally aimed at simple fairness among flows and will be discussed in more detail below.
In another method, the scheduler that provides CPU time to server threads is pre-programmed to give certain threads higher priority. This approach is not practical for the short data responses typically transmitted in the Internet environment. A typical data response over the Internet is between 8 Kbytes and 16 Kbytes, whereas operating systems can generally buffer 32 Kbytes or more data waiting for transmission. When a thread gets CPU time from the scheduler, it will try to push all of its data into the operating system buffer. After the data is stored in the buffer, the priorities allocated by the scheduler have no influence on the rate at which the network protocol stack transmits data out of a buffer. This approach might have some applicability for long data responses, but is ineffective in actually allocating bandwidth according to scheduling priorities. An example of this approach is described in “Providing Differentiated Quality-of-Service in Web Hosting Services,” by Jussara Almeida, Mihaela Dabu, Anand Manikutty and Pei Cao. Technical Report, Computer Sciences Dept, Univ. of Wisconsin-Madison, March 1998; and reprinted in the 1998 SIGMETRICS Workshop on Internet Server Performance.
In yet another method, the server application software uses a rate-limiting mechanism to control the amount of data it hands to the network protocol stack to be transmitted to the network. This approach was developed to prevent theft of information. This approach may be unreliable because in a large-scale system accurate control is very difficult. An example of this approach is described in “X Through the Firewall, and Other Application Relays,” by G. Winfield Treese and Alec Wolman, USENIX Summer 1993 Conference Proceedings, June 1993, pages 87-99.
All of the above described approaches are inadequate when a server wants to give higher priority to specific requests. For example, a Web proxy operator may wish to give higher priority to users of the internal network, to retrievals requested by specific users, or to retrievals from specific sites.
SUMMARY OF THE INVENTION
A server computer handles multiple data flows between itself and other devices. The server has one or more applications that allocate bandwidth to respective flows and a network protocol stack that implements those allocations. When bandwidth allocations are made in accordance with a bandwidth allocation policy, the protocol stack in the server enforces the policy. The network protocol stack provides a programming interface that allows the application to specify the bandwidth allocation for a flow. The network protocol stack then enforces this allocation unless there is no shortage of available bandwidth.
The present invention provides many advantages over the prior art method of using routers or switches to implement bandwidth allocation. In the prior art method, a router must determine a flow's identity to implement appropriate bandwidth allocation. However, the current protocol, IPv4, does not include a flow label in each data packet; as a result, the router must infer flow identity from other packet header fields which can be a very complicated and time consuming process. On the other hand, the network protocol stack can simply tag internal packet buffers with the appropriate flow identities while implementing bandwidth allocations.
The present invention also dramatically reduces packet loss resulting from queue overflow. When bandwidth allocation is implemented by a router, frequently the router's queues fill up, causing packet loss. Packet loss creates severe inefficiencies and delays. Using the network protocol stack to implement bandwidth allocation allows the data packets to be deferred internally (for example, by blocking an application thread) without any packet loss.
Implementing the present invention involves minimal change to existing systems, in part because it does not involve any change to network routers between sending and receiving systems, and in part because packet-scheduling decisions are made in the network protocol stack. The sending application needs little or no modification. If the sending application is modified, it simply needs to specify the target bandwidth (or a corresponding data transmission priority level) to the network protocol stack. The sending application does not need complex mechanisms to schedule data transmissions. The present invention is also “work-conserving”; namely, when the link is idle, data is sent regardless of its priority.
REFERENCES:
patent: 5479404 (1995-12-01), Francois et al.
patent: 5485460 (1996-01-01), Schrier et al.
patent: 5640389 (1997-06-01), Masaki et al.
patent: 5764645 (1998-06-01), Bernet et al.
patent: 5805203 (1998-09-01), Horton
patent: 5907555 (1999-05-01), Raith
patent: 5996013 (1999-11-01), Delp et al.
patent: 6021263 (2000-02-01), Kujoory et al.
patent: 6046980 (2000-04-01), Packer
patent: 6075791 (2000-06-01), Chiussi et al.
patent: 6122287 (2000-09-01), Ohanian et al.
patent: 6154776 (2000-11-01), Martin
patent: 6167445 (2000-12-01), Gai et al.
patent: 6170022 (2001-01-01), Linville et al.
patent: 6173325 (2001-01-01), Kukreja
patent: 6175575 (2001-01-01), Ahuja et al.
patent: 6208640 (2001-03-01), Spell et al.
patent: 6247061 (2001-06-01), Douceur et al.
patent: 6286052 (2001-09-01), McCloghrie et al.
patent: 6292834 (2001-09-01), Ravi et al.
patent: 6321260 (2001-11-01), Takeuchi et al.
patent: 6359901 (2002-03-01), Todd et al.
patent: 6381228 (2002-04-01), Prieto et al.
patent: 6389010 (2002-05-01), Kubler et al.
patent: 6404738 (2002-06-01), Reininger et al.
patent: 6438141 (2002-08-01), Hanko et al.
patent: 6477670 (2002-11-01), Ahmadvand
patent: 6487170 (2002-11-01), Chen et al.
Almeida, Jussara et al. “Providing Differentiated Levels of Service in Web Content Hosting,” Technical Report, Computer Sciences Department, University of Wisconsin-Madison, Mar. 1998.*
Treese., G. Winfield and Wolman, Alec. “X Through the Firewall,and Other Application Relays,” Cambridge Research Lab Technical Report 93/10, Digital Equipment Corporation, May 3, 1993. Jan. 25, 1994.*
Floyd, Sally and Jacobson, Van. “The Synchronization of Periodic Routing Messages,” IEEE/ACM Transactions on Networking, vol. 2, No. 2, Apr. 1994, pp. 122-136.*
Skowler et al. “The PPP Multilink Protocol (MP)” Network Working Group, RFC 1990, Aug. 1996.*
C. Richards and K. Smith, “The PPP Bandwidth Allocation Protocol (BAP)” and “The PPP Bandwidth Allocation Control Protocol (BACP)”, Network Working Group, RFC 2125, Mar. 1997.*
Hariri, Salim et al. “A Hierarchical Analysis Approach for High Performance Computing and Communication Applications,” Proceedings of the 32nd Hawaii International Conference on System Sciences, 1999.*
Metz, Chris. “IP QoS: Traveling in First Class on the Internet
Harrell Robert B.
Hewlett--Packard Development Company, L.P.
P M H
LandOfFree
System and method for allocating server output bandwidth does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with System and method for allocating server output bandwidth, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and System and method for allocating server output bandwidth will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3146087