We study a robust variant of the online bin packing problem that models reliable cloud resource allocation. In this problem, bins represent servers and items represent jobs of various workloads. Furthermore, to guarantee that the service of each item is available regardless of any η bins turn to be faulty, each item is replicated into η + 1 bins. In the case of bin failures, the faulty replica’s workload is distributed to other bins associated with the same item with ensuring the extra workloads do not cause an overflow in any bins. The key issue is to minimize the total number of activated bins under the demands and robustness constraints. OrthogonFit algorithm, which is proposed, solves this key issue by categorizing replicas into distinct classes based on workloads and packing identical replicas onto the same type of bins. It efficiently reuses those already-activated bins without the need of new ones. Theoretical analysis and simulation results demonstrate its superior performance over existing works.

As important network infrastructures to support data storage and service delivery for worldwide users, cloud data centers are facing great threaten by frequent disasters around the world and thus the survivability of cloud data centers becomes a critical issue. Since both data and service evacuations are desired at the same time under a real disaster scenario, this paper studies a joint design of them to fight against disasters. We consider a disaster that can present an early warning time before it really affects cloud data centers, and by exploiting the intrinsic interplay between data and service evacuations and efficiently utilizing the early warning time we propose a joint data and service evacuation scheme for emergency protection. We first formulate the joint design as two optimal Integer Linear Program (ILP) models. Notice that the protection process is highly time-sensitive due to the early warning time constraint, two time-efficient heuristics are then designed by carefully selecting evacuated services and candidate evacuation nodes to achieve a better sharing of network resources between data backup and service migration. Extensive numerical results demonstrate the efficiency of the proposed scheme on improving survivability of data and services in cloud data centers. With a set of given resource and early warning time constraints, this work can guide data center operators to achieve a tradeoff between data backup and service migration.

In support of effectively discovering the market value of resources and dynamic resource provisioning, auction design has recently been studied in the cloud. However, there are limitations due to the inability to accept time-varying user demands or offline settings. These limitations create a large gap between the real needs of users and the services available from cloud providers. In addition, existing auction mechanisms do not consider service interruption due to server failures caused by software or hardware problems. To address the limitations of existing auction mechanisms and to avoid service interruption, this paper targets a more general scenario of online cloud resource auction design where: 1) users can request multiple types of time-varying resources; and 2) at least one server is available for each accepted bid even when one or more servers fail; and 3) profit is maximized over the system execution span. Specifically, we model the profit maximization problem using an Integral Linear Programming (ILP) optimization framework, which offers an elastic model for time-varying user demands. In addition, we design an online, truthful, and time efficient auction mechanism consisting of a price-based allocation strategy and a pricing function. The online allocation strategy allocates multiple types of resource to each user while satisfying the time-varying demands and ensuring at least one server is available for each user in each allocated time slot. Lastly, the efficacy of online auctions is validated through careful theoretical analysis and trace-driven simulation studies.

We study server consolidation problem in clouds under simultaneous failures of multiple servers, where consolidation means that cloud providers put tenants on shared servers to improve resource utilization and thus reduce operation and maintenance costs. With replicas of each tenant put on multiple servers, our objective is to minimize the total number of opened servers and ensure that a particular failure will not result in overload on any remaining server. In this paper, we propose Rotation algorithm. It packs comparable sizes replicas into the same type of servers and adopts a cyclic shift method to quickly reuse those already-opened servers without the need of new ones for new tenants. Through experimental evaluations, we show that the proposed algorithms can achieve a better performance than existing works and produce near-optimal replications allocation.

Distributed multi-controller deployment is a key issue in the innovative Software Defined Network (SDN) to scale network while improving performance and reliability. It is interesting to know how many controllers should be deployed and where to locate under a wide range of performance sensitive and completive constraints, including latency, fair load distribution as well as cost. We solve this problem by minimizing propagation latency and controller cost. The required number of controllers is determined based on requests and controller capacity. Due to the uneven distribution of network load, it is more likely to deploy controllers on nodes with high request density. A clustering algorithm NWDP (Node Weight Deployment Policy) is thus proposed based on node weight to choose location of multi-controller. To achieve effectively, autonomous and dynamic deployment in large-scale networks, we further propose a supervised graph convolution network model with fusion features(FF-GCN). The open network database Internet Topology Zoo is adopted to evaluate the effectiveness of our algorithms. Simulation results show that NWDP efficiently outperforms traditional algorithms in medium-sized topology, and the trained FF-GCN can figure out the deployment in a 702 nodes large-scale topology with an average prediction accuracy of 90%.

Array, as a fundamental data structure, is widely used in programs. Automated reasoning about arrays needs to discover properties about ranges of elements at certain program points. Such properties are formally specified by universally quantified formulas. A universally quantified formula usually includes two parts: the index range and the properties of the corresponding array elements. In this paper, we first propose a classification of array-handling loops to understand the complexity of discovering two parts of properties about arrays, which is based on whether array variables appear in judgment statements (loop conditions and loop branch conditions). Secondly, for each type, we extend the path dependency automaton (PDA) to capture the dependencies between paths for an array-handling loop and discover useful facts about individual elements for each state of the PDA. Finally, an algorithm is proposed to identify the index range and generalize useful facts about individual elements to entire ranges for each state of the PDA. These properties are enough to verify the assertion of the end of the program. We show this method can be extended to programs with complex loops and nested loops as well. The result of experiments shows that this method outperforms several state-of-the-art tools on a suite of benchmarks from SV-COMP.

In this paper, we propose a physical layer authentication scheme in heterogeneous coexist multiple-input-multiple-output (MIMO) systems. This scheme utilizes two physical layer features in terms of location-specific channel gains and transmitter-specific phase noise caused by imperfect oscillators to identify transmitters. Three properties of the proposed scheme: covertness, robustness, and security, are analyzed in detail. By using a maximum-likelihood estimator (MLE) and extended Kalman filter (EKF), we estimate channel gains and phase noise, and formulate variances of estimation errors. We also quantize the temporal variations of channel gains and phase noise through the developed quantizers. Based on quantization results and theories of hypothesis testing and stochastic process, we then derive the closed-form expressions for false alarm and detection probabilities with the consideration of quantization errors. Simulations are carried out to validate the theoretical results of the two probabilities. Based on theoretical models, we further demonstrate that the proposed scheme makes it possible for us to flexibly control authentication performance by adjusting thresholds (for channel gain, phase noise, and decision, respectively) to achieve a required authentication performance in specific MIMO applications.

