计算机网络原理：Internet路由选择协议

在互联网的世界里，数据就像快递包裹一样需要从一个地方送到另一个地方。路由算法和路由协议就像是快递员的导航系统和交通规则，帮助数据找到最快的路，确保它们能够准确无误地到达目的地。没有它们，数据就会迷失方向，网络也就无法正常工作。

一、数据链路层服务

从数据链路层来看，无论是主机还是路由器等网络设备，都可以统称为结点，因为它们通常都是一条数据链路的端点。数据链路层传输的数据单元称为帧。数据链路层通常提供的以下几点服务：

组帧。数据链路层将要传输的数据封装成帧，称为组帧或成帧。

在组帧过程中，会在数据（例如网络层数据报）的基础上增加帧头（或称帧首）和帧尾。帧头中通常包含发送结点和接收结点的地址等信息，帧尾通常包含用于差错检测的差错编码。

组帧过程增加的帧头和帧尾中还有一部分信息，用于帧定界，即确保接收结点从物理层收到的比特流中，能够依据帧头和帧尾中的定界字符或定界比特串，成功识别一个帧的开始和结束。例如，有的数据链路层协议组帧时，帧头的第一个字节和帧尾的最后一个字节都是01111110，以此来作为帧的定界，
链路接入。物理链路可以分为点对点链路和广播链路两大类。

在点对点链路中，发送结点和接收结点独占通信链路，只要链路处于空闲状态，随时可以使用链路发送和接收帧，因此链路的接入控制很简单（甚至可以说无须专门控制）。

在广播链路中，通信链路被多个结点共享，任意两个结点同时通过链路发送帧，都会彼此干扰，导致帧传输的失败。因此，对于广播链路，各个结点必须运行媒介访问控制(Medium Access Control, MAC)协议，来协调各结点使用共享的物理传输媒介，实现帧的成功传输。
可靠交付。数据链路层协议也可以提供可靠交付服务，即在相邻结点间经数据链路实现数据报的可靠传输。事实上，支持可靠数据传输的数据链路层协议，多应用于高出错率的链路中，例如无线链路。对于低出错率的链路，例如，光纤、双绞线链路等，实施可靠传输似乎没有太大必要，因此，有线链路的数据链路层协议通常不提供可靠传输服务。
差错控制。帧在物理媒介上的传播过程中，可能会产生差错（比特翻转）。在一段时间内，传输过程中出现差错的比特数，占所传输比特总数的比率，称为误比特率。误比特率与线路的信噪比有很大的关系。为了保证帧传输的可靠性，或者为了确保出现差错的帧不再被处理和继续传输，数据链路层协议通常都采用不同的差错控制措施，或者通过确认重传纠正差错，或者直接丢弃差错帧。

二、差错控制

差错控制是指通过差错编码技术，实现对信息传输差错的检测，并基于某种机制进行差错纠正和处理，是计算机网络中实现可靠传输的重要技术手段。

信号在信道传输过程中，会受到各种噪声的干扰，从而导致传输差错。噪声大致可以分为随机噪声和冲击噪声两大类。

随机噪声包括热噪声、传输介质引起的噪声等，具有典型的随机特征。随机噪声引起的传输差错称为随机差错或独立差错，具有独立性、稀疏性和非相关性等特点，对于二进制信息传输，通常呈现为随机的比特差错。
冲击噪声是指突然发生的噪声，如雷击、电机启停等，具有很强的突发性，并且容易造成一段时间的传输差错。冲击噪声引起的差错称为突发差错，通常是连续或成片的信息差错，差错之间具有相关性，差错通常集中发生在某段信息。突发错误发生的第一位错误与最后一位错误之间的长度称为突发长度。

2.1、差错控制的基本方式

不同网络对数据传输速率、实时性、可靠性、信道特性等需求不尽相同，通常对于差错的处理可以选择不同的差错控制方式。典型的差错控制方式包括以下四种：

检错丢弃。直接丢弃错误数据。适用于允许一定比例的差错存在，对实时性要求较高的系统。比如，多媒体应用。
检错重发。发送端对待发送数据进行差错编码，然后传输编码后的数据，接收端利用差错编码检测数据是否出错。对于出错的数据，接收端请求发送端重发数据进行纠正，直到接收端收到正确数据为止。该方式广泛应用于计算机网络中。
前向纠错（Forward Error Correction，FEC）。该机制基于纠错编码。此类编码不仅可以检测数据传输过程中是否发生了错误，还可以定位错误位置并直接加以纠正。在该机制中，发送端对数据进行纠错编码，然后发送包含纠错编码信息的帧，接收端利用纠错编码进行差错检测，对于错误的帧直接进行纠错。适用于单工链路或者对实时性要求比较高的应用。
反馈校验。接收端将收到的数据原封不动发回发送端，发送端通过比对接收端反馈的数据与发送的数据，确认接收端是否正确无误接收了已发送的数据。如果发送端发现有不同，则认为接收端没有正确接收到发送的数据，则立即重发数据，直到收到接收端反馈的数据与已发数据一致为止。该方式的优点是原理简单、易于实现、无须差错编码；缺点是需要相同传输能力的反向信道，传输效率低、实时性差。

2.2、差错编码的基本原理

香农信道编码定理指出：对于一个给定的有干扰信道，只要发送端以低于信道容量C的数据速率R发送信息，则一定存在一种编码方法，使得编码错误概率P随着码长n的增加而按指数下降至任意小的值。这也就是说，理论上可以通过编码使得数据传输过程不发生错误或者将错误概率控制在很小的数值之下。香农信道编码定理论证了这一编码的存在，但并未说明如何找到这样的编码或者说如何设计这样的编码。

在实际的网络系统中，如果需要提高数据传输的可靠性，通常都是采用差错编码来实现。差错编码的基本原理是：在待传输（或待保护）数据基础上，附加一定的冗余信息，该冗余信息同原始数据建立某种关联关系，将数据以及附加的冗余信息一同发送到接收端，接收端可以检测冗余信息所表现的与数据之间的关联关系是否存在，如果存在则没有错误，否则就有错误。

