JP4319486B2 - Communication network system - Google Patents

Description

  The present invention relates to a communication network system, and more particularly, by constructing a symmetric overlay network having a plurality of nodes on an IP network, bidirectional communication between any of the nodes in the symmetric overlay network is performed. The present invention relates to a communication network system that is enabled via a network.

  Currently, the current IP network (for example, the Internet) can be used for the first time in the WAN (Wide Area Network) by connecting each client machine to an addressable server machine. Become. In other words, the IP network is “asymmetric” in the sense that the roles of the server machine and the client machine are clearly separated. This asymmetry of the IP network does not occur in operation in a LAN (Local Area Network) but occurs in operation in a WAN. In short, it can be considered that the symmetry of the IP network is broken in the WAN.

  By the way, as the use of the IP network in the WAN becomes widespread, a form of using a globally addressable machine having a global IP address from a machine that is not necessarily globally addressable is spreading. For example, when browsing the WWW, the content is on a globally addressable machine, and the form is accessed from a personal computer such as a home via an IP provider. On the other hand, it is very difficult to arrange an HTTP server on the personal computer side such as a home and accept external access for the following reasons. First, one reason is that in general, personal computers at home are not globally addressable. The second reason is that it is difficult to keep the personal computer in the home secure enough to withstand external connections.

  For the reasons described above, the use of the IP network in the WAN is currently asymmetric, and the roles and operation methods of the server machine and the client machine are clearly distinguished. Therefore, in such a situation, it is impossible to connect PCs between households or between companies and receive the same benefits as a LAN.

In other words, the current Internet problems include the following.
(1) Since information is distributed only through a limited server, it is difficult to use for information exchange between households or workgroup support between companies.
(2) Building and maintaining a server environment is more difficult than creating content.
(3) Since the possibility of connection depends on the presence / absence / type of a firewall and the presence / absence of a global IP address, existing excellent protocols cannot be easily used.
(4) Generally, broadcast and multicast cannot be used.
(5) Enormous costs are required to realize security, anonymous communication, billing, and QoS.
(6) Concentration of load on the server reduces the overall throughput.

  On the other hand, in recent years, low-priced high-bandwidth communication services such as ADSL and FTTH have become widespread, and the processing capacity of personal computers that are often used as personal terminals has been remarkably improved. Maintaining the form is becoming meaningless, and thus a technology that enables symmetric connection on the WAN, that is, P2P (peer-to-peer) is also becoming popular. Advantages of this P2P technology include the following.

  First, you can connect to the network without a global IP address in the firewall and service files, data, and calculations. Second, streaming services can be provided to thousands and tens of thousands of machines even from machines with small capabilities. It is easy to use because it does not require difficult settings such as name service and firewall and server management. In addition, it is safe because it does not pose a threat of normal Internet cracking. It has a powerful search capability by Internet broadcast communication. Supports group activities via Internet multicast communication. Furthermore, operation management of the application server is unnecessary.

As specific examples of the current P2P technology, there are applications using the P2P technology such as “Gnutella”, “Napster”, and “Internet Relay Chat” (see Non-Patent Document 1).
Ito Naoki, “P2P Computing -Technical Explanation and Applications-”, 1st Edition, Soft Research Center, November 2001

  For example, “Gnutella” is an early P2P software capable of exchanging files of various formats, but has a drawback that other calculation processing and remote operation are impossible. “Gnutella” is a typical serverless type pure P2P software, but it is not more than a file exchange function.

  “Internet Relay Chat” is server-use type P2P software having functions such as message exchange and file exchange. Each of them has a drawback that it is a target application-dependent type and cannot perform data processing or calculation processing on the network (Internet) outside the application.

  The present invention has been made in view of the above circumstances, and an object of the present invention is to construct an arbitrary symmetric overlay network in the symmetric overlay network by constructing a symmetric overlay network having a plurality of nodes on the IP network. Another object of the present invention is to provide a communication network system that enables two-way communication between the nodes via the IP network.

  The present invention provides a communication that enables bidirectional communication between any of the nodes in the symmetric overlay network by constructing a symmetric overlay network having a plurality of nodes on the IP network. With respect to a network system, the above object of the present invention is to establish bidirectional communication between any of the nodes in the symmetric overlay network by constructing a symmetric overlay network having a plurality of nodes on the IP network. A symmetric overlay network in which all nodes are logically connected as an n-ary classification tree, and a unique identifier for the node to identify itself And the identifier of the node By interpreting as a base number, adjacent nodes to be connected to each other are determined autonomously, the basic number of connections of the nodes is n + 1, and the nodes are connected by the IP transport layer Is achieved by doing so.

