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

• US 20030112809A1
• Filed: 08/23/2002
• Published: 06/19/2003
• Est. Priority Date: 08/24/2001
• Status: Active Grant

• Current Assignee: Juniper Networks Incorporated
• Original Assignee: Juniper Networks Incorporated
• Inventors: Singh, Balraj, Singh, Amit P., Bharali, Anupam A., Batra, Rajiv, Sampat, Manish H.
• Granted Patent: US 7,230,949 B2
• Time in Patent Office: Days
• US Class Current: 370/400
• 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, configured to maintain a virtual network routing table; and

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

the ingress point further configured to select 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 the ingress point selecting the circuit responsive to the virtual network routing table and a destination of the data packet.

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 further comprising a second egress point coupled to the base network configured to gather information corresponding to a second destination local subnet associated with the second egress point, and to send the gathered information to the ingress point for inclusion in the virtual network routing table.

6. The overlay network of claim 1 wherein the egress point is configured to monitor changes to the associated local destination subnet and to transmit updated information corresponding to the associated local destination subnet to the ingress point.

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

8. The overlay network of claim 1 wherein the ingress point is further configured to validate 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.

9. The overlay network of claim 8:

further comprising at least one additional egress point coupled to the base network configured to gather information corresponding to at least one additional destination local subnet associated with the at least one additional egress point, and to send the gathered information to the ingress point for inclusion in the virtual network routing table; and

wherein the virtual network routing table comprises at least one additional listing corresponding to the at least one additional destination local subnet, and the ingress point is further configured to validate the at least one additional entry by sending a 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 probe packet was detected.

10. The overlay network of claim 8 wherein the ingress point is configured to transmit a plurality of probe packets to a plurality addresses located in the destination local subnet.

11. The overlay network of claim 8 wherein the egress point terminates the probe packet when detected.

12. The overlay network of claim 8 wherein the ingress point is configured to re-validated the subnet listed in the virtual network routing table.

13. 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.

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

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

transmitting the summarized information to the ingress point.

15. The method of claim 13 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.

16. The method of claim 13 further comprising the step of discovering information corresponding to a second destination local subnet associated with a second egress point;

and wherein the step of maintaining the virtual network routing table is additionally responsive to information corresponding to the second destination local subnet.

17. The method of claim 13 wherein the step of discovering information comprises the egress point passively monitoring routing a protocol message corresponding to the associated destination local subnet on a base network.

18. The method of claim 13 wherein the step of discovering information comprises the egress point 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.

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

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;

confirming detection of the probe packet by the egress point corresponding to the destination local subnet; and

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

20. The method of claim 19 further 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.

21. The method of claim 19 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 egress point.

22. The method of claim 19:

further comprising the step of discovering an additional information corresponding to an at least one additional destination local subnet associated with an at least one additional egress point;

wherein the step of maintaining the virtual network routing table is further responsive to the additional information;

the virtual network routing table comprises at least one additional destination local subnet entry corresponding to the transmitted additional information; 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 at least one additional destination local subnet entry.

23. 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.

24. The overlay network of claim 23 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.

25. The overlay network of claim 23 wherein:

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

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

26. The overlay network of claim 23 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.

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

28. The overlay network of claim 23 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.

29. The overlay network of claim 23 wherein the ingress point means further comprises:

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

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

30. The overlay network of claim 29 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.

31. The overlay network of claim 29 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.

32. 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.

33. The overlay network of claim 32 further comprising:

at least one additional egress point coupled to the base network and configured to forward the data packet to at least one additional associated destination local subnet; and

wherein the virtual network routing table comprises at least one additional routing entry corresponding to the at least one additional destination local subnet, and the ingress point is further configured to validate 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.

34. The overlay network of claim 32 wherein the ingress point is configured to send multiple probe packets to separate addresses located in the destination local subnet.

35. The overlay network of claim 32 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.

36. The overlay network of claim 32 wherein:

the ingress point is located in a first router; and

the egress point is located in a second router.

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

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

39. The overlay network of claim 32 wherein the ingress point is configured to re-validate the routing entry.

40. 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.

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

42. The method of claim 40 wherein:

the virtual network routing table comprises at least one additional destination local subnet entry; 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 at least one additional destination local subnet entry.

43. The method of claim 40 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.

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

45. 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.

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

47. The system of claim 45 wherein:

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

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.

48. The system of claim 45 wherein the ingress point means further comprises means for sending an at least one additional probe packet to an at least one additional address within the destination local subnet.

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