Congestion Window

Fig. 3. Internet Ecosystem Typology

Fig. 3. Internet Ecosystem Typology the amount of data the sender can transmit into the network before receiving an acknowledgment (ACK). We assume that all connections are long-lived and have unlimited bulk data for communication.

In analogy, this network can be viewed as an ecosystem that connects a wide variety of habitats such as routers, hosts, links and operating systems (OS), and etc. We consider that there is some species in these habitats such as "Human", "Computers", "Congestion Window"(W), "Packet Drop"(P) and "Queue Length"(q), "link utilization" (u) and so on. Fig. 3 shows the typology of Internet ecosystem from congestion control perspective. Since these species interact, the population size of each species is affected. In general, there is a whole web of interacting species, which makes for structurally complex communities. Fig. 3 shows that the Congestion Window (W) is a species that lives in the hosts. Let the population of W in source Si be Wi (congestion window size of connection i) and assume that each organism of this population sends one packet in each RTT. It is clear that if the population of this species is increased, then the number of sent packet will be inflated; hence, the population size of W should be controlled to avoid congestion. In order to control the population size of W species, we use some population control tactics of nature. In the following sections, we propose a methodology to use "Perdition" and "Competition" tactics for this purpose.

2.2 Types of Population Interactions

As mentioned, we need to build and validate simplifying abstract representations and models of the biology. Since the population control tactics of nature are candidate to be used for bio-inspired congestion control algorithms, hence, let us take an overview of types of population interactions, to put the rest of this section in context [27]. These interactions can be considered between populations:

Mutualism: Mutualism is any relationship between two species of organisms that benefits both species. Most people think of when they use the word "symbiosis" this relationship.

Herbivores: Herbivores eats pieces of plants, this harms the plant in some way, and population growth is slowed.

Parasites: Parasites do not kill the host outright, necessarily. They might cause it to be weak and die for other reasons, or might make lower the birth rate. Predation: This interaction refers to classical predators that kill individuals and eat them; such as carnivores, insectivores and etc. We can summarize this interaction as below:

(1) In the absence of predators, prey would grow exponentially. (2) The effect of predation is to reduce the prey's growth rate. (3) In the absence of prey, predators will decline exponentially. (4) 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. There are no handling time or satiation constraints on predators.

One of the first models to incorporate interactions between predators and prey was proposed in 1925 by the American biophysicist Alfred Lotka and the Italian mathematician Vito Volterra. The Lotka-Volterra model [28] describes interactions between two species in an ecosystem, a predator and a prey. Since we are considering two species, the model will involve two equations, one, which describes how the prey population changes, and the second, which describes how the predator population changes. For concreteness, let us assume that the preys in our model are rabbits, and that the predators are foxes. If we let r(t) and f(t) represent the number of rabbits and foxes, respectively, that are alive at time t, then the Lotka-Volterra model is:

Where the parameters are defined by:

a is the natural growth rate of rabbits in the absence of predation, b is the death rate per encounter of rabbits due to predation, c is the efficiency of turning predated rabbits into foxes, d is the natural death rate of foxes in the absence of food (rabbits). For example there is a classical set of data on a pair of interacting populations that come close: the Canadian lynx and snowshoe hare pelt-trading records of the Hudson Bay Company over almost a century. Fig. 4 (from Odum, Fundamentals of Ecology, Saunders, 1953) shows a plot of that data.

Fig. 4. Fluctuation in the number of pelts

Competition: Here two or more species compete for the same limited food source or in some way inhibit each other's growth. For example, competition may be for territory, which is directly related to food resources. Here we discuss a very simple competition model, which demonstrates a general principle, which is observed to hold in Nature, namely, that when two species compete for the same limited resources. Consider the basic 2-species Lotka-Volterra competition model with each species n and n2 having logistic growth in the absence of the other. Inclusion of logistic growth in the Lotka-Volterra systems makes them much more realistic, but to highlight the principle we consider the simpler model which nevertheless reflects many of the properties of more complicated models, particularly as regards stability. We thus consider.

Where h1, l1, r2, l2, f12 and f21 are all positive constants and the his are the linear birth rates and the lis are the carrying capacities. The fn and f2i measure the competitive effect of «2 on n, and n, on «2 respectively: they are generally not equal.

2.3 Evaluation Parameters

We pose the objective of finding a protocol that can be implemented in a decentralized way by sources and routers, and controls 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. All of these are required to be scalable, i.e. hold for an arbitrary network, with possibly high capacity and delay. We first specify the design objectives for the equilibrium point to be achieved by our system:

1. Network utilization: Link equilibrium rates should of course not exceed the capacity (B), but also should attempt to track it. 2. Equilibrium queues should be empty (or small) to avoid queuing delays and achieve constant RTT. 3. Resource allocation fairness: Congested link bandwidth should be allocated fairly among the sources.

Equilibrium considerations are meaningful if the system can operate at or near this point; for this reason we pose as a basic requirement the stability of the equilibrium point. Ideally, we would seek global stability from any initial condition, but at the very least, we should require local stability from a neighborhood. This objective is sometimes debated, since instability in the form of oscillations could perhaps be tolerated in the network context, and might be a small price to pay for an aggressive control. In other terms some ones believe that instability in the form of oscillations is better than stability that is realized through an aggressive control.

In summary, network flow control concerns adjustment of individual transmission rates of a number of sources over a set of links, subject to link capacity constraints. The main purpose of flow control is to fully utilize all the links in the network, while at the same time achieving some sort of fairness among the sources. It is also desirable that congestion control system operates in a stable regime.

3 Predator-Prey Approach: Congestion Control Using Predator-Prey Model

In order to clarify the similarity between TCP/AQM1 congestion control mechanism and predator-prey interaction, we look at the TCP/AQM running on a network: (1) In the absence of packet drop (P), congestion window (W) would grow. (2) On the occurrence of a packet drop, congestion window size would decline. (3) Incoming packet rate contribution to packet drop growth is proportional to available traffic intensity, as well as, the packet drop rate itself. (4) In the absence of a packet stream, for sustenance, packet drop rate will decline. We see that this behavior is close to the predator-prey interaction. This similarity motivates us to use predator-prey approach to control population size of W;s. We define two class of predator species that can prey W,-s Suppose that there are K species, Pj, P2,..., Pk in the congested router. Pi can prey all the W individuals but there can be a weighting preference for Pi to prey Wi several times more significant to all other Wk (k^i) individuals. A similar relation can also be imagined between "queue occupancy" in congested router (q) and "congestion window size" (W) of the sources sharing this queue. Hence the interactions of (P, W) and (q, W) has been considered as predator- prey interaction.

To specify a congestion control system, it remains to define (i) how the sources adjust their rates based on their aggregate prices (the TCP algorithm), and (ii) how the links adjust their prices and queue size based on their aggregate rates (the AQM algorithm). We can in general postulate a dynamic model of the form

Since we adopted predator-prey interaction for population control of W, hence we use generalized Lotka-Volterra predator-prey system to drive F, G an H. This deliberation leads to the following Bio-inspired distributed congestion control algorithms.

0 0

Post a comment