11111111111111111111111111fIllloRI11011111111111111111111111111111
`
`US006046980A
`11
`Patent Number:
`[n] Patent Number: (cid:9)
`(45) Date of Patent:
`[45] Date of Patent: (cid:9)
`
`6,046,980
`6,046,980
`Apr. 4, 2000
`Apr. 4, 2000
`
` 395/600
`6/1996 Meske, Jr. et al. (cid:9)
`5,530,852
`5,530,852 6/1996 Meske, Jr. et al. ..................... 395/600
`5,583,857 12/1996 Soumiya (cid:9)
` 370/233
`5,583,857 12/1996 Soumiya ........
`... 370/233
`59. E. E.
`38.
`5,694,548 12/1997 Baugher (cid:9)
` 370/231
`5,701,465 12/1997 Baugher (cid:9)
` 370/468
`2 : - -a-
`allSile . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
`5,732.219 3/1998 Blumer et al..
`5,732,219
`3/1998 Blumer et al. .
` 370/468
`5,748,629
`5/1998 Caldara (cid:9)
`5,748,629 5/1998 Caldara ................................... 370/468
`5,764,645 6/1998 Bernet ..................................... 370/466
`5,764,645
`6/1998 Bernet (cid:9)
` 370/466
`Primary Examiner Ajit Patel
`Primary Examiner—Ajit Patel
`ASSistant Examiner-Ricardo M. Pizarro
`Assistant Examiner—Ricardo M. Pizarro
`Attorney, Agent, or Firm Townsend and Townsend and
`Attorney, Agent, or Firm—Townsend and Townsend and
`Crew LLP; Kenneth R. Allen
`Crew LLP; Kenneth R. Allen
`57
`ABSTRACT
`[57] (cid:9)
`ABSTRACT
`57
`In a packet communication environment, a method is pro
`In a packet communication environment, a method is pro-
`Vided for classifying packet network flows for use in deter
`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
`enforcing that policy by direct rate control. The method
`comprises applying individual instances of traffic objects,
`comprises applying individual instances of traffic objects,
`i.e., packet network flows to a classification model based on
`i.e., packet network flows to a classification model based on
`selectable information obtained from a plurality of layers of
`selectable information obtained from a plurality of layers of
`a multi-layered communication protocol, then mapping the
`a multi-layered communication protocol, then mapping the
`flow to the defined traffic classes, which are arbitrarily
`flow to the defined traffic classes, which are arbitrarily
`assignable by an offline manager which creates the classi
`assignable by an offline manager which creates the classi-
`fication. It is useful to note that the classification need not be
`fication. It is useful to note that the classification need not be
`a complete enumeration of the possible traffic.
`a complete enumeration of the possible traffic.
`
`mining a policy, or rule of assignment of a Service level, and
`
`17 Claims, 20 Drawing Sheets
`17 Claims, 20 Drawing Sheets
`
`United States Patent [19]
`United States Patent (19)
`Packer (cid:9)
`Packer
`
`54 SYSTEM FOR MANAGING FLOW
`[54] SYSTEM FOR MANAGING FLOW
`BANDWIDTH UTILIZATION AT NETWORK,
`BANDWIDTH UTILIZATION AT NETWORK,
`TRANSPORT AND APPLICATION LAYERS
`TRANSPORT AND APPLICATION LAYERS
`IN STORE AND FORWARD NETWORK
`INSTORE AND FORWARD NETWORK
`
`[75] Inventor: Robert L. Packer, Los Gatos, Calif.
`75 Inventor: Robert L. Packer, Los Gatos, Calif.
`[73] Assignee: Packeteer, Inc., Cupertino, Calif.
`73 Assignee: Packeteer, Inc., Cupertino, Calif.
`
`[21] Appl. No.: 08/977,642
`21 Appl. No.: 08/977,642
`22 Filed:
`Nov. 24, 1997
`[22] Filed: (cid:9)
`Nov. 24, 1997
`
`O
`
`-1 - O
`
`- - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - - -
`
`Related U.S. Application Data
`Related U.S. Application Data
`60 Provisional application No. 60/032,485, Dec. 9, 1996.
`[60] Provisional application No. 60/032,485, Dec. 9, 1996.
`51 Int. CI.7
`G01R 31/08
`[51] Int. C1.7 (cid:9)
` GO1R 31/08
`[52] U.S. Cl. (cid:9)
` 370/230; 370/229
`52) U.S. Cl. ............................................. 370/230; 370/229
`[58] Field of Search (cid:9)
` 370/229, 230,
`58 Field of Search ..................................... 370/229, 230,
`370/231, 232, 235, 465, 466, 468
`370/231, 232, 235, 465, 466, 468
`References Cited
`References Cited
`U.S. PATENT DOCUMENTS
`U.S. PATENT DOCUMENTS
`4,870,641 9/1989 Pattavina .
`4870,641 9/1989 Pattavina.
`5,315,586
`5/1994 Charvillat .
`370/54
`E. SE Savilla
` 370/54
`5,347,511 9/1994 Gun (cid:9)
`5.442,630 8/1995 Gagliardiet al... 370/85
` 370/85
`5,442,630 8/1995 Gagliardi et al. (cid:9)
`5,506,834 4/1996 Sekihata et al..
`5,506,834 4/1996 Sekihata et al. .
`
`[56] (cid:9)
`56)
`
`44
`/414
`
`POLICY
`
`(cid:9)(416
`46
`
`PARTITION
`
`PARTITION
`
`POLICY
`
`45
`415
`
`PARTITION
`
`PARTITION
`
`PARTITION A.
`
`(cid:9)(.417
`47
`
`POLICY
`—1 POLICY
`
`r 413
`43
`BWPOOLS
`BWPOOLS
`BWPOOLS
`
`r 412
`42
`WOOLS
`BWPOOLS
`BWPOOLS
`
`40
` 410
`E.
`GEAR 1
`GEAR
`GEAR
`GEAR
`
`OUBOUND
`
`OUTBOUND
`
`4.
`411
`
`GEAR
`GEAR
`GEAR
`
`NBOUND
`INBOUND
`
`
`
`402
`(cid:9) 402
`
`(cid:9) r 404 404
`404
`404
`TCB
`TCB
`404
`404
`
`CONN
`HASH
`TABLE
`
`,408
`408
`
`
`
`406
`/ 406
`
`HOSTINFO
`
`HOSTINFO
`HOSTINFO
`HOST INFO
`
`HOST
`HASH
`TABLE
`
`NOAC Ex. 1009 Page 1
`
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 1 of 20 (cid:9)
`Sheet 1 of 20
`
`6,046,980
`6,046,980
`
`G?y
`
`
`
`
`
`
`
`
`
`EIF-1111•
`
`1.L.
`NC
`CC
`0
`M
`1--
`LA-1
`Z
`
`NBC
`CC
`4=0
`3
`1—
`LIJ
`Z
`
`.......11m
`
`me.
`
`1
`
`i (cid:9)
`
`WM (cid:9)
`
`47=1
`PC)
`N....000000000
`0
`O
`0
`O
`0 = 0
`0
`(cid:9) so. 0 (cid:9)
`cL. (cid:9)
`0
`C.
`o
` 0
`0 (cid:9)
`
`O
`0
`000000000
`
`O
`M
``000000000
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`0
`000000000
`
`=
`C:1-
`C...,
`
`e&t
`
`
`(18W 8018d)
`
`
`'%/ 39/-/
`
`NOAC Ex. 1009 Page 2
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 2 of 20
`Sheet 2 of 20 (cid:9)
`
`6,046,980
`6,046,980
`
`9.
`Siss-
`
`SERVER
`
`WEB SERVER
`WEB SERVER
`OPERATING
`SYSTEM
`
`OPERATING
`SYSTEM
`
`55
`55
`
`46
`46
`
`/. OBJECT Z-50
`
` an
`/
`,////DATAOBJECT/,4'-"
`I
`
`42
`
`42
`44
`44
` /
`
`•
`
`\ (cid:9)
`I
`5I
`DATA OBJECTM-5
`DATA OBJECT
`N
`
`QUERY FROM USER
`QUERY FROM USER I/
`
`HTML OUTPUT TO USER
`HTML OUTPUT TO USER
`
`45
`
`(O"
`
`I 1
`
`19s
`
`C E N T
`CLIENT
`
`44'
`
`42
`
`2
`42'
`
`46
`6
`/ 46'
`/
`
`OPERATING
`SYSTEM
`SYSTEM
`
`WEB
`WEB
`BROWSER
`BROWSER
`
`FIG. 18.
`A/6 /A
`
`NOAC Ex. 1009 Page 3
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent (cid:9)
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 3 of 20 (cid:9)
`Sheet 3 of 20
`
`6,046,980
`6,046,980
`
`01
`
`(
`
`Ili
`0009 XWM
`
`e---,
`-,......."
`
`CC
`LLI
`I—
`CD
`CC
`
`
`
`I:2.3
`CO
`I-
`0-.
`=
`CD
`CC
`M
`CO
`
`Oil
`
`0
`
`LLI
`Z.0 —
`C:I CC
`I--
`
`CC
`CO
`
`CO
`
`13
`
`MI
`
`a
`
`0
`
`NOAC Ex. 1009 Page 4
`
`

`

`U.S. Patent (cid:9)
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 4 of 20
`Sheet 4 of 20 (cid:9)
`
`6,046,980
`6,046,980
`
`
`
`TELNET HTTP
`TCP
`TCP
`
`SNMP
`
`RPC
`UDP
`UDP
`
`88
`88-- FTP
`86--
`86---
`84
`84---
`
`82
`82
`80
`80
`
`RIP
`IP AND ICMP
`RIP
`IP AND ICMP
`ETHERNET, TOKENRING, IEEE 802.3, X.25, SERIAL (SLIP)
`ETHERNET, TOKEN RING, IEEE 802.3, X.25, SERIAL (SLIP)
`ATM, FRAME RELAY, CSMA/CD, PACKET SWITCHING
`ATM, FRAME RELAY, CSMA/CD, PACKET SWITCHING
`LEGEND
`LEGEND
`88 SESSION/APPLICATION LAYER
`88 SESSION/APPLICATION LAYER
`86 TRANSPORT LAYER
`86 TRANSPORT LAYER
`84 NETWORK LAYER
`84 NETWORK LAYER
`82 DATA LINK LAYER
`82 DATA LINK LAYER
`80 PHYSICAL LAYER
`80 PHYSICAL LAYER
`
`
`
`ARP
`ARP
`
`FIG. ID.
`A/G /D
`(PRIOR ART)
`(PRIOR ART)
`
`NOAC Ex. 1009 Page 5
`
`

`

`U.S. Patent (cid:9)
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 5 of 20
`Sheet 5 of 20 (cid:9)
`
`6,046,980
`6,046,980
`
`
`
`
`
`
`
`
`
`TIME
`
`
`
`
`
`LOCAL TOP
`LOCAL TCP
`END POINT
`END POINT
`(SERVER)
`(SERVER)
`
`REMOTE TCP
`REMOTE TOP
`ENDPOINT
`END POINT
`
`NEGLIBLE
`NEGLIBLE
`LATENCY
`LATENCY
`St. St. o Sty
`St/ Stx+Stw
`
`I St w
`
`i
`LATENCY
`LATENCY
`(INVARLANT)
`(INVARIANT)
`i
`
`LOCATION
`LOCATION
`
`FIG /E.
`A/6 /A.
`(PRIOR ART)
`(PRIOR ART)
`
`NOAC Ex. 1009 Page 6
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 6 of 20
`Sheet 6 of 20
`
`6,046,980
`6,046,980
`
`- 20
`/. 201
`206
`(cid:9)f 206
`
`208
`(cid:9)`208
`
`(cid:9)j210
`20
`
`22
`(cid:9)f 212
`
`
`
`(cid:9)/ 202
`
`DEPT A
`DEPT A
`INSIDE HOST
` (cid:9)
`INSIDE HOST
`.1
`SUBNET A
`SUBNET A
`
`FTP
`OUTSIDE
`OUTSIDE
`PORT 20
`PORT 20
`
`/204
`
`DEPT B
`DEPT B
`INSIDE HOS
`INSIDE HOST
`SUBNET 8
`SUBNET B
`
`(cid:9)1205
`
`DEFAULT
`
`WEB
`
`FTP
`
`WEB
`
`F/G. 2A.
`
`
`
`220
`/220
`
`203
`203
`226 1.
`/226
`
`WEB
`
`TOP
`
`224
`
`DEPT A
`
`DEPT B
`
`DEPT A
`
`/• 225
`
`1 DEPT B
`
`DEFAULT
`DEFAULT
`
`228
`(cid:9) 228
`
`230
`(cid:9) i 230
`
`232
`(cid:9) 1232
`
`F/G. 28
`
`NOAC Ex. 1009 Page 7
`
`(cid:9)
`(cid:9)
`(cid:9)
`

`

`U.S. Patent
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 7 of 20
`Sheet 7 of 20 (cid:9)
`
`6,046,980
`6,046,980
`
`(240
`240
`
`203 /
`(203
`
`
`
`
`
`
`
`ALLOCATE ATCLASS
`ALLOCATE A TCLASS
`FOR THE TRAFFIC
`FOR THE TRAFFIC
`CLASS
`CLASS
`
`C 242
`242
`I
`SET UP THE ATRAF
`SET UP THE A TRAF-
`FIC SPECIFICATION
`FIC SPECIFICATION
`FOR THE NEW TCL
`FOR THE NEW TCLASS
`(SEE FIG. 20)
`(SEE FIG. 20)
`
`c 244
`244
`
`INSERT THE NEW
`INSERT THE NEW
`TCLASS INTO THE
`TCLASS INTO THE
`TREE (SEE FIG. 2E)
`TREE (SEE FIG. 2E)
`
`
`
`II
`
`
`
`i 246
`246
`
`REDISTRIBUTE
`REDISTRIBUTE
`BANOWOTH
`BANDWIDTH
`(SEE FIG. 50)
`(SEE FIG. 50)
`
`I
`
`RETURN
`( RETURN )
`
`A/G 2C
`FIG 2C
`
`NOAC Ex. 1009 Page 8
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 8 of 20
`Sheet 8 of 20 (cid:9)
`
`6,046,980
`6,046,980
`
`205
`/ 205
`A?
`
`TCLASSSETUPTSPEC
`
`ETCLASSSETUPTSPEC)
`
`250
`/ 250
`
`
`
`I
`
`CURRENT TSPEC
`CURRENT TSPEC
`= ROOT
`=ROOT
`
`252
`252
`SN
`IS
`TENEWSPECS N0
`THE NEW TSPEC
`NO
`<GS SPECIFIC TH
`LESS SPECIFIC TH
`CURRENTSPEC
`CURRENT TSPEC
`YES
`YES
`254
`
`YES
`YES
`
`NO
`NO
`
`256
`(256
`
`
`
`CURRENT SPEC=NEXT
`CURRENT TSPEC. NEXT
`TSPEC IN TCLASS
`TSPEC IN TCLASS
`
`258
`, 258
`
`INSERT THE NEW TSPEC
`INSERT THE NEW TSPEC
`AFTER THE CURRENT
`AFTER THE CURRENT
`TSPEC
`TSPEC
`
`RETURN
`( RETURN )
`
`A/G 2A
`F/G. 20.
`
`NOAC Ex. 1009 Page 9
`
`(cid:9)
`

`

`6,046,980
`6,046,980
`r 207
`207
`A?
`
`U.S. Patent (cid:9)
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 9 of 20
`Sheet 9 of 20 (cid:9)
`
`TCLASSINSERTCHILD
`ICLASSINSERTCHIL-D)
`
`260
`i260
`
`t (cid:9)
`CURRENT SIBLINGs FIRST
`CURRENT SIBLING= FIRST
`SBLNG
`SIBLING
`
`262
`262
`NEW
`EW
`TCLASSESS SPE
`< CLASS LESS SPE- (cid:9)
`<E THAN CURRENT
`IFIC THAN CURREN
`SLIN CASS
`SIBLING CLASS
`YES
`YES
`264
`264
`
`NO
`NO
`
`LAST
`SIBLENG 2
`
`YES
`
`NO
`NO
`I (cid:9)
`
`266
`/266
`
`
`
`CURRENT SIBLINC=NEXT
`CURRENT SIBLING=NEXT
`SIBLNG
`SIBLING
`
`268
`/ 268
`
`INSERT THE NEW TCLA
`INSERT THE NEW TCLASS
`AFTER THE CURRENT
`AFTER THE CURRENT
`SIBLING
`SIBLING
`
`RETURN
`( RETURN )
`
`A/6 2A.
`F/G. 2E
`
`NOAC Ex. 1009 Page 10
`
`

`

`U.S. Patent (cid:9)
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 10 0f 20
`Sheet 10 of 20 (cid:9)
`
`6,046,980
`6,046,980
`
`302
`302 (cid:9)
`
`304
`/304
`
`/ 301
`M1 30
`
`TCP
`C TCP
`AUTOBAUD
`AUTOBAUD
`•
`
`DETECT
`DETECT
`FLOW
`FLOW
`SPEED
`SPEED
`
`CLASSIFIER
`(-CLASSIFIER.)
`\. (cid:9)
`
`I
`FIND
`FIND
`POLICY
`POLICY
`FOR
`FOR
`FLOW
`FLOW
`
`306
`/306
`BWIDTHMGR
`(cid:9)< BWIDTLAIGR .)
`I
`
`ALLOCATE
`ALLOCATE
`BWOTH
`BWIDTH
`
`e300
`300
`NEW FOW
`(cid:9)(NEW FLOW ) (cid:9)
`
`
`
`
`298
`/ 298
`
`END FLOW
`END FLOW)
`\
`
`DEALLOCATE
`DEALLOCATE
`BWIDTH
`BWOTH
`
`t299
`299
`FORWARD FLOW
`FORWARD FLOW
`
`PACKET
`PACKET
`
`308
`308
`
`
`
`SCHEDULER
`( SCHEDULER
`
`[
`FORWARD TCP DATA
`FORWARD TCP DATA
`WITHOUT DELAY
`WITHOUT DELAY (cid:9)
`
`|
`
`1
`
`OUT PACKETS
`OUT PACKETS
`
`|
`
`r PROTOCOL
`PROTOCOL
`(cid:9)-I (cid:9)
`FINITE STATE
`FINITE STATE
`MACHINE
`MACHINE
`
`NPACKETS
`IN PACKETS
`
`A/G 3.
`F/G. 3.
`
`NOAC Ex. 1009 Page 11
`
`(cid:9)
`(cid:9)
`

`

`U.S. Patent
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000
`
`Sheet 11 of 20
`Sheet 11 of 20
`
`6,046,980
`6,046,980
`
`44
`/414
`
`46
`(416
`
`POLICY
`
`A.
`
`PARTITION
`PARTITION
`
`..---1—"" (cid:9)
`
`POLICY
`
`
`
`42
`/412
`BWPOOLS
`BWPOOLS
`BWPOOLS
`BWPOOLS
`
`/415
`45
`
`PARTITION
`
`PARTITION
`
`A. PARTTON
`
`47
`(cid:9)1417
`
`POLICY
`
`POLICY
`POLICY
`
`(413
`43
`,.. BWPOOLS
`BWPOOLS
`BWPOOLS
`BWPOOLS
`
`40
`I /410
`E.
`GEAR
`GEAR
`GEAR
`
`OUTBOUND
`
`OUTBOUND
`
`E. " He
`
`(cid:9)(411
`4.
`
`GEAR
`GEAR 1
`GEAR
`
`INBOUND
`
`NBOUND
`
`
`
`(cid:9) 402
`402
`
`404
`y f404
`404
`
`4 04
`404
`404
`
`TCB
`TCB (cid:9)
`
`
`CONN
`HASH
`TABLE
`
`1408
`408
`
`HOST
`HASH
`TABLE
`
`406
`HOSTINM / 406
`HOST1NFO I
`HOSTINFO
`HOSTINFO In. (cid:9)
`
`A/G 44.
`F/G. 4A.
`
`NOAC Ex. 1009 Page 12
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000
`
`Sheet 12 of 20 (cid:9)
`Sheet 12 of 20
`
`6,046,980
`6,046,980
`
`C,
`L.L.1
`C.D
`CO
`>-
`
`CC
`O
`CC
`0-
`
`| || ~ ~ ~ ||0d31S
`
`}' SJIWN
`
`
`
`O
`
`0
`C:3
`CD
`
`
`CZ) CD CD 0 4=1
`CZ/ 0 IM 0 CM C3
`CV
`--•
`
`LU
`
`II
`LAJ
`1.1.1
`"cC
`CC
`e=1
`C.D 1_1"
`4C CC
`O
`LU 1.1•1
`0 CC 0
`LIJ C-*
`CD
`"C
`
`(08W)
`
`ti
`
`
`
`(JNWW30I DOTT
`
`
`0 ,:
`...=, dc=, CD ez,
`CD
`CD
`
`
`
`0NWW30 TW10||
`
`(01)
`
`O
`
`CD
`CZO
`0)
`nr)
`
`3000
`3000
`000
`
`CD
`C=1
`CD
`C=:$
`0
`C=3
`
`ro nt- 5
`
`2000
`
`C=.1
`C:)
`CZ/
`
`ti
`
`O
`
`O CD
`
`O CD
`O
`O
`
`er- CO
`‘2"
`
`O
`
`00
`00
`00
`0 0
`0 0 C=1
`40
`NN NN
`
`0 C3 CM LLJ
`'CC (cid:9)
`Ls- ":C
`CC
`CI- c:$
`1—
`
`-J a_ w
`crj CD
`=
`Be (cid:9)
`szn (cid:9)
`CC
`Ace
`-J (cid:9)
`
`O
`
`a. a. Fr ,,,
`
`a.
`cz
`Fr ),
`
`3000
`
`3000
`000
`
`a, a,
`c=. :. 2 3
`R
`
`c„ c=
`
`'Cr
`
`ti
`
`2000
`2000
`2000
`
`CD
`
`O
`
`CD . CD 0 c= CD CD
`
`21
`
`NOAC Ex. 1009 Page 13
`
`

`

`U.S. Patent
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 13 of 20
`Sheet 13 of 20
`
`6,046,980
`6,046,980
`50
`/501
`502
`,- 502
`
`DETECT NETWORK
`DETECT NETWORK
`SPEED FOR THIS FLOW
`SPEED FOR THIS FLOW
`
`504
`(cid:9) 504
`
`DETERMINE TRAFFIC
`DETERMINE TRAFFIC
`CLASS FOR THIS FLOW
`CLASS FOR THIS FLOW
`AND POLICY THEREFROM
`AND POLICY THEREFROM
`
`i
`SET GIR ANDEIRBASED50
`r 506
`SET GIR AND EIR BASED
`UPON POLICY AND
`UPON POLICY AND
`INCOMING FLOW SPEED
`INCOMING FLOW SPEED
`
`i
`'508
`ALLOCATE GIR ANDER
`ALLOCATE GIR AND EIR
`TO INITIAL FLOW TARGET
`TO INITIAL FLOW TARGET
`RATE
`RATE
`
`54
`5I4
`
`ADD EIR DEMANDED TO
`ADD EIR DEMANDED TO
`TOTAL ER DEMANDED
`TOTAL EIR DEMANDED
`
`
`
`Ii (cid:9)
`
`56
`r5I6
`
`REDISTRIBUTE
`REDISTRIBUTE
`EIR
`EIR
`
`58
`f 518
`
`ASSOCATE FOW
`ASSOCIATE FLOW
`WITH PARTITION
`WITH PARTITION
`
`
`
`
`
`50
`
`PARTITION
`EXCEEDED2
`
`YES
`
`52
`
`APPLY
`APPLY
`ADMISSIONS
`ADMISSIONS
`POLICY
`POLICY
`
`C E211...)
`
`( END )
`
`NO
`NO
`
`
`
`
`
`F/6 5A.
`A/G 64.
`
`NOAC Ex. 1009 Page 14
`
`(cid:9)
`

`

`U.S. Patent (cid:9)
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 14 of 20
`Sheet 14 of 20 (cid:9)
`
`6,046,980
`6,046,980
`
`TERMINATOR
`( TERMINATOR )
`
`/503
`503
`
`524
`524
`
`NO
`
`
`
`FORWARD
`FORWARD
`IMMEDIATELY
`IMMEDIATELY
`
`END
`
`
`
`YES
`
`(522
`1 (cid:9)
`SCHEDULE OUTPUT OF
`SCHEDULE OUTPUT OF
`FLOWPACKETS ON A
`FLOW PACKETS ON A
`MILLISECOND BOUNDRY
`MILLISECOND BOUNDRY
`BASED UPON TARGET
`BASED UPON TARGET
`RATE
`RATE
`
`( END )
`
`FIG. 58
`A/6 5A
`
`NOAC Ex. 1009 Page 15
`
`

`

`U.S. Patent
`U.S. Patent (cid:9)
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 15 of 20
`Sheet 15 of 20 (cid:9)
`
`6,046,980
`6,046,980
`
`M 505
`505
`/
`
`
`
`START
`
`RESTORE GIR
`RESTORE GIR
`
`530
`530
`
`(cid:9)r 532
`532
`
`SUBTRACTER FOR
`SUBTRACT EIR FOR
`THIS FLOW FROM
`THIS FLOW FROM
`TOTAL ER DEMANDED
`TOTAL EIR DEMANDED
`
`534
`(cid:9)1534
`
`REDISTRIBUTE
`REDISTRIBUTE
`EIR
`EIR
`
`It (cid:9)
`
`536
`x536
`
`REMOVE FLOW
`REMOVE FLOW
`FROM PARTITION
`FROM PARTITION
`
`( END )
`
`A/G 50
`FiG. 5C.
`
`NOAC Ex. 1009 Page 16
`
`

`

`6,046,980
`6,046,980
`-507
`/507
`
`END
`
`U.S. Patent
`U.S. Patent (cid:9)
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 16 of 20
`Sheet 16 of 20 (cid:9)
`
`
`
`
`
`
`
`
`
`540
`540
`
`/
`
`CALCULATE DEMAND
`CALCULATE DEMAND
`SATISFACTION METRIC
`SATISFACTION METRIC
`FOR THIS BANDWDTH
`FOR THIS BANDWIDTH
`POOL
`POOL
`
`542
`
`DEMAND
`DEMAND
`SATISFACTION
`SATISFACTION
`CHANGED?
`CHANGED?
`
`NO
`
`YES
`
`544
`
`YES
`
`LAST GEAR?
`
`NO
`
`f 546
`
`CALCULATE NEW ER
`CALCULATE NEW EIR
`TOTAL AND NEW TARGET
`TOTAL AND NEW TARGET
`RATE FOR THIS GEAR
`RATE FOR THIS GEAR
`
`
`
`
`
`
`
`
`
`
`
`FIG. 5D
`A/6 5A
`
`NOAC Ex. 1009 Page 17
`
`

`

`U.S. Patent (cid:9)
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 17 of 20 (cid:9)
`Sheet 17 of 20
`
`6,046,980
`6,046,980
`
`550
`MORE
`EXISTING RESERVED
`FLOWS
`
`NO
`
`554
`
`AGGREGATE INDIVIDUAL
`AGGREGATE INDIVIDUAL
`FLOW DEMANDS INTO AN
`FLOW DEMANDS INTO AN
`AGGREGATE RATE
`AGGREGATE RATE
`DEMAND (ARD)
`DEMAND (ARD)
`
`
`
`
`
`
`
`
`
`
`
`
`
`/ 509
`1. 509
`
`p 552
`552
`
`
`
`EXTRAPOLATE UNRE
`EXTRAPOLATE UNRE-
`SERVED DEMAND (EUD)
`SERVED DEMAND (EUD)
`FROM INPUT RATE INTO
`FROM INPUT RATE INTO
`PRIORITY BUCKETS
`PRIORITY BUCKETS
`
`
`
`556
`[556
`
`I
`COMBINE ARD AND
`COMBINE MD AND
`EUO TO ARRIVE AT TOTAL
`EUD TO ARRIVE AT TOTAL
`INSTANTANEOUS
`INSTANTANEOUS
`DEMAND (TD)
`DEMAND (TD)
`
`558
`r 558
`
`COMPUTE SATISFACTION
`COMPUTE SATISFACTION
`PERCENTAGE (SP) BASED
`PERCENTAGE (SP) BASED
`ON TOTAL DEMAND AND
`ON TOTAL DEMAND AND
`AVAILABLE BANOWDTH
`AVAILABLE BANDWIDTH
`RESOURCES IN PARTITION
`RESOURCES IN PARTITION
`
`i
`COMPUTE TARGET RATE
`COMPUTE TARGET RATE
`FOR INDIVIDUAL RESERVED
`FOR INDIVIDUAL RESERVED
`RATE BASED FLOWS
`RATE BASED FLOWS
`
`560
`560
`
`i
`562
`[562
`COMPUTE TARGET RATE
`COMPUTE TARGET RATE (cid:9)
`FOR PRIORITY BUCKETS
`FOR PRIORITY BUCKETS
`FOR UNRESERVED FLOWS
`FOR UNRESERVED FLOWS
`
`Fla 5E
`A/6 5A.
`
`NOAC Ex. 1009 Page 18
`
`(cid:9)
`

`

`U.S. Patent
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 18 of 20
`Sheet 18 of 20 (cid:9)
`
`6,046,980
`6,046,980
`
`
`
`
`
`TCLASSCHECK
`( TCLASSCHECK )
`
`570
`570
`r (cid:9)
`
`1 (cid:9)
`CHECK F
`CHECK IF
`CHILD'S CLASS
`CHILD'S CLASS
`MATCHES FLOW
`MATCHES FLOW
`
`YES
`
`
`
`
`
`
`
`572
`
`YES
`YES
`
`MATCH?
`
`NO
`
`576
`
`ANOTHER
`ANOTHER
`CHILD2
`CHILD?
`
`NO
`
`
`
`
`
`578
`
`THIS
`LEAF. IS THER
`A POLICY?
`
`NO
`
`YES
`
`i 582
`APPLY THE
`APPLY THE
`POLICY OF THIS LEAF
`POLICY OF THIS LEAF
`TO THIS FLOW
`TO THIS FLOW
`
`
`
`/511
`
`75ll
`
`574
`574
`
`/
`
`APPLY TCLASSCHECK
`APPLY TCLASSCHECK
`RECURSIVELY TO
`RECURSIVELY TO
`MATCHING CHILD
`MATCHING CHILD
`
`RETURN
`RETURN
`
`580
`580
`
`BACKTRACK TO
`BACKTRACK TO
`PARENT AND
`PARENT AND
`APPLY POLICY
`APPLY POLICY
`OF PARENT
`OF PARENT
`
`RETURN
`RETURN )
`
`RETURN
`( RETURN )
`
`A/G 5A
`FIG. 5F
`
`NOAC Ex. 1009 Page 19
`
`

`

`U.S. Patent (cid:9)
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 19 of 20
`Sheet 19 of 20 (cid:9)
`
`6,046,980
`6,046,980
`
`-513
`,-5I3
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SCALE TOOAD
`SCALE TOLOAD
`
`582
`582
`
`SET GER SCALED RATE
`SET GIR SCALED RATE
`BASED UPON CONNECTION
`BASED UPON CONNECTION
`SPEED FOR THIS GEAR
`SPEED FOR THIS GEAR
`(SEE FIG. 5H)
`(SEE FIG. 5H)
`
`584
`c584
`
`►
`SET ER SCALED RATE
`SET EIR SCALED RATE
`BASED UPON CONNECTION
`BASED UPON CONNECTION
`SPEED FOR THIS GEAR
`SPEED FOR THIS GEAR
`(SEE FIG 5H)
`(SEE FIG. 5H)
`
`586
`r-586
`►
`COMPUTE A LIMIT FROM
`COMPUTE A LIMIT FROM
`EITHER THE REMAINING
`EITHER THE REMAINING
`EIR OR A TOTAL LIMIT,
`EIR OR A TOTAL LIMIT,
`F AVAILABLE
`IF AVAILABLE
`
`588
`588
`
`590
`590
`
`DETERMINE EXTRA ER
`DETERMINE EXTRA EIR
`FROM LIMIT AND
`FROM LIMIT AND
`REMAINING ER
`REMAINING EIR
`
`ALLOCATE LIMITS TO
`ALLOCATE LIMITS TO
`PRIORITY LEVELS IN
`PRIORITY LEVELS IN
`DESCENDING ORDER
`DESCENDING ORDER
`
`YES
`
`592
`
`ANOTHER
`GEAR
`
`NO
`
`
`
`TERMINATOR
`
`C TERMINATOR )
`FIG 5G
`A/6 66
`(STEP 506 OF FIG. 5A)
`(STEP 506 OF FIG. 5A)
`
`NOAC Ex. 1009 Page 20
`
`

`

`U.S. Patent (cid:9)
`U.S. Patent
`
`Apr. 4, 2000
`Apr. 4, 2000 (cid:9)
`
`Sheet 20 of 20
`Sheet 20 of 20 (cid:9)
`
`6,046,980
`6,046,980
`
`SCALERATE
`C SCALE RATE
`
`592
`592 (cid:9)
`DETECTED RATEN YES
`YES (cid:9)
`C BASE LIMIT
`
`NO
`NO
`
`55
`515
`1
`/
`
`594
`(594
`
`..-E
`
`RETURN BASE
`RETURN BASE
`
`
`
`
`
`
`
`
`
`
`
`
`
`596
`596 (cid:9)
`YES
`RATESIT< &YES
`
`598
`598
`
`(
`RETURN LIMIT C.C.
`RETURN LIMIT« )
`
`602
`602
`
`/
`RETURN LIMIT
`RETURN LIMIT
`
`N0
`NO
`
`
`
`
`
`
`
`
`
`600
`600 (cid:9)
`DETECTED Ti YES
`RATE
`
`YES (cid:9)
`
`NO
`NO
`
`604
`/ 604
`
`COMPUTE A PERCENTAGE
`COMPUTE A PERCENTAGE
`s (DETECTED RATE < <7)
`a (DETECTED RATE < <7)
`/ TOTAL
`/ TOTAL
`
`f 606
`606
`
`I
`RETURN BASE-- (LIMIT
`RETURN BASE+ WAIT
`- BASE). PERCENTAGE)
`— BASE) * PERCENTAGE)
`>> > 7)
`>> 7)
`
`
`
`I
`RETURN
`
`C RETURN )
`
`A/G 5A/
`F/G. 5H
`(STEPS 582 AND 584 OF FIG. 5G)
`(STEPS 582 AND 584 OF FIG. 5G)
`
`NOAC Ex. 1009 Page 21
`
`(cid:9)
`

`

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