In a Hierarchical Inference (HI) system, an end device processes data samples using a local Deep Learning (DL) model. Only when the confidence of the local DL is less than a chosen threshold, it offloads the sample for remote DL inference on an edge server. By balancing the misclassifications and offloading costs, a HI system can improve accuracy and responsiveness and reduce bandwidth usage. To this end, prior work studied a HI learning problem for classification tasks, aiming to learn an optimal threshold on the confidence to minimize the cumulative costs. However, existing formulations considered (i) abstract offloading costs and (ii) assumed that the remote DL inference for an offloaded task is available by the end of each round. In contrast, considering that end devices are wirelessly connected to edge servers, we study a HI system with an offload queue where the offloading cost is implicitly modeled by the queue length. Also, we consider the practical setting, where the remote DL inference is obtained only after the task is served from the offload queue. For bounded but unknown arrival and service processes, we formulate the problem of average mismatch error minimization subject to queue stability. We propose a BOLD Hedge-Q policy based on Lyapunov optimization. The novelty of BOLD Hedge-Q lies in solving a delayed-feedback online learning problem — with sub-linear regret — that results from the Lyapunov drift-plus-penalty analysis. Given a penalty parameter V ≥ 1, we show that under BOLD Hedge-Q, the queue is upper bounded by V + λm, and the mismatch error is within an additive factor of O(1/V) from that of the optimal policy, where λm is the maximum number of arrivals in a round.

Random walk (RW)-based algorithms have long been popular in distributed systems due to low overheads and scalability, with recent growing applications in decentralized learning. However, their reliance on local interactions makes them inherently vulnerable to malicious behavior. In this work, we investigate an adversarial threat that we term the ``Pac-Man'' attack, in which a malicious node probabilistically terminates any RW that visits it. This stealthy behavior gradually eliminates active RWs from the network, effectively halting the learning process without triggering failure alarms. To counter this threat, we propose the Average Crossing (AC) algorithm--a fully decentralized mechanism for duplicating RWs to prevent RW extinction in the presence of Pac-Man. Our theoretical analysis establishes that (i) the RW population remains almost surely bounded under AC and (ii) RW-based stochastic gradient descent remains convergent under AC, even in the presence of Pac-Man, with a quantifiable deviation from the true optimum. Our extensive empirical results on both synthetic and real-world datasets corroborate our theoretical findings. Furthermore, they uncover a phase transition in the extinction probability as a function of the duplication threshold. We offer theoretical insights by analyzing a simplified variant of the AC, which sheds light on the observed phase transition.

We consider the problem of sharing correlated data under a perfect information-theoretic privacy constraint. We focus on redaction (erasure) mechanisms, in which data are either withheld or released unchanged, and measure utility by the average cardinality of the released set, equivalently, the expected Hamming distortion. Assuming the data are generated by a finite time-homogeneous Markov chain, we study the protection of the initial state while maximizing the amount of shared data. We establish a connection between perfect privacy and window-based redaction schemes, showing that erasing data up to a strong stationary time preserves privacy under suitable conditions. We further study an optimal sequential redaction mechanism and prove that it admits an equivalent window interpretation. Interestingly, we show that both mechanisms achieve the optimal distortion while redacting only a constant average number of data points, independent of the data length~$N$.

We consider a large-scale service marketplace with numerous servers that scale with the job arrival rate. Jobs arrive with private valuations representing their willingness to pay. In a centralized system, jobs are matched to available servers, and prices are set in a centralized manner to maximize revenue. We investigate whether similar scalability can be achieved in a distributed marketplace where jobs are randomly matched to servers, which set their own prices based on job valuations and system occupancy. Our results show that matching a job to a single randomly selected server leads to higher blocking, resulting in lower throughput and reduced revenue. We then examine matching jobs to two servers, which compete to provide service if unoccupied. We demonstrate the existence of a mean field equilibrium (MFE) in this setup, where servers strategically respond to competitors’ prices. We characterize the MFE and show that this two-server choice ensures lower blocking probabilities and higher system revenue. Our findings are validated through simulations illustrating a variety of operating scenarios.

