Data_Link_Layer sliding window ppt

Data Link Layer : 

Networks: Data Link Layer 1 Data Link Layer

Data Link Layer : 

Networks: Data Link Layer 2 Data Link Layer Provides a well-defined service interface to the network layer. Determines how the bits of the physical layer are grouped into frames (framing). Deals with transmission errors (CRC and ARQ). Regulates the flow of frames. Performs general link layer management.

Slide 3: 

Networks: Data Link Layer 3 1 2 Physical layer entity Data link layer entity 3 Network layer entity Physical Layer Data link Layer Physical Layer Data link Layer A B A B Packets Packets Frames (a) (b) Figure 5.2 Leon-Garcia & Widjaja: Communication Networks Copyright ©2000 The McGraw Hill Companies

Slide 4: 

Networks: Data Link Layer 4 1 2 3 4 5 Data Data Data Data ACK/NAK ACK/NAK ACK/NAK ACK/NAK Figure 5.7 End to End Hop by Hop Leon-Garcia & Widjaja: Communication Networks Copyright ©2000 The McGraw Hill Companies

Tanenbaum’s Data Link Treatment : 

Networks: Data Link Layer 5 Tanenbaum’s Data Link Treatment Concerned with communication between two adjacent nodes in the subnet (node to node). Assumptions: Bits delivered in the order sent. Rigid interface between the HOST and the node  the communications policy and the Host protocol (with OS effects) can evolve separately. uses a simplified model.

Slide 6: 

Networks: Data Link Layer 6 Host A Host B Layer 4 Node 2 Node 1 Layer 4 Layer 2 frame Data Link Layer Model Assume Host has infinite supply of messages. Node constructs frame from a single packet message. Checksum is automatically appended in the hardware. Protocols are developed in increasing complexity to help students understand the data link layer issues.

Slide 7: 

Networks: Data Link Layer 7 Packet sequence Error-free packet sequence Information frames Control frames Transmitter Receiver CRC Information packet Station A Station B Information Frame Control frame CRC Header Figure 5.8 Leon-Garcia & Widjaja: Communication Networks Copyright ©2000 The McGraw Hill Companies Basic Elements of ARQ

Tanenbaum’s Protocol Definitions : 

Networks: Data Link Layer 8 Tanenbaum’s Protocol Definitions Continued  Figure 3-9. Some definitions needed in the protocols to follow. These are located in the file protocol.h.

Protocol Definitions(continued.) : 

Networks: Data Link Layer 9 Protocol Definitions(continued.) Figure 3-9. Some definitions needed in the protocols to follow. These are located in the file protocol.h.

Slide 10: 

Networks: Data Link Layer 10 ack seq kind info buffer physical layer network layer data link layer frame packet

Figure 3-10.Unrestricted Simplex Protocol : 

Networks: Data Link Layer 11 Figure 3-10.Unrestricted Simplex Protocol

Figure 3-11. Simplex Stop-and-Wait Protocol : 

Networks: Data Link Layer 12 Figure 3-11. Simplex Stop-and-Wait Protocol

Slide 13: 

Networks: Data Link Layer 13 (a) Frame 1 lost A B frame 0 frame 1 ACK frame 1 ACK time Time-out frame 2 (b) ACK lost A B frame 0 frame 1 ACK frame 1 ACK time Time-out frame 2 ACK In parts (a) and (b) transmitting station A acts the same way, but part (b) receiving station B accepts frame 1 twice. Figure 5.9 Ambiguities with Stop-and-Wait [unnumbered frames] Leon-Garcia & Widjaja: Communication Networks Copyright ©2000 The McGraw Hill Companies

Slide 14: 

Networks: Data Link Layer 14 Transmitter Receiver Slast Rnext 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 (0,0) (0,1) (1,0) (1,1) Timer Global State: (Slast, Rnext) Error-free frame 0 arrives at receiver ACK for frame 0 arrives at transmitter ACK for frame 1 arrives at transmitter Error-free frame 1 arrives at receiver Station A Station B Rnext Slast Figure 5.11 Leon-Garcia & Widjaja: Communication Networks Copyright ©2000 The McGraw Hill Companies State Machine for Stop-and-Wait

Protocol 3(PAR) Positive ACKwith Retransmission[Old Tanenbaum Version] : 

Networks: Data Link Layer 15 #define MAX_SEQ 1 typedef enum {frame_arrival, cksum_err, timeout} event_type; include “protocol.h” void sender_par (void) { seq_nr next_frame_to_send; frame s; packet buffer; event_type event; next_frame_to_send = 0; from_network_layer (&buffer); while (true) { s.info = buffer; s.seq = next_frame_to_send; to_physical_layer (&s); start_timer (s.seq); wait_for_event(&event); if (event == frame_arrival) { from_network_layer (&buffer); inc (next_frame_to_send); } } } Protocol 3(PAR) Positive ACKwith Retransmission[Old Tanenbaum Version]

Slide 16: 

Networks: Data Link Layer 16 void receiver_par (void) { seq_nr next_frame_to_send; frame r, s; event_type event; frame_expected = 0; while (true) { wait_for_event (&event); if (event == frame_arrival) { from_physical_layer (&r); if (r.seq == frame_expected) { to_network_layer(&r.info); inc (frame_expected); } to_physical_layer (&s); /* Note – no sequence number on ACK */ } } } Protocol 3(PAR) Positive ACKwith Retransmission[Old Tanenbaum Version]

