Asynchronous And Synchronous William Stallings .

William StallingsData and ComputerCommunicationsChapter 6- 7The Data CommunicationsInterface, Data Link ControlAsynchronousAsynchronous and SynchronousTransmissionz Timing problems require a mechanism tosynchronize the transmitter and receiverz Two solutionsy Asynchronousy SynchronousAsynchronous (diagram)z Data transmitted one character (7 -8 bits) at atimez Timing only needs maintaining within eachcharacterz Resync with each characterz Also called start -stop transmission, because wewill have a start/stop bit around each character,or “frame”Framing error1

Asynchronous File TransferProtocolsAsynchronous - Behaviorz In a steady stream, interval between characters isuniform (length of stop element)z In idle state, receiver looks for transition 1 to 0z Then samples next seven intervals (char length)z Then looks for next 1 to 0 for next charOlder microcomputer file transfer protocols usedasynchronous point-t o-point circuits, typicallyacross telephone lines via a modem.y XMODEMx XMODEM-CRC (CRC- 8)x XMODEM-1K (CRC 1K blocks)z Simple, cheapz Transmission Efficiency #Info Bits / #Total Bitsy With parity, Efficiency 7 / 10 (start, stop, parity bit)y 70% Efficiency or 30% Overheady Without parity, 20% overhead (8- N-1) – Eight data bits, Noparity, 1 stop bitAsynchronous File TransferExampley YMODEM(CRC-16)y ZMODEM (CRC-32)y KERMIT (CRC-24)Synchronous - Bit Levelz Block of data transmitted without start or stopbitsXMODEM FORMATz Clocks must be synchronizedz Can use separate clock liney Good over short distancesy Subject to impairmentsSTX1 bytePacket#compliment1 byteMessage128 bytesChecksum1 bytez Embed clock signal in datay Manchester encodingPacket #1 byte2

Synchronous (diagram)Synchronous - Block Levelz Need to indicate start and end of blockz Use preamble and postambley e.g. series of SYN (hex 16) charactersy e.g. block of 11111111 patterns ending in 11111110z More efficient (lower overhead) than async for largeblocks of datay Consider a block that requires 8 bytes of overhead (preamble,postamble, other bookkeeping) with 100 information characters,or 800 bits.y Transmission Efficiency 800 / 800 64 92.6% efficiencyy Efficiency goes up the larger our blocks are, assuming theoverhead bytes stay the same. Why not make our blocks evenbigger?Transmission EfficiencyRest of Chapter 6z Skip rest of chapter 6 (Interfacing, Pinouts)3

Chapter 7 - Flow Control / ErrorDetection, CorrectionModel of Frame Transmissionz Flow Controly Ensuring the sending entity does not overwhelm thereceiving entityx Preventing buffer overflowy Factorsx Transmission time - Time taken to emit all bits into mediumx Propagation time - Time for a bit to traverse the linkStop and WaitFragmentationz Simplest form of flow controlz Large block of data may be split into smallframesz Source transmits framez Destination receives frame and replies withacknowledgementz Source waits for ACK before sending next framez Destination can stop flow by not sending ACKz Works well for a few large framesyyyyLimited buffer sizeErrors detected sooner (when whole frame received)On error, retransmission of smaller frames is neededPrevents one station occupying medium for longperiodsz Stop and wait becomes inadequatey Only one frame at a time “in transit”y Latency for each ACK4

Stop and Wait Link UtilizationSliding Windows Flow Controlz Allow multiple frames to be in transitz Receiver has buffer W longz Transmitter can send up to W frames withoutACKz Each frame is numberedz ACK includes number of next frame expectedz Sequence number bounded by size of field (k)y Frames are numbered modulo 2kSliding Window DiagramExample Sliding WindowRR N Receive Ready on N5

Sliding Window EnhancementsError Detectionz Receiver can acknowledge frames withoutpermitting further transmission (Receive NotReady)z Must send a normal acknowledge to resumez If duplex, need two windows, one for transmitand one for receivez Additional bits added by transmitter for errordetection codey Piggybacking – if sending data and acknowledgementframe, combine togetherz Parityy Value of parity bit is such that character has even(even parity) or odd (odd parity) number of onesy Even number of bit errors goes undetectedz More efficient than stop -and-wait since manyframes may be in the pipelinePolynomial CheckingPolynomial checking adds 1 or more characters to theend of the message based on a mathematicalalgorithm.With checksum, 1 byte is added to the end of themessage. It is obtained by summing the messagevalues,and dividing by 255. The remainder is thechecksum. (95% effective)With CRC (Cyclic Redundancy Check), 8, 16, 24 or 32bits are added, computed by calculating aremainder to a division problem. (99.969% with 8 bit, 99.99% with 16 bit).Error Controlz Detection and correction of errorsz Lost framesz Damaged framesz Automatic Repeat reQuest (ARQ)yyyyError detectionPositive acknowledgmentRetransmission after timeoutNegative acknowledgement and retransmission6

Automatic Repeat Request(ARQ)z Stop and waitz Go back Nz Selective reject (selective retransmission)Stop and Wait ARQz Source transmits single framez Wait for ACKz If received frame damaged, discard ity Transmitter has timeouty If no ACK within timeout, retransmitz If ACK damaged,transmitter will not recognize ity Transmitter will retransmity Receive gets two copies of framey Use ACK0 and ACK1; frames alternate with tag of 0 or 1 todistinguish lost ACK vs. new framez Simple technique, but inefficient due to Stop and WaitStop and Wait DiagramGo Back N (1)z Based on sliding windowz If no error, ACK as usual with next frameexpectedz Use window to control number of outstandingframesz If error, reply with rejectiony Discard that frame and all future frames until errorframe received correctlyy Transmitter must go back and retransmit that frameand all subsequent frames7

