高级计算机网络

1、The Data Link Layer,Chapter 3,3.1 Data Link Layer Design Issues,Services Provided to the Network Layer Framing Error Control Flow Control,Functions of the Data Link Layer,Provide service interface to the network layer Dealing with transmission errors Regulating data flow Slow receivers not swamped b

2、y fast senders,Functions of the Data Link Layer (2),Relationship between packets and frames.,Services Provided to Network Layer,(a) Virtual communication. (b) Actual communication.,Services Provided to Network Layer,Unacknowledged connectionless service no logical connection real-time communications

3、 Acknowledged connectionless service no logical connection, acknowledged each frame wireless channels,Services Provided to Network Layer,Acknowledged connection-oriented service the connection is established frames are transmitted the connection is released,Services Provided to Network Layer (2),Pla

4、cement of the data link protocol.,Framing,Character count Flag bytes with byte stuffing Starting and ending flags,with bit stuffing Physical layer coding violations,Framing,A character stream. (a) Without errors. (b) With one error.,Framing (2),(a) A frame delimited by flag bytes. (b) Four examples

5、of byte sequences before and after stuffing.,Framing (3),Bit stuffing (a) The original data. (b) The data as they appear on the line. (c) The data as they are stored in receivers memory after destuffing.,Framing (4),局域网中采用曼彻斯特编码进行传输（IEEE 802.5令牌环协议）。 帧的起始定界符：J K 0 J K 0 0 0（二进制序列） 帧的结束定界符：J K 1 J K

6、1 X X J K 0 J K 0 0 0 J K 1 J K 1,3.2 Error Detection and Correction,Error-Correcting Codes Error-Detecting Codes,Error-Correcting Codes,A frame: m data bits + r check bits ,total length be n=m+r bits Codeword: n bits a Hamming code to correct burst errors Hamming distance:C1=10001001, C2=10110001,

7、d(C1,C2)=3 Hamming distance of the complete code: minimum,Error-Correcting Codes,一种编码的检错和纠错能力取决于它的Hamming距离： (1) 能够检测出d位差错的编码，其编码的Hamming距离至少为d+1; (2) 能够纠正d位差错的编码，其编码的Hamming距离至少为2d+1;,Error-Correcting Codes,(3) 有m个信息位和r个检测位的编码，它能纠正所有单错，则(m + r +1)2r 例：m = 4, r = 3 m = 7, r =4 m =8, r =4,Error-Corre

8、cting Codes,Hamming码的纠错过程： 1 k n 检测位在2i位上(i=0,1) k = 11 = 1 + 2 + 8 “H”: 1001000 0 0 1 1 0 0 1 0 0 0 0 （奇校验） 接收 0 0 1 1 0 0 1 0 0 0 1 检测位 1: （奇数位）0 + 1 + 0 + 1 + 0 + 1 = 1 2：(2,3,6,7,10,11) 0 + 1 + 0 + 1 + 0 + 1 = 1 4: (4,5,6,7) 1 + 0 + 0 + 1 = 0 8: (8,9,10,11) 0 + 0 + 0 + 1 = 1 出错位 k=1011,Error-Cor

9、recting Codes,Use of a Hamming code to correct burst errors.,Error-Detecting Codes,一种多项式编码：循环冗余码（CRC，Cyclic Redundancy Check） m位数据：am-1, am-2, . . . , a1, a0 (ai = 1/0) 对应的多项式，称为信息多项式M(x): M(x)= am-1xm-1+ am-2xm-2+ . . . + a1 x+ a0 产生CRC，找到一个生成多项式G(x)，阶数为r G(x)=xr+ . . . +1 代码 c= am-1, am-2, . . . ,

10、 a1, a0,br-1, br-2, . . . ,b0 (bi=1/0) 对应的代码多项式C(x): C(x)= am-1xm+r-1+ am-2xm+r-2+. . . + a1xr+1+ a0 xr+ br-1xr-1+ br-2xr-2+ . . .+ b0,Error-Detecting Codes,如何找出C(x)： C(x) = xrM(x) + R(x), R(x)的阶 = r-1, 为 xrM(x)/ G(x)的余数多项式。 设接收多项式T(x): 若T(x)/ G(x)的余数多项式为零，则T(x)是码多项式，视为无差错。,Error-Detecting Codes,CRC

