Method for quick reconfiguration of routing in the event of a fault in a port of a switch

Method of rapid reconfiguration of a routing on failure of a port of a switch

TECHNICAL FIELD OF THE INVENTION

The invention relates to a method of rapid reconfiguration of a routing failure of a port of a switch. More specifically, the invention relates to a method for rapid reconfiguration of a routing on failure of a port of a switch of a network of computing nodes.

[0002] In this document, the expression “failure of a port” will be understood to mean the change of state of a port. Such a change of state occurs, for example, for a failure of the port, but also for a failure of a hardware or logical element connected to the port, such as a cable or even a logical link.

[0003] In the context of this document, the term “computing node network” will be understood to mean any network of machines, a machine being at least one of: a computer, a server, a blade, etc. Are particularly aimed at clusters of servers , that is to say supercomputers or high performance computers. The field of high performance computing referred to as HPC is also targeted.

STATE OF THE PRIOR ART

[0004] As the size of the supercomputers increases, the topologies of the corresponding networks become more complex as they become denser. As the frequency of network failures is a function of the number of devices, this frequency is increasing. At the same time, computing equipment becomes denser so that the number of cores per processor and the number of processors per computing node increase. Therefore, the impact of a failure, even classic, or even expected, such as an interconnection cable failure is likely to affect a very large number of applications and lead to failure of their execution. These critical occurrences are to be avoided, and yet they are bound to increase by the conjunction of the two factors exposed: increase in the sizes of interconnection networks and densification of computing resources.

[0005] The technical problem is based on a temporal problem. It is driven by an optimization problem which aims to minimize the reaction time from detection of the failure to its circumvention. After a reaction time defined by application criteria, a parallel program will fail. However, if a workaround is found and deployed before this period expires, the outage will be invisible to affected applications. The action lever acts on routing, ie the calculation and use of the routes that a message must follow on a network to reach its destination. A recalculation operation must be launched to take the failure into account and bypass it, in order on the one hand to give the support teams time to intervene and on the other hand to minimize the disruptive impact of the failure.

The increase in the size of network topologies and the number of equipment capable of sending messages pushes the existing routing algorithms to their limits. Their complexity explodes their computing time and makes their reaction time go beyond the allowable reaction time.

[0007] Current supercomputers manage their routing, and therefore re-routing operations, centrally: a single server is responsible for retrieving the state of the topology as well as the consequent routing decisions. This is for example the case with "OpenSM", a daemon used by Infiniband networks. This centralized approach does not extend to the scale of the exaflops, or even that of the fifty or so petaflops. This was also the case with the MCP software component of the Myrinet networks. None of these solutions:

does not scale;

does not offer the possibility of offering a fast rerouting.

[0008] It is indeed necessary to centralize the topology on a single point of the network, then to perform a global calculation before redeploying the updated routing tables.

DISCLOSURE OF THE INVENTION

[0009] The present invention offers a solution to make it possible to drastically reduce the recovery times on failure, falling below the detection threshold of calculation applications. The types of failures covered range from the loss of a link to the loss of a router. The effectiveness of the remediation depends on the high-performance topology and the position of the fault.

The invention implements a distribution as close as possible to the re-routing operation which allows scaling up and obtaining a solution that works both on existing scales and on scales. to come up. However, this distribution, if it involves the expected confrontation with the problems inherent in the domain, should also ideally be done as close as possible to the failure, ie within the router. This implementation as close as possible to the failure allows the detection-action time to be reduced to its minimum but only offers very limited resources, reducing the field of action of the algorithms. However, it makes it possible to provide the applications with routing continuity which avoids the faulting of said applications.

The invention is a method that can be executed directly on the control cards associated with each switch of a network. These cards are on-board computers of modest size, which are responsible in particular for communication with a management network, error handling and the routing tables.

Without any information other than those accessible locally, that is to say the availability of the ports, the method according to the invention is capable of re-calculating a routing, by replacing the routes which used a faulty port with a new functional road. This local information is partial, but it is sufficient to set up a functional rerouting, in most cases.

In this design, one aspect of the invention relates to a method of rapid reconfiguration of a routing on failure of a port of a switch comprising a plurality of ports, a persistence memory for persisting corresponding data to a routing table and a working memory for working on data corresponding to a routing table characterized in that it comprises the following steps:

Emission of a first fault notification message,

Autonomous update of the routing data only in the working memory by replacing an identifier of the failed port by an identifier of a functional port, the identifier of the functional port being selected locally,

Emission of a second message indicating the update of the table.

In addition to the main characteristics which have just been mentioned in the previous paragraph, the method / device according to the invention may have one or more additional characteristics among the following, considered individually or according to the technically possible combinations:

it also includes the following steps:

Receipt (1040) of a routing table update message,

Using (1050) data from the routing table update message to update the working memory and the persistence memory, such updates being consistent with the data in the update message.

the functional port identifier used for the update is selected from a set formed by functional port identifiers of the plurality of ports the functional port identifier used for the update is randomly selected.

the functional port identifier used for the update is selected as a function of a counter corresponding to a number of updates performed.

