计算机网络第四章

4.3.1输入端口线路端接和链路层处理实现了用于各个输入链路的物理层和链路层。查找，转发，排队----在这个地方，路由器用转发表查找输出端口，使分组能经过交换结构转发到输出端口。----转发表的一个影子副本会存放在每个输入端口，使转发决策能在输入端口做出，避免了集中式处理的瓶颈。线路端接数据链路处理（协议、拆封）查找、转发、排队交换结构输入端口处理输入链路查找：概念上讲查找是简单的，即我们只是搜索转发表查找最长前缀匹配。但在吉比特速率下，这种查找必须在纳秒级执行。我们不仅要用硬件执行查找，还要对大型转发表使用超出简单线性搜索的技术。三态内容可寻址存储器（TCAM）经常被用于查找。通过查找确定输出端口后，分组就能发送进入交换结构。但若此交换结构正被其他输入端口的分组占用，则此分组会被阻塞，以致必须在输入端口处排队，等待稍后被及时调度以通过交换结构。除查找外，输入端口处理还需采取其他动作：1、必须出现物理层和链路层处理2、必须检查分组的版本号、检验和以及寿命字段，并重写后两个字段3、必须更新用于网络管理的计数器4.3.2交换结构位于路由器的核心，实现了分组从一个输入端口交换到一个输出端口。内存内存总线纵横式经内存交换：早期用计算机作为路由器输入端口与输出端口之间的交换由CPU(选路处理器)控制完成；输入端口与输出端口类似I/O设备：

当分组到达输入端口时，通过中断向选路处理器发出信号，将分组拷贝到处理器内存中；

选路处理器根据分组首部中的目的地址查表找出适当的输出端口，将该分组拷贝到输出端口的缓存中。此情况下，若内存带宽为每秒写入或读出B个分组，则总的转发吞吐量(分组从输入端口被传送到输出端口的总速率)必然小于B/2。且注意不能同时转发两个分组，即使有不同的端口号，因为经过共享系统总线一次仅能执行一个内存读/写。

现代路由器与早期路由器的主要差别是：输入线路上的处理器来执行目的地址的查找，并将分组存储(交换)进适当的存储位置。

在某些方面，类似共享内存的多处理机，用一个线路卡上的处理器将分组存储进适当输出端口的内存中。如，Cisco的Catalyst8500系列的交换机。经总线交换：输入端口通过一条共享总线将分组直接传送到输出端口，不需要选路处理器的干预。总线

输入端口为分组预先计划一个内部标签指示本地输出端口，通过总线传送到输出端口，只有与该标签匹配的输出端口才能保存该分组。每次只能有一个分组通过总线传送。分组到达一个输入端口时，若总线正忙，会被暂时阻塞，在输入端口排队因为每个分组必须跨过单一总线，故路由器交换带宽受总线速率限制。经互联网络交换：纵横式交换机：由2n条总线组成，n个输入端口与n个输出端口连接。每条垂直的总线在交叉点与每条水平的总线交叉，交叉点通过交换结构控制器能在任何时候开启和闭合。当某分组到达A，需转发到端口Y，交换机控制器闭合总线A和Y的交叉点，然后A在其总线上发送分组，分组仅由总线Y安排接收。不同输入输出总线上传输的分组不会相互阻塞。但若两个分组是两个不同输入端口，同一输出端口，则一个分组必须在输入端等待，因为给定总线在某个时刻仅有一个分组能被发送。纵横式4.3.3输出端口用于取出存放在输出端口内存中的分组，并将其发送到输出链路上。

交换结构排队：缓存管理数据链路处理(协议、解封)线路端接输出端口处理4.3.4何处出现排队输入端口和输出端口都会形成分组队列。排队的位置和程度，取决于流量负载、交换结构的相对速率、线路速率等因素。当队列逐步增长，路由器缓存空间终将耗尽，并当无内存可用于存储到达的分组是会出现丢包。假定：输入线路速率与输出线路速率相同，均为每秒Rline个分组，有n个输入端口和n个输出端口。定义交换结构速率Rswitch为:将分组从输入端口移动到输出端口的速率。输出端口排队设交换结构的速率至少是线路速率的n倍。最坏情况：到达每个输入端口的分组都被发往同一个输出端口。因为输出端口在一个单位时间（分组传送时间）内只能发送一个分组，有n个到达的分组必须排队(等待)发送到输出链路上；在发出队列中一个分组的时间内，又有n个分组到达。依此类推，最终排队的分组快速增长，很快占满输出端口的存储空间，使后续分组被丢弃。例假定：线路速度相同，交换以三倍快的线路速度进行操作。交换结构交换结构在时间t输出端口竞争一个分组时间以后

在t时刻每个输入端口都到达一个分组，都发往最上侧的输出端口。一个时间单位后（接收或发送一个分组的时间）：三个原始分组都被传送到输出端口，并排队等待发送。又有两个新分组到达交换结构的输入端，其中的一个分组要发往最上侧的输出端口。下一个单位时间：三个分组中的一个通过输出链路发送出去。输出端口排队的后果：

在输出端口上的一个分组调度程序必须在排队的分组中选一个来发送。

原则有：先来先服务FCFS：简单。加权公平排队WFQ：在具有排队分组的不同端到端连接之间公平地共享输出链路。当没有足够内存来缓存一个入分组，则要么丢弃到达的分组（弃尾策略），要么删除一个或多个已排队的分组来为新的分组腾出空间。已经提出和分析了许多分组丢弃与标记策略，统称为主动队列管理算法（AQM）。随机早期检测（RED）算法是一种得到广泛实现的AQM算法，此算法为输出队列长度维护着一个加权平均值。随机早期检测（RED）设最小阈值minth和最大阈值maxth平均队列长度小于最小阈值minth，到达分组会被纳入队列；队列满或平均队列长度大于最大阈值maxth

，到达分组则被标记或丢弃；平均队列长度在[minth，maxth]之间，到达分组则以某种概率被标记或丢弃。输入端口排队交换结构比输入端口总和的速度慢输入队列产生排队

交换结构不够快，即相对于输入线路速度而言不能快得使所有到达的分组无延迟地通过它传送，则在输入端口出现分组排队，以等待通过交换结构传送到输出端口。为说明这种排队的重要后果：考虑纵横式交换结构

假定：1.所有链路速度相同；2.一个分组能够以一条输入链路接收一个分组所用的相同的时间量，从任意一个输入端口传送到给定的输出端口。3.分组按FCFS方式从一指定输入队列移动到其要求的输出队列中。结果：1.分组输出端口不同：多个分组可以被并行传送。2.发往相同输出端口：位于两个输入队列前端的两个分组是发往同一输出队列的，则其中的一个分组被阻塞，在输入队列中等待，因为交换结构一次只能传一个分组到端口。举例：不同输入队列前端的两个分组要发往右上角的同一输出端口。若先发送左上角队列前端的分组，左下角队列中的分组要等待，左下角队列中排在该分组后面的分组也要等待，即使右中侧输出端口中无竞争。这种现象叫做输入排队交换机中的线路前部（HOLhead-of-the-line)阻塞：即在一个输入队列中排队的分组必须等待通过交换结构发送（即使输出端口使空闲的），因为它被位于线路前部的另一个分组所阻塞。时间t：输出端口竞争，仅一个红色分组能被传输时间t＋1：绿色分组经历了HOL阻塞交换结构交换结构4.3.5路由选择控制平面