`
`(19) i. Canadian
`Intellectual Property
`Office
`
`Office de la Propriété
`Intellectuelle
`du Canada
`
`(11) CA 2 310 531
`(40) 02.12.2000
`(43) 02.12.2000
`
`(13) Aq
`
`An Agency of
`Industry Canada
`
`Un organisme
`d'Industrie Canada
`
`
`
`(12)
`
`HO4L 29/02, HO4L 29/08
`Int. Cl.”:
`(51)
`(21) 2310531
`
`(22)
`01.06.2000
`(30)
`
`60/137,082 US 02.06.1999
`09/578,564 US 25.05.2000
`
`(71)
`
`NORTEL NETWORKS CORPORATION,
`World Trade Center of Montreal
`SMART & BIGGAR
`380 St. Antoine Street West
`8th Floor, MONTREAL, @1 (CA).
`
`(74)
`
`(54)
`(54)
`
`METHODE ET APPAREILLAGE DE GESTION DEFILE D'ATTENTE
`METHOD AND APPARATUS FOR QUEUE MANAGEMENT
`
`(72)
`
`FIROIU, VICTOR (US).
`BORDEN, MARTY(US).
`
`cn, te TY Sroraae,
`(57)
`coneurel ae .an
`A method, apparatus, and computer program
`tes kK
`\
`»
`product for determining a drop probability for use in a
`P Jee Ne
`congestion control module
`located in
`a node
`in
`a
`_ 4
`network is disclosed. A weight value for determining a Nie dbTY)
`
`ao oe
`weighted moving average of a queue in a nodeis first
`f
`|
`systematically calculated. The weighted moving average
`i
`LIsomone
`is calculating and an average queue size for the node
`Ve
`
`“f- oN
`is determined based upon the weighted moving average.
`
`—
`
`1 tao
`
`Nerupee
`
`congestion
`the
`associated with
`function
`A control
`control module is evaluated using the average queue
`size to determine
`the drop probability. The weight
`value may be calculated by first determining a sampling
`period for measuring the queue size. Next,
`a time
`period for which
`samples
`significantly contribute
`to
`the average queue size is calculated. The weight
`is
`determined based upon the sampling period and the time
`period.
`In a further embodiment,
`the control
`function
`is calculated based upon a queue function where the
`queue function is calculated based upon predetermined
`system parameters. The control function may be selected
`based upon a queue policy for management of
`the
`queue. From the queue policy a threshold value which
`lies along the queue function curve is determined. This
`point provides a minimum value for the maximum point of
`the control
`function so as to avoid oscillations within
`the buffer. A maximum point may then be selected which
`resides outside of
`the curve for
`the queue function.
`The control
`function may then be selected so that the
`
`control function crosses through the maximum_point.
`Thus, when the congestion control module drops packets
`based upon the drop probability determined by the
`control
`function
`the
`queue
`will
`not
`oscillate.
`
`Junioer Exhibit 1006
`
`Junioer Exhibit 1006
`
`

`

