链路层和局域网

一、引论和服务

1.引论

1.1 导引

• 网络层解决了一个网络如何到达另外一个网络的路由问题

• 在一个网络内部如何由一个节点（主机或者路由器）到达另外一个相邻节点

  链路层的点到点传输层功能

• 一个子网中的若干节点是如何连接到一起的

• 点到点连接，容易实现在广域网中应用
• 多点连接：共享型介质、通过网络交换机，比较困难实现在局域网中应用，如果在广域网（两个半球之类的城市相连）实现这个多点连接，我们需要巨大的带宽，并且伴随巨大的延迟，就会出现因为时间差发生的数据碰撞，那么前面发送的全部都功亏一篑，在广域网中使用点到点连接就不会出现这种情况，一个点的接收者永远不会变，我发的只有也只能是某个点接收，反之亦然

1.2 数据链路层和局域网

• WAN:网络形式采用点到点链路

• 带宽大、距离远（延迟大） >带宽延迟积大
• 如果采用多点连接方式 • 竞争方式：一旦冲突代价大； 令牌等协调方式：在其中协调节点的发送代价大

• 点到点链路的链路层服务实现非常简单，封装和解封装
• LAN一般采用多点连接方式

• 连接节点非常方便
• 接到共享型介质上（或网络交换机），就可以连接所有其他节点

• 多点连接方式网络的链路层功能实现相当复杂

• 多点接入：协调各节点对共享性介质的访问和使用
• 竞争方式：冲突之后的协调；
• 令牌方式：令牌产生，占有和释放等

• 数据链路层负责从一个节点通过链路将（帧中的）数据报发送到相邻的物理节点（一个子网内部的2节点）

1.3 一些术语

• 主机和路由器是节点（网桥和交换机也是）：nodes
• 沿着通信路径,连接个相邻节点通信信道的是链路：links

• 有线链路
• 无线链路
• 局域网，共享性链路

• 第二层协议数据单元帧frame，封装数据报

2.链路层: 上下文

• 数据报（分组）在不同的链路上以不同的链路协议传送：

• 第一跳链路：以太网
• 中间链路：帧中继链路
• 最后一跳802.11 :

• 不同的链路协议提供不同的服务

• e.g.,比如在链路层上提供（或没有）可靠数据传送

2.1 传输类比

3.链路层服务（即需要解决的问题）

3.1 数据链路层的三个基本问题

帧定界、透明传输、差错检测

3.2 具体

1. 成帧，链路接入：

• 将数据报封装在帧中，加上帧头、帧尾部，其实就是封装解封装
• 如果采用的是共享性介质，信道接入获得信道访问权
• 在帧头部使用“MAC”（物理）地址来标示源和目的 ；不同于IP地址

2. 在（一个网络内）相邻两个节点完成可靠数据传递

• 已经学过了（第三章）
• 在低出错率的链路上（光纤和双绞线电缆）很少使用
• 在无线链路经常使用：出错率高

3. 在相邻节点间（一个子网内）进行可靠的转发

• 我们已经学习过（见第三章）！
• 在低差错链路（链路本身很可靠）上很少使用 （光纤,一些双绞线）：以太网
  

• 在高差错链路上需要进行可靠的数据传送：无线局域网
  

4. 流量控制：

使得相邻的发送和接收方节点的速度匹配

5. 错误检测：

• 差错由信号衰减和噪声引起
• 接收方检测出的错误: • 通知发送端进行重传或丢弃帧

6. 差错纠正:

接收端检查和纠正bit错误，不通过重传来纠正错误

7. 半双工和全双工:

半双工：链路可以双向传输，但一次只有一个方向

• 为什么在链路层和传输层都实现了可靠性

• 一般化的链路层服务，不是所有的链路层都提供这些服务
• 一个特定的链路层只是提供其中一部分的服务

4.链路层在哪里实现？

• 在每一个主机上

• 也在每个路由器上
• 交换机的每个端口上

• 链路层功能在“适配器”上实现(aka network interface card NIC) 或者在一个芯片组上

• 以太网卡，802.11 网卡; 以太网芯片组
• 实现链路层和相应的物理层功能
• 适配器是半自治的实现了链路和物理层功能

• 接到主机的系统总线上
• 硬件、软件和固件的综合体

4.1 适配器通信

• 发送方:

• 在帧中封装数据报
• 加上差错控制编码，实现RDT和流量控制功能等

• 接收方

• 检查有无出错，执行rdt和流量控制功能等
• 解封装数据报，将至交给上层

二、差错检测和纠正

1.错误检测

EDC=差错检测和纠正位（冗余位）
D =数据由差错检测保护，可以包含头部字段

• 错误检测不是100%可靠的!

• 协议会漏检一些错误，但是很少
• 更长的EDC字段可以得到更好的检测和纠正效果
  

2.奇偶校验（校验位+数据位）

• 单bit奇偶校验：检测单个bit级错误，当出现多位跳变，是检测不出来的：具体含义就是奇校验只能检测出奇数个位错误，而偶校验则只能检测出偶数位个错误

例如100 -》 111，利用奇校验是检测不出来的，偶数个位的错误的

• 二维奇偶校验（两个校验位）：检测和纠正单个bit错误，就是后来的CRC校验和海明校验码

3.Internet校验和

有更简单的检查方法全部加起来看是不是全1

• 目标:

检测在传输报文段时的错误（如位翻转），（注：仅仅用在传输层）

• 发送方:

• 将报文段看成16-bit整 数
• 报文段的校验和: 和 (1’的补码和)
• 发送方将checksum的值放在‘UDP校验和’字段

• 接收方:

• 计算接收到的报文段的校验和
• 检查是否与携带校验和字段值一致： 不一致：检出错误 一致：没有检出错误，但可能还是有错误

4.检验和：CRC（循环冗余校验）

4.1 概述即过程

多项式的最高次就是校验位的R位，如果多项式给的是二进制的形式则为二进制的位数-1

• 强大的差错检测码
• 将数据比特 D, 看成是二进制的数据
• 生成多项式G：双方协商r+1位模式（r次方）

生成和检查所使用的位模式

• 目标:选择r位 CRC附加位R，使得

• <D,R> 正好被 G整除 (modulo 2)
• 接收方知道 G, 将 <D,R>除以 G. 如果非0余数: 检查出错误!
  
• 能检出所有少于r+1位的突发错误

• 实际中广泛使用（以太网、802.11 WiFi、ATM）

• 相关解释：

1. 模二运算

   每个位产生的进位忽略，产生的借位也同样忽略，即0+0=0,1+1=0，其实就是异或预算撒，相同是0不同是1

2. 位串的两种表示
   

4.2 CRC 例子

1. 生成多项式（确定二进制码）

   就是用双方约定的一个串转化成另一种的表达形式这个就是多项式，次数最高的项的次数记为r

2. 移位：

   在D（数据位）后加上r位的冗余位，在接收方用约定的多项式整除这个D+r的串，能整除就对，否则为错，算出来的结果如果不足r位则在前面补零
   

3. 相除

对移位后的信息码，用生成多项式进行模2除法，产生余数

4. 得到对应的CRC码

信息位+校验位

4.3 CRC性能分析

5.其他校验：海明校验码

• 概述

之前单个校验位，只能看到全局的情况，无法应对局部的错误，所以引入多个校验位切入局部，并且还具有纠错的能力

• 步骤

1. 确定海明码的位数
   

2. 确定海明码的分布
   

3.求校验位的值，并填入表格

4. 纠错
   

三、多点访问协议

1.两种类型的链路（一个子网内部链路连接形式）：

• 点对点

• 拨号访问的PPP协议
• 以太网交换机和主机之间的点对点链路

• 广播 (共享线路或媒体)即多点访问

• 传统以太网
• HFC上行链路
• 802.11无线局域网

2.多路访问协议（介质访问控制协议：MAC）

2.1 概述

• 单个共享的广播型链路
• 2个或更多站点同时传送: 冲突（collision）

• 多个节点在同一个时刻发送，则会收到2个或多个信号叠加

• 分布式算法-决定节点如何使用共享信道，即：决定节点什么时候可以发送？
• 关于共享控制的通信必须用借助信道本身传输！

• 没有带外的信道，各节点使用其协调信道使用
• 用于传输控制信息

2.2 理想的多路访问协议

给定：Rbps的广播信道
必要条件：

1. 当一个节点要发送时，可以R速率发送.
2. 当M个节点要发送，每个可以以R/M的平均速率发送
3. 完全分布的:

