Information communication system, information communication method, node device included in information communication system and recording medium recording information process program

A group of nodes mutually connected through a communication route form an information communication system. The nodes include a memory for memorizing node information indicating a candidate node of information transfer destination, a participation request information transfer unit for judging whether node information indicating a node of a transfer destination in response to information of the participation request node is memorized, when participation request information is received, and for transferring the participation request information to the node when the node information is memorized, an existence confirmation information sending unit for judging whether information of other than the transfer destination is memorized when the participation request information is received, and for sending existence confirmation information to the node when the information other than the transfer destination is memorized, and a unit for sending return information to the participation request node device when the existence confirmation information is received.

The entire disclosures of Japanese Patent Application No. 2006-110626 filed on Apr. 13, 2006 including the specification, claims, drawings and summary are incorporated herein by reference in its entirety.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to a peer-to-peer (P2P) type information communication system including a plurality of node devices mutually connected through a network, a method thereof, and the like.

2. Discussion of Related Art

A technology of peer-to-peer has been paid attention recently. With respect to a peer-to-peer type information communication system, in an overlay network logically built using a distributed hash table (hereinafter referred to as DHT), each node device does not necessarily recognize link information (e.g. IP address) to all the node devices participating in the overlay network but retains (memorizes) only link information to a portion of node devices obtained at the time of participation, and data inquiry or the like is made based on such the link information.

In such the overlay network, even in a case where participation and withdrawal (separation) of node devices are often repeated, a load thereto should be appropriately distributed. There is disclosed in “Lightweight Load Balancing for Distributed Hash Table” by Toshio Oka, Hiroyuki Morikawa, Tomonori Aoyama; Technical report of the Institute of Electronics, Information and Communication Engineers Feb. 5, 2004, Vol. 103, No. 650, p. 7-12, that an art of an overlay network wherein load is appropriately distributed even in a case where participation and withdrawal (separation) are often repeated.

SUMMARY OF THE INVENTION

A node device sends a participation request message to a previously recognized contact node when newly participating in an overlay network. By an action of a contact node and other node devices to be described below, there may be a mode that a node device being a sending source of a participation request message (hereinafter referred to as participation request node) acquires link information of the other node device, and creates a DHT routing table.

The contact node returns link information of the other node device registered in the stage of the largest bundle of the DHT routing table when receiving the participation request message from the participation request node. Further, the contact node transfers the participation request message to the other node device in a case where the own node device is not a root node of the participation request node (inherent identification information (node ID) corresponding to the link information being the node device closest to the participation request node). When transferring the participation request message, the contact node sends together with information of the next stage where returning the link information to the participation request node.

The node device receiving thus transferred participation request message sends the link information of the corresponding node device to the participation request node based on information at the stage of returning the link information. Further, in a case where the own node device is not the root node of the participation request node, this node device transfers the participation request message to the other node device. When further transferring the participation request message, the node device has the participation request message transferred sends together with information at the further next stage where link information is returned to the participation request node.

Thus, the node device receiving the participation request message transferred to the root node of the participation request node returns link information at the respective prescribed stages to the participation request node.

The participation request node receiving link information one after another creates a DHT routing table based on the respective link information.

However, when the participation request node creates the routing table according to the above-mentioned procedures, there is a possibility that information of the node device already withdrawing from the overlay network is included in the received link information of the other node devices. Then in a case where information is desired to send to the withdrawn node device or the node device having the node ID close thereto, information transfer may be delayed.

Thus the present invention is provided in view of the above problems, and an object of the present invention is to provide a peer-to-peer type information communication system including plural node devices mutually connected through a communication route and a method thereof, wherein a participation request node can acquire link information of the node device participating in (not withdrawing from) the overlay network.

To solve the above described problem of the present invention, according to the first aspect of the invention, there is provided an information communication system having an overlay network formed by participation of a plurality of node devices, mutually connected through a communication route, a node device included in the plurality of node devices including:

a memory means for memorizing node information indicative of a node device to be a candidate of information transfer destination;

a participation request information transfer means for judging whether or not node information indicative of a node device of a transfer destination in response to node information of the participation request node device is memorized, in a case where a participation request into the overlay network is indicated and participation request information including the node information of the participation request node device requesting participation is received, and for transferring the participation request information to the node device, in a case where the node information indicative of the node device of the transfer destination is memorized;

an existence confirmation information sending means for judging whether or not node information indicative of a node device other than the transfer destination in response to the node information of the participation request node device being a sending source of the participation request information is memorized, in a case where the participation request information is received, and for sending existence confirmation information including the node information of the participation request node device to the node device, in a case where the node information indicative of the node device other than the transfer destination is memorized; and

a return information sending means for sending return information to the participation request node device in a case where the existence confirmation information is received.

According to this, the participation request node can confirm an issue that a node device on a transmission source of return information participates in an overlay network because existence confirmation information sending means of a node device receiving the participation request sends existence confirmation information to other node devices, and a return information sending means of a node device receiving the existence confirmation information sends the return information to the participation request node device (hereafter referred to as participation request node). Therefore, it is possible for the participation request node newly participating in the overlay network can acquire node information (e.g. IP address) being a link information of the node device assuredly participating in the overlay network. The participation request node memorizes each node information into the memory means on the basis of the node information and so on thus acquired.

