目标：

  • 理解数据链路层服务的原理：
  • 检错和纠错
  • 共享广播信道：多点接入（多路访问）
  • 链路层寻址
  • LAN：以太网、VLANs
  • 可靠数据传输，流控制

实例和各种链路层技术的实现

6.1 引论和服务

有线链路出错率低
无线链路出错率高
两种：
（1）点到点链路，两个点之间直接相连，点可以是主机节点可以是路由器，不存在抢介质抢资源的问题。
（2）多点链路，存在编址问题，访问控制问题，多是局域网。

网络节点的连接方式

点到点连接
多点连接

数据链路和局域网

  • WAN：网络形式采用点到点链路
    • 带宽大、距离远（延迟大）
      • 带宽延迟大
    • 如果采用多点连接方式
      • 竞争方式：一旦冲突代价大
      • 令牌等协调方式：在其协调节点的发送代价大

  • 点到点链路的链路层服务实现非常简单，封装和解封装

  • LAN一般采用多点连接方式

    • 连接节点非常方便
    • 连接到共享型介质上（或网络交换机），就可以连接所有其他节点
  • 多点连接方式网络的链路层功能实现相当复杂
    • 多点接入：协调各节点对其共享性介质的访问和使用
    • 竞争方式：冲突之后的协调
    • 令牌方式：令牌产生，占有和释放等。

导论

一些术语：

  • 主机和路由器是节点（网桥和交换机也是）：nodes
  • 沿着通信路径，连接各相邻节点通信信道的是链路：links
    • 有线链路
    • 无线链路
    • 局域网，共享性链路
  • 第二层协议数据单元帧frame，封装数据报

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

物理层解决：将链路层中的帧变成物理信号发送出去，接收信号进行解析
链路层解决：相邻两物理节点间的传输
网络层实现：端到端数据的传输
传输层实现：进程到进程的区分，加强网络服务把不可靠变成可靠
应用层实现：交换报文，实现网络应用

链路层：上下文

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

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

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

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

链路层服务

  • 成帧：链路接入
    • 将数据报封装在帧中，加上帧头、帧尾
    • 如果采用的是共享性介质，信道接入获得信道访问权
    • 在帧头部使用”MAC”（物理）地址来标示源和目的
  • 在相邻两个节点完成可靠数据传输
  • 在相邻节点间进行可靠的转发
    • 低差错链路上很少使用（光纤，双绞线）
    • 高差错链路上需要进行可靠的数据传送（无线链路）
  • 流量控制:
    • 使得相邻的发送和接收方节点的速度匹配
  • 错误检测:
    • 差错由信号衰减和噪声引起
    • 接收方检测出的错误
      • 通知发送端进行重传或丢弃帧
  • 差错纠正
    • 接收端查和纠正bit错误,不通过重传来纠正错误
  • 半双工和全双工:
    • 半双工:链路可以双向传输,但一次只有一个方向

链路层在哪里实现？

  • 在每个主机、路由器、交换机的每个端口上
  • 链路层功能在“适配器”上实现或者在一个芯片组上：以太网卡，802.11；以太网芯片组（IEEE802.11是现今无线局域网通用的标准）
  • 接到主机的系统总线上
  • 硬件、软件和固件的综合体

每个主机上插了若干网卡，每个网卡实现了链路层和相应物理层的功能。
网卡也叫网络接口卡，NIC，网络适配器。
网卡接到系统总线上。开机自动运行

适配器通信

发送方：

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

接收方：

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

适配器是半自治的，实现了链路和物理层功能

6.2 差错检测和纠正

略

6.3 多点访问协议

多路访问链路和协议

两种类型的链路：

  • 点对点
    • 拨号访问的PPP
    • 以太网交换机和主机之间的点对点链路
  • 广播（共享线路或媒体）
    • 传统以太网
    • HFC上行链路
    • 802.11无线局域网

从算法角度看，称为MAC media access control
从协议角度看，称为MAP multiple access protocol

MAC(媒体访问控制)协议：分类

3大类：
（1）信道划分
把信道划分成小片（时间、频率、编码），分配片给每个节点专用
（2）随机访问
信道不划分，允许冲突
冲突后恢复
（3）依次轮流
节点依次轮流
但是有很多数据传输的节点可以获得较长的信道使用权

第一类：时分、频分、码分

时分：TDMA time division multiple access

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

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

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

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

第二类：随机存取协议

  • 当节点有帧要发送时
    • 以信道带宽的全部Rbps发送
    • 没有节点间的预先协调
  • 两个或更多节点同时传输,会发生→冲突“ collision
  • 随机存取协议规定:
    • 如何检测冲突
    • 如何从冲突中恢复(如:通过稍后的重传)
  • 随机MAC协议:
    • 时隙ALOHA
    • ALOHA
    • CSMA CSMA/CD CSMA/CA

