Method for optimizing network "Point of Presence" locations

• US 20090290508A1
• Filed: 05/22/2008
• Published: 11/26/2009
• Est. Priority Date: 05/22/2008
• Status: Abandoned Application

• Current Assignee: AT&T Labs Incorporated (AT&T, Inc.)
• Original Assignee: AT&T Labs Incorporated (AT&T, Inc.)
• Inventors: Puthenpura, Sarat, Belanger, David G., Jotshi, Arun, Zhao, Wenjie, Parker, Sam Houston
• Application Number:
  US12/154,352
• Publication Number:
  US 20090290508A1
• Time in Patent Office: Days
• US Class Current: 370/254
• CPC Class Codes: H04L 12/2854 Wide area networks, e.g. public data networks
• 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/80 Ingress point selection by the source endpoint, e.g. selection of ISP or POP

Abstract

A methodology for optimizing the placement of network “Points of Presence” (POPs) across the carrier'"'"'s entire network (i.e., a “global” solution”) utilizes carefully constructed customer clustering and simulated annealing methodology to create a cost-efficient solution. The customer base is first partitioned into a plurality of clusters such that the customers within each cluster are closer to its centroid than the centroid of any other cluster (e.g., applying the k-means clustering algorithm or any other suitable method of partitioning the customer base). A linear algorithm process is used to minimize the costs associated with the number of placement of POPs within each cluster. A simulated annealing (SA) process is then used to iterate the entire set of potential POP locations until a compact, steady-state solution is achieved (or, alternatively, until a given number of iterations has been performed). In a preferred embodiment, a number of iterations are performed at each “temperature” in the simulating annealing process to further improve the result (this iterative process referred to in the art as “intensification”).

Claims

1. A method of optimizing the placement of a network carrier'"'"'s “

Point of Presences”

(POPs) facility locations across a communication network, the method comprising the steps of;

a) identifying a plurality of N customer facilities to be served by the network carrier, a plurality of F potential POP facility locations and a plurality of S access suppliers available for providing communication between the customer facilities and the POP facilities;

b) creating an initial solution Y_initial for associating each customer facility with a POP facility location through an access supplier; and

c) performing simulated annealing on the initial solution Y_initial for a predetermined number of iterations to achieve an optimized placement solution for the plurality of POP facility locations.

2. The method as defined in claim 1, wherein the initial solution is created by:

partitioning the plurality of N customer facilities into a set of CL clusters;

forming a locally optimized POP facility location solution for each cluster; and

combining the set of CL locally optimized solutions to form the initial solution Y_initial.

3. The method as defined in claim 2, where in performing the partitioning, each cluster is formed to have approximately the same number of customer facilities therein.

4. The method as defined in claim 2, where in performing the locally optimized POP facility location the follow steps are performed:

applying a linear algorithm process to obtain a minimal cost solution for the placement of at least one POP facility to service the customers within the cluster using a selected access supplier, for a given cluster i, the minimal cost solution defined as y(i) and the identified at least one POP facility defined as Y_i.

5. The method as defined in claim 2 wherein the plurality of N customer facilities are geographically partitioned into a plurality of CL separate customer clusters.

6. The method as defined in claim 1 wherein a k-means clustering process is used to form a plurality of CL separate customer clusters.

7. The method as defined in claim 6, wherein the k-means clustering process comprises the steps of:

i) randomly assigning each customer to a cluster;

ii) calculating the centroid C of each cluster;

iii) for each customer facility, determining the closest centroid and, if the closest centroid is within a different cluster, moving the customer facility to that cluster;

iv) repeating steps ii) and iii) until each customer facility is located in its closest cluster and no additional moves are performed in step iii); and

v) defining the results of step iv) as the k-means clustering solution.

8. The method as defined in claim 4, wherein the following analysis is performed separately for each cluster in the plurality of CL clusters:

