Technical Reports

CSE Tech reports  Upload  Edit  Delete

IITB/KReSIT/2007/May/49, TR-KReSIT-2007-49
Trimarg: A Distributed Algorithm for the Formation of Highly Available Underlay Aware Overlay Networks of Event Brokers
Madhu Kumar S.D and Umesh Bellur

Event broker networks are used to interconnect publishers and subscribers in an event based distributed computing system. Event broker networks are overlay networks formed over the underlying physical network (underlay). In modern distributed applications, high availability in the presence of the runtime failures is an important concern. This paper presents an asynchronous distributed algorithm for constructing and maintaining an underlay aware overlay which ensures 3-degree of availability in the presence of node and link failures in the underlying physical network. We prove theoretically that our algorithm is correct. The time complexity of our algorithm is estimated to be O(diameter * degree)2 of the network and the message complexity is O(diameter * degree). We have investigated the scalability of the algorithm on a simulation testbed. The preliminary scalability test results demonstrate the scalability of our method.

IITB/KReSIT/2007/May/47, TR-KReSIT-2007-47
An Adaptive Algorithm for Establishment of Reliable Routes on Dynamic Overlays in Event Broker Networks
Shruti P. Mahambre, Umesh Bellur, Ramdas Rao

The decoupled and asynchronous nature of the publish-subscribe paradigm, has made it a popular choice for large scale event based systems. Event Broker Networks, which form this paradigm, are used in building these scalable systems, which take the form of overlay nodes, and incorporate several routing schemes when delivering event notifications to clients. Our work in this area revolves around providing quality of service guarantees. We focus on reliability as a QoS parameter, requested by clients when receiving event notifications. In this paper, we first define reliability in a publish-subscribe domain, and propose a multiplicative model for calculating route-reliability over which event notifications are dispatched. We propose the AR(Adaptive-Reliability) algorithm, which refines these routes, based on rewards obtained, and takes decisions for choosing future routes, using the previously calculated values. We also provide a complexity analysis of the AR-Algorithm in terms of the number of messages generated in the system during route establishment, and show through experiments, that the message complexity of our algorithm remains almost constant even with changes in the connectivity of the overlay nodes. We run our simulations using the Hermes middleware simulator, over which we have implemented our own simulator, which measures dynamically changing reliability values of every broker node in the network. Our results reveal that the AR-Algorithm has a much lower message complexity that the Pruning Algorithm (previous work in this area), and is able to adapt to varying reliabilities of broker nodes during route establishment.

IITB/KReSIT/2007/February/43, TR-KReSIT-2007-43
Designing Delay Tolerant Applications for Low Bandwidth and Intermittently Connected Users: the aAQUA Experience
Saurabh Sahni and Krithi Ramamritham

With the explosive growth and spread of Internet, web access from mobile and rural users has become significant. But these users face problems of low bandwidth and intermittent Internet connectivity. To make the benefits of Internet reach the common man in developing countries such as India, accessibility and availability of the information has to be improved. aAQUA is an online multilingual, multimedia Agricultural portal for disseminating information from and to rural communities. Considering resource constrained rural environments, we have designed and implemented an offline solution which provides an online experience to users in disconnected mode. Our solution is based on heterogeneous database synchronization which involves only a small synchronization payload ensuring an efficient use of available bandwidth. Offline aAQUA has been deployed in the field and systematic studies show that with our solution the user experience is improved tremendously not only in disconnected but also in connected mode.

IITB/KReSIT/2007/January/42, TR-KReSIT-2007-42
Adaptive Contour Estimation Using Collaborating Mobile Sensors
Sumana Srinivasan, Krithi Ramamritham and Parmesh Ramanathan

