Network location management system

• US 7,586,853 B2
• Filed: 10/11/2002
• Issued: 09/08/2009
• Est. Priority Date: 10/17/2001
• Status: Active Grant

• Current Assignee: British Telecommunications PLC (BT Group PLC)
• Original Assignee: British Telecommunications PLC (BT Group PLC)
• Inventors: Bonsma, Erwin R., Hoile, Cefn R.
• Primary Examiner(s): Kizou; Hassan
• Assistant Examiner(s): Moutaouakil; Mounir
• Application Number:
  US10/491,086
• Publication Number:
  US 20040246911A1
• Time in Patent Office: 2,524 Days
• Field of Search: 370/254, 370/255, 370/256, 370/257, 370/258, 370/355, 370/356, 370/357, 370/397, 370/399, 370/395.3, 370/395.32
• US Class Current: 370/254
• CPC Class Codes: H04L 45/44 Distributed routing
• CPC Class Codes: H04L 61/00 Network arrangements, protocols or services for addressing or naming
• CPC Class Codes: H04L 67/104 Peer-to-peer [P2P] networks
• CPC Class Codes: H04L 67/1046 Joining mechanisms
• CPC Class Codes: H04L 67/1048 Departure or maintenance mechanisms
• CPC Class Codes: H04L 67/1068 Discovery involving direct consultation or announcement among potential requesting and potential source peers
• CPC Class Codes: H04L 67/1072 Discovery involving ranked list compilation of candidate peers
• CPC Class Codes: H04L 69/329 in the application layer [OSI layer 7]
• CPC Class Codes: H04W 64/00 Locating users or terminals or network equipment for network management purposes, e.g. mobility management
• CPC Class Codes: H04W 8/26 Network addressing or numbering for mobility support

Abstract

In a communications network environment, nodes, such as personal computers, are assigned co-ordinates in a co-ordinate space which is independent of network address and physical location. Each node maintains links to a limited set of other nodes by storing the network addresses for those selected nodes. Each stored network address represents a link in co-ordinate space. It becomes possible for any node to obtain the network address for a target node by initiating a query message to a node for which it has the network address, which query message is propagated through the network between nodes which have the network address for a next node across co-ordinate space. When a receiving node finds it is the target node, or is as close in co-ordinate space as it is possible to forward the query message, it returns its own network address to the initiating node. This technique can also be used to retrieve information other than network addresses—such as objects.

Claims

1. Apparatus for use in retrieving information relating to a node in a network, wherein the network includes a plurality of nodes and communications links therebetween, the apparatus comprising:

receiving means arranged to receive, on behalf of a node, a request in respect of information relating to a target node including a request for a network address of the target node, the request including an identifier indicative of location of the target node in a virtual space, wherein the location is independent of physical location and network address;

sending means arranged to send, on behalf of said node, a request in respect of said target node, onward to another node;

storage arranged to store data in respect of a plurality of nodes, the data including, for each such node, an identifier indicative of location of the node and a network address corresponding thereto in said virtual space, wherein the location is independent of physical location and network address;

evaluating means arranged to evaluate distance between the locations of two nodes in said virtual space;

the apparatus being arranged, upon receipt of such a request, to translate the target node'"'"'s ID into coordinates in virtual space and to evaluate the distance between the locations of each of a plurality of evaluated nodes and the target location, at least one of said plurality of evaluated nodes being the receiving node, and to identify which of the plurality of evaluated nodes are closer to the target node than the receiving, node is to the target node in said virtual space, and

wherein the sending means sends the request to one of the identified nodes.

2. Apparatus according to claim 1, wherein the sending means is arranged to select a node from identified nodes in dependence on either or both of (a) degree of proximity to the target node in said virtual space or/and (b) transmission characteristics between the receiving node and the identified node.

3. Apparatus according to claim 1, including transforming means arranged to transform an identifier into a location in said virtual space, wherein, in use, the transforming means transforms the identifier corresponding to the target node to a target location.

4. Apparatus according to claim 1, wherein:

the receiving means is arranged to identify the node from which the request message originated, and

the sending means is arranged to send a response message to the originating node in the event that none of the identified nodes are closer to the target node in said virtual space than the receiving node is to the target node, the response message including the requested information relating to the receiving node.

5. Apparatus according to claim 1, wherein the data stored in the storage includes an inter-node distance and, for at least some of the plurality of nodes, distance values associated therewith, and the apparatus includes:

quantifying means arranged to estimate the distribution of locations of nodes in the network, and to quantify the same as the inter-node distance;

modifying means arranged to modify a distance value associated with one of the plurality of nodes in accordance with an exponential expression involving the inter-node distance;

the apparatus being arranged, in use, such that the quantifying means estimates and quantifies inter-node distance, and, for at least one of the stored plurality of nodes, the modifying means modifies the distance value corresponding thereto in dependence on a selective modification criterion.

