Coded caching is the distribution of content across a communication system using techniques from coding theory in order to create multicasting opportunities among the users receiving the content. This enables a multiplicative improvement over the classic uncoded caching with respect to the transmission rates required in the delivery phase of the content. Since its introduction, coded caching has eliceted significant research interest as a result of which several different schemes have been proposed over the last few years. This work focuses on the fundamental case of coded caching with uncoded prefetching. In this case, the users’ caches are filled with uncoded content during a prefetching phase in order to best serve the request made by each user during a subsequent delivery phase. This important case has recently received a complete information-theoretic characterization. However, reaching the information-theoretic optimality imposes a significant computational imbalance among the users. To mitigate this imbalance, we perform a complete computational analysis of the two major forms of coded caching with uncoded prefetching, namely centralized and decentralized. Furthermore, we propose a new information-theoretically optimal method for the delivery phase that achieves a significant computational improvement compared to the state of the art.

In this paper, we investigate transmission techniques for a fundamental cooperative cognitive radio network, i.e., a cognitive radio system where a Secondary user may act as relay for messages sent by the Primary user, hence offering performance improvement of Primary user transmissions, while at the same time obtaining more transmission opportunities for its own transmissions. Specifically, we examine the possibility of improving the overall system performance by employing network coding techniques. The objective is to achieve this while affecting Primary user transmissions only positively, namely: 1) avoid network coding operations at the Primary transmitter, hence avoiding increase of its storage requirements and keeping its complexity low, 2) keep the order of packets received by the Primary receiver the same as in the non cooperative case and 3) induce packet service times that are stochastically smaller than the packet service times induced in the non-cooperative case. A network coding algorithm is investigated in terms of achieved throughput region and it is shown to enlarge Secondary user throughput as compared to the case where the Secondary transmitter acts as a simple relay, while leaving the Primary user stability region unaffected. A notable feature of this algorithm is that it operates without knowledge of channel and packet arrival rate statistics. We further present a second network coding algorithm which increases the throughput region of the system under certain conditions on system parameters; however, the latter algorithm requires knowledge of channel and packet arrival rate statistics.

We consider the N -receiver broadcast erasure channel with feedback and message side information at the receivers prior to beginning of transmission. Specifically, the transmitter must deliver different, independent messages to each of the receivers, and each receiver knows a function of these messages before transmission begins. This situation can arise in multi-hop wireless networks, where a receiver may overhear transmissions consisting of possibly encoded combinations of messages (e.g., encoded using a network coding technique) prior to beginning of transmission over a given broadcast channel. We provide an outer bound to the capacity region of this system. For the case, where each message consists of a number of symbols taking values in a finite field and each receiver knows linear combinations of these symbols, the outer bound is given in terms of ranks of matrices expressing the linear combinations. For the latter case and when N=2 , the outer bound is tight under mild conditions on the limiting behavior of the ranks of matrices expressing the side information. We provide a capacity achieving code for this case. The special case, where each receiver either knows the entire message of another receiver or has no information about it, constitutes a generalization of the index coding problem that incorporates channel erasures. For this instance, and when there are no channel errors, we show that the outer bound reduces to the known maximum weighted acyclic induced subgraph bound.

In this paper, we describe a network coding scheme for the Broadcast Erasure Channel with multiple unicast stochastic flows, for a single source transmitting packets to N users with per-slot ACK/NACK feedback. This scheme performs only binary (XOR) operations and involves a network of queues, along with special rules for coding and moving packets among the queues, that ensure instantaneous decodability. Additionally, for the scheme to work, one has to specify which packets to select for encoding at each time, based on the received feedback. Contrary to prior work where this packet selection was explicitly specified a priori, we employ a backpressure-type policy that makes the selection based only on queue backlogs. We next provide a stability region outer bound for arbitrary N and erasure patterns and show that this bound effectively coincides with a bound on the system's information-theoretic capacity region (accounting for idle slots). Finally, for N=4 and i.i.d. erasures, we provide a policy that achieves the stability outer bound and employs the proposed XOR scheme using a restricted set of coding rules.

Exchange of services and resources in, or over, networks is attracting nowadays renewed interest. However, despite the broad applicability and the extensive study of such models, e.g., in the context of P2P networks, many fundamental questions regarding their properties and efficiency remain unanswered. We consider such a service exchange model and analyze the users' interactions under three different approaches. First, we study a centrally designed service allocation policy that yields the fair total service each user should receive based on the service it offers to the others. Accordingly, we consider a competitive market where each user determines selfishly its allocation policy so as to maximize the service it receives in return, and a coalitional game model where users are allowed to coordinate their policies. We prove that there is a unique equilibrium exchange allocation for both game theoretic formulations, which also coincides with the central fair service allocation. Furthermore, we characterize its properties in terms of the coalitions that emerge and the equilibrium allocations, and analyze its dependency on the underlying network graph. That servicing policy is the natural reference point to the various mechanisms that are currently proposed to incentivize user participation and improve the efficiency of such networked service (or, resource) exchange markets.

