• Calendar

April 7, Monday
14:00 – 15:30

The Internet is an indispensable part of our society, and yet its basic foundations remain vulnerable to simple attacks. In recent years, the networking community has considered a variety of proposals for securing Internet routing; path-quality monitoring is a crucial component of many of these proposals.

In this talk, we give a rigorous treatment of the path-quality monitoring problem. We consider protocols that allow a router to robustly raise an alarm when packet loss and delay exceeds some threshold, even when an adversary tries to bias monitoring results. Despite the strong threat model we considered, we develop secure protocols that efficient enough to be deployed in the highly constrained environment of high-speed routers. We present a simple protocol that combines sketching techniques with ideas from cryptography and requires O(log T) storage in order to monitor T packets sent on an Internet data path; e.g., monitoring billions of packets requires only 200-600 bytes of storage and a single IP packet of communication. We then show how to compose instances of this protocol to obtain a protocol that localizes faulty or malfunctioning links on a data path.

This is joint work with David Xiao, Eran Tromer, Boaz Barak, and Jennifer Rexford.