United States Patent
`[19]
`[11] Patent Number:
`6,046,980
`
`Packer
`[45] Date of Patent:
`Apr. 4, 2000
`
`USOO6046980A
`
`[54]
`
`[75]
`
`SYSTEM FOR MANAGING FLOW
`BANDWIDTH UTILIZATION AT NETWORK,
`TRANSPORT AND APPLICATION LAYERS
`IN STORE AND FORWARD NETWORK
`.4
`.
`,
`V
`Inventor‘ RObert L' PaCker’ hos oatos’ Lam
`
`..................... 395/600
`6/1996 Meske, Jr. et a1.
`5,530,852
`5,583,857 12/1996 Soumiya .............. 370/233
`
`3:33:22: 3;133; ganglia ----------- 23%;;
`,
`,
`aug er ..................................
`5,732,219
`3/1998 Blumer et a1.
`.
`5,748,629
`5/1998 Caldara ................................... 370/468
`5,764,645
`6/1998 Bcrnct
`..................................... 370/466
`
`[73] Assrgnee: Packeteer, Inc., Cupertino, Calif.
`
`Primary Examiner—Ajit Patel
`Assistant Examiner—Ricardo M. Pizarro
`
`[21] APPL N05 08/977,642
`[22]
`Filed'
`NOV. 24, 1997
`Related US. Application Data
`Provisional application No. 60/032,485, Dec. 9, 1996.
`[60]
`Int Cl 7
`G01R 31/08
`[511
`.....................................................
`.
`.
`.
`[52] U..S. Cl.
`............................................. 370/230, 370/229
`[58] Fleld of Search ..................................... 370/229, 230,
`370/231’ 232’ 235’ 465’ 466’ 468
`.
`References CltEd
`US. PATENT DOCUMENTS
`.
`?/1989 BMW?” ‘
`313;: gflimllat ’
`8/1995 Gagliardi et a1.
`4/1996 Sekihata et a1.
`
`[56]
`
`4’870’641
`2’32???
`5:442:630
`5,506,834
`
`Attorney, Agent, or Firm—Townsend and Townsend and
`Crew LLP; Kenneth R. Allen
`57
`ABSTRACT
`[
`]
`In a packet communication environment, a method is pro-
`Vided for classifying packet network flows for use in deter—
`mining a policy, or rule of assignment of a service level, and
`enforcing that policy by direct rate control. The method
`comprises applying individual instances of traffic objects,
`i.e., packet network flows to a classification model based on
`selectable information obtained from a plurality of layers of
`a multi-layered communication protocol, then mapping the
`flow to the defined traffic classes, which are arbitrarily
`assignable by an offline manager which creates the classi-
`fication. It is useful to note that the classification need not be
`a complete enumeration of the possible traffic.
`
`17 Claims, 20 Drawing Sheets
`
`370/54
`......................... 370/85
`
`,
`
`4|4
`
`‘06
`
`415
`
`4”
`
`PARTITION
`
`'5
`
`4|2
`
`BWPOOLS
`
`E
`
`4|?)
`
`BWPOOLS
`
`'-
`
`m
`
`Film
`i cm
`
`ouraouun
`
`F“
`
`4H
`
`INBOUND
`
`
`
`402
`
`TGB
`
`404
`
`404
`404
`
`408
`
`406
`
`I HOSTIHFO
`
`EX 1031 Page 1
`EX 1031 Page 1
`
`

`

`US. Patent
`
`Apr. 4, 2000
`
`Sheet 1 0f 20
`
`6,046,980
`
`:s
`"5
`
`'A
`‘I F‘
`‘5
`Q5 2;
`t2
`‘4
`
`"a“7
`N5
`
`5U
`
`
`
`OOOOOOOO
`
`
`00000000'
`
`00000000
`
`EX 1031 Page 2
`EX 1031 Page 2
`
`25
`
`NETWORKIF
`
`\
`\
`v
`
`45
`
`20
`
`32
`
`40
`
`40'
`
`NETWORKIF
`
`.n
`:3
`
`
`
`0OOOOOOOO
`
`
`
`
`
`0000000
`
`

`

`US. Patent
`
`Apr. 4, 2000
`
`Sheet 2 0f 20
`
`6,046,980
`
`55
`
`46
`
`'DATA OBJECT
`
`'
`
`WEB SERVER
`
`20
`OPERATING
`03 I
`
`SYSTEM
`
`SERVER
`
`TCP/IP
`
`42
`44 ' DATA OBJECT
`ll
`
`QUERY FROM USER N
`
`HTML OUTPUT T0 USER
`
`50
`
`5|
`
`.45
`
`13
`
`TE W25
`‘v’
`"‘
`
`42
`
`CLIENT
`
`6f4
`
`WEB
`BROWSER
`
`
`
`FIG:
`
`IB.
`
`EX 1031 Page 3
`EX 1031 Page 3
`
`

`

`US. Patent
`
`Apr. 4, 2000
`
`Sheet 3 0f 20
`
`6,046,980
`
`7|
`
`70
`
`SUNSPARC
`
`
`
`VAX6000
`
`FIGSICI
`
`(PRIORART)
`
`
`
`IBMCOMPATIBLE
`
`IBMR5/6000
`
`IBMAS/400
`
`EX 1031 Page 4
`EX 1031 Page 4
`
`