Slide 17: 

Networks: Data Link Layer 17 A B frame 0 frame 0 ACK frame 1 ACK time time-out frame 2 Transmitting station A misinterprets duplicate ACKs Figure 5.10 Leon-Garcia & Widjaja: Communication Networks Copyright ©2000 The McGraw Hill Companies PAR [OLD] problem Ambiguities when ACKs are not numbered

Simplex Protocol for a Noisy Channel : 

Networks: Data Link Layer 18 Simplex Protocol for a Noisy Channel Figure 3-12.A positive acknowledgement with retransmission protocol. Continued 

A Simplex Protocol for a Noisy Channel : 

Networks: Data Link Layer 19 A Simplex Protocol for a Noisy Channel Figure 3-12.A positive acknowledgement with retransmission protocol.

Sliding Window Protocols[Tanenbaum] : 

Networks: Data Link Layer 20 Sliding Window Protocols[Tanenbaum] Must be able to transmit data in both directions. Choices for utilization of the reverse channel: mix DATA frames with ACK frames. Piggyback the ACK Receiver waits for DATA traffic in the opposite direction. Use the ACK field in the frame header to send sequence number of frame being ACKed.  better use of the channel capacity.

Sliding Window Protocols : 

Networks: Data Link Layer 21 Sliding Window Protocols ACKs introduce a new issue – how long does receiver wait before sending ONLY an ACK frame. We need an ACKTimer!! sender timeout period needs to set longer. The protocol must deal with the premature timeout problem and be “robust” under pathological conditions.

Slide 22: 

Networks: Data Link Layer 22

Sliding Window Protocols : 

Networks: Data Link Layer 23 Sliding Window Protocols Each outbound frame must contain a sequence number. With n bits for the sequence number field, maxseq = 2n - 1 and the numbers range from 0 to maxseq. Sliding window :: sender has a window of frames and maintains a list of consecutive sequence numbers for frames that it is permitted to send without waiting for ACKs. receiver has a window that is a list of frame sequence numbers it is permitted to accept. Note – sending and receiving windows do NOT have to be the same size. Windows can be fixed size or dynamically growing and shrinking.

Sliding Window Protocols : 

Networks: Data Link Layer 24 Sliding Window Protocols Host is oblivious, message order at transport level is maintained. sender’s window :: frames sent but not yet ACKed. new packets from the Host cause the upper edge inside sender window to be incremented. ACKed frames from the receiver cause the lower edge inside window to be incremented.

Sliding Window Protocols : 

Networks: Data Link Layer 25 Sliding Window Protocols All frames in the sender’s window must be saved for possible retransmission and we need one timer per frame in the window. If the maximum sender window size is B, the sender needs B buffers. If the sender window gets full (i.e., reaches its maximum window size, the protocol must shut off the Host (the network layer) until buffers become available.

Sliding Window Protocols : 

Networks: Data Link Layer 26 Sliding Window Protocols receiver window Frames received with sequence numbers outside the receiver window are not accepted. The receiver window size is normally static. The set of acceptable sequence numbers is rotated as “acceptable” frames arrive. a receiver window size = 1  the protocol only accepts frames in order. There is referred to as Go Back N.

Slide 27: 

Networks: Data Link Layer 27 Standard Ways to ACK ACK sequence number indicates the last frame successfully received. - OR - 2. ACK sequence number indicates the next frame the receiver expects to receive. Both of these can be strictly individual ACKs or represent cumulative ACKing. Cumulative ACKing is the most common technique.

Slide 28: 

Networks: Data Link Layer 28 A B fr 0 time fr 1 fr 2 fr 3 fr 4 fr 5 fr 6 fr 3 ACK1 error Out-of-sequence frames Go-Back-4: 4 frames are outstanding; so go back 4 fr 5 fr 6 fr 4 fr 7 fr 8 fr 9 ACK2 ACK3 ACK4 ACK5 ACK6 ACK7 ACK8 ACK9 Figure 5.13 Leon-Garcia & Widjaja: Communication Networks Copyright ©2000 The McGraw Hill Companies Go Back N ACKing next frame expected

Slide 29: 

Networks: Data Link Layer 29 A B fr 0 time fr 1 fr 2 fr 3 fr 4 fr 5 fr 1 fr 2 ACK1 error Out-of-sequence frames Go-Back-7: fr 4 fr 5 fr 3 fr 6 fr 7 fr 0 NAK1 ACK3 ACK4 ACK5 ACK6 ACK7 ACK2 Transmitter goes back to frame 1 Figure 5.17 Go Back N with NAK error recovery Leon-Garcia & Widjaja: Communication Networks Copyright ©2000 The McGraw Hill Companies

Slide 30: 

Networks: Data Link Layer 30

Slide 31: 

Networks: Data Link Layer 31

Slide 32: 

Networks: Data Link Layer 32 A B fr 0 time fr 1 fr 2 fr 3 fr 4 fr 5 fr 6 fr 2 ACK1 error fr 8 fr 9 fr 7 fr 10 fr 11 fr 12 ACK2 NAK2 ACK7 ACK8 ACK9 ACK10 ACK11 ACK12 ACK2 ACK2 ACK2 Figure 5.21 Selective Repeat with NAK error recovery Leon-Garcia & Widjaja: Communication Networks Copyright ©2000 The McGraw Hill Companies

Slide 33: 

Networks: Data Link Layer 33

Slide 34: 

Networks: Data Link Layer 34