Optical switches are widely considered the most promising candidate to provide ultra-high speed interconnections for future communication and computing systems. Due to the difficulty in implementing an all-optical buffer, optical switches with electronic buffers have been proposed recently. Among these switches, the optical cut-through (OpCut) switch has the capability to achieve low latency and minimize optical-electronic-optical (O/E/O) conversions. We studied the packet-scheduling problem in single-wavelength OpCut switches in our previous work. In this paper, we consider the wavelength division multiplexed (WDM) case. While WDM makes much higher bandwidth possible, it also increases the complexity of the switch architecture, as well as packet scheduling. Our goal is to schedule as many as possible packets to the switch output in each time slot and to maintain the packet order at the same time. While we prove that such an optimal scheduling problem is NP-hard and inapproximable in polynomial time within any constant factor by reducing the set packing problem to it, we present an approximation algorithm that maintains packet order and approximates the optimal scheduling within a factor of √(2Nk) with regard to the number of packets transmitted, where N is the switch size, and k is the number of wavelengths multiplexed on each fiber. This result is in line with the best known approximation algorithm for set packing problem. Based on the approximation algorithm, we also give practical schedulers that can be implemented in the fast optical switches. Simulation results show that the schedulers achieve close performance to the ideal WDM output-queued switch in terms of packet delay under various traffic models.

Optical switches are widely considered as the most promising candidate to provide ultra-high speed interconnections. Due to the difficulty in implementing all-optical buffer, optical switches with electronic buffers have been proposed recently. Among these switches, the Optical Cut-Through (OpCut) switch has the capability to achieve low latency and minimize optical-electronic-optical (O/E/O) conversions. In this paper, we consider packet scheduling in this switch with wavelength division multiplexing (WDM). Our goal is to maximize throughput and maintain packet order at the same time. While we prove that such an optimal scheduling problem is NP-hard and inapproximable in polynomial time within any constant factor by reducing it to the set packing problem, we present an approximation algorithm that maintains packet order and approximates the optimal scheduling within a factor of √2Nk with regard to the number of packets transmitted, where N is the switch size and k is the number of wavelengths multiplexed on each fiber. This result is in line with the best known approximation algorithm for set packing. Based on the approximation algorithm, we also give practical schedulers that can be implemented in fast optical switches. Simulation results show that the schedulers achieve close performance to the ideal WDM output-queued switch in terms of packet delay under various traffic models.

Optical switching architectures with electronic buffers have been proposed to tackle the lack of optical Random Access Memories (RAM). Out of these architectures, the OpCut switch achieves low latency and minimizes optical-electronic-optical (O/E/O) conversions by allowing packets to cut-through the switch. In an OpCut switch, a packet is converted and sent to the electronic buffers only if it cannot be directly routed to the switch output. As the length of a time slot shrinks with the increase of the line card rate in such a high-speed system, it may become too stringent to calculate a schedule in each single time slot. In such a case, pipelining scheduling can be adopted to relax the time constraint. In this paper, we present a novel mechanism to pipeline the packet scheduling in the OpCut switch by adopting multiple “sub-schedulers.” The computation of a complete schedule for each time slot is done under the collaboration of sub-schedulers and spans multiple time slots, while at any time schedules for different time slots are being calculated simultaneously. We present the implementation details when two sub-schedulers are adopted, and show that in this case our pipelining mechanism eliminates duplicate scheduling which is a common problem in a pipelined environment. With an arbitrary number of sub-schedulers, the duplicate scheduling problem becomes very difficult to eliminate due to the increased scheduling complexity. Nevertheless, we propose several approaches to reducing it. Finally, to minimize the extra delay introduced by pipelining as well as the overall average packet delay under all traffic intensities, we further propose an adaptive pipelining scheme. Our simulation results show that the pipelining mechanism effectively reduces scheduler complexity while maintaining good system performance

Packet scheduling algorithms that deliver 100% throughput under various types of traffic enable an interconnect to achieve its full capacity. Although such algorithms have been proposed for electronic interconnects, they cannot be directly applied to WDM optical interconnects due to the following reasons. First, the optical counterpart of electronic random access memory (RAM) is absent; second, the wavelength conversion capability of WDM interconnects changes the conditions for admissible traffic. To address these issues, in this paper, we first introduce a new fiber-delay-line (FDL)-based input buffering fabric that is able to provide flexible buffering delay, followed by a discussion on the conditions that admissible traffic must satisfy in a WDM interconnect. We then propose a weight-based scheduling algorithm, named Most-Packet Wavelength-Fiber Pair First (MPWFPF), and theoretically prove that given a buffering fabric with flexible delay, MPWFPF delivers 100% throughput for input-buffered WDM interconnects with no speedup required. Finally, we further propose the WDM-i SLIP algorithm, a generalized version of the i SLIP algorithm for WDM interconnects, which efficiently finds an approximate optimal schedule with low time complexity. Extensive simulations have been conducted to verify the theoretical results, and test the performance of the proposed scheduling algorithms in input-buffered WDM interconnects.

