Distributing customer location access links across network provider nodes during network planning

• US 7,839,801 B2
• Filed: 12/12/2008
• Issued: 11/23/2010
• Est. Priority Date: 12/12/2008
• Status: Expired due to Fees

• Current Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Original Assignee: Verizon Patent and Licensing Incorporated (Verizon Communications Inc.)
• Inventors: Campbell, Gary L., Hubner, Paul
• Primary Examiner(s): Vu; Thong H
• Application Number:
  US12/333,512
• Publication Number:
  US 20100150028A1
• Time in Patent Office: 711 Days
• Field of Search: 370/237, 370/429, 370/353, 707/104, 707/2
• US Class Current: 370/255
• CPC Class Codes: H04L 12/2852 Metropolitan area networks
• CPC Class Codes: H04L 12/2854 Wide area networks, e.g. public data networks
• CPC Class Codes: H04L 41/145 involving simulating, designing, planning or modelling of a network
• CPC Class Codes: H04L 67/1001 for accessing one among a plurality of replicated servers
• CPC Class Codes: H04L 67/1021 based on client or server locations
• CPC Class Codes: H04W 28/086 among access entities
• CPC Class Codes: H04W 4/02 Services making use of location information
• CPC Class Codes: H04W 48/20 Selecting an access point

Abstract

A computing-device implemented network planning process distributes access links associated with customer locations to selected nodes of a provider network. The network planning process distributes the access links associated with the customer locations to the selected nodes of provider network such that overall latency goals for the network are met and such that the density of the connected customer locations to the network nodes in the network satisfy density requirements. The network planning process seeks diversity in customer location assignments by creating additional capacity through the re-assignment of customer locations to alternate network nodes in order to free up space on network nodes needed to off-load customer locations from other over-loaded network nodes. The network planning process permits an expanded ring of network nodes to accommodate dense customer traffic load across a wide area while meeting both individual connection and overall system requirements.

Claims

1. A non-transitory computer-readable medium containing instructions executable by at least one processor, the computer-readable medium comprising:

one or more instructions for obtaining a list of customer locations proposed to be connected to a network;

one or more instructions for obtaining a list of locations of network nodes of a network that is capable of providing network service to the customer locations;

one or more instructions for identifying nearest network nodes to a first customer location of the customer locations;

one or more instructions for ranking the identified nearest network nodes in order from closest to farthest from the first customer location to produce a ranked list;

one or more instructions for stepping through each network node in the ranked list until a network node is identified which will not be placed in an overloaded state if the first customer location is connected to the network node; and

one or more instructions for selecting the identified network node as the access node for the first customer location.

2. The non-transitory computer-readable medium of claim 1, where the network nodes comprise network provider edge (PE) nodes.

3. The non-transitory computer-readable medium of claim 1, where the customer locations each comprise one of customer premises equipment (CPE) or an additional network.

4. The non-transitory computer-readable medium of claim 1, further comprising:

one or more instructions for selecting a first distance range extending out from the first customer location,

where the one or more instructions for identifying nearest network nodes further comprises one or more instructions for identifying the nearest network nodes to the first customer location within the distance range.

5. The non-transitory computer-readable medium of claim 4, further comprising:

one or more instructions for selecting a second distance range extending out from the first customer location,

one or more instructions for identifying nearest network nodes to a first customer location of the customer locations within the second distance range;

one or more instructions for ranking the identified nearest network nodes in order from closest to farthest from the first customer location to produce a second ranked list;

one or more instructions for stepping through each network node in the second ranked list until a network node is identified which will not be placed in an overloaded state if the first customer location is connected to the network node; and

one or more instructions for selecting the identified network node as the access node for the first customer location.

6. The non-transitory computer-readable medium of claim 1, further comprising:

one or more instructions for determining if a distance between the identified network node and the first customer location is less than a distance limit,

where selecting the identified network node as the access node for the first customer location is based on whether the distance is less than the distance limit.

7. The non-transitory computer-readable medium of claim 1, further comprising:

