# US 7,080,161 B2 · Routing information exchange

> Agents: this data is available as JSON from the patentgrep API and MCP server — see https://patentgrep.com/llms.txt

- Number: US 7,080,161 B2
- Document ID: US7080161B2
- Status: Granted
- Kind: B2
- Application number: 09/903,441
- Filed: 2001-07-10
- Published: 2002-12-05
- Granted: 2006-07-18
- Earliest claimed: 2000-10-17
- Assignees: Avaya Technology Corp.
- Inventors: John G. Leddy; Michael A. Lloyd; Sean P. Finn; James G. McGuire; Omar C. Baldonado; Herbert S. Madan
- Web page: https://patentgrep.com/patent/US7080161B2

## CPC

- H04L 45/70: {Routing based on monitoring results}
- H04L 43/00: Arrangements for monitoring or testing data switching networks
- H04L 45/026: {Details of "hello" or keep-alive messages}
- H04L 45/033: by updating distance vector protocols
- H04L 45/04: {Interdomain routing, e.g. hierarchical routing}
- H04L 45/123: {Evaluation of link metrics (techniques for monitoring network metrics H04L43/08)}
- H04L 45/124: {using a combination of metrics}
- H04L 45/50: using label swapping, e.g. multi-protocol label switch [MPLS]
- H04L 45/64: using an overlay routing layer
- H04L 47/10: Flow control; Congestion control
- H04L 47/11: Identifying congestion
- H04L 47/20: Traffic policing
- H04L 47/283: in response to processing delays, e.g. caused by jitter or round trip time [RTT]
- H04L 43/0829: Packet loss
- H04L 43/0852: Delays
- H04L 43/087: Jitter
- H04L 43/16: Threshold monitoring
- H04L: TRANSMISSION OF DIGITAL INFORMATION, e.g. TELEGRAPHIC COMMUNICATION (arrangements common to telegraphic and telephonic communication H04M)

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

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

### Claim 2 (depends on 1)

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.

### Claim 3 (depends on 1)

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.

### Claim 4 (depends on 3)

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.

### Claim 5 (depends on 3)

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.

### Claim 6 (depends on 3)

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.

### Claim 7 (depends on 3)

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.

### Claim 8 (depends on 3)

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.

### Claim 9 (depends on 8)

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.

### Claim 10 (depends on 9)

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

### Claim 11 (depends on 10)

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.

### Claim 12 (depends on 11)

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

### Claim 13 (depends on 12)

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

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

### Claim 15 (depends on 14)

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

### Claim 16 (depends on 15)

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

### Claim 17 (depends on 14)

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

### Claim 18 (depends on 17)

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

### Claim 19 (depends on 17)

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

### Claim 20 (depends on 17)

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.

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

### Claim 22 (depends on 21)

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.

### Claim 23 (depends on 21)

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.

### Claim 24 (depends on 21)

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.

### Claim 25 (depends on 21)

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

### Claim 26 (depends on 25)

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

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

### Claim 28 (depends on 27)

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.

### Claim 29 (depends on 28)

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

### Claim 30 (depends on 28)

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

### Claim 31 (depends on 28)

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

### Claim 32 (depends on 28)

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

### Claim 33 (depends on 28)

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

### Claim 34 (depends on 27)

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.

### Claim 35 (depends on 34)

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

### Claim 36 (depends on 27)

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.

### Claim 37 (depends on 27)

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.

### Claim 38 (depends on 27)

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.

### Claim 39 (depends on 27)

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.

### Claim 40 (depends on 27)

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.

### Claim 41 (depends on 27)

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.

### Claim 42 (depends on 27)

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

### Claim 43 (depends on 27)

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

### Claim 44 (depends on 27)

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

### Claim 45 (depends on 27)

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

### Claim 46 (depends on 45)

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

### Claim 47 (depends on 27)

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

### Claim 48 (depends on 47)

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

### Claim 49 (depends on 27)

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

### Claim 50 (depends on 49)

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