`
`
`
`
`(12) United States Patent
`
`
`
`
`US 6,934,256 BI
`(10) Patent No.:
`
`
`
`
`
`
`
`Aug.23, 2005
`(45) Date of Patent:
`Jacobson etal.
`
`
`US006934256B1
`
`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 Primary Examiner—Kenneth Vanderpuye
`
`
`
`
`
`
`
`patent is extended or adjusted under 35
`Assistant Examiner—Rhonda Murphy
`
`
`
`
`
`
`
`
`
`
`
`US.C. 154(b) by 916 days.
`(74) Attorney, Agent, or Firm—Cesari and McKenna, LLP
`
`
`
`
`
`Appl. No.: 09/769,544
`
`(54)
`
`(75)
`
`
`
`
`
`(73)
`
`
`
`(21)
`
`(22)
`
`(61)
`(52)
`(58)
`
`
`
`
`
`
`
`
`
`METHOD OF DETECTING
`
`
`NON-RESPONSIVE NETWORK FLOWS
`
`
`
`
`
`
`
`
`Inventors: Van Jacobson, Woodside, CA (US); Li
`
`
`
`
`
`Fan, San Jose, CA (US); Kathleen
`
`
`
`Nichols, Woodside, CA (US)
`
`
`
`
`
`
`Assignee: Cisco Technology, Inc., San Jose, CA
`
`(US)
`
`
`
`
`
`Jan. 25, 2001
`
`
`
`Filed:
`
`
`
`
`HO4L 12/26
`
`
`
`
`
`US. C1. ccc cccccceteteeteenseneenes 370/235; 370/235.1
`
`
`
`
`Field of Search .............0..0cce 370/235, 235.1,
`
`
`
`370/236, 401, 412
`
`(56)
`
`
`
`References Cited
`
`
`
`
`U.S. PATENT DOCUMENTS
`
`
`
`
`
`
`
`
`
`6,646,988 B1* 11/2003 Nandyet al... 370/235
`
`
`
`
`
`
`
`6,690,645 B1*
`2/2004 Aweyaet al... 370/230
`
`2002/0089930 A1 *
`7/2002 Aceveset al. wee. 370/230
`
`
`
`
`
`
`
`
`
`
`
`
`300
`
`
`
`
`302
`
`
`
`PERIODICALLY TEST
`
`QUEUE LENGTH
`
`
`
`
`
`
`(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 atleast 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
`
`
`
`
`EXCEEDED
`
`
`
`LOWER THRESHOLD
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` 310™~
`
`CHOOSE A RANDOM
`
`NUMBER BETWEEN:
`
`1ANDN
`
`
`CHOOSE Z
`
`
`
`COUNTARRIVING PACKETS
`AND DROP NUMBER"2"
`
`
`
`
`
`
`
`
`
`
`30
`
`
`
`8
`
`COUNT REMAINING
`N PACKETS
`
`
`
`
`
`Splunk Inc.
`
`Exhibit 1029
`
`Page 1
`
`EXCEEDED
`
`
`
`UPPER THRESHOLD.
`
`
`
`
`
` DROP ALL
`
`ARRIVING PACKETS
`
`
`APPLY CONTROL LAW
`
`
`
`
`TO CALCULATE
`
`
`P
`
`THE DROP PROBABILITY
`
`320
`
`
`
`
`322
`
`
`
`COMPUTE:
`
`
`
`N=1/P [N AN INTEGER VALUE]
`ONE PACKETIN "N"
`
`
`MUST BE DROPPED
`
`
`
`
`
`
`
`Splunk Inc. Exhibit 1029 Page 1
`
`

`

`
`U.S. Patent
`
`
`
`
`Aug.23, 2005
`
`
`
`
`
`Sheet 1 of 15
`
`
`
`US 6,934,256 B1
`
`
`
`
`
`
`FIG. 1
`
`Splunk Inc.
`
`Exhibit1029
`
`Page 2
`
`Splunk Inc. Exhibit 1029 Page 2
`
`

