Peer-model support for virtual private networks with potentially overlapping addresses

• US 6,339,595 B1
• Filed: 12/23/1997
• Issued: 01/15/2002
• Est. Priority Date: 12/23/1997
• Status: Expired due to Term

• Current Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Original Assignee: Cisco Technology, Inc. (Cisco Systems, Inc.)
• Inventors: Rekhter, Yakov, Rosen, Eric C.
• Primary Examiner(s): Marcelo, Melvin
• Assistant Examiner(s): LEE, CHI HO A
• Application Number:
  US08/997,343
• Time in Patent Office: 1,484 Days
• Field of Search: 370/351-360, 370/389, 370/392, 370/393, 370/400, 370/401, 370/474, 370/404, 370/396
• US Class Current: 370/392
• CPC Class Codes: H04L 12/4645 Details on frame tagging routing of packets H04L45/00; support for virtual LAN H04L49/354
• 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/50 using label swapping, e.g. multi-protocol label switch [MPLS]
• CPC Class Codes: H04L 63/0272 Virtual private networks

Abstract

A service provider'"'"'s routers (PE1, P1, P2, PE2) provide connections between and share routine information with routers (CE1, CE2) of a customer virtual private network (VPN) as well as routers of other customers'"'"' VPNs, which may have overlapping address spaces. A service provider'"'"'s edge router (PE1) informed by the customer'"'"'s router (CE1) that it will forward packets to a given prefix notifies the other edge router (PE2) that PE1 can forward packets to that address prefix if the destination is in the VPN to which CE1 belongs. PE1 also tells PE2 to tag any thus-destined packets with a particular tag T3. PE2 stores this information in a forwarding information base that it separately keeps for that VPN so that when PE2 receives from a router CE2 in the same VPN a packet whose destination address has that prefix, it tags the packet as requested. But PE2 also tags it with a tag T2 that the router P2 to which PE2 first sends it has asked PE2 to apply to packets to be sent to PE1. P2 routes the packet in accordance with T2, sending it to P1 after replacing T2 with a tag T1 that P1 has similarly asked P2 to use. P1 removes T1 from the packet and forwards it in accordance with T1 to PE1, which in turn removes T3 from the packet and forwards it in accordance with T3 to CE1. In this manner, only the edge routers need to maintain separate routing information for separate VPNs.

Claims

1. A service-provider network comprising a plurality of interconnected provider edge routers and transit routers, wherein:

A) each edge router includes circuitry for;

i) receiving from a source not in the service-provider network packets that include destination-address fields that specify final destinations that also are not located in the service-provider network;

ii) for each of a plurality of such received packets;

a) making a routing decision based not only on the contents of that packet'"'"'s destination-address field but also on the source from which it receives that packet;

b) inserting into the packet an internal-routing field, determined at least in part in accordance with the source from which the edge router received the packet, that specifies a route to an interface on another of the provider edge routers; and

c) forwarding the resultant packet to another router in the service-provider network in accordance with the routing decision; and

iii) receiving, from other routers in the service provider network, packets that include internal-routing fields and forwarding them without their internal-routing fields to routers, that are not located in the service-provider network, that it selects in accordance with a routing decision based on the contents of the packets'"'"' internal-routing fields; and

B) each transit router includes circuitry for;

i) receiving, from other routers in the service provider network, packets that include internal-routing fields and destination-address fields;

ii) making routing decisions based on the contents of those packets'"'"' internal-routing fields without reference to those of their destination-address fields; and

iii) in accordance with those routing decisions, forwarding those packets to other routers in the service-provider network.

2. A service-provider network as defined in claim 1 wherein:

A) a plurality of the provider edge routers make routing decisions based on the contents of reachability messages that they receive;

B) the provider edge routers are together connected to at least first and second pluralities of customer routers, with which the service-provider network respectively associates first and second VPN IDs;

C) when an provider edge router receives a reachability message concerning a given network-address range from a customer router with which it associates a given VPN ID, it sends a reachability message concerning the combination of that network-address range and the given VPN ID to each provider edge router connected to a customer router with which the service-provider network associates the same VPN ID; and

D) when a provider edge router receives a reachability message concerning the combination of a network-address range and a given VPN ID associated with a customer router to which it is connected, it sends that customer router a reachability message concerning that network-address range.