We study transmitter authentication in massive multiple-input multiple-output (MIMO) systems with non-ideal hardware for the fifth generation (5G) and beyond networks. A new channel-based authentication scheme is proposed by taking hardware impairments into account. Based on signal processing theory, we first formulate channel estimation under hardware impairments and determine error covariance matrix to assess the quantity caused by hardware impairments on authentication performance. With the help of hypothesis testing and matrix transformation theories, we are then able to derive exact expressions for the probabilities of false alarm and detection under different channel covariance matrix models. Extensive simulations are carried out to validate theoretical results and illustrate the efficiency of the proposed scheme. Impacts of system parameters on performance are revealed as well.

Task scheduling in cloud computing is an NP-complete problem. It concerns how to properly arrange task execution process using a set of necessary cloud resources. Existing works assume that tasks can be interrupted without any overhead, based on which task schedules can be optimized to achieve some objectives (e.g., maximize resource utilization). We observe that interrupting tasks, as well as subsequent task recovery process, will inevitably impose overheads in terms of consuming additional CPU time on corresponding physical machines. In addition, not all tasks can be interrupted. Those observations motivate us to consider a more general scenario where a job consists of both interruptible and non-interruptible tasks with specific deadline and resource requirements. Accordingly, we design algorithms to minimize task interruption overhead while ensuring task completion deadline. Specifically, we first formulate an Integer Linear Program (ILP) for offline optimization. A heuristic algorithm is then proposed for online task scheduling, and is compared with the optimal ILP solution. Numerical results confirm the correctness of our ILP and show the efficiency of the proposed heuristic.

Resource scheduling is one of the main problems for multi-satellite Tracking, Telemetry and Command (TT&C) networks. Traditional multi-resource joint scheduling algorithms are with long solution time, low efficiency, high computational cost, and simple description on the system. Deep Neural Network (DNN) provides a possible new way to solve those problems, but it is difficult to handle correlations among the input data. This motivates our work to solve the strong correlation problem based on the accumulated historical data, and thus enables DNN for TT&C resource scheduling. By discretizing the data, multiple constraints and related attributes are transformed into different flags, and some binary bits of the data are used to reflect the constraint relationship. Then, we can use DNN model and construct an intelligent TT&C resource scheduling system to handle multiple constraints and data attributes (such as priorities among tasks and others). This improves the efficiency of TT&C resources utilization and automation. Effectiveness of the proposed model is verified by simulations.

Nash noncooperative power game is an effective method to implement interference cooperation in downlink multiuser multiple-input multiple-output (MU-MIMO). Power equilibrium point of Nash noncooperative power game can achieve a satisfactory tradeoff between self-benefits of Internet of Things (IoT) users and interference between IoT users which largely enhance the edge IoT user throughput. However, either power strategy space, i.e., the enabled range of power allocation for IoT users, or overall BS transmit power in the existing Nash noncooperative power games is generally static. This limits the performance of systems, especially in IoT systems, etc., in 5G. As an effort to address these problems, we design a novel framework of Nash noncooperative game with iterative convergence for downlink MU-MIMO. We first decompose the MU-MIMO into multiple virtual single-antenna transmit-receive pairs with a stream analytical model. Afterwards, based on streams, we propose a noncooperative water-filling power game with pricing (WFPGP) where the power strategy space of each stream can be dynamically determined byiterative water-filling. We derive the sufficient condition for the existence and uniqueness of WFPGP game, in which the verification of the sufficient condition can be executed in a distributed manner. By simulations, we verify the performance of WFPGP compared to other Nash noncooperative games.

Cloud computing is an Internet-based computing pattern through which shared resources are provided to devices on-demand. It is an emerging but promising paradigm to integrating mobile devices into cloud computing, and the integration performs in the cloud based hierarchical multi-user data-shared environment. With integrating into cloud computing, security issues such as data confidentiality and user authority may arise in the mobile cloud computing system, and it is concerned as the main constraints to the developments of mobile cloud computing. In order to provide safe and secure operation, a hierarchical access control method using modified hierarchical attribute-based encryption (M-HABE) and a modified three-layer structure is proposed in this paper. In a specific mobile cloud computing model, enormous data which may be from all kinds of mobile devices, such as smart phones, functioned phones and PDAs and so on can be controlled and monitored by the system, and the data can be sensitive to unauthorized third party and constraint to legal users as well. The novel scheme mainly focuses on the data processing, storing and accessing, which is designed to ensure the users with legal authorities to get corresponding classified data and to restrict illegal users and unauthorized legal users get access to the data, which makes it extremely suitable for the mobile cloud computing paradigms.

Many real-world wireless networks for industrial internet of things applications have diverse connectivity characteristics, which makes routing protocol design challenging. Although adaptive routing protocols have been emerging to deal with connectivity diversity, there is still lack of a unified routing framework in well-connected and intermittently connected networks. In this paper, we present a unified routing metric for wireless networks with diverse connectivity, and formulate the adaptive routing problem as an integer linear programming optimization one. We then propose a heuristic routing protocol, caching-optimized adaptive routing protocol (COARP). Extensive simulation results show that COARP is near optimal in simple static network scenarios, and performs well across all the range of connectivity spectrum in dynamic network scenarios.

When people purchase products on the Internet, the overwhelming information makes it difficult to choose a satisfactory merchandise. Hence, an effective recommendation system seems to be very necessary. The user-based collaborative filtering recommendation is the earliest and most popular recommendation system. The most significant step of user-based collaborative filtering recommendation is comprehensive user similarity calculation. However, most recommendation systems ignore the indispensability of user evaluation normalization and the weighted user attributes in comprehensive user similarity calculation, which leads to the inaccurate recommendation. Based on these issues, this paper proposes an optimized user-based collaborative filtering recommendation system, called O-Recommend. O-Recommend not only validates the necessity of the user evaluation normalization and the weighted user attributes in the comprehensive user similarity calculation, but also improves the recommendation accuracy.