`

`
`U.S. Patent
`
`
`
`
`Aug.23, 2005
`
`
`
`
`Sheet 2 of 15
`
`
`
`US 6,934,256 B1
`
`PROBABILITY
`
`
`
`
`
`
`
`
`200
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`CONTROL LAW CURVE
`
`
`
`
`FIG. 2
`
`Splunk Inc.
`
`Exhibit1029
`
`Page 3
`
`10%=12% 544 60% 100% 202
`
`
`
`
`204
`
`
`UPPER
`LOWER
`THRESHOLD
`THRESHOLD
`
`Splunk Inc. Exhibit 1029 Page 3
`
`

`

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

`

`
`U.S. Patent
`
`
`
`
`Aug.23, 2005
`
`
`
`
`Sheet 4 of 15
`
`
`
`US 6,934,256 B1
`
`
`
`
`
`4
`
`
`400
`
`
`
`>So
`
`Lu
`
`e
`
`uu
`
`—l
`
`
`
`
`
`
`
`
`
`©>©L
`
`u =-o<
`
`EVENT
`
`
`
`
`SOURCE STATION BEGINS DATA TRANSMISSION
`
`
`A WINDOW OFSIX PACKETSIS TRANSMITTED
`
`
`
`(PIPE NOT FULL)
`
`
`
`
`PACKET#1 REACHES GATEWAY AND IS FORWARDED
`
`
`
`
`PACKET #2 REACHES GATEWAYAND IS FORWARDED
`
`
`
`
`PACKET #3 REACHES GATEWAY AND IS FORWARDED
`
`
`
`
`PACKET #4 IS DROPPED BY GATEWAY BECAUSE QUEUE
`
`
`
`
`IS FULL FROM OTHER FLOWS
`
`
`
`
`
`PACKET #5 REACHES GATEWAY AND IS FORWARDED
`
`
`
`
`
`PACKET #6 REACHES GATEWAYAND IS FORWARDED
`
`
`
`
`DESTINATION STATION RECEIVES PACKETS#1, #2, #3
`
`
`
`
`DESTINATION STATION SENDS ACKs FOR PACKETS#1, #2, #3
`
`
`
`
`
`
`SENDER STATION RECEIVES ACKs FOR PACKETS#1, #2, #3
`
`
`
`
`
`
`
`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
`
`
`
`
`
`
`SOURCE STATION RECEIVES ACK FOR PACKET#4
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`SUCCESSFUL TRANSMISSIONS WITH ACKs FOR "X" PACKETS
`
`
`
`
`
`
`SOURCESTATION INCREASES WINDOW WIDTH BY ONE (1) PACKET
`SUCCESSFUL TRANSMISSIONS WITH ACKs FOR "X" PACKETS
`
`
`
`
`
`
`
`
`
`
`SOURCE STATION INCREASES WINDOW WIDTH BY ONE(1) PACKET
`
`
`> 438
`
`
`
`GATEWAY DROPSA PACKET DUE TO CONGESTION
`
`
`
`> 442
`>
`
`
`ADAPTIVE FLOWTIMELINE
`
`
`
`
`
`
`
`
`
`
`
`
`FIG. 4
`
`Splunk Inc.
`
`Exhibit1029
`
`Page5
`
`
`
`=t
`
`xa<
`
`
`x
`
`Splunk Inc. Exhibit 1029 Page 5
`
`

`

`
`U.S. Patent
`
`
`
`
`Aug. 23, 2005
`
`
`
`
`Sheet 5 of 15
`
`
`
`US 6,934,256 B1
`
`200
`
`
`
`
`
`
`
`508 502
`
`
`
`
`512
`440
`
`
`
`
`T
`
`
`
`
`
`ADAPTIVE CYCLE TIME
`
`
`
`FOR ONE FLOW
`
`
`FIG. 5
`
`Splunk Inc.
`
`Exhibit1029
`
`Page6
`
`Splunk Inc. Exhibit 1029 Page 6
`
`

`

`
`U.S. Patent
`
`
`
`
`Aug.23, 2005
`
`
`
`
`Sheet 6 of 15
`
`
`
`US 6,934,256 B1
`
`TRANSMISSION
`
`RATE
`
`
`
`
`
`NON ADAPTIVE FLOW
`
`
`
`600
`
`
`, 604
`
`
`
`602
`
`
`
`
`FIG. 6
`
`Splunk Inc.
`
`Exhibit1029
`
`Page7
`
`Splunk Inc. Exhibit 1029 Page 7
`
`

