Performance Enhancement of TFRC in Wireless Networks

Performance Enhancement of TFRC in Wireless Networks

Data Link Layer Computer Networks Data Link Layer Outline Parallelism between Transport and Data Link Layer Tanenbaums Treatment/Model of Data Link Layer Protocol 1: Utopia Protocol 2: Stop-and-Wait Protocol 3: Positive Acknowledgment with Retransmission [PAR] Old flawed version NewerComputer version Networks Data Link Layer 2

DL Layer Outline (cont) Pipelining and Sliding Windows Protocol 4: One Bit Sliding Window Protocol 5: Go Back N Protocol 6: Selective Repeat Further Details and Decisions Computer Networks Data Link Layer 3 Reliable Protocols at Two Transport Layers Layer ACK/NAK End to End 1

2 Data 3 Data 4 Data 5 Data Leon-Garcia & Widjaja: Communication Networks Hop by Hop Data Link Layer Data 1 Data 2 ACK/ NAK Data 3

ACK/ NAK Computer Networks Data 4 ACK/ NAK Data Link Layer 5 ACK/ NAK 4 Data Link Layer Protocols To achieve control when sending data, a layer of logic, the Data Link Layer protocol is added above the Physical layer. To manage data exchange over a link, DL layer protocol needs: frame synchronization flow control error control addressing control and data

DCC 9 Ed. link management Stallings th Computer Networks Data Link Layer 5 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. Computer Networks Data Link Layer 6 Tanenbaums DL Layer Treatment Concerned with communication between two adjacent nodes in the subnet (node to node). Assumptions: The bits are delivered in the order sent. A rigid interface between the Host and the node the communications policy and the Host protocol (with OS effects) can evolve separately. He uses a simplified model. Computer Networks

Data Link Layer 7 Tanenbaums Simplified Model Layer 4 Host Host A B Node 1 Layer 2 frame Node 2 Tanenbaums Data Link Layer Model Assume the sending Host has infinite supply of messages A node constructs a frame from a single packet messag The CRC is automatically appended in the hardware. The protocols are developed in increasing complexity to he students understand the data link layer issues. Computer Networks

Data Link Layer 8 Basic Elements of ARQ Error-free packet sequence Information frames Packet sequence Transmitter Station A Receiver Control frames CRC Station B Header Information

packet CRC Header Control frame Information Frame Computer Networks Leon-Garcia & Widjaja: Communication Networks Data Link Layer 9 Tanenbaums Protocol Definitions Continued Figure 3-9. Some definitions needed in the protocols to follow. These are located in the file protocol.h. Computer Networks Data Link Layer

10 Packet and Frame Definitions packet network layer buffer frame data link layer info ack seq kind preamble physical layerpostambleCRC Computer Networks Data Link Layer 11 Protocol Definitions (continued

) Figure 3-9. Some definitions needed in the protocols to follow. These are located in the file protocol.h. Computer Networks Data Link Layer 12 Figure 3-10 Unrestricted Simplex Protocol Computer Networks Data Link Layer 13 Figure 3-11 Simplex Stop-andWait

Protocol Computer Networks Data Link Layer 14 Stop-and-Wait Scenarios Now we introduc a noisy channel into our world! Figure 2.17 Timeline showing four different scenarios for the stop-and-wait algorithm. (a) The ACK is received before the timer expires; (b) the original frame is lost; (c) the ACK is lost; (d) the timeout fires too soon {premature timeout!!} P&D Computer Networks Data Link Layer 15 Stop-and-Wait [with errors] (a) Frame 1 lost

A B Time-out time frame 0 ACK (b) ACK lost A B frame 1 frame frame 1 2 ACK Time-out without sequence numbers ambiguous results !! time

frame 0 ACK frame 1 ACK frame frame 1 2 ACK In parts (a) and (b) transmitting station A acts the same way, but part (b) receiving station B accepts frame 1 twice. Computer Networks Data Link Layer 16 Protocol 3: Positive Acknowledgement with Retransmissions [PAR] Introduce Noisy Channels

This produces: 1. Damaged and lost frames 2. Damaged and lost ACKs PAR Protocol Tools and issues: Timers Sequence numbers Duplicate frames Computer Networks Data Link Layer 17 Protocol 3 Positive ACK with Retransmission (PAR) [Old Tanenbaum Version] #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) { stop_timer (s.seq); from_network_layer (&buffer); inc (next_frame_to_send); } } } Computer Networks Data Link Layer 18

