JP2010273277A - Node device and program for the same - Google Patents

Abstract

<P>PROBLEM TO BE SOLVED: To calculate physical vicinity between node devices based on given group information or proximity information of each node device, regardless of presence/absence of an IP (Internet Protocol) address, in an overlay network. <P>SOLUTION: A node-specific bit string transmission section 13 transmits a node-specific bit string of a present node device generated by a node-specific bit string generation section 11 in accordance with a proximate node list stored in a proximate node list generation and storage section 12. On the basis of a node-specific bit string of a proximate node device received by a node-specific bit string receiving section 14 and stored in a node-specific bit string storage section 15, a proximate node bit string generation section 16 generates a proximate node bit string by degenerating information on the proximate node device. In accordance with the proximate node bit string received from the other node device and the proximate node bit string of the present node device, a proximate node bit string comparing section 19 calculates an inter-bit distance (namely, physical vicinity). <P>COPYRIGHT: (C)2011,JPO&INPIT

Description

  The present invention relates to a node device in an overlay network and a program for a node device for operating a computer as a node device, and more particularly to a technique for detecting proximity between node devices.

  An overlay network is another logical (virtual) computer network constructed according to the purpose in an upper layer using an existing physical computer network such as the Internet. Node devices (computers) on the overlay network can communicate without being aware of the topology of the lower network.

  A typical example of an overlay network is P2P (Peer to Peer). Unlike conventional client / server systems, P2P is an equivalent of node devices (also referred to as peers) connected to a network (sometimes a client, sometimes a server). It is a system that can communicate. Thereby, P2P has an advantage that high scalability (expandability) can be obtained without load and traffic being concentrated on a specific server.

  As a technique for constructing an overlay network by coordinating a plurality of node devices in a distributed manner, there is a structured overlay network. This is to constrain the network configuration with an ID (identification code) assigned to each node device, and to independently construct an efficient network in the ID space (see Non-Patent Documents 1 to 5). ).

  In general, an ID in a structured overlay network is obtained by applying a hash function (for example, SHA (Secure Hash Standard) -1, Non-Patent Document 6) to an IP (Internet Protocol) address and a boat number assigned to each node device. The value that is applied and mapped to random space is used. Thereby, a logical network completely different from the physical network is constructed. That is, in the structured overlay network, the proximity on the ID space and the proximity on the physical network (number of hops, transmission delay, etc.) are irrelevant between any two node devices.

  Therefore, even if the node device A and the node device B are adjacent to each other on the physical network, there is a possibility that an unnecessarily large number of routers are routed from one to the other. For this reason, the conventional overlay network has a problem in that the message transmission delay increases.

  In order to solve such a problem, in Patent Document 1, in the method of Non-Patent Document 2, the upper bits of the ID are determined by a hash function based on the network address of the IP address, and the lower bits are assigned to the IP of the node device. A data management apparatus that determines a hash function from a set of an address and a port number is disclosed. In this data management apparatus, node devices having close network addresses are assigned IDs having values close to each other even in the ID space, so that the number of router hops in the physical network can be reduced.

  In Patent Document 2, a plurality of peers participating in an overlay network are grouped so as to have similar transport network proximity in order to suppress long-distance connection by a transport network (physical network) between peers. And a system configured to minimize the number of inter-group connections is described.

  In Patent Document 3, each node device constituting an overlay network stores a service name and a service entity provided by itself, a service key obtained by hashing the service name, and a hash of a node identifier obtained by hashing identification information of the own node. A system that provides a service based on a distance D1 in space is described. That is, each node device activates the service entity and autonomously operates the global service when the distance D1 is closer than any of the distance D2 between the node identifier of the node other than the own node existing in the hash space and the service key. Start providing.

  In Patent Document 4, each peer participating in an overlay network measures communication response times for a plurality of landmarks, calculates multidimensional position information based on the response times, and further calculates multidimensional position information. Convert to one-dimensional position information using a space filling curve, apply a spatial distribution function to this one-dimensional position information to obtain uniformed one-dimensional information, and this one-dimensional information and logical identifier space An overlay search technique is described in which the logical identifier of a peer is determined by taking the product of Thereby, the distribution of logical identifiers of peers becomes uniform, and the load is not biased to specific peers.

  In Patent Document 5, the zone space of the overlay network has a double structure of an index zone space and a routing zone space, and the index zone space is divided according to the load of the peer, and the routing zone space is divided. Describes an overlay construction technique in which nodes are divided in consideration of the proximity of nodes. As a result, when peers that manage zones at the same position in two zone spaces are linked to each other, the uneven load of the peers is resolved by dividing the zone space for the index, and the routing efficiency is improved by the zone space for routing. Has been.

  Patent Document 6 describes a technique for determining a unique node ID that does not overlap with other node devices when a node device participating in an overlay network determines a node ID representing its logical position. Yes. According to Patent Document 6, a participation request node device that requests participation in an overlay network determines its own node ID and transmits a participation message to a contact node for the purpose of creating a routing table. On the other hand, when each node device is not a participation request node but receives a participation message in a state where it is the final transfer destination node of the participation message, it transmits a transfer completion message including its own node ID to the participation request node. To do. Further, the participation requesting node device changes the node ID of its own node device and transmits the participation message to the contact node again when the node ID matches the node ID of its own at the final transfer destination of the received transfer completion message. .

  Patent Document 7 describes a technique for hierarchically configuring an overlay network in order to avoid the difficulty of configuring an overlay network with a full mesh when the total number of nodes is large. According to Patent Document 7, a super node layer is formed by logically connecting, as super nodes, some of nodes constituting an overlay network that meet a predetermined condition. Further, the other general nodes are logically connected to and belong to the nearest super node, and a hierarchy in which these general nodes exist is formed as a general node layer. Further, each node is given a two-dimensional coordinate position, and each super node divides the two-dimensional space into the six sectors at an angle θ = π / 3 with respect to itself as a sector j (j = 1 to 1). The super node closest to itself among other super nodes located in the space 6) is logically connected as an adjacent super node to form a super node layer.

JP 2008-011330 A JP 2005-094773 A JP 2008-204299 A JP 2008-269141 A JP 2008-299586 A JP 2009-017069 A JP 2009-043771 A

