Transcription
Data Link LayerNetworks: Data Link Layer1
Data Link Layer Provides a well-defined service interface to thenetwork layer. Determines how the bits of the physical layer aregrouped into frames (framing). Deals with transmission errors (CRC and ARQ). Regulates the flow of frames. Performs general link layer management.Networks: Data Link Layer2
(a)APacketsPacketsData linkLayerData linkLayerFramesPhysicalLayer(b)21 2312 12MediumA11 23B21Copyright 2000 The McGraw Hill Companies12 1Physical layer entity32BPhysicalLayerNetwork layer entityData link layer entityLeon-Garcia & Widjaja: Communication NetworksNetworks: Data Link LayerFigure 5.23
End to EndACK/NAK12Data3Data45DataDataHop by HopDataData12ACK/NAKFigure 5.7Data3ACK/NAKData4ACK/NAKLeon-Garcia & Widjaja: Communication NetworksNetworks: Data Link Layer5ACK/NAKCopyright 2000 The McGraw Hill Companies4
Tanenbaum’s Data Link LayerTreatment Concerned with communication between twoadjacent nodes in the subnet (node to node). Assumptions:– The bits are delivered in the order sent.– Rigid interface between the HOST and the nodeÎ the communications policy and the Hostprotocol (with OS effects) can evolve separately.– He uses a simplified model.Networks: Data Link Layer5
HostANode1LayerLayer44Layer 2frameHostBNode2Data Link Layer ModelAssume the sending Host has infinite supply of messages.A node constructs a frame from a single packet message.The CRC is automatically appended in the hardware.The protocols are developed in increasing complexity to helpstudents understand the data link layer issues.Networks: Data Link Layer6
Basic Elements of sequenceTransmitterReceiverStation AControlframesStation BCRCCRCInformationpacketHeaderHeaderControl frameInformation FrameCopyright 2000 The McGraw Hill CompaniesLeon-Garcia & Widjaja: Communication NetworksNetworks: Data Link LayerFigure 5.87
Tanenbaum’s Protocol DefinitionsContinued ÆFigure 3-9. Some definitions needed in the protocols tofollow. These are located in the file protocol.h.Networks: Data Link Layer8
ProtocolDefinitions(continued)Figure 3-9. Somedefinitions needed inthe protocols tofollow. These arelocated in the fileprotocol.h.Networks: Data Link Layer9
packetnetwork layerbufferframedata link layerinfoackseqkindphysical layerNetworks: Data Link Layer10
Figure 3-10UnrestrictedSimplexProtocolNetworks: Data Link Layer11
Figure 3-11SimplexStop-andWaitProtocolNetworks: Data Link Layer12
Ambiguities with Stop-and-Wait[unnumbered frames](a) Frame 1 lostATime-outtimeframe0frame1ACKB(b) ACK ame1ACKframe2ACKIn parts (a) and (b) transmitting station A acts the same way, but part (b)receiving station B accepts frame 1 twice.Copyright 2000 The McGraw Hill CompaniesLeon-Garcia & Widjaja: Communication NetworksNetworks: Data Link LayerFigure 5.913
State Machine for Stop-and-Wait01 01 01 0101 01 01 01RnextSlastTimerSlastTransmitterRnextStation A(0,0)Global State:(Slast, Rnext)ReceiverStation BError-free frame 0arrives at receiverACK forframe 1arrives attransmitterError-free frame 1arrives at receiver(1,0)Copyright 2000 The McGraw Hill CompaniesLeon-Garcia & Widjaja: Communication NetworksNetworks: Data Link Layer(0,1)ACK forframe 0arrives attransmitter(1,1)Figure 5.1114
#define MAX SEQ 1typedef 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]}}}Networks: Data Link Layer15
void receiver par (void){seq nr next frame to send;frame r, s;Protocol 3event type event;(PAR) Positive ACKframe expected 0;while (true)with Retransmission{ wait for event (&event);[Old Tanenbaum Version]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 */}}}Networks: Data Link Layer16
PAR [OLD] problemAmbiguities when ACKs are not e2Transmitting station A misinterprets duplicate ACKsCopyright 2000 The McGraw Hill CompaniesLeon-Garcia & Widjaja: Communication NetworksNetworks: Data Link LayerFigure 5.1017
PARSimplexProtocolfor aNoisyChannelCode addedFigure 3-12.A Positive Acknowledgement with Retransmission protocol.Networks: Data Link LayerContinued Æ18
A Simplex Protocol for a Noisy ChannelCode addedFigure 3-12.A positive acknowledgement with retransmission protocol.Networks: Data Link Layer19
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 sequencenumber of frame being ACKed.– Î better use of the channel capacity.Networks: Data Link Layer20
Sliding Window Protocols ACKs introduce a new issue – how long doesreceiver wait before sending ONLY an ACKframe.Î Now we need an ACKTimer !!Î The sender timeout period needs to be set longer. The protocol must deal with the prematuretimeout problem and be “robust” underpathological conditions.Networks: Data Link Layer21
Sliding Window ProtocolsEach outbound frame must contain a sequence number. With nbits for the sequence number field, maxseq 2n - 1 and thenumbers range from 0 to maxseq.Sliding window :: the sender has a window of frames andmaintains a list of consecutive sequence numbers for framesthat it is permitted to send without waiting for ACKs.The receiver has a window of frames that has space for frameswhose sequence numbers are in the range of frame sequencenumbers it is permitted to accept.Note – sending and receiving windows do NOT have to be thesame size.The windows can be fixed size or dynamically growing andshrinking.Networks: Data Link Layer22
Sliding Window ProtocolsThe Host is oblivious to sliding windows and themessage order at the transport layer is maintained.sender’s window :: holds frames sent but not yetACKed.– new packets from the Host cause the upperedge inside the sender’s window to beincremented.– acknowledged frames from the receiver causethe lower edge inside the sender’s window tobe incremented.Networks: Data Link Layer23
Sliding Window Protocols All frames in the sender’s window must besaved for possible retransmission and weneed one timer per frame in the window. If the maximum sender window size is B,the sender needs at least B buffers. If the sender’s window gets full (i.e., itreaches the maximum window size, theprotocol must shut off the Host (the networklayer) until buffers become available.Networks: Data Link Layer24
Sliding Window Protocolsreceiver’s window– Frames received with sequence numbersoutside the receiver’s window are notaccepted.– The receiver’s window size is normally static.The set of acceptable sequence numbers isrotated as “acceptable” frames arrive.If a receiver’s window size 1 , then theprotocol only accepts frames in order.This scheme is referred to as Go Back N.Networks: Data Link Layer25
Sliding Window ProtocolsSelective Repeat :: receiver’s windowsize 1. The receiver stores all correct frameswithin the acceptable window range. Either the sender times out and resendsthe missing frame, or Selective repeat receiver sends a NACKframe back the sender.Networks: Data Link Layer26
Choices in ACK Mechanisms1. The ACK sequence number indicates thelast frame successfully received.- OR 2. ACK sequence number indicates the nextframe the receiver expects to receive.Both of these can be strictly individual ACKsor represent cumulative ACKs.Cumulative ACKs is the most commontechnique.Networks: Data Link Layer27
One-BitSlidingWindowProtocolNetworks: Data Link Layer28
Go Back N4 frames are outstanding; so go back CK1ACK2ACK3Out-of-sequence frames ACK4errorACK5fr8ACK6timefr9ACK7ACK8ACK9ACKing next frame expectedCopyright 2000 The McGraw Hill CompaniesLeon-Garcia & Widjaja: Communication NetworksNetworks: Data Link LayerFigure 5.1329
Go Back Nwith NAK error recoveryTransmitter goes back to frame ACK5ACK6ACK7errorCopyright 2000 The McGraw Hill CompaniesLeon-Garcia & Widjaja: Communication NetworksNetworks: Data Link LayerFigure 5.1730
Networks: Data Link Layer31
Networks: Data Link Layer32
Selective Repeatwith NAK error recoveryABfr0fr1fr2ACK1fr3ACK2fr4fr5errorCopyright 2000 The McGraw Hill K8fr11ACK9Leon-Garcia & Widjaja: Communication NetworksNetworks: Data Link Layertimefr12ACK10ACK11ACK12Figure 5.2133
Networks: Data Link Layer34
Networks: Data Link Layer35
Layer 4 Layer 2 frame Networks: Data Link Layer 6 Data Link Layer Model Assume the sending Host has infinite supply of messages. A node constructs a framefrom a single packet message. The CRC is automatically appended in the hardware. The protocols are developed in increasing complexity to help students understand the data link layer issues.