The node device on the sending source of the existence confirmation information can confirm that another node device exists in a case where the existence confirmation information can be successfully sent, and can confirm that the other node device does not exist in a case where the existence confirmation information can not be successfully sent, wherein operation for confirming the existence is also carried out with efficiency.

DESCRIPTION OF THE PREFERRED EMBODIMENTS

Hereinafter, each designation of numerical reference in the drawings is typically as follows:1: Node device;8: Network;9: Overlay network;11: Control unit;12: Memory unit;13: Buffer memory;14: Decoder;15: Image processing unit;16: Display unit;17: Audio processing unit;18: Speaker;20: Communication unit;21: Input unit;22: Bus; andS: Information communication system.

THE BEST MODE FOR CARRYING OUT THE CLAIMED INVENTION

Hereinafter, embodiments of the present invention will be described in reference of drawings. Here, the embodiments explained below is a case where the present invention is applied to an information communication system using DHT, an IP address as node information, and a node ID as identification information. According to the present embodiment, in the information communication system, a node device (participation request node) newly participating in the overlay network sends a participation message as participation request information to a contact node being an arbitrary node device, and the participation request node creates a DHT routing table by utilizing an existence confirmation message as existence confirmation information and a response message as return information. Here, inventions of information communication system and the like according to the present invention are not limited to the embodiments described below and can be practiced by appropriately modifying within a scope of technical concept of the present invention.

[1. Configuration and the Like of Information Communication System]

First, with reference toFIG. 1, schematic configuration and the like of an information communication system is described.

FIG. 1is a view showing an example of connection status of respective node devices in an information communication system according to the present embodiment.

As shown in lower frame101inFIG. 1, a network (network in the real world)8such as Internet is constructed by an internet exchange (IX)3, internet service providers (ISP)4, digital subscriber line (DSL) providers (or device thereof)5, fiber to the home (FTTH) line provider (or device thereof)6, and communication line (e.g. a phone line or an optical cable)7and the like.

The information communication system S is provided with plural node devices1a,1b,1c. . .1x,1y,1z. . . , which are mutually connected through such the network8, is a peer-to-peer type network system. An inherent manufacturing number and an IP (Internet Protocol) address as information showing the node device (node information in the present invention) are allocated to each of the node devices1a,1b,1c. . .1x,1y,1z. . . . Such manufacturing numbers and IP addresses do not overlap among plural node devices1. Here, in some cases, any one of the node devices1a,1b,1c. . .1x,1y,1z. . . is referred to as a node device1for convenience.

Next, algorithm using a distributed hash table (hereinafter referred to as “DHT”) related to the present embodiment is described.

In the above-mentioned information communication system S, the node devices1should know an IP address as node information with each other when they exchange information with each other.

For example, in a system where contents are shared with each other, there is a simple method that respective node devices1participating in the network8know IP addresses of all the node devices1participating in the network8. However, it is not realistic to memorize IP addresses of all the node devices1when the number of terminals becomes large, tens of thousands or hundreds of thousands. Further, when arbitrary node devices are turned on or turned off, operation becomes difficult because the IP addresses of the arbitrary node devices memorized in the respective node devices1are frequently updated.

Therefore, there is devised a system such that, as to information of a unit of node device1, only IP addresses of necessary minimum node devices1having the information are learned (memorized) among all the node devices1participating in the network8, and as to information in a node device1of which IP address is unknown (not memorized), the information is mutually transferred and delivered among the node devices1.

As an example of such the system, an overlay network9is configured by an algorithm using DHT as shown in an upper frame100ofFIG. 1. In other words, the overlay network9means a network configuring a virtual link formed by use of an existing network8.

In the present embodiment, as a prerequisite for an overlay network9configured by the algorithm using DHT, a node device1allocated to this overlay network9is referred to as a node device1participating in the information communication system S (i.e. participating in the overlay network9). Here, participation into the information communication system S is done when a node device not yet participating (participation request node) sends a participation request information (hereinafter referred to as participation message) to an arbitrary node device1already participating (referred to as contact node). Here, the participation message as the participation request information indicates participation request into the overlay network and includes node information of the participation request node for requesting the participation.

Node IDs (identification information) of the respective node devices1participating in the information communication system S provides unique (inherent) number to respective node devices. The number is required to accommodate a bit number enough to include maximum operation number of node devices. For example, when the number is 128-bit number, the node can operate node devices of units of 2128=340×1036.

More specifically, the node IDs of the respective node devices1are hash values obtained by hashing an inherent value such as IP address or manufacturing number of the respective node devices by a common hash function (hash algorithm), and are distributed and located in one ID space without deviation. Such the node ID obtained (hashed) by a common hash function has a very low possibility of having the same value if the IP address or the manufacturing number differs. Here, detailed explanation is omitted because the hash function is well known. Here, in the present embodiment, a value hashing IP address (global IP address; node information) by a common hash function is referred to as a node ID (GUID (Global Unique Identifier); identification information).

[1.2 Creation of Routing Table]

Next, an example of a method of creating a routing table used in DHT is explained with reference toFIG. 2.FIG. 2is a view showing an example of creating a routing table using DHT.

