The two dimensional mesh is widely considered to be a promising parallel ar
chitecture in its scalability. In this architecture, processors are natural
ly placed at intersections of horizontal and vertical grids, while there ca
n be three different types of communication links: (i) The first type is th
e most popular model, called a mesh-connected computer: Each processor is c
onnected to its four neighbours by local connections. (ii) Each processor o
f the second type is connected to a couple of (row and column) buses. The s
ystem is then called a mesh of buses. (iii) The third model is equipped wit
h both buses and local connections, which is called a mesh-connected comput
er with buses. Mesh routing has received considerable attention for the las
t two decades, and a variety of algorithms have been proposed. This paper p
rovides an overview of lower and upper bounds for algorithms, with pointers
to the literature, and suggests further research directions for mesh routi
ng.