Network Working Group D. Awduche
`Request for Comments: 3272 Movaz Networks
`Category: Informational A. Chiu
` Celion Networks
` A. Elwalid
` I. Widjaja
` Lucent Technologies
` X. Xiao
` Redback Networks
` May 2002
`
` Overview and Principles of Internet Traffic Engineering
`
`Status of this Memo
`
` This memo provides information for the Internet community. It does
` not specify an Internet standard of any kind. Distribution of this
` memo is unlimited.
`
`Copyright Notice
`
` Copyright (C) The Internet Society (2002). All Rights Reserved.
`
`Abstract
`
` This memo describes the principles of Traffic Engineering (TE) in the
` Internet. The document is intended to promote better understanding
` of the issues surrounding traffic engineering in IP networks, and to
` provide a common basis for the development of traffic engineering
` capabilities for the Internet. The principles, architectures, and
` methodologies for performance evaluation and performance optimization
` of operational IP networks are discussed throughout this document.
`
`Table of Contents
`
` 1.0 Introduction...................................................3
` 1.1 What is Internet Traffic Engineering?.......................4
` 1.2 Scope.......................................................7
` 1.3 Terminology.................................................8
` 2.0 Background....................................................11
` 2.1 Context of Internet Traffic Engineering....................12
` 2.2 Network Context............................................13
` 2.3 Problem Context............................................14
` 2.3.1 Congestion and its Ramifications......................16
` 2.4 Solution Context...........................................16
` 2.4.1 Combating the Congestion Problem......................18
` 2.5 Implementation and Operational Context.....................21
`
`Awduche, et. al. Informational [Page 1]
`
`Arista Networks, Inc.
`Ex. 1026, p. 1
`
`

`

`RFC 3272 Overview and Principles of Internet TE May 2002
`
` 3.0 Traffic Engineering Process Model.............................21
` 3.1 Components of the Traffic Engineering Process Model........23
` 3.2 Measurement................................................23
` 3.3 Modeling, Analysis, and Simulation.........................24
` 3.4 Optimization...............................................25
` 4.0 Historical Review and Recent Developments.....................26
` 4.1 Traffic Engineering in Classical Telephone Networks........26
` 4.2 Evolution of Traffic Engineering in the Internet...........28
` 4.2.1 Adaptive Routing in ARPANET...........................28
` 4.2.2 Dynamic Routing in the Internet.......................29
` 4.2.3 ToS Routing...........................................30
` 4.2.4 Equal Cost Multi-Path.................................30
` 4.2.5 Nimrod................................................31
` 4.3 Overlay Model..............................................31
` 4.4 Constraint-Based Routing...................................32
` 4.5 Overview of Other IETF Projects Related to Traffic
` Engineering................................................32
` 4.5.1 Integrated Services...................................32
` 4.5.2 RSVP..................................................33
` 4.5.3 Differentiated Services...............................34
` 4.5.4 MPLS..................................................35
` 4.5.5 IP Performance Metrics................................36
` 4.5.6 Flow Measurement......................................37
` 4.5.7 Endpoint Congestion Management........................37
` 4.6 Overview of ITU Activities Related to Traffic
` Engineering................................................38
` 4.7 Content Distribution.......................................39
` 5.0 Taxonomy of Traffic Engineering Systems.......................40
` 5.1 Time-Dependent Versus State-Dependent......................40
` 5.2 Offline Versus Online......................................41
` 5.3 Centralized Versus Distributed.............................42
` 5.4 Local Versus Global........................................42
` 5.5 Prescriptive Versus Descriptive............................42
` 5.6 Open-Loop Versus Closed-Loop...............................43
` 5.7 Tactical vs Strategic......................................43
` 6.0 Recommendations for Internet Traffic Engineering..............43
` 6.1 Generic Non-functional Recommendations.....................44
` 6.2 Routing Recommendations....................................46
` 6.3 Traffic Mapping Recommendations............................48
` 6.4 Measurement Recommendations................................49
` 6.5 Network Survivability......................................50
` 6.5.1 Survivability in MPLS Based Networks..................52
` 6.5.2 Protection Option.....................................53
` 6.6 Traffic Engineering in Diffserv Environments...............54
` 6.7 Network Controllability....................................56
` 7.0 Inter-Domain Considerations...................................57
` 8.0 Overview of Contemporary TE Practices in Operational
` IP Networks...................................................59
`
`Awduche, et. al. Informational [Page 2]
`
`Arista Networks, Inc.
`Ex. 1026, p. 2
`
`

`