• 没有特殊节点协调发送
• 没有时钟和时隙的同步

4. 简单

3.MAC（媒体访问控制）协议

3.1 概述及分类

1. 信道划分

• 把信道划分成小片（时间、频率、编码）
• 分配片给每个节点专用

2. 随机访问

• 信道不划分，允许冲突
• 冲突后恢复

3. 依次轮流

• 节点依次轮流
• 但是有很多数据传输的节点可以获得较长的信道使用权

3.2 信道划分MAC协议

3.2.1 TDMA（time division multiple access）

• 轮流使用信道，信道的时间分为周期
• 每个站点使用每周期中固定的时隙(长度=帧传输时间)传输帧
• 如果站点无帧传输，时隙空闲------>浪费
• 如：6站LAN，1、3、4有数据报，时隙2、5、6空闲

3.2.2 FDMA（frequency division multiple access）

• 信道的有效频率范围被分成一个个小的频段
• 每个站点被分配一个固定的频段
• 分配给站点的频段如果没有被使用，则空闲
• 例如：6站LAN，1、3、4有数据报，频段2、5、 6空闲

3.2.3 码分多路访问（CDMA：code division multiple access）

• 所有站点在整个频段上同时进行传输, 采用编码原理加以区分
• 完全无冲突
• 假定:信号同步很好,线性叠加

3.2.4 对比

• TDM：不同的人在不同的时刻讲话
• FDM：不同的组在不同的小房间里通信
• CDMA：不同的人使用不同的语言讲话

3.3 随机存取协议（ALOHA协议和CSMA协议）

• 当节点有帧要发送时

• 以信道带宽的全部 R bps发送
• 没有节点间的预先协调

• 两个或更多节点同时传输，会发生➜冲突“collision”
• 随机存取协议规定:

• 如何检测冲突
• 如何从冲突中恢复（如：通过稍后的重传）

• 随机MAC协议:

• 时隙ALOHA
• ALOHA
• CSMA, CSMA/CD, CSMA/CA

3.3.1 时隙（Slot又称槽）ALOHA

• 假设

• 所有帧是等长的
• 时间被划分成相等的时隙，每个时隙可发送一帧
• 节点只在时隙开始时发送帧
• 节点在时钟上是同步的
• 如果两个或多个节点在一个时隙传输，所有的站点都能检测到冲突

• 运行

• 当节点获取新的帧，在下一个时隙传输
• 传输时没有检测到冲突（如何检测冲突就看这个物理信道的频率是否为冲突时的频率），成功，节点能够在下一时隙发送新帧
• 检测时如果检测到冲突，失败，节点在每一个随后的时隙以概率p（四种可能）重传帧直到成功

• 优点

• 节点可以以信道带宽全速连续传输
• 高度分布：仅需要节点之间在时隙上的同步
• 简单

• 缺点

• 存在冲突，浪费时隙
• 即使有帧要发送，仍然有可能存在空闲的时隙
• 节点检测冲突的时间 < 帧传输的时间，必须传完
• 需要时钟上同步

• 效率

当有很多节点，每个节点有很多帧要发送时，x%的时隙是成功传输帧的时隙，最好情况：信道利用率37%

3.3.2 纯ALOHA(非时隙)

• 无时隙ALOHA：简单、无须节点间在时间上同步
• 当有帧需要传输：马上传输
• 冲突的概率增加:

• 帧在t0发送，和其它在[t0-1, t0+1]区间内开始发送的帧冲突
• 和当前帧冲突的区间（其他帧在此区间开始传输）增大了一倍
  

• 效率：效率比时隙ALOHA更差了!

3.3.3 CSMA(载波侦听多路访问)

• 冲突仍然可能发生:

由传播延迟造成：两个节点可能侦听不到正在进行的传输

• 冲突:

整个冲突帧的传输时间都被浪费了，是无效的传输(红黄区域)

• 注意：

传播延迟（距离）决定了冲突的概率

3.3.4 CSMA/CD(冲突检测)

比ALOHA更好的性能，而且简单，廉价，分布式!

• 以太网CSMA/CD算法
  
• 指数退避
  

3.3.5 无线局域网 CSMA/CA

• 概述
  

• 发送方和接收方
  

• IEEE 802.11 MAC 协议: CSMA/CA
  