`

`POLidId
`
`ZZgel922velvelwyLLNolwolt=}wore}row!§=—|gore|I
`
`NSO0ZW902%90/}M90Lf90Z
`veLILELI
`||
`
`
`
`GAddOYQCGdddOWdGaddOYdCaddOuG
`
`
`
`
`
`H904)S90L4902}3902}A90ZL9902)9902V90L
`
`Z°9ld
`
`QobZ
`
`GObZWObd
`
`cel
`
`Id
`
`ccl
`
`O¢2
`
`Id
`
`O¢2
`
`PL
`AYMALVOAS
`QaddvMa0s
`
`U.S. Patent
`
`Aug.23, 2005
`
`Sheet 7 of 15
`
`US 6,934,256 B1
`
`COL|
`
`|
`
`CGdddOud
`
`002
`
`AAV
`
`AYM3LV9LV
`
`Splunk Inc.
`
`Exhibit 1029
`
`Page 8
`
`Splunk Inc. Exhibit 1029 Page 8
`
`

`

`
`U.S. Patent
`
`
`
`
`Aug.23, 2005
`
`
`
`
`Sheet 8 of 15
`
`
`
`US 6,934,256 B1
`
`800
`
`
`
`rer
`
`
`
`
`
`
`DENSITY FUNCTION FOR RANDOM
`
`
`
`
`804
`
`810
`
`812
`
`DROP INTERVALS
`
`
`
`
`
`
`DROP
`
`
`
`
`
`
`
`
`INTERVAL
`
`
`
`806
`802 (TIME)
`
`
`
`
`
`
`
`
`FIG. 8
`
`Splunk Inc.
`
`Exhibit1029
`
`Page9
`
`Splunk Inc. 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
`
`
`TIME OF
`
`DROP
`
`
`FLOW
`
`IP SA
`
`IP DA
`
`(OTHER
`
`
`INDICIA)
`
`
`
`
`
`
`
`
`FIG. 9
`
`Splunk Inc.
`
`Exhibit1029
`
`Page 10
`
`Splunk Inc. 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
`
`
`
`|
`DROP INTERVAL
`
`
`= T(THIS) - T(LAST)|
`
`T
`
`10,002
`
`
`
`10,004
`
`
`
`10,006
`
`
`
`
`FIG. 10
`
`
`
`Splunk Inc.
`
`Exhibit1029
`
`Page 11
`
`Splunk Inc. Exhibit 1029 Page 11
`
`

`

`
`U.S. Patent
`
`
`
`
`Aug.23, 2005
`
`
`
`
`
`Sheet 11 of 15
`
`
`
`US 6,934,256 B1
`
`SMO1d/SdOUd
`
`
`
`Paye|900'F1¥00'L1200tt
`
`.S't
`
`cb0
`
`LO
`
`80°0
`900
`
`
`
`QYO03H NI SdOUd JO NOILOVeS
`
`
`
`
`
`OSttOSOL056058OGL0590&6
`
`QNOOASNISLLNOLLVINWIS
`
`
`
`YdAHLYOsGHOOSYSH!NiSdONd4ONOILOVYS
`
`
`
`
`
`Sdi4SAILVLNSSSed3yeNOONY
`
`LlSls
`
`SplunkInc.
`
`Exhibit 1029
`
`Page 12
`
`Splunk Inc. Exhibit 1029 Page 12
`
`

`

`U.S. Patent
`
`Aug.23, 2005
`
`Sheet 12 of 15
`
`US 6,934,256 B1
`
`00021
`
`cbOld
`
`YaoJONVICSAWWILNANOdxX]aWOdSSunLeVvd3dGSZNVNYON
`
`
`
`rf02d~9NekafWVWoeempZsdi47)$60
`OSt}O0S0'O56058O0S40590550S%
` aNM:0z6dL4odid4sro
`
`900°100/1AU
`
`
`SdidSAILVLNASSYd3yeNOSONV
`
`QNOOSNISWILNOLLVINWIS
`
`S90
`
`90
`
`SS0
`
`o0
`
`G20
`
`NVIGSW WILNSNOdX4 SHL
`WOds AYNLYVdsd
`
`SplunkInc.
`
`Exhibit 1029
`
`Page 13
`
`Splunk Inc. Exhibit 1029 Page 13
`
`
`

