Print Email Download

Paid Writing Services

More Free Content

Get Your Own Essay

Order Now

Instant Price

Search for an Essay


TCP Congestion Algorithm

Computer Networks is the interconnected collection of autonomous computers. Inter-connected computers exchange information in the form of packets. When the packets overwhelm the network infrastructure, congestion occurs. The congestion is a condition of severe delay caused by overload of datagrams at one or more switching points(e.g. at routers). When congestion occurs, delay increases and the router begins to enqueue datagrams until it can route them. EXPO Congestion Control Algorithm can be implemented to avoid congestion by reducing the transmission rate of the sender in the network.

Initially the Congestion Window of the sender is initialized to a smaller value like 1 and then it is incremented until the congestion occurs. Then the EXPO Algorithm is used to find the new congestion window size from previous values and the window size is incremented using the same algorithm to avoid retransmission.

In this Project, through extensive simulation experiments, I evaluate the performance of EXPO mechanism in high-speed and long-delay networks. We evaluate the performance of EXPO mechanism in terms of throughput, the change in the congestion window size and queue length of the bottleneck link. Also, I compared the performance of EXPO mechanism with those of other existing TCP variants, and present that this mechanism achieves good performance.

Keywords

Transmission Control protocol (TCP), Congestion Control, Congestion Window, Congestion Algorithms

LIST OF SYMBOLS AND ABBREVIATION

Ack-Acknowledgement

SACK-Selective Acknowledgement

Bit-Binary digit

ECN-Explicit Congestion Notification

Gb/s-Gigabits per second

Kb/s- Kilobits per second

IETF-Internet Engineering Task Force

ISP-Internet Service Provider

MSS-Maximum Segment Size

RFC-Request for Comments

RSVP-Resource Reservation Protocol

IP- Internet Protocol

TCP- Transmission Control Protocol

TCP/IP- Transmission Control Protocol/ Internet Protocol

UDP-User Datagram Protocol

ToS- Type of Service

EIPD-Exponential Increase Proportional Decrease

Cwndq-Congestion Window

1. INTRODUCTION

The Transmission Control Protocol (TCP) is a reliable, connection-oriented protocol. To provide efficiency in the internet, packets take different path/route to reach destination. The TCP performance is mainly based on congestion control algorithm. Congestion will degrades the performance of an network. When there are too many hosts inside the collision domain, then there is a chance of network congestion.

When there are too many packets in the network it also affects the performance of network because the transmission device can't process too many packets at the same time. For this reason TCP uses flow control. TCP uses sliding window for the purpose of flow control. TCP congestion control algorithm can be used to avoid congestion in the network. TCP congestion control algorithm uses congestion window (cwnd) to control the rate of transmission between the sender and receiver. The congestion window is the agreed transmission rate between the sender and receiver. The size of the window increases for every positive acknowledgement the sender receives. Similarly, the size decreases if any packet loss is found by the sender. The congestion window size increases till it reaches the maximum window size.

The TCP hosts sends packets into the network without a reservation and then the host reacts to observable events. Each source determines how much capacity is available to a given flow in the network. Acknowledgements are used to pace the transmission of packets. Many congestion algorithms are introduced by scientists through various researches.

1. A. The problem and sub problems

The networks have two drawbacks because of congestion control. They are congestion collapse from undelivered packets, and unfair allocation of bandwidth between competing traffic flows.

The IP is based on connectionless delivery, so packets is forwarded based on network bandwidth and cost. The congestion collapse from undelivered packets is due to bandwidth consumption by the dropped packets before it reach the destination. These packets will consume the most of the bandwidth which causes the congestion in the network. The other packets in the network have to compete with undelivered packet for the bandwidth which results in congestion. This type of congestion is very difficult to eliminate.

The main reason for unfair bandwidth allocation is congestion in the network. The congestion due to undelivered packets is found in the internet for a range of reasons, which are unresponsive flow. The TCP/IP flow that will reduce the transmission rate to avoid congestion will produce unfair bandwidth allocations to avoid the packet loss. Congestion control algorithm will allocate bandwidth for each TCP flow that is inversely proportional to RRT. For example, the packets with short RRT will be allocated more bandwidth then packets with longer RRT.

2. LITERATURE REVIEW

