`
`
`
`
`
`
`
`
`
`United States Patent
`(12)
`US 7,225,271 Bl
`(10) Patent No.:
`
`
`
`
`
`
`
`May29, 2007
`(45) Date of Patent:
`DiBiasio et al.
`
`
`
`
`US007225271B1
`
`
`
`
`
`(75)
`
`
`
`
`
`
`
`
`(54) SYSTEM AND METHOD FOR
`
`RECOGNIZING APPLICATION-SPECIFIC
`
`
`
`FLOWS AND ASSIGNING THEM TO
`QUEUES
`
`
`
`
`
`Inventors: Michael V. DiBiasio, Westford, MA
`
`
`
`
`(US); Bruce S. Davie, Belmont, MA
`
`
`
`
`(US); David R. Oran, Acton, MA (US)
`
`
`
`
`
`
`
`(73) Assignee: Cisco Technology, Inc., San Jose, CA
`
`(US)
`
`
`(*) Notice:
`
`
`
`
`
`
`
`
`
`Subject to any disclaimer, the term of this
`
`
`
`
`patent is extended or adjusted under 35
`
`
`
`
`U.S.C. 154(b) by 738 days.
`
`
`
`
`(21) Appl. No.: 09/896,276
`
`
`
`(22)
`
`
`
`Jun. 29, 2001
`
`
`
`Filed:
`
`
`Int. Cl.
`
`
`
`(2006.01)
`GO6F 15/173
`
`
`
`(2006.01)
`GO6F 15/16
`
`
`
`
`
`
`
`(52) U.S. Ch wees 709/240; 709/224; 709/231;
`
`
`709/238; 709/241
`
`
`
`
`
`
`(58) Field of Classification Search........ 709/223-225,
`
`
`
`
`709/231-233, 236, 238-240
`
`
`
`
`
`
`
`See application file for complete search history.
`
`
`References Cited
`U.S. PATENT DOCUMENTS
`
`
`
`(51)
`
`
`
`
`
`(56)
`
`
`
`
`
`
`
`5/1996 Kim we eceeeeeeeeee 370/232
`5,519,689 A *
`
`
`
`
`6/1998 Valizadeh
`5,765,032 A
`
`
`
`
`7/1999 Vin eee ccececeeeeeeeeee 370/230
`5,926,458 A *
`
`
`
`
`12/1999 Colby et al.
`6,006,264 A
`
`
`
`
`3/2000 Hugheset al.
`6,034,945 A
`
`
`
`
`
`7/2000 Marin et al... 709/232
`6,088,734 A *
`
`
`
`
`7/2000 Harrison et al.
`6,091,709 A
`
`
`
`
`7/2000 Cheriton etal.
`6,091,725 A
`
`
`
`
`
`8/2000 Galand et al... 704/500
`6,104,998 A *
`
`
`
`
`
`8/2000 Wilford etal.
`6,111,877 A
`
`
`
`
`
`6,157,955 A * 12/2000 Narad et al... 709/228
`
`
`
`
`6,167,445 A
`12/2000 Gaiet al.
`
`
`
`
`
`
`6,188,698 Bl
`2/2001 Galandetal.
`
`
`
`
`
`6,192,032 B1*
`2/2001 Izquierdo «1.0... 370/230
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`6,243,667 BL
`
`6,286,052 B1*
`
`
`6,292,832 Bl
`6,308,148 Bl
`
`
`
`
`
`6,320,845 Bl
`
`
`
`
`6/2001 Kerr et al.
`
`
`9/2001 McCloghrie et al.
`
`
`
`9/2001. Shah et al.
`10/2001 Bruins etal.
`
`
`
`
`
`11/2001 Davie
`
`
`
`
`
`
`....... 709/238
`
`
`
`
`(Continued)
`
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`
`RSVP Support for Low Latency Queueing, Cisco Systems Incor-
`
`
`
`
`
`
`
`
`
`porated, San Jose, CA, Jul. 24, 2000,pp. 1-18.
`
`
`
`
`(Continued)
`
`
`
`
`Primary Examiner—Ario Etienne
`
`
`
`
`Assistant Examiner—Hussein E]-chanti
`
`
`
`
`
`
`(74) Attorney, Agent, or Firm—Cesari and McKenna LLP
`
`
`
`
`
`
`
`(57)
`
`ABSTRACT
`
`
`
`
`
`
`
`
`
`
`
`Asystem assigns networktraffic flows to appropriate queues
`
`
`
`
`
`
`
`
`and/or queue servicing algorithms based upon one or more
`
`
`
`
`
`
`flow parameters contained in reservation requests associated
`
`
`
`
`
`
`
`
`
`with the traffic flows. The system may be disposed at an
`
`
`
`
`
`
`intermediate network device within a computer network.
`The intermediate network device includes a reservation
`
`
`
`
`
`
`
`
`
`
`
`
`engine, a packet classification engine, an admission control
`
`
`
`
`
`
`
`
`entity, a traflic scheduler, and a flow analyzer. The flow
`
`
`
`
`
`
`
`analyzer includes or has access to a memory that is prepro-
`
`
`
`
`
`
`
`
`
`grammed with one or more heuristic sets for use in evalu-
`
`
`
`
`
`
`
`ating the flow parameters of reservation requests. When a
`
`
`
`
`
`
`
`
`reservation request that includes one or more flow param-
`
`
`
`
`
`
`eters
`characterizing the bandwidth and/or
`forwarding
`
`
`
`
`
`
`requirements of the anticipated traffic flow is received, the
`
`
`
`
`
`
`
`
`flow analyzer applies the heuristic sets. Depending on which
`
`
`
`
`
`
`
`
`
`
`set of heuristics, if any, the parameters satisfy, the flow
`
`
`
`
`
`
`
`
`analyzer selects the appropriate queue and/or queue servic-
`
`
`
`
`
`ing algorithm for the flow.
`
`
`
`
`28 Claims, 10 Drawing Sheets
`
`
`
`
`
`
`
`
`
`PACKETS
`
`RECEIVED
`
`FOR
`
`TRANSMISSION
`
`
`
`
`424
`
`
`
`ENGINE
`
`
`
`
`
`CLASSIFICATION
`ENGINE
`
`
`
`
`
`
`
`
`OUTPUT
`
`
`
`516
`
`
`
`
`
`QUEUESELECTOR/SCHEDULER
`
`
`
`
`
` OUTPUT
`
`
`
`Splunk Inc.—Exhibit 1011 Page 1
`
`
`
`
`
`
`INTERFACE
`406b
`
`
`
`
`
`
`DEFAULT
`
`QUEUE
`
`508
`
`Splunk Inc. Exhibit 1011 Page 1
`
`

`

