OVERLAY NETWORK SYSTEM WHICH CONSTRUCTS AND MAINTAINS AN OVERLAY NETWORK

• US 20090154476A1
• Filed: 12/11/2008
• Published: 06/18/2009
• Est. Priority Date: 12/13/2007
• Status: Active Grant

• Current Assignee: Toshiba Solutions Corporation (Toshiba Corporation)
• Original Assignee: Kabushiki Kaisha Toshiba (Toshiba Corporation), Toshiba Solutions Corporation (Toshiba Corporation)
• Inventors: Kobara, Makoto
• Granted Patent: US 7,773,609 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• CPC Class Codes: H04L 2101/604 Address structures or formats
• CPC Class Codes: H04L 41/044 comprising hierarchical management structures
• CPC Class Codes: H04L 41/08 Configuration management of networks or network elements address allocation H04L61/50
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/17 Shortcut routing, e.g. using next hop resolution protocol [NHRP]
• CPC Class Codes: H04L 45/54 Organization of routing tables
• CPC Class Codes: H04L 61/5038 for local use, e.g. in LAN or USB networks, or in a controller area network [CAN]

Abstract

An overlay network system comprises an overlay network composed of a plurality of nodes and a plurality of sub-overlay networks each of which is composed of a subset of the plurality of nodes and which are hierarchized. The overlay network is managed as a 0th-level sub-overlay network at the highest hierarchical level. Each of the plurality of sub-overlay networks is allocated a sub-overlay network ID whose number of bits corresponds to the hierarchical level of the network. The high-order one or more bits in the sub-overlay network ID also indicate the sub-overlay network ID of a sub-overlay network at the high hierarchical level corresponding to the number of the one or more bits.

Claims

1. An overlay network system comprising:

an overlay network composed of a plurality of nodes;

a plurality of sub-overlay networks each of which is composed of a subset of said plurality of nodes and which are hierarchized, the plurality of sub-overlay networks being included in a hierarchical structure where the overlay network is a 0th-level sub-overlay network at the highest hierarchical level, each of the plurality of sub-overlay networks being allocated a sub-overlay network ID for identifying said each of the plurality of sub-overlay networks, the number of bits in the sub-overlay network ID corresponding to the hierarchical level of a sub-overlay network to which the sub-overlay network ID is allocated, the high-order one or more bits in the sub-overlay network ID also indicating the sub-overlay network ID of a sub-overlay network whose hierarchical level not only is higher than that of the sub-overlay network allocated the sub-overlay network ID but also corresponds to the number of the one or more bits,

wherein each of the plurality of nodes includes;

a configuration storage unit configured to store an adjacent table, the adjacent table holding IDs and addresses of one or more nodes for each of the hierarchical levels of the sub-overlay networks ranging from a mask-level sub-overlay network to the 0th-level sub-overlay network in the hierarchical structure, the one or more nodes adjoining said each of the plurality of nodes when the IDs of all the nodes included in a sub-overlay network at a corresponding hierarchical level are arranged in a ring in order of magnitude of the IDs, and the mask-level sub-overlay network being the deepest-hierarchical-level one of the plurality of sub-overlay networks which includes said each of the plurality of nodes;

a management module which is configured to manage the ID of said each of the plurality of nodes using the adjacent table and which is further configured to manage not only the ID of said each of the plurality of nodes as an ID composed of the sub-overlay network ID of the mask-level sub-overlay network and node ID of said each of the plurality of nodes but also the sub-overlay network ID of the mask-level sub-overlay network as the sub-overlay network ID of a sub-overlay network in which said each of the plurality of nodes participates, and the node ID of said each of the plurality of nodes being distinguishable from node IDs of other nodes included in the mask-level sub-overlay network; and

a routing module which is configured to perform routing for a first node to obtain an address of a second node and which is further configured to obtain the address of the second node on the basis of information in the adjacent table corresponding to the hierarchical level of a sub-overlay network in which the second node participates or a sub-overlay network including the sub-overlay network in which the second node participates by referring to the adjacent table possessed by the first node, using the ID of the second node as an input, the first node being said each of the plurality of nodes, and the second node being an arbitrary one of the plurality of nodes.

2. The overlay network system according to claim 1, wherein the routing module is configured to use an address of a node adjacent to the first node held in the adjacent table when having failed to obtain the address of the second node, thereby requesting the adjacent node to obtain the address of the second node.

