Routing and wavelength assignment for hypercube communications embedded on optical chordal ring networks of degrees 3 and 4

Routing and wavelength assignment for realizing hypercube communications on WDM ring networks has been discussed in previous research. To reduce the wavelength requirement, we study routing and wavelength assignment for realizing hypercube communications on WDM ring networks with additional links. We design the embedding schemes and derive the numbers of wavelengths required on WDM chordal ring networks of both degrees 3 and 4. Based on our proposed embedding schemes, we provide the analysis of chord length with optimal number of wavelengths to realize hypercube communications on 3-degree and 4-degree chordal rings. Results show that the wavelength requirement for realizing hypercube communications on optical chordal ring networks is significantly lower than that on optical ring networks. In addition, our research also provides solutions for embedding hypercube graph on chordal rings in graph embedding theory.     

并行LU分解的通信模式在WDM环网上的波长分配算法

波长分配是光网络设计的基本问题，设计波长分配算法是洞察光网络通信能力的基本方法．不同的并行算法具有不同的通信模式，如何在光互连网上实现这些通信模式，是当前一个颇受关注的研究领域．本文基于WDM环网络，针对矩阵的并行LU分解，构造了一种并行LU分解的通信模式，讨论了将该通信模式嵌入在环形光网络中的波长分配问题．在解决该问题的过程中，得到了将一种特殊的二分图结构的通信模式嵌入在环网中的波长分配算法．通过分析和证明得到了在WDM环网上实现该并行LU分解通信模式所需的最小波长数．     

Routing and wavelength assignment for 3-ary n-cube communication patterns in linear array optical networks for n communication rounds

k-ary n-cubes are a class of communication patterns that are employed by a number of typical parallel algorithms. This paper addresses the implementation of parallel algorithms with bidirectional 3-ary n-cube communication patterns on a bidirectional linear array WDM optical networks when the information is transmitted one dimension after another. By giving an embedding scheme ?, we prove the optimal number of wavelengths under ? and design a routing and wavelength assignment strategy of it.     

并行BP算法在WDM环网上的波长分配

波长分配是光网络设计的基本问题,设计波长分配算法是洞察光网络通信能力的基本方法。不同的并行算法具有不同的通信模式,如何在光互联网上实现这些通信模式,同时优化波长分配问题,是当前一个颇受关注的研究领域。神经网络计算的一个重要特点是大规模并行计算,该文基于WDM环网络,讨论了在其上实现并行BP算法的波长分配问题,设计了将完全二分图结构Kmn,通信模式嵌入环网的方案,给出了在WDM环网络上实现并行BP算法所需的最小波长数。     

光RP(k)网络上Hypercube通信模式的波长指派算法

