路由和交换.ppt

输出竞争解决 3阶段算法解决Batcher-Banyan交换机输出竞争 第1阶段：输入端口发送短的请求（由源和目的组成），通过Batcher排序网络根据目的非递减排序，然后进行仲裁 第2阶段：赢得竞争的请求通过交换网络发送确认（Acknowledgement）给对应的输入端口 第3阶段：赢得竞争的输入端口通过Batcher-Banyan交换网络发送信元 第1阶段 仲裁 第2阶段 确认 第3阶段 发送 在高速路由器中，数据路径功功能速度要求高，大部分通过硬件实现；而控制面功能速度要求低，一般使用软件来实现 对于IPv4分组，路由器除了执行基于分组目的地址的路由查找以外，还要更新IPv4头标中的TTL域，然后重新计算校验和，这些操作硬件实现比较容易 这里假设IP地址长度为8个比特 该算法的名称来自于提出者所在的研究机构名称，Lule? University of Technology Lulea trie可以看做是用bitmap来压缩的multi-bit trie 在第二级或者第三级查找过程中，密集和高密集块的查找算法与第一级类似。对于稀疏chunk，8个8-bit索引表示了每个head在256-bit比特向量中的位置。将它们按照从大到小的顺序排列。为了避免查找时碰到最差的情况，采用了一种类似于折半查找的算法。即首先检查8-bit索引的第4个值，看是否匹配上，如果没有，则知道要查找的元素是在最开始的4个值还是最后的4个值。确定后再次使用要查找的元素和8-bit索引值比较，直到找到第一个小于或者等于查找关键字的索引为止，该索引就是所要找的。对于稀疏块，查找时最多只需要访问7个字节（2字节指针+5字节查找8-bit索引）。 在查找的时候，只能用k-1比特来查找，因为真正的k比特长前缀被push到下一个节点了 Internal bit map中有1bit用于长度为0的前缀，接下来2比特用于长度为1的前缀，接下来的4bit用于长度为2的前缀，等等 我们使用一个简单的lazy策略，即直到查找结束了才访问结果节点。根据最长前缀匹配规则，我们只需要访问最后一次匹配到前缀的节点的结果数组就可以了。这仅仅只在查找结束的时候增加一次存储引用，而不是对每个节点都执行一次存储引用。 如果Skip不为0，则在CPA的末尾需要添加一个failure CP。当查找关键字没有匹配上Bitstring时，返回failure CP。 除去2B的头标，还有128-2=126B=1008b用于bitmap和CPA，假设word frame中只有1个subtrie结构，并且CPA的大小为1，则subtrie的最大高度为Log2（1008-16）=9。 前缀trie被划分为3个sub-trie，高度或者说步长分别为2，2，3。3个sub-trie的CPA的大小都为4（个指针），因此他们都存储在一个word frame中。在例子中，假设IP地址的长度为7比特，而word的大小为8B。因此，sub-trie的大小也被限制在8B。 空分交换 也被称为第三代交换技术 交换机速率受限于交换结构，通常汇聚容量小于50Gbps 空分交换 分布式控制 多级交换交换结构 更高的交换机速率 空分交换 单路径交换 任何输入-输出端口对之间只有1条路径 路由控制简单 多路径交换 任何输入-输出端口对之间只有多条路径 具有更好地连接灵活性和故障容忍能力 总的交换容量：能够同时发送信元的路径数量×每条路径的带宽 单路径交换—Crossbar 输入 输出 交叉点 Cross State Bar State 1 2 3 4 1 2 3 4 单路径交换—Crossbar 优点 内部无阻塞 体系结构简单 模块化 但是不能避免输出端口竞争！ 对于N×N Crossbar交换机，交叉点的数量为O(N2) 4个请求 输入端口1到输出端口3 输入端口2到输出端口4 输入端口3到输出端口1 输入端口4到输出端口3 CrossBar举例 交叉点交换 (1,3) (2,4) (3,1) (4,3) (1,3)和(4,3)竞争 1 2 3 4 2 1 3 4 多路径交换—Clos 三级结构： 第一级分发输入数据 第二级多路径（决定路径的数量） 第三级交换到正确的输出端口 0 0 交换结构 基本概念 交换结构 缓存策略 Banyan交换机 共享存储器队列 用于共享存储交换 1）存储器由所有的输入和输出共享 2）存储器被划分为逻辑队列，与每个输出端口对应 输入 逻辑队列 输出 输出队列 解决输出端口竞争 1）每个 输出端口都设置队列 2）加速大于1（最大为N）必须使用输出缓存 3）易于实现基于QoS调度 输入 输出 输出队列 交换结构 输入队列 解决输出竞争 1）每个 输入都设置队列 2）存在着头阻