then wg should be chosen to satisfy the following equation we compare two methods for calculating the final packet for aug minth marking probability, and demonstrate the advantages of the second method. In the first method when the aver L+1+ (1-n)2+1 <minth constant the number of arriving packe between marked packets is a geometric random variable Given minth =5, andL=50, for example, it is neces- the second method the number of arriving packets be <0.0042 tween marked packets is a uniform random variable. The initial packet-marking probability is computed as follows 6.2 A lower bound for w RED gateways are designed to keep the calculated average P matp(aug-minth/(maTth -minth queue size aug below a certain threshold. However, this The parameter ma. tp gives the maximum value for the serves little purpose if the calculated average au g is not a packet-marking probability po, achieved when the average reasonable reflection of the current average queue size. If wq is set too low, then avg responds too slowly to changes Method 1: Geometric random variables. In Method in the actual queue size. In this case, the gateway is unable 1, let each packet be marked with probability p. Let the to detect the initial stages of congestion intermarking time X be the number of packets that arrive Assume that the queue changes from empty to one after a marked packet, until the next packet is marked packet, and that, as packets arrive and depart at the same because each packet is marked with probability pu rate, the queue remains at one packet. Further assume that initially the average queue size was zero. In this case it ProbX =n]=(1-p) takes-1In(1 -wg) packet arrivals(with the queue size remaining at one)until the average queue size aug reachs Thus with Method 1, X is a geometric random variable 0.63=1-1/e[5]. For wg =0.001, this takes 1000 with parameter p, and E[X]=1/p packet arrivals, for wg =0.002, this takes 500 packet ar- With a constant average queue size, the goal is to mark rivals, for wg=0.003, this takes 333 packet arrivals. In packets at fairly regular intervals. It is undesirable to have most of our simulations we use wg =0.002 too many marked packets close together, and it is also undesirable to have too long an interval between marked 6.3 Setting minth and mac packets. Both of these events can result in global synchro- The optimal values for minth and maTth depend on the nization, with several connections reducing their windows desired average queue size. If the typical traffic is fairly X is a geometric random variable. bursty, then minth must be correspondingly large to al- Method 2: Uniform random variables. a more de- low the link utilization to be maintained at an acceptably sirable alternative is for X to be a uniform random vari- high level. For the typical traffic in our simulations, for able from [1, 2, 1/po)(assuming for simplicity that connections with reasonably large delay-bandwidth prod- 1/p is an integer). This is achieved if the marking prob- ucts, a minimum threshold of one packet would result in ability for each arriving packet is po/(1-count. pb unacceptably low link utilization. The discussion of the where count is the number of unmarked packets that have optimal average queue size for a particular traffic mix is arrived since the last marked packet. Call this Method 2 left as a question for future research In this cas The optimal value for matth depends in part on the maximum average delay that can be allowed by the gate- Prolx-nl 1-(n-1)po 1-i way The RED gateway functions most effectively wher narth-minth is larger than the typical increase in the for1<n≤1/P alculated average queue size in one roundtrip time. A useful rule-of-t to set matth to at least twice minth Prob[X=n]=0 for n >1/pb 7 Calculating the packet-marking prob-Figure shows an experiment comparing the two meth ability ods for marking packets. The top line shows Method I, where each packet is marked with probability p, for The initial packet-marking probability p is calculated as p=0.02. The bottom line shows Method 2, where each a linear function of the average queue size. In this section packet is marked with probability p/(1+ip), for p=0.01then ❂❅❄ should be chosen to satisfy the following equation for ✆✠✝✠✟✡➓➋✗✖☛✌☞✎✍✑✏✓✒ : ➒➙❈ ✵ ❈ ✫❇✵ ✬✮❂➡❄❞✯ ➓★➛ ↔ ✬ ✵ ❂❄ ✗✖☛✤☞✥✍✑✏✓✒★✳ (3) Given ☛✤☞✥✍✑✏✓✒◗t ✇ , and ➒➢t ✇ ✿ , for example, it is neces￾sary to choose ❂❅❄◆✔ ✿ ✳ ✿✡✿❣➤❛✉. 6.2 A lower bound for ➐✕➑ RED gateways are designed to keep the calculated average queue size ✆✞✝✡✟ below a certain threshold. However, this serves little purpose if the calculated average ✆✞✝✠✟ is not a reasonable reflection of the current average queue size. If ❂❅❄ is set too low,then ✆✠✝✠✟ responds too slowly to changes in the actual queue size. In this case,the gateway is unable to detect the initial stages of congestion. Assume that the queue changes from empty to one packet, and that, as packets arrive and depart at the same rate, the queue remains at one packet. Further assume that initially the average queue size was zero. In this case it takes ✬ ✵ ✰✻➥❥➦ ✫❇✵ ✬✮❂❄ ✯ packet arrivals (with the queue size remaining at one) until the average queue size ✆✞✝✠✟ reachs ✿ ✳ ➧✡➊✮t ✵ ✬ ✵ ✰❣❏ [35]. For ❂❄ t ✿ ✳ ✿✡✿ ✵ , this takes 1000 packet arrivals; for ❂❄ t ✿ ✳ ✿✡✿✞✉, this takes 500 packet ar￾rivals; for ❂❅❄❺t ✿ ✳ ✿✠✿➊, this takes 333 packet arrivals. In most of our simulations we use ❂❅❄❅t ✿ ✳ ✿✡✿✠✉. 6.3 Setting ➨➫➩✱➭➲➯➵➳ and ➨➎➸✢➺●➯➵➳ The optimal values for ☛✤☞✥✍✏✓✒ and ☛✌✆✞✛✏✓✒ depend on the desired average queue size. If the typical traffic is fairly bursty, then ☛✤☞✥✍✑✏✓✒ must be correspondingly large to al￾low the link utilization to be maintained at an acceptably high level. For the typical traffic in our simulations, for connections with reasonably large delay-bandwidth prod￾ucts, a minimum threshold of one packet would result in unacceptably low link utilization. The discussion of the optimal average queue size for a particular traffic mix is left as a question for future research. The optimal value for ☛✚✆✠✛✏✓✒ depends in part on the maximum average delay that can be allowed by the gate￾way. The RED gateway functions most effectively when ☛✚✆✠✛✏✓✒ ✬➻☛✤☞✥✍✏✓✒ is larger than the typical increase in the calculated average queue size in one roundtrip time. A useful rule-of-thumb isto set ☛✚✆✠✛✣✏✓✒ to atleasttwice ☛✌☞✥✍✑✏✓✒ . 7 Calculating the packet-marking prob￾ability The initial packet-marking probability ✂✦ is calculated as a linear function of the average queue size. In this section we compare two methods for calculating the final packet￾marking probability, and demonstrate the advantages of the second method. In the first method, when the aver￾age queue size is constant the number of arriving packets between marked packets is a geometric random variable; in the second method the number of arriving packets be￾tween marked packets is a uniform random variable. The initial packet-marking probability is computed as follows: ✂✦✪✩ ☛✌✆✞✛✧★✫ ✆✞✝✠✟✭✬✮☛✤☞✥✍✑✏✓✒✠✯✱✰ ✫☛✌✆✞✛✣✏✓✒✲✬✮☛✤☞✥✍✑✏✓✒✞✯✴✳ The parameter ☛✚✆✞✛✧ gives the maximum value for the packet-marking probability ✂☎✦ , achieved when the average queue size reaches the maximum threshold. Method1: Geometric random variables. In Method 1, let each packet be marked with probability ✂☎✦ . Let the intermarking time ➼ be the number of packets that arrive, after a marked packet, until the next packet is marked. Because each packet is marked with probability ✂✦ , ➽❉➾ ✸❣➚▲➪➼➶t➫✍✢➹✢t ✫✶✵ ✬ ✂✦ ✯✶➘ ↕ ↔ ✂✦ ✳ Thus with Method 1, ➼ is a geometric random variable with parameter ✂✦ , and ➴✘➪➼➷➹☎t ✵ ✰✂✦ . With a constant average queue size, the goalis to mark packets at fairly regular intervals. It is undesirable to have too many marked packets close together, and it is also undesirable to have too long an interval between marked packets. Both of these events can result in global synchro￾nization, with several connectionsreducing their windows at the same time, and both of these events can occur when ➼ is a geometric random variable. ➬ Method 2: Uniform random variables. A more de￾sirable alternative is for ➼ to be a uniform random vari￾able from ➮ 1, 2, ..., ✵ ✰✂☎✦✴➱ (assuming for simplicity that ✵ ✰✂✦ is an integer). This is achieved if the marking prob￾ability for each arriving packet is ✂✦ ✰ ✫❇✵ ✬✃✷❁✸✻✺☎✍✑✼❅✽ ✂✦ ✯ , where ✷❁✸✻✺✣✍✑✼ is the number of unmarked packets that have arrived since the last marked packet. Call this Method 2. In this case, ➽❉➾✸❣➚❣➪➼➶tP✍✢➹❐t ✂✦ ✵ ✬ ✫✍✌✬ ✵ ✯✂✦ ➘ ↕❒➞ →➣❳➠ ❮ ✵ ✬ ✂✦ ✵ ✬❃☞ ✂✦✡❰ t ✂✦✭Ï➵❹✡Ð ✵ ✔✖✍❃✔ ✵ ✰✂✦✴Ñ and ➽❉➾ ✸❣➚▲➪➼Òt➎✍✢➹✢t ✿➙Ï➵❹✠Ð ✍➙Ó ✵ ✰✂✦ ✳ For Method 2, ➴✘➪➼➋➹✢t ✵ ✰ ✫ ✉✂✦ ✯❳❈ ✵ ✰ ✉ . ➬ Figure 8 shows an experiment comparing the two meth￾ods for marking packets. The top line shows Method 1, where each packet is marked with probability ✂ , for ✂ t ✿ ✳ ✿✞✉. The bottom line shows Method 2, where each packetis marked with probability ✂ ✰ ✫✶✵ ❈❉☞✂ ✯ ,for ✂ t ✿ ✳ ✿ ✵ , 10