Because the node IDs provided to respective node devices1are generated by a common hash function, they are considered to be dispersed and located in an identical ring-shaped ID space without large deviation as shown inFIGS. 2(A) to 2(C). In the figures, the node ID is provided at 8 bits and illustrated. A black dot in the figures indicates a node ID, and ID increases counterclockwise.

First, as shown inFIG. 2(A), the ID space is divided into several areas. Although actually the ID space divided into about sixteen areas is often used, the ID space is quadrisected for easy explanation here, and ID is expressed by quaternary number of bit length of 8 bits. A node ID of a node device1N is set to “1023”, and an example of creating a routing table of this node device1N is explained.

When the ID space is quadrisected, it is divided into four areas having different maximum digit, “0XXX”, “1XXX”, “2XXX”, and “3XXX” (X being integer number of 0 to 3, similar to this hereinafter) that are expressed by quaternary number. Because the node ID of the node device1N itself is “1023”, the node device1N is located in the area “1XXX” at the lower left of the figure. The node device1N appropriately selects the node device1located in the area other than the area where the own exists (i.e. the area “1XXX”), and memorizes the IP address of the node ID in the table level1.FIG. 3(A)is an example of the table level1. Since the second column indicates the node device1N itself, the IP address is not necessary to be registered.

Next, as shown inFIG. 2(B), among the areas thus quadrisected by routing, the area where the own exists is further quadrisected into four areas “10XX”, “11XX”, “12XX”, and “13XX”. In a manner similar to the above, the node device1existing in an area other than the area where the own exists is appropriately selected, and the IP address of the node ID is memorized in the table level2.FIG. 3(B)is an example of the table level2. Since the first column indicates the node device1N itself, the IP address is unnecessary to be registered.

Next as shown inFIG. 2(C), among the areas thus quadrisected by the routing, the area where the own exists is further quadrisected into four areas “100X”, “101X”, “102X”, and “103X”. In a manner similar to the above, the node device1existing in an area other than the area where the own exists is appropriately selected, and the IP address of the node ID is memorized in the table level1.FIG. 3(C)is an example of the table level3. Since the third column indicates the node device1N itself, the IP address is not necessary to be registered.

The second column and the fourth column are blank because no node device exists in the area.

In such a way, routing tables are created up to level4as shown inFIG. 3(D)to cover all 8-bit IDs. Blank in the table becomes outstanding as the level increases.

All node devices1respectively create and retain the routing table created in accordance with the above-mentioned methods. Thus, the node device1creates the DHT routing table memorizing the IP address of other node devices1. In this embodiment, the node device1memorizes the IP address as node information, the node ID as identification information, and the area of the node ID space as a region where the identification information belongs, or respective levels and respective columns of DHT, in correspondence with one another. Here, the node device corresponding to the node ID closest to the node ID of the own node device1N is referred to as a root node described below (node device having node ID:1000inFIGS. 2(C) and 3(D)).

Here, the number of levels is determined in response to the number of digits of the node ID, and the attention digit number of respective levels inFIG. 3(D)is determined in response to the base number. Specifically, in a case of 16-digit hexadecimal number, ID is 64 bits and the number of alpha-numeral of attention digits in level16is 0 to f. In explanation of the routing table described below, a portion indicating the attention digit number of the respective levels is also simply called “column” or “column number”.

[2. Configuration and the Like of Node Device]

Next, with reference toFIG. 4, configuration and function of the node device1is explained. Here, the configurations of respective node devices1are the same.FIG. 4is a view showing a schematic configuration example of the node device1.

The respective node devices1are configured by including, as shown inFIG. 4, a control unit11being a computer configured by a CPU having computing function, a RAM for work, a ROM for memorizing various data and programs, or the like; a memory unit12, as a memory means, configured by an HD or the like for memorizing (storing) content data, index information, the above-mentioned DHT, program, or the like (the above-mentioned content data being not stored in some node devices1); a buffer memory13for temporarily storing received content data or the like; a decoder14for decoding (stretching data and the like) encoded video data (image information), audio data (audio information) or the like included in the content data; an image processing unit15for providing a predetermined graphic process to the video data or the like thus decoded and outputting the data as video signal; a display unit16such as CRT or liquid crystal display for displaying image based on the video signal outputted from the image processing unit15; an audio processing unit17for converting the thus decoded audio data into an analog audio signal in use of digital/analog (D/A) conversion, amplifying thus converted signal by an amplifier and outputting the same; a speaker18for outputting the audio signal thus outputted from the audio processing unit17as acoustic wave; a communication unit20for carrying out communication control of information with other node devices1via the network8; and an input unit21(e.g. a keyboard, a mouse, or an operation panel) for receiving instruction from a user and providing the instruction signal corresponding to the instruction to the control unit11, wherein the control unit11, the memory unit12, the buffer memory13, the decoder14, and the communication unit20are mutually connected each other via a bus22.

When CPU in the control unit11executes various programs memorized in the memory unit12or the like, the control unit11entirely controls the node device1. Further, the control unit11carries out a content data registration process or the like according to an instruction signal from the input unit21. The node device1functions as a node device for sending (transferring) information and as a node device for receiving information according to executed programs. Further, the control unit11of the node device1functions as a participation request information transfer means, an existence confirmation information sending means, a return information sending means, and a node information sending means.