2.1 时隙ALOHA

无法保证在某个时刻前一定能传输成功
没有延迟保证
假设：

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

运行：

  • 当节点获取新的帧，在下一个时隙传输
  • 传输时没有检测到冲突，成功；节点能够在下一时隙发送新帧
  • 检测时如果检测到冲突，失败；节点在每一个随后的时隙以概率p重传帧直到成功

优点

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

缺点

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

时隙ALOHA最好情况下信道利用率37%

2.2 纯ALOHA

无时隙ALOHA：简单、无须节点间在时间上同步
当帧需要传输：马上传输
冲突的概率增加：
帧在t0发送，和其他在[t0-1,to+1]区间内开始发送的帧冲突
和当前帧冲突的区间（其他帧在此区间开始传输）增大了一倍
效率比时隙ALOHA还要低

2.3 CSMA

carrier sensing Multiple Access 载波侦听多路访问
在时隙和纯ALOHA中， 一个节点传输的决定独立于连接到这个广播信道上的其他节点的活动。
载波监听多路访问有下面两个特点

  1. 说话之前先听。 如果其他人正在说话， 等到他们说完话为止。 在网络领域中， 这被称为载波侦听(carrier sensing),即一个节点在传输前先听信道。 如果来自另一个节点的帧正向信道上发送， 节点则等待直到检测到一小段时间没有传输， 然后开始传输。
  2. 如果与他人同时开始说话， 停止说话。 在网络领域中， 这被称为碰撞检测(collision detection),即当一个传输节点在传输时一直在侦听此信道。 如果它检测到另一个节点正在传输干扰帧， 它就停止传输， 在重复“侦听-当空闲时传输” 循环之前等待一段随机时间。

冲突仍然可能发生！由传播延迟造成：两个节点可能侦听不到正在进行的传输。
如果发生冲突，整个冲突帧的传输时间都被浪费了，是无效的传输。
注意：传播延迟（距离）决定了冲突的概率

csma/cd和csma/ca都听，但是发送之后如果冲突，cd会停止发送，ca不会

2.4 以太网 CSMA/CD 冲突检测

Carrier Sense Multiple Access with Collision Detection
CSMA/CD:

  • 载波侦听CSMA:和在CSMA中一样发送前侦听信道
  • 没有传完一个帧就可以在短时间内检测到冲突
  • 冲突发生时则传输终止,减少对信道的浪费
    • 冲突检测CD技术,有线局域网中容易实现:
  • 检测信号强度,比较传输与接收到的信号是否相同
  • 通过周期的过零点检测
    • 人类类比:礼貌的对话人

CSMA/CD算法
1.适配器获取数据报，创建帧
2.发送前：侦听信道cs
1)闲：开始传送帧
2)忙：一直等到闲再发送
3发送过程中，冲突检测CD
1)没有冲突：成功
2)检测到冲突：放弃，之后尝试重发
4.发送方适配器检测到冲突，除放弃外，还发送一个Jam信号，所有听到冲突的适配器也是如此
强化冲突：让所有站点都知道冲突
5如果放弃，适配器进入指数退避状态
在第m次失败后，适配器随机选择一个{0,1,2,…,2^m)中K，等待K*512位时，然后转到步骤2

2.5 无线局域网 CSMA/CA

冲突检测在无线中不好用，无线网络存在干扰和衰减
发的时候，如果冲突不放弃（不像CSMA/CD）
因为有冲突也可能成功，冲不冲突和成功不成功没必然联系
例如：C在给D发送，B可以检测到这个信号，但是B给A发送信息是能够成功的。
所以做不做CD没有用。
image.png
利用随机回退值实现冲突避免：
发送方

  1. 如果站点侦测到信道空闲持续DIFs长,则传输整个帧(noCD)
  2. 如果侦测到信道忙碌,那么选择一个随机回退值,并在信道空闲时递减该值:如果信道忙碌,回退值不会变化。

到数到0时(只生在信道闲时)发送整个帧如果没有收到ACK,增加回退值,重复2
802.11接收方
如果帧正确,则在SIFs后发送ACK

在 count down时,侦听到了信道空闲为什么不发送,而要等到0时在发送？
2个站点有数据帧需要发送，第三个节点正在发送
LAN CD：让2者听完第三个节点发完，立即发送

  • 冲突：放弃当前的发达，避免了信道的浪费于无用冲突帧的发送
  • 代价不昂贵

WLAN: CA

  • 无法CD，一且发送就必须发完，如冲突信道浪费严重，代价高昂
  • 思想：尽量事先避免冲突，而不是在发生冲突时放弃然后重发
  • 听到发送的站点，分别选择随机值，回退到0发送
    • 不同的随机值,一个站点会胜利
    • 失败站点会冻结计数器,当胜利节点发完再发

