[Nrg-l] MA Defense: Sam Epstein (next Fri 10/17 @ 9:30AM)

Abraham Matta matta at cs.bu.edu
Thu Oct 9 14:58:41 EDT 2008


Computer Science Department
Boston University

Date: Friday October 17, 2008
Time: 9:30AM
Place: Room MCS 135, 111 Cummington Street

An Online Distributed Algorithm for Inferring
Policy Routing Configurations
Sam Epstein
We present an online distributed algorithm, the Causation
Logging Algorithm (CLA), in which Autonomous Systems
(ASes) in the Internet individually report route oscillations/flaps
they experience to a central Internet Routing Registry (IRR).
The IRR aggregates these reports and may observe what we
call causation chains where each node on the chain caused
a route flap at the next node along the chain. A chain may
also have a causation cycle. The type of an observed causation
chain/cycle allows the IRR to infer the underlying policy routing
configuration (i.e., the system of economic relationships and
constraints on route/path preferences).

Our algorithm is based on a formal policy routing model that
captures the propagation dynamics of route flaps under arbitrary
changes in topology or path preferences. We derive invariant
properties of causation chains/cycles for ASes which conform to
economic relationships based on the popular Gao-Rexford model.
The Gao-Rexford model is known to be safe in the sense that
the system always converges to a stable set of paths under static
conditions. Our CLA algorithm recovers the type/property of an
observed causation chain of an underlying system and determines
whether it conforms to the safe economic Gao-Rexford model.
Causes for nonconformity can be diagnosed by comparing the
properties of the causation chains with those predicted from
different variants of the Gao-Rexford model.
MA Thesis Examination Committee:
 - Abraham Matta (Advisor, 1st Reader)
 - John Byers (2nd Reader) 

More information about the Nrg-l mailing list