`
`
`
`US 7,225,271 B1
`
`
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`
`
`
`
`
`
`
`
`
`
`
`3/2002 Elwalid et al. «0.0.0.0... 370/443
`6,353,616 BI1*
`
`
`
`
`
`10/2002 Mohaban etal.
`6,463,470 B1
`
`
`
`
`
`10/2002 Navehetal.
`6,466,984 Bl
`
`
`
`
`
`6,640,248 B1* 10/2003 Jorgensen .............06. 709/226
`
`
`
`
`
`
`
`
`6,654,373 B1* 11/2003 Maher,III etal.
`we 370/392
`
`
`
`
`
`6,665,273 Bl
`12/2003 Goguenetal.
`
`
`
`
`
`
`
`6,690,647 B1*
`2/2004 Tang etal. oe 370/235
`
`
`
`
`
`
`
`
`6,738,361 B1*
`5/2004 Immonenetal. .
`wee 370/328
`
`
`
`
`
`
`
`6,744,767 B1*
`6/2004 Chiu et al. ......0.... 370/395.21
`
`
`
`
`
`
`
`6,909,708 B1*
`6/2005 Krishnaswamy et al.
`... 370/352
`
`
`
`
`
`
`
`7,072,336 B2*
`7/2006 Barany etal... 370/389
`OTHER PUBLICATIONS
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`VoIP Call Admission Control Using RSVP, Cisco Systems Incor-
`
`
`
`
`
`
`
`
`porated, San Jose, CA, Aug. 7, 2000, pp. 1-16.
`
`
`
`
`
`
`
`White Paper: DiffServ-The Scalable End-to-End Qos Model, Cisco
`
`
`
`
`
`
`
`
`
`Systems, Incorporated, San Jose, CA, Mar. 1, 2001, pp. 1-16.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Davie, B., Implementing Qos for Packet Telephony, Packet Maga-
`
`
`
`
`
`
`
`
`
`
`zine, Cisco Systems Incorporated, San Jose, CA, Apr. 2000, pp. 1-6.
`
`
`
`
`
`
`Wroclawski, J., Integrated Service Mappings for Differentiated
`
`
`
`
`
`
`
`Services Networks, Internet Engineering Task Force, Internet Draft,
`
`
`
`
`draft-ietf-issll-ds-map-01.txt, http://www.ietforg, Feb. 2001, pp.
`1-19.
`
`
`
`
`
`Wroclawski, J., Specification of the Controlled-Load Network Ele-
`
`
`
`
`
`
`
`
`ment Service, Internet Engineering Task Force, Request for Com-
`
`
`
`
`
`
`
`
`ments (RFC) 2211 http:/www.ietf.org, Sep. 1997, pp. 1-19.
`
`
`
`
`
`
`Bernet, Y., et al., A Framework for Integrated Services Operation
`
`
`
`
`
`
`
`
`over Diffserv Networks, Internet Engineering Task Force, Request
`
`
`
`
`
`
`
`
`for Comments (RFC) 2998, http://www.ietf.org, Nov. 2000, pp.
`1-31.
`
`
`
`
`
`
`
`
`
`Bernet, Y., et al., Application and Sub Application Identity Policy
`
`
`
`
`
`
`
`
`
`Element for Use with RSVP, Internet Engineering Task Force,
`
`
`
`
`
`
`
`
`Request for Comments (RFC) 2872, http://www.ietf.org, Jun. 2000,
`
`
`pp. 1-6.
`
`
`* cited by examiner
`
`
`
`
`
`
`
`
`Splunk Inc.—Exhibit 1011 Page 2
`
`Splunk Inc. Exhibit 1011 Page 2
`
`

`

`
`U.S. Patent
`
`
`
`
`May29, 2007
`
`
`
`
`
`Sheet 1 of 10
`
`
`
`US 7,225,271 Bl
`
`
`
`9S/cSt
`LS30|30YNOS
`LY¥Od|LdOd
`
`
`
`00
`
`90180LvOCOL
`
`
`
`
`
`
`
`(1YVYOIdd)OL‘Ol
`
`TO90LOYdot
`0zi-~cr
`ZLOzhcol
`
`(LYVYOIYd)VL‘OIA“
`
`
`
`(LavYOIMd)gl‘Sls
`
`
`
`Splunk Inc.
`
`Exhibit 1011
`
`Page 3
`
`Splunk Inc. Exhibit 1011 Page 3
`
`
`

