数据通信笫十三讲交换机.ppt

《数据通信与计算机网络（第二版）》电子教案 笫十三讲 交换机 本讲内容 第五章 高速网络技术 5.4 交换机 5.4.1 转发表查询 5.4.2 缓冲区的设计 5.4.2 CROSSBAR交换 5.4.3 共享媒体交换 5.4.4 自路由交换 5.4 交换机 交换机可被看成一具有M个输入链路和N个输出链路的设备，链路连接到交换机的端口，用M*N交换机来表示。 在大多数情况下，M和N是相等的，比如交换机的链路是全双工时 交换机（续） 对不同的网络采用的交换方法可能会不一样 电路交换网络：电路建立好后通信沿预先建立好的通路进行 交换机必须维护交换机的当前配置 交换延迟非常短，交换机内部不需要维护大量的缓冲区。 分组交换网络：每次到来一个分组，交换机检查分组携带的路由信息来决定转发的链路 在很短的时间内，可能会有大量的分组都要往一条输出链路转发，要求交换机具有缓冲支持。 交换机（续） 交换机常用的性能度量包括： 大小或者容量指交换机支持的端口数目 延迟包括交换延迟和排队延迟 交换延迟指交换机分析分组然后决定并放到哪个输出链路的延迟 排队延迟则指分组在交换机内排队等待处理的延迟。 吞吐量：和交换机的端口数以及每个输入链路的速率相关 最理想结果是交换机的吞吐量等于所有输入链路的数据速率之和 在实践中交换机的吞吐量可能达不到理想值。 输入链路到来的负载可能会动态变化的，输出端口可能来不及处理，需要缓存或者丢弃 考虑到分组可能是可变长的，吞吐量的度量包括单位时间内的通过的比特数bps以及单位时间内通过的最小分组数pps 复杂性：交换机内部采用的设计的开销，包括交换单元的个数、缓冲区的个数、交换机内部的比特流的速率等。一般交换机支持的吞吐量越高，交换机的设计也越复杂。 5.4.1 转发表查询 一个交换设备实际上包括路由与交换两个部分 路由部分负责与其他交换设备进行通信来了解网络的拓扑信息，从而知道到达目的地的路由情况，并据此来构造一张转发表 交换部分在收到一个分组后，通过查询转发表来决定应该向哪个链路转发，然后把该分组通过交换逻辑放到输出链路中 转发表的每个表项包括（转发标签，对应的转发决定信息） 转发标签给出了如何与分组包含的路由信息进行匹配 IP网络中转发标签是目的节点的IP地址 虚电路网络中转发标签是虚电路号 以太网交换中转发标签是以太网地址 对应的转发决定消息给出了应该转发给哪个端口 转发表查找过程对交换机的性能非常关键的 转发表查询（续） 直接寻址： 转发表中对于每个转发标签都有一个对应的表项 每次收到分组，根据分组里面包含的转发标签直接找到对应的表项 要求大量的内存，每个转发标签的可能组合都需要有一个表项对应 如果N＝32，需要有232个表项 线性查找： 转发表只包含当前活跃的表项 收到一个分组时，和转发表中的每个活跃表项进行匹配 线性查找过程需要相当长的时间：O(K)，其中K为转发表的表项数 树查找策略：比线性查找快 转发表以一个树的形式组织的 N个比特的转发标签分割为总共m个n比特的单元b1b2…bm，即N=n*m。 b1的每个可能取值或者对应着一个空指针，或者对应着另外一个表格，这个表格进一步对应着b2的每个可能的取值，如此继续。 转发表查询（续） Hash查找法： 通过一个Hash函数把N个比特的转发标签映射为K个比特，然后这个表项再分别对应着一个相应的转发信息 如果有两个相应的转发信息经过Hash映射之后对应着同一个K比特的值，则该转发信息被附加在原有的转发信息之后 内容寻址内存CAM CAM保存了目前活跃的N比特的路由标签 交换机在收到一个分组后，从分组头部截取路由标签然后递交给高速CAM进行匹配，如果标签匹配，则CAM返回一K比特的索引号。 K比特索引号可再用来查询（比如采取直接寻址）一个表格来获取转发决定信息 CAM相对来说比较贵，因此其容量是相对有限的。 5.4.2 缓冲区的设计 来自于多个输入链路的分组可能都同过某一条或者某几条链路转发，这样就要求进行排队。 分组可以在输入端口处、输出端口处或者在交换机内部进行排队。 共享内存交换机采用的是内部缓冲策略（internal buffering），而KNOCKOUT交换机采用的是输出排队策略 缓冲区的设计（续） 分组在哪里进行排队？ 输出排队：分组在输出端口处进行排队 由于可能要把多个链路上的分组交换到输出端口中，因此要求比较高的交换速度，要求大于所有输入链路的数据速率之和。 内部排队：在交换机内部进行排队，比如共享内存交换机采用的策略 输入排队：在输入端口处排队，最简单的方法是采用FIFO 如果有多个输入队列的最前面的分组都要交换到同一个输出端口，就会出现竞争，此时交换逻辑选择其中某个分组来转发 输入排队机制的优点是交换逻辑的交换速度和输入端口的