Patent ID: 7626948

Claim:
An apparatus for verifying a validity of a path, comprising: a network element included in a first autonomous system that: constructs a directed graph comprising a plurality of nodes and a plurality of edges, a node representing an autonomous system, an edge representing a connection between two autonomous systems, the edges marked tentative; receives an advertisement communication from each respective autonomous system within an internetwork, the advertisement comprising a list of all autonomous systems connected to the respective autonomous system; for each advertisement received: determines from the respective received advertisement whether the respective autonomous system claims a connection to any of the other autonomous systems within the internetwork; determines from any other received advertisements whether any of the other autonomous systems within the internetwork claim a connection to the respective autonomous system; for each connection claimed by the respective autonomous system with another autonomous system within the internetwork that is reciprocated by the other autonomous system, establishes that there is two-way connectivity between the two autonomous systems; if there is two-way connectivity between the two autonomous systems, marks the edge representing the connection between the two autonomous systems as verified in the directed graph; and if there is no two-way connectivity between the two autonomous systems, removes the edge representing the connection between the two autonomous systems from the directed graph.