Due to the reconfiguration overhead of optical fabrics, batch scheduling method is generally used to schedule an optical packet switch, with a necessary speedup inside the switch to ensure 100% throughput with a bounded packet delay. Existing algorithms take each traffic matrix as a batch, and adopt traffic matrix decomposition techniques to decompose it into the sum of a set of weighted permutation matrices (which are then used as switch configurations). Nevertheless, existing algorithms adopt an equal weight for all switch configurations, meaning that each configuration should be held for the same time duration to transmit packets. We observe that this rigid strategy may limit the flexibility of the scheduling and result in a large speedup requirement due to inefficient time slot utilization. Motivated by this observation, we propose a UWS (Unequal Weight Sequence) algorithm to decompose the traffic matrix. UWS uses a different weight for each switch configuration. It first takes an arithmetic progression as the starting weight sequence, and then adjusts the weights for configurations to ensure 100% throughput with a bounded packet delay (such that QoS can be guaranteed). We theoretically prove that the worst case speedup of UWS will never be larger than that of the best existing ADAPT algorithm. Simulation results indeed demonstrate a speedup improvement of around 15%.

Internet of Things (IoT) is becoming an emerging paradigm to achieve ubiquitous connectivity, via massive deployment of physical objects, such as sensors, controllers, and actuators. However, concerns on the IoT security are raised due to the wireless broadcasting nature and the energy constraint of the physical objects. In this paper, we study secure downlink transmission from a controller to an actuator, with the help of a cooperative jammer to fight against multiple passive and noncolluding eavesdroppers. In addition to artificial noise aided secrecy beamforming for secure transmission, cooperative jamming (CJ) is explored to further enhance physical layer security. In particular, we provide a secrecy enhancing transmit design to minimize the secrecy outage probability (SOP), subject to a minimum requirement on the secrecy rate. Based on a strict mathematical analysis, we further characterize the impacts of the main channel quality and the minimum secrecy rate on transmit designs. Numerical results confirm that our design can enhance both security (in terms of SOP) and power efficiency as compared with the approach without CJ.

In this paper, we investigate cooperative security in wireless networks, where a source (Alice) intends to transmit a confidential message to a legitimate destination (Bob), with the help of a cooperative node (Charlie), in the presence of multiple independent eavesdroppers (Eves). In particular, cooperative jamming (CJ) is explored to enhance secure communication between Alice and Bob. We provide a transmit design to maximize the secrecy rate, subject to a secrecy outage probability (SOP) constraint. Specifically, we establish a condition under which positive secrecy rate can be guaranteed. In addition to secrecy rate performance, we also pay attention to the secure energy efficiency, defined as the ratio of secrecy rate to total power consumption. Numerical results validate the effectiveness and energy efficiency of our proposed CJ scheme.

Summary By separating control plane from data plane, software‐defined network (SDN) adopts centralized controllers to manage data flows in the network. Nevertheless, the rapid growth of network service traffic requires a large number of controllers, reducing network performance due to the scalability constraint. Therefore, we consider distributed placement of controllers in wide‐area network to construct a scalable SDN architecture, by taking service traffics, traffic propagation delay, and load balancing into account. Specifically, we first partition the network into several small sections (named SDN domains) and then place the least amount of controllers to a proper node in each domain. The architecture provides a control channel to deliver requested messages for each SDN domain, so it reduces the link delay (which is assumed to be proportional to the physical length of the link) between switches and SDN controllers. Unfortunately, it also introduces extra latency among controller sets at different SDN domain. Accordingly, we formulate an integer linear program to optimize network cost and performance by considering all those conflicting factors and propose an efficient heuristic algorithm called distributed SDN placement to solve the problem. Simulation results confirm that our proposed heuristic distributed SDN placement can achieve suboptimal solutions as compared with the integer linear program results.

Banyan networks serve as a class of important switching network architecture, whose multicast capability is critical for future high-performance switches to support multicast-intensive applications. The available literature indicates that, in order to construct optical multicast banyan networks based on the directional coupler (DC) technology, a high-hardware cost is usually involved to ensure the nonblocking property. In this paper, we conduct blocking probability analysis for such networks to explore the inherent tradeoff between blocking probability and hardware cost. In particular, we focus on a class of DC-based optical networks built on the replicated banyan network (RBN) architecture, and develop a theoretical upper bound on blocking probability for such networks under the general f-cast traffic, which covers the unicast and multicast as special cases. This bound captures the overall blocking behavior of f-cast optical RBN networks and agrees with the conditions of strictly nonblocking f-cast optical RBN networks. The proposed bound is significant because it provides a fundamental guideline to achieve the desirable tradeoff between blocking probability and hardware cost. This paper shows that the hardware cost of an f-cast optical RBN network can be dramatically reduced if a small blocking probability is allowed.

Data backup in data center networks (DCNs) is critical to minimize the data loss under disaster. This paper considers the cost-efficient data backup for DCNs against a disaster with ε early warning time. Given geo-distributed DCNs and such a ε-time early warning disaster, we investigate the issue of how to back up the data in DCN nodes under risk to other safe DCN nodes within the ε early warning time constraint, which is significant because it is an emergency scheme for data protection against a predictable disaster and also help DCN operators to build a complete backup scheme, i.e., regular backup and emergency backup. Specifically, an Integer Linear Program (ILP)-based theoretical framework is proposed to identify the optimal selections of backup DCN nodes and data transmission paths, such that the overall data backup cost is minimized. Extensive numerical results are also provided to illustrate the proposed framework for DCN data backup.

In this paper, we consider physical layer security in wireless communication networks in which a source (Alice) intends to send a confidential message to a legitimate destination (Bob) with the help of a cooperative jammer (CJ), in the presence of a passive eavesdropper (Eve). Assuming that only statistical channel state information (CSI) of Eve is available, artificial-noise (AN) assisted beamforming and cooperative jamming are designed. The goal is to maximize the secrecy rate, subject to a constraint on secrecy outage probability. Numerical results validate the effectiveness of our scheme. Moreover, a higher secure energy efficiency (EE) can be achieved as compared with other schemes without a cooperative jammer.

In current data centers, an application (e.g. MapReduce) usually generates a collection of parallel flows sharing a common goal. These flows compose a coflow and only completing them all is meaningful. Accordingly, minimizing the average coflow completion time (CCT) becomes a critical objective for flow scheduling. In this topic, the state-of-the-art centralized method, Varys, achieves a good average CCT; but it has the scalability problem. Alternatively, the only existing decentralized method, Baraat, suffers from the head-of-line blocking problem. To solve these problems, we propose D-CAS, a preemptive, decentralized, coflow-aware scheduling system in this paper. D-CAS pursues coflow-level remaining-time-first (MRTF) principle by leveraging a simple negotiation mechanism between each coflow's data senders and receivers. As the MRTF principle is inherently preemptive and proven to be a near-optimal guideline to minimize average CCT, D-CAS avoids the head-of-line blocking problem and gets good performances. Through extensive simulations, we find that D-CAS achieves a performance close to Varys (gap <; 15%) and outperforms Baraat significantly (about 1.4-4×).

