Browse Prior Art Database

An Algorithm For Negotiating Unique Names Among Networked Peers

IP.com Disclosure Number: IPCOM000201804D
Publication Date: 2010-Nov-23
Document File: 3 page(s) / 55K

Publishing Venue

The IP.com Prior Art Database

Abstract

The algorithm described in this invention applies to the network nodes which meet the following conditions. 1. The nodes are connected to each other on a reliable physical network which has a known communication latency. 2. There exists a method for any node to send a message to all the other nodes without identifying itself by any unique identifier. There are no other assumptions besides the above two conditions. Especially, there is no requirement to pre-load any unique identifier, hardware or software, on all the nodes involved. These two conditions implies that a practical implementation of this invention will likely be suitable for limited number of nodes directly connected on a local network instead of distributed across the internet.

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 40% of the total text.

Page 01 of 3

An Algorithm For Negotiating Unique Names Among Networked Peers

In a network system, it is essential that each network node has a unique identifier for itself to facilitate communication on the network. Typically, unique network identifiers are pre-allocated and assigned by some kind of centralized authorities. Internet protocol address and media access control address are examples of such predetermined unique identifier systems. In a practical operating environment, the unique identifiers are either manually configured on each node on the network or distributed by a special node which controls and distributes all the identifiers available. However, it is sometimes desirable for a group of network nodes to be able to come up with unique identifiers for all the nodes involved without resorting to any predetermined values and without making one particular node special relative to all other nodes. The goal is to make all the network nodes truly equal peers. Any node can leave or join the network in any order without interrupting the network operation and the negotiation must be autonomous, i.e. relying on only the networked nodes themselves without any outsider's help.

In order to achieve the above stated goal, there must be a protocol for the networked nodes to negotiate among themselves to agree upon a unique identifier for each node. The negotiation should not be too difficult when some of the nodes are already up and running, i.e. already have unique identifiers configured for themselves. The most difficult task is how to negotiate unique identifiers for each node when two or more nodes are starting together initially. A node is "starting initially" means that it does not know what its unique identifier is when it is powered up. This disclosure describes one algorithm by which negotiation among nodes starting initially together can be done to reliably achieve a unique identifier for each node involved.

The Algorithm

This algorithm is used for a group of two or more nodes to agree upon a unique identifier for each node when they are: 1) starting at the same time or at slightly different times with unspecified differentials; 2) all wanting to claim a unique identifier from a known pool of identifiers.

This algorithm makes the following assumptions. The first assumption is that there is a known

pool of identifiers to choose from. This assumption is theoretically not necessary by this

algorithm itself, but it will most likely be the case in a practical implementation. The second assumption is that the network which is connecting all the nodes involved has a well-characterized latency, Δ. This is a good assumption when all the nodes are connected on a local network. Again, this assumption is not absolutely necessary for the algorithm itself, but will make the discussion of the algorithm simpler. Another assumption is that the messaging system used supports sending and receiving messages on separate threads and there is no one-to-one...