冲突避免也可以使用RTS-CTS交换
request to send
clear to send
两台主机A、B，都想发送信息，所以先发RTS(A) RTS(B)，结果冲突，等待
之后A再发RTS给目标主机，没有冲突，目标主机收到RTS(A) >>>目标主机和A都发送CTS(A)，CTS发生碰撞，A知道可以发送了>>>A发送帧 DATA>>>互相发送ACK(A)

第三类 轮流协议

信道划分MAC协议：

  • 共享信道在高负载时是有效和公平的
  • 在低负载时效率低下
  • 只能等到自己的时隙开始发送或者利用1/N的信道频率发送
  • 当只有一个节点有帧传时，也只能够得到1/N个带宽分配

随机访问MAC协议

  • 在低负载时效率高：单个节点可以完全利用信道全部带宽
  • 高负载时：冲突开销大，效率极低，时间很多浪费在冲突中。

轮流协议有2者的优点。

3.1轮询协议

节点之一被指定为主节点，主节点以循环的方式轮询每个点。
轮询协议消除了困扰随机接入协议的碰撞和空时隙，使得轮询取得高得多的效率。
缺点：
（1）轮询开销：轮询本身消耗信道带宽
（2）等待时间：每个节点需要等到主节点轮询后开始传输，即使只有一个节点，也许要等到轮询一周后才能够发送。
（3）单点故障：主节点失效时造成整个系统无法工作

3.2令牌传递协议

这种协议中没有主节点，一个称为令牌的小的特殊帧在节点之间以某种固定的次序进行交换。
令牌传递是分散的，并有很高的效率。
缺点：
（1）令牌开销：本身消耗带宽。
（2）延迟：只有等到抓出令牌，才可传输
（3）单点故障：令牌丢失系统级故障，整个系统无法传输；复杂机制重新生成令牌

总结

多点接入问题：对于一个共享型介质，各个节点如何协调对它的访问和使用？

  • 信道划分：按时间、频率或者编码
    • TDMA、FDMA、CDMA
  • 随机访问(动态)
    • ALOHA S-ALOHA CSMA CSMA/CD
    • 载波侦听:在有些介质上很容易(wire:有线介质).但在有些介质上比较困难( wireless:无线)
    • CSMA/CD:802.3 Ethernet中使用
    • CSMA/CA:802.11WLAN中使用
  • 依次轮流协议
    • 集中:由一个中心节点轮询
    • 分布:通过令牌控制
    • 蓝牙、FDDI、令牌环

6.4 交换局域网

MAC地址和ARP

  • 32bit IP地址
    • 网络层地址
    • 用于使数据报到达目的IP子网：前n-1跳
    • 从而到达子网中的目标节点：最后一跳
  • LAN(MAC/物理/以太网)地址：
    • 用于使帧从一个网卡传递到与其物理连接的另一个网卡（在同一个物理网中）
    • 48 bit Mac地址固化在适配器的ROM，有时也可以通过软件设定
    • 理论上全球任何2个网卡的MAC地址都不相同，例如:1A-2F-BB-76-09-AD，16进制表示（每一位代表4bits）

网络地址和MAC地址分离

IP地址和MAC地址的作用不同
a)IP地址是分层的

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

b)mac地址是一个平面的

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

分离的好处：

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

捆绑的问题：

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

LAN地址和ARP

局域网上每个适配器都有一个唯一的LAN地址
Boroadcast address=FF-FF-FF-FF-FF
MAC地址由IEEE管理和分配
制造商购入MAC地址空间（保证唯一性）
MAX平面地址，支持移动，可以将网卡接到其他网络

ARP：Address Resolution Protocol

已知B的IP地址，如何确定B的MAC地址？
在LAN上的每个IP节点都有一个ARP表
ARP表：包括一些LAN节点IP/MAC地址的映射

TTL一般是20min

编址：路由到其他LAN

  1. A创建数据报，源IP地址A，目标IP地址B
  2. A创建一个链路层帧，目标MAC地址R（下一跳路由器），该帧包含A到B的IP数据报
  3. 帧从A发送到R
  4. 帧被R接收到，从中提取出IP分组，交给上层IP协议实体
  5. R转发数据报，源IP地址为A，目标IP地址B
  6. R创建一个链路层帧，目标MAC地址B（下一跳），该帧包含A到B的IP数据报

以太网

物理拓扑：总线、星型
以太网：无连接、不可靠的服务
无连接：帧传输前，发送方和接收方之间没有握手
不可靠：接收方适配器不发送ACKs或NAKs给发送方

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

以太网的MAC协议：采用二进制退避的CSMA/CD介质访问控制形式

使用CSMA/CD