【正文】 If error, the buffer does not hold a valid cell, all the bits are shift right one bit 187。 Check HEC 187。 Add the constant 01010101 to the remainder ? How to locate the cell boundaries in the ining bit stream? – Using HEC 187。 Save time – Procedure 187。 ATM was designed for use over fiber, and fiber is highly reliable 187。Corresponding to OSI Physical layer – TC (Transmission Convergence，傳輸聚合 ) 187。 phaseout A formal standard。 UA (Unnumbered Acknowledgement): ACK of control frames 187。 SABM (Set Asynchronous Balanced Mode): Connecting – PeertoPeer 187。 DISC (Disconnect): Announcing it is going down 187。 – One of the enabled transitions is fired: the tokens in all of the input places are removed。 States: represented as nodes 187。Retransmit only the timeout frame, not all the other outstanding frames. Ch. 3 Data Link Layer 41 A Protocol Using Go Back n (3) ? GoBackN – ? no need for receiver buffer – ? unnecessary retransmission 1. Frame 2 in error 2. Frame 2 times out 3. Frame 2 ~ 8 retransmitted ? ? ? Ch. 3 Data Link Layer 42 A Protocol Using Selective Repeat ? Selective Repeat – ? No unnecessary retransmission – ? Receiver buffer is needed 1. Frame 2 in error 2. Frame 2 times out 3. Frame 2 retransmitted ? ? ? Ch. 3 Data Link Layer 43 Protocol Specification and Verification ? Finite State Machine Models ? Petri Net Models Ch. 3 Data Link Layer 44 Finite State Machine (1) ? Finite State Machine (FSM) – FSM (Sender or Receiver) is in one of the states at any instant – Only a finite number of states are allowed. – When an event (事件 ) occurs, FSM may go from one state to another state (socalled transition) 。Pipelining (管線法 ) ? Allowing the sender to transmit up to w frames before blocking (without being ACKed), instead of just 1. ? Maximum allowable window size = w ↑ Data 0 20 250 Data ↑ 270 ACK ↓ 520 ↓ ACK Q: In 520ms, only one data frame is transmitted? A: Pipelining Ch. 3 Data Link Layer 40 A Protocol Using Go Back n (2) ? Pipelining frames over an unreliable channel raises serious issues. – When the sender recognizes that one frame is damaged or lost (. time out), there are several frames already been sent. How does the sender retransmit? (1) GoBackN (回到 N) 187。A data frame 20ms 187。Selective Repeat ? Window Size ≒ 2n1 (. n=3 ? 4) ? On receiving a frame: – If SN [lies within the window] but [is not equal to the Leading Edge] Store the frame in the buffer – If SN [equals to the Leading Edge] Deliver the frame and the kth consecutive frames in the buffer to the work layer Leading Edge? Leading Edge + k + 1 Trailing Edge? Trailing Edge + k + 1 (Forward the window by k + 1) Send PACK (SN + k) – the largest SN Ch. 3 Data Link Layer 37 Sliding Windows Protocols (7) ? 範例 – 3bit sequence number (0 ~7) – Maximum allowable sending window size = 7 (Stopandwait) = 4 (Go Back N) – Maximum allowable receiving window size = 1 (Stopandwait) = 4 (Go Back N) Ch. 3 Data Link Layer 38 A One Bit Sliding Window Protocol (1) ? One bit sequence number (0 and 1) ∴ Max Window = 1 (stopandwait) ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ ▲ (Duplicate) Normal ▲ ▲ (Delayed) (Timeout→ReTx) Ch. 3 Data Link Layer 39 A Protocol Using Go Back n (1) ? Transmission Delay vs. Bandwidth Utilization – For example 187。Next Frame Expected 187。 Remove the frame from the buffer ? Ch. 3 Data Link Layer 35 Sliding Windows Protocols (5) – Receiving Windows 187。The windows size is varying ? The initial windows size is set to 0 ? The maximum allowable window size is: – 2n 1 (GoBackN) – 2n /2 = 2n1 (Selective Repeat) – n=3 ? 7 (GoBackN) or 4 (Selective Repeat) Ch. 3 Data Link Layer 34 Sliding Windows Protocols (4) ? Leading edge: – When a frame is passed from the work layer ? Frame SN ? Leading Edge SN ? Leading Edge SN ? Leading Edge SN + 1 (forwarded by 1) ? Buffer and send the frame ? If the window size reaches the maximum allowable window size , close the work layer ? Trailing edge: – When an ACK with SN equal to the trailing edge: 187。Sequence Number: nbit field ( 0 ~ 2n1 ) – Sending Window 187。 Full duplex (全雙工 ) ? At the same time, . telephone and newer walkietalkie ? Piggybacking (搭便車 ) ACK – Put the ACK onto the next outgoing data frame in the opposite direction 187。 Data can be t