Multiplex communications – Pathfinding or routing – Switching a message which includes an address header
Reexamination Certificate
1998-09-21
2001-06-12
Olms, Douglas (Department: 2661)
Multiplex communications
Pathfinding or routing
Switching a message which includes an address header
C370S256000
Reexamination Certificate
active
06246689
ABSTRACT:
TECHNICAL FIELD
This invention relates to aggregating the topology of a sub-network and, more particularly, to efficient aggregation of hierarchically organized networks.
BACKGROUND OF THE INVENTION
A typical communication system is made up of nodes, including switching systems, which are interconnected by so-called links including transmission facilities. When such a communication system is arranged to include a hierarchical arrangement of subnetworks, or domains, there is a need to advertise, i.e., to distribute, the topologies of the sub-networks in a compact manner. One such communication system is the Asynchronous Transfer Mode (ATM) system. Usually, the relevant topology information to be advertised is the value of some network topology parameter, for example, delay, available bandwidth, usage cost, distance, or the like, related to traversing the network between so-called border nodes. Note that a border node is one having a link to a node outside the sub-network. For an accurate representation of the network topology parameters, the number of values that should be advertised is quadratic in the number of border nodes. If the number of values to be advertised can be reduced, there will be a corresponding reduction in the cost of storing, advertising and calculating routing based on the values. However, the compression of the number of the topology parameter values required to realize these advantages introduces errors, i.e., distortion, between the advertised and real value of the network parameter between some of the border nodes.
SUMMARY OF THE INVENTION
These and other problems and limitations of such topology aggregation techniques are addressed in apparatus and a method for efficient topology aggregation by utilizing a so-called full-mesh topology that is generated 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 in accordance with prescribed criteria to determine if the resultant spanning tree aggregation topology requires further refinement in order to meet a predetermined distortion criterion. If no further refinement of the aggregation topology is required the aggregation topology is advertised.
Additionally, a prescribed network parameter, for example, a so-called network radius, defined as one-half the maximum distance between any two nodes in the full-mesh topology, is generated from the full-mesh topology. In this example, the network parameter is the network “radius”, which is evaluated along with the first spanning tree aggregation topology to determine if the resultant spanning tree aggregation topology requires further refinement. If no further refinement is required, both the aggregation topology and the network parameter are advertised.
Specifically, the need, or not, for further refinement of the first spanning tree aggregation topology, i.e., topology to be advertised, is based on a distortion measure. Distortion is defined as the ratio of the value of the network topology parameter as determined from the aggregation topology to be advertised and the network parameter, e.g., network, radius, and the value of the network topology parameter in the full-mesh topology.
In one embodiment of the invention, the firs spanning tree is a minimum spanning tree (MST) and the cost of the network topology parameter is the cost of the shortest path between a pair of border nodes.
If the resultant first spanning tree aggregation topology requires further refinement to reduce the distortion, a second spanning tree aggregation topology, different from the first, is generated and merged with the first spanning tree aggregation topology to yield a first merged aggregation topology. The first merged aggregation topology is evaluated for distortion, along with the network parameter, and if it is satisfactory no further refinement is required. However, if further refinement is needed to reduce distortion, another second spanning tree aggregation topology is generated and merged with the first merged aggregation topology to yield a second merged aggregation topology. Then, the second merged aggregation topology is evaluated for distortion, along with the network parameter, and if it is satisfactory no further refinement is required. If still more refinement is required to reduce the distortion, links between nodes having the highest level of distortion are added to the second merged aggregation topology until a prescribed number of links is reached. The prescribed number of links is related to the number of border nodes in the aggregated, i.e., original or full-mesh, topology.
In another embodiment of the invention, the first spanning tree is a minimum spanning tree (MST) and the second spanning tree is a random spanning tree (RST), while the cost of the network topology parameter is still the cost of the shortest path between a pair of border nodes.
In still another embodiment of the invention, the first spanning tree is a minimum spanning tree (MST) and the second spanning tree is a first random spanning tree (RST), which are merged with another second spanning tree that is a second random spanning tree (new RST), to yield the second merged aggregation topology, i.e., MTS+RTS+new RTS.
In yet another embodiment of the invention, links between nodes having the highest distortion are added to the second merged aggregation topology, i.e., MST+RST+new RST, until the prescribed number of links is reached.
REFERENCES:
patent: 5535195 (1996-07-01), Lee
patent: 6122283 (2000-08-01), Lee
B. Awerbuch et al. “Routing Through Networks with Hierarchical Topology Aggregation”,Journal of High Speed Networks, vol. 7, No. 1, 1998.
B. Awerbuch et al. “Topology Aggregation for Directed Graphs”,Third(IEEE)Symposium on Computers and Communications, pp. 47-52, Jun. 1998.
W. C. Lee “Topology Aggregation for Hierarchical Routing in ATM Networks”,Computer Communication Review, vol. 25, No. 2, pp. 82-92, Apr. 1995.
Lucent Technologies - Inc.
Olms Douglas
Vanderpuye Ken
LandOfFree
Method and apparatus for efficient topology aggregation for... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method and apparatus for efficient topology aggregation for..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for efficient topology aggregation for... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2514729