3. The overlay network system according to claim 2, wherein:

the ID of each of the plurality of nodes has a length of M bits and is unique in the entire overlay network, the high-order “

mask”

bits in the ID indicating the sub-overlay network ID of the mask-level sub-overlay network in which said each of the plurality of nodes participates, and the low-order “

M-mask”

bits in the ID indicating the node ID of said each of the plurality of nodes distinguishable from node IDs of other nodes included in the mask-level sub-overlay network; and

the management module of the first node is configured to manage the sub-overlay network ID of the mask-level sub-overlay network in which the first node participates on the basis of the ID of the first node and the number of mask bits “

mask”

.

4. The overlay network system according to claim 3, wherein the routing module is configured to select and use information in the adjacent table corresponding to a second sub-overlay network to obtain the address of the second node, the second sub-overlay network being the deepest-hierarchical-level one of the sub-overlay networks common to a sub-overlay network in which the second node participates and the sub-overlay network including the sub-overlay network in which the second node participates and to a first sub-overlay network and a sub-overlay network including the first sub-overlay network, and the first sub-overlay network being the mask-level sub-overlay network in which the first node participates.

5. The overlay network system according to claim 4, wherein the routing module is configured to count the maximum number of bits k through which the sub-overlay network ID indicated by the ID of the second node coincides with the sub-overlay network ID indicated by the ID of the first node consecutively from the highest-order bit and determines a kth-level sub-overlay network indicated by the counted maximum number of bits k to be the second sub-overlay network.

6. The overlay network system according to claim 1, wherein:

the configuration storage unit is configured to store a skip table which holds the IDs and addresses of a plurality of skip nodes for said each of the plurality of nodes, the plurality of skip nodes being arbitrary ones of the plurality of nodes and including a node not adjoining said each of the plurality of nodes when the IDs of the plurality of nodes are arranged in a ring in order of magnitude of the IDs; and

the routing module is configured to refer to the skip table at the time of routing to obtain the address of the second node and obtain the address of the second node on the basis of information in the skip table and, if having failed to obtain the address of the second node, use one of the addresses of the plurality of skip nodes held in the skip table and request a skip node indicated by the one of the addresses to obtain the address of the second node.

7. The overlay network system according to claim 6, wherein the plurality of skip nodes include other nodes participating in the mask-level sub-overlay network in which a node with the skip table holding the IDs and addresses of the plurality of skip nodes participates.

8. The overlay network system according to claim 7, wherein the plurality of skip nodes also include other nodes included in a sub-overlay network including the mask-level sub-overlay network in which a node with the skip table holding the IDs and addresses of the plurality of skip nodes participates.

9. The overlay network system according to claim 8, wherein the routing module is configured to select information in the skip table corresponding to a second sub-overlay network when having failed to obtain the address of the second node and use the selected information in the skip table to determine a skip node which is requested to obtain the address of the second node, the second sub-overlay network being the deepest-hierarchical-level one of the sub-overlay networks common to a sub-overlay network in which the second node participates and a sub-overlay network including the sub-overlay network in which the second node participates and to a first sub-overlay network and a sub-overlay network including the first sub-overlay network, and the first sub-overlay network being the mask-level sub-overlay network in which the first node participates.

10. The overlay network system according to claim 1, wherein said each of the plurality of nodes further includes:

an object storage unit for storing a plurality of objects; and

an object storing module configured to store an arbitrary object into the object storage unit of any one of the plurality of nodes,

wherein each of the plurality objects is allocated a unique ID composed of an object ID used to determine a storage location node and an object sub-ID for identifying the object in the storage location node, the storage location node being a node in which each of the plurality of objects is to be stored, and the object ID being composed of a sub-overlay network ID specifying a sub-overlay network in which the storage location node participates and a node ID specifying the storage location node, and

in the process of storing an arbitrary object, the object storing module is configured to cause the routing module to search for a node whose node ID is closest to the node ID in the object ID of the arbitrary object when the node IDs of all the nodes participating in a sub-overlay network whose sub-overlay network ID is the same as the sub-overlay network ID in the object ID of the arbitrary object are arranged in a ring in order of magnitude of the IDs, and store the arbitrary object into the node searched for.