This paper investigates the$(k,k)$fork-join scheduling scheme on a system of n parallel servers comprising both slow and fast servers. Tasks arriving in the system are divided into k sub-tasks and assigned to a random set of k servers, where each task can be assigned independently to a distinct slow or fast server with selection probability$p_{s}$or$1-p_{s}$, respectively. Our analysis demonstrates that the joint distribution of the stationary workload across any set of k queues becomes asymptotically independent as the number of servers n grows, with k scaling as$o\left ({{n^{\frac {1}{4}}}}\right)$. Under asymptotic independence, the limiting mean task completion time can be expressed as an integral. However, it is analytically challenging to compute the optimal selection probability$p_{s}^{\ast } $that minimizes this integral. To address this, we provide an upper bound on the limiting mean task completion time and identify the selection probability$\hat {p}_{s}$that minimizes this bound. We validate that this selection probability$\hat {p}_{s}$yields a near-optimal performance through numerical experiments.

We consider the setting of a distributed storage system where a single file is subdivided into smaller fragments of same size which are then replicated with a common replication factor across servers of identical cache size. An incoming file download request is sent to all the servers, and the download is completed whenever the request gathers all the fragments. At each server, we are interested in determining the set of fragments to be stored, and the sequence in which fragments should be accessed, such that the mean file download time for a request is minimized. We model the fragment download time as an exponential random variable independent and identically distributed for all fragments across all servers, and show that the mean file download time can be lower bounded in terms of the expected number of useful servers summed over all distinct fragment downloads. We present deterministic storage schemes that attempt to maximize the number of useful servers. We show that finding the optimal sequence of accessing the fragments is a Markov decision problem, whose complexity grows exponentially with the number of fragments. We propose heuristic algorithms that determine the sequence of access to the fragments which are empirically shown to perform well.

We consider a distributed storage system storing a single file, where the file is divided into equal sized fragments. The fragments are replicated with a common replication factor, and stored across servers with identical storage capacity. An incoming download request for this file is sent to all the servers, and it is considered serviced when all the unique fragments are downloaded. The download time for all fragments across all servers, is modeled as an independent and identically distributed (i.i.d.) random variable. The mean download time can be bounded in terms of the expected number of useful servers available after gathering each fragment. We find the mean number of useful servers after collecting each fragment, for a random storage scheme for replication codes. We show that the performance of the random storage for replication code achieves the upper bound for expected number of useful servers at every download asymptotically in number of servers for any storage capacity. Further, we show that the performance of this storage scheme is comparable to that of Maximum Distance Separable (MDS) coded storage.

Given the unpredictable nature of the nodes in distributed computing systems, some of the tasks can be significantly delayed. Such delayed tasks are called stragglers. Straggler mitigation can be achieved by redundant computation. In maximum distance separable (MDS) redundancy method, a task is divided into$k$subtasks which are encoded to$n$coded subtasks, such that a task is completed if any$k$out of$n$coded subtasks are completed. Two important metrics of interest are task completion time, and server utilization which is the aggregate completed work by all servers in this duration. We consider a proactive straggler mitigation strategy where$n_{0}$out of$n$coded subtasks are started at time 0 while the remaining$n-n_{0}$coded subtasks are launched when$\ell _{0}\le \min \left \{{n_{0},k}\right \}$of the initial ones finish. The coded subtasks are halted when$k$of them finish. For this flexible forking strategy with multiple parameters, we analyze the mean of two performance metrics when the random service completion time at each server is independent and distributed identically (i.i.d.) to a shifted exponential. From this study, we find a tradeoff between the metrics which provides insights into the parameter choices. Experiments on Intel DevCloud illustrate that the shifted exponential distribution adequately captures the random coded subtask completion times, and our derived insights continue to hold.

