Patent ID: 8526331

Claim:
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.