`
`11111111111111111111111111111111119111111111111111111111111111111
`
`(12) United States Patent
`Jacobson et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 6,934,256 Bl
`Aug. 23, 2005
`
`(54)
`
`METHOD OF DETECTING
`NON-RESPONSIVE NETWORK FLOWS
`
`(75)
`
`Inventors: Van Jacobson, Woodside, CA (US); Li
`Fan, San Jose, CA (US); Kathleen
`Nichols, Woodside, CA (US)
`
`(73)
`
`Assignee: Cisco Technology, Inc., San Jose, CA
`(US)
`
`OTHER PUBLICATIONS
`
`Sally Floyd and Van Jacobson Random Early Detection
`Gateways for Congestion Avoidance Aug., 1993 pp. 1-22.
`V. Jacobson, K. Nichols, K. Poduri Cisco Systems RED in
`a Different Light Sep. 30, 1999 pp. 1-38.
`Van Jacobson Notes on using RED for Queue Management
`and Congestion Avoidance Jun. 8, 1998.
`
`* cited by examiner
`
`(*)
`
`Notice:
`
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 916 days.
`
`Primary Examiner—Kenneth Vanderpuye
`Assistant Examiner—Rhonda Murphy
`(74) Attorney, Agent, or Firm—Cesari and McKenna, LLP
`
`(21)
`
`Appl. No.: 09/769,544
`
`(22)
`
`Filed:
`
`Jan. 25, 2001
`
`(51)
`(52)
`(58)
`
`
`Int. CI.'
`U.S. Cl.
`
`Field of Search
`
` HO4L 12/26
` 370/235; 370/235.1
` 370/235, 235.1,
`370/236, 401, 412
`
`(56)
`
`References Cited
`
`U.S. PATENT DOCUMENTS
`
`11/2003 Nandy et al.
`6,646,988 B1
`6,690,645 B1 * 2/2004 Aweya et al.
`7/2002 Acevea et al.
`2002/0089930 Al'
`
` 370/235
` 370/230
` 370/230
`
`(57)
`
`ABSTRACT
`
`A network device identifies a non-adaptive flow as follows.
`The network device drops packets on a random basis using
`a Random Early Detection (RED) algorithm. A classifier
`reads indicia of a selected flow from at least one field of a
`header of a packet received by the network device. The
`network device calculates a drop interval for packets of the
`selected flow dropped by the RED algorithm, in response to
`a time at which the packets were dropped. The network
`device then applies a statistical test to drop intervals of a
`plurality of flows in order to identify the non-adaptive flow.
`
`20 Claims, 15 Drawing Sheets
`
`300
`
`302—
`
`PERIODICALLY TEST
`QUEUE LENGTH
`
`304
`
`EXCEEDED
`LOWER THRESHOLD
`
`NO
`
`YES
`
`312
`
`EXCEEDED
`UPPER THRESHOLD
`
`YES
`
`NO
`
`320
`
`APPLY CONTROL LAW
`TO CALCULATE
`P
`THE DROP PROBABILITY
`
`1
`COMPUTE:
`
`-I 322 N=1/P IN AN INTEGER VALUE)
`ONE PACKET IN *N"
`MUST BE DROPPED
`
`324—
`
`CHOOSE A RANDOM
`NUMBER BETWEEN:
`1 AND N
`CHOOSE Z
`4
`326-- COUNT ARRIVING PACKETS
`AND DROP NUMBER 7
`4
`COUNT REMAINING
`N PACKETS
`
`328^
`
`306
`
`/ 308
`NO NEGATIVE
`FEEDBACK
`
`
`
`314
`5
`
`, 316
`
`DROP ALL
`ARRIVING PACKETS
`
`310—
`
`4
`
`Cloudflare - Exhibit 1029, page 1
`
`Cloudflare - Exhibit 1029, page 1
`
`

`

`U.S. Patent
`
`Aug. 23, 2005
`
`Sheet 1 of 15
`
`US 6,934,256 B1
`
`100
`
`S2
`
`104
`
`S1
`
`102
`
`Q
`
`108
`
`106
`
`FIG. 1
`
`Cloudflare - Exhibit 1029, page 2
`
`Cloudflare - Exhibit 1029, page 2
`
`

