Method and apparatus for efficient topology aggregation for networks with hierarchical structure

• US 6,246,689 B1
• Filed: 09/21/1998
• Issued: 06/12/2001
• Est. Priority Date: 09/21/1998
• Status: Expired due to Fees

• Current Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Original Assignee: Lucent Technologies, Inc. (Nokia Corporation)
• Inventors: Shavitt, Yuval
• Primary Examiner(s): Olms, Douglas
• Assistant Examiner(s): VANDERPUYE, KENNETH N
• Application Number:
  US09/157,858
• Time in Patent Office: 995 Days
• Field of Search: 370/255, 370/256, 370/408, 370/395, 370/400, 370/406, 709/242
• US Class Current: 370/406
• 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/10 Routing in connection-oriented networks, e.g. X.25 or ATM
• CPC Class Codes: H04L 45/46 Cluster building
• CPC Class Codes: H04L 45/48 Routing tree calculation
• CPC Class Codes: H04Q 11/0478 Provisions for broadband connections

Abstract

Efficient topology aggregation is realized by generating a full-mesh topology from an original sub-network topology, without compromising accuracy. Then, the full-mesh topology is reduced to a first spanning tree aggregation topology. Distortion in the first spanning tree aggregation topology is evaluated to determine if the resultant spanning tree aggregation topology requires further refinement in order to meet a predetermined distortion criterion. If no further refinement is required, the aggregation topology is advertised. Additionally, a network parameter, e.g., a so-called network radius is generated from the full-mesh topology. In this example, the network parameter is evaluated along with the first spanning tree aggregation topology to determine if the spanning tree aggregation topology requires further refinement. If no further refinement is required, both the aggregation topology and the network parameter are advertised.

Claims

1. A method for use in a communication system to obtain efficient sub-network topology aggregation of an aggregated sub-network topology, the aggregated topology including nodes and transmission links coupling the nodes and wherein nodes having links coupling nodes outside the sub-network are defined as border nodes, comprising the steps of:

generating a full-mesh topology from the aggregated topology having a plurality of nodes including border nodes of the aggregated topology and virtual links coupling all node pairs;

generating a first spanning tree aggregation topology having a plurality of nodes including border nodes of the full-mesh topology and a prescribed number of virtual links coupling the nodes;

determining distortion between all pairs of border nodes in said first spanning tree aggregation topology;

evaluating said distortion to determine whether or not a predetermined quality of aggregation has been attained of said first spanning tree aggregation topology; and

if the predetermined quality of aggregation of said first spanning tree aggregation topology has been achieved, advertising the first spanning tree aggregation topology.

2. The method as defined in claim 1 wherein said first spanning tree is a minimum spanning tree (MTS).

3. The method as defined in claim 1 further including a step of generating a network parameter of said aggregated topology and said step of advertising includes advertising said network parameter along with said first spanning tree aggregation topology.

4. The method as defined in claim 3 wherein said network parameter is one-half the diameter of said aggregated topology, said diameter being the maximum distance between any two nodes in the aggregated topology.

5. The method as defined in claim 1, if the predetermined quality of aggregation has not been achieved of the first spanning tree aggregation topology, further including a step of further refining the first spanning tree aggregation topology including the steps of generating a second spanning tree aggregation topology having nodes and transmission links coupling the nodes, merging said second spanning tree aggregation topology with said first spanning tree aggregation topology to obtain a first merged aggregation topology, said first merged aggregation topology having a plurality of nodes including border nodes of the full-mesh topology and a prescribed number of virtual links coupling the nodes, determining distortion between all pairs of border nodes in said first merged aggregation topology, evaluating said distortion to determine whether or not a predetermined quality of aggregation has been attained, and if the predetermined quality of aggregation has been achieved, advertising the first merged aggregation topology.

6. The method as defined in claim 5 wherein said first spanning tree is a minimum spanning tree (MST) and said second spanning tree is a random spanning tree (RST), and said first merged aggregation topology is MST+RST.

7. The method as defined in claim 5 further including a step of generating a network parameter of said aggregated topology and said step of advertising includes advertising said network parameter along with said first merged aggregation topology.

8. The method as defined in claim 7 wherein said network parameter is one-half the diameter of said aggregated topology, said diameter being the maximum distance between any two nodes in the aggregated topology.