the functional port identifier used for the update is selected according to a predetermined rank in a list of port identifiers.

a list of ports used to select the functional port identifier is sorted.

the sorting criterion is the load of the ports.

The invention also relates to a digital storage device comprising a file corresponding to instruction codes implementing the method according to a combination of the preceding characteristics.

The invention also relates to a device implementing the method according to a combination of the preceding characteristics.

BRIEF DESCRIPTION OF THE FIGURES

Other characteristics and advantages of the invention will emerge on reading the following description, with reference to the appended figures, which illustrate:

FIG. 1, a view of a switch implementing a method according to the invention;

FIG. 2, an illustration of steps of the method according to the invention.

For greater clarity, identical or similar elements are identified by identical reference signs in all of the figures.

The invention will be better understood on reading the following description and on examining the accompanying figures. These are presented as an indication and in no way limit the invention.

DETAILED DESCRIPTION OF AN EMBODIMENT

In Figure 1 is illustrated a device on which the invention can be implemented. Figure 1 shows a switch 100 comprising:

a microprocessor 110;

a working memory 120, also called random access memory or RAM; a persistence memory 130, that is to say a memory capable of saving data even in the absence of power supply, typically a flash memory is used, more rarely an SSD or conventional hard disk;

a management port 140, in general this is an Ethernet port;

a plurality 150 of 150.i operating ports, in general these are InfiniBand ports.

The microprocessor 110 of the switch 100, the working memory 120 of the switch 100, the persistence memory 130 of the switch 100, the management port 140 of the switch 100 and the plurality 150 of operating ports of the switch 100 are interconnected by at least one bus 160. When action is taken to a device, this is in fact performed by a microprocessor of the device controlled by instruction codes stored in a memory of the device. If an action is assigned to an application, the latter is in fact carried out by a microprocessor of the device in a memory of which the instruction codes corresponding to the application are recorded.

FIG. 1 shows that the persistence memory 130 comprises at least one area 130.1 routing table comprising a plurality of routing records. A routing record is made up of at least two fields:

A destination identifier field, a port identifier field.

A switch receives messages through one port and does not retransmit them to another port. This other port is determined by increasing at least one characteristic of a message with the records of the routing table. A message is at least characterized by recipient information. This recipient information is used to find a record in the routing table. The record found makes it possible to determine via which port the message must be re-sent.

Figure 1 shows that the working memory 120 has several areas including at least:

a zone 120.1 routing table, this is a copy of the routing table of the persistence memory, accesses to this working memory are fast but this working memory is not capable of saving data without power supply, the microprocessor therefore loads the data from the persistence memory into the working memory, in the same way when the processor wishes to record data in the persistence memory, it first writes it in the working memory;

a port status zone 120.2 in which port status records are recorded, a port status record comprising at least two fields:

A first port identifier field,

A second port status field, a status being chosen from the list made up of at least: “operational”, “down”.

It is noted here that a port can be down for various reasons:

Fault at the port,

Fault in a cable connected to the port,

No cable,

... The list is not exhaustive.

Figure 2 shows a preliminary step 1000 in which a failure occurs at a port 150.i of the plurality 150 of ports. Such a failure causes, in a known manner, the implementation, by the switch 100 of a signaling step 1010. The present invention modifies this signaling step to add branching instructions to steps specific to the invention. A failure, or failure, can be due to the port itself, but also to a cable in connection with the port, to another port in connection with the port, to a link failure, that is to say a problem of software making the port unusable ... the list is not exhaustive

In step 1010 of signaling the switch 100 produces and sends a first signaling message via the management port 140. The first signaling message is a message according to the SNMP protocol (Simple Network Management Protocol), for example a TRAP or INFORM message. The payload of this first message includes at least one identifier of the switch and an identifier of the failed port of the switch. In the signaling step 1010, the switch also updates the status zone 120.2 of the working memory to write there the “failed” status in the record corresponding to the failed port.

From step 1010 the switch then goes to a step 1020 for updating the routing data in the working memory. This step is said to be autonomous because it only uses local data, that is to say recorded in memories of the switch and especially data produced by the switch.

In the step 1020 of updating the routing data, the switch searches in the routing table area 120.1 of the working memory of the switch for routing records comprising the identifier of the faulty port in their identifier field of destination.

For each of the records found, the switch replaces the value of the identifier of the faulty port with a value of an identifier of an operational port. This update is therefore done in the working memory of the switch. This update will not propagate into switch persistence memory. This means that if the switch reboots, this update will be lost. This is a temporary update, but quickly completed.

In some switches, a routing table also exists in a memory of a specialized circuit. This specialized circuit, dedicated to routing management, is used for performance reasons. This specialized circuit then has its own copy of the routing data. For such a switch, in step 1020, the routing data of the dedicated circuit is also updated. The memory of such a specialized circuit is not persistent. Such an update is therefore temporary.

The value of an operational port can be selected in several ways. A first mode of selecting a value is to choose the same value for all the updates. This selected value is then, for example:

The first operational port identifier value found in the zone