`

`US. Patent
`
`Apr. 4, 2000
`
`Sheet 4 0f 20
`
`6,046,980
`
`
`
`88
`86“
`mm]
`34
`IP AND ICMP
`
`ETHERNET, TOKEN RING, IEEE 802.5, x.25. SERIAL (SLIP)
`
`
`ATM, FRAME RELAY, csuA/co, PACKET svmcumc
`
`
`
`
`
`82
`
`so
`
`LEGEND
`
`88 SESSION/APPLICATION LAYER
`
`86 TRANSPORT LAYER
`84 NETWORK LAYER
`82 DATA LINK LAYER
`80 PHYSICAL LAYER
`
`FIG.
`
`ID.
`
`(PRIOR ART)
`
`EX 1031 Page 5
`EX 1031 Page 5
`
`

`

`US. Patent
`
`Apr. 4, 2000
`
`Sheet 5 0f 20
`
`6,046,980
`
`LOCAL TOP
`END POINT
`(SERVER)
`
`REMOTE TOP
`ENDPOINT
`
`
`
`
`
`
`
`
`NEGLIBLE
`LATENCY
`
`5"; 3f: "' 5f"
`
`
`LATENCY
`(INVARIANT)
`
`LOCATION
`
`FIG.
`
`IE.
`
`(PRIOR ART)
`
`EX 1031 Page 6
`EX 1031 Page 6
`
`

`

`US. Patent
`
`Apr. 4, 2000
`
`Sheet 6 0f 20
`
`6,046,980
`
`DEPT A
`lNSlDE HOST
`SUBNET A
`
`OUTSIDE
`PORT 20
`
`DEPT B
`INSIDE HOST
`SUBNET B
`
`
` DEFAULT
`
`212
`
`220
`
`EX 1031 Page 7
`EX 1031 Page 7
`
`

`

`US. Patent
`
`Apr. 4, 2000
`
`Sheet 7 0f 20
`
`6,046,980
`
`240
`
`203
`
`/
`
`ALLOCATE A TCLASS
`FOR THE TRAFFIC
`CLASS
`
`242
`
`244
`
`246
`
`
`
`SET UP THE A TRAF-
`FIG SPECIFICATION
`FOR THE NEVI T ,
`(SEE FIG. 20)
`
`INSERT THE NEW
`TGLASS INTO THE
`TREE (SEE FIG. 2E)
`
`REDISTRIBIITE
`BANDNIDTH
`(SEE FIG. 50)
`
`FIG 26‘.
`
`EX 1031 Page 8
`EX 1031 Page 8
`
`

`

`US. Patent
`
`Apr. 4, 2000
`
`Sheet 8 0f 20
`
`6,046,980
`
`TCLASSSETUPTSPEC
`
`205
`
`/
`
`250
`
`N0
`
`
`
`CURRENT TSPEC
`=RO0T
`
`252
`
`IS
`-
`THE NEWTSPEG
`@55 SPECIFIC TH
`CURRENITSPEC
`
`vss
`
`254
`
`00
`
`YES
`
`256
`
`CURRENT TSPEC= NEXT
`TSPEG m TCLASS
`
`253
`
`
`
`INSERT THE NEW TSPEC
`AFTER THE CURRENT
`
`TSPEC
`
`RETURN
`
`FIG: 20.
`
`EX 1031 Page 9
`EX 1031 Page 9
`
`

`

`US. Patent
`
`Apr. 4, 2000
`
`Sheet 9 0f 20
`
`6,046,980
`
`TGLASSINSERTGHILD
`
`/ 207
`
`260
`
`CURRENT SIBLING = FIRST
`
`SIBLING
`
`262
`
`‘ EW
`TCLASS LESS SPE-
`
`@c THAN CURRENT
`50ng cuss
`
`YES
`
`264
`
`LAST
`SIBLING?
`
`N0
`
`YES
`
`266
`
`CURRENT SIBLING=NEXT
`SIBLING
`
`SIBLING
`
`INSERT THE NEW TO '
`AFTER THE CURRENT
`
`268
`
`RETURN
`
`Fl6: 25.
`
`EX 1031 Page 10
`EX 1031 Page 10
`
`

`

`US. Patent
`
`Apr. 4,2000
`
`Sheet 10 M20
`
`6,046,980
`
`502
`
`304
`
`/ 30!
`
`TOP
`AUTOBAUD
`
`CL RSSIFIER
`
`DETECT
`FLOW
`SPEED
`
`FIND
`POLICY
`FOR
`FLOW
`
`306
`
`BUIOTHJ‘CR
`
`ALLOCATE
`BWIDTH
`
`NEW FLOW
`
`END FLOW
`
`DEAwLLOCATE
`
`B IDTH
`
`
`
`293
`300
`
`
`
`PROTOCOL
`FINITE STATE
`MACHINE
`
`TN PACKETS
`
`299
`
`FORWARD FLOW
`PACKET
`
`308
`
`SCHEDULER
`
`FORWARD TCP DATA
`WITHOUT DELAY
`
`OUT PACKETS
`
`FIG 3.
`
`EX 1031 Page 11
`EX 1031 Page 11
`
`

`

