|_|
`
`
`
`
`
`
`
`Splunk Inc. Exhibit 1019 Page 1
`
`

`

`
`
`1999 Seventh
`International Workshop
`on Quality of Service
`
`=
`IWQoS ’99
`
`London, England
`May31 — 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
`
`Splunk Inc.
`
`Exhibit1019
`
`Page 2
`
`Splunk Inc. Exhibit 1019 Page 2
`
`

`

`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 those articles in this volume that carry a
`code at the bottom ofthe first page, provided the per-copy fee indicated in the code is 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-567 1-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
`
`"Kurt K. Wendt Library”
`University of Wisconsin-Madisog
`45 N. Randal! Avenue
`Madison, W! 53706-1688:
`
`Splunk Inc.
`
`Exhibit 1019
`
`Page3
`
`Splunk Inc. Exhibit 1019 Page 3
`
`

`

`IWQos 799 Table of Contents
`
`Session 1 - Admission Control and Related RINaccaaaivainerssi ureaniacp maniecci—2. 1
`Measurement-Based Admission Control: Whatis the Research PRBOMGA csscaeiavhasGAOcs ecacnSerantennevenronranerar
`Lee Breslau, Sugih Jamin, Scott Shenker
`
`Tie TREY PASTOR16 OOS atnccseucesrasennvinsnscisicnete ispertbssseshansonns eb beawaivtndbiecbiaSteeee.---..... 6
`Gunnar Karlsson and Fredrik Orava
`
`IP over Photons: How notto waste the waist of the FAGUNDLB8Sc csvyesscvviston netacsesenanpeseiecctiore co 9
`Jon Crowcroft
`
`Utility Curves: Mean Opinion Scores Considered BASEsaeses araemvsecesessasarcignapeeceronareencnuaieiseneenneeesanceeTD
`Hendrik Knoche, Herman De Meer, David Kirsh
`
`Session 2 ~ Distributed QoS Architecture .....0........cccccsecesssssesssssecsescssseeeeSits basaha pneehaaneens SENN RE NRSC 15
`Performance of QoS Agents for Provisioning Network Resources ..........ccs:ssssssscssssassesssssssssvassvereesessesseeecses.., 17
`Olov Schelén , Andreas Nilsson, Joakim Norrgard, Stephen Pink
`
`A Distributed Resource ManagementArchitecture that Supports Advance
`Reservations and Co-AlOcation ...ssssserseseseesmuanunasssessesessereeescanmnsesssecesessssnsusasevscassesssasescsssesssesesrescsssneeesneesssss2T
`Ian Foster, Carl Kesselman, Craig Lee, Bob Lindell, Klara Nahrstedt, Alain Roy
`OptimalState Prediction for Feedback-Based QoS ADapHOns._...rs essen ncercssnnnzaseonsorssssieennsivaiavesvanciabsxtvaisedureea ved:37
`Baochun Li, Dongyan Xu, Klara Nahrstedt
`
`Session 3 - Software Structures and QoS................... sonecatetenanecrtnhenrannencateaeanedien{enpaxinuanaenscedinineadiiesatieduinn vevevacecdttevsbien47
`The Role of Reflection in Supporting Dynamic QoS Management Functions ...0..0.0.0.....cccecccseccssesssessecesseesseeees 49
`Gordon Blair , Anders Anderson, Lynne Blair, Geoff Coulson
`
`A Software Framework for Application Level QoS Management ...........scccccesessssssessssssessevsssessresseseseeseseussessseces 52
`Varuni Witana, Michael Fry and Mark Antoniades
`
`Securing QoS:Threats to RSVP Messagesand Their Countermeasures........sssses:esscsssssssossssesteieeeeeeceocceeccce62
`Tsung-Li Wu,S. Felix Wu, Zhi Fu, He Huang, Fengmin Gong
`
`Virtuosity: Performing Virtual Network Resource Management 223.sisssssisessceesecsueeynesrenesensnsetnteneesiveaxesstemavonrnccc05
`Andrew T. Campbell, John Vicente, Daniel A. Villela
`
`SeatG— eRntsacaagscynnacpsiosninic acreSioseoaese seppeaeorcaseysserreesesr&ecececemesece,17
`OnService Guarantees for Input Buffered Crossbar Switches:
`A Capacity Decomposition Approach by Birkoff and von Neumann.oscssscscessecsssssosssssosesssssstecseeeeeecseeeccccee 79
`Cheng-Shang Chang, Wen-Jyh Chen and Hsiang-Yi Huang
`
`QOS Enhancement with Partial State.........cssssssesssnsssssesessssueseesnsuussssstesssssssussssssvaevessteuieeeeeesseeeee 87-
`Deying Tong, A. L. Narasimha Reddy
`
`Evaluation of Differentiated Services using an Implementation under Linux v.cccsese----secccsosseceeceeeeeeccccccccec.. 97
`Roland Bless, Klaus Wehrle
`
`Splunk Inc.
`
`Exhibit1019
`
`Page 4
`
`Splunk Inc. Exhibit 1019 Page 4
`
`

`

