Although optical circuit switch (OCS) based data center network (DCN) can offer high-bandwidth and low-power consumption interconnection for server blocks, it has slow reconfiguration speed and thus is not well-suited to handling highly bursty traffic. Despite several Valiant load-balancing (VLB) type algorithms designed to mitigate this mismatch, they cause notable residual traffic fluctuation, measured by second moment of traffic rate. This leads to a notable tail distribution of flow completion time (FCT). Thereby, this paper proposes a second-moment VLB (sVLB), leveraging the fact that all optical links from the same source rarely burst simultaneously. Different from previous VLB-type algorithms, sVLB utilizes spare capacity in the DCN for load balancing. Specifically, it offloads the bursty traffic from optical links to other intermediate blocks, employing only spare capacity on temporarily idle optical links, and these blocks subsequently route the bursty traffic to its destination. We introduce an sVLB-based framework, which additionally provides a suitable optical topology for sVLB to work with and a weight-based scheme to assist sVLB in intermediate block selection during bursty traffic offloading. Our qualitative assessment and extensive simulation demonstrate that the sVLB-based framework can smooth out the residual traffic fluctuation, thus outperforming existing strategies in normalized FCT.

The emerging high-capacity optical networks make it urgent to design large-scale flexible mesh optical cross-connect (OXC). Though Clos networks are the theory for building scalable and cost-effective switching fabrics, the nonblocking conditions for flex-grid optical Clos networks without wavelength conversion remain unknown. This paper studies the nonblocking conditions for the flex-grid OXC-Clos network, which is constructed from a number of small-size standard OXCs. We first show that a strictly nonblocking (SNB) OXC-Clos network will incur a high cost, as small-granularity lightpaths may abuse central modules (CMs), rendering them unavailable for large-granularity requests due to frequency conflicts. Hence, we propose a granularity differential routing (GDR) strategy, the idea of which is to restrict the set of CMs that can be utilized by the lightpaths of each granularity. Under the GDR strategy, we investigate two system models, called granularity-port binding and unbinding models, and prove the wide-sense nonblocking (WSNB) conditions. We show that the cost of WSNB network is remarkably smaller than that of SNB network, and find that the granularity-port unbinding model can offer more flexible network-bandwidth utilization compared to the binding model, with a slight cost associated with switching fabrics.

The emerging high-capacity optical networks makes it urgent to design large-scale flexible mesh optical cross-connects (OXCs). Though Clos network is the theory for building scalable and cost-effective switching fabrics, the nonblocking conditions of flex-grid optical Clos networks without wavelength conversion remain unknown. This paper studies the nonblocking conditions for the flex-grid OXC-Clos network, which is constructed from a number of small-size standard OXCs. We first show that a strictly nonblocking (SNB) OXC-Clos network will incur a high cost, as small-granularity lightpaths may abuse central modules, rendering them unavailable for large-granularity requests due to frequency conflicts. We thus propose a granularity differential routing (GDR) strategy, the idea of which is to restrict the set of CMs that can be used by the lightpaths of each granularity. Under the GDR strategy, we investigate two system models, granularity-port binding and unbinding models, and prove the wide-sense nonblocking (WSNB) conditions for OXC-Clos network. We show that the cost of WSNB network is remarkably smaller than that of SNB network, and find that the second model can lead to more flexible network-bandwidth utilization than the first model only at a small cost of switching fabrics.

As a key component in dynamic wavelength-routing optical networks (WRONs), the contention performance at add/drop (A/D) ports of ROADMs has attracted a lot of attention in recent years. For the first time, this paper derives the close-form solutions of the blocking probability (BP) of A/D requests to characterize the fundamental tradeoff between A/D flexibility and system complexity in the ROADM. We show that the ROADM with fiber cross-connect (FXC) can decide whether a request can be satisfied based on global transceiver-usage information, and thus an exact expression of BP can be obtained. In comparison, the ROADM without FXC needs detail transceiver-usage information to make decision, and thus is hard to be analyzed. To circumvent the difficulty in analysis, we describe the evolution of the number of busy transceivers using a one-dimensional Markov chain, where the state transition rates are estimated from global transceiver-usage information. Based on this model, we obtain an approximate BP the accuracy of which is high enough for currently commercialized ROADMs and increases with the number of drop ports. Our analytical results provide an interesting insight into the tradeoff between A/D flexibility and system complexity, based on which we give some suggestions for system design.

This article investigates an unmanned aerial vehicle (UAV)-assisted wireless-powered mobile-edge computing (MEC) system, where the UAV powers the mobile terminals by wireless power transfer (WPT) and provides computation service for them. We aim to maximize the computation bits of terminals while ensuring fairness among them. Considering the random trajectories of mobile terminals, we propose a soft actor–critic (SAC)-based UAV trajectory planning and resource allocation (SAC-TR) algorithm, which combines off-policy and maximum entropy reinforcement learning to improve the convergence of the algorithm. We design the reward as a heterogeneous function of computation bits, fairness, and destination. Simulation results show that SAC-TR can quickly adapt to varying network environments and outperform representative benchmarks in various situations.

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.

This paper focuses on dynamic integrated routing in multifiber Internet protocol/wavelength-division multiplexing (IP/WDM) networks, which can be implemented through either one-step routing (OSR) or two-step routing (TSR) approach. Based on an extended layered-graph, two resource assignment strategies, termed channel-level balance (CLB) and link-level balance (LLB), are proposed to balance the traffic in the network at different levels. To further improve the performance, a parameter K is introduced to make a dynamic tradeoff between the logical-layer links and the optical-layer links. Simulation studies are carried out for various topologies. The results show that LLB is better than CLB in most cases, and LLB combined with OSR has the optimal performance. Also, we find that the routing approach and the resource assignment strategy individually play different roles with different values of r/sub l/ that is introduced to indicate the resource richness of the network. As a multifiber network is functionally equivalent to a single-fiber network with limited wavelength conversion, we investigate the effects of wavelength conversion by studying the multifiber IP/WDM networks. The analysis shows that, when the granularity of each connection request is much smaller than the wavelength granularity, wavelength conversion may increase the request blocking probability in the network.