例如，发送端向接收端发送2位数据，如果不进行差错编码，则接收端收到2位数据可能是00、01、10或11，这4个码字均是发送端可能发送的数据，因此接收端无法判断数据传输过程中是否发生错误。如果对2位的数据进差错编码，比如增加2位冗余信息，该冗余信息是对数据的复制，则经过差错编码后的4个码字分别为 0000、0101、1010、1111。这样，编码后的码字如果在传输过程中发生1位差错，则接收端一定可以判断出来。比如，如果接收端收到的码字为1011，由于数据10与冗余信息 11不满足复制关系，因此接收端可以断定，数据再传输过程中发生了错误。但是，至于是哪位（或哪些位）发生了错误，还无法判断，因为该差错编码无法实现纠错。

如下图，是差错编码进行差错检测的一般性原理的过程示意图。

2.3、差错编码的检错与纠错能力

不同差错编码的检错或纠错能力是不同的。差错编码的检错或纠错能力与编码集的汉明距离有关。

两个等长码字之间，对应位不同的位数，称为两个码字的汉明距离，记为 $d_c$ 。例如，码字01100101与码字10011101之间，有5位是不同的，因此它们的汉明距离 $d_c=5$ 。类似地，可以将一个编码集的汉明距离，定为该编码集中任意两个码字之间汉明距离的最小值，记为 $d_s$ 。例如，在编码集{10000111,10010110, 10100101, 10110100)中，任意两个码字之间汉明距离的最小值为2，即 $d_s=2$ 。

差错编码的所有有效码字的集合称为该差错编码的编码集。差错编码的检错或纠错能力跟该差错编码的编码集的汉明距离有关。

1）对于检错编码，如果编码集的汉明距离 $d_s=r+1$ ，则该差错编码可以检测r位的差错。

例如，如果差错编码采取一次重复码，即冗余信息是数据的一次复制（重复），则编码集的汉明距离 $d_s=2$ 。因此可以检测1位差错。

如果数据为2位数据，则采用一次重复差错编码的编码集为{0000, 0101, 1010, 1111} ，显然该编码集的汉明距离 $d_s=2$ ，如果发生1位差错，可以100％被检测出来。

2）对于纠错编码，如果编码集的汉明距离 $d_s=2r+1$ ，则该差错编码可以纠正r位的差错。

例如，如果差错编码采取二次重复码，即冗余信息是数据的两次复制（重复），则编码集的汉明距离 $d_s=3$ ，因此可以纠正1位差错。

如果数据为2位数据，则采用二次重复差错编码的编码集为{000000, 010101, 101010, 111111}，显然该编码集的汉明距离 $d_s=3$ ，如果发生1位差错，则错码（即无效码字）距离发生错误的有效码字的汉明距离最近，可以恢复为该有效码字。例如，如果接收端收到的码字为100010，则码字100010 与码字000000 之间的汉明距离为2，与010101 之间的汉明距离为5，与101010 之间的汉明距离为1，与111111 之间的汉明距离为4。显然，无效码字 100010与有效码字 101010 之间的汉明距离最小，因此将100010 恢复为101010。事实上，因为有效码字 101010 错成无效码字100010 的概率最大所以恢复为101010。

差错编码的检错与纠错能力可以利用下图直观解释。

对于编码集汉明距离 $d_s=r+1$ 的检错编码，任意两个码字 $C_i$ 和 $C_j$ 之间的汉明距离 $d_c \ge r+1$ 。当 $C_i$ 发生r位错，错成码字 C’时，C’和 $C_j$ 之间的汉明距离 $d_c \ge1$ ，即C’一定是一个无效码字，所以一定会被检测出来。

类似地，对于编码集汉明距离 $d_s=2r+1$ 的纠错编码，任意两个码字 $C_i$ 和 $C_j$ 之间的汉明距离 $d_c \ge 2r+1$ 。当 $C_i$ 发生r位错，错成无效码字C’时（此时一定能检测出差错），C’和 $C_j$ 之间汉明距离 $d_c \ge r+1$ ，大于C’和 $C_i$ 之间的汉明距离r。根据概率最大化原则，C’可以纠正为 $C_i$ , 得到正确恢复，而没有错误地恢复为其他码字。

2.4、典型的差错编码

差错编码基于按位异或（XOR）运算。该操作等价于模2算术操作，用符号“ $\oplus$ ”表示，即参与运算的两个位值，如果两个位值相同，则结果为0，否则为1。

典型的差错编码有：奇偶校验码、汉明码以及循环冗余码(CRC)。

2.4.1、奇偶校验码

奇偶校验码是一种最简单的检错码，包括奇校验码和偶校验码。奇偶校验码利用1位冗余信息实现差错检测，可以表示为(n, n-1)。

2.4.1.1、奇校验码

在奇校验码编码过程中，1位冗余位的取值为"0"或"1"，使得编码后的码字中"1"的个数为奇数，即满足下式

a_{n-1} \oplus a_{n-2} \oplus ··· \oplus a_1 \oplus a_0 = 1

式中， $a_0$ 为冗余位； $a_1···a_{n-1}$ 为数据位。比如，对于数据10110111，采用奇校验码编码后的码字为101101111。

2.4.1.2、偶校验码

在偶校验码编码过程中，1 位冗余位的取值为"0"或"1"，使得编码后的码字中"1"的个数为偶数，即满足下式

a_{n-1} \oplus a_{n-2} \oplus ··· \oplus a_1 \oplus a_0 = 0

式中， $a_0$ 为冗余位； $a_1···a_{n-1}$ 为数据位。比如，对于数据10110111，采用奇校验码编码后的码字为101101110。

2.4.1.3、小结

对于采用奇偶校验的码字，如果在传输过程中有奇数位（包括数据位和冗余位）发生错误，那么奇偶校验码可以检测出错误的发生，但是如果有偶数位发生错误，则无法被检测出来。因此，奇偶检验码可以实现 50％的检错率，当然漏检率也高达50%。

奇偶校验位码是一种检错码，无法进行错误纠正。奇偶校验码仅仅需要简单的异或操作即可完成编码／解码，因此奇偶校验码的优点是编码简单、编码效率高，是开销最小的检错编码，但缺点是检错率不高。由于奇偶校验码简单，常应用于低速串行通信链路中。通常编码格式是7 位数据位、1位校验位、1~2位停止位，或者8 位数据加上1个校验位，可以传输任意的8位数据或者ASCII 字符。