Sylvia Ratnasamy, Paul Francis, Mark Handley, Richard Karp, Scott Shenker, "A Scalable Content-Addressable Network", Proceedings of ACM SIGCOMM 2001. Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan, "Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications", Proceedings of ACM SIGCOMM 2001. Antony Rowstron, Peter Druschel, "Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems", Proceedings of the IFIP / ACM International Conference on Distributed Systems Platforms.Heiderberg, Germany, November 2001. Petar Maymounkov, David Mazieres "Kademlia: A Peer-to-peer Information System Based on the XOR Metric", Proceedings of IPTPS 2002, Cambrige, Mar. 2002. Ben Y. Zhao, Ling Huang, Jeremy Stribling, Sean C. Rhea, Anthony D. Joseph, John D. Kubiatowicz, "Tapestry: A Resilient Global-Scale Overlay for Service Deployment", IEEE Journal on Selected Areas in Communications, 2004. FIPS PUB 180-1, "SECURE HASH STANDARD", U.S. Department of Commerce, Apr. 1995. L. Yang, R. Dantu, T. Anderson, R. Gopal, "Forwarding and Control Element Separation (ForCES) Framework", RFC3746, IETF, Apr. 2004. Nick McKeown, Tom Anderson, Hari Balakrishnan, Guru Parulkar, Larry Peterson, Jennifer Rexford, Scott Shenker, Jonathan Turner, "OpenFlow: Enabling Innovation in Campus Networks", SIGCOMM Computer Communication Review, Mar. 2008.

  In the conventional method described in Patent Literature 1 and the like, proximity is calculated using a hierarchical structure of IP addresses in a physical network. For this reason, when the IP address does not exist or the network address part is the same even if it exists, there is a problem that the physical proximity cannot be calculated.

  The present invention has been made in view of the above-described problems. Regardless of the presence or absence of an IP address in the overlay network, a value indicating proximity between node devices is obtained based on given group information and proximity information of individual node devices. The object is to calculate and calculate the distance between node devices only by comparing these values.

  To achieve the above object, a node device according to a first aspect of the present invention is a plurality of node devices constituting an overlay network system, each of which is close to information unique to its own node device. From the other node device, a bit string generation unit that degenerates information unique to the bit string to generate a neighboring node bit string, a bit string transmission unit that transmits the neighboring node bit string generated by the bit string generation unit to another node device, and Bit string comparison means for comparing the received neighboring node bit string and the neighboring node bit string generated by the bit string generation means with corresponding bits and determining the proximity of the other node device according to the inter-bit distance. It is characterized by.

  A node device according to a second aspect of the present invention is a plurality of node devices constituting an overlay network system, each of which includes a node-specific bit sequence generation unit that generates a node-specific bit sequence for identifying its own node device; An adjacent node list generation storage unit that generates and stores a adjacent node list for designating adjacent node devices, and a node specific bit string generated by the node specific bit string generation unit according to the adjacent node list A node-specific bit string transmitter that transmits to a node apparatus, a node-specific bit string receiver that receives a node-specific bit string transmitted from the adjacent node apparatus, and a node-specific bit string received by the node-specific bit string receiver Node-specific bit string storage that is stored in association with the original node device A neighboring node that generates a neighboring node bit string by degenerating a node-specific bit string corresponding to a neighboring node device specified in the neighboring node list and its own node-specific bit string generated by the node-specific bit string generation unit A bit string generation unit, a neighboring node bit string transmission unit that transmits the neighboring node bit string generated by the neighboring node bit string generation unit to another node device, and a proximity that receives a neighboring node bit sequence transmitted from the other node device The node bit string receiving unit, the adjacent node bit string received by the neighboring node bit string receiving unit and the neighboring node bit string generated by the neighboring node bit string generating unit are compared with each other corresponding bits, and the neighborhood is determined according to the inter-bit distance. A proximity node bit string comparison unit for determining .

  A node device according to a third aspect of the present invention is a plurality of node devices constituting an overlay network system, each generating and storing a neighboring node list for designating neighboring node devices. A generation storage unit, a neighboring node bit string storage unit that stores a neighboring node bit string of a neighboring node device specified by the neighboring node list, and the neighboring node bit string and the neighboring node bit string and the neighboring node list A neighboring node bit string generation / modification unit that changes the neighboring node bit string so that the inter-bit distance to the neighboring node bit string of any node device of the selected node device, a neighboring node bit string notified from another node device, and its own node Proximity that determines proximity according to the bit-to-bit distance from the adjacent node bit string of the device And Dobitto string comparison unit, characterized in that it comprises a.

  A node device program according to a fourth aspect of the present invention is a program for operating a computer as a node device constituting an overlay network system, and generates a node-specific bit string for identifying its own node device. A node-specific bit string generation unit, a neighboring node list generation / storage unit that generates and stores a neighboring node list for designating neighboring node devices, and a node-specific bit string generated by the node-specific bit string generation unit A node-specific bit string transmitting unit that transmits to the adjacent node device according to the above, a node-specific bit sequence receiving unit that receives a node-specific bit sequence transmitted from the adjacent node device, and a node-specific bit sequence received by the node-specific bit sequence receiving unit For the source node device A node specific bit string storage unit that stores the node specific bit string corresponding to the adjacent node device specified by the adjacent node list, and the node specific bit string generated by the node specific bit string generation unit Proximity node bit string generation unit for generating adjacent node bit string, adjacent node bit string transmission unit for transmitting the adjacent node bit string generated by the adjacent node bit string generation unit to another node device, and proximity transmitted from the other node device A neighboring node bit string receiving unit that receives a node bit string, and a neighboring node bit string received by the neighboring node bit string receiving unit and a neighboring node bit string generated by the neighboring node bit string generating unit are compared between corresponding bits, Neighboring node bit string that determines proximity according to the distance between bits較部, characterized in that causes a computer to function as a.

  A node device program according to a fifth aspect of the present invention is a program for operating a computer as a node device constituting an overlay network system, and generates a neighboring node list for designating neighboring node devices. A neighboring node list generating and storing unit, a neighboring node bit string storing unit that stores a neighboring node bit string of a neighboring node device specified by the neighboring node list, and generating the neighboring node bit string, and the neighboring node bit string and the Proximity node bit string generation and change unit that changes the adjacent node bit string so that the inter-bit distance with the adjacent node bit string of an arbitrary node device in the adjacent node list, and the adjacent node bit string notified from other node devices And the adjacent node bit string of its own node device Neighboring nodes the bit string comparison unit determines locality accordance bit distance, and characterized by causing a computer to function as a.

  According to the present invention, regardless of the presence / absence of an IP address in the overlay network, a value indicating proximity between node devices is calculated based on given group information and proximity information of individual node devices. The distance between node devices can be calculated only by comparison.