`
`
`Session 5 — Routing & Forwarding ..............cccsccssssssssscsscsssescssscsssesesenssssessnscscsescssecseasssnseesensessassrasseesasaeasaceratsneees 107
`
`Efficient Multi-field Packet Classification for QOS Purposes.........ssssccescsesesssessessescessnesesensessssessesseeeasaeearateas 109
`Niklas Borg, Emil Svanberg and Olov Schelén
`
`Quality-of-Service Routing using Maximally Disjoint Paths ..............:ccssscssssssssssssscecessecesesecesesseeessneesseessrasens 119
`Nina Taft-Plotkin, Bhargav Bellur and Richard Ogier
`
`Quality-of-Service Routing without Global Information Exchange..........:.cccssessssesssssesseessesscesessnecsnesessesesaess 129
`Srihari Nelakuditi, Rose P Tsang, and Zhi-Li Zhang.
`
`A:Proposal for an‘ Asymmetric Best-Bifort Service. 2.2. coo 2ccc.cicscccccctec ce siseaten st ccsat enc sveuattac vate tecnnsuadgugdvavalovebs 132
`Paul Hurley, Jean-Yves Le Boudec
`
`Session 6 — (panel/discussion)
`
`Panel: What Service Differentiation Do Users Really Want?
`
`Session 7:—:Agaregations. scszissscsescessvesvertovccascoassosanssop sinarstcvasaanancessaasasipsanisnincestisaxniavestcasiadis auaaianssecasimsasciseiensiettes 135
`
`Source-oriented Topology Aggregation with Multiple QoS Parameters
`in: Hierarchical ATM: Netwotks scesissssussessssesvenssensianconsvacssavecanavaoussesnesnepcasenssnastasesssnesnsnnisascivagunnecqevsbversainenscactss 137
`Turgay Korkmaz and Marwan Krunz
`
`Aggregation of Guaranteed Service FOWS's....sersresssesorsessoyecrsssessenonsvnsiestcanenovesssvosensy enn uth tan catsvessnesmsessnatasienssestes 147
`Jens Schmitt, Martin Karsten, Lars Wolf, Ralf Steinmetz
`
`Impact of Marking Strategy on Aggregated Flows ina
`Differentiated Services Network,
`.....csaacses-sooxereoseresarssssovqnessecsovsersnvasonasarserheshesstersnanas ote suse csnenpviennsnanssasbanisensss 156
`Ikjun Yeom, A. L. Narasimha Reddy
`
`Paris Metro Pricing: The Minimalist Differentiated Services Solution ..............c.ccccesccseescseeesescesesceseecereasceeeees 159
`Andrew Odlyzko
`
`Session 8 — Pricing ...............cssccsssssescessesssscsssesesscscsssesssosssesssssncssessssnssseasosaseasaassonssseasecsecssonsiseessessscseeseasereeserssesnssess 163
`
`Managing and Pricing Service Level Agreements for Differentiated Services............:.ccccssseseesesssessesseeteeeess 165
`Costas Courcoubetis and Vasilios A. Siris
`
`Provider-Oriented Linear Price Calculation for Integrated Services .........:ccccescecessseeeseseeseeseeeesseeecsesesseceeeeens 174
`Martin Karsten, Jens Schmitt, Lars Wolf, Ralf Steinmetz
`
`MarketPricing of Differential Internet Services........ccssssccssceesesecssneccsessssesessesssneesseseeseesanesestaesisseeseaesenseeceass 184
`Nemo Semret, Raymond R.F. Liao, Andrew T. Campbell, Aurel A. Lazar
`
`Sesakon 9 MPUss cscsicscscauscscsuascesasdavansuesssooasecouas teunase op susoucsacaiunbes avons v Sassi wan vos sous ves GNUEET ae UANou Wis axadnCE Sau SAN MNIT AL Svoaaae 195
`
`Resource: Allocation in: Multiservice: MPISS «65023505 csse8 acess sok snpsstcsecetccassncsoduguas susesuusicesssseaveudawvbaivessbunssessauaivects 197
`MagdaChatzaki, Stelios Sartzetakis, Nikos Papadakis, Costas Courcoubetis
`
`Supporting Differentiated Services in MPLS Networks............ccccccssscessecssseesescesnscsssecessccasecesnscacscsesevscsvecareeens 207
`Ilias Andrikopoulos, George Pavlou
`
`Web Server QoS Managementby Adaptive Content Delivery.............ccccccscsesessesetesseseseeseseeeecseasessecsssceusesess 216
`Tarek F. Abdelzaher, Nina Bhatti
`
`vi
`
`Splunk Inc.
`
`Exhibit1019
`
`Page 5
`
`Splunk Inc. Exhibit 1019 Page 5
`
`