The above object of the present invention is to make sure that a two-route connection is established for a relay node from a certain node to an arbitrary node in the symmetric overlay network, and the relay node includes a representative node and a sub-representative node. Alternatively, the symmetric overlay network includes a P2P networking protocol module unit, a P2P transport module unit, a P2P routing table module unit, a P2P routing algorithm module unit, and a P2P link communication module. And a callback management / execution module unit, or in the symmetric overlay network, each node has at least two primary and secondary connections. Or the symmetric overlay network operates a “router node” that relays a packet and an application that is operated by a user without relaying the packet. A leaf node and an entry point that mediates when a new entry node enters the symmetric overlay network and teaches an adjacent node to which the new entry node is connected, or In the overlay network, appropriate filtering is performed at the “entry point” so that entry of nodes other than nodes known in advance can be eliminated, or the representative node is connected to the symmetric overlay. When leaving the network, the secondary representative node It becomes de, and by so they elect a new vice president from among the nodes that know as deputy, or as the IP transport layer, TCP, or reliable
It is more effectively achieved by using UD P.

  In a conventional IP network, if any node has a minimum requirement of contracting with an IP provider or connecting to a LAN connected to a WAN, it will join the network and It is possible to try cracking. On the other hand, in the symmetric overlay network (SON) in the communication network system according to the present invention, it is possible to eliminate entry of nodes other than previously known nodes by performing appropriate filtering at the entry point. Therefore, the symmetric overlay network (SON) of the present invention has a remarkable effect that it can operate more securely than the conventional IP network.

  The communication network system according to the present invention is multipurpose and general-purpose communication software on a WAN such as the Internet, which is realized by completely separating application functions and network functions. While many other conventional P2P software is application-dependent, the communication network system of the present invention enables remote complex processing functions such as computation processing on any network through any protocol and any application. Provide a general-purpose communication infrastructure. Therefore, the communication network system of the present invention has an excellent effect that various existing communication application protocols can be tunneled.

  Needless to say, the present invention for realizing such a function is the world's first and unique.

  In the communication network system of the present invention, a symmetric overlay network is autonomously constructed, and the symmetric overlay network can be autonomously routed to provide a transport communication layer. In the present invention, a symmetrical overlay network can be used for multiple purposes, and an arbitrary IP application packet can be transmitted and received.

  DESCRIPTION OF EXEMPLARY EMBODIMENTS Hereinafter, preferred embodiments of the invention will be described in detail with reference to the drawings.

  A communication network system according to the present invention constructs a symmetric overlay network having a plurality of nodes on an IP network (preferably, for example, the Internet), so that any of the nodes in the symmetric overlay network is connected. It is a communication network system that enables bidirectional communication via the IP network.

  In the present invention, a symmetric WAN is constructed by overlaying an existing IP network with a transport layer that is as symmetric as an IP network in a LAN environment. The communication network system according to the present invention also provides a transport layer for P2P networking (ie, a symmetric transport layer based on an autonomous overlay network). The greatest feature of the present invention is that a conventional client / server communication protocol is tunneled through a symmetric overlay network (hereinafter also referred to as a P2P overlay network), so that a programming-less symmetric computing environment (hereinafter referred to as a P2P computing network). (Also referred to as a storage environment).

  In the communication network system according to the present invention, WAN symmetry by the P2P overlay network constructed on the IP network is realized as follows.

  First, “symmetry breaking” of an IP network in a WAN can be defined as the following difference. First, in a LAN, node addressability is realized with the entry of a node. Next, in the WAN, even if a node enters the network, it is not always addressable.

  Therefore, when a node is entered, a network in which the node becomes addressable may be realized on the IP network. In general, a network virtually constructed on an existing network is called an “overlay network”. Therefore, the main feature of the present invention is to construct a symmetric overlay network on the IP network.

  In the communication network system according to the present invention, a symmetric overlay network composed of a plurality of nodes is also called SON. In the symmetric overlay network (SON), as an alternative to the IP address, a 128-bit uuid (that is, a universally unique identifier, also referred to as a UUID) is used as the identifier of each node. The uuid is calculated by each node when the node is activated for the first time.

  Specifically, a symmetric overlay network includes a “router node” (hereinafter also referred to as a relay node) that relays a packet, a “leaf node” that does not relay a packet and an application operated by a user, and a new node. Consists of “entry points” that mediate when entering a symmetric overlay network and teach neighboring nodes to be connected.

  In a symmetric overlay network, each node has an identifier. By interpreting the identifier (that is, uuid) as an n-ary number, adjacent nodes to be connected to each other are autonomously determined. In a symmetric overlay network, each node has at least two primary and secondary connections, and when one of the connections is detected, another connection is acquired immediately.

When a new node presents its uuid to a globally addressable node called an “entry point”, the symmetric overlay network (SON) introduces the globally addressable nearest node with the worst 2p-1 hop count, The new node establishes an IP transport connection with the introduced closest node. Here, the equation p = Log _n N holds. Here, N is the total number of nodes in the symmetric overlay network, and n is n in the n-ary classification tree described later.

  TCP, reliable UDP (that is, a mechanism for performing order guarantee and arrival guarantee (retransmission) using UDP), and HTTP are preferably used as candidates for the IP transport connection as a base. Thereafter, the IP transport connection is maintained as a TCP permanent connection or a pseudo connection using a pulse signal over UDP, and all packets to (from) the new node are routed through the IP transport connection. Thus, it is reached from any other node with the worst hop count of 2p-1. Therefore, once a node connects to a symmetric overlay network, it becomes globally addressable via uuid on the symmetric overlay network (SON) even if it is not globally addressable in the IP network.

  As described above, since the connection between nodes is a single IP transport connection, when a node produces / consumes / relays packets of a plurality of communication services, each of those communications is multiplexed. ) Need to be done. The application on the symmetric overlay network (SON) uses a virtual circuit (hereinafter referred to as a channel) provided on the SON as a socket in the IP network. Therefore, in the communication network system according to the present invention, There is no need to be aware of the existence of the multiplexing mechanism.

Next, problems in implementing a symmetrical overlay network (SON) in the present invention and a solution to the problem will be described.
<1> Realization of robustness As described above, the connection between the nodes is a single IP transport connection. However, in this connection, for example, in the connection of node A → node B → node C, node B is removed from the symmetric overlay network. If it leaves, the problem that the packet from the node A to the node C will not reach | attain will arise. Therefore, two connections (for example, not only the connection with the node B but also the connection with the node D) are always established for the relay node from the node A to the arbitrary destination node such as the node C. To do.

