`
`(12) Unlted States Patent
`(10) Patent No.:
`US 7,225,271 B1
`
`DiBiasio et a].
`(45) Date of Patent:
`May 29, 2007
`
`(54) SYSTEM AND METHOD FOR
`RECOGNIZING APPLICATION-SPECIFIC
`FIIJE‘JESAND ASSIGNING THEM TO
`Q
`
`(75)
`
`Inventors: Michael V. DiBiasio, Westford, MA
`(US); Bruce S. Davie, Belmont, MA
`(US); David R. Oran, Acton, MA (US)
`
`6,243,667 B1
`6,286,052 B1*
`6,292,832 B1
`6,308,148 B1
`
`6/2001 Kerr et a1.
`9/2001 McCloghrie et al.
`9/2001 Shah et 31.
`10/2001 Bruins et al.
`
`6’320’845 B1
`
`11/2001 DaVie
`
`....... 709/238
`
`(73) Assignee: Cisco Technology, Inc., San Jose, CA
`(Us)
`
`(Continued)
`OTHER PUBLICATIONS
`
`( * ) Netice:
`
`Subjectto any diSCIaimera. the term Of this
`patent 1s extended or adjusted under 35
`U.S.C. 154(b) by 738 days.
`
`RSVP Support for Low Latency Queueing, Cisco Systems Incor-
`porated, San Jose, CA, Jul. 24, 2000, pp. 1-18.
`
`(21) Appl. No.: 09/896,276
`
`(22)
`
`Filed:
`
`Jun. 29, 2001
`
`(51)
`
`Int. Cl.
`(2006.01)
`G06F 15/173
`(2006.01)
`G06F 15/16
`(52) US. Cl.
`...................... 709/240; 709/224; 709/231;
`709/238; 709/241
`(58) Field of Classification Search ........ 709/2237225,
`.
`.
`709/2317233, 236, 2387240
`See app11catlon file for complete search 111510130
`References Cited
`
`(56)
`
`U.S. PATENT DOCUMENTS
`5,519,689 A *
`5/1996 Kim ........................... 370/232
`5,765,032 A
`6/1998 Valizadeh
`5 926 458 A *
`7/1999 Yin ............................ 370/230
`6:006:264 A
`12/1999 Colby et 31.
`6,034,945 A
`3/2000 Hughes et 31.
`6,088,734 A *
`7/2000 Marin et al.
`................ 709/232
`6,091,709 A
`7/2000 Harrison et al.
`6,091,725 A
`7/2000 Cheriton et 31~
`66513411122: 2 *
`$3888 \C’Ifiiitniettali """"""" 704/500
`a
`,
`1 or
`e a .
`6,157,955 A * 12/2000 Narad et al.
`................ 709/228
`6,167,445 A
`12/2000 Gai et al.
`6,188,698 B1
`2/2001 Galand et 31.
`6,192,032 B1*
`2/2001 Izquierdo .................... 370/230
`
`(Continued)
`
`Primary ExamineriArio Etienne
`Assistant ExamineriHussein El-chanti
`(74) Attorney, Agent, or FirmiCesari 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 1ntermed1ate network dev1ce 1ncludes a reservation
`
`engine, a packet classification engine, an admission control
`emllty’ a Fraifi: SChegmer’ and ta flow analytzlfri .The flow
`ana yzer1nc.u es or
`as access oamemory a 1s prepro-
`grammed Wlth one or more heunmc sets for use “1 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
`.
`.
`_
`3111alzlzeorfistilmwsoihtigpé’orsvpnate queue and/0r queue sew10
`g
`g
`‘
`
`28 Claims, 10 Drawing Sheets
`
`424
`
`ENGINE
`
`
`
`
`
`
`
`PACKETS
`RECEIVED
`FOR
`TRANSMISSION
`
`E
`d
`8D
`”:1a
`
`
`
`E E¥8
`
`
`
`OUTPUT
`
`m
`
`
`
`DEFAULT
`OUTPUT
`QUEUE
`INTERFACE
`
`
`
`
`Palo Alto Networks V. Sable Networks
`
`EX1011
`
`IPR2020-01712
`
`EX1011
`Palo Alto Networks v. Sable Networks
`IPR2020-01712
`
`
`
`US 7,225,271 B1
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`............. 370/443
`
`3/2002 Elwalid et a1.
`6,353,616 B1 *
`10/2002 Mohaban et a1.
`6,463,470 B1
`10/2002 Naveh et a1.
`6,466,984 B1
`6,640,248 B1 * 10/2003 Jorgensen ................... 709/226
`6,654,373 B1 *
`11/2003 Maher, III et a1.
`.
`370/392
`
`6,665,273 B1
`12/2003 Goguen et a1.
`6,690,647 B1 *
`2/2004 Tang et a1.
`................. 370/235
`6,738,361 B1 *
`5/2004 Immonen et al.
`370/328
`
`6,744,767 B1 *
`6/2004 Chiu et a1.
`............. 370/395.21
`6,909,708 B1*
`6/2005 Krishnaswamy et al.
`370/352
`
`7,072,336 B2*
`7/2006 Barany et al.
`.....
`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-O1.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.ietforg, 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.ietforg, Jun. 2000,
`pp. 1-6.
`
`* cited by examiner
`
`
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 1 of 10
`
`US 7,225,271 B1
`
`09‘
`
`E3E8a<295%momaom
`
`02V\
`
`2NE
`
`EH?«6?:or.oE
`
`
`
`Cm<moEn:m:.GE
`
`02ms3EnmoiECm<moan:4;.OE
`
`D
`
`moV
`
`oer
`\
`
`we?.2:m9
`
` >tmOEm<m<0
`
`
`1mm:o<_>_o<_>_
`
`
`
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 2 of 10
`
`US 7,225,271 B1
`
` 030.6
`com
`
`xmoibmz
`
`
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 3 of 10
`
`US 7,225,271 B1
`
`mom
`
`n_>mm
`
`mbfib
`
`
`
`mz_Io<_>_
`
`mom
`
`
`
`\Cfizmn_>mm
`
`n_>mm
`
`mo<mmm=2
`
`mohémzmo
`
`._._<o
`
`023.3205
`
`>._._._.2m_
`
`vomSm
`
`
`
`Hzm®<mo_o>
`
`VEO>>._.m_z
`
`_>_Omu_\o_.
`
`com
`
`m.OE
`
`
`
`>._._..__o<u_2922232200
`
`
`
`
`
`
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 4 of 10
`
`US 7,225,271 B1
`
`vmv
`
`MEEEVGE
`
`
`
`BmaomMEEmzqfi
`
` omvmogimzww
`
`8vmmsmowmN8
`
`
`
`
`wmv
`
`
`
`mzfizmmz__._o<_>_WEBn_>mm_
`
`
`
`mo<wmm§m>wm
`
`CON
`
`va
`
`vmv
`
`
`
`
`
`>._._.r2m_._Om._.zoozo_mm__>_o<
`
`omv3v
`
`
`
`w._m<.rzo_wmm_w
`
`
`
`mmSQMIomOEHZEH
`
`mmohwDimiamz
`
`
`
`w.O_n_
`
`mmN>._<z<>>O.Ew3
`
`m2
`
`wow
`
`o;
`
`N;
`
`vow
`
`o;
`
`omv
`
`
`
`
`
`
`
`
`S.U
`
`May 29, 2007
`
`US 7,225,271 B1
`
`0S53..
`
`
`
` t_IIaEh5&8sem0..mzazw
`
`NO
`
`«buHNS05Em31—
`
`MG
`
`tmzazmm0;15mMl—‘P.gm§
`
`I2920;8va
`
`0W:H3..mom
`
`On
`
`m.07.
`
`5342me
`
`mamSO.5950
`
`
`momamo<n_mm_.z_
`
`mom.
`
`3.5.9»;
`
`om>_m_om_m
`
`in
`
`zo_mm__>_wz<m._.
`
`
`
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 6 of 10
`
`US 7,225,271 B1
`
`
`CALL SIGNALING ENTITY DETECTS START
`OF CALL
`
`
`602
`
`RSVP ENGINE GENERATES ONE OR MORE PATH
`MESSAGES IN ORDER TO RESERVE NETWORK
`RESOURCES FOR THE ANTICIPATED
`
`504
`
`VOICE TRAFFIC
`
`
`
`PATH MESSAGE IS FORWARDED TOWARD DESTINATION/
`RECEIVER ENTITY
`
`606
`
`RECEIVED PATH MESSAGE IS PASSED TO INTERMEDIATE
`NETWORK DEVICE'S RSVP ENGINE FOR PROCESSING
`
`508
`
`
`610
`
`
`
`
`
`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
`
`I MESSAGE TOWARD THE DESTINATION/RECEIVER ENTITY
`
`612
`
`
`DESTINATION/RECEIVER ENTITY RESPONDS TO PATH
`
`
`MESSAGE BY GENERATING AND SENDING A RSVP RESV
`MESSAGE TOWARD SOURCING ENTITY
`
`
`
`614
`
`RECEIVED RESV MESSAGE IS PASSED TO INTERMEDIATE
`NETWORK DEVICE'S RSVP ENGINE FOR PROCESSING
`
`616
`
`TO FIG. 68
`
`FIG. 6A
`
`
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 7 of 10
`
`US 7,225,271 B1
`
`FROM FIG. 6A
`
`
`
`
`
`RSVP ENGINE SEARCHES ITS SESSION TABLE FOR A
`MATCHING ENTRY TO THE RECEIVED RESV MESSAGE
`
`618
`
`ANALYZE FLOW PARAMETERS USING ONE OR MORE
`SETS OF HEURISTICS
`
`620
`
`
`
`
`622
`
`D0
`FLOW PARAMETERS
`SATISFY APPLIED SET OF
`
`NO
`
`HEURISTICS
`
`
`
`
`
`
`YES
`
`ANTICIPATED TRAFFIC FLOW WILL BE CARRYING
`REAL-TIME VOICE TRAFFIC
`
`
`
`
`
`SELECT APPROPRIATE QUEUE SELECTION STRATEGY
`AND QUEUE FOR THE REAL-TIME VOICE TRAFFIC FLOW
`
`
`524
`
`626
`
`638+
`
`
`640~
`
`
`
`
`ANTICIPATED TRAFFIC FLOW WILL BE CARRYING
`INFORMATION OTHER THAN REAL-TIME VOICE TRAFFIC
`
`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. GB
`
`
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 8 of 10
`
`US 7,225,271 B1
`
`FROM FIG. BB
`
`
`628
`
`DOES
`
`RESERVATION REQUEST
`PASS ADMISSION
`CONTROL
`
`
`
`
`
`ASSIGN AND RESERVE SELECTED RESOURCES TO
`THE TRAFFIC FLOW OF THE RESERVATION REQUEST
`
`
`
`
`
`
`
`GENERATE AND SEND RESERVATION ERROR (Restrr)
`MESSAGE BACK TO DESTINATION/RECEIVER ENTITY
`
`FORWARD RESV MESSAGE TO NEXT HOP TOWARD
`SOURCING ENTITY
`
`634
`
`FIG. 60
`
`
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 9 of 10
`
`US 7,225,271 B1
`
`HE
`
`COO
`
`N
`
`IEllml
` ll
` _‘o.w:.©:umm
`
`QdeSAmm
`
`x—x—
`
`mtmmwfimdm
`
`\—\—‘C\l
`
`IEHlml
`LEIIF'35
`omzbmjmwzO_._.om._m_m
`
`IMala
`movmimidmano:
`JOOOHONE
`
`mzmsd
`
`89>me
`
`[\
`
`tdofimmfivm
`
`03
`
`
`
`
`
`wowmm.._m<._.206wan_>wm
`
`o
`N
`
`_.._‘an:52mom2:Na:Emmmmoo<
`
`.EOQ
`
`
`
`
`
`29.22:.me29.22;memomaow
`
`
`
` N.OE has52Egg;Ego:8.29mm3§.w§H0.882momwommag%nahmm?wmfivmgmfimmmwK
`
`momDOm
`
`mmmmoo<
`
`3.8325500"
`or:Emfimmw
`
`tximmmwww
`ozmmwmmdom
`
`wiootoovmmv
`
`we:
`
`no:
`
`co:
`
`8:
`
`we:
`
`
`
`
`
`
`
`
`
`
`
`U.S. Patent
`
`May 29, 2007
`
`Sheet 10 of 10
`
`US 7,225,271 B1
`
`
`
`VERS. FLAGS MSGTYPE
`
`
`
`g
`
`820
`
`826
`
`816
`
`v.
`
`822
`
`818
`
`RSVP LENGTH
`
`824
`
`828
`
`830
`
`'
`
`|
`
`800
`
`8% (M)
`
`TOKEN BUCKET RATE (r)
`
`TOKEN BUCKET SIZE (b)
`
`PEAK DATA RATE (p)
`
`8_4_2
`
`84_4
`
`{316
`
`MINIMUM POLICED UNIT w
`
`MAXIMUM PACKET SIZE
`
`_—_.._
`
`852
`
`854
`
`856
`
`LENGTH
`
`CLASS-NUM
`
`C-TYPE
`
`IP DESTINATION ADDRESS
`
`808
`
`
`
`DEST PORT
`
`858
`
`860
`
`
`
`US 7,225,271 B1
`
`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.
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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
`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
`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
`to the called party with a high probability and in a timely
`manner.
`
`services and
`include numerous
`Computer networks
`resources for use in forwarding network traffic. For example,
`different network links, such as Fast Ethernet, Asynchronous
`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
`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
`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-
`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
`
`(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., 077) that is asso-
`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
`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
`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
`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
`
`
`
`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),
`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
`
`5
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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-
`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
`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
`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 (Difi‘Serv) Model. With this
`solution, per flow state is offloaded to the edges of one or
`more Difi‘Serv networks, and packets corresponding to the
`flow are marked before entering the Difi‘Serv networks with
`appropriate DSCP. Within the Difi‘Serv networks, the RSVP
`messages are ignored and RSVP states are not maintained.
`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
`with the correct DSCP. Each device within the Difi‘Serv
`
`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 Difi‘Serv 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
`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,
`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,
`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.
`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
`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
`
`
`
`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. lAiC, 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. 6A7C 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 2187220 that have been
`
`configured to provide VoIP gateway support to other devices
`or entities, such as conventional analog telephone sets
`2227224, 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
`
`10
`
`15
`
`20
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`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-
`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-
`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/Intemet Protocol (TCP/IP)
`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.
`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 ofan
`intermediate network device in accordance with the present
`invention, such as router 208, which is the first hop router
`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
`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 4061).
`
`The traffic scheduler 404 includes a plurality of resources or
`services that are used by router 208 to forward packets. For
`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
`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
`allocation and reservation components. In the preferred
`embodiment, router 208 includes a RSVP entity or engine
`424. The RSVP engine 424 includes a RSVP message
`generator 426, a RSVP state machine engine 428, a session
`table 700, and an admission control entity 430. In accor-
`dance with the present invention, the RSVP engine 424 is
`further configured to include a flow analyzer 432. Disposed
`at (or otherwise accessible by) the flow analyzer 432 are one
`or more memory devices, such as heuristic store 434, which
`has been preprogrammed with one or more sets of heuristics
`for use in evaluating flow parameters associated with traffic
`flows. As described herein, the flow analyzer 432 processes
`reservation requests and assigns suitable PHBs to the traffic
`flows associated with those requests.
`Router 208 and, more specifically, flow analyzer 432
`comprises programmable processing elements (not shown),
`which may contain software program instructions pertaining
`to the methods of the present invention. Other computer
`
`
`
`US 7,225,271 B1
`
`7
`readable media may also be used to store the program
`instructions of the present invention.
`FIG. 5 is a highly schematic diagram of the output or
`outbound side 4061) of interface 406. Output interface 406!)
`includes a classification engine 502 that is in communicating
`relationship with the RSVP engine 424. Output interface
`406!) further includes a plurality of queues. In particular,
`interface 406!) preferably includes one or more priority
`queues, such as priority queue (PQ) 504, one or more
`reserved queue structures 506 that defines one or more
`reserved queues 506a7d, and one or more default queues
`508. Each queue 504, 506 and 508 is coupled to a queue
`selector/scheduler 510, which,
`in turn,
`is coupled to an
`output 512. Packets and/or frames to be forwarded from
`output interface 406!) are initially received by the classifi-
`cation engine 502 as indicated by arrow 514. Classification
`engine 502, based on information received from the RSVP
`engine 424 or from other entities, determines which queue
`504, 506 or 508 into which the received packet is to be
`buffered for transmission. The queue selector/scheduler 510
`retrieves packets from the queues 504, 506, 508 and pro-
`vides them to the output 512 for transmission on the network
`link associated with output
`interface 406b. Output 512
`includes transmitting circuitry for forwarding packets on the
`associated link, as indicated by arrow 516.
`Queue selector/scheduler 510 is preferably a multi, e.g.,
`two, level hierarchical scheduler. The top level in the hier-
`archy preferably uses a priority q