Recently, network coding has been applied to the loss recovery of reliable multicast in wireless networks, where multiple lost packets are XOR-ed together as one packet and forwarded via single retransmission, resulting in a significant reduction of bandwidth consumption. In this paper, we first prove that maximizing the number of lost packets for XOR-ing, which is the key part of the available network coding-based reliable multicast schemes, is actually a complex NP-complete problem. To address this limitation, we then propose an efficient heuristic algorithm for finding an approximately optimal solution of this optimization problem. Furthermore, we show that the packet coding principle of maximizing the number of lost packets for XOR-ing sometimes cannot fully exploit the potential coding opportunities, and we then further propose new heuristic-based schemes with a new coding principle. Simulation results demonstrate that the heuristic-based schemes have very low computational complexity and can achieve almost the same transmission efficiency as the current coding-based high-complexity schemes. Furthermore, the heuristic-based schemes with the new coding principle not only have very low complexity, but also slightly outperform the current high-complexity ones.

Vertical stacking is a novel technique for creating nonblocking (crosstalk-free) optical multistage interconnection networks (MINs). In this paper, we propose a new class of optical MINs, the vertically stacked Benes (VSB) networks, for crosstalk-free realization of permutations in a single pass. An NN VSB network requires at most O(Nlog N) switching elements, which is the same as the Benes network, and much lower overall hardware cost than that of the existing optical MINs built on the combination of horizontal expansion and vertical stacking of banyan networks, to provide the same crosstalk-free permutation capability. Furthermore, the structure of VSB networks provides a more flexible way for constructing optical MINs because they give more choices in terms of the number of stages used in an optical MIN. We also present efficient algorithms to realize crosstalk-free permutations in an NN VSB network in time O(Nlog N), which matches the same bound as required by the reported schemes.

Genetic Algorithms (GA) provide an attractive approach to solving the challenging problem of dynamic routing and wavelength assignment (RWA) in optical Wavelength Division Multiplexing (WDM) networks, because they usually achieve a significantly low blocking probability. Available GA-based dynamic RWA algorithms were designed mainly for WDM networks with a wavelength continuity constraint, and they cannot be applied directly to WDM networks with wavelength conversion capability. Furthermore, the available GA-based dynamic RWA algorithms suffer from the problem of requiring a very time consuming process to generate the first population of routes for a request, which may results in a significantly large delay in path setup. In this paper, we study the dynamic RWA problem in WDM networks with sparse wavelength conversion and propose a novel hybrid algorithm for it based on the combination of mobile agents technique and GA. By keeping a suitable number of mobile agents in the network to cooperatively explore the network states and continuously update the routing tables, the new hybrid algorithm can promptly determine the first population of routes for a new request based on the routing table of its source node, without requiring the time consuming process associated with current GA-based dynamic RWA algorithms. To achieve a good load balance in WDM networks with sparse wavelength conversion, we adopt in our hybrid algorithm a new reproduction scheme and a new fitness function that simultaneously takes into account the path length, number of free wavelengths, and wavelength conversion capability in route selection. Our new hybrid algorithm achieves a better load balance and results in a significantly lower blocking probability than does the Fixed-Alternate routing algorithm, both for optical networks with sparse and full-range wavelength converters and for optical networks with sparse and limited-range wavelength converters. This was verified by an extensive simulation study on the ns-2 network simulator and two typical network topologies. The ability to guarantee both a low blocking probability and a small setup delay makes the new hybrid dynamic RWA algorithm very attractive for current optical circuit switching networks and also for the next generation optical burst switching networks.

Three dimensional (3D) integrated circuits (ICs) have the potential to significantly enhance VLSI chip performance, functionality and device packing density. Interconnects delay and signal integrity issues are critical in chip design. In this paper, we extend the idea of redundant via insertion of conventional 2D ICs and propose an approach for vias insertion/placement in 3D ICs to minimize the propagation delay of interconnects with the consideration of signal integrity. The simulation results based on a 65 nm CMOS technology demonstrate that our approach in general can result in a 9% improvement in average delay and a 26% decrease in reflection coefficient. It is also shown that the proposed approach can be more effective for interconnects delay improvement when it is integrated with the buffer insertion in 3D ICs.