The ability of a P2P network to scale its throughput up in proportion to the arrival rate of peers has recently been shown to be crucially dependent on the chunk sharing policy employed. Some policies can result in low frequencies of a particular chunk, known as the missing chunk syndrome, which can dramatically reduce throughput and lead to instability of the system. For instance, commonly used policies that nominally “boost” the sharing of infrequent chunks such as the well-known rarest-first algorithm have been shown to be unstable. We take a complementary viewpoint, and instead consider a policy that simply prevents the sharing of the most frequent chunk(s), that we call mode-suppression. We also consider a more general version that suppresses the mode only if the mode frequency is larger than the lowest frequency by a fixed threshold. We prove the stability of mode-suppression using Lyapunov techniques, and use a Kingman bound argument to show that the total download time does not increase with peer arrival rate. We then design versions of mode-suppression that sample a small number of peers at each time, and construct noisy mode estimates by aggregating these samples over time. We show numerically that mode suppression stabilizes and outperforms all other recently proposed chunk sharing algorithms, and via integration into BitTorrent implementation operating over the ns-3 that it ensures stable, low sojourn time operation in a real-world setting.

We consider the setting where a master wants to run a distributed stochastic gradient descent (SGD) algorithm on n workers each having a subset of the data. Distributed SGD may suffer from the effect of stragglers, i.e., slow or unresponsive workers who cause delays. One solution studied in the literature is to wait at each iteration for the responses of the fastest k <; n workers before updating the model, where k is a fixed parameter. The choice of the value of k presents a trade-off between the runtime (i.e., convergence rate) of SGD and the error of the model. Towards optimizing the error-runtime trade-off, we investigate distributed SGD with adaptive k. We first design an adaptive policy for varying k that optimizes this trade-off based on an upper bound on the error as a function of the wallclock time which we derive. Then, we propose an algorithm for adaptive distributed SGD that is based on a statistical heuristic. We implement our algorithm and provide numerical simulations which confirm our intuition and theoretical analysis.

Straggler mitigation can be achieved by redundant computation. In MDS redundancy method, a task is divided into k sub-tasks which are encoded to n coded sub-tasks, such that a task is completed if any k coded sub-tasks are completed. Two important metrics of interest are task completion time, and server utilization cost which is the aggregate completed work by all servers in this duration. We consider a proactive straggler mitigation strategy where n0out of n coded sub-tasks are started at time 0 while the remaining n - n0coded sub-tasks are launched when ℓ0≤ min(n0, k) of the initial ones finish. The coded sub-tasks are halted when k of them finish. For this flexible forking strategy with multiple parameters, we analyze the mean of two performance metrics for the proposed forking strategy when the random service completion time at each server is independent and distributed identically to a shifted exponential. Our analysis demonstrates that the regime of n00= n), and is thus not a regime of interest. For n0≥ k, we find that there is a tradeoff between the two performance metrics and leads to decrease in mean server utilization cost at the expense of mean service completion time and an efficient choice of the parameters is helpful.

Samples from a high-dimensional AR[1] process are quantized and sent over a time-slotted communication channel of finite capacity. The receiver seeks to form an estimate of the process in real-time. We consider the slow-sampling regime where multiple communication slots occur between two sampling instants. We propose a successive update scheme which uses communication between sampling instants to update the estimates of the latest sample. We show that there exist quantizers that render the fast but loose version of this scheme, which updates estimates in every slot, universally optimal asymptotically. However, we provide evidence that most practical quantizers will require a judiciously chosen update frequency.

We consider the setting of a Master server, M, who possesses confidential data and wants to run intensive computations on it, as part of a machine learning algorithm for example. The Master wants to distribute these computations to untrusted workers who volunteered to help with this task. However, the data must be kept private in an information theoretic sense. Some of the workers may be stragglers, e.g., slow or busy. We are interested in reducing the delays experienced by the Master. We focus on linear computations as an essential operation in many iterative algorithms. We propose a solution based on new codes, called Staircase codes, introduced previously by two of the authors. Staircase codes allow flexibility in the number of stragglers up to a given maximum, and universally achieve the information theoretic limit on the download cost by the Master, leading to latency reduction. We find upper and lower bounds on the Master's mean waiting time. We derive the distribution of the Master's waiting time, and its mean, for systems with up to two stragglers. We show that Staircase codes always outperform existing solutions based on classical secret sharing codes. We validate our results with extensive implementation on Amazon EC2.

