We study the problem of leaky private information retrieval (L-PIR), where the amount of privacy leakage is measured by the pure differential privacy parameter, referred to as the leakage ratio exponent. Unlike the previous L-PIR proposed by Samy et al., which is merely a re-allocation of the clean (low-cost) retrieval pattern within the generalized TSC family, we show that the active pure-DP constraints couple adjacent Hamming-weight layers of the random key, which reduces the optimization to a layered problem whose optimum is geometric across these layers. As a result, only cyclic permutations are needed without loss of optimality, and lower-Hamming weight keys should be assigned higher probabilities. This new scheme provides a significant improvement, leading to anO(logK) leakage ratio exponent with fixed download costD, in contrast to the previous art that only achieves a Θ(K) exponent, whereKis the number of messages.

This work presents an algorithmic framework that uses linear programming to construct addition-based Private Information Retrieval (AB-PIR) schemes, where retrieval is performed by downloading only linear combinations of message symbols with coefficients set to 0 or 1. The AB-PIR schemes generalize several existing capacity-achieving PIR schemes and are of practical interest because they use only addition operation-savoiding multiplication and other complex operations-and are compatible with any finite field, including binary. Our framework broadens the search space to include all feasible solutions and can be used to construct optimal AB-PIR schemes for the entire range of problem parameters, including the number of servers, the total number of messages, and the number of messages that need to be retrieved. The framework enables us to identify schemes that outperform the previously proposed PIR schemes in certain cases and, in other cases, achieve performance on par with the best-known AB-PIR solutions. Additionally, the schemes generated by our framework can be integrated into existing solutions for several related PIR scenarios, improving their overall performance.

We study the problem of leaky private information retrieval (L- PIR), where the amount of privacy leakage is measured by the pure differential privacy parameter, referred to as the leakage ratio exponent. Unlike the previous L-PIR scheme proposed by Samy et al., which only adjusted the probability allocation to the clean (low-cost) retrieval pattern, we optimized the probabilities assigned to all the retrieval patterns jointly. It is demonstrated that the optimal probability distribution of the retrieval pattern is quite sophisticated and has a layered structure: the retrieval associated with the random key values of lower Hamming weights should be assigned higher probabilities. This new scheme provides a significant improvement, leading to an$O(\log K)$leakage ratio exponent with fixed download cost$D$and number of servers$N$, in contrast to the previous art that only achieves a$\theta(K)$exponent, where$K$is the number of messages.

Maximum Distance Profile (MDP) convolutional codes are an important class of channel codes due to their maximal delay-constrained error correction capabilities. The design of MDP codes has attracted significant attention from the research community. However, only limited attention was given to addressing the complexity of encoding and decoding operations. This paper aims to reduce encoding complexity by constructing partial unit-memory MDP codes with structured and sparse generator matrices. In particular, we present a matrix completion framework that extends a structured superregular matrix (e.g., Cauchy) over a small field to a sparse sliding generator matrix of an MDP code. We show that the proposed construction can reduce the encoding complexity compared to the current state-of-the-art MDP code designs.

The Singleton bound provides a fundamental limit on the maximum possible size of an error-correcting code of a given length and distance. However, recent work by Zhang et. al. [IEEE Trans. Comm., Dec. 2023] showed that in the context of the wiretap multipath network when the adversary has limited knowledge about the codewords and a vanishing probability of decoding error is permitted, a rate higher than the Singleton bound is achievable. Their results, however, are confined to an ideal setting where the adversary is allowed to behave non-causally. Motivated by real-world scenarios, this work considers communication over a wiretap multipath network in the presence of a causal adversary (i.e., the adversary which is only allowed to use the observations up to the current time slot to decide the current jamming strategy) and in the presence of passive feedback from the receiver to the transmitter. We characterize both the capacity and secrecy capacity of the wiretap multipath network, either with or without passive feedback. We observe that in comparison to the non-causal and non-feedback setting, the capacity and secrecy capacity can be strictly higher for a wide variety of parameters, demonstrating the benefits of causality and feedback.

Switching, routing, and security functions are the backbone of packet processing networks. Fast and efficient processing of packets requires maintaining the state information for many transient network connections. In particular, modern stateful firewalls, security monitoring devices, and Software-Defined Networking (SDN) dataplanes require maintaining state-ful flow tables. These flow tables often grow much larger than can fit on-chip, requiring caching to maintain performance.This paper focuses on improving caching efficiency, an important architectural component of the packet processing data planes. We present a novel predictive approach (Flow Correlator) to network flow table cache management by adapting the Hashed Perceptron binary classifier to improve the reliability and performance of the data plane caching. We also discovered an iterative approach to feature selection and ranking while adapting the Hashed Perceptron mechanism to network flow table cache management.Through extensive experimentation, we demonstrate improved caching efficiency of the proposed Flow Correlator mechanism. We also rigorously validate the performance and generic applicability of our technique across real-world datasets.

We consider the problem of secure distributed ma-trix multiplication in which a user wishes to compute the product of two matrices with the assistance of honest but curious servers. We show how to construct polynomial schemes for the outer product partitioning which take advantage of the user's ability to precompute, and provide bounds for our technique. We show that precomputation allows for a reduction in the order of the time complexity for the cases where the number of colluding servers is a fixed percentage of the number of servers. Furthermore, with precomputation, any percentage (less than 100%) of collusions can be tolerated, compared to the upper limit of 50% for the case without precomputation.

This paper presents new solutions for Private Information Retrieval (PIR) with side information. This problem is motivated by PIR settings in which a client has side information about the data held by the servers and would like to leverage this information in order to improve the download rate. The problem of PIR with side information has been the subject of several recent studies that presented achievability schemes as well as converses for both multi -server and single-server settings. However, the solutions for the multi-server settings adapted from the solutions for the single-server setting in a rather straightforward manner, relying on the concept of super-messages. Such solutions require an exponential degree of sub-packetization (in terms of the number of messages). This paper makes the following contributions. First, we revisit the PIR problem with side information and present a new approach to leverage side information in the context of PIR. The key idea of our approach is a randomized algorithm to determine the linear combinations of the sub-packets that need to be recovered from each server. In addition, our approach takes advantage of the fact that the identity of the side information messages does not need to be kept private, and, as a result, the information retrieval scheme does not need to be symmetric. Second, we present schemes for PIR with side information that achieve a higher rate than previously proposed solutions and require a significantly lower degree of sub-packetization (linear in the number of servers). Our scheme not only achieves the highest known download rate for the problem at hand but also invalidates a previously claimed converse bound on the maximum achievable download rate.

This paper focuses on the study of the minimum possible alphabet size of codes in a generalized setting where the coding scheme is required to handle a pre-specified set of erasure or error patterns, naturally represented by a hypergraph. The need for such codes arises in many settings of practical interest, including wireless communication and flash memory systems. In many such settings, a smaller field size is achievable than that offered by MDS and other standard codes. We establish a connection between the minimum alphabet size of codes in this generalized setting and the combinatorial properties of the hypergraph that represents the pre-specified collection of erasure or error patterns. We also establish connections between error and erasure correcting codes in our generalized setting. Finally, we consider a variation of the problem that allows a small probability of decoding error and relate it to an approximate version of hypergraph coloring.

Maximum distance separable (MDS) codes are often considered to have the optimal error correction capability against malicious adversaries because they achieve the Singleton bound in terms of the rate-distance tradeoff. However, by allowing a vanishing probability of decoding error and considering an adversary with limited knowledge, it is interesting to understand whether a rate higher than the Singleton bound is achievable, and if so, what the optimal rate is. To answer these questions, we instantiate the aforementioned problem as a communication problem where the transmission medium is a wiretap multipath network that consists of multiple parallel links. A malicious adversary is able to eavesdrop on a subset of links, and also jam on a potentially overlapping subset of links. The primary objective is to ensure the communication is robust to adversarial jamming; additionally, another goal is to guarantee that the communication is information-theoretically secure with respect to the adversary. We present a complete characterization of both capacity and secrecy capacity as functions of the number of links that can be eavesdropped and/or jammed. Our achievability schemes are computationally efficient, and rely on a non-trivial combination of MDS codes and a pairwise hashing scheme.

Group testing is one of the fundamental problems in coding theory and combinatorics in which one is to identify a subset of contaminated items from a given ground set. There has been renewed interest in group testing recently due to its applications in diagnostic virology, including pool testing for the novel coronavirus. The majority of existing works on group testing focus on the uniform setting in which any subset of size d from a ground set V of size n is potentially contaminated.In this work, we consider a generalized version of group testing with an arbitrary set-system of potentially contaminated sets. The generalized problem is characterized by a hypergraph H = (V, E), where V represents the ground set and edges e ∈ E represent potentially contaminated sets. The problem of generalized group testing is motivated by practical settings in which not all subsets of a given size d may be potentially contaminated, rather, due to social dynamics, geographical limitations, or other considerations, there exist subsets that can be readily ruled out. For example, in the context of pool testing, the edge set E may consist of families, work teams, or students in a classroom, i.e., subsets likely to be mutually contaminated. The goal in studying the generalized setting is to leverage the additional knowledge characterized by H = (V, E) to reduce the number of tests.The paper considers both adaptive and non-adaptive group testing and makes the following contributions. First, for the non-adaptive setting, we show that finding an optimal solution for the generalized version of group testing is NP-hard. For this setting, we present a solution that requires O(d log |E|) tests, where d is the maximum size of a set e ∈ E. Our solutions generalize those given for the traditional setting and are shown to be of order-optimal size O(log |E|) for hypergraphs with edges that have “large” symmetric differences. For the adaptive setting, when edges in E are of size exactly d, we present a solution of size O(log |E| + d log2d) that comes close to the lower bound of $\Omega (\log |E| + d)$

This paper introduces the problem of Private Information Retrieval with Reusable and Single-use Side Information (PIR-RSSI). In this problem, one or more remote servers store identical copies of a set of K messages, and there is a user that initially knows M of these messages, and wants to privately retrieve one other message from the set of K messages. The objective is to design a retrieval scheme in which the user downloads the minimum amount of information from the server(s) while the identity of the message wanted by the user and the identities of an M1-subset of the M messages known by the user (referred to as reusable side information) are protected, but the identities of the remaining M2:=M−M1messages known by the user (referred to as single-use side information) do not need to be protected. The PIR-RSSI problem reduces to the classical Private Information Retrieval (PIR) problem when M1=M2= 0, and reduces to the problem of PIR with Private Side Information or PIR with Side Information when M1≥ 1, M2= 0 or M1= 0, M2≥ 1, respectively. In this work, we focus on the single-server setting of the PIR-RSSI problem. We characterize the capacity of this setting for the cases of M1= 1, M2≥ 1 and M1≥ 1, M2= 1, where the capacity is defined as the maximum achievable download rate over all PIR-RSSI schemes. Our results show that for sufficiently small values of K, both the single-use and reusable side information messages can help in reducing the download cost; and for larger values of K, only the single-use side information messages can help in reducing the download cost.

This paper considers the problem of single-server Individually-Private Information Retrieval with side information (IPIR). In this problem, there is a remote server that stores a dataset of K messages, and there is a user that initially knows M of these messages, and wants to retrieve D other messages belonging to the dataset. The goal of the user is to retrieve the D desired messages by downloading the minimum amount of information from the server while revealing no information about whether an individual message is one of the D desired messages. In this work, we focus on linear IPIR schemes, i.e., the IPIR schemes in which the user downloads only linear combinations of the original messages from the server. We prove a converse bound on the download rate of any linear IPIR scheme for all K, D, M, and show the achievability of this bound for all K, D, M satisfying a certain divisibility condition. Our results characterize the linear capacity of IPIR, which is defined as the maximum achievable download rate over all linear IPIR schemes, for a wide range of values of K, D, M.