[3. Outline of Information Communication System]

Next, outline of the information communication system S of the present embodiment is explained with reference toFIGS. 5 to 7. After participating in the overlay network, one node device receives a response message as return information from the other node device to thereby create the DHT routing table based on information of the node device of response message sending source. In the explanation below, the participation request node is set up to a node Z and an arbitrary node device which already knows the IP address and the node Z first communicates with (hereinafter referred to as contact node) is set up to a node B.

Hereinafter, DHT routing table is also simply referred to as “table”. Further, memory of the node information and the identification information of the other node device is also referred to as “registration”.

FIG. 5is a schematic view showing a flow of respective messages for creating the DHT routing table after the participation request node participates in the information communication system S. The respective views ofFIG. 6are examples of DHT routing tables respectively memorized by the node B, the node E and the node G already participating in the information communication system S.FIG. 7is an example of the DHT routing table created when the node Z receives the return information (response message).

As shown inFIG. 5, when one node device1(node Z) participates in the communication network in the information communication system S, the node Z sends the participation message as participation request information to the node B being a contact node (arrow mark101). Then the node A confirms that the node B exists when the participation message (arrow mark102) is successfully sent. Next, the node B sequentially sends an existence confirmation message as existence confirmation information to the node A, the node E, and the node C that are registered in level1as shown inFIG. 6(A)(arrow marks103,105, and107). Then the node A sends the response message to the node Z (arrow mark104), the node E sends the response message to the node Z, and the node C sends the response message to the node Z (arrow mark108). Here, inFIGS. 6(A) to 6(C), a black triangle mark means that the existence confirmation message is sent to the node device registered in the level thereof, and the node device enclosed by dual squares means that the participation message is to be sent to the node device.

At this time, the node Z can memorize the IP address and the node ID corresponding thereto in association with each other to thereby acquire the IP address of the node A, the node B, the node C, and the node E in the table ofFIG. 7.

Then the node B transfers the participation message to the root node of the node Z, or the node E in this case (arrow mark109). At this time region designation information that the sending destination of the existence confirmation message is the next level2is added to the participation message. Next as shown inFIG. 6(B), the node E sequentially sends the existence confirmation message to the node G, node D, and node F registered in the next level2(arrow marks110,112, and114). Then the node G sends the response message to the node Z (arrow mark111), and the node D sends the response message to the node Z (arrow mark113), and the node F sends the response message to the node Z (arrow mark115).

At this time, the node Z can memorize the IP address and the node ID of the node D, node F, and node C in the table inFIG. 7.

The node E transfers the participation message to the root node of the node Z, node G in this case (arrow mark116). Here the region designation information that the sending destination of the existence confirmation message is the next level3is added to the participation message. Next, the node G sends the existence confirmation message to the node H registered in the next level3(arrow mark117). Then the node H sends the response message to the node Z (arrow mark118). Here since the node G is the root node of the node Z, which has no further transfer destination, the process is finished.

Here the node Z can memorize the IP address and the node ID of the node H in the table ofFIG. 7, and can create the DHT routing table shown inFIG. 7according to the flow mentioned above. Since this table of the node Z is created based on the response message received from the respective existing node devices and the other node device1memorized in the table is withdrawn, the probability of delay in information transfer or sending based on the table becomes low. Therefore, communication efficiency is improved for the information communication system S as a whole.

[3.1 Operation of Information Communication System in the Present Embodiment]

Next, operation of the respective node devices1in the information communication system S of the present embodiment will be described with reference toFIGS. 5 to 10. Processes in the respective node devices1after one node device1(the above-mentioned node Z) participates in the communication network in the information communication system S will be explained with reference to flowcharts ofFIGS. 8 to 10. Here, although the respective processes are explained by taking some node devices1as an example, any node devices1are also processed in similar manner.

(1) Basic Process of Node Device

A basic process of the node device1(node Z) is explained with reference toFIG. 8. The node Z creates and retains (memorizes) a DHT routing table shown inFIG. 7according to the process shown inFIG. 5as mentioned above after participating in a communication network.

When a control unit11of a node Z recognizes that the own node device is powered in by an input unit11or the like, various settings of the node Z are initialized and the basic process starts (Start). Here, it is based on a premise that the node Z retains an IP address of a contact node device1(node B) which the node Z first communicates with when the node Z participates in the communication network.

When the basic process is started, the control unit11sends a participation message designating a level1as region designation information to the contact node (node B) (Step S1). Here, the control unit11of the node Z confirms that the contact node B exists when communication with the contact node B is established for sending the participation message. As shown in Step S32ofFIG. 10described later, information of the node B is enabled to be registered in the table. Next, the control unit11judges whether or not the power is off (Step S2), judges that the power is not off because usually the power is not turned off immediately after the power is turned on (Step S2; NO), and judges whether or not a message (information) is received from other node device1(Step S3). This time, because a response message is received at least from a node A, the control unit11judges that the message is received from the other node device1(node A) (Step S3; YES), and carries out the message receiving process (Step S4). Here, the message receiving process is described later with reference toFIG. 9.

