KReSIT Logo Kanwal Rekhi School of Information Technology
IITB Logo
IIT Bombay
 
 Research
 Groups
 Publications
 Tech Reports
 Upload Report(LDAP login)
 Delete Report(LDAP login)
 Projects
 Seminars
 Labs
 Techtalks
 


Notice: Uninitialized string offset: 0 in /home/activities/webteam/web/research/techreport/index.php on line 18

Notice: Uninitialized string offset: 0 in /home/activities/webteam/web/research/techreport/index.php on line 18

Notice: Uninitialized string offset: 0 in /home/activities/webteam/web/research/techreport/index.php on line 18

Notice: Uninitialized string offset: 0 in /home/activities/webteam/web/research/techreport/index.php on line 18

Notice: Uninitialized string offset: 0 in /home/activities/webteam/web/research/techreport/index.php on line 18

Notice: Uninitialized string offset: 0 in /home/activities/webteam/web/research/techreport/index.php on line 18

Notice: Uninitialized string offset: 0 in /home/activities/webteam/web/research/techreport/index.php on line 18

Notice: Uninitialized string offset: 0 in /home/activities/webteam/web/research/techreport/index.php on line 18

Notice: Uninitialized string offset: 0 in /home/activities/webteam/web/research/techreport/index.php on line 18


Home > Research > Techreport 

Technical Report



  • Technical reports are documents created by KReSIT faculty and students to report their technical findings.
  • Anyone with an LDAP login can submit a technical report.
  • Once submitted, the report will be activated, uploaded and cannot be modified.
  • User has ability to delete the report though the user would lose the timestamp associated with the same.
  • Technical reports should be original documents, authored solely by the user(s).


Distributed Boundary Estimation using Sensor Networks        Subhasri Duttagupta and Krithi Ramamritham         IITB/KReSIT/2006/April/1
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.
 
Vehacol: Vehicular Anti-Collision Mechanism using a Combination of Periodic Information Exchange and Power Measurements       Ashwin Gumaste and Anirudha Sahoo         IITB/KReSIT/2006/April/2
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.
 
Collaborative Contour Estimation Using Mobile Sensors       Sumana Srinivasa, Krithi Ramamritham and Parmesh Ramanathan         IITB/KReSIT/2006/April/3
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.
 
A New Model for Adaptive Event Based Middleware       Madhu Kumar S.D, Umesh Bellur         IITB/KReSIT/2006/April/4
A new Event Model for Adaptive Event Based Middleware is proposed
 
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         IITB/KReSIT/2006/April/5
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.
 
A Local Coefficient Based Load Sensitive Routing Protocol for Providing QoS       Anunay Tiwari and Anirudha Sahoo         IITB/KReSIT/2006/April/7
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.
 
Cross Layer based Congestion Control in Wireless Networks       Hemant Kumar Rath and Anirudha Sahoo         IITB/KReSIT/2006/April/8
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.
 
Efficient Real-Time Support for Automotive Applications: A Case Study       Gurulingesh Gouda, Neera Sharma, Krithi Ramamritham and Sachitanand Malewar         IITB/KReSIT/2006/April/10
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.
 
Improving RFID System to Read Tags Efficiently       Anirudha Sahoo, Sridhar Iyer and Naval Bhandari         IITB/KReSIT/2006/July/18
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.
 
A contention window differentiation mechanism for providing QoS to high priority data in 802.11       M .Mishra and A. Sahoo         IITB/KReSIT/2006/July/19
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.
 
Interference-Constrained Wireless Coverage in a Protocol Model       Prateek R Kapadia and Om P. Damani         IITB/KReSIT/2006/July/21
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.
 
Adaptive Overlays for Event Based Middleware: A case for Chordal Reliability Rings       Madhu Kumar S.D, Umesh Bellur, V.K Govindan         IITB/KReSIT/2006/August/23
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.
 
Application Partitioning - A Dynamic, Runtime, Object-level Approach       Anshu Veda and Sridhar Iyer         IITB/KReSIT/2006/August/24
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
hosts.

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.
 
Light-frames – Pragmatic Framework for Optical Packet Transport: Extending Ethernet LANs to Optical Networks        Ashwin Gumaste and Si Qing Zheng         IITB/KReSIT/2006/August/26
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.
 
Service Aware Control Mechanisms for Light-trail WDM Networks        Ashwin Gumaste, Janak Chandarana, Nasir Ghani and Vishal Sharma         IITB/KReSIT/2006/August/27
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.
 
