哈工大计算机网络第五章——数据链路层与局域网复习_本章节的学习,学生应掌握:链路层的作用,以太网帧的结构,交换机工作原理,虚拟

目录

1. 数据链路层服务

2. 差错编码

3. MAC——多路访问控制协议

4. ARP协议——地址解析协议

5. 以太网

6. PPP协议

7. 802.11无线局域网

---

1. 数据链路层服务

节点（书上P285谓之节点，PPT谓之结点，吾亦不明矣，故任选一而用之）：所有运行链路层协议的设备，包括主机、路由器、交换机和Wifi接入点

链路：沿着通信路径连接相邻节点的通信信道，包括有线链路，无线链路和局域网。

在通过特定链路时，传输节点把网络层数据报封装在链路层帧中，并将该帧传送到链路中。数据链路层负责通过一条链路从一个节点向另一个物理链路直接相连的相邻结点传送数据报。

链路层提供的服务

❖组帧(framing)：封装数据报构成数据帧，加首部和尾部。帧同步：分析首部和尾部 

❖链路接入(link access)：Mac协议规定了帧在链路上传输的规则。如果是共享介质，需要解决信道接入(channel access) 。帧首部中的“MAC”地址，用于标识帧的源和目的，这个与IP地址不同。 

❖相邻结点间可靠交付：在低误码率的有线链路上很少采用 (如光纤，某些双绞线等) 。但在无线链路这种误码率高的链路上，需要可靠交付。链路层提供可靠交付时，能保证无差错地经链路层移动每个网络层数据报。与传输层的可靠服务类似，链路层的可靠服务也是通过确认和重传做到的。

❖流量控制(flow control) ：协调(pacing)相邻的发送结点和接收

❖差错检测(error detection)： 信号衰减和噪声会引起差错。接收端检测到差错后，通知发送端重传或者直接丢弃帧

❖差错纠正(error correction) ：接收端直接纠正比特差错

❖全双工和半双工通信控制：1. 全双工：链路两端结点同时双向传输 2. 半双工：链路两端结点交替双向传输

链路层的实现

链路层的主体部分在网络适配器（网络接口卡）中实现。除此之外还包括每个主机或路由器接口和链接主机的系统总线。链路层由硬件、软件与固件组成。

网卡间通信

❖ 发送端：

▪ 将数据报封装成帧

▪ 增加差错检测比特，实现可靠数据传输和流量控制等.

❖ 接收端：

▪ 检测差错，实现可靠数据传输和流量控制等

▪ 提取数据报，交付上层协议实体

2. 差错编码

 检错码

汉明距离是两个字符串对应位置的不同字符的个数。换句话说，它就是将一个字符串变换成另外一个字符串所需要替换的字符个数。在一系列字符串中，汉明距离表示其中每个字符串与其他字符串汉明距离的最小值。（MOOC中好像有详细讲）

纠错码

奇偶校验

假设发送的信息D有d比特。在偶校验方案中，发送方只需要包含一个附加的比特，选择它的值，使得这d+1个比特中1的个数是偶数。奇校验方案中，是奇数个1。接受方只需要计算1的个数即可。在偶校验方案中，出现奇数个1，说明出现了奇数个差错比特。

为解决偶数个无法检测的问题，使用二维校验方案。

 接收方不仅可以检测到单个比特差错，还可以利用列和行的索引进行识别和纠正。

检验和方法

发送端:

❖ 将“数据”(校验内容)划分为16位的二进制“整数”序列

