4.1 存储器概述

存储器可以分为：

• 随机存储器RAM，按照地址随机读写数据存储单元，且存取访问时间与存储单元的位置无关。
• 顺序存储器SAM，存储单元中的内容只能按照顺序访问，且访问速度与存储单元的位置有关。
• 直接存储器DAM，不必经过顺序搜索就能够在存储器中直接存取信息的存储器，兼有随机存储器和顺序存储器的访问特性。
• 只读存储器ROM。

存储系统的层次结构

现实世界中，一个存储器的存储速度、存储容量和成本往往是相互矛盾的，因此需要多种不同类型的存储器。典型的存储系统是一个金字塔结构，从上到下依次为寄存器、高速缓存、主存、磁带、磁盘等。越往上访问速度越快，单位容量的成本越高，越往下存储容量越大。

存储体系层次化结构的理论基础：时间局部性原理和空间局部性原理。

主存中数据的存放

• 存储字长：主存的一个存储单元能够存储的二进制位数。
• 数据字长：计算机一次能处理的二进制数的位数。
• 数据的边界对齐：在数据对齐的情况下，访问主存的次数相对于不对齐会减少一些，虽然浪费了一些空间，但是能够提升速度。以32位系统为例，双字数据的地址应该以8为倍数对齐，字数据地址应该以4为倍数对齐，以此类推。
• 大小端存储：采用多字节方式访问主存时主存中的字节顺序。存储器的低字节单元中存放的是数据的高字节时，称为大端，反之称为小端。

4.2 半导体存储器

4.2.1 静态MOS存储器

存储器以静态MOS存储元为基本单元构成的存储器称为静态MOS存储器（SRAM）。

工作原理

• 要想获取该单元存储的数据是0还是1，需要看A点和B点的电位。当A点为高电平而B点为低电平时，存储1，反之存储0。当A点为高电位时，T₂导通，T₁断路。
• T₃和T₄为补充电荷使用。无论A还是B为高电平，这两个三极管一定导通，当A为高电平时，B接地，因此从T₄过来的电荷都漏掉了，B点的电压还是0V，而A点则可以维持高电平。反之同理。
• 读取：当X地址译码线与Y地址译码线均导通时，4个三极管均导通，A的电平输出到左边，B的电平输出到右边。
• 写入：两个地址线导通后左边与右边一个输入高电平，一个输入低电平。设原来单元中存储1，现需要将其写为0，则需要向左边输入0V，右边输入高电平，这样放走了左边A的电荷之后，右边的T₂就断路，B不再接地，其电荷量增加，导通T₁使A的电荷完全被导走，以此达到新的稳态。注意这其中的步骤顺序。

单译码结构：一维的线性结构，索引一个存储单元只需要一个地址线。索引2ⁿ地址空间需要2ⁿ条地址线。
双译码结构：二维的地址结构，索引一个单元需要两个地址线。索引2ⁿ地址空间需要2^n/2+1条地址线。

4.2.2 动态MOS存储器

SRAM的不足之处有：晶体管数量较多，存储密度低，功耗大。

工作原理

• 处于保持状态时，预充、两条译码线均为低电平，若此时A为高电平，B为低电平，则B接地，A上有大量电荷，因此电容C₂带电，可以让A的高电平状态维持一段时间，但电荷还是会有流失，因此保持状态如果时间过长，其中的数据就会丢失。
• 刷新状态：预充和一条译码线（X译码线）导通，进行充电。如果原来A上带有电荷，但由于泄露已经较为微弱。在导通X译码线和预充之后，A得到了直接的电荷补充，而B由于此时仍然接地，因此无法得到电荷。双地址结构的DRAM刷新是按行进行的。
• 读数据：首先导通预充信号充电，使得左右两个C_D充满电。若此时A为高电平，充电完成后先导通X地址译码线，这样左边C_D会为C₂充电，自身电荷量增加，而右边的C_D将电荷部分转移到C₁中，自身电荷量减少。然后导通Y地址译码线，左边输出的电平略高于V_CC/2，右边输出的电平略低于V_CC/2。
• 写数据：首先导通Y地址译码线，并写入高电平和低电平，设向原来保存1的单元写入数据0，则右边输入高电平，左边输入低电平，因此右边C_D带电荷。然后导通X地址译码线。先是C₂上的电荷量大量减少，使得B不再接地，然后B接收到右边C_D的电荷，让A接地。

DRAM的刷新

• 最大刷新周期：信息存储到丢失之前的这段时间，两次刷新时间间隔不能超过最大刷新周期。
• 刷新周期：存储器实际上完成两次刷新的之间的时间间隔。
• DRAM按行进行刷新，为减少刷新的周期，可以减少存储矩阵行数，增加列数。
• 读操作也有刷新功能，但只能刷新一个单元。

刷新的不同方式：

• 集中刷新：将所有行在连续的一段时间内全部刷新完成。设刷新周期为2ms，2ms内一共可以进行4000次读写与保持操作，DRAM共256行，则集中刷新法是在前3744个读写周期内进行读写，而在后256个读写周期进行每一行的刷新。优点：读写操作期间不受刷新操作的影响，速度较快。缺点：存在较长时间无法进行访问的情况，“死区”。
• 分散刷新：将存储周期（时间较短，1μs左右）分为两个部分，第一个部分用于读写，第二个部分用于刷新。优点：不存在死区。缺点：速度慢。
• 异步刷新：将所有行的刷新平均分配到刷新周期之内，如刷新周期为2ms，共有256行，则将刷新周期分为256等份，每一个等份的前面所有存储周期用于读写，最后的一个存储周期用于刷新。

4.3 主存的组织和CPU的连接

4.3.2 存储器的扩展

• 位扩展：又称为字长扩展或数据总线扩展，将所有存储芯片的地址线、读写控制线并联，将输出合并得到数据内容，可以理解为，如果一块芯片的一个单元只能保存一位信息，则第一块芯片只保存所有地址中的第一位信息，第二块芯片只保存所有地址的第二位信息，等等。
• 字扩展：又称容量扩展或地址总线扩展，其不会增加数据的位宽，每一次寻址只会访问一块芯片，其他芯片没有被访问，输出也只是接受一个芯片的输出。将扩展出来的数据位线（地址的高位）连接到译码器来确定访问哪一块存储芯片。
• 字位同时扩展：上面两种方式的结合。

4.5 高速缓冲存储器

cache：在CPU与主存之间添加一块小容量的快速的SRAM，以提升访问主存的性能。依据的原理是空间局部性。

4.5.3 cache的基本原理

CPU通过字节地址访问快速的cache，首先需要确定需要访问的数据是否在cache中。

• 数据命中：数据在cache中。
• 命中访问时间：当数据命中时数据的访问时间，包括查找时间和cache访问时间两部分。
• 数据缺失：需要访问的数据不在cache中。需要将缺失的数据从主存调入到cache中才能访问数据。
• 缺失补偿：数据缺失时的访问时间，包括数据查找时间、主存访问时间、cache访问时间。
• 命中率：所有访问中成功命中的次数占总访问次数的比例。
• 缺失率：1-命中率。
• 访问效率：cache的命中访问时间与cache/主存系统的平均访问时间的比值。

4.5.4 cache读、写流程与关键技术

读

读入时查找cache中是否有需要读取的数据，有则读取，没有则调入这一块数据后再读取。

写

写比读复杂一些。
首先查找目标地址处的数据是否保存在cache，如果有则写入数据到cache。这里有两种策略：写回策略和写穿策略，写回策略在将数据写入cache之后立即结束操作，会导致cache与主存中数据的不一致；写穿策略在cache中数据被修改后再将数据写入到主存中，速度较慢。
如果目标地址处的数据不在cache，则也有两种选择：一种是将数据直接写入到主存，另一种是将这一块地址的内容载入到cache后写入到cache，至于之后是否需要写入主存使用的就是写回策略和写穿策略两种策略了。

4.5.5 相联存储器

相联存储器可用于判断对应地址的数据是否保存在该存储器中，基本数单元是键值对，键是主存地址，值是主存地址下的数据。由于相联存储器可以进行所有键值对的并行查找，因此只需查找一次就可以确定一个键值对。

4.5.6 地址映射

地址映射即为将主存地址空间映射到cache的地址空间，将存放在主存的程序或数据载入到cache块的规则。

• 全相联：各个主存块都可以映射到cache中的任意一个数据块。
• 直接相联：各个主存块只能映射到cache的固定某一块。
• 组相联：各个主存块只能映射到cache固定组中的任意块。

全相联映射

主存中每一个数据块都可以放置到cache中的任意一个数据块中，是一对多的映射关系。新的数据块可以载入到cache中任意一个空闲位置，只有cache满时才会进行数据块置换。

在全相联映射中，主存地址被划分为两部分：块号和块内地址。如果一块的大小为1024字节，则块内地址共10位，高位为块号。在cache中会保存块号和主存中该块号下的数据内容。

优点：cache利用率高，块冲突率低。缺点：淘汰算法复杂。适用于小容量的cache。

直接相联映射

在直接相联映射中，主存地址分为三部分：区号、区内块号、块内地址。其中区内块号为x，cache行数为y，则该块在cache中应该保存在第x行的位置。区内块号表示的数值应该与cache中的行数相同。

优点：淘汰算法简单。缺点：利用率较低，块冲突率高。使用率大容量cache。

组相联映射

组相联映射将主存地址分为3部分：组号、组内块号、块内地址。cache中所有行分为若干组，设一组有m行，共n组，则主存地址组号为x时应该保存在cache中的第x mod n组，组内块号为y的地址处应该保存在cache中的保存该组号的组中的任意一行。

4.5.7 替换算法

• 先进先出算法
• 最不经常使用算法：替换访问次数最少的cache
• 近期最少使用算法：为每一行维持一个计数器，命中时计数器清零，否则加1，将计数器最大的行换出。
• 随机替换算法

4.6 虚拟存储器

虚拟存储器处于主存-辅存存储层次，为了解决主存容量不足的问题，为程序设计者提供比主存空间大的编程空间。
虚拟存储器可以分为：页式、段式和段页式。
三种地址空间：虚拟地址空间、主存的地址空间、辅存地址空间。

在虚拟存储系统中运行时，CPU以虚拟地址访问主存，使用存储管理部件MMU找到虚拟地址与物理地址的对应关系，并判断该虚拟地址对应的物理地址是否在主存中，如果在则将虚拟地址转化为物理地址，CPU直接访问主存单元；否则将包含这个字的一页或一段调入主存，并在MMU中填写相关的标记信息。

4.6.3 页式虚拟存储器

虚拟地址被划分为虚拟页号VPN和虚拟页偏移VPO两部分，同时物理地址按照相同的划分方式分为物理页号PPN（页框号）和物理页偏移PPO。

页面命中时CPU硬件执行的步骤：

• CPU将虚拟地址传送给MMU。
• MMU用页表基址寄存器PTBR和虚页号生成页表项地址PTEA，通过这个页表项地址可以找到目标虚拟地址对应的物理地址值保存在什么位置。
• cache或主存向MMU返回页表项PTE。
• 如果返回的PTE中有效位为1，则MMU利用返回的PTE构造物理地址PA，并利用构造出的物理地址PA访问cache或主存。
• cache或主存返回数据给CPU。

缺页处理流程：前3步与上面相同

• PTE中有效位为0，所访问的页不在主存中，MMU触发异常调用内核的缺页中断处理程序。
• 如果主存页满，需要根据算法确定换出哪一个页，如果换出的页的有效位为1，则需要将其换出到磁盘。
• 缺页中断处理程序从磁盘中调入新的页，更新存储器中的页表项PTE。
• 返回原来进行继续执行。

如果存储系统中包含cache，则可以将部分页表的内容保存到cache中。

转换旁路缓冲区：TLB，用于缓冲经常访问的页表项PTE，实质是一个小容量的cache，大多采用全相联或组相联形式以提高访问速度，且采用随机替换算法。通常称TLB中保存的表为快表，主存中保存的表称为慢表。

3.1 计算机中的运算

注意移位运算中逻辑移位和算术移位的区别，算术移位不会修改符号位。

3.2 定点加减法运算

3.2.1 补码加减法运算

$$[x]_补+[y]_补=[x+y]_补 \pmod M$$

在以M为模时，两数的补码之和等于两数和的补码。

$$[x-y]_补=[x]_补-[y]_补=[x]_补+[-y]_补 \pmod M$$

3.2.2 溢出及检测

对于补码加法运算（减法可以转化为加法），溢出的检测方式有：

• 当正数与正数相加得到负数，或负数与负数相加得到正数时，有溢出。当两个运算数符号不同时，一定不会发生溢出。
• 根据运算过程中最高数据位的进位和符号位的进位来判断。当最高数据位的进位与符号位的进位不一致时发生溢出。考虑正数加正数的情况，如果结果为负数，说明最高数据位的进位为1，而符号位的进位为0，不一致。若为负数加负数得到正数，则符号位的进位为1，最高数据位的进位为0（否则得到的结果中符号位为1），不一致。
• 使用变形补码，即使用两个二进制数表示数据的符号。正数符号以00表示，负数为11。在运算过程中如果符号位出现了01或10则说明发生了溢出。
• 使用软件的方法判断
• 对于无符号数的溢出，只需要看两者相加后有没有溢出的进位即可。

3.2.3 加减法的逻辑实现

全加器

一位全加器需要接收两个操作数以及上一位的进位，输出该位的结果与下一位的进位。在设计过程中，如果需要使用减法，则将1与第二个操作数异或，然后进行加法操作。

多位串行加法器

将多个全加器串行在一起，上一位的进位传送到下一位的全加器中，多位串行全加器只能一位一位进行加法。

注意如果需要同时实现加法与减法，则增加一个输入标识计算是加法还是减法，0为加法，1为减法。如果需要计算减法，就需要首先计算第二个操作数的相反数的补码。计算一个数相反数的补码的方法是：对这个数所有二进制位取反再加1。因此减法标识位需要加到第一个全加器的进位中，然后让所有第二个操作数的位取反，即异或1。

溢出检测方法：如果按照第一种溢出方法进行检测，将最高位输出结果与两个最高位输入进行检测，看是否满足正正得负或者负负得正的情况。如果按照第二种溢出方法检测则更加简单，只需要对最高位全加器的进位输出与次高位全加器的进位输出异或即可。

缺点：串行进位，计算时间长。优化：并行计算，首先求出每一位进位的条件，然后用门电路连接输入与输出，这样能够实现仅依靠操作数输入而不需要前一位的进位就可以判断某一位是否会产生进位。

3.3 定点乘法运算

3.3.1 原码一位乘法

二进制乘法的手工计算与十进制的乘法类似，都使用竖式计算。
缺点：

• 需要多个输入的全加器
  • 解决方式：基于全加器循环累加0或被乘数
• 需要长度足够的结果寄存器
  • 解决方式：从部分积和乘数寄存器中获取结果
• 对应乘数的不同位，部分积的左移次数不同，且整个过程中总的移位次数较多。
  • 解决方式：右移部分积

原码一位乘法流程：

3.3.2 补码一位乘法

$$[x×y]_补=[x]_补\times 0.y_1y_2...y_n-[x]_补\times y_0\\ =[x]_补\times\sum_{i=0}^n(y_{i+1}-y_i)2^{-i}$$

由上面公式可推出运算规则：

• 如果y_n+1=y_n，部分积加0，算数右移1位。
• 如果y_ny_n+1=01，部分积加[x]_补，算数右移1位。
• 如果y_ny_n+1=10，部分积加[-x]_补，算数右移1位。
• 重复进行n+1步，最后一步不右移。

注意补码乘数在运算开始时符号位为1位，且后面要补一个0。

3.4 定点除法计算

3.4.1 原码一位除法

原码恢复余数除法

每一次需要尝试，如果不够减还需要重新加回去。

原码不恢复余数除法

当不够减时，下一次计算则是左移之后加，即加减交替。不够减或不够加商都上0，否则都上1。

3.5 浮点运算

3.5.1 浮点加减法计算

规格化浮点数

将一个浮点数按照指定的格式进行转换，规格化浮点数的尾数形式为00.1…或11.0…。如果是00.0…或11.1…这个形式，则需要进行左移，将尾数向左移动，每一次移动阶码-1，直到尾数为规范形式。当尾数为01或10开头时需要右移，阶码+1。

浮点数加减

• 对阶：求出两个数的阶码的差，然后右移阶码小的数的尾数并增加其阶码直到二者阶码相等。
• 尾数加减
• 结果规格化
• 右移舍入规则：
  • 0舍1入：如果右移出去的是1，则在最低位加1
  • 恒置1：只要1被移出就将最后一位置为1。
• 溢出处理：当阶码的尾数为01开头说明为尾数上溢，为10开头说明为下溢。

