《计算机网络：自顶向下方法》第六章--链路层和局域网

网络层提供了任意两台主机之间的通信服务。在两台主机之间，数据报跨越一系列通信链路传输，（一些是有线链路，一些是无线链路）从源主机开始，通过一系列分组交换机到达目的主机

链路层中有两种不同类型的链路层信道。第一种类型是广播信道，这种信道用于连接有线网络、卫星网和混合光纤同轴电缆接入网中的多台主机。由于许多主机与相同的广播信道连接，因此需要媒体访问协议来协调帧的传输。第二种类型是点对点通信链路，比如长距离链路连接的两台路由器之间、或计算机与临近的以太网交换机之间。点对点链路的访问比较简单，包括从经电话线的拨号服务到经光纤链路的告诉点到点帧传播

6.1 链路层概述

本节中件运行链路层协议的任何设备称为节点。节点包括主机、路由器、交换机和WIFI接入点

把沿着通信路径连接相邻节点的通信信道称为链路。为了将一个数据报从源主机传输到目的主机，数据报必须通过沿端到端路径上的各段链路传输

以下图为例，无线主机之一向服务器之一发送一个数据报，该数据报将会通过六段链路：发送主机与WIFI接入点之间的WIFI链路->接入点和链路层交换机之间的以太网链路->链路层交换机与路由器之间的链路->两台路由器之间的链路->交换机和服务器之间的以太网链路

在通过特定的链路时，传输节点间数据报封装在链路层帧中，并将该帧传送到链路中

网络层与链路层的关系

假设有个人要去一个很远的地方旅行，并且计划先后乘坐火车、飞机、公交车到达目的地。为此他决定先去旅行社购买机票和火车票。旅行社不仅为他预定好了旅途过程中所需要的机票和火车票，而且也为他制定了一个详细的行程表，详细到几点几分需要乘坐飞机和火车都一目了然。当然，机票和火车票只有在特定的那个时间区间才有效

这个人相当于数据报，每个运输区段相当于一段链路，每种运输方式相当于一种链路层协议旅行社相当与路由选择协议

6.1.1 链路层提供的服务

任一链路层的基本服务都是将数据报通过单一通信链路从一个节点移动到相邻节点。除此之外，链路层提供的服务细节取决于链路层协议

·成帧：每个网络层数据报在通过链路传送之前，几乎所有的链路层协议都要求将其先用链路层帧封装。一个帧由一个数据字段和若干首部字段组成，其中网络层数据报就存储在数据字段中

·链路接入：媒体访问控制（Medium Access Control，MAC）协议规定了帧在链路上传输的规则。对于只有一个发送方和一个接收方的点对点链路，MAC协议规定无论何时，只要链路空闲，发送方都能够发送帧。对于多个节点共享单个广播链路时（即多路访问问题）MAC协议用于协调多个节点的帧传输

·可靠交付：链路层提供可靠交付服务时，保证无差错地经链路层移动每个网络层数据报。链路层的可靠交付服务通常是通过确认和重传取得的。链路层的可靠交付服务一般用于易产生高差错率的链路（比如无线链路），目的是能够本地纠正差错，而不是通过运输层或应用层协议强制进行端到端重传。对于低比特差错的链路（比如光纤、同轴电缆、双绞铜线链路）链路层的可靠交付服务被认为是一种不必要的开销

·差错检验和纠正：由于信号衰减和电磁噪声，帧中的比特可能从1被错误的判断成0。这种比特差错因为没有必要重传一个有错误的数据报，所以许多链路层协议提供检测机制。通过使发送节点在帧中增加差错检测比特，让接收节点进行差错检测。网络层和运输层中也提供了因特网检验和。但是链路层的差错检验更加负载，并且在硬件中实现。差错纠正不仅能检测帧中出现的比特差错，而且能够确定帧中出现差错的位置，并纠正差错

6.1.2 链路层在何处实现

链路层的主体部分是在网络适配器（network adapter）中实现的，网络适配器又是也称为网络接口卡（Network Interface Card，NIC）。位于网络适配器核心的是链路层控制器，该控制器通常是一个实现了许多链路层服务的专用芯片

在发送端，控制器取得了由协议栈较高层生成并存储在主机内存中的数据报，在链路层帧中封装该数据报，然后遵循链路接入协议将该帧传进通信链路中

在接收端，控制器接收整个帧，抽取出网络层数据报。如果链路层执行差错检验，则需要发送控制器在该帧的首部设置差错检验比特，由接收控制器执行差错检测

如上图所示，大部分的链路层是在硬件中实现的，但部分链路层是运行于主机CPU上的软件中实现的。链路层的软件组件实现了高层链路层功能，如组装链路层寻址信息和激活控制器硬件。在接收端，链路层软件响应控制器钟端、处理差错条件和将数据报向上传递给网络层

链路层是硬件和软件的结合体，是协议栈中软件与硬件交接的地方

6.2 差错检测和纠正技术

比特级差错检测和纠正，即对从一个节点发送到另一个物理上连接的邻近节点的链路帧中的比特损伤进行检测和纠正

 上图中，在发送节点，为了保护比特免受差错，使用差错检测和纠正比特（Error-Detection and-Correction，EDC）来增强数据D。通常要保护的数据不仅包括从网络层传递下来需要通过链路传输的数据报，还包括链路帧首部中的链路级的寻址信息、序号和其他字段。链路级帧中的D和EDC都被发送到接收节点。在接收节点，接收到比特序列D‘和EDC’。由于传输中的比特翻转，所以D‘和EDC’可能与初始的D和EDC不同

接收方通过差错检测对链路层帧进行检测，绝大多数情况下都可以检测出错误，但也可能有未检出比特差错

所以需要选择一个差错检测方案，使得未检出比特差错事件的发生概率最小。一般来说，差错检验和纠错技术越复杂，导致的开销就越大

常见的三种检测差错技术为：奇偶校验、检验和方法、循环冗余检验

6.2.1 奇偶校验

1.单比特就校验方案

单个奇偶校验位是比较简单的方式，假设下图中要发送的信息D有d个比特。

