Int. j. inf. tecnol.

https://doi.org/10.1007/s41870-023-01312-9

ORIGINAL RESEARCH

Framework for evaluating reliability of stochastic flow networks

under different constraints
Muhammad A. Elgamal1 · Lamiaa Y. Younis2 · Hani A. Abdou2 · Yehea I. Ismail1 ·
Moatamad R. Hassan2

Received: 10 December 2022 / Accepted: 25 May 2023

© The Author(s), under exclusive licence to Bharati Vidyapeeth’s Institute of Computer Applications and Management 2023

Abstract Capacitated stochastic flow networks have wide work fine for single-source single-sink single-commodity
applications including modelling of electricity, transpor- networks for both static and dynamic demands.
tation, and delivery networks. Evaluating the reliability
of stochastic flow networks is crucial for network design Keywords Stochastic flow network · Minimal path ·
and maintenance. The reliability of a network to deliver a Recursive sum of disjoint product · Network reliability
specific demand is subject to flow constraints depending on
network purpose. Additionally, for designed networks, our
assumptions on arc directionality, node failure and dynamic- 1 Introduction
ity of demand and arc reliability—can vary. Consequently,
we need a generic framework that accommodates all these Stochastic flow networks, SFN, model real networks like
variations and helps designers evaluate reliability. In this electricity [1], water or data network infrastructure [2] or
paper we introduce Flexible Evaluation Algorithm for Reli- transportation networks [3]. Each element in these networks,
ability, FEAR v1.0 to evaluate reliability of designed net- i.e., arc or node- can have a set of discrete capacity levels
works and provide maintenance plans. We benchmark the with independent random probability [4, 5]. In this regard,
performance of our framework against networks from the network reliability is defined as the probability that the max-
literature beside introducing a new example of coapplied imum flow of the network is not less than a given demand
multiple constraints. Afterward, we validate our framework [6]. Evaluating reliability can help find optimal network
against recent literature for networks with dynamic arc reli- designs to boost up performance [7]. Besides, SFN’s can
ability. Finally, we show a novel maintenance algorithm for transport single or multiple commodities between source
dynamic demand. At the end, the framework is proven to and sink nodes [8].
In the contrary of multistate systems, binary networks
* Muhammad A. Elgamal have only two states: functioning or failing [9], and hence
melgamal@aucegypt.edu network reliability is simply the connectivity between source
Lamiaa Y. Younis and sink nodes. Methods of estimating network reliability
lamiaayoussif22@gmail.com depend either on knowing constituting path sets or cut sets
Hani A. Abdou [4].
haniabdou2000@sci.aswu.edu.eg Lin et al., tried to evaluate the reliability of capacitated-
Yehea I. Ismail flow network with multistate elements in terms of path sets
y.ismail@aucegypt.edu [10] compared to a previous algorithm based on Xue’s work
Moatamad R. Hassan [11], where the network is decomposed to subnetworks
mr.hassan@sci.aswu.edu.eg with simple connections like series and parallel etc., then
1
Center of Nanoelectronics and Devices, The American the whole system reliability is estimated. Alternatively,
University in Cairo, P.O. 11835, Cairo, Egypt Lin made computing reliability of a generic network much
2
Department of Mathematics and Computer Science, Faculty easier. The only constraint on flow vectors satisfied network
of Science, Aswan University, P.O. 81528, Aswan, Egypt demand only, however in later works, Lin et al., in [4], added

13
Vol.:(0123456789)
 Int. j. inf. tecnol.