It is a block diagram which shows an example of the network with which the node apparatus of embodiment of this invention is applied. It is a block diagram of the node apparatus which shows the 1st Embodiment of this invention. It is a flowchart which shows operation | movement of the node apparatus of FIG. It is a block diagram of the node apparatus which shows the 2nd Embodiment of this invention. 6 is a flowchart showing the operation of the node device of FIG. It is a block diagram of the node apparatus which shows the 3rd Embodiment of this invention. It is a flowchart which shows operation | movement of the node apparatus of FIG.

Hereinafter, embodiments of the present invention will be described in detail with reference to the drawings.
(First embodiment)
The node device according to the first embodiment of the present invention is applied to a network as shown in FIG. This network includes physical communication networks 1A, 1B, and 1C, trunk lines 2A and 2B that connect the communication networks 1A to 1C, and a plurality of node devices 10 that are connected to the communication networks 1A to 1C. It consists of

  For example, node devices 10-A1, 10-A2, and 10-A3 are connected to the communication network 1A, node devices 10-B1, 10-B2, and 10-B3 are connected to the communication network 1B, and the communication network 1C is connected to the communication network 1C. Are connected to node devices 10-C1, 10-C2, 10-C3. The number of communication networks 1A to 1C and the number of node devices 10 connected to each communication network 1A to 1C are arbitrary. In the following description, a suffix (A1 or the like) in the symbol of the node device is omitted except when referring to a specific node device.

  Each of the node devices 10 has the same configuration, and as shown in FIG. 2, a node-specific bit string generation unit 11, a neighboring node list generation storage unit 12, a node-specific bit string transmission unit 13, a node-specific bit string reception unit 14, a node-specific bit string A storage unit 15, a neighboring node bit string generation unit 16, a neighboring node bit string transmission unit 17, a neighboring node bit string reception unit 18, and a neighboring node bit string comparison unit 19 are provided.

  Note that the node device 10 is generally configured by a personal computer or the like having a communication function, and each unit such as the node-specific bit string generation unit 11 is realized as a computer function controlled by a preinstalled program. It has become so.

  The node specific bit string generation unit 11 generates a node specific bit string that is a bit string specific to the node device 10 itself. Specifically, the node-specific bit string is an N-bit bit string (where N is an integer of 2 or more), and an arbitrary bit number n (where n is an integer of 1 or more) is a specific bit value (for example, Logical value “1”). However, since bits having a specific bit value need to be sparse, n <N / 2. The node-specific bit string once generated is stored in the node-specific bit string generation unit 11, and the stored value is output in response to a request.

  As a method for generating the node-specific bit string, there is a method using a random number. That is, a random number generator that generates integers 1 to N is used, and the bit of the digit corresponding to the generated random number is repeatedly set to “1”, so that n bits in N bits become “1”. Just do it.

  As another method for generating a node-specific bit string, for example, for an ID unique to the node device 10 such as an IP address, a port number, a MAC (Media Access Control) address, an SSH (Secure Shell) key, etc. There is a method of applying a Bloom filter. The Bloom filter uses a plurality of hash functions that generate different values, calculates the remainder by dividing the value obtained by passing the hash function for the ID by the bit string length N, and sets the bit corresponding to the remainder +1 to “1”. "

  Further, as another node specific bit string generation method, a logical value between a randomly generated value or a value obtained by applying a Bloom filter to a unique ID and a value obtained by applying a Bloom filter to an ID shared by node devices in a group. There is also a method of taking the sum to form a node-specific bit string. Specific examples of IDs shared by the node devices in the group include an AS (Autonomous System) number of BGP (Boarder Gateway Protocol) on the Internet, an OSPF (Open Shortest Path First) area number, and the like.

  The adjacent node list generation storage unit 12 generates and stores a list of adjacent node device groups to which its own node device 10 belongs, that is, a adjacent node list. The adjacent node device group may be the same among the node devices or may be different for each node device. The neighboring node device group may be physically adjacent or logically adjacent. In addition, a neighboring node device group may be configured in consideration of both physical proximity and logical proximity. Furthermore, the neighboring node list is not limited to node devices belonging to a single neighboring node device group, and can include node devices of a plurality of neighboring node device groups.

  The physical neighboring node device group is composed of node devices having a proximity relationship considering an underlay network topology. Specifically, the neighboring node device group includes other node devices connected to a network relay device such as a single switch or a plurality of switches and routers connected to the node device. A neighboring node device group can also be configured by node devices having the same network identifier (for example, a network address in an IP address) or node devices belonging to the same network identifier group.

  The network information of these underlays may be set in advance based on the setting information of the network relay device, but the setting information is acquired using a management information acquisition mechanism (SNMP: Simple Network Management Protocol) or the like. It is also possible to set it dynamically.

  The group unit may be a single or a plurality of computer clusters to which the node device belongs. Further, grouping can be performed based on the transmission delay time between node devices. That is, when the transmission delay time between node devices is within a certain threshold, it is determined that the node devices belong to the same communication network.

  Other grouping methods include routing protocol link information (for example, OSPF LSA: Link-State Advertisement), a protocol for discovering adjacent relay devices (for example, LLDP: Link Layer Discovery Protocol), There is a method of acquiring topology information of network relay devices from presetting and grouping according to the number of hops from the network relay device to which the node device is connected. Also, node devices can be grouped according to the management classification of the routing protocol.

  In a network relay device, in the case of an architecture (ForCES (see Non-Patent Document 7) or OpenFlow (see Non-Patent Document 8)) in which a control plane and a relay plane are separated and connected via a communication network used for inter-node communication. Based on the connection of the network relay devices that are planes, it is possible to group the node devices on which the control plane is operating. Also, node devices can be grouped based on the connection between network relay devices to which the control plane is connected.

  On the other hand, the logical proximity node device group is a group of node devices based on information connection. Specifically, node devices having a high communication frequency and node devices having the same required information are grouped. Grouping by communication frequency refers to a communication history for each node device, and sets the number of communication times per unit time exceeding a threshold as the same group. Grouping based on necessary information is based on the number of shared database table names and messaging mechanism message channel names that are the same, and those whose number exceeds a threshold value are grouped together.

  Further, the management configuration of the node device may be used as the logical proximity node device group. In a node device name having a hierarchical domain such as FQDN (Fully Qualified Domain Name) of DNS (Domain Name System), node devices belonging to a single or a plurality of hierarchical domains may be made into the same group. When node devices are managed by a Lightweight Directory Access Protocol (LDAP) directory service, node devices belonging to a single directory or multiple directories in the directory service may be grouped.

  Furthermore, grouping according to the length of the duration for the overlay network can be performed as a logical neighboring node device group. In the P2P network, the shorter the connection time, the higher the possibility of leaving the overlay network, and the longer the connection time, the higher the possibility that the node device remains in the overlay network. Therefore, grouping node devices having a certain connection time or more leads to an improvement in the reliability of the overlay network.

  The node-specific bit string transmission unit 13 reads out its own node-specific bit string from the node-specific bit string generation unit 11 and transmits it to the adjacent node device 10 according to the adjacent node list stored in the adjacent node list generation storage unit 12. is there.

  The node specific bit string receiving unit 14 receives a node specific bit string transmitted from another adjacent node device 10. The node specific bit string of the other node device 10 received by the node specific bit string receiving unit 14 is given to the node specific bit string storage unit 15, and is stored in association with each node device 10 by the node specific bit string storage unit 15. It has become so.

  The neighboring node bit string generation unit 16 generates a neighboring node bit string obtained by degenerating information on neighboring nodes according to the node unique bit string of each node device 10 of the neighboring node device group to which the node device 10 belongs and the own node unique bit string. is there. That is, the neighboring node bit string generation unit 16 reads the neighboring node list from the neighboring node list generation storage unit 12, and reads the node specific bit string of the node device 10 corresponding to this neighboring node list from the node specific bit string storage unit 15. Further, the adjacent node bit string generation unit 16 reads out its own node specific bit string from the node specific bit string generation unit 11, calculates the logical sum of the node specific bit strings of the node devices 10 adjacent to itself, and calculates the calculation result as the adjacent node bit string Output as.

  The adjacent node bit string transmission unit 17 transmits the adjacent node bit string generated by the adjacent node bit string generation unit 16 to another node device 10. It is desirable that the transmission of the adjacent node bit string is not performed alone but is transmitted together with the message or the like in the payload at a timing when other communication such as message transmission / reception is performed.

  The neighboring node bit string receiving unit 18 receives a neighboring node bit string sent from another node device 10 (along with a message or the like).

  The neighboring node bit string comparison unit 19 compares the neighboring node bit string received from the other node device 10 received by the neighboring node bit string reception unit 18 with its own neighboring node bit string generated by the neighboring node bit string generation unit 16, and The proximity between the devices 10 is calculated. As a method for calculating the proximity, a Hamming distance or an inter-bit distance based on the number of matched bits is used. In the case of the Hamming distance, the smaller the value is, the closer the position is. In the case of the number of matched bits, the closer the position is, the closer the number is. When a sparse value of “1” bits is used as the node-specific bit string, the comparison is performed using the Hamming distance or the number of coincident “0” bits.

  The determination result of the proximity between the node devices 10 calculated by the adjacent node bit string comparison unit 19 is used for actual connection control between the node devices 10. For example, if the distance to a certain node device 10 is not more than a certain threshold value, the connection with the corresponding node device 10 is continued, and if it exceeds this threshold value, the connection is disconnected. Can do.

  Next, the operation of the node device of FIG. 2 will be described with reference to FIG. In this description of operation, the node devices 10-A2, 10-A3, 10-B1, 10-B2, and 10-B3 are designated as adjacent node devices with the node device 10-A1 in FIG. 1 as the center. Shall. Here, the operation of the node device 10-A1 will be described, but the same operation is performed in each of the other node devices 10-A2 and the like.

  In the node specific bit string generation / transmission / reception process shown in FIG. 3A, first, the node specific bit string generation unit 11 of the node device 10-A1 generates its own node specific bit string (step S1). Here, N, which is the length of the node-specific bit string, is 9 bits, and the number of bits n having a specific bit value (here, logical value “1”) is 1.

  Thereby, the node specific bit string of the node device 10-A1 is set to, for example, “000000001”, and the node devices 10-A2, 10-A3, 10-B1, 10-B2, 10-B3, 10-C1, 10− The node specific bit strings of C2, 10-C3 are set to “000000010”, “000000100”, “000001000”, “000010000”, “000100000”, “001000000”, “010000000”, “100000000”, respectively. To do. A method for preventing the node devices 10 from setting the same node-specific bit string is described in Patent Document 6, for example.

  The neighboring node list generation storage unit 12 of the node device 10-A1 generates a neighboring node list based on a physical or logical proximity relationship (step S2). Here, as described above, based on the physical proximity relationship, the adjacent node list is generated using the node devices 10-A2, 10-A3, 10-B1, 10-B2, and 10-B3 as adjacent node devices. Is done.

  Further, the node specific bit string transmission unit 13 of the node apparatus 10-A1 registers the node specific bit string generated by the node specific bit string generation unit 11 in the adjacent node list of the adjacent node list generation storage unit 12. (Step S3). As a result, the node-specific bit string “000000001” of the node device 10-A1 is transmitted to the adjacent node devices 10-A2, 10-A3, 10-B1, 10-B2, and 10-B3.

  On the other hand, the node specific bit string receiving unit 14 of the node device 10-A1 receives the node specific bit string transmitted from the other node device 10-A2 or the like (step S4), and stores it in the node specific bit string storage unit 15 (step S4). Step S5). In this way, the node-specific bit string of the node device 10-A1 is notified to the adjacent node device 10-A2 etc., and the nodes set in the respective node devices 10 from these adjacent node devices 10-A2 etc. The unique bit string is notified to this node device 10-A1.

  In the adjacent node bit string generation / transmission process shown in FIG. 3B, the adjacent node bit string generation unit 16 reads and acquires its own node specific bit string from the node specific bit string generation unit 11 (step S11). Further, the neighboring node bit string generation unit 16 reads the neighboring node list from the neighboring node list generation storage unit 12, and reads the node specific bit string of the neighboring node device 10 corresponding to this neighboring node list from the node specific bit string storage unit 15. Obtain (step S12).

  Further, the adjacent node bit string generation unit 16 calculates a logical sum of the node specific bit strings of the node device 10 adjacent to itself, and generates the calculation result as a adjacent node bit string (step S13). As a result, the node-specific bit string “000000001” of the node device 10-A1 and the node-specific bit sequences “000000010” of the adjacent node devices 10-A2, 10-A3, 10-B1, 10-B2, and 10-B3, A logical sum “000111111” of “000000100”, “000001000”, “000010000”, and “000100000” is generated as the adjacent node bit string.

  The adjacent node bit string generated by the adjacent node bit string generation unit 16 is read by the adjacent node bit string transmission unit 17 at a timing when other communication such as transmission / reception of a message is performed, and is loaded on the payload and other messages and the like It is transmitted to the node device 10 (step S14).

  In the proximity determination process shown in FIG. 3C, when a message or the like is transmitted from another node device 10, the adjacent node bit string receiving unit 18 uses the adjacent node bit string loaded in the payload together with the message or the like. Receive (step S21).

  The neighboring node bit string received by the neighboring node bit string receiving unit 18 is given to the neighboring node bit string comparing unit 19 and compared with the neighboring node bit string generated by the neighboring node bit string generating unit 16 (step S22).

  For example, when the Hamming distance is used for calculating the proximity, if the node device 10-A2 designates the node devices 10-A1, 10-A3, 10-B1 to 10-B3 as the neighboring node devices, this node device The adjacent node bit string of 10-A2 is “000111111” which is the same as the adjacent node bit string of the node device 10-A1. Accordingly, the Hamming distance between the node device 10-A1 and the node device 10-A2 is zero.

  Further, when all the node devices 10-A1 to 10-C3 in FIG. 1 are designated as the adjacent node devices to the node device 10-B1, the adjacent node bit string of the node device 10-B1 is “111111111”. is there. Accordingly, the Hamming distance between the node device 10-A1 and the node device 10-B1 is 3.

  When the node device 10-C1 designates the node devices 10-B1 to 10-B3, 10-C2, and 10-C3 as the adjacent node devices, the adjacent node bit string of the node device 10-C1 is “111111000”. It is. Therefore, the Hamming distance between the node device 10-A1 and the node device 10-C1 is 6.

  The proximity determination result calculated by the adjacent node bit string comparison unit 19 is given to a connection management unit (not shown) and used for connection control between the node devices 10.