This paper introduces the problem of Private Linear Transformation (PLT) which generalizes the problems of private information retrieval and private linear computation. The PLT problem includes one or more remote server(s) storing (identical copies of)$K$messages and a user who wants to compute$L$independent linear combinations of a$D$-subset of messages. The objective of the user is to perform the computation by downloading minimum possible amount of information from the server(s), while protecting the identities of the$D$messages required for the computation. In this work, we focus on the single-server setting of the PLT problem when the identities of the$D$messages required for the computation must be protected jointly. We consider two different models, depending on whether the coefficient matrix of the required$L$linear combinations generates a Maximum Distance Separable (MDS) code. We prove that the capacity for both models is given by$L/(K-D+L)$, where the capacity is defined as the supremum of all achievable download rates. Our converse proofs are based on linear-algebraic and information-theoretic arguments. For each model, we also present an achievability scheme that relies on MDS codes.

Packet classification methods rely upon matching packet content/header against pre-defined rules, which are generated by network applications and their configurations. With the rapid development of network technology and the fast-growing network applications, users seek more enhanced, secure, and diverse network services. Hence it becomes critical to improve the performance of arbitrary matching operations. This article presents SIMD-Matcher, an efficient Single Instruction Multiple Data (SIMD) and cache-friendly arbitrary matching framework. To further improve the arbitrary matching performance, SIMD-Matcher adopts a trie node with a fixed high fanout and a varying span for each node depending on the data distribution. The trie node layout leverages cache and modern processor features such as SIMD instructions. To support arbitrary matching, we first interpret arbitrary rules into three fields: value, mask, and priority. Second, to support insertion of randomly positioned wildcards to arbitrary rules, we propose the SIMD-Matcher extraction algorithm to process the wildcard bits. Third, we add an array of wildcard entries to the leaf entries, which store the wildcard rules and guarantee the correctness of matching results. Experiments show that SIMD-Matcher outperforms GenMatcher under large-scale ruleset and key set, in terms of search time, insert time, and memory cost. Specifically with 5M rules, our method achieves a 2.7X speedup on search time, and the insertion time takes \( ~\sim \!\! 7.3 \) seconds, gaining a 1.38X speedup; meanwhile, the memory cost reduction is up to 6.17X.

We study the relation betweenlatencyandalphabet sizein the context of Multicast Network Coding. Given a graph$G = (V, E)$representing a communication network, a subset$S \subseteq V$of sources, each of which initially holds a set of information messages, and a set$T \subseteq V$of terminals; we consider the problem in which one wishes to design a communication scheme that eventually allows all terminals to obtain all the messages held by the sources. In this study we assume that communication is performed in rounds, where in each round each network node may transmit a single (possibly encoded) information packet on any of its outgoing edges. The objective is to minimize the communication latency, i.e., number of communication rounds needed until all terminals have all the messages of the source nodes. For sufficiently large alphabet sizes (i.e., large block length, packet sizes), it is known that traditional linear multicast network coding techniques (such as random linear network coding) minimize latency. In this work we seek to study the task of minimizing latency in the setting of limited alphabet sizes (i.e., finite block length), and alternatively, the task of minimizing the alphabet size in the setting of bounded latency. We focus on the establishing the computation complexity of the problem and present several intractability results. In particular, through reductive arguments, we prove that it is NP-hard to (i) approximate (and in particular to determine) the minimum alphabet size given a latency constraint; (ii) approximate (and in particular to determine) the minimum latency of communication schemes in the setting of limited alphabet sizes.

In this paper, we introduce the problem of Private Linear Transformation (PLT). This problem includes a single (or multiple) remote server(s) storing (identical copies of)$K$messages and a user that wants to compute$L$linear combinations of a$D$-subset of these messages by downloading the minimum amount of information from the server(s) while protecting the privacy of the entire set of$D$messages. This problem generalizes the private information retrieval and private linear computation problems. In this work, we focus on the single-server case. For the setting in which the coefficient matrix of the required$L$linear combinations generates a Maximum Distance Separable (MDS) code, we characterize the capacity for all parameters$K, D, L$, where the capacity is defined as the supremum of all achievable download rates. In addition, we present lower and/or upper bounds on the capacity for the settings with non-MDS coefficient matrices and the settings with a prior side information.

This paper considers the single-server Private Linear Transformation (PLT) problem when individual privacy is required. In this problem, there is a user that wishes to obtain$L$linear combinations of a D-subset of messages belonging to a dataset of$K$messages stored on a single server. The goal is to minimize the download cost while keeping the identity of every message required for the computation individually private. We focus on the setting in which the matrix of coefficients pertaining to the required linear combinations is the generator matrix of a maximum distance separable code. We establish lower and upper bounds on the capacity of PLT with individual privacy, where the capacity is defined as the supremum of all achievable download rates. We show that our bounds are tight under certain divisibility conditions. In addition, we present lower bounds on the capacity of the settings in which the user has a prior side information about a subset of messages.

This paper focuses on error-correcting codes that can handle a predefined set of specific error patterns. The need for such codes arises in many settings of practical interest, including wireless communication and flash memory systems. In many such settings, a smaller field size is achievable than that offered by MDS and other standard codes. We establish a connection between the minimum alphabet size for this generalized setting and the combinatorial properties of a hypergraph that represents the prespecified collection of error patterns. We also show a connection between error and erasure correcting codes in this specialized setting. This allows us to establish bounds on the minimum alphabet size and show an advantage of non-linear codes over linear codes in a generalized setting. We also consider a variation of the problem which allows a small probability of decoding error and relate it to an approximate version of the hypergraph coloring problem.

This paper considers the problem of single-server Individually-Private Information Retrieval (IPIR). In this problem, a user wants to retrieve D messages belonging to a dataset of K messages stored on a single server. Initially, the user knows M other messages belonging to the dataset as side information, where the identities of these M messages are unknown to the server. The goal is to minimize the total amount of information that the user must download from the server while keeping the identity of each of the D desired messages individually private, i.e., the identity of every individual message wanted by the user must be protected. The capacity of IPIR, which is defined as the supremum of all achievable download rates, was previously characterized for D = 2, M = 1. However, the capacity was left open for all other values of D, M. In this work, we present a technique for the proof of converse, based on a novel combinatorial approach. Using this technique, we establish an upper bound on the capacity of IPIR for D = 2, M = 2. For this setting, we also propose a new IPIR scheme—based on a probabilistic partitioning of the messages, that achieves the capacity upper bound. We believe that our approach can be employed for proving the converse and designing optimal schemes for the general cases of the problem.

The paper presents techniques for analyzing the expected download time in distributed storage systems that employ systematic availability codes. These codes provide access to hot data through the systematic server containing the object and multiple recovery groups. When a request for an object is received, it can be replicated (forked) to the systematic server and all recovery groups. We first consider the low-traffic regime and present the close-form expression for the download time. By comparison across systems with availability, maximum distance separable (MDS), and replication codes, we demonstrate that availability codes can reduce download time in some settings but are not always optimal. In the high-traffic regime, the system contains multiple inter-dependent Fork-Join queues, making exact analysis intractable. Accordingly, we present upper and lower bounds on the download time, and an M/G/1 queue approximation for several cases of interest. Via extensive numerical simulations, we evaluate our bounds and demonstrate that the M/G/1 queue approximation has a high degree of accuracy.

The index coding problem includes a server, a group of clients, and a set of data chunks. While each client wants a subset of the data chunks and already has another subset as its side information, the server transmits some (uncoded or coded) chunks to the clients over a noiseless broadcast channel. The objective of the problem is to satisfy the demands of all clients with the minimum number of transmissions. This paper investigates the index coding setting from a game-theoretical perspective. We consider selfish clients, where each selfish client has private side information and a private valuation of each data chunk it wants. In this context, our objectives are following: 1) to motivate each selfish client to reveal the correct side information and true valuation of each data chunk it wants; 2) to maximize the social welfare, i.e., the total valuation of the data chunks recovered by the clients minus the total cost incurred by the transmissions from the server. Our main contribution is to jointly develop coding and incentive schemes for achieving the first objective perfectly and achieving the second objective optimally or approximately with guaranteed approximation ratios (potentially within some restricted sets of coding matrices).

We study the role of coded side information in single-server Private Information Retrieval (PIR). An instance of the single-server PIR problem includes a server that stores a database of K independently and uniformly distributed messages, and a user who wants to retrieve one of these messages from the server. We consider settings in which the user initially has access to a coded side information which includes a linear combination of a subset of M messages in the database. We assume that the identities of the M messages that form the support set of the coded side information as well as the coding coefficients are initially unknown to the server. We consider two different models, depending on whether the support set of the coded side information includes the requested message or not. We also consider the following two privacy requirements: (i) the identities of both the demand and the support set of the coded side information need to be protected, or (ii) only the identity of the demand needs to be protected. For each model and for each of the privacy requirements, we consider the problem of designing a protocol for generating the user's query and the server's answer that enables the user to decode the message they need while satisfying the privacy requirement. We characterize the (scalar-linear) capacity of each setting, defined as the ratio of the number of information bits in a message to the minimum number of information bits downloaded from the server over all (scalar-linear) protocols that satisfy the privacy condition. Our converse proofs rely on new information-theoretic arguments-tailored to the setting of single-server PIR and different from the commonly-used techniques in multi-server PIR settings. We also present novel capacity-achieving scalar-linear protocols for each of the settings being considered.

A Maximum Distance Separable code over an alphabet F is defined via an encoding function C : Fk→ Fnthat allows to retrieve a message m ∈ Fkfrom the codeword C(m) even after erasing any n - k of its symbols. The minimum possible alphabet size of general (non-linear) MDS codes for given parameters n and k is unknown and forms one of the central open problems in coding theory. The paper initiates the study of the alphabet size of codes in a generalized setting where the coding scheme is required to handle a pre-specified subset of all possible erasure patterns, naturally represented by an n-vertex k-uniform hypergraph. We relate the minimum possible alphabet size of such codes to the strong chromatic number of the hypergraph and analyze the tightness of the obtained bounds for both the linear and non-linear settings. We further consider variations of the problem which allow a small probability of decoding error.

This paper considers the problem of single-server Private Computation (PC) in the presence of Side Information (SI). In this problem, there is a server that stores K i.i.d. messages, and a user who has a subset of M uncoded messages or a coded linear combination of them as side information, where the identities of these messages are unknown to the server. The user wants to privately compute a linear combination of a subset of D other messages by downloading information from the server, where the identities of these messages must be kept private individually or jointly. For each setting, we define the capacity as the supremum of all achievable download rates.We characterize the capacity of both PC with coded and un-coded SI when individual privacy is required, for all K, M, D. Our results indicate that both settings have the same capacity. In addition, we establish a non-trivial lower bound on the capacity of PC with coded SI when joint privacy is required, for a range of parameters K, M, D. This lower bound is the same as the lower bound we previously established on the capacity of PC with uncoded SI when joint privacy is required.