QoS in Event Based Middleware       Shruti P. Mahambre and Umesh Bellur         IITB/KReSIT/2006/August/28
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.
 
An Efficient Call Admission Control for IEEE 802.16 Networks       Sarat Chandra and Anirudha Sahoo         IITB/KReSIT/2006/October/30
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.
 
An Energy Efficient MAC in Wireless Sensor Networks to Provide Delay Guarantee       Anirudha Sahoo and Prashant Baronia         IITB/KReSIT/2006/October/31
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.
 
DS2R2: Delay Sensitive Smoothed Round Robin Scheduler for Connection Scheduling in SLiT (Strongly connected Light-trail) Networks       Paresh Bafna and Ashwin Gumaste         IITB/KReSIT/2006/October/32
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.
 
Towards Intelligent Vehicles: Automatic Merge Control       Gurulingesh Raravi, Jatin Bharadia and Krithi Ramamritham         IITB/KReSIT/2006/October/33
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.
 
Graphical Models for Multi-labeled Text Classification       Manoj Kumar Chinnakotla, Sunita Sarawagi         IITB/KReSIT/2006/November/34
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.
 
Channel Selection under Interference Temperature Model in Multi-hop Cognitive Mesh Networks       Manuj Sharma, Anirudha Sahoo, K.D. Nayak         IITB/KReSIT/2006/November/35
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.
 
A taxonomy and classification of adaptive event based middleware with support for service guarantees       Shruti P. Mahambre, Madhu Kumar S.D., Umesh Bellur         IITB/KReSIT/2006/November/36
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.
 
Reliable Routing of Event Notifications over P2P Overlay Routing Substrate in Event Based Middleware       Shruti P. Mahambre and Umesh Bellur         IITB/KReSIT/2006/November/37
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.
 
Electrigence: Electrical distribution networks with added Intelligence for Home/Office Automation and Control       Ashwin Gumaste         IITB/KReSIT/2006/December/38
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.
 
Merge Algorithms for Intelligent Vehicles       Gurulingesh Raravi, Vipul Shingde, Krithi Ramamritham, Jatin Bharadia         IITB/KReSIT/2007/January/40
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.
 
Stochastic Optimization of Light-trail WDM Ring Networks using Bender’s Decomposition       Akhil Lodha, Ashwin Gumaste, Paresh Bafna and Nasir Ghani         IITB/KReSIT/2007/January/41
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.
 
Adaptive Contour Estimation Using Collaborating Mobile Sensors       Sumana Srinivasan, Krithi Ramamritham and Parmesh Ramanathan         IITB/KReSIT/2007/January/42
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.
 
Designing Delay Tolerant Applications for Low Bandwidth and Intermittently Connected Users: the aAQUA Experience       Saurabh Sahni and Krithi Ramamritham         IITB/KReSIT/2007/February/43
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.
 
An Adaptive Algorithm for Establishment of Reliable Routes on Dynamic Overlays in Event Broker Networks       Shruti P. Mahambre, Umesh Bellur, Ramdas Rao         IITB/KReSIT/2007/May/47
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.
 
Trimarg: A Distributed Algorithm for the Formation of Highly Available Underlay Aware Overlay Networks of Event Brokers       Madhu Kumar S.D and Umesh Bellur         IITB/KReSIT/2007/May/49
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.

 
DynaSPOT: Dynamic Services Provisioned Optical Transport Test-bed – 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          IITB/KReSIT/2007/July/50
We report on the DynaSPOT (Dynamic Services Provisioned Optical Transport) test-bed – 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 – 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 – 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 – 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.
 
Merge-by-Wire: Algorithms and System Support       Gurulingesh Raravi, Vipul Shingde, Ashish Gudhe, Krithi Ramamritham         IITB/KReSIT/2007/July/52
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.
 
1-Persistent Collision-Free MAC Protocols for Opportunistic Optical Hyperchannels       Jing Chen, Ashwin Gumaste, Jianping Wang and Si Qing Zheng         IITB/KReSIT/2007/July/53
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.
 


Printer friendly    Comment
  Copyright © 2004 KReSIT, IIT Bombay. All rights reserved sitemap    
  Kanwal Rekhi School of Information Technology, Indian Institute of Technology Bombay, Powai, Mumbai - 400 076.
+91-22-2576 7901/02. Fax: +91-22-2572 0022
Designed by Kamlesh