Arrangement for load sharing in computer networks

(54) (56)

PATENT HOLDER Telia AB, 123 86 Farsta SE

INVENTOR'S OFFICE

Nail Kavak, Haninge SE Telia Research AB

NAME: Load Balancing Arrangement in Computer Networks PUBLICATIONS: - - (57) SUMMARY: The invention relates to a load balancing arrangement in computer networks and more particularly to an arrangement for distribution of traffic, e.g. via the Internet, from clients (1) to service providers that provide services from a variety of servers. The invention enables distribution to one of a number of replicated servers. Appropriate server is selected e.g. based on available resources at the server's interface or less connection delay. The invention leads to better performance and reduced traffic by distributing the traffic geographically and resources. According to the invention, a number of replicated servers (5A-5E) belong to a common address group (anycast group) and each address group is connected to a domain name server (2) which has the ability to select one of the replicated servers, so that a directive (4) can establish a connection between the selected server and the client requesting service computer. Each replicated server (5A-5E) can send out a resource message that contains information about available resources of the server in question and the server's link parameters.

<img file="SE507720C2_D0001.tif" />

The numbers in brackets indicate international identification code, INID code. Letters in clamps indicate international document code.

507 720

FIELD OF THE INVENTION

The present invention relates to an arrangement for load balancing in computer networks and more particularly to an arrangement for distribution of traffic, e.g. via the Internet, from clients to service providers that provide services from a variety of servers. The invention enables distribution to one of a number of replicated servers. Appropriate server is selected e.g. based on available resources at the server's interface or less connection delay. The invention leads to better performance and reduced traffic by distributing the traffic geographically and resources.

BACKGROUND OF THE ART

Many internationally large companies provide multiple copies of their information servers, in some cases even outside the country, in order to increase accessibility and performance for the Internet user. One problem is that some servers are always more loaded than others, especially as real-time audio and video file transfers are becoming more popular. This leads to blockages in the network.

A conventional way to solve this problem is to replace an existing server with another that has higher processing capacity and more memory space. Most often, however, the problem is not a lack of capacity but a lack of load sharing, ie the solution is usually to make better use of the existing network resources.

In some cases, the information is copied or replicated in many servers that are geographically distributed in different locations to improve response times. Traditionally, traffic is distributed on the various servers using a sequential one

507 720 (round robin) or random technology. In this sequential technology, the servers are sequentially selected in sequence, while the random technique selects servers in any order. None of these techniques utilize information about server load or server location in the network.

The present invention solves the above problems by utilizing information on server load and network topology along with a technique of addressing suitable servers, namely anycast technology (anycast routing and anycast addressing). In this way, the invention can distribute traffic to geographically dispersed servers so that traffic is distributed to, for example, least-loaded server.

SUMMARY OF THE INVENTION

Thus, the present invention provides a load balancing arrangement in computer networks comprising a greater number of users or clients with computers, at least one service provider providing services via a number of replicated servers, a computer network of conductors capable of connecting the client computers to the servers to connect a client computer requesting a service with a suitable server.

According to the invention, a number of replicated servers belong to a common address group (anycast group) and each address group is connected to a domain name server which has the ability to select one of the replicated servers, so that a directive can establish a connection between the selected server and the service requesting client computer. .

Preferably, the domain name server is arranged to select the least-loaded replicated server or the closest replicated server. Each replicated server can send out a resource message containing information about available resources of the server in question and the server's link parameters.

Thanks to the new technique of the present invention, a number of advantages are obtained. End users benefit from lower delay and higher performance. The number of servers in the network or at the service provider can be reduced. It is easy to add or remove servers without it

507 The 720 end users are affected, ie without interrupting ongoing services. This means significantly reduced investment costs and handling costs for the network operator and service provider, while at the same time offering higher performance to the end user. End users are unaware that there are multiple servers providing the same service.

The invention provides cost-effective, automatically configurable and user-transparent solutions. The invention enables step-by-step expansion of servers and adjusts the capacity according to need. Redirecting traffic to the least-loaded server reduces the number of jumps and potential time delays.

BRIEF DESCRIPTION OF THE DRAWINGS

A preferred embodiment of the invention will be described in detail below with reference to the accompanying drawings, of which:

