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.     

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.     

Genetic algorithm for finding minimal cost light-forest of multicast routing on WDM networks

Wavelength division multiplexing (WDM) is an important technique to make use of the large amount of bandwidth in optical fibers to meet the bandwidth requirements of applications. Multicast is the transmission of information from one source to multiple destinations simultaneously. Given a multicast request in a WDM network, the goal is to find a set of light-trees, the assigned wavelengths of light-trees, and construct a light-forest. In this paper, the Minimal cost multicast routing problem (MCMRP) on WDM networks with Tap-and-continue nodes is defined and studied. A new cost model which consists of thewavelength usage and communication cost is defined. The objective is to minimize the sum of the cost of used wavelengths and the communication cost of the light-forest. Specifically, the formulation for the WDM multicast routing problem is given. Because the MCMRP is NP-hard, two genetic algorithms (GAs) are proposed to solve this problem. In the proposed GAs, a path-oriented encoding chromosome is used to represent the routing paths. These routing paths are used to construct source-based light-forests to represent a feasible solution to the multicast request. Moreover, to speed up the convergence of GAs, a Farthest-first greedy heuristic algorithm is proposed and used to generate one of the initial chromosomes. Simulation results demonstrate that the proposed GAs can run efficiently.     

Compact Routing on Chordal Rings of Degree 4

A chordal ring G(n;c) of degree 4 is a ring of n nodes with chords connecting each vertex i to the vertex (i + c) mod n . In this paper we investigate compact routing schemes on such networks. We show an optimal boolean routing scheme for any such network that requires O( log n) bits of storage at each node, and O(1) time to compute a shortest path to any destination. This improves on the results of [16] which gives a linear time algorithm for such networks and [6] where efficient routing schemes for certain fixed values of c were developed. Further, we show several bounds on interval routing schemes for such networks. We show that while every chordal ring has an optimal interval routing scheme with at most intervals on any edge, there exist chordal rings for which any optimal interval routing scheme that labels the vertices around the ring in the graph requires intervals on some edges. Additionally, there are chordal rings which admit no optimal one-interval routing schemes, regardless of the vertex labeling. We also consider interval routing schemes under relaxed requirements for the lengths of paths. Received September 5, 1997; revised December 1, 1997.     

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.     

Efficient fault-tolerant routing in multihop optical WDM networks

This paper addresses the problem of efficient routing in unreliable multihop optical networks supported by Wavelength Division Multiplexing (WDM). We first define a new cost model for routing in (optical) WDM networks that is more general than the existing models. Our model takes into consideration not only the cost of wavelength access and conversion but also the delay for queuing signals arriving at different input channels that share the same output channel at the same node. We then propose a set of efficient algorithms in a reliable WDM network on the new cost model for each of the three most important communication patterns-multiple point-to-point routing, multicast, and multiple multicast. Finally, we show how to obtain a set of efficient algorithms in an unreliable WDM network with up to f faulty optical channels and wavelength conversion gates. Our strategy is to first enhance the physical paths constructed by the algorithms for reliable networks to ensure success of fault-tolerant routing, and then to route among the enhanced paths to establish a set of fault-free physical routes to complete the corresponding routing request for each of the communication patterns     

An optimal inherently stabilizing routing algorithm for star P2P overlay networks

Star graphs possess many desirable properties such as scalable node degrees and diameters, which are essential to facilitate reduced routing table sizes and low maximum path length for routing in large P2P networks. In addition, because a large number of disjoint paths are available and each data/replica in an n‐star can be placed in an (n − 1)‐star, load balancing and alleviation of network bottlenecks can be implemented in star P2P overlay networks. Therefore, star networks have been proposed as viable alternatives to existing overlay topologies for large P2P networks. In this paper, we propose an optimal stabilizing and inherently stabilizing algorithm for routing messages over all disjoint paths between two peers in a star P2P overlay network. The algorithm is optimal in terms of its time complexity in rounds and the length of the longest path traversed by the messages, and fault tolerant due to being stabilizing and inherently stabilizing, allowing the system to withstand transient faults. The algorithm can be used to increase network reliability and survivability in P2P networks. In addition, the usage of all disjoint paths to route messages between two peers leads to increased network bandwidth while distributing the communication overhead across the network and eliminating network bottlenecks in P2P networks. Copyright © 2016 John Wiley & Sons, Ltd.     

Sparse communication networks and efficient routing in the plane

