Data Link Control & Protocols
Textbook: Ch.11
SEHH2238: Computer Networking
SEHH2238 Lecture 4 1
Copyright By PowCoder代写 加微信 powcoder
SEHH2238: Computer Networking
11.1 Flow And Error Control
Main Topics
11.2 Stop-and-Wait
Implicit Retransmission and ARQ Error-control
Piggybacking
11.3 Framing with HDLC
High-level Data Link Control
11.1 Bit stuffing
SEHH2238 Lecture 4 2
SEHH2238: Computer Networking
Data Link Control
WCB/McGraw-Hill
SEHH2238 Lecture 4 3
SEHH2238: Computer Networking
Flow Control
Balance between the sending rate and receiving rate
If sender transmits faster than the receiver can handle – data lost
If sender transmits too slow, receiver has to wait – less efficient
Flow control is related to the first issue
Prevent data lost
Sender waits for acknowledgement (ACK) from receiver
SEHH2238 Lecture 4 4
SEHH2238: Computer Networking
Flow control Mechanisms
Stop and Wait ARQ
Go-Back-N ARQ
WCB/McGraw-Hill
(Details in Lecture 9) SEHH2238 Lecture 4 5
Selective Repeat ARQ
SEHH2238: Computer Networking
Error Control
Error detection by CRC or FCS
Error correction by retransmission
If error is detected, a negative acknowledgment (NAK) is returned and the specified frames are resent.
If no error, receiver sends acknowledgment (ACK) to sender, sender sends next frame
If no ACK is received after a period of time, sender retransmits
SEHH2238 Lecture 4 6
SEHH2238: Computer Networking
Error Control
Automatic Repeat Request (ARQ) does not use NAK
Implicit retransmission in ARQ
Receiver discards the error frame and does
Sender interprets the absence of an ACK (after a timeout) as an indication that the previous frame was corrupted or lost
SEHH2238 Lecture 4 7
SEHH2238: Computer Networking
Flow control and Error control
Can be combined
Acknowledgement is used in both control
Sender waits for ACK to transmit the next frame Receiver uses ACK to confirm no error
Sender retransmits if no ACK is received
Stop-and-Wait ARQ
The simplest protocol for flow and error control
SEHH2238 Lecture 4 8
SEHH2238: Computer Networking
Stop-and-Wait ARQ
The sender sends one frame and waits for an ACK before sending the next frame
If no ACK is received after a period of time (timeout), the sender retransmits
Implicit retransmission in ARQ Advantage: Simple
Disadvantage: Inefficient
SEHH2238 Lecture 4 9
SEHH2238: Computer Networking
Normal Situation
EOT = End of Transmission
SEHH2238 Lecture 4 10
SEHH2238: Computer Networking
If ACK is lost…
SEHH2238 Lecture 4
New or resent?
SEHH2238: Computer Networking
Sequence Number
Use 1 bit sequence number to distinguish the frame is newly transmitted or resent of previous frame
ACK confirms the correct receive of frame
ACK also contains the sequence number of
the expected frame
Sender knows what frame the receiver is expecting
SEHH2238 Lecture 4 12
SEHH2238: Computer Networking
Normal Operation
SEHH2238 Lecture 4 13
SEHH2238: Computer Networking
Normal Operation
Sender can have only one frame ready to send at a time
When sender initiates a transmission of a frame, it starts a timer
If the frame is received without error, the receiver sends ACK
If sender receives ACK, it sends another frame
SEHH2238 Lecture 4 14
SEHH2238: Computer Networking
Implicit Retransmission
Receiver discards the frame if it contains errors No ACK is sent
If sender does not receive an ACK within a predefined time-out interval, it retransmits the frame in the buffer
Receiver checks the frame identifier (sequence number)
Accept if it is the expecting frame
Discard if the frame has been correctly received previously
Need to send ACK?
SEHH2238 Lecture 4 15
SEHH2238: Computer Networking
Buffer in Sender
Error correction in Stop-and-Wait ARQ is done by keeping a copy of the sent frame
Sender maintains a buffer with size = 1 frame
Sender may not receive ACK because
Receiver detects error in the frame
The frame is lost before it reaches the receiver The ACK is lost, delayed or corrupted
Retransmitting the frame in the buffer when the timer expires
SEHH2238 Lecture 4 16
SEHH2238: Computer Networking
Stop-and-Wait ARQ, lost frame
SEHH2238 Lecture 4 17
SEHH2238: Computer Networking
Stop-and-Wait ARQ, delayed ACK
SEHH2238 Lecture 4 18
SEHH2238: Computer Networking
Piggybacking
For bidirectional transmission
The technique of temporarily delaying outgoing ACKs so that they can be hooked onto the next outgoing data frame
A way of improving link utilization
Normally most links using continuous ARQ are full-duplex and carry data frames in both directions
Each side contains both a sender & a
SEHH2238 Lecture 4 19
SEHH2238: Computer Networking
Piggybacking
SEHH2238 Lecture 4 20
SEHH2238: Computer Networking
Data Link Protocols
• Asynchronous protocols, used primarily in modems, use start and stop bits and variable length gap between characters
• Due to slow data rate, they are being replaced by higher-speed synchronous protocols
SEHH2238 Lecture 4 21
WCB/McGraw-Hill The McGraw-Hill Companies, Inc.,
SEHH2238: Computer Networking
Synchronous Protocols
In character-oriented protocols, the frame is interpreted as a series of characters
8-bit (e.g. ASCII), popular in old days with only text
In bit-oriented protocols, each bit or groups of bits
can have meaning
SEHH2238 Lecture 4 22
WCB/McGraw-Hill The McGraw-Hill Companies, Inc.,
SEHH2238: Computer Networking
Bit-oriented Protocols
Protocols use predefined bit patterns rather than transmission control characters to signal the start and end of a frame. (frame delimiting)
The receiver searches the received bit stream on a bit by bit basis for the known start and end of frame bit pattern.
E.g. HDLC
SEHH2238 Lecture 4 23
SEHH2238: Computer Networking
High-level Data Link Control (HDLC)
an ISO international standard used on both point to point and multipoint (multidrop) data links
supports both half-duplex and full-duplex with error detection
adopts continuous ARQ with window mechanism
used extensively in computer networks
But many large manufacturers still use their own protocols similar to HDLC, e.g.,
IBM’s SDLC (synchronous data link control) SEHH2238 Lecture 4 24
SEHH2238: Computer Networking
HDLC Frame Formats
Both data & control messages are carried in a standard format block
SEHH2238 Lecture 4 25
SEHH2238: Computer Networking
HDLC Frame Formats
Flag field
(01111110) indicates start & end of a frame
Address Field
Address of the station receiving the frame
Control Field
For flow and error control (more details later)
Information Field
Contains user’s data from upper layer
Frame Check Sequence (FCS) Field For error checking similar to CRC
SEHH2238 Lecture 4 26
SEHH2238: Computer Networking
HDLC Frame Types
Information frames (I-frames) carry actual data
also act as piggyback ACK
Supervisory frames (S-frames) for transporting control information
Unnumbered frames (U-frames)
for link set-up and disconnection
SEHH2238 Lecture 4 27
SEHH2238: Computer Networking
HDLC frame types
SEHH2238 Lecture 4 28
SEHH2238: Computer Networking
Data transparency
Data can be any combination of bits
Confusion between control information and
data is called a lack of data transparency E.g. data field contains 01111110
SEHH2238 Lecture 4 29
SEHH2238: Computer Networking
Data transparency
when data are transparent, which means we should be able to send any combination of bits as data
Bit Stuffing method is used in HDLC for achieving data transparency
SEHH2238 Lecture 4 30
SEHH2238: Computer Networking
Bit Stuffing
A method used in HDLC for achieving data transparency
Ensure that the flag pattern is not present in the frame contents
Sender inserts a “0” bit after transmitting five consecutive “1” bits
Exceptions: when the bit sequence is really a flag
Receiver removes the “0” bit after receiving five consecutive “1” bits
SEHH2238 Lecture 4 31
SEHH2238: Computer Networking
Bit stuffing and removal
SEHH2238 Lecture 4 32
SEHH2238: Computer Networking
Flow Control and Error Control
Stop-and-Wait ARQ
High-level Data Link Control (HDLC) Bit stuffing
Revision Quiz
http://highered.mheducation.com/sites/0073376
221/student_view0/chapter11/quizzes.html
SEHH2238 Lecture 4 33
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com