A node device to participate in an overlay network formed by all or a part of a plurality of node devices, mutually connected through a communication network, including: a device information acquisition means for acquiring device information of node devices to which participation request information is to be transmitted; a reachable range setting means for setting up the participation request information, transmitted on the communication network; a participation request information transmission means for adding reachable range to the participation request information and transmitting it to each of the node devices specified by the device information acquired; a reply information receiving means for receiving reply information, transmitted from a node device, and including a transfer destination table for the overlay network; and a transfer destination table generation means for generating the own node device on the basis of the transfer destination table included in the reply information received.