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

• US 7,230,949 B2
• Filed: 08/23/2002
• Issued: 06/12/2007
• Est. Priority Date: 08/24/2001
• Status: Expired due to Fees

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Singh, Balraj, Singh, Amit P., Bharali, Anupam A., Batra, Rajiv, Sampat, Manish H.
• Primary Examiner(s): PHAM, BRENDA H
• Application Number:
  US10/226,502
• Publication Number:
  US 20030112809A1
• Time in Patent Office: 1,754 Days
• Field of Search: 370/351, 370/386, 370/389, 370/392, 370/397, 370/399, 370/395.3, 370/395.31, 370/395.32, 370/395.53, 370/395.54, 370400-402
• US Class Current: 370/395.2
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/125 based on throughput or bandwidth
• CPC Class Codes: H04L 45/26 Route discovery packet
• CPC Class Codes: H04L 45/64 using an overlay routing layer

Abstract

The present invention provides an efficient system and method for routing information through a dynamic network. The system includes at least one ingress point and one egress point. The ingress and egress point cooperate to form a virtual circuit for routing packets to destination subnets directly reachable by the egress point. The egress point automatically discovers which subnets are directly accessible via its local ports and summarizes this information for the ingress point. The ingress point receives this information, compiles it into a routing table, and verifies that those subnets are best accessed by the egress point. Verification is accomplished by sending probe packets to select addresses on the subnet. Additionally, the egress point may continue to monitor the local topology and incrementally update the information to the ingress to allow the ingress to adjust its compiled routing table.

Claims

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

an ingress point coupled to the base network, wherein the ingress point maintains a virtual network routing table; and

an egress point coupled to the base network, wherein the egress point gathers information corresponding to a destination local subnet associated with the egress point, but not associated with the ingress point, and sends the gathered information to the ingress point for inclusion in the virtual network routing table;

wherein the ingress point further selects a virtual network circuit for transporting the data packet, the virtual network circuit beginning at the ingress point and ending at the egress point, and wherein the ingress point selects the circuit responsive to the virtual network routing table and a destination of the data packet, wherein the ingress point validates a route through the base network to the destination local subnet listed in the virtual network routing table by transmitting a probe packet to an address in the destination local subnet and receiving confirmation of detection from the egress point; and

a second egress point coupled to the base network, wherein the second egress point gathers information corresponding to a second destination local subnet associated with the second egress point, and sends the gathered information to the ingress point for inclusion in the virtual network routing table.

2. The overlay network of claim 1 wherein:

the ingress point comprises a first router; and

the egress point comprises a second router.

3. The overlay network of claim 1 wherein the base network is one of a point-to-point network;

a multi-point network, or a dynamic multi-point network.

4. The overlay network of claim 1 wherein the egress point consolidates the gathered information, to reduce the amount of information to be transmitted to the ingress point.

5. The overlay network of claim 1 wherein the egress point monitors changes to the associated local destination subnet and transmits updated information corresponding to the associated local destination subnet to the ingress point.

6. The overlay network of claim 1 wherein the gathered information includes at least one of a network IP address of the destination, a route mask, a gateway IP address of the next hop router, an interface type, a route type, a route protocol, a route age, or a route cost.

7. The overlay network of claim 1:

wherein the virtual network routing table comprises an entry corresponding to the second destination local subnet, and wherein the ingress point to validates the entry by sending a probe packet to an address located in the second destination local subnet and receiving a confirmation from the second egress point that the probe packet was detected.

8. The overlay network of claim 1 wherein the ingress point transmits a plurality of probe packets to a plurality addresses located in the destination local subnet.

9. The overlay network of claim 1 wherein the egress point terminates the probe packet when detected.

10. The overlay network of claim 1 wherein the ingress point re-validates the subnet listed in the virtual network routing table.

11. 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;

discovering information corresponding to a second destination local subnet associated with a second egress point;

maintaining the virtual network routing table at an ingress point responsive to the discovered information corresponding to the destination local subnet and the discovered information corresponding to the second destination local subnet;

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;

sending a probe packet from the ingress point to an address within the destination local subnet corresponding to a routing entry in the virtual network routing table; and

confirming detection of the probe packet by the respective egress point corresponding to the destination local subnet.

12. The method of claim 11 further comprising the steps of:

consolidating the discovered information to reduce the amount of information; and

transmitting the summarized information to the ingress point.

13. The method of claim 11 further comprising the steps of:

monitoring the destination local subnet for a change at the egress point; and

updating the virtual network routing table responsive to the updated information.

14. The method of claim 11 wherein at least one of the steps of discovering information comprises the egress points passively monitoring a routing a protocol message corresponding to the associated destination local subnet on a base network.

15. The method of claim 11 wherein at least one of the steps of discovering information comprises the respective egress points actively routing data to the associated destination local subnet on a base network and collecting a routing protocol message corresponding to the associated destination local subnet.

16. The method of claim 11 further comprising the step of:

modifying the virtual network routing table responsive to the confirmation to indicate the confirmation of the routing entry.

17. The method of claim 11 wherein the step of sending a probe packet comprises sending an at least one additional probe packet to an at least one additional address within the destination local subnet.

