Stability results for networks with input and output blocking
Matthew Andrews, Lisa Zhang · 1998
We study network stability in the presence of both input blocking and output blocking.In this setting, two packets can cross a switch simultaneously only if they do not share an input link and they do not share an output link.We adopt the adversarial model of packet injections introduced hy Borodin et al, [S], Previous work in thii injection model assumed the existence of output blocking only.We dcmonotrate that providing network stability is more difllcult when the extra constraint of input blocking is present.For example, some natural analogues of many protocols that were stable in the output blocking model become unstable.Furthermore, instability can be achieved on simple acyclic networks, Our main contribution is a construction of distributed protocols that are stable for all networks.Our approach lo motivated by the LONQEST-IN-SYSTEM protocol for the output blocking model.A similar approach applied to other protocols leads to instability.The assumption of both input and output blocking is common in switching theory.To the best of our knowledge, the effect of input blocking on nettuorhstabiity has not been explored.