As described above in detail, the node device 10 according to the first embodiment generates a neighboring node bit string according to the neighboring node list, and the inter-bit distance between the neighboring node bit string and the neighboring node bit string received from the other node device 10. The proximity is determined according to
As a result, regardless of the presence or absence of an IP address in the overlay network, a value indicating the proximity between the node devices 10 is calculated based on the given group information and the proximity information of each node device, that is, according to an arbitrary criterion. There is an advantage that the distance between the node devices 10 can be calculated only by comparing these values.

(Second Embodiment)
The node device 10A according to the second embodiment of the present invention is used in place of the node device 10 in FIG. 1, and, as shown in FIG. 4, the node device 10 according to the first embodiment has an adjacent node bit string. A storage unit 20 and a node-specific bit string changing unit 21 are added. In FIG. 4, elements common to those in FIG. 2 are denoted by common reference numerals, and description thereof is omitted.

  The neighboring node bit string storage unit 20 stores the neighboring node bit string received by the neighboring node bit string receiving unit 18 in association with the node device 10A that transmitted the neighboring node bit string.

  The node-specific bit string changing unit 21 is configured so that the inter-bit distance between the neighboring node bit string of its own node device 10A and the neighboring node bit string of the node device 10A that is not registered in the neighboring node list generation storage unit 12 increases. The node-specific bit string is changed.

  More specifically, the node-specific bit string changing unit 21 refers to the neighboring node list in the neighboring node list generating and storing unit 12 and uses the neighboring node bit string of the node device 10A that does not exist in the neighboring node list as the neighboring node bit string storage unit 20. , And the matching bit in the acquired adjacent node bit string and its own node-specific bit string are checked, and an arbitrary number of bits in the matching own node-specific bit string are changed. This change may be performed once or may be repeated a plurality of times.

  Next, the operation of the node-specific bit string changing process in the node device 10A of FIG. 4 will be described with reference to FIG.

  The adjacent node bit string generation unit 16 reads out and acquires its own node specific bit string from the node specific bit string generation unit 11 (step S31), and also reads out the adjacent node list from the adjacent node list generation storage unit 12, and stores it in the adjacent node list. The node specific bit string of the corresponding adjacent node device 10A is read out from the node specific bit string storage unit 15 and acquired (step S32).

  Further, the adjacent node bit string generation unit 16 calculates a logical sum of the node-specific bit strings of the node device 10A adjacent to itself and generates the calculation result as a adjacent node bit string (step S33).

  The node specific bit string changing unit 21 first acquires a neighboring node bit string corresponding to the node device 10A that is not registered in the neighboring node list among the neighboring node bit strings stored in the neighboring node bit string storage unit 20 (step S34). ). Next, the node-specific bit string changing unit 21 compares the adjacent node bit string acquired in step S34 with its own adjacent node bit string generated by the adjacent node bit string generating unit 16 for each bit, and the number of matching bits Is calculated (step S35).

  Further, the node-specific bit string changing unit 21 determines whether or not there is a node device 10A in which the number of matching bits in the adjacent node bit string is equal to or less than the threshold (step S36). If there is a node device 10A in which the number of matching bits is equal to or less than the threshold (step S36; Yes), the node-specific bit string of its own node device 10A generated by the node-specific bit string generation unit 11 is changed (step S37). The process returns to step S33.

  On the other hand, when there is no node device 10A in which the number of coincidence bits calculated in step S35 is equal to or less than the threshold (step S36; No), the node specific bit string transmission unit 13 generates the node specific bit string generation unit 11 itself. The node-specific bit string of the node device 10A is transmitted without change to the other node device 10A (step S38).

  This node-specific bit string changing process is not only performed when the node device 10A is activated, but can also be performed periodically during operation. As a result, even if a proximity node bit string having a proximity between the node devices 10A having no proximity is generated, the proximity can be eliminated over time.

