We investigate the problem of replication in large wireless networks that employ caching in the case of a single file whose popularity varies with time. As opposed to the case of static popularity, in this case for the network resources to be efficiently allocated the replication should vary with time. In this study, we first outline the low-level operations of wireless networks with caching, which involve decisions of combinatorial complexity, such as about the contents of all network caches. To overcome this complexity, we approximate the network optimization with a formulation based on the frequency of file replication across the network - a high-level perspective, amenable to mathematical analysis. We present a solution that is based on looking ahead into the future and has a simple graphical representation.

We study flow optimization in wireless Delay Tolerant Networks (DTNs), using Capacity Region Evolving Graphs (CREGs). CREGs comprise cascaded subgraphs which represent the network topology at consecutive time intervals called epochs. The data flows jointly attainable at all wireless links during each time interval are described in terms of a respective capacity region. We associate the sizes of the node buffers at the beginning and end of time with a set of cost and utility functions, and formulate the transport problem of maximizing the sum of the utilities minus the sum of the costs. Then, we present a primal decomposition algorithm for solving this flow optimization problem exactly and efficiently, taking advantage of its special structure. This algorithm unavoidably relies on the knowledge, in advance, of the complete evolution of the network topology at all epochs. As this is a stringent requirement, we devise a heuristic online algorithm that arrives at efficient (but suboptimal) flows at each epoch without looking into future epochs.

We investigate the scalability of multihop wireless communications, a major concern in networking, for the case that users access content replicated across the nodes. In contrast to the standard paradigm of randomly selected communicating pairs, content replication is efficient for certain regimes of file popularity, cache, and network size. Our study begins with the detailed joint content replication and delivery problem on a 2-D square grid, a hard combinatorial optimization. This is reduced to a simpler problem based on replication density, whose performance is of the same order as the original. Assuming a Zipf popularity law, and letting the size of content and network both go to infinity, we identify the scaling laws and regimes of the required link capacity, ranging from$O\!\left(\!\sqrt {N}\right)$down to$O(1)$.

A key consideration in novel communication paradigms in multihop wireless networks regards the scalability of the network. We investigate the case of nodes making random requests on content stored in multiple replicas over the wireless network. We show that, in contrast to the conventional paradigm of random communicating pairs, multihop communication is a sustainable scheme for certain values of file popularity, cache and network size. In particular, we formulate the joint problem of replication and routing and compute an order optimal solution. Assuming a Zipf file popularity distribution, we vary the number of files M in the system as a function of the nodes N, let both go to infinity and identify the scaling regimes of the required link capacity, from O(√N) down to O(1).

We study load balancing in wireless networks with a single class of traffic, focusing our attention on an important example, i.e., wireless sensor networks. The analysis is based on the wireless minimum cost problem, an optimization problem that implicitly captures the effects of interference through the novel use of an arc cost function that depends on the amount of traffic flowing through nearby links. We present an algorithm that optimizes the flow by modifying the traffic along cycles constructed during an initialization phase. Its operation may be viewed as trying to satisfy Kirchhoff's Voltage Law on an electric circuit containing interferistors. It is robust, distributed, with minimal communication overhead, and converges quickly. Furthermore, when the traffic is elastic, the algorithm can be easily modified to also perform congestion control.

We investigate a wireless computing architecture, where mobile terminals can execute their computation tasks either 1) locally, at the terminal's processor, or 2) remotely, assisted by the network infrastructure, or even 3) combining the former two options. Remote execution involves: 1) sending the task to a computation server via the wireless network, 2) executing the task at the server, and 3) downloading the results of the computation back to the terminal. Hence, it results to energy savings at the terminal (sparing its processor from computations) and execution speed gains due to (typically) faster server processor(s), as well as overheads due to the terminal server wireless communication. The net gains (or losses) are contingent on network connectivity and server load. These may vary in time, depending on user mobility, network, and server congestion (due to the concurrent sessions/connections from other terminals). In local execution, the wireless terminal faces the dilemma of power managing the processor, trading-off fast execution versus low energy consumption. We model the system within a Markovian dynamic control framework, allowing the computation of optimal execution policies. We study the associated energy versus delay trade-off and assess the performance gains attained in various test cases in comparison to conventional benchmark policies.

We investigate efficient schemes for data communication from a server (base station and access point) to a mobile terminal over a wireless channel of randomly fluctuating quality. The terminal user generates requests for data items. If the buffer (cache) of the terminal contains the requested data, no access delay/latency is incurred. If not, the data is downloaded from the server, and until becoming available locally at the terminal, the user incurs a delay cost. Moreover, a transmission/power cost is incurred to transmit the data over the wireless link at a dynamically selected power level. To lower both the access delay and transmission costs, the system may prefetch data predictively and cache them on the terminal (especially during high-link-quality periods), anticipating future user requests. The goal is to jointly minimize the overall latency and power costs by dynamically choosing what data to (pre)fetch, what power level to use, and when to use it. We develop a modeling framework (based on dynamic programming and controlled Markov chains) that captures essential performance trade-offs. It allows for the computation of optimal decisions regarding what data to (pre)fetch and what power levels to use. To cope with emerging complexities, we then design efficient online heuristics whose simulation analysis demonstrates substantial performance gains over standard approaches.

