The performance of simple routing algorithms that drop packets
Suprakash Datta, Ramesh K. Sitaraman · 1997
Several modern high-speed networks implement routing algorithms that resolve contention for resources such as buffer space by dropping (i.e., deleting) packets.In this paper, we analyze the performance of such routing algorithms for the commonly-used butterfly network.We assume that each switch of the butterfly has a buffer that can hold a bounded number of packets, and any packet attempting to enter a switch with a full buffer is simply dropped from the network.We study three significant metrics that characterize routing performance:expected throughput of the network, packet loss rate, and expected delay of a packet.Our main results are analytic expressions for these three performance metrics in terms of the network-size, size of the buffer at each switch, and the packet arrival rate.Our analyses for the throughput and packet loss rate hold for any non-predictive queuing protocol, including simple, often-implemented protocols such as i%st-in fist-out (FIFO) and fixed-priority scheduling.Our delay expressions hold for the FIFO protocol.Several facts of interest to a network designer fall out of our analysis.Further, our results provide quantitative insights into how the three performance metrics tradeoff against each other.Also, we present simulation results to bolster the results of our analysis.Finally, we outline preliminary results for routing on other networks such aa the crossbar."The authors are supported in part by NSF Grant CCR-94-1OO77.Permission 10 nmkc digilillhrd copIcs otall or pml Ol-lhIS m;IINI:Il Ior personal or clmsroom mse is gmntc[i u'ithoul lte pmwdtd 1]1o1 (he copies are NOImade or distrihu{ed for protit o!-comnmrci:ll :Idlmltagc.the mp,vright iwlice.(he litle o!'dw puh(ictlllon Jnd its dale JPPMI'.and notice IS given 11111 copyright is by pwmwslon ol'lhr .+4Chi.inc."1'(copyo!hmwsc.10republish, !0 posl on scnvrs or (0 redislrlhu[c 10 1]s[s,rcqultm spwllic pmnissm atd/or lee STA4 97 NwpoII, Rhode lslw)d 1ISA Copyright 1997 ACh4 0-89791-8°0-8/97/06 .$3.5(1