Patent Document

FIELD OF THE INVENTION 
   This invention relates to private network-to-network interfaces (PNNI), and more specifically to methods for constructing PNNI networks with optimized architecture. 
   BACKGROUND OF THE INVENTION 
   Private network-to-network interfaces (PNNI) refers to very large ATM networks that communicate between multiple private networks. A typical PNNI network is organized in peer groups. These are subunits of the total network that are interconnected as a group, with each group then interconnected in the PNNI network. An advantage of this architecture is that communications between members in a peer group can be independent of overall network management. When a communication between a node in one peer group and a node in another peer group is initiated, the PNNI protocol is used for that call set-up and management. The size of the peer groups, i.e. the number of nodes in each peer group, also affects the overall performance of the PNNI network. 
   Depending on the number of nodes served by the PNNI network, the architecture may be flat (non-hierarchical) or may have two or more hierarchical levels. When the network topology moves to multiple level architecture, several new effects on network performance are introduced. A primary motive for introducing new levels in a PNNI network is to increase routing efficiency and reduce call set-up time. However, added levels increase cost and management complexity. Thus there is an important trade-off when considering adding new hierarchical levels. A technique for resolving this trade-off is described and claimed in my co-pending application Ser. No. 10/346,460. 
   In both flat and multi-level networks, the size of the peer groups, i.e. the number of nodes in each peer group, affects the overall performance of the PNNI network. Thus the division of the network nodes into peer groups presents an important design variable that has not been generically solved previously in a rigorous fashion. 
   BRIEF STATEMENT OF THE INVENTION 
   According to the invention, a technique has been developed that evaluates important network performance parameters, for example, call set-up time, in terms of the peer group size. These are used to determine the optimum peer group size for a given PNNI network. 

   
     BRIEF DESCRIPTION OF THE DRAWING 
     The invention may be better understood when considered in conjunction with the drawing in which: 
     The FIGURE is a schematic diagram of a PNNI network showing a sample peer group configuration. 
   

   DETAILED DESCRIPTION OF THE INVENTION 
   With reference to  FIG. 1 , a flat topological PNNI network is represented. These networks typically have many nodes. For simplicity, the illustration shows relatively few nodes  11 , organized in peer groups as shown. The peer groups in the figure are illustrated as having five nodes per peer group. For the illustration, the peer group size is arbitrarily chosen. That design approach, more or less, typically with some empirical data or design experience, is used to determine the peer group size in conventional network designs. But a rigorous solution to the optimum peer group size, in terms of identifiably network performance parameters has not been available. The following section describes a rigorous approach to determining the optimum peer group size. 
   In the discussion that follows, let N be the total number of lowest-level nodes (i.e., the number of ATM switches). Let x 1  be the number of lowest-level nodes in each level-1 PG, and let x 2 =N/x 1  be the number of level-1 PGs (all variables are assumed to be continuous). 
   For a flat network, define            ={α|α&gt;1}. We assume the time complexity of computing a minimum cost path in a flat (non-hierarchical) network with z nodes is R 1 (z)=α 0 z α , where α 0 &gt;0 and αε         . For example, for Dijkstra&#39;s shortest path method we have a α=2.
   Certain nodes are identified as border nodes. A level-1 border node of a PG is a lowest-level node which is an endpoint of a trunk linking the PG to another level-1 PG. For example, if each U.S. state is a level-1 PG, and if there is a trunk from switch a in Chicago to switch b in Denver, then a and b are level-1 border nodes. Define Γ={γ|0≦γ&lt;1}. We assume the number of level-1 border nodes in a PG with x 1  lowest-level nodes is bounded above by B 1 (x 1 )=γ 0 x 1   γ , where γ 0 &gt;0 and γεΓ. The case where each PG has a constant number k of border nodes is modelled by choosing γ 0 =k and γ=0. The case where the border nodes are the (approximately 4√{square root over (x 1 )}) boundary nodes of a square grid of x 1  switches is modelled by choosing γ 0 =4 and γ=½. 
   Define            ={κ|0≦κ≦1}. We assume the total number of level-1 PGs, excluding the source level-1 PG, that the connection visits is bounded above by V 1 (x 2 )=κ 0 (x 2   κ −1), where κ 0 &gt;0 and κε         . Note that V 1 (1)=0, which means that in the degenerate case of exactly one level-1 PG, there are no PGs visited other than the source PG.
   This functional form for V 1 (x 2 ) is chosen since the expected distance between two randomly chosen points in a square with side length L is kL, where k depends on the probability model used: using rectilinear distance, with points uniformly distributed over the square, we have k=⅔; using Euclidean distance we have k=( 1/15)[2+√{square root over (2)}+5 log(√{square root over (2)}+1]≈0.521; with an isotropic probability model we have k=[(2√{square root over (2)}/(3π)]log(1+√{square root over (2)})≈0.264. If the x 2  PGs are arranged in a square grid, a random connection will visit approximately κ√{square root over (x 2 )}PGs. Choosing κ 0 =k and κ=½, the total number of PGs visited is approximately κ 0 x 2   κ . Choosing κ 0 =1 and κ=1 models the worst case in which the path visits each level-1 PG. 
   The source node of a connection sees the x 1  nodes in the source PG, and at most B 1 (x 1 ) border nodes in each of the x 2 −1 non-source PGs. A path computation is performed by the entry border node of at most V 1 (x 2 ) non-source PGs. In each non-source PG visited, the entry border node sees only the x 1  nodes in its PG when computing a path across the PG (or a path to the destination node, in the case of the destination PG), and so the path computation time complexity at each entry border node is R 1 (x 1 ). Hence the total path computation time is bounded above by R 1 (x 1 +(x 2 −1)B 1 (x 1 ))+V 1 (x 2 )R 1 (x 1 )=α 0 [x 1 +(x 2 −1)γ 0 x 1   γ ] α +κ 0 (x 2   κ −1)α 0 x 1   α . We ignore the constant factor α 0 . The optimization problem for a 2-level hierarchy is thus: minimize [x 1 +(x 2 −1)γ 0 x 1   γ ] α+κ   0 x 1   α (x 2   κ −1) subject to x 1 x 2 =N. 
   We next transform this optimization problem to a convex optimization problem (which has a convex objection function, a convex feasible region, and any local minimum is also a global minimum. We approximate x 2 −1 by x 2  and x 2   κ −1 by x 2   κ , yielding the objective function [x 1 +γ 0 x 1   γ x 2 ] α +κ 0 x 1   α x 2   κ , which also upper bounds the total path computation time. We rewrite the constraint x 1 x 2 =N as Nx 1   −1 x 2   −1 =1, which can be replaced by Nx 1   −1 x 2   −1 ≦1, since the inequality must be satisfied as an equality at any solution of the optimization problem. Letting y=x 1 +γ 0 x 1   γ x 2  yields the optimization problem: minimize y α +κ 0 x 1   α x 2   κ subject to x 1 +γ 0 x 1   γ x 2 ≦y and Nx 1   −1 x 2   −1 ≦1. The inequality constraint x 1 +γ 0 x 1   γx   2 ≦y must be satisfied as an equality in any solution; we rewrite this constraint as x 1 y −1 +γ 0 x 1   γ x 2 y −1 ≦1. Let s 1 =log x 1 , s 2 =log x 2 , s=(s 1 , s 2 ), and t=log y. Combining exponential terms, we obtain the optimization problem              2 (N):
 
minimize  f   2 ( s, t ) =e   αt   +κ   0   e   (αs     1     +κs     2     )   (1)
 
subject to  e   (s     1     −t) +γ 0   e   (γs     1     +s     2     −t) ≦1;  (2)
 
 Ne   (−s     1     −s     2     ) ≦1.  (3)
 
Problem            2 (N) it is a special type of convex optimization problem called a geometric program. Geometric programs are particularly well suited to engineering design, with a rich duality theory permitting particularly efficient solution methods.

   The following algorithm determines values for s 1  and s 2  that solve the optimization problem              2 (N). Thus, the algorithm determines the optimal x 1 (the optimal PG size) and the optimal x 2 (the optimal number of PGs).
   Step 1. Choose any  s =(  s   1 ,  s   2 ) such that e   s       1   e   s       2   =N, and choose  t  such that e   s       1   +γ 0 e (γ  s       1     +  s       2     ) =e   t   .   Step 2. Define ε 1 =e α  t   /f 2 (  s ,  t ) and ε 2 =κ 0 e (α  s       1     +κ  s       2     ) /f 2 (  s ,  t ).   Step 3. Define δ=(δ 1 , δ 2 , δ 3 , δ 4 ) by   

   
     
       
         
           
             
               δ 
               1 
             
             = 
             1 
           
           , 
           
             
               δ 
               2 
             
             = 
             
               
                 
                   
                     ε 
                     1 
                   
                   ⁢ 
                   
                     α 
                     ⁡ 
                     
                       ( 
                       
                         1 
                         - 
                         γ 
                       
                       ) 
                     
                   
                 
                 + 
                 
                   
                     ε 
                     2 
                   
                   ⁡ 
                   
                     ( 
                     
                       κ 
                       - 
                       α 
                     
                     ) 
                   
                 
               
               
                 2 
                 - 
                 γ 
               
             
           
           , 
           
             
               δ 
               3 
             
             = 
             
               
                 
                   ε 
                   1 
                 
                 ⁢ 
                 α 
               
               - 
               
                 δ 
                 2 
               
             
           
           , 
           
             
 
           
           ⁢ 
           
             
               δ 
               4 
             
             = 
             
               
                 
                   ε 
                   1 
                 
                 ⁢ 
                 α 
               
               + 
               
                 
                   ε 
                   2 
                 
                 ⁢ 
                 κ 
               
               - 
               
                 
                   δ 
                   2 
                 
                 . 
               
             
           
         
       
     
       
       Step 4. Define b 1 =log(N), b 2 =log (δ 2 /(ε 1 α)), and b 3 =log (δ 3 /(γ 0 ε 1 α)).
       Define (s, t)=(s 1 , s 2 , t) by
 
 s   1 =( b   1   +b   2   −b   3 )/(2−γ),  s   2   =b   1   −s   1   , t=s   1   =b   2 .
   and d=(s, t)−(  s ,  t ).   
     
       Step 5. Use any well-known technique (e.g., bisection) to obtain a value θ* solving the 1-dimensional optimization problem: minimize {f 2 ((  s ,  t )+θd)|0≦θ≦1}. If θ*τ for some small positive stopping tolerance τ, go to Step 6. Otherwise, set (  s ,  t )←(  s ,  t )+θ*d and go to Step 2. 
       Step 6. The optimal PG size is x 1 *=e   s       1    and the optimal number of PGs is x 2 *=e   s       2   . Stop. 
     
  
   For a three-level PNNI network, let N be the total number of lowest-level nodes, let x 1  be the number of lowest-level nodes in each level-1 PG, x 2  be the number of level-1 PGs in each level-2 PG, and x 3  be the number of level-2 PGs. Thus x 1 x 2 x 3 =N. 
   As for H=2, we assume the complexity of routing in a flat network with z lowest-level nodes is R 1 (z)=α 0 z α , where α 0 &gt;0 and αε           .
   As for H=2, certain nodes are identified as border nodes. A level-1 border node of a PG in a 3-level network is a lowest-level node which is an endpoint of a trunk linking the PG to another level-1 PG within the same level-2 PG. A level-2 border node of a PG in a 3-level network is a lowest-level node which is an endpoint of a trunk linking the PG to another level-2 PG within the same PNNI network. For example, suppose each country in the world is a level-2 PG, and each U.S. state is a level-1 PG. Then if there is a trunk from a switch a in Boston to a switch b in London, a and b are level-2 border nodes. 
   For h=1, 2, we assume that the number of level-h border nodes in a level-h PG with z lowest-level nodes is bounded above by B h (z)=γ 0 z γ , where γ 0 &gt;0 and γεΓ. Thus each level-1 PG has at most B 1 (x 1 )=γ 0 x 1   γ level-1 border nodes, and each level-2 PG has at most B 2 (x 1 x 2 )=γ 0 (x 1 x 2 ) γ  level-2 border nodes. 
   We assume that the total number of level-2 PGs, excluding the source level-2 PG, that the connection visits is bounded above by V 2 (x 3 )=κ o (x 3   κ 1), where κ 0 &gt;0 and κε           . Note that V 2 (1)=0, which means that in the degenerate case where there is one level-2 PG, there are no level-2 PGs visited other than the source level-2 PG. We assume that the total number of level-1 PGs visited within the source level-2 PG, excluding the source level-1 PG, is bounded above by V 1 (x 2 )=κ 0 (x 2   κ −1).
   The source node sees the x 1  nodes in its level-1 PG, at most B 1 (x 1 ) level-1 border nodes in each of the x 2 −1 level-1 PGs (excluding the source level-1 PG) in the same level-2 PG as the source, and at most B 2 (x 1 x 2 ) level-2 border nodes in each of the x 3 −1 level-2 PGs (excluding the source level-2 PG) in the PNNI network. Thus the total number of nodes seen by the source is bounded above by
 
 x   1 +( x   2 −1) B   1 ( x   1 )+( x   3 −1) B   2 ( x   1   x   2 )= x   1 +( x   2 −1)/γ 0   x   1   γ +( x   3 −1)γ 0 ( x   1   x   2 ) γ .
 
The time complexity of the source path computation is bounded above by
 
 R   1 ( x   1 +( x   2 −1) B   1 ( x   1 )+( x   3 −1) B   2 ( x   1 x 2 )).
 
   The total path computation time for all the level-1 PGs in the source level-2 PG, excluding the source level-1 PG, is at most V 1 (x 2 )R 1 (x 1 ). For z&gt;0, define R 2 (z)=ω 0 z ω . The total path computation time for each of the V 2 (x 3 ) level-2 PGs visited (other than the source level-2 PG) is, by definition, f 2 *(x 1 x 2 ), which by Theorem 2 is bounded above by R 2 (x 1 x 2 ). 
   To minimize the upper bound on the total path computation time for a three-level net-work, we solve the optimization problem:
 
minimize R 1 (x 1 +(x 2 −1) B   1 ( x   1 )+( x   3 −1) B   2 ( x   1   x   2 ))+ V   1 ( x   2 ) R   1 ( x   1 )+ V   2 ( x   3 ) R   2 ( x   1   x   2 )
 
subject to x 1 x 2 x 3 =N. We approximate x 2 −1 by x 2 , x 3 −1 by x 3 , x 2   κ −1 by x 2   κ , and x 3   κ −1 by x 3   κ , which preserves the upper bound. Introducing the variable y, we obtain the optimization problem: minimize α 0 y α +κ 0 x 2   κ α 0 x 1   α +κ 0 x 3   κ ω 0 (x 1 x 2 ) ω  subject to x 1 +x 2 γ 0 x 1   Γ +x 3 γ 0 +(x 1 x 2 ) γ ≦y and Nx 1   −1 x 2   −1 x 3   −1 ≦1. Letting s 1 =log x 1 , s 2 =log x 2 , s 3 =log x 3 , s=(s 1 , s 2 , s 3 ), and t=log y, we obtain the geometric program              3 (N):
 
minimize  f   3 ( s, t )=α 0 e αt +α 0 κ 0   e   (αs     1     +κs     2     ) +κ 0 ω 0   e   (ω(s     1     +s     2     )+κs     3     )   (4)
 
subject to  e   s     1     −t +γ 0   e   (γs     1     s     2     −t) +γ 0   e   (γ(s     1     +s     2     )+s     3     −t) ≦1  (5)
 
 Ne   (−s     1     −s     2     −s     3)   ≦1  (6)

   The following algorithm determines values for s 1 , s 2 , and s 3  that solve the optimization problem              3 (N). Thus, the algorithm determines the optimal x 1  (the optimal level-1 PG size), x 2  (the optimal number of level-1 PGs in each level-2 PG), and x 3  (the optimal number of level-2 PGs).
   Step 1. Choose any  s =(  s   1 ,  s   2 ,  s   3 ) such that e   s       1   e   s       2   e   s       3   =N, and choose  t  such that
 
 e     s       1   +γ 0   e   (γ  s       1     +  s       2     ) +γ 0 e (γ(  s       1     +  s       2     )+  s       3     )   =e     t   .
   Step 2. Define ε 1 =α 0 e α  t   /f 3 (  s ,  t ), ε 2 =α 0 κ 0 e (α  s       1     +κ  s       2     ) /f 3 (  s ,  t ), and ε 3 =κ 0 ω 0 e (ω(  s       1     +  s       2     )+κ  s       3     ) /f 3 (  s ,  t ).   

   Define (α 1 , α 2 , α 3 , α 4 )=(ε 2 α+ε 3 ω, ε 2 κ+ε 3 ω, ε 3 κ, ε 1 α).
     Step 3. Define δ=(δ 1 , δ 2 , δ 3 , δ 4 , δ 5 ) by δ 1 =1,
 
δ 3 =[(1−γ)(α 1 +α 4 )+(γ−2)α 2 +α 3 ]/(γ 2 −3γ+3),
 
δ 2 =(1−γ)δ 3 +α 2 −α 1 , δ 4 =α 4 −δ 2 −δ 3 , and δ 5 =α 2 +δ 3 +γδ 4 .
   Step 4. Define λ=δ 2 +δ 3 +δ 4 , and define b 1 =log(N), b 2 =log(δ 2 /λ), b 3 =log(δ 3 /(γ 0 λ)),
       and b 4 =log(δ 4 /(γ 0 λ)). Define (s, t)=(s 1 , s 2 , s 3 , t) by
 
 s   1   =[b   1   +b   2 (2−γ)+ b   3 (γ−1)− b   4 ]/(γ 2 −3γ+3),  t=s   1   −b   2   , s   2   =b   3   +t−γs   1 ,
   and s 3 =b 1 =s 1 −s 2 . Define d=(s, t)−(  s ,  t ).   
       Step 5. Use any well-known technique (e.g., bisection) to obtain a value θ* solving the 1-dimensional optimization problem: minimize {f 3 ((  s ,  t )+θd) |0≦θ≦1}. If θ*&lt;τ for some small positive stopping tolerance τ, go to Step 6. Otherwise, set (  s ,  t )←(  s ,  t )+θ*d and go to Step 2.   Step 6. The optimal level-1 PG size is x 1 *=e   s       1   , the optimal number of level-1 PGs in each level-2 PG is x 2 *=e   s       2   , and the optimal number of level-2 PGs is x 3 *=e   s       3   . Stop.   

   Various additional modifications of this invention will occur to those skilled in the art. All deviations from the specific teachings of this specification that basically rely on the principles and their equivalents through which the art has been advanced are properly considered within the scope of the invention as described and claimed.

Technology Category: h