9. The method as defined in claim 5, if the predetermined quality of aggregation of said first merged aggregation topology has not been achieved, further including a step of further-refining the first merged aggregation topology including the steps of generating a third spanning tree aggregation topology having nodes and transmission links coupling the nodes, merging said third spanning tree aggregation topology with said first spanning tree aggregation topology and said second spanning tree aggregation topology to obtain a second merged aggregation topology, said first merged aggregation topology having a plurality of nodes including border nodes of the full-mesh topology and a prescribed number of virtual links coupling the nodes, determining distortion between all pairs of border nodes in said second merged aggregation topology, evaluating said distortion to determine whether or not a predetermined quality of aggregation has been attained of said first merged aggregation topology, and if the predetermined quality of aggregation has been achieved, advertising said second merged aggregation topology.

10. The method as defined in claim 9 wherein said first spanning tree is a minimum spanning tree (MST), said second spanning tree is a random spanning tree (RST), said third spanning tree is a new random spanning tree (new RST), and said second merged aggregation topology is MST+RST+new RST.

11. The method as defined in claim 9 further including a step of generating a network parameter of said aggregated topology and said step of advertising includes advertising network parameter along with said second merged aggregation topology.

12. The method as defined in claim 11 wherein said network parameter is one half the diameter of said aggregated topology, said diameter being the maximum distance between any two nodes in the aggregated topology.

13. The method as defined in claim 9, if the predetermined quality of aggregation of said second merged aggregation topology has not been achieved, further including a step of further refining the second merged aggregation topology including the steps of adding links from said aggregated topology having the highest distortion to said second merged aggregation topology until a prescribed number of links has been reached to generate a third merged aggregation topology, and advertising said third merged aggregation topology.

14. The method as defined in claim 13 wherein said first spanning tree is a minimum spanning tree (MST), said second spanning tree is a random spanning tree (RST), said third spanning tree is a new random spanning tree (new RST), and said third merged aggregation topology is MST+RST+new RST+added links.

15. The method as defined in claim 13 wherein said prescribed number of links is related to the number of border nodes in said aggregated topology.

16. The method as defined in claim 15 wherein said prescribed number of links is 3b, where b is the number of border nodes in said aggregated topology.

17. The method as defined in claim 13 further including a step of generating a network parameter of said aggregated topology and said step of advertising includes advertising said network parameter along with said third merged aggregation topology.

18. The method as defined in claim 17 wherein said network parameter is one-half the diameter of said aggregated topology, said diameter being the maximum distance between any two nodes in the aggregated topology.

19. Apparatus for use in a communication system node to obtain efficient sub-network topology aggregation of an aggregated sub-network topology, the aggregated topology including nodes and transmission links coupling the nodes and wherein nodes having links coupling nodes outside the sub-network are defined as border nodes, the apparatus comprising:

means for generating a full-mesh topology from the aggregated topology having a plurality of nodes including border nodes of the aggregated topology and virtual links coupling all node pairs;

means for generating a first spanning tree aggregation topology having a plurality of nodes including border nodes of the full-mesh topology and a prescribed number of virtual links coupling the nodes;

means for determining distortion between all pairs of border nodes in said first spanning tree aggregation topology;

means for evaluating said distortion to determine whether or not a predetermined quality of aggregation of said first spanning tree aggregation topology has been attained; and

means, responsive to an indication that the prescribed quality of aggregation has been achieved, for advertising the first spanning tree aggregation topology.

20. The invention as defined in claim 19 wherein said first spanning tree is a minimum spanning tree (MTS).

21. The invention as defined in claim 19 further including a means for generating a network parameter of said aggregated topology and said step of advertising includes advertising said network parameter along with said first spanning tree aggregation topology.

22. The invention as defined in claim 21 wherein said network parameter is one-half the diameter of said aggregated topology, said diameter being the maximum distance between any two nodes in the aggregated topology.

23. The invention as defined in claim 19 further including means, responsive to an indication that said prescribed quality of aggregation has not been achieved of the first spanning tree aggregation topology, for further refining the aggregation topology including means for generating a second spanning tree aggregation topology having nodes and transmission links coupling the nodes, means for merging said second spanning tree aggregation topology with said first spanning tree aggregation topology to obtain a first merged aggregation topology, said first merged aggregation topology having a plurality of nodes including border nodes of the full-mesh topology and a prescribed number of virtual links coupling the nodes, means for determining distortion between all pairs of border nodes in said first merged aggregation topology, means for evaluating said distortion to determine whether or not said prescribed quality of aggregation has been attained, and means responsive to an indication that said prescribed quality of aggregation has been achieved, for advertising the first merged aggregation topology.

