[网络协议]计算机网络读书笔记(五)

链路层

我们将看到两种截然不同的链路层信道，第一种类型是广播信道，这种信道用于连接有线局域网、卫星网和混合光纤同轴电缆接入网中的多台主机。第二种类型的链路层信道是点对点通信链路，这一般应用在长距离链路连接的两台路由器之间，或用户办公室计算机与他们所连接的邻近以太网交换机之间等场合。

一.概述

运行链路层协议的任何设备均称为结点，结点包括主机、路由器、交换机和WiFi接入点。我们把沿着通信路径连接相邻结点的通信信道称为链路，为了将一个数据报从源主机传输到目的主机，数据报必须通过沿端到端路径上的各段链路传输。在通过特定的链路时，传输结点将数据报封装在链路层帧中，并将该帧传送到链路中。

1.1 链路层提供的服务

链路层协议可能提供的服务包括：

• 成帧：在每个网络层数据报经过链路传送之前，几乎所有的链路层协议都要将其用链路层帧封装起来。一个帧由一个数据字段和若干首部字段组成，其中网络层数据报就插在数据字段中。
• 链路接入：媒体访问控制协议规定了帧在链路上传输的规则。
• 可靠交付：当链路层协议提供可靠交付服务时，它保证无差错地经链路层移动每个网络层数据报。
• 差错检测和纠正：链路层提供一种机制用于检测当某一比特位发生接收错误时的检测以及纠正。

1.2 链路层在何处实现

链路层的主体部分是在网络适配器中实现的，网络适配器有时也称为网络接口卡。位于网络适配器核心的是链路层控制器，该控制器通常是一个实现了许多链路层服务(成帧，链路接入，差错检测等)的专用芯片。

在发送端，控制器取得了由协议栈叫高层生成并存储在主机内存中的数据报，在链路层帧中封装了该数据报(填写该帧的各个字段)，然后遵循链路接入协议将该帧传进通信链路中。在接收端，控制器接受了整个帧，抽取出网络层数据报。如果链路层执行差错检测，则需要发送控制器在该帧的首部设置差错检测比特，由接收控制器执行差错检测。

二.差错检测和纠正技术

比特级差错检测和纠正：对从一个结点发送到另一个物理上连接的邻近节点的链路层帧中的比特损伤进行检测和纠正。
为了保护比特免受差错，使用差错检测和纠正比特来增强数据D，通常要保护的数据不仅包括从网络层传递下来需要通过链路传输的数据报，而且包括链路帧首部中的链路级的寻址信息、序号、和其他字段。
即使使用了差错检测比特，也可能有未检出比特差错。

2.1奇偶校验

1 单个比特校验

• 偶校验：发送方只需包含一个附加的比特，选择它的值，使得这d+1比特中1的总数是偶数。
• 奇校验：发送方中选择校验比特值使得有奇数个1。

2.二维奇偶校验

D中的d个比特被划分为i行j列.对每行每列计算奇偶值.产生的i + j + 1奇偶比特就构成了链路层帧的差错检测比特.
当出现单个比特差错时,发生错误的行和列都会出现差错.接收方不仅可以检测差错,还可以根据行列索引来纠正它.
二维奇偶校验也可以检测(但不能纠正)两个比特错误的任何组合.
如果在同一行两个比特错误,则那一行的奇偶校验正确,但是会有两列的奇偶校验失败.如果不同行,则会有四列出错.这两种情况都无法纠错,只能检测.但是还是有一些偶数个错误的情况是二维奇偶校验无法检测的.
接收方检测和纠错的能力被称为前向纠错（FEC）.

2.2 校验和方法

在校验和技术中，一个简单的校验和方法就是将k比特整数加起来，并且用得到的和作为差错检测比特。因特网校验和就是基于这种技术，即数据的字节作为16比特的整数对待并求和。

为什么传输层使用校验和而链路层使用CRC呢?

1. 传输层使用软件实现,采用简单快速的方案是必须的(校验和)
2. 链路层的CRC用硬件实现,能够快速执行CRC操作。

2.3 循环冗余检测

循环冗余检测CRC编码也被称为多项式编码，该编码能够将要发送的比特串看作为系数是0和1一个多项式，对比特串的操作被解释为多项式算术。

