Computer Networks


Larger Questions


Useful web sites for TCP/IP (Lawrence Berkely National Labs Network Research Group){fast ethernet)†† (the ATM forum) to ATM related web sites)†† (General networking issues) interest group on Communications)


1.Transport protocols like TCP provide a reliable connection between application processes on remote hosts.What issues must be addressed in providing a reliable connection between hosts, and how does TCP specifically address them?


2.Discuss the similarities between the issues addressed at the data link level and the transport layer level and indicate the significant differences.


3. Compare the congestion/flow control algorithm used in SNA that we discussed earlier in class (and the backpressure algorithm of TYMNET mentioned in passing) with the methods for controlling flow and congestion used in TCP.What are the similarities, and what are the reasons that the methods for detecting and controlling congestion in SNA cannot be duplicated in TCP ?


4. In an Internet, hosts and users can have many different names or addresses.These include the local network ID, the internet ID, the URL, the e-mail address, etc.How are the different names and addresses that are used resolved to be able to locate the desired process or user over the Internt?


5.Discuss how adaptable both IP and TCP are to the changing scale (size, bandwidth, uses) of the internet.Version updates such as IPv6 partially address this question, but also discuss the strengths and weaknesses of the philosophical approach to networking that TCP/IP represents.




Computer Networks


TCP Issues

1.Transport layer protocols manage a peer to peer (host to host) connection.†† Many of the issues are similar to ones confronted in managing an end to end connection across a data communications channel, but the "channel" that must be used for transmiting data here is a network or an interconnection of many networks.This "channel" differs from a transmission line in that it has storage capability.It also has a variable "bandwidth" or maximum data rate that is dependent upon the path to the destination.Packets can be delayed and arrive long after a duplicate has been received and sometimes even after a particular connection has been closed.In less extraordinary circumstances, the delay in sending data and acknowledgements across this network carrier can vary dramatically even over short periods of time.When we studied the data link layer, we learned that the choice for a sender's window size was governed by the desire to keep the "pipe" full to maximize utillization.We wanted:


††††††††††† W x packet size > RTT xData Rate


On a "network channel" RTT has a large variance and the Data Rate is limited to the lowest capacity of the networks in the data path.The strategy that TCP will use to find the appropriate data rate for a given connection will be to increase the output of the source until it reaches the capacity of the destination to receive or exceeds the capacity of the internet to deliver.When congestion occurs and packets are lost, TCP goes through a modified version of the original "slow start" process.


††††††††††† The issues that one confronted in the Data Link protocols involved managing a point to point connection so that data was not lost or duplicated, efficient use was made of the bandwidth, errors in transmission were detected, and packet transmissions were properly delineated.A transport protocol uses data link connections that detect, and correct through retransmission, errors that occur in transmission -- errors caused by transmission phenomena such as noise.The errors that must be detected at the transport level are memory errors -- errors in reading and writing memory that may occur during the store and forward transit of the data through the networks.Memory errors are more infrequent than transmission errors, and a ones complement of the sum of the data bytes (the Internet checksum algorithm) is used.The bytes being totaled in this count include the address and length fields of the IP header, the TCP header, and the data.Therefore,to compute the checksum, a pseudo (IP) header is appended to the TCP packet.


††††††††††† TCP maintains two window parameters for managing flow control and congestion control: a credit window limit and a congestion window limit.The credit window is used to control the flow betweem the source and destination.The sequence numbers start from an initial value stipulated during the three way handshake that is used to open a transport connection.The credit window limit is simply the advertised window size (in the TCP header) + the last byte ACKed - the (sequence number of) the last byte sent.


†††††††† last ACK†††††††† last SYN††††††††††††††††††††††††††††††††††††† †††

††††††††††† |†††††††††††††††††††††† |<-- †††† (credit window)††††††††††† †††††† -->|

††††††††††† |†††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† |

††††††††††† | <--†††† (latest advertised window size)††††††††††††† †††††† -->|

††††††††††† |†††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††††† |

††††††††††† |<--†††† (current congestion window size)††††† -->|

