DATA LINK CONTROL
• servicesprovidedbytheDLCsublayer • simpleandcommondata-linkprotocols • HDLCprotocol
Copyright By PowCoder代写 加微信 powcoder
Framing Service
• Thedata-linklayerneedstopackbitsintoframes,so that each frame is distinguishable from another
• Framinginthedata-linklayerseparatesamessage from one source to a destination by adding a sender address and a destination address
– destination address defines where the packet is to go;
– sender address helps the recipient acknowledge the receipt.
• Framescanbeoffixedorvariablesize
Frame Size
• Infixed-sizeframing,thereisnoneedfordefiningthe boundaries of the frames; the size itself can be used as a delimiter
– example of this type of framing is the ATM WAN, which uses frames of fixed size called cells
• Variable-sizeframingisprevalentinlocal-areanetworks
• Variable-sizeframingneedawaytodefinetheendof
one frame and the beginning of the next.
• Historically,twoapproacheswereusedforthispurpose:
– a byte-oriented approach and – a bit-oriented approach
byte-oriented framing
• datatobecarriedare8-bitcharactersfromacoding system such as ASCII
• Theheader,whichnormallycarriesthesourceand destination addresses and other control information, and the trailer, which carries error detection redundant bits, are also multiples of 8 bits
• Toseparateoneframefromthenext,an8-bit(1-byte) flag is added at the beginning and the end of a frame
• Flag is composed of protocol-dependent special characters, signals the start or end of a frame
byte-oriented framing
• Character-orientedframingwaspopularwhenonlytext was exchanged by the data-link layers.
• Theflagcouldbeselectedtobeanycharacternotused for text communication.
• Nowwesendothertypesofinformationsuchasgraphs, audio, and video; any character used for the flag could also be part of the information.
– If this happens, the receiver, when it encounters this pattern in the middle of the data, thinks it has reached the end of the frame
– To fix this problem, a byte-stuffing strategy was added to character-oriented framing
Byte-stuffing
• Inbytestuffing(orcharacterstuffing),aspecialbyteis added to the data section of the frame when there is a character with the same pattern as the flag. The data section is stuffed with an extra byte. This byte is usually called the escape character (ESC) and has a predefined bit pattern
• WheneverthereceiverencounterstheESCcharacter,it removes it from the data section and treats the next character as data, not as a delimiting flag
Byte-stuffing
byte-oriented framing
• Character-orientedprotocolspresentanotherproblemin data communications.
• Theuniversalcodingsystemsinusetoday,suchas Unicode, have 16-bit and 32-bit characters that conflict with 8-bit characters.
• Wecansaythat,ingeneral,thetendencyismoving toward the bit-oriented protocols
bit-oriented framing
Inbit-orientedframing,thedatasectionofaframeisa sequence of bits to be interpreted by the upper layer as text, graphic, audio, video, and so on
in addition to headers (and possible trailers), we still need a delimiter to separate one frame from the other.
Mostprotocolsuseaspecial8-bitpatternflag, 01111110, as the delimiter to define the beginning and the end of the frame
bit-oriented framing
• Thisflagcancreatethesametypeofproblemwesawin the character-oriented protocols
• iftheflagpatternappearsinthedata,weneedto somehow inform the receiver that this is not the end of the frame
• Thestrategyiscalledbitstuffing.
– if a 0 and five consecutive 1 bits are encountered, an extra 0 is added
– This extra stuffed bit is eventually removed from the data by the receiver
Bit-stuffing
Data Link Protocols
• Traditionallyfourprotocolshavebeendefinedforthe data-link layer to deal with flow and error control:
– Stop-and-Wait, – Go-Back-N, and – Selective-Repeat
• Although the first two protocols still are used at the data-link layer, the last two have disappeared (moved to transport layer!)
Simple Protocol – FSM
• simple protocol neither support flow nor error control
– assumethatthereceivercanimmediatelyhandle any frame it receives
Simple Protocol – Example
• example of communication using this protocol. It is very simple. The sender sends frames one after another without even thinking about the receiver
Stop-and-Wait Protocol
• Stop-and-Waitprotocolusesbothflowanderrorcontrol
• the sender sends one frame at a time and waits for an acknowledgment before sending the next one
• Todetectcorruptedframes,weneedtoaddaCRCto each data frame
• Whenaframearrivesatthereceiversite,itischecked. If its CRC is incorrect, the frame is corrupted and silently discarded. The silence of the receiver is a signal for the sender that a frame was either corrupted or lost
• Also called Stop-and-Wait Automatic Repeat Request (ARQ)
Stop-and-Wait Protocol
Everytimethesendersendsaframe,itstartsatimer. If an acknowledgment arrives before the timer expires, the timer is stopped and the sender sends the next frame (if it has one to send). If the timer expires, the sender resends the previous frame, assuming that the frame was either lost or corrupted
the sender needs to keep a copy of the frame until its acknowledgment arrives
Sender FSM
• Ready State: When the sender is in this state, it is only
waiting for a packet from the network layer
• Blocking State: When the sender is in this state, three events can occur:
1. Ifatime-outoccurs,thesenderresendsthesaved copy of the frame and restarts the timer.
2. IfacorruptedACKarrives,itisdiscarded.
3. Ifanerror-freeACKarrives,thesenderstopsthe timer and discards the saved copy of the frame. It then moves to the ready state
Receiver FSM
• Thereceiverisalwaysinthereadystate. • Twoeventsmayoccur:
1. Ifanerror-freeframearrives,themessageinthe frame is delivered to the network layer and an ACK is sent.
2. Ifacorruptedframearrives,theframeisdiscarded
Notice duplicate frame received But not detected
Using Sequence & Ack Numbers
there is a problem with the previous scheme. The network layer at the receiver site receives two copies of the third packet, which is not right.
WecanchangetheFSMtoincludethesequenceand acknowledgment numbers to be able to detect duplicate frames – see figure
Using Sequence & Ack Numbers
Piggybacking
• Thetwoprotocolswediscussedinthissectionare designed for unidirectional communication, in which data is flowing only in one direction although the acknowledgment may travel in the other direction
• tomakethecommunicationmoreefficient,thedatain one direction is piggybacked with the acknowledgment in the other direction
High-level Data Link Control (HDLC)
• HDLC is a bit-oriented protocol for communication over
point-to-point and multipoint links.
• ItimplementstheStop-and-Waitprotocol
• Althoughthisprotocolismoreatheoreticalissuethan practical, most of the concept defined in this protocol is the basis for other practical protocols such as PPP, or the Ethernet protocol, or in wireless LANs
Configurations and Transfer Modes
• HDLCprovidestwocommontransfermodesthatcanbe used in different configurations:
– normal response mode (NRM)
the station configuration is unbalanced one primary station and multiple secondary
primary station can send commands; a secondary station can only respond
– asynchronous balanced mode (ABM)
link is point-to-point, and each station can function as a primary and a secondary (peers)
normal response mode (NRM)
asynchronous balanced mode (ABM)
HDLC Framing
• HDLCdefinesthreetypesofframes: – information frames (I-frames),
used to data-link user data and control information relating to user data (piggybacking)
– supervisory frames (S-frames)
used only to transport control information
– unnumbered frames (U-frames)
intended for managing the link itself
HDLC Framing
HDLC Frame Fields
• Flag field: This field contains synchronization pattern 01111110, which identifies both the beginning and the end of a frame
• Address field: This field contains the address of the secondary station (to/from address)
• Control field. The control field is one or two bytes used for flow and error control
• Information field: The information field contains the user’s data from the network layer or management information. Its length can vary from one network to another
• FCS field: The frame check sequence (FCS) is the HDLC error detection field, 2- or 4-byte CRC
Control field format
Control Field for I-Frames
• Startswith0
• 3bitN(S):sequencenumberofsender
• 3bitN(R):sequencenumberofreceiver(piggybacked)
• P/F:whensetto1,meanseitherpollthis(from primary), or final answer (from secondary)
– a.k.a. valid bit
Control Field for S-Frames
• Startswith10
• 3bitN(R):correspondtotheacknowledgmentnumber (ACK) or negative acknowledgment number (NAK), depending on the type of S-frame
• 2bitscalledcodeareusedtodefinethetypeofS-frame itself
Control Field for S-Frames
• 00 – Receive ready (RR): acknowledges the receipt of a safe and sound frame or group of frames. In this case, the value of the N(R) field defines the acknowledgment number
• 10 – Receive not ready (RNR): acknowledges the receipt of a frame or group of frames, and it announces that the receiver is busy and cannot receive more frames. It acts as a kind of congestion-control mechanism by asking the sender to slow down. The value of N(R) is the acknowledgment number
Control Field for S-Frames
• 01 – Reject (REJ): This is a NAK frame, The value of
N(R) is the negative acknowledgment number
• 11 – Selective reject (SREJ): This is a NAK frame used in Selective Repeat ARQ. The value of N(R) is the negative acknowledgment number
Control Field for U-Frames
• Startswith11
• Unnumberedframesareusedtoexchangesession management and control information between connected devices
• usedforsystemmanagementinformation,notuser data
• two segments (5 bits) can be used to create up to 32 different types of U-frames
Control Field for U-Frames
• ShowinghowU-framescanbeusedforconnection establishment and connection release.
• NodeAasksforaconnectionwithasetasynchronous balanced mode (SABM) frame; node B gives a positive response with an unnumbered acknowledgment (UA) frame. After these two exchanges, data can be transferred between the two nodes (not shown in the figure). After data transfer, node A sends a DISC (disconnect) frame to release the connection; it is confirmed by node B responding with a UA (unnumbered acknowledgment).
Example of connection & disconnection
• a)showsanexchangeusingpiggybacking.NodeA begins the exchange of information with an I-frame numbered 0 followed by another I-frame numbered 1.
• b)showsanexchangeinwhichaframeislost.NodeB sends three data frames (0, 1, and 2), but frame 1 is lost.
References
• DataCommunicationsandNetworking5thedition– 2013, Behrouz A. Forouzan; Chapter 11
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com