Slide #1.

Chapter 4. Data Link Layer Business Data Communications and Networking Fitzgerald and Dennis, 7th Edition Copyright Β© 2002 John Wiley & Sons, Inc. 1
More slides like this


Slide #2.

Copyright John Wiley & Sons, Inc. All rights reserved. Reproduction or translation of this work beyond that named in Section 117 of the United States Copyright Act without the express written consent of the copyright owner is unlawful. Requests for further information should be addressed to the Permissions Department, John Wiley & Sons, Inc. Adopters of the textbook are granted permission to make back-up copies for their own use only, to make copies for distribution to students of the course the textbook is used in, and to modify this material to best suit their instructional needs. Under no circumstances can copies be made for resale. The Publisher assumes no responsibility for errors, omissions, or damages, caused by the use of these programs or from the use of the information contained herein. 2
More slides like this


Slide #3.

Chapter 4. Learning Objectives β€’ Understand the role of the data link layer β€’ Become familiar with two basic approaches to controlling access to the media β€’ Become familiar with common sources of error and their prevention β€’ Understand three common error detection and correction methods β€’ Become familiar with several commonly used data link protocols 3
More slides like this


Slide #4.

Chapter 4. Outline β€’ Introduction β€’ Media Access Control – Controlled Access, Contention, Relative Performance β€’ Error Control – Sources of Errors, Error Prevention, Error Detection, Error Correction via Retransmission, Forward Error Correction β€’ Data Link Protocols – Asynchronous Transmission, Asynchronous File Transfer Protocols, Synchronous Transmission β€’ Transmission Efficiency β€’ Summary 4
More slides like this


Slide #5.

Introduction 5
More slides like this


Slide #6.

Introduction β€’ The data link layer sits between the physical and network layers, organizing physical layer bit streams into coherent messages that are passed up to the network layer. β€’ Data link protocols have three functions: – Media Access Control: Controlling when computers transmit. – Error Control: Detecting and correcting transmission errors. – Message Delineation: Identifying the beginning and end of a message. 6
More slides like this


Slide #7.

Media Access Control 7
More slides like this


Slide #8.

Media Access Control β€’ Media Access Control means controlling when computers transmit. β€’ It is important in situations where more than one computer wants to send data at the same time over the same circuit, such as: – Point-to-point half duplex links requiring computers to take turns – Multipoint configurations in which several computers share the same circuit β€’ The two main MAC approaches are: controlled access and contention. 8
More slides like this


Slide #9.

I. Controlled Access β€’ Controlled access works like a stop light, controlling access to the shared resource of the network circuit. β€’ It is commonly used with access to mainframes, whereby the mainframe or its front end processor determine which circuits have access to it at a given moment. β€’ It is also used by some local area network protocols (token ring, FDDI). 9
More slides like this


Slide #10.

X-ON/X-OFF β€’ X-ON/X-OFF is an older controlled access protocol first developed for teletype but still used on some half duplex circuits or between a computer and a printer. β€’ Computer A begins by sending an initial message requesting to transmit data. If Computer B is not busy, it responds with an X-ON signal. Then Computer A starts transmitting. β€’ A periodically pauses to let B send a message. If B is busy it sends an X-OFF message. A waits until B sends an X-ON message again, signaling A that it can begin sending again. 10
More slides like this


Slide #11.

Polling β€’ With polling, the server periodically contacts each client to see if it wants to transmit. Clients transmit only after being asked by the server if they want to send something. β€’ In roll call polling, each client is checked in order to see if it wants to transmit. Clients can also be prioritized so that they are polled more frequently. β€’ In hub polling (also called token passing) one computer starts the poll, sending a message (if it has one) and then passes the token on to the next computer. This continues in sequence until the token reaches the first computer, which starts the polling cycle all over again. 11
More slides like this


Slide #12.

II. Contention β€’ Contention approaches, such as Ethernet, allow computers to transmit whenever the circuit is free. β€’ This means collisions can occur (more than one computer transmitting at the same time). Like two people in a group speaking at the same time, their messages collide and have to be resent. β€’ Contention approaches to media access control need to have a way to sort out which computer is allowed to transmit first after a collision occurs. 12
More slides like this


Slide #13.

Relative Performance (Figure 4-1) β€’ The performance of controlled access versus contention approaches depends on network conditions. β€’ Contention approaches tend to work better for smaller networks with relatively low usage. Since usage is low, the probability of collisions is also low, but when volume is high their performance deteriorates. β€’ Controlled access tends to work better for networks with high traffic volumes where the probability of collisions is high and controlling access means the network will be more efficiently used. 13
More slides like this