`

`U.S. Patent
`
`Aug.23, 2005
`
`Sheet 13 of 15
`
`US 6,934,256 B1
`
`SMO1s/SdOudSL
`
`
`
`00210001008009OOF
`
`QYOO03Y NI SdOwd 40 NOILOVYS
`
`
`
`QNOOASNISWILNOLLVINAIS
`
`
`
`489FHLYOsGYOOsYSHINISdOUG40NOILOVYS
`
`SdidTIv¥ONV
`
`elOla
`
`SplunkInc.
`
`Exhibit 1029
`
`Page 14
`
`Splunk Inc. Exhibit 1029 Page 14
`
`

`

`
`U.S. Patent
`
`
`
`
`Aug.23, 2005
`
`
`
`
`Sheet 14 of 15
`
`
`
`US 6,934,256 B1
`
`
`
`G90
`
`9°0
`
`SS0
`
`G0
`
`Se0
`
`
`
`NVIGSW IWILNANOdxX3 SHL
`
`WOSJeNLYVdsd
`
`
`OStLOSObO0S6O88OS0590&5OF
`SWOOb-di4£0
`
`
`
`48940NVIGSWWILNSNOdxX3WOUsSYuNLYVdadCSZIVWYON
`
`
`
`
`
`
`
`ONOOASNISWILNOLLVINWIS
`
`
`
`SdldT1¥ONY
`
`blSls
`
`SplunkInc.
`
`Exhibit 1029
`
`Page 15
`
`S70
`
`70
`
`Splunk Inc. Exhibit 1029 Page 15
`
`

`