波长指派是光网络设计的基本问题,设计波长指派算法是洞察光网络通信能力的基本方法.基于光RP(k)网络,讨论了其波长指派问题. 含有N=2ⁿ个节点的Hypercube通信模式,构造了节点间的一种排列次序Xn,并设计了RP(k)网络上的波长指派算法.在构造该算法的过程中,得到了在环网络上实现n维Hypercube通信模式的波长指派算法.这两个算法具有较高的嵌入效率.在RP(k)网络上,实现Hypercube通信模式需要max{2,「5(2^n-5/3」}个波长.而在环网络上,实现该通信模式需要复用(N/3+N/12(个波长,比已有算法需要复用「N/3+N/4」个波长有较大的改进.这两个算法对于光网络的设计具有较大的指导价值.     

基于模拟退火遗传算法求解路由和波长分配问题

静态的路由选择和波长分配(RWA)问题是波分复用（WDM）光网络中的一个重要问题,目前常用的处理方法是将RWA问题拆成选路子问题和波长分配子问题。静态RWA问题通常先按某种策略确定建立光路的顺序,然后用启发式的算法加以解决。提出通过模拟退火遗传算法对光路的建立顺序进行优化,然后用基于爬山算法的启发式算法可求解以波长数最小为优化目标的静态RWA问题。通过对ARPANet等5种实际光网络的仿真表明,该算法和文献[5]相比,所用的波长数更少,且大部分优化结果达到最优。     

All-to-All Optical Routing in Chordal Rings of Degree 4

We consider the problem of routing in networks employing all-optical routing technology. In such networks, information between nodes of the network is transmitted as light on fiber-optic lines without being converted to electronic form in between. We consider switched optical networks that use the wavelength-division multiplexing (or WDM) approach. A WDM network consists of nodes connected by point-to-point fiber-optic links, each of which can support a fixed number of wavelengths. The switches are capable of redirecting incoming streams based on wavelengths, without changing the wavelengths. Different messages may use the same link concurrently if they are assigned distinct wavelengths. However, messages assigned the same wavelength must be assigned edge-disjoint paths. Given a communication instance in a network, the optical routing problem is the assignment of {routes} to communication requests of the instance, as well as wavelengths to routes so that the number of wavelengths used by the instance is minimal. We focus on the all-to-all communication instance I _A in a widely studied family of chordal rings of degree 4, called optimal chordal rings . For these networks, we prove exact bounds on the optimal load induced on an edge for I _A , over all shortest-path routing schemes. We show an approximation algorithm that solves the optical routing problem for I _A using at most 1.006 times the lower bound on the number of wavelengths. The previous best approximation algorithm has a performance ratio of 8. Furthermore, we use a variety of novel techniques to achieve this result, which are applicable to other communication instances and may be applicable to other networks. Received July 22, 1998; revised October 14, 1999.     

A multipopulation parallel genetic simulated annealing-based QoS routing and wavelength assignment integration algorithm for multicast in optical networks

In this paper, we propose an integrated Quality of Service (QoS) routing algorithm for optical networks. Given a QoS multicast request and the delay interval specified by users, the proposed algorithm can find a flexible-QoS-based cost suboptimal routing tree. The algorithm first constructs the multicast tree based on the multipopulation parallel genetic simulated annealing algorithm, and then assigns wavelengths to the tree based on the wavelength graph. In the algorithm, routing and wavelength assignment are integrated into a single process. For routing, the objective is to find a cost suboptimal multicast tree. For wavelength assignment, the objective is to minimize the delay of the multicast tree, which is achieved by minimizing the number of wavelength conversion. Thus both the cost of multicast tree and the user QoS satisfaction degree can approach the optimal. Our algorithm also considers load balance. Simulation results show that the proposed algorithm is feasible and effective. We also discuss the practical realization mechanisms of the algorithm.     

波分复用光传输网中波长路由算法的研究进展

光纤正迅速成为主干通信网的标准传介媒质．随着光学器件的发展，使得信号在传输过程中，除了在源、汇节点需要光电转换外，中间节点可保持光传输，这种通信网络叫光传送网．光传送网中的波分复用技术是将整个光纤的带宽分成多个信道，不同的信道可使用不同的波长来同时进行信息传输，从而增加了整个网络的带宽．在光传送网中，实现一个通信请求需要建立一条通信路径，并为该通信路径所经过的每条链上分配一个波长，即所谓波长路由．该文详细介绍了波分复用光传送网中波长路由算法的研究进展，内容包括波长分配算法、网络的信元阻塞率分析、容错和QoS波长路由、多播波长路由、最小化ADM数路由以及基于光或光电连接的并行机模型等．     

Designing a fine‐grained parallel differential evolution with Pareto tournaments for solving an optical networking problem

The future of designing optical networks focuses on the wavelength division multiplexing technology. This technology divides the huge bandwidth of an optical fiber into different wavelengths, providing different available channels per link of optical fiber. However, when it is required to establish a set of demands, a problem comes up. This problem is known as routing and wavelength assignment problem. In this work, we have tackled the static routing and wavelength assignment problem by using multiobjective evolutionary computing. The algorithm applied is the differential evolution but modified with the Pareto tournaments concept for being adapted to the multiobjective context. By using OpenMP, an application programming interface that supports multiplatform shared memory multiprocessing programming, we have demonstrated that this algorithm is highly suitable to be parallelized. We have performed several experiments in multicore systems with two, four, and eight cores, obtaining 97.57% of mean efficiency. To ensure that our heuristic obtains relevant results, we have compared it with a parallel version of the standard fast nondominated sorting genetic algorithm. Finally, in order to show the goodness and effectiveness of the differential evolution with Pareto tournaments algorithm when dealing with this problem, we present diverse multiobjective comparisons with the nondominated sorting genetic algorithm and other approaches published in the literature. Copyright © 2013 John Wiley & Sons, Ltd.     

交换超立方体网络的网络嵌入研究

本文主要研究超立方网和星型网嵌入交换超立方体网络的问题。首先,利用图形嵌入的方法,设计了超立方网到交换超立方体网络的嵌入映射,分析并证明了该嵌入映射所具有的评价性能。其次,给出了星型网到交换超立方体网络两种嵌入策略,也就是所谓的优化嵌入映射和奇偶嵌入映射,进而给出了具有更小的扩张率的星型网到另一种交换超立方体网络的嵌入方法。     

On the complexity and algorithm of grooming regular traffic in WDM optical networks

In SONET/WDM networks, a high-speed wavelength channel is usually shared by multiple low-rate traffic demands to make efficient use of the wavelength capacity. The multiplexing is known as traffic grooming and performed by SONET Add-Drop Multiplexers (SADM). The maximum number of low-rate traffic demands that can be multiplexed into one wavelength channel is called grooming factor. Since SADMs are expensive, a key optimization goal of traffic grooming is to minimize the total number of SADMs in order to satisfy a given set of traffic demands. As an important communication traffic pattern, all-to-all traffic has been widely studied for the traffic grooming problem. In this paper, we study the regular traffic pattern, which is considered as a generalization of the all-to-all traffic pattern. We focus on the Unidirectional Path-Switched Ring (UPSR) networks. We prove that the traffic grooming problem is NP-hard for the regular traffic pattern in UPSR networks, and show that the problem does not admit a Fully Polynomial Time Approximation Scheme (FPTAS). We further prove that the problem remains NP-hard even if the grooming factor is any fixed value chosen from a subset of integers. We also propose a performance guaranteed algorithm to minimize the total number of required SADMs, and show that the algorithm achieves a better upper bound than previous algorithms. Extensive simulations are conducted, and the empirical results validate that our algorithm outperforms the previous ones in most cases. In addition, our algorithm always uses the minimum number of wavelengths, which are precious resources as well in optical networks.     

全光双向网络中的波长转换

在许多光学路由中,对于给定一组通讯路的集合,必须对有公共边的路安排相同的波长.为了充分利用光学的带宽,目的是安排尽量少的波长数.但有时候也考虑使用波长转换器. 如果一个顶点安装转换器,任何经过这个顶点的路都可以改变其波长.因此在某些顶点安装波长转换器后可以将波长的数目减少到一个拥塞界,因此,Wilfong和Winkler定义了一个顶点集 S,在S上安装转换器后,任何路集都可以分配数目等于拥塞界的波长,这样的集合S被称为充分集.研究在双向网络中的最小充分集问题,并把他转化为最小顶点覆盖问题.对此问题给出几个算法.     

Simple, Efficient Routing Schemes for All-Optical Networks

All-optical networks promise data transmission rates several orders of magnitude higher than current networks. The key to high transmission rates in these networks is to maintain the signal in optical form, thereby avoiding the prohibitive overhead of conversion to and from the electrical form, and to exploit the large bandwidth of optical fibers by sending many signals at different frequencies along the same optical link. Optical technology, however, is not as mature as electronic technology. Hence it is important to understand how efficiently simple routing elements can be used for all-optical communication. In this paper we consider two types of routing elements. Both types can move messages at different wavelengths to different directions. If in the first type a message wants to use an outgoing link that is already occupied by another message using the same wavelength, the arriving message is eliminated (and therefore has to be rerouted). The second type can evaluate priorities of messages. If more than one message wants to use the same wavelength at the same time, then the message with the highest priority wins. We prove nearly matching upper and lower bounds for the runtime of a simple and efficient protocol for both types of routing elements, and apply our results to meshes, butterflies, and node-symmetric networks. Received January 6, 1998, and in final form July 17, 1998.     

Optimal Routing Based on Super Topology in Optical Parallel Interconnect

Traditionally the routing in optical parallel interconnect is based on an embedded virtual topology. However, one important fact that has been neglected in the past is that the wavelength assignment to transceivers actually creates additional (logical) links not present in the virtual topology. Such a side-effect can be utilized to significantly reduce the number of hops between a pair of processors. This observation leads to the concept of super topology. This paper considers the hypercube as the embedded virtual topology. The ideas contained here are easily applicable to optical parallel interconnects employing other virtual topologies as well. We present a general framework for embedding a regular topology, the structure of the super topology, the optimal routing algorithm, the distance between any pair of processors and the diameter in the super topology.     

Multihop all-to-all broadcast on WDM optical networks

Wavelength-division multiplexing (WDM) optical networks provide huge bandwidth by allowing multiple data streams transmitted simultaneously along the same optical fiber, with each stream assigned a distinct wavelength. A key issue on WDM optical networks is to minimize the number of wavelengths for communications. All-to-all broadcast (gossiping) is a fundamental communication application on computer/communication networks. It is known that the minimum numbers of wavelengths for realizing gossiping in one-hop of optical routing on the ring and the two-dimensional torus of N nodes are cN/sup 2/ and cN/sup 3/2/, c /spl ap/ 1/8, respectively. These numbers can be too large even for moderate values of N. One approach to reduce the number of wavelengths is to realize gossiping in multihops of routing. We give routing algorithms which realize gossiping in k-hops (k /spl ges/ 2) by O(N/sup 1+1/k/) wavelengths on the ring, O(N/sup 1+1/(2k)/) wavelengths on the 2D torus, and O(N/sup 1+1/(3k)/) wavelengths on the 3D torus on a simple multihop routing model. We also discuss the multihop routing for gossiping on a merge model. We give the upper bounds on the numbers of wavelengths for gossiping in two-hops and three-hops for the ring, 2D torus, and 3D torus on the merge model.     

矩阵乘在一组规则WDM光网络上的波长分配

在光互连网络上实现并行算法的通信模式是当前一个颇受关注的研究领域。矩阵乘法是数值分析领域中一种常用的基本运算,许多数值代数中的计算问题最终会归结到矩阵乘法的计算。提出一种嵌入算法MRDR,在此基础上分析了在一组规则WDM光网络线性阵列、环、mesh、双环网上实现并行矩阵乘通信模式的波长分配问题,并给出了所需的最小波长数。     

Executing algorithms with hypercube topology on torusmulticomputers

Many parallel algorithms use hypercubes as the communication topology among their processes. When such algorithms are executed on hypercube multicomputers the communication cost is kept minimum since processes can be allocated to processors in such a way that only communication between neighbor processors is required. However, the scalability of hypercube multicomputers is constrained by the fact that the interconnection cost-per-node increases with the total number of nodes. From scalability point of view, meshes and toruses are more interesting classes of interconnection topologies. This paper focuses on the execution of algorithms with hypercube communication topology on multicomputers with mesh or torus interconnection topologies. The proposed approach is based on looking at different embeddings of hypercube graphs onto mesh or torus graphs. The paper concentrates on toruses since an already known embedding, which is called standard embedding, is optimal for meshes. In this paper, an embedding of hypercubes onto toruses of any given dimension is proposed. This novel embedding is called xor embedding. The paper presents a set of performance figures for both the standard and the xor embeddings and shows that the latter outperforms the former for any torus. In addition, it is proven that for a one-dimensional torus (a ring) the xor embedding is optimal in the sense that it minimizes the execution time of a class of parallel algorithms with hypercube topology. This class of algorithms is frequently found in real applications, such as FFT and some class of sorting algorithms     

Hierarchical Hypercube Networks (HHN) for Massively Parallel Computers

The hypercube is one of the most widely used topologies because it provides small diameter and embedding of various interconnection networks. For very large systems, however, the number of links needed with the hypercube may become prohibitively large. In this paper, we propose a hierarchical interconnection network based on hypercubes called hierarchical hypercube network (HHN) for massively parallel computers. The HHN has a smaller number of links than the comparable hypercube and in particular, when we construct networks with 2^Knodes, the node degree of HHN with the minimum node degree isO([formula]) while that of hypercube isO(K). Regardless of its smaller node degree, many parallel algorithms can be executed in HHN with the same time complexity as in the hypercube.