Figure 1 is a diagram of the arrangement of the invention and Figure 2 is an illustration of the format of a resource message according to the invention.

DETAILED DESCRIPTION OF PREFERRED EMBODIMENTS

One of the significant limited resources e.g. The World Wide Web is the network bandwidth and processor capacity of servers and client computers. Broadband bandwidth and processor power are generally increasing but not fast enough to keep up with the ever-increasing number of users in the network. The number of users will soon be one billion.

This would not be a problem if users restricted their activities to their local machines but the network allows users to request documents and services from remote servers. It is also true that some servers are more popular than others, which means that these servers may carry too high a load, although there are many servers that can provide the same services. One solution to this problem is to store the documents closer to the users. This reduces both network traffic and server load. A similar solution is replication or copying

507 720 which essentially means buffer storage before ordering the documents. The cost of mass replication can be reduced by using stream broadcast distribution as supported by NNTP (Network News Transfer Protocol). Furthermore, replication can be applied to both services and documents. If replicated servers are in clusters close to the original server, this reduces the load on the individual server but does not reduce network traffic since all orders still go to the cluster. However, if replicated servers are distributed over the network and if clients can automatically locate the nearest or least loaded server, this would also reduce network traffic.

The object of the present invention is to provide an arrangement with which the network resources can be used more efficiently. The goal is to dynamically direct user traffic to a least-loaded application server. The advantages thus obtained are mentioned above. Although the invention is described with particular reference to IP over ATM (ie networks that work with Internet protocols with Asynchronous Transfer Mode), the invention can also be applied to techniques other than ATM.

Figure 1 shows a diagram of a preferred arrangement according to the invention. A client computer 1 has a virtual circuit connection established to its domain name servers (DNS) 2, one of which is shown in the figure, via the network 3. There may be a secondary connection to a backup domain name server (not shown) that can be contacted in the event of a failure or interruption. In the network there are a number of conductors 4 which establish connections with servers 5A to 5E at service providers. All servers 5A, 5B, 5C, 5D, 5E are copies of each other and form the same anycast group or co-address group. Anycast groups only broadcast a virtual IP address to their neighbors. A logical address can correspond to several physical addresses.

The domain name server has knowledge of all the anycast groups. For scalability and performance reasons, anycast groups can be distributed across multiple domain name servers. Anycast group members are connected to the domain name servers with a point-to-multipoint connection.

The function of the event can be summarized as follows. The client computer first sends a request to a domain name's 507 720 server to resolve a domain name to an IP address. Control messages to and from the domain name server are represented by the larger arrows 6 in the figure. The domain name server first checks the semantics of the DNS request to find out which application was requested. For example, an ftp request is treated differently than a ping request. The former is long-lived while the latter is short-lived. The type of application helps the domain name server to select the most relevant server for each request. In some cases, the least-loaded server is selected, while in other cases the cheapest link and associated server are selected.

In an IPATM network, a transmitter sometimes prefers to use the shortest route for time-critical applications, e.g. images, video, ftp, and in other cases, the same transmitter would prefer the cheapest route, such as ping, dns, etc.

The domain name server receives continuous routing information from all anycast servers it serves. The routing information is transmitted via the connections labeled 7 in Figure 1. The routing information includes details of the available capacity for each link, the number of jumps to each server, each link's bandwidth, processor capacity, measured delay, and so on. The domain name server returns the IP address of the server that is best adapted to the application requirements derived from the DNS request. When the IP address is resolved, it is returned to the client computer so that a direct connection is established between the client computer and the server. The connection is transparent to the domain name server. The service or document requested can then be transferred to the client computer. The data flow is shown at 8 in Figure 1.

Anycast technology is used to select a server from the various suitable, similar servers. An anycast address (co-address) is used to represent a group of nodes, one of which is to be selected. When an anycast address is received, the domain name server delivers the IP address to all destinations represented by the anycast address. Since many servers can have the same anycast address, the manager conventionally selects one of them by retrieving information about the number of jumps to the different servers and choosing the closest one. Link usage is another currently available criterion. Other possible criteria are cost, processor load,

507 720 memory space, routing policy, etc.

