Forward Error Correction Code

The Forward Error Correction Code structural pattern is a derivative of the Redundancy architectural pattern and the Compensation strategy pattern in the original resilience design pattern specification (Fig. 32) [B24]. It offers detection, containment, and mitigation with continuous operatation in the presence of an error or failure, and with none-to-significant interruption and no loss of progress. The following describes the Pattern and its application in the System Scope and in the Service Scope of the INTERSECT federated ecosystem for instrument science. Note that the Pattern description uses the terms system, subsystem, and service in an abstract way, while the System Scope and the Service Scope map those terms to the INTERSECT federated ecosystem.

Pattern

Problem

A hardware error or subsystem failure due to a physical fault (e.g., wear-out or destruction) causes a software, such as a service, to experience an error and potentially a subsequent failure.

Context

The pattern applies to a system that has the following characteristics:

  • The system is deterministic, i.e. forward progress of the system is defined in terms of the input state to the system and the execution steps completed since system initialization.

  • The system state is represented using a sequence of symbols.

Forces

  • The pattern introduces an execution time and/or resource requirement (storage space, computational capability, etc.) penalty independent of whether an error or failure occurs during system operation or not.

  • The scope and strength of the redundancy employed by the pattern determine its execution time and resource requirement overhead.

  • The number of errors and failures that are detectable and correctable is limited by the amount of redundant information contained in the forward error correction code.

Solution

The pattern enables the continuous correct operation of a system impacted by an error or failure. It supports resilient operation by applying redundancy to system state and optionally to system resources. This redundancy is in the form of encoded system state. The pattern requires very well defined input and output to permit input encoding and output decoding. Input is encoded, processed redundantly in an encoded fashion by the system, and the output is then decoded. The decoding corrects an error or failure. The scope and strength of the redundancy are defined by the encoding/decoding.

Redundancy can be in time, meaning the same system resources process the encoded input in time. Redundancy can also be in space, meaning additional (redundant) system resources are used, such that the different system resources process the encoded input in space. Redundancy in time saves system resources, while redundancy in space offers more error/failure coverage. A mix between redundancy in time and space is possible as well, where there is more encoded system state than additional (redundant) system resources.

Encoding in its simplest form may be just repeating the input for redundancy in time, where the decoding just compares subsequent outputs. More involved encoding/processing/decoding schemes involve \(k\) information symbols and \(r\) redundant information symbols, where there may be less than, equal to or more than \(r\) symbols than \(k\) symbols. In the previously mentioned simplest form, the \(k\) and \(r\) symbols are the same and there may be 1 or more \(r\) symbols. The components of this pattern are illustrated in Fig. 54.

Forward Error Correction Code pattern components

Fig. 54 Forward Error Correction Code pattern components

Capability

A system using this pattern is able to continue to operate in the presence of an error or failure with no interruption. This pattern provides error and/or failure detection in the system by applying redundancy to system state in the form of encoded system state. The pattern provides mitigation of an error or failure in the system by applying redundancy to system state and optionally to system resources, such that the system continues to operate correctly in the presence of such an event. The flowchart of the pattern is shown in Fig. 55, the state diagram in Fig. 56, and its parameters in Table 11.

Flowchart

Fig. 55 Flowchart

State diagram

Fig. 56 State diagram

Table 11 Forward Error Correction Code pattern parameters

Parameter

Definition

\(T_{a}\)

Time to activate the redundant information storage

\(T_{en}\)

Time to encode the input for the (sub-) system

\(T_{ex}\)

Time to execute (sub-) system progress

\(T_{d}\)

Time to decode the output from the (sub-) system and detect

\(T_{c}\)

Time to correct using redundant information
Protection Domain

The protection domain extends to the encoded system state and to the system resources processing it.

Resulting Context

Correct operation is performed despite an error or failure impacting the system. Progress in the system is not lost due to an error or failure. The system is not interrupted during error/failure-free operation or when encountering an error or failure. Resource usage in time or space is increased according to the amount of redundancy employed in the form of encoded system state and due to the encoding of input and decoding and correction of output.

A trade-off exists between the amount of redundancy employed and the number of errors and/or failures that can be tolerated at the same time and/or in time. More redundancy tolerates generally more errors and/or failures, but requires either more resources or more execution time.

The pattern may be used in conjunction with other patterns that provide containment and mitigation in a complementary fashion, where some error/failure types are covered by the other pattern(s) and the pattern covers for the remaining error/failure types.