11、的一些性质： (1)G(x)=x16+x12+x5+1,则生成的CRC码可以检测出所有的单位错和双位错，所有奇数错。 突发差错：一个长度为k的突发差错，其差错多项式E(x)为 E(x) = xi( xk-1+ . . . +1 ) (2)若G(x)的阶为r，则生成的CRC码可以检测出所有长度等于或小于r位的突发差错。,Error-Detecting Codes,(3) 若G(x)的阶为r，则生成的CRC码不能检测出所有长度等于r+1位的突发差错的概率（2r-1）-1。 （E(x)= G(x) 中间有r-1项，只有一个是G(x) ） (4) 若G(x)的阶为r，则生成的CRC码不能检测出所有长度

12、 大于r+1位的突发差错的概率（2r）-1。,Error-Detecting Codes,Calculation of the polynomial code checksum.,3.3 Elementary Data Link Protocols,An Unrestricted Simplex Protocol A Simplex Stop-and-Wait Protocol A Simplex Protocol for a Noisy Channel,Elementary Data Link Protocols,通信模型的约定： 物理层、数据链路层和网络层是各自独立的进程 主机A用可靠的、

13、面向连接的服务向主机B发送长的数据流（待发的数据无限） 程序中有两个进程 to_physical_layer: 发送一帧 from_physical_layer:接收一帧 校验和的计算与填入由硬件实现,Elementary Data Link Protocols, 过程wait_for_event(&event), 接收一帧后： event=cksun_err , frame_arrival , timeout, network_layer_ready 定义了五种数据结构（用C语句描述） boolean, seq_nr, packet, frame_kind, frame seq_nr 取值0

14、MaxSeq（常量由各协议定义） packet 长度固定为MAX_PKT字节 frame 包含四个字段：kind, seq, ack, info,Elementary Data Link Protocols,其中kind：控制 ，数据 seq：序号 ack：确认 info：分组（数据帧） 过程 to_network_layer, from_network_layer 超时控制：过程 start_timer, stop_timer 确认控制：过程 start_ack_timer, stop_ack_timer 宏inc将序号循环加1,Protocol Definitions,Continued

15、,Some definitions needed in the protocols to follow. These are located in the file protocol.h.,Protocol Definitions(ctd.),Some definitions needed in the protocols to follow. These are located in the file protocol.h.,3.3.1 Unrestricted Simplex Protocol,假设：信道无差错，单向传输，报文处理时间忽略不计，缓冲器空间无限大。 协议1（乌托邦） 两个过程

16、：发送 接收 （无序号，无确认，只有info） 详教材205页,Unrestricted Simplex Protocol,3.3.2 Simplex Stop-and-Wait Protocol,去掉协议1的条件：收方能以无限快的速率处理外来数据 主要问题：防止发方发送数据过快，使收方来不及处理 收方：花费t执行from_physical_layer和 to_network_layer 发方：平均速率小于每t秒一帧。（前一帧取出后，才可发下一帧）。 收方将收到的分组交给网络层后，回送给发方一个短帧（确认帧） 协议2（停等协议）详教材207页 与协议1的区别是在接收和发送过程中增加了一个等待过

17、程,Simplex Stop-and-Wait Protocol,3.3.3 A Simplex Protocol for a Noisy Channel,帧可能出错或丢失，防止帧的重复接收问题： 主机A将分组1交给数据链路层成帧经物理层发送。主机B正确接收帧，将收到的分组1交给网络层，发一个确认帧给主机A。 确认帧在信道上丢失，主机A的数据链路层超时没有收到确认帧，会认为数据帧丢失，重发含分组1的数据帧给主机B。 主机B会认为新的数据帧到达，而又将分组1取出送交网络层，造成重复接收。,3.3.3 A Simplex Protocol for a Noisy Channel,要区分：重发帧和新