Next, the control unit11registers the node device1(node B) of a sending source of the received message in the table (Step S5). This table registration process is described later with reference toFIG. 10. This time, information of the node A is registered in level1and area of each level attention digit X=0 in the table of the node Z (Refer toFIG. 7).

Next, the control unit11returns to Step S2. In a case where the power is not turned off (Step S2; NO) and the message is not received (Step S3; NO), the control unit11carries out the other process responsive to the input from the input unit21or the like (Step S6). Then the process returns to Step S2. The control unit11of the node Z repeats operations of Steps S2to S5or Steps S2, S3and S6responsive to cases. In a case where the power of the node Z is turned off, the control unit11judges so (Step S2; YES) and finishes the basic process (End).

(2) Message Receiving Process of Node Device

A message receiving process of node Z, node B, node E, node G, and node A is described with reference toFIG. 9.

When a message receiving process (Step S4) in the above-mentioned basic process starts, the control unit11of the node Z starts this message receiving process (Start). Here, explanation is given on a premise that a response message is first received from the node A.

When the message receiving process starts, the control unit11judges whether or not thus received message is a participation message (Step S11). Here, since the received message is the response message, the control unit11judges that the received message is not a participation message (Step S11; NO). Next, the control unit11judges whether or not the received message is an existence confirmation message (Step S12).

Here, since the received message is the response message, the control unit11judges that the received message is not the existence confirmation message (Step S12; NO). Next, the control unit11judges whether or not the received message is the response message (Step S13). Here, the control unit11judges that the received message is the response message (Step S13; YES) and returns to the original process flow (Return).

On the other hand, the message receiving process in a case where the participation message is received from the node Z participating in the communication network, in the contact node B, is described below. The node B memorizes the table shown inFIG. 6(A).

When the control unit11of the node B receives the participation message and the message receiving process (Step S4) in the above-mentioned basic process starts, the control unit11starts this message receiving process (Start). When, in Step S11, the control unit11of the node B judges that the received message is the participation message (Step S11; YES), the control unit11acquires region designation information indicative of level1included in the participation message (Step S14). The control unit11determines the level number1in the table in response to the region designation information of this participation message (Step S15).

Next, the control unit11determines the column number (each level attention digit X) in the table as 0 (Step S16), and pays attention to an area of level1and attention digit X=0 inFIG. 6(A)showing the table of the node B.

The control unit11judges whether or not thus determined column number is not larger than the column number of the entire table (Step S17). Since the determined column number0is not larger than the entire table column number3(Step S17; YES), the control unit11judges whether or not the node device falling into the attention [level number] [column number] is the own node device (Step S18).

Here, since the node device falling into the attention [level number1] [column number0] is not the own node device as shown inFIG. 6(A), the control unit11judges so (Step S18; NO). Next, the control unit11judges whether or not information of the other node device is memorized in the attention [level number] [column number] (Step S19).

Here, since the node device of the node ID [0211] is memorized in [level number1] [column number0], the control unit11judges so (Step S19; YES), creates the existence confirmation message including the IP address of the node Z being a participation message sending source, and sends the existence confirmation message to the node device (node A) of a node ID [0211] memorized in [level number1] [column number0] (Step S20). Here, the message sending process is considered to succeed here.

Next, the control unit11judges whether or not the message sending process succeeds (Step S21), and in this case, since sending process of the existence confirmation message succeeds, the control unit11judges so (Step S21; YES). Next, the control unit11adds 1 to the column number0to make a column number1(Step S22) and returns to Step S17.

Next, going through Step S17; YES, Step S18; NO, Step S19; YES, Step S20, and Step S21; YES, the control unit11sends the existence confirmation message to the node device (node E) of the node ID [1221] memorized in [level number1] [column number1], adds 1 to the column number1to make a column number2(Step S23) and returns to Step S17.

Next, going through Step S17; YES, the control unit11judges the area of [level number1] [column number2] is the own node device in Step S18(Step S19; YES), adds 1 to the column number2to make a column number3(Step S22), and returns to Step S17.

Next, going through Step S17; YES, Step S18; NO, Step S19; YES, Step S20, and Step S21; YES, the control unit11sends the existence confirmation message to the node device (node C) of the node ID [3121] memorized in [level number1] [column number3], adds 1 to the column number3to make a column number4(Step S22), and returns to Step S17.

Here, the control unit11judges whether or not the determined column number is not larger than the column number of the entire table (Step S17), and since the determined column number4is not larger than the column number3of the entire table (Step S17; NO), the control unit11recognizes the node device of the participation message transfer destination (sending destination) (Step S23). Here, as explained with reference toFIG. 2, since the node device closest to the node ID [1013] of the node Z being the participation request node is the node E of the node ID [1221], the node E is recognized as transfer destination of the participation message.

Next, the control unit11judges whether or not the own node device is the node device which is the closest to the node ID [1013] of the root node, or the node Z being the participation request node (Step S24). As mentioned above, here, the node device closest to the node ID [1013] of the node Z being the participation request node is the node E having the node ID [1221], and the own node device is not the root node. Therefore, the control unit11judges so (Step S24; NO), and creates the participation message which is added with level number information adding 1 to the attention level number as the region designation information and transfers to the transfer destination recognized in Step S24(Step S25), and returns to the original process flow (Return). Here, the control unit11adds the region designation information of level number2where 1 is added to the attention level number being 1, to the participation message, transfers to the node E, and returns to the original flow.

