CMSC417 - Post midterm 2

What is the difference between PSH and URG

URG just says where some ‘important’ data ends, PSH actually makes it so this data is what will be delivered to the application next, not buffered.

What is the sliding window protocol?

Sliding Window Protocol allows sending multiple packets (a "window") before receiving acknowledgments. Used in both data link and TCP

What is the Stop and Wait protocol

The sender transmits one data frame at a time and then pauses for a period of time until it receives an acknowledgment (ACK) from the receiver. If the ACK is received, the sender proceeds with the next frame; otherwise, it retransmits the same frame

What is ARQ? What are the two types?

Automatic Repeat Request: The general strategy of using acknowledgments and timeouts to implement reliable delivery. The two types are Stop and Wait and Sliding Window

What is TCP wraparound?

When the number of possible sequence numbers is consumed so quickly that the possibility for a delayed packet from a previous ‘cycle’ could arrive and be misinterpreted as one from this cycle, if its sequence number happens to fall within the current window. This is possible on very high bandwidth connections, to consume all 2^32 numbers. A 1 GBps link takes only 17 seconds to do so. We use sequence numbers and timestamps to prevent this.

What variable is used in detecting duplicate packets? What does it track?

The last in-order byte received (by sequence number); packets with sequence numbers before this are duplicates.

What are three scenarios for TCP retransmission?

Packet loss, ACK loss, early timeout.

How does TCP set the timeout to retransmit?

As a function of RTT, \keeping a running average of the time it took to receive an ACK.

How does TCP transmit timestamps?

In the header there are two 4 byte values representing timestamps. The first represents the time the sender sent the packet. The second represents the copied value of the packet being ACKd (if the ack flag is set). So the receiver can check the time it sent compared to the time it receives.

How does TCP calculate RTT?

Using sampled RTTs from ACKs and smoothing them with an exponential weighted average.

How does network capability affect segment size decision for stop-and-wait? Formula?

Basically the utilization of the network in stop-and-wait is determined by the formula U = (L / R) / (RTT + L / R), this basically gives the portion of time we spend sending. L is length of segment sent, R is bandwidth. So the only thing a stop-and-wait can change is L. It would need to send enormous packets to be able to utilize the network well, but this would be impossible because of MTU’s and such.

What is pipelining?

Allowing multiple unacknowledged packets to be in flight simultaneously.

What is go back N?

Go-back-n is a strategy for pipelining and ensuring delivery. The sender will send n packets, and receiver will send only cumulative acks, meaning it only acks when everything up to that point has been received. The sender keeps track of just one timer to retransmit, and if it times out it will retransmit all unacknowledged packets.

What is duplicated ACK for?

Duplicate ACKs signal out-of-order delivery and can trigger early retransmission.

What is Selective retransmit?

Sender sends n packets, receiver acknowledges packets individually, sender must keep track of a timer for each packet, it only retransmits individual packets who have timed out.

How is advertised window field used? Formula? Why doesn’t it account for out-of-order received segments?

AdvertisedWindow = MaxRcvBuffer - ((NextByteExpected - 1) - LastByteRead). We don’t need to account for the out-of-order bytes received because from the sender’s end, it won’t send anything that’s larger than LastByteAckd + AdvertisedWindow anyway

How can deadlocks occur? How are they resolved?

If AdvertisedWindow is 0, then no data will be sent. This is a potential problem because ACKs are only guaranteed to be sent when data is received. So the sender will periodically send a packet with a single byte of data, which the receiver will have to respond to with an ACK. If any data has been read, then the AdvertisedWindow associated will be greater than zero, breaking the deadlock.

What is silly window?

Silly window syndrome is when we repeatedly send very small packets. This happens if the receiver’s advertised window gets small due to it recv’ing very slowly. If advertised window gets down to 1 byte, then sender might send a single byte in a packet. It might only recv 1 byte, then it will send advertised window to be 1 byte again. Until the receiver consumes data much quicker, it will not stop. The solution is either to have the sender not always send small packets (Nagle’s), or for the receiver to wait some time before ACK.

What is effective window formula/use?

EffectiveWindow = AdvertisedWindow - (LastByteSent - LastByteAcked), essentially it subtracts unacknowledged data that it sent from the window, it doesn’t want to needlessly retransmit.

How does MSS relate to advertised window?

If AdvertisedWindow < MSS, inefficient small packets may be sent.

What is the advertised window?

The amount of free buffer space a receiver tells the sender it has, communicated in ACK packets, telling the sender how many bytes it can send before needing an acknowledgment

What is MSS?

