首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Stable routing under the Spanning Tree Protocol
Authors:Fabrizio Grandoni  Laura Sanità
Institution:a Dipartimento di Informatica, Sistemi e Produzione, Università di Roma Tor Vergata, Via del Politecnico 1, 00133 Roma, Italy
b Dipartimento di Informatica e Automazione, Università degli Studi Roma Tre, Via della Vasca Navale 79, I 00146 Roma, Italy
c Dipartimento di Ingegneria dell’Impresa, Università di Roma Tor Vergata, via del Politecnico 1, 00133 Roma, Italy
d Institute of Mathematics, École Polytechnique Fédérale de Lausanne, 1015 Lausanne, Switzerland
Abstract:The Spanning Tree Protocol routes traffic on shortest path trees. If some edges fail, the traffic has to be rerouted consequently, setting up alternative trees. In this paper we design efficient algorithms to compute polynomial-size integer weights so as to enforce the following stability property: if q=O(1) edges fail, traffic demands that are not affected by the failures are not redirected. Stability is a goal pursued by network operators in order to minimize transmission delays due to the restoration process.
Keywords:Stable routing  Spanning Tree Protocol  Randomized algorithms
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号