At this time, if node B leaves the symmetric overlay network, it is necessary to establish connection with node E in addition to node D immediately. In the present invention, a condition that secures two connections to one node is called a “robustness condition” in a symmetric overlay network (SON). How these relay nodes (for example, node B, node D, and node E) are actually determined will be described later.
<2> Management of Routing Table with Node Entering and Exiting In a symmetric overlay network (SON), nodes are logically connected as an n-ary classification tree. Therefore, the basic number of nodes is n + 1. However, additional connections are required according to the robustness conditions described above.

  In the communication network system according to the present invention, a unique n-ary number (that is, uuid) is assigned as an identifier to a component (that is, a node) of a symmetric overlay network (SON). The symmetric overlay network (SON) uses this n-ary classification tree as a physical connection (permanent connection of TCP or pseudo connection using a pulse signal on UDP) and “partial n-ary” that each node has. It is expressed as “classification tree (ie, routing table)”.

  FIG. 1 is a schematic diagram showing a logical configuration (n-ary classification tree) of a symmetric overlay network of a communication network system according to the present invention. As described above, the logical configuration of the symmetric overlay network according to the present invention is represented by an n-ary classification tree formed by hierarchizing n-ary numbers.

  FIG. 1 shows a ternary classification tree formed by hierarchizing ternary numbers when n is three. In FIG. 1, the numbers in [] are ternary representations of uuid, which is the node identifier, and the root node (node 2100 in this example) is a node that matches all the first digits (that is, a symmetric overlay network). Of all nodes). In addition, the three nodes at level 2 (in this example, node 0002, node 2100, and node 1211) are representative of all nodes whose first digit is 0, 1, and 2, respectively. In other words, in the present invention, the symmetric overlay network is configured as an n-ary classification tree with numerical values equal to the number of levels.

  In the symmetric overlay network of the present invention, any one of the n nodes having the same L-th digit at level L is always a sub-representative for the L-1 representative, and the representative node leaves Becomes a new representative, and satisfies the robustness condition described above by selecting a new representative from among the nodes that he / she knows as the representative. A classification tree that satisfies this robustness condition is called a “classification representative tree”.

  Further, in FIG. 1, all nodes connected to a certain node by solid lines and broken lines are referred to as “adjacent nodes”. A class including an adjacent node is referred to as an “adjacent class”. Furthermore, an upper node and a lower node directly connected by a solid line are said to be “parent-child relationship”. As can be seen from FIG. 1, for example, the parent of the node 1210 is the node 2100. For a classification (also referred to as a class) such as Postfix (tail common part) '* 0', the representative (R) of class '* 0' is node 2100, and the sub-representative (r) of class '* 0' is node 1210. Further, the parent class of the class “* 0” is “*”, and the child classes of the class “* 0” are “* 00”, “* 10”, and “* 20”.

  Packet routing in a symmetric overlay network (SON) is performed by following an n-ary classification tree (in this example, a ternary classification tree) as shown in FIG. Therefore, the unicast communication packet from the node 0020 to the node 0002 reaches the node 0002 via the node 2100 because the node 2100 is the representative node at the level 2 and the level 1 for the node 0020. Broadcast routing is performed on the classification tree by the up * / down * algorithm.

Each node of the symmetric overlay network (SON) distributes and manages a subtree related to a node to which the node is directly connected in the classification representative tree. That is, the routing table in the symmetric overlay network (SON) is a partial n-ary classification tree of the classification representative tree. In the example of FIG. 1, the node 2100 manages a partial ternary classification tree including the node 2100, the node 1211, and the node 0002. In a symmetric overlay network (SON), the entry and exit of a node results in an algorithm in which related nodes autonomously maintain a distributed classification representative (partial) tree while performing the minimum necessary communication with each other. ing.
<3> Avoiding deadlock and circulation in dynamic configuration change (node entry and departure) For example, in a symmetric overlay network that allows node leave / join at an arbitrary timing, the following problem occurs.
(1) The appearance of connection establishment necessary for maintenance of the routing table (classification representative subtree) is not uniform among nodes. That is, with a slight time difference, it may appear unconnected or connected, or it may appear unconnected or disconnected. At this time, if it is attempted to synchronize the recognition of connection establishment / disconnection, a deadlock occurs.
(2) In all communications including the routing table maintenance protocol, the update status of the routing table differs depending on the node with a slight time difference. This causes packet cycling.

  First, in order to avoid deadlock, an implementation method called “delayed connection” is introduced in the present invention. In the programming level, the protocol is implemented without being aware of the time difference, and the packet is transmitted after the communication layer waits for the actual connection. This eliminates the synchronization that causes the deadlock from programming. The actual connection establishment is detected by the communication layer when the socket is accepted in the IP transport layer.

