US 8,526,331 B2 · Maintaining distributed hash tables in an overlay network

Abstract

A method of maintaining routing tables at nodes of an overlay network, where a routing table of a given node contains, for each of a set of neighboring successor and predecessor nodes, a mapping between an overlay network address of the node and a physical locator of the node. The method comprises, upon or immediately prior to departure of a node from the overlay network, sending a Leave request from the departing node (or one of the neighboring nodes of the departing node aware of the departure) to each neighboring node (or each other neighboring node of the departing node), indicating the departure and containing one or more mappings for nodes not contained within the routing table of the recipient node. Each neighboring node (or each other neighboring node) receives the Leave request and uses said mapping(s) to update its routing table.

Drawings

Drawings are temporarily unavailable. Open the PDF at USPTO

Drawings

Claims16

Dependent claims

A method of maintaining a plurality of routing tables at a respective plurality of nodes of a Distributed Hash Table (DHT) based overlay network, with each of the plurality of routing tables being maintained for a respective one of the nodes, the method comprising:

periodically exchanging DHT maintenance messages between the nodes of the DHT based overlay network to allow the nodes to learn of other nodes that have newly joined the DHT based overlay network, where a routing table of a given node contains, for each of a set of neighboring nodes including neighboring successor nodes and neighboring predecessor nodes, a mapping between an overlay network address of the neighboring node and a physical locator of the neighboring node;
upon or immediately prior to departure of a departing node from the DHT based overlay network, sending a Leave request from the departing node or one of the neighboring nodes of the departing node aware of the departure, to each neighboring recipient node or each other neighboring recipient node of the departing node, wherein the Leave request indicates the departure of the departing node and wherein the Leave request contains one or more mappings for nodes not contained within the routing table of at least one of the respective neighboring recipient nodes;
and
receiving the Leave request at each neighboring recipient node or at each other neighboring recipient node of the departing node and updating the respective routing table at the at least one of the neighboring recipient node using the one or more mappings contained in the Leave request.

1 more element

A method of maintaining a plurality of routing tables with each of the plurality of routing tables being maintained at a respective plurality of nodes of a Distributed Hash Table, (DHT) based overlay network, with each of the plurality of routing tables being maintained for a respective one of the nodes, comprising:

periodically exchanging DHT maintenance messages between the nodes of the DHT based overlay network to allow the nodes to learn of other nodes that have newly joined the DHT based overlay network, where a routing table of a given node contains, for each of a set of neighboring nodes including neighboring successor nodes and neighboring predecessor nodes, a mapping between an overlay network address of the neighboring node and a physical locator of the neighboring node;
upon departure of a departing node from the DHT based overlay network, sending a Leave request from one of the neighboring nodes of the departing node aware of the departure, to other neighboring nodes of the departing node, wherein the Leave request indicates the departure of the departing node and wherein the Leave request contains one or more mappings for nodes not contained within the routing table of at least one of the other neighboring nodes of the departing node receiving the Leave request;
and
receiving the Leave request at said each of the other neighboring nodes of the departing node and updating the routing table of at least one of the other neighboring nodes of the departing node using the one or more mappings contained in the Leave request.

1 more element

A node for use within a Distributed Hash Table (DHT) based overlay network comprising:

a memory for storing a routing table containing, for each of a set of neighboring nodes including neighboring successor nodes and neighboring predecessor nodes, a mapping between an overlay network address of the neighboring node and a physical locator of the neighboring node;
a processing unit configured to periodically exchange DHT maintenance messages with other nodes of the DHT based overlay network to allow the node to learn of other nodes that have newly joined the DHT based overlay network, and to send a Leave request to one or more of the recipient neighboring nodes of the node upon departure of the node or upon departure of a neighboring node from the DHT based overlay network, wherein the Leave request indicates the departure of the departing node and wherein the Leave request contains one or more overlay network address to physical locator mappings for nodes not contained within the routing table of at least one of the recipient neighboring nodes.

Dependencies are inferred from the claim text.

Description5,412 words

Summary2,822 words