The aim of this paper is to develop link layer transmission schemes for hybrid optical wireless (OW)/radio frequency (RF) systems, with constraints on both per-link and total average power consumption at the transmitter. In this context, we adopt a timeslot structure with a queue for storing the data packets for transmission and model the hybrid channel as an erasure channel with parameters varying along the time-slots according to a Markov chain. Then, a stochastic optimization problem is formulated, where intelligent decisions regarding the number of the packets admitted in the queue and the power levels used in every link, are taken by the hybrid transmitter in each slot. The objective of this formulation is to design a control policy that maximizes the transmitter throughput, while satisfying the power constraints as well. A solution is offered by using the Lyapunov optimization framework and an on-line transmission algorithm is developed. The proposed transmission algorithm takes decisions based only on the status of the queue and the statistical parameters of the OW/RF channel in each time-slot, without requiring any knowledge of the underlying Markov chain of the channel process, or the statistics of the packet arrival process. Furthermore, in order to alleviate the requirement for full feedback at the transmitter, i.e., feedback for every successfully received packet, which is critical for the accurate queue update, we extend our analysis and incorporate reduced-feedback coding schemes. The proposed transmission policy in this scenario still meets the throughput objective and satisfies the power consumption constraints, while a tradeoff between transmission delays and feedback requirements is revealed.

We study a one-hop broadcast channel with two receivers. The receivers have side information obtained by overhearing wireless channels. The relay takes control decisions by coding transmissions based on its knowledge of side information in the receivers. We consider two control mechanisms. In the ACK system, the relay has definite knowledge of side information announced via overhearing reports. In the NACK system, the relay has statistical knowledge of side information and receives feedback after every decoding failure. Our contribution is as follows. We provide the minimal evacuation times for the two systems and obtain analytical expressions of the throughput region for the ACK and the code-constrained region for the NACK system. When the transmission rates are the same (r1= r2) or when the receiver with the highest transmission rate has perfect side information (pf=1), we show that the two regions are equal. We then provide simple joint xor coding and scheduling policies that achieve those regions and, thus, are throughput optimal. Subsequently, we evaluate the report overhead performance for both mechanisms and reflect on the involved tradeoff with throughput. Ultimately, we demonstrate by simulations that the proposed throughput optimal policies can be appropriately enhanced to have good delay properties, particularly for protocols that utilize sequenced packet delivery.

We consider a system where packets (jobs) arrive for processing using one of the policies in a given class. We study the connection between the minimal evacuation time and the stability region of the system and show that evacuation time optimal policies can be used for stabilizing the system (and for characterizing its stability region) under broad assumptions. Conversely, we show that while a stabilizing policy can be suboptimal in terms of evacuation time, one can always design a randomized version of any stabilizing policy that achieves an optimal evacuation time in the asymptotic regime when the number of evacuated packets scales to infinity.

In cognitive radio networks, secondary users (SUs) may cooperate with the primary user (PU) so that the success probability of PU transmissions are improved, while SUs obtain more transmission opportunities. However, SUs have limited power resources and, therefore, they have to take intelligent decisions on whether to cooperate or not and at which power level, to maximize their throughput. Cooperation policies in this framework require the solution of a constrained Markov decision problem with infinite state space. In our work, we restrict attention to the class of stationary policies that take randomized decisions of an SU activation and its transmit power in every time slot based only on spectrum sensing. Assuming infinitely backlogged SUs queues, the proposed class of policies is shown to achieve the maximum throughput for the SUs, while significantly enlarging the stability region of PU queue. The structure of the optimal policies remains the same even if the assumption of infinitely backlogged SU queues is relaxed. Furthermore, the model is extended for the case of imperfect channel sensing. Finally, a lightweight distributed protocol for the implementation of the proposed policies is presented, which is applicable to realistic scenarios.

This paper investigates link layer transmission schemes for hybrid optical wireless (OW)/radio frequency (RF) systems with constraints on both per-link and total power consumption at the transmitter. Assuming timeslot structure and using a queue for storing the random data packet arrivals, we formulate a stochastic optimization problem where intelligent control decisions are taken by the hybrid transmitter in each slot, regarding the number of the packets admitted in its queue and the power levels used in each link. The aim of this formulation is to design a control policy that maximizes the transmitter throughput, while satisfying its power constraints as well. A solution is offered by using the Lyapunov optimization framework. An on-line transmission algorithm is derived, which takes control decisions based only on the status of the transmitter queue and the erasure probabilities of the OW and RF links. The proposed algorithm meets the desired throughput objective by efficiently exploiting both links, while provides explicit power consumption guarantees.

In cognitive radio networks, secondary users (SUs) may cooperate with the primary user (PU) in order to obtain more transmission opportunities and thus maximize their throughput. The synergy consists in the following: the SU opts to cooperate by using its own transmit power to improve the probability of successful transmission of the PU. By increasing the probability of successful packet transmission for the PU, the SU essentially increases the service rate of the PU queue and thus, for given packet arrival rate, it increases the chances that it will be empty, and the channel will be free to use. Due to power limitations however, SUs have to take intelligent decisions on whether to cooperate or not and at which power level. Cooperation policies in this framework require the solution of a constrained Markov decision problem with infinite state space. In our work, we restrict attention to the class of stationary policies that take randomized decisions of an SU activation and its transmit power in every time slot based only on spectrum sensing. The proposed class of policies is shown to achieve the same set of SU rates as the more general policies, while significantly enlarging the stability region of the PU queue. Finally, a lightweight distributed protocol based on the proposed class of policies is presented, which is amenable to implementation in realistic scenarios.

