We study the asymptotic behaviour of the distance to the first available parking slot in a recursive Manhattan street network endowed with a hyperfractal intensity structure, where slot-release events occur according to Poisson processes along the streets. We establish, by analysing the associated self-similar harmonic sums via Mellin-transform asymptotics [Flajolet et al., 1995], a power-law decay of the expected distance as the total intensity grows, with exponent equal to the inverse of the hyperfractal dimension. In particular, the scaling exponent depends only on the large-scale geometry of the network. We further prove that this exponent is robust under random multiplicative modulations of the street intensities: mild stochastic heterogeneity affects only the multiplicative constant. Similar scaling behaviour holds for the variance, the number of turns before parking, and for a jump-over variant of the search strategy.

The paper deals with a load-balancing algorithm for a closed stochastic network with two zones with different demands. The algorithm is motivated by an incentive algorithm for redistribution of cars in a large-scale car-sharing system. The service area is divided into two zones. When cars stay too long in the low-demand zone, users are encouraged to pick them up and return them in the high-demand zone. The zones are divided in cells called stations. The cars are the network customers. The mean-field limit solution of an ODE gives the large scale distribution of the station state in both clusters for this incentive policy in a discrete Markovian framework. An equilibrium point of this ODE is characterized via the invariant measure of a random walk in the quarter-plane. The proportion of empty and saturated stations measures how the system is balanced. Numerical experiments illustrate the impact of the incentive policy. Our study shows that the incentive policy helps when the high-demand zone observes a lack of cars but a saturation must be prevented especially when the high-demand zone is small.

Spatial outliers are objects having a behavior sig- nificantly different from their spatial neighbors, in a context where neighbors are heavily correlated. Moran scatterplot is a well-known method that exploits similarity between neighbors in order to detect spatial outliers. In this paper, we proposed first an improved version of Moran scatterplot, using a robust distance metric called Gower's similarity. We used the new version of Moran scatterplot to study the homogeneity of the Parisian bike sharing system (Velib). We carried out different experiments on a real dataset issued from the Velib system. We identified many spatial outliers stations, very different from their neighboring stations (often with much more available bikes or with much more empty docks during the day). Then, we designed and tested a new method that globally improves the distribution of the resources (bikes and docks) among bike stations. This method is motivated by the existence of spatial outliers stations. It relies on a local small change in users behaviors, by adapting their trips to resources' availability around their departure and arrival stations. Results show that, even with a partial users collaboration, the proposed method enhances significantly the global homogeneity of the bike sharing system and therefore the users' satisfaction.

The paper deals with load balancing between one-server queues on a circle by a local choice policy. Each one-server queue has a Poissonian arrival of customers. When a customer arrives at a queue, he joins the least loaded queue between this queue and the next one, ties solved at random. Service times have exponential distribution. The system is stable if the arrival-to-service rate ratio called load is less than one. When the load tends to zero, we derive the first terms of the expansion in this parameter for the stationary probabilities that a queue has 0 to 3 customers. We investigate the error, comparing these expansion results to numerical values obtained by simulations. Then we provide the asymptotics, as the load tends to zero, for the stationary probabilities of the queue length, for a fixed number of queues. It quantifies the difference between policies with this local choice, no choice and the choice between two queues chosen at random.

We consider in this paper an important Quality of Experience (QoE) indicator in mobile networks that is reneging of users due to impatience. We specifically consider a cell under heavy load conditions and compute the reneging probability by using a fluid limit analysis. By solving the fixed point equation, we obtain a new QoE perturbation metric quantifying the impact of reneging on the performance of the system. This metric is then used to devise a new pricing scheme accounting of reneging. We specifically propose several flavors of this pricing around the idea of having a flat rate for accessing the network and an elastic price related to the level of QoE perturbation induced by communications.

We propose in this paper an on-line algorithm based on Bloom filters to detect port scan attacks in IP traffic. Only relevant information about destination IP addresses and destination ports are stored in two steps in a two-dimensional Bloom filter. This algorithm can be indefinitely performed on a real traffic stream thanks to a new adaptive refreshing scheme that closely follows traffic variations. It is a scalable algorithm able to deal with IP traffic at a very high bit rate thanks to the use of hashing functions over a sliding window. Moreover it does not need any a priori knowledge about traffic characteristics. When tested against real IP traffic, the proposed on-line algorithm performs well in the sense that it detects all the port scan attacks within a very short response time of only 10 seconds without any false positive.

Passive optical networks are increasingly used for access to the Internet and it is important to understand the performance of future long-reach, multi-channel variants. In this paper we discuss requirements on upstream dynamic wavelength and bandwidth allocation (DWBA) and propose a simple novel algorithm that is considerably more efficient than classical approaches. We demonstrate that the algorithm emulates a multi-server polling system and deduce capacity formulas that are valid for general traffic processes.