`
`
`Conpers
`
`a
`
`: oN wet [1~emee
`
` INTELLECTUELLE DU CANADA
`
`OPrIc
`
`OFFICE DE LA PROPRIETE
`
`CIPO
`CANADIAN INTELLECTUAL
`PROPERTY OFFICE
`
`(12) (19) (CA) Demande-Application
`(21) (Al) 2.3 10,531
`(22)
`2000/06/01
`(43)
`2000/12/02
`
`(72) FIROIU, VICTOR, US
`(72) BORDEN, MARTY, US
`i) NORTEL NETWORKS CORPORATION, CA
`(51) Int.CL.” HO4L 29/02, HO4L 29/08
`(30) 1999/06/02 (60/137,082) US
`(30) 2000/05/25 (09/578,564) US
`64) METHODE ET APPAREILLAGE DE GESTIONDE FILE
`D’ATTENTE
`64) METHOD AND APPARATUS FOR QUEUE MANAGEMENT
`
`.
`
`d
`
`~ .
`
`ot "
`
`oe
`
`on
`NO
`nk
`\
`|
`fmA Ny
`:
`
`fan ‘ NN
`- al
`‘eB
`ATT
`
`ae
`\
`OQ “Neve
`i
`i{Ne
`belComPuTee
`J Neat
`
`‘
`
`:
`
`oN
`*%,
`
`7
`fe
`A
`
`Nerweex
`
`(57) A method, apparatus, and computer program product for determining a drop probability for use in a congestion
`control module located in a node in a network is disclosed. A weight value for determining a weighted moving average
`of a queue in a nodeis first systematically calculated. The weighted moving average 1s calculating and an average
`queue size for the node is determined based upon the weighled moving average. A control function associated with the
`congestion control module is evaluated using the average queue size to determine the drop probability. The weight
`value may be calculated by first determining a sampling period for measuring the queue size. Next, a time period for
`which samples significantly contribute to the average queue size 1s calculated. ‘The weight is determined based upon
`the sampling period and the time period. In a further embodiment, the control function 1s calculated based upon a queue
`funchion where the queue funchion 1s calculated based upon predetermined system parameters. The control function
`may be selected based upon a queue policy for management of the queue. Fromthe queue policy a threshold value
`which lies along the queue function curve is determined. This point provides a minimumvalue for the maximumpoint
`of the control function so as to avoid oscillations within the butter. A maximum point may then be selected which
`resides outside of the curve for the queue function. The control function may then be selected so that the control
`funcuion crosses through the maximum point. Thus, when the congestion control module drops packets based upon the
`drop probability determined by the control function the queue will not oscillate.
`
`i+ Industrie Canada
`
`Industry Canada
`
`

`

`CA 02310531 2000-06-01
`
`ABSTRACT OF THE DISCLOSURE
`
`A method, apparatus, and computer program productfor determining a drop
`probability for use in a congestion control module located in a node in a networkis
`disclosed. A weight value for determining a weighted moving average of a queue in a
`nodeis first systematically calculated. The weighted moving average is calculating and
`an average queuesize for the node is determined based upon the weighted moving
`average. A control function associated with the congestion control module is evaluated
`using the average queue size to determine the drop probability. The weight value may be
`calculated by first determining a sampling period for measuring the queue size. Next, a
`time period for which samples significantly contribute to the average queuesize 1s
`calculated. The weight is determined based upon the sampling period and the time
`
`period. In a further embodiment, the control function is calculated based upon a queue
`function where the queue function is calculated based upon predetermined system
`parameters. The control function may be selected based upon a queue policy for
`management of the queue. From the queuepolicy a threshold value which lies along the
`queue function curve is determined. This point provides a minimum value for the
`maximum pointof the control function so as to avoid oscillations within the buffer. A
`maximum point maythen be selected which resides outside of the curve for the queue
`function. The control function may then be selected so that the control function crosses
`
`10
`
`15
`
`20
`
`through the maximum point. Thus, when the congestion contro] module drops packets
`
`based upon the drop probability determined by the control function the queue will not
`
`oscillate.
`
`115003
`
`