Available statistical skew models are too conservative in estimating the expected clock skew of a well-balanced H-tree. New closed form expressions are presented for accurately estimating the expected values and the variances of both the clock skew and the largest clock delay of a well-balanced H-tree. Based on the new model, clock period optimizations of wafer scale H-tree clock network are investigated under both conventional clocking mode and pipelined clocking mode. It is found that when the conventional clocking mode is used, clock period optimization of wafer scale H-tree is reduced to the minimization of expected largest clock delay under both area restriction and power restriction. On the other hand, when the pipelined clocking mode is considered, the optimization is reduced to the minimization of expected clock skew under power restriction. The results obtained in this paper are very useful in the optimization design of wafer scale H-tree clock distribution networks.

Shared-Memory Optical Packet (SMOP) switch architecture is very promising for significantly reducing the amount of required optical memory, which is typically constructed from fiber delay lines (FDLs). The current reservation-based scheduling algorithms for SMOP switches can effectively utilize the FDLs and achieve a low packet loss rate by simply reserving the departure time for each arrival packet. It is notable, however, that such a simple scheduling scheme may introduce a significant packet out of order problem. In this paper, we first identify the two main sources of packet out of order problem in the current reservation-based SMOP switches. We then show that by introducing a "last-timestamp" variable and modifying the corresponding FDLs arrangement as well as the scheduling process in the current reservation-based SMOP switches, it is possible to keep packets in-sequence while still maintaining a similar delay and packet loss performance as the previous design. Finally, we further extend our work to support the variable-length burst switching.

The capacity of general mobile ad hoc networks (MANETs) remains largely unknown up to now, which significantly hinders the development and commercialization of such networks. Available throughput capacity studies of MANETs mainly focus on either the order sense capacity scaling laws, the exact throughput capacity under a specific algorithm, or the exact throughput capacity without a careful consideration of critical wireless interference and transmission range issues. In this paper, we explore the exact throughput capacity for a class of MANETs, where we adopt group-based scheduling to schedule simultaneous link transmissions for interference avoidance and allow the transmission range of each node to be adjusted. We first determine a general throughput capacity upper bound for the concerned MANETs, which holds for any feasible packet delivery algorithm in such networks. We then prove that the upper bound we determined is just the exact throughput capacity for this class of MANETs by showing that for any traffic input rate within the throughput capacity upper bound, there exists a corresponding two-hop relay algorithm to stabilize such networks. A closed-form upper bound for packet delay is further derived under any traffic input rate within the throughput capacity. Finally, based on the network capacity result, we examine the impacts of transmission range and node density upon network capacity.

We focus on non-conflicting construction of an optical multistage feedforward network to emulate the N-to-1 output buffer multiplexer by using switched fiber delay line (SDL). In [1], Y.T. Chen et al. presented a sufficient condition (an upper bound) for the number of delay lines required for such a multiplexer with variable length bursts. In this paper, we first give an improved upper bound. Then we develop a framework to construct an arrival case of bursts which can be used to achieve a necessary condition (a lower bound). These results are further extended to the feedforward construction of N-to-N output buffer switch. Through simulation and performance comparison, we find that the new bounds can significantly decrease the hardware cost for constructing both the feedforward SDL-based multiplexer and output buffer switch while still provide the same performance as that of the old ones.

Routing is still a challenging issue for wireless sensor networks (WSNs), in particular for WSNs with a non-uniform deployment of nodes. This paper introduces a Node Aggregation Degree-aware Random Routing (NADRR) algorithm for non-uniform WSNs with the help of two new concepts, namely the Local Vertical Aggregation Degree (LVAD) and Local Horizontal Aggregation Degree (LHAD). Our basic idea is to first apply the LVAD and LHAD to determine one size-proper forwarding region (rather than a fixed-size one as in uniform node deployment case) for each node participating in routing, then select the next hop node from the size-proper forwarding region in a probabilistic way, considering both the residual energy and distribution of nodes. In this way, a good adaptability to the non-uniform deployment of nodes can be guaranteed by the new routing algorithm. Extensive simulation results show that in comparison with other classical geographic position based routing algorithms, such as GPSR, TPGF and CR, the proposed NADRR algorithm can result in lower node energy consumption, better balance of node energy consumption, higher routing success rate and longer network lifetime.