#This application is a 35 U.S.C. §371 national stage application of PCT International Application No. PCT/EP2008/056376, filed on 23 May 2008, the disclosure and content of which is incorporated by reference herein in its entirety. The above-referenced PCT International Application was published in the English language as International Publication No. WO 2009/141013 A1 on Nov. 26, 2009.

#The present invention relates to a mechanism for maintaining distributed hash tables in an overlay network. The invention is applicable in particular to an optimised procedure for handling the leaving of a node from an overlay network

#Peer-to-peer or P2P networks make use of the pooled resources of participating nodes including processing capabilities and communication bandwidth to facilitate a wide variety of services including file sharing and VoIP telephony. In the absence of central servers, particular P2P services may make use of “overlay networks” to optimise resource location. An overlay network comprises nodes connected by virtual links representing paths extending across possibly many physical links in the underlying network (e.g. the Internet). Each node in the overlay network maintains a routing table containing a set of links to certain other nodes within the overlay network. Resource requests are passed between nodes until they arrive at a node which is responsible for that resource.

Brief description of the drawings5 figures

#FIG. 1 illustrates schematically a DHT-based ring overlay network comprising a number of nodes;

#FIG. 2 further illustrates a DHT-based ring overlay network, showing neighbourhood relations between nodes;

#FIG. 3 illustrates schematically a node of the overlay network of FIG. 2;

Detailed description2,499 words

#The optimized DHT leave operation described here relies upon a node assisting a neighbouring node to quickly update its routing tables in the event that the neighbouring node's routing table is affected by the departure of a node from the network. The departing node may be the neighbouring node, i.e. in the graceful departure scenario, or another neighbouring node in the case of an ungraceful departure. These two scenarios will now be considered in detail.

#Reference is made again to FIG. 2 which shows an example of a Chord DHT-based overlay network using a ring topology. Whilst Chord DHT is used here by way of example, the procedures described are equally applicable to other DHT-based overlay networks. In the example illustrated, it is assumed that each node in the DHT-based overlay network maintains pointers to six neighbours: namely three predecessor nodes and three successor nodes. Of course, the proposed mechanism works with any number of successor and predecessor pointers.

#In FIG. 2, a Node X has three successors: S1, S2, and S3. If the overlay network is experiencing heavy “churn”, all of the successors of Node X might choose to leave the overlay network within a short time frame. Assuming that the nodes depart gracefully, they will send Leave requests to their neighbours. However, as described above, Node X may not have time to identify any other successor nodes before all three successors have left the network. In order to avoid a partitioning of the network in this scenario, each node that intends to leave the overlay helps its neighbours to fill their routing tables with alternative neighbour nodes, before actually leaving the network.

Facts

Application

12/993,990Filed 23 May 2008

Published

US 2011/0110269 A112 May 2011

Granted

3 Sep 2013

Term ends

3 Jan 2029

Estimated · how

20 years from earliest known nonprovisional domestic filing plus recorded patent term adjustment, including 225 days of adjustment. Maintenance-fee lapses, terminal disclaimers and statutory extensions have not been checked. The continuity chain may be incomplete; this is not an enforceability determination.

Classification4 codes

H04L 67/104
In which an application is distributed across nodes in the network: peer-to-peer [P2P] networks
H04L 67/1048
Group management mechanisms: departure or maintenance mechanisms
H04L 67/1065
Using node-based peer discovery mechanisms: discovery involving distributed pre-established resource-based relationships among peers, e.g. based…
H04L
Digital communication

Timeline

23 May 2008Application filedUS 12/993,990
22 Nov 2010Assigned to Telefonaktiebolaget Lm Ericsson (Publ)assignment of assignor's interest
12 May 2011PublishedUS 2011/0110269 A1
3 Sep 2013GrantedUS 8,526,331 B2
12 Oct 2026TodayWithin its term
3 Jan 2029Term endsEstimated, includes 225 days of adjustment

Maintaining distributed hash tables in an overlay network

Life of this patent

Maintaining distributed hash tables in an overlay network

Life of this patent

Life of this patent

Abstract

Drawings

Drawings

Claims16

Description5,412 words

Drawings

Classification4 codes

Life of this patent

Description5,412 words