In recent years, hybrid optical/electrical data center network has been considered a promising interconnection technology for large-scale data centers, since it can efficiently provide sufficient bandwidth. A key issue in hybrid optical/electrical data center networks is finding a way to offload burst traffic through optical circuit switches (OCSs), such that the burst traffic can be offloaded timely while the system operation overhead is low. This article extends the idea of Mahout to propose a local-push asynchronous optical traffic offloading strategy, in which each ToR switch offloads the traffic via the OCSs if its queue length is larger than a preset threshold, and transfers the traffic back to electrical packet switches (EPSs) when the backlog is empty. To seek a proper threshold, we develop a fluid-flow model to analyze the performance of the proposed traffic offloading strategy, from which we demonstrate that there is a trade-off between the mean delay of the traffic and the system operation overhead in a typical data center network. Based on such a trade-off, we provide a rule to select the buffer threshold. We show via simulation that the proposed optical traffic offloading strategy with the threshold selection rule outperforms C-through.

In recent years, connection-based slotted-Aloha (CS-Aloha) has been proposed to improve the performance of random access networks. In this protocol, each node attempts to send a request to the access point (AP) before packet transmission. Once this attempt is successful, the node can transmit up to M packets to the AP. Previous works indicated that the CS-Aloha can achieve a higher throughput than the classical slotted Aloha (S-Aloha), if M is large enough. However, the impact of M on the delay performance and stability is still unknown. To solve this problem, we model each node of the CS-Aloha as a vacation queueing system with limited service discipline, where we consider each batch of packet transmissions as a busy period, and the attempt process between two successive busy periods as a vacation period. We derive the delay distribution, which is turned out to be a geometric distribution. From this result, we further obtain the mean delay, the delay jitter, and the bounded delay region. Our analysis shows that increasing M can accelerate the clean-up of the buffer in each node and thus decrease the attempt rate, which can reduce the average time needed by a node to make a successful attempt. As a result, a large M can decrease the mean delay and the delay jitter, and enlarge the bounded delay region. Also, we obtain the condition to achieve the minimum mean delay under different values of M .

Optical shuffle-exchange networks (SENs) have wide application in different kinds of interconnection networks. This article proposes an approach to construct modular optical SENs, using a set of arrayed waveguide gratings (AWGs) and tunable wavelength converters (TWCs). According to the wavelength routing property of AWGs, we demonstrate for the first time that an AWG is functionally equivalent to a classical shuffle network by nature. Based on this result, we devise a systematic method to design a large-scale wavelength-division-multiplexing (WDM) shuffle network using a set of small-size AWGs associated with the same wavelength set. Combining the AWG-based WDM shuffle networks and the TWCs with small conversion range, we finally obtain an AWG-based WDM SEN, which not only is scalable in several ways, but also can achieve 100% utilization when the input wavelength channels are all busy. We also study the routing and wavelength assignment (RWA) problem of the AWG-based WDM SEN, and prove that the self-routing property and the nonblocking routing conditions of classical SENs are preserved in such AWG-based WDM SEN.

The traffic of large-scale interconnection networks is increasingly showing high-speed and high-burst characteristics, which imposes a big challenge on the performance of switching systems. However, the existing scheduling and routing algorithms for the switching systems have either high computation complexity or high operation cost, which cannot keep up with the rapid development of the Internet. To cope with this problem, we present a parallel scheduling algorithm and a parallel routing algorithm for large-scale high-speed switching systems in this paper. Starting from the edge coloring problem of bipartite graphs, this paper first presents algebraic edge coloring approach, based on which we design the scheduling and routing algorithms. Our simulation results show that these algorithms possess the following features: 1) They have a low computation complexity; 2) They can provide 100% throughput; 3) They can achieve end-to-end delay in microseconds; 4) They do not require any hardware acceleration, and do not lead to packet out-of-sequence problem.

Delayed offloading is a widely accepted solution for mobile users to offload their traffic through Wi-Fi when they are moving in urban areas. However, delayed offloading enhances offloading efficiency at the expense of delay performance. Previous works mainly focus on the improvement of offloading efficiency while keeping delay performance in an acceptable region. In this paper, we study the impact of the user mobility on delayed data offloading in respect to the tradeoff between offloading efficiency and delay performance. We model a mobile terminal with delayed data offloading as an M/MMSP/1 queuing system with three service states. To be practical, we consider the feature of currently commercial mobile terminals in our analysis. Our analytical result shows that the mobility of the users can reduce the queueing delay incurred by the delayed offloading, and suggests that delayed offloading strategies can be optimized according to the mobility of the terminals once the delay requirement is given.

The three-stage fault-tolerant Clos network, where extra switch modules exist in the middle stage in case of switch failures, is widely used in the design of OTN switches. This paper proposes a route assignment algorithm for such Clos networks by solving its counterpart in edge-coloring problem. Based on complex coloring, a novel edge coloring method, the proposed algorithm possesses two properties. First, our algorithm can make full use of extra switch modules in the middle stage of Clos network. The extra switch modules provide additional colors for edge coloring, which help to reduce the running time of the coloring process remarkably. Second, our algorithm can be implemented in a parallel manner to further shorten the running time. The proposed routing algorithm achieves a low complexity of O(√N(m-1)/m-1+(m-√N)logN logN), where N is the network size and m is the number of switch modules in the middle stage. The performance of our algorithm has been verified by extensive simulation experiments.

Along with the recent surge in scale expansion of data centers, the interconnection scheme is facing a grave challenge. A huge amount of cables between the switches make the system maintenance and heat dissipation extremely difficult. A promising solution to this problem is using the arrayed waveguide grating (AWG), which can provide a set of wavelength links between its inputs and outputs. However, the scalability of the AWG-based interconnection scheme is restricted by the coherent crosstalk and the wavelength granularity of AWGs. In this paper, we propose a generic modular AWG-based interconnection scheme with scalable wavelength granularity for mega data centers. We first devise a matrix-based method to decompose the AWG into a three-stage network of smaller AWGs, while preserving the nonblocking wavelength routing property of the AWGs. We then introduce the concept of wavelength independency based on the partitioning of the optical connections, such that modular AWGs in the network can reuse the same wavelength set with smaller granularity. We show that the proposed modular AWG-based interconnection network can simplify the cabling complexity of data center networks, while preserving the same function and bandwidth as the original data center network.

This paper explores the scheduling problem of input-queued switches, based on a new algebraic method of edge coloring called complex coloring. The proposed scheduling algorithm possesses three important features inherent from complex coloring: parallelizability, optimality and rearrangeability. Parallelizability makes the algorithm running very fast in a distributed manner, optimality ensures that the algorithm always returns a proper connection pattern with the minimum number of required colors, and rearrangeability allows partially re-scheduling the existing connection patterns if the traffic patterns only changes slightly. The amortized time complexity of the proposed parallel scheduling algorithm, in terms of the time to compute a matching in a timeslot, is O(log N), where N is the switch size. As for the scalability of input-queued switches, due to its low complexity, our algorithm can achieve nearly 100 percent throughput and provide acceptable queuing delay when N is large. Furthermore, the complex coloring method naturally provides an adaptive solution to non-uniform input traffic pattern. Thus, the proposed parallel scheduling algorithm is highly robust in the face of traffic fluctuations.

In wavelength-division-multiplexing (WDM) switches, such as arrayed-waveguide-grating (AWG)-based Clos networks, the supporting of multicast traffic must rise to the challenge of route and wavelength assignment (RWA) problem. In this paper, we study the non-blocking multicast RWA problem in two phases with respect to the cascaded combination of an AWG-based broadcast Clos network, called copy network, and a point-to-point AWG-based Clos network. In phase one, input requests generate broadcast trees in the copy network, and then point-to-point connections are established in the AWG-based Clos network in the second phase. The Clos-type AWG-based multicast networks can be constructed from modular AWGs of smaller sizes with the purpose of minimizing the number of wavelengths required and reducing the tuning range of the wavelength selective converters (WSCs). For solving the multicast RWA problem, we extend the rank-based routing algorithm for traditional space-division broadcast Clos networks such that broadcast trees can also be generated in the WDM copy network in a contention-free manner. However, due to wavelength routing properties of AWGs, the subset of requests input to each subnetwork in the middle stage may not satisfy the precondition of the rank-based RWA algorithm. Nevertheless, we prove that this problem can be solved by cyclically shifting the indices of wavelengths in each subnetwork, which provides the key to recursively route the multicast requests in a non-blocking and contention-free manner in the decomposed AWG-based broadcast Clos network. The time complexity of the proposed multicast RWA algorithm is comparable to that of an AWG-based unicast Clos network.

In this paper, we study the power efficiency and delay performance of the burst mode transmission (BTR) strategy for the IEEE 802.3az energy efficient Ethernet (EEE) protocol. In the BTR strategy, the Ethernet interface goes to sleep once its transmission buffer becomes empty and wakes up as soon as the first arrival has waited for time r or the N-th frame arrives at the interface. Based on the number of arrivals during the vacation time, a new approach is proposed to analyze the M/G/1 queue with vacation times that are governed by the arrival process and the r and N parameters of BTR strategy. Our key idea is to establish the connection between the vacation time and the arrival process to account for their dependency. We first derive the distribution of the number of arrivals during a vacation time based on an event tree of the BTR strategy, from which, we obtain the mean vacation time and the power efficiency. Next, from the condition on the number of arrivals at the end of a vacation period, we derive a generalized P-K formula of the mean delay for EEE systems, and prove that the classical P-K formula of the vacation model is only a special case when the vacation time is independent of the arrival process. Our analysis demonstrates that the r policy and N policy of the BTR strategy are compensating each other. The r policy ensures the frame delay is bounded when the traffic load is light, while the N policy ensures the queue length at the end of vacation times is bounded when the traffic load is heavy. These results, in turn, provide the rules to select appropriate r and N. Our analytical results are confirmed by simulations.

Despite the high throughput and low complexity achieved by input scheduling based on Birkhoff-von-Neumann (BvN) decomposition, the performance of the BvN switch becomes less predictable when the input traffic is bursty. In this paper, we propose a deflection-compensated BvN (D-BvN) switch architecture to enhance the quasistatic scheduling based on BvN decomposition. D-BvN switches provide capacity guarantee for virtual circuits (VCs) and deflect bursty traffic when overflow occurs. The deflection scheme is devised to offset the excessive buffer requirement of each VC when input traffic is bursty. The design of our conditional deflection mechanism is based on the fact that it is unlikely that the traffic input to VCs is all bursty at the same time; most likely, some starving VCs have spare capacities when some other VCs are in the overflow state. The proposed algorithm makes full use of the spare capacities of those starving VCs to deflect the overflow traffic to other inputs and provide bandwidth for the deflected traffic to re-access the desired VC. Our analysis and simulation results show that this deflection-compensated mechanism can support BvN switches to achieve close to 100% throughput of offered load even with bursty input traffic, and reduces the average end-to-end delay and delay jitter. Also, our result indicates that the packet out-of-sequence probability due to deflection of overflow traffic is negligible, and thus, only a small re-sequencing buffer is needed at each output port. We also compare D-BvN with the well-established online scheduling algorithm iSLIP, and the result demonstrates that D-BvN outperforms iSLIP in terms of the throughput of offered load when the traffic is non-uniform or the traffic load is not very high.

The three-stage Clos networks remain the most popular solution to many practical switching systems to date. The aim of this paper is to show that the modular structure of Clos networks is invariant with respect to the technological changes. Due to the wavelength routing property of arrayed-waveguide gratings (AWGs), non-blocking and contention-free wavelength-division-multiplexing (WDM) switches require that two calls carried by the same wavelength must be connected by separated links; otherwise, they must be carried by different wavelengths. Thus, in addition to the non-blocking condition, the challenge of the design of AWG-based multistage switching networks is to scale down the wavelength granularity and to reduce the conversion range of tunable wavelength converters (TWCs). We devise a logic scheme to partition the WDM switch network into wavelength autonomous cells and show that the wavelength scalability problem can be solved by recursively reusing similar, but smaller, set of wavelengths in different cells. Furthermore, we prove that the rearrangeably non-blocking (RNB) condition and route assignments in these AWG-based three-stage networks are consistent with that of classical Clos networks. Thus, the optimal AWG-based non-blocking Clos networks also can achieve 100% utilization when all input and output wavelength channels are busy.

The Ethernet passive optical network (EPON) has recently emerged as the mainstream of broadband access networks. The registration process of EPON, which is defined by the IEEE 802.3av standard, is a multi-point control protocol within the media access control layer. As with other contention-based channel access methods, such as ALOHA and CSMA, stability and delay are critical issues concerning the performances of implementing the protocol on systems with finite channel capacity. In this paper, the registration process of an EPON subscriber, called optical network units (ONUs), is modeled as a discrete-time Markov chain, from which we derive the fundamental throughput equation of EPON that characterizes the registration processes. The solutions of this characteristic equation depend on the maximum waiting time. The aim of our stability analysis is to pinpoint the region of the maximum waiting time that can guarantee a stable registration throughput and a bounded registration delay. For a maximum waiting time selected from the stable region, we obtain the expression of registration delay experienced by an ONU attempting to register. All analytic results presented in this paper were verified by simulations.

Functional decomposition of Boolean functions has a profound influence on all quality aspects of cost-effectively implementing modern digital systems and data-mining. The relational databases are multivalued tables, which include any truth tables of logic functions as special cases. In this article, we propose a relational database approach to the decomposition of logic circuits. The relational algebra consists of a set of well-defined algebraic operations that can be performed on multivalued tables. Our approach shows that the functional decomposition of logic circuits is similar to the normalization of relational databases; they are governed by the same concepts of functional dependency (FD) and multivalued dependency (MVD). The completeness of relational algebra demonstrated by our approach to functional decomposition reveals that the relational database is a fundamental computation model, the same as the Boolean logic circuit.

The traffic matrix decomposition provides an effective scheduling approach to guarantee capacity of services supported by input queued packet switches. The Birkhoff-von Neumann (BvN) decomposition is widely used to express the doubly stochastic rate matrix as a weighted sum of permutation matrices. The switch then schedules these permutation matrices, using weights corresponding to the coefficients in the decomposition. In a Clos network, each permutation matrix corresponds to a connection pattern in the middle stage. If we regard this set of predetermined connection patterns as a code book, scheduling incoming packets in the input buffer according to predetermined connection patterns is a process similar to the encoding of source signals. In light of the concerns on delay jitter, it is expected that the scheduling should be as smooth as possible. A measurement of smoothness is defined in terms of interstate time of the scheduled sequence. In this paper, we show that the smoothness of scheduling is bounded by the entropy of BvN decomposition, and satisfies the Kraft's inequality. The optimal scheduling can be achieved if and only if the Kraft's equality holds.

Buffers are essential components of any packet switches for resolving contentions among arriving packets. Currently, optical buffers are composed of Fiber Delay Lines (FDL), whose blocking and delay behavior differ drastically from that of conventional RAM in at least two folds: (i) only multiples of discrete time delays can be offered to arriving packets; (ii) a packet must be dropped if the maximum delay provided by optical buffer is not sufficient to avoid contention, this property is called balking. As a result, optical buffers only have finite time resolution, which may lead to excess load and prolong the packet delay. In this paper, the closed-form expressions of blocking probability and mean delay are derived to explore the tradeoff between buffer performance and system parameters, such as the length of the optical buffer, the time granularity of FDLs, and to evaluate the overall impact of packet length distribution on the buffer performance.

A scheduling algorithm based on Huffman algorithm and Weighted Fair Queueing (WFQ) is proposed. The aim of this scheduler is to provide good fairness and smooth output traffic, while remaining simple in operation. Since WFQ can only guarantee good relative fairness between two flows, we apply WFQ on adjacent nodes of the Huffman binary tree. Therefore, it secures a good worst case fairness result. The Huffman algorithm also suggests that the number of comparisons needed is optimal among all possible tree structures. Our algorithm is able to achieve delay, relative fairness and worst case fairness bounds in the order of O(1) while the complexity is O(logN), where N is the number of flows.

In this paper, we propose a multistage switch architecture for optical burst switching based on dual shuffle-exchange network (DSN). DSN is a deflection, self-routing network which exerts small penalty on each deflection. Its operational simplicity and bufferless nature are highly preferable in the optical environment. It can also be showed that this architecture is able to achieve high throughput even with blocking internal modules.

Energy conserving design is the research focus to prolong the lifetime of sensor networks. A simple and effective way to save energy is to place nodes in sleep mode, however, sleep mode corresponds to low power consumption as well as to reduced operation capacity and increased latency. We derive a queuing model for the sensor node and performance models for the whole sensor network. We use our models to study the node and network performance metrics in terms of throughput, energy consumption and packet delivery delay. Our analytical models enable us to explore the trade-off existing between sensor sleep/active dynamics and those performance metrics. We validate our analytical results through extensive simulations and simulation results match well with our analysis and show the accuracy of our framework.

In this paper, we propose a novel MAC protocol, namely broadcast control (BC) protocol, to enhance the standard IEEE 802.11. In our BC protocol, the access point (AP) collects the contention information of the mobile stations and sends back the optimized control information to guarantee that the communication overhead of the whole wireless local area network (WLAN) maintains in low level. The BC protocol can be implemented by making some negligible modification of standard 802.11 protocols. The performance of BC strategy is compared with the IEEE 802.11 MAC protocols via extensive simulations, which show that BC strategy can significantly elevate the efficiency regardless the number of active mobile stations in the WLAN