2.4.2、汉明码

1950年，理查德·卫斯里·汉明在美国贝尔实验室的工作中，为了解决读卡机错误检测与纠正问题，设计了著名的汉明码。汉明码(Hamming Code)是典型的线性分组码，可以实现单个比特差错纠正，在数据通信以及数据存储系统中得到了广泛应用。当信息位足够长时，它的编码效率很高。

一串数据位为k=n-1位的比特流 $a_{n-1}a_{n-2}···a_1$ ，加上偶校验位 $a_0$ ，构成一个n位的码字 $a_{n-1}a_{n-2}···a_1a_0$ 。接收方在校验时，可按如下关系式来计算

S=a_{n-1} \oplus a_{n-2} \oplus ··· \oplus a_1 \oplus a_0

若S=0，则无错；若S=1, 则有错。上式可称为监督关系式，S称为校正因子。在这种情况下，只有一个监督关系式，一个校正因子，其取值只有两种(0或1)，分别代表了无错和有错两种情况，但不能指出差错所在的位置。

不难推测，若增加冗余位，也就相应地增加了监督关系式和校正因子，就能区分更多的情况。例如，若有两个校正因子，则其取值有4种可能：00、01、10或11，就能区分4种不同的情况。若其中一种表示无错，另外3种不但可以用来指出有错，还可用来区分错误的情况。比如，指出是哪一位出错，就可能使得这种编码实现纠错。

一般来说，数据位为k位，增加r位冗余位，构成n=k+r 位码字。若希望用r个监督关系式产生的r个校正因子来区分无错和在码字中n个不同位置的一位错，则要求

2^r \ge n+1

或

2^r \ge k+r+1

以k＝4为例来说明，要满足上述不等式，则 $r\ge3$ 。现取r=3，则n=k+r=7。这也就是说，在4 位数据位 $a_6a_5a_4a_3$ 的后面，加上3位冗余位 $a_2a_1a_0$ ，构成7位码字 $a_6a_5a_4a_3a_2a_1a_0$ 。其中 $a_2$ 、 $a_1$ 和 $a_0$ 分别由4位数据位中的某几位异或运算得到。在校验时， $a_2$ 、 $a_1$ 和 $a_0$ 分别与这些位进行异或运算，构成3个不同的监督关系式。

无错时，这3个关系式的值 $S_2$ 、 $S_1$ 和 $S_0$ 全为0；若 $a_2$ 错，则 $S_2=1$ ，而 $S_1=S_0=0$ ；若 $a_1$ 错，则 $S_1=1$ ，而 $S_2=S_0=0$ ；若 $a_0$ 错，则 $S_0=1$ ，而 $S_2=S_1=0$ 。 $S_2S_1S_0$ 这3个校正因子和其他4种编码的值可用来区分 $a_3、a_4、a_5或a_6$ 哪一位出错。该对应关系可按下表所来执行（也可以规定成另外的对应关系）。

$S_2S_1S_0$	000	001	010	100	011	101	110	111
错码位置	无措	a0	a1	a2	a3	a4	a5	a6

由上表可见， $a_2、a_4、a_5或a_6$ 中的一位出错都应使 $S_2=1$ ，由此可以得到如下监督关系式

S_2=a_2 \oplus a_4 \oplus a_5 \oplus a_6

同理还有

S_1=a_1 \oplus a_3 \oplus a_5 \oplus a_6

S_0=a_0 \oplus a_3 \oplus a_4 \oplus a_6

发送端在编码时，信息位 $a_3、a_4、a_5或a_6$ 的值取决于输入信号，是随机的。冗余位 $a_2$ 、 $a_1$ 和 $a_0$ 的值应根据信息位的取值按监督关系式来决定，使上述3个式子中的 $S_2$ 、 $S_1$ 和 $S0$ 的取值为0，即

a_2 \oplus a_4 \oplus a_5 \oplus a_6 = 0

a_1 \oplus a_3 \oplus a_5 \oplus a_6 = 0

a_0 \oplus a_3 \oplus a_4 \oplus a_6 = 0

由此可求得

a_2 = a_4 \oplus a_5 \oplus a_6

a_1 = a_3 \oplus a_5 \oplus a_6

a_0 = a_3 \oplus a_4 \oplus a_6

已知信息位后，按上式即可算出各冗余位。对于各种信息位算出的汉明码冗余位如下所示。

信息位	冗余位
$a_6a_5a_4a_3$	$a_2a_1a_0$
0000	000
0001	011
…	…
1111	111

接收方在收到每个码字后，按监督关系式算出 $S_2$ 、 $S_1$ 和 $S_0$ ，若全为"0"则认为无错。若不全为"0"，在一位错的情况下，可查上表来判定是哪一位出错，从而纠正之。例如，码字0010101，在传输中一位出错，接收方收到的为 0011101，代入监督关系式可算得 $S_2=0$ 、 $S_1=1$ 和 $S_0=1$ ，由上表可查得 $S_2S_1S_0=011$ 对应于 $a_3$ 出错，因而可将0011101纠正为0010101。

上述汉明码的编码效率为4/7。若k=7，按 $2^r \ge k+r+1$ 可算得r至少为4，此时编码效率为7/11。信息位长度越长编码效率越高。

汉明码只能纠正一位错，若用来纠正传输过程中出现的突发性差错时，可采用下述方法：将连续 P个码字排成一个矩阵，每行一个码字。如果发生突发长度小于等于P的突发错误，那么在P个码字中最多每个码字有一位有差错，正好由汉明码纠正。

2.4.3、循环冗余码

在计算机网络中，数据链路层广泛使用的差错编码是循环冗余检测（Cyclic Redundancy Check, CRC）编码，简称循环冗余码，或称CRC码。CRC编码是一个重要的线性分组码，也称为多项式编码（Polynomial Code）。

