Patent ID: 8392607

Claim:
A relay device in a plurality of relay devices including one or more upstream relay devices and one or more downstream relay devices mutually connected through links to compose a communication network, the communication network including a plurality of paths for transmitting communication data through said relay device, said relay device comprising: a memory storing instructions; a processor configured to execute said instructions to perform a method comprising: receiving at least one link status notification message accumulated according to a degree of maintainability of a path, at a time of link disconnecting, at each of a plurality of relay devices located downstream of said relay device and wherein the notification message is forwarded from one of the downstream relay devices; generating a probability value according to a predetermined probability distribution; selecting one of the plurality of paths based on the number of the link status notification messages and the probability value; and relaying the communication data from one of the upstream relay devices to one of the downstream relay devices on the path selected by said selecting, wherein said selecting further includes: calculating an activation level indicating suitability of a selection of a primary path that is currently selected, from the plurality of paths, for transferring the communication data, based on a ratio of (a) the number of link status notification messages received from one of the downstream relay devices on a path on the plurality of paths other than the primary path to (b) the number of link status notification messages received from one of the downstream relay devices on the primary path; and (i) determining a selection frequency value of each of the plurality of paths for determining a selection frequency for the path, wherein the smaller the suitability represented by the activation level calculated by said calculating is, the smaller a difference between a maximum one of the selection frequency values and other selection frequency values becomes, and to (ii) selecting a new path for transmitting the communication data, according to a probability distribution represented by a frequency value obtained by adding the probability value generated by said generating to the determined selection frequency value for each path.