SCIENCE CHINA Information Sciences

. RESEARCH PAPERS .

June 2011 Vol. 54 No. 6: 1251–1263 doi: 10.1007/s11432-011-4235-6

Globally stable and high-performance Internet congestion control through a computational inspiration from nature JAMALI Shahram1* & ANALOUI Morteza2* 1Computer

2Computer

Engineering Department, University of Mohaghegh Ardabili, Ardabil 55199-11367, Iran; Engineering Department, Iran University of Science and Technology, Tehran 16846-13114, Iran

Received August 3, 2010; accepted November 17, 2010; published online April 8, 2011

Abstract There are many reasons to worry that the current congestion control schemes in the Internet may be reaching its limits. Since the nature is a source of excellent solutions for complex problems, this work attempts to solve the congestion control problem, by adopting some biological principles and mechanisms. The current work proposes that the congestion problem in the Internet can be addressed through an inspiration from the population control tactics in nature. Toward this idea, each flow (W ) in the network is viewed as a species whose population size matches congestion window size of the flow. By this assumption, congestion control problem is redefined as population control of flow species. This paper defines a three-trophic food chain analogy in congestion control area, and gives a model to control population size of W species within this food chain. We call this model BICCTT and show mathematically, it is stable and efficient regardless of the link capacity, the round-trip delay, and number of flows. Extensive packet-level simulations in ns-2, show that BICCTT operates better than TCP/RED and XCP in both typical and high bandwidth-delay environments. BICCTT achieves fair bandwidth allocation, high utilization, small queue size, and near-zero packet drops. It does not maintain any per-flow state in routers and have low computational loads per packet, which makes it scalable. Keywords

nature-inspired algorithm, congestion control, TCP, stability

Citation Jamali S, Analoui M. Globally stable and high-performance Internet congestion control through a computational inspiration from nature. Sci China Inf Sci, 2011, 54: 1251–1263, doi: 10.1007/s11432-011-4235-6

1

Introduction

Congestion collapse is a condition which a packet switched computer network can reach, when little or no useful communication is happening due to congestion. There are two general approaches to avoid congestion collapse: admission control and congestion control. Admission control is useful in situations where a certain number of connections (e.g., phone conversations) may all share a link, while an even greater number of connections cause significant degradation in all connections to the point of making them all useless such as in congestive control. An application that wishes to use the network to transport traffic with QoS must first request a connection, which involves informing the network about the characteristics of the traffic and the QoS required by the application. This information is stored in a traffic contract. *Corresponding author (email: [email protected], [email protected])

c Science China Press and Springer-Verlag Berlin Heidelberg 2011 

info.scichina.com

www.springerlink.com

1252

Jamali S, et al.

Sci China Inf Sci

June 2011 Vol. 54 No. 6

The network judges whether it has enough resources available to accept the connection, and then either accepts or rejects the connection request. On the other hand, congestion control concerns controlling traffic entry into a telecommunications network, so as to avoid congestive collapse by attempting to avoid oversubscription of any of the processing or link capabilities of the intermediate nodes and networks, such as reducing the rate of sending packets. It should not be confused with flow control, which prevents the sender from overwhelming the receiver. The congestion control mechanisms in the Internet consist of the congestion window algorithms of transmission control protocol (TCP), running at end-systems, and active queue management (AQM) algorithms at routers, seeking to obtain high network utilization, small amounts of queuing delay, and some degree of fairness among users [1, 2]. These implementations are the result of an evolutionary cycle involving heuristics, small-scale simulation and experimentation, and deployment. However, there are reasons to wonder whether this evolutionary path may be reaching its limits (deficiencies of the current loss-based protocol in wireless environments; difficulties in providing quality of service and the growing evidence [3–5] that the additive-increase multiplicative-decrease structure in TCP does not scale well to high capacity networks). On the other hand, biological systems show a number of properties, such as self-organization, adaptability, scalability, robustness, autonomy, locality of interactions and distribution, which are highly desirable to deal with the growing complexity of current and future networks. In recent years a growing number of effective solutions for problems related to networked systems have been proposed through an inspiration from the natural systems and processes. The most known examples are swarm intelligence, evolutionary or genetic algorithms, and the artificial immune system. The customized mechanisms find applications in computer networking, for example, in the areas of network security [6, 7], pervasive computing, and sensor networks [8]. This paper suggests methods to engineer a congestion control algorithm that has potential benefits of both the mathematical and the bio-inspired models. It presents a mathematical framework for congestion control algorithms that has been developed, inspired by the nature. Thus, on the one hand, this algorithm can inherit some intrinsic characteristics of biology such as stability and robustness, and on the other hand, it provides us with a theoretical and mathematical framework that we can benefit from its facilities in analysis and development of the model. Toward this idea, we map mathematical model of a typical three-trophic food chain (plant-herbivore-carnivorous) to design a bio-inspired congestion control algorithm. We show mathematically that, BICCTT globally directs the system to a stable equilibrium point, which satisfies some basic requirements: high utilization of network resources, small queues, and a degree of control over resource allocation. Section 2 briefly presents preliminaries for biologically-inspired congestion control and explains analogy between the biological environment and the communication networks. Section 3 presents a methodology for applying mathematical model of tri-trophic food chain to the Internet congestion control issue and discuses its parameters setting. Section 4 presents implementation details of BICCTT. Section 5 suggests simulation results on the proposed algorithm in ns-2 environment and section 6 presents concluding remarks.