Maximum Sending Size: Defines the largest payload a packet can send

What are the two solutions to the silly window syndrom?

Receiver side approach: Delayed ACK

• Instead of immediately sending an ACK, the receiver will wait for a period of time.
  delay MUST be less than 0.5 seconds
  In a stream of full MSS sent then at least every other packet should be ACKd.

Sender side approach: Nagle’s Algorithm

• If window size >= MSS and available data >= MSS send immediately, else if unconfirmed data in the pipe wait for ACK, else send

What is the issue with using delayed ACK and Nagle’s algorithm at the same time

Using delayed ACK and Nagle’s algorithm together can cause unnecessary delays because both sides end up waiting on each other. Nagle’s algorithm causes the sender to buffer small packets until an ACK is received, while delayed ACK causes the receiver to wait before sending an ACK in hopes of acknowledging more data at once. If the sender sends a small packet and then waits for an ACK, and the receiver delays the ACK waiting for another packet, no further data is sent and the ACK is delayed until the timeout expires.

Original calculation to estimate RTT? Problems?

EstimatedRTT = α * EstimatedRTT + (1 - α) * SampleRTT.

α = Smoothing factor (recommended between 0.8 -0.9)
SampleRTT = measured round-trip time for a single segment
EstimatedRTT = a smoothed running average of RTT

The problem is sometimes SampleRTT is wrong! For example, if the sender has to retransmit, it will use the timestamp sent back to it by TCP for the ACK, but this could be the original packet being ACK'd or it could be the retransmit. If it’s the original, it’s gonna be way too big.

How is the TCP timeout value calculated?

Timeout = 2 * EstimatedRTT

What is the Karn/Partridge algorithm?

A solution to how EstimatedRTT is calculated. Stop measuring RTT when we retransmit, and start again after a regular transmit/ack. Also when there is a timeout set the next timeout to be twice this value.

What do resource flows compete over?

Link bandwidth AND queue space

What is congestion specifically?

When contention for resources leads toward queue build-ups and packet drops

Why is congestion possible?

Queue buildups when a router receives more packets than it can transmit

What is goodput?

The amount of application-level data successfully delivered over the network

What is the ‘knee’?

As ‘offered load’ increases, throughput will increase until the network gets congested. This point is the knee. After this, throughput may increase slightly, but eventually there will be a collapse where very little data actually gets delivered.

What danger of TCP does congestion introduce?

When segments don’t get acknowledged due to congestion, they are retransmitted which will only increase the congestion’s severity.

What is the simplest queue type?

Drop-tail FIFO. Drop tail meaning incoming packets are dropped if the queue is full and FIFO is First In, First Out.

How does TCP know there is delay?

Two ways, either timeout or Dup Ack. Dup Ack because it means one of the packets arrived out of order, the other one probably got dropped due to congestion

How is congestion at the link layer detected?

CSMA and collision detection

In CSMA/CD (Carrier Sense, Multiple Access with Collision Detect) networks, when multiple nodes transmit at the same time, their signals collide; detecting a collision indicates that the shared medium is being contended too heavily

How do we respond to congestion?

Basically we decrease the sending rate.

How does TCP detect lack of congestion?

When there are no drops.

What is the congestion window?

The congestion window is another limit on how much to send based on how much congestion we think is in the network

What is AIMD?

Additive increase multiplicative decrease

Why exponential decrease?

Because congestion is so dangerous, we need to be cautious and back off quickly.

What is slow-start?

Slow start is basically we do exponential increase only at first so that we can quickly get to the upper bound of the network’s capabilities. We double CWND (congestion window) once per RTT.

What is the difference between the advertised window in flow control and the congestion window?

The advertised window keeps a fast sender from overwhelming a slow receiver while the congestion window keeps a set of senders from overloading the network

How do responses to loss differ based on loss type in TCP?

Triple-dup ACK: If packet n is lost, but packets n+1, n+2, etc. arrive, then, sender quickly resends packet n and does a multiplicative decrease (usually just halves it) and keep going using additive increase instead of exponential

Timeout: the sender will set CWND to zero and do “slow start restart” instead.

What is slow start restart?

CWND is reset to zero and slow start begins again after timeout.

In what conditions is TCP slow-start used?

Start of connection, after timeout, or after long idle period.

What triggers CNWD updates in slow start? In regular phase? Formulas?

ACKs trigger updates. Slow start: CWND += 1 MSS. Congestion avoidance: CWND += MSS*(MSS/CWND).

What is slow start restart?

CWND is reset to zero and slow start begins again after timeout.

In what conditions is TCP slow-start used?

