Michael Borokhovich
Michael Borokhovich has a total of 17 co-authors. Here are the top co-authors by number of shared publications:
- Chen Avin
Ben-Gurion University of the Negev, Beer Sheva, Israel
4 shared publications - Stefan Schmid
TU Berlin & Weizenbaum Institute, Berlin, Germany
3 shared publications Zvi Lotker
3 shared publicationsDavid Peleg
2 shared publications- Gianni Antichi
Politecnico di Milano & Queen Mary University of London, London, United Kingdom
2 shared publications - Marco Chiesa
KTH Royal Institute of Technology, Stockholm, Sweden
2 shared publications
Latest Publications
- 6 January 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 29 (2) , 637-650
Fast ReRoute on Programmable Switches
Highly dependable communication networks usually rely on some kind of Fast Re-Route (FRR) mechanism which allows to quickly re-route traffic upon failures, entirely in the data plane. This paper studies the design of FRR mechanisms for emerging reconfigurable switches. Our main contribution is an FRR primitive for programmable data planes, PURR, which provides low failover latency and high switch throughput, by avoiding packet recirculation. PURR tolerates multiple concurrent failures and comes with minimal memory requirements, ensuring compact forwarding tables, by unveiling an intriguing connection to classic ``string theory'' (i.e., stringology), and in particular, the shortest common supersequence problem. PURR is well-suited for high-speed match-action forwarding architectures (e.g., PISA) and supports the implementation of a broad variety of FRR mechanisms. Our simulations and prototype implementation (on an FPGA and a Tofino switch) show that PURR improves TCAM memory occupancy by a factor of 1.5x-10.8x compared to a naïve encoding when implementing state-of-the-art FRR mechanisms. PURR also improves the latency and throughput of datacenter traffic up to a factor of 2.8x-5.5x and 1.2x-2x, respectively, compared to approaches based on recirculating packets.
- 6 January 2021
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 29 (2) , 637-650
Fast ReRoute on Programmable Switches
Highly dependable communication networks usually rely on some kind of Fast Re-Route (FRR) mechanism which allows to quickly re-route traffic upon failures, entirely in the data plane. This paper studies the design of FRR mechanisms for emerging reconfigurable switches. Our main contribution is an FRR primitive for programmable data planes, PURR, which provides low failover latency and high switch throughput, by avoiding packet recirculation. PURR tolerates multiple concurrent failures and comes with minimal memory requirements, ensuring compact forwarding tables, by unveiling an intriguing connection to classic ``string theory'' (i.e., stringology), and in particular, the shortest common supersequence problem. PURR is well-suited for high-speed match-action forwarding architectures (e.g., PISA) and supports the implementation of a broad variety of FRR mechanisms. Our simulations and prototype implementation (on an FPGA and a Tofino switch) show that PURR improves TCAM memory occupancy by a factor of 1.5x-10.8x compared to a naïve encoding when implementing state-of-the-art FRR mechanisms. PURR also improves the latency and throughput of datacenter traffic up to a factor of 2.8x-5.5x and 1.2x-2x, respectively, compared to approaches based on recirculating packets.
- Open Access
- 28 September 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 26 (6) , 2583-2597
Load-Optimal Local Fast Rerouting for Dense Networks
Reliable and highly available computer networks must implement resilient fast rerouting mechanisms: upon a link or node failure, an alternative route is determined quickly, without involving the network control plane. Designing such fast failover mechanisms capable of dealing with multiple concurrent failures, however, is challenging, as failover rules need to be installed proactively, i.e., ahead of time, without knowledge of the actual failures happening at runtime. Indeed, only little is known today about the design of resilient routing algorithms. This paper introduces a general framework to reason about and design local failover algorithms that minimize the resulting load after failover on dense networks, beyond destination-based routing. We show that due to the inherent locality of the failover decisions at runtime, the problem is fundamentally related to the field of distributed algorithms without coordination. We derive an intriguing lower bound on the inherent network load overhead any local fast failover scheme that will introduce in the worst case, even though globally seen, much more balanced traffic allocations exist. We then present different randomized and deterministic failover algorithms and analyze their overhead load. In particular, we build upon the theory of combinatorial designs and develop a novel deterministic failover mechanism based on symmetric block design theory, which tolerates a maximal number of link failures while ensuring low loads.
- 28 September 2018
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 26 (6) , 2583-2597
Open AccessLoad-Optimal Local Fast Rerouting for Dense Networks
Reliable and highly available computer networks must implement resilient fast rerouting mechanisms: upon a link or node failure, an alternative route is determined quickly, without involving the network control plane. Designing such fast failover mechanisms capable of dealing with multiple concurrent failures, however, is challenging, as failover rules need to be installed proactively, i.e., ahead of time, without knowledge of the actual failures happening at runtime. Indeed, only little is known today about the design of resilient routing algorithms. This paper introduces a general framework to reason about and design local failover algorithms that minimize the resulting load after failover on dense networks, beyond destination-based routing. We show that due to the inherent locality of the failover decisions at runtime, the problem is fundamentally related to the field of distributed algorithms without coordination. We derive an intriguing lower bound on the inherent network load overhead any local fast failover scheme that will introduce in the worst case, even though globally seen, much more balanced traffic allocations exist. We then present different randomized and deterministic failover algorithms and analyze their overhead load. In particular, we build upon the theory of combinatorial designs and develop a novel deterministic failover mechanism based on symmetric block design theory, which tolerates a maximal number of link failures while ensuring low loads.
- Open Access
- 7 August 2018
- Published by Association for Computing Machinery (ACM)
- p. 52-57
Supporting Emerging Applications With Low-Latency Failover in P4
- 7 August 2018
- Published by Association for Computing Machinery (ACM)
- p. 52-57
Open AccessSupporting Emerging Applications With Low-Latency Failover in P4
- 1 January 2017
- Published by Elsevier in Journal of Parallel and Distributed Computing
- Vol. 99, 51-67
Distributed computing on core–periphery networks: Axiom-based design
- 1 January 2017
- Published by Elsevier in Journal of Parallel and Distributed Computing
- Vol. 99, 51-67
Distributed computing on core–periphery networks: Axiom-based design
- 1 June 2015
- Published by Elsevier in Theoretical Computer Science
- Vol. 584, 91-102
Self-adjusting grid networks to minimize expected path length
- 1 June 2015
- Published by Elsevier in Theoretical Computer Science
- Vol. 584, 91-102
Self-adjusting grid networks to minimize expected path length
- 6 January 2013
- Published by Society for Industrial & Applied Mathematics (SIAM)
- p. 478-497
Generalized Perron–Frobenius Theorem for Multiple Choice Matrices, and Applications
- 6 January 2013
- Published by Society for Industrial & Applied Mathematics (SIAM)
- p. 478-497
Generalized Perron–Frobenius Theorem for Multiple Choice Matrices, and Applications
- 1 January 2009
- Published by INSTICC
- p. 250-257
MASTERING (VIRTUAL) NETWORKS - A Case Study of Virtualizing Internet Lab
- 1 January 2009
- Published by INSTICC
- p. 250-257
MASTERING (VIRTUAL) NETWORKS - A Case Study of Virtualizing Internet Lab