The fading channel model is seen as an important approach that can efficiently capture the basic time-varying properties of wireless channels, while physical layer security is a promising approach to providing a strong form of security. This paper focuses on the fundamental performance study of applying physical layer security to achieve secure and reliable information transmission over the fading wire-tap channel. For the practical scenario where the main channel is correlated with the eavesdropper channel but only the real time channel state information (CSI) of the main channel is known at the transmitter, we conduct a comprehensive study on the fundamental performance limits of this system by theoretically modeling its secrecy capacity, transmission outage probability and secrecy outage probability. With the help of these theoretical models, we then explore the inherent performance tradeoffs under fading wire-tap channel and also the potential impact of channel correlation on such tradeoffs.

Throughput capacity is of great importance for the design and performance optimization of mobile ad hoc networks (MANETs). We study the exact per node throughput capacity of MANETs under a general 2HR-(g, x, f) routing scheme which combines erasure coding and packet replication techniques. Under this scheme, a source node first encodes a group of g packets into x (x ≥ g) distinct coded packets, and then replicates each of the coded packets to at most f relay nodes which help to forward them to the destination node. All original packets can be recovered once the destination node receives any g distinct coded packets of the group. To study the throughput capacity, we first construct two absorbing Markov chain models to depict the complicated packet delivery process under the routing scheme. Based on these Markov models, an analytical expression of the throughput capacity is derived. Extensive simulation and numerical results are provided to verify the accuracy of theoretical results on throughput capacity and to illustrate how system parameters will affect the throughput capacity in MANETs. Interestingly, we find that the replication of coded packets can improve the throughput capacity when the parameter x is relatively small.

Crosstalk in optical switch is an intrinsic drawback of optical networks, and avoiding crosstalk is important for making optical network work properly. Horizontal expansion and vertical stacking are two basic techniques for creating nonblocking multistage interconnection networks (MINs). Rearrangeable (nonblocking) optical MINs are feasible since they have lower complexity than their strictly nonblocking counterparts. In this paper, we study the crosstalk-free permutations in rearrangeable optical MINs built on a combination of horizontal expansion and vertical stacking of banyan networks, and provide a scheme for realizing crosstalk-free permutations in this kind of optical MINs. The basic idea of this scheme is to first decompose a permutation into multiple partial permutations by using Euler Split technique, then route and realize each of these partial permutations crosstalk-free in one plane (stacked copy) of a MIN based on both the Euler Split technique and self-routing property of a banyan network. The tradeoff between the overall time complexity and hardware cost of this class of MINs is also explored in this paper.

The Distributed Denial of Service attack (DDoS) is one of the major threats to network security that exhausts network bandwidth and resources. Recently, an efficient approach Live Baiting was proposed for detecting the identities of DDoS attackers in web service using low state overhead without requiring either the models of legitimate requests nor anomalous behavior. However, Live Baiting has two limitations. First, the detection algorithm adopted in Live Baiting starts with a suspects list containing all clients, which leads to a high false positive probability especially for large web service with a huge number of clients. Second, Live Baiting adopts a fixed threshold based on the expected number of requests in each bucket during the detection interval without the consideration of daily and weekly traffic variations. In order to address the above limitations, we first distinguish the clients activities (Active and Non-Active clients during the detection interval) in the detection process and then further propose a new adaptive threshold based on the Change Point Detection method, such that we can improve the false positive probability and avoid the dependence of detection on sites and access patterns. Extensive trace-driven simulation has been conducted on real Web trace to demonstrate the detection efficiency of the proposed scheme in comparison with the Live Baiting detection scheme.

The multi-log2N network architecture is attractive for constructing optical switches, and the related routing algorithms are critical for the operation and efficiency of such switches. Although several routing algorithms have been proposed for multi-log2N networks, a full performance comparison among them has not been published up to now. Thus, we rectify this omission by providing such a comparison in terms of blocking probability, time complexity, hardware cost and load balancing capability. Notice that the load balance is important for reducing the peak power requirement of a switch, so we also propose in this paper a new routing algorithm for optical multi-log2N networks to achieve a better load balance.

Secure sensor localization is a prerequisite for many sensor networks to retrieve trustworthy data. However, most of existing node positioning systems were studied in trust environment and are therefore vulnerable to malicious attacks. In this work, we develop a robust node positioning mechanism(ROPM) to protect localization techniques from position attacks. Instead of introducing countermeasures for every possible internal or external attack, our approach aims at making node positioning system attack-tolerant by removing malicious beacons. We defeat internal attackers and external attackers by applying different strategies, which not only achieves robustness to attacks but also dramatically reduces the computation overhead. Finally, we provide detailed theoretical analysis and simulations to evaluate the proposed technique.

