waashk/dblp huggingface dataset:
one-way delay estimation using network-wide measurements. we present a novel approach for the estimation of one-way delays between network nodes without any time synchronization in the network. it is based on conducting multiple and simple one-way measurements among pairs of nodes, and estimating the one-way delays by optimizing the value of a global objective function that is affected by the overall network topology and not just by individual measurements. we examine two objective functions. the first intuitive choice is the least square error (lse). using a novel concept of delay-induced link probabilities, we develop a second objective function that is based on the maximum-entropy (me) principle. extensive numerical experiments show that both functions considerably outperform the common method of halving the round-trip delays. they also show that me outperforms the commonly used lse.
on the capacity of information networks. an outer bound on the rate region of noise-free information networks is given. this outer bound combines properties of entropy with a strong information inequality derived from the structure of the network. this blend of information theoretic and graph theoretic arguments generates many interesting results. for example, the capacity of directed cycles is characterized. also, a gap between the sparsity of an undirected graph and its capacity is shown. extending this result, it is shown that multicommodity flow solutions achieve the capacity in an infinite class of undirected graphs, thereby making progress on a conjecture of li and li. this result is in sharp contrast to the situation with directed graphs, where a family of graphs is presented in which the gap between the capacity and the rate achievable using multicommodity flows is linear in the size of the graph.
a general minimax result for relative entropy. suppose nature picks a probability measure p on a complete separable metric space x at random from a fixed set of probability measures. then, without knowing which measure is picked, a statistician picks a measure q on x. finally, the statistician suffers a loss equal to the relative entropy between p and q. we show that the minimax and maximin values of this game are always equal, and there is always a minimax strategy in the closure of the set of all bayes strategies. this generalizes previous results of gallager, and davisson and leon-garcia.
the probability of undetected error can have several local maxima. we show that for a code used for error detection in the bsc, the probability of an undetected error can have several local maxima. in particular, we construct a code with three local maxima in (0,1/2), a code with five local maxima in (0,1); and a linear code with two local maxima in (0,1/2) and a linear code with three local maxima in (0,1).
on the capacity of multiple unicast sessions in undirected graphs. li and li conjectured that in an undirected network with multiple unicast sessions, network coding does not lead to any coding gain. surprisingly enough, this conjecture could not so far be verified even for the simple network consisting of k 3, 2 with four source-sink pairs. using entropy calculus, we provide the first verification of the li-li conjecture for this network. we extend our bound to the case of an arbitrary directed bipartite network.
relaying protocols for two colocated users. we consider a wireless network where a remote source sends information to one of two colocated users, and where the second user can serve as a relay. the source's transmission is subjected to quasi-static flat rayleigh fading, while the transmission of the relay experiences a fixed amplitude gain with a uniform random phase, capturing its close proximity to the destination. all communications share the same time/bandwith resources, and perfect channel state information is known only to the receivers. we propose relaying protocols which are based on wyner-ziv quantization at the relay, and demonstrate their high efficiency (in terms of expected throughput) with respect to previously reported relaying schemes based on amplify-and-forward and decode-and-forward. a salient feature of these protocols is that the relay need not know the actual fading gain experienced by the destination in order to perform the quantization. we also consider a hybrid amplify-quantize-decode-and-forward scheme which exhibits superior performance.
the encoding complexity of network coding. in the multicast network coding problem, a source s needs to deliver h packets to a set of k terminals over an underlying communication network g. the nodes of the multicast network can be broadly categorized into two groups. the first group incudes encoding nodes, i.e., nodes that generate new packets by combining data received from two or more incoming links. the second group includes forwarding nodes that can only duplicate and forward the incoming packets. encoding nodes are, in general, more expensive due to the need to equip them with encoding capabilities. in addition, encoding nodes incur delay and increase the overall complexity of the network.accordingly, in this paper, we study the design of multicast coding networks with a limited number of encoding nodes. we prove that in a directed acyclic coding network, the number of encoding nodes required to achieve the capacity of the network is bounded by h3 k2. namely, we present (efficiently constructible) network codes that achieve capacity in which the total number of encoding nodes is independent of the size of the network and is bounded by h3k2. we show that the number of encoding nodes may depend both on h and k by presenting acyclic coding networks that require ω (h2k) encoding nodes. in the general case of coding networks with cycles, we show that the number of encoding nodes is limited by the size of the minimum feedback link set, i.e., the minimum number of links that must be removed from the network in order to eliminate cycles. we prove that the number of encoding nodes is bounded by (2b + 1) h3k2, where bis the minimum size of a feedback link set. finally, we observe that determining or even crudely approximating the minimum number of required encoding nodes is an np-hard problem.
matrix games in the multicast networks: maximum information flows with network switching. network coding for achieving the maximum information flow in the multicast networks has been proposed by ahlswede, cai, li, and yeung. they have demonstrated that the conventional network switching, without resort to network coding, is in general not able to achieve the optimum information flow that has been promised by network coding. a basic problem arising here is that, for a given multicast network, what is the switching gap of the network defined as the ratio of the maximum information flow in the multicast network with network coding to that only with network switching.in the paper, by considering network switching as a special form of network coding, we make a complete theoretical and computational determination of the achievable information rate region for multisource multicast network switching. the multicast networks are allowed to be cyclic or acyclic with links having arbitrary positive integer or real-valued capacity. network switching is essentially a problem of multicast-route packing in the multicast networks. based on this, we use the theory of games to formulate the network switching as a matrix game between the first "player" of links and the second "player" of multicast routes in the multicast networks. we prove that the maximum achievable information rate at each probabilistic direction in the information rate region is the reciprocal of the value of the corresponding game. consequently, the maximum achievable information rate can be computed in a simple way by applying the existing theory and algorithms for the computation of the value of a matrix game, especially for such multicast networks with links all having unit capacity as the ahlswede-cai-li-yeung multicast networks. for multicast networks with links having arbitrary positive real-valued capacity, by using convex optimization, we develop a simple and efficient iterative algorithm to find the maximum achievable information rates for multisource multicast network switching.for single-source multicast networks whose links have arbitrary positive real-valued capacity, we present two max-flow min-cut theorems. the maximum information flow for single-source network switching is the minimum capacity among all soft link-cuts of the multicast network, while the maximum information flow for single-source network coding is the minimum capacity among all hard link-cuts. consequently, by applying the theory of approximation algorithms for the set-covering problem, we demonstrate that the switching gap of a single-source multicast network is upper-bounded by the th harmonic number hn=1 + ½ +.....+ 1/n where nis the largest number of multicast routes containing a given link in the network. this harmonic-number bound is asymptotically tight as o(ln n) for the combination multicast network. for the special class of multisource multicast networks with the same set of sink nodes, we make a comparison between the achievable information rate regions for network switching and network coding.
a fast lightweight approach to origin-destination ip traffic estimation using partial measurements. in this paper, a novel approach is proposed for estimating traffic matrices. our method, called pamtram for partial measurement of traffic matrices, couples lightweight origin-destination (od) flow measurements along with a computationally lightweight algorithm for producing od estimates. the first key aspect of our method is to actively select a small number of informative od flows to measure in each estimation interval. to avoid the heavy computation of optimal selection, we use intuition from game theory to develop randomized selection rules, with the goals of reducing errors and adapting to traffic changes. we show that it is sufficient to measure only one flow per measurement period to drastically reduce errors--thus rendering our method lightweight in terms of measurement overhead. the second key aspect is an explanation and proof that an iterative proportional fitting algorithm approximates traffic matrix estimates when the goal is a minimum mean-squared error; this makes our method lightweight in terms of computation overhead. a one-step error bound is provided for pamtram that bounds the average error for the worst scenario. we validate our method using data from sprint's european tier-1 ip backbone network and demonstrate its consistent improvement over previous methods.
on achieving maximum multicast throughput in undirected networks. the transmission of information within a data network is constrained by the network topology and link capacities. in this paper, we study the fundamental upper bound of information dissemination rates with these constraints in undirected networks, given the unique replicable and encodable properties of information flows. based on recent advances in network coding and classical modeling techniques in flow networks, we provide a natural linear programming formulation of the maximum multicast rate problem. by applying lagrangian relaxation on the primal and the dual linear programs (lps), respectively, we derive a) a necessary and sufficient condition characterizing multicast rate feasibility, and b) an efficient and distributed subgradient algorithm for computing the maximum multicast rate. we also extend our discussions to multiple communication sessions, as well as to overlay and ad hoc network models. both our theoretical and simulation results conclude that, network coding may not be instrumental to achieve better maximum multicast rates in most cases; rather, it facilitates the design of significantly more efficient algorithms to achieve such optimality.
degenerate delay-capacity tradeoffs in ad-hoc networks with brownian mobility. there has been significant recent interest within the networking research community to characterize the impact of mobility on the capacity and delay in mobile ad hoc networks.in this correspondence, the fundamental tradeoff between the capacity and delay for a mobile ad hoc network under the brownian motion model is studied. it is shown that the two-hop relaying scheme proposed by grossglauser and tse (2001), while capable of achieving a per-node throughput of θ(1), incurs an expected packet delay of ω(logn/αn2), where αn2) is the variance parameter of the brownian motion model. it is then shown that an attempt to reduce the delay beyond this value results in the throughput dropping to its value under static settings.in particular, it is shown that under a large class of scheduling and relaying schemes, if the mean packet delay is o(nα/αn2), for any α ≤ 0, then the per-node throughput must be o(1/√n). this result is in sharp contrast to other results that have recently been reported in the literature.
nonhomogeneous trellis codes for the quasi-synchronous multiple-access binary adder channel with two users. a trellis code is {em homogeneous} if the number of branches emanating from each node (or state) in the trellis diagram is constant. for example, convolutional codes are linear homogeneous trellis codes. a trellis code is {em nonhomogeneous} if the number of branches emanating from each node in the trellis diagram is not the same. the two-user binary adder channel is a multiple-access channel with two binary inputs,x_{1}andx_{2}, and one ternary output,y = x_{1} + x_{2}, where the addition is done in the real number field. the adder channel is synchronous if both encoders and the decoder maintain block (frame) synchronism. it is quasi-synchronous if the encoders do not start their blocks at the same time, but the decoder knows the position of each block. the difference between the starting times of the blocks is called the slippage. the channel is asynchronous if no block synchronism exists among the encoders and the decoder. some uniquely decodable code pairs(c_{1}, c_{2})are presented that can be used to transmit information reliably over the quasi-synchronous binary adder channel with two users. one of the codes is a nonhomogeneous trellis code, the other is a common block code. our code rates are better than deaett-wolf codes and are close to or equal to the asymptotic rates of kasami {em et al}. a method for calculating the rates of nonhomogeneous trellis codes is described. an algorithm for finding more uniquely decodable code pairs for the quasi-synchronous binary adder channel is formulated.
on the throughput, capacity, and stability regions of random multiple access. this paper studies finite-terminal random multiple access over the standard multipacket reception (mpr) channel. we characterize the relations among the throughput region of random multiple access, the capacity region of multiple access without code synchronization, and the stability region of aloha protocol. in the first part of the paper, we show that if the mpr channel is standard, the throughput region of random multiple access is coordinate convex. we then study the information capacity region of multiple access without code synchronization and feedback. inner and outer bounds to the capacity region are derived. we show that both the inner and the outer bounds converge asymptotically to the throughput region. in the second part of the paper, we study the stability region of finite-terminal aloha multiple access. for a class of packet arrival distributions, we demonstrate that the stationary distribution of the queues possesses positive and strong positive correlation properties, which consequently yield an outer bound to the stability region. we also show the major challenge in obtaining the closure of the stability region is due to the lack of sensitivity analysis results with respect to the transmission probabilities. particularly, if a conjectured "sensitivity monotonicity" property held for the stationary distribution of the queues, then equivalence between the closure of the stability region and the throughput region follows as a direct consequence, irrespective of the packet arrival distributions.
set reconciliation with nearly optimal communication complexity. we consider a fundamental problem that arises in the context of gossip protocols. specifically, we consider the problem of efficiently reconciling two similar sets held by different hosts while minimizing the communication complexity. we provide two surprisingly simple and efficient protocols that exhibit tractable computational complexity and nearly optimal communication complexity. these protocols can be adapted to work over a broadcast channel, allowing many clients to reconcile with one host based on a broadcasted signal.\note{we keep on bouncing back and forth on whether the ``a''''s are necessary. i like it better without, but it''s not a big deal.} thus, an arbitrary number of clients each of whose data differs from that of the host by no more than $n$ bits can be reconciled by a single broadcast of $o(n)$ bits, independent of the the number of clients and independent of the size of the data sets.
overcoming untuned radios in wireless networks with network coding. the drive toward the implementation and massive deployment of wireless sensor networks calls for ultralow-cost and low-power nodes. while the digital subsystems of the nodes are still following moore's law, there is no such trend regarding the performance of analog components. this work proposes a fully integrated architecture of both digital and analog components (including local oscillator) that offers significant reduction in cost, size, and overall power consumption of the node. even though such a radical architecture cannot offer the reliable tuning of standard designs, it is shown that by using random network coding, a dense network of such nodes can achieve throughput linear in the number of channels available for communication. moreover, the ratio of the achievable throughput of the untuned network to the throughput of a tuned network with perfect coordination is shown to be close to 1/e. this work uses network coding to leverage the fact that throughput equal to the max-flow in a graph is achievable even if the topology is not know a priori. however, the challenge here is finding the max-flow of the random graph corresponding to the network.
quantum signal propagation in depolarizing channels. quantum signal propagation in depolarizing channels nicholas pippenger abstract: let x be an unbiassed random bit, let y be a qubit whose mixed state depends on x, and let the qubit z be the result of passing y through a depolarizing channel, which replaces y with a completely random qubit with probability p. we measure the quantum mutual information between x and y by t(x; y) = s(x) + s(y) - s(x,y), where s(...) denotes von neumann''s entropy. (since x is a classical bit, the quantity t(x; y) agrees with holevo''s bound chi(x; y) to the classical mutual information between x and the outcome of any measurement of y.) we show that t(x;z) >= (1-p)^2 t(x;y). this generalizes an analogous bound for classical mutual information due to evans and schulman, and provides a new proof of their result.
the inequalities of quantum information theory. the inequalities of quantum information theory nicholas pippenger given an n-part quantum state, we consider the 2^n substates obtained by restricting attention to a subset of the parts. the entropies (in the sense of von neumann) of these substates may be regarded as a point, called the allocation of entropy, in a (2^n)-dimensional real vector space. we show that the topological closure of the set of allocations of entropy form a convex cone. we show that a set of inequalities due to lieb and ruskai characterize this cone when n is at most 3. we also consider the symmetric situation in which the entropy depends only on the number of parts in the substate. in this case, the topological closure of the set of allocations of entropy (in (n+1)-dimensional space) again form a convex cone, and we give inequalities characterizing this cone for all n.
entropy and expected acceptance counts for finite automata. entropy and expected acceptance counts for finite automata nicholas pippenger if a sequence of independent unbiased random bits is fed into a finite automaton, it is straightforward to calculate the expected number of acceptances among the first n prefixes of the sequence. this paper deals with the situation in which the random bits are neither independent nor unbiased, but are nearly so. we show that, under suitable assumptions concerning the automaton, if the the difference between the entropy of the first n bits and n converges to a constant exponentially fast, then the change in the expected number of acceptances also converges to a constant exponentially fast. we illustrate this result with a variety of examples in which numbers following the reciprocal distribution, which governs the significands of floating-point numbers, are recoded in the execution of various multiplication algorithms.
on a lower bound for the redundancy of reliable networks with noisy gates. we prove that a logarithmic redundancy factor is necessary for the reliable computation of the parity function by means of a networks with noisy gates. this result is the same as one claimed by dobrushin and ortyukov in 1977, but the proof they gave appears to be incorrect.
two families of optimal identifying codes in binary hamming spaces. a motivation for identifying codes comes from quality control in multiprocessor systems, that is, we are able to find faulty processors in such a system with the aid of these codes. in this paper we give a construction of two infinite families of optimal codes, which identify up to two malfunctioning processors in hamming spaces.
the multicast capacity of deterministic relay networks with no interference. the multicast capacity is determined for networks that have deterministic channels with broadcasting at the transmitters and no interference at the receivers. the multicast capacity is shown to have a cut-set interpretation. it is further shown that one cannot always layer channel and network coding in such networks. the proof of the latter result partially generalizes to discrete memoryless broadcast channels and is used to bound the common rate for problems where one achieves a cut bound on throughput.
statistical location detection with sensor networks. the paper develops a systematic framework for designing a stochastic location detection system with associated performance guarantees using a wireless sensor network. to detect the location of a mobile sensor, the system relies on rf-characteristics of the signal transmitted by the mobile sensor, as it is received by stationary sensors (clusterheads). location detection is posed as a hypothesis testing problem over a discretized space. large deviations results enable the characterization of the probability of error leading to a placement problem that maximizes an information-theoretic distance (chernoff distance) among all pairs of probability distributions of observations conditional on the sensor locations. the placement problem is shown to be np-hard and is formulated as a linear integer programming problem; yet, large instances can be solved efficiently by leveraging special-purpose algorithms from the theory of discrete facility location. the resultant optimal placement is shown to provide asymptotic guarantees on the probability of error in location detection under quite general conditions by minimizing an upper bound of the error-exponent. numerical results show that the proposed framework is computationally feasible and the resultant clusterhead placement performs near-optimal even with a small number of observation samples in a simulation environment.