• 冲突避免（预约）
  

3.3.6 线缆接入网络

3.4 轮流(Taking Turns)MAC协议

3.4.1 与前两者的对比

有2者的优点!

3.4.2 轮询

3.4.3 令牌传递

抓住令牌，表示自己有数据可发，将标志位置为0并且携带数据进行传输，最后回到发送者，变化标志位继续轮询等待需要者

4.MAC 协议总结

有线LAN：不冲突 = 成功，因为每次都会做冲突检测（CD），所以不需要数据收到后的确认
无线LAN：不冲突 != 成功，而无线就不行了，因为没有CD，所以需要接收方发送ACK来确认

四、 LANs

1.MAC 地址和ARP

1.1 概述

• 32bitIP地址（网络号 + 主机号）

• 网络层地址，如果到下一层链路层需要使用MAC地址来识别下一跳，也就是说每一层有每一层的规则，通过ARP协议来得到这个IP转化而来的MAC地址
• 前n-1跳：用于使数据报到达目的IP子网
• 最后一跳：到达子网中的目标节点

• LAN（MAC/物理/以太网）地址

• 用于使帧从一个网卡传递到与其物理连接的另一个网卡(在同一个物理网络内部)
• 48bit MAC地址固化在适配器的ROM，有时也可以通过软件设定
• 理论上全球任何2个网卡的MAC地址都不相同
• 例如： 1A-2F-BB-76-09-AD
  

1.2 网络地址和mac地址分离（为什么不只使用一个号码代表两个地址）

1.2.1 IP地址和MAC地址的作用不同

• IP地址是分层的

• 一个子网所有站点网络号一致，路由聚集，减少路由表
• 需要一个网络中的站点地址网络号一致，如果捆绑需要定制网卡非常麻烦
• 希望网络层地址是配置的；IP地址完成网络到网络的交付

• mac地址是一个平面的

• 网卡在生产时不知道被用于哪个网络，因此给网卡一个唯一的标示，用于区分一个网络内部不同的网卡即可
• 可以完成一个物理网络内部的节点到节点的数据交付

1.2.2 分离好处

• 网卡坏了，ip不变，可以捆绑到另外一个网卡的mac上
• 物理网络还可以除IP之外支持其他网络层协议，链路协议为任意 上层网络协议， 如IPX等

1.2.3 捆绑的问题

• 如果仅仅使用IP地址，不用mac地址，那么它仅支持IP协议
• 每次上电都要重新写入网卡 IP地址；
• 另外一个选择就是不使用任何地址；不用MAC地址，则每到来一个帧都要上传到IP层次，由它判断是不是需要接受，干扰一次

1.3 LAN 地址和ARP

• 局域网上每个适配器都有一个唯一的LAN地址
  

1.3.1 概述

• MAC地址由IEEE管理和分配
• 制造商购入MAC地址空间（保证唯一性）
• 类比:

(a)MAC地址：社会安全号；(b)IP地址：通讯地址

• MAC平面地址 ➜ 支持移动

可以将网卡到接到其它网络

• IP地址有层次-不能移动

依赖于节点连接的IP子网，与子网的网络号相同（有与其相连的子网相同的网络前缀）

1.4 ARP: Address Resolution Protocol

1.4.1 概述

• 在LAN上的每个IP节点都有一个ARP表
• ARP表：包括一些LAN节点IP/MAC地址的映射< IP address; MAC address; TTL>

• TTL时间是指地址映射失效的时间
• 典型是20min，缓存20分钟，如果不需要了就删掉。即查即用

1.4.2 例子：已知B的IP地址，如何确定B的MAC地址?前提是必须是在一个LANs（网络中）

1.4.3 路由到其他LAN

Walkthrough :发送数据报：由A通过R到B，假设A知道B的IP地址

• 在R上有两个ARP表，分别对应两个LAN
• 在源主机的路由表中，发现到目标主机的下一跳时111.111.111.110
• 在源主机的ARP表中，发现其MAC地址是E6-E9-00-17-BB-4B, etc
  

• A创建数据报，源IP地址：A；目标IP地址：B
• A创建一个链路层的帧，目标MAC地址是R，该帧包含A到B的IP数据报
  

• 帧从A发送到R
• 帧被R接收到，从中提取出IP分组，交给上层IP协议实体
  