18、帧 帧头：序号（0，1） 超时的时间间隔：足够长，使帧到收方后，处理完毕，确认帧发送，传送时间 发送过程保持：序号 next_frame_to_send（变量） 接收过程保持：序号 frame_expected （变量） 协议3（PAR: Positive Acknowledgement with Retransmission /ARQ: Automatic Repeat reQuest） 详教材210页,3.3.3 A Simplex Protocol for a Noisy Channel,发送过程：传完一帧和启动定时器后，处于等待状态 1) 确认帧正确到达，取下一个分组存入缓冲区，序号加

19、1 2) 帧受损且来迟和计数器超时，缓冲区和序号不变，重发该帧 接收过程：当有效帧到达 检查序号，判是否为重复帧；若不是，则接收该帧，并取出分组交网络层，产生一个确认帧，发送确认帧。,A Simplex Protocol for a Noisy Channel,A positive acknowledgement with retransmission protocol.,Continued ,A Simplex Protocol for a Noisy Channel (ctd.),A positive acknowledgement with retransmission protocol

20、.,3.4 Sliding Window Protocols,A One-Bit Sliding Window Protocol A Protocol Using Go Back N A Protocol Using Selective Repeat,Sliding Window Protocols,以上协议数据是单向传输，实际上需要数据双向传输。 捎带技术（piggybacking）: 当一个数据帧到达后，接收过程不是立即发回一个独立的确认帧，而是等到网络层交给它下一分组，将确认帧附加在数据帧上（帧头的 ACK字段）。 充分利用信道的带宽。 这个等待时间显然不能太长，一般应固定为毫秒级的数值

21、。时间到没有分组发送时，则发确认帧。,Sliding Window Protocols,发送窗口：对发送端进行流量控制 发送窗口的大小Ws就代表在还没有收到对方确认的条件下，发送端最多可以发送数据帧的数目。 发送窗口的下界 LN(s) 上界 UN(s) Ws=5：0，1，2，3，4 4 3 此时，LN(s)=0，UN(s)=4,Sliding Window Protocols,接收窗口：控制对数据帧的接收与否 接收窗口的大下Wr表示允许接收未处理帧的数目。 接收窗口的下界LN(r) 上界UN(r) 允许Ws与Wr取值不同 帧头的 seq/ack:n位 序号：0(2n-1),Sliding Wi

22、ndow Protocols (2),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.,A One-Bit Sliding Window Protocol,对协议2（停等协议）的改进，双工通信 协议4（滑动窗口） 可以防止

23、重复帧和超时设置不当的问题： 设定A想发0号帧给B，而B想发0号帧给A。 若A的超时设置过短 A会发一系列的帧：seq=0,ack=1 当A的第一帧到达时，被接收，frame_expected=1 B对以后到达的seq=0而拒绝。由于ack=1，B没有收到对其0号帧的确认，而等待，故不会从网络层取分组。每次拒绝后，B发给A一个seq=0,ack=0帧，最后总有一帧会被正确接收。,A One-Bit Sliding Window Protocol,Continued ,A One-Bit Sliding Window Protocol (ctd.),A One-Bit Sliding Windo

24、w 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.,A Protocol Using Go Back N,去掉前面协议的假设条件：帧到达时间和确认帧传输时间忽略 过长的往返时间对信道的利用率有重大影响 例 卫星信道上信号的传输时延为250ms（单向） 数据速率为50kbps，设帧

25、长1000比特 在t=0开始发第一帧，t=20ms时发毕 t=270ms才到达接收方 t=520ms确认帧才到达发送方 发送方：500/520=96%的时间没有发送（发一帧，等一帧确认）,A Protocol Using Go Back N,采用滑动窗口法：最大Ws=26, 称为流水线技术 信道的容量 b bit/s 帧长 l bits 往返传输时间 R sec 在停-等协议中：信道忙 l/b sec 信道闲R sec 信道的利用率U=(l/b)/(l/b+R)=l/(l+bR) 若lbR 则 U50% 采用流水线技术后，信道的不可靠，帧受损或丢失，如何处理的问题：,A Protocol Us

