Virtual private network employing tag-implemented egress-channel selection

• US 6,526,056 B1
• Filed: 12/21/1998
• Issued: 02/25/2003
• 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: Rosen, Eric C., Rekhter, Yakov
• Primary Examiner(s): Nguyen, Chau
• Assistant Examiner(s): LEE, CHI HO A
• Application Number:
  US09/217,976
• Time in Patent Office: 1,527 Days
• Field of Search: 370/389, 370/392, 370/393, 370/394, 370/395.1, 370/396-399, 370/395.2, 370/395.3, 370/395.31, 370/395.52, 370/395.54, 370/400-401, 370/410, 370/466, 370/474, 370/402-406
• 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 routing 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 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 a node of any other subset; and

B) a service-provider network forming a virtual private network with the set of customer 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 nodes and further including at least first and second provider edge routers associated with the set of customer nodes, said first provider edge router being linked by a first provider-customer channel with at least one customer node, denominated a first customer edge router, in the first customer-node subset, said second provider edge router being linked by a second provider-customer channel with a plurality of customer nodes, denominated second customer edge routers, of which at least one is in the second customer-node subset, wherein;

i) the first provider edge router includes circuitry for;

a) receiving by way of the first provider-customer channel data packets that include destination-address fields that specify nodes in another of the customer-node subsets; and

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

(1) making a routing decision based on the contents of that packet'"'"'s destination-address field;

(2) inserting into the packet an internal-routing field that includes both an egress-router field and an egress-channel field and 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;

ii) the second provider edge router includes circuitry for receiving, from at least one other router in the service-provider network, packets that include internal-routing fields and forwarding them without their internal-routing fields by way of a second provider-customer channel that it selects in accordance withe the contents of the packets'"'"' egress-channel fields; and

iii) at least one said 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 egress-channel fields or their destination-address fields; and

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

2. A communications system as defined in claim 1 wherein the provider edge routers together form routing adjacencies with at least one node in each of the customer-node subsets.

3. A communications system as defined in claim 2 wherein said at least one transit router maintains an information base that associates egress-router-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'"'"'s egress-router-fields.

4. A communications system as defined in claim 3 wherein the information base of said at least one transit router associates egress-router-field contents with replacement egress-router-field contents, and that transit router replaces the egress-router-field contents with the replacement egress-router-field contents in packets that it forwards.

5. A communications system as defined in claim 1 wherein said at least one transit router maintains an information base that associates egress-router-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'"'"'s egress-router-fields.

6. A communications system as defined in claim 5 wherein the information base of said at least one transit router associates egress-router-field contents with replacement egress-router-field contents, and that transit router replaces the egress-router-field contents with the replacement egress-router-field contents in packets that it forwards.

7. For operating a communications system, a 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 routind adjacency of a node of any other subset;

B) providing a serivce-provider network that forms a virtual private network with the set of customer nodes and comprises a plurality of provider nodes including provider transit routers that form no routing adjacencies with any node of the set of customer nodes and further including at least first and second provider edge routers associated with the set of customer nodes, said first provider edge router being linked by a first provider-customer channel with at least one customer node, denominated a first customer edge router, in the first customer-node subset, said secone provider edge router being linked by a second provider-customer channel with a plurality of customer nodes,denominated second customer edge routers, of which at least one is in the second customer-node subset;

C) receiving at the first provider edge router, by way the first provider-customer channel, data packets that include destination-address fields that specify nodes in another of the customer-node subset;

D) for each of a plurality of such packets, employing that provider edge router to;

i) make a routing decision that is based on the contents of that packet'"'"'s destination-address;

ii) insert into the packet an internal-routing field that includes both an egress-router field and an egress-channel field and specifies a route to a channel that links another of the provider edge routers; and

iii) forward the resultant packet to another router in the service-provider network in accordance with the routing decision;

E) employing the second provider edge router to recieve, from other routers in the service-provider network, packets that include internal-routing fields and forward them without their internal-routing fields by way of a second provider-customer channel that it selects in accordance with contents of the packets'"'"' egress-channel fields; and

F) employing each of a plurality of the provider transit routers to;

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

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

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

8. A method as defined in claim 7 wherein the procider edge routers together form routing adjacencies with at least one node in each of the customer-node subsets.

9. A method as defined in claim 8 wherein:

A) said at least one transit router maintains an information base that associates egress-router-field contents with routers to which it is connected in the service-provider network; and

B) the method further includes employing said at least one transit router to forward packets containing internal-routing fields to the routers with which that transit router'"'"'s information base associates the contents of those internal-routing fields'"'"' egress-router fields.

10. A method as defined in claim 9 wherein:

A) the information base of said at least one transit router associates egress-router-field contents with replacement egress-router-field contents, and

B) the method further comprises employing that transit router to replace the egress-router-field contents with the replacement egress-router-field contents in packets that it forwards.

11. A method as defined in claim 7 wherein:

A) said at least one transit router maintains an information base that associates egress-router-field contents with routers to which it is connected in the service-provider network; and

B) the method further comprises employing that transit router to replace the egress-router-field contents with the replacement egress-router-field contents in packets that it forwards.

12. A method as defined in claim 11 wherein:

A) the information base of said at least one transit router associates egress-router-field contents with replacement egress-router-field contents, and

B) the method further comprises employing that transit router to replace the egress-router-field contents with the replacement egress-router-field contents in packets that it forward.