Study of TCP friendliness of CEAS routing system in comparison with Distance Vector Routing and Link State Routing

June 2009

Bjarne Emil Helvik, ITEM Otto J Wittner, ITEM

Sasu Tarkoma, External (TKK)

Master in Security and Mobile Computing

Submission date:

Supervisor:

Co-supervisor:

Norwegian University of Science and Technology

Study of TCP friendliness of CEAS routing system in comparison with

Distance Vector Routing and Link State Routing

Sandeep Tamrakar

Problem Description

Ensuring that a network treats TCP traffic in a "friendly" manner has been an important topic for at least a decade. A promising stochastic path management (routing) system known as CEAS (Cross Entropy Ant System) has been developed at the department and Q2S. An important issue is the level of "TCP friendliness" CEAS may provide. To investigate this and related questions, it is suggested to perform comparative studies of the performance of CEAS based and distant vector based routing.

Work toward this objective ha started as an autumn project, using ns-2 as a tool. The master thesis is

a continuation of this work, where it will be look at more complex network scenarios. For instance:

- various topologies.

- dependence on the traffic source characteristics.

- multiple TCP streams and background traffic.

- a range of failure characteristics, including link failures statistic observed in operational networks

An expected outcome of the study is a mapping of the pros and cons of CEAS routed network relative to distant vector routing for this kind of transport.

Assignment given: 15. January 2009

Supervisor: Bjarne Emil Helvik, ITEM

Withtheontinuousdevelopmentof theInternettehnologiesnewroutingrequire-

mentshavesurfaed. Inresponse, several adaptive,stohastirouting algorithmshave

been purposed. The Cross Entropy Ant System (CEAS) is an adaptive, robust and

distributed routing and managementsystem basedon the swarm intelligene. Several

prototypeimplementationsandenhanementshavebeenmadeonthissystem,however

the level of TCP friendlinessthe CEAS may provideis yetan important issue.

In order to investigate the level of TCP friendliness, the behavior of the CEAS

system during dierent network dynamis needs to be understood. For this reason,

the behaviorof the CEAS system under dierent networkeventand its orresponding

eets onTCPperformaneisexaminedrstusingasimplenetwork. Laterthe levelof

TCP performaneismeasuredonomplexnetworks. Alsotheloadsharingapabilities

of the CEAS system isinvestigated the eieny of the system tomanageandupdate

aording to the network load. Additionally the results are ompared against the

resultsobtainedfromthestandardLinkStateRoutingprotoolandtheDistaneVetor

Routing protoolunder similaronditions.

In this work,we ndthat the updateproess inresponse tothe hange innetwork

dynamis is slower on CEAS ompared to the other systems. However, the update

proess speeds up with the inrease in the ant rates. During suh period the use

of multiple path redues the TCP performane. We also nd that large amount of

pakets loop around some links during link failures. Suh looping redues the TCP

performane signiantly. However, implementing previous hop memory tehnique

failure.

ComparetotheLSRPandtheDVR,wendthatCEASmanagesnetworkresoures

more eiently to produe higher TCP performane. We nd that the CEAS diverts

the data tra on the basis of the quality of the path rather than the length of the

path. WealsondthattheCEAS systemhandlesmultipleTCPstreamindependently

with equal priority. But the smaller transition delay on the ants ompared to the

data paket redues the TCP performane to some extent. However, foring the ants

to experiene longer queuing delay aording to the tra load improves the TCP

performane aswell ashelps CEAS update more aurately.

This text is submitted as the onluding part of my Master of Siene degree in

Seurity and Mobile Computing in the NordSeMob program. This work has been

arriedout atthe Departmentof Telematis(ITEM), Norwegian University ofSiene

and Tehnology (NTNU)during the spring of 2009.

IwouldliketothankmysupervisorProfessorBjarneE.HelvikandmytutorOttoJ.

Wittner, Post Do atthe Center of QuantiableQualityof Servie inCommuniation

System, Centre of Exellene (Q2S), for all their guidane, assistane and valuable

feedbaks throughout the period of this thesis. Additionally, I would like to thank

Professor Sasu Tarkoma at the Helsinki University of Tehnology (TKK) in Finland

for his supervision. Speial thanks to Laurent Paquereau, Phd at Q2S for providing

the requiredmaterials forthis thesis, hisguidane and assistane.

Sandeep Tamrakar

NorwegianUniversityofSiene andTehnology(NTNU),Trondheim

June2009

ABC Ant Based Control

ACK Aknowledgement

AIMD AdditiveInrease and MultipliativeDerease

CBR Constant Bit Rate

CE Cross Entropy

CEAS Cross Entropy Ants System

wnd ongestion window

DUPACK Dupliate Aknowledgement

DVR Distane Vetor Routing

FIB ForwardingInformation Base

Gbps Gigabits perseond

IGP InteriorGateway Protool

IP InternetProtool

IS-IS IntermediateSystem to Intermediate System

Kbps Kilobits per seond

LSA Link State Advertisement

LSRP Link State RoutingProtool

Mbps Mega bits perseond

MSS Maximum Segment Size

NS 2 Network Simulator 2

OSPF Open Shortest Path First

RIP Routing InformationProtool

RTO RetransmissionTime Out

RTT Round TripTime

SACK Seletive Aknowledgement

SMSS Sender Maximum SegmentSize

ssthresh slow-start threshold

TCP Transmission ControlProtool

TTL Time To Live

UDP UserDatagram Protool

Abstrat i

Aknowledgements iii

Abbreviations and Aronyms v

List ofTables x

List ofFigures xi

Chapter 1 Introdution 1

1.1 IntrodutionandMotivation . . . 1

1.2 Related Works . . . 3

1.3 ResearhMethods . . . 4

1.4 Struture of thesis . . . 5

Chapter 2 Bakground 7 2.1 Stohasti Routing . . . 7

2.2 AntRouting . . . 8

2.3 Cross Entropy AntSystem . . . 9

2.4 Link State Routing(OSPF) . . . 11

2.5 Distane Vetor Routing(RIP) . . . 12

2.6 TCP . . . 12

2.6.1 TCPongestionontrol . . . 12

2.6.1.1 Slow start / ongestionavoidane . . . 13

2.6.1.2 Fast Retransmit /Fast Reovery . . . 14

2.7 Eet of Stohasti Routingon TCP . . . 15

Chapter 3 Simulation Module 21

3.1 SimulatorBasis . . . 21

3.2 CEAS Extension Modiation . . . 22

3.2.1 CEASForwardingUnitImplementation . . . 23

3.2.2 CostPathModiation . . . 23

3.2.3 ReordSingleHopRouteAddressImplementation . . . 24

3.3 Prodution . . . 24

3.4 Parameters . . . 25

3.5 Topologies . . . 27

3.6 Network Dynamis . . . 27

3.6.1 TCPConnetions . . . 28

3.6.2 BakgroundTra . . . 29

Chapter 4 Measuring TCPperformane on CEASsystem 31 4.1 Performane Metris . . . 33

4.2 TCP performane onsteady-state network . . . 33

4.3 TCP performane duringLink Failure . . . 39

4.4 TCP performane duringLink Congestion . . . 44

4.5 The eet of dierent apaity linkson TCP. . . 48

4.6 Multiple TCP onnetions. . . 49

4.7 Previous Hop memory . . . 54

Chapter 5 Case Study 59 5.1 Performane Metris . . . 59

5.2 TCP performane using 12node network . . . 60

5.2.1 TCPperformaneonsteadynetwork . . . 61

5.2.2 TCPperformaneduring multiplelink failures . . . 64

5.2.3 TCPperformaneduring frequenttransientlinks . . . 67

5.3 TCP Performane onlarge Topology . . . 72

Chapter 6 Conlusion and Future Works 81 6.1 Conluding remarks . . . 81

6.2 Future works . . . 83

Appendix B CEAS extension modiation 89

B.1 Forwarding Unit . . . 89

B.2 Link ost modiation . . . 90