Many real life applications such as tracking of pollutant flows, studying plankton populations in lakes, monitoring ocean currents etc. require real-time detection and tracking of level sets in a dynamic(spatio-temporal) field. In this paper, we examine the problem of estimating a level set or a contour of a particular value within a bounded region of varying field values using a network of mobile sensors. Given the task of estimating a contour, the sensors need to move towards the contour (converge phase) and then trace the contour (coverage phase). In order to minimize the error in estimation, the sensors need to trace all the points on the contour faithfully and to minimize latency, the maximum number of steps taken by the sensors during converge and coverage phases needs to be minimized. In our algorithm called ACE (Adaptive Contour Estimation), we overlap converge and coverage phases to minimize latency. ACE uses the history of movement of sensors to estimate the distance from the contour and strikes a tradeoff between arriving at the contour as quickly as possible and spreading out, compromising on latency initially, but reducing the overall latency by distributing the task of tracing the contour. ACE incorporates a collaborative wall moving algorithm during coverage phase for covering the contour thereby guaranteeing minimization of error in estimation for closed and continuous contours. We demonstrate that, irrespective of the type of initial deployment of sensors, ACE performs well ($>50$\% reduction in latency) when compared to a previous approach. We present results using both simulated and experimentally measured fields obtained by performing actual measurements of light intensity.

IITB/KReSIT/2007/January/41, TR-KReSIT-2007-41
Stochastic Optimization of Light-trail WDM Ring Networks using Benderメs Decomposition
Akhil Lodha, Ashwin Gumaste, Paresh Bafna and Nasir Ghani

Linear optimization has been exhaustively used for resource conservation and network design/planning. The primary assumption facilitating the use of linear optimization is that traffic is assumed to be deterministic, which in reality is not the case. In the domain of optical networks, the Routing and Wavelength Assignment (RWA) problem for provisioning lightpaths or optical circuits is well known and is solved using constrained linear optimization. However, with emerging service requirements such as Triple Play, Video-on-Demand (VoD) and Pseudo-Wire Edge-to-Edge Emulation (PWE3), the optimization involves stochastic parameters for dynamic service provisioning. Alternate solutions to lightpath communication, that solve the paradox between maximizing dynamism as well as maintaining high-efficiency are proposed. In the electronic domain, solutions such as Resilient Packet Rings (RPR) and Next Generation Packet Over SONET (NG-POS) have been considered. Conversely, in the all-optical domain light-trails, has been proposed as a solution to meet requirements of these emerging services. Optimal allocation of resources and subsequent network design is not possible using traditional linear programming approaches due to the time-variant nature of traffic and architectural properties of these optical and electronic solutions. Stochastic optimization ヨ a technique that assumes probabilistic nature of traffic is a promising approach for planning and allocation of resources in a network. This paper discusses application of stochastic optimization to high-speed all-optical networks, in particular, to the emerging concept of light-trail networks. Light-trails are a generalized lightpath that enable dynamic sharing of a wavelength leading to efficient network utilization. A stochastic formulation for design of light-trail networks in metropolitan rings is presented. A simpler (tractable) formulation is also developed using a quantization hypothesis that restricts the solution space. The formulation is then abstracted to the well known Benderメs decomposition method for solving stochastic optimization problems. The formulation is evaluated under varying traffic conditions. Results are obtained and compared with linear optimization. Cost savings in terms of network equipment (transponders) is presented.

IITB/KReSIT/2007/January/40, TR-KReSIT-2007-40
Merge Algorithms for Intelligent Vehicles
Gurulingesh Raravi, Vipul Shingde, Krithi Ramamritham, Jatin Bharadia

There is an increased concern towards the design and development of computer controlled automotive applications to improve safety, reduce accidents, increase traffic flow, and enhance comfort for drivers. Automakers are trying to make vehicles more intelligent by embedding processors which can be used to implement Electronic and Control Software (ECS) for taking smart decisions on the road or assisting the driver in doing the same. These ECS applications are
high-integrity, distributed and real-time in nature. Inter-Vehicle Communication and Road-Vehicle Communication (IVC/RVC) mechanisms will only add to this intelligence by enabling distributed implementation of these applications. Our work studies one such application, namely Automatic Merge Control System, which ensures safe vehicle maneuver in the region where two roads intersect. We have discussed two approaches for designing this system both aimed at minimizing the Driving-Time-To-Intersection (DTTI) of vehicles, subject to certain constraints for ensuring safety. We have (i) formulated this system as an optimization problem which can be solved using standard solvers and (ii) proposed an intuitive approach namely, Head of Lane (HoL) algorithm which incurs less computational overhead compared to optimization formulation. Simulations carried out usingMatlab and C++ demonstrate that the proposed approaches ensure safe vehicle maneuvering at intersection regions. In this on-going work, we are implementing the system on robotic vehicular platforms built in our lab.

