Electrical computers and digital processing systems: multicomput – Computer network managing – Network resource allocating
Reexamination Certificate
1999-03-11
2001-11-06
Burgess, Glenton B. (Department: 2153)
Electrical computers and digital processing systems: multicomput
Computer network managing
Network resource allocating
C709S217000
Reexamination Certificate
active
06314465
ABSTRACT:
TECHNICAL FIELD
This invention relates to wide area networks such as the Internet, and more particularly, to a method and apparatus for minimizing the average delay per unit of time of all client requests incurred over all connections established for accessing server devices, such as web servers and proxy cache servers, which are located across the wide area network.
BACKGROUND OF THE INVENTION
In co-pending patent application Ser. No. 08/953577 entitled “Data Distribution Techniques for Load-Balanced Fault-Tolerant Web Access”, by B. Narendran, S. Rangarajan (co-inventor herein) and S. Yajnik, assigned to the assignee of the present application, and which is incorporated herein by reference, a methodology is described for balancing the load on a set of devices connected on a wide area network such as the Internet. Specifically, the methodology for load balancing described in that application provides, in a first phase, an algorithm for distributing web documents, or objects, onto different servers such that the total access rates to each server (equal to the total number of connection requests that a server handles per time unit) are balanced across all the servers. Further, in a second phase of the methodology, a network flow-based algorithm is used to re-balance the access rates to each server in response to system changes without moving objects between the different servers.
In further detail, in the first phase of the load balancing methodology, logical items, such as the web documents, or objects, are mapped to different physical devices such as web servers, cache servers, ftp servers, etc., based on the a priori access rates that are known for requests from/to these web documents. This mapping, referred to the initial distribution, takes as an input the access rates of each web document, the number of replicas of these web documents that need to be made on the physical devices, such as document servers or caches, and the capacity of each of the physical devices, and produces a mapping between the web documents and the physical devices. It also produces as an output the probabilities (or weights) that will then be used by a redirection server to redirect requests from/to replicated web documents to one of the physical devices to which they are mapped. This initial distribution mapping is performed such that the load is balanced among the physical devices, or, i.e., the sum of access rates of requests to the web documents redirected to each physical device is balanced across all the devices. Load balance is achieved across the physical devices irrespective of the web documents that they handle.
In the second phase of the methodology, once the initial distribution of the web documents is performed, any change in the system parameters that affects the load balance is handled using a network flow load balance algorithm to determine new probabilities (or weights) with which the redirection server will then thereafter redirect requests from/to web documents to one of the physical devices to which they are mapped. Thus, instead of re-mapping web documents to different documents servers or caches to handle a perturbation in load, the load is re-balanced by changing the probability with which requests to each replicated web document is redirected to one of the plurality of physical devices to which that physical item is mapped. Examples of parameters that may change in the system include the load on each physical device and the capacity of each of the physical devices, the latter of which can instantly become zero upon the failure of a device.
The goal of load balancing, as described, is to balance across all physical devices the sum of the access rates of requests to the web documents redirected to each physical device. The latency, or delay, incurred in providing a response from a physical device to a request for a web document made by a client has not been previously considered.
SUMMARY OF THE INVENTION
In accordance with the present invention, minimization of request latency on a wide area network such as the Internet is the goal rather than pure load balancing. The load sharing methodology of the present invention minimizes delay by determining the probabilities, or weights with which web requests are redirected over the wide area network to the web servers so as to minimize the average delay of all connections across all servers per unit of time. Such redirection to the different servers is effected as a function of a logical item, the logical item being the factor that the redirector uses in determining where and with what weights the request is to be directed. In determining a solution to a non-linear programming optimization problem, the network delay associated with accessing a server and the server delay, which itself is a function of the access rate on that server, are taken into account. After an initial distribution of logical items is completed, such as for load balancing purposes in accordance with the aforedescribed prior art methodology, or another method, the following are determined: (1) the access rates, which are equal to the number of requests per unit time associated with each redirector-logical item pair; (2) the network delay, which is equal to the sum of the propagation and the transmission delays between the client and the server; and (3) the server delays incurred in processing a web request. Once these parameters are measured or mathematically computed they are used to determine the solution of a non-linear program optimization problem. This non-linear programming problem is formulated and solved as a minimum cost network flow problem to ultimately determine the probability or distributions, or weights, with which each redirector in the network will then redirect requests to the different servers which can satisfy them.
In a specific embodiment of the present invention, highly popular, a/k/a hot sites, are mapped to particular caching servers dispersed in a wide area network, with each hot site being mapped to one or more caching servers. Statistics of access rates to each hot site are dynamically determined by each redirector in the network from the traffic flow and reported to a central management station (CMS). Network delay is similarly measured by each redirector and reported to the CMS and server delay at each server is computed using a queuing model of each server. Using these parameters, the CMS solves a network flow problem to determine the weights with which each redirector will then probabilistically forward requests for a hot site to the different plural servers which are responsible for that requested site. As the access rate statistics, as well as possibly the measured network delay and server delay, dynamically change, the CMS, using the network flow algorithm, recalculates the weights and forwards the adjusted weights back to each redirector. The weights with which each redirector forwards requests for specific documents to a particular server re therefore continually modified in a manner that minimizes the average delay based on the most recent access rate, network delay and server delay statistics.
REFERENCES:
patent: 5031089 (1991-07-01), Liu et al.
patent: 5329619 (1994-07-01), Page et al.
patent: 5495426 (1996-02-01), Waclawsky et al.
patent: 5572643 (1996-11-01), Judson
patent: 5644720 (1997-07-01), Boll et al.
patent: 5774660 (1998-06-01), Brendel et al.
patent: 5828837 (1998-10-01), Eikeland
patent: 5933606 (1999-08-01), Mayhew
patent: 6006259 (1999-12-01), Adelman et al.
patent: 6070191 (2000-05-01), Narendran et al.
patent: 6070192 (2000-05-01), Holt et al.
patent: 6192408 (2001-02-01), Vahalia et al.
G. Goldszmidt et al., NetDispatcher: A TCP Connection Router,IBM Research Report, IBM Research Division, T.J. Watson Research Center, Yorktown Heights, NY, May 19, 1997, vol. RC 20853, p. 1-31.*
A. Bestavros., “Speculative Data Dissemination and Service to Reduce Server Load, Network Traffic and Service Time in Distributed Information System”. 1063-6382 IEEE 1996. pp. 180-187.*
Antoine Mourad., “Scalable Web Server Architect
Paul Sanjoy
Rangarajan Sampath
Burgess Glenton B.
Gurey Stephen M.
Lucent Technologies - Inc.
Safavian Seyed M.
LandOfFree
Method and apparatus for load sharing on a wide area network does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for load sharing on a wide area network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for load sharing on a wide area network will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2584557