budget of transmission as a constraint given the cost of trans- that Recursive Sum of Disjoint Product, RSDP, is more
mission through any of network elements. efficient for networks with elements’ count greater than
Afterward, Lin in [12], generalized the algorithm devel- 15, compared with state-space decomposition as proposed
oped in [10] to account for the possibility of node failure, in [6]; which is crucial for real networks and their perfor-
at which each node has a capacity distribution as well as mance. It is also noteworthy, that RSDP must drop some of
other arcs. Lin and Huang [13], studied the case when trans- state vectors that are less than other state vectors, as they
mission error occurs affecting reliability; so, they found all do not affect reliability calculation and consume memory
lower boundary points to the flow vectors after being con- for recursive implementation of the algorithm [21]. For
strained to follow maximum tolerable error rate of the whole these reasons, several state vectors ordering heuristics
network. They studied the performance of their developed were proposed to speedup computation of reliability [21].
algorithm on the National Science Foundation Network, Most of previous works [10–17] evaluate reliability
NSFNET. Additionally, they studied the time complexity of case by case, with aid of manual calculations which are
their proposed algorithm. prone to error. In addition, when the variation of network
Other authors constrained the network performance to fit reliability problems increases, we need to define a pro-
other applications. For instance, Lin et al. in [14], tried to gramming framework where we design stochastic flow net-
model good delivery networks where each node stood for a works, make them subject to flow constraints and evaluate
middle supplier or a middle city within the delivery network. their reliability. In the scope of this version of framework
Each network arc stood for a carrier between different nodes. we limit its capability to model single-source/single-sink/
As transferred goods spoil through transportation like fruits single-commodity stochastic flow networks. Also, we
for instance, we can give a spoiling rate for each arc within limit our scope to use constraints specified in step 2 of
the network. Hence, we can constrain the network such that the framework. The framework also can model situations
the total spoiled goods at the sink nodes do not exceed a when the number of components per arc is stochastic,
specific value. Hence Lin et al. proposed constraining the given that each component produces the same amount of
network with a spoilage constrain which altered the reli- commodity. Additionally, the framework can be used to
ability evaluation process compared to [12, 13]. model reliability of network under time-varying demands,
Another example is stochastic networks representing and time-varying arc reliability. With considering time in
online-food delivery systems [15] where each node repre- evaluating reliability, one can design a maintenance plan
sents a delivery region, and each arc represents a real path- to sustain network performance.
way between two regions- can have time and space con- We implemented our framework in MATLAB program-
straints where the reliability of the network is the probability ming language. In this framework, one can define network
that food is delivered within a specific time and without topology, find minimal path sets, apply constraints on flow
exceeding the size of the delivery box. vectors and convert these flow vectors into corresponding
Another example is the use of SFN’s to model multistate state vectors, leading to reliability evaluation at the end. We
computational grids [16]. In such a situation the network use RSDP for reliability evaluation to scaleup for large net-
reliability is constrained by bandwidth, maximal loads, and works. In order to demonstrate the efficiency of our frame-
total cost. work, we simulate several known examples from the litera-
Interestingly, Chang in [17] could model network time- ture and study new problems as well.
varying reliability when the reliability of each arc varies The paper will be divided as follows:
with time given a specific function, it was presumed that
the network had constant demand rate through a specific 1. Section 2 will show given assumptions and basic defini-
time-window. Chang proposed several policies to maintain tions.
the overall network reliability above a specific level by main- 2. Section 3 will describe all steps required in our frame-
taining constituting arcs. work to go from network definition up to reliability
Several methods existed to estimate reliability depend- evaluation.
ing on inclusion/exclusion principle, IE, or state-space 3. Section 4 will contain four examples where element
decomposition [6, 18]. Given all state vectors and for each capacity distributions do not change with time. We use
iteration, reliability is updated, and state vectors are grouped the first three examples to validate the performance of
into three groups: acceptable, unacceptable and unspeci- our framework against benchmarks from the literature
fied. Each group of unspecified state vectors is decomposed and evaluate reliability under different demands and
recursively until no state vector is unspecified anymore. Par- constraints rather than originally done by authors. It is
allelization speeds the execution of the algorithm as in [18]. noteworthy, that these benchmarks have different topolo-
Furthermore, reliability can be evaluated based on sum gies, flow constraints and element reliabilities. On the
of disjoint product as in [5, 19, 20]. Zuo claims in [4], other hand, the fourth example is a novel example where

13
Int. j. inf. tecnol.

we apply error and cost constraints together on TANET with time as given by the function ri (t). Subsequently the
and evaluate reliability. reliability of the whole network is time dependent and is
4. Sections 5 and 6 provide the most general case when ele- R(t).
ment reliability decay with time and when demand rates
change as well. Besides, it provides an arc maintenance E. Assumptions
algorithm that is included within our framework.
The network works at constraints (d, E, H ), where d is
Finally, we show potential future developments, provide demand (conserved through transmission [23]), E is maxi-
our source code on a GitHub repository then conclude our mum acceptable transmission error and H is the maximum
work. transmission cost through the network. The network may
work at all, none, or part of these constraints. The set of
feasible flow vectors satisfying (d, E, H) is called W. Also,
the set of corresponding state vectors is called T(W). Finally,
2 Definitions and assumptions
from T(W) we have subset of acceptable state vectors that we
A. Definition 1 can apply RSDP on and we call this set 𝜓[T(W)].
(1) Lemma 1
∑
Let G ={ (A, N, C)}be an SFN with following elements: From definition 2, we have si = j fj ��ei ∈ MPj and
arcs A = A1 , … Aa that can be directed or not, and nodes si ≤ 𝛾i ci.
{ }
N = N1 , … , Nn . All non-perfectly reliable elements that (2) Lemma 2
have capacity distributions [22] belong to K = {e1 , … , eL }, The probability that a vector X is not less than a specific
where ei ∈ (A ∪ N) (we use the following convention- we state vector S ∈ T(W) based on our assumptions and defini-
number arcs before nodes). We assume the capacity distribu- tions is (1).
tion of each element to be statistically independent. Addi- l ci
� � � �
tionally, we assume each arc within K to have 𝛾i productive Pr ⌈xi ∕𝛾i ⌉𝛾i = j𝛾i (1)
components. i=1 j=si ∕𝛾i

B. Definition 2

The flow within SFN is the number of transferrable units 3 Framework description
through all components within an arc. We define the state
vector S = (s1 , … , sL ) to be the flow through each element The algorithm can describe SFNs with various structures
in K . under multiple constraints. It is extensible and applicable
The SFN has l minimal paths noted as MPj and each state on several structures included in earlier works like [4, 10,
vector has a corresponding flow vector F = (f1 , … , fl ) where 12, 13, 17]. In our work, we implement the algorithm on
fj stands for flow inMPj . For all state vectors the maximum MATLAB [24] class named reliability_net; the
number of transferrable units in all(non-reliable elements is algorithm is outlined in Fig. 1. and is divided into steps 0,
)
the maximal capacity vector, C = c1 , .., cL . 1,2, 3, 4 and 5.
When considering the error constraint, we denote error The network graph can be plotted with plot(net)
of transmission in ei as 𝜖i ; likewise, for cost constraint, we which shows network topology, element ordering and ter-
denote the cost of transmission in ei as hi. minal nodes.
In case of a static network the following class method
C. Definition 3 is used evaluate_reliability(net, plot_
curve, maximal_cost, maximal_error, com-
( )
Let Y and be two state vectors, such that pute_fast). Here net is a reliability_net object
and Z = z1 , … , zL , Y is less than Z if and only if yi ≤ zi ∀i .
( Z ) Y = y1 , … , yL
and demand is the required demand at which we show
( ) the flow and any of maximal_cost and maximal_
The maximum of both( vectors
) is Q = Y ⊕ Z = q1 , … , qL
such that qi = max yi , zi ∀i. demand is passed as empty array [] if it does not apply.
Both plot_curve (for plotting demand reliability curve)
D. Definition 4 and compute_fast can take true or false values.
In case of a dynamic network, we use the class method
For time-varying demand d(t) applied to an SFN, we con- reliability_dependent_time (net, w,
sider the reliability of each non-reliable element to decay dist, parameters), where c is maximal capac-
ity vector, and dist is string array that takes values of

