| Method and apparatus of hierarchical node partitioning for address planning in pnni networks -> Monitor Keywords |
|
|
 
Method and apparatus of hierarchical node partitioning for address planning in pnni networksRelated Patent Categories: Multiplex Communications, Pathfinding Or Routing, Switching A Message Which Includes An Address Header, Message Transmitted Using Fixed Length Packets (e.g., Atm Cells), Connection Identifier AssignmentMethod and apparatus of hierarchical node partitioning for address planning in pnni networks description/claimsThe Patent Description & Claims data below is from USPTO Patent Application 20080056270, Method and apparatus of hierarchical node partitioning for address planning in pnni networks. Brief Patent Description - Full Patent Description - Patent Application Claims
[0001] This application is a continuation of co-pending application Ser. No. 10/748,942, filed Dec. 29, 2003 (currently allowed) which claims the benefit of U.S. Provisional Application No. 60/472,361 filed on May 21, 2003. Each of the above cited applications is herein incorporated by reference in their entirety. [0002] The present invention relates generally to communication networks and, more particularly, to a method and apparatus of effectively performing hierarchical node partitioning in an ATM PNNI network using ATM End System Address. BACKGROUND OF THE INVENTION [0003] In the PNNI routing and signaling protocol for ATM networks, switching nodes are organized into logical peer groups. Each node in a peer group has full details of the topology of that peer group, but only summary knowledge of the topology of other peer groups. Each ATM node requires a 160 bit address, called the ATM end system address (AESA), defined by the ATM Forum. All nodes in a given peer group have, for some value of k, where 0<=k<=104, identical values of the first k bits in their node AESAs. This value of k is called the PNNI level indicator. Judicious definition of peer groups and their corresponding level of PNNI hierarchy can create a logical partitioning of the ATM switches that increases PNNI routing efficiency and performance. A peer group with more than one node can itself be partitioned, leading to a tree representation of the hierarchies. When designing a hierarchy, nodes are often assigned to peer groups to form geographic clusters. If the hierarchy is not appropriately defined, changing it may require changing the AESA, which results in a temporary loss of service to customers. This leads to the problem of node partitioning to support both a current view of the hierarchy as well as possible future creation of both lower level and higher level peer groups. [0004] Therefore, a need exists for a method and apparatus to effectively design hierarchical node partitions in a PNNI network using ATM End System Addresses (AESAs). SUMMARY OF THE INVENTION [0005] In one embodiment, the present invention is a recursive method for creating a hierarchical partitioning of a set N of nodes in the plane and defining corresponding bit strings for the nodes. The bit string can be used to define the AESA, which in general contains other non-hierarchical information (e.g., which of the several possible AESA formats is being used). The partitioning is recursive: the first partitioning of N creates two sets N.sub.--0 and N.sub.--1; the partitioning method is then applied to both N.sub.--0 and N.sub.--1, and so on, until there are no more sets to partition (each node is in its own partition). [0006] Since the present invention partitions each set into exactly two pieces in one embodiment, the present invention can associate a bit string with each node in the set to be partitioned. Initially, before any partitioning has occurred, each bit in the bit string is initialized to the value zero. When the set of nodes represented by a given string is partitioned, the present invention assigns a 0 or 1 to the address string starting with the most significant bit first toward the least significant bit of the address string one bit at a time, to indicate the subdivision into two sets. When the partitioning halts, no two nodes will have an identical bit string. The required length of the bit string is L=ceiling(log2|N|), where |N| is the number of nodes in the set N and ceiling(x) is the smallest integer not less than x. [0007] Using this method, the present invention can create AESAs that will support the efficient use of PNNI routing as the number of switches in the network increases. At some network size, it is worthwhile creating a two level hierarchy. At some yet larger size, the present invention can easily split one or both of the lowest level peer groups and so on, up to L levels. This ability to scale requires a carefully designed address plan. [0008] This method differs from other methods in that the present invention only requires knowledge of switch locations and uses no link (e.g., trunk) information. This is advantageous since in practice the universe of potential switch locations is relatively easy to generate, while the set of trunks changes significantly as the network grows. Moreover, for a network that will grow, the present invention must create an addressing plan that includes locations that do not even have a switch yet, but may in the near future. BRIEF DESCRIPTION OF THE DRAWINGS [0009] The teaching of the present invention can be readily understood by considering the following detailed description in conjunction with the accompanying drawings, in which: [0010] FIG. 1 illustrates a diagram of 4 types of AESAs defined by the ATM Forum; [0011] FIG. 2 illustrates a block diagram of a communication network comprising a plurality of nodes; and [0012] FIG. 3 illustrates a flowchart of the present invention for creating hierarchical ATM addresses by recursive partitioning of the set of nodes. [0013] To facilitate understanding, identical reference numerals have been used, where possible, to designate identical elements that are common to the figures. DETAILED DESCRIPTION [0014] The present invention relates to data communication networks. These networks include, but are not limited to, Asynchronous Transfer Mode (ATM) networks. [0015] In an ATM network, each node requires a 160 bit address, called the ATM end system address (AESA), defined by ATM Forum. Three types of AESA used in specifications UNI 3.1, UNI Signaling 4.0, ILMI 4.0, PNNI version 1.0, etc., are shown in FIG. 1. The local AESA can be used for private purposes. The fields defined by the ATM Forum specifications are: [0016] AFI: Authority and Format Indicator. The value of this field determines the type of the AESA (e.g., DCC, ICD, E.164, Local) and also indicates what authority can assign codes (the structure and values of fields) in the rest of the AESA. [0017] DCC: Data Country Code. This type of AESA is assigned by ISO to national authorities (each country has a unique DCC code value). For AESAs using the DCC format, each country is free to decide the structure and rules for assignment of the Domain Specific Part (bytes 4-20). The AFI for a DCC is 39 and the value of the DCC field indicates the country. [0018] ICD: International Code Designator. An ICD is intended for use in the construction of internationally recognized codes. For AESAs using the ICD format, each ICD code point assignee is free to decide the structure and rules used for assignment of the Domain Specific Part (bytes 4-20). The AFI for an ICD is 47 and the value of the ICD field indicates to which code set or organization that particular ICD is assigned. [0019] E.164: An E.164 AESA can be constructed by populating the Initial Domain Identifier of the AESA with a valid E.164 address. The AFI for an E.164 AESA is 45. [0020] IDI: Initial Domain Identifier. The contents of this field vary depending on the value of the AFI. For example, with a DCC AESA (AFI=39), the IDI value of 0.times.840F identifies the United States. [0021] HO-DSP: High-Order Domain Specific Part. This field has meaning as defined by the address authority controlling the AESA and its delegate. This component (together with the AFI and IDI) is typically used within the network to identify a peer group. [0022] ESI: End-System Identifier. The ESI is usually an IEEE 802.2 Media Access Control (MAC) address. [0023] SEL: Selector. The selector is not used for ATM routing, but may be used by end systems. [0024] All nodes in a given peer group have, for some value of k, where 0<=k<=104, identical values of the first k bits in their node AESAs. This value of k is called the PNNI level indicator. Judicious definition of peer groups and their corresponding level indicators can create a logical partitioning of the ATM switches that increases PNNI routing efficiency and performance. A peer group with more than one node can itself be partitioned, leading to a tree representation of the hierarchies. A given physical switch can contain multiple nodes, where each node operates at a different level of the PNNI hierarchy. [0025] In practice, certain fields, such as the AFI field, IDI field, and part of the HO-DSP field, of the first 13 octets (104 bits) of the AESA are assigned by and registered with national or international authorities, depending on the AESA type used, responsible for address assignments. Therefore, only a subset of the lower order bits of the HO-DSP field can be freely assigned by a user or a network operator. The number of lower order bits that can be freely assigned by a user or a network operator varies depending on the AESA type used as well. The present invention addresses how those remaining lower order freely assignable k bits within HO-DSP field, where 0<k<=104, can be partitioned to design peer groups that increases PNNI routing and efficiency and performance. [0026] When designing a hierarchy, nodes are often assigned to peer groups to form geographic clusters. For example, Africa and Europe might be two large peer groups in the partitioning of a worldwide network. If both the Africa and Europe peer groups have the same PNNI level indicator with a string of k bits in length, then all node AESAs in Africa have the same first k bits, and similarly for Europe, but the first k bits in Africa and Europe are not identical. Additionally, within Africa the present invention might, for example, require all nodes in the same country to have the same first q bits, where k<q<=104. Even if the present invention currently chooses to not have a separate peer group for each country in Africa, the AESA should nonetheless be defined to allow this additional partitioning, in case it is desired later (for example, if the number of switches in Africa grows substantially). If the AESA is not appropriately defined, changing it requires temporarily downing the node, resulting in a loss of service to customers. This leads to the problem of defining AESAs to support both a current view of the hierarchy as well as possible future creation of both lower level and higher level peer groups. [0027] To address this criticality, the present invention provides a method and apparatus of effective hierarchical node partitioning for ATM address planning in an ATM network. [0028] Although the present invention applies to ATM Private Network to Network Interface (PNNI) networks using AESA, those skilled in the art will realize the present invention can be adapted, with suitable modifications and extensions, to Frame Relay and optical switch networks as well. Similar extensions are possible for Internet Protocol (IP)/MPLS networks. Continue reading about Method and apparatus of hierarchical node partitioning for address planning in pnni networks... Full patent description for Method and apparatus of hierarchical node partitioning for address planning in pnni networks Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Method and apparatus of hierarchical node partitioning for address planning in pnni networks patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Method and apparatus of hierarchical node partitioning for address planning in pnni networks or other areas of interest. ### Previous Patent Application: Inclusion of quality of service indication in header compression channel Next Patent Application: Method and apparatus for dynamically maintaining a routing database for a sip server Industry Class: Multiplex communications ### FreshPatents.com Support Thank you for viewing the Method and apparatus of hierarchical node partitioning for address planning in pnni networks patent info. IP-related news and info Results in 0.14489 seconds Other interesting Feshpatents.com categories: Electronics: Semiconductor , Audio , Illumination , Connectors , Crypto , 174 |
 * Protect your Inventions * US Patent Office filing 
PATENT INFO |
|