18. The method of claim 11 wherein the step of sending a probe packet comprises sending a probe packet to the address to reconfirm detection of the probe packet by the respective egress point.

19. The method of claim 11:

wherein the virtual network routing table comprises a destination local subnet entry corresponding to the discovered information corresponding to the second destination local subnet; and

the step of sending a probe packet comprises sending an at least one additional probe packet from the ingress point to an address within the second destination local subnet entry.

20. 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;

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.

wherein the egress point means further comprises means for monitoring the destination local subnet for a chance and for transmitting an updated information corresponding to the change to the ingress point means, and

wherein the ingress point means further comprises means for updating the virtual network routing table responsive to the updated information; and

a means for sending a probe packet from the ingress point means to an address within the destination local subnet corresponding to a routing entry in the virtual network routing table;

a means for confirming receipt of the probe packet by the egress point means.

21. The overlay network of claim 20 wherein the egress point means further comprises means for consolidating the discovered information to reduce the amount of information to be transmitted to the ingress point means.

22. The overlay network of claim 20 further comprising:

an at least one additional egress point means for discovering an at least one additional information corresponding to an at least one additional destination local subnet associated with the at least one additional egress point means and for transmitting the at least one additional information to the ingress point means;

wherein the ingress point means additionally maintains the virtual network routing table responsive to the at least one additional destination local subnet.

23. The overlay network of claim 20 wherein the egress point means passively monitors a routing protocol message corresponding to the associated destination local subnet on a base network.

24. The overlay network of claim 20 wherein the egress point means actively routes data to the associated destination local subnet on a base network and collects a routing protocol message corresponding to the associated destination local subnet.

25. The overlay network of claim 20 wherein the ingress point means further comprises:

a means for modifying the virtual network routing table to the confirmation.

26. The overlay network of claim 20 wherein the means for sending a probe packet further comprises means for sending an at least one additional probe packet to an at least one additional address within the destination local subnet.

27. The overlay network of claim 20 wherein the means for sending a probe packet further comprises means for sending a probe packet to the address to reconfirm detection of the probe packet.

28. An overlay network for transmitting a data packet through a base network, comprising:

an egress point coupled to the base network, wherein the egress point forwards the data packet to an associated destination local subnet;

an ingress point coupled to the base network, wherein the ingress point maintains a virtual network routing table comprising a routing entry corresponding to the destination local subnet;

validates the routing entry by sending a probe packet to an address located in the destination local subnet and by receiving a confirmation from the egress point that the probe packet was detected; and

selects 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; and

at least one additional egress point coupled to the base network, wherein the at least one additional egress point forwards the data packet to at least one additional associated destination local subnet,

wherein the virtual network routing table comprises at least one additional routing entry corresponding to the at least one additional destination local subnet, and wherein the ingress point validates the at least one additional routing entry by sending an at least one additional probe packet to an address located in the at least one additional destination local subnet and receiving a confirmation from the at least one additional egress point that the at least one additional probe packet was detected.

29. The overlay network of claim 28 wherein the ingress point sends multiple probe packets to separate addresses located in the destination local subnet.

30. The overlay network of claim 28 wherein the egress point serves the destination local subnet directly and the ingress point does not need to validate the entry associated with the subnet.

31. The overlay network of claim 28 wherein:

the ingress point is located in a first router; and

the egress point is located in a second router.

32. The overlay network of claim 28 wherein the egress point terminates the probe packet when the probe packet is detected by the egress point.

33. The overlay network of claim 32 wherein the egress point allows a subsequent identical probe packet to continue to the destination local subnet address.

34. The overlay network of claim 28 wherein the ingress point re-validates the routing entry.

35. 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;

sending at least one additional probe packet from the ingress point to an address within an additional destination local subnet entry of the virtual network routing table;

confirming detection of the probe packets by respective egress points corresponding to the destination local subnets;

modifying the virtual network routing table responsive to the confirmation to indicate a validated entries;

an

selecting a virtual network circuit for each of the validated entries in the virtual network routing table, the virtual network circuits selected to begin at the ingress point and to end at a respective one of the egress points.

36. The method of claim 35 wherein the step of sending a probe packet comprises sending the probe packet on a base network.

37. The method of claim 35 wherein the step of sending a probe packet comprises sending at least one additional probe packet to at least one additional address within the destination local subnet.

38. The method of claim 35 wherein the step of sending a probe packet comprises sending a probe packet to the address to reconfirm detection of the probe packet.

39. 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;

wherein the ingress point means modifies the virtual network routing table responsive to the confirmation from the egress point means to indicate a validated routing entry; and

selects 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;

wherein the virtual network routing table comprises an at least one additional destination local subnet entry; and

wherein the ingress point means further comprises means for sending an at least one additional probe packet from the ingress point means to an address within the at least one additional destination local subnet entry.

40. The system of claim 39 wherein the ingress point means is further for sending the probe packet on a base network.

41. The system of claim 39 wherein the ingress point means further comprises means for sending a probe packet to the address periodically to reconfirm detection of the probe packet.