Appendix C The eet ofdierentapaity linkson TCP 91

Appendix D MultipleTCP stream on LSRP and DVR 93

Appendix E Loations ofthe 58 node Uninett Network 95

3.1 CEAS parameters . . . 26

3.2 LSRPparameters. . . 26

3.3 DVRparameters . . . 26

4.1 TCPonguration . . . 35

4.2 PheromoneStabilizationPhasewithEliteSeletiononAllAnts . . . 35

4.3 TCPthroughputduringmultiple onnetions . . . 50

4.4 TCPThroughputduringmultiple onnetionat paket sizeof9000bytes . . . 52

5.1 TCPonguration . . . 61

5.2 Bakgroundtraparameters . . . 61

2.1 TCPongestionontrolmehanism. . . 14

4.1 A simple11nodenetwork . . . 32

4.2 PheromoneStabilization period . . . 36

4.3 TimerequiredforTCPto transmitwithFullDataRate . . . 37

4.4 wndat dierentantrate . . . 38

4.5 Out-of-orderpaketreeivedat Antrate5(aninstaneofsimulation) . . . 38

4.6 Re-stabilizationphase . . . 40

4.7 TimerequiredforTCPto resumetransmissionafterLinkFailure . . . 41

4.8 TimerequiredforTCPto regainfulldatarateaftertransmissionis resumed . . . 42

4.9 Miro-LoopsafterLinkFailure . . . 42

4.10 TimerequiredforTCPto regainfulldatarateafterlinkre-establishment . . . 43

4.11 TCPThroughputduringongestion . . . 45

4.12 TCPThroughputondierentsystemwithLargepaketsize . . . 47

4.13 PheromoneDistributionatnode3 . . . 51

4.14 PheromoneDistributionatnode3usingpaketsizeof9000bytes . . . 53

4.15 Comparison of TCP data rate between TCP Reno and TCP Sak (results from an instaneofasimulation) . . . 53

4.16 Miro-loopingduringLinkfailure . . . 54

4.17 averageperentagegaininTCPThroughput . . . 56

5.1 12nodesnetwork. . . 60

5.2 TCPConnetTime. . . 62

5.3 TCPThroughputatvariouslevelsofbakgroundtraloads . . . 63

5.4 TCPGoodputatvarious levelsofbakgroundtraloads . . . 64

loads . . . 65

5.6 TCPGoodputduringmultiplelinksfailureat variouslevelsofbakgroundtra loads 66 5.7 TCP data retransmission during multiple links failure at 1000 Kbps of bakground traloads . . . 67

5.8 TCPperformaneafter usingonehopmemorytehnique. . . 68

5.9 TCPThroughputunderfrequenttransientlinksat variouslevelsofbakgroundtra loads . . . 69

5.10 TCPGoodputunderfrequenttransientlinksatvariouslevelsofbakgroundtraloads 70 5.11 TCPperformaneafter usingonehopmemorytehnique. . . 71

5.12 UninettTopologyOt2007. . . 73

5.13 TCPThroughputofrstTCPonnetion . . . 75

5.14 TCPdatatransmissionofrstTCPonnetion . . . 76

5.15 TCPThroughputofseondTCPonnetion . . . 77

5.16 TCPThroughputofthirdTCPonnetion . . . 78

5.17 TCPThroughputoffourthTCPonnetion . . . 79

A.1 NS2Nodelayout . . . 85

A.2 NodeLayout . . . 86

A.3 Arhitetureof NetworkLayerUnit . . . 87

C.1 TCPthroughputwhentheshortestpathhaslowerlinkapaity . . . 92

C.2 ImprovedTCPperfromaneafterinreasingpaketsizeto9000bytes. . . 92

D.1 DataratesofTwoTCPstreamonLSRPandDVR . . . 93

Introdution

1.1 Introdution and Motivation

WiththeontinuousdevelopmentoftheInternettehnologies,largeamountofnew

appliations based on the Internet is being evolved. As a onsequene, the volume of

data traisgrowingenormously. Suhhugetraallsfornew routingrequirements

those that are salable,self adaptive and self manageable. In other words, we require

routing algorithms that detet and utilize its available network resoures, distribute

data traarossmultiplepathsandquiklyadapttothehangingnetworkloadsand

the network topologiestoprodue lowlateny,lowloss andhigh throughput. A study

