Sack Implementation at PSC

• Activities in several areas:
  
  
  • Reference Implementation for NetBSD 1.1
    
    
  • Research Implementations for NetBSD 1.1 and Digital Unix 3.2c
    
    
• Changes for SACK are relatively straightforward
  
  
  • tcp.h
    
    
  • tcp_var.h
    
    
  • tcp_input.c
    
    
  • tcp_output.c
    
    

SACK Reference Implementation

• SACK_PERMITTED option is trivial
  
  
• SACK option has three main parts
  
  
  • SACK Generation (by receiver)
    
    
  • SACK Scoreboarding (by sender)
    
    
  • Sender retransmission and congestion control
    
    

SACK Generation

• Performed when adding segments to the TCP reassembly queue
  
  
• After adding a segment, scan the reassembly queue for the start and end of the contiguous block which holds the segment
  
  
• Store the block in a new data structure, sack_list
  
  
• Remove duplicate data within sack_list
  
  
• Remove blocks from sack_list as ACK advances
  
  
• In reference implementation, sack_list is just a short fixed length array kept in struct tcpcb
  
  
• In some cases, this may result in the receiver losing track of old SACK blocks
  
  
• From SACK I-D:
  
  
  • The first SACK block (i.e., the one immediately following the kind and length fields in the option) MUST specify the contiguous block of data containing the segment which triggered this ACK, unless that segment advanced the Acknowledgment Number field in the header. This assures that the ACK with the SACK option reflects the most recent state change at the
    
    data receiver.
  • The data receiver SHOULD include as many distinct SACK blocks as possible in the SACK option. Note that the maximum available option space may not be sufficient to report all
    
    blocks present in the receiver's queue.
  • The SACK option SHOULD be filled out by repeating the most recently reported SACK blocks (based on first SACK blocks in previous SACK options) that are not subsets of a SACK block already included in the SACK option being constructed. This assures that in normal operation every SACK block is repeated several times. (At least three times for large-window TCP implementations [RFC1323]).

SACK Scoreboarding

• Performed when a SACK option is received
  
  
• Blocks are added to a scoreboard data structure
  
  
• Scoreboard includes
  
  
  • Start and End of block
    
    
  • Information on segments which have been retransmitted
    
    
• An efficient scorboard implementation is still an open question
  
  
• In reference implementation, the scoreboard is just a fixed length array kept in struct tcpcb
  
  
• This has the unfortunate side effect that large, discontinuous losses, will overload the data structure, resulting in the loss of some SACK information
  
  
• From the I-D:
  
  
  • When receiving an ACK containing a SACK option, the data sender SHOULD record the selective acknowledgement for future reference. The data sender is assumed to have a retransmission queue that contains the segments that have been transmitted but not yet acknowledged, in sequence-number order. If the data sender performs re-packetization before retransmission, the block boundaries in a SACK option that it receives may not fall on boundaries of segments in the retransmission queue; however, this does not pose a serious difficulty for the sender.

SACK Retransmission and Congestion Control

• Test for retransmission remains dupacks >= tcprexmtthresh
  
  
• Change calls to tcp_output to specify segments known to be lost (per scoreboard)
  
  
• Mark retransmitted segments as such in the scoreboard
  
  
• Avoid "silly retransmissions", for example in telnet...
  
  
• Once all lost segments have been retransmitted, proceed with new data as permitted by congestion control
  
  
• Congestion control will be identical to Sally's algorith in ns
  
  
• From the I-D:
  
  
  • This document does not attempt to specify in detail the congestion control algorithms for implementations of TCP with SACK. However, the congestion control algorithms present in the de facto standard TCP implementations MUST be preserved [Stevens94]. In particular, to preserve robustness in the presence of packets reordered by the network, recovery is not triggered by a single ACK reporting out-of-order packets at the receiver. Further, during recovery the data sender limits the number of segments sent in response to each ACK. Existing implementations limit the data sender to sending one segment during Reno-style fast recovery, or to two segments during slow-start [Jacobson88]. Other aspects of congestion control, such as reducing the congestion window in response to congestion, must similarly be preserved.

SACK Research Implementations

• Existance of SACK is causing new congestion control research
  
  
• PSC is exploring more precise congestion control techniques during congestion via the FACK algorithm
  
  
• The FACK algorithm precisely estimates data outstanding in the network and more accurately regulates transmissions than current algorithms do
  
  
• At USC, Peter Danzig and Ya Xu are implementing SACK with the Vegas CAM algorithm
  
  
• Vegas CAM attempts to reduce congestion in the network during the "normal" part of TCP congestion avoidance through the use of delay sensing techniques