††††††††††† |†††††††††††††††††††††† |†††††††††††††††††††††††††††††††††††††††††††††† |

††††††††††† |†††††††††††††††††††††† |<--(effective window size)-->|


TCPís effective window is


††††††††††† WS = min(CongestionWindow, AdvertisedWindow)

††††††††††† EffectiveWindowSize = WS - (last byte ACKed - last byte sent)


The advertised window is sent by the receiving size and indicates the receiverís (known) ability to accept bytes of data.The congestion window size must be learned from the network.


††††††††††† In a network architecture like SNA individual routers can inform the destination or source directly that they are experiencing congestion, and hence cause the sender to reduce its effective window size.TCP assumes only the internet protocol of ďbest effort serviceĒ and must infer that congestion on the path between the source and destination is occurring when timeouts occur.TCP has the following goals:

††††††††††† A) maximize throughput

††††††††††† B) prevent the persistence of congestion

††††††††††† C) react quickly to changing conditions


To achieve goal A, TCP will attempt to increase its effective window size to the capacity of the destination to receive (Advertised Window Size), however, to achieve B it may have to lower its window size down to a minimum.(1 MSS -- maximum segment size (in bytes))


Additive Increase -- Multiplicative Decrease


††††††††††† A} Each time a timeout occurs, the source set the Congestion Window Size (CWS)

††††††††††† ††††† to Ĺ its current value.

††††††††††† B} Every time the source sends a CWS of packets it increments CWS by 1 (MSS)


Slow Start


††††††††††† A} Set Congestion Window Size (CWS) to 1 MSS (1 packet)

††††††††††† B) When an ACK returns, increase CWS by 1 packet


††††††††††† Therefore, every RTT the effective window size is doubled (up to a maximum)


††††††††††† C) When a timeout occurs, set the the target CWS to Ĺthe current CWS

††††††††††† D) Restart the transmission using slow start up to the target CWS and

††††††††††† †††† additive increase thereafter.


Fast Retransmit - Fast Recovery


††††††††††† A) Attempt to retransmit before timeout.

††††††††††††††††††††††† When Receiver gets packet out of sequence, it resends ACK of last packet

††††††††††††††††††††††††††††††††††† received in sequence for each new (out of sequence) packet that arrives.

††††††††††††††††††††††† When send receives 3 consecutive duplicate ACKs, it assumes next packet

††††††††††††††††††††††† †††††††††† is lost and retransmits.(the sender uses slow start -- as if a timeout

††††††††††††††††††††††††††††††††††† caused the retransmission.)

††††††††††† ††††††††††† Receiver buffers out of sequence packets and sends a cumulative ACK

††††††††††† B) With Fast Recovery, slow start only occurs when a connection is established

††††††††††† †††† and when a timeout occurs.Additive increase/multiplicative decrease is used

††††††††††† †††† at all other times. (Specifically, when a fast retransmit occurs, the CWS is

††††††††††† †††† halved, and additive increase is used to increase the window again.)


††††††††††† (Note-- the fact that duplicate ACKs arrive at the sender means the rest of the

††††††††††† packets are getting through. If multiple packets are lost, timeouts are likely

††††††††††† and the time before the next retransmission is longer and slow start will occur,

††††††††††† which will ease the load on the internet. connection.)†††


2. Congestion Avoidance


††††††††††† A) DECbit

††††††††††††††††††††††† If a router is experiencing moderate congestion (average queue length = 1),

††††††††††††††††††††††† it sets a congestion bit to 1.The destination host copies this congestion bit

††††††††††††††††††††††† with the ACK that it sends back to the source.The source determines what

††††††††††††††††††††††† fraction of its CWS of packets return ACKs with a congestion bit set, and

††††††††††††††††††††††† increases CWS by 1 if this number is less than 50%.If it is more than 50%

††††††††††††††††††††††† it decreases CWS by a factor of 0.875 * the current value.


††††††††††† B) RED Gateways

††††††††††††††††††††††† Implicitly let the source know that a router is becoming congested by

††††††††††† ††††††††††† dropping one of its packets.The formula for deciding when to drop a