编码步骤如下 :

1. 发送方和接收方实现协商一个r + 1的比特模式(比特串)G,叫做生成多项式.要求G的最高位是1
2. 对于一个给定的数据段D,发送方选择r个附加比特R,并将它们附加到D上.
3. 使得得到的d + r比特模式用模2算数恰好能被G整除.(模2算数就是异或)
   

接收方的解码步骤很简单,用G去除收到的d + r比特.如果余数非0,接收方知道出了差错.否则认为数据被正确接收.

怎么计算R？

• 要使得R对于n有: D * XOR R = nG.
• 两边同异或R得: D * = nG XOR
• 所以 R = remainder {D * / G}

三.多路访问链路和协议

点对点链路由链路一端的单个发送方和链路另一端的单个接收方组成。许多链路层协议都是为点对点链路设计的，例如点对点协议(PPP)和高级数据链路控制(HDLC)就是这样的协议；广播链路能够让多个发送和接受节点都连接到相同的、单一的、共享的广播信道上，以太网和无线局域网是广播链路层技术的例子。

多路访问问题用于协调多个发送和接收节点对一个共享广播信道的访问，而节点通过多路访问协议来规范他们在广播信道上的传输行为。当多个节点在同一时刻发送的时候，接收方可能会收到2个或多个信号的叠加，从而导致接收混乱。

我们将任何多路访问协议划分为3个类型：信道划分协议，随机接入协议，轮流协议。
对于协议我们希望有以下的特性，理想情况下对速率R bps的广播信道：
1.仅有一个结点发送数据，结点具有R bps的吞吐量
2.M个结点发送数据时，每个结点平均吞吐量R/M bps
3.协议分散，不会因为主结点故障似整个系统崩溃
4.协议简单实现不昂贵

3.1 信道划分协议

时分多路复用TDM和频分多路复用FDM是两种用于在所有共享信道节点之间划分广播信道带宽的技术。

• 时分多路复用TDM：
  将时间划分为时间帧，并进一步划分每个时间帧为N个时隙，然后把每个时隙分配给N个节点中的一个。
  TDM是有吸引力的，因为它消除了碰撞而且非常公平：每个节点在每个帧时间内得到了专用的传输速率R/N bps。然而他有两个缺陷，首先节点速度被限制即便是仅仅只有很小一部分分组要发送；其次就是节点总是等待它在传输序列中的轮次，轮到他了才能发送。
• 频分多路复用FDM
  FDM将R bps信道划分为不同的频段(每个频段具有R/N带宽)，并将每个频率分配给N个节点中的一个。因此FDM在单个较大的R bps信道中创建了N个较小的R/N bps信道。也避免了碰撞公平的划分了带宽，但是对节点所能使用的带宽加以限制。
• 码分多址CDMA
  CDMA对每个节点分配一种不同的编码，然后每个节点用它唯一的编码来对它发送的数据进行编码。

3.2 随机接入协议

在随机接入协议中，一个传输节点总是以信道的全部速率R bps进行发送。当发生碰撞的时候，会等待一个随机时延后进行重新发送，直到该帧无碰撞的通过位置。

3.2.1 时隙ALOHA
对时隙ALOHA的描述中，我们做下列假设：

• 所有帧由L比特组成
• 时间被划分成长度为L/R秒的时隙
• 节点旨在时隙起点开始传输帧
• 节点是同步的，每个节点都知道时隙何时开始
• 如果在一个时隙中有两个或多个帧碰撞，则所有节点在该时隙结束之前检测到该碰撞事件。

时隙ALOHA的操作：
1.当结点有新帧发送时，等到下一个时隙开始传输整个帧（设一个时隙传一个帧）。时隙开始时传输。
2.如果有碰撞，结点在时隙结束之前检测到这次碰撞，以p的概率在后序的每个时隙重传它的帧，直到无碰撞。

时隙ALOHA的确需要在结点中对时隙同步。刚好有一个结点传输的时隙称为一个成功时隙。时隙多路访问协议的效率定义为：当有大量的活跃结点且每个结点总有大量的帧要发送时，长期运行中成功时隙的份额。
效率：当活跃结点数量趋向无穷大时，最大效率1/e，即37%。一个给定的结点成功传送的概率是,因为有N个结点，任意一个结点成功传送的概率是N。