CRC编码的基本思想是：将二进制位串看成是系数为0或1的多项式的系数。一个k位二进制数据可以看作是一个k-1 次多项式的系数列表，该多项式共有k项（从 $x^{k-1}$ 到 $x^0$ ）。高次（最左边）位是 $x^{k-1}$ 项的系数，接下来的位是 $x^{k-2}$ 项的系数，以此类推。例如，100101有6位，因此代表了一个有6项的多项式，其系数分别是1、0、0、1、0和1，即 $1x^5+0x^4+0x^3+1x^2+0x^1+1x^0=x^5+x^2+1$

在使用CRC编码时，发送方和接收方必须预先商定一个生成多项式G(x)。生成多项式的最高位和最低位系数必须是1。假设一帧数据有m位，对应的多项式为M(x)，为了计算它的CRC编码，该帧必须比生成多项式G(x)长。基本思想是在帧的尾部附加校验和，使得附加校验和之后的帧，所对应的多项式能够被生成多项式G(x)除尽。当接收方收到了经过编码的数据时，用生成多项式G(x)系数对应的位串去除它，如果余数为0，则表明传输过程中没有错误，否则有错。

如果假设生成多项式G(x)的阶为r（即对应的位串为r+1位），则CRC编码过程如下。

在帧的低位端加上r个0位，使该帧扩展为m+r位（相当于左移r位），对应的多项式为 $x^rM(x)$ 。
用G(x)系数对应的位串，去除（模2除法） $x^rM(x)$ 系数对应的位串，求得r位余数R。
用 $x^rM(x)$ 系数对应的位串，减（模2减法）去余数R，结果就是完成CRC编码的帧。

接下来，我们来看一个具体的例子。假设CRC编码采用的生成多项式为 $G(x)=x^3+x^2+1$ ，求位串101001的CRC编码。

因为生成多项式 $G(x)=x^3+x^2+1$ 对应的比特位串是1101，有4位，因此在待编码位串101001后添加3个零，得到101001000。然后，按如下图求得余数R。最后，得到的CRC编码结果为101001001。

CRC编码具有优良的性能，很适合用于差错检测。一方面，CRC编码具有很强的检错能力。另一方面，CRC的编码、解码实现简单，只需通过简单的移位与异或运算即可实现。另外，CRC编码效率高，CRC编码附加的冗余校验和®的长度，只取决于生成多项式G(x)，与数据位数无关，当数据远大于R的位数时， CRC编码的开销就很小。因此，CRC 在计算机网络的数据链路层协议中得到了广泛应用，例如以太网、IEEE802.11无线局域网和PPP协议等。

三、多路访问控制协议

数据链路层使用的信道主要有两种类型：点对点信道和广播信道。

点对点信道使用一对一的通信方式，信道被通信双方独享。广播信道使用一对多的广播通信方式，广播信道上连接的结点很多，信道被所有节点共享，必须使用多路访问控制（Multiple Access Control，MAC）协议来协调结点的数据发送。

随着网络技术的发展，有很多MAC协议被提出。概括起来，主要可以分为3种类型的MAC协议：信道划分MAC协议、随机访问MAC协议和受控接入MAC协议。

3.1、信道划分MAC协议

MAC 协议的根本任务是解决信道共享问题。

多路复用技术是实现物理信道共享的经典技术，其基本思想是：将信道资源按某种方式划分后，分配给不同的结点，各结点通信时只使用其分配到的资源，从而实现信道共享，并避免了多结点通信时的相互干扰。这种采用多路复用技术实现信道共享的MAC协议，称为信道划分MAC协议。

多路复用是指在物理线路的传输能力远超过单一信道所需的传输能力时，可以将多条信道复合在一条物理线路上的技术。在通信网络中，被广泛使用。多路复用主要包括频分多路复用(Frequency Division Multiplexing, FDM)、时分多路用(Time Division Multiplexing, TDM)、波分多路复用(Wave Division Multiplexing , WDM)和码分多路(Coe Division Multiplexing, CDM)。

采用上述几种多路复用技术的MAC协议分别称为 FDMA、TDMA、WDMA和CDMA。下面分别简要介绍这几类多路复用技术。

3.1.1、频分多路复用（FDM）

频分多路复用（FDM）简称频分复用，采用频域划分制，即在频域内将信道带宽划分为多个子信道，并利用载波调制技术，将原始信号调制到对应某个子信道的载波信号上，使得同时传输的多路信号在整个物理信道带宽允许的范围内频谱不重叠，从而共用一个信道。

3.1.2、时分多路复用（TDM）

时分多路复用（TDM）简称时分复用，采用时域划分制，即将通信信道在时域内划分为多个等长的时隙，每路信号占用不同的时隙，在时域上互不重叠，使多路信号合用单一的通信信道，从而实现信道共享。

时分多路复用可分为同步时分多路复用（STDM）和异步时分多路复用（ATDM）。同步时分多路复用是按固定的顺序把时隙分配给各路信号。异步时分多路复用，也叫做统计时分多路复用，它是为数据量大的用户分配较多的时隙，数据量小的用户分配相对较少的时隙，没有数据的用户不分配时隙。

3.1.3、波分多路复用（WDM）

波分多路复用（WDM）简称波分复用，其实质是波的频分多路复用，即在一根光纤中，传输多路不同波长的光信号。多个波长不同的光信号，在同一个信道中互不干扰、同时传输，从而实现信道共享。

3.1.4、码分多路复用（CDM）

码分多路复用（CDM）简称码分复用，通过利用更长的相互正交的码组分别编码各路原始信息的每个码元（比如1位），使得编码后的信号在同一信道中混合传输，接收端利用码组的正交特性分离各路信号，从而实现信道共享。

3.2、随机访问MAC协议

随机访问MAC协议是指所有用户都可以根据自己的意愿随机地向信道发送信息。如果一个用户在发送信息期间没有其他用户发送信息，则该用户发送成功。如果有两个或两个以上的用户同时向信道发送信息，则产生冲突或碰撞（collision），导致用户发送失败，此时每个用户随机退让一段时间后，再次尝试，直至成功。

随机访问实际上就是竞争接入。竞争胜利者可以暂时占用共享信道发送信息，竞争失败者随机等待一段时间，再次竞争，直至竞争成功。随机访问协议的特点是，站点可随时发送数据，争用信道，容易发生冲突，需要消解冲突的机制，但能灵活适应站点数目及其通信量的变化。