Vertical stacking of banyan networks has been an attractive architecture to construct optical switching networks due to its small depth, absolute signal loss uniformity and good fault tolerance property. Recently, F.K. Hwang extended the study of banyan-based networks to the general f-cast case, which covers the unicast (f = 1) and multicast (f = N) as special cases. In this paper, we study the blocking probability of f-cast optical banyan networks under crosstalk-free constraint. It is expected that the proposed probability model can be used to dimension such an f-cast network and achieve a graceful tradeoff between hardware cost and blocking probability.

This study proposes an approach for achieving strong communication security based on explosive fountain code with coset pre‐coding, where both main and wire‐tap channels are memoryless binary erasure channels. Coset pre‐coding is used to prevent the eavesdroppers from intercepting the confidential information from the leaked bits. Further, an explosive fountain code is designed to ensure the reliability and low information leakage. By this way, the proposed approach can keep strong security and reliability when the erasure probability of the main channel is slightly lower than that of the wire‐tap channel. Extensive simulations are conducted to verify the correctness and effectiveness of the approach.

The explosion of Internet traffic calls for quality of service (QoS)-guaranteed packet transmission in wavelength division multiplexing (WDM) networks with high energy and bandwidth efficiency. Conventional routing and wavelength assignment (RWA) algorithms focus on circuit switching, which does not well meet this requirement due to the bursty nature of IP traffic. Based on a novel traffic matrix decomposition technique, we study the joint design of traffic scheduling and routing in a reconfigurable WDM optical network to improve energy and bandwidth efficiency. Specifically, every node in the network is equipped with a set of parallel tunable lasers, each with a reconfiguration overhead. A dynamic matrix is adopted to model the traffic among the nodes and is decomposed into a set of transmission configurations (i.e., traffic scheduling). The configurations are then fulfilled by tuning the parallel lasers and routing the scheduled traffic under the topology constraint, to achieve loss-free packet transmissions with bounded delay (i.e., QoS guarantee). We reveal that a tradeoff exists between the packet delay and the required number of tunable lasers. The latter is then minimized under a given packet delay to save energy. As far as we know, this is the first work to adopt traffic matrix decomposition in WDM networks to save energy. The proposed framework is validated by extensive simulation studies.

Cloud services based on data center networks (DCNs) require a transmission infrastructure with high-capacity, low-latency, low-cost and high-availability, which can be offered by survivable optical networks. DCN placement is a fundamental issue in supporting cloud services in optical networks. It concerns not only the cost of providing cloud services, but also the service availability against failures via proper service replicas. In this paper, we jointly optimize DCN placement with service routing and protection to minimize the network cost, while ensuring fast protection of all services against any single link failure or service failure at a particular DCN. An ILP (Integer Linear Program) is first formulated to achieve optimal joint design. It integrates p-cycle (preconfigured protection cycle) for fast protection against a single link failure, and DCN replicas and fast service rerouting against a service failure. To make the design more scalable, a two-step heuristic is then proposed for large-size network scenarios. The first step separately solves the DCN placement and service routing problem in the failure-free scenario, and the second step takes fast service protection into account. The proposed design is validated by extensive numerical experiments.

Network virtualization facilitates sharing and efficient utilization of computing and bandwidth resources of an underlying substrate network. As network virtualization becomes popular, it is important to efficiently map a virtual infrastructure (VI) onto a substrate network, such that the survivability of the former can be guaranteed against failures in the latter. In this paper, we study a virtualization layer approach to survivability, whereby the virtualization layer customizes a VI request with redundant nodes and links according to its reliability requirements and then passes limited information about the augmented VI to the physical layer, where the mapping of the augmented VI takes place. More specifically, we develop a flexible scheme to enhance the original VI graph with K redundant nodes, in order to fight against an arbitrary substrate node failure. In addition, a scenario-based component group (SBCG) concept is proposed to describe resource sharing of enhanced VI requests at the physical layer. We also develop an efficient heuristic that takes advantage of the limited information on SBCG to reduce costs when mapping the enhanced VI to the substrate network. The efficiency of the proposed solution is compared using extensive simulation under various performance metrics. It is shown that the K-redundant-node scheme with SBCG information is more cost efficient than the existing 1-redundant-node solution.

In 3GPP LTE-A, Coordinated Multi-Point (CoMP) is adopted to enhance the transmission rates of edge users. To maximize the total downlink throughput of all edge users, it is crucial to properly determine the set of simultaneously served users in each physical resource block (PRB) and the cooperative base stations (BSs) for each scheduled user, as well as the transmit power of the BSs. Based on the reference signal receiving power (RSRP) of each edge user, we first propose two simple and integrated transmission scheduling algorithms, one distributed and the other centralized, to choose cell-edge users and cooperative BSs in each PRB. With the scheduling results, the classic Water-Filling (WF) algorithm is carried out over all PRBs at each BS to get an initial single cell power allocation. To take the interference among different cooperative BS sets into account, we further formulate a non-cooperative power allocation game to adjust the initial power allocation for interference coordination, where the initial power allocation provides the strategy space of the game for each BS. This increases the total downlink throughput of edge users over all BSs. We prove that the game has a unique Nash Equilibrium (NE), and design an algorithm to find the NE. Performance gain is then demonstrated through extensive simulation studies.

Data center networks (DCNs) generally adopt Clos network with crossbar middle switches to achieve non-blocking data switching among the servers, and the number of middle switches is proportional to the number of ports of the aggregation switches in a fixed manner. Besides, reconfiguration overhead of the switches is generally ignored, which may contradict the engineering practice. In this paper, we consider batch scheduling based packet switching in DCNs with reconfiguration overhead at each middle switch, which inevitably leads to packet delay. With existing state-of-the-art traffic matrix decomposition algorithms, we can generate a set of permutations, each of which stands for the configuration of a middle switch. By reconfiguring each middle switch to fulfill multiple configurations in parallel with others, we reveal that a tradeoff exists between packet delay and switch cost (denoted by the number of middle switches), while performance guaranteed switching with bounded packet delay can be achieved without any packet loss. Based on the tradeoff, we can minimize the number of middle switches (under a given packet delay bound) and an overall cost metric (by translating delay into a comparable cost factor), as well as formulating criterions for choosing a matrix decomposition algorithm. This provides a flexible way to reduce the number of middle switches by slightly enlarging the packet delay bound.

