IEEE/ACM TRANSACTIONS ON NETWORKING, VOL 9, NO. 3, JUNE 2001 265 Deriving Traffic Demands for Operational IP Networks: Methodology and Experience Anja Feldmann, Member, IEEE, Albert Greenberg, Member, IEEE, Carsten Lund, Nick Reingold, Jennifer Rexford, Member, IEEE, and Fred True AbstractmEngineering a large IP backbone network without an accurate network-wide view of the traffic demands is challenging. Shifts in user behavior, changes in routing policies, and failures of network elements can result in significant (and sudden) fluctua- tions in load. In this paper, we present a model of traffic demands to support traffic engineering and performance debugging of large Internet Service Provider networks. By defining a traffic demand as a volume of load originating from an ingress link and destined to a set of egress links, we can capture and predict how routing affects the traffic traveling between domains. To infer the traffic demands, we propose a measurement methodology that combines flow-level measurements collected at all ingress links with reachability infor- marion about all egress links. We discuss how to cope with situa- tions where practical considerations limit the amount and quality of the necessary data. Specifically, we show how to infer interdo- main traffic demands using measurements collected at a smaller number of edge links---the peering links connecting to neighboring providers. We report on our experiences in deriving the traffic de- mands in the AT&T IP Backbone, by collecting, validating, and joining very large and diverse sets of usage, configuration, and routing data over extended periods of time. The paper concludes with a preliminary analysis of the observed dynamics of the traffic demands and a discussion of the practical implications for traffic engineering. Index Terms--Internet, measurement, routing, traffic engi- neering. I. INTRODUCTION T HE engineering of large IP backbone networks faces a number of difficult challenges. Owing to the astonishing success of Internet applications and the continuing rollout of faster access technologies, demand for bandwidth across backbones is growing explosively. In addition, shifts in user behavior, publishing of new Web content, and deployment of new applications result in significant fluctuations in the volume of traffic exchanged between various hosts in the In- ternet. Furthermore, changes in routing policies and failures of network elements can cause sudden fluctuations in how traffic flows through the backbone. This leaves network operators in the difficult situation of trying to tune the configuration of the network to adapt to changes in the traffic demands. The task is particularly daunting since the Internet Service Provider Manuscript received July 17, 2000; revised November 14, 2000; approved by IEEE/ACM TRANSACTIONS ON NETWORKING Editor C. Diot. A. Feldmann is with the Computer Science Department, University of Saar- briicken, Saarbriicken D-66123, Germany (e-mail: [email protected]). A. Greenberg, C. Lund, N. Reingold, J. Rexford, and E True are with the In- ternet and Networking Systems Center, AT&T Labs--Research, Florham Park, NJ 07932 USA (e-mail: [email protected]; [email protected]; rein- [email protected]; [email protected]; [email protected]). Publisher Item Identifier S 1063-6692(01)04728-8. (ISP) responsible for administering the backbone does not have end-to-end control of the path from the source to the destina- tion. The majority of traffic in an Internet Service Provider • network travels across multiple administrative domains. The networking community has responded with research and development on increasing link and router capacity and pro- viding a more easily configurable infrastructure. However, rel- atively little attention has been given to the systems needed to guide the operation and management of the improved infrastruc- ture. In particular, there has been very little work on models for traffic demands or on techniques for populating these models from network measurements. Most existing measurement tech- niques provide views of the effects of the traffic demands--poor end-to-end performance (e.g., high delay and low throughput) and heavy load (e.g., high link utilization and long queues). These effects are captured by active measurements of delay, loss, or throughput on a path through the network [1], or pas- sive monitoring of individual routers and links [2], [3]. However, managing an ISP backbone begs for a network-wide understanding of the flow of traffic. An accurate view of the traffic demands is crucial for a number of important tasks, such as debugging performance problems, optimizing the configura- tion of the routing protocols, and planning the rollout of new capacity. In particular, the recently formed IETF working group on Internet Traffic Engineering recognizes that 1) accurate de- mand models are crucial for effective traffic engineering of IP networks, but 2) developing such models and populating them via appropriate measurements are open problems [4], [5]. These are precisely the topics we address in this paper. As far as we know, no comparable study of the network-wide traffic demands in an ISP backbone has been conducted to date. How should traffic demands be modeled and inferred from network measurements? At one extreme, IP traffic could be rep- resented at the level of individual source-destination pairs, pos- sibly aggregating sources and destinations to the network ad- dress or autonomous system level. Such an end-to-end traffic matrix would lend insight into the fluctuations in load over the Internet across time. However, representing all hosts or network addresses would result in an extremely large traffic matrix. In addition, no single ISP is likely to see all of the traffic to and from each network address, making it virtually impossible to populate such a model. Alternatively, IP traffic could be aggregated to point-to-point demands between edge links or routers in the ISP backbone, an option suggested in [6] in the context of MPLS-enabled net- works. However, this approach has fundamental difficulty in dealing with traffic that traverses multiple domains. A given 1063~5692/01510.00 © 2001 IEEE266 IEEE/ACM TRANSACTIONS ON NETWORKING, VOL. 9, NO. 3, JUNE 2001 Fig. 1. source ~estination, ISP Backbone