Efficient routing with small buffers in dense networks

The analysis and design of routing algorithms for finite buffer networks requires solving the associated queue network problem which is known to be hard. We propose alternative and more accurate approximation models to the usual Jackson's theorem that give more insight into the effect of routing algorithms on the queue size distributions. Using the proposed approximation models, we analyze and design routing algorithms that minimize overflow losses in grid networks with finite buffers and different communication patterns, namely uniform communication and data gathering. We show that the buffer size required to achieve the maximum possible rate decreases as the network size increases. Motivated by the insight gained in grid networks, we apply the same principles to the design of routing algorithms for random networks with finite buffers that minimize overflow losses. We show that this requires adequately combining shortest path tree routing and traveling salesman routing. Our results show that such specially designed routing algorithms increase the transmitted rate for a given loss probability up to almost three times, on average, with respect to the usual shortest path tree routing.