IITB/KReSIT/2006/December/38, TR-KReSIT-2006-38
Electrigence: Electrical distribution networks with added Intelligence for Home/Office Automation and Control
Ashwin Gumaste

Homes and offices with smart devices/appliances are soon becoming a reality leading to comfort and automation. The heterogeneity of devices is a critical hurdle in the developing of a system that enables integration and centralized control. Significant literature is available in the area of automation and control of high-end devices and appliances. The nature of the work being proprietary and specific to the application of high-end devices has prevented integration and automation of lower-end devices on a single unified platform – that serves as a common point for control and acquisition of data. We propose “Electrigence” or Electrical-Intelligence a concept that utilizes local (office and home) power distribution grids as a basis for home/office automation. The concept of Electrigence has two prominent features. Firstly, it provides for a unified software platform and vastly simplified hardware that enables the control of devices in home and office environments. Secondly, Electrigence provides a communicative environment that enables the control as well as processing of information in devices both at a local (intra-office, intra-home) and a global (Internet) level. The concept enables local electrical distribution networks to emulate an operating system behavior, and further allow the coalescing of heterogeneous devices over the electrical distribution network. We examine the concept of Electrigence in this paper. A simulation study examining scalability, protocol features as well as service provisioning over the framework is also presented.

IITB/KReSIT/2006/November/37, TR-KReSIT-2006-37
Reliable Routing of Event Notifications over P2P Overlay Routing Substrate in Event Based Middleware
Shruti P. Mahambre and Umesh Bellur

Event broker networks(EBN) are a scalable incarnation of the publish subscribe paradigm for building asynchronous systems. These take the form of overlays of broker nodes and several routing schemes exist that deliver events from publishers to subscribers efficiently on different overlay structures. However qualities of service based routing schemes are rare and our work addresses this gap. Specifically we look into the prospect of routing events based on reliability requirements of subscribers for an event type being delivered via the EBN. In this paper, we propose a multiplicative model to measure reliability of the P2P overlay routing substrate and an algorithm based on this model, to deliver event notifications to the client. We employ a technique called 'pruning' by which we restrict flooding the entire overlay routing substrate, when finding a reliable path. The complexity analysis of our algorithm shows that it finds a reliable path with a lower message
complexity, as compared to the flooding approach. Our algorithm also determines a path with higher reliability than the path established by Hermes. We present initial simulation results, using the Hermes middleware simulator.

IITB/KReSIT/2006/November/36, TR-KReSIT-2006-36
A taxonomy and classification of adaptive event based middleware with support for service guarantees
Shruti P. Mahambre, Madhu Kumar S.D., Umesh Bellur

Event Broker Networks are scalable versions of the publish subscribe paradigm that take the form of P2P overlays of broker nodes. Several routing schemes help disseminate events efficiently from publishers to subscribers on different overlay topologies. While there exist various frameworks that demonstrate several overlay topologies and routing schemes, attention has now turned to exploring non-functional attributes of such systems. In this effort, we first present a detailed taxonomy and a comprehensive survey of existing event based middleware efforts, centered around qualities of service and adaptation. In the process of putting together this survey we have also identified open research problems in the area.

IITB/KReSIT/2006/November/35, TR-KReSIT-2006-35
Channel Selection under Interference Temperature Model in Multi-hop Cognitive Mesh Networks
Manuj Sharma, Anirudha Sahoo, K.D. Nayak

A cognitive radio-based wireless mesh network is
considered. In addition to forwarding the data packets, each mesh node also senses the channels of a target primary system to identify the spectrum opportunities, and uses them for its own data transmission. Interference temperature model is used to define the occupancy and availability of a channel. A cooperative algorithm based on interference temperature model is proposed for computation of available channels by mesh nodes. Cases for mesh nodes with fixed transmission power and adaptive transmission power are considered separately. Finally, link and end-to-end routing metrics are proposed to select appropriate
channels from the computed set of available channels.

IITB/KReSIT/2006/November/34, TR-KReSIT-2006-34
Graphical Models for Multi-labeled Text Classification
Manoj Kumar Chinnakotla, Sunita Sarawagi