Traditional approaches to network design separate the issues of designing the network itself and designing its management and control subsystems. This paper proposes an approach termed routing-oriented network design, which is based on designing the network topology and its routing scheme together, attempting to optimize some of the relevant parameters of both simultaneously. This approach is explored by considering the design of communication networks supporting efficient routing in the special case of points located in the Euclidean plane. The desirable network parameters considered include low degree and small number of communication links. The desirable routing parameters considered include small routing tables, small number of hops and low routing stretch. Two rather different schemes are presented, one based on direct navigation in the plane and the other based on efficient hierarchical tree covers. On a collection of n sites with diameter D, these methods yield networks with a total of communication links and some bounds on the degree, coupled with routing schemes with constant routing stretch, memory bits per vertex and routes with at most or hops. Received: October 2000 / Accepted: May 2001     

Wavelength Assignment for Realizing Parallel FFT on Regular Optical Networks

Routing and wavelength assignment (RWA) is a central issue to increase efficiency and reduce cost in Wavelength Division Multiplexing (WDM) optical networks. In this paper, we address the problem of wavelength assignment for realizing parallel FFT on a class of regular optical WDM networks. We propose two methods for sequential mapping and shift-reversal mapping of FFT communication pattern to the optical WDM networks concerned. By sequential mapping, the numbers of wavelengths required to realize parallel FFT with 2ⁿ nodes on WDM linear arrays, rings, 2-D meshes and 2-D tori are 2^{n − 1}, 2^{n − 1}, 2^{max (k,n − k) − 1} and 2^{max (k,n − k) − 1} respectively. By shift-reversal mapping, the numbers of wavelengths required are max (3× 2^{n − 3},2), 2^{n − 2}, max (3× 2^{max (k,n − k) − 3},2) and 2^{max (k,n − k) − 2}. These results show that shift-reversal mapping outperforms sequential mapping. Our results have a clear significance for applications because FFT represents a common computation pattern shared by a large class of scientific and engineering problems and WDM optical networks as a promising technology in networking has an increasing popularity.     

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

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

Fault-tolerant routing over shortest node-disjoint paths in hypercubes

This paper presented a routing algorithm that finds n disjoint shortest paths from the source node s to target node d in the n-dimensional hypercube. Fault-tolerant routing over all shortest node-disjoint paths has been investigated to overcome the failure encountered during routing in hypercube networks. In this paper, we proposed an efficient approach to provide fault-tolerant routing which has been investigated on hypercube networks. The proposed approach is based on all shortest node-disjoint paths concept in order to find a fault-free shortest path among several paths provided. The proposed algorithm is a simple uniform distributed algorithm that can tolerate a large number of process failures, while delivering all n messages over optimal-length disjoint paths. However, no distributed algorithm uses acknowledgement messages (acks) for fault tolerance. So, for dealing the faults, acknowledgement messages (acks) are included in the proposed algorithm for routing messages over node-disjoint paths in a hypercube network.     

Simple Algorithms for Multimessage Multicasting with Forwarding

We consider multimessage multicasting over the n processor complete (or fully connected) static network when the forwarding of messages is allowed. We present an efficient algorithm that constructs for every degree d problem instance a communication schedule with total communication time at most 2d , where d is the maximum number of messages that each processor may send (or receive). Our algorithm consists of two phases. In the first phase a set of communications are scheduled to be carried out in d time periods in such a way that the resulting problem is a multimessage unicasting problem of degree d . In the second phase we generate a communication schedule for this problem by reducing it to the Makespan Openshop Preemptive Scheduling problem which can be solved in polynomial time. The final schedule is the concatenation of the communication schedules for each of these two phases. For 2 ≤ l ≤ d , we present an algorithm to generate a communication schedule with total communication time at most \lfloor ( 2 - 1/l ) d \rfloor +1 , for problem instances where each processor needs to send messages to at most ld destinations. We also discuss multimessage multicasting for dynamic networks. Received September 22, 1997; revised August 29, 1998.     

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

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

Routing and wavelength assignment for hypercube in array-based WDM optical networks

Hypercube is one of the most versatile and efficient communication patterns shared by a large number of computational problems. As the number of edges in hypercube grows logarithmically with the size of networks, the complexity of network topologies can be significantly reduced to realize hypercube in optical networks by taking advantage of the parallel transmission characteristic of optical fibers. In this paper, we study the routing and wavelength assignment for realizing hypercube on WDM optical networks including linear arrays and rings with the consideration of communication directions. Specifically, we analyze this problem for both bidirectional and unidirectional hypercubes. For each case, we identify a lower bound on the number of wavelengths required, and design the embedding scheme and wavelength assignment algorithm that uses a provably near-optimal number of wavelengths. In addition, we extend the results to meshes and tori. By our embedding schemes, many algorithms, originally designed based on hypercubes, can be applied to optical networks, and the wavelength requirements can be easily derived using our obtained results.     

