On-Chip Clock Network Skew Measurement using Sub-Sampling

We present a technique for an all-digital on-chip delay measurement system to measure the skews in a clock distribution network. It uses the principle of sub-sampling. Measurements from a prototype fabricated in a 65 nm industrial process, indicate the ability to measure delays with a resolution of 0.5ps and a DNL of 1.2 ps.

A Slotted Aloha joint MAC-cum-Routing protocol for data gathering sensor network applications

In this paper we have proposed and implemented a joint Medium Access Control (MAC) -cum- Routing scheme for environment data gathering sensor networks. The design principle uses node 'battery lifetime' maximization to be traded against a network that is capable of tolerating: A known percentage of combined packet losses due to packet collisions, network synchronization mismatch and channel impairments Significant end-to-end delay of an order of few seconds We have achieved this with a loosely synchronized network of sensor nodes that implement Slotted-Aloha MAC state machine together with route information. The scheme has given encouraging results in terms of energy savings compared to other popular implementations. The overall packet loss is about 12%. The battery life time increase compared to B-MAC varies from a minimum of 30% to about 90% depending on the duty cycle.

Analysis of network architectures for zigbee sensor clusters

We provide a comparative performance analysis of network architectures for beacon enabled Zigbee sensor clusters using the CSMA/CA MAC defined in the IEEE 802.15.4 standard, and organised as (i) a star topology, and (ii) a two-hop topology. We provide analytical models for obtaining performance measures such as mean network delay, and mean node lifetime. We find that the star topology is substantially superior both in delay performance and lifetime performance than the two-hop topology.

An efficient reduction algorithm for computation of interconnect delay variability for statistical timing analysis in clock tree planning

In this paper, we propose a novel and efficient algorithm for modelling sub-65 nm clock interconnect-networks in the presence of process variation. We develop a method for delay analysis of interconnects considering the impact of Gaussian metal process variations. The resistance and capacitance of a distributed RC line are expressed as correlated Gaussian random variables which are then used to compute the standard deviation of delay Probability Distribution Function (PDF) at all nodes in the interconnect network. Main objective is to find delay PDF at a cheaper cost. Convergence of this approach is in probability distribution but not in mean of delay. We validate our approach against SPICE based Monte Carlo simulations while the current method entails significantly lower computational cost.

In-Network Computation in Random Wireless Networks: A PAC Approach to Constant Refresh Rates with Lower Energy Costs

We propose a method to compute a probably approximately correct (PAC) normalized histogram of observations with a refresh rate of Theta(1) time units per histogram sample on a random geometric graph with noise-free links. The delay in computation is Theta(root n) time units. We further extend our approach to a network with noisy links. While the refresh rate remains Theta(1) time units per sample, the delay increases to Theta(root n log n). The number of transmissions in both cases is Theta(n) per histogram sample. The achieved Theta(1) refresh rate for PAC histogram computation is a significant improvement over the refresh rate of Theta(1/log n) for histogram computation in noiseless networks. We achieve this by operating in the supercritical thermodynamic regime where large pathways for communication build up, but the network may have more than one component. The largest component however will have an arbitrarily large fraction of nodes in order to enable approximate computation of the histogram to the desired level of accuracy. Operation in the supercritical thermodynamic regime also reduces energy consumption. A key step in the proof of our achievability result is the construction of a connected component having bounded degree and any desired fraction of nodes. This construction may also prove useful in other communication settings on the random geometric graph.

Delay constrained optimal relay placement for planned wireless sensor networks

In this paper, we study the problem of wireless sensor network design by deploying a minimum number of additional relay nodes (to minimize network design cost) at a subset of given potential relay locationsin order to convey the data from already existing sensor nodes (hereafter called source nodes) to a Base Station within a certain specified mean delay bound. We formulate this problem in two different ways, and show that the problem is NP-Hard. For a problem in which the number of existing sensor nodes and potential relay locations is n, we propose an O(n) approximation algorithm of polynomial time complexity. Results show that the algorithm performs efficiently (in over 90% of the tested scenarios, it gave solutions that were either optimal or exceeding optimal just by one relay) in various randomly generated network scenarios.