6. Apparatus according to claim 5, wherein the selective modification criterion involves a stochastic value dependent on successively quantified inter-node distances.

7. Apparatus according to claim 5, including:

creating means arranged to create an identifier for a target node such that the location of the target node is separated from the location of the receiving node by the modified distance value and wherein in use;

the creating means creates an identifier for a target node whose location is separated from the location of the receiving node by the modified distance value, and

the sending means sends a request in respect of said target node.

8. Apparatus according to claim 5, wherein:

the distribution estimated by the quantifying means is dependent on the locations of at least some of the plurality of nodes in the storage that do not have distance values associated therewith.

9. Apparatus according to claim 1, wherein:

the storage is arranged to update the stored data in response to input from the evaluating means, and

the receiving means is arranged to identify e type of message received by a node;

the apparatus being arranged, in receipt of a message, such that the receiving means identifies the type, and originating location, of the received message, and, if the message is identified as being a message requiring action, the evaluating means (a) evaluates the distance between the locations of each of a plurality of nodes and that of the originating node, at least one of the evaluated plurality being the said node, (U) identifies which of the plurality of nodes is closest to the originating node, and, (c) if the identified node is the said node, the storage adds data items in respect of the originating node.

10. Apparatus according to claim 9, wherein data items in respect of one of the plurality of nodes are replaced with the data items in respect of the originating node.

11. Apparatus according to claim 1, wherein

the request in respect of information relating to a target node includes a request for data from the target node.

12. A network management system including:

a plurality of nodes and communications links therebetween, wherein each node of the plurality has apparatus according to claim 1.

13. A system according to claim 12, wherein the nodes are representative of computers, databases, files, mobile software agents, service providers and/or data items accessible via the network.

14. Network management apparatus, wherein:

the network includes a plurality of nodes and communications links therebetween,

each node is arranged to send a message through the network, the message including an identifier indicative of the location in virtual space of the node from which the message originated, and

the location in said virtual space is independent of physical location and network address,

the apparatus comprising;

receiving means arranged to identify the type of message received by a node including a request for a network address of a target node;

storage arranged to store data in respect of a plurality of nodes, the data including, for each such node, an identifier indicative of location of the node in said virtual space and a network address corresponding thereto, wherein the location in said virtual space is independent of physical location and network address;

evaluating means arranged to evaluate distance between locations of two nodes in virtual space;

the apparatus being arranged, in receipt of a message, such that the receiving means identifies the type of message, and, if the message is identified as being a message requiring action, the evaluating means translates the target node'"'"'s ID into coordinates in virtual space and evaluates the distance between the locations of each of a plurality of evaluated nodes in virtual space and that of the originating node and identifies which of the plurality of nodes is closest to the originating node in virtual space,

wherein the plurality of evaluated nodes includes the receiving node, and, if the identified node is the receiving node, data items in respect of the originating node are added to the storage.

15. Apparatus according to claim 14, including:

transforming means arranged to transform an identifier into a location in said virtual space, wherein the location is independent of both physical location and network address of the associated node, and

wherein the transforming means transforms an identifier corresponding to the originating node to an originating location in virtual space.

16. Apparatus according to claim 14, includes

sending means arranged to send a message to another node,

wherein the sending means sends the message to the identified node in the event that the identified node is not the receiving node.

17. Apparatus according to claim 14, wherein:

if the message is identified as being an onward transmission type of message, the sending means is arranged to review the lifetime of the message, and,

in the event that the lifetime has not expired, the sending means is arranged to send the message to another node.

18. Apparatus according to claim 14, including:

generating means for generating messages requiring action, the generating means being operable to receive input from the sending means in the event that the lifetime of an onward transmission type of message is deemed to have expired, and to generate a message requiring action in response to the input.

19. Apparatus according to claim 18, wherein the sending means is arranged to send the message requiring action to another node.

20. Apparatus according to claim 19, wherein the sending means is arranged to select one of the plurality of nodes stored in the storage, so that the other node to which the message is sent is one of said plurality.

21. Apparatus according to claim 14, wherein data items in respect of one of the plurality of nodes are replaced with the data items in respect of the originating node.

22. A network management system including:

a plurality of nodes and communications links therebetween, wherein each node of the plurality comprises apparatus according to claim 14.

23. A method of retrieving information relating to a node in a network, the network including a plurality of nodes and communications links therebetween, the method comprising:

sending a request from a first node in respect of information relating to a target node including a request for a network address of the target node, the request including an identifier indicative of the location of the target node in a virtual space, wherein the location is independent of physical location and network address;

receiving the request at a second node;

accessing data at the second node in respect of a plurality of nodes, the data including, for each such node, an identifier indicative of location of the node in said virtual space and a network address corresponding thereto, wherein the location is independent of physical location and network address;

