[Nrg-l] Next: An Algebraic Approach to Overlay Network Monitoring

Nahur Fonseca nahur at cs.bu.edu
Thu Oct 14 16:17:50 EDT 2004


Next NRG, Liying Tang will lead the discussion of the following paper:
"An Algebraic Approach to Practical and Scalable Overlay Network
Monitoring" by Yan Chen (Northewestern Univ.) and David Bindel,
Hanhee Song, Randy Katz (UC Berkeley).

The meeting will be held at the Graduate Student Lounge,
next Monday Oct, 18th, at 3 PM, in a tentative to avoid 
conflict with the CS655 seminar which is at 4 PM.

More details in the nrg web site.

The paper can be found in the following link:

And here is the paper's abstract: 

Overlay network monitoring enables distributed Internet applications to
detect and recover from path outages and periods of degraded performance
within seconds. 
For an overlay network with n end hosts, existing systems either require
O(n^2) measurements, and thus lack scalability, or can only estimate the
latency but not congestion or failures. 
Our earlier extended abstract briefly proposes an algebraic approach that
selectively monitors k linearly independent paths that can fully describe
all the O(n^2) paths. 
The loss rates and latency of these k paths can be used to estimate the
loss rates and latency of all other paths. Our scheme only assumes
knowledge of the underlying IP topology, with links dynamically varying
between lossy and normal.

In this paper, we improve, implement and extensively evaluate such a
monitoring system.  
We further make the following contributions: i) scalability analysis 
indicating that for reasonably large n (e.g., 100), the growth of k is
bounded as O(n log n), ii) efficient adaptation algorithms for topology
changes, such as the addition or removal of end hosts and routing changes,
iii) measurement load balancing schemes, and iv) topology measurement
error handling.  
Both simulation and Internet experiments demonstrate we obtain highly
accurate path loss rate estimation while adapting to topology changes
within seconds and handling topology errors.


More information about the Nrg-l mailing list