Next, in the node E, the participation message is transferred from the node B, and the message receiving process when the message is received is described below. The node E is assumed to memorize the table shown inFIG. 6(B).

When the control unit11of the node E receives the participation message and the message receiving process (Step S4) in the above-mentioned basic process starts, the control unit11starts this message receiving process (Start). In Step S1, when the control unit11of the node E judges that thus received message is the participation message (Step S11; YES), it acquires the region designation information indicative of level2included in the participation message (Step S14). The control unit11determines the level number in the table as level number2in response to the region designation information of this participation message (Step S15).

Next, the control unit11determines the column number (each level attention digit X) in the table as 0 (Step S16) and notices the area of level2, attention digit X=0 inFIG. 6(B)showing the table of the node E. The control unit11judges whether or not the determined column number is smaller than the column number of the entire table (Step S17). Since the determined column number0is smaller than the column number3of the entire table (Step S17; YES), the control unit11judges whether or not the node device corresponding to the attention [level number] [column number] is the own node device (Step S18).

Here, since the node device corresponding to the attention [level number2] [column number0] is not the own node device as shown inFIG. 6(B), the control unit11judges so (Step S18; NO), and then judges whether or not information of the other node device is memorized in the attention [level number] [column number] (Step S19).

Here, since the node device of the node ID [1023] is memorized in [level number2] [column number0], the control unit11judges so (Step S19; YES), creates the existence confirmation message including the IP address of the node Z being the participation request node, and sends the message to the node device (node G) of the node ID [1023] memorized in [level number2] [column number0] (Step S20). Here the message sending process is considered to succeed.

Next, the control unit11judges whether or not the message sending process succeeds (Step S21). Here since the message sending process of the existence confirmation message succeeds, the control unit11judges so (Step S21; YES). Next, the control unit11adds 1 to the value of the column number0to make the column number1(Step S22) and returns to Step S17.

Next, the control unit11goes through Step S17; YES, Step S18; NO, Step S19; YES, Step S20, and Step S21; YES, sends the existence confirmation message to the node device (node D) of the node ID [1120] memorized in [level number2] [column number1], adds 1 to the value of the column number1to make the column number2(Step S22), and returns to Step S17.

Next, the control unit11goes through Step S17; YES, judges that the area of [level number2] [column number2] is the own node device in Step S18(Step S18; YES), adds 1 to the value of column number2to make the column number3(Step S22), and returns to Step S17.

Next, the control unit11goes through Step S17; YES, Step S18; NO, Step S19; YES, Step S20, and Step S21; YES, sends the existence confirmation message to the node device (node F) of the node ID [1323] memorized in [level number2] [column number3], adds 1 to the value of the column number3to make the column number4(Step S22), and returns to Step S17.

Here, the control unit11judges whether or not the determined column number is smaller than the column number of the entire table (Step S17). Since the determined column number4is not smaller than the column number3of the entire table (Step S17; NO), the control unit11recognizes the node device of the participation message transfer destination (sending destination) (Step S23). At this time, since the node device which is the closest to the node ID [1013] of the node Z being the participation request node is the node G of the node ID [1023], the control unit11recognizes the node G as the participation message transfer destination.

Next, the control unit11judges whether or not the own node device is the node device which is the closest to the node ID [1013] of the node Z being the root node or the participation request node (Step S24). As mentioned above, here, since the node device closest to the node ID [1013] of the node Z being the participation request node is the node G of the node ID [1023] and the own node device is not the root node, the control unit11judges so (Step S24; NO), and creates the participation message added with information of level number where 1 is added to the attention level number, as region designation information. The control unit11transfers to the other node recognized as a transfer destination (Step S25) and returns to the original process flow (Return). Here, the attention level number is 2, and the control unit11adds the region designation information of level number3where 1 is added to the level number2, to the participation message. The control unit11sends it to the node G of the transfer destination and returns to the original process flow.

Here, in a case where the message sending process is failed in Step S20, the control unit11judges that the message sending process does not succeed in Step S21(Step S21; NO), deletes information such as IP address of the node device1of the corresponding [level number] [column number] from the table (Step S26), and returns to Step S22.

Next, in the node G, the participation message is transferred from the node E, and the message receiving process in a case where the message is received is described hereinafter. The node G is assumed to memorize the table shown inFIG. 6(C).

When the control unit11of the node G receives the participation message and the message receiving process in the above-mentioned basic process starts (Step S4), the control unit11starts this message receiving process (Start). In Step S11, when the control unit11of the node G judges that thus received message is the participation message (Step S11; YES), it acquires the region designation information indicative of level3included in the participation message (Step S14). The control unit11determines the level number in the table as level number3in response to the region designation information of the participation message (Step S15).

Next, the control unit11determines the column number (each level attention digit X) in the table as 0 (Step S16) and notices the area of level3, attention digit X=0 inFIG. 6(C), which is indicative of the table of the node G. The control unit11judges whether or not thus determined column number is smaller than the column number of the entire table (Step S17). Since the determined column number0is smaller than the column number3of the entire table (Step S17; YES), the control unit11judges whether or not the node device corresponding to the attention [level number] [column number] is the own node device (Step S18).

