Routing information exchange

• US 7,080,161 B2
• Filed: 07/10/2001
• Issued: 07/18/2006
• Est. Priority Date: 10/17/2000
• Status: Expired due to Term

• Current Assignee: Avaya Incorporated
• Original Assignee: Avaya Technology Corporation Miami Lakes FLA US
• Inventors: Madan, Herbert S., Baldonado, Omar C., McGuire, James G., Finn, Sean P., Lloyd, Michael A., Leddy, John G.
• Primary Examiner(s): VU, THONG H
• Application Number:
  US09/903,441
• Publication Number:
  US 20020184393A1
• Time in Patent Office: 1,834 Days
• Field of Search: 709/225, 709/238, 709/246, 709/219, 709/220, 709/239, 709/250, 370/397, 370/392, 370/351, 370/422, 370/463, 340/825, 379/219, 710/316, 375/219, 703 23- 28
• US Class Current: 709/250
• CPC Class Codes: H04L 43/00 Arrangements for monitoring or testing data switching networks
• CPC Class Codes: H04L 43/0829 Packet loss
• CPC Class Codes: H04L 43/0852 Delays
• CPC Class Codes: H04L 43/087 Jitter
• CPC Class Codes: H04L 43/16 Threshold monitoring
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/026 Details of "hello" or keep-alive messages
• CPC Class Codes: H04L 45/033 by updating distance vector protocols
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/123 Evaluation of link metrics techniques for monitoring network metrics H04L43/08
• CPC Class Codes: H04L 45/124 using a combination of metrics
• CPC Class Codes: H04L 45/22 Alternate routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 45/64 using an overlay routing layer
• CPC Class Codes: H04L 45/70 Routing based on monitoring results
• CPC Class Codes: H04L 47/10 Flow control; Congestion control
• CPC Class Codes: H04L 47/11 Identifying congestion
• CPC Class Codes: H04L 47/20 Traffic policing
• CPC Class Codes: H04L 47/283 in response to processing delays, e.g. caused by jitter or round trip time [RTT]

Abstract

Network architectures and protocols to support enhancements to the decision making process of standard routing protocols are described. Embodiments allow decisions to be exchanged between networks, or autonomous systems, about which internetwork paths have been chosen for outbound traffic. Some embodiments of the invention allow information about the measured performance of internetwork paths to be exchanged between autonomous systems. Embodiments allow additional policy information to be communicated between networks, including but not limited to information about why local policy decisions have been made; requests of policies from remote networks; performance information about particular paths; and informational status. Such information may be exchanged dynamically between networks.

Claims

1. In an internetwork comprising a plurality of coupled autonomous systems, wherein the plurality of coupled autonomous systems communicate routing information via a Border Gateway Protocol (BGP), and the internetwork includes a routing overlay network to communicate routing parameters between the plurality of coupled autonomous systems, a BGP update message comprising:

a Network Layer Reachability Information (NLRI) field, the NLRI field including;

a first network prefix; and

a first network mask;

an origin attribute, the origin attribute including an identifier for the routing overlay network; and

a first community attribute, the first community attribute including;

an identifier for a private autonomous system from the plurality of autonomous systems.

2. The BGP update message of claim 1, wherein the BGP update message is transmitted from the routing overlay network to one or more points of presence in the plurality of coupled autonomous systems.

3. The BGP update message of claim 1, wherein the first network prefix and the first network mask comprise a first classless address, the first classless address identifying a first internetwork destination.

4. The BGP update message of claim 3, wherein the first classless address is a member of an equivalence class of addresses, the equivalence class including a plurality of classless network addresses, wherein the plurality of classless network addresses are in geographical proximity.

5. The BGP update message of claim 3, wherein the first classless address is a member of an equivalence class of addresses, the equivalence class including a plurality of classless network addresses, wherein the plurality of classless network addresses have jitter statistics within a pre-defined threshold.

