waashk/dblp huggingface dataset:
robust and scalable integrated routing in manets using context-aware ordered meshes. a new context-aware routing framework for multicast and unicast routing in mobile ad hoc networks is introduced. this framework, which is called carom (context-aware routing over ordered meshes), uses regions of interest to identify connected componnets of the network that span sources and destinations of interest to restrict signaling to occur mostly within these regions. context information is used to compute routing meshes composed of shortest-paths located inside of regions of interest. experimental results based on extensive simulations show that carom attains similar or better data delivery and end-to-end delays than traditional unicast and multicast routing schemes for manets (aodv, olsr, odmrp), and that carom incurs only a fraction of the signaling overhead of traditional routing schemes.
survivable distributed storage with progressive decoding. we propose a storage-optimal and computation efficient primitive to spread information from a single data source to a set of storage nodes, to allow recovery from both crash-stop and byzantine failures. a progressive data retrieval scheme is employed, which retrieves minimal amount of data from live storage nodes. the scheme adapts the cost of successful data retrieval to the degree of errors in the system. implementation and evaluation studies demonstrate comparable performance to that of a genie-aid decoding process.
an attack-defense game theoretic analysis of multi-band wireless covert timing networks. we discuss malicious interference based denial of service (dos) attacks in multi-band covert timing networks using an adversarial game theoretic approach. a covert timing network operating on a set of multiple spectrum bands is considered. each band has an associated utility which represents the critical nature of the covert data transmitted in the band. a malicious attacker wishes to cause a dos attack by sensing and creating malicious interference on some or all of the bands. the covert timing network deploys camouflaging resources to appropriately defend the spectrum bands. a two tier game theoretic approach is proposed to model this scenario. the first tier of the game is the sensing game in which, the covert timing network determines the amount of camouflaging resources to be deployed in each band and the malicious attacker determines the optimal sensing resources to be deployed in each band. in the second tier of the game, the malicious attacker determines the optimal transmit powers on each spectral band it chooses to attack. we prove the existence of nash equilibriums for the games. we compare the performance of our proposed game theoretic mechanism with that of other well known heuristic mechanisms and demonstrate the effectiveness of the proposed approach.
towards an efficient reservation algorithm for distributed reservation protocols. with the proliferation of wireless technologies and the convenience they offer, transporting quality-of-service (qos) demanding traffic such as compressed video over wireless links becomes a trend and a challenging issue. among many factors, media access control (mac) protocols play an important role in the network stack to ensure the qos provisioning for multimedia applications and the efficient utilization of wireless channels. various contention-based or contention-free mac protocols have been proposed to solve these problems. in this paper, we model, analyze with an existing framework, and evaluate two reservation algorithms, subframe-fit and isozone-fit, proposed for distributed reservation protocols exampled by wimedia uwb mac. the models have been validated by extensive simulations using ns- 2 and an mpeg-4 traffic generator. we further improve the system performance by introducing cross-isozone allocation and on-demand compaction to isozone-fit, and discuss how to leverage both contention-based and contention-free mac protocols.
mobility assisted secret key generation using wireless link signatures. we propose an approach where wireless devices, interested in establishing a secret key, sample the channel impulse response (cir) space in a physical area to collect and combine uncorrelated cir measurements to generate the secret key. we study the impact of mobility patterns in obtaining uncorrelated measurements. using extensive measurements in both indoor and outdoor settings, we find that (i) when movement step size is larger than one foot the measured cirs are mostly uncorrelated, and (ii) more diffusion in the mobility results in less correlation in the measured cirs. we develop efficient mechanisms to encode cirs and reconcile the differences in the bits extracted between the two devices. our results show that our scheme generates very high entropy secret bits and that too at a high bit rate. the secret bits, that we generate using our approach, also pass the 8 randomness tests of the nist test suite.
routing in socially selfish delay tolerant networks. existing routing algorithms for delay tolerant networks (dtns) assume that nodes are willing to forward packets for others. in the real world, however, most people are socially selfish; i.e., they are willing to forward packets for nodes with whom they have social ties but not others, and such willingness varies with the strength of the social tie. following the philosophy of design for user, we propose a social selfishness aware routing (ssar) algorithm to allow user selfishness and provide better routing performance in an efficient way. to select a forwarding node, ssar considers both users' willingness to forward and their contact opportunity, resulting in a better forwarding strategy than purely contact-based approaches. moreover, ssar formulates the data forwarding process as a multiple knapsack problem with assignment restrictions (mkpar) to satisfy user demands for selfishness and performance. trace-driven simulations show that ssar allows users to maintain selfishness and achieves better routing performance with low transmission cost.
stable maximum throughput broadcast in wireless fading channels. this research considers network coded broadcast system with multi-rate transmission and dual queue stability constraints. existing network coded broadcast systems consider single rate transmission without receiver queue constraints. first, we shall illustrate that broadcast without network coding cannot support maximum throughput in wireless fading channels. however, the network coded broadcast poses new constraints for the receivers to manage stable queues while the fading channel characteristics suggest the broadcast to operate at multi-rate to achieve higher throughput. in this research, we propose a joint scheduling and network coding (jsnc) strategy for such network coded broadcast system to achieve maximum throughput under queue stability constraint. in a single cell broadcast networks with exogenous arrivals of packets at the base station, we prove that jsnc can stabilize the system as long as the rate of the exogenous arrival flow is within the capacity region. sufficient control parameters are provided in jsnc for trading off between sender's buffer and the receivers' buffers. jsnc can be viewed as a generalization of the classical backpressure scheduling rule to coded information flow. alternatively, jsnc can also be viewed as an extension of network coding theory to queuing system.
inpac: an enforceable incentive scheme for wireless networks using network coding. wireless mesh networks have been widely deployed to provide broadband network access, and their performance can be significantly improved by using a new technology called network coding. in a wireless mesh network using network coding, selfish nodes may deviate from the protocol when they are supposed to forward packets. this fundamental problem of packet forwarding incentives is closely related to the incentive compatible routing problem in wireless mesh networks using network coding, and to the incentive compatible packet forwarding problem in conventional wireless networks, but different from both of them. in this paper, we propose inpac, the first incentive scheme for this fundamental problem, which uses a combination of game theoretic and cryptographic techniques to solve it. we formally prove that, if inpac is used, then following the protocol faithfully is a subgame perfect equilibrium. to make inpac more practical, we also provide an extension that achieves two improvements: (a) an online authority is no longer needed; (b) the computation and communication overheads are reduced. we have implemented and evaluated inpac on the orbit lab testbed. our evaluation results verify the incentive compatibility of inpac and demonstrate that it is efficient.
urca: pulling out anomalies by their root causes. traffic anomaly detection has received a lot of attention over recent years, but understanding the nature of these anomalies and identifying the flows involved is still a manual task, in most cases. we introduce unsupervised root cause analysis (urca) which isolates anomalous traffic and classifies alarms with minimal manual assistance and high accuracy. urca proceeds by successive reduction of the anomalous space, eliminating normal traffic based on feedback from the anomaly detection method. classification is done by clustering a new anomaly with previously labeled events. we validate urca using manually analyzed real anomalies as well as synthetic anomaly injection. our validation shows that urca can accurately diagnose a large range of anomaly types, including network scans, ddos attacks, and major routing changes.
network reliability with geographically correlated failures. fiber-optic networks are vulnerable to natural disasters, such as tornadoes or earthquakes, as well as to physical failures, such as an anchor cutting underwater fiber cables. such real-world events occur in specific geographical locations and disrupt specific parts of the network. therefore, the geography of the network determines the effect of physical events on the network's connectivity and capacity. in this paper, we develop tools to analyze network failures after a 'random' geographic disaster. the random location of the disaster allows us to model situations where the physical failures are not targeted attacks. in particular, we consider disasters that take the form of a 'random' line in a plane. using results from geometric probability, we are able to calculate some network performance metrics to such a disaster in polynomial time. in particular, we can evaluate average two-terminal reliability in polynomial time under 'random' line-cuts. this is in contrast to the case of independent link failures for which there exists no known polynomial time algorithm to calculate this reliability metric. we also present some numerical results to show the significance of geometry on the survivability of the network and discuss network design in the context of random line-cuts. our novel approach provides a promising new direction for modeling and designing networks to lessen the effects of geographical disasters or attacks.
first-fit scheduling for beaconing in multihop wireless networks. beaconing is a primitive communication task in which every node locally broadcasts a packet to all its neighbors within a fixed distance. assume that all communications proceed in synchronous time-slots and each node can transmit at most one fixed-size packet in each time-slot. the problem minimum-latency beaconing schedule (mlbs) in multihop wireless networks seeks a shortest schedule for beaconing subject to the interference constraint. mlbs has been intensively studied since the mid-1980s, but all assume the protocol interference model with uniform interference radii. in this paper, we first present a constant-approximation algorithm for mlbs under the protocol interference model with arbitrary interference radii. then, we develop a constant-approximation algorithm for mlbs under the physical interference model. both approximation algorithms have efficient implementations in a greedy first-fit manner.
reliable adaptive multipath provisioning with bandwidth and differential delay constraints. robustness and reliability are critical issues in network management. to provide resiliency, a popular protection scheme against network failures is the simultaneous routing along multiple disjoint paths. most previous protection and restoration schemes were designed for all-or-nothing protection and thus, an overkill for data traffic. in this work, we study the reliable adaptive multipath provisioning (ramp) problem with reliability and differential delay constraints. we aim to route the connections in a manner such that link failure does not shut down the entire stream but allows a continuing flow for a significant portion of the traffic along multiple (not necessary disjoint) paths, allowing the whole network to carry sufficient traffic even when link/node failure occurs. the flexibility enabled by a multipath scheme has the tradeoff of differential delay among the diversely routed paths. this requires increased memory in the destination node in order to buffer the traffic until the data arrives on all the paths. increased buffer size will raise the network element cost and could cause buffer overflow and data corruption. therefore, differential delay between the multiple paths should be bounded by containing the delay of a path in a range. we first prove that ramp is an np-hard problem. then we present a pseudo-polynomial time solution to solve a special case of ramp, representing edge delays as integers. next, an (1 + ε)-approximation algorithm is proposed to solve the optimization version of the ramp problem. an efficient heuristic is also provided for the ramp problem. we also present numerical results confirming the advantage of our schemes as the first solution for the ramp problem.
slideor: online opportunistic network coding in wireless mesh networks. opportunistic routing significantly increases unicast throughput in wireless mesh networks by effectively utilizing the wireless broadcast medium. with network coding, opportunistic routing can be implemented in a simple and practical way without resorting to a complicated scheduling protocol. traditionally, due to the constraints of computational complexity, a protocol utilizing network coding needs to partition the data into multiple segments and encode only packets in the same segment. however, it is extremely challenging to decide the optimal time to move to the transmissions of the next segment, and existing designs all resort to different heuristic ideas that might harm network throughput. to address this problem, we propose slideor, a new protocol to encode source packets in overlapping sliding windows such that coded packets from one window position may be useful towards decoding the source packets inside another window position. through extensive simulations, we show that slideor outperforms the existing solutions and is amenable to much simpler implementation than solutions with complicated scheduling among multiple segments.
maintaining approximate minimum steiner tree and k-center for mobile agents in a sensor network. we study the problem of maintaining group communication between m mobile agents, tracked and helped by n static networked sensors. we develop algorithms to maintain a o(lg n)-approximation to the minimum steiner tree of the mobile agents such that the maintenance message cost is on average o(lg n) per each hop an agent moves. the key idea is to extract a 'hierarchical well-separated tree (hst)' on the sensor nodes such that the tree distance approximates the sensor network hop distance by a factor of o(lg n). we then prove that maintaining the subtree of the mobile agents on the hst uses logarithmic messages per hop movement. with the hst we can also maintain o(lg n) approximate k-center for the mobile agents with the same message cost. both the minimum steiner tree and the k-center problems are np-hard and our algorithms are the first efficient algorithms for maintaining approximate solutions in a distributed setting.
efficient tag identification in mobile rfid systems. in this paper we consider how to efficiently identify tags on the moving conveyor. considering conditions like the path loss and multi-path effect in realistic settings, we first propose a probabilistic model for rfid tag identification. based on this model, we propose efficient solutions to identify moving rfid tags, according to the fixed-path mobility on the conveyor. a dynamic program based solution and an adaptive solution are proposed to select optimized frame sizes during the query cycles. simulation results indicate that by leveraging the probabilistic model our solutions can achieve much better performance than using parameters for the ideal propagation situations.
pinpoint time difference of arrival for unsynchronized 802.11 wireless cards. the ability to measure location using time of flight in 802.11 networks is impeded by the standard one microsecond clock resolution, imprecise synchronization of the 802.11 protocol, and the inaccuracy of available clock oscillators. we demonstrate a technique for off-the-shelf 802.11 hardware that enables accurate determination of location of transmitting 802.11 devices using time difference of arrival (tdoa). the technique refines the pinpoint clock model for 802.11 wireless cards, enabling accurate translation of times from one frame of reference to another for free-running clocks and producing accurate location of transmitting nodes to within 3m. this technique can locate nodes regardless of their participation in the location system and may be applied to other wireless communication protocols where send and receive timestamps are available.
measurement and diagnosis of address misconfigured p2p traffic. misconfigured p2p traffic caused by bugs in volunteer-developed p2p software or by attackers is prevalent. it influences both end users and isps. in this paper, we discover and study address-misconfigured p2p traffic, a major class of such misconfiguration. p2p address misconfiguration is a phenomenon in which a large number of peers send p2p file downloading requests to a "random" target on the internet. on measuring three honeynet datasets spanning four years and across five different /8 networks, we find address-misconfigured p2p traffic on average contributes 38.9% of internet background radiation, increasing by more than 100% every year. in this paper, we design the p2pscope, a measurement tool, to detect and diagnose such unwanted traffic. after analyzing about two tb data and tracking millions of peers, we find, in all the p2p systems, address misconfiguration is caused by resource mapping contamination, i.e., the sources returned for a given file id through p2p indexing are not valid. different p2p systems have different reasons for such contamination. for emule, we find that the root cause is mainly a network byte ordering problem in the emule source exchange protocol. for bittorrent misconfiguration, one reason is that anti-p2p companies actively inject bogus peers into the p2p system. another reason is that the ktorrent implementation has a byte order problem. we also design approaches to detect anti-p2p peers without false positives.
m-polar: channel allocation for throughput maximization in sdr mesh networks. in traditional wireless networks, nodes use only a single channel per radio interface, thus limiting the overall channel diversity of the network. this restriction is due to the inherent limitations of commercially-available rf devices. with the advent of high-bandwidth software-defined radios (sdrs), we now have the option of assigning multiple contiguous, independent channels to a single wireless interface. this new-found opportunity raises an important question: how do we assign contiguous channels to nodes in order to maximize overall network throughput? this question lies at the often-ignored intersection of single-radio-multi-channel and multi-radio-multi-channel assignment schemes. in this paper, we develop a protocol that assigns contiguous channels with the goal of evenly spreading the load across the multiple channels. neighboring nodes greedily adjust their channel ranges according to channel conditions to achieve an overall pattern of partially-overlapping bandwidths that maximizes the network throughput. the end-result is a network that can dynamically adapt its bandwidth usage to the network load and the conditions of the different channels. the proposed protocol is evaluated with a prototype built upon the usrp as well as with detailed simulation.
throughput, delay, and mobility in wireless ad hoc networks. throughput capacity in wireless ad hoc networks has been studied extensively under many different mobility models such as i.i.d. mobility model, brownian mobility model, random walk model, and so on. most of these research works assume global mobility, i.e., each node moves around in the whole network, and the results show that a constant per-node throughput can be achieved at the cost of very high expected average end-to-end delay. thus, we are having a very big gap here, either low throughput and low delay in static networks or high throughput and high delay in mobile networks. in this paper, employing a more practical restricted random mobility model, we try to fill in this gap. specifically, we assume a network of unit area with n nodes is evenly divided into n2α cells with an area of n-2αwhere 0 ≤ α ≤ 1/2 , each of which is further evenly divided into squares with an area of n-2β where 0 ≤ β ≤ 1/2. all nodes can only move inside the cell which they are initially distributed in, and at the beginning of each time slot, every node moves from its current square to a uniformly chosen point in an uniformly chosen adjacent square. proposing a new multi-hop relay scheme, we present an upper bound and a lower bound on per-node throughput capacity and expected average end-to-end delay, respectively. we finally explicitly show smooth trade-offs between throughput and delay by controlling nodes' mobility.
designing low-capacity backup networks for fast restoration. there are two basic approaches to allocate protection resources for fast restoration. the first allocates resources upon the arrival of each connection request; yet, it incurs significant setup time and is often capacity-inefficient. the second approach allocates protection resources during the network configuration phase; therefore, it needs to accommodate any possible arrival pattern of connection requests, hence potentially calling for a substantial over-provisioning of resources. however, in this study we establish the feasibility of this approach. specifically, we consider a scheme that, during the network configuration phase, constructs an (additional) low-capacity backup network. upon a failure, traffic is rerouted through a bypass in the backup network. we establish that, with proper design, backup networks induce feasible capacity overhead. we further impose several design requirements (e.g., hop-count limits) on backup networks and their induced bypasses, and prove that, commonly, they also incur minor overhead. motivated by these findings, we design efficient algorithms for the construction of backup networks.