`RFC 3272 Overview and Principles of Internet TE May 2002
`
` 9.0 Conclusion....................................................63
` 10.0 Security Considerations......................................63
` 11.0 Acknowledgments..............................................63
` 12.0 References...................................................64
` 13.0 Authors’ Addresses...........................................70
` 14.0 Full Copyright Statement.....................................71
`
`1.0 Introduction
`
` This memo describes the principles of Internet traffic engineering.
` The objective of the document is to articulate the general issues and
` principles for Internet traffic engineering; and where appropriate to
` provide recommendations, guidelines, and options for the development
` of online and offline Internet traffic engineering capabilities and
` support systems.
`
` This document can aid service providers in devising and implementing
` traffic engineering solutions for their networks. Networking
` hardware and software vendors will also find this document helpful in
` the development of mechanisms and support systems for the Internet
` environment that support the traffic engineering function.
`
` This document provides a terminology for describing and understanding
` common Internet traffic engineering concepts. This document also
` provides a taxonomy of known traffic engineering styles. In this
` context, a traffic engineering style abstracts important aspects from
` a traffic engineering methodology. Traffic engineering styles can be
` viewed in different ways depending upon the specific context in which
` they are used and the specific purpose which they serve. The
` combination of styles and views results in a natural taxonomy of
` traffic engineering systems.
`
` Even though Internet traffic engineering is most effective when
` applied end-to-end, the initial focus of this document document is
` intra-domain traffic engineering (that is, traffic engineering within
` a given autonomous system). However, because a preponderance of
` Internet traffic tends to be inter-domain (originating in one
` autonomous system and terminating in another), this document provides
` an overview of aspects pertaining to inter-domain traffic
` engineering.
`
` The key words "MUST", "MUST NOT", "REQUIRED", "SHALL", "SHALL NOT",
` "SHOULD", "SHOULD NOT", "RECOMMENDED", "MAY", and "OPTIONAL" in this
` document are to be interpreted as described in RFC 2119.
`
`Awduche, et. al. Informational [Page 3]
`
`Arista Networks, Inc.
`Ex. 1026, p. 3
`
`

`

`RFC 3272 Overview and Principles of Internet TE May 2002
`
`1.1. What is Internet Traffic Engineering?
`
` Internet traffic engineering is defined as that aspect of Internet
` network engineering dealing with the issue of performance evaluation
` and performance optimization of operational IP networks. Traffic
` Engineering encompasses the application of technology and scientific
` principles to the measurement, characterization, modeling, and
` control of Internet traffic [RFC-2702, AWD2].
`
` Enhancing the performance of an operational network, at both the
` traffic and resource levels, are major objectives of Internet traffic
` engineering. This is accomplished by addressing traffic oriented
` performance requirements, while utilizing network resources
` economically and reliably. Traffic oriented performance measures
` include delay, delay variation, packet loss, and throughput.
`
` An important objective of Internet traffic engineering is to
` facilitate reliable network operations [RFC-2702]. Reliable network
` operations can be facilitated by providing mechanisms that enhance
` network integrity and by embracing policies emphasizing network
` survivability. This results in a minimization of the vulnerability
` of the network to service outages arising from errors, faults, and
` failures occurring within the infrastructure.
`
` The Internet exists in order to transfer information from source
` nodes to destination nodes. Accordingly, one of the most significant
` functions performed by the Internet is the routing of traffic from
` ingress nodes to egress nodes. Therefore, one of the most
` distinctive functions performed by Internet traffic engineering is
` the control and optimization of the routing function, to steer
` traffic through the network in the most effective way.
`
` Ultimately, it is the performance of the network as seen by end users
` of network services that is truly paramount. This crucial point
` should be considered throughout the development of traffic
` engineering mechanisms and policies. The characteristics visible to
` end users are the emergent properties of the network, which are the
` characteristics of the network when viewed as a whole. A central
` goal of the service provider, therefore, is to enhance the emergent
` properties of the network while taking economic considerations into
` account.
`
` The importance of the above observation regarding the emergent
` properties of networks is that special care must be taken when
` choosing network performance measures to optimize. Optimizing the
` wrong measures may achieve certain local objectives, but may have
`
`Awduche, et. al. Informational [Page 4]
`
`Arista Networks, Inc.
`Ex. 1026, p. 4
`
`

`