在偶校验方案中，发送方只需要包含一个附加的比特，选择这个比特的值，使得d+1个比特中1的总数为偶数；在奇校验方案中，选择校验比特值使得有奇数个1

采用单个奇偶校验位方式，接收方的操作也比较简单。接收方只需要计算接受的d+1个比特中1的数量即可。如果出现奇数个值为1的比特，则说明出现了奇数个比特差错

但如果出现偶数个比特差错，就会导致一个未检出的差错。在突发差错的情况下，使用单比特奇偶校验保护的一帧中未检测出差错的概率能够达到50%

2.二维奇偶校验方案

将单比特奇偶校验方案优化为二维一般化方案。D 中的 d 个比特被划分为 i 行 j 列。对每行和每列计算奇偶值。产生的i+j+1奇偶比特构成了链路层帧的差错检验比特

如果在初始d比特的信息中出现了比特差错，那么包含比特值改变的行和列校验值都会出现差错。因此接收方不仅可以检测到出现了单个比特差错的事实，还可以利用存在奇偶校验差错的行和列的索引定位发生差错的比特并纠正它

上图表示了位于（2，2）的值为1的比特损坏，该差错就是一个可以在接收方检测并纠正的差错。实际上除了初始信息D会发生错误，校验比特本身也可能出现错误同时也可以被纠正。

二维奇偶校验能够检测一个分组中两个比特差错的任意组合，但并不能纠正

6.2.2 检验和方法

检验和方法，将长度为d的比特数据作为一个k比特整数序列处理。一种简单的检验和方法就是将这k比特整数加起来，并且将得到的和作为差错检测比特

因特网检验和将数据的字节作为16比特的整数对待并求和。这个和的反码形成了携带在报文段首部的因特网检验和。接收方通过对接受的数据的和取反码，判断其和是否全为1比特来检测检验和

检验和方法需要相对小的分组开销。与后面的链路层CRC相比，它们提供相对弱的差错保护

为什么运输层使用检验和而链路层使用CRC呢？

运输层通常是在主机中作为用户操作系统的一部分用软件实现的。因为运输层差错检测用软件实现，采用简单而快速的方案（如检验和）是重要的

链路层的差错检验在适配器中用专用的硬件实现，能够快速执行更复杂的CRC操作

6.2.3 循环冗余检测

如今广泛使用的差错检测奇数基于循环冗余检测（Cyclic  Redundancy Check，CRC）编码。CRC编码也称为多项式编码，该编码能够将要发送的比特串看作系数为0或1的一个多项式

有d比特的数据D，发送节点将它发送给接收节点。发送方和接收方首先必须协商一个r+1比特模式，称为生成多项式，将其表示为G。G的最高有效位比特为1

对于给定的数据段D，发送方要选择r个附加比特R，并将它们附加到D上，使得得到的d+r比特模式，采用模2运算恰好可以被G整除。接收方用约定的G除以d+r比特，如果余数非0则出现差错

在所有的CRC计算中都采用模2算术，在加法中不进位，减法中不借位。也就是加减法相同并等价为按位异或。即1011 xor 0101=1110，1011-0101=1110

R的计算方法:求出R使得 

计算步骤

1. 计算冗余位的位数，即生成多项式的最高阶数

2. 在信息位后补冗余位个数的0

3. 将第二步的结果与生成多项式相除，这里采用的除法叫做模2除法，就是只要部分余数的高位为1，便可商1 之后上下做的减法是异或。

4. 经过第三步不断地计算后得到余数
   将信息为后面补的0换成余数

下图是D=101110，d=6，G=1001，r=3时的计算过程。在这种情况下传输的全部比特为101110011

 国际标准定义了8、12、16和32比特生成多项式G。在CRC-32中32比特的标准被多种链路层IEEE协议使用，G=100000100110000010001110110110111

6.3 多路访问链路和协议

目前有两种类型的网络链路：点对点链路和广播链路。点对点链路（point-to-point link）由链路一端的单个发送方和链路另一端的单个接收方组成。点对点协议和高级数据链路控制就用于点对点链路。广播链路（broadcast link）能够让多个发送和接收节点都连接到相同的、单一的、共享的广播信道上。“广播”是指当任何一个节点传输一个帧时，信道广播该帧，每个节点都收到一个副本

这里需要考虑多路访问问题：如何协调多个发送和接收节点对一个共享广播信道的访问。因此产生了多路访问协议（multiple access protocol），即节点通过协议来规范在共享广播信道上的传输行为

由于所有节点都能够传输帧，因此多个节点可能同时传输帧。节点可能在同一时刻接受到多个帧，也就是传输的帧在接收方出现碰撞，碰撞的信号纠缠在一起，所以没有有效的帧传输，导致广播信道的使用被浪费

目前由三种类型的多路访问协议用于解决上述问题：信道划分协议（channel partitioning protocol）、随机接入协议（random access protocol）、轮流协议（taking-turns protocol）

6.3.1 信道划分协议

在计算机网络与因特网中学习过时分多路复用（TDM）与频分多路复用（FDM）是两种能够用于所有共享信道节点之间划分广播信道带宽的技术

TDM

假设一个支持N个节点的信道且信道的传输速率为 R bps。TDM将时间划分为时间帧（time frame），并把每个时间帧划分为N个时隙（slot）。这里的时间帧与链路层传输的数据单元帧并不是同一个，后面为了区分将链路层帧称为分组

给链路上的每个节点分发不同数量的时隙，只要节点有分组需要发送，就在循环的TDM帧中通过分配的时隙传输单个分组

TDM允许每个节点在固定的时间段传输，每个节点允许的传输时长是相同的。每个节点在每个帧时间内都获得 R/N bps的传输速率。但有两大缺陷：①节点被限制于 R/N bps的平均速率②即使该节点是唯一需要发送分组的节点，它也必须在循环中等待它在传输序列中的轮次

FDM

