X-Git-Url: http://git.meshlink.io/?a=blobdiff_plain;f=README;h=9906a2c1eddc0ab865cdad234b5a54d03979b114;hb=7d8a65c11dd4b0555575ff75efab859236c4964f;hp=0f91f871c9eef353439f57f6dc21af9846ffe649;hpb=e5db16f2c3e5debdc60b129f8f271faa1c482959;p=utcp

diff --git a/README b/README
index 0f91f87..9906a2c 100644
--- a/README
+++ b/README
@@ -178,16 +178,61 @@ RETRANSMIT
 RECEIVE PACKET
 --------------
 
-- Drop invalid packets:
-  - Invalid flags or state
-  - ACK always set
-  - 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