2.2 数值数据的表示

• 真值：使用"+“、”-"表示正负号的数值表示方式。
• 机器数：符号数值化的数据表示方法，使用0、1表示符号。
• 三种常见机器数（整数）：
  • 原码：最高位为符号位，其余位值为数值的绝对值，符号位正数为0，负数为1。原码表示方便，但计算复杂，且有+0和-0两种0的表示方式。
  • 反码：最高位符号位规则与原码相同，当数值为负数时，其余位值相对于原码全部取反。表示相对于原码较复杂，但计算简单，但0的表示同样不唯一。
  • 补码：表示负数时为反码+1。
  • 规则：对于总位数为n的二进制数，三种码对于正数的表示方法相同，可表示正数范围均为0~2^n-1-1。原码表示负数x，二进制数的值为2^n-1-x，反码表示为2ⁿ+x-1，补码表示为2ⁿ+x。反码的加法计算方法：二进制数直接相加后再加1。
• 移码：非符号位与补码相同，符号位与补码相反。编码方式是直接将真值加上一个常数偏移量，因此得名。
• 定点数表示：X₀.X₁X₂…，其表示范围为-1~1-2^-n（使用补码形式进行编码）
• 浮点数表示：一般格式为E_SE₁E₂…E_nM_SM₁M₂…M_k，其中E为阶码位，确定数据的范围，M为尾数，表示数的精度。其中阶码位和尾数位的最高位均表示符号。浮点数表示的不足之处是不同机器可能从相同的二进制数中提取出不同的浮点数。
  • IEEE754标准规定单精度浮点数阶码8位，有效尾数23位（不含尾数中的符号位，尾数中的符号位位于阶码前面，在最高位）；双精度浮点数阶码11位，有效尾数52位。阶码采用移码的方式表示，常数为127。其中有效尾数的整数位1被省略。对于单精度浮点数，若其偏指数（带有符号位的阶码的无符号值）为E，尾数为M，则真值可表示为2^E-127×(-1)^S×1.M。
    • 当E=0、M=0时表示机器零，无论S等于0还是1。
    • 当E=0、M≠0时，真值为非规格化的浮点数，2^-126×(-1)^S×0.M。即这个数太接近0，即使阶码为0也必须让尾数的整数位为0才能表示，这样会影响数的表示精度。
    • 当1≤E≤254时，正常表示，是规格化的浮点数。
    • 当E=255、M=0时表示无穷大。
    • 当E=255、M≠0时表示NaN。

2.4 数据信息的校验

2.4.1 码距与校验

码距：信息编码中两个编码对应的二进制位不同的位的个数。如10101和10001的码距为1，只有1个二进制位不同。码距越大、抗干扰、纠错能力越强，数据冗余越大，编码效率越低。
码距越大，纠错就越容易，当码距变大时，将一个合法编码转化为另一个合法编码需要修改多位，概率较低，且可以根据不合法编码与合法编码之间的码距，选择与不合法编码的码距最小的合法编码纠错。

• 当码距d≥e+1时，可以检测出e个错误
• 当码距d≥2t+1时，可以纠正t个错误
• 当码距d≥e+t+1时（e≥t），可以在检测e个错误的同时纠正t个错误。

2.4.2 奇偶校验

检测二进制代码中1的个数的奇偶性进行校验。
奇校验要让数据位和校验位整个的1的个数为奇数，偶校验则让1的个数为偶数。因此奇校验是1的个数为偶数时校验码为1，而偶校验时1的个数为奇数时校验码为1。

优点：检错简单，编码效率高。
缺点：不能获取错误位置，只是一种检错码，无错结论不可靠（如果两位同时错误无法检测出来）

改进：交叉奇偶校验，将原始数据信息构建为行列矩阵式结构，每一行和每一列都产生一个偶校验位，最后生成一个公共校验位。当有一位出错时，可以根据行校验位和列校验位的检查判断出是哪一位出错。但当两位数据同事出错时，不能确定到底是哪两位出错（有两种情况）。可纠正1位错误、检查部分偶数位错误、不能检测出错误发生在数据位中任意一个矩形4个顶点上的错误。

2.4.3 CRC校验

Cyclic Redundancy Check，循环冗余校验，是一种基于模2运算建立编码规则的校验码。其中模2运算与异或运算的规则相同，在加的基础上不用进位。在此基础上可以获取模2乘法运算和除法运算的规则。

编码规则：设CRC码长度n位，原始数据C_k-1C_k-2…C₀共k位，校验位P_r-1P_r-2…P₀共r位，则n=k+r≤2^r-1。生成一个多项式G(x)，将待发送的二进制数据用该多项式表示：G(x)=C_k-1x^k-1+C_k-2x^k-2+…+C₁x+C₀。G(x)需要满足：

• 最高位和最低位必须为1。
• 被传送信息任意一位出错时，被生成多项式除之后余数均不为0。
• 不同位发生错误时，模2除运算后余数不同。
• 对不为0的余数进行模2除运算能够使余数循环。

编码方法：

• 根据待校验信息的长度k按照k+r≤2^r-1确定校验码位数。
• 根据r和生成多项式的选择原则，选择一个位数为r+1的生成多项式。
• 将有效信息左移r位得到r+k位的二进制数Q。
• 对Q除生成多项式，以余数替换Q的低r位。

校验方法：
用数据除生成多项式，余数为0即为正确。

CRC校验码的循环特性：第i位出错的数据除以生成多项式获得的余数R_i与第i+1位出错的数据除以生成多项式获得的余数R_i+1满足：R_i+1=R_i左移1位后除以生成多项式获得的余数。

纠错方法：
记录当数据最高位错误时除以生成多项式获取的余数R。
当待检测数据除以生成多项式获得的余数不是0也不是R时，一边对余数补零继续除，另一边对待检测数据循环左移，当余数的值为R时，将当前循环移位后的待检测数据的最高位取反，再移位回来即可完成纠错。

2.4.3 海明校验

一种既能检错又能纠错的校验码，本质是多重奇偶校验。（海明码为偶校验）

设海明校验码共n位，原始数据k位，校验位r位，满足k+r≤2^r-1。
r位校验码（P_i，i=1,2,…,r）分别位于海明编码的第2^i-1位。海明码第i位的数据由若干个位于小于i的校验位校验。注意：第i位如果为数据位，那么参与检验该位的海明码的计算方式是——获取i的二进制表示，二进制中若第j位为1，则第j个海明码参与检验该值。如海明校验码的第11位，二进制表示为1011，则第1、2、4个校验码位参与校验该值。当有1位出错时，只需要将指错字的所有位转换为一个数值，该数值即为出错的位的索引。如第11位出错，则4个指错字中第1、2、4位必然为1，4个指错字结合为1011，即为出现错误的那一位。这种纠错方式可以纠正海明校验码中任何一位的错误，包括校验位。但海明校验不一定能够分辨出一位错与两位错。

1.2 计算机系统的组成

计算机系统由硬件系统和软件系统组成。

冯诺依曼计算机的工作原理：
冯诺依曼计算机由两部分：存储程序和程序控制构成。

• 存储程序将程序存放在计算机的存储器中。
• 程序控制按指令地址访问存储器并取出指令，经译码依次产生指令执行所需的控制信号，实现对计算的控制，完成指令的功能。

1.3 计算机系统的层次结构

可将计算机的层次结构分为6个基本层次：

• 高级语言层
• 汇编语言层
• 操作系统层
• 指令集架构层
• 微代码层
• 逻辑门层

其中上三层属于软件层，下三层属于硬件层。高层是低层功能的扩展，低层是高层的基础。

• 不同的用户位于不同的层次
• 不同层次具有不同属性
• 不同层次使用不同工具
• 不同层次代码效率不同

透明性概念：用户在高层中所看到的计算机并不会展现出计算机低层的特性，但并不代表这些特性不存在。

1.4 计算机性能指标与评价

1.4.1 基本性能指标

字长：CPU一次处理的数据位数，用二进制数的长度来衡量。字长一般与计算机内部寄存器、运算器、数据总线的位宽相等。

字长影响计算精确度，字长越长精确度越高。另外还影响数据的表示范围和精度。字长越长，定点数的表示范围就越大，浮点数的表示范围越大，精度越高。

总线宽度：数据总线一次并行传输的最大信息位数。

主存容量：主存中能够存储的最大信息量，一般以M×N表示，M表示存储单元数（字容量），N表示每个存储单元存储的二进制位数（位容量）。

存储带宽：单位时间内与主存交换的二进制数据量，单位B/s。（影响存储带宽的指标包括数据位宽和数据传输速率）

1.4.2 与时间有关的性能指标

时钟周期：计算机中最基本的最小的时间单位，一个时钟周期内CPU仅完成一个基本的动作。是时钟频率的倒数，常记为T。CPU内核工作的时钟频率称为主频，常记作f。外频：指CPU(内存)与主板之间同步的时钟频率(系统总线的工作频率)；倍频：CPU主频与外频之间的倍数；主频=外频×倍频。

CPI：Clock Cycles Per Instruction，执行每一条指令所需要的平均时钟周期数。
CPI = 程序中所有指令的时钟周期数之和 / 程序指令总数 = Σ(程序中各类指令的CPI × 程序中该类指令的比例)

CPU时间：即执行一个程序所需的物理时间，等于执行程序所需的时间周期数量 × 时间周期 = CPI × 程序中的指令数量 × 时间周期。

IPC：CPI的倒数，每个时钟周期能够执行的指令条数。

MIPS：Million Instructions Per Second，每秒多少百万条指令。计算公式：$$MIPS=\frac{IC}{T_{cpu}\times10^{6}$$其中IC表示程序中指令数量。$T_{cpu}$表示程序的CPU时间。如果上面的公式去掉10}6^，则表示的是每秒可以执行多少条指令。公式变形：$$MIPS=\frac{f}{CPI}=IPC\times f$$这里时钟频率f的单位为MHz。

课后习题和问题

6.1~6.2

1. 具体的交通工具
2. 如果链路层能够实现TCP协议能够实现的所有可靠性，那么TCP可靠传输服务才是多余的。这些可靠性包括内容可靠、拥塞控制、流量控制等。
3. 链路层能够提供的可能服务包括：

• 成帧，在每一个网络层数据报经链路传送之前，几乎所有的链路层协议都要将其使用链路层帧封装起来。
• 链路接入，媒体访问控制（MAC）协议规定了帧在链路上传输的规则。
• 可靠交付，当链路层协议提供可靠交付服务时，能够保证无差错地经过链路层移动每一个网络层数据报。
• 差错检测和纠正，通过让发送节点在帧中包括差错检测比特，让接收节点进行差错检查。

6.3

4. d(prop)<L/R，意味着传播时延小于传输时延。当传播距离很大时，一方将自己的分组发送完毕之后才会收到对方发送过来的分组，此时不会出现碰撞。当传播距离较小时，一方的分组还未完全发送完毕就已经检测到了对方分组的数据，此时就发生了碰撞。
5. 广播信道4种希望的特性：

• 仅有一个节点发送时，该结点能够独占所有的带宽。
• 多个节点发送时，能够平均分配带宽且充分利用带宽。
• 协议是分散的，任何一个节点的故障不会影响到整个系统的运作。
• 协议是简单的，实现成本低。
  时隙ALOHA能够实现第1、3、4种特性，但无法满足第2种。当有多个节点发送时，会产生碰撞。
  令牌传递能够实现第1、2种特性，无法满足第3、4种。当一个节点产生故障时，传递令牌的链路就会断裂，整个系统将会失效。另外每一种令牌传输协议都需要解决一些棘手的问题（P301原话）

6. 第5次碰撞后，节点应该在0~31中选择一个数字延时，因此选择4的概率为1/32。选择4时，网卡将会等待4×512bit时间，在10Mbps以太网中的时延为2048/10⁷=2.048×10^-4s。
7. 略
8. 当局域网周长很大时，令牌传递一个周期可能需要很长时间，当整个局域网中只有一台主机需要广播时，其不能一直广播，必须等待若干个周期的时间才能完成其广播，降低了效率。

6.4

9. MAC地址是48bit值，空间大小为2⁴⁸。IPv4为2³⁰，IPv6为2¹²⁸。
10. 不会处理这些帧（丢弃）。也不会将这些帧传递给C的网络层。如果A使用广播，则会处理，也会传递给网络层。
11. 因为ARP的功能是查询给定IP地址主机的MAC地址，此时发起请求的主机还不知道该IP地址对应的MAC地址是什么，因此只能通过广播的方式让ARP请求在整个网络中传播，期望目标IP地址主机能够给出回应。ARP响应报文已经知道了源、目的主机的IP地址以及MAC地址，因此不需要另外使用广播帧增加链路的负担，而是使用普通的链路层帧直接发送即可。
12. 不可能，两张ARP表对应的是两个子网中主机的MAC地址。
13. 没有什么不同，新的以太网和已经安装的以太网设备基础保持完全兼容。
14. 5个
15. 这取决于交换机一共有多少个端口。802.1Q标准中在标准以太网帧中加入了4字节的VLAN标签，理论上这个标签的空间为2³²，但一台交换机不可能有这么多端口，因此取决于这个交换机的端口数量。
16. 略

习题

1. 偶校验方法，对于16个比特的检验，4×4校验使用的检验位最少。
   1110 1
   0110 0
   1001 0
   1101 1
   1100 0
2. 对于单比特差错，二维奇偶校验的行校验码和列校验码必然各有一位出错，根据出错的行和列可以定位错误位，取反即可纠正。如将上一题修改为：
   1110 1
   0110 0
   1011 0
   1101 1
   1100 0
   此时容易发现第3行的行校验码错误，第3行的列校验码错误。
   某些双比特差错能够监测但不能纠正。如：
   1110 1
   0110 0
   1001 0
   1101 1
   1100 0
   这里的第2、4行的校验码出错，第2、3列的校验码出错。但是，有两种错误都可能会导致这种校验错误：第2行第2列和第4行第3列的2位出错，第2行第4列和第4行第3列2位出错。
3. 这个字符串对应的比特数据为：
   0100 1110 0110 0101
   0111 0100 0111 0111
   0110 1111 0111 0010
   0110 1011 0110 1001
   0110 1110 0110 0111
   以16比特分组求和，结果为0000 1100 0010 0000，取反得到1111 0011 1101 1111
4. a. 和为0001 1001 0001 1110，取反为1110 0110 1110 0001
   b. 和为0110 0100 0101 1111，取反为1001 1011 1010 0000
   c. 和为0000 0101 0000 0000，取反为1111 1010 1111 1111
5. 余数为100，R=100=4
6. 略
7. a. 因为任何单比特差错都会导致校验码除以生成多项式的余数改变。设第 i 位反转，0<=i<=d+r-1，则接收到的数据 K = D*2^r XOR R + 2ⁱ，如果用 G 除 K，那么余数一定不为 0
   b. 能。这里的G可以被11（二进制）整除，但是，任何奇数个比特错误（不论是否连续）所造成的偏差必然不可被11（二进制）整除。
8. a. 求导得$N(1-p)^{N-1}+N(N-1)p(1-p)^{N-2}=0$，计算得到$(1-p)-(N-1)p=0$，$p=\frac{1}{N}$。
   b. 使用该p值，效率为$\frac{N}{N}(\frac{N-1}{N})^{N-1}$，当N趋近于无穷时，其值趋近于1/e。
9. 同样的流程。
10. a. 在一个时隙，结点A成功占用信道的概率为$P_A(1-P_B)$，总体效率为$P_A(1-P_B)+P_B(1-P_A)$
    b. 如果$p_A=2p_B$，则发生碰撞后，在后面的一个时隙A重传成功的概率为$p_A(1-p_B)$，B重传成功的概率为$p_B(1-p_A)$，二者并不是两倍关系。要使得二者为两倍关系，则$p_A-p_Ap_B=2p_B-2p_Ap_B$，$p_A+p_Ap_B=2p_B$，$p_A=\frac{2p_B}{1+p_B}$
    c. 节点A的平均吞吐量为$2p(1-p)^{N-1}$，其他节点：$p(1-2p)(1-p)^{N-2}$
11. a. 一个节点没能在一个时隙传输数据的概率为$1-p(1-p)^3$，故节点A在时隙5首次成功的概率为$p(1-p)^3(1-p(1-p)^3)^4$。
    b. 某个节点在时隙4成功的概率为$1-p(1-p)^3$。
    c. 在时隙3中出现首个成功的概率为$4p(1-p)^3(1-p(1-p)^3)^2$。
    d. 效率为$4(1-p(1-p)^3)$
