This paper presents preliminary results of a progressive research work investigating effects of vegetation on RF propagation. A theoretical model is developed to predict signal loss due to vegetation. The model considers path segments of different vegetation densities where the density measurements are available from satellite data. Signal loss over the entire propagation path is calculated by predicting and combining losses over individual segments. The model predicts vegetation loss factor (VLF) over each segment and then calculates the overall VLF of a path traversing multiple segments. The model has been validated against field data. Further modification of the model to include the effects of other environmental factors and different signal frequencies is under way.

While indoor wireless sensor network (WSN) research has recently flourished for monitoring civil and industrial infrastructure, considerably less attention has been given to the development of reliable outdoor WSNs capable of long-term operation in challenging remote locations. We present wireless sensor network link performance results from the first year of monitoring micro-meteorological conditions alongside the 802.15.4 link received signal strength indicator (RSSI) within an old growth stand of deciduous boreal Aspen forest (Populus tremuloides) in Northern Alberta, Canada. Thirty-six weather proof nodes were equipped with meteorological sensors and distributed across one hectare in the forest understory to assess the application of WSNs for observing high resolution changes in seasonal ecosystem productivity and forest phenology. We describe here the density distribution of node RSSI using Gaussian kernel density estimates in relation to node antenna-receiver orientation and vegetation seasonality. RSSI across the network displays a lognormal distribution with an increasing bimodal tendency with path length through the forest stand. Spatial variability in RSSI is discussed with respect to forest structure. A strong temporal relationship between RSSI variability and plant canopy development is observed with a 20dBm or 100 fold difference in mean network radio signal power from spring leaf presence to fall leaf absence. The meteorological and biophysical factors associated with this trend are explored using multiple regression and relative factor importance analysis. Our results indicate that in addition to meteorological data, spectral vegetation density metrics are useful in assisting deployment planning and network performance diagnostics when using wireless sensor networks for remote forestry applications. The longevity and performance of this outdoor WSN can be seen as a new standard for harsh network-climate tolerance in northern boreal environments.

In this paper, we present two approximation algorithms for minimizing power consumption of wireless sensor networks (WSNs) in environmental monitoring applications. Most approximation algorithms for similar problems assume that the cost function satisfies the triangle inequality. For a cost function defined based on power consumption for reliable transmission between two nodes in a WSN, this assumption is not true. We first prove that we have the triangle inequality in a relaxed sense for these cost functions and then we use this in performance analysis of our two algorithms. The first algorithm is a natural bottom-up algorithm, while the second algorithm is a more complicated, top-down algorithm. We show that the solutions from both these algorithms are within a constant factor of the optimum value, and that the top-down algorithm has a better constant ratio. Our experimental results show that these two algorithms usually perform much better than proven approximation guarantees.

In this paper, we present two approximation algorithms for near-optimal design of hierarchical wireless sensor networks (WSNs) in environmental monitoring applications. Since the problem of our interest is NP-hard, we design two approximation algorithms for this problem. The first algorithm is a natural bottom-up algorithm that uses an approximation algorithm of the k-median problem with approximation ratio ρ. The second algorithm is a less obvious, top-down algorithm that also uses the same ρ-approximation algorithm. We show that the bottom-up algorithm is a ((ρ + 1)p- 1)-approximation algorithm, where p is the number of levels in the hierarchy, while the top-down algorithm is a 3ρ- approximation. That is, the performance of the top-down algorithm does not depend on p. Our experimental results show that these two algorithms perform very well, with the top-down algorithm being superior.

In mobile networks, node movements may lead to a situation called network partition where an end-to-end path may never exist because the network is divided into several isolated subnetworks. Deploying stationary relays introduces new transmission opportunities leading to the improvement of network connectivity and performance. The majority of the proposed solutions concentrated on deploying the minimum number of relays in the network. However, relay deployment should also be resilient regarding relay node failures. In this paper, we show how the relay deployment problem can be modelled as a k-element connectivity problem in which multiple relay-disjoint paths are deployed to connect isolated subnetworks. To solve this problem, we present three heuristic algorithms targeting at finding the minimum number of relays to form k-element connected networks. Our experiments using synthetic and real data showed that the proposed greedy algorithm is 2 or 3 orders of magnitude faster and never worse than the other two algorithms.

In this paper, we present Structured Message Transport (SMT). SMT is a transport protocol coordinator designed to alleviate the head-of-line blocking problem of existing transport layer protocols, such as TCP. SMT uses explicit dependency tracking instead of assuming total ordering between messages of a communication. Moreover, explicit dependency tracking creates the opportunity for using multiple paths. SMT can distribute messages into more than one path. However, unlike the stream-based Multi-Path-TCP, SMT is not limited to a single stream of messages. Relaxing the ordering constraints between the messages makes it possible to deliver the received messages to the application layer if they do not have any unmet dependencies. We have designed and implemented a prototype of SMT to test our ideas. Moreover, we have integrated the ideas from SMT into a proprietary software system and we show that the SMT version performs better than the base version.

