[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


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