13
 Int. j. inf. tecnol.

Table 1  Possible Arc Reliability Functions

STEP 0
1. Specify Network topology and the set . Arc reliability ri (t) Equation
2. Check if network reliability is dynamic. If yes,
a. Specify element reliability as a function of time. [ ( ) ]
Weibull distribution 𝛽i
b. Estimate capacity probability distribution at each time ri (t) = exp − 𝛼t
instance. i
3. Take capacity probability distribution for all unreliable elements. [ (
4. Check if nodes are perfectly reliable. Normal distribution )2 ]
t−𝜇
If yes, exp − 12 𝜎 i
i
a. Take the number of units produced by each component
[ ]
in each arc. Exponential Distribution exp −𝜆i t
5. Take required demand.
STEP 1
0. If the network has bidirectional arcs, replace each bidirectional arc
by two unidirectional arcs as in [28] time instances. In case of a dynamic network, we can enter
1. Implement BFS to find minimal paths.
2. Show shortest paths in two terms of traversed nodes (if they are not a specific arc reliability function like those in Table 1 or
reliable) and traversed arcs.
assume an arbitrary reliability function that is positive, real,
STEP 2
1. Define different constraints.
and monotonically decreasing. Finally, the capacity prob-
STEP 3 ability distribution can be expressed in terms of arc reli-
1. Find all flow vectors, which satisfy abilities as shown in (2) according to [17].
for all , the number of such vectors is .
2. Apply each constraint defined in step 2, on the given flow vectors, (c ) [ ]c −i
each constraint decreases the number of feasible flow vectors, to 𝑃 𝑟(d(t) = i) = i ri (t)i 1 − ri (t) i (2)
reach a flow vector set . i
STEP 4
1. Find Convert flow vectors to state vectors according to [33]- Lemma Third, if only arcs are not perfectly reliable, i.e., have
1, so ∑ and ⌈ ⌉ capacity probability distribution; then we need to tell the
2. Remove repeated state vectors, to reach the feasible state vector set
maximum number of units produced per each component
3. Check the cyclicity of the network (step 1.2), according to [33]- in all network arcs.
Lemma 4, if the network is acyclic, then every element of is
an MP (lower boundary point), i.e., , otherwise, In all situations when capacity probability distribution is
we need an additional step:
a. Assume initially that .
known, the demand must be specified.
b. For all and , if then is not In this step we assume that 𝛾i = 1 unless otherwise
an MP element, so
from it.
, and it is excluded
specified.
STEP 5
1. Use RSDP to evaluate network reliability given acceptable state B. Step 1
vectors.

Several algorithms exist to find minimal paths and deter-

Fig. 1  Brief description of FEAR algorithm mine the cyclicity of the network [25–27]. In our framework
we implement Breadth-first Search, BFS [28], to find all
minimal paths connecting terminal nodes. All minimal paths
“normal”, “Weibull” and “exponential” for are stored in a cell array [29], where each cell stands for a
each element. parameters is a cell array for each of single path traversed from source node to target node.
arc parameters. It is noteworthy that the method can take Lines 121–136 in reliability_net demonstrates
additional input containing arbitrary arc reliability function the BFS algorithm. There, sn and tn are source and target
for each time instance. nodes respectively, P is the cell array having minimal paths,
A complete description of the framework flow can be from and to are two column vectors containing start and
invoked by the class method disp_flow(net, demand, end nodes of each arc within the network and net is an
maximal_cost, maximal_error). Here demand is object of class reliability_net which encapsulates
the required demand at which we show the flow. our algorithm. Additionally, update_path_vectors is
a function that finds all arcs whose end node is a search node
A. Step 0 and find the start nodes of these arcs.

First, we define the network topology by specifying C. Step 2

source and sink nodes, and two other arrays standing for the
start and the end of each arc. Besides, whether the network Update flow constraints applied on the network. These
is unidirectional or bidirectional is specified. constraints are applied on feasible flow vectors after estimat-
Second, dynamicity of the network is declared. If it is ing them and they are noted as follows:
dynamic, we follow the procedure in [17] to solve at specific

13
Int. j. inf. tecnol.

TM1 = 𝑃 𝑟 X ≥ S1
• ’flow = demand’, which corresponds to the following
( )
∑l (4)
condition j=1 fj = d , [10].
{ Lj’, which})corresponds to the condition TMi = Pr X ≥ Si
• ’less (than
fj ≤ 𝑚𝑖𝑛 d, ci 𝛾i |ei ∈ MPj ∀1 ≤ j ≤ l , [10].
( )

− PrU {S1 ⊕ Si , S2 ⊕ Si , … , Si−1 ⊕ Si} } for i ≥ 2

