Business Data Communications and Networking - Chapter 4: Data Link Layer

Business Data Communications and Networking 8th Edition Jerry Fitzgerald and Alan DennisJohn Wiley & Sons, Inc Prof. M. UlemaManhattan CollegeComputer Information Systems1Copyright 2005 John Wiley & Sons, IncChapter 4Data Link Layer2Copyright 2005 John Wiley & Sons, IncOutlineMedia Access ControlControlled Access, Contention, Relative PerformanceError Control Sources of Errors, Error Prevention, Error Detection, Error Correction via Retransmission, Forward Error CorrectionData Link ProtocolsAsynchronous Transmission, Asynchronous File Transfer Protocols, Synchronous TransmissionTransmission Efficiency3Copyright 2005 John Wiley & Sons, IncData Link Layer - IntroductionResponsible for moving messages from one device to anotherControls the way messages are sent on mediaOrganizes physical layer bit streams into coherent messages for the network layerMajor functions of a data link layer protocolMedia Access ControlControlling when computers transmitError ControlDetecting and correcting transmission errorsMessage DelineationIdentifying the beginning and end of a messageData Link LayerPhysical LayerNetwork Layer4Copyright 2005 John Wiley & Sons, IncMedia Access Control (MAC)Controlling when and what computers transmitImportant when more than one computer wants to send data (at the same time over the same circuit); e.g., Point-to-point half duplex links computers to take turnsMultipoint configurations Ensure that no two computers attempt to transmit data at the same timeMain approachesControlled accessContention based access5Copyright 2005 John Wiley & Sons, IncControlled AccessControlling access to shared resourcesActs like a stop lightCommonly used by mainframes (or its front end processor)Determines which circuits have access to mainframe at a given timeAlso used by some LAN protocolsToken ring, FDDIMajor controlled access methodsX-ON/X-OFF and Polling6Copyright 2005 John Wiley & Sons, IncX-ON / X-OFFABX-ONnot busyRequest to TransmittransmittingPausing (periodically done)busyX-OFFX-ONnot busytransmittingdatadatadatadataAn older controlled access protocolStill used on some half duplex circuits, but it is fadingStill used between a computer and a printer7Copyright 2005 John Wiley & Sons, IncPollingProcess of transmitting to a client only if asked and/or permittedClient stores the info to be transmittedServer (periodically) polls the client if it has data to sendClient, if it has any, sends the dataIf no data to send, client responds negatively, and server asks the next clientTypes of pollingRoll call polling Hub polling (also called token passing)8Copyright 2005 John Wiley & Sons, IncRoll Call PollingInvolves waiting: Poll and wait for a responseNeeds a timer to prevent lock-up (by client not answering)ServerEBCDACheck each client (consecutively and periodically) to see if it wants to transmit : A, B, C, D, E, A, B, Clients can also be prioritized so that they are polled more frequently: A, B, A, C, A, D, A, E, A, B, .. Clients9Copyright 2005 John Wiley & Sons, IncHub Polling (Token Passing) EBCDAtokenOne computer starts the poll:sends message (if if any) thenpasses the token on to the next computerContinues in sequence until the token reaches the first computer, which starts the polling cycle all over again10Copyright 2005 John Wiley & Sons, IncContentionTransmit whenever the circuit is free Collisions Occurs when more than one computer transmitting at the same timeNeed to determine which computer is allowed to transmit first after the collisionUsed commonly in Ethernet LANs11Copyright 2005 John Wiley & Sons, IncRelative PerformanceDepends on network conditionsWork better for smaller networks with low usageWork better for networks with high traffic volumesWhen volume is high, performance deteriorates (too many collisions)Network more efficiently usedCross-over point: About 20 computers12Copyright 2005 John Wiley & Sons, IncError ControlHandling of network errors caused by problems in transmissionNetwork errorse.g., changing a bit value during transmissionControlled by network hardware and softwareHuman errors: e.g., mistake in typing a numberControlled by application programsCategories of Network ErrorsCorrupted (data changed)Lost data13Copyright 2005 John Wiley & Sons, IncError Control (Cont.)Error Rate1 bit error in n bits transmitted, e.g., 1 in 500,000Burst errorMany bits are corrupted at the same timeErrors not uniformly distributede.g., 100 in 50,000,000  1 in 500,000Major functionsPreventing errorsDetecting errorsCorrecting errors 14Copyright 2005 John Wiley & Sons, IncSources of ErrorsLine noise and distortion – major causeMore likely on electrical mediaUndesirable electrical signalIntroduced by equipment and natural disturbancesDegrades performance of a circuitManifestationExtra bits“flipped” bitsMissing bits15Copyright 2005 John Wiley & Sons, IncSource of ErrorWhat causes itHow to prevent itLine Outages Faulty equipment, Storms, Accidents (circuit fails) White Noise (hiss)(Gaussian Noise)Movement of electrons (thermal energy)Increase signal strength (increase SNR)Impulse Noise (Spikes)Sudden increases in electricity (e.g., lightning, power surges)Shield or move the wiresCross-talkMultiplexer guard bands are too small or wires too close togetherIncrease the guard bands, ormove or shield the wiresEcho Poor connections (causing signal to be reflected back to the source)Fix the connections, ortune equipmentAttenuation Gradual decrease in signal over distance (weakening of a signal)Use repeaters or amplifiersIntermodulation NoiseSignals from several circuits combineMove or shield the wiresJitter Analog signals change (small changes in amp., freq., and phase)Tune equipmentHarmonic Distortion Amplifier changes phase (does not correctly amplify its input signal)Tune equipment Sources of Errors and Preventionmostly on analogMore important16Copyright 2005 John Wiley & Sons, IncError DetectionMathematical calculations?=Mathematical calculationsData to be transmittedSender calculates an Error Detection Value (EDV) and transmits it along with dataReceiver recalculates EDV and checks it against the received EDVIf the same  No errors in transmissionIf different  Error(s) in transmissionEDVLarger the size, better error detection (but lower efficiency)17Copyright 2005 John Wiley & Sons, IncError Detection TechniquesParity checksLongitudinal Redundancy Checking (LRC)Polynomial checkingChecksumCyclic Redundancy Check (CRC)18Copyright 2005 John Wiley & Sons, IncParity CheckingOne of the oldest and simplestA single bit added to each characterEven parity: number of 1’s remains evenOdd parity: number of 1’s remains oddReceiving end recalculates parity bitIf one bit has been transmitted in error the received parity bit will differ from the recalculated oneSimple, but doesn’t catch all errors If two (or an even number of) bits have been transmitted in error at the same time, the parity check appears to be correctDetects about 50% of errors19Copyright 2005 John Wiley & Sons, IncExamples of Using Paritysenderreceiver01101010EVEN parityparitynumber of all transmitted 1’s remains EVENTo be sent: Letter V in 7-bit ASCII: 0110101senderreceiver01101011ODD parityparitynumber of all transmitted 1’s remains ODD20Copyright 2005 John Wiley & Sons, IncLRC - Longitudinal Redundancy CheckingAdds an additional character (instead of a bit)Block Check Character (BCC) to each block of dataDetermined like parity but, but counting longitudinally through the message (as well as vertically)Calculations are based on the 1st bit, 2nd bit, etc. (of all characters) in the block1st bit of BCC  number of 1’s in the 1st bit of characters2nd bit of BCC number of 1’s in the 2ndt bit of charactersMajor improvement over parity checking98% error detection rate for burst errors ( > 10 bits)Less capable of detecting single bit errors21Copyright 2005 John Wiley & Sons, IncLetterDATAUsing LRC for Error DetectionNote that the BCC’s parity bit is also determined by parityBCC 1 1 0 1 1 1 1 1Parity bit1101Example: Send the message “DATA” using ODD parity and LRCASCII 1 0 0 0 1 0 0 1 0 0 0 0 0 11 0 1 0 1 0 01 0 0 0 0 0 122Copyright 2005 John Wiley & Sons, IncPolynomial CheckingAdds 1 or more characters to the end of message (based on a mathematical algorithm)Two types: Checksum and CRCChecksumCalculated by adding decimal values of each character in the message, Dividing the total by 255. and Saving the remainder (1 byte value) and using it as the checksum95% effectiveCyclic Redundancy Check (CRC)Computed by calculating the remainder to a division problem: 23Copyright 2005 John Wiley & Sons, IncP / G = Q + R / GCyclic Redundancy Check (CRC)Most powerful and most commonDetects 100% of errors (if number of errors <= size of R)Otherwise: CRC-16 (99.998%) and CRC-32 (99.9999%)Message (treated as one long binary number)A fixed number (determines the length of the R)Remainder:added to the message as EDV) could be 8 bits, 16 bits, 24 bits, or 32 bits longQuotient (whole number)Example:P = 58G = 8Q = 7R = 224Copyright 2005 John Wiley & Sons, IncError CorrectionOnce detected, the error must be correctedError correction techniquesRetransmission (a.k.a, Backward error correction)Simplest, most effective, least expensive, most commonly usedCorrected by retransmission of the dataReceiver, when detecting an error, asks the sender to retransmit the message Often called Automatic Repeat Request (ARQ)Forward Error CorrectionReceiving device can correct incoming messages itself 25Copyright 2005 John Wiley & Sons, IncAutomatic Repeat Request (ARQ)Process of requesting that a data transmission be resentMain ARQ protocolsStop and Wait ARQ (A half duplex technique)Sender sends a message and waits for acknowledgment, then sends the next messageReceiver receives the message and sends an acknowledgement, then waits for the next messageContinuous ARQ (A full duplex technique) Sender continues sending packets without waiting for the receiver to acknowledgeReceiver continues receiving messages without acknowledging them right away26Copyright 2005 John Wiley & Sons, IncStop and Wait ARQSends the packet, then waits to hear from receiver.Sends acknowledgementSends negative acknowledgementResends the packet againSends the next packetSenderReceiver27Copyright 2005 John Wiley & Sons, IncContinuous ARQSender sends packets continuously without waiting for receiver to acknowledgeNotice that acknowledgments now identify the packet being acknowledged. Receiver sends back a NAK for a specific packet to be resent.28Copyright 2005 John Wiley & Sons, IncFlow Control with ARQEnsuring that sender is not transmitting too quickly for the receiverStop-and-wait ARQReceiver sends an ACK or NAK when it is ready (to receive more packets)Continuous ARQ:Both sides agree on the size of the sliding window Number of messages that can be handled by the receiver without causing significant delays)29Copyright 2005 John Wiley & Sons, IncFlow Control Examplereceiversender...3 2 1 0ACK 0......4ACK 4...8 7 6 5ACK 7..set window size to 2..9 ...9 8window size =4 0 1 2 3 4 5 6 7 8 9 (slide window) 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 0 1 2 3 4 5 6 7 8 9 (slide window)(slide window)(timeout)30Copyright 2005 John Wiley & Sons, IncForward Error Correction (FEC)Receiving device can correct incoming messages itself (without retransmission)Requires extra corrective information Sent along with the data Allows data to be checked and corrected by the receiverAmount of extra information: usually 50-100% of the dataUseful for satellite transmissionOne way transmissions (retransmission not possible)Transmission times are very long (retransmission will take a long time)Insignificant cost of FEC (compare to total cost of eq.)31Copyright 2005 John Wiley & Sons, IncHamming Code – An FEC ExampleEach data bit figures into three EVEN parity bit calculationsIf any one bit (parity or data) changes  change in data bit can be detected and correctedOnly works for one bit errors32Copyright 2005 John Wiley & Sons, IncData Link ProtocolsClassificationAsynchronous transmissionSynchronous transmission Differ by Message delineation Frame lengthFrame field structureframe kframe k+1frame k-133Copyright 2005 John Wiley & Sons, IncAsynchronous TransmissionEach character is sent independentlySometimes called start-stop transmissionSent between transmissions (a series of stop bits)Used by the receiver for separating characters and for synch.Used on point-to-point full duplex circuits (used by Telnet when you connect to Unix/Linux computers)34Copyright 2005 John Wiley & Sons, IncAsynchronous File TransferUsed on Point-to-point asynchronous circuitsTypically over phone lines via modemComputer to computer for transfer of data filesCharacteristics of file transfer protocolsDesigned to transmit error-free dataGroup data into blocks to be transmitted (rather sending character by character)Popular File transfer ProtocolsXmodem, Zmodem, and Kermit35Copyright 2005 John Wiley & Sons, IncFile Transfer ProtocolsSOHPacket #Packet # compl. (128 bytes)Checksum Start of Header One of the oldest async file transfer protocol Uses stop-and-wait ARQ.Xmodem-CRC: uses 1 byte CRC (instead of checksum) Xmodem-1K: Xmodem-CRC + 1024 byte long message fieldXmodemZmodemKermit Uses CRC-32 with continuous ARQ Dynamic adjustment of packet size (based on circuit) Very flexible, powerful and popular Typically uses CRC-24 and 1K size, but adjustable36Copyright 2005 John Wiley & Sons, IncSynchronous TransmissionData sent in a large block Called a frame or packetTypically about a thousand characters (bytes) longIncludes addressing informationEspecially useful in multipoint circuits Includes a series of synchronization (SYN) characters Used to help the receiver recognize incoming dataSynchronous transmission protocols categoriesBit-oriented protocols: SDLC, HDLCByte-count protocols: EthernetByte-oriented protocols: PPP37Copyright 2005 John Wiley & Sons, IncSDLC – Synchronous Data Link ControlDestination Address (8 or 16 bits)Identifies frame type; Information (for transferring of user data) Supervisory (for error and flow control)dataCRC-32Ending(01111110)Beginning(01111110) Bit-oriented protocol developed by IBM Uses a controlled media access protocol38Copyright 2005 John Wiley & Sons, IncTransparency Problem of SDLCProblem: TransparencyUser data may contain the same bit pattern as the flags (01111110)Receiver may interpret it as the end of the frame and ignores the restSolution: Bit stuffing (aka, zero insertion)Sender inserts 0 anytime it detects 11111 (five 1’s)If receiver sees five 1's, checks next bit(s)if 0, remove it (stuffed bit)if 10, end of frame marker (01111110)if 11, error (7 1's cannot be in data)Works but increases complexity39Copyright 2005 John Wiley & Sons, IncHDLC – High-Level Data Link ControlFormal standard developed by ISOSame as SDLC, exceptLonger address and control fieldsLarger sliding window sizeAnd moreBasis for many other Data Link Layer protocolsLAP-B (Link Accedes Protocol – Balanced) Used by X.25 technologyLAP-D (Link Accedes Protocol – Balanced)Used by ISDN technologyLAP- F (Used by Frame Relay technology)40Copyright 2005 John Wiley & Sons, IncEthernet (IEEE 802.3)Most widely used LAN protocol, developed jointly by Digital, Intel, and Xerox, now an IEEE standardUses contention based media access controlByte-count data link layer protocolNo transparency problem uses a field containing the number of bytes (not flags) to delineate framesError correction: optional41Copyright 2005 John Wiley & Sons, IncEthernet (IEEE 802.3) Frame(number of bytes in the message field)Data(43 - 1497 bytes)Repeating pattern of 1’s and 0’s (1010101010)Used by Virtual LANs; (if no vLAN, the field is omittedIf used, first 2 bytes is set to: 24,832 (8100H)Used to exchange control info (e.g., type of network layer protocol used)Used to hold sequence number, ACK/NAK, etc., (1 or 2 bytes)0001101142Copyright 2005 John Wiley & Sons, IncPoint-to-Point Protocol (PPP)Byte-oriented protocol developed in early 90sCommonly used on dial-up lines from home PCsDesigned mainly for point-to-point phone line (can be used for multipoint lines as well) (up to 1500 bytes)Specifies the network layer protocol used (e.g, IP, IPX)43Copyright 2005 John Wiley & Sons, Inc  ProtocolSizeError DetectionRetransmissionMedia AccessAsynchronous Xmission1ParityContinuous ARQFull Duplex     File Transfer Protocols    XMODEM1328-bit ChecksumStop-and-wait ARQControlled AccessXMODEM-CRC1328-bit CRCStop-and-wait ARQControlled AccessXMODEM-1K10288-bit CRCStop-and-wait ARQControlled AccessZMODEM*32-bit CRCContinuous ARQControlled AccessKERMIT*24-bit CRCContinuous ARQControlled Access     Synchronous Protocols    SDLC *16-bit CRCContinuous ARQControlled AccessHDLC *16-bit CRCContinuous ARQControlled AccessToken Ring*32-bit CRCStop-and wait ARQControlled AccessEthernet*32-bit CRCStop-and wait ARQContentionSLIP*NoneNoneFull DuplexPPP*16-bit CRCContinuous ARQFull Duplex* Varies depending on message length.Data Link Protocol Summary44Copyright 2005 John Wiley & Sons, IncTransmission EfficiencyAn objective of the network:Move as many bits as possible with min errors  higher efficiency and lower costFactors affecting network efficiency:Characteristics of circuit (error rate, speed)Speed of equipment, Error control techniquesProtocol usedInformation bits (carrying user information)Overhead bits ( used for error checking, frame delimiting, etc.)Total number of info bits to be transmittedTotal number of bits transmitted=45Copyright 2005 John Wiley & Sons, IncTransmission Efficiency of ProtocolsAsync Transmission: 7-bit ASCII (info bits), 1 parity bit, 1 stop bit, 1 start bit Transmission Efficiency = 7 / 10  70% e.g., V.92 modem with 56 Kbps  39.2 Kbps effective rateSDLC Transmission Assume 100 info characters (800 bits), 2 flags (16 bits) Address (8 bits), Control (8 bits), CRC (32 bits) Transmission Efficiency = 800 / 64  92.6% e.g., V.92 modem with 56 Kbps  51.9 Kbps effective rateBigger the message length, better the efficiencyHowever, large packets likely to have more errors (more likely to require retransmission)  wasted capacity46Copyright 2005 John Wiley & Sons, IncThroughputA more accurate definition of efficiencyTotal number of information bits received per second; takes into account:Overhead bits (as in transmission efficiency) Need to retransmit packets containing errors Complex to calculate; depends onTransmission efficencyError rateNumber of retransmissionTransmission Rate of Information Bits (TRIB)Used as a measurement of throughput47Copyright 2005 John Wiley & Sons, IncOptimum Packet SizeTrade-off between packet size and throughput(more costly in terms of circuit capacity to retransmit if there is an error)(less likely to contain errors)Acceptable range48Copyright 2005 John Wiley & Sons, IncTRIBK (M – C) (1 – P)(M / R) + TInfo bits per characterAverage number of non-info characters per blockProbability that a block will require retransmissionTime between blocks (in seconds) (propagation time + turnaround time) (a.k.a., reclocking time)Packet length in charactersData xmission rate in char per second = Number of info bits accepted / total time required to get the bits (number of info bits) (Prob. Of successful xmission) time it takes to transmit these bits + propagation delay TRIB =Ex:K=7 bits/characterM = 400 char/blockR= 4.8 Kb/sC = 10 char/blockP = 1%T = 25 ms7(400-10)(1-0.01)(400/600)+0.025)= 3.908 Kb/sTRIB =49Copyright 2005 John Wiley & Sons, IncImplications for ManagementProvide a few, widely used data link layer protocols for all networksMinimize costly customizationMinimize costly translation among many protocolsLess training, simpler network managementBigger pool of available expertsLess expensive, off-the-shelf equipment50Copyright 2005 John Wiley & Sons, IncCopyright 2005 John Wiley & Sons, Inc. All rights reserved. Reproduction or translation of this work beyond that permitted in section 117 of the 1976 United States Copyright Act without express permission of the copyright owner is unlawful. Request for further information should be addressed to the Permissions Department, John Wiley & Sons, Inc. The purchaser may make back-up copies for his/her own use only and not for distribution or 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 herein. 51Copyright 2005 John Wiley & Sons, Inc