—Reliability is an important aspect of operating safety-critical applications of networked systems, such as in avionics. In order to ensure sufﬁcient reliability, one approach is to apply redundancy. However, redundancy may be costly if the degree of redundancy is too high. This paper proposes an optimization-based framework for guaranteeing the desired reliability of any graph-based networked system. It focuses on integrated modular avionics architecture, based on the use of minimally redundant components. This framework consists of two steps. The ﬁrst is to compute the minimum number of components within the architecture, using a geometric program. The second is to determine the topology with the minimal number of connections between these components, using a signomial program. Finally, the method is illustrated on a small example network and a larger network of the A350 avionics architecture. Index Terms —reliability, redundancy, optimization, signomial, networked system, integrated modular avionics I. I NTRODUCTION An integrated modular avionics (IMA) architecture in a commercial aircraft usually consists of several end-system devices (ES), i.e., core processing input/output modules (CPI- OMs), common remote data concentrators (CRDCs), line replaceable units (LRUs), and Ethernet switches, connected in a network scheme called an avionics full duplex switched Ethernet (AFDX) network [1], [2]. In addition to the AFDX network, there are three additional architectures, i.e. ARINC 429, MIL-STD-1553B, and ARINC 629, used in the aircraft [3]. However, they are the federated architecture implemented in aircraft developed before the 2000s and unlikely to continue their service in modern aircraft. Additionally, their network topology is linear, which entails that the reliability may simply be analyzed using an equation for a series system. Thus, the AFDX network, which is applied to modern aircraft like A350, is the sole focus of this paper. The AFDX network can be considered as a safety-critical networked system, in which its continuity of service is required in the presence of ES or component failures [4]. The capability This effort has been funded in part by SAFRAN, KAUST, and by the National Science Foundation, Grants CNS 1544332 and 1446758. T. Khamvilai and E. Feron are with King Abdullah Uni- versity of Science and Technology, Thuwal, Saudi Arabia, fthanakorn.khamvilai,eric.feron g[at]kaust.edu.sa A. A. Syed is with Georgia Institute of Technology, Atlanta, GA, USA, asyed36[at]gatech.edu J. B. Mains is with Yamaha Motor Corporation, Kennesaw, USA, bmains16277[at]gmail.com L. Sutter is with Safran Electronics and Defense, Massy, France, sut- ter.louis[at]gmail.com P. Baufreton, F. Neumann are with Safran Electronics and Defense, Massy, France, fphilippe.baufreton, francois.neumann g[at]safrangroup.comof the network to satisfy this requirement is usually quantiﬁed by its probability of maintaining its intended function, also named reliability. Network reliability may be evaluated by modeling the system as a probabilistic graph [5], where each vertex represents a single component or subsystem, and each edge represents communication, or the ﬂow of information between vertices. Both vertices and edges are also associated with a component-level reliability, which can be obtained from their speciﬁcation of failure rate or maintenance schedule. Then, the reliability of a system is interpreted as the probabil- ity that a vertex set of interest is properly connected through available edges. To ensure that the evaluated system reliability is above a given level, more vertices and edges can be added to the network graph. However, having too much redundancy poses impracticalities due to several constraints, for example, the prices of components, the physical distance between two ES constrained by the size of the aircraft, the communication bandwidth of an Ethernet cable, and the aircraft maximum gross weight. Therefore, it is necessary to formulate an opti- mization problem which minimizes the cost of the network, while guaranteeing the desired reliability. In this paper, a two-step framework for solving this prob- lem is proposed. The ﬁrst step is to leverage Geometric Programming (GP) [6] to determine the minimal number of redundant components that satisfy the required reliability. Hence, this step is referred to as a redundancy optimization. In the next step, by using Signomial Programming (SP), the minimum number of connections among these components can be computed, to form the network architecture, which maintains the same required reliability. This is effectively a topology optimization problem. Both methods are in the form of mixed-integer mathematical programs, which offer beneﬁts of using readily available solvers, e.g., GPkit [7] and Mosek [8], to determine their globally optimal solution, and providing a ﬂexibility to introduce other relevant constraints, such as a common cause failure [9] or a bandwidth constraint [10]. The justiﬁcation for the two-step formulation arises from the inherent traceability of the problem. Such a formulation mitigates issues with the unstructured nature of the one-step formulation and subsequent difﬁculties associated with solving the problem. Several works on redundancy optimization are studied in [11]. Recent developments in meta-heuristic approaches are presented in [12], [13]; however, these methods cannot guar- antee the solution to be globally optimal as opposed to exact methods as in the case of GP. The formulation of GP in the ﬁeld of reliability has been introduced in [14]–[16]. However, 2 the formulation in [14] only yields an approximate solution. The formulation in [15] is only valid for a system connected in series. Lastly, although the formulation in [16] solves the previously mentioned issues, it does not consider the cost of establishing connections between redundant components. For the topology optimization, there also exist meta- heuristic methods [17]–[19] for solving the problem. On the contrary, some exact methods, such as dynamic programming [20], and best-ﬁrst search approach [21], can provide global optimality, however, they are not as robust to the introduction of new constraints. The proposed method of SP has been applied to many engineering applications, for instance, aircraft design [22], propulsion system sizing [23], circuit design [24], and wireless communication systems [25]. However, its application to topology optimization is seemingly novel. The remainder of this paper is organized as follows. Section II introduces relevant mathematical background. Section III describes the formulation for the redundancy optimization problem as a mixed-integer GP. Section IV contains the formulation of a mixed-integer SP for a topology optimization problem, and proposes the algorithm and its implementation, to obtain a globally optimal solution. Section V presents an example inspired by the A350 IMA architecture. Section VI summarizes the contributions and discuss the future works. II. M ATHEMATICAL BACKGROUND A. Network Model The network model is an undirected graph, G= (V;E), whereVrepresents a set of vertices, and EVV represents a set of edges. Let M=jVjandN=jEjbe the number of vertices and the number of edges, respectively. Each vertex,vi2Vhas a reliability, ri2[0;1]; i2f1;:::;Mg deﬁned as a probability of failure nonoccurence. Similarly, each edgeej2Ehas a reliability of rj2[0;1]; j2 fM+ 1;:::;M +Ng. Depending on the system behavior, the value of riandrjcan be either constant or evaluated at a speciﬁc point in time. In this paper, the network can remain functional in the presence of failures of its vertices and edges, should the vertices which provide different functionality to the network remain connected. For example, consider an A350 AFDX network comprised of two redundant networks, with seven switches each [3], [26] as shown in Figure 1. Assume that all functionalities provided by these components are equally important. All ES can be considered as vertices, and Ethernet cables as edges. If PRIM1A ,FMC1 , and the Ethernet cable between switch 1and switch 2fail, the network is still functional, as there exist other redundant ES which can provide the same functionality to the network. On the other hand, if SCI fails, the entire network also fails. B. Reliability Evaluation The probability that determines whether a network is func- tional deﬁnes its reliability. Assuming the failures of all vertices / edges are independent, the reliability equation of the network can be written R(r;G) =X y( (y)M+NY i=1h (1ri)(1yi) +riyii) (1) Fig. 1: A350 AFDX network (Left). Green boxes represent Line Replaceable Units (LRUs). Yellow boxes represent Core Processing Input/Output Module (CPIOMs). Orange boxes represent Common Remote Data Concentrator (CRDCs). Blue boxes represent Ethernet switches. Blue lines represent Ethernet cables. See [27] for abbreviation. A350 AFDX Network with only Ethernet switches (Right). whereR(r;G)2[0;1], and the binary vector y= [y1;:::;yM+N]T2f0;1gM+Nrepresents the state of vertices and edges where yi= 1means active . The binary Boolean function :f0;1gM+N!f0;1grepresents the state of the network where (y) =( 1if the network is functional 0otherwise(2) To evaluate (1) with a linear time complexity, an approach that involves representing (y)as a Binary Decision Diagram (BDD) is used and described in the following section [28]. C. Binary Decision Diagram A Binary Decision Diagram (BDD) is a Directed Acylic Graph that consists of a hierarchy of nodes that have two branches, a low-branch and a high-branch, pointing to their lower-hierarchical nodes. The two lowest hierarchy nodes with nooutgoing branches are called terminal nodes , labeled by either?or>. The highest hierarchy node with no incoming branches is called the root node . The BDD expands the solution of (2) in form of a binary tree. The details of constructing a BDD for the given network can be found in [29]–[31]. An example of a simple network and its BDD is given in Figure 2. In order to distinguish between the network and the BDD, the words vertices and edges are used for the network, and the words nodes and branches are used for the BDD. The structure of the BDD is represented as a set of nodes B= fb1;:::;bB;b?;b>g, whereB=jBj 2represents the size of the BDD and the ordering of b1;:::;bBis in the topological order, such that b1is the root node. The following deﬁnitions represent the relationship between network vertices/edges and BDD nodes/branches. Deﬁnition II.1. Given a networkGand its correspond BDD of a sizeB, the function ve:B ! f V[Egrepresents a mapping from the node to its correspond vertex or edge. Deﬁnition II.2. Given a networkGand its correspond BDD of a sizeB, the function lo=hi:N!Nrepresents a mapping from the index of the node to the index of its lower-hierarchy node that corresponds to its low / high-branches. 3 (a) Network with each vertex having different functionality. (b) Corresponding BDD. Fig. 2: An example network (2a), and its BDD (2b). Deﬁning II.1 and II.2, facilitates representing the Boolean function (y)as a recursive equation (yjyj) = (:yj^ (yjyj0))_(yj^ (yjyj1)) (3) wherej=ve(bi),j0 =ve(blo(i)), andj1 =ve(bhi(i))for i2f1;:::;Bgandj; j0; j12f1;:::;M +Ng. To determine whether the network is functional ( (y) = 0 , or (y) = 1) for a given vector y, (3) may be simply evaluated from the root nodeb1down to the terminal node b?orb>. At a particular nodei, ifyj= 0, the termyj^ (yjyj1)is always false and can be ignored. Similarly, for yj= 1. The network is functioning if the nodeb>is reached. To recursively evaluate the network reliabilityR(r;G), substitution of (3) into (1) yields Ri(r;G) = (1rj)Rlo(i)(r;G) +rjRhi(i)(r;G)(4) wherej=ve(bi)fori2f1;:::;Bgandj2f1;:::;M + Ng. By using dynamic programming (DP), (4) can be com- puted, as described in Algorithm 1 with a complexity of O(B). Algorithm 1: DP for Reliability Evaluation Input: network BDD, Reliability of vertices / edges Output: Reliability of the Network 1R? 0:0; R> 1:0 2Fori=B;B1;:::; 1 3Ri (1rve(i))Rlo(i)+rve(i)Rhi(i) 4ReturnR1 The following subsections introduce the mathematical pro- gramming techniques that will be used for formulating the optimization problems. D. Exponential Cone Programming Deﬁnition II.3. An exponential cone is deﬁned as a convex subset of R3of the form Kexp= (x1;x2;x3)jx2expx3 x2 x1 [f(x1;0;x3)jx10;x30g(5)Deﬁnition II.4. An exponential cone program refers to a convex optimization problem that has at least one exponential conic constraint, i.e. (x1;x2;x3)2Kexp. E. Geometric Programming Deﬁnition II.5. A monomial function is a function, f: Rn ++!Rdeﬁned by f(x) =cQn i=1xai iwhere x= [x1;:::;xn]T,c>0, andai2R. Deﬁnition II.6. A posynomial function is a function, f: Rn ++!Rdeﬁned by f(x) =P iciQn j=1xaij jwhere x= [x1;:::;xn]T,ci>0, andaij2R. Deﬁnition II.7. A geometric program (GP) is an optimization problem of the form minimize xf0(x) subject tofi(x)1; gi(x) = 1(6) wherefiare posynomial and giare monomial. The problem (7) is generally not convex; however, it is possible to do a log-transformation to turn it into a convex program that guarantees a solution which can be found in polynomial time, i.e. a globally optimal solution [6]. F . Signomial Programming Deﬁnition II.8. A signomial function is a function, f: Rn ++!Rdeﬁned by f(x) =P iciQn j=1xaij jwhere x= [x1;:::;xn]T,ci2R, andaij2R. Deﬁnition II.9. A signomial program (SP) is an optimization problem of the form minimize xf0(x) subject tofi(x)1; gi(x) = 1(7) wherefiare signomial and giare monomial. In general, solving an SP involves approximating a sig- nomial function as a monomial function, in which the SP becomes a GP, then iteratively solving the approximated problem, resulting in a locally optimal solution [6]. III. R EDUNDANCY OPTIMIZATION This section addresses an optimization problem for de- termining the minimum number of redundant components required to construct an initial network topology, under the constraint that its reliability be above a certain value. A. Problem Description Consider a system of Ifunctionally-different subsystems. Each subsystem has Ji,i2 f1;:::;Igcomponents. To mitigate the effects of a common cause failure, components in the same subsystem are assumed to be functionally-similar, meaning that they provide the same functionality, but differ in other features. The example are hardware from different manufacturers, or software compiled by different compilers or written by different teams. As illustrated in Figure 3, the connection of functionally-similar components can be assumed 4 to have a parallel network structure because the system can still provide the continuity of service if one or more, but not all, of these components fail. Otherwise, they are in a series network structure. Fig. 3: A conﬁguration of a series-parallel system. Given the reliability of each component, rijwherej2 f1;:::;Jig, the overall reliability of the series-parallel net- work may be calculated using a special case of an equation (1) [32]. B. Problem Formulation Consider the same system in III-A, where each component is associated with a component weight, wij>0and a connec- tion pricewij;kl>0if the connection between the component ijandklis required; otherwise, wij;kl = 0 . Further, let n2NIJwhereJ= maxiJi, be a decision matrix that determines the level of redundancy for each component in each subsystem (the number of components), and rbe the desired reliability of the overall system. Then, the optimization problem for minimum redundancy can be cast as minimize n2NIJIX i=1JiX j=1 wijnij+1 2IX k=1JkX l=1wij;klnijnkl! subject toIY i=12 41JiY j=1(1rij)nij3 5r:(8) The objective function is to minimize the total cost of the system, where the factor1 2accounts for the duplicate between the connection from the component ijtokland fromkltoij. For the case where ij=kl,wij;kl is set to zero, meaning that there is no connection to the same component. Although this problem is in the form of a mixed-integer nonlinear program, it can be reformulated into a form similar to a mixed-integer GP by exponentiating the objective function and performing appropriate change of variables, i.e., pij= log(1rij), nij;kl=nijnkl,n()= log y() , and ^yi1QJi j=1ypij ij. minimize ^yi;y()IY i=1JiY j=1 ywij ijIY k=1JiY l=1ywij;kl 2 ij;kl! subject to r IY i=1^yi!1 1;^yi+JiY j=1ypij ij1 log(yij;kl) = log(yij) + log(ykl) 8i;k2f1;:::Ig;8j;l2f1;:::;Jg(9) Because of the last constraint, this problem is not in the form of a GP; however, its integer relaxation can still be convertedinto a convex optimization problem. By applying the log- transformation to the objective function and constraints, and lettingz()= log n() ,^zi= log(^xi), this problem becomes minimize n();z();^ziIX i=1JiX j=1 wijnij+1 2IX k=1JkX l=1wij;klnij;kl! subject to log(r)IX i=1^zi0 log2 4exp(^zi) + exp0 @JiX j=1pijnij1 A3 50 zij+zklzij;kl= 0;exp z() n() 8i;k2f1;:::;Ig;8j;l2f1;:::;Jg(10) The last inequality constraint is the convex relaxation of its equality constraint and is equivalent to n();1;z() 2Kexp. Despite, in theory, the convexiﬁed problem provides the lower bound in terms of the cost value to the original problem, solving (10) using a high performance solver, e.g. Mosek [8] together with a branch-and-bound method for integer variables, in practice, provides the solution closed to the case where the constraint is not relaxed as shown in Section V. Once the level of redundancy of components is determined, these redundant components can be considered as vertices of the network, with fully-connected edges between subsystems. C. Additional Constraints for Common Cause Failures Since some of decision variables in the problem (10), i.e.nij, have the same physical interpretation as those in the problem (8), any additional mixed-integer constraints, whose relaxation is convex which depends on these decision variables can be included. For example, a boundary constraint for satisfying the allowable minimum and maximum number of components, or a modulo constraint for specifying the number of components to be even or odd [33]. Another useful constraint is one that handles common cause failure on redundant components. The analysis result of common cause failures from [34] may be summarized as “for a given ratio of the failure rates between a single component and its redundant system, using one component may, on average, provide a longer continuity of service than the redundant one if the number of redundant components is lower than some value.” Mathematically, this is translated to nij( = 1 ifnij<Lij Lijotherwise(11) whereLijis a lower bound for each component obtained from a method presented in [34]. By applying a Big- Mmethod, the additional constraints are nijLij+Mbij (12) nij1 +M(1bij) (13) whereMis a sufﬁciently large positive number, and bij2 f0;1gis an extra decision variable indicating either (12) or 5 (13) is active. If bij= 1, the inequality constraint nij1 is active, which suggests that it is not beneﬁcial to use a redundancy to improve the system reliability, and vice versa. IV. T OPOLOGY OPTIMIZATION In section III, it was shown that the network reliability can be improved using redundancy. However, it is advantageous in terms of both price and maintenance costs if the network is modiﬁed to contain fewer edges, whilst maintaining the desired reliability with the same number of vertices. Hence, this section addresses the problem of determining an optimal topology, in which the number of edges is minimized under a given reliability requirement. A. Problem Formulation Given a BDD of size Bencoding an initial network topol- ogy graph,G= (V;E), and its connectivity, the problem can be formulated as an SP. Let M=jVj,N=jEj,rbe the desired network reliability and x= [x1;:::;xM+N]T2 f0;1gM+Nbe a decision vector for determining whether a vertexvi2V,i2 f1;:::;Mgor an edge ej2E, j2fM+1;:::;M +Ngshould be kept (xi= 1) or removed (xi= 0) . Additionally, denote the corresponding weights, w= [w1;:::;wM+N]T, and reliability, r= [r1;:::;rM+N]T, for each vertex and edge. The reliability equation (1) may then be expressed as R(x;r;G) =X y( (y)M+NY i=1h (1rixi)(1yi) +rixiyii) (14) Furthermore, with the notions of BDD as described in II-C, equation (14) can be reformulated as a recursive equation Ri(x;r;G) = (1rjxj)Rlo(i)(x;r;G) +rjxjRhi(i)(x;r;G)(15) wherej=ve(bi)fori2f1;:::;Bgandj2f1;:::;M +Ng. To evaluate (15), we may again leverage Algorithm 1 by multiplying rwithx, which implies that the reliability of the removed vertex or edge is set to zero. The resulting equation is signomial in x. Considering each Rias an intermediate variable, the optimization problem may then be cast as an integer signomial program (SP). 8i2f1;:::;Bg; j=ve(bi); j2f1;:::;M +Ng minimize x;Riz=wTx subject toRi(1rjxj)Rlo(i)+rjxjRhi(i) R1r;x2f0;1gM+N(16) To determine a globally optimal solution to this problem, x, the branch-and-bound based approach can be used [35], [36]. However, this approach requires a valid upper bound, u, and lower bound, l, of the objective value for each iteration, which may be obtained via relaxations of the original problem (16).B. Integer Relaxation for Upper Bound Computation The upper bound of the objective value can be computed by relaxing the integer constraints, solving the following SP problem, and rounding the result to 0or1[37]. 8i2f1;:::;Bg; j=ve(bi); j2f1;:::;M +Ng minimize x;Riu=wTx subject toRi(1rjxj)Rlo(i)+rjxjRhi(i) R1r;0x1 xk=k8k2f1;:::;jjg(17) whereis a set of indices indicating which element of the decision vector xshould be ﬁxed during the branching process, andk2f0;1g. C. Signomial Relaxation for Lower Bound Computation To compute the lower bound, the convex relaxation of (16) must be approximated [37]. To do so, each signomial constraint is under-approximated by a polynomial function as follows. Each signomial constraint can be written as fi(x;R) =Rlo(i)rjxjRlo(i)+rjxjRhi(i) Ri1 =)Rlo(i)R1 i+rjxjRhi(i)R1 i 1 +rjxjRlo(i)R1 i1(18) Therefore, an under-approximation of fi(x;R), may be found by computing an over-approximation of the denom- inator. The following proposition provides such an over- approximation in the form of a monomial function. Proposition 1. Given a function f: [0;1]m(0;1]n!R+of the formf(x) = 1+cQm i=1xiQm+n j=m+1x1 jwherec>0, the tightest monomial over-approximation, in the L2-norm sense, off(x)is given by ~f(x) = (1 +c)m+nY j=m+1x1 j Proof. See Appendix.  Hence, by applying Proposition 1 with m= 2,n= 1, and c=rj, the relaxed problem becomes a GP of the form 8i2f1;:::;Bg; j=ve(bi); j2f1;:::;M +Ng minimize x;Ril=wTx subject toRlo(i)+rjxjRhi(i)1 +rj R1r;0x1 xk=k8k2f1;:::;jjg(19) which may then be transformed into a convex optimization problem and solved for the lower bound. 6 Algorithm 2: Mixed-Integer SP Algorithm for Reliability-Constrained Optimization Problem Input: BDD representing the network, Reliability and weight of vertices / edges, Desired reliability Output: x;z 1z wT1+ 1 2  u l None 3S U L ? 4Whilez>wT1 orS6=? 5IfS6=? 6; S1; S SnS1 7u U1; U UnU1 8l L1; L LnL1 9Iflis None or lmaxuU 10U Ufug; L Lflg 11 xu;u solve (17) 12 xl;l solve (19) 13 If xu2f0;1gM+Nandu<z 14 x xu; z u 15 Else if 0xu1 or 0xl1 16 IflmaxuU 17 s arg maxxfxj0<x<1g 18  s 19 S Sf(;0);(;1)g 20 U Ufu;ug; L Lfl;lg 21Return x;z D. Algorithm for Reliability-Constrained Optimization The Algorithm 2 is based on a standard branch-and-bound method [38] with the upper bound and lower bound being a solution from integer-relaxed problem (17) and a convex re- laxation obtained from the transformation of (19), respectively (which becomes convex upon making a change of variables). The heuristic used in this algorithm is to choose the element of xclosest to one as a branching variable, since such variables are more likely to be a vertex / an edge that cannot be removed from the network. Hence, the branch where this variable is ﬁxed to zero is likely to be infeasible and immediately fathomed. Theorem 1. Given the problem formulation of reliability- constrained optimization for networked systems as (16), the branch-and-bound based algorithm 2 provides a globally optimal solution through relaxation problems (17) and (19). Proof. See Appendix.  V. N UMERICAL EXAMPLES This section provides applications of the proposed methods on a small network of mobile robots with a hardware imple- mentation, and on a larger network of A350 IMA architecture. A. Small network of mobile robots Consider two types (pink, and green) of mobile robots collaborating as a network of two components, as shown in Figure 4a. Each robot has a different functionality. Assumethat the ﬁrst robot has a reliability of 0:8, whereas the second has a reliability of 0:7. Additionally, let the reliability of the wireless communication between a pair of robots be 0:9. Suppose further that the desired reliability of the network is 0:8. It is obvious that this requirement is not satisﬁed by the two-robot conﬁguration. Therefore, the method proposed in section III is used to improve the network reliability. To this end, the method proposed in section IV is used to optimize the topology. (a) two functionally different robots. (b) Resulting Network from (20). Fig. 4: Network of Mobile Robots. 1) Redundancy Optimization: Following the description in section III, this problem has two functionally-different subsys- tems, each with a single component. Taking all the weights to be unity, the optimization problem (10) can be expressed as minimize ^z1;^z2; n11;n21;n11;21; z11;z21;z11;21n11+n21+n11;21 subject to log(0:8)^z1^z20 log [exp(^z1) + exp (log(0 :2)n11)]0 log [exp(^z2) + exp (log(0 :3)n21)]0 z11+z21z11;21= 0 exp (z11)n11;exp (z21)n21 exp (z11;21)n11;21(20) wheren11andn12indicate the number of robots for each type. The results of (20) are provided in Table I and Figure 4b. Note that there are only fully-connected communications between functionally-different subsystems. Following the cor- respond BDD in Figure 5, the reliability of the network is 0:8559 , which is higher than the desired reliability. TABLE I: Optimization Result of (20) ^z1 ^z2 n11 n21 n11;21 z11 z21 z11;21 -0.0408 -0.0943 2 2 4 0.693 0.693 1.386 2) Topology Optimization: To further optimize the network in Figure 4b, its corresponding BDD (Figure 5) is used for formulating a problem. With all weights set to 1, the 7 optimization problem (16) can be written as minimize x2f0;1g4;R2R16 +x1+x2+x3+x4 subject toR10:8 R10:2R4+ 0:8R2; R2(10:9x1)R3+ 0:9x1R6 R30:3R8+ 0:7R5; R40:3R9+ 0:7R7 R5(10:9x2)R7+ 0:9x2R11; R60:3R8+ 0:7 R70:3R13+ 0:7R10; R8(10:9x2)R9+ 0:9x2R16 R90:7R12; R10(10:9x3)R12+ 0:9x3R15 R110:3R13+ 0:7; R120:8R14 R130:9x3R15; R140:9x4 R150:8; R160:7 (21) The optimization result of (21) is shown in Table II and Figure 6. Note that because the number of vertices has been determined by (20), there is no need to consider vertices as decision variables. The result shows that e1 can be removed, while the reliability of this ﬁnal conﬁguration (0:8062) still remains higher than the desired reliability. Fig. 5: BDD corresponds to the network in Figure 4b. TABLE II: Optimization Result of (21). variable x1 x2 x3 x4 R1 value 0 1 1 1 0.8062 variable R2 R3 R4 R5 R6 value 0.8351 0.8351 0.6905 0.9014 0.9041 variable R7 R8 R9 R10 R11 value 0.7704 0.6804 0.504 0.792 0.916 variable R12 R13 R14 R15 R16 value 0.72 0.72 0.9 0.8 0.7 3) Hardware Implementation: An experiment has been conducted on a swarm robotics platform [39] to illustrate the obtained result. The objective of this experiment is to simulate the failure of the networked system over time. This means thatwhen failure occurs on one or more components such that the entire system fails, data will be recorded, and the system will be repaired, such that it may continue operating. Then, from the recorded data, the overall system reliability can be shown to converge to the reliability obtained from (21), i.e., 0:8062 . In this setup, the robot network is moving along a rectangu- lar trajectory, where each corner is marked by G 1-G4as shown in Figure 6. To evaluate the reliability, at each time step the component-level reliability are evaluated to determine whether the vertices (robot) or edges (communication between robots) are available. If not, those vertices or edges are removed from the network for a brief ﬁxed interval, immobilizing the disconnected robot. After the interval has passed, the faulty vertices and edges are recovered. Then, the overall reliability is re-evaluated for the next time step. This experiment procedure is summarized in Algorithm 3. Algorithm 3: Procedure for Estimating System Re- liabiliy in Example V-A Input: The number of time steps T, The number of robotsM, The number of communication pairs N, Reliability of each robot rrobot, and each communication pair rcomm Output: Estimated System Reliability R 1R 0,nf 0 2Fort= 1 :T 3a 0M1,b 0N1 4Fori= 1 :M+N 5x U(0;1) 6 IfiMandrrobot<x 7 ai 1 8 bcommunication pair connected to robot i 1 9 Ifi>M andrcomm<xand biM= 0 10 biM 1 11 Check the connection among robots 12Ifone or more robots is disconnected 13nf nf+ 1 14R 1nf t 15 Recover all of faulty components 16ReturnR wherenfis the number of times that that system has been failed, aandbare Boolean vectors indicating which components are failed at a given time step. Line 410are used to randomly inject faults to the system based on the value of its components’ reliability. Line 11check whether all robots are still able to communicate despite some injected faults. One method to do this is to construct the graph form the remaining components and compute eigenvalues of the graph Laplacian [40]. The remaining lines are to keep track of the number of failures and to calculate the reliability of each time step. Then the state of the system is recovered for the next step. In this example, the experiment is repeated for 300 time steps. Since the desired reliability is 0:8, it is expected that out of these 300evaluations, approximately 60of them should end up in the system failures. The number of failures is counted and shown in 6 as well as the plot of the estimated system 8 reliability in Figure 7, which shows that the desired reliability of0:8can be achieved. Fig. 6: Experiment illustrating the assurance of the reliability. Link to the video of the experiment: dropbox.com/s/ti01o4z7v2nt62r/RobotExp.mpeg?dl=0 0 50 100 150 200 250 30000:20:40:60:81 Time StepReliability Estimated Reliability over Time Step Desired Reliability Fig. 7: Evaluation of system reliability at each time step. B. A350 IMA Architecture A large network inspired by the A350 Integrated Modular Avionics, shown in Figure 1 is now considered. However, instead of assuming the reliability of each ES is known, as in the previous example, the procedure adopted from ARP4761 [41] is applied to determine the acceptable component-level reliability for the original IMA architecture. Then, it is shown that from starting with this component-level reliability, the optimal architecture obtained from the proposed methodology is the same as the original one. 1) Determination of component-level reliability: Given a hazardous system severity (failure rate 107per hour), the fault tree analysis (FTA) [42] can be used to determine each ES reliability, as shown in Figure 8. The level of redundancy for each ES is shown in Table III. At the bottom of the fault tree, the failure may come from either the ES or the cables connecting these ES. The reliability of an individual ES can be computed using equations for series-parallel system structure [43], while the reliability of the cable can be computed by constructing a BDD and solving the higher-order polynomial equation obtained from recursive substitution of terms on theright-hand side of (4) [44]. It should be noted that although the switches are connected in a network structure, a single switch failure blocks the communication of other ES that connect to the faulty switch. Said failure leads to the failure of the entire network. Thus, this behavior of failure is equivalent to the series system. Assuming the average ﬂight hour of an A350 is 7hours, the desired reliability to satisfy the severity requirement is e710717107. The computational result of component-level reliability is shown in Table III. Fig. 8: FTA inspired by Airbus A350 AFDX network. TABLE III: Component-Level Redundancy and Reliability. End-SystemsRedundancyReliability based on Fig. 1 CRDC-A15, CDAU, SDU 1 0:999999985 DU-fIC,UC,OC,IF,LC,OF g CDLCU, ECB-APU, SCI Other CRDCs, AESU 2 0:999877961 CPIOM- fJ1, J5, J7 g, CMV CMV , ETRAS, EMU ADIRU, FMC 3 0:997539632 CPIOM- fH3, H4, H6, J2 g4 0:988952855 SFCC, EEC, EPDC, SPDB PRIM, SEC 6 0:950397903 Switches (per ADFX) 7 0:999991282 Ethernet Cables N/A 0:999994915 2) Redundancy Optimization: The problem has been for- mulated as in the form of (10) with all weights set to 1. Connections are only allowed between CPIOMs/CDRCs/LRUs and switches. There are 233variables (excluding slacks), 93of which are integer. The problem is solved in 40.08 milliseconds on an Intel i7-9700F computer, with 16 GB of memory running Ubuntu 20.04. The result is provided in Table IV, whose contents are similar to those in Table III. 3) Topology Optimization: The problem has been formu- lated as in the form of (16), with a fully-connected network 9 TABLE IV: Redundancy Optimization Result. End-Systems nij End-Systems nij CRDC-A15, CDAU, SDU 1Other CRDCs, AESU 2 DU-fIC,UC,OC,IF,LC,OF g CPIOM- fJ1, J5, J7 g, CMV CDLCU, ECB-APU, SCI CMV , ETRAS, EMU ADIRU, FMC 3CPIOM- fH3, H4, H6, J2 g4 SFCC, EEC, EPDC, SPDB PRIM, SEC 6 Switches (per ADFX) 7 between CPIOMs/CDRCs/LRUs and switches, and among switches. There are 1526 binary variables to determine the connections that can be removed without affecting network reliability. To avoid non-unique solutions, each weight is set to the scaled distance between ES and switches, according to Figure 1. An additional equality constraint forcing the homo- geneity between two redundant AFDX network is imposed. The problem is solved on the same machine as the redun- dancy optimization problem. It takes 549:35seconds to obtain the results shown in Table V, and Figure 9. The number 1in Table V indicates that there is a connection between two ES, and0otherwise. In Figure 9, for the ease of visibility, only the connections among Ethernet switches are shown. VI. C ONCLUSION A two-step framework for designing a network architecture under reliability constraints is proposed. Both steps are based on a mixed-integer program, in which the tools solving for their globally optimal solution are also presented. Numerical calculations show that the pertinence of the proposed method for optimization of real-world network applications on an A350 IMA. Furthermore, the assurance of the desired relia- bility is illustrated by a hardware implementation on a swarm robotics environment, further demonstrating the effectiveness of the proposed formulation. For the future works, the actual component reliability data should be gathered. A more sophisticated representation of reliability function should be considered. Potential sources of a common cause failure must be examined. ACKNOWLEDGMENT The authors would like to thank Dr. Pascal Traverse at Airbus for his useful discussion about avionics architecture. APPENDIX Proof of Proposition 1. Consider a monomial function of the general form ~f(x; ) = 0Qm+n k=1x k k. Finding the tightest monomial over-approximation of fis equivalent to minimizing a function,e(x; ) =~f(x; )f(x), i.e.,TABLE V: Network Topology Result. The value 1indicates the connection between two components, 0otherwise. End-SystemsSwitches1 2 3 4 5 6 7 PRIM- f3,4g, SEC- f3,4g 1000000CRDC- fA2,A4,A10 g, DU-IC CPIOM- fJ22,J72 g, ADIRU2, FMC2 SFCC- f3,4g, EMU2, EEC3 PRIM- f1,2g, SEC- f1,2g 0100000CRDC- fA7,A11,B13 g, DU-IF CPIOM- fJ21,J71 g, ADIRU1, FMC1 SFCC- f1,2g, EMU1, EEC1 AESU1, CMV1, DU-UC 0010000CPIOM- fJ11,J23,H31,H43.H61 g CRDC- fA3,B5,B9 g, ETRAS1 EEC2, EPDC1, SPDB1 AESU2, CMV2, DU-LC 0001000CPIOM- fJ12,J24,H32,H44.H62 g CRDC- fA6,B8,B10 g, ETRAS2 EEC4, EPDC3, SPDB4 CIDS1, DU-OC, EPDC2, SPDB2 0000100 CPIOM- fJ51,H33,H41,H63 g CRDC-A f1,9,13,17 g, Bf1,3,7,11 g CIDS2, DU-OF, EPDC4, SPDB4 0000010 CPIOM- fJ52,H34,H42,H64 g CRDC-A f8,12g, Bf2,4,6,12,14 g PRIM- f5,6g, SEC- f5,6g, ADIRU3 0000001 CDLCU, FMC3, ECB-APU, SCI CRDC- fA05,A15 g, SDU, CDAU Switch 1 - 1 1 0 0 0 1 Switch 2 1 - 0 1 0 0 1 Switch 3 1 0 - 1 1 0 1 Switch 4 0 1 1 - 0 1 1 Switch 5 0 0 1 0 - 1 0 Switch 6 0 0 0 1 1 - 0 Switch 7 1 1 1 1 0 0 - minimize 2Rm+n+11 2 0m+nY k=1x k k1cmY i=1xim+nY j=m+1x1 j 2 2 subject to 0m+nY k=1x k k1 +cmY i=1xim+nY j=m+1x1 j 8xi2[0;1]; i2f1;:::;mg 8xj2(0;1]; j2fm+ 1;:::;m +ng(22) To solve this problem, the feasible domain of each imust be analyzed. First, 0>0by the deﬁnition of monomial function. Next, for the constraint to be valid at every xi= 0, ~f(x)must be greater or equal to 1, which implies  i= 0, and j0. If everyxis set to 1except one single xlwhere l2fm+ 1;:::;m +ng, then1< l0violates the constraint, and l1increases the value of the objective function as lincreases. Therefore,  l=1is optimal in this case. Applying this for every l2fm+ 1;:::;m +ng implies that every j=1. Consequently, when every xis set to 1, any 0<1+cviolates the constraint, and 01+c 10 Fig. 9: Sequence of Integer-Feasible Solutions for AFDX Network Topology Optimization. The optimal topology is the same as the one shown in Figure 1. increases the value of the objective function as 0increases. Therefore,  0= 1 +cis optimal. To check that  0= 1+c,  i= 0, and  j=1are indeed optimal, the KKT necessary conditions are used [45]. The equation for Lagrangian can be written as L=1 2 0m+nY k=1x k k1cmY i=1xim+nY j=m+1x1 j 2 2 +0 @1 +cmY i=1xim+nY j=m+1x1 j 0m+nY k=1x k k1 A(23) It can be seen that it is not possible for the constraint to be active for all value of xin the domain; therefore, the Lagrange multipliers must be zero (= 0) to satisfy the complementary slackness condition. The partial derivatives of Lagrangian w.r.t. 0, i, and jare @L(x; ) @ 0 =e(x; )m+nY k=m+1x1 k(24) @L(x; ) @ i=j =e(x; )(1 +c)m+nY k=m+1x1 klog(xi=j) (25) where e(x; ) = (1 +c)m+nY k=m+1x1 k1cmY i=1xim+nY j=m+1x1 j Sincee(x; ) = 0 atx=1, KKT necessary conditions are satisﬁed. Note that, based on the previous analysis, if is picked to be optimal at other point, it will violate the constraint atx=1. For the second-order sufﬁcient condition, it can be seen that the only non-zero second-order partial derivative of Lagrangian evaluated at andx=1is @2L(x; ) @ 2 0 ;x=1=m+nY k=m+1x2 k ;x=1= 1 (26)Hence, the Hessian is positive semi-deﬁnite, which implies optimality.  Proof of Theorem 1. Because the branch-and-bound method depends on the convergence of upper and lower bounds towards each other as the size of the optimization domain shrinks, its global optimality can be achieved if both bounds obtained from relaxation problems (17) and (19) are valid. The validity of the upper bound can be derived by leveraging that fact that the problem (17) is an integer-relaxed SP and its solution is at least locally optimal. Thus, if this solution is not globally optimal itself, there always exists another solution that cannot be worse than this one. Hence, it is a valid upper bound. For a lower bound, it is necessary to show that nonconvex constraints are under-approximated and the relaxed problem (19) can be solved to a globally optimal solution. From (18), since every element of x, andRare in the domain of [0;1]. fi(x;R) =Rlo(i)R1 i+pjxjRhi(i)R1 i 1 +pjxjRlo(i)R1 i =Rlo(i)+pjxjRhi(i) Ri+pjxjRlo(i)Rlo(i)+pjxjRhi(i) 1 +pj (27) Therefore, the constraints used in (19) under-approximate the original ones in (16). Furthermore, these functions are posynomial, which implies that the problem (19) can be solved to a globally optimal solution. 