Efficient method and system for automatic discovery and verification of optimal paths through a dynamic multi-point meshed overlay network

In an overlay network, a method for verifying a virtual network routing table comprising the steps of:

• discovering information corresponding to a destination local subnet associated with an egress point;
• maintaining the virtual network routing table at an ingress point responsive to the discovered information;
• and
• selecting a virtual network circuit responsive to the virtual network routing table, the virtual circuit beginning at the ingress point and ending at the egress point.

An overlay network for transporting a data packet through a base network comprising:

• An egress point means for discovering information corresponding to a destination local subnet associated with the egress point means and for transmitting the discovered information to an ingress point means;
• and
• an ingress point means for maintaining a virtual network routing table responsive to the transmitted information;
• and for selecting a virtual network circuit responsive to the virtual network routing table, the virtual network circuit beginning at the ingress point means and ending at the egress point means.

An overlay network for transmitting a data packet throught a base network, comprising:

• an egress point coupled to the base network, configured to forward the data packet to an associated destination local subnet;
• and
• an ingress point coupled to the base network, configured to maintain a virtual network routing table comprising a routing entry corresponding to the destination local subnet;
• to validate the routing entry by sending a probe packet to an address located in the destination local subnet and by receiveing a confirmation from the egress point that the probe packet was detected;
• and to select a virtual network circuit beginning at the ingress point and ending at the egress point responsive to the validated routing entry and the destination of the data packet.

In an overlay network, a method for validating a virtual network routing table comprising the steps of:

• maintaining a virtual network routing table at an ingress point;
• sending a probe packet from the ingress point to an address within a destination local subnet corresponding to an entry in the virtual network routing table;
• confirming detection of the probe packet by an egress point corresponding to the destination local subnet;
• modifying the virtual network routing table responsive to the confirmation to indicate a validated entry;
• and
• selecting a virtual network circuit responsive to the validated entry in the virtual network routing table, the virtual network circuit selected to begin at the ingress point and to end at the egress point.

A system for validating a virtual network routing table in an overlay network comprising:

• an ingress point means for maintaining the virtual network routing table and for sending a probe packet to a network address within a destination local subnet corresponding to a routing entry in the virtual network routing table;
• a egress point means associated with the destination local subnet for confirming detection of the probe packet;
• and
• the ingress point means further configured for modifying the virtual network routing table responsive to the confirmation from the egress point means to indicate a validated routing entry;
• and for selecting a virtual network circuit responsive to the validated routing entry, the virtual network circuit beginning at the ingress point means and ending at the egress point means.