`

`CA 02310531 2000-06-01
`
`Atty. Dkt. 2204/A05
`
`METHOD AND APPARATUS FOR QUEUE MANAGEMENT
`
`PRIORITY
`This application claims priority from United States Provisional Application
`
`60/137,082 entitled “Apparatus and Method of Design and Configuration of Active
`
`Queue Managementin Routers and Switches” filed on June 2, 1999 whichis
`
`incorporated by reference herein in its entirety.
`
`10
`
`15
`
`FIELD OF THE INVENTION
`
`The invention generally relates to networks and, moreparticularly, the invention
`
`relates to the managementof a queue at a node in a network.
`
`BACKGROUNDOF THE INVENTION
`
`Congestion occurs in a network when resource demands exceed capacity. In
`
`prior art communications networks, resource demands exceed capacity when datais sent
`on a path from a senderto a recipient and a node on the path cannot send data as quickly
`
`as itis received. In this case, the throughput of the node decreases and may dropto zero.
`
`20
`
`Whenthe throughput drops at the node, received packets build up in the node’s
`
`memory, referred to as a buffer, increasing the number of accumulated packets forming a
`
`queue until the buffer is full and overflows. As the buffer overflows, data at the receiver
`
`may be delayed or the data may be Jost. Such a state is generally a transient condition in
`
`a network as users of the network vie for resources during peak time periods. In the past,
`
`25
`
`nodes in high-speed networks have been forced to include large buffers in an attempt to
`
`avoid overflow during periods of congestion. As a result of increasing buffersize,
`
`defined as accumulated packets waiting to be serviced, the average queuesize increases.
`
`The average queue size for a buffer is the average number of packets present in the
`
`buffer.
`
`30
`
`One technique for avoiding large queues andlarge network delays is Random
`
`Early Detection (RED). REDis designed to accompany transport-layer congestion
`
`control protocols such as TCP and operates as a mechanism for regulating the amount of
`
`information that is sent to a node by decreasing the numberof acknowledgment packets
`
`that are sent to the sender. The congestion control mechanism in TCPis a closed control
`
`

`

`CA 02310531 2000-06-01
`
`system that reacts to unacknowledgedpackets by re-sending the unacknowledged
`packets and reducing the transmission rate. Systems that implement RED detect
`congestion by computing the average queue size as data is received into a buffer. When
`the average queue size exceeds a preset threshold, the node refuses to service i.e. “drops”
`
`a percentage of packets as determined bya control function.
`The queue sizes determined by the RED technique, in combination with TCP
`congestion control, are subject to large size oscillations. Using the RED technique,
`parameters defining the control function are set by a system’s administrator, without a
`methodology for determining values for the parameters. As such, the control function
`may be unstable and fail to adequately regulate the feedback to the TCP congestion
`control. The large oscillations that result under such circumstances in one node can
`
`propagateto other nodes and cause erratic behavior in the network. Because RED does
`not define a methodologyfor calculating the parameters, system administrators have
`
`used trial and error techniques. Thesetrial and error techniques do not provide for a
`
`10
`
`15
`
`controllable network.
`
`SUMMARYOF THE INVENTION
`
`A method, apparatus, and computer program product for determining a drop
`
`probability for use in a congestion control module located in a node in a network are
`
`disclosed. A weight value for determining a weighted moving average of a queue in a
`
`20
`
`nodeis first systematically calculated. The weighted moving averageis calculating and
`
`an average queuesize for the node is determined based upon the weighted moving
`
`average. A control function associated with the congestion control module is evaluated
`
`using the average queue size to determine the drop probability. The weight value may be
`
`calculated by first determining a sampling period for measuring the queue size. Next, a
`
`25
`
`time period for which samples significantly contribute to the average queuesize is
`
`calculated. The weight is determined based upon the sampling period andthe time
`
`period. In a further embodiment, the control function is calculated based upon a queue
`
`function where the queue function is calculated based upon predetermined system
`
`parameters. The control function may be selected based upon a queue policy for
`
`30
`
`management of the queue. From the queue policy a threshold value which lies along the
`
`queue function curve is determined. This point provides a minimum value for the
`
`maximum point of the control function so as to avoid oscillations within the buffer. A
`
`maximum point may then be selected which resides outside of the curve for the queue
`
`function. The control function may then be selected so that the control function crosses
`
`2
`
`

