Method for building virtual private networks using routers

• US 20060268740A1
• Filed: 05/24/2005
• Published: 11/30/2006
• Est. Priority Date: 05/24/2005
• Status: Active Grant

• Current Assignee: AT&T Corporation (AT&T, Inc.)
• Original Assignee: AT&T Corporation (AT&T, Inc.)
• Inventors: Uttaro, James, Rosenberg, Eric
• Granted Patent: US 7,583,617 B2
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 12/4641 Virtual LANs, VLANs, e.g. virtual private networks [VPN] LAN interconnection over a bridge based backbone H04L12/462; encapsulation techniques H04L12/4633; routing of packets H04L45/00; packet switches H04L49/00; virtual private networks for security H04L63/0272
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• 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

Abstract

A method for forming a communications network using routers. The first step is analyzing a router location to determine if the router location is VPN resource constrained or interface-constrained. The VPN resource constrained router network comprises at least at least two groups of routers and the same number of customer groups. The next step is connecting the first group of customers and routers, and the second group of customers and routers, using a round robin connectivity methodology and saving information in each router'"'"'s database. The interface-constrained router network, comprises no more routers than the value [Q*], wherein [Q*] represents the number of routers that can be used by a group of customers so that VPN resources will not be exhausted faster than interface resources for the group of routers, then connecting customers to the group of routers using a round robin connectivity methodology and saving information in each router'"'"'s database.

Claims

1. A method for forming a communications network using routers, wherein the method comprises the steps of:

a. analyzing a router location to determine if the router location is VPN resource constrained or interface constrained;

b. if the router location is interface constrained, form an interface constrained router network, comprising;

i. a group of routers numbering at most [Q*] wherein [Q*] represents the number of routers that can be used by a defined group of customers so that VPN resources will not be exhausted faster than interface resource for the group of routers;

ii. distributing customer connections for the defined group of customers over the group of routers numbering at most [Q*] using a round robin connectivity methodology; and

iii. saving information in a database on each connected customer; and

c. if the router location is not interface constrained, forming a VPN resource constrained router network.

2. The method of claim 1, wherein the step of forming a VPN constrained router network comprises:

i. at least a first group of routers and a second group of routers, and wherein the quantity of routers in each group of routers is equal or nearly equal;

ii. at least a first group of customers and a second group of customers, wherein the quantity of customers in each group of customers is equal or nearly equal, and wherein the number of groups of customers is equal to the number of groups of routers;

iii. connecting the first group of customers to the first group of routers, and the second group of customers to the second group of routers, using a round robin connectivity methodology, and if needed, connecting additional groups of customers to additional groups of routers; and

iv. saving information in a database on each connected customer.

3. The method of claim 1, wherein [Q*] is determined by dividing a quantity of VPN resources available from a router [R] by an average amount of VPN resource averaged over the defined group of customers[F] forming a value [VR], and then dividing a quantity of interfaces available from a router in the group of routers [B] by an average number of interfaces [P] averaged over the defined group of customers forming [IR], and then dividing [VR] by [IR], thus [Q*] equals [VR] divided by [IR].

4. The method of claim 1, wherein the analyzing of the router location comprises the steps of:

i. determining an average number of interfaces [P], averaged over a plurality of customers, needed to operate the communications network for a customer at the router location;

ii. determining a quantity of interfaces [B] available on a router at the router location;

iii. determining an average amount of VPN resources [F], averaged over the defined group of customers, needed to operate the communications network for the customer at the router location;

iv. determining an amount of VPN resource [R] available on the router;

v. dividing [B] by [P], forming an interface ratio [IR];

vi. dividing [R] by [F] forming a VPN resource ratio [VR]; and

if [IR] is greater than [VR], then forming the VPN constrained router network and if [VR] is greater than [IR] then forming the interface constrained router network.

5. The method of claim 1, further comprising the step of assigning colors to each group of routers when forming the VPN resource constrained network, and assigning corresponding colors to each group of customers when forming the VPN resource constrainted network.

6. The method of claim 1, wherein the round robin connectivity methodology initially comprises randomly selecting a router from the group of routers for the communication network and connecting the first interface for the customer to the selected router.

7. The method of claim 2, wherein the step of determining the average number of interfaces needed to operate a communication network for a customer is determined by using existing customer data at the router location.

8. The method of claim 2, wherein the step of determining the average amount of VPN resource needed to operate the communication network for a customer is determined by using existing customer data at the router location.

9. The method of claim 1, wherein the interface constrained router network is constrained by Border Gateway Protocol (BGP) sessions, policy maps, bandwidth or combinations thereof.

10. The method of claim 1, wherein the VPN constrained router network is constrained by a route constraint, memory constraint, or combinations thereof.

11. The method of claim 2, wherein the average number of interfaces [P] needed in a router location is from about 1 to about 50 BGP sessions.

12. The method of claim 2, wherein the average amount of VPN resource needed to operate the communication network is from about 10 to about 10,000 routes.

13. The method of claim 2, wherein the quantity of interfaces [B] is from about 500 to about 3000 BGP sessions.

14. The method of claim 2, wherein the VPN resource is from about 100,000 to about 1,000,000 routes.

15. The method of claim 1, wherein the communications network is a virtual private network.