Improving Robustness of Next-Hop Routing Public Deposited

http://ir.library.oregonstate.edu/concern/articles/br86b533t

This is an author's peer-reviewed final manuscript, as accepted by the publisher. The published article is copyrighted by Springer and can be found at:  http://link.springer.com/journal/10878

Descriptions

Attribute NameValues
Creator
Abstract or Summary
  • A weakness of next-hop routing is that following a link or router failure there may be no routes between some source-destination pairs, or packets may get stuck in a routing loop as the protocol operates to establish new routes. In this article, we address these weaknesses by describing mechanisms to choose alternate next hops. Our first contribution is to model the scenario as the following TREE AUGMENTATION problem. Consider a mixed graph where some edges are directed and some undirected. The directed edges form a spanning tree pointing towards the common destination node. Each directed edge represents the unique next hop in the routing protocol. Our goal is to direct the undirected edges so that the resulting graph remains acyclic and the number of nodes with outdegree two or more is maximized. These nodes represent those with alternative next hops in their routing paths. We show that TREE AUGMENTATION is NP-hard in general and present a simple 1/2[one over two]-approximation algorithm. We also study 3 special cases. We give exact polynomial-time algorithms for when the input spanning tree consists of exactly 2 directed paths or when the input graph has bounded treewidth. For planar graphs, we present a polynomial-time approximation scheme when the input tree is a breadth-first search tree. To the best of our knowledge, TREE AUGMENTATION has not been previously studied.
Resource Type
DOI
Date Available
Date Issued
Citation
  • Borradaile, G., Kennedy, W. S., Wilfong, G., & Zhang, L. (2016). Improving robustness of next-hop routing. Journal of Combinatorial Optimization, 31(3), 1206-1220. doi:10.1007/s10878-014-9818-x
Series
Keyword
Rights Statement
Funding Statement (additional comments about funding)
Publisher
Peer Reviewed
Language
Replaces
Additional Information
  • description.provenance : Approved for entry into archive by Deanne Bruner(deanne.bruner@oregonstate.edu) on 2016-04-26T22:35:40Z (GMT) No. of bitstreams: 1 BorradaileImprovingRobustnessOfNext-HopRouting.pdf: 348948 bytes, checksum: d64f831b236de86338450d05629fae1b (MD5)
  • description.provenance : Made available in DSpace on 2016-04-26T22:35:40Z (GMT). No. of bitstreams: 1 BorradaileImprovingRobustnessOfNext-HopRouting.pdf: 348948 bytes, checksum: d64f831b236de86338450d05629fae1b (MD5) Previous issue date: 2016-04
  • description.provenance : Submitted by Deanne Bruner (deanne.bruner@oregonstate.edu) on 2016-04-26T22:34:44Z No. of bitstreams: 1 BorradaileImprovingRobustnessOfNext-HopRouting.pdf: 348948 bytes, checksum: d64f831b236de86338450d05629fae1b (MD5)

Relationships

In Administrative Set:
Last modified: 07/26/2017

Downloadable Content

Download PDF
Citations:

EndNote | Zotero | Mendeley

Items