典型的随机访问协议有ALOHA协议、载波监听多路访问（CSMA）协议以及带冲突检测的载波监听多路访问（CSMA/CD）协议等。

3.2.1、ALOHA协议

ALOHA协议是最早、最基本的无线数据通信协议。

ALOHA系统的最初设计是实现分散在夏威夷群岛的通信站点（计算机）与中心计算机之间的一点对多点的数据通信。

ALOHA系统的通信站点随机接入共享信道（天空），利用相同载波频率，通过分组无线电系统广播数据帧。任意两个或两个以上的站点，以相同的频率同时广播帧，都将使信号遭到破坏，导致数据传输失败。ALOHA协议就是在该系统中，用于解决无线共享信道的共享接入，是一种典型的随机多路访问控制协议。

ALOHA协议分为纯ALOHA和时隙ALOHA两种。

纯ALOHA协议的工作原理非常简单，任何一个站点有数据要发送时可直接发送至信道。发送站在发出数据后需要对信道侦听一段时间。通常这个时间是电波传到最远端的站点再返回本站点所需的时间。如果在这段侦听时间里收到接收站发送的应答信号，说明发送成功。否则说明数据帧遭到破坏（发生冲突），则等待一个随机时间后再进行重发，如果再次冲突，继续等待一个随机时间，直到重发成功为止。
时隙ALOHA的基本思想是，把信道时间分成离散的时隙（Slot），每个时隙是发送一帧所需的发送时间，每个通信站只能在每个时隙开始时刻发送帧，如果在一个时隙内发送帧出现冲突，以概率P在下一个时隙重发该帧，以概率1-P不发该帧（等待下一个时隙），直到发送成功。显然，P不能为1，否则协议会死锁。时隙ALOHA协议需要所有通信站在时间上同步。

尽管时隙ALOHA协议，通过同步各个通信站发送时间的方式，相对纯ALOHA协议提高了信道的利用率，但是最高36.8％的利用率仍不能今人满意。在此基础上，人们分析总结了ALOHA协议的一个根本缺点：发送之前无论信道是否空闲都进行发送，这会大大增加冲突的可能性。在发送帧之前，若能先判断一下信道是否空闲，如果空闲则发送帧，否则推迟发送，这样，冲突的可能性便会减少。基于这一思想，提出了载波监听多路访问协议(Carrier Sense Multiple Access, CSMA)。

3.2.2、CSMA协议

CSMA的特点是通过硬件装置，即载波监听装置，使通信站在发送数据之前，监听信道上其他站点是否在发送数据，如果在发送，则暂时不发送，从而减少了发生冲突的可能，提高了系统的吞吐量。有时候又称CSMA的工作方式为“先听后说”。

根据监听策略的不同，CSMA可细分为3种不同类型。

非坚持CSMA。其基本原理是：若通信站有数据发送，先侦听信道；若发现信道空闲，则立即发送数据；若发现信道忙，则等待一个随机时间，然后重新开始发送过程若发送数据时产生冲突，则等待一个随机时间，然后重新开始发送过程。该协议的优点是减少了冲突概率，缺点是增加了信道空闲时间，增大了数据发送延迟。
1-坚持CSMA。其基本原理是：若通信站有数据发送，先侦听信道；若发现信道空闲，则立即发送数据；若发现信道忙，则继续侦听信道，直至发现信道空闲后，立即发送数据。若发送数据时产生冲突，则等待一个随机时间，然后重新开始发送过程。该协议的优点是减少了信道空闲时间，缺点是增加了发送冲突概率（与信号传播延迟关系很大。传播延迟越大，发生冲突的概率就越大，协议性能就越差）。
P-坚持CSMA。其基本原理是：若通信站有数据发送，先侦听信道；若发现信道空闲，则以概率P在最近时隙开始时刻发送数据，以概率1-P延迟至下一个时隙重新开始发送过程；若发现信道忙，则等待下一个时隙，重新开始发送过程；若发送数据时产生冲突，则等待一个随机时间，然后重新开始发送过程。该协议适用于时隙信道（即同步划分时隙）

因为信号传播延迟，CSMA 即使在发送前进行监听，也会在发送数据时产生冲突，当两个帧发生冲突时，不仅导致两个数据帧都被破坏，也会使得信道无法被其他站所使用，因此，在冲突发生时，继续传输数据帧会造成信道的很大浪费。最好的办法就是一旦发现有突发生，所有通信站都立即停止继续发送数据。这就需要通信站在发送数据的同时，还要监听信道，这就是 CSMA/CD 协议，其中 CD表示冲突检测(Collision Detection)。

3.2.3、CSMA/CD协议

CSMA/CD协议可理解为“先听后说，边说边听”。其基本原理是，通信站使用CSMA协议进行数据发送，发送数据的同时监听信道；在发送数据期间如果检测到碰撞，立即终止发送，并发出一个冲突强化信号，使所有通信站都知道冲突的发生；然后等待一个随机时间，重新开始发送过程。

CSMA/CD的工作状态可分为传输周期、竞争周期和空闲周期，即信道有3种状态：

传输状态：一个通信站使用信道，其他站禁止使用。
竞争状态：所有通信站都有权尝试对信道的使用权。
空闲状态：没有通信站使用信道。

CSMA/CD仍然会存在冲突，主要原因是信号传播时延。一个通信站发出的信号，需要经过一定的延迟才能到达其他站，而在信号到达其他站之前，如果某通信站此时也有数据要发送，那么侦听信道的结果仍会是“空闲”，于是发送数据，冲突便发生了。

CSMA/CD的性能优于普通的CSMA协议，以太网的MAC协议就是CSMA/CD。

3.3、受控接入MAC协议

受控接入的特点是各用户不能随意接入信道而必须服从一定的控制，受控接入可分为集中式控制和分散式控制。

3.3.1、集中式控制

在采用集中式控制接入方式的系统中，有一个主机负责调度其他通信站接入信道，从而避免冲突。主要方法是轮询技术，其可分为论叫轮询和传递轮询。

3.3.2、分散式控制

典型的分散式控制方法是令牌技术。令牌（Token）是一种特殊的帧，代表通信站对信道的使用许可权，信道空闲时一直在信道上传输，一个通信站如果想发送数据就必须先获得令牌，然后在一定时间内发送数据，在发送完数据后重新产生令牌并发送到信道上，以便其他通信站使用信道。

