[talks] M Suchara preFPO

[Melissa Lawson]

Martin Suchara will present his preFPO on Tuesday November 23 at 10AM in Room 402.
The members of his committee are:  Jennifer Rexford, advisor; Mung Chiang (ELE) and 
Gordon Wilfong (Bell Labs), readers; Mike Freedman and Ed Felten, nonreaders.  Everyone 
is invited to attend his talk.  His abstract follows below.
---------------------------------------
Reliable Internet Routing

The network routing system is a critical infrastructure that enables communication of
hosts connected to the Internet. Despite its importance, the design is vulnerable to
hardware faults, routing policy misconfigurations, as well as malicious attacks. Each of
these vulnerabilities may either cause loss of availability, or degrade network
performance. This thesis provides several complementary mechanisms that address these
reliability, security and performance concerns. The design of each of these mechanisms
takes into account practical considerations, such as the incentives for adoption, ease of
deployment, or computational complexity of the required calculations.
Preventing BGP Route Oscillations
The Internet consists of tens of thousands of separately administered autonomous systems
with independently chosen routing policies. Policy interactions may cause permanent route
oscillations in the interdomain routing protocol (BGP), leading to degraded network
performance as well as unnecessary message-processing overhead. The first step towards
only using "safe" policies is to understand the exact conditions when these policies
guarantee convergence, and to provide an efficient algorithm that allows such safety
verification. To that end, we develop DPVP, a new theoretical model of routing that is
more amenable to analysis.  DPVP includes several BGP implementation features that have
been omitted in the previous theoretical models. In particular, our model allows
"spurious" announcements of less-preferred routes that may be caused by a variety of
mechanisms integrated in BGP. In this new, more robust model, we derive the necessary and
sufficient condition for safety, which furthermore admits an efficient algorithm for
checking BGP safety in most practical circumstances -- two complementary results that have
been elusive in the past decade's worth of classical studies of BGP convergence in more
simple models.
Securing BGP against Attacks
Integrity of the interdomain routing system is threatened by compromised routers which
announce address prefixes that they do not own. Deployment of the many countermeasures
that have been proposed in the past decade is complicated by the requirement for
cooperation of all of the independently administered autonomous systems. Instead of
requiring unilateral cooperation, we argue that small groups should be the basis for
securing interdomain routing, and we offer a new design where routing is secured by a few
(e.g., 5--10) participating autonomous systems. We conduct extensive simulations and
identify conditions for small groups to be effective. In particular, the participants can
achieve remarkable security gains by filtering compromised interdomain routes, cooperating
to expose additional path diversity, inducing non-participants to select valid routes, and
convincing a few large ISPs to participate. We also propose two novel mechanisms that the
group members can employ to achieve these goals, namely secure overlay routing and the
cooperative announcement of each other's address space. Our experiments show that
combining these two techniques allows small groups to secure interdomain routing. 

Making Routing Failure Resilient
Unexpected hardware failures often result in loss of connectivity or poor performance
while the routing system converges to a new set of paths. To enable reliable data delivery
and balance load in the presence of failures, this thesis proposes a new mechanism that
combines path protection and traffic engineering. The key benefit of our solution is its
simplicity, allowing for fast recovery while imposing minimal requirements on the routers.
To provide resilience against every failure scenario from a known set, we advocate using a
fixed set of parallel end-to-end paths for each traffic demand. Upon detecting a path
failure, the ingress router uses a local rule to rebalance the outgoing traffic on the
remaining available paths. We describe several candidate rebalancing algorithms, and
analyze their performance. Although calculating the optimal set of paths and the
path-splitting parameters for each router is NP-hard, our extensive simulations on a
tier-1 IP backbone demonstrate that our easy-to-calculate heuristic suffices to achieve
nearly optimal load balancing.

Planned Work
In addition to the above, I plan to answer the following questions:
(i)	This work uses the DPVP model to study the dynamics of interdomain routing (eBGP).
How applicable is the model to intradomain routing (iBGP) and what new insights can we
gain?
(ii)	We provide an algorithm that determines routing safety in polynomial time for
virtually all policies that are used by network operators in practice. Is it possible to
formalize the conditions under which the algorithm runs in polynomial time?