( )
• ’maximal capacity constraint’, which cor-
responds to the condi- (5)
tionsi = j fj �ei ∈ MPj } ≤ ci 𝛾i , ∀ei ∈ K , [10].
∑ � �
(3). Lemma 3
( If i ≠ j,) {Si , Sj } ⊂ M and Si ≥ Sj then PrU(M) = PrU
�
• ’cost’, which corresponds
∑ � to the condition
≤
∑l
• U j f H ∶ U j = i h i
�e ∈ MP }[4], which ensures
� i j
M − {Si } .
j=1 j

Proof: If Si ≥ Sj then {X|X ≥ Si } ∪ {X|X ≥ Sj } = {X|X ≥ Sj } so

the transmission cost to be lesser than specified maximal
cost.
X�X ≥ Sj = X�X ≥ Sj and
⋃�M� � � ⋃�M� � �
• ’ e r �r o r ’ , which corresponds to the condition
f ei ∈MPj 1 − 𝜖i ≥ d(1 − E) [13], which ensures
�� j=1

( j≠i )
∑l ∏ � j=1
j=1 j
that the correctness of transmitted symbols is greater than PrU(M) = PrU M − {Si } after removing Si from the
minimum acceptable correctness d(1 − E). input.

Lemma 3 is used to reduce the number of state vectors at

D. Step 3 each time the RSDP algorithm is called for execution in the
code, which in turn reduces memory and time of calculating
The estimation of flow vectors can be done in several ways, the reliability [21].
but the way introduced in [30] avoids counting all possible
flow vectors and applying all constraints on them. Despite
of that, for coding ease, we compute the set of flow vectors
{0, … , d}l using repeated Cartesian product with aid of a 4 Examples on static reliability
related MATLAB function [31]. While finding this set, we
used parallel processing to boost up computation especially for The target of these examples is to confirm the performance
large networks. Our approach is implemented in the method of our framework against results reported in the literature
generate_flows of the MATLAB class reliability_ and then demonstrate its generality. All examples have
net. The corresponding flow vectors is found in the prop- related MATLAB scripts that aim to calculate reliability at
erty of network class as ’net.reliability.F’ where different conditions. Examples 1, 2, and 3 are found in the
’net’ is the name of the network instance. literature, while example 4 is a novel example where both
error and cost constraints are applied on a real network
E. Step 4 simultaneously.
The same network is used for examples 1, 2, 5, 6 and 7.
Discussed in Fig. 1. The capacity distribution used in these examples is taken
from [4, 9], and [10]. In examples 1 and 2, arcs have differ-
F. Step 5 ent capacity distributions. We number the arcs in order of e1
to e6 and the nodes in order of e7 to e10.
At this step we use RSDP to evaluate reliability of the net- A. Example 1. (Perfectly reliable nodes)
work given the state vectors and the capacity distribution of
each element belonging to K. According to [32], reliability is The flowing example is in ([10]—example 2). The prob-
defined as the probability that the state of the system is greater ability distributions of the arc capacities used in this exam-
than the required demand. The state vectors are 𝜓[T(W)]. ple are found in [4, 9]. The network has e7 as source node
According to [32], the union and e10 as target node, n = 4 and a = 6 . All arcs are uni-
�⋃probability is a recursive function
defined as PrU(M) ≡ Pr X�X ≥ Sj ∈ M . Then the
�M� � �� directional, and nodes are perfectly reliable. The required
j=1 demand is d = 3 and we have C = (3, 2, 1, 1, 1, 2, 0, 0, 0, 0).
reliability is found as in (3), (4) and (5). The following constraints are applied upon the network
d(t) ’flow = demand’, ’less than Lj’, ’maximal
∑
R(t) = PrU(𝜓[T(W)]) = TMi (3) capacity constraint’.
i=1

13
 Int. j. inf. tecnol.

Table 2  Reliability against Demand 0 1 2 3 4 ≥5

various demand levels. Example
1 Reliability 1 0.98892 0.88307 0.61142 0.20412 0

Table 3  Reliability against various demand levels Example 2 1

E=0.03
E=0.02
Network reliability

R(d, E)
H=6 H = 10 H = 14 H = 18 0.5

d =0 1 1 1 1
d =1 0.97479 0.97803 0.97803 0.97803
d =2 0 0.59500 0.86266 0.86266 0
0 1 2 3 4 5 6 7 8
d =3 0 0 0 0.58212 d
d ≥4 0 0 0 0
Fig. 2  Reliability curve for different error rates

After the framework runs R is 0.6114 which is same as

reported in [10]. Reliability values for several demands are Figure 2 shows reliability of the network against several
shown in Table 2. demands and at two maximum tolerable error rate 0.02 and
B. Example 2. (Cost constraint with perfectly reliable 0.03. We find that lower maximum error rates reduce net-
nodes) work reliability as shown.

