Sarkar, Saswati
Email Address
ORCID
Disciplines
relationships.isProjectOf
relationships.isOrgUnitOf
Position
Introduction
Research Interests
Collection
50 results
Search Results
Now showing 1 - 10 of 50
Publication Maximum Damage Malware Attack in Mobile Wireless Networks(2010-03-01) Khouzani, MHR; Sarkar, Saswati; Altman, EitanMalware attacks constitute a serious security risk that threatens to slow down the large scale proliferation of wireless applications. As a first step towards thwarting this security threat, we seek to quantify the maximum damage inflicted on the system owing to such outbreaks and identify the most vicious attacks. We represent the propagation of malware in a battery-constrained mobile wireless network by an epidemic model in which the worm can dynamically control the rate at which it kills the infected node and also the transmission range and/or the media scanning rate. At each moment of time, the worm at each node faces the following trade-offs: (i) using larger transmission range and media scanning rate to accelerate its spread at the cost of exhausting the battery and thereby reducing the overall infection propagation rate in the long run or (ii) killing the node to inflict a large cost on the network, however at the expense of loosing the chance of infecting more susceptible nodes at later times. We mathematically formulate the decision problems and utilize Pontryagin Maximum Principle from optimal control theory to quantify the damage that the malware can inflict on the network by deploying optimum decision rules. Next, we establish structural properties of the optimal strategy of the attacker over time. Specifically, we prove that it is optimal for the attacker to defer killing of the infective nodes in the propagation phase for a certain time and then start the slaughter with maximum effort. We also show that in the optimal attack policy, the battery resources are used according to a decreasing function of time, i.e., mostly during the initial phase of the outbreak. Finally, our numerical investigations reveal a framework for identifying intelligent defense strategies that can limit the damage by appropriately selecting network parameters.Publication Arbitrary Throughput Versus Complexity Tradeoffs in Wireless Networks Using Graph Partitioning(2008-11-01) Sarkar, Saswati; Ray, SaikatSeveral policies have recently been proposed for attaining the maximum throughput region, or a guaranteed fraction thereof, through dynamic link scheduling. Among these policies, the ones that attain the maximum throughput region require a computation time which is linear in the network size, and the ones that require constant or logarithmic computation time attain only certain fractions of the maximum throughput region. In contrast, in this paper we propose policies that can attain any desirable fraction of the maximum throughput region using a computation time that is largely independent of the network size. First, using a combination of graph partitioning techniques and Lyapunov arguments, we propose a simple policy for tree topologies under the primary interference model that requires each link to exchange only 1 bit information with its adjacent links and approximates the maximum throughput region using a computation time that depends only on the maximum degree of nodes and the approximation factor. Then we develop a framework for attaining arbitrary close approximations for the maximum throughput region in arbitrary networks, and use this framework to obtain any desired tradeoff between throughput guarantees and computation times for a large class of networks and interference models. Specifically, given any ∊ ≻ 0, the maximum throughput region can be approximated in these networks within a factor of 1- ∊ using a computation time that depends only on the maximum node degree and ∊.Publication RIDA: Robust Intrusion Detection in Ad Hoc Networks(2005-05-02) Subhadrabandhu, Dhanant; Sarkar, Saswati; Anjum, FarooqWe focus on detecting intrusions in wireless ad hoc networks using the misuse detection technique. We allow for detection modules that periodically fail to detect attacks and also generate false positives. Combining theories of hypothesis testing and approximation algorithms, we develop a framework to counter different threats while minimizing the resource consumption. We obtain computationally simple optimal rules for aggregating and thereby minimizing the errors in the decisions of the nodes executing the intrusion detection software (IDS) modules. But, we show that the selection of the optimal set of nodes for executing the IDS is an NP-hard problem. We present a polynomial complexity selection algorithm that attains a guaranteeable approximation bound. We also modify this algorithm to allow for seamless operation in time varying topologies, and evaluate the efficacy of the approximation algorithm and its modifications using simulation. We identify a selection algorithm that attains a good balance between performance and complexity for attaining robust intrusion detection in ad hoc networks.Publication Back Pressure Based Multicast Scheduling for Fair Bandwidth Allocation(2005-09-01) Sarkar, Saswati; Tassiulas, LeandrosWe study the fair allocation of bandwidth in multicast networks with multirate capabilities. In multirate transmission, each source encodes its signal in layers. The lowest layer contains the most important information and all receivers of a session should receive it. If a receiver’s data path has additional bandwidth, it receives higher layers which leads to a better quality of reception. The bandwidth allocation objective is to distribute the layers fairly. We present a computationally simple, decentralized scheduling policy that attains the maxmin fair rates without using any knowledge of traffic statistics and layer bandwidths. This policy learns the congestion level from the queue lengths at the nodes, and adapts the packet transmissions accordingly. When the network is congested, packets are dropped from the higher layers; therefore, the more important lower layers suffer negligible packet loss. We present analytical and simulation results that guarantee the maxmin fairness of the resulting rate allocation, and upper bound the packet loss rates for different layers.Publication Stochastic Control Techniques for Throughput Optimal Wireless Multicast(2003-12-09) Chaporkar, Prasanna; Sarkar, SaswatiWe design transmission strategies for MAC layer multicast which maximize the utilization of available bandwidth. Bandwidth efficiency of wireless multicast can be improved substantially by exploiting the fact that several receivers can be reached at the MAC layer by a single transmission. However, this feature can be effectively exploited only by resolving several decision problems. The fundamental relations between QoS parameters such as throughput, stability and loss change on account of the multicast nature of transmissions, e.g., a strategy that maximizes the system throughput does not necessarily maximize the stability region or minimize packet loss. We explore the trade-off between the QoS parameters, and provide optimal transmission strategies which maximize the system throughput subject to stability and loss constraints.Publication A statistical framework for intrusion detection in ad hoc networks(2006-04-01) Subhadrabandhu, Dhanant; Sarkar, Saswati; Farooq, AnjunWe focus on detecting intrusions in ad hoc networks using the misuse detection technique. We allow for detection modules that periodically fail to detect attacks and also generate false positives. Combining theories of hypothesis testing and approximation algorithms, we develop a framework to counter different threats while minimizing the resource consumption. We obtain computationally simple optimal rules for aggregating and thereby minimizing the errors in the decisions of the nodes executing the intrusion detection software (IDS) modules. But, we show that the selection of the optimal set of nodes for executing the IDS is an NP-hard problem. We describe a polynomial complexity, distributed selection algorithm, "Maximum Unsatisfied Neighbors in Extended Neighborhood" (MUNEN) that attains the best possible approximation ratio. The aggregation rules and MUNEN can be executed by mobile nodes with limited processing power. The overall framework provides a good balance between complexity and performance for attaining robust intrusion detection in ad hoc networks.Publication Minimizing Delay in Loss-Tolerant MAC Layer Multicast(2006-10-01) Chaporkar, Prasanna; Sarkar, SaswatiThe goal of this correspondence is to minimize delay in real-time multiple-access channel (MAC) layer multicast by exploiting the broadcast nature of wireless medium and limited loss tolerance of the applications. Multiple transmissions of a packet at the MAC layer significantly reduces the delay than that when only one transmission is allowed. But each additional transmission consumes additional power and increases network load. Therefore, the goal is to design a policy that judiciously uses the limited transmission opportunities so as to deliver each packet in the minimum possible time to the required number of group members. The problem is an instance of the stochastic shortest path problem, and using this formulation computationally simple, closed-form transmission strategies have been obtained in important special cases.Publication Throughput and Fairness Guarantees Through Maximal Scheduling in Wireless Networks(2008-02-01) Chaporkar, Prasanna; Kar, Koushik; Luo, Xiang; Sarkar, SaswatiThe question of providing throughput guarantees through distributed scheduling, which has remained an open problem for some time, is addressed in this paper. It is shown that a simple distributed scheduling strategy, maximal scheduling, attains a guaranteed fraction of the maximum throughput region in arbitrary wireless networks. The guaranteed fraction depends on the "interference degree" of the network, which is the maximum number of transmitter–receiver pairs that interfere with any given transmitter–receiver pair in the network and do not interfere with each other. Depending on the nature of communication, the transmission powers and the propagation models, the guaranteed fraction can be lower-bounded by the maximum link degrees in the underlying topology, or even by constants that are independent of the topology. The guarantees are tight in that they cannot be improved any further with maximal scheduling. The results can be generalized to end-to-end multihop sessions. Finally, enhancements to maximal scheduling that can guarantee fairness of rate allocation among different sessions, are discussed.Publication Fair Coalitions for Power-Aware Routing in Wireless Networks(2004-12-14) Guha, Ratul K.; Gunter, Carl A.; Sarkar, SaswatiSeveral power aware routing schemes have been developed under the assumption that nodes are willing to sacrifice their power reserves in the interest of the network as a whole. But, in several applications of practical utility, nodes are organized in groups, and as a result a node is willing to sacrifice in the interest of other nodes in its group but not necessarily for nodes outside its group. Such groups arise naturally as sets of nodes associated with a single owner or task. We consider the premise that groups will share resources with other groups only if each group experiences a reduction in power consuption. When this is the case the groups may form a coalition in which they route each other's packets. We demonstrate that sharing between groups has different properties from sharing between individuals and investigate fair mutually-beneficial sharing between groups. In particular, we propose a pareto-efficient condition for group sharing based on max-min fairness called fair coalition routing. We propose distributed algorithms for computing the fair coalition routing. Using these algorithms we demonstrate that fair coalition routing allows different groups to mutually benefecially share their resources.Publication Fair Bandwidth Allocation for Multicasting in Networks with Discrete Feasible Set(2004-07-01) Sarkar, Saswati; Tassiulas, LeandrosWe study fairness in allocating bandwidth for loss-tolerant real-time multicast applications. We assume that the traffic is encoded in several layers so that the network can adapt to the available bandwidth and receiver processing capabilities by varying the number of layers delivered. We consider the case where receivers cannot subscribe to fractional layers. Therefore, the network can allocate only a discrete set of bandwidth to a receiver, whereas a continuous set of rates can be allocated when receivers can subscribe to fractional layers. Fairness issues differ vastly in these two different cases. Computation of lexicographic optimal rate allocation becomes NP-hard in this case, while lexicographic optimal rate allocation is polynomial complexity computable when fractional layers can be allocated. Furthermore, maxmin fair rate vector may not exist in this case. We introduce a new notion of fairness, maximal fairness. Even though maximal fairness is a weaker notion of fairness, it has many intuitively appealing fairness properties. For example, it coincides with lexicographic optimality and maxmin fairness, when maxmin fair rate allocation exists. We propose a polynomial complexity algorithm for computation of maximally fair rates allocated to various source-destination pairs, which incidentally computes the maxmin fair rate allocation, when the latter exists.