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

Abraham Matta matta at cs.bu.edu
Thu Oct 16 19:34:58 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
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