`US. Patent
`
`Apr. 4, 2000
`
`Sheet 11 0f 20
`
`6,046,980
`
`OM
`
`416
`
`4'5
`
`PARTITION
`
`PARTITION
`PARTITION
`
`4‘2
`
`BWPOOLS
`
`BWPOOLS
`
`41?
`
`POLICY
`
`413
`
`BWPOOLS
`
`BWPOOLS
`
`4l0
`
`FE
`NI
`
`ONTRONNO
`
`4"
`
`PM
`NO
`
`INRouNO
`
`
`
`402
`
`TCB
`
`404
`
`404
`
`404
`
`I
`
`406
`
`ll HOSTINFO
`
`FIG? 4A.
`
`408
`
`
`
`EX 1031 Page 12
`EX 1031 Page 12
`
`

`

`US. Patent
`
`Apr. 4, 2000
`
`Sheet 12 0f 20
`
`6,046,980
`
`3:2ESE2559:3312:5%.
`
`.was.
`
`“5:59893%.2253:
`
`
`
`Es.“Emma:egg3:_
`
`
`
`Bus
`
`2223NIiowe
`
`2»
`
`
`
`35.8.28.—
`
`at
`
`
`
`20:5:.mvwt
`
`”33...BEo!'3238552
`
`av
`
`23
`
`22:33.:
`
`oz:2.mm53325::m_
`
`PE:52.5
`
`EX 1031 Page 13
`EX 1031 Page 13
`
`
`

`

`US. Patent
`
`Apr. 4,2000
`
`Sheet 13 M20
`
`6,046,980
`
`/ 50I
`
`502
`
`504
`
`506
`.
`
`
`
`DETECT NETWORK
`SPEED FOR THIS FLOW
`
`DETERMINE TRAFFIC
`CLASS FOR THIS FLOW
`AND POLICY THEREFRON
`
`SET cm AND EIR BASED
`UPON POLICY AND
`
`
`
`INCOMINC FLOW SPEED
`
`ADD EIR DENANDED TO
`
`REDISTRIBUTE
`
`EIR
`
`SM
`
`SIS
`
`5I8
`
`ASSOCIATE FLOW
`
`TOTAL EIR DEMANDED
`EXCEEOED?
`
`
`
`WITH PARTITION
`
`ALLOCATE CIR AND EIR
`TO INITIAL FLOW TARGET
`RATE
`
`NO
`
`5|D
`
`PARTITION
`
`
`
`
`YES
`
`5l2
`
`APPLY
`ADMISSIONS
`
`POLICY
`
`FIG 5A.
`
`EX 1031 Page 14
`EX 1031 Page 14
`
`

`

`US. Patent
`
`Apr. 4,2000
`
`Sheet 14 M20
`
`6,046,980
`
`/503
`
`TERMlNATOR
`
`
` FORWARD
`IMMEDIATELY
`
`524
`
`
`
`
`
`
`SCHEDULE OUTPUT 0F
`FLOW PACKETS ON A
`
`MILLISECOND BOUNDRY
`BASED UPON TARGET
`
`RATE
`
`FIG: 5B.
`
`EX 1031 Page 15
`EX 1031 Page 15
`
`

`

`US. Patent
`
`Apr. 4, 2000
`
`Sheet 15 0f 20
`
`6,046,980
`
`START
`
`
`RESTORE GlR
`
`
`
`505
`
`/
`
`550
`
`532
`
`
`
`
`SUBTRACT EIR FOR
`THIS FLOW FROM
`TOTAL EIR OEMANOED
`
`
`
`
`REDISTRIBUTE
`
`EIR
`
`
`REMOVE FLOW
`FROM PARTITION
`
`
`
`
`FIG: 5C.
`
`534
`
`536
`
`EX 1031 Page 16
`EX 1031 Page 16
`
`

`

`US. Patent
`
`Apr. 4, 2000
`
`Sheet 16 0f 20
`
`6,046,980
`
`/507
`
`540
`
`
`
`
`
`
`
`
`CALCULATE DEMAND
`SATISFACTION NETRIC
`FOR THIS BANDWIDTH
`POOL
`
`
`
`
`
`DEMAND
`
`SATISFACTION
`
`CHAN CED?
`
`
`
`
`
`
`
`CALCULATE NEW EIR
`
`TOTAL AND NEW TARGET
`
`RATE FOR THIS GEAR
`
`
`
`FIG: 50
`
`EX 1031 Page 17
`EX 1031 Page 17
`
`

