Data Communication and Networking - Chapter 3: Data Link Layer Protocols - Vo Que Son

Nội dung text: Data Communication and Networking - Chapter 3: Data Link Layer Protocols - Vo Que Son

1. Data Communication and Networking Dr. –Ing. Vo Que Son Email: sonvq@hcmut.edu.vn Telecomm. Dept. DCN 1 Faculty of EEE HCMUT
2. Framing The data link layer needs to pack bits into frames, so that each frame is distinguishable from another. Fixed-Size Framing Variable-Size Framing Telecomm. Dept. DCN 3 Faculty of EEE HCMUT
3. Error Control Forward Error Control (FEC) Usually used in real-time application (e.g. voice, video) Accept errors if can not correct List some FEC methods? Error Detection + ARQ (Automatic Retransmission Request) Require absolutely correct data transmission Used in non real-time application (e.g. email, file transmission) 2 basic ARQ protocols: • Idle RQ: Bisync (IBM), XModem • Continuous RQ: – Go-back N: e.g. HDLC, V.42 – Selective-Repeat: TCP, Service Specific Connection Oriented Protocol Telecomm. Dept. DCN 5 Faculty of EEE HCMUT
4. Idle RQ  Principle:  P can have only 1 I-frame outstanding (awaiting for an ACK) at a time  On receipt of an error-free ACK frame, P transmits another I-frame  If S receives an I-frame or P receives an ACK containing transmission error: the frame is discarded  If P does not receive an ACK within a given timeout interval: retransmits the waiting I-frame  If an ACK is corrupted, the S receives another copy of the frame and it is rejected by S. Telecomm. Dept. DCN 7 Faculty of EEE HCMUT
5. Idle RQ Advantages : Send and Wait (Stop and Wait) Small buffers: both P and S keeps only 1 frame Disadvantages: Low link utilization Used in transmission of printable characters Half-duplex applications Notation: N(S): send sequence number N(R): receive sequence number Telecomm. Dept. DCN 9 Faculty of EEE HCMUT
6. Idle-RQ  Remember: Tp a= (length of the link in bits) Tix . If a Tp ): when 1st transmitted bit reaches S, P will still be transmitting. Hence U is close 100% . If a > 1 (i.e. Tix 1 where a << 1 (long frames compared to propagation time) Telecomm. Dept. DCN 11 Faculty of EEE HCMUT
7. Idle-RQ  Number of transmissions: Pf 1 N=1+=r 1-P1-Pff  Utilization: 1-P U= f (1+2a)  Total average delay per frame if using Implicit scheme?s  Utilization Performance when working with high speed and long propagation delay? Tt Telecomm. Dept. DCN 13 Faculty of EEE HCMUT
8. Idle-RQ: Communication Usually, Idle-RQ is used in unidirectional communication. If using bidirectional communication? Both sender and receiver have to send and acknowledge data Piggy back methods: outstanding ACKs are placed in the header of information frames save bandwidth since the overhead from a data frame and an ACK frame (addresses, CRC, etc) can be combined into just one frame Telecomm. Dept. DCN 15 Faculty of EEE HCMUT
9. Continuous RQ Telecomm. Dept. DCN 17 Faculty of EEE HCMUT
10. Continuous RQ Selective Repeat: can be implemented in 2 ways: S acknowledges correctly received frames and P determines from the sequence of ACK-frames received that a frame has been lost: implicit retransmission Or S returns NAK for a frame that is missing from the sequence: explicit request Telecomm. Dept. DCN 19 Faculty of EEE HCMUT
11. Continuous RQ  Selective Repeat: implicit retransmission  Corrupted I-frame Telecomm. Dept. DCN 21 Faculty of EEE HCMUT
12. Continuous RQ  Selective Repeat: implicit retransmission  Corrupted ACK-frame Telecomm. Dept. DCN 23 Faculty of EEE HCMUT
13. Continuous RQ  Principle:  On receipt of I-frame N+1, S leaves the retransmission state and resumes returning ACK-frames.  ACK N+4 acknowledges all frames up to including frame N+4  A timer is used with each NAK to ensure that if it is corrupted (and hence frame N+1 is not received), it is retransmitted  Selective Repeat: explicit request:  Correct Operation Telecomm. Dept. DCN 25 Faculty of EEE HCMUT
14. Continuous RQ  Selective Repeat is used primarily when either the frames being transmitted are self-contained entities (the order is not important)  In many application, frames must be delivered in order. Hence, Selective Repeat requires large buffer for storing ordered frames Telecomm. Dept. DCN 27 Faculty of EEE HCMUT
15. Continuous RQ  Go-back-N:  I-frame corrupted Telecomm. Dept. DCN 29 Faculty of EEE HCMUT
16. Continuous RQ  Link Utilization:  In general, the link utilization U for a send window K: • If K  1+2a : U = 1 • If K  1+2a : K.TK.T K U=== ixix T(T+2Ttixp )(1+2a)  Using Selective Repeat: impact by choosing K • If K  1+2a : U = 1-Pf • If K  1+2a : K.T K.T K.(1-P ) U=ix = ix = f Nr .T t N r .(T ix +2T p ) (1+2a) Telecomm. Dept. DCN 31 Faculty of EEE HCMUT
17. Example of sliding window: perfect link  A series of 1000-bit frames is to be transmitted using a continuous RQ protocol. Determine the link efficiency for the following type of data link if the velocity of propagation is 2.108 m/s and the bit error rates of the links are all negligibly low: A 1 km link of 1 Mbps and a send window K = 2 A 10 km link of 200 Mbps and a send window K=7 A 50 000 km satellite link of 2 Mbps, a send window K =127  Solution? Telecomm. Dept. DCN 33 Faculty of EEE HCMUT
18. Timeout Timeout mechanism: A separate timer is started each time I-frame is transmitted by P, and is stopped when an ACK indicating its correct receipt is received If an ACK for an I-frame is not received before it timeout interval expires, the frame is retransmitted The timeout interval must be greater than the worst-case propagation delay between transmitting a frame and receiving the associated ACK S may receive multiple copies due to corrupted ACK-frames • With Go-back-N: this is not the problem. The N(S) in the duplicate frames will not equal to the current V(R) held by S and will be discarded • With Selective Repeat: S retains a ordered list of the last N correctly received I-frames. In this way, S can check if a received frame is a duplicate of an already correctly received frame or a new frame. Telecomm. Dept. DCN 35 Faculty of EEE HCMUT
19. Flow control Control the data transmission rates of characters or frames on a link so that the receiver always has sufficient buffer storage resources to accept them prior to processing Two kinds: X-ON/X-OFF and Sliding Window X-ON/X-OFF: When the receive buffer at S is overflowed, S sends X-OFF back to P, P stops the data transmission When S escape the overload state, it will return X-ON to P to inform its ready state for receiving data. P will continue to transmit data to S For example: in RS232, CTS/RST pins are used for flow control Telecomm. Dept. DCN 37 Faculty of EEE HCMUT
20. Sequence Number  All previous example: assuming that the next frame sequence is simply equal to the last sequence + 1: sequence number go to infinitive  Need to define the maximum limit on the number of I-frames being transferred across a link: limit the size of the link retransmission and receive list, and limit the range of sequence numbers to define frames uniquely  Idle RQ: both send and receive window are 1. Hence 2 identifiers are required to allow S to determine the last I-frame and the new I-frame.  Go-back-N: send window is K: the identifier must be K+1.  Selective Repeat: send and receive windows are K. Hence the identifiers must not be less than 2K Telecomm. Dept. DCN 39 Faculty of EEE HCMUT
21. Sequence Number  In practice, since the identifier of a frame is in binary form, a set number of binary digits must be reserved for its use.  For example, with a send window of 3 and Go-back-N is used, 2 binary digits are required for the send and receive sequence numbers yielding 8 possible identifiers: 0 7. The send and receive sequence variables are then incremented modulo-8 by P and S, respectively Telecomm. Dept. DCN 41 Faculty of EEE HCMUT
22. Connection Management Telecomm. Dept. DCN 43 Faculty of EEE HCMUT
23. Data Link Protocol Application DTE DTE DTE: Data Terminal Equipment DLP: Data Link Protocol DCE: Data Circuit Terminating Equipment DLP : Communication Subsystem DTE DCE DCE DTE PSTN Modem Modem DLP Telecomm. Dept. DCN 45 Faculty of EEE HCMUT
24. Protocol Classification  Character-oriented Protocols:  Asynchronous transmission • XMODEM, YMODEM • Simplex Protocol: Kermit protocol  Synchronous transmission: • Half-duplex protocol: BSC • Full-duplex protocol: APRANET IMP-to-IMP protocol  Bit-oriented Protocols  High-level Data Link Control: single link procedure  Link access procedure version B (LAPB): extension of LAPA, used in X.25 networks  Multilink procedure: extension of LAPB  Link access procedure for modems (LAPM): used in error correction modems (e.g. V32)  Link access procedure for D-channel (LAPD): used in ISDN networks Telecomm. Dept. DCN 47 Faculty of EEE HCMUT
25. BSC Control Characters Telecomm. Dept. DCN 49 Faculty of EEE HCMUT
26. Binary Synchronous Communication  Supervisory frame: the ACK and NAK control characters have 2 functions:  As an acknowledgement: one or other is returned to a previously transmitted data block and hence contains an sequence number.  AS a response to a select control message: an ACK indicates that the selected station is able to receive a data block whereas a NAK indicates that it is not Telecomm. Dept. DCN 51 Faculty of EEE HCMUT
27. Binary Synchronous Communication  Protocol operation:  Poll and Select schematic  Select operation  Master sends data to a specific slave  Put the slave address in the Select control frame  If the Slave is unready: reply by NAK. Otherwise, return ACK Telecomm. Dept. DCN 53 Faculty of EEE HCMUT
28. Example  A BSC protocol is to be used to control the flow of messages between a computer (Master station) and 10 block-mode terminals (secondaries) over a multipoint data link. The link data rate, R, is 10 kbps and the average length of a message, Ni, is 1000 bits. If a poll message and its associated ACK is 30 bits and the total time to process these messages is 1ms, determine the average time each terminal will be polled if the average rate at which messages are generated is:  1 message per minute  6 message per second The bit error rate and signal propagation delay times of the link can be assumed to be negligible  Solution:  Tix=100ms  Time to transmit a poll and its ACK: 30/104=3 ms  Time to poll a single secondary: 3 + 1 = 4 ms  Minimum time to poll all secondaries: Tmin=10x4 = 40 ms -3  Mr = 1 msg/minute = 10 /60 msg/ms: Tavr=40 ms Telecomm. Dept. DCN 55 Faculty of EEE HCMUT
29. HDLC  Operational modes:  Normal Response Mode (NRM) • Used in unbalanced configuration • Slave stations (secondaries) can transmit only when specially instructed by the master (primary) station. • The link may be point-to-point, multipoint (only 1 primary allowed)  Asynchronous Response Mode (ARM) • Used in unbalanced configuration • Allow a secondary to initiate a transmission without receiving permission from the primary • Normally used in point-to-point configuration and duplex links  Asynchronous Balanced Mode (ABM) • Mainly used on duplex point-to-point links • Each station has an equal status and performs both primary and secondary functions Telecomm. Dept. DCN 57 Faculty of EEE HCMUT
30. HDLC  Address Field: Depending on operational mode. In NRM mode, multi-drop line: each station has 1 unique address. If the primary wants to connect with the slave, it will put the slave address in this address field. Certain addresses known as group address can be assigned to more than one secondary. If the address is all bits 1: broadcast address. Not used in ABM mode (point-to-point). Instead, it is used to indicate the direction of commands and their associated responses 8 bit in length, can be expanded with multiple of 7 bits. Last octet will have the first bit equal to 1 Telecomm. Dept. DCN 59 Faculty of EEE HCMUT
31. HDLC  Control field: 1 byte or 2 bytes in length 1 or 2 first bits define the frame type (S,I,U) N(S): send sequence number N(R): receive sequence number P/F: Poll or Select depending on the context: • Command: bit P, request the response from a secondary • Response: bit F, indicating this is the response to a command o Primary to Secondary: If P=1, address is destination 00 o Secondary to Primary: If 10 F=1, address is source 01 11 Telecomm. Dept. DCN 61 Faculty of EEE HCMUT
32. HDLC Extended control bit field definitions Telecomm. Dept. DCN 63 Faculty of EEE HCMUT
33. HDLC Link Management Setup connection Disconnection Telecomm. Dept. DCN 65 Faculty of EEE HCMUT
34. HDLC  Data transfer:  Negative Acknowledgement  Go-back-N  Using REJ/RR b. with NAK frames and Go-back-N strategy Telecomm. Dept. DCN 67 Faculty of EEE HCMUT
35. HDLC  Piggyback with errors:  Example: an exchange in which a frame is lost. Node B sends three data frames (0, 1, and 2), but frame 1 is lost.  When node A receives frame 2, it discards it and sends a REJ frame for frame 1. Note that the protocol being used is Go-Back-N with the special use of an REJ frame as a NAK frame. The NAK frame does two things here: It confirms the receipt of frame 0 and declares that frame 1 and any following frames must be resent.  Node B, after receiving the REJ frame, resends frames 1 and 2. Node A acknowledges the receipt by sending an RR frame (ACK) with acknowledgment number 3. Telecomm. Dept. DCN 69 Faculty of EEE HCMUT