3.1 Data Link Layer Design Issues Services Provided to the Network Layer Framing Error Control Flow Control 2

Size: px

Start display at page:

Download "3.1 Data Link Layer Design Issues Services Provided to the Network Layer Framing Error Control Flow Control 2"

席阡班
5 years ago
Views:

1 Chapter 3 The Data Link Layer 23:03:47 1

2 3.1 Data Link Layer Design Issues Services Provided to the Network Layer Framing Error Control Flow Control 2

3 3.1.1 Services provided to the network layer Unacknowledged connectionless service Acknowledged connectionless service Acknowledged connection-oriented service 3

4 Functions of the Data Link Layer Provide service interface to the network layer Dealing with transmission errors Regulating data flow Slow receivers not swamped by fast senders 4

5 Functions of the Data Link Layer (2) Relationship between packets and frames. 5

6 Services Provided to Network Layer (a) Virtual communication. (b) Actual communication. 6

7 Services Provided to Network Layer (2) Placement of the data link protocol. 7

8 数据链路层的简单模型主机 H 1 向 H 2 发送数据路由器 R 1 路由器 R 主机 H 1 路由器 R 3 2 主机 H 2 电话网局域网广域网局域网 H 1 从层次上来看数据的流动 H 2 应用层运输层网络层链路层物理层 R 1 R 2 R 3 网络层链路层物理层网络层链路层物理层网络层链路层物理层应用层运输层网络层链路层物理层 8

9 数据链路层的简单模型 ( 续 ) 主机 H 1 向 H 2 发送数据路由器 R 1 路由器 R 主机 H 1 路由器 R 3 2 主机 H 2 电话网局域网广域网局域网 H 1 仅从数据链路层观察帧的流动 H 2 应用层运输层网络层链路层物理层 R 1 R 2 R 3 网络层链路层物理层网络层链路层物理层网络层链路层物理层应用层运输层网络层链路层物理层 9

10 3.1.2 Framing Methods 1. Byte count. 2. Flag bytes with byte stuffing. 3. Flag bits with bit stuffing. 4. Physical layer coding violations.

11 Framing (2) Byte count( 字节计数法 ) A character stream. (a) Without errors. (b) With one error. 11

12 Framing (3) Flag bytes with byte stuffing (a) A frame delimited by flag bytes. (b) Four examples of byte sequences before and after stuffing. 12

13 Framing (4) Flag bytes with byte stuffing Starting and ending character, with character stuffing ( 带字符填充的首尾界符法 ) Frame flags: DLE STX(Start Text), DLE ETX(End Text) DLE in data(between flags): DLE-->DLE DLE, so that: DLE ETX--> DLE DLE ETX ESC=0x1B,SOH(Start of Header)=0x01,EOT(End of Transmission)=0x04 Application Example: PPP(Point-to-Point Protocol)

14 Framing (5) Flag bits with bit stuffing. Starting and ending flags,with bit stuffing( 带位填充的首尾界符法 ). -( ) Application Example:HDLC Bit stuffing (a) The original data. (b) The data as they appear on the line. (c) The data as they are stored in receiver s memory after destuffing. 14

15 Framing (6) Physical layer coding violation a 1 bit ->high-low pair, a 0 bit ->low-high pair 15

16 3.1.3 Error Control( 差错控制 ) Error detection Error correction Repeated data frame Lost frame Timer 16

17 3.1.4 Flow Control( 流量控制 ) To solve the problem that a sender wants to transmit frames faster than the receiver can accept them. Feedback-based flow control Rate-based flow control 17

18 3.2 Error Detection and Correction Error-Correcting Codes( 纠错码 ) codeword ( 码字 ) Hamming distance ( , => ,3) parity bit 纠正 d 比特错需距离为 2d+1 比特的编码 Error-Detecting Codes( 检错码 ) polynomial code(cyclic redundancy code,crc code) 检测 d 比特错需距离为 d+1 比特的编码 18

19 3.2.1Error-Correcting Codes (1) 1.Hamming codes. 2.Binary convolutional codes. 二进制卷积码 3.Reed-Solomon codes. 4.Low-Density Parity Check codes.

20 Error-Correcting Codes (2) Example of an (11, 7) Hamming code correcting a single-bit error.

21 Error-Correcting Codes (3) Use of a Hamming code to correct burst errors. 21

22 Error-Correcting Codes (4) The NASA binary convolutional code used in

23 3.2.2 Error-Detecting Codes (1) Linear, systematic block codes 1.Parity. 2.Checksums. 3.Cyclic Redundancy Checks (CRCs).

24 Error-Detecting Codes (2) Interleaving of parity bits to detect a burst error.