26、ing Go Back N, 退后n帧法： 接收方直接丢弃所有后继帧，并且不发确认（Wr=1)。 选择性重发： 当发送方发现某个帧出错时（收到NAK帧），才重发此帧（Wr1占大量内存） 协议5（退后n帧协议） 详教材220-221页,A Protocol Using Go Back N,Pipelining and error recovery. Effect on an error when (a) Receivers window size is 1. (b) Receivers window size is large.,Sliding Window Protocol Using Go

27、Back N,Continued ,Sliding Window Protocol Using Go Back N,Continued ,Sliding Window Protocol Using Go Back N,Continued ,Sliding Window Protocol Using Go Back N,Sliding Window Protocol Using Go Back N,发送窗口的最大值： Ws =MAX_SEQ (2n-1) n=3 Ws=7 若Ws=8： 发送方连续发送07号帧，接收方正确接收，发数据帧捎带7号帧确认； 发送方又连续发送新的07号帧，接收方正确接收

28、，发数据帧捎带7号帧确认。 发送方无法清楚后8帧是丢失了，还是被正确接收了？,Sliding Window Protocol Using Go Back N,有多个未被确认的帧，需要多个定时器 每一帧的超时是独立的 用软件模拟这些定时器： 硬件时钟周期性产生中断 不超时的事件组成一个链表 节点中有离超时的时钟节拍数（clock ticks) 例如 100ms,Sliding Window Protocol Using Go Back N (2),Simulation of multiple timers in software.,A Sliding Window Protocol Using

29、Selective Repeat,有时协议5的帧重传量很大，信道的有效利用率不高。 采用Ws= Wr接收方对每一个窗口内的序号都保留一个缓冲区。 一帧到达时，检查序号落在窗口内就被接收和缓存，只要求重发出错帧。 无序接收会带来有序接收没有的问题：,A Sliding Window Protocol Using Selective Repeat,例：Ws= Wr=5 发送方连续发送04号帧，接收方正确接收04号帧 发送方 接收方 a) 发送方连续发送04号帧 b) 接收方正确接收04号帧，发ACK后，窗口变化，而ACK丢失，发送方又重发送04号帧,其中0和1号帧落在接收窗口内，会造成重复接收。,

30、A Sliding Window Protocol Using Selective Repeat,因此W不能太大： W的最大值（MAX_SEQ）/2即2n-1 发送方 接收方 4 3 ACK丢失 4 3 当重发03号帧后，没有落在接收窗口内，不会重复接收,A Sliding Window Protocol Using Selective Repeat,Continued ,Continued ,A Sliding Window Protocol Using Selective Repeat (2),A Sliding Window Protocol Using Selective Repeat

31、 (3),Continued ,A Sliding Window Protocol Using Selective Repeat (4),A Sliding Window Protocol Using Selective Repeat (5),(a) Initial situation with a window size seven. (b) After seven frames sent and received, but not acknowledged. (c) Initial situation with a window size of four. (d) After four f

32、rames sent and received, but not acknowledged.,3.5 Protocol Verification,Finite State Machined Models Petri Net Models,Finite State Machined Models,实际的协议及其实现程序常常是十分复杂的，通常需要找到一些形式化的、数学的技术来描述和验证协议。 协议机（接收方/发送方）：特定状态，由许多变量值组成（含程序计数器）。 为方便起见，可将大量状态组合在一起。,Finite State Machined Models,有限状态机可以将协议形式化为一个四元组（

33、S，M，I，T），其中： S是进程和信道可能的状态集合 M是能在信道上交换的帧的集合 I是进程初始状态的集合 T是在状态之间的迁移(transition)的集合,Finite State Machined Models,迁移：每个状态有0个或多个可能，当某事件发生时就转移到其它状态，这种现象称为迁移。 以协议3（PAR：肯定确认和重发）为例 发送方：要发0#帧，要发1#帧 接收方：等待0#帧，等待1#帧 信道：0#帧从发到收方，1#帧从发到收方，确认帧从收到发方，空闲 每个状态用三个字母x,y,z来标记 0 0#帧在信道上 0 0 1 1#帧在信道上 x= 发方要发帧 y = 收方希望收的帧