`RFC 3272 Overview and Principles of Internet TE May 2002
`
` disastrous consequences on the emergent properties of the network and
` thereby on the quality of service perceived by end-users of network
` services.
`
` A subtle, but practical advantage of the systematic application of
` traffic engineering concepts to operational networks is that it helps
` to identify and structure goals and priorities in terms of enhancing
` the quality of service delivered to end-users of network services.
` The application of traffic engineering concepts also aids in the
` measurement and analysis of the achievement of these goals.
`
` The optimization aspects of traffic engineering can be achieved
` through capacity management and traffic management. As used in this
` document, capacity management includes capacity planning, routing
` control, and resource management. Network resources of particular
` interest include link bandwidth, buffer space, and computational
` resources. Likewise, as used in this document, traffic management
` includes (1) nodal traffic control functions such as traffic
` conditioning, queue management, scheduling, and (2) other functions
` that regulate traffic flow through the network or that arbitrate
` access to network resources between different packets or between
` different traffic streams.
`
` The optimization objectives of Internet traffic engineering should be
` viewed as a continual and iterative process of network performance
` improvement and not simply as a one time goal. Traffic engineering
` also demands continual development of new technologies and new
` methodologies for network performance enhancement.
`
` The optimization objectives of Internet traffic engineering may
` change over time as new requirements are imposed, as new technologies
` emerge, or as new insights are brought to bear on the underlying
` problems. Moreover, different networks may have different
` optimization objectives, depending upon their business models,
` capabilities, and operating constraints. The optimization aspects of
` traffic engineering are ultimately concerned with network control
` regardless of the specific optimization goals in any particular
` environment.
`
` Thus, the optimization aspects of traffic engineering can be viewed
` from a control perspective. The aspect of control within the
` Internet traffic engineering arena can be pro-active and/or reactive.
` In the pro-active case, the traffic engineering control system takes
` preventive action to obviate predicted unfavorable future network
` states. It may also take perfective action to induce a more
` desirable state in the future. In the reactive case, the control
` system responds correctively and perhaps adaptively to events that
` have already transpired in the network.
`
`Awduche, et. al. Informational [Page 5]
`
`Arista Networks, Inc.
`Ex. 1026, p. 5
`
`

`

`RFC 3272 Overview and Principles of Internet TE May 2002
`
` The control dimension of Internet traffic engineering responds at
` multiple levels of temporal resolution to network events. Certain
` aspects of capacity management, such as capacity planning, respond at
` very coarse temporal levels, ranging from days to possibly years.
` The introduction of automatically switched optical transport networks
` (e.g., based on the Multi-protocol Lambda Switching concepts) could
` significantly reduce the lifecycle for capacity planning by
` expediting provisioning of optical bandwidth. Routing control
` functions operate at intermediate levels of temporal resolution,
` ranging from milliseconds to days. Finally, the packet level
` processing functions (e.g., rate shaping, queue management, and
` scheduling) operate at very fine levels of temporal resolution,
` ranging from picoseconds to milliseconds while responding to the
` real-time statistical behavior of traffic. The subsystems of
` Internet traffic engineering control include: capacity augmentation,
` routing control, traffic control, and resource control (including
` control of service policies at network elements). When capacity is
` to be augmented for tactical purposes, it may be desirable to devise
` a deployment plan that expedites bandwidth provisioning while
` minimizing installation costs.
`
` Inputs into the traffic engineering control system include network
` state variables, policy variables, and decision variables.
`
` One major challenge of Internet traffic engineering is the
` realization of automated control capabilities that adapt quickly and
` cost effectively to significant changes in a network’s state, while
` still maintaining stability.
`
` Another critical dimension of Internet traffic engineering is network
` performance evaluation, which is important for assessing the
` effectiveness of traffic engineering methods, and for monitoring and
` verifying compliance with network performance goals. Results from
` performance evaluation can be used to identify existing problems,
` guide network re-optimization, and aid in the prediction of potential
` future problems.
`
` Performance evaluation can be achieved in many different ways. The
` most notable techniques include analytical methods, simulation, and
` empirical methods based on measurements. When analytical methods or
` simulation are used, network nodes and links can be modeled to
` capture relevant operational features such as topology, bandwidth,
` buffer space, and nodal service policies (link scheduling, packet
` prioritization, buffer management, etc.). Analytical traffic models
` can be used to depict dynamic and behavioral traffic characteristics,
` such as burstiness, statistical distributions, and dependence.
`
`Awduche, et. al. Informational [Page 6]
`
`Arista Networks, Inc.
`Ex. 1026, p. 6
`
`

`

