`International Workshop
`on Quality of Service
`oe
`mn
`IWQOS ’99
`
`London, England
`May 31 —June 4, 1999
`
`[aa
`tte Lt Smet
`
`fg
`
`=
`
`2
`ATIC
`OMMUNIC
`OCIETY
`
`~
`- mK
`
`me
`
`Cloudflare - Exhibit 1019, cover
`
`Cloudflare - Exhibit 1019, cover
`
`
`
`
`
`1999 Seventh
`International Workshop
`on Quality of Service
`
`=
`IWQOS ’99
`
`London, England
`May 31 — June 4, 1999
`
`Sponsored by IEEE Communications Society and
`IFIP WG6.1 in Association with ACM SIGCOMM
`
`With generous support from
`Nortel Research UK
`Hewlett Packard Internet Research Institute,
`Microsoft Research, and Sprint Labs
`
`Cloudflare - Exhibit 1019, pagei
`
`Cloudflare - Exhibit 1019, page i
`
`
`
`1999 Seventh International Workshop on Quality of Service
`
`Abstracting is permitted with credit to the source. Libraries are permitted to photocopy beyondthe
`limits of U.S. copyright law for private use of patrons thosearticles in this volume that carry a
`code at the bottom ofthefirst page, provided the per-copy fee indicated in the codeis paid through
`the Copyright Clearance Center, 222 Rosewood Drive, Danvers, MA 01923. For other copying,
`reprint, or republication permission, write to the IEEE Copyright Manager, IEEE Operations
`Center, 445 Hoes Lane, Piscataway, NJ 08855-1331. All rights reserved. Copyright © 1999 by
`TheInstitute of Electrical and Electronics Engineers, Inc.
`
`ISBN Softbound:
`
`0-7803-5671-3
`
`IEEE Catalog Number:
`
`Library of Congress:
`
`98EX354
`
`99-63125
`
`Additional copies of this publication are available from
`
`IEEE Operations Center
`P. O. Box 1331
`445 Hoes Lane
`Piscataway, NJ 08855-1331 USA
`
`1-800-678-IEEE (1-800-678-4333)
`1-732-981-0060
`1-732-981-1393
`1-732-981-9667 (FAX)
`email: customer.service @ieee.org
`
`"Yurt K. WendtLibrary”
`
`University of Wiscons!
`-Madisog
`4 ee ee
`il Avenue
`215 N. Randall /
`Madison, Wi 53706-1688:
`
`n
`
`Cloudflare - Exhibit 1019, pageii
`
`
`
`Cloudflare - Exhibit 1019, page ii
`
`
`
`IWQoS 799 Table of Contents
`
`Session 1 — Admission Control and Related Matters.............0.0.c.ccccccccssssssssssscsesssssscssesssessssesessavevesesveveesesececescececccce, 1
`
`Measurement-Based Admission Control: Whatis the Research Agenda?..0.........cccsccssssssssssssesesscssssessesseevesceveesene 3
`Lee Breslau, Sugih Jamin, Scott Shenker
`
`The DEY ApprGACh 16 QOS sss crsscsasnsncasaysazacarasnesanamsbeatearatnenss chobehesvokonentveigticensteuuSeerenaceunssvaies Geaxecteasseconos occ 6
`Gunnar Karlsson and Fredrik Orava
`
`IP over Photons: How notto waste the waist of the Hourglass .............cccccscssssesssssecsessesescecssessevereeseceveseecesescesesee. 9
`Jon Crowcroft
`
`Utility Curves: Mean Opinion Scores Considered Biased ........c.ccccccssssesessessssesscsessesvesesessessssesseresversevesvevescessesee 12
`Hendrik Knoche, Herman De Meer, David Kirsh
`
`Session 2 — Distributed QoS Architecture .0...........c.cccccccsccssssssssssssssvssssessvsisatsussssuessaresesvsssssssssvereavessevescevesceseecescecee. 15
`
`Performance of QoS Agents for Provisioning Network ReSOUurces.........scsssssesscssesssesssssesseseseceseseeceeecececececececces. 17
`Olov Schelén , Andreas Nilsson, Joakim Norrgard, Stephen Pink
`
`A Distributed Resource ManagementArchitecture that Supports Advance
`Reservations and Co-Allocation ............ccsssssssesssssssssesssescscsucscssscsucscsvsvsscassvsususasasavsusasasavavarsseavavateavavereeseveceeecs 27
`Ian Foster, Carl Kesselman, Craig Lee, Bob Lindell, Klara Nahrstedt, Alain Roy
`
`OptimalState Prediction for Feedback-Based QoS Adaptions.........c.c.ccccccssssssssessssesceesesessesesesseveveceesesescecececcee. 37
`Baochun Li, Dongyan Xu, Klara Nahrstedt
`
`Session 3 — Software Structures and QOS 0..0.......c.:c:cccssssssssssessessessessessessssussusssssssussussussssssassasesessvsssersateseeseeseeseeseece. 47
`
`The Role of Reflection in Supporting Dynamic QoS ManagementFunctions .......cccccccccccscsscescesescescevescececcescesc. 49
`Gordon Blair , Anders Anderson, Lynne Blair, Geoff Coulson
`
`A Software Framework for Application Level QoS Management.0...........ccccccssesssscesesesseseeseseesesveseevsevescesesceseee. 52
`Varuni Witana, Michael Fry and Mark Antoniades
`
`Securing QoS: Threats to RSVP Messages and Their CountermeasureS.......c.ccccsccsecsssessecseseesescesescersesesceseccescee. 62
`Tsung-Li Wu,S. Felix Wu, Zhi Fu, He Huang, Fengmin Gong
`
`Virtuosity: Performing Virtual Network Resource Management............cccccssessssesescsssseseseevesesceveseseecesescecesescecee. 65
`Andrew T. Campbell, John Vicente, Daniel A. Villela
`
`Session 4 — Performance ..........csss.ssssecscssossoeesssersssessssssessetscsussseusesssenvsbsapsveaavenbeusassussssesssascianscsvensaveveesessoeesccesesessesce 77
`
`OnService Guarantees for Input Buffered Crossbar Switches:
`A Capacity Decomposition Approach by Birkoff and von Neumann...........c.cccccccsccocesesescesesescevececceceseccecescececee. 79
`Cheng-Shang Chang, Wen-Jyh Chen and Hsiang-Yi Huang
`
`QOS Enhancementwith Partial State..........ccccccccsssscscsssscscssscsssvsvsscacssusasscavsuesessssaverssvavevavsteavevevereeveseececescevees 87-
`Deying Tong, A. L. Narasimha Reddy
`
`Evaluation of Differentiated Services using an Implementation under Linux .......cccccccccsesesececececececesecescececececee. 97
`Roland Bless, Klaus Wehrle
`
`
`
`
`
`Cloudflare - Exhibit 1019, page v
`
`Cloudflare - Exhibit 1019, page v
`
`
`
`Session 5 — Routing & Forwarding 2000.00.00... ccscssscsesscssessesessessesecseeseesesecesessesseeseeseeaesaesaseaeeaeeaeeeeersnesaeereneerenees 107
`
`Efficient Multi-field Packet Classification for QOS PUrpoOSes............:csseesesesecesecsseseeesetensessecseceseeateaeeneeneeneens 109
`Niklas Borg, Emil Svanberg and Olov Schelén
`
`Quality-of-Service Routing using Maximally Disjoint Paths ..0...0.. 0. eesseseessesseeeeseesseseeseeseteecneesesecseeaeeees 119
`Nina Taft-Plotkin, Bhargav Bellur and Richard Ogier
`
`Quality-of-Service Routing without Global Information Exchange ..............:ccescssesesscsscnecseeersereesecesseeeeneree 129
`Srihari Nelakuditi, Rose P Tsang, and Zhi-Li Zhang.
`
`A Proposal for an Asymmetric Best-Effort Service... ccscssssscsecseeseceeceecsecsecseeeesecseesecseenessecaseecnecneeseeeenens 132
`Paul Hurley, Jean-Yves Le Boudec
`
`Session 6 — (panel/discussion)
`
`Panel: What Service Differentiation Do Users Really Want?
`
`Session 7 — Appregationisisciciscssssscsscsixiassoassapoases mies ceapesstasviaviseess inp stoanbasdaveroanSenonnetsnrsseroncaeecmnussernnnnannerreesenncenanastes 135
`
`Source-oriented Topology Aggregation with Multiple QoS Parameters
`in Hierarchical ATM Networks sccssccsvescssssssesevesarsesesesssoorsxaevaassxvassensansasaaravesssaeaenaren neues eye ox nev icensamim sass cas doventeene 137
`Turgay Korkmaz and Marwan Krunz
`
`Aggregation of Guaranteed Service PlOWS js scccccssesecseasecnaseacesteevsonercravaucannenseevoruy cuana sivans caucus cece tures seveaswiexeuns caves 147
`Jens Schmitt, Martin Karsten, Lars Wolf, Ralf Steinmetz
`
`Impact of Marking Strategy on Aggregated Flowsina
`Differentiated Services Network o........cecesesccesssseeseceeceseesecsseesecseeesecsecsseseeesseesecsseessesecssessecseseasesecsessaseaeeeseess 156
`Ikjun Yeom,A. L. Narasimha Reddy
`
`Paris Metro Pricing: The Minimalist Differentiated Services Solution ...........ccccceecessessessesseseessescsecsseessecsees 159
`Andrew Odlyzko
`
`SOSSiOMS'— uPCingo oh aie coc cas da os es cvs aie ts av esahins posscaasnnstcntecpr cqqagueewsateneurswneauy sansa reencenronssenreennerkensnasuatnsntversunnwcors 163
`
`Managingand Pricing Service Level Agreements for Differentiated Services ............:ccccccccscsscesseseessessenseeees 165
`Costas Courcoubetis and Vasilios A. Siris
`
`Provider-Oriented Linear Price Calculation for Integrated Services ............ccccccccscecseesscesecsseeessscesecsecsscseeneesees 174
`Martin Karsten, Jens Schmitt, Lars Wolf, Ralf Steinmetz
`
`MarketPricing of Differential Internet Services...........cecscsccssscsseeceseceeesseeeceseeeesseceaeeseeeseseesesssaesssenseseeseeaes 184
`Nemo Semret, Raymond R.F. Liao, Andrew T. Campbell, Aurel A. Lazar
`
`Session 9 — MPLS...0.........cccccccccccesssssscccccccccesseseesssccsccccccceessesensnsussscscecceseseeensnssseecsseeseseesessesersetttetstttasaseseeeeeestssseeess 195
`
`Resource Allocation in Multiservice MPLS ..0..........cceccesssscsseesesneeesecseceeeesecesesscsecsecesesseessecsasaeestsstesssatestenees 197
`MagdaChatzaki, Stelios Sartzetakis, Nikos Papadakis, Costas Courcoubetis
`
`Supporting Differentiated Services in MPLS Networks .0....0....cccccscssessceesscneesceseseseeseseesesecsesesssseestscsesseassteees 207
`Ilias Andrikopoulos, George Pavlou
`
`WebServer QoS Managementby Adaptive Content Delivery... ec eeeeseeeeceteeneeeeeeeeeseeeeesecascsecseeaeeseeaes 216
`Tarek F. Abdelzaher, Nina Bhatti
`
`vi
`
`Cloudflare - Exhibit 1019, pagevi
`
`Cloudflare - Exhibit 1019, page vi
`
`
`
`Session Based Admission Control:
`A Mechanism for Improving Performance of Commercial Web Sites ..0.......... cc ssesseseseeseerseceseeseeteteeeeseeeseneeas 226
`Ludmila Cherkasovaand Peter Phaal
`
`Session 10 — Flow Control & Adaptation & RED .000...........ccccccccssesssccsnecstecssscsseeessecesecseseeeseecseecsssceseseseseseesseenses 237
`
`Hop-by-hop Flow Control as a Method to Improve QoS in 802.3 LANS..........ccsccssssseeseseeesceecneeeesereseneneesens 239
`Jerzy Wechta, Martin Fricker, Fred Halsall
`
`Work Conserving vs. Non-workconserving Packet Scheduling: An Issue Revisited .............:cecceseeseseseeseees 248
`Jorg Liebeherr, Erhan Yilmaz
`
`Drop Behaviour of RED for Bursty and Smooth Traffic... ceesesesceesecneeseeeecesesaeeeeeeseesteseeatesecssessessenses 257
`Thomas Bonald, Martin May
`
`Reasons Notto Deploy RED ...........ceceecessesesssesessesesesseseecesecssesessesaeessessseseensesaeeeneesesaesaeeesesessscnesseesersersenes 260
`Martin May, Jean Bolot, Christophe Diot, Bryan Lyles
`
`Author Tnen os 05 cea cic hoa dase Ges tha wha Ses ask nda raGie Geo igoamsancanensonsens aeaoasansuaneannmemtentacemnersens Follows page 262
`
`vii
`
`Cloudflare - Exhibit 1019, pagevii
`
`Cloudflare - Exhibit 1019, page vii
`
`
`
`Supporting Differentiated Services in MPLS Networks
`
`Ilias Andrikopoulos and George Pavlou
`
`Centre for Communication Systems Research (CCSR)
`University of Surrey
`Guildford, Surrey, GU2 5XH, UK
`Email: {I.Andrikopoulos, G.Pavlou}@ee.surrey.ac.uk
`
`0-7803-5671-3/99/$10.00 © 1999 IEEE
`
`207
`
`Cloudflare - Exhibit 1019, page 207
`
`
`
`
`
`
`swapping paradigm with network-layer routing. Label-
`Abstract: Multi-Protocol Label Switching is a relatively
`swapping is performed by associating labels with routes
`new technology based on the association of labels with
`and using the label value to forward packets at Layer 2 of
`routes and the use of labels to forward packets. In other
`the OSI Reference Model (RM), including the procedure
`words MPLS integrates the label-swapping paradigm with
`of determining the value of any replacement label. All IP
`network-layer routing. Differentiated Services define a
`routing functionality remains as is, but the forwarding is
`model for implementing scalable differentiation of QoS in
`now performed at the ATM layer by meansof switching.
`the Internet. Packets are classified and marked, policed
`The complex ATM signalling protocols are not required
`and shapedat the edge of the network in order to receive a
`and, more specifically, all the ATM protocols above the
`particular per-hop forwarding behaviour on nodes along
`ATMAdaptation Layer (AAL) are completely removed.
`their path. Per-flow state does not need to be maintained in
`the interior network nodes,
`thus leading to increased
`Although still in the “draft” process within the MPLS
`scalability. This obviates the use of complex signalling
`Working Groupin the IETF,a great deal of research work
`protocols like RSVP. The inherent characteristics of
`has been done andseveral proposals have been submitted.
`MPLS make it a very good candidate for providing
`Moreover, a current European ACTSprojectcalled IthACI
`Differentiated Services. In this paper we describe various
`(Internet and the ATM: Experiments and Enhancements
`approaches which can be used to support differentiated
`for Convergence and /ntegration), aims to provide a
`services in MPLS environments.
`number of important enhancements to MPLS: multicast,
`QoSprovisioning, IP mobility and resource management —
`Keywords: Differentiated Services, Multi-Protocol Label
`features which will make MPLSaviable technology.It is
`Switching (MPLS), Asynchronous Transfer Mode (ATM),
`in the context of this project the research work described
`Internet Protocol (IP), Quality of Service (QoS).
`in this paper has been undertaken.
`Differentiated Services define a model for implementing
`scalable differentiation in the
`Internet. Packets
`are
`classified and marked, policed and shaped at the edge of
`the network in order to receive a particular per-hop
`forwarding behaviour on nodes along their path. Per-flow
`state does not need to be maintained in the interior
`network nodes, whichleads to increased scalability.
`By closely examining the various characteristics of
`MPLS,one can see that it is a very good candidate for
`providing differentiated services. Traffic classification, its
`ability to reserve Class of Service (CoS)
`through its
`lightweight signalling protocol LDP (Label Distribution
`Protocol) and the label aggregation feature are someofits
`useful properties.
`This paper attempts to show how Differentiated Services
`can be supported in MPLS networks. Section 2 briefly
`
`1. Introduction
`
`Over the last years a lot of research has been carried out
`and various standards have been ratified from IETF and
`ATM Forum addressing the integration of IP and ATM.
`Exampleproposed solutions are Classical IP over ATM,
`Multi-Protocol over ATM (MPOA), LAN Emulation
`(LANE) and Next Hop Resolution Protocol
`(NHRP).
`Additionally, various complex signalling protocols, such
`as P-NNI, have been developed so that ATM networks can
`be deployed in the widearea.
`MPLShasbeenrecently introduced as a new approach
`for integrating IP with ATM [1]. Also known as IP
`switching, IP over ATM,or Layer 3 Switching,it tries to
`provide the best of both IP and ATM worlds:
`the
`efficiency and simplicity of IP routing together with the
`high-speed switching of ATM by integrating the label-
`
`Cloudflare - Exhibit 1019, page 207
`
`
`
`modeland its basic architecture as defined in the current
`Internet Drafts. Section 3 gives a short introduction to the
`MPLS
`architecture
`and
`lists
`some
`of
`its main
`characteristics.
`In section 4, various approaches
`for
`supporting Differentiated Services in MPLS networksare
`described and a solution is proposed and elaborated. An
`example is also used to explain analytically the proposed
`architecture. Finally, our conclusions and a summary are
`presented in section 5.
`
`2. Differentiated Services
`
` presents the main features of the Differentiated Services
`
`208
`Cloudflare - Exhibit 1019, page 208
`
`
`service parameters for each service level. These service
`parameters include service performance parameters (e.g.
`throughput, latency, drop probability) and traffic profiles
`corresponding to the requested service. Furthermore, the
`TCS maydefine the marking and shaping functions to be
`provided.
`
`2.1 Fundamental Functional Elements of the
`Differentiated Services Architecture
`
`Traffic Conditioners
`
`form the most vital part of a
`Traffic conditioners
`differentiated services network. Their goal
`is to apply
`conditioning functions on the previously classified packets
`according to a predefined TCS. A traffic conditioner
`consists of one or more of the following components:
`
`¢ Meter
`
`A device which measures the temporal properties of a
`traffic stream selected bya classifier.
`¢ Marker
`
`A device that sets the DS Codepoint in a packet based
`on well defined rules.
`
`The Differentiated Services architecture is composed of a
`numberof functional elements, namely packetclassifiers,
`traffic conditioners and per-hop forwarding behaviours
`(PHB) [4]. According to the basic differentiated services
`IETF
`as proposed by the
`services,
`Differentiated
`Differentiated Services Working Group,allow IP traffic to
`architecture definition, these elements are normally placed
`in ingress and egress boundary nodes of a differentiated
`be classified into a finite number of service classes that
`receive different router treatment. For example,
`traffic
`services domain and in interior DS-compliant nodes.
`belonging to a higher priority and/or delay service class
`However, it is not necessary for all the elements to be
`receives some form of preferential treatment over traffic
`present
`in all
`the DS-compliant nodes, something that
`strictly depends on the functionality that is required at
`classified into a
`lower
`service class. Differentiated
`services do not attempt
`to give explicit end-to-end
`each node [5].
`In the following paragraphs a short
`description for each of the elements is given and the
`guarantees.Instead, in congested network elements,traffic
`with a higher class of priority has a higher probability of
`various components
`that comprise them are briefly
`getting through, or in case of delay priority, is scheduled
`presented.
`for transmission before traffic that is less delay-sensitive
`Packet Classifiers
`[2].
`Packet classification is a significant function which is
`perform actual
`to
`required
`information
`The
`normally required at the edge of the differentiated services
`differentiation in the network elements is carried in the
`network.Its goal is to provide identification of the packets
`Type of Service (TOS)field of the IPv4 packet headers or
`
`belonging stream that may_receiveto a traffic
`
`
`
`the Traffic Class field of the IPv6 packet headers, referred
`differentiated services. Classification is done with packet
`-to as the DS Field or Codepoint (DSCP) [3]. Thus, since
`classifiers, which select packets based on the content of
`the information required by the buffer management and
`packet headers according to well-defined rules determined
`scheduling mechanisms is carried within the packet,
`by the Traffic Conditioning Agreement.
`differentiated services do not require signalling protocols
`the
`Two types of classifiers are currently defined:
`to control the mechanismsthat are used to select different
`Behaviour Aggregate
`(BA)
`classifier, which selects
`treatment for the individual packets. Consequently,
`the
`packets based on the DS Codepoint only, and the Multi-
`amount of state information, which is required to be
`Field (MF)classifier, which performs the selection based
`maintained per node,
`is proportional
`to the number of
`on the combination of one or more headerfields.
`service classes and not proportional
`to the number of
`application flows.
`At each differentiated services user/provider boundary,
`the service provided is defined by means of a Service
`Level Agreement
`(SLA). The SLA is
`a
`contract,
`established either statically or dynamically, that specifies
`the overall performance and features which can be
`expected by a customer. Because differentiated services
`are for unidirectional traffic only, each direction must be
`considered separately. The subset of the SLA which
`provides the technical specification of the service is
`referred to as the Service Level Specification (SLS).
`A profound
`subset of
`the SLS is
`the Traffic
`Conditioning Specification (TCS) which specifies detailed
`
`Cloudflare - Exhibit 1019, page 208
`
`
`
`
`
`is not
`packets a probability of timely forwarding that
`lower than that given to packets marked with a Class
`Selector codepoint of lower relative order,
`i.e. smaller
`numerical value, under reasonable operating conditions
`and traffic loads [3].
`Currently there are three proposed PHBs which are
`briefly described below.
`The Default
`(DE) PHB is the common, best-effort
`forwarding available in today’s Internet. IP packets marked
`for this service are sent into a network without adhering to
`any particular rules and the network will deliver as many
`of these packets as possible and as soon as possible but
`without any guarantees.
`The Expedited Forwarding (EF) PHBisa high priority
`behaviourtypically used for network control traffic such
`as routing updates. The EF PHBis defined as a forwarding
`treatment for a particular differentiated services aggregate
`where the departure rate of the aggregate’s packets from
`any DS-compliant node must
`equal or
`exceed a
`configurable rate. The EFtraffic should beallocated this
`rate independently of the intensity of any other traffic
`attemptingto transit the node[6].
`Finally, the Assured Forwarding (AF) PHB is a means
`for a provider differentiated services domain to offer
`different levels of forwarding assurances for IP packets
`received from a customerdifferentiated services domain.
`Four AF classes are defined, where each AF class in each
`differentiated services nodeis allocated a certain amount
`of forwarding resources,e.g. buffer space and bandwidth.
`Within each AF class, IP packets are marked with one of
`three possible drop precedence values.
`In case of
`congestion, the drop precedence of a packet determines
`the relative importance of the packet within the AF class
`[7].
`According to the basic architecture assumptions, traffic
`classifiers and conditioners can be located within DS-
`compliant nodesat the ingress and egress boundary of a
`differentiated services domain, although they can also be
`found in nodes within the interior of a differentiated
`services domain, or within a non-DS-compliant domain
`since this is not precluded. However, the exact location of
`the various components mainly depends on policy and
`managementissues as specified by the network provider.
`Typically, end-users/customers will mark their packets
`to indicate the service they would like to receive. Then,
`the user traffic entering a differentiated services domain
`will be conditioned at the ingress node according to the
`predetermined SLS. Moreover, packets going from one
`domain to another may need to be re-marked, according to
`the SLS established between the adjacent domains.
`
`209
`
`Cloudflare - Exhibit 1019, page 209
`
`e Shaper
`A device that delays packets within a traffic stream to
`cause the stream to conform to some defined traffic
`profile.
`¢ Dropper/Policer
`A device that discards packets based on specified rules
`(e.g. when the traffic stream does not conform to its
`TCS).
`
`the
`of
`arrangement
`A typical
`componentsis illustrated in Figure 1.
`
`above mentioned
`
`Packets
`
`|
`Incoming
`a cu
`
`
`
`
`
`
`
`
`
`
`Outgoing
`Packets
`
`=< Shaper/
`Dropper
`
`Traffic
`Conditioner
`
`Figure 1 Typical arrangement of a Packet Classifier and a
`Traffic Conditioner[4].
`
`Per-Hop Forwarding Behaviours (PHB)
`A PHBis a description of the externally observable
`forwarding behaviour of a differentiated services node,
`applied to a collection of packets with the same DS
`Codepoint that are crossing a link in a particular direction
`(called differentiated services behaviour aggregate). Each
`service class is associated with a PHB. PHBsare defined
`in terms of behaviour characteristics relevant to service
`provisioning policies, and not
`in terms of particular
`implementations. PHBs may also be specified in terms of
`their resource priority relative to other PHBs,or in terms
`of their relative observable traffic characteristics. These
`PHBs are normally specified as group PHBs and are
`implemented by means of buffer management and packet
`scheduling mechanisms.
`To preserve partial backwards compatibility with known
`current uses of the IP Precedence field without sacrificing
`future flexibility, minimum requirements on a set of PHBs
`that are compatible with mostof the deployed forwarding
`treatments selected by the IP Precedence field have been
`defined.
`In this context,
`the set of codepoints that are
`mapped to PHBs meeting these minimum requirements are
`known as Class Selector Codepoints. The minimum
`requirements for PHBs that these codepoints may map to
`are called the Class Selector PHB Requirements. PHBs
`selected by a Class Selector Codepoint should give
`
`Cloudflare - Exhibit 1019, page 209
`
`
`
`
`
`3. Multi-Protocol Label Switching
`
`MPLS is a technology that integrates the label-swapping
`paradigm with network-layer routing. Although the main
`focus of MPLS is IP-over-ATM networks,
`it
`is not
`restricted to these technologies. Its goal is to be multi-
`protocol at both Layer 2 (e.g. ATM, Frame Relay) and
`Layer3 (e.g. IP, IPX) of the OSI RM.
`__link-level
`use
`Label
`Switching Routers
`(LSRs)
`forwarding to provide a simple and fast packet-forwarding
`capability. Label swapping is accomplished by associating
`fixed-length labels with routes and using the label value to
`forward packets, including the procedure of determining
`the value of any replacement
`label. Depending on the
`Layer 2 and Layer 3 technologies involved, different label
`encoding schemescanbe used [8]. Theseare illustrated in
`Figure 2.
`
`
`
` shim
`
`header
`
`20
`
`3
`
`1
`
`8
`
`e.g. ATM
`
`Label / L2 Header
`
`Label: Label Value
`Exp: Experimental Use
`
`S: Bottom of Stack
`TTL: Time to Live
`
`Figure 2 Three different label encoding schemes.
`
`Whenunlabelled packets need to traverse the same path
`between an ingress and an egress LSR (packets from an
`aggregate of one or more flows are said to belong to a
`stream) belonging to the same MPLS domain, a Label
`Switched Path (LSP) — a LSPis similar to a unidirectional
`ATM Virtual Circuit (VC) — needs to be set-up. This will
`allow the packets to be forwarded from one MPLS node to
`another just by using the assigned label as an index to a
`forwarding table. The LSP set-up can betraffic, request,
`or topology-driven [1]. In the traffic-driven scheme the
`label assignmentis triggered by the arrival of data at an
`LSR, whereas with the request-driven schemethe labelis
`assigned in response to normal processing of request
`based control
`traffic.
`In the case of a topology-driven
`scheme the labels are pre-assigned according to existing
`routing protocol information.
`
`The packetsarefirst classified at the ingress node. Then
`a mapping between IP packets and a LSP, musttakeplace.
`This is done by providing a Forwarding Equivalence Class
`(FEC)specification for each LSP. A FECis specified as a
`set of one or more FEC elements, where each FEC
`element
`identifies a set of IP packets which may be
`mappedto the corresponding LSP. Currently, two types of
`FEC elements exist: the IP address prefix and the host
`address. In the former, the IP address is said to match the
`IP address prefix if and only if this address begins with
`this prefix. In the latter, there must be an exact match
`between the two addresses.
`In the MPLS domain, in order for a LSP to beset-up,
`labels must be negotiated, distributed, and their semantics
`defined through a protocol, namely the Label Distribution
`Protocol (LDP)[9]. LDP is the signalling protocol through
`which one LSR informs its peers of the label/FEC
`bindings it has made. An LSR may use a discovery
`mechanism to discover potential LDP peers. This is done
`by sending Hello Messages on the MPLS-interface using
`UDP/IP (User Datagram Protocol
`/ Internet Protocol).
`Moreover, LDP sessions between LSR peers
`are
`established on top of TCP/IP (Transmission Control
`Protocol / Internet Protocol) -based reliable connections.
`LDP messages are exchanged through LDP Protocol Data
`Units (PDUs). Each LDP PDUcancarry at least one LDP
`message.It consists of an LDP header which is followed
`by one or more LDP messages.The information carried by
`LDP messages is encoded by using the TLV (Type-
`Length-Value) scheme. LDP messagesare classified under
`four main categories: discovery, session, advertisement
`and notification messages.
`As the labelled packets are transmitted downstream
`along the LSP, each LSR examinesthe label and forwards
`the packets downstream to the next hop accordingtoits
`locally significant Next Hop Label Forwarding Entry.
`
`MPLS
`
`Figure 3 A Multi-Protocol Label Switching network connected
`to two stub networks on either edge comprising two ingress, two
`core and two egress Label Switching Routers.
`
`210
`Cloudflare - Exhibit 1019, page 210
`
`Cloudflare - Exhibit 1019, page 210
`
`
`
`According to Rosen et al., three conceptual information
`bases are needed to hold MPLS-related information [10]:
`
`¢ Next Hop Label Forwarding Entry (NHLFE). The
`NHLFEis used when forwarding a labelled packet. It
`contains the outgoing interface (next hop), the data
`link encapsulation used for the transmitted packets,
`the outgoing label and the operation (add, replace, or
`remove) to perform onthe label stack.
`Incoming Label Map (ILM). The ILM is a mapping
`from incoming labels to NHLFEs.
`It
`is used when
`forwarding packets that arrive as labelled packets.
`FEC-to-NHLFE Map (FIN). The FTN is a mapping
`from FECs to NHLFEs. It is used when forwarding
`packets that arrive unlabeled, but which are to be
`labelled before forwarding.
`
`¢
`
`¢
`
`In the next section we will be dealing with possible ways
`for providing support of differentiated services in MPLS
`networks. These will be further clarified by using an
`example to describe the operation of
`the proposed
`architecture.
`
`4. Differentiated Services and MPLS
`
`Asit has already been mentioned in section 2, in order to
`support differentiated services in a network environment,
`three fundamental functional elements must be present:
`packet
`classifiers,
`traffic
`conditioners
`and
`_per-hop
`behaviours. We have already discussed how and where
`these elements should be placed in order for the network
`to be capable of providing differentiated services. The
`question that arises is how these components will be
`efficiently utilised in
`an MPLS network so_
`that
`differentiated services are supported.
`in MPLS
`The
`support of differentiated services
`environments requires either signalling support for the
`association of the desired category with the label, or each
`packet belonging to a
`stream needs
`to carry the
`information of the desired service category (behaviour
`aggregate).
`In this paper we deal with ATM LSRsand hence the
`packets of a labelled IP stream are actually transported by
`ATM cells. This poses the question of whether certain
`peculiarities of ATM should be taken into account or
`whether a generic approach, independentof the link layer
`technology, should be followed.If it had not been ATM at
`Layer 2, it would be possible to include a “shim” header in
`the packets as mentioned earlier in this paper. However,
`with ATM,a “shim” header cannot be used becausethis
`would involve doing segmentation and re-assembly at
`
`each ATM-LSRin order to read the DSCP field which is
`against
`the ATM switching “philosophy”. Hence,
`the
`DSCP in the IP header is not accessible by the ATM
`hardware responsible for the forwarding. Therefore, two
`alternative solutions may be considered. Either to have
`somepart of the ATM cell header mapped to the DSCP,or
`to use LDP.
`In the first approach, the most likely solution is to use
`the VPI (Virtual Path Identifier) and part of the VCI
`(Virtual Channel Identifier) of the ATM cell header as the
`label, and the remaining eight least significant bits of the
`VCI be used to map the DSCP [11]. Then all that
`is
`needed is the existence of a functional component in the
`interior DS-compliant ATM LSRs
`to perform the
`appropriate traffic management mechanisms onthecells
`by interpreting the DSCP correctly, with respect to the
`PHB.
`In the second approach, which is more likely for future
`deployment, the DSCP is mapped to an LSPat the ingress
`of the MPLS domain. This means that for each DSCP
`value/PHB a separate LSP will be established for the same
`egress LSR.So,if there are n Classes and m egress LSRs,
`n-m LSPsneed to beset-up, 1 labels for each of the m
`FECs. The packets belonging to streams with the same
`DSCP and FEC will be forwarded on the same LSP. In
`other words,
`the label
`is regarded as
`the behaviour
`aggregate selector.
`Furthermore, two LSPsare allowed to be merged into
`one LSPonlyif the packets they carry belong to the same
`Behaviour Aggregate or, even better, if they have the same
`DSCP. The decision for the merge will be taken at the
`merging LSR based upon the DSCP entry it has in its
`modified NHLFEtable. Given that the two DSCP values
`are identical and provided that the necessary resources are
`available for the rest of the common LSP, the two LSPs
`can be merged. To check whether there are available
`resourcesornotis the role of an admission control module
`resident in each LSR. A request message needsto besent
`to all
`following hops
`to check for
`the necessary
`bandwidth. If this can be eventually granted,
`then the
`merging process may proceed.
`Additionally, there must be an MPLS-to-ATM mapping
`element in every MPLS DS-compliant node which will
`perform the mapping between the Behaviour Aggregate
`and the ATMtraffic class and traffic parameters.
`An issue that would need more discussion is what
`happens when the MPLS network is topology-driven.
`Should there be n-m already established LSPs thus
`forming a kind of overlay network on top of the physical
`network, or shou