Conflict-Tolerant Real-Time Specifications in Metric Temporal Logic

A framework based on the notion of "conflict-tolerance" was proposed in as a compositional methodology for developing and reasoning about systems that comprise multiple independent controllers. A central notion in this framework is that of a "conflict-tolerant" specification for a controller. In this work we propose a way of defining conflict-tolerant real-time specifications in Metric Interval Temporal Logic (MITL). We call our logic CT-MITL for Conflict-Tolerant MITL. We then give a clock optimal "delay-then-extend" construction for building a timed transition system for monitoring past-MITL formulas. We show how this monitoring transition system can be used to solve the associated verification and synthesis problems for CT-MITL.

Optimizing Delay in Sequential Change Detection on Ad Hoc Wireless Sensor Networks

We consider the classical problem of sequential detection of change in a distribution (from hypothesis 0 to hypothesis 1), where the fusion centre receives vectors of periodic measurements, with the measurements being i.i.d. over time and across the vector components, under each of the two hypotheses. In our problem, the sensor devices ("motes") that generate the measurements constitute an ad hoc wireless network. The motes contend using a random access protocol (such as CSMA/CA) to transmit their measurement packets to the fusion centre. The fusion centre waits for vectors of measurements to accumulate before taking decisions. We formulate the optimal detection problem, taking into account the network delay experienced by the vectors of measurements, and find that, under periodic sampling, the detection delay decouples into network delay and decision delay. We obtain a lower bound on the network delay, and propose a censoring scheme, where lagging sensors drop their delayed observations in order to mitigate network delay. We show that this scheme can achieve the lower bound. This approach is explored via simulation. We also use numerical evaluation and simulation to study issues such as: the optimal sampling rate for a given number of sensors, and the optimal number of sensors for a given measurement rate

Distributed load adaptive scheduling for throughput and delay guarantees in fading wireless LANs

We consider a problem of providing mean delay and average throughput guarantees in random access fading wireless channels using CSMA/CA algorithm. This problem becomes much more challenging when the scheduling is distributed as is the case in a typical local area wireless network. We model the CSMA network using a novel queueing network based approach. The optimal throughput per device and throughput optimal policy in an M device network is obtained. We provide a simple contention control algorithm that adapts the attempt probability based on the network load and obtain bounds for the packet transmission delay. The information we make use of is the number of devices in the network and the queue length (delayed) at each device. The proposed algorithms stay within the requirements of the IEEE 802.11 standard.

Fault-tolerant Video on Demand in RSerPool Architecture

With the advent of Internet, video over IP is gaining popularity. In such an environment, scalability and fault tolerance will be the key issues. Existing video on demand (VoD) service systems are usually neither scalable nor tolerant to server faults and hence fail to comply to multi-user, failure-prone networks such as the Internet. Current research areas concerning VoD often focus on increasing the throughput and reliability of single server, but rarely addresses the smooth provision of service during server as well as network failures. Reliable Server Pooling (RSerPool), being capable of providing high availability by using multiple redundant servers as single source point, can be a solution to overcome the above failures. During a possible server failure, the continuity of service is retained by another server. In order to achieve transparent failover, efficient state sharing is an important requirement. In this paper, we present an elegant, simple, efficient and scalable approach which has been developed to facilitate the transfer of state by the client itself, using extended cookie mechanism, which ensures that there is no noticeable change in disruption or the video quality.

On network coding for acyclic networks with delays

Problems related to network coding for acyclic, instantaneous networks (where the edges of the acyclic graph representing the network are assumed to have zero-delay) have been extensively dealt with in the recent past. The most prominent of these problems include (a) the existence of network codes that achieve maximum rate of transmission, (b) efficient network code constructions, and (c) field size issues. In practice, however, networks have transmission delays. In network coding theory, such networks with transmission delays are generally abstracted by assuming that their edges have integer delays. Using enough memory at the nodes of an acyclic network with integer delays can effectively simulate instantaneous behavior, which is probably why only acyclic instantaneous networks have been primarily focused on thus far. However, nulling the effect of the network delays are not always uniformly advantageous, as we will show in this work. Essentially, we elaborate on issues ((a), (b) and (c) above) related to network coding for acyclic networks with integer delays, and show that using the delay network as is (without adding memory) turns out to be advantageous, disadvantageous or immaterial, depending on the topology of the network and the problem considered i.e., (a), (b) or (c).