`

`
`U.S. Patent
`
`
`
`
`May29, 2007
`
`
`
`
`Sheet 2 of 10
`
`
`
`US 7,225,271 Bl
`
`
`
`MYOMLAN
`
`
`
`
`
`
`GNOTO
`
`00¢
`
`
`
`Splunk Inc.
`
`Exhibit 1011
`
`Page 4
`
`Splunk Inc. Exhibit 1011 Page 4
`
`

`

`
`U.S. Patent
`
`
`
`
`May29, 2007
`
`
`
`
`Sheet 3 of 10
`
`
`
`US 7,225,271 Bl
`
`
`
`COG
`
`
`
`vOOLE
`
`
`
`LN39VASIOA
`
`dASY
`
`ALVLS
`
`dASHY
`
`AOVSSAN
`
`ANIHOVIN
`YOLVYANAD
`
`90€
`
`
`
`ALILNAdASd
`
`ONITIVNOIS
`
`
`
`TWO
`
`ALILNA
`
`
`
`
`
`
`
`
`
`
`
`MYOMLAN
`
`WOus/Ol
`
`00¢
`
`€Ols
`
`
`
`ALIMOV4NOLLWOINANAWOS
`
`Splunk Inc.
`
`Exhibit 1011
`
`Page5
`
`Splunk Inc. Exhibit 1011 Page 5
`
`
`
`
`
`

`

`
`U.S. Patent
`
`
`
`
`May29, 2007
`
`
`
`
`Sheet 4 of 10
`
`
`
`US 7,225,271 Bl
`
`
`
`SOP
`
`
`
`
`
`vev
`
`9er
`
`Ber
`
`002
`
`Oey
`
`CLy
`
`bey
`
`
`
`
`
`YOLVYHANADAOVSSAWdASdY
`
`
`
`
`
`
`
`AWVYs/LAMOVd
`
`ANIDNAANIHOVWALVLSdASHY
`
`
`
`
`
`
`
`ATaVLlNOISSSS
`
`YSATNGAHOSOlasVaL
`
`
`
`
`
`ALILNaTONLNOONOISSINGY
`
`
`
`dAZAIVNYMO14
`
`
`
`AYXOLSOLSIYNAH
`
`Splunk Inc.
`
`Exhibit 1011
`
`Page6
`
`Splunk Inc. Exhibit 1011 Page 6
`
`

`

`U.S. Patent
`
`
`May29, 2007
`
`
`
`Sheet 5 of 10
`
`
`
`US 7,225,271 Bl
`
`
`
`
`
`70Spev
`
`OddASY
`
`ANIDNA
`
`OLS
`
`INdLNO
`
`CLS
`
`OLS
`
`YAINGSHOS / HOLOATAS ANAND
`
`LInv4sd
`
`
`
`NOILLWOISISSVT9HIS
`
`
`
`
`
`ANIONSSLAMOWd
`
`0S
`
`yOd
`
`QSAIS034
`
`
`NOISSINSNVYL
`
`GSOla
`
`
`
`80Sq907
`
`
`
`ANANDLNdLNO
`
`JOVIGALN!
`
`Splunk Inc.
`
`Exhibit 1011
`
`Page 7
`
`Splunk Inc. Exhibit 1011 Page 7
`
`
`
`

`

`
`U.S. Patent
`
`
`
`
`May29, 2007
`
`
`
`
`Sheet 6 of 10
`
`
`
`US 7,225,271 B1
`
`
`
`
`
`
`
` CALL SIGNALING ENTITY DETECTS START
`
`
`
`
`OF CALL
`
`
`
`
`
`
`
`
`
`
`
`RSVP ENGINE GENERATES ONE OR MORE PATH
`
`
`
`
`MESSAGES IN ORDER TO RESERVE NETWORK
`
`
`
`
`RESOURCES FOR THE ANTICIPATED
`
`
`VOICE TRAFFIC
`
`602
`
`
`
`604
`
`
`
`
`
`
`
`
`PATH MESSAGEIS FORWARDED TOWARD DESTINATION/
`
`RECEIVER ENTITY
`
`
`
`606
`
`
`
`
`
`RECEIVED PATH MESSAGE IS PASSED TO INTERMEDIATE
`
`
`
`
`
`NETWORKDEVICE'S RSVP ENGINE FOR PROCESSING
`
`
`
`608
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`NETWORK DEVICE'S RSVP ENGINE FOR PROCESSING
`
`
`
`
`
`
`RSVP ENGINE STORES CONTENTS OF RECEIVED PATH
`
`
`
`
`MESSAGE INCLUDING ADDRESS OF PREVIOUS HOP
`
`
`
`
`
`
`INTERMEDIATE NETWORK DEVICE LOADS ITS ADDRESS
`
`
`
`
`
`
`
`
`INTO THE PATH MESSAGE AND FORWARDS THE PATH
`
`
`
`
`
`| MESSAGE TOWARD THE DESTINATION/RECEIVER ENTITY
`
`
`
`
`
`DESTINATION/RECEIVER ENTITY RESPONDS TO PATH
`
`
`
`
`
`MESSAGE BY GENERATING AND SENDING A RSVP RESV
`
`
`
`MESSAGE TOWARD SOURCING ENTITY
`
`
`
`
`
`
`
`
`
`RECEIVED RESV MESSAGE IS PASSED TO INTERMEDIATE
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`TO FIG. 6B
`
`
`FIG. 6A
`
`Splunk Inc.
`
`Exhibit1011
`
`Pages
`
`Splunk Inc. Exhibit 1011 Page 8
`
`

