A relay node (203) is a relay node in relay nodes mutually connected through links to compose a communication network, the communication network including paths for transmitting communication data through the relay node (203), including a link status receiving unit (104) which receives at least one link status notification message which is accumulated according to a degree of maintainability of a path, at a time of link disconnecting, at each of the relay devices downstream of the relay device and is forwarded from the downstream relay node (203), a probability generating unit (106) which generates a probability value according to a predetermined probability distribution, a path selection unit (107) which selects one of the paths based on the number of the link status notification message and the probability value, and a relay processing unit (108) which relays the communication data from upstream to a downstream relay device on the path selected by the path selection unit (107).