Name
Abstract | ||
|---|---|---|
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. |
Year | DOI | Venue |
|---|---|---|
2005 | 10.1109/IPSN.2005.1440936 | IPSN |
Keywords | Field | DocType |
small buffer,dense network,overflow loss,accurate approximation model,finite buffer,grid network,network size increase,efficient routing,queue size distribution,finite buffer network,buffer size,salesman routing,shortest path tree routing,intelligent networks,grid computing,probability,minimization,shortest path tree,minimisation,queueing theory,approximation theory,approximation algorithms,traveling salesman,algorithm design and analysis,routing,space technology,data gathering | Mathematical optimization,Multipath routing,Equal-cost multi-path routing,Link-state routing protocol,Dynamic Source Routing,Computer science,Static routing,Path vector protocol,Destination-Sequenced Distance Vector routing,Geographic routing | Conference |
ISBN | Citations | PageRank |
0-7803-9202-7 | 6 | 0.65 |
References | Authors | |
6 | 3 | |
Name | Order | Citations | PageRank |
|---|---|---|---|
| Guillermo Barrenetxea | 1 | 414 | 27.80 |
| Baltasar Beferull-Lozano | 2 | 588 | 67.49 |
| Martin Vetterli | 3 | 13926 | 2397.68 |