3. A service-provider network as defined in claim 2 wherein the provider edge routers use an external gateway protocol to send other provider edge routers the reachability message concerning the combination of network-address range and the given VPN ID.

4. A service-provider network as defined in claim 3 wherein the external gateway protocol that the provider edge routers use to send other provider edge routers the reachability message concerning the combination of network-address range and the given VPN ID is the Border Gateway Protocol.

5. A service-provider network as defined in claim 2 wherein:

A) the internal-routing field includes both an egress-router field and an egress-channel field;

B) the transit routers base their routing decisions concerning packets that include internal-routing fields on the internal-routing fields'"'"' egress-router fields without reference to their egress-channel fields; and

C) the provider edge routers base their selections of the routers that are not located in the service-provider network on the internal-routing fields'"'"' egress-channel fields.

6. A service-provider network as defined in claim 5 wherein each transit router maintains an information base that associates internal-routing-field contents with routers to which it is connected in the service-provider network and forwards packets containing internal-routing fields to the routers with which that transit router'"'"'s information base associates the contents of those internal-routing fields.

7. A service-provider network as defined in claim 6 wherein the information base of at least one transit router associates at least certain internal-routing-field contents with replacement internal-routing-field contents, and that transit router replaces the certain internal-routing-field contents with the replacement internal-routing-field contents in packets that it forwards.

8. A service-provider network as defined in claim 7 wherein the transit router that replaces internal-routing-field contents replaces the contents of the the egress-router field without replacing the contents of the egress-channel field.

9. A service-provider network comprising a plurality of interconnected routers including provider edge routers, wherein:

A) the provider edge routers are together connected to at least first and second pluralities of customer routers, with which the service-provider network respectively associates first and second VPN IDs;

B) each provider edge router includes circuitry for;

i) responding to receipt of communications packets by forwarding them in accordance with routing decisions that it makes in accordance with the contents of reachability messages that it has received;

ii) responding to receipt of a reachability message concerning a given network-address range from a customer router with which it associates a given VPN ID by sending a reachability message concerning the combination of that network-address range and the given VPN ID to each said provider edge router connected to a customer router with which the service-provider network associates the same VPN ID; and

iii) responding to receipt of a reachability message concerning the combination of a network-address range and a given VPN ID associated with a customer router to which it is connected by sending that customer router a reachability message concerning that network-address range.

10. A communications system comprising:

A) a set of customer nodes so divided into at least first and second customer-node subsets that no node of any given subset is a routing adjacency of any other subset'"'"'s node; and

B) a service-provider network forming a virtual private network with the set of customer communications nodes and comprising a plurality of provider nodes including provider transit routers that form no routing adjacencies with any node of the set of customer communications nodes and further including provider edge routers associated with the set of customer communications nodes, which provider edge routers together form routing adjacencies with at least one node in every one of the customer node subsets, each provider edge router associated with the set of customer communications nodes forming a routing adjacency with at least one customer node, denominated a customer edge router, to which it is linked by at least one provider-customer channel, wherein;

i) each provider edge router associated with the set of customer communications nodes includes circuitry for;

a) receiving by way of a customer-provider channel that links it to a customer edge router in one of the customer node subsets data packets that include destination-address fields that specify nodes in another of the customer node subsets;

b) for each of a plurality of Such received packets;

(1) making a routing decision based not only on the contents of that packet'"'"'s destination-address field but also on the source from which it receives that packet;

(2) inserting into the packet an internal-routing field, determined at least in part in accordance with the source from which the edge router received the packet, that specifies a route to a channel that links another of the provider edge routers; and

(3) forwarding the resultant packet to another router in the service-provider network in accordance with the routing decision; and

c) receiving, from other routers in the service-provider network, packets that include internal-routing fields and forwarding them without their internal-routing fields by way of a provider-customer channel that it selects in accordance with the contents of the packets'"'"' internal-routing fields; and

ii) each provider transit router includes circuitry for;

a) receiving, from other routers in the service provider network, packets that include internal-routing fields and destination-address fields;

b) making routing decisions based on the contents of those packets'"'"' internal-routing fields without reference to those of their destination-address fields; and