12. 略
13. 一个结点的传输时间为Q/R，一个轮询周期的时间为N(Q/R+t_poll)，在这段时间内可传输NQ比特数据，故吞吐量为Q/(Q/R+t_poll)
14. a. 从A到F依次为：192.168.1.1、192.168.1.3、192.168.2.1、192.168.2.4、192.168.3.1、192.168.3.3
    b. 从A：00-00-00-00-00-00、左路由器左接口：11-11-11-11-11-11、B：22-22-22-22-22-22、左路由器右接口：33-33-33-33-33-33、C：44-44-44-44-44-44、右路由器左接口：55-55-55-55-55-55、D：66-66-66-66-66-66、右路由器右接口：77-77-77-77-77-77、E：88-88-88-88-88-88、F：99-99-99-99-99-99。
    c. 主机E发送数据报，其以太网帧中目的MAC地址为右路由器的右接口MAC，即77-77-77-77-77-77，IP报头的目的IP地址为192.168.1.3。交换机注意到MAC地址为路由器的MAC，将其转发到路由器，第一步完成。右路由器接收到这个帧之后传递到其网络层，查询完成之后将其从左边接口发送出去，MAC地址修改为左路由器的右接口，即44-44-44-44-44-44。然后左边路由器接收到帧，将MAC修改为B的MAC即33-33-33-33-33-33，转发到B。
    d. 首先发送ARP报文广播获取192.168.3.2的MAC地址，然后发送。
15. a. 不用，因为二者在同一个子网。源IP为E的IP，目的IP为F的IP，源MAC为E的MAC，目的MAC为F的MAC。
    b. 不用，二者不在同一个子网。源IP为E的IP，目的IP为B的IP，源MAC为E的MAC，目的MAC为R1右端口的MAC。
    c. 广播查询B的MAC，会收到，不会转发，B不会发送一个ARP请求查询A的MAC，因为A发出的帧中已经包含了A的MAC地址。S1会在转发表中记录B的地址并向A转发。
16. a. 同15.a
    b. 会，因为此时E不知道B和它是不是在一个子网中。目的MAC地址为广播MAC。
    c. 会向子网3发送报文，其他同15.c
17. 10Mbps等待51200比特时间需要5.12ms，0.512ms。
18. A将会在512+64=576比特时刻完成帧的传输，在A传输结束之前B开始传输一帧，因此在B开始传输时，A的传输信号还没有到达B，也即B传输开始的时刻在0~324比特时间之内。最坏情况下，B的信号将在324+325=649比特时间到达A，而A此时已经完成了传输，因此A能够完成传输。
19. 两者在245比特时间时同时检测到碰撞，因此会等待K×512比特时间，其中K取0或1。如果两者选取的K相同，那么重传依然会碰撞。如果选择的K不同，不妨设A选择的是0，B选择的是1，二者在检测到碰撞后发送48比特时间的干扰数据，在293比特时间同时停止发送数据，然后在293+245=538比特时间A和B停止检测到信号，然后A开始传输数据，需要96比特时间，即在634比特时间完成传输。同时B等待到293+512=805比特时间。而A的重传数据在538+245=783比特时间时被B检测到，一直到634+245=879比特时间才结束接收信号，B也在这个比特时间开始传输其数据。
20. a. 一帧需要k个时隙才能传输完成。设Y为连续X个空闲时隙，直到出现一个工作时隙，Y=X+1。则$E(Y)=\frac{1}{P_{working}}=\frac{1}{Np(1-p)^{N-1}}$，故$E(X)=E(Y)-1$。故效率=$\frac{k}{k+x}$可求出。
    b. 求导计算得到p=1/N时得到最大值。
    c. N趋于无穷时，效率为$\frac{k}{k+e-1}$
    d. 帧长度变大时，发送一个帧需要的时隙增加，有其他节点等待发送数据的可能性越大，空闲时隙的数量就越少。
21. 略，易得。
22. 略
23. 1100Mbps。转发设备是交换机，因此无碰撞。
24. 使用集线器代替则下面的3个100Mbps光纤只能以100Mbps的总带宽服务下面的主机，故一共500Mbps。
25. 100Mbps。
26. 第一步完成后，交换机学习到B的MAC地址以及接口。然后将这个帧发送到其他所有接口，因为此时交换机还不知道E在哪。第二步完成后，交换机学习到E的MAC地址以及接口。然后将这个帧发送给B。第三步完成后，交换机学习到A的MAC地址以及接口，然后将这个帧发送给B。第四步完成后，交换机没有学习。
27. 略
28. EE发送的帧到达交换机时，交换机将帧转发到路由器，然后路由器修改目的MAC地址将其发送到交换机，然后交换机将该帧通过CS的VLAN发送出去。
29. 略
30. 略
31. 以太网、DHCP、ARP、DNS、TCP、HTTP。
32. 略
33. 略

链路层服务的原则：

• 错误检测，校正
• 共享广播信道：多址访问
• 链路层寻址
• 局域网：以太网，VLAN

实例化，各种链路层技术的实现

6.1 链路层概述

• 节点：主机和路由器
• 链路：沿着通信路径连接相邻节点的通信信道，分为有线和无线链路
• 帧：数据链路层的分组单元

数据链路层的主要功能：负责将数据包通过链路从一个结点传输到物理上相邻的节点

数据链路层的简单模型：一个主机向另一个主机发送数据，期间经过多个路由器，通过了多个网络，数据在这些网络中流动。

说明：

• 数据报咋不同链路上可能由不同的链路层协议进行处理
  • 如第一段链路由PPP处理，最后一段链路由以太网处理等
• 不同的链路层协议可能提供不同的服务，如可靠传递等

6.1.1 链路层提供的服务类型

• 成帧、链路访问
  • 将数据加上头部和尾部，以此封装为数据帧
  • 共享介质的信道访问
  • 帧头部用MAC地址标识源和目的，不同于IP地址
• 可靠传递
  • 很少用于误码率低的链路（光纤、双绞线链路）
  • 用于误码率高的链路（无线链路）
• 流量控制
  • 在相邻的收发节点之间限制流量
• 差错检测
  • 信号衰减和电磁干扰噪声容易导致出错，接收方检测到错误存在时，会给发送方发送信号要求重传或者丢弃该数据帧
• 差错纠正
  • 接收方检测和纠正帧中错误，不用重传
• 半双工和全双工
  • 半双工时链路两段的节点都能够传输分组但不能同时传输

6.1.2 链路层在何处实现

链路层的主体部分是在网络适配器中实现的，网络适配器有时也称为网络接口卡，位于网络适配器的核心是链路层控制器，其中实现了多个链路层服务。

适配器通信

• 在每一台设备上都有一个适配器（主机、交换机、路由器等）
• 链路层在适配器或芯片上实现
• 直接与主机的系统总线相连，与其他连接主机的IO设备相同
• 是硬件、软件和固件的结合体
• 适配器是半自治单元
  • 网络接口卡或芯片是适配器
  • 帧的发送和接收、检错、丢弃都是适配器自主进行的
  • 向上提交数据时，需要节点干预
  • 最终受控于节点
• 发送方在一个帧内封装数据报，增加差错检测位，可靠交付，流量检测等；接收方查找错误，可靠交付，进行流量控制，取出数据报并交给网络层。

6.2 差错检测和纠正技术

在发送节点，为了保护比特免受差错，使用差错检测和纠正比特EDC来增强数据D。通常要保护的数据不仅从网络层传递下来需要通过链路传输的数据报，而且包括链路层首部中的链路级的寻址信息、序号和其他字段。链路级帧中的D和EDC都被发送到接收节点。差错检测不是100%可靠的，EDC越长可靠程度越高，检错和纠错的能力越强。

6.2.1 奇偶校验

最简单的差错检测方式就是单个比特的奇偶校验，但是检错能力太差了，因此可以使用二维奇偶校验方法，包含比特值改变的列和行的校验值都将会出现差错，因此接收方不仅可以检查到单个比特出错，还可以纠正。

接收方检测和纠正差错的能力被称为前向纠错。

6.2.2 检验和方法

因特网检查和

• 目标：检测发送包中的错误，仅用于运输层
• 发送方：
  • 将数据段的内容作为16比特的整数序列
  • 校验和：累加求和，计算和的反码
  • 发送方将得到的校验和值放入到PDU校验和字段
• 接收方
  • 计算收到的数据段的校验和
  • 检查计算出的校验和与校验和字段中的值是否相同
    • 如果不同则检测到错误
    • 如果相同则认为没有监测错误（不代表就一定没有错误）
• 仅用于TCP、UDP和IPv4协议之中

6.2.3 循环冗余纠错CRC

对于d个比特的数据D，选择r+1比特模式（生成多项式）表示为G，目标是选择r个CRC比特R使得：
- <D,R>刚好能够被G整除（模2计算）
- 接收方已知G，用G去除<D,R>，如果余数不为0则检测到错误
- 能检测到所有小于r+1个比特的错误

6.3 多路访问（即多址访问）链路与协议

链路分为两种：

• 点到点链路，由链路一端的单个发送方和链路另一端的单个接收方组成。如PPP、以太网交换机和主机之间点到点的链路
• 广播链路，能够让多个发送和接收节点连接到相同的、单一的、共享的广播信道上。如传统以太网、802.11无线LAN。
  • 特点：
    • 单个共享广播信道
    • 当两个或多个节点同时传输时，会产生相互干扰。
    • 碰撞：一个节点同时收到两个或多个信号

多址访问协议：

• 分布式算法决定节点如何共享信道，如结点何时可以传输数据
• 特别注意：有关共享信道的通信需要使用信道本身，没有额外的信道用于协调
• 理想的多址访问协议需要满足：
  • 假定：信道为速率为Rb/s的广播信道
  • 当只有一个节点有数据发送时，该结点的吞吐量为R
  • 当M个节点有数据发送时，每一个结点的吞吐量为R/M
  • 分散，没有特定节点用于调整传输，没有时钟同步
  • 简单，容易实现
• 多路访问协议的分类：
  • 信道划分协议
    • 将信道划分为多个小片（使用时隙、频率、编码等划分）
    • 将不同的片分配给不同的节点使用
  • 随机访问协议
    • 信道没有被分割，允许碰撞
    • 需要有碰撞恢复的技术
  • 轮流协议
    • 节点轮流传送，但是数据量大的节点轮流更长时间

6.3.1 信道划分协议

信道划分分为时分复用、统计时分复用、频分复用和随机访问这几种。

信道划分协议TDMA

• 时分复用TDM
  • 循环访问信道，每一个结点在每一次循环中得到固定长度的时隙（时隙长度=传输单个分组的时间）
  • 没有数据发送的时隙空闲
• 统计时分复用STDM
  • 使用STDM帧作为基本单位，一个STDM帧可以容纳多个分组，时隙数量小于用户数量。
  • 每当用户需要发送分组时将其发送到集中器中的集中缓存
  • 集中器按照一定的顺序依次扫描用户是否输入，将缓存中的输入数据放到STDM帧中，没有数据的缓存跳过，当一个帧的数据放满时发送。
  • 是时分复用的改进
• 信道划分协议FDMA
  • 信道按照频谱分为若干个频段
  • 每一个节点分配固定的频段
  • 在频段不用时该部分信道就被闲置浪费了

6.3.2 随机访问协议

• 当节点有数据发送时
  • 以信道全部速率R传输
  • 没有主节点起到协调作用
• 两个或多个节点传送时会发送碰撞
• 需要有检测碰撞和恢复碰撞的技术，如延时之后重传
• ALOHA，时隙ALOHA等

ALOHA

Additive Link On-Line HAwaii system，是计算机网络早期发展中一个著名的网络，至今还在运行。

特征：

• 网络拓扑采用星形结构
• 为了节省费用和易于组网，网络中各个站点的通信采用无线传输介质
• 由于采用无线电信道。考虑到无法申请更多的频率点，因此所有站点都使用同一的频率通过主机交换信息

工作原理：

• 当一帧首次到达（即一个网络层数据报在发送节点从网络层传递下来），节点立刻将该帧完整地传输到广播信道中，取帧传输时间为时间单元。
• 在任何给定时间，某个结点传输一个帧的概率为p。在其传输过程中其他节点不能传输，根据计算，一次传输成功的概率为p(1-p)^2(N-1)。ALOHA协议的最大效率为1/2e。
• 如果发生了碰撞，节点等待随机的一段时间之后重新发送分组。
• ALOHA系统中一个节点并不会关心其他结点是否正在发送帧，这也就是为什么纯ALOHA一次传输成功的概率为p(1-p)^2(N-1)，对于一个在t时刻开始传输的帧（所有帧传输时间为1）而言，需要从t-1到t+1的这段时间内都没有其他的帧开始传输，可见如果传播速率足够快，在该帧还没有发送完的时候，已经有节点能够接收该帧了，但它不会因此而阻止自己不发送自己需要发送的帧。

时隙ALOHA

将整个链路以时隙分割，每一个主机如果要发送分组，则必须在每一个时隙之内将分组发送完成。如果有冲突则随机等待几个时隙之后重发。

载波侦听多路访问CSMA

在时隙和纯ALOHA中，一个节点传输的决定独立于连接到这个广播信道上的其他节点的活动。特别是一个结点不关心在它开始传输时是否有其他节点正在传输。

载波侦听：在传输前首先对链路进行监听，如果信道空闲，则传输整个帧，否则等待。但是碰撞还是可能发生。如果一个信道的延迟时间比较长，当其他主机开始发送分组时，这个分组可能不会很快地传到当前主机，使得当前主机误以为信道中没有分组正在传输，因此可能存在其传输还未完成时发现有碰撞的情况。

CSMA分类：

• 非坚持CSMA，一旦监听到信道忙，就不再继续监听，而是根据协议的算法延迟一个随机的时间之后重新监听。如果进行载波监听时发现信道空闲，则将准备好的帧发送出去。
• 时隙非坚持CSMA，采用划分时隙的随机接入CSMA协议，协议规定只能在每一个时隙开始时才能发送帧。
• 1坚持CSMA，一个站点要传送数据之前首先监听信道，如果忙则持续等待到监听到信道空闲时发送数据，如果发生冲突则站点等待一个随机长的时间然后重新开始。
• P坚持CSMA，一个站点要传送数据之前首先监听信道，如果忙则持续等待到监听到信道空闲时，以概率P发送数据，而以（1-P）延迟一段时间τ（网络中最远的端到端传播时延），重新监听信道。如果发生冲突，站点等待一个随机长的时间，然后重新开始。

CSMA比较：

• 非坚持：不能充分利用信道刚刚转入空闲期的这段时间
• 1坚持：容易在上述这段时间之内产生冲突，实际网络常用
• P坚持：很难选择一个用于各种通信量度的P值

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

• 在短时间内碰撞能够被检测
  • 在有线LANs中比较容易：测量信号强度，比较收发的信号
  • 在无线LANs中比较困难：传输时接收器关闭，接收的信号远小于发送的信号强度
• 碰撞之后停止传输，减少信道浪费
• 强化碰撞
  • 当发送数据的站一旦发现产生碰撞，除了立即停止发送数据之外，还要继续发送若干比特的人为干扰信号，以便让所有的用户都知道现在已经发生了碰撞

争用期：

• 最先发送数据帧的站，在发送数据帧之后至多经过2τ（最长的端到端时延）时间就可以知道发送的数据帧是否遭受碰撞
• 以太网的端到端往返时延2τ称为争用期，或碰撞窗口
• 经过争用期这段时间还没有检测到碰撞，就可以确认这次发送没有碰撞

以太网CSMA/CD算法：

• 网卡从网络层接收数据报，并创建数据帧
• 如果网卡检测信道空闲，则开始进行帧传输
• 如果网卡检测信道忙，则等待直到信道关闭，然后发送
• 如果网卡发送整个帧没有探测到另一个传输，则网卡完成帧发送
• 如果网卡检测到另一个传输，则传输终止并发送干扰信号
• 传输终止之后，使用二进制退避（网卡随机从0/1/2/3/…/2^m-1之中选择K，网卡等待K*512bit时间，返回第2步）越多的碰撞决定越大的退避间隔

6.3.3 轮流协议

为了满足：当有M个节点活跃时，每一个活跃节点的吞吐量接近R/M bps，开发了此协议。

• 信道划分协议的特点：
  • 在负荷重时，共享信道有效公平
  • 在负荷轻时效率低，信道访问延时，即使只有一个活动结点也只能分配到1/N的带宽
• 随机访问协议的特点：
  • 在负荷轻时效率高，只有一个节点也能够充分利用信道
  • 在负荷重时将会产生巨大的碰撞开销

轮询协议

• 要求这些节点之一要被指定为主节点。
• 主节点以循环的方式轮询每一个节点。主节点首先向节点1发送一个报文说明其能够传输的帧的最多数量，然后在节点1传输了某些帧之后，主节点再发送报文向节点2说明，以此类推。
• 这个协议引入了轮询时延的开销，且如果主节点故障，整个网络都将崩溃。