`

`
`U.S. Patent
`
`
`
`
`May29, 2007
`
`
`
`
`Sheet 7 of 10
`
`
`
`US 7,225,271 B1
`
`
`
`
`
`FROM FIG. 6A
`
`
`
`
`
`
`
`RSVP ENGINE SEARCHESITS SESSION TABLEFORA|_gig
`
`
`
`
`
`MATCHING ENTRY TO THE RECEIVED RESV MESSAGE
`
`
`
`
`
`ANALYZE FLOW PARAMETERS USING ONE OR MORE
`
`
`SETS OF HEURISTICS
`
`
`
`
`
`620
`
`
`
`
`
`
`
`
`
`
`
`DO
`
`FLOW PARAMETERS
`
`
`
`
`
`SATISFY APPLIED SET OF
`
`HEURISTICS
`
`
`
`YES
`
`NO
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`624
`
`
`
`
`
`
`
`
`
`
`ANTICIPATED TRAFFIC FLOW WILL BE CARRYING
`REAL-TIME VOICE TRAFFIC
`
`
`
`
`
`
`
`
`
`
`
`SELECT APPROPRIATE QUEUE SELECTION STRATEGY
`
`
`
`
`
`
`
`
`AND QUEUE FOR THE REAL-TIME VOICE TRAFFIC FLOW
`
`
`ne
`
`
`
`
`
`
`ANTICIPATED TRAFFIC FLOW WILL BE CARRYING
`
`
`
`
`
`INFORMATION OTHER THAN REAL-TIME VOICE TRAFFIC
`
`
`
`
`
`
`
`640~
`
`
`
`
`
`
`
`
`
`SELECT APPROPRIATE QUEUE SELECTION STRATEGY
`
`
`
`
`
`
`
`AND QUEUE FOR THE TRAFFIC FLOW DEEMED TO BE
`
`
`
`
`
`CARRYING OTHER THAN REAL-TIME VOICE
`
`
`
`GO TO BLOCK 628)—627
`
`
`FIG. 6B
`
`Splunk Inc.
`
`Exhibit1011
`
`Page 9
`
`Splunk Inc. Exhibit 1011 Page 9
`
`

`

`
`U.S. Patent
`
`
`
`
`May29, 2007
`
`
`
`
`Sheet 8 of 10
`
`
`
`US 7,225,271 B1
`
`
`
`
`
`FROM FIG. 6B
`
`628
`
`
`
`
`
`
`
`
`
`
`
`
`
`ASSIGN AND RESERVE SELECTED RESOURCES TO
`
`
`
`
`
`
`
`THE TRAFFIC FLOW OF THE RESERVATION REQUEST
`
`
`
`
`
`
`
`FORWARD RESV MESSAGE TO NEXT HOP TOWARD
`
`SOURCING ENTITY
`
`
`
`
`
`
`
`
`GENERATE AND SEND RESERVATION ERROR(ResvErr)
`
`
`
`MESSAGE BACK TO DESTINATION/RECEIVER ENTITY
`
`
`
`
`
`
`
`
`
`
`DOES
`
`RESERVATION REQUEST
`
`PASS ADMISSION
`
`CONTROL
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`634
`
`
`
`
`FIG. 6C
`
`Splunk Inc.
`
`Exhibit1011
`
`Page 10
`
`Splunk Inc. Exhibit 1011 Page 10
`
`

`

`
`U.S. Patent
`
`
`
`
`May29, 2007
`
`
`
`
`Sheet 9 of 10
`
`
`
`US 7,225,271 Bl
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`JOla
`
`
`
`Lagyz|64a|)Odsfzorerrsirezt|«dol=|bot=Sozporzeztii]—sss__|ertgoroor'eziLeg
`||Dawmam|zlosivarvect]dan|soo|sovier'zertii]sso|sr¥90l00ezL-eo1z||dfopvosreirezs}gan=|eo,=faizeprozeerz|pt|Sor
`zezgeze0z}poz|dv|cOMIM
`
`
`tse|pelzrsze'so1|og)aeeeeespsbezizc|siz|boligersst
`fosrssrtizeze]dol| oeor—|s0zeozesrac1]
`CALOSTSS|NOWLOSTSS|~spgingugJOUNOS
`
`
`Hd|/ADSLVELSssaeay09010udSssauddv
`
`
`vd
`
`
`
`002
`
`
`
`
`
`—|aNaNO|sesyqqu
`
`
`
`d1aVvlNOISSSSdASHY
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SplunkInc.
`
`Exhibit1011
`
`Page 11
`
`Splunk Inc. Exhibit 1011 Page 11
`
`
`
`

`

