ES2237346B2 - TOLERANT ROADING MECHANISM TO HIGHLY SCALABLE FAULTS. - Google Patents

Abstract

Highly scalable fault-tolerant routing mechanism called S-Immunet, which is characterized as an efficient mechanism to tolerate faults in interconnection networks of parallel and distributed computers. The mechanism is based, on the one hand, on a method of re-routing the messages when a network failure occurs and on the other hand, on a specific hardware structure of the message routing apparatus. The main differences with the previous fault tolerance mechanisms are that the invention can be applied to very large networks (thousands of nodes) of type k-ary n-cube; it does not produce an overload of the network in the absence of failure; automatic and transparent reconfiguration to the application; Once the components are repaired, the network performance is recovered before the failure and the new mechanism is also able to tolerate any number of link failures and any spatial and temporal combination of failures.

Description

Fault-tolerant routing mechanism highly scalable

Technical sector

The invention is related to the networks of interconnection of multiple computers (multicomputers or multiprocessors) and more specifically with fault tolerance that can occur in the networks that compose them.

State of the art

Achieving high availability rates is desirable goal in most computers. But nevertheless, achieve this goal in large parallel computers with tasks of critical character ceases to be an option to become a need. Any computer of this size must have efficient mechanisms to tolerate the occurrence of failures at all its levels, because the multiplicity of components increases by considerable way its mean time between failures (MTBF).

The context in which this invention focuses is on the interconnection subsystem. Fault tolerance problems within the interconnection network can be subdivided between errors or failures at the link level, errors at the router level and at the network level. We will focus on the network level. At this level, the fundamental problem is not related to the implementation techniques, as occurs in the other two levels, being a broader problem. When an interconnection network suffers a failure in one of its resources (links or nodes) immediately its topological properties are altered. This is not difficult to solve from the point of view of the routing mechanism used to bring the packets to their destination. However, that change affects other more subtle aspects. The most important is that the strategies used to avoid any possible failure in the fault-free network are no longer valid. Accordingly, after a failure in one component, even in networks with hundreds of thousands of components, it can be completely disabled. The type of anomaly most closely linked to the topological aspects is the blocking between packets or deadlock . The production of a deadlock in a part of the network as a result of the failure and subsequent invalidation of the mechanism for its avoidance can render the entire system useless.

This problem is not new and the solutions proposed by other authors go from eliminating those healthy resources that as a consequence of the failure can induce the deadlock [1], include new physical or virtual resources to solve the situation [2] - [10] or reconfigure suitably the topological information of the network using a sufficiently versatile deadlock avoidance mechanism. In [11] the authors of this invention proposed a new mechanism in this regard, called Immunet. Its main virtues were that it tolerated any spatio-temporal combination in failures, as long as the network remained connected.

However Immunet presents a series of deficiencies that make it almost impracticable when it comes to networks with tens of thousands of nodes. Loss of performance observed after a reduced number of failures tends to be high. This limited the applicability of the idea in large parallel supercomputers, which is where fault tolerance It makes more sense. The invention presented here, S-Immunet, It is an evolution of the mechanism that allows to achieve with total success a very low loss of performance at a very low cost.

The invention is based on the exploitation of the typical characteristics of the interconnection networks used in these systems. Just as Immunet's applicability was completely generic, S-Immunet specializes in k-ary n-cube networks. In this way, the new mechanism, in addition to dynamically tolerating the occurrence of network failures, achieves performance losses below 1% when used in a network with 1024 nodes with a single link failure (the best results they obtained them the old version that degenerated up to 15% with the same fault). Furthermore, the invention allows the dynamic recovery of the initial performance of the interconnection network when the repair is carried out. That is, once all the faults have been eliminated, the mechanism is able to detect the new situation and without stopping the execution of the applications that are running on the parallel machine, it can carry out the mentioned recovery.

[one]

NR Adiga , GS Almasi , and Aridor , M Bae , Rajkishore Barik , et al ., "An Overview of the BlueGene / L Supercomputer", Supercomputing \ underline {2002}.

[2]

RV Boppana and S. Chalasani . "Fault-tolerant wormhole routing algorithms for mesh networks". IERF, Trans. on Computers , vol. 44, no.7, pp. 848-864, July \ underline {1995}.

[3]

J. Bruck , R. Cypher , and C. Ho . "Fault-tolerant meshes with small degree". SIAM Journal of Computing , vol. 26, no. 6, pp. 1764-1784, December \ underline {1997}.

[4]

R. Casado , A. Bermudez , FJ Quiles , JL Sanches , and J. Duato , "Performance evaluation of dynamic reconfiguration in high-speed local area networks". International Symposium on High-Performance Computer Architecture (HPCA), January \ underline {2000}.

