`
`(19) I *I Canadian
`Intellectual Property
`Office
`
`Office de la Propriete
`lntellectuelle
`du Canada
`
`(11) CA 2 310 531
`
`(13) A1
`
`(40) 02.12.2000
`(43) 02.12.2000
`
`An Agency of
`Industry Canada
`
`Un organisme
`d'lndustrie Canada
`
`
`
`(12)
`
`(21)
`
`2 310 531
`
`H04L 29/02, H04L 29/08
`Int. C|.7:
`(51)
`
`(22)
`01.06.2000
`
`(30)
`
`60/137,082 US 02.06.1999
`09/578,564 US 25.05.2000
`
`(72)
`
`FIROIU, VICTOR (US).
`BORDEN, MARTY (US).
`
`(71)
`
`NORTEL NETWORKS CORPORATION,
`World Trade Center of Montreal
`SMART & BIGGAR
`380 St. Antoine Street West
`
`8th Floor, MONTREAL, Q1 (CA).
`
`(74)
`
`(54)
`(54)
`
`METHODE ET APPAREILLAGE DE GESTION DE FILE D'ATTENTE
`METHOD AND APPARATUS FOR QUEUE MANAGEMENT
`
`
`
`N: may“
`
`(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 node is first
`systematically calculated. The weighted moving average
`is calculating and an average queue size 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 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
`
`
`
`OFFICE DE LA PROPRIE’TE’ INTELLECTUELLE DC CANADA
`
`OPIC
`
`(72) FIROIU, VICTOR, US
`
`(72) BORDEN, MARTY, US
`
`C I P O
`
`CANADIAN IN T ELL Ec rUAL
`
`(12)(19) (CA) Demande-Application
`
`PROPERTY OFFICE
`
`(21) (A1) 2,3 10,531
`(22)
`2000/06/01
`(43)
`2000/12/02
`
`(71) NORTEL NETWORKS CORPORATION, CA
`(51) Int.Cl.7 H04L 29/02, H04L 29/08
`(30) 1999/06/02 (60/137,082) US
`(30) 2000/05/25 (09/578,564) US
`(54) METHODE ET APPAREILLAGE DE GESTION DE FILE
`D’ATTENTE
`
`(54) METHOD AND APPARATUS FOR QUEUE MANAGEMENT
`
`‘5
`
`.
`
`I
`2
`Lgd—
`r .
`1.2—9
`
`LI&_M_ iiixr '
`5,»-
`‘ \ (
`5 Mass.
`1
`
`\
`\4
`
`,7
`
`.
`
`‘:“<
`x
`\m
`IN“
`()/L
`
`\
`
`My
`
`Narmfls
`
`(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 node is first systematically calculated. The weighted moving average is calculating and an average
`queue size 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 queue size is calculated. The weight is determined based upon
`the sampling period and the time period. In afurther embodiment, the control function is calculated based upon a queue
`function Where the queue function is calculated based upon predetelmined 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.
`
`I*I IndustrleCanada
`
`Industry Canada
`
`
`
`CA 02310531 2000-06-01
`
`ABSTRACT OF THE DISCLOSURE
`
`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
`
`node is first systematically calculated. The weighted moving average is calculating and
`
`an average queue size 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
`
`10
`
`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
`
`15
`
`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
`
`20
`
`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.
`
`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 Management in Routers and Switches” filed on June 2, 1999 which is
`
`incorporated by reference herein in its entirety.
`
`10
`
`15
`
`FIELD OF THE INVENTION
`
`The invention generally relates to networks and, more particularly, the invention
`
`relates to the management of a queue at a node in a network.
`
`BACKGROUND OF THE INVENTION
`
`Congestion occurs in a network when resource demands exceed capacity. In
`
`prior art communications networks, resource demands exceed capacity when data is sent
`
`on a path from a sender to a recipient and a node on the path cannot send data as quickly
`
`as it is received. In this case, the throughput of the node decreases and may drop to zero.
`
`20
`
`When the 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 lost. 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 buffer size,
`
`defined as accumulated packets waiting to be serviced, the average queue size 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 and large network delays is Random
`
`Early Detection (RED). RED is 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 number of acknowledgment packets
`
`that are sent to the sender. The congestion control mechanism in TCP is a closed control
`
`
`
`CA 02310531 2000-06-01
`
`system that reacts to unacknowledged packets 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 by a 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
`
`10
`
`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
`
`propagate to other nodes and cause erratic behavior in the network. Because RED does
`
`not define a methodology for calculating the parameters, system administrators have
`
`used trial and error techniques. These trial and error techniques do not provide for a
`
`15
`
`controllable network.
`
`SUNIMARY OF 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
`
`node is first systematically calculated. The weighted moving average is calculating and
`
`an average queue size 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 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
`
`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.
`
`5
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The foregoing and other objects and advantages of the invention will be I
`
`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 which the
`
`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
`
`15
`
`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 number of flows, the size of a packet, and the round
`
`trip transmission time.
`
`25
`
`Fi g. 10 shows a 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
`
`control function of the congestion control module.
`
`Fig. 11 is a flow chart showing the steps taken in calculating the point (qm,
`
`Pm“)-
`
`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 is 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 control module in which the
`
`queue law is used for long term adjustment of the drop probability.
`
`Fig. 17A shows an illustrative configuration module.
`
`Fig. 17B shows a control function module that resides within a congestion
`
`control module.
`
`. Fig. 18A shows a weight calculation module.
`
`Fig. 18B shows a congestion control module which is similar to the congestion
`
`control module of Fig. 13, but Fig. 18B also shows the data which is necessary for
`
`configuring the congestion control module prior to operation.
`
`DESCRIPTION OF SPECIFIC EMBODIMENTS
`
`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 be sent, received,
`
`and retrieved. All devices that forward and filter data, such as, but not limited to,
`
`10
`
`15
`
`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 nodes shall 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 node to a receiving node. In the
`
`25
`
`description and the claims the term “capacity” refers to the total amount of data that a
`
`link can process in a given time and is equivalent to line speed.
`
`Nodes within the network each have at 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 flows into the buffer, the
`
`queue becomes larger 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 sending rate at the sending node. For example, in a
`
`network employing TCP as the 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 sending rate 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 node to 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 embodiment in
`
`which TCP is the transport layer protocol. This is done for exemplary purposes and is in
`
`no way meant to 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
`
`down its sending rate, which has the effect of decreasing the size of the average queue in
`
`the buffer of the receiving node. As stated before, the average queue size 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 control 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
`
`referred to collectively together as a steady-state operating point.
`
`In a node that incorporates a congestion control 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
`
`15
`
`20
`
`25
`
`being a queue law function and a control function. Fig. 2 shows a 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 upon the traffic 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 can be:
`
`Gov) = min(B,c(T;‘(p.c/n)- Rel)
`
`
`
`
`
`__
`
`
`
`
`_
`
`
`
`
`
`Next the control function is determined (Step 220). The control function is
`
`characteristic of the node congestion control module. It determines the drop percentage
`
`when the buffer of the node is 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 be set and the control module uses the drop percentage to drop packets evenly
`
`across all flows (step 230).
`
`15
`
`The queue law may be 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 enabled to 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 minimum traffic conditions. This modeling of the queue can
`
`aid 21 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 control 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 two figures. Fig. 3
`
`shows a network that is used as a model for determining the queue law for a complex
`
`communications network. The network of 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
`
`known traffic characteristics for the node, such as, the line speed, number of TCP flows
`
`10
`
`and propagation delay. The queue law function determines an average queue size for 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 An, flow into node B, which
`
`contains a node congestion control module. Node B is connected to node C through a
`
`single link.
`
`20
`
`25
`
`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 round trip time R, the average packet size M, the average
`
`number of packets acknowledged in one acknowledgement message b, the maximum
`
`congestion window size advertised by the flow’s TCP receiver Wm“, and the duration of
`
`the basic TCP timeout To. The throughput of a TCP flow is approximately equal to
`
`Ttp,R)=
`
`1—
`
`
`W
`
`Mm if
`
`th)<Wm
`
`"52+ :p)+Q(p.W(p))
`timestw
`1_p W
`P
`
`_.____+
`max +Q(p,Wmux)
`'
`:7
`2
`M———'—— Otherwrse
`
`
`{Eu/mi. l-P zjw
`
`8
`
`meax
`
`l—p
`
`
`
`where
`
`CA 02310531 2000-06-01
`
`
`2+b+ 8(l-p)+ 2+1:
`W(P)=—
`"31'7““
`3!;
`3bp
`
`2
`
`_
`
`Qtp,w)—nun[1.
`
`-
`
`1-(1-
`
`)31+(1-
`
`” Hlfp).
`
`)31-(1-
`
`)W'3
`
`p
`
`]
`
`F(p)=1+p+2p2 +4p3 +8p“ +1611;5 +32p6
`
`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 which is 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 11 flows combine at the buffer of node B and each
`
`flow provides digital data that adds to the queue. One simplification of the model
`
`network that is used to determine the queue law function assumes that there is only one
`
`15
`
`link between two nodes. Additionally, packets of data are assumed to flow in only one
`
`20
`
`25
`
`direction. In Fig. 3 data flows from nodes A1-“ to nodes D”. The only data that flows in
`
`the other direction is assumed to be acknowledgment packets (ACKs). Further, the
`
`number of flows into node B is assumed to remains constant. Assuming that all flows
`
`have the same average round trip time and the same average packet size and that the
`
`maximum congestion window size is so large that it does not influence the throughput,
`
`the network may be reduced to a single-flow feedback system as shown in 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 and B is the only possible point of congestion, the average round trip time of
`
`a packet is the sum of the average waiting time in the queue of node B and R0, 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 q/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 round trip so that
`
`30
`
`R=Ro+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:
`
`u
`
`(p)
`
`=
`
`TULRO)
`C / n
`
`S
`
`The link utilization u(p) takes values between 0 (not utilized) 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(T;‘(p,c/n)— R0)
`
`where c is equal to the line speed and TR"(p,t) is the inverse of T(p,R) in R, i.e.,
`
`10
`
`TR'1(p,T(p,R)) = R. Since the average queue size cannot exceed the size of the buffer
`
`B, the queue law is:
`
`G(p) = maixLB,c(TR'1 (p, c/n)— R0 ))
`
`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 made that
`
`result in different equations for the utilization and the average queue size. For example,
`
`if the system is assumed to be free of TCP timeouts, the throughput T(p,R) can be
`
`approximated as
`
`M 3
`T(P.R)=m —
`R pr
`
`20
`
`and thus it can be easily shown that:
`
`l 3
`G(p) — m2){B,nM —2b—p —cRo]
`
`if the link is fully utilized, i.e., if u(p)=1 where
`
`, nM 3
`ma =——— ——
`CR0
`2bp
`
`The resulting queue law equation can be programmed into a processor or programmed in
`
`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 round trip
`
`time R, the number of flows, n, and the throughput or all variables necessary to calculate
`
`the throughput. For example, the minimum and maximum throughput per flow (1'min Imax)
`
`
`
`CA 02310531 2000-06-01
`
`which for a dial—up modem in a wide area network is 28.8Kb/s for rm,“ and 56Kb/s for
`
`rm however the speed of rm,“ and rmax the connection is implementation dependent.
`
`Additional traffic characteristics include the minimum and maximum packet sizes (Mm-n,
`
`Mm“) the minimum and maximum round trip time outside of the queue (Rom, Rom“) the
`
`minimum and maximum drop probability outside of the queue (p0min: pew) and the
`
`minimum and maximum TCP receiver window ((Wmax) min, (Wmax) max ).
`
`Fig. 6 shows a 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
`
`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
`
`queue size. The segment is 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 (gm, pm“) when the node is under normal operating
`
`conditions, i.e. there is not an unexpected change in any of the traffic conditions. For
`
`example, if a node normally handles up to 1000 simultaneous flows, and traffic
`
`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 queue size.
`
`15
`
`20
`
`25
`
`This segment is preferably designed with a steeper slope as shown in 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 (gm, pm“) and (qclip, 1) where qclip is defined, as
`
`shown in 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 segment B, like segment A, may be non-linear in
`
`shape.
`
`Although the intersection point is the point of convergence for the average queue
`
`size, the communications network may encounter various changes that 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 point if the system is stable. If the maximum value
`
`of the control function on segment A (qmax. pm“) 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 sending rate of the sending
`
`node varies, 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. qmax) 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 decay so that the oscillations of the system dissipate
`
`and the system returns to the equilibrium point. The maximum value (pmx, gm“) 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 number of flows, M, the average
`
`25
`
`packet size, and R, the average round trip time. As shown in Fig. 9 by the shaded region,
`
`the queue law may take on any value within this region dependent upon the values for n,
`
`M, and R. If the control function is originally set to control function A pictured in Fig. 9
`
`and the queue law curve is originally Gmin,
`
`the system is stable at initialization and large
`
`fluctuations do not occur in the average queue size. 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 becom