Resource competition is inevitable in shared-resource systems, as the number of users increases or their resource demands change. In wireless networks, this problem is aggravated due to the existence of co-channel interference. Without appropriate control, harmful competition causes unbalanced user consumption of resources (e.g. starvation), and resource waste due to conflicts and idleness. In this paper we propose a novel framework to effectively manage resources (e.g. shared wireless channels). Compared with the state-of-art global optimization algorithm, our method is superior in terms of eliminating control overhead caused by message passing, achieving competitive performance, and reducing computational complexity. This framework combines the advantages of global and local optimization methods and drives the system toward a global optimum by intelligently exploiting local information.

Allocating wireless network resources fairly to users, and using these limited resources efficiently is crucial for improving system performance and satisfying user requirements. Our proposal is to achieve higher network throughput via lower transmit power, and to reduce throughput differences between flows caused by uncontrolled resource competition. A hierarchical joint control framework has been designed to achieve this goal. The performance of this framework has been evaluated via ns2 simulation. Our experimental results demonstrate that our control framework significantly improves performance and results in lower packet loss rates, higher network throughput, shorter end-to-end delay and enhanced fairness.

Inefficient resource management may cause problems of reliability of service in shared medium wireless networks. Resources include bandwidth, processor cycles and buffers. Excessive competition for these resources can cause severe packet collision rates, compound network congestion, or even result in starvation of some nodes. In such a situation, data transmission is subject to very long delays and significant packet losses. Although transport layer protocols can help improve end-to-end performance, these approaches are slow in responding to network changes and incur additional overhead. This paper aims to reduce transmission delay and increase packet delivery ratio. A hybrid resource allocation problem is formulated by the Primal algorithm and a controller is derived to decrease congestion globally and to reduce collisions locally. Our simulation results show that this hybrid controller can achieve packet loss rates close to 1% and significantly shorten end-to-end delay even in a high interference environment with heavy system load. In addition, we also compare the performance of the hybrid controller with the impact of multipath routing. The accuracy of our simulation is improved by adding a probabilistic preamble detection model and SINR collision model based on frame error rate.

In shared-medium wireless networks, nodes contend for medium access in space, time and channel bandwidth. Uncontrolled competition for limited network resources causes severe packet collisions and compounds network congestion. Consequently, data transmission is subject to very long delay, significant packet loss and poor throughput. This work focuses on improving data transmission in wireless ad hoc networks through optimal control of spatial, temporal and bandwidth contention. Our simulation study demonstrates that this optimal control scheme outperforms RTS/CTS and achieves significant improvement of CSMA/CA performance under various effects.

In routers based on commodity off-the-shelf (COTS) hardware and open-source operating systems, there are correlations between the transmission and reception capabilities of individual network interface cards (NICs) and multiple NICs on the same bus because of NIC/bus bottlenecks. To manage the adverse effects of this correlation, we propose an adaptive scheduling mechanism based on system state information, which balances transmission and reception rates and increases the overall forwarding rate.

The Hurst parameter characterizes the degree to which a time series is long range dependent (LRD). The value of this parameter can be used as an input to algorithms for bandwidth allocation, buffer sizing and congestion control. However, for these algorithms to be effective over the long run they must change their actions when the value of the Hurst parameter changes. We demonstrate a new technique which uses a wavelet decomposition to detect a change in the Hurst parameter. Our technique tests the variance structure of the wavelet coefficients at multiple scales and uses changes in variance to signal a change in the value of the Hurst parameter. The efficacy of the proposed technique is demonstrated by comparing its performance to that of another recently proposed method for change detection. The performance tests were conducted using artificially generated data sets which contain changes in the Hurst parameter of known position, magnitude and sign.

Extensible software-based routers running on commodity off-the-shelf hardware and open-source operating systems have been motivated by the progress in hardware technologies and by the demand for routers with new capabilities. The Click modular router is one such software system. Click provides a mechanism to extend packet processing functions while supporting higher packet forwarding performance compared with other software-based routers. However the limitation of executing on a PC is in tension with the requirement for higher performance. In this paper, we explore the scalability of an extended version of Click that runs on a cluster of PCs connected by a high-speed/low latency InfiniBand interconnection network. We present the implementation and evaluation of our prototype. Our measurements show that the performance of this router can be scaled nearly linearly with increasing cluster size.