TDM在时间上共享广播信道，而FDM将 R bps信道划分为不同的频段，每个频段都具有R/N的带宽，将每个频率分配给N个节点中的一个。FDM在单个较大的 R bps信道中创建了N个较小的 R/N bps信道。FDM避免了碰撞，在N个节点之间公平的划分了带宽，但它具有与TDM同样的问题

码分多址

码分多址（Code Division Multipke Access，CDMA）。TDM和FDM分别为节点分配时隙和频率，而CDMA对每个节点分配不同的编码。每个节点使用唯一的编码对发送的数据进行编码。选择合适的编码可以使得不同的节点同时传输，并且各自相应的接收方能正确的接收发送方编码的数据比特。具有一定的抗干扰性，广泛适用于军用系统，民用蜂窝电话

6.3.2 随机接入协议

第二大类多访问协议是随机接入协议。在随机接入协议中，一个节点总是以信道的全部速率进行发送。如果发生碰撞，则涉及碰撞的每个节点都重复发送分组，直至该分组无碰撞发送成功为止。但一个节点发生碰撞时，无需立刻重新发送该分组，而是在重新发送该分组之前等待一个随机时延。每个节点独立地选择随机时延，所以可以减少与其他节点的碰撞

6.3.2.1 时隙ALOHA

前提假设

假设所有帧由L比特组成

假设时间被划分成长度为L/R秒的时隙，即一个时隙等于传输一帧的时间

假设节点只在时隙七点开始传输帧

假设节点是同步的，每个节点都知道时隙何时开始

如果一个时隙中由两个或者多个帧碰撞，则所有节点在该时隙结束之前都能检测到该碰撞

在每个节点中，时隙ALOHA的操作包括：

①当节点有一个新帧要发送时，需要等到下一个时隙开始并在该时隙中传输整个帧

②如果没有碰撞，则该节点成功的传输，不需要考虑重传

③如果有碰撞，该节点以概率p在后续的时隙中重传，直至该帧被无碰撞的传输出去

这个概率p是一个0-1分布模型，即要么以p的概率重传，要么以1-p的概率在下一个时隙中重传

相较于信道划分的优点：当节点是唯一活跃的节点时，时隙ALOHA允许该节点以全速R连续传输

当有多个活跃节点时，一部分时隙将会产生碰撞，因此被浪费；所有活跃节点由于概率传输策略会节制传输，所有有一部分时隙处于空闲状态。因此定义刚好有一个节点传输的时隙被称为成功时隙（successful slot）

时隙多路访问协议的效率：当有大量的活跃节点且每个节点总有大量的帧要发送，长期运行中成功时隙的比例

时隙ALOHA最大效率推导

假设每个节点总有帧需要发送，并且节点对新帧和已经经历过碰撞的帧都已概率p传输

假设有N个节点，每个节点在每个时隙以概率p传输一帧

则一个给定时隙是成功时隙的概率等于一个节点传输并且其他N-1个节点不传输的概率

一个节点传输的概率是 p ，剩余N-1个节点不传输的概率是，因此一个节点成功传输的概率是

由于总共有N个节点，所以任意一个节点成功传输的概率是

当N趋近于无穷大时，也就是有大量的节点有很多的帧要传输时，该协议的最大效率为（1/e），即只有37%的时隙做有用功，26%的时隙产生碰撞

6.3.2.2 ALOHA

时隙ALOHA协议要求所有的节点同步传输，也就是在每个时隙开始时传输。而纯ALOHA协议不监听信道，不按照时隙发送

如果出现碰撞，数据被丢弃或出错则发送失败。接受方如果没接收到数据或收到错误数据，则向发送方返回错误信息或不回送确认信息。发送方如果没有接收到确认信息，则重传

为了使帧能够成功的传输，在时间间隔[t0 -1，t0]中不能有其他节点开始传输。这种传输将与节点i的帧传输起始部分相重叠，与前面时隙ALOHA类似的概率计算，一个给定节点成功传输一次的概率是，因此可以计算出纯ALOHA协议的最大效率经为（1/2e），也就是时隙ALOHA的一半

6.3.2.3载波侦听多路访问（CSMA）

在时隙和纯ALOHA中，一个节点传输的决定独立于连接到这个广播信道上的其他节点的活动。也就是ALOHA不监听其他节点的活动，只是节点不断地尝试发送直至成功

在载波侦听多路访问（Carrier Sense Multiple Access，CSMA）和具有碰撞检测的CSMA（CSMA with Collision Detection，CSMA/CD）中包括两个规则分别是载波侦听和碰撞检测

载波侦听：一个节点在传输之前先侦听信道，如果检测到另一个节点正在传输干扰帧，则停止传输

碰撞检测：一个节点在传输时一直侦听信道，如果检测到另一个节点正在传输干扰帧，则停止传输

为什么所有节点都进行了载波侦听还会出现碰撞？
以下图为例，在t0，节点B侦听到信道是空闲的，因此B开始传输，沿着广播媒体在两个方向上传播它的比特。下图中B的比特随时间开始向下传播，因此B沿着广播媒体传播的实际时间并不是零

在t1，节点B传输的比特还没有到D，因此D侦听到信道空闲，开始传输它的帧。在一个短暂的时间之后，B的传输开始在D位置干扰D的传输

从图中可以明显看出，广播信道的端到端信道传播时延在决定性能方面起着关键的作用。该传播时延越长，载波侦听节点不能侦听到网络中另一个节点开始传输的机会就越大

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

当节点执行碰撞检测时，一旦检测到碰撞会立刻停止传输。在多路访问协议中加入碰撞检测，通过不传输无用的损坏的帧，可以改善协议性能

从与广播信道相连接的适配器角度分析CSMA/CD协议的运行：
①适配器从网络层获取一条数据包，准备链路层帧，将数据报存入帧适配器的缓存中

②如果适配器侦测到信道空闲，则开始传输帧。如果侦测到信道正忙（有信号能量从信道进入适配器），则执行等待

③传输过程中，适配器实时监视其他使用该广播信道的适配器的信号能量

④如果适配器传输整个帧而没有检测到其他适配器的能量，则适配器成功传输该帧；若检测到其他适配器的能量，则终止传输该帧

