waashk/dblp huggingface dataset:
on the cost of knowledge of mobility in dynamic networks. in this paper, an information-theoretic framework is developed for characterizing the minimum cost, in bits per second, of tracking the motion state information, such as locations and velocities, of nodes in dynamic networks. the minimumcost motion-tracking problem is formulated as a rate-distortion problem, where the minimum cost is the minimum rate of information required to identify the network state at a sequence of tracking time instants within a certain distortion bound. the formulation is general in that it can be applied to a variety of mobility models, distortion criteria, and stochastic sequences of tracking time instants. under the gauss-markov mobility model, lower bounds on the information rate of tracking the motion state information of nodes in dynamic networks are derived, where the motion state of a node is 1) the node's locations only, or 2) both its locations and velocities. the results are then used to analyze the protocol overhead of geographic routing protocols in mobile ad hoc networks. the minimum overhead incurred by maintaining the geographic information of the nodes is characterized in terms of node mobility, packet arrival process and distortion bounds. this leads to precise mathematical description of the observation that, given certain state-distortion allowance, protocols aimed at tracking motion state information (such as geographic routing protocols) may not scale beyond a certain level of node mobility.
practical and general amplify-and-forward designs for cooperative networks. cooperative networks allow the nodes relaying each other's messages to enhance the transmission reliability over wireless fading channels by achieving cooperative diversity. among the various relaying protocols, the amplify-and-forward (af) strategy is well studied for its simplicity. however, to collect the cooperative diversity, there are two main issues that the af protocol is facing. one is that the channel state information (csi) of the source-to-relay link (i.e., two-hop csi) is needed at the destination. the other concern is that the power scaling factor (psf) and output signals at the relay are unbounded. these two issues make af less practical in resource constrained networks, e.g., blind and peak power constrained relays. in this paper, we reveal the necessary and sufficient conditions on designing the psf for the maximum ratio combining (mrc) receiver at the destination with two-hop (th) csi to achieve full cooperative diversity. furthermore, we also provide the necessary conditions on the psf design so that mrc with only one-hop (oh) csi still collects full cooperative diversity. these designs make af strategies more general and practical. the theoretical analysis is corroborated by numerical simulations.
on providing non-uniform scheduling guarantees in a wireless network. significant research effort has been directed towards the design and performance analysis of imperfect scheduling policies for wireless networks. these imperfect schedulers are of interest despite being sub-optimal, as they allow for more tractable implementation at the expense of some loss in performance. however much of this prior work takes a uniform scaling approach to analyzing scheduling performance, whereby the performance of a scheduling policy is characterized in terms of a single scalar quantity, the efficiency-ratio. while suitable for characterizing worst-case performance, this approach limits one's ability to understand the different extents of performance degradation that may be experienced by different links in a network. such an understanding is very valuable when average performance is of greater interest than the worst-case, or when certain links are more important than others. furthermore, once one approaches scheduler design with non-uniform performance guarantees in mind, one finds that simple modifications to well-known scheduling algorithms can yield substantially improved non-uniform scaling results compared to the original algorithms. in this paper, we make a comprehensive case for adopting such an approach by presenting non-uniform scaling results for a set of algorithms that are variants of well-known algorithms from the class of maximal schedulers.
optimal probing for unicast network delay tomography. network tomography has been proposed to ascertain internal network performances from end-to-end measurements. in this work, we present priority probing, an optimal probing scheme for unicast network delay tomography that is proven to provide the most accurate estimation. we first demonstrate that the fisher information matrix in unicast network delay tomography can be decomposed into an additive form where each term can be obtained numerically. this establishes the space over which we can design the optimal probing scheme. then, we formulate the optimal probing problem into a semidefinite programming (sdp) problem. high computation complexity constrains the sdp solution to only small scale scenarios. in response, we propose a greedy algorithm that approximates the optimal solution. evaluations through simulation demonstrate that priority probing effectively increases estimation accuracy with a fixed number of probes.
reliable gps-free double-ruling-based information brokerage in wireless sensor networks. because the global positioning system (gps) consumes a large amount of power and does not work indoors, many gps-free information brokerage schemes are proposed for wireless sensor networks. each of them, however, either cannot guarantee successful data retrieval or demands a great deal of message overhead to replicate the data. in this paper, we propose a gps-free information brokerage scheme, rdrib, in which the double-ruling technique is used to replicate and retrieve the data. rdrib guarantees successful data retrieval, and, in addition, simulations show that rdrib has good performance in terms of the replication message overhead and the construction message overhead.
towards reliable scheduling schemes for long-lived replaceable sensor networks. to address energy constraint problem in sensor networks, node reclamation and replacement strategy has been proposed for networks accessible to human beings and robots. the major challenge in realizing the strategy is how to minimize the system maintenance cost, especially the frequency in replacing sensor nodes with limited number of backup nodes. new duty cycle scheduling schemes are required in order to address the challenge. tong et al. have proposed a staircase-based scheme to address the problem based on ideal assumptions of sensor nodes that are free of failure and have regular energy consumption rate. since sensor nodes are often deployed in outdoor unattended environment, node failures are inevitable. energy consumption rates of sensor nodes are irregular due to manufacture or environmental reasons. hence, this paper proposes several new schemes to achieve reliable scheduling for node reclamation and replacement. extensive simulations have been conducted to verify that the proposed scheme is effective and efficient.
elastic rate limiting for spatially biased wireless mesh networks. ieee 802.11-based mesh networks can yield a throughput distribution among nodes that is spatially biased, with traffic originating from nodes that directly communicate with the gateway obtaining higher throughput than all other upstream traffic. in particular, if single-hop nodes fully utilize the gateway's resources, all other nodes communicating with the same gateway will attain very little (if any) throughput. in this paper, we show that it is sufficient to rate limit the single-hop nodes in order to give transmission opportunities to all other nodes. based on this observation, we develop a new rate limiting scheme for 802.11 mesh networks, which counters the spatial bias effect and does not require, in principle, any control overhead. our rate control mechanism is based on three key techniques. first, we exploit the system's inherent priority nature and control the throughput of the spatially disadvantaged nodes by only controlling the transmission rate of the spatially advantaged nodes. namely, the single-hop nodes collectively behave as a proxy controller for multi-hop nodes in order to achieve the desired bandwidth distribution. second, we devise a rate limiting scheme that enforces a utilization threshold for advantaged single-hop traffic and guarantees a small portion of the gateway resources for the disadvantaged multi-hop traffic. we infer demand for multi-hop flow bandwidth whenever gateway resource usage exceeds this threshold, and subsequently reduce the rates of the spatially advantaged single-hop nodes. third, since the more bandwidth the spatially disadvantaged nodes attain, the easier they can signal their demands, we allow the bandwidth unavailable for the advantaged nodes to be elastic, i.e., the more the disadvantaged flows use the gateway resources, the higher the utilization threshold is. we develop an analytical model to study a system characterized by such priority, dynamic utilization thresholds, and control by proxy. moreover, we use simulations to evaluate the proposed elastic rate limiting technique.
socially-aware network design games. in many scenarios network design is not enforced by a central authority, but arises from the interactions of several self-interested agents. this is the case of the internet, where connectivity is due to autonomous systems' choices, but also of overlay networks, where each user client can decide the set of connections to establish. recent works have used game theory, and in particular the concept of nash equilibrium, to characterize stable networks created by a set of selfish agents. the majority of these works assume that users are completely non-cooperative, leading, in most cases, to inefficient equilibria. to improve efficiency, in this paper we propose two novel socially-aware network design games. in the first game we incorporate a socially-aware component in the users' utility functions, while in the second game we use additionally a stackelberg (leader-follower) approach, where a leader (e.g., the network administrator) architects the desired network buying an appropriate subset of network's links, driving in this way the users to overall efficient nash equilibria. we provide bounds on the price of anarchy and other efficiency measures, and study the performance of the proposed schemes in several network scenarios, including realistic topologies where players build an overlay on top of real internet service provider networks. numerical results demonstrate that (1) introducing some incentives to make users more socially-aware is an effective solution to achieve stable and efficient networks in a distributed way, and (2) the proposed stackelberg approach permits to achieve dramatic performance improvements, designing almost always the socially optimal network.
a systematic approach for evolving vlan designs. enterprise networks are large and complex, and their designs must be frequently altered to adapt to changing organizational needs. the process of redesigning and reconfiguring enterprise networks is ad-hoc and error-prone, and configuration errors could cause serious issues such as network outages. in this paper, we take a step towards systematic evolution of network designs in the context of virtual local area networks (vlans). we focus on vlans given their importance and prevalence, the frequent need to change vlan designs, and the time-consuming and error-prone process of making changes. we present algorithms for common design tasks encountered in evolving vlans such as deciding which vlan a new host must be assigned to. our algorithms trade off multiple criteria such as broadcast traffic costs, and costs associated with maintaining spanning trees for each vlan in the network, while honoring correctness and feasibility constraints on the design. our algorithms also enable automatic detection of network-wide dependencies which must be factored when reconfiguring vlans. we evaluate our algorithms on longitudinal snapshots of configuration files of a large-scale operational campus network obtained over a two year period. our results show that our algorithms can produce significantly better designs than current practice, while avoiding errors and minimizing human work. our unique data-sets also enable us to characterize vlan related change activities in real networks, an important contribution in its own right.
distributed opportunistic scheduling for ad-hoc communications under delay constraints. with the convergence of multimedia applications and wireless communications, there is an urgent need for developing new scheduling algorithms to support real-time traffic with stringent delay requirements. however, distributed scheduling under delay constraints is not well understood and remains an under-explored area. a main goal of this study is to take some steps in this direction and explore the distributed opportunistic scheduling (dos) with delay constraints. consider a network with m links which contend for the channel using random access. distributed scheduling in such a network requires joint channel probing and distributed scheduling. using optimal stopping theory, we explore dos for throughput maximization, under two different types of average delay constraints: 1) a network-wide constraint where the average delay should be no greater than a; or 2) individual user constraints where the average delay per user should be no greater than αm, m = 1, . . . , m. since the standard techniques for constrained optimal stopping problems are based on sample-path arguments and are not applicable here, we take a stochastic lagrangian approach instead. we characterize the corresponding optimal scheduling policies accordingly, and show that they have a pure threshold structure, i.e. data transmission is scheduled if and only if the rate is above a threshold. specifically, in the case with a network-wide delay constraint, somewhat surprisingly, there exists a sharp transition associated with a critical time constant, denoted by α*. if α is less than α*, the optimal rate threshold depends on α, otherwise it does not depends on α at all, and the optimal policy is the same as that in the unconstrained case. in the case with individual user delay constraints, we cast the threshold selection problem across links as a non-cooperative game, and establish the existence of nash equilibria. again we observe a sharp transition associated with critical time constants {αm*}, in the sense that when αm ≥ αm* for all users, the nash equilibrium becomes the same one as if there were no delay constraints.
value-aware resource allocation for service guarantees in networks. the traditional formulation of the total value of information transfer is a multi-commodity flow problem. here, each data source is seen as generating a commodity along a fixed route, and the objective is to maximize the total system throughput under some concept of fairness, subject to capacity constraints of the links used. this problem is well studied under the framework of network utility maximization and has led to several different distributed congestion control schemes. however, this idea of value does not capture the fact that flows might associate value, not just with throughput, but with link-quality metrics such as packet delay, jitter and so on. the traditional congestion control problem is redefined to include individual source preferences. it is assumed that degradation in link quality seen by a flow adds up on the links it traverses, and the total utility is maximized in such a way that the quality degradation seen by each source is bounded by a value that it declares. decoupling source-dissatisfaction and link-degradation through an "effective capacity" variable, a distributed and provably optimal resource allocation algorithm is designed, to maximize system utility subject to these quality constraints. the applicability of our controller in different situations is illustrated, and results are supported through numerical examples.
approximation algorithms for many-to-many traffic grooming in wdm mesh networks. a large number of network applications today allow several users to interact together using the many-to-many service mode. in many-to-many communication, also referred to as group communication, a session consists of a group of users (we refer to them as members), where each member transmits its traffic to all other members in the same group. in this paper, we address the problem of grooming sub-wavelength many-to-many traffic (e.g., oc-3) into high-bandwidth wavelength channels (e.g., oc-192) in wdm mesh networks. the cost of a wdm network is dominated by the cost of higher layer electronic ports (i.e., transceivers). a transceiver is needed for each initiation and termination of a lightpath. therefore, our objective is to minimize the total number of lightpaths established. unfortunately, the grooming problem even with unicast traffic has been shown to be np-hard. for a number of special cases where the many-to-many traffic grooming problem is tractable, we efficiently derive the optimal solution, while in the general case, we introduce two novel approximation algorithms. we also consider the routing and wavelength assignment problem with the objective of minimizing the number of wavelengths used. through extensive experiments, we show that the two algorithms use a number of lightpaths that is very close to that of a derived lower bound. also, we compare the two algorithms on the several costs mentioned in the paper including the number of lightpaths and the number of wavelengths used.
approximate capacity subregions of uniform multihop wireless networks. the capacity region of multihop wireless network is involved in many capacity optimization problems. however, the membership of the capacity region is np-complete in general, and hence the direct application of capacity region is quite limited. as a compromise, we often substitute the capacity region with a polynomial approximate capacity subregion. in this paper, we construct polynomial µ-approximate capacity subregions of multihop wireless network under either 802.11 interference model or protocol interference model in which all nodes have uniform communication radii normalized to one and uniform interference radii ρ ≥ 1. the approximation factor µ decreases with ρ in general and is smaller than the best-known ones in the literature. for example, µ = 3 when ρ ≥ 2.2907 under the 802.11 interference model or when ρ ≥ 4.2462 under the protocol interference model. our construction exploits a nature of the wireless interference called strip-wise transitivity of independence discovered in this paper and utilize the independence polytopes of cocomparability graphs in a spatial-divide-conquer manner. we also apply these polynomial µ-approximate capacity subregions to compute µ-approximate solutions for maximum (concurrent) multiflows
topology control for effective interference cancellation in multi-user mimo networks. in multi-user mimo networks, receivers decode multiple concurrent signals using successive interference cancellation (sic). with sic a weak target signal can be deciphered in the presence of stronger interfering signals. however, this is only feasible if each strong interfering signal satisfies a signal-to-noise-plus-interference ratio (sinr) requirement. this necessitates the appropriate selection of a subset of links that can be concurrently active in each receiver's neighborhood; in other words, a sub-topology consisting of links that can be simultaneously active in the network is to be formed. if the selected sub-topologies are of small size, the delay between the transmission opportunities on a link increases. thus, care should be taken to form a limited number of sub-topologies. we find that the problem of constructing the minimum number of sub-topologies such that sic decoding is successful with a desired probability threshold, is np-hard. given this, we propose music, a framework that greedily forms and activates sub-topologies, in a way that favors successful sic decoding with a high probability. music also ensures that the number of selected sub-topologies is kept small. we provide both a centralized and a distributed version of our framework. we prove that our centralized version approximates the optimal solution for the considered problem. we also perform extensive simulations to demonstrate that (i) music forms a small number of sub-topologies that enable efficient sic operations; the number of sub-topologies formed is at most 17% larger than the optimum number of topologies, discovered through exhaustive search (in small networks). (ii) music outperforms approaches that simply consider the number of antennas as a measure for determining the links that can be simultaneously active. specifically, music provides throughput improvements of up to 4 times, as compared to such an approach, in various topological settings. the improvements can be directly attributable to a significantly higher probability of correct sic based decoding with music.
transition from heavy to light tails in retransmission durations. retransmissions serve as the basic building block that communication protocols use to achieve reliable data transfer. until recently, the number of retransmissions were thought to follow a light tailed (in particular, a geometric) distribution. however, recent work seems to suggest that when the distribution of the packets have infinite support, retransmission-based protocols may result in heavy tailed delays and even possibly zero throughput. while this result is true even when the distribution of packet sizes are light-tailed, it requires the assumption that the packet sizes have infinite support. however, in reality, packet sizes are often bounded by the maximum transmission unit (mtu), and thus the aforementioned result merits a deeper investigation. to that end, in this paper, we allow the distribution of the packet size l to have finite support. this packet is sent over an on-off channel {(ai, ui)} with alternating available ai and unavailable ui periods. if l ≥ ai, the transmission fails and we wait for the next period ai+1 to retransmit the packet. the transmission duration is thus measured from the first attempt to a point when a channel available period larger than l. under mild conditions, we show that the transmission duration distribution exhibits a transition from a power law main body to an exponential tail with weibull type distributions between the two. the time scale to observe the power law main body is roughly equal to the average transmission duration of the longest packet. both the power law main body and the exponential tail could dominate the overall performance. for example, the power law main body, if significant, may cause the channel throughput to be very close to zero. on the other hand, the exponential tail, if more evident, may imply that the system operates in a benign environment. these theoretical findings provide an understanding on why some empirical measurements suggest heavy tails and light tails for others (e.g., wireless networks). we use these results to further highlight the engineering implications from distributions with power law main bodies and light tails by analyzing two cases: (1) the throughput of on-off channels with retransmissions, where we show that even when packet sizes have small means and bounded support the variability in their sizes can greatly impact system performance. (2) the distribution of the number of jobs in an m/m/∞ queue with server failures. here we show that retransmissions can cause long-range dependence and quantify the impact of the maximum job sizes on the long-range dependence.