6. The BGP update message of claim 3, wherein the first classless address is a member of an equivalence class of addresses, the equivalence class including a plurality of classless network addresses, wherein the plurality of classless network addresses have packet loss statistics within a pre-defined threshold.

7. The BGP update message of claim 3, wherein the first classless address is a member of an equivalence class of addresses, the equivalence class including a plurality of classless network addresses, wherein the plurality of classless network addresses have packet delay statistics within a predefined threshold.

8. The BGP update message of claim 3, wherein the first classless address is a member of an equivalence class of addresses, the equivalence class including a plurality of classless network addresses, wherein the plurality of classless network addresses have similar jitter, delay, and loss statistics within a pre-determined threshold.

9. The BGP update message of claim 8, wherein the equivalence class includes a second classless address, the second classless address including:

a second network prefix; and

a second network mask.

10. The BGP update message of claim 9, wherein the second classless address identifies a second internetwork destination.

11. The BGP update message of claim 10, further comprising:

a second community attribute, the second community attribute including;

the identifier for the private autonomous system; and

a scalar identifier for the equivalence class.

12. The BGP update message of claim 11, wherein the identifier for the routing overlay network is 65534.

13. The BGP update message of claim 12, wherein the identifier for the private autonomous system has the value 65001.

14. In an internetwork comprising a plurality of coupled autonomous systems, wherein the plurality of coupled autonomous systems communicate routing information via a Border Gateway Protocol (BGP), and the internetwork includes a routing overlay network to communicate routing parameters between the plurality of coupled autonomous systems, a method of identifying a classless network address as a member of an equivalence class, the equivalence class comprising a plurality of classless addresses, wherein a route for the classless address has already been advertised to the plurality of coupled autonomous systems, the method comprising:

generating a BGP update message, the BGP update message including;

a destination network for the classless address;

a network mask for the classless address;

an Autonomous System (AS) Path attribute, the AS Path attribute having a value of the route for the network destination; and

a first community attribute, the community attribute including;

an identifier for a private autonomous system from the plurality of coupled autonomous systems; and

forwarding the BGP update message from the routing overlay network to the plurality of coupled autonomous systems.

15. The method of claim 14, wherein the first community attribute is a scalar with a value 65001.

16. The method of claim 15, wherein the first community attribute further includes a value 0.

17. The method of claim 14, wherein the plurality of classless addresses in the equivalence class have similar network performance characteristics.

18. The method of claim 17, wherein the plurality of classless addresses are in geographic proximity.

19. The method of claim 17, wherein the similar network performance characteristics include one or more of delay statistics, jitter statistics, and loss statistics.

20. The method of claim 17, wherein the BGP update message further includes a second community attribute, the second community attribute including:

the scalar with the value 65001; and

a unique scalar identifier for the equivalence class.

21. In an internetwork comprising a plurality of coupled autonomous systems, wherein the plurality of coupled autonomous systems communicate routing information via a Border Gateway Protocol (BGP) and the internetwork includes a routing overlay network to communicate routing parameters between the plurality of coupled autonomous systems, a method of communicating network performance parameters for a route in the internetwork, the method comprising:

advertising a BGP update message from a point of presence in the internetwork to the routing overlay network; and

prior to advertising the BGP update message, generating the BGP update message, the BGP update message including;

a classless address for a network destination of the route, the classless address further including;

an identifier for the network destination; and

a mask for the network destination;

an autonomous system path attribute, indicating a chain of autonomous systems from the plurality of coupled autonomous systems traversed by the route; and

a community string including;

a first hop autonomous system indicating an ISP coupled to the point of presence; and

one or more value pairs including;

a type, indicating a type of performance measurement of the route; and

an argument, indicating a value of the performance measurement of the route.

22. The method of claim 21, wherein the one or more value pairs includes a value pair indicating jitter measurements for the route, such that the type identifies the jitter measurement as jitter for the route, and the argument indicates the value for the jitter.

23. The method of claim 21, wherein the one or more value pairs includes a value pair indicating packet drop measurement for the route, such that the type identifies the measurement as packet drop for the route, and the argument indicates the value for the packet drop.