`

`CA 02310531 2000-06-01
`
`through the maximum point. Thus, when the congestion control module drops packets
`
`based upon the drop probability determined by the control function the queue will not
`
`oscillate.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`The foregoing and other objects and advantages of the invention will be )
`appreciated more fully from the following further description thereof with reference to
`
`the accompanying drawings wherein:
`
`Fig. 1 shows a schematic drawing of a communications network in whichthe
`
`10
`
`apparatus and method for queue management may be implemented.
`
`Fig. 2 is a flow chart for determining the steady state operating point of a queue.
`
`Fig. 3 shows a simplified network, which is used to simulate a more complex
`
`communications network.
`
`Fig. 4 is a block diagram showing another simplification of the network where
`
`1S
`
`the network is reduced to a single-flow feedback system.
`
`Fig. 5 is a sample plot of the queue law function.
`
`Fig. 6 is a graphical representation of the queue law function and the control
`
`function in which the axes are the average queue size and the drop percentage.
`
`Fig. 7 is a graphical representation of a control function.
`
`20
`
`Fig. 8 is a graphical representation showing two control functions superimposed
`
`upon the queue law function.
`
`Fig. 9 is a graphical representation of the ranges that the queue law function may
`
`take based upon the values for the numberofflows, the size of a packet, and the round
`
`trip transmission time.
`
`25
`
`Fig. 10 showsa flow chart of the steps used by either a designer of a congestion
`
`control module or of a system administrator setting the parameters for defining the
`
`contral function of the congestion control module.
`
`Fig. 11 is a flow chart showing the steps taken in calculating the point (qmax.
`
`Pmax).
`
`30
`
`Fig. 12 is a flow chart showing the steps taken in calculating the minimum buffer
`
`Size.
`
`Fig. 13 is a block diagram of another embodiment of a congestion control module
`
`containing a processor and a queue estimator.
`
`Fig. 14 1s a flow chart of the method used in calculating the value of the
`
`3
`
`

`

`CA 02310531 2000-06-01
`
`weight,w. in a queue estimator
`
`Fig. 15 is a graphical representation of the sending rate verses time for an
`
`exemplary communications network.
`
`Fig. 16 is an alternative embodiment of a congestion contro] module in which the
`
`queuelaw is used for long term adjustmentof the drop probability.
`
`Fig. 17A showsanillustrative configuration module.
`
`Fig. 17B shows a control function module that resides within a congestion
`
`control module.
`
`Fig. 18A shows a weight calculation module.
`
`10
`
`Fig. 18B shows a congestion control module whichis similar to the congestion
`
`control module of Fig. 13, but Fig. 18B also showsthe data which is necessary for
`
`configuring the congestion control module prior to operation.
`
`DESCRIPTION OF SPECIFIC EMBODIMENTS
`
`15
`
`Fig. 1 shows a schematic drawing of a communications network in which the
`
`apparatus and method for queue management may be implemented. The communications
`
`network, such as the Internet, connects computers and other processing devices to other
`
`computers, servers, and processing devices via nodes so that data may besent, received,
`
`and retrieved. All devices that forward and filter data, such as, but not limited to,
`
`20
`
`routers, bridges, b-routers, switches, repeaters and gateways will be referred to as nodes
`
`in the following description and claims and all connections between such nodesshall be
`
`referred to as links.
`
`In the following description and appended claims the term “flow”shall refer to a
`
`signal representative of data sent from a sending nodeto a receiving node. In the
`
`25
`
`description and the claims the term “capacity”refers to the total amountof data that a
`
`link can processin a given time and is equivalentto line speed.
`
`Nodes within the network each haveat least one ingress and one egress port. A
`
`node may receive multiple flows of data, usually in the form of packets, into one or more
`
`of the ingress ports where each flow is stored and queued in a buffer prior to routing the
`
`30
`
`data flow to an egress port in the node. As more information flowsinto the buffer, the
`
`queue becomeslarger until the capacity of the buffer is reached and then the subsequent
`
`data is lost. To prevent buffer overflow, the buffer of each node is regulated by a node
`
`congestion control module that operates in conjunction with an end-system congestion
`
`control module. The node congestion control module regulates the average queue size by
`
`4
`
`