$\mathrm{Min}<br><br>\underset{i\notin <br><br><br><br>N}{\sum <br><br>}<br><br><br><br>\underset{j\in <br><br><br><br>F}{\sum <br><br>}<br><br><br><br>\underset{k\in <br><br><br><br>S}{\sum <br><br>}<br><br>\left(C_{\mathrm{ijk}}+C_{\mathrm{ijk}}^{\mathrm{\prime <br><br>}}·<br><br>t\right)<br><br>x_{\mathrm{ijk}}+\underset{j\in <br><br><br><br>F}{\sum <br><br>}<br><br>\left(f_j+f_j^{\mathrm{\prime <br><br>}}·<br><br>t\right)<br><br>y_j,$

where C_ijk is the initial cost for providing service to customer circuit i to POP location j via supplier k, C_ijk is the recurring costs for the same, t is the time period, f_j is the initial cost for installing a POP facility at location j and f′

_j is the recurring costs for maintaining a POP facility at location j.

9. The method as defined in claim 8 wherein the analysis includes the following constraints:

$\underset{j\in <br><br><br><br>F}{\sum <br><br>}<br><br><br><br>\underset{k\in <br><br><br><br>S}{\sum <br><br>}<br><br><br><br>x_{\mathrm{ijk}}=1<br><br><br><br>\forall <br><br>i\in <br><br>N$

such that each customer circuit served by exactly one POP facility via exactly one access supplier; and

x_ijk≦

y_j ∀

i ε

N, j ε

F, k ε

S, such that a customer circuit is assigned to a POP facility j facility only if a POP facility is installed at location j.

10. The method as defined in claim 1, wherein in performing step c), the following steps are performed:

i) creating an alternative, nearby solution Y₁ relative to the initial solution Y_initial generated in step e);

ii) determining the minimal cost solution f(Y₁) for nearby solution Y₁ of step i);

iii) comparing the difference between f(Y₁) and f(Y_initial) and, if Y₁ provides a lower cost, replace Y_initial with Y₁ and move to step v), otherwise

iv) performing a random operation to determine if Y₁ should replace Y_initial as the lower cost solution; and

v) repeating steps i)-iv) until an optimized solution is achieved.

11. The method as defined in claim 10 wherein in performing step v), the process is repeated for a predetermined number of iterations.

12. The method as defined in claim 10 wherein in performing step v), the process is repeated until a minimal difference between Y₁ and Y_initial is achieved.

13. The method as defined in claim 10, wherein in performing step i), a neighborhood generation function is used to create the alternative, nearby solution.

14. The method as defined in claim 13 wherein the neighborhood generation function comprises the following steps:

if the total number of POP facility locations is equal to plurality of F potential POP facility locations, removing a random POP facility and defining the result as nearby solution Y₁;

otherwise,

generating a random fraction between zero and one; and

, for a random fraction in a first interval,

if the total number of POP facilities is greater than one, exchanging an open POP facility for a closed POP facility to create nearby solution Y₁, otherwise

if the random fraction is within a second interval, adding one closed POP facility to the plurality of open POP facilities to create nearby solution Y₁, otherwise

if the random fraction is within a third interval, exchanging an open POP facility for a closed POP facility to create nearby solution Y₁, otherwise

if the random fraction is within a fourth interval, adding one closed POP facility to the plurality of open POP facilities to create nearby solution Y₁, otherwise

removing one open POP facility to create nearby solution Y₁.

15. The method as defined in claim 10, wherein steps iii)-v) are repeated at a predetermined temperature variable T₀ for a predefined number of t cycles, providing intensification of the solution.

16. The method as defined in claim 15 wherein the number of cycles is shorted to be less than t if a predetermined number k₂ nearby solutions are selected as preferred solutions.

17. The method as defined in claim 15, wherein for each repetition of steps iii)-v) the temperature variable T₀ is modified as follows:

$T_0=\frac{T_0}{1+\mathrm{\beta <br><br>}<br><br><br><br>T_0},$

where

β

is a predetermined fractional value.