A MDP Approach to Fault-Tolerant Routing

被引:3
作者
Pietrabissa, Antonio [1 ]
Castrucci, Marco [1 ]
Palo, Andi [1 ]
机构
[1] Univ Roma La Sapienza, Comp & Syst Sci Dept DIS, I-00185 Rome, Italy
关键词
Markov decision processes; routing; fault-tolerant; communication networks; stochastic control; AD HOC NETWORKS; MULTISERVICE NETWORKS; CAC; FRAMEWORK;
D O I
10.3166/EJC.18.334-347
中图分类号
TP [自动化技术、计算机技术];
学科分类号
0812 ;
摘要
This paper defines a theoretical framework based on Markov Decision Processes (MDP) to deal with fault-tolerant routing algorithms in heterogeneous networks, which are realized through the integration of assorted wired and wireless telecommunication technologies. Such kinds of networks are characterized by fast dynamics of link availabilities, mainly due to the extensive use of wireless technologies. The novelty of this paper is the formulation of the fault-tolerant routing problem as a MDP, which is used to compute the optimal re-routing policy As in existing fault-tolerant algorithms, when a path becomes unavailable, the traffic flows transmitted over that path are re-routed on another available path; the novelty is that the new selected path is the one that minimizes re-routing occurrences, since it is selected taking into consideration the probability that also the alternative paths can become unavailable in the future. As a by-product, the optimal path selection for new traffic flows is also obtained. Simulations show the effectiveness of the proposed approach.
引用
收藏
页码:334 / 347
页数:14
相关论文
共 50 条
[41]   Providing Fault-Tolerant Ad hoc Routing Service in Adversarial Environments [J].
Yuan Xue ;
Klara Nahrstedt .
Wireless Personal Communications, 2004, 29 :367-388
[42]   Evaluation of a Fault-tolerant WSN Routing Algorithm Based on Link Quality [J].
Burgos, Unai ;
Soraluze, Iratxe ;
Lafuente, Alberto .
SENSORNETS: PROCEEDINGS OF THE 4TH INTERNATIONAL CONFERENCE ON SENSOR NETWORKS, 2015, :97-102
[43]   An efficient fault-tolerant routing algorithm in NoCs to tolerate permanent faults [J].
Reza Akbar ;
Ali Asghar Etedalpour ;
Farshad Safaei .
The Journal of Supercomputing, 2016, 72 :4629-4650
[44]   Fault-tolerant routing algorithm for meshes without using virtual channels [J].
Chen, KH ;
Chiu, GM .
JOURNAL OF INFORMATION SCIENCE AND ENGINEERING, 1998, 14 (04) :765-783
[45]   An Efficient Placement and Routing Technique for Fault-Tolerant Distributed Embedded Computing [J].
Jafari, Roozbeh ;
Ghasemzadeh, Hassan ;
Dabiri, Foad ;
Nahapetian, Ani ;
Sarrafzadeh, Majid .
ACM TRANSACTIONS ON EMBEDDED COMPUTING SYSTEMS, 2009, 8 (04)
[46]   Fault-tolerant routing for wormhole routed two-dimensional meshes [J].
Avresky, DR ;
Cunningham, C ;
Ravichanran, H .
COMPUTER SYSTEMS SCIENCE AND ENGINEERING, 2000, 15 (06) :385-397
[47]   Dynamic Fault-Tolerant Routing Based on FSA for LEO Satellite Networks [J].
Lu, Yong ;
Zhao, Youjian ;
Sun, Fuchun ;
Li, Hongbo ;
Wang, Dianjun .
IEEE TRANSACTIONS ON COMPUTERS, 2013, 62 (10) :1945-1958
[48]   Preprocessing of Scenarios for Fast and Efficient Routing Reconfiguration in Fault-Tolerant NoCs [J].
Silveira, Jarbas ;
Marcon, Cesar ;
Cortez, Paulo ;
Barroso, Giovanni ;
Ferreira, Joao M. ;
Mota, Rafael .
23RD EUROMICRO INTERNATIONAL CONFERENCE ON PARALLEL, DISTRIBUTED, AND NETWORK-BASED PROCESSING (PDP 2015), 2015, :404-411
[49]   Providing fault-tolerant ad hoc routing service in adversarial environments [J].
Xue, Y ;
Nahrstedt, K .
WIRELESS PERSONAL COMMUNICATIONS, 2004, 29 (3-4) :367-388
[50]   An Enhanced Fault-Tolerant Routing Algorithm for Mesh Network-on-Chip [J].
Rezazadeh, Arshin ;
Fathy, Mahmood ;
Rahnavard, Gholamali .
2009 INTERNATIONAL CONFERENCE ON EMBEDDED SOFTWARE AND SYSTEMS, PROCEEDINGS, 2009, :505-+