System and method for information object routing in computer networks

• US 7,552,233 B2
• Filed: 09/10/2002
• Issued: 06/23/2009
• Est. Priority Date: 03/16/2000
• Status: Expired due to Term

• Current Assignee: ADARA Networks, Inc.
• Original Assignee: ADARA Networks, Inc.
• Inventors: Garcia-Luna-Aceves, J. J., Smith, Bradley R., Raju, Jyoti
• Primary Examiner(s): Etienne; Ario
• Assistant Examiner(s): Higa; Brendan Y
• Application Number:
  US10/241,767
• Publication Number:
  US 20030200307A1
• Time in Patent Office: 2,478 Days
• Field of Search: 709227-229, 709230-237, 709223-226, 709217-219, 709/221, 709/228, 709238-244
• US Class Current: 709/238
• 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 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

Abstract

An address of a server that should supply an information object or service to a requester is returned in response to a request therefor. The address of the server that is returned is an optimal server selected according to specified performance metrics. The specified performance metrics may include one or more of an average delay from the server to another, average processing delays at the server, reliability of a path from the server to another, available bandwidth in said path, and loads on the server.

Claims

1. A method, comprising:

returning, in response to a request from a client, an address of a first server that should service a second server'"'"'s request for an information object based on the second server receiving the client'"'"'s request of the information object that is not located at the second server, the address of the first server being selected according to specified performance metrics, wherein the specified performance metrics comprise average processing delays at the first server, average delay from the first server to the second server, reliability of a path from the first server to the second server, and available bandwidth in said path from the first server to the second server;

referring the second server'"'"'s request for the information object to a first Web router; and

configuring the first Web router to create a map that associates an identifier of the information object with the address of the first server according to other mappings generated by other Web routers and forwarded to the first Web router, wherein the other mappings generated by the other Web routers are forwarded to the first Web router as inter-Web router communication messages passed between the Web routers using a Web Information Locator by Distance (WILD) protocol.

2. The method of claim 1 wherein the specified performance metrics comprises average delay from the first server to the second server, average processing delays at the first server, reliability of a path from the first server to the second server, available bandwidth in said path, and loads on the first server.

3. The method of claim 2 wherein the first server is an optimum server for servicing the second server'"'"'s request.

4. The method of claim 3 wherein the first server is the optimum server, because the first server offers a lowest response time in delivering the information object, according to the specified performance metrics.

5. The method of claim 1 wherein upon receipt of an instruction to do so, the first server contacts an information object repository determined to store the information object.

6. The method of claim 1 wherein the first server stores a copy of the information object.

7. The method of claim 1 wherein the first server and the second server are coupled together through a virtual network.

8. The method of claim 1 wherein the map is generated by the first Web router according to the specified performance metrics, which comprise one or more of average delay from the first server to the second server, average processing delays at the first server, reliability of a path from the first server to the second server, available bandwidth in said path, and loads on the first server.

9. The method of claim 1 wherein one or more the communication messages passed between the Web routers further report an associated address of one of the other Web routers co-located with an information object repository that contains the information object.

10. The method of claim 1 wherein the other mappings specify optional associations of information object identifiers to information object repository addresses.

11. The method of claim 1 wherein the map is based on distance information obtained using a routing protocol that provides accurate distances from one Web router to another, the distance information being based on one or more of the specified performance metrics.

12. The method of claim 11 wherein the routing protocol is at least one of:

a diffusing update algorithm (DUAL);

a loop-free path-finding algorithm (LPA);

a link-vector algorithm (LVA);

a bandwidth efficient source tree (BEST) protocol;

a dynamic source tree (DST) routing protocol;

a diffusing algorithm for shortest multipaths (DASM);

a multipath distance vector algorithm (MDVA);

a routing on-demand acyclic multipath (ROAM) protocol;

a multiple-path partial-topology dissemination algorithm (MPDA);

a multipath loop-free routing algorithm (MPATH);

an adaptive link-state protocol (ALP);

a topology broadcast protocol;

a path vector algorithm used as part of the Border Gateway Protocol (BGP);

or a static table in the first Web router specifying the next hops or paths to one or more other active Web routers.

