Designing Paths with Minimum Number of Hops: Comparing Disaggregated and Aggregated Formulations

摘要

Given an undirected network N velence (X, U) with link capacities (b_(e)) and a set of commodities with known demands, this paper addresses the problem of routing demands (r_(pq)) for each commodity (p, q) over the network N, under the survivability mechanism (Path Diversity or Path Protection) one wishes to implement, through D hop-constrained node disjoint paths for every commodity and complying with the installed bandwidth on each edge e E U. The two types of survivability mechanisms - Path Diversity and Path Protection - which differ in the way one wishes to protect total demand: the first is suitable to enhance demand protection but total protection is not a requirement (as each demand is equally split over D paths); the latter mechanism is preferred when total demand protection is needed (any D - 1 out of D paths have enough capacity to support each total demand). An optimal routing is the one that minimizes either i) the average number of hops or ii) the maximum number of hops, of all relevant paths between any pair of nodes p, q E S (is contained in) X. For each commodity, the relevant paths are the best (that is, those with fewer number of hops) DELTA paths (with 1 <= DELTA <= D). Due to the way total demand is protected, under Path Diversity we have DELTA velence D and, under Path Protection, we have DELTA velence D - 1.