waashk/dblp huggingface dataset:
buffer management for aggregated streaming data with packet dependencies. in many applications the traffic traversing the network has inter-packet dependencies due to application-level encoding schemes. for some applications, e.g., multimedia streaming, dropping a single packet may render useless the delivery of a whole sequence. in such environments, the algorithm used to decide which packet to drop in case of buffer overflows must be carefully designed, to avoid goodput degradation. we present a model that captures such inter-packet dependencies, and design algorithms for performing packet discards. traffic consists of an aggregation of multiple streams, each of which consists of a sequence of inter-dependent packets. we provide two guidelines for designing buffer management algorithms for this problem, and demonstrate the effectiveness of these criteria. we devise an algorithm according to these guidelines and evaluate its performance analytically, using competitive analysis. we also present a simulation study that shows that the performance of our algorithm is within a small fraction of the performance of the best offline algorithm.
green wave: latency and capacity-efficient sleep scheduling for wireless networks. while scheduling the nodes in a wireless network to sleep periodically can save energy, it also incurs higher latency and lower throughput. we consider the problem of designing optimal sleep schedules in wireless networks, and show that finding sleep schedules that can minimize the latency over a given subset of source-destination pairs is np-hard. we also derive a latency lower bound given by d+o(1/p) for any sleep schedule with a required active rate (i.e., the fraction of active slots of each node) p, and the shortest path length d. we offer a novel solution to optimal sleep scheduling using green-wave sleep scheduling (gwss), inspired by coordinated traffic lights, which is shown to meet our latency lower bound (hence is latency-optimal) for topologies such as the line, grid, ring, torus and tree networks, under light traffic. for high traffic loads, we propose noninterfering gwss, which can achieve the maximum throughput scaling law given by t(n, p) = ω(p/√n) bits/sec on a grid network of size n, with a latency scaling law d(n, p) = o(√n)+o(1/p). finally, we extend gwss to a random network with n poisson-distributed nodes, for which we show an achievable throughput scaling law of t(n, p) = ω(p/√n log n) bits/sec and a corresponding latency scaling law d(n, p) = o(√n/ log n) + o(1/p); hence meeting the well-known gupta-kumar achievable throughput rate ω(1/√n log n) when p → 1.
truthful least-priced-path routing in opportunistic spectrum access networks. we study the problem of finding the least-priced path (lpp) between a source and a destination in opportunistic spectrum access (osa) networks. this problem is motivated by economic considerations, whereby spectrum opportunities are sold/leased to secondary radios (srs). this incurs a communication cost, e.g., for traffic relaying. as the beneficiary of these services, the end user must compensate the service-providing srs for their spectrum cost. to give an incentive (i.e., profit) for srs to report their true cost, typically the payment to a sr should be higher than the actual cost. however, from an end user's perspective, unnecessary overpayment should be avoided. so we are interested in the optimal route selection and payment determination mechanism that minimizes the price tag of the selected route and at the same time guarantees truthful cost reports from srs. this setup is in contrast to the conventional truthful least-cost path (lcp) problem, where the interest is to find the minimum-cost route. the lpp problem is investigated with and without capacity constraints at individual srs. for both cases, our algorithmic solutions can be executed in polynomial time. the effectiveness of our algorithms in terms of price saving is verified through extensive simulations.
bittorrent darknets. a private bittorrent site (also known as a "bit-torrent darknet") is a collection of torrents that can only be accessed by members of the darknet community. the private bittorrent sites also have incentive policies which encourage users to continue to seed files after completing downloading. although there are at least 800 independent bittorrent darknets in the internet, they have received little attention in the research community to date. we examine bittorrent darknets from macroscopic, medium-scopic and microscopic perspectives. for the macroscopic analysis, we consider 800+ private sites to obtain a broad picture of the darknet landscape, and obtain a rough estimate of the total number of files, accounts, and simultaneous peers within the entire darknet landscape. although the size of each private site is relatively small, we find the aggregate size of the darknet landscape to be surprisingly large. for the medium-scopic analysis, we investigate content overlap between four private sites and the public bittorrent ecosystem. for the microscopic analysis, we explore in-depth one private site and examine its user behavior. we observe that the seed-to-leecher ratios and upload-to-download ratios are much higher than in the public ecosystem. the macroscopic, medium-scopic and microscopic analyses when combined provide a vivid picture of the darknet landscape, and provide insight into how the darknet landscape differs from the public bittorrent ecosystem.
understanding node localizability of wireless ad-hoc 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 localized. 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 examine 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 and 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 nodes one can expect to locate in sparsely or moderately connected networks. to validate this design, we implement our solution on a real-world system and the experimental results show that node localizability provides useful guidelines for network deployment and other location-based services.
deploying mesh nodes under non-uniform propagation. wireless mesh networks are popular as a cost-effective means to provide broadband connectivity to large user populations. a mesh network placement provides coverage, such that each target client location has a link to a deployed mesh node, and connectivity, such that each mesh node wirelessly connects directly to a gateway or via intermediate mesh nodes. prior work on placement assumes wireless propagation to be uniform in all directions, i.e., an unrealistic assumption of circular communication regions. in this paper, we present approximation algorithms to solve the np-hard mesh node placement problem for non-uniform propagation settings. the first key challenge is incorporating non-uniform propagation, which we address by formulating the problem input as a connectivity graph consisting of discrete target coverage locations and potential mesh node locations. this graph incorporates non-uniform propagation by specifying the estimated signal quality per link. secondly, our algorithms are the first to minimize the number of deployed mesh nodes with constant-factor approximation ratio in the non-uniform propagation setting. to achieve this, we formulate the degree-constrained terminal steiner tree problem and present approximation algorithms which leverage prior results on the steiner tree problem. third, it is impractical to measure all possible potential mesh links, and therefore deployment planning must rely on estimations. to address this challenge, we extend our algorithm to iteratively measure the links in the solution steiner tree, refining the graph input on a per-link basis in order to ensure the deployed network is not disconnected. finally, we use propagation measurements at 35,000 locations in the deployed googlewifi network to investigate placement in a realistic, non-uniform propagation environment. under this measured propagation setting, our algorithms result in up to 80% fewer mesh nodes than current algorithms and only require an average of 3 measurements per deployed mesh node to ensure backhaul connectivity.
distributed monitoring and aggregation in wireless sensor networks. self-monitoring the sensor statuses such as liveness, node density and residue energy is critical for maintaining the normal operation of the sensor network. when building the monitoring architecture, most existing work focuses on minimizing the number of monitoring nodes. however, with less monitoring points, the false alarm rate may increase as a consequence. in this paper, we study the fundamental tradeoff between the number of monitoring nodes and the false alarm rate in the wireless sensor networks. specifically, we propose fully distributed monitoring algorithms, to build up a poller-pollee based architecture with the objective to minimize the number of overall pollers while bounding the false alarm rate. based on the established monitoring architecture, we further explore the hop-by-hop aggregation opportunity along the multihop path from the polee to the poller, with the objective to minimize the monitoring overhead. we show that the optimal aggregation path problem is np-hard and propose an opportunistic greedy algorithm, which achieves an approximation ratio of 5/4. as far as we know, this is the first proved constant approximation ratio applied to the aggregation path selection schemes over the wireless sensor networks.
cooperative communications in multi-hop wireless networks: joint flow routing and relay node assignment. it has been shown that cooperative communications (cc) have the potential to significantly increase the capacity of wireless networks. however, most of the existing results are limited to single-hop wireless networks. to illustrate the benefits of cc in multi-hop wireless networks, we solve a joint optimization problem of relay node assignment and flow routing for concurrent sessions. we study this problem via mathematical modeling and solve it using a solution procedure based on the branch-and-cut framework. we design several novel components to speed-up the computation time of branch-and-cut. via numerical results, we show the significant rate gains that can be achieved by incorporating cc in multi-hop networks.
wireless network virtualization as a sequential auction game. we propose a virtualization framework to separate the network operator (no) who focuses on wireless resource management and service providers (sp) who target distinct objectives with different constraints. within the proposed framework, we model the interactions among sps and no as a stochastic game, each stage of which is played by sps (on behalf of the end users) and is regulated by the no through the vickrey-clarke-groves (vcg) mechanism. due to the strong coupling between the future decisions of sps and lack of global information at each sp, the stochastic game is notoriously hard. instead, we introduce conjectural prices to represent the future congestion levels the end users potentially will experience, via which the future interactions between sps are decoupled. then, the policy to play the dynamic rate allocation game becomes selecting the conjectural prices and announcing a strategic value function (i.e., the preference on the rate) at each time. we prove that there exists one nash equilibrium in the conjectural prices and, given the conjectural prices, the sps have to truthfully reveal their own value function. we further prove that this nash equilibrium results in efficient rate allocation in our virtualized wireless network. in other words, there are enough incentives for no to advertise such a conjectural price and sps to follow this advice.
employing the one-sender-multiple-receiver technique in wireless lans. in this paper, we study the one-sender-multiple-receiver (osmr) transmission technique, which allows one sender to send to multiple receivers simultaneously by utilizing multiple antennas at the sender. we implemented a prototype osmr transmitter/receiver with gnu software defined radio, and conducted experiments in a university building to study the physical layer characteristics of osmr. our results are positive and show that wireless channels allow osmr for a significant percentage of the time. motivated by our physical layer study, we propose extensions to the 802.11 mac protocol to support osmr transmission, which is backward compatible with existing 802.11 devices. we also note that the ap needs a packet scheduling algorithm to efficiently exploit osmr. we show that the scheduling problem without considering the packet transmission overhead can be formalized as a linear programming problem, but the scheduling problem considering the overhead is np-hard.we then propose a greedy algorithm to schedule osmr transmissions. we tested the proposed protocol and algorithm with simulations driven by traffic traces collected from wireless lans and channel state traces collected from our experiments, and the results show that osmr significantly improves the downlink performance
a hybrid decision approach for the association problem in heterogeneous networks. the area of networking games has had a growing impact on wireless networks. this reflects the recognition in the important scaling advantages that the service providers can benefit from by increasing the autonomy of mobiles in decision making. this may however result in inefficiencies that are inherent to equilibria in non-cooperative games. due to the concern for efficiency, centralized protocols keep being considered and compared to decentralized ones. from the point of view of the network architecture, this implies the co-existence of network-centric and terminal centric radio resource management schemes. instead of taking part within the debate among the supporters of each solution, we propose in this paper hybrid schemes where the wireless users are assisted in their decisions by the network that broadcasts aggregated load information. we derive the utilities related to the quality of service (qos) perceived by the users and develop a bayesian framework to obtain the equilibria. numerical results illustrate the advantages of using our hybrid game framework in an association problem in a network composed of hsdpa and 3g lte systems.
a flexible platform for hardware-aware network experiments and a case study on wireless network coding. in this paper, we present the design and implementation of a general, flexible hardware-aware network platform which takes hardware processing behavior into consideration to accurately evaluate network performance. the platform adopts a network-hardware co-simulation approach in which the ns-2 network simulator supervises the network-wide traffic flow and the systemc hardware simulator simulates the underlying hardware processing in network nodes. in addition, as a case study, we implemented wireless all-to-all broadcasting with network coding on the platform. we analyze the hardware processing behavior during the algorithm execution and evaluate the overall performance of the algorithm. our experimental results demonstrate that hardware processing has a significant impact on the algorithm performance and hence should be taken into consideration in the algorithm design. we expect that this hardwareaware platform will become a very useful tool for more accurate network simulations and optimal designs of processingintensive applications.
a new constant factor approximation for computing 3-connected m-dominating sets in homogeneous wireless networks. in this paper, we study the problem of constructing quality fault-tolerant connected dominating sets (cdss) in homogeneous wireless networks, which can be defined as minimum k-connected m-dominating set ((k,m)-cds) problem in unit disk graphs (udgs). we found that every existing approximation algorithm for this problem is incomplete for k ≥ 3 in a sense that it does not generate a feasible solution in some udgs. based on these observations, we propose a new polynomial time approximation algorithm for computing (3, m)-cdss. we also show that our algorithm is correct and its approximation ratio is a constant.
understanding sub-stream scheduling in p2p hybrid live streaming systems. the p2p pull-push hybrid architecture has achieved great success in delivering live video traffic over the internet. however, a formal study on the sub-stream scheduling problem, a key design issue in hybrid systems, is still lacking. in this paper, we propose a max-flow model for mathematical analysis of this problem. we find that the sub-stream scheduling schemes used in existing hybrid systems, including coolstreaming+, gridmedia and lstreaming, individually solve one special case of the proposed max-flow model. moreover, this model can also serve as a benchmark to assess the performance of these existing sub-stream scheduling schemes. further, we propose a weighted max-flow scheme to address the issue of peer heterogeneity in scheduling sub-streams. finally, we point out the benefits of combining the hybrid streaming architecture and layered coding, and we also investigate how to schedule sub-streams in hybrid layered streaming systems.
randomized differential dsss: jamming-resistant wireless broadcast communication. jamming resistance is crucial for applications where reliable wireless communication is required. spread spectrum techniques such as frequency hopping spread spectrum (fhss) and direct sequence spread spectrum (dsss) have been used as countermeasures against jamming attacks. traditional anti-jamming techniques require that senders and receivers share a secret key in order to communicate with each other. however, such a requirement prevents these techniques from being effective for anti-jamming broadcast communication, where a jammer may learn the shared key from a compromised or malicious receiver and disrupt the reception at normal receivers. in this paper, we propose a randomized differential dsss (rd-dsss) scheme to achieve anti-jamming broadcast communication without shared keys. rd-dsss encodes each bit of data using the correlation of unpredictable spreading codes. specifically, bit "0" is encoded using two different spreading codes, which have low correlation with each other, while bit "1" is encoded using two identical spreading codes, which have high correlation. to defeat reactive jamming attacks, rd-dsss uses multiple spreading code sequences to spread each message and rearranges the spread output before transmitting it. our theoretical analysis and simulation results show that rd-dsss can effectively defeat jamming attacks for anti-jamming broadcast communication without shared keys.
leaping multiple headers in a single bound: wire-speed parsing using the kangaroo system. more fundamental than ip lookups and packet classification in routers is the extraction of fields such as ip dest and tcp ports that determine packet forwarding. while parsing of packet fields used to be easy, new shim layers (e.g., mpls, 802.1q, mac-in-mac) of possibly variable length have greatly increased the worst-case path in the parse tree. the problem is exacerbated by the need to accommodate new packet headers and to extract other higher layer fields. programmable routers for projects such as geni will need such flexible parsers. in this paper, we describe the design and implementation of the kangaroo system, a flexible packet parser that can run at 40 gbps even for worst-case packet headers. because conventional solutions that traverse the parse tree one protocol at a time are too slow, kangaroo uses lookahead to parse several protocol headers in one step using a new architecture in which a cam directs the next set of bytes to be extracted. the challenge is to keep the number of cam entries from growing exponentially with the amount of lookahead. we deal with this challenge using a non-uniform traversal of the parse tree, and an offline dynamic programming algorithm that calculates the optimal walk. our experiments on a netfpga prototype show a speedup of 2 compared to an architecture with a lookahead of 1. the architecture can be implemented as a parsing block in a standard 400 mhz asic at 40 gbps using less than 1% of chip area.
distributed power control for cognitive user access based on primary link control feedback. we venture beyond the "listen-before-talk" strategy that is common in many traditional cognitive radio access schemes. we exploit the bi-directional nature of most primary communication systems. by intelligently choosing their transmission parameters based on the observation of primary user (pu) communications, secondary users (sus) in a cognitive network can achieve higher spectrum usage while limiting their interference to the pu. specifically, we propose that the sus listen to the pu's feedback channel to assess their interference on the primary receiver (pu-rx), and adjust radio power accordingly to satisfy the pu's interference constraint. we investigate both centralized and distributed power control algorithms without active pu cooperation. we show that the pu feedback information inherent in many two-way primary systems can be used as important coordination signal among multiple sus to distributively achieve a joint performance guarantee on the primary receiver's quality of service.
acr: active collision recovery in dense wireless sensor networks. packet collision causes packet loss and wastes resources in wireless networks. it becomes even worse in dense wsns, due to burst-traffic and congestion around sinks. in this paper, we propose a novel protocol to recover collided packets. our experiments on a testbed reveal that collisions between long packets and short packets cause a partial error pattern on collided packets, which can be used for efficient recovery. we give a theoretical analysis that demonstrates that combining such collision recovery with csma protocols achieves a significant performance improvement. then, we design acr, an active collision recovery protocol, which actively converts most potential collisions into ls-collisions, and then applies a lightweight fec scheme to recover collided packets with such partial error patterns. we implement acr on a tmote testbed, and compare its performance with other packet recovery schemes. results show that acr significantly reduces the number of retransmissions, and achieves around 25% improvement on transmission efficiency over other schemes.