25 Error-Detecting Codes (3) Calculation of the polynomial code checksum 多项式编码 ( 循环冗余码,CRC 码 ) 生成多项式 G(x) 计算校验和的算法 : -[see page 197] CRC-12 = x 12 +x 11 +x 3 +x 2 +x 1 +1 CRC-16 = x 16 +x 15 +x 2 +1 CRC-CCITT = x 16 +x 12 +x 5 +1 结论 : 具有 r 检测位的多项式能够检测所有长度 <=r 的突发错误长度大于 r+1 的错误逃脱的概率为 1/2 r. Example calculation of the CRC 25

26 循环冗余检验的原理说明 Q 商除数 P n M 被除数 R 余数 26

27 3.3 Elementary Data Link Protocols A utopian Simplex Protocol( 一种无限制的单工协议 ) A Simplex Stop-and-Wait Protocol( 一种单工的停 - 等协议 ) Error-Free Channel A Simplex Protocol for a Noisy Channel( 有噪声信道的单工协 ) Noisy Channel 进程 (process) 分组 (packet) 和帧 (frame) wait_for_event(&event), 3 events: frame_arrival: Received correct frame cksum_err: Received frame with checksum error timeout: Timeout when waiting acknowledgement 27

28 Elementary Data Link Protocols Implementation of the physical, data link, and network layers.

29 Protocol Definitions Continued Some definitions needed in the protocols to follow. These are located in the file protocol.h. 29

30 Protocol Definitions (ctd.) Some definitions needed in the protocols to follow. These are located in the file protocol.h. 30

31 3.3.1 Utopian Simplex Protocol( 一种无限制的单工协议 ) 31

32 3.3.2 Simplex Stop-and-Wait Protocol ( 一种单工的停 - 等协议 ) stop-andwait, 单向数据传输, 发送方网络层一直有无限的数据要发送, 从不损坏或丢失帧. 抛弃约束条件 : 接收方网络层一直可以接收, 接收方缓冲空间无限大. 32

33 3.3.3 A Simplex Protocol for a Noisy Channel 一个肯定确认的重传协议 (PAR) 计时器 (timer) 序号 (sequence) PAR/ARQ 时间间隔 (timeout) network layer of sender has unlimited data to transmit. Discard restricted condition: channel never damages or loses frame. PAR:Positive Acknowledgement with Retransmission ARQ:Automatic Repeat request Continued 33

34 A Simplex Protocol for a Noisy Channel (ctd.) A positive acknowledgement with retransmission protocol. 34

35 3.4 Sliding Window Protocols ( 滑动窗口协议 ) Bidirectional transmission, piggybacking( 捎带 ), better use of available bandwidth slide window sending window: a set of sequence numbers corresponding to frame it is permitted to send for sender receiving window: corresponding to the set of frames which is permitted to accept for receiver 35

36 Sliding Window Protocols (2) A One-Bit Sliding Window Protocol A Protocol Using Go Back N( 后退 n 帧 ) A Protocol Using Selective Repeat( 选择性重传 ) 36

37 Sliding Window Protocols (3) A sliding window of size 1, with a 3-bit sequence number. (a) Initially. (b) After the first frame has been sent. (c) After the first frame has been received. (d) After the first acknowledgement has been received. 37

38 3.4.1 A One-Bit Sliding Window Protocol Continued 38

39 A One-Bit Sliding Window Protocol (ctd.) 39

40 A One-Bit Sliding Window Protocol (2) Two scenarios for protocol 4. (a) Normal case. (b) Abnormal case. The notation is (seq, ack, packet number). An asterisk(*) indicates where a network layer accepts a packet. 40

41 3.4.2 A Protocol Using Go Back N The long round-trip time can have important implications for the efficiency of the bandwidth utilization. Consider a 50kbps satellite channel with a 500msec round-trip propagation delay. Assume using protocol 4 to send 1000bit frames via satellite. At t= 0 msec: sending the first frame. At t= 20 msec: the frame being completely sent. At t=270 msec: the frame arrived at the receiver. At t=520 msec: the acknowledgement arrived back at the sender The sender was blocked during 500/520 or 96 percent of the time.

42 A Protocol Using Go Back N

43 Line utilization ( 线路利用率 ) This technique is known as pipelining. If the channel capacity is b bits/sec, the frame size l bits, and the round-trip propagation time R sec, the time required to transmit a single frame is l/b sec. After the last bit of a data frame has been sent, there is a delay of R/2 before that bit arrives at the receiver and another delay of at least R/2 for the acknowledgement to come back, for a total delay of R. In stop-and-wait the line is busy for l/band idle for R, giving Line utilization = l/(l+br) If l < br, the efficiency will be less than 50 percent.

44 A Protocol Using Go Back N Pipelining and error recovery. Effect on an error when (a) Receiver s window size is 1. (b) Receiver s window size is large. 44