基于Photonic Slot Routing的波分复用网络的协议与结构

本文介绍了波分复用技术与全光网络的概念,提出了基于光槽路由的波分复用网络体系结构,讨论了实现光槽与分组传送的方法以及有关的网络存取协议,并给出了全光学网络中网桥与节点的示意性结构。本文的目的是提供一个这种方法的基本描述。     

An Approximation Algorithm for Circular Arc Colouring

We consider the problem of colouring a family of n arcs of a circle. This NP-complete problem, which occurs in routing and network design problems, is modelled as a 0-1 integer multicommodity flow problem. We present an algorithm that routes the commodities in the network by augmenting the network with some extra edges which correspond to extra colours. The algorithm, which relies on probabilistic techniques such as randomized rounding and path selection, is a randomized approximation algorithm which has an asymptotic performance ratio of 1+1/e (approximately 1.37) except when the minimum number of colours required is very small (O(\ln n) ). This is an improvement over the best previously known result [7], which is a deterministic approximation algorithm with a performance ratio of 3/2. The substantial improvement is valuable, for instance in wavelength allocation strategies in communication networks where bandwidth is a precious resource. Received October 25, 1998; revised August 26, 1999, and April 17, 2000.     

Integrated Differentiated Survivability in IP over WDM Networks

The problem of differentiated Multi-Layer Integrated Survivability (MLIS) in IP over WDM networks is studied, which is decomposed into three sub-problems: survivable strategies design (SSD), spare capacity dimensioning (SCD), and dynamic survivable routing (DSR). A related work of network survivability in IP over WDM networks is firstly provided, and adaptive survivable strategies are also designed. A new Integrated Shared Pool (ISP) approach for SCD is then proposed, which is formulated by using integer-programming theory.Moreover, a novel survivable routing scheme called Differentiated Integrated Survivability Algorithm (DISA) for DSR is developed. Simulation results show that the proposed integrated survivability scheme performs much better than other solutions (e.g., “highest layer recovery” and “lowest layer recovery” schemes) in terms of traffic blocking ratio, spare resource requirement, and average traffic recovery ratio in IP over WDM networks.     

The impact of virtual channel allocation on the performance of deterministic wormhole-routed k-ary n-cubes

Virtual channels yield significant improvement in the performance of wormhole-routed networks as they can greatly reduce message blocking over network resources. K-ary n-cubes with deterministic routing have been widely analysed using analytical modelling tools. Most existing models, however, have either entirely ignored the effects of virtual channel multiplexing or have not considered the impact of virtual channels allocation on message latency. This paper discusses two different organisations of virtual channels in k-ary n-cubes, resulting in two deterministic routing algorithms. It then proposes an analytical model to compute message latency for the two routing algorithms. The proposed model is used in a case study to demonstrate the sensitivity of network latency to the way virtual channels are allocated to messages.     

WDM光传送网中基于链路状态等级的动态路由与波长分配算法

提出了两种基于链路状态分级的路由与波长分配算法．分别为链路等级优先的动态路由与波长分配算法（LFLS-DRAW）和满足等级要求的动态路由与波长分配算法（RLSDRAW）算法．理论分析表明，基于链路状态分级的路由与波长分配算法的计算复杂度与同类算法相当，且与其它算法相比具有一定的优越性．仿真结果表明．基于链路状态分级的路由与波长分．配算法在计算时间和平均路由跳数相近的情况下．所选择路径的路由状态等级较高．具有较强的负载均衡能力，可以有效降低网络的拥塞概率．     

Path-Based Multicast Communication in Wormhole-Routed Unidirectional Torus Networks

This paper addresses the problem of one-to-many, or multicast, communication in wormhole-routed,n-dimensional torus networks. The proposed methods are designed for systems that support intermediate reception, which permits multidestination messages to be pipelined through several nodes, depositing a copy at each node. A key issue in the design of such systems is the routing function, which must support both unicast and multicast traffic while preventing deadlock among messages. An efficient, deadlock-free routing function is developed and used as a basis for a family of multicast algorithms. TheS-torusmulticast algorithm uses a single multidestination message to perform an arbitrary multicast operation. TheM-torusalgorithm is a generalized multiphase multicast algorithm, in which a combination of multidestination messages is used to perform a multicast in one or more communication steps. Two specific instances of the M-torus algorithm, theM_d-torusandM_u-torusmulticast algorithms, are presented. These algorithms produce contention-free multicast operations and are deadlock-free under all combinations of network traffic. A simulation study compares the performance of the different multicast algorithms, and implementation issues are discussed. The results of this research are applicable to the design of architectures for both wormhole-routed massively parallel computers and high-speed local area networks with wormhole-routed switch fabrics.