`
`U.S. Patent
`
`
`
`
`May29, 2007
`
`
`
`Sheet 10 of 10
`
`
`US 7,225,271 B1
`
`
`
`
`
`
`
`
`
`
`
`800
`
`
`
`816
`814
`
`
`|FLAGS} MSG.TYPE
`
`
`
`
`
`RESV
`
`
`
`812
`
`
`VERS.
`
`SEND TTL
`
`
`]
`
`820
`
`
`
`82
`
`
`
`Z
`
`826
`
`
`
`
`
`
`18
`8
`
`RSVP CHECKSUM
`
`
`
`RSVP LENGTH
`
`!
`
`828
`
`
`
`
`
`
`
`830
`
`836
`
`838
`
`840
`
`|
`
`
`
`
`842
`
`
`
`
`
`
`
`
`
`PARAM
`
`
`
`
`
`
`TOKEN BUCKET RATE (r)
`
`
`
`
`
`
`844
`TOKEN BUCKETSIZE (b)
`
`
`846
`PEAK DATA RATE(p)
`
`
`
`
`MINIMUM POLICED UNIT
`
`
`
`
`MAXIMUM PACKETSIZE
`eeee
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`IP DESTINATION ADDRESS
`ProrocoLio{ |—|DEST PORT
`
`
`
`
`
`858
`
`860
`
`FIG. 8
`
`Splunk Inc.
`
`Exhibit1011
`
`Page 12
`
`Splunk Inc. Exhibit 1011 Page 12
`
`

`