45 Sliding Window Protocol Using Go Back N (2) 接收窗口大小为 W=1 抛弃所有后续的帧最多允许有 MAX_SEQ 帧未被确认 Stop-and-wait is not fitful for channel which has long round-trip delay, e.g. Satellite channel,270 ms Bidirectional transmission, noisy channel, Discard restricted condition: network layer of sender has unlimited data to transmit size of receiving window = 1, receiver discards all subsequent frames after a damaged or lost data frame. 45

46 思考题 Sliding Window Protocol Using Go Back N (3) MAX_SEQ+1 distinct sequence numbers(0,1,2,... MAX_SEQ),no more than MAX_SEQ unacknowledged frames,the sender window<=max_seq. Why? Consider the following scenario with MAX_SEQ=7(a sender window of size eight): The sender sends frames 0 through 7. A piggybacked acknowledgement for frame 7 eventually comes back to the sender. The sender sends another eight frames,again with sequence numbers 0 through 7. All eight frames belonging to the second batch get lost All eight frames belonging to the second batch arrive successfully. Another piggybacked acknowledgement for frame 7 come in, ambiguity will arise to sender: All eight frames belonging to the second batch get lost,ack=7 All eight frames belonging to the second batch arrive successfully,ack=7 46

47 Sliding Window Protocol Using Go Back N (4) A Protocol Using Go Back n( when the size of sender window=7,no ambiguity: The sender sends frames 0 through 6 A piggybacked acknowledgement for frame 6 eventually comes back to the sender The sender sends another 7 frames:7,0,1,2,3,4,5, Frame 7,0,1,2,3,4,5 belonging to the second batch get lost Frame 7,0,1,2,3,4,5 belonging to the second batch arrive Another piggybacked ack nowledgement comes in,no ambiguity Frame 7,0,1,2,3,4,5 belonging to the second batch get lost,ack=6 Frame 7,0,1,2,3,4,5 belonging to the second batch arrive, ack=5 the problem : Since a sender may have to retransmit all the unacknowledged frames at a future time,it must hang on to all transmitted frames until it knows for sure that they have been accepted by the receiver. No acknowledged frames without data. 47

48 Sliding Window Protocol Using Go Back N (5) Continued 48

49 Sliding Window Protocol Using Go Back N (6) Continued 49

50 Sliding Window Protocol Using Go Back N (7) Continued 50

51 Sliding Window Protocol Using Go Back N (8) 51

52 Sliding Window Protocol Using Go Back N (9) Simulation of multiple timers in software. 52

53 3.4.3 A Sliding Window Protocol Using Selective Repeat 允许接收后续的帧 ( 接收窗口 >1) 窗口大小为 W<=(MAX_SEQ+1)/2 所需缓冲器的数量 =W 所需计时器的数量 =W 否定性确认帧 -NAK 思考题 53

54 A Sliding Window Protocol Using Selective Repeat (2) Continued 54

55 A Sliding Window Protocol Using Selective Repeat (3) Continued 55

56 A Sliding Window Protocol Using Selective Repeat (4) Continued 56

57 A Sliding Window Protocol Using Selective Repeat (5) 57

58 A Sliding Window Protocol Using Selective Repeat (6) (a) Initial situation with a window size 7. (b) After 7 frames sent and received, but not acknowledged. (c) Initial situation with a window size of 4. (d) After 4 frames sent and received, but not acknowledged. 58

59 3.5 Example Data Link Protocols Content in 4 th edition: HDLC High-Level Data Link Control The Data Link Layer in the Internet (PPP) Content in 5 th edition: Packet over SONET (PPP) ADSL (Asymmetric Digital Subscriber Loop) 59

60 Content in 4 th edition: High-Level Data Link Control SDLC(IBM SNA) ADCCP(ANSI) HDLC(ISO) LAP(CCITT) LAPB(X.25) bit-oriented protocol frame format-[see fig 3-24] flag sequence ( ) the minimum frame:three fields 32 bits three kinds of frames:information Supervisory Unnumbered-[see fig 3-25] 60

61 Content in 4 th edition: High-Level Data Link Control (2) Seq --- sender seq(like former protocol 5 ) Next --- expected frame seq, different from former ack,it is (ack+1) mod 8 61

62 Content in 4 th edition: High-Level Data Link Control (3) Information frame( 信息帧 ): Supervisory frame( 监控帧 ): RR(Receive Ready), 接收准备就绪 RNR(Receive Not Ready): to implement flow control REJ(Reject): like NAK frame, 从 Next 起的所有帧都被否认, 但确认序号为 Next 及其以前的各帧 SREJ(Selective Reject), 选择性拒绝 Unnumbered frame ( 无序号帧 ): request to establish connection: SNRM(Set Normal Response Mode), SABM(set asynchronous balanced mode) request to disconnect: DISC(Disconnect) response frame: UA(unnumbered acknowledgement) report severe error: FRMR(FRaMe Reject) 62

63 Content in 4 th edition: The Data Link Layer in the Internet A home personal computer acting as an internet host. 63

64 Content in 4 th edition: 用户拨号入网的示意图用户家庭 PC 机使用 TCP/IP 的客户进程调制解调器拨号电话线使用 TCP/IP 的 PPP 连接因特网服务提供者 (ISP) 调制解调器路由器路由选择进程至因特网 64

65 Content in 4 th edition: PPP 协议 1992 年制订了 PPP 协议经过 1993 年和 1994 年的修订, 现在的 PPP 协议已成为因特网的正式标准 [RFC 1661] PPP 协议有三个组成部分一个将 IP 数据报封装到串行链路的方法链路控制协议 LCP (Link Control Protocol) 网络控制协议 NCP (Network Control Protocol) 65

66 Content in 4 th edition: PPP 协议的帧格式 PPP 的帧格式和 HDLC 的相似标志字段 F 仍为 0x7E ( 符号 0x 表示后面的字符是用十六进制表示十六进制的 7E 的二进制表示是 ) 地址字段 A 只置为 0xFF 地址字段实际上并不起作用控制字段 C 通常置为 0x03 PPP 是面向字节的, 所有的 PPP 帧的长度都是整数字节 66

Content in 4 th edition: PPP 协议的帧格式先发送首部 IP 数据报尾部 7E F FF A 03 C 协议信息部分 FCS 7E F 字节 1 1 1 2 不超过 1500 字节 2 1

67 Content in 4 th edition: PPP 协议的帧格式先发送首部 IP 数据报尾部 7E F FF A 03 C 协议信息部分 FCS 7E F 字节不超过 1500 字节 2 1 PPP 帧 PPP 有一个 2 个字节的协议字段当协议字段为 0x0021 时,PPP 帧的信息字段就是 IP 数据报若为 0xC021, 则信息字段是 PPP 链路控制数据若为 0x8021, 则表示这是网络控制数据 67

68 Content in 4 th edition: PPP Point to Point Protocol (2) ( 点到点协议 ) SLIP PPP Support:error detection multiple protocols(ip,ipx,apple Talk,XNS,...),allows IP address to be negotiated permits authentication LCP(Link Control Protocol): byte oriented and bit-oriented encodings NCP(Network Control Protocol). Frame format(as HDLC):-[see fig 3-27] A simplified phase diagram for bringing a line up and down- [see fig 3-28] 68

69 Content in 4 th edition: PPP Point to Point Protocol (3) Flag: The PPP full frame format for unnumbered mode operation. Address: always Control: default (unnumbered mode) Protocol: default size is 2 bytes, tell what kind of packet is in the Playload field protocols starting with a 0 bit are network lay protocols such as IP, IPX,OSL CLNP, XNS; Those starting with a 1 bit are used to negotiate other protocols: LCP or other NCP Payload: variable length, up to some negotiated maximum; default length of 1500 bytes is used for LCP line setup Checksum: 2 or 4 bytes 69

70 Content in 4 th edition: PPP Point to Point Protocol (4) A simplified phase diagram for bring a line up and down. 70

71 Content in 4 th edition: PPP Point to Point Protocol (5) The LCP frame types. Note: Initiator(I) Responder(R) 71

72 Content in 5 th edition: Packet over SONET (1) Packet over SONET. (a) A protocol stack. (b) Frame relationships

73 Content in 5 th edition: Packet over SONET (2) PPP Features 1.Separate packets, error detection 2.Link Control Protocol 3.Network Control Protocol

74 Content in 5 th edition: Packet over SONET (3) The PPP full frame format for unnumbered mode operation

75 Content in 5 th edition: Packet over SONET (4) State diagram for bringing a PPP link up and down

76 Content in 5 th edition: ADSL (Asymmetric Digital Subscriber Loop) (1) ADSL protocol stacks.

77 Content in 5 th edition: ADSL (Asymmetric Digital Subscriber Loop) (1) AAL5 frame carrying PPP data

78 3.6 Summary The task of the data link layer The size of window the sliding window stop-wait protocol sliding window protocol Example of the data link layer: bit-oriented:sdlc HDLC ADCCP or LAPB byte-oriented and bit-oriented:slip and PPP(Internet) 78

79 Exercises In 4 th Edition: 2,3,5,14-18, 27,29,32,37 In 5 th Edition: 3,7,13-16,18,20, 27,29,31,33 79

穨control.PDF

穨control.PDF TCP congestion control yhmiu Outline Congestion control algorithms Purpose of RFC2581 Purpose of RFC2582 TCP SS-DR 1998 TCP Extensions RFC1072 1988 SACK RFC2018 1996 FACK 1996 Rate-Halving 1997 OldTahoe