2

Preliminaries and backgrounds

In this section we explain how the Internet can be viewed as an ecosystem, and then we bring some natural population interaction models [9, 10], which later will be used in design of the congestion control mechanism. 2.1

Internet ecosystem

Consider a network with a set of k source nodes and a set of k destination nodes. We denote by S = {S1 , S2 , . . . , Sk } the set of source nodes with identical round-trip time (RT T ) and by D = {D1 , D2 , . . . , Dk } the set of destination nodes. Our network model consists of a bottleneck link from LAN to WAN as shown in Figure 1 and uses a window-based algorithm for congestion control. The bottleneck link has capacity

Jamali S, et al.

Figure 1

Sci China Inf Sci

June 2011 Vol. 54 No. 6

Network model.

Figure 2

1253

Internet ecosystem typology.

of B packet per RT T . The congestion window (W ) is a sender-side limit on the amount of data the sender can transmit into the network before receiving an acknowledgment (ACK). All connections are assumed to be long-lived. We imagine this network as an ecosystem that connects a wide variety of habitats such as routers, hosts, links and operating systems. From congestion control viewpoint, there are some species in these habitats such as “flow”(W ), “packet drop”(P ), “queue”(q) and “link free capacity” (C). The size of these network variables refers to their population size in the Internet ecosystem. In this ecosystem there is a whole web of interacting species and hence, their population sizes are affected. Figure 2 shows the typology of the Internet ecosystem from congestion control perspective. Now, assume that population of W in source Si is Wi (congestion window size of connection i). Normally, if the population size of this species is increased, then the number of sent packet would be increased, too. Thus, in order to control the congestion in the communication networks the population size of Wi (for i = 1, . . . , k) must be controlled. This means that the population control problem in the nature can be mapped to the congestion control problem in the communication networks. Nature uses many tactics, such as predation, competition, and parasites to control the population size of any species, which can be generalized to control the population size of W species. In [11–14] we have used predator-prey and competition interactions to control population size of W species. This work controls population size of W species within a three-trophic food chain and its preliminary version has been published in [15]. Ref. [15] maps the food chain interaction to congestion control issue and solves its equations by using Matlab software package. As an important improvement over [15], this work presents theoretical foundations of BICCTT and discusses its stability and performance. Also, this paper implements BICCTT in ns-2 environment for packet-level simulation purpose and compares its results with other important congestion control protocols. 2.2

Predator-prey interaction

Predator-prey interaction refers to classical predators that kill individuals and eat them: i) In the absence of predators, prey would grow exponentially. ii) The effect of predation is to reduce the prey’s growth rate. iii) In the absence of prey, predators will decline exponentially. iv) The prey’s contribution to the predator’s growth rate is proportional to the available prey as well as to the size of the predator population. v) Prey’s carrying capacity puts a ceiling on the prey population. This interaction controls the population size of prey and predator species in a limited range. If r and f represent the number of rabbits (prey) and foxes (predator), then this interaction can be explained by using (1) and (2) (see [9]): dr = ar − brf, dt

(1)

