Dynamic transition matrix generation for topology aggregation

In large networks nodes are clustered into groups for the purpose of simplifying routing. Each group has a set of ingress-egress nodes, and routing information is conveyed to the outside world in the form of a transition matrix that gives the cost of traversing the network between each ingress-egress node pair. In a dynamic environment where costs are subject to change, the cost for traversing a group, and consequently the transition matrix is affected. In this paper, we present a novel graph-coloring method for computing and consistently maintaining in a dynamic environment the transition matrix corresponding to a group of nodes. This method is applicable in the case where path selection is based on restrictive costs, such as bandwidth, and it considers the symmetric case. A key characteristic of the method is its ability to distinguish between topology or link-cost changes that necessarily leave the transition matrix unchanged and those that may not; that is, a correct transition matrix is maintained at all times without recomputing it every time a cost change occurs. Numerical results illustrate the efficiency of the method, expressed in terms of the percentage of time that the transition matrix needs to be recomputed. © 2002 Elsevier Science B.V. All rights reserved.