**** Columbia Network Research Center Seminar ****

Title:    Felix Project:  Inferential Topology Discovery Based on Packet Delay Data
Speaker:  Mark W. Garrett 
          Telcordia Technologie 
When:     Wednesday, February 14, 2001 - 10 am
Where:    Interschool Lab, CEPSR Building, 7th floor
          Columbia University
          Refreshments will be served

Abstract:

We describe a method of determining the essential topology of a
network from strictly end-to-end measurements.  A set of monitors
trade timestamped packets across the target network.  The resulting
record of delay and loss with time is analysed to produce the topology
and an estimate of congestion on each link of the network.  This
method does not require any network management protocols, or for the
routers to do anything except forward packets.

Current research on this problem is generally limited to mapping
multicast trees.  Our solution can map out general mesh networks.  We
break the problem into two components, first correlating the
occurrence of congestion events across different paths to identify
common network components.  The second part creates a best-guess
topology, that is (conveniently) especially successful on realistic
internet-like networks.  (This talk will focus on the first
algorithm.)  Though our models abstract away a few important
properties of real networks, we believe the core ideas will
generalize.  This technology can become the basis for a very flexible
type of network autodiscovery.

Bio: 

Mark W.  Garrett is Director of the Internet Management Research Group
at Telcordia Technologies.  His current work is focused on design and
management of advanced IP-based networks and services.  He was PI of a
Darpa project on independent network monitoring and topology discovery
("Felix project").  Dr.  Garrett co-authored RFC 2381, which deals with
mapping QoS between IP and ATM technologies, and was active for 3 years
in the ATM Forum Traffic Management group.

Dr.  Garrett received the B.S.  (1982) and Ph.D.  (1993) degrees in
Electrical Engineering from Columbia University, and has been with
Telcordia since 1984.  His doctoral thesis included the first
compilation and detailed analysis of a long trace of variable-rate video
traffic.