Path diversity for customer-to-customer traffic

• US 20080123651A1
• Filed: 11/27/2006
• Published: 05/29/2008
• Est. Priority Date: 11/27/2006
• Status: Active Grant

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Vasseur, Jean-Philippe, Guichard, Jim
• Granted Patent: US 7,710,902 B2
• Time in Patent Office: Days
• US Class Current: 370/392
• CPC Class Codes: H04L 12/4633 Interconnection of networks using encapsulation techniques, e.g. tunneling
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/24 Multipath
• CPC Class Codes: H04L 45/28 using route fault recovery
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

Abstract

In one embodiment, egress provider edge devices (PEs) send advertisements to ingress PEs for address prefixes of a first multi-homed customer network that desires path diversity through a service provider network to a second customer network. A first ingress PE receives the advertisements, and determines whether a second ingress PE is multi-homed with the first ingress PE to the second customer network. If so, the first ingress PE computes a plurality of diverse paths within the service provider network from the first and second multi-homed ingress PEs to a corresponding egress PE. If a plurality of diverse paths exists, the first ingress PE employs one of those paths to establish a first tunnel from itself to a first egress PE, and the second ingress PE employs another of the paths to establish a second tunnel from itself to a second egress PE that is diverse from the first tunnel.

Claims

1. A method, comprising:

sending advertisements from a plurality of egress provider edge devices (PEs) to a plurality of ingress PEs for one or more address prefixes of a first multi-homed customer network that desires path diversity through a provider network to a second customer network;

receiving the plurality of advertisements at a first ingress PE;

determining at the first ingress PE whether at least a second ingress PE is multi-homed with the first ingress PE to the second customer network;

computing, in response at the first ingress PE, a plurality of diverse paths within the provider network from at least the first and second multi-homed ingress PEs to a corresponding egress PE of the plurality of egress PEs;

determining whether a plurality of diverse paths exist;

establishing a first tunnel from the first ingress PE to a first egress PE of the plurality of egress PEs in response to existence of a plurality of diverse paths; and

establishing a second tunnel from the second ingress PE to a second egress PE of the plurality of egress PEs that is diverse from the first tunnel.

2. The method as in claim 1, further comprising:

receiving traffic from the second customer network for the address prefixes desiring path diversity at one of the ingress PEs; and

forwarding traffic of the address prefixes onto a corresponding tunnel established from the receiving ingress PE.

3. The method as in claim 1, further comprising:

advertising the one or more address prefixes from the first multi-homed customer network to the plurality of ingress PEs.

4. The method as in claim 3, further comprising:

advertising the one or more address prefixes from two or more customer edge devices (CEs).

5. The method as in claim 3, further comprising:

advertising the one or more address prefixes from a customer edge device (CE) that is multi-homed to two or more egress PEs.

6. The method as in claim 1, further comprising:

dynamically discovering the first multi-homed customer network at the plurality of egress PEs; and

in response,

sending the advertisements from the egress PEs for the one or more address prefixes.

7. The method as in claim 1, wherein the advertisements are extended community attributes for path diversity within a Border Gateway Protocol (BGP) advertisement.

8. The method as in claim 1, further comprising:

determining, at the ingress PEs, that the advertisements for the first customer network are received from a plurality of egress PEs; and

if so, establishing the diverse tunnels.

9. The method as in claim 1, further comprising:

determining, at the ingress PEs, that the first customer network is an originating customer network of the one or more address prefixes for the received plurality of advertisements; and

if so, establishing the diverse tunnels.

10. The method as in claim 1, wherein the diverse tunnels reserve zero bandwidth.

11. The method as in claim 1, further comprising:

determining, at the ingress PEs, that the first and second diverse tunnels already exist; and

in response,

using the existing first and second diverse tunnels.

12. The method as in claim 1, wherein the step of computing the plurality of diverse paths further comprises:

minimizing a sum of costs of the plurality of diverse paths.

13. The method as in claim 1, further comprising:

sending a notification from the first ingress PE to the second ingress PE, the notification to inform the second PE of a second path for the second tunnel from the second ingress PE to the second egress PE that was computed by the first ingress PE.

14. The method as in claim 13, further comprising:

establishing the second tunnel along the second path from the second ingress PE to the second egress PE that was computed by the first ingress PE.

15. The method as in claim 1, further comprising:

sending a notification from the first ingress PE to the second ingress PE, the notification to inform the second PE of the first tunnel and to request that the second ingress PE compute and establish the second tunnel from the second ingress PE to the second egress PE that is diverse from the first tunnel.

16. The method as in claim 1, further comprising:

determining, at the second ingress PE, that the second ingress PE is unable to establish the second tunnel to the second PE; and

in response,

sending a notification from the second ingress PE to the first ingress PE, the notification to indicate to the first ingress PE that the second ingress PE is unable to establish the second tunnel.

17. The method as in claim 16, further comprising:

determining whether a third ingress PE is multi-homed to the second customer network; and

if so,

establishing the second tunnel from the third ingress PE to the second egress PE that is diverse from the first tunnel.

18. The method as in claim 16, further comprising:

recomputing a first diverse path for the first tunnel from the first ingress PE to the first egress PE to allow a second diverse path from the second ingress PE to the second egress PE; and

reestablishing the first tunnel along the recomputed first diverse path.

19. A node, comprising:

one or more network interfaces adapted to provide an ingress to a provider network for a second customer network;

one or more processors coupled to the network interfaces and adapted to execute one or more processes; and

a memory adapted to store a path diversity process executable by each processor, the path diversity processes when executed adapted to;

i) receive advertisements from a plurality of egress provider edge devices (PEs) for one or more address prefixes of a first multi-homed customer network that desire path diversity through the provider network to the second customer network;

ii) determine whether the second customer network is multi-homed with a second ingress PE;

iii) compute, in response, a plurality of diverse paths within the provider network from at least the node and the second multi-homed ingress PE to a corresponding egress PE of the plurality of egress PEs;

iv) determine whether a plurality of diverse paths exist;

v) establish a first tunnel from the node to a first egress PE of the plurality of egress PEs in response to existence a plurality of diverse paths; and

vi) request that the second ingress PE establish a second tunnel from the second ingress PE to the second egress PE that is diverse from the first tunnel.

20. An system, comprising:

a plurality of egress provider edge devices (PEs) adapted to send advertisements for one or more address prefixes of a first multi-homed customer network that desire path diversity through a provider network to a second customer network;

a first ingress PE adapted to i) receive the plurality of advertisements, ii) determine whether at least a second ingress PE is multi-homed with the first ingress PE to the second customer network, iii) compute, in response, a plurality of diverse paths within the provider network from at least the first and second multi-homed ingress PEs to a corresponding egress PE of the plurality of egress PEs, iv) determine whether a plurality of diverse paths exist, and v) establish a first tunnel from the first ingress PE to a first egress PE of the plurality of egress PEs in response to existence a plurality of diverse paths; and

a second ingress PE adapted to establish a second tunnel from the second ingress PE to a second egress PE of the plurality of egress PEs that is diverse from the first tunnel.