df = crf − hf, (2) dt where a is the natural growth rate of rabbits, b is the death rate per encounter of rabbits due to predation, c is the efficiency of turning predated rabbits into foxes and h is the natural death rate of foxes in the absence of food (rabbits). One of the unrealistic assumptions in the Lotka-Volterra model (1) and (2) is

1254

Jamali S, et al.

Sci China Inf Sci

June 2011 Vol. 54 No. 6

that the prey growth is unbounded in the absence of predation. As a reasonable step, we might expect the prey to satisfy a logistic growth [9], say, in the absence of any predators, has some maximum carrying capacity:   r dr =a 1− r − brf, (3) dt Cr in which Cr is the carrying capacity for the prey (r). 2.3

Three-trophic food chain

In an ecosystem there is always a foundation species of plant (p) that directly harvests energy from the sun, for example, grass. Next are herbivores (primary consumers) that eat the grass, such as the rabbits (r). Next are carnivores (secondary consumers) that eat the rabbits, such as foxes (f ). In this three-species food chain the lowest-level prey p is preyed upon by a mid-level species r, which, in turn, is preyed upon by a top-level predator f . Eqs. (4)–(6) can model this ecosystem (while it can be modeled in other forms as well, see [10]):     p dp =p α 1− − βr , (4) dt Cp     dr r =r a 1− + εp − bf , (5) dt Cr df = f (cr − h), dt

(6)

in which α is the natural growth rate of plant, β is the death rate per encounter of plant due to predation by rabbits, Cp is the carrying capacity of plant, ε is rate of turning predated plants into rabbits and other parameters are defined as before.

3

Congestion control by using the interacting population models

In [11–14] we have used predation and competition models to design congestion control mechanisms, which were indeed explaining a two-level food chain in the Internet ecosystem. Another reasonable step in this evolutionary path, inspired from the three-trophic food chain, is to design a congestion control algorithm. In this section, we present a congestion control scheme that includes both source and AQM algorithms. AQM algorithm computes some feedbacks and sends them to the source algorithm to be used in update process of senders’ congestion window size. 3.1

Three-trophic food chain in the Internet ecosystem

For those AQM algorithms such as RED, that use length of queue, at the congested router, as a congestion measure, interaction of TCP and AQM can be described as follows: i) In the absence of waiting packets in the queue, congestion window (W ) would grow. ii) When there is backlog of waiting packets in the queue, congestion window size would decline. iii) Incoming packets rate (congestion window size) contribution to the queue length growth is proportional to available traffic intensity, as well as the queue length itself. iv) In the absence of packets stream (small congestion window size), the queue length will decline. v) Bottleneck bandwidth is a limit for packet rate. We see that queue-flow interaction is so similar to the predator-prey interaction. Now, we consider the congestion control mechanism from other viewpoint and discuss about interaction of “link free capacity” and “flow” (congestion window): i) In the absence of packets stream, free capacity of the link would grow. ii) When sending rate is increased (large congestion window), then free capacity of the link would decline. iii) Any growth of free capacity of link leads to packet rate increment at the sources. iv) In the absence of free capacity in the link, sending rate (congestion window size) will decline. v) Bottleneck bandwidth is a limit for link free capacity (carrying capacity). We see that this behavior is

Jamali S, et al.

Sci China Inf Sci

June 2011 Vol. 54 No. 6

1255

also similar to the predator-prey interaction. Hence, capacity-flow-queue is similar to a plant-herbivorecarnivorous food chain, in which, “link free capacity” is preyed upon by “flow”, which, in turn, is preyed upon by “queue length”. These similarities motivate us to use the tri-trophic food chain model to design a congestion control scheme. For this purpose, we assume that there are two species “virtual capacity” (C) and “virtual queue” (Q) that take part in tri-trophic food chain C-W -Q. This food chain can be illustrated by using (7)–(9), which we call BICCTT (bio-inspired congestion control by using tri-trophic food chain):     k  C dC =C α 1− −β Wj , dt Cc j=1     dWi Wi = W i hi 1 − + λC − ri Q , where i = 1, . . . , k, dt CW   k  dQ =Q ei Wi − m ε, where m = min(B, Q + Wi ), dt i=1

(7)

(8)

(9)