Multi-labeled text classification refers to the task of classifying documents where each document may belong to more than one single class. SVMs are known to be the best discriminative classifiers for text. One way of extending them to handle multi-labeled classification is to construct an ensemble of binary one-vs-rest classifiers for each class. The ensemble will output, for each document, a score for each class that indicates the proximity of the document from the hyperplane that separates the given class from the rest. The final set of labels for the document is chosen after thresholding the scores using some constant. However, in real life situations, class labels are often correlated and the above approach does not model them. In this project, we explore the idea of using probabilistic graphical models, on top of basic one-vs-rest SVM outputs, to model the correlation between the class labels for improving the accuracy of classification.

IITB/KReSIT/2006/October/33, TR-KReSIT-2006-33
Towards Intelligent Vehicles: Automatic Merge Control
Gurulingesh Raravi, Jatin Bharadia and Krithi Ramamritham

There is an increased concern towards the design anddevelopment of computer-controlled automotive applicationsto improve safety, reduce accidents, increase trafficflow, and enhance comfort for drivers. Automakers are tryingto make vehicles more intelligent by embedding processorswhich can be used to implement Electronic and ControlSoftware (ECS) for taking smart decisions on the road or assistingthe driver in doing the same. These ECS applicationsare high-integrity, distributed and real-time in nature. Inter-Vehicle Communication and Road-Vehicle Communicationwill only add to this intelligence by providing platform fordistributed control implementation. Our work studies onesuch application, namely Automatic Merge Control System,which ensures safe vehicle maneuver in the region wheretwo roads intersect. We have formulated this problem asan optimization problem aimed at minimizing the DTTI ofvehicles, subject to certain constraints to ensure safety. Inon-going work, we are implementing the system on roboticvehicular platforms built in our lab.

IITB/KReSIT/2006/October/32, TR-KReSIT-2006-32
DS2R2: Delay Sensitive Smoothed Round Robin Scheduler for Connection Scheduling in SLiT (Strongly connected Light-trail) Networks
Paresh Bafna and Ashwin Gumaste

We propose Delay Sensitive Smoothed Round Robin scheduling algorithm for provisioning services over light-trail and SLiT networks. Compliance to latencies of services such as PWE3, VoD, Voice and data and good efficiency are observed.

IITB/KReSIT/2006/October/31, TR-KReSIT-2006-31
An Energy Efficient MAC in Wireless Sensor Networks to Provide Delay Guarantee
Anirudha Sahoo and Prashant Baronia

This paper presents RTMAC, a realtime MAC
protocol for wireless sensor network that can provide delay
guarantee. RTMAC is based on TDMA protocol, but it is carefully
designed to overcome the high latency of traditional TDMA
protocols. It also conserves energy when a node may not be
transmitting or receiving packets. We discuss the details of time
slot assignment procedure of RTMAC and then present delay
analysis of the protocol. We compare the performance of RTMAC
with the well known energy efficient MAC protocol S-MAC using
simulation. The simulation results show that RTMAC is better
than S-MAC in terms of providing delay guarantee to packets.

IITB/KReSIT/2006/October/30, TR-KReSIT-2006-30
An Efficient Call Admission Control for IEEE 802.16 Networks
Sarat Chandra and Anirudha Sahoo

IEEE 802.16 is a standard recommended by
IEEE as a Wireless Metropolitan Area Network (WMAN)
technology to provide connectivity to the last mile of a network.
Not only does it provide high bandwidth but also it has a
long transmission range (upto 30 miles). In addition, 802.16
MAC and physical layer are carefully designed to support
different types of real time application by providing Quality of
Service (QoS). But without proper scheduling and connection
admission control (CAC), the system cannot provide promised
QoS to the real time applications. Hence, scheduling and CAC
play a vital role in 802.16 network. But the standard does not
specify any scheduling or CAC. Although there are few 802.16
based QoS scheduling architectures proposed in the literature,
most of them assume a conventional bandwidth based CAC
(BW-CAC). But BW-CAC does not take QoS requirements
(e.g., deadline) of connections into account. Hence, they would
not be appropriate for real time application. In this paper,
we propose an efficient QoS CAC that ensures that QoS
guarantee of the connections are met. Using simulation, we
present performance of our CAC in different scenarios and
show that our CAC performs better than BW-CAC.

IITB/KReSIT/2006/August/28, TR-KReSIT-2006-28
QoS in Event Based Middleware
Shruti P. Mahambre and Umesh Bellur

