[ieee 2012 international conference on computer & information science (iccis) - kuala lumpur,...

2012 International Conference on Computer & Information Science (ICCIS)

Impact of Fountain-based Protocol In the Uncongested and Congested Network

Zan-Kai Chong I , Bok-Min Gail, Hong-Tat Ewel , Su-Wei Tan2 and Cheng-Kuan Bryan Ng3 1Faculty of Engineering Science, Universiti Tunku Abdul Rahman, Kuala Lumpur, Malaysia.

2Faculty of Engineering, Multimedia University, Cyberjaya, Malaysia. 1 - Unite de recherche, INRIA Sophia Antipolis, France.

Email: {chongzk.goibm.eweht}@utar.edu.my . [email protected] . [email protected]

Abstract-We presume a perfect fountain-based protocol (FBP) with zero decoding inefficiency will be realised in the near future. The FBP node encodes a message of k symbols into infinite number of codewords and the receiver may decode any combination of k codewords to the original message without error. Therefore, the FBP node may transmit data at maximum speed even if the network is congested. We model the throughput of TCP and FBP nodes with point process and further study the performance through simulation in both uncongested and congested network. The results suggest that both FBP and TCP nodes have a similar performance in the uncongested network. However, FBP nodes dominate all the bandwidth if the network congested.

I. INTRODUCTION

Undoubtedly, part of the success of the Internet is credited to its doctrine of resource sharing and measures in overcoming the network congestion issues. The network congestion issue first appeared in the early development of ARPANET (former project of Internet). It was caused by the improper retransmission of lost packets that flooded the network with excessive packets and subsequently congested the network [1]. To mitigate this issue, Transmission Control Protocol (TCP) was proposed to adapt the packets transmission rate to the network state as to avoid the congestion collapse.

In recent years, there is a trend of applying forward errorcorrection (FEC) to TCP. FEC is a type of error control scheme where the error (the missing packets) will be corrected at the receiver side. For example, Lundqvist and Karlsson [2] and Sharma et a!. [3] apply a fixed rate erasure code (a type of FEC) to recover the loss packets but retransmission mechanism is still a necessary when channel erasure probability is higher than the correction capability of the fixed rate erasure code.

A rateless erasure code encodes a message of k symbols into an infinite number of codewords and the receiver just needs to accumulate any combination of k (1 + E) codewords in order to extract the original message, where E is a nonzero positive real number that denotes its decoding inefficiency. The advancement in coding theory has nurtured the development of first rateless erasure code named LT code [4] and its derivative Raptor code [5]. The rateless erasure code is commonly known as fountain code due to its similarity to a fountain which generates an infinite number of drops. One just needs to fill a

978-1-4673-1938-6112/$31.00 ©20 12 IEEE

cup with enough water to quench one's thirst irrespective of which fountain the drop was gathered from.

The emergence of fountain code eliminates the need of retransmission mechanism in the network as the lost packets can always be recovered by the next incoming packet even without the feedback link. This issue has drawn the attention of Raghavan and Snoeren [6] in studying the impact of the fountain code especially in the TCP network. They conjectured a perfect fountain code (i.e. decoding inefficiency E = 0) exists in the future and it is able to improve the throughput and fairness of nodes in a congested network. Bonald et a!. [7] confirmed the proposition and they further concluded the stability of Internet in the absence of any congestion avoidance scheme. Furthermore, Lopez et a!. [8] stated that TCP nodes have incentive to switch to fountain-based protocol (FBP) and sending at maximum rate. All the aforementioned work has signified the trend of FBP in future.

Extending the work of Lopez et a!., we show that TCP nodes have a little incentive to switch to FBP in the uncongested network. Nevertheless, they have a strong incentive to adopt FBP in congested network. Assuming a perfect fountain code protocol (FBP) existsl and a FBP node (node that adopts the FBP) will transmit data at maximum speed regardless of the network condition. The lost packets are inconsequential as the original message can be recovered as long as the receiver obtains sufficient packets to decode. Ideally, the receiver only acknowledges the sender during session termination (cf. Figure 1). One may find that the insensitivity of FBP towards congestion signal is identical to the User Datagram Protocol (UDP). The UDP provides an unreliable real time data transfer to the network. In contrast, like TCP, FBP is a reliable data transfer protocol but TCP-unfriendly.

The rest of this paper is structured as follows. Section II describes the assumptions and the network model used in FBP and its analytic performance under uncongested and congested networks. The propositions that are stated in Section II are verified with the simulation results in Section III. Lastly we present our conclusion in Section IV.

1 At the time of writing, RaptorQ code [9] claimed to have achieve a near zero decoding inefficiency_

[747 ]


Sender

Application FBP

Encoder

Receiver

FBP Decoder

Application

Figure 1. Packets flow under FBP scheme: (1) Sender generates a message. (2) The FBP encodes the message into codewords and send to the receiver. (3) The FBP receives enough codewords to decode. (4) Receiver acknowledges the sender for session termination. (5) Receiver receives the original message.

II. MODEL AND ANALYSIS

This section elaborates the assumptions and network model of this paper. Then, the performance of FBP in the uncongested and congested networks will be discussed.

A. Assumptions and Network Model

We assume a perfect FBP exists such that a message of k symbols can be encoded into an infinite number of codewords

(encoded packets) and the receiver merely needs at most k symbols to recover the original message. In other words, it has zero decoding inefficiency E = O.

The network consists of N nodes and a server as shown in Figure 2. Each node i generates packets of the same size at rate Ai to the server and all the packets will first be queued

in the buffer of the server with equal probability before being processed at rate f.L. The buffer has a maximum queue size of I unit and exceeding this limit the packets will be dropped.

B. Un congested Networks

Let the link capacity be denoted as C. All nodes are able to send packets at a constant maximum speed lvI (e.g. window size advertised by the server) without causing congestion (i.e. N lvI « C). Though the network is uncongested, we assume that there is a small number of packet loss due to interference. Denoting Aloss the loss intensity (Aloss has near zero value

[748 ]

1

2

11111111111111111111111111111111111110 Buffer Server

N

Node

Figure 2. Network model.

in an uncongested network) and 0: the increase rate of TCP's slow start after packet loss, Altman et al. [10] derived the TCP throughput as a stationary ergodic point process and showed that it converges to

(1)

if it is able to achieve maximum throughput !vI frequently.

On the other hand, the FBP does not slow start the transmission like TCP after packet loss as the missing packet can always be replaced with the new incoming packet irrespective of the sequence. In the TCP's perspective, the increase rate of FBP's "slow start" is infinitely fast (0: ---+ (X)). Thus, m an uncongested network, the throughput of FBP is

M _ [AlosslvI2] , 80: a--+=

M. (2)

Subsequently, we have the following proposition:

Proposition 1. FBP has a similar throughput as TCP in an uncongested network.

C. Congested Network

In contrast, a node can hardly achieve a maximum throughput in a congested network. The link capacity is incapable of supporting the excessive incoming packets and buffer overflow

is the main cause of packet losses in the network.

Since TCP is a reliable data transfer protocol, it responds to congestion signal (packet losses) by slowing down the transmission rate. Let R (k) be the autocorrelation function of the interarrival process of loss packets, Altman et al. [10] generalises the TCP throughput as

- [1 � k 1 Xc = AlossO: 2R (0) + � v R (k) , (3)


in their Proposition 3, where Al08s is the loss intensity. The constants 0: and v denote increase rate of slow start and the decrease ratio when a packet loss occurs respectively. Normalising the autocorrelation function R (n) = ArOS8R (n), Eq. 3 can be further expressed as

0:

Azoss (4)

In term of bandwidth utilisation, the TCP is always one step behind the unresponsive flow [11]. Given that a congested

network consists of both FBP and TCP nodes. Increasing the ratio of FBP nodes in the network will aggravate the packets loss events (loss arrival rate Al08s and its autocorrelation function R(n)) in the network as they do not respond to the congestion signal in the network. The increasing Azoss will further induce a reduction in the TCP throughput. As the FBP nodes becomes the majority, the TCP throughput will be marginalised. In this particular moment, the FBP nodes monopolise the bandwidth among themselves, that is

- C Yc :=:::::: --- ,

NFBP (5)

where C denotes the link capacity and N F BP denotes the number of FBP nodes in the network. Therefore, we deduce the following proposition.

Proposition 2. FBP dominates TCP in terms of bandwidth

We have run the simulation for a couple of times and the results are consistent. The following graphs are plotted based on the result of a particular simulation run time.

The instantaneous transmission rate (labelled with "Tx") and throughput (labelled with "Ack") of both FBP and TCP are plotted in Figures 3 and 4 with 10 seconds time scale for both uncongested and congested networks. These instantaneous values are average throughput of nodes that fall under the same scheme (FBP or TCP). Figure 3 demonstrates the instantaneous performance of TCP in the absence of FBP nodes. In the uncongested network, the instantaneous throughput of TCP nodes correlates with their own instantaneous transmission rate as there is no packet loss throughout the whole simulation. However, as they are deployed in a congested network, some packets are dropped and the unacknowledged packet timeout events trigger the TCP's congestion avoidance algorithm. Subsequently, it halves the TCP instantaneous transmission rate. Multiplexing all the TCP sources and we observed the instantaneous transmission rate fluctuated about a saturation point.

The saturation point is the maximum throughput bounded by the server's service rate J.L.

70-----,---------------------------TCPTx

. . . . . . . . . . ... . _ _ . . . . . . . . _ . . . . . . . _ . . _ . . . . . . . _ . . _ _ . _ . . . . _ . . . . . . . . . . . I

utilisation in the congested network. 20

III. SIMUL ATION

We simulate a network as shown Figure 2 with SimPy [12] and adopt all the assumptions in Section II-A. 30 nodes and a server are deployed in the network. The node will generate a message of 500 packets every 100 second. Both of these val ues will vary exponentially during the run time (modified version

of packet train traffic generation model). All transmissions (i.e.

TCP and FBP) have a common maximum transmission rate lvI = 10 packet/second. To construct an uncongested network, a server of buffer length I = 5000 unit and service rate J.L = 500 packet/second is used. Both of these values are reduced by factor of lOin the congested network.

We only implement slow-start and congestion avoidance algorithm in TCP scheme. Fast recovery and fast retransmit mechanisms have been removed because there is no outof-sequence packets delivery and packet losses will always happen in a continuous sequence. The unacknowledged packet will trigger retransmission mechanism after 100 seconds. On the other hand, FBP has a zero decoding inefficient (E = 0) and it will try to transmit packets at maximum speed regardless of packet losses. The sink will acknowledge the sender when it has received enough packets to recover the original message.

10- .

�OMO��JO�OOO---WffiMOO��50�O"O--·OO�O�O---,,70�ooO-�aooo �("on.<1

(a)

)O-----,------------------�------� TCPlx TCPAck

�O�O--�JO�OO�--W�O�O--�50�OO��,�OO�O---=,O�OO��800·0 5!:!col"bd

(b)

Figure 3. Instantaneous transmission rate and throughput of 0 FBP vs 30 TCP nodes in (a) uncongested network; (b) congested network.

We plot the instantaneous performance of 5 FBP vs 25 TCP

[749 ]


nodes in Figure 4. FBP nodes coexists peacefully with other TCP nodes in the uncongested networks. Nevertheless, the FBP nodes marginalised the TCP nodes in the congested networks. The FBP nodes may continue their transmission at maximum rate regardless of the loss packets. Whereas, TCP nodes have to respond to the congestion signal with congestion avoidance algorithm in order to ensure the transmission reliability.

1.10---�

120- .

10.

30 � £ til)

