| +91 9790176891


Category Archives

A New Constant Factor Approximation to Construct Highly Fault-Tolerant Connected Dominating Set in Unit Disk Graph

This paper proposes a new polynomial time constant factor approximation algorithm for a more-a-decade-long open NP-hard problem, the minimum four-connected m-dominating set problem in unit disk graph (UDG) with any positive integer m ≥ 1 for the first time in the literature. We observe that it is difficult to modify the existing constant factor approximation algorithm for the minimum three-connected m-dominating set problem to solve the minimum four-connected m-dominating set problem in UDG due to the structural limitation of Tutte decomposition, which is the main graph theory tool used by Wang et al. to design their algorithm. To resolve this issue, we first reinvent a new constant factor approximation algorithm for the minimum three-connected m-dominating set problem in UDG and later use this algorithm to design a new constant factor approximation algorithm for the minimum four-connected m-dominating set problem in UDG.

Accurate Per-Packet Delay Tomography in Wireless Ad Hoc Networks

In this paper, we study the problem of decomposing the end-to-end delay into the per-hop delay for each packet, in multi-hop wireless ad hoc networks. Knowledge on the per-hop per-packet delay can greatly improve the network visibility and facilitate network measurement and management. We propose Domo, a passive, lightweight, and accurate delay tomography approach to decomposing the packet end-to-end delay into each hop. We first formulate the per packet delay tomography problem into a set of optimization problems by carefully considering the constraints among various timing quantities. At the network side, Domo attaches a small overhead to each packet for constructing constraints of the optimization problems. By solving these optimization problems by semi-definite relaxation at the PC side, Domo is able to estimate the per-hop delays with high accuracy as well as give a upper bound and lower bound for each unknown per-hop delay. We implement Domo and evaluate its performance extensively using both trace-driven studies and large-scale simulations. Results show that Domo significantly outperforms two existing methods, nearly tripling the accuracy of the state-of-the-art.

Adaptive Influence Maximization in Dynamic Social Networks

For the purpose of propagating information and ideas through a social network, a seeding strategy aims to find a small set of seed users that are able to maximize the spread of the influence, which is termed influence maximization problem. Despite a large number of works have studied this problem, the existing seeding strategies are limited to the models that cannot fully capture the characteristics of real-world social networks. In fact, due to high-speed data transmission and large population of participants, the diffusion processes in real-world social networks have many aspects of uncertainness. As shown in the experiments, when taking such uncertainness into account, the state-of-the-art seeding strategies are pessimistic as they fail to trace the influence diffusion. In this paper, we study the strategies that select seed users in an adaptive manner. We first formally model the dynamic independent Cascade model and introduce the concept of adaptive seeding strategy. Then, based on the proposed model, we show that a simple greedy adaptive seeding strategy finds an effective solution with a provable performance guarantee. Besides the greedy algorithm, an efficient heuristic algorithm is provided for better scalability. Extensive experiments have been performed on both the real-world networks and synthetic power-law networks. The results herein demonstrate the superiority of the adaptive seeding strategies to other baseline methods.

Delay Network Tomography Using a Partially Observable Bivariate Markov Chain

Estimation of link delay densities in a computer network, from source-destination delay measurements, is of great importance in analyzing and improving the operation of the network. In this paper, we develop a general approach for estimating the density of the delay in any link of the network, based on continuous-time bivariate Markov chain modeling. The proposed approach also provides the estimates of the packet routing probability at each node, and the probability of each source-destination path in the network. In this approach, the states of one process of the bivariate Markov chain are associated with nodes of the network, while the other process serves as an underlying process that affects statistical properties of the node process. The node process is not Markov, and the sojourn time in each of its states is phase-type. Phase-type densities are dense in the set of densities with non-negative support. Hence, they can be used to approximate arbitrarily well any sojourn time distribution. Furthermore, the class of phase-type densities is closed under convolution and mixture operations. We adopt the expectation-maximization (EM) algorithm of Asmussen, Nerman, and Olsson for estimating the parameter of the bivariate Markov chain. We demonstrate the performance of the approach in a numerical study.

Enabling Network Anti-Inference via Proactive Strategies: A Fundamental Perspective

Network inference is an effective mechanism to infer end-to-end flow rates and has enabled a variety of applications (e.g., network surveillance and diagnosis). This paper is focused on the opposite side of network inference, i.e., how to make inference inaccurate, which we call network anti-inference. As most research efforts have been focused on developing efficient inference methods, a design of anti-inference is largely overlooked. Anti-inference scenarios can rise when network inference is not desirable, such as in clandestine communication and military applications. Our objective is to explore network dynamics to provide anti-inference. In particular, we consider two proactive strategies that cause network dynamics: transmitting deception traffic and changing routing to mislead the inference. We build an analytical framework to quantify the induced inference errors of the proactive strategies that maintain limited costs. We find by analysis and simulations that for deception traffic, a simple random transmission strategy can achieve inference errors on the same order of the best coordinated transmission strategy, while changing routing can cause the inference errors of higher order than any deception traffic strategy. Our results not only reveal the fundamental perspective on proactive strategies, but also offer the guidance into the practical design of anti-inference.