(Third embodiment)
The node device 30 according to the third embodiment of the present invention is used in place of the node device 10 in FIG. 1, and as shown in FIG. 6, the adjacent node list generation storage unit 31, the adjacent node adjacent node bit string A receiving unit 32, a neighboring node bit string storage unit 33, a neighboring node bit string generation / modification unit 34, a neighboring node neighboring node bit string transmitting unit 35, a neighboring node bit string transmitting unit 36, a neighboring node bit string receiving unit 37, and a neighboring node bit string comparing unit 38 It has.

  The neighboring node list generation storage unit 31 generates and stores a list of neighboring node device groups to which its own node device 30 belongs, that is, a neighboring node list, and is similar to the neighboring node list generation storage unit 12 in FIG. It has a function.

  The adjacent node adjacent bit string receiving unit 32 receives the adjacent node bit string transmitted from the node device 30 in the adjacent node list stored in the adjacent node list generating and storing unit 31.

  The neighboring node bit string storage unit 33 stores the neighboring node bit string received by the neighboring node neighboring node bit string receiving unit 32 in association with the source node device 30. The storage contents of the adjacent node bit string storage unit 33 are updated at an arbitrary timing. The update timing may be a constant interval or may be performed based on the probability of being a constant interval.

  The neighboring node bit string generation / change unit 34 generates a neighboring node bit string of its own node device 30 and changes the generated neighboring node bit string so as to approach a neighboring node bit string of an arbitrary node device 30 in the neighboring node list. Is.

  Specifically, the neighboring node bit string generation / change unit 34 selects one or a plurality of node devices 30 from the neighboring node list stored in the neighboring node list generation storage unit 31, and the neighboring node corresponding to the selected node device 30. A bit string is acquired from the adjacent node bit string storage unit 33. Furthermore, the bit of the arbitrary location (possibly a plurality of locations) of the acquired adjacent node bit string is overwritten in the corresponding location of the adjacent node bit sequence of its own node device 30. Thereby, the Hamming distance between the adjacent node bit strings of the own node device 30 and any other node device 30 approaches.

  If there is no adjacent node bit string, a random number or node-specific ID (eg, IP address, port number, MAC address, SSH key, commercial software serial number, etc.) is prepared by applying a hash function. Then, the bit at an arbitrary position of the value is overwritten in the corresponding position of the adjacent node bit string of the own node device 30.

  In order to prevent the adjacent node bit string of all the node devices 30 from having the same value due to the change of the adjacent node bit string, the bits of arbitrary portions of the adjacent node bit string of the node device 30 are different with a smaller probability than the overwriting change. It may be changed to a value.

  The adjacent node bit string transmission unit 35 between adjacent nodes is the adjacent node generated or changed by the adjacent node bit string generation / change unit 34 with respect to the node device 30 of the adjacent node list stored in the adjacent node list generation storage unit 31. A bit string is transmitted. It is desirable that this adjacent node bit string is not transmitted alone, but is transmitted together with the message or the like in the payload at a timing when other communication such as message transmission / reception is performed.

  The neighboring node bit string transmission unit 36 transmits its own neighboring node bit string generated or changed by the neighboring node bit string generation / change unit 34 to other node devices 30 without being limited to the node devices 30 in the neighboring node list. is there. It is desirable that the transmission of the adjacent node bit string is not performed alone but is transmitted together with the message or the like in the payload at a timing when other communication such as transmission / reception of the message is performed.

  Note that the adjacent node bit string transmitter 35 and the adjacent node bit string transmitter 36 differ only in whether or not the transmission destination of the adjacent node bit string is the node device 30 specified in the adjacent node list. Other functions are the same. Therefore, if it can be identified that information is transmitted between neighboring node devices, it can be shared. As an identification method, there is a method of putting an identification flag for the adjacent node device 30 at the time of transmission.

