Method and apparatus of hierarchical node partitioning for address planning in pnni networks

Abstract

Method and apparatus for hierarchical node partitioning for address planning in networks, e.g., PNNI ATM networks to perform judicious definition of peer groups to create a logical partitioning of the ATM switches that increases PNNI routing efficiency and performance.

1 . A method for partitioning and assigning addresses based on geographic node locations in a network, comprising: 
 defining a first bounding outline that contains a plurality of nodes within the network;    partitioning said first bounding outline into two smaller bounding outlines divided according to an aspect ratio of said first bounding outline and assigning address bits to an address string of each of said two smaller bounding outlines; and    recursively dividing each of said resulting smaller bounding outlines from said partitioning step until all smaller bounding outlines contain one node each.    
   
   
       2 . The method of  claim 1 , wherein said first bounding outline is a bounding rectangle expressed as:  
         xL =min of  x ( i ) where { i  in  N}     yL   0 =min of  y ( i ) where { i  in  N}     xH   0 =max of  x ( i ) where { i  in  N}     yH   0 =max of  y ( i ) where { i  in  N}   where N represents a set of nodes and x(i) and y(i) represent x and y coordinates of an i-th node within a set N, where a rectangle Z(N) whose lower left corner is (xL 0 ,yL 0 ) and whose upper right corner is (xH 0 , yH 0 ) is a bounding rectangle that contains N.    
   
   
       3 . The method of  claim 2 , wherein said aspect ratio, t, is expressed as follows:  
         t ( Z ( N ))=( yH   0   −yL   0 )/( xH   0   −xL   0 ).  
   
   
       4 . The method of  claim 1 , wherein said partitioning step comprises: 
 partitioning said first bounding outline parallel to a y-axis, if said aspect ratio is smaller than or equal to one; and    partitioning said first bounding outline parallel to the y-axis, if said aspect ratio is greater than one.    
   
   
       5 . The method of  claim 4 , wherein said partitioning step further comprising: 
 finding a value of x=x* such that a function        f 1(( Z ( N ),  x ))=| c 1( Z ( N ),  x )−size( N )/2|   is minimized, where c1(Z(N), x), defined over [xL 0 , xH 0 ], is a number of nodes in N that are contained in an outline whose lower left coordinate is (xL 0 , yL 0 ) and whose upper right coordinate is (x, yH 0 ).    
   
   
       6 . The method of  claim 4 , wherein said partitioning step further comprising: 
 finding a value of y=y* such that a function        f 2(( Z ( N ),  y ))=| c 2( Z ( N ),  y )−size( N )/2|   is minimized, where c2(Z(N), y), defined over [yL 0 , yH 0 ], is a number of nodes in N that are contained in an outline whose lower left coordinate is (xL 0 , yL 0 ) and whose upper right coordinate is (xH 0 , y).    
   
   
       7 . The method of  claim 4 , wherein one of said partitioning steps produces 2 smaller divided outlines, R — 0 and R — 1, where R — 0 contains all nodes N — 0 within an outline with lower left coordinates of (xL 0 , yL 0 ) and upper right coordinates of (x*, yH 0 ) and R — 1 contains all nodes N — 1 within an outline with lower left coordinates of (x*+1, yL 0 ) and upper right coordinates of (xH 0 , yH 0 ).  
   
   
       8 . The method of  claim 4 , wherein one of said partitioning steps produces 2 smaller divided outlines, R — 0 and R — 1, where R — 0 contains all nodes N — 0 within an outline with lower left coordinates of (xL 0 , yL 0 ) and upper right coordinates of (xH 0 , y*) and R — 1 contains all nodes N — 1 within an outline with lower left coordinates of (xL 0 , y*+1) and upper right coordinates of (xH 0 , yH 0 ).  
   
   
       9 . The method of  claim 7 , further comprising: 
 assigning a value of 0 to a most significant unassigned bit of an address string for R — 0 and a value of 1 to a most significant unassigned bit of an address string for R — 1.    
   
   
       10 . The method of  claim 8 , further comprising: 
 assigning a value of 0 to a most significantly unassigned bit of an address string for R — 0 and a value of 1 to a most significantly unassigned bit of an address string for R — 1.    
   
   
       11 . The method of  claim 1 , wherein said recursive dividing step terminates if each of the smaller bounding outlines contains only one node and wherein said addresses are AESA addresses.  
   
   
       12 . An apparatus for partitioning and assigning addresses based on geographic node locations in a network, comprising: 
 means for defining a first bounding outline that contains a plurality of nodes within the network;    means for partitioning said first bounding outline into two smaller bounding outlines divided according to an aspect ratio of said first bounding outline and assigning address bits to an address string of each of said two smaller bounding outlines; and    means for recursively dividing each of said resulting smaller bounding outlines from said partitioning step until all smaller bounding outlines contain one node each.    
   
   
       13 . The apparatus of  claim 12 , wherein said first bounding outline is a bounding rectangle expressed as:  
         xL   0 =min of  x ( i ) where { i  in  N}     yL   0 =min of  y ( i ) where { i  in  N}     xH   0 =max of  x ( i ) where { i  n  N}     yH   0 =max of  y ( i ) where { i  in  N}   where N represents a set of nodes and x(i) and y(i) represent x and y coordinates of an i-th node within a set N, where a rectangle Z(N) whose lower left corner is (xL 0 ,yL 0 ) and whose upper right corner is (xH 0 , yH 0 ) is a bounding rectangle that contains N.    
   
   
       14 . The apparatus of  claim 13 , wherein said aspect ratio, t, is expressed as follows:  
         t ( Z ( N ))=( yH   0   −yL   0 )/( xH   0   −xL   0 ).  
   
   
       15 . The apparatus of  claim 12 , wherein said partitioning means partitions said first bounding outline parallel to a y-axis, if said aspect ratio is smaller than or equal to one; and partitions said first bounding outline parallel to a y-axis, if said aspect ratio is greater than one.  
   
   
       16 . A computer-readable medium having stored thereon a plurality of instructions, the plurality of instructions including instructions which, when executed by a processor, cause the processor to perform the steps comprising of: 
 defining a first bounding outline that contains a plurality of nodes within the network;    partitioning said first bounding outline into two smaller bounding outlines divided according to an aspect ratio of said first bounding outline and assigning address bits to an address string of each of said two smaller bounding outlines; and    recursively dividing each of said resulting smaller bounding outlines from said partitioning step until all smaller bounding outlines contain one node each.    
   
   
       17 . The computer-readable medium of  claim 16 , wherein said first bounding outline is a bounding rectangle expressed as:  
         xL   0 =min of  x ( i ) where { i  in  N}     yL   0 =min of  y ( i ) where { i  in  N}     xH   0 =max of  x ( i ) where { i  in  N}     yH   0 =max of  y ( i ) where { i  in  N}   where N represents a set of nodes and x(i) and y(i) represent x and y coordinates of an i-th node within a set N, where a rectangle Z(N) whose lower left corner is (xL 0  ,yL 0 ) and whose upper right corner is (xH 0 , yH 0 ) is a bounding rectangle that contains N.    
   
   
       18 . The computer-readable medium of  claim 17 , wherein said aspect ratio, t, is expressed as follows:  
         t ( Z ( N ))=( yH   0   −yL   0 )/( xH   0   −xL   0 ).  
   
   
       19 . The computer-readable medium of  claim 16 , wherein said partitioning step comprises: 
 partitioning said first bounding outline parallel to the y-axis, if said aspect ratio is smaller than or equal to one; and    partitioning said first bounding outline parallel to the y-axis, if said aspect ratio is greater than one.    
   
   
       20 . The computer-readable medium of  claim 16 , wherein said recursive dividing step terminates if each of the smaller bounding outlines contains only one node.