The Data Link Layer - Institute for Computing and Information ...

The Data Link Layer - Institute for Computing and Information ...

Chapter 3 The Data Link Layer 2010 1 Design Issues Controls communication between 2 machines directly connected by wire-like link Services Provided to the Network Layer Framing: frame as an unit for physical layer to send in one go

Error Control Flow Control, not sending faster than can be received 2010 2 Services Provided to Network Layer Unacknowledged connectionless service. no recovering of lost or corrupted frame when the error rate is very low

real-time traffic, like speech or video Acknowledged connectionless service. returns information a frame has safely arrived. time-out, resend, frames received twice unreliable channels, such as wireless systems. Acknowledged connection-oriented service. established connection before any data is sent. provides the network layer with a reliable bit stream. 2010 3

Framing, character count Time gaps between frames are not suitable times are variable in networks received gaps can be smaller or larger Need to be combined with other methods 2010 4 Framing, flag bytes (a) A frame delimited by flag bytes.

(b) Four examples of byte sequences before and after stuffing. 2010 5 Framing, bit stuffing Flag is 6 1 bits After 5 1s a 0 is added 2010 6

Error-Detecting Codes, CRC Cyclic redundancy Checks related to polynomial theories usually implemented in hardware using 16 of 32 bit generators -detect burst errors fewer than r+1 bits -any odd number of bit errors -up to an certain even number of errors 2010 7 Error-Correcting Codes

Use of a Hamming code, adding extra bits, to correct errors. Error-correcting codes used in the early days, noisy lines Later lines and electronics got better: error-detection and resend Now used for wireless communication and high speed ethernet 2010 8 Protocols

ACK (acknowledgements) for correct frames possible NACK for lost or corrupted frames (piggybacked) Pipelining error correction by resend of lost or corrupted frames Flow control 2010 9

Stop and Wait Protocols A Simplex Protocol for a Noisy Channel sender waits for an ack for each send frame frames may be damaged or lost, same for acks no nacks for lost or error frames might be used to increase the data rate sender uses a timer and re-sends frame a 1-bit frame number (0 and 1) is needed for data and ack frames, to separate a re-send frame from the original one also called: alternating bit protocol 2010 10

Pipelining sender receiver last bit transmitted, t = L / R first packet bit arrives RTT last packet bit arrives, send ACK ACK arrives, send next packet, t = RTT + L / R

Sender needs to buffer a send frame until its ack has arrived the buffer is a sliding window on all frames in the stream 2010 11 Go Back N receiver has no buffer it can only accept (and send to its higher layer) a correct frame with the next expected sequence number sends an ack for that sequence number, this implies that all previous frames have arrived

otherwise it discards the frame and either sends nothing back or an ack for the last accepted frame or a nack for the next frame receiver timer to send ack (or nack) in separate frame do not wait too long for return frame to piggyback the ack or nack 2010 12 Go Back N, sender

buffer for a number of already send but not yet acked frames a timer for the oldest frame in the buffer resend in case of time-out, an ack for an already acked frame or a nack in case of a resend: all next already send frames must be resend more than 1 bit for sequence numbers are needed: Nr_Buf <= Max_Seq+1 2010

13 Selective Repeat also receiver buffers frames: can store out-of-order correct frames only 1 frame has to be resend in case of error or lost

nacks are usually used for error or lost frames just makes it faster Nr_Buf <= (Max_Seq+1)/2 (0Max_Seq) sender needs timer of each send frame receiver timer to send ack (or nack) in separate frame do not wait too long for return frame to piggyback the ack or nack 2010 14 Selective Repeat buffers 2010

15 Go Back N vs Selective Repeat 2010 16 Protocol Verification Modeling needed Finite State Machine Models Petri Net Models Formal verification

Uppaal PVS 2010 17

Recently Viewed Presentations

  • Promozionale - Libero.it

    Promozionale - Libero.it

    Sono orgoglioso della capacità che ho maturato di costruire la mia conoscenza su un bambino non solo dai test o dalle osservazioni, ma dallo scambio con i papà e le mamme, e di spiegare la natura delle difficoltà e le...
  • Dissecting Bitcoin Architecture and Security

    Dissecting Bitcoin Architecture and Security

    transaction small. Keeps . uniformity. of transaction fields. Spender . needs to include script to spend the money. Scripting Language The bitcoin transaction script language, called Script, is a Forth-like reverse-polish notation stack-based execution language. If that sounds like gibberish,...
  • New Features in the .NET Framework V2.0

    New Features in the .NET Framework V2.0

    Wintellect Other titles: Times New Roman Arial Wingdings TechEd 2005 TechEd2005_Template New Features in the .NET Framework V2.0 Agenda New "framework only" feature list - not the complete list! Code Demos Your Feedback is Important! Slide 6 Slide 7 Slide...
  • NAME

    NAME

    ITEC 7445. Emerging Technology. July 14, 2014. What is Edmodo? Edmodo is a free social learning website. Made in the image of Facebook© ...
  • Hiệp Lại Trong Ân Điển Ngài

    Hiệp Lại Trong Ân Điển Ngài

    O Lord cleanse our hearts with fire . And fill us with desire for Your courts for Your presence in our lives. Instrumental (2) NguyệnNgàidìu con mỗingày. bằngtìnhyêukhôngbếnbờ, ... Cho đến mãi sau Cha hằng đưa dắt.
  • PS4: Encouraging Expected Behavior

    PS4: Encouraging Expected Behavior

    The Science of Behavior: ... Behavior, when we focused on the development of the Schoolwide Expectations Matrix and the lessons to teach matrix behaviors. Clarifying the behavior you want your students to exhibit, teaching that behavior and providing non-contingent attention...
  • Unit 2

    Unit 2

    developed the _____ RR car . meat was now_____ then _____ ... Different national trade unions came together to form this federation. The AFL represented skilled workers in different trades. The AFL fought for better pay, shorter hours, better working...
  • DOOCS DAQ software for the EUDET prototype

    DOOCS DAQ software for the EUDET prototype

    DOOCS DAQ software for the EUDET prototype Valeria Bartsch (UCL) Andrzej Misiejuk (RHUL) Tao Wu (RHUL) Overview over the task - DOOCS software - Overview over the task - ENS naming service - ENS Naming Service Overview over the task...