The neighboring node bit string receiving unit 37 receives neighboring node bit strings from other node devices 30.
Note that the adjacent node bit string receiving unit 32 and the adjacent node bit string receiving unit 37 are different only in whether or not the transmission source of the adjacent node bit string is the node device 30 specified in the adjacent node list. Other functions are the same. Therefore, if it can be identified that information is received between neighboring node devices, it can be shared. As a method of identification, there is a method of collating the source node device 30 with a neighboring node list at the time of reception.

  The neighboring node bit string comparison unit 38 is a proximity node bit string received from the other node device 30 received by the neighboring node bit string receiving unit 37 and its own node device 30 generated or changed by the neighboring node bit string generation changing unit 34. The node bit strings are compared, and the proximity between the node devices 30 is calculated. As a method of calculating the proximity, there is a method of using a Hamming distance or an inter-bit distance based on the number of matched bits, as in the proximity node bit string comparison unit 19 in FIG.

  Next, the operation of the proximity determination process in the node device 30 of FIG. 6 will be described with reference to FIG.

  First, the proximity node list generation storage unit 31 generates and stores a proximity node list (step S41). On the other hand, the adjacent node bit string receiving unit 32 between adjacent nodes receives the adjacent node bit string transmitted from the adjacent node device 30 (step S42), and the adjacent node bit string storage unit 33 stores the received adjacent node bit string. (Step S43).

  Next, if the adjacent node bit string has not been generated yet, the adjacent node bit string generation / change unit 34 refers to the adjacent node list in the adjacent node list generation storage unit 31 to generate the adjacent node bit string. If the adjacent node bit string has already been generated, the adjacent node bit string generation / change unit 34 performs its own proximity according to the adjacent node list in the adjacent node list generation storage unit 31 and the adjacent node bit string stored in the adjacent node bit string storage unit 33. The node bit string is changed (step S44).

  The adjacent node bit string transmission unit 35 between adjacent nodes transmits the adjacent node bit string generated or changed by the adjacent node bit string generation / change unit 34 to the adjacent node device 30 in accordance with the transmission timing of a message or the like (step S45). .

  The neighboring node bit string receiving unit 37 receives the neighboring node bit string transmitted from the other node device 30 together with a message or the like (step S46). The neighboring node bit string of the other node device 30 received by the neighboring node bit string receiving unit 37 is given to the neighboring node bit string comparing unit 38, and held in the neighboring node bit string generating / changing unit 34 in the neighboring node bit string comparing unit 38. It is compared with its own neighboring node bit string (step S47).

  The proximity determination result calculated by the adjacent node bit string comparison unit 38 is given to a connection management unit (not shown) and used for connection control between the node devices 30.