⑤终止传输后，等待一个随机时间量，然后执行步骤二

随机时间量的确定应当满足：当碰撞节点数量少时，时间间隔短；当碰撞节点数量大时，时间间隔长

用于以太网以及DOCSIS电缆网络多路访问协议中的二进制指数后退算法（binary exponential backoff）确定了随机时间量。当传输一个给定帧时，在该帧经历了n次碰撞之后，节点随机的从{0，1，2，……，}中选择一个K值。一个帧经历的碰撞越多，K值选择的间隔越大

对于以太网来说，一个节点等待的实际时间时K·512比特时间（即发送512比特进入以太网所需要的时间量的K倍）

假设一个适配器首次尝试传输一个帧，并在传输中它检测到碰撞。然后该节点以概率0.5选择K=0，以概率0.5选择K=1。如果该节点选择K=0，则它立即开始侦听信道。如果这个适配器选择K=1，它在开始“侦听-当空闲时传输”。周期前等待512比特时间（例如对于100Mbps 以太网来说为5.12ms)。在第2次碰撞之后，从{0，1，2,3中等概率地选择K。在第3次碰撞之后，从﹔0，1，2，3，4，5，6，7/中等概率地选择K。在10次或更多次碰撞之后，从 |0，1，2，…，1023|中等概率地选择K。因此从中选择K的集合长度随着碰撞次数呈指数增长;正是由于这个原因，该算法被称为二进制指数后退。

6.3.2.5 CSMA/CD效率

当只有一个节点有一个帧发送时，该节点能够以信道的全部速率进行传输。如果有多个节点有帧要发送，则信道的有效传输速率会减少很多。因此定义CSMA/CD效率：当有大量的活跃节点，并且每个节点有大量的帧要发送时，帧在信道中无碰撞的传输的那部分时间在长期运行中的比例

                                                     

CSMA/CD的效率计算公式类似上式。其中dprop表示信号能量在任意两个适配器之间传播需要的最大时间，dtrans表示传输一个最大长度的以太网帧的时间。从计算式子可以看出，当dprop接近0时，效率接近1

6.3.3 轮流协议

多路访问协议的两个理想特性是：①但只有一个节点活跃时，该郭跃节点具有R bps 的吞吐量②当有M个节点活跃时，每个活跃节点的吞吐量都接近R/M bps 。然而ALOHA协议和CSMA协议都只具备第一个特性，但不具备第二个特性。由此产生了轮流协议（taking-turns protocol）。轮流协议有很多种，比较重要的包括轮询协议和令牌传递协议

轮询协议（polling protocol）：要求所有的节点中选择一个主节点，主节点以循环的方式轮询每个节点。主节点向节点1发送报文指定节点1能够传输帧的最多数量，节点1传输部分帧之后，主节点指定节点2能够传输的帧的最多数量。主节点通过观察在信道上是否缺乏信号，来决定每个节点何时完成了帧的发送

轮询协议消除了随机接入协议的碰撞和空时隙问题。但是引入了轮询时延，也就是通知节点可以传输所需要的时间。并且当主节点有故障时，整个信道都将不可操作损坏

令牌传递协议（token-passing protocol）：这种协议中没有主节点。一个称为令牌的小的特殊帧在节点之间以某种固定次序进行交换。比如节点1将令牌发送给节点2，节点2将令牌发送给节点3……依此类推。如果一个节点接收到令牌，当有帧发送时则持有该令牌；否则立刻将令牌传递给下一个节点。

令牌的传递是分散的，并且有很高的效率。但是一个节点的故障可能会使得整个信道崩溃。一个节点如果没有释放令牌，则必须调用某些恢复步骤使得令牌返回到循环中来。

上面描述的轮询协议更像是有主持人统筹负责成员的工作量分配，而令牌传递协议更像无组织的击鼓传花活动

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

一个电缆接入网通常在电缆网头端将几千个住宅电缆调制解调器与一个电缆调制解调器端接系统（Cable Modem Termination System，CMTS）连接。数据经电缆服务接口规范（DOCSIS）定义了电缆数据网络体系结构及其协议

DOCSIS使用FDM将下行（CMTS->调制解调器）和上行（调制解调器->CMTS）网络段划分为多个频率信道。每个上行和下行信道均为广播信道。CMTS在下行信道中传输的帧被所有在信道上等待接收的电缆调制解调器接收。由于在下行信道上仅存在单一CMTS传输，所以不存在多路访问问题。但是上行方向将有多个调制解调器共享上行信道，因此可能存在碰撞

如上图所示，每个上行信道被划分为时间间隔，每个时间间隔包含一个微时隙序列，电缆调制解调器可在该微时隙中向CMTS传输。CMTS在下行信道上通过发送MAP报文指定电缆调制解调器，使其能够在微时隙中传输有控制报文指定的时间间隔，微时隙被明确分配给电缆调制解调器，所以CMTS可以保障微时隙中没有碰撞传输

电缆调制解调器在一些特殊的微时隙内向CMTS发送请求帧，使得CMTS获取电缆调制解调器的发送需求。这些微时隙请求帧以随机接入的方式传输，因此可能发生相互碰撞

由于电缆调制解调器不具备信道侦听和碰撞检测功能，所以只能通过下一个下行控制信报中是否有相应来判断。如果没有响应，则说明请求帧发生碰撞，电缆调制解调器使用二进制回退将其请求帧延缓到之后的微时隙中发送

6.4 交换局域网

如下图所示，包括两台服务器和一台与4台交换机连接的路由器。由于这些交换机运行在链路层，所以它们交换链路层帧（而不是网络层数据报），所以不适用RIP或OSPF之类的路由选择算法

交换机使用链路层地址而不是IP地址来转发链路层帧通过交换机网络

6.4.1 链路层寻址和ARP

主机和路由器都具有网络层地址，同时也具有链路层地址，这两层地址都是必不可少的

主机和路由器接口除了MAC地址之外还有网络层地址的原因

①局域网是为网络层协议设计的，而不只是IP和因特网。如果适配器只有IP地址的话，适配器将不能够方便的支持其他网络层协议（比如IPX或DECnet），因此需要MAC地址来实现

②如果适配器使用网络地址而非MAC地址，则网络层地址必须存储在适配器的RAM中，并且在每次移动适配器时都需要重新配置

③如果在适配器中不适用任何地址，则需要将接收到的所有帧都向上传递至网络层，网络层再判断网络地址是否匹配。这会导致主机将会被局域网中发送的每个帧终端（即使该帧的目的地是局域网内的其他节点）

为了使网络体系结构中的各个层次尽量独立，每个层次都需要它们自己的寻址方案。比如：应用层的主机名、网络层的IP地址、链路层的MAC地址

1.MAC地址

实际上，并不是主机或路由器具有链路层地址，而是他们的适配器（即网络接口）具有链路层地址。如果主机或路由器有多个网络接口，则有多个链路层地址

链路层交换机并不具有网络接口（与主机和路由器相连）的链路层地址，因为链路层交换机的任务是在主机与路由器之间承载数据报。主机或路由器不必明确地将帧寻址到途径的交换机，交换机透明的执行该任务

链路层地址有多个名字：LAN地址（LAN address）、物理地址（physical address）、MAC地址（MAC address）

对于大多数局域网，MAC地址长度为6个字节，因此共有个可能的MAC地址。这些地址通常采用十六进制表示法，每个字节表达为一对十六进制数。MAC地址被设计为永久的，但是目前也实现了通过软件改变适配器的MAC地址。没有任何两个适配器具有相同的MAC地址

IP地址可以理解为人的收货地址，可能由于空间移动发生变化。而MAC地址类似为人的身份证号码，不论何时都为同一个。这种设计叫做扁平化设计

当适配器要向目的适配器发送一个帧时，发送适配器将会把目的适配器的MAC地址插入到该帧中，并将这个帧广播到所有接口上。但适配器接收到一个帧时，把自身的MAC地址与帧中的MAC地址进行匹配，如果匹配则提取出封装的数据报，并将该数据报沿协议栈向上传递。如果不匹配，则适配器丢弃该帧

有时可能会出现适配器需要局域网上所有的其他适配器接收和处理它发送的帧。在这种情况下，发送适配器在该帧的目的地址字段中插入一个特殊的MAC广播地址，以6字节地址的局域网来说，广播地址是48个连续的1组成的字符串（即十六进制FF-FF-FF-FF-FF-FF）

2.地址解析协议

由于网络层地址（如IP地址）和链路层地址的存在，所以需要实现它们之间的相互转换。通过地址解析协议（Address Resolution Protocol，ARP）来实现

如上图，假设IP地址为222.222.222.220的主机要向主机222.222.222.222发送IP数据报。源和目的地址均位于相同的子网中。为了发送数据报，源必须要向适配器提供IP数据报和目的主机222.222.222.222的MAC地址。然后发送适配器将会构造一个包含目的地MAC地址的链路层帧，并将该帧发送进局域网

发送主机如何确定IP地址为222.222.222.222的目的主机的MAC地址？

在发送主机中的ARP模块，取在同一局域网内的任何IP地址作为输入，然后返回相应的MAC地址。

 在本例中发送主机222.222.222.220向自身的ARP模块提供目的主机的IP地址222.222.222.222，其ARP模块返回相应的MAC地址49-BD-D2-C7-56-2A

ARP的工作模式与DNS类似，DNS将主机名解析为IP地址，ARP将IP地址解析为MAC地址。不同的是，DNS为因特网中任何地方的主机解析主机名，而ARP只为同一个子网上的主机和路由器接口解析IP地址

每台主机或路由器在内存中都有一个ARP表，这张表包含IP地址到MAC地址的映射关系，ARP表也包含一个寿命（TTL）值，标识从表中删除映射的时间。ARP表中无需包含子网中的所有主机或路由器，有些主机或路由器可能自始至终都不在该表中，部分可能已经过期，一个表项过期的时间是20分钟

如果ARP表中没有目的主机的表项，则发送方使用ARP协议来解析地址。发送方构造一个ARP分组，分组中包括发送和接收IP地址以及MAC地址。ARP查询报文和响应报文具有相同的格式，ARP查询分组的目的是询问子网上所有的其他主机和路由器（通过广播MAC地址FF-FF-FF-FF-FF-FF），从而获得目的IP地址对应的MAC地址

ARP协议的查询报文是在广播帧中发送的，而响应报文是在一个标准帧中发送的。ARP是即插即用的，也就是说ARP表是自动建立的，而无需系统管理员配置。如果主机与子网断开连接，则子网中的节点会最终删除有关该主机的表项

由于ARP协议，实现了网络层和链路层地址的转换，因此很难直接界定为网络层协议或链路层协议，ARP可以理解为跨越链路层和网络层边界两边的协议

3.发送数据报到子网之外

从上图可以看出，每个主机仅有一个IP地址和MAC地址，但是一台路由器的每个接口都有一个IP地址，同样一台路由器的每个接口也有一个ARP模块和一个适配器。上图中的路由器有两个接口，所以有两个IP地址、两个ARP模块、两个适配器。每个适配器都有自己的MAC地址

上图中的两个子网分别为子网1（111.111.111.xxx）和子网2（222.222.222.xxx）。假设主机111.111.111.111要向主机222.222.222.222发送一个IP数据报。发送主机需要向它的适配器传递数据报，同时还需要一个目的MAC地址。由于源主机与目的主机并不在同一个子网中，所以如果目的MAC地址是主机222.222.222.222的MAC地址（49-BD-D2-C7-56-2A），则子网中的所有适配器的MAC地址都不匹配，该数据报将会被丢弃

 实际上子网1向子网2发送数据报，必须先经过路由器接口111.111.111.110。所以对于封装了该数据报的帧来说，目的MAC地址应该为路由器接口111.111.111.110的MAC地址E6-E9-00-17-BB-4B。

发送主机通过ARP获取路由器的MAC地址，并创建一个帧（帧中包含寻址到222.222.222.222的数据报），将该帧发送到子网1中，子网1中的路由器适配器获取该帧，得知该帧是用于寻址的，就将该帧传递给路由器的网络层。路由器通过查询路由器中的转发表，得知要从了接口222.222.222.220转发。该接口把数据报传递给适配器，适配器将数据报封装到一个新的帧中，并将帧转发到子网2中

6.4.2 以太网

网络发展早期，以太网面临着令牌环、FDDI和ATM的挑战。如今以太网是最流行的有线局域网技术

以太网成功的原因

①以太网是第一个广泛部署的高速局域网

②令牌环、FDDI和ATM比以太网更复杂，更昂贵

③改用其他网络技术可能是因为新技术由更高的数据速率，但是以太网总能更新具有相同或更高数据速率的版本

④由于以太网的流行，硬件发展成熟，价格便宜

以太网采用星形拓扑结构，用交换机代替原本中间的集线器

1. 以太网帧结构

 假设两台主机处于相同的以太局域网上，一台主机向另一台主机发送一个IP数据报。假设发送适配器A的MAC地址是AA-AA-AA-AA-AA-AA，接收适配器B的MAC地址BB-BB-BB-BB-BB-BB。发送适配器在一个以太网帧封装了一个IP数据报，并把该帧传递到物理层。接受适配器从物理层接收到该帧，提取出IP数据报，并将该数据报传递给网络层

·数据字段：承载IP数据报。以太网的最大传输单元（MTU）是1500字节。如果超过1500字节，主机将该数据报分片。数据字段的最小长度是46字节。如果IP数据报小于46字节，则必须填充到46字节。如果发生填充，则传递到网络层的数据就包括IP数据报和填充部分，网络层需要使用IP数据报首部中的长度字段来去除填充部分

·目的地址：包含目的适配器的MAC地址

·源地址：这个字段包含了传输该帧到局域网上的适配器的MAC地址

·类型字段：类型字段允许以太网复用多种网络层协议。一台给定的主机可以支持多种网络层协议，从而应对不同的协议。目的是为了把一层中的某协议与上一层的某协议结合起来

·CRC：循环冗余检测字段的目的是使得接收适配器检查帧中是否出现了差错

·前同步码：以太网帧以一个8字节的前同步码字段开始。该前同步码的前7字节的值都是10101010；最后一个字节是10101011。前同步码字段的前七个字节用于“唤醒”接受适配器，并且将他们的时钟与发送方的时钟同步。发送适配器根据以太局域网类型的不同，以不同的速率传输帧，但不一定严格的按照额定速率传输帧。相对于额定速率会有一些偏移

所有的以太网技术都向网络层提供无连接服务，不需要类似TCP的握手服务

以太网技术都向网络层提供不可靠服务，在链路层只有CRC校验。在链路层缺乏可靠的传输，意味着传递到网络层的数据报流可能出现间隙

如果由于丢弃了以太网帧而出现间隙，接收主机上的应用使用UDP就会看到数据中的间隙，使用TCP将不会确认包含在丢弃帧中的数据，从而使得发送主机重传

2. 以太网技术

上图所示的以太网协议名称。首字母缩写词的第一部分指该标准的速率：10、100、1000……。“BASE”指基带以太网，表示物理媒体仅承载以太网流量。最后一部分表示物理媒体本身，比如“T”代表双绞铜线

现今使用的以太网是基于交换机的星形拓扑，采用的是存储转发分组交换，是全双工的。这使得一台交换机和一个节点能够在同时向对方发送帧而没有干扰。这也就是说基于交换机的以太局域网中，不会产生碰撞，因此也就不需要使用MAC协议

6.4.3 链路层交换机

交换机自身对子网中的主机和路由器是透明的（transparent）；某主机/路由器向另一个主机/路由器寻址一个帧（而不是向交换机寻址该帧），顺利的将该帧发送进局域网。帧到达该交换机的任何输出接口之一的速率可能暂时会超过该接口的链路容量

1.交换机转发和过滤

过滤（filtering）是决定一个帧应该转发到某个接口或是将其丢弃的交换机功能

转发（forwarding）是决定一个帧应该被导向哪个接口，并将该帧移动到对应接口的交换机功能

 交换机的过滤和转发借助于交换机表（switch table）完成。该交换机包含某局域网上某些主机和路由器的但不必是全部的表项。交换机表中的一个表项包括：①一个MAC地址②通向该MAC地址的交换机接口③表项放置在表中的时间

假设目的地址为DD-DD-DD-DD-DD-DD的帧从交换机接口x到达。交换机用MAC地址DD-DD-DD-DD-DD-DD索引它的转发表。有以下三种可能情况 

·表中没有对于DD-DD-DD-DD-DD-DD的表项。在这种情况下，交换机向除了接口x外的所有接口前面的输出缓存转发该帧的副本。也就是说，如果没有目的地址的表项，则交换机广播该帧

·表中有一个表项将DD-DD-DD-DD-DD-DD与接口x联系起来。该帧从包括适配器DD-DD-DD-DD-DD-DD的局域网网段来到该交换机，无需将该帧转发到任何其他接口，交换机通过丢弃该帧执行过滤功能

·表中有一个表项将DD-DD-DD-DD-DD-DD与接口y≠x联系起来。该帧需要被转发到与接口y相连的局域网网段。交换机通过该帧放到接口y前面的输出缓存，完成转发功能

2.自学习

交换机的表是自动、动态和自治地建立的。不需要来自网络管理员或来自配置协议的任何干预。交换机是自学习（self - learning）的

1）交换机表初始为空

2）对于在每个接口收到的每个进入帧，该交换机在表中存储①在该帧源地址字段中的MAC地址②该帧到达的接口③当前时间。交换机通过这种方式在表中记录发送节点所在的局域网网段。如果在局域网上的每个主机最终都发送了一个帧，则每个主机最终都会被记录在交换机表中

3）如果一段时间后（老化期aging time），交换机没有接收到以该地址作为源地址的帧，将会在表中删除该地址。如果一个端主机被另一台端主机（不同的适配器）替代，那么最终原来端主机的MAC地址会从交换机表中清楚

以上图为例，假设交换机的老化期为60min，在9：32~10：32期间，源MAC地址为62-FE-F7-11-89-A3的帧并没有到达该交换机，那么在10：32时，交换机将会从表中删除该地址表项

交换机是即插即用设备，因此不需要网络管理员或用户的干预。只需要在安装交换机时，将局域网网段与交换机的接口相连。交换机的双工的，任何交换机接口能够同时发送和接收

3.链路层交换机的性质

交换机的优点

消除碰撞。在使用交换机构建的局域网中，没有因为碰撞而浪费的带宽。交换机缓存帧并且不会在网段上同时传输多余一个帧。交换机的最大聚合带宽是该交换机所有接口速率之和

异质的链路。交换机将链路彼此隔离，因此局域网中不同链路能够以不同的速率运行并且能够在不同的媒体上运行

管理。除了提供强化的安全性，交换机也易于进行网络管理。交换机可以检测到异常持续发送以太网帧的适配器，并在内部断开异常适配器

4.交换机和路由器比较

路由器是使用网络层地址转发分组的存储转发分组交换机。交换机也是一个存储转发分组交换机，与路由器不同的是，他用MAC地址转发分组。交换机是第二层的分组交换机，路由器是第三层的分组交换机

通常，几百台主机组成的小网络有几个局域网网段，因此交换机就足够，因为不要求IP地址的任何配置就能使流量局部化并增加总计吞吐量。在几千台主机组成的更大网络中，通常除了交换机还需要路由器。路由器提供了更加强大的流量隔离方式和对广播风暴的控制，并使得网络中的主机更加智能的路由

6.4.4 虚拟局域网

现代机构的局域网通常是配置为等级结构的，每个工作组都有自己的交换局域网，经过一个交换机等级结构与其他工作组的交换局域网互联。但存在三个缺点

缺乏流量隔离。尽管该等级结构把组流量局域化到一个单一交换机中，但广播流量仍然需要跨越整个机构网络。限制这些广播流量的范围将会改善局域网的性能，并且有助于安全或隐私目的。通过使用路由器替代中心交换机可以实现流量隔离

交换机的无效使用。如果一个机构有十个组而不是三个组，那么就需要十个第一级交换机。如果每个组中的人数都很少，那么可能单台交换机就足够每个人使用，但是单一的交换机不能实现流量隔离

管理用户。如果一个员工在不同组之间移动，那么就必须改变物理线路，从而将员工连接到不同的交换机上

现今通过支持虚拟局域网（Virtual Local Network，VLAN）的交换机来处理

VLAN（Virtual Local Area Network）即虚拟局域网，是将一个物理的LAN在逻辑上划分成多个广播域的通信技术。每个VLAN是一个广播域，VLAN内的主机间可以直接通信，而VLAN间则不能直接互通。这样，广播报文就被限制在一个VLAN内

在一个基于端口的VLAN中，交换机的端口由网络管理员划分为组。每个组构成一个VLAN，在每个VLAN中的端口形成一个广播域，即来自一个端口的广播流量仅能够到达该组中的其他端口

一种更具有扩展性互联VLAN交换机的办法称为VLAN干线连接（VLAN trunking）。如下图所示，每台交换机上的一个特殊端口被配置为干线端口，从而互联两台VLAN交换机。该干线端口属于所有的VLAN，发送到任何VLAN的帧通过干线链路转发到其他交换机

交换机如何判断干线上的某帧属于那个VLAN？

IEEE定义了一种扩展的以太网帧格式--802.1Q，用于跨越VLAN干线的帧。该帧由标准以太网帧与加进首部4字节VLAN标签（VLAN tag）组成，VLAN标签标记该帧所属的VLAN

VLAN标签在VLAN干线发送侧的交换机加进帧中，解析后并由在VLAN干线接收侧的交换机删除

VLAN标签自身由一个2字节的标签协议标识符（Tag Protocol Identifier，TPID）字段、一个2字节的标签控制信息字段和一个3比特优先权字段组成

虚拟局域网与子网

通过将IP地址的网络部分进一步划分为若干子网，可以解决IP地址空间利用率低和两级IP地址不够灵活的问题

与VLAN类似的是，子网也可以隔离主机间的通信。属于不同VLAN的主机之间不能直接通信，属于不同子网的主机之间也不能直接通信。但是二者并没有必然的对应关系

6.5 链路虚拟化：网络作为链路层

本节中考虑多协议标签交换（MPLS）网络。与电路交换的电话网不同，MPLS是一种分组交换的虚电路网络。有自己的分组格式和转发行为。MPLS可以作为IP设备提供互联服务的链路层技术

6.5.1 多协议标签交换

多协议标签交换（Multiprotocol Label Switching，MPLS）采用来自虚电路网络领域的关键概念：固定长度标签。目标是：对于基于固定长度标签和虚电路的技术，在不放弃基于目的地IP数据报转发的基础设施的前提下，在可能是通过选择性地标识数据报并允许路由器基于固定长度的标签（而不是基于目的地IP地址转发）转发数据报来强化功能

相对于传统的IP路由方式，MPLS提供了一种新的网络交换方式，它将IP地址映射为简短且长度固定、只具有本地意义的标签，以标签交换替代IP查表，从而显著提升转发效率。同时，MPLS的标签机制可以在IP网络中构筑一条逻辑上的隧道，而且MPLS兼容不同的网络层和链路层协议

MPLS首部增加在第二层（如以太网）首部和第三层（如IP）首部之间。MPLS首部中的字段是：标签、预留的3农业实验字段、1比特S字段、寿命字段

与传统的IP路由方式相比，一个MPLS加强的帧仅能在两个均为MPLS使能的路由器之间发送。一个MPLS使能的路由器通常为被称为标签交换路由器（label-switched router）。①它通过在转发表中查找MPLS标签，然后立即将数据报传递给适合的输出接口来转发MPLS帧。②当报文进入MPLS区域后，只需要在位于边缘的入、出节点解析IP报文头部，封装或者解封装标签。而在中间的所有节点上都无需解析IP报文首部，只需要进行标签交换，进一步减少转发报文的处理时间。因此MPLS使能的路由器不需要提取目的IP地址和在转发表中执行最长前缀匹配的查找 

下图中有六个路由器，其中R5，R6为普通的IP使能路由器。R1-R4为MPLS使能的路由器，它们各自的标签交换表如下。通过出入标签实现报文的路由 

对于上图中的外围设备（R5、R6、A、D），它们可以通过一个MPLS基础设施连接在一起，这与交换局域网与ATM网络能够将IP设备连接到一起的方式十分相似。并且与交换局域网或ATM网络相似，MPLS使能路由器在完成转发的工作时，并不直接接触分组的IP首部，只使用MPLS首部

在本书中并不学习MPLS的具体实现方式。关注的重点在于①MPLS基于标签执行交换，而不考虑分组的IP地址 ②MPLS使能具有新的流量管理功能，IP路由选择协议只能指定单一最小费用路径，而MPLS提供了沿着多条路由转发分组的能力③MPLS可以用于实现虚拟专用网（Virtual Private Network，VPN），使得用户利用VPN跨ISP访问资源

6.6 数据中心网络

每个数据中心都有自己的数据中心网络，这些数据中心网络将其内部主机彼此互联并与因特网中的数据中心互联

数据中心中的主机称为刀片（blade），一般是包括CPU、内存和磁盘存储的商用主机。主机被堆叠在机架上，每个机架一般堆放20~40台刀片。在每个机架顶部有一台交换机，这台交换机被称为机架顶部（Top of Rack，TOR）交换机，他们与机架上的主机互联，并于数据中心中的其他交换机互联

具体来说，机架上每台主机都有一块与TOR交换机连接的网卡，每台TOR交换机有额外的端口能够与其他TOR交换机连接

数据中心网络支持两种类型的流量：在外部客户与内部主机之间流动的流量、内部主机之间流动的流量

为了除了外部客户与内部主机之间的流量，数据中心网络包括一台或多台边界路由器，他们将数据中心网络与公共因特网相连。数据中心网络因此需要将所有机架彼此互联，并将机架与边界路由器连接

1. 负载均衡

一个云数据中心，为了支持来自外部客户的请求，每一个应用都与一个公开可见的IP地址关联，外部用户向该地址发送其请求并从该地址接收响应。在数据中心内部，外部请求先被定向到一个负载均衡器（load balancer），负载均衡器将请求分发到处理该应用的某一台主机上。当主机处理完该请求之后，向负载均衡器回送响应，再由负载均衡器中继发回给外部客户

负载均衡器的任务

①向主机分发请求，以主机当前的负载作为函数来在主机之间均衡负载

②负载均衡器不仅平衡主机间的工作负载，而且还提供类似NAT功能，将外部IP地址转换为内部适当主机的IP地址，然后将反方向流向客户的分组按照相反的转换进行处理。防止客户直接接触主机，从而具有隐藏网络内部结构和防止客户直接与主机交互等安全性益处

2. 等级体系结构

对于仅有数千台主机的小型数据中心：只需要一台边界路由器、一台负载均衡器和几十个机架组成，这些机架由单一以太网交换机进行互联

对于几万或几十万主机：数据中心通常由应用路由器和交换机等级结构（hierarchy of router and switch）。在该等级结构的顶端，边界路由器与接入路由器相连，每台接入路由器与一台第一层交换机相连，每台第一层交换机与多台第二层交换机以及一台负载均衡器相连。每台第二层交换机又通过机架的TOR交换机（第三层交换机）与多个机架相连。所有链路通常使用以太网作为链路层和物理层协议，并混合使用铜缆和光缆

这种等级结构很好的解决了扩展性问题，从图中可以看出每个接入路由器下的主机形成了单一子网，每个子网都可以划分为更小的VLAN子网

主机到主机容量受限问题

假设每台主机用1Gbps链路连接到它的TOR交换机，交换机之间的链路是10Gbps

假设上图中，机架1上10台主机向机架5上对应主机发送一条流；机架2向5发送总共10条流……依次类推。如果每一条流和其他流经同一条链路的流平均的共享链路容量，则经过10Gbps的A到B链路和10Gbps的B到C链路上的40条流中，每条流获得的速率为10Gbps/40=250Mbps，显著小于1Gbps的网络接口卡速率

如果主机间的流量需要穿过该等级结构的更高层，则该问题会更加严重。解决方式是部署更高速率的交换机和路由器，但这会增加数据中心的费用

 3. 数据中心网络的发展趋势

为了降低数据中心的费用，同时提高在时延和吞吐量上的性能，克服传统等级设计缺陷的新型互联体系结构和网络协议，各大厂商提供了新的方案

全连接拓扑（fully connected topology）：在这种设计中，每台第一层交换机都与所有第二层交换机相连。因此①主机到主机的流量绝不会超过该交换机层次②对于n台第一层交换机，在任意两台二层交换机间有n条不相交的路径。

考虑上面所说的40条流的问题。如上图第1台第二层交换机和第2台第二层交换机间存在4条不相交的路径，可以一起为前两台第二层交换机之间提供总和为40Gbps的聚合容量。这样减轻了主机到主机的容量限制，同时创建了更加灵活的计算和服务环境。这种环境下，任何未连接到同一台交换机的两个机架之间的通信在逻辑上是等价的，不论其在数据中心的位置如何

模块化数据中心（Modular Data Center，MDC）：在一个MDC中，在一个船运集装箱内构建一个迷你数据中心，并将该集装箱运送到数据中心的位置。每个集装箱中有数千个主机，放在数十个机架上。在数据中心位置，多个集装箱彼此互联，同时也和因特网连接。集装箱难以检修，因此会产生性能下降，下降一定程度之后会直接换新

MDC的关键是每个集装箱中的内部网路和互联每个集装箱的核心网络。内部网络可以用吉比特以太网交换机创建全连接的网络，但是核心网络需要互联大量集装箱，并且为工作负载提供跨多个集装箱的主机到主机间的高带宽