The flowing example is found in [4]—example 2. Steps D. Example 4 (Cost and error constraints with perfectly
0 and 1 are (same as example 1 but with addition of budget reliable nodes)
)
constraint h1 , .., h10 = (2, 3, 1, 1, 3, 3, 0, 0, 0, 0) and total In this example, we apply our algorithm on Taiwan
budgetH = 18. The ’cost’ constraint is added to net- Academic network, TANET. TANET covers all academic
work constraints. institutions in Taiwan like universities, high schools and
The reliability of the network under (d = 3, H = 18) is elementary schools [33]. It has 30 arcs e1 to e30 and 26 per-
0.5821 which is same as in [4]. Table 3 shows reliability fectly reliable nodes- e31 to e56. Each of these nodes stands
at several demands and total budgets. It is noticeable that for a location on the geographic map of Taiwan. We need to
lowering the cost affects reliability significantly. calculate R at (d, E, H) = (3, 0.04, 120).
The network has e31 as source node and e56 as target node,
C. Example 3. (Error constraint with unreliable nodes
all arcs are unidirectional, and nodes are perfectly reliable.
except for source and sink nodes)
Two constraints affect transmitted data from source to
The following example is found in ([13]—example 1). target node- error rate associated with each link and cost of
The arcs in order of e1 to e8 and the nodes in order of e9 to transmission through this arc. For our example, the capacity
e13. distribution of each arc follows [34] where it was chosen to
The network has e12 as source node and e13 as target node, maximize reliability for demand and time-limit constraints.
n = 5 and a = 8.. All arcs are unidirectional, and nodes are Error rates are generated randomly, for our example to prove
unreliable (has a capacity distribution) except for source and the computational capability of our framework.
target nodes. The required demand is 4. On the contrary to [33, 34] where only 6 minimal paths
In this example, C = (4, 4, 4, 3, 4, 3, 5, 4, 5, 3, 4) and are considered, we find total of 8 minimal paths, and we con-
(the error)of transmission through unreliable elements is sider them all in our calculations. The following constraints
𝜖1 , .., e11 = (5, 3, 6, 2, 8, 4, 4, 5, 8, 6, 7)∕1000 . The maxi- are applied to the network: ’flow = demand’,’maximal
mum tolerable error rate is E = 0.03. The following con- capacity constraint’, ’error’ and ’cost’.
straints are applied to the network ‘flow = demand’, Additionally, the effect of changing cost budget and maxi-
‘ m a x i m a l c a p a c i t y c o n s t r a i n t ’ and mum tolerable error rate are investigated on the reliability of
‘error’. network for different demand as shown in in Table 4. Lower-
The network has 63 lower boundary points in total and ing maximum tolerable error degrades network reliability
some acceptable flow and state vectors are missing in the more considerably than lowering its budget.
results of [13]. The reliability was 0.6411 at demand 4 and
maximal error rate of 0.03 which is same as [13].

13
Int. j. inf. tecnol.

Table 4  Simulation Results for Demand level

different maximal cost and error
Constraints 0 1 2 3 4 5
H E

60 1 1 1 0.9952 0.6268 0 0
80 1 1 1 0.9954 0.8662 0 0
120 1 1 1 0.9954 0.8865 0.5955 0
120 0.030 1 0.9668 0 0 0 0
120 0.035 1 0.9670 0.9558 0.6440 0 0
120 0.040 1 0.9969 0.9978 0.8662 0 0

5 Example on dynamic reliability

Maintenance Algorithm
1. Read , , maximum number of maintainable arcs
In examples 5 and 6, we are going to demonstrate the capa-
(max_a) and set = 1.
bility of our framework to verify some results in [17]- 2. Simulate dynamic reliability for this period.
especially a situation where arc reliability decreases with 3. Set = + 1.
time and when demand is supplied with a constant rate 4. Stop the algorithm if you simulate through the last
maintenance period, otherwise simulate dynamic
called the instantaneous demand.
reliability for this period and set = 1.
A. Example 5 (Verification of Example 1 in [17]). 5. If (system reliability < and < max_a) go to 6,
otherwise go to 3.
Network in example 1 is used in this example when nodes 6. Sort arcs ascendingly based on difference in arc
are perfectly reliable. In this exampleC = (3, 2, 2, 2, 4, 3) , reliability between start and end of the maintenance
period { 1, 2, …, }.
(γ1 , … , γ6 ) = (15, 20, 25, 25, 10, 15) and we use Weibull
7. Maintain arcs from 1 to .
distribution for (arc reliabilities) with following param- 8. Simulate dynamic reliability for this period and go to
e t (e r s : ) 𝛼 1 , .., 𝛼 a = (350, 250, 200, 200, 300, 180) step 5.
and 𝛽1 , … , 𝛽a = (1.1, 1, 0.8, 0.8, 1, 1).
The values of capacities, arc reliability parameters Fig. 3  Summary of proposed maintenance algorithm
are reordered to follow our ordering the network order-
ing in example 1. The total demand between t = 0hr and
t = 40hr is 2400 so the demand rate is d = 60 . The prob- 6 Modeling networks for dynamic demand
ability distribution of all arcs at t = 40hr is displayed and for maintenance
within the example script. The following constraints
apply: ‘flow = demand’ and ‘maximal capac- In this section we introduce mathematical formulation for
ity constraint’. The network is cyclic, and we dynamic demand and how our framework can accommodate
notice that 𝜓[𝐓(𝐖)] = 𝐓(𝐖). Finally, we find that the it. Furthermore, we propose a novel maintenance policy to
R(40) = 0.74297. fix networks with dynamic demand. In most of real systems,
B. Example 6 (Reliability against completion time) not only does the element reliability changes with time but
also the instantaneous demand. One of the shortcomings of
The reliability of the network if the demand was deliv-
[17] is that it assumes constant demand over time.
ered in several completion times- was investigated in
For a dynamic network, it is needed to deliver Dn units
in the time interval [(n − 1)Td , nTd ] for n ≥ 1. During this
([17]- Sect. 4.3). The network is same as in example 5,
but with C = (2, 3, 2, 2, 3, 2), (γ1 , … , γ6 ) = (2, 1, 3, 3, 1, 1)
duration instantaneous demand d(t) can vary anyway so we
and( arc reliabilities follow an exponential distribution
) have (6)
with 𝜆1 , … , 𝜆6 = (0.001, 0.003, 0.002, 0.002, 0.001, 0.003).
Assuming we have a total demand level D , checking nTd