In this paper, it is shown that the coexistence of a variety of different traffics in third generation cellular networks may lead to a very undesirable behavior of the whole network: a metastability property. When this property holds, the state of the network fluctuates on a very long time scale between different set of states. These long oscillations of the network make impossible to predict the average performances of some of the key characteristics of the connections, such as the handoff blocking rate or the probability of call blocking. As a consequence, the quality of service provided by such a network can be guaranteed only by, sometimes poor, lower bounds. Experiments of a UMTS network with this behavior are presented and the analysis of a corresponding simplified mathematical model is developed. The practical implications in the design of radio resource management for CDMA cellular networks are discussed.

On the basis of a reference model for ADSL traffic on an IP backbone link, established in an earlier study, we show that it is possible to infer the characteristics of long flows by performing a deterministic 1/N packet sampling. By using the fact that the number of active long flows can be represented by means of the number of customers in an M/G//spl infin/ queue with Weibullian service times, we derive some probabilistic properties of the sampled data. These properties are then used to infer the characteristics of the original flows. The method is illustrated by considering an actual traffic trace captured in the France Telecom IP backbone network. Experimental data show that the method proves quite efficient.

Memory interleaving considerably increases memory bandwidth in vector processor systems. The concurrent operation of the processors can produce memory bank conflicts and hence alter the memory bandwidth. Total or steady state performance for vector operations in a memory system is studied. Many methods of resolving memory bank conflicts are proposed and compared. Analytical results on the resulting effective bandwidth are presented for one of them and the others are described by exhaustive simulations. Some nonintuitive results are obtained on how conflicts depend on the size of the architecture, the number, the stride and the length of the vectors, the register length assigned by each processor to vector components.>

State-of-the art data locality optimizing algorithms are targeted for local memories rather than for cache memories. Recent work on cache interferences seems to indicate that these phenomena can severely affect blocked algorithms cache performance. Because of cache conflicts, it is not possible to know the precise gain brought by blocking. It is even difficult to determine for which problem sizes blocking is useful. Computing the actual optimal block size is difficult because cache conflicts are highly irregular. In this article, we illustrate the issue of precisely evaluating cross-interferences in blocked loops with blocked matrix-vector multiply. Most significant interference phenomena are captured because unusual parameters such as array base addresses are being considered. The techniques used allow us to compute the precise improvement due to blocking and the threshold value of problem parameters for which the blocked loop should be preferred. It is also possible to derive an expression of the optimal block size as a function of problem parameters. Finally, it is shown that a precise rather than an approximate evaluation of cache conflicts is sometimes necessary to obtain near-optimal performance.

The impact of cache interferences on program performance (particularly numerical codes, which heavily use the memory hierarchy) remains unknown. The general knowledge is that cache interferences are highly irregular, in terms of occurrence and intensity. In this paper, the different types of cache interferences that can occur in numerical loop nests are identified. An analytical method is developed for detecting the occurrence of interferences and, more important, for computing the number of cache misses due to interferences. Simulations and experiments on real machines show that the model is generally accurate and that most interference phenomena are captured. Experiments also show that cache interferences can be intense and frequent. Certain parameters such as array base addresses or dimensions can have a strong impact on the occurrence of interferences. Modifying these parameters only can induce global execution time variations of 30% and more. Applications of these modeling techniques are numerous and range from performance evaluation and prediction to enhancement of data locality optimizations techniques.

In numerical codes, the regular interleaved accesses that occur within do-loop nests induce cache interference phe nomena that can severely degrade program performance. Cache interferences can significantly increase the volume of memory traffic and the amount of communication in uniprocessors and multiprocessors. In this paper, we iden tify cache interference phenomena, determine their causes and the conditions under which they occur. Based on these results, we derive a methodology for computing an analyt ical expression of cache misses for most classic loop nests, which can be used for precise performance analysis and prediction. We show that cache performance is unstable, because some unexpected parameters such as arrays base address can play a significant role in interference phenom ena. We also show that the impact of cache interferences can be so high, that the benefits of current data local ity optimization techniques can be partially, if not totally, eradicated.

In numerical codes, the regular interleaved accesses that occur within do-loop nests induce cache interference phenomena that can severely degrade program performance. The authors identify cache interference phenomena and determine their causes and the conditions under which they occur. Based on these results, a methodology is derived for computing an analytical expression of cache misses for most classic loop nests, which can be used for precise performance analysis and prediction. It is shown that cache performance is unstable, because some unexpected parameters, such as arrays base address, can play a significant role in interference phenomena. It is also shown that the impact of cache interferences can be so high that the benefits of current data locality optimization techniques can be partially, if not totally, eradicated.>