`
`U.S. Patent
`
`
`
`
`Aug.23, 2005
`
`
`
`
`Sheet 15 of 15
`
`
`
`US 6,934,256 B1
`
`
`
`, 15,022
`
`15.010
`15,010A
`
`
`
`15,006
`15,006A
`
`|
`1
`
`15,012
`15,012A
`
`15,014
`L
`|. 15,014A
`
`
`
`
`15,009
`
`
`
`15,017
`
`
`| |*15,016A3
`
`
`
`_| et 15,016
`
`
`SWITCH FABRIC
`
`
`
`
`
`FIG. 15
`
`Splunk Inc.
`
`Exhibit1029
`
`Page 16
`
`Splunk Inc. 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
`
`
`
`
`
`10
`
`
`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.
`
`
`
`
`
`
`
`Notall transmitting end nodes employ adaptive transmis-
`
`
`
`
`
`
`
`
`
`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
`
`
`
`
`
`
`
`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
`bandwidth of the intermediate node network device.
`
`
`
`
`
`
`
`
`
`
`
`
`Amethodofidentifying non-adaptive flows is required in
`
`
`
`
`
`
`
`order for a network device to take appropriate action.
`
`SUMMARYOF THE INVENTION
`
`
`
`
`
`
`
`
`
`
`
`
`
`Aplurality of different source end nodes transmit packets
`
`
`
`
`
`
`onto a computer network. A “flow” of packets is identified
`
`
`
`
`
`
`
`
`
`by contents offields 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
`
`
`
`
`
`
`
`combinationsoffields to identify the flow, including fields
`
`
`
`
`
`
`
`
`
`from the layer 2 header,
`the layer 3 header,
`the layer 4
`
`
`
`
`
`
`
`
`
`header,etc.
`A network device identifies a non-adaptive flow as fol-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`lows. In the presence of congestion,
`the network device
`When a destination end node receives a packet from the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`drops packets on a random basis using a Random Early
`network, the destination end node ordinarily communicates
`
`
`
`
`
`
`
`with the source end node in orderto let the source end node
`
`
`
`
`
`
`
`
`
`
`
`Detection (RED) algorithm. The RED algorithm is used by
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the network device to calculate a drop interval for the
`know that the packet was received. For example,
`in the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`arriving packet stream based on the current congestion level
`TCP/IPunicast protocol the destination end node transmits
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`an acknowledgement message (ACK)to the source end node
`of the target queue. In this invention, when a packet is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`dropped, one or more headerfields of the packet are stored,
`indicating that a packet was received. Until the ACK is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`along with a timestamp of the drop time. The stored data is
`received, the source end node keeps a copy of the transmit-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`used to test for non-adaptive flows in a two-step process.
`ted packet in memoryso that the packet can be resent in the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`First, a flow is only tested if it has a significant share of the
`event that no ACK is received after expiration of a re-
`
`
`
`
`
`
`
`
`
`
`
`
`
`recorded total drops. For flows for which this is true, the
`transmit time period.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`stored drop data is used by the network device to compute
`TCP/IP is an “adaptive flow” protocol. By an “adaptive
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`flow”it is meant that, in the event that no ACK indications
`drop intervals on a per-flow basis, where a “flow” is indi-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`cated by one or more fields in the packet header. The
`are received for a packet, or for a plurality of packets, an
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`network device appliesstatistical testing to the drop inter-
`adaptive transmitter slows down its rate of transmission for
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`vals in order to identify non-adaptive flows. The network
`that flow. One method of regulating a transmission rate of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`device may apply the invention at any suitable time interval
`packets is the use of a sliding window,as is implemented in
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`in order to avoid interfering with the packet forwarding and
`the TCP/IP protocol. TCP/IP slows downthe rate of packet
`
`
`
`
`
`
`other work of the network device.
`
`
`
`
`
`transmission by reducing the numberof packets transmitted
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`In an exemplary embodiment of the invention, the net-
`during a window opportunity, and thereby places a longer
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`work device calculates a drop interval for packets of the
`average time interval between the transmitted packets. In
`
`
`
`
`
`
`
`
`
`
`
`
`selected flow dropped by the RED algorithm,in response to
`common implementations of TCP/IP, the window width is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`divided by two (2) each timethat the retransmit timer times
`a time at which the packets were dropped. The network
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`device then applies a statistical test to drop intervals of a
`out. Also, typically, the retransmit time interval is doubled
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`plurality of flows in order to identify the non-adaptive flow.
`upon a timeout event. Later, as packets are received by the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`destination station and ACK messages are received by the
`The drop interval is calculated by subtracting fromafirst
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`source station, the source station then slowly increases its
`measured time at which the most recently received packet
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`window width, and the retransmit timer timeout interval is
`was dropped, a second measured time at which an earlier
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`shortened. This dynamic behavior adjusts the transmission
`dropped packet was dropped. Thestatistical test
`is per-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`rate and retransmit timer timeout interval to network param-
`formed by first computing an average drop interval for the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`eters, especially as those parameters change dynamically
`selected flow. Next the median drop interval for the selected
`
`
`
`
`
`
`
`
`
`with time.
`
`
`flow is computed, the median drop interval having onehalf
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Following a reduction in transmission rate, and after
`of the drop intervals larger than the median and having one
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`receiving a plurality of ACK indicationsthat its packets are
`half of the drop intervals less than the median. Also the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`now being received by the destination end station,
`the
`average drop interval for the recorded drop intervals is
`
`
`
`
`
`
`
`
`
`
`
`
`
`adaptive transmitter, using TCP/IP or some other adaptive
`computed. The drops of a non-responsive flow should be
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`protocol, begins slowly increasing its transmission rate until
`distributed in a uniformly random wayovertime, thus their
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the rate is back up to the maximum transmission rate
`time intervals should have an exponential distribution. For
`
`
`
`
`
`
`
`
`
`permitted.
`an exponential density function, the median drop interval is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`expected to be 0.693 times the average drop interval.
`Network devices may typically be a router serving as a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`node in the network, where the router typically operates by
`A quantity referred to as the “Departure from Exponential
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Mean” (DEM)is computed by determining the numberof a
`reading and reacting to layer 3 fields read from the packet
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`layer 3 header. Alternatively, the network device may be a
`flow’s drop intervals that are smaller than the experimental
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`layer 2 switch, where the switch reacts to fields read from the
`average, and then dividing by the total number of drop
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`packet layer 2 header. Further, some network devices read
`intervals. Then, a value greater than 0.5 indicates a flow with
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`and react to fields read from the layer 4 header of a packet,
`more short drop intervals than the predicted median, and a
`SplunkInc.
`Exhibit 1029
`Page 17
`
`15
`
`
`
`20
`
`25
`
`
`
`30
`
`35
`
`
`
`40
`
`
`
`45
`
`
`
`50
`
`
`
`55
`
`
`
`60
`
`
`
`65
`
`
`
`Splunk Inc. Exhibit 1029 Page 17
`
`