24. The invention as defined in claim 23 wherein said first spanning tree is a minimum spanning tree (MST) and said second spanning tree is a random spanning tree (RST), and said first merged aggregation topology is MST+RST.

25. The invention as defined in claim 23 further means for generating a network parameter of said aggregated topology and said means for advertising said first merged aggregation includes advertising said network parameter along with said first merged aggregation topology.

26. The invention as defined in claim 25 wherein said network parameter is one-half the diameter of said aggregated topology, said diameter being the maximum distance between any two nodes in the aggregated topology.

27. The invention as defined in claim 23, further including means, responsive to an indication that said prescribed quality of aggregation of said first merged aggregation topology has not been achieved, for further refining the first merged aggregation topology including means for generating a third spanning tree aggregation topology having nodes and transmission links coupling the nodes, means for merging said third spanning tree aggregation topology with said first spanning tree aggregation topology and said second spanning tree aggregation topology to obtain a second merged aggregation topology, said first merged aggregation topology having a plurality of nodes including border nodes of the full-mesh topology and a prescribed number of virtual links coupling the nodes, means for determining distortion between all pairs of border nodes in said second merged aggregation topology, means for evaluating said distortion to determine whether or not a prescribed quality of aggregation has been attained of said second merged aggregation topology, and means, responsive to an indication that said prescribed quality of aggregation of said second merged aggregation topology has been achieved, for advertising said second merged aggregation topology.

28. The invention as defined in claim 27 wherein said first spanning tree is a minimum spanning tree (MST), said second spanning tree is a random spanning tree (RST), said third spanning tree is a new random spanning tree (new RST), and said second merged aggregation topology is MST+RST+new RST.

29. The invention as defined in claim 27 further including means for generating a network parameter of said aggregated topology and said means for advertising said second merged aggregation topology includes means for advertising said network parameter along with said second merged aggregation topology.

30. The invention as defined in claim 29 wherein said network parameter is one half the diameter of said aggregated topology, said diameter being the maximum distance between any two nodes in the aggregated topology.

31. The invention as defined in claim 27 further including means, responsive to an indication that said prescribed quality of aggregation of said second merged aggregation topology has not been achieved, for further refining the second merged aggregation topology including means for adding links from said aggregated topology having the highest distortion to said second merged aggregation topology until a prescribed number of links has been reached to generate a third merged aggregation topology, and means for advertising said third merged aggregation topology.

32. The invention as defined in claim 31 wherein said first spanning tree is a minimum spanning tree (MST), said second spanning tree is a random spanning tree (RST), said third spanning tree is a new random spanning tree (new RST), and said third merged aggregation topology is MST+RST+new RST+added links.

33. The invention as defined in claim 31 wherein said prescribed number of links is related to the number of border nodes in said aggregated topology.

34. The invention as defined in claim 33 wherein said prescribed number of links is 3b, where b is the number of border nodes in said aggregated topology.

35. The invention as defined in claim 31 further including means for generating a network parameter of said aggregated topology and said mans for advertising said third merged aggregation topology includes means for advertising said network parameter along with said third merged aggregation topology.

36. The invention as defined in claim 35 wherein said network parameter is one-half the diameter of said aggregated topology, said diameter being the maximum distance between any two nodes in the aggregated topology.

37. Apparatus for use in a communication system node to obtain efficient sub-network topology aggregation of an aggregated sub-network topology, the aggregated topology including nodes and transmission links coupling the nodes and wherein nodes having links coupling nodes outside the sub-network are defined as border nodes, the apparatus comprising:

a full-mesh topology generator for generating a full-mesh topology from the aggregated topology having a plurality of nodes including border nodes of the aggregated topology and virtual links coupling all node pairs;

a first aggregation topology generator for generating a first spanning tree aggregation topology having a plurality of nodes including border nodes of the full-mesh topology and a prescribed number of virtual links coupling the nodes;

a first distortion detector for determining distortion between all pairs of border nodes in said first spanning tree aggregation topology;

a first evaluator for evaluating said distortion to determine whether or not a prescribed quality of aggregation of said first spanning tree aggregation topology has been attained; and

a first advertiser, responsive to an indication that said prescribed quality of aggregation has been achieved, for advertising the first spanning tree aggregation topology.

38. The apparatus as defined in claim 37 wherein said first spanning tree is a minimum spanning tree (MST).

39. The apparatus as defined in claim 37 further including a parameter generator for generating a network parameter of said aggregated topology and said first advertiser advertises said network parameter along with said first spanning tree aggregation topology.