Next, avoidance of packet circulation is performed by each node checking whether or not packet circulation occurs based on its own routing table. When the circulation is detected, the node performs routing using the routing table one version before.
<4> QoS (Quality of Service) problems associated with multiplexing within a single connection As described above, in a symmetric overlay network (SON), a node produces / consumes / relays packets of a plurality of communication services. In that case, each of those communications is multiplexed over one IP transport connection. In general protocols such as Telnet, http, and rfbp (protocols used in virtual network computing), the output per unit time of packets at the client (or server) and the consumption of packets at the server (or client) are equal. .

  However, in some streaming services, output is much higher than consumption. In other words, while the output side writes as much as possible, the consumption side consumes only at a constant rate. When this type of packet flows on a communication path shared by a general protocol, the execution of other services may be hindered, or the streaming service may not be able to continue due to a large amount of general protocol packets being mixed. Happens.

  In the present invention, in order to avoid such a problem, the flow rate of all protocols sharing the communication path is limited so that the packet flows at a level slightly exceeding the lower limit value of the bandwidth required for the streaming service. I am doing so.

  FIG. 2 is a schematic diagram showing a physical configuration of the symmetric overlay network shown in FIG. In FIG. 2, for example, in the case of the node 2220, “class of“ * 20 ”” is referred to as a parent class of “class of“ * 220 ””, as indicated in a frame indicated by an arrow, and “ “Class of“ * 220 ”” is called a child class of “class of“ * 20 ””.

  FIGS. 3A and 3B are schematic diagrams showing entry of nodes into a symmetric overlay network in the present invention. In detail, FIG. 3A is a schematic diagram showing the entry of a node into a symmetric overlay network by a logical configuration. FIG. 3B is a schematic diagram showing the entry of a node into a symmetric overlay network with a physical configuration.

  FIG. 4 is a schematic diagram showing the leaving of a node from the P2P overlay network in the present invention. FIG. 4 shows the physical configuration of the P2P overlay network before the node 2100 leaves and after the node 2100 leaves. FIG. 5 is a schematic diagram showing communication (packet routing) in the present invention.

  FIG. 6A is a configuration diagram of the function (module unit) of the P2P overlay network of the communication network system according to the present invention. Furthermore, FIGS. 6B, 6C, 6D, 6E, 6F, and 6G are schematic diagrams showing the traffic flow of each module unit. 6A to 6G, the arrows in the drawings indicate the traffic flow direction, the letters on the arrows indicate the contents of the traffic, and the alphanumeric characters 6A01 to 6A29 in parentheses on the arrows indicate the traffic order. Show.

  As shown in FIGS. 6A and 6B, the P2P networking protocol module unit 6A1 is executed when a node joins or leaves, and maintains the consistency between the network connection and the routing table held by each node. More specifically, the P2P networking protocol module unit 6A1 receives the network entry request from the application and the notification of the leaving of the adjacent node from the P2P link communication module, and executes the joining protocol and the leaving protocol. Details of the entry protocol and the withdrawal protocol are shown in detail in sequence diagrams of FIGS. 7 and 13 to be described later and flowcharts of algorithms used by them.

  The list of the uuid of the local node and the address of the entry point to be referenced when entering is read from the configuration file. If uuid is not set (at first startup), this process generates uuid and writes it to the configuration file. Messages for entry / exit protocols (hello, welcome, newbee, miss, update) are sent to (or from) other nodes by issuing open / close requests and read / write requests to “P2P Transport Module 6A2”. (Received).

  The P2P networking protocol module unit 6A1 receives adjacent node information and a change request from the “P2P routing table module unit 6A3” in order to construct a message for the entry / exit protocol. In addition, in order to reflect the contents of the message in the routing table, initial information (at the time of new entry), a node addition request, and a complement request are passed. Further, in order to include the IP address of the adjacent node in the welcome message, the IP address is received from “P2P link communication module unit 6A5”.

  Further, in order to send the hello message for the entry protocol to the closest node of the new entry node, the P2P networking protocol module unit 6A1 receives the uuid of the nearest neighbor node from the “P2P routing algorithm module unit 6A4”.

  The P2P networking protocol module unit 6A1 maintains a pseudo connection by TCP / IP connection or UDP / IP which is the basis of P2P communication (this is called “peer” in the present invention), so that the “P2P link communication module unit 6A5” A link creation request, a link accept request, a temporary connection (used for communication with an entry point) link request, and a link disconnection request.

  As shown in FIG. 6A and FIG. 6C, the P2P transport module unit 6A2 enables communication equivalent to tcp / ip and udp / ip (however, unlike IP communication, communication bidirectionality and broadcast also in WAN) / Multicast availability), that is, a function equivalent to socket API. More specifically, the P2P transport module unit 6A2 receives channel open / close requests and read / write requests from the application and the “P2P networking protocol module unit 6A1”, and returns the results. At this time, the data to be written is delimited by a fixed length, headers such as a transmission source uuid and a destination uuid are added, and the packet is passed to the “P2P routing algorithm module unit 6A4”. When reading, the header is removed from the packet and the data is concatenated and returned to the caller.

  When the P2P transport module unit 6A2 is instructed to perform temporary connection communication (performed between the new entry node and the entry point) in the open request, the P2P transport module unit 6A2 sends a temporary connection establishment request to the “P2P link communication module unit 6A5”. put out.

  The P2P transport module unit 6A2 issues a callback execution request to the “callback management / execution module unit 6A6” when a callback process (application) corresponding to the received packet exists.

  As illustrated in FIGS. 6A and 6D, the P2P routing table module unit 6A3 adds and deletes nodes to and from the routing table held by each node. More specifically, the P2P routing table module unit 6A3 receives initial information, a node addition request, and a complement request from the “P2P networking protocol module unit 6A1”, and updates the state of the routing table. Also, adjacent node information and a change request are passed to “P2P networking protocol module unit 6A1”, and routing table information is passed to “P2P routing algorithm module unit 6A4”.

  As shown in FIGS. 6A and 6E, the P2P routing algorithm module unit 6A4 determines a packet relay destination communication channel (peer) and a reception channel. More specifically, the P2P routing algorithm module unit 6A4 sends the transmission request obtained from the “P2P transport module unit 6A2” based on the contents of the routing table information received from the “P2P routing table module unit 6A3” to the “P2P link communication module unit”. 6A5 ". At this time, an appropriate peer is selected by outbound routing. Also, the incoming request obtained from the “P2P link communication module unit 6A5” is passed as an incoming request to the “P2P transport module 6A2” or a transmission request to the “P2P link communication module unit 6A5”. At this time, an appropriate peer or channel is selected by inbound routing.

  As shown in FIGS. 6A and 6F, the P2P link communication module unit 6A5 establishes and disconnects a communication path between nodes. More specifically, the P2P link communication module unit 6A5 sends a link creation request, a link accept request, a provisional connection link request, a link disconnection request from the “P2P networking protocol module unit 6A1” and the “P2P transport module unit 6A2”. A temporary connection establishment request is obtained, and a TCP / IP connection or a pseudo connection (referred to as “peer”) based on UDP / IP, which is the basis of P2P communication, is maintained.

  Since the P2P link communication module unit 6A5 waits for a packet to arrive from peer, it can detect disconnection. When disconnection is detected, a disconnection notice is passed to “P2P networking protocol module unit 6A1”. When a packet is received from the peer, an incoming request is passed to “P2P algorithm module unit 6A4”. Also, a transmission request is received from the “P2P algorithm module unit 6A4”, and data is transmitted to the corresponding peer (using TCP / IP or UDP / IP).

  As shown in FIGS. 6A and 6G, the callback management / execution module unit 6A6 receives a callback registration request from the application and registers it in the management table. Further, the callback management / execution module unit 6A6 receives a callback execution request from the “P2P transport module unit 6A2”, and activates a corresponding callback process in the table.

  FIG. 7 is a sequence diagram showing a networking protocol (node entry) in the P2P overlay network of the communication network system according to the present invention. First, as indicated by an arrow 701 in FIG. 7, the new entry node sends a hello message to the entry point. The hello message includes the uuid of the new entry node (that is, its own node) and the IP address of the new entry node. Next, as indicated by an arrow 702, the entry point uses the routing table information and obtains the uuid of the parent node by the algorithm shown in FIG. Next, as indicated by an arrow 703, if the obtained parent node's uuid is not equal to its own uuid, a hello message is sent to the obtained uuid's node. At this time, the entry point includes the uuid of its own node in the hello message. The node that has received the hello message performs the processing from arrow 702 to arrow 703.

  Next, as indicated by the arrow 704, when the uuid of the parent node obtained by the algorithm shown in FIG. 8 is equal to its own uuid, the node is the parent node of the new entry node. Next, as indicated by arrow 705, the parent node adds a new entry node to the routing table. Next, as indicated by arrow 706, the parent node obtains a list of adjacent classes for the new entry node. Then, as indicated by the arrow 707, the parent node sends a newbee message to the adjacent node of the new entry node. The newbee message includes the uuid of the new entry node and the IP address of the new entry node. Here, the adjacent node means a node that is a representative and a sub representative of the adjacent class.

  Next, as indicated by arrow 708, the parent node sends a welcome message to the entry point. The welcome message includes a list of adjacent classes (obtained from arrow 706) and a list of IP addresses of adjacent nodes (obtained from “P2P link communication module 6A5”). Then, as indicated by an arrow 709, the entry point transfers a welcome message to the new entry node. Next, as indicated by the arrow 712, the new entry node initializes the routing table based on the list of adjacent classes in the welcome message. On the other hand, as indicated by the arrow 710, the adjacent node adds the uuid of the new entry node given by the newbee message to the routing table. Finally, as indicated by arrows 714, 711, and 713, the new entry node, the parent node, and the neighboring nodes other than the parent perform connection updates according to the algorithm shown in FIG.

  FIG. 8 shows a flowchart of the “find parent” function in the networking protocol of the present invention. In FIG. 8, the uuid of the new entry node is 'uuid'. For an arbitrary class C in the routing table to which the new entry node belongs, the parent of the class C is searched as shown in FIG.

  As shown in FIG. 8, first, C postfix and 'uuid' end common length L are obtained (step S801). Then, a child class whose end common part length is longer than L or a parent class equal to L is searched (step S802). If the corresponding class is found (step S803), the found class is set to C (step S804), and the process returns to step S801. On the other hand, if the corresponding class is not found, the representative uuid of C is returned (step S805).

  FIG. 9 shows a flowchart of the “get a list of neighboring classes” function in the networking protocol of the present invention. As shown in FIG. 9, first, an empty result list is prepared (step S901). Then, the class (C) represented by the new entry node is entered in the result list (step S902). Next, it is determined whether or not a parent class of C exists (step S903). If the parent class of C does not exist, the result list is returned and the process ends (step S907). On the other hand, if the parent class of C exists, it is determined whether the secondary representative of C is a new entry node (step S904). If the C sub-representative is not a new entry node, the result list is returned and the process ends (step S907). On the other hand, if the C sub-representative is a new entry node, a child class other than the class represented by the new entry node of the parent class of C is entered in the result list (step S905). Then, the parent class is set to C (step S906), and the process returns to step S903.

  FIG. 10 shows a flowchart of the “add new entry node to routing table” function in the networking protocol of the present invention. The “shortest identifiable tail” that appears in FIG. 10 is a postfix (in this example, “* 0011”) that can be identified in the shortest direction when uuid1 (for example, 10011) and uuid2 (for example, 1101) are present. ('* 1011' from the viewpoint of uuid2).

  As shown in FIG. 10, first, the “find a parent” function is executed, and the obtained representative class is set as C (step S1001). Then, it is determined whether or not a C sub-representative exists (step S1002). If there is a C sub representative, the process ends. On the other hand, if there is no C deputy representative, uuid is set to the C deputy representative (step S1003). Then, a child class of C represented by the representative of C is created, and the shortest distinguishable end part of u representative and 'uuid' of the representative of C is set as the common end part of the new class (step S1004). Next, it is determined whether one of the child classes of C and the end common part length are longer than the shortest distinguishable end part length of the representative uuid and ‘uuid’ of the class (step S1005). If it is long, a copy of C is inserted between C and the child class of C, and the representative uuid of C and the shortest distinguishable end of 'uuid' are set in the copy (step S1006). On the other hand, if one of the child classes of C and the end common part length are not longer than the shortest distinguishable end part length of the representative uuid and 'uuid' of the class, the process ends.

  FIG. 11 shows a flowchart of the “routing table initialization” function of the new entry node in the networking protocol of the present invention. As shown in FIG. 11, first, an empty routing table is prepared (step S1101). Then, it is determined whether or not the adjacent class list is empty (step S1102). If the adjacent class list is empty, the routing table is returned (step S1104), and the process ends. On the other hand, if the adjacent class list is not empty, one that does not overlap with the existing adjacent class is extracted from the adjacent class list, put into the routing table (step S1103), and the process returns to step S1102.

  FIG. 12 shows a flowchart of the “connection update” function in the networking protocol of the present invention. As shown in FIG. 12, first, before and after the update of the routing table is compared, a list of deleted nodes and a list of additional nodes are obtained (step S1201). Then, it is determined whether the list of deleted nodes is empty (step S1202). If the list of deleted nodes is not empty, the node is taken out from the list, the peer is deleted (disconnected) (step S1203), and the process returns to step S1202. On the other hand, if the list of deleted nodes is empty, it is further determined whether or not the list of additional nodes is empty (step S1204). If the list of additional nodes is empty, the process ends. On the other hand, if the list of additional nodes is not empty and the additional node is a new entry node, create a peer by making a new tcp connection (however, if a temporary connection exists, reuse it). If not, accept the tcp connection and create a peer (however, if a temporary connection exists, reuse it) (step S1205), and return to step S1204.

  FIG. 13 is a sequence diagram showing a networking protocol (leave of a node) in the P2P overlay network of the communication network system according to the present invention. First, as shown by an arrow 1301 in FIG. 13, when a node leaves, an adjacent node detects disconnection of a TCP connection or non-arrival of a UDP pulse. Next, as indicated by arrow 1302, the adjacent node deletes the leaving node from the routing table. Then, as indicated by an arrow 1303, a class (that is, a missing class) that is generated as a result of deletion of the leaving node and in which the vice representative is absent is determined. Next, as indicated by an arrow 1304, for each of the missing classes, a miss message is transmitted to the representative node. The miss message includes the postfix of the class in which the defect occurs, the uuid of the detached node, and the uuid of the local node (that is, the originating node).

  Then, as indicated by the arrow 1305, the node that has received the miss message constructs update information according to the algorithm shown in FIG. Next, as indicated by an arrow 1306, the update information is transmitted to the node where the missing class has occurred by an update message. The update message includes a postfix of a class in which a defect occurs, update information, and a list of IP addresses corresponding to uuid included in the update information. Then, as indicated by the arrow 1307, the adjacent node complements the routing table according to the algorithm shown in FIG. 16 based on the update information. Finally, as indicated by arrow 1308, the adjacent node performs connection update according to the algorithm shown in FIG.

  FIG. 14 shows a flowchart of the “delete node from routing table” function in the networking protocol of the present invention. In FIG. 14, the deletion target is uuid_dep, and C is each of all classes in the routing table.

  As shown in FIG. 14, first, it is determined whether uuid_dep is equal to a representative of C (step S1401). If uuid_dep is equal to the representative of C, it is determined whether or not there exists a secondary representative of C (step S1402). If there is a C sub representative, the C sub representative is represented (step S1403). Then, the process proceeds to step S1408. If it is determined in step S1402 that no C sub-representative exists, the representative is first emptied (step S1404). Next, the parent class is requested to delete C (step S1405). Then, the process proceeds to step S1408.

  On the other hand, if it is determined in step S1401 that uuid_dep is not equal to the representative of C, the process proceeds to step S1406. If it is determined in step S1406 that uuid_dep is equal to the C sub representative, the C sub representative is emptied (step S1407). Then, the process proceeds to step S1408.

  Next, it is determined whether there is a representative, no secondary representative, and whether there is a child class (step S1408). If there is a representative, no sub-representation, and there is a child class, a child class representative that is different from the C representative and uuid_dep is selected as the C sub-representative (step S1409).

  The “missing class determination” function in the networking protocol of the present invention is a function of “deleting a leaving node from the routing table” function, and returns a class in which the sub representative remains empty.

  FIG. 15 shows a flowchart of the “construct update information” function in the networking protocol of the present invention. In FIG. 15, a postfix of a class in which a defect occurs is defined as postfix_defect.

  As shown in FIG. 15, first, an empty result list is prepared (step S1501). Next, if there is a leaving node uuid in the routing table, it is deleted by the algorithm shown in FIG. 14 (step S1502). Next, class C whose postfix is postfix_defect is obtained (step S1503). Then, it is determined whether or not the C sub-representative is equal to the uuid of the calling node (step S1504). If the deputy representative of C is equal to the uuid of the originating node, first, if there is no C in the result list, C is entered (step S1505). Next, if there is no class identical to the child class of C in the result list, it is entered (step S1506). Next, it is determined whether or not a parent class of C exists (step S1507). If it is determined that the parent class of C exists, the parent class postfix is set in postfix_defect (step S1507). Then, the process returns to step S1503.

  FIG. 16 shows a flowchart of the “routing table complement” function in the networking protocol of the present invention. As shown in FIG. 16, first, it is determined whether or not the update information is empty (step S1601). If the update information is not empty, one class C that is an element of the update information is extracted (step S1602). Next, it is determined whether or not the class C ′ in the routing table having the same postfix as the C postfix exists (step S1603). If it is determined that C 'exists, the contents of C' are replaced with C (step S1604). Then, the process returns to step S1601. If it is determined in step S1603 that C 'does not exist, C is inserted into the routing table (step S1605). Then, the process returns to step S1601.

  FIG. 17 is a schematic diagram showing packet transmission / reception and routing in the present invention. FIG. 17 shows the flow of data from the data transmission source application to the destination application. The source application creates a channel prior to transmission. The channel has a type (any one of a temporary channel, a unicast channel, and a broadcast channel), a service port number for identifying an application, a bandwidth to be used, and a destination uuid. A temporary channel is a special unicast channel for a new entry node to communicate with an entry point.

  A data structure for managing a connection with an adjacent node that is a packet relay destination (original) is called peer. Peer has uuid and priority bandwidth table of neighboring nodes. The priority bandwidth table manages the bandwidth value for each virtual connection indicated by the uuid of the transmission source node, the uuid of the destination node, and the service port number.

  When the transmission source application writes data, the data is divided into fixed lengths, header information including the transmission source uuid and the destination uuid is added, and a communication packet is constructed. The packet is connected to the peer queue selected by the outbound routing algorithm, and the tcp transmission daemon existing for each peer transmits the packet by TCP / IP or UDP / IP.

  At the receiving node, the peer's tcp receive daemon that the packet arrives on reads the packet and passes it to the inbound routing algorithm. The inbound routing algorithm looks at the header information of the packet and selects the corresponding channel if the node is the destination, or the peer to be relayed otherwise. If peer is selected, the inbound routing algorithm puts the packet in the peer queue.

  If the destination is the local node, the inbound routing algorithm places the packet in the channel queue. If there is no channel corresponding to the service port number, a new channel is created. The callback execution daemon in the channel is activated if the corresponding callback processing is not activated. When the activated callback process (application) attempts to read data for processing, the channel removes the packet from the queue, removes the header, and supplies the data to the application. When a packet is put in the peer queue, bandwidth control is performed according to an algorithm shown in FIGS. 18A, 18B, and 18C described later.

  The “outbound routing” function in the networking protocol of the present invention is as follows. First, if it is a temporary connection packet, the peer is fetched by the destination ip address and the packet is connected to the queue of the peer. Next, in the case of this connection, if the request is a unicast or channel close request, if the peer can be fetched with the destination uuid, the packet is queued to that peer, otherwise, a "unicast relay" is performed and the packet is sent. Connect to the peer queue corresponding to the result. In the case of broadcast, “broadcast relay” is performed, and the packet is obtained and connected to the peer queue corresponding to the obtained result.

  The “inbound routing” function in the networking protocol of the present invention is as follows. First, if it is a temporary connection packet, if there is a channel indicated by the destination uuid, the packet is connected to the queue of that channel, otherwise a channel is created and the packet is connected to the queue of that channel. Next, if it is a broadcast packet of this connection, “broadcast relay” is performed, and if there is a channel indicated by the destination, the packet is connected to the queue for that channel, otherwise a channel is created and the packet is queued for that channel. Connect. If it is a unicast packet of this connection, if the destination uuid is not itself, “unicast relay” is performed, and the packet is obtained and connected to the peer queue corresponding to the result, otherwise the destination uuid indicates If there is a channel, the packet is connected to the queue of that channel, otherwise a channel is created and the packet is connected to the queue of that channel.

  The “broadcast relay” function in the networking protocol of the present invention is as follows. A set of representatives of a parent class of a class represented by the own node and different from the own node is called an up node. A set of child classes that are representative of the self node and that is different from the self node is called a down node set. If the relay source node is an up node, the relay destination is a set of down nodes. If the relay source node is an element of the down node set, the relay destination is an up node and an element node of the down set, and the relay source node is excluded.

  The “unicast relay” function in the networking protocol of the present invention is as follows. First, the class (C) having the maximum common end part length is searched. Next, C's representative is himself, and if there is a child class representative or sub-representative that matches the destination, send it to it. Also, if the representative of C is other than yourself, send it to that representative.

  18A, 18B, and 18C show a flowchart of the “enqueue to peer and bandwidth control” function in the networking protocol of the present invention. As shown in FIGS. 18A, 18B, and 18C, first, it is determined whether or not the bandwidth limit is 0 or less or a temporary connection packet (step S1801). If it is determined that the bandwidth limit is 0 or less or a temporary connection packet, the process proceeds to step S1819 described later. On the other hand, if the bandwidth limit is 0 or less or not a temporary connection packet, a key is created with the source uuid, destination uuid, and service port number in the packet header (step S1802). Next, it is determined whether or not there is an entry that matches the key (step S1803). If there is an entry that matches the key, the process proceeds to step S1808 described later.

  On the other hand, if there is no entry that matches the key, the bandwidth limit of the header is set as the bandwidth limit of the entry, the current time is set as the entry start time, and the entry is registered (step S1804). Then, it is determined whether or not the total bandwidth limit of peer is 0 (step S1805). If it is determined that the total bandwidth limit of the peer is not 0, the process proceeds to step S1807 described later. On the other hand, if the total bandwidth limit of peer is 0, the entry start time is set as the peer start time (step S1806). Then, the bandwidth limit of the header is added to the total bandwidth limit of peer (step S1807). Subsequently, the communication amount (Kbits) of the entry is added by the “data length” value of the header (step S1808). Then, it is determined whether or not it is 3 seconds after the entry start time (step S1809). If it is determined that it is not 3 seconds after the start time of the entry, the process proceeds to step S1811 described later.

  On the other hand, if it is 3 seconds after the start time of the entry, the “current bandwidth” of the entry is set to the entry traffic volume / the elapsed time (seconds) from the entry start time (step S1810). The communication amount (Kbits) of the peer is added by the value of the “data length” in the header (step S1811). Thereafter, it is determined whether or not it is 3 seconds after the peer start time (step S1812). If it is determined that it is not 3 seconds after the peer start time, the process proceeds to step S1814 described later. On the other hand, if it is 3 seconds after the peer start time, the “current bandwidth” of peer is set to the amount of peer traffic divided by the elapsed time (seconds) from the peer start time (step S1813).

  Thereafter, it is determined whether or not the bandwidth limit is greater than 0 (step S1814). If the bandwidth limit is greater than 0, it is further determined whether the current bandwidth of the entry exceeds 120% of the bandwidth limit of the entry (step S1815). If the current bandwidth of the entry does not exceed 120% of the bandwidth limit of the entry, the process proceeds to step S1819 described later. On the other hand, when the current bandwidth of the entry exceeds 120% of the bandwidth limit of the entry, sleep is performed for the number of seconds obtained by dividing the excess bandwidth of the entry by the limit (step S1816). The process moves to step S1801.

  On the other hand, if it is not determined in step S1814 that the bandwidth limit is greater than 0, the value obtained by subtracting the current bandwidth to the entry from the peer current bandwidth is 120, which is the value obtained by subtracting the bandwidth limit of the entry from the peer bandwidth limit. It is determined whether it is less than% (step S1817). If the value obtained by subtracting the current bandwidth of the peer from the current bandwidth of the peer is not less than 120% of the value obtained by subtracting the bandwidth limit of the entry from the bandwidth limit of the peer, the peer is transmitted to the transmission queue (step S1819). On the other hand, if the value obtained by subtracting the current bandwidth of the entry from the peer's current bandwidth is less than 120% of the value obtained by subtracting the bandwidth limit of the entry from the peer's bandwidth limit, the excess bandwidth of the entry can be limited. Sleep for the divided number of seconds (step S1818). Then, the process returns to step S1801.

  In the present invention, the message specifications are as follows. That is, the header of the P2P overlay network of the communication network system according to the present invention includes the type (TMP (temporary connection), BROAD (broadcast), UNI (unicast), CLOSE (channel close request)), data It consists of a length, a remaining data length, a transmission source uuid, a destination uuid, a service port number, a transmission source channel identifier, a destination channel identifier, and a bandwidth limit (lower limit Kbps).