`

`Session Based Admission Control:
`A Mechanism for Improving Performance of Commercial Web Sites ...........:ccsccssescesesseseescseesseeesessceesatseesciee 226
`Ludmila Cherkasova and Peter Phaal
`
`Session 10 — Flow Control & Adaptation & RED .u00.........cccccsssssesssecesessesteessecssnessetesscaeesessscassesnecesseseeeaeees 237
`
`Hop-by-hop Flow Control as a Method to Improve QoS in 802.3 LANS.........:ccsccsesseseseseeeeseseessseseneeseesnsaenanee 239
`Jerzy Wechta, Martin Fricker, Fred Halsall
`
`Work Conserving vs. Non-workconserving Packet Scheduling: An Issue Revisited ............cccsesssseesseseceeenees 248
`Jorg Liebeherr, Erhan Yilmaz
`
`Drop Behaviour of RED for Bursty and Smooth Traffic........scccssssesssersesseessenscssescesesseetecseseseerseesneesansessnseeees 257
`Thomas Bonald, Martin May
`
`Reasons Not to Deploy RED ................cccccccccesseceseeeceeeecsersssecseneecseeesseaacessacaecscsaseeeaecaceacaceacsaseseasracscesenteseseenees 260
`Martin May, Jean Bolot, Christophe Diot, Bryan Lyles
`
`AWCMION Fineness oF ans tbeseioasennanesbantcechsosshantunnatinsnanenaimacsnncaeees saul aabunonaspssessansonennonssonensonanonmsucsasenreopsoseved Follows page 262
`
`vil
`
`Splunk Inc.
`
`Exhibit1019
`
`Page6é
`
`Splunk Inc. Exhibit 1019 Page 6
`
`

`

`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
`
`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 means of switching.
`the Internet. Packets are classified and marked, policed
`The complex ATMsignalling protocols are not required
`and shaped at 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
`ATM Adaptation 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 Group in the IETF, a great deal of research work
`protocols like RSVP. The inherent characteristics of
`has been done and several proposals have been submitted.
`MPLS make it a very good candidate for providing
`Moreover, a current European ACTSproject called 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 Jntegration), aims to provide a
`services in MPLS environments.
`number of important enhancements to MPLS: multicast,
`QoS provisioning, 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 nodesalong their path. Per-flow
`state does not need to be maintained in the interior
`network nodes, which leads 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
`
`Overthe last years a lot of research has been carried out
`and various standards have beenratified from IETF and
`ATM Forum addressing the integration of IP and ATM.
`Example proposed 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 wide area.
`MPLS has beenrecently 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-
`
`1, Introduction
`
`0-7803-5671-3/99/$10.00 © 1999 IEEE
`
`207
`
`Splunk Inc.
`
`Exhibit1019
`
`Page 7
`
`Splunk Inc. Exhibit 1019 Page 7
`
`

`