`

`CA 02310531 2000-06-01
`
`indicating to the sending node that congestion is occurring at the receiving node. The
`end-system congestion control module refers to the part of the transport layer protocol |
`that is responsible for adjusting the sendingrate at the sending node. For example, in a
`network employing TCP asthe transport layer protocol, the node congestion control
`
`module drops acknowledgement packets to indicate congestion and the end-system
`
`congestion control module decreases the sending rate in response. In another example,
`
`the node congestion control module may send an acknowledgement packet from the
`
`receiver indicating that congestion is occurring and again the end-system congestion
`
`control module decreases the sendingrate at the sending node. It will be understood by
`
`10
`
`those of ordinary skill in the art, that any end-system congestion control module may be
`
`used which causes a sending nodeto adjust its sending rate as the result of congestion.
`
`Additionally, the node congestion control module would be designed to work in
`
`conjunction with the chosen end-system congestion control module. For the remainder of
`
`this disclosure, the end-system congestion control module will refer to an embodimentin
`
`15
`
`which TCPis the transport layer protocol. This is done for exemplary purposes andis in
`
`no way meantto limit the scope of the disclosed invention.
`
`In a TCP environment, when packets of data are dropped, the node does not send
`
`an acknowledgment packet to the sending node. As a result, the sending node slows
`
`downits sending rate, which has the effect of decreasing the size of the average queuein
`
`20
`
`the buffer of the receiving node. As stated before, the average queuesize is the average
`
`amount of data found in the node’s buffer. The average queue size shall be represented
`
`by q. The interaction between the node congestion contro] and the end-system congestion
`
`control has the effect of stabilizing the node's queue size and the rate it drops packets.
`
`The values of average queue size and drop probability in such a stable or steady state are
`
`25
`
`referred to collectively together as a steady-state operating point.
`
`In a node that incorporates a congestion contro] module and implements one
`
`embodiment of the invention for queue management, the steady-state operating point can
`
`be calculated based on the solution for a system of two equations. The two equations
`
`being a queue law function and a control function. Fig. 2 showsa flow chart for
`
`30
`
`determining the steady-state operating point. First the queue law is evaluated (step 210).
`
`This first function represents a characterization of the end-system's congestion control.
`
`In other words, the queue law function is an approximation of the average queue size of
`
`an exemplary queue in a node based uponthetraffic characteristics and the percentage of
`
`dropped packets. For example, one embodiment of the queue law equation that will be
`
`5
`
`
`
`

`

`CA 02310531 2000-06-01
`
`further explained and derived below canbe:
`
`G(p) = min(B, c(T¢'(p,c/n)- R,))
`
`
`Po Drop percentage
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Next the control function is determined (Step 220). The control function is
`
`characteristic of the node congestion control module. It determines the drop percentage
`
`whenthe buffer of the nodeis filled above a predetermined threshold based upon an
`
`10
`
`average queue size as an input parameter. The control function may be any type of
`
`function, but is preferably a linear function. The point of intersection between the queue
`
`law function and the control function determines a value to which the drop percentage
`
`should beset and the control module uses the drop percentage to drop packets evenly
`
`across all flows (step 230).
`
`15
`
`The queue law maybe used in variety of ways for the design, configuration, and
`operation of a congestion control module. In one embodiment, the congestion control
`
`module may be enabledto calculate both the queue law and the control function based
`
`upon input data concerning traffic characteristics, and determine the point of intersection
`
`of the functions thus determining the packet drop rate. In another embodiment, the queue
`
`20
`
`law may be used to model the queue variation for a node over all drop probabilities
`
`based upon maximum and minimumtraffic conditions. This modeling of the queue can
`
`aid a system administrator in determining configuration parameters for the control
`
`function of the congestion control module of a node in a network in order to avoid
`
`oscillations in the queue. In such an embodiment, a predefined contro! function exists in
`
`25
`
`the congestion control module that has a definable shape, and the queue law provides
`
`information for configuring the shape so that the system remains stable. In yet another
`
`embodiment, the modeling of the queue law based upon the expected maximum and
`
`
`
`

`