We propose a novel technique for constructing a graph representation of a code through which we establish a significant connection between the service rate problem and the well-known fractional matching problem. Using this connection, we show that the service capacity of a coded storage system equals the fractional matching number in the graph representation of the code, and thus is lower bounded and upper bounded by the matching number and the vertex cover number, respectively. This is of great interest because if the graph representation of a code is bipartite, then the derived upper and lower bounds are equal, and we obtain the capacity. Leveraging this result, we characterize the service capacity of the binary simplex code whose graph representation is bipartite. Moreover, we show that the service rate problem can be viewed as a generalization of the multiset primitive batch codes problem.

A major concern in cloud/edge storage systems is serving a large number of users simultaneously. The service rate region is introduced recently as an important performance metric for coded distributed systems, which is defined as the set of all data access requests that can be simultaneously handled by the system. This paper studies the problem of designing a coded distributed storage system storing k files where a desired service rate region $\mathcal{R}$ of the system is given and the goal is 1) to determine the minimum number of storage nodes $n(\mathcal{R})$ for serving all demand vectors inside the set $\mathcal{R}$ and 2) to design the most storage-efficient redundancy scheme with the service rate region covering the set $\mathcal{R}$. Towards this goal, we propose three general lower bounds for $n(\mathcal{R})$. Also, for k = 2, we characterize $n(\mathcal{R})$, i.e., we show that the proposed lower bounds are tight, via designing a novel storage-efficient redundancy scheme with $n(\mathcal{R})$ storage nodes and service rate region covering $\mathcal{R}$.

