科研之友
微信
新浪微博
Facebook
分享链接
摘要
Demand-oblivious routing has become a promising technology for traffic engineering, since there is no need to estimate or measure traffic volume precisely, and network congestion in the worst case can be bounded. An important issue for demand-oblivious routing is to deal with topology changes, and there have been studies on demand-oblivious routing under the situation of failures. In this paper, we consider demand-oblivious routing under another type of topology change: links are pruned initiatively for such purpose as energy conservation. In existing studies, oblivious performance ratio (OPR) is used to evaluate a static routing, which measures the congestion with the routing under the worst-case traffic matrix. We propose extended oblivious performance ratio (EOPR) to extend OPR in the topology with pruned links. We show that EOPR is a general form of OPR, and a set of models can be extended to deal with EOPR. We define the Green-EOPR problem, which selects a given number of links to prune and minimizes the EOPR. We prove that the minimum EOPR is bounded by a linear function of the pruned links' number. We develop efficient heuristics to solve Green-EOPR. The pruned link selection heuristic is based on the definition of local performance ratio. And the rerouting heuristic is based on Dijkstra's algorithm. Extensive simulations show that our heuristics can achieve an EOPR much less than the upper bound.
- 出版日期2018-8-4
- 单位清华大学