We study the case of a three-user broadcast erasure channel with multiple unicast traffic sessions, where feedback from the users is fed back to the transmitter in the form of positive acknowledgment (ACK)/negative acknowledgment (NACK) messages. The capacity region of this system has been recently derived and two capacity-achieving coding algorithms employing intersession linear network coding have been proposed. Since these algorithms suffer from large computational complexity and decoding delay, our aim, in this paper, is to design a coding algorithm with reduced computational complexity and a low decoding delay that achieves a comparable rate region to the former algorithms. We exclusively consider algorithms that require no knowledge of channel statistics, only perform XOR operations among the packets, and allow for instantaneous decoding by any receiver that successfully receives a packet. We present such an algorithm, named IXOR, which operates on a specially constructed network of virtual queues and, through intelligent packet combining, achieves the capacity under a general condition, which is satisfied in the following settings: spatially independent identically distributed erasure channels with arbitrary values of erasure probability; and spatially independent erasure channels where the maximum erasure probability does not exceed 8/9.

We study an 1-hop broadcast channel with two receivers. Due to overhearing channels, the receivers have side information which can be leveraged by interflow network coding techniques to provide throughput increase. In this setup, we consider two different control mechanisms, the deterministic system, where the contents of the receivers' buffers are announced to the coding node via overhearing reports and the stochastic system, where the coding node makes stochastic control decisions based on statistics and the performance is improved via NACK messages. We study the minimal evacuation times for the two systems and obtain analytical expressions of the throughput region for the deterministic and the code-constrained region for the stochastic. We show that maximum performance is achieved by simple XOR policies. For equal transmission rates r1= r2, the two regions are equal. If r1≠ r2, we showcase the tradeoff between throughput and overhead.

In this paper we describe a network coding scheme for the Broadcast Erasure Channel with multiple unicast stochastic flows, for the case of a single source transmitting packets to N users, where per-slot feedback is fed back to the transmitter in the form of ACK/NACK messages. This scheme performs only binary (XOR) operations and includes special rules for coding packets that ensure instantaneous decodability. Drawing on the results of network stability under statistical overhearing, we provide a stabilizing policy using this coding scheme. Furthermore, we show that, for N = 4 and i.i.d. erasure events, the stability region of such a system effectively coincides with its information-theoretic capacity region, and provide a stabilizing policy that employs this XOR-based scheme.

We consider the N-user broadcast erasure channel with N unicast sessions (one for each user) where receiver feedback is regularly sent to the transmitter in the form of ACK/NACK messages. We first provide a generic outer bound to the capacity of this system; we then propose a virtual-queue-based inter-session mixing coding algorithm, determine its rate region, and show that it achieves capacity under certain conditions on channel statistics, assuming that instantaneous feedback is known to all users. Removing this assumption results in a rate region that asymptotically differs from the outer bound by 1 bit as L → ∞, where L is the number of bits per packet (packet length). For the case of arbitrary channel statistics, we present a modification of the previous algorithm whose rate region is identical to the outer bound for N = 3, when instant feedback is known to all users, and differs from the bound by 1 bit as L → ∞, when the three users know only their own ACK. The proposed algorithms do not require any prior knowledge of channel statistics.

We consider a source node broadcasting to two receivers over a general erasure channel with receiver feedback. We characterize the capacity region of the channel and construct algorithms based on linear network coding (either randomized or depending on channel dynamics) that achieve this capacity. We then consider stochastic arrivals at the source for the two destinations and characterize the stable throughput region achieved by adapting the same algorithms that achieve capacity. Next, we modify these algorithms to improve their delay performance and characterize their stable throughput regions. Although the capacity and stability regions obtained by the algorithms are not always identical (because of the extra overhead needed for the algorithms to handle stochastic traffic), they are within a few bits of each other and have similar forms. This example exhibits an unusual relationship between capacity and stability regions and extends similar prior studies for multiple access channels.

We consider a system where jobs (packets) arrive for processing using one of the policies in a given class. We study the connection between the minimal evacuation times and the stability region of the system under the given class of policies. The result is used to establish the equality of information theoretic capacity region and system stability region for the multiuser broadcast erasure channel with feedback.

We consider the N-user memoryless broadcast erasure channel with N unicast sessions (one for each user) where receiver feedback is sent to the transmitter in the form of ACK/NACK messages. We first provide a generic outer bound to the capacity of this system; using concepts from network coding, we then propose a session-mixing coding algorithm applied on specially constructed and maintained virtual queues (at the transmitter side), determine its throughput region and show that it achieves capacity under certain conditions on channel statistics (assuming that instantaneous feedback is known to all users). The algorithm requires no knowledge of channel statistics or future events.

We consider a noise-limited wireless sensor network that consists of battery-operated nodes which can route information to a mobile sink in a multi-hop fashion. The problem of maximizing the network's lifetime, defined as the period of time during which the network can route a feasible flow to each sink location subject to power/energy constraints, is cast into a linear program, reduced into a simpler equivalent form and solved via dual decomposition. The unknowns are the sink sojourn times and the routing flow vector for each sink location. The presence of a mobile sink presents new challenges but the problem structure can still be exploited to find the optimal solution. A distributed algorithm based on the subgradient method and using the sink as leader is proposed and its performance is evaluated through simulation for random networks. The algorithm's requirements in memory are also provided.

We examine the performance of a dual-hop nonregenerative system with adjustable relay gain, subject to power constraints. An optimization problem is formulated and solved algorithmically for the binary phase-shift keying bit-error rate utility. The model allows for arbitrary channel statistics. Emphasis is placed on the relation between the optimal solutions obtained when observing the channels of either the first or both hops, as well as the comparison with easily implementable heuristic policies. Numerical results indicate that simple heuristics perform well for a wide range of signal-to-noise ratio (SNR), except for certain high-SNR cases. Finally, the effect of independent channel assumption on system performance is evaluated.

