`
`milminiuliul!ipig21,01o111111111111111111
`
`(12) United States Patent
`DiBiasio et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,225,271 B1
`May 29, 2007
`
`(54) SYSTEM AND METHOD FOR
`RECOGNIZING APPLICATION-SPECIFIC
`FLOWS AND ASSIGNING THEM TO
`QUEUES
`
`(75)
`
`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)
`
`Filed:
`
`Jun. 29, 2001
`
`(51)
`
`(52)
`
`(58)
`
`(56)
`
`Int. Cl.
`GO6F 15/173
`GO6F 15/16
`U.S. Cl.
`
`(2006.01)
`(2006.01)
` 709/240; 709/224; 709/231;
`709/238; 709/241
` 709/223-225,
`Field of Classification Search
`709/231-233, 236, 238-240
`See application file for complete search history.
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`5,519,689 A * 5/1996 Kim
`5,765,032 A
`6/1998 Valizadeh
`5,926,458 A
`7/1999 Yin
`6,006,264 A
`12/1999 Colby et al.
`6,034,945 A
`3/2000 Hughes et al.
`6,088,734 A
`7/2000 Mann et al.
`6,091,709 A
`7/2000 Harrison et al.
`6,091,725 A
`7/2000 Cheriton et al.
`6,104,998 A
`8/2000 Galand et al.
`6,111,877 A
`8/2000 Wilford et al.
`6,157,955 A
`12/2000 Narad et al.
`6,167,445 A
`12/2000 Gai et al.
`6,188,698 B1
`2/2001 Galand et al.
`6,192,032 B1 * 2/2001 Izquierdo
`
`370/232
`
`370/230
`
`709/232
`
`704/500
`
`709/228
`
`370/230
`
`6/2001 Kerr et al.
`6,243,667 B1
`6,286,052 Bl* 9/2001 McCloghrie et al.
`6,292,832 B1
`9/2001 Shah et al.
`6,308,148 B1
`10/2001 Bruins et al.
`6,320,845 B1
`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 El-chanti
`(74) Attorney, Agent, or Firm Cesari and McKenna LLP
`
`(57)
`
`ABSTRACT
`
`A system assigns network traffic 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 traffic 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
`
`424
`
`RSVP
`ENGINE
`
`504
`
`PQ
`
`514
`PACKETS
`RECEIVED
`FOR
`TRANSMISSION
`
`CLASSIFICATION
`ENGINE
`
`502
`
`RESERVED —506
`QUEUES
`506a
`Q1
`
`2
`
`r.506b
`
`
`506c
`
`506d
`
`3
`
`4
`
`rr
`
`0
`
`LU
`CO
`LU
`
`—510
`
`512
`
`OUTPUT
`
`516
`
`OUTPUT
`INTERFACE
`406b
`
`DEFAULT
`QUEUE
`508
`
`Cloudflare - Exhibit 1011, page 1
`
`Cloudflare - Exhibit 1011, page 1
`
`

`

`US 7,225,271 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
` 370/443
`
`3/2002 Elwalid et al.
`6,353,616 B1 *
`10/2002 Mohaban et al.
`6,463,470 B1
`10/2002 Naveh et al.
`6,466,984 B1
`6,640,248 B1 * 10/2003 Jorgensen
`6,654,373 B1 * 11/2003 Maher, III et al.
`6,665,273 B1
`12/2003 Goguen et al.
` 370/235
`6,690,647 B1 *
`2/2004 Tang et al.
` 370/328
`6,738,361 B1 *
`5/2004 Immonen et al.
` 370/395.21
`6,744,767 B1 * 6/2004 Chiu et al.
`6,909,708 B1 * 6/2005 Krishnaswamy et al ... 370/352
`7,072,336 B2 *
`7/2006 Barany et al.
` 370/389
`
` 709/226
` 370/392
`
`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-iss11-ds-map-01.txt, http://www.ietf.org, 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 Diffsery 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
`
`Cloudflare - Exhibit 1011, page 2
`
`Cloudflare - Exhibit 1011, page 2
`
`

`

