Abstract:
We consider a task of scheduling a crawler to retrieve content from several sites with ephemeral content. A user typically loses interest in ephemeral content, like news or posts at social network groups, after several days or hours. Thus, development of timely crawling policy for such ephemeral information sources is very important. We first formulate this problem as an optimal control problem with average reward. The reward can be measured in the number of clicks or relevant search requests. The problem in its initial formulation suffers from the curse of dimensionality and quickly becomes intractable even with moderate number of information sources. Fortunately, this problem admits a Whittle index, which leads to problem decomposition and to a very simple and efficient crawling policy. We derive the Whittle index and provide its theoretical justification.

Abstract:
We consider Content Centric Network (CCN) interest forwarding problem as a Multi-Armed Bandit (MAB) problem with delays. We investigate the transient behaviour of the $\eps$-greedy, tuned $\eps$-greedy and Upper Confidence Bound (UCB) interest forwarding policies. Surprisingly, for all the three policies very short initial exploratory phase is needed. We demonstrate that the tuned $\eps$-greedy algorithm is nearly as good as the UCB algorithm, the best currently available algorithm. We prove the uniform logarithmic bound for the tuned $\eps$-greedy algorithm. In addition to its immediate application to CCN interest forwarding, the new theoretical results for MAB problem with delays represent significant theoretical advances in machine learning discipline.

Abstract:
We consider a GI/G/c/K-type retrial queueing system with constant retrial rate. The system consists of a primary queue and an orbit queue. The primary queue has $c$ identical servers and can accommodate the maximal number of $K$ jobs. If a newly arriving job finds the full primary queue, it joins the orbit. The original primary jobs arrive to the system according to a renewal process. The jobs have general i.i.d. service times. A job in front of the orbit queue retries to enter the primary queue after an exponentially distributed time independent of the orbit queue length. Telephone exchange systems, Medium Access Protocols and short TCP transfers are just some applications of the proposed queueing system. For this system we establish minimal sufficient stability conditions. Our model is very general. In addition, to the known particular cases (e.g., M/G/1/1 or M/M/c/c systems), the proposed model covers as particular cases the deterministic service model and the Erlang model with constant retrial rate. The latter particular cases have not been considered in the past. The obtained stability conditions have clear probabilistic interpretation.

Abstract:
We consider coalition formation among players in an n-player finite strategic game over infinite horizon. At each time a randomly formed coalition makes a joint deviation from a current action profile such that at new action profile all players from the coalition are strictly benefited. Such deviations define a coalitional better-response (CBR) dynamics that is in general stochastic. The CBR dynamics either converges to a strong Nash equilibrium or stucks in a closed cycle. We also assume that at each time a selected coalition makes mistake in deviation with small probability that add mutations (perturbations) into CBR dynamics. We prove that all strong Nash equilibria and closed cycles are stochastically stable, i.e., they are selected by perturbed CBR dynamics as mutations vanish. Similar statement holds for strict strong Nash equilibrium. We apply CBR dynamics to the network formation games and we prove that all strongly stable networks and closed cycles are stochastically stable.

Abstract:
The choice of the PageRank damping factor is not evident. The Google's choice for the value c=0.85 was a compromise between the true reflection of the Web structure and numerical efficiency. However, the Markov random walk on the original Web Graph does not reflect the importance of the pages because it absorbs in dead ends. Thus, the damping factor is needed not only for speeding up the computations but also for establishing a fair ranking of pages. In this paper, we propose new criteria for choosing the damping factor, based on the ergodic structure of the Web Graph and probability flows. Specifically, we require that the core component receives a fair share of the PageRank mass. Using singular perturbation approach we conclude that the value c=0.85 is too high and suggest that the damping factor should be chosen around 1/2. As a by-product, we describe the ergodic structure of the OUT component of the Web Graph in detail. Our analytical results are confirmed by experiments on two large samples of the Web Graph.