in which α is the growth rate of C, β is the decrement rate per encounter of C due to W. hi is the growth rate of Wi , λ is the increment rate per encounter of Wi due to C and ri is the decrement rate per encounter of Wi due to Q. ei is the efficiency of turning predated Wi into Q and m is death rate of Q. ε is a positive constant that indicates degree of influence of traffic changes on C and Q dynamics (for smoothness purpose). CC and CW are the carrying capacities of C and W , respectively. Note that, Q and C in (7)–(9) are two control variables, which are defined by inspiration from nature, to control and direct W size to a stable point that satisfies characteristics such as fairness and performance. In this model CW is a limit on the congestion window size and bottleneck capacity is the best value for it (it can also be set to other reasonable values as well, while its lower bound is the fair share of each source from bottleneck bandwidth). Congestion control system of (7)–(9) has the following preliminary properties: • Eq. (7) shows that C is increased by B (bandwidth of bottleneck link), but this increment is offset  by incoming packets rate Wi . • Eq. (8) shows that Wi population has multiplicative increase, but this growth will be inhibited by size of Q and Wi . • Eq. (9) is similar to a formal definition of queue dynamics at a router. 3.2

Setting the parameters of BICCTT

Any congestion control scheme must be evaluated from two points of view: equilibrium and dynamics. Equilibrium properties are fairness, throughput and performance, and dynamic properties are convergence and stability. Design of BICCTT follows two important objective goals: performance guarantee and stability guarantee. In other words, this design process is seeking a congestion control scheme, which, always converges to its equilibrium, and offers high performance in this equilibrium. 3.2.1

Stability guarantee

This section is going to draw those conditions, which must hold to make BICCTT converge to its equilibrium. To this end, consider the generalized n-species Lotka-Volterra system, described by the following equation:   n  aij xj (t) , where i = 1, . . . , n, (10) x˙ i (t) = xi (t) gi + j=1

in which, real matrix A = [aij ] describes the quadratic interactions. Stability of (10) can be analyzed by using the following theorem (see [16] for more details): Theorem. A known sufficient condition for global convergence of (10) to its equilibrium in the whole n is the existence of a positive definite diagonal matrix D, such that DA + AT D is negative space R+ definite.

1256

Jamali S, et al.

Sci China Inf Sci

June 2011 Vol. 54 No. 6

Now, we use this theorem to extract those conditions, which make system (10) stable. Take D as an n × n identity matrix. We know that D is a positive definite diagonal matrix. Therefore, it is sufficient to prove that M = DA + AT D is negative definite matrix. M will be negative definite matrix, if for all non-zero vectors x, xT = (x1 , x2 , . . . , xn ), the condition xT M x < 0 holds. In other words, stability conditions of (10) can be extracted from xT M x < 0: M = DA + AT D ⎡ a11 a12 ⎢ ⎢ a21 a22 ⎢ ⎢ =I ×⎢ ⎢ ⎢ ··· ··· ⎣

· · · a1n

⎡

⎤

a11

⎥ ⎢ ⎢ · · · a2n ⎥ ⎥ ⎢ a12 ⎥ ⎢ ⎥+⎢ ⎥ ⎢ ⎢ ··· ··· ⎥ ⎦ ⎣ ··· · · · ann a1n

an1

a21 a22 ···

· · · an1

⎤

⎥ · · · an2 ⎥ ⎥ ⎥ ⎥ × I, ⎥ ··· ··· ⎥ ⎦ · · · ann 

  n n  x M x < 0 ⇒ x M x = x1 xi (ai1 + a1i ) + x2 xi (ai2 + a2i T

T

+ x3

n 

i=1

xi (ai3 + a3i ) + · · · + xn

n 

i=1

i=1

xi (ain + ani )) < 0.

(11)

i=1

According to (11), it can be easily found that xT M x will be negative, and therefore (10) will be stable, if conditions (12) and (13) hold: ∀i, ∀i, j

aii < 0,

(12)

aij = −aji or aij = aji = 0 or aii < aij = aji < 0.

(13)

To integrate (12) and (13) into the design process of BICCTT, we first rewrite (7)–(9) in the form of the generalized n-species Lotka-Volterra system. In this way the following translations are done: n = k + 2, xi (t) = Wi (t)

and

g i = hi ,

xk+1 (t) = C

and

gk+1 = α,

xk+2 (t) = Q

and

gk+2 = −m.

for i = 1, . . . , k,