[5]

S. Chalasani and R V. Boppana , "Communication in Multicomputers with Nonconvex Faulty". IEEE Trans. on Computers , vol. 46, no.5, pp. 616-622, \ underline {1997}.

[6]

MS Chen and KG Shin , "Adaptive Fault-Tolerant Routing in Hypercube Multicomputers", IEEE Trans. on Computers , vol. 39, no.12, pp. 1406-1416, December \ underline {1990}.

[7]

D. Avresky , "Embedding and Reconfiguration of Spanning Trees in Faulty Hypercubes", IEEE Transactions on Parallel and Distributed Systems vol. 10 no.3, pp. 211-222, March \ underline {1999}.

[8]

M. Galles , "Spider: a high-speed network interconnect", IEEE Micro , vol. 17, no.1, pp. 34-39, Jan-Feb. \ underline {1997}.

[9]

PT Gaughan and S. Yalamanchili , "A Family of Fault-Tolerant Routing Protocols for Direct Multiprocessor Networks", IEEE Trans. on Parallel and Distributed Systems , vol. 6, no.5, pp. 482-497, May \ underline {1995}.

[10]

Rpang , T. Pinkston , "The Double Scheme: deadlock- free reconfiguration of Cut-through Networks", International Conference of Parallel Processing (ICPP) August \ underline {2000}.

[eleven]

V. Puente , JA Gregorio , F. Vallejo and R. Beivide , "Immunet: A Cheap and Robust Fault-Tolerant Packet Routing Mechanism". The 31st Annual International Symposium on Computer Architecture (ISCA2004), pp. 198-209, Munchen, Germany, June \ underline {2004}.

[12]

V. Puente , C. Izu , R. Beivide , JA Gregorio , F. Vallejo and JM Prellezo , "The Adaptive Bubble Router", Journal of Parallel and Distributed Computing . vol 61, no. 9, September \ underline {2001}.

Description of the invention Brief Description of the Invention

The invention, called S-Immunet, is an efficient mechanism for tolerating faults in interconnection networks of parallel and distributed computers. The mechanism is based, on the one hand, on a method of re-routing the messages when a network failure occurs and on the other hand, on a specific hardware structure of the message routing apparatus. The main differences with the previous fault tolerance mechanisms are that the invention can be applied to very large networks (thousands of nodes) of type k-ary n-cube and also the repair of the components is taken into account and the network performance before failure. The mechanism is capable of tolerating any number of link failures and any spatial and temporal combination of failures; After any failure, it allows an automatic reconfiguration to be carried out and is also transparent to the application that is being executed.
taking place in the multiprocessor system. The mechanism also does not cause network overload in the absence of failures.

Brief description of the content of the figures

Figure 1. Example of a broken link in a toroidal network (3-ary 2-cube).

Figure 2. Parent node and child nodes of node 5 after communication of the fault by node 4.

Figure 3. Road or "tour" along the tree and that will form the Ring or Safe Path.

Figure 4. Examples of use of the channels of first and second order escape over a two toroidal network dimensions.

Figure 5. Structure of the message router which can be used in the invention.

Detailed description of the invention

Before the appearance in the interconnection network of one or several link or node failures, S-Immunet allows the automatic obtaining of a "Ring" that covers all the nodes of the network and applying on it the technique known as Buffer Flow Control , BFC [12], said ring becomes a "Ring or Safe Path" so that any package reaches its destination in the presence of failures. The process of obtaining the Ring is carried out without throwing any package in transit.

The Safe Ring is obtained from the generation of a tree ( spanning tree ), which always exists embedded in any topology, and whose root is the node that detected the fault. Carrying out a "tour" (tour) along said shaft and applying on it the BFC mentioned technique ensures the existence of a Ring sure to exchange packets between all network nodes survivors.

The generation of the tree is carried out by means of a trivial process of diffusion ( broadcast ) to its immediate neighbors of the fault situation. With the response, or not, of its neighbors each node creates a provisional route table that allows the updating of the necessary route tables to support the topological change that has forced the failure.

For example, it is assumed that in the network of the figure 1 the link between nodes # 4 and # 1 has been broken and that node # 5 has received a failure notification from node # 4 (and therefore it has become its parent node) and its immediate neighbors # 3 and # 8 have responded to their remission (and have become their children ordered locally and arbitrarily). From that moment, the node # 5 only needs to remember which is corresponding port to the "father" in the tree and which of each of the "children", as shown in figure 2.

