Complex node representation in an asynchronous transfer mode PNNI network

• US 6,456,600 B1
• Filed: 04/28/1999
• Issued: 09/24/2002
• Est. Priority Date: 04/28/1999
• Status: Expired due to Fees

• Current Assignee: Hewlett-Packard Development Company, L.P. (HP Inc.)
• Original Assignee: 3Com Corporation (HP Inc.)
• Inventors: Margolis, David, Morgenstern, Meir, Rochberger, Haim
• Primary Examiner(s): Ngo, Ricky
• Assistant Examiner(s): Phan, Tri H.
• Application Number:
  US09/300,882
• Time in Patent Office: 1,245 Days
• Field of Search: 370/238, 370/238.1, 370/254-257, 370/395.1, 370/396, 370/395.5, 370/395.51, 370/400, 370/408, 370/252, 709/220, 709/223
• US Class Current: 370/255
• CPC Class Codes: H04L 2012/5621 Virtual private network [VPN]; Private-network - network-interface (P-NNI)
• CPC Class Codes: H04L 2012/5623 Network design, dimensioning, topology or optimisation
• CPC Class Codes: H04L 45/02 Topology update or discovery
• CPC Class Codes: H04L 45/026 Details of "hello" or keep-alive messages
• CPC Class Codes: H04L 45/04 Interdomain routing, e.g. hierarchical routing
• CPC Class Codes: H04L 45/06 Deflection routing, e.g. hot-potato routing
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

A method of calculating a complex node representation for logical nodes in a hierarchical peer group in a PNNI based ATM network. The summary information for default spokes, exceptions and bypasses is determined in a way that closely represents the underlying metrics associated with the peer group. A list of all border nodes in the peer group is generated and maintained and a matrix of tables is generated, one table for each metric per each class of service. The table is populated by the best value associated with the corresponding metric for a particular pair of border nodes within a particular class of service. Once the table is populated, each element is placed in a group or bin. The bins are generated by dividing the full range of the metric into a plurality of smaller subgroups or bins. The bin having a count greater than a threshold count is selected and 80% of the worst value for that group is used as the default spoke. If no bin exists having at least a threshold count, the number of bins is reduced by one and a new set of subranges is calculated. The elements of the table are placed in the newly divided bins and a scan is performed once again.

Claims

1. In a Private Network to network Interface (PNNI) based Asynchronous Transfer Mode (ATM) network a method of determining a complex node representation for a logical node in a peer group, said method comprising the steps of:

generating a list of border nodes located within said peer group, each border node corresponding to a port in said logical node;

generating a plurality of tables, each table associated with a particular metric within a particular class of service, each table populated with a plurality of elements, each element representing an optimum metric between an associated pair of ports;

dividing the total range for each metric into M bins representing a subrange of said total range and placing said plurality of elements in said bins in accordance with an element'"'"'s value;

choosing a bin having an element count greater then a threshold and setting a default spoke value in accordance with the percentage of a value within the subrange of the bin corresponding thereto; and

wherein M is a positive integer.

2. The method according to claim 1, wherein said list comprises a linearly linked list.

3. The method according to claim 1, wherein said list comprises a circularly linked list.

4. The method according to claim 1, wherein the initial value of M is set to 5.

5. The method according to claim 1, wherein said default spoke is in accordance with a percentage of a value, said value comprising the worse value within said subrange.

6. The method according to claim 1, wherein said default spoke is in accordance with 80% of the worse value within said subrange.

7. In a Private Network to network Interface (PNNI) based Asynchronous Transfer Mode (ATM) network a method of determining a complex node representation for a logical node in a peer group, said method comprising the steps of:

generating a list of border nodes located within said peer group, each border node corresponding to a port in said logical node;

generating a plurality of tables, each table associated with a particular metric within a particular class of service, each table populated with a plurality of elements, each element representing an optimum metric between an associated pair of ports;

dividing the total range for each metric into M bins representing a subrange of said total range and placing said plurality of elements in said bins in accordance with an element'"'"'s value;

choosing a bin having an element count greater then a threshold and setting a default spoke value in accordance with the percentage of a value within the subrange of the bin corresponding thereto;

decrementing the number of bins M by one if no bin has an element count greater then said threshold and repeating said steps of dividing said total range, placing said plurality of elements in said bins and choosing a bin; and

wherein M is a positive integer.

8. The method according to claim 7, further comprising the step of choosing one group at random from among the two remaining bins when said number of bins M is decremented to two, and setting said default spoke in accordance with the percentage of a value within the subrange of said chosen bin.

9. The method according to claim 7, further comprising the step of combining the two remaining bins when said number of bins M is decremented to two, and setting said default spoke in accordance with the percentage of a value within the total range of the metric corresponding thereto.

10. The method according to claim 7, further comprising the step of choosing one group from among the three remaining bins when said number of bins M is decremented to three, and setting said default spoke in accordance with the percentage of a value within the subrange of said chosen bin.

11. The method according to claim 7, wherein said list comprises a linearly linked list.

12. The method according to claim 7, wherein said list comprises a circularly linked list.

13. The method according to claim 7, wherein the initial value of M is set to 5.

14. The method according to claim 7, wherein said default spoke is in accordance with a percentage of a value, said value comprising the worse value within said subrange.

15. The method according to claim 7, wherein said default spoke is in accordance with 80% of the worse value within said subrange.