5.3.4
Congestion Control in Datagram Subnets
Let us now turn to some approaches
that can be used in datagram subnets (and also in virtual-circuit subnets).
Each router can easily monitor the utilization of its output lines and other
resources. For example, it can associate with each line a real variable, u,
whose value, between 0.0 and 1.0, reflects the recent utilization of that line.
To maintain a good estimate of u, a sample of the instantaneous line
utilization, f (either 0 or 1), can be made periodically and u updated
according to
where the constant a determines how
fast the router forgets recent history.
Whenever u moves above the
threshold, the output line enters a ''warning'' state. Each newly-arriving
packet is checked to see if its output line is in warning state. If it is, some
action is taken. The action taken can be one of several alternatives, which we
will now discuss.
The old DECNET architecture signaled
the warning state by setting a special bit in the packet's header. So does
frame relay. When the packet arrived at its destination, the transport entity
copied the bit into the next acknowledgement sent back to the source. The
source then cut back on traffic.
As long as the router was in the warning
state, it continued to set the warning bit, which meant that the source
continued to get acknowledgements with it set. The source monitored the
fraction of acknowledgements with the bit set and adjusted its transmission
rate accordingly. As long as the warning bits continued to flow in, the source
continued to decrease its transmission rate. When they slowed to a trickle, it
increased its transmission rate. Note that since every router along the path
could set the warning bit, traffic increased only when no router was in
trouble.
The previous congestion control
algorithm is fairly subtle. It uses a roundabout means to tell the source to
slow down. Why not just tell it directly? In this approach, the router sends a choke
packet back to the source host, giving it the destination found in the packet.
The original packet is tagged (a header bit is turned on) so that it will not
generate any more choke packets farther along the path and is then forwarded in
the usual way.
When the source host gets the choke
packet, it is required to reduce the traffic sent to the specified destination
by X percent. Since other packets aimed at the same destination are probably
already under way and will generate yet more choke packets, the host should
ignore choke packets referring to that destination for a fixed time interval.
After that period has expired, the host listens for more choke packets for
another interval. If one arrives, the line is still congested, so the host
reduces the flow still more and begins ignoring choke packets again. If no
choke packets arrive during the listening period, the host may increase the
flow again. The feedback implicit in this protocol can help prevent congestion
yet not throttle any flow unless trouble occurs.
Hosts can reduce traffic by
adjusting their policy parameters, for example, their window size. Typically,
the first choke packet causes the data rate to be reduced to 0.50 of its
previous rate, the next one causes a reduction to 0.25, and so on. Increases
are done in smaller increments to prevent congestion from reoccurring quickly.
Several variations on this
congestion control algorithm have been proposed. For one, the routers can
maintain several thresholds. Depending on which threshold has been crossed, the
choke packet can contain a mild warning, a stern warning, or an ultimatum.
Another variation is to use queue
lengths or buffer utilization instead of line utilization as the trigger
signal. The same exponential weighting can be used with this metric as with u,
of course.
At high speeds or over long
distances, sending a choke packet to the source hosts does not work well
because the reaction is so slow. Consider, for example, a host in San Francisco
(router A in Fig. 5-28) that is sending traffic to a host in
New York (router D in Fig. 5-28) at 155 Mbps. If the New York host
begins to run out of buffers, it will take about 30 msec for a choke packet to
get back to San Francisco to tell it to slow down. The choke packet propagation
is shown as the second, third, and fourth steps in Fig. 5-28(a). In those 30 msec, another 4.6
megabits will have been sent. Even if the host in San Francisco completely
shuts down immediately, the 4.6 megabits in the pipe will continue to pour in
and have to be dealt with. Only in the seventh diagram in Fig. 5-28(a) will the New York router notice a
slower flow.
Figure 5-28. (a) A choke packet that
affects only the source. (b) A choke packet that affects each hop it passes
through.
An alternative approach is to have
the choke packet take effect at every hop it passes through, as shown in the
sequence of Fig. 5-28(b). Here, as soon as the choke packet
reaches F, F is required to reduce the flow to D. Doing so will require F to
devote more buffers to the flow, since the source is still sending away at full
blast, but it gives D immediate relief, like a headache remedy in a television
commercial. In the next step, the choke packet reaches E, which tells E to
reduce the flow to F. This action puts a greater demand on E's buffers but
gives F immediate relief. Finally, the choke packet reaches A and the flow
genuinely slows down.
The net effect of this hop-by-hop
scheme is to provide quick relief at the point of congestion at the price of
using up more buffers upstream. In this way, congestion can be nipped in the
bud without losing any packets. The idea is discussed in detail and simulation
results are given in (Mishra and Kanakia, 1992).
When none of the above methods make
the congestion disappear, routers can bring out the heavy artillery: load
shedding. Load shedding is a fancy way of saying that when routers are being
inundated by packets that they cannot handle, they just throw them away. The
term comes from the world of electrical power generation, where it refers to
the practice of utilities intentionally blacking out certain areas to save the
entire grid from collapsing on hot summer days when the demand for electricity
greatly exceeds the supply.
A router drowning in packets can
just pick packets at random to drop, but usually it can do better than that.
Which packet to discard may depend on the applications running. For file
transfer, an old packet is worth more than a new one because dropping packet 6
and keeping packets 7 through 10 will cause a gap at the receiver that may
force packets 6 through 10 to be retransmitted (if the receiver routinely
discards out-of-order packets). In a 12-packet file, dropping 6 may require 7
through 12 to be retransmitted, whereas dropping 10 may require only 10 through
12 to be retransmitted. In contrast, for multimedia, a new packet is more
important than an old one. The former policy (old is better than new) is often
called wine and the latter (new is better than old) is often called milk.
A step above this in intelligence
requires cooperation from the senders. For many applications, some packets are
more important than others. For example, certain algorithms for compressing
video periodically transmit an entire frame and then send subsequent frames as
differences from the last full frame. In this case, dropping a packet that is
part of a difference is preferable to dropping one that is part of a full
frame. As another example, consider transmitting a document containing ASCII
text and pictures. Losing a line of pixels in some image is far less damaging
than losing a line of readable text.
To implement an intelligent discard
policy, applications must mark their packets in priority classes to indicate
how important they are. If they do this, then when packets have to be
discarded, routers can first drop packets from the lowest class, then the next
lowest class, and so on. Of course, unless there is some significant incentive
to mark packets as anything other than VERY IMPORTANT— NEVER, EVER DISCARD, nobody
will do it.
The incentive might be in the form
of money, with the low-priority packets being cheaper to send than the
high-priority ones. Alternatively, senders might be allowed to send
high-priority packets under conditions of light load, but as the load increased
they would be discarded, thus encouraging the users to stop sending them.
Another option is to allow hosts to
exceed the limits specified in the agreement negotiated when the virtual
circuit was set up (e.g., use a higher bandwidth than allowed), but subject to
the condition that all excess traffic be marked as low priority. Such a
strategy is actually not a bad idea, because it makes more efficient use of
idle resources, allowing hosts to use them as long as nobody else is
interested, but without establishing a right to them when times get tough.
It is well known that dealing with
congestion after it is first detected is more effective than letting it gum up
the works and then trying to deal with it. This observation leads to the idea
of discarding packets before all the buffer space is really exhausted. A
popular algorithm for doing this is called RED (Random Early Detection) (Floyd
and Jacobson, 1993). In some transport protocols (including TCP), the response
to lost packets is for the source to slow down. The reasoning behind this logic
is that TCP was designed for wired networks and wired networks are very
reliable, so lost packets are mostly due to buffer overruns rather than
transmission errors. This fact can be exploited to help reduce congestion.
By having routers drop packets
before the situation has become hopeless (hence the ''early'' in the name), the
idea is that there is time for action to be taken before it is too late. To
determine when to start discarding, routers maintain a running average of their
queue lengths. When the average queue length on some line exceeds a threshold,
the line is said to be congested and action is taken.
Since the router probably cannot
tell which source is causing most of the trouble, picking a packet at random
from the queue that triggered the action is probably as good as it can do.
How should the router tell the
source about the problem? One way is to send it a choke packet, as we have
described. A problem with that approach is that it puts even more load on the
already congested network. A different strategy is to just discard the selected
packet and not report it. The source will eventually notice the lack of
acknowledgement and take action. Since it knows that lost packets are generally
caused by congestion and discards, it will respond by slowing down instead of
trying harder. This implicit form of feedback only works when sources respond
to lost packets by slowing down their transmission rate. In wireless networks,
where most losses are due to noise on the air link, this approach cannot be
used.
For applications such as audio and
video streaming, it does not matter much if the packets take 20 msec or 30 msec
to be delivered, as long as the transit time is constant. The variation (i.e.,
standard deviation) in the packet arrival times is called jitter. High jitter,
for example, having some packets taking 20 msec and others taking 30 msec to
arrive will give an uneven quality to the sound or movie. Jitter is illustrated
in Fig. 5-29. In contrast, an agreement that 99
percent of the packets be delivered with a delay in the range of 24.5 msec to
25.5 msec might be acceptable.
The range chosen must be feasible,
of course. It must take into account the speed-of-light transit time and the
minimum delay through the routers and perhaps leave a little slack for some
inevitable delays.
The jitter can be bounded by
computing the expected transit time for each hop along the path. When a packet
arrives at a router, the router checks to see how much the packet is behind or
ahead of its schedule. This information is stored in the packet and updated at
each hop. If the packet is ahead of schedule, it is held just long enough to
get it back on schedule. If it is behind schedule, the router tries to get it
out the door quickly.
In fact, the algorithm for
determining which of several packets competing for an output line should go
next can always choose the packet furthest behind in its schedule. In this way,
packets that are ahead of schedule get slowed down and packets that are behind
schedule get speeded up, in both cases reducing the amount of jitter.
In some applications, such as video
on demand, jitter can be eliminated by buffering at the receiver and then
fetching data for display from the buffer instead of from the network in real
time. However, for other applications, especially those that require real-time
interaction between people such as Internet telephony and videoconferencing,
the delay inherent in buffering is not acceptable.
Congestion control is an active area
of research. The state-of-the-art is summarized in (Gevros et al., 2001).
No comments:
Post a Comment
silahkan membaca dan berkomentar