Performance analysis of packet -switched networks

There has been a lot of interest in recent times on the performance analysis of routing algorithms for packet-switched networks. In this thesis, we focus on some aspects of performance analysis of simple routing algorithms that are not well-understood from an analytical standpoint. We focus on two classes of networks in this dissertation, viz., networks that drop packets to resolve contention for buffer space, and networks which have infinite buffers. We study the steady-state performance of butterfly networks that drop packets and prove upper and lower bounds on its expected throughput and packet loss rate. Then, we prove that for any acyclic network, the throughput is within a constant factor of its expected value with high-probability. We then focus on the transient phase in acyclic queuing networks and derive upper bounds on the time the network takes to get close to steady-state. The bounds are functions of the network size, buffer size and the number of levels in the network. For networks with infinite buffers, we derive sufficient conditions for any discrete-time network to approach a steady-state (this property has sometimes been called stability in the literature). Next, we focus on the butterfly network and derive high-probability bounds on the queue-length distributions. We obtain a necessary and sufficient condition necessary for the butterfly network to approach a steady-state. Finally, we prove upper bounds on the time taken by infinite-buffer linear networks to get close to steady-state after starting from the empty state