.0

20 -

30�O �OOIl

]t'",o __ 140- .

120- .

100

!

: � £

II

500[} moo Second

(a)

5l:corKl

(b)

TCP� TCP�k I I FBP Tx FBP Ac.k

J 700('} 80M

TCPTx TCPAck _ FBP Tx FBP Ack _

I

Figure 4. Instantaneous transmission rate and throughput of 5 FBP vs 25 TCP nodes in (a) uncongested network; and (b) congested network.

Figure 5 depicts the mean throughput of different combination ratio of FBP and TCP nodes in the congested networks for 8000 seconds simulation run time. FBP sources have the highest throughput given on average when they are the minority group in the network (i.e. 5 FBP vs 25 TCP nodes). Increasing the ratio of FBP nodes in the network will degrade their mean throughput. As FBP nodes become the majority (i.e. 30 FBP vs 0 TCP nodes) in the network, their throughput will drop to the lowest given on average and this is the point where the bandwidth is shared equally among all the nodes (FBP nodes). All the aforementioned observations are consistent with Propositions 1 and 2. That is, TCP nodes has strong incentives to switch to FBP only when the network is congested.

[750 ]

401,)00

35000

3000.0

. . . . � · . . · . . 1 ]i 7�(]D(1

� 2DOOD ·:,:,:-:,:·1

10000

---,-----

1= TCP

=�

Figure 5. Mean throughput of FBP vs TCP nodes in a congested network.

IV. CONCLUSION

In this paper, we assume the perfect fountain based protocol (FBP) exists and we study its impact to the network under the uncongested and congested state. Our finding suggests that TCP nodes have no incentive to adopt FBP if the network is uncongested. On the other hands, the TCP nodes are forced to adopt FBP in congested network in order to gain an equal share of network bandwidth.

REFERENCES

[11 J. Nagle, "Congestion control in IP/TCP internetworks," ACM SIG

COMM Computer Communication Review, vol. 25, no.!, pp. 61-65, 1995.

[21 H. Lundqvist and O. Karlsson, "TCP with end-to-end FEC," in Interna

tional Zurich Seminar on Communications, pp. 152-155, IEEE, 2004. [31 V. Sharma, K. Ramakrishnan, K. Kar, and S. Kalyanaraman, "Com

plementing TCP congestion control with forward error correction," NETWORKING 2009, pp. 378-391, 2009.

[41 M. Luby, "LT codes," in The 43rd Annual IEEE Symposium on Foun

dations of Computer Science, pp. 27l-280, IEEE, 2002. [5] A. Shokrollahi, "Raptor codes," IEEE Transactions on Information

Theory, vol. 52, no. 6, pp. 2551-2567, 2006. [6] B. Raghavan and A. Snoeren, "Decongestion control," IRVINE IS

BURNING, p. 61, 2006. [7l T. Bonald, M. Feuillet, and A. Proutiere, "Is the "law of the jungle"

sustainable for the Internet?," in IEEE INF O COM, pp. 28-36, IEEE, 2009.

[81 L. L6pez, A. Fernandez, and V. Cholvi, "A game theoretic comparison of tcp and digital fountain based protocols," Computer Networks, vol. 51, no. 12, pp. 3413-3426, 2007.

[9] "RaptorQ technical overview," tech. rep., QUALCOMM, United States, 2010.

[101 E. Altman, K. Avrachenkov, and C. Barakat, "A stochastic model of TCPIIP with stationary random losses," IEEEIACM Transactions on

Networking (TON), vol. 13, no. 2, pp. 356-369, 2005. [Ill S. Floyd and K. Fall, "Promoting the use of end-to-end congestion

control in the internet," IEEEIACM Transactions on Networking (TON),

vol. 7, no. 4, pp. 458-472, 1999. [121 "SimPy 2.1.0 documentation." http://simpy.sourceforge.netiSimPyDocs/

index.htm!

[ieee 2012 international conference on computer & information science (iccis) - kuala lumpur,...

Documents