Here, since the node device corresponding to the attention [level number3] [column number0] is not the own node device as shown inFIG. 6(C), the control unit11judges so (Step S18; NO), and then judges whether or not information of the other node device is memorized in the attention [level number] [column number] (Step S19).

Here, since the other node device is not memorized in [level number3] [column number0], the control unit11judges so (Step S19; NO), the control unit11skips this area, adds 1 to the value of the column number0to make the column number1(Step S22), and returns to Step S17.

Next, the control unit11goes through Step S17; YES, Step S18; NO, and Step S19; NO, and since the other node device is not memorized in [level number3] [column number1], the control unit11skips this area, adds 1 to the value of the column number1to make the column number2(Step S22), and returns to Step S17.

Next, the control unit11goes through Step S17; YES, judges that the area of [level number2] [column number2] is the own node device in Step S18(Step S18; YES), adds 1 to the value of the column number2to make the column number3(Step S22), and returns to Step S17.

Next, the control unit11goes through Step S17; YES, Step S18; NO, Step S19; YES, Step S20, and Step S21; YES, sends the existence confirmation message to the node device (node H) having the node ID [1032] memorized in the [level number2] [column number3], adds 1 to the value of the column number3to make the column number4(Step S22), and returns to Step S17.

Here, the control unit11judges whether or not the determined column number is smaller than the column number of the entire table (Step S17), and since the determined column number4is not smaller than the column number3of the entire table (Step S17; NO), the control unit11recognizes the node device of the participation message transfer destination (sending destination) (Step S23). At this time, since the node device which is the closest to the node ID [1013] of the node Z being the participation request node is the own node device (node G) having the node ID [1023], the control unit11recognizes the node G as the participation message transfer destination.

Next, the control unit11judges whether or not the own node device is the node device which is the closest to the node ID [1013] of the node Z being the root node or the participation request node (Step S24). As mentioned above, since the own node device (node G) is the root node here, the control unit11judges so (Step S24; YES), and returns to the original process flow (Return).

Thus, the existence confirmation message sending process for creating the DHT routing table of the node Z being the participation request node and the participation message transfer process are finished.

Meanwhile, the message receiving process when the node A receives the existence confirmation message sent from the contact node B is described below.

When the control unit11of the node A receives the existence confirmation message and the message receiving process in the above-mentioned basic process starts (Step S4), the control unit11starts this message receiving process starts (Start). Here, it is premised that the existence confirmation message is received from the node B.

When the message receiving process starts, the control unit11judges whether or not thus received message is the participation message (Step S11). Here, since the received message is the existence confirmation message, the control unit11judges that the received message is not the participation message (Step S11; NO), and then judges whether or not the received message is the existence confirmation message (Step S12).

The control unit11judges that the received message is the existence confirmation message (Step S12; YES), acquires the IP address of the node Z being the participation request node which is added to the existence confirmation message, sends the response message to the node Z (Step S27), and returned to the original process flow (Return).

Besides, in a case where the message received by the node device1is not either of the participation message, the existence confirmation message, and the response message, the control unit11judges as Step S11; NO, Step S12; NO, and Step S13; NO, carries out the process in the case of receiving the other message (Step S30), and returns to the original process flow (Return).

(3) Process of Registering Other Node Device in Table in Node Device

The registration process of the other node device1in the node Z will be described with reference toFIG. 10and the aboveFIG. 7. Here the registration process of the other node device1is explained under the assumption that the node Z receives a response message from the node A.

When the registration process of the other node device1in the above-mentioned basic process starts (Step S5), the control unit11of the node Z starts the table registration process of the node A (Start).

When the table registration process starts, the control unit11acquires information, specifically information such as IP address of the node A being the sending source node device, from the received response message (Step S31). Next, the control unit11recognizes the area to be registered in the table from thus acquired IP address, registers (Step S32), and returns to the original process flow (Return). Since the node A has the node ID [0211] as shown inFIG. 6(A), the area to be registered is level1, each level attention digit X=0 inFIG. 7. The control unit11of the node Z registers the information of the node A in the area of the table level1, each level attention digit X=0.

Meanwhile, subsequently the node Z receives the response message from one after another, the node E, the node C, the node G, the node D, the node F, and the node H. The control unit11registers information of each node device1in the table in response to the response messages from these node devices through the above-mentioned Steps S31and S32, creates and memorizes the DHT routing table shown inFIG. 7. Further, the node Z may confirm that the other node device1exists and register information of the other node device1in the table when communication with the other node device1is established, as the participation message is sent to the above-mentioned node B.

In the above-mentioned embodiments, the memory unit12of the node device1memorizes IP address and the node ID of the other node device1in correspondence with the DHT routing table. However, the configuration is not limited thereto. The node device1may memorize the node information indicative of a node device1being a candidate of the transfer destination of at least information.

