System and method for discovering information objects and information object repositories in computer networks

• US 20010056416A1
• Filed: 03/15/2001
• Published: 12/27/2001
• Est. Priority Date: 03/16/2000
• Status: Active Grant

• Current Assignee: Cents Technologies, Inc., Online Video Network, Inc.
• Original Assignee: Online Video Network, Inc.
• Inventors: Garcia-Luna-Aceves, J.J.
• Granted Patent: US 7,162,539 B2
• Time in Patent Office: Days
• US Class Current: 1/1
• 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

An address of an information object repository that should service a client request for an information object is returned in response to a request therefor. The address of the information object repository which is returned is selected according to specified performance metrics regardless of whether or not the information object repository maintains a local copy of the information object that is the client request. In some cases, the address of the information object repository is further selected according to an address of a client making the client request. Further, the address of the information object repository is selected from a number of addresses of information object repositories. The specified performance metrics may include one or more of an average delay from the information object repository to the client, average processing delays at the information object repository, reliability of a path from the information object repository to the client, available bandwidth in said path, and loads on the information object repository. In some cases, the information object repository may be instructed to obtain a copy of the information object after the address of the information object repository is returned in response to the request therefore.

Claims

1. A method, comprising returning, in response to a request therefore, an address of an information object repository that should service a client request for an information object, the address of the information object repository being selected according to specified performance metrics regardless of whether or not the information object repository maintains a local copy of the information object that is the client request.

2. The method of

claim 1

wherein the address of the information object repository is further selected according to an address of a client making the client request.

3. The method of

claim 2

wherein the specified performance metrics comprise one or more of average delay from the information object repository to the client, average processing delays at the information object repository, reliability of a path from the information object repository to the client, available bandwidth in said path, and loads on the information object repository.

4. The method of claims 2 wherein the address of the information object repository is selected from a number of addresses of information object repositories.

5. The method of

claim 1

further comprising instructing the information object repository to obtain a copy of the information object after returning the address of the information object repository in response to the request therefore.

26. The method of

claim 1

wherein an address of a second information object repository that maintains a local copy of the information object specified in the client request is provided to the information object repository selected to service the client request. The selection of the information object repository maintaining a copy of an object is made according to one or more of the specified performance metrics.

6. 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 specified performance metrics.

7. The communication protocol of

claim 6

wherein the mappings are optimal mappings of the client addresses or address ranges to the information object repository addresses.

8. The communication protocol of

claim 7

wherein the specified performance metrics comprise are one or more of average delay from an information object repository to a selected client address or address range, an average processing delay at an information object repository, reliability of a path from an information object repository to a client, available bandwidth in such a path, and loads on an information object repository.

9. The communication protocol of

claim 7

wherein said messages report updated distances from said information object repository addresses to said client addresses or address ranges, said distances being based on said specified performance metrics.

10. The communication protocol of

claim 9

wherein said messages further report, for each updated distance, an associated client address or address range.

11. The communication protocol of

claim 10

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

28. The communication protocol of

claim 6

wherein said messages also include second mappings of information object identifiers to information object repository addresses that maintain local copies of information objects.

29. The communication protocol of

claim 28

wherein the second mappings comprise optimal mappings of information object identifiers to information object repository addresses.

30. The communication protocol of

claim 9

wherein said messages further report second updated distances from the information object repository addresses to specified information object repositories hosting particular information objects or services, these distances being based on the specified performance metrics.

12. A method, comprising mapping an address of a client seeking an information object to one or more addresses of information object repositories that have a first best distance to the client address according to specified performance metrics independently of whether the information object repositories maintain a local copy of the information object sought by the client.

13. The method of

claim 12

further comprising mapping the address of the client to one or more addresses of redirecting Web routers that have a second best distance to the client according to some or all of the specified performance metrics.

14. The method of

claim 12

wherein the specified performance metrics include one or more of an average delay from the information object repositories to the clients, an average processing delay at the information object repositories, reliability of the paths from the information object repositories to the clients, available bandwidth in such paths, and loads on the information object repositories.

15. The method of

claim 12

wherein distance information between client addresses and information object repositories is computed according to a shortest-path first algorithm.

16. The method of

claim 12

wherein distance information between client addresses and information object repositories is computed according to routing information provided by internetwork routers.

17. The method of

claim 16

wherein the routing information comprises inter-domain and intra-domain routing information.

18. A method, comprising verifying mapping information between client addresses or address ranges and one or more information object repositories according to whether or not a distance between a Web router maintaining the mapping information and a Web router that originated the mapping information is finite.

19. The method of

claim 18

further comprising adopting the mapping information for at least one of the client addresses or address ranges.

20. The method of

claim 19

further comprising selecting from among two or more valid mappings for the at least one of the client addresses or address ranges according to type of service distance associated with the mappings.

21. The method of

claim 20

, wherein the type of service distances are determined according to average processing delays at the information object repositories, average delays from the information object repositories to the client addresses or address ranges, reliability of paths between the information object repositories and the client addresses or address ranges, available bandwidth in said paths, and/or loads at the information object repositories.

22. The method of

claim 20

wherein in the case of two or more equal type of service distances, that mapping information which is originated by a Web router having a smallest minimum-hop distance to the Web router maintaining the mapping information is adopted.

31. The method of

claim 18

further comprising verifying second mapping information between information object identifiers and information object repository addresses according to whether or not a distance between a Web router maintaining the second mapping information and a Web router that originated the second mapping information is finite.

32. The method of

claim 31

wherein the distance between the Web router maintaining the second mapping information and the Web router that originated the second mapping information comprises a minimum-hop distance.

33. The method of

claim 31

further comprising adopting the second mapping information for each known information object identifier.

34. The method of

claim 18

wherein the distance between the Web router maintaining the mapping information and the Web router that originated the mapping information comprises a minimum-hop distance.

23. A method, comprising:

determining which of a number of available information object repositories should service a client'"'"'s request for an information object or service;

determining which of the information object repositories actually maintains the information object or service requested by the client; and

bringing the information object or service requested by the client to the information object repository which it has been determined should service the client request.

24. The method of

claim 23

wherein bringing the information object or service requested by the client to the information object repository which it has been determined should service the client request comprises instructing that information object repository to retrieve the information object or service requested by the client from the information object repository which actually maintains the information object or service.

25. The method of

claim 24

wherein upon receiving an instruction to do so, the information object repository which it has been determined should service the client request contacts the information object repository which actually maintains the information object or service requested by the client directly to request the information object or service.

27. The method of

claim 27

wherein the second information object repository is selected according to one or more of the specified performance metrics.