The Data Link Layer Data Link Layer Design

The Data Link Layer Data Link Layer Design

The Data Link Layer Data Link Layer Design Issues Error Detection and Correction Elementary Data Link Protocols Sliding Window Protocols Example Data Link Protocols

The Data Link Layer Responsible for delivering frames of information over a single link Handles transmission errors and regulates the flow of data Application Transport Network Link Physical Data Link Layer Design Issues

Frames Possible services Framing methods Error control Flow control Ultimately, the data link layer uses

the services of the physical layer to send and receive bits over communication channels. To accomplish these goals, the data link layer takes the packets it gets from the network layer and encapsulates them into Frames for transmission. Frames Link layer accepts packets from the network layer, and encapsulates them into frames that it sends using the physical layer; reception is the opposite process Network Link

Virtual data path Physical Actual data path CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Possible Services Unacknowledged connectionless service Frame is sent with no connection / error recovery Ethernet is example Acknowledged connectionless service Frame is sent with retransmissions if needed

Example is 802.11 Acknowledged connection-oriented service Connection is set up; rare CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Framing Methods

Byte count Flag bytes with byte stuffing Flag bits with bit stuffing Physical layer coding violations Use non-data symbol to indicate frame To allow a receiver to prepare for an incoming packet, a common pattern used for Ethernet and 802.11 is to have a frame begin with a well-defined pattern called preamble. CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Framing Byte count

Frame begins with a count of the number of bytes in it Simple, but difficult to resynchronize after an error Expected case Error case CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Framing Byte stuffing Special flag bytes delimit frames; occurrences of flags in the data must be stuffed (escaped)

Longer, but easy to resynchronize after error Frame format Need to escape extra ESCAPE bytes too! Stuffing examples CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Framing Bit stuffing Stuffing done at the bit level:

Frame flag has six consecutive 1s (not shown) On transmit, after five 1s in the data, a 0 is added On receive, a 0 after five 1s is deleted Data bits Transmitted bits with stuffing CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Error Control Error control repairs frames that are received in error Requires errors to be detected at the receiver Typically retransmit the unacknowledged frames

Timer protects against lost acknowledgements Detecting errors and retransmissions are next topics. CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Flow Control Prevents a fast sender from out-pacing a slow receiver Receiver gives feedback on the data it can accept Rare in the Link layer as NICs run at wire speed Receiver can take data as fast as it can be sent Flow control is a topic in the Link and Transport layers.

CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 TWIT Resources Li-Fi https://www.youtube.com/watch?v=yLCljViTkus Error Detection and Correction Error codes add structured redundancy to data so errors can be either detected, or corrected. Error correction codes:

Hamming codes Binary convolutional codes Reed-Solomon and Low-Density Parity Check codes Mathematically complex, widely used in real systems Error detection codes: Parity Checksums Cyclic redundancy codes CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Error Bounds Hamming distance Code turns data of n bits into codewords of n+k bits

Hamming distance is the minimum bit flips to turn one valid codeword into any other valid one. Example with 4 codewords of 10 bits (n=2, k=8): 0000000000, 0000011111, 1111100000, and 1111111111 Hamming distance is 5 Bounds for a code with distance: 2d+1 can correct d errors (e.g., 2 errors above) d+1 can detect d errors (e.g., 4 errors above) CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Error Correction Hamming code

Hamming code gives a simple way to add check bits and correct up to a single bit error: Check bits are parity over subsets of the codeword Recomputing the parity sums (syndrome) gives the position of the error to flip, or 0 if there is no error Hamming Code Video and Detecting (11, 7) Hamming code adds 4 check bits and can correct 1 error Error Detection Parity (1) Parity bit is added as the modulo 2 sum of data bits Equivalent to XOR; this is even parity Ex: 1110000 11100001

Detection checks if the sum is wrong (an error) Simple way to detect an odd number of errors Ex: 1 error, 11100101; detected, sum is wrong Ex: 3 errors, 11011001; detected sum is wrong Ex: 2 errors, 11101101; not detected, sum is right! Error can also be in the parity bit itself Random errors are detected with probability CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Error Detection Parity (2) Interleaving of N parity bits detects burst errors up to N Each parity sum is made over non-adjacent bits An even burst of up to N errors will not cause it to fail

CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Error Detection Checksums Checksum treats data as N-bit words and adds N check bits that are the modulo 2N sum of the words Ex: Internet 16-bit 1s complement checksum Properties: Improved error detection over parity bits Detects bursts up to N errors Detects random errors with probability 1-2N Vulnerable to systematic errors, e.g., added zeros

Error Detection CRCs (1) Adds bits so that transmitted frame viewed as a polynomial is evenly divisible by a generator polynomial Start by adding 0s to frame and try dividing Offset by any reminder to make it evenly divisible CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011

Elementary Data Link Protocols Link layer environment Utopian Simplex Protocol Stop-and-Wait Protocol for Error-free channel Stop-and-Wait Protocol for Noisy channel

CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Elementary Data Link Protocols An important design issue that occurs in the data link layer is what to do with a sender that systematically wants to transmit frames faster than the receiver can accept them. In rate-based flow control, the protocol has a built-in mechanism that limits the rate at which senders may transmit data, without using feedback from the receiver. The use of error-correcting codes is often referred to as FEC (Forward Error Correction). CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011

Link layer environment (1) Commonly implemented as NICs and OS drivers; network layer (IP) is often OS software CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Link layer environment (2) Link layer protocol implementations use library functions See code (protocol.h) for more details Group Library Function

Description Network layer from_network_layer(&packet) to_network_layer(&packet) enable_network_layer() disable_network_layer() Take a packet from network layer to send Deliver a received packet to network layer

Let network cause ready events Prevent network ready events Physical layer from_physical_layer(&frame) to_physical_layer(&frame) Get an incoming frame from physical layer Pass an outgoing frame to physical layer Events &

timers wait_for_event(&event) start_timer(seq_nr) stop_timer(seq_nr) start_ack_timer() stop_ack_timer() Wait for a packet / frame / timer event Start a countdown timer running Stop a countdown timer from running Start the ACK countdown timer Stop the ACK countdown timer

CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Utopian Simplex Protocol An optimistic protocol (p1) to get us started Assumes no errors, and receiver as fast as sender Considers one-way data transfer } Sender loops blasting frames

Receiver loops eating frames Thats it, no error or flow control CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Stop-and-Wait Error-free channel Protocol (p2) ensures sender cant outpace receiver: Receiver returns a dummy frame (ack) when ready Only one frame out at a time called stop-and-wait We added flow control!

Sender waits to for ack after passing frame to physical layer Receiver sends ack after passing frame to network layer CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Stop-and-Wait Noisy channel (1) ARQ (Automatic Repeat reQuest) adds error control Receiver acks frames that are correctly delivered Sender sets timer and resends frame if no ack) For correctness, frames and acks must be numbered