四、局域网

局域网(LAN)是局部区域网络，其特点是覆盖面积较小，网络传输速率高，传输误码率低。

局域网拓扑类型主要包括星形网络、总线型网络、环形网络等，目前比较多见的局域网拓扑是星形网络以及以星形网络为基础的树形网络拓扑，例如最常见的以网多数情况下都是这类网络拓扑结构。

为了使数据链路层能更好地适应多种局域网标准，IEEE802委员会将局域网的数据链路层拆分为两个子层：逻辑链路控制(LLC)子层（即 IEEE 802.2 标准）和介质访问控制MAC子层。

与介质访问控制有关的内容都放在MAC子层，而LLC子层则与传输媒介无关，它的工作是面向网络层，隐藏802系列协议之间的差异，即不管采用何种协议的局域网对LLC子层来说都是透明的。由于TCP/IP体系结构的网络（如Internet)，经常使用的局域网是以太网(Ethernet)，因此IEEE802委员会制定的逻辑链路控制子层LLC的作用已经不大了，基本名存实亡。事实上，很多厂商生产的网络适配器上就仅装有MAC协议而没有LLC协议。

4.1、数据链路层寻址与ARP

数据链路层的帧，需要携带发送结点的数据链路层地址，以及接收结点的数据链路层地址，以标识帧的发送方与接收方。尤其是在广播链路中，帧中的这两个地址必不可少，结点需要根据帧的地址判断该帧是否是发送给自己的。

4.1.1、MAC地址

事实上，并不是主机或路由器具有链路层地址，而是它们的适配器（即网络接口卡）具有链路层地址，或称为MAC地址、物理地址、局域网地址等，用来标识局域网中的结点或网络接口。

适配器的MAC地址具有“扁平”结构，具有唯一性。网络层IP地址，则具有层次结构，随着主机的迁移而发生相应的变化，因为当主机连接到不同IP子网中时，主机的IP地址需要描述对于不同子网的归属关系，IP地址类似于邮政地址。

当某适配器要向某目的适配器发送一个帧时，发送适配器将目的适配器的MAC地址设置为该帧的目的MAC地址，并将该帧发送到局域网上。当适配器接收到一个帧时，检查该帧中的目的MAC地址是否与它自己的MAC地址匹配，如果匹配，则提取出封装的数据报，并将该数据报沿协议栈向上层协议提交；如果不匹配，则丢弃该帧。

4.1.2、地址解析协议

地址解析协议(ARP)用于根据本网内目的主机或默认网关的IP地址获取其MAC地址。ARP的基本思想是：在每一台主机中设置专用内存区域，称为ARP高速缓存（也称为ARP 表），存储该主机所在局域网中其他主机和路由器（即默认网关）的IP地址与MAC地址的映射关系，并且这个映射表要经常更新。ARP通过广播ARP查询报文，来询问某目的IP地址对应的MAC地址，即已知本网内某主机的IP地址，就可以查询得到其MAC地址。

关于ARP有两点需要注意：

ARP查询分组是通过一个广播帧发送的，而ARP响应分组是通过以个标准的单播帧发送的；
ARP是即插即用的，即一个ARP表是自动建立的，不需要系统管理员来配置。

4.2、以太网

冲突域是指在一个局域网内，如果任意两个结点同时向物理介质中发送信号（数据），这两路信号一定会在物理介质中相互叠加或干扰，从而导致数据发送失败，那么，这两个结点位于同一个冲突域。

广播域是指任一结点如果发送链路层广播帧的话，接收该广播帧的所有结点与发送结点同属于一个广播域。

4.2.1、以太网帧结构

以太网采用的是CSMA/CD协议，利用曼彻斯特编码发送，使用截断二进制指数后退算法来确定碰撞后重传的时机。以太网帧结构如下图所示。

   6字节     6字节  2字节  46~1500字节  4字节
-------------------------------------------
| 目的地址 | 源地址 | 类型 |    数据    | CRC |
-------------------------------------------

帧结构中包含两个地址：一个是目的地址，另一个是源地址，均为48位物理地址即MAC地址。

2字节类型字段用于标识上层协议，即标识帧中封装的数据是上层什么协议的分组。比如0x0800，表示该以太网帧封装的数据字段是一个IP数据报。

CRC即循环冗余校验，长度为4字节。该字段的目的是使得接收方适配器检测帧中是否出现差错。

4.2.2、以太网技术

常见的以太网技术有：

10Base-T。10Base-T以太网是替代同轴电缆以太网的产品，采用非屏蔽的双绞线(UTP)作为以太网传输介质，数据传输速率为10Mbit/s，支持以太网结构化布线方式和集线器设备.
快速以太网。快速以太网是在传统以太网基础上发展起来的，保留了传统以太网的帧格式和 CSMA/CD介质访问控制方式，但数据传输速率提高到100Mbit/s。
千兆位以太网。干兆位以太网涉及数据传输速率、是否支持全双工传送方式以及帧格式与以太网帧格式是否兼容等问题。千兆位以太网是建立在以太网标准之上的技术。
万兆位以太网。万兆位以太网进一步扩了以太网的数据传输速率和传输距离，还使得以太网技术突破局域网领域的限制，开始应用于城域网和广域网领域。

4.3、交换机

从工作原理角度看，交换机就是多端口的网桥，是目前应用最广泛的数据链路层设备。

交换机与网桥的工作原理相同，可以依据接收到的链路层帧的目的MAC地址，选择性地转发到相应的端口，这就是交换机的转发与过滤功能。

4.3.1、转发和过滤

交换机的基本工作原理是当一帧到达时，交换机首先需要决策将该帧丢弃还是转发，如果是转发的话，还必须进一步决策应该将帧转发到哪个（或哪些）端口去。

作为第二层设备的以太网交换机，可以实现帧的选择性转发，通过交换机互连的主机，不再属于一个冲突域，不会发生传统的冲突，交换机实现了冲突域的分割。

4.3.2、自学习

4.3.3、优点

消除冲突
支持异质链路
网络管理

4.4、虚拟局域网

