waashk/dblp huggingface dataset:
near-optimal power control in wireless networks: a potential game approach. we study power control in a multi-cell cdma wireless system whereby self-interested users share a common spectrum and interfere with each other. our objective is to design a power control scheme that achieves a (near) optimal power allocation with respect to any predetermined network objective (such as the maximization of sum-rate, or some fairness criterion). to obtain this, we introduce the potential-game approach that relies on approximating the underlying noncooperative game with a "close" potential game, for which prices that induce an optimal power allocation can be derived. we use the proximity of the original game with the approximate game to establish through lyapunov-based analysis that natural user-update schemes (applied to the original game) converge within a neighborhood of the desired operating point, thereby inducing near-optimal performance in a dynamical sense. additionally, we demonstrate through simulations that the actual performance can in practice be very close to optimal, even when the approximation is inaccurate. as a concrete example, we focus on the sumrate objective, and evaluate our approach both theoretically and empirically.
minimizing end-to-end delay in wireless networks using a coordinated edf schedule. we study the end-to-end delay bounds that can be achieved in wireless networks using packet deadlines. we assume a set of flows in the network, for which flow i has burst parameter ωi, injection rate ρi, and path length ki. it was already known that, in wireline networks, the coordinated-earliest-deadline-first (cedf) protocol can achieve and end-to-end delay of approximately (ωi/ρi)+ki, whereas other schedulers such as weighted fair queuing, have end-to-end delay bounds of the form (ωi + ki)/ρi. for the case of wireless networks of arbitrary topology, the focus has typically been more on throughput optimality than minimizing delay. in this paper, we study the delay bounds that can be achieved by combining wireless link scheduling algorithms with a cedf packet scheduler. we first present a centralized scheduler that has an end-to-end delay of approximately o(ω/ρi + σl∈pi n/rl), where rl is the total rate of flows through link l, n is the number of links in the network, and pi is the path followed by packets of flow i. we then show how to convert this into a distributed scheduler. we also study the extent to which results on the schedulability of packet deadlines can be carried over from the wireline to the wireless context. lastly, we examine ways in which the theoretical schedulers considered in this paper can be transferred to a more practical random-access based setting. this work was supported by nsf contract ccf-0728980 and was performed while the first author was visiting bell labs in summer, 2009.
opportunistic routing in multi-radio multi-channel multi-hop wireless networks. two major factors that limit the throughput in multi-hop wireless networks are the unreliability of wireless transmissions and co-channel interference. one promising technique that combats lossy wireless transmissions is opportunistic routing (or). or involves multiple forwarding candidates to relay packets by taking advantage of the broadcast nature and spacial diversity of the wireless medium. furthermore, recent advances in multi-radio multi-channel transmission technology allows more concurrent transmissions in the network, and shows the potential of substantially improving the system capacity. however, the performance of or in multi-radio multi-channel multi-hop networks is still unknown, and the methodology of studying the performance of traditional routing (tr) can not be directly applied to or. in this paper, we present our research on computing an end-to-end throughput bound of or in multiradio multi-channel multi-hop wireless networks. we formulate the capacity of or as a linear programming (lp) problem which jointly solves the radio-channel assignment and transmission scheduling. leveraging our analytical model, we gain the following insights into or: 1) or can achieve better performance than tr under different radio/channel configurations, however, in particular scenarios, tr is more preferable than or; 2) or can achieve comparable or even better performance than tr by using less radio resource; 3) for or, the throughput gained from increasing the number of potential forwarding candidates becomes marginal.
topological properties affect the power of network coding in decentralized broadcast. there exists a certain level of ambiguity regarding whether network coding can further improve download performance in p2p content distribution systems, as compared to commonly applied heuristics such as rarest first protocols. in this paper, we revisit the problem of broadcasting multiple data blocks from a single source in an overlay network using gossiplike protocols. our new finding reveals that the marginal benefit of network coding critically depends on the dynamics of network topologies. we show that although network coding is optimal as a block selection mechanism, simple non-coding protocols are close to optimal in complete and random graphs, leading to marginal benefits of network coding. however, network coding demonstrates salient benefits in clustered and time-varying topologies, which are common in real-world systems with isp-locality mechanisms implemented. through both theoretical analysis and simulation results, we unveil the underlying reasons behind discrepancies in the power of network coding under different scenarios.
adaptive calibration for fusion-based wireless sensor networks. wireless sensor networks (wsns) are typically composed of low-cost sensors that are deeply integrated with physical environments. as a result, the sensing performance of a wsn is inevitably undermined by various physical uncertainties, which include stochastic sensor noises, unpredictable environment changes and dynamics of the monitored phenomenon. traditional solutions (e.g., sensor calibration and collaborative signal processing) work in an open-loop fashion and hence fail to adapt to these uncertainties after system deployment. in this paper, we propose an adaptive system-level calibration approach for a class of sensor networks that employ data fusion to improve system sensing performance. our approach features a feedback control loop that exploits sensor heterogeneity to deal with the aforementioned uncertainties in calibrating system performance. in contrast to existing heuristic based solutions, our control-theoretical calibration algorithm can ensure provable system stability and convergence. we also systematically analyze the impacts of communication reliability and delay, and propose an optimal routing algorithm that minimizes the impact of packet loss on system stability. our approach is evaluated by both experiments on a testbed of tmotes as well as extensive simulations based on data traces gathered from a real vehicle detection experiment. the results demonstrate that our calibration algorithm enables a network to maintain the optimal detection performance in the presence of various system and environmental dynamics.
optimal channel choice for collaborative ad-hoc dissemination. collaborative ad-hoc dissemination has been proposed as an efficient means to disseminate information among devices in wireless ad-hoc networks. it is based on each device forwarding channels that the user of this device is subscribed to and helping forward some other channels. we consider the case where devices have limited resources and thus have to decide which channels to help. the goal is to identify a channel selection strategy that optimizes a global system welfare that is a function of the dissemination times across all distinct channels. we consider a random mixing mobility model under which the channel dissemination time is a function of the number of nodes that forward this channel. we show that maximizing system welfare is equivalent to an assignment problem whose solution can be obtained by a centralized greedy algorithm. we provide empirical evidence that the difference between the system welfare of an optimum assignment and some heuristics proposed in the past can be significant. furthermore, we show that the optimum social welfare can be approximated by a decentralized algorithm based on metropolis-hastings sampling and give a variant that also accounts for the battery energy. our work provides guidelines how to design decentralized channel selection algorithms that optimize an a priori defined global objective.
on the impact of tcp and per-flow scheduling on internet performance. internet performance is tightly related to the properties of tcp and udp protocols, jointly responsible for the delivery of the great majority of internet traffic. it is well understood how these protocols behave under fifo queuing and what are the network congestion effects. however, no comprehensive analysis is available when flow-aware mechanisms such as per-flow scheduling and dropping policies are deployed. previous simulation and experimental results leave a number of unanswered questions. in the paper, we tackle this issue by modeling via a set of fluid non-linear odes the instantaneous throughput and the buffer occupancy of n longlived tcp sources under three per-flow scheduling disciplines (fair queuing, longest queue first, shortest queue first) and with longest queue drop buffer management. we study the system evolution and analytically characterize the stationary regime: closed-form expressions are derived for the stationary throughput/sending rate and buffer occupancy which give a thorough understanding of short/long-term fairness for tcp traffic. similarly, we provide the characterization of the loss rate experienced by udp flows in presence of tcp traffic. as a result, the analysis allows to quantify benefits and drawbacks related to the deployment of flow-aware scheduling mechanisms in different networking contexts. the model accuracy is confirmed by a set of ns2 simulations and by the evaluation of the three scheduling disciplines in a real implementation in the linux kernel.
multicast scheduling with cooperation and network coding in cognitive radio networks. cognitive radio networks (crns) have recently emerged as a promising technology to improve spectrum utilization by allowing secondary users to dynamically access idle primary channels. as progress are made and computationally powerful wireless devices are proliferated, there is a compelling need of enabling multicast services for secondary users. thus, it is crucial to design an efficient multicast scheduling protocol in crns. however, state-of-the-art multicast scheduling protocols are not well designed for crns. first, due to primary channel dynamics and user mobility, there may not exist commonly available channels for secondary users, which inevitably makes the multicast scheduling infeasible. second, the potential benefits provided by user and channel diversities are overlooked, which leads to under-utilization of the scarce wireless bandwidth. in this paper, we present an optimization framework for multicast scheduling in crns, by fully embracing its characteristics. in this framework, base station multicasts data to a subset of secondary users first by carefully tuning the power. concurrently, secondary users opportunistically perform cooperative transmissions using locally idle primary channels, in order to mitigate multicast loss and delay effects. network coding is adopted during the transmissions to reduce overhead and perform error control and recovery. we jointly consider important design factors in our scheduling protocols, including power control, relay assignment, buffer management, dynamic spectrum access, primary user protection, and fairness. we also incorporate user, channel, and cooperative diversities. two forms of multicast scheduling protocols in crns are proposed accordingly: (i) a greedy protocol based on centralized optimization; (ii) an online protocol based on stochastic optimization in both centralized and decentralized manners. with rigorous analysis based on lyapunov optimization, we provide closed-form bounds to characterize the performance of our protocols, in terms of the interference to primary users and throughput utility of secondary users. with extensive simulations, we show that our proposed protocols can significantly improve the multicast performance in crns.
forward contracts for complementary segments of a communication network. congestion-dependent pricing is a form of traffic management that would ensure the efficient allocation of bandwidth between users and applications. as the unpredictability of congestion prices creates revenue uncertainty for network providers and cost uncertainty for users, it has been suggested that longer-term financial agreements such as forward contracts could be used to manage these risks. in a network managed by a single service provider, long-term forward contracts are beneficial for both the provider and the users. we investigate whether forward contracts would be adopted by multiple service providers in a future internet with congestion-dependent pricing. we develop a novel game-theoretic model of a multi-provider communication network with two complementary segments. 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 or all of their capacity. we show that the equilibrium forward contracting levels 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.
ccack: efficient network coding based opportunistic routing through cumulative coded acknowledgments. the use of random linear network coding (nc) has significantly simplified the design of opportunistic routing (or) protocols by removing the need of coordination among forwarding nodes for avoiding duplicate transmissions. however, nc-based or protocols face a new challenge: how many coded packets should each forwarder transmit? to avoid the overhead of feedback exchange, most practical existing nc-based or protocols compute offline the expected number of transmissions for each forwarder using heuristics based on periodic measurements of the average link loss rates and the etx metric. although attractive due to their minimal coordination overhead, these approaches may suffer significant performance degradation in dynamic wireless environments with continuously changing levels of channel gains, interference, and background traffic. in this paper, we propose ccack, a new efficient nc-based or protocol. ccack exploits a novel cumulative coded acknowledgment scheme that allows nodes to acknowledge network coded traffic to their upstream nodes in a simple way, oblivious to loss rates, and with practically zero overhead. in addition, the cumulative coded acknowledgment scheme in ccack enables an efficient credit-based, rate control algorithm. our evaluation shows that, compared to more, a state-of-the-art nc-based or protocol, ccack improves both throughput and fairness, by up to 20x and 124%, respectively, with average improvements of 45% and 8.8%, respectively.
virtual appliance content distribution for a global infrastructure cloud service. cloud computing in general and virtualized infrastructure provisioning in particular, are significant trends with the potential to increase agility and lower costs of it. an emerging cloud service is a virtual server shop, that allows cloud customers to order virtual appliances to be delivered virtually on the cloud. like physical shops, customers want to customize the ordered products, e.g., have them pre-installed with their desired applications and pre-configured. global cloud providers need to create customized virtual-server disk images and deliver them on time to meet the customer reservations and service level. this framework creates a new flavor of content distribution over the web, where large virtual server images need to be delivered to the target compute farms (either on the global cloud or on customer private clouds). in order to reduce provisioning time and meet reservation deadlines, one approach is to stage images on storage near the customer. this introduces an optimization problem of finding an optimal staging schedule, according to network bandwidth, pending reservations schedule, and customer value. this problem has some similarities to cache pre-filling and production-line scheduling. it combines scheduling, bandwidth considerations, and storage capacity constraints. in this paper we study the fundamental properties of this approach and formalize several flavors of the related optimization problem. we prove useful properties of the problem and then use those properties to provide exact efficient algorithms to solve it. we also derive efficient approximate solutions with proven error bounds.
a novel xcast-based caching architecture for inter-gateway handoffs in infrastructure wireless mesh networks. handoff management plays an important role in wireless mesh networks (wmns) in delivering quality of service to mobile users. inter-gateway (across subnets) movement in wmns usually requires the handoff support from multilayers and thus causes nonnegligible delays and packet loss. previous solutions on handoff management in infrastructure wmns mainly focus on intra-gateway mobility (e.g., single gateway is assumed in ieee 802.11s wmns) and exert the reduction of handoff delay so as to reduce packet loss. furthermore, some handoff issues involved in inter-gateway mobility in wmns (e.g., the network-layer handoff detection issue) have not been properly addressed. in this paper, we present a novel architectural design, namely explicit multicast-based (xcast-based) wmns (xmesh), to facilitate inter-gateway handoff management. the proposed xmesh architecture enables parallel executions of handoffs from multilayers, in conjunction with a xcast-based caching mechanism which builds on top of mesh routing protocols to guarantee minimum packet loss during handoffs in wmns. the required number and optimal placement of special mesh routers that form the xmesh architecture are modeled as a set covering problem which is solved based on a greedy algorithm. a comprehensive simulation study shows that the xmesh architecture enables fast handoffs and re-establishment of session communications in the inter-gateway mobility environment. with both the parallel handoff execution and data caching mechanism, our architecture offers a seamless handoff for supporting real-time applications.
cooperative resource management in cognitive wimax with femto cells. wimax with femto cells is a cost-effective next-generation broadband wireless communication system. cognitive radio (cr) has recently emerged as a promising technology to improve spectrum utilization by allowing dynamic spectrum access. there will be large potential benefits by applying the cr technique to wimax with femto cells, which are barely explored in the literature. in this paper, we propose a novel cognitive wimax architecture with femto cells, where the base station and users are equipped with crs and intelligently adjusts power, channel, and other resources to accommodate the entire network ecosystem. in this new design, we develop an optimization framework for location-aware cooperative resource management, by jointly employing multi-hop cooperative communication, power control, channel assignment, primary user protection, buffer management, and fairness, and incorporating user, channel, and cooperative diversities. to achieve optimality, it is designed based on stochastic lyapunov optimization, aiming to take advantage of the radio flexibility and fully utilize the spectrum. evaluated by the rigorous analysis and extensive simulations, our resource management protocol is near-optimal with closed-form bounds, with which cognitive wimax achieves substantial performance improvement.
efficient similarity estimation for systems exploiting data redundancy. many modern systems exploit data redundancy to improve efficiency. these systems split data into chunks, generate identifiers for each of them, and compare the identifiers among other data items to identify duplicate chunks. as a result, chunk size becomes a critical parameter for the efficiency of these systems: it trades potentially improved similarity detection (smaller chunks) with increased overhead to represent more chunks. unfortunately, the similarity between files increases unpredictably with smaller chunk sizes, even for data of the same type. existing systems often pick one chunk size that is "good enough" for many cases because they lack efficient techniques to determine the benefits at other chunk sizes. this paper addresses this deficiency via two contributions: (1) we present multiresolution (mr) handprinting, an application-independent technique that efficiently estimates similarity between data items at different chunk sizes using a compact, multi-size representation of the data; (2) we then evaluate the application of mr handprints to workloads from peer-to-peer, file transfer, and storage systems, demonstrating that the chunk size selection enabled by mr handprints can lead to real improvements over using a fixed chunk size in these systems.
greedy forwarding in dynamic scale-free networks embedded in hyperbolic metric spaces. we show that complex (scale-free) network topologies naturally emerge from hyperbolic metric spaces. hyperbolic geometry facilitates maximally efficient greedy forwarding in these networks. greedy forwarding is topology-oblivious. nevertheless, greedy packets find their destinations with 100% probability following almost optimal shortest paths. this remarkable efficiency sustains even in highly dynamic networks. our findings suggest that forwarding information through complex networks, such as the internet, is possible without the overhead of existing routing protocols, and may also find practical applications in overlay networks for tasks such as application-level routing, information sharing, and data distribution.
is network coding always good for cooperative communications? network coding (nc) is a promising approach to reduce time-slot overhead for cooperative communications (cc) in a multi-session environment. most of the existing works take advantage of the benefits of nc in cc but do not fully recognize its potential adverse effect. in this paper, we show that employing nc may not always benefit cc. we substantiate this important finding in the context of analog network coding (anc) and amplify-and-forward (af) cc. this paper, for the first time, introduces an important concept of network coding noise (nc noise). specifically, we analyze the signal aggregation at a relay node and signal extraction at a destination node. we then use the analysis to derive a closed-form expression for nc noise at each destination node in a multi-session environment. we show that nc noise can diminish the advantage of nc in cc. our results formalizes an important concept on using nc in cc.