令牌传递协议

• 没有主节点，一个称为令牌的小的特殊帧在节点之间以某种固定的次序进行交换。
• 当一个节点收到令牌时，仅当它有一些帧要发送时，它才持有这个令牌，否则立即向下一个节点转发该令牌。当一个节点收到令牌时，如果它确实有帧要传输，它发送最大数目的帧数，然后把令牌转发给下一个节点。
• 令牌传递分散，并高效，但一个节点的故障可能会使整个信道崩溃。如果一个节点偶然忘记了释放令牌，则必须调用某些恢复步骤使得令牌返回到循环。

总结：对共享介质的处理

• 信道划分，可基于时间、频率、编码，分为时分和频分
• 随机划分（动态）
  • ALOHA，S-ALOHA，CSMA，CSMA/CD
  • 载波侦听：有线较容易，无线较困难
  • CSMA/CD 用于以太网
  • CSMA/CA 用于802.11
• 轮流
  • 主节点轮询，令牌传递

6.4 交换局域网

6.4.1 链路层寻址与ARP

MAC地址（LAN地址，物理地址）

作用：在数据链路层表示每一块网络适配器，使得能够在广播信道上寻找目标节点
组成：

• 48 bit
• 前24bit由IEEE分配管理——OUI号
• 后24bit由厂商自行分配
• IEEE管理MAC地址空间

MAC地址是烧在网络适配器的ROM中，不可修改（软件模拟的可以修改）

与IP地址比较：

• MAC地址是平面地址，类似于身份证号
• IP地址是层次地址，类似于邮政通信地址
• MAC地址在不同的网络之间迁移时，不会改变
• IP地址在不同的网络之间迁移时，需要改变以适应新的网络配置
• 无线网络中进行漫游时，如果在不同的网络之间切换时，改变网络设置会导致连接中断。

MAC地址的重要性：

• 局域网设备不能识别IP地址，因为其工作在链路层，因此只能够通过MAC地址寻找主机。
• 进程产生的套接字是端口号+IP地址，在局域网中是通过IP地址获得MAC地址。
• 通过ARP（地址解析协议）可以在已知IP地址的情况下，获得MAC地址。

地址解析协议（ARP）

目标：根据目标的IP地址获取其MAC地址
ARP高速缓存（ARP表）

• 每一个IP节点（主机、路由器）都有ARP表
• 局域网节点的IP/MAC地址映射：<IP; MAC; TTL>
• TTL：时限，Time to Live，超过TTL的地址映射会被删除（一般20分钟）

ARP协议工作流程：

• 建立ARP请求包
• 广播发送该ARP请求包，其中包含目标的IP地址。广播的MAC地址为全1，即FF:FF:FF:FF:FF:FF
• 目的主机接收到该ARP请求包，建立包含自己的MAC地址的ARP应答包（请求包和应答包的源、目标是不一致的）并发送
• 发出请求的主机接收到该数据包之后，更新ARP高速缓存

当一台主机需要发送数据到另一个子网的主机时，首先需要通过ARP报文获取目标主机的MAC地址，然后在发送IP报文时，MAC地址不应该填目标主机的MAC，而应该是路由器的MAC，这样路由器才能将这个报文转发到另外一个子网。

6.4.2 以太网

类型：

• 总线式以太网：所有的主机都与一条总线连接，接收到不是发送到本机的报文则不予理会。
• 交换式以太网：主机与主机通过交换机连接为网状结构。

以太网帧结构

• 数据字段：46~1500字节
• 前同步码：8字节，前面7个字节的格式为10101010，最后一个字节为10101011，用于同步发送方与接收方的时钟
• 地址：6字节，若适配器收到以太网帧，目的地址为自己的MAC地址或广播地址，就将帧中的数据传给网络层，否则适配器丢弃该帧
• 类型：上层协议类型（大多为IP协议，也支持其他协议）
• CRC：由接收方检查，如果检测到错误就将该帧丢弃

以太网提供的服务：

• 无连接服务：在发送适配器和接收适配器之间不需要另外的连接操作
• 不可靠服务：接收适配器不发送确认帧或否认帧给发送方
• 交给网络层的数据包可能存在间隙，如果应用使用TCP，间隙会被填充，否则应用会看见间隙

以太网使用的CSMA/CD

• 没有时隙
• 当适配器侦听到其他的适配器在传输时，它不传输帧，即载波侦听
• 正在传输的适配器如果检测到其他适配器也在传输，则其终止自己的传输，即碰撞检测
• 在重新传输之前，适配器等待一段随机时间，即随机访问

算法流程：

• 适配器收到来自网络层的数据包，创建帧
• 若适配器检测到信道空闲，则开始传输帧；若检测到信道忙，就开始等待，直到信道空闲时才开始传输该帧
• 若适配器传输了整个帧而没有检测到其他适配器的传输，则该适配器完成该帧的传输
• 若适配器在传输时检测到其他适配器也在传输，则停止传输并发出拥塞信号
• 终止传输之后适配器进入指数回退阶段，在经历第m次碰撞之后，适配器随机从{0, 1, 2, …, 2^m-1}中选择k值。适配器等待k*512比特时间之后返回第2步

拥塞信号：用于确保所有传输者都能检测到碰撞而传输的信号，共48比特
比特时间：传输1个比特所用的时间

指数回退算法

• 目的：适配器重传时试图估计正确的负载。
• 重载：随机等待的时间可能会更长。
• 第一次碰撞：从{0, 1}中选择K；延迟是K*512比特传输时间
• 第二次碰撞：从{0, 1, 2}中选择K
• …

重要特性：

• 使用CSMA/CD协议的以太网不能进行全双工通信，而只能使用双向交替通信（半双工通信）
• 每一个站在发送数据之后的一小段时间之内存在遭遇碰撞的可能性
• 这种发送的不确定性使得整个以太网的平均通信量远小于以太网的最高数据率

争用期长度：

• 10Mb/s的以太网取51.2μs为争用期的长度，100Mb/s为其1/10
• 对于10Mb/s的以太网，在争用期之内可以发送512比特（64字节）
• 以太网在发送数据时，如果前64字节没有发生碰撞，则后续的数据旧不会发生碰撞

最短有效帧长

• 如果发生碰撞，就一定会发生在发送的前64字节内
• 由于一检测到碰撞就立刻中止发送，则此时已经发送出去的数据量一定小于64字节
• 以太网规定最短的有效帧长为64字节，凡是长度小于64字节的帧都是由于冲突而异常中止的无效帧

物理层简介

信号编码：

• 曼彻斯特编码：设置0为上升沿，1为下降沿
• 差分曼彻斯特编码：0翻转，1不翻转

集线器互联

• 主干集线器互联LAN网段
• 扩展了节点之间的最大距离
• 原先独立的网段碰撞域变成了一个大的碰撞域
• 不能将10BaseT和100BaseT的以太网互联
  • 10和100代表速率，T代表使用双绞线
  • 节点连接到集线器，是一个星形的拓扑形状。在节点和集线器之间的最大距离为100m
  • 10Base5代表粗同轴电缆，可靠性好，抗干扰能力强。
    • 收发器：用于发送、接收数据，冲突检测，电气隔离等。
    • AUI：连接件单元接口
    • 这种电缆一般使用总线型拓扑，用于网络骨干连接
  • 10Base2代表细同轴电缆，可靠性稍差
    • 使用BNC T型接头连接，使用总线型拓扑，可用于办公室LAN
• 集线器
  • 集线器本质上是物理层的中继器
  • 从一个接口收到的比特流会传给其他所有接口
  • 同样速率
  • 没有帧缓存
  • 集线器没有CSMA/CD，由适配器检测碰撞
  • 提供网络管理功能（可网管、智能、网络分段）
• 千兆以太网
  • 使用标准以太网帧格式
  • 允许点对点链路和共享的广播信道
  • 共享信道时使用CSMA/CD，为了得到可接受的效率，节点之间的距离需要短一些
  • 对于点到点链路可以以1Gbps的速率全双工工作

6.4.3 链路层交换机

• 链路层设备
  • 存储、转发以太网帧
  • 查看输入帧的MAC地址，选择性地将帧输出到一个或多个输出链路，使用CSMA/CD
  • 对外透明，主机不知道交换机的存在
  • 即插即用，自学习，交换机无需配置
• 交换机：多路同时传输
  • 主机直接连接到交换机
  • 交换机缓存到数据包
  • 每一条链路都采用了以太网协议，但之间没有冲突，全双工通信
    • 每一条链路是其自身的冲突碰撞域
    • 这里的全双工通信指的是当两个主机之间存在至少一台交换机时，可以进行全双工通信，其中的每一条物理链路都是半双工的，但由于交换机可以进行存储转发工作，所以两边的两个分组在某一个交换机会相遇，然后各自继续在链路中传输。
  • 交换机中存在一个交换表
    • 表结构：主机MAC地址，连接主机的接口，时间戳（产生表项的时间）
    • 与路由表类似
  • 交换机通过学习可知通过哪一个接口可以到达哪一个主机
    • 当数据帧进入交换机时，交换机学习发送方连接的接口，并将发送方/接口对记录到交换表
  • 交换机：帧过滤/转发
    • 使用发送方输入接口与MAC地址
    • 使用目标MAC地址检索交换表
    • 如果检索到目标地址对应的接口，当目标地址接口不是来源接口时，从该接口转发数据帧，否则丢弃该数据帧。如果没有检索到接口则向所有非来源接口转发数据帧广播

网桥互联

• 网桥实质上就是一种存储-转发设备，用于实现MAC层的LAN互连
• 工作原理：
  • 不断监听各端口是否有信号
  • 收到无差错的帧则缓存，反之将差错帧丢弃
  • 若所收帧的目的MAC地址属于另一网段，则通过站表决定向何端口转发
  • 网桥不转发同一“网段”内通信的帧
    • 目的主机和源主机不连接在网桥的同一个接口上才会转发
  • 网桥不会修改所转发的帧的源地址
• 网桥的优势
  • 过滤通信量
  • 扩大了局域网的物理范围
  • 提高可靠性
  • 可互联不同物理层、不同MAC子层和不同速率的局域网
• 网桥的缺点
  • 接收和转发产生时延
  • MAC子层没有流量控制功能，网络负荷重时，网桥缓存空间可能发生溢出，产生帧丢失现象
  • 不同MAC子层的网段桥接时，在转发帧之前要修改帧的某些字段，这也需要时间
  • 广播风暴。网桥只适合用户少于几百个和通信量不太大的局域网，当广播信息过多时会产生拥塞
• 网桥和集线器的区别
  • 集线器只是将网络覆盖距离简单地延长，且距离有限，实现在物理层。网桥不仅具有将LAN的覆盖距离延长的作用，而且理论上可以做到无限延长，具体实现在MAC层
  • 集线器仅具有简单的信号整形和放大功能，网桥属于一种智能互联设备，主要提供信号的存储、转发、数据过滤、路由选择等能力
  • 集线器仅是一种硬件设备，网桥还有软件
  • 集线器只能互联同类的LAN，而网桥可以互联不同类型的LAN
• 透明网桥：网桥对于局域网其他的站点时不可见的
• 网桥的问题：当一个局域网中有不止一个网桥时，一个帧可能从一个网桥传到另一个网桥，然后另一个网桥又传回来，导致兜圈子现象
  • 解决方法：支撑树算法
    • 互联在一起的网桥彼此通信后，能够找出原来的网络拓扑的一个子集，在这个子集里面整个连通的网络中不存在回路。一旦支撑树确定，网桥会断开某些端口，以确保原来的拓扑是一个支撑树。
    • 支撑树算法选择一个网桥为树的根，然后以最短路径为依据，找到树上的每一个结点
    • 为了让支撑树能够反映网络拓扑的变化，每隔几秒钟每个网桥要广播其标识号，和它知道的所有其他网桥
    • 缺点：互联的局域网数量很大时，支撑树算法开销会显著增加
• 多端口网桥
  • 链路层可以实现直通交换：帧从入端口转发到出端口不需要收集整个帧，实际上只需要找到帧开头的目的地址即可，这样能够少量减少延迟。
• 以太网交换机与路由器的比较
  • 两者都是存储转发设备，但路由器是网络层设备，交换机是链路层设备
  • 路由器维护的是路由表，实现路由算法，而交换机维护交换表，实现MAC地址过滤和自学习

6.4.4 虚拟局域网VLAN

在一个局域网内，所有的第二层广播流量都将穿过整个局域网，这对于安全性不利，并且传播的数据报数量较大，也会影响效率。

虚拟局域网VLAN：是基于接口的VLAN，交换机对接口进行分组使得单一的交换机设备可以为多个虚拟的局域网工作，像是多台交换机实现的功能。

功能：

• 流量隔离，一个VLAN内的帧不能传递到其他的VLAN中
• 动态分组，交换机的接口可以动态组合，因此VLAN也是可以动态分配的
• 数据转发，通过VLAN间路由转发

trunk接口：多个物理交换机上多个VLAN中的帧发送。VLAN中跨交换机进行转发的帧不能够简单地使用802.1帧格式，而是必须携带VLAN ID信息。802.1q协议（VLAN标记协议）可在trunk接口处增加/删除附加的帧的首部字段

6.7 回顾Web页面请求的历程

• 沿着协议向下依次为应用层、传输层、网络层、链路层
• 目标：通过请求www页面场景，识别、回顾、理解协议
• 场景：学生在校园网中用笔记本电脑访问www.google.com并接收信息

Step 1: 计算机连接到Internet

正在连接的笔记本需要获得校园网局域网的IP地址、网关、DNS服务器等信息。

• DHCP请求依次进行UDP封装、IP封装、802.3以太网帧封装
• 以太网向局域网发送广播，由运行DHCP server的网关路由器收到
• 以太帧解封装，IP解封装，UDP解封装，得到DHCP请求
• DHCP server生成DHCP ACK报文，包含客户端IP、掩码、网关、DNS服务器
• DHCP server进行封装，将数据帧通过局域网转发（交换机自学习），在客户端进行解封装
• DHCP client收到DHCP ACK应答，现在学生笔记本拥有了自己的IP地址以及DNS服务器、网关

Step 2: ARP协议获取网关路由器MAC

• 广播发送ARP请求，路由器收到之后发送ARP应答，给出路由器接口的MAC地址
• 客户端知道了网关路由器的MAC地址之后就可以发送包含DNS请求的数据帧了

Step 3: DNS查询

• 将包含DNS查询的IP数据报通过局域网交换机转发到网关路由器
• 校园网的IP数据包路由转发到comcast网络（路由表由RIP、OSPF、IS-IS和/或BGP协议产生的DNS服务器）
• 多路分解到DNS server
• DNS server向客户端发送包含www.google.com的IP的DNS应答

Step 4: TCP连接

• 客户端首先创建到web服务器的TCP套接字
• TCP SYN报文的域间路由到web server
• web server回应TCP SYNACK
• 建立TCP连接

Step 5: HTTP请求与响应

• 将HTTP请求发送到TCP socket
• 包含HTTP请求的IP数据报路由转发到 www.google.com
• web server进行HTTP reply响应，包含web page
• 包含HTTP响应的IP数据报被路由转发回客户端

课后习题和问题

5.2

3. 集中式路由选择算法用完整的、全局性的网络知识计算出从源到目的地之间的最低开销路径，该算法以所有结点之间的连通性以及所有链路的开销为输入。这要求该算法在真正开始计算之前要以某种方式获取这些信息。具有全局状态信息的算法常被称为链路状态算法（LS）。分散式路由选择算法中路由器以迭代、分布式的方式计算出最低开销路径。没有节点拥有关于所有网络链路开销的完整信息。每个节点仅有与其直接相连链路的开销知识即可开始工作。距离向量算法（DV）属于分散式路由选择算法。OSPF协议属于集中式路由选择算法，BGP协议属于分散式路由选择算法。
4. 这两种算法一个是集中式的，另一种是分布式的。
5. 无穷计数问题与DV算法中“坏消息传得慢”这一特性有关。当一条链路的代价增加时，该链路两端的某一个路由器检测到代价增加，开始重新计算其到其他路由器的代价最小路由，但这个计算过程需要使用该路由器之前计算得到的到其他路由器的代价最小路由，而随着这一条链路的代价增加，这些最小路由很可能不再是最小的路由，因此每一次更新只能够将最短路由增加1，从而导致无穷计数问题的产生。无穷计数问题会导致代价增加这个“坏消息”的处理时间大大增加，严重影响到整个网络的性能。
6. 没有必要，不同的AS的内部路由器互相不关联，因此无论当前AS使用什么内部路由选择算法，其对外部的路由器都是透明不可见的。

5.2~5.3