34、z= A 确认帧在信道 1 1 - 空闲,Finite State Machined Models,初始状态选为（0 0 0）： 发方正在发送0#帧，收方希望收0#帧，0#帧正在信道上 定义九种迁移： （详教材231页）,Finite State Machined Models,(a) State diagram for protocol 3. (b) Transmissions.,Finite State Machined Models,协议正确性的验证： a） 不存在任何路径，发送方可以改变状态两次（010，101），而接收方状态不变。 b） 不存在死锁：从初始状态可达的状态子集，具有以下

35、两条性质 1）没有能跳出该子集的迁移； 2）子集内没有引起前行的迁移,Petri Net Models,Petri网是Danthine在1980年的博士论文中首先提出的一种描述协议的形式化工具，它具有广泛的用途。 Petri网：四种基本元素 位置，迁移，（输入/输出）弧，令牌（token） 位置用 表示 迁移用 |表示 令牌用 （当前所处状态） 就绪(enabled)：迁移至少有一个输入令牌 触发（fire）：令牌从输入位置转移到输出位置 当前状态：由无序的位置组合表示,Petri Net Models,A Petri net with two places and two transitio

36、ns. Rules 1 AB 2 B A,Petri Net Models (2),A Petri net model for protocol 3.,Petri Net Models (2),Rules: 1 BDAC 2 A空AC 3 ADBE 4 B空BE 5 C空 6 D空 7 E空 8 CFDF 9 EGDG 10 CGDF 11 EFDG 例：当前状态为BEF，若传送无差错下三个状态是BDG； 若丢失1#帧下两个状态是BF（空）,3.6 Example Data Link Protocols,HDLC High-Level Data Link Control The Data Li

37、nk Layer in the Internet,High-Level Data Link Control,IBM SDLC（Synchronous Data Link Control ）protocol ANSI modified ADCCP（Advanced Data Communication Control Procedure） ITU-T（CCITT） modified HDLC（High-level Data Link Control）protocol X25网在数据链路层采用HDLC的一个子集，称为LAPB（Link Access Procedure Balanced）,High

38、-Level Data Link Control,基本概念 1 ） 通信站的类型：主站（P），从站（S），复合站（C） 2 ） 链路结构：三种 点点结构 P S 多点结构 S P S S 平衡结构 C C,High-Level Data Link Control,3）传输响应的类型 正常响应：只有主站轮询 (poll)之后，从站才可发信息 异步响应：主站允许从站不经轮询自动发信息 异步平衡：每个站都可以自动发信息帧和响应帧 4） 通信操作模式 正常响应模式（NRM）：Normal Response Mode 适合于多点结构,High-Level Data Link Control,异步响应模式

39、（ARM）：Asynchronous Response Mode 适合于点点结构 异步平衡模式（ABM）：Asynchronous Balanced Mode 适合于平衡结构 操作模式的建立：主站（复合站）发置模式命令帧 SNRM,SARM,SABM， 扩充 SNRME,SARME,SABME(7b seq),High-Level Data Link Control,Frame format for bit-oriented protocols.,High-Level Data Link Control (2),Control field of (a) An information frame

40、. (b) A supervisory frame. (c) An unnumbered frame.,High-Level Data Link Control (2),Seq:发送帧的序号 Next：希望接收的帧的序号 Type：占二位， 接收就绪（RR） 例 RR，1（希望接收1#帧） 拒绝 （REJ） REJ，1（希望重发1#帧开始各帧）接收未绪（RNR） RNR，1（暂不发1#帧） 选择拒绝（SREJ） SREJ，1（要求重发1#帧） 在X.25和ADCCP中不允许使用SREJ形式 P：轮询位（命令帧） F：最后一帧的表示位（响应帧）,High-Level Data Link Control (2),U帧中的Modifier：占5位，表示各种命令帧和响应帧 目前只定义20种 选介几种: 类型 类型 Modifier SNRM（置正常响应模式） 命令帧 0 0 0 0 1 SABM（置异步平衡模式） 命令帧 1 1 0 0 0 UA（无编号确认） 响应帧 0 0 1 1 0,High-Level Data Link Control (2),UA是对各种“置模式命令”和“拆除”命令的响应 类型 Modifier DISC（拆除） 命