It is obvious that the path along the tree (figure 3) is generated without more than each node forwarding the packets applying the rules in table 1. In addition, any package injected on this path will reach its destination (although in the worst if you have to go through the entire ring).

TABLE 1 Rules for forwarding messages after the appearance of failures

packages coming from They must be sent to son i son i + 1 father Son 1 (first child) last child father ^ (1)} injection port father ^ (1)} adaptive channel father ^ (1)} (1) An exception is the root of the tree (has no father). Packages must be sent to the first child

Once each node has the necessary information to send packets to any other node in the network, the definitive route tables resulting from the new fault situation are updated and the sending of both new packets is carried out. generated by applications, such as those found in traffic queues ( buffers ) waiting for reconfiguration.

The ability to support any spatio-temporal combination of faults is achieved through the use of a unique fault identifier, EPL ( Emergency Priority Level ), generated with each new fault and dependent on the identifier (ID) of the node that detects it and the number of previous failures that node has supported until that moment. For example, in a network of N nodes, if a router whose identifier is ID = x detects a new fault, it will generate an EPL equal to tN + x , where t is the number of previous reconfigurations experienced by the node. Thus, the EPL value generated after the detection of a fault is always different and therefore a single tree is generated.

Although the methodology is completely general, when we have a network composed of thousands of nodes, the failure in a single component, or a few, (are the most likely situations) can cause a very marked performance degradation, as a consequence of the high length of the resulting Safe Ring. In addition, if the component is repaired, the mechanism is not able to recover the original malfunction free operation. By means of S-Immunet, these two problems are solved for networks of any size with a structure of the type k-ary n-cube .

The invention associates with the interconnection network Three different virtual networks. The first network is completely adaptive and with minimal routing. In the second virtual network, called "first-order virtual escape network", it it will assume that the network is free from failure, even if this is not true. Therefore, the packets in this network will be routed in dimension order (X, Y, Z, ..). In a fault situation it is impossible to get all traffic to reach its destination because the path in some dimension will be cut. When a package is find using this network reach a failed resource that prevents continue applying routing in order of dimension, it will be enabled to use the third virtual network, called "network second-order virtual escape. "In this network we will apply the Safe Ring described above as a mechanism to avoid blocking. Since we know that the second virtual escape network Order is lock free, regardless of configuration of failures, the entire network will be free from failure.

Under the conditions previously stated, it It has two virtual networks with the possibility of blocking and one third block free under any circumstances. The types of traffic that can be used by each of the three virtual networks and that the router will determine are the following:

-

The net Adaptive virtual is available for whatever type of traffic and its previous route.

-

The net First-order virtual escape is available to all those packages that have not found a bug on their way to destination, come from injection, from the adaptive virtual network or are advancing by herself.

-

The net Second-order exhaust may be used exclusively by the  packages that having previously circulated through the exhaust network of First order they found a resource in failure in their way.

Several examples of routes for different packages. This policy results extremely simple to apply and involves only a bit of package overload This type of allocation policy allows limit the application of the Safe Ring only to that traffic that is frontally with a resource in failure. When he number of resources in failure is relatively low, most of traffic will flow as if the network were free from failures. So, the loss of performance due to the Safe Ring is eliminated for the most part, as the number of packages that reach failures are reduced, being, consequently, the level of occupation of the second order exhaust network very small and making the Effect of the length of the Ring Sure is practically negligible.

In a fault-free situation it is not necessary apply any kind of additional mechanism to avoid blocking originally proposed in [12]. Applying routing in order of dimension in one of the three virtual networks that we have it is enough (the first order exhaust network). Exhaust network second order is used as a second adaptive channel additional.

Finally, the invention allows full recovery of performance after complete network repair. Thus, if we assume that a reconfiguration process is triggered in the network after any kind of reconfiguration, it is easy to determine if all the nodes of the network have all their links functioning. For a k-ary n-cube network , any of the fault-free routers must have 2 * n operational bi-directional links. Globally, the network must have 2 * n * k2 links in operation. Therefore, known the amount, called w, of operational links, the network will be free of failure if and only if w = 2 * n * k2.

W can easily be known during the updating of the tables in the reconfiguration process. Each node sends an update packet to its parent node with the sender node identifier, the EPL priority level and the number of links available on that particular node. Thus, the root node determines the number of correct links w. If w = 2 * n * k2, the root node sends a specific control packet along with the EPL level of the reconfiguration to its immediate children and they retransmit it to their children. Each node that receives this packet will discard the use of the Secure Ring and from then on it will use the resources previously dedicated to the second order exhaust network (Safe Ring) to route the packets adaptively. By repeating this process on all the nodes of the network, two adaptive channels will be available again and the original network performance will be restored.