By this mapping, according to (7)–(9), matrix ABICCTT is defined as follows (note that according to (9), Q is self-inhibitive and this can be demonstrated by a negative entry such as −ζ in matrix ABICCTT ). ⎤ ⎡ −h 1 0 ··· 0 λ −r1 CW ⎥ ⎢ −h2 ⎢ 0 ··· 0 λ −r2 ⎥ CW ⎥ ⎢ ⎢ ··· ··· ··· ··· ··· ··· ⎥ ⎥ ⎢ ABICCTT = ⎢ ⎥. −hk ⎥ ⎢ 0 λ −r 0 · · · k C ⎥ ⎢ W ⎥ ⎢ −α 0 ⎦ ⎣ −β −β · · · −β CC −ζ εe1 εe2 · · · εek 0 Regarding this matrix, it can be easily found that, to satisfy conditions of (12) and (13) and hence stability guarantee, the following constrains can be considered in setting of BICCTT’s parameters: ∀, hi = 0, α = 0, λ = β and ri = εei .

(14)

3.2.2 Equilibrium performance guarantee According to (7)–(9), the equilibrium behavior of BICCTT can be defined as follows:   k  C −β Wj = 0, α 1− Cc j=1

(15)

Jamali S, et al.

Sci China Inf Sci

June 2011 Vol. 54 No. 6

  W + λC − ri Q = 0, hi 1 − CW k 

ei Wi − m = 0,

where

1257

where i = 1, . . . , k,

(16)

   m = min B, Q + Wj .

(17)

i=1

j

On the other hand, from equilibrium perspective, objective goals of our design can be written as follows: k 

High utilization:

Wj = B,

(18)

j=1

Empty queue (zero drop) :

Q = 0,

(19)

Fairness : for

Wj = Wi .

(20)

i, j = 1, . . . , k,

We apply (18)–(20) to (15)–(17) to extract required conditions. This process leads to (21) (note that in the equilibrium, we expect the bottleneck link to be fully-utilized; hence free capacity of link (C) will be around zero): (21) ∀i, ei = 1, β = 1/B. We can integrate (14) and (21) in the form of (22) which guarantees globally convergence and equilibrium performance of BICCTT: ∀ i, λ = ri = β = ε = 1/B, CC = CW = B, ei = hi = α = 1.

(22)

Setting of hi = α = 1 means that, in each step Wi and C can be increased by a coefficient of 2. We take ri = 1/B to assign equal weight for Q and C in eq. (8).

4

Packet-level implementation of BICCTT

We now present a Source/AQM algorithm to implement the proposed model in the communication networks. Like TCP, BICCTT is a window-based congestion control protocol. According to (7)–(9), source i needs C, Q and CW to update his congestion window (Wi ) and these variables can only be maintained in the congested router, so each BICCTT packet carries a congestion header, which is used to communicate congestion information from router to sources. Since λ = ri = 1/B, hence router feeds back C − Q, instead of C and Q to save packet headers. Therefore, the header includes three fields: Hdr CQ = The Last Value for “C − Q”, Hdr F lN um = Number of Flows (k), Hdr Share = Fair Share of Congested Link Bandwidth (B/k). BICCTT algorithm has three parts: router’s algorithm, sender’s algorithm and receiver’s algorithm. Router’s algorithm. The function of a BICCTT router is to compute the control variables and feedback them to cause the system to converge to optimal efficiency and max-min fairness. BICCTT router’s algorithm can be summarized as follows: At time RT T , 2RT T , 3RT T , . . . congested router: 1. Receives Wi packets from all of the sources si ∈ S that goes through bottleneck link (its capacity is B bps). 2. Computes k (passing flows number), RT T (averaged RT T of all passing flows), C and Q. 3. Inserts k, C − Q and B/k in header of all passing packets. Estimation of router’s current average RT T and number of passing flows from bottleneck link can be done by using the approach proposed in [19].

1258

Jamali S, et al.

Sci China Inf Sci

June 2011 Vol. 54 No. 6

