Stop and Wait protocol Algorithm at sender(node A) (with initial condition SNEO 1) Accept packet from higher layer when available assign number sn to it 2) Transmit packet SN in frame with sequence SN 3 Wait for an error free frame from B if received and it contains rn>sn in the request#f field. set sn to rn and go to 1 if not received within given time, go to 2 Eytan modiano
Stop and Wait Protocol Algorithm at sender (node A) (with initial condition SN=0) 1) Accept packet from higher layer when available; assign number SN to it 2) Transmit packet SN in frame with sequence # SN 3) Wait for an error free frame from B i. if received and it contains RN>SN in the request # field, set SN to RN and go to 1 ii. if not received within given time, go to 2 Eyt an Modiano 6
Stop and wait Algorithm at receiver (node B) (with initial condition RN=O) Whenever an error-free frame is received from a with a sequence equal to RN, release received packet to higher layer and increment RN 2)At arbitrary times, but within bounded delay after receiving any error free frame from A, transmit a frame to a containing rn in the request field Eytan modiano
Stop and Wait Algorithm at receiver (node B) (with initial condition RN=0) 1) Whenever an error-free frame is received from A with a sequence # equal to RN, release received packet to higher layer and increment RN. 2) At arbitrary times, but within bounded delay after receiving any error free frame from A, transmit a frame to A containing RN in the request # field. Eytan Modiano 7
Correctness of stop wait with integer SN, RN Assume, for a to( from)B transmission, that All errors are detected as errors Initially no frames are on link, SN=0, RN=O Frames may be arbitrarily delayed or lost Each frame is correctly received with at least some probability q>0 Split proof of correctness into two parts SAFETY: show that no packet is ever released out of order or more than once LIVENESS: show that every packet is eventually released Eytan modiano
Correctness of stop & wait with integer SN, RN • Assume, for A to (from) B transmission, that – All error s are detected as errors – Initially no frames are on link, SN=0, RN=0 – Frames may be arbitrarily delayed or lost – E a ch frame is correctly recei ved with at least some probability q>0. • Split proof of correctness into two parts: – SAFETY: show that no packet i s ever r eleased out o f order o r m ore than once – LIVENESS: show that every packet is eventually released Eyt an Modiano 8
Safety No frames on link initially, packet 0 is first packet accepted at A, it is the only packet assigned SN=o, and must be the packet released by B if B ever releases a packet Subsequently(using induction) if b has released packets up to and including n-1, then rn is updated to n when n-1 is released, and only n can be released next Eytan modiano
Safety • No frames on link initially, packet 0 is first packet accepted at A, it is the only packet assigned SN=0, and must be the packet released by B if B ever releases a packet • Subsequently (using induction) if B has released packets up to and including n-1, then RN is updated to n when n-1 is released, and only n can be released next Eytan Modiano 9
LIVENESS Node a Node B Packets out t,= time at which A first starts to transmit packet t 2 =time at which B correctly receives releases i, and increases rn to i+1 t3 =time at which SN is increased to i+1 Will prove that t, <t2 <t3 <oo. = Liveness Eytan modiano
LIVENESS i i i i SN RN Node A Node B x i+1 x i+1 t t t 1 2 3 i Packets out i t1 = time at which A first starts to transmit packet i t2 = time at which B correctly receives & releases i, and increases RN to i+1 t3 = time at which SN is increased to i+1 Will prove that t1 < t2 < t3 < ∞. => Liveness Eytan Modiano 10