《网路概论》PPT课件.ppt

-1-,網路概論 Class 4 Data Link Control Part II,授課老師 楊人順 2001/10/16-17,-2-,Presentation Outlines,Error Detection Techniques Cyclic redundancy check Error Control Error Control Technique Error Control Mechanism Data Link Protocols Multiplexing What is multiplexing ? Frequency Division Multiplexing Time Division Multiplexing Code Division Multiple Access Digital Subscriber Line,-3-,Cyclic redundancy check,CRC is the most common and powerful error-detecting codes. Algorithm Sender calculates a Frame Check Sequence (FCS) from a pattern. Sender sends a frame with (Message + FCS). Receiver then divides the incoming frame by the same pattern and, if there is no remainder, assume there was not error. Modulo 2 Arithmetic: an exclusion-OR operation to replace the “Add” and “Subtract” Definition T = (k + n)-bit frame to be transmitted, with n k M = k-bit message, the fist k bits of T F = n-bit FCS, the last n bits of T P = pattern of n+1 bits; this is the predetermined divisor.,-4-,CRC Principle,Targets in receiver site No error detected: T/P no remainder Errors detected : T/P with as least one bit error. A true : |P| = |F| + 1 FCS generation,-5-,CRC Principle (cont),Error Detection Example : pp. 204 Another view of CRC : express all value as polynomials in a dummy variable X E.g., M=110011, M(X)=X5 + X4 + X + 1, P=11001, P(X) = X4 + X3 + 1,-6-,Capacity of CRC,An error E(X) will only be undetectable if it is divisible by P(X). The following error types are detectable : All single-bit errors All double-bit errors, as long as P(X) has as least three 1s Any odd number of errors, as long as P(X) contains a factor (X + 1) Any burst error for which the length of the burst is less than the length of the divisor polynomial; that is, less than or equal to the length of the FCS Most larger burst errors Undetectable error probability (r is the length of FCS) A burst error of length r + 1, undetectable error probability is 1/2r1 A longer burst, undetectable error probability is 1/2r,-7-,Current CRC Versions,CRC-12, P(X)=X12 + X11 + X3 + X2 + X + 1 Used for the stream of 6 bits characters, FCS is 12 bits CRC-16, P(X)=X16 + X15 + X2 + 1 Used for the stream of 8 bits characters, FCS is 16 bits Popular for most applications United States CRC-CCITT, P(X)=X16 + X12 + X5 + 1 Used for the stream of 8 bits characters, FCS is 16 bits Popular for most applications Europe CRC-32, P(X)=X32 + X26 + X23 + X22 + X16 + X12 + X11 + X10 + X8 + X7 + X5 + X4 + X2 + X + 1 Some point-to-point synchronous transmission standards.,-8-,Error Control,Error types : lost frame, damaged frame Error control techniques Error detection : typically CRC is used Positive acknowledgment (ACK) Negative acknowledgment (NAK) Error control mechanisms Stop-and-wait ARQ (Automatic Repeat Request) Go-back-N ARQ Selective-reject ARQ Piggybacked acknowledgment,-9-,Stop-and-Wait ARQ,Belong to Idle RQ (Fred pp.170) Based on stop-and-wait flow control Example : pp. 210 figure 7.8 Note 1 : frame sequence 0,1 Note 2 : frame loss time out Link Utilization,-10-,Go-Back-N ARQ,Belong to continues ARQ Based on sliding window flow control Algorithm : pp. 209 - pp.211 Example in next slide If sequence number field = n bits, then window size = 2n 1 (why ?) Link Utilization,-11-,An Example of Go-back-N ARQ,-12-,Selective-Reject ARQ,Belong to continues ARQ Based on sliding window flow control Algorithm : only re-transmitting the frame with Negative acknowledgement (SREJ) Time out loss Example in next slide If sequence number field = n bits, then window size = 2n-1 (why ?) Link Utilization,-13-,An Example of Selective-Reject ARQ,-14-,Data Link Protocols,High-Level Data Link Control (HDLC) HDLC is the basis for many other important data link control protocols ISO 3009, ISO 4335 Link Access Procedure, Balanced (LAPB) LAPB was issued by ITU-T X.25 packet-switching network interface standard, it provides p-t-p link control between a user system and a packet-switching network node Link Access Procedure, D-Channel (LAPD) LAPD was issued by ITU-T as part of its set of recommendations on ISDN LAPD provides data link control over D channel,-15-,Data Link Protocols (cont),Logical Link Control (LLC) LLC is part of IEEE 802 family of standards LLC control the link operation over a LAN Link control functions in the case of LLC are divided between two layers: LLC and MAC (Media Access Control) layers Use CRC-32 Frame Relay (will be explained in Class 13) Asynchronous Transfer Mode (ATM) (will be explained in Class 13),-16-,Multiplexing,What is Multiplexing ? Multiplexing Types Frequency Division Multiplexing (FDM) Time Division Multiplexing (TDM) Synchronous TDM Asynchronous (Statistical) TDM Code Division Multiplexing (CDM),-17-,FDM v.s. TDM,-18-,FDM System,Separated Frequency Band Un-shareable Channel Narrow Band Channel Simultaneously Transmission Cable-TV,-19-,Synchronous TDM,Shared Frequency Band Un-shareable Time-slot Fixed Time-slot allocation Digital Carrier System, ISDN and Telephone Network,-20-,An Example of Synchronous TDM,-21-,Digital Carrier Systems,-22-,DS-1 Transmission Format,-23-,ISDN Primary Access Frame Formats,-24-,Synchronous TDM v.s. Statistical TDM,-25-,s1(t),s2(t),s(t) = s1(t) +s2(t),d1(t)+c1(t)s2(t),c2(t)s1(t)+d2(t),LPF,LPF,Simplified Scheme of CDMA (uplink),-26-,Digital Subscriber Line,Asynchronous Digital Subscriber Line (ADSL) Provides high-speed digital data rate transmission over ordinary telephone wire Uses FDM to exploit the 1-MHz capacity of twisted pair Each carrier (frequency) is use QAM (ASK + PSK) analog signaling technique High Data Rate Digital Subscriber Line (HDSL) To cope the problems of high bandwidth (1.5 MHz) and short distance (1km) in T1 line HDSL uses 2B1Q coding scheme to provide a data rate of up to 2Mbps