Method for optimal assignment of customer edge (CE) routers to virtual private network route forwarding (VRF) tables

• US 20060215578A1
• Filed: 03/25/2005
• Published: 09/28/2006
• Est. Priority Date: 03/25/2005
• Status: Active Grant

• Current Assignee: Alcatel-Lucent USA, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Naik, Tejas, Feather, Frank, Andrapalliyal, Bala
• Granted Patent: US 7,564,802 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 12/4679 Arrangements for the registration or de-registration of VLAN attribute values, e.g. VLAN identifiers, port VLAN membership

Abstract

A method for optimal assignment of customer edge (CE) routers to virtual private network route forwarding (VRF) tables uses a “peer model”, in which the CE routers communicate their routes to a Service Provider'"'"'s edge routers (PE routers). The routes of a particular VPN are then exchanged among the PE routers that are attached to that VPN. This is accomplished in a manner which ensures that routes from different VPNs remain distinct and separate, even if two VPNs comprise an overlapping address space. The PE routers distribute, to the CE routers in a particular VPN, the routes from other CE routers in that VPN. The CE routers do not peer with each other and, as such, there is no “overlay” visible to a VPN'"'"'s routing algorithm.

Claims

1. A method, comprising:

determining virtual private network (VPN) membership for each of a plurality of customer edge (CE) routers, each VPN being associated with at least one respective VPN route forwarding (VRF) table; and

attaching to each VRF table those CE routers having membership in the VPN associated with the respective VRF table.

2. The method of claim 1, wherein:

each VRF table supporting a respective VPN has attached to it CE routers from only one customer.

3. The method of claim 1, wherein:

at least one VRF table supporting multiple VPNs has attached to it CE routers supporting a plurality of customers.

4. The method of claim 1, wherein said VRF tables are only associated with VPNs within one of a mesh topology and a hub and spoke topology.

5. The method of claim 4, wherein:

a VRF table is constrained to have attached to it one of either hub CE routers or spoke CE routers.

6. The method of claim 1, further comprising:

adding a CE router to a first customer VPN, said CE router not being attached to a VRF table, said step of adding comprising;

in response to the existence of a VRF table being associated with said first VPN, attaching said new CE to said VRF table being associated with said first VPN;

in response to the absence of a VRF table being only associated with said first VPN, creating a new VRF table identifying the properties of the new CE router and attaching said new CE to said created VRF table using an interface identified in the new CE router properties.

7. The method of claim 6, wherein:

the properties of each of said CE router identify a respective customer (CUST), autonomous system number (ASN), interface (IF) and connected provider edge (PE).

8. The method of claim 1, further comprising:

adding a CE router to a first VPN, said CE router being attached to a VRF table associated with a plurality of VPNs, said step of adding comprising;

if said CE router is the only CE router associated with the VRF table, then adding at least one route target (RT) to the VRF table to associate the VRF table with the first VPN.

9. The method of claim 1, further comprising:

adding a CE router to a first VPN, said CE router being attached to a VRF table associated with a second VPN, said step of adding comprising;

splitting said CE router from said VRF table associated with said second VPN; and

in response to the existence of a VRF table being associated with said first VPN and said second VPN, attaching said new CE to said VRF table;

in response to the absence of a VRF table being associated with said first VPN and said second VPN, creating a new VRF table identifying the properties of the new CE router and attaching said new CE to said created VRF table using an interface identified in the new CE router properties.

10. The method of claim 1, further comprising:

removing a first CE router from one of a plurality of VPNs to which the CE router participates, said one VPN being associated with a first VRF table, said step of removing comprising;

in response to the existence of a VRF table being associated with said plurality of VPNs with the exclusion of said one VPN, attaching said CE to said VRF table;

in response to the absence of such a VRF table, if said CE router is the only CE router associated with the VRF table, removing at least one route target (RT) from the VRF table to disassociate the VRF table from the first VPN.

11. The method of claim 1, further comprising:

removing a first CE router from one of a plurality of VPNs to which the CE router participates, said one VPN being associated with a first VRF table, said step of removing comprising;

creating a second VRF table using a modified route target (RT) attribute of said first VRF table, said modification comprising the exclusion of said one VPN from said RT attribute;

disassociating said first CE router from said first VRF table; and

associating said first CE router with said second VRF table.

12. The method of claim 11, wherein:

said step of creating a second VRF table is performed prior to said step of disassociating said first CE router from said first VRF table.

13. The method of claim 11, further comprising:

deleting said first VRF table if no other CE routers are associated thereto.

14. The method of claim 1, wherein:

if the routing protocol between a PE router and a CE router comprises the Extended Interior Gateway Routing Protocol (EIGRP), then all CE routers running EIGRP within the VRF table are within the same Autonomous System (AS).

15. A computer program product wherein computer instructions, when processed by a computer, adapt the operation of the computer to perform a method, comprising:

determining virtual private network (VPN) membership for each of a plurality of customer edge (CE) routers, each VPN being associated with at least one respective VPN route forwarding (VRF) table; and

attaching to each VRF table those CE routers having membership in the VPN associated with the respective VRF table.

16. A method, comprising:

assigning customer edge (CE) routers to virtual private network (VPN) route forwarding (VRF) tables, wherein said assigning is performed in a manner tending to reduce the relative number of VRF tables needed to support each of a plurality of customer VPNs.

17. A control device adapted for causing the routing of data traffic via at least one virtual private networks (VPN), said control device router including control circuitry adapted to execute a method comprising:

determining VPN membership for each of a plurality of customer edge (CE) routers, each VPN being associated with at least one respective VPN route forwarding (VRF) table; and

attaching to each VRF table those CE routers having membership in the VPN associated with the respective VRF table.

18. The control device of claim 17, wherein said control device comprises one of a CE router and a PE router.

19. The control device of claim 18, wherein:

said CE router has associated with it respective customer (CUST), autonomous system number (ASN), interface (IF) and connected provider edge (PE) parameters, said parameters being utilized to determine an appropriate VRF table.

20. The control device of claim 17, further comprising:

adding a CE router to a first VPN, said CE router being attached to a first VRF table associated with a plurality of VPNs, said step of adding comprising;

if said CE router is the only CE router associated with said first VRF table, then adding at least one route target (RT) to the VRF table to associate the VRF table with the first VPN.