Method and tool for producing a telecommunication network

• US 6,628,618 B1
• Filed: 11/05/1999
• Issued: 09/30/2003
• Est. Priority Date: 05/06/1997
• Status: Active Grant

• Current Assignee: Telefonaktiebolaget LM Ericsson
• Original Assignee: Telefonaktiebolaget LM Ericsson
• Inventors: Cinkler, Tibor
• Primary Examiner(s): Marcelo, Melvin
• Assistant Examiner(s): Ferris, Derrick W.
• Application Number:
  US09/434,443
• Time in Patent Office: 1,425 Days
• Field of Search: 370/229, 370/235, 370/237, 370/238, 370/241, 370/252, 370/253, 370/351, 370/400, 455/352, 379/912
• US Class Current: 370/238
• CPC Class Codes: H04L 45/12 Shortest path evaluation
• CPC Class Codes: H04L 45/122 by minimising distances, e.g. by selecting a route with minimum of number of hops

Abstract

The invention concerns a method for producing a telecommunication network, comprising the steps of determining geographical locations of exchange nodes and equivalent distances between these, and traffic capacities between node pairs based on the expected traffic volume between the respective nodes. The node pairs are at first sorted such that an expression S for each node pair is non-decreasing, S being a strictly monotonic increasing function of the equivalent distance and a strictly monotonic decreasing function of the traffic capacity between the nodes of the pair. For each node pair in this order, then a path P is selected for implementation among all possible paths, which path P satisfies the condition that (I) is minimum. In this expression k, n is an index for all links of the path and for all links of the path not yet selected for implementation in any previous step, respectively, C1 is selected in accordance with link implementation costs per distance unit, C2 is selected in accordance with link implementation costs per distance unit and per traffic capacity unit, Dk and Dn are the equivalent distances for the node pair belonging to link k and to link n, respectively $\begin{array}{cc}C\left(P\right)=T\left(i,j\right)·\sum _k\mathrm{C2}·\mathrm{Dk}+\sum _n\mathrm{C1}·\mathrm{Dn}.& \left(I\right)\end{array}$

Claims

1. A method of producing a telecommunication network, comprising the steps:

a) determining geographical locations of m network exchange nodes N1 to Nm, m being a positive integer;

b) determining equivalent distances D(i,j) between all pairs Ni, Nj of said nodes based on the relative geographical locations of the nodes Ni, Nj of each pair wherein i,j ε

{1 , . . . , m} and i≈

j;

c) determining traffic capacities T (i,j) between all pairs of nodes Ni, Nj based on the expected amount of traffic to be carried between node Ni and node Nj;

d) for all node pairs Ni, Nj, evaluating an expression S(i,j) which is a strictly monotonic increasing function of D(i,j) and a strictly monotonic decreasing finction of T(i,j);

e) ordering the node pairs Ni, Nj such that S(i,j) is non decreasing; and

f) selecting in said order f or each node pair Ni, Nj among all possible paths each consisting of at least one link connecting two nodes, a path P between node Ni and Nj for implementation, for which path P $C<br><br>\left(P\right)=T<br><br>\left(i,j\right)·<br><br>\underset{k}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{C2}·<br><br>\mathrm{Dk}+\underset{n}{\sum <br><br>}<br><br>\text{\hspace{1em}<br><br>}<br><br>\mathrm{C1}·<br><br>\mathrm{Dn}$

 

is minimum,

k being an index for all links of the path;

n being an index for all links not yet selected for implementation in any previous step, of the path,

C1 being a positive real number selected in accordance with link implementation costs per unit distance,

C2 being a positive real number selected in accordance with link implementation costs per unit distance and per unit traffic capacity;

Dk and Dn, respectively, being the equivalent distance for the pair of nodes associated with link k, and link n, respectively.

2. The method of producing a telecommunication network of claim 1, further comprising the following steps repeated for q=2 to Q, Q being a positive integer greater than one and predetermined in accordance with the connectivity of the telecommunication network:

g) for each node Ni of degree less than q, selecting an associated node Nj for which D(i,j) is minimum;

h) for each pair of nodes Ni, Nj of step g), selecting for implementation a q-th path Pq among all possible paths between Ni and Nj not having any link in common with any other path between Ni and Nj already selected in a previous step, for which path Pq the expression C(Pq) is minimum;

