Shared communications network employing virtual-private-network identifiers

• US 20030016672A1
• Filed: 09/19/2002
• Published: 01/23/2003
• Est. Priority Date: 01/19/1999
• Status: Active Grant

• Current Assignee: Eric C. Rosen, Yakov Rekhter
• Original Assignee: Eric C. Rosen, Yakov Rekhter
• Inventors: Rekhter, Yakov, Rosen, Eric C.
• Granted Patent: US 7,307,990 B2
• Time in Patent Office: Days
• 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 router in a communications system comprising:

A) means for coupling said router to a set of customer nodes so divided into at least first and second customer node subsets, said customer node subsets having no routing adjacency between nodes, and said first customer-node subset including a target node associated with a target network address;

B) means for coupling said router to a set of outside nodes separate from said customer nodes, at least one of the outside nodes being an outside edge router;

C) means for coupling said router to a set of provider nodes, said router functioning essentially as one of a plurality of provider edge routers;

D) means for forming a virtual private network with said customer communications nodes having associated internal and external VPN IDs and said provider nodes associated with said customer nodes, said router and said plurality of provider edge routers forming routing adjacencies with at least one node in every one of the customer node subsets, denominated a customer edge router;

E) means for receiving reachability messages that advertise a network-address range that includes the target network address from at least one said customer edge router to said router;

F) means for making routing decisions based on the contents of said reachability messages, wherein;

i) when said router that receives from a customer node in said first customer node subset a reachability message that advertises a network-address range that includes the target network address, it sends a reachability message that advertises the combination of the internal VPN ID and that network-address range to each other provider edge router that forms a provider-customer channel with the set of customer communications nodes;

ii) when said router that receives from a provider node a reachability message that advertises a network-address range that includes the target network address, it sends a reachability message that advertises the combination of the external VPN ID and that network-address range to at least one provider edge router associated with the set of outside nodes;

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

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