∫
the reliability if we change the time to which our network Dn = d(t)dt (6)
can deliver required network is equivalent to changing the (n−1)Td
demand in time, which we will formulate soon, so d(t) = D∕t
to ensure integer demand levels. It will produce the same Maintenance Policies As real networks are not main-
output in ([17]- Fig. 3), when time range is 120 ≤ t ≤ 300 tained continuously, nor instantaneous demand is always
and D can be any of 300, 600 or 900. constant. We propose to simulate the network reliability

13
 Int. j. inf. tecnol.

for each maintenance period Tm . If the network reliability In case of constant demand (as in [17]), we have 𝛼n = Td
falls below service level 𝜃 we maintain the arc with lowest which
( is not)the case as in (8). We choose daily demand to be
average rate of change (i.e., lowest difference of the arc reli- D1 , … , D7 = (2400, 2400, 1500, 2600, 2800, 4400, 4800)
ability between the start and the end of maintenance period). implying high demand of cars at weekends. However, these
After that, we repeat the simulation if the problem persists. high levels of demand mean enormous search space for find-
we maintain nearest arc with higher rate of change until the ing flow vectors according to step 3 in the algorithm descrip-
network reliability never falls below service level. A sum- tion. So, we discretize levels of demand where each level
mary of the algorithm is presented in Fig. 3. The algorithm corresponds( to 50 cars,)so the corresponding demand levels
ensures that minimum number of arcs is maintained at each we have are D1 , … , D7 = (48, 48, 30, 52, 56, 88, 96). From
� �

maintenance period without exceeding a chosen maximum daily demand levels we can derive hourly demand based
number of maintained arcs. on (7) to be as depicted
( in Fig. ) 4. Additionally, we assume
B. Example 7 (Modelling realistic demand) C = (3, 2, 2, 2, 4, 3), 𝛾1 , .., 𝛾a = (15, 20, 25, 25, 10, 15) and
as we use Weibull distribution
( ) for arc reliabilities with fol-
If we think of vehicles moving across the road as trans- lowing parameters 𝛼1 , .., 𝛼a = (87.5, 62.5, 50, 50, 75, 45)
ferred units, we know that rush hours have the biggest ( )
and 𝛽1 , … , 𝛽a = (1.1, 1, 0.8, 0.8, 1, 1) . Accordingly, we
instantaneous demand. For network shown in ([17]—Fig. 3), evaluate dynamic reliability to be as shown in Fig. 5.
we can assume Td = 24hr , Tm = 1week = 168hr . Through- When we maintain the network to be at acceptable service
out a single day we think of instantaneous demand to be, level 𝜃 = 0.8 and with maintenance period Tm = 48hr we
{ [ ]} rise the system reliability above 0.8. However, the maxi-
2 𝜋
( )
dn (t) = round 𝛿n cos t − Ps (7) mum number of maintained arcs limits the efficacy of our
Td

The instantaneous demand peaks at a specific hour and

declines away from this hour which is the case for (7) where
maximum demand is 𝛿n and Ps represents the shift of the
peak from the beginning of the day, here we assume that
Ps = 12hr which is the time of rush hour. The instantaneous
demand is rounded to nearest integer. So, we can find the
required demand as in (9) as follows in (8) and (9)
( ) ( )
Dn = D nTd − D (n − 1)Td = 𝛿n 𝛼n (8)

and
{ { [ ( ) ( )]}}
𝛿n 2𝜋Ps 2𝜋
D(t) = round 2𝜋t + Td sin − sin (Ps − t)
4𝜋 Td Td
(9)

Fig. 5  System reliability when the network is not maintained, when

3 arcs can be maintained at maximum and when 5 arcs can be main-
8 tained at maximum
7

6
Demand / 50 [cars]

0
0 20 40 60 80 100 120 140 160 180
Time [hr]

Fig. 4  Instantaneous demand for example 7 Fig. 6  Arc 6 reliability when it is maintained

13
Int. j. inf. tecnol.