❖ 求和(sum)：补码求和 (最高位进位的“1”，返回最低位继续加）

❖ 校验和(Checksum)：sum的反码

❖ 放入分组(UDP、TCP、IP)的校验和字段

接收端:

❖ 与发送端相同算法计算

❖ 计算得到的"checksum"，计算为16位全0（或sum为16位全1），则无错。否则，有错

CRC——循环冗余校验码

考虑d比特的数据D。发送方与接收方首先协商一个r+1比特模式，称为生成生成多项式，用G表示。G的最高有效位（最左边）为1。CRC的关键思想是，对于D，发送方选择r个附加比特R，并附加在D上，得到的d+r的比特模式用模2算法恰好被G整除。接收端用G去除除收到的d+人格比特，如果余数为0，代表正确，否则出错。可以检测所有突发长度小于r+1位差错。

3. MAC——多路访问控制协议

两类“链路”

❖ 点对点链路：链路一段的单个发送方和链路另一端的单个接收方

▪ 拨号接入的PPP

▪ 以太网交换机与主机间的点对点链路

❖ 广播链路 (共享介质)：多个发送和接收节点使用相同的单一的共享的广播信道

▪ 早期的总线以太网

▪ HFC的上行链路

▪ 802.11无线局域网

在两个或者两个以上结点同时传输，会出现干扰(interference)

冲突(collision) ：结点同时接收到两个或者多个信号→接收失败！

多路访问控制协议(multiple access control protocol)

❖ 采用分布式算法决定结点如何共享信道，即决策结点何时可以传输数据

❖ 必须基于信道本身，通信信道共享协调信息！无带外信道用于协调。

理想MAC协议

给定：速率为R bps的广播信道

期望：

1. 当只有一个结点希望传输数据时，它可以以速率 R发送.

2. 当有M个结点期望发送数据时，每个节点平均发送数据 的平均速率是R/M

3. 完全分散控制: 无需特定结点协调，无需时钟、时隙同步

4. 简单

MAC分类

❖信道划分(channel partitioning)MAC协议 ：采用多路复用技术，如TDMA、FDMA、CDMA、WDMA等

❖随机访问(random access)MAC协议：信道不划分，允许冲突，采用冲突“恢复”机制

❖轮转(“taking turns”)MAC协议：结点轮流使用信道

信道划分MAC协议

TDMA：“周期性”接入信道，每个站点在每个周期，占用固定长度的时隙(e.g.长度= 分组传输时间) 。未用时隙空闲(idle)。

 FDMA：信道频谱划分为若干频带(frequency bands)，每个站点分配一个固定的频带。无传输频带空闲

随机访问MAC协议

当结点要发送分组时，利用信道全部数据速率R发送分组，但没有事先的结点间协调。当两个或多个结点同时传输，会产生“冲突” 。

随机访问MAC协议需要定义: 如何检测冲突和如何从冲突中恢复 (e.g., 通过延迟重传)

❖典型的随机访问MAC协议： ▪ 时隙(sloted)ALOHA ▪ ALOHA ▪ CSMA、CSMA/CD、CSMA/CA

时隙ALOHA协议

假定：所有帧大小相同，时间被划分为等长的时隙 (每个时隙可以传输1个帧) 。结点只能在时隙开始时刻发送帧。结点间满足时钟同步。如果2个或2个以上结点在同一时隙发送帧，结点即检测到冲突。

运行：当结点有新的帧时，在下一个时隙(slot)发送。如果无冲突，该结点可以在下一个时隙继续发送新的帧。如果冲突，该结点在下一个时隙以概率p重传该帧，直至成功

优点: 1. 单个结点活动时，可以连续以信道全部速率传输数据 2. 高度分散化：只需同步时隙 3. 简单

缺点: 1. 冲突，浪费时隙 2. 有较多空闲时隙 3. 结点也许能以远小于分组传输时间检测到冲突 4. 时钟同步

效率(efficiency): 长期运行时，成功发送帧的时隙所占比例(很多结点，有很多帧待发送)

时隙ALOHA 最好情况: 信道被成功利用的时间占37%。

ALOHA协议

非时隙(纯)Aloha，实现更加简单，无需同步。当有新的帧生成时，立即发送。但是冲突可能性增大。在t0时刻发送帧，会与在[t0 -1, t0+1]期间其他结点发送的帧冲突

ALOHA 最好情况: 信道被成功利用的时间占18%。

CSMA协议——载波监听多路访问协议

在发送帧之前，监听信道 (载波)。如果信道空闲，发送完整帧。如果信道忙，推迟发送。因为信号传播延迟，冲突可能仍然发生。此时继续发送冲突帧，会浪费信道资源。发生冲突时，节点会坚持发完所有比特，但是实际发生冲突后比特不会再被接收，因此造成浪费。

1-坚持CSMA：一直监听信道，一旦发现空闲，立即发送

非坚持CSMA：随机等待一段时间，再来监听信道，判断是否可发送

P-坚持CSMA ：以概率P使用1-坚持CSMA，概率（1-P）坚持非CSMA。

CSMA/CD协议

短时间内可以检测到冲突，冲突后传输中止，减少信道浪费

冲突检测: 1. 有线局域网易于实现：测量信号强度，比较发射信号与接收信号 2. 无线局域网很难实现：接收信号强度淹没在本地发射信号强度下

由于边发边听，我们要在发送之前收到检测冲突的消息，则发送时间需要比检测消息来回的时间长

 CSMA/CD效率

轮转访问MAC协议

轮询(polling)：主结点轮流“邀请” 从属结点发送数据

典型应用： “哑(dumb)” 从属设备

问题： 1. 轮询开销 2. 等待延迟 3. 单点故障

令牌传递(token passing)：控制令牌依次从一个结点传递到下一个结点。令牌是一个特殊帧

问题转化为： 1. 令牌开销 2. 等待延迟 3. 单点故障

MAC总结

❖信道划分MAC协议：时间、频带、码片划分，如TDMA、FDMA、CDMA

❖随机访问MAC协议：ALOHA, S-ALOHA, CSMA, CSMA/CD，其中CSMA/CD应用于以太网，CSMA/CA应用802.11无线局域网

❖轮转访问MAC协议：主结点轮询；令牌传递。应用于蓝牙、FDDI、令牌环网

4. ARP协议——地址解析协议

MAC地址

32位IP地址: 接口的网络层地址，用于标识网络层(第3层)分组，支持分组转发

MAC地址(或称LAN地址,物理地址,以太网地址) : 用于局域网内标识一个帧从哪个接口发出，到达 哪个物理相连的其他接口，表示为48位MAC地址(用于大部分LANs)，固化在网卡的 ROM中，有时也可以软件设置 。举例一个用16进制表示的MAC地址为1A-2F-BB-76-09-AD。

局域网中的每个网卡都有一个唯一的MAC地址。MAC地址由IEEE统一管理与分配，网卡生产商购买MAC地址空间(前24比特)。我们可以类比MAC地址为身份证号，IP地址为邮政地址。MAC地址是“平面”地址。是可“携带”的，可以从一个LAN移到另一个LAN。IP地址是层次地址，是不可“携带”的，IP地址依赖于结点连接到哪个子网。

ARP——地址解析协议

问题: （在同一个LAN内）如何在已知目的接口的IP地址前提下确定其MAC地址？

ARP表: LAN中的每个IP结点(主机、路由器)维护一个表，存储某些LAN结点的IP/MAC地址映射关系: < IP地址; MAC地址; TTL> 。其中TTL (Time To Live)代表经过这个时间以后该映射关系会被遗弃(典型值为20min)

在一个局域网内

A想要给同一局域网内的B发送数据报，但B的MAC地址不在 A的 ARP 表中。A广播ARP查询分组，其中包含B的IP地址，网络适配器用MAC广播地址来发送分组，即查询分组中目的MAC地址 为 FF-FF-FF-FF-FF-FF 。适配器在链路层帧中封装这个ARP分组，传进子网中。包含该ARP查询的帧能被子网上全部适配器接收到（LAN中所有结点都会接收 ARP查询）。B接收ARP查询分组，IP 地址匹配成功，向A应答 B的MAC 地址。利用单播帧向A发送应答（响应ARP分组）。A在其ARP表中，缓存B的 IP-MAC地址对，直至超时。超时后，再次刷新

ARP是“即插即用”协议：结点自主创建ARP表， 无需干预

从一个LAN路由到另一个LAN

A通过路由器R向B发送数据报。我们关注的问题是寻址，IP地址(数据报中)和MAC地址(帧中)。

假设A知道B的IP地址：使用DNS查询，根据主机名查询IP地址，然后封装到IP数据报中。

假设A知道第一跳路由器R (左)接口IP地址 ：默认网关，就是子网外联的路由器的向内IP地址

假设A知道第一跳路由器R (左)接口MAC地址：ARP协议，上面讲过的一个局域网内的查询，根据上一个IP地址，查询路由器的MAC地址。

A构造IP数据报，其中源IP地址是A的IP地址，目的IP地址是B的IP地址。A构造链路层帧，其中源MAC地址是A的MAC地址，目的MAC地址是 R(左)接口的MAC地址，封装A到B的IP数据报。帧从A发送至R。R接收帧，提取IP数据报，传递给上层IP协议

R转发IP数据报（源和目的IP地址不变）。R创建链路层帧，其中源MAC地址是R(右)接口的MAC地址，目的MAC地址是B的MAC地址，封装A到B的IP数据报。

5. 以太网

❖总线(bus): 上世纪90年代中期前流行，所有结点在同一冲突域(collision domain) (可能彼此冲突)

❖星型(star): 目前主流网络拓扑，采用中心交换机(switch) ，每个结点一个单独冲突域(结点间彼此不冲突)

无连接：发送帧的网卡与接收帧的网卡间没有“握手”过程

不可靠：接收网卡不向发送网卡进行确认。差错帧直接丢弃，丢弃帧中的数据恢复依靠高层协议 (e.g., TCP)，否则，发生数据丢失

CSMA/CD算法

以太网的MAC协议: 采用二进制指数退避算法的CSMA/CD

1. NIC从网络层接收数据报，创建数据帧。

2. 监听信道： 如果NIC监听到信道空闲，则开始发送帧； 如果NIC监听到信道忙，则一直等待到信道空闲，然后发送帧。

3. NIC发送完整个帧，而没有检测到其他结点的数据发送，则NIC确认帧发送成功！

4. 如果NIC检测到其他结点传输数据，则中止发送，并发送堵塞信号(jam signal)

5. 中止发送后，NIC进入二进制指数退避。第m次连续冲突后，取n = Min(m, 10) 。NIC 从{0,1,2, …, 2^n -1}中随机选择一个数K，NIC等待K·512比特的传输延迟时间，再返回第2步。连续冲突次数越多，平均等待时间越长。

以太网帧结构

发送端网卡将IP数据报(或其他网络层协议分组) 封装到以太网帧中：

❖ 前导码(Preamble)(8B)：7个字节的10101010，第8字节为10101011，用于发送端与接收端的时钟同步

❖ 目的MAC地址、源MAC地址(各6B)： 如果网卡的MAC地址与收到的帧的目的MAC地址匹配，或者帧的目的MAC地址为广播地址(FF-FF-FF-FF-FF-FF)，则网卡接收该帧，并将其封装的网络层分组交给相应的网络层协议。否则，网卡丢弃(不接收)该帧。

❖ 类型(Type)(2B): 指示帧中封装的是哪种高层协议的分组 (如，IP数据报、Novell IPX数据报、AppleTalk数据报等)

❖ 数据(Data)(46-1500B): 指上层协议载荷。

计算当前链路状态要保证实时监听所需要承载的最小数据量：R=10Mbps，RTTmax =512μs，Lmin / R = RTTmax， Lmin=512bits=64B，Datamin=Lmin-18=46B，18代表首部尾部其他字节数。

❖ CRC(4B): 循环冗余校验码，在以太网中会丢弃差错帧

802.3 以太网标准

许多不同的以太网标准，使用相同的MAC协议和帧格式，但可以有不同速率: 2 Mbps, 10 Mbps, 100 Mbps, 1Gbps, 10G bps ，经由不同物理介质: 光纤, 线缆

以太网交换机

是链路层设备，负责存储-转发以太网帧。检验到达帧的目的MAC地址，选择性 (selectively) 向一个或多个输出链路转发帧。利用CSMA/CD访问链路，发送帧

交换机是透明(transparent)，主机感知不到交换机的存在。具有即插即用(plug-and-play) 和自学习(self-learning) 特征，无需配置。

主机利用独享链路直接连接交换机。交换机缓存帧，在每段链路上利用 CSMA/CD收发帧，但无冲突，且可以全双工。每段链路有自己一个独立的冲突域。交换(switching)意味着 A-A’与 B-B’的传输可以同时进行，没有冲突

每个交换机有一个交换表 (switch table), 每个条目为：(主机的MAC地址, 到达主机的接口, 时间戳)

交换机通过自学习，获知到达主机的接口信息。当收到帧时，交换机通过帧的源MAC地址，“学习”到发送帧的主机、位于收到该帧的接口所连接的LAN网段，然后将发送主机MAC地址/接口信息记录到交换表中

当交换机收到帧:

1. 记录帧的源MAC地址与输入链路接口

2. 利用目的MAC地址检索交换表

3. if 在交换表中检索到与目的MAC地址匹配的入口(entry)

    then {

                if 目的主机位于收到帧的网段

                then 丢弃帧

                else 将帧转发到该入口指向的接口

     }

    else 泛洪(flood) /* 向除收到该帧的接口之外的所有接口转发 */

目的MAC地址A’，位置未知采用泛洪；位置已知采用选择性转发 

路由器与交换机比较

两者均为存储-转发设备:

▪路由器: 网络层设备 (检测网络层分组首部)

▪交换机: 链路层设备 (检测链路层帧的首部)

二者均使用转发表:

▪路由器: 利用路由算法(路由协议)计算(设置), 依据IP地址

▪交换机: 利用自学习、泛洪构建转发表, 依据MAC地址

VLANs——虚拟局域网

❖ 流量隔离(traffic isolation): 去往/来自端口1-8的帧只到达端口1-8。也可以基于MAC地址定义 VLAN, 而不是交换端口

❖ 动态成员: 端口可以动态分配给不同VLAN 路由器

❖ 在VLAN间转发: 通过路由(就像在独立的交换机之间) 实践中，厂家会将交换机与路由器集成在一起

❖ 多线缆连接：每个线缆连接一个VLAN

❖ 中继端口(trunk port): 在跨越多个物理交换机定义的VLAN 承载帧。为多VLAN转发802.1帧容易产生歧义 (必须携带VLAN ID信息) ，802.1q协议为经过中继端口转发的帧增加/去除额外的首部域

 

6. PPP协议

一个发送端，一个接收端，一条链路（拨号链路, ISDN链路）

▪ 无需介质访问控制(Media Access Control)

▪ 无需明确的MAC寻址

❖常见的点对点数据链路控制协议：

▪ HDLC: High Level Data Link Control

▪ PPP (Point-to-Point Protocol)

PPP设计需求

❖组帧：将网络层数据报封装到数据链路层帧中，可以同时承载任何网络层协议分组(不仅IP数据报)，也可以向上层实现分用（多路分解）

❖比特透明传输：数据域必须支持承载任何比特模式

❖差错检测：(无纠正)

❖连接活性(connection liveness)检测：检测、并向网络层通知链路失效

❖网络层地址协商：端结点可以学习/配置彼此网络地址

❖无需差错纠正/恢复

❖无需流量控制

❖不存在乱序交付

❖无需支持多点链路

PPP数据帧

❖ 标志(Flag): 定界符(delimiter)

❖ 地址(Address): 无效(仅仅是一个选项)

❖ 控制(Control): 无效；未来可能的多种控制域

❖ 协议(Protocol): 上层协议 (eg, PPP-LCP, IP, IPCP, etc)

❖ 信息(info): 上层协议分组数据

❖ 校验(check): CRC校验，用于差错检测

字节填充

“数据透明传输”需求: 数据域必须允许包含标志模式。那么如何判断该作为数据接收，还是作为标志处理

发送端: 在数据中的<01111110>和<01111101>字节前添加额外的字节 (“填充(stuffs)”)<01111101>

接收端：单个<01111101>字节表示一个填充字节；连续两个<01111101>字节，丢弃第1个，第2个作为数据接收。单个<01111110>字节: 标志字节

PPP数据控制协议

在交换网络层数据之前，PPP数据链路两端必须配置PPP链路，保证最大帧长和身份认证(authentication) 等功能。同时链路还需要学习/配置网络层信息。对于IP协议，通过交换IPCP 协议 (IP Control Protocol )报文 (IP分组首部的“上层协议”字段取值: 8021)，完成IP地址等相关信息配置。

7. 802.11无线局域网

均使用CSMA/CA多路访问控制协议，均有基础设施(基站)网络模式和特定网(自组网)网络模式

❖ 无线主机与基站通信：基站(base station) = 访问点(access point-AP)

❖ 基本服务集BSS(Basic Service Set) ，也称为单元(cell)。基础设施网络模式由无线主机和AP（基站）组成。自组网(ad hoc)模式只有主机

信道与AP关联

在802.11b中，2.4GHz-2.485GHz频谱划分为11个不同频率的信道，每个AP选择一个频率(信道) 。存在干扰可能，即相邻的AP可能选择相同的信道！

主机必须与某个AP关联(associate) 。扫描信道，监听包含AP名称(服务集标识符-SSID )和MAC地址的信标 (beacon)帧，选择一个AP进行关联。可能需要进行身份认证。典型情形：运行DHCP获取IP地址等信息

被动扫描：各AP发送信标帧，主机(H1)向选择的AP发送关联请求帧。AP向主机(H1)发送关联响应帧

主动扫描：主机(H1)主动广播探测请求帧 (Probe Request Frame) 。AP发送探测响应帧(Probe Response Frame) 。主机(H1)向选择的AP发送关联请求帧。AP向主机(H1)发送关联响应帧。

多路访问控制——MAC协议：CSMA/CA

当2+结点同时传输，需要避免冲突。在802.11中，使用 CSMA ，在发送数据前监听信道，避免与正在进行传输的其他结点冲突。但802.11不能像CSMA/CD那样，边发送、边检测冲突。这在无线信道很难实现，因为隐藏站、信号衰落的问题，无法侦听到所有可能的冲突。则目标变为避免冲突(avoid collisions)-CSMA/C(ollision)A(voidance)

802.11 sender

1 if 监听到信道空闲了DIFS时间 then 发送整个帧(无同时检测冲突，即CD)

2 if 监听到信道忙 then 开始随机退避计时

   当信道空闲时，计时器倒计时

   当计时器超时时，发送帧

    if 没有收到ACK then 增加随机退避间隔时间 重复第2步

802.11 receiver 

if 正确接收帧延迟SIFS时间后，向发送端发送ACK (由于存在隐藏站问题)

基本思想：允许发送端“预约”(reserve)信道，而不是随机发送数据帧，从而避免长数据帧的冲突

❖ 发送端首先利用CSMA向BS发送一个很短的RTS (request-to-send)帧，但RTS帧仍然可能彼此冲突 (但RTS帧很短)

❖ BS广播一个CTS(clear-to-send)帧作为对RTS的响应

❖ CTS帧可以被所有结点接收，从而消除隐藏站影响，发送端可以发送数据帧。其他结点推迟发送

IEEE 802.11 MAC帧结构

802.11数据帧有4个地址字段，地址 4 用于采用无线桥接（无线DS）等情形