• R转发数据报，数据报源IP地址为A，目标IP地址为B
• R创建一个链路层的帧，目标MAC地址为B，帧中包含 A到B的IP 数据报
  

• R 转发数据报，源IP地址为A，目标IP地址为B
• R创建一个链路层的帧，目标MAC地址为B，帧中包含 A到B的IP 数据报
  

• R 转发数据报，源IP地址为A，目标IP地址为B
• R创建一个链路层的帧，目标MAC地址为B，帧中包含 A到B的IP 数据报
  

2.以太网（Ethernet）

2.1 概述

• 目前最主流的LAN技术：98%占有率
• 廉价：30元RMB 100Mbps！
• 最早广泛应用的LAN技术
• 比令牌网和ATM网络简单、廉价
• 带宽不断提升：10M， 100M， 1G， 10G
  

2.1.1 Hups

• 节点和HUB间的最大距离是100 m
  

2.2 以太帧结构

• 前导码:

• 7B 10101010 + 1B 10101011
• 用来同步接收方和发送方的时钟速率， 使得接收方将自己的时钟调到发送端的时钟， 从而可以按照发送端的时钟来接收所发送的帧

• 地址：6字节源MAC地址，目标MAC地址

• 如：帧目标地址=本站MAC地址，或是广播地址，接收，递交帧中的数据到网络层
• 否则，适配器忽略该帧

• 类型：指出高层协议（大多情况下是IP，但也支持其它网络层协议Novell IPX和AppleTalk）
• CRC：在接收方校验

如果没有通过校验，丢弃错误帧

• 最大长度

传统以太网的最大帧长是1518字节，这个数字不包括VLAN，MPLS等标签。 对应MTU就是1500，如果有多个VLAN，MPLS等标签的话，一个4字节，可以多个嵌套，具体看支持。

2.3 以太网：无连接、不可靠的服务

• 因为以太网采用有型的物理介质传输本身就比较可靠，所以协议就不提供可靠的传输，失败丢失就重传
• 以太网的MAC协议：采用二进制退避的CSMA/CD介质访问控制形式

2.3.1 无连接

帧传输前，发送方和接收方之间没有握手

2.3.2 不可靠

接收方适配器不发送ACKs或NAKs给发送方

• 递交给网络层的数据报流可能有gap
• 如上层使用像传输层TCP协议这样的rdt，gap会被补上(源主机，TCP实体)
• 否则，应用层就会看到gap

2.4 802.3 以太网标准：链路和物理层

2.4.1 前言

2.4.2 以太网使用CSMA/CD

• 没有时隙
• NIC如果侦听到其它NIC在发送就不发送：载波侦听carrier sense
• 发送时，适配器当侦听到其它适配器在发送就放弃对当前帧的发送，冲突检测collision detection
• 冲突后尝试重传，重传前适配器等待一个随机时间，随机访问random access
• CSMA/CD算法前面再说MAC协议时已经讲到，请读者回顾

2.4.3 Manchester 编码（曼彻斯特编码）

• 要传输两种信息，时钟序列和数字信号本身

• 在 10BaseT中使用

• 每一个bit的位时中间有一个信号跳变

• 允许在接收方和发送方节点之间进行时钟同步

  节点间不需要集中的和全局的时钟

• 10Mbps，使用20M带宽，效率50%，因为这个编码会把每一个数字信号都加上信号跳变

• 应用

在IE802.3和以太网规定必须使用改编码进行

2.4.4 4b5b编码（改善Manchester 编码中经过编码后使用带宽翻倍的问题）

• 概述

字面意思就是由5个bit来代表4个bit，避免4个bit位传递相同数值，无跳变难识别，在4b5b编码讲这些冗余编码除去，使用跳变明显的形式

• 图例
  

2.5 千兆以太网

3.802.11WLAN和移动IP（无线网络和移动网络）

3.1 802.11

• 无线网络中的角色

• 无线主机：运行应用程序的端系统设备。
• 无线链路：主机通过无线通信链路连接到一个基站或者另一台无线主机。
• 基站：负责向与之关联的无线主机发送数据和从主机那里接收数据。

• 采用的介质访问控制为随机存取中的CSAM/CA

上面讲到过，请回顾

• 为什么不用CSAM/CD