Event Broker Networks are a scalable incarnation of the publish subscribe paradigm for building asynchronous systems. These take the form of overlays of broker nodes and several routing schemes exist that deliver events from publishers to subscribers efficiently on different overlay structures. The decoupled and asynchronous nature of event based architectures has made it a popular choice for large scale software systems today. While a number of principles on which such architectures ride, have been well established, attention has now turned to exploring non-functional attributes of such systems. In this
effort, we first present a taxonomy of event based middleware and an accompanying survey of existing event based middleware efforts centered around the provision for qualities of service guarantees. In the process of putting together this survey we have also identified open research problems in the area. Specifically we look at the prospect of routing events based on reliability requirements of subscribers based on the event type, via the broker network. We propose a reliability model, which measures reliability of the overlay network, and an algorithm based on this model, to deliver event notifications to the client. We employ a technique called 'pruning', by which we restrict flooding the entire overlay network, when finding a reliable path. The complexity analysis of our algorithm shows that it finds a reliable path with a lower message complexity, as compared to the flooding approach. We also verify our claims, with simulation results, using the Hermes middleware simulator.

IITB/KReSIT/2006/August/27, TR-KReSIT-2006-27
Service Aware Control Mechanisms for Light-trail WDM Networks
Ashwin Gumaste, Janak Chandarana, Nasir Ghani and Vishal Sharma

Abstract: A light-trail is a generalized lightpath that enables multiple nodes to statistically share an optical communication path (wavelength bus). A light-trail is different from a lightpath on account of its unique node architecture ヨ that enables formation of wavelength buses by supporting characteristics of optical drop-and-continue and optical passive-add. Apart from the node architecture, another differentiation between light-trails and lightpaths is the out-of-band control channel. The combined effect of a unique node architecture and out-of-band control channel enables light-trails to provide sub-wavelength grooming capability, dynamic provisioning and optical multicasting. These features offered by light-trails are critical for next generation emerging applications such as Video-on-demand (VoD), Triple-play and Pseudo-Wire Edge-to-Edge Emulation (PWE3). The control channel requires engineering enhancement to provision dynamic and bandwidth efficient services over light-trails. We investigate into the control channel hierarchies of light-trail networks to provision these emerging services. Centralized, distributed, static, dynamic, and cooperative control mechanisms are discussed. Performance of light-trail control for providing next generation services such as pseudo-wires, VoD and triple play are considered through simulation.

IITB/KReSIT/2006/August/26, TR-KReSIT-2006-26
Light-frames ヨ Pragmatic Framework for Optical Packet Transport: Extending Ethernet LANs to Optical Networks
Ashwin Gumaste and Si Qing Zheng

In this article, we propose a network architecture for the realization of a pragmatic framework for optical packet transport called the light-frame framework. The architecture enables the transport of packets over optical media. While doing so, it relaxes the need for address recognition as well as high-speed switching, the two key hindering factors that have prevented contemporary optical packet transport solutions from being deployed. Using this framework, we achieve a trade-off between cost (maturity in deployment) and performance (network efficiency). The idea is to create a logical topology that enables N2 connectivity, yielding sub-lambda granularity, thereby facilitating packet transport. We propose methods for topology discovery and conflict resolution. The article also discusses stochastic as well as optimization analysis of the framework. We compare the fiber resource requirements of this network-solution to a leading access networking solution ヨ Passive Optical Networks (PON) and show cost benefit. The light-frames concept due to its finely granular application, despite present technological bottleneck, presents a good implementation case that allows it to be pushed for next generation optical packet transport especially in the access area.

IITB/KReSIT/2006/August/24, TR-KReSIT-2006-24
Application Partitioning - A Dynamic, Runtime, Object-level Approach
Anshu Veda and Sridhar Iyer

With the advent of increase in the computational complexity of the programs, it seems conducive to distribute a centralized program written for a standalone system onto a
network of nodes. Application partitioning is one such technique, that aims at division (alocation) of application components amongst di erent hosts in the network, thereby
getting a standalone application executed in a distributed setting.

Most of the existing work in application partitioning, uses classes as the basic component for partitioning. However, the behavior of an application is determined by the
interaction of its entities at run-time. In an object-oriented program, the run-time entities are principaly objects. We believe that, a more e ective and relevant partitioning mechanism can be created by considering objects as the basic components for distribution.

We also believe that, a truly flexible partitioning system should as far as possible, postpone the decision regarding the placement of each component to run-time. Any
such decision should try to optimize on both - the number of remote invocations that a distribution strategy would result in, as well as the load distribution on the available

We thus propose a working architecture that exploits the dependency relationships between the components, to build a model prior to the program execution. At run-time,
the model progressively incorporates the information about already alocated components and helps in deciding the position of new component.

IITB/KReSIT/2006/August/23, TR-KReSIT-2006-23
Adaptive Overlays for Event Based Middleware: A case for Chordal Reliability Rings
Madhu Kumar S.D, Umesh Bellur, V.K Govindan

Distributed, event based applications executing on publish-subscribe middleware (aka Event Based Middleware or EBM) are subject to many disruptive changes at runtime. These changes can be caused either by a change in environmental conditions such as the failure of an event broker node or can be caused by dynamically evolving application needs such as the sudden need to route events securely from a specific publisher to a set of subscribers. Ideally, the middleware should facilitate uninterrupted execution of applications without costly redeployment in the face of these changes. We formally study the requirements of such an モadaptiveヤ middleware infrastructure and analyze adaptation in existing efforts. An adaptive overlay for a core level adaptive middleware with a chordal reliability ring is proposed on the basis of the study. We illustrate and prove that two of the adaptation triggers - node and link failures can be handled by the middleware in O (log n) time with the help of the chordal reliability ring.

IITB/KReSIT/2006/July/21, TR-KReSIT-2006-21
Interference-Constrained Wireless Coverage in a Protocol Model
Prateek R Kapadia and Om P. Damani

We present an efficient algorithm to compute the coverage map of a given set of transmitters under interference constraints. That is, we compute the set of points that lie within the transmission range of one transmitter and lie outside the interference range of every other transmitter. To our knowledge, there is no existing satisfactory algorithm for this purpose. We assume that the transmission and interference ranges of each transmitter are circular disks centered at the transmitter location. We show that for an appropriate choice of `distance' measure, coverage at each point can be computed by considering only certain `proximate' transmitters. Hence, we partition the plane into proximity regions and the coverage in these proximity regions is computed considering only proximate transmitters. Our algorithm takes O(n log n) time. We use Voronoi diagrams and power diagrams for representing these proximity regions.

IITB/KReSIT/2006/July/19, TR-KReSIT-2006-19
A contention window differentiation mechanism for providing QoS to high priority data in 802.11
M .Mishra and A. Sahoo

IEEE 802.1 based wireles LANs (WLAN) are rapidly replacing traditional wireline ethernet LANs. Running real time voice and video applications over LANs is becoming common place. These applications require QoS in terms of delay, throughput etc. But 802.1 does not have inherent QoS support. Since 802.1 has a large instalation base and QoS-aware IEEE 802.1e standard based products are not available yet, providing QoS in 802.11 WLANs is an important issue. In this paper,we propose a MAC protocol based on 802.1 which can provide QoS to real time applications. The MAC asigns different contention window to two priority clases to provide service differentiation. When colision occurs, contention window is increased in a linear fashion and the new contention windows for high and low priority traffic become non-contiguous. This unique method of contention window management provides beter relative performance betwen the two clases and achieves higher system throughput. We propose two modes of realizing this new MAC protocol, present an analytical model to show that high priority class gets better service and report our simulation experiment results that show that our protocol produces performance comparable to 802.11e.

IITB/KReSIT/2006/July/18, TR-KReSIT-2006-18
Improving RFID System to Read Tags Efficiently
Anirudha Sahoo, Sridhar Iyer and Naval Bhandari

Radio Frequency Identification (RFID) is slated to become a standard for tagging various
products. As more and more products become RFID enabled, fast tag identification
mechanisms will become important. Various tag identification (or anti-collision) algorithms
have been proposed for RFID systems. This work focuses on methods to improve
tag read efficiency in RFID Systems. In this report, we propose an Intelligent Query
Tree (IQT) Protocol for tag identification that exploits specific prefix patterns in the tags
and make the identification process more efficient. IQT is a memoryless protocol that
identifies RFID tags more efficiently in scenarios where tag IDs have some common prefix
(e.g., common vendor ID or product ID). IQT is suitable for readers deployed in exclusive
showrooms, shipment points of big malls, where the products may come from same
manufacturer and may have same product IDs. We provide the worst case complexity
analysis of IQT and show the performance improvement of this protocol over traditional
Query Tree protocol in different scenarios. For other cases we show the improvement
using simulation results.

IITB/KReSIT/2006/April/10, TR-KReSIT-2006-10
Efficient Real-Time Support for Automotive Applications: A Case Study
Gurulingesh Gouda, Neera Sharma, Krithi Ramamritham and Sachitanand Malewar

The number of computer-controlled functions in an automobile is increasing at a rapid rate and so is the number of microprocessors implementing and controlling these functionalities. Therefore, there is a need to minimize the computing power provided without affecting the performance and safety of the applications. The latter is especially important since intelligent automotive applications deal with critical data and involve deadline bound computations on data gathered from the automobiles environment. These applications have stringent requirements on the freshness of data items and completion time of the tasks. Our work studies one such safety-critical application, namely Adaptive Cruise Control (ACC). We take a task+data centric approach for designing and implementing this application.As our contributions we have (i) identified the data and task characteristics of ACC and shown how to map them on a real-world (robotic) platform, (ii) facilitated a realtime approach towards designing ACC by the application of mode-change and real-time data repository concepts for reducing CPU capacity requirements and (iii) provided the scheduling strategies to meet the timing requirements of the tasks. Experiments demonstrate that the CPU capacity requirement can be reduced without compromising the real-time guarantees for safety-critical applications.

IITB/KReSIT/2006/April/8, TR-KReSIT-2006-8
Cross Layer based Congestion Control in Wireless Networks
Hemant Kumar Rath and Anirudha Sahoo

In this paper, we discuss a cross layer congestion control technique of TCP Reno-2 in wireless networks. In this both TCP layer and PHY layer jointly control congestion. The PHY layer changes transmission power as per the channel condition, interference received and congestion in the network, whereas the TCP layer controls congestion using Reno-2 window based flow control. Our simulations show that the cross layer congestion control technique provides performance improvement in terms of throughput and window size variations.

IITB/KReSIT/2006/April/7, TR-KReSIT-2006-7
A Local Coefficient Based Load Sensitive Routing Protocol for Providing QoS
Anunay Tiwari and Anirudha Sahoo

It is well known that in an Open Shortest Path First (OSPF) based best effort network, the OSPF shortest path can become the bottleneck when congestion occurs. There may be some less congested alternate paths available,but OSPF does not forward packets through those paths. Hence, OSPF cannot be used to provide Quality ofService. Earlier, we reported a Load Sensitive Routing (LSR) algorithm which finds alternate path based on OSPFproperty. The performance of LSR depends on the operating parameter (or coefficient) used in the algorithm. In theearlier work, the LSR used global coefficients i.e. all the nodes in the network use the same coefficient for a givendestination. The global coefficient is decided based on some optimization criteria. But assigning network-wide global coefficient may lead to uneven distribution of alternate paths. That is, some nodes may have many alternate paths whereas others may have few or none. The use of global coefficient was thought to be necessary to make the protocol loop free. In this study, we allow nodes to choose LSR coefficients locally (we call the coefficient L-LSR coefficient) while still retaining the loop-free property. This leads to nodes having more number of alternate paths than the case where they had to use global coefficient. But allowing local coefficients makes the process of calculating the local coefficients complex. Since our protocol has to be loop free, the local coefficients have to be calculated such that the loop free OSPF property is still satisfied. Thus, it will lead to a set of constraints which need to be resolved to assign correct L-LSR coefficients to the nodes. This paper presents detailed algorithm for calculating L-LSR coefficients. Using simulation, we show that L-LSR algorithm not only performs better than OSPF, but also has very significant performance improvement over the other LSR family of algorithms. Hence, L-LSR protocol can be very effective in providing QoS support at the routing layer.

IITB/KReSIT/2006/April/5, TR-KReSIT-2006-5
A Novel K-out-of-N Auction Mechanism and Strategic Scaling for Dynamic Bandwidth Allocation in GE-PON
Kumar N, Ashish Gudhe, Ashwin Gumaste and Nasir Ghani