This paper examines the performance of a dualhop, noise-limited, non-regenerative system where the relay gain is allowed to vary as an unknown deterministic function of the channel states, subject to instantaneous (i.e. peak) and average power constraints, the latter directly affecting battery lifetime in wireless systems. A convex optimization problem, in terms of a generic performance metric, is formulated and solved algorithmically for the Signal-to-Noise Ratio (SNR), Shannon rate and BPSK Bit-Error-Rate (BER) utilities. The presented model allows for arbitrary statistics of the fading channels, including correlation between them. Special emphasis is placed on the relation between the optimal solutions obtained when observing the channels of either the first or both hops. The regions in channel state space where zero and full power is allocated are determined in closed form, with numerical results being presented for the Shannon rate and BER utilities. It is observed that, for sufficiently high first hop SNR, monitoring both channels instead of just the first hop can lead to a significant performance increase.

In this paper, we investigate structural properties of multicast trees that give rise to the so-called multicast power law. The law asserts that the ratio R(n) of the average number of links in a multicast tree connecting the source to n destinations to the average number of links in a unicast path, satisfies asymptotically R(n)/spl ap/cn/sup /spl phi//, 0</spl phi/<1. In order to obtain a better insight, we first analyze some simple multicast tree topologies, which under appropriately chosen parameters give rise to the multicast power law. The asymptotic analysis of R(n) in this case indicates that it is very difficult to infer the validity of power law by observing graphs of R(n) alone. Next we introduce a new metric, "reachability degree," which is easy to measure and applicable to general networks where multicast trees are constructed as subtrees of a given spanning tree which we call Global Multicast Tree. The reachability degree is indicative of the structure of the Global Multicast Tree. We show that this metric provides a more reliable means for inferring the validity of the power law. Finally, we perform experiments on real and simulated networks to demonstrate the use of the new metric.

A single commodity network that models the information flow in an arbitrary topology sensor field that collects and forwards information to a backbone through certain designated gateway nodes is considered. Resilient operation in overload stress situations caused by unpredictable traffic or topology variations is investigated. That amounts to studying the network in instability mode, where the traffic load distribution is outside the throughput region. A fluid model is adopted where superflows model traffic forwarding and backlog formations at the network level. Quantitative performance metrics of the overload including throughput, lexicographic minimization, most balanced allocation, and amount of lost traffic due to buffer overflow are considered to capture the information loss process due to overflow in the network. Optimal superflows with respect to these metrics are characterized and a distributed asynchronous algorithm that computes such superflows is given. The characterization of the optimal superflow amounts to obtaining a structural decomposition of the network in a sequence of disjoint subregions with decreasing overload such that traffic flows only from regions of higher overload to regions of lower overload. The optimal superflow represents the smoothest trajectory to overflow, followed by the network in case of instability.

The network planning problem of placing replicated servers with QoS constraints is considered. Each server site may consist of multiple server types with varying capacities and each site can be placed in any location among those belonging to a given set. Each client can be served by more than one location as long as the round-trip delay of data requests satisfies predetermined upper bounds. Our main focus is to minimize the cost of using the servers and utilizing the link bandwidth, while serving requests according to their delay constraint. This is an NP-hard problem. A pseudopolynomial and a polynomial algorithm that provide guaranteed approximation factors with respect to the optimal for the problem at hand are presented

We consider the operation of a network in overload situations, that is, when the incoming traffic is outside the feasibility region determined by the network topology. In such a situation nodes will be overloaded and it is important to maintain a balanced network overload while ensuring that maximum amount of traffic reaches the sink nodes. We formulate the problem as lexicographic optimization of node overloads, study the properties of the solution and provide a distributed flow reallocation mechanism whose node overloads converge to the optimal solution

We consider the problem of precomputing constrained widest paths and multicast trees in a communication network. Precomputing and storing of the relevant information minimizes the computational overhead required to determine an optimal path when a new connection request arrives. We evaluate algorithms that precompute paths with maximal bandwidth (widest paths), which in addition satisfy given end-to-end delay constraints. We analyze and compare both the worst case and average case performance of the algorithms. We also show how the precomputed paths can be used to provide computationally efficient solutions to the constrained widest multicast tree problem. In this problem, a multicast tree with maximal bandwidth (widest multicast tree) is sought, which in addition satisfies given end-to-end delay constraints for each path on the tree from the source to a multicast destination.

We consider the problem of scheduling packets over channels with time-varying quality. This problem has received a lot of attention lately in the context of devising methods for providing quality of service in wireless communications. Earlier work dealing with this problem considered two cases. One case is that the arrival rate vector is in the throughput region and then policies that stabilize the system are pursued. The other case is that all packet queues are saturated and then policies that optimize an objective function of the channel throughputs are investigated. In this paper, we address the case where no assumption on the arrival rates is made. We obtain a scheduling policy that maximizes the weighted sum of channel throughputs. Under the optimal policy, in the general case, the system may operate in a regime where some queues are stable, while the other become saturated. If stability for the whole system is at all possible, it is always achieved. The optimal policy is a combination of a criterion that gives priorities based on queue lengths and a strict priority rule. The scheduling mechanism switches between the two criteria based on thresholds on the queue lengths and is modulated by the availability of the channels. The analysis of the operation of the system involves the study of a vector process which in steady state has some of its components stable while others are unstable. We adopt a novel model for time-varying channel availability that dispenses with the statistical assumptions and makes a rigorous description of system dynamics possible.

The problem of routing in a network where QoS constraints are placed on network traffic is considered. We provide two optimal algorithms that are based on determining the discontinuities of functions related to the optimization at hand. The proposed algorithms have pseudopolynomial worst case running time and for a wide variety of tested networks they have fairly satisfactory running times. They perform significantly better than the algorithm based on the direct application of the dynamic programming equations and can also be used in conjunction with known polynomial-time approximation algorithms to provide good average case behavior, in addition to guaranteeing polynomial worst-case running time.