Slide #14.

Figure 4-1 Relative Performance of Controlled vs. Contention based MAC protocols 14
More slides like this


Slide #15.

Error Control 15
More slides like this


Slide #16.

Error Control β€’ Error control is handling network errors caused by problems in transmission, not human errors. β€’ Error types include corrupted data and lost data. β€’ Error control is concerned with: 1) preventing, 2) detecting and 3) correcting errors. β€’ While errors can occur in a single bit, they can also be longer. β€’ An important error type is a burst error in which many bits are corrupted at the same time. 16
More slides like this


Slide #17.

Sources of Errors (Figure 4-2) β€’ Sources of errors include: – Line outages in which a circuit fails – White noise caused by thermal energy (hiss) – Impulse noise (spikes) are an important source of burst errors and can be caused by lightning, power surges, and poor connections – Cross-talk occurs when one circuit picks up signals from another – Echoes are caused by poor connections causing the signal to be reflected back to the transmitting source – Attenuation is the weakening of a signal over a distance – Jitter occurs due to small variations in the amplitude, frequency, and phase of a signal – Harmonic distortion occurs when an amplifier does not correctly amplify its input signal 17
More slides like this


Slide #18.

Sources of Errors 18
More slides like this


Slide #19.

Source of Error What causes it How to prevent it Line Outages Storms, accidents White Noise Movement of electrons Increase signal strength Impulse Noise Sudden increases in electricity (e.g., lightning) Shield or move the wires Cross-talk Multiplexer guard bands are too small or wires too close together Increase the guard bands, or move or shield the wires Echo Poor connections Fix the connections, or tune equipment Attenuation Gradual decrease in signal over distance Use repeaters or amplifiers Intermodulation Noise Signals from several circuits combine (form of crosstalk) Move or shield the wires Jitter Analog signals change phase Tune equipment Harmonic Distortion Amplifier changes phase Tune equipment Figure 4-2 Sources of errors and ways to prevent or minimize them 19
More slides like this


Slide #20.

Error Detection β€’ Most error detection techniques work in the same way: – An error detection value is first calculated by the sender and transmitted along with the data. – At the receiving end, the error detection value is recalculated and checked against the received value. – If the two values are the same, the data has been received correctly – If they differ, however, an error has occurred and the data needs to be sent again. β€’ Three common forms of error detection techniques are currently in use: parity checks, longitudinal redundancy checking, and polynomial checking. 20
More slides like this


Slide #21.

Parity Checking (Figure 4-3) β€’ Parity checking is one of the oldest and simplest error detection techniques. β€’ In parity checking, a single bit is added to each character. For even parity, the sum of the bits (including the parity bit) remains even, for odd parity, the sum remains odd. β€’ At the receiving end, the parity bit is recalculated. If one bit has been transmitted in error the received parity bit will differ from the recalculated one. β€’ Parity checking is simple, but doesn’t catch all errors. β€’ If two (or an even number of) bits have been changed at the same time, the parity check appears to be correct even though an error has occurred. 21
More slides like this


Slide #22.

Assume we are using even parity with 7-bit ASCII. The letter V in 7-bit ASCII is encoded as 0110101. Because there are four 1’s (an even number), Parity is set to 0, so that the sum of all the bits remains even. This would be transmitted as: 01101010. Assume we are using odd parity with 7-bit ASCII. Again, the letter V in 7-bit ASCII is encoded as 0110101. Because there are four 1’s (an even number), Parity is set to 1, so that the sum of all the bits remains odd. This would be transmitted as: 01101011. Figure 4-3 Using parity for error detection Note: the above slide differs from the text. 22
More slides like this


Slide #23.

Figure 4-3 Using parity for error detection Assume we are using even parity with 7-bit ASCII. The letter V in 7-bit ASCII is encoded as 0110101. Because there are four 1’s (an even number), Parity is set to 0, so that the sum of all the bits remains even. This would be transmitted as: 01101010. Assume we are using even parity with 7-bit ASCII. The letter W in 7-bit ASCII is encoded as 0001101. Because there are three 1’s (an odd number), Parity is set to 1, so that the sum of all the bits remains even. This would be transmitted as: 00011011. 23
More slides like this


Slide #24.