Conventional all-optical restoration strategies like p-cycle achieve very fast restoration with high spare capacity consumption. In contrast, failure dependent protection (FDP) can achieve near-optimal capacity efficiency at the cost of high signaling/control complexity (so as for long restoration time). In this paper, we investigate a previously reported all-optical restoration framework that aims to yield a restoration speed similar to p-cycle while achieving near optimal resource consumption as FDP. In particular, we propose a simple yet efficient heuristic for joint allocation of monitoring trails and protection lightpaths, which serves as the key to enable the all-optical restoration. The resultant all-optical restoration framework is further examined by extensive simulations regarding the network resource consumption, number of transmitters, monitoring requirement, and running time.

Water‐Filling (WF) is widely applied in power allocation in multichannel wireless communications. By mathematically linearising the optimal WF expression, the authors observe an intrinsic parallel‐shift property of WF, based on which a fast and efficient WF algorithm is proposed. Compared with the conventional WF algorithms, it greatly simplifies WF execution by removing the Lagrange multiplier (or water‐level) searching process. The authors further apply the proposed parallel‐shift WF to solve the power allocation problem in orthogonal frequency division multiplexing (OFDM)‐based underlay cognitive radios (CRs), with the objective of maximising the secondary user's throughput over all OFDM sub‐channels under the transmit power and the interference constraints. To this end, the existing algorithm adopts an iterative binary searching process to find the solution, where the conventional WF algorithm with Lagrange multiplier searching is invoked in each iteration. In contrast, the authors propose a new power allocation algorithm to remove the iterative binary searching process. It runs the simplified parallel‐shift WF only once, and then directly calculates the final solution using a power adjustment process (with the parallel‐shift property as the underlying enabling mechanism). Numerical results show that both the proposed parallel‐shift WF and the OFDM‐based CR power allocation algorithms can run multiple times faster than the existing counterparts, and the gap on the running time increases with the total number of OFDM sub‐channels in the system.

In this paper, we look at the simplest instance of heterogeneous broadcast channel (BC) where a multi-antenna transmitter base station (BS) is trying to communicate data to two user equipments (UEs), having the perfect CSIT about UE-1 and no CSIT about UE-2. We focus on UE-2 which is severely limited by the interference of UE-1. We consider the question whether additional spatial diversity or advanced receiver design at UE-2 is feasible for mitigating this interference. We investigate both the options and show that the rate of UE-2 gets significantly improved in both cases however hardware and RF design constraints may make the advanced receiver design solution preferable over spatial diversity solution.

We consider power allocation in energy efficient OFDM (Orthogonal Frequency Division Multiplexing) or MIMO (Multiple-Input Multiple-Output) transmissions. An energy-per-goodbit (EPG) metric is used to gauge the average energy consumed for transmitting each bit. Existing works minimize EPG by searching for a set of dual variables which are used to compute the optimal power allocation in a Water-Filling (WF) expression. The searching process is complex and requires a long running time. In this paper, we propose a new algorithm to compute the optimal power allocation without searching any dual variables. Our algorithm is based on an iterative calculation of the total transmission power and it converges when the minimum EPG is reached. It takes WF as the basic building block. Unlike the conventional WF approach which needs to search for a Lagrange multiplier (i.e., the water level), we additionally propose a novel WF algorithm without searching the Lagarange multiplier. Numerical results show that our power allocation algorithm for EPG minimization, together with the embedded fast WF algorithm, can run multiple times faster than the existing ones.

The concept of monitoring trail (m-trail) provides a striking mechanism for fast and unambiguous link failure localization in all-optical networks. To achieve fast m-trail design in large-size networks, two efficient heuristics RCA+RCS and MTA are proposed against the optimal ILP (Integer Linear Program) model. However, RCA+RCS suffers from the disjoint trail problem which increases the required number of m-trails, and MTA always finds a deterministic solution which may not be good enough due to the limited solution space. In this paper, we propose a new heuristic RNH-MTA (Monitoring Trail Allocation with the Random Next Hop policy) to solve those issues. Similar to MTA, RNH-MTA ensures a valid optical structure of each m-trail and sequentially adds necessary m-trails to the solution, and thus is free of the disjoint trail problem. By replacing the deterministic searching in MTA using the Random Next Hop policy, RNH-MTA sets up a probabilistic model in extending each m-trail. This not only enlarges the solution space and increases the solution diversity, but also enables a controllable tradeoff between the solution quality and the running time of the algorithm. Our numerical results show the advantages of RNH-MTA over both RCA+RCS and MTA.

In LTE-A (3GPP LTE-Advance) systems, CoMP (Cooperative Multi-Point) is adopted to enhance the performance of edge users. To maximize the edge user throughput, it is very crucial to properly determine the set of simultaneously served users in the same PRB (physical resource block) and cooperating BSs (base stations) for each selected user, as well as the transmit power of the BSs. In this paper, we first propose a simple scheduling algorithm to choose cell-edge mobile stations (MSs) and cooperating BSs for each PRB according to the RSRP (reference signal receiving power) of each MS, based on which the classic Water-Filling (WF) is applied at each BS to allocate transmit power over all PRBs. However, the objective of single cell power allocation is to maximize the throughput of each individual cell without considering interference among different cooperating BS sets. Therefore, we further formulate a power reallocation mechanism using non-cooperative game theory to refine the single cell WF result for interference coordination, which maximizes the total edge user throughput over all BSs and PRBs by properly taking CCI (co-channel interference) into account. Based on proving the existence of a unique Nash Equilibrium for the formulated game, we design an algorithm to find the Nash Equilibrium and demonstrate the performance gain through extensive simulation studies.

Under a given modulation scheme and a target BER (bit error rate) requirement, it is difficult to increase the number of bits transmitted in each symbol (i.e., the rate), since this generally requires a significant increase of transmit power. In this paper, we study how to increase the rate in multiuser multiple-input multiple-output (MU-MIMO) broadcast channels using only bit and power loading, without requiring additional transmit power. To solve this challenging problem, our approach is to carry out a joint design of bit loading and power allocation over all streams, and meanwhile take user and stream selection into account. Specifically, we maximize the total number of bits per symbol (rather than the Shannon capacity) over all selected streams, under a target BER constraint for each stream and a constant total transmit power constraint. To enable flexible user and stream selection as well as achieving a high total rate, we consider OSDM (orthogonal space division multiplexing) rather than BD (block diagonalization) based MU-MIMO broadcast channels. Numerical results show that our proposed joint bit and power loading with OSDM user and stream selection is effective in increasing the total transmission rate without consuming additional resources.

