METHOD AND APPARATUS OF HIERARCHICAL NODE PARTITIONING FOR ADDRESS PLANNING IN PNNI NETWORKS

• US 20080056270A1
• Filed: 10/31/2007
• Published: 03/06/2008
• Est. Priority Date: 05/21/2003
• Status: Abandoned Application

• Current Assignee: Eric Rosenberg
• Original Assignee: Eric Rosenberg
• Inventors: ROSENBERG, ERIC
• Application Number:
  US11/930,271
• Publication Number:
  US 20080056270A1
• Time in Patent Office: Days
• US Class Current: 370/395.3
• CPC Class Codes: H04L 12/5601 Transfer mode dependent, e.g. ATM
• CPC Class Codes: H04L 2012/5621 Virtual private network [VPN]; Private-network - network-interface (P-NNI)
• CPC Class Codes: H04L 2012/5685 Addressing issues
• CPC Class Codes: H04L 2101/604 Address structures or formats
• CPC Class Codes: H04L 61/50 Address allocation

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.

Claims

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₀=min of y(i) where {i in N}
xH₀=max of x(i) where {i in N}
yH₀=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₀,yL₀) and whose upper right corner is (xH₀, yH₀) 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₀−

yL₀)/(xH₀−

xL₀).

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

f1((Z(N), x))=|c1(Z(N), x)−

size(N)/2|

is minimized, where c1(Z(N), x), defined over [xL₀, xH₀], is a number of nodes in N that are contained in an outline whose lower left coordinate is (xL₀, yL₀) and whose upper right coordinate is (x, yH₀).

6. The method of claim 4, wherein said partitioning step further comprising:

finding a value of y=y* such that a function

f2((Z(N), y))=|c2(Z(N), y)−

size(N)/2|

is minimized, where c2(Z(N), y), defined over [yL₀, yH₀], is a number of nodes in N that are contained in an outline whose lower left coordinate is (xL₀, yL₀) and whose upper right coordinate is (xH₀, 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₀, yL₀) and upper right coordinates of (x*, yH₀) and R_—

1 contains all nodes N_—

1 within an outline with lower left coordinates of (x*+1, yL₀) and upper right coordinates of (xH₀, yH₀).

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₀, yL₀) and upper right coordinates of (xH₀, y*) and R_—

1 contains all nodes N_—

1 within an outline with lower left coordinates of (xL₀, y*+1) and upper right coordinates of (xH₀, yH₀).

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₀=min of x(i) where {i in N}
yL₀=min of y(i) where {i in N}
xH₀=max of x(i) where {i n N}
yH₀=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₀,yL₀) and whose upper right corner is (xH₀, yH₀) 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₀−

yL₀)/(xH₀−

xL₀).

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₀=min of x(i) where {i in N}
yL₀=min of y(i) where {i in N}
xH₀=max of x(i) where {i in N}
yH₀=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₀ ,yL₀) and whose upper right corner is (xH₀, yH₀) 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₀−

yL₀)/(xH₀−

xL₀).

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.