[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


MA THESIS DEFENSE

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
  
Abstract:
 
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