The problem of scheduling packets over a number of channels with time varying connectivity is considered. Policies proposed for this problem either stabilize the system when the arrival rates are within the stability region, or optimize an objective function under the assumption that all channel queues are saturated. We address the realistic situation where it is not known a priori whether the channel queues are saturated or not, and provide a scheduling policy that maximizes the weighted sum of channel throughputs. We employ a burstiness-constrained channel model that allows us to dispense of statistical assumptions and simplifies the proofs.

Given the emergence of IP networks and the Internet as the multi-service network of choice, it is plausible consider its use for transporting demanding multimedia traffic with high bandwidth and low delay and packet loss requirements. Emerging technologies for quality of service such as differentiated services and MPLS can be used for premium quality traffic. We present a traffic engineering and control system that starts from services agreed with customers and provisions the network according to the expected traffic demand so as to meet the requirements of contracted services while optimizing the use of network resources. We devise a non-linear programming formulation of the problem and show through simulations that we can achieve the objectives and meet the requirements of demanding customer traffic.

There are various techniques for adapting the transmission rate of an application while maintaining the perceived quality at the receiver at acceptable levels. Shared channel systems can use this rate adaptation capability to increase the number of concurrent applications in the system. This can be achieved by appropriately modifying the rate of the already running applications when a new connection arrives in the system. We present an analytical model for a class of algorithms for channel sharing by rate adaptive applications. We provide means for calculating performance measures related to the quality of reception of an application. We also present the design of algorithms that ensure fair channel sharing while keeping the application performance within acceptable levels.

We consider the problem of allocating bandwidth between two endpoints of a backbone network so that no parts of the network are unnecessarily loaded. We formulate the problem as lexicographic optimization and develop algorithms for its solution. The solution consists of: (1) identifying a cut in the network where the optimal load can be determined on all the links of the cut and (2) considering the same problem for each of the subnetworks to which the cut is dividing the original network.

As the Internet evolves, a key consideration is support for services with guaranteed quality of service (QoS). The proposed differentiated services (DiffServ) framework, which supports aggregate traffic classes, is seen as the key technology to achieve this. DiffServ currently concentrates on control/data plane mechanisms to support QoS but also recognises the need for management plane aspects through the bandwidth broker (BB). In this paper we propose a model and architectural framework for supporting end-to-end QoS in the Internet through a combination of both management and control/data plane aspects. Within the network we consider control mechanisms for traffic engineering (TE) based both on explicitly routed paths and on pure node-by-node layer 3 routing. Management aspects include customer interfacing for service level specification (SLS) negotiation, network dimensioning, traffic forecasting and dynamic resource and routing management. All these are policy-driven in order to allow for the specification of high-level management directives. Many of the functional blocks of our architectural model are also features of BBs, the main difference being that a BB is seen as driven purely by customer requests whereas, in our approach, TE functions are continually aiming at optimising the network configuration and its performance. As such, we substantiate the notion of the BB and propose an integrated management and control architecture that will allow providers to offer both qualitative and quantitative QoS-based services while optimising the use of underlying network resources.

We consider the problem of allocating bandwidth between two endpoints of a backbone network so that no parts of the network are unnecessarily loaded. We formulate the problem as lexicographic optimization, and develop algorithms for its solution. The solution consists of (a) identifying a cut in the network where the optimal load can be determined on all the links of the cut, and (b) considering the same problem in each of the subnetworks to which the cut is dividing the original network.

The concept of tracking fluid policies by packetized policies is extended to input queueing switches. It is considered that the speedup of the switch is one. One of the interesting applications of the tracking policy in TDMA satellite switches is elaborated. For the special case of 2/spl times/2 switches, it is shown that a tracking nonanticipative policy always exists. It is found that, in general, nonanticipative policies do not exist for switches with more than two input and output ports. For the general case of N/spl times/N switches, a heuristic tracking policy is provided. The heuristic algorithm is based on two notions: port tracking and critical links. These notions can be employed in the derivation of other heuristic tracking policies as well. Simulation results show the usefulness of the heuristic algorithm and the two basic concepts it relies on.

The concept of tracking policies for fluid policies is extended to input queueing switches. It is considered that the speed up of the switch is 1. For the special case of 2/spl times/2 switches it is shown that tracking policy always exists. One of the interesting applications of the tracking policy in TDMA satellite switches is elaborated upon. For the general case of N/spl times/N switches a heuristic tracking policy is provided. The heuristic algorithm is based on two notions of port tracking and critical links. These notions can be employed in derivation of other heuristic tracking policies as well. Simulation results present the usefulness of the heuristic algorithm and the two basic concepts it relies upon.

In distributed multimedia servers where client requests for different video streams may have different probabilities, placement of video streams is an important parameter because it may result in unbalanced requests to the system's stations, and thus to high blocking probabilities of requests. We present a method, MMPacking, to balance traffic load and storage use in a distributed server environment. Since different video streams are requested by clients with different rates, video stream replication is used to balance the traffic patterns of the stations; thus, the requests and I/O usage of the stations are balanced, since replication allows requests for the same video stream to be routed to different stations. MMPacking achieves load balancing by producing at most N-1 replicas of video streams in a system with N servers. These replicas are distributed among the stations so that storage balancing is achieved as well, since no station stores more than two video streams more than any other station in the system.