Longitudinal Redundancy Checking (LRC) β€’ LRC was developed as an improvement over parity checks. LRC adds an additional character of parity checks, called a block control character (BCC) to each block of data. β€’ Unlike ordinary parity, the BCC parity calculations are based on the 1st bit, 2nd bit, etc. in a block (see Figure 4-4). β€’ LRC is a major improvement over parity checking, catching over 98% of all errors, but still misses a significant number of errors. 24
More slides like this


Slide #25.

Figure 4-4 Using LRC for error detection For example, suppose we were to send the message β€œDATA” using odd parity and LRC with 7-bit ASCII: Letter D A T A BCC ASCII Parity bit 1000100 1 1000001 1 1010100 0 1000001 1 1101111 1 (Note that the BCC’s parity bit is also determined by parity.) 25
More slides like this


Slide #26.

Polynomial Checking β€’ Polynomial checking, the most powerful error checking technique currently in widespread use, adds 1 or more characters to the end of the message based on a mathematical algorithm. β€’ Checksum is a 1-byte calculation made by adding the byte values of the message, dividing the total by 255 and saving the remainder (95% effective). β€’ Cyclic Redundancy Check (CRC) is also computed by calculating the remainder to a division problem. CRC-16 (99.969% effective) and CRC-32 (99.99%) are in common use today. 26
More slides like this


Slide #27.

Error Correction via Retransmission β€’ When an error is detected, it is corrected by retransmission of the data along with its error detection value. β€’ The process of requesting that a data transmission be resent is called an Automatic Repeat Request or ARQ. β€’ The two main ARQ protocols are: – Stop and Wait ARQ – Continuous ARQ 27
More slides like this


Slide #28.

Stop-and-Wait ARQ (Figure 4-5) β€’ Stop-and-Wait ARQ is a half duplex technique that works just like it sounds. β€’ The sender first sends a packet, then waits to hear from the receiver. β€’ If the packet has been received without error, an acknowledgement (ACK) is sent back by the receiver and the next packet is sent. β€’ If the receiver detects an error in the packet that was just sent, the receiver sends back a negative acknowledgement (NAK) and the sender resends the packet again. 28
More slides like this


Slide #29.

Figure 4-5. Stop and Wait ARQ 29
More slides like this


Slide #30.

Continuous ARQ (Figure 4-6) β€’ Continuous ARQ is a full duplex technique that allows the sender to continue sending packets without waiting for the receiver to acknowledge that they have been received correctly. β€’ Acknowledgements are still sent back by the receiver once they have been processed and include some kind information to identify which packet was acknowledged. β€’ If a packet is received in error, the receiver sends back a NAK for a specific packet to be resent. β€’ A sliding window size provides flow control. 30
More slides like this


Slide #31.

Figure 4-6. Continuous ARQ 31
More slides like this


Slide #32.

Forward Error Correction β€’ ARQ techniques are also called backward error correction. β€’ The alternative, forward error correction, means the receiving device can correct incoming messages itself instead of having them resent. β€’ To do this, extra corrective information needs to be sent along with the data that allows the data to be checked and corrected by the receiver. β€’ The amount of extra information needed is usually quite a lot (50-100% of the data). β€’ This technique is useful for one way transmissions or when transmission times are very long (as with communications to spacecraft). 32
More slides like this


Slide #33.

Forward Error Correction (Figure 4-7) β€’ One forward error correction technique, called a Hamming Code, work a bit like LRC – Longitudinal Redundancy Checking. Extra parity values are calculated so that each data bit figures into two parity bit calculations. β€’ That means that if any one bit, either parity or data, gets changed in transmission, the change in the received data can be detected and corrected (see Figure 4-7). β€’ This technique, however, only works for one bit errors. 33
More slides like this


Slide #34.

Figure 4-7 Forward Error Correction 34
More slides like this


Slide #35.

Data Link Protocols 35
More slides like this


Slide #36.

Data Link Protocols (Figure 4-8) β€’ Data link protocols differ by message delineation, frame length, and frame field structure. β€’ Another fundamental difference is between asynchronous and synchronous transmission data link protocols. 36
More slides like this


Slide #37.