3.2.2 ALOHA
当一帧首次到达，节点立刻将该帧完整地传输进广播信道。如果一个传输的帧与一个或多个传输经历了碰撞，这个节点将立即以概率p重传该帧，否则等待下一个帧传输事件，在等待之后则以概率p传输该帧或者以1-p概率等待。
效率：仅为时隙ALOHA的一半：\frac{1}{2e}.一个给定结点成功传输一次的该概率是p(1-p)^{2(N-1)}

3.2.3 载波侦听多路访问CSMA
有两个重要规则如下所示：

• 载波侦听：一个节点在传输前先听信道，如果来自另一个节点的帧正向信道上发送，节点则等待直到检测到一小段时间没有传输，然后开始传输。
• 碰撞检测：当一个传输节点在传输时一直在侦听此信道。如果它检测到另一个节点正在传输干扰帧，它就停止传输，在重复“侦听-当空闲时传输”循环之前等待一段随机事件。

这两个规则都被包含在载波侦听多路访问和具有碰撞检测的CSMA协议族中。
所有结点都载波侦听了，为何当初会发生碰撞？

• B的比特沿着广播媒体传播所实际需要的时间不是0（即使2*10^8），在还没到D时，尽管B正在发，但D侦听的信道空闲，D就开始传输，于是发生了碰撞

广播信道的端到端信道传播时延决定了性能，该传播时延越长，不能侦听到已传输结点的可能就越大，碰撞越多，性能越差

3.2.4 具有碰撞检测的载波侦听多路访问CSMA/CD

1. 载波监听CSMA/CD：和在CSMA中一样发送前侦听信道
2. 没有传完一个帧就可以在短时间内检测到冲突
3. 冲突发生时则传输终止，减少对信道的浪费

从适配器的角度总结它的运行：
1.适配器从网络层一条获得一条数据报，准备链路层帧，并将其放入帧适配器缓存中
2.如果适配器侦听到信道空闲，开始传输帧；如果侦听到信道在忙，等待，直到空闲
3.传输过程中，适配器监视信道
4.如果适配器传输整个帧而未检测到其他信号，该适配器完成了该帧，否则停止传输帧
5.中止传输后，适配器等待一个随机时间量，继续侦听

选择随机回退时间间隔太大，信道会空闲，太小会再次碰撞。当碰撞结点数量较少时时间应该间隔较短，否则较长。因此使用二进制指数后退算法解决这个问题：
1.帧经历一连串n次碰撞，结点随机从{0，1，2，…，2^n-1}选择一个K值
2.一个帧经历碰撞越多，K选择的间隔越大.
以太网中，一个结点等待的实际时间量是K*512bit的时间。

3.3 轮流协议

多路访问协议的理想状态：
1.仅有一个节点活跃，速率为R bps
2.有N个节点活跃，速率为R/N bps
ALOHA和CMSA协议具备第一个状态却不具备第二个，因此激活了轮流协议，以下为其中两种比较重要的：

• 轮询协议：
  要求这些节点之一被指定为主节点，主节点以循环的方式轮询每个节点。特别是主节点首先向节点1发送一个报文，告诉节点1能够传输的帧的最多数量；在节点1传输了某些帧后，主节点告诉节点2它能够传输的帧的最多数量。
• 令牌传递协议：
  在这种节点中没有主节点，一个称为令牌的小的特殊帧在节点之间以某种固定的次序进行交换。

3.4 DOCSIS：用于电缆因特网接入的链路层协议

一个电缆接入网通常在电缆网头端将几千个住宅电缆调制解调器与一个**电缆调制解调器端接系统(CMTS)**连接。数据经电缆服务接口规范定义了电缆数据网络体系结构及其结构。

四.交换局域网

交换机运行在链路层，它们使用链路层地址而不是IP地址来转发链路层帧通过交换机网络。

4.1 链路层寻址和ARP

4.1.1.MAC协议
并不是主机或路由器具有链路层地址，而是他们的适配器具有链路层地址。因此，具有多个网络接口的主机或路由器将具有与之相关联的多个链路层地址，就像他也具有与之相关联的多个IP地址一样。

