Topology aggregation using parameter obtained by internodal negotiation

• US 6,385,201 B1
• Filed: 04/29/1998
• Issued: 05/07/2002
• Est. Priority Date: 04/30/1997
• Status: Expired due to Term

• Current Assignee: NEC Corporation
• Original Assignee: NEC Corporation
• Inventors: Iwata, Atsushi
• Primary Examiner(s): Chin, Wellington
• Assistant Examiner(s): Duong, Frank
• Application Number:
  US09/069,121
• Time in Patent Office: 1,469 Days
• Field of Search: 370/230, 370/235, 370/237, 370/238, 370/252, 370/253, 370/395.1, 370/395.2, 370/395.21, 370/395.32, 370/395.41, 370/400, 370/408, 370/254, 370/255, 709/241, 709/242
• US Class Current: 370/400
• CPC Class Codes: H04L 2012/562 Routing
• CPC Class Codes: H04L 2012/5621 Virtual private network [VPN]; Private-network - network-interface (P-NNI)
• CPC Class Codes: H04L 2012/5634 In-call negotiation
• CPC Class Codes: H04L 2012/5638 Services, e.g. multimedia, GOS, QOS
• CPC Class Codes: H04L 49/205 Quality of Service based
• CPC Class Codes: H04L 49/25 Routing or path finding in a switch fabric
• CPC Class Codes: H04L 49/3081 ATM peripheral units, e.g. policing, insertion or extraction
• CPC Class Codes: H04L 49/55 Prevention, detection or correction of errors
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections
• CPC Class Codes: H04Q 3/0062 Provisions for network management

Abstract

In a hierarchical network, an aggregation parameter is exchanged between a node and its neighbor to agree on a negotiated parameter. A set of physical links between them are aggregated into a logical link according to the negotiated parameter and resource data of the logical link is stored in a database of each node. The resource data is then exchanged between them and the contents of the database of each node are updated with resource data of its neighbor. To optimize the link aggregation, an operating performance of the logical link is evaluated by the node using traffic data from the network, and the negotiated parameter is updated according to the detected operating performance. The updated aggregation parameter of the node is exchanged with its neighbor to agree on a negotiated updated parameter which is used to aggregate the physical links into the logical link.

Claims

1. A network node for a communication network in which said node is one of a plurality of network nodes, the network node comprising:

negotiating means for exchanging aggregation parameters with a neighbor node to agree on a negotiated aggregation parameter;

link aggregating means for aggregating a plurality of physical links between the network node and a neighbor node into a logical link according to the negotiated aggregation parameter;

a database for storing resource data of said logical link; and

means for exchanging the resource data with said neighbor node and updating contents of said database with resource data of said neighbor node.

2. The network node of claim 1, wherein said plurality of network nodes are divided into a plurality of peer groups, and said neighbor node shares one of said peer groups in common with said network node.

3. The network node of claim 1, wherein each of said physical links is represented by a resource vector and each element of the vector is represented by a resource value of a different resource class, and wherein said logical link is represented by a resource vector and each element of the vector is represented by a sum of a maximum resource value, multiplied by the aggregation parameter, of the elements of the resource vectors of the physical links and a minimum resource value, multiplied by unity minus the aggregation parameter, of the elements of the resource vectors of the physical links.

4. The network node of claim 1, wherein each of said physical links is represented by a resource vector and each element of the vector is represented by a quality-of-service value of a different class, and wherein said logical link is represented by a resource vector and each element of the vector is represented by a sum of a maximum quality-of-service value, multiplied by the aggregation parameter, of the elements of the resource vectors of the physical links and a minimum quality-of-service value, multiplied by unity minus the aggregation parameter, of the elements of the resource vectors of the physical links.

5. The network node of claim 1, further comprising:

link performance evaluation means for evaluating an operating performance of said logical link by using traffic data from the network; and

update means for updating the negotiated aggregation parameter according to the detected operating performance,

said negotiating means exchanging the updated aggregation parameter with said neighbor node to agree on a negotiated aggregation parameter,

said link aggregating means aggregating said physical links into a logical link according to the negotiated aggregation parameter and storing resource data of the logical link into said database.

6. The network node of claim 1, further comprising means for organizing said physical links into a plurality of groups according to similarities of resource classes of said physical links,

said aggregating means aggregating the physical links of each of said groups into a logical link according to the negotiated aggregation parameter and storing resource data of the logical link into said database.

7. The network node of claim 6, further comprising:

link group performance evaluation means for detecting an operating performance of each of said groups of physical links; and

update means for updating the negotiated aggregation parameter according to the detected operating performance,

said negotiating means exchanging the updated aggregation parameter with said neighbor node to agree on a negotiated updated aggregation parameter,