With the development of Multi-Processor System-on-Chip (MP-SoC) in recent years, the intra-chip communication is becoming the bottleneck of the whole system. Current electronic network-on-chip (NoC) designs face serious challenges, such as bandwidth, latency and power consumption. Optical interconnection networks are a promising technology to overcome these problems. In this paper, we study the routing problem in optical NoCs with arbitrary network topologies. Traditionally, a minimum hop count routing policy is employed for electronic NoCs, as it minimizes both power consumption and latency. However, due to the special architecture of current optical NoC routers , such a minimum-hop path may not be energy-wise optimal. Using a detailed model of optical routers we reduce the energy-aware routing problem into a shortest-path problem, which can then be solved using one of the many well known techniques. By applying our approach to different popular topologies, we show that the energy consumed in data communication in an optical NoC can be significantly reduced. We also propose the use of optical burst switching (OBS) in optical NoCs to reduce control overhead, as well as an adaptive routing mechanism to reduce energy consumption without introducing extra latency. Our simulation results demonstrate the effectiveness of the proposed algorithms.

In this paper, we study packet scheduling in the OpCut switch, a recently proposed optical switching architecture that can be adopted for high-performance parallel computers. The key feature of the OpCut switch is that it allows packets to cut-through the switch whenever possible, such that packets experience minimum delay. Packets that cannot cut-through are received by optical receivers and stored in the electronic buffer, and can be sent to the output ports by the optical transmitters later. Due to its feed-back buffer structure, existing scheduling algorithms cannot be directly applied to the OpCut switch. Keeping packet order also becomesmore challenging in the OpCut switch. In this paper, we propose a scheduling algorithmfor the OpCut switch that achieves overall low packet latency while maintaining packet order. The scheduling algorithmis very simple and can be implemented in hardware. To relax the time constraint on computing a schedule, we further propose a mechanism to pipeline the packet scheduling in the OpCut switch by distributing the scheduling task to multiple “sub-schedulers.” Our simulation results show that the OpCut switch with the proposed scheduling algorithms achieve chose performance to the ideal output-queued (OQ) switch in terms of packet latency, and that the pipelined mechanism effectively reduces scheduler complexity while maintaining satisfactory system performance.

All-optical wavelength-division-multiplexing (WDM) interconnects are a promising candidate for future ultra highspeed interconnections due to the huge capacity of optics. Packet scheduling algorithms that can guarantee 100% throughput under various types of traffic enable an interconnect to achieve its full capacity. However, although such algorithms have been proposed for electronic interconnects, they cannot be directly applied to WDM optical interconnects due to the following reasons. First, almost all of these algorithms depend on the virtual output queue (VOQ) technique which is currently difficult to implement in WDM optical interconnects due to lack of optical RAM; Second, a packet arriving at the input of a WDM interconnect now have more than one output wavelength channels to choose from due to wavelength conversion capability. The former motivates us to search for a new input buffering fabric that is more practical under the current optical technology and can achieve satisfactory performance, and the latter indicates that a new definition of "admissible traffic" may be needed for WDM optical interconnects. In this paper, we first introduce a new fiber- delay-line (FDL) based input buffering fabric that is able to provide flexible buffering delay in WDM optical interconnects. We then give a new definition of "admissible traffic" for a WDM optical interconnect, and propose the most- packet wavelength-fiber pair first (MPWFPF) scheduling algorithm for WDM interconnects using such buffering fabric. We theoretically prove that with the new buffering fabric, MPWFPF can deliver 100% throughput for input-buffered WDM interconnects with no speedup required. Finally, we further propose a faster scheduling algorithm, WDM-iSLIP, that can efficiently determine an approximate optimal schedule with much lower time complexity. Extensive simulations have been conducted to verify the theoretical results, and test the performance of the proposed scheduling algorithms in input-buffered WDM interconnects with the new buffering fabric.

All-optical packet switching is a promising candidate for future high-speed switching. However, due to the absence of optical Ran-dom Access Memory, the traditional Virtual Output Queue (VOQ) based input-queued switches are difficult to implement in optical domain. In this paper we consider output-buffered optical packet switches. We focus on packet scheduling in an output-buffered optical packet switch with limited-range wavelength conversion, aiming at maximizing throughput and minimizing average queuing delay simultaneously. We show that it can be converted to a minimum cost maximum network flow problem. To cope with the high complexity of general network flow algorithms, we further present a new algorithm that can determine an optimal scheduling in O (min {W2,BW}) time, where W is the number of wave-length channels in each fiber and B is the length of the output buffer. We also conduct simulations to test the performance of the proposed scheduling algorithm under different traffic models.

In this paper we study Optical Burst Switching (OBS) networks. Since OBS still suffers high loss ratio due to the lack of buffer at the OBS core routers, we study methods to reduce the loss without using optical buffers. We consider time-slotted OBS called Slotted OBS (SOBS), where routers are synchronized and only send fixed length bursts at the beginning of time slots. Our simulation results show that SOBS reduces the packet loss probability significantly. Moreover, we show that SOBS can be implemented with little or no additional cost and has other advantages such as the better supporting of Quality of Service (QoS).