`

`U.S. Patent
`
`Aug. 23, 2(105
`
`Sheet 2 of 15
`
`US 6,934,256 B1
`
`PROBABILITY
`212
`1.0
`222
`220 \
`0.51-
`
`0.1
`
`200
`
`210
`
`216
`
`206
`
`12% 214
`
`204 10%
`LOWER
`THRESHOLD
`
`60%
`
`100%
`
`202
`
`UPPER
`THRESHOLD
`
`CONTROL LAW CURVE
`
`FIG. 2
`
`Cloudflare - Exhibit 1029, page 3
`
`Cloudflare - Exhibit 1029, page 3
`
`

`

`U.S. Patent
`
`Aug. 23, 2005
`
`Sheet 3 of 15
`
`US 6,934,256 B1
`
`306
`5
`
`308
`NO NEGATIVE
`FEEDBACK
`
`314
`S
`
`/ 316
`DROP ALL
`ARRIVING PACKETS
`
`310—
`
`300
`
`302d
`
`PERIODICALLY TEST
`QUEUE LENGTH
`
`304
`
`EXCEEDED
`LOWER THRESHOLD
`
`NO
`
`YES
`
`312
`
`EXCEEDED
`UPPER THRESHOLD
`
`YES
`
`320
`
`322
`
`324
`
`NO
`
`APPLY CONTROL LAW
`TO CALCULATE
`THE DROP PROBABILITY
`
`1
`COMPUTE:
`N=1/P [N AN INTEGER VALUE]
`ONE PACKET IN "N"
`MUST BE DROPPED
`
`'t
`CHOOSE A RANDOM
`NUMBER BETWEEN:
`1 AND N
`CHOOSE Z
`
`326
`
`COUNT ARRIVING PACKETS
`AND DROP NUMBER "Z"
`
`328—
`
`COUNT REMAINING
`N PACKETS
`
`FIG. 3
`
`Cloudflare - Exhibit 1029, page 4
`
`Cloudflare - Exhibit 1029, page 4
`
`

`

`U.S. Patent
`
`Aug. 23, 2(105
`
`Sheet 4 of 15
`
`US 6,934,256 B1
`
`EVENT
`
`400
`
`402 —
`SOURCE STATION BEGINS DATA TRANSMISSION
`406 -- A WINDOW OF SIX PACKETS IS TRANSMITTED
`(PIPE NOT FULL)
`PACKET #1 REACHES GATEWAY AND IS FORWARDED
`
`408 —,
`
`410 ---
`
`412 - ,
`
`PACKET #2 REACHES GATEWAY AND IS FORWARDED
`
`PACKET #3 REACHES GATEWAY AND IS FORWARDED
`
`PACKET #4 IS DROPPED BY GATEWAY BECAUSE QUEUE
`414 2
`IS FULL FROM OTHER FLOWS
`416 -- PACKET #5 REACHES GATEWAY AND IS FORWARDED
`418 -- PACKET #6 REACHES GATEWAY AND IS FORWARDED
`420 -- DESTINATION STATION RECEIVES PACKETS #1, #2, #3
`DESTINATION STATION SENDS ACKs FOR PACKETS #1, #2, #3
`422 --- SENDER STATION RECEIVES ACKs FOR PACKETS #1, #2, #3
`
`4241
`
`
`
`426 —
`
`ADAPTIVE CYCLE TIME
`
`440
`l--.
`
`J—
`428 --
`
`
`430 2
`
`SENDER STATION TIMES OUT WAITING FOR ACK #4
`(RETRANSMIT TIMER EXPIRES)
`SENDER STATION REDUCES WINDOW BY FACTOR "F"
`SENDER STATION DOUBLES RETRANSMIT TIMER
`SENDER STATION RETRANSMITS PACKET #4
`DESTINATION STATION RECEIVES PACKETS #4
`DESTINATION STATION TRANSMITS ACK FOR PACKETS #4
`TO SOURCE STATION
` STATION RECEIVES ACK FOR PACKET #4
`
`SUCCESSFUL TRANSMISSIONS WITH ACKs FOR "X" PACKETS
`
`SOURCE STATION INCREASES WINDOW WIDTH BY ONE (1) PACKET
`
`SUCCESSFUL TRANSMISSIONS WITH ACKs FOR "X" PACKETS
`
`
`432 2
`c
`
`
`
`434 '
`
`SOURCE STATION INCREASES WINDOW WIDTH BY ONE (1) PACKET
`436 2
`i > 438
`439
` -."‘"— GATEWAY DROPS A PACKET DUE TO CONGESTION
`i > 442
`ADAPTIVE FLOW TIME LINE
`
`T'
`
`FIG. 4
`
`Cloudflare - Exhibit 1029, page 5
`
`Cloudflare - Exhibit 1029, page 5
`
`

`

`U.S. Patent
`
`Aug. 23, 2(105
`
`Sheet 5 of 15
`
`US 6,934,256 B1
`
`DROP
`
`POINT T
`
`506
`
`500
`
`510
`
`508
`
`502—'
`
` " - 512
`
`ADAPTIVE CYCLE TIME
`FOR ONE FLOW
`
`FIG. 5
`
`Cloudflare - Exhibit 1029, page 6
`
`Cloudflare - Exhibit 1029, page 6
`
`

`

`U.S. Patent
`
`Aug. 23, 2(105
`
`Sheet 6 of 15
`
`US 6,934,256 B1
`
`TRANSMISSION
`RATE
`
`NON ADAPTIVE FLOW
`
`600
`
`1 604
`
`602
`
`FIG. 6
`
`Cloudflare - Exhibit 1029, page 7
`
`Cloudflare - Exhibit 1029, page 7
`
`

`

`luaind 'S'9
`
`qa
`
`O c::, u,
`
`Si Jo L
`
`T9 93t17£6`9 Sfl
`
`t
`
`700
`
`DROPPED DROPPED DROPPED DROPPED
`706A 7068 706C 706D 706E 706F 706G
`06H 706J
`
`ti FLI
`
`rsi
`
`h c It It c
`
`DROPPED
`706K
`7061. 706M
`
`706N
`
`rsi (.'.
`
`702
`
`1710J
`
`710K
`
`726
`
`736
`DI)
`
`K.
`
`728
`
`1710M
`
`41 1
`
`710N
`• • •
`
`704
`
`710A 710B
`
`1 710D
`
`tl
`
`)
`
`720
`
`
`
`1-51 1
`
`722
`DI"
`
`,
`
`'
`
`I
`
`I
`
`7p
`DI'
`
`,
`
`730
`
`4 (
`
`1710G
`
`HL
`
`~IL
`
`724
`
`DI'
`
`FIG. 7
`
`ARRIVE
`AT GATEWAY
`
`FORWARDED
`BY GATEWAY
`
`Clouciflare - Exhibit 1029, page 8
`
`Cloudflare - Exhibit 1029, page 8
`
`

`

`U.S. Patent
`
`Aug. 23, 2(105
`
`Sheet 8 of 15
`
`US 6,934,256 B1
`
`800
`
`DENSITY FUNCTION FOR RANDOM
`DROP INTERVALS
`
`808
`
`804-
`
`830
`
`810
`
`814
`812
`806
`
`r )
`816
`
`818
`
`820
`
`822
`
`824
`
`DROP
`INTERVAL
`802 (TIME)
`
`FIG. 8
`
`Cloudflare - Exhibit 1029, page 9
`
`Cloudflare - Exhibit 1029, page 9
`
`

`

`U.S. Patent
`
`Aug. 23, 2005
`
`Sheet 9 of 15
`
`US 6,934,256 B1
`
`900
`
`STATE MAINTAINED FOR DROPPED PACKETS
`
`PACKET
`N
`
`FLOW
`IP SA
`IP DA
`(OTHER
`INDICIA)
`
`TIME OF
`DROP
`
`902
`
`904
`
`906
`
`• ,,, .•••
`
`FIG. 9
`
`Cloudflare - Exhibit 1029, page 10
`
`Cloudflare - Exhibit 1029, page 10
`
`

`

`U.S. Patent
`
`Aug. 23, 2005
`
`Sheet 10 of 15
`
`US 6,934,256 B1
`
`10,000
`
`FLOW ANALYSIS FOR DROPPED PACKETS
`
`FOR EACH FLOW
`
`PACKET
`
`N
`
`TIME OF
`DROP
`T
`
`DROP INTERVAL
`= T(THIS) - T(LAST)
`
`10,002
`
`(
`10,004
`
`(
`10,006
`
`FIG. 10
`
`Cloudflare - Exhibit 1029, page 11
`
`Cloudflare - Exhibit 1029, page 11
`
`

`

`wind 'S'9
`
`SI Jo II Pats
`
`T9 93t17£6`9 Sfl
`
`11.000
`
`11,004
`
`
`11,006
`
`kid
`
`CBR
`
`1.5" DROPS/FLOWS
`
`FTP920
`
`FTP720
`
`11,002
`
`0.12
`
`0.1
`
`FTPO
`
`0.08
`
`0.06
`
`0.04
`
`FTP520
`
`FRACTION OF DROPS IN RECORD
`
`0.02
`450
`
`550
`
`750
`650
`950
`850
`1050
`SIMULATION TIME IN SECOND
`
`1150
`
`FRACTION OF DROPS IN THE RECORD FOR THE CBR
`AND FOUR REPRESENTATIVE FTPs
`
`FIG. 11
`
`Cloudflare - Exhibit 1029, page 12
`
`Cloudflare - Exhibit 1029, page 12
`
`

`

`wind 'S'9
`
`SI Jo Z1 laailS
`
`T9 93t17£6`9 Sfl
`
`11.002
`'CV
`
`12,000
`
`11,004
`
`11,006
`
`ti
`
`1
`
`1
`
`I
`
`i
`
`1
`
`CBR
`
`- FTPO
`
`F1P520
`
`FTP920
`
`0.65
`
`0.6
`o 1.11 0.55
`cr
`u- —1
`0.5
`
`w 0.45
`z
`0
`0.4
`a_ 0-
`0 u juJ 0.35
`0.3
`
`0.25
`450
`
`550
`
`I
`
`FTP720
`I
`l
`i
`I
`t
`750
`650
`1050
`950
`850
`SIMULATION TIME IN SECOND
`
`l
`
`1150
`
`NORMALIZED DEPARTURE FROM EXPONENTIAL MEDIAN OF CBR
`AND FOUR REPRESENTATIVE FTPs
`
`FIG. 12
`
`Cloudflare - Exhibit 1029, page 13
`
`Cloudflare - Exhibit 1029, page 13
`
`

`

`waled 'S'9
`
`SI Jo £T Pails
`
`T9 93t17£6`9 Sfl
`
`13,002
`
`13,000
`
`if
`
`FTP-20ms
`
`12,002
`
`a
`
`0.2
`
`0.15
`
`0.1
`
`CBR
`
`0.05
`
`0
`400
`
`FTP-100ms
`
`1.5" DROPS/FLOWS
`
`----ean'egse519,
`
`1000
`800
`600
`SIMULATION TIME IN SECOND
`
`1200
`
`FRACTION OF DROPS IN THE RECORD FOR THE CBR
`AND ALL FTPs
`FIG. 13
`
`FRACTION OF DROPS IN RECORD
`
`Cloudflare - Exhibit 1029, page 14
`
`Cloudflare - Exhibit 1029, page 14
`
`

`

`3UaJud "S'fl
`
`SI Jo PI lamIS
`
`IA 9SZI7C6`9 Sfl
`
`I
`
`I
`1150
`
`NORMALIZED DEPARTURE FROM EXPONENTIAL MEDIAN OF CBR
`AND ALL FTPs
`
`FIG. 14
`
`14.000
`
`0.65
`
`0.6
`
`CBR
`
`0.55
`
`0.5
`
`o E5
`cc
`1.11 Z——
`Tr
`j 0,45
`D
`- z
`< 0
`Li] X
`ish i 0.35
`
`0.4
`
`-
`
`0.3
`0.25
`450
`
`FTP-20ms
`14,002
`
`550
`
`i
`
`FTP-100ms
`
`t
`
`i
`
`i
`
`I
`I
`I
`1
`1
`1050
`950
`850
`750
`650
`SIMULATION TIME IN SECOND
`
`Cloudflare - Exhibit 1029, page 15
`
`Cloudflare - Exhibit 1029, page 15
`
`

`

`U.S. Patent
`
`Aug. 23, 2(105
`
`Sheet 15 of 15
`
`US 6,934,256 B1
`
`15.000
`
`MEMORY
`
`CPU
`
`15,002—
`
`15,024
`15,020
`
`15,022
`
`P
`
`15,002M
`
`15,002A
`15,002P
`
`15,004
`
`15,004A
`
`15,006
`15,006A
`
`15,008A
`15,008
`
`15,009
`
`
`
` r15,01010150A
`
`15,012
`15,012A
`
`M
`
`15,014
`( 15,014A
`
`M
`
`15,017
`
` 12
`
`15,016A
`15,016
`
`SWITCH FABRIC
`
`FIG. 15
`
`Cloudflare - Exhibit 1029, page 16
`
`Cloudflare - Exhibit 1029, page 16
`
`

`

`US 6,934,256 B1
`
`1
`METHOD OF DETECTING
`NON-RESPONSIVE NETWORK FLOWS
`
`FIELD OF THE INVENTION
`
`This invention relates to regulation of flows of packets in
`computer networks, and more particularly to identifying
`non-adaptive flows.
`
`BACKGROUND OF THE INVENTION
`
`A plurality of different source end nodes transmit packets
`onto a computer network. A "flow" of packets is identified
`by contents of fields in the packet, for example by the Layer
`3 source address, destination address, protocol type field,
`etc. Flows are also identified by internal parameters of the
`router, for example input port and output port. Different
`types of flows may be identified by choosing different
`combinations of fields to identify the flow, including fields
`from the layer 2 header, the layer 3 header, the layer 4 20
`header, etc.
`When a destination end node receives a packet from the
`network, the destination end node ordinarily communicates
`with the source end node in order to let the source end node
`know that the packet was received. For example, in the
`TCP/IP unicast protocol the destination end node transmits
`an acknowledgement message (ACK) to the source end node
`indicating that a packet was received. Until the ACK is
`received, the source end node keeps a copy of the transmit-
`ted packet in memory so that the packet can be resent in the
`event that no ACK is received after expiration of a re-
`transmit time period.
`TCP/IP is an "adaptive flow" protocol. By an "adaptive
`flow" it is meant that, in the event that no ACK indications
`are received for a packet, or for a plurality of packets, an
`adaptive transmitter slows down its rate of transmission for
`that flow. One method of regulating a transmission rate of
`packets is the use of a sliding window, as is implemented in
`the TCP/IP protocol. TCP/IP slows down the rate of packet
`transmission by reducing the number of packets transmitted
`during a window opportunity, and thereby places a longer
`average time interval between the transmitted packets. In
`common implementations of TCP/IP, the window width is
`divided by two (2) each time that the retransmit timer times
`out. Also, typically, the retransmit time interval is doubled
`upon a timeout event. Later, as packets are received by the
`destination station and ACK messages are received by the
`source station, the source station then slowly increases its
`window width, and the retransmit timer timeout interval is
`shortened. This dynamic behavior adjusts the transmission
`rate and retransmit timer timeout interval to network param-
`eters, especially as those parameters change dynamically
`with time.
`Following a reduction in transmission rate, and after
`receiving a plurality of ACK indications that its packets are
`now being received by the destination end station, the
`adaptive transmitter, using TCP/IP or some other adaptive
`protocol, begins slowly increasing its transmission rate until
`the rate is back up to the maximum transmission rate
`permitted.
`Network devices may typically be a router serving as a
`node in the network, where the router typically operates by
`reading and reacting to layer 3 fields read from the packet
`layer 3 header. Alternatively, the network device may be a
`layer 2 switch, where the switch reacts to fields read from the
`packet layer 2 header. Further, some network devices read
`and react to fields read from the layer 4 header of a packet,
`
`2
`etc. All such network devices are subject to congestion when
`packets arrive at the devices faster than the devices can
`handle the arriving packets.
`Not all transmitting end nodes employ adaptive transmis-
`5 sion techniques. An end node which does not adapt is
`referred to as producing a "non-adaptive" flow. A non-
`adaptive flow is frequently bad for the computer network,
`because for flows through a congested network device the
`adaptive transmitter will reduce its flow rate, however the
`to non-adaptive transmitter will continue to blast packets at the
`network device without regard to the congestion. The non-
`adaptive flows then begin to occupy more and more of the
`bandwidth of the congested network device. That is, the
`"bad" flows begin to hog more and more of the congested
`15 bandwidth of the intermediate node network device.
`A method of identifying non-adaptive flows is required in
`order for a network device to take appropriate action.
`
`SUMMARY OF THE INVENTION
`
`A network device identifies a non-adaptive flow as fol-
`lows. In the presence of congestion, the network device
`drops packets on a random basis using a Random Early
`Detection (RED) algorithm. The RED algorithm is used by
`25 the network device to calculate a drop interval for the
`arriving packet stream based on the current congestion level
`of the target queue. In this invention, when a packet is
`dropped, one or more header fields of the packet are stored,
`along with a timestamp of the drop time. The stored data is
`30 used to test for non-adaptive flows in a two-step process.
`First, a flow is only tested if it has a significant share of the
`recorded total drops. For flows for which this is true, the
`stored drop data is used by the network device to compute
`drop intervals on a per-flow basis, where a "flow" is indi-
`35 cated by one or more fields in the packet header. The
`network device applies statistical testing to the drop inter-
`vals in order to identify non-adaptive flows. The network
`device may apply the invention at any suitable time interval
`in order to avoid interfering with the packet forwarding and
`ao other work of the network device.
`In an exemplary embodiment of the invention, the net-
`work device calculates a drop interval for packets of the
`selected flow dropped by the RED algorithm, in response to
`a time at which the packets were dropped. The network
`45 device then applies a statistical test to drop intervals of a
`plurality of flows in order to identify the non-adaptive flow.
`The drop interval is calculated by subtracting from a first
`measured time at which the most recently received packet
`was dropped, a second measured time at which an earlier
`so dropped packet was dropped. The statistical test is per-
`formed by first computing an average drop interval for the
`selected flow. Next the median drop interval for the selected
`flow is computed, the median drop interval having one half
`of the drop intervals larger than the median and having one
`55 half of the drop intervals less than the median. Also the
`average drop interval for the recorded drop intervals is
`computed. The drops of a non-responsive flow should be
`distributed in a uniformly random way over time, thus their
`time intervals should have an exponential distribution. For
`60 an exponential density function, the median drop interval is
`expected to be 0.693 times the average drop interval.
`A quantity referred to as the "Departure from Exponential
`Mean" (DEM) is computed by determining the number of a
`flow's drop intervals that are smaller than the experimental
`65 average, and then dividing by the total number of drop
`intervals. Then, a value greater than 0.5 indicates a flow with
`more short drop intervals than the predicted median, and a
`Cloudflare - Exhibit 1029, page 17
`
`Cloudflare - Exhibit 1029, page 17
`
`

`

`US 6,934,256 B1
`
`3
`value smaller than 0.5 indicates a flow with longer intervals
`than the predicted median for an exponential. The oscillatory
`adaptive flows have more long drop intervals than the
`exponential predicts, and so generally have a smaller value
`of DEM than 0.5. Stated differently, the drops of properly
`adapting flows should be periodic in time, thus the drop
`intervals will be longer than what the exponential predicts,
`and so generally have a smaller value of DEM than 0.5.
`The statistical test is performed by comparing the DEM
`value with the number 0.5, and in the event that the DEM
`value is within a preselected range of 0.5, the flow is
`identified as non-adaptive. The preselected range may be
`chosen between 0.45 and any number larger than 0.5.
`The preselected range may be dynamically selected in
`response to DEM values of selected flows, especially as
`congestion becomes worse at the network device. The
`non-adaptive flows may have a larger DEM value as mul-
`tiple randomly arriving adaptive flows have packets dropped
`on a random basis. The adaptive flows may be selected as a
`subset of all flows, the subset having selected values of
`DEM less than a largest value of DEM computed in a set of
`flows, and the non-adaptive flows identified as those having
`the larger values of DEM.
`In an exemplary implementation of the invention, a clas-
`sifier reads indicia of a selected flow from at least one field
`of a header of a packet received by the network device. The
`flow is then classified and steered away from the normal
`queue to a special queue, particularly in the event that the
`flow is found to be non-responsive. The special queue may
`then operate at a lower priority, or drop packets, etc.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`Turning now to the drawings in which like numerals
`represent like parts in the several views:
`FIG. 1 is block diagram of a computer network;
`FIG. 2 is a graph of a control law in a RED algorithm
`controller;
`FIG. 3 is a flow diagram of a RED algorithm controller
`FIG. 4 is a time line diagram of events in a computer
`network employing a RED algorithm controller;
`FIG. 5 is a transmission rate of a source end station of an
`adaptive flow, in accordance with the invention;
`FIG. 6 is a graph giving a transmission rate of a source
`end station of a non adaptive flow, in accordance with the
`invention;
`FIG. 7 is a graph giving packet drops of a non-adaptive
`flow by a RED algorithm controller, in accordance with the
`invention;
`FIG. 8 is a statistical density function for random drop
`intervals, in accordance with the invention;
`FIG. 9 is a table holding state information maintained by
`a network device for dropped packets, in accordance with
`the invention;
`FIG. 10 is a table holding state information maintained by
`a network device for dropped packets, in accordance with
`the invention;
`FIG. 11 is a graph giving a plot of results obtained from
`a simulation of a congested network, in accordance with the
`invention;
`FIG. 12 is a graph giving a plot of results obtained from
`a simulation of a congested network, in accordance with the
`invention;
`FIG. 13 is a graph giving a plot of results obtained from
`a simulation of a congested network, in accordance with the
`invention;
`
`4
`FIG. 14 is a graph giving a plot of results obtained from
`a simulation of a congested network, in accordance with the
`invention; and,
`FIG. 15 is a block diagram of a typical network device.
`
`5
`
`DETAILED DESCRIPTION OF AN
`ILLUSTRATIVE EMBODIMENT
`
`Turning now to FIG. 1, Computer Network 100 is shown.
`to Computer Network 100 represents a general computer net-
`work, from a small local area network to the entire world-
`wide Internet. End-station 102 serves as a source station for
`transmission of data packets in this example, and end-station
`104 serves as a receiving station for the packets transmitted
`15 by source station 102. As the packets traverse network 100
`the IP source address of the packets is "Si", representing
`source station 102. The IP destination address of the packets
`is "S2" representing station 104. Gateway 106 represents a
`network device through which the packets must pass on their
`20 travels from source station 102 to destination station 104.
`Gateway 106 may be a layer 2 switch within the network
`100, may be a router operating at layer 3, or may be any
`other convenient intermediate network device. We refer to
`gateway 106 as a "gateway" because it serves as a band-
`25 width limiting feature in the path that the packets take from
`source station 102 to destination station 104.
`A queue 108 within gateway 106 receives packets as they
`arrive from source station 102, and serves as a buffer as the
`packets are transmitted by gateway 106 to destination station
`3o 104. For example, queue 108 may be a rate limiting queue
`placed at an output port of a router, where the function of
`queue 108 is to buffer bursts of packets received from a
`source station, and to transmit them at regularly timed
`intervals on an outgoing link from gateway 106.
`35 A Random Early Detection (RED) gateway algorithm is
`executed within gateway 106 for congestion avoidance in
`network 100. The RED gateway algorithm detects incipient
`congestion by reacting to the average queue size. When the
`average queue size exceeds a preset threshold, gateway 106
`ao drops arriving packets with a certain probability. The exact
`probability is a function of average queue size. The RED
`gateway keeps the average queue size low while allowing
`room for occasional bursts of packets in the queue. Opera-
`tion of a Random Early Detection (RED) gateway is
`as described in the paper by Sally Floyd and Van Jacobson, in
`their paper entitled "Random Early Detection Gateways for
`Congestion Avoidance", IEEE/ACM Transactions on Net-
`working, August 1993, all disclosures of which are incor-
`porated herein by reference.
`so Also, operation of a Random Early Detection (RED)
`gateway is described in the paper by V. Jacobson, K. Nichols
`and K. Poduri, in their paper entitled "RED in a Different
`Light", dated Sep. 30, 1999, unpublished but widely circu-
`lated, and available on the Internet.
`Further similar information is given in Notes on Using
`RED for Queue Management and Congestion Avoidance,
`talk at The North American Network Operators Group
`(NANOG), NANOG 13, Dearborn, Mich., June 1998, avail-
`able on the Internet.
`60 Other documents concerning the RED algorithm are
`available on the Internet from the Lawrence Berkley Labo-
`ratory web site.
`Turning now to FIG. 2, a control law implemented in a
`RED algorithm is illustrated in graph 200. The horizontal
`65 axis 202 represents a quantity giving the amount by which
`queue 108 is full. A lower threshold is shown at point 204,
`and an upper threshold is shown at point 206. For example.
`Cloudflare - Exhibit 1029, page 18
`
`55
`
`Cloudflare - Exhibit 1029, page 18
`
`

`

`US 6,934,256 B1
`
`5
`the lower threshold is set, for illustrative purposes, at a
`filling quantity of 10%. Also, for example, the upper thresh-
`old 206 is shown as the queue being 100% full.
`Curve 210 translates the measure of how full the queue is,
`indicated on the horizontal axis, into a probability for
`dropping packets. The probability for dropping packets is
`plotted on the vertical axis 212. For example, at or below the
`lower threshold 204 in filling the queue, the probability for
`dropping a packet is computed by curve 210 to be "0".
`However at a slightly higher degree of filling of the queue,
`for example at 12% at point 214, the probability for drop-
`ping a packet is computed by curve 210 to be 10% (prob-
`ability P equals 0.1). Further, as the queue becomes more
`filled, for example at point 216 where the queue is repre-
`sented as 60% full, curve 210 computes the probability P for
`dropping a packet to be 0.5 at location 220, that is a 50%
`probability for dropping a packet. When the queue filling
`reaches the upper threshold 206, curve 210 indicates, at
`point 222 that the probability for dropping a packet is be 1.0,
`that is 100% (probability P of 1.0). That is, when the queue
`filling reaches the upper threshold 206, all packets arriving
`at gateway 108 are dropped.
`Turning now to FIG. 3, a flow chart 300 showing opera-
`tion of the RED gateway is shown. Particularly, flow chart
`300 shows how a packet is chosen for being dropped by the
`RED gateway 106. Starting with block 302, the queue 108
`is periodically tested to determine the length of the queue.
`After a queue length determination is made the process goes
`to block 304.
`At block 304 the queue length is tested to determine if it
`exceeds the lower threshold 204. In the event that the lower
`threshold is not exceeded, the process goes along path 306
`to block 308 where it is determined that no negative feed-
`back is required. From block 308 the process returns along
`path 310 to block 302 for again periodically determining the
`queue length.
`In the event that block 304 tests "yes", that the lower
`threshold was exceeded, the process goes to block 312. At
`block 312 the queue length is tested to determine if the upper
`threshold 206 has been exceeded. In the event that block 312
`answers "yes", the upper threshold is exceeded, the process
`goes along path 314 to block 316.
`At block 316 the process decides to drop all arriving
`packets. From block 316 the process returns along path 310
`to again periodically test the queue length at block 302. In
`the event that block 312 answers "No", the upper threshold
`was not exceeded, the process goes to block 320.
`At block 320 the control law, for example the control law
`200 shown in FIG. 2, is used to calculate the probability that
`a packet should be dropped. The probability is represented
`by the symbol "P". The probability "P" is computed by using
`the measured queue length and applying the control law 200
`in order to determine the probability "P". After the prob-
`ability "P" is computed, the process goes to block 322.
`At block 322 the inverse of the probability is computed,
`where the inverse is represented by "N", and "N" is rounded
`to an integer value. "N" represents the fact that application
`of the RED algorithm requires that one packet in "N" must
`be dropped in order to avoid congestion. After calculation of
`the value of "N" at block 322, the process goes to block 324.
`At block 324 a random number generator is queried, and
`a random number is chosen between the values of 1 and "N".
`The random number between 1 and "N" which is chosen is
`represented by the symbol "Z". Upon choosing the random
`number "Z" which lies between "1" and "N", the process
`goes to block 326.
`
`6
`At block 326 the process counts the arriving packets and
`drops packet number "Z". By counting the arriving packets,
`and dropping the "Z'th" packet, the RED algorithm imposes
`the control law 200, by applying a probability for dropping
`5 incoming packets, and applies that probability by choosing
`a random packet within the range of "1" to the inverse of the
`probability. After dropping the "Z'th" packet, the process
`goes to block 328.
`At block 328 the process counts the remaining "N"
`to packets. After counting the remaining "N" packets as they
`arrive at queue 108 of gateway 106, the process returns
`along path 310 to block 302 where the queue length is again
`periodically tested.
`Process 300 continues, for example, periodically testing
`15 queue length at block 302, and dropping a randomly selected
`packet at block 326 when the queue length is between the
`lower threshold 204 and the upper threshold 206.
`As an example, other indicia of congestion besides queue
`length may be used as the control parameter in control law
`20 200. For example, the control law 200 shown in FIG. 2 uses
`queue length as a detection parameter for congestion. Other
`parameters showing congestion, or incipient congestion,
`may be computed at block 302, and a lower threshold and
`upper threshold for the other parameter tested so that in the
`25 event that the measured parameter lies between the lower
`threshold and the upper threshold, a randomly arriving
`packet may be dropped at block 326.
`Turning now to FIG. 4, a timeline 400 for end-to-end
`operation of the packet transfer from source end-station 102
`30 to destination end-station 104 is shown. For example, source
`end-station 102 and destination end-station 104 may imple-
`ment an adaptive transfer protocol for reliable packet trans-
`fer. For example, the source end-station 102 and destination
`end-station 104 may implement the TCP/IP protocol, which
`35 is an adaptive protocol for reliable packet transfer. The
`TCP/IP protocol is used in the Internet for many types of
`data transfer. The TCP/IP protocol is described by W.
`Richard Stevens in his book: TCP/IP Illustrated, Vol. 1, Vol.
`2, Vol. 3, published by Addison Wesley, Copyright date
`ao 1994, all disclosures of which are incorporated herein by
`reference.
`In short, the TCP/IP protocol requires that the destination
`station transmit an acknowledgement message (ACIC) to the
`source station, upon receipt by the destination station 104 of
`45 a complete packet. Packets carry a serial number, and a serial
`number of the last properly received packet is transmitted
`within the ACK message from the destination station to the
`source station. Meanwhile, the source station maintains in
`memory all of its transmitted packets until it receives an
`so ACK message, or until a retransmit timer times out. In the
`event of the retransmit timer times out, the source station
`retransmits the packet. By exchanging ACK messages in this
`manner, the source station and destination station establishes
`a reliable communications path for data packets. Also, the
`55 adaptive nature of the source end-station executing the
`TCP/IP protocol is that the source station reduces the rate at
`which it transmits packets upon the time-out of the retrans-
`mit timer. The source station reduces the rate at which it
`transmits packets after a retransmit timer times out on the
`60 assumption that the packet was lost due to congestion within
`the network. By reducing the rate at which it transmits
`packets, the source station accommodates its transmission
`rate to the congestion state of the network. Details of this
`adaptive process are set out in the book is by Stevens,
`65 TCP/IP illustrated, vol. 1.
`The timeline 400 indicates principal events in the adaptive
`process of the TCP/IP protocol, as an example of an adaptive
`Cloudflare - Exhibit 1029, page 19
`
`Cloudflare - Exhibit 1029, page 19
`
`

`

`US 6,934,256 B1
`
`7
`method of congestion avoidance, or congestion control,
`within a computer network. At time 402 the source station
`begins data transmission. At time 406 a window of packets
`is transmitted, and for example, the timeline shows a win-
`dow of six (6) packets being transmitted. We assume further
`that the "pipe" between the source station 102 and destina-
`tion station 104 is not filled by this window of packets being
`transmitted by source station 102. At time 408 packet
`number 1 reaches gateway 106 and is forwarded to desti-
`nation station 104. At time 410 packet number 2 reaches
`gateway 106 and is forwarded to destination station 104. At
`time 412 packet number 3 reaches gateway 106 and is
`forwarded to destination station 104.
`At time 414 packet number 4 reaches gateway 106.
`However packet number 4 is dropped by gateway 106 as the
`gateway executes the RED congestion avoidance algorithm,
`as shown in FIG. 2 and FIG. 3.
`At time 416 packet number 5 reaches the gateway and is
`forwarded to destination station 104. At time 418 packet
`number 6 reaches the gateway and is forwarded to destina-
`tion station 104. Following time 420, t