Method for obtaining a lossless compressed aggregation of a communication network
First Claim
1. A method for providing a substantially lossless compressed aggregation of a non-compressed topology representing a predetermined plurality of switching nodes interconnected by communication links in a data communication network, wherein the non-compressed topology has a plurality of paths each of which is formed by a tandem of communication links and wherein each communication link has a predetermined topology characteristic, said method comprising the steps of:
- A) identifying border vertices among the predetermined plurality of switching nodes as those having communications links to switching nodes outside the predetermined plurality of switching nodes, and designating those remaining switching nodes among the predetermined plurality of switching nodes as interior vertices;
B) reducing the plurality of paths in the non-compressed topology by identifying an optimal path between each unique pair of said border vertices based upon the predetermined topology characteristic to create a plurality of optimal paths; and
C) aggregating the plurality of optimal paths to provide for storage of, in at least one of the predetermined plurality of switching nodes, the substantially lossless compressed aggregation of the non-compressed topology spanning the border vertices of the non-compressed topology.
4 Assignments
0 Petitions
Accused Products
Abstract
A method for providing a lossless, compressed topology aggregation of a group of switching nodes and interconnecting links. The switching nodes are divided into border vertices having communications with other networks or subnetworks and interior vertices. The method determines non-redundant optimal paths between different pairs of border vertices. These paths are aggregated for storage at individual border switching nodes to enable the characteristic, metric or attribute to be advertised outside of the subnetwork or peer group.
46 Citations
32 Claims
-
1. A method for providing a substantially lossless compressed aggregation of a non-compressed topology representing a predetermined plurality of switching nodes interconnected by communication links in a data communication network, wherein the non-compressed topology has a plurality of paths each of which is formed by a tandem of communication links and wherein each communication link has a predetermined topology characteristic, said method comprising the steps of:
-
A) identifying border vertices among the predetermined plurality of switching nodes as those having communications links to switching nodes outside the predetermined plurality of switching nodes, and designating those remaining switching nodes among the predetermined plurality of switching nodes as interior vertices; B) reducing the plurality of paths in the non-compressed topology by identifying an optimal path between each unique pair of said border vertices based upon the predetermined topology characteristic to create a plurality of optimal paths; and C) aggregating the plurality of optimal paths to provide for storage of, in at least one of the predetermined plurality of switching nodes, the substantially lossless compressed aggregation of the non-compressed topology spanning the border vertices of the non-compressed topology. - View Dependent Claims (29, 30)
-
-
2. A method for providing a topology aggregation of a predetermined plurality of switching nodes in a data communication network interconnected by communication links, wherein each communication link has a predetermined topology characteristic, said method comprising the steps of:
-
A) identifying border vertices among the predetermined plurality of switching nodes as those having communications links to switching nodes outside the predetermined plurality, and designating those remaining switching nodes among the predetermined plurality as interior vertices, B) determining a non-redundant optimal path between each pair of said border vertices based upon the predetermined topology characteristic, wherein said step of determining the non-redundant optimal path comprises, for each pair of border vertices, comprises the steps of; quantifying the predetermined topology characteristic of the communication links extending between the pair of border vertices; iteratively processing alternate paths between the pair of border vertices to identify an optimal path therebetween; testing each optimal path for redundancy with respect to previously determined optimal paths; and saving the optimal path unless the optimal path is redundant; and C) aggregating the non-redundant optimal paths to provide for storage of, at least one of the predetermined plurality of switching nodes, a substantially lossless compressed topology aggregation of the predetermined topology characteristic spanning the border vertices. - View Dependent Claims (3, 4, 5, 6, 7, 8, 9, 10)
-
-
11. A method for providing a substantially lossless compressed aggregation of a non-compressed topology having a plurality of paths between a plurality of border switching nodes in a peer group of an ATM network, wherein the border switching nodes and additional interior switching nodes are interconnected by communication links, and wherein each combination of switching nodes and connected communication links has a predetermined topology characteristic, said method comprising the steps of:
iteratively, for each border switching node identified as a first border switching node, determining an optimal path from the first border switching node to all other switching nodes in the peer group based on the predetermined topology characteristic to create a plurality of optimal paths; segregating, during each iteration, each path from the first border switching node to a switching node in the peer group into a category when the path does not traverse a second border switching node as an intermediate node; and aggregating the plurality of optimal paths in the category to generate a substantially lossless compressed aggregation for storage at the border switching nodes in the peer group. - View Dependent Claims (12, 13, 14, 15, 16, 17, 18, 19, 20)
-
21. A method for providing a substantially lossless compressed aggregation of a non-compressed topology having paths between a plurality of border switching nodes in a peer group of an ATM network, wherein the border switching nodes and additional interior switching nodes are interconnected by paths, each of which is formed by a tandem of communication links, and wherein each combination of switching nodes and connected communication links has a predetermined topology characteristic, said method comprising the steps of:
-
in a first phase, iteratively, for each pair of switching nodes in the peer group, determining a first estimated optimal path between the pair of switching nodes such that the path is permitted to include only interior switching nodes as intermediate switching nodes, in a second phase, iteratively, for each pair of border switching nodes in the peer group, determining a second estimated optimal path between the pair of border switching nodes such that the path is permitted to include other border switching nodes as intermediate switching nodes, and segregating, during each iteration, into a category, each path between two border switching nodes using another border switching node as an intermediate switching node, and aggregating the optimal paths in the category to generate the substantially lossless compressed aggregation for distribution to the border switching nodes in the peer group. - View Dependent Claims (22, 23, 24, 25, 26, 27, 28)
-
-
31. A method for providing a topology aggregation of paths between a plurality of border switching nodes in a peer group of an ATM network, wherein the border switching nodes and additional interior switching nodes are interconnected by communication links, and wherein each combination of switching nodes and connected communication links has a predetermined topology characteristic, said method comprising the steps of:
-
iteratively, for each border switching node, determining an optimal path from one border switching node to all other switching nodes in the peer group, wherein said iterative determination of optimal paths includes the step of using a Dijkstra methodology for obtaining the optimal paths between border switching nodes and all other switching nodes, and segregating, during each iteration, each path between two switching nodes in the peer group into a first of two categories when the path does not traverse a border switching node, and aggregating the optimal paths in the first category to generate a substantially lossless compressed topology aggregation for storage at the border switching nodes in the peer group.
-
-
32. A method for providing a topology aggregation of paths between a plurality of border switching nodes in a peer group of an ATM network wherein the border switching nodes and additional interior switching nodes are interconnected by communication links, and wherein each combination of switching nodes and connected communication links has a predetermined topology characteristic, said method comprising the steps of:
-
in a first phase, iteratively, for each interior switching node, determining a first estimated optimal path between all pairs of interior switching nodes in the peer group that are direct paths and that are paths involving only other interior switching nodes, in a second phase, iteratively, for each border switching node, determining a second estimated optimal path between all pairs of border switching nodes in the peer group that are pats involving other border switching nodes as intermediate switching nodes, and segregating, during each iteration, into a first of two categories, each path between two border switching nodes using another border switching node as an intermediate switching node, and aggregating the first and second optimal paths in the first category to generate a substantially lossless compressed topology aggregation for distribution to the border switching nodes in the peer group, wherein said iterative determination of optimal paths includes the step of using a Floyd-Warshall methodology for obtaining an optimal path between each pair of switching nodes.
-
Specification