We design p-reconstructible μ-secure [n, k] erasure coding schemes (0 ≤ μ3/4.

We study the problem of Private Information Retrieval (PIR) in the presence of prior side information. The problem setup includes a database of K independent messages possibly replicated on several servers, and a user that needs to retrieve one of these messages. In addition, the user has some prior side information in the form of a subset of M messages, not containing the desired message and unknown to the servers. This problem is motivated by practical settings in which the user can obtain side information opportunistically from other users or has previously downloaded some messages using classical PIR schemes. The objective of the user is to retrieve the required message with downloading minimum amount of data from the servers while achieving information-theoretic privacy in one of the following two scenarios: (i) the user wants to protect jointly the identities of the demand and the side information; (ii) the user wants to protect only the identity of the demand, but not necessarily the side information. To highlight the role of side information, we focus first on the case of a single server (single database). In the first scenario, we prove that the minimum download cost is K - M messages, and in the second scenario it is [K/(M + 1)] messages, which should be compared to K messages-the minimum download cost in the case of no side information. Then, we extend some of our results to the case of the database replicated on multiple servers. Our proof techniques relate PIR with side information to the index coding problem. We leverage this connection to prove converse results, as well as to design achievability schemes.

We consider a multi-user variant of the private information retrieval problem described as follows. Suppose there are D users, each of which wants to privately retrieve a distinct message from a server with the help of a trusted agent. We assume that the agent has a subset of M messages whose indices are unknown to the server. The goal of the agent is to collectively retrieve the users' requests from the server. For this problem, we introduce the notion of individual-privacy - the agent is required to protect the privacy only for each individual user (but may leak some correlations among user requests). We refer to this problem as Individually-Private Information Retrieval with Side Information (IPIR-SI).We first establish a lower bound on the capacity, which is defined as the maximum achievable download rate, of the IPIR-SI problem by presenting a novel achievability protocol. Next, we characterize the capacity of IPIR-SI problem for M = 1 and D = 2. In the process of characterizing the capacity for arbitrary M and D we present a novel combinatorial conjecture, that may be of independent interest.

We study the problem of single-server single-message Private Information Retrieval with Private Coded Side Information (PIR-PCSI). In this problem, there is a server that stores a database, and a user who knows a random linear combination of a random subset of messages in the database. The number of messages contributing to the user's side information is known to the server a priori, whereas the indices and the coefficients of these messages are unknown to the server a priori. The user wants to retrieve a message from the server, while protecting the identities of both the demand message and the side information messages. Depending on whether the demand is part of the coded side information or not, we consider two different models for the problem. For the model in which the demand does not contribute to the side information, we prove a lower bound on the minimum download cost for all (linear and non-linear) PIR schemes; and for the model wherein the demand is one of the messages contributing to the side information, we prove a lower bound for all scalar-linear PIR protocols. In addition, we propose novel PIR protocols that achieve these lower bounds.

This paper considers the problem of single-server Private Computation wit Side Information (PC-SI). In this problem, there is a user that initially has a subset of M messages from a database stored on a single server, where the identities of the side information messages are initially unknown to the server. The user wishes to compute a linear combination of a subset of D messages (disjoint from the set of side information messages) while protecting the identities of the messages in the demanded linear combination. The objective of the user is to minimize the download cost, which is defined as the total amount of information that the user downloads from the server.We establish a lower bound on the capacity of the PC-SI problem, where the capacity is defined as the supremum of all achievable download rates. The proof relies on a novel achievability scheme which combines together the ideas of the interference alignment and the Partition and Code scheme previously introduced for private information retrieval with side information. In addition, for the case of M = 1 and D = 2, we prove the tightness of the rate achievable by the proposed scheme, when we restrict ourselves to the scalar-linear PC-SI schemes. The proof of converse is based on a combination of new algebraic and information-theoretic arguments.

In many practical settings, the user needs to retrieve information messages from a server in a periodic manner, over multiple rounds of communication. The messages are retrieved one at a time and the identity of future requests are not known to the server. In this paper, we focus on the private information retrieval protocols that ensure that the identities of all the messages retrieved from the server are protected. This scenario can occur in practical settings such as periodic content download from text and multimedia repositories. We refer to this problem of minimizing the rate of data download as online private information retrieval problem.Following the previous line of work by Kadhe et al. we assume that the user knows a subset of M messages in the database as side information. The identities of these M messages are initially unknown to the server. Focusing on scalar-linear settings, we characterize the per-round capacity, i.e., the maximum achievable download rate at each round. In particular, we show that for the setting with K messages stored at the server, the per-round capacity of the scalar-linear setting is C1= (M + 1)/K for round i = 1 and Ci= (2i -1(M + 1))/KM for round i ≥ 2, provided that K/(M + 1) is a power of 2. The key idea≥of our achievability scheme is to combine the data downloaded during the current round and the previous rounds with the original side information messages and use the resulting data as side information for the subsequent rounds.

Private Information Retrieval (PIR) problem has recently attracted a significant interest in the information-theory community. In this problem, a user wants to privately download one or more messages belonging to a database with copies stored on a single or multiple remote servers. In the single server scenario, the user must have prior side information, i.e., a subset of messages unknown to the server, to be able to privately retrieve the required messages in an efficient way.In the last decade, there has also been a significant interest in Locally Recoverable Codes (LRCs), a class of storage codes in which each symbol can be recovered from a limited number of other symbols. More recently, there is an interest in cooperative locally recoverable codes, i.e., codes in which multiple symbols can be recovered from a small set of other code symbols.In this paper, we establish a relationship between coding schemes for the single-server PIR problem and LRCs. In particular, we show the following results: (i) PIR schemes designed for retrieving a single message are equivalent to classical LRCs; and (ii) PIR schemes for retrieving multiple messages are equivalent to cooperative LRCs. These equivalence results allow us to recover upper bounds on the download rate for PIR-SI schemes, and to obtain a novel rate upper bound on cooperative LRCs. We show results for both linear and non-linear codes.

This paper considers the problem of Quantitative Group Testing (QGT). Consider a set of N items among which K items are defective. The QGT problem is to identify (all or a sufficiently large fraction of) the defective items, where the result of a test reveals the number of defective items in the tested group. In this work, we propose a non-adaptive QGT scheme using sparse graph codes over bi-regular bipartite graphs and binary t-error-correcting BCH codes. The proposed scheme provides exact recovery with probabilistic guarantee, i.e. recovers all the defective items with high probability. In particular, we show that for the sub-linear regime where K vanishes as K, N → ∞, the proposed scheme requires at most m ≈ 1.19K log2(4.74 N/K) tests to recover all the defective items with probability approaching one as K, N → ∞. This bound can be achieved by t = 2. The testing and recovery algorithms of the proposed scheme for any t ≤ 4 have the computational complexity of O(K log2N/K) and O(K log N/K), respectively. Our simulation results also show that the proposed scheme significantly outperforms a non-adaptive semi-quantitative group testing scheme recently proposed by Abdalla et al. in terms of the required number of tests for identifying all the defective items with high probability.

Packet classification methods rely upon packet content/header matching against rules. Thus, throughput of matching operations is critical in many networking applications. Further, with the advent of Software Defined Networking (SDN), efficient implementation of software approaches to matching are critical for the overall system performance. This article presents 1 GenMatcher, a generic, software-only, arbitrary matching framework for fast, efficient searches. The key idea of our approach is to represent arbitrary rules with efficient prefix-based tries. To support arbitrary wildcards, we rearrange bits within the rules such that wildcards accumulate to one side of the bitstring. Since many non-contiguous wildcards often remain, we use multiple prefix-based tries. The main challenge in this context is to generate efficient trie groupings and expansions to support all arbitrary rules. Finding an optimal mix of grouping and expansion is an NP-complete problem. Our contribution includes a novel, clustering-based grouping algorithm to group rules based upon their bit-level similarities. Our algorithm generates near-optimal trie groupings with low configuration times and provides significantly higher match throughput compared to prior techniques. Experiments with synthetic traffic show that our method can achieve a 58.9X speedup compared to the baseline on a single core processor under a given memory constraint.

We extend the notion of locality from the Hamming metric to the rank and subspace metrics. Our main contribution is to construct a class of array codes with locality constraints in the rank metric. Our motivation for constructing such codes stems from the need to design codes for efficient data recovery from correlated and/or mixed (i.e., complete and partial) failures in distributed storage systems. Specifically, the proposed local rank-metric codes can recover locally from crisscross errors and erasures, which affect a limited number of rows and/or columns of the storage array. We also derive a Singlet-on-like upper bound on the minimum rank distance of (linear) codes with rank-locality constraints. Our proposed construction achieves this bound for a broad range of parameters. The construction builds upon Tamo and Barg's method for constructing locally repairable codes with optimal minimum Hamming distance. Finally, we construct a class of constant-dimension subspace codes (also known as Grassmannian codes) with locality constraints in the subspace metric. The key idea is to show that a Grassmannian code with locality can be easily constructed from a rank-metric code with locality by using the lifting method proposed by Silva et al. We present an application of such codes for distributed storage systems, wherein nodes are connected over a network that can introduce errors and erasures.

This paper presents millimeter wave propagation measurements at 28 GHz for a typical suburban environment using a 400-megachip-per-second custom- designed broadband sliding correlator channel sounder and highly directional 22-dBi (15° half-power beamwidth) horn antennas. With a 23-dBm transmitter installed at a height of 27m to emulate a microcell deployment, the receiver obtained more than 5000 power delay profiles over distances from 80m to 1000m at 50 individual sites and on two pedestrian paths. The resulting basic transmission losses were compared with predictions of the over-rooftop model in recommendation ITU-R P.1411-9. Our analysis reveals that the traditional channel modeling approach may be insufficient to deal with the varying site-specific propagations of millimeter waves in suburban environments. For line-of-sight measurements, the path loss exponents obtained for the close-in (CI) free space reference distance model and the alpha-beta-gamma (ABG) model are 2.00 and 2.81, respectively, which are close to the recommended site-general value of 2.29. The root mean square errors (RMSEs) for these two reference models are 9.93dB and 9.70dB, respectively, which are slightly lower than that for the ITU site-general model (10.34dB). For non-line-of-sight measurements, both reference models, with the resulting path loss exponents of 2.50 for the CI model and 1.12 for the ABG model, outperformed the site-specific ITU model by around 14dB RMSE.

This paper considers the problem of cooperative data exchange with selfish users. In this setting, each user has a subset of packets in the ground set$X$, and wants all other packets in$X$. The users can exchange coded combinations of their packets over a lossless broadcast channel, and monetary transactions are allowed between any pair of users. We define the utility of each user as the sum of two functions: (i) the difference between the total payment received by the user and the total transmission rate of the user, and (ii) the difference between the total number of required packets by the user and the total payment made by the user. A rate-vector and payment-matrix pair$(r,p)$is said to stabilize the grand coalition (i.e., the set of all users) if$(r,p)$is Pareto optimal over all minor coalitions (i.e., all proper subsets of users who collectively know all packets in$X$). Our goal is to design a stabilizing rate-payment pair with minimum sum-rate and minimum sum-payment for any given problem instance. In this work, we show that such a solution always exists, and we propose two algorithms to find such a solution. Moreover, we show that both algorithms maximize the sum utility of all users, while one also maximizes the minimum utility among all users.

This paper considers a generalized version of the coin weighing problem with a spring scale that lies at the intersection of group testing and compressed sensing problems. Given a collection of n ≥ 2 coins of total weight d (for a known integer d), where the weight of each coin is an unknown integer in the range of {0, 1, ..., k} (for a known integer k ≥ 1), the goal is to determine the weight of each coin by weighing subsets of coins in a spring scale. The problem is to devise a weighing strategy that minimizes the average number of weighings over all possible weight configurations. For d = k = 1, an adaptive bisecting weighing strategy is known to be optimal. However, even the simplest non-trivial case of the problem, i.e., d = k = 2, is still open. For this case, we propose and analyze a simple and effective adaptive weighing strategy. Our analysis shows that the proposed strategy requires about 1.365log2n-0.5 weighings on average. As n grows unbounded, the proposed strategy, when compared to an optimal strategy within the commonly-used class of nested strategies, requires about 31.75% less number of weighings on average; and in comparison with the information-theoretic lower bound, it requires at most about 8.16% extra number of weighings on average.

This paper considers the problem of single-server single-message private information retrieval with coded side information (PIR-CSI). In this problem, there is a server storing a database, and a user which knows a linear combination of a subset of messages in the database as a side information. The number of messages contributing to the side information is known to the server, but the indices and the coefficients of these messages are unknown to the server. The user wishes to download a message from the server privately, i.e., without revealing which message it is requesting, while minimizing the download cost. In this work, we consider two different settings for the PIR-CSI problem depending on the demanded message being or not being one of the messages contributing to the side information. For each setting, we prove an upper bound on the maximum download rate as a function of the size of the database and the size of the side information, and propose a protocol that achieves the rate upper-bound.

This paper considers the problem of approximating the failure frequency of large-scale composite k-terminal reliability systems. In such systems, the nodes (k of which are terminals) are connected through components, which are subject to random failure and repair processes. At any time, a system failure occurs if the surviving system fails to connect all the k terminals together. We assume that each component's up times and down times follow statistically independent stationary random processes, and these processes are statistically independent across the components. In this setting, the exact computation of failure frequency is known to be computationally intractable (NP-hard). In this paper, we present an algorithm to approximate the failure frequency for any given multiplicative error factor that runs in polynomial time in the number of (minimal) cutsets. Moreover, for the special case of all-terminal reliability systems, i.e., where all the nodes are terminals, we propose an algorithm for approximating the failure frequency within an arbitrary multiplicative error that runs in polynomial time in the number of nodes (which can be much smaller than the number of cutsets). Our simulation results confirm that the proposed method is much faster and more accurate than the standard Monte Carlo simulation technique for approximating the failure frequency.

This paper considers the problem of designing maximum distance separable (MDS) codes over small fields with constraints on the support of their generator matrices. For any given m χ n binary matrix M, the GM-MDS conjecture, due to Dau et al., states that if M satisfies the so-called MDS condition, then for any field F of size q ≥ n + m - 1, there exists an [n, m]qMDS code whose generator matrix G, with entries in F, fits M (i.e., M is the support matrix of G). Despite all the attempts by the coding theory community, this conjecture remains still open in general. It was shown, independently by Yan et al. and Dau et al., that the GM-MDS conjecture holds if the following conjecture, referred to as the TM-MDS conjecture, holds: if M satisfies the MDS condition, then the determinant of a transformation matrix T, such that TV fits M, is not identically zero, where V is a Vandermonde matrix with distinct parameters. In this work, we generalize the TM-MDS conjecture, and present an algebraic-combinatorial approach based on polynomial-degree reduction for proving this conjecture. Our proof technique's strength is based primarily on reducing inherent combinatorics in the proof. We demonstrate the strength of our technique by proving the TM-MDS conjecture for the cases where the number of rows (m) of M is upper bounded by 5. For this class of special cases of M where the only additional constraint is on m, only cases with m4.

This paper considers two generalizations of the cooperative data exchange problem, referred to as the successive local omniscience (SLO) and the successive global omniscience (SGO). The users are divided into ℓ nested sub-groups. Each user initially knows a subset of packets in a ground set X of size k, and all users wish to learn all packets in X. The users exchange their packets by broadcasting coded or uncoded packets. In SLO or SGO, in the lth (1≤ l ≤ ℓ) round of transmissions, the lth smallest ub-group of users need to learn all packets they collectively hold or all packets in X, respectively. The problem is to find the minimum sum-rate (i.e., the total transmission rate by all users) for each round, subject to minimizing the sum-rate for the previous round. To solve this problem, we use a linear-programming approach. For the cases in which the packets are randomly distributed among users, we construct a system of linear equations whose solution characterizes the minimum sum-rate for each round with high probability as k tends to infinity. Moreover, for the special case of two nested groups, we derive closed-form expressions, which hold with high probability as k tends to infinity, for the minimum sum-rate for each round.

We consider the problem of designing repair efficient distributed storage systems, which are information-theoretically secure against a passive eavesdropper that can gain access to a limited number of storage nodes. We present a framework that enables design of a broad range of secure storage codes through a joint construction of inner and outer codes. As case studies, we focus on two specific families of storage codes: (i) minimum storage regenerating (MSR) codes, and (ii) maximally recoverable (MR) codes, which are a class of locally repairable codes (LRCs). The main idea of this framework is to utilize the existing constructions of storage codes to jointly design an outer coset code and inner storage code. Finally, we present a construction of an outer coset code over small field size to secure locally repairable codes presented by Tamo and Barg for the special case of an eavesdropper that can observe any subset of nodes of maximum possible size.

Distributed file systems enable the reliable storage of exabytes of information on thousands of servers distributed throughout a network. These systems achieve reliability and performance by storing multiple copies of data blocks in different locations across the network. The management of these copies of data is commonly handled by intermediate servers that track and coordinate the placement of data in the network. This introduces potential network bottlenecks, as multiple transfers to fast storage nodes can saturate network links between intermediate servers and storage devices. The advent of open Network Operating Systems and Software Defined Networking presents an opportunity to alleviate this bottleneck, as it is now possible to give network elements enough intelligence to handle bandwidthintensive tasks, such as data replication and reconstruction. In this paper, we propose a new in-network packet processing architecture for distributed file systems. The key idea of the proposed architecture is to offload several actions of distributed file systems onto a new fundamental component of the system that runs on network devices such as routers and switches. We describe the component's architecture and how it can be integrated into existing distributed file systems. To evaluate the performance of our approach, we implement the proposed solution in a block-level storage array distributed across multiple iSCSI targets. We show that the proposed architecture results in reduced network congestion and a decrease in request latency proportional to the number of storage nodes involved in the request.

This paper considers the problem of cooperative data exchange with different client priority classes. In this problem, each client initially knows a subset of packets in the ground set X of size K, and all clients wish to learn all packets in X. The clients exchange packets by broadcasting coded combinations of their packets. The primary objective is to satisfy all high-priority clients in the first round of transmissions with minimum sum-rate, and the secondary objective is to satisfy low-priority clients in the second round of transmissions with minimum sum-rate, subject to minimizing the sum-rate in the first round. For any arbitrary problem instance, we provide a linear programming-based approach to find the minimum sum-rate in each round. Moreover, for the case in which the packets are randomly distributed among clients, we derive a closed-form expression for the minimum sum-rate in each round, which holds with probability approaching 1 as K tends to infinity.

In many practical settings, there is a need to design distributed storage codes with certain locality constraints. For a code C, its i-th symbol is said to have locality r if it can be recovered by accessing some other r symbols of C. Locally repairable codes (LRCs) are the family of codes such that every symbol has small locality.

Because the exchange of information among all the users in a large network can take a long time, a successive omniscience protocol is proposed. Namely, subgroups of users first recover the information of other users in the same subgroup at an earlier stage called local omniscience. Then, the users recover the information of all other users at a later stage called global omniscience. To facilitate the information exchange, a distributed storage system is used, so that users can conveniently upload and download messages through some reliable central servers. The minimum upload bandwidth is characterized and a bandwidth-storage trade-off is discovered. The results reveal the new connections to the problem of secret key agreement and, consequently, provide meaningful interpretations of a recently proposed multivariate mutual information measure that was inspired by the secret key agreement problem.

As modern CMPs scale to ever increasing core counts, Networks-on-Chip (NoCs) are emerging as an interconnection fabric, enabling communication between components. While NoCs provide high and scalable bandwidth, current routing algorithms, such as dimension-ordered routing, suffer from poor load balance, leading to reduced throughput and high latencies. Improving load balance, hence, is critical in future CMP designs where increased latency leads to wasted power and energy waiting for outstanding requests to resolve. Adaptive routing is a known technique to improve load balance, however, prior adaptive routing techniques either use local or regionally-aggregated information to form their routing decisions. This paper proposes a new, light-weight, adaptive routing algorithm for on-chip routers based on global link state and congestion information, Global Congestion Awareness (GCA). GCA uses a simple, low-complexity route calculation unit, to calculate paths to their destination without the myopia of local decisions, nor the aggregation of unrelated status information, found in prior designs. In particular GCA outperforms local adaptive routing by 26 percent, Regional Congestion Awareness (RCA) by 15 percent, and a recent competing adaptive routing algorithm, DAR, by 8 percent on average on realistic workloads.

Software Defined Networking (SDN) drastically changes the meaning and process of designing, building, testing, and operating networks. The current support for wireless networking in SDN technologies has lagged behind its development and deployment for wired networks. The purpose of this work is to bring principled support for wireless access networks so that they can receive the same level of programmability as wireline interfaces. Specifically we aim to integrate wireless protocols into the general SDN framework by proposing a new set of abstractions in wireless devices and the interfaces to manipulate them. We validate our approach by implementing our design as an extension of an existing OpenFlow data plane and deploying it in an IEEE 802.11 access point. We demonstrate the viability of software-defined wireless access networks by developing and testing a wireless handoff application. The results of the experiment show that our framework is capable of providing new capabilities in an efficient manner.

In distributed storage systems, a special sub-class of locally repairable codes, referred to as availability codes, has been proposed to enable recovery of each data block from one of its repair groups. A repair group typically contains a small number of nodes and does not overlap with any other repair group of the same data block. Availability codes have several important benefits, including high degree of fault tolerance, efficient recovery from failures, and efficient access to data by multiple users. In this paper, we study the availability codes from a queuing-theoretical perspective. Specifically, we analyze the average time necessary to download a block of data under the Poisson request arrival model in two service/scheduling scenarios. We compare the availability codes with several alternatives such as MDS codes and replication schemes. Our results indicate that availability codes can minimize the download time in some settings, but are not always optimal.

We consider the problem of communication over a multi-path network in the presence of a causal adversary. The limited-view causal adversary is able to, based on the current and past observations, eavesdrop on a subset of links and also jam on a potentially overlapping subset of links. The goal is to ensure that the communication takes place reliably and secretly. We study two adversarial models - additive and overwrite jamming. For both adversarial models, we consider communication models both without and with passive feedback from decoder to encoder, i.e., the encoder sees everything that the decoder sees. The problem assumes transmissions are in the large alphabet regime. For both types of jamming models, we find the capacity under three scenarios - reliability without feedback, reliability and secrecy without feedback, and reliability with feedback. We observe that in comparison to the non-causal setting the capacity with a causal adversary is strictly increased for a wide variety of parameter settings, and present our intuition through several examples.

In the Cooperative Data Exchange (CDE) problem, a group of wireless clients need to exchange data over a shared broadcast channel, such that at the end of the transfer all clients have access to all packets held by other clients. In this paper, we focus on the robust version of the problem in which the clients must be able to complete the transfer even if one of the clients fails before the transfer is complete. The event of a client failure is referred to as an erasure. We show that, while the original CDE problem can be solved in polynomial time, the robust version of the problem is NP-hard, even in the special case when robustness to a single failure is required. Focusing on the practically important special case of a single failure, we establish an approximation algorithm for this problem that can find a solution within a constant factor of the optimum. Our simulation studies show that the algorithm is able to find solutions that are very close to the optimum.

We consider reliable and secure communication of information over a multipath network. A transmitter Alice sends messages to the receiver Bob in the presence of a hidden adversary Calvin. The adversary Calvin can both eavesdrop and jam on (possibly non-identical) subsets of transmission links. The goal is to communicate reliably (intended receiver can understand the messages) and secretly (adversary cannot understand the messages). Two kinds of jamming, additive and overwrite, are considered. Additive jamming corresponds to wireless network model while overwrite jamming corresponds to wired network model and storage systems. The multipath network consists of C parallel links. Calvin can both jam and eavesdrop any zionumber of links, can eavesdrop (but not jam) any zi/onumber of links, and can jam (but not eavesdrop) any zo/inumber of links. We present the first “complete” information-theoretic characterization of maximum achievable rate as a function of the number of links that can be jammed and/or eavesdropped for equal and unequal link capacity multipath networks under additive and overwrite jamming in the large alphabet regime. Our achievability and converse proofs require non-trivial combination of information theoretic and coding theoretic ideas and our achievability schemes are computationally efficient. The PHaSE-Saving techniques1are used for achievability while a “stochastic” singleton bound is obtained for converse.

It has been well established that wireless network coding can significantly improve the efficiency of multihop wireless networks. However, in a stochastic environment, some of the packets might not have coding pairs, which limits the number of available coding opportunities. In this context, an important decision is whether to delay packet transmission in hope that a coding pair will be available in the future or transmit a packet without coding. This paper addresses this problem by establishing a stochastic dynamic framework whose objective is to minimize a long-run average cost. We identify an optimal control policy that minimizes the costs due to a combination of transmissions and packet delays. We show that the optimal policy would be stationary, deterministic, and threshold-type based on queue lengths. Our analytical approach is applicable for many cases of interest such as time-varying on/off channels. We further substantiate our results with simulation experiments for more generalized settings.

Physical layer network coding has attracted extensive theoretical interest, although relatively little research has been done in support of deployment to wireless networks where internode synchronization is difficult to achieve. In particular, wireless networks constructed with inexpensive and commercially available software defined radio technology, or more generally, radio front-end samplers connected to internet-based remote processors (i.e., the Internet of Things network) may exhibit large time, frequency, and phase offsets that are difficult to control. In this paper, we define an asynchronous discrete-time model that accounts for these impairments as part of the information transfer between network users and a relay. Derived from this model are maximum likelihood algorithms for relay parameter estimation and a symbol decoder inspired from asynchronous multi-user detection. Additionally, null space-based frequency offset estimation that reduces computational complexity is proposed. Simulation results and the design and performance of a two-user system implemented with the Universal Software Radio Peripheral (USRP) platform and GNU radio are included to demonstrate the proof of concept. Our results indicate that the physical layer network coding technique can be successfully deployed and yields significant benefits even in the presence of impairments found in practical settings.

The Software Defined Networking (SDN) approach has numerous advantages, including the ability to program the network through simple abstractions, provide a centralized view of network state, and respond to changing network conditions. One of the main challenges in designing SDN enabled switches is efficient packet classification in the data plane. As the complexity of SDN applications increases, the data plane becomes more susceptible to Denial of Service (DoS) attacks, which can result in increased delays and packet loss. Accordingly, there is a strong need for network architectures that operate efficiently in the presence of malicious traffic. In particular, there is a need to protect authorized flows from DoS attacks. In this work we utilize a probabilistic data structure to pre-classify traffic with the aim of decoupling likely legitimate traffic from malicious traffic by leveraging the locality of packet flows. We validate our approach by examining a fundamental SDN application: software defined network firewall. For this application, our architecture dramatically reduces the impact of unknown/malicious flows on established/legitimate flows. We explore the effect of stochastic pre-classification in prioritizing data plane classification. We show how pre-classification can be used to increase the effective Quality of Service (QoS) for established flows and reduce the impact of adversarial traffic.

We consider the scenario wherein a transmitter Alice wants to (potentially) communicate to the intended receiver Bob over a multipath network, i.e., a network consisting of multiple parallel links, in the presence of a passive eavesdropper Willie, who observes an unknown subset of links. A primary goal of our communication protocol is to make the communication “deniable”, i.e., Willie should not be able to reliably estimate whether or not Alice is transmitting any covert information to Bob. Moreover, if Alice is indeed actively communicating, her covert messages should be information-theoretically “hidable” in the sense that Willie's observations should not leak any information about Alice's (potential) message to Bob - our notion of hidability is slightly stronger than the notion of information-theoretic strong secrecy well-studied in the literature. We demonstrate that deniability does not imply either hidability or (weak or strong) information-theoretic secrecy; nor does information-theoretic secrecy imply deniability. We present matching inner and outer bounds on the capacity for deniable and hidable communication over multipath networks.

We focus on secure data exchange among a group of wireless clients. The clients exchange data by broadcasting linear combinations of packets over a lossless channel. The data exchange is performed in the presence of an eavesdropper who has access to the channel and can obtain all transmitted data. Our goal is to develop a weakly secure coding scheme that prevents the eavesdropper from being able to decode any of the original packets held by the clients. We present a randomized algorithm based on Generalized Reed-Solomon (GRS) codes. The algorithm has two key advantages over the previous solutions: it operates over a small (polynomial-size) finite field and provides a way to verify that constructed code is feasible. In contrast, the previous approaches require exponential field size and do not provide an efficient (polynomial-time) algorithm to verify the secrecy properties of the constructed code. We formulate an algebraic-geometric conjecture that implies the correctness of our algorithm and prove its validity for special cases. Our simulation results indicate that the algorithm is efficient in practical settings.

We survey here recent work pertaining to “deniable” communication - i.e., talking without being detected. We first highlight connections to other related notions (anonymity and secrecy). We then contrast the notions of deniability and secrecy. We highlight similarities and distinctions of deniability with a variety of related notions (LPD communications, stealth, channel resolvability) extant in the literature.

Reductions, or transformations of one problem to the other, are a fundamental tool in complexity theory used for establishing the hardness of discrete optimization problems. Recently, there is a significant interest in using reductions for establishing relationships between different classes of problems related to network coding, index coding, and matroid theory. The goal of this paper is to survey the basic reduction techniques for proving equivalence between network coding and index coding, as well as the establishing relations between the index coding problem and the problem of finding a linear representation of a matroid. The paper reviews recent advances in the area and discusses open research problems.

We consider a relay node that stochastically receives packets from two opposing flows. Whenever opportunities exist, the relay performs network coding to efficiently transmit packets. However, on one hand, because of the stochastic nature, as well as possible asymmetry between the opposing flows, it would not be possible to always code packets. On the other hand, waiting for a coding opportunity could result in excessive latency, and one may be better off transmitting packets without coding. Thus, one needs to decide at each transmission opportunity whether to transmit a packet uncoded or wait for a future transmission opportunity. To enable us to optimally make that decision, we consider costs for transmission and delay, and formulate our problem as a Markov decision process. We show that the optimal policy is threshold type under a sufficient condition, and we compute it by modeling the resulting system as a Markov chain. Through numerical analysis, we show the effectiveness of the threshold policy in the relay node network, as well as in a line network scenario. Further, we compare the threshold policy against a number of simple heuristic policies and identify situations where these policies can be effective.

We consider wireless networks in which multiple paths are available between each source and destination. We allow each source to split traffic among all of its available paths, and we ask the question: How do we attain the lowest possible number of transmissions per unit time to support a given traffic matrix? Traffic bound in opposite directions over two wireless hops can utilize the “reverse carpooling” advantage of network coding in order to decrease the number of transmissions used. We call such coded hops “hyper-links.” With the reverse carpooling technique, longer paths might be cheaper than shorter ones. However, there is a peculiar situation among sources—the network coding advantage is realized only if there is traffic in both directions of a shared path. We consider the problem of routing with network coding by selfish agents (the sources) as a potential game and develop a method of state-space augmentation in which additional agents (the hyper-links) decouple sources' choices from each other by declaring a hyper-link capacity, allowing sources to split their traffic selfishly in a distributed fashion, and then changing the hyper-link capacity based on user actions. Furthermore, each hyper-link has a scheduling constraint in terms of the maximum number of transmissions allowed per unit time. We show that our two-level control scheme is stable and verify our analytical insights by simulation.

Modern cellular networks are expected to support both voice and a growing volume of data traffic. The rapid growth in data traffic has promoted network operators to move to Long Term Evolution (LTE), a 4th generation of wireless network infrastructure. However, LTE architecture does not support native circuit switching services and relies on the IP Multimedia Subsystem (IMS) for supporting voice and Short Messaging Service (SMS). Unfortunately, the uptake of IMS has not been as rapid as expected and deployments of IMS cores have been limited. This poses a major issue for operators who wish to deploy LTE in the near future. In particular, voice and SMS drive a majority of service provider revenue, who are concerned with voice quality, call continuity, and reliable SMS delivery in deployed LTE networks. In this paper we analyze several contending approaches to delivering voice services over LTE networks. Each approach will be illustrated with sequence diagrams to explain how voice and SMS services are rendered. We compare the proposed solutions in terms of complexity, cost, features, and interoperability.

Firewalls are ubiquitous security functions and exist in almost all network connected devices whether protecting host stacks or providing transient packet filtering. Firewall performance, which is a key ingredient for network performance, can be greatly degraded by traffic crafted to exploit its filtering algorithms. These attacks can greatly reduce the Quality of Service (QoS) received by existing authorized flows in the firewall. This paper proposes a novel architecture that decouples this linkage between authorized flow QoS and adversarial traffic, marginalizing disruption caused by unauthorized flows, and ultimately improving overall performance of software defined firewalls. We show substantial improvements in throughput, packet loss, and latency over baseline software defined firewalls with varying ratios of attack traffic. All results are obtained using the cycle accurate architecture simulator gem5, and Internet packet traces obtained from 10 Gbps interfaces of core Internet routers.

Incorrect implementations of network protocol message specifications affect the stability, security, and cost of network system development. Most implementation defects fall into one of three categories of well defined message constraints. However, the general process of constructing network protocol stacks and systems does not capture these categorical constraints. We introduce a systems programming language with new abstractions that capture these constraints. Safe and efficient implementations of standard message handling operations are synthesized by our compiler, and whole-program analysis is used to ensure constraints are never violated. We present language examples using the OpenFlow protocol.

The Index Coding problem has recently attracted a significant interest from the research community. In this problem, a server needs to deliver a set of packets to a group of wireless clients over a noiseless broadcast channel. Each client requests a subset of packets and has another subset given to it as side information. The objective is to satisfy the demands of all clients with the minimum number of transmissions. In this paper, we study the Index Coding problem from the game-theoretic perspective. We assume that each client is selfish and has a hidden private value for each packet it requests. The objective of the server is to maximize the value of social welfare that captures the trade-off between values of the transmitted packets and the transmission cost incurred by the server. The transmission process is decided through an auction in which the clients are required to submit bids to the server. Our goal is to design a truthful auction scheme that provides an incentive for each client to bid the true value of the packets and maximizes the value of the social welfare. The key challenge in this context is to determine the encoding functions of the transmitted packets. Since finding an optimal encoding function is an NP-hard problem, we propose efficient algorithms that identify the encoding functions as well as a payment scheme that provide an approximate solution and guarantee truthfulness.

As modern CMPs scale to ever increasing core counts, Networks-on-Chip (NoCs) are emerging as an interconnection fabric, enabling communication between components. While NoCs provide high and scalable bandwidth, current routing algorithms, such as dimension-ordered routing, suffer from poor load balance, leading to reduced throughput and high latencies. Improving load balance, hence, is critical in future CMP designs where increased latency leads to wasted power and energy waiting for outstanding requests to resolve. Adaptive routing is a known technique to improve load balance, however, prior adaptive routing techniques either use local or regionally aggregated information to form their routing decisions. This paper proposes a new, light-weight, adaptive routing algorithm for on-chip routers based on global link state and congestion information, Global Congestion Awareness (GCA). GCA uses a simple, low-complexity route calculation unit, to calculate paths to their destination without the myopia of local decisions, nor the aggregation of unrelated status information, found in prior designs. In particular GCA outperforms local adaptive routing by 26%, Regional Congestion Awareness (RCA) by 15%, and a recent competing adaptive routing algorithm, DAR, by 8% on average on realistic workloads.

We consider the problem of securing a multicast network against a wiretapper that can eavesdrop on the packets on a limited number of network edges of its choice. We assume that the network employs network coding to simultaneously deliver the packets available at the source to all the destinations. We show that this problem can be looked at as a network generalization of the wiretap channel of type II introduced in a seminal paper by Ozarow and Wyner. In particular, we show that the transmitted information can be secured by using the Ozarow–Wyner approach of coset coding at the source on top of the existing network code. This way, we quickly and transparently recover some of the results available in the literature on secure network coding for wiretap networks. Moreover, we use this framework to derive new bounds on the code alphabet size that are independent of the network size, and provide algorithms for explicit construction of secure network codes. We also analyze the amount of information that can be leaked to the wiretapper as a function of the number of wiretapped edges.

The Index Coding problem has recently attracted a significant attention from the research community. In this problem, a server needs to deliver data to a set of wireless clients over the broadcast channel. Each client requires one or more packets, but it might have access to the packets requested by other clients as side information. The goal is to deliver the required data to each client with minimum number of transmissions. In this paper, we focus on finding sparse solutions to the Index Coding problem. In a sparse solution each transmitted packet is a linear combination of at most two original packets. We focus both on scalar and vector versions of the problem. For the scalar case, we present a polynomial time algorithm that achieves an approximation ratio of 2-(1/√n). For the vector case, we present a polynomial time algorithm that identifies an optimal solution to the problem. Our simulation studies demonstrate that our algorithms achieve good performance in practical scenarios.

In this paper, we present an algorithm for joint decoding of the modulo-2 sum of the bits transmitted from two unsynchronized transmitters using Physical Layer Network Coding (PLNC). We address the problems that arise when the boundaries of the signals do not align with each other and when the channel parameters are slowly varying and are not known to the receiver at the relay node. Our approach first estimates jointly the timing and fading gains of both the signals, and uses a state-based Viterbi decoding scheme that takes into account the timing offsets between the interfering signals. We also track the amplitude and phase of the channel which may be slowly varying. Simulation results demonstrate the sensitivity of the detection performance at the relay node to the relative offset of the timings of the two user's signals as well as the advantage of our algorithm over previously published algorithms.

We consider the problem of secure cooperative data exchange in wireless networks. The cooperative data exchange problem includes a set of wireless clients that exchange information over a lossless broadcast channel. The clients are missing some packets but collectively know all packets. Each client can transmit packets it currently has or a combination thereof. The problem asks for a scheme that allows all clients to recover all packets with the minimum number of transmissions. We focus on secure information exchange in the presence of an eavesdropper that can observe all packets transmitted over the broadcast channel. Our goal is to construct a weakly secure solution to the cooperative data exchange problem, i.e., a solution that does not reveal information about any single packet. This is in contrast to strongly secure solutions that do not reveal any data about the entire set of packets. Weakly secure solutions can be implemented more efficiently in practical settings and do not require sharing secret keys. Our paper makes the following contributions. First, we establish necessary and sufficient conditions for the feasibility of weakly secure data exchange for any given instance of the weakly secure data exchange problem. Second, we show that if it is possible to obtain a weakly secure solution for an instance of the cooperative data exchange problem, then weak security can be achieved with no penalty in terms of the total number of transmissions. Finally, we present an algorithm that finds an optimal weakly secure solution to the cooperative data exchange problem.

The Index Coding problem is one of the basic problems in wireless network coding. In this problem, a server needs to deliver a set P of packets to several clients through a noiseless broadcast channel. Each client needs to obtain a certain subset of P and has prior side information about a different subset of P. The objective is to satisfy the requirements of all clients with the minimum number of transmissions. Recently, it was shown that the Index Coding problem is NP-hard. Furthermore, this problem was shown to be hard to approximate under a widely accepted complexity assumption. In this paper, we consider a complementary problem whose goal is to maximize the number of saved transmissions, i.e., the number of transmissions that are saved by combining packets compared to the solution that does not involve coding. We refer to this problem as the the Complementary Index Coding problem. It turns out that the complementary problem can be approximated in certain cases of practical importance. We consider the multiple unicast and multiple multicast scenarios. In the multiple unicast scenario, each packet is requested by a single client; while in the multiple multicast scenario, each packet can be requested by several clients. For the multiple unicast scenario, we present approximation algorithms for finding scalar and vector linear solutions. For the multiple multicast scenario, we show that finding an approximation solution is NP-hard.

It has been well established that reverse-carpooling based network coding can significantly improve the efficiency of multi-hop wireless networks. However, in a stochastic environment when there are no opportunities to code because of packets without coding pairs, should these packets wait for a future opportunity or should they be transmitted without coding? To help answer that question we formulate a stochastic dynamic program with the objective of minimizing the long-run average cost per unit time incurred due to transmissions and delays. In particular, we develop optimal control actions that would balance between costs of transmission against those of delays. In that process we seek to address a crucial question: what should be observed as the state of the system? We analytically show that just the queue lengths is enough if it can be modeled as a Markov process. Subsequently we show that a stationary policy based on queue lengths is optimal and describe a procedure to find such a policy. We further substantiate our results with simulation experiments for more generalized settings.

Network-on-chip (NoC) designs have emerged as a replacement for traditional shared-bus designs for on-chip communication. As with all current very large scale integration designs, however, reducing power consumption in NoCs is a critical challenge. One approach to reduce power consumption is to dynamically scale the voltage and frequency of each network node or groups of nodes (DVFS). Another approach is to replace the balanced clock tree with a globally-asynchronous, locally-synchronous (GALS) clocking scheme. In both DVFS and GALS designs, the chip as a whole is multi-synchronous. As the NoCs interconnecting those nodes must communicate across these clock domain boundaries, they tend to have high latencies as packets must be synchronized at the intermediate nodes. In this paper, we propose a novel router microarchitecture which offers superior performance with respect to typical synchronizing router designs for multi-synchronous networks. Our approach features asynchronous bypass channels which allow flit traversal of intermediate nodes within the network without the latching or synchronization overheads of typical designs. We also propose a new network topology and routing algorithm that leverage the advantages of the bypass channel offered by our router design. We present a detailed analysis of design decisions which affect the performance of the asynchronous bypass channel network. Our experiments show that our design improves the performance of a conventional synchronizing design with similar resources by up to 26% at low loads and increases saturation throughput by up to 50% for a uniform random traffic.

This work addresses the computational complexity of achieving the capacity of a general network coding instance. It has been shown [Lehman and Lehman, SODA 2005] that determining the “scalar linear” capacity of a general network coding instance is NP-hard. In this paper we address the notion of approximation in the context of both linear and nonlinear network coding. Loosely speaking, we show that given an instance of the general network coding problem of capacityC, constructing a code of rate αCfor any universal (i.e., independent of the size of the instance) constant α ≤ 1 is “hard”. Specifically, finding such network codes would solve a long standing open problem in the field of graph coloring. Our results refer to scalar linear, vector linear, and nonlinear encoding functions and are the first results that address the computational complexity of achieving the network coding capacity in both the vector linear and general network coding scenarios. In addition, we consider the problem of determining the (scalar) linear capacity of a planar network coding instance (i.e., an instance in which the underlying graph is planar). We show that even for planar networks this problem remains NP-hard.

We consider the problem of establishing reliable unicast connections across a communication network with nonuniform edge capacities. Our goal is to provide instantaneous recovery from single edge failures. With instantaneous recovery, the destination node can decode the packets sent by the source node even if one of the network edges fails, without the need of retransmission or rerouting. It has been recognized that the network coding technique offers significant advantages for this problem over standard solutions such as disjoint path routing and diversity coding. We focus on two cases of practical interest: 1) backup protection of a single flow that can be split into two subflows; and 2) shared backup protection of two unicast flows. We present an efficient network coding algorithm that operates over a small finite field (GF(2)). The small size of the underlying field results in a significant reduction in the computational and communication overhead associated with the practical implementation of the network coding technique. Our algorithm exploits the unique structure of minimum coding networks, i.e., networks that do not contain redundant edges. We also consider the related capacity reservation problem and present an approximation algorithm that finds a solution whose cost is at most two times more than the optimum.

