Patent ID: 7769019

Claim:
A system, comprising: an ingress router coupled to the base network, wherein the ingress router maintains a network routing table specifying a plurality of virtual circuits forming an overlay network through a base network; and an egress router coupled to the base network, wherein the egress router gathers information corresponding to a destination local subnet associated with the egress router using a plurality and sends the gathered information to the ingress router for inclusion in the network routing table; wherein the ingress router validates a route through the base network to the destination local subnet listed in the network routing table by: (i) generating a plurality of addresses within the destination local submit, (ii) sending a list of the addresses to the egress router to direct the egress router to monitor for diagnostic probe packets associated with the addresses, (iii) transmitting at least one probe packet to one or more of the addresses, and (iv) receiving confirmation of detection from the egress router, wherein the ingress router selects one of the virtual circuit for transporting a data packet as encapsulated data to the egress router, the selected virtual circuit beginning at the ingress router and ending at the egress router, and wherein the ingress router selects the virtual circuit responsive to the network routing table and a destination of the data packet.