Monitoring trail (m-trail) has been proposed as an effective approach for link failure localization in all-optical wavelength division multiplexing (WDM) mesh networks. Previous studies in failure localization rely on alarm dissemination via control plane signaling such that the network controller can collect the flooded alarms to form an alarm code for failure identification. Such cross-layer signaling effort obviously leads to additional control complexity. This paper investigates a novel m-trail failure localization scenario, called network-wide local unambiguous failure localization (NWL-UFL), where each node can perform UFL based on locally available on–off state of traversing m-trails, such that alarm dissemination in the control plane can be completely avoided. The paper first defines and formulates the m-trail allocation problem under NWL-UFL and conducts a series of bound analysis on the cover length required for localizing any single-link failure. This is the first study on monitoring trail allocation problem that aims to gain understanding on the consumed cover length via analytical approaches due to the special feature of the NWL-UFL scenario. A novel heuristic algorithm based on random spanning tree assignment (RSTA) and greedy link swapping (GLS) is developed for solving the formulated problem. Extensive simulation on thousands of randomly generated network topologies is conducted to verify the proposed scheme by comparing it to a naive counterpart and with the derived lower bounds. We also demonstrate the impact of topology diversity on the performance of the proposed scheme as well as its scalability regarding network sizes.

We consider energy detection based spectrum sensing for opportunistic SU (Secondary User) transmissions in cognitive radio networks. Due to the time-varying nature of wireless fading channels and PU (Primary User) activities, the instantaneous SINR (Signal to Interference plus Noise Ratio) at the SU receiver changes from slot to slot in a time-slotted system. Unlike the conventional energy detector which uses a fixed value of energy threshold to detect the PU's occurrence, we let the SU transmitter dynamically adjust the threshold according to the instantaneous SINR. Under the constraint of limiting the average interference to the PU within a target level, the objective is to maximize the SU's average transmission rate and throughput. Our task is to determine a proper policy function for threshold control, which formulates the value of the threshold as a function of the SINR to achieve the above objective. In particular, we consider a linear policy function, which allows a higher threshold and thus more aggressive SU transmissions under a larger SINR. Simulation results show that the SU's average transmission rate can be significantly improved using the optimized policy function.

Monitoring trail (m-trail) provides an efficient way to achieve fast and unambiguous failure localization (UFL) in all-optical networks. To remove electronic alarm dissemination, the extended m-trail concept allows trail status checking at each on-trail node. Each monitoring node can localize any failure using its locally available on-off status of the traversing m-trails. In this paper, we introduce a novel algorithm to unambiguously localize any SRLG failure locally at any MN. The proposed algorithm is characterized by a signalling-free alarm collection mechanism which can completely be realized in the optical domain. We will show that in the course of minimizing the number of m-trails, the consumed monitoring resources in terms of cover length can also be effectively reduced. Simulation is conducted to verify the proposed algorithm with respect to the number of m-trails, resource consumption, and running time.

Femtocell networks are widely being deployed to extend cellular network coverage in indoor environments such as office building spaces and homes. In order to mitigate possible co-channel interferences, designs based on the concept of cognitive radio (CR) that enables an overlay between macrocell (primary) and femtocells (secondary) has been considered a promising approach. The paper first introduces a general dynamic sensing mechanism, which is characterized by performing per-time-slot fast sensing upon a channel at the femto devices, in contrast to the conventional CR design that each channel is sensed for identifying available TV bands. Then, based on the proposed sensing mechanism, the paper analyzes the possible throughput achieved by a femto user via a Markov chain model. Numerical experiment is conducted to verify the proposed model and examine different sensing scenarios using the practical GSM standard parameters, and prove the effectiveness of the proposed approach.

We consider power allocation in OFDM based underlay cognitive radio networks with partially known inter-system CSI (Channel State Information). Under a given total transmit power limit at the SU (Secondary User) transmitter, the goal is to assign a certain amount of power for signal transmission in each OFDM sub-channel, such that the SU's overall throughput can be maximized, and the average interference to the PU can be kept within a target outage probability level. The existing algorithm adopts an iterative binary searching process to find the solution, where the classic Water-Filling (WF) is invoked in each loop, which needs a relatively long running time. In this paper, an efficient algorithm is proposed to solve the problem in a much simpler and faster way. Specifically, we first propose an efficient approach to implement WF based on some in-depth theoretical analysis. Then, a novel power allocation algorithm is proposed by removing the binary searching process. Our algorithm runs WF only once and then directly calculates the final solution. Numerical results show that it can run tens to hundreds times faster than the existing algorithms, depending on the total number of OFDM sub-channels.

Achieving fast and precise failure localization has long been a highly desired feature in all-optical mesh networks. Monitoring trail (m-trail) has been proposed as the most general monitoring structure for achieving unambiguous failure localization (UFL) of any single link failure while effectively reducing the amount of alarm signals flooding the networks. However, it is critical to come up with a fast and intelligent m-trail design approach for minimizing the number of m-trails and the total bandwidth consumed, which ubiquitously determines the length of the alarm code and bandwidth overhead for the m-trail deployment, respectively. In this paper, the m-trail design problem is investigated. To gain a deeper understanding of the problem, we first conduct a bound analysis on the minimum length of alarm code of each link required for UFL on the most sparse (i.e., ring) and dense (i.e., fully meshed) topologies. Then, a novel algorithm based on random code assignment (RCA) and random code swapping (RCS) is developed for solving the m-trail design problem. The algorithm is verified by comparison to an integer linear program (ILP) approach, and the results demonstrate its superiority in minimizing the fault management cost and bandwidth consumption while achieving significant reduction in computation time. To investigate the impact of topology diversity, extensive simulation is conducted on thousands of random network topologies with systematically increased network density.

We study SRLG (Shared Risk Link Group) failure monitoring and localization in all-optical WDM (Wavelength Division Multiplexing) networks. All links in each SRLG are logically grouped as a whole, and they fail at the same time when the SRLG failure event occurs. To achieve fast SRLG failure localization, monitoring is carried out at the optical layer using the recently proposed monitoring trail (m-trail) structure. By formulating an ILP (Integer Linear Program), we optimally solve the m-trail allocation problem to achieve unambiguous SRLG failure localization with the minimum monitoring cost. We claim that our work provides the first study in optimally allocating free-routed m-trails for achieving fast and unambiguous SRLG failure localization, with flexible tradeoff between the monitor cost and the bandwidth cost (i.e., supervisory wavelength-links).