40. The apparatus as defined in claim 39 wherein said network parameter is one-half the diameter of said aggregated topology, said diameter being the maximum distance between any two nodes in the aggregated topology.

41. The apparatus as defined in claim 37 further including a first refiner, responsive to an indication that the prescribed quality of aggregation has not been achieved of the first spanning tree aggregation topology, for further refining the first spanning tree aggregation topology including a second aggregation topology generator for generating a second spanning tree aggregation topology having nodes and transmission links coupling the nodes, a first merger for merging said second spanning tree aggregation topology with said first spanning tree aggregation topology to obtain a first merged aggregation topology, said first merged aggregation topology having a plurality of nodes including border nodes of the full-mesh topology and a prescribed number of virtual links coupling the nodes, a second distortion detector for determining distortion between all pairs of border nodes in said first merged aggregation topology, a second evaluator for evaluating said distortion of said first merged aggregation topology to determine whether or not a predetermined quality of aggregation has been attained of said second merged aggregation topology, and a second advertiser, responsive to an indication that said prescribed quality of aggregation of said first merged aggregation topology has been achieved, for advertising the first merged aggregation topology.

42. The apparatus as defined in claim 41 wherein said first spanning tree is a minimum spanning tree (MST) and said second spanning tree is a random spanning tree (RST), and said first merged aggregation topology is MST+RST.

43. The apparatus as defined in claim 41 further including a parameter generator for generating a network parameter of said aggregated topology and said second advertiser advertises said network parameter along with said first merged aggregation topology.

44. The apparatus as defined in claim 43 wherein said network parameter is one-half the diameter of said aggregated topology, said diameter being the maximum distance between any two nodes in the aggregated topology.

45. The apparatus as defined in claim 41 further including a second refiner, responsive to an indication that said prescribed quality of aggregation of said first merged aggregation topology has not been achieved, for further refining the second merged aggregation topology including a third aggregation topology generator for generating a third spanning tree aggregation topology having nodes and transmission links coupling the nodes, a second merger for merging said third spanning tree aggregation topology with said first spanning tree aggregation topology and said second spanning tree aggregation topology to obtain a second merged aggregation topology, said first merged aggregation topology having a plurality of nodes including border nodes of the full-mesh topology and a prescribed number of virtual links coupling the nodes, a third distortion detector for determining distortion between all pairs of border nodes in said second merged aggregation topology, a third evaluator for evaluating said distortion of said second merged aggregation topology to determine whether or not a prescribed quality of aggregation has been attained, and a third advertiser, responsive to an indication that said prescribed quality of aggregation of said second merged aggregation topology has been achieved, for advertising said second merged aggregation topology.

46. The apparatus as defined in claim 45 wherein said first spanning tree is a minimum spanning tree (MST), said second spanning tree is a random spanning tree (RST), said third spanning tree is a new random spanning tree (new RST), and said second merged aggregation topology is MST+RST+new RST.

47. The apparatus as defined in claim 45 further including a parameter generator for generating a network parameter of said aggregated topology and said step of advertising includes advertising said network parameter along with said second merged aggregation topology.

48. The apparatus as defined in claim 47 wherein said network parameter is one half the diameter of said aggregated topology, said diameter being the maximum distance between any two nodes in the aggregated topology.

49. The apparatus as defined in claim 45 further including a third refiner, responsive to an indication that said prescribed quality of aggregation of said second merged aggregation topology has not been achieved, for further refining the second merged aggregation topology including an adder for adding links from said aggregated topology having the highest distortion to said second merged aggregation topology until a prescribed number of links has been reached to generate a third merged aggregation topology, and a fourth advertiser for advertising said third merged aggregation topology.

50. The apparatus as defined in claim 49 wherein said first spanning tree is a minimum spanning tree (MST), said second spanning tree is a random spanning tree (RST), said third spanning tree is a new random spanning tree (new RST), and said third merged aggregation topology is MST+RST+new RST+added links.

51. The apparatus as defined in claim 49 wherein said prescribed number of links is related to the number of border nodes in said aggregated topology.

52. The apparatus as defined in claim 51 wherein said prescribed number of links is 3b, where b is the number of border nodes in said aggregated topology.

53. The apparatus as defined in claim 49 further including a parameter generator for generating a network parameter of said aggregated topology and said step of advertising includes advertising said network parameter along with said third merged aggregation topology.

54. The apparatus as defined in claim 53 wherein said network parameter is one-half the diameter of said aggregated topology, said diameter being the maximum distance between any two nodes in the aggregated topology.