We consider the problem of accessing large data files stored at multiple locations across a content distribution, peer-to-peer, or massive storage network. We assume that the data is stored in either original form, or encoded form at multiple network locations. Clients access the data through simultaneous downloads from several servers across the network. The central problem in this context is to find a set of disjoint paths of minimum total cost that connect the client with a set of servers such that the data stored at the servers is sufficient to decode the required file. We refer to this problem as the Distributed Data Retrieval (DDR) problem. We present an efficient polynomial-time solution for this problem that leverages the matroid intersection algorithm. Our experimental study shows the advantage of our solution over alternative approaches.

We consider wireless networks in which multiple paths are available between each source and destination. We allow each source to split traffic among all of its available paths, and ask the question: how do we attain the lowest possible number of transmissions per unit time to support a given traffic matrix? Traffic bound in opposite directions over two wireless hops can utilize the ``reverse carpooling'' advantage of network coding in order to decrease the number of transmissions used. We call such coded hops as ``hyper-links''. With the reverse carpooling technique longer paths might be cheaper than shorter ones. However, there is a prisoners dilemma type situation among sources -- the network coding advantage is realized only if there is traffic in both directions of a shared path. We develop a two-level distributed control scheme that decouples user choices from each other by declaring a hyper- link capacity, allowing sources to split their traffic selfishly in a distributed fashion, and then changing the hyper-link capacity based on user actions. We show that such a controller is stable, and verify our analytical insights by simulation.

