Abstract: Mesh network is studied early and it is still one of the most important and attractive network models at pre-sent.Because of its simple,regular and scalable structure,and it is useful for the implementation of VLSI (Very Large Scale Integrated Circuit),Mesh network has not only become the basic model of many theoretical studies,but also the topology structure of many large multiprocessor and parallel computer systems.A mesh with m rows and n columns is denoted by M_m,n.In this paper,we gave the shortest routing algorithm under two different kinds of faulty area.1)We gave a routing algorithm to find the shortest path between any two fault-free nodes in M_m,n with m≥3 and n≥3,and calculated the length of the path obtained by the algorithm when there is a rectangular faulty region.2)We gave a routing algorithm to find the shortest path between any two fault-free nodes in M_m,n with m≥3 and n≥3,and calculated the length of the path given by the algorithm when there exists such a situation that a node and its k-hop neighbours are faulty.

Key words: Shortest routing algorithm,Fault-tolerant routing algorithm,Mesh network