Abstract:
In average consensus protocols, nodes in a network perform an iterative weighted average of their estimates and those of their neighbors. The protocol converges to the average of initial estimates of all nodes found in the network. The speed of convergence of average consensus protocols depends on the weights selected on links (to neighbors). We address in this paper how to select the weights in a given network in order to have a fast speed of convergence for these protocols. We approximate the problem of optimal weight selection by the minimization of the Schatten p-norm of a matrix with some constraints related to the connectivity of the underlying network. We then provide a totally distributed gradient method to solve the Schatten norm optimization problem. By tuning the parameter p in our proposed minimization, we can simply trade-off the quality of the solution (i.e. the speed of convergence) for communication/computation requirements (in terms of number of messages exchanged and volume of data processed). Simulation results show that our approach provides very good performance already for values of p that only needs limited information exchange. The weight optimization iterative procedure can also run in parallel with the consensus protocol and form a joint consensus-optimization procedure.

Abstract:
We study the interaction between the AIMD (Additive Increase Multiplicative Decrease) congestion control and a bottleneck router with Drop Tail buffer. We consider the problem in the framework of deterministic hybrid models. First, we show that the hybrid model of the interaction between the AIMD congestion control and bottleneck router always converges to a cyclic behavior. We characterize the cycles. Necessary and sufficient conditions for the absence of multiple jumps of congestion window in the same cycle are obtained. Then, we propose an analytical framework for the optimal choice of the router buffer size. We formulate the problem of the optimal router buffer size as a multi-criteria optimization problem, in which the Lagrange function corresponds to a linear combination of the average goodput and the average delay in the queue. The solution to the optimization problem provides further evidence that the buffer size should be reduced in the presence of traffic aggregation. Our analytical results are confirmed by simulations performed with Simulink and the NS simulator.

Abstract:
We study power control in optimization and game frameworks. In the optimization framework there is a single decision maker who assigns network resources and in the game framework users share the network resources according to Nash equilibrium. The solution of these problems is based on so-called water-filling technique, which in turn uses bisection method for solution of non-linear equations for Lagrange multiplies. Here we provide a closed form solution to the water-filling problem, which allows us to solve it in a finite number of operations. Also, we produce a closed form solution for the Nash equilibrium in symmetric Gaussian interference game with an arbitrary number of users. Even though the game is symmetric, there is an intrinsic hierarchical structure induced by the quantity of the resources available to the users. We use this hierarchical structure to perform a successive reduction of the game. In addition, to its mathematical beauty, the explicit solution allows one to study limiting cases when the crosstalk coefficient is either small or large. We provide an alternative simple proof of the convergence of the Iterative Water Filling Algorithm. Furthermore, it turns out that the convergence of Iterative Water Filling Algorithm slows down when the crosstalk coefficient is large. Using the closed form solution, we can avoid this problem. Finally, we compare the non-cooperative approach with the cooperative approach and show that the non-cooperative approach results in a more fair resource distribution.

Abstract:
Two independent Poisson streams of jobs flow into a single-server service system having a limited common buffer that can hold at most one job. If a type-i job (i=1,2) finds the server busy, it is blocked and routed to a separate type-i retrial (orbit) queue that attempts to re-dispatch its jobs at its specific Poisson rate. This creates a system with three dependent queues. Such a queueing system serves as a model for two competing job streams in a carrier sensing multiple access system. We study the queueing system using multi-dimensional probability generating functions, and derive its necessary and sufficient stability conditions while solving a boundary value problem. Various performance measures are calculated and numerical results are presented.

Abstract:
We consider a general honest homogeneous continuous-time Markov process with restarts. The process is forced to restart from a given distribution at time moments generated by an independent Poisson process. The motivation to study such processes comes from modeling human and animal mobility patterns, restart processes in communication protocols, and from application of restarting random walks in information retrieval. We provide a connection between the transition probability functions of the original Markov process and the modified process with restarts. We give closed-form expressions for the invariant probability measure of the modified process. When the process evolves on the Euclidean space there is also a closed-form expression for the moments of the modified process. We show that the modified process is always positive Harris recurrent and exponentially ergodic with the index equal to (or bigger than) the rate of restarts. Finally, we illustrate the general results by the standard and geometric Brownian motions.