Else receiver cant tell retransmission (due to lost ack or early timer) from new frame For stop-and-wait, 2 numbers (1 bit) are sufficient Protocols in which the sender waits for a positive acknowledgement before advancing to the next data item are often called ARQ (Automatic Repeat reQuest) or PAR (Positive Acknowledgement with Retransmission) CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Stop-and-Wait Noisy channel (2) {

Sender loop (p3): Send frame (or retransmission) Set timer for retransmission Wait for ack or timeout If a good ack then set up for the next frame to send (else the old frame will be retransmitted) CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Stop-and-Wait Noisy channel (3) Receiver loop (p3):

Wait for a frame If its new then take it and advance expected frame Ack current frame CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Sliding Window Protocols

Sliding Window concept One-bit Sliding Window Go-Back-N Selective Repeat Sliding Window concept (1) Sender maintains window of frames it can send Needs to buffer them for possible retransmission Window advances with next acknowledgements Receiver maintains window of frames it can receive Needs to keep buffer space for arrivals

Window advances with in-order arrivals Sliding Window concept (2) A sliding window advancing at the sender and receiver Ex: window size is 1, with a 3-bit sequence number. Sender Receiver At the start First frame is sent

First frame is received Sender gets first ack Sliding Window concept (3) Larger windows enable pipelining for efficient link use Stop-and-wait (w=1) is inefficient for long links Best window (w) depends on bandwidth-delay (BD) Want w 2BD+1 to ensure high link utilization Pipelining leads to different choices for errors/buffering

We will consider Go-Back-N and Selective Repeat The technique of temporarily delaying outgoing acknowledgements so that they can be hooked onto the next outgoing data frame is known as piggybacking CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 One-Bit Sliding Window (1) Transfers data in both directions with stop-and-wait Piggybacks acks on reverse data frames for efficiency Handles transmission errors, flow control, early timers { Each node is sender

and receiver (p4): Prepare first frame Launch it, and set timer ... One-Bit Sliding Window (2) ... Wait for frame or timeout If a frame with new data then deliver it

If an ack for last send then prepare for next data frame (Otherwise it was a timeout) Send next data frame or retransmit old one; ack the last data we received One-Bit Sliding Window (3) Two scenarios show subtle interactions exist in p4: Simultaneous start [right] causes correct but slow operation compared to normal [left] due to duplicate transmissions.

Time Notation is (seq, ack, frame number). Asterisk indicates frame accepted by network layer . Normal case Correct, but poor performance Go-Back-N (1) Receiver only accepts/acks frames that arrive in order: Discards frames that follow a missing/errored frame Sender times out and resends all outstanding frames

Go-Back-N (2) Tradeoff made for Go-Back-N: Simple strategy for receiver; needs only 1 frame Wastes link bandwidth for errors with large windows; entire window is retransmitted Implemented as p5 (see code in book) CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Selective Repeat (1)

Receiver accepts frames anywhere in receive window Cumulative ack indicates highest in-order frame NAK (negative ack) causes sender retransmission of a missing frame before a timeout resends window CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Selective Repeat (2) Tradeoff made for Selective Repeat: More complex than Go-Back-N due to buffering at receiver and multiple timers at sender More efficient use of link bandwidth as only lost

frames are resent (with low error rates) Implemented as p6 (see code in book) CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Selective Repeat (3) For correctness, we require: Sequence numbers (s) at least twice the window (w) Error case (s=8, w=7) too few sequence numbers Originals

Retransmits New receive window overlaps old retransmits ambiguous Correct (s=8, w=4) enough sequence numbers Originals Retransmits

New and old receive window dont overlap no ambiguity CN5E by Tanenbaum & Wetherall, Pearson Education-Prentice Hall and D. Wetherall, 2011 Hak 5 Resources TCP Flow Control https://www.youtube.com/watch?v=McDNzBvRPHA Using Wireshark https://www.youtube.com/watch?v=2ircAIQ7U2A Example Data Link Protocols

Packet over SONET PPP (Point-to-Point Protocol) ADSL (Asymmetric Digital Subscriber Loop) Packet over SONET Packet over SONET is the method used to carry IP packets over SONET optical fiber links Uses PPP (Point-to-Point Protocol) for framing

most commonly used protocol over the wide-area optical fiber links that make up the back-bone of communications networks Protocol stacks PPP frames may be split over SONET payloads PPP (1) PPP (Point-to-Point Protocol) is a general method for delivering packets across links Framing uses a flag (0x7E) and byte stuffing

Unnumbered mode (connectionless unacknowledged service) is used to carry IP packets Errors are detected with a checksum 0x21 for IPv4 IP packet PPP (2) A link control protocol brings the PPP link up/down State machine for link control ADSL (1)

Widely used for broadband Internet over local loops ADSL runs from modem (customer) to DSLAM (ISP) IP packets are sent over PPP and AAL5/ATM (over) ADSL (2) PPP data is sent in AAL5 frames over ATM cells: ATM is a link layer that uses short, fixed-size cells (53 bytes); each cell has a virtual circuit identifier AAL5 is a format to send packets over ATM PPP frame is converted to a AAL5 frame (PPPoA) AAL5 frame is divided into 48 byte pieces, each of which goes into one ATM cell with 5 header bytes

The Lab The End

Recently Viewed Presentations

  • Run coordination Summary C. Gemme  INFN Genova on

    Run coordination Summary C. Gemme INFN Genova on

    M167.C3 (HEC C) HV decreased due to new short HECA cell 0x3b1a5200 (tower 0x4110400) disabled at each run, consider if permanently disable this shaper switch Reprocessing to consider it DQ/Monitoring under test: online flagging of Mini Noise Bursts (prev. offline)...
  • Organisation du système d'information comptable et de gestion

    Organisation du système d'information comptable et de gestion

    TAGGER L'INFORMATION Fiable Pertinente Actuelle Licite Disponible Utilisable Non redondante Sélective Synthétique Précise Évaluable QUATRE NIVEAUX SÉMANTIQUES : Données Ex. Volume de transactions Interprétation Information Ex. Segments de consommation Codification Connaissances Ex ...
  • What is a Marathon? - WordPress.com

    What is a Marathon? - WordPress.com

    What is a Marathon? A Marathon is a 26.2 mile long race. Many people take part and are committed to do such a technical event. You can either run, walk, skip, do it in a wheel chair, hop, jump or...
  • The CONTINUITY and CHANGE OVER TIME ESSAY

    The CONTINUITY and CHANGE OVER TIME ESSAY

    The CONTINUITY and CHANGE OVER TIME ESSAY. The BIG PICTURE. The ripple effect. ... Write a thesis statement that contains the main elements of change and continuity from above. ... like the potato and corn, became a staple in many...
  • Computer-Aided Design - Vanderbilt University

    Computer-Aided Design - Vanderbilt University

    Computer-Aided Design Chapter 7 Computer-Aided Design (CAD) Use of computer systems to assist in the creation, modification, analysis, and optimization of a design Typical tools: Tolerance analysis Mass property calculations Finite-element modeling and visualization Defines the geometry of the design...
  • Premature Spontaneous Rupture of The Membranes

    Premature Spontaneous Rupture of The Membranes

    PREMATURE SPONTANEOUS RUPTURE OF THE MEMBRANES ... with a sterile speculum pH tested with nitrazine paper (AF→ pH=7,0-7,25) cervical secretions for culture fern test (air-dry a drop of the fluid on a slide arborization) Nile blue sulfate staining of fetal...
  • A New Anecdote of Antiquity in the History

    A New Anecdote of Antiquity in the History

    Origins of Writing! 1999- Amorites Babylon Rule 1792-1749 Hammurabi Sumerian Trailblazing Science - Business Religion Nammu (mother goddess), Ishtar or Inanna (love goddess), w/wind and thunder gods Ziggurats Dumuzi-gamil fails in crash of '88 Conclusions What is it?
  • The Spectrum of Neurodegenerative Dementia

    The Spectrum of Neurodegenerative Dementia

    MCI of a Neurodegenerative Etiology. Meets MCI clinical criteria, BUT. Biomarkers not tested, OR. Biomarkers tested but are ambiguous for AD, OR. Biomarkers tested but are negative for AD. MCI of the Alzheimer Type. Meets MCI clinical criteria, AND. At...