Real-time decision making relies on the availability of accurate data and, therefore, delivering status updates in a timely fashion is of paramount importance. The topic of real-time status updates has received much attention in recent years. This article contributes new results to this research area by studying the interplay between average timeliness and design decisions made at the physical layer, for unreliable communication channels. Specifically, this study explores the tension between the fact that more reliable transmissions with lower probabilities of decoding failure tend to improve timely delivery, unless these improvements come at the expense of significantly longer codewords. The average timeliness is adopted as an evaluation criterion, and a framework to efficiently compute the performance of various transmission schemes for the binary erasure channel is developed. We show that the average timeliness decreases as we increase the feedback rate in a hybrid ARQ scheme for a range of codeword lengths. This article also provides design guidelines for the codeword length selection for an hybrid ARQ scheme to improve the average information timeliness. Numerical examples are included to further illustrate the applicability of our findings.

A transmitter observing a sequence of independent and identically distributed random variables seeks to keep a receiver updated about its latest observations. The receiver need not be apprised about each symbol seen by the transmitter, but needs to output a symbol at each time instant t. If at time t the receiver outputs the symbol seen by the transmitter at time U (t) ≤ t, the age of information at the receiver at time t is t - U(t). We study the design of lossless source codes that enable transmission with minimum average age at the receiver. We show that the asymptotic minimum average age can be attained up to a constant gap by the Shannon codes for a tilted version of the original pmf generating the symbols, which can be computed easily by solving an optimization problem. Furthermore, we exhibit an example with alphabet X where age of a factor O(√(log |X|)) more than that achieved by our Shannon codes for the original pmf incur an asymptotic average codes. Underlying our prescription for optimal codes is a new variational formula for integer moments of random variables, which may be of independent interest. Also, we discuss possible extensions of our formulation to randomized schemes and to the erasure channel, and include a treatment of the related problem of source coding for minimum average queuing delay.

The performance of large-scale distributed compute systems is adversely impacted by stragglers when the execution time of a job is uncertain. To manage stragglers, we consider a multi-fork approach for job scheduling, where additional parallel servers are added at forking instants. In terms of the forking instants and the number of additional servers, we compute the job completion time and the cost of server utilization when the task processing times are assumed to have a shifted exponential distribution. We use this study to provide insights into the scheduling design of the forking instants and the associated number of additional servers to be started. Numerical results demonstrate orders of magnitude improvement in cost in the regime of low completion times as compared to the prior works.

We consider the status updates of a physical process over an unreliable channel. In this setting, one may not be able to reliably transmit the current state at all times. Instead, one is interested in the timeliness of the accurately received information. This is a setting for several cyber-physical system applications that require real-time monitoring and control. In this paper, we study periodic data transmission schemes at a single source which exploit the temporal correlation in the source messages. When the source has no feedback, it can periodically send the actual information, interspersed with differential messages. On the availability of receiver's feedback at the source, it can decide to send either the differential or the actual information at each transmission opportunity. For a fixed length coding, we show that the differential encoding improves the timeliness performance only if the receiver's feedback is available.

This paper focuses on the design and evaluation of pragmatic schemes for delay-sensitive communication. Specifically, this contribution studies the operation of data links that employ incremental redundancy as a means to shield information bits from the degradation associated with unreliable channels. While this inquiry puts forth a general methodology, exposition centers around erasure channels because they are well suited for analysis. Nevertheless, the goal is to identify both structural properties and design guidelines that are broadly applicable. Conceptually, this paper leverages a methodology, termed sequential differential optimization, aimed at identifying near-optimal block sizes for hybrid ARQ. This technique is applied to erasure channels and it is extended to scenarios where throughput is maximized subject to a constraint on the feedback rate. The analysis shows that the impact of the coding strategy adopted and the propensity of the channel to erase symbols naturally decouple when maximizing throughput. Ultimately, block size selection is informed by approximate distributions on the probability of decoding success at every stage of the incremental transmission process. This novel perspective, which rigorously bridges hybrid automatic repeat request and coding, offers a computationally efficient framework to select code rates and blocklengths for incremental redundancy. These findings are supported through numerical results.

