Adaptive Fault-Tolerant Routing in 2D Mesh with Cracky Rectangular Model
This paper mainly focuses on routing in two-dimensional mesh networks. We propose a novel faulty block model, which is cracky rectangular block, for fault-tolerant adaptive routing. All the faulty nodes and faulty links are surrounded in this type of block, which is a convex structure, in order to a...
Saved in:
| Main Authors: | , , , |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Wiley
2014-01-01
|
| Series: | Journal of Applied Mathematics |
| Online Access: | http://dx.doi.org/10.1155/2014/592638 |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1832552129674346496 |
|---|---|
| author | Yi Yang Meirun Chen Hao Li Lian Li |
| author_facet | Yi Yang Meirun Chen Hao Li Lian Li |
| author_sort | Yi Yang |
| collection | DOAJ |
| description | This paper mainly focuses on routing in two-dimensional mesh networks. We propose a novel faulty block model, which is cracky rectangular block, for fault-tolerant adaptive routing. All the faulty nodes and faulty links are surrounded in this type of block, which is a convex structure, in order to avoid routing livelock. Additionally, the model constructs the interior spanning forest for each block in order to keep in touch with the nodes inside of each block. The procedure for block construction is dynamically and totally distributed. The construction algorithm is simple and ease of implementation. And this is a fully adaptive block which will dynamically adjust its scale in accordance with the situation of networks, either the fault emergence or the fault recovery, without shutdown of the system. Based on this model, we also develop a distributed fault-tolerant routing algorithm. Then we give the formal proof for this algorithm to guarantee that messages will always reach their destinations if and only if the destination nodes keep connecting with these mesh networks. So the new model and routing algorithm maximize the availability of the nodes in networks. This is a noticeable overall improvement of fault tolerability of the system. |
| format | Article |
| id | doaj-art-006d43c13492419b9f277e48f0188d09 |
| institution | Kabale University |
| issn | 1110-757X 1687-0042 |
| language | English |
| publishDate | 2014-01-01 |
| publisher | Wiley |
| record_format | Article |
| series | Journal of Applied Mathematics |
| spelling | doaj-art-006d43c13492419b9f277e48f0188d092025-02-03T05:59:26ZengWileyJournal of Applied Mathematics1110-757X1687-00422014-01-01201410.1155/2014/592638592638Adaptive Fault-Tolerant Routing in 2D Mesh with Cracky Rectangular ModelYi Yang0Meirun Chen1Hao Li2Lian Li3School of Information Science and Engineering, Lanzhou University, Lanzhou 730000, ChinaSchool of Applied Mathematics, Xiamen University of Technology, Xiamen 361024, ChinaLaboratoire de Recherche en Informatique, Bat 490, Universite Paris-Sud 11, 91405 Orsay Cedex, FranceSchool of Information Science and Engineering, Lanzhou University, Lanzhou 730000, ChinaThis paper mainly focuses on routing in two-dimensional mesh networks. We propose a novel faulty block model, which is cracky rectangular block, for fault-tolerant adaptive routing. All the faulty nodes and faulty links are surrounded in this type of block, which is a convex structure, in order to avoid routing livelock. Additionally, the model constructs the interior spanning forest for each block in order to keep in touch with the nodes inside of each block. The procedure for block construction is dynamically and totally distributed. The construction algorithm is simple and ease of implementation. And this is a fully adaptive block which will dynamically adjust its scale in accordance with the situation of networks, either the fault emergence or the fault recovery, without shutdown of the system. Based on this model, we also develop a distributed fault-tolerant routing algorithm. Then we give the formal proof for this algorithm to guarantee that messages will always reach their destinations if and only if the destination nodes keep connecting with these mesh networks. So the new model and routing algorithm maximize the availability of the nodes in networks. This is a noticeable overall improvement of fault tolerability of the system.http://dx.doi.org/10.1155/2014/592638 |
| spellingShingle | Yi Yang Meirun Chen Hao Li Lian Li Adaptive Fault-Tolerant Routing in 2D Mesh with Cracky Rectangular Model Journal of Applied Mathematics |
| title | Adaptive Fault-Tolerant Routing in 2D Mesh with Cracky Rectangular Model |
| title_full | Adaptive Fault-Tolerant Routing in 2D Mesh with Cracky Rectangular Model |
| title_fullStr | Adaptive Fault-Tolerant Routing in 2D Mesh with Cracky Rectangular Model |
| title_full_unstemmed | Adaptive Fault-Tolerant Routing in 2D Mesh with Cracky Rectangular Model |
| title_short | Adaptive Fault-Tolerant Routing in 2D Mesh with Cracky Rectangular Model |
| title_sort | adaptive fault tolerant routing in 2d mesh with cracky rectangular model |
| url | http://dx.doi.org/10.1155/2014/592638 |
| work_keys_str_mv | AT yiyang adaptivefaulttolerantroutingin2dmeshwithcrackyrectangularmodel AT meirunchen adaptivefaulttolerantroutingin2dmeshwithcrackyrectangularmodel AT haoli adaptivefaulttolerantroutingin2dmeshwithcrackyrectangularmodel AT lianli adaptivefaulttolerantroutingin2dmeshwithcrackyrectangularmodel |