X-Git-Url: http://git.meshlink.io/?a=blobdiff_plain;f=README;h=9906a2c1eddc0ab865cdad234b5a54d03979b114;hb=5f80449794064756239fb6d0488d0324508f5e4b;hp=1c9baf62e2917fa1466b9f53bff1706fe9180988;hpb=bfde83247774e40b3d178852d286b00e6be75132;p=utcp diff --git a/README b/README index 1c9baf6..9906a2c 100644 --- a/README +++ b/README @@ -21,6 +21,7 @@ TODO v1.0: * Implement send buffer * Window scaling * Handle retransmission + - Proper timeout handling TODO v2.0: @@ -44,6 +45,15 @@ Fast transaction: Does this need special care or can we rely on higher level MACs? +RFCs +---- + +793 Transmission Control Protocol (Functional Specification) +2581 TCP Congestion Control +2988 Computing TCP's Retransmission Timer + + + INVARIANTS ---------- @@ -61,30 +71,87 @@ INVARIANTS - SYN and FIN each count as one byte for the sequence numbering, but no actual byte is transferred in the payload. +CONNECTION TIMEOUT +------------------ + +This timer is intended to catch the case when we are waiting very long for a response but nothing happens. +The timeout is in the order of minutes. + +- The conn timeout is set whenever there is unacknowledged data, or when we are in the TIME_WAIT status. +- If snd.una is advanced while the timeout is set, we re-set the timeout. +- If the conn timeout expires, close the connection immediately. + +RETRANSMIT TIMEOUT +------------------ + +(See RFC 2988, 3366) + +This timer is intended to catch the case where we didn't get an ACK from the peer. +In principle, the timeout should be slightly longer than the maximum latency along the path. + + +- The rtrx timeout is set whenever snd.nxt is advanced. +- If the rtrx timeout expires, retransmit at least one packet, and re-set the timeout. + STATES ------ -CLOSED: this connection is cloed, all packets received will result in RST. +CLOSED: this connection is closed, all packets received will result in RST. + RX: RST + TX: return error + RT: clear timers + RST: ignore LISTEN: (= no connection yet): only allow SYN packets, it application does not accept, return RST|ACK, else SYN|ACK. + RX: on accept, send SYNACK, go to SYN_RECEIVED + TX: cannot happen + RT: cannot happen + RST: ignore SYN_SENT: we sent a SYN, now expecting SYN|ACK + RX: must be valid SYNACK, send ACK, go to ESTABLISHED + TX: put in send buffer (TODO: send SYN again with data?) + RT: send SYN again SYN_RECEIVED: we received a SYN, sent back a SYN|ACK, now expecting an ACK + RX: must be valid ACK, go to ESTABLISHED + TX: put in send buffer (TODO: send SYNACK again with data?) + RT: send SYNACK again ESTABLISHED: SYN is acked, we can now send/receive normal data. + RX: process data, return ACK. If FIN set, go to CLOSE_WAIT + TX: put in send buffer, segmentize and send + RT: send unACKed data again FIN_WAIT_1: we want to close the connection, and just sent a FIN, waiting for it to be ACKed. + RX: process data, return ACK. If our FIN is acked, go to FIN_WAIT_2, if a FIN was also received, go to CLOSING + TX: return error + RT: send unACKed data or else FIN again -FIN_WAIT_2: FIXME +FIN_WAIT_2: our FIN is ACKed, just waiting for more data or FIN from the peer. + RX: process data, return ACK. If a FIN was also received, go to CLOSING + TX: return error + RT: should not happen, clear timeouts CLOSE_WAIT: we received a FIN, we sent back an ACK + RX: only return an ACK. + TX: put in send buffer, segmentize and send + RT: send unACKed data again CLOSING: we had already sent a FIN, and we received a FIN back, now waiting for it to be ACKed. + RX: if it's ACKed, set conn timeout, go to TIME_WAIT + TX: return an error + RT: send unACKed data or else FIN again LAST_ACK: we are waiting for the last ACK before we can CLOSE + RX: if it's ACKed, go to CLOSED + TX: return an error + RT: send FIN again TIME_WAIT: connection is in princple closed, but our last ACK might not have been received, so just wait a while to see if a FIN gets retransmitted so we can resend the ACK. + RX: if we receive anything, reset conn timeout. + TX: return an error + RT: should not happen, clear rtrx timeout SEND PACKET ----------- @@ -111,15 +178,61 @@ RETRANSMIT RECEIVE PACKET -------------- -- Drop invalid packets: - - Invalid flags or state - - hdr.seq not within our receive window - - hdr.ack ahead of snd.nxt -- Handle RST packets -- Advance snd.una? - - reset conn timer if so - - remove ACKed data from send buffer -- If snd.una == snd.nxt, clear rtrx and conn timer -- Process state changes due to SYN -- Send new data to application -- Process state changes due to FIN +1 Drop invalid packets: + a Invalid flags or state + b ACK always set + c hdr.seq not within our receive window + d hdr.ack ahead of snd.nxt or behind snd.una +2 Handle RST packets +3 Advance snd.una? + a reset conn timer if so + b check if our SYN or FIN has been acked + c check if any data been acked + - remove ACKed data from send buffer + - increase cwnd + d no advance? NewReno +4 If snd.una == snd.nxt, clear rtrx and conn timer +5 Process state changes due to SYN +6 Send new data to application +7 Process state changes due to FIN + +CONGESTION AVOIDANCE +-------------------- + +We want to send as much packets as possible that won't cause any packets to be +dropped. So we should not send more than the available bandwidth, and not more +in one go than buffers along the path can handle. + +To start, we use "self-clocking". We send one packet, and wait for an ACK +before sending another packet. On a network with a finite bandwidth but zero +delay (latency), this will send packets as efficiently as possible. We don't +need any timers to control the outgoing packet rate, that's why we call this +self-clocked. However, latency is non-zero, and this means a number of packets +is always on the way between the sender and receiver. The amount of packets +"inbetween" is in principle the bandwidth times the delay (bandwidth-delay +product, or BDP). + +Delay is fairly easy to measure (equal to half the round-trip time of a packet, +which in TCP is easily obtained from the SYN and SYNACK pair, or the ACK in +response of a segment), however bandwidth is more difficult and might change +more rapidly than the latency. + +Back to the "inbetween" packets: ideally we would like to fill the available +inbetween space completely. It should be easy to see that in that case, +self-clocking will still work as intended. Our estimate of the amount of +packets in the inbetween space is called the congestion window (CWND). If we +know the BDP, we can set the CWND to it, however if we don't know it, we can +start with a small CWND and gradually increase it (for example, every time we +receive an ACK, send the next 2 segments). At some point, we will start sending +at a higher rate than the available bandwidth, in which case packets will +inevitably be lost. We detect that because we do not receive an ACK for our +data, and then we have to reduce the CWND (for example, by half). + +The trick is to choose an algorithm that best keeps the CWND to the effective +BDP. + +A nice introduction is RFC 2001. + +snd.cwnd: size of the congestion window. +snd.nxt - snd.una: number of unacknowledged bytes, = number of bytes in flight. +snd.cwnd - (snd.nxt - snd.una): unused size of congestion window