`2. Differentiated Services
`
`model and 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 networks are
`described and a solution is proposed and elaborated. An
`exampleis also used to explain analytically the proposed
`architecture. Finally, our conclusions and a summary are
`presented in section S.
`
` presents the main features of the Differentiated Services
`
`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
`the
`as proposed by
`services,
`Differentiated
`architecture definition, these elements are normally placed
`Differentiated Services Working Group, allow IP traffic to
`be classified into a finite number of service classes that
`in ingress and egress boundary nodes of a differentiated
`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 ofpreferential treatment over traffic
`present
`in all
`the DS-compliant nodes, something that
`classified into a lower
`service class. Differentiated
`strictly depends on the functionality that
`is required at
`services do not attempt
`to give explicit end-to-end
`each node [5].
`In the following paragraphs a short
`guarantees. Instead, in congested network elements,traffic
`description for each of the elements is given and the
`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
`PacketClassifiers
`[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 mechanismsthatare usedto 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
`
`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 by a classifier.
`¢ Marker
`
`A device that sets the DS Codepoint in a packet based
`on well defined rules.
`
`208
`
`Splunk Inc.
`
`Exhibit1019
`
`Page 8
`
`Splunk Inc. Exhibit 1019 Page 8
`
`

`

`¢ 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 thetraffic stream does not conform to its
`TCS).
`
`the
`of
`arrangement
`A typical
`componentsis illustrated in Figure 1.
`
`above
`
`mentioned
`
`
`
`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 crossinga link in a particular direction
`(called differentiated services behaviour aggregate). Each
`service class is associated with a PHB. PHBs are 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 managementand packet
`scheduling mechanisms.
`To preserve partial backwards compatibility with known
`current uses of the IP Precedencefield without sacrificing
`future flexibility, minimum requirements on a set of PHBs
`that are compatible with most of 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 requirementsare
`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
`
`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, ic. smaller
`numerical value, under reasonable operating conditions
`andtraffic 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
`anyparticular 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) PHB is a high priority
`behaviour typically used for network control traffic such
`as routing updates. The EF PHB is defined as a forwarding
`treatmentfor 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 be allocated this
`rate independently of the intensity of any other traffic
`attempting to 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 node is 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 nodes at 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
`managementissuesas 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 mayneedto be re-marked, according to
`the SLS established between the adjacent domains.
`
`209
`
`Splunk Inc.
`
`Exhibit1019
`
`Page 9
`
`Splunk Inc. Exhibit 1019 Page 9
`
`

`

`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 schemescan be used [8]. These are illustrated in
`Figure 2.
`
`
`
` 3. Multi-Protocol Label Switching
`
`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) — needsto be set-up. This will
`allow the packets to be forwarded from one MPLS nodeto
`another just by using the assigned label as an index to a
`forwarding table. The LSP set-up can be traffic, 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 label is
`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 packets are first classified at the ingress node. Then
`a mapping betweenIP 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
`mapped to 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 be set-up,
`labels must be negotiated, distributed, and their semantics
`defined through a protocol, namely the Label Distribution
`Protocol (LDP)[9]. LDPis 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 PDUcan carry at least one LDP
`message. It consists of an LDP header whichis 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 according to its
`locally significant Next Hop Label Forwarding Entry.
`
`
`
`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
`
`Splunk Inc.
`
`Exhibit1019
`
`Page 10
`
`Splunk Inc. Exhibit 1019 Page 10
`
`

`

`According to Rosen et al., three conceptual information
`bases are needed to hold MPLS-related information [10]:
`
`¢
`
`¢ Next Hop Label Forwarding Entry (NHLFE). The
`NHLFE is 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 on the label stack.
`Incoming Label Map (ILM). The ILM is a mapping
`from incoming labels to NHLFEs. It is used when
`forwarding packetsthat arrive as labelled packets.
`FEC-to-NHLFE Map (FTN). 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 ofa 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, independent of 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 because this
`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 ChannelIdentifier) of the ATM cell header asthe
`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 on the cells
`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 LSP atthe ingress
`of the MPLS domain. This means that for each DSCP
`value/PHBa separate LSP will be established for the same
`egress LSR.So,if there are n Classes and m egress LSRs,
`n-:m LSPs need to be set-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 LSPs are allowed to be merged into
`one LSPonly if the packets they carry belong to the same
`Behaviour Aggregateor, 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 NHLFE table. 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
`resourcesor notis the role of an admission control module
`resident in each LSR. A request message needsto be sent
`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 should the LSPs be set-up on demand, which
`conserves resources in case someof the standard service
`
`211
`
`Splunk Inc.
`
`Exhibit1019
`
`Page 11
`
`Splunk Inc. Exhibit 1019 Page 11
`
`

`

`rarely used? Evidently, having all LSPs in place is an
`advantage from the perspective of minimising the LSPset-
`up delay. Another problem that emerges is the level of
`aggregation of “microflows” with the same differentiated
`services behaviour aggregate that can be admitted in such
`a DS-capable MPLS network. Are
`the bandwidth
`reservations per node going