链路层交换机的任务是在主机和路由器之间承载数据报，交换机透明地执行该项任务，也就是说，主机或路由器不必明确地将帧寻址到其间的交换机。

链路层地址也叫LAN地址、物理地址、MAC地址。

MAC地址长度6字节，2^48个可能的MAC地址，通常用十六进制表示法，如5C-66-AB-90-75-B1
MAC地址一般是固定的（也有软件改变适配器MAC地址的可能），没有两块适配器有相同的MAC地址，MAC地址空间由IEEE管理，IEEE给公司固定前24个比特，后面24个比特让公司自己去生成。
MAC地址具有扁平接口。比如具有802.11接口的手机总是有相同mac地址，而当主机移动时，IP地址会改变（IP地址是层次结构）
MAC地址像身份证号，IP地址像邮政地址，有层次，会改变
当某适配器要向目的适配器发送一个帧时，发送适配器将目的适配器的MAC地址插入该帧，发送到局域网上，适配器可以接受一个并非向它寻址的帧，当适配器接受一个帧时，检查帧中的目的MAC地址与自己的MAC地址是否匹配，若匹配则取出数据报，向上传递，否则丢弃
适配器通过MAC广播地址FF-FF-FF-FF-FF-FF来广播。

4.1.2.地址解析协议ARP
1.转换网络层地址和链路层地址，如IP地址和MAC地址的转换
2.DNS为因特网中任何地方的主机解析主机名，而ARP只为在同一个子网上的主机和路由器接口解析IP地址
3.每台主机和路由器在内存中有一个ARP表，包含IP地址到MAC地址的映射关系，过期时间20分钟
4.若发送方的ARP表没有目的主机的表项，发送方公用ARP协议来解析这个地址

• 首先发送方构造一个ARP分组，字段包括发送和接受IP地址和MAC地址，ARP查询分组和响应分组格式相同
• 适配器用MAC广播地址发送该ARP查询分组，每个适配器都把ARP分组向上传递给ARP模块，检查自己的IP地址和分组中的目的IP地址是否一致
• 匹配的主机发送回一个ARP响应分组，然后查询主机更新它的ARP表，并发送它的IP数据报

5.ARP协议是一个跨越链路层和网络层的协议

4.1.3.发送数据到子网以外
路由器有几个接口，就有几个IP地址、ARP模块和适配器，假设一个路由器连着两个子网A、B：

• 子网A中的适配器要发往子网B中的适配器，先通过子网A的ARP把数据报发到子网A跟子网B相连的路由器（目的地址是路由器的MAC），路由器通过子网B的ARP将该数据报转发给目的适配器（目的地址是最终目的地的MAC）
  

4.2 以太网

以太网占领了现有的有线局域网市场，就像因特网之于全球联网的地位
集线器是一种物理层设备，作用于比特而不是帧。当0或1的比特到达一个接口时，集线器只是重新生成这个比特，将其能量强度放大，并将该比特向其他所有接口传输出去。
早期基于集线器星形拓扑以太网，现在位于中心的集线器被交换机所取代。交换机是无碰撞的存储转发分组交换机，运行在链路层。

4.2.1 以太网帧结构

• 数据字段（46~1500字节）：这个字段承载了IP数据报，以太网的最大传输单元MTU是1500字节，如果IP数据报超过了1500字节，则主机要对该数据报分片，数据字段的最小长度是46字节，如果IP数据报长度小于46，则必须被填充到46字节。
• 目的地址（6字节）：
  目的适配器的MAC地址。当目的适配器收到一个以太网帧，若目的地址是自己的MAC地址或广播地址，将数据字段传给网络层，其他则丢弃
• 源地址（6字节）
• 类型字段(2字节)：允许以太网复用多种网络层协议
• CRC（4字节）：差错检测
• 前同步码（8字节）：以太网帧以前同步码开始，前7个字节用于唤醒接收适配器，同步发送方接收方时钟，第8个字节最后两个比特（11）警告目的适配器。

以太网技术向网络层提供不可靠、无连接服务。没有通过CRC校验只是丢弃。
以太网有时候的确重传了数据，但并不知道正在传输新数据还是旧数据。

