数据通信笫十三讲交换机.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地址 虚电路网络中转发标签是虚电路号 以太网交换中转发标签是以太网地址 对应的转发决定消息给出了应该转发给哪个端口 转发表查找过程对交换机的性能非常关键的,转发表查询（续）,直接寻址： 转发表中对于每个转发标签都有一个对应的表项 每次收到分组，根据分组里面包含的转发标签直接找到对应的表项 要求大量的内存，每个转发标签的可能组合都需要有一个表项对应 如果N32，需要有232个表项 线性查找： 转发表只包含当前活跃的表项 收到一个分组时，和转发表中的每个活跃表项进行匹配 线性查找过程需要相当长的时间：O(K)，其中K为转发表的表项数 树查找策略：比线性查找快 转发表以一个树的形式组织的 N个比特的转发标签分割为总共m个n比特的单元b1b2bm，即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 如果有多个输入队列的最前面的分组都要交换到同一个输出端口，就会出现竞争，此时交换逻辑选择其中某个分组来转发 输入排队机制的优点是交换逻辑的交换速度和输入端口的速率相同，因此用硬件实现时比其他两种策略要具有更高的吞吐量 输入排队可能会遇到线头阻塞HOL，从而造成吞吐量的下降。,HOL阻塞,HOL阻塞：队列头部的分组使得队列后面的分组尽管可以不遇到任何冲突，但是仍然不能被交换出去 考虑一个22交换机，两个输入队列的头部的分组都要交换到输出端口2，假设选择端口1的分组转发，这样输入端口2被阻塞。 输入端口1目前空闲，但是输入端口2的第二个分组由于前面的分组被阻塞，该分组也不能交换出去，造成了交换机吞吐量的浪费。 研究者已经证明，如果每个输入端口到来的负载服从Bernoulli分布，并且分组交换到哪个输出端口的概率都相等时，输入排队机制的吞吐量只有理论上的最大吞吐量的58。,HOL阻塞（续）,解决HOL阻塞可以有两种方法 可以检查输入队列的前面多个分组来看是否出现竞争的情况，检查的分组数越多，吞吐量也越高。 检查的分组为无穷大时，相当于输入扩充 每个输入队列中，对每个输出端口都有一个缓冲区。 在每个时槽时间内，每个输入端口处的一个分组都可以直接交换到输出端口中，利用率接近于1。 输出扩充：原来的每个输出端口被L个输出端口代替。这样交换逻辑可以同时把L个分组交换到同一个目的端口中，因此可以大大提高吞吐率。,5.4.2 CROSSBAR交换机,NN CROSSBAR交换机中，每个输入端口和输出端口之间通过一个交换点（纵横点）连接 纵横点合上时，对应的输入链路和输出链路是连通的 如果纵横点被打开，则对应的输入链路和输出链路是断开的,CROSSBAR交换机（续）,NN点到点交换机（即没有输出排队机制）的输入端口和输出端口的不同连接数为N！ 在一个时槽内，任何两个不同的输入端口不能连接到同一个输出端口 任何两个不同的输出端口不能连接到同一个输入端口 为了完成同样的连接配置，最少需要多少个纵横点？ 假设一个交换机有C个纵横点 ，交换机支持的配置数最多为2C，显然 2C不同的连接配置数（N!） 按照Stirling逼近 化简后 即一个NN点到点交换机所需要的纵横点的最少数目的数量级为,Knockout交换机,纵横交换机一般采用输出排队机制，每个输出端口要能够处理所有N个输入端口的分组都到来的情况，从而限制了输入端口的个数 考虑到不可能在每个时槽内所有输入端口来的分组都要交换到同一个输出端口处，因此一个时槽时间内需要接收的分组数目为一个小于N的值，比如说K。 如果有超过K个分组要交换到同一个输出端口处，则只选择其中K个分组来转发，而其余的分组被丢弃。 K的取值要保证一个时槽时间内超过K个分组到达同一个输出端口的概率达到一个比较小的值。,Knockout交换机（续）,K的取值如何选择？ 假设交换机的负载符合如下的模型： N个输入端口，每个端口到来的负载服从Bernoulli分布，每个时槽有一个分组到来的概率为p。 到来的分组的目的端口的选择也是完全独立的，所有目的端口被选中的概率相同，即在给定时槽内一个给定的输入端口有一个到某目的端口的分组的概率为p/N 对于某一个目的端口，在一个时槽内有i个分组到达该目的端口的概率为P(i)：,假设有i个分组到达某一目的端口，所以对于一个给定目的端口，在一个时槽内分组被丢失的平均个数A为： 对于一个给定的目的端口，在一个时槽内到达的分组的目的端口正好就是该端口的概率为Np/Np。因此对于一个给定目的端口，分组的丢失率等于分组丢失的平均数除以到达分组数p：,丢失概率为： 如果p=1，即总是有分组到来时的丢失率为： 当K大于8时丢失率为O(10-6)，已经达到一个相对较小的值，正是这点导致了Knockout交换机的出现,Knockout交换机（续）,Knockout交换机有N条广播总线，每个输入端口连接到相应的总线上，每个输出端口通过一个总线接口连接到所有的广播总线上。,Knockout交换机（续）,总线接口负责从N个广播总线上选择最多K个属于该输出端口的分组，选择时要求采取公平的策略： 分组过滤器从N个广播总线上选择那些属于本端口的分组 集中器选择最多K个分组，其他分组被丢弃 移位缓冲区由一个移位器和K个单独的FIFO分组缓冲区组成 移位器的作用是为了保证K个分组缓冲区的FIFO顺序 从集中器来的最多K个分组通过移位器按顺序轮流进入到分组缓冲区中，输出端口也按照顺序轮流从缓冲区中选择分组传输。,Knockout交换机（续）,集中器要求能够从最多N个分组中公平地选择K个分组。 最基本部件是一个22的竞争交换单元 其功能是让两个竞争者决定赢家和输家，交换单元输出的左边是赢家，右边为输家，如图(a)所示 图（b）给出了该竞争交换单元的实现，只需要检查左边输入端的比特值，如果为逻辑1，则左边的输入被交换到赢家输出端口，右边的输入被交换到输家输出端口，如果为逻辑0，则右边的输入被交换到赢家窗口，而左边输入则不进行交换。,Knockout交换机（续）,集中器除了交换单元外还包括延迟单元（用D表示） 延迟单元只有一个输入和输出，其主要功能是实现1比特的延迟。 集中器采用了类似于锦标赛的思想 首先竞争者通过22交换单元两两竞争来选取一个赢家， 接着除了刚才的第一个胜者之外所有竞争者再进行一次锦标赛来选出另外一个胜者。 除了前面两个胜者之外的其他所有竞争者继续选出另外一个胜者，这个过程持续下去，直到选择了K个胜者为止。 竞争过程中如果出现奇数个竞争者的情况时，通过延迟单元等待从前面一个部分的竞争中淘汰下来的竞争者，同时延迟单元也用来保证所有的输出都在同一个时刻完成。,Knockout交换机（续）,Knockout交换机的复杂性为O（N2） 当N比较大时，集中器的交换单元个数接近于NK 分组过滤器的个数为N 移位缓冲区的设计与N无关 每个输出端口都有一个总线接口与之对应 Knockout交换机的设计是基于这样的假设：所有分组到来的负载是独立的，并且交换到目的端口的概率相等。在实际情况下，这个假设可能不成立，此时Knockout交换机的性能会受到比较大的影响。,5.4.3 共享媒体交换,一般包括共享高速总线和共享内存两种方式 共享高速总线： 所有输入端口和输出端口都连接到高速总线上 一个总线控制器或者仲裁单元轮流从输入端口选择分组，保证在某个时刻只有一个分组出现在高速总线上 要求总线的交换速度等于所有输入链路的速度之和，因此支持的端口数目是相对有限的。,共享媒体交换（续）,共享内存交换： 共享缓冲区是一个由许多缓冲区组成的缓冲区池，缓冲区通过多个链表连接起来，每个链表对应着一个输出端口，同时有一个空闲链表，包括那些还没有使用的缓冲区 每个时槽时刻： 输出端口对应的那些链表的头部所指的分组交换到对应的输出端口，并且将对应的缓冲区移到空闲链表中； 如果输入端口有分组到来，从空闲链表中取一个缓冲区，然后放到相应目的端口对应的链表中 能够有效地提高缓冲区的利用率，但交换逻辑的速度必须等于所有输入链路的速度之和,5.4.4 自路由交换（续）,多级交换的目的是减少纵横点的数目 考虑通过三级交换来代替一个NN的纵横交换： 第一级的纵横点是一个nk交换单元，所有N个输入连接到总共N/n个n*k交换单元， 第二级包括k个N/nN/n交换单元，第一级的每个交换单元的k个输出分别作为这k个N/nN/n交换单元的某一个输入 第三级包括N/n个kn个交换单元，这些交换单元是通过从第二级的k个交换单元中各选一个输出来连接的。 3级交换机的交换单元个数为：,自路由交换（续）,纵横交换和共享媒体交换中，首先通过一个决定过程来决定输入端口到输出端口的连接，然后对交换逻辑进行配置来完成交换功能。 自路由交换 交换逻辑由许多小的互连的交换单元组成 来自于输入端口的分组在决定了其输出端口后在其上附加一个头部，交换单元根据附加头部的信息来决定如何进行转发 自路由交换一般是采用多个22的交换单元来构造的，并且采用了多级交换策略 如果输入端口和输出端口的个数N=2n，则采用n级交换，每一级有N/2个22交换单元 如果一个22的交换单元进一步通过4个纵横点来实现，则总的纵横点的个数为,自路由交换的工作过程,决定路由，附加内部标记 交换机的决定过程根据分组包含路由标记来判断该分组应该交换到哪个目的端口 附加一个标明目的端口号的内部标记，标记总共需要n=log2N位 包含标记的分组沿途中的22交换单元（总共log2N级）移动直到到达相应的目的端口 交换单元根据分组包含的标记决定应该往“上”还是往“下”移动。 比如考虑一个n=3的自路由交换网络，内部标记记为b3b2b1： 第一级比特b1被用来决定分组是往“上”还是往“下”移动 然后比特b1被移走，在第二级b2来决定路由 第三级由b3来决定路由,Banyan网络，内部标记是这样的，如果输出端口为ABC，则标记b3b2b1为ABC。标记对应的比特如果为0，则表示分组往“上”移动，如果为1，则表示分组往“下”移动。 Omega网络中，如果输出端口为ABC，则内部标记为CBA，正好是相反的顺序，同样的标记对应的比特如果为0，则表示分组往“上”移动，如果为1，则表示分组往“下”移动。,Banyan网,自路由交换机制可能会出现阻塞，也就是说即便所有输入端口来的分组的目的端口都各不相同，这些分组可能也不能同时传输： 考虑一个Banyan网： 假设第一级交换单元的输入端口有两个目的端口分别为100和101的分组到来，相应的内部标记分别为100和101 该交换单元发现对应的比特都为1，因此都把分组往“上”移动，这样就会出现冲突。 Banyan网络中，如果输入端口到达的分组对应的目的端口号为升序排列，则不会遇到阻塞的情况。,Banyan网（续）,如何解决阻塞的问题？ 最直接的方法就是在每个交换单元处进行排队，如果出现阻塞，则把那个被阻塞的分组暂时缓冲起来。 在前面再附加一个Banyan网络 把到来的分组随机分布到第二个Banyan网络的输入端口上，从而使得阻塞出现机会降低 当一个分组到达时，原有的内部标记被一个随机选取的内部标记替代，该分组到达第二个Banyan网后恢复原有的内部标记 不能完全消除阻塞，要求在每个交换单元处实现排队机制。 前面附加一个排序机制 可以完全消除阻塞的情况 当然如果有多个分组要到同一个目的端口时，此时这些分组不可能同时传输。,Batcher网络,Batcher网络实现一个合并排序过程 首先按照输出端口号把分组两两排序、接着每4个分组排序、接着每8个分组排序、最后直到所有N个分组都排好序 包含两种类型的交换单元，分别是升序和降序交换单元，对应着标记大的分组应该是往下面移动还是往上面移动。 如果标记相同则随机选择顺序，如果没有输入，则对应的标记相当于无穷大。,Batcher网络（续）,一个Batcher网络所需要的交换单元的级数M为： 而每一级的交换单元为N/2个，因此总的交换单元数为 Batcher-Banyan网络增加了复杂性,Sunshine交换机,Batcher-Banyan网络中如果有多个分组的目的端口相同，则这些分组不能同时传输，需要丢弃分组 Sunshin