Advanced search
2 files | 719.04 KB Add to list

Single failure resiliency in greedy routing

Seyedeh Sahel Sahhaf (UGent) , Wouter Tavernier (UGent) , Didier Colle (UGent) , Mario Pickavet (UGent) and Piet Demeester (UGent)
Author
Organization
Abstract
Using greedy routing, network nodes forward packets towards neighbors which are closer to their destination. This approach makes greedy routers significantly more memory-efficient than traditional IP-routers using longest-prefix matching. Greedy embeddings map network nodes to coordinates, such that greedy routing always leads to the destination. Prior works showed that using a spanning tree of the network topology, greedy embeddings can be found in different metric spaces for any graph. However, a single link/node failure might affect the greedy embedding and causes the packets to reach a dead end. In order to cope with network failures, existing greedy methods require large resources and cause significant loss in the quality of the routing (stretch loss). We propose efficient recovery techniques which require very limited resources with minor effect on the stretch. As the proposed techniques are protection, the switch-over takes place very fast. Low overhead, simplicity and scalability of the methods make them suitable for large-scale networks. The proposed schemes are validated on large topologies with properties similar to the Internet. The performances of the schemes are compared with an existing alternative referred as gravity pressure routing.
Keywords
NETWORKS, IBCN, GRAPHS, TREES

Downloads

  • (...).pdf
    • full text
    • |
    • UGent only
    • |
    • PDF
    • |
    • 388.63 KB
  • 5581 i.pdf
    • full text
    • |
    • open access
    • |
    • PDF
    • |
    • 330.40 KB

Citation

Please use this url to cite or link to this publication:

MLA
Sahhaf, Seyedeh Sahel et al. “Single Failure Resiliency in Greedy Routing.” 9th International Workshop on the Design of Reliable Communication Networks, Proceedings. IEEE, 2013. 306–313. Print.
APA
Sahhaf, S. S., Tavernier, W., Colle, D., Pickavet, M., & Demeester, P. (2013). Single failure resiliency in greedy routing. 9th International Workshop on the Design of Reliable Communication Networks, Proceedings (pp. 306–313). Presented at the 9th International Workshop on the Design of Reliable Communication Networks (DRCN - 2013), IEEE.
Chicago author-date
Sahhaf, Seyedeh Sahel, Wouter Tavernier, Didier Colle, Mario Pickavet, and Piet Demeester. 2013. “Single Failure Resiliency in Greedy Routing.” In 9th International Workshop on the Design of Reliable Communication Networks, Proceedings, 306–313. IEEE.
Chicago author-date (all authors)
Sahhaf, Seyedeh Sahel, Wouter Tavernier, Didier Colle, Mario Pickavet, and Piet Demeester. 2013. “Single Failure Resiliency in Greedy Routing.” In 9th International Workshop on the Design of Reliable Communication Networks, Proceedings, 306–313. IEEE.
Vancouver
1.
Sahhaf SS, Tavernier W, Colle D, Pickavet M, Demeester P. Single failure resiliency in greedy routing. 9th International Workshop on the Design of Reliable Communication Networks, Proceedings. IEEE; 2013. p. 306–13.
IEEE
[1]
S. S. Sahhaf, W. Tavernier, D. Colle, M. Pickavet, and P. Demeester, “Single failure resiliency in greedy routing,” in 9th International Workshop on the Design of Reliable Communication Networks, Proceedings, Budapest, Hungary, 2013, pp. 306–313.
@inproceedings{3259301,
  abstract     = {Using greedy routing, network nodes forward packets towards neighbors which are closer to their destination. This approach makes greedy routers significantly more memory-efficient than traditional IP-routers using longest-prefix matching. Greedy embeddings map network nodes to coordinates, such that greedy routing always leads to the destination. Prior works showed that using a spanning tree of the network topology, greedy embeddings can be found in different metric spaces for any graph. However, a single link/node failure might affect the greedy embedding and causes the packets to reach a dead end. In order to cope with network failures, existing greedy methods require large resources and cause significant loss in the quality of the routing (stretch loss). We propose efficient recovery techniques which require very limited resources with minor effect on the stretch. As the proposed techniques are protection, the switch-over takes place very fast. Low overhead, simplicity and scalability of the methods make them suitable for large-scale networks. The proposed schemes are validated on large topologies with properties similar to the Internet. The performances of the schemes are compared with an existing alternative referred as gravity pressure routing.},
  author       = {Sahhaf, Seyedeh Sahel and Tavernier, Wouter and Colle, Didier and Pickavet, Mario and Demeester, Piet},
  booktitle    = {9th International Workshop on the Design of Reliable Communication Networks, Proceedings},
  isbn         = {9781479900497},
  keywords     = {NETWORKS,IBCN,GRAPHS,TREES},
  language     = {eng},
  location     = {Budapest, Hungary},
  pages        = {306--313},
  publisher    = {IEEE},
  title        = {Single failure resiliency in greedy routing},
  year         = {2013},
}

Web of Science
Times cited: