Search

Vertically stacked pruned optical banyan networks with extra planes (in short, EP-VSOB networks) have lower switch count and optimal time complexity (O(log2 N)) for routing N input requests. However, blocking probability is relatively higher than that of a VSOB networks using regular banyan planes. In the EP-VSOB architecture, the number of pruned planes has always been considered as N , and a few extra planes (regular banyan) have been added with these pruned planes. In this paper we present the results of blocking analysis of a more generalized architecture in which the number of pruned planes can be 2x, where x ⩾ 0 in addition to the variable extra planes. This generalization helps us make a compromise between different constraints and performance metrics. Our simulation results show that for some given performance requirements (e.g. cost, speed or blocking probability) we can choose a network that has lower switch count compared to N -plane pruned crosstalk-free optical banyan networks. For example, to ensure blocking probability

In this paper, we address the issue of faster connection establishment in a large vertically stacked optical Banyan (VSOB) network. The best known global routing algorithm, which turns an N × N crosstalk-free VSOB network into a rearrangeably non-blocking one, has time complexity O ( N log N ). This is quite large compared to O ( N log N ) time complexity of a single plane banyan network, which is a self-routing network with very high blocking probability. For a large size of switching network this O ( N log N ) time complexity may result unacceptably long delay. Therefore, an optical network with very low blocking probability and O ( N log N ) time complexity will be useful. Previously proposed Plane Fixed Routing (PFR) algorithm has O (log N ) time complexity but results in higher than 2% blocking probability with zero-crosstalk constraint for a network as large as 4096 × 4096 at full load. In this paper, first we propose the pruning of VSOB networks that reduces the hardware cost by almost 30%. The networks can still use the PFR algorithm and results in the same blocking probability. However, we show that the blocking probability can be reduced dramatically while keeping the optimum time complexity O (log N ) by allowing only a small amount of crosstalk. Then, we propose a new kind of switching networks in which extra regular banyan planes have been added with the pruned VBOS (P-VSOB) networks. Necessary routing algorithms, namely, PFR_RS and PFR_LS show that this new switching network can reduce the blocking probability to very low value even with zero-crosstalk constraint while keeping the hardware cost 3almost the same as for P-VSOB networks. Both these algorithms also have time complexity O ( N log N ).

Vertical stacking of multiple optical banyan networks is a novel scheme for building banyan-based nonblocking optical switches. The resulting network, namely vertically stacked optical banyan (VSOB) network, preserves the properties of small depth and absolutely loss uniformity but loses the nice self-routing capability of banyan networks. To guarantee a high switching speed, routing in VSOB network needs special attentions so that paths can be established as fast as possible. The best known global routing algorithm for an N × N nonblocking VSOB network has the time complexity of O(Nlog N), which will introduce an unacceptable long delay in path establishment for a large size optical switch. In this paper, we propose two fast routing algorithms for the VSOB network based on the idea of inputs grouping. The two algorithms, namely plane fixed routing (PFR) algorithm and partially random routing (PRR) algorithm, have the time complexities of O(log N) and O$(\sqrt{N})$ respectively, and FR algorithm can actually turn a VSOB network into a self-routing one. Extensive simulation based on a network simulator indicates that for large VSOB networks our new algorithms can achieve a reasonably low blocking probability while guarantee a very high switching speed.

Banyan networks are attractive for constructing directional coupler (DC)-based optical switching networks for their small depth and self-routing capability. Crosstalk between optical signals passing through the same DC is an intrinsic drawback in DC-based optical networks. Vertical stacking of multiple copies of an optical banyan network is a novel scheme for building nonblocking (crosstalk-free) optical switching networks. The resulting network, namely vertically stacked optical banyan (VSOB) network, preserves all the properties of the banyan network, but increases the hardware cost significantly. Though much work has been done for determining the minimum number of stacked copies (planes) required for a nonblocking VSOB network, little is known on analyzing the blocking probabilities of VSOB networks that do not meet the nonblocking condition (i.e., with fewer stacked copies than required by the nonblocking condition). In this paper, we analyze the blocking probabilities of VSOB networks and develop their upper and lower bounds with respect to the number of planes in the networks. These bounds depict accurately the overall blocking behaviors of VSOB networks and agree with the conditions of strictly nonblocking and rearrangeably nonblocking VSOB networks respectively. Extensive simulation on a network simulator with both random routing and packing strategy has shown that the blocking probabilities of both strategies fall nicely within our bounds, and the blocking probability of packing strategy actually matches the lower bound. The proposed bounds are significant because they reveal the inherent relationships between blocking probability and network hardware cost in terms of the number of planes, and provide network developers a quantitative guidance to trade blocking probability for hardware cost. In particular, our bounds provide network designers an effective tool to estimate the minimum and maximum blocking probabilities of VSOB networks in which different routing strategies may be applied. An interesting conclusion drawn from our work that has practical applications is that the hardware cost of a VSOB network can be reduced dramatically if a predictable and almost negligible nonzero blocking probability is allowed.

During the path establishment, states of switching elements in the switch network may need rearrangement. C.-T. Lea et. al [1] has first mentioned about the rearrangement behavior of the switching networks. He has analyzed the frequency of its occurrence using stochastic method. It is notable that rearrangement behavior of switching network includes rearrangement of connections and rearrangement of switching elements. Optimization of rearrangement cost of switching network can save both power and time, which in turn can increase the switching speed. This paper determines the rearrangement cost of strictly non-blocking Vertically Stacked Optical Banyan networks in terms of switching elements. We believe that our result will be helpful in designing, implementing and analyzing different algorithms of the networks.

Optical banyan networks can be made rearrangeably nonblocking using its multiple copies in unison. Such rearrangeably nonblocking networks are known as vertically stacked optical banyan (VSOB) networks. Centralized control routing algorithm for this rearrangeably nonblocking optical banyan networks has time complexity O ( N log2 N ). A distributed control routing algorithm with time complexity O (log2 N ) has been proposed recently in which authors have considered N completely connected processors to take routing decision which practically would be very difficult to implement for large N . In this paper we propose two distributed control routing algorithms where processors are loosely connected. In the first algorithm ) ( N O processors work in pipelined fashion, and take the routing decision in linear time. In the second algorithm N inputs synchronously hunt for a free route among ) ( N O copies of a banyan network using a look up table. This algorithm has time complexity ) ( N O . Also the processors do not need to be completely connected, which makes it more practical for implementation.

Due to its nice properties of small depth and absolute signal loss uniformity, vertical stacking of optical banyan (VSOB) networks becomes an attractive optical switch architecture. It is expected that a VSOB switch will have a good fault-tolerant capability, because it consists of multiple banyan networks. To verify our expectation, in this paper we study the overall blocking behavior of a VSOB switch by establishing an upper bound on its blocking probability in presence of link failures. The upper bound accurately depicts the overall blocking behavior of a VSOB switch for a reasonable small link failure rate, as verified by extensive simulation results. Although our upper bound demonstrates that VSOB switches have a good fault-tolerance property, it reveals a surprising overall blocking behavior of a faulty VSOB switch that, not as we usually expected, the blocking probability of the switch may not always increase monotonously with the increase of link failure rate. Our upper bound is significant, because it provides switch designers a quantitative tool to determine the effects of link failure on the blocking behavior and to estimate the maximum blocking probability of a VSOB switch, in which different routing algorithms can be applied with a guaranteed performance in terms of blocking probability and hardware cost.