††††††††††††††††††††††† packet is somewhat complicated.


††††††††††††††††††††††† 1) Compute average queue length --


††††††††††††††††††††††††††††††††††† AveLen = (1 - Weight) * AveLen + Weight * SampleLen

††††††††††††††††††††††††††††††††††††††††††††††† where†† 0 < Weight < 1


††††††††††††††††††††††† 2) Determine whether to queue or drop the packet


††††††††††††††††††††††††††††††††††† If (AveLen £ MinThreshold)

††††††††††††††††††††††††††††††††††††††††††††††† queue the packet

††††††††††††††††††††††††††††††††††† If (MinThreshold < AveLen < MaxThreshold)

††††††††††††††††††††††††††††††††††††††††††††††† calculate probability P

††††††††††††††††††††††††††††††††††††††††††††††† drop packet with probability P

††††††††††††††††††††††††††††††††††† If (MaxThreshold £ AveLen)

††††††††††††††††††††††††††††††††††††††††††††††† drop packet


††††††††††††††††††††††† 3) Determine the probability P


††††††††††††††††††††††††††††††††††† TempP = MaxP * (AveLen - MinThrshld)/(MaxThrshld - MinThrshld)

††††††††††††††††††††††††††††††††††† P = TempP / (1 - count * TempP)

††††††††††††††††††††††††††††††††††††††††††††††† where count = number of newly arriving pkts queued

††††††††††††††††††††††† (Note! Constants are set by simulation and experience to maximize power)


††††††††††††††††††††††††††††††††††† power = Throughput / Delay


††††††††††† C) TCP Vegas


††††††††††††††††††††††† 1) Calculate the difference between the expected rate and the actual rate --


††††††††††††††††††††††††††††††††††† ExpectedRate = CWS / BaseRTT

††††††††††††††††††††††††††††††††††††††††††††††† where BaseRTT is the smallest RTT measured

††††††††††††††††††††††††††††††††††††††††††††††† (assumes no congestion)

††††††††††††††††††††††††††††††††††† Actual Rate = number of bytes sent between the transmission of

††††††††††††††††††††††††††††††††††††††††††††††† a distinguished packet and the return of its ACK divided

††††††††††††††††††††††††††††††††††††††††††††††† by the Sample RTT

††††††††††††††††††††††††††††††††††† Sample RTT = time between the sending of a distinguished

††††††††††††††††††††††††††††††††††††††††††††††† packet and receipt of its ACK

††††††††††††††††††††††††††††††††††† Diff = ActualRate - ExpectedRate (always 0)


††††††††††††††††††††††† 2) Adjust CWS


††††††††††††††††††††††††††††††††††† If Diff < athen

††††††††††††††††††††††††††††††††††††††††††††††† increase CWS linearly during next RTT

††††††††††††††††††††††††††††††††††† If(a<Diff <b)

††††††††††††††††††††††††††††††††††††††††††††††† do nothing

††††††††††††††††††††††††††††††††††† If (Diff > b)

††††††††††††††††††††††††††††††††††††††††††††††† decrease CWS linearly during next RTT


3. Determining RTT



††††††††††††††† A) Karn/Partridge --


††††††††††††††††††††††† EstimatedRTT =a * EstimatedRTT + (1 -a) * SampleRTT

††††††††††††††††††††††† TimeOut = 2 * EstimatedRTT


††††††††††††††††††††††† Donít count retransmissions in the sample RTT


††††††††††† B) Jacobson/Karels --


††††††††††††††††††††††† Donít count retransmissions in the sample RTT

††††††††††††††††††††††† Diff = SampleRTT - EstimatedRTT

††††††††††††††††††††††† EstimatedRTT = EstimatedRTT + d* Diff

††††††††††††††††††††††† †††††††††††††††††††††† where 0 < d < 1

††††††††††††††††††††††† Deviation = Deviation +d * (Diff - Deviation)

††††††††††††††††††††††† TimeOut =m* EstimatedRTT + j * Deviation

††††††††††††††††††††††††††††††††††† where by experience m = 1 andj = 4