Study of computer network reliability with congestion

Conventionally, connectivity is used to measure the reliability based on physical failures of links. In practical situations, the links have finite capacity, and when the message load becomes too large, the excess messages are stored in a queue at the nodes. The network can fail due to excessive delays or drops in a queue (congestion) or link failures that isolate node pairs. How congestion can be included in network reliability computation is a problem.; In this thesis, first, reliability simulation models are built on packet switching computer networks with consideration of maximum queue length (congestion threshold), routing algorithm, link capacity, and packet arrival rate at each node. Poisson distribution is used to generate host traffic. Congestion can be caused by many factors. A link is considered as congested if the number of packets waiting to be transmitted over the link exceeds its maximum queue length or the queue is full. Simulation results on several network models with different parameters show that once link capacity and host traffic are given, network topology and routing algorithm are the key factors which determine how congestion occurs and how network reliability is affected by congestion.; Next, a state-space based algorithm is proposed to compute the reliability of vBNS—an IP over ATM network, at IP level including congestion. The algorithm is based on the facts: (1) congestion failure is considered as node failure because of the connection and queuing structure of a Cisco router, and (2) IP rerouting in vBNS network is only caused by physical trunk failures. Congestion is measured by the probability of buffer overflow at IP routers, and is computed using Markov Chain controlled on-off source model. Based on the bounds |R_all–R_a| < (qn) i < $3$ (with R_a the approximated all-terminal reliability, q link failure rate, n the number of links, and i the maximum number of link failures occurring at the same time), the number of states to be computed is O(n i), with i = and qn << 1. The complexity of the algorithm is O(ni * polynomial(m, n)), m is the number of nodes.