计算机网络-自顶向下设计的读书笔记(13)

1、1、 数据链路层服务1、 数据链路层的一些术语/概述(1) 、结点：主机和路由器1) 链路： 连接相邻结点的通信信道a. 物理链路a) 有线链路（wired link）b) 无线链路（wireless link）c) 局域网（LANs）b. 数据链路(2) 、帧（frame）：链路层（第二层）数据分组，封装网络层数据报(3) 数据链路层负责实现物理链路之间直接相连的相邻结点传送数据报2、 链路层服务1 组帧1) 封装数据报构成数据帧，加首部和尾部2) 帧同步：如何从物理层传来的比特流识别帧2 链路接入1) 如果是共享介质，需要解决信道接入（channel access）2) 帧首部中的“MAC

2、”地址，用于标识帧源和目的a. 不同于IP地址3)3 相邻结点间可靠交付/传输1) 在低误码率的有线链路上很少采用（如光纤，某些双绞线）2) 无线链路：wife4 流量控制1) 协调相邻的发送结点和接收5 差错检测1) 信号衰减和噪音会引起差错2) 接收端检测到差错a. 通知发送端重传或者直接丢弃帧6 差错纠正1) 接收端直接纠正比特拆错7 全双工和半双工通信控制1) 全双工：链路两端结点同时双向传输2) 半双工：链路两端结点交替双向传输？3、 链路层的具体实现1 每个主机或者嗯路由器接口-网卡2 链路层在“适配器”（即网络接口卡-NIC）中实现或者在一共芯片上实现1) 以太网卡，802.11

3、网卡；以太网芯片组2) 实现链路层和物理层3 链接主机的系统总线4 由硬件、软件于固件组成562、 差错编码1、 差错检测的基本原理(1)2、 差错编码的检错能力1 差错编码可分为检错码和纠错码2 对于检错码，如果编码集的汉明距离ds = r + 1，则该差错编码可以检测r位的差错1) 汉明距离：两个等长字符串之间的汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数2) 编码集的汉明距离：任意两个数的汉明距离的最小值3) 比如由c1与c2，c1与c2之间汉明编码一定大于r+1，如果c1错了r位，那c1也变成不了c2，因此错误的那一

4、个一定会被检测出来的3 对于纠错码，如果编码集的汉明距离ds = 2*r + 1,则该差错编码可以纠正r位的差错1) 将无效的码字纠错成离它最近的码字2)4 奇偶校验码1)5 CheckSum发送端1) 将“数据”（校验内容）划分位为16位的二进制“整数”序列2) 求和（sum）：补码求和（最高位进位的“1”，返回最低位继续加）3) 校验和（Checksum）：sum的反码4) 放入分组（UDP、TCP、IP）的校验和字段接收端1) 与发送端相同算法计算2) 计算得到的“checksum”a) 全为0（或全1）：无措b) 否则有错6 循环冗余校验码（CRC）1) 检错能力更强大的差错编码2)

5、将数据比特，D,视为一个二进制数3) 选择一个r+1位的比特模式（生成比特模式），G4) 目标：选择r位的CRC比特，R，满足a. <D,R>刚好可以被G整出（模2）b. 接收端检错：利用G除<D,R>，余式全0，无措；否则，有错！c. 可以检错所有突发长度小于r+1的差错5) 广泛应用于实际网络（以太网，802.11wife，ATM0）6)7)8)3、 MAC：（multiple access control protocol）多路访问控制协议1、 两类电路：1 点对点电路1) 拨号接入的PPP2) 以太网交换机于主机间的点对点链路2 广播电路(共享介质)1) 早期的

6、总线以太网2) 802.11无线局域网3) HFC的上行链路4)2、 解决问题-1 单一共享广播信道2 两个或者两个以上结点同时传输：干扰1) 冲突a. 结点同时接收两个或多个信号-接收失败3 MAC协议1) 采用分布式算法决定结点如何共享信道，即决策结点合可以传输数据2) 必须基于信道本身，通信信道共享协调信息！a. 无带外信道用于协调4 理想的MAC协议1) 给定：速率位R bps的广播信道2) 期望：a. 当只有一个结点希望传输数据时，它可以以速度R发送b. 当有M个结点期望发送数据时，每个结点平均以速度R/M速度发送c. 完全分散控制a) 无需特定结点协调b) 无需时钟、时隙同步d.

7、简单5 MAC协议分类1) 三大类a. 信道划分MAC协议a) 多路复用技术b) TDMA，FDMA，CDMA，WDMA等c) FDMAi. 信道频谱划分未若干频带ii. 每个站点分配一个固定频带iii. 无传输频带空闲iv.d) TDMAi. “周期性”接入信道ii. 每个站点在每个周期、占用固定长度的时隙（长度=每组传输时间）iii. 未使用时隙空闲iv.e) 如果网络负载重，利用率大f) 如果网络负载轻，利用率小b. 随机访问（random access）MAC协议a) 信道不划分，允许冲突b) 当有结点要发送分组时:i. 利用信道的全部速率R发送分组ii. 没有实现的结点间协调iii.

8、c) 采用冲突“恢复”机制i. 如何检测冲突ii. 如何从冲突中恢复（eg 通过延迟重传）d) 典型的随机访问MAC协议i. 时隙（sloted）ALOHA协议i) 假定a. 所有帧大小相同b. 时间被划分为等长的时隙（每个时隙可以传输一个帧）c. 结点只能在时隙开始时刻发送帧d. 结点间时钟同步e. 如果有2个或2个以上结点在同一时隙发送帧，结点检测到冲突ii) 运行a. 当结点有新的帧时，在下一个时隙发送b. 如果无冲突：该结点可以在下一个时隙继续发送新的帧c. 如果冲突：该结点在下一个时隙以概率p重传该帧，知道成功iii) 优点a. 单个结点活动时，可以连续以信道全部速率传输速率b. 高

9、度分散化：只需同步时隙c. 简单缺点a. 冲突、浪费时隙b. 空闲时隙c. 结点也许远小于分组传输时间检测到冲突d. 时钟同步效率ii. ALOHAi) 非时隙（纯）Aloha：更加简单，无需同步ii) 当有新的数据帧生成时a. 立即发送iii) 冲突可能性增大效率iii. CSMA CSMA/CD CSMA/CAi) CSMA（载波监听多路访问协议：carrier sense multiple access）a. 发送帧之前，监听信道（载波）-判断是否有其他数据信道空闲：发送完整帧信道忙：推迟发送1- -坚持CSMA非坚持CSMAP- -坚持CSMAb. 冲突仍然有可能发生：信号传播延迟c. 继续发送冲突帧：浪费信道资源ii) CSMA/CD CSMA with collision detectiona. 短时间可以检测冲突b. 冲突后传输终止，减少信道浪费c. 冲突检测a) 有限局域网易于实现：测量信号强度，比较发射信号于接收信号b) 无线局域网很难实现：接收信号强度淹没在本 地发射信号强度下c) 边发边听，不发不听c. 轮转（“taking turns”）MAC协议a) 结点轮流使用信道b) 轮询（polling）：i. 主结点轮流“邀请”从属结点发送数据ii. 典型运用：i) 哑从属设备ii) . 轮询开销iii) 等待延迟iv) 单点故障问题（主结点有问题）