24. The method of claim 21, wherein the one or more value pairs includes a value pair indicating delay measurement for the route, such that the type identifies the measurement as delay for the route, and the argument indicates the value for the delay as delay.

25. The method of claim 21, wherein the autonomous path attribute includes an identifier for the routing overlay network.

26. The method of claim 25, wherein the identifier for the routing overlay network is 65534.

27. In an internetwork comprising a plurality of coupled autonomous systems, wherein the plurality of coupled autonomous systems (ASs) communicate routing information via a Border Gateway Protocol (BGP) and the internetwork includes a routing overlay network to communicate routing parameters between the plurality of coupled autonomous systems, a method of exchanging routing information between a source network and a destination network coupled to the internetwork, the method comprising:

inserting a BGP community into a BGP feed, the BGP community including;

a cooperative private autonomous system field, the cooperative private autonomous system field being between 65001 and 65100; and

a corresponding value corresponding to the cooperative private autonomous system field; and

exchanging the BGP feed between the source network and the destination network via the routing overlay network.

28. The method of claim 27, wherein the cooperative private autonomous system field has a value of 65001, indicating that the value is an identifier of an equivalence class, the equivalence class including a group of network addresses.

29. The method of claim 28, wherein the group of network addresses exhibit similar network performance characteristics.

30. The method of claim 28, wherein the group of network addresses have similar measurements for jitter.

31. The method of claim 28, wherein the group of network addresses have similar measurements for packet loss.

32. The method of claim 28, wherein the group of network addresses have similar measurements for packet delay.

33. The method of claim 28, wherein the group of network addresses are geographically proximate.

34. The method of claim 27, wherein the cooperative private autonomous system field is 65002, such that the cooperative private autonomous system field indicates a request for symmetric AS path routing.

35. The method of claim 34, wherein the corresponding value is zero.

36. The method of claim 27, wherein the corresponding value is an AS from the plurality of coupled ASs, and the cooperative private autonomous system field has a value 65003, indicating that paths with the AS are preferred with first priority.

37. The method of claim 27, wherein the corresponding value is an AS from the plurality of coupled ASs, and the cooperative private autonomous system field has a value 65004, indicating that paths with the AS are preferred with second priority.

38. The method of claim 27, wherein the corresponding value is an AS from the plurality of coupled ASs, and the cooperative private autonomous system field has a value 65005, indicating that paths with the AS are preferred with third priority.

39. The method of claim 27, wherein the corresponding value is an AS from the plurality of coupled ASs, and the cooperative private autonomous system field has a value 65006, indicating that paths with the AS are to be avoided with first priority.

40. The method of claim 27, wherein the corresponding value is an AS from the plurality of coupled ASs, and the cooperative private autonomous system field has a value 65007, indicating that paths with the AS are to be avoided with second priority.

41. The method of claim 27, wherein the corresponding value is an AS from the plurality of coupled ASs, and the cooperative private autonomous system field has a value 65008, indicating that paths with the AS are to be avoided with third priority.

42. The method of claim 27, wherein the cooperative private autonomous system field has a value 65009, indicating a black hole Denial of Service Attack.

43. The method of claim 27, wherein the cooperative private autonomous system field has a value 650010 indicating a rate limit Denial of Service Attack.

44. The method of claim 27, wherein the cooperative private autonomous system field has a value 65011, indicating an informational Denial of Service Attack.

45. The method of claim 27, wherein the cooperative private autonomous system field has a value 65012, indicating unacceptable packet loss.

46. The method of claim 45, wherein the corresponding value indicates a packet loss number.

47. The method of claim 27, wherein the cooperative private autonomous system field has a value 65013, indicating unacceptable jitter.

48. The method of claim 47, wherein the corresponding value indicates a jitter number.

49. The method of claim 27, wherein the cooperative private autonomous system field has a value 65014, indicating a performance metric.

50. The method of claim 49, wherein the corresponding value is a scalar value of the performance metric.