A management device configured to manage an overlay network built on a network, wherein management devices, belonging to the same domain, are configured to function as nodes of the overlay network, and key information for nodes belonging to a particular domain of the plurality of domains in the overlay network is associated with each of the management devices belonging to the same particular domain; the management device comprising: a hash processing unit configured to calculate first key information corresponding to a subject node of the overlay network to which said management device is directly connected; and a communication processing unit configured to acquire, from an initial node that has already participated in the overlay network, an IP address of a second node corresponding to a second key information that is determined by the first key information, that is configured to acquire, by accessing the second node based on the IP address of the second node, an IP address of a third node corresponding to a third key information that is determined by the first key information, that is configured to insert the subject node having the first key information between the second node having the second key information and the third node having the third key information and update the subject node in a routing table, and that is configured to store key information corresponding to a destination node that communicates with the subject node in the overlay network and update the routing table, a node name of the destination node, key information corresponding to a routing node that routs communication of the subject node with the destination node, and an IP address of the routing node; characterized in that: the hash processing unit is further configured to calculate hash values of a host and a guest of a virtual machine running on the subject node, the hash processing unit is configured to register, in a hash table, node names of the host and the guest, and calculated hash values as key information calculated associated with names of said host and guest, the management device further comprises a management target searching unit configured to search an IP address of another management device running on another node belonging to the same domain of the subject node in the overlay network, the management target searching unit being further configured to acquire management information of the overlay network when the another management device is already present at the searching, and the management device further comprises a management information creating unit configured to construct configuration information of the overlay network based on the hash value of the subject node when the another management device is not already present at searching. management devices, belonging to the same domain, are configured to function as nodes of the overlay network, and key information for nodes belonging to a particular domain of the plurality of domains in the overlay network is associated with each of the management devices belonging to the same particular domain; the management device comprising: a hash processing unit configured to calculate first key information corresponding to a subject node of the overlay network to which said management device is directly connected; and a communication processing unit configured to acquire, from an initial node that has already participated in the overlay network, an IP address of a second node corresponding to a second key information that is determined by the first key information, that is configured to acquire, by accessing the second node based on the IP address of the second node, an IP address of a third node corresponding to a third key information that is determined by the first key information, that is configured to insert the subject node having the first key information between the second node having the second key information and the third node having the third key information and update the subject node in a routing table, and that is configured to store key information corresponding to a destination node that communicates with the subject node in the overlay network and update the routing table, a node name of the destination node, key information corresponding to a routing node that routs communication of the subject node with the destination node, and an IP address of the routing node; the hash processing unit is further configured to calculate hash values of a host and a guest of a virtual machine running on the subject node, the hash processing unit is configured to register, in a hash table, node names of the host and the guest, and calculated hash values as key information calculated associated with names of said host and guest, the management device further comprises a management target searching unit configured to search an IP address of another management device running on another node belonging to the same domain of the subject node in the overlay network, the management target searching unit being further configured to acquire management information of the overlay network when the another management device is already present at the searching, and the management device further comprises a management information creating unit configured to construct configuration information of the overlay network based on the hash value of the subject node when the another management device is not already present at searching.