This paper is motivated by the need to provide per-session quality of service guarantees in fast packet-switched networks. We address the problem of characterizing and designing scheduling policies that are optimal in the sense of minimizing buffer and/or delay requirements under the assumption of commonly accepted traffic constraints. We investigate buffer requirements under three typical memory allocation mechanisms which represent tradeoffs between efficiency and complexity. For traffic with delay constraints we provide policies that are optimal in the sense of satisfying the constraints if they are satisfiable by any policy. We also investigate the tradeoff between delay and buffer optimality, and design policies that are "good" (optimal or close to) for both. Finally, we extend our results to the case of "soft" delay constraints and address the issue of designing policies that satisfy such constraints in a fair manner. Given our focus on packet switching, we mainly concern ourselves with nonpreemptive policies, but one class of nonpreemptive policies which we consider is based on tracking preemptive policies. This class is introduced and may be of interest in other applications as well.

We consider a slotted ring that allows simultaneous transmissions of messages by different nodes, known as ring with spatial reuse. To alleviate fairness problems that arise in such networks, policies have been proposed that operate in cycles and guarantee that a certain number of packets, not exceeding a given number called a quota, will be transmitted by every node in every cycle. We provide sufficient and necessary stability conditions that implicitly characterize the stability region for such rings. These conditions are derived by extending a technique developed for some networks of queues satisfying a monotonicity property. Our approach to instability is novel and its peculiar property is that it is derived from the instability of a dominant system. Interestingly, the stability region depends on the entire distribution of the message arrival process and the steady-state average cycle lengths of lower dimensional systems, leading to a region with nonlinear boundaries, the exact computation of which is in general intractable. Next, we introduce the notions of essential and absolute stability region. An arrival rate vector belongs to the former region if the system is stable under any arrival distribution with this arrival vector, while it belongs to the latter if there exists some distribution with this rate vector for which the system is stable. Using a linear programming approach, we derive bounds for these stability regions that depend only on conditional average cycle lengths. For the case of two nodes, we provide closed-form expressions for the essential stability region.

We consider the design of efficient channel allocation algorithms in personal communication networks (PCN) where the cells have varying traffic loads. A common communication channel is to be dynamically shared between the cells. We propose a distributed intercell channel allocation policy that is easy to implement through the use of simple signaling between neighboring cells. For cells arranged in a line, we show that the proposed policy achieves maximum throughput. The same is true when the cells are arranged in a circle and the frequency reuse distance is 2, while for larger reuse distances and planar hexagonal arrays, the policy may not always achieve maximal throughput. For general circular arrays, we enhance the policy to achieve maximal throughput asymptotically as the number of cells increases. For planar hexagonal arrays, we show that the policy can guarantee throughputs which are fairly close to maximal.

Ring network architectures that employ spatial reuse permit concurrent transmissions of messages over different links. While spatial reuse increases network throughput, it may also cause starvation of nodes. To alleviate this problem, various policies have been suggested in the literature. In this paper, we concentrate on a class of such policies that achieves fairness by allocating transmission quotas to nodes. For such policies, we provide mechanisms for improving delays and increasing overall throughput without compromising fairness.

In distributed multimedia servers where client requests for different video streams may have different probabilities, placement of video streams is an important parameter, because it may result in unbalanced requests to the system's stations, and thus to high blocking probabilities of requests. We present a method, MMPacking, to balance traffic load and storage use in a distributed server environment. Since different video screams are requested by clients with different rates, video stream replication is used to balance the traffic patterns of the stations; thus, the requests and I/O usage of the stations is balanced, since replication allows requests for the same video stream to be routed to different stations. MMPacking achieves load balancing by producing at most N-1 replicas of video streams in a system with N servers. These replicas are distributed among the stations, so that storage balancing is achieved as well, since no station stores more than 2 video streams than any other station in the system.

This paper addresses the problem of providing per-connection end-to-end delay guarantees in a high-speed network. We assume that the network is connection oriented and enforces some admission control which ensures that the source traffic conforms to specified traffic characteristics. We concentrate on the class of rate-controlled service (RCS) disciplines, in which traffic from each connection is reshaped at every hop, and develop end-to-end delay bounds for the general case where different reshapers are used at each hop. In addition, we establish that these bounds can also be achieved when the shapers at each hop have the same "minimal" envelope. The main disadvantage of this class of service disciplines is that the end-to-end delay guarantees are obtained as the sum of the worst case delays at each node, but we show that this problem can be alleviated through "proper" reshaping of the traffic. We illustrate the impact of this reshaping by demonstrating its use in designing RCS disciplines that outperform generalized processor sharing-based service disciplines.

In this paper, we investigate some issues related to the efficient provision of end-to-end delay guarantees in the context of the Guaranteed (G) Services framework [16]. First, we consider the impact of reshaping traffic within the network on the end-to-end delay, the end-to-end jitter, as well as per-hop buffer requirements. This leads us to examine a class of traffic disciplines that use reshaping at each hop, namely rate-controlled disciplines. In this case, it is known that it is advantageous to use the Earliest Deadline First (EDF) scheduling policy at the link scheduler [8]. For this service discipline, we determine the appropriate values of the parameters that have to be exported, as specified in [16]. Subsequently, with the help of an example, we illustrate how the G service traffic will typically underutilize the network, regardless of the scheduling policy used. We then define a Guaranteed Rate (GR) service, that is synergetic with the G service framework and makes use of this unutilized bandwidth to provide rate guarantees to flows. We outline some of the details of the GR service and explain how it can be supported in conjunction with the G service in an efficient manner.