`RFC 3272 Overview and Principles of Internet TE May 2002
`
` Performance evaluation can be quite complicated in practical network
` contexts. A number of techniques can be used to simplify the
` analysis, such as abstraction, decomposition, and approximation. For
` example, simplifying concepts such as effective bandwidth and
` effective buffer [Elwalid] may be used to approximate nodal behaviors
` at the packet level and simplify the analysis at the connection
` level. Network analysis techniques using, for example, queuing
` models and approximation schemes based on asymptotic and
` decomposition techniques can render the analysis even more tractable.
` In particular, an emerging set of concepts known as network calculus
` [CRUZ] based on deterministic bounds may simplify network analysis
` relative to classical stochastic techniques. When using analytical
` techniques, care should be taken to ensure that the models faithfully
` reflect the relevant operational characteristics of the modeled
` network entities.
`
` Simulation can be used to evaluate network performance or to verify
` and validate analytical approximations. Simulation can, however, be
` computationally costly and may not always provide sufficient
` insights. An appropriate approach to a given network performance
` evaluation problem may involve a hybrid combination of analytical
` techniques, simulation, and empirical methods.
`
` As a general rule, traffic engineering concepts and mechanisms must
` be sufficiently specific and well defined to address known
` requirements, but simultaneously flexible and extensible to
` accommodate unforeseen future demands.
`
`1.2. Scope
`
` The scope of this document is intra-domain traffic engineering; that
` is, traffic engineering within a given autonomous system in the
` Internet. This document will discuss concepts pertaining to intra-
` domain traffic control, including such issues as routing control,
` micro and macro resource allocation, and the control coordination
` problems that arise consequently.
`
` This document will describe and characterize techniques already in
` use or in advanced development for Internet traffic engineering. The
` way these techniques fit together will be discussed and scenarios in
` which they are useful will be identified.
`
` While this document considers various intra-domain traffic
` engineering approaches, it focuses more on traffic engineering with
` MPLS. Traffic engineering based upon manipulation of IGP metrics is
` not addressed in detail. This topic may be addressed by other
` working group document(s).
`
`Awduche, et. al. Informational [Page 7]
`
`Arista Networks, Inc.
`Ex. 1026, p. 7
`
`

`

`RFC 3272 Overview and Principles of Internet TE May 2002
`
` Although the emphasis is on intra-domain traffic engineering, in
` Section 7.0, an overview of the high level considerations pertaining
` to inter-domain traffic engineering will be provided. Inter-domain
` Internet traffic engineering is crucial to the performance
` enhancement of the global Internet infrastructure.
`
` Whenever possible, relevant requirements from existing IETF documents
` and other sources will be incorporated by reference.
`
`1.3 Terminology
`
` This subsection provides terminology which is useful for Internet
` traffic engineering. The definitions presented apply to this
` document. These terms may have other meanings elsewhere.
`
` - Baseline analysis:
` A study conducted to serve as a baseline for comparison to
` the actual behavior of the network.
`
` - Busy hour:
` A one hour period within a specified interval of time
` (typically 24 hours) in which the traffic load in a network
` or sub-network is greatest.
`
` - Bottleneck:
` A network element whose input traffic rate tends to be
` greater than its output rate.
`
` - Congestion:
` A state of a network resource in which the traffic incident
` on the resource exceeds its output capacity over an interval
` of time.
`
` - Congestion avoidance:
` An approach to congestion management that attempts to
` obviate the occurrence of congestion.
`
` - Congestion control:
` An approach to congestion management that attempts to remedy
` congestion problems that have already occurred.
`
` - Constraint-based routing:
` A class of routing protocols that take specified traffic
` attributes, network constraints, and policy constraints into
` account when making routing decisions. Constraint-based
` routing is applicable to traffic aggregates as well as
` flows. It is a generalization of QoS routing.
`
`Awduche, et. al. Informational [Page 8]
`
`Arista Networks, Inc.
`Ex. 1026, p. 8
`
`

`

