DOC PREVIEW
UCLA COMSCI 218 - Claudio-pres218

This preview shows page 1-2-24-25 out of 25 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
View full document
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 25 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

Slide 1Slide 2Slide 3Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20Slide 21Slide 22Slide 23Slide 24Slide 25TCP Westwood (TCPW) and Bandwidth Estimationcs218 – fall 2003Claudio E. Palazzitutor: Dr. Giovanni PauOutline•Background: TCP and wireless environment•TCP Westwood overview•New bandwidth estimation algorithm•Simulations results with NS-2•ConclusionsTCP Congestion Control (1/2)•end-end control (no network assistance)•sender limits transmission: LastByteSent-LastByteAcked  CongWinRoughly,•CongWin is dynamic, function of perceived network congestionHow does sender perceive congestion?•loss event = timeout or 3 duplicate acks•TCP sender reduces rate (CongWin) after loss eventtwo mechanisms:–AIMD–slow startrate = CongWin RTT Bytes/secTCP Congestion Control (2/2)Problems Affecting Current TCP•Error losses in wireless environment: –wrong congestion assumption.•Random errors results in low performance:–Congestion window cut too much–If happens during slow start, cause TCP premature exits D a t a G e n e r a lD a t a G e n e r a lB a s e S t a t i o nW i r e l e s sH o s tI n t e r n e t I n t e r n e tT C Pl o n g p r o p a g a t i o n t i m el i n k e r r o r sRelated TCP + Bdw estimation work•TCP Vegas monitors bandwidth and RTT to infer the bottleneck backlog; then, from backlog it derives feedback to congestion window.•Keshav’s Packet Pair scheme also monitors bandwidth to estimate the bottleneck backlog and compare to common target; it adjusts source rate.•…•TCP-Probing discriminates between error losses, congestion losses, handoffs and disconnections using probing cycles after each loss.•WTCP estimates the bandwidth at the receiver considering the packets received, then calculates the new sending ratio and communicates it to the sender (SACK and no more T.O.)•…•Enhance congestion control via Eligible Rate Estimate (ERE)•Samples are derived from ACK arrival statistics, and info in ACKs regarding bytes delivered•ERE is used by sender to set cwnd and ssthresh after packet loss indicationReceiverSenderInternetBottleneckpacketsACKsmeasureTCP WestwoodTCP Westwood: Control After Packet Loss IndicationWhen three duplicate ACKs are received:•set ssthresh=ERE*RTTmin (instead of ssthresh=cwin/2 as in Reno and NewReno)•if (cwin > ssthresh) set cwin=ssthreshWhen a TIMEOUT expires:•set ssthresh=ERE*RTTmin (instead of ssthresh=cwnd/2 as in Reno) and •set cwin=1TCP Westwood: Eligible Rate EstimateBE Sampling:Packet pair, effective under random loss, overestimates under congestionUnder CongestionUnder No CongestionRTTdkRTTktjtjs TkTkRE Sampling:Packet train, fair estimate under congestion, underestimates under random loss)/(1kkkkttdS• To obtain ERE: adapt the sample interval Tk according to congestion level• Congestion level is similar to that in Vegas: Expected Rate-Achieved Rate•Tk ranges from one ‘interACK’ interval to RTTTCP Westwood and random losses•Reno overreacts to random loss (cwin cut by half)•TCPW less sensitive to random loss •a small fraction of “randomly” lost packets minimally impacts the rate estimate RE•Thus, cwin = RE x RTT remains unchanged •As a result, TCPW throughput is higher than Reno and SACKBut…Current BW Estimation WeaknessPrinciple behind Westwood (and others): BW estimation = Bytes_acked / time NOT ALWAYS CORRECT ! It doesn’t consider idle time at sender…1 TCP Westwood Agile connection - 70 ms RTT - queue = pipesizeMultiple losses caused by UDP flows which start when the queue is almost fullRationale of the ideaTime line chunked into slotsPckts departureCorresponding acks arrivalEffective tx time Sender idle timeBandwidth estimation mechanism that rely on byte transmitted on time, should take into account the unused time at sender.New BW estimation algorithm • At sender side, divide time into slots• In each slot, N packets are sent to destination• The corresponding N acks will return back in a certain amount of time T• The bandwidth computation considers also the time the sender was idle (it hasn’t sent anything because he was waiting for ACKS…)• BWE sample:• Slot size is computed at the starting of the new one as a multiple of the RTO• Bwe sample is averaged (k less or equal than 1): BWES = Bytes_in_slot / (Time_for_acks – Time_sender_idle)BWEi= (1-k)*BWEi-1 + k*BWESData StructureRTT 0RTT 1RTT 2RTT 3RTT 9Element of the array:Seq no. of first pkt tx in that rttSeq no. of last pkt tx in that rttDep. time first pkt tx in that rttDep. time last pkt tx in that rttStart time receiving slotArr. time last ack rec in that rtt• Every slot change element where insert new departures• Every slot compute new bandwidth estimationJust after last bwe calculationSimulation Environment100 Mbps1 ms delayMin RTT: 70 ms100 Mbps1 ms delayBottleneck (various bw value)33 ms delayErrors in the Bottleneck: 0 or 0.1% PERQueue = pipe size1 flow TCPNew estimator tested above Westwood AgileSimulations 1/41 TCP Westwood Agile connection - 70 ms RTT - queue = pipesizeMultiple losses caused by UDP flows which start when the queue is almost full new bwe: no more big drop due to idle time at sender sideSimulations 2/41 TCP Westwood Agile connection - 70 ms RTT - queue = pipesizeBottleneck BW = 1Mb - pipe size = 9pktsPER = 0%PER = 0.1%Slot=3RTOk_avg=0.5Simulations 3/41 TCP Westwood Agile connection - 70 ms RTT - queue = pipesizeBottleneck BW = 5Mb - pipe size = 44pktsPER = 0%PER = 0.1%Slot=2RTOk_avg=0.2Simulations 4/41 TCP Westwood Agile connection - 70 ms RTT - queue = pipesizeBottleneck BW = 10Mb - pipe size = 88pktsPER = 0%PER = 0.1%Slot=3RTOk_avg=0.2Conclusions• With one flow, our proposed algorithm: - provides a bandwidth estimation comparable with TCP Westwood (both with or without random errors)- detects initial available bandwidth as fast as (or faster than) AGILE does- is lighter to calculate than TCP Westwood’s formula- performs better than TCP Westwood in conditions characterized by long sender-side idle time period, as during long Fast Retransmit – Fast Recovery • We think that, our algorithm:- differently than TCP Westwood, detects the total bandwidth at the bottleneck, and not the shared bandwidth- could really be effective if integrated


View Full Document

UCLA COMSCI 218 - Claudio-pres218

Documents in this Course
GSM

GSM

59 pages

Chord

Chord

30 pages

10_2

10_2

9 pages

13_4

13_4

10 pages

RAP

RAP

17 pages

46_4

46_4

9 pages

32_4

32_4

10 pages

umts

umts

39 pages

AdHoc-MAC

AdHoc-MAC

29 pages

rma

rma

8 pages

Lecture

Lecture

29 pages

Load more
Download Claudio-pres218
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Claudio-pres218 and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Claudio-pres218 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?