Online learning algorithms have been successfully used to design caching policies with sublinear regret in the total number of requests, with no statistical assumption about the request sequence. Most existing algorithms involve computationally expensive operations and require knowledge of all past requests. However, this may not be feasible in practical scenarios such asfemtocaching, where a base station (BS) jointly decides the content of many edge caches and visibility of all requests at the BS requires constant communication between these caches and the BS. To capture this constraint, we study a single cache problem under a more restrictive setting, that we refer to as the Bernoulli Partial Observability (BPO) model, in which the caching policy only observes a request with probability$p$, reflecting the fraction of requests forwarded from the edge caches to the BS in thefemtocachingexample. We propose a policy, based on the classic online learning algorithm Follow-the-Perturbed-Leader (FPL), that achieves an asymptotically optimal regret bound of$\mathcal {O}(\sqrt {CT/p})$under BPO in$\mathcal {O}(1)$amortized time complexity as$T$goes to infinity, where$C$is the cache size and$T$is the number of requests. Moreover, we show that our policy extends to bipartite caching albeit with a sublinear$\alpha $-regret for$\alpha =1-1/e$and a higher computational cost. The experimental evaluation compares the proposed solution with classic caching policies and validates the proposed approach using both synthetic and real-world request traces.

Similarity caching allows requests for an item$i$to be served by a similar item i’. Applications include recommendation systems, multimedia retrieval, and machine learning. Recently, many similarity caching policies have been proposed, but still we do not know how to compute the hit rate even for simple policies, like SIM-LRU and RND-LRU that are straightforward modifications of classic caching algorithms. This paper proposes the first algorithm to compute the hit rate of similarity caching policies under the independent reference model for the request process. In particular, we show how to extend the popular time-to-live approximation in classic caching to similarity caching. The algorithm is evaluated on both synthetic and real world traces.

This note is to correct the author list and authors' affiliations for the above listed paper (ibid., vol. 29, no. 8, pp. 1630-1640, Sep 2011). The acknowledgements are also revised.

In this paper, we analyze the power save and its impact on web traffic performance when customers adopt the continuous connectivity paradigm. To this aim, we provide a model for packet transmission and cost. We model each mobile user's traffic with a realistic web traffic profile, and study the aggregate behavior of the users attached to a base station by means of a processor-shared queueing system. In particular, we evaluate user access delay, download time and expected economy of energy in the cell. The model is validated through packet-level simulations. Our model shows that dramatic energy save can be achieved by both mobile users and base stations, e.g., as much as 70% of the energy cost due to packet transmission at the base station.

We consider a mobile connected to a base station, and study how to optimally schedule shutting off its transceiver. First, we study the model from optimal control perspective. We consider off-times (periods of inactivity) of (controlled) duration. We study the question of scheduling "waking up" instants in which the mobile communicates with the base station and checks whether the inactivity period is over. There is a cost proportional to the delay from the moment the off-time ends until the mobile discovers it, a (small) running cost while the mobile is sleeping and a cost for waking up. We present conditions for optimal sleep periods to be constant and derive the optimal period. For the case that the conditions do not hold, we obtain suboptimal solutions which perform strictly better than the optimal constant one. We then investigate optimality restricted to classes of policies with specific constraints. We adopt the parametric optimization approach which entails cost minimization for a given parameterized policy and selection of the best policy among a class. We then compare the performance of optimal policies, of the proposed suboptimal policies as well as that of standard policies like IEEE 802.16e.

No abstract available.

In this work, we introduce a framework to let forwarding schemes evolve in order to adapt to changing and a priori unknown environments. The framework is inspired by genetic algorithms: at each node a genotype describes the forwarding scheme used, a selection process fosters the diffusion of the fittest genotypes in the system and new genotypes are created by combining existing ones or applying random changes. A case study implementation is presented and its performance evaluated via numerical simulations.

This paper presents an algorithm for resource allocation in satellite networks. It deals with planning a time/frequency plan for a set of terminals with a known geometric configuration under interference constraints. Our objective is to maximize the system throughput while guaranteeing that the different types of demands are satisfied, each type using a different amount of bandwidth. The proposed algorithm relies on two main techniques. The first generates admissible configurations for the interference constraints, whereas the second uses linear and integer programming with column generation. The obtained solution estimates a possible allocation plan with optimality guarantees, and highlights the frequency interferences which degrade the construction of good solutions.

We propose two novel on-line estimation algorithms to determine the size of a dynamic multicast group. We first use a Wiener filter to derive an optimal estimator for the membership size of the session in case the join process is Poisson and the lifetime of participants is distributed exponentially. We next develop the best first-order linear filter from which we derive an estimator that holds for any lifetime distribution. We apply this approach to the case where the lifetime distribution is hyperexponential. Both estimators hold under any traffic regime. Applying both estimators on real traces corresponding to video sessions, we find that both schemes behave well, one of which performs slightly better than the other in some cases. We further provide guidelines on how to tune the parameters involved in both schemes in order to achieve high quality estimation while simultaneously avoiding feedback implosion.

We propose an efficient on-line estimation algorithm for determining the size of a dynamic multicast group. By using diffusion approximation and a Kalman filter, we derive an estimator that minimizes the mean square of the estimation error. As opposed to previous studies, where the size of the multicast group is supposed to be fixed throughout the estimation procedure, we consider a dynamic estimation scheme that updates the estimation at every observation step. The robustness of our estimator to violation of the assumptions under which it has been derived is addressed via simulations. Further validations of our approach are carried out on real audio traces.

The Internet has allowed the creation of huge amounts of data located on many sites. Performing complex operations on some data requires that the data be transferred first to the machine on which the operations are to be executed, which may require a non-negligible amount of bandwidth and may seriously limit performance if it is the bottleneck. However, instead of moving the data to the code, it is possible to move the code to the data, and perform all the operations locally. This simple idea has led to a new paradigm called code-mobility: a mobile object --- sometimes called an agent --- is given a list of destinations and a series of operations to perform on each one of them. The agent will visit all of the destinations, perform the requested operations and possibly pass the result on to another object. Any mobility mechanism must first provide a way to migrate code from one host to another. It must also ensure that any communication following a migration will not be impaired by it, namely that two objects should still be able to communicate even if one of them has migrated. Such a mechanism is referred to as a location mechanism since it often relies on the knowledge of the location of the objects to ensure communications. Two location mechanisms are widely used: the first one uses a centralized server whereas the second one relies on special objects called forwarders.This paper evaluates and compares the performance of an existing implementation of these approaches in terms of cost of communication in presence of migration. Based on a Markov chain analysis, we will construct and solve two mathematical models, one for each mechanism and will use them to evaluate the cost of location. For the purpose of validation, we have developed for each mechanism a benchmark that uses ProActive [2], a Java library that provides all the necessary primitives for code mobility. Experiments conducted on a LAN and on a MAN have validated both models and have shown that the location server always performs better than the forwarders. Using our analytical models we will nevertheless identify situations where the opposite conclusion holds. However, under most operational conditions location servers will perform better than forwarders.

In this work we develop simple inference models based on finite capacity single server queues for estimating the buffer size and the intensity of cross traffic at the bottleneck link of a path between two hosts. Several pairs of moment-based estimators are proposed to estimate these two quantities. The best scheme is then identified through simulation.