`

`US. Patent
`
`Apr. 4, 2000
`
`Sheet 17 0f 20
`
`6,046,980
`
`550
`
`/ 509
`
`MORE
`
`
`
`
`
`EXISTING RESERVED
`
`FLOVIS?
`
`
`
`
`AGGREGATE INDIVIDUAL
`
`
`
`FLOW DEMANDS INTO AN
`
`
`AGGREGATE RATE
`
`
`DEMAND IARD)
`
`
`
`NO
`
`554
`
`552
`
`EXTRAPOLATE UNRE-
`SERVED DEMAND (EUD)
`FROM INPUT RATE INTO
`PRIORITY BUCKETS
`
`
`
`556
`
`558
`
`560
`
`562
`
`COMBINE ARD AND
`
`EUD T0 ARRIVE AT TOTAL
`INSTANTANEOUS
`
`DEMAND (TD)
`
`
`
`
`
`COMPUTE SATISFACTION
`PERCENTAGE (SP) BASED
`ON TOTAL DEMAND AND
`AVAILABLE BANDVIIDTH
`RESOURCES IN PARTITION
`
`
`
`
`
`
`
`
`
`COMPUTE TARGET RATE
`FOR INDIVIDUAL RESERVED
`RATE BASED FLOWS
`
`
`
`
`
`
`
`
`COMPUTE TARGET RATE
`
`FOR PRIORITY BUCKETS
`
`FOR UNRESERVED FLOWS
`
`
`
`
`FIG? 55.
`
`EX 1031 Page 18
`EX 1031 Page 18
`
`

`

`US. Patent
`
`Apr. 4,2000
`
`Sheet 18 M20
`
`6,046,980
`
`TCLASS CHECK
`
`/5Il
`
`
`
` CHECK IF
`CHILD'S CLASS
`MATCHES FLOW
`
`
`
`570
`
`YES
`
`574
`
`APPLY TCLASSCHECK
`RECURSIVELY T0
`
`MATCHING CHILD
`
`
`ANOTHER
`CHILD?
`
`
`
`RETURN
`
`578
`
`.
`
`
` 9
`LEAF-
`'5 THE“
`
`A POLICY'
`
`
`no
`
`TO THIS FLOW
`
`APPLY THE
`POLICY OF THIS LEAF
`
`580
`
`
`333mm”?
`REN
`APPLY POLICY
`
`OF PARENT
`
`RETURN
`
`RETURN
`
`FIG 5F.
`
`EX 1031 Page 19
`EX 1031 Page 19
`
`

`

`US. Patent
`
`Apr. 4,2000
`
`Sheet 19 M20
`
`6,046,980
`
`/5|3
`
`SCALE TOLOAD
`
`
`
`
`
`SET GIR SCALED RATE
`
`
`BASED UPON CONNECTION
`
`
`SPEED FOR THIS GEAR
`
`
`(SEE FIG. SH)
`
`
`
`582
`
`584
`
`
`
`
`
`
`
`
`
`
`
`SET EIR SCALED RATE
`BASED UPON CONNECTION
`SPEED FOR THIS GEAR
`(SEE FIG SH)
`
`
`
`
`
`
`
`DETERMINE EXTRA EIR
`FROM LIMIT AND
`
`REMAINING EIR
`
`
`ALLOCATE LIMITS TO
`PRIORITY LEVELS IN
`
`
`COMPUTE A LIMIT FROM
`
`EITHER THE REMAINING
`EIR OR A TOTAL LIMIT,
`IF AVAILABLE
`
`586
`
`588
`
`590
`
`DESCENDING ORDER
`
`
`ANOTHER
`GEAR?
`
`TERMINATOR
`
`
`
`F/62 5G
`(STEP 506 or FIG. 5A)
`
`EX 1031 Page 20
`EX 1031 Page 20
`
`

`

`US. Patent
`
`Apr. 4,2000
`
`Sheet 20 M20
`
`6,046,980
`
`SCALERATE
`
`aw
`
`1”
`
`594
`
`593
`
`602
`
`592
`
`
`
`
`DETECTED "
`< BASE LIMIT?
`
`YES
`
`RETURN BASE
`
`no
`
`596
`
`
`
`RATE>LIIMIT<<
`
`
`YES
`
`no
`
`
`
`600
`
`
`“$3002
`
`
`
`N0
`
`604
`
`CONPUTE A PERCENTAGE
`'(DETECTED RATE < <7)
`
`/ TOTAL
`
`606
`
`RETURN BASE+ (((LIMIT
`- BASE) * PERCENTAGE)
`
`>> 7)
`
`RETURN
`
`F/G‘. 5H
`
`(STEPS 582 AND 584 or FIG 5c)
`
`EX 1031 Page 21
`EX 1031 Page 21
`
`

`