This paper addresses the problem of providing per-connection end-to-end delay guarantees in a high-speed network. We consider a network comprised of store-and-forward packet switches, in which a packet scheduler is available at each output link. We assume that the network is connection oriented and enforces some admission control which ensures that the source traffic conforms to specified traffic characteristics. We concentrate on the class of rate-controlled service (RCS) disciplines, in which traffic from each connection is reshaped at every hop, and develop end-to-end delay bounds for the general case where different reshapers are used at each hop. In addition, we establish that these bounds can also be achieved when the shapers at each hop have the same "minimal" envelope. The main disadvantage of this class of service discipline is that the end-to-end delay guarantees are obtained as the sum of the worst-case delays at each node, but we show that this problem can be alleviated through "proper" reshaping of the traffic. We illustrate the impact of this reshaping by demonstrating its use in designing RCS disciplines that outperform service disciplines that are based on generalized processor sharing (GPS). Furthermore, we show that we can restrict the space of "good" shapers to a family which is characterized by only one parameter. We also describe extensions to the service discipline that make it work conserving and as a result reduce the average end-to-end delays.

We consider the ring network with spatial reuse. Traffic streams may enter and exit the network at any node. We adopt an arrival traffic model with deterministic constraints on its sample paths, which conforms to the output traffic of a leaky bucket rate control mechanism. A transmission policy specifies each time at which the traffic stream will be transmitted at the outgoing link by each node. We provide an upper bound on the asymptotic backlog of the ring that holds for all work-conserving policies and is independent of the initial conditions. This bound remains finite as long as the maximum load of every link is less than one. The latter condition is also necessary for the existence of an asymptotic bound that is independent of the initial conditions.

Considers the design of efficient channel allocation algorithms in personal communication networks where the cells have varying traffic loads. A common communication channel is to be dynamically shared between the cells. The authors propose a distributed inter-cell channel allocation policy that is easy to implement through the use of simple signalling between neighboring cells. For cells arranged in a line they show that the proposed policy achieves maximum throughput. The same is true when the cells are arranged in a circle and the channel can be reused in every other cell. For larger reuse distances and planar hexagonal arrays, the policy may not always achieve maximal throughput. For these cases the authors provide regions of achievable cell throughputs under the proposed policy and show that they are tight in certain cases.

Addresses the problem of designing optimal buffer management policies in shared memory switches when packets already accepted in the switch can be dropped (pushed-out). The goal is to maximize the overall throughput, or equivalently to minimize the overall loss probability in the system. For a system with two output ports, the authors prove that the optimal policy is of pushout with threshold type (POT). The same result holds if the optimality criterion is the weighted sum of the port loss probabilities. For this system, the authors also give an approximate method for the calculation of the optimal threshold, which they conjecture to be asymptotically correct. For the N-ported system, the optimal policy is not known in general, but it is shown that for a symmetric system (equal traffic on all ports) it consists of always accepting arrivals when the buffer is not full, and dropping one from the longest queue to accommodate the new arrival when the buffer is full. Numerical investigations show that under the optimal POT policy the loss probability of a port is insensitive to traffic fluctuations in the other port.

We address the problem of designing optimal buffer management policies in shared memory switches when packets already accepted in the switch can be dropped (pushed-out). Our goal is to maximize the overall throughput, or equivalently to minimize the overall loss probability in the system. For a system with two output ports, we prove that the optimal policy is of push-out with threshold type (POT). The same result holds if the optimality criterion is the weighted sum of the port loss probabilities. For this system, we also give an approximate method for the calculation of the optimal threshold, which we conjecture to be asymptotically correct. For the N-ported system, the optimal policy is not known in general, but we show that for a symmetric system (equal traffic on all ports) it consists of always accepting arrivals when the buffer is not full, and dropping one from the longest queue to accommodate the new arrival when the buffer is full. Numerical results are provided which reveal an interesting and somewhat unexpected phenomenon. While the overall improvement in loss probability of the optimal POT policy over the optimal coordinate-convex policy is not very significant, the loss probability of an individual output port remains approximately constant as the load on the other port varies and the optimal POT policy is applied, a property not shared by the optimal coordinate-convex policy.>

Ring network architectures that employ spatial reuse permit concurrent transmissions of messages over different links. While spatial reuse increases network throughput, it may also cause starvation of nodes. To alleviate this problem, various policies have been suggested in the literature. In the paper the authors concentrate on a class of such policies that achieve fairness by allocating transmission quotas to nodes. For such policies, they provide mechanisms for improving delays and increasing overall throughput without compromising fairness.>

This paper is motivated by the need to support multiple service classes in fast packet-switched networks. The authors address the problem of characterizing and designing scheduling policies that are optimal in the sense of minimizing buffer and/or delay requirements under the assumption of commonly accepted traffic constraints. They investigate the buffer requirements under three typical memory allocation mechanisms, that represent trade-offs between efficiency and complexity. For classes with delay constraints they provide policies that are optimal in the sense of satisfying the constraints if they are satisfiable by any policy, and they also have low buffer requirements. They also address the issue of designing policies that satisfy delay constraints in a fair manner. They mainly concern ourselves with non-preemptive policies. One of the proposed policies is based on a class of non-preemptive policies that tracks preemptive policies. This class is introduced in this paper and may be of interest in other applications as well.>

Considers a ring network with spatial reuse. Traffic streams may enter and exit the network at any node. The burstiness of each traffic stream is bounded by a deterministic bound. A transmission policy specifies at each time which traffic stream will be transmitted at the outgoing link by each node. The authors provide an upper bound on the asymptotic backlog of the ring that holds for all work-conserving policies and is independent of the initial conditions. This bound remains finite as long as the maximum load of every link is less than one. The latter condition is also necessary for the existence of an asymptotic bound that is independent of the initial conditions.>