Receiver’s algorithm. BICCTT receiver is similar to a TCP receiver except that when acknowledging a packet, it copies the congestion header from the data packet to its acknowledgment. BICCTT receiver: 1. Receives packets and extracts k, B/k, C − Q from their header. 2. Inserts k, B/k and C − Q in sent ACK packets. Sender’s algorithm. BICCTT sender’s function revolves around adjusting its sending rate based on received feedback. Sender: 1. Receives ACK packets and extracts k, B/k and C − Q from their header. 2. If there is any change in extracted values, re-computes new congestion windows size:     Wi dWi = W i hi 1 − + λC − ri Q , where Cw = Hdr Share × Hdr F lN um, dt CW C − Q = Hdr CQ, λ = ri = 1/B = 1/CW . One important point in this protocol is its fast response to variations of network environments. Unlike other protocols such as TCP and XCP (eXplicit congestion notification protocol [19]), BICCTT’ source does not wait for RTT duration to adjust its sending rate; rather, it re-computes new sending rate upon sensing any change in receiving feedbacks. To implement this protocol, we use the packet-level simulator ns-2 [20], and modify the XCP module to implement BICCTT’s sender, receiver and router algorithms.

5

Packet-level simulation results

We present a group of simulation results to demonstrate the validity of our design. We demonstrate through extensive simulations that BICCTT outperforms TCP/RED, especially in high bandwidth delay environments and behaves better than XCP in many scenarios. Our simulations also show that BICCTT never drops any packet. Also, it dampens oscillations and smoothly converges to high utilization, small queue size and fair bandwidth allocation. 5.1

Simulation setup

Our simulations use the topology in Figure 1. The bottleneck capacity, the round trip delay, and the number of flows vary according to the objective of the experiment. The buffer size is always set to the delay-bandwidth product. The data packet size is 1000 bytes. Simulations’ running times vary depending on the propagation delay but are always larger than 300 RT T s. All simulations were run long enough to ensure that the system has reached a consistent behavior. We compare BICCTT with TCP Reno/RED and XCP. TCP/RED is the most common congestion control scheme that is used today and XCP is the most efficient congestion control scheme that has been developed so far (especially in high bandwidthdelay product environments). We present two series of simulations. In the first group of simulations we focus on long-term average behavior and study bottleneck utilization, queue size, packet drop and throughput. The second group of simulations focuses on short-term dynamics of BICCTT. 5.2

Long term average behavior of BICCTT

To study different aspects of BICCTT, in this section we present a set of simulation results that show behavior of BICCTT for a wide range of bandwidth, RT T and flows number. 5.2.1

Effect of capacity

We show that an increase in link capacity (with the resulting increase of per-flow bandwidth) will cause a significant degradation in TCP’s performance. In this experiment, 50 long-lived FTP flows share a bottleneck. The round trip propagation delay is 80 ms and bottleneck capacity is varied from 2 Mbps to 4 Gbps to study its effects. Figure 3 demonstrates that as capacity increases, TCP/RED’s bottleneck

Jamali S, et al.

Figure 3

Sci China Inf Sci

June 2011 Vol. 54 No. 6

1259

BICCTT outperforms TCP/RED and is similar to XCP in high bandwidth environments.

utilization decreases significantly. By contrast, XCP and BICCTT utilizations are always near optimal independent of the link capacity. Furthermore, XCP and BICCTT never drop any packet, whereas TCP drops thousands of packets. Although the XCP and BICCTT’s queue increases with the capacity, it is quite negligible as shown in Figure 3. 5.2.2

Effect of feedback delay

In this experiment, we fix the bottleneck capacity at 150 Mbps and study the impact of increased delay on the performance of congestion control. Flows number is 50 and all other parameters have the same values used in the previous experiment. Figure 4 shows that as the propagation delay increases, TCP/RED’s utilization degrades considerably. It also shows that, when RT T goes beyond 1000 ms, XCP’s utilization drops very fast. By contrast, BICCTT maintains high utilization independently of delay. 5.2.3

Effect of number of flows

This experiment fixes the bottleneck bandwidth at 150 Mbps and RT T at 80 ms and repeats the same experiment with a varying number of FTP sources. Other parameters have the same values used in the previous experiment. Figure 5 shows that BICCTT shows good utilization, near zero queue size, and no packet loss. As we see in Figure 5, TCP’s performance is quite low in contrast with XCP and BICCTT. The figure shows that XCP queue size increases as the number of flows increases. 5.3

Dynamic of BICCTT

While the simulations presented above focus on long-term average behavior, this section presents the short-term dynamics of BICCTT. 5.3.1

Convergence dynamics