c) in accordance with those routing decisions, forwarding those packets to other routers in the service-provider network.

11. A communications system as defined in claim 10 wherein:

A) the communications system further includes a set of outside nodes not included in the virtual private network, at least one of the outside nodes being an outside edge router;

B) at least one of the nodes of the provider network is a provider edge router associated with the set of outside nodes and forming a provider-exterior channel with the outside edge router;

C) the provider edge routers associated with the set of customer nodes and the set of outside nodes make routing decisions based on the contents of reachability messages that they have received;

D) the provider network associates internal and external VPN IDs with the set of customer nodes;

E) one of the customer node subsets, denominated the target customer node subset, includes a target node associated with a target network address;

F) at least first and second ones of the provider-customer channels are formed between the target customer node subset and the provider network and provide access to the target node;

G) the customer edge router of the target customer node subset sends through the first provider-customer channel to a provider edge router reachability messages that advertise a network-address range that includes the target network address;

H) the provider edge router that receives such a reachability message through the first provider-customer channel sends a reachability message that advertises the combination of the internal VPN ID and that network-address range only to each other provider edge router that forms a provider-customer channel with the set of customer communications nodes;

I) a customer edge router of the target customer node subset also sends through the second provider-customer channel to a provider edge router reachability messages that advertise a network-address range that includes the target network address;

J) the provider edge router that receives such a reachability message through the second provider-customer channel sends a reachability message that advertises the combination of the second VPN ID and that network-address range at least to the provider edge router associated with the set of outside nodes;

K) when a provider edge router associated with the set of customer nodes receives a reachability message that advertises the combination of a network-address range and the internal VPN ID associated with the virtual private network, it sends to one said customer router with which it forms a customer-provider channel a reachability message that advertises that network-address range;

L) when a provider edge router associated with the set of customer nodes receives therefrom a data packet whose destination-address field contains the target network address, it inserts into the packet an internal-routing field that specifies a route to the first provider-customer channel that provides access to the target node;

M) when a provider edge router associated with the set of outside nodes receives a reachability message that advertises the combination of a network-address range and the external VPN ID associated with the virtual private network, it sends to one said customer router with which it forms a provider-exterior channel a reachability message that advertises that network-address range; and

N) when a provider edge router associated with a set of outside nodes receives therefrom a data packet whose destination-address field contains the target network address, it inserts into the packet an internal-routing field that spedifies a route to the second provider-customer channel that provides access to the target node.

12. For performing packet-based communication though a service-provider network comprising a plurality of interconnected provider edge routers and transit routers, a method comprising:

A) receiving at one said edge router, denominated an ingress router, from a source not in the service-provider network, packets that include destination-address fields that specify final destinations that also are not located in the service-provider network; and

B) for each of a plurality of such received packets;

i) making a routing decision at said ingress router based not only on the contents of that packet'"'"'s destination-address field but also on the source from which the ingress router received that packet;

ii) inserting into the packet an internal-routing field, determined at least in part in accordance with the source from which the ingress router received the packet, that specifies a route to an interface on another of the provider edge routers, denominated an egress router;

iii) forwarding the resultant packet from said edge router to a chain of at least one transit router in the service-provider network in accordance with the routing decision;

iv) making routing decisions in the chain of at least one transit router based on the contents of the packet'"'"'s internal-routing field without reference to those of its destination-address field;

v) in accordance with those routing decisions, forwarding that packet through the chain of at least one transit touter to the egress router; and

vi) employing the egress router to forward that packet without its internal-routing field to a router, not located in the service-provider network, that the egress router selects in accordance with a routing decision based on the contents of the packet'"'"'s internal-routing field.

13. A method as defined in claim 12 wherein:

A) the routing decisions made at a plurality of the provider edge routers, including the ingress and egress routers, are based on the contents of reachability messages that those routers receive;

B) the provider edge routers are together connected to at least first and second pluralities of customer routers, with which the service-provider network respectively associates first and second VPN IDs;

C) when an provider edge router receives a reachability message concerning a given network-address range from a customer router with which it associates a given VPN ID, it sends a reachability message concerning the combination of that network-address range and the given VPN ID to each provider edge router connected to a customer router with which the service-provider network associates the same VPN ID; and

