Performance of Fast Routing Algorithms in Large Optical Switches Built on the Vertical Stacking of Banyan Structures
Performance of Fast Routing Algorithms in Large Optical Switches Built on the Vertical Stacking of Banyan Structures
复制标题
DOI：
10.1023/b:clus.0000028000.94688.a1
复制
发表时间：
2004-07
期刊：
影响因子：
--
通讯作者：
Md. Mamun-ur-Rashid Khandker;Xiaohong Jiang;P. Ho;S. Horiguchi;Hussein T. Mouftah
中科院分区：
文献类型：
--
作者：
Md. Mamun-ur-Rashid Khandker;Xiaohong Jiang;P. Ho;S. Horiguchi;Hussein T. Mouftah
多个光榕树网络的垂直堆叠是一种新颖的基于榕树的无阻塞光开关方案。该网络保留了榕树网络的小深度和绝对损耗均匀性，但失去了榕树网络良好的自路由能力。为了保证较高的交换速度，VPENS网络中的路由需要特别注意，以便尽可能快地建立路径。N × N无阻塞VWDM网络的最佳全局路由算法的时间复杂度为O（NlogN），对于大规模光开关，这将导致不可接受的长时延。本文基于输入分组的思想，提出了两种适用于VPENS网络的快速路由算法。平面固定路由（PFR）算法和部分随机路由（PRR）算法的时间复杂度分别为O（logN）和O（），FR算法实际上可以将一个虚拟网络转化为一个自路由网络。基于网络模拟器的大量仿真表明，对于大型VLANs网络，我们的新算法可以实现相当低的阻塞概率，同时保证非常高的切换速度。
Vertical stacking of multiple optical banyan networks is a novel scheme for building banyan-based nonblocking optical switches. The resulting network, namely vertically stacked optical banyan (VSOB) network, preserves the properties of small depth and absolutely loss uniformity but loses the nice self-routing capability of banyan networks. To guarantee a high switching speed, routing in VSOB network needs special attentions so that paths can be established as fast as possible. The best known global routing algorithm for anN×Nnonblocking VSOB network has the time complexity of O(NlogN), which will introduce an unacceptable long delay in path establishment for a large size optical switch. In this paper, we propose two fast routing algorithms for the VSOB network based on the idea of inputs grouping. The two algorithms, namely plane fixed routing (PFR) algorithm and partially random routing (PRR) algorithm, have the time complexities of O(logN) and O() respectively, and FR algorithm can actually turn a VSOB network into a self-routing one. Extensive simulation based on a network simulator indicates that for large VSOB networks our new algorithms can achieve a reasonably low blocking probability while guarantee a very high switching speed.