Modern communication and computation systems often consist of large networks of unreliable nodes. Still, it is well known that such systems can provide aggregate reliability via redundancy. While duplication may increase the load on a system, it can lead to significant performance improvement when combined with the judicious management of extra system resources. Prime examples of this abstract paradigm include multi-path routing across communication networks, content access from multiple caches in delivery networks, and master/slave computations on compute clusters. Several recent contributions in the area establish bounds on the performance of redundant systems, characterizing the latency-redundancy tradeoff under specific load profiles. Following a similar line of research, this paper introduces new analytical bounds and approximation techniques for the latency-redundancy tradeoff for a range of system loads and a class of symmetric redundancy schemes, under the assumption of Poisson arrivals, exponential service-rates, and fork-join scheduling policy. The proposed approach can be employed to efficiently approximate the latency distribution of a queueing system at equilibrium. Various metrics can subsequently be derived for this system, including the mean and variance of the sojourn time, and the tail decay rate of the stationary distribution. This paper also establishes the stability region in terms of arrival rates for redundant systems with certain symmetries. Finally, it offers selection guidelines for design parameters to provide latency guarantees based on the proposed approximations. Findings are substantiated by numerical results.

For timely sensor update, the traditional approach is to send new information at every available opportunity. Recent research has shown that with limited receiver feedback, sensors can improve the update timeliness by transmitting differential information for slowly varying correlated sources. One can elect to transmit either the actual or the differential state information based on a differential encoding threshold for a general Markov source. This threshold captures the natural trade-off between differential transmission opportunities and the coding gains. Using matrix-geometric method, we find the limiting age distribution for a Markov source as a function of the encoding threshold, from which several other performance metrics of interest, such as mean age, peak age, and the probability of decoding failure can be derived.

The ability of a P2P network to scale its throughput up in proportion to the arrival rate of peers has recently been shown to be crucially dependent on the chunk sharing policy employed. Some policies can result in low frequencies of a particular chunk, known as the missing chunk syndrome, which can dramatically reduce throughput and lead to instability of the system. For instance, commonly used policies that nominally “boost” the sharing of infrequent chunks such as the well-known rarest-first algorithm have been shown to be unstable. Recent efforts have largely focused on the careful design of boosting policies to mitigate this issue. We take a complementary viewpoint, and instead consider a policy that simply prevents the sharing of the most frequent chunk(s). Following terminology from statistics wherein the most frequent value in a data set is called the mode, we refer to this policy as mode suppression. We prove the stability of this algorithm using Lyapunov techniques. We also design a distributed version that suppresses the mode via an estimate obtained by sampling three randomly selected peers. We show numerically that both algorithms perform well at minimizing total download times, with distributed mode suppression outperforming all others that we tested against.

As sensing and instrumentation play an increasingly important role in systems controlled over wired and wireless networks, the need to better understand delay-sensitive communication becomes a prime issue. Along these lines, this article studies the operation of data links that employ incremental redundancy as a practical means to protect information from the effects of unreliable channels. Specifically, this work extends a powerful methodology termed sequential differential optimization to choose near-optimal block sizes for hybrid ARQ over erasure channels. Furthermore, results show that the impact of the coding strategy adopted and the propensity of the channel to erase symbols naturally decouple when analyzing throughput. Overall, block size selection is motivated by normal approximations on the probability of decoding success at every stage of the incremental transmission process. This novel perspective, which rigorously bridges hybrid ARQ and coding, offers a pragmatic means to select code rates and blocklengths for incremental redundancy.

A transmitter observing a sequence of independent and identically distributed random variables seeks to keep a receiver updated about its latest observations. The receiver need not be apprised about each symbol seen by the transmitter, but needs to output a symbol at each time instant t. If at time t the receiver outputs the symbol seen by the transmitter at time U(t) ≤ t, the age of information at the receiver at time t is t-U(t). We study the design of lossless source codes that enable transmission with minimum average age at the receiver. We show that the asymptotic minimum average age can be attained (up to a constant bits gap) by Shannon codes for a tilted version of the original pmf generating the symbols, which can be computed easily by solving an optimization problem. Underlying our construction for minimum average age codes is a new variational formula for integer moments of random variables, which may be of independent interest.