Example of embodiment of the invention

For a better understanding of the invention, an application example is described below. Assume the existence of a network of interconnection of computers of the type k-ary n-cube as in Figure 1 but which may be composed of thousands of nodes or computational elements. Each of the routers that make up the network has a structure like the one in Figure 5. Three virtual channels (without failures, two will be adaptive and one escape), a switching or crossbar element that allows the interconnection of the inputs and Departures, as well as with the local computing elements. The selection of the input channels that will have access to the output channels is carried out by an Arbitrator. The Routing Unit (RU) would use two tables. A small one, indicating the ports that constitute the escape path at each moment (Escape Table) and the other table (Adaptive Table) will have an entry for each node of the network and will be used to route the messages depending on the node destination.

If a node wishes to send a message to another that is at a distance (\ Delta x , \ Delta y ) 5 it will use either of the two adaptive virtual channels (Adaptive Table). In case you cannot do it, you will try to enter the escape channel that will always follow a route in order of dimension (DOR). Ie first traverse the ring Xs while supplies this component address (the distance \ Delta x is 0), then continue through the corresponding ring to the axis of the Ys to destination (the distance \ Delta and is 0) . However, in your advance you will return to adaptive channels whenever you can.

If a router detects a failure in any of your links with a neighbor, enters a state of failure, stops communication with all other nodes, becomes the root node and, using the hardware lines, communicates it to its neighbors. These will interpret it as the beginning of a process of reconfiguration and after responding to the requirement they will be communicated to turn with its neighbors and so on until reaching the last node of the net. Each of the routers will point at their small table (Escape Table) what was the port through which he received the step-by-step failure requirement (parent node from then) and those of your neighbors have responded to yours (children nodes in the order of the response). After a short period of time, all routers have their little table, so that together form a tree (like the one in figure 3) whose root is the node that detected the failure. Therefore, any router that you want to send a package to any other, you have a way to do what. If also to introduce a new package in this way the condition of maintaining an additional gap is added, this path is  "safe," that is, mutual blockages cannot occur between packages. From this moment, in a simple process of diffusion, adaptive tables are updated again to have consider the topological change produced by the broken link.

From that moment on, if a node wishes to send a message to another that is at a distance (\ Delta x , \ Delta y ), just as when it is free of faults, it will use the only adaptive channel currently available to the router (Updated Adaptive Table). In case you can't do it, you will try to enter the first-order escape channel, which will always follow a DOR route as if there were no broken links. If on the DOR path the package encounters a broken link and therefore cannot move forward, it will now go to the second order escape route or Safe Ring that has just been created with the reconfiguration at the expense of one of the channels adaptive

Thus, with a small number of broken links, the performance degradation will be very small because most likely is that the package is not with the link in bad condition, greatly in networks with a large number of nodes which is also where more degradation occurs when the mechanism is not applied in  which is based on the invention that is being described.

If the broken link is repaired, there will be a reconfiguration process and during tables update communication is also carried out to the parent nodes of the links in correct condition, until you reach the root node that can Determine if all network links are free from bugs. Yes If so, it will issue a specific package to indicate all network nodes that from then on can reuse the second order escape channel as a second adaptive channel. That is, the original network performance is restored.

If during this or at any other time a new fault occurs, the existence of a unique identifier EPL guarantees a new and correct update of the tables of routing

Claims (5)

1. Highly scalable fault-tolerant routing mechanism that is characterized by its application, especially in regular direct networks of the large k-ary n-cube type and in which a message routing device is distinguished in each node network with table-based routing; a method to reroute messages based on the automatic creation of an escape path over a ring; and a method to recover network performance after the repair of failures. 2. Highly scalable fault tolerant routing mechanism according to claim 1, characterized in that the message routing device of each node consists of at least three virtual channels per physical channel. In the absence of failures two of the channels are used as adaptive and the third as deterministic. 3. Highly scalable fault-tolerant routing mechanism according to claim 1, characterized in that the routing device messages from each node in the presence of one or more faults automatically reassigns one of the adaptive channels to form part of a large ring that joins all the nodes of the network and that can be used as a second order escape channel. 4. Highly scalable fault-tolerant routing mechanism according to claim 1, characterized in that the method for re-routing messages, based on the automatic creation of an escape path over a ring, is carried out by creating a spanning tree composed of all the nodes of the network and whose root is the one that detected the fault. 5. Highly scalable fault-tolerant routing mechanism, according to claim 1, characterized in that the method for recovering network performance after fault repair is based on automatic communication to the root node, by any node of the network , of any repair detected.