Abstract:
This research shows that Butterfly networks can be fault-tolerant
using Masked Interval Routing Scheme (MIRS). The MIRS was introduced with the
aim of compressing the routing tables in a network. It was shown that MIRS could
drastically reduce interval information stored in networks such as globe and
hypercube graphs, compared to the classical Interval Routing Scheme (IRS). In
Butterfly graphs of O(N) vertices the number of intervals per edge goes down
from Ω in IRS to
O(logN) in MIRS. This research shows that MIRS may be advantageously used in
Butterfly networks, proving that optimal routing with one interval per edge
is still possible with a harmless subset of faulty vertices. This research gives
an optimal algorithm to reconfigure the intervals in the presence of faults.
Subscribe Today 
in IRS to
O(logN) in MIRS. This research shows that MIRS may be advantageously used in
Butterfly networks, proving that optimal routing with one interval per edge
is still possible with a harmless subset of faulty vertices. This research gives
an optimal algorithm to reconfigure the intervals in the presence of faults.