Go Back N - Damaged FrameGo Back N - Lost Frame (1)z Receiver detects error in frame iz Receiver sends rejection-iz Frame i lostz Transmitter sends i 1z Transmitter gets rejection-iz Transmitter retransmits frame i and allsubsequentz Receiver gets frame i 1 out of sequencez Receiver send reject iGo Back N - Lost Frame (2)z Frame i lost and no additional frame sentz Receiver gets nothing and returns neitheracknowledgement nor rejectionz Transmitter times out and sendsacknowledgement frame with P bit set to 1z Receiver interprets this as command which itacknowledges with the number of the nextframe it expects (frame i )z Transmitter then retransmits frame iz Transmitter goes back to frame i andretransmitsGo Back N - DamagedAcknowledgement / Rejectz Receiver gets frame i and sendacknowledgement (i 1) which is lostz Acknowledgements are cumulative, so nextacknowledgement (i n) may arrive beforetransmitter times out on frame iz If transmitter times out, it sendsacknowledgement with P bit set as beforez This can be repeated a number of times beforea reset procedure is initiated8

Go Back N DiagramSelective Rejectz Also called selective retransmissionz Only rejected frames are retransmitted (butreceiver still sends back ACKs )z Subsequent frames are accepted by the receiverand bufferedz Minimizes retransmissionz Receiver must maintain large enough bufferz More complex login in transmitterSelective Reject DiagramHigh Level Data Link Controlz HDLCz ISO 33009, ISO 4335z Model Protocoly Variants are used in practicey SDLC – Synchronous Data Link Control, IBM 1972. Used withSNA at the network layery LAPB – Link Access Procedure Balanced, used with X.25y LAPD – Link Access Procedure, D-Channel, used with ISDNy LAPF – Link Access Procedure, Frame-Mode), used with FrameRelayy Skip basic characteristics of modes 9

Frame StructureFrame Structure Diagramz Synchronous transmissionz All transmissions in framesz Single frame format for all data and controlexchangesz Bit-oriented ProtocolFlag FieldszzzzzDelimit frame at both ends01111110May close one frame and open anotherReceiver hunts for flag sequence to synchronizeBit stuffing used to avoid confusion with data containing01111110 Flag 01111110, with bit stuffing Address Station Address, included for uniformity onPoint to Point Control ARQ, Flow control, Frame Type Information Data to transmit FCS Frame Check Sequence, CRC16 or CRC32 forerror controlAddress Fieldz Identifies secondary station that sent or willreceive framez All ones (11111111) is broadcasty If sender wants to send six 1’s as data then it really sends five1’s and then a 0, followed by a 1: 1111101y Receiver needs logic to check the next bit after 5 bits arereceived. If it is 0, then the 0 is deleted and the next bit isread.y If receiver reads 1 and seventh bit is 0, accept as flagy Known as the transparency problem10

Control FieldControl Field Diagramz Different for different frame typey Information - data to be transmitted to user (nextlayer up)x Flow and error control piggybacked on information framesy Supervisory - ARQ when piggyback not usedy Unnumbered - supplementary link controlz First one or two bits of control filed identifyframe typePoll/Final BitInformation Fieldz Use depends on contextz Command framez Only in information and some unnumberedframesy P bity 1 to solicit (poll) response from peerz Must contain integral number of octetsz Variable lengthz Response framey F bity 1 indicates response to soliciting command11

Frame Check Sequence FieldHDLC Operationz FCSz Error detectionz Exchange of information, supervisory andunnumbered framesz 16 bit CRCz Optional 32 bit CRCz Three phasesy Initializationy Data transfery DisconnectOther DLC Protocols(LAPB,LAPD)Other DLC Protocols (LLC)z Link Access Procedure, Balanced (LAPB)z Logical Link Control (LLC)y Part of X.25 (ITU-T)y Subset of HDLC - ABMy Point to point link between system and packetswitching network nodez Link Access Procedure, D-ChannelyyyyISDN (ITU-D)ABMAlways 7-bit sequence numbers (no 3-bit)16 bit address field contains two sub-addressesyyyyIEEE 802 - Token Ring, EthernetDifferent frame formatNo primary and secondary - all stations are peersTwo addresses neededx Sender and receivery Error detection at Medium Access (MAC) layerx 32 bit CRCy Destination and source access points (DSAP, SSAP)x One for device and one for user (next layer up)12

Other Data Link Protocolsz Token Ring (IEEE 802.5) was developed by IBMin the early 1980s, and later became a formalstandard of the IEEE. It uses a controlledaccess media access protocol.z Ethernet (IEEE 802.3) is a byte -count protocol,because instead of using special characters orbit patterns to mark the end of a packet itincludes a field that specifies the length of themessage portion of the packet.y More on Ethernet later when we cover LANs!Other DLC Protocols(Frame Relay) (1)z Streamlined capability over high speed packetwitched networksz Used in place of X.25z Uses Link Access Procedure for Frame-ModeBearer Services (LAPF)z Two protocolsy Control - similar to HDLCy Core - subset of controlSynchronous Transmission802.XToken Ring formatStartFrame Destinationdelimitercontrol addressAccesscontrol1 heck sequence4 bytesEthernet formatDestinationaddress6 bytesSourceaddress6 bytesLength2 bytesMessagevariableCRC- 324 bytesOther DLC Protocols (ATM)z Asynchronous Transfer Modez Streamlined capability across high speednetworksz Not HDLC basedz Frame format called “cell”z Fixed 53 octet (424 bit)z Details later13