REPLICA/CACHE LOCATOR, AN OVERLAY NETWORK AND A METHOD TO LOCATE REPLICATION TABLES AND CACHES THEREIN

• US 20090006593A1
• Filed: 06/29/2007
• Published: 01/01/2009
• Est. Priority Date: 06/29/2007
• Status: Active Grant

• Current Assignee: RPX Corporation
• Original Assignee: Alcatel Lucent Technologies BV (Nokia Corporation)
• Inventors: Cortes, Mauricio
• Granted Patent: US 8,930,522 B2
• Time in Patent Office: Days
• US Class Current: 709/223
• CPC Class Codes: H04L 12/66 Arrangements for connecting between networks having differing types of switching systems, e.g. gateways

Abstract

A replica/cache locator, a method to locate replication tables and caches in an overlay network having multiple nodes and an overlay network. In one embodiment, the method includes: (1) determining a network distance between a first node of the multiple nodes in the overlay network and each of the remaining multiple nodes, (2) calculating m clusters of the multiple nodes based on the network distances and (3) designating at least a single node from the m clusters to include a replication table of the first node.

Claims

1. A replica/cache locator, comprising:

a coordinate determiner configured to determine network virtual coordinates between a first node in an overlay network and each remaining node in said overlay network;

a node clusterer coupled to said coordinate determiner and configured to calculate m clusters of nodes in said overlay network based on said network virtual coordinates; and

a replica/cache manager coupled to said node clusterer and configured to designate a node from said m clusters to include a replication table of said first node.

2. The replica/cache locator as recited in claim 1 wherein said coordinate determiner is configured to determine said network virtual coordinates by sending at least one request message from said first node to each of said remaining nodes.

3. The replica/cache locator as recited in claim 2 wherein said coordinate determiner is configured to send multiple request messages to determine said network virtual coordinates.

4. The replica/cache locator as recited in claim 1 wherein said replication table includes a copy of a content table of said first node and said content table is a sorted partition of domain data of said overlay network in a (key, value) pair form.

5. The replica/cache locator as recited in claim 1 wherein said replica/cache manager is configured to designate multiple nodes from said m clusters to include a replication table of said first node.

6. The replica/cache locator as recited in claim 1 wherein said replica/cache manager is further configured to designate nodes of said m clusters to include a cache of said first node.

7. The replica/cache locator as recited in claim 6 wherein said replica/cache manager is further configured to designate at least a single node in each of said m clusters to include said cache.

8. The replica/cache locator as recited in claim 1 wherein said replica/cache manager is configured to designate at most a single node in each of said m clusters to include said replication table.

9. A computer implemented method to locate replication tables in an overlay network having multiple nodes, comprising:

determining network virtual coordinates between a first node of said multiple nodes in said overlay network and each of said remaining multiple nodes;

calculating m clusters of said multiple nodes based on said network virtual coordinates; and

designating a node from said m clusters to include a replication table of said first node.

10. The method as recited in claim 9 wherein said designating includes designating no more than a single node in each of said m clusters to include said replication table.

11. The method as recited in claim 9 wherein said replication table includes a copy of a content table of said first node and said content table is a sorted partition of domain data of said overlay network in a (key, value) pair form.

12. The method as recited in claim 9 wherein said m clusters have an unequal amount of nodes.

13. The method as recited in claim 9 wherein each of said multiple nodes are coupled via said virtual coordinate system.

14. The method as recited in claim 9 further comprising designating at most a single node from anyone of said m clusters to include said replication table of said first node.

15. The method as recited in claim 9 wherein at least four nodes are designated to include said replication table.

16. The method as recited in claim 9 wherein said designating is based on reliability of components of said network.

17. The method as recited in claim 9 wherein said designating is based on availability requirement of said network.

18. An overlay network, comprising:

multiple nodes coupled in a ring, wherein at least a first node of said multiple nodes includes;

a content table having a sorted partition of domain data in a (key, value) pair form;

a flat routing table configured to associate an IP address of each of said multiple nodes with a corresponding range of keys; and

a replica/cache locator, including;

a coordinate determiner configured to determine network virtual coordinates between said first node and each remaining node of said multiple nodes;

a node clusterer coupled to said coordinate determiner and configured to calculate m clusters of said multiple nodes based on said network virtual coordinates; and

a replica/cache manager coupled to said node clusterer and configured to designate a node from said m clusters to include a replication table of said first node.

19. The overlay network as recited in claim 18, said first node further comprising an address database configured to include an IP address of k neighboring nodes proximate said node, k=1, . . . , n/2 wherein n=number of said multiple nodes.

20. The overlay network as recited in claim 18 wherein said node clusterer is further configured to calculate said m clusters based on dynamic information associated with some of said multiple nodes.

21. The overlay network as recited in claim 20 wherein one of said m clusters includes more nodes than at least another of said m clusters, said one including said some of said multiple nodes with said dynamic information.

22. A computer implemented method to locate caches in an overlay network having multiple nodes, comprising:

determining network virtual coordinates between a first node of said multiple nodes in said overlay network and each of said remaining multiple nodes; and

designating, based on said virtual coordinates, at least a single node of said multiple nodes to include a cache of said first node.

23. The method as recited in claim 22 further comprising calculating m clusters of said multiple nodes based on said network virtual coordinates and designating at least a single node in each of said m clusters to include said cache.

24. The method as recited in claim 23 further comprising designating multiple nodes in at least one of said m clusters to include said cache.