`

`DETAILED DESCRIPTION OF AN
`
`
`ILLUSTRATIVE EMBODIMENT
`
`
`
`
`
`US 6,934,256 B1
`
`
`
`
`
`
`
`
`
`
`
`15
`
`
`
`20
`
`25
`
`
`
`30
`
`
`
`35
`
`
`
`
`
`40
`
`
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`
`
`
`
`
`45
`
`
`
`
`
`
`
`
`50
`
`
`
`
`
`55
`
`
`
`
`
`
`60
`
`
`
`
`
`
`65
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`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.
`
`
`
`
`
`
`
`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.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Turning now to FIG. 1, Computer Network 100 is shown.
`Thestatistical test is performed by comparing the DEM
`
`
`
`
`
`
`
`10
`
`
`
`
`
`
`
`
`
`
`
`Computer Network 100 represents a general computer net-
`value with the number 0.5, and in the event that the DEM
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`work, from a small local area network to the entire world-
`value is within a preselected range of 0.5,
`the flow is
`
`
`
`
`
`
`
`wide Internet. End-station 102 serves as a source station for
`
`
`
`
`
`
`
`
`identified as non-adaptive. The preselected range may be
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`transmission of data packets in this example, and end-station
`chosen between 0.45 and any numberlarger than 0.5.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`104 serves as a receiving station for the packets transmitted
`The preselected range may be dynamically selected in
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`by source station 102. As the packets traverse network 100
`response to DEM values of selected flows, especially as
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the IP source address of the packets is “S1”, representing
`congestion becomes worse at
`the network device. The
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`source station 102. The IP destination address of the packets
`non-adaptive flows may have a larger DEM value as mul-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`is “S2” representing station 104. Gateway 106 represents a
`tiple randomly arriving adaptive flows have packets dropped
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`network device through which the packets must pass ontheir
`on a random basis. The adaptive flows may beselected as a
`travels from source station 102 to destination station 104.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`subset of all flows,
`the subset having selected values of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Gateway 106 may bea layer 2 switch within the network
`DEMlessthan a largest value of DEM computedinaset of
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`100, may be a router operating at layer 3, or may be any
`flows, and the non-adaptive flows identified as those having
`other convenient intermediate network device. We refer to
`
`
`
`
`
`
`
`
`
`
`
`the larger values of DEM.
`
`
`
`
`
`
`
`
`
`
`
`
`gateway 106 as a “gateway” because it serves as a band-
`In an exemplary implementation of the invention,a clas-
`
`
`
`
`
`
`
`
`
`
`sifier reads indicia of a selected flow from at least one field
`
`
`
`
`
`
`
`
`
`width limiting feature in the path that the packets take from
`source station 102 to destination station 104.
`
`
`
`
`
`
`
`
`
`
`
`
`
`of a header of a packet received by the network device. The
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`A queue 108 within gateway 106 receives packets as they
`flow is then classified and steered away from the normal
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`arrive from source station 102, and serves as a buffer as the
`queue to a special queue, particularly in the event that the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`packets are transmitted by gateway 106 to destination station
`flow is found to be non-responsive. The special queue may
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`104. For example, queue 108 may be a rate limiting queue
`then operate at a lower priority, or drop packets,etc.
`
`
`
`
`
`
`
`
`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.
`
`
`
`
`
`
`
`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
`
`
`
`
`
`
`
`
`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
`
`
`
`
`
`
`
`
`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.
`
`
`
`
`
`
`
`Also, operation of a Random Early Detection (RED)
`
`
`
`
`
`
`gatewayis 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.
`
`
`
`
`
`
`
`
`
`Other documents concerning the RED algorithm are
`
`
`
`
`
`
`
`available on the Internet from the Lawrence Berkley Labo-
`
`
`
`ratory website.
`
`
`
`
`
`
`Turning now to FIG. 2, a control law implemented in a
`
`
`
`
`
`
`
`
`REDalgorithm is illustrated in graph 200. The horizontal
`
`
`
`
`
`
`
`
`axis 202 represents a quantity giving the amount by which
`
`
`
`
`
`
`
`
`queue 108 is full. A lower threshold is shownat point 204,
`
`
`
`
`
`
`
`
`and an upper threshold is shownat point 206. For example,
`SplunkInc.
`Exhibit 1029
`Page 18
`
`
`
`
`
`
`
`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;
`
`Splunk Inc. Exhibit 1029 Page 18
`
`