Migrating (uploading) encrypted file blocks from mobile wireless devices to network servers for decryption provides substantial performance gains, including (i) reduced battery drain at the device, and (ii) fast execution at server’s powerful processors. This, however, introduces the risk of communicating through an unreliable wireless channel of varying (soft) connectivity, which can induce substantial performance degradation. To address the dilemma of decrypting blocks locally at the device, or remotely at the network server, we develop a parsimonious stochastic model that leverages the Dynamic Programming methodology and captures the dominant performance trade-offs. Based on this model, we obtain efficient algorithms for making upload decisions, as well as power management at the wireless device. Of particular interest is the case of RSA decoding at wireless sensors where the developed algorithms are demonstrated to achieve substantial performance gains over conventional approaches.

We introduce a probabilistic framework, based on service risk mitigation and disruption management, for the problem of capacity protection in optical networks. This contrasts the established deterministic approach of designing the protection network to guarantee no service disruption for up to M failures. We present the novel problem formulation and establish a framework for optimal network design in this extended abstract, while leaving the detailed optimization results and algorithms for the full paper (N. Bambos et al., 2003).

Prefetching is a technique for lowering the access delay by making data available in anticipation of future requests. Correspondingly, power control has been proposed in wireless networks for the efficient use of the wireless resources and low energy consumption at the transmitters. This work investigates the two techniques jointly (1) for communications over a fluctuating wireless channel whose dynamics and statistics is unknown, and (2) explore approximating schemes for exercising deep prefetching. In short, a user uses a wireless terminal to access various data items residing at a server over a wireless network. Every requested item not found in the cache of the terminal incurs to the system (1) an access delay cost, and (2) an energy/network cost to download it over the wireless link. To minimize the total cost, the system may either (i) postpone the transmissions when the link quality is sensed to be low, or reversely, (ii) proactively prefetch data items during link quality 'highs', in anticipation to future user requests. The decision therefore involves choosing when and what to (pre)fetch, and at what power level. To quantify on the above, we formulate the problem in the context of controlled Markov chains using the technique of dynamic programming. After analyzing the structure of the problem, we construct a set of policies based on justified heuristics for taking near-to-optimal decisions. Simulation is then used to quantify on the performance gains over standard schemes.

We investigate the technique of the task migration from mobile terminals to computation servers over the wireless network. In the perceived architecture, the mobile terminals are assisted by the network infrastructure in the execution of their computational tasks. Thus, the terminal has two basic options (and combinations of them): A) local execution, that is execute the tasks locally, or B) remote execution, which involves (1) sending the tasks to a computation server over the wireless network, (2) executing the tasks at the server, and (3) downloading the computation results back to the terminal. The latter provides energy savings for the terminal (sparing its local processor) and execution speed gains (the server is usually much faster than the terminal), but incurs some overhead as well, resulting from the terminal /spl harr/ server wireless communication. The net gains, if any, are dependent on (i) the degree of the connectivity between the terminal and the network server, and (ii) the server load. Both these two parameters fluctuate with time; the former due to the varying network load and the volatile wireless channel, and the latter due to the sharing with other clients at the server. To decide optimally on the execution policy, we introduce a Markovian framework. We then study the associated energy vs. delay trade-offs, and assess the performance gains attained in various test cases compared to the conventional paradigms of the exclusively local/remote execution.

We investigate the problem of packet relaying in power-controlled wireless data networks. For reasons of limited range or energy efficiency, packets are not transmitted from the source to the destination nodes directly, but in two hops via an intermediary relay node. The nodes are equipped with buffers to store the incoming packets while they take turns to transmit. The communication takes place over wireless links whose quality fluctuates due to fading and interference from other users. At each point in time, the system has to decide (i) which transmitter takes possession of the channel, and (ii) the power level at the transmitter. On adverse channel conditions, the system can even decide to refrain from all transmissions (back-off), waiting for the links to improve before resuming transmissions. Clearly, this dilemma induces the fundamental trade-off between packet delay and transmission power. In a delay-sensitive configuration, the transmitters prefer to remain always active so as to keep the packet backlogs at the queues low. On the contrary, a power-sensitive configuration favors the use of back-off, resulting in low transmission power levels at the cost of increased packet delay and high packet backlogs. Overall, the decision is taken based on (i) the state of the wireless links, and (ii) the backlog size of the queues. Toward designing efficient transmission schemes, we model the system as a controlled Markov chain and formulate the optimization problem in the context of dynamic programming. We construct a set of transmission schemes by analyzing the system dynamics, which are evaluated over standard approaches and shown to achieve significant performance gains.

We investigate efficient schemes for data communication from a server to a mobile terminal over a wireless channel of fluctuating quality. A user requests to access various data items on the terminal. If a requested item is found in the local terminal buffer or cache, no access delay is incurred. If not, it is downloaded from the server and the user incurs a delay cost until it becomes locally available. Moreover, a power cost is incurred to transmit the data item at a selected power level over the wireless link. To lower both the average delay and power costs, the system may prefetch data items and predictively cache them on the terminal - especially during link quality 'highs' - in anticipation of future user requests. The goal is to minimize the overall delay and power cost, by judiciously choosing which data item to fetch and what power level to use, given the current user, buffer, and channel states. We develop a modeling framework - based on controlled Markov chains and dynamic programming - capturing the essential performance tradeoffs in the system and allowing computation of optimal decisions on items to (pre)fetch and power levels to use. To cope with emerging complexities, we then design efficient heuristics, whose simulation analysis demonstrates substantial performance gains over standard approaches.