Start of connection, after timeout, or after long idle period.

What triggers CNWD updates in slow start? In regular phase? Formulas?

ACKs trigger updates. Slow start: CWND += 1 MSS. Congestion avoidance: CWND += MSS*(MSS/CWND)

Why would there be a straight horizontal line on the CWND/time graph?

No ACKs received, so CWND doesn’t change until timeout.

What is SSTHRESH/formula?

SSTHRESH is the point at which, during slow-start restart, we switch back to regular additive increase. It is half the previous CNWD before timeout.

Which TCP implementation first introduced congestion control, and how?

Tahoe introduced it first. After any loss, it went back to slow-start restart.

What improvement was made after Tahoe, and by who?

Reno made the next optimization, only on timeout we will do slow-start restart. On triple-dup ack we will just divide by 2 and continue with additive increase, also FR/FR

What is FR/FR? Who introduced it? How is it used now?

Basically we inflate the window size when we retransmit and deflate when we get the ACK we wanted.

What did Vegas introduce? What is ingress/egress?

Vegas introduced basically binary search using packet delay as a hint about congestion.

Ingress traffic refers to traffic that enters the network from the outside

Egress traffic is the traffic that leaves your network

What are the components of Queue management? Goals?

The components of queue management are drop policy and scheduling discipline. We want to balance throughput and delay.

What are the benefits/tradeoffs of bigger buffers?

If buffers are too big we won’t drop a lot but we will have long delays. If too small we will drop a lot.

What is the basic drop policy?

The basic queue management is FIFO with drop-tail.

However, this only gives information to end hosts when the router’s buffer is completely full, meaning many connections will suddenly back off at the same time (bursty loss). One solution is RED

What is bursty loss?

A situation in TCP congestion control where lost data packets occur in consecutive clumps or "bursts" due to a buffer being full

What is RED?

Random early detection. Basically we have a probability to randomly drop packets to signal congestion; this probability is set as a function of how full the buffer is. The more full the buffer, the more likely we are to drop packets. However, it’s difficult to ‘tune’ this just right, to not drop packets when there isn’t congestion, and to drop early enough to avoid problems when there is. There is BLUE which is self-tuning

What is ECN? Advantages/disadvantages?

ECN is Explicit Congestion Notification, set the ECN bit when there is congestion. This only informs the receiver of congestion, but the receiver will echo this bit back on its ACK packet.

What is Link scheduling?

The optimization that some ‘flows’ should have higher priority because they need low latency to work at all (video-streaming).

What is Strict priority?

A method that assigns absolute priority to certain data, ensuring high-priority packets (like voice/video) are always sent first, even if it means starving lower-priority traffic

What is weighted fair scheduling?

A fraction of the link bandwidth is dedicated to each flow depending on its priority. Sends extra traffic from one queue if others are idle. The downside is complexity of implementation.

What are the three TCP vulnerabilities and their countermeasures? 

Three: 

1. ACK division - because CWND is incremented only when we receive an ACK, you can split one ACK into multiple ACKs, and it will get incremented much faster. To combat, we can only increase CWND when receiver ACKs >= 1 segment. 

2. DupACK spoofing - Send a bunch of duplicate ACKs for the same number. This forces the sender into fast retransmit mode where it artificially inflates CWND by 1 MSS for each dupack received. To combat this, we can count outstanding packets and ignore extra ACKs. 

3. Optimistic ACKing - when receiving a packet, ACK the packet you expect the sender to send next. To combat this, we can randomize segment boundaries and ignore ACKs that don’t match a boundary. 

What are today’s TCP versions?

1. BIC - BIC considers available bandwidth as a search problem and basically uses binary search. We maintain a ‘max window’ and ‘min window’ variable, as well as ‘max increment’ and ‘min increment.’ As long as there is no packet loss, we set CNWD to be halfway between max and min window, updating min window to be CNWD. If CWND gets to be greater than WMax, we do cwnd += (cwnd - max window). Then, when there is packet loss, if CWND > max, max = CWND. Else, set it to CWND * (1 - constant / 2)

2. CUBIC - BIC still has room to improve, its function is too aggressive for low-bandwidth links. It uses the function cwnd = C(t - k)^3 + Wmax. C is a constant, t is time since the last window reduction, K is a value updated on recovery by the function K = cube_root(B * wMax / C). Wmax is just the CWND size right before the last time it was reduced. 

What are the responsibilities of the Link Layer?

Single hop addressing, MAC, single hop ack

What is promiscuous mode?

In ethernet it will accept all packets no matter the destination address, so it can snoop on traffic and such