120.2 of switch working memory port statuses. In this case, the switch sequentially goes through the records in zone 120.2 of statuses of the ports of the working memory of the switch and stops as soon as it finds one whose status field is “operational”. The record identifier value is then used for all updates.

The nth operational port identifier value found in the zone

120.2 of switch working memory port statuses. In this case, the switch sequentially goes through the records of zone 120.2 of statuses of the ports of the working memory of the switch and stops as soon as it has counted N records whose status field is “operational”. The identifier value of the record on which the counting stopped is then used for all the updates. The value of N is predetermined or chosen randomly by a pseudo-random function implemented by the switch.

A second mode of selecting a value is to choose a value depending on the updated record. In this mode, the updates are counted as they are carried out via a counter, a value is selected according to the first selection mode by using the nth value, N being the value of the counter. The port identifier value therefore changes for each new update.

Whatever the mode of selection of an operational port, it is noted that the search can be restricted to a subset of the available operational ports. Such a subset is predetermined, for example by parameterization, and makes it possible to speed up the selection or to ensure greater relevance of the selected port.

A notable difference between the first and second modes for selecting an update value is that in the second mode the value for the update is calculated for each update. The modes for selecting an update value are not the only ones possible.

In a variant of the invention, the data of the zone is sorted

120.2 of port statuses before browsing it, a sorted list is thus obtained which can be browsed according to at least one of the modes described. Sorting is done for example according to the port identifier, another sorting is done according to the status of the port, yet another sorting is done according to port load information. Such load information is obtained by browsing the 120.1 routing table area and aggregating the port identifier, which makes it possible to obtain, for each port identifier, the number of occurrences in the 120.1 zone. . This number of occurrences is the load of the port. In a variant of a sorting by the port load, each modification of the routing table zone 120.1 is considered in order to recalculate, at the time of the modification, the load of the port concerned, which modifies the sorting for any subsequent modifications.

So if we consider a variant sorted according to the load and predetermined rand equal to one, we will always select the least loaded port.

It is clear that in the operations described, the faulty ports are ignored.

In another variant, which can be combined with the previous ones, only a subset of ports is considered for the selection of the functional port identifier. We therefore perform a pre-selection. In particular, this pre-selection makes it possible to exclude, for example, the downlink ports. The fact that a port is downlink is a characteristic of the port which is recorded, for example, as a type field in the port status field 120.2. Thus, for each port, additional characteristics can be managed. The typical characteristic is entered by configuration when the switch 100 is fitted.

Thus a set of ports in which an identifier is selected is, for example:

the set of all the functional ports a subset of the set of all the functional ports according to a predetermined criterion such as the type of the port.

The step 1020 for updating the routing data in the working memory is followed by a step 1030 for sending a second signaling message via the management port 140. The second signaling message is a message according to the SNMP protocol, for example a TRAP or INFORM message. The payload of this second message includes at least one identifier of the switch and a description of the modifications made to the routing data in the working memory.

The first signaling message and the second signaling message are sent to a management server, not shown. The management server uses the payloads to calculate new routing information before issuing this new routing information to the switch that issued the signaling messages.

Without the invention, the management server only has a faulty port identifier. With the invention he also knows what modifications have been made by the rapid correction made by the switch. It can therefore take these modifications into account in its calculation. One such consideration is:

A validation, that is to say the modification is good and therefore there is no reason to transmit it again,

A correction, that is to say the rapid correction carried out is not optimal and it must be corrected.

Once it has been calculated, the management server sends a message for updating the routing information to the switch. Such an update message is a response to the reporting messages. The production of such a routing information update message takes, with or without the invention, at least ten seconds, but this time generally exceeds one minute for very large topologies, that is to say topologies of more than 50,000 compute nodes.

In a step 1040 of receiving a message for updating a routing table, the switch 100 receives the message produced by the server. Such a message is usual for a switch. The processing of such a message consists in using the data of the message to update the routing data in all the memories of the switch using this data. In our example, this includes working memory and persistence memory. After processing this update message, if the switch reboots, the failed switch will be properly taken into account. The correction was persisted.

In the case of implementation has been described a switch managing routing data via two memories. The invention remains valid for a switch using more memory. For example, it is possible that the microprocessor 110 of the switch 100 is a specialized circuit comprising a dedicated ultra-fast memory in which it stores routing information. In this case, the invention makes it possible to rapidly update the dedicated memory but neither the working memory nor the persistence memory. It is also possible to update only the dedicated memory and the working memory. The principle of the invention is to update only the memories involved in the routing operations, that is to say the memories used by the microprocessor to determine a route.

Thus with the invention, these partial repairs are not intended to be optimal. The modes presented will succeed in forwarding traffic arriving from downlink ports but cannot act upstream to prevent traffic that descended through a fallen port from continuing to be routed. In all cases, a more complete update will follow, calculated by a routing module of the management server.

Also, the modifications carried out by a rapid repair according to the invention are not stored in the persistence memory: they are temporary.

This rapid repair nevertheless makes it possible to prevent application faults at the level of computing nodes connected to the switch.