Dynamic bandwidth allocation for upstream transmission in EPONs has gathered significant attention. Maximizing utilization is inversely related to dynamic bandwidth allocation. We propose an auctioning mechanism for bandwidth allocation with a view to dissolution of the paradox between efficiency (utilization) and dynamism. While conventional bandwidth auctioning schemes pose efficiency as well as fairness issues, our extensions overcome these. We propose three extensions: to increase efficiency we propose a K-out-of-N auctioning mechanism; to promote dynamism and reduce bandwidth starvation, we enhance the auctioning mechanism by introducing strategic scaling; and to cater to services we propose a bid computation mechanism that is uniquely tailored to reflect different service requirements. Through a simulation model we evaluate the performance of our scheme for latency, dynamism, efficiency and blocking.

IITB/KReSIT/2006/April/4, TR-KReSIT-2006-4
A New Model for Adaptive Event Based Middleware
Madhu Kumar S.D, Umesh Bellur

A new Event Model for Adaptive Event Based Middleware is proposed

IITB/KReSIT/2006/April/3, TR-KReSIT-2006-3
Collaborative Contour Estimation Using Mobile Sensors
Sumana Srinivasa, Krithi Ramamritham and Parmesh Ramanathan

Controlled movement of sensors within a given region is known to improve the overall quality of measurements by reducing sensing uncertainty. A mobile wireless sensor network may be deployed to detect and track a large-scale physical phenomenon in a geographical region such as an oil spill in the ocean. It may be called upon to provide a description of a contour characterized by an isoline of a specific concentration value. In this paper, we examine the problem of tracing a contour of a particular concentration within a bounded geographical region of varying pollutant concentration using a network of mobile sensors. We explore various ways of guiding a set of mobile sensors optimally so as to surround and trace the contour. We formulate the contour estimation problem as a nonlinear multi-extremal optimization problem and use gradient free finite difference based technique to estimate the target contour in the given region. We use accuracy and latency as performance metrics and show that in the majority of the cases our proposed strategy based on collaboration of sensors delivers the best performance.

IITB/KReSIT/2006/April/2, TR-KReSIT-2006-2
Vehacol: Vehicular Anti-Collision Mechanism using a Combination of Periodic Information Exchange and Power Measurements
Ashwin Gumaste and Anirudha Sahoo

Vehacol or Vehicular Anti-Collision is a mechanism for determining collision course between two or more vehicles. The mechanism uses a combination of physical and logical layer techniques to generate self and remote node information that can be exchanged to enable location awareness. Two vehicles (nodes) periodically exchange information about their individual movement in terms of displacement, speed and direction (with reference to a geographic North). In addition to the information exchange through an ad hoc network, vehicles also measure the separating distance through physical measurement. To do so, the vehicles use a unique but simple modulation format and reception technique that avoids the problems caused by multipath fading. Combining the inputs obtained through the measurement of distance and periodic information exchanges, vehicles are able to determine whether or not they are on a collision course with another vehicle. The paper discusses system parameters, protocol and other design issues related to the implementation of the Vehacol system. Simulation results and assumptions are also presented that validate the mechanism from the perspectives of error computation and discovery times.

IITB/KReSIT/2006/April/1, TR-KReSIT-2006-1
Distributed Boundary Estimation using Sensor Networks
Subhasri Duttagupta and Krithi Ramamritham

We examine the problem of determining boundaries occurring in natural phenomena using sensor networks. Sensor nodes remotely collect data about various points on the boundary. From this data, we estimate the boundary along with the confidence intervals using a regression relationship among sensor locations and the distances to the boundary. The confidence intervals are not wider than a specified maximum value.Our distributed boundary estimation strategy uses a hierarchical structure of clusters of sensor nodes and requires an order of magnitude less messages as compared to a centralized scheme. The computed intervals show desired coverage of the true boundary points.
Further, motivated by the practical need to estimate the boundary with a minimum number of sensors, we develop an approach for turning on sensors and turning off.The number of ON sensors in this scheme is only 5-15% more than what a Practical Oracle needs to evaluate the boundary and confidence intervals around it. Our regression-based approach has combined approximate query processing, optimal availability of sensors to meet the accuracy requirement and utilizing spatial correlation among sensors in solving the non-trivial problem of boundary estimation.


Faculty CSE IT
Forgot Password
    [+] Sitemap     Feedback