Floyd and Fall have approached the problem of congestion control by proposing low-complexity router mechanisms that promote the use of adaptive or “TCP-friendly” end-to-end congestion control. Their suggested approach requires selected gateway routers to monitor high-bandwidth flows in order to determine whether they are responsive to congestion. Flows that are determined to be unresponsive are penalized by a higher packet discarding rate at the gateway router. A limitation of this approach is that the procedure currently available to identify unresponsive flows are somewhat arbitrary and not always successful.

3. STANDARD TCP CONGESTION CONTROL ALGORITHMS

There are four standard TCP congestion control algorithms. They are,

3.1 Slow Start

Slow start is also known as sender-based flow control. The sender is responsible for the congestion control. This algorithm increases the transmission rate based on the acknowledgement it receives from the other end. As the name implies it will increase the window size slowly.

3.2 Congestion Avoidance

When the connection is established between the TCP sender and TCP receiver, packets are transmitted based on the slow start algorithm. When there is any congestion or packet loss is detected, the congestion avoidance algorithm is used to eliminate the congestion by reducing the rate of transmission between the TCP sender and TCP receive.

3.3 Fast Retransmit

When three or more duplicate acknowledgements with the same acknowledge number is received by TCP sender, then the sender can assume that there is a packet loss. The sender then again retransmits the packet that was dropped.

3.4 Fast Recovery

Fast recovery is used to maintain the flow rate by going to congestion avoidance mode instead of slow start mode. So that, the transmission rate is maintained instead of starting the window size with one. The Fast Recovery will increase the performance of TCP by maintaining the transmission rate.

4. SURVEY ON CONGESTION CONTROL ALGORITHMS

TCP is among the most popular of protocols and it owes a good deal of this praise to its congestion control strategies. TCP employs the following algorithms.

4.1 BIN Algorithm

The BIN algorithm is based on the familiar Binary Search algorithm. The first task of the algorithm is to find the range of pinning [a, b]. The optimal congestion window size ‘U', lies within this range of pinning [a, b]. There are different methods to find the range of pinning. For example, we can use TCP Slow Start algorithm. Once a failure occurs, ‘b' (the upper limit) will receive the size of congestion window used at that time. ‘a' (lower limit) will be then set to one. The other method, which I have chosen to implement, is set the lower limit to one and the upper limit to the maximum size of the sending window. In this case the sender initially assumes that the receiver can receive at least half of the maximum sending window size.

Having determined ‘a' and ‘b', the congestion window size is set to (a + b)/2. This algorithm yields a decreasing interval of pinning at all times. In a “steady state”, the algorithm uses the following method:

When all Acks arrive (i.e. success in the search):

Increase ‘a' to be (a + b)/2

When failure occurs (i.e. failure in the search):

Decrease ‘b' to be (a + b)/2

4.2 EIPD Algorithm (Exponential Increase Proportional Decrease)

The EIPD is a hybrid algorithm suitable for networks which possess unstable network bandwidth but assured sequential delivery of packets. The EIPD algorithm uses the acknowledgement packet sent from the receiver to calculate the exact size of available network bandwidth. The acknowledgement packet is expected to contain the sequence number of the last successfully received packet. The algorithm initially employs the exponential pinner algorithm to find the interval of pinning. After the range of pinning has been found, the following procedure is followed

EIPD Algorithm

INITIAL CONDITION

NACK ACK

If 4 successive ack

Cwnd = cwnd +

cwnd = cwnd * (f*B)

if (f>0)

ACK

NACK

ACK NACK

4.3 Exponential Pinner Algorithm

The Exponential Pinner algorithm increases the congestion window size rapidly by repeated squaring. Once a transfer fails, the lower bound is set to where the transfer last succeeded, and the upper bound is set to twice the lower bound. Now, we try to make some subtle changes to the two limits - I try sending some messages with the congestion window set to the upper limit. If the search succeeds, the lower bound is set twice the previous lower bound, and the upper bound is set to four times the previous lower bound. This continues until the search fails.

Initial condition: Cwnd = 2

ACK

NACK

‘a' = sqrt (cwnd)

‘b' = 2 * ‘a'

Cwnd = ‘b'

ACK

‘a' = 2 * ‘a'

‘b' = 2 * ‘b'