by Tangmunarunkit etal. [35℄ shows that the urrent IP routing does not make good

utilization of itsavailable network resoures in order toprovide high throughput. For

example, inanetworktheremayexistsome pathotherthantheroutingpoliydened

paththathasmorenumberofintermediarynodesandyetproduesbetterperformane

than the predened path.

Inresponsetotheserequirements,severaladaptivestohastialgorithmshavebeen

purposed that makeuse of multi-pathrouting. Further,self-organized, distributed al-

gorithms inspired by the native behavior of ants have been studied for a while. Suh

systems are referred to asSwarm Intelligene 1

. Algorithms based onant olony opti-

1

SwarmIntelligeneisadeentralized,self-organizedsystemsthatresultsinanoptimalsolutionbyolletivebehavior

mizationshavebeenappliedtosolvevariousombinatorialoptimizationproblemssuh

as traveling salesman problem, quadrati assignment, protein folding, graph oloring

et. Suh algorithms have been proposed for network routing as well. AntNet [7℄,

Ant-based Control [32℄, Adaptive Swarm-based Routing [36℄ et are some of the ex-

amples of ant based routings. In these algorithmsthe swarming behavior of ants are

represented bymobileagentsthatowthroughoutthe networkand olletinformation

that are later used formanagingand ontrolling the network.

Typially antbased routing are studiedwith fous on datagram network i.e. User

Datagram Protool(UDP) asatransportlayerprotool [ 7, 10℄ . However, mostof the

appliationsontheInternetuse TransmissionControlProtool(TCP)asthetransport

layer protool for reliability. The nature of adaptive routing is that it makes use

of dierent available paths to transmit data of the same session. At eah node the

probability of seleting next node is based on the quality of the path between them.

At the destination, the data following dierent paths may reah out of order. UDP

respondstheout-of-order pakets simplybydisardingthem. However, beyond ertain

threshold, TCP assumes suh out-of-order delivery is due to the network ongestion

and responds by dereasing TCP throughput. Therefore, the behavior of the TCP on

a network using antbased routing shouldbewell studied.

A promisingstohastipath managementsystem,basedonthe swarmingbehavior

of ants and the rare event optimizationmethodross entropy, know asCross Entropy

AntSystem (CEAS) has been developed at the departmentof Telematis, NTNU and

Q2S. Several prototype implementations and enhanements have been made on the

system, however the level of TCP friendlinessCEAS may provide isyet animportant

issue.

The mainobjetiveofthis workistounderstandthe behaviorofthe CEAS during

dierent network events and its orresponding eets on the TCP performane. The

timetakenbytheCEAStoupdatethesysteminresponsetothehangeinthenetwork

dynamis is an important fator. This helps us to understand how well the TCP

ofsimpleloalinterationsbetweenelementsofthesystem.

performs during suh events. Thus a part of the work inludes measurement of the

CEAS update proess and the behavior of the TCP during suh period. The other

important issues are to nd out the performane of TCP during network ongestion,

the load sharing apabilities of the CEAS system et. One of the main objetive of

this study is also to ompare the results against other standard routing systems suh

as Link State Routingand Distane Vetor Routingunder similar onditions.

1.2 Related Works

Ant Based Control (ABC) by Shoonderwoerd et al. [32℄ was the rst attempt

to implementanant basedoptimizationmethod tothenetwork routing. Howeverthis

is limited to the symmetri iruit swithed teleommuniation network and is not

appliable to the paket swithing network like the Internet. Dorigo and Di Caro [7℄

laterintroduedAntNetwhihisdesignedforpaketswithing,onnetionlessnetwork.

The Cross Entropy Ants System, purposed by Helvik and Wittner [16℄ , forms the

groundwork for this work.

GodomskaandPautin [ 10℄havestudiedthebehaviorofTCPonantbasedrouting

likeAntNetandAdaptiveSwarm-based Routing. They onludedthat,althoughTCP

sets higherdemands onthe adaptationproess,the loadrangeof thenetworkouldbe

extended inawaytoprovideeientroutingpoliies. However, their studywasbased

on the omparison of TCP performane againstUDP.

In Master's projet [33℄ , we ompared and analyzed the TCP performane in a

network applying CEAS based stohasti routing against Link State Routing OSPF.

The TCPperformane weremeasuredusingfators likeConnettime, throughputand

goodputs. The study was based on a small network with only one TCP onnetion

withvariousbakgroundtraloads. Duringtheprojetwefoundthatalargeamount

of TCP pakets were lost due to looping after linkfailures. Suh looping signiantly

redued the TCP performane. In this work, we try to avoid suh looping by imple-

menting previous hop memory tehnique that forbids forwarding pakets bak to the

node that reently forwarded.

Further, the projet work was arried out only using one TCP onnetion on a

network. In this work, we examine the behavior of the CEAS system during dierent

network events and measure the TCPperformane. Wealsoexamine the performane

of multipleTCP soures using two dierent variants of TCP.

1.3 Researh Methods

In ordertoevaluatethe performane of TCPonCEAS system, the followingmain

questions are investigated.

1. How fast the CEAS system updates and stabilizes in response to the network

dynamisand how they aet the TCP performane?

2. Does the use of multipathroutingauses redution in the TCP performane?

3. How wellthe system handlesTCP data tra during ongestion?

4. Does the system re-routes the TCP tra in response to the ongestion or they

are ontinuously forwarded along the ongested path?

5. HowdoestheCEAS handlesmultipleTCPtrawhentheyshareommonlinks?

6. Does the CEAS system divert multipleTCP tra onseparate pathor the TCP

onnetionsstruggle touse the best path?

7. Does the TCP performane onCEAS isbetterthan on the LSRPand DVR?

Eah of the questions is investigated using simulations. The simulations are arried

out ina simple network. The simple network helps usunderstand and investigate the

questions in aneasier way. Further,it is easier to visuallyexamine the simulations to

gain more insight.

All the simulationsin this work have been arried out using Network Simulator 2

(NS2) 2

. NS2isawidelyuseddisreteeventsimulatorthatprovidesareproduibleand

2

FormoreinformationonNS2,seehttp://www.isi.edu/nsnam/ns

ontrollable environmentfor the evaluationof the Internetprotools. Allthe previous

studies related to the CEAS have been based on the modules developed by Helvik

and Wittner [16℄. However, for this work a newer version of the CEAS module has

been provided by the department oftelematis, NTNU. Thisnew version isdeveloped

on top of the multi- * network extension by Paquereau and Helvik [ 26, 27℄ . The

modules are written in C ++ and some modiations have been made aording to

our requirements. 15 independent repliations have been simulated for eah senario,

the results have been then synhronized to alulate 95 perent ondene interval.

Chapter 3desribesthe simulationmodelin detailas wellas the modiations made.

The resultsrelatedtothe TCPperformane aswellasCEAS behaviorarestudied.

The results related to CEAS behavior during dierent network events are used to

understand the behavior of the TCP. If TCP performane shows unexpeted results,

theCEASbehavioristhenstudiedtondlogialexplanations. Further,thesimulations

are visually examinedto gain more insight duringsuh unexpeted results. The TCP

performaneresultsarethenompared withtheresultsobtainedfromLSRPand DVR

under similar ongurations.

Later, two ase studies are made to measure the performane of TCP in omplex

CEAS networks. Eahasestudyisbasedondierenttopologies. Theresultsfromour

basi studies are used as referenes toreason out the behaviorof TCP in the omplex

networks.

1.4 Struture of thesis

In this hapter, we briey outlined the researh area and our approah. The rest

of the thesis isorganized as follows.

Chapter 2 provides the neessary bakground on stohasti routing, LSRP and

DVR.ItalsoprovidesbriefoverviewofCEASsystem. Setion2.6,givesabriefoverview

of TCP andthe underlyingongestion ontrolalgorithms. Further,Setion2.7denes

the problemsrelatedtoTCPonstohastinetworks. Finally,inSetion2.8we explain

the ongestionontrolalgorithmused indierentversions of TCP

In Chapter 3, we outline our measurement platform and simulation models. The

modiation made on extension is explained in Setion 3.2. The rest of the setions

denes the implementation, parameters, topologies, network dynamis used in our

study.

In Chapter 4,wemeasure the TCP performane onCEAS system under inuene

ofdierentnetworkevents. Thesetionsareorganizedaordingtothenetworkevents.

Theresultsfromeaheventsare explainedusinggraphs. Theresultsarealsoompared

with the resultsfrom LSRPand DVR.

Chapter 5, presents two ase studies basedon two dierent networks. The studies

inthishaptermainlyfousonobservingthebehavioroftheTCPinomplexnetworks.

TheresultsfromChapter4areusedasreferenestoreasonoutthebehavioroftheTCP

in omplex networks. The hapter is divided into two setions based on the network

topologies; a12 node network and the 58 node topologyfrom the Uninett network.

The main results of this work are summarized in Chapter 6 and the future works

are outlined.

Bakground

2.1 Stohasti Routing

Basially IProutingis aset of protools responsiblefor determiningthe paththat

datafollowsfromitssouretothedestination. Thepathfromasouretoitsdestination

may onsist of series of routers. The IP routing protool helps routers maintain a set

of rules that they refer while forwarding data pakets to the next node towards the

destination [34℄.

The state of art Link State Routing protools suh as OSPF 1

and IS-IS 2

are de-

terministi. Suh routingalgorithmsare ne tuned inorder topre-determine the best

path fromsoure tothe destination. Eah routeralong the pathmaintainsa next-hop

routing table that onsists of the addresses of its neighboring nodes along with the

assoiated path ost. The seletion of the next hop is based on the ost assoiated

with the path towards the destination. Similarly Distane Vetor Routing suh as

RIP 3

uses hop ount asrouting metrito nd the best path between a pair of nodes.

Therefore, the data pakets are always routed through the same path dened by the

routing poliy even though there may exists multiple paths towards the destination

1

OpenShortest PathFirst(OSPF)isanInternet domainroutingbasedon Dijkstra'salgorithm. SeeIETFRFC

2328.

2

Intermediate SystemtoIntermediateSystem(IS-IS)issimilartoOSPFbasedonDijkstra'salgorithm. SeeIETF

RFC1195.

3

RoutingInformationProtool(RIP)isadistane-vetorroutingthatuseshopountasroutingmetri. SeeIETF

RFC1058

[28℄.

However, instohastirouting,theroutingtablesmaintainedbyeahrouteronsist

of possible next node addresses based on a probability distribution. During paket

forwarding eah node randomly selets next node from its routing table irrespetive

of the previous seletions. However, the probability of seleting a partiular node

among other possible nodes is proportional to the quality of the path between them.

In stohasti routing there are no pre-determined path dened by the routing poliy.

Thus, the data pakets do not always followthe same path whih makes this routing

non-deterministi [28, 6℄. However, swarm based routing algorithms use stohasti

optimizationmethodsinordertominimizethetimendingtheoptimizedpath [22,15℄.

2.2 Ant Routing

Aolletionofnumeroussimpleloalinterationsbetweenelementsofself-organizing

system that results in omplex olletive behavior is known as Emergent behavior.

Emergent behaviors are very useful to solve optimization problems [ 11, 18℄. Suh

behavior an be found in nature, for example; a olony of ants sorting eggs without

having ants the knowledge of sorting. In this example the optimization proess is not

entrally ontrolled but in fat the solution is produed by the olletive behavior of

individual elements of the distributed system.

SwarmbasedroutingalgorithmsmakeuseoftheemergentbehaviorofAntssearh-

ing for food. In nature, ants ontinuously forge around in searh of food. They form

a self-organizing system by interating with eah other using a hemial signal alled

pheromones. During foodsearh ants leave behind pheromones ontheir way towards

the food. These pheromones diret other ants towards the food. Paths with the

stronger pheromones are likely to be followed by most of the ants. As time passes

by, the pheromone gradually evaporates, yet the shorter paths tend to have stronger

pheromonesthanthelongerpaths. Thus, theshortest pathismorelikelytobefollowed

by further ants. The resultingshortest pathis the outome of simple loalinteration

[18, 11,7,15℄ .

2.3 Cross Entropy Ant System

The Cross Entropy Ants System (CEAS), purposed by Helvik and Wittner [16℄ ,

forms the basi foundation of this work. The CEAS routing is based on two key

priniples;emergentbehavior andtherossentropy method forstohastioptimization.

InCEAS, emergeneanbeexplainedby thebehaviorofnumerous ant-likemobile

agentsthatows randomlythroughoutthenetworkinsearhofpossiblepathsbetween

two nodes. When a path from a soure to its destination is found the ants retreats

bak followingthe samepath aswellas updatingaparameter, denoted aspheromone.

This pheromone is a ruial element in path nding as it guides other ants traveling

towardsthedestination. Eahnodesalongthepathmaintainsatablethatinorporates

addresses of its neighboring nodes along with their orresponding pheromone values

towards them [16, 15℄.

The CEAS uses a Cross Entropy (CE) method introdued by Rubinstein [30℄ to

update pheromones. The CE method has been widely used as powerful tehnique for

solving ombinatorialoptimizationproblems. The CE methoduses adaptivesampling

tehnique to probabilistially onverge random sequene of solutions to an optimal

solution. Thus, it is very helpful in nding optimal solutions in ase of rare events

where the probability of ourring an event is very low. For example, on a large

network, the probability of nding an optimal path between two nodes by searhing

randomly throughout the network is very low. Hene the use of adaptive sampling

helps gradually and iteratively minimize the ross-entropy between randomly found

paths and onverge various found paths into an optimized path on the basis of the

path ost [30, 16, 15℄.

In CEAS system, the soure node is responsible for generating simple agents de-

noted as ants. All ants are initiallygenerated as forward ants that explore the entire

network searhing paths towards the destination. The forward ants are of two types:

explorer ants and normal ants. At eah intermediate node, the explorer ants hoose

the next node randomly. These explorer ants are responsible for nding new paths.

Unlike explorer ants, normal ants hoose the next node aording to the probability

distribution i.e. the probability p

ij,t

for a normalant at visitt innode i, isalulated

aording the random proportional rule 2.1. Eah node maintains a database known

as messagedatabase tostore the outome of the randomproportionalrule [15℄.

P _ij,t = τ ij,t .I(j / ∈ U) P

(i,l) ∈ / E,l / ∈ U τ il,t

(2.1)

where,

τ ij,t

^{isthepheromonevalueoflink}

(i, j) ∈ E

^atupdate

t

^,

U

^{isalistofforbidden}

nodes, and

E

^{isthe set of alllinks.}

When a forward ant reahes its destination, a path ost, denoted by

L (ω)

^{, is}

alulated as in 2.2. The path ost

L (ω)

^{isthe summation of allthe linkosts along}

the path that antfollowed. This path ost may varywith tra loads and time.

L (ω) = X

∀ (i,j) ∈ ω

L ((i, j ))

^(2.2)

where,

L((i, j ))

^{is alink ost between nodes}

i

^and

j

^.

In additiontothis, aontrolvariable,knowastemperature, isalsoupdated. Over

time thetemperaturevariabledereases butasmoreantsarriveatthe destination,the

temperaturevariablestabilizes.

Bakwardantsthentravelbakfromthe destinationnodetothesourenodealong

the same pathbut inreverse order. At eah node along the path these bakward ants

update the pheromone values. The pheromone values are updated aording to the

path ost and the temperature variable. Thus, over time the pheromone values along

the better pathget stronger therebyinreasing the probabilityofnormalants passing

through the path (from equation 2.1). As more ants pass through the better paths,

the routingtable onverges tond an optimalpath amongmultiplepaths [ 16, 15℄.

2.4 Link State Routing (OSPF)

Open Shortest Path First (OSPF) is a link-state routing protool and is a family

of Interior Gateway Protool(IGP). As a link-staterouting protool, routersdisover

theirneighborsandtheirstatesbyexhanginglink-statemessagesknown asLinkState

Advertisements. Initially LSA messages are ooded throughout the network (usually

Autonomous System 4

) todisover neighboring nodes. One the initializationphase is

ompletedtheLSAmessagesareexhangedperiodiallyorinresponsetoanyhangein

the topology. LSAmessageshelpsnodesmaintainalinkstatedatabaseregardingtheir

loaland neighbor's information,topologialinformationandthe ost assoiatedwith

eah linktowards the neighbors. UponreeivinganLSA messageeahnode ompares

the messagewiththe entryintheirdatabaseand updatesthemprovided thatthe LSA

message is newer. Thus, every node within the Autonomous System has information

about the entire network topology whih they use to alulate end-to-end path ost

using ShortestPathFirstorDijkstra'salgorithm. Duringrouting,thenext node along

the path isthe one with the lowest path ost towards the destination [23,34℄.

The omplete knowledge of the entire network topology allows the OSPF nodes

to easily alulate the shortest path from a soure node to its destination node. In

addition to this, it also allows the system to quikly respond to any hange in the

topologies suh aslink failuresand linkre-establishments. However, linkstate routing

protools arenot salable;inreasingthe numberofnodes inthenetworkinreases the

volumeofthe LSAmessages exhangeaswellasinreases thetimerequire toalulate

entire end-to-end path. Additionally, the protool is not suitable in the environment

where the frequeny of link failures is very high. At suh high rate of link failures the

amountofLSAmessageexhangetoupdatethesysteminreasesandalsotheoverhead

of realulating the entire end-to-end path ost inreases. A study by Heegaard and

Wittner [ 14℄ shows how stohasti routing CEAS outperforms link state routing in

ase of frequenttransient failures in the network.

4

AutonomousSystem(AS)isaolletionofonnetedrouterswithinaontrolofommonnetworkadministrator.

SeeIETFRFC1930

2.5 Distane Vetor Routing (RIP)

RoutingInformationProtool(RIP)is one ofthe IGP protools that arebased on

Distane Vetor Routingalgorithm. Similartolink state routingRIP isused within a

singleAutonomousSystem. AlsoRIPnodessendrouting-updatemessagesperiodially

or in response to any hange in the topology. Upon reeiving a new update message

eah node updates its routing table to reet the hanges. However, RIP nodes only

maintain information regarding the best path towards the destination. Further, RIP

uses hop ount as routing metri to alulate the distane between a soure and a

destination node. In order to prevent routing loops in the network, RIP denes the

maximumnumberofhopsinapathtobe15whihinfatlimitsthesizeofthenetwork.

Any destination node beyond this limitis onsidered unreahable.

2.6 TCP

TheTransmissionControlProtool(TCP)iswidelyusedonnetion-orientedTrans-

portLayerprotool. TCPensure end-to-end reliableonnetionover the Internet. By

onnetionorienteditmeansthataonnetionmustbeestablished between twonodes

before transferring data. Further, TCP inludes error detetion and error orretion

mehanism inorder toprovide the end-to-end reliability.

TCP transfer data in a form of segment whih inludes both the TCP header

and the payload (user data). The segment size may vary aording to the payload.

However, it should not exeed the Maximum Segment Size (MSS) of the onnetion.

EahTCPsegmentisassignedauniquesequenenumber. Whenadestinationreeives

a segment it sends bak an aknowledgment (ACK) for the reeived segment. The

aknowledgment also onsists of the next sequene number that the reeiver expets

to reeive [29℄.

2.6.1 TCP ongestion ontrol

TCPuses feedbakontrolalgorithm,additiveinreaseandmultipliativederease

(AIMD) algorithm, to avoid ongestion in the network. Congestion builds up when

the tra load exeeds beyond the network apaity. The idea is to inrease the

transmission rate until loss ours. The transmission rate is governed by two entities

Congestion window (wnd) and reeiver's advertised window (rwnd). wnd limitsthe

maximum amount of data that sender an transmit while rwnd limitsthe maximum

amount of data the reeiver is willing to reeive. In general, the transmission rate

should not exeed the minimum of wnd and rwnd [2℄.

For every segment transmitted, a timer known as retransmissiontime-out (RTO)

is set. When this timerexpires, TCP assumesthat the segment is lost. In additionto

this,TCPreeivergeneratesDUPACKforeveryout-of-ordersegmentreeived. Beyond

ertain threshold, TCP interprets ontinuous DUPACKs as paket loss.

When a segment islost, TCP ongestion ontrol mehanism interprets the loss as

a resultof networkongestion [17℄,thereforeit responds by dereasing the ongestion

window. The derease in ongestion window size depends on the TCP variation yet

mostoftheTCPvariantsusethefollowinginter-winedalgorithmstohandleongestion;

slow-start,ongestion avoidane, fast retransmit and fast reovery.

2.6.1.1 Slow start / ongestion avoidane

Slow-start begins when a TCP onnetion is established. Initially a ongestion

window isset to not more than twie the maximum segment size (SMSS) that sender

an transmit.

cwnd ≤ 2 ∗ SMSS bytes

^(2.3)

For eah ACK reeived, the wnd value is inreased by one SMSS until itexeeds

the slow-start threshold (ssthresh) or ongestion ours. After this the TCP enters

ongestion avoidane phase. During this phase, wnd is inreased by one full sized

segment for eah round-trip time (RTT). In general, wnd is inreased as in equation

2.4. Thus, wndgrows exponentiallyduringslow-startphasebutgrows linearlyduring

ongestion avoidane.

Figure 2.1: TCPongestionontrolmehanism.

cwnd+ = SMSS ∗ SMSS/cwnd

^(2.4)

When the retransmission timer RTO expires, TCP interprets this as ongestion.

Then,thelostsegmentisretransmittedandthessthreshissettothehalfoftheurrent

wnd value. Thereafter, TCP re-enters slow start phase with wnd value set to one

full sized segment [17℄.

2.6.1.2 Fast Retransmit / Fast Reovery

For eah out-of-order segment reeived, a dupliate aknowledgment (DUPACK)

is sent by the reeiver indiatingsegment(s) missing. However, as any of the missing

segments is reeived, the reeiver should immediatelyaknowledgeindiatingthat the

missing segment has been reeived.

TCP sender waits for 3 onjugative DUPACK before retransmitting the rst un-

aknowledged segment. Thereafter, ssthresh isset to the half of wnd, then the wnd

is set asin equation2.5 and Fastreovery phase is ativated.

cwnd = ssthresh + 3 ∗ SMSS

^(2.5)

ForeahadditionalDUPACKreeived,wndisinrementedbyoneSMSStoreet

that anadditionalsegment has been sent. A new segment may alsobetransmitted if

permittedby the new wnd and the reeiver's advertised window. When a next ACK

is reeived, wnd is set tossthresh. This indiates that allthe missing segments have

been reeived. Figure2.1 illustratesthe whole proedure [17℄ .

2.7 Eet of Stohasti Routing on TCP

Instohastirouting,thenextnodealongthepathisseletedrandomlyirrespetive

of their previous seletions. Therefore, data pakets from a same TCP session may

followdierent pathsto the destination. This randombehavior has negative eet on

the TCP performane. For example; assume

p

^and

p ^′

^{to be two dierent paths that}

existbetweentwonodes

A

^and

B

^{,wherethepath}

p ^′

^haslongerpropagationdelay than the path

p

^{. Also assume that a TCP onnetion is} established between the nodes. If a TCP paket generated attime

t

^{takes the route through the path}

p ^′

^{and next TCP}

paketgeneratedattime

t + x

^{takestheroutethrough thepath}

p

^{then thelaterpaket}

reahesthedestinationbeforetheformerpaket. Thus,pakets followingdierentpath

auses re-orderingof the pakets. Although theout of orderpaketdeliveryis notdue

tothepaketloss,beyondertainthresholdTCPtreatssuhoutoforderpaketreeive

as paket lossand ativates the ongestion ontrol mehanism [17℄.

In our example the out-of-order paket delivery is neither due to the paket loss

nor due to the ongestion yet TCP enters the ongestion ontrol mehanism ausing

redue in the TCP performane. As explained in Setion 2.6.1, TCP respond paket

lossby retransmittingthe lostpaketsand reduingthe windowsizeinordertoredue

the overload onthe network. This unneessary Fastretransmit/ Fastreovery wastes

available bandwidth aswell asredues Datatransmission rate [1,31, 24℄.

Generally, a TCP sender waits for 3 DUPACKs before retransmitting the rst

unaknowledged paket. After this, TCP enters the fast reovery phase. In order to

avoidTCP fromentering Fastretransmissionand Fastreovery phasethe propagation

delay onthe longerpath

p ^′

^{shouldbeless thanthetime requiredbynext 3onjugative}

paketstoreahthedestination. Let

x

^{betheintervalofpaket}generation,

d

^and

d ^′

^be

the total propagationtimefor apaket toreah from

A

^to

B

^via

p

^and

p ^′

respetively. Assume a paket generated at time

t

^{takesthe longerpath}

p ^′

^{and other3 onjugative}

paketsgenerated at

t +x

^,

t + 2x

^and

t + 3x

^{alltakeshorterpath}

p

^{. Therefore,toavoid}

retransmissionthepaketviapath

p ^′

^shouldreahdestination

B

^beforetime

t + 3x+ d

^.

i.e.

t + d ^′ < t + 3x + d or

d ^′ − d < 3x

^(2.6)

Let

t pab

^and

t p ^′ ab

^{bethe totaltime,exludingqueuing delaysand routerproessing}

delays, requiredforapakettotravelfromAtoB via

p

^and

p ^′

respetively. Assuming

t q

^and

t r

^{be the queuing delay and the proessing time for a router} respetively. Also assumingthatthepath

p

^onsistof

n

^{numbersofroutersand}

p ^′

^onsistof

n +k

^numbers

of routers then fromEquation 2.6;

t _p ^′ _ab + (n + k)(t _r + t _q ) − {t _pab + n(t _r + t _q )} < 3x, or

t p ^′ ab − t pab < 3x − k(t r + t q )

^(2.7)

Thepaketgenerationinterval,

x

^isinverselyproportionaltotheDatatransmissionrate but diretly proportionaltothe paket size. Further,

t p ^′ ab

^and

t pab

^isalsoproportional to the paket size. Therefore, for a path p' with longer delay we an avoid spurious

retransmission by reduing the Data transmission rate and inreasing the paket size.

However, the Maximum Transmission Unitavailablefor Ethernet frameis 1500bytes.

Further,

k

^{in Equation 2.7 indiates the number of additional routers in the longer}

path

p ^′

^{whih refers that the delay dierene dereases as we inrease the number of}

additionalrouters in the longerpath

p ^′

^.

Inadditiontothis,astudybyBlantonandAllman [4℄listsfurthernegativeeets

of paket reordering

•

^{TCP's standard ongestion ontrol algorithms prohibits to transmit any paket}

when a DUPACK is reeived until fast retransmit is triggered. However TCP

stores permission to send new data and if an ACK overing new data arrives

beforethe fastretransmit is triggered then the burst of data issent onthis ACK

willbe larger than if reordering had not ourred.

•

^{TCP reordering auses RTT sampling ambiguous; Generally RTT is estimated}

using a timer that starts just before a given segment S is transmitted and then

stopped as the ACK overing the segment arrives. During retransmission, the

sender an not make sure whether the ACK overing the segment is in response

of the rst transmission of the segment or inresponse tothe retransmission.

2.8 TCP variants

TCP Renoiswidely usedTCP protoolontheInternet. Ituses ongestionontrol

mehanism desribed in Setion 2.6.1. However, fast reover used in Reno does not

reovereiently when there are multiplepaket losses in asingle ight [2℄. Inorder

to deal with multiple paket losses, NewReno [9℄ isdesigned with modiation inthe

original FastRetransmit and Fast Reovery algorithm.

NewReno reovers multiple losses one paket per round trip time using partial

aknowledgments onept. During multiple paket losses, the rst non-dupliate a-

knowledgment reeived does not neessarily indiate that all the pakets transmitted

prior to the Fast retransmit have been suessfully reeived. However, Reno leaves

FastReovery phase assoonas it reeives rst non-dupliateaknowledgment. Thus,

inase of multiplepaketlosses, the additionalDUPACKsreeived afterthe rstnon-

dupliate ACK auses Reno to enter another yle of the Fast Retransmit and Fast

reover phase with further derease if wnd and ssthresh. Unlike Reno, NewReno re-

mains in the FastReovery phase retransmittingone paket per RTT until every lost

pakethave been retransmitted and aknowledged.

During transmission, NewReno saves the highest sequene number that has been

transmitted. When a paket loss is indiated by 3 ontinuous DUPACK, it performs

Fast Retransmission and Fast Reovery as usual. Reno exits reovery phase as soon

as a non-dupliate ACK arrives however, NewReno performs additional veriation

to onrm that the ACK atually overs the highest sequene number stored. If the

veriation fails, it assumes the ACK as partial ACK and retransmits the rst una-

knowledged paket.

The major drawbak of NewReno is that it annot predit multiple paket losses

until it veries the ACK against the highest sequene number stored. Thus, this may

take substantial amount of time to reover from a series of loss depending on the

numberof pakets lostand the size of RTT [9℄.

In general,anACK only onrms that allthe pakets up tothe numberindiated

bythatACKhasbeensuessfullyreeivedbutdoesnotprovideanyinformationabout

further reeived pakets. In other word, TCP does not send ACK for those pakets

that are reeived beyond the one it expets [ 2℄.

TCP SeletiveAknowledgment (SACK) [21℄is speiallydesigned tohandle mul-

tiple paket losses orretly. TCP SACK implementation uses the onventional on-

gestion ontrol algorithm as used by TCP Reno. Similarly, the Fast Retransmit and

Fast Reovery phase in SACK implementation is triggered after reeiving 3 ontinu-

ous DUPACK.The maindierenebetween the two implementationsistheir behavior

during multiple paket losses ina single ight.

An ACK with SACK option is sent by reeiver informing the sender about the

arrivalofnon-ontiguoussegments. TheSACKoptionontainsalistofthe ontiguous

data bloks reeived and queued at the reeiver. Two 32bitunsigned integer are used

to indiate the starting and the ending of eah bloks. In general, a 40 byte ACK

an inlude maximum of 3 SACK bloks. The SACK option must always provide

the information about the most reently reeived segment to inform sender about

the urrently missing segments. When missing segments are reeived they must be

aknowledged immediately. In this way, SACK method helps to inform the sender

about the orretly reeived pakets as well as the missing pakets. The reeiver uses

SACK option as referene during retransmission to orretly retransmit only those

segmentsthat has been reported missing [ 21℄.

Simulation Module

We used simulations toompare the performane of TCP over CEAS, LSRP and

DVR routing protools. We arried out all our simulations using Network Simulator

2 (NS2) 1

. NS2 is a disreteevent simulatorwidely used for researh of IP network on

the paket level.

3.1 Simulator Basis

NS2 simulator is a widely used tool for evaluation of Internet Protools whih

is based on two languages; Objet oriented C++ lasses and OTl 2

. The ompiled

C++ lasses ating as the kernel of the simulator holds the neessary details and the

operationsofdierentprotools. Ontheotherhand,theOTlatsastheuserinterfae

allowinguser todenenetwork topologies,speify protools and appliations thatone

wish to simulate. ThusNS2 provides a reproduible and ontrollableenvironment for

theevaluationoftheimplementedprotools. ThestandarddistributionofNS2inludes

allthe neessary support forthe LinkStateRouting Protooland theDistane Vetor

Routing.

All previousstudies regarding CEAS were based onthe NS2module developed by

1

FormoreinformationonNS2,seehttp://www.isi.edu/nsnam/ns

2

OTl, short for MIT Objet Tl, is an extension to Tl/Tk for objet-oriented programming. (http://otl-

tll.soureforge.net/otl/)

Helvik and Wittner [16℄. However, for this work we reeived a new version of CEAS

modulefromthedepartmentoftelematis,NTNU.ThisnewCEASmoduleisdesigned

on top of the NS2 extension that supports multi-* networks developed by Paquereau

et al. [27, 26℄. The multi-* network extension provides better support for wireless

and mobile networks. This extension enables nodes to support multiple interfaes of

dierenttypes. Suhmultipleinterfaesallowthe nodes toommuniateovermultiple

hannelat the same time. Allnew features are added ina form of modules making it

easier toenableand disable suh featuresby enablingand disablingthe modules [26℄.

TypiallyanodeinNS2onsistsoftwoTlobjets: anaddresslassierandaport

lassier. These lassiersare responsiblefordistributinginomingpakets either toa

orresponding agent ortoan outgoinglink [8℄. The extensionprovided by Paquereau

et al. [ 26, 27℄ adds two new objets; NetworkLayerManager and NetworkLayerUnit.

TheNetworkLayerUnit onsistsofaForwardingUnitand aRoutingUnitwhihhandles

the data pakets and the routing pakets respetively The multi-* network extension

is briey explained inAppendix A.

3.2 CEAS Extension Modiation

The newCEAS extensionthatwe reeived for thiswork wasstillunderdeveloping

proess. It laked support for self-tuned refresh rates [13℄, also the ForwardingUnit

module for CEAS had not been implemented and the Link ost alulation ignored

the tra loadson thepath. However, featureslikeelite-seletion,routing-loops,tem-

perature approximation and pheromone approximation were implemented as modules

making it easier toongure through OTl sript.

Atthetimewebeginourwork,nostudiesrelatedtodata pakets hadbeen arried

out with the new CEAS extension. Moreover, the inomplete ForwardingUnit made

our study diult as the unit is responsible for handling data pakets. Further, the

tra loads onthe linkhad no eet onthe linkost whih madethe system diult

to handle load balaning and re-routing during ongestion. So, before proeeding to

the studies our rst objetive is to implement a working ForwardingUnit module and

to adjust Link ost alulation.

The new CEAS extensionis divided into two modules;ommon moduleand plain

module. The ommon module ats as the ore of the CEAS system. It provides the

basi properties and funtionalities of the system. It also denes the premises of the

system. The plain module is a sublass of the ommon CEAS module whih denes

and expands the funtionalities of the system.

3.2.1 CEAS ForwardingUnit Implementation

The CEAS ForwardingUnitis aninheritedlass ofthe ForwardingUnit(3.1). This

unit handles alldata pakets that pass through the CEAS NetworkLayerUnit. Allthe

pakets that are destined tothe node are passed upwards tothe orresponding agent.

Likewise, the pakets that are in transit are either forwarded to a neighboring node

based onthe pheromonelevelassoiatedwith the orrespondingpathordroppedif no

neighbornode exist. The seletionof next neighbornode alongthe pathismadeusing

stohastisamplingwithreplaementmethod(Roulettewheelmethod) [3℄amongthe

neighboring nodes taking assoiated pheromone values as the parameter of seletion.

(See Appendix B.1 for detail.)

3.2.2 Cost Path Modiation

A path ost

L(ω)

^{isalulated using the Equation 2.2, whih isthe sum of allthe}

link ostsalong thepath. The linkost ismeasured usingshort termaverage delay on

the link. Theaveragedelayhangesaordingtothetraloadonthe link. Therefore

the alulation of end-to-end delay asthe path ost reets the quality of the path at

the given time.

The CEAS extension that we reeived for our work however did not aount any

tra load on a path during the path ost alulation. Thus, the path ost only

depends on the transitiondelay onthe linksbut not onthe quality of the path.

In order to ahieve the variable path ost that hanges with respet to the tra

load weaddedatimestamp oneahantatthe timeoftheirreation. Thistime stamp

enables us to measure the atual end-to-end delay on the path that the ant traveled.

We used this informationduring the path ost alulation.

3.2.3 Reord Single Hop Route Address Implementation

In our previous work [33℄, we found that large number of pakets are lostdue to

looping when there is link failures. Suh loopingsare found inthis work as well. (see

Setion 4.3 for detail.) Toavoid suh loopings weintroduea tehnique that prevents

forwarding pakets bak to the node that reently forwarded them. To implement

this we use prev_hop() method of ommon paket header to retrieve the address of

the reently forwarded node. We then remove the node from the list of neighboring

nodes sothat the next node seleted wouldnot be theone that reentlyforwardedthe

paket. However, in onditions where there remain no neighboring node other than

the previously forwarded node the paket wouldhave tobeultimatelydropped by the

routers. Thus, insuh onditions weallowforwardingthe paketbak tothe previous

node.

3.3 Prodution

All the simulations in this report related to the CEAS system are run with 15

repliationspersenariosusingdierentseedsfortherandomnumbergenerator. Other

simulations related to the Link State Routing and the Distane Vetor Routing are

arried out one per senario. The simulation output from all the repliations are

synhronized and postproessed usingthe AWK 3

programminglanguage. The graphs

from the simulationresults have been plotted using gnuplot 4

.

3

AWKisageneralpurposeprogramminglanguagedesignedforproessingtext-baseddata

4

Gnuplotisaversatileommand-linedriveninterativeutilityforgeneratingplotsofdataandfuntions.

3.4 Parameters

The input parameters to the simulator are given using the TCL user sript. The

parameters used for CEAS system are listed in Table 3.1. Similarly the default pa-

rameters usedforLinkStateroutingprotoolandDistane vetor routingprotoolare

listed in Table 3.2and Table 3.3.

The elite seletion wasintroduedby [12℄toreduethe overhead ofthe bakward

ants arrying insigniant updates. With elite seletion only those ants following the

pathwiththebestostvaluessofararereturnedtoupdatepheromone. Duringforward

searh explorer ants selet next node randomly. Exluding the explorer ants update

from the elite seletion allows the explorer ants to return bak. While returning, the

explorerantsupdatepheromonelevelalongtheirway. Inasmallnetworklike4.1where

there are onlyfew paths availableand the dierenes between the path osts are very

small, suhupdates would inrease the pheromone levelalong the alternativepaths as

well. Although allowingthe explorer antsto returnbak helps system reats faster to

network dynamis, the inrease in the probability of seleting alternative path auses

reordering of the pakets. Thus in this study,we use elite seletiononall ants.

During forwardsearhantslistalltheaddresses ofthe nodesthatthey pass by. At

the destination, thelistisanalyzed toremoveyli pathsthat the antshave traveled.

Sine our path ost alulationdepends onthe entire end-to-end delay, removingsuh

yli paths doesnot redue the delay experiened by the ants along the yli paths.

The ants following the yli path experiene longer end-to-end delay than those

that travel straight. Suppose after removing the yli paths both the paths beome

idential then this might reate an ambiguity during the path ost alulation. How-

ever, this is not the ase in subpath method introdued by Kjeldsen [ 19℄, where the

ants notonlystores the addressesof the nodesbut alsoreordeahlinkost alongthe

path. At the destination, the redution of the yli path also redues the link ost

around the yli path.

Parameter Desription

Seed 179324 +timid(for eah repliation timid

is inremented by 1)

SimulationTime Simulation time varies aording to the

senarios

InitializationPhase 50 seonds

InitializationPhase antrate 100 antsperseond (Allants are explorer

in this phase)

Ant-rate normal 1 to 20ants perseonds

Ant-rate explorer 10 %of normal antrate

Proessing delay 0 (The total delay isspeied for eah

link in the topology)

Beta

(β)

^0.98 (Evaporation,for detail see [16℄) Rho

(ρ)

^{0.01 (Searhfous, for detail see [16℄)}

EliteSeletion All Ants

Cyle treatment Allowyles

Table3.1: CEASparameters

Parameter Desription

preferene 120

advertInterval 1800 seonds (Periodiroute update

interval)

Spf waittime 0.01+0.250 (Shortest path rst waittime)

Table 3.2: LSRPparameters

Parameter Desription

preferene 120

advertInterval 2 seonds (Periodiroute update interval)

INFINITY 32 (todetermine the validity of route, see

NS2 manualfor detail)

Table 3.3: DVR parameters

3.5 Topologies

Three dierent topologies are used in our studies. A simple eleven node network

as shown in Figure 4.1 is used to understand the behavior of CEAS during dierent

network events and to study its orresponding eet on the TCP performane. This

elevennodenetworkishoseninordertohaveasimplestruture inthetopologywhih

is easier to study as well as easier to visually examine the simulations. Further, we

haveusedidentialbandwidthof100Mbps andtransmissiondelay of1milli-seondon

eah links to have a regular struture on the topology. However, in a partiular ase

we varied bandwidth on a link whih is explained later. We use the results from this

network asa referene to understand and analyze the behavior of TCP under various

network onditions in more omplexnetworks.

The remainingtwo topologiesare used asase studies;a twelvenode network and

the 58node topologyextrated fromthe Uninett 5

network. The twelvenode network,

asshowninFigure5.1, ishosentohavemoreomplexnetworkthantheoneweuse for

our basistudies. Weintroduedvariouslevelsofbakgroundtrasandmultiplelink

failures to analyze its eet on TCP performane. Finally, we used 58 node Uninett

network topology as depited in Figure 5.12. This topology is hosen to provide a

realistisetting forour study. The routersinallofour topologiesuse maximumqueue

size of 60segments and a drop-tailqueuing strategy.

3.6 Network Dynamis

NS2 providesfuntionality tosimulate network dynamislikelink failures. In this

work,we study the system using multiplelinkfailures as wellaswith multiple levelof

bakgroundtra. Wehaveategorizedlinkfailures intotwotypesonthebasis ofthe

link failures and their re-establishment time. The rst types of failures that we all

steady link failures takes longer time to re-establish. On the other hand, the seond

types of link failures that we all transient linkfailures takes very short time, usually

5

www.uninett.no

less than a seond, to re-establish. Further, we introdue suh transient link failures

for ertain time interval to exhibit apping or unstable behavior of the link. These

transient links are used inour ase studies.

A link ost is alulated onthe basis of an average delay onalink. The delays on

eahlinkarespeiedonthetopologyand remainonstantthroughoutthesimulation.

However, the pathost variesaording tothe tra load alongthe path. Datarates,

Connetion types, paket size et are dened using TCL sripts whih also remain

onstant throughout the simulation.

3.6.1 TCP Connetions

Eah senario is studied using two variants of TCP; TCP Reno and TCP Sak.

TCP Reno is one of the most widely used TCP ongestion avoidane algorithms on

the Internet. However, TCPRenosuers duringmultiplepaketlossesinasameight

of transmission. On the other hand, TCP Sak is better designed to handle multiple

paket losses. In this work we have ompared the results from both the variants. All

of our simulations are onduted using a bulk TCP transfer. Although suh TCP

onnetions are not realisti, it allows us to measure the ideal TCP performane on

the CEAS system.

The TCP souresare reatedusing aConstantBit Rate (CBR)sourethat gener-

atesdataataonstantrate. InallofoursimulationstheTCPdataratesgeneratedare

more than 70% of the link apaity. The TCP soure uses the maximum ongestion

windowup to200 segments. TimetoLive(TTL)valuesforsmallernetworksareset to

10whereas forthe largenetwork theyare set to30. TheTCP Reno reeiveruses TCP

Sink with delayed ACKs and the TCP Sak reeiver uses the sak1 TCP sink with

delayed ACKs. The delayed ACK timeris implemented with 100 msgranularity. The

default allowed maximum DUPACK is 3 as well as the TCP sender uses the default

lok granularity of 60ms for the retransmissiontimer. The TCP paket size used in

our simulations is usually 1500 bytes whih is the Maximum Transmission Unit used

in the Ethernet. However, paket size of 512 bytes and 9000 bytes 6

are also used in

our simulations.

3.6.2 Bakground Tra

Some of our simulationsare onduted under inuene of bakground tras. All

the bakground tra in this study is generated using CBR UDP soure. During

our ase studies we use various levels of bakground tra. Suh bakground tra

is generated using multiple CBR UDP soures. The bakground onnetion pairs are

seleted insuhawaythatatleastoneoftheonnetionsharesaommonlinkwiththe

TCP onnetion when there are no link failures. In order to have suh a shared links

some oftheneighboringnodesofTCP soureanddestinationaswellasthemselvesare

seleted as bakground soures orsinks.

6

Jumbo frames allows paket size up to 9000 bytes

(http://sd.wareonearth.om/~phil/jumbo.html)

Measuring TCP performane on

CEAS system

This hapter presents the simulation studies of the CEAS system under dierent

network dynamis and the orresponding eets on the TCP behavior. The simula-

tions performed inthis setion are approahes tond out the answers tothe researh

questions listed in Setion1.3

All of our simulation studies inthis hapter uses a simple eleven node network as

depited inFigure: 4.1. Wehooseanodeoneithersideof thenetworkasasoureand

adestination sothat therearetwopathsbetween them. Eahsenarioissimulatedfor

both TCP Reno and TCP Sak and the results are ompared. The TCP performane

studies are divided intothe followingsetions:

Setion 4.2, TCP performane on steady network

The time required tostabilize the pheromone levelsalong the available paths and

the number of ants partiipating on this stabilization proess are measured. As well

as the eet of starting TCP onnetion immediatelyafter the initializationphase is

examined.

Setion 4.3, TCP performane during Link Failure

The behavior of the CEAS system during link failure is observed and the time

required to update and re-stabilize the pheromone level along the alternative path is

measured. Inadditiontothis,theeet oflinkfailureonTCPperformane isobserved

and the time required for the TCP to resumeonnetion and regain its full data rate

after the link failureisalso measured.

Setion 4.4, TCP performane during Link Congestion

The behavior of the CEAS system during link ongestion along the best path is

observed. Further, how the system diverts the tra during ongestion is examined.

The performane of TCP during linkongestion isstudiedand the eet of inreasing

the paket size is alsodisussed.

Setion 4.5, TCP performane dierent apaity links

TheCEASsystemonthenetworkwithvaryinglinkapaityisstudied. Thesystem

is examinedusing the lowerapaitylink along the best path toexamine whether the

system selets the alternative path as the best path or ontinues to use the lower

apaity link as the best path. The performane of the TCP under suh network is

also studiedand alsothe eet of inreasing the paketsize isexamined.

Setion 4.4, Multiple TCP onnetions

The performaneofthe TCPwhenthereare morethanoneonnetionsisstudied.

The study isfoused onndingout whetherboththe TCPonnetion strugglestouse

the best path or the system diverts the TCP streams onseparate path.

Setion 4.4, Previous Hop memory tehnique

The improvement onthe TCP performane duringlink failureafter implementing

previous hop memorytehnique is studied.

4.1 Performane Metris

The followingperformane metrisare appliedwhilemeasuringthe performaneof

TCP onCEAS system:

•

^{The best path - The path with the shortest end-to-end delay from the soure}

node to the destination node.

•

^Pheromone Stabilization period - A point in time when the probability of normal ants following the best path is 100 times higher than the other paths in

the network.

•

Re-stabilizationperiod -Apointintimewhenthe systemupdates pheromone leveltoelet newbestpath inresponsetothe networkeventssuhaslinkfailure,

linkEstablishment orongestion.

•

^{TCP data rate - the rate at whih TCP soure transmitsdata.}

•

^{TCP Throughput - The totalamountof TCP data} transferred afterstarting a TCP onnetion overthe entire intervalof the simulation.

4.2 TCP performane on steady-state network

Before measuring the TCP performane in a network with CEAS system, it is

importanttoobservethetimerequiredfortheCEASsystemtostabilizethepheromone

levels along the available paths. One the pheromone level stabilizes the majority of

ants follow through the best path making it the most popular path in the network.

The stabilizationperiod depends onthe numberof the antsin the network. Thus, we

use simulationsat dierent ant rates and ompare the results. Then, we observed the

eet ofstartingTCP onnetionimmediatelyaftertheinitializationphaseusingTCP

data rateastheperformane metri. Wemeasured thetimerequiredforaTCPsoure

to transfer pakets at full data rate. TCP onnetion using both of the TCP variants

is studied.

Senario:

To measure the stabilization periodtwo nodes; node 0 and node 8 are seleted as

a soure and destination nodes. In this simulation only ant tra is generated but

not the data tra. Eliteseletions are made on allants inluding the explorer ants.

Further, yli paths are not removed at the destination. The senario is simulated

for 600 seonds with the rst 50 seonds as the initialization phase, during whih all

antsgenerated are explorerantssearhing the possible paths. The stabilizationperiod

at dierent ant rates are ompared and graphs are plotted with 95perentondene

interval. Throughoutthe simulation,thenetwork remainssteady withnolinkfailures.

In seond phase of this simulation we start the TCP onnetion right after the

initializationphase i.e. at 50 se. andmeasured the time requiredfor the TCPsoure

totransmitdataatthefullrate. Thesenarioissimulatedfor1800 seonds. TheTCP

reeiver uses the Sak1 TCP sink along with delayed ACKs for TCP Sak whereas

simply TCPSink with delayed ACK for TCP Reno. The paket size, data rates and

other TCP parameters are as inthe Table 4.1.

Results and Disussion:

Figure 4.2 shows the Pheromone Stabilization periodsat dierent ant rates. The

timerequiredtostabilizepheromonevaluesdereaseswiththeinreaseintheantrates.

Parameter Values

Data Rate 75Mbps

TTL 10

WindowSize 80

Paket Size 1500 bytes

Table4.1: TCPonguration

Ant Rate Mean Time Approx. Number of Ants

required

(Normal +Explorer) (Normal +Explorer)

1 +0.1 151.2

≈

¹⁶⁶

2 +0.2 73

≈

¹⁶⁰

3 +0.3 49.8

≈

¹⁶⁴

5 +0.5 30.7

≈

¹⁶⁹

10+ 1 14.9

≈

¹⁶⁴

15+ 1.5 9.8

≈

¹⁶²

20+ 2 7.52

≈

¹⁶⁵

Average

≈

¹⁶⁴

Table4.2: PheromoneStabilizationPhasewithEliteSeletiononAllAnts

The Table 4.2 summarizes the stabilization time period as wellas the number of ants

partiipating in the stabilization proess. The number of ants generated during the

initializationphaseisexluded. TheTableshows thatthenumberofantspartiipating

in the stabilizationproess atallant rates isalmost equal. From theseresults, wean

assume that atanant rate of164 ants perseond the system would establishthe best

path inour network immediatelyafterthe initializationphase.

Figure4.3ompares thetime taken by TCP Renoand TCPSak totransmitdata

at full rate i.e. 75 Mb for our senario. The results from both of the TCP variants

at dierent ant rates are ompared. The gure shows similar results to that of the

pheromone stabilization proess; at higher ant rates the time required by both the

variants are shorter. Graphs plotted in the gure also indiate that at all ant rates

the TCP Sak takes shorter time to transmit at full data rate than the TCP Reno.

However, athigher ant rates the time dierenes between the variantsare smaller.

In these simulationswestart the TCP onnetion immediatelyafterthe initializa-

tionphase,atthismomentthepheromonelevelsinthenetworkareyettobestabilized.