System and method for directing clients to optimal servers in computer networks

• US 20030101278A1
• Filed: 09/10/2002
• Published: 05/29/2003
• Est. Priority Date: 03/16/2000
• Status: Active Grant

• Current Assignee: Online Video Network, Inc.
• Original Assignee: Online Video Network, Inc.
• Inventors: Vutukury, Srinivas, Garcia-Luna-Aceves, J.J.
• Granted Patent: US 7,664,876 B2
• Time in Patent Office: Days
• US Class Current: 709/240
• CPC Class Codes: G06F 12/1483 using an access-table, e.g. matrix or list
• CPC Class Codes: G06F 16/9574 of access to content, e.g. by caching
• CPC Class Codes: H04L 12/18 for broadcast or conference , e.g. multicast
• CPC Class Codes: H04L 43/0805 by checking availability
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 61/457 containing identifiers of data entities on a computer, e.g. file names
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1006 with static server selection, e.g. the same server being selected for a specific client
• CPC Class Codes: H04L 67/1008 based on parameters of servers, e.g. available memory or workload monitoring of computer activity G06F11/30
• CPC Class Codes: H04L 67/101 based on network conditions
• CPC Class Codes: H04L 67/1014 based on the content of a request
• CPC Class Codes: H04L 67/1023 based on a hash applied to IP addresses or costs
• CPC Class Codes: H04L 67/1038 Load balancing arrangements to avoid a single path through a load balancer
• CPC Class Codes: H04L 67/568 Storing data temporarily at an intermediate stage, e.g. caching

Abstract

A communication protocol includes one or more messages passed between Web routers over a reliable transmission protocol used for inter-Web router communication. These messages include information that allows the Web routers to dynamically update mappings of client addresses or address ranges to information object repository addresses based on client-to-server distance and server load. The mappings are preferably optimal mappings of the client addresses or address ranges to the information object repository addresses and the messages report updated distances from these information object repository addresses to the client addresses or address ranges. For example, the messages may report, for each updated distance, an associated client address or address range and/or an associated anchor address of a Web router co-located with an information object repository that is the subject of the message.

Claims

1. A method, comprising:

constructing, at one or more of a collection of Web routers communicatively coupled to one another via a computer network that supports an inter-Web router communication protocol wherein inter-Web router communication messages are exchanged between neighbor Web routers, one or more tables containing client-to-server distance information, the tables constructed by each of the respective Web routers being stored in a computer-readable medium accessible by the corresponding Web router, wherein the term client refers to any information object requesting device, or a group thereof, communicatively coupled to one or more of the Web routers and the term server refers the any information object repository accessible by one or more clients; and

determining, using the client-to-server distance information contained in one or more of the tables, a best server for servicing a request for a particular information object made by one of the clients.

2. The method of claim 1, wherein the best server is determined in terms of distance from the best server to the client making the request and a current load on the best server.

3. The method of claim 2, wherein the distance from the best server to the client making the request is measured in terms of network latency.

4. The method of claim 2, further comprising updating the tables in response to revised client-to-Web router distance information.

5. The method of claim 4, wherein the revised client-to-Web router distance information is included in the inter-Web router communication messages.

6. The method of claim 5, wherein the revised client-to-Web router distance information is determined, at least in part, from internetwork connectivity information received through an exchange of messages according to an inter-domain routing protocol.

7. The method of claim 6, wherein the inter-domain routing protocol comprises a Border Gateway Protocol.

8. The method of claim 2, further comprising updating the tables in response to revised server load information.

9. The method of claim 8, further comprising updating the tables in response to revised client-to-Web router distance information.

10. The method of claim 9, wherein the revised client-to-Web router distance information is included in the inter-Web router communication messages.

11. The method of claim 10, further comprising transmitting updated table information to one or more of the Web routers using one or more inter-Web router communication messages.

12. The method of claim 8, further comprising updating the tables in response to revised client-to-server distance information.

13. The method of claim 12, wherein the revised client-to-server distance information is included in one or more inter-Web router communication messages.

14. A communication protocol, comprising one or more messages passed between Web routers over a reliable transmission protocol used for inter-Web router communication, said messages including information which allows said Web routers to dynamically update mappings of client addresses or address ranges to information object repository addresses based on client-to-server distance and server load, wherein the term client refers to any information object requesting device, or a group thereof, communicatively coupled to one or more of the Web routers and the term server refers the any information object repository accessible by one or more clients.

