Routing in Coloured Sparse Optical Tori by Using Balanced WDM and Network Sparseness

Routing in Coloured Sparse Optical Tori by Using Balanced WDM and Network Sparseness

Risto Honkanen (Kajaani University Consortium, Kajaani, Finland) and Ville Leppänen (Department of Information Technology, University of Turku, Turku, Finland)
Copyright: © 2012 |Pages: 11
DOI: 10.4018/jdst.2012100105
OnDemand PDF Download:
$30.00
List Price: $37.50

Abstract

The authors present a WDM (Wavelength-Division Multiplexing) based all-optical network architecture, and study scheduled routing on it. Their architecture can be seen as a communication system of parallel multi-core computer or a large-scale high bandwidth routing switch of e.g., telecommunication network. The goal is to construct such a scalable architecture and a supporting routing protocol for it so that no electro-optical conversions are needed on the routing paths, all packets are routed along one of the shortest paths, processor nodes can inject packets constantly into the network, and all the packets injected into the routing machinery reach their targets without collisions. The authors’ CSOT is a sparse network. A large fraction of the nodes are intermediate nodes instead of processor nodes. Only the processor nodes are sources and sinks of packets. The number of all nodes is and is the number of processor nodes in our construction. For scheduled routing to work, the authors consider routing problems as a set of h-relations. They achieved work-optimal routing of -relations for a reasonable size of . The efficiency of routing is based on routing latency hiding which is made possible by WDM and sparseness based increase bandwidth per processor node.
Article Preview

Introduction

Efficient data routing has many different kinds of applications as there are a lot of contexts with a need to transfer a huge amount of messages between a large number of sources and destinations. Such settings appear in the Internet and telecommunication network routing switches as well as in implementing shared memory abstractions on top of distributed memory systems. Requirements concerning switching differ in these settings. In some cases only the bandwidth of the switch is most important whereas in some cases it is the switching speed and expected delay. Also scalability and simplicity of the solution are important factors.

Efficiency of shared memory based throughput computing relies on the idea to hide the memory access latencies by enabling the nodes to do something useful while memory requests are routed. The latency of routing memory operations can be hidden by being able to execute instructions from several independent threads in each processor node, if there are enough network bandwidth and sufficient number of executable threads. This requires certain properties from the routing machinery.

Our contribution to this setting is an all-optical sparse architecture with a scheduled routing protocol for routing h-relations very efficiently. In particular, our construction is truly scalable, supports very fast switching as no electro-optical conversions are needed on the routing paths, all packets are routed along one of the shortest paths, processor nodes can inject packets at each step into the network, and all the packets injected into the routing machinery reach their targets without collisions.

Our work is motivated by studying to support throughput computing via so-called emulated shared memory with a network of distributed memory modules (Fortune & Wyllie, 1978; Valiant, 1990). If a parallel algorithm has enough parallel “slackness,” i.e., large enough number of independent parallel threads at each processor, the implementation of shared memory can be reduced to efficient routing of an -relation (Valiant, 1990). An -relation is a routing problem where each processor has at most packets to send and is the target of at most packets (Adler, Byers, & Karp, 1995). An implementation of an -relation is said to be work-optimal at cost c, if all the packets arrive at their targets in time ch. A precondition of work-optimality is that h is greater than the diameter of the network and the network can move packets in each step, where P is the number of processors. Otherwise slackness cannot be used to “hide” the latency due to travel across the diameter (Adler, Byers, & Karp, 1995; Honkanen, Leppänen, & Penttonen, 2001).

Some architectural solutions satisfying the above are presented, e.g., by Valiant (1990) and by Sibeyn (1998).

Complete Article List

Search this Journal:
Reset
Open Access Articles
Volume 8: 4 Issues (2017)
Volume 7: 4 Issues (2016)
Volume 6: 4 Issues (2015)
Volume 5: 4 Issues (2014)
Volume 4: 4 Issues (2013)
Volume 3: 4 Issues (2012)
Volume 2: 4 Issues (2011)
Volume 1: 4 Issues (2010)
View Complete Journal Contents Listing