IP routers are now increasingly expected to do more than just traditional packet forwarding - they must be extensible as well as scalable. It is a challenge to design a router architecture to support both high (and increasing) packet forwarding rates as well as a wide array of packet processing services. The most easily extensible design would be entirely software-based, but this is in tension with the requirement for high performance. One possible answer is to couple a software-based router with a high performance platform. Cluster-based supercomputers are very successful due to their scalability and high availability, and they also exhibit outstanding performance/cost ratio. In this paper, we describe the implementation and evaluation of an extensible and scalable software-based IP router, which is built using a cluster of processors connected by a high-speed/low latency InfiniBand interconnection network. Our measurements show that the performance of this router can be scaled nearly linearly with increasing hardware

Packet scheduling in parallel forwarding systems is a hard problem. Two major goals of a scheduler that distributes incoming packets to multiple forwarding engines are to achieve high system utilization (by balancing the load evenly among the multiple engines) and to maintain packet ordering within individual flows. Additionally, from the viewpoint of the overall performance, the system should exhibit a good cache behavior by preserving temporal locality in the workload of each forwarding engine. In this paper, we show how the burstiness in Internet flows can be exploited to improve the performance of the scheduler. Specifically, TCP flows, which contribute to over 90 percent of the Internet traffic, transmit in bursts with relatively large delays in between. We propose a load balancing scheme based on this insight to achieve the scheduling goals. Our design is verified by simulations driven by real-world traces.

Workload distribution is critical to the performance of network processor based parallel forwarding systems. Scheduling schemes that operate at the packet level, e.g., round-robin, cannot preserve packet-ordering within individual TCP connections. Moreover, these schemes create duplicate information in processor caches and therefore are inefficient in resource utilization. Hashing operates at the flow level and is naturally able to maintain per-connection packet ordering; besides, it does not pollute caches. A pure hash-based system, however, cannot balance processor load in the face of highly skewed flow-size distributions in the Internet; usually, adaptive methods are needed. In this paper, based on measurements of Internet traffic, we examine the sources of load imbalance in hash-based scheduling schemes. We prove that under certain Zipf-like flow-size distributions, hashing alone is not able to balance workload. We introduce a new metric to quantify the effects of adaptive load balancing on overall forwarding performance. To achieve both load balancing and efficient system resource utilization, we propose a scheduling scheme that classifies Internet flows into two categories: the aggressive and the normal, and applies different scheduling policies to the two classes of flows. Compared with most state-of-the-art parallel forwarding schemes, our work exploits flow-level Internet traffic characteristics.

Network routers rely on Content Addressable Memories (CAMs) to accelerate the process of looking up the next hop of a packet. We describe our implementation of a versatile prototype for a CAM. This prototype allows the empirical evaluation of the idea of caching lookup results in a multizone cache organized according to the length of the network prefix portion of the addresses. Implementing a cache in an FPGA efficiently required the design of a new cache replacement policy, the Bank Nth Chance policy. In this paper we present results from a functional simulator that allows the comparison of this new policy with existing ones such as LRU, FIFO and Second Chance. We have a complete and functional prototype with pipelined lookups implemented in a Xilinx Virtex 2000E device; we also report frequency of operation and occupation of the device.

We estimate that approximately 40% of current Internet traffic is due to Web crawlers retrieving pages for indexing. We address this problem by introducing an efficient indexing system based on active networks. Our approach employs strategically placed active routers that constantly monitor passing Internet traffic, analyze it, and then transmit the index data to a dedicated back-end repository. Our simulations have shown that active indexing is up to 30% more efficient than the current crawler-based techniques.

The total transmission capacity required by a transport network to satisfy demand and protect it from failures contributes significantly to its cost, especially in long-haul networks. Previously, the spare capacity of a network with a given set of working span sizes has been optimized to facilitate span restoration. Path restorable networks can, however, be even more efficient by defining the restoration problem from an end to end rerouting viewpoint. We provide a method for capacity optimization of path restorable networks which is applicable to both synchronous transfer mode (STM) and asynchronous transfer mode (ATM) virtual path (VP)-based restoration. Lower bounds on spare capacity requirements in span and path restorable networks are first compared, followed by an integer program formulation based on flow constraints which solves the spare and/or working capacity placement problem in either span or path restorable networks. The benefits of path and span restoration, and of jointly optimizing working path routing and spare capacity placement, are then analyzed.