We consider scenarios where wireless clients are missing some packets, but they collectively know every packet. The clients collaborate to exchange missing packets over an error-free broadcast channel with capacity of one packet per channel use. First, we present an algorithm that allows each client to obtain missing packets, with minimum number of transmissions. The algorithm employs random linear coding over a sufficiently large field. Next, we show that the field size can be reduced while maintaining the same number of transmissions. Finally, we establish lower and upper bounds on the minimum number of transmissions that are easily computable and often tight as demonstrated by numerical simulations.

Networks-on-Chip (NoC) have emerged as a replacement for traditional shared-bus designs for on-chip communications. As with all current VLSI design, however, reducing power consumption in NoCs is a critical challenge. One approach to reduce power is to dynamically scale the voltage and frequency of each network node or groups of nodes (DVFS). Another approach to reduce power consumption is to replace the balanced clock tree with a globally-asynchronous, locally-synchronous (GALS) clocking scheme. NoCs implemented with either of these schemes, however, tend to have high latencies as packets must be synchronized at intermediate nodes between source and destination. In this paper, we propose a novel router microarchitecture which offers superior performance versus typical synchronizing router designs. Our approach features Asynchronous Bypass Channels (ABCs) at intermediate nodes thus avoiding synchronization delay. We also propose several new network topology and routing algorithm that leverage the advantages of the bypass channel offered by our router design. Our experiments show that our design improves the performance of a conventional synchronizing design with similar resources by up to 26% at low loads and increases saturation throughput by up to 50%.