said link aggregating means aggregating said physical links of each of said groups into a logical link according to the negotiated updated aggregation parameter and storing resource data representing the logical link into said database.

8. A peer group leader node of a peer group in a communication network in which a plurality of interconnected nodes are divided into a plurality of peer groups, each peer group having border nodes via which the peer group is interconnected with other peer groups, comprising:

negotiating means for exchanging aggregation parameters with other peer group leader nodes to agree on negotiated aggregation parameters;

topology aggregating means for aggregating physical topology of the border nodes of said peer group into a logical star topology using said negotiated aggregation parameters;

a database for storing resource data of said logical star topology; and

routing means for exchanging the resource data with a neighbor peer group leader node and updating the database with resource data from the neighbor peer group leader node.

9. The peer group leader node of claim 8, further comprising:

star topology performance evaluation means for evaluating an operating performance of the star topology by using traffic data from the network;

update means for updating the negotiated aggregation parameters according to the evaluated operating performance,

said negotiating means exchanging the updated aggregation parameters with other peer group leader nodes to agree on negotiated updated aggregation parameters,

said topology aggregating means aggregating said physical topology using the negotiated updated aggregation parameters.

10. The peer group leader node of claim 8, wherein said topology aggregating means is arranged to:

a) organize the border nodes of the peer group into a predetermined topology,

b) calculate initial least costs of links of the topology,

c) organize said border nodes into a star topology in which the border nodes are represented as a nucleus and ports,

d) determine aggregation parameters for links of the star topology using said initial least costs,

e) recalculate second least costs of said predetermined topology using the aggregation parameters,

f) aggregate physical links between said nucleus and said ports into logical links according to said aggregation parameter,

g) determine a plurality of differences between the initial least costs and the second least costs,

h) determine a link having a maximum value of said differences if said maximum value is greater than a convergence threshold value, and

i) interconnect adjacent ones of said ports with said link bypassing the nucleus.

11. The peer group leader node of claim 10, wherein said predetermined topology is a mesh topology.

12. The peer group leader node of claim 8, wherein said topology aggregating means is arranged to:

aggregate physical links between two peer groups into a logical link; and

remove one of said ports from the star topology corresponding to one of said physical links.

13. The peer group leader node of claim 10, wherein said negotiating means is further arranged to exchange the convergence threshold value with other peer group leader nodes to agree on a negotiated convergence threshold value,

said topology aggregating means determining said link having a maximum value of said differences if said maximum value is greater than the negotiated convergence threshold value.

14. A communication network comprising:

a plurality of network nodes organized into a plurality of interconnected peer groups, each of said peer groups having a peer group leader node and a plurality of border nodes through which the at least one peer group is connected to other peer groups;

each network node comprising;

negotiating means for exchanging aggregation parameters with a neighbor node of the same peer group to agree on a negotiated aggregation parameter;

link aggregating means for aggregating a plurality of physical links between the network node and a neighbor node into a logical link according to the negotiated aggregation parameter;

a database for storing resource data of said logical link; and

means for exchanging the resource data with said neighbor node and updating contents of said database with resource data of said neighbor node,

each group leader node comprising;

negotiating means for exchanging aggregation parameters with other peer group leader nodes to agree on negotiated aggregation parameters;

topology aggregating means for aggregating physical topology of the border nodes of said peer group into a logical star topology using said negotiated aggregation parameters;

a database for storing resource data of said logical star topology; and

routing means for exchanging the resource data with a neighbor peer group leader node and updating the database with resource data from the neighbor peer group leader node.

15. The communication network of claim 14, wherein said plurality of network nodes are divided into a plurality of peer groups, and said neighbor node shares one of said peer groups in common with said network node.

16. The communication network of claim 14, wherein each of said physical links is represented by a resource vector and each element of the vector is represented by a resource value of a different resource class, and wherein said logical link is represented by a resource vector and each element of the vector is represented by a sum of a maximum resource value, multiplied by the aggregation parameter, of the elements of the resource vectors of the physical links and a minimum resource value, multiplied by unity minus the aggregation parameter, of the elements of the resource vectors of the physical links.

17. The communication network of claim 14, wherein each of said physical links is represented by a resource vector and each element of the vector is represented by a quality-of-service value of a different class, and wherein said logical link is represented by a resource vector and each element of the vector is represented by a sum of a maximum quality-of-service value, multiplied by the aggregation parameter, of the elements of the resource vectors of the physical links and a minimum quality-of-service value, multiplied by unity minus the aggregation parameter, of the elements of the resource vectors of the physical links.

18. The communication network of claim 14, further comprising:

link performance evaluation means for evaluating an operating performance of said logical link by using traffic data from the network; and

update means for updating the negotiated aggregation parameter according to the detected operating performance,