Traffic Profiling for Efficient Network Resource Utilization.

Traffic Engineering has been the prime concern for Internet Service Providers (ISPs), with the main focus being minimization of over-utilization of network capacity even though additional capacity is available which is under-utilized, Furthermore, requirements of timely delivery of digitized audiovisual information raises a new challenge of finding a path meeting these requirements. This paper addresses the issue of (a) distributing load to achieve global efficiency in resource utilization. (b) Finding a path satisfying the real time requirements of, delay and bandwidth requested by the applications. In this paper we do a critical study of the link utilization that varies over time and determine the time interval during which the link occupancy remains constant across days. This information helps in pre-determining link utilization that is useful in balancing load in the network Finally, we run simulations that use a dynamic time interval for profiling traffic and show improvement in terms number of calls admitted/blocked.

Delay Optimal Event Detection on Ad Hoc Wireless Sensor Networks

We consider a small extent sensor network for event detection, in which nodes periodically take samples and then contend over a random access network to transmit their measurement packets to the fusion center. We consider two procedures at the fusion center for processing the measurements. The Bayesian setting, is assumed, that is, the fusion center has a prior distribution on the change time. In the first procedure, the decision algorithm at the fusion center is network-oblivious and makes a decision only when a complete vector of measurements taken at a sampling instant is available. In the second procedure, the decision algorithm at the fusion center is network-aware and processes measurements as they arrive, but in a time-causal order. In this case, the decision statistic depends on the network delays, whereas in the network-oblivious case, the decision statistic does not. This yields a Bayesian change-detection problem with a trade-off between the random network delay and the decision delay that is, a higher sampling rate reduces the decision delay but increases the random access delay. Under periodic sampling, in the network-oblivious case, the structure of the optimal stopping rule is the same as that without the network, and the optimal change detection delay decouples into the network delay and the optimal decision delay without the network. In the network-aware case, the optimal stopping problem is analyzed as a partially observable Markov decision process, in which the states of the queues and delays in the network need to be maintained. A sufficient decision statistic is the network state and the posterior probability of change having occurred, given the measurements received and the state of the network. The optimal regimes are studied using simulation.

A study of epileptogenic network structures in rat hippocampal cultures using first spike latencies during synchronization events

Study of hypersynchronous activity is of prime importance for combating epilepsy. Studies on network structure typically reconstruct the network by measuring various aspects of the interaction between neurons and subsequently measure the properties of the reconstructed network. In sub-sampled networks such methods lead to significant errors in reconstruction. Using rat hippocampal neurons cultured on a multi-electrode array dish and a glutamate injury model of epilepsy in vitro, we studied synchronous activity in neuronal networks. Using the first spike latencies in various neurons during a network burst, we extract various recurring spatio-temporal onset patterns in the networks. Comparing the patterns seen in control and injured networks, we observe that injured networks express a wide diversity in their foci (origin) and activation pattern, while control networks show limited diversity. Furthermore, we note that onset patterns in glutamate injured networks show a positive correlation between synchronization delay and physical distance between neurons, while control networks do not.

A study of epileptogenic network structures in rat hippocampal cultures using first spike latencies during synchronization events

Study of hypersynchronous activity is of prime importance for combating epilepsy. Studies on network structure typically reconstruct the network by measuring various aspects of the interaction between neurons and subsequently measure the properties of the reconstructed network. In sub-sampled networks such methods lead to significant errors in reconstruction. Using rat hippocampal neurons cultured on a multi-electrode array dish and a glutamate injury model of epilepsy in vitro, we studied synchronous activity in neuronal networks. Using the first spike latencies in various neurons during a network burst, we extract various recurring spatio-temporal onset patterns in the networks. Comparing the patterns seen in control and injured networks, we observe that injured networks express a wide diversity in their foci (origin) and activation pattern, while control networks show limited diversity. Furthermore, we note that onset patterns in glutamate injured networks show a positive correlation between synchronization delay and physical distance between neurons, while control networks do not.