Architecture and algorithms used to emulate an unconstrained switch

Abstract

Optical switchings technologies are still under research. In this paper, author presented an architecture and three algorithms for using constrained switch to exactly emulate the behavior of an unconstrained (no overhead) switch with a fixed delay. Scheduling algorithms are characterized by the number of configurations (required to cover the batch of requests) and the speedup required to compensate for empty slots. Algorithms described in this paper (EXACT, MIN and DOUBLE) provides a range of speedup versus delay, making emulation universally for various technologies of optical switches.
Autor: Dawid ZYDEK

1. INTRODUCTION

Optical switching technologies [3] have been developed to increase demand for switch bandwidth and port count. Today’s switching architecture require significant time to reconfigure due to mechanical settling, synchronization and other factors. These configuration overheads are in range from milliseconds to few nanoseconds. Efficiently scheduling for optical switches needs special algorithms whose are able to count the current configuration overhead and optimize the final schedule [1], [2]. Algorithms and architectures for unconstrained switches (no overhead switches) often base on the fact, that switches are stateless – configuration is presented by slot time, when there is no difference in switch behavior. We have the configuration overhead, when the current switch configuration differs from the previous slot’s configuration.

The presented emulation architecture accumulates a “batch of switch” requests and then sets new switch configuration. The time spent on reconfiguring switches is reduced by minimizing the number of configurations. However, significantly reduction of the number of configurations can introduce a large number of empty slots and, hence, requires a large speedup.

Each presented algorithm in [1], [2] emulates an unconstrained switch by accumulating configuration requests and generating a corresponding schedule for a constrained switch. Compensate for empty slots caused by scheduling algorithm and cover the configuration overhead is executed by speedup.

2.1. BASIC NOTIONS

NS: Number of connection required to cover batch of request (number of switch per batch).
C: Matrix to accumulate request of switch in slot times (the row and column sum to the number of configuration request).
δ: Switching overhead in slot times (δ=0 for unconstrained switch, δ>0 for constrained switch).
N: Number of switch ports.
Φ: Weight of switching execute (switch configuration).
S: Internal speedup of switch.
P: Switch configuration/permutation matrix.
T: Batch size in slot time.

Configuration: It represented by slot time, where we don’t have switching.

Switching Overhead (δ): We said switching overhead, if the current switch configuration in slot time differs from the previous slot’s configuration.

Configuration Overhead: We have configuration overhead, when the switching overhead occurs.

2.2. PROBLEM DESCRIPTION

Presented architecture and algorithms [1] have restrictions that do not allow changes of the switch configuration of some switching elements while others continue to transmit. Emulation architecture uses standard unconstrained interface (N inputs, N outputs and configuration input) and constrained switch (taking internal connections into consideration) – Figure 1.



Algorithms and architecture described in this paper deals with scheduling of a crossbar switch that can realize any unicast (one-to-one) connection of inputs to outputs (no multicast). This connection is presented by switch configuration P (permutation matrix). In this matrix every element pi,j presents a single connection between input i and output j. When the switch configuration was changed, then our model associates a fixed, no zero switching overhead δ which includes all effects, such as mechanical and synchronization overhead. This fixed delay is expressed in units of slot time.