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 Ω
INTRODUCTION
The routing of messages in a network is one of the most fundamental tasks in parallel and distributed systems. The number of edges between any two vertices in a network measures the cost of sending a message between them. Therefore, it is highly desirable to route along short paths. At each intermediate vertex, path information is needed to guide the message to the destination. The simplest approach to store this information is by maintaining a complete routing table at each of the n vertices, which gives for possible destination the name of the next vertex on a shortest path to the destination. This approach requires that n-1 items of routing information be stored at each vertex in the network, with each item being a vertex name. Therefore, a more compact way is needed for representing the routing table. One way to make the tables more compact is to establish some relation among the group of vertices associated with an edge (Tan and van Leeuwen, 1995). A well-known approach that has been used to compact such groups of vertices is Interval Routing Scheme (IRS).
Interval routing was introduced by Santoro and Khatib (1985). It has found industrial applications in the C104 Router Chip used in the (INMOS, 1991) T9000 Transputer design, (Welch et al., 1993) and is clearly reviewed by Gavoille (2000). This method assigns a distinct label from the set {0, ..., n-1} for each vertex. Each edge is labeled with a unique subinterval of the interval [0, n-1]. The set of intervals associated with the edges of a vertex must be disjoint and their union covers the interval [0, n-1]. In general, all subintervals can wraparound. This is denoted as IRS. As a result, a routing table of d entries is needed at a vertex, where d is the degree of the vertex. When a message with a destination x arrives at an intermediate vertex, a comparison between x and the vertex label is made. If they match, the message is consumed at the vertex. Otherwise, the local routing table is searched for the interval containing x and the corresponding edge is selected (Bakker et al., 1991).
The routing scheme is called optimal if the messages are routed along shortest paths. Hereafter, it refers to optimal IRS simply by IRS. The size of the routing tables could be reduced at the cost of increasing the lengths of the routing paths (Gavoille and Guevermont, 1998; Peleg and Upfal, 1989). If you allow multiple labels to be associated with every edge, then you have a multi-label interval routing scheme k-IRS, when there are at most k intervals per edge, k>0. This scheme Van Leeuwen and Tan (1987) deals with certain graphs that do not have optimal routing with one interval per edge (Kranakis et al., 1996), (1-IRS).
Another approach called Masked Interval Routing Scheme (MIRS), introduced by Luccio et al. (1998) makes interval routing more flexible and deals with networks that are difficult to deal with in IRS. MIRS introduced as a new interval routing scheme, where a mask is added to each interval to indicate particular subsets of consecutive labels.
In MIRS the labels can be consecutive in many different ways. According to MIRS an interval is expressed through three integers [Start, Stop, Mask],(S, T and M, for short).
| Table 1: | Three intervals in MIRS and their binary interpretation |
These three integers indicate the initial, final labels of the interval and its mask respectively. The three integers have to be represented in binary and the bits equal to 1 in the mask indicate that the bits in the corresponding positions of the start and stop labels remain unchanged for all the labels of the interval. For instance, the interval [0, 8, 2] specifies the labels 0, 1, 4, 5, 8, since S = 0000 (using four bits), T = 1000 and the mask M = 0010 means that the second less significant bit remains unchanged for all the labels of the interval; note that, by ignoring the second bit, all these numbers are consecutive. Significant results are shown in Table 1; several sets of intervals obtained with different masks (notice the masked bits are underlined).
By introducing the mask, a large variety of sets of consecutive labels can be obtained, thus, making interval routing more flexible. For example, using MIRS and labels of r bits and masks contain i ones, you can express 2i(ri) sets of 2r-i consecutive elements, where the bits in the non masked positions are all 0's in S and all 1's in T. To represent the intervals you need 3 log2n bits, where n is the number of the vertices of the graph, hence n-1 is the value of the maximum label.
This research shows that MIRS can be advantageously used in fault-tolerant butterflies with a harmless subset of faulty vertices.
MIRS ON BUTTERFLY NETWORK
The family of butterfly graph is well known (Leighton, 1992), a butterfly BF(n) consists of N = 2n (n+1) vertices arranged in 2n rows numbered from 0 to 2n-1 and n+1 levels (columns) numbered from 0 to n. Each vertex v is denoted by a pair of integers (i, j) indicating the level and the row of v, respectively. An edge connects two vertices (i, j), (h, k) if h = i -1 and j = k (straight edge) or the binary representations of j and k differ in the hth bit (cross edge). Figure 1 shows BF(3) with N = 23.4 = 32 vertices arranged in four levels numbered 0..3 and eight rows numbered 0...7 in binary.
The vertices are numbered from 0 to N-1 level by level, from right to left. In fact, a vertex (i, j) is labeled with the integer formed by the concatenation i j, with i represented in decimal and j represented in binary as jn jn-1…j1. For example, vertex (2, 5) of BF(3) is labeled 2101.
| Fig. 1: | Butterfly BF(3) with N = 23, 4 = 32 vertices. The four dark vertices form the interval [2001, 3011] |
The reason for this mixed representation is to enhance readability, taking into account that only the bits of j will be masked and need to be explicitly indicated under the compact notation with underlining for mask. For example, the interval [2001, 3011] with two masked bits specifies the four vertices 2001, 2011, 3001, 3011 in BF(3). The four dark vertices in Fig. 1 form the interval [2001, 3011].
To apply MIRS to the butterfly you first need to determine a shortest path between any two vertices S, T, or better the initial edge of such a path which leaves S and whose associated interval contains T. Let S and T be labeled by san…a1 and tbn…b1 respectively. Let e1, e2, e3, e4 be the edges leaving S, where e1, e2 are the straight and cross edges from level s to level s-1 (for s>0) and e3, e4 are the straight and cross edges from s to level s+1 (for s<n), respectively. These edges are shown in Fig. 2 for vertex 1100. For an…a1≠ bn…b1, let r be the smallest value i for which ai ≠ bi; and let l be the greatest value i for which ai ≠ bi. The following lemma detects the first edge of a shortest path between S and T as a function of s, t, r, l. The proof easily follows from known properties of the butterfly.
Lemma 1: In BF(n) there exists a shortest path between two arbitrary vertices S and T with the following first edge f(S,T):
| Fig. 2: | The shortest path between S = 1100 and T = 3111 is shown with darkened lines in butterfly BF(3) |
Lemma 1 covers all the possible situations for S and T. In particular, for
s = 0, e1 and e2 are undefined and the comparison between
as and bs does not apply (cases-1 and 2). For s = n, e3
and e4 are undefined and the comparison between as+1 and
bs+1 does not apply (cases-3 and 4). For example let S = 1100 and
T= 3111 in BF(3), as shown in Fig. 3. You have s = 1, t =
3, r = 1, l = 2 and case-1 applies with as ≠ bs. Then
f(S,T) = e2 and the shortest path between S and T proceeds. The shortest
path between S and T is shown with darkened lines. Now, it can be shown how
to construct efficient MIRS on butterflies. For a bit x, let
Theorem 1: for any vertex S labeled san…a1 in BF (n), MIRS can be built as follows:
Proof: Intervals on e1. The intervals grouped under 1.1 are built according to case 1 of lemma-1 with as = bs. In fact, all destination vertices T labeled tbn…b1, with t≥s≥r and bs= as, are reached through e1. For any value of r such vertices have br ≠ ar and br-1…b1=ar-1…a1, which implies that the values ar¯ ar-1...a1 and as are fixed for all these vertices, while the other bits take all possible values. By the label structure, for any given value of r all the destinations T from an interval masked in positions s, r, r -1, ..., 1.
The interval marked 1.2 is built according to case 2 of lemma-1 with as = bs. All the destination vertices T with s>t, s≥ l and bs = as, are reached through e1. These vertices share with S all the bits in positions n, n-1, …, s, hence they form an interval masked in such positions.
The proof for the intervals on e2, e3 and e4 proceeds by similar inspection. In particular the intervals marked 2.1 and 2.2 are respectively built according to cases-1 and 2 of lemma-1, with as≠bs; the intervals marked 3.1 and 3.2 are built according to cases 3 and 4 of lemma-1, with as+1=bs+1; and the intervals marked 4.1 and 4.2 are built according to cases 3 and 4 of lemma-1, with as+1≠bs+1.
Consider BF(4) in Fig. 3, only the upper half of the graph (rows 0000 to 0111) is shown. According to Theorem-1, the intervals on the edges leaving from vertex S labeled 30110 are the following:
| • | Intervals on e1: | α = [30101, 41111], β
= [30100, 41100], γ = [00100, 20111] |
| • | Intervals on e2: | δ = [30000, 41011], ε = [00000, 20011] |
| • | Intervals on e3: | φ = [30110, 40110] |
| • | Intervals on e4: | ι = [01000, 21111], ω = [31110, 41110] |
Note that there are three intervals on e1, with the ones denoted by α and β corresponding to group 1.1 Theorem-1 (we have s-1 = 2 intervals) and γ corresponding to 1.2. There is only one interval φ on e3, corresponding to 3.2 and including S (see observation-1). The intervals grouped under 3.1 in the theorem are defined for s + 2 ≤ n, hence do not exist here because you have s = 3 = n-1. All the vertices in intervals γ, ε and φ belong to the upper half of the butterfly.
| Fig. 3: | MIRS for vertex 30110 in BF(4) according to Theorem-1 |
The vertices in the other intervals are splitted between the two halves of the graph, except for the ones in ι that are fully contained in the lower half.
As already mentioned, the butterfly requires Ω
Corollary 1: BF(n) admits a MIRS with n intervals.
Proof: The number of intervals on edge e1 is s - 1 + 1 = s ≤ n, where the maximum occurs for the vertices at level n. Similarly, the number of intervals on edge e3 is n-(s+2)+1+1= n-s ≤ n, where the maximum occurs for the vertices at level 0. Finally, only two intervals are present on edges e2 and e4. Recalling that BF(n) has N = 2n(n+1) vertices, from corollary-1, an upper bound of O(log N) intervals per edge can be immediately derived.
Observation 1: The interval marked 3.2 in Theorem-1 includes the label san…a1, that is it includes S. In general this is not a drawback because S is never searched for from S itself. If this is not acceptable, it can be shown that interval 3.2 can be broken into O(log N) disjoint intervals not including S. The upper bound of O(log N) intervals per edge still holds.
The use of an increased set of labels can be applied to particular sub-graphs of a butterfly, to maintain a low number of intervals per edge. First note that BF(n) includes 2n-r smaller butterflies BF(r), 0≤r≤n-1, which occupy the levels 0 to r of BF(n), (Fig. 3).
| Fig. 4: | Extended butterfly BF(3,1) with increased set of labels {0000, ..., 3111} pertaining to BF(3) |
The vertices of each sub-graph BF(r) are identified by constant values of the row-label bits jn…jr+1 (the upper BF(1) in BF(3) is identified by the bit values j3j2=00). Two BF(r) are adjacent if their vertices have the same values of jn…jr+2 (The upper two BF(1) in BF(3) are adjacent, since they are identified by j3=0). An extended butterfly BF(n,k), 0≤k≤n-1, is obtained by removing from BF(n) some non-adjacent sub-graphs BF(r) with possibly different values r≤k. The extended butterfly BF(3,1) shown in Fig. 4 is obtained from BF(3) removing two sub-graph BF(1) and one sub-graph BF(0) consisting of the single vertex 0011. Note that each vertex of BF(n, k) maintains the leaving edges e3, e4, but edge e1, or e2 may be missing. This happens for the critical vertices, that is the ones for which an adjacent vertex of BF(n) has been removed (all the vertices of level 2 in Fig. 4).
For BF(n,k),an increased set of labels is adopted. The same set of labels of BF(n) with the vertices of BF(n,k) maintaining the labels of the corresponding vertices of BF(n) and the unused labels being dummy. Consider now two arbitrary vertices u, v of BF(n,k) and the minimal path π from u to v in BF(n) determined by the routing intervals of Theorem-1. If all the edges of π are present in BF(n,k), then this path will also be adopted in the routing of BF(n,k). If instead, going from u to v along π, we encounter a vertex z that is critical in BF(n,k) and π proceeds through the missing edge e1 (respectively e2), we must change the path. It is easy to verify that there is another minimal path π' in BF(n) that goes along e2 (respectively e1) and is totally contained in BF(n,k). The π' is adopted in the routing of BF(n,k). Now, it is not difficult to verify that the following construction generates valid MIRS intervals for BF(n,k):
| • | For each non-critical vertex, build the intervals on e1, e2, e3 and e4 as for the corresponding vertex of BF(n) |
| • | For each critical vertex with missing edge e1, build the intervals on e2, e3 and e4 as for the corresponding vertex of BF(n) and add on e2 the intervals 1.1 of Theorem-1. The interval 1.2 is ignored, because is entirely composed of dummy labels |
| • | For each critical vertex with missing edge e2, build the intervals on e1, e3 and e4 as for the corresponding vertex of BF(n) and add on e1 the interval 2.1 of Theorem-1. The interval 2.2 is ignored, because is entirely composed of dummy labels |
In Fig. 4, edge e1 from vertex 2000 is missing, then the interval α = [2001, 3101] is attached to e2 (α is the only interval in the set 1.1, see Theorem-1 with s = 2). Edge e2 from vertex 1010 is missing, then the interval β = [1001, 3111] is attached to e1.
Corollary 2: BF(n,k) admits a MIRS with n+1 intervals.
Proof: Immediately from the procedure above. The number of intervals on e1, for missing e2, or on e2, for missing e1, assumes maximum value n +1 for s = n in Theorem-1.
RECONFIGURATION ALGORITHM
The reconfiguration procedure for the 1-MIRS in the presence of faults can be derived as follows: Let X be any vertex with standard binary label xk-1...x0 and Y be another vertex with standard binary label yk-1...y0 adjacent to X. Assume that vertex Y belongs to the harmless subset of vertices F, which is now failed. Now we can rearrange the intervals of the edges leaving X to cope with this new situation. Let j be the bit position at which X and Y differ. Considering first the right-most bit of X, x0, we assign the interval [xk-1...... x'0, xk-1 ... x'j... x'0, 1…101…1], where the 0 is at bit position j, to edge (X- xk-1..... x'0). Secondly, consider x1 and assign the interval [xk-1...... x'1x0, xk-1... x'j... x11, 1…101…10], where the 0’s are at bit positions j and 0, to edge (X- xk-1...... x'1x0). Now consider x2 and assign the interval [xk-1...... x'2x1x0, xk-1... x'j ... x'211, 1…101…100], where the 0’s are at bit positions j, 0 and 1, to edge (X-xk-1...... x'2x1x0). Similarly on all other bits I=3,…,k-1 except where i = j to obtain the remaining intervals. The pseudo-code for the reconfiguration procedure is given:
Algorithm reconfigure (Y):
The algorithm is clearly very efficient and can be executed independently and in parallel, by each vertex X, provided that X knows the identity of a faulty neighbor Y (if any) and there is a global guarantee that the faults belong to a harmless set of vertices. Obviously, it can be seen that the algorithm takes O(k) since all the bits of X will be processed (except the bit at which X differs from Y) and the standard binary label for any vertex is k bits.
CONCLUSIONS AND FUTURE RESEARCH
This research reviews the new technique of Masked Interval Routing Scheme (MIRS),
which was introduced with the aim of compressing the routing tables stored in
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 Ω
This study shows that MIRS may be advantageously used in fault-tolerant networks, proving that optimal routing with one interval per edge is still possible in Butterflies with a proper subset of faulty vertices. This research gives the algorithm needed to reconfigure the intervals in the presence of faults in Butterfly networks. Further research needed in the reconfiguration problem of faulty networks considering different topologies. The definition of a harmless subset of faulty vertices should be generalized.