`CA 02310531 2000-06-01
`
`minimum traffic conditions can be used to define a range of operation for a node. The
`
`ranges of operation can then be used in the design of a node to determine the minimum
`
`buffer size.
`
`The derivation of the queue law function is shown in the next twofigures. Fig. 3
`
`showsa networkthat is used as a model for determining the queue law for a complex
`
`communications network. The networkof Fig. 3 is a simplification of a real network
`
`such as the Internet. In this simplified network, the transport layer protocol is TCP. The
`
`simplified network is used to determine a queue law function for a node based upon
`
`knowntraffic characteristics for the node, such as, the line speed, number of TCP flows
`
`10
`
`and propagation delay. The queue law function determines an average queuesizefor a
`
`buffer based upon a drop percentage, where the drop percentage is an independent
`
`variable.
`
`In the simplified network, a node congestion control module is situated in node
`
`B. The communications system acts as a feedback control system in which the control
`
`15
`
`module is the sending node, the controlling element is the node congestion control
`
`module, the feedback signal is the drop percentage, and the controlled variable is the
`
`sending rate. A total of n flows, from node A, through node A,, flow into node B, which
`
`contains a node congestion control module. Node B is connected to node C through a
`
`single link.
`
`20
`
`One function/operation of the node control module is to maintain the cumulative
`
`data rate of all flows below or equal to the link’s capacity so that the rate of the
`
`combined flows from node B, i.e. the throughput,is less than or equal to the capacity of
`
`the link between B and C. The throughput of a TCP flow is dependent on the drop
`
`percentage p, the average roundtrip time R, the average packet size M,the average
`
`25
`
`number of packets acknowledged in one acknowledgement messageb, the maximum
`
`congestion windowsize advertised by the flow’s TCP receiver Wmax, and the duration of
`
`the basic TCP timeout T,. The throughput of a TCP flow is approximately equal to
`
`2PAP) + Op.Wip)
`M ——#——*__________ if, W(p) < Wasa
`a{SepptjSPWEPDFore—P
`
`Woan
`1~-
`2
`Pp
`MS —aattherrwise
`R ow a l-p +2 l+ QOP.Wwp)
`PWanax
`1~ p
`
`T(p,R)=
`
`

`

`where
`
`CA 02310531 2000-06-01
`
`/[8-p)
`2+b
`W(p)=——+,|-—— +
`3b
`3bp
`
`(P)
`
`(2+)
`3b
`
`__f,
`
`Otp.w) =m E eee
`
`i-(@-p) N+(1- p)-G- p)””
`
`S
`
`F(p)=1+ pt+2p’?+4p? +8p* +16p* +32p°
`
`which was derived in Padhye, Firoiu, Towsley and Kurose A Stochastic Model of TCP
`
`RENO congestion Avoidance and Control Technical Report CMPSCI TR-99-02
`
`University of Massachusetts, Amherst 1999 whichis incorporated by reference herein in
`
`its entirety.
`
`10
`
`For discussion purposes, the assumption is made that all links into node B and
`
`out of node C have enough capacity. Accordingly, the link between B and C is the only
`
`link where congestion can occur. All n flows combineat the buffer of node B and each
`
`flow provides digital data that adds to the queue. One simplification of the model
`
`networkthat is used to determine the queue law function assumesthat there is only one
`
`15
`
`link between two nodes. Additionally, packets of data are assumedto flow in only one
`
`direction. In Fig. 3 data flows from nodes Aj. to nodes Dj... The only data that flows in
`
`the other direction is assumed to be acknowledgment packets (ACKs). Further, the
`
`numberof flows into node B is assumed to remains constant. Assumingthatall flows
`
`have the same average roundtrip time and the same average packet size and that the
`
`20
`
`maximum congestion windowsize is so large that it does not influence the throughput,
`
`the network may be reducedto a single-flow feedback system as shownin Fig.4.
`
`Based on aforementioned assumptions, the queue law =G(p) is determined
`
`(where is the average size of the queue and p is the drop probability). Since the link
`
`between A andB is the only possible point of congestion, the average roundtrip time of
`
`25
`
`a packet is the sum of the average waiting time in the queue of node B and Ro, the
`
`propagation and the round-trip transmission time outside the node. Assuming a FIFO
`
`(First and First Out) queuing scheme, the average waiting time in the queue is g/c and
`
`the overall round trip time for a packet is the sum of the average waiting time in the
`
`queue and the propagation and transmission time on the rest of the roundtrip so that
`
`30
`
`R=R,+q/c.
`
`Regulating the queue due to congestion is only relevant when the link is fully
`
`

`

