Search for: All records

We study how to schedule data sources in a wireless time-sensitive information system with multiple heterogeneous and unreliable channels to minimize the total expected Age-of-Information (AoI). Although one could formulate this problem as a discrete-time Markov Decision Process (MDP), such an approach suffers from the curse of dimensionality and lack of insights. For single-channel systems, prior studies have developed lower-complexity solutions based on the Whittle index. However, Whittle index has not been studied for systems with multiple heterogeneous channels, mainly because indexability is not well defined when there are multiple dual cost values, one for each channel. To overcome this difficulty, we introduce new notions of partial indexability and partial index, which are defined with respect to one channel's cost, given all other channels' costs. We then combine the ideas of partial indices and max-weight matching to develop a Sum Weighted Index Matching (SWIM) policy, which iteratively updates the dual costs and partial indices. The proposed policy is shown to be asymptotically optimal in minimizing the total expected AoI, under a technical condition on a global attractor property. Extensive performance simulations demonstrate that the proposed policy offers significant gains over conventional approaches by achieving a near-optimal AoI. Further, the notion of partial index is of independent interest and could be useful for other problems with multiple heterogeneous resources. 

There has been significant interest in leveraging limited look-ahead to achieve low competitive ratios for online convex optimization (OCO). However, existing online algorithms (such as Averaging Fixed Horizon Control (AFHC)) that can leverage look-ahead to reduce the competitive ratios still produce competitive ratios that grow unbounded as the coefficient ratio (i.e., the maximum ratio of the switching-cost coefficient and the service-cost coefficient) increases. On the other hand, the regularization method can attain a competitive ratio that remains bounded when the coefficient ratio is large, but it does not benefit from look-ahead. In this paper, we propose a new algorithm, called Regularization with Look-Ahead (RLA), that can get the best of both AFHC and the regularization method, i.e., its competitive ratio decreases with the look-ahead window size when the coefficient ratio is small, and remains bounded when the coefficient ratio is large. We also provide a matching lower bound for the competitive ratios of all online algorithms with look-ahead, which differs from the achievable competitive ratio of RLA by a factor that only depends on the problem size. The competitive analysis of RLA involves a non-trivial generalization of online primal-dual analysis to the case with look-ahead. 

Operating distributed Scrubbing Centers (SCs) to mitigate massive Distributed Denial of Service (DDoS) traffic in large-scale networks faces critical challenges. The operator needs to determine the diversion rule installation and elimination in the networks, as well as the scrubbing resource activation and revocation in the SCs, while minimizing the long-term cost and the cumulative decision-switching penalty without knowing the exact amount of the malicious traffic. We model and formulate this problem as an online nonlinear integer program. In contrast to many other online problems where future inputs are unknown but at least current inputs are known, a key new challenge here is that even part of the current inputs are unknown when decisions are made. To learn the best decisions online, we transform our problem via a gap-preserving approximation into an online optimization problem with only the known inputs, which is further relaxed and decoupled into a series of one-shot convex programs solvable in individual time slots. To overcome the intractability, we design a progressive rounding algorithm to convert fractional decisions into integral ones without violating the constraints. We characterize the competitive ratio of our approach as a function of the key parameters of our problem. We conduct evaluations using real-world data and confirm our algorithms’ superiority over de facto practices and state-of-the-art methods 

Operating distributed cloudlets at optimal cost is nontrivial when facing not only the dynamic and unpredictable resource prices and user requests, but also the low efficiency of today's immature cloudlet infrastructures. We propose to control cloudlet networks at multiple granularities - fine-grained control of servers inside cloudlets and coarse-grained control of cloudlets themselves. We model this problem as a mixed-integer nonlinear program with the switching cost over time. To solve this problem online, we firstly linearize, "regularize", and decouple it into a series of one-shot subproblems that we solve at each corresponding time slot, and afterwards we design an iterative, dependent rounding framework using our proposed randomized pairwise rounding algorithm to convert the fractional control decisions into the integral ones at each time slot. Via rigorous theoretical analysis, we exhibit our approach's performance guarantee in terms of the competitive ratio and the multiplicative integrality gap towards the offline optimal integral decisions. Extensive evaluations with real-world data confirm the empirical superiority of our approach over the single granularity server control and the state-of-the-art algorithms.