Router for virtual private network employing tag switching

• US 7,369,556 B1
• Filed: 11/22/2002
• Issued: 05/06/2008
• Est. Priority Date: 12/23/1997
• Status: Expired due to Fees

• 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): LEE, CHI HO A
• Application Number:
  US10/302,201
• Time in Patent Office: 1,992 Days
• Field of Search: None
• US Class Current: 370/392
• CPC Class Codes: H04L 12/465 wherein a single frame includes a plurality of VLAN tags
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/50 using label swapping, e.g. multi-protocol label switch [MPLS]

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 method for operating a provider edge router, comprising:

receiving a data packet by the provider edge router from a first customer edge router of a customer network, the data packet associated with a particular virtual private network (VPN) of the customer network;

creating a header for forwarding the data packet, the header containing a first tag and a second tag, the first tag to be read by a provider transit router, the first tag indicating a next-hop on a path through a provider network to a second provider edge router, and the second tag to be read by the second provider edge router, the second tag indicating an egress channel of the second provider edge router providing access to a second customer edge router that is part of the VPN; and

forwarding the data packet with the header to the provider transit router so that the provider transit router can forward the data packet toward the second provider edge router in response to the first tag, and the second provider edge router can forward the data packet to the second customer edge router in response to the second tag.

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

forming a router adjacency between the provider edge router and the first customer edge router.

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

forming a router adjacency between the second provider edge router and the second customer edge router.

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

maintaining an information base by the provider edge router, the information base holding forwarding data accessible in response to fields in the data packet received from the first customer edge router, the forwarding data associating the second provider edge router with an address read from the data packet, and the forwarding data base also associating the provider transit router with a route to the second provider edge router;

placing the first tag and the second tag into the header in response to the second provider edge router and the provider transit router as determined from the information base in association with the address read from the data packet.

12. The method as in claim 1, wherein the data packet received by the provider edge router includes a destination address that specifies a customer node accessible through the second customer edge router, and the step of creating a header is performed in response to determining the data packet should traverse one or more provider routers to reach the second customer edge router.

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

maintaining the VPN through the provider edge router for transmission of the data packet.

14. The method as in claim 13, wherein the VPN extends at least between the first customer edge router and the second customer edge router.

5. A method for operating a system of routers, comprising:

receiving at a first provider edge router a data packet from a first customer edge router of a customer network, the data packet associated with a particular virtual private network (VPN) of the customer network;

creating a header by the first provider edge router for forwarding the data packet, the header containing a first tag and a second tag, the first tag to be read by a provider transit router, the first tag indicating a next-hop on a route through the provider network to a second provider edge router, and the second tag to be read by a second provider edge router, the second tag indicating a particular egress channel of the second provider edge router providing access to a second customer edge router that is part of the VPN;

forwarding the data packet with the header to the provider transit router;

reading the first tag by the provider transit router, and forwarding the data packet in response to the first tag, on the route to the second provider edge router; and

reading the second tag by the second provider edge router, and forwarding the data packet by the second provider edge router in response to the second tag to a second customer edge router.

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

forming a router adjacency between the first provider edge router and the first customer edge router.

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

forming a router adjacency between the second provider edge router and the second customer edge router.

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

maintaining an information base by the first provider edge router, the information base holding forwarding data accessible in response to fields in the data packet received from the customer edge router, the forwarding data associating the second provider edge router with an address read from the data packet, and the forwarding data base also associating the provider transit router with a route to the second provider edge router;

placing the first tag and the second tag into the header in response to the second provider edge router and the provider transit router as determined from the information base in association with the address read from the data packet.

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

maintaining an information base by the provider transit router, the information base associating the first tag with a route to the second provider edge router.

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

removing the first tag from the data packet by the provider transit router before forwarding the data packet along the route to the second provider edge router.

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

forwarding the data packet to a second provider transit router in response to the second tag when the route to the second provider edge router requires a hop through the second provider transit router;

removing the first tag from the header before forwarding the data packet to the second provider transit router; and

writing a third tag into the header for the second provider transit router to use in forwarding the data packet on a further route toward the second provider edge router.

15. A method for operating a router, comprising:

receiving a data packet from a provider router, the data packet having a header, the data packet associated with a particular virtual private network (VPN) of a customer network;

reading a first tag and a second tag from the header;

deciding, in response to the first tag and the second tag, whether the router is a provider transit router or a provider edge router;

routing the data packet, in the event that the decision is that the router is a provider transit router, to a downstream provider router in response to the first tag; and

routing the data packet, in the event that the decision is that the router is a provider edge router, to a particular egress channel that leads to a downstream customer edge router that is part of the VPN in response to the second tag.

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

deciding that the router is a provider transit router, in response to the first tag specifying a route to another provider router.

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

deciding that the router is a provider edge router, in response to the first tag not specifying a route to another provider router.

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

reading, in response to the first tag, forwarding data from a tag information database, and in response to the forwarding data, deciding that the router is a provider transit router.

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

reading, in response to the first tag, forwarding data from a tag information database, and in response to the forwarding data, deciding that the router is a provider edge router.

20. A method for operating an edge router of a provider network comprising:

receiving a data packet from a router of a customer network associated with a virtual private network (VPN), the data packet including a destination address field that specifies an address of a node in another portion of the customer network also associated with the VPN, the other portion of the customer network accessible through the provider network;

making a routing decision based on the contents of the data packet'"'"'s destination address field and the router of the customer network the data packet is received from, the routing decision determining a path through the provider network to an egress edge router that provides access to the other portion of the customer network;

adding to the data packet an internal-routing field that includes a first tag and a second tag, the first tag to indicate a next hop along the path to the egress edge router, and the second tag to indicate a particular egress channel of the egress edge router that leads to the node in another portion of the customer network also associated with the VPN;

indicating in the data packet that any routers along the path through the provider network to the egress edge router are to make routing decisions based on the internal-routing field without reference to the destination address field; and

forwarding the data packet.

21. The method of claim 20 further comprising:

forming a routing adjacency between the edge router and at least one node of the customer network.

22. The method as in claim 20 wherein the internal-routing field further comprises a field that identifies a virtual channel for the data packet.

23. A system comprising:

an edge router of a provider network configured to receive a data packet from a router of a customer network associated with a virtual private network (VPN), the data packet including a destination address field that specifies an address of a node in another portion of the customer network that is also associated with the VPN, the other portion of the customer network accessible through the provider network, the edge router configured to determine a path through the provider network to an egress edge router that provides access to the other portion of the customer network, the path determined based upon the data packet'"'"'s destination address field and the router of the customer network the data packet is received from, the edge router to add to the data packet an internal-routing field that includes a first tag and a second tag that describe the path;

a transit router of the provider network configured to receive the data packet and to make a next-hop routing decision based on the first tag of the internal-routing field, without reference to the destination address field, the transit router further configured to generate a new value for the first tag and to update the first tag with this new value before forwarding the data packet; and

an egress edge router of the provider network configured to receive the data packet and to select a particular egress channel based on the second tag, the egress channel to lead to the node in another portion of the customer network also associated with the VPN.

24. The system of claim 23 wherein the edge router of the provider network is further configured to form an adjacency with at least one node of the customer network.

25. The system of claim 24 wherein the transit router of the provider network is configured to not have an adjacency with any nodes of the customer network.

26. The system of claim 23 wherein the transit router of the provider network is configured to not maintain VPN-specific routing information.

27. The system of claim 23, wherein the internal-routing field further comprises a field that identifies a virtual channel for the data packet.