Patent ID: 6643699
Filing Date: 2003-11-04
Classification: H04L

Abstract:
A computerized method encoded in a computer readable medium, for taking a data structure of a Blocking Island Contour Map of a network graph of a network-level, a to-be-modified network-link, and a corresponding new capacity value, and a currently-processed abstract node and computing overall splitting-cost, the method comprising the steps of:(a) terminating and returning cost of zero, if there exists no currently processed abstract node or the capacity of the currently-processed abstract node is smaller or equal to the new capacity value; (b) initializing the split-cache for the to-be-modified network-link and the currently-processed abstract node by setting the split-cache entry to an empty set and further initializing a set of nodes and edges of a network-level graph with the empty set; (c) mapping the currently-processed abstract node to a desired network level, which results in a graph defined with the set of nodes and edges initialized in step (b); (d) computing a connected component for some point of the network-level graph, from which the to-be-modified network link is removed for this computation; (e) terminating and returning a cost of zero, if the connected component and the network-level graph have the same set of vertices; and (f) terminating by returning the weighted sun of the cost of splitting the currently-processed abstract node and the cost returned by applying the method to the abstract node denoted by the abstract node slot of the currently-processed abstract node.