A method for analyzing the delay distribution of window random-access algorithms is presented. The window size is allowed to vary during the operation of the algorithm. It is shown that the quantities of interest in the computation of the delay distribution can be related to the solution of appropriate infinite systems of linear equations. Once the constants and the coefficients of the unknowns of the system are determined, bounds on the solution can be developed by applying previously developed methodologies. The method is applied to the delay distribution analysis of the Capetanakis window random-access algorithm and the part-and-try algorithm, both under binary feedback.>

Considers a slotted ring in which simultaneous transmission of messages by different stations is allowed, a property referred to as spatial reuse. Ring networks with spatial reuse can achieve significantly higher throughput than standard token rings but they also introduce the possibility of starvation for some nodes on the ring. To alleviate this problem, various policies have been suggested in the literature. The present objective is to characterize the node throughputs achievable by general transmission policies in ring networks with spatial reuse and then to evaluate the throughput trade-off for a class of policies that has been proposed in the literature in order to avoid starvation. Specifically, the authors study a policy that is based on the idea of allocating transmission quotas to the nodes. Each node is guaranteed transmission of his quota within a specified interval. The authors show that by appropriately allocating the quotas, policies that satisfy general optimality criteria-in particular criteria related to fairness-can be designed. They also study the asymptotic behavior of the quota policy when either the quotas or the number of nodes increase.>

The interconnection of two single-hop random-access networks is considered. In each network a station, called the bridge node, receives internetwork packets from the local users and forwards them to the bridge node of the other network via a point-to-point link, for subsequent broadcasting to the users of that network. In each network, the bridge node shares the available broadcast channel with the local users either via contention or via frequency division. Under the infinite population Poisson user model, conditions for the stability of the interconnected system are derived.>

A method for delay distribution analysis of window random-access algorithms is presented. The window size is allowed to vary during the operation of the algorithm. It is shown that the quantities of interest can be obtained from the solution of appropriate infinite systems of linear equations. Once the constants and the coefficients of the unknowns of a system are determined, bounds on the solution can be developed by applying previously developed methodologies. The method is applied to the delay distribution analysis of the Capetanakis's window random-access algorithm and the part-and-try algorithm, both under binary C-NC feedback.>

Random multiple-access algorithms are used to control the accessing of a common communication channel by a large population of bursty channel users. For such algorithms, the induced transmission delay is a key performance measure. A systematic method for finding the delay characteristics of random multiple-access algorithms, whose delay process is regenerative, is presented. The method uses a powerful result from the theory of regenerative processes, in effect, to reduce the problem of determining the delay moments to the problem of solving denumerable dimensional systems of linear equations. Techniques for finding tight bounds on the solutions of such systems are presented. The "0.487" algorithm is used to exemplify the method.

We examine the relation between the finite and the infinite population models for a class of random access algorithms. The algorithms in the class are a combination of random access and reservation techniques, they are synchronous, and they are studied under the condition that each of the users can monitor the channel feedback continuously (full feedback sensing). For any finite number of independent and identical users in the system, and any i.i.d. arrival process per user, the algorithms are stable, provided that the total input rate is less than one. However, as the population size increases, the stability of an algorithm in the class is determined by its throughput in the presence of the infinite population model for all practical purposes.

We consider Poisson packet traffic accessing a single-slotted channel. We assume the existence of a ternary feedback per channel slot. We also adopt the limited feedback sensing model where each user senses the feedback only while he has a packet to transmit. For this model we develop a collision resolution algorithm with last come-first served characteristics. The algorithm attains the same throughput as Gallager's algorithm without the latter's full feedback sensing requirement. In addition, it is easy to implement, requires reasonable memory storage, induces uniformly good transmission delays, and is insensitive to feedback errors. In the presence of binary (collision versus noncollision) feedback the algorithm may attain a throughput of0.4493.

A slotted packet broadcast channel with an infinite user population is considered. A limited feedback sensing algorithm is proposed and analyzed for collision versus noncollision binary feedback. The algorithm bas maximum throughput equal to0.42(packets/slot), has uniformly good delay characteristics within its stability region, and is robust in the presence of feedback errors. A variation of the algorithm, for ternary feedback, attains maximum throughput0.425and bas uniformly good delay characteristics within its stability region. In contrast, the highest throughput limited feedback sensing algorithm existing for ternary feedback attains maximum throughput0.456, but induces relatively high delays for Poisson intensities below0.3.

In this paper, we consider the random accessing of a single slotted channel by a large number of packet-transmitting, bursty users. We assume that feedback broadcasting is available where some different information, in addition to the information assumed by the Capetanakis, Gallager, Massey, etc., models, is included in the feedback. In particular, we assume that the existence of energy detectors permits the broadcasting of the number of collided packets within each collision slot, whenever this number is below a certain limit. We first consider this limit to be infinity, and then a finite small number. For the model considered, we propose and analyze a collision resolution protocol (CRAI), whose implementation is simple. For Poisson input traffic and infinite number of energy detectors, we found that the CRAI is stable for input rates below 0.53237. For finite number of energy detectors, we propose a modified version of the CRAI (MCRAI). We found that the MCRAI reaches the throughput 0.53237, through the utilization of only about eight energy detectors. These protocols, like the ones introduced by Capetanakis, Gallager, Massey, etc., have good delay properties.