最新宽带网课件第三部分(交换1)

宽带网课件第三部分(交换1)宽带网课件第三部分(交换1)1传统电路交换的优缺点。统计复用：用户数据不再固定、周期性地占用时隙，而是根据用户请求和网络资源情况，由网络动态分配。接收端不按固定的时隙关系来提取相应用户数据，而是根据数据中携带的目的地址来接收数据。这种复用方式称为异步时分复用，也称为统计时分复用。传统电路交换的优缺点。2最新宽带网课件第三部分(交换1)3最新宽带网课件第三部分(交换1)4最新宽带网课件第三部分(交换1)5最新宽带网课件第三部分(交换1)6最新宽带网课件第三部分(交换1)7最新宽带网课件第三部分(交换1)8交换结构的评价方法可以从性能和实现成本两方面评价一种交换结构的优劣。性能：在各种可能的业务流模式（包括多播）下，分组经过交换结构的时延、时延抖动、丢失率等。成本：实现交换结构所需的缓存和连线资源的多少，做工程实现时所需花费的人力物力。共享缓存交换结构可以认为是最好的一种。由于充分共享内部缓存资源，资源消耗较少。因此，可以将共享缓存作为一种比较对象。交换结构的评价方法可以从性能和实现成本两方面评价一种交换结构9交换结构中的资源冲突交换结构是由连线和缓存构成的。连线又分输入端连线、内部连线和输出端连线。当多个信元要同时去往一个输出端口，就造成输出端冲突（outputportcontention)，解决办法：选择一个信元从输出端口发出，将其余信元暂时缓存或丢弃。当多个信元要同时经过一个内部连线时，就造成内部连线冲突（internallinecontention)，或称为内部连线阻塞（internallineblocking)。解决办法：暂时缓存信元或丢弃信元。交换结构中的资源冲突交换结构是由连线和缓存构成的。10当资源冲突引起信元暂时缓存，如果缓存里只有一个FIFO(FirstInFirstOut)队列，就会产生队头阻塞（HeadofLineBlocking：HOLBlocking）现象。当资源冲突引起信元暂时缓存，如果缓存里只有一个FIFO(F11研究交换结构要解决的中心问题用多少连线和缓存资源，如何配置资源，在各种可能的业务流量模式下，将冲突的概率减少到可以接受的程度，从而使信元延迟和丢失率达到一定指标。研究交换结构要解决的中心问题12交换结构中的资源冲突

—Outputportcontention交换结构中的资源冲突

—Outputportconten13交换结构中的资源冲突

—InternalLineBlocking交换结构中的资源冲突

—InternalLineBloc14交换结构中的资源冲突

—引起HeadOfLineBlocking交换结构中的资源冲突

—引起HeadOfLineBlo15交换结构的分类

—按外部特性内部无阻塞型：如果一个外部输入端和一个外部输出端是空闲的，则一定可以找到空闲的内部通道将输入端和输出端连接起来。内部阻塞型：如果一个外部输入端和一个外部输出端是空闲的，不一定可以找到空闲的内部通道将输入端和输出端连接起来。交换结构的分类

—按外部特性内部无阻塞型：如果一个外部输入16交换结构的分类switchfabric按资源的使用方法可做如下分类：交换结构的分类switchfabric按资源的使用方法可做17交换结构的分类

—时分复用交换交换结构中的内部资源被所有从输入到输出的信元分时共享，即时分复用。这种内部资源可以是一个总线，也可以是一个缓存。时分复用交换结构可以分为共享媒介型和共享缓存型，共享媒介可以是总线或环。交换结构的分类

—时分复用交换交换结构中的内部资源被所有从输18共享总线型交换结构

从各个输入端口来的信元分时通过总线到达输出端，输出端的AF让目的的为本输出端口的信元通过。总线速率至少等于各个输入端口速率的和。优点是简单、容易支持多播。缺点是各个输出端口的缓存不能共享，缓存的速率至少等于总线速率，且缓存比较大。支持大的交换容量比较困难。共享总线型交换结构从各个输入端口来的信元分时通过总线到19共享缓存型交换结构优点：缓存可以得到充分共享。缺点：缓存的速率限制了交换容量的扩展。共享缓存型交换结构优点：缓存可以得到充分共享。20在时分复用交换中，所有从输入端到输出端的信元经过的是同一个通道。在空分交换中，从输入端到输出端有多条通道，这些通道可以同时工作，多个信元可以同时从输入端到输出端。空分交换结构的交换容量等于通道的带宽乘以可以同时工作的通道数目。因此，扩容的方法就是提高通道的带宽和提高可以同时工作的通道数目。交换结构的分类

—空分交换在时分复用交换中，所有从输入端到输出端的信元经过的是同一个通21空分交换又分为单路径和多路径。单路径空分交换结构中，从一个输入端到一个输出端，只有一条路径；多路径空分交换结构中，则有多条。空分交换又分为单路径和多路径。单路径空分交换结构中，从一个输22空分单路径交换结构

—fullyinterconnectedswitch（全互联交换）空分单路径交换结构

—fullyinterconnecte23空分单路径交换结构

—Crossbar（交叉连接矩阵）空分单路径交换结构

—Crossbar（交叉连接矩阵）24空分单路径交换结构

—Banyanbasedswitch空分单路径交换结构

—Banyanbasedswitch25Banyan-based交换机是由多个2×2的交换单元构成，每个交换单元都是自路由的，即自己可以决定进入信元的输出口。优点：容易用大规模集成电路构成大容量的交换机。缺点：由于是单路径，因此是内部阻塞的。当端口数很多时，阻塞概率增大，性能降低。Banyan-based交换机是由多个2×2的交换单元构成，26空分多路径交换结构空分多路径交换结构27空分多路径交换结构

—AugmentedBanyan(扩张的Banyan)普通的Banyan的交换级数为log2N，扩张的Banyan的交换级数大于log2N。普通的Banyan中，从一个入端口到一个出端口只有一条路径，当竞争失败，信元偏离其预定路径，则必定被丢弃。扩张的Banyan中，从一个入端口到一个出端口的路径有多条。竞争失败的信元可以转往其它路径，也可能到达目的端口。扩张的Banyan性能比普通的Banyan好，但是实现的复杂性增加了。空分多路径交换结构

—AugmentedBanyan(扩张28Benes交换结构以最后一级为对称轴，翻转N×N的Banyan的其它级，就得到N×N的Benes结构。Benes交换结构以最后一级为对称轴，翻转N29空分多路径交换结构——三级Clos在第一级，N个输入线被分为r个组，每个组有n条线，连接到一个交换单元，交换单元有m条输出线，每一条分别连接到第二级的一个交换单元。第二级有m个交换单元，每个交换单元有t条输出线。第三级有t个交换单元，每个交换单元有N/t条输出线。空分多路径交换结构——三级Clos在第一级，N个输入线被分为30三级Clos，N=9，n=3，m=3，有内部阻塞。粗线表示当前被占用的连线。输入端口9到输出端口4或6，无法连通。三级Clos，N=9，n=3，m=3，有内部阻塞。31空分多路径交换结构

—多平面交换多平面交换结构中有多个交换平面可以让信元通过。优点：与单平面交换结构相比，可以降低信元冲突概率，提高性能。同时，可靠性也提高。当交换平面中的一个或多个发生故障时，剩余的交换平面仍然工作，整个交换机仍然可以工作，只不过性能降低了。缺点：实现复杂性增加。为避免乱序，属于同一个packet的信元必须走同一个交换平面。空分多路径交换结构

—多平面交换多平面交换结构中有多个交换平32空分多路径交换结构

—循环交换循环交换结构中，竞争失败的信元从循环端口输出，返回到输入端，竞争下一次机会。优点是可以在一定程度上提高性能。缺点是循环端口使交换机的端口数增加了，且可能出现信元乱序问题，即属于一个packet（IP）的信元没有按进入的顺序到达输出端。必须采用一定的机制来处理。空分多路径交换结构

—循环交换循环交换结构中，竞争失败的信元33交换结构中的缓存共享缓存；OQ（OutputQueuing）；IQ（InputQueuing）；VOQ（VirtualOutputQueuing）；CIOQ（CombinedInputandOutputQueuing）；CrosspointQueuing交换结构中的缓存共享缓存；34共享缓存缓存资源可得到充分共享，各输入、输出端口可访问同一缓存；在每个信元时隙，要完成所有入端口输入信元和全部出端口输出信元的读写操作。因此：memoryaccesscycle<=celllength/(2N×linkspeed)（假设：存储器的总线宽度等于一个cell）例如：对于155Mb/s的53字节信元，如果存储器的访问周期为10ns，则交换结构的端口数小于等于136。共享缓存35OQ（OutputQueuing）OQ（OutputQueuing）36数据到达输入端后，立即被发送到对应的输出端；各输出端口数据的到达速率大于发送速率，需配置缓存；规模受到缓存存取速率的限制；缓存利用率不如共享缓存结构。数据到达输入端后，立即被发送到对应的输出端；37IQ（InputQueuing）IQ（InputQueuing）38数据到达各输入端后，首先被存放在FIFO中；交换结构的规模不再受缓存的限制；需要设计相应的调度算法，在每个时隙进行入端口/出端口配对；会产生队头阻塞现象（HOL）；在业务均匀分布的情况下，吞吐率仅为58.6%。数据到达各输入端后，首先被存放在FIFO中；39VOQ（VirtualOutputQueuing）VOQ（VirtualOutputQueuing）40各输入端口均设置N个队列，分别对应N个输出端口；不会出现队头阻塞现象；在每个时隙，每个入端口的N个队列只能选择一个队列发送数据，匹配算法较复杂；时延、吞吐率、复杂度等是考察匹配算法的重要参数。各输入端口均设置N个队列，分别对应N个输出端口；41CIOQ（CombinedInputandOutputQueuing）CIOQ（CombinedInputandOutput42在输入端口、输出端口均设置缓存；是另一种解决“队头阻塞”的方法；交换结构工作速率是端口的S（1<S<N）倍；当S=4时，在均匀业务情况下，CIOQ交换结构的吞吐率可达99%。在输入端口、输出端口均设置缓存；43CrosspointQueuingCrosspointQueuing44缓存位于crossbar交换结构的各个交叉点；各入端口数据首先被存储在XB（cross-pointbuffer）中，是另一种解决“队头阻塞”的方法；各输出端口配置一仲裁器，利用一定的算法（如：轮循）从对应列的多个缓存中选择一个输出；需要N2个缓存，共享性差；由于缓存有限，只能存储较少分组，常常与VOQ结合使用。缓存位于crossbar交换结构的各个交叉点；45交换结构分类—按缓存位置交换结构分类—按缓存位置46最新宽带网课件第三部分(交换1)47宽带网课件第三部分(交换1)宽带网课件第三部分(交换1)48传统电路交换的优缺点。统计复用：用户数据不再固定、周期性地占用时隙，而是根据用户请求和网络资源情况，由网络动态分配。接收端不按固定的时隙关系来提取相应用户数据，而是根据数据中携带的目的地址来接收数据。这种复用方式称为异步时分复用，也称为统计时分复用。传统电路交换的优缺点。49最新宽带网课件第三部分(交换1)50最新宽带网课件第三部分(交换1)51最新宽带网课件第三部分(交换1)52最新宽带网课件第三部分(交换1)53最新宽带网课件第三部分(交换1)54最新宽带网课件第三部分(交换1)55交换结构的评价方法可以从性能和实现成本两方面评价一种交换结构的优劣。性能：在各种可能的业务流模式（包括多播）下，分组经过交换结构的时延、时延抖动、丢失率等。成本：实现交换结构所需的缓存和连线资源的多少，做工程实现时所需花费的人力物力。共享缓存交换结构可以认为是最好的一种。由于充分共享内部缓存资源，资源消耗较少。因此，可以将共享缓存作为一种比较对象。交换结构的评价方法可以从性能和实现成本两方面评价一种交换结构56交换结构中的资源冲突交换结构是由连线和缓存构成的。连线又分输入端连线、内部连线和输出端连线。当多个信元要同时去往一个输出端口，就造成输出端冲突（outputportcontention)，解决办法：选择一个信元从输出端口发出，将其余信元暂时缓存或丢弃。当多个信元要同时经过一个内部连线时，就造成内部连线冲突（internallinecontention)，或称为内部连线阻塞（internallineblocking)。解决办法：暂时缓存信元或丢弃信元。交换结构中的资源冲突交换结构是由连线和缓存构成的。57当资源冲突引起信元暂时缓存，如果缓存里只有一个FIFO(FirstInFirstOut)队列，就会产生队头阻塞（HeadofLineBlocking：HOLBlocking）现象。当资源冲突引起信元暂时缓存，如果缓存里只有一个FIFO(F58研究交换结构要解决的中心问题用多少连线和缓存资源，如何配置资源，在各种可能的业务流量模式下，将冲突的概率减少到可以接受的程度，从而使信元延迟和丢失率达到一定指标。研究交换结构要解决的中心问题59交换结构中的资源冲突

—Outputportcontention交换结构中的资源冲突

—Outputportconten60交换结构中的资源冲突

—InternalLineBlocking交换结构中的资源冲突

—InternalLineBloc61交换结构中的资源冲突

—引起HeadOfLineBlocking交换结构中的资源冲突

—引起HeadOfLineBlo62交换结构的分类

—按外部特性内部无阻塞型：如果一个外部输入端和一个外部输出端是空闲的，则一定可以找到空闲的内部通道将输入端和输出端连接起来。内部阻塞型：如果一个外部输入端和一个外部输出端是空闲的，不一定可以找到空闲的内部通道将输入端和输出端连接起来。交换结构的分类

—按外部特性内部无阻塞型：如果一个外部输入63交换结构的分类switchfabric按资源的使用方法可做如下分类：交换结构的分类switchfabric按资源的使用方法可做64交换结构的分类

—时分复用交换交换结构中的内部资源被所有从输入到输出的信元分时共享，即时分复用。这种内部资源可以是一个总线，也可以是一个缓存。时分复用交换结构可以分为共享媒介型和共享缓存型，共享媒介可以是总线或环。交换结构的分类

—时分复用交换交换结构中的内部资源被所有从输65共享总线型交换结构

从各个输入端口来的信元分时通过总线到达输出端，输出端的AF让目的的为本输出端口的信元通过。总线速率至少等于各个输入端口速率的和。优点是简单、容易支持多播。缺点是各个输出端口的缓存不能共享，缓存的速率至少等于总线速率，且缓存比较大。支持大的交换容量比较困难。共享总线型交换结构从各个输入端口来的信元分时通过总线到66共享缓存型交换结构优点：缓存可以得到充分共享。缺点：缓存的速率限制了交换容量的扩展。共享缓存型交换结构优点：缓存可以得到充分共享。67在时分复用交换中，所有从输入端到输出端的信元经过的是同一个通道。在空分交换中，从输入端到输出端有多条通道，这些通道可以同时工作，多个信元可以同时从输入端到输出端。空分交换结构的交换容量等于通道的带宽乘以可以同时工作的通道数目。因此，扩容的方法就是提高通道的带宽和提高可以同时工作的通道数目。交换结构的分类

—空分交换在时分复用交换中，所有从输入端到输出端的信元经过的是同一个通68空分交换又分为单路径和多路径。单路径空分交换结构中，从一个输入端到一个输出端，只有一条路径；多路径空分交换结构中，则有多条。空分交换又分为单路径和多路径。单路径空分交换结构中，从一个输69空分单路径交换结构

—fullyinterconnectedswitch（全互联交换）空分单路径交换结构

—fullyinterconnecte70空分单路径交换结构

—Crossbar（交叉连接矩阵）空分单路径交换结构

—Crossbar（交叉连接矩阵）71空分单路径交换结构

—Banyanbasedswitch空分单路径交换结构

—Banyanbasedswitch72Banyan-based交换机是由多个2×2的交换单元构成，每个交换单元都是自路由的，即自己可以决定进入信元的输出口。优点：容易用大规模集成电路构成大容量的交换机。缺点：由于是单路径，因此是内部阻塞的。当端口数很多时，阻塞概率增大，性能降低。Banyan-based交换机是由多个2×2的交换单元构成，73空分多路径交换结构空分多路径交换结构74空分多路径交换结构

—AugmentedBanyan(扩张的Banyan)普通的Banyan的交换级数为log2N，扩张的Banyan的交换级数大于log2N。普通的Banyan中，从一个入端口到一个出端口只有一条路径，当竞争失败，信元偏离其预定路径，则必定被丢弃。扩张的Banyan中，从一个入端口到一个出端口的路径有多条。竞争失败的信元可以转往其它路径，也可能到达目的端口。扩张的Banyan性能比普通的Banyan好，但是实现的复杂性增加了。空分多路径交换结构

—AugmentedBanyan(扩张75Benes交换结构以最后一级为对称轴，翻转N×N的Banyan的其它级，就得到N×N的Benes结构。Benes交换结构以最后一级为对称轴，翻转N76空分多路径交换结构——三级Clos在第一级，N个输入线被分为r个组，每个组有n条线，连接到一个交换单元，交换单元有m条输出线，每一条分别连接到第二级的一个交换单元。第二级有m个交换单元，每个交换单元有t条输出线。第三级有t个交换单元，每个交换单元有N/t条输出线。空分多路径交换结构——三级Clos在第一级，N个输入线被分为77三级Clos，N=9，n=3，m=3，有内部阻塞。粗线表示当前被占用的连线。输入端口9到输出端口4或6，无法连通。三级Clos，N=9，n=3，m=3，有内部阻塞。78空分多路径交换结构

—多平面交换多平面交换结构中有多个交换平面可以让信元通过。优点：与单平面交换结构相比，可以降低信元冲突概率，提高性能。同时，可靠性也提高。当交换平面中的一个或多个发生故障时，剩余的交换平面仍然工作，整个交换机仍然可以工作，只不过性能降低了。缺点：实现复杂性增加。为避免乱序，属于同一个packet的信元必须走同一个交换平面。空分多路径交换结构

—多平面交换多平面交换结构中有多个交换平79空分多路径交换结构

—循环交换循环交换结构中，竞争失败的信元从循环端口输出，返回到输入端，竞争下一次机会。优点是可以在一定程度上提高性能。缺点是循环端口使交换机的端口数增加了，且可能出现信元乱序问题，即属于一个packet（IP）的信元没有按进入的顺序到达输出端。必须采用一定的机制来处理。空分多路径交换结构

—循环交换循环交换结构中，竞争失败的信元80交换结构中的缓存共享缓存；OQ（OutputQueuing）；IQ（InputQueuing）；VOQ（VirtualOutputQueuing）；CIOQ（CombinedInputandOutputQueuing）；CrosspointQueuing交换结构中的缓存共享缓存；81共享缓存缓存资源可得到充分共享，各输入、输出端口可访问同一缓存；在每个信元时隙，要完成所有入端口输入信元和全部出端口输出信元的读写操作。因此：memoryaccesscycle<=celllength/(2N×linkspeed)（假设：存储器的总线宽度等于一个cell）例如：对于155Mb/s的53字节信元，如果存储器的访问周期为10ns，则交换结构的端口数小于等于136。共享缓存