Document Type

Technical Report

Publication Date

1988-04-01

Filename

WUCS-88-14.pdf

DOI:

10.7936/K7NK3CCM

Technical Report Number

WUCS-88-14

Abstract

Noahnet is an experimental flood local area network with features such as high reliability and high performance. Noahnet uses a randomly connected graph topology with four to five interconnections per node and a flooding protocol to route messages.

In Noahnet flooding, the routing of a message from a source to the destination node is a two step process: flooding-growth and flooding-contraction. During the growth of flooding, the message propagates to every node which is not occupied with a message and is reachable from the source node. During the contraction of flooding, the nodes that became occupied during the growth of flooding become unoccupied again. Nodes on unsuccessful paths become unoccupied in a relatively short time compared to the nodes on the successful path.

The purpose of this paper is to present two analytical performance models which we have designed to understand the load-throughout behavior of Noahnet. Both models assume slotted Noahnet operation and also assume the if k messages attempt transmission in a slot, the network gets divided into k partitions of arbitrary sizes - one partition for each message.

First, we show that the average number of successful messages in a slot given k attempted transmissions is (M-k)/(N-1), where N is the number of nodes in the network and M is the number of nodes out of N that participate in the flooding of k messages. This is an interesting result and is used in both models to derive the load-throughout equations.

Each model is then presented using a set of assumptions, derivations of load-throughout equations, a set of plots, and the discussion of results. Models one and two differ in the way they account from retransmissions. Model two helps study the effect the retransmission probability on the performance of the network.

The results from these models suggest that the maximum throughput of Noahnet is always less than one message per slot. Also the network is unstable in the sense that the throughput increases with the load only up to a certain threshold value of load; beyond that the throughput starts decreasing with the load. Model two suggests that Noahnet is essentially a contention system, and to get the maximum throughput, the load should be such as to given the optimal contention.

Comments

Permanent URL: http://dx.doi.org/10.7936/K7NK3CCM

Share

COinS