在无线局域网中可能会出现隐蔽终端的可能性，导致冲突。由于衰减，无线节点信号范围有一定局限，当两个节点之间都检测不到信号，认为信道空闲时，同时向终端发送数据帧，就会导致冲突。

• 802.11的帧

与以太网的十分相似，但它也包括了许多特定用于无线链路的字段

3.2 移动IP

• 组成角色

• 代理发现：移动IP定义了一个归属代理或外部代理用来向移动节点通告其服务的协议以及移动节点请求一个外部代理所使用的协议。
• 向归属代理注册：移动 IP 定义了移动结点和/或外部代理向一个移动结点的归属代理注册或注销 COA 所使用的协议。
• 数据报的间接路由选择：该标准也定义了数据报被一个归属代理转发给移动结点的方式，包括转发数据报使用的规则、处理差错情况的规则和几种不同的封装形式.

• 流程

4.网络设备

4.1 Hub：集线器

• 网段(LAN segments) ：可以允许一个站点发送的网络范围 ，高级称呼：碰撞域

• 在一个碰撞域（即可以理解为在同一个盒子内的端口，如果某个端口是级联了另外一个hub，那么这个hub与上一个hub同样在一个碰撞域中），同时只允许一个站点在发送 （向所有端口发，然后匹配）
• 如果有2个节点同时发送，则会碰撞 （所以发送前会监听信道）
• 通常拥有相同的前缀，比IP子网更详细的前缀

• 所有以hub连到一起的站点处在一个网段，处在一个碰撞域

骨干hub将所有网段连到了一起

• 通过hub可扩展节点之间的最大距离
• 通过HUB，不能将10BaseT和100BaseT的网络连接到一起
• 理论上是一个总线型，但物理上又是一个星型
  

4.2 交换机

• 前言

为了解决hub设备在请求忙碌时期的资源浪费问题（因为同时只能有一个端口在发送，其他端口只能干瞪眼），交换机应运而生

4.2.1 概述

• 链路层设备：扮演主动角色（端口执行以太网协议）

• 对帧进行存储和转发
• 对于到来的帧，检查帧头，根据目标MAC地址进行选择性转发
• 当帧需要向某个（些）网段进行转发，需要使用CSMA/CD进行接入控制
• 通常一个交换机端口一个独立网段

• 透明：主机和路由器对交换机的存在可以不关心

• 通过交换机相联的各节点好像这些站点是直接相联的一样
• 有MAC地址；无IP地址

• 即插即用，自学习：

交换机无需配置

• 也可以级联

4.2.2 多路同时传输

• 主机有一个专用和直接到交换机的连接
• 交换机缓存到来的帧
• 对每个帧进入的链路使用以太网协议，没有碰撞；全双工

• 每条链路都是一个独立的碰撞域
• MAC协议在其中的作用弱化了

• 交换例子：A-to-A’和 B-to-B’可以同时传输，没有碰撞

4.2.3 交换机转发表

• 交换机如何知道通过接口1到达A，通过接口5到达 B’?

每个交换机都有一个交换表 switch table, 每个表项: (主机的MAC地址,到达该MAC经过的接口，时戳) 比较像路由表!

• 每个表项是如何创建的？如何维护的？

通过交换机的自学习逐渐创建而来的

4.2.4 交换机：自学习

交换机通过学习得到哪些主机（mac地址）可以通过哪些端口到达

• 当接收到帧，交换机学习到发送站点所在的端口（网段）
• 记录发送方MAC地址/进入端口映射关系，在交换表中
  

自学习转发的例子

如果泛洪（向所有端口进行转发）以后匹配到了对应端口，发送方和接收方是不需要二次转发并且回传帧是不需要或泛洪的，因为你已经就知道了目的地的路径并且自学习到了转发表中

4.2.5 交换机：过滤／转发 / 泛洪

一个帧在发送的时候会有三种命运：

1. 过滤：就是当发出去的端口和接收的端口一样时就会选择过滤
2. 转发：最普遍的命运，知道目标MAC地址和端口的绑定关系直接进行转发就可以了
3. 泛洪：不知道目标MAC地址和端口的绑定关系则进行泛洪查找
   

4.2.6 交换机级联及多交换自学习的例子

4.3 交换机与路由器

读者们可以了解一下交换机的生成树算法

5.VLANS（虚拟局域网）

5.1 需求

5.2 概述