i) for all remaining node pairs Ni, Nj selecting for implementation a q-th path Pq among all possible paths between Ni and Nj satisfying at least one of the conditions

not having any link in common with any other path between Ni and Nj already selected for implementation in a previous step, for which path the expression C(Pq) is minimum,

not having any node in common with any other path between Ni and Nj already selected for implementation in a previous step, for which path the expression C(Pq) is minimum.

3. The method of producing a telecommunication network of claim 2, wherein step g) further comprises the steps of:

g1) sorting the pairs of nodes Ni, Nj of step g) in an order such that S(i,j) is non-decreasing, S(i,j) being a real number between 0 and 1;

g2) performing step h) in the order according to step g1).

4. The method of producing a telecommunication network of claim 1, comprising the step of decreasing C2 after selecting a path for implementation.

5. The method of producing a telecommunication network of claim 2, comprising the steps performed for each pair of nodes Ni, Nj:

j) among all paths selected for implementation between Ni and Nj, finding a primary path for which the sum over all its links of the link lengths is minimum; and

k) increasing a traffic capacity value of each link of said path by said traffic capacity determined in step c).

6. The method of claim 5, comprising the steps performed for each link selected for implementation, of the network:

1) among all paths connecting a respective node pair Ni, Nj connected by a primary path comprising the link, finding a secondary path other than the primary path found in step j), for which the sum over all its links of the link lengths is minimum; and

m1) for each link of the secondary paths between all node pairs Ni, Nj satisfying the node pair condition of step

     1), obtaining the sum TC of the traffic capacities of all secondary paths which include it;

the traffic capacity of a secondary path being equal to the traffic capacity of its associated primary path;

m2) setting its backup traffic capacity value B to the maximum of the sum TC and of a backup traffic capacity value B assigned to it in a previous step; and

m3) obtaining its link traffic capacity Tk as the sum of the primary link traffic capacity obtained in step k) and of its backup capacity B.

7. The method of producing a telecommunication network of claim 1, wherein the equivalent distance between a pair of nodes is determined in proportion to the geographical distance between the nodes.

8. The method of producing a telecommunication network of claim 1, wherein the equivalent distance between a pair of nodes is determined in proportion to costs arising for the implementation of a link having unit traffic capacity between the pair of nodes.

9. The method of producing a telecommunication network of claim 1, wherein

10. The method of producing a telecommunication network of claim 1, wherein S(i,j) is a strictly monotonously increasing function of the number K(i) of links already selected for implementation and connected to node Ni, and of the number K(j) of links already selected for implementation and connected to node Nj.

11. The method of producing a telecommunication network of claim 10, wherein

12. The method of producing a telecommunication network of claim 6, further comprising the steps of:

n) for each link k selected for implementation, calculating a coefficient n in proportion to a link implementation effort LC(k)=C2·

Dk·

Tk+C1·

Dk and inversely proportional to the physical link length and to the traffic capacity Tk of the link;

o) calculating the sum Σ

LC of LC(k) over all links k selected for implementation;

p) for a link with the highest coefficient η

, performing the steps of;

p1) determining paths selected for implementation between node pairs Ni, Nj which paths use the respective link;

p2) for each path determined in step p1) selecting an additional path for implementation between the nodes Ni, Nj of the path determined in step p1) said additional path not having any link in common with the path determined in step p1);

p3) calculating link traffic capacities according to steps to m) for the links of all paths between nodes Ni and Nj including the additional path but excluding the path determined in step p1);

p4) calculating the sum Σ

LC of LC(k) over all links k selected for implementation, of the network;

p5) comparing the sum obtained in step o) with the sum obtained in step p4); and

p6) if the sum obtained in step p5) is smaller than the sum obtained in step o), discard the selection of the link of step p) else discard the selection for implementation of the additional path of step p2).

13. The method of producing a telecommunication network of claim 1, comprising the step of implementing the links of each path selected for implementation.

14. A tool for producing a telecommunication network, comprising

means for inputting and storing data related to equivalent distances between a plurality of pairs of exchange nodes of a telecommunication network and to traffic capacities to be provided between each pair of nodes;

means including a central processing unit, a working memory and a read only memory, adapted to perform a method according to any one of claims 1 to 12; and

means for outputting pairs of nodes selected for connection by a link, in accordance with the paths selected for implementation.