Performance

The error/failure-free free performance \(T_{f=0}\) of the pattern is defined by the task total execution time without any resilience strategy \(T_{E}\), the total time to activate the redundant information storage \(T_{a}\), the time to encode \(T_{en}\), and the time to decode and detect \(T_{d}\) with the total number of input-execute-output cycles \(P\).

\[\begin{aligned} T_{f=0} = T_{E} + T_{a} + P(t_{en} +t_{d}) \end{aligned}\]

The performance under errors/failures \(T_{f!=0}\) is defined by the failure free performance \(T_{f=0}\) plus the time \(T_{c}\) to correct using redundant information, where total time to correct using redundant information is the number of errors or failures \(N\) times \(T_{c}\). Assuming constant time to activate the redundant information storage \(T_{a}\), time to encode \(T_{en}\) (\(t_{en}\)), time to decode \(T_{d}\) (\(t_{d}\)), and time to correct \(T_{c}\), the performance under errors/failures \(T_{f!=0}\) can be further simplified using the mean-time to interrupt (MTTI) \(M\).

\[\begin{aligned} T_{f!=0} = T_{f=0} + \frac{T_{E}}{M} T_{c} \end{aligned}\]
Reliability

Given that the pattern enables the resumption of correct operation after an error or failure, the reliability of a system employing it is defined by errors and failures that are not handled by the pattern, such as failures of the persistent storage. The reliability after applying the pattern \(R(t)\) can be obtained using the performance under errors or failures that are handled as part of the protected the system \(T_{f!=0}\) and the assumed constant probabilistic rate \(\lambda_{u}\) of errors and failures of the unprotected part of the system that are not handled (or its corresponding inverse, the MTTI \(M_{u}\)).

\[\begin{aligned} R(t) = e^{-\lambda_{u} T_{f!=0}} = e^{-T_{f!=0}/M_{u}} \end{aligned}\]
Availability

The availability of the pattern can be calculated using the task’s total execution time without the pattern \(T_{E}\) and performance under errors/failures \(T_{f!=0}\). \(T_{E}\) is the planned uptime (PU) \(t_{pu}\). \(T_{f!=0}\) is the planned uptime (PU) \(t_{pu}\), the scheduled downtime (SD) \(t_{sd}\), and the unscheduled downtime (UD) \(t_{ud}\).

\[\begin{aligned} A = \frac{T_{E}}{T_{f!=0}} = \frac{t_{pu}}{t_{pu}+t_{ud}+t_{sd}} \end{aligned}\]
Examples

There are various schemes that enable forward error correction in memory devices, storage systems as well as communication channels. Based on time and space overhead constraints, schemes of different detection and correction capabilities are used. Popular examples include parity bits, checksums, Hamming codes, hash function codes. More elaborate schemes such as systematic cyclic block codes include binary Bose-Chaudhuri-Hocquenghem (BCH), Reed-Solomon, and cyclic redundancy check (CRC). Forward error correction can be found in storage systems with redundant array of independent disks (RAID), the InfiniBand interconnect [B58], the memory hierarchy [B59, B60], algorithm-based fault tolerance (ABFT) solutions [B61] and coded computing [B62].

Rationale

The pattern enables a system to tolerate an error or failure through continuation of correct operation after impact. It relies on system state redundancy in the form of encoded system state. The pattern performs mostly proactive actions, such as maintaining redundancy. Error or failure detection is part of the pattern in the form of output decoding. The pattern has high design complexity due to the need for encoding input, decoding output, and processing encoded system state.

System Scope

In the context of INTERSECT Systems, Subsystems, and Services, this pattern can be applied to INTERSECT systems and subsystems. It would be primarily applied to an entire infrastructure system and its subsystems, but it could also be applied an entire logical system that spans across multiple infrastructure systems. It could be applied to a logical subsystem of an infrastructure system only.

Service Scope

In the context of INTERSECT Systems, Subsystems, and Services, this pattern can be applied to an INTERSECT service. If it is applied to a group of services, then this is typically within the System Scope. However, it could also be applied to interconnected services, such as to services participating in the same campaign.

Microservice Scope

In the context of the INTERSECT Microservices Architecture, this pattern can be applied to an INTERSECT microservice. If it is applied to a group of microservices, then this is typically within the Service Scope.