In order to address the adaptability of BICCTT with variations in traffic demands, we consider another scenario on Figure 1. We simulate this network with bottleneck capacity of 200 Mbps, shared by five sources. Only two sources are active at time 0, every 4 s thereafter one more source becomes active until all five sources are active. At times t=24, 32, 40 s three sources close their connections and therefore two sources are active. All sources have the same RT T of 80 ms. In reference to the results of Figure 6, we

1260

Jamali S, et al.

Figure 4

Sci China Inf Sci

June 2011 Vol. 54 No. 6

BICCTT outperforms TCP/RED and XCP in high delay environments. BICCTT behaves more efficiently than

XCP in aspect of bottleneck utilization.

Figure 5

BICCTT is efficient with any number of flows.

note that the source rates track the expected equilibrium when new sources activate or a source deactivates. After a short transient phase, in the equilibrium stage the bandwidth is shared equally among the sources regardless of their count and utilization remains around 100%. Figure 6 shows that the BICCTT is stable around its equilibrium and dampens oscillations and converges smoothly to high utilization small queues and fair bandwidth allocation. This figure also shows that BICCTT’s speed of convergence is more than XCP. BICCTT and XCP do not drop any packet in this scenario and their queue sizes are similar, excluding initial peak in BICCTT’s queue size. 5.3.2

Fairness dynamic

As we know, TCP’s throughput is inversely proportional to the RT T , so fairness too might become a problem, as users with different RT T s compete for the same bottleneck capacity. We show that BICCTT allocates bandwidth more fairly than TCP.

Jamali S, et al.

Figure 6

Sci China Inf Sci

June 2011 Vol. 54 No. 6

1261

BICCTT is converging to its new equilibrium smoothly, when number of flows is varied.

We have five long-lived FTP flows sharing a single 50 Mbps bottleneck. In this simulation, the flows have different RT T s in the range [40 ms, 80 ms] (RT Ti+1 = RT Ti +10 ms). The simulation results of this experiment are shown in Figure 7. In spite of different RT T for various sources, BICCTT allocates bandwidth fairly for different sources and throughput of each source is equal to 10 Mbps. As we see in the figure, due to difference of RTT s, congestion windows of different sources are different to ending same throughput for each source.

5.3.3

Dynamic of BICCTT in high bandwidth-delay product environment

As we know, the TCP functions poorly in high bandwidth-delay product networks because of its slow response with large congestion windows [3]. In order to study BICCTT’s behavior in such environments, we increase bottleneck capacity of Figure 1 to 1.5 Gbps, and RTT to 500 ms. Figure 8 shows the simulation results for four sources. This figure shows that our algorithm improves performance of connections (bottleneck utilization is always near one, BICCTT’s queue size is smaller than XCP and its drops count is zero) as well as remaining fair when the bandwidth-delay product increases. According to Figure 8(a), XCP’s bottleneck utilization converges a little faster than BICCTT, but its queue size is larger than BICCTT. Also, we see in Figure 8(b) that throughput of BICCTT’s flows converges faster than XCP’s flows to their fair equilibrium.

1262

Jamali S, et al.

Figure 7

Figure 8

Sci China Inf Sci

June 2011 Vol. 54 No. 6

BICCTT operates fairly in bandwidth allocation.

BICCTT in high bandwidth-delay product network. (a) BICC behaves efficiently in high bandwidth-delay

product network; (b) BICC converges fast in high bandwidth-delay product network.

6

A TCP-friendly BICCTT

In previous section, we considered a pure network for each of TCP/RED, XCP and BICCTT schemes, and did not take into account their coexistence. This was due to this fact that each of these mechanisms needs its own AQM algorithm to compute mechanism-specific variables. In this subsection, we describe a mechanism allowing BICCTT to compete fairly with TCP in the same network. This design can be used to allow BICCTT to exist in a multi-protocol network. To start a BICCTT connection, the sender must check whether the receiver and the routers along the path are BICCTT-enabled. If they are not, the sender reverts to TCP or another conventional protocol. These checks can be done using simple TCP and IP options. We can extend the design of a BICCTT router to handle a mixture of BICCTT and TCP flows while ensuring that BICCTT flows are TCP-friendly. The router distinguishes BICCTT traffic from non-BICCTT traffic and queues it separately. TCP packets are queued in a conventional RED queue. BICCTT flows are queued in a BICCTT-enabled queue. To be fair, the router should process packets from the two queues such that the average throughput observed by BICCTT flows equals the average throughput observed by TCP flows, irrespective of the number of flows. This is done using weighted fair queuing with two queues where the weights are dynamically updated and converge to the fair shares of BICCTT and TCP.

