AT&T Labs Research — Leading Invention, Driving Innovation

(c) ACM, 2012. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in NANOG 54 , 2012-02-06.

{Knowing what paths packets are taking within a network is crucial for several network management tasks. When the network is running OSPF, determining paths is supposedly straight-forward, since OSPF is basically a link-state protocol, and with link-state protocols, a packet follows the shortest path in terms of link weights from its source to the destination. However, OSPF allows a network to be divided into areas for scalability, and this makes it more than a link-state protocol. As a result, though packets still follow shortest paths within an area, this is not guaranteed to be the case across areas. In fact, paths followed by packets with areas can often be unexpected and non-intuitive. Some recent extensions to OSPF, namely multi-area adjacencies (RFC 5185) and alternative implementation of border routers (RFC 3509), have further exacerbated the situation. This presentation illustrates such cases with examples, while providing insights into why OSPF paths can look so strange with areas. }

The definitive version was published in SIAM Journal on Computing. , 2011-06-01

{From a high volume stream of weighted items, we want to maintain a generic sample of a certain limited size k that we can later use to estimate the total weight of arbitrary subsets. This is the classic context of on-line reservoir sampling, thinking of the generic sample as a reservoir. We present an efficient reservoir sampling scheme, VAROPTk, that dominates all previous schemes in terms of estimation quality. VAROPTk provides variance optimal unbiased estimation of subset sums. More precisely, if we have seen n items of the stream, then for any subset size m, our scheme based on k samples minimizes the average variance over all subsets of size m. In fact, the optimality is against any off-line scheme with k samples tailored for the concrete set of items seen. In addition to optimal average variance, our scheme provides tighter worst-case bounds on the variance of particular subsets than previously possible. It is efficient, handling each new item of the stream in O(log k) time. Finally, it is particularly well suited for combination of samples from different streams in a distributed setting. }

(c) ACM, 2010. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM Internet Measurement Conference , 2010-11-01.

{The reconvergence of routing protocols in response to changes in network topology can impact application performance. While improvements in protocol specification and implementation have significantly reduced reconvergence times, increasingly performance-sensitive applications continue to raise the bar for these protocols. As such, monitoring the performance of routing protocols remains a critical activity for network operators. We design FlowRoute, a tool based on passive data plane measurements that we use in conjunction with control plane monitors for offline debugging and analysis of forwarding table dynamics. We discuss practical constraints that affect FlowRoute, and show how they can be addressed in real deployment scenarios. As an application of FlowRoute, we study forwarding table updates by backbone routers at a tier-1 ISP. We detect interesting behavior such as delayed forwarding table updates and routing loops due to buggy routers � confirmed by network opera- tors � that are not detectable using traditional control plane monitors.}

(c) ACM, 2008. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in ACM SIGMETRICS 2008 , 2008-06-06.

{Enterprise customers are increasingly adopting MPLS(Multiprotocol Label Switching) VPN (Virtual Private Network) service that offers direct any-to-any reachability among the customer sites via a provider network. Unfortunately this direct reachability model makes the service provider's routing tables grow very large as the number of VPNs and the number of routes per customer increase. As a result, router memory in the provider's network has become a key bottleneck in provisioning new customers. This paper proposes Relaying, a scalable VPN routing architecture that the provider can implement simply by modifying the configuration of routers in the provider network, without requiring changes to the router hardware and software. Relaying substantially reduces the memory footprint of VPNs by choosing a small number of hub routers in each VPN that maintain full reachability information, and by allowing nonhub routers to reach other routers through a hub. Deploying Relaying in practice, however, poses a challenging optimization problem that involves minimizing router memory usage by having as few hubs as possible, while limiting the additional latency due to indirect delivery via a hub. We first investigate the fundamental tension between the two objectives and then develop algorithms to solve the optimization problem by leveraging some unique properties of VPNs, such as sparsity of traffic matrices and spatial locality of customer sites. Extensive evaluations using real traffic matrices, routing configurations, and VPN topologies demonstrates that Relaying is very promising and can reduce routing-table usage by up to 90%, while increasing the additional distances traversed by traffic by only a few hundred miles, and the backbone bandwidth usage by less than 10%. }

Awards
Science & Technology Medal, 2005. Honored for fundamental advances in algorithms and complexity, and their application to network design and management.

Goedel Prize, 2001.