Publication Details

Detecting Routing Loops in the Data Plane

KUČERA Jan, BEN Basat Ran, KUKA Mário, ANTICHI Gianni, YU Minlan and MITZENMACHER Michael. Detecting Routing Loops in the Data Plane. In: CoNEXT 2020 - Proceedings of the 16th International Conference on Emerging Networking EXperiments and Technologies. New York, NY: Association for Computing Machinery, 2020, pp. 466-473. ISBN 978-1-4503-7948-9.
Czech title
Detekce směrovacích smyček v datové cestě
Type
conference paper
Language
english
Authors
Kučera Jan, Ing. (DCSY FIT BUT)
Ben Basat Ran (HARVARD)
Kuka Mário, Ing. (CESNET)
Antichi Gianni (QMUL)
Yu Minlan (HARVARD)
Mitzenmacher Michael (HARVARD)
Keywords

Network algorithms, monitoring, routing loop detection, Unroller

Abstract

Routing loops can harm network operation. Existing loop detection mechanisms, including mirroring packets, storing state on switches, or encoding the path onto packets, impose significant overheads on either the switches or the network. We present Unroller, a solution that enables real-time identification of routing loops in the data plane with minimal overheads. Our algorithms encode a varying fixed-size subset of the traversed path on each packet. That way, our overhead is independent of the path length, while we can detect the loop once the packet returns to some encoded switch. We implemented Unroller in P4 and compiled into three different FPGA targets. We then compared it against state-of-the-art solutions on real WAN and data center topologies and show that it requires from 6x to 100x fewer bits added to packets than existing methods.

Published
2020
Pages
466-473
Proceedings
CoNEXT 2020 - Proceedings of the 16th International Conference on Emerging Networking EXperiments and Technologies
Conference
International Conference on emerging Networking EXperiments and Technologies, Barcelona, ES
ISBN
978-1-4503-7948-9
Publisher
Association for Computing Machinery
Place
New York, NY, US
DOI
10.1145/3386367.3431303
EID Scopus
2-s2.0-85097615541
BibTeX 
@INPROCEEDINGS{FITPUB12105,
   author = "Jan Ku\v{c}era and Ran Basat Ben and M\'{a}rio Kuka and Gianni Antichi and Minlan Yu and Michael Mitzenmacher",
   title = "Detecting Routing Loops in the Data Plane",
   pages = "466--473",
   booktitle = "CoNEXT 2020 - Proceedings of the 16th International Conference on Emerging Networking EXperiments and Technologies",
   year = 2020,
   location = "New York, NY, US",
   publisher = "Association for Computing Machinery",
   ISBN = "978-1-4503-7948-9",
   doi = "10.1145/3386367.3431303",
   language = "english",
   url = "https://www.fit.vut.cz/research/publication/12105"
}
Back to top