This paper describes the design and performance of a routing protocol for mobile ad-hoc networks. Our routing protocol is named "hybrid routing" in that it attempts to take advantage of both proactive and reactive approaches. The protocol is based on the concept of multipoint relaying (MPR) to minimize flooding traffic. For most applications over mobile ad-hoc networks, it is expected that a major portion of communication will be done in the two-hop region. Therefore, when a node needs a route to a destination in the two-hop region, it consults with the routing table as the proactive approach to find the route directly. Outside this region, on the other hand, it discovers a route on demand as the reactive approach through the use of MPR flooding. The proposed protocol has been validated using the ns network simulator with wireless and mobility extensions. The simulation results show that our MPR-HR protocol provides higher efficiency in terms of routing overhead compared to AODV one of the most efficient routing protocols released for mobile ad-hoc networks.

This paper describes the design and performance of a medium access control protocol (called reservation CSMA/CA) for multimedia traffic over mobile ad-hoc networks. The reservation CSMA/CA protocol is based on a hierarchical approach consisting of two sublayers. The lower sublayer of the MAC protocol provides a fundamental access method using CSMA/CA to support asynchronous data traffic over mobile ad-hoc networks. The upper sublayer is designed to support real-time periodic traffic by making a slot reservation with the three-way handshake prior to actual data transmission. The proposed protocol has been validated using a software emulator which was carried out with the UNIX implementation. The simulation results show that the reservation CSMA/CA offers higher throughput for real-time periodic traffic compared to the IEEE 802.11 standard, while providing deterministic delay performance.

We develop and evaluate several heuristics for the construction of a multicast tree to transmit a given message of size r from a source to a set of destinations with guarantees on the end-to-end delay over a computer network. Different multicast trees can be constructed for various values of r. We consider delay sources on links to be from propagation and bandwidth availability. The heuristics that we have developed try to minimize the end-to-end delay of the multicast tree taking into consideration various switching architectures that range from pipeline to store-and-forward. Our evaluations of these heuristics consider various network generation models including locality, Waxman I and II, and transit-stub. We have evaluated multicast tree generation heuristics based on both shortest path and Steiner tree heuristics. A novel heuristic called grow-tree is proposed in this paper and it is based on both Kruskal's and Prim's minimum spanning tree algorithm. This heuristic performs admirably well in many network environments.

A dynamic ad hoc network consists of a collection of mobile hosts with frequently changing network topology. We propose a distributed algorithm that adapts to the topology by utilizing spanning trees in the regions where the topology is stable, and resorting to an intelligent flooding-like approach in highly dynamic regions of the network. Routing is performed using the spanning trees based on a hold-and-forward or shuttling method. We introduce the notion of connectivity-through-time and holding time to quantify the performance of the routing algorithms for various network connectivity scenarios. Using simulation, we study the throughput, reachability and message-reachability ratio of the proposed network under various connection/reconnection rates and holding times.

We consider the transmission of a message of size r from a source to a destination over a computer network with n nodes and m links. There are three sources of delays: (a) propagation delays along the links, (b) delays due to bandwidth availability on the links, and (c) queuing delays at the intermediate nodes. First, we consider that the delays on various links and nodes are given as functions of the message size. If the delay in (b) is a non-increasing function of the bandwidth, we propose O(m/sup 2/+mn log n) time algorithm to compute a path with the minimum end-to-end delay for any given message size r. We then consider that the queuing delay in (c) is a random variable correlated with the message size according to an unknown distribution. At each node, the measurements of queuing delays and message sizes are available. We propose two algorithms to compute paths whose delays are close to optimal delays with a high probability, irrespective of the distribution of the delays.

We consider two generic routing problems via multiple paths in a computer network wherein bandwidth can be reserved, and guaranteed, once reserved, on the links. The first problem requires that a message of finite length be transmitted from s to d within /spl tau/ units of time. The second problem requires that a sequential message of /spl tau/ units be transmitted at a rate of /spl eta/ such that maximum time difference between two units received out of order is no more than q. We propose a polynomial-time algorithm to the first problem, and present simulation results to illustrate its applicability. We show the second problem to be NP-complete, and propose a polynomial-time approximate solution.

Researchers have proposed the core-based trees (CBTs) and protocol independent multicasting (PIM) protocols to route multicast data an internetworks. We compare the simulated performance of CBT and PIM using the OPNET network simulation tool. Performance metrics include end-to-end delay, network resource usage, join time, the size of the tables containing multicast routing information, and the impact of the timers introduced by the protocols. We also offer suggestions to improve PIM sparse mode while retaining the ability to offer both shared tree and source-based tree routing.

Researchers have proposed the core based trees (CBT) and protocol independent multicasting (PIM) protocols to route multicast data on internetworks. The performance of these protocols is examined in the distributed interactive simulation (DIS) environment using the OPNET network simulation tool. The simulation results provide measures of important performance metrics including end-to-end delay, network resource usage, and join time. The size of the tables containing multicast routing information and the impact of the timers introduced by the protocols are also examined. Suggestions are offered to improve PIM Sparse while retaining the ability to offer both shared tree and source-based tree routing.