11. A method of constructing and maintaining an overlay network in an overlay network system, the overlay network system including an overlay network composed of a plurality of nodes and a plurality of sub-overlay networks, the plurality of sub-overlay networks being hierarchized, the plurality of sub-overlay networks being included in a hierarchical structure where the overlay network is a 0th-level sub-overlay network at the highest hierarchical level, each of the plurality of sub-overlay networks being allocated a sub-overlay network ID for identifying said each of the plurality of sub-overlay networks, the number of bits in the sub-overlay network ID corresponding to the hierarchical level of a sub-overlay network to which the sub-overlay network ID is allocated, the high-order one or more bits in the sub-overlay network ID also indicating the sub-overlay network ID of a sub-overlay network whose hierarchical level not only is higher than that of the sub-overlay network allocated the sub-overlay network ID but also corresponds to the number of the one or more bits, the method comprising:

inquiring, by a first node, a node adjacent to the first node from a second node, the first node being a new node participating in a mask-level one of the plurality of sub-overlay networks, and the second node being an arbitrary one of the plurality of nodes;

in response to the inquiry made by the first node, determining whether the second node adjoins the first node for each of the hierarchical levels of the sub-overlay networks ranging from the mask-level sub-overlay network to the 0th-level sub-overlay network, the determining including referring to a second adjacent table stored in a configuration storage unit possessed by the second node, the second adjacent table holding the IDs and addresses of one or more nodes for each of the hierarchical levels of the sub-overlay networks ranging from a sub-overlay network in which the second node participates to the 0th-level sub-overlay network, if the deepest-hierarchical-level sub-overlay network including the second node in the hierarchical structure is a sub-overlay network in which the second node participates, and the one and more nodes adjoining the second node when the IDs of all the nodes included in the sub-overlay network of the corresponding hierarchical level are arranged in order of magnitude of the IDs;

updating, by the second node, information in a first adjacent table and information in the second adjacent table each corresponding to the hierarchical level at which the second node is determined to be adjacent to the first node, the first adjacent table being stored in a configuration storage unit possessed by the first node and having a structure corresponding to the second adjacent table;

after the determining and the updating, transferring, by the second node, the inquiry made by the first node to a node adjacent to the second node on the 0th-level sub-overlay network; and

when a third node has to obtain an address of a fourth node, executing, by the third node, routing to obtain the address of the fourth node on the basis of information in a third adjacent table, the third node being an arbitrary one of the plurality of nodes, the fourth node being another arbitrary one of the plurality of nodes, the executing including referring to the third adjacent table, using the ID of the fourth node as an input, the third adjacent table being stored in a configuration storage unit possessed by the third node and having a structure corresponding to the first adjacent table, information in the third adjacent table corresponding to the hierarchical level of a sub-overlay network in which the fourth node participates or a sub-overlay network including a sub-overlay network in which the fourth node participates, the ID of the fourth node being composed of the sub-overlay network ID of a sub-overlay network in which the fourth node participates and node ID of the fourth node, and the node ID of the fourth node being distinguishable from node IDs of other nodes included in a sub-overlay network in which the fourth node participates.

12. The method according to claim 11, further comprising using an address of a node adjacent to the third node held in the third adjacent table when having failed to obtain the address of the fourth node, thereby requiring, by the third node, a node adjacent to the third node to obtain the address of the fourth node.

13. The method according to claim 12, wherein:

the ID of each of the plurality of nodes has a length of M bits and is unique in the entire overlay network, the high-order “

mask”

bits in the ID indicating the sub-overlay network ID of the mask-level sub-overlay network in which said each of the plurality of nodes participates, and the low-order “

M-mask”

bits in the ID indicating the node ID of said each of the plurality of nodes distinguishable from node IDs of other nodes included in the mask-level sub-overlay network; and

the first node manages the sub-overlay network ID of the mask-level sub-overlay network in which the first node participates on the basis of the ID of the first node and the number of mask bits “

mask”

.

14. The method according to claim 13, wherein the information in the third adjacent table corresponds to the deepest-hierarchical-level one of the sub-overlay networks common to a sub-overlay network in which the fourth node participates and a sub-overlay network including the sub-overlay network in which the fourth node participates and to a sub-overlay network in which the third node participates and a sub-overlay network including the sub-overlay network in which the third sub-overlay network participates.

