The algorithm makes use of the following variables:

$t=$ current time

$t_i=$ time of $i$ th arrival or departure event

$q=$ number of frames in the system after the event

$T_0=$ time at the beginning of the previous cycle

$T_1=$ time at the beginning of the current cycle

The algorithm consists of three components:

Update: Beginning with $q_0$:$=0$

If the $i$ th event is an arrival event, $q$:$=q_{i-1}+1$

If the $i$ th event is a departure event, $q$:$=q_{i-1}-1$

$A_{i-1}={\displaystyle \underset{?}{\overset{?}{}}}$

$L=\frac{A_1+A_{i-1}}{t-T_0}$

Figure $20\mathrm{.}15$ A Frame Relay Algorithm

In one of the frame relay specifications, an algorithm for monitoring queue

lengths is suggested; this is shown in Figure $20\mathrm{.}15.$ A cycle begins when the outgoing

circuit goes from idle $($queue empty$)$ to busy $($nonzero queue size, including the cur$-$

rent frame$).$ If a threshold value is exceeded, then the circuit is in a state of incipient

congestion, and the congestion avoidance bits should be set on some or all logical

connections that use that circuit. Describe the algorithm in words and explain its

advantages$\mathrm{.}20\mathrm{.}5$ For a frame relay network to be able to detect and then signal congestion, it is neces$-$

sary for each frame handler to monitor its queueing behavior. If queue lengths begin

to grow to a dangerous level, then either forward or backward explicit notification or

a combination should be set to try to reduce the flow of frames through that frame

handler. The frame handler has some choice as to which logical connections should

be alerted to congestion. If congestion is becoming quite serious, all logical connec$-$

tions through a frame handler might be notified. In the early stages of congestion,

the frame handler might just notify users for those connections that are generating

the most traffic.

Figure $20\mathrm{.}14$ Network of Packet$-$Switching Nodes