There are a number of contexts in transport network design where cost savings arise from providing a dedicated transmission system between two nonadjacent nodes. This occurs when the cost to terminate demands at intermediate cross-connecting and grooming nodes exceeds the alternative of providing a dedicated, perhaps only partly filled, system. Today, dedicated end-to-end "express routes" are usually found where large demands flow between major centers or to/from hubbing sites where traffic can be aggregated to warrant an express system. Smaller demand flows are usually terminated at each flexibility point en route to permit remultiplexing with other demands, thereby keeping the fiber system fill high. We consider a new means to find economic express system opportunities among combinations of the smaller co-routed demands. The hypothesis is that certain collections of demand may warrant express treatment over some common portion of their routes. These demands need not share common end nodes or be aggregated at a hub. Rather, they are discovered among the natural pattern of demand flows as a group of demands that travel together over some sequence of spans on which an express system might be cost-effective. The search problem is to detect the maximally coherent subgroups of demands en route that yield the best economic payback. Test results were obtained in four representative transport network topology and demand matrix models. Assuming a 75% level of system fill in the nonexpress baseline case, opportunities worth up to $45 M in equipment savings, relative to conventional design, were obtained using industry-supplied cost data. The concept of distributed partial-express system design may also be applicable to WDM-based networks to assign OC-n level units of demand to various express or nonexpress wavelengths.

In the development of technologies for span failure restoration, a question arises about the restoration rerouting characteristics to be specified. In theory, maximal rerouting capacity is obtained with a maximum flow (Max Flow) criterion. However, rerouting that realizes the k-successively shortest link disjoint paths (KSP) may be faster, easier, and, in distributed implementation, more robust than a distributed counterpart for Max Flow. The issue is, therefore, what the restoration capacity penalty is if KSP is used instead of Max Flow. To explore this tradeoff, the authors present a comparative study of the effectiveness of KSP versus Max Flow as an alternative rerouting criteria in the context of transport network span restoration. The comparison applies to both centrally controlled and distributed restoration systems. Study methods include exhaustive span failure experiments on a range of network models, and parametric and analytical investigations for insight into the factors resulting in KSP versus Max Flow differences. The main finding is that KSP restoration capacity is more than 99.9% of that from Max Flow in typical network models. The hypothesis is made that a generalized "trap" topology is responsible for all KSP-Max Flow capacity differences. The hypothesis is tested experimentally and used to develop analytical bounds which agree well with observed results. These findings and data are relevant to standards makers and equipment developers in specifying and engineering future restorable networks.>

Abstract The problem of finding shortest paths arises in many contexts; testing restoration algorithms and developing design packages for large telecommunications networks are two cases where the simple task of finding sets of restoration paths can consume up to 95 per cent of the execution time of an application program. This paper presents experimental studies of several well‐known shortest‐paths algorithms adapted to the task of finding the k‐successively‐shortest link‐disjoint replacement paths for restoration in a telecommunications network with n nodes. The implementations range in complexity fromO(kn2) when based on Dijkstra's original method, through several improvements to an efficient implementation ofO(kn[v+longn]) complexity, and finally to anO(kn) implementation for the special case of edge‐sparse graphs with small integer edge weights. Here v is the maximum degree of a node in the network. Several alternatives were tested during the course of these studies, particularly with a view to minimizing the number of heap updates, These alternatives are possible because we are searching for several paths between a given pair of nodes, rather than just one path between one or more pairs of nodes. Two fairly straightforward changes yield a decrease in execution time, whereas a more complex heap management strategy consumes as much time in the added code as it releases from the main routine. Experimental results confirm the theoretical complexity of q k n log n) and demonstrate a speed‐up of nearly an order of magnitude over the simplerO(kn2) implementation in the largest networks tested. The optimized implementation is recommended for planning and operational applications of k‐shortest paths rerouting for telecommunications network restoration and restorable network design. If hop counts or small integer link weights can be used to measure distances, then the qkn) implementation is recommended, as typical telecommunications networks are edge‐sparse.

This paper presents a metric for managing dynamically reconfigurable transport networks. In such networks, one physical set of transport links can be configured into many different logical networks, in order to meet uncertain and volatile traffic demands. Connectability is a figure of merit for capturing the composite routing efficiency and capacity utilization of a transport network. Connectability is mathematically inspired by existing metrics for reliability. Reliability concepts are adapted to quantify notions of efficiency in reconfigurable networks. The authors define connectability mathematically, and set out a procedure for its' calculation in a distributed real-time setting. The centralized version of this calculation has O(n log n) time complexity. A series of simulation studies are presented to illustrate the use of connectability in characterizing strategies for transport network reconfiguration. One strategy based on the isolated calculation of connectability at each node is shown to yield lower blocking and more efficient use of transport network resources than the other strategies tested. Finally, a short study of applying connectability to restoration in a national network demonstrates that there is a continuum along which restoration can be temporarily traded off against transport network management.>

The methodology used, and results obtained, in the development and verification of a protocol for real-time network restoration are described. This protocol, called selfhealing, relies on a combination of hardware and software features to achieve an advance in the speed of restoring network spans that have been cut. The hardware environment provides a paradigm for heavily parallel, asynchronous, distributed interaction. This environment is uniquely suited to interactions between digital cross-connect switches (DCS) embedded in a highly-capacity transport network. A speed determination based on an implementation of the protocol exactly as it would exist in the target DCS host machine is given.>