translating at the second node the target node'"'"'s ID into coordinates in virtual space and evaluating at the second node the distance in said virtual space between the locations of each of a plurality of nodes and the target location, at least one of the plurality being the second node,

identifying at said second node which of the plurality of nodes are closer to the target node than the second node is to the target node in said virtual space; and

sending from the second node the request to one of the identified nodes.

24. A method according to claim 23, in which the second node selects a node from the identified nodes in dependence on either or both of degree of proximity to the target node or/and transmission characteristics between the second node and the identified node.

25. A method according to claim 23, including

transforming the identifier of the target node into a target location.

26. A method according to claim 23, in which the accessed data includes an inter-node distance and, for at least some of the plurality of nodes, distance values associated therewith, the method including:

quantifying the distribution of nodes in the network as an inter-node distance in said virtual space; and

modifying a distance value associated with one of the plurality of nodes in accordance with an exponential expression involving the inter-node minimum distance.

27. A method according to claim 26, including creating an identifier for a target node such that the location of the target node is separated from the location of the receiving node by the modified distance value, and sending a request in respect of said target node.

28. A method according to claim 23 in which the second node:

identifies the type of message, and, if the message is identified as being a message requiring action,

evaluates the distance between the locations of each of a plurality of nodes and that of the originating node, at least one of the evaluated plurality being the said node,

identifies which of the plurality of nodes is closest to the originating node, and, if the identified node is the said node, storing data items in respect of the originating node.

29. A method according to claim 23, wherein the request in respect of information relating to a target node includes a request for data from the target node.

30. A network management method, the network including a plurality of nodes and communications links therebetween, the method comprising:

identifying the type of message received by a node including a request for a network address of a target node and, if the message is identified as being a message requiring action, identifying, from the received message, an identifier indicative of the location of the node in a virtual space from which the received message originated, wherein the location is independent of physical location and network address;

accessing data in respect of a plurality of nodes, the data including, for each such node, an identifier indicative of location of the node in said virtual space and a network address corresponding thereto, wherein the location in virtual space is independent of physical location and network address;

translating the target node'"'"'s ID into coordinates in virtual space and evaluating the distance between the locations in said virtual space of each of a plurality of nodes and that of the originating node, the plurality including the receiving node and the said plurality of nodes,

identifying which of the evaluated plurality of nodes is closest in said virtual space to the originating node, and, if the identified node is the receiving node, storing data items in respect of the originating node.

31. A method according to claim 30, including transforming the identifier corresponding to the originating node to an originating location.

32. A method according to claim 30, including sending a message to the identified node in the event that the identified node is not the receiving node.

33. A method according to claim 30, in which, if the message is identified as being an onward transmission type of message, the method includes reviewing the lifetime of the message, and, in the event that the lifetime has not expired, sending the message to another node.

34. A method according to claim 33, including generating a message requiring action in the event that the lifetime of an onward transmission type of message is deemed to have expired.

35. A method according to claim 34, including sending the message requiring action to another node.

36. A method according to claim 35, including selecting data in respect of one of the accessible plurality of nodes, so that the other node to which the message is sent is one of the said plurality.

37. A computer program product embodied on a computer readable medium, the program product comprising a set of instructions to cause a computer, or a suite of computers, to:

a) receive a request at a node in respect of information relating to a target node, the request including an identifier indicative of the location of the target node in a virtual space, wherein the location is independent of physical location and network address;

access data in respect of a plurality of nodes, the data including, for each such node, an identifier indicative of location of the node in said virtual space and a network address corresponding thereto, wherein the location is independent of physical location and network address;

translating the target node'"'"'s ID into coordinates in virtual space and evaluating the distance in said virtual space between the locations of each of a plurality of nodes and the target location, at least one of the plurality being the receiving node, identifying which of the plurality of nodes is closest to the target node, and, if the identified node is a node other than the receiving node, the receiving node sending the request to the identified node; and

/or

b) identify the type of message received by a node and, if the message is identified as being a message requiring action, identifying, from the received message, an identifier indicative of the location of the node in said virtual space from which the received message originated, wherein the location is independent of physical location and network address;

accessing data in respect of a plurality of nodes, the data including, for each such node, an identifier indicative of location in virtual space of the node and a network address corresponding thereto, wherein the location is independent of physical location and network address;

evaluate the distance in virtual space between the locations of each of a plurality of nodes and that of the originating node, the plurality including the receiving node and the said plurality of nodes, identifying which of the evaluated plurality of nodes is closest to the originating node, if the identified node is the receiving node, storing data items in respect of the originating node, if the identified node is not the receiving node, sending the message to the identified node; and

/or

c) identify the type of message received by a node and, if the message is identified as being an onward transmission type of message, reviewing the lifetime of the message, and, in the event that the lifetime has not expired, sending the message to another node.