An important aspect of the invention is the use of anycast technology to access services provided by one of a larger number of servers operating on different network nodes. In particular, the same service can be accessed with a single anycast address regardless of how many servers are used for the service and where the servers are located in the network. Copying the service on many servers over the net is valuable when high service availability is required. Other services that could take advantage of anycast technology include: World Wide Web, video services, domain name servers, address resolution servers, Neighbor Discovery servers, 020 number services, telephony over the Internet and the public telecommunications network to find the most cost effective voice services, etc.

An ANC server ANS, which may be located in conjunction with the domain name server 2, holds membership information for all anycast service members 5A-5E. A node can register with the anycast service, join as a member, exit and stop participating in the ANS service.

In order for load sharing to be distributed on least-loaded server, each server needs to communicate its available resources to the environment. To this end, a resource message RA (Resource Advertisement) is broadcast. When calculating service quality routes (QoS routes), RA is used.

Each server generates a resource message for each area and specifies the largest amount of available resources for reservations on each of the server's interfaces in the area along with the link delay parameters. These parameters are roughly analogous to the default cost value open shortest path first OSPF (Open Shortest Path First) but are independent of the standard service type value to better characterize a link's static delay properties. A new copy of the resource message is generated whenever a new routing resource message is generated for the area or whenever the available bandwidth resource or delay changes for a link in the area. An algorithm can be used so that a new resource message is generated only when the available bandwidth resource changes significantly. Resource messages are being sent

507 720 through a single region. The format of the resource message is shown in Figure 2.

The number of links is the number of links included in the resource message. For each link, the link type, link identity, and link data are the same as for the routing resource message. The available link resource is represented by packet data parameters in floating point format with simple precision according to IEEE, as well as in the service model Control Load. The link delay is a static delay value for the link expressed in milliseconds.

The input to the routing calculation includes the source address and destination address and the service quality requirements for the flow, which are currently the packet data parameters from the Resource Reservation Protocol Path message but could also be derived from other trigger units. To calculate the best route or route with the lowest delay, the static delay value is used in the same way that OSPF uses the conductor's TOS (Type of Service) zero cost value.

The DNS server needs both information about available resources and existing resource reservation in addition to the normal topology and membership information.

When a new replicated server joins an anycast group, the local conductor informs the presence of the service as part of its normal routing exchanges with the neighboring conductors. If the local router notices that a replicated server has stopped sending messages, this negative information is also sent to the neighboring routers. The neighbor conductors each study a distance value for the announced anycast server, update their tables based on this value, and in turn forward the updated information to their neighbors. Each manager maintains knowledge at least about the path to the nearest anycast servers and possibly a small list of alternative servers in case it is announced that the previous nearest server is down. In this way, each conductor in the network gets sufficient knowledge to route anycast packets to the nearest server, but does not need to maintain a database of all the anycast servers in the network. If a client sends a connection request to

507 720 anycast group and if it is not a service in the local subnet, the local router forwards the packet to the nearest replicated server based on the current routing tables.

It is assumed that an anycast call can be routed to any of the servers at a normal level in the server hierarchy, regardless of where these servers are physically located in the network. For many applications, the normal level would be either the level of the anycast caller's node or the closest level. The Anycast caller should not need to know any details about how the server hierarchy is organized or even how the levels in the server hierarchy are numbered. All that the caller needs to specify is that an anycast call should be routed to a server at the lowest possible higher level where a server can be found. In order to meet the requirements and address a single-address server hierarchy, the invention proposes to broaden the definition of proximity used by routing algorithms to include new proximity measurement parameters. Suppose that Private Network Node Interface (PNNI) routing levels are used to identify the hierarchy level of the servers. If we let the difference between two routing level identifiers be an acceptable measure of proximity between two corresponding nodes, an anycast caller does not need to directly specify a level in the hierarchy. Using this measurement parameter, routing to servers at the lowest possible higher level in a hierarchy of servers can be supported regardless of the physical distance between the requested server and the client.

Thus, the present invention provides a load balancing arrangement which solves the problems stated. One skilled in the art will recognize that the invention can be implemented in many different ways with different combinations of hardware and software without departing from the scope of the invention. The scope of the invention is limited only by the claims below.

507 720