Theindex codingproblem has recently attracted a significant attention from the research community due to its theoretical significance and applications in wireless ad hoc networks. An instance of the index coding problem includes a sender that holds a set of information messagesX={x1,...,xk}and a set of receiversR. Each receiver(x,H)inRneeds to obtain a messagex Xand has priorside informationconsisting of a subsetHofX. The sender uses a noiseless communication channel to broadcast encoding of messages inXto all clients. The objective is to find an encoding scheme that minimizes the number of transmissions required to satisfy the demands of all the receivers. In this paper, we analyze the relation between the index coding problem, the more general network coding problem, and the problem of finding a linear representation of a matroid. In particular, we show that any instance of the network coding and matroid representation problems can be efficiently reduced to an instance of the index coding problem. Our reduction implies that many important properties of the network coding and matroid representation problems carry over to the index coding problem. Specifically, we show thatvector linear codesoutperform scalar linear index codes and that vector linear codes are insufficient for achieving the optimum number of transmissions.

We consider a communication system where two transmitters wish to exchange information through a central relay. The transmitter and relay nodes exchange data over synchronized, average power constrained additive white Gaussian noise channels with a real input with signal-to-noise ratio (SNR) of snr. An upper bound on the capacity is 1/2 log(1 + snr) bits per transmitter per use of the multiple access phase and broadcast phase of the bidirectional relay channel. We show that, using lattice codes and lattice decoding, we can obtain a rate of 1/2 log(1/2 + snr) bits per transmitter, which is essentially optimal at high SNR. The main idea is to decode the sum of the codewords modulo a lattice at the relay followed by a broadcast phase which performs Slepian-Wolf coding. We also show that if the two transmitters use identical lattices with minimum angle decoding, we can achieve the same rate of 1/2 log(1/2 + snr). The proposed scheme can be thought of as a joint physical-layer network-layer code which outperforms other recently proposed analog network coding schemes.

We consider the problem of establishing reliable multicast connections across a communication network. Our goal is to provide instantaneous recovery from single edge failures. With instantaneous recovery, all destination nodes can decode the packets sent by the source node even if one of the edges in the network fails, without the need of retransmission or rerouting. We build on the novel technique of network coding that offers significant advantages over standard solutions such as disjoint path routing and diversity coding. We begin by focusing on the case in which all network edges have equal capacity. For this case we present a network coding algorithm that constructs a robust network code over a small field. The algorithm takes advantage of special properties of the Maximum Rank Distance codes. Second, we consider a case of non-uniform edge capacities. We show that for the special case in which a small number of packets need to be transmitted from the source to destination nodes, special combinatorial properties of minimum coding networks can be exploited for constructing efficient robust network codes.

We study the problem of information flow in communication networks with noiseless links in which the dependency relations among the data flowing on the different network edges satisfy matroidal constraints. We present a construction that maps any given matroid to a network that admits vector linear network codes over a certain field if and only if the matroid has a multilinear representation over the same field. This new construction strengthens previous results in the literature and, thus, establishes a deeper connection between network coding and matroid theory. We also explore another, more general, mathematical construct referred to as FD-relation which is more suitable than matroids in capturing the dependency relations in general networks.

In this work, we study the computational perspective of network coding, focusing on two issues. First, we address the computational complexity of finding a network code for acyclic multicast networks. Second, we address the issue of reducing the amount of computation performed by network nodes. In particular, we consider the problem of finding a network code with the minimum possible number of encoding nodes, i.e. nodes that generate new packets by performing algebraic operations on packets received over incoming links.We present a deterministic algorithm that finds a feasible network code for a multicast network over an underlying graph G(V,E) in time 0(\E\kh + \V\k2h2+ h4k3(k + h)), where k is the number of destinations and h is the number of packets. Our algorithm improves the best known running time for network code construction. In addition, our algorithm guarantees that the number of encoding nodes in the obtained network code is upper- bounded by 0(h3k2). Next, we address the problem of finding integral and fractional network codes with the minimum number of encoding nodes. We prove that in the majority of settings this problem is NP-hard. However, we show that if h = O(1),k = O(1), and the underlying communication graph is acyclic, then there exists an algorithm that solves this problem in polynomial time.

At present, service providers have several incentives to extend the reach of long-lived MPLS paths across domains. Providers, however, will face a number of trade-offs while choosing the optimal set of MPLS paths to be established. In this paper, we focus on the multi-objective decision problem of maximizing the traffic demands to be covered by long-lived MPLS paths from a source domain S to its major destination domains, while minimizing the monetary costs incurred. The problem is formulated subject to a budget constraint, which assures the minimum expected revenue for the provider in S. A major advantage of the analysis and solution proposed in this paper is that it can be easily generalized, and applied in other settings where constrained problems considering maximum coverage vs. cost are critical.

This work addresses the computational complexity of achieving the capacity of a general network coding instance. We focus on the linear capacity, namely the capacity of the given instance when restricted to linear encoding functions. It has been shown [Lehman and Lehman, SODA 2005] that determining the (scalar) linear capacity of a general network coding instance is NP-hard. In this work we initiate the study of approximation in this context. Namely, we show that given an instance to the general network coding problem of linear capacity C, constructing a linear code of rate alphaC for any universal (i.e., independent of the size of the instance) constant alphales1 is ldquohardrdquo. Specifically, finding such network codes would solve a long standing open problem in the field of graph coloring. In addition, we consider the problem of determining the (scalar) linear capacity of a planar network coding instance (i.e., a general instance in which the underlying graph is planar). We show that even for planar networks this problem remains NP-hard.

In this paper we show that the Index Coding problem captures several important properties of the more general Network Coding problem. An instance of the Index Coding problem includes a server that holds a set of information messages X = {x1, …, xk} and a set of receivers R. Each receiver has some side information, known to the server, represented by a subset of X and demands another subset of X. The server uses a noiseless communication channel to broadcast encodings of messages in X to satisfy the receivers’ demands. The goal of the server is to find an encoding scheme that requires the minimum number of transmissions. We show that any instance of the Network Coding problem can be efficiently reduced to an instance of the Index Coding problem. Our reduction shows that several important properties of the Network Coding problem carry over to the Index Coding problem. In particular, we prove that both scalar linear and vector linear codes are insufficient for achieving the minimal number of transmissions.

We study broadcast systems that distribute a series of data updates to a large number of passive clients. The updates are sent over a broadcast channel in the form of discrete packets. We assume that clients periodically access the channel to obtain the most recent update. Such scenarios arise in many practical applications, such as distribution of traffic information and market updates to mobile wireless devices. Our goal is to design broadcast schedules that minimize the waiting time, i.e., the amount of time the client needs to wait in order to obtain the most recent update. We assume that each client has a different access pattern depending on the channel conditions, computing power, and storage capabilities. We introduce and analyze optimal universal schedules that guarantee low waiting time for any client, regardless of its behavior.

We present a distributed routing algorithm for finding two disjoint (primary and backup) QoS paths that run across multiple domains. Our work is inspired by the recent interest in establishing communication paths with QoS constrains spanning multiple IP/MPLS domains. In such settings, the routing decisions in each domain are made by the path computation element (PCE). We assume that the PCEs run a joint distributed routing protocol, decoupled from the BGP, which enables them to establish efficient paths across multiple domains. This study makes the following contributions. First, we present an aggregated representation of a multi-domain network that is small enough to minimize the link-state overhead, and, at the same time, is sufficiently accurate, so that the PCEs can find optimal disjoint QoS paths across multiple domains. Second, we present a distributed routing algorithm that uses the proposed representation to find disjoint paths in an efficient manner. Finally, we consider the problem of finding two disjoint paths subject to the export policy limitations, imposed by customer-provider and peer relationships between routing domains. We show that this problem can be efficiently solved by employing the concept of line graphs. To the best of our knowledge, this is the first scheme fully decoupled from BGP that enables to establish disjoint QoS IP/MPLS paths in a multi-domain environment with provable performance guarantees.

Let Aq(n, d) be the maximum order (maximum number of codewords) of a q-ary code of length n and Hamming distance at least d. And let A(n, d, w) that of a binary code of constant weight w. Building on results from algebraic graph theory and Erdos-ko-Rado like theorems in extremal combinatorics, we show how several known bounds on Aq(n,d) and A(n,d, w) can be easily obtained in a single framework. For instance, both the Hamming and Singleton bounds can derived as an application of a property relating the clique number and the independence number of vertex transitive graphs. Using the same techniques, we also derive some new bounds and present some additional applications.

With the standard approach for establishing multicast connections over a network, network nodes are utilized to forward and duplicate the packets received over the incoming links. Recently, there has been a significant interest in a novel paradigm of network coding. Network coding generalizes the traditional routing approach by allowing the network nodes to generate new packets by performing algebraic operations on packets received over the incoming links. It has been shown that network coding can increase the throughput of multicast communication. In this paper, we explore the benefits of network coding for improving the routing characteristics of VLSI designs. We demonstrate that when data has to be routed across the IC, it is often beneficial to perform network coding. Initial results demonstrate that network coding can result in a healthy reduction in wire length, wire area, interconnect power as well as the active area associated with the interconnects. This comes at a small delay penalty.