As described above in detail, in the node device 30 according to the third embodiment, the neighboring node bit string generation / change unit 34 generates its own neighboring node bit string according to the neighboring node list specified by the neighboring node list generation storage unit 31. In addition, the adjacent node bit string is changed using the adjacent node bit string received from the adjacent node device 30 and stored in the adjacent node bit string storage unit 33.
Thereby, the node device 30 of the present embodiment has an advantage that the proximity can be sequentially updated in accordance with the adjacent node bit string of the adjacent node device 30 in addition to the same advantages as the first embodiment.

  In addition, this invention is not limited to the said embodiment, The following various deformation | transformation are possible.

(A) In the second embodiment, the adjacent node bit string storage unit 20 and the node-specific bit string change unit 21 are provided, and the node-specific bit string of its own so that the inter-bit distance between the node devices 10A other than the adjacent node list is increased. However, the same configuration can be adopted in the third embodiment.
In that case, the neighboring node bit string storage unit 33 stores the neighboring node bit string of another node device 30 (other than the neighboring node) received by the neighboring node bit string receiving unit 37, and the neighboring node bit string generation / change unit 34 stores the other node device. What is necessary is just to change an adjacent node bit sequence so that the distance between bits with 30 may become long. Specifically, the proximity node bit string of an arbitrary node device 30 not included in the proximity node list stored in the proximity node list generation storage unit 31 so that the proximity determination result of the proximity node bit string comparison unit 38 is away from each other, What is necessary is just to reduce the number of bits with which the adjacent node bit string of the own node apparatus 30 corresponds.
Alternatively, the adjacent node bit string generation / change unit 34 may change the bit at an arbitrary position of the adjacent node bit string of the node device 30 to a different value.

(B) In the first to third embodiments, the description has been made using the binary bit string. However, the Galois field having the element of 2n powers even in the multivalued bit of 2n powers, It is possible to respond by thinking.

(C) In the first to third embodiments, all adjacent node bit sequences from a certain node device have been described as having the same value. However, a different reference node bit sequence is calculated by setting a setting criterion for each node device. Also good. Here, the setting criterion is to remove a specific node device from the adjacent node list for a specific node device or add a specific node device to the adjacent node list for a specific node device. In addition, a specific bit string can be added to the adjacent node bit string.

1A to 1C Communication network 2A, 2B Core line 10, 10A, 30 Node device 11 Node specific bit string generation unit 12, 31 Proximity node list generation storage unit 13 Node specific bit string transmission unit 14 Node specific bit string reception unit 15 Node specific bit string storage unit 16 Proximity node bit string generation unit 17, 36 Proximity node bit string transmission unit 18, 37 Proximity node bit string reception unit 19, 38 Proximity node bit string comparison unit 20, 33 Proximity node bit string storage unit 21 Node-specific bit string change unit 32 Proximity node between adjacent nodes Bit string reception unit 34 Proximity node bit string generation change unit 35 Proximity node bit string transmission unit between adjacent nodes

Claims (22)