In the communication network system according to the present invention, the existing protocols and technologies that can be used in P2P include the following.
・ Remote desktop (VNC: virtual network computing)
・ IP phone, Internet conference ・ Existing CGI application via http ・ Arbitrary client / server application used in LAN ・ RPC application using xmlrpc / WebService / CORBA / JavaRMI The conventional P2P application “gnutella” Since the new entry node directly connects to the entry point, the load is concentrated on the entry point. In contrast, in the communication network system according to the present invention, load distribution is automatically performed.

The basic services of the P2P overlay network (router) in the communication network system according to the present invention include the following.
(1) Information backup service (representative / deputy representative is the backup destination)
・ Public key (for authentication / encryption communication)
・ Communications statistics ・ Others (file blocks, etc.)
(2) Provision of distributed storage / Save in storage on router having uuid closest to file block identifier (3) Data caching / Cache data in router on path Also, P2P in the communication network system according to the present invention The overlay network has the following characteristics as a multi-hop overlay network.
(1) Easy implementation of anonymization network (for example, onion routing network) (2) Reduction of server load by bucket relay type streaming (3) Easy realization of multicast network (4) Non-voluntarity ( Billing information management based on will independence. (Monitoring the communication flow between adjacent nodes that are anonymously connected)

It is a schematic diagram which shows the logical structure of the P2P overlay network of the communication network system which concerns on this invention. It is a schematic diagram which shows the physical structure of the P2P overlay network of the communication network system which concerns on this invention. It is a schematic diagram showing the entry into the P2P overlay network of a node by a logical configuration. It is a schematic diagram showing a node's entry into the P2P overlay network with a physical configuration. In this invention, it is a schematic diagram showing detachment | leave from a P2P overlay network of a node. In this invention, it is a schematic diagram showing communication (routing of a packet). It is a block diagram of the function (module part) of the P2P overlay network of the communication network system which concerns on this invention. It is a schematic diagram which shows the flow of the traffic of a P2P networking protocol module part. It is a schematic diagram which shows the flow of the traffic of a P2P transport module part. It is a schematic diagram which shows the flow of the traffic of a P2P routing table module part. It is a schematic diagram which shows the flow of the traffic of a P2P routing algorithm module part. It is a schematic diagram which shows the flow of the traffic of a P2P link communication module part. It is a schematic diagram which shows the flow of the traffic of a callback management / execution module part. It is a sequence diagram which shows the networking protocol (node participation) in the P2P overlay network of the communication network system which concerns on this invention. It is a flowchart of the "find a parent" function in the networking protocol of this invention. 6 is a flowchart of a function “get a list of adjacent classes” in the networking protocol of the present invention. It is a flowchart of the "add new entry node to a routing table" function in the networking protocol of this invention. It is a flowchart of the "initialization of a routing table" function in the networking protocol of this invention. It is a flowchart of the "connection update" function in the networking protocol of this invention. It is a sequence diagram which shows the networking protocol (leave of a node) in the P2P overlay network of the communication network system which concerns on this invention. It is a flowchart of the "deletion of a leaving node from the routing table" function in the networking protocol of this invention. It is a flowchart of the "construction of update information" function in the networking protocol of this invention. It is a flowchart of the "routing table complement" function in the networking protocol of this invention. In this invention, it is a schematic diagram which shows transmission / reception and routing of a packet. It is a part of flowchart of the "enqueue and bandwidth control to peer" function in the networking protocol of this invention. It is a part of flowchart of the "enqueue and bandwidth control to peer" function in the networking protocol of this invention. It is a part of flowchart of the "enqueue and bandwidth control to peer" function in the networking protocol of this invention.

Explanation of symbols

6A1 P2P Networking Protocol Module 6A2 P2P Transport Module 6A3 P2P Routing Table Module 6A4 P2P Routing Algorithm Module 6A5 P2P Link Communication Module 6A6 Callback Management / Execution Module

Claims (8)

A communication network system that enables bidirectional communication between any of the nodes in the symmetric overlay network through the IP network by constructing a symmetric overlay network having a plurality of nodes on the IP network. And
In the symmetric overlay network, all nodes are logically connected as an n-ary classification tree, the node has a unique identifier for identifying itself, and the identifier of the node is an n-ary number. By interpreting, adjacent nodes to be connected to each other are autonomously determined, the basic number of connections of the nodes is n + 1, and the nodes are connected by the IP transport layer. A communication network system characterized by the above. 2. The relay node according to claim 1, wherein in the symmetric overlay network, a two-route connection is always established for a relay node from a certain node to an arbitrary node, and the relay node includes a representative node and a sub-representative node. Communication network system. The symmetric overlay network includes a P2P networking protocol module unit, a P2P transport module unit, a P2P routing table module unit, a P2P routing algorithm module unit, a P2P link communication module unit, a callback management / execution module unit, The communication network system according to claim 1 or 2, further comprising: In the symmetric overlay network, each node has at least two primary and secondary connections, and when one of the connections is detected, another connection is immediately acquired. Item 4. The communication network system according to Item 3. In the symmetric overlay network, a “router node” that relays packets, a “leaf node” that does not relay packets and operates an application operated by a user, and a new entry node enters the symmetric overlay network. The communication network system according to any one of claims 1 to 4, further comprising an "entry point" that mediates at that time and teaches an adjacent node to which the new entry node is to be connected. The communication network system according to claim 5, wherein in the overlay network, appropriate filtering is performed at the “entry point” so that entry of nodes other than nodes known in advance can be excluded. When the representative node leaves the symmetric overlay network, the secondary representative node becomes the representative node, and a new secondary representative is selected from the nodes that the node knows as the secondary representative. The communication network system according to claim 2. The communication network system according to claim 1, wherein TCP or reliable UDP is used as the IP transport layer.

Images