Improved Utility-Based Congestion Control for Delay-Constrained Communication

Due to the presence of buffers in the inner network nodes, each congestion event leads to buffer queueing and thus to an increasing end-to-end delay. In the case of delay sensitive applications, a large delay might not be acceptable and a solution to properly manage congestion events while maintaining a low end-to-end delay is required. Delay-based congestion algorithms are a viable solution as they target to limit the experienced end-to-end delay. Unfortunately, they do not perform well when sharing the bandwidth with congestion control algorithms not regulated by delay constraints (e.g., loss-based algorithms). Our target is to fill this gap, proposing a novel congestion control algorithm for delay-constrained communication over best effort packet switched networks. The proposed algorithm is able to maintain a bounded queueing delay when competing with other delay-based flows, and avoid starvation when competing with loss-based flows. We adopt the well-known price-based distributed mechanism as congestion control, but: 1) we introduce a novel non-linear mapping between the experienced delay and the price function and 2) we combine both delay and loss information into a single price term based on packet interarrival measurements. We then provide a stability analysis for our novel algorithm and we show its performance in the simulation results carried out in the NS3 framework. Simulation results demonstrate that the proposed algorithm is able to: achieve good intra-protocol fairness properties, control efficiently the end-to-end delay, and finally, protect the flow from starvation when other flows cause the queuing delay to grow excessively.

Network Capability in Localizing Node Failures via End-to-End Path Measurements

We investigate the capability of localizing node failures in communication networks from binary states (normal/failed) of end-to-end paths. Given a set of nodes of interest, uniquely localizing failures within this set requires that different observable path states associate with different node failure events. However, this condition is difficult to test on large networks due to the need to enumerate all possible node failures. Our first contribution is a set of sufficient/necessary conditions for identifying a bounded number of failures within an arbitrary node set that can be tested in polynomial time. In addition to network topology and locations of monitors, our conditions also incorporate constraints imposed by the probing mechanism used. We consider three probing mechanisms that differ according to whether measurement paths are: (i) arbitrarily controllable; (ii) controllable but cycle-free; or (iii) uncontrollable (determined by the default routing protocol). Our second contribution is to quantify the capability of failure localization through: 1) the maximum number of failures (anywhere in the network) such that failures within a given node set can be uniquely localized and 2) the largest node set within which failures can be uniquely localized under a given bound on the total number of failures. Both measures in 1) and 2) can be converted into the functions of a per-node property, which can be computed efficiently based on the above sufficient/necessary conditions. We demonstrate how measures 1) and 2) proposed for quantifying failure localization capability can be used to evaluate the impact of various parameters, including topology, number of monitors, and probing mechanisms.

Optimal path encoding for software-defined networks

Packet networks need to maintain state in the form of forwarding tables at each switch. The cost of this state increases as networks support ever more sophisticated per-flow routing, traffic engineering, and service chaining. Per-flow or per-path state at the switches can be eliminated by encoding each packet’s desired path in its header. A key component of such a method is an efficient encoding of paths through the network. We introduce a mathematical formulation of this optimal path-encoding problem. We prove that the problem is APX-hard, by showing that approximating it to within a factor less than 8/7 is NP-hard. Thus, at best we can hope for a constant-factor approximation algorithm. We then present such an algorithm, approximating the optimal path-encoding problem to within a factor 2. Finally, we provide empirical results illustrating the effectiveness of the proposed algorithm.

Optimally Approximating the Coverage Lifetime of Wireless Sensor Networks

We address a classical problem concerning energy efficiency in sensor networks. In particular, we consider the problem of maximizing the lifetime of coverage of targets in a wireless sensor network with battery-limited sensors. We first show that the problem cannot be approximated within a factor less than lnn by any polynomial time algorithm, where n is the number of targets. This provides closure to the long-standing open problem of showing optimality of previously known lnn approximation algorithms. We also derive a new ln n approximation to the problem by showing the lnn approximation to the related maximum disjoint set cover problem. We show that this approach has many advantages over algorithms in the literature, including a simple and optimal extension that solves the problem with multiple coverage constraints. For the 1-D network topology, where sensors can monitor contiguous line segments of possibly different lengths, we show that the optimal coverage lifetime can be found in polynomial time. Finally, for the 2-D topology in which coverage regions are unit squares, we combine the existing results to derive a 1 + € approximation algorithm for the problem. Extensive simulation experiments validate our theoretical results, showing that our algorithms not only have optimal worst case guarantees but also match the performance of the existing algorithms on special network topologies. In addition, our algorithms sometimes run orders of magnitude faster than the existing state of the art.