13. The method of claim 1 wherein the first Web router executes a communication protocol with which it determines:

addresses of other Web routers participating in a virtual overlay network with the first Web router; and

optimum distances to each Web router in the virtual overlay network.

14. The method of claim 13 wherein the first Web router further determines neighbor Web routers that offer the optimum distances to each Web router in the virtual overlay network.

15. The method of claim 13 wherein the first Web router updates the map according to messages received from other Web routers in the virtual overlay network.

16. The method of claim 15 wherein the map is implemented as one or more tables stored in a computer readable medium.

17. A communication system, comprising:

one or more messages passed between Web routers over a Web information locator by distance (WILD) protocol, used for inter-Web router communication, said messages including information which allows said web routers to dynamically update mappings of information objects to server addresses including an address of a first server that should service a second server'"'"'s request for an information object in response to the second server receiving a client requestor'"'"'s request for an information object that is not located at the second server based on specified performance metrics, wherein the specified performance metrics comprise an average processing delay at the first server, average delay from the first server to the second server, reliability of a path from the first server to the second server, and available bandwidth in said path from the first server to the second server; and

a first web router, comprising a general purpose computer, for receiving the second server'"'"'s request for the information object, wherein the first web router is configured to create a map that associates an identifier of the information object with the address of the first server according to other mappings generated by other web routers and forwarded to the first web router, wherein the other mappings generated by the other Web routers are forwarded to the first Web router as inter web router communication messages passed between the web routers using a Web information locator by distance (WILD) protocol.

18. The communication system of claim 17 wherein the mappings are optimal mappings of the information objects to the server addresses.

19. The communication system of claim 18 wherein the specified performance metrics comprises average delay from a server to another, an average processing delay at a server, reliability of a path from a server to another, available bandwidth in such a path, and loads on a server.

20. The communication system of claim 18 wherein said messages report updated distances from said server addresses to another information object, said distances being based on said specified performance metrics.

21. The communication system of claim 20 wherein said messages further report, for each updated distance, an associated server.

22. The communication system of claim 21 wherein said messages further report, for each updated distance, an associated address of a first Web router co-located with a first server that is a subject of the message.

23. The communication system of claim 17. wherein Web routers dynamically update mappings in response to one or more of the following inputs:

addition/deletion messages from an associated information object repository, changes in load messages from the associated information object repository, changes in information object repository connectivity information, URL updates from neighbor Web routers, changes in Web router neighbor connectivity information, changes in distances to other Web Routers, and URL lookup queries.

24. The communication system of claim 23 wherein in response to one or more of the inputs, Web routers take one or more of the following actions;

if an input offers a better distance to a URL than is currently maintained, change a corresponding routing table entry accordingly and transmit an add message;

if an input offers a worse distance than a present routing table entry, ignore that input;

if an input causes a loss of a last path, transmit a delete message; and

if an input causes a distance increase, change a corresponding routing table entry accordingly and transmit a query.

25. A method, comprising

mapping an address of a requesting server seeking an information object to an address of an information object repository that has a best distance to the requesting server based on the requesting server receiving a requestor'"'"' s request of the information object that is not located at the requesting server according to specified performance metrics, wherein the specified performance metrics comprise average processing delays at the requesting server, average delay from one information object repository to another within a network, reliability of a path from one information object repository to another, and available bandwidth in said path;

and

referring the requesting server'"'"'s request for the information object to a first Web router; and

configuring the first Web router to create a map that associates an identifier of the information object with the address of the information object repository according to other mappings generated by other Web routers and forwarded to the first Web router, wherein the other mappings generated by the other Web routers are forwarded to the first Web router as inter-Web router communication messages passed between the Web routers using a Web Information Locator by Distance (WILD) protocol.

26. The method of claim 25 wherein distance information between information object repositories is computed according to a shortest-path first algorithm.

27. The method of claim 25, further comprising verifying mapping information between the information object and the requesting server by only trusting a neighbor node of a communication network that offers a shortest path to the requesting server.

28. The method of claim 27 wherein in the case of two or more equal distances, that mapping information which is received is adopted.