Protocol 3 Positive ACK with Retransmission (PAR) [Old Tanenbaum Version] 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 */ Computer Networks Data Link Layer 19 PAR [OLD] problem Ambiguities occur when ACKs are not numbered. premature time-out A B frame 0 ACK time frame 0 ACK

frame 1 frame 2 Transmitting station A misinterprets duplicate ACKs. This protocol is broken !! Computer Networks Data Link Layer Leon-Garcia & Widjaja: Communication Networks 20 PAR Simplex Protocol for a Noisy Channel Code added Figure 3-12.A Positive Acknowledgement with Retransmission

Continued protocol. Computer Networks Data Link Layer 21 A Simplex Protocol for a Noisy Channel Code added Figure 3-12.A Positive Acknowledgement with Retransmission protocol. Computer Networks Data Link Layer 22 State Machine for Stop-andWait 0 10 1 0 1 0 1 0 10 10

10 1 Rnext Slast Timer Slast Transmitter Rnext Station A (0,0) Global State: (Slast, Rnext) FSMs used to check logic on both ends of a protocol. Receiver Station B Error-free frame 0 arrives at receiver ACK for

frame 1 arrives at transmitter Error-free frame 1 arrives at receiver (1,0) Computer Networks Data Link Layer (0,1) ACK for frame 0 arrives at transmitter (1,1) 23 Pipelined Protocols pipelining:: sender allows multiple, in-flight, yet-to-beacknowledged packets range of sequence numbers must be increased buffering at sender and/or receiver Two generic forms of pipelined protocols: Go Back N, Selective

Repeat Computer Networks Data Link Layer K&R 24 Sliding Window Protocols [Tanen] 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 the sequence number of frame being ACKed. better use of the channel capacity. Computer Networks Data Link Layer 25

Sliding Window Protocols ACKs introduce a new issue how long does receiver wait before sending ONLY an ACK frame? Now we need an ACKTimer !! The sender timeout period needs to be set longer. The protocol must deal with the premature timeout problem and be robust under pathological conditions. Computer Networks Data Link Layer 26 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:: the 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.Computer Networks Data Link Layer 27 Sliding Window Protocols The receiver has a window of frames that has space for frames whose sequence numbers are in the range of frame sequence numbers it is permitted to accept. Note sending and receiving windows do NOT have to be the same size. The windows can be fixed size or dynamically growing and shrinking Computer Networks Data Link Layer (e.g., TCP

uses dynamic cwnd). 28 Sliding Window Protocols The Host is oblivious to sliding windows and the message order at the transport layer is maintained. senders DL window :: holds frames sent but not yet ACKed. new packets from the Host cause the upper edge inside the senders window to be incremented. acknowledged frames from the receiver cause the lower edge inside the senders window to be incremented. Computer Networks Data Link Layer 29 Sliding Window Protocols