Achieving fast and precise failure localization has long been a highly desired feature in all-optical mesh networks. M-trail (monitoring trail) has been proposed as the most general monitoring structure for achieving unambiguous failure localization (UFL) of any single link failure while effectively reducing the amount of alarm signals flooded in the networks. However, it is critical to come up with a fast and intelligent m-trail design approach for minimizing the number of m-trails and the totally consumed bandwidth, which ubiquitously determines the length of alarm code and bandwidth overhead for the M-trail deployment, respectively. In this paper, the m-trail design problem is investigated. To gain deeper understanding of the problem, we firstly conduct a bound analysis on the minimum length of alarm code required for UFL. Then, a novel algorithm based on random code assignment (RCA) and random code swapping (RCS) is developed for solving the m-trail design problem. The algorithm prototype can be found in. The algorithm is verified by comparing with an integer linear program (ILP), and the results demonstrate its superiority in minimizing the fault management cost and bandwidth consumption while achieving significant reduction in computation time. To investigate the impact of topology diversity, extensive simulation is conducted on thousands of random network topologies with systematically increased network connectivity. Lastly, we provide abundant discussions and interesting conclusive remarks that position our discoveries.

We introduce Cooperative Fast Protection (CFP) as a novel protection scheme in WDM networks. CFP achieves capacity-efficient fast protection with the features of node-autonomy and failure-independency. It differs from p-cycle by reusing the released working capacity of the disrupted lightpaths (i.e. stubs) in a cooperative manner. This is achieved by allowing all the failure-aware nodes to switch the traffic, such that the disrupted lightpaths can be protected even if the end nodes of the failed link are not on the protecting cycles. CFP also differs from FIPP p-cycle by not requiring the source node of the disrupted lightpath on the protecting cycle. By jointly optimizing both working and spare capacity placement, we formulate an ILP for CFP design. Numerical results show that CFP significantly outperforms p-cycle by achieving faster protection with much higher capacity efficiency.

We consider optical layer monitoring schemes for fast link failure localization in WDM mesh networks. A new concept monitoring trail (m-trail) is proposed. It differs from the existing monitoring cycle (m-cycle) concept by removing the cycle constraint. As a result, m-trail provides a more flexible all-optical monitoring structure which includes simple, non-simple m-cycles and open trails as special cases. Aiming at minimizing the total monitoring cost, an integer linear program (ILP) is formulated for m-trail design. Numerical results show that the m-trail based scheme significantly outperforms its m-cycle based counterpart.

The concept ofp-cycle (Preconfigured Protection Cycle) allows fast and efficient span protection in WDM mesh networks. Compared to a simpler-cycle, a non-simplep-cycle can traverse a node or span multiple times. As a result, non-simplep- cycles can better explore mesh connectivity of a network. On the other hand, the recently proposed PXT (Pre-Cross-Connected Trail) concept removes the cycle constraint by allowing arbitrary protection trails. In this paper, we carry out a comparative study among these fast protection schemes, and formulate ILPs (Integer Linear Programs) for non-simplep-cycle and PXT design. As far as we know, our ILP for non-simplep-cycle design is the first one without candidate cycle enumeration, and our ILP for PXT design is the first one proposed in this area. Based on our ILPs, we find simple, non-simplep-cycle and PXT solutions for a simple network. We show that the required spare capacity for 100% protection in each scheme is reduced in the same order above.

Efficient broadcast schemes are essential in wireless mesh networks (WMNs) for minimizing the content update time. In this paper, we consider the widest spanning tree problem in a multi-channel multi-interface WMN, where the width of a tree is determined by the bottleneck link bandwidth. To the best of our knowledge, we present the first effort in solving the widest spanning tree problem using mathematical formulation. In our model, we jointly consider and solve the problems of channel assignment, routing, scheduling and server/root placement. Unlike other spanning tree approaches, we allow WMN nodes to have heterogeneous number of network interface cards (NICs), and multiple NICs of a node can share the same assigned set of channels. To find a practical schedule, we also introduce the channel conflict graph and NIC constraint graph, and show that the associated scheduling problem is equivalent to the classic graph coloring problem.

Fast link failure detection in all-optical networks (AONs) can be achieved using monitoring cycles (m-cycles). An m-cycle is a loop-back optical connection of supervisory wavelengths with a dedicated monitor. Compared to the channel-based or link-based monitoring schemes, m-cycle based schemes require much less number of monitors. In this paper, we propose an ILP (Integer Linear Program) formulation for m-cycle design to minimize the network cost. Our contributions are two-fold: 1) non-simple m-cycles are enabled; and 2) an efficient tradeoff is allowed between the monitor cost and the bandwidth cost. Numerical results show that our algorithm outperforms existing algorithms with a significant performance gain. © 2007 IEEE.

The concept of p-cycle (Preconfigured Protection Cycle) allows fast and efficient span protection in WDM mesh networks. To construct p-cycles, conventional algorithms need to enumerate all the candidate cycles in the network before ILP (Integer Linear Program) can be applied to find the optimal solution. To reduce the size of the candidate set and thus speed up the optimization process, heuristic algorithms are proposed for candidate cycle pre-selection at the cost of lower solution quality. Recently, some interesting ILP formulations were proposed to construct p-cycles without candidate cycle enumeration/preselection. But they tend to require a long running time. Following the approach of no candidate cycle enumeration, we formulate a new ILP based on flow conservation in this paper. Numerical results show that our new ILP runs much faster than the existing ones.

Burst loss and delay are two main issues in optical burst switching (OBS) networks. In OBS, if the hop-count between the source-destination node pair can be reduced, both the control packet and the corresponding data burst will suffer less risk of contention, and the delay caused by offset time will be reduced as well. Therefore, it is meaningful to overlay OBS upon a virtual topology with reduced network diameter and average hop-count. In this paper, a novel algorithm LWMD (Least Weight Minimum Diameter) is proposed to construct virtual topology for this goal. Based on the virtual topology obtained, two traffic accommodation schemes are also designed to provision wavelengths for a given traffic matrix. This provides a comprehensive solution to improve the performance of OBS networks.

The notion of p-cycle (preconfigured protection cycle) allows capacity efficient schemes to be designed for fast span protection in WDM mesh networks. Conventional p-cycle construction algorithms need to enumerate/pre-select candidate cycles before ILP (integer linear program) can be applied. In this paper, we propose a new algorithm which is only based on ILP. When the required number of p-cycles is not too large, our ILP can generate optimal/suboptimal solutions in reasonable amount of running time.

