Search

The idea of coded caching was introduced by Maddah-Ali and Niesen who demonstrated the advantages of coding in caching problems. To capture the essence of the problem, they introduced the $(N, K)$ canonical cache network in which $K$ users with independent caches of size $M$ request files from a server that has $N$ files. Among other results, the caching scheme and lower bounds proposed by them led to a characterization of the exact rate memory tradeoff when $M\geq \frac{N}{K}(K-1)$. These lower bounds along with the caching scheme proposed by Chen et al. led to a characterization of the exact rate memory tradeoff when $M\leq \frac{1}{K}$. In this paper we focus on small caches where $M\in \left[0,\frac{N}{K}\right]$ and derive new lower bounds. For the case when $\big\lceil\frac{K+1}{2}\big\rceil\leq N \leq K$ and $M\in \big[\frac{1}{K},\frac{N}{K(N-1)}\big]$, our lower bounds demonstrate that the caching scheme introduced by G{\'o}mez-Vilardeb{\'o} is optimal and thus extend the characterization of the exact rate memory tradeoff. For the case $1\leq N\leq \big\lceil\frac{K+1}{2}\big\rceil$, we show that the new lower bounds improve upon the previously known lower bounds., Comment: arXiv admin note: substantial text overlap with arXiv:2101.09785

The idea of coded caching for content distribution networks was introduced by Maddah-Ali and Niesen, who considered the canonical $(N, K)$ cache network in which a server with $N$ files satisfy the demands of $K$ users (equipped with independent caches of size $M$ each). Among other results, their work provided a characterization of the exact rate memory tradeoff for the problem when $M\geq\frac{N}{K}(K-1)$. In this paper, we improve this result for large caches with $M\geq \frac{N}{K}(K-2)$. For the case $\big\lceil\frac{K+1}{2}\big\rceil\leq N \leq K$, we propose a new coded caching scheme, and derive a matching lower bound to show that the proposed scheme is optimal. This extends the characterization of the exact rate memory tradeoff to the case $M\geq \frac{N}{K}\Big(K-2+\frac{(K-2+1/N)}{(K-1)}\Big)$. For the case $1\leq N\leq \big\lceil\frac{K+1}{2}\big\rceil$, we derive a new lower bound, which demonstrates that the scheme proposed by Yu et al. is optimal and thus extend the characterization of the exact rate memory tradeoff to the case $M\geq \frac{N}{K}(K-2)$.

Maddah-Ali and Niesen, in a seminal paper, introduced the notion of coded caching. The exact nature of the fundamental limits in this context has remained elusive even as several approximate characterizations have been found. A new optimal scheme for the (3, 3) cache network, operating at the memory rate pair (5/3, 1/2) for the demand where all the users request for distinct files, was introduced recently to partially address this issue. In this paper, an extension of this scheme to the general (K, K) cache network, operating at the memory rate pair (K-1-1/K, 1/(K-1)), is proposed. A new lower bound is also derived which demonstrates the optimality of the proposed scheme for the demand where all the users request for distinct files., Comment: 5 pages, 2 figures. To be presented in ISIT 2019

It is known a vector linear solution may exist if and only if the characteristic of the finite field belongs to a certain set of primes. But, can increasing the message dimension make a network vector linearly solvable over a larger set of characteristics? To the best of our knowledge, there exists no network in the literature which has a vector linear solution for some message dimension if and only if the characteristic of the finite field belongs to a set $P$, and for some other message dimension it has a vector linear solution over some finite field whose characteristic does not belong to $P$. We have found that by \textit{increasing} the message dimension just by $1$, the set of characteristics over which a vector linear solution exists may get arbitrarily larger. However, somewhat surprisingly, we have also found that by \textit{decreasing} the message dimension just by $1$, the set of characteristics over which a vector linear solution exists may get arbitrarily larger. As a consequence of these finding, we prove two more results: (i) rings may be superior to finite fields in terms of achieving a scalar linear solution over a lesser sized alphabet, (ii) existences of $m_1$ and $m_2$ dimensional vector linear solutions guarantees the existence of an $(m_1 + m_2)$-dimensional vector linear solution only if the $m_1$ and $m_2$ dimensional vector linear solutions exist over the same finite field., Comment: Submitted to IEEE Transactions on Information Theory

It is known that for any finite/co-finite set of primes there exists a network which has a rate $1$ solution if and only if the characteristic of the finite field belongs to the given set. We generalize this result to show that for any positive rational number $k/n$, and for any given finite/co-finite set of primes, there exists a network which has a rate $k/n$ fractional linear network coding solution if and only if the characteristic of the finite field belongs to the given set. For this purpose we construct two networks: $\mathcal{N}_1$ and $\mathcal{N}_2$; the network $\mathcal{N}_1$ has a $k/n$ fractional linear network coding solution if and only if the characteristic of the finite field belongs to the given finite set of primes, and the network $\mathcal{N}_2$ has a $k/n$ fractional linear network coding solution if and only if the characteristic of the finite field belongs to the given co-finite set of primes. Recently, a method has been introduced where characteristic-dependent linear rank inequalities are produced from networks whose linear coding capacity depends on the characteristic of the finite field. By employing this method on the networks $\mathcal{N}_1$ and $\mathcal{N}_2$, we construct two classes of characteristic-dependent linear rank inequalities. For any given set of primes, the first class contains an inequality which holds if the characteristic of the finite field does not belong to the given set of primes but may not hold otherwise; the second class contains an inequality which holds if the characteristic of the finite field belongs to the given set of primes but may not hold otherwise. We then use these inequalities to obtain an upper-bound on the linear coding capacity of $\mathcal{N}_1$ and $\mathcal{N}_2$., Comment: arXiv admin note: text overlap with arXiv:1610.08004

Sum-networks are networks where all the terminals demand the sum of the symbols generated at the sources. It has been shown that for any finite set/co-finite set of prime numbers, there exists a sum-network which has a vector linear solution if and only if the characteristic of the finite field belongs to the given set. It has also been shown that for any positive rational number $k/n$, there exists a sum-network which has capacity equal to $k/n$. It is a natural question whether, for any positive rational number $k/n$, and for any finite set/co-finite set of primes $\{p_1,p_2,\ldots,p_l\}$, there exists a sum-network which has a capacity achieving rate $k/n$ fractional linear network coding solution if and only if the characteristic of the finite field belongs to the given set. We show that indeed there exists such a sum-network by constructing such a sum-network.

It is known that there exists a multiple-unicast network which has a rate $1$ linear network coding solution if and only if the characteristic of the finite field belongs to a given finite or co-finite set of primes. In this paper, we show that for any non-zero positive rational number $\frac{k}{n}$, there exists a multiple-unicast network which has a rate $\frac{k}{n}$ fractional linear network coding solution if and only if the characteristic of the finite field belongs to a given finite or co-finite set of primes.

It is known that the Fano network has a vector linear solution if and only if the characteristic of the finite field is $2$; and the non-Fano network has a vector linear solution if and only if the characteristic of the finite field is not $2$. Using these properties of Fano and non-Fano networks it has been shown that linear network coding is insufficient. In this paper we generalize the properties of Fano and non-Fano networks. Specifically, by adding more nodes and edges to the Fano network, we construct a network which has a vector linear solution for any vector dimension if and only if the characteristic of the finite field belongs to an arbitrary given set of primes $\{p_1,p_2,\ldots,p_l\}$. Similarly, by adding more nodes and edges to the non-Fano network, we construct a network which has a vector linear solution for any vector dimension if and only if the characteristic of the finite field does not belong to an arbitrary given set of primes $\{p_1,p_2,\ldots,p_l\}$.

Recently designed cross-layer contention based synchronous MAC protocols like the PRMAC protocol, for wireless sensor networks (WSNs) enable a node to schedule multi-hop transmission of multiple data packets in a cycle. However, these systems accommodate both the request-to-send data process and the confirmation-to-send data process in the same data transmission scheduling window (i.e. data window). This reduces the length of the multi-hop flow setup in the data window. In a multi-hop scenario, this degrades both the packet delivery ratio (PDR) and the end-to-end transmission delay (E2ETD). In this paper, we propose a cross-layer contention based synchronous MAC protocol, which accommodates the request-to-send data process in the data window and the confirmation-to-send data process in the sleep window for increased efficiency. We evaluate our proposed protocol through ns-2.35 simulations and compare its performance with the PRMAC protocol. Results suggest that in multi-hop scenario, proposed protocol outperforms PRMAC both in terms of the E2ETD and the packet delivery ratio (PDR)., Comment: Accepted to TENCON 2016

It is known that there exists a network, called as the M-network, which is not scalar linearly solvable but has a vector linear solution for message dimension two. Recently, a generalization of this result has been presented where it has been shown that for any integer $m\geq 2$, there exists a network which has a $(m,m)$ vector linear solution, but does not have a $(w,w)$ vector linear solution for $w

It is known that there exists a network which does not have a scalar linear solution over any finite field but has a vector linear solution when message dimension is $2$ [3]. It is not known whether this result can be generalized for an arbitrary message dimension. In this paper, we show that there exists a network which admits an $m$ dimensional vector linear solution, where $m$ is a positive integer greater than or equal to $2$, but does not have a vector linear solution over any finite field when the message dimension is less than $m$.

We consider directed acyclic networks with multiple sources and multiple terminals where each source generates one i.i.d. random process over an abelian group and all the terminals want to recover the sum of these random processes. The different source processes are assumed to be independent. The solvability of such networks has been considered in some previous works. In this paper we investigate on the capacity of such networks, referred as {\it sum-networks}, and present some bounds in terms of min-cut, and the numbers of sources and terminals., Comment: Revised version

A directed acyclic network is considered where all the terminals need to recover the sum of the symbols generated at all the sources. We call such a network a sum-network. It is shown that there exists a solvably (and linear solvably) equivalent sum-network for any multiple-unicast network, and thus for any directed acyclic communication network. It is also shown that there exists a linear solvably equivalent multiple-unicast network for every sum-network. It is shown that for any set of polynomials having integer coefficients, there exists a sum-network which is scalar linear solvable over a finite field F if and only if the polynomials have a common root in F. For any finite or cofinite set of prime numbers, a network is constructed which has a vector linear solution of any length if and only if the characteristic of the alphabet field is in the given set. The insufficiency of linear network coding and unachievability of the network coding capacity are proved for sum-networks by using similar known results for communication networks. Under fractional vector linear network coding, a sum-network and its reverse network are shown to be equivalent. However, under non-linear coding, it is shown that there exists a solvable sum-network whose reverse network is not solvable., Comment: Accepted to IEEE Transactions on Information Theory

We consider directed acyclic {\em sum-networks} with $m$ sources and $n$ terminals where the sources generate symbols from an arbitrary alphabet field $F$, and the terminals need to recover the sum of the sources over $F$. We show that for any co-finite set of primes, there is a sum-network which is solvable only over fields of characteristics belonging to that set. We further construct a sum-network where a scalar solution exists over all fields other than the binary field $F_2$. We also show that a sum-network is solvable over a field if and only if its reverse network is solvable over the same field.

We consider the problem of communicating the sum of $m$ sources to $n$ terminals in a directed acyclic network. Recently, it was shown that for a network of unit capacity links with either $m=2$ or $n=2$, the sum of the sources can be communicated to the terminals if and only if every source-terminal pair is connected in the network. We show in this paper that for any finite set of primes, there exists a network where the sum of the sources can be communicated to the terminals only over finite fields of characteristic belonging to that set. As a corollary, this gives networks where the sum can not be communicated over any finite field even though every source is connected to every terminal., Comment: 5 pages, 3 figures