Abstract
We study queueing networks with a single source and a single sink. We assume that walkers traverse a network according to an unbiased random walk, and we analyze how network topology affects the total mean queue size $Q$, which we use to measure congestion. We examine network topologies that minimize $Q$ and provide proofs for some cases and numerical evidence of optimality for others. Finally, we present greedy algorithms that add and delete edges from a network to reduce $Q$, and we apply these algorithms to a supermarket store layout. We find that these greedy algorithms, which typically tend to add edges to the sink node, are able to significantly reduce $Q$. Our work helps improve understanding of how to design networks with low congestion and to amend networks to reduce congestion.