Table 5  Maintained Arcs at j for jTm Maximum Number set of constraints when cost and error constraints are used
Different Maintenance Periods of maintained arcs simultaneously to model the reliability of Taiwan Academic
(In ascending order Network, TANET.
of arc reliability Furthermore, our framework is confirmed against [17] for
average rate of
change) modelling dynamic reliability when demand is constant and
when arc-reliability follow a specific stochastic distribution.
3 5
In example 7, the capability of our framework for model-
1 3, 4, 6 3, 4, 6, 2 ling networks with varying demand (e.g., traffic networks)
2 2, 5, 1 5, 1, 3, 4, 6 and varying arc reliability is demonstrated. Our framework
3 6 2 supplies maintenance algorithm for dynamic networks that
maintains minimal number of arcs to keep network reliabil-
ity above acceptable service level.
algorithm, so when we have three maintainable arcs at max- Our framework, FEAR v 1.0, can be used to model vari-
imum, the system reliability drops below 𝜃 at the second ous networks under several constraints in static and dynamic
maintenance period. This sudden drop is eliminated when settings, as well as giving insights at required maintenance
we have five maintainable arcs at maximum. Besides, rais- procedures for such dynamic networks.
ing maximum number of maintainable arcs enhances sys-
tem reliability in general as shown in the third maintenance
period in Fig. 4. A plot of arc reliability is shown in Fig. 6, 8 Future work
when network is maintained, the arc reliability is restored to
100% again and we can say that( if arc i )is maintained at jTm, Several directions can be enhanced in our framework:
i.e., jth maintence period so ri jTm + t = ri (t). Our frame-
work produces a cell array containing all maintained arcs at 1. Modelling multiple-source multiple-sink networks with
each maintenance period by using the method minimum_ single and multiple commodities.
arc_maintainence (net,maintence_period, 2. Implementing algorithms for reliability evaluation other
service_level, maximum_arcs_maintained, than RSDP and enhancing speed of computation by
c) (c is a row vector containes maximal number of com- using parallel processing or GPU capabilities.
ponents per arc). Consequently, the maintained arcs at each 3. Developing an algorithm to solve the constraint satisfac-
maintenance period are listed in Table 5. In Fig. 5, the reli- tion problem, CSP of finding suitable flow vectors like
ability of arc 6 is demonstrated when maximum maintain- for instance forward checking, maintain arc consistency,
able arcs is three or five arcs. or backtracking [35].

7 Conclusion 9 Source code

This work presents a unified framework for the definition of All data that support this article including all MATLAB
stochastic flow network with single source, single sink and scripts can be accessed openly at: https://g​ ithub.c​ om/M
​ uham​
single commodity, as well as the estimation of its reliability. madEl​gamal/​FEAR_​frame​work
The framework can accommodate several variations in net-
work topology, flow-vector constraints, dynamicity of relia-
bility and can be used to simulate maintenance procedures as
References
well. First, we can assume perfectly reliable or failure-prone
nodes and as well as we can exclude terminal nodes (sink 1. Guo Y, Summers TH (2019) A performance and stability analysis
and source nodes) and assume them perfectly reliable. Sec- of low-inertia power grids with stochastic system inertia. In: Pro-
ond, arcs can be defined as unidirectional or bidirectional. ceedings of the American Control Conference, 2019, vol. 2019-
July, pp 1965–1970. https://​doi.​org/​10.​23919/​acc.​2019.​88144​02
Third, arcs can have multiple components producing the
2. Chang PC, Lin YK, Huang DH (2019) Reliability for a stochastic
same number of commodity units. Fourth, network demand flow computer network subject to time constraint and correlated
and reliability can be static or dynamic and if the network is failures. In: Proceedings - 25th ISSAT International Conference
dynamic, the framework can simulate several maintenance on reliability and quality in design, 2019, pp 24–28
3. Liu Z, Wang S, Zhou B, Cheng Q (2017) Robust optimization of
procedures on the given network.
distance-based tolls in a network considering stochastic day to day
In addition, our framework is confirmed against several dynamics. Transp Res Part C Emerg Technol 79:58–72. https://​
benchmarks found in the literature for static networks in [4, doi.​org/​10.​1016/j.​trc.​2017.​03.​011
10, 13]. Afterward, our framework is tested against a new

13
 Int. j. inf. tecnol.

