PublicationAbstract:
In recent years, multiple optical fibers are installed on each optical link to deal with the surge of Internet traffic, which calls for large-scale reconfigurable optical add/drop multiplexers (ROADMs). However, the scalability of the standard optical crossconnect (OXC), the key component of ROADM, is limited by the port count of commercial wavelength selective switches (WSSs). The theory of Clos network could be used to design a scalable OXC, but it will lead to a large insertion loss (∼30 dB). To address this issue, we propose a three-phase approach to construct a modular OXC network. Starting from a classical OXC, phase 1 decomposes each WSS in the input and output stages into a two-stage cascaded structure of WSSs, based on which phase 2 factorizes the shuffle network between the inputs and the outputs of the original OXC into the interconnection of small-size shuffle networks. Phase 3 combines the small-size shuffle networks together with the smallsize WSSs to form small-size OXC modules. As a result, we obtain a modular OXC network, which is an interconnection of small-size OXCs. The modular OXC network is a strictly nonblocking and flex-grid optical switching fabric and has ∼20-dB insertion loss. At last, we experimentally evaluate the transmission performance of modular OXC network and discuss the related issues when it is deployed in a ROADM.
Abstract:
This paper 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.
Abstract:
In recent years, hybrid optical/electrical data center network has been considered a promising interconnection technology for 5 large-scale data centers, since it can efficiently provide sufficient bandwidth. A key issue in hybrid optical/electrical data center networks 6 is finding a way to offload burst traffic through optical circuit switches (OCSs), such that the burst traffic can be offloaded timely while the 7 system operation overhead is low. This article extends the idea of Mahout to propose a local-push asynchronous optical traffic offloading 8 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 9 traffic back to electrical packet switches (EPSs) when the backlog is empty. To seek a proper threshold, we develop a fluid-flow model 10 to analyze the performance of the proposed traffic offloading strategy, from which we demonstrate that there is a trade-off between the 11 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 12 to select the buffer threshold. We show via simulation that the proposed optical traffic offloading strategy with the threshold selection rule 13 outperforms C-through.
Abstract:
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.
Abstract:.
In this paper, we analyze the delay performance of queueing systems in which the service rate varies with time and the number of service states may be infinite. Except in some simple special cases, in general, the queueing model with varying service rate is mathematically intractable. Motivated by the P-K formula for M/G/1 queue, we developed a limiting analysis approach based on the connection between the fluctuation of service rate and the mean queue length. Considering the two extreme service rates, we provide a lower bound and upper bound of mean queue length. Furthermore, an approximate mean queue length formula is derived from the convex combination of these two bounds. The accuracy of our approximation has been confirmed by extensive simulation studies with different system parameters. We also verified that all limiting cases of the system behavior are consistent with the predictions made by our formula.
Abstract:
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.
Abstract:
This paper investigates the dual-mode power-saving strategy designed for the 100G Energy Efficient Ethernet. The process of this strategy is a sequence of cycles, where each cycle is an interval elapsed between two consecutive instants when the buffer of the Ethernet interface becomes empty. In each cycle, the interface first enters the fast-wake mode to perform the conditional sleep-mode selection of the strategy. If the number of arrivals during the fast-wake mode reaches a threshold, the interface directly wakes up; otherwise, it proceeds to the deep-sleep mode. The sequence of cycles switches between two types: deep-sleep cycles with deep-sleep mode and light-sleep cycles without deep-sleep mode. We analyze the dual-mode strategy based on the condition of the number of arrivals during the fast-wake mode. We first derive the weights of conditions according to the feature of the conditional sleep-mode operation, and then calculate the unconditioned performance measure of the dual-mode strategy based on the weighted average of that of these two kinds of cycles. Finally, we obtain the close-form expressions of the power efficiency and the mean delay, based on which we provide a set of parameter selection rules. We show that the dual-mode strategy with these rules can select suitable sleep modes according to the instantaneous traffic rate, and thus perform well under bursty input traffic.
Abstract:
This paper studies the Ethernet Passive Optical Network (EPON) with limited service. The transmission window (TW) is limited in this system to guarantee a bounded delay experienced by disciplined users and to constrain malicious users from monopolizing the transmission channel. Thus, selecting an appropriate TW size is critical to the performance of EPON with limited service discipline. In this paper, we develop an M/G/1 queueing model with vacation times and limited-service discipline to investigate the impact of TW size on packet delay. A distinguishing feature of this model is that there are two queues in the buffer of each optical network unit (ONU): one queue is inside the gate and the other one is outside the gate, from which we derive the generalized formula of mean waiting time. Furthermore, based on the service level agreements of users and the Chernoff bound of queue length, we provide a simple rule to determine an optimum TW size for limited-service EPONs. Analytic results reported in this paper are all verified by simulations.
9. Kui Chen, Tong Ye, Hao He, and Zidong Guo, "Modular Optical Cross-Connects (OXCs) for Large-Scale Optical Networks," IEEE Photonics Technology Letters, vol. 31, no. 10, pp. 763-766, 15 May. 2019.
Abstract:
Due to the explosive growth of traffic demands, large-scale optical cross-connects (OXCs) are highly desired in next-generation optical networks. However, the scalability of classical OXCs is not good in terms of the size of optical switching modules and cabling complexity to meet application requirement. To address this issue, this letter proposes a two-phase approach to construct modular large-scale OXCs, using a set of small-size OXC modules. We first decompose each optical space switch (OS) in a classical OXC to a Clos network and then merge the corresponding links and decomposed optical switching modules of different Clos networks to form small-size OXC modules, which finally yields a modular OXC. We show that the proposed modular OXC has good scalability and acceptable physical-layer performance.
10. Lingkang Wang, Tong Ye, and Tony T. Lee, "A Parallel Route Assignment Algorithm for Fault-tolerant Clos Networks in OTN switches," IEEE Trans. on Parallel and Distributed Systems, vol. 30, no. 5, pp. 977-989, 1 May. 2019. (slides)
Abstract:
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 optical 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 low complexity for Clos networks, 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.
11. Tong Ye, Tony T. Lee, M. Ge, and Weisheng Hu, "Modular AWG-based Interconnection for Large-Scale Data Center Networks," IEEE Trans. on Cloud Computing, vol. 6, no. 3, pp. 785-799, 1 Jul.-Sep. 2018. (slides)
Abstract:
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.
12. Lingkang Wang, Tong Ye, Tony T. Lee, and Weisheng Hu, "A Parallel Complex Coloring Algorithm for Scheduling of Input-Queued Switches," IEEE Trans. on Parallel and Distributed Systems, vol.29, no.7, pp.1456-1468, 1 Jul. 2018. (slides)
Abstract:
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 on the order of O(logN), 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% 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.
13. Xiaodan Pan, Tong Ye, Tony T. Lee, and Weisheng Hu, "Power Efficiency and Delay Tradeoff of 10GBase-T Energy Efficient Ethernet Protocol," IEEE/ACM Trans. on Networking, vol. 25, no. 5, pp. 2773-2787, Oct. 2017. (slides)
Abstract:
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 τ 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 τ 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 τ policy and N policy of the BTR strategy are compensating each other. The τ 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 τ and N. Our analytical results are confirmed by simulations.
Abstract:
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.
Abstract:
Predictable network performance is critical for cloud applications and can be achieved by providing tenants a dedicated virtual data center (VDC) with bandwidth guarantee. Recently, the extended Hose model was applied to the VDC abstraction to characterize the tradeoff between cost and network performance. The acceptability determination problem of a VDC with heterogeneous bandwidth demand was proved to be NP-complete, even in the simple tree topology. In this paper, we investigate the embedding problem for heterogeneous bandwidth VDC in substrate networks of general topology. The embedding problem involves two coupled sub-problems: virtual machine (VM) placement and multipath route assignment. First, we formulate the route assignment problem with linear programming to minimize the maximum link utilization, and provide K-widest path load-balanced routing with controllable splitting paths. Next, we propose a polynomial-time heuristic algorithm, referred to as the perturbation algorithm, for the VM placement. The perturbation algorithm is congestion-aware as it detects the bandwidth bottlenecks in the placement process and then selectively relocates some assigned VMs to eliminate congestion. Simulation results show that our algorithm performs better in comparison with the existing well-known algorithms: first-fit, next-fit, and greedy, and very close to the exponential-time complexity backtracking algorithm in typical data center network architectures. For the tree substrate network, the perturbation algorithm performs better than the allocation-range algorithm. For the homogeneous bandwidth VDC requests, the perturbation algorithm produces a higher success rate than the recently proposed HVC-ACE algorithm. Therefore, it provides a compromised solution between time complexity and network performance.
Abstract:
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.
Abstract:
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.
Abstract:
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.
Abstract:
In this paper, we study the performances of the registration protocol in Ethernet passive optical networks (EPONs). In each registration process, the newly-connected optical network units (ONUs) send their requests to the optical line terminal (OLT) without any scheduling, which may cause collisions and lower the registration success probability. Thus, a random-delay based registration protocol has been defined in the IEEE 802.3av standard to prevent collisions. Intuitively, the registration protocol of EPON possesses similar characteristics as medium access control (MAC) protocols. Based on this principle, we derive the closed-form expression of the registration throughput to evaluate the random-delay based protocol. We show that an optimal discovery-window size can be determined by maximizing the registration efficiency. Our analytical results indicate that the random delay introduced in the protocol is helpful to enhance the registration efficiency when the number of ONUs is large, or if all ONUs are clustered. However, the throughput improvement by random delay is marginal if there is only a small number of evenly distributed ONUs in the vicinity of EPON.
Abstract:
Array-waveguide grating (AWG) is a kind of passive wavelength router. It can perform nonblocking switching functions in conjunction with tunable wavelength converters (TWCs). For optical switching systems with large number of ports, however, the scalability of the AWG is restricted by coherent crosstalk. In this paper, we propose a modular method of designing arrays of AWGs for large-scale switching systems, in which a contention-free connection from an idle input to an idle output can always be established regardless of the number of existing connections in progress. The construction process of AWG networks is sometimes called AWG function decomposition. For the decomposition of an N × N AWG, we describe the modular architecture of a functionally equivalent three-stage network of smaller AWGs, and derive the necessary and sufficient conditions on the number of smaller AWG modules needed for nonblocking switching. Our results can be applied to the decomposition of any AWG components employed in an AWG-based switching network to suppress the coherent crosstalk.