A hybrid electronic/optical packet switch consists of electronically buffered line-cards interconnected by an optical switch fabric. It provides a scalable switch architecture for next generation high-speed routers. Due to the non-negligible switch reconfiguration overhead, many packet scheduling algorithms are invented to ensure performance guaranteed switching (i.e. 100% throughput with bounded packet delay), at the cost of speedup. In particular, minimum delay performance can be achieved if an algorithm can always find a schedule of no more than N configurations for any input traffic matrix, where N is the switch size. Various minimum delay scheduling algorithms (MIN, alphai-SCALE and QLEF) are proposed. Among them, QLEF requires the lowest speedup bound. In this paper, we show that the existing speedup bound for QLEF is not tight enough. A new bound which is 10% lower than the existing one is derived.

Light-trail has emerged as a promising candidate for enabling IP over WDM networks. The problem of static light- trail assignment is to find a set of light-trails to cover the given traffic demands, such that the total number of light-trails required is minimized. Because of the power loss caused by splitting at each hop, the length of a light-trail is limited. Existing light-trail assignment algorithms adopt ILP (Integer Linear Programming) approach. Due to the high complexity of ILP, such algorithms are not scalable. In this paper, we propose an efficient heuristic algorithm LTA (Light-Trail Assignment) to solve this problem. In LTA, each light-trail is judiciously assigned based on the request discreteness, the shortest path length and the traffic volume of each request. A reference node mechanism is also designed to enhance the solution. Numerical results show that LTA always returns sub-optimal solutions.

To achieve fast link failure detection in all-optical networks, the notion of monitoring-cycle (m-cycle) is introduced. The best known m-cycle construction algorithm (HST [7]) adopts a spanning tree-based approach. In this paper, we propose a new algorithm M2-CYCLE to construct a set of minimum-length m- cycles (or m2-cycles) for more efficient link failure detection. We prove that the performance of M2-CYCLE is never worse than any spanning tree-based approach. Comparing M2-CYCLE to the existing algorithms, we show that it uses the least amount of network resources (measured by the number of cycles, cover length and monitoring wavelength requirement) to achieve the most accurate link failure detection (measured by localization degree).

Aiming at providing 100% throughput with bounded packet delay, we consider traffic scheduling in high-speed routers with optical switch fabrics. Because of the switch reconfiguration overhead, a speedup in the switch fabric is essential. For a given packet delay bound, our objective is to minimize the overall speedup S = Sreconfiguretimes Sscheduleso as to lower the implementation cost. Leveraging on the existing ADAPTIVE and DOUBLE algorithms, we show the speedup can be reduced by improving scheduling efficiency. Specifically, following the traffic matrix decomposition in ADAPTIVE and DOUBLE, we shift some packets from the residue matrix R to the quotient matrix Q, while keeping the number of configurations required to cover each matrix the same. We reduce the number of time slots required to send the diminished residue matrix. In case of DOUBLE, this translates into a 12.5% cut in Sschedule(from 2 to 1.75). We call the resulting algorithm Scheduling Residue First (SRF).

For performance guaranteed OPS switches with reconfiguration overhead, it has been shown that packet delay can be minimized by using N switch configurations (where N is the switch size) to schedule the traffic. However, this usually involves an exorbitant speedup requirement, which makes it impractical under current technology. In this paper, a new minimum-delay scheduling algorithm QLEF (quasi largest-entry-first) is proposed. We prove that QLEF pushes the required speedup bound to the lowest known level. As an example, when N=950, QLEF only requires a speedup of Sschedule=21.33 instead of 42.25 for MIN (B. Towles and W.J. Dally, 2003) and 30.27 for ai-SCALE (B. Wu and K.L. Yeung, 2005). This gives a 50% improvement over MIN and 30% over ai-SCALE

An optical packet switch (OPS) is called performance guaranteed if it can achieve 100% throughput with bounded packet delay. Presently, high speedup requirement and large packet delay are two main disadvantages in designing performance guaranteed OPS. Survivability is another important issue that must be considered for real OPS implementations. In this paper, we propose a two-layer parallel OPS architecture together with an efficient scheduling scheme to address all the above issues. The tradeoff between speedup and packet delay under this new parallel architecture is also formulated to provide more design flexibility. Compared to the single-layer OPS, our proposed solution can simultaneously reduce both speedup and packet delay. For example, a delay of 4/spl delta/N slots can be achieved with a speedup of 2 in our solution (where N is the switch size and /spl delta/ is the switch reconfiguration overhead), whereas the single-layer OPS needs a speedup of 6 for a delay of 7/spl delta/N slots. We show that this significant improvement benefits from a careful overall design rather than simply adding an extra switching layer.

In order to achieve the minimum traffic delay in a performance guaranteed optical packet switch (OPS) with reconfiguration overhead, the switch fabric has to use the minimum number of configurations (i.e. N configurations where N is the switch size) for traffic scheduling. This requires a very high speedup in the switch fabric to compensate for the loss in scheduling efficiency. The high speedup requirement makes the idea of using N configurations (to schedule the traffic) impractical under current technology. In this paper, we propose a new scheduling algorithm called /spl alpha//sup i/-SCALE to lower the speedup required. Compared with the existing MIN algorithm B. Towles, et al., 2003, /spl alpha//sup i/-SCALE succeeds in pushing the speedup bound (i.e. worst-case speedup requirement) to a much lower level. For example, when N=200, the speedup bound required to compensate the loss in scheduling efficiency is 30.75 for MIN, whereas 23.45 is sufficient for our /spl alpha//sup i/-SCALE.

Providing QoS guarantees for Internet services is very important. It evokes the issue that packet switches should provide guaranteed performance (i.e. 100% throughput with bounded worst-case delay). Optical switching technology is widely considered as an excellent solution for packet switches in future networks. However, to achieve guaranteed performance in optical packet switches, an internal speedup is required due to the existence of reconfiguration overhead. How to reduce the internal speedup is the main concern for making these switches practical. In this paper, we first derive the internal speedup S as a function of the number of switch configurations N/sub S/ and the reconfiguration overhead /spl delta/, or S=f(N/sub S/,/spl delta/). We show that the recently proposed ADJUST algorithm is flawed. Based on the internal speedup function we derived, a new algorithm (ADAPTIVE), with time complexity of O((/spl lambda/-1)N/sup 2/logN), is proposed to minimize S.