JAVA IEEE 2012 PROJECT ABSTRACTS
DOMAIN - MOBILE COMPUTING
APPROXIMATION ALGORITHMS FOR DATA BROADCAST IN WIRELESS NETWORKS
Broadcasting is a fundamental operation in wireless networks and plays an important role in the communication protocol design. In multihop wireless networks, however, interference at a node due to simultaneous transmissions from its neighbors makes it nontrivial to design a minimum-latency broadcast algorithm, which is known to be NP-complete.
We present a simple 12-approximation algorithm for the one-to-all broadcast problem that improves all previously known guarantees for this problem. We then consider the all-to-all broadcast problem where each node sends its own message to all other nodes. For the all-to-all broadcast problem, we present two algorithms with approximation ratios of 20 and 34, improving the best result available in the literature.
Finally, we report experimental evaluation of our algorithms. Our studies indicate that our algorithms perform much better in practice than the worst-case guarantees provided in the theoretical analysis and achieve up to 37 percent performance improvement over existing schemes
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
CHANNEL ESTIMATION FOR OPPORTUNISTIC SPECTRUM ACCESS: UNIFORM AND RANDOM SENSING
The knowledge of channel statistics can be very helpful in making sound opportunistic spectrum access decisions. It is therefore desirable to be able to ef ficiently and accurately estimate channel statistics. In this paper we study the problem of optimally placing sensing/sampling times over a time window so as to get the best estimate on the parameters of an on-off renewal channel. We are particularly interested in a sparse sensing regime with a small number of samples relative to the time window size.
Using Fisher information as a measur e, we analytically derive the best and worst sensing sequences under a sparsity condition. We also present a way to derive the bes t/worst sequences without this condition using a dynamic programming approach. In both cases the worst turns out to be the uniform sensing sequence, where sensing times are evenly spaced within the window. Interestingly the best sequence is also uniform but with a much smaller sensing interval that requires a priori knowledge of the channel parameters.
With these results we argue that without a priori knowledge, a robust sensing strategy should be a randomized strategy. We then compare different random schemes using a family of distributions generated by the circular β ensemble, and propose an adaptive sensing scheme to effectively track time-varying channel parameters. We further discuss the applicability of compressive sensing for this problem
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
AN MIMO CONFIGURATION MODE AND MCS LEVEL SELECTION SCHEME BY FUZZY Q-LEARNING FOR HSPA ÞSYSTEMS
In this paper, we propose afuzzy Q-learning-based MIM O configuration mode and MCS level (FQL-MOMS) selection scheme for high speed packet access evolution (HSPA þ) systems. The FQL-MOMS selection scheme intends to enhance the system throughput under the block error rate (BLER) requirement guarantee.
It will determine an appropriate MIMO configuration mode and MCS (modulation and coding scheme) level for packet data transmission in HSPA þ systems, under the situations that the channel status is varying and the channel quality indication (CQI) has report delay.
The FQL-MOMS scheme considers not only the reported CQI and the last transmission result but also the BLER performance metric and the transmission efficiency. Moreover, it is effectively configured, where the fuzzy rules and the reinforcement signals for the Q-learning algorithm are sophisticatedly designed.
Simulation results show that the proposed FQL-MOMS scheme increases the system throughput by up to 49.3 and 35.9 percent, compared to the conventional adaptive threshold selection (ATS) scheme [12] and the Q-HARQ scheme [14], respectively, under the BLER requirement fulfillment
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
A NOVEL MAC SCHEME FOR MULTICHANNEL COGNITIVE RADIO AD HOC NETWORKS
This paper proposes a novel medium access control (MAC) scheme for multichannel cognitive radio (CR) ad hoc networks, which achieves high throughput of CR system while protecting primary users (PUs) effectively.
In designing the MAC scheme, we consider that the PU signal may cover only a part of the network and the nodes can have the different sensing result for the same PU even on the same channel. By allowing the nodes to use the channel on which the PU exists as long as their transmissions do not disturb the PU, the proposed MAC scheme fully utilizes the spectrum access opportunity.
To mitigate the hidden PU problem inherent to multichannel CR networks where the PU signal is detectable only to some nodes, the proposed MAC scheme adjusts the sensing priorities of channels at each node with the PU detection information of other nodes and also limits the transmission power of a CR node to the maximum allowable power for guaranteeing the quality of service requirement of PU.
The performance of the proposed MAC scheme is evaluated by using simulation. The simulation results show that the CR system with the proposed MAC accomplishes good performance in throughput and packet delay, while protecting PUs properly.
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
A COST ANALYSIS FRAMEWORK FOR NEMO PREFIX DELEGATION-BASED SCHEMES
Network Mobility (NEMO) efficiently manages the mobility of multiple nodes that moves together as a mobile network. A major limitation of the basic protocol in NEMO is the inefficient route between end hosts. A number of prefix delegation-based schemes have been proposed in the literature to solve the route optimization problem in NEMO.
Approaches used by the schemes trade off delivery of packets through the partially optimized route with signaling and other processing overheads. Cost of delivering packets through the partially optimized route along with signaling and processing cost need to be measured to find out the gain from tradeoff. However, cost analysis performed so far on NEMO protocols consider only the cost of signaling.
In this paper, we have developed analytical framework to measure the costs of the basic protocol for NEMO, and four representative prefix delegation-based schemes. Our results show that cost of packet delivery through the partially optimized route dominates over other costs.
Therefore, optimizing the route completely is preferable to reduction of signaling as far as cost of network mobility is concerned. Our cost analysis framework will help in decision making to select the best route optimization scheme depending on the load imposed by the scheme on the infrastructure.
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
USING ROTATABLE AND DIRECTIONAL (R&D) SENSORS TO ACHIEVE TEMPORAL COVERAGE OF OBJECTS AND ITS SURVEILLANCE APPLICATION
Due to hardware design or cost consideration, sen-sors may possess sector-like sensing coverage. Furthermore, by stepper motors, sensors can rotate to cover the objects around them. This type of sensors are called rotatable and directional (R&D) sensors. Through rotation, R&D sensors provide temporal coverage to objects by “periodically” detecting their existence.
In the paper, we first develop an event-driven surveillance system by R&D sensors, where objects are monitored by the sensors equipped with infrared detectors and cameras. When an object is taken away, the sensor monitoring the object reports a warning message along with detailed snapshots from the surroundings.
Then, motivated by the system, we formulate an R&D sensor deployment problem, which tries to deploy the minimum number of R&D sensors to cover a given set of objects such that each object is covered by 0 <δ ≤ 1 ratio of time in every frame. We show this problem to be NP-hard and propose two efficient heuristics.
The maximum covering deployment (MCD) heuristic iteratively deploys a sensor to cover more objects, and performs well when objects congregate together. The disk-overlapping deployment (DOD)heuristic deploys sensors to cover the joint sectors of overlapped disks, so it works better when objects are arbitrarily placed in the sensing field.
The paper contributes in defining a new temporal coverage model by R&D sensors, developing a surveillance application for this model, and proposing efficient heuristics to reduce the deployment cost
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
UNDERSTANDING NODE LOCALIZABILITY OF WIRE-LESS AD-HOC AND SENSOR NETWORKS
Location awareness is highly critical for wireless ad-hoc and sensor networks. Many efforts have been made to solve the problem of whether or not a network can be local-ized. Nevertheless, based on the data collected from a working sensor network, it is observed that the network is not always entirely localizable.
Theoretical analyses also suggest that, in most cases, it is unlikely that all nodes in a network are localizable, although a (large) portion of the nodes can be uniquely located. Existing studies merely ex-amine whether or not a network is localizable as a whole; yet two fundamental questions remain unaddressed: First, given a network configuration, whether or not a specific node is localizable? Second, how many nodes in a network can be located and which are them? In this study, we analyze the limitation of previous works an d propose a novel concept of node localizability.
By deriving the necessary and sufficient conditions for node localizability, for the first time, it is possible to analyze how many n odes one can expect to locate in sparsely or moderately connected networks.
To validate this design, we implement our solution on a real-world sys-tem and the experimental results show that node localizability provides useful guidelines for network deployment and other location-based services
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
STORM: A FRAMEWORK FOR INTEGRATED ROUTING, SCHEDULING AND TRAFFIC MANAGEMENT IN AD HOC NETWORKS
A cross-layer framework is introduced for the effective dissemination of real-time and elastic traffic in multi-hop wireless networks called STORM (Scheduling and Traffic Management in Ordered Routing Meshes).
Unicast and multicast routes are estab-lished in coordination with the scheduling of transmissions and band-width reservations in a way that bandwidth and delay guarantees can be enforced on a per-hop and end-to-end basis. The routes established in STORM are shown to be loop-free and real-time packets forwarded along these routes are shown to have bounded end-to-end delays.
Results from detailed simulation experiments show that, compared to a protocol stack consisting of 802.11 DCF for channel access, AODV or OLSR for unicast routing, and ODMRP for multicast routing, STORM attains similar or better performance for elastic traffic, and up to two orders of magnitude improvement in end-to-end delays, with twice the amount of data delivery for real-time traffic while inducing considerably less communication overhead.
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
THE BOOMERANG PROTOCOL: TYING DATA TO GEOGRAPHIC LOCATIONS IN MOBILE DISCONNECTED NETWORKS
We present the boomerang protocol to efficiently retain information at a particular geographic location in a sparse network of highly mobile nodes without using infrastructure networks. To retain information around certain physical location, each mobile device passing that location will carry the information for a short while.
This approach can become challenging for remote locations around which only few nodes pass by. To address this challenge, the boomerang protocol, similar to delay-tolerant communication, first allows a mobile node to carry packets away from their location of origin and periodically returns them to the anchor location.
A unique feature of this protocol is that it records the geographical trajectory while moving away from the origin and exploits the recorded trajectory to optimize the return path. Simulations using automotive traffic traces for a southern New Jersey region show that the boomerang protocol improves packet return rate by 70 percent compared to a baseline shortest path routing protocol.
This performance gain can become even more significant when the road map is less connected. Finally, we look at adaptive protocols that can return information within specified time limits
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
PROSPECT: A PROACTIVE SPECTRUM HANDOFF FRAMEWORK FOR COGNITIVE RADIO AD HOC NETWORKS WITHOUT COMMON CONTROL CHANNEL
Cognitive Radio (CR) technology is a promising solution to enhance the spectrum utilization by enabling unlicensed users to exploit the spectrum in an opportunistic manner. Since unlicensed users are temporary visitors to the licensed spectrum, they are required to vacate the spectrum when a licensed user reclaims it.
Due to the randomness of the appearance of licensed users, disruptions to both licensed and unlicensed communications are often difficult to prevent, which may lead to low throughput of both licensed and unlicensed communications. In this paper, a proactive spectrum handoff framework for CR ad hoc networks, ProSpect, is proposed to address these concerns.
In the proposed framework, Channel-Switching (CW) policies and a proactive spectrum handoff protocol are proposed to let unlicensed users vacate a channelbefore a licensed user utilizes it to avoid unwanted interference. Network coordination schemes for unlicensed users are also incorporated into the spectrum handoff protocol design.
Moreover, a distributed channel selection scheme to eliminate collisions among unlicensed users in a multiuser spectrum handoff scenario is proposed. In our proposed framework, unlicensed users coordinate with each other without using a Common Control Channel (CCC), which is highly adaptable in a spectrum-varying environment.
We compare our proposed proactive spectrum handoff protocol with a reactive spectrum handoff protocol, under which unlicensed users switch channels after collisions with licensed transmissions occur. Simulation results show that our proactive spectrum handoff outperforms the reactive spectrum handoff approach in terms of higher throughput and fewer collisions to licensed users.
Furthermore, our distributed channel selection can achieve higher packet delivery rate in a multiuser spectrum handoff scenario, compared with existing channel selection schemes
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
ROBUST RELATIVE LOCATION ESTIMATION IN WIRELESS SENSOR NETWORKS WITH INEXACT POSITION PROBLEMS
In this paper, the relative location estimation problem, a prominent issue faced by several applications in wireless sensor networks (WSNs), is considered. Sensors are classified into two categories: location-aware and location-unaware sensors. To estimate the positions of location-unaware sensors, exact positions are often assumed for location-aware sensors. However, in practice, such precise data may not be available.
Therefore, determining the positions of location-unaware sensors in the presence of inexact positions of location-aware sensors is the primary focus of this study. A robust min-max optimization method is proposed for the relative location estimation problem by minimizing the worst-case estimation error.
The corresponding optimization problem is originally nonconvex, but after it is transformed into a convex semidefinite program (SDP), it can be solved by existing numerical techniques. In the presence of inexact positions of location-aware sensors, the robustness of the proposed approach is validated by simulations under different WSN topologies.
Modified maximum-likelihood (ML) estimation and second-order cone programming (SOCP) relaxation methods have been used for localization in comparison with the proposed approach
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
ON THE VULNERABILITIES OF CSI IN MIMO WIRELESS COMMUNICATION SYSTEMS
Multiple-input multiple-output (MIMO) technologies are apopular choice for emerging wireless systems due to their promised gains in throughput and reliability. In order to realize any gains over traditional non-MIMO communication systems, these systems must possess accurate knowledge of the wireless channel.
In this paper, we investigate strategies for disrupting MIMO communications by developing attacks that target the often over-looked, but essential, channel estimation procedure.
Our study focuses on the two most popular and well-known MIMO techniques: the capacity achieving SVD-based MIMO scheme, and the Alamouti space-time block code (STBC), which spans many protocols including 802.11n, WiMAX, and 3GPP. We augment theoretical and simulation results with real-world experimentation using the USRP/GNU Radio software de fined radio platform.
We also present novel methodology to protect the channel estimation procedure from such attacks by embedding authentication messages into physical layer features of the transmissions
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
NATURE-INSPIRED SELF-ORGANIZATION, CONTROL, AND OPTIMIZATION IN HETEROGENEOUS WIRELESS NETWORKS
In this paper, we present new models and algorithms for control and optimization of a class of next generation communication networks: Hierarchical Heterogeneous Wireless Networks (HHWNs), under real-world physical constraints. Two biology-inspired techniques, a Flocking Algorithm (FA) and a Particle Swarm Optimizer (PSO), are investigated in this context.
Our model is based on the control framework at the physical layer presented previously by the authors. We first develop a nonconvex mathematical model for HHWNs. Second, we propose a new FA for self-organization and control of the backbone nodes in an HHWN by collecting local information from end users.
Third, we employ PSO, a widely used artificial intelligence algorithm, to directly optimize the HHWN by collecting global information from the entire system. A comprehensive evaluation measurement during the optimization process is developed.
In addition, the relationship between HHWN and FA and the comparison of FA and PSO are discussed, respectively. Our novel framework is examined in various dynamic scenarios. Experimental results demonstrate that FA and PSO both outperform current algorithms for the self-organization and optimization of HHWNs while showing different characteristics with respect to convergence speed and quality of solutions
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
MODELING AND PERFORMANCE EVALUATION OF BACKOFF MISBEHAVING NODES IN CSMA/CA NETWORKS
Backoff misbehavior, in which a wireless node deliberately manipulates its backoff time, can induce significant network problems, such as severe unfairness and denial-of-service. Although great progress has been made towards the design of countermeasures to backoff misbehavior, little attention has been focused on quantifying the gain of backoff misbehaviors.
In this paper, to assess the gain that misbehaving nodes can obtain, we define and study two general classes of backoff misbehavior: continuous misbehavior, which keeps manipulating the backoff time unless it is disabled by countermeasures, and intermittent misbehavior, which tends to evade the detection of countermeasures by performing misbehavior sporadically. Our approach is to introduce a new performance metric, namely order gain, to characterize the performance benefits of misbehaving nodes in comparison to legitimate nodes in CSMA/CA-based wireless networks.
We derive the order gains of both continuous andintermittent misbehaviors and further investigate the relation between our metric, order gain, and the throughput gain for a misbehaving node. We show that in IEEE 802.11 networks, the throughput ratio of a backoff misbehaving node to a legitimate node is either bounded above or proportional to the number of legitimate nodes.
We use both simulations and experiments to validate our theoretical analysis and to further demonstrate the impact of a wide range of backoff misbehaviors on network performance in CSMA/CA-based wireless networks
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
LOW POWER CONSUMPTION SOLUTIONS FOR MOBILE INSTANT MESSAGING
Instant messaging (IM) services enable real-time text and multimedia exchange and online presence awareness. Users typically log onto instant messaging services persistently to discover available friends and also to be discovered.
However, our analysis shows that the frequency exchange of presence information incurs massive power consumption to mobile devices over cellular or wireless local area networks. Such power consumption penalty can render persistent-instant messaging infeasible for battery-powered mobile devices.
In this paper, we propose several solutions to mitigate the power consumption problem. By reducing the network access and keeping mobile devices in the sleep mode as much as possible, these solutions achieve significant power saving. The power consumption of the proposed solutions is derived analytically in this paper and the proposed solutions are implemented using a Jabber-based architecture.
Actual power measurement results show that the power consumption of the proposed solutions agrees well with our analysis, and significant power saving can be achieved on mobile handsets with our low power consumption solutions implemented.
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
GAME-THEORETIC ANALYSIS OF COOPERATION INCENTIVE STRATEGIES IN MOBILE AD HOC NETWORKS
In mobile ad hoc networks (MANETs), tasks are conducted based on the cooperation of nodes in the networks. However, since the nodes are usually constrained by limited computation resources, selfish nodes may refuse to be cooperative. Reputation systems and price-based systems are two main solutions to the node non-cooperation problem.
A reputation system evaluates node behaviors by reputation values and uses a reputation threshold to distinguish trustworthy nodes and untrustworthy nodes. A price-based system uses virtual cash to control the transactions of a packet forwarding service. Although these two kinds of systems have been widely used, very little research has been devoted to investigating the effectiveness of the node cooperation incentives provided by the systems.
In this paper, we use game theory to analyze the cooperation incentives provided by these two systems and by a system with no cooperation incentive strategy. We find that the strategies of using a threshold to determine the trustworthiness of a node in the reputation system and of rewarding cooperative nodes in the price-based system may be manipulated by clever or wealthy but selfish nodes.
Illumined by the investigation results, we propose and study an integrated system. Theoretical and simulation results show the superiority of the integrated system over an individual reputation system and a price-based system in terms of the effectiveness of cooperation incentives and selfish node detection.
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
ERROR RESILIENT ESTIMATION AND ADAPTIVE BINARY SELECTION FOR FAST AND RELIABLE IDENTIFICATION OF RFID TAGS IN ERROR-PRONE CHANNEL
In RFID systems, far field passive tags send information using back scattering. The signal level is typically very small, so channel error during transmission may occur frequently. Due to channel error, performance of RFID tag identification under error-prone channel is degraded compared to that under error-free channel.
In this paper, we propose a novel error resilient estimation and adaptive binary selection to overcome the problem of channel errors. Our proposed error resilient estimation algorithm can estimate the number of tags and the channel state accurately regardless of frame errors.
And our proposed adaptive binary selection reduces the idle slots caused by frame errors. Performance analysis and simulation results show that the proposed algorithm consumes up to 20 percent less time slots than the binary tree protocol and dynamic framed slotted ALOHA (DFSA) in various packet error rate (PER) conditions
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
LEVERAGING THE ALGEBRAIC CONNECTIVITY OF A COGNITIVE NETWORK FOR ROUTING DESIGN
In this paper, we consider the implications of spectrum heterogeneity on connectivity and routing in a Cognitive Radio Ad Hoc Network (CRAHN). We study the Laplacian spectrum of the CRAHN graph when the activity of primary users is considered. We introduce the cognitive algebraic connectivity , i.e., the second smallest eigenvalue of the Laplacian of a graph, in a cognitive scenario.
Throughout this notion we provide a methodology to evaluate the connectivity of CRAHNs and consequently introduce a utility function that is shown to be effective in capturing key characteristics of CRAHN paths. This model provides a unique metric that captures network connectivity, path length, and impact of primary users.
Moreover, the proposed metric penalizes paths where spectrum band switchings are highly probable. We design all the components of our routing framework, named Gymkhana, and we present a twofold performance verification: one from a topological perspective to show all the potentialities of the proposed routing approach, and the other considering network traffic to evaluate the performance in terms of end-to-end delay and packet delivery ratio.
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
FAST RELEASE/CAPTURE SAMPLING IN LARGE-SCALE SENSOR NETWORKS
Efficient estimation of global information is a com-mon requirement for many wireless sensor network applications. Examples include counting the number of nodes alive in the network and measuring the scale of physically correlated events.
These tasks must be accomplished at extremely low overhead due to the severe resource limitation of sensor nodes, which poses a challenge for large-scale sensor networks. In this paper, we develop a novel protocol FLAKE to efficiently and accurately estimate the global information of large-scale sensor networks based on the sparse sampling theory.
Specially, FLAKE dissem-inates a small number of messages called seeds to the network and issues a query about which nodes receive a seed. The number of nodes that have the information of interest can be estimated by counting the seeds disseminated, the nodes queried, and the nodes that receive a seed. FLAKE can be easily implemented in a distributed manner due to its simplicity.
Moreover, desirable trade-offs can be achieved between the accuracy of estimation and the system overhead. Our simulations show that FLAKE significantly outperforms several existing schemes on accuracy, delay and message overhead
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
EFFICIENT AND FAIR BANDWIDTH ALLOCATION IN MULTI-CHANNEL COGNITIVE RADIO NETWORKS
Cognitive radio improves spectrum efficiency by allowing secondary users (SUs) to dynamically exploit the idle spectrum owned by primary users (PUs).
This paper studies optimal bandwidth allocation of SUs for throughput efficiency. Consider the following tradeoff: an SU increases its instantaneous throughput by accessing more spectrum, but channel access/switching overhead, contention among multiple SUs, and dynamic PU activity create higher liability for larger bandwidths. So how much is too much? In this paper, we study the optimal bandwidth allocation for multiple SUs.
Our approach is two-fold. We first study the optimal bandwidth a SU should use to maximize the per-SU throughput in the long term. The optimal bandwidth is derived in the context of dynamic PU activity, where we consider both independent and correlated PU channel scenarios while accounting for the effects of channel switching overhead.
We further consider the case of sub-optimal spectrum use by SUs in the short term due to PU activity dynamics. We propose an efficient channel reconfiguration scheme to improve SUs’ performance. We use real PU channel activity traces in the simulations to validate our results. The work sheds light on the design of spectrum sharing protocols in cognitive radio networks
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
ENERGY-EFFICIENT COOPERATIVE VIDEO DISTRIBUTION WITH STATISTICAL QOS PROVISIONS OVER WIRELESS NETWORKS
For real-time video broadcast where multiple users are interested in the same content, mobile-to-mobile cooperation can be utilized to improve delivery efficiency and reduce network utilization. Under such cooperation, however, real-time video transmission requires end-to-end delay bounds.
Due to the inherently stochastic nature of wireless fading channels, deterministic delay bounds are prohibitively difficult to guarantee. For a scalable video structure, an alternative is to provide statistical guarantees using the concept of effective capacity/bandwidth by deriving quality of service exponents for each video layer.
Using this concept, we formulate the resource allocation problem for general multihop multicast network flows and derive the optimal solution that minimizes the total energy consumption while guaranteeing a statistical end-to-end delay bound on each network path. A method is described to compute the optimal resource allocation at each node in a distributed fashion.
Furthermore, we propose low complexity approximation algorithms for energy-efficient flow selection from the set of directed acyclic graphs forming the candidate network flows. The flow selection and resource allocation process is adapted for each video frame according to the channel conditions on the network links.
Considering different network topologies, results demonstrate that the proposed resource allocation and flow selection algorithms provide notable performance gains with small optimality gaps at a low computational cost.
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
DELAY OPTIMAL SCHEDULING FOR COGNITIVE RADIOS WITH COOPERATIVE BEAMFORMING: A STRUCTURED MATRIX-GEOMETRIC METHOD
There have been increasing interests in integrating cooperative diversity into Cognitive Radios (CRs). However, conventional cooperative diversity protocols require at least two randomly available idle timeslots or temporal spectrum holes for one transmission, thus leading to limited throughput and/or large latency.
In this paper, we propose a novel cross-layer approach for ef ficient scheduling in CR systems with bursty secondary traf fics. Specifically, cooperative beamforming is exploited for Secondary Users (SUs) to access busy timeslots or spatial spectrum holes wi thout causing interference to primary users.
We first propose a basic cooperative beaMforming and Automatic repeat request aided oppoRtunistic speCtrum scHeduling (MARCH) scheme to balance available spectrum resources, namely temporal and spatial spectrum holes, between the source and the relays.
To analyze the proposed scheme, we develop a tandem queueing framework, which captures bursty traffic arrival, dynamic availability of spectrum holes, and time-varying channel fading. The stable throughput region and the average delay are characterized using a structured matrix-analytical method.
We then obtain delay optimal scheduling schemes for various scenarios by jointly optimizing the scheduling parameters. Finally, we propose a modi fied scheme, MARCH-IR, which combines MARCH with Incremental Relay selection to further improve the system performance. Simulation results reveal that the proposed schemes provide significant Quality of Service (QoS) gains over conventional scheduling schemes that access only temporal spectrum holes
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
DETECTION OF SELFISH MANIPULATION OF CARRIER SENSING IN 802.11 NETWORKS
Recently, tuning the clear channel assessment (CCA) threshold in conjunction with power control has been considered for improving the performance of WLANs. However, we show that, CCA tuning can be exploited by selfish nodes to obtain an unfair share of the available bandwidth.
Specifically, a selfish entity can manipulate the CCA threshold to ignore ongoing transmissions; this increases the probability of accessing the medium and provides the entity a higher, unfair share of the bandwidth. We experiment on our 802.11 testbed to characterize the effects of CCA tuning on both isolated links and in 802.11 WLAN configurations.
We focus on AP-client(s) configurations, proposing a novel approach to detect this misbehavior. A misbehaving client is unlikely to recognize low power receptions as legitimate packets; by intelligently sending low power probe messages, an AP can efficiently detect a misbehaving node.
Our key contributions are: 1) We are the first to quantify the impact of selfish CCA tuning via extensive experimentation on various 802.11 configurations. 2) We propose a lightweight scheme for detecting selfish nodes that inappropriately increase their CCAs. 3) We extensively evaluate our system on our testbed; its accuracy is 95 percent while the false positive rate is less than 5 percent
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
CHARACTERIZING THE SECURITY IMPLICATIONS OF THIRD-PARTY EMERGENCY ALERT SYSTEMS OVER CELLULAR TEXT MESSAGING SERVICES
Cellular text messaging services are increasingly being relied upon to disseminate critical information during emergencies. Accordingly, a wide range of organizations including colleges and universities now partner with third-party providers that promise to improve physical security by rapidly delivering such messages.
Unfortunately, these products do not work as advertised due to limitations of cellular infrastructure and therefore provide a false sense of security to their users. In this paper, we perform the first extensive investigation and characterization of the limitations of an Emergency Alert System (EAS) using text messages as a security incident response mechanism.
We show emergency alert systems built on text messaging not only can meet the 10 minute delivery requirement mandated by the WARN Act, but also potentially cause other voice and SMS traffic to be blocked at rates upward of 80 percent. We then show that our results are representative of reality by comparing them to a number of documented but not previously understood failures.
Finally, we analyze a targeted messaging mechanism as a means of efficiently using currently deployed infrastructure and third-party EAS. In so doing, we demonstrate that this increasingly deployed security infrastructure does not achieve its stated requirements for large populations.
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
CONTROLLED MOBILITY SENSOR NETWORKS FOR TARGET TRACKING USING ANT COLONY OPTIMIZATION
In mobile sensor networks, it is important to manage the mobility of the nodes in order to improve the performances of the network. This paper addresses the problem of single target tracking in controlled mobility sensor networks.
The proposed method consists of estimating the current position of a single target. Estimated positions are t hen used to predict the following location of the target. Once an area of interest is de fined, the proposed approach consists of moving the mobile nodes in order to cover it in an optimal way. It thus de fines a strategy for choosing the set of new sensors locations.
Each node is then assigned one position within the set in the way to minimize the total traveled distance by the nodes. While the estimation and the prediction phases are performed using the interval theory, relocating nodes employs the ant colony optimization algorithm.
Simulations results corroborate the efficiency of the proposed method compared to the target tracking methods considered for networks with static nodes
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
SCALABLE LOOKAHEAD REGULAR EXPRESSION DETECTION SYSTEM FOR DEEP PACKET INSPECTION
Regular expressions (RegExes) are widely used, yet their inherent complexity often limits the total number of RegExes that can be detected using a single chip for a reasonable throughput. This limit on the number of RegExes impairs the scalability of today’s RegEx detection systems.
The scalability of existing schemes is generally limited by the traditional detection paradigm based on per-character-state processing and state transition detection. The main foc us of existing schemes is on opti-mizing the number of states and the required transitions, but not on optimizing the suboptimal character-based detection method.
Furthermore, the potential benefi ts of allowing out-of-sequence detection, instead of detecting components of a RegEx in the order of appearance, have not been explored. Lastly, theexisting schemes do not provide ways to ad apt to the evolving RegExes. In this paper, we propose Lookahead Finite Automata (LaFA) to perform scalable RegEx detection.
LaFA requires les smemory due to these three contributions:
1) providing specialized and optimized detection modules to increase resource utilization;
2) systematically reordering the RegEx detection sequence to reduce the number of concurrent operations;
3) sharing states among automata for different RegExes to reduce resource re-quirements.
Here, we demonstrate that LaFArequires an order of magnitude less memory compared to today’s state-of-the-art RegEx detection systems.
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
ACCELERATING MULTIPATTERN MATCHING ON COMPRESSED HTTP TRAFFIC
Current security tools, using “signature-based” de-tection, do not handle compressed traf fi c, whose market-share is constantly increasing.
This paper focuses on compressed HTTP traf fi c. HTTP uses GZIP compression and requires some kind of decompression phase before performing a string matching. We present a novel algorithm, Aho–C orasick-based algorithm for Compressed HTTP (ACCH), that takes advantage of information gathered by the decompression phase in order to accelerate the commonly used Aho–Corasick pattern-matching algorithm.
By analyzing real HTTP traf fi c and real Web application fi rewall signatures, we show that up to 84% of the data can be skipped in its scan. Surprisingly, we show that it is faster to perform pattern matching on the compressed data, with the penalty of decompression, than on regular traffic. As far as we know, we are the first paper that analyzes the problem of “on-the-fl y” multipattern matching on compressed HTTP traffic and suggest a solution
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
SPATIO-TEMPORAL COMPRESSIVE SENSING AND INTERNET TRAF FI C MATRICES (EXTENDED VERSION)
Despite advances in measurement technology, it is still challenging to reliably compile large-scale network datasets. For ex ample, because offlaws in the measurement systems or difficulties posed by the measurement problem itself, missing, ambiguous, or indirect data are common.
In the case where such data have spatio-temporal structure, it is natural to try to leverage this structure to deal with the challenges posed by the problem-atic nature of the data. Our work involving network datasets draws on ideas from the area of compressive sensing and matrix completion, where sparsity is exploited in estimating quantities of interest.
However, the standard results on compressive sensing are: 1) reliant on conditions that generally do not hold for network datasets; and 2) do not allow us to exploit all we know about their spatio-temporal structure.
In this paper, we overcome these limitations with an algorithm that has at its heart the same ideas espoused in compressive sensing, but adapted to the problem of network datasets.
We show how this algorithm can be used in a variety of ways, in particular on traffic data, to solve problems such as simple interpolation of missing values, traffic matrix inference from link data, prediction, and anomaly detection.
The elegance of the approach lies in the fact that it unifies all of these tasks and allows them to be performed even when as much as 98% of the data is missing
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
SPARSE WIFI DEPLOYMENT FOR VEHICULAR INTERNET ACCESS WITH BOUNDED INTERCONNECTION GAP
Vehicular Internet access via open WiFi access points (APs) has been demonstrated to be a feasible solution to provide opportunistic data service to moving vehicles. Using an in situ deployment, however, such a solution does not provide performance guarantees due to unpredictable intermittent connectivity.
On the other hand, a solution that tries to cover every point in an entire road network with Aps (a full coverage) is not very practical due to prohibitive deployment and operational costs. In this paper, we introduce a new notion of intermittent coverage for mobile users, called Alpha Coverage, which provides worst-case guarantees on the interconnection gap, i.e., the distance or expected delay between two consecutive mobile-AP contacts for a vehicle, while using significantly fewer APs than needed for full coverage.
We propose efficient algorithms to verify whether a given deployment provides Alpha Coverage. The problem of finding an economic deployment that provides coverage turns out to be NP-hard.
We hence provide both approximation algorithms that have provable guarantees on the performance as well as efficient heuristics that perform well in practice. The efficiency of our algorithms is demonstrated via simulations using data from real-world road networks
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
RELIABLE COLLECTIVE COMMUNICATIONS WITH WEIGHTED SRLGS IN OPTICAL NETWORKS
In this paper, we study the problem of reliable collective communication (broadcast or gossip) with the objective of maximizing the reliability of the collective communication. The need for collective communication arises in many problems of parallel and distributed computing, including Grid or cloud computing and database management.
We describe the network model, formulate the reliable collective communication problem, prove that the maximum reliable collective communication problem is NP-hard, and provide an integer linear program (ILP) formulation for the problem.
We then provide a greedy approximation algorithm to construct collective communication (through a spanning tree) that achieves an approximation ratio of where is the average number of shared link risk groups (SRLGs) along links, and are the total number of vertices and edges of the network, respectively.
Simulations demonstrate that our approximation algorithm achieves good performance in both small and large networks and that, in almost 95% of total cases, our algorithm outperforms the modifi ed minimum spanning tree algorithms
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
POLYNOMIAL-TIME ALGORITHMS FOR MULTIRATE ANY PATH ROUTING IN WIRELESS MULTIHOP NETWORKS
In this paper, we present a new routing paradigm that generalizes opportunistic routing for wireless multihop net-works.In multirate anypath routing, each node uses both a set of next-hops and a selected transmission rate to reach a destination. Using this rate, a packet is broadcast to the nodes in the set, and one of them forwards the packet on to the destination.
To date, there is no theory capable of jointly optimizing both the set of next-hops and the transmission rate used byeach node. We solve this by introducing two polynomial-time routing algorithms and provide the proof of their optimality.
The proposed algorithms have roughly the same running time as regular shortest-path algorithms and are therefore suitable for deployment in routing protocols. We conducted measurements in an 802.11b testbed network, and our trace-driven analysis shows that multirate anypath routing is on average 80% better than 11-Mbps anypath routing, with a factor of 6.4 improvement in the best case.
If the rate is fi xed at 1 Mbps instead, pe rformance improves by a factor of 5.4 on average
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
ON IDENTIFYING ADDITIVE LINK METRICS USING LINEARLYINDEPENDENT CYCLES AND PATHS
In this paper, we study the problem of identifying con-stant additive link metrics using linearly independent monitoring cycles and paths. A monitoring cycle starts and ends at the same monitoring station, while a monitoring path starts and ends at distinct monitoring stations.
We show that three-edge connectivity is a necessary and sufficient condition to identify link metrics using one monitoring station and employing monitoring cycles. We develop a polynomial-time algorithm to compute the set of linearly independent cycles.
For networks that are less than three-edge-connected, we show how the minimum number of monitors required and their placement may be computed. For networks with symmetric directed links, we show the relationship between the number of monitors employed, the number of directed links for which metric is known apriori, and the identi fi ability for the remaining links.
To the best of our knowledge, this is the first work that derives the necessary and sufficient conditions on the network topology for identifying additive link metrics and develops a polynomial-time algorithm to compute linearly independent cycles and paths
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
INSIGHTS ON MEDIA STREAMING PROGRESS USING BITTORRENT-LIKE PROTOCOLS FOR ON-DEMAND STREAMING
This paper develops analytical models that characterize the behavior of on-demand stored media content delivery using BitTorrent-like protocols. The models capture the effects of different piece selection policies, including Rarest-First, two vari-ants of In-Order, and two probabilistic policies (Portion and Zipf).
Our models provide insight into system behavior and help explain the sluggishness of the system with In-Order streaming. We use the models to compare different retrieval policies across a wide range of system parameters, including peer arrival rate, upload/ download bandwidth, and seed residence time.
We also provide quantitative results on the startup delays and retrieval times for streaming media delivery. Our results provide insights into the de-sign tradeoffs for on-demand media streaming in peer-to-peer net-works. Finally, the models are validated using simulations
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
GREEDY GEOGRAPHIC ROUTING IN LARGE-SCALE SENSOR NETWORKS: A MINIMUM NETWORK DECOMPOSITION APPROACH
In geographic (or geometric) routing, messages are by default routed in a greedy manner: The current node always forwards a message to its neighbor node that is closest to the destination. Despite its simplicity and general efficiency, this strategy alone does not guarantee delivery due to the existence of local minima (or dead ends).
Overcoming lo cal minima requires nodes to maintain extranonlocal state or to use auxiliary mechanisms. We study how to facilitate greedy forwarding by using a minimum amount of such nonlocal states in topologically complex networks. Specifically, we investigate the problem of decomposing a given network into a minimum number of greedily routable components (GRCs), where greedy routing is guaranteed to work.
We approach it by considering an approximate version of the problem in a continuous domain, with a central concept called the greedily routable region(GRR). A full characterization of GRR is given concerning its geometric properties and routing capability. We then develop simple approximate algorithms for the problem. These results lead to a practical routing protocol that has a routing stretch below 7 in a continuous domain, and close to 1 in several realistic network settings
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
ESM: EFFICIENT AND SCALABLE DATA CENTER MULTICAST ROUTING
Multicast benefits group communications in saving network traffic and improving application throughput, both of which are important for data center applications. However, the technical trend of data center design poses new challenges for efficient and scalable multicast routing. First, the densely connected networks make traditional receiver-driven multicast routing protocols inefficient in multicast tree formation.
Second, it is quite difficult for the low-end switches widely used in data centers to hold the routing entries of massive multicast groups. In this paper, we propose ESM, an effi cient and scalable multicast routing scheme for data center networks.
ESM addresses the challenges above by exploiting the feature of modern data center networks. Based on the regular topology of data centers, ESM uses a source-to-receiver expansion approach to build efficient multicast trees, excluding many unnecessary intermediate switches used in receiver-driven multicast routing.
For scalable multicast routing, ESM combines both in-packet Bloom Filters and in-switch entries to make the tradeoff between the number of multicast groups supported and the additional bandwidth overhead. Simulations show that ESM saves 40% 50% network traffic and doubles the application throughputs compared to receiver-driven multicast routing, and the combination routing scheme significantly reduces the number of in-switch entries required. We implement ESM on a Linux platform.
The experimental results further demonstrate that ESM can well support online tree building for large-scale groups with churns, and the overhead of the combination for-warding engine is light-weighted
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
EFFICIENT SCHEDULING FOR PERIODIC AGGREGATION QUERIES IN MULTIHOP SENSOR NETWORKS
In this paper, we study periodic query scheduling for data aggregation with minimum delay under various wireless in-terference models. Given a set o f periodic aggregation queries, each query has its own period and the subset of source nodes containing the data.
We first propose a family of efficient and effective real-time scheduling protocols that can answer every job of each query task within a relative delay under resource constraints by addressing the following tightly coupled tasks: routing, transmission plan constructions, node activity scheduling, and packet scheduling. Based on our protocol design, we further propose schedulability test schemes to efficiently and effectively test whether, for a set of queries, each query job can be finished within a finite delay.
Our theoretical analysis shows that our methods achieve at least a constant fraction of the maximum possible total utilization for query tasks, where the constant depends on wireless interference models. We also conduct extensive simulations to validate the proposed protocol and evaluate its practical performance. The simulations corroborate our theoretical analysis
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
DIFFERENTIATED QUALITY-OF-RECOVERY IN SURVIVABLE OPTICAL MESH NETWORKS USING -STRUCTURES
This paper investigates desi gn methods of protection schemes in survivable WDM networks that use preconfigured protection structures ( -structures) in order to pro vide different quality-of-recovery (QoR) classes within 100% resilient single-link protection schemes.
QoR differentiation is a practical and effective approach in order to strike different balance s among protection cost, recovery delay, and manage ment complexity.
Based on the degree of pre-cross connectivity of the protection structures, we develop three design approaches of shared protection capacity schemes based on the following: 1) fully pre-cross-connected -structures ( -structures); 2) partially pre-cross-connected -structures ( -structures); and 3) dynamically recon figured -structures ( -structures). In order to identify the optimal combinations of protection structures to meet the requirements of the three QoR classes, we use a column generation (CG) model that we solve using large-scale optimization techniques.
Our CG decomposition approach is based on the separation processes of the design and selection of the protection structures. In the design process of the protection structures, the shape and protection capability of each -structure is decided dynamically during the selection process depending on the network topology and the targeted QoR parameters.
Extensive experiments are carried out on several data instances with different design constraints in order to measure the protection capacity cost and the recovery delay for the three QoR classes
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
DESIGN OF WIRELESS SENSOR NETWORKS FOR MOBILE TARGET DETECTION
We consider surveillance applications through wire-less sensor networks (WSNs) where the areas to be monitored are fully accessible and the WSN topology can be planned apriori to maximize application efficiency.
We pro pose an optimization framework for selecting the positions of wireless sensors to detect mobile targets traversing a given area. By leveraging the concept of path exposure as a measure of detection quality, we propose two problem versions: the minimization of the sensors installation cost while guaranteeing a minimum exposure, and the maximization of the exposure of the least-exposed path subject to a budget on the sensors installation cost.
We present compact mixed-integer linear programming formulations for these problems that can be solved to optimality for reasonable-sized network instances. More-over, we develop Tabu Search heuristics that are able to provide near-optimal solutions of the same instances in short computing time and also tackle large size instances.
The basic versions are extended to account for constraints on the wireless connectivity as well as heterogeneous devices and nonuniform sensing. Finally, we analyze an enhanced exposure definition based on mobile target detection probability
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
CONGESTION-DEPENDENT PRICING AND FORWARD CONTRACTS FOR COMPLEMENTARY SEGMENTS OF A COMMUNICATION NETWORK
Congestion-dependent pricing is a form of traffic management that ensures the efficient allocation of bandwidth between users and applications. As the unpredictability of con-gestion prices creates revenue uncertainty for network providers and cost uncertainty for users, it has been suggested that forward contracts could be used to manage these risks.
We develop a novel game-theoretic model of a multiprovider communication network with two complementary segments and investigate whether for-ward contracts would be adopted by service providers.
Service on the upstream segment is provided by a single Internet service provider (ISP) and priced dynamically to maximize profit, while several smaller ISPs sell connectivity on the downstream network segment, with the advance possibility of entering into forward contracts with their users for some of their capacity.
We show that the equilibrium forward contracting volumes are necessarily asymmetric, with one downstream provider entering into fewer forward contracts than the other competitors, thus ensuring a high subsequent downstream price level.
In practice, network providers will choose the extent of forward contracting strategically based not only on their risk tolerance, but also on the market structure in the interprovider network and their peers’ actions.
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
DECLARATIVE POLICY-BASED ADAPTIVE MOBILE AD HOC NETWORKING
This paper presents DAWN, a declarative platform that creates highly adaptive policy-based mobile ad hoc network (MANET) protocols. DAWN leverages declarative networking techniques to achieve extensible routing and forwarding using declarative languages. We make the following contributions.
First, we demonstrate that traditional MANET protocols can be expressed in a concise fashion as declarative networks and policy-driven adaptation can be specified i n the same language to dictate the dynamic selection of different protocols based on various network and traffic conditions.
Second, we propose interprotocol forwarding techniques t hat ensure packets are able to seamlessly traverse across clusters of nodes running different protocols selected based on their respective policies.
Third, we have developed a full-fl edged implementation of DAWN using the RapidNet declarative networking system. We experimentally validate a variety of policy-based adaptive MANETs in various dynamic settings using a combination of ns-3 simulations and deployment on the ORBIT testbed.
Our experimental results demonstrate that hybrid protocols developed using DAWN out-perform traditional MANET routing protocols and are able to flexibly and dynamically adapt their routing mechanisms to achieve a good tradeoff between b and width utilization and route quality. We further demonstrate DAWN’s capabilities to achieve interprotocol forwarding across different protocols
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
CONCISE LOOKUP TABLES FOR IPV4 AND IPV6 LONGEST PREFIX MATCHING IN SCALABLE ROUTERS
We present a distinct longest prefi xmatching(LPM) lookup scheme able to achieve exceedingly concise lookup ta-bles (CoLT), suitable for scalable routers.
Based on unified hash tables for handling both IPv4 and IPv6 simultaneously, CoLT excels over previous mechanisms in: 1) lower on-chip storage for lookup tables; 2) simpler table formats to enjoy richer prefi x aggregation and easier implementation; and 3) most importantly, deemed the only design able to accommodate both IPv4 and IPv6 addresses uniformly and effectively.
As its hash tables permit multiple possible buckets to hold each prefix (following a migration rule to avoid false positives altogether), CoLT exhibits the best memory efficiency and can launch parallel search over tables during every LPM lookup, involving fewer cycles per lookup when on-chip memory is used to implement hash tables.
With 16 (or 32) on-chip SRAM blocks clocked at 500 MHz (achievable in today’s 65-nm technology), it takes 2 (or 1.6) cycles on average to complete a lookup, yielding 250 (or 310 ) millions of packets per second (MPPS) mean throughput. Being hash-oriented, CoLT well supports incremental table updates, besides its high table utilization and lookup throughput.
*------------*------------*------------*------------*------------*------------*
DOMAIN – NETWORKING
BALANCING RELIABILITY AND UTILIZATION IN DYNAMIC SPECTRUM ACCESS
Future wireless networks will dynamically access spectrum to maximize its utilization. Conventional design of dynamic spectrum access focuses on maximizing spectrum utilization, but faces the problem of degraded reliability due to unregulated demands and access behaviors. Without providing proper reliability guarantee, dynamic spectrum access is unacceptable to many infrastructure networks and services.
In this paper, we propose SPARTA, a new architecture for dynamic spectrum access that balances access reliability and spectrum utilization. SPARTA includes two complementary techniques: proactive ad-mission control performed by a central entity to determine the set of wireless nodes to be supported with only statistical information of their spectrum demands, and online adaptation performed by admitted wireless nodes to adjust their instantaneous spectrum usage to time-varying demand.
Using both theoretical analysis and simulation, we show that SPARTA fulfills the reliability re-quirements while dynamically multiplexing spectrum demands to improve utilization.
Compared to conventional solutions, SPARTA improves spectrum utilization by 80%–200%. Finally, SPARTA also allows service providers to explore the tradeoff between utilization and reliability to make the best use of the spectrum. To our best knowledge, our work is the first to identify and address such a tradeoff
*------------*------------*------------*------------*------------*------------*
DOMAIN – NETWORKING
ADAPTIVE SELECTIVE VERIFICATION: AN EFFICIENT ADAPTIVE COUNTERMEASURE TO THWART DOS ATTACKS
Denial-of-service (DoS) attacks are considered within the province of a shared channel model in which attack rates may be large but are bounded and client request rates vary within fixed bounds. In this setting, it is shown that clients can adapt effectively to an attack by increasing their request rate based on timeout windows to estimate attack rates.
The server will be able to process client requests with high probability while pruning out most of the attack by selective random sampling. The protocol introduced here, called Adaptive Selective Verification (ASV), is shown to use bandwidth efficiently and does not require any server state or assumptions about network congestion.
The main results of the paper are a formulation of optimal performance and a proof that ASV is optimal
*------------*------------*------------*------------*------------*------------*
DOMAIN – NETWORKING
A THEORY FOR THE CONNECTIVITY DISCOVERED BY ROUTING PROTOCOLS
Route-vector protocols, such as the Border Gateway Protocol (BGP), have nodes elect and exchange routes in order to discover paths over which to send traffic. We ask the following: What is the minimum number of links whose failure prevents a route-vector protocol from finding such paths?
The answer is not obvious because routing policies prohibit some paths from carrying traffic and because, on top of that, a route-vector protocol may hide paths the routing policies would allow. We develop an algebraic theory to address the above and related questions.
In particular, we characterize a broad class of routing policies for which we can compute in polynomial time the minimum number of links whose failure leaves a route-vector protocol without a communication path from one given node to another.
The theory is applied to a publicly available description of the Internet topology to quantify how much of its intrinsic connectivity is lost due to the traditional customer–provider, peer–peer r outing policies and how much can be regained with simple alternative policies
*------------*------------*------------*------------*------------*------------*
APPROXIMATION ALGORITHMS FOR DATA BROADCAST IN WIRELESS NETWORKS
Broadcasting is a fundamental operation in wireless networks and plays an important role in the communication protocol design. In multihop wireless networks, however, interference at a node due to simultaneous transmissions from its neighbors makes it nontrivial to design a minimum-latency broadcast algorithm, which is known to be NP-complete.
We present a simple 12-approximation algorithm for the one-to-all broadcast problem that improves all previously known guarantees for this problem. We then consider the all-to-all broadcast problem where each node sends its own message to all other nodes. For the all-to-all broadcast problem, we present two algorithms with approximation ratios of 20 and 34, improving the best result available in the literature.
Finally, we report experimental evaluation of our algorithms. Our studies indicate that our algorithms perform much better in practice than the worst-case guarantees provided in the theoretical analysis and achieve up to 37 percent performance improvement over existing schemes
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
CHANNEL ESTIMATION FOR OPPORTUNISTIC SPECTRUM ACCESS: UNIFORM AND RANDOM SENSING
The knowledge of channel statistics can be very helpful in making sound opportunistic spectrum access decisions. It is therefore desirable to be able to ef ficiently and accurately estimate channel statistics. In this paper we study the problem of optimally placing sensing/sampling times over a time window so as to get the best estimate on the parameters of an on-off renewal channel. We are particularly interested in a sparse sensing regime with a small number of samples relative to the time window size.
Using Fisher information as a measur e, we analytically derive the best and worst sensing sequences under a sparsity condition. We also present a way to derive the bes t/worst sequences without this condition using a dynamic programming approach. In both cases the worst turns out to be the uniform sensing sequence, where sensing times are evenly spaced within the window. Interestingly the best sequence is also uniform but with a much smaller sensing interval that requires a priori knowledge of the channel parameters.
With these results we argue that without a priori knowledge, a robust sensing strategy should be a randomized strategy. We then compare different random schemes using a family of distributions generated by the circular β ensemble, and propose an adaptive sensing scheme to effectively track time-varying channel parameters. We further discuss the applicability of compressive sensing for this problem
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
AN MIMO CONFIGURATION MODE AND MCS LEVEL SELECTION SCHEME BY FUZZY Q-LEARNING FOR HSPA ÞSYSTEMS
In this paper, we propose afuzzy Q-learning-based MIM O configuration mode and MCS level (FQL-MOMS) selection scheme for high speed packet access evolution (HSPA þ) systems. The FQL-MOMS selection scheme intends to enhance the system throughput under the block error rate (BLER) requirement guarantee.
It will determine an appropriate MIMO configuration mode and MCS (modulation and coding scheme) level for packet data transmission in HSPA þ systems, under the situations that the channel status is varying and the channel quality indication (CQI) has report delay.
The FQL-MOMS scheme considers not only the reported CQI and the last transmission result but also the BLER performance metric and the transmission efficiency. Moreover, it is effectively configured, where the fuzzy rules and the reinforcement signals for the Q-learning algorithm are sophisticatedly designed.
Simulation results show that the proposed FQL-MOMS scheme increases the system throughput by up to 49.3 and 35.9 percent, compared to the conventional adaptive threshold selection (ATS) scheme [12] and the Q-HARQ scheme [14], respectively, under the BLER requirement fulfillment
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
A NOVEL MAC SCHEME FOR MULTICHANNEL COGNITIVE RADIO AD HOC NETWORKS
This paper proposes a novel medium access control (MAC) scheme for multichannel cognitive radio (CR) ad hoc networks, which achieves high throughput of CR system while protecting primary users (PUs) effectively.
In designing the MAC scheme, we consider that the PU signal may cover only a part of the network and the nodes can have the different sensing result for the same PU even on the same channel. By allowing the nodes to use the channel on which the PU exists as long as their transmissions do not disturb the PU, the proposed MAC scheme fully utilizes the spectrum access opportunity.
To mitigate the hidden PU problem inherent to multichannel CR networks where the PU signal is detectable only to some nodes, the proposed MAC scheme adjusts the sensing priorities of channels at each node with the PU detection information of other nodes and also limits the transmission power of a CR node to the maximum allowable power for guaranteeing the quality of service requirement of PU.
The performance of the proposed MAC scheme is evaluated by using simulation. The simulation results show that the CR system with the proposed MAC accomplishes good performance in throughput and packet delay, while protecting PUs properly.
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
A COST ANALYSIS FRAMEWORK FOR NEMO PREFIX DELEGATION-BASED SCHEMES
Network Mobility (NEMO) efficiently manages the mobility of multiple nodes that moves together as a mobile network. A major limitation of the basic protocol in NEMO is the inefficient route between end hosts. A number of prefix delegation-based schemes have been proposed in the literature to solve the route optimization problem in NEMO.
Approaches used by the schemes trade off delivery of packets through the partially optimized route with signaling and other processing overheads. Cost of delivering packets through the partially optimized route along with signaling and processing cost need to be measured to find out the gain from tradeoff. However, cost analysis performed so far on NEMO protocols consider only the cost of signaling.
In this paper, we have developed analytical framework to measure the costs of the basic protocol for NEMO, and four representative prefix delegation-based schemes. Our results show that cost of packet delivery through the partially optimized route dominates over other costs.
Therefore, optimizing the route completely is preferable to reduction of signaling as far as cost of network mobility is concerned. Our cost analysis framework will help in decision making to select the best route optimization scheme depending on the load imposed by the scheme on the infrastructure.
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
USING ROTATABLE AND DIRECTIONAL (R&D) SENSORS TO ACHIEVE TEMPORAL COVERAGE OF OBJECTS AND ITS SURVEILLANCE APPLICATION
Due to hardware design or cost consideration, sen-sors may possess sector-like sensing coverage. Furthermore, by stepper motors, sensors can rotate to cover the objects around them. This type of sensors are called rotatable and directional (R&D) sensors. Through rotation, R&D sensors provide temporal coverage to objects by “periodically” detecting their existence.
In the paper, we first develop an event-driven surveillance system by R&D sensors, where objects are monitored by the sensors equipped with infrared detectors and cameras. When an object is taken away, the sensor monitoring the object reports a warning message along with detailed snapshots from the surroundings.
Then, motivated by the system, we formulate an R&D sensor deployment problem, which tries to deploy the minimum number of R&D sensors to cover a given set of objects such that each object is covered by 0 <δ ≤ 1 ratio of time in every frame. We show this problem to be NP-hard and propose two efficient heuristics.
The maximum covering deployment (MCD) heuristic iteratively deploys a sensor to cover more objects, and performs well when objects congregate together. The disk-overlapping deployment (DOD)heuristic deploys sensors to cover the joint sectors of overlapped disks, so it works better when objects are arbitrarily placed in the sensing field.
The paper contributes in defining a new temporal coverage model by R&D sensors, developing a surveillance application for this model, and proposing efficient heuristics to reduce the deployment cost
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
UNDERSTANDING NODE LOCALIZABILITY OF WIRE-LESS AD-HOC AND SENSOR NETWORKS
Location awareness is highly critical for wireless ad-hoc and sensor networks. Many efforts have been made to solve the problem of whether or not a network can be local-ized. Nevertheless, based on the data collected from a working sensor network, it is observed that the network is not always entirely localizable.
Theoretical analyses also suggest that, in most cases, it is unlikely that all nodes in a network are localizable, although a (large) portion of the nodes can be uniquely located. Existing studies merely ex-amine whether or not a network is localizable as a whole; yet two fundamental questions remain unaddressed: First, given a network configuration, whether or not a specific node is localizable? Second, how many nodes in a network can be located and which are them? In this study, we analyze the limitation of previous works an d propose a novel concept of node localizability.
By deriving the necessary and sufficient conditions for node localizability, for the first time, it is possible to analyze how many n odes one can expect to locate in sparsely or moderately connected networks.
To validate this design, we implement our solution on a real-world sys-tem and the experimental results show that node localizability provides useful guidelines for network deployment and other location-based services
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
STORM: A FRAMEWORK FOR INTEGRATED ROUTING, SCHEDULING AND TRAFFIC MANAGEMENT IN AD HOC NETWORKS
A cross-layer framework is introduced for the effective dissemination of real-time and elastic traffic in multi-hop wireless networks called STORM (Scheduling and Traffic Management in Ordered Routing Meshes).
Unicast and multicast routes are estab-lished in coordination with the scheduling of transmissions and band-width reservations in a way that bandwidth and delay guarantees can be enforced on a per-hop and end-to-end basis. The routes established in STORM are shown to be loop-free and real-time packets forwarded along these routes are shown to have bounded end-to-end delays.
Results from detailed simulation experiments show that, compared to a protocol stack consisting of 802.11 DCF for channel access, AODV or OLSR for unicast routing, and ODMRP for multicast routing, STORM attains similar or better performance for elastic traffic, and up to two orders of magnitude improvement in end-to-end delays, with twice the amount of data delivery for real-time traffic while inducing considerably less communication overhead.
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
THE BOOMERANG PROTOCOL: TYING DATA TO GEOGRAPHIC LOCATIONS IN MOBILE DISCONNECTED NETWORKS
We present the boomerang protocol to efficiently retain information at a particular geographic location in a sparse network of highly mobile nodes without using infrastructure networks. To retain information around certain physical location, each mobile device passing that location will carry the information for a short while.
This approach can become challenging for remote locations around which only few nodes pass by. To address this challenge, the boomerang protocol, similar to delay-tolerant communication, first allows a mobile node to carry packets away from their location of origin and periodically returns them to the anchor location.
A unique feature of this protocol is that it records the geographical trajectory while moving away from the origin and exploits the recorded trajectory to optimize the return path. Simulations using automotive traffic traces for a southern New Jersey region show that the boomerang protocol improves packet return rate by 70 percent compared to a baseline shortest path routing protocol.
This performance gain can become even more significant when the road map is less connected. Finally, we look at adaptive protocols that can return information within specified time limits
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
PROSPECT: A PROACTIVE SPECTRUM HANDOFF FRAMEWORK FOR COGNITIVE RADIO AD HOC NETWORKS WITHOUT COMMON CONTROL CHANNEL
Cognitive Radio (CR) technology is a promising solution to enhance the spectrum utilization by enabling unlicensed users to exploit the spectrum in an opportunistic manner. Since unlicensed users are temporary visitors to the licensed spectrum, they are required to vacate the spectrum when a licensed user reclaims it.
Due to the randomness of the appearance of licensed users, disruptions to both licensed and unlicensed communications are often difficult to prevent, which may lead to low throughput of both licensed and unlicensed communications. In this paper, a proactive spectrum handoff framework for CR ad hoc networks, ProSpect, is proposed to address these concerns.
In the proposed framework, Channel-Switching (CW) policies and a proactive spectrum handoff protocol are proposed to let unlicensed users vacate a channelbefore a licensed user utilizes it to avoid unwanted interference. Network coordination schemes for unlicensed users are also incorporated into the spectrum handoff protocol design.
Moreover, a distributed channel selection scheme to eliminate collisions among unlicensed users in a multiuser spectrum handoff scenario is proposed. In our proposed framework, unlicensed users coordinate with each other without using a Common Control Channel (CCC), which is highly adaptable in a spectrum-varying environment.
We compare our proposed proactive spectrum handoff protocol with a reactive spectrum handoff protocol, under which unlicensed users switch channels after collisions with licensed transmissions occur. Simulation results show that our proactive spectrum handoff outperforms the reactive spectrum handoff approach in terms of higher throughput and fewer collisions to licensed users.
Furthermore, our distributed channel selection can achieve higher packet delivery rate in a multiuser spectrum handoff scenario, compared with existing channel selection schemes
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
ROBUST RELATIVE LOCATION ESTIMATION IN WIRELESS SENSOR NETWORKS WITH INEXACT POSITION PROBLEMS
In this paper, the relative location estimation problem, a prominent issue faced by several applications in wireless sensor networks (WSNs), is considered. Sensors are classified into two categories: location-aware and location-unaware sensors. To estimate the positions of location-unaware sensors, exact positions are often assumed for location-aware sensors. However, in practice, such precise data may not be available.
Therefore, determining the positions of location-unaware sensors in the presence of inexact positions of location-aware sensors is the primary focus of this study. A robust min-max optimization method is proposed for the relative location estimation problem by minimizing the worst-case estimation error.
The corresponding optimization problem is originally nonconvex, but after it is transformed into a convex semidefinite program (SDP), it can be solved by existing numerical techniques. In the presence of inexact positions of location-aware sensors, the robustness of the proposed approach is validated by simulations under different WSN topologies.
Modified maximum-likelihood (ML) estimation and second-order cone programming (SOCP) relaxation methods have been used for localization in comparison with the proposed approach
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
ON THE VULNERABILITIES OF CSI IN MIMO WIRELESS COMMUNICATION SYSTEMS
Multiple-input multiple-output (MIMO) technologies are apopular choice for emerging wireless systems due to their promised gains in throughput and reliability. In order to realize any gains over traditional non-MIMO communication systems, these systems must possess accurate knowledge of the wireless channel.
In this paper, we investigate strategies for disrupting MIMO communications by developing attacks that target the often over-looked, but essential, channel estimation procedure.
Our study focuses on the two most popular and well-known MIMO techniques: the capacity achieving SVD-based MIMO scheme, and the Alamouti space-time block code (STBC), which spans many protocols including 802.11n, WiMAX, and 3GPP. We augment theoretical and simulation results with real-world experimentation using the USRP/GNU Radio software de fined radio platform.
We also present novel methodology to protect the channel estimation procedure from such attacks by embedding authentication messages into physical layer features of the transmissions
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
NATURE-INSPIRED SELF-ORGANIZATION, CONTROL, AND OPTIMIZATION IN HETEROGENEOUS WIRELESS NETWORKS
In this paper, we present new models and algorithms for control and optimization of a class of next generation communication networks: Hierarchical Heterogeneous Wireless Networks (HHWNs), under real-world physical constraints. Two biology-inspired techniques, a Flocking Algorithm (FA) and a Particle Swarm Optimizer (PSO), are investigated in this context.
Our model is based on the control framework at the physical layer presented previously by the authors. We first develop a nonconvex mathematical model for HHWNs. Second, we propose a new FA for self-organization and control of the backbone nodes in an HHWN by collecting local information from end users.
Third, we employ PSO, a widely used artificial intelligence algorithm, to directly optimize the HHWN by collecting global information from the entire system. A comprehensive evaluation measurement during the optimization process is developed.
In addition, the relationship between HHWN and FA and the comparison of FA and PSO are discussed, respectively. Our novel framework is examined in various dynamic scenarios. Experimental results demonstrate that FA and PSO both outperform current algorithms for the self-organization and optimization of HHWNs while showing different characteristics with respect to convergence speed and quality of solutions
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
MODELING AND PERFORMANCE EVALUATION OF BACKOFF MISBEHAVING NODES IN CSMA/CA NETWORKS
Backoff misbehavior, in which a wireless node deliberately manipulates its backoff time, can induce significant network problems, such as severe unfairness and denial-of-service. Although great progress has been made towards the design of countermeasures to backoff misbehavior, little attention has been focused on quantifying the gain of backoff misbehaviors.
In this paper, to assess the gain that misbehaving nodes can obtain, we define and study two general classes of backoff misbehavior: continuous misbehavior, which keeps manipulating the backoff time unless it is disabled by countermeasures, and intermittent misbehavior, which tends to evade the detection of countermeasures by performing misbehavior sporadically. Our approach is to introduce a new performance metric, namely order gain, to characterize the performance benefits of misbehaving nodes in comparison to legitimate nodes in CSMA/CA-based wireless networks.
We derive the order gains of both continuous andintermittent misbehaviors and further investigate the relation between our metric, order gain, and the throughput gain for a misbehaving node. We show that in IEEE 802.11 networks, the throughput ratio of a backoff misbehaving node to a legitimate node is either bounded above or proportional to the number of legitimate nodes.
We use both simulations and experiments to validate our theoretical analysis and to further demonstrate the impact of a wide range of backoff misbehaviors on network performance in CSMA/CA-based wireless networks
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
LOW POWER CONSUMPTION SOLUTIONS FOR MOBILE INSTANT MESSAGING
Instant messaging (IM) services enable real-time text and multimedia exchange and online presence awareness. Users typically log onto instant messaging services persistently to discover available friends and also to be discovered.
However, our analysis shows that the frequency exchange of presence information incurs massive power consumption to mobile devices over cellular or wireless local area networks. Such power consumption penalty can render persistent-instant messaging infeasible for battery-powered mobile devices.
In this paper, we propose several solutions to mitigate the power consumption problem. By reducing the network access and keeping mobile devices in the sleep mode as much as possible, these solutions achieve significant power saving. The power consumption of the proposed solutions is derived analytically in this paper and the proposed solutions are implemented using a Jabber-based architecture.
Actual power measurement results show that the power consumption of the proposed solutions agrees well with our analysis, and significant power saving can be achieved on mobile handsets with our low power consumption solutions implemented.
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
GAME-THEORETIC ANALYSIS OF COOPERATION INCENTIVE STRATEGIES IN MOBILE AD HOC NETWORKS
In mobile ad hoc networks (MANETs), tasks are conducted based on the cooperation of nodes in the networks. However, since the nodes are usually constrained by limited computation resources, selfish nodes may refuse to be cooperative. Reputation systems and price-based systems are two main solutions to the node non-cooperation problem.
A reputation system evaluates node behaviors by reputation values and uses a reputation threshold to distinguish trustworthy nodes and untrustworthy nodes. A price-based system uses virtual cash to control the transactions of a packet forwarding service. Although these two kinds of systems have been widely used, very little research has been devoted to investigating the effectiveness of the node cooperation incentives provided by the systems.
In this paper, we use game theory to analyze the cooperation incentives provided by these two systems and by a system with no cooperation incentive strategy. We find that the strategies of using a threshold to determine the trustworthiness of a node in the reputation system and of rewarding cooperative nodes in the price-based system may be manipulated by clever or wealthy but selfish nodes.
Illumined by the investigation results, we propose and study an integrated system. Theoretical and simulation results show the superiority of the integrated system over an individual reputation system and a price-based system in terms of the effectiveness of cooperation incentives and selfish node detection.
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
ERROR RESILIENT ESTIMATION AND ADAPTIVE BINARY SELECTION FOR FAST AND RELIABLE IDENTIFICATION OF RFID TAGS IN ERROR-PRONE CHANNEL
In RFID systems, far field passive tags send information using back scattering. The signal level is typically very small, so channel error during transmission may occur frequently. Due to channel error, performance of RFID tag identification under error-prone channel is degraded compared to that under error-free channel.
In this paper, we propose a novel error resilient estimation and adaptive binary selection to overcome the problem of channel errors. Our proposed error resilient estimation algorithm can estimate the number of tags and the channel state accurately regardless of frame errors.
And our proposed adaptive binary selection reduces the idle slots caused by frame errors. Performance analysis and simulation results show that the proposed algorithm consumes up to 20 percent less time slots than the binary tree protocol and dynamic framed slotted ALOHA (DFSA) in various packet error rate (PER) conditions
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
LEVERAGING THE ALGEBRAIC CONNECTIVITY OF A COGNITIVE NETWORK FOR ROUTING DESIGN
In this paper, we consider the implications of spectrum heterogeneity on connectivity and routing in a Cognitive Radio Ad Hoc Network (CRAHN). We study the Laplacian spectrum of the CRAHN graph when the activity of primary users is considered. We introduce the cognitive algebraic connectivity , i.e., the second smallest eigenvalue of the Laplacian of a graph, in a cognitive scenario.
Throughout this notion we provide a methodology to evaluate the connectivity of CRAHNs and consequently introduce a utility function that is shown to be effective in capturing key characteristics of CRAHN paths. This model provides a unique metric that captures network connectivity, path length, and impact of primary users.
Moreover, the proposed metric penalizes paths where spectrum band switchings are highly probable. We design all the components of our routing framework, named Gymkhana, and we present a twofold performance verification: one from a topological perspective to show all the potentialities of the proposed routing approach, and the other considering network traffic to evaluate the performance in terms of end-to-end delay and packet delivery ratio.
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
FAST RELEASE/CAPTURE SAMPLING IN LARGE-SCALE SENSOR NETWORKS
Efficient estimation of global information is a com-mon requirement for many wireless sensor network applications. Examples include counting the number of nodes alive in the network and measuring the scale of physically correlated events.
These tasks must be accomplished at extremely low overhead due to the severe resource limitation of sensor nodes, which poses a challenge for large-scale sensor networks. In this paper, we develop a novel protocol FLAKE to efficiently and accurately estimate the global information of large-scale sensor networks based on the sparse sampling theory.
Specially, FLAKE dissem-inates a small number of messages called seeds to the network and issues a query about which nodes receive a seed. The number of nodes that have the information of interest can be estimated by counting the seeds disseminated, the nodes queried, and the nodes that receive a seed. FLAKE can be easily implemented in a distributed manner due to its simplicity.
Moreover, desirable trade-offs can be achieved between the accuracy of estimation and the system overhead. Our simulations show that FLAKE significantly outperforms several existing schemes on accuracy, delay and message overhead
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
EFFICIENT AND FAIR BANDWIDTH ALLOCATION IN MULTI-CHANNEL COGNITIVE RADIO NETWORKS
Cognitive radio improves spectrum efficiency by allowing secondary users (SUs) to dynamically exploit the idle spectrum owned by primary users (PUs).
This paper studies optimal bandwidth allocation of SUs for throughput efficiency. Consider the following tradeoff: an SU increases its instantaneous throughput by accessing more spectrum, but channel access/switching overhead, contention among multiple SUs, and dynamic PU activity create higher liability for larger bandwidths. So how much is too much? In this paper, we study the optimal bandwidth allocation for multiple SUs.
Our approach is two-fold. We first study the optimal bandwidth a SU should use to maximize the per-SU throughput in the long term. The optimal bandwidth is derived in the context of dynamic PU activity, where we consider both independent and correlated PU channel scenarios while accounting for the effects of channel switching overhead.
We further consider the case of sub-optimal spectrum use by SUs in the short term due to PU activity dynamics. We propose an efficient channel reconfiguration scheme to improve SUs’ performance. We use real PU channel activity traces in the simulations to validate our results. The work sheds light on the design of spectrum sharing protocols in cognitive radio networks
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
ENERGY-EFFICIENT COOPERATIVE VIDEO DISTRIBUTION WITH STATISTICAL QOS PROVISIONS OVER WIRELESS NETWORKS
For real-time video broadcast where multiple users are interested in the same content, mobile-to-mobile cooperation can be utilized to improve delivery efficiency and reduce network utilization. Under such cooperation, however, real-time video transmission requires end-to-end delay bounds.
Due to the inherently stochastic nature of wireless fading channels, deterministic delay bounds are prohibitively difficult to guarantee. For a scalable video structure, an alternative is to provide statistical guarantees using the concept of effective capacity/bandwidth by deriving quality of service exponents for each video layer.
Using this concept, we formulate the resource allocation problem for general multihop multicast network flows and derive the optimal solution that minimizes the total energy consumption while guaranteeing a statistical end-to-end delay bound on each network path. A method is described to compute the optimal resource allocation at each node in a distributed fashion.
Furthermore, we propose low complexity approximation algorithms for energy-efficient flow selection from the set of directed acyclic graphs forming the candidate network flows. The flow selection and resource allocation process is adapted for each video frame according to the channel conditions on the network links.
Considering different network topologies, results demonstrate that the proposed resource allocation and flow selection algorithms provide notable performance gains with small optimality gaps at a low computational cost.
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
DELAY OPTIMAL SCHEDULING FOR COGNITIVE RADIOS WITH COOPERATIVE BEAMFORMING: A STRUCTURED MATRIX-GEOMETRIC METHOD
There have been increasing interests in integrating cooperative diversity into Cognitive Radios (CRs). However, conventional cooperative diversity protocols require at least two randomly available idle timeslots or temporal spectrum holes for one transmission, thus leading to limited throughput and/or large latency.
In this paper, we propose a novel cross-layer approach for ef ficient scheduling in CR systems with bursty secondary traf fics. Specifically, cooperative beamforming is exploited for Secondary Users (SUs) to access busy timeslots or spatial spectrum holes wi thout causing interference to primary users.
We first propose a basic cooperative beaMforming and Automatic repeat request aided oppoRtunistic speCtrum scHeduling (MARCH) scheme to balance available spectrum resources, namely temporal and spatial spectrum holes, between the source and the relays.
To analyze the proposed scheme, we develop a tandem queueing framework, which captures bursty traffic arrival, dynamic availability of spectrum holes, and time-varying channel fading. The stable throughput region and the average delay are characterized using a structured matrix-analytical method.
We then obtain delay optimal scheduling schemes for various scenarios by jointly optimizing the scheduling parameters. Finally, we propose a modi fied scheme, MARCH-IR, which combines MARCH with Incremental Relay selection to further improve the system performance. Simulation results reveal that the proposed schemes provide significant Quality of Service (QoS) gains over conventional scheduling schemes that access only temporal spectrum holes
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
DETECTION OF SELFISH MANIPULATION OF CARRIER SENSING IN 802.11 NETWORKS
Recently, tuning the clear channel assessment (CCA) threshold in conjunction with power control has been considered for improving the performance of WLANs. However, we show that, CCA tuning can be exploited by selfish nodes to obtain an unfair share of the available bandwidth.
Specifically, a selfish entity can manipulate the CCA threshold to ignore ongoing transmissions; this increases the probability of accessing the medium and provides the entity a higher, unfair share of the bandwidth. We experiment on our 802.11 testbed to characterize the effects of CCA tuning on both isolated links and in 802.11 WLAN configurations.
We focus on AP-client(s) configurations, proposing a novel approach to detect this misbehavior. A misbehaving client is unlikely to recognize low power receptions as legitimate packets; by intelligently sending low power probe messages, an AP can efficiently detect a misbehaving node.
Our key contributions are: 1) We are the first to quantify the impact of selfish CCA tuning via extensive experimentation on various 802.11 configurations. 2) We propose a lightweight scheme for detecting selfish nodes that inappropriately increase their CCAs. 3) We extensively evaluate our system on our testbed; its accuracy is 95 percent while the false positive rate is less than 5 percent
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
CHARACTERIZING THE SECURITY IMPLICATIONS OF THIRD-PARTY EMERGENCY ALERT SYSTEMS OVER CELLULAR TEXT MESSAGING SERVICES
Cellular text messaging services are increasingly being relied upon to disseminate critical information during emergencies. Accordingly, a wide range of organizations including colleges and universities now partner with third-party providers that promise to improve physical security by rapidly delivering such messages.
Unfortunately, these products do not work as advertised due to limitations of cellular infrastructure and therefore provide a false sense of security to their users. In this paper, we perform the first extensive investigation and characterization of the limitations of an Emergency Alert System (EAS) using text messages as a security incident response mechanism.
We show emergency alert systems built on text messaging not only can meet the 10 minute delivery requirement mandated by the WARN Act, but also potentially cause other voice and SMS traffic to be blocked at rates upward of 80 percent. We then show that our results are representative of reality by comparing them to a number of documented but not previously understood failures.
Finally, we analyze a targeted messaging mechanism as a means of efficiently using currently deployed infrastructure and third-party EAS. In so doing, we demonstrate that this increasingly deployed security infrastructure does not achieve its stated requirements for large populations.
*------------*------------*------------*------------*------------*------------*
DOMAIN - MOBILE COMPUTING
CONTROLLED MOBILITY SENSOR NETWORKS FOR TARGET TRACKING USING ANT COLONY OPTIMIZATION
In mobile sensor networks, it is important to manage the mobility of the nodes in order to improve the performances of the network. This paper addresses the problem of single target tracking in controlled mobility sensor networks.
The proposed method consists of estimating the current position of a single target. Estimated positions are t hen used to predict the following location of the target. Once an area of interest is de fined, the proposed approach consists of moving the mobile nodes in order to cover it in an optimal way. It thus de fines a strategy for choosing the set of new sensors locations.
Each node is then assigned one position within the set in the way to minimize the total traveled distance by the nodes. While the estimation and the prediction phases are performed using the interval theory, relocating nodes employs the ant colony optimization algorithm.
Simulations results corroborate the efficiency of the proposed method compared to the target tracking methods considered for networks with static nodes
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
SCALABLE LOOKAHEAD REGULAR EXPRESSION DETECTION SYSTEM FOR DEEP PACKET INSPECTION
Regular expressions (RegExes) are widely used, yet their inherent complexity often limits the total number of RegExes that can be detected using a single chip for a reasonable throughput. This limit on the number of RegExes impairs the scalability of today’s RegEx detection systems.
The scalability of existing schemes is generally limited by the traditional detection paradigm based on per-character-state processing and state transition detection. The main foc us of existing schemes is on opti-mizing the number of states and the required transitions, but not on optimizing the suboptimal character-based detection method.
Furthermore, the potential benefi ts of allowing out-of-sequence detection, instead of detecting components of a RegEx in the order of appearance, have not been explored. Lastly, theexisting schemes do not provide ways to ad apt to the evolving RegExes. In this paper, we propose Lookahead Finite Automata (LaFA) to perform scalable RegEx detection.
LaFA requires les smemory due to these three contributions:
1) providing specialized and optimized detection modules to increase resource utilization;
2) systematically reordering the RegEx detection sequence to reduce the number of concurrent operations;
3) sharing states among automata for different RegExes to reduce resource re-quirements.
Here, we demonstrate that LaFArequires an order of magnitude less memory compared to today’s state-of-the-art RegEx detection systems.
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
ACCELERATING MULTIPATTERN MATCHING ON COMPRESSED HTTP TRAFFIC
Current security tools, using “signature-based” de-tection, do not handle compressed traf fi c, whose market-share is constantly increasing.
This paper focuses on compressed HTTP traf fi c. HTTP uses GZIP compression and requires some kind of decompression phase before performing a string matching. We present a novel algorithm, Aho–C orasick-based algorithm for Compressed HTTP (ACCH), that takes advantage of information gathered by the decompression phase in order to accelerate the commonly used Aho–Corasick pattern-matching algorithm.
By analyzing real HTTP traf fi c and real Web application fi rewall signatures, we show that up to 84% of the data can be skipped in its scan. Surprisingly, we show that it is faster to perform pattern matching on the compressed data, with the penalty of decompression, than on regular traffic. As far as we know, we are the first paper that analyzes the problem of “on-the-fl y” multipattern matching on compressed HTTP traffic and suggest a solution
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
SPATIO-TEMPORAL COMPRESSIVE SENSING AND INTERNET TRAF FI C MATRICES (EXTENDED VERSION)
Despite advances in measurement technology, it is still challenging to reliably compile large-scale network datasets. For ex ample, because offlaws in the measurement systems or difficulties posed by the measurement problem itself, missing, ambiguous, or indirect data are common.
In the case where such data have spatio-temporal structure, it is natural to try to leverage this structure to deal with the challenges posed by the problem-atic nature of the data. Our work involving network datasets draws on ideas from the area of compressive sensing and matrix completion, where sparsity is exploited in estimating quantities of interest.
However, the standard results on compressive sensing are: 1) reliant on conditions that generally do not hold for network datasets; and 2) do not allow us to exploit all we know about their spatio-temporal structure.
In this paper, we overcome these limitations with an algorithm that has at its heart the same ideas espoused in compressive sensing, but adapted to the problem of network datasets.
We show how this algorithm can be used in a variety of ways, in particular on traffic data, to solve problems such as simple interpolation of missing values, traffic matrix inference from link data, prediction, and anomaly detection.
The elegance of the approach lies in the fact that it unifies all of these tasks and allows them to be performed even when as much as 98% of the data is missing
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
SPARSE WIFI DEPLOYMENT FOR VEHICULAR INTERNET ACCESS WITH BOUNDED INTERCONNECTION GAP
Vehicular Internet access via open WiFi access points (APs) has been demonstrated to be a feasible solution to provide opportunistic data service to moving vehicles. Using an in situ deployment, however, such a solution does not provide performance guarantees due to unpredictable intermittent connectivity.
On the other hand, a solution that tries to cover every point in an entire road network with Aps (a full coverage) is not very practical due to prohibitive deployment and operational costs. In this paper, we introduce a new notion of intermittent coverage for mobile users, called Alpha Coverage, which provides worst-case guarantees on the interconnection gap, i.e., the distance or expected delay between two consecutive mobile-AP contacts for a vehicle, while using significantly fewer APs than needed for full coverage.
We propose efficient algorithms to verify whether a given deployment provides Alpha Coverage. The problem of finding an economic deployment that provides coverage turns out to be NP-hard.
We hence provide both approximation algorithms that have provable guarantees on the performance as well as efficient heuristics that perform well in practice. The efficiency of our algorithms is demonstrated via simulations using data from real-world road networks
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
RELIABLE COLLECTIVE COMMUNICATIONS WITH WEIGHTED SRLGS IN OPTICAL NETWORKS
In this paper, we study the problem of reliable collective communication (broadcast or gossip) with the objective of maximizing the reliability of the collective communication. The need for collective communication arises in many problems of parallel and distributed computing, including Grid or cloud computing and database management.
We describe the network model, formulate the reliable collective communication problem, prove that the maximum reliable collective communication problem is NP-hard, and provide an integer linear program (ILP) formulation for the problem.
We then provide a greedy approximation algorithm to construct collective communication (through a spanning tree) that achieves an approximation ratio of where is the average number of shared link risk groups (SRLGs) along links, and are the total number of vertices and edges of the network, respectively.
Simulations demonstrate that our approximation algorithm achieves good performance in both small and large networks and that, in almost 95% of total cases, our algorithm outperforms the modifi ed minimum spanning tree algorithms
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
POLYNOMIAL-TIME ALGORITHMS FOR MULTIRATE ANY PATH ROUTING IN WIRELESS MULTIHOP NETWORKS
In this paper, we present a new routing paradigm that generalizes opportunistic routing for wireless multihop net-works.In multirate anypath routing, each node uses both a set of next-hops and a selected transmission rate to reach a destination. Using this rate, a packet is broadcast to the nodes in the set, and one of them forwards the packet on to the destination.
To date, there is no theory capable of jointly optimizing both the set of next-hops and the transmission rate used byeach node. We solve this by introducing two polynomial-time routing algorithms and provide the proof of their optimality.
The proposed algorithms have roughly the same running time as regular shortest-path algorithms and are therefore suitable for deployment in routing protocols. We conducted measurements in an 802.11b testbed network, and our trace-driven analysis shows that multirate anypath routing is on average 80% better than 11-Mbps anypath routing, with a factor of 6.4 improvement in the best case.
If the rate is fi xed at 1 Mbps instead, pe rformance improves by a factor of 5.4 on average
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
ON IDENTIFYING ADDITIVE LINK METRICS USING LINEARLYINDEPENDENT CYCLES AND PATHS
In this paper, we study the problem of identifying con-stant additive link metrics using linearly independent monitoring cycles and paths. A monitoring cycle starts and ends at the same monitoring station, while a monitoring path starts and ends at distinct monitoring stations.
We show that three-edge connectivity is a necessary and sufficient condition to identify link metrics using one monitoring station and employing monitoring cycles. We develop a polynomial-time algorithm to compute the set of linearly independent cycles.
For networks that are less than three-edge-connected, we show how the minimum number of monitors required and their placement may be computed. For networks with symmetric directed links, we show the relationship between the number of monitors employed, the number of directed links for which metric is known apriori, and the identi fi ability for the remaining links.
To the best of our knowledge, this is the first work that derives the necessary and sufficient conditions on the network topology for identifying additive link metrics and develops a polynomial-time algorithm to compute linearly independent cycles and paths
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
INSIGHTS ON MEDIA STREAMING PROGRESS USING BITTORRENT-LIKE PROTOCOLS FOR ON-DEMAND STREAMING
This paper develops analytical models that characterize the behavior of on-demand stored media content delivery using BitTorrent-like protocols. The models capture the effects of different piece selection policies, including Rarest-First, two vari-ants of In-Order, and two probabilistic policies (Portion and Zipf).
Our models provide insight into system behavior and help explain the sluggishness of the system with In-Order streaming. We use the models to compare different retrieval policies across a wide range of system parameters, including peer arrival rate, upload/ download bandwidth, and seed residence time.
We also provide quantitative results on the startup delays and retrieval times for streaming media delivery. Our results provide insights into the de-sign tradeoffs for on-demand media streaming in peer-to-peer net-works. Finally, the models are validated using simulations
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
GREEDY GEOGRAPHIC ROUTING IN LARGE-SCALE SENSOR NETWORKS: A MINIMUM NETWORK DECOMPOSITION APPROACH
In geographic (or geometric) routing, messages are by default routed in a greedy manner: The current node always forwards a message to its neighbor node that is closest to the destination. Despite its simplicity and general efficiency, this strategy alone does not guarantee delivery due to the existence of local minima (or dead ends).
Overcoming lo cal minima requires nodes to maintain extranonlocal state or to use auxiliary mechanisms. We study how to facilitate greedy forwarding by using a minimum amount of such nonlocal states in topologically complex networks. Specifically, we investigate the problem of decomposing a given network into a minimum number of greedily routable components (GRCs), where greedy routing is guaranteed to work.
We approach it by considering an approximate version of the problem in a continuous domain, with a central concept called the greedily routable region(GRR). A full characterization of GRR is given concerning its geometric properties and routing capability. We then develop simple approximate algorithms for the problem. These results lead to a practical routing protocol that has a routing stretch below 7 in a continuous domain, and close to 1 in several realistic network settings
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
ESM: EFFICIENT AND SCALABLE DATA CENTER MULTICAST ROUTING
Multicast benefits group communications in saving network traffic and improving application throughput, both of which are important for data center applications. However, the technical trend of data center design poses new challenges for efficient and scalable multicast routing. First, the densely connected networks make traditional receiver-driven multicast routing protocols inefficient in multicast tree formation.
Second, it is quite difficult for the low-end switches widely used in data centers to hold the routing entries of massive multicast groups. In this paper, we propose ESM, an effi cient and scalable multicast routing scheme for data center networks.
ESM addresses the challenges above by exploiting the feature of modern data center networks. Based on the regular topology of data centers, ESM uses a source-to-receiver expansion approach to build efficient multicast trees, excluding many unnecessary intermediate switches used in receiver-driven multicast routing.
For scalable multicast routing, ESM combines both in-packet Bloom Filters and in-switch entries to make the tradeoff between the number of multicast groups supported and the additional bandwidth overhead. Simulations show that ESM saves 40% 50% network traffic and doubles the application throughputs compared to receiver-driven multicast routing, and the combination routing scheme significantly reduces the number of in-switch entries required. We implement ESM on a Linux platform.
The experimental results further demonstrate that ESM can well support online tree building for large-scale groups with churns, and the overhead of the combination for-warding engine is light-weighted
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
EFFICIENT SCHEDULING FOR PERIODIC AGGREGATION QUERIES IN MULTIHOP SENSOR NETWORKS
In this paper, we study periodic query scheduling for data aggregation with minimum delay under various wireless in-terference models. Given a set o f periodic aggregation queries, each query has its own period and the subset of source nodes containing the data.
We first propose a family of efficient and effective real-time scheduling protocols that can answer every job of each query task within a relative delay under resource constraints by addressing the following tightly coupled tasks: routing, transmission plan constructions, node activity scheduling, and packet scheduling. Based on our protocol design, we further propose schedulability test schemes to efficiently and effectively test whether, for a set of queries, each query job can be finished within a finite delay.
Our theoretical analysis shows that our methods achieve at least a constant fraction of the maximum possible total utilization for query tasks, where the constant depends on wireless interference models. We also conduct extensive simulations to validate the proposed protocol and evaluate its practical performance. The simulations corroborate our theoretical analysis
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
DIFFERENTIATED QUALITY-OF-RECOVERY IN SURVIVABLE OPTICAL MESH NETWORKS USING -STRUCTURES
This paper investigates desi gn methods of protection schemes in survivable WDM networks that use preconfigured protection structures ( -structures) in order to pro vide different quality-of-recovery (QoR) classes within 100% resilient single-link protection schemes.
QoR differentiation is a practical and effective approach in order to strike different balance s among protection cost, recovery delay, and manage ment complexity.
Based on the degree of pre-cross connectivity of the protection structures, we develop three design approaches of shared protection capacity schemes based on the following: 1) fully pre-cross-connected -structures ( -structures); 2) partially pre-cross-connected -structures ( -structures); and 3) dynamically recon figured -structures ( -structures). In order to identify the optimal combinations of protection structures to meet the requirements of the three QoR classes, we use a column generation (CG) model that we solve using large-scale optimization techniques.
Our CG decomposition approach is based on the separation processes of the design and selection of the protection structures. In the design process of the protection structures, the shape and protection capability of each -structure is decided dynamically during the selection process depending on the network topology and the targeted QoR parameters.
Extensive experiments are carried out on several data instances with different design constraints in order to measure the protection capacity cost and the recovery delay for the three QoR classes
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
DESIGN OF WIRELESS SENSOR NETWORKS FOR MOBILE TARGET DETECTION
We consider surveillance applications through wire-less sensor networks (WSNs) where the areas to be monitored are fully accessible and the WSN topology can be planned apriori to maximize application efficiency.
We pro pose an optimization framework for selecting the positions of wireless sensors to detect mobile targets traversing a given area. By leveraging the concept of path exposure as a measure of detection quality, we propose two problem versions: the minimization of the sensors installation cost while guaranteeing a minimum exposure, and the maximization of the exposure of the least-exposed path subject to a budget on the sensors installation cost.
We present compact mixed-integer linear programming formulations for these problems that can be solved to optimality for reasonable-sized network instances. More-over, we develop Tabu Search heuristics that are able to provide near-optimal solutions of the same instances in short computing time and also tackle large size instances.
The basic versions are extended to account for constraints on the wireless connectivity as well as heterogeneous devices and nonuniform sensing. Finally, we analyze an enhanced exposure definition based on mobile target detection probability
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
CONGESTION-DEPENDENT PRICING AND FORWARD CONTRACTS FOR COMPLEMENTARY SEGMENTS OF A COMMUNICATION NETWORK
Congestion-dependent pricing is a form of traffic management that ensures the efficient allocation of bandwidth between users and applications. As the unpredictability of con-gestion prices creates revenue uncertainty for network providers and cost uncertainty for users, it has been suggested that forward contracts could be used to manage these risks.
We develop a novel game-theoretic model of a multiprovider communication network with two complementary segments and investigate whether for-ward contracts would be adopted by service providers.
Service on the upstream segment is provided by a single Internet service provider (ISP) and priced dynamically to maximize profit, while several smaller ISPs sell connectivity on the downstream network segment, with the advance possibility of entering into forward contracts with their users for some of their capacity.
We show that the equilibrium forward contracting volumes are necessarily asymmetric, with one downstream provider entering into fewer forward contracts than the other competitors, thus ensuring a high subsequent downstream price level.
In practice, network providers will choose the extent of forward contracting strategically based not only on their risk tolerance, but also on the market structure in the interprovider network and their peers’ actions.
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
DECLARATIVE POLICY-BASED ADAPTIVE MOBILE AD HOC NETWORKING
This paper presents DAWN, a declarative platform that creates highly adaptive policy-based mobile ad hoc network (MANET) protocols. DAWN leverages declarative networking techniques to achieve extensible routing and forwarding using declarative languages. We make the following contributions.
First, we demonstrate that traditional MANET protocols can be expressed in a concise fashion as declarative networks and policy-driven adaptation can be specified i n the same language to dictate the dynamic selection of different protocols based on various network and traffic conditions.
Second, we propose interprotocol forwarding techniques t hat ensure packets are able to seamlessly traverse across clusters of nodes running different protocols selected based on their respective policies.
Third, we have developed a full-fl edged implementation of DAWN using the RapidNet declarative networking system. We experimentally validate a variety of policy-based adaptive MANETs in various dynamic settings using a combination of ns-3 simulations and deployment on the ORBIT testbed.
Our experimental results demonstrate that hybrid protocols developed using DAWN out-perform traditional MANET routing protocols and are able to flexibly and dynamically adapt their routing mechanisms to achieve a good tradeoff between b and width utilization and route quality. We further demonstrate DAWN’s capabilities to achieve interprotocol forwarding across different protocols
*------------*------------*------------*------------*------------*------------*
DOMAIN - NETWORKING
CONCISE LOOKUP TABLES FOR IPV4 AND IPV6 LONGEST PREFIX MATCHING IN SCALABLE ROUTERS
We present a distinct longest prefi xmatching(LPM) lookup scheme able to achieve exceedingly concise lookup ta-bles (CoLT), suitable for scalable routers.
Based on unified hash tables for handling both IPv4 and IPv6 simultaneously, CoLT excels over previous mechanisms in: 1) lower on-chip storage for lookup tables; 2) simpler table formats to enjoy richer prefi x aggregation and easier implementation; and 3) most importantly, deemed the only design able to accommodate both IPv4 and IPv6 addresses uniformly and effectively.
As its hash tables permit multiple possible buckets to hold each prefix (following a migration rule to avoid false positives altogether), CoLT exhibits the best memory efficiency and can launch parallel search over tables during every LPM lookup, involving fewer cycles per lookup when on-chip memory is used to implement hash tables.
With 16 (or 32) on-chip SRAM blocks clocked at 500 MHz (achievable in today’s 65-nm technology), it takes 2 (or 1.6) cycles on average to complete a lookup, yielding 250 (or 310 ) millions of packets per second (MPPS) mean throughput. Being hash-oriented, CoLT well supports incremental table updates, besides its high table utilization and lookup throughput.
*------------*------------*------------*------------*------------*------------*
DOMAIN – NETWORKING
BALANCING RELIABILITY AND UTILIZATION IN DYNAMIC SPECTRUM ACCESS
Future wireless networks will dynamically access spectrum to maximize its utilization. Conventional design of dynamic spectrum access focuses on maximizing spectrum utilization, but faces the problem of degraded reliability due to unregulated demands and access behaviors. Without providing proper reliability guarantee, dynamic spectrum access is unacceptable to many infrastructure networks and services.
In this paper, we propose SPARTA, a new architecture for dynamic spectrum access that balances access reliability and spectrum utilization. SPARTA includes two complementary techniques: proactive ad-mission control performed by a central entity to determine the set of wireless nodes to be supported with only statistical information of their spectrum demands, and online adaptation performed by admitted wireless nodes to adjust their instantaneous spectrum usage to time-varying demand.
Using both theoretical analysis and simulation, we show that SPARTA fulfills the reliability re-quirements while dynamically multiplexing spectrum demands to improve utilization.
Compared to conventional solutions, SPARTA improves spectrum utilization by 80%–200%. Finally, SPARTA also allows service providers to explore the tradeoff between utilization and reliability to make the best use of the spectrum. To our best knowledge, our work is the first to identify and address such a tradeoff
*------------*------------*------------*------------*------------*------------*
DOMAIN – NETWORKING
ADAPTIVE SELECTIVE VERIFICATION: AN EFFICIENT ADAPTIVE COUNTERMEASURE TO THWART DOS ATTACKS
Denial-of-service (DoS) attacks are considered within the province of a shared channel model in which attack rates may be large but are bounded and client request rates vary within fixed bounds. In this setting, it is shown that clients can adapt effectively to an attack by increasing their request rate based on timeout windows to estimate attack rates.
The server will be able to process client requests with high probability while pruning out most of the attack by selective random sampling. The protocol introduced here, called Adaptive Selective Verification (ASV), is shown to use bandwidth efficiently and does not require any server state or assumptions about network congestion.
The main results of the paper are a formulation of optimal performance and a proof that ASV is optimal
*------------*------------*------------*------------*------------*------------*
DOMAIN – NETWORKING
A THEORY FOR THE CONNECTIVITY DISCOVERED BY ROUTING PROTOCOLS
Route-vector protocols, such as the Border Gateway Protocol (BGP), have nodes elect and exchange routes in order to discover paths over which to send traffic. We ask the following: What is the minimum number of links whose failure prevents a route-vector protocol from finding such paths?
The answer is not obvious because routing policies prohibit some paths from carrying traffic and because, on top of that, a route-vector protocol may hide paths the routing policies would allow. We develop an algebraic theory to address the above and related questions.
In particular, we characterize a broad class of routing policies for which we can compute in polynomial time the minimum number of links whose failure leaves a route-vector protocol without a communication path from one given node to another.
The theory is applied to a publicly available description of the Internet topology to quantify how much of its intrinsic connectivity is lost due to the traditional customer–provider, peer–peer r outing policies and how much can be regained with simple alternative policies
*------------*------------*------------*------------*------------*------------*