All frames in the senders 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 at least B buffers. If the senders window gets full (i.e., it reaches the maximum window size, the protocol must shut off the Host (the network layer) until buffers becomeComputer available. 30 Networks Data Link Layer Sliding Window Diagram DCC 9th Ed. Stallings Computer Networks Data Link Layer 31

Sliding Window Protocols receivers DL window Frames received with sequence numbers outside the receivers window are not accepted. The receivers window size is normally static. The set of acceptable sequence numbers is rotated as acceptable frames arrive. If a receivers window size = 1, then the protocol only accepts frames in order. This scheme is referred to as Go Back N. Computer Networks Data Link Layer 32 Sliding Window Protocols Selective Repeat :: receivers window size > 1. The receiver stores all correct

frames within the acceptable window range. Either the sender times out and resends the missing frame, or Selective repeat receiver sends a NACK frame back the sender. Computer Networks Data Link Layer 33 Choices in ACK Mechanisms 1. The ACK sequence number indicates the last frame successfully received. - OR 2. ACK sequence number indicates the next frame the receiver expects to receive. Both schemes can be strictly individual ACKs or represent cumulative ACKs. Computer Networks Cumulative ACKsData

is Link theLayer most 34 One-Bit Sliding Window Protocol Computer Networks Data Link Layer 35 Go Back N Timeout Occurs for frame 3 !! 4 outstanding frames so go back 4 Go-Back-4: fr 0 A B

fr 1 fr 2 A C K 1 fr 3 A C K 2 fr 4 A C K 3 fr

5 fr 6 fr 3 fr 4 fr 5 Out-of-sequence frames A C K 4 error fr 6 fr 7 A C K

5 A C K 6 fr 8 time fr 9 A C K 7 A C K 8 A C K 9

ACKing next frame expected Leon-Garcia & Widjaja: Communication Networks Computer Networks Data Link Layer 36 Go Back N with NAK error recovery Transmitter goes back to frame 1 Go-Back-7: A fr 0 fr 1 fr 2 fr

3 fr 4 fr 5 fr 1 fr 2 fr 3 fr 4 fr 5 fr 6 fr 7

time fr 0 B A C K 1 N A K 1 Out-ofsequence frames A C K 2 A C K 3

A C K 4 A C K 5 A C K 6 error Computer Networks A C K 7 Leon-Garcia & Widjaja: Communication Networks Data Link Layer 37

Computer Networks Data Link Layer 38 Computer Networks Data Link Layer 39 Sliding Window Example DCC 9th Ed. Stallings Computer Networks Data Link Layer 40 Selective Repeat with NAK error recovery Retransmit only frame 2 A

B fr 0 fr 1 fr 2 A C K 1 fr 3 fr 4 A C K 2 fr 5

error fr 6 N A K 2 A C K 2 fr 2 fr 7 A C K 2 A C

K 2 fr 8 fr 9 A C K 7 time fr fr fr 10 11 12 A C K 8 A C K 9

A C K 1 0 A C K 1 1 A C K 1 2 Cumulative ACK Computer Networks Data Link Layer 41 Computer Networks Data Link Layer

42 Computer Networks Data Link Layer 43 Data Link Layer Summary Parallelism between Transport and Data Link Layer Tanenbaums Treatment/Model of Data Link Layer Protocol 1: Utopia Protocol 2: Stop-and-Wait Protocol 3: Positive Acknowledgment with Retransmission [PAR] Old flawed version NewerComputer

Networks Data Link Layer version 44 DL Layer Summary (cont) Pipelining and Sliding Windows Protocol 4: One Bit Sliding Window Protocol 5: Go Back N Protocol 6: Selective Repeat Further Details and Decisions Computer Networks Data Link Layer 45

Recently Viewed Presentations

  • Becoming a Persuasive Writer - College of Charleston

    Becoming a Persuasive Writer - College of Charleston

    Becoming a Persuasive Writer Chapter 2 Cutting Through the Clutter Public relations writers spend much of their working day crafting and disseminating information that will (hopefully) persuade and motivate people.
  • Types of Pathogens - Mr. Kowaleski's Webpage

    Types of Pathogens - Mr. Kowaleski's Webpage

    Types of Pathogens. ... Many Protists are carried by a vector, a carrier of a disease that passes it on to a human host ie. mosquito, tick. ... They obtain energy from their environment, meaning they are heterotrophes. They live...
  • Muscular System - Mrs. Hoffert's Anatomy Class

    Muscular System - Mrs. Hoffert's Anatomy Class

    Arrangement of a Muscle. Muscle Fascicle Muscle Fiber (cell) Myofibril Myofilaments (thick/thin) Muscle Fiber [cell] structure. up to .5 meter long yet only .1 mm in thickness. multinucleated (several nuclei) ... Muscular System Last modified by:
  • PowerPoint 演示文稿

    PowerPoint 演示文稿

    Hamlet, Shakespeare. Act 1, Scene 1 ... Once upon a midnight dreary, while I pondered, weak and weary, Over many a quaint and curious volume of forgotten lore— ...
  • Today's Value Equation - National-Academies.org

    Today's Value Equation - National-Academies.org

    Unknowns ignored Pieter Bruegel the Elder, The Adoration of Kings Methodology can convey a false sense of precision All models use assumptions and assumptions can have a material impact on the model outcomes.
  • Storia del pensiero economico a.a. 2004-2005

    Storia del pensiero economico a.a. 2004-2005

    Storia del pensiero economico a.a. 2007-2008 Prof. Massimo Fornasari Programma d'esame I parte - Nascita e consolidamento di una disciplina: dalla scolastica ai classici L'oggetto ed i metodi della scienza economica Il pensiero economico pre-classico: Valore ed etica dello scambio...
  • 23 - media.rochester.k12.mi.us

    23 - media.rochester.k12.mi.us

    23 The Digestive System: Part A Tongue Terminal sulcus marks the division between Body: anterior 2/3 residing in the oral cavity Root: posterior third residing in the oropharynx Figure 23.8 Epiglottis Palatopharyngeal arch Palatine tonsil Lingual tonsil Palatoglossal arch Foliate...
  • Novela Morisca

    Novela Morisca

    Granada. de José Zorrilla. Autores y obras. En el tiempo que reinabael Infante don Fernando,que del reino de Aragónfue después Rey coronado,en España residíaun caballero esforzado,que Rodrigo de Narváezfue de su nombre llamado,que a todos los de su tiempoen valor...