以太网采用的是数据链路层的分组交换技术，不需使用CSMA/CD共享媒体，因此交换式以太网可以工作在无冲突的全双工方式下，且不受CSMA/CD端到端最大时延的限制，比共享式以太网能够连接更多的计算机。然而用交换机连接太多计算机会带来性能问题。

交换机虽然隔离了冲突域，但并不隔离广播域，一个由多个交换机互连而成的交换式以太网仍然是一个广播域。交换机在学习地址表的过程中会对所有目的MAC地址未知的帧进行广播。因此，当以太网中连接的计算机太多时会产生大量的广播帧，甚至导致“广播风暴”，使整个网络瘫痪。
另外，一个单位的所有计算机都连接在一个局域网中可能带来安全问题。一些部门或工作组因为安全保密的需求，不希望自己的计算机与其他部门或工作组的计算机直接进行通信。然而，一个单位建立多个物理上独立的局域网需要投入更多的经济成本和管理成本。

虚拟局域网（Virtual LAN，VLAN）技术的出现正好解决了上述两个问题。

4.4.1、简介

虚拟局域网是一种基于交换机逻辑分割广播域的局域网应用形式。虚拟局域网具有以下优点。

简化网络管理。由于站点物理位置与逻辑分组无关，当站点从一个工作组迁移到另一个工作组时，网络管理员仅需调整VLAN配置，无须改变网络布线或将站点搬移到新的物理位置。
控制广播风暴。当用交换机构建较大局域网时，大量的广播报文会导致网络性能下降，甚至会引发广播风暴（网络因传播过多的广播信息而性能恶化）。VLAN将广播报文限制在本VLAN之内，将大的局域网分隔成多个独立的广播域，可有效防止或控制广播风暴，提高网络整体性能。
增强网络安全性。便于管理员根据用户的安全需要隔离VLAN间的通信。

利用虚拟局域网技术，可以在一个物理局域网上建立多个逻辑上独立的虚拟网络。管理员可以将连接在交换机上的站点按需要划分为多个与物理位置无关的逻辑组，每个逻辑组就是一个VLAN。属于同一VLAN的站点之间可以直接通信，而不属于同一VLAN的站点之间不能直接通信。连接在同一交换机上的两个站点可以属于不同的VLAN，而属于同一VLAN的两个站点可能连接在不同的交换机上。

如下图所示，有10个站点分布在三个楼层，分别连接各自所在楼层的交换机，但这10个站点根据工作需要被划分为三个工作组，也就是说划分为三个VLAN，每个VLAN的成员分布在不同的楼层。

每个VLAN在逻辑上就如同一个物理上独立的局域网，VLAN中的站点仅能与同一VLAN中的站点通信。例如，站点B1～B3同属于虚拟局域网VLAN2 。B1仅能接收到工作组内成员（B2和B3）发送的帧，虽然它们没有和B1连在同一个交换机上。相反，B1接收不到与B1连接在同一个交换机上的其他工作组的成员（A1 、A2 和C1 ）发送的帧，即使这些帧的目的MAC地址是B1或广播地址。

注：虚拟局域网只是局域网给用户提供的一种服务，而不是一种新型局域网。

4.4.2、划分方法

虚拟局域网的划分方法主要3种：

基于端口：局域网的网络管理员可以按照以太网交换机的端口定义VLAN成员，通常每个交换机端口属于一个 VLAN（也可以有同时属于所有 VLAN的特殊端口，如Trunk端口）。
基于MAC地址：基于MAC地址划分虚拟局域网，是按连接到交换机的每个主机的MAC地址定义VLAN成员。
基于上层协议类型或地址：根据链路层帧所携带数据中的上层协议类型（如IP）或地址（如IP地址）定义 VLAN 成员，这种方法的优点是有利于组成基于应用的VLAN。

接下来，仅介绍其中最常用的方法，即基于交换机接口划分VLAN。如下图所示，管理员可以将交换机的接口1，3，5配置为属于VLAN1，而将接口2，4，6配置为属于VLAN2。为此，交换机的MAC地址表中除了MAC地址和对应接口号外，还有一个VLAN号。在逻辑上，可以认为交换机为每个VLAN维护一个转发表，并且仅同一VLAN内的接口间能转发帧，从而将一个物理交换机划分成多个逻辑上独立的交换机。

如果某些VLAN要跨越多个交换机，最简单的方法是将两个交换机中属于同一VLAN的接口用网线连接起来，然而这种方法导致交换机之间需要用网线连接多对接口，即n个VLAN就需要连接n对接口。

一种更好的互连VLAN交换机的方法是使用VLAN中继（Trunk）技术。如下图所示，管理员可以将交换机的某个接口配置为Trunk接口，将两个VLAN交换机用一对Trunk接口互连，由于Trunk接口可以同时属于多个VLAN，因此多个VLAN可以共享同一条中继来传输各自的帧。

问：交换机是如何知道从Trunk接口上接收到的一个帧属于哪个VLAN呢？

IEEE定义了802.1Q标准对以太网帧格式进行了扩展，允许交换机在以太网帧格式中插入一个4字节的标识符，称为VLAN标记（Tag），用来指明该帧来自于哪一个VLAN，如下图所示。当交换机需要将帧从Trunk接口转发出去时，VLAN标记会被插入帧中；当插入了VLAN标记的帧要从非Trunk接口转发出去时，会将该VLAN标记删除。因此，802.1Q标准虽然修改了以太网的帧格式，但对所有连接非Trunk接口的用户站点是完全透明的，802.1Q标记帧仅在交换机间各VLAN复用的Trunk链路上使用。

需要注意的是，当各站点被划分到不同的VLAN后，它们是不能直接进行通信的。因为每个VLAN在逻辑上都是独立的局域网。要想使这些站点能够互相通信，就需要使用路由器将这些VLAN在第三层（即IP层）互连起来。此时，虽然不同VLAN的站点之间通过路由器的转发能够在IP层互相通信，但它们在数据链路层是不能直接通信的，并且处于不同的广播域之中。

五、点对点链路协议

点对点链路协议大多应用于广域网中。对于点对点链路，由于不存在介质共享问题，所以这类链路不需要MAC协议。典型的点对点链路协议是：PPP和HDLC协议