Protocol Size Error Detection Retransmission Media Access Asynchronous Transmission 1 Parity Continuous ARQ Full Duplex XMODEM 132 8-bit Checksum Stop-and-wait ARQ Controlled Access XMODEM-CRC 132 8-bit CRC Stop-and-wait ARQ Controlled Access XMODEM-1K 1028 8-bit CRC Stop-and-wait ARQ Controlled Access ZMODEM * 32-bit CRC Continuous ARQ Controlled Access KERMIT * 24-bit CRC Continuous ARQ Controlled Access SDLC * 16-bit CRC Continuous ARQ Controlled Access HDLC * 16-bit CRC Continuous ARQ Controlled Access Token Ring * 32-bit CRC Stop-and wait ARQ Controlled Access Ethernet * 32-bit CRC Stop-and wait ARQ Contention SLIP * None None Full Duplex PPP * 16-bit CRC Continuous ARQ Full Duplex File Transfer Protocols Synchronous Protocols * Varies depending on message length. Figure 4-8 Data Link Protocol Summary 37
More slides like this


Slide #38.

Asynchronous Transmission (Figure 4-9) β€’ In asynchronous transmission (sometimes called start-stop transmission), each character is sent independently. β€’ The transmission sequence begins with a start bit, next the character is sent, then the parity bit and finally a stop bit are sent. The start bit is usually a 0 and the stop bit a 1. β€’ Between transmissions (called β€œidle time”), a series of stop bits are sent. β€’ When a new character is sent, the start bit is used by the receiver for synchronization. 38
More slides like this


Slide #39.

Figure 4-9 Asynchronous Transmission 39
More slides like this


Slide #40.

Synchronous Transmission β€’ In synchronous transmission, data is sent in a large block called a frame or packet, typically about a thousand characters long. β€’ Synchronous transmission is used on both pointto-point and multipoint circuits. In the latter case, addressing information needs to be included in the frame. β€’ Synchronous packets sometimes begin and end with a series of synchronization (SYN) characters that are used to help the receiver recognize incoming data. β€’ Synchronous transmission protocols can be byteoriented, bit-oriented, or byte-count protocols. 40
More slides like this


Slide #41.

Synchronous Data Link Control (SDLC) β€’ SDLC is a bit-oriented protocol developed by IBM (Figure 4-11) – SDLC uses a controlled media access protocol. – Frames begin & end with a special 8-bit flag (01111110). – Supervisory frames are used for error and flow control. β€’ Each SDLC frame contains the following fields: – – – – – – Start Flag (8 bits) Destination Address (8 or 16 bits) Control: identifies frame type; information or supervisory Message: variable length, contains data Frame Check Sequence (CRC-32) Ending Flag (8 bits) 41
More slides like this


Slide #42.

Figure 4-11 SDLC Frame Format 42
More slides like this


Slide #43.

Ethernet (IEEE 802.3) β€’ Most widely used LAN protocol. β€’ Byte-count with contention based media access control. Developed jointly by Digital, Intel, and Xerox (see Figure 4-12). β€’ Each frame contains: – – – – Destination and source addresses (6 bytes each) Length (of data) field (2 bytes) Data or message field of variable length Frame Check Sequence (CRC-32, 4 bytes long) 43
More slides like this


Slide #44.

Figure 4-12 Ethernet Frame Format 44
More slides like this


Slide #45.

Point-to-Point Protocol (PPP) β€’ Byte-oriented protocol developed in the early 90s. β€’ Commonly used on voice grade dial-up lines between home PCs and ISPs. β€’ Each PPP frame contains: – – – – – – Start Flag (1 byte) Address and Control fields (1 bytes each) Protocol field (2 bytes) Data or message field (variable length, up to 1500B) Frame Check Sequence (CRC-16, 2 bytes long) End Flag (1 byte) 45
More slides like this


Slide #46.

Figure 4-13 PPP packet layout 46
More slides like this


Slide #47.

Transmission Efficiency 47
More slides like this


Slide #48.

Optimal Packet Size (Figure 4-14) β€’ Throughput is the total number of information bits received per second, after taking into account the overhead bits and the need to retransmit packets containing errors. β€’ In designing a protocol, there is a trade-off between large and small packets. β€’ Small packets are less efficient, but are less likely to contain errors and less costly in terms of circuit capacity to retransmit if there is an error. 48
More slides like this


Slide #49.

Figure 4-14 Optimum Packet Size 49
More slides like this


Slide #50.

TRIB: Transmission Rate of Information Bits (per second) β€’ β€’ β€’ β€’ β€’ β€’ β€’ TRIB = K(M-C)(1-P) / [(M/R) + T] K = information bits per character M = characters / packet R = data transmission rate (characters/sec) C = non-information characters / packet P = probability that block is retransmitted T = time between blocks 50
More slides like this


Slide #51.

End of Chapter 4 51
More slides like this