l|||||||||||||||||||||||||||||||||l||||||||||||||||||||||||||||||||||||||||
`
`U3006934256B].
`
`(12) United States Patent
`Jacobson et at.
`
`{10) Patent N0.:
`
`(45) Date of Patent:
`
`US 6,934,256 B1
`Aug. 23, 2005
`
`(54} METHOD OF DETECTING
`NON-RESPONMVE NEIWORK I‘LOWS
`1
`-
`1
`1
`1.:v
`t.
`w dsd (.A URL
`) we" mg FE: ‘33::(:Xliugsfkmhieen)’
`Nicllflls, “roadside, (.‘A (’US)
`
`75
`
`(
`
`(73) Assignee: Cisco Technology, lnc., San Jose, CA
`(US)
`
`.
`I
`
`OTHER PUBLICATIONS
`Sally l-‘loyd and Van Jacobson Random Early Detection
`Gatcwa s for Con cstion Avoidance AUG. 1993
`. 1—22.
`Y
`g
`a!
`PP
`V. Jacobson, K. Nichols, K. Poduri Cisco Systems RED in
`a Diflcmnl Light Scp 30. 1999 pp. 1‘38t
`Van Jacobson Notes on using RED for Queue Management
`and Congestion Av01danee 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 Exmm'nermRhonda Murphy
`(74} Atlanta}; Agent, or Firrrt—Cesart and McKenna, LLP
`
`2
`
`0.:
`
`09;“769 544
`,
`
`Jan. 25’ 2001
`
`{56)
`
`1 N
`1
`App .
`9
`:‘
`.
`(2“)
`1 mid
`5.
`'
`1 .7
`3701;232:475 £322?
`$5.1?) Ll]; (SI
`
`370 1’35 :35 '1
`‘5: F: Id f9]
`0 Learn """"""""""""""£7004; 46141,;
`(‘
`l
`19
`"“ ’
`’
`‘
`‘
`.
`References Cited
`U.S. PA'l'le'l‘ [)(JCUMEN'I‘S
`b 646 988 Bl * “£2th Nandy cl at
`6,600.645 Bl *
`2;“2004 chya et at.
`newscast: At *
`”#2002 Acevcs ct at.
`
`
`
`370t235
`3703230
`370930
`
`57)
`
`ABSTRACT
`-
`
`Anctwork 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
`reacts indieia 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 [he
`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 flours in order to identify the non-adaptive flow.
`
`20 Claims, 15 Drawing Streets
`
`310
`
`302
`
`PERIODICALLY TEST
`0U EUE LENGTH
`
`
`
`EXC EEDED
`
`LOWER THRESHOLD
`
`NO NEGATNE
`YES
`FEEDBACK
`
`
`EXC EEDED
`U PPE R TH RESHOLD
`
`
`
`
`316
`DROP ALL
`ARRNING PACKETS
`
`APPLY CONTROL LAW
`TO CALCULATE
`P
`THE DROP PROBABILlT‘I’
`
`
`
`
`322
`
`324
`
`326
`
`328
`
`COMPUTE;
`
`N=1tP IN AN INTEGER VALUE]
`
`ONE PACKET IN “N"
`MUST BE DROPPED
`
`
`CHOOSE A RANDOM
`
`NUMBER BETWEEN:
`1 AND N
`CHOOSE Z
`
`
`COUNT ARRIVING PACKETS
`AND DROP NUMBER '2“
`
`
`
`COUNT REMAINING
`N PACKETS
`
`Palo Alto Networks V. Sable Networks
`
`IPR2020-01712
`
`EX 1 029
`
`EX1029
`Palo Alto Networks v. Sable Networks
`IPR2020-01712
`
`

`

`US. Patent
`
`Aug. 23, 2005
`
`Sheet 1 0f15
`
`US 6,934,256 B1
`
`
`
`FIG. 1
`
`

`

`US. Patent
`
`Aug. 23, 2005
`
`Sheet 2 0f 15
`
`Us 6,934,256 B1
`
`PROBABILITY
`
`29—0
`
`212
`
`10
`
`0.5 0.1
`
`222
`
`220
`
`204 10%
`
`12% 214
`
`60%
`
`100%
`
`202
`
`LOWER
`THRESHOLD
`
`UPPER
`THRESHOLD
`
`CONTROL LAW CURVE
`
`FIG. 2
`
`

`

`US. Patent
`
`Aug. 23, 2005
`
`Sheet 3 0f 15
`
`US 6,934,256 B1
`
`30
`
`302
`
`PERIODICALLY TEST
`QUEUE LENGTH
`
`304
`
`
`EXCEEDED
`
`
`LOWER THRESHOLD
`
`
`
`YES
`
`306
`
`NO
`
`308
`
`NO NEGATIVE
`FEEDBACK
`
`312
`
`
`
`
`
`EXCEEDED
`
`UPPER THRESHOLD
`
`
`
`
`
`314
`
`YES
`
`316
`
`DROP ALL
`ARRIVING PACKETS
`
`320
`
`322
`
`324
`
`326
`
`328
`
`APPLY CONTROL LAW
`TO CALCULATE
`p
`THE DROP PROBABILITY
`
`COMPUTE:
`N=‘I/P [N AN INTEGER VALUE]
`ONE PACKET IN "N"
`MUST BE DROPPED
`
`
`
`CHOOSE A RANDOM
`NUMBER BETWEEN:
`1 AND N
`
`CHOOSE Z
`
`COUNT ARRIVING PACKETS
`AND DROP NUMBER “2"
`
`COUNT REMAINING
`N PACKETS
`
`FIG. 3
`
`310
`
`

`

`US. Patent
`
`Aug. 23, 2005
`
`Sheet 4 0f 15
`
`Us 6,934,256 B1
`
`402
`
`406
`
`408
`
`410
`
`412
`
`
`
`
`EVENT
`
`_"
`
`SOURCE STATION BEGINS DATA TRANSMISSION
`
`A WINDOW OF SIX PACKETS IS TRANSMITTED
`(PIPE NOT FULL)
`
`PACKET #1 REACH ES GATEWAY AND IS FORWARDED
`
`PACKET #2 REACH ES GATEWAY AND 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 REACH ES GATEWAY AND 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
`SOURCE STATION INCREASES WINDOW WIDTH BY ONE (1) PACKET
`SUCCESSFUL TRANSMISSIONS WITH ACKS FOR "x" PACKETS
`SOURCE STATION INCREASES WINDOW WIDTH BY ONE (1) PACKET
`E > 438
`GATEWAY DROPS A PACKET DUE TO CONG ESTION
`
`' > 442
`
`ADAPTIVE FLOW TIME LINE
`
`FIG. 4
`
`414
`
`416
`
`418
`
`420
`
`422
`
`424
`
`426
`
`428
`
`
`
`
`
`ADAPTIVECYCLETIME
`
`
`440
`
`430
`432
`434
`436
`439
`
`
`

`

`US. Patent
`
`Aug. 23, 2005
`
`Sheet 5 0f 15
`
`Us 6,934,256 B1
`
`DROP
`POINT
`
`506
`
`
`
`512
`440
`
`T
`
`502
`
`ADAPTIVE CYCLE TIME
`FOR ONE FLOW
`
`FIG. 5
`
`

`

`US. Patent
`
`Aug. 23, 2005
`
`Sheet 60f 15
`
`US 6,934,256 B1
`
`TRANSMISSION
`
`RATE
`
`NON ADAPTIVE FLOW
`
`600
`
`I 604
`
`602
`
`FIG. 6
`
`

`

`US. Patent
`
`Aug. 23, 2005
`
`Sheet 7 0f 15
`
`US 6,934,256 B1
`
`2mm:
`
`/\
`
`<E:55:"
`
`_______
`
`anEOmo
`
`ooh
`
`
`
`DmmaomaanEOmoownflomoowamomo
`
`
`
`
`
`
`
`SEE.69v53BE:03003”an:woeDoomUoowmach(we
`
`I_fi_H__.fl__
`
`n.07.
`
`
`
` BEmmm___Nm~_Nun9:.—cm“ EEa?mm.”3»vm~III
`
`___________
`
`x0:
`
`_
`
`3:."
`
`_
`
`8:.“
`
`mot.
`
`mot.46:
`
`m>Em<
`
`>¢§ww<oP4
`
`QMDKSSMOL
`
`>$Smw<o>m
`
`

`

`US. Patent
`
`Aug. 23, 2005
`
`Sheet 8 0f 15
`
`Us 6,934,256 B1
`
`80
`
`7L6“
`
`DENSITY FUNCTION FOR RANDOM
`DROP INTERVALS
`
`804
`
`810
`
`812
`
`814
`805
`
`816
`
`818
`
`820
`
`822
`
`824
`
`DROP
`INTERVAL
`302 (TIME)
`
`FIG. 8
`
`

`

`US. Patent
`
`Aug. 23, 2005
`
`Sheet 9 0f15
`
`US 6,934,256 B1
`
`900
`
`STATE MAINTAINED FOR DROPPED PACKETS
`
`TIME OF
`DROP
`
`;
`
`:
`
`PACKET
`N
`
`FLOW
`IP SA
`IP DA
`(OTHER
`
`INDICIA)
`
`902
`
`904
`
`905
`
`FIG. 9
`
`

`

`US. Patent
`
`Aug. 23, 2005
`
`Sheet 10 0f 15
`
`US 6,934,256 B1
`
`10,000
`
`FLOW ANALYSIS FOR DROPPED PACKETS
`
`TIME OF
`DROP
`
`DROP INTERVAL
`= T(TH!S) ~T(LAST)
`
`;
`
`FOR EACH FLOW
`
`PACKET
`
`N
`
`T
`
`10,002
`
`10,004
`
`10,006
`
`FIG. 10
`
`

`

`US. Patent
`
`Aug. 23, 2005
`
`Sheet 11 0f 15
`
`US 6,934,256 B1
`
`
`
`mgofixwmoma..m._‘
`
`
`
`
`
`
`
`mELm>_._.<._rzmmmm_n_mmKDOmozq
`
`
`
`mmoME.mo;Dmoommw:...z.mmomonoZOFoém
`
`
`
`ozoomm2.E22.20:43:55
`
`on:om?omm9mm0mmomwomm
`
`o
`
`mw
`
`:.O_n_
`
`
`
`omEEmmmnzh
`
`mod
`
`mod
`
`3.0
`
`No.0
`
`(180033 NI SdOHG dO NOliOVHd
`
`

`

`US. Patent
`
`Aug. 23, 2005
`
`Sheet 12 0f 15
`
`US 6,934,256 B1
`
`
`
`«50u_O230m:Jihzwzomxw20mmmmakmfin—woQmN_._<§mOz
`
`
`
`
`
`
`
`
`
`mnzh.m>_._..E.zmmm_mn.wmmama02.4.
`
`NV.0.“—
`
`(.0
`8.
`
` m8“E
`
`'d'
`8.
`
`
`
`0200mm2_m2;ZO_H<._3§m
`
`
`
`om:om?ommomwom»oneommomw
`
`mad
`
`ed
`
`mmd
`
`md
`
`3.0
`
`v.9
`
`mmd
`
`md
`
`mud
`
`NVIGEIIN 'IVIlNEINOcIXEI 3H1
`
`WOHd EltlfliHVdEICl
`
`

`

`US. Patent
`
`Aug. 23, 2005
`
`Sheet 13 0f 15
`
`US 6,934,256 B1
`
`
`
`$8.95
`
`wBOfiEaOmDgm;
`
`9:8795
`
`mat4.3024
`
`9,.0E
`
`
`
`mmom5.m0;0100mm$2.7:wmomm“.0zo_ko<mm
`
`
`
`0200mm2_msE.zo_._.<._:E_m
`
`com?82,comcom
`
`cow
`
`mg
`
`to
`
`mod
`
`080038 NI SdOEICI :IO NOIlOVHd
`
`

`

`US. Patent
`
`Aug. 23, 2005
`
`Sheet 14 0f 15
`
`US 6,934,256 B1
`
`
`
`
`
`mmomo2.3092._(_._.zmonxmEOEmanhmxflmoDmN_._(§mOZ
`
`_,-n_._.m
`
`mEoo
`
`am:om?0mmommomm0mmommomv
`
`
`
`0200mm2_E22.20:33:45
`
`NVICIEIIN 'IVIlNEINOdXEI EIHl
`
`WOEH BHHlHVdEG
`
`
`
`man._._.4024.
`
`3‘.O_n_
`
`

`

`US. Patent
`
`Aug. 23, 2005
`
`Sheet 15 0f 15
`
`Us 6,934,256 B1
`
`
`
`
`15,010
`15,010A
`
`15,012
`15.012A
`
`15,014
`15,014A
`
`15,009
`
`
`
`15,016A
`
`15.01?
`
`
`
`SWITCH FABRIC
`
`15,016
`
`FIG. 15
`
`

`

`US 6,934,256 131
`
`1
`METHOD OF DETECTING
`NON-RESPONSIVE NETWORK FLOWS
`
`FIELD OF THE INVENTION
`
`'th is 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 difierent 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. I-‘lows 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 dill'erent
`combinations of fields to identify the flow, including fields
`from the layer 2 header,
`the layer 3 header,
`the layer 4
`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
`
`in the
`the packet was received. For example,
`know that
`TCPIIP 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.
`TCPIIP is an “adaptive tlow” 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 How. One method of regulating a transmission rate of
`packets is the use of a sliding window, as is implemented in
`the TCPt'IP protocol. TCPi’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 TCPFIP, 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 TCPIIP 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,
`
`‘JI
`
`It)
`
`15
`
`toU!
`
`3!]
`
`4E}
`
`45
`
`SD
`
`55
`
`60
`
`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-
`sion techniques. An end node which does not adapt
`is
`referred to as producing a "non-adaptive" flow. A non-
`adaptivc flow is frequently bad for the computer network,
`because for flows through a congested network device the
`adaptive transmitter will reduce its [low 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.
`A method of identifying non-adaptive [lows 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
`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
`used to test for non-adaptive [lows 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-[low basis, where a “flow" is indi-
`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
`other work of the network device.
`
`the net-
`In an exemplary embodiment of the invention,
`work device caleulates 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.
`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
`dropped packet was dropped. The statistical test
`is per—
`formed hy 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
`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
`an exponential density function, the median drop interval is
`expected to be 0.693 times the average drop interval.
`Aquantity referred to as the "Departure from Exponential
`Mean" (DEM) is computed by determining the number of a
`fiow’s drop intervals that are smaller than the experimental
`average, and then dividing by the total number of drop
`intervals. Then, a value greater than 05 indicates a [low with
`more short drop intervals than the predicted median, and a
`
`

`

`US 6,934,256 I31
`
`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 [lows should he 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 [lows may have a larger DEM value as mul-
`tiple randomly arriving adaptive flows have packets dropped
`on a random basis. The adaptive Ilows 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
`
`‘JI
`
`I0
`
`15
`
`oi‘a header ofa packet received by the network device. The
`How 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.
`
`3E]
`
`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. 1'1 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;
`
`40
`
`45
`
`50
`
`55
`
`60
`
`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.
`
`DETAILED DESCRIP'I'ION ()FAN
`ILLUSTRATIVE EMBODIMENT
`
`Turning now to FIG. 1, Computer Network 100 is shown.
`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 oidata packets in this example, and end-station
`104 serves as a receiving station for the packets transmitted
`by source station 102. As the packets traverse network 100
`the 11’ source address of the packets is “81”, representing
`source station 102. The Il’ destination address of the packets
`is "$2" representing station 104. Gateway 106 represents a
`network device through which the packets must pass on their
`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-
`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
`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 butler 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”, lEEEtACM Transactions on Net-
`working, August 1993, all disclosures of which are incor-
`porated herein by reference.
`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 o Drfl'crem
`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.,.Iune 1998, avail-
`able on the Internet.
`
`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 fllustrated in graph 200. The horizontal
`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,
`
`

`

`US 6,934,256 131
`
`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 horimntal 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 2'14, the probability for drop-
`ping a packet is computed by curve 210 to be 10% (prob-
`ability I’ 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 iiow 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.
`the lower
`that block 304 tests “yes", that
`In the event
`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 ”I’” 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 I and “N” which is chosen is
`
`represented by the symbol "Z". Upon choosing the random
`number “2” which lies between “1” and “N", the process
`goes to block 326.
`
`‘JI
`
`It)
`
`15
`
`3t]
`
`40
`
`45
`
`SD
`
`55
`
`60
`
`6
`At block 326 the process counts the arriving packets and
`drops packet number “2.”. 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
`incoming packets, and applies that probability by choosing
`a random packet within the range of“ l” 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”
`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
`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
`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
`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 cnd—to-end
`operation of the packet transfer from source end—station 102
`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 'I‘CPEIP protocol, which
`is an adaptive protocol for reliable packet
`transfer. The
`TCPIIP protocol is used in the Internet for many types of
`data transfer. The TCPEIP protocol
`is described by W.
`Richard Stevens in his book: 'I‘CPIIP Illustrated, Vol. 1, Vol.
`2, Vol. 3, published by Addison Wesley, Copyright date
`1994, all disclosures of which are incorporated herein by
`reference.
`In short, the TCPt’lP protocol requires that the destination
`station transmit an acknowledgement message (ACK) to the
`source station, upon receipt by the destination station 104 of
`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
`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
`adaptive nature of the source end-station executing the
`'I'CPth 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
`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,
`TCPt'IP illustrated, vol. 1.
`The timeline 400 indicates principal events in the adaptive
`process of the TCPJIP protocol, as an example of an adaptive
`
`

`

`US 6,934,256 I31
`
`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.
`
`time 414 packet number 4 reaches gateway 106.
`At
`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, the destination station
`104 receives packets number 1, number 2 and number 3.
`Also, destination station 104 sends ACKs for packets num-
`ber 1, number 2, and number3, to source station 102. At time
`422 the source station 102 receives the ACKs for packets
`number 1, number 2 and number 3.
`At time 424 source station 102 times out its retransmit
`timer for packet number 4. That is, no ACK is received by
`source station 102 for packet number 4 because packet
`number 4 was dropped at time 414 by gateway 106. Also,
`beginning at time 424 the source station 102 reduces its
`window by a factor “F”. In commonly implemented TCP/IP
`protocols in source stations, the window is reduced by a
`factor of 2, that is “I?” is "2“. Also, in accordance with the
`'I‘Cl’r’tl’ protocol the source station doubles the time-out time
`for
`the retransmit
`timer. The retransmit
`timer timing is
`doubled on the assumption that the timer time interval is too
`short for the rounrltrip time in the network, and so this
`feature of TCPEIP assists the source station in adapting its
`timer specification to actual round trip times in the network.
`Also at
`time 424 the source station retransmits packet
`number 4.
`
`At time 426 the destination station 104 receives packet
`number 4. Also at
`time 426 the destination station 104
`
`transmits an ACK for packet number 4 to source station 102.
`At
`time 428 the source station receives the ACK for
`packet number 4.
`At time 430 it is determined that successful transmission
`
`of packets from source station 102 to destination station 104
`for a number of packets represented by “X" has been
`accomplished. That is, source station 102 transmitted “”X
`packets addressed to destination station 104, and received
`ACK messages for each of those packets before the retrans-
`mit timer of source station 102 expired.
`Upon the successful completion of transmission of “X”
`packets to the destination end—station, at time 432 the source
`station increases its window width by one packet, in order to
`increase the rate at which it
`transmits packets into the
`network. It is common in implementations of TCPIIP for the
`number "X" to be selected as 4. Thus upon the successful
`transmission of four packets the window width of the source
`station is increased by one packet. At time 434 it is deter-
`mined that another number of "X" packets have been
`successfully transmitted from source station 102 to destina—
`tion station 104, and so at
`time 436 the source station
`increases its window width by another one packet.
`
`3‘
`
`It)
`
`15
`
`toU"
`
`3!]
`
`4E}
`
`45
`
`SD
`
`55
`
`60
`
`8
`indicated by the "three
`During the time interval 438,
`dots”, the source station successfully transmits a plurality of
`a number “X" of packets to destination station 104, and has
`increased its transmission rate by incr