`6,046,980
`
`1
`SYSTEM FOR MANAGING FLOW
`BANDWIDTH UTILIZATION AT NETWORK,
`TRANSPORT AND APPLICATION LAYERS
`IN STORE AND FORWARD NETWORK
`
`CROSS-REFERENCE TO RELATED
`APPI .ICATIONS
`
`This application claims the benefit of US. Provisional
`Ser. No. 60/032,485 filed Dec. 9, 1996.
`The following related commonly-owned copending appli-
`cation is being filed concurrently and is hereby incorporated
`by reference in its entirety for all purposes: US. patent
`application Ser. No. 08/977,376, in the name of Robert L.
`Packer, entitled “Method for Managing Flow Bandwidth
`Utilization at Network, Transport and Application Layers,”.
`This application claims priority from the following US.
`Provisional Application, the disclosure of which, including
`all appendices and all attached documents, is incorporated
`by reference in its entirety for all purposes:
`US. Provisional Patent Application Ser. No. 60/032,485,
`Robert L. Packer, entitled, “Method for Managing Flow
`Bandwidth Utilization at Network, Transport and Applica-
`tion Layers in Store and Forward Network”, filed Dec. 9,
`1996.
`
`Further, this application makes reference to the following
`commonly owned US. patent Application, which is incor—
`porated herein in its entirety for all purposes:
`Copending US. patent application Ser. No. 08/762,828,
`in the name of Robert L. Packer, entitled “Method for Rapid
`Data Rate Detection in a Packet Communication Environ-
`ment Without Data Rate Supervision,” relates to a technique
`for automatically determining the data rate of a TCP con—
`nection.
`
`Further, this application makes reference to the following
`US. patent Application:
`Copending US. patent application Ser. No. 08/742,994,
`in the name of Robert L. Packer, entitled “Method for
`Explicit Data Rate Control
`in a Packet Communication
`Environment Without a Data Rate Supervision,” relates to a
`technique for automatically scheduling TCP packets for
`transmission.
`
`COPYRIGHT NOTICE
`
`A portion of the disclosure of this patent document
`contains material which is subject to copyright protection.
`The copyright owner has no objection to the facsimile
`reproduction by anyone of the patent document or the patent
`disclosure as it appears in the Patent and Trademark Office
`patent file or records, but otherwise reserves all copyright
`rights whatsoever.
`
`PAPER APPENDIX
`
`The following paper appendices are included herewith
`and incorporated by reference in their entirety for all pur-
`poses:
`
`Appendix A: Source code listing of bandwidth allocation
`processing an embodiment of the invention comprising
`ten (10) sheets;
`Appendix B: Source code listing of URL classification
`processing an embodiment of the invention comprising
`twenty-four (24) sheets;
`Appendix C: Source code listing of classification process-
`ing an embodiment of the invention comprising nine
`(9) sheets; and
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`2
`Appendix D: Source code listing of speed scaling pro-
`cessing an embodiment of the invention comprising ten
`(10) sheets.
`BACKGROUND OF THE INVENTION
`
`invention relates to digital packet
`This
`telecommunications, and particularly to management of
`network bandwidth based on information ascertainable from
`
`multiple layers of OSI network model. It is particularly
`useful
`in conjunction with data flow rate detection and
`control of a digitally-switched packet telecommunications
`environment normally not subject to data flow rate control.
`The ubiquitous TCP/IP protocol suite, which implements
`the world-wide data communication network environment
`called the Internet and is also used in private networks
`(Intranets), intentionally omits explicit supervisory function
`over the rate of data transport over the various media which
`comprise the network. While there are certain perceived
`advantages, this characteristic has the consequence of jux-
`taposing very high—speed packet flows and very low—speed
`packet flows in potential conflict for network resources,
`which results in inefficiencies. Certain pathological loading
`conditions can result in instability, overloading and data
`transfer stoppage. Therefore, it is desirable to provide some
`mechanism to optimize efficiency of data transfer while
`minimizing the risk of data loss. Early indication of the rate
`of data flow which can or must be supported is very useful.
`In fact, data flow rate capacity information is a key factor for
`use in resource allocation decisions.
`
`Internet/Intranet technology is based largely on the TCP/
`IP protocol suite, where IP, or Internet Protocol,
`is the
`network layer protocol and TCP, or Transmission Control
`Protocol, is the transport layer protocol. At the network
`level,
`IP provides a “datagram” delivery service. By
`contrast, TCP builds a transport
`level service over the
`datagram service to provide guaranteed, sequential delivery
`of a byte stream between two IP hosts.
`TCP flow control mechanisms operate exclusively at the
`end stations to limit the rate at which TCP endpoints emit
`data. However, TCP lacks explicit data rate control. In fact,
`there is heretofore no concept of coordination of data rates
`among multiple flows. The basic TCP flow control mecha-
`nism is a sliding window, superimposed on a range of bytes
`beyond the last explicitly-acknowledged byte. Its sliding
`operation limits the amount of unacknowledged transmis-
`sible data that a TCP endpoint can emit.
`Another flow control mechanism is a congestion window,
`which is a refinement of the sliding window scheme, which
`employs conservative expansion to fully utilize all of the
`allowable window. A component of this mechanism is
`sometimes referred to as “slow start”.
`
`The sliding window flow control mechanism works in
`conjunction with the Retransmit Timeout Mechanism
`(RTO), which is a timeout to prompt a retransmission of
`unacknowledged data. The timeout length is based on a
`running average of the Round Trip Time (RTT) for acknowl-
`edgment receipt, i.e. if an acknowledgment is not received
`within (typically) the smoothed RTT+4*mean deviation,
`thcn packet loss is inferred and the data pending acknowl-
`edgment is retransmitted.
`Data rate flow control mechanisms which are operative
`cnd-to-cnd without explicit data rate control draw a strong
`inference of congestion from packet loss (inferred, typically,
`by RTO). TCP end systems, for example, will ‘back-off’,
`i.e., inhibit transmission in increasing multiples of the base
`RTT average as a reaction to consecutive packet loss.
`
`EX 1031 Page 22
`EX 1031 Page 22
`
`

`

`6,046,980
`
`3
`Bandwidth Management in TCP/IP Networks
`Conventional bandwidth management
`in TCP/IP net-
`works is accomplished by a combination of TCP end sys-
`tems and routers which queue packets and discard packets
`when certain congestion thresholds are exceeded. The
`discarded, and therefore unacknowledged, packet serves as
`a feedback mechanism to the TCP transmitter. (TCP end
`systems are clients or servers running the TCP transport
`protocol, typically as part of their operating system.)
`The term “bandwidth management” is often used to refer
`to link level bandwidth management, e.g. multiple line
`support for Point to Point Protocol (PPP). Link level band-
`width management
`is essentially the process of keeping
`track of all traffic and deciding whether an additional dial
`line or ISDN channel should be opened or an extraneous one
`closed. The field of this invention is concerned with network
`level bandwidth management, i.e. policies to assign avail-
`able bandwidth from a single logical link to network flows.
`Routers support various queuing options. These options
`are generally intended to promote fairness and to provide a
`rough ability to partition and prioritize separate classes of
`traffic. Configuring these queuing options with any precision
`or without side effects is in fact very difficult, and in some
`cases, not possible. Seemingly simple things, such as the
`length of the queue, have a profound effect on traffic
`characteristics. Discarding packets as a feedback mechanism
`to TCP end systems may cause large, uneven delays per-
`ceptible to interactive users.
`In a copending US. patent application Ser. No. 08/742,
`994, in the name of Robert L. Packer, entitled “Method for
`Explicit Data Rate Control
`in a Packet Communication
`Environment Without Data Rate Supervision,” a technique
`for automatically scheduling TCP packets for transmission is
`disclosed. Furthermore, in a copending US. patent applica-
`tion Ser. No. 08/762,828, in the name of Robert L. Packer,
`entitled “Method for Rapid Data Rate Detection in a Packet
`Communication Environment Without Data Rate
`
`Supervision,” a technique for automatically determining the
`data rate of a TCP connection is disclosed. While these
`
`patent applications teach methods for solving problems
`associated with scheduling transmissions and for automati-
`cally determining a data flow rate on a TCP connection,
`respectively, there is no teaching in the prior art of methods
`for explicitly managing TCP packet
`traffic based upon
`information about the flow’s characteristics at multiple OSI
`protocol layers.
`is heretofore not known to
`Bandwidth management
`employ information contained in the packets corresponding
`to higher OSI protocol layers, even though such information
`may be extremely useful in making bandwidth allocation
`and management decisions.
`SUMMARY OF THE INVENTION
`
`10
`
`15
`
`30
`
`35
`
`40
`
`45
`
`50
`
`According to the invention, in a packet communication
`environment, a method is provided for classifying packet
`network flows for use in determining a policy, or rule of _
`assignment of a service level, and enforcing that policy by
`direct rate control. The method comprises applying iridi-
`vidual instances of trafiic objects, i.e., packet network flows
`to a classification model based on selectable information
`
`obtained from a plurality of layers of a multi-layered com-
`munication protocol, then mapping the flow to the defined
`traffic classes, which are arbitrarily assignable by an offline
`manager which creates the classification. It is useful to note
`that the classification need not be a complete enumeration of
`the possible traflic.
`In one aspect of the invention, bandwidth may be divided
`into arbitrary units, partitions,
`facilitating isolation and
`
`60
`
`65
`
`4
`allocation. Apartition is allocated for a class or set of traffic
`classes, carving the bandwidth of the associated link into
`multiple, independent pieces.
`In another aspect of the invention, available bandwidth
`may be allocated among flows according to a policy, which
`may include any combination of guaranteed information
`rate, excess information rate, the later allocated according to
`a priority.
`In another aspect of the invention, bandwidth resource
`needs of multiple heterogeneous requesting flows are rec-
`onciled with available bandwidth resources in accordance
`
`with policy of each flow based upon the flow’s class. Flows
`requiring reserved service with guaranteed information
`rates, excess information rates or unreserved service are
`reconciled with the available bandwidth resources continu-
`
`ously and automatically.
`In another aspect of the invention, providing an admis-
`sions policy which is invoked whenever a request for a
`bandwidth cannot be met consistently with other users of
`bandwidth.
`
`An advantage of network management techniques accord-
`ing to the present invention is that network managers need
`only define traffic classes which are of interest.
`A further advantage of the present invention is that traffic
`classes may include information such as a URI for web
`traffic.
`
`A yet filrther advantage of the present invention is that
`service levels may be defined in terms of explicit rates and
`may be scaled to a remote client or server’s network access
`rate. Different service levels may be specified for high speed
`and low speed users.
`A yet further advantage of the present invention is that
`service levels may be defined in terms of a guaranteed
`minimum service level.
`
`The mvention will be better understood upon reference to
`the following detailed description in connection with the
`accompanying drawings.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`FIG. 1A depicts a representative client server relationship
`in accordance with a particular embodiment of the inven—
`tion;
`FIG. 1B depicts a functional perspective of the represen-
`tative client server relationship in accordance with a par—
`ticular embodiment of the invention;
`FIG. 1C depicts a representative internetworking envi-
`ronment in accordance with a particular embodiment of the
`invention;
`FIG. 1D depicts a relationship diagram of the layers of the
`TCP/IP protocol suite;
`FIG. 1E depicts a two dimensional representation of
`timing relationships in the exchange of packets between
`hosts using the TCP protocol;
`FIGS. 2A—2B depict representative divisions of band-
`width according to a particular embodiment of the invention;
`FIGS. 2C—2E are flow charts depicting process steps
`according to a particular embodiment of the invention;
`FIG. 3 is a block diagram of a particular embodiment
`according to the invention;
`FIG. 4A is a block diagram of a data structure according
`to a particular embodiment of the invention;
`FIG. 4B is a block diagram of data structure according to
`a particular embodiment of the invention; and
`FIGS. 5A—5H are flow charts depicting process steps
`according to a particular embodiment of the invention.
`
`EX 1031 Page 23
`EX 1031 Page 23
`
`

`

`,—
`3
`DETAILED DESCRIPTION OF SPECIFIC
`EMBODIMENTS
`
`6,046,980
`
`6
`
`TABLE 1-continued
`
`LIST OF DEFINITIONAL TERMS
`
`A preferable embodiment of a flow bandwidth manage-
`ment system according to the invention has been reduced to
`practice and will be made available under the trade name
`“PacketShaperTM.”
`1.0 Introduction
`
`invention provides techniques to manage
`The present
`network bandwidth such as on a network access link
`between a local area network and a wide area network.
`
`Systems according to the present invention enable network
`managers to: define traffic classes; create policies which
`define service levels for traffic classes; and isolate band-
`width resources associated with certain traffic classes.
`
`Inbound as well as outbound traffic may be managed. Table
`1 provides a definitional list of terminology used herein.
`
`TABLE 1
`LIST OF DEFINITIONAL TERMS
`
`ADMISSIONS CONTROL
`
`CLASS SEARCH ORDER
`
`COMMITTED INFORMATION
`RATE (CIR)
`
`EXCEPTION
`
`EXCESS INFORMATION
`RATE (EIR)
`
`FLOW
`
`GUARANTEED
`INFORMATION RATE
`(GIR)
`
`HARD ISOLATION
`
`INSIDE
`
`ISOLATION
`
`OUTSIDE
`
`PARTITION
`
`POLICY
`POLICY INHERITANCE
`
`A policy invoked whenever a system
`according to the invention detects that a
`guaranteed information rate cannot
`be maintained. An admissions control
`policy is analogous to a busy signal
`in the telephone world.
`A search method based upon traversal
`of a N-ary tree data structure
`containing classes.
`A rate of data flow allocated to reserved
`service traffic for rate based bandwidth
`allocation for a committed bandwidth.
`Also called a guaranteed information
`rate (GIR).
`A class of traffic provided by the user
`which supersedes an automatically
`determined classification order.
`A rate of data flow allocated to reserved
`service traffic for rate based bandwidth
`a location for uncommitted bandwidth
`resources.
`A flow is a single instance of a traffic
`c ass. For example, all packets in a TCP
`connection belong to the same flow.
`As do all packets in a UDP session.
`A rate of data flow allocated to reserved
`service traffic for rate based bandwidth
`a location for a committed bandwidth.
`Also called a committed information
`rate (CIR).
`Hard isolation results from the creation
`0 an entirely separate logical channel
`for a designated set of classes.
`On the system side of an access link.
`Outside clients and servers are on the
`0 her side of the access link.
`Isolation is the degree that bandwidth
`resources are allocable to traffic classes.
`On the opposite side of an access link as
`viewed from the perspective of the
`system on which the software resides.
`Partition is an arbitrary unit of network
`resources.
`A rule for the assignment of a service
`level to a flow.
`A method for assigning policies to
`flows for which no policy exists in a
`hierarchical arrangement of policies.
`For example, if a flow is determined
`to be comprised of FTP packets for
`Host A, and no corresponding policy
`exists, a policy associated with a parent
`node, such as an FTP policy, may be
`located and used. See also POLICY
`SEARCH ORDER.
`
`
`
`5
`
`10
`
`15
`
`30
`
`35
`
`45
`
`50
`
`LALII
`
`60
`
`65
`
`POLICY BASED SCALING
`
`RESERVED SERVICE
`
`SCALFD RATE
`
`SERVICE LEVEL
`
`SOFT ISOLATION
`
`TARG ET RATE
`
`TRAFFIC CLASS
`
`UNRESERVED SERVICE
`
`An adjustment of a requested data rate
`for a particular flow based upon the
`policy associated with the flow and
`information about the flow’s potential
`rate.
`Reserved service is a service level
`intended for traflic which “bursts” or
`sends chunks of data. Reserved service
`is defined in terms of a scaled rate.
`Assignment of a data rate based upon
`detected speed.
`A service paradigm having a
`combination of characteristics defined
`by a network manager to handle a
`particular class of traffic. Service
`levels may be designated as either
`reserved or unreserved.
`Restricting GIR allocated for traffic
`classes in a partition.
`A target rate is a combination of a
`guaranteed rate and an excess rate.
`Target rate is a policy-based paradigm.
`Excess rate is allocated by systems
`according to the invention from
`bandwidth that is not consumed by
`reserved service. Policies will demand
`excess rate at a given priority and
`systems according to the invention
`satisfy this demand by a priority level.
`All traffic between a client and a server
`endpoints. A single instance of a traffic
`class is called a flow. Traffic classes
`have properties or class attributes
`such as, directionality, which is the
`property of traffic to be flowing
`inbound or outbound.
`Unreserved service is a service level
`defined in terms of priority in which
`no reservation of bandwidth is made.
`
`1.1 Hardware Overview
`
`The method for [low bandwidth management in a packet
`oriented telecommunications network environment of the
`present invention is implemented in the C programming
`language and is operational on a computer system such as
`shown in FIG. 1A. This invention may be implemented in a
`client-server environment, but a client-server environment is
`not essential. This figure shows a conventional client-server
`computer system which includes a server 20 and numerous
`clients, one of which is shown as client 25. The use of the
`term “server” is used in the context of the invention, wherein
`the server receives queries from (typically remote) clients,
`does substantially all the processing necessary to formulate
`responses to the queries, and provides these responses to the
`clients. However, server 20 may itself act in the capacity of
`a client when it accesses remote databases located at another
`
`node acting as a database server.
`The hardware configurations are in general standard and
`will be described only briefly. In accordance with known
`practice, server 20 includes one or more processors 30 which
`communicate with a number of peripheral devices via a bus
`subsystem 32. These peripheral devices typically include a
`storage subsystem 35, comprised of a memory subsystem
`35a and a file storage subsystem 35b holding computer
`programs (e.g., code or instructions) and data, a set of user
`interface input and output devices 37, and an interface to
`outside networks, which may employ Ethernet, Token Ring,
`ATM, IEEE 802.3, ITU X25, Serial Link Internet Protocol
`(SLIP) or the public switched telephone network. This
`interface is shown schematically as a “Network Interface”
`
`EX 1031 Page 24
`EX 1031 Page 24
`
`

`

`6,046,980
`
`7
`block 40. It is coupled to corresponding interface devices in
`client computers via a network connection 45.
`Client 25 has the same general configuration, although
`typically with less storage and processing capability. Thus,
`while the client computer could be a terminal or a low-end
`personal computer, the server computer is generally a high-
`end workstation or mainframe, such as a SUN SPARC
`server. Corresponding elements and subsystems in the client
`computer are shown with corresponding, but primed, refer-
`ence numerals.
`
`Bus subsystem 32 is shown schematically as a single bus,
`but a typical system has a number of buses such as a local
`bus and one or more expansion buses (e.g.,ADB, SCSI, ISA,
`EISA, MCA, NuBus, or PCI), as well as serial and parallel
`ports.
`Network connections are usually established through a
`device such as a network adapter on one of these expansion
`buses or a modem on a serial port. The client computer may
`be a desktop system or a portable system.
`The user interacts with the system using interface devices
`37' (or devices 37 in a standalone system). For example,
`client queries are entered via a keyboard, communicated to
`client processor 30', and thence to modem or network
`interface 40' over bus subsystem 32'. The query is then
`communicated to server 20 via network connection 45.
`
`Similarly, results of the query are communicated from the
`server to the client via network connection 45 for output on
`one of devices 37' (say a display or a printer), or may be
`stored on storage subsystem 35'.
`FIG. 1B is a functional diagram of a computer system
`such as that of FIG. 1A. FIG. 1B depicts a server 20, and a
`representative client 25 of a plurality of clients which may
`interact with the server 20 via the Internet 45 or any other
`communications method. Blocks to the right of the server
`are indicative of the processing steps and functions which
`occur in the server’s program and data storage indicated by
`blocks 35a and 35b in FIG. 1A. ATCP/IP “stac ” 44 works
`in conjunction with Operating System 42 to communicate
`with processes over a network or serial connection attaching
`Server to Internet 45. Web server software 46 executes
`
`concurrently and cooperatively with other processes in
`server 20 to make data objects 50 and 51 available to
`requesting clients. A Common Gateway Interface (CGI)
`script 55 enables information from user clients to be acted
`upon by web server 46, or other processes within server 20.
`Responses to client queries may be returned to the clients in
`the form of a Hypertext Markup Language (HTML) docu-
`ment outputs which are then communicated via Internet 45
`back to the user.
`
`Client 25 in FIG. 1B possesses software implementing
`functional processes operatively disposed in its program and
`data storage as indicated by block 3511' in FIG. 1A. TCP/IP
`stack 44', works in conjunction with Operating System 42' to
`communicate with processes over a network or serial con-
`nection attaching Client 25 to Internet 45. Software imple-
`menting the function of a web browser 46’ executes con-
`currently and cooperatively with other processes in client 25
`to make requests of server 20 for data objects 50 and 51. The
`user of the client may interact via the web browser 46' to
`make such queries of the server 20 via Internet 45 and to
`view responses from the server 20 via Internet 45 on the web
`browser 46'.
`1.2 Network Overview
`
`FIG. 1C is illustrative of the internetworking of a plurality
`of clients such as client 25 of FIGS. 1A and 1B and a
`
`plurality of servers such as server 20 of FIGS. 1A and 1B as
`
`8
`In FIG. 1C, network 70 is an
`described herein above.
`example of a Token Ring or frame oriented network. Net-
`work 70 links host 71, such as an I