ACK

FINSH

NACK NACK

Now the upper and lower limits are finalized to implement the EIPD algorithm.

4.4 EXPO Algorithm

The preliminary condition employed for implementing the EXPO algorithm is the pinning range [a, b]. The TCP slow start algorithm is used to calculate the pinning range. Once the pinning range has been determined, the procedure shown below is followed.

Initial condition:

a < cwnd < b

ACK NACK

a = a - calc_cwnd(a,b)

b = cwnd

cwnd = a

a = cwnd

b = a + calc_cwnd(a, b)

cwnd = b

NACK

ACK

ACK Figure 3 NACK

Calc_Cwnd Calculation

Calc_Cwnd ( )

M = T =

Return :

5. PERFORMANCE

The results of their simulations as follows:

Static Case

BIN

EPA

EIPD

EXPO

Data transfer rate

Average

Average

Best

Worst

Retransmission

Average

Best

Good

Worst

Slightly Varying Case

BIN

EPA

EIPD

EXPO

Data transfer rate

Best

Worst

Average

Average

Retransmission

Best

Best

Average

Worst

Greatly Varying Case

BIN

EPA

EIPD

EXPO

Data transfer rate

Average

Worst

Worst

Best

Retransmission

Best

Good

Average

Worst

6. OUTLINE OF THE PROJECT

The Project implements the EXPO Algorithm to avoid congestion in network. The User Interface is done using Network Simulator. The EXPO Congestion Algorithm is implemented using C++.

Network is simulated using network simulator. NS is a object Oriented Simulator written in C++. The simulator supports a class hierarchy in C++ and a similar class hierarchy within the OTcl interpreter. The two hierarchy are closely related to each other; from the user's perspective, there is a one-to-one correspondence between a class in the interpreted hierarchy and one in the compiled hierarchy. The root of this hierarchyis the class TclObject. Users create new simulator objects through the interpreter; these objects are instantiated within the interpreter, and are closely mirrored by the corresponding object in the compiled hierarchy. The interpreted class hierarchy is automatically established through methods defined in the class Tclclass. User instantiated objects are mirrored through methods defined in the class Tcl object. There are other hierarchies in the C++ code and OTcl scripts.

7. IMPLEMENTATION

The implementation of the project is divided into three files

expo.tcl:

It implements the user interface of the project. The code is written in TCL Scripts. The network is assumed to contain 4 nodes named n0, n1, n2, n3

n0---------------------n1-----------------------------------------------n2------------------n3

The Bandwidth between the nodes are assumed that are connected are configured. It can be varied to our wish for various simulations.

tcpexpo.h:

The tcpexpo.h is the header file that defines all the functions and variables needed for the EXPO algorithm.

tcpexpo.cc:

This implements the function of the expotcpclass and the algorithm. The Constructor binds the traced variables to the TCL script and resets the value of the variables. The Destructor deletes the variables and array used.

recv() method is used when node receives the packet. It finds from the acknowledged packet whether the acks is valid or the received acknowledgement is a duplicate and it updates the cwnd_value according to the duplicate acks.

Calc_cwnd calculates the target congestion window given the current window size. update_avgrtt() and update_avgcwnd() is used to create a history of average RTT values and congestion window values.

Expo_pace() is used to increase the values of the congestion window according to the desired value given and the RTT.

Est() method uses the expo_avgrtt() and expo_avgcwnd() to estimate the values of the packet.

Packet data structure is used to create and manipulate the packets. hdr_flags and hdr_tcp is used to point the packet data structure.

8. CONCLUSION

This PROJECT succeeds in the following activities:

The following improvements can be made in this research

9. REFERENCES

Print Email Download

Share This Essay

Did you find this essay useful? Share this essay with your friends and you could win £20 worth of Amazon vouchers. One winner chosen at random each month.

Request Removal

If you are the original writer of this essay and no longer wish to have the essay published on the UK Essays website then please click on the link below to request removal:

Request the removal of this essay.


More from UK Essays

Need help with your essay?

We offer a bespoke essay writing service and can produce an essay to your exact requirements, written by one of our expert academic writing team. Simply click on the button below to order your essay, you will see an instant price based on your specific needs before the order is processed:

Order an Essay - via our secure order system!