linkres@ignore linkmodres@+LinkResourceNextEvent linkmodres linkres linkmodres@+(LinkResourceNextEvent linkmodres)
LinkSent connsegment@+(LinkTransmitTime ())
Figure8: CPN model forthelink
5 Analysis of the Model
Simulation was performed considering one, two and three packet loss situations. For each
situation, the sequence of packets sent by the TCP sender was observed. In addition, the
numberof packets delivered wasobtainedand a performancemeasurewascomputed.
5.1 Behavioural Analysis
ToobservethebehaviourofthetwoTCPversions,wedenedagraphthatshowsthesequence
of packets sent fromtheSender to theReceiver. We have timeonthex-axis, and thepacket
number(mod 60)on the y-axis. A square represents each packet as itarrivesin theswitch.
Packetlosses are represented inthegurebya crossmark.
One Packet Loss
We considerthe situation wherethe packet with sequence number14 is lost. Figures9 and
10 show the sequence of packets sent by the Sender, considering the TCP Reno and TCP
Tahoeversionsrespectively.
IncaseofTCPReno,packets0-13aresentwithoutproblems(14squaremarksinthefour
initialwindowsinFigure9). Duringthisphase,TCPperforms slowstartand thecongestion
windowincreasesexponentiallyfrom1 to15. Packetnumber14is dropped,representedbya
crossmarkinFig.9. Thismeansthatallthepacketsforthefourth windowweresuccessfully
delivered, except packet 14. Thus, the TCPsender receives 7 ack segments and it increases
CWND from 8 to 15. The TCP sender is allowed to send packets 15-28 (fth window in
Figure 9).
0 10 20 30 40 50 60
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
Packet Number (Mod 60)
Time (seconds)
Figure 9: TCPReno- one packet loss
0 10 20 30 40 50 60
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
Packet Number (Mod 60)
Time (seconds)
Figure10: TCPTahoe - one packetloss
33
asking for packet number 14. Packets 15-28 were successfully delivered. Therefore, besides
the rst acknowledgement asking for packet 14, the sender receives 14 additional
acknowl-edgementsforthissame packet(dupACKs).
AfterreceptionofthethirddupACKaskingforpacket14,fastretransmissionisperformed.
At thispoint,SSTHRESHissetto 7(halfof CWND)andCWND issetto 10(half plusK).
Packet 14 is then retransmitted. Since 11 dupACKs were received after retransmission of
packet14,CWND isincreased upto 21.
WhenCWNDisincreasedforthelastsixdupACKs,thesenderisallowedto sendpackets
29-34. When the retransmitted packet is received, the sender exits fast recovery and starts
congestion avoidance withCWND setto 7.
In case of TCP Tahoe, the behaviour is identical to TCP Reno's behaviour until the
reception of the third dupACK for packet 14. Then, the sending TCP Tahoe reduces it
congestion windowto one and retransmitspacket14. When anacknowledgement is received
for theretransmitted packet, CWND is increasedby1 and packets 29 and 30 aresent. The
sendercontinuesinslow startandwhen packet34issent,theslow-startthresholdisreached
and congestion avoidancestarts.
Two Packet Losses
Figures11 and12 showthesequence ofpackets sent forthetwo packetlosssituation
consid-eringTCPReno andTCPTahoe, respectively. Thetwo lostpacketsare14and 28,asshown
bythecross marksinFigures 11and 12.
Theprotocolbehavesexactlythesameasintheonedropsituationuntilpacket28issent.
Since packet28 is also lost, thenumberof duplicateacknowledgements asking forpacket 14
is 13 insteadof 14 fortheone-dropsituation.
Considering the TCP Reno protocol, the sender is able to send packets 29-33. After
receptionofthethirdduplicateacknowledgement,CWND dropsto10andincreasesupto 20
due to the reception of the last 7 duplicateacknowledgements asking for packet 14. When
the retransmitted packet 14 is acknowledged, packet 28 is expected. Since this is the rst
acknowledgement thatasksforpacket28,thesenderisallowedto sendanew packet (packet
34). At thispoint,thesenderexits fastrecovery withCWND of 7.
Sincepacket28isalsolost,thesenderwillreceive6duplicateacknowledgementsaskingfor
packet28. Reception of thethird duplicateacknowledgement triggers a second fast
retrans-mission situation. CWND and SSTHRESHare setto 6and 3respectively. CWND increases
to 9 whenthesenderreceivesthesixth duplicateacknowledgement. Then,thesenderisable
to sendpackets 35 and 36. When the acknowledgement forthe second retransmittedpacket
is received,thesender exitsagain fastrecovery witha congestionwindow ofthree.
In the case of TCP Tahoe protocol, after the reception of the third dupACK for packet
14, CWND is reduced to 1 and packet 14 is retransmitted. The sender then receives an
acknowledgement asking for packet 28 and CWND is increased by one. Packets 28 and 29
are sent and the sender continues in the slow start phase. The congestion avoidance phase
starts when thesendersendspacket40.
0 10 20 30 40 50 60
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
Packet Number (Mod 60)
Time (seconds)
Figure 11: TCPReno- two packet losses
0 10 20 30 40 50 60
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
Packet Number (Mod 60)
Time (seconds)
Figure 12: TCPTahoe -twopacket losses
35
0 10 20 30 40 50 60
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
Packet Number (Mod 60)
Time (seconds)
Figure13: TCP Reno- threepacket losses
0 10 20 30 40 50 60
0 0.5 1 1.5 2 2.5 3 3.5 4 4.5 5
Packet Number (Mod 60)
Time (seconds)
Figure 14: TCPTahoe - three packet losses
In addition to loss of packets 14 and 28, now also packet 26 is lost. Figure 13 shows the
sequenceof packets sent bytheTCP Reno senderforthe three packet losssituation. Figure
14showsthe sequenceof packets fortheTCPTahoeprotocol.
In case of TCP Reno, packets 0-13 are sent without problems. When packets 15-28 are
sent, the TCP sender receives 12 dupACKs asking for packet 14. After retransmission of
packet14, CWND decreasesto 10 and reaches 19 due to dupACKs. When the TCPsender
receivesanacknowledgementaskingforpacket26,itexitsfastrecovery. Atthispoint,CWND
is setto 7. However, sincepacket26 islost, after receivingthree dupACKs askingforpacket
26,the TCPsender performs a second fast retransmission. SSTHRESHis reducedto 3 and
CWND is set to 6. The three next dupACKs increase CWND to 9. After receiving an
acknowledgement asking forpacket 28, the senderexits fast recovery and CWND is reduced
to 3.
Since CWND is 3 and three packets still unacknowledged, the sender is stalled and is
unabletoperformfastretransmission. ThisisreectedinFig.13astheabsenceofsquaresin
the period from 1.5seconds to about3 seconds. Thus, thesenderwaitsfora retransmission
timeout. When timeout occurs,packet28 is retransmittedand theTCPsender sets CWND
to 1, and slow start is then performed. The congestion window CWND now increases
ex-ponentially to a value of 3, after which congestion avoidance is entered sinceSSTHRESH is
3.
TCP Tahoe acts as in the two previous cases to cope with the loss of packet 14. When
the sender receives an acknowledgement asking for packet 26, theCWND is increased to 2.
Insome situations,TCPTahoesendermayforgetthefactthatsomepackets werepreviously
sent. This problem is likely to appear when multiple packet losses occur in one window of
packets. So, packets 26 and 27 are sent for the second time. Two acknowledgements for
packet 28 are received. However the congestion window is increased to 3 because only one
of the two acknowledgements represents the acknowledgement for a new data. The sender
remains inthe slow startphase and switchesto congestion avoidancephase when packet 37
is sent.
5.2 Performance Analysis
Dierent kind of performance measures can be dened and analysed by simulation of the
CPN TCP model. In this section we consider eÆciency, which is dened as the number of
packets delivered to thereceiver dividedby the maximum number of packets that could be
delivered (when there is no loss of packets). It means that eÆciency is 1 when there is no
packetdrop.
In the simulationswe have assumed a segment size of 1000 bytesand a TCP maximum
receiverwindowsizeof 32Kbytes. Allsimulationsruns correspond to5 secondsofreal time.
We observed the eÆciency in both TCP versionsfor the situations of packet losses
pre-sentedintheprevioussection. Table1 summarises theresults.
The results indicate that the TCP Tahoe keeps almost the same eÆciency for the three
situations. If we analyse the TCP Tahoe behaviour presented in the last section, we can
observe that TCP Tahoe recovers from the packet losses in the three situations performing
one slowstart.
TCP Reno presents greater eÆciency when it faces the one packet loss situation. This
37
Situation TCPReno TCPTahoe
1packet loss 0.59 0.47
2packet losses 0.38 0.47
3packet losses 0.14 0.45
Table1: EÆciencyResults
occurs because Reno uses fast recovery after retransmission of the loss packet, allowing a
smoothly recover from the packet loss. For the two packet losses situation, TCP Reno was
forced to perform two successive fast retransmit and fast recovery procedures. Thus, the
congestion window was reduced in half twice. Since the reductions were performed in two
successive round-trip times, the performance of TCP connection was degraded. TCP Reno
presents vary poor performance(eÆciency of 14%) for the three packet losses situation. In
this case, TCP Reno waited for a retransmit timeout to recover from a packet loss and a
considerably performancereductionwas observed.
The experiments showed that TCP Reno performs nicelyin the case of a simple packet
drop. Fortwoormore packet losses theperformanceof TCPReno is signicantlydegraded.
6 Conclusion
WehavepresentedatimedhierarchicalCPNmodelforbehaviouralandperformanceanalysis
ofTCPprotocols. ThemodelconsidersthefourmostprevalentTCPalgorithmsforcongestion
control. We have used theterm generic to emphasise that withminor changes itis possible
to adapt themodel fordierentTCP versions.
Simulationbased performanceanalysisfor theTCPReno and TCPTahoeprotocols was
alsopresentedfocusingoneÆciencyunderdierentpacketlossscenarios. Theobtainedresults
indicatethat themodelcan besuccessfully appliedto investigate TCPperformanceand can
be usedasa test-bed to evaluatedierent scenariosand variationsof TCP.
The CPN TCP model has also been used as a buildingblock in two other performance
analysis projects. In oneprojectitwasusedasacomponent ina modelfocusingon capacity
planning andperformanceanalysis ofwebservers. TheTCPprotocol isusedinthiscontext
for transmission of documents between web clients and web servers. In another project, it
was used as component in a model analysing the performance of a web based application
for distributedteaching. The TCP protocol is usedinthiscontext to implement theremote
procedurecall mechanism bymeansof whichclients andserverscommunicate.
Although the preliminary results indicate that the CPN TCP model can be applied to
analyse performanceof TCP protocols, further investigation on thisissue still needed. The
ideaistousethenewlydevelopedbatchsimulationfacilitiesintheDesign/CPNtoolinorder
to make a larger numberof simulations, considering various network scenarios and dierent
switch droppolicies.
Further renements in the CPN TCP model to incorporate additional aspects are also
important. For example, a more detailedmodel forRTO estimationcan be developed. The
timer granularityis an important factor indeterminingTCPperformance.
[1] M. Allman, C. Hayes, and S. Ostermann. An Evaluation of TCP SlowStart
Modica-tions. Computer Communication Review,28(3):41{52, 1998.
[2] S. Christensen,J.B. Jrgensen, and L.M. Kristensen. Design/CPN - A Computer Tool
forColouredPetriNets. InE.Brinksma,editor, Proceedingsof TACAS'97,volume1217
of Lecture Notes in Computer Science,pages 209{223. Springer-Verlag,1997.
[3] G. Ciardo, L.Cherkasova, V.Kotov, and T. Rokicki. Modelinga ScaleableHigh-Speed
InterconnectwithStochasticPetriNets. InProceeding of PNPM'95, pages83{93. IEEE
ComputerSocietyPress, 1995.
[4] H. Clausen and P. R. Jensen. Validation and Performance Analysis of Network
Al-gorithms by Coloured Petri Nets. In Proceeding of PNPM'93, pages 280{289. IEEE
ComputerSocietyPress, 1993.
[5] H.ClausenandP.R.Jensen. AnalysisofUsageParameterControlAlgorithmsforATM
Networks. InS. Tohme and A.Casada, editors,Broadband Communications II (C-24),
pages 297{310. ElsevierSciencePublishers,1994.
[6] D.E.Comer. Internetworkingwith TCP/IP, Vol. 1, Principles,Protocols and
Architec-ture. Prentice Hall, 1994.
[7] DARPA. TransmissionControlProtocol|ProtocolSpecication. RFC|793,
Septem-ber1981.
[8] K. Fall and S.Floyd. Simulation-BasedComparisons ofTahoe, Reno,and SACKTCP.
Computer Communications Review, 26(3):5{21, 1996.
[9] R.Goyal,R.Jain,S.Kalyanaraman,S.Fahmy,andB.Vandalore.Improvingthe
Perfor-manceofTCPovertheATM-UBRService. ComputerCommunications,21(10):898{911,
July1998.
[10] J. C. Hoe. Improving theStart-up Behavior of a Congestion ControlScheme for TCP.
In Proceedings of SIGCOMM'96. ACM,August 1996.
[11] V.Jacobson. CongestionAvoidanceandControl.InProceedingsofSIGCOMM'88,pages
314{329. ACM, August 1988.
[12] K. Jensen. Coloured Petri Nets. Basic Concepts, Analysis Methods and Practical Use.
Volume 1, Basic Concepts. Monographs in Theoretical Computer Science.
Springer-Verlag, 1992.
[13] K. Jensen. Coloured Petri Nets. Basic Concepts, Analysis Methods and Practical Use.
Volume 2, Analysis Methods. Monographs in Theoretical Computer Science.
Springer-Verlag, 1995.
[14] K. Jensen. Coloured Petri Nets. Basic Concepts, Analysis Methods and Practical Use.
Volume3,PracticalUse.MonographsinTheoreticalComputerScience.Springer-Verlag,
1997.
39
[16] L. M. Kristensen,S.Christensen,and K. Jensen. The Practitioner'sGuideto Coloured
PetriNets. Software Tools for Technology Transfer, 2(2):98{132, 1999.
[17] A. Kumar. Comparative Performance Analysis of Versionsof TCP ina Local Network
withaLossyLink. IEEE/ACMTransactionsonNetworking,6(4):485{498,August1998.
[18] T. V.Lakshmanand U.Madhow. The PerformanceofTCP/IPforNetworkswithHigh
Bandwith-DelayProductsand RandomLoss. IEEE/ACM Transactions on Networking,
5(3), June1997.
[19] B.LindstrmandL.M.Wells.SimulationBased PerformanceAnalysis inDesign/CPN.
In K. Jensen, editor, Proceedings of Workshop on Practical Use of Coloured Petri nets
and Design/CPN, pages117{130, 1998.
[20] Design/CPN Online. http://www.daimi.au.dk/designCPN/.
[21] A. Ost and B. R. Haverkort. Analysis of Windowing Mechanisms with Innite-State
StochasticPetri Nets. Performance Evaluation Review,26(2):38{46, August 1998.
[22] W. R. Stevens. TCP/IP Illustrated, Vol. 1, The Protocols. Professional Computing
Series.Addison-Wesley,1994.
[23] W. R. Stevens. TCP Slow Start, Congestion Avoidance, Fast Retransmit, and Fast
Recovery Algorithms. RFC| 2001, January 1997.