Overlay network system which constructs and maintains an overlay network
First Claim
Patent Images
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.
5 Assignments
0 Petitions
Accused Products
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.
-
Citations
19 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. - View Dependent Claims (2, 3, 4, 5, 6, 7, 8, 9, 10)
-
-
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. - View Dependent Claims (12, 13, 14, 15, 16, 17)
-
-
18. A Non-transistory 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. - View Dependent Claims (19)
-
Specification