one or more instructions for determining if selection of the identified network node as the access node for the first customer location achieves a certain load distribution.

8. The non-transitory computer-readable medium of claim 7, where the certain load distribution satisfies a specified load criterion that further satisfies overall network latency goads and customer location density parameters.

9. The non-transitory computer-readable medium of claim 1, further comprising:

one or more instructions for identifying nearest network nodes to a second customer location of the customer locations, where the second customer location is different than the first customer location;

one or more instructions for ranking the identified nearest network nodes in order from closest to farthest from the second customer location to produce a ranked list;

one or more instructions for stepping through each network node in the ranked list until a network node is identified which will not be placed in an overloaded state if the second customer location is connected to the network node; and

one or more instructions for selecting the identified network node as the access node for the second customer location.

10. A computing-device implemented method, comprising:

obtaining a list of customer locations proposed to be connected to a network;

obtaining a list of locations of network nodes of the network that is capable of providing network service to the customer locations;

identifying nearest network nodes to a first customer location of the customer locations;

ranking the identified nearest network nodes in order from closest to farthest from the first customer location to produce a ranked list;

stepping through each network node in the ranked list until a network node is identified which will not be placed in an overloaded state if the first customer location is connected to the network node;

determining if a distance between the identified network node and the first customer location is less than a distance limit; and

selecting the identified network node as the access node for the first customer location based on whether the distance is less than the distance limit.

11. The computing-device implemented method of claim 10, further comprising:

selecting a first distance range extending out from the first customer location,

where identifying nearest network nodes further comprises identifying the nearest network nodes to the first customer location within the distance range.

12. The computing-device implemented method of claim 11, further comprising:

selecting a second distance range extending out from the first customer location,

identifying nearest network nodes to a first customer location of the customer locations within the second distance range;

ranking the identified nearest network nodes in order from closest to farthest from the first customer location to produce a second ranked list;

stepping through each network node in the second ranked list until a network node is identified which will not be placed in an overloaded state if the first customer location is connected to the network node; and

selecting the identified network node as the access node for the first customer location.

13. The computing-device implemented method of claim 10, further comprising:

determining if a distance between the identified network node and the first customer location is less than a distance limit,

where selecting the identified network node as the access node for the first customer location is based on whether the distance is less than the distance limit.

14. The computing-device implemented method of claim 10, further comprising:

determining if selection of the identified network node as the access node for the first customer location achieves a certain load distribution.

15. The computing-device implemented method of claim 14, where the certain load distribution satisfies a specified load criterion that further satisfies overall network latency goals and customer location density parameters.

16. The computing-device implemented method of claim 10, where the network nodes comprise network provide edge (PE) nodes and where the customer locations each comprise one of customer premises equipment (CPE) or an additional network.

17. A computing-device, comprising:

means for obtaining a list of customer locations proposed to be connected to a network;

means for obtaining a list of locations of network nodes of the network that is capable of providing network service to the customer locations;

means for selecting a first customer location from the list of customer locations;

means for identifying nearest network nodes to the first customer location;

means for ranking the identified nearest network nodes to the first customer location in order from closest to farthest from the first customer location to produce a first ranked list;

means for selecting a second customer location from the list of customer locations;

means for identifying nearest network nodes to the second customer location;

means for ranking the identified nearest network nodes to the second customer location in order from closest to farthest from the second customer location to produce a second ranked list;

means for selectively stepping through each network node in the first ranked list and the second ranked list and comparing the respective network nodes in the first and second ranked lists to determine if the respective nodes are the same network node; and

means for swapping the same network node with a network node at a top of the first ranked list and for swapping the same network node with a network node at a top of the second ranked list.

18. The computing-device of claim 17, where the network nodes comprise network provider edge (PE) nodes.

19. The computing-device of claim 17, where the customer locations each comprise one of customer premises equipment (CPE) or an additional network.

20. The computing-device of claim 17, further comprising:

means for selecting a first distance range extending out from the first customer location,

where the means for identifying nearest network nodes to the first customer location further comprises means for identifying the nearest network nodes to the first customer location within the first distance range.