Modern communication and computation systems consist of large networks of unreliable nodes. Yet, it is well known that such systems can provide aggregate reliability via information redundancy, duplicating paths, or replicating computations. While redundancy may increase the load on a system, it can also lead to major performance improvements through the judicious management of additional system resources. Two important examples of this abstract paradigm are content access from multiple caches in content delivery networks and master/slave computations on compute clusters. Many recent articles in the area have proposed bounds on the latency performance of redundant systems, characterizing the latency-redundancy tradeoff under specific load profiles. Following a similar line of research, this article introduces new analytical bounds and approximation techniques for the latency-redundancy tradeoff for a range of system loads and two popular redundancy schemes. The proposed framework allows for approximating the equilibrium latency distribution, from which various metrics can be derived including mean, variance, and the tail decay of stationary distributions.

We consider the setting of a master server who possesses confidential data (genomic, medical data, etc.) and wants to run intensive computations on it, as part of a machine learning algorithm for example. The master wants to distribute these computations to untrusted workers who have volunteered or are incentivized to help with this task. However, the data must be kept private (in an information theoretic sense) and not revealed to the individual workers. The workers may be busy and will take a random time to finish the task assigned to them. We are interested in reducing the aggregate delay experienced by the master. We focus on linear computations as an essential operation in many iterative algorithms. A known solution is to use a linear secret sharing scheme to divide the data into secret shares on which the workers can compute. We propose to use instead new secure codes, called Staircase codes, introduced previously by two of the authors. We study the delay induced by Staircase codes which is always less than that of secret sharing. The reason is that secret sharing schemes need to wait for the responses of a fixed fraction of the workers, whereas Staircase codes offer more flexibility in this respect. For instance, for codes with rate R = 1/2 Staircase codes can lead to up to 40% reduction in delay compared to secret sharing.

For timely sensor update, the traditional approach is to send new information at every available opportunity. Recent research has shown that with limited receiver feedback, sensors can improve the update timeliness by transmitting differential information for slowly varying correlated sources. In general, correlated sources can elect to transmit actual or differential state information depending on the current state. This encoding scheme generalizes the actual and differential updates schemes. Using this generalized scheme, we quantify the timeliness gains for some example sources. Further, we show a stochastic ordering among the actual update, the differential update, and the generalized update schemes.

For many applications in sensor networks and cyber-physical systems, receiving timely information is of utmost importance. In this article, we study data transmission schemes for a single source, sending periodic updates to a receiver through an unreliable channel. We consider two schemes that exploit the temporal correlation in the source messages, to send differential information to the receiver. Taking advantage of the receiver feedback in the first scheme, the source can decide between the differential and the actual information, to be sent at each transmission opportunity. Contrastingly, in the second scheme without any feedback, the source periodically sends the actual information, interspersed with differential messages. We observe that the differential encoding improves the timeliness performance, only if the receiver feedback is available.

As sensing, control, and actuation become further integrated into modern communication infrastructures, special consideration must be given to the type of traffic generated by associated devices. Real-time decision making relies on the availability of accurate data and, as such, delivering status updates in a timely fashion is of paramount importance. The topics of real-time status updates and low- delay communications have received much attention in recent years. Within this context, this article presents new results by looking at the interplay between average timeliness and design decisions made at the physical layer for unreliable communication channels. This study focuses on the natural tension between the protection afforded by additional redundancy and the decoding delay associated with longer codewords. The average timeliness is adopted as a performance criterion, and a framework to efficiently compute the performance of various transmission schemes for the binary erasure channel is developed. The problem formulation precludes the use of asymptotically long codewords typical of information theory. Yet, the presence of limited feedback does not seem to boost performance in the present context. Rather, having accurate channel estimates is key in minimizing average timeliness. Numerical examples are included in this article to further illustrate the applicability of the findings.