`RFC 3272 Overview and Principles of Internet TE May 2002
`
` - Demand side congestion management:
` A congestion management scheme that addresses congestion
` problems by regulating or conditioning offered load.
`
` - Effective bandwidth:
` The minimum amount of bandwidth that can be assigned to a
` flow or traffic aggregate in order to deliver ’acceptable
` service quality’ to the flow or traffic aggregate.
`
` - Egress traffic:
` Traffic exiting a network or network element.
`
` - Hot-spot:
` A network element or subsystem which is in a state of
` congestion.
`
` - Ingress traffic:
` Traffic entering a network or network element.
`
` - Inter-domain traffic:
` Traffic that originates in one Autonomous system and
` terminates in another.
`
` - Loss network:
` A network that does not provide adequate buffering for
` traffic, so that traffic entering a busy resource within the
` network will be dropped rather than queued.
`
` - Metric:
` A parameter defined in terms of standard units of
` measurement.
`
` - Measurement Methodology:
` A repeatable measurement technique used to derive one or
` more metrics of interest.
`
` - Network Survivability:
` The capability to provide a prescribed level of QoS for
` existing services after a given number of failures occur
` within the network.
`
` - Offline traffic engineering:
` A traffic engineering system that exists outside of the
` network.
`
`Awduche, et. al. Informational [Page 9]
`
`Arista Networks, Inc.
`Ex. 1026, p. 9
`
`

`

`RFC 3272 Overview and Principles of Internet TE May 2002
`
` - Online traffic engineering:
` A traffic engineering system that exists within the network,
` typically implemented on or as adjuncts to operational
` network elements.
`
` - Performance measures:
` Metrics that provide quantitative or qualitative measures of
` the performance of systems or subsystems of interest.
`
` - Performance management:
` A systematic approach to improving effectiveness in the
` accomplishment of specific networking goals related to
` performance improvement.
`
` - Performance Metric:
` A performance parameter defined in terms of standard units
` of measurement.
`
` - Provisioning:
` The process of assigning or configuring network resources to
` meet certain requests.
`
` - QoS routing:
` Class of routing systems that selects paths to be used by a
` flow based on the QoS requirements of the flow.
`
` - Service Level Agreement:
` A contract between a provider and a customer that guarantees
` specific levels of performance and reliability at a certain
` cost.
`
` - Stability:
` An operational state in which a network does not oscillate
` in a disruptive manner from one mode to another mode.
`
` - Supply side congestion management:
` A congestion management scheme that provisions additional
` network resources to address existing and/or anticipated
` congestion problems.
`
` - Transit traffic:
` Traffic whose origin and destination are both outside of the
` network under consideration.
`
` - Traffic characteristic:
` A description of the temporal behavior or a description of
` the attributes of a given traffic flow or traffic aggregate.
`
`Awduche, et. al. Informational [Page 10]
`
`Arista Networks, Inc.
`Ex. 1026, p. 10
`
`

