Patent ID: 8395999
Filing Date: 2013-03-12
Classification: H04L

Abstract:
1. A method of detecting a failed link in a network where multiple nodes are connected with one another via inter-node links, wherein the nodes send/receive route-update messages to their neighbors, in accordance with a pre-selected routing protocol, each node sends in a broadcast manner, a route-update message containing a prefix and a unique node number of the each node, each node, upon receiving a route-update message, transfers the received route-update message after adding the unique node number of the each node to a path represented by a sequence of unique node numbers contained in the received route-update message, wherein the path was used for the same route-update message to be transferred to the each node, and one of the nodes is selected as an observer node, and another is selected as a managed node, the method is implemented for the observer node, the method comprising: a first step of determining, for the prefix of the managed node, a single normal-state path which it is in a normal state, out of the paths contained in the received route-update messages containing the same prefix; a second step of determining, for each of the links on the normal-state path determined for the prefix of the managed node, at least one prefix advertised from one of the nodes which is located adjacent to the each link on an upstream side, as at least one monitored prefix, a third step of selecting ones of the received route-update messages which contain the monitored prefixes determined for the nodes; a fourth step of determining, for each of the selected route-update messages, whether the path contained in the each selected route-update message is unmatched with the normal-state path determined for the monitored prefix contained in the each selected route-update message; a fifth step of counting, for each of the monitored links, an unmatched-prefix count which refers to a count of at least one unmatched prefix of the at least one monitored prefix for the each monitored link, a sixth step of extracting at least one link from the monitored links, as at least one failed link, based on a relationship between the unmatched-prefix count and the per-link total monitored-prefix number for the at least one monitored link; and a seventh step of determining, when a count of the extracted at least one failed link is two or more, one of the extracted two or more failed links, which is closer to the observer node on the normal-state path determined for the managed node, than any other failed link or links.