5.1、PPP

5.1.1、简介

PPP协议，即点对点协议（Point to Point Protocol，PPP），是全世界使用得最多的点对点链路。

PPP可以进行错误检测、支持多种上层协议（即支持复用）、允许在连接时刻协商IP地址、允许身份认证等。

PPP主要提供3类功能：

成帧。确定一帧的开始和结束，帧格式支持错误检测。
链路控制协议（Link Control Protocol，LCP）。用于启动线路、检测线路、协商参数以及关闭线路。
网络控制协议（Network Control Protocol，NCP）。用于协商网络层选项，协商方法与使用的网络层协议独立。

在实际应用中，PPP的设计要困难得多，因此，有些功能不要求其实现。

差错纠正。仅要求PPP能够进行比特差错检测，但不要求纠正它们。
流量控制。由较高层协议负责遏制分组交付给 PPP 的发送速率，即由较高层负责弃分组或者遏制位于较高层的发送方，而不是由PPP进行控制。
按序交付。PPP 不要求链路中发送方发送帧的顺序与接收方交付帧的顺序相同。但是工作于PPP之上的其他网络层协议需要有序地进行端到端分组交付。

PPP的一个典型应用场景是家庭用户拨号上网。当用户拨号接入ISP时，路由器的调制解调器对拨号做出确认，并建立一条物理连接。PC机向路由器发送一系列的LCP分组（装成多个PPP帧），并接收LCP响应，为PPP选择一些参数，完成PPP链路配置。进一步，利用NCP进行网络层配置，NCP给新接入的PC机分配一个临时的IP地址，使PC机成为因特网上的一个主机。通信完毕时，NCP释放网络层连接，收回原来分配出去的IP地址，接着LCP释放数据链路层连接，最后释放的是物理层的连接。

5.1.2、帧结构

如下图，是PPP数据帧结构。

PPP 帧中的标志字段置为0x7E（符号"0x"表示后面的字符是用十六进制表示，7E的二进制表示是 01111110)。地址字段置为 0xFF（即11111111)，地址字段实际上并不起作用。控制字段通常置为0x03（即 00000011)。

协议字段告诉PPP接收方所接收的封装数据（即 PPP 帧信息字段的内容）所属的上层协议。当PPP接收方收到 PPP 帧时，需要检测该帧的正确性，如果检测到差错，则丢弃帧；否则将帧中封装的数据传递给相应的上层协议。例如，在Internet中，PPP 最常见的就是封装IP数据报，此时，协议字段的值为0x21。

信息字段内容的是上层协议分组（如 IP数据报），在 PPP 链路上发送被封装分组（如IP数据报），该字段最大的默认长度1500字节，在链路配置时可以改变该字段的长度。

检验和字段用于检测帧中的比特差错，使用2或4字节的CRC编码。

PPP帧中的地址字段和控制字段，在PPP链路建立之初，可以通过协商省略不用，即在帧中不包含这两个字段。另外，协议字段和校验和字段分别占1字节或2字节和2字节或4字节，也可以在PPP链路建立之初通过协商来确定。这是通过LCP来完成的，属于参数协商功能。

5.1.3、字节填充

PPP 是面向字节的，所有的PPP帧其长度都是整数字节，当PPP用在同步传输链路时，协议规定采用硬件来完成位填充（和HDLC的做法一样）；当PPP用在异步传输时，就使用一种特殊的字符填充法。

PPP 需要提供透明传输服务，即无论上层协议的分组中包含什么样的位串或字节，都应该能够通过PPP正确传输。为此，就需要考虑到，一旦上层协议分组中包含PPP帧中的标志字段01111110，就会导致PPP的接收方将上层协议分组中的 01111110 解释成PPP 帧的定界符，从而导致错误。解决这个问题的方法就是让PPP能够将信息中的 01111110与标志字段01111110区分开来，不产生二义性。PPP的具体做法是使用字节填充(Byte Stuffing）技术。

PPP定义了一个特殊的控制转义字节01111101。在成帧时，对帧中除了标志字段外的内容进行扫描，如果 01111110 出现在除标志字段以外的任何地方，PPP 就在01111110 之前插入一个控制转义字节01111101，即在01111110 前“填充”（加）一个控制转义字节进入传输的数据流中，以指示随后的 01111110不是一个标志字段，而是真正的数据。这样，当接收方收到01111101 后面紧跟一个01111110，就会去除填充的控制转义字节，将01111110 作为数来处理。

类似地，如果控制转义字节的比特模式自身作为实际数据出现，它前面也必须填充一个控制转义字节。因此，当接收方在数据流中看到单个控制转义字节时，它知道该字节是被填充到数据流中的，相继出现的一对控制转义字节意味着在发送的初始数据中出现了一个控制转义字节的实例。

如下图，是 PPP字节填充的过程示例。

5.2、HDLC协议

HDLC协议，即高级数据链路控制（High-level Data Link Control，HDLC）协议，可应用于点对点链路和点对多点链路。

5.2.1、帧结构

HDLC协议的帧结构如下图所示。

其中，帧的定界符是01111110，地址字段用于标识一个终端，控制字段用作序列号、确认、查询与结束，数据是传送的内容，校验和采用循环冗余码校验。

HDLC有3种类型的帧：信息帧(I格式）、管理帧(S格式）和无序号帧(U格式），3种帧的8位控制字段如下图所示。

HDLC协议使用了一个滑动窗口，其中序列号 Seq为3位，是当前帧的序列号，Next 字段用于确认Next之前的帧（即采用捎带确认），Next 值表示期望接收的下一帧。T/F 位中的T位表示主机询问终端，终端发送帧结束时置F位。

5.2.2、位填充

HDLC 协议是面向位的协议，为确保数据的透明传输，HDLC使用位填充。首先，发送端扫描整个数据字段（多采用速度较快的硬件实现），只要发现5个连续的1，就立即插入一个0，经过此过程处理后，数据字段不会出现连续的6个1。接收端接收到一个帧后，先找到标志字段01111110确定帧的边界，接着利用硬件扫描整个比特流，当发现5个连续的1，就删除其后的0，以还原成原来的信息。

如下图，是位填充的过程示例。