15. The communication protocol of claim 14 wherein the mappings are optimal mappings of the client addresses or address ranges to the information object repository addresses.

16. The communication protocol of claim 14 wherein the messages report updated distances from said information object repository addresses to said client addresses or address ranges.

17. The communication protocol of claim 16 wherein the messages further report, for each updated distance, an associated client address or address range.

18. The communication protocol of claim 17 wherein said messages further report, for each updated distance, an associated anchor address of a Web router co-located with an information object repository that is the subject of the message.

19. A method, comprising creating, at a first Web router of a network of Web routers, a network latency map for at least one of the Web routers of the network and a client communicatively coupled to the at least one Web router using internetwork connectivity information received at the first Web router through an inter-domain routing protocol, and disseminating the network latency map from the first Web router to one or more neighbor Web routers of the first Web router through a reliable communication protocol used for inter-Web router communication messages exchanged via the network.

20. The method of claim 19 wherein the network latency map specifies a distance between the client and the at least one Web router as reported by the first Web router.

21. The method of claim 19 further comprising using, the at least one Web router, the network latency map to produce a client-to-server map which specifies a most favored server for servicing information object requests by the client.

22. The method of claim 21 wherein the client-to-server map is produced by combining server load information with information specified by the network latency map.

23. The method of claim 22 wherein the client-to-server map combining comprises adding.

24. The method of claim 23 wherein the server load and the distance between the client and the at least one Web router are measured in common units.

25. The method of claim 23 further comprising updating the client-to-server map in response to one or more of a server load change or a network latency map update.

26. The method of claim 25 wherein the network latency map update is transmitted as one of the inter-Web router communication messages exchanged via the network.

27. The method of claim 25 wherein in response to updating the client-to-server map, a client-to-server map update is transmitted as one of the inter-Web router communication messages exchanged via the network.

28. The method of claim 23 further comprising updating the client-to-server map in response to a network latency map update only if the network latency map update specifies a better mapping than the client to server map.

29. The method of claim 28 wherein the network latency map update specifies a better mapping than the client-to-server map if a first sequence number associated with the network latency map update is greater than a second sequence number associated with the client-to-server map.

30. The method of claim 28 wherein the network latency map update specifies a better mapping than the client-to-server map if a first distance associated with the network latency map update is less than a second distance associated with the client-to-server map.

31. The method of claim 28 wherein the network latency map update specifies a better mapping than the client-to-server map if a first result of a hashing function computed using one or more parameters of the network latency map update is less than a second result of the hashing function computed using corresponding one or more parameters of the client-to-server map.

32. A method, comprising receiving, at a first Web router, an inter-Web router communication message including an update for a mapping between a client and a second Web router and updating, at the first Web router, a client-to-Web router table to include the mapping between the client and the second Web router if this client-to-Web router mapping specifies a better client-to-Web router distance than is currently maintained in the client-to-Web router table for the client.

33. The method of claim 32 further comprising propagating the mapping between the client and the second Web router to neighbor Web routers of the first Web router.

34. The method of claim 32 further comprising using the mapping between the client and the second Web router to compute a client-to-server mapping.

35. The method of claim 34 further comprising updating, at the first Web router, a client-to-server table to include the client-to-server mapping if the client-to-server mapping specifies a better client-to-server distance than is currently maintained in the client-to-server table for the client.

36. The method of claim 35 further comprising propagating the client-to-server mapping to neighbor Web routers of the first Web router.

37. The method of claim 34 wherein the client-to-server mapping is computed by adding server load to distance information included in the client-to-Web router mapping.

38. The method of claim 32 wherein determining whether the client-to-Web router mapping specifies a better client-to-Web router distance than is currently maintained in the client-to-Web router table for the client comprises comparing one or more of (1) sequence numbers associated with the client-to-Web router mapping and the client-to-Web router distance maintained in the client-to-Web router table, (2) anchor addresses associated with the client-to-Web router mapping and the client-to-Web router distance maintained in the client-to-Web router table, (3) Web router addresses associated with the client-to-Web router mapping and the client-to-Web router distance maintained in the client-to-Web router table, or (4) distances associated with the client-to-Web router mapping and the client-to-Web router distance maintained in the client-to-Web router table.