This paper considers the relationship between code-rate selection and queueing performance for communication systems subject to time-varying channel conditions. While error-correcting codes offer protection against channel uncertainties, there exists a natural tradeoff between the enhanced protection of low-rate codes and the rate penalty imposed by additional redundancy. In the limiting regime where codewords are asymptotically long, this tradeoff is well understood and characterized by the Shannon capacity. However, for delay-sensitive communication systems and finite block lengths, a complete characterization of this tradeoff is not fully developed. This paper offers a new perspective on the queueing performance of communication systems with finite block lengths operating over correlated erasure channels. A rigorous framework that links code rate to overall system performance for random codes is presented. Guidelines for code-rate selection in delay-sensitive systems are identified. These findings are supported by a numerical study.

Quantization is intrinsic to several data acquisition systems. This process is especially important in distributed settings, where observations must first be compressed before they are disseminated. There have been many practical successes in the area of quantization, including the acclaimed Lloyd-Max algorithm. This article adopts a different perspective and it explores quantization at a fundamental level, seeking to identify classes of problems for which efficient quantization is possible. The focus is primarily on positive random variables of unbounded support, where severe degradation may occur. Established properties of Banach spaces are exploited, together with the boundedness of probability measures, to prove that efficient quantization schemes necessarily exist in the fine-quantization regime. The results are algorithmic in nature and provide bounds on the number of bits necessary to achieve a desired level of performance.

The rapid increase of content delivery over the Internet has led to the proliferation of content distribution networks (CDNs). Management of CDNs requires algorithms for request routing, content placement, and eviction in such a way that user delays are small. We abstract the system of frontend source nodes and backend caches of the CDN in the likeness of the input and output nodes of a switch. In this model, queues of requests for different pieces of content build up at the source nodes, which route these requests to a cache that contains the requested content. For each request that is routed to a cache, a corresponding data file is transmitted back to the requesting source across links of finite capacity. Caches are of finite size, and the content of the caches can be refreshed periodically. Our objective is to design policies for request routing, content placement and content eviction with the goal of small user delays. Stable policies ensure the finiteness of the request queues, while good polices also lead to short queue lengths. We first design a throughput-optimal algorithm that solves the routing-placement-eviction problem. The design yields insight into the impact of different cache refresh policies on queue length, and we construct throughput optimal algorithms that engender short queue lengths. We illustrate the potential of our approach through simulations on different CDN topologies.

The traditional formulation of the total value of information transfer is a multi-commodity flow problem. Each data source is seen as generating a commodity along a fixed route, and the objective is to maximize the total system throughput under some concept of fairness, subject to capacity constraints of the links used. This problem is well studied under the framework of network utility maximization and has led to several different distributed congestion control schemes. However, this view of value does not capture the fact that flows may associate value, not just with throughput, but with link-quality metrics such as packet delay and jitter. In this work, the congestion control problem is redefined to include individual source preferences. It is assumed that degradation in link quality seen by a flow adds up on the links it traverses, and the total utility is maximized in such a way that the end-to-end quality degradation seen by each source is bounded by a value that it declares. Decoupling source-dissatisfaction and link-degradation through an effective capacity variable, a distributed and provably optimal resource allocation algorithm is designed to maximize system utility subject to these quality constraints. The applicability of the controller in different situations is supported by numerical simulations, and a protocol developed using the controller is simulated on ns-2 to illustrate its performance.

The traditional formulation of the total value of information transfer is a multi-commodity flow problem. Here, each data source is seen as generating a commodity along a fixed route, and the objective is to maximize the total system throughput under some concept of fairness, subject to capacity constraints of the links used. This problem is well studied under the framework of network utility maximization and has led to several different distributed congestion control schemes. However, this idea of value does not capture the fact that flows might associate value, not just with throughput, but with link-quality metrics such as packet delay, jitter and so on. The traditional congestion control problem is redefined to include individual source preferences. It is assumed that degradation in link quality seen by a flow adds up on the links it traverses, and the total utility is maximized in such a way that the quality degradation seen by each source is bounded by a value that it declares. Decoupling source-dissatisfaction and link- degradation through an ``effective capacity'' variable, a distributed and provably optimal resource allocation algorithm is designed, to maximize system utility subject to these quality constraints. The applicability of our controller in different situations is illustrated, and results are supported through numerical examples.