4.2.2 以太网技术
早期10BASE-2和10BASE-5标准规定两种类型的同轴电缆的10Mbps以太网，每种标准限制在500米，通过转发器得到更长运行距离。

BASE表示基带以太网。前面的数字代表速率。T代表双绞线。F代表光纤。 100BASE-FX
今天的以太网，结点经点对点由双绞铜线或光纤构成的线段与一台交换机相连。
10Gbps以太网，5类UTP线缆
线代交换机是全双工的，一台交换机和一个结点能同时向对方发送帧而没有干扰。在基于交换机的以太局域网中，没有必要使用MAC协议了！

4.3 链路层交换机

交换机的任务：接收入链路层帧，转发到出链路

• 交换机自身对子网中的主机和路由器是透明的，主机/路由器向另一个主机/路由器寻址一个帧，顺利将帧发送进局域网。
• 交换机输出接口设有缓存
• 交换机是即插即用设备，管理员无需配置
• 交换机是双工的，任何交换机接口能同时发送和接收

4.3.1 交换机转发和过滤
过滤是决定一个帧应该转发刀某个接口还是丢弃；转发是决定一个帧应该被导向按个接口，并把该帧移动到那些接口的交换机功能。交换机的过滤和转发借助于交换机表完成。
交换机表包含局域网上某些主机和路由器的表项（MAC地址，通向该地址的交换机接口，表项放置的时间）

假定目的地址为DD-DD-DD-DD-DD-DD的帧从交换机接口x到达，交换机用该MAC地址索引交换机表，有三种可能：
1.表中没有该地址，交换机广播该帧
2.表中有表项将该地址与接口x联系起来，过滤掉，因为该帧从x来，DD也通过x去，说明该帧跟DD适配器在同一个局域网段，该帧已经在包含目的地的局域网网段广播过了
3.表中有表象将该地址与接口y≠x联系起来，该帧需要被转发到与接口y相连的局域网段，放到接口y前的输出缓存，完成转发功能

4.3.2 自学习
交换机的表是自动、动态建立的，这种功能是以如下形式实现的：

1. 交换机表初始为空
2. 对于每个接口接收到的每个入帧，交换机在其表中存储该帧源MAC地址、帧到达的接口、当前时间。
3. 一段时间后，交换机没有接受到以该地址作为源地址的帧，在表中删除该地址。如果一台PC被另一台PC代替，原来PC的MAC地址将被清除

4.3.3 链路层交换机的性质

• 消除碰撞：交换机缓存帧并且不会在网段上同时传输多于一个帧，交换机提供了比广播链路局域网高的多的性能改善
• 异质的链路：交换机将链路彼此隔离，因此局域网中的不同链路能够以不同速率运行，在不同媒介上运行
• 管理：主动断开异常适配器、收集带宽使用的统计数据、碰撞率和流量类型，这些信息用来调试解决问题

4.3.4 交换机和路由器的比较

路由器是第三层的分组交换机，交换机是第二层的分组交换机
交换机：

• 交换机即插即用，相对高的分钟过滤和转发速率
• 防止广播帧循环，交换网络的活跃拓扑限制为一颗生成树
• 大型交换网络要求在主机和路由器中有大的ARP表，生成大量ARP流量和处理量
• 对广播风暴不提供任何保护，使得以太网崩溃

路由器：

• 分组不会被限制到生成树上，可以使用源到目的地的最佳路径，拓扑结构更加丰富
• 对第二层的广播风暴提供了防火墙保护
• 不是即插即用，需要人为配置IP地址
• 对分组处理时间较长，因为必须处理第三层字段
  

五.链路虚拟化：网络作为链路层

多协议标签交换MPLS

目标：对于基于固定长度标签和虚电路的技术，在不放弃基于目的地IP数据报转发的基础设施的前提下，当可能时通过选择性地标识数据报并允许路由器基于固定长度的标签(而不是目的地IP地址)转发数据报来增强其功能。

一个MPLS使能的路由器常被称为标签交换路由器，因为它通过在其转发表中查找MPLS标签，然后立即将数据报传递给适当的输出端口来转发MPLS帧。