15. The method according to claim 14, wherein the executing includes counting the maximum number of bits k through which the sub-overlay network ID indicated by the ID of the fourth node coincides with the sub-overlay network ID indicated by the ID of the third node consecutively from the highest-order bit, and

selecting a kth-level sub-overlay network indicated by the counted maximum number of bits k as the deepest-hierarchical-level one of the common sub-overlay networks.

16. The method according to claim 11, wherein the executing includes obtaining the address of the fourth node on the basis of information in a skip table holding the IDs and addresses of a plurality of skip nodes for the third node, the skip table being stored in the configuration storage unit possessed by the third node, the plurality of skip nodes being arbitrary ones of the plurality of nodes and including a node not adjoining the third node when the IDs of the plurality of nodes are arranged in a ring in order of magnitude of the IDs.

17. The method according to claim 16, wherein the executing includes using one of the addresses of the plurality of skip nodes held in the skip table when having failed to obtain the address of the fourth node, thereby requiring, by the third node, a skip node indicated by one of the addresses to obtain the address of the fourth node.

18. A computer-readable storage medium storing a computer program product which implements a method of constructing and maintaining an overlay network in an overlay network system, the overlay network system including an overlay network composed of a plurality of nodes including a first node and a plurality of sub-overlay networks, the plurality of sub-overlay networks being hierarchized, each of the plurality of sub-overlay networks included in a hierarchical structure where the overlay network is a 0th-level sub-overlay network at the highest hierarchical level being allocated a sub-overlay network ID for identifying said each of the plurality of sub-overlay networks, the number of bits in the sub-overlay network ID corresponding to the hierarchical level of a sub-overlay network to which the sub-overlay network ID is allocated, the high-order one or more bits in the sub-overlay network ID also indicating the sub-overlay network ID of a sub-overlay network whose hierarchical level not only is higher than that of the sub-overlay network allocated the sub-overlay network ID but also corresponds to the one or more bits, the computer-readable storage medium being used in a storage device possessed by the first node, the method comprising:

when a second node inquires a node adjacent to the second node from the first node, determining by the first node whether the second node adjoins the first node for each of the hierarchical levels of the sub-overlay networks ranging from a mask-level sub-overlay network to the 0th-level sub-overlay network, the second node being a new node participating in the mask-level one of the plurality of sub-overlay networks, the determining including referring, by the first node, to a first adjacent table stored in a configuration storage unit possessed by the first node, the first adjacent table holding the IDs and addresses of a node adjacent to the first node when the IDs of all the nodes included in the sub-overlay network at the corresponding level are arranged in a ring in order of magnitude of the IDs for each of the hierarchical levels of the sub-overlay networks ranging from a sub-overlay network in which the first node participates to the 0th-level sub-overlay network, if the deepest-hierarchical-level sub-overlay network including the first node in the hierarchical structure is a sub-overlay network in which the first node participates;

updating, by the first node, information in the first adjacent table and information in a second adjacent table each corresponding to the hierarchical level at which the first node is determined to be adjacent to the second node, the second adjacent table being stored in a configuration storage unit possessed by the second node and having a structure corresponding to the first adjacent table;

after the determining and the updating, transferring, by the second node, the inquiry made by the first node to a third node, the third node being a node adjacent to the first node on the 0th-level sub-overlay network; and

when the first node has to obtain an address of a fourth node, executing, by the first node, routing to obtain the address of the fourth node on the basis of information in the first adjacent table, the fourth node being an arbitrary one of the plurality of nodes, the executing including referring, by the first node, to the first adjacent table, using the ID of the fourth node as an input, information in the first adjacent table corresponding to the hierarchical level of a sub-overlay network in which the fourth node participates or a sub-overlay network including the sub-overlay network in which the fourth node participates, the ID of the fourth node being composed of the sub-overlay network ID of a sub-overlay network in which the fourth node participates and node ID of the fourth node, and the node ID of the fourth node being distinguishable from node IDs of other nodes included in a sub-overlay network in which the fourth node participates.

19. The computer-readable storage medium according to claim 18, wherein the method further comprising using an address of a node adjacent to the first node held in the first adjacent table when having failed to obtain the address of the fourth node, thereby requiring, by the first node, the node adjacent to the first node to obtain the address of the fourth node.