However, the memory unit12as a memory means of the node device1preferably memorizes the node information and the identification information inherent to the node information, in correspondence with every region where the identification information belongs as the DHT routing table is. In such the case, the participation request node acquires the node information of the respective node devices belonging to respective regions of identification information appropriate to the identification information, by using the above-mentioned region designation information, and is able to memorize while maintaining a good balance. Further, it is preferable that the identification information region is divided into plural regions in conformity with rules of the identification information as the DHT routing table is, and the region the own node device belongs to is further divided into plural regions in conformity with rules of the identification information up to the stage where a region only own node device belongs to exists.

Here, the node information may include the port number or the like besides the IP address and is not especially limited. The identification information is not limited to the node ID but may be other identification information inherent to the node information.

In the above-mentioned embodiment, the control unit11of the node device1judges whether or not the node device1of transfer destination is memorized in a case where the control unit11of the node device1receives the participation message. In a case where it is memorized, the control unit11transfers the participation message to the node device1(Steps S23, S24; NO, S25). However, the configuration is not limited thereto. The control unit11as a participation request information transfer means of the node device1indicates a request of participation into the overlay network. In a case where the participation request information including the node information of the participation request node requesting for participation is received, the control unit11judges whether or not the node information indicating the node device of the transfer destination in response to the node information of the participation request node is memorized. In a case where the node information indicating the node device of the transfer destination is memorized, the participation request information may be transferred to the node device.

In the above-mentioned embodiment, the control unit11of the node device1sends the existence confirmation message to the node device1registered in one level of the table (Refer to black triangle marks inFIGS. 6(A) to 6(C)). However, the configuration is not limited thereto. The control unit11of the node device1as an existence confirmation information sending means judges whether or not the node information indicative of the node device other than transfer destination in response to the node information of the participation request node device is memorized. In a case where the node information indicative of the node device other than the transfer destination is memorized, the control unit11may send the existence confirmation message including the node information of the participation request node to the node device. More specifically, the control unit11may send the existence confirmation message to the node device1registered at plural levels. Or the control unit11may send the existence confirmation message to the arbitrarily selective node device1registered. Further, when the control unit11sends the existence confirmation message to the node device1other than the above-mentioned transfer destination, the control unit11may send the existence confirmation message to the node device1of the transfer destination in response to the node information of the participation request node device1.

In the above-mentioned embodiment, the control unit11of the node device1sends region designation information being level number information in the DHT routing table (Steps S1and S25), when initially sending the participation message or transferring the participation message. However, the configuration is not limited thereto. The control unit11of the node device1as a participation request information transfer means may add region designation information designating the prescribed region in the memory means, to the participation request information, when transferring the participation request information. The region designation information is not limited to the level number information. In a case where the region designation information is used, the control unit11as an existence confirmation information sending means sends the existence confirmation information in response to contents of region designation information or whether or not the region designation information is added to the received participation request information (Steps S14and S15), in a case where node information of the other node device being sending destination is memorized.

Further, as in the above-mentioned embodiment, it is preferable that the control unit11as an existence confirmation information sending means sends the existence confirmation information to the other node device belonging to the region corresponding to the region designation information of the memorized identification information, in a case where the region designation information is added to the received participation request information (Steps S14, S15, and S20). Here, it is preferable that the control unit11as an existence confirmation information sending means sends the existence confirmation information to the other node device belonging to the largest region (level1in the above-mentioned embodiment) of the memorized identification information (Step S20), in a case where the participation node does not use the region designation information or the received participation request information is not added to the region designation information. Here, the control unit11as participation request information transfer means adds the region designation information designating the region in response to the smaller scope than the identification information corresponding to the region designation information, to the participation request information (Steps S14, S15, and S25), in a case where the region designation information is added to the received participation request information. Further, the control unit11as participation request information transfer means adds the region designation information designating the next step region (level2in the above-mentioned embodiment) of the largest region (level1in the above-mentioned embodiment) of the identification information, to the participation request information (Step S25), in a case where the region designation information is not added to the received participation request information.

The information communication system or the like according to the present invention can carry out a participation request information transfer process, an existence confirmation information sending process, and a return information sending process without using the above-mentioned region designation information.

In the above-mentioned embodiment, operations of the respective node devices and the entire system in a case where the node device1participates in the information communication system S are not limited to the explanation with reference toFIGS. 8 to 10. The node device1causing the participation request information transfer means to function by the operations of Steps S23, S24, and S25may further send the node information of the node device1being the sending destination of the existence confirmation message, to the participation request node. This operation is carried out by the control unit11as a node information sending means. Here, it is possible for the participation request node to acquire node information of the other node device from two units of node devices, thereby enabling to memorize more accurate DHT routing table.

In the above-mentioned embodiment, the node A or the like receiving the existence confirmation message sends the response message to the participation request node (node Z). However, the configuration is not limited thereto. The control unit11of the node device1as a return information sending means may send the return information to the participation request node in a case where at least existence confirmation information is received. For example, the control unit11of the node device1as a return information sending means may further send the return information to the participation request node in a case where the participation request information is received.

Further, a program corresponding to each operation of the above-mentioned node device1may be recorded in the information recording medium such as flexible disk or hard disk, or acquired and recorded through a network such as internet, and read out by a microcomputer or the like for execution, so that the microcomputer can function as the control unit11related to the respective embodiments.