Loading balancing across servers in a computer network

Details Loading balancing across servers in a computer network Loading balancing across servers in a computer network

1997-05-30

2002-02-26

Lim, Krisna (Department: 2153)

Electrical computers and digital processing systems: multicomput

Computer-to-computer data routing

C709S239000, C709S240000, C709S241000, C709S242000, C370S237000, C370S400000

Reexamination Certificate

active

06351775

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates generally to providing load balancing across a collection (or cluster) of servers such as proxy servers and Web servers in the Internet environment. A more particular aspect of the present invention relates to a method of updating routing information using meta data piggybacked with the response to client requests. Yet another aspect is related to a load balancing method which also optimizes caching efficiency.
GLOSSARY OF TERMS
While dictionary meanings are also implied by certain terms used here, the following glossary of some terms may be useful.
Internet
The network of networks and gateways that use the TCP/IP suite of protocols.
Client
A client is a computer which issues commands to the server which performs the task associated with the command.
Server
Any computer that performs a task at the command of another computer is a server. A Web server typically supports one or more clients.
World Wide Web (WWW or Web)
The Internet's application that lets people seeking information on the Internet switch from server to server and database to database by clicking on highlighted words or phrases of interest (hyperlinks). An Internet WWW server supports clients and provides information. The Web can be considered as the Internet with all of the resources addressed as URLs and which uses HTML to display the information corresponding to URLs and provide a point-and-click interface to other URLs.
Universal Resource Locator (URL)
A way to uniquely identify or address information on the Internet. Can be considered to be a Web document version of an e-mail address or a fully-qualified network file name. They can be accessed with a Hyperlink. An example of a URL is “http://www.philipyu.com:80/table.html”. Here, the URL has four components. Starting from the left, the first specifies the protocol to use, separated from the rest of the locator by a “:”. Next is the hostname or IP address of the target host; this is delimited by the “//” on the left and on the right by a “/” or optionally a “:”. The port number is optional, and is delimited on the left from the hostname by a “:” and on the right by a “/”. The fourth component is the actual file name or program name. In this example, the “.html” extension means that this is an HTML file.
HyperText Markup Language (HTML)
HTML is a language which can be used, among other things, by Web servers to create and connect documents that are viewed by Web clients. HTML uses Hypertext documents.
Hypertext Transfer Protocol (HTTP)
HTTP is an example of a stateless protocol, which means that every request from a client to a server is treated independently. The server has no record of previous connections. At the beginning of a URL, “http:” indicates the file should be retrieved using http.
Internet Browser or Web Browser
A graphical interface tool that runs Internet protocols such as http, and display results on the user's screen. The browser can act as an Internet tour guide, complete with pictorial desktops, directories and search tools used when a user “surfs” the Internet. In this application the Web browser is a client service which communicates with the World Wide Web.
Client Cache
Client caches are typically used as primary caches for objects accessed by the client. In a WWW environment, client caches are typically implemented by web browsers and may cache objects accessed during a current invocation, i.e., a nonpersistent cache, or may cache objects across invocations.
Caching Proxies
Specialized servers in a network which act as agents on the behalf of the client to locate a cached copy of an object. Caching proxies typically serve as secondary or higher level caches, because they are invoked as a result of cache-misses from client caches.
HTTP Daemon (HTTPD)
A server having Hypertext Markup Language and Common Gateway Interface capability. The HTTPD is typically supported by an access agent which provides the hardware connections to machines on the intranet and access to the Internet, such as TCP/IP couplings.
BACKGROUND
The traffic on the World Wide Web is increasing exponentially. Proxy servers, especially at a gateway to a large organization or region, can comprise a collection of computing nodes. Similarly, at popular (hot) Web sites, a collection (or cluster) of computing nodes is used to support the access demand.
To achieve good performance in a server cluster, the load should be balanced among the collection of nodes. This should be tempered by the need to optimize the cache hit ratio in a given server in the cluster by localizing identical object requests.
Previous work on load balancing in a multi-processor or multiple node environment, such as the IBM S/390 Sysplex, primarily focused on scheduling algorithms which select one of multiple generic resources for each incoming task or user session. The scheduler controls the scheduling of every incoming task or session and there is no caching of the resource selection.
One known method for balancing the load among geographically distributed replicated sites is known as the Round-Robin Domain Name Server (RR-DNS) approach. In the paper by Katz., E., Butler, M., and McGrath, R., entitled “A Scaleable HTTP Server: The NCSA Prototype”, Computer Networks and ISDN Systems, Vol. 27, 1994, pp. 68-74, the RR-DNS method is used to balance the node across a set of web server nodes. Here, the set of distributed sites is represented by one URL (e.g., www.hotsite.com); a cluster sub-domain for this distributed site is defined with its sub-domain name server. The sub-domain name server maps the name resolution requests to different IP addresses (in the distributed cluster) in a round-robin fashion. Thus, subsets of the clients will be assigned to each of the replicated sites. In order to reduce network traffic, a mapping request is not issued for each service request. Instead, the result of the mapping request is saved for a “time-to-live” (TTL) interval. Subsequent requests issued during the TTL interval retain the previous mapping and hence will be routed to the same server node.
A problem with the RR-DNS method is that a load imbalance among the distributed sites may result (see e.g., Dias, D. M., Kish, W., Mukherjee, R., and Tewari, R., in “A Scaleable and Highly Available Web Server”, Proc. 41st IEEE Computer Society Intl. Conf. (COMPCON) 1996, Technologies for the Information Superhighway, pp. 85-92, February 1996). The load imbalance can be caused by caching of the association between a name and IP address at various gateways, fire-walls, and domain name-servers in the network. Thus, for the TTL period all new client requests routed through these gateways, fire-walls, and domain name-servers will be assigned to the single site stored in the cache. Those skilled in the art will realize that a simple reduction in the TTL value will not solve the problem. In fact, low TTL values are frequently not accepted by many name servers. More importantly, a simple reduction of TTL value may not reduce a load skew caused by unevenly distributed client request rates.
One method of load balancing within a local cluster of nodes is to use a so-called TCP router as described in: “A Virtual Multi-Processor Implemented by an Encapsulated Cluster of Loosely Coupled Computers,” by Attanasio, Clement R. and Smith, Stephen E., IBM Research Report RC 18442, 1992; and U.S. Pat. No. 5,371,852, entitled “Method and Apparatus for Making a Cluster of Computers Appear as a Single Host,” issued Dec. 6, 1994 which is hereby incorporated by reference in its entirety. Here, only the address of the TCP router is given out to clients; the TCP router distributes incoming requests among the nodes in the cluster, either in a round-robin manner, or based on the load on the nodes. It should be noted that this TCP router method is limited to a local cluster of nodes.
More recently, in the paper by Colajanni, M., Yu, P., and Dias, D., entitled “Scheduling Algorithms for Distributed Web Servers,” IBM Research Report, RC 20680, January 1997, which is hereby incorporated by referen

Affiliated with

Also associated with

Rating

Loading balancing across servers in a computer 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 Loading balancing across servers in a computer network, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Loading balancing across servers in a computer network will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2977879