said negotiating means exchanging the updated aggregation parameter with said neighbor node to agree on a negotiated aggregation parameter,

said link aggregating means aggregating said physical links into a logical link according to the negotiated aggregation parameter and storing resource data of the logical link into said database.

19. The communication network of claim 14, further comprising means for organizing said physical links into a plurality of groups according to similarities of resource classes of said physical links,

said aggregating means aggregating the physical links of each of said groups into a logical link according to the negotiated aggregation parameter and storing resource data of the logical link into said database.

20. The communication network of claim 19, further comprising:

link group performance evaluation means for detecting an operating performance of each of said groups of physical links; and

update means for updating the negotiated aggregation parameter according to the detected operating performance,

said negotiating means exchanging the updated aggregation parameter with said neighbor node to agree on a negotiated updated aggregation parameter,

said link aggregating means aggregating said physical links of each of said groups into a logical link according to the negotiated updated aggregation parameter and storing resource data representing the logical link into said database.

21. The communication network of claim 14, further comprising:

star topology performance evaluation means for evaluating an operating performance of the star topology by using traffic data from the network;

update means for updating the negotiated aggregation parameters according to the evaluated operating performance,

said negotiating means exchanging the updated aggregation parameters with other peer group leader nodes to agree on negotiated updated aggregation parameters,

said topology aggregating means aggregating said physical topology using the negotiated updated aggregation parameters.

22. The communication network of claim 14, wherein said topology aggregating means is arranged to:

a) organize the border nodes of the peer group into a predetermined topology,

b) calculate initial least costs of links of the topology,

c) organize said border nodes into a star topology in which the border nodes are represented as a nucleus and ports,

d) determine aggregation parameters for links of the star topology using said initial least costs,

e) recalculate second least costs of said predetermined topology using the aggregation parameters,

f) aggregate physical links between said nucleus and said ports into logical links according to said aggregation parameter,

g) determine a plurality of differences between the initial least costs and the second least costs,

h) determine a link having a maximum value of said differences if said maximum value is greater than a convergence threshold value, and

i) interconnect adjacent ones of said ports with said link bypassing the nucleus.

23. The communication network of claim 22, wherein said predetermined topology is a mesh topology.

24. The communication network of claim 14, wherein said topology aggregating means is arranged to:

aggregate physical links between two peer groups into a logical link; and

remove one of said ports from the star topology corresponding to one of said physical links.

25. The communication network of claim 22, wherein said negotiating means is further arranged to exchange the convergence threshold value with other peer group leader nodes to agree on a negotiated convergence threshold value,

said topology aggregating means determining said link having a maximum value of said differences if said maximum value is greater than the negotiated convergence threshold value.

26. An aggregation method for each of a plurality of nodes of a communication network, the method comprising the steps of:

a) exchanging aggregation parameters with a neighbor node to agree on a negotiated aggregation parameter;

b) aggregating a plurality of physical links from the node to the neighbor node into a logical link according to the negotiated aggregation parameter and storing resource data of said logical link into a database; and

c) exchanging the resource data with said neighbor node and updating contents of said database with resource data of said neighbor node.

27. The method of claim 26, wherein each of said physical links is represented by a resource vector and each element of the vector is represented by a resource value of a different resource class, wherein the step (b) comprises the steps of:

b₁) detecting a maximum resource value and a minimum resource value of an element of the resource vectors of the physical links;

b₂) multiplying the maximum resource value by the aggregation parameter and multiplying the minimum resource value by unity minus the aggregation parameter; and

b₃) summing the multiplied maximum resource value and the multiplied minimum resource value; and

b₄) repeating the steps (b₁) to (b₃) for each successive element of the resource vectors of the physical links.

28. The method of claim 26, wherein each of said physical links is represented by a resource vector and each element of the vector is represented by a quality-of-service value of a different class, wherein the step (b) comprises the steps of:

b₁) detecting a maximum quality-of-service value and a minimum quality-of-service value of an element of the resource vectors of the physical links;

b₂) multiplying the maximum quality-of-service value by the aggregation parameter and multiplying the minimum quality-of-service value by unity minus the aggregation parameter; and

b₃) summing the multiplied maximum quality-of-service value and the multiplied minimum quality-of-service value; and

b₄) repeating the steps (b₁) to (b₃) for each successive element of the resource vectors of the physical links.

29. An aggregation method for each of a plurality of nodes of a communication network, the method comprising the steps of:

a) exchanging aggregation parameters with a neighbor node to agree on a negotiated aggregation parameter;

b) aggregating a plurality of physical links from the node to the neighbor node into a logical link according to the negotiated aggregation parameter and storing resource data of said logical link into a database;