Arrayed waveguide grating (AWG) is a promising technology for constructing high-speed large-capacity WDM switches, because it can switch fast, is scalable to large size and consumes little power. To take the full advantage of high-speed AWG, the routing control of a massive AWG-based switch should be as simple as possible. In this paper, we focus on the self-routing design of AWG-based switches with O(1) constant routing complexity and propose a novel construction of self-routing AWG switches that can guarantee the attractive nonblocking property for both the wavelength-to-wavelength and wavelength-to-fiber request models. We also fully analyze the proposed design in terms of its blocking property, hardware cost and crosstalk performance and compare it against traditional designs. It is expected that the proposed construction will be useful for the design and all-optical implementation of future ultra high-speed optical packet/burst switches.

Vertical stacking is a novel technique for building switching networks, and packing multiple compatible connections together is an effective strategy to reduce network hardware cost. In this paper, we study the crosstalk-free permutation capability of an optical switching network built on the vertical stacking of optical banyan networks to which packing strategy is applied. We first look into the nonblocking condition of this optical switching network. We then study the crosstalk-free permutation in this network by decomposing a permutation evenly into multiple crosstalk-free partial permutations (CFPPs) and realizing each CFPP in a stacked plane of the network such that a crosstalk-free permutation can be performed in a single pass. We present a rigorous proof of CFPP decomposability of a permutation and also a complete algorithm for CFPP decomposition. The possibility of a tradeoff between the number of passes and the number of planes required for realizing a crosstalk-free permutation in this network is also explored in this paper.

This paper investigates data uploading in cellular networks with the consideration of device-to-device (D2D) communications. A generalized data uploading scheme is proposed by leveraging D2D cooperation among the devices to reduce the data uploading time. In this scheme, we extend the conventional schemes on cooperative D2D data uploading for cellular networks to a more general case, which considers D2D cooperation among both the devices with or without uploading data. To motivate D2D cooperation among all available devices, we organize the devices within communication range by offering them rewards to construct multi-hop D2D chains for data uploading. Specifically, we formulate the problem of chain formation among the devices for data uploading as a coalitional game. Based on merge-and-split rules, we develop a coalition formation algorithm to obtain the solution for the formulated coalitional game with convergence on a stable coalitional structure. Finally, extensive numerical results show the effectiveness of our proposed scheme in reducing the average data uploading time.

Recently, network coding has been applied to reliable multicast in wireless networks for packet loss recovery, resulting in significant bandwidth savings. In network-coding-based multicast schemes, once a receiver receives one packet from the source it sends an ACK to acknowledge packet receipt. Such acknowledgment mechanism has the following limitation: when an ACK from one receiver is lost, the source considers the corresponding packet to be lost at this receiver and then conducts unnecessary retransmission. Motivated by this basic observation, we first propose a block-based acknowledgment mechanism, where an ACK now acknowledges all previously received packets in the current block such that the later received ACKs can offset the loss of previous ACKs. To reduce the total amount of feedback overhead, we further propose a more simple feedback mechanism, in which the receivers only start to send acknowledgments from the last two packets (not from the first one as in the first mechanism) of the current block. The first mechanism has the potential to achieve better performance over the latter one in wireless networks with long deep fades (i.e., continuous packet losses) due to its continuous transmissions of ACKs, while the second one is more promising for wireless networks with only random packet losses due to its smaller amount of feedback. Both theoretical and simulation results demonstrate that, compared to the current acknowledgment mechanism in network-coding-based reliable multicast schemes, these two mechanisms can achieve much higher bandwidth efficiency.

The evolution of VLSI chips towards larger die size, smaller feature size and faster clock speed makes the clock distribution an increasingly important issue. In this paper, we propose a new clock distribution network (CDN), namely Variant X-Tree, based on the idea of X-Architecture proposed recently for efficient wiring within VLSI chips. The Variant X-Tree CDN keeps the nice properties of equal-clock-path and symmetric structure of the typical H-Tree CDN, but results in both a lower maximal clock delay and a lower clock skew than its H-Tree counterpart, as verified by an extensive simulation study that incorporates simultaneously the effects of process variations and on-chip inductance. We also propose a closed-form statistical models for evaluating the skew and delay of the Variant X-Tree CDN. The comparison between the theoretical results and the simulation results indicates that the proposed statistical models can be used to efficiently and rapidly evaluate the performance of the variant X-Tree CDNs.