`lualud °S11
`
`OI Jo 1 WIN
`
`la utszt`L sa
`
`102
`/
`MAC
`DA
`
`104
`
`MAC
`SA
`
`108
`
`USER
`PRIORITY
`
`L
`
`:100
`
`c
`
`106
`
`DATA
`
`132
`
`122
`
`DS
`
`[
`
`
`ToS
`
`FIG. 1A (PRIOR ART)
`
`124
`,
`PROTOCOL
`
`126
`,
`IP
`SA
`
`128
`,
`IP
`DA
`
`c
`
`120
`
`130
`r
`DATA
`
`FIG. 1B (PRIOR ART)
`
`Ell
`
`K 150
`
`152
`/
`SOURCE
`PORT
`
`154
`/
`DEST.
`PORT
`
`156
`/
`DATA
`
`FIG. 1 C (PRIOR ART)
`
`Cloudflare - Exhibit 1011, page 3
`
`Cloudflare - Exhibit 1011, page 3
`
`

`

`U.S. Patent
`
`May 29, 2007
`
`Sheet 2 of 10
`
`US 7,225,271 B1
`
`r
`
`I
`
`offfl
`
`CN
`
`CN
`CV
`
` J
`
`CN
`
`0
`U-
`
`CN
`
`CN
`
`On
`
`z
`
`CD
`O
`CN
`
`CD
`
`CN
`
`cal
`
`CO O
`/
`
`, CO
`i
`
`8
`
`Cloudflare - Exhibit 1011, page 4
`
`Cloudflare - Exhibit 1011, page 4
`
`

`

`lualud °S11
`
`In JO £ JamiS
`
`la utszt`L sa
`
`( -202
`
`302
`7
`
`VOICE AGENT
`310
`
`/
`
`CALL
`SIGNALLING
`ENTITY
`
`RSVP ENTITY
`306
`7
`RSVP
`MESSAGE
`GENERATOR
`
`304
`7
`
`7 308
`
`RSVP
`STATE
`
`MACHINE 1
`
`COMMUNICATION FACILITY
`
`TO/FROM
`NETWORK
`200
`
`FIG. 3
`
`Cloudflare - Exhibit 1011, page 5
`
`Cloudflare - Exhibit 1011, page 5
`
`

`

`lualud °S11
`
`in JO 17 JamiS
`
`la utszt`L sa
`
`/ 208
`
`N
`-1/
`
`- 422
`
`FORWARDING ENGINE
`
`RSVP ENGINE
`
`
`RSVP MESSAGE GENERATOR
`
`
`
`1-405
`I
`
`424
`
`426
`
`RSVP STATE MACHINE ENGINE-1--- 428
`
`SESSION TABLE
`
`1,700
`
`ADMISSION CONTROL ENTITY1---- 430
`
`FLOW ANALYZER
`
`HEURISTIC STORE
`
`--432
`
`434
`
`/ 7-
`
`FIG. 4
`
`PACKET/FRAME
`RECEIVER
`TRANSMITTER OBJECT
`
`406a
`
`408a
`
`410a
`
`412a
`
`406b
`
`I
`
`408b
`
`I
`
`410b
`
`412b
`
`I
`
`I
`
`402
`
`406
`
`408
`,.._,,,..
`410H
`
`
`
`412
`H
`
`404,, TRAFFIC SCHEDULER
`414
`
`I
`I
`1
`
`4161
`
`METER ENTITY
`
`MARKER ENTITY
`
`418 1
`
`SHAPER ENTITY
`420 -- DROPPER ENTITY I
`
`Cloudflare - Exhibit 1011, page 6
`
`Cloudflare - Exhibit 1011, page 6
`
`

`

`Walud *S11
`
`OT JO S JamiS
`
`Ill utszt`L sa
`
`504
`
`?
`
`PQ
`
`I
`
`510
`
`512
`?
`
`-,-pp.-
`
`OUTPUT
`
`516
`4._
`
`QUEUE SELECTOR / SCHEDULER
`
`RESERVED —506
`QUEUES
`r 506a
`
`
`Qi
`
`21
`
`Q3
`
`
`
`Q4
`
`506 b
`I.
`
`506c
`I.
`
`506d
`
`d DEFAULT
`
`QUEUE
`
`508
`
`FIG. 5
`
`424
`
`RSVP
`ENGINE
`
`514
`?
`PACKETS
`RECEIVED
`FOR
`TRANSMISSION
`
`CLASSIFICATION
`ENGINE
`
`r
`502
`
`OUTPUT
`INTERFACE
`406b
`
`Cloudflare - Exhibit 1011, page 7
`
`Cloudflare - Exhibit 1011, page 7
`
`

`