A plurality of node devices constituting the overlay network system,
Bit string generation means for generating information on a neighboring node bit string by degenerating information unique to its own node device and information unique to a neighboring node device;
Bit string transmission means for transmitting the adjacent node bit string generated by the bit string generation means to another node device;
Bit string comparison for comparing neighboring node bit string received from the other node device and the neighboring node bit string generated by the bit string generating unit between corresponding bits and determining the proximity of the other node device according to the inter-bit distance Means,
A node device comprising: A plurality of node devices constituting the overlay network system,
A node-specific bit string generation unit that generates a node-specific bit string for identifying its own node device;
A neighboring node list generation storage unit that generates and stores a neighboring node list for designating neighboring node devices;
A node-specific bit string transmission unit that transmits the node-specific bit string generated by the node-specific bit string generation unit to the adjacent node device according to the adjacent node list;
A node-specific bit string receiving unit that receives a node-specific bit string transmitted from the adjacent node device;
A node-specific bit string storage unit that stores the node-specific bit string received by the node-specific bit string reception unit in association with a source node device;
Proximity node bit string generation for degenerating a node specific bit string corresponding to a neighboring node device specified in the adjacent node list and its own node specific bit string generated by the node specific bit string generation unit to generate a neighbor node bit string And
A neighboring node bit string transmitter that transmits the neighboring node bit string generated by the neighboring node bit string generator to another node device;
A neighboring node bit string receiving unit that receives a neighboring node bit string transmitted from the other node device;
Neighboring node that compares neighboring node bit string received by the neighboring node bit string receiving unit and its neighboring node bit string generated by the neighboring node bit string generating unit with corresponding bits and determines proximity according to the inter-bit distance A bit string comparison unit;
A node device comprising: A neighboring node bit string storage unit that stores a neighboring node bit string received by the neighboring node bit string receiving unit in association with a source node device;
The inter-bit distance between the adjacent node bit string stored in the adjacent node bit string storage unit and the node specific bit string generated by the node specific bit string generation unit with a node device not specified in the adjacent node list as a transmission source is long A node-specific bit string changing unit that changes the node-specific bit string so that
The node device according to claim 2, further comprising:   The node specific bit string changing unit is stored in the neighboring node bit string storage unit with a node device not specified in the neighboring node list among the node specific bit strings generated by the node specific bit string generating unit as a transmission source 4. The node device according to claim 3, wherein an arbitrary number of bits matching the adjacent node bit string is changed.   5. The node device according to claim 2, wherein the node specific bit string generation unit generates a sparse bit string as the node specific bit string.   The node device according to claim 5, wherein the node-specific bit string generation unit generates the sparse bit string from an identification code unique to the node device using a Bloom filter.   The node specific bit string generation unit generates, as the node specific bit string, a value obtained by performing a logical OR for each bit of the sparse bit string and a bit string calculated using a Bloom filter for a unique identification code for each group. The node device according to claim 6, wherein:   The adjacent node list generation storage unit stores other node devices having either a physical distance or a logical distance close to each other, or other node devices having both a physical distance and a logical distance close to each other. The node device according to claim 2, wherein the node device is designated as a neighboring node device by a neighboring node list.   The proximity node list generation storage unit is a proximity based on one or more elements of an underlay network topology, a delay time between node devices, and a hop count of a relay device between node devices as a physical distance. The node device according to claim 8, wherein a relationship is used.   The node device according to claim 8, wherein the proximity node list generation storage unit uses a proximity relationship based on grouping based on information association as a logical distance.   The node device according to claim 8, wherein the proximity node list generation storage unit uses a proximity relationship based on grouping of management configurations of node devices as a logical distance.   The adjacent node bit string generation unit is configured such that the node specific bit string corresponding to the adjacent node device specified by the adjacent node list and the corresponding bits of the node specific bit string generated by the node specific bit string generation unit 12. The node device according to claim 2, wherein the adjacent node bit string is generated by a logical sum.   The neighboring node bit string comparison unit includes the bit according to the Hamming distance or the number of matches of a specific bit value between the neighboring node bit string received by the neighboring node bit string receiving unit and the neighboring node bit string generated by the neighboring node bit string generating unit. The node device according to any one of claims 2 to 12, wherein an inter-distance is calculated and proximity is determined. A plurality of node devices constituting the overlay network system,
A neighboring node list generation storage unit that generates and stores a neighboring node list for designating neighboring node devices;
A neighboring node bit string storage unit that stores neighboring node bit strings of neighboring node devices specified in the neighboring node list;
Proximity node bit string generation change that generates the neighboring node bit string and changes the neighboring node bit string so that the inter-bit distance between the neighboring node bit string and the neighboring node bit string of any node device in the neighboring node list approaches And
A neighboring node bit string comparison unit that determines proximity according to the inter-bit distance between the neighboring node bit string notified from another node apparatus and the neighboring node bit string of its own node apparatus;
A node device comprising:   The adjacent node list generation storage unit stores other node devices having either a physical distance or a logical distance close to each other, or other node devices having both a physical distance and a logical distance close to each other. The node device according to claim 14, wherein the node device is designated as a neighboring node device by a neighboring node list.   The neighboring node bit string generation / modification unit selects one or a plurality of node devices from the neighboring node list, obtains a neighboring node bit string of the selected node device, and obtains a bit at an arbitrary location of the obtained neighboring node bit string The node device according to claim 14 or 15, wherein the adjacent node bit string is changed by overwriting a corresponding portion of the adjacent node bit string of the node device.   The neighboring node bit string generation / change unit selects an arbitrary node device not specified in the neighboring node list, obtains a neighboring node bit string of the selected node device, and obtains the obtained neighboring node bit string and its own device. 16. The node apparatus according to claim 14, wherein the adjacent node bit string is changed so that a distance between bits with the adjacent node bit string is increased.   The neighboring node bit string generation / modification unit selects an arbitrary node device not specified in the neighboring node list, acquires a neighboring node bit string of the selected node device, and within the neighboring node bit string of its own node device 16. The node device according to claim 14, wherein the adjacent node bit string is changed so that the inter-bit distance is increased by changing a bit that matches the acquired adjacent node bit string. .   The node device according to any one of claims 14 to 18, wherein the neighboring node bit string generation / change unit changes a bit at an arbitrary position of a neighboring node bit string of its own node device to a different value.   The adjacent node bit string comparison unit calculates the inter-bit distance according to the Hamming distance or the number of coincidence of specific bit values between the adjacent node bit string notified from another node apparatus and the adjacent node bit string of its own node apparatus. The node device according to any one of claims 14 to 19, wherein proximity is determined. A program for a node device for operating a computer as a node device constituting an overlay network system,
A node-specific bit string generation unit that generates a node-specific bit string for identifying its own node device;
Proximity node list generation storage unit for generating and storing a proximity node list for designating adjacent node devices,
A node-specific bit string transmission unit that transmits the node-specific bit string generated by the node-specific bit string generation unit to the adjacent node device according to the adjacent node list;
A node-specific bit string receiving unit that receives a node-specific bit string transmitted from the adjacent node device;
A node-specific bit string storage unit that stores the node-specific bit string received by the node-specific bit string reception unit in association with a source node device;
Neighboring node bit string that generates a neighboring node bit string by degenerating the node-specific bit string corresponding to the neighboring node device specified in the neighboring node list and its own node-specific bit string generated by the node-specific bit string generation unit Generator,
A neighboring node bit string transmitter that transmits the neighboring node bit string generated by the neighboring node bit string generator to another node device;
A neighboring node bit string receiving unit that receives a neighboring node bit string transmitted from the other node device; and
A proximity node bit string comparison that compares the neighboring node bit string received by the neighboring node bit string reception unit and the neighboring node bit string generated by the neighboring node bit string generation unit with corresponding bits and determines proximity according to the inter-bit distance. Part,
A program for a node device, which causes a computer to function as: A program for a node device for operating a computer as a node device constituting an overlay network system,
Proximity node list generation storage unit for generating and storing a proximity node list for designating adjacent node devices,
A neighboring node bit string storage unit that stores neighboring node bit strings of neighboring node devices specified in the neighboring node list;
Proximity node bit string generation change that generates the neighboring node bit string and changes the neighboring node bit string so that the inter-bit distance between the neighboring node bit string and the neighboring node bit string of any node device in the neighboring node list approaches Part and
Proximity node bit string comparison unit for determining proximity according to the inter-bit distance between the adjacent node bit string notified from another node apparatus and the adjacent node bit string of its own node apparatus
A program for a node device, which causes a computer to function as:

Images