# Webmail

 IITB/CSE/2013/February/51, TR-CSE-2013-51Stochastic Model Based Opportunistic Spectrum Access in Wireless Networks Manuj Sharma and Anirudha Sahoo We present a stochastic model based opportunistic channel access and transmission scheme for cognitive radio-enabled secondary users for single data channel. We refer to this scheme as RIBS (Residual Idle Time Distribution based Scheme). In this scheme, the SU uses residual white space distribution to estimate its transmission duration such that the probabilityof its interference with PU is less than a predefined threshold value. We derive analytical formulae for computing the average raw SU frames per transmission operation, average raw SU throughput, and the average sensing overhead for SU. Using simulation experiments, we show that using RIBS, SU can use the channel opportunistically without violating the interferenceprobability constraint. We conduct simulation experiments by collecting channel occupancy data due to PU traffic in two different scenarios. In the first scenario, we synthetically generate channel occupancy data due to PU transmissions using two standard distributions (2-phase Erlang and Uniform distribu-tion). We validate the analytical formulations using simulation with synthetic channel occupancy. In the second scenario, we simulate a PU network that runs realistic applications (VoIP andWeb browsing) using a TDMA MAC protocol. A pair of sender and receiver SU uses RIBS to opportunistically transmit on the channel. We analyze the characteristics of white spaces obtained due to these realistic applications, list some of the challenges in using RIBS in realistic scenarios, and provide comprehensive methodology to use RIBS in primary network running real applications. IITB/CSE/2013/February/50, TR-CSE-2013-50Resource Availability Based Performance Benchmarking of Virtual Machine Migrations Senthil Nathan, Purushottam Kulkarni, and Umesh Bellur Virtual machine migration enables load balancing, hot spot mitigation and server consolidation in virtualized environments. Live VM migration can be of two types - adaptive, in which the rate of page transfer adapts to virtual machine behavior (mainly page dirty rate), and non-adaptive, in which the VM pages are transferred at a maximum possible network rate. In either method, migration requires a significant amount of CPU and network resources, which can seriously impact theperformance of both the VM being migrated as well as other VMs. This calls for building a good understanding of the performance of migration itself and the resource needs of migration. Such an understanding can help select the appropriate VMs for migration while at the same time allocating the appropriate amount of resources for migration. While several empirical studies exist, a comprehensive evaluation of migration techniques with resource availability constraints is missing. As a result, it is not clear as to which migration technique to employ under a given set of conditions. In this work, we conduct a comprehensive empirical study to understand the sensitivity of migration performance to resource availability and other system parameters (like page dirty rate and VM size). The empirical study (with the Xen Hypervisor) reveals several shortcomings of the migration process. We propose several fixes and develop the Improved Live Migration technique (ILM) to overcome these shortcomings. Over a set of workloads used to evaluate ILM, the network traffic for migration was reduced by 14-93\% and the migration time was reduced by 34-87\% compared to the vanilla live migration technique. We also quantified the impact of migration on the performance of applications running on the migrating VM and other co-located VMs. IITB/CSE/2013/February/49, TR-CSE-2013-49All page sharing is equal, but some sharing is more equal than others Shashank Rachamalla, Debadatta Mishra, Purushottam Kulkarni Content based memory sharing in virtualized environments has been proven to be a useful memory management technique. As part of this work, we are interested in studying the trade-off between extent of sharing opportunities (compared to actual sharing potential) that can be identified and the overheads for doing the same. Our work is based on Kernel Virtual Machine (KVM) in Linux which in turn uses Kernel Samepage Merging (KSM) to identify and exploit sharing opportunities. We instrument the Linux kernel and KSM to log sharing and copy-on-write related parameters for accurate estimation of useful and effective KSM sharing extent. For several combinations of workloads, exhibiting different memory usage characteristics, we benchmark KSM performance (achieved savings vs. total possible savings) and CPU overheads for different KSM configurations. The benchmarking results are used to develop an adaptive scheme to dynamically reconfigure KSM configuration parameters (scan rate and pages per scan), to maximize shar ing opportunities at minimal overheads. We evaluate the adaptive technique and compare it with default settings of KSM to show its efficacy. Based on our experiments we show that the adaptive sharing technique correctly adapts scan rate of KSM based on sharing potential. With our setup, the adaptive sharing technique yields a factor of 10 improvement in memory savings at negligible increase in CPU utilization. IITB/CSE/2012/September/48, TR-CSE-2012-48Building A Low Cost Low Power Wireless Network To Enable Voice Communication In Developing Regions Vijay Gabale, Jeet Patani, Rupesh Mehta, Ramakrishnan Kalyanaraman, Bhaskaran Raman In this work, we describe our experiences in building a low cost and low power wireless mesh network using IEEE 802.15.4 technology to provide telephony services in rural regions of the developing world. 802.15.4 was originally designed for a completely different application space of non-real-time, low data rate embedded wireless sensing. We use it to design and prototype a telephony system, which we term as Lo3 (Low cost, Low power, Local voice). Lo3 primarily provides two use cases; (1) local and broadcast voice within the wireless mesh network, and (2) remote voice to a phone in the outside world. A Lo3 network can cost as less as $2K, and can last for several days without power “off the grid”, thus making it an ideal choice to meet cost and power constraints of rural regions. We test deployed a full-fledged Lo3 system in a village near Mumbai, India for 18 hours over 3 days. We established voice calls with an end-to-end latency of less than 120ms, with anaverage packet loss of less than 2%, and a MOS of 3.6 which is considered as good inpractice. The users too gave a positive response to our system. We also tested Lo3 withinour department where it can be used as a wireless intercom service. To our knowledge, Lo3is the first system to enable such a voice communication system using 802.15.4 technology,and show its effectiveness in operational settings. IITB/CSE/2012/July/46, TR-CSE-2012-46Host-Bypass: Approximating Node-Weighted Connectivity Problems In Two-Tier Networks Vijay Gabale, Ashish Chiplunkar We focus on network design problems in those networks which have two distinct sets or {it tiers} of network nodes: hosts and infrastructure nodes. For instance, wireless mesh networks are often composed of the infrastructure nodes which relay the data between the client nodes. Similarly, the switches (infrastructure) in data center networks sit between the servers (hosts) to route the information flow. In such {it two-tier} networks, a network designer typically requires paths between hosts in the host-tier through nodes in the infrastructure-tier while minimizing the cost in building the network. A subtle constraint, which we call as {it the host-tier constraint},in choosing such paths requires that no host in host-tier is an intermediate node on any path. Often, this constraint is necessary for designing network topologies in practice. In this work, we first show that the network design algorithms in prior work are inapplicable to the above described Two-Tier Network Connectivity (TTNC) problem with the host-tier constraint. We then investigate TTNC problem with the goal of minimizing the cost in building the network. We show that TTNC problem is NP-hard, and present {it Host-Bypass}, the first algorithm for TTNC problem with provable performance bound on cost of$O(h^{frac{1}{2}+epsilon} log^2 h)$where$h$is the number of host nodes,$epsilon > 0$. Host-Bypass has polynomial running time of$O(n^{1+frac{1}{epsilon}}h^{2+frac{2}{epsilon}})$($n$is total number of nodes), and our simulation study shows that Host-Bypass performs close to optimal and is 30\% better than a heuristic from an algorithm in prior work. IITB/CSE/2012/July/45, TR-CSE-2012-45A Per-File Partitioned Page Cache Prateek Sharma, Purushottam Kulkarni In this paper we describe a new design of the operating system pagecache. Page caches form an important part of the memory hierarchy andare used to access file-system data. In most operating systems, thereexists a single page cache whose contents are replaced according toa LRU eviction policy.We design and implement a page cache which is partitioned byfile---the per-file page cache. The per-file page cache providesthe ability to control fine-grained caching parameters such as cachesize and eviction policies for each file. Furthermore, the deterministiccache allocation and partitioning allows for improved isolation amongprocesses. We provide dynamic cache partitioning(among files) byusing utility derived from the miss-ratio characteristics of thefile accesses.We have implemented the per-file page cache architecture in the Linux kerneland demonstrate its efficacy using disk image files of virtual machinesand different types of file access patterns by processes.Experimental results show that the utility-based partitioning canreduce the cache size by up to an order of magnitude while increasingcache hit ratios by up to 20%. Among other features, the per-file pagecache has fadvise integration, a scan-resistant eviction algorithmand reduced lock-contention and overhead during the eviction process. IITB/CSE/2012/February/42, TR-CSE-2012-42Singleton: System-wide Page Deduplication in Virtual Environments Prateek Sharma, Purushottam Kulkarni We consider the problem of providing memory-management in hypervisors and propose Singleton, a KVM-based system-wide page deduplication solution to increase memory usage efficiency. Specifically, we address the problem of double-caching that occurs in KVM---the same disk blocks are cached at both the host(hypervisor) and the guest(VM) page-caches. Singleton's main components are identical-page sharing across guest virtual machines and an implementation of an exclusive-cache for the host and guest page-cache hierarchy. We use and improve KSM--Kernel SamePage Merging to identify and share pages across guest virtual machines. We utilize guest memory-snapshots to scrub the host page-cache and maintain a single copy of a page across the host and the guests. Singleton operates on a completely black-box assumption---we do not modify the guest or even the hypervisor. We show that conventional operating system cache management techniques are sub-optimal for virtual environments, and how Singleton supplements and improves the existing Linux kernel memory management mechanisms. Singleton is able to improve the utilization of the host cache by reducing its size(by upto an order of magnitude), and increasing the cache-hit ratio(by factor of 2x). This translates into better VM performance(40% faster I/O). Singleton's unified page deduplication and host cache scrubbing is able to reclaim large amounts of memory and facilitates higher levels of memory overcommitment. The optimizations to page deduplication we have implemented keep the overhead down to less than 20% CPU utilization. IITB/CSE/2011/December/41, TR-CSE-2011-41General Caching with Lifetimes Ashish Chiplunkar, Sundar Vishwanathan We consider the problem of caching with lifetimes, where a lifetime is specified whenever a page is loaded into the cache. The copy of a page loaded into the cache may be used to serve requests to the same page, only until its expiration time. We present a generic method to get an algorithm for caching with lifetimes, from an algorithm for caching without lifetimes. This method works for any cost model, and in online as well as offline settings. In the online (resp. offline) setting, the competitive (resp. approximation) ratio of resulting algorithm for caching with lifetimes, is one more than the competitive (resp. approximation) ratio of the original algorithm for caching without lifetimes. Using this method and the existing algorithms for caching without lifetimes, we get an$H_k+1$competitive randomized algorithm and a$2$-approximation algorithm for standard caching with lifetimes, where$k$is the cache size. This is an improvement over the$(2H_k+3)$-competitive algorithm and the$3$-approximation algorithm given by Gopalan et. al. \cite{GopalanKMMV02}. We also get$\mathcal{O}(\log k)$competitive randomized algorithms for various subclasses of general caching such as weighted caching and the Bit and Fault models, asymptotically matching the lower bound of$H_k$on the competitive ratio; and a$5\$ approximation algorithm for the general offline caching problem. IITB/CSE/2011/December/40, TR-CSE-2011-40Importance Aware Bloom Filter for Set Membership Queries in Streaming Data Purushottam Kulkarni, Ravi Bhoraskar, Vijay Gabale, Dhananjay Kulkarni Various data streaming applications like news feeds, stock trading generate a continuous sequence of data items. In such applications, based on the priority of different items, a set of items are more important than others. For instance, in stock trading, some stocks are more important than others, or in a cache-based system, the cost of fetching new objects into the cache is directly related to the the size of the objects. Motivated by these examples, our work focuses on developing a time and space efﬁcient indexing and membership query scheme which takes into account data items with different importance levels. In this respect, we propose Importance-aware Bloom Filter (IBF), an extension of Bloom Filter (BF) which is a popular data structure to approximately answer membership queries on a set of items. As part of IBF, we provide a set of insertion and deletion algorithms to make BF importance-aware and to handle a set of unbounded data items. Our comparison of IBF with other Bloom ﬁlter-based mechanisms, for synthetic as well as real data sets, shows that IBF performs very well, it has low false positives, and low false negatives for important items. Importantly, we ﬁnd properties of IBF analytically, for instance, we show that there exists a tight upper bound on false positive rate independent of the size of the data stream. We believe, IBF provides a practical framework to balance the application-speciﬁc requirements to index and query data items based on the data semantics. IITB/CSE/2011/September/39, TR-CSE-2011-39"At least one" caching Ashish Chiplunkar, Sundar Vishwanathan We consider a variant of the caching problem, where each request is a set of pages of a ﬁxed size, instead of a single page. In order to serve such a request, we require at least one of those pages to be present in the cache. Each page is assumed to have unit size and unit cost for getting loaded into the cache. We prove lower bounds on the competitive ratio for this problem in both the deterministic and the randomized settings. We also give online algorithms for both settings and analyze them for competitive ratio. IITB/CSE/2011/May/35, TR-CSE-2011-35Efficient Rule Ensemble Learning using Hierarchical Kernels Pratik J., J. Saketha Nath and Ganesh R. This paper addresses the problem of Rule Ensemble Learning (REL), where the goal is simultaneous discovery of a small set of simple rules and their optimal weights that lead to good generalization. Rules are assumed to be conjunctions of basic propositions concerning the values taken by the input features. From the perspectives of interpretability as well as generalization, it is highly desirable to construct rule ensembles with low training error, having rules that are i) simple, {\em i.e.}, involve few conjunctions and ii) few in number. We propose to explore the (exponentially) large feature space of all possible conjunctions optimally and efficiently by employing the recently introduced Hierarchical Kernel Learning (HKL) framework. The regularizer employed in the HKL formulation can be interpreted as a potential for discouraging selection of rules involving large number of conjunctions -- justifying its suitability for constructing rule ensembles. Simulation results show that, in case of many benchmark datasets, the proposed approach improves over state-of-the-art REL algorithms in terms of generalization and indeed learns simple rules. Although this is encouraging, it can be shown that HKL selects a conjunction only if all its subsets are selected, and this is highly undesirable. We propose a novel convex formulation which alleviates this problem and generalizes the HKL framework. The main technical contribution of this paper is an efficient mirror-descent based active set algorithm for solving the new formulation. Empirical evaluations on REL problems illustrate the utility of generalized HKL. IITB/CSE/2011/February/34, TR-CSE-2011-34Affinity-aware Modeling of CPU Usage for Provisioning Virtualized Applications Sujesha Sudevalayam, Purushottam Kulkarni While virtualization-based systems become a reality, an important issue is that of virtual machine migration-enabled consolidation and dynamic resource provisioning. Mutually communicating virtual machines, as part of migration and consolidation strategies, may get co-located on the same physical machine or placed on different machines. In this work, we argue the need for network affinity-aware resource provisioning for virtual machines. First, we empirically demonstrate and quantify the resource savings due to colocation of communicating virtual machines. We also discuss the effect on resource usage due to dispersion of previously co-located virtual machines. Next, we build models based on different resource-usage micro-benchmarks to predict the resource usages when moving from non-colocated placements to co-located placements and vice-versa. These generic models can serve as animportant input for consolidation and splitting decisions. Via extensive experimentation, we evaluate the applicability of our models using synthetic and real application workloads. IITB/CSE/2010/December/33, TR-CSE-2010-33Distributed Fault Tolerance for WSNs with Routing Tree Overlays Chilukuri Shanti and Anirudha Sahoo WSNs are inherently power constrained and areoften deployed in harsh environments. As such, node death isa possibility that must be considered while designing protocolsfor such networks. Rerouting of data is generally necessary sothat data from the descendant nodes of the dead node canreach the sink. Since slot allocation in TDMA MAC protocolsis generally done based on the routing tree, all the nodes mustswitch to the new routing tree to avoid collisions. This necessitatesdisseminating the fault information to all the nodes reliably. Wepropose a flooding algorithm for disseminating fault info to thenetwork reliably even in a lossy channel. Simulation results showthat the proposed flooding scheme consumes lesser energy andconverges faster than a simple flooding scheme. Rerouting thedata may result in increased TDMA schedule length. The energyexpenditure of the newly assigned parents also increases becausethey have to relay data from more children than before. Wepropose two distributed parent assignment algorithms in thispaper. The first algorithm minimizes the change in the TDMAschedule and the second algorithm balances the load among thenewly assigned parents. Simulation of random topologies showsthat the increase in the TDMA frame length is lesser than thatwith random parent assignment when the first algorithm is used.We also observe that the lifetime of the most energy constrainednode (after fault recovery) is longer when the second algorithmis used than that when random parent assignment is done. IITB/CSE/2010/November/32, TR-CSE-2010-32On Delay-constrained Scheduling in Multi-radio, Multi-channel Wireless Mesh Vijay Gabale, Ashish Chiplunkar, Bhaskaran Raman In this work, we consider the goal of scheduling the maximum number of voice calls in a TDMA-based multi-radio, multi-channel mesh network. One of main challenges to achieve this goal is the difficulty in providing strict (packet-level) delay guarantees for voice traffic in capacity limited multi-hop wireless networks. In this respect, we propose DelayCheck, an online centralized scheduling and call-admission-control (CAC) algorithm which effectively schedules constant-bit-rate voice traffic in TDMA-based mesh networks. DelayCheck solves the joint routing, channel assignment and link scheduling problem along with delay constraint. We formulate a relaxed version of this scheduling problem as an Integer Linear Program (ILP), the LP version of which gives us an optimality upper bound. We compare the output of DelayCheck with the LP-based upper bound as well as with two state-of-the-art prior scheduling algorithms. DelayCheck performs remarkably well, accepting about 93\% of voice calls as compared to LP-based upper bound. As compared to state-of-the-art algorithms, DelayCheck improves scheduler efficiency by more than 34\% and reduces call rejections by 2 fold. We also demonstrate that DelayCheck efficiently exploits the number of channels available for scheduling. With implementation optimizations, we show that DelayCheck has low memory and CPU requirements, thus making it practical. IITB/CSE/2010/August/31, TR-CSE-2010-31Ranking in Information Retrieval Joydip Datta In this report we study several aspects of an information retrieval with focus on ranking. First we introduce basic concepts of information retrieval and several components of an information retrieval system. Then we discuss important theoretical models of IR. Web-specific c topics likelink analysis and anchor text are presented next. We discuss how IR systems are evaluated and different IR evaluation forums. We end the report with a case study of cross lingual information retrieval system at IIT Bombay. In the future scope, we introduce upcoming trends in Web IR like user modeling and Quantum IR. IITB/CSE/2010/June/30, TR-CSE-2010-30Residual White Space Distribution Based Opportunistic Channel Access Scheme for Cognitive Radio Systems Manuj Sharma and Anirudha Sahoo We propose an opportunistic channel access scheme for cognitive radio-enabledsecondary networks. In our work, we model the channel occupancy due to PrimaryUser (PU) activity as a 2-state Alternating Renewal Process, with alternatingbusy and idle periods. Once a Secondary Node (SN) senses the channel idle, theproposed scheme uses the residual idle time distribution to estimate the transmissionduration in the remaining idle time. The SN transmits the frames within thetransmission duration without further sensing the channel, thereby reducing averagesensing overhead per transmitted frame. The analytical formulations used bythe scheme does not require the SN to know the start of the idle period. We validatethe analytical formulations using simulations, and compare the performance of theproposed scheme with a Listen-Before-Talk (LBT) scheme. IITB/CSE/2010/April/29, TR-CSE-2010-29Balancing Response Time and CPU allocation in Virtualized Data Centers using Optimal Controllers Varsha Apte, Purushottam Kulkarni, Sujesha Sudevalayam and Piyush Masrani The cloud computing paradigm proposes a flexible payment model, where a cloud user pays only for the amount of resources used. Thus, the cloud provider must only allocate as many resources to a user, as are to meet client performance requirements. In this paper, we present a control-theoretic approach to tune the CPU resource allocated to a virtual machine (VM) such that application performance metrics are optimized while using minimal CPU resource. Moreover, our approach expects no inputs of performance targets to steer the system towards optimal values of CPU share allocations and system performance. We prototype and validate our methodology on a small virtualized testbed using the Xen virtualization environment. A simple server consolidation scheme which triggers VM migrations and powers servers up and down, uses our control-theoretic resource tuning approach. Preliminary results demonstrate that our controller allocates CPU share optimally, even in the presence of changing load, and can work well with a server consolidationscheme to achieve good application performance. IITB/CSE/2010/March/25, TR-CSE-2010-25Reachability of Safe State for Online Update of Concurrent Programs Yogesh Murarka and Umesh Bellur Online update helps in reducing the maintenance downtime by applying a patch to a running process. To avoid the errors that can arise due to an online update, existing online update solutions interleave the update with process execution at specific states called safe states. This approach works well for sequential processes but for multithreaded process it presents the challenge of reaching a safe state across all threads. It turns out that in concurrent processes, even if individual threads can reach a safe state in bounded time a process may take unbounded time to reach a safe state or may never reach it. Therefore, with existing update solutions a user is uncertain whether a patch can be applied or not till the user tries to apply the patch.In this report we address the problem of safe state reachability for multithreaded processes. We prove that identifying whether a process can reach a safe state is undecidable. Hence, we derive a sufficient (conservative) condition for checking the reachability of a safe state. Our novel thread scheduling technique can force a process to reach a safe state in bounded time if the sufficient condition is met. The proposed approach eliminates the uncertainty of online updates. Complexity analysis of our algorithms shows that the practical implementation of our technique will work well with most real-world applications. IITB/CSE/2009/October/24, TR-CSE-2009-24Energy aware contour covering using collaborating mobile sensors Sumana Srinivasan, Krithi Ramamritham, Purushottam Kulkarni Environmental sensing systems are useful in the area of disaster management where the system can provide alerts as well as remediation services in the event of a disaster such as pollutant spills. Recent advances in robotics technology have led to the development of sensors with the ability to sense, move, andwe show how such sensors can be deployed to perform tasks such as locating and covering a hazardous concentration contour in a pollutant spill. As mobile sensors consume energy for movement and have limited available energy, it is important for the sensors to plan their movement such that the coverage is maximized and the error in coverage (i.e., area not relevant to the contour) is minimized. In this paper, we address the nontrivial problem of continuously adjusting the direction of movement by presenting a distributed algorithm where a sensor determines the direction of movement by (i) estimating the distance to the contour and perimeter of the contour using locally sensed information as well as information gathered through collaboration and (ii) deciding dynamically whether to directly approach the contour or surround the contour based on the amount of work remaining to be done by the sensor vis a vis the energy remaining. We show that our proposed algorithm has the best coverage vs. error trade-off when compared to algorithms that directly approach or surround the contour. IITB/CSE/2009/October/23, TR-CSE-2009-23Light-trains: An Integrated Optical-Wireless Solution for High Bandwidth Applications in High-Speed Metro-Trains Ashwin Gumaste, Akhil Lodha, Saurabh Mehta, Jianping Wang and Si Qing Zheng Moving trains represent a voluminous mass of usersmoving at high velocities that require bandwidth (on demand). All wireless solutions alone cannot scale efficiently to provide for bandwidth to such fast-moving voluminous users. A new solution is proposed that facilitates dynamic provisioning, good scalabilityand efficient use of available bandwidth. The proposed solution called light-trains seamlessly integrates optical and wireless networking modules to provide an ideal broadband Internet access solution to users in moving trains. The solution identifies the set of requirements that a solution would require – such as fast hand-off, low-cost of deployment, mature technology and ability to provide dynamic bandwidth provisioning (and hence low experienced delay). IITB/CSE/2009/August/22, TR-CSE-2009-22Model-Based Opportunistic Channel Access in Cognitive Radio Enabled Dynamic Spectrum Access Networks Manuj Sharma, Anirudha Sahoo, K.D. Nayak We propose a model-based channel access mecha-nism for cognitive radio-enabled secondary network, which op-portunistically uses the channel of an unslotted primary networkwhen the channel is sensed idle. We refer to primary networkas the network which carry the main trafﬁc in a designatedspectrum band. We have considered IEEE 802.11 WLAN as a defacto primary network operating in ISM band. Our study focuseson a single WLAN channel that is used by WLAN clients anda WLAN server for a mix of Email, FTP, and HTTP-based webbrowsing applications. We model the occupancy of the channel byprimary WLAN nodes as an alternating renewal process. Whenthe secondary sender node has one or more frames to send, thismodel is used by the the sender and receiver pair to estimateresidual idle time duration after the channel is sensed as idle.The secondary sender then opportunistically transmits frames inthat duration without signiﬁcantly degrading performance of theprimary WLAN applications. Our simulation results show thatthe performance of secondary network is sensitive to the channelsensing duration and that high secondary throughput can beachieved without affecting the primary network signiﬁcantly bychoosing appropriate value of channel sensing duration. IITB/CSE/2008/December/19, TR-CSE-2008-19Energy Harvesting Sensor Nodes: Survey and Implications Sujesha Sudevalayam, Purushottam Kulkarni Sensor networks with battery-powered nodes can seldom simultaneously meet the design goals of lifetime,cost, sensing reliability and sensing and transmission coverage. Energy-harvesting, converting ambient energy toelectrical energy, has emerged as an alternative to power sensor nodes. By exploiting recharge opportunities andtuning performance parameters based on current and expected energy levels, energy harvesting sensor nodes have the potential to address the conflicting design goals of lifetime and performance. This paper surveys various aspects of energy harvesting sensor systems---architecture, energy sources and storage technologies and examples of harvesting based nodes and applications. The study also discusses the implications of recharge opportunities on sensor node operation and design of sensor network solutions. IITB/CSE/2008/October/18, TR-CSE-2008-18Graph Theoretic Concepts for Highly Available Underlay Aware P2P Networks Madhu Kumar S D and Umesh Bellur In our previous work we have demonstrated that underlay awareness is necessary in P2P overlays for the availability of overlay paths and proved that the problem of formation of overlay networks with guaranteed availability is NP complete. Despite this complexity,underlay aware overlay networks, which use knowledge of the underlay to provide guaranteed levels of availability can be efficiently formed and maintained, under aspecified set of constraints. In this technical report, wepresent the graph theoretic concepts developed, leadingto the development of efficient algorithms for availability guaranteed overlay construction and maintenance. IITB/CSE/2008/October/17, TR-CSE-2008-17Towards a Transponder for Serial 100 Gigabit Ethernet using a Novel Optical SERDES Ashwin Gumaste A 100 Gbps serial transponder is proposed using off-the-shelf 10 Gbps optics, a novel combining optical SERDES and mature optical logic. Data-center and metro connectivity is simulated validating the preliminary design. IITB/CSE/2008/August/16, TR-CSE-2008-16TDMA Scheduling in Long-Distance WiFi Networks Debmalya Panigrahi and Bhaskaran Raman In the last few years, long-distance WiFi networks have been used to provide Internet connectivity in rural areas. The strong requirement to support real-time applications in these settings leads us to consider TDMA link scheduling. Such scheduling takes on a different flavour in long-distance mesh networks due to the unique spatial reuse pattern. In this paper, we consider the FRACTEL architecture for long-distance mesh networks. We propose and substantiate a novel angular interference model. This model is not only practical, but also makes the problem of TDMA scheduling tractable. We then make two significant algorithmic contributions. (1) We first present a simple, 3/2 approximate algorithm for TDMA scheduling. (2) We then consider delay-bounded scheduling and present an algorithm which uses at most 1/3rd more time-slots than the optimal number of slots required without the delay bound. Our evaluation on random as well as real network topologies shows that the algorithms are practical, and are more efficient in practice than their worst-case bounds. IITB/CSE/2008/July/15, TR-CSE-2008-15Alternating Renewal Theory-based MAC Protocol for Cognitive Radio Networks Manuj Sharma, Anirudha Sahoo and K.D. Nayak We propose a MAC protocol for cognitive radioenabled secondary networks, which opportunistically use the channels of CSMA/CA-based primary network. We have considered IEEE 802.11 WLAN as a de facto primary network in ISM band. Our study focuses on a single WLAN channel that is used by a WLAN client and server for HTTP-based web browsing application. We use the theory of alternating renewal processes to model the occupancy of channel by WLAN nodes. This model is used by a pair of secondary nodes for estimating idle time durations on the channel and opportunistically transmit frames during the estimated idle times to maximize channel throughput without significantly degrading the WLAN and web application performance. IITB/CSE/2008/July/14, TR-CSE-2008-14Channel Modeling based on Interference Temperature in Underlay Cognitive Wireless Networks Manuj Sharma, Anirudha Sahoo and K.D. Nayak Cognitive radio based dynamic spectrum access network is emerging as a technology to address spectrum scarcity. In this study, we assume that the channel is licensed to some primary (licensed) operator. We consider a sensor network with cognitive radio capability that acts as a secondary (unlicensed) network and uses the channel in underlay mode. The secondary network uses interference temperature model [3] to ensure that the interference to the primary devices remain below a predefined threshold. We use Hidden Markov Model (HMM) to model the interference temperature dynamics of the primary channel. On sensing the event of interest, the sensor nodes transmit observation packets (to some central monitoring station), which constitutes the interference traffic on the primary channel. One of the secondary sensor nodes periodically measures the interference temperature on the channel. If the measured interference temperature is greater than a predefined threshold, then the measuring node records symbol 1; otherwise it records symbol 0. Using a sequence of symbols measured over a period of time, the node constructs and trains an HMM using Baum-Welch procedure. The trained HMM is shown to be statistically stable. The node uses this trained HMM to predict the future sequences and use them in computing the value of Channel Availability Metric for the channel, which is used to select a primary channel. Results of application of such trained HMMs in channel selection in multi-channel wireless network are presented. IITB/CSE/2008/July/13, TR-CSE-2008-13Self Organizing Underlay Aware P2P Networks Madhu Kumar S D, Umesh Bellur and V.K Govindan Computing nodes in modern distributed applications on large scale networks form an overlay network, a logical abstraction of the underlying physical network. Reliability of data delivery is an essential requirement for many of these applications. Traditional methods of ensuring guaranteed data delivery among overlay nodes, are built on the idea of duplication of routing tables at multiple overlay nodes, to handle data delivery even when overlay nodes or links fail. This does not guarantee data delivery as the new routing path to the destination node may also contain the failed node or link in the underlay path. We claim that reliable data delivery in overlay networks can be achieved only through underlay awareness at the overlay level. We propose that reliable data delivery can be achieved by using highly available overlays. An overlay network with reliability guarantees has to be self organizing, due to the large size, distributed nature and cost of redeployment. The major contribution of this paper is a chordal ring based self organizing overlay which is self healing upto two node/link failures. We also present asynchronous distributed algorithms that are executed by the nodes that join and leave the overlay, which ensure that the data delivery guarantees of the overlay are maintained. The algorithms are proved to be correct under distributed and concurrent executions and the time, space and message complexities are O(pathlength), where \'pathlength\' is the average path length between overlay nodes, counting underlay nodes of degree greater than two. The scalability of the algorithm is demonstrated with a simulation study. IITB/CSE/2008/June/12, TR-CSE-2008-12Correctness of Request Executions in Online Updates of Concurrent Programs Yogesh Murarka and Umesh Bellur Online update is a technique which reduces the disruption caused during software update by applying a patch to a running process. It is a challenge to update a process while ensuring that it continues to operate correctly during and after the update. Most of the continuously running processes concurrently execute the requests arriving in a stream. Online update should guarantee a correct outcome of the requests which execute during and after an update. In this report we provide a solution for the same. We first define a request execution criteria to ensure the correct outcome of the requests which execute concurrently with an update. The report then describes an online update approach that fulfills this criteria. The approach avoids deadlocks during update by analyzing interthread dependencies and guarantees that the process remains in a consistent state after the update. Thus, the update procedure is guaranteed to terminate and the requests which execute during and after an update are ensured the correct execution. Our literature survey reveals that this is the first solution to update concurrent programs while requests are executing and ensure correctness. IITB/CSE/2008/April/11, TR-CSE-2008-11Evolution of Carrier Ethernet – Technology Choices and Drivers Ashwin Gumaste, Naresh Reddy, Deepak Kataria and Nasir Ghani The shift from native Ethernet in LANs to switched Ethernet in WANs has propelled efforts of making Ethernet as an ideal candidate technology for transport. Carrier Ethernet has the advantage of being able to be offered as a service to customers. Two questions that we desire to answer in this paper are (1) how Carrier Ethernet can scale as a service in the metropolitan and access premises and (2) what are the key applications that will most benefit from such technology development. We attempt to answer the first question by first reviewing the multiple strategies adapted by vendors in deploying Carrier Ethernet. We then show how scalable Carrier Ethernet can be used for multiple service offerings, especially focusing on video distribution/SAN/mobile-backhaul. We then discuss the service requirements which need to be satisfied to make the native Ethernet carrier class. The paper also discusses impacting underlying technologies which are crucial in making Carrier Ethernet a success. A simulations study throws light on the different strategies of implementing Carrier Ethernet. IITB/CSE/2008/April/10, TR-CSE-2008-10A CAVALIER Architecture for Metro Data Center Networking Akhil Lodha and Ashwin Gumaste Data Center Networking (DCNs) is a fast emerging enterprise application that is driving metropolitan bandwidth needs. This paper evaluates the needs of this emerging IT-centric, bandwidth voluminous and service rendering application from a metro optical networking perspective. We identify a set of needs called CAVALIER (Consolidation, Automation, Virtualization, Adaptability, Latency, Integration, Economy and Reliability) that are underlying requirements for a network to support DCN services. The CAVALIER requirements are met by proposing a metro optical solution which is based on light-trail ROADM technology. Light-trails exhibit properties such as dynamic bandwidth provisioning, optical multicasting, sub-wavelength granular support and low-cost for deployment. Adapting light-trails to DCN needs is discussed in this paper through engineering requirements and network-wide design. Each aspect of the CAVALIER requirement is then mapped on to light-trail technology. Simulation results are shown to lead to performance betterments. Key words: data-center metro networks, light-trails, ROADMs IITB/CSE/2008/January/9, TR-CSE-2008-9Topology Abstraction Algorithms for Light-Mesh - An Alternate Model for PON Anuj Agrawal, Ashwin Gumaste, Mohit Chamania and Nasir Ghani Abstract: Light-mesh – an alternate solution for access networks is presented. Two heuristic topology algorithms are discussed and simulated showing cost and performance benefits. © 2008 Optical Society of AmericaOCIS codes: 060.4250 Networks; 060.4250 Networks IITB/CSE/2007/November/8, TR-CSE-2007-8Complexity Analysis of Availability Models for Underlay Aware Overlay Networks Madhu Kumar S.D, Umesh Bellur Availability of an overlay network is a necessary con- dition for event delivery in event based systems. The availability of the overlay links depends on the under- lying physical network. Overlay networks have to be underlay aware in order to provide assured levels of availability. We propose two models of availability for overlay networks, Manifest and Latent Availability. In the Manifest availability model, distinct paths at the overlay level are also node disjoint at the underlay and hence the alternate paths viewed by the overlay are in- dependent in the underlay also. In the latent avail- ability model, it is only guaranteed that any two over- lay nodes have a guaranteed number of node disjoint paths between them in the underlay. We analyze both the models for complexity of formation and mainte- nance, and prove that in the general case, both are NP-complete. Then we identify a set of practical con- straints applicable to large scale networks. We demon- strate that under these constraints, latent availability constraint becomes a polynomial time problem. We also introduce the concept of reduced underlays, and further reduce the complexity of the problem of determining la- tent availability overlays. IITB/CSE/2007/November/7, TR-CSE-2007-7Tracking Dynamic Boundary Fronts using Range Sensors S. Duttagupta, K. Ramamritham and P. Kulkarni and K. M. Moudgalya We examine the problem of tracking dynamic boundaries occurring in natural phenomena using sensor networks. Remotely placed sensor nodes produce noisy measurements of various points on the boundary using range-sensing. Two main challenges of the boundary tracking problem are energy-efficient boundary estimations from noisy observations and continuous tracking of the boundary. We propose a novel approach which uses discrete estimations of points on the boundary using a regression-based spatial estimation technique and a smoothing interpolation scheme to estimate a confidence band around the entire boundary. In addition, a Kalman Filter-based temporal estimation is used to help selectively refresh the estimated boundary at a point only if the boundary is predicted to move out of the previous estimated intervals at that point. An algorithm for dynamic boundary tracking (DBTR), the combination of temporal estimation with an aperiodically updated spatial estimation, allows us to provide a low overhead solution to track dynamic boundaries that does not require prior knowledge about the nature of the dynamics. Experimental results demonstrate the effectiveness of our algorithm and estimated confidence bands achieve loss of coverage of less than 2% for smooth boundaries. IITB/CSE/2007/October/6, TR-CSE-2007-6A Novel Node Architecture for Light-trail Provisioning in Mesh WDM Metro Networks Ashwin Gumaste, Admela Jukan, Akhil Lodha, Xiaomin Chen and Nasir Ghani We propose an efficient node architecture to support light-trails (intelligent-shared-wavelength bus) in mesh WDM metro networks. Simulation results and performance benefits as compared to legacy technologies are shown. IITB/CSE/2007/October/5, TR-CSE-2007-5Light-trains: An Integrated Optical-Wireless Solution for High Bandwidth Applications in High-Speed Metro-Trains Ashwin Gumaste, Akhil Lodha, Jianping Wang, Nasir Ghani and Si Qing Zheng Moving trains represent a voluminous mass of users moving at high velocities that require bandwidth (on demand). Existing solutions typically based on wireless technology alone cannot scale efficiently to provide for bandwidth to such fast-moving voluminous users. A new approach is proposed that facilitates dynamic provisioning, good scalability and efficient use of available bandwidth. The proposed approach called light-trains seamlessly integrates optical and wireless networking techniques to provide an ideal broadband Internet access solution to users in moving trains. We identify the set of requirements that a solution would require – such as fast hand-off, low-cost of deployment, mature technology and ability to provide dynamic bandwidth provisioning (and hence low experienced delay). The requirements mentioned influence our choices of technologies for different domains in the network: (1) For access to end-users that reside within the train we use an efficient wireless last-inch solution like WiFi in the Point Coordination Function (PCF) mode. (2) For providing access between the wired backbone network and the train we use a modified WiMax system that gives good throughput and efficient channel utilization capacity in a point-to-point configuration. (3) Finally, to be able to provision bandwidth between the core network and the WiMax base-stations we propose the use of light-trail technology at the optical layer. The light-trail technology allows for dynamic provisioning of bandwidth at the optical layer through a unique node architecture and out-of-band control protocol. It turns out that the light-trail control protocol is useful for assisting fast hand-offs. The hand-off time being drastically reduced enables efficient utilization of the wireless channel even at very high speeds. A protocol that enable end-to-end provisioning across the three domains of technology aka light-trails, WiMax and WiFi is also proposed. The proposed protocol is a cornerstone mechanism for providing inter-domain (technology) connectivity in a pragmatic way. Different aspects of the protocol are considered, amongst which delay and efficiency are computed. The protocol and system requirements juxtaposed are simulated extensively. Results pertaining to utilization, delay, efficiency and network wide performance are all showcased. Viability of the model in being able to provide bandwidth to moving users is shown. IITB/CSE/2007/July/3, TR-CSE-2007-31-Persistent Collision-Free MAC Protocols for Opportunistic Optical Hyperchannels Jing Chen, Ashwin Gumaste, Jianping Wang and Si Qing Zheng Recently, a new WDM optical network infrastructure named SMART [1], which is capable of dynamically setting up, modifying, and tearing down optical connections, was proposed. The performance of SMART is determined by the performance of its hyperchannels, which are essentially optical buses or light-trails. Previously proposed MAC protocols for unidirectional optical buses can be used as distributed medium access control protocols for hyperchannels. However, these protocols require optical detection and they are either unfair, or not work-conserving. In this paper, we propose a class of workconserving, collision-free, detection-free, and fair MAC protocols for opportunistic hyperchannels which are tailored hyperchannels for SMART. We compare our proposed MAC protocols with known pi-persistent CSMA protocols and priority-based CSMA protocol by simulations. We show that the performances of our proposed protocols are much better than that of pi-persistent CSMA and that of priority-based CSMA protocol in terms of throughput and fairness. IITB/CSE/2007/July/2, TR-CSE-2007-2Merge-by-Wire: Algorithms and System Support Gurulingesh Raravi, Vipul Shingde, Ashish Gudhe, Krithi Ramamritham Automakers are trying to make vehicles more intelligent and safe by embedding processors which can be used to implement by-wire applications for taking smart decisions on the road or assisting the driver in doing the same. Given this proliferation, there is a need to minimize the computing power required without affecting the performance and safety of the applications. The latter is especially important since these by-wire applications are distributed and real-time in nature and hence deal with critical data and involve deadline bound computations on data gathered from the environment. These applications have stringent requirements on the freshness of data items and completion time of the tasks. Our work studies one such safety-related application namely, Automatic Merge Control (AMC) which ensures safe vehicle maneuver in the region where two or more roads intersect.As our contributions, we (i) propose two merge algorithms for AMC: Head of the Lane (HoL) and All Feasible Sequences (AFS) (ii) demonstrate how DSRC-based wireless communication protocol can be leveraged for the development of AMC (iii) present a real-time approach towards designing AMC by integrating mode-change and real-time repository concepts for reducing the processing power requirements and (iv) identify task characteristics of AMC and provide a scheduling strategy to meet their timing requirements. Simulations demonstrate the advantages of using our approach for constructing merge-by-wire systems. IITB/CSE/2007/July/1, TR-CSE-2007-1DynaSPOT: Dynamic Services Provisioned Optical Transport Test-bed <96> Achieving Multi-Rate Multi-Service Dynamic Provisioning using Strongly connected Light-trail (SLiT) Technology Ashwin Gumaste, Nasir Ghani, Paresh Bafna, Akhil Lodha, Anuj Agrawal, Tamal Das and Si Qing Zheng We report on the DynaSPOT (Dynamic Services Provisioned Optical Transport) test-bed <96> a next-generation metro ring architecture that facilitates provisioning of emerging services such as Triple Play, Video-on-Demand (VoD), Pseudo Wire Edge to Edge Emulation (PWE3), IPTV and Data Center Storage traffic. The test-bed is based on the recently proposed Strongly connected Light-trail (SLiT) technology that enables the triple features of dynamic provisioning, spatial sub-wavelength grooming and optical multicasting <96> that are quintessential for provisioning of the aforementioned emerging services. SLiT technology entails the use of a bidirectional optical wavelength bus that is time-shared by nodes through an out-of-band control channel. To do so, the nodes in a SLiT exhibit architectural properties that facilitate bus function. These properties at the network side include ability to support the dual signal flow of drop and continue as well as passive add, while at the client side include the ability to store data in order to support time-shared access. The latter (client side) improvisation is done through a new type of transponder card <96> called the trailponder that provides for storage (electronic) of data and fast transmission (burst-mode) onto the SLiT. Further in order to efficiently provision services over the SLiT, there is a need for an efficient algorithm that facilitates meeting of service requirements. To meet service requirements we propose a dynamic bandwidth allocation algorithm that allocates data time-slots to nodes based on a valuation method. The valuation method is principally based on an auctioning scheme whereby nodes send their valuations (bids) and a controller node responds to bids by sending a grant message. The auctioning occurs in the control layer, out-of-band and ahead in time. The novelty of the algorithm is the ability to take into consideration the dual service requirements of bandwidth request as well as delay sensitivity. At the hardware level, implementation is complex <96> as our trailponders are layer-2 devices that have limited service differentiation capability. Here, we propose a dual VLAN tag and GFP based unique approach that is used for providing service differentiation at layer-2. Another innovation in our test-bed is the ability to support multi-speed traffic. While some nodes function at 1 Gbps, and others function at 2.5 Gbps (using corresponding receivers), a select few nodes can support both 1 Gbps and 2.5 Gbps operation. This novel multi-speed support coalesced with the formerly mentioned multi-service support is a much needed boost for services in the metro networks. We showcase the test-bed and associated results as well as descriptions of hardware subsystems.