`U.S. Patent
`
`May 29, 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
`
`T
`
`PATH MESSAGE IS FORWARDED TOWARD DESTINATION/
`RECEIVER ENTITY
`
`606
`
`RECEIVED PATH MESSAGE IS PASSED TO INTERMEDIATE
`NETWORK DEVICE'S RSVP ENGINE FOR PROCESSING
`
`608
`
`Tv
`RSVP ENGINE STORES CONTENTS OF RECEIVED PATH
`MESSAGE INCLUDING ADDRESS OF PREVIOUS HOP
`
`I
`INTERMEDIATE NETWORK DEVICE LOADS ITS ADDRESS
`INTO THE PATH MESSAGE AND FORWARDS THE PATH
`MESSAGE TOWARD THE DESTINATION/RECEIVER ENTITY
`
`1
`DESTINATION/RECEIVER ENTITY RESPONDS TO PATH
`MESSAGE BY GENERATING AND SENDING A RSVP RESV
`MESSAGE TOWARD SOURCING ENTITY
`
`ly
`RECEIVED RESV MESSAGE IS PASSED TO INTERMEDIATE
`NETWORK DEVICE'S RSVP ENGINE FOR PROCESSING
`
`610
`
`612
`
`614
`
`616
`
`TO FIG. 6B
`
`FIG. 6A
`
`Cloudflare - Exhibit 1011, page 8
`
`Cloudflare - Exhibit 1011, page 8
`
`

`

`U.S. Patent
`
`May 29, 2007
`
`Sheet 7 of 10
`
`US 7,225,271 B1
`
`FROM FIG. 6A
`
`[
`
`RSVP ENGINE SEARCHES TS SESSION TABLE FOR A
`MATCHING ENTRY TO THE RECEIVED RESV MESSAGE
`
`ANALYZE FLOW PARAMETERS USING ONE OR MORE
`SETS OF HEURISTICS
`
`618
`
` 620
`
`622
`DO
`FLOW PARAMETERS
`SATISFY APPLIED SET OF
`HEURISTICS
`
`NO
`
`YES
`
`ANTICIPATED TRAFFIC FLOW WILL BE CARRYING
`REAL-TIME VOICE TRAFFIC
`
`624
`
`SELECT APPROPRIATE QUEUE SELECTION STRATEGY
`AND QUEUE FOR THE REAL-TIME VOICE TRAFFIC FLOW
`
`626
`
`638
`
`ANTICIPATED TRAFFIC FLOW WILL BE CARRYING
`INFORMATION OTHER THAN REAL-TIME VOICE TRAFFIC
`
`1.4
`
`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
`
`Cloudflare - Exhibit 1011, page 9
`
`Cloudflare - Exhibit 1011, page 9
`
`

`

`U.S. Patent
`
`May 29, 2007
`
`Sheet 8 of 10
`
`US 7,225,271 B1
`
`FROM FIG. 6B
`
`628
`
`NO
`
`DOES
`RESERVATION REQUEST
`PASS ADMISSION
`CONTROL
`?
`VYES
`ASSIGN AND RESERVE SELECTED RESOURCES TO
`THE TRAFFIC FLOW OF THE RESERVATION REQUEST
`
`630
`
`FORWARD RESV MESSAGE TO NEXT HOP TOWARD
`SOURCING ENTITY
`
`I.,_ 632
`
`634
`
`GENERATE AND SEND RESERVATION ERROR (ResvErr)
`MESSAGE BACK TO DESTINATION/RECEIVER ENTITY
`
`FIG. 6C
`
`Cloudflare - Exhibit 1011, page 10
`
`Cloudflare - Exhibit 1011, page 10
`
`

`