`

`
`
`US 6,934,256 B1
`
`
`
`
`
`
`
`
`
`
`
`
`6
`5
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`At block 326 the process counts the arriving packets and
`the lower threshold is set, for illustrative purposes, at a
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`drops packet number “Z”. By counting the arriving packets,
`filling quantity of 10%. Also, for example, the upper thresh-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`and dropping the “Z’th” packet, the RED algorithm imposes
`old 206 is shown as the queue being 100% full.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`the control law 200, by applying a probability for dropping
`Curve 210 translates the measure of how full the queueis,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`incoming packets, and applies that probability by choosing
`indicated on the horizontal axis,
`into a probability for
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`a random packet within the range of “1”to the inverse of the
`dropping packets. The probability for dropping packets is
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`probability. After dropping the “Z’th” packet, the process
`plotted on the vertical axis 212. For example, at or below the
`
`
`
`
`
`
`
`
`
`
`
`
`goes to block 328.
`lower threshold 204 in filling the queue, the probability for
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`At block 328 the process counts the remaining “N”
`dropping a packet is computed by curve 210 to be “0”.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`packets. After counting the remaining “N” packets as they
`Howeverat a slightly higher degree offilling of the queue,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`arrive at queue 108 of gateway 106,
`the process returns
`for example at 12% at point 214, the probability for drop-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`along path 310 to block 302 where the queue length is again
`ping a packet is computed by curve 210 to be 10% (prob-
`
`
`
`
`
`
`
`
`
`
`
`periodically tested.
`ability P equals 0.1). Further, as the queue becomes more
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Process 300 continues, for example, periodically testing
`filled, for example at point 216 where the queueis repre-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`queuelength at block 302, and dropping a randomly selected
`sented as 60% full, curve 210 computes the probability P for
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`packet at block 326 when the queue length is between the
`dropping a packet to be 0.5 at location 220, that is a 50%
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`lower threshold 204 and the upper threshold 206.
`probability for dropping a packet. When the queue filling
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`As an example, other indicia of congestion besides queue
`reaches the upper threshold 206, curve 210 indicates, at
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`length may be used as the control parameter in control law
`point 222 that the probability for dropping a packetis be 1.0,
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`200. For example, the control law 200 shownin FIG. 2 uses
`that is 100% (probability P of 1.0). That is, when the queue
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`queue length as a detection parameter for congestion. Other
`filling reaches the upper threshold 206, all packets arriving
`
`
`
`
`
`
`
`
`
`
`
`parameters showing congestion, or incipient congestion,
`at gateway 108 are dropped.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`may be computed at block 302, and a lower threshold and
`Turning now to FIG. 3, a flow chart 300 showing opera-
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`upper threshold for the other parameter tested so that in the
`tion of the RED gateway is shown. Particularly, flow chart
`25
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`event that the measured parameter lies between the lower
`300 shows howapacket is chosen for being dropped by the
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`threshold and the upper threshold, a randomly arriving
`RED gateway 106. Starting with block 302, the queue 108
`
`
`
`
`
`
`
`
`
`
`
`
`
`packet may be dropped at block 326.
`is periodically tested to determine the length of the queue.
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Turning now to FIG. 4, a timeline 400 for end-to-end
`After a queue length determination is made the process goes
`
`
`
`
`
`
`
`
`to block 304.
`
`
`
`operation of the packet transfer from source end-station 102
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`to destination end-station 104 is shown. For example, source
`At block 304 the queue length is tested to determineif it
`
`
`
`
`
`
`
`
`exceeds the lower threshold 204. In the ev