7

Conclusions

In this paper we have made an attempt to design a bio-inspired congestion control algorithm. Therefore, the following steps were considered: i) redefining the congestion control problem as population control

Jamali S, et al.

Sci China Inf Sci

June 2011 Vol. 54 No. 6

1263

of W species; ii) choosing a tri-trophic food chain as a natural population control framework to control population size of W species; iii) deriving a congestion control model from mathematical model of the tri-trophic food chain; iv) setting BICCTT’s parameters regarding stability and performance guarantee; v) simulative studying equilibrium and dynamic properties of the proposed model in ns-2 environment. Simulation results show that the proposed algorithm globally converges to its fair and high-performance equilibrium.

References 1 Jacobson V. Congestion avoidance and control. In: Proceedings of the ACM Symposium on Communications Architectures and Protocols, Stanford, USA, 1988. 314–329 2 Floyd S, Jacobson V. Random early detection gateways for congestion avoidance. IEEE/ACM Trans Netw, 1993, 1: 397–413 3 Floyd S. HighSpeed TCP for large congestion windows, RFC 3649, http://www.ietf.org/rfc/rfc3649.txt, 2003 4 Low S H, Paganini F, Wang J, et al. Dynamics of TCP/RED and a scalable control. IEEE Infocom, 2002, 1: 239–248 5 Wang J. A theoretical study of Internet congestion control: Equilibrium and dynamics. Dissertation for PhD Degree. Pasadena: University of Caltech, 2005 6 D’haeseleer P, Forrest S. An immunological approach to change detection: Algorithms, analysis and implications. In: Proceedings of the 1996 IEEE Symposium on Computer Security and Privacy, Oakland, USA, 1996. 110–119 7 Hofmeyer S. An immunological model of distributed detection and its application to computer security. Dissertation for PhD Degree. Albuquerque: University of New Mexico, 1999 8 Dressler F. Efficient and scalable communication in autonomous networking using bio-inspired mechanisms—an overview. Informatica, 2005, 29: 183–188 9 Elizabeth S, Rhodes J A. Mathematical Models in Biology: An Introduction. Cambridge: Cambridge University Press, 2003 10 Murray J D. Mathematical Biology: I. An Introduction. 3rd ed. Berlin: Springer-Verlag, 2002 11 Analoui M, Jamali S. A conceptual framework for bio-inspired congestion control in communication networks. In: Proceedings of the 1st International Conference on Bio-inspired Models of Network, Information and Computing Systems, Trento, Italy, 2006. 1–5 12 Analoui M, Jamali S. Bio-inspired congestion control: Conceptual framework, algorithm and discussion. Stud Comput Intell, 2007, 69: 63–81 13 Analoui M, Jamali S. Nature-inspired congestion control: Using a realistic predator-prey model. Lect Notes Comput Sci, 2007, 4527: 416–426 14 Analoui M, Jamali S. Equation-based congestion control in the Internet biologic environment. J LNS Trans Comput Syst Biol, 2007, 4789: 42–62 15 Analoui M, Jamali S. Congestion control in the Internet: Inspirationfrom balanced food chains in the nature. J Netw Syst Manage, 2008, 16: 1–10 16 Takeuchi Y, Adachi N. Global stability of ecosystem of the generalized volterra type. Math Biosci, 1978, 42: 119–136 17 Kelly F. Mathematical Modeling of the Internet, Mathematics Unlimited—2001 and Beyond. Berlin: Springer-Verlag, 2001 18 Analoui M, Jamali S. TCP fairness enhancement through a parametric mathematical model. In: Proceedings of the 1st International Conference on Computers, Communications and Signal Processing with Special Track on Biomedical Engineering, Kuala Lumpur, Malaysia, 2005. 91–95 19 Katabi D, Handley M, Rohrs C. Congestion control for high bandwidth-delay product networks. In: Proceedings of ACM SIGCOMM 2002, Pittsburgh, USA, 2002. 89–102 20 Ns-2, Network Simulator, www.isi.edu