`lualud °S11
`
`OT JO 6 WIN
`
`la utszt`L sa
`
`( 714
`
`SELECTED
`PHB
`
`EF
`
`AF
`
`/
`
`700
`
`( 702
`
`( 704
`
`RSVP SESSION TABLE
`( 706
`( 708
`
`( 710
`
`SOURCE
`ADDRESS
`
`SOURCE DESTINATION DESTINATION PROTOCOL
`PORT
`ADDRESS
`PORT
`
`716a
`716b
`716c —
`716d
`716e —
`
`123.100.106.148
`155.136.114.101
`165.225.147.174
`203.238.237.106
`123.100.106.148
`
`555
`718
`951
`114
`555
`
`111.222.104.205
`222.123.154.158
`156.189.208.205
`248.226.143.218
`111.132.141.168
`
`1061
`1032
`1030
`1028
`1061
`
`TCP
`TCP
`TCP
`UDP
`UDP
`
`FIG. 7
`
`Cloudflare - Exhibit 1011, page
`
`713
`
`712
`
`(
`PREVIOUS
`HOP
`ADDRESS
`
`(
`QUEUE
`SELECTION
`STRATEGY/
`QUEUE
`123.115.119.102
`PQ
`154.122.166.177 WFQ/Q2
`222211.155.156 WFO/Q3
`123.118.150.160
`PQ
`123.116.118.012 WFQ/DQ
`
`Cloudflare - Exhibit 1011, page 11
`
`

`

`U.S. Patent
`
`May 29, 2007
`
`Sheet 10 of 10
`
`US 7,225,271 B1
`
`816
`
`818
`
`RSVP CHECKSUM
`RSVP LENGTH
`
`rVERS.
`
`814
`812
`FLAGS MSG.TYPE
`RESV,
`SEND TTL
`820
`
`822
`
`X826
`LENGTH
`
`824
`
`( 830
`C-TYPE
`
`1
`1
`1
`
`802
`
`804
`
`( 828
`CLASS-NUM
`IP SOURCE ADDRESS
`SOURCE PORT
`\ 834
`
`832
`
`836
`
`838
`
`.840
`
`1
`
`800
`
`vi_
`
`LENGTH
`
`C-TYPE
`CLASS-NUM
`LENGTH
`SERV. HEADER
`LEN. OF SERV. 1 DATA
`PARAMETER LENGTH
`PARAM. ID PARAM. FLAGS
`842
`TOKEN BUCKET RATE (r)
`TOKEN BUCKET SIZE (b)
`844
`846
`PEAK DATA RATE (p)
`MINIMUM POLICED UNIT
`848 (m)
`850 (M)
`MAXIMUM PACKET SIZE
`
`/ 854
`( 852
`CLASS-NUM
`LENGTH
`IP DESTINATION ADDRESS
`DEST PORT
`‘860
`
`PROTOCOL ID
`
`858
`
`„..856
`,..._____.
`C-TYPE
`
`806
`
`808
`
`FIG. 8
`
`Cloudflare - Exhibit 1011, page 12
`
`Cloudflare - Exhibit 1011, page 12
`
`

`

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

`

`US 7,225,271 B1
`
`3
`three one bit flags (Delay, Throughput and Reliability). By
`setting the various flags, a source may indicate which overall
`service it cares most about (e.g., throughput versus reliabil-
`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 computer link.
`The Resource Reservation Protocol
`As set forth above, to support VoIP, packets carrying voice
`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
`network traffic. The Resource reSerVation Protocol (RSVP), 40
`which is set forth at Request for Comments (RFC) 2205, is
`a signaling protocol that was developed so that entities
`(typically referred to as receivers) could reserve bandwidth
`within their computer networks to receive a desired traffic
`flow, such as voice information or a multimedia stream, from
`one or more sourcing entities.
`Pursuant to RSVP, sources send RSVP Path messages
`identifying themselves and indicating the bandwidth needed
`to receive their programming or content. These messages
`proceed hop-by-hop through the intermediate network
`devices of the computer network, making those devices
`aware of the possibility that a reservation of resources may
`be required. If a receiver is interested in the programming or
`content offered by a particular source, it responds with a
`RSVP Reservation (Resv) message, which travels hop-by-
`hop back to the source. At each hop, the corresponding
`intermediate device establishes a session for the receiver and
`sets aside sufficient resources to provide the requested
`bandwidth for the desired traffic flow. If the resources are not
`available, the reservation is explicitly refused so that the
`receiver knows it cannot depend on resources being devoted
`to its traffic. By using RSVP, packets carrying voice infor-
`mation can be accorded the resources and services they need
`to ensure timely delivery.
`In some RSVP implementations, each traffic flow, such as
`a streaming multimedia flow, a real-time voice flow, a video
`conference flow, etc., is assigned its own reserved queue for
`
`4
`transmission purposes. Each reserved queue, moreover, is
`given a weight and a selection strategy, such as Weighted
`Fair Queuing (WFQ), is used to select packets from among
`the various queues for transmission. Many practical imple-
`5 mentations of flow-based queuing, however, do not always
`result in real-time voice flows being forwarded at 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
`10 as the number of flows increases. Indeed, certain devices,
`such as core routers, may have to maintain thousands or 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
`15 refreshed, thereby increasing the number of "overhead"
`messages that are forwarded through the network.
`One solution to the real-time traffic forwarding and scal-
`ability problems is to have RSVP interoperate with the PHBs
`of the Differentiated Services (DiffServ) Model. With this
`20 solution, per flow state is offloaded to the edges of one or
`more DiffSery networks, and packets corresponding to the
`flow are marked before entering the DiffSery networks with
`appropriate DSCP. Within the DiffSery networks, the RSVP
`messages are ignored and RSVP states are not maintained.
`25 Instead, packets are provided with the PHB associated 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
`30 with the correct DSCP. Each device within the DiffSery
`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.
`35 Otherwise, the network could suffer theft-of-service attacks.
`Furthermore, packets traversing multiple DiffSery networks
`that belong to different administrative domains may need to
`be re-marked, unless the domains can agree upon common
`marking values.
`
`SUMMARY OF THE INVENTION
`
`Briefly, the invention relates to a system for assigning
`network traffic flows to appropriate queues and/or queue
`45 servicing algorithms based upon one or more flow param-
`eters contained in reservation requests associated with the
`traffic flows. In the illustrative embodiment, an intermediate
`network device disposed within a computer network
`includes a reservation engine, a packet classification engine,
`so an admission control entity, a traffic scheduler and a flow
`analyzer. The flow analyzer includes or has access to a
`memory that is preprogrammed with heuristics for use in
`evaluating the flow parameters of reservation requests. A
`network entity that wishes to receive certain information,
`55 such as real-time voice information, issues a reservation
`request to the computer network. The network entity loads
`the reservation request with one or more flow parameters
`that characterize the bandwidth and/or forwarding require-
`ments of the anticipated traffic flow.
`60 When the reservation request is received at the interme-
`diate network device, it is passed to the flow analyzer. The
`flow analyzer applies the predefined heuristics from the
`memory to identify and select the queue and/or the queue
`servicing algorithm that best meets the requirements of the
`65 traffic flow. The traffic flow is then assigned to the selected
`queue. In particular, the packet/frame classification engine is
`instructed to identify packets corresponding to the traffic
`Cloudflare - Exhibit 1011, page 14
`
`Cloudflare - Exhibit 1011, page 14
`
`

`

`US 7,225,271 B1
`
`5
`flow, and the traffic scheduler is directed to apply the
`reserved resources, i.e., the selected queue, to packets
`matching the identified flow.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`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 flow diagram of the method of the
`present invention;
`FIG. 7 is a highly schematic illustration of a data struc-
`ture; and
`FIG. 8 is a block diagram of a reservation request mes-
`sage.
`
`DETAILED DESCRIPTION OF AN
`ILLUSTRATIVE EMBODIMENT
`
`FIG. 2 is a highly schematic diagram of a computer
`network 200. The network 200 includes first, second and
`third voice agents 202, 204, 206 that are interconnected by
`a plurality of intermediate network devices. More specifi-
`cally, first voice agent 202 is coupled to a first hop network
`device, such as router 208, which, in turn, is coupled to a
`second network device, such as router 210. Router 210, in
`turn, is coupled to a network cloud 212. The network cloud
`212 may consist of a plurality of network devices, local area
`networks (LANs), and end stations. Second voice agent 204
`is coupled to a first hop network device, such as router 214,
`which is coupled to router 216. Router 216, in turn, is
`coupled to network cloud 212. Third voice agent 206 is
`coupled to router 216.
`In the illustrative embodiment, voice agents 202, 204, 206
`are intermediate network devices 218-220 that have been
`configured to provide VoIP gateway support to other devices
`or entities, such as conventional analog telephone sets
`222-224, coupled thereto. Suitable VoIP gateway devices
`include the 3600 series of routers from Cisco Systems, Inc.
`of San Jose, Calif.
`It should be understood that the network configuration
`200 of FIG. 2 is for illustrative purposes only and that the
`present invention will operate with other, possibly far more
`complex, network topologies.
`FIG. 3 is a highly schematic, partial block diagram of a
`voice agent, such as voice agent 202. Voice agent 202, more
`specifically device 218, preferably includes a communica-
`tion facility 302 and one or more resource reservation
`components, such as a Resource reSerVation Protocol
`(RSVP) entity or engine 304. The RSVP entity 304, which
`includes a RSVP message generator 306 and a RSVP state
`machine engine 308, operates in accordance with the RSVP
`specification standard, which is set forth at Request for
`Comments (RFC) 2205 and is hereby incorporated by ref-
`erence in its entirety. Voice agent 202 further includes a call
`signaling entity 310 in communicating relationship with the
`RSVP entity 304 and the communication facility 302. Entity
`
`25
`
`6
`310 operates in accordance with a signaling protocol, such
`as H.323, Session Initiation Protocol (SIP), Media Gateway
`Control Protocol (MGCP) or MEGACO, which is an alter-
`native to MGCP. The RSVP entity 304 is also in commu-
`5 nicating relationship with the communication facility 302,
`and can thus exchange information, including network pack-
`ets and frames, with facility 302.
`The communication facility 302 preferably includes one
`or more software libraries for implementing a communica-
`10 tion protocol stack allowing voice agent 202 to exchange
`messages with other entities of network 200, such as voice
`agents 204 and/or 206. The communication facility 302 may,
`for example, include software layers corresponding to the
`Transmission Control Protocol/Internet Protocol (TCP/IP)
`15 communication stack, although other communication pro-
`tocols, such as Asynchronous Transfer Mode (ATM) cells,
`the Internet Packet Exchange (IPX) protocol, the AppleTalk
`protocol, the DECNet protocol and/or NetBIOS Extended
`User Interface (NetBEUI), among others, could be utilized.
`20 Communication facility 302 further includes transmitting
`and receiving circuitry and components, including one or
`more network interface cards (NICs) that establish one or
`more physical ports for exchanging data packets and frames
`with router 208 to which it is connected.
`It should be understood that voice agents 204 and 206
`include these same components, among others.
`FIG. 4 is a highly schematic, partial block diagram of an
`intermediate network device in accordance with the present
`invention, such as router 208, which is the first hop router
`30 from voice agent 202. Router 208 preferably includes one or
`more packet/frame receiver transmitter objects 402, a traffic
`scheduler 404, and a forwarding engine 405. The packet/
`frame receiver transmitter object 402 is preferably config-
`ured to provide one or more interfaces 406, 408, 410 and 412
`35 or ports for receiving and sending network messages by
`router 208. Each interface, e.g., interface 406, moreover,
`includes an inbound side 406a and an outbound side 406b.
`The traffic scheduler 404 includes a plurality of resources or
`services that are used by router 208 to forward packets. For
`40 example, scheduler 404 may include one or more metering
`entities 414, one or more marker entities 416, one or more
`shaper entities 418, and one or more dropper entities 420.
`The packet/frame receiver transmitter object 402, the
`traffic scheduler 404, and forwarding engine 405 are all in
`45 communicating relationship with each other via one or more
`communication paths or bus structures, such as system bus
`422, so that network messages as well as commands may be
`exchanged between them.
`Router 208 may also include one or more resource
`so allocation and reservation components. In the preferred
`embodiment, router 208 includes a RSVP