4. Lin JS (1998) Reliability evaluation of capacitated-flow networks 20. Hudson JC, Kapur KC (1985) Reliability bounds for multistate
with budget constraints. IIE Trans (Institute of Industrial Engi- systems with multistate components. Oper Res 33(1):153–160.
neers) 30(12):1175–1180. https://​doi.​org/​10.​1080/​07408​17980​ https://​doi.​org/​10.​1287/​opre.​33.1.​153
89665​74 21. Bai G, Zuo MJ, Tian Z (2015) Ordering heuristics for reliability
5. Hudson JC, Kapur KC (1983) Reliability analysis for multistate evaluation of multistate networks. IEEE Trans Reliab 64(3):1015–
systems with multistate components. IIE Trans (Institute of Indus- 1023. https://​doi.​org/​10.​1109/​TR.​2015.​24304​91
trial Engineers) 15(2):127–135. https://​doi.​org/​10.​1080/​05695​ 22. Aggarwal KK, Gupta JS, Misra KB (1975) A simple method for
55830​89746​23 reliability evaluation of a communication system. IEEE Trans
6. Aven T (1985) Reliability evaluation of multistate systems with Commun 23(5):563–566. https://​doi.​org/​10.​1109/​TCOM.​1975.​
multistate components. IEEE Trans Reliab R-34(5):473–479. 10928​38
https://​doi.​org/​10.​1109/​TR.​1985.​52222​35 23. Ford LR, Fulkerson DR (2015) Flows in networks. Flows Netw.
7. Datta E, Goyal NK (2021) An efficient approach to find reli- https://​doi.​org/​10.​2307/​30074​01
able topology of stochastic flow networks under cost constraint. 24. MathWorks (2018) “MATLAB”
Int J Inform Technol (Singapore). https:// ​ d oi. ​ o rg/ ​ 1 0. ​ 1 007/​ 25. Chen SG, Lin YK (2012) Search for all minimal paths in a general
s41870-​020-​00555-0 large flow network. IEEE Trans Reliab 61(4):949–956. https://d​ oi.​
8. Lin JS (2016) Reliability evaluation of a multicommodity capaci- org/​10.​1109/​TR.​2012.​22208​97
tated-flow network in terms of minimal pathsets. Int J Inf Manage 26. Nahman JM (1994) Enumeration of minimal paths of modified
Sci 27(3):269–281. https://​doi.​org/​10.​6186/​IJIMS.​2016.​27.3.4 networks. Microelectron Reliab 34(3):475–484. https://​doi.​org/​
9. Fardis MN, Cornell CA (1981) Analysis of coherent multistate 10.​1016/​0026-​2714(94)​90086-8
systems. IEEE Trans Reliab R-30(2):117–122. https://​doi.​org/​10.​ 27. Yeh WC (2007) A simple heuristic algorithm for generating all
1109/​TR.​1981.​52210​02 minimal paths. IEEE Trans Reliab 56(3):488–494. https://d​ oi.o​ rg/​
10. Lin J-S, Jane C-C, Yuan J (1995) On reliability evaluation of a 10.​1109/​TR.​2007.​903290
capacitated-flow network in terms of minimal pathsets. Networks 28. Meghanathan N (2017) “Breadth First Search”, routing protocols
25(3):131–138. https://​doi.​org/​10.​1002/​net.​32302​50306 and graph theory algorithms for mobile. Ad Hoc Netw. https://d​ oi.​
11. Janan X (1985) On multistate system analysis. IEEE Trans Reliab org/​10.​4018/​978-1-​5225-​2227-0.​les3
R-34(4):329–337. https://​doi.​org/​10.​1109/​TR.​1985.​52221​78 29. MathWorks (2019) Cell arrays ; Strings. https://​www.​mathw​orks.​
12. Lin YK (2001) A simple algorithm for reliability evaluation of com/​help/​matlab/​cell-​arrays.​html. Accessed 27 Jul 2021
a stochastic-flow network with node failure. Comput Oper Res 30. (1971) Solving integer programs by enumeration. Math Sci Eng
28(13):1277–1285. https://​d oi.​o rg/​1 0.​1 016/​S 0305-​0 548(00)​ 76(C): 81–102, https://​doi.​org/​10.​1016/​S0076-​5392(08)​61099-1
00039-3 31. Fass D (2004) CARTPROD: Cartesian product of multiple sets.
13. Lin YK, Huang CF (2013) Stochastic flow network reliability https://​www.​mathw​orks.​com/​matla​bcent​ral/​filee​xchan​ge/​5475-​
with tolerable error rate. Qual Technol Quant Manag 10(1):57–73. cartp​rod-​carte​sian-​produ​ct-​of-​multi​ple-​sets. Accessed 17 Aug
https://​doi.​org/​10.​1080/​16843​703.​2013.​11673​308 2021
14. Lin YK, Yeh CT, Huang CF (2013) Reliability evaluation of a 32. Zuo MJ, Tian Z, Huang HZ (2007) An efficient method for reli-
stochastic-flow distribution network with delivery spoilage. Com- ability evaluation of multistate networks given all minimal path
put Ind Eng 66(2):352–359. https://d​ oi.o​ rg/1​ 0.1​ 016/j.c​ ie.2​ 013.0​ 6.​ vectors. IIE Trans (Institute of Industrial Engineers) 39(8):811–
019 817. https://​doi.​org/​10.​1080/​07408​17060​10136​53
15. Chiu YH, Lin YK, Nguyen TP (2021) Network reliability of a 33. Lin YK, Yeh CT (2013) A two-stage approach for a multi-objec-
stochastic online-food delivery system with space and time con- tive component assignment problem for a stochastic-flow network.
straints. Int J Perform Eng 17(5):433–443. https://​doi.​org/​10.​ Eng Optim 45(3):265–285. https://​doi.​org/​10.​1080/​03052​15X.​
23940/​ijpe.​21.​05.​p3.​433443 2012.​669381
16. Das D, Tripathy CR, Tripathy PK, Kabat MR (2020) System 34. Aissou A, Daamouche A, Hassan MR (2021) Components assign-
reliability estimation of constrained multi-state computational ment problem for flow networks using MOPSO. IAENG Int J
grids. Int J Inform Technol (Singapore). https://​doi.​org/​10.​1007/​ Comput Sci 48(1)
s41870-​018-​0132-1 35. Brailsford SC, Potts CN, Smith BM (1999) Constraint satis-
17. Chang PC (2022) Theory and applications of an integrated model faction problems: algorithms and applications. Eur J Oper Res
for capacitated-flow network reliability analysis. Comput Ind Eng. 119(3):557–581. https://d​ oi.o​ rg/1​ 0.1​ 016/S
​ 0377-2​ 217(98)0​ 0364-6
https://​doi.​org/​10.​1016/j.​cie.​2021.​107877
18. Bai G, Liu T, Zhang Y, Tao J (2020) An improved method for Springer Nature or its licensor (e.g. a society or other partner) holds
reliability evaluation of two-terminal multistate networks based on exclusive rights to this article under a publishing agreement with the
state space decomposition. IEEE Trans Reliab 70(3):1084–1095. author(s) or other rightsholder(s); author self-archiving of the accepted
https://​doi.​org/​10.​1109/​tr.​2020.​29889​87 manuscript version of this article is solely governed by the terms of
19. Hudson JC, Kapur KC (1983) Modules in coherent multistate such publishing agreement and applicable law.
systems. IEEE Trans Reliab R-32(2):183–185. https://​doi.​org/​
10.​1109/​TR.​1983.​52215​22

13