About cookies on this site Our websites require some cookies to function properly (required). In addition, other cookies may be used with your consent to analyze site usage, improve the user experience and for advertising. For more information, please review your options. By visiting our website, you agree to our processing of information as described in IBM’sprivacy statement. To provide a smooth navigation, your cookie preferences will be shared across the IBM web domains listed here.
Publication
Computer Communications
Paper
Dynamic transition matrix generation for topology aggregation
Abstract
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.