`CA 02310531 2000-06-01
`
`utilized, since the average queue size is small otherwise. The link utilization can be
`
`determined through the following calculation:
`
`_ T(p,R,)
`u(p)=——
`
`Thelink utilization u(p) takes values between 0 (notutilized) and 1 (fully utilized). If it
`
`is determined that the link is fully utilized, the queue law function for providing the
`
`average queue size is:
`
`G(p) = c(Tz'(p,c/n)— R, )
`wherec is equal to the line speed and Ta’(pt) is the inverse of T(p,R) in R,ie.,
`Tr(p,T(p,R)) =R. Since the average queue size cannot exceed the size of the buffer
`
`10
`
`B, the queue law is:
`
`G(p) = max(B, ¢(7;' (p.c/n)-R, })
`
`A sample plot of the queue law function is provided in Fig. 5. It should be
`
`15
`
`understood by those skilled in the art that additional simplifications may be madethat
`
`result in different equations for the utilization and the average queue size. For example,
`
`if the system is assumedto be free of TCP timeouts, the throughput T(p,R) can be
`
`approximated as
`
`3
`M/
`T(p,R)=— |——
`R\2bp
`
`20
`
`and thusit can be easily shownthat:
`
`G(p)=maBt bphy
`| 3
`
`if the link is fully utilized,i.e., if u(p)=1 where
`
`AM|3
`u(p) =|
`cR,\2bp
`
`Theresulting queue law equation can be programmed into a processor or programmedin
`
`25
`
`software to be executed or embedded into an electronic chip associated with the node
`
`congestion control module for automatic calculation during operation of the node based
`
`upon traffic conditions. Traffic conditions include the line speed c and the roundtrip
`
`time R, the numberof flows, n, and the throughputor all variables necessary to calculate
`
`the throughput. For example, the minimum and maximum throughputper flow (tmin tmax)
`
`

`

`CA 02310531 2000-06-01
`
`which for a dial-up modem in a wide area network is 28.8Kb/s for t,,, and 56Kb/s for
`
`t.,, however the speed of t_,, and t_,, the connection is implementation dependent.
`
`Additional traffic characteristics include the minimum and maximum packet sizes (Mmin,
`
`Minax) the minimum and maximum roundtrip time outside of the queue (Romin, Romax) the
`
`minimum and maximum drop probability outside of the queue (pomin, Pomax) and the
`
`minimum and maximum TCPreceiver window (CWinax) mins (Wimax) max ):
`
`Fig. 6 showsa graphical representation of the queue law function and the control
`
`function in which the axes on which the functions are graphed are the average queue size
`
`(Y- axis) and the drop percentage (X-axis). The two functions are each dependent on
`
`10
`
`one variable that is the product of the other function and as a result, both functions
`
`intersect at a point. This intersection point is the expected equilibrium for the node based
`
`on the initial traffic conditions. The equilibrium point provides the drop percentage for
`
`the congestion control module so that data packets may be dropped as the data enters the
`
`buffer of the node to regulate the queue size. By dropping packets based upon a
`
`15
`
`percentage of packets entering the node, each flow is proportionally affected regardless
`
`of the sending rate of the particular flow.
`
`Fig. 7 is a graphical representation of the control function H(q) = p. In an
`
`exemplary embodiment, the control function is composed of two linear segments. The
`
`first linear segment, segment A, defines the expected operational range of the average
`
`20
`
`queue size. The segmentis selected to be linear for ease of design and management as a
`
`control system, although a non-linear segment can be substituted. The maximum point of
`
`the first segment defines the maximum expected values for the average queue size and
`
`the corresponding drop rate (qmax; Pmax) When the node is under normal operating
`
`conditions, i.e, there is not an unexpected changein any ofthetraffic conditions. For
`
`25
`
`example, if a node normally handles up to 1000 simultaneous flows, andtraffic
`
`conditions change producing 100,000 flows, such a scenario would cause the node to
`
`operate in overload outside of the normal operating conditions. The second linear
`
`segment, segment B, defines the overload operation range for the average queuesize.
`
`This segmentis preferably designed with a steeper slope as shownin Fig. 7, but does not
`
`30
`
`have an infinite slope, as an infinite slope creates a discontinuity and possible
`
`uncontrollable oscillations to the average queue size. The steeper slope of segment B
`
`allows the queue to degrade gracefully to its normal operational range along Segment A.
`
`Segment B is defined by points (¢max, Pmax} and (gclip, 1) where gclip is defined, as
`
`shownin Fig. 7, as the average queue size at which there is a one hundred percent drop
`
`10
`
`

`

`CA 02310531 2000-06-01
`
`rate. It should be understood that segmentB, like segment A, may be non-linear in
`
`shape.
`
`Althoughthe intersection point is the point of convergence for the average queue
`
`size, the communications network may encounter various changesthat affect the queue
`
`law and cause fluctuations affecting the average queue size of the node. These transient
`
`fluctuations are normal in complex communications networks and the queue average will
`
`eventually return to the equilibrium pointif the system is stable. If the maximum value
`
`of the control function on segment A (qmax: Pmax) lies below the equilibrium point and
`
`thus inside of the queue law function, the transient behavior of the system is unstable
`
`10
`
`causing the queue size to fluctuate in an oscillatory pattern. The average queue size can
`
`oscillate between empty and full buffer, causing the packet drop percentage to vary
`
`between zero and 100%. As packets are dropped and the sendingrate of the sending
`
`nodevaries, a similar state can occur in the queue of the sending node. As such,the
`
`oscillations may reverberate throughout the communications network.
`
`15
`
`Fig. 8 shows two control functions superimposed upon the queue law function. In
`
`control function A the expected maximum value (pmax, @max) for the control function lies
`
`above the equilibrium point and therefore outside of the queue law function, allowing the
`
`transient response of the system to decayso that the oscillations of the system dissipate
`
`and the system retumsto the equilibrium point. The maximum value (Pmax. @max) Of
`
`20
`
`control function B is shown to be below the equilibrium point and therefore inside the
`
`queue law function which results in the average queue size fluctuating causing
`
`oscillations in the queue and throughout the communications network.
`
`It should be understood by those skilled in the art that the queue law can have
`
`various curves depending on the input values of n, the numberof flows, M, the average
`
`25
`
`packet size, and R, the average roundtrip time. As shown in Fig. 9 by the shaded region,
`
`the queue law may take on any value within this region dependent upon the valuesfor n,
`
`M,and R.If the control function is originally set to control function A pictured in Fig. 9
`
`and the queue law curveis originally Gin,
`
`the system is stable at initialization and large
`
`fluctuations do not occur in the average queuesize. If the parameters n, M, and R change
`
`30
`
`to their maximum, maximum, and minimum values respectively during the course of
`
`operation of the node, the queue law curve would then become Gmax, and the control
`
`function A would