7. 考虑到了以下3点因素：（P263）
   策略。有些AS可能不希望其他AS的流量经过自身，也可能希望经过，但这种策略问题在AS内部选择路由算法中并不重要，强行设计则会增加系统的冗余度。
   规模。在一个AS之内，通常网络的规模不会太大，如果一个AS内的网络规模超出了该AS内部路由选择算法的承载能力，完全可以将这个AS分割为多个AS，并通过AS间路由选择协议进行管理。这使得AS内部路由选择算法没有必要考虑当网络规模特别大时产生的诸多问题。
   性能。在AS之间基本没有与路由相关的开销概念，而在AS内部，一切的路由选择都需要将性能放在至关重要的位置，因此AS间路由选择算法与AS内路由选择算法对于性能的要求不同。
8. 错误，OSPF属于集中式路由选择算法，其自身发送的链路状态信息需要被这个网络中的所有路由器知悉，因此该信息将会在网络中不断传递，直到被所有路由器接收确认为止。
9. 一个区域指的是AS中的一组路由器，一个区域内可以实现自己的OSPF算法，不同区域之间通过边界路由器实现互相通信。引入区域的概念主要是用于构建大型网络，简化路由器中的路由表，并提升路由选择算法的效率。
10. 子网是一个更大的网络中的一部分，一定隶属于某个网络，其不包含路由器，其边界是由路由器和主机接口所定义的。前缀表示的是一个子网或一个子网的集合，是CIDR化的网络部分。CIDR即无类别域间路由选择，是因特网的地址分配策略。BGP路由指的是前缀及其属性。属性包含有AS-PATH、NEXT-HOP等。当路由器通过BGP连接通告前缀时，在前缀中会包括一些BGP属性。
11. NEXT-HOP是AS-PATH起始的路由器接口的IP地址，是BGP要前往的下一个AS中的第一个路由器地址，作用是配置路由表的下一条为NEXT-HOP指向的地址。AS-PATH记录了到目的地的一系列地址前缀，作用有检测环路、多路选择。
12. 如果一个一级ISP不得在另两个ISP（A和B）之间运输中转流量，而该ISP与另外两个ISP有对等传输协议，该ISP只需要不将通过A的路由通知给B，不将通过B的路由通知给A，那么该ISP在A和B看来就是透明的。
13. 错误。有时为了特殊需求，BGP路由器可以选择不将自己的表示添加到已经接受的路径之中，此时该BGP将不会作为中转路由器工作。

5.6

19. ICMP报文有：ping报文（回显报文）、traceroute（目标端口不可达报文、TTL过期报文）、用于拥塞控制的源抑制报文。
20. TTL过期报文和目标端口不可达报文。解释：Traceroute用ICMP报文实现，源主机的数据报中携带了一个具有不可达UDP端口号的UDP报文段，第1个数据报的TTL为1，第2个为2，等等。当TTL为0时，接收到该数据报的路由器应该向源主机发送一个ICMP警告报文给源主机。如果有数据报到达了目的主机，那么该目的主机将向源发送一个端口不可达的ICMP报文，以标志路由探测完毕。

习题

1. y→x→u，y→w→x→u，y→w→v→u，y→w→v→x→u，y→z→w→v→x→u，y→z→w→v→u，y→z→w→x→u等。
2. 略

4. 略
5. DV算法流程：

z表

6. 最大迭代次数为这个网络中最长无环路径的长度，迭代到这个值时网络中所有的路径都能够被遍历到。
7. a. D_x(w)=2，D_x(y)=4，D_x(u)=7。
   b. 若让x通知邻居有一条通往u的新的最低开销路径，则可以将c(x,w)的值增大，只要让c(x,w)+c(w,u)>=c(x,y)+c(y,u)，即c(x,w)>6即可。或者让c(x,y)的值变为1。
   c. 只能让c(x,w)的值增加到7或以上才可以。

初始向量表：
x：

y：

z：

第一次迭代后：
x：

y：

z：

9. 不会。将没有链路的两个节点连接，相当于距离从无穷大降到了有限值。
10. 每一次更新，至少有一个距离向量的某维度的值减小。(假如没有任何距离向量发生改变，更新就停止。)
    由于这些值都是整数、不可能增加、也不可能小于0、所以减小的次数必然是有限的，所以更新也必然是有限的。
11. a. 考虑增加了毒性逆转。y将通知w和z其到x的最短距离为4。z将通知w，其到x的距离为无穷大，因为z此时到x的最短路径是通过w的。另外z通知y其到x的距离为6（因为z只保存了其下一跳，因此并不知道它到x最短路径经过y，因此不发送无穷大）。w通知z其到x的距离为5，通知y其到x的距离为无穷大。
    b. 不能。问题出在z上，因为z和x的最短路径经过了y，z却告知y的Dz(x)=6（这是毒性逆转作用不到的地方），y就会把Dy(x)更新成9（实际上并不是）,然后陷入了无穷计数。
    c. 设置为无穷大即可。
12. BGP是ISP之间的路由选择，如果在寻路时发现了自己所在ISP的路由器，则说明产生了环路。
13. 不是。路由器将偏向于本地偏好值。
14. a. 路由器3c从eBGP中学习到了前缀x，因为其与AS4直接相连。
    b. 路由器3a从iBGP学习到前缀x，其需要通过iBGP与3c通信。
    c. 路由器1c从eBGP学习到前缀x。
    d. 路由器1d从iBGP学习到。
15. a. I₁，距离1c更近。
    b. I₂，根据热土豆路由选择算法其距离2a更近。
    c. I₁，这样AS-PATH更短。
16. 考虑到B将流量传给C的西海岸路由器，因此为了减少西海岸路由器的负担，C可以只告诉D它的东海岸路由器。
17. 因为B不希望C通过它自身转发分组，因此B和C的这条链路对于w是不可见的。同理x为了不想通过自身转发C和B之间的分组，不会告诉B自己与C连接，因此C和w的这条链路对于w也不可见。同理，为了不让x经过自己转发到w的流量，C到A的链路对于x不可见，且C到B的链路对于x不可见。
18. BitTorrent
19. A会向B通告其有到w的路由，不会向c通告，A会向B和C通告有到v的路由。
20. 不允许。
21. 略
22. 略

课后习题和问题

4.1

1. 网络层的分组名为数据报，路由器能够在网络层处理数据报，而链路层交换机只能在链路层处理链路层帧。
2. 数据平面的主要功能是转发和路由，控制平面的主要功能是连接建立。
3. 路由选择指的是路由器指定一条到目的主机的路由的过程，转发指的是路由器内部将输入端口的分组正确转移到指定的输出端口。
4. 转发表中保存了若干个<目标，端口>数据对，便于路由器根据这些数据确定需要将数据报转发到哪一个端口。
5. 因特网的网络层提供单一的服务，称为尽力而为服务。传送的分组既不能保证以它们发送的顺序被接收，也不能保证它们最终交付；既不能保证端到端时延，也不能保证有最小的带宽。

4.2

6. 输入端口、输出端口、交换端口由硬件实现，其数据表处理功能比软件快很多；路由选择处理器由软件实现，维护路由表以及其他的路由信息，并计算转发表。数据平面使用硬件实现，控制平面使用软件实现。
7. 在高速路由器的输入端口存储转发表的副本可以大大减少路由器进行路由选择的时间，无需每一次都计算一次路径。转发决策能在每个输入端口本地做出，无须基于每个分组调用集中式路由选择处理器，因此避免了集中式处理的瓶颈。
8. 基于目的地转发意味着路由器仅会根据数据报的目的IP地址来决定转发端口，通用转发除了数据报的最终目的地之外还有其他的影响因素，如转发决策可以基于数据报的TCP/UDP源端口号和目的端口号进行转发。
9. 使用最长前缀匹配原则来确定应该转发到哪一个端口。
10. 经过内存交换：在输入端口与输出端口之间的交换是在CPU的直接控制之下完成的，一个分组到达一个输入端口时，该端口会通过中断方式向路由选择处理器发出信号，该分组从输入端口处被复制到处理器内存中，理由选择处理器提取目的地址，在转发表中查找到适当的转发端口，并将该分组复制到输出端口的缓存中。
    经过总线交换：输入端口经过一条共享总线将分组直接传送到输出端口，不需要路由选择处理器的干预。让输入端口为分组预先计划一个交换机内部标签，指示本地输出端口，使分组在总线上传送和传输到输出端口。该分组能够由所有输出端口收到，但只有与该标签匹配的端口才能保存该分组。
    经互联网络交换：使用一个更为复杂的互联网络，如纵横式交换机结构，每条垂直的总线在交叉点与每条水平的总线交叉，交叉点通过交换结构控制器能够在任何时候开启和闭合。当分组到达端口A需要转发到Y时，交换机控制器闭合A和Y总线交叉部分的交叉点，然后即可转发。只有互联网络交换可以并行交换多个分组。
11. 如果数据报到达的速率大于数据报处理的速率，当输入端口的数据报缓存满时，后面到达的数据报就可能会丢失。加快路由器处理器的处理速率即可消除排队。
12. 如果数据报被大量送入输入端口，速率大于转发速率时，会导致输出端口排队，到达一定程度后出现丢失。无法防止这种丢失。
13. HOL阻塞，即线头阻塞，即在一个输入端口的缓存中，后面的分组由于前面的分组等待转移到输出端口而产生等待时延的现象，又称线路前部阻塞。出现于输入端口。
14. FIFO
15. 不同的数据报中的数据的重要程度不同，对时延的要求也不同，因此需要为分组设置优先权。
16. RR指循环排队原则，WFQ指加权公平排队原则，二者的基本差异是RR将所有类通信都一视同仁地看待，而WFQ则将通信分为多个不同优先权的分组，优先权表现在一个循环周期内某一类分组处理的时间比例。当WFQ中所有类具有相同的服务权重时，与RR相同。

4.3

17. IP数据报首部中含有上层协议字段，可用于标识上层协议。
18. TTL（time to live），每一次转发都会减1，当该值被减为0时即丢弃。
19. 不用，IP数据报只检验其头部信息。
20. 当数据报中数据部分的长度大于MTU，即链路的最大传送单元时，需要对数据报进行分割，较小的数据报在最终目的主机装配。
21. 路由器有IP地址，有多个IP地址，数量等于其有效接口数量。
22. 11011111 00000001 00000011 00011011
23. 略
24. 8个接口，3个
25. IP数据报头部20字节，TCP报文段头部20字节，一个数据报中头部信息占40字节，还有40字节为数据，因此开销为50%，即发送的内容只有1-50%是有效数据，应用数据所占百分比为50%
26. 通过路由器的DHCP服务器为5台PC分配IP地址，该无线路由器使用NAT，因为ISP只给了它一个IP地址，它必须自己构建一个局域网。
27. 路由聚合指使用单个网络前缀通告多个网络的能力，其使用一个具有公共前缀的地址来汇聚许多的子网。
28. 能够自动配置主机的IP地址。
29. 专用网络地址指在各个子网中可以重复使用的网络IP地址。具有专用网络地址的数据报不会出现在大型公共因特网中，否则数据报将无法确定到底应该发送到哪一台主机。
30. 有，如源IP和目的IP。
31. 是，因为IPv6载荷包裹在IPv4数据报中。

习题

1. a. 路由器A的转发表：其中1项的目的地址为H3，转发端口为3。
   b. 无法实现，因为路由器转发仅根据目的地址转发，而不根据数据来源转发。
2. a. 不能，因为交换结构是共享总线时，一次只能转发一个分组。
   b. 不能，因为交换结构是内存交换时，一次也只能转发一个分组。
   c. 不能，因为两个分组转发到相同的输出端口，交换结构为纵横式时，允许不同端口同时转发不同分组，但一个端口在一个时刻不能同时转发多个分组。
3. 内存和总线交换结构：每一次只能转发一个分组，因此最大时延为(n-1)D。纵横式：不同端口的输出可以交互进行，因此最大时延为0。
4. 在第一个时隙，第一个输入端口的X分组到达X输出端口，另外剩余两个端口的最前两个Y分组选择一个到达Y输出端口，之后的分组还需要两个时隙完成传输，故最少需要3个时隙。最大也是3个时隙。
5. a.
   目的地址为192.0.0.0/10时输出到0端口，前缀11100000 00
   目的地址为192.64.0.0/16时输出到1端口，前缀11100000 01000000
   目的地址为192.0.0.0/7且不属于端口0、1的地址范围时输出到2端口，前缀1110000
   其余输出到3端口
   b. 第一个地址根据最长前缀匹配原则匹配到其他，输出到3端口
   第二个地址可匹配端口2，且不匹配端口0、1，输出到2端口
   第三个地址匹配到其他，输出到3端口
6. 首先看前缀长的。
   接口1前缀010，匹配64~95，地址数量为32。
   接口2前缀011，匹配96~127，地址数量为32。
   接口0前缀00，匹配0~63，地址数量为64。
   接口2前缀10，匹配128~191，地址数量为64。
   接口2可匹配96~191，地址数量为96。
   接口3前缀11，匹配192~255，地址数量为64。
7. 首先看前缀长的。
   接口2前缀111，匹配224~255，地址数量为32。
   接口1前缀10，匹配128~191，地址数量为64。
   接口0前缀1，匹配192~223，地址数量为32。
   接口3匹配0~127，地址数量为128。
8. 首先分配需求大的子网，子网2分配一个25地址，即223.1.17.0/25，子网1分配一个26地址，即223.1.17.128/26，子网3分配剩余地址，即223.1.17.192/26。
9. 略

244.0.0.0/10 → 端口0
224.64.0.0/16 → 端口1
224.0.0.0/7 → 端口2
0.0.0.0/0 → 端口3

11. 128.119.40.(64\80\96\112)/28
12. 子网1：214.97.254.0/24
    子网2：214.97.255.0/25 - 214.97.255.0/29
    子网3：214.97.255.128/25
    子网4：214.97.255.0/31
    子网5：214.97.255.2/31
    子网6：214.97.255.4/30
13. 略
14. 将会产生4个分片，表示均为422，偏移分别为0、85、170、255，前3个分片的MF为1，数据量700字节，最后一个为0，数据量300字节。
15. 5MB=5×10⁶字节，首部字段的长度为40字节（含IP首部和TCP首部），故每个数据报最大数据量为1460字节，需要将5MB分为3425个数据报。
16. a. 192.168.1.1~192.168.1.3
    b. 源IP地址：192.168.1.1，端口3345；转换IP地址：24.34.112.235，端口4000。其余5个类似。
17. a. 通过标识号识别，由于每一台主机的标识号都是连号的，可以将所有的分组编号提取出来，检测其中连号或单号的数量，可以大致检测出主机的数量，通过这样的方式检测出的主机数量不会大于实际的主机数量，因为不同主机在不同的时间段可能会使用同一个编号。
    b. 不能。这样就无法通过标识号的规律对数据报进行源关联。
18. 不可能设计这种技术。TCP首先需要创建一个连接，一方通过NAT地址转换可以找到另一方NAT的网关，但不能定位到NAT内部子网的另一方。
19. 略
20. 略
21. 略
22. 略

Chapter 4 网络层——数据平面

4.1 网络层概述

网络层的任务：完成主机到主机之间的通信

网络层是五层架构中的第三层，为运输层（进程之间的通信）提供支持。

为实现从源主机到目标主机成功的移动数据分组，整个路径上每一台分组交换机上均需要实现网络层，才能实现通信。

网络层功能：

• 在全局范围内对主机通信进行选路，结果反映为分组交换机上的转发表（理解为每一台设备尝试获取整个网络的拓扑结构，控制层面）
• 分组交换机上的网络层根据转发表以及分组头部信息，将分组向合适的链路进行转发（数据层面）
• 对于面向连接的网络层服务，提供连接建立的功能

分组交换机分类：

• 根据链路层首部信息进行转发的——链路层结点交换机
• 根据网络层首部信息进行转发的——路由器

注意：链路层结点交换机和路由器的区别的理解：链路层在网络层之下，通过以太网（Ethernet）协议工作，链路层结点交换机根据MAC地址找到主机，而路由器通过IP地址找到主机。在一个内网之中，可能存在有多个交换机，交换机在内网主机之间的通信效率高于路由器（主机与路由器直接相连也可以实现交换机的功能，但效率不如交换机）。参考路由器与交换机的区别与联系_WhataNerd的博客-CSDN博客_交换机和路由器的区别

网络层可能提供的服务：

• 确保交付：确保分组最终到达目的地（与以太网协议不同，以太网协议为尽力传输）
• 具有时延上界的确保交付：在时延上限以内交付
• 有序分组交付：以发送顺序到达
• 确保最小带宽：以低于特定比特率速率传输时分组不会丢失而且在时延内可达
• 确保最大时延抖动：连续分组间隔时间不超过特定值
• 安全性服务：机密性、完整性和源鉴别（如TLS）

