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 probability
of 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 interference
probability 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 and
Web 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.

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 the
performance 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.

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.

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 an
average packet loss of less than 2%, and a MOS of 3.6 which is considered as good in
practice. The users too gave a positive response to our system. We also tested Lo3 within
our department where it can be used as a wireless intercom service. To our knowledge, Lo3
is the first system to enable such a voice communication system using 802.15.4 technology,
and show its effectiveness in operational settings.

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.

In this paper we describe a new design of the operating system page
cache. Page caches form an important part of the memory hierarchy and
are used to access file-system data. In most operating systems, there
exists a single page cache whose contents are replaced according to
a LRU eviction policy.

We design and implement a page cache which is partitioned by
file---the per-file page cache. The per-file page cache provides
the ability to control fine-grained caching parameters such as cache
size and eviction policies for each file. Furthermore, the deterministic
cache allocation and partitioning allows for improved isolation among
processes. We provide dynamic cache partitioning(among files) by
using utility derived from the miss-ratio characteristics of the
file accesses.

We have implemented the per-file page cache architecture in the Linux kernel
and demonstrate its efficacy using disk image files of virtual machines
and different types of file access patterns by processes.
Experimental results show that the utility-based partitioning can
reduce the cache size by up to an order of magnitude while increasing
cache hit ratios by up to 20%. Among other features, the per-file page
cache has fadvise integration, a scan-resistant eviction algorithm
and reduced lock-contention and overhead during the eviction process.

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.

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.

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 efficient 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 filter-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 find 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-specific requirements to index and query data items based on the data semantics.

We consider a variant of the caching problem, where each request is a set of pages of a fixed 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.

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.

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 an
important input for consolidation and splitting decisions. Via extensive experimentation, we evaluate the applicability of our models using synthetic and real application workloads.

WSNs are inherently power constrained and are
often deployed in harsh environments. As such, node death is
a possibility that must be considered while designing protocols
for such networks. Rerouting of data is generally necessary so
that data from the descendant nodes of the dead node can
reach the sink. Since slot allocation in TDMA MAC protocols
is generally done based on the routing tree, all the nodes must
switch to the new routing tree to avoid collisions. This necessitates
disseminating the fault information to all the nodes reliably. We
propose a flooding algorithm for disseminating fault info to the
network reliably even in a lossy channel. Simulation results show
that the proposed flooding scheme consumes lesser energy and
converges faster than a simple flooding scheme. Rerouting the
data may result in increased TDMA schedule length. The energy
expenditure of the newly assigned parents also increases because
they have to relay data from more children than before. We
propose two distributed parent assignment algorithms in this
paper. The first algorithm minimizes the change in the TDMA
schedule and the second algorithm balances the load among the
newly assigned parents. Simulation of random topologies shows
that the increase in the TDMA frame length is lesser than that
with random parent assignment when the first algorithm is used.
We also observe that the lifetime of the most energy constrained
node (after fault recovery) is longer when the second algorithm
is used than that when random parent assignment is done.

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.

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 like
link 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.

We propose an opportunistic channel access scheme for cognitive radio-enabled
secondary networks. In our work, we model the channel occupancy due to Primary
User (PU) activity as a 2-state Alternating Renewal Process, with alternating
busy and idle periods. Once a Secondary Node (SN) senses the channel idle, the
proposed scheme uses the residual idle time distribution to estimate the transmission
duration in the remaining idle time. The SN transmits the frames within the
transmission duration without further sensing the channel, thereby reducing average
sensing overhead per transmitted frame. The analytical formulations used by
the scheme does not require the SN to know the start of the idle period. We validate
the analytical formulations using simulations, and compare the performance of the
proposed scheme with a Listen-Before-Talk (LBT) scheme.

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 consolidation
scheme to achieve good application performance.

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.

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, and
we 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.

Moving trains represent a voluminous mass of users
moving 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 scalability
and 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).

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 network
when the channel is sensed idle. We refer to primary network
as the network which carry the main traffic in a designated
spectrum band. We have considered IEEE 802.11 WLAN as a de
facto primary network operating in ISM band. Our study focuses
on a single WLAN channel that is used by WLAN clients and
a WLAN server for a mix of Email, FTP, and HTTP-based web
browsing applications. We model the occupancy of the channel by
primary WLAN nodes as an alternating renewal process. When
the secondary sender node has one or more frames to send, this
model is used by the the sender and receiver pair to estimate
residual idle time duration after the channel is sensed as idle.
The secondary sender then opportunistically transmits frames in
that duration without significantly degrading performance of the
primary WLAN applications. Our simulation results show that
the performance of secondary network is sensitive to the channel
sensing duration and that high secondary throughput can be
achieved without affecting the primary network significantly by
choosing appropriate value of channel sensing duration.

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 to
electrical energy, has emerged as an alternative to power sensor nodes. By exploiting recharge opportunities and
tuning 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.

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 a
specified set of constraints. In this technical report, we
present the graph theoretic concepts developed, leading
to the development of efficient algorithms for availability guaranteed overlay construction and maintenance.

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.

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.

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.

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.

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.

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.

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.

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

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 America
OCIS codes: 060.4250 Networks; 060.4250 Networks

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.

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.

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.

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.

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.

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.

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.