
The modeling and analysis of an LRU cache is extremely challenging as exact
results for the main performance metrics (e.g. hit rate) are either lacking or
cannot be used because of their high computational complexity for large caches.
As a result, various approximations have been proposed. The stateoftheart
method is the socalled TTL approximation, first proposed and shown to be
asymptotically exact for IRM requests by Fagin. It has been applied to various
other workload models and numerically demonstrated to be accurate but without
theoretical justification. In this paper we provide theoretical justification
for the approximation in the case where distinct contents are described by
independent stationary and ergodic processes. We show that this approximation
is exact as the cache size and the number of contents go to infinity. This
extends earlier results for the independent reference model. Moreover, we
establish results not only for the aggregate cache hit probability but also for
every individual content. Last, we obtain bounds on the rate of convergence.

In this paper, we consider the problem of allocating cache resources among
multiple content providers. The cache can be partitioned into slices and each
partition can be dedicated to a particular content provider, or shared among a
number of them. It is assumed that each partition employs the LRU policy for
managing content. We propose utilitydriven partitioning, where we associate
with each content provider a utility that is a function of the hit rate
observed by the content provider. We consider two scenarios: i)~content
providers serve disjoint sets of files, ii)~there is some overlap in the
content served by multiple content providers. In the first case, we prove that
cache partitioning outperforms cache sharing as cache size and numbers of
contents served by providers go to infinity. In the second case, It can be
beneficial to have separate partitions for overlapped content. In the case of
two providers, it is usually always beneficial to allocate a cache partition to
serve all overlapped content and separate partitions to serve the
nonoverlapped contents of both providers. We establish conditions when this is
true asymptotically but also present an example where it is not true
asymptotically. We develop online algorithms that dynamically adjust partition
sizes in order to maximize the overall utility and prove that they converge to
optimal solutions, and through numerical evaluations, we show they are
effective.

We analyze the connectivity of an $M$layer network over a common set of
nodes that are active only in a fraction of the layers. Each layer is assumed
to be a subgraph (of an underlying connectivity graph $G$) induced by each node
being active in any given layer with probability $q$. The $M$layer network is
formed by aggregating the edges over all $M$ layers. We show that when $q$
exceeds a threshold $q_c(M)$, a giant connected component appears in the
$M$layer networkthereby enabling faraway users to connect using `bridge'
nodes that are active in multiple network layerseven though the individual
layers may only have small disconnected islands of connectivity. We show that
$q_c(M) \lesssim \sqrt{\ln(1p_c)}\,/{\sqrt{M}}$, where $p_c$ is the bond
percolation threshold of $G$, and $q_c(1) \equiv q_c$ is its site percolation
threshold. We find $q_c(M)$ exactly for when $G$ is a large random network with
an arbitrary nodedegree distribution. We find $q_c(M)$ numerically for various
regular lattices, and find an exact lower bound for the kagome lattice.
Finally, we find an intriguingly close connection between this multilayer
percolation model and the wellstudied problem of sitebond percolation, in the
sense that both models provide a smooth transition between the traditional site
and bond percolation models. Using this connection, we translate known
analytical approximations of the sitebond critical region, which are functions
only of $p_c$ and $q_c$ of the respective lattice, to excellent general
approximations of the multilayer connectivity threshold $q_c(M)$.

In source routing, a complete path is chosen for a packet to travel from
source to destination. While computing the time to traverse such a path may be
straightforward in a fixed, static graph, doing so becomes much more
challenging in dynamic graphs, in which the state of an edge in one time slot
(i.e., its presence or absence) is random, and may depend on its state in the
previous time step. The traversal time is due to both time spent waiting for
edges to appear and time spent crossing them once they become available. We
compute the expected traversal time (ETT) for a dynamic path in a number of
special cases of stochastic edge dynamics models, and for three edge failure
models, culminating in a surprisingly challenging yet realistic setting in
which the initial configuration of edge states for the entire path is known. We
show that the ETT for this "initial configuration" setting can be computed in
quadratic time, by an algorithm based on probability generating functions. We
also give several lineartime upper and lower bounds on the ETT.

In this paper we study the behavior of a continuous time random walk (CTRW)
on a stationary and ergodic time varying dynamic graph. We establish conditions
under which the CTRW is a stationary and ergodic process. In general, the
stationary distribution of the walker depends on the walker rate and is
difficult to characterize. However, we characterize the stationary distribution
in the following cases: i) the walker rate is significantly larger or smaller
than the rate in which the graph changes (timescale separation), ii) the
walker rate is proportional to the degree of the node that it resides on
(coupled dynamics), and iii) the degrees of node belonging to the same
connected component are identical (structural constraints). We provide examples
that illustrate our theoretical findings.

A typical web search engine consists of three principal parts: crawling
engine, indexing engine, and searching engine. The present work aims to
optimize the performance of the crawling engine. The crawling engine finds new
web pages and updates web pages existing in the database of the web search
engine. The crawling engine has several robots collecting information from the
Internet. We first calculate various performance measures of the system (e.g.,
probability of arbitrary page loss due to the buffer overflow, probability of
starvation of the system, the average time waiting in the buffer). Intuitively,
we would like to avoid system starvation and at the same time to minimize the
information loss. We formulate the problem as a multicriteria optimization
problem and attributing a weight to each criterion. We solve it in the class of
threshold policies. We consider a very general web page arrival process modeled
by Batch Marked Markov Arrival Process and a very general service time modeled
by Phasetype distribution. The model has been applied to the performance
evaluation and optimization of the crawler designed by INRIA Maestro team in
the framework of the RIAM INRIACanon research project.

In this paper we study the dynamic aspects of the coverage of a mobile sensor
network resulting from continuous movement of sensors. As sensors move around,
initially uncovered locations are likely to be covered at a later time. A
larger area is covered as time continues, and intruders that might never be
detected in a stationary sensor network can now be detected by moving sensors.
However, this improvement in coverage is achieved at the cost that a location
is covered only part of the time, alternating between covered and not covered.
We characterize area coverage at specific time instants and during time
intervals, as well as the time durations that a location is covered and
uncovered. We further characterize the time it takes to detect a randomly
located intruder. For mobile intruders, we take a game theoretic approach and
derive optimal mobility strategies for both sensors and intruders. Our results
show that sensor mobility brings about unique dynamic coverage properties not
present in a stationary sensor network, and that mobility can be exploited to
compensate for the lack of sensors to improve coverage.