`

`RFC 3272 Overview and Principles of Internet TE May 2002
`
` - Traffic engineering system:
` A collection of objects, mechanisms, and protocols that are
` used conjunctively to accomplish traffic engineering
` objectives.
`
` - Traffic flow:
` A stream of packets between two end-points that can be
` characterized in a certain way. A micro-flow has a more
` specific definition: A micro-flow is a stream of packets
` with the same source and destination addresses, source and
` destination ports, and protocol ID.
`
` - Traffic intensity:
` A measure of traffic loading with respect to a resource
` capacity over a specified period of time. In classical
` telephony systems, traffic intensity is measured in units of
` Erlang.
`
` - Traffic matrix:
` A representation of the traffic demand between a set of
` origin and destination abstract nodes. An abstract node can
` consist of one or more network elements.
`
` - Traffic monitoring:
` The process of observing traffic characteristics at a given
` point in a network and collecting the traffic information
` for analysis and further action.
`
` - Traffic trunk:
` An aggregation of traffic flows belonging to the same class
` which are forwarded through a common path. A traffic trunk
` may be characterized by an ingress and egress node, and a
` set of attributes which determine its behavioral
` characteristics and requirements from the network.
`
`2.0 Background
`
` The Internet has quickly evolved into a very critical communications
` infrastructure, supporting significant economic, educational, and
` social activities. Simultaneously, the delivery of Internet
` communications services has become very competitive and end-users are
` demanding very high quality service from their service providers.
` Consequently, performance optimization of large scale IP networks,
` especially public Internet backbones, have become an important
` problem. Network performance requirements are multi-dimensional,
` complex, and sometimes contradictory; making the traffic engineering
` problem very challenging.
`
`Awduche, et. al. Informational [Page 11]
`
`Arista Networks, Inc.
`Ex. 1026, p. 11
`
`

`

`RFC 3272 Overview and Principles of Internet TE May 2002
`
` The network must convey IP packets from ingress nodes to egress nodes
` efficiently, expeditiously, and economically. Furthermore, in a
` multiclass service environment (e.g., Diffserv capable networks), the
` resource sharing parameters of the network must be appropriately
` determined and configured according to prevailing policies and
` service models to resolve resource contention issues arising from
` mutual interference between packets traversing through the network.
` Thus, consideration must be given to resolving competition for
` network resources between traffic streams belonging to the same
` service class (intra-class contention resolution) and traffic streams
` belonging to different classes (inter-class contention resolution).
`
`2.1 Context of Internet Traffic Engineering
`
` The context of Internet traffic engineering pertains to the scenarios
` where traffic engineering is used. A traffic engineering methodology
` establishes appropriate rules to resolve traffic performance issues
` occurring in a specific context. The context of Internet traffic
` engineering includes:
`
` (1) A network context defining the universe of discourse, and in
` particular the situations in which the traffic engineering
` problems occur. The network context includes network
` structure, network policies, network characteristics,
` network constraints, network quality attributes, and network
` optimization criteria.
`
` (2) A problem context defining the general and concrete issues
` that traffic engineering addresses. The problem context
` includes identification, abstraction of relevant features,
` representation, formulation, specification of the
` requirements on the solution space, and specification of the
` desirable features of acceptable solutions.
`
` (3) A solution context suggesting how to address the issues
` identified by the problem context. The solution context
` includes analysis, evaluation of alternatives, prescription,
` and resolution.
`
` (4) An implementation and operational context in which the
` solutions are methodologically instantiated. The
` implementation and operational context includes planning,
` organization, and execution.
`
` The context of Internet traffic engineering and the different problem
` scenarios are discussed in the following subsections.
`
`Awduche, et. al. Informational [Page 12]
`
`Arista Networks, Inc.
`Ex. 1026, p. 12
`
`

`

`RFC 3272 Overview and Principles of Internet TE May 2002
`
`2.2 Network Context
`
` IP networks range in size from small clusters of routers situated
` within a given location, to thousands of interconnected routers,
` switches, and other components distributed all over the world.
`
` Conceptually, at the most basic level of abstraction, an IP network
` can be represented as a distributed dynamical system consisting of:
` (1) a set of interconnected resources which provide transport
` services for IP traffic subject to certain constraints, (2) a demand
` system representing the offered load to be transported through the
` network, and (3) a response system consisting of network processes,
` protocols, and related mechanisms which facilitate the movement of
` traffic through the network [see also AWD2].
`
` The network elements and resources may have specific characteristics
` restricting the manner in which the demand is handled. Additionally,
` network resources may be equipped with traffic control mechanisms
` superintending the way in which the demand is serviced. Traffic
` control me