第三部分(交换2)

基于入端口缓存的队列调度交换结构一般采用定长交换技术，变长分组（如IP包）需要在入端口被分成多个固定长度的信元（cell），然后在出端口进行重组；初期对交换结构容量的需求在几百Mb/s~Gb/s数量级。此时，OQ结构相对于共享缓存、IQ结构在吞吐率、时延等方面有较大优势；随着交换容量的迅速提高（线速、端口数量），OQ结构缓存的存取速率成为瓶颈；为了构建大规模、高速交换结构，IQ、CIOQ交换结构及其调度方法再次成为人们研究的重点；为了消除HOL现象，一般采用VOQ结构。总共有N2个FIFO，到达入端口i去往出端口j的分组被存储在VOQi,j中；在每个时隙，位于各队列的第一个分组有机会被选中发往其目的输出端，但每个入端口的N个队列最多只能有一个分组被选中；如果各输入端的分组到达率相同，且等概率地发往各输出端，就称这种到达业务服从均匀分布。吞吐量（throughput）和时延（delay）是分析交换结构性能的重要参数；吞吐量是指，在一个时隙周期，交换结构传输的分组总数；时延是指，一个分组从到达到离开所需要的时间；如果各等待队列的长度是有限的，则称交换结构是稳定的。为了使交换结构工作在稳定状态，并具有较好的网络性能，队列的调度算法（schedulingalgorithms）起关键作用；调度算法可用匹配图加以说明，如下图所示。图中左右两边的节点分别代表输入、输出端口，各条边表示相关入口有分组要发往对应的出口；调度器的作用：从最多N2条边中选出一组边（匹配），使一个入端口最多只与一个出端口相连，同时一个出端口最多只与一个入端口相连；匹配结果可用矩阵表示为：M=(Mi,j)，i,j≤N，当入端口i与出端口j匹配后，对应元素Mi,j=1；一个简单的例子如下图所示。选择调度算法需考虑的因素：效率：在一个时隙周期能实现较多的“输入-输出”匹配，以获得较高的吞吐量以及较低的时延；公平性：需避免部分队列长期得不到服务的现象；稳定性：对于可能出现的任何业务模型，队列长度均是有限的；低复杂度：算法运算耗费的时间需较短，否则会限制交换结构的线速。最大极限匹配（MaximumMatching）最大权重匹配（MWM：MaximumWeightMatching）在匹配图中，首先给各条边赋予不同的权值，以代表该VOQ队列的优先程度（它可以代表队列长度，等）；对于连接入端i到出端j的边ei,j，设wi,j为其权值，则实现MWM的目标就是使最大。如下图所示：复杂度较高（N3），对于速率较高的大规模分组交换结构，实现难度大；较典型的算法有LQF（longestqueuefirst）、OCF（oldestcellfirst）；LQF算法以等待队列的长度为权值，但可能使部分业务量较少的队列长期得不到服务；OCF算法则以各队列第一个分组的等待时间为权值。B.最大规模匹配（MSM：MaximumSizeMatching）以获得最多“匹配对”为目标；是MWM的特例（当各条边的权值均为1时）；前例的MSM算法结果如下图所示。最大匹配（MaximalMatching）在添加新匹配对时，不删除已确定的配对，简化匹配过程（复杂度较低）；如果一个非空的入端口在一个匹配周期未实现匹配，其目的端口一定与其它入端口已经匹配；一般地，能成功配对的数量少于最大极限匹配的情况。A.并行迭代匹配（PIM：ParallelIterativeMatching）在每个时隙周期最多可以有N次迭代过程。在每个匹配周期开始时，全部输入端、输出端均为未匹配状态；只有未实现匹配的输入端、输出端才能参与新一轮的匹配；每次迭代，全部输入、输出端并行执行3个步骤：请求（Request）、同意（Grant）、接受（Accept）。

请求：每个未匹配的输入端向其全部目的输出端发出请求；同意：如果一输出端收到多个请求，就从中任意选择一个，每个请求获得“同意”的概率相等；接受：如果一个输入端同时收到多个“同意”回复，就从中确认一个，并将确认信息告诉对应的输出端。PIM的一次迭代过程如下图所示。当业务为均匀分布时，一次PIM迭代后的吞吐率约为63%。假设N×N交换结构的全部VOQ非空，那么每个输出端口会同时收到N个请求，依据PIM原则，每个请求被同意的概率是1/N。那么，一个入端口未收到“同意”的概率就是

。当业务为均匀分布时，N次PIM迭代后的吞吐率为100%。业务较重时，PIM可能引起不同连接间的不公平性。迭代轮循匹配（iRRM：IterativeRound-RobinMatching）工作方式与PIM相似，每次迭代包含3个步骤：请求（Request）、同意（Grant）、接受（Accept）；与PIM的不同之处在于，收端、发端不再采取随机的方式选择端口，而是采用轮循的方式，为此，在收端与发端，分别有一指针（入端口为ai，出端口为gj）指向最高优先级端口，每完成一次选择，指针值加1。工作示例如下图所示，假设ai、gj的初始值均为1。iRRM相对于PIM具有较好的公平性；一次迭代后，iRRM的吞吐率与PIM相同；iRRM存在输出端同步现象，会使其一次迭代吞吐率下降。入端口i的VOQ均为非空；各出端口指针值相同，均为i。一次迭代只有一对端口完成匹配，而且下一轮迭代时，所有出端口指针值仍相同。iSLIP为了解决iRRM输出端口的同步现象；每次迭代同样包含3个步骤：请求（Request）、同意（Grant）、接受（Accept）；与iRRM的不同之处在于，只有当发端确认后，收端指针才进行更新，而且收端、发端指针只在第一次迭代时才进行更新，其余N-1次迭代均不更新，避免出现部分VOQ队列长期得不到服务的现象（starvation）；单个VOQ等待服务的时间不超过2N个时隙。iSLIP的一次迭代过程如下图所示。Starva