Modern society is heavily dependent on wireless networks for providing voice and data communications. Wireless data broadcast has recently emerged as an attractive way to disseminate dynamic data to a large number of clients. In data broadcast systems, the server proactively transmits the information on a downlink channel; the clients access the data by listening to the channel. Wireless data broadcast systems can serve a large number of heterogeneous clients, minimizing power consumption as well as protecting the privacy of the clients' locations. The availability and relatively low cost of antennas resulted in a number of potential threats to the integrity of the wireless infrastructure. In particular, the data broadcast systems are vulnerable to jamming, i.e., the use of active signals to prevent data broadcast. The goal of jammers is to cause disruption, resulting in long waiting times and excessive power consumption. In this paper we investigate efficient schedules for wireless data broadcast that perform well in the presence of a jammer. We show that the waiting time of client can be reduced by adding redundancy to the schedule and establish upper and lower bounds on the achievable minimum waiting time under different requirements on the staleness of the transmitted data

We investigate the network coding problem in a certain class of minimal multicast networks. In a multicast coding network, a source S needs to deliver h symbols, or packets, to a set of destinations T over an underlying communication network modeled by a graph G. A coding network is said to be h-minimal if it can deliver h symbols from S to the destination nodes, while any proper subnetwork of G can deliver at most h — 1 symbols to the set of destination nodes. This problem is motivated by the requirement to minimize the amount of network resources allocated for a multicast connections. We show that surprisingly, minimal multicast networks have unique properties that distinguish them from the general case of multicast networks. In particular, we show that it is possible to determine whether a 2-minimal network has a routing solution (i.e., a solution without encoding nodes) in polynomial time, while this problem is NP-hard in general. In addition, we show that if a 2-minimal network is planar, then the minimum size of the required field for linear network codes is at most 3. Also, we investigate several structural properties of 2-minimal networks and generalize our results for h > 2.

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 includes 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 h/sup 3/k/sup 2/. 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 h/sup 3/k/sup 2/. We show that the number of encoding nodes may depend both on h and k by presenting acyclic coding networks that require /spl Omega/(h/sup 2/k) 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)h/sup 3/k/sup 2/, where B is 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 /spl Nscr/P-hard problem.

In the multicast network coding problem, a source s needs to deliver h packets to a set of k terminals over an underlying network G. The nodes of the coding network can be broadly categorized into two groups. The first group includes 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 an acyclic coding network, the number of encoding nodes required to achieve the capacity of the network is bounded h3k2. 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 as we present acyclic instances of the multicast network coding problem in which Omega (h2k) encoding nodes are required. In the general case of coding networks with cycles, we show that the number of encoding nodes is limited by the size of the feedback link set, i.e., the minimum number of links that must be removed from the network in order to eliminate cycles. Specifically, we prove that the number of encoding nodes is bounded by (2 B + 1)h3k2, where B is the minimum size of the feedback link set. Finally, we observe that determining or even crudely approximating the minimum number of encoding nodes required to achieve the capacity for a given instance of the network coding problem is NP-hard

In this paper we study the distribution of dynamic data over a broadcast channel to a large number of passive clients. The data is simultaneously distributed to clients in the form of discrete packets, each packet captures the most recent state of the information source. Clients obtain the information by accessing the channel and listening for the next available packet. This scenario, referred to as discrete broadcast, has many practical applications such as the distribution of stock information to wireless mobile devices and downloading up-to-date battle information in military networks. Our goal is minimize the amount of time a client has to wait in order to obtain a new data packet, i.e., the waiting time of the client. We show that we can significantly reduce the waiting time by adding redundancy to the schedule. We identify universal schedules that guarantee low waiting time for any client, regardless of the access pattern. A key point in the design of data distribution systems is to ensure that the transmitted information is always up-to-date. Accordingly, we introduce the notion of staleness that captures the amount of time that passes from the moment the information is generated, until it is delivered to the client. We investigate the fundamental trade-off between the staleness and the waiting time. In particular, we present schedules that yield lowest possible waiting time for any given staleness constraint

There is a growing interest among service providers to offer new services with Quality of Service (QoS) guarantees that are also resilient to failures. Supporting QoS connections requires the existence of a routing mechanism, that computes the QoS paths, i.e., paths that satisfy QoS constraints (e.g., delay or bandwidth). Resilience to failures, on the other hand, is achieved by providing, for each primary QoS path, a set of alternative QoS paths used upon a failure of either a link or a node. The above objectives, coupled with the need to minimize the global use of network resources, imply that the cost of both the primary path and the restoration topology should be a major consideration of the routing process. We undertake a comprehensive study of problems related to finding suitable restoration topologies for QoS paths. We consider both bottleneck QoS constraints, such as bandwidth, and additive QoS constraints, such as delay and jitter. This is the first study to provide a rigorous solution, with proven guarantees, to the combined problem of computing QoS paths with restoration. It turns out that the widely used approach of disjoint primary and restoration paths is not an optimal strategy. Hence, the proposed algorithms construct a restoration topology , i.e., a set of bridges, each bridge protecting a portion of the primary QoS path. This approach guarantees to find a restoration topology with low cost when one exists.

Supporting quality of service (QoS) in large-scale broadband networks poses major challenges, due to the intrinsic complexity of the corresponding resource allocation problems. An important problem in this context is how to partition QoS requirements along a selected topology (path for unicast and tree for multicast). As networks grow in size, the scalability of the solution becomes increasingly important. This calls for efficient algorithms, whose computational complexity is less dependent on the network size. In addition, recently proposed precomputation-based methods can be employed to facilitate scalability by significantly reducing the time needed for handling incoming requests. We present a novel solution technique to the QoS partition problem(s), based on a "divide-and-conquer" scheme. As opposed to previous solutions, our technique considerably reduces the computational complexity in terms of dependence on network size; moreover, it enables the development of precomputation schemes. Hence, our technique provides a scalable approach to the QoS partition problem, for both unicast and multicast. In addition, our algorithms readily generalize to support QoS routing in typical settings of large-scale networks.

Networks are expected to meet a growing volume of requirements imposed by new applications such as multimedia streaming and video conferencing. Two essential requirements are support of quality of service (QoS) and resilience to failures. In order to satisfy these requirements, a common approach is to use two disjoint paths between the source and the destination nodes, the first serving as a primary path and the second as a restoration path. Such approach, referred to as path restoration, has several advantages, the major one being the ability to switch promptly from one path to another in the event of a failure. A major issue in this context is how to identify two paths that satisfy the QoS constraints imposed by network applications. Since network resources, e.g., bandwidth, are allocated along both primary and restoration paths, we need to consider also the overall network performance. Accordingly, in this paper we study the fundamental problem of finding two disjoint paths that satisfy the QoS constraints at minimum cost. We present approximation algorithms with provable performance guarantees for this fundamental network problem.

This paper investigates an efficient scheduling for sending dynamic data over lossless broadcast channels. A server transmits dynamic data periodically to a number of passive clients and thus the updated discrete packets are sent into a separate packet. The objective of this paper is to design universal schedules that minimize the time that passes between a client's request and the broadcast of a new item, independently of the client's behavior. From the results the optimal scheduling of high transmission rate for discrete broadcast data is obtained by considering adaptive clients.

There is a growing interest among service providers to offer new services with quality of service (QoS) guaranties that are also resilient to failures. Supporting QoS connections requires the existence of a routing mechanism, that computes the QoS paths, i.e., paths that satisfy QoS constraints (e.g., delay or bandwidth). Resilience to failures, on the other hand, is achieved by providing, for each primary QoS path, a set of alternative QoS paths used upon a failure of either a link or a node. The above objectives, coupled with the need to minimize the global use of network resources, imply that the cost of both the primary path and the restoration topology should be a major consideration of the routing process. We undertake a comprehensive study of problems related to finding suitable restoration topologies for QoS paths. We consider both bottleneck QoS constraints, such as bandwidth, and additive QoS constraints, such as delay and jitter. This is the first study to provide a rigorous solution, with proven guarantees, to the combined problem of computing QoS paths with restoration. It turns out that the widely used approach of disjoint primary and restoration paths is not an optimal strategy. Hence, the proposed algorithms construct a restoration topology, i.e., a set of bridges, each bridge protecting a portion of the primary QoS path. This approach guaranties to find a restoration topology with low cost when one exists. In addition to analysis, we test our approach also by way of simulations. The simulation results demonstrate that our proposed approximation algorithms identify QoS restoration paths whose cost is significantly smaller than those provided by alternative approaches.

Precomputation-based methods have recently been proposed as an instrument to facilitate scalability, improve response time, and reduce computation load on network elements. The key idea is, in effect, to reduce the time needed to handle an event by performing some computation in advance, i.e., prior to the event's arrival. Such computations are performed as background processes, enabling a solution to be provided promptly upon a request, through a simple, fast procedure. We investigate precomputation methods in the context of quality-of-service (QoS) routing. Precomputation is highly desirable for QoS routing schemes due to the high computational complexity of selecting QoS paths, and the need to provide a satisfactory path promptly upon a request. We consider two major settings of QoS routing. The first case is where the QoS constraint is of the "bottleneck" type, e.g., a bandwidth requirement, and network optimization is sought through hop minimization. The second is the more general setting of "additive" QoS constraints (e.g., delay) and general link costs. The paper mainly focuses on the first setting. We show that, by exploiting the typical hierarchical structure of large-scale networks, a substantial improvement can be achieved in terms of computational complexity. We consider networks with topology aggregation. We show that precomputation is a necessary element for any QoS routing scheme and establish a precomputation scheme appropriate for such settings. We consider the case of additive QoS constraints (e.g., delay) and general link costs. As the routing problem becomes NP-hard, we focus on /spl epsiv/-optimal approximations and derive a precomputation scheme that offers a major improvement over the standard approach.

Supporting quality of service (QoS) in large-scale broadband networks poses major challenges, due to the intrinsic complexity of the corresponding resource allocation problems. An important problem in this context is how to partition QoS requirements along a selected topology (path for unicast, tree for multicast). As networks grow in size, the scalability of the solution becomes increasingly important. This requires us to devise efficient algorithms, whose computational complexity is less dependent on the network size. In addition, recently proposed precomputation-based methods can be employed to facilitate scalability by significantly reducing the time needed for handling incoming requests. We present a novel solution technique to the QoS partition problem(s), based on a "divide and conquer" scheme. As opposed to previous solutions, our technique considerably reduces the computational complexity in terms of dependence on network size; moreover, it enables the development of precomputation schemes. Hence, our technique provides a scalable approach to the QoS partition problem, for both unicast and multicast. In addition, our algorithms readily generalize to support QoS routing in typical settings of large-scale networks.

A major algorithmic challenge posed by QoS routing is the need to promptly identify a suitable path upon a connection request, while at the same time ensuring that the selected path is satisfactory, both in terms of the connection's QoS requirements, as well as in terms of the global utilization of network resources. In many practical cases, a precomputation scheme offers a suitable solution to the problem: a background process prepares a database, which enables identification of a suitable path upon each connection request, through a simple, fast, procedure. While much work has been done in terms of path selection algorithms, the precomputation perspective has received little attention. Simplistic adaptations or standard algorithms turn out to be inefficient. Accordingly, we consider the precomputation perspective, focusing on two major settings of QoS routing. The first is the (practically important) special case where the QoS constraint is of the "bottleneck" type, e.g., a bandwidth requirement, and network optimization is sought through hop minimization. For this setting, the standard Bellman-Ford algorithm offers a straightforward precomputation scheme. However, we show that by exploiting the typical hierarchical structure of large-scale networks, one can achieve a substantial improvement in terms of computational complexity. Then, we turn to consider the more general setting of "additive" QoS constraints (e.g., delay) and general link costs. As the routing problem becomes NP-hard, we focus on /spl epsiv/-optimal approximations, and derive a precomputation scheme that offers a major improvement over the standard approach.