《交换技术论文1.》由会员分享，可在线阅读，更多相关《交换技术论文1.（25页珍藏版）》请在金锄头文库上搜索。
1、云南大学信息学院交换技术论文交换技术论文论文题目：基于优选的交换机年 级：2009级小组成员：郭正红 20091170096 王 斌 20091060233 王东昊 20091060031 任 崝 20091060115任课教师：常俊老师 二零一二年六月目 录摘 要3绪论4一、单阶段优选交换机4（一）基本结构4（二）优选集中器原则7（三）集中器的结构9二、信道分组原则12（一）最大吞吐量12（二）广义优选原则14三、二级的组播输出缓冲器ATM的交换机16四、附录21五、结论23参考文献23摘 要交换机(英文：Switch，意为“开关”)是一种用于电信号转发的网络设备。它可以为接入交换机的任意两
2、个网络节点提供独享的电信号通路。最常见的交换机是以太网交换机。其他常见的还有电话语音交换机、光纤交换机等。本文主要讨论基于优选的交换机。目前还没有商业的交换机使用了此规则优选规则。这是因为这些结果建立在假设从不同的输入端输入的通信量分配是不相关的，而这一假设很不实际。除此之外，多余的单元被交换系统丢弃这种说法也很难让人轻易接受。通常，当缓冲器满了或者是超过了设定值，多的单元才会被自动丢弃。虽然优选规则还没有应用到实际的交换系统中，但它的概念已经吸引了很多专家，并且很多基于该概念的结构提出来了。有一些结构将在本章节进行讨论。关键词：交换机，网络设备，优选绪论如同第五章所述，带有输出缓冲器的交换机
3、（包括带共享存储的交换机）可以提供最好的时延输出特性。输出缓冲器式交换机的问题在于它们的容量受内存速率的影响。考虑有100个端口的ATM交换机：在同一时隙100个单元同时到达同一个输出端口的概率是多少？如果这个概率很低，为什么我们还需要在同一时刻容纳可以100个单元的输出缓存器。在20世纪80年代，一群在贝尔实验室的研究人员曾试图解决这个问题。他们通过限制在每个时隙可到达输出端口的单元个数，因此在输出端内存速率不再是交换系统的一个约束。多余的单元被交换系统丢掉。这个概念就被称为“优选规则”。现在的问题是在每个时隙应该有多少个单元传输到输出端口。如果太多，内存速率将是一个瓶颈。如果太少，在交换系
4、统中单元的损失率就会太高。在一定的损失率的基础上，单元的数量可以确定。不考虑交换机的大小，在损失率为10-10时单元的个数为12.对于输出缓冲器内存速率不再是一个瓶颈，结果在某种程度上看似很好的。然而，目前还没有商业的交换机使用了此规则优选规则。这是因为这些结果建立在假设从不同的输入端输入的通信量分配是不相关的，而这一假设很不实际。除此之外，多余的单元被交换系统丢弃这种说法也很难让人轻易接受。通常，当缓冲器满了或者是超过了设定值，多的单元才会被自动丢弃。虽然优选规则还没有应用到实际的交换系统中，但它的概念已经吸引了很多专家，并且很多基于该概念的结构提出来了。有一些结构将在本章节进行讨论。第9.
5、1节描述了优选规则、一个应用实现和基于优选交换机的结构。第9.2章介绍了一个强有力的概率信道分组，它保存在交换机上的路由连接。一个广义的优选规则的概念将被提出，它通过整合信道分组来扩展原优选规则。第9.3节，基于广义优选规则，描述了两个阶段的组播输出缓冲器交换机。第9.4节是一个附录，它主要介绍了在本章节中出现的方程式的来源。一、单阶段优选交换机（一）基本结构优选交换机如图9.1所示。它由完全广播互连的结构和N个总线接口组成。其中，广播互连结构有二个基本的特点：（1）每个输入端口都有独立的广播总线，（2）每个输出端口都可以连接都所有的广播总线，也即所有的输入单元。因为每个输入都有一个直连的路径
6、到达每个输出端口，在互连结构里是没有交换机堵塞的。唯一的堵塞出现在输出端的接口处，由于不同输入端的单元会同时到达同一个输出端。在某一程度下交换机结构可以模块化，N个广播总线可以安放在一个设备背板上，即在一个单一的插入式电路板上安置N对输入/输出线。图9.2阐述了总线接口结构与交换机的每个输出端口的联系。总线接口主要有三个部分。在最上面是一行的N个单元滤波器，每个单元的目的地址将在这被检查，只有那些目的地址是输出端口的才被允许进入集中器，其他的就被阻塞了。集中器是N个端口输入的，L个端口输出的，在每个时隙集中器都将有L个输出单元。这L个输出单元将输入到一个共享缓冲器，这个共享缓冲器主要由一个移位
7、寄存器和L个独立的FIFO缓存器组成。这个共享缓冲器完全共享这L个独立的FIFO缓存器，并提供一个L个输入、一个输出的队列，每个操作都按照FIFO队列规则。移位寄存器的操作如图9.3。在时隙T时，A、B、C单元到达并保存在FIFP缓冲器的最顶部，在时隙T+1时，D到J单元到达并且以此保存到FIFO缓冲器中。在移位寄存器的输出端单元的位置号是等于所有到达的单元数模除L。（二）优选集中器原则所有的单元通过单元滤波器进入集中器，集中器是N-L形的。在一个时隙中有k个单元达到集中器的输入端，如果kL，集中器的所有L个输出端口都将有输出单元，另外的k-L个单元将在集中器中丢失。单元损失率的估计如下。假设
8、在每个时隙单元到达输入端口的固定概率为。每个单元都有相同的概率到达任意输出端口。定义为在一个时隙内有k个单元要到达同一个输出端口。其二项式描述如下：在N-L型集中器里单元的丢失概率为：当 利用式9.2和9.3，图9.4a画出了单元损失率相对于集中器输出端口数L的曲线，其中，=0.9，N=16、32、64、。从曲线图中可以看出对于很大的N值，集中器的输出端口仅仅有8个时单元损失率已经小于10-6。这就好比传输中以10-9的比特错误率丢失500比特的单元。从图9.4a中还可以看出当集中器的输出端口数超过8个时，单元损失率减小。因此，不管集中器的输入端口数N，当集中器有12个输出端口时单元损失率将小
9、于10-10。图9.4b说明了，即使是在交换机负载为100%时集中器的输出端口数与交换机的负载量不是很有关系。同样也很重要的是，假设相互独立的单元到达各个输入端口，在分析中采用了相对最坏的简单同构的模型，其在图9.4显示的单元损失率在任何一个异构统计之上。（三）集中器的结构集中器的基本组成单元如图9.5a所示为22的交换单元。二个输入端口通过活动位相互竞争，在输出端分出赢方端和输方端。如果只有一个输入端口有输入（也就是只有一个活动为是1），那么这个输入端口就在输出端口为赢家。如果二个输入端口都有输入，那么在输出端输出到赢方端，另一个就被输出到输方端口。如果二个输入端口都没有输入单元，我们只关心
10、在交换机的输出端口活动位都应该为逻辑0.如上描述交换机可以有二种状态如图9.5b。交换机仅仅检查左边的输入端口的活动位。如果该活动为是1，则左边的输入将被输出到赢方端口，右边的输出到输方端口。反之，活动位是0，那么右边输入的输出到赢方端口，左边的就将没有输出路径。这种交换机可以用16个门电路实现，并且最多有一位时延。注意到22交换机的优先权是给了左边的输入端口。为了避免这个，交换机可以设计使得其优先权可以是左边输入端口和右边输出端口。如果交换机的优先权没有改变，那么集中器的第N个输入端口将有最低的优先级进入集中器。当N无穷大时，在这种最坏情况下的单元损失率为：以上方程式的得出是假设集中器的其余
11、N-1个端口中有k个输入端口是要输出到同一输出端口的，其中，当N无穷大时，如果集中器的其余N-1个输入端口中输出端口相同的输入端口数小于等于（L-1），那么第N个端口就可以被输出。式9.4的后面求和项是第N个输入单元不会丢失的概率。将式9.4与单元平均损失率（也即在式9.3和图9.4b中给出的）作对比，可以发现最坏情况下的单元损失率比平均的大10倍。而这个更大的损失率可以通过增加集中器的输出端口数来弥补。图9.6展示了一个8输入4输出的集中器，它由22基本的单元和1输入1输出的延时单元（标记为D）组成。在集中器的输入端口，从单元滤波器中输出的N个单元成对出现并进入到N/2个的基本交换单元中。这
12、个就可以看成N个单元进行第一轮的竞争，每个基本单元的赢者就出现在交换单元的左边输出口，而输者就出现在右边输出口。第一轮胜出的N/2个赢者就成对提前进入第二轮竞赛的N/4个基本交换单元中。赢的单元就这样一直竞争直到只有一个，它可以第一个在集中器中输出。只要有输入单元输入到集中器中，那么集中器的第一个输出单元就有单元输出。含有一个树形结构的比赛，结果只能有一个胜出者，这个也称为一次优选（含有多次比赛），在一次优选中，只要你输了一场比赛，那么你就被本次比赛优选了。在二次优选中，在第一次比赛中输掉的N-1个单元再进行第二轮的优选，再产生出N-2个输掉的单元。从图9.6可以看出在第一轮比赛中输掉的单元可
13、以进行第二轮的比赛。当有奇数个单元竞争时，有一个单元必须等到下一轮才能进行比赛。在集中器里，延时单元就是为这项工作服务的。对于N-L性集中器而言，有L次优选（含一个树形结构的区域），每一次优选都会产生一个输出，就有L个输出了。只有当超过L个单元输入时集中器才会发生丢失。当NL时，集中器的每个区大约包含N个基本交换单元，那么对整个的集中器，一共将有16NL个门组成。例如，N=32，L=8，那么整个集中器保守的计算则至少需要4000门。一旦小型的集中器被焊接完成，图9.7说明了几个小型的集中器如何连接成一个大的集中器。二级的单元集中器的单元损失率与一级的单元损失率是一样的。一般性结论，有KJL个输
14、入端口，L个输出端口的集中器可以由J行KL-L型的集中器构成，其中第i行包含Ki-1个KL-L型集中器。比如如图9.7，L=8，K=4，J=2.二、信道分组原则二级网络的建立是基于信道分组原则以区分一级网络和二级网络。如同一级网络一样，二级网络也有同一级网络一样的输出端口。比如如图9.8所示。一级网络将单元转发到合适的输出单元上，二级网络在进一步的将这些单元转发到他们的合适的位置。这减缓了输出端竞争的问题，从而更好的权衡了一级网络的复杂性。（一）最大吞吐量这部分主要围绕图9.9的交换机结构。一个输出群，每个输出群包含M个输出端口，也就相当于一级网络的输出地址。任意一个输入单元可以到达一级网络的
15、任意一个输出端口。在任意给定的时隙，在一个输出群组里最多有M个单元被清除。一个输入缓存的交换机的最大吞吐量被行头阻塞限制着。表9.1列出了在不同M和K/N下的最大吞吐量。对于给定的M值，最大吞吐量随着K/N的增加而增加，因为每个输出群的负载会随着K/N的增加而减小。对于给定的K/N，最大吞吐量随着M的增大而增大，因为每个输出群将有更多的输出单元。表9.2列出了在不同的M和线性膨胀系数（KM）/N，也即输出端口数比输入端口数）下的最大吞吐量。在一定的线性膨胀系数下，最大吞吐量随着M的增大而增大。信道分组对吞吐量的作用小的线性膨胀系数比大的明显。这是因为在大的线性膨胀系数且M=1时，线性膨胀已经减轻了由于行头阻塞限制的吞吐量。（二）广义优选原则这个部分
