Selected Topics GPU Software
Selected Topics GPU Software CSC 391
Popular in Course
Popular in ComputerScienence
This 37 page Class Notes was uploaded by Melyssa Aufderhar on Wednesday October 28, 2015. The Class Notes belongs to CSC 391 at Wake Forest University taught by Errin Fulp in Fall. Since its upload, it has received 7 views. For similar materials see /class/230723/csc-391-wake-forest-university in ComputerScienence at Wake Forest University.
Reviews for Selected Topics GPU Software
Report this Material
What is Karma?
Karma is the currency of StudySoup.
You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!
Date Created: 10/28/15
m HighrSpeed Networks Transport Layer UDP and TCP csc 391790 WAKE FOREST Department of Computer Science Spring 2009 Transport Layer UDP and TCP Transport Layer 0 Reliable cost effective data transport from source to destination End to end protocol Only implemented at hosts not routers o What is the difference between transport and network layers Transport provides logical communication between processes Network provides logical communication between hosts What does this di erence imply What is an example 0 Transport entity provides services to upper layers Type of service data transfer connection management and flow control W Fulp 1 Transport Layer UDP and TCP 2 HighrSpeed Network TCPI P EndtoEnd Communication Source host Des nan39on host TCPUDP PDUs TCPAJDP lnlemet global inlemelwork logical oommunican39ons pelh of prolonol data urils PDUs Access network X I astral path TCPUDP lrensmission oonlrol probeduser dalagram proloool P lnlemetp39oloool LP lirk proloool PL physical layer m w Fulp Sprmg 2009 Transport Layer UDP and TCP 3 HighrSpeed Network Type of Service Two types of service available connection oriented and connectione55 o Connection oriented Establishment maintenance and termination of connection Typically implies reliable service 0 Connectionless Unreliable service delivery not guaranteed Reduces the overhead associated with transport layer Network layer has connection oriented and connectionless why is it speci ed here Is it redundant E w Fulp Sprmg 2009 ngheSpeed Network Transport Layer 00R and TCP E w rdlp o Might want to provide a service not provided by lower layer What if the network layer is connection oriented but unreliable What happens if a router crashes Provide a reliable service over an unreliable network Can you provide a reliable service using an unreliable network nghrSpeed Network Sprlllg 2009 Transport Layer UDP and TCP 5 E w rdlp o TPDU are messages sent from transport entity to transport entity 0 Message encapsulated as it passes through other layers TPDU a network layer datagram a link layer frame 0 For example TCP or UDP using IP using Ethernet Transport Protocol Data Unit Frarne TPDU header header Packet header l TPDU payload l Packet payload l Flame payload r Ethernet F TOP ol UDP header header header r TCP or UDP payload la leayload l Sprlllg 2009 4 HighrSpeed Networks Transport Layer UDP and TCP 6 Internet Transport Layer 0 There are two distinct Internet transport layer protocols User Datagram Protocol UDP Transmission Control Protocol TCP Session diredo Conlerence Audio Video lQharprl ry rol l tools SDP RSVP RTP and RTCP SDAP HTTP SMTP UDP TCP o UDP provides unreliable connectionless service 0 TCP provides reliable connection oriented service E w Fulp Spring 2009 HighrSpeed Networks Transport Layer UDP and TCP 7 Port Numbers 0 When an application process wishes to set up a connection to a remote application process it must specify which one 1521714092 provides http and ssh services Therefore network layer address is not sufficient 0 Transport addresses are used to identify processes For Internet transport layers this called a port number Both source and destination processes have a port number 0 Source and destination ports together uniquely identify a process 0 Port numbers are 16 bits ranging from O to 65535 Numbers 0 to 1023 are well known port numbers Reserved for use by well known protocols RFC 1700 E w Fulp Spring 2009 HighrSpeed Networks Transport Layer UDP and TCP s UDP User Datagram Protocol UDP is a lightweight protocol with minimalist service model RFC 768 Connectionless so no handshaking before sending What is handshaking Unreliable there is no guarantee of delivery Datagrams may arrive out of order In addition there is no flow control Send as much and as quickly as desired Often used for multimedia applications In summary an UDP application almost talks directly to IP UDP takes message from application then adds port numbers and two other fields before sending to IP E w Fulp HighrSpeed Networks m Transport Layer UDP a Spring 2009 nd TCP 9 U D P Datagram Structure What WWIin man111mm r a 7 a mamaquot w mm W Daa I l Ferluau 0 Source and destination port numbers 16 bits each 0 UDP length field 16 bits length of header and data in bytes 0 Checksum field 16 bits error checking for the UDP datagram One39s complement sum of all the 16 bit words in the segment If UDP 239s unreliable why error check W Fulp Spring 2009 HighrSpeed Networks Transport Layer UDP and TCP When is UDP Preferred UDP has the following benefits making it better for some applications 0 No connection establishment TCP requires a three way handshake before sending data UDP sends data immediately no initial connection delay No connection state TCP requires state information about sendreceive buffers congestion control sequence numbers per connection UDP does not require any of this state information Small packet header overhead UDP only adds 8 bytes of header information Unregulated send rate Send as quickly as desired great for high speed Has introduced the idea of TCP friendy applications m w Fulp HighrSpeed Networks Transport Layer UDP and TCP Sprmg 2009 11 TCP 0 Transport Control Protocol TCP provides connection oriented reliable service RFC 793 1122 1323 2018 2581 o All connections TCP connections are full duplex point to point Requires three way handshake to establish connection 0 Reliable transport service Deliver all data without error and proper order 0 Congestion control mechanism Attempts to limit each connection to fair share of bandwidth No minimum bandwidth guaranteed 0 TCP connection is a byte stream not a message stream Message boundaries are not preserved Data is buffered before sent additional delay E w Fulp Sprmg 2009 HighrSpeed Networks Transport Layer 00R and TCP 12 TCP Sending and Receiving 0 Sending process sends a stream of data to the socket Message placed in send buffer sized via three way handshake o TCP will periodically take chunks of data from send buffer Maximum amount that should be taken is limited by the Maximum Segment Size MSS E w Fulp HighrSpeed Networks Spring 2009 Transport Layer 00R and TCP 13 MSS is negotiable what should it be based on o TCP encapsulates the data with the client TCP header which creates a segment 0 Segment sent to IP layer which is encapsulated in datagram o How often does TCP take data from buffer segments at its own convenience RFC 793 quotSend data in 0 When TCP receives a segment it is placed in the receive buffer Application then reads information from buffer E w Fulp Spring 2009 HighrSpeed Networks Transport Layer 00R and TCP E w Fulp TCP Segment Structure 0 Segment consists of a header and data field 0 Data field contains the application data MSS limits the maximum size of the segment39s data field Large files are typically broken into mutliple pieces 0 For interactive applications telnet smaller data pieces are sent Segments sent are m 21 bytes long header is 20 bytes Would it have been better to develop telnet for UDP HighrSpeed Network Spring 2009 Transport Layer 00R and TCP E w Fulp 0 Source and destination port fields 16 bits each Identify source and destination processes TCP Header mp heath Ile s En cider To lxed may Dan M any Payload mmmm i KM mm Maximum memsmelMSS l Codebnde nmus 0mm Env snnn Namermncuun merit mama numbqslnmer Malislugs Spring 2009 14 HignSpeed Networks Transport Layer 00R and TCP 0 Sequence and acknowledgement number fields 32 bits each Used by TCP to ensure reliable data transfer service 0 Window field 16 bits Number of bytes receiver can accept from sender Is this congestion control 0 Header length field 4 bits Length of the TCP header in 32 bit words Variable length due to options standard length 20 bytes 0 Flag field consists of 6 bits ACK indicates value in acknowledgement field is valid RST SYN FIN used for connection establishment and teardown URG indicates data is urgent send immediately E w Fulp HighrSpeed Networks Spring 2009 Transport Layer 00R and TCP Sequence and Acknowledgement Numbers 0 TCP views data as a unstructured ordered stream of bytes 0 Sequenceacknowledgements numbers are for bytes not segments 0 If a host wants to send stream of data TCP will number each byte of information SN will represent the first byte number 0 Acknowledgement numbers are for the next byte expected In addition acknowledgements can be cumulative Host A Host B SN42 Data8 bytes ACKSO SNSO Data100 bytes E w Fulp Spring 2009 17 16 Hrgns peed Networks Transport Layer UDP and TCP TCP Connection Management Following events occur to establish a connection 1 Client side send a special TCP segment to server SYN segment 0 SYN bit is set specifies initial SN port and MSS 0 Contains no application data 2 SYN segment arrives at server check if process listening on port 0 If process exists and accepts connection Buffers reserved for connection SYNACK segment is sent back SYN bit set ACKs client SN and specifies server SN 3 Client side receives SYNACK o Allocates buffer space 0 Sends segment back to server ACKs server SN E w Fulp HighrSpeed Networks Sprmg 2009 Transport Layer UDP and TCP Host A Host B SYN1 SN42 SYN1 SN99 ACK43 SYNO SNSO ACK1OO o For termination consider connection as two simplex connections Each released separately TCP segment with FIN set FIN indicates no more to send and must be acknowledged Any problems with TCP close A type of network attack is the SYN flood where a client sends multiple SYN segments but never ACKs the SYNACK How is this an attack E w Fulp Sprmg 2009 19 18 HighrSpeed Networks Transport Layer UDP and TCP 20 TCP Reliable Data Transfer 0 TCP ensures that data placed in the receive buffer is Not corrupted has no gaps or duplicates and is in sequence 0 To achieve this TCP protocol is similar to Go Back N Timeouts are used per segment transmitted ACKs are cumulative Correctly received out of order segments are not ACKed o Proposals exist for TCP ACKing similar to selective repeat Specifically identify which segments were in error Called TCP Selective ACK TCP SACK E w Fulp Spring 2009 HighrSpeed Networks Transport Layer UDP and TCP 21 TCP Flow Control 0 TCP reserves a receive buffer for data received Rate at which data removed depends on application Therefore receive buffer can become full 0 TCP provides flow control by requiring the sender to maintain a variable called the received window Indicates the amount of free space at the receiver Can change size over time E w Fulp Spring 2009 HighrSpeed Networks Transport Layer UDP and TCP TCP Flow Control Operation Assume a TCP connection between stations A and B exists where station B allocates space for the received data rchuffer o Receiver station B has two additional variables lastByteRead is the number of the last byte read and removed from the receive buffer lastByteRcv is the number of the last byte received and placed in the receive buffer Since TCP is not permitted to overflow the buffer lastByteRcv 7 lastByteRead S rchuffer E w Fulp Sprmg 2009 HighrSpeed Networks Transport Layer UDP and TCP 23 Receive window rcvWindow is the spare room in the buffer rcvWindow rchuffer 7 lastByteRcv 7 lastByteRead Sender station A keeps track of two variables lastByteSent is the number of the last byte sent lastByteACKed is the number of the last byte ACKed The difference between these two variables is the amount of unACKed data sent Keeping the amount of unACKed data below the rcvWindow station will not overflow station B buffer lastByteSent 7 lastByteACKed S rcvWindow E w Fulp Sprmg 2009 m HrgnSpeed Network Transport Layer UDP and TCP Sender Recewer Reservers Appncauon buffer 4 0 4K Sim ACK 2040 WIN 2048 Appncauon We in sse2o48 Sender rs Appncatron blocked reads 2K Sender may send up to 2rlt a E w Fulp Sprrng 2009 HrgnSpeed Network Transport Layer UDP and TCP 25 Round Trip Time and Timeout 0 When a segment is sent into a TCP connection a timer is started If the timer expires before an ACK is received retransmit o How long should the timeout be7 Should be larger than round trip time Why Want to quickly retransmit lost segments Estimating the Round Trip Time RTT Let sampleRTT be the amount of time from when a segment is sent until its ACK just a sample value sampleRTT will fluctuate based on network conditions w Fulp Sprrng 2009 nghrSpeed Network Transport Layer UDP and TCP 26 For this reason TCP maintains a variable estimateRTT as the estimated RTT which is updated based on new samples estimateRTT 17 a X estimateRTT a gtlt sampleRTT Therefore estimateRTT is a weighted sum of the previous measurements and estimates typically a 0125 Example R TT Samples and Eslmaled R TT e0l25 a Sample R TT Esllmaleemr Erample R TT Samples and Eslmaled R TT a 0 75 Sample R TT Esllmaled R TT a a round mp llme round mp llme m E w Fulp nghrSpeed Network Transport Layer UDP and TCP Sprlrlg 2009 27 Setting the Timeout 0 Typically the timer is set to estimateRTT plus a margin Margin should be small when there is little fluctuation Margin should be large if there is a large fluctuation o TCP uses the formula timeout estimateRTT 4 X deviation 0 deviation is an estimate of how much sampleRTT deviates from estimateRTT deviation 1 7 gtlt deviation Q X lsampleRTT 7 estimateRTTl E w Fulp Sprlrlg 2009 Transport Layer UDP and TCP 2s HighrSpeed Network Example RTT Values and Timeuut a B 0125 Example RTT Values and Timeuut a 3 0125 N ha RTT Esnmated RTT Tlmeuut raunump tlme raunump tlme Since segments maybe lost how should retransmissions change the estimated RTT E w Pulp Sprmg 2009 Transport Layer UDP and TCP 29 HighrSpeed Network Delay Bandwidth Product o What is the best flow control Window size7 Large enough to allow the sender to transmit at full speed Need to quotkeep the pipe full to avoid delays we Mapuvm Don39t let the window exhaust before first ACK is received 0 The amount is called the delay bandwidth product r gtlt d Increasing bandwidth 7 makes the pipe fat increasing delay d makes the pipe long insertjoke here m w Pulp Sprmg 2009 m HignSpeed Network in HignSpeed Network W Tianspoit Layer UDP and TCP TCP and Window Size 0 Assume RTT delay is 100 msec and bandwidth is 1544 Mbps What is the minimum Window size7 011 secgtlt1t544 X 106 bitssec 154400 bits 0 Is the TCP Window size large enough TCP ack39s every byte therefore SN represents a byte 15440 b39t W 7 19300 bytes TCP window 216 71 65 535 bytes it works 0 Consider at 1 Gbps 011 secgtlt110 gtlt 109 bitssec gtlt 12500000 bytes TCP window field is too small Should Nairb go outside and shoot TCP Fulp Spiing 2009 Tianspoit Layer UDP and TCP 31 TCP Window Scale Option 0 Allows the sender and receiver to negotiate window RFC 1323 The senderrecevier shift the window by 2 c where max at is 14 NOP option window scale option lt gt l l E 9 32 i iiiiiiiiiiiiiiiiiii iiii Nnd i l Kind 3 l Lengtn 3 l Shillcoum no opeiation option used to pad tne Wmdow scale option to 4 bytes The Value in tnesnitt counllield is tne poweioi 2 inuitipies oi tne value in tne iiindow size tieid The maximum count Va 0 I snitt 00m i oscaing maximum Wm 0w 65535 bytes Shillcou 1i inuitipiy by 2 maximum Wmdow i3io7o Shillcoum M mulliply by 2 maximum Window 1073725440 0 Maximum window size is 214 gtlt 65535 1073725440 Is there enough sequence number to cover this window W Fulp Spiing 2009 HrgrSpeed Networks Transport Layer UDP and TCP 32 TCP Sequence Numbers 0 TCP specifies that a segment lifetime should be S 120 seconds Gerg says awkwardly so what slapping Nairb Send a TCP segment after 120 seconds can reuse the number Numbers wrap around after 232 byte sent 4294967296 bytes 0 Ifa connection bandwidth is 1544 Mbps how much time is that 32 8 m 2781 seconds or 6 hours 0 Ifa connection bandwidth is 1 Gbps how much time is that 32 X8 10gtlt109 This is less than the MSL 34 seconds E w Fulp H1ghrSpeed Networks Sprlng 2009 Transport Layer UDP and TCP 33 Time Stamp Option 0 Allows the sender to place a timestamp in every segment Timestamp is monotonically increasing value Receiver copies timestamp in the returning ACK 1 a 9 1617 111111111111111111111 Nnd l Nnd1 Kind 8 Timestamp value 32 l l length 10 Timestamp echo reply 0 Original intent was to better calculate RTT estimates RTT is current time minus returned timestamp in the ACK Does this solve the previous RTT problem What about detecting when numbers have wrapped E w Fulp Sprlng 2009 HignSpeed Networks Transport Layer UDP and TCP 34 PAWS 0 Protection Against Wrapped Sequence Numbers Consider the timestamp an eXtension of the sequence number If a segment arrives with valid number but timestamp is old then discard Does this require clock synchronization Unfortunately there is a security risk with PAWS mrrrrrow Attacker sets a large value as the packet timestamp Target computer processes this packet the internal timer is updated to the large value that the attacker supplied Causes all other valid packets that are received to be dropped Vulnerable http www securityfocus combid13676discuss E w Fulp Spring 2009 TCP Congestion Control and Performance csc 391790 WAKE FOREST Department of Computer Science Spring 2009 Higanpeed Networks TCP Congestion Control and Performance 1 TCP Congestion Control Control TCP connections sharing the bandwidth of a congested link 0 TCP congestion control is closed loop and uses implicit feedback 0 Transmission rate limited by the window size in Number of bytes that can be sent without ACKs 0 General operation Transmit as fast as possible as long as no segments are lost TCP starts with a small w and increases slowly over time Once a segment is lost w is reduced quickly Process is repeated during the connection lifetime Why is this implicit feedback not emplicit feedback E w Fulp Spring 2009 Higanpeed Networks TCP Congestion Control and Performance TCP Throughput 0 An important measure of TCP performance is throughput Rate at which data transmitted from sender to receiver 0 Throughput will depend on w If w segments sent back to back must wait RTT to send again If w bytes every RTT seconds the throughput bytessec is w W 0 Consider k TCP connections traversing a link that has capacity 7 Assume no UDP connections use the link and each TCP connection requires more bandwidth than 7 Why no UDP m w Fulp Higanpeed Networks Spring 2009 TCP Congestion Control and Performance Ideally each connection should receive 0 Consider a connection that passes through 11 links Assume link i has capacity 7 and k connections use the link The maximum throughput for the connection would be 7 2 no 7quot1 mm kilk72a This is called a max min fair allocation E w Fulp Spring 2009 3 2 Higanpeed Networks TCP Congestion Control and Performance 4 TCP Congestion Control Overview 0 Each side of a TCP connection maintains Send and receive buffers Variables lastByteSent rcvWindow 0 There are two additional variables to maintain congWindow Another constraint on the amount sent threshold How quickly congWindow grows o The amount of unACKed data that can be sent is lastByteSent 7 lastByteACKed S min congWindow IcvWindow Therefore amount that can be sent is bound by two windows rcvWindow determined by the receiver congWindow determined by congestion E w Fulp Spring 2009 Higanpeed Networks TCP Congestion Control and Performance 5 Example Operation 0 Assume station A sends to station B using a TCP connection Station A takes one MSS from the send buffer and sends to B Initially congWindow equals one MSS bytes 2 If the segment is ACKed before the timeout congWindow is increased by one MSS 3 Station A sends two MSS to station B 39gt If these segments are ACKed before their timeout congWindow increased by one MSS per ACKed segment 5 Station A sends 4 MSS o The procedure continues as long as congWindow lt threshold ACKs arrive before timeout E w Fulp Spring 2009 TCP Congestion Control and Performance 6 Higanpeed Network During the initialization congWindow increases exponentially congWindow 2 after 1 RTT congWindow 4 after 2 RTT congWindow 8 after 3 RTT o This is called slow start because the window size starts small although increases quickly 0 Once threshold is passed congWindow increases linearly Increase congWindow by one MSS every RTT This phase is called congestion avoidance E w Filip Spring 2009 TCP Congestion Control and Performance 7 Higanpeed Network o A timeout indicates congestion Set threshold threshold2 and congWindow 1 M55 TCFCangeslianWindaW TCPCungesliunWinduw m a conges1ionwindow segmenls s m m a m s m mngesiinnwmunwiseg 20 25 a 10 12 14 5 in i5 numbei ui liansmissiuns 4 a numbeiolliansmissions E w Filip Spring 2009 Higanpeed Networks TCP Congestion Control and Performance 8 TCP Tahoe o The previous congestion mechanism is TCP Tahoe rules are If congWindow lt threshold slow start phase congWindow grows exponentially 2 If congWindow gt threshold congestion avoidance phase congWindow grows linearly 3 Whenever a timeout occurs threshold threshold2 and congWindow 1 o This process continues for the duration of the connection However timeouts are lengthy need to detect congestion earlier E w Fulp Spring 2009 Higanpeed Networks TCP Congestion Control and Performance 9 0 Two other variations of Tahoe eXist Reno implemented by most OS and Vegas Both attempt to improve on the performance of Tahoe E w Fulp Spring 2009 Higanpeed Networks TCP Congestion Control and Performance TCP Reno o Attempts to adjust to congestion before timeout Use timeouts and duplicate ACKs to indicate congestion 0 Why would a sender receive duplicate ACKs7 TCP does not allow NACKs If a segment is received out of order receiver re ACKs the last in order byte duplicate ACKs NB This means other segments are being received so congestion may exist o If the sender receives 3 duplicate ACKs This signals the sender to send the segment following the segment that has been ACKed three times E w Fulp Higanpeed Networks Spring 2009 TCP Congestion Control and Performance E w Fulp aSimplification details in RFC2581 Hopefully this occurs before the missing segment timeout This is called fast retransmit RFC 2581 Sender Receiver ACKZ ACKS ACKS ACKS ACKS Retransmil packela After fast retransmit following steps are taken in TCP Renoa TCP moves to congestion avoidance phase Set threshold threshold2 Set congWindow congWindow2 This is called fast recovery Spring 2009 11 10 Higanpeed Networks TCP Congestion Control and Performance 0 After a timeout same action taken as Tahoe 0 Generally speaking no slow start TCP increases congWindow by 1 M55 per RTT then halves the value once path is congested Called Additive Increase Multiplicative Decrease AIMD E w Fulp Higanpeed Networks 12 Spring 2009 TCP Congestion Control and Performance TCP Vegas 0 Previous congestion control were based on last packet transmitted Set timeouts and measured round trip delays Why is this not good enough 0 Measures throughput as well as duplicate ACKs and timeouts ln Tahoe and Reno the congestion avoidance mechanism increases congWindow over time decreases if there is a loss 0 Vegas computes the expected throughput of the connection as congWindow ex ectedThru P min sampleRTT o The actual throughput actualThru is also calculated Periodically measure the time to send a segment E w Fulp 13 Spring 2009 m E Higanpeed Networks Higanpeed Networks TCP Congestion Control and Performance 0 Vegas compares the two throughputs and adjusts congWindow 0 Let 6 expectedThru 7 actualThru In addition define two thresholds a and Q where a lt Q The difference in throughput is compared to the thresholds if 6 lt a increase congWindow linearly if 6 gt decrease congWindow linearly avoid congestion if a lt 6 lt congWindow remains the same Still performs multiplicative for segment loss Vegas attempts to avoid this situation w Fulp Spring 2009 TCP Congestion Control and Performance TC P Congestion Performance 0 The congestion window at the ith ACK is wi1 0 Let39s rewrite in the time domain 0115 where y is the threshold and It is the time threshold is reached wi1 wi l ii slow start congestion avoidance w t 2 RTT slow start tity RTT congestion avoidance 0 We have assumed no losses 7 Mt The rate of the connection 7 i W W Fulp Spring 2009 m HighrSpeed Network TCP Congestion Control and Performance 16 0 Therefore smaller RTT can achieve higher rates more quickly 56 Congestion Window Kbyte 0 50 100 150 200 250 31 350 41 450 51 550 Elapsed Time ms E w Fulp Spring 2009 HighrSpeed Network TCP Congestion Control and Performance 17 Performance with Losses 0 Let39s only consider the AIMD part of TCP Interested in relationship to loss rate and throughput i w lfwmdow IS w the rate IS 7 i W 0 Also know that w increases linearly until a loss then w 1112 Insert awesome picture of me strangling a bookl Therefore lose a packet every d y seconds 0 ln d seconds TCP sends l 1 l 2 w Fulp Spring 2009 Higanpeed Networks TCP Congestion Control and Performance 0 Let loss be p m 38 which is one loss in d time Therefore w 3 p 0 Combine with previous equations for the rate 8 3ig 7 125 4t wit This is the quotinverse square root law for TCP connections 7 o This law is used to create TCP friendly protocols What does that mean E w Fulp Higanpeed Networks m TCP Congestion Control and Performance Spring 2009 TCP Hybla o TCP performance suffers with high latency Takes too long to expand the transmission window A problem for high latency terrestrial or satellite radio links 0 Expected since TCP throughput is dependent on window size Hybla Attempts to make w independent of RTT Com pensate for dividing the window by RTT o The congestion window at the ith ACK is H wi1 where p RTTRTTO w 2 7 1 slow start 2 w congestion av0idance z W Fulp Spring 2009 HighrSpeed Network TCP Congestion Control and Performance 20 o The window size used for transmission at time t is wHt gt slow start p p 7 congestion avoidance onhuearnh WindW lee cnhgegmh WndUW Kml2 an mm 150 2m 250 300 Elapsed whet TCP quot3 So RTT is still in the equations How is the transmission rate independent of the RTT 350 6m an am 550 50 mu 150 200 E 250 300 350 mu osu 500 550 lapsed rhe ms TCP Hybla E w Fulp HighrSpeed Network TCP Congestion Control and Performance 2 Sphhg 2009 Simple TCP Modification 0 Let39s keep AIMD just make the following modifications Increases in by a larger number say 32 each RTT After a packet loss decreases in by 18 instead of 12 This should grow it faster 155 The rate IS 1V where t is RTT scalable but not fair TCP Thruugnput as Prubability 0f Lass increases throughput bps in quot luss prubability E w Fulp Sphhg 2009 Higanpeed Networks TCP Congestion Control and Performance 22 TCP Congestion Control for HighSpeed 0 Simple changes to AMID are not sufficient Provide scalability but not fair 0 Several new TCP congestion control methods HighSpeed TCP HSTCP TCP BIC binary increase TCP CUBIC E w Fulp Spring 2009 Higanpeed Networks TCP Congestion Control and Performance 23 H ighS peed TC P o HSTCP attempts to model the fairness of n TCP connections Adaptiver increase or decrease in based on in value Larger the w the larger increment and smaller the decrement Would this mimic the behavior ofn connections 0 Let in increase by aw segments per RTT assume no loss wi1 W awiwi 0 Let in decrease to w1 7 bw segments in response to a loss wi1 wi X 1 MW 0 For standard TCP aw 1 and bw 12 HSTCP uses these values when w 3 wow E w Fulp Spring 2009 Higanpeed Networks t TCP Congestion Control and Performance 24 o For w tum9h we have specified a loss rate of phigh Adjust w to maintain TCP fair allocations WU 2 Z 2 aw pk 9hwhzgh 2 7 where bw is decthgh for w tum9h default values of tum9h 83000 and phigh 1gtlt 107 0 Value of bw for other values of w gt wlow Let bw vary linearly as the log of w Mm decrhigh 05 lOgw 7 lOgwlow 05 10gwhigh 7 10gwlow lncrease parameter aw can then be computed as follows aw w2 gtr pw gtr 2 gtr bw2 7 bw m w Fulp Sphhg 2009 Higanpeed Network TCP Congestion Control and Performance 25 0 As a result w will grow faster than standard TCP and recover from losses more quickly quotThis behavior allows HSTCP to be friendly to standard TCP flows in normal networks and also to quickly utilize available bandwidth in networks With large bandwidth delay products quot RFC3649 o The approximate rate of HSTCP is 7 txgo TCP Thruughput as Luss Rate increases TCP Rena M AlMD 1 HSTCP throughput E w Fulp Sphhg 2009 Higanpeed Network TCP Congestion Control and Performance 0 Consider congestion control as a search problem Current w does not have loss set as minimum 111mm Maximum w was obtained from last loss wmagc 0 Perform binary search to determine best w whilewmm S wmam inc wmiL wmam2 7 u ifinc gt 37mm inc 3mm else ifinc lt 3mm inc 3min endif u u inc ifno packet loss endwhile where 3mm is min increment and 5mm is the maX increment E w Fulp Spring 2009 Higanpeed Network TCP Congestion Control and Performance 27 o A unique feature is that its increase function is logarithmic So what 0 A few other considerations lf w reaches wmagc then set w wmm and wmam to constant lf loss occurs then w w gtlt 17 Wiride Size asTime increases vwiduvv Size as Time increases 5 in i5 2 5 in i5 20 25 30 time an E w Fulp Spring 2009 Highrspeed Network TCP Congestion Control m Performance 28 TCP CUBIC o CUBIC is similar to BIC but simplifies the algorithm Still have the concave and convex window growth Installed on most Linux systems 0 Determines a target w value wtarget Ct 7 K3 wmm K Depending on the current w there are three different modes TCP standard ifw is less than where a standard TCP connection should be set w to this value Concave if w lt wmm then increment by iwtmjj w Convex if w gt wmm then algorithm searching for new maximum increment w by W but wtwggt is different E w mp Spring 2009 Hig spTed39Nawmk TCP Congestion Control m Performance 29 o In terms of fairness E w mp Spring 2009 H1ghrSpeed Network TCP Congesmon Control and Performance 30 TCP Window and Loss 105 MEI iSE UEnEE number ACK 2 iSeuuence number ACK 12356 12356 12356 1 2356 lime 1 56 12356 12356 12356 1256 x109 1 2356 lime MUS iSE UEnEE number ACK 12356 12356 12356 lime MUS iSEqUEHEE numnev ACK 12356 1 2356 1235 lime X mg r 1 2356 1 2356 E w Fulp H1ghrSpeed Network Spring 2009 TCP Congesmon Control and Performance 31 N 9 gt TCP Congestion Control Weaknesses Assumes any loss is an indication of congestion 0 Loss may be due to temporary router error 0 Wireless networks have higher loss rate due to transmission technology sending moreless segments does not change performance Assumes congestion is due to own window size 0 A malicious user could force others to reduce their rate 0 No differentiation Detects congestion using loss with no room for error 0 In steady state buffers are typically full 0 A short burst will cause everyone to reduce rate Assumes all users experience same loss probability E w Fulp Spring 2009 nganpeed Networks TCP Congestion Control and Performance 32 Sending Data Using TCP Consider a telnet session where the user is using vi 0 In the worse case When a character arrives to the send buffer new TCP segment 21 bytes created given to IP 41 byte datagram Receiver side TCP immediately sends 40 byte ACK Why is the ACK 40 bytes When vi processes character it sends it back to sender echo which requires another 41 byte lP datagram As a result 162 bytes sent for each character One solution is to delay ACKs and rely on cumulative ACKs Reduces the number of ACKs Does not reduce sending overhead E w Fulp Spring 2009 nganpeed Networks TCP Congestion Control and Performance 33 Nagle39s Algorithm 0 Nagle39s algorithm is an another solution to the preceding problem 0 When data comes one character at a time into sending buffer Send first character buffer remaining until ACK received Hopefully a larger segment can be sent once ACK received What type of application does not work well with the algorithm E w Fulp Spring 2009 Htganpeed Network TCP Congestton Control and Performance 34 Silly Window Syndrome 0 Problem occurs when data is passed to sending entity in large blocks but receiver application only reads one byte at a time 0 Consider the following situation 1 One byte read by receiver TCP sends window update Advertised window size is one byte 3 Sender sends one byte 9 Receiver ACKs advertises window size is zero b Application reads one byte E w Fulp Htganpeed Network m Sprtng 2009 TCP Congestton Control and Performance 35 Recetvev s bullet ls lull Appltcalton reads t byte I Room tot one move byte thdow update segment sent New byte antes t Byte Recetvev s bullet ls lull 0 Solution prevent the receiver from advertising a window of 1 byte Instead wait until advertised window equals one MSS Is Nagle s algorithm and the solution to silly window syndrome complements or the some solution W Fulp Sprtng 2009 HighrSpeed Networks r TCP Congesuon Control and Performance 36 Internet Transport and Application Layers Application Transport Application Layer Protocol Layer Protocol Electronic mail SMTP RFC 821 TCP Remote terminal access telnet RFC 854 TCP Web http RFC 2616 TCP File transfer ftp RFC 959 TCP Remote file server NFS UDP or TCP Streaming multimedia UDP Internet telephony UDP E w Fulp Sprmg 2009
Are you sure you want to buy this material for
You're already Subscribed!
Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'