Dead Locks

An ultimate congestion is called Dead Lock.(Also called Lock Up). First IMP cannot proceed until second IMP does something and second IMP cannot proceed because it waits for first IMP to do something. Both IMPs have ground to a complete halt and will stay that way forever.

The simplest lockup can happen with two IMPs. Suppose that IMP A has five buffers, all of which are queued for output to IMP B. Similarly, IMP B has five buffers, all of which are occupied by packets needing to go to IMP A. Neither IMP can accept any incoming packets from the other. They are both stuck. This situation is called direct store-and-forward lockup. The same thing can happen on a larger scale. Each IMP is trying to send to a neighbor, but nobody has any buffers available to receive incoming packets. This situation is called indirect store-and-forward lockup. When an IMP is locked up, all its lines are effectively blocked, including those not involved in the lockup.

Solution for Dead Lock:

A directed graph is constructed with being the nodes of the graph. Arcs connect pairs of buffers (in the same IMP or on adjacent IMPs). The graph is designed in such a way that if packets move from buffer to buffer along the arc, then there is no deadlock.

Choke Packets

Each IMP monitors the percentage utilization of lines. Associated with this is a real variable u, whose value lies between 0, 0 and 1.0 u is periodically updated using.





u_new = au_old + (1-a) f

f -> Instance of line utilization . (0 or 1)

a -> constant which determines how fast the IMP 'forgets' recent history.

As 'u' crosses a threshold, the output line enters a 'warning' state. Then a 'Choke Packet' is sent to the source host. When the source host receives the choke packet it is required to reduce the traffic to the destination by X percent. Since some packets have already been sent, the successive choke packets are ignored for some time. Even after that, if choke packets arrive, then the traffic is still reduced.

Two threshold levels can be used. Above the first level the packets are sent and above the second level the packets are discarded. Queue length can also be monitored instead of line utilization.

Flow Control

This is used by tranport layer to prevent one IMP from flooding another IMP with packets. Flow control can be applied between pairs of

• User processes (For e.g: one outstanding message per virtual circuit).


• Hosts, irrespective of the number of virtual circuits open.


• Source and destination IMPs, without regard to hosts.

Isarithmic Congestion Control

The algorithm is called Isarithmic because the tidal number of packets in the network is kept constant by issuing "permits", circulate in the subnet. To transfer data, and IMP must capture a "permit", destroy it and transfer the data to the destination IMP and destination IMP on reception of the data regenerates the "permit". By this method the congestion can never arise, in the subnet as a whole.

However it has a few drawbacks,

• It does not guarantee that a given IMP will never be flooded with packets.
• Permits must be uniformly distributed to prevent long delays by some IMPs. It is preferred to have them centralized.
• If a permit is destroyed for some reason, they are lost forever and the network capacity is reduced.

Packet Discarding to control Congestion

The packets are discarded by IMPs to control congestion. The source IMPs will have to keep sending the packets until it is accepted or make a time out and start every thing again. One buffer is always reserved in the IMPs to check to acknowledgement packets. If there are some number of input lines, S number of output lines and K number of buffers, then for a good performance, the max queue length of buffers for each line must be

That is, if there are 7 free buffers and three output lines, then it is not desirable to use all buffers for a single output line, because if they are all used up (waiting in the queue) the the packets for other output lines must be discarded.

So a maximum limit for the number of buffers for an output line is set using the formula (see above) and the other buffers are set free.

It has drawback that it needs extra bandwidth for duplicates.

Preallocation of Buffers to control Congestion

By permanently allocating buffers to each virtual circuit in each IMP, there will always be a place to store any incoming packet until it can be forwarded. First consider the case of a stop-and-wait IMP-IMP protocol. One buffer per virtual circuit per IMP is sufficient for simplex circuits, and one for each direction is sufficient for full duplex circuits. When a packet arrives, the acknowledgement is not sent back to the sending IMP until the packet has been forwarded. Thus an acknowledgment means that the receiver not only received the packet correctly, but also has a free buffer and is willing to accept another one. If the IMP-IMP protocol allows multiple outstanding packets, each IMP will have to dedicate a full window's worth of buffers to each virtual circuit to completely eliminate the possibility of congestion. Because dedicating a complete set of buffers to an idle virtual circuit is expensive, some subnets may use it only where low delay and high bandwidth are essential, for example, on virtual circuits carrying digitized speech.

Congestion Control Algorithms

There are five strategies for congestion control. These strategies involve allocating resources in advance, allowing packets to be discarded when they cannot be processed, restricting the number of packets in the subnet, using flow control to avoid congestion and chocking off input, when the subnet is overloaded.

• Preallocating resources
• Packet discarding
• Isarithmic Congestion Control
• Flow control
• Choke Packets
• Dead Locks

Congestion

When there are too many packets in a network beyond the network capacity, the performance of the network degrades. This is called congestion.

Consider that a sender sends a packet to a receiver which has no buffers free, as a consequence, the sender repeatedly sends the packet until an acknowledgement is released. This the sender cannot free its buffer (queue), which at some time becomes saturated and thus congestion arises.