Sui, Pao-HwaPao-HwaSuiSHENG-DE WANG2009-03-042018-07-062009-03-042018-07-06200001678191http://ntur.lib.ntu.edu.tw//handle/246246/142288https://www.scopus.com/inward/record.uri?eid=2-s2.0-0034159220&doi=10.1016%2fS0167-8191%2899%2900113-1&partnerID=40&md5=d149d63a552b33838ff37c89fd670371We investigate fault-tolerant routing schemes which aim at using low number of virtual channels in wormhole-routed mesh networks. The faults under consideration are rectangular block faults, which are suitable for modeling faults on board level in networks with grid structures. There is no restriction on the number of faults. The concepts of f-ring and f-chain are used in our scheme. Messages are routed minimally when not blocked by faults and are routed along the boundaries of the faults encountered. Only three virtual channels and local knowledge of faults are required for our routing scheme to be correct, deadlock- and livelock-free. By allocating virtual channels to messages carefully, all virtual channels have the potential to be used by messages; hence, none of the virtual channels and its associated hardware is wasted.application/pdf148695 bytesapplication/pdfen-USAlgorithms; Communication channels (information theory); Computer networks; Computer system recovery; Fault tolerant computer systems; Parallel processing systems; Theorem proving; Deadlock free; Mesh networks; Virtual channel; Wormhole routing; Data communication systemsjournal article10.1016/S0167-8191(99)00113-12-s2.0-0034159220http://ntur.lib.ntu.edu.tw/bitstream/246246/142288/1/21.pdf