c) exchanging the resource data with said neighbor node and updating contents of said database with resource data of said neighbor node;

d) evaluating an operating performance of said logical link by using traffic data from the network;

e) updating the negotiated aggregation parameter according to the detected operating performance;

f) exchanging the updated aggregation parameter with said neighbor node to agree on a negotiated aggregation parameter; and

g) repeating the steps (b) to (f) using the negotiated aggregation parameter.

30. An aggregation method for each of a plurality of nodes of a communication network, the method comprising the steps of:

a) organizing a plurality of physical links between the node and a neighbor node into a plurality of groups according to similarities of resource classes of said physical links;

b) exchanging an aggregation parameter with the neighbor node to agree on a negotiated aggregation parameter;

c) aggregating said physical links into a plurality of said groups of logical links using the negotiated aggregation parameter and storing resource data of said logical link into a database; and

d) exchanging the resource data with said neighbor node and updating contents of said database with resource data of said neighbor node.

31. An aggregation method for each of a plurality of nodes of a communication network, the method comprising the steps of:

a) organizing a plurality of physical links between the node and a neighbor node into a plurality of groups according to similarities of resource classes of said physical links;

b) exchanging an aggregation parameter with the neighbor node to agree on a negotiated aggregation parameter;

c) aggregating said physical links into a plurality of said groups of logical links using the negotiated aggregation parameter and storing resource data of said logical link into a database;

d) exchanging the resource data with said neighbor node and updating contents of said database with resource data of said neighbor node;

e) evaluating an operating performance of each of said groups of physical links from traffic data from the network;

f) updating the negotiated aggregation parameter according to the evaluated operating performance; and

g) repeating the steps (b) to (e) using the updated aggregation parameter as said aggregation parameter.

32. An aggregation method for a peer group leader node in a communication network formed by a plurality of interconnected nodes which are divided into a plurality of peer groups, each peer group having said peer group leader node and border nodes via which the peer group is interconnected with other peer groups, the method comprising the steps of:

a) exchanging aggregation parameters with other peer group leader nodes to agree on negotiated aggregation parameters;

b) aggregating physical topology of the border nodes of said peer group into a logical star topology using said negotiated aggregation parameters and storing resource data of said logical star topology in a database; and

c) exchanging the resource data with a neighbor peer group leader node and updating the database with resource data from the neighbor peer group leader node.

33. The method of claim 32, wherein the step (b) comprises the steps of:

b₁) organizing the border nodes of said peer group into a predetermined topology;

b₂) calculating initial least costs of links of the topology;

b₃) organizing said border nodes into a star topology in which the border nodes are represented as a nucleus and ports;

b₄) determining aggregation parameters for links of the star topology using said initial least costs;

b₅) recalculating second least costs of said predetermined topology using the aggregation parameters;

b₆) aggregating physical links from said nucleus to said ports into logical links according to said aggregation parameter;

b₇) determining a plurality of differences between the initial least costs and the second least costs;

b₈) determining a link having a maximum value of said differences if said maximum value is greater than a convergence threshold value; and

b₉) interconnecting adjacent ones of said ports with the link bypassing the nucleus.

34. The method of claim 33, wherein said predetermined topology is a mesh topology.

35. The method of claim 33, further comprising the steps of:

aggregating physical links between two peer groups into a logical link; and

removing one of said ports of step (b₉) corresponding to one of said physical links.

36. The method of claim 33, further comprising the steps of:

following the step (b₉), recalculating the aggregation parameters and said second least costs of the links of the predetermined topology; and

repeating the steps (b₇) to (b₉) until said maximum value becomes smaller than said convergence threshold value.

37. The method of claim 32, further comprising the steps of:

evaluating an operating performance of the logical star topology by using traffic data from the network;

updating the negotiated aggregation parameters of the step (a) according to the evaluated operating performance; and

repeating the steps (b) and (c).

38. The method of claim 33, further comprising the steps of:

evaluating an operating performance of the logical star topology by using traffic data from the network;

updating the negotiated aggregation parameters of the step (a) according to the evaluated operating performance;

exchanging the negotiated updated aggregation parameters with other peer group leader nodes to agree on negotiated updated aggregation; and

repeating the steps (b₅) to (b₉).

39. A network node for a communication network in which said node is one of a plurality of network nodes, the network node comprising:

negotiating means for exchanging aggregation parameters with a neighbor node to agree on a negotiated aggregation parameter, said negotiated aggregation parameter having a value between 0 and 1 inclusive;

link aggregating means for aggregating a plurality of physical links between the network node and a neighbor node into a logical link according to the negotiated aggregation parameter;

a database for storing resource data of said logical link; and

means for exchanging the resource data with said neighbor node and updating contents of said database with resource data of said neighbor node.