`
`
`US 7,225,271 Bl
`
`
`
`
`1
`SYSTEM AND METHOD FOR
`
`
`
`RECOGNIZING APPLICATION-SPECIFIC
`
`FLOWS AND ASSIGNING THEM TO
`
`
`
`
`
`QUEUES
`
`
`2
`
`
`
`
`
`
`
`Voice over IP (VoIP) typically refers to a group of technolo-
`
`
`
`
`
`
`
`gies used to transmit voice information over computer
`
`
`
`
`
`
`
`networks. Such networks include a plurality of voice agents
`
`
`
`
`
`
`
`that convert voice information from its traditional telephony
`
`
`
`
`
`
`
`
`form to a form suitable for packet transmission. In other
`
`
`
`
`
`
`
`
`words, the voice agent encodes, compresses and encapsu-
`
`
`
`
`
`
`
`
`lates the voice information into a plurality of data packets.
`
`
`
`
`
`
`
`
`1. Field of the Invention
`
`
`
`
`Examples of voice agents include endstations running voice
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`applications, IP telephones, VoIP gateways, certain private
`The present invention relates to computer networks and,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`branch exchanges (PBXs), etc. A calling party uses a voice
`more specifically, to the application of Quality of Service
`
`
`
`
`
`
`
`
`
`
`
`
`
`agent to initiate a VoIP call. Once the voice information has
`(QoS) treatments to network traffic flows.
`
`
`
`
`
`
`
`
`
`
`
`
`been converted into packet format,
`is carried by the
`it
`2. Background Information
`
`
`
`
`
`
`
`
`
`
`
`
`computer network to a second voice agent configured to
`Computer networks typically comprise a plurality of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`serve the called party. Voice traflic, unlike static data files or
`interconnected entities. An entity may consist of any device,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`records, is highly sensitive to delay andto lost packets. That
`such as a computer or endstation, that “sources” (i.e.,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`is, delays in receiving data packets carrying voice informa-
`transmits) or “sinks”(1.e., receives) datagrams(e.g., packets
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tion at the called party’s voice agentor the loss of such data
`and/or frames). A common type of computer network is a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`packets can seriously degrade the quality of the call. Accord-
`local area network (“LAN”) which typically refers to a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ingly, packets carrying voice information must be delivered
`privately owned network within a single building or campus.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`to the called party with a high probability and in a timely
`LANstypically employ a data communication protocol
`manner.
`
`
`
`
`
`
`
`
`
`(LANstandard), such as Ethernet, FDDI or token ring, that
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`services and
`include numerous
`Computer networks
`defines the functions performedby the data link and physical
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`resources for use in forwarding network traffic. For example,
`layers of a communications architecture (i.e., a protocol
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`different network links, such as Fast Ethernet, Asynchronous
`stack). In many instances, several LANs may be intercon-
`
`
`
`
`
`
`
`
`
`
`
`
`
`Transfer Mode (ATM) channels, SONET links, satellite
`nected by point-to-point links, microwave transceivers, sat-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`links, etc., offer different speed and bandwidth capabilities.
`ellite hook-ups, etc. to form a wide area network (“WAN”)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`specific
`Particular
`intermediate devices
`also include
`or intranet that may span an entire country or continent.
`
`
`
`
`
`
`
`One or more intermediate network devices are often used
`
`
`
`
`
`
`
`
`resources or services, such aspriority queues, filter settings,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`traffic shapers, queue selection strategies, congestion control
`to couple LANstogether and allow the corresponding enti-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`algorithms, etc. that affect the rate at which traflic moves
`ties to exchange information. For example, a bridge may be
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`through the device and thus across the network. Depending
`used to provide a “bridging” function between two or more
`
`
`
`
`
`
`
`
`
`
`
`
`
`on the selection or allocation of such resources or services,
`LANs. Alternatively, a switch may be utilized to provide a
`
`
`
`
`
`
`network traffic for different sources and sinks can be for-
`
`
`
`
`
`
`
`
`
`“switching” or interconnection function for transferring
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`warded at different speeds or rates, thereby controlling the
`information between a plurality of LANs or endstations.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`loss and/or delay experienced bythetraffic. To take advan-
`Bridges and switches may operate at various levels of the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`tage of these services and resources, individual frames or
`communication protocol stack. For example, a switch may
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`packets can be markedsothat intermediate devices will treat
`operate at layer 2 which, in the Open Systems Interconnec-
`
`
`
`
`
`
`
`
`
`
`
`
`
`them in a predetermined manner.
`tion (OSI) Reference Model, is called the data link layer and
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Morespecifically, the Institute of Electrical and Electron-
`includes the Logical Link Control (LLC) and Media Access
`40
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`ics Engineers (IEEE), in an appendix (802.1p) to the 802.1D
`Control (MAC) sub-layers. Data frames at the data link layer
`
`
`
`
`
`
`
`
`
`
`
`
`
`bridge specification standard, describes additional informa-
`typically include a header containing the MAC address of
`
`
`
`
`
`
`
`
`
`tion that can be loaded into the MAC header of Data Link
`
`
`
`
`
`
`
`
`
`
`the entity sourcing the message, referred to as the source
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Layer frames. FIG. 1A is a partial block diagram of a Data
`address, and the MAC address of the entity to whom the
`
`
`
`
`
`
`
`Link frame 100 which includes a MAC destination address
`
`
`
`
`
`
`
`
`messageis being sent, referred to as the destination address.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`(DA)field 102, a MAC source address (SA)field 104 and a
`To perform the switching function, layer 2 switches examine
`
`
`
`
`
`
`
`
`the MAC destination address of each data frame received on
`
`
`
`
`
`
`
`
`data field 106. In accordance with the 802.1p standard, a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`user_priority field 108, among others, is inserted after the
`a source port. The frame is then switched onto the destina-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`MACSAfield 104. The user_priority field 108 may be
`tion port(s) associated with that MAC destination address.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`loaded with a predetermined value (e.g., 0-7) that is asso-
`Other network devices, commonly referred to as routers,
`
`
`
`
`
`
`
`
`
`
`
`
`
`ciated with a particular treatment. Possible treatments
`mayoperate at higher communication layers, such as layers
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`include background, best effort, excellent effort, etc. Net-
`3, 4 or even higher. Layers 3 and 4 of Transmission Control
`
`
`
`
`
`
`
`
`
`
`
`
`
`work devices examinethe user_priority field 108 of received
`Protocol/Internet Protocol (TCP/IP) networks correspond to
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`frames 100 and apply the corresponding treatment to the
`the IP and TCP/User Datagram Protocol
`(UDP)
`layers,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`frames. For example, an intermediate device may have a
`respectively. Data frames at the IP layer also include a
`
`
`
`
`
`
`
`
`header that contains an IP source address and an IP desti-
`
`
`
`
`
`
`
`plurality of transmission queues per port each queue having
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a different priority, and may assign frames to different
`nation address. Routers or layer 3 switches may re-assemble
`
`
`
`
`
`
`
`or convert received data frames from one LAN standard
`
`
`
`
`
`
`
`
`
`queuesof a destination port on the basis of the frame’s user
`
`
`
`
`
`
`
`
`
`
`priority value.
`(e.g., Ethernet) to another (e.g. token ring). Thus, layer 3
`
`
`
`
`
`
`devices are often used to interconnect dissimilar subnet-
`
`
`
`
`
`
`
`FIG. 1B is a partial block diagram of a Network Layer
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`packet 120 corresponding to the Internet Protocol
`(IP).
`works. Many equipment manufacturers include both layer 2
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Packet 120 includes a type_of_service (ToS) field 122, a
`switching and layer 3 routing functions in a single device.
`
`
`
`
`
`
`
`
`
`
`
`protocol field 124, an IP source address (SA) field 126, an
`Voice Over IP (VoIP)
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`IP destination address (DA)field 128 and a data field 130.
`Traditionally, computer networks were used to exchange
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The ToS field 122 is used to specify a particular service to
`static files or data, such as text and spreadsheetfiles, while
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`be applied to the packet 120, such as high reliability, fast
`the Public Switched Telephone Network (PSTN) wasused to
`
`
`
`
`
`
`
`
`
`
`
`
`
`delivery, accurate delivery, etc. It comprises a number of
`exchange voice information. Computer networks, however,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`sub-fields, including a three bit IP precedence (IPP) field and
`are increasingly being used to transport “voice” information.
`
`Splunk Inc.—Exhibit 1011 Page 13
`
`BACKGROUND OF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`
`20
`
`25
`
`
`
`30
`
`
`
`35
`
`
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`Splunk Inc. Exhibit 1011 Page 13
`
`

`

`
`
`
`
`US 7,225,271 Bl
`
`
`
`
`
`
`
`20
`
`25
`
`
`
`30
`
`
`
`
`4
`
`
`
`
`
`
`transmission purposes. Each reserved queue, moreover, is
`
`
`
`
`
`
`
`given a weight anda selection strategy, such as Weighted
`
`
`
`
`
`
`
`
`Fair Queuing (WFQ), is used to select packets from among
`
`
`
`
`
`
`
`
`the various queues for transmission. Manypractical imple-
`
`
`
`
`
`
`mentations of flow-based queuing, however, do not always
`
`
`
`
`
`
`
`result in real-time voice flows being forwardedat sufficient
`
`
`
`
`
`speeds to avoid a degradation in call quality.
`
`
`
`
`
`
`
`
`Furthermore, with RSVP, path and reservation state is
`
`
`
`
`
`
`
`
`maintained for each flow. This presents scalability problems
`
`
`
`
`
`
`
`
`as the number of flows increases. Indeed, certain devices,
`
`
`
`
`
`
`
`
`such as core routers, may have to maintain thousandsor tens
`
`
`
`
`
`
`
`
`
`
`of thousands of RSVP flows. This can severely tax the
`
`
`
`
`
`
`
`
`router’s processor and memory resources. The path and
`
`
`
`
`
`
`
`reservation states, moreover, must also be periodically
`
`
`
`
`
`
`thereby increasing the number of “overhead”
`refreshed,
`
`
`
`
`
`
`
`messages that are forwarded through the network.
`
`
`
`
`
`
`
`
`Onesolution to the real-time traffic forwarding and scal-
`
`
`
`
`
`
`
`
`ability problemsis to have RSVPinteroperate with the PHBs
`
`
`
`
`
`
`
`
`of the Differentiated Services (DiffServ) Model. With this
`
`
`
`
`
`
`
`
`solution, per flow state is offloaded to the edges of one or
`
`
`
`
`
`
`
`more DiffServ networks, and packets corresponding to the
`
`
`
`
`
`
`
`
`
`flow are marked before entering the DiffServ networks with
`
`
`
`
`
`
`
`
`appropriate DSCP. Within the DiffServ networks, the RSVP
`
`
`
`
`
`
`
`
`
`messages are ignored and RSVPstates are not maintained.
`
`
`
`
`
`
`
`
`
`Instead, packets are provided with the PHBassociated with
`
`
`
`
`
`
`
`
`
`the DSCP value with which they have been marked.
`
`
`
`
`
`
`
`There are, nonetheless,
`several drawbacks with this
`
`
`
`
`
`
`
`
`
`approach. For example, the source entity or the edge device
`
`
`
`
`
`
`
`must be configured to mark the packets of the traffic flow
`with the correct DSCP. Each device within the DiffServ
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`networks, moreover, must be configured to recognized the
`
`
`
`
`
`
`
`
`marked traffic and apply the corresponding PHB. Precau-
`
`
`
`
`
`
`
`
`
`tions must be taken to ensure that only “approved” or
`“trusted” entities or devices mark traffic with DSCP values.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Otherwise, the network could suffer theft-of-service attacks.
`
`
`
`
`
`
`Furthermore, packets traversing multiple DiffServ networks
`
`
`
`
`
`
`
`that belong to different administrative domains may need to
`
`
`
`
`
`
`
`
`
`be re-marked, unless the domains can agree upon common
`
`
`marking values.
`
`
`3
`
`
`
`
`
`
`
`
`three one bit flags (Delay, Throughput and Reliability). By
`
`
`
`
`
`
`
`
`
`setting the variousflags, a source may indicate which overall
`
`
`
`
`
`
`
`
`service it cares most about(e.g., throughput versusreliabil-
`
`
`
`
`
`
`
`
`
`
`ity). The protocol field 124 is used to identify the next higher
`
`
`
`
`
`
`
`
`
`
`protocol
`that
`is to receive the packet. Version 6 of the
`
`
`
`
`
`
`
`
`Internet Protocol (IPv6) similarly defines a traffic class field,
`
`
`
`
`
`
`
`
`
`which is also intended to be used for defining the type of
`
`
`
`
`
`service to be applied to the corresponding packet.
`
`
`
`
`
`
`
`Recently, a working group of the Internet Engineering
`
`
`
`
`
`
`
`Task Force (IETF) developed a specification standard for
`
`
`
`
`
`
`
`
`
`replacing the ToS field 112 of Network Layer packets 120
`
`
`
`
`
`
`
`
`
`with a one octet differentiated services (DS) field 132 that
`
`
`
`
`
`
`
`can be loaded with a differentiated services codepoint
`
`
`
`
`
`
`
`
`(DSCP) value. Layer 3 devices that are DS compliant apply
`
`
`
`
`
`
`
`
`a particular per-hop behavior (PHB)to packets based on the
`
`
`
`
`
`
`
`value contained in their DS fields 132. Examples of PHBs
`
`
`
`
`
`
`
`defined by the IETF include expedited forwarding (EF) and
`
`
`
`assured forwarding (AF).
`
`
`
`
`
`
`FIG. 1C is a partial block diagram of a Transport Layer
`
`
`
`
`
`
`
`
`packet 150. In the TCP/IP Reference Model, the transport
`
`
`
`
`
`
`
`layer corresponds to the Transmission Control Protocol
`
`
`
`
`
`
`
`
`(TCP) or the User Datagram Protocol (UDP). The transport
`
`
`
`
`
`
`
`
`
`layer packet 150 preferably includes a source port field 152,
`
`
`
`
`
`
`
`
`
`
`a destination port field 154 and a data field 156, among
`
`
`
`
`
`
`
`
`
`
`others. Fields 152 and 154 are preferably loaded with the
`
`
`
`
`
`
`predefined or dynamically agreed-upon TCP or UDP port
`
`
`
`
`
`numbers being utilized by the respective applications of the
`
`
`
`
`
`
`corresponding network entities. A TCP or UDP packet 150
`
`
`
`
`
`
`
`is typically encapsulated within an IP packet 120 by placing
`
`
`
`
`
`
`
`
`
`it in the data portion 130 of the IP packet 120. The IP packet
`
`
`
`
`
`
`
`
`120, in turn, is encapsulated in the data portion 106 of a Data
`
`
`
`
`
`
`
`
`Link frame 100 for transmission across a computerlink.
`The Resource Reservation Protocol
`
`
`
`
`
`
`
`
`
`
`
`
`Asset forth above, to support VoIP, packets carrying voice
`35
`
`
`
`
`
`
`
`information must typically be delivered within narrow time
`
`
`
`
`
`
`
`
`constraints and with high probability. Although many com-
`
`
`
`
`
`
`
`
`
`puter networks have the resources and services to meet the
`
`
`
`
`
`
`
`delivery requirements of VoIP, these resources and services
`
`
`
`
`
`
`
`
`must be allocated, preferably in advance,
`to the correct
`
`
`
`
`
`
`
`networktraffic. The Resource reSerVation Protocol (RSVP),
`
`
`
`
`
`
`
`
`whichis set forth at Request for Comments (RFC) 2205, is
`
`
`
`
`
`
`
`
`
`a signaling protocol that was developed so that entities
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Briefly, the invention relates to a system for assigning
`(typically referred to as receivers) could reserve bandwidth
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`network traffic flows to appropriate queues and/or queue
`within their computer networks to receive a desiredtraffic
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`flow, such as voice information or a multimedia stream, from
`servicing algorithms based upon one or more flow param-
`
`
`
`
`
`
`
`
`
`
`
`eters contained in reservation requests associated with the
`one or more sourcing entities.
`
`
`
`
`
`
`
`
`
`
`
`
`
`traffic flows. In the illustrative embodiment, an intermediate
`Pursuant to RSVP, sources send RSVP Path messages
`
`
`
`
`
`
`
`
`
`
`
`
`
`network device disposed within a computer network
`identifying themselves and indicating the bandwidth needed
`
`
`
`
`
`
`
`
`
`
`
`
`
`includesa reservation engine, a packet classification engine,
`to receive their programming or content. These messages
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`an admission control entity, a traffic scheduler and a flow
`proceed hop-by-hop through the intermediate network
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`analyzer. The flow analyzer includes or has access to a
`devices of the computer network, making those devices
`
`
`
`
`
`
`
`
`
`
`
`
`
`memory that is preprogrammed with heuristics for use in
`aware of the possibility that a reservation of resources may
`
`
`
`
`
`
`
`
`
`
`
`
`
`evaluating the flow parameters of reservation requests. A
`be required. If a receiveris interested in the programming or
`
`
`
`
`
`
`
`
`
`
`
`
`
`network entity that wishes to receive certain information,
`content offered by a particular source, it responds with a
`
`
`
`
`
`
`
`
`
`
`
`
`
`such as real-time voice information,
`issues a reservation
`RSVP Reservation (Resv) message, which travels hop-by-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`request to the computer network. The network entity loads
`hop back to the source. At each hop,
`the corresponding
`
`
`
`
`
`
`
`
`intermediate device establishes a session for the receiver and
`
`
`
`
`
`
`
`
`the reservation request with one or more flow parameters
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`that characterize the bandwidth and/or forwarding require-
`sets aside sufficient resources to provide the requested
`
`
`
`
`
`bandwidth for the desired traflic flow. If the resources are not
`
`
`
`
`
`
`
`
`
`
`ments of the anticipated traflic flow.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Whenthe reservation request is received at the interme-
`available, the reservation is explicitly refused so that the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`diate network device, it is passed to the flow analyzer. The
`receiver knowsit cannot depend on resources being devoted
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`flow analyzer applies the predefined heuristics from the
`to its trafic. By using RSVP, packets carrying voice infor-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`memory to identify and select the queue and/or the queue
`mation can be accorded the resources and services they need
`
`
`
`
`
`
`
`
`
`
`
`servicing algorithm that best meets the requirements of the
`to ensure timely delivery.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`traffic flow. The traffic flow is then assigned to the selected
`In some RSVP implementations, each traflic flow, such as
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`queue. In particular, the packet/frameclassification engine is
`a streaming multimedia flow, a real-time voice flow, a video
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`instructed to identify packets corresponding to the traflic
`conferenceflow,etc., is assigned its own reserved queue for
`
`Splunk Inc.—Exhibit 1011 Page 14
`
`SUMMARY OF THE INVENTION
`
`
`
`
`
`
`
`40
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`Splunk Inc. Exhibit 1011 Page 14
`
`

`

`
`
`US 7,225,271 Bl
`
`
`5
`
`
`
`
`
`
`
`
`flow, and the traffic scheduler is directed to apply the
`
`
`
`
`
`
`
`reserved resources,
`i.e.,
`the selected queue,
`to packets
`
`
`
`
`matching the identified flow.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`The invention description below refers to the accompa-
`
`
`
`nying drawings, of which:
`
`
`
`
`
`
`
`FIGS. 1A-C, previously discussed, are partial block dia-
`
`
`
`grams of network messages;
`
`
`
`
`
`FIG.2 is a highly schematic block diagram of a computer
`
`network;
`
`
`
`
`
`FIG.3 is a highly schematic block diagram of a network
`
`entity;
`
`
`
`
`
`
`FIG. 4 is a highly schematic block diagram of an inter-
`
`
`
`
`
`
`
`mediate network device in accordance with the present
`
`invention;
`
`
`
`
`
`FIG. 5 is a highly schematic block diagram of an interface
`
`
`
`
`of the device of FIG. 4;
`
`
`
`
`
`
`
`FIGS. 6A-C is a fl