This paper considers the queueing performance of a system that transmits coded data over a time-varying erasure channel. In our model, the queue length and channel state together form a Markov chain that depends on the system parameters. This gives a framework that allows a rigorous analysis of the queue as a function of the code rate. Most prior work in this area either ignores block-length (e.g., fluid models) or assumes error-free communication using finite codes. This work enables one to determine when such assumptions provide good, or bad, approximations of true behavior. Moreover, it offers a new approach to optimize parameters and evaluate performance. This can be valuable for delay-sensitive systems that employ short block lengths.

Network coding has gained significant attention in recent years as a means to improve throughput, especially in multicast scenarios. These capacity gains are achieved by combining packets algebraically at various points in the network, thereby alleviating local congestion at the nodes. The benefits of network coding are greatest when the network is heavily utilized or, equivalently, when the sources are saturated so that there is data to send at every scheduling opportunity. Yet, when a network supports delay-sensitive applications, traffic is often bursty and congestion becomes undesirable. The lighter loads typical of real-time traffic with variable sources tend to reduce the returns of network coding. This work seeks to identify the potential benefits of network coding in the context of delay-sensitive applications. As a secondary objective, this paper also studies the cost of establishing network coding in wireless environments. For a network topology to be suitable for coding, links need to possess a proper structure. The cost of establishing this structure may require excessive radio resources in terms of bandwidth and transmit power. Bursty traffic together with structural cost tend to decrease the potential benefits of network coding. This paper describes how, for real-time applications over wireless networks, there exist network topologies for which it may be best not to establish a network structure tailored to network coding.

Network coding has gained significant attention in recent years as a means to improve throughput, especially in multicast scenarios. These capacity gains are achieved by combining packets algebraically at various points in the network, thereby alleviating local congestion at the nodes. The benefits of network coding are greatest when the network is heavily utilized or, equivalently, when the sources have infinite backlogs. However, if a network supports delay-sensitive applications, traffic is often sparse and congestion becomes undesirable. The lighter loads typical of real-time traffic with variable sources tend to reduce the returns of network coding. This work seeks to identify the potential benefits of network coding in the context of delay-sensitive applications. As a secondary objective, this paper also studies the cost of establishing network coding in wireless environments. For a network topology to be suitable for coding, links need to possess a proper structure. The cost of establishing this structure may require excessive wireless resources in terms of bandwidth and transmit power. Together, these effects decrease the potential benefits of network coding. For real-time applications over wireless networks, it may be best not to combine information at the nodes.

A wireless communication system in which multiple users cooperate to transmit information to a common destination is considered. The traffic generated by the users is subject to a stringent quality of service requirement, which is defined in terms of the asymptotic decay-rate of buffer occupancy. The performance of this communication system is analyzed, and the corresponding achievable rate-region for the two-user scenario is identified. A simple user-cooperation scheme that improves performance is proposed. This cooperative scheme is shown to significantly enlarge the achievable rate-region of the service constrained communication system, provided that the quality of the wireless link between cooperating users is better than the individual connections from the users to the intended destination. Numerical results further indicate that the gains of cooperative strategies can be substantial. This suggests that cooperation allows for a fair distribution of the wireless resources among active users.

Wireless systems offer a unique mixture of connectivity, flexibility, and freedom. It is therefore not surprising that wireless technology is being embraced with increasing vigor. For real-time applications, user satisfaction is closely linked to quantities such as queue length, packet loss probability, and delay. System performance is therefore related to, not only Shannon capacity, but also quality of service (QoS) requirements. This work studies the problem of resource allocation in the context of stringent QoS constraints. The joint impact of spectral bandwidth, power, and code rate is considered. Analytical expressions for the probability of buffer overflow, its associated exponential decay rate, and the effective capacity are obtained. Fundamental performance limits for Markov wireless channel models are identified. It is found that, even with an unlimited power and spectral bandwidth budget, only a finite arrival rate can be supported for a QoS constraint defined in terms of exponential decay rate