D) when a provider edge router receives a reachability message concerning the combination of a network-address range and a given VPN ID associated with a customer router to which it is connected, it sends that customer router a reachability message concerning that network-address range.

14. A method as defined in claim 13 wherein the provider edge routers use an external gateway protocol to send other provider edge routers the reachability message concerning the combination of network-address range and the given VPN ID.

15. A method as defined in claim 14 wherein the external gateway protocol that the provider edge routers use to send other provider edge routers the reachability message concerning the combination of network-address range and the given VPN ID is the Border Gateway Protocol.

16. A method as defined in claim 13 wherein:

A) the internal-routing field includes both an egress-router field and an egress-channel field;

B) the transit routers base their routing decisions concerning packets that include internal-routing fields on the internal-routing fields'"'"' egress-router fields without reference to their egress-channel fields; and

C) the egress routers bases its selections of the routers that are not located in the service-provider network on the internal-routing fields'"'"' egress-channel fields.

17. A method as defined in claim 16 wherein each transit router maintains an information base that associates internal-routing-field contents with routers to which it is connected in the service-provider network and forwards packets containing internal-routing fields to the routers with which that transit router'"'"'s information base associates the contents of those internal-routing fields.

18. A method as defined in claim 17 wherein the information base of at least one transit router associates at least certain internal-routing-field contents with replacement internal-routing-field contents, and that transit router replaces the certain internal-routing-field contents with the replacement internal-routing-field contents in packets that it forwards.

19. A method as defined in claim 18 wherein the transit router that replaces internal-routing-field contents replaces the contents of the egress-router field without replacing the contents of the egress-channel field.

20. For performing packet-based communication though a service-provider network comprising a plurality of interconnected routers including provider edge routers together connected to at least first and second pluralities of customer routers, a method comprising:

A) associating first and second VPN IDs with the first and second pluralities of customer routers, respectively;

B) employing each said provider edge router to respond to receipt of communications packets by forwarding them in accordance with routing decisions that it makes in accordance with the contents of reachability messages that it receives;

C) employing each said provider edge router to respond to receipt of a reachability message concerning a given network-address range from a customer router with which a given VPN ID is associated by sending a reachability message concerning the combination of that network-address range and the given VPN ID to each said provider edge router connected to a customer router with which the service-provider network associates the same VPN ID; and

D) employing each said provider edge router to respond to receipt of a reachability message concerning the combination of a network-address range and a given VPN ID associated with a customer router to which it is connected by sending that customer router a reachability message concerning that network-address range.

21. A communications method comprising:

A) providing a set of customer nodes so divided into at least first and second customer-node subsets that no node of any given subset is a routing adjacency of any other subset'"'"'s node;

B) providing a service-provider network forming a virtual private network with the set of customer communications nodes and comprising a plurality of provider nodes including provider transit routers that form no routing adjacencies with any node of the set of customer communications nodes and further including provider edge routers associated with the set of customer communications nodes, which provider edge routers together form routing adjacencies with at least one node in every one of the customer node subsets, each provider edge router associated with the set of customer communications nodes forming a routing adjacency with at least one customer node, denominated a customer edge router, to which it is linked by at least one provider-customer channel;

C) employing a provider edge router associated with the set of customer communications nodes to receive by way of a customer-provider channel that links that provider edge router to a customer edge router in one of the customer node subsets data packets that include destination-address fields that specify nodes in another of the customer node subsets; and

D) for each of a plurality of such received packets;

i) employing the provider edge router to;

a) make a routing decision based not only on the contents of that packet'"'"'s destination-address field but also on the source from which it receives that packet;

b) insert into the packet an internal-routing field, determined at least in part in accordance with the source from which the edge router received the packet, that specifies a route to a channel that links another of the provider edge routers, denominated an egress router; and

c) forward the resultant packet to a chain of at least one of the transit routers in the service-provider network in accordance with the routing decision;

ii) making routing decisions in the chain of at least one transit router based on the contents of those packet'"'"'s internal-routing field without reference to those of their destination-address field;

iii) in accordance with those routing decisions, forwarding that packet through the chain of at least one transit router to the egress router; and

iv) employing the egress router to forward that packet without its internal-routing field by way of a provider-customer channel that it selects in accordance with the contents of the packet'"'"'s internal-routing field.