]> git.meshlink.io Git - utcp/blob - README
Fix a memory leak.
[utcp] / README
1 This is a light-weight, user-space implementation of RFC 793 (TCP), without any
2 reliance on an IP layer.  It can be used to provide multiple in-order, reliable
3 streams on top of any datagram layer.
4
5 UTCP does not rely on a specific event system. Instead, the application feeds
6 it with incoming packets using utcp_recv(), and outgoing data for the streams
7 using utcp_send(). Most of the rest is handled by callbacks. The application
8 must however call utcp_timeout() regularly to have UTCP handle packet loss.
9
10 The application should run utcp_init() for every peer it wants to communicate
11 with.
12
13 DIFFERENCES FROM RFC 793:
14
15 * No checksum. UTCP requires the application to handle packet integrity.
16 * 32-bit window size. Big window sizes are the default.
17 * No ECN, PSH, URG
18
19 TODO v1.0:
20
21 * Implement send buffer
22 * Window scaling
23 * Handle retransmission
24   - Proper timeout handling
25
26 TODO v2.0:
27
28 * Nagle (add PSH back to signal receiver that now we want an immediate ACK?)
29 * NAK and SACK
30 * Congestion window scaling
31 * Timestamps?
32
33 Future ideas:
34
35 Fast open:
36         SYN + data?
37
38 Receive-only open:
39         SYN|FIN
40
41 Fast transaction:
42         SYN|FIN + request data ->
43         <- SYN|ACK|FIN + response data
44         ACK ->
45
46 Does this need special care or can we rely on higher level MACs?
47
48 RFCs
49 ----
50
51 793  Transmission Control Protocol (Functional Specification)
52 2581 TCP Congestion Control
53 2988 Computing TCP's Retransmission Timer
54
55
56
57 INVARIANTS
58 ----------
59
60 - snd.una: the sequence number of the first byte we did not receive an ACK for
61 - snd.nxt: the sequence number of the first byte after the last packet we sent (due to retransmission, this may go backwards)
62 - snd.wnd: the number of bytes we have left in our (UTCP/application?) input buffer
63 - snd.last: the sequence number of the last byte that was enqueued in the TCP stream (increases only monotonically)
64
65 - rcv.nxt: the sequence number of the first byte after the last one we passed up to the application
66 - rcv.wnd: the number of bytes the receiver has left in its input buffer (may be more/less than our send buffer size)
67
68 - The only packets that do not have ACK set must either have SYN or RST set
69 - Only packets received with rcv.nxt <= hdr.seq <= rcv.nxt + rcv.wnd are valid, drop others.
70 - If it has ACK set, and it's higher than snd.una, update snd.una.
71   But don't update it past c->snd.next. (RST in that case?)
72
73 - SYN and FIN each count as one byte for the sequence numbering, but no actual byte is transferred in the payload.
74
75 CONNECTION TIMEOUT
76 ------------------
77
78 This timer is intended to catch the case when we are waiting very long for a response but nothing happens.
79 The timeout is in the order of minutes.
80
81 - The conn timeout is set whenever there is unacknowledged data, or when we are in the TIME_WAIT status.
82 - If snd.una is advanced while the timeout is set, we re-set the timeout.
83 - If the conn timeout expires, close the connection immediately.
84
85 RETRANSMIT TIMEOUT
86 ------------------
87
88 (See RFC 6298.)
89
90 This timer is intended to catch the case where we didn't get an ACK from the peer.
91 In principle, the timeout should be slightly longer than the maximum latency along the path.
92
93 - The rtrx timer is set whenever we send a packet that must be ACKed by the peer:
94   - when it contains data
95   - when SYN or FIN is set
96 - The rtrx timer is reset when we receive a packet that advances snd.una.
97   - it is cleared when snd.una == snd.last
98   - otherwise the timeout is set to the value of utcp->rto
99 - If the rtrx timer expires, retransmit at least one packet, multiply the timeout by two, and rearm the timeout.
100
101 The value of RTO is calculated according to the RFC. At the moment, no
102 timestamps are added to packets. When the RTT timer is not set, start it when
103 sending a packet. When the ACK arrives, stop the timer and use the time
104 difference as a measured RTT value.  Use the algorithm from RFC 6298 to update
105 RTO.
106
107 STATES
108 ------
109
110 CLOSED: this connection is closed, all packets received will result in RST.
111   RX: RST
112   TX: return error
113   RT: clear timers
114   RST: ignore
115
116 LISTEN: (= no connection yet): only allow SYN packets, it application does not accept, return RST|ACK, else SYN|ACK.
117   RX: on accept, send SYNACK, go to SYN_RECEIVED
118   TX: cannot happen
119   RT: cannot happen
120   RST: ignore
121
122 SYN_SENT: we sent a SYN, now expecting SYN|ACK
123   RX: must be valid SYNACK, send ACK, go to ESTABLISHED
124   TX: put in send buffer (TODO: send SYN again with data?)
125   RT: send SYN again
126
127 SYN_RECEIVED: we received a SYN, sent back a SYN|ACK, now expecting an ACK
128   RX: must be valid ACK, go to ESTABLISHED
129   TX: put in send buffer (TODO: send SYNACK again with data?)
130   RT: send SYNACK again
131
132 ESTABLISHED: SYN is acked, we can now send/receive normal data.
133   RX: process data, return ACK. If FIN set, go to CLOSE_WAIT
134   TX: put in send buffer, segmentize and send
135   RT: send unACKed data again
136
137 FIN_WAIT_1: we want to close the connection, and just sent a FIN, waiting for it to be ACKed.
138   RX: process data, return ACK. If our FIN is acked, go to FIN_WAIT_2, if a FIN was also received, go to CLOSING
139   TX: return error
140   RT: send unACKed data or else FIN again
141
142 FIN_WAIT_2: our FIN is ACKed, just waiting for more data or FIN from the peer.
143   RX: process data, return ACK. If a FIN was also received, go to CLOSING
144   TX: return error
145   RT: should not happen, clear timeouts
146
147 CLOSE_WAIT: we received a FIN, we sent back an ACK
148   RX: only return an ACK.
149   TX: put in send buffer, segmentize and send
150   RT: send unACKed data again
151
152 CLOSING: we had already sent a FIN, and we received a FIN back, now waiting for it to be ACKed.
153   RX: if it's ACKed, set conn timeout, go to TIME_WAIT
154   TX: return an error
155   RT: send unACKed data or else FIN again
156
157 LAST_ACK: we are waiting for the last ACK before we can CLOSE
158   RX: if it's ACKed, go to CLOSED
159   TX: return an error
160   RT: send FIN again
161
162 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.
163   RX: if we receive anything, reset conn timeout.
164   TX: return an error
165   RT: should not happen, clear rtrx timeout
166
167 SEND PACKET
168 -----------
169
170 - Put the packet in the send buffer.
171 - Decide how much to send:
172   - Not more than receive window allows
173   - Not more that congestion window allows
174 - Segmentize and send the packets
175 - At the end, snd.nxt is advanced with the number of bytes sent
176 - Set the rtrx and conn timers if they have not been set
177
178 RETRANSMIT
179 ----------
180
181 - Decide how much to send:
182   - Not more than we have in the send buffer
183   - Not more than receive window allows
184   - Not more that congestion window allows
185 - Segmentize and send packets
186 - No advancement of sequence numbers happen
187 - Reset the rtrx timers
188
189 RECEIVE PACKET
190 --------------
191
192 1 Drop invalid packets:
193   a Invalid flags or state
194   b ACK always set
195   c hdr.seq not within our receive window
196   d hdr.ack ahead of snd.nxt or behind snd.una
197 2 Handle RST packets
198 3 Advance snd.una?
199   a reset conn timer if so
200   b check if our SYN or FIN has been acked
201   c check if any data been acked
202     - remove ACKed data from send buffer
203     - increase cwnd
204   d no advance? NewReno
205 4 If snd.una == snd.nxt, clear rtrx and conn timer
206 5 Process state changes due to SYN
207 6 Send new data to application
208 7 Process state changes due to FIN
209
210 CONGESTION AVOIDANCE
211 --------------------
212
213 We want to send as much packets as possible that won't cause any packets to be
214 dropped.  So we should not send more than the available bandwidth, and not more
215 in one go than buffers along the path can handle.
216
217 To start, we use "self-clocking". We send one packet, and wait for an ACK
218 before sending another packet. On a network with a finite bandwidth but zero
219 delay (latency), this will send packets as efficiently as possible. We don't
220 need any timers to control the outgoing packet rate, that's why we call this
221 self-clocked. However, latency is non-zero, and this means a number of packets
222 is always on the way between the sender and receiver. The amount of packets
223 "inbetween" is in principle the bandwidth times the delay (bandwidth-delay
224 product, or BDP).
225
226 Delay is fairly easy to measure (equal to half the round-trip time of a packet,
227 which in TCP is easily obtained from the SYN and SYNACK pair, or the ACK in
228 response of a segment), however bandwidth is more difficult and might change
229 more rapidly than the latency.
230
231 Back to the "inbetween" packets: ideally we would like to fill the available
232 inbetween space completely. It should be easy to see that in that case,
233 self-clocking will still work as intended. Our estimate of the amount of
234 packets in the inbetween space is called the congestion window (CWND).  If we
235 know the BDP, we can set the CWND to it, however if we don't know it, we can
236 start with a small CWND and gradually increase it (for example, every time we
237 receive an ACK, send the next 2 segments). At some point, we will start sending
238 at a higher rate than the available bandwidth, in which case packets will
239 inevitably be lost. We detect that because we do not receive an ACK for our
240 data, and then we have to reduce the CWND (for example, by half).
241
242 The trick is to choose an algorithm that best keeps the CWND to the effective
243 BDP.
244
245 A nice introduction is RFC 2001.
246
247 snd.cwnd: size of the congestion window.
248 snd.nxt - snd.una: number of unacknowledged bytes, = number of bytes in flight.
249 snd.cwnd - (snd.nxt - snd.una): unused size of congestion window