Throughput-centric routing algorithm design

ABSTRACT

The increasing application space of interconnection networks now encompasses several applications, such as packet routing and I/O interconnect, where the throughput of a routing algorithm, not just its locality, becomes an important performance metric. We show that the problem of designing oblivious routing algorithms that have high worst-case or average-case throughput can be cast as a linear program. Globally optimal solutions to these optimization problems can be efficiently found, yielding provably good oblivious routing algorithms. Applying these techniques to k-ary 2-cube (tori) networks shows that previous routing algorithms sacrifice too much locality to achieve optimal worst-case throughput. This motivates the development of two new algorithms, IVAL and 2TURN, which improve locality to within 0.3% of optimal for an 8-ary 2-cube. Both algorithms have simple, deadlock-free implementations. Expanding the analysis of tori to average-case throughput reveals that there is a weak tradeoff between average-case and worst-case throughput. Specifically, both the IVAL and 2TURN algorithms developed for the worst-case also have good average-case throughput.

REFERENCES

• 1: W. J. Dally, P. P. Carvey, and L. R. Dennison, "The Avici terabit switch/router," in Conference Record of Hot Interconnects 6, August 1998, pp. 41--50.
• 2: InfiniBand Trade Association, "InfiniBand architecture specification," http://www.infinibandta.org.
• 3: L. G. Valiant , G. J. Brebner, Universal schemes for parallel communication, Proceedings of the thirteenth annual ACM symposium on Theory of computing, p.263-277, May 11-13, 1981, Milwaukee, Wisconsin, United States [doi>10.1145/800076.802479]
• 4: Herbert Sullivan , T R Bashkow, A large scale, homogeneous, fully distributed parallel machine, I, Proceedings of the 4th annual symposium on Computer architecture, p.105-117, March 23-25, 1977
• 5: Matthew Andrews , Baruch Awerbuch , Antonio Fernández , Tom Leighton , Zhiyong Liu , Jon Kleinberg, Universal-stability results and performance bounds for greedy contention-resolution protocols, Journal of the ACM (JACM), v.48 n.1, p.39-69, Jan. 2001 [doi>10.1145/363647.363677]
• 6: Li-Shiuan Peh , William J. Dally, A Delay Model and Speculative Architecture for Pipelined Routers, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.255, January 20-24, 2001
• 7: Ravindra K. Ahuja , Thomas L. Magnanti , James B. Orlin, Network flows: theory, algorithms, and applications, Prentice-Hall, Inc., Upper Saddle River, NJ, 1993
• 8: Dimitri Bertsekas , Robert Gallager, Data networks, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 9: Stephen Boyd , Lieven Vandenberghe, Convex Optimization, Cambridge University Press, New York, NY, 2004
• 10: D. P. Bertsekas, Nonlinear Programming, Athena Scientific, Belmont, MA, second edition, 1999.
• 11: Brian Towles , William J. Dally, Worst-case traffic for oblivious routing functions, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564872]
• 12: H. Kuhn, "The Hungarian method for the assignment problem," Naval Res. Logist. Q., vol. 2, pp. 83--97, 1955.
• 13: M. Beck and D. Pixton, "The Ehrhart polynomial of the Birkhoff polytope," to appear in Discrete Comp. Geom., arXiv:math.CO/0202267.
• 14: ILOG, Mountain View, CA, CPLEX 7.5 User's Manual, http://www.ilog.com.
• 15: A. Borodin , J. E. Hopcroft, Routing, merging, and sorting on parallel models of computation, Journal of Computer and System Sciences, v.30 n.1, p.130-145, Feb. 1985 [doi>10.1016/0022-0000(85)90008-X]
• 16: C. Kaklamanis , D. Krizanc , T. Tsantilas, Tight bounds for oblivious routing in the hypercube, Proceedings of the second annual ACM symposium on Parallel algorithms and architectures, p.31-36, July 02-06, 1990, Island of Crete, Greece [doi>10.1145/97444.97453]
• 17: W. A. Aiello, F. T. Leighton, B. M. Maggs, and M. Newman, "Fast algorithms for bit-serial routing on a hypercube," Mathematical Systems Theory, vol. 24, no. 4, pp. 253--271, 1991.
• 18: Arjun Singh , William J. Dally , Brian Towles , Amit K. Gupta, Locality-preserving randomized oblivious routing on torus networks, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564873]
• 19: Ted Nesson , S. Lennart Johnsson, ROMM routing on mesh and torus networks, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.275-287, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215455]
• 20: W. J. Dally , C. L. Seitz, Deadlock-free message routing in multiprocessor interconnection networks, IEEE Transactions on Computers, v.36 n.5, p.547-553, May 1987 [doi>10.1109/TC.1987.1676939]
• 21: Arjun Singh , William J. Dally , Amit K. Gupta , Brian Towles, GOAL: a load-balanced adaptive routing algorithm for torus networks, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 22: Farhad Shahrokhi , D. W. Matula, The maximum concurrent flow problem, Journal of the ACM (JACM), v.37 n.2, p.318-334, April 1990 [doi>10.1145/77600.77620]
• 23: L. Fratta, M. Gerla, and L. Kleinrock, "The flow deviation method --- an approach to the store-and-forward communication network design," Networks, vol. 3, pp. 97--133, 1973.
• 24: F. Ros Peran, Routing to minimize the maximum congestion in a communication network, Ph.D. thesis, MIT, 1978.
• 25: Allan Borodin , Jon Kleinberg , Prabhakar Raghavan , Madhu Sudan , David P. Williamson, Adversarial queuing theory, Journal of the ACM (JACM), v.48 n.1, p.13-38, Jan. 2001 [doi>10.1145/363647.363659]
• 26: M. Andrew , A. Goel , A. Fernández, Source Routing and Scheduling in Packet Networks, Proceedings of the 42nd IEEE symposium on Foundations of Computer Science, p.168, October 14-17, 2001
• 27: B. Awerbuch, Y. Azar, and S. A. Plotkin, "Throughput-competitive on-line routing," in Proc. of IEEE Symposium on Foundations of Computer Science, Palo Alto, CA, Nov. 1993, pp. 32--40.
• 28: Harald Räcke, Minimizing Congestion in General Networks, Proceedings of the 43rd Symposium on Foundations of Computer Science, p.43-52, November 16-19, 2002
• 29: Richard D. McBride, Progress Made in Solving the Multicommodity Flow Problem, SIAM Journal on Optimization, v.8 n.4, p.947-955, 1998 [doi>10.1137/S1052623496304542]
• 30: Naveen Garg , Jochen Koenemann, Faster and Simpler Algorithms for Multicommodity Flow and other Fractional Packing Problems., Proceedings of the 39th Annual Symposium on Foundations of Computer Science, p.300, November 08-11, 1998
• 31: Lisa K. Fleischer, Approximating Fractional Multicommodity Flow Independent of the Number of Commodities, SIAM Journal on Discrete Mathematics, v.13 n.4, p.505-520, Oct. 2000 to Nov. 2000 [doi>10.1137/S0895480199355754]
• 32: G. Birkhoff, "Tres observaciones sobre el algebra lineal," Univ. Nac. Tucumán Rev. Ser. A, vol. 5, pp. 147--151, 1946.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.2 ANALYSIS OF ALGORITHMS AND PROBLEM COMPLEXITY
      F.2.2 Nonnumerical Algorithms and Problems
          Subjects: Routing and layout

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Interconnection architectures (e.g., common bus, multiport memory, crossbar switch)

General Terms:
Algorithms, Performance

Keywords:
interconnection networks, multicommodity flows, oblivious routing