网络层提供的服务可以分为：（下面两种只能提供一种，而运输层可通知提供两种）

• 面向有连接的服务：虚电路，需要事先握手
• 面向无连接的服务：数据报，不需事先握手

网络层与运输层中相应服务的区别：

• 网络层是向运输层提供主机到主机的服务，而运输层是向应用层提供进程到进程的服务。
• 网络层仅提供上述两种服务中的一种，不同时提供两种，而运输层则同时提供两种。
• 运输层的服务在网络边缘的端系统中实现，而网络层的服务则在整个网络中实现，含路由器。

虚电路网络

虚电路的目标是使首发双方之间的路径表现得如同电话线路一般。
工作机制：

• 数据开始流动之前，呼叫建立，流动结束后要断开
• 每一个分组携带虚电路的标识（而不是目的主机的地址）
• 路径上的每一个路由器必须为进行中的连接维持连接状态信息
• 链路，路由器资源可以分配给虚电路，为了达到类似线路交换的性能

虚电路的组成：

• 从源到目的主机的路径，含有一系列链路和路由器
• VC号，沿着该路径的每段链路的一个号码
  • 一条虚电路在每条链路上具有不同的VC号
  • 每台中间路由器必须用一个新的VC号替代每个传输分组的VC号
• 沿着该路径的每台路由器中的转发表
  • 创建一条新的虚电路，转发表增加一个新表项
  • 终止一条虚电路，表中相应项被删除

数据报网络

数据报网络在网络层没有连接建立过程。路由器在端到端的连接中不维护连接状态信息（在网络层不存在“连接”的概念）。传输报文时使用目的主机地址信息，同一对主机之间的报文可能会走不同的路径。

虚电路网络与数据报网络的对比：虚电路网络将重点放在网络，数据报网络将重点放在终端。数据报网络互联不同类型的网络更加容易，启用新服务的速度更快更简单。

4.2 路由器工作原理

路由器关键组成：

• 运行路由算法/协议（如RIP选路算法）
• 从入口到出口的转发

路由器的分散式交换：

• 按照给定的目标地址，使用输入端口内存中存储的路由表，查找输出端口
• 路由器需要以“线路速度”完成输入输出端口的处理
• 如果数据报到达的速度超过了输入输出端口将数据报转交给交换结构的速度，则会产生排队现象。
  • 基于目标的转发：仅基于目标IP地址的转发，以最长前缀匹配方法确定向何处转发。
  • 通用转发：基于任意首部字段值转发

输入端口

输入端口排队：

• 输入端口处理速率超过交换结构速率时产生
• 当输入缓冲区溢出时可能会导致排队丢包和时延
• 线头阻塞：在输入队列中排队的分组必须等待通过交换结构发送，因为它被位于线头的另一个分组阻塞了。

交换结构工作原理：

• 经总线交换：输入端口通过一根共享总线直接传送到输出端口，缺点是总线的带宽是交换速度的瓶颈。一次处理一个分组。
• 经内联网络：将长度变化的IP分组分片为固定尺寸的信元，通过交换结构对信元进行转发。克服了总线带宽的限制。
• 经内存交换：在输入端口和输出端口之间的交换是在CPU的直接控制下完成的。分组被拷贝到系统内存中，CPU提出报头中的目标地址，查找路由表中的输出接口，将数据包拷贝到输出接口。其转发速度受限于内存的带宽（吞吐量<带宽/2），一次转发一个分组。

输出端口

输出端口需要缓存管理和调度原则。当交换结构将分组交付给输出端口的速率超过输出链路速率时进行缓存管理，在数据报队列中选择数据报进行传输时需要调度原则。

输出端口排队：

• 当通过交换结构到达的分组速率超过输出链路速率时产生。
• 需要对分组进行缓存，超过缓存缓冲区大小会造成排队和丢包。

拥塞问题的解决方法

缓冲区设置问题：

• 经过试验认为对于有N条TCP连接经过的链路而言，缓冲区大小应为：$$B=\frac{\operatorname{RTT}\times R}{\sqrt{N}}$$其中R为带宽，RTT为往返时间。

输出端口分组调度策略：

• 先来先服务策略（First Come First Serve，FIFO的队列策略）
  • 当缓冲区满时，有几种丢弃方法：
    • 尾部丢弃
    • 按照优先级丢弃
    • 随机丢弃
• 优先级排队策略
  • 针对高优先级和低优先级的数据报创建多个不同队列
• 循环调度策略
  • 循环扫描不同类的队列，轮流发送数据包
• 加权公平队列策略
  • 每一个类赋予对应的权重，在一个周期之内可以获得一定数量的服务，既可以保证高优先级队列获得最大优先权，又可以防止低优先级队列等待时间过长。

分组丢弃策略

• 被动策略
  • 丢弃尾部
  • 随机丢弃已排队分组
• 主动策略
  • 随时计算平均队列长度，并设置一个最小和最大阈值。
  • 当队列长度小于最小阈值时，无条件允许分组入队列。
  • 当队列长度大于最大阈值时，无条件禁止分组入队列。
  • 当队列长度在两个阈值之间时，按照概率标记或丢弃分组。

4.3 网际协议

IPv4协议数据报格式：

IP分片和重组

MTU：最大传送单元，一个网络层数据包的最大长度（包含网络层协议头）

受限于MTU，大的数据包在一些链路中会被拆分为多个数据包。网络中的交换机都有可能会拆分数据包，但只有目标主机会对数据包进行重组，具有较大MTU的链路即使接收到小数据包也不会进行重组。 重组后由于数据包头部数量增加，因此总的传输的字节数量会增加。

IP地址

• 结构：网络号（子网号）+主机号，在同一个网络下的主机和路由器的IP地址中的网络号必须相同，同一网络下的主机可以直接通信。
• 接口：连接主机、路由器之间的物理链路，一般路由器有多个接口，主机也有可能有多个接口，IP地址只和接口有关而与主机、路由器没有太多关联。
• 传统形式下的IP地址分类：
  • A类：0.0.0.0~127.255.255.255，网络号7位，主机号24位
  • B类：128.0.0.0~191.255.255.255，网络号14位，主机号16位
  • C类：192.0.0.0~223.255.255.255，网络号21位，主机号8位
  • D类：224.0.0.0~239.255.255.255，组播地址
  • E类：240.0.0.0~255.255.255.255，保留
• 路由器的IP地址：为完成分组转发功能，路由器至少拥有两个IP地址，接入不同的子网之中，用于不同子网之间的通信。
• 子网划分方法：在主机号中借用一部分位数作为子网号
• 子网掩码：对内用于指示网络号和子网号的位置，对外可以隐藏子网的存在。获得方法：通过在网络号的子网号相应的位置全部置为1，主机号相应的位置全部置为0，即可得到子网掩码。
• 在同一个局域网上的主机或路由器的IP地址中的网络号必须是一样的，图中的网络号就是IP地址中的net-id。路由器总是具有两个或两个以上的IP地址，路由器的每一个接口都有一个不同网络号的IP地址。

IPv4编址

网络地址=IP地址 逻辑与 子网掩码。
采用子网掩码之后，路由器的寻址过程将演变为一个两级寻址过程：

• 检查分组目的IP地址中的网络号，若网络号不是本网络，则从路由表中找出相应的的转发节点地址将其转发出去。
• 检查子网号：当网络号是本网络时，路由器将检查子网号，向相应的子网转发此分组。

IP地址扩展：构造超网，从网络号中借用一部分位数作为主机号。

CIDR

无类别域间路由选择。应用于地址空间的利用率低，地址空间面临耗尽时。

编址格式：IP地址::={网络前缀，主机号}
斜线记法：192.168.0.1/24
简写记法：10.0.0.0/10可以简写为10/10

最长前缀匹配：

• 使用CIDR时，路由表中的每一个项目由“网络前缀”和“下一条地址”组成，在查找路由表时可能会得到不止一个匹配结果。
• 应当从匹配结果中选择具有最长网络前缀的路由：最长前缀匹配。
• 网络前缀越长，其地址块就越小，因而路由就越具体。
• 最长前缀匹配又被称为最长匹配或最佳匹配。

主机获得IP地址的方法：手工配置，或使用DHCP协议动态获取。

DHCP：动态主机配置协议

允许主机在加入网络时动态地从网络服务器中获取其网络地址。

• 能够在使用过程中更新地址
• 允许地址重用
• 支持移动用户

主要流程

• 主机广播DHCP发现报文。
• DHCP服务器使用“DHCP提供”报文进行应答（广播方式，由于现在主机还没有获取IP地址，因此只能广播）。
• 主机使用DHCP请求报文请求IP地址。
• DHCP服务器使用DHCP ACK报文响应。

DHCP除了可以获取IP地址，还可以获取网关地址、DNS地址、子网掩码。其工作在应用层，是引导程序协议的一种，属于局域网的网络协议，使用UDP协议工作。
DHCP有3个端口，67和68作为正常的DHCP服务端口，分别是服务器和客户端的服务端口，546号端口用于DHCPv6客户端，这是为了特别开启DHCP failover服务。

网络地址转换（NAT）

其目的是让本地网络只使用一个IP地址就可以和外部网络相连，且不需要从ISP获取大批的IP地址，所有的设备可以使用同一个IP地址，可以在不通知外部网络的情况下改变内网主机的IP地址，即使改变了ISP也无需改变内网主机的IP地址，且内网主机对于外网主机是不可见的，不可寻址的。

实现方法：

• 发送数据报：将每个外出报文的源IP地址和端口号替换为NAT的IP地址以及新的端口号，远程客户机或服务器将以NAT IP地址以及新的端口号作为目的地址进行响应。
• 网关存储每一个地址转换对，在接收数据报时根据NAT转换表将每一个进入报文的NAT IP地址和端口号替换为相应的源IP地址以及端口号。

三种地址转换方式：

• 静态NAT：一个本地地址对应于一个全球地址
• 动态NAT：一个全球地址对应于多个本地地址
• 端口NAT：一个本地地址的端口对应到一个全球地址的端口

争议：

• 端口号是用于进程编址而不是用于主机编址的
• 路由器仅应当处理高达第三层的分组
• NAT协议违反了端到端原则，即主机彼此应当相互直接对话，结点不应该介入。
• 应该使用IPv6来解决IP地址的短缺问题

ICMP：因特网控制报文协议

用于主机、路由器、网关之间交换网络层信息，其传递的信息包括：

• 错误报告，如主机、网络、端口、协议不可达等
• 回声请求/回答，如ping

从体系结构上看其位于IP层之上，被封装在IP分组中。报文种类有两种：ICMP差错报告报文和询问报文。

5.2 路由选择算法

默认路由器：一台主机直接连接到的路由器
源路由器：源主机的默认路由器
目的路由器：目的主机的默认路由器

选路算法的目的：

• 给定一组路由器以及连接路由器的链路，从中找到一条从源路由器到目标路由器的“好的”路径，这条路径通常需要拥有最低的成本。

选路算法分类：

• 根据信息是全局性还是分散性的进行分类
  • 全局选路算法
    • 所有路由器都知道整个网络的拓扑图以及链路的费用信息
    • 链路状态算法
  • 分散式选路算法
    • 每一个路由器仅有与其相连的链路的费用信息
    • 通过迭代计算过程与相邻结点交换信息
    • 距离向量算法
• 根据信息是静态还是动态进行分类
  • 静态选路算法
    • 随着时间的流逝，路由的变化很慢
  • 动态选路算法
    • 路由信息可以很快地发生变化
    • 需要对路由信息进行周期性的更新
    • 可以相应拓扑或链路费用的变化
• 根据是否对负载敏感进行分类
  • 负载敏感算法
    • 链路费用会动态地变化以反映出链路的当前状况
  • 负载迟钝算法
    • 链路费用不明显地反映链路的当前状况

Dijkstra算法

条件：

• 所有结点都知道网络拓扑和链路费用
  • 通过链路状态广播获得信息
  • 所有结点具有该网络的同一个完整的视图
• 计算从某结点到网络中所有其他结点的最低费用
  • 为该结点提供转发表
• 迭代：经过算法的K次迭代之后，可以知道到K个目的节点的最低费用路径。
• 通过跟踪前一跳结点可以构造最短路径树。

复杂性：

• 对于第一次迭代，需要搜索所有的n个结点以确定出结点w，w具有最低费用
• 在所有迭代中需要搜索的结点总数为n(n+1)/2，所以链路状态算法在最差情况下的复杂性为O(n²)
• 该算法的一种更复杂的实现（堆）可以降到O(nlogn)

缺点：当路径的价值在不断变化时，每一次都需要重新进行计算，耗费资源。
解决方案：

• 强制链路费用不依赖于所承载的流量，但这无法解决高拥塞的问题
• 确保并非所有的路由器同时运行LS算法（链路状态路由选择算法），这样因特网上的路由器能够自同步，随机化路由器发送链路通告的时间。

5.3 OSPF协议

OSPF协议是公开发表的，用于因特网中自治系统内部的路由选择。
最短路径优先是因为使用了Dijkstra提出的最短路径算法SPF。这是一个分布式的链路状态协议。

链路状态在路由器之间交流使用的方法：洪泛法，其向本自治系统中所有路由器发送信息，发送的信息就是与本路由器相邻的所有路由器的链路状态。只有当链路状态发生变化时，路由器采用洪泛法向所有路由器发送此信息。

由于各个路由器之间频繁交换链路状态信息，所有的路由器最终都能够建立一个链路状态数据库。这个数据库实际上描述了全网的拓扑结构图，在全网范围是一致的。OSPF的链路状态数据能够较快地进行更新，使得各个路由器能够及时更新其路由表。OSPF的更新过程收敛快就是其重要优点。

OSPF协议特点：

• 不强制如何设置链路权值的策略，但是提供对给定链路权值集合确定最低费用路径的机制。
• 即使链路状态未发生变化，每30分钟广播一次链路状态。
• 链路状态以OSPF通告形式封装于OSPF报文中，由IP分组承载，协议号89。
• OSPF路由器之间的交换都是经过鉴别的，以确认OSPF通告的真实性以防止伪造和篡改。
• OSPF通告具有序列号，可防止重放攻击。
• OSPF中支持多条具有相同费用的路径。
• OSPF支持多播选路和层次路由。

OSPF距离向量选路算法

特点：迭代、分布、自我终止、异步
思想：

• d_x(y)=min_v{c(x, v)+d_v(y)}
• 每一个路由器中都有一张路由表，包含3个内容：目的网络号、经过的邻居路由器、距离
• 路由器定期向其邻居路由器传送路由表的拷贝

路由表更新算法：将每条边的权值都定义为1

• 路由器X得到相邻路由器Y的路由表，从而得知：Y到网络Z的最短距离为N
• 如果路由器X没有到网络Z的路由条目，则添加一条经由路由器Y到网络Z距离为N+1的路由条目
• 如果路由器X已经有到网络Z的路由条目，其距离为M，如果M>N+1，则更新该条目为经由路由器Y到网络Z距离为N+1，否则不更新。
• 特点：
  • 好消息传播快，每一次发现距离更新的路径，都能够很快通知到邻居：
    • 在t0时刻，y检测到链路费用变化，更新自己的距离向量，同时将这个变化通知给它的邻居
    • 在t1时刻，z收到来自y的更新报文并更新了自己的距离向量表，计算出到x的新的最低费用，并向邻居发送它的新距离向量
    • 在t2时刻，y收到来自z的更新并更新其距离向量表，Y的最低费用不变，因此y不发送任何报文给z。
  • 坏消息传播慢，如果一条链路的权值增大，每一次更新只能让链路最短距离增加1，这会导致路由选择环路（P252）。解决方案：毒性逆转，即如果z通过y选路到达目的地x，则z通告y其到x的距离为无穷大，这样在比较时不会产生上述情况，但仍然没有解决不可记数问题。涉及3个或更多结点的环路将无法使用毒性逆转技术检测到。

链路状态路由选择算法LS & 距离向量路由选择算法DV

• 从报文的复杂性来看：
  • LS：对于n个结点和E条链路，需要发送O(nE)个报文
  • DV：只对直连的邻居发送报文
• 从收敛速度来看：
  • 算法收敛时间依赖于许多因素，因此可变
  • LS：是一个要求O(nE)个报文的O(n²)算法，可能会存在震荡
  • DV：收敛时间不确定。可能会遇到环路选路和无穷记数问题
• 从健壮性来看：
  • LS：结点能够向其连接的链路广播不正确费用，每一个结点只计算自己的转发表
  • DV：一个结点可以向任意或所有目的结点通告其不正确的最低费用路径，每一个结点的计算都会传递给它的邻居

RIP协议

• 相邻两点间链路上的费用定义为1，即只考虑源到目标经过多少个路由器，或多少“跳”
• 一条路径的最大费用限制为15
• 选路更新信息每30s在邻居之间以RIP响应报文的形式进行交换
• 路由器经过180s没有收到来自某个邻居的RIP通告，则认为该邻居已经离线，修改选路表，向其他邻居广播
• RIP是一个运行在UDP上的应用层协议（端口520）

层次路由

当因特网规模过大时，路由器无法存储每一台主机的选路信息，路由表更新的报文广播太多占用带宽。另外路由器也需要有一个子网管理的功能，每个网络管理员可能希望能够按照自己的愿望进行管理其网络。

解决方法：

• 将路由器聚合到一个区域，形成一个自治系统（AS）
• 在相同AS内的路由器可以全部运行同样的选路算法：自治系统内部选路协议，最常用的是内部网关协议IGP，包含RIP和OSPF
• 在不同AS内的路由器可以运行不同的自治系统内部选路协议
• 转发表是由AS内部选路算法与AS间选路算法共同决定的，AS内部选路算法为内部目的地址设置转发表信息，AS内部选路算法与AS外部选路算法共同为外部目的地址设置转发表信息

自治系统间路由器的任务：
需要知道自己所在AS通过某个相邻的AS能够到达哪些AS，并将这些可达性信息向自身AS中的所有路由器传播。

当从源到目标在AS粒度下只有一条路可选时，源知道其哪一个接口在到AS边缘路由器的最低费用路径上，因此将接口与目标作为一对放入转发表。如果不止一条路可选，那么源必须确定通过哪一个网关路由器转发报文，其策略是将报文发送到最近的路由器，即热土豆选路原则

因特网中的AS内层次路由：层次OSPF

• 为了使得OSPF能够用于规模更大的网络，OSPF将一个自治系统再划分为若干个更小的范围，称为区域
• 每一个区域都有一个32bit的区域标识符
• 区域不能太大，一个区域内最好不要有200个以上路由器
• 划分区域的好处就是将利用洪泛法交换链路状态信息的范围局限于每一个区域而不是整个自治系统，这就减少了整个网络上的通信量。
• 在一个区域内部的路由器只知道本区域的完整网络拓扑，而不知道其他区域内的网络拓扑的情况。
• OSPF使用层次结构的区域划分。在上层的区域叫做主干区域。主干区域的标识符规定为0.0.0.0，主干区域的作用是用于连通其他在下层的区域。

因特网上的AS间路由：BGP4

• 在自治系统之间寻找最佳路由的代价很大，不现实，因此需要考虑有关策略。
• BGP为每一个AS提供一种手段，来处理
  • 从相邻AS获取子网可达性信息
  • 向该AS内部所有路由器传播这些可达性信息
  • 基于该可达性信息和AS策略，决定达到子网的好路由
  • 注意BGP只是寻找一个较好的路由，而不一定是最好的路由

每一个自治系统的管理员要选择至少一个路由器作为该自治系统的BGP发言人，一般两个发言人都是通过一个共享网络连接在一起的，而BGP发言人往往是BGP边界路由器，但也可以不是。

一个BGP发言人与其他自治系统中的BGP发言人交换路由信息，首先需要建立TCP连接，然后在此连接基础上交换BGP报文以建立BGP会话，利用BGP会话交换路由信息

使用TCP连接能够提供可靠服务，也简化了路由选择协议。

使用TCP连接交换路由信息的两个发言人彼此成为对方的邻站或对等站。

• BGP路由通告
  • 一个AS可以集合多个前缀为一个，并使用BGP向其他AS通告单一前缀，则当前AS承诺它将沿着朝向该前缀的路径，转发指向该前缀的任何数据报。
• 选路算法
  • 在不同AS的网关路由器之间使用eBGP，一个AS向另一个AS发送一个自其自身可达的前缀列表。
  • 而另一个AS的网关路由器使用iBGP对话向该AS中的其他路由器发布这些前缀。
  • 这个AS内的其他网关路由器使用eBGP会话将学习到的前缀信息发布到与其直接相连的其他AS的网关路由器中。
  • 当一个路由器得知一个新的前缀，它为该前缀在其转发表中创建一个表项。
• 路径和BGP路由
  • 当路由器通告一个前缀时，它随着前缀包含一些BGP属性，前缀+属性=路由。
  • 两个重要属性：
    • AS_PATH：该属性包含了前缀的通告已经通过的那些AS
    • NEXT_HOP：指明到下一跳AS的具体的路由器（从当前AS到下一跳AS之间可能有多条链路）
  • 当一台网关路由器接收到一个路由器通告时，它使用输入策略决定是否接收或过滤该路由。
• BGP路由选择
  • 一台路由器可能知道到一条前缀的多条路由路，路由器必须在可能的路由之中选择一条。消除规则：
    • 本地偏好值：策略决定，具有最高本地偏好值的路由将被选择
    • 最短AS-PATH：在余下的路由之中，具有最短AS-PATH的路由将被选择
    • 从余下的路由中，选择具有最靠近NEXT-HOP路由器的路由：热土豆路由。
    • 如果依然剩下多条路由，该路由器使用BGP标识来选择路由

步骤：

• 路由器知晓前缀的存在性：通过BGP通告得知
• 确定此前缀的转发端口：使用BGP路由选择确定最佳域间路由，使用IGP路由选择确定最佳域内路由，确定最佳路由的转发端口
• 将（前缀，端口）表项放入转发表中

IP组播

组播：将数据分发给网络中处于同一个组的多台主机上的应用进程。

5.5 SDN

传统网络的问题：

• 各个设备厂家网络层实现的方式各不相同，架构封闭，导致接口模糊封闭，功能单元界面不清晰。封闭架构导致设备制造商对新技术的驱动力不强，协议更新慢。

路由器实现的控制平面：每一个路由器都具备独立的路由功能和数据转发功能，路由算法组件分布在不同的路由器上，彼此交互，计算生成转发表，构成分布式的控制平面。

实现目标：

• 确定性路由：从固定源到固定目标要求经过固定的路由
• 负载均衡路由：从源到目标的多条路径上实现负载均衡

解决方案：分层
路由控制功能从本地路由器分离，汇聚到远程控制器，与路由器中的本地控制代理进行交互，来计算转发表。

SDN架构包含数据平面与控制平面，数据平面负责处理和转发数据包，根据转发状态和数据报头决定转发决策，而控制平面负责计算路由器的转发状态，确定数据报应该如何转发和转发到哪里，对路由、流量工程和防火墙状态管理控制，实现分布路由协议、手工配置或集中计算。不同的平面需要分别进行抽象，以满足SDN需求。

OpenFlow流表

由多个流条目组成，流条目包括：

• 头域：用于匹配规则确定输入报文是否与本条目匹配

• 计数器：用于与本流相关的跟踪统计

• 动作：描述交换机针对匹配报文采取的动作

• OpenFlow交换机由OpenFlow协议、安全通道、报文匹配、流表与动作等构成。

• 报文匹配功能基于流表对输入报文进行匹配，将其引导至动作箱。

• 动作包括三种可选动作

  • 转发报文输出，可能先修改头域字段
  • 丢弃报文
  • 通过报文输入消息将报文转发至控制器

• 控制器和交换机之间的报文通过安全通道传输

• 当控制器有报文需要通过交换机输出时采用PACKET_OUT消息

• 控制器直接指定输出端口

• 控制器通过报文匹配逻辑决定转发策略

SDN控制平面：包括SDN控制器和SDN网络控制应用程序。

• 控制平面基于网络的抽象，简化了网络编程控制
• SDN控制平面包括两个层面的抽象：
  • 流抽象-交换机API，通过OpenFlow协议与数据平面交互
  • 映射抽象-网络API，控制器与网络控制应用程序之间交互

课后习题和问题

3.1~3.3

1. 略
2. 略
3. 对于主机B发送到主机A的报文段，源端口号为y，目的端口号为x。
4. UDP的速度快，有些应用如实时视频可能不需要数据完全可靠，不希望受到拥塞控制。
5. 因为语音和图像要求数据可靠准确，而UDP不能保证。标准答案：大多数防火墙被配置为阻止UDP通信，因此使用TCP处理视频和语音通信可以让通信通过防火墙。
6. 可能，需要在应用层设置另外的校验程序，UDP本身是不提供可靠数据传输的。
7. 是。注意UDP数据包中是没有IP地址的，主机C是通过应用中的套接字来确定，在套接字接口处，有操作系统向进程提供IP地址，以确定各个报文段的源。
8. 不同的套接字。对于每一个持久连接，Web服务器都会创建一个单独的“连接套接字”，每一个连接套接字都由一个四元组表示：源IP地址、源端口号、目的IP地址、目的端口号。当主机C接收IP数据报时，检查报文中的这4个字段，以确定将这个数据报上传到哪一个套接字。用于连接两台主机的套接字中都以80作为目的端口。注意当传输层将TCP报文段的有效负载传递给应用程序进程时，不会指定源IP地址，因为这是由套接字标识符隐式指定的，这与UDP不同。可以理解为，TCP会将从不同源发送的报文段分到不同的套接字，因此不需要另外指定源IP。

3.4

9. 标识一个ACK是对应于哪一个报文段的。接收方的确认报文如果在链路中发生了错误，发送方就只能重新发送一次这个报文，但是接收方不知道这个报文是一个新的报文还是上一个报文的重传，因此需要标识。
10. 如果报文丢失，就需要重传报文，设置定时器的目的是防止丢包导致无限等待，在定时器到达一定的时间之后认定为丢包，即直接重传。如果收到了ACK，则重启该定时器。
11. 是，在往返时延固定的情况下，定时器只要检测到在往返时延之内没有接收到希望的ACK报文即可重传报文。
12. 小程序
    a. 毁掉第一个分组之后，会发送4个序号相同的ACK报文，并开启定时器，在一段时间之后发送方重新发送5个报文。这里解释一下，由于第一个报文被毁，因此接收方只能够发送上一次成功接收的序号的ACK，发送方能够收到4个相同序号的ACK，其需要等待一段时间确认第5个ACK是否正在发送，如果能够成功收到第5个报文，则说明发送方发送数据报到接收方时出现了失序，序号最小的数据报反而是最后被接收的；如果计时器结束，就全部进行重传。
    b. 此时窗口会移动，因为发送方接收到了序号更大的ACK，这说明前面的数据报都已经被成功接收，即使第一个ACK丢失也不影响窗口右移。
    c. 无法发送第6个分组，因为窗口大小只有5。
13. 小程序
    选择重传的不同之处在于，其ACK报文与GBN的ACK报文表达的含义不同了，选择重传的ACK报文只能表示该序号的数据报正常接收，而GBN的ACK报文表示该序号及小于该序号的所有数据报均已经被正常接收。因此选择重传只会重传没有收到ACK的序号的数据报，并在窗口的第一个数据报收到时调整窗口的位置，使得窗口的第一个序号永远处于没有被确认的状态。

3.5

14. a. 错误，TCP协议中接收方需要发送确认数据报，与随数据捎带确认没有关系。
    b. 错误，rwnd全称为receive window，即接收窗口，其值等于接收缓存-（接收到的字节数-主机应用进程从缓存读出的字节数），因此该值是一直在动态变化的。
    c. 正确。
    d. 错误，报文段的序号是按照字节编址的，下一个报文段的序号应该等于该报文段的序号+该报文段的长度。
    e. 正确。
    f. 错误。TimeoutInterval = EstimatedRTT + 4 × DevRTT = (1-α) × EstimatedRTT + α × SampleRTT + 4 × ((1-β) × DevRTT + β × |SampleRTT - EstimatedRTT|)，无法推导出该题结论。
    g. 错误，TCP通信双方的序号是各自决定的，因此确认号与序号没有直接的关系。
15. 20字节；90
16. 3个报文段：
    Seq=43, Ack=80
    Seq=80, Ack=44
    Seq=44, Ack=81

3.7

17. R/2，TCP可以通过调度使得链路中多个连接的吞吐量基本公平。
18. 错误，应该被设置为门限值的一半。
19. 略

习题

1. e. 可能相同。
   f. 同一台主机不可能相同。
2. 主机A连接：源端口80，目的端口26145；主机C连接：源端口80，目的端口7532
3. 11010001，接收方将带有反码的4个8比特求和，结果为全1则验证完成。1比特的差错可以出来，但2比特的错误可能不能检测出来。
4. a. 00111110
   b. 10111111
   c. 将最低位的0改成1，1改成0。
5. 不能绝对确信。
6. 在发送方发送分组1时，接收方接收完成并发送一个ACK，但ACK损坏，发送方收到损坏的ACK之后重传分组1，但接收方要的不是分组1，因此会返回NAK，发送方误以为分组1传输错误就会继续重传，由此陷入死锁状态。
7. 不理解题意。
8. 与rdt2.2的FSM相同
9. 略
10. 
    需要将计时器设置为最大往返时延与处理时间之和，每一次发送新的数据分组时重启计时器。
11. 不能正常工作。如果在收到重复的数据包或数据包损坏的情况下不发送数据包，那么发送方就永远无法收到来自接收方的任何确认信息，就会一直等待下去，进入死锁的状态。注意rdt 3.0之前的所有版本都是没有计时器的。
12. 仅有一个比特差错时，能够正常运行。如果定时器过早超时，那么对于序号为n的分组将会重传n次。流程：发送1分组，在ACK1被接收前计时器超时，重传1次1分组，然后接收到1ACK，发送2分组，在ACK2被接收前计时器超时，重传1次2分组，然后接收到来自第1次重传1分组的ACK1回应，第2次重传2分组，然后收到ACK2，发送3分组，超时第一次重传3分组，接收到两次2分组重传的回应ACK2，再重传2次3分组……可以发现1分组重传了1次，2分组重传了2次，……n分组将会重传n次。
13. 如果能够重排报文顺序，首先发送老1分组，回应的老ACK1迟迟未到，重传1次老1分组，收到ACK1，然后发送0分组，接收方接收到0分组之后发送1个0分组ACK，此时链路中有1个ACK0和1个ACK1，且ACK1是先进入链路的，但如果ACK0首先被收到，那么会发送新1分组，如果此时接收到ACK1分组，注意这个分组确认的是老1分组，那么发送方就会误以为新1分组已经被收到，会继续发送新0分组，如果新1分组没能被收到，那么接收方就会产生错误，迟迟无法收到新1分组。
14. 不会，因为如果只使用NAK，当发送方发送数据的频率较低时，如果编号为x的数据包没能成功接收，那么接收方只有在接收到编号为x+1的数据包时才能察觉到编号为x的数据包接收错误，才能发送NAK，这会降低效率。如果发送方要发送大量的数据，且该端到端连接很少丢包，则只使用NAK协议会比使用ACK的协议更好，因为少发送了很多的确认数据包。
15. RTT=30ms，传输时延为0.012ms，如果不考虑ACK分组的传输时延与接收方的处理时间，那么一个分组从开始发送到接收到确认信息一共需要30.012ms，其中忙的时间为0.012ms，要使得忙的时间超过90%，那么需要在前面分组还没有被确认的情况下发送新的分组，设一共需要发送x个分组才能使忙的时间超过90%，则有0.012x/30.012>90%，解得x=2251，这即是窗口的最小值
16. 能增加信道利用率，因为发送方能够持续不断地接收到ACK，从而发送分组的时间间隔就会短很多，但出现差错时很难检测到，且发送方的ACK会占用带宽资源。
17. 略
18. 报文格式与SR协议相同。
19. 略
20. 略
21. 略
22. a. k-4~k+3都有可能。极端情况：所有分组全部被正常接收，但所有ACK全部丢失，此时接收方分组第一个序号为k，但发送方分组第一个序号为k-4；另所有分组全部传回ACK，则发送方分组第四个序号为k+3，此时发送方与接收方窗口位置相同。
    b. k-4~k-1都有可能。发送方发送k-5，接收方收到并且返回ACK(k-5)。发送方收到之前就超时，重发k-5。 发送方收到ACK(k-5)， 发送k-4, k-3, k-2, k-1。接收方收到重发k-5，返回ACK(k-5)。收到k-4, k-3, k-2, k-1，返回ACK(k-4)，ACK(k-3)，ACK(k-2)，ACK(k-1)
23. 对于GBN协议，窗口的最大值为k-1；对于SR协议，窗口的最大值为k/2。需要保证当接收方全部接收到且ACK全部丢失时，接收方能够识别出发送方重传的任何一个分组是老分组而不是新分组。
24. a. 正确。当出现超时重传时，可能会收到落在窗口前面的ACK。
    b. 正确。同样是超时重传，另外窗口的第一个ACK丢失也可能导致收到落在窗口前面的ACK。
    c. 正确
    d. 正确
25. 因为UDP协议是即时传输，应用程序将数据传递给UDP之后UDP协议就会尽快进行传输，而TCP可能还会对这些数据进行缓存、分片等操作，从而降低了应用程序的控制能力。因为TCP有拥塞控制，而UDP没有，应用程序使用UDP可以完全自行调节发送速度等。
26. a. 在序号不重复利用的情况下，TCP报文的序号最大值为2³²-1，那么L的最大值应该为2³²。
    b. 需要使用8012999个分组来封装这么多数据，加上首部分组的长度，一共需要传输2³²+8012999×64字节的数据，需要大约237s的时间。
27. a. 第一个报文段是由主机A发送，序号为127，含80字节数据，因此第二个报文段的序号为207。源端口号302，目的端口号80。
    b. 第一个报文段的确认中确认号为207，源端口号80，目的端口号302。
    c. 如果第二个报文段首先到达，则确认号为127。因为第二个报文段的序号不对。
    d. 如果第一个确认丢失，丢失的确认报文段中确认号为207。第二个确认（确认号为247）在第一个超时间间隔之后到达，在此之前发送方重传第一个报文段，然后收到了确认号为247的第二个确认报文段，于是不再重传，接收方收到重传的第一个报文段之后再一次返回确认号为247的确认报文段。
28. 本题中主机B读出数据的速率小于发送方发送的速率，因此主机B在发回来的确认报文段中会填入剩余缓存数量，表示剩余能够接受的窗口大小，当返回的窗口大小为0时，A将逐渐减缓发送数据，直到窗口为0时暂停发送。最终的传输速率不会超过50Mbps。
29. 略
30. a. 当数据输入到套接字的速度过快时，容易导致丢包，进而产生很多重复的数据包占用带宽资源，降低总吞吐量。如果路由器缓存容量增加，则会增加缓存中报文的等待时延，当等待时延过大使得发送方超时是又会进行重传，进一步增加了链路中重复报文的数量，可能会导致吞吐量进一步减少。
    b. 有助于，因为这样将不会有多余的重复报文占用带宽和缓存。
31. 公式回顾：$$\operatorname{EstimatedRTT}=\operatorname{EstimatedRTT}×(1-\alpha)+\operatorname{SampleRTT}\times\alpha\
    \operatorname{DevRTT}=\operatorname{DevRTT}\times(1-\beta)+|\operatorname{DevRTT}-\operatorname{EstimatedRTT}|\times\beta\
    \operatorname{TimeoutInterval}=\operatorname{EstimatedRTT}+4\times\operatorname{DevRTT}$$
    记忆技巧：EstimatedRTT相当于通过前几个RTT加权计算出来的RTT预估值，DevRTT相当于RTT的波动情况，TimeoutInterval相当于此链路中大多数情况下不会超过的RTT值。计算略。
32. a. $\operatorname{EstimatedRTT}_i=\sum_{j=0}^{i-1}\operatorname{SampleRTT}_i\times0.9^{i+1}+0.1\times\operatorname{SampleRTT}_i$
    b. 略
    c. 当n趋于无穷时，可以发现越近的RTT对EstimatedRTT的影响最大。
33. 如果ACK超时，那么重传之后收到的ACK可能不是对应于重传的分组而是一开始发送的分组，这样计算得到的RTT就小于正确的RTT。
34. LastByteRcvd≤SendBase-1。SendBase是最早未被确认的字节序号，LastByteRcvd是被接收方接收的最大字节序号。如果链路中没有正在传输的分组，则是等于号，否则为小于号。
35. y≤LastByteRcvd。假设TCP接收方丢弃失序的报文段的场合：在生成ACK的时间，y等于LastByteRcvd，当ACK报文传回发送方的时候，可能有新的报文到达接收方。
36. 这样会导致重传更加频繁，如两个数据包反序就会导致重传，容易占用大量带宽。
37. 主机A向主机B发送5个报文段且第2个丢失。
    a. 对于GBN，A发送的第一批5个报文段收到4个，发送了4个编号为1的ACK。然后A发送4个报文段，收到4个ACK。一共有8个ACK。对于SR，A发送的第一批5个收到4个，发送了4个不同编号的ACK，然后A发送1个报文段即可，收到1个ACK，一共有5个ACK。TCP协议在发送方接收到3个重传ACK之后就即刻重发，只重发了1个报文段，一共有5个ACK。（注意TCP有缓存机制）
    b. TCP，因为TCP在检测到3个重复ACK之后就立即重传。
38. 当出现丢包事件时，发送方发送的速率，每个RTT是必须大约等于cwnd报文段。首先发送方发送的速率不能大于cwnd，这是固定的限制条件。发送速率总是大约为cwnd/RTT。
39. 对于图3-46b，即在有限缓存情况下，发送方仅当在确定了一个分组丢失之后才重传，如果$\lambda_{in}'$增加超过了R/2，$\lambda_{out}'$不能增加超过R/3。如果发送速率超过了R/2，则多余的分组一定会丢失，因此增加了链路中重传的报文数量，故接收速率不仅不能增加，还可能会下降。对于图3-46c，即发送方也许会提前发生超时并重传在队列中已经被推迟但还未丢失的分组。这种情况下初始数据分组和重传分组都可能到达接收方，此时可用的吞吐量更加有限。如果一个分组平均重传次数是固定的，那么$\lambda_{in}'$增加可能会导致$\lambda_{out}'$增加，但实际情况下发送速率增加必然会增加重传次数，因此最终$\lambda_{out}'$不会增加。
40. a. TCP慢启动运行时的时间间隔为1~6、23~26。
    b. TCP拥塞避免运行时的时间间隔为6~16、17~22。
    c. 在第16个传输轮回之后，拥塞窗口长度cwnd没有变为1，因此是由于发现了3个冗余ACK而导致的。
    d. 是根据检测出超时而导致的。
    e. ssthresh的值设置为32。
    f. 在第18个传输轮回里，ssthresh的值设置为上一个传输轮回的cwnd的一半，即为21。
    g. 在第24个传输轮回中，ssthresh的值被设置为上一个传输轮回的cwnd的一半，即14。
    h. 第70个报文段是在第7个传输轮回中被发送。
    i. 拥塞的窗口长度为ssthresh+3（因为收到了3个冗余ACK，这是快速恢复的内容，不考），ssthresh的值为4，即变为拥塞长度的一半。cwnd=7。
    j. 如果使用TCP tahoe，则在第16个轮回后cwnd会变为1。在第19个传输轮回，ssthresh的值为21，拥塞窗口的长度为4。
    k. 从第17个传输轮回到第22个，分别传输了：1、2、4、8、16、21个分组，一共52个。
41. TCP的AIMD算法的收敛特性。假设TCP不采用乘性减，而是采用按某一个常量减少窗口。所得的AIAD算法将不能收敛于一个平等共享算法。如果是按照某一个常量减少窗口，则不能够收敛到45°线。假设某个时刻两个连接的传输速率为(r₁, r₂)，在没有丢包的情况下，这个点将沿着东北方向（45°）线移动，直到穿过135°的带宽阈值线。如果此时两个连接在一个传输轮回都发生了丢包，那么这个点将沿着225°线沿着西南方向后退，没有向中线移动。如果只有其中一个传输轮回发生了丢包，那么这个点或者向正西移动，或者向正南移动。即使这个点距离传输轮回更近，也没有收敛的意思。考虑到在传输速率过大时，传输速率较大的连接更容易发生丢包，因此这里这个点向中线移动的概率更大，但不能收敛到中线。
42. 如果发生了超时，不减少窗口大小，那么发送方会发送很多的重复数据包，而发生超时时链路可能已经非常拥塞，因此这会恶化情况。因此减少窗口大小可以在一定程度上缓解链路的拥塞情况。
43. 本题出现的情况是，链路的传输速率小于应用程序向套接字输入数据的速度，当发送缓存满时，就无法向套接字输入数据了。考虑到链路中不会有任何分组丢失和计时器超时，因此此问题无法通过拥塞控制来解决。实际上当发送缓存满时，进程传输数据的速率自动就降下来了，因为此时发送缓存将这个进程的任务进行了阻塞。
44. a. 6RTT
    b. 平均吞吐量为(6+7+8+9+10+11)/6=8.5MSS。
45. a. 连接速率从W/2RTT变化到W/RTT，在该周期的结束只丢失了一个分组。这个过程中一共传输了$\frac{\frac{3W}{2}(\frac{W}{2}+1)}{2}=\frac{3W^2}{8}+\frac{3W}{4}$，丢包率=这个值的倒数。
    b. 一条连接的丢包率为L，要证明平均速率的值，即证一个RTT之内平均传输了$\frac{1.22}{\sqrt{L}}$个数据包。考虑a中出现的理想情况，当W足够大时，$L\approx\frac{8}{3W^2}$，注意W的单位是分组数。可以求出$W=\sqrt{\frac{8}{3L}}$。平均速率应该为$\frac{\frac{3W}{2}(\frac{W}{2}+1)}{2(\frac{W}{2}+1)}=\frac{3W}{4\operatorname{RTT}}\approx\frac{1.22}{\sqrt{L}}$。其中$\frac{3W}{4}$是一个周期平均传输的分组数量。
46. a. 这条TCP连接取得最大窗口长度时，该链路处于满负荷状态。一个RTT是150ms，因此10Mbps=x×1500×8/RTT，求得x=125。
    b. 这条连接的平均窗口长度为：(125+125/2)/2=94个报文段，平均吞吐量为94×1500×8/0.15=7.52Mbps。
    c. 从丢包恢复之后，再一次到达最大窗口一共经历了x-x/2个RTT，即63个RTT，即9.45s。
47. 发送方和接收方之间的链路速率与双向传播时延之积，实际上就等于链路在一个时刻正在传输的最大的分组数量（将链路速率的单位设置为分组数量而不是比特数量）。在前一题中，在出现丢包的时候，cwnd减半，容易发现减半之后链路并没有满负荷工作。现在链路出现了缓存，当发送方的发送速率小于链路的带宽时，缓存可以同时发送分组使得链路保持饱和状态。这个缓存不能太短，否则会过早返回冗余ACK导致发送端暂缓传输（也就是该链路不忙于发送数据），所以必须足够大，大到一个RTT传输的数据量，这样，缓存区满时，再发送包会立刻引发重传。需要注意这里缓存的工作方式。如果发送方在一个RTT之内发送的数据大于一个RTT内能够传输的数据量，那么链路缓存将会缓存发送方最后发送的几个数据包，并使得在这个RTT时间内，发送方除去这几个数据包之外其他的数据包的数据量正好等于这个RTT内链路能够发送的最大数据量。在下一个RTT传输数据时，首先将缓存中的数据发送出去，然后发送发送方的前面一部分数据，再将这个RTT无法发送的数据包进行缓存。正因如此，当缓存满时，在一个RTT之内就会出现丢包的情况，发送方检测到冗余的ACK，将发送窗口减为一半，此时就需要将缓存中的数据包进行发送，逐渐减少缓存中的数据包数量以确保链路处于饱和状态。
48. a. 125000
    b. 7.5Gbps
    c. 156.25min，可以使用乘型增的方式增加。
49. 由45题可知，使用RTT为单位度量的T与W有函数关系，即T=W/2，平均吞吐量=3W/4RTT，因此平均吞吐量可以用T表示。
50. a. 拥塞链路的带宽为每秒30个报文段，在时刻0，C1的数据速率为200个报文段/s，而C2为100，远远超过链路带宽，因此会减半，直到二者的拥塞窗口都为1时，数据速率等于链路速率。
    b. 不会。
51. a. 时刻1，C1=15，C2=10，产生拥塞。时刻2，C1=7，C2=5，产生拥塞。时刻3，C1=3，C2=2，产生拥塞。时刻4，C1=1，C2=1，不产生拥塞。时刻5，C1=2，C2=2，产生拥塞。之后偶数时刻等于时刻4的情况，奇数时刻等于时刻5的情况。在2200ms之后情况等于时刻4的情况，拥塞窗口为1。（2100ms~2200ms时产生拥塞）
    b. 会。
    c. 是。
    d. 不能。可以让两个连接交替拥塞，这样可以提高利用率。
52. 这个乘型增的机制是当一个RTT内没有丢包事件发生时，窗口数量将乘以1+a。对于连续的几个RTT，记第一个RTT的编号为0，窗口长度为W/2，设最后一个RTT（编号为n）的窗口长度$\frac{W}{2}\times (1+a)^n=W$，W为链路最大传输速率（单位为分组数/RTT）。然后丢包，窗口变为一半。因此易得$(1+a)^n=2$，这些RTT一共发送了$\frac{W}{2}\times\frac{(1+a)^{n+1}-1}{a}=\frac{W}{2}\times\frac{2a+1}{a}$个分组，丢包率为其倒数：$L=\frac{2a}{(1+2a)W}$。在这个体系中，TCP连接将其拥塞窗口长度从W/2增加到W的周期时间不变。
53. 使用公式，一条连接的平均吞吐量=$\frac{1.22MSS}{RTT\sqrt{L}}$，取MSS=1500，RTT=100ms，求得L的值为2×10^-12。
54. 优点：可以略过慢启动和一部分拥塞避免的过程，可以让传输速率提升地更快。缺点：二者对于新的链路环境可能需要多次调整。建议可以增加链路缓存，让链路的使用情况变化地平缓一些。
55. a. 服务器将向Y发送响应，这个响应可能无法被收到。
    b. 可以确认。SYNACK将初始序号发送给了Y，其他人无法知道正确的初始序号。
56. a. S/R<RTT<3S/R

|时刻|事件|窗口大小|剩余窗口大小|
|:-😐:-😐:-😐:-😐:-😐
|0|发送SYN|0|0|
|1RTT|接收SYNACK|0|0|
|1RTT+1S/R|发送分组1完毕|1|0|
|2RTT+1S/R|接收ACK1|2|2|
|2RTT+2S/R|发送分组2完毕|2|1|
|2RTT+3S/R|发送分组3完毕|2|0|
|3RTT+2S/R|接收ACK2|3|2|
|3RTT+3S/R|发送分组4完毕，接收ACK3|4|3|
|3RTT+4S/R|发送分组5完毕|4|2|

在此之后，分组6和7将分别在3RTT+5R/S和3RTT+6R/S被发送，而考虑到4RTT+3R/S<3RTT+6R/S，因此ACK4先于分组7发送被接收，因此分组7发送完毕后窗口依然不为0，同理4RTT+4R/S<3RTT+7R/S（分组8发送完成的时间），因此ACK5先于分组8发送被接收，由此之后的所有时刻窗口都不会为0，于是就一直发送。最终需要时间为4RTT+14R/S。

b. RTT>3S/R

|时刻|事件|窗口大小|剩余窗口大小|
|:-😐:-😐:-😐:-😐:-😐
|0|发送SYN|0|0|
|1RTT|接收SYNACK|0|0|
|1RTT+1S/R|发送分组1完毕|1|0|
|2RTT+1S/R|接收ACK1|2|2|
|2RTT+2S/R|发送分组2完毕|2|1|
|2RTT+3S/R|发送分组3完毕|2|0|
|3RTT+2S/R|接收ACK2|3|2|
|3RTT+3S/R|发送分组4完毕，接收ACK3|4|3|
|3RTT+4S/R|发送分组5完毕|4|2|
|3RTT+5S/R|发送分组6完毕|4|1|
|3RTT+6S/R|发送分组7完毕|4|0|
|4RTT+3S/R|接收ACK4|5|2|
|4RTT+4S/R|发送分组8完毕，接收ACK5|6|3|
|4RTT+5S/R|发送分组9完毕，接收ACK6|7|4|
|4RTT+6S/R|发送分组10完毕，接收ACK7|8|5|

在此之后，发送到第15个分组之前窗口数量都不会变成0了，因此总时间为5RTT+11R/S。

c. RTT<S/R

|时刻|事件|窗口大小|剩余窗口大小|
|:-😐:-😐:-😐:-😐:-😐
|0|发送SYN|0|0|
|1RTT|接收SYNACK|0|0|
|1RTT+1S/R|发送分组1完毕|1|0|
|2RTT+1S/R|接收ACK1|2|2|
|2RTT+2S/R|发送分组2完毕|2|1|
|3RTT+2S/R|接收ACK2|3|2|
|2RTT+3S/R|发送分组3完毕|3|2|
|3RTT+3S/R|接收ACK3|4|3|
|2RTT+4S/R|发送分组4完毕|4|3|

考虑到发送一个分组的传输时延大于RTT，因此分组5发送完毕之前分组4就已经确认，剩余窗口大小等于窗口大小-1，而窗口大小不断增加，因此后面所有分组都将连续发送。共需要3RTT+15S/R。