Computational Approach for Assessment of Critical Infrastructure in Network SystemsEmil KelevedjievInstitute of Mathematics and InformaticsBulgarian Academy of Sciences: Computational Approach for Assessment of Critical Infrastructure in Network Systems Emil Kelevedjiev Institute of Mathematics and Informatics Bulgarian Academy of Sciences
Critical infrastructure: Critical infrastructure Critical infrastructure is a term used by governments to describe material assets that are essential for the functioning of a society and economy.
Critical-infrastructure protection is the study, design and implementation of precautionary measures aimed to reduce the risk that critical infrastructure fails as the result of war, disaster, civil unrest, vandalism, or sabotage.
Slide3: In the USA's National Strategy for Homeland Security, which was issued in July 2002, critical infrastructure is defined as those
"systems and assets, whether physical or virtual, so vital to the United States that the incapacity or destruction of such systems and assets would have a debilitating impact on security, national economic security, national public health or safety, or any combination of those matters."
Slide4: The thirteen sectors of critical infrastructures and the agency liaisons identified by the National Strategy for Homeland Security are the following:
Slide5: Agriculture – Department of Agriculture
Food – Departments of Agriculture and Health and Human Services
Water – Environmental Protection Agency
Public Health – Department of Health and Human Services
Emergency Services – Department of Homeland Security
Government – Department of Homeland Security
Defense Industrial Base – Department of Defense
Information and Telecommunications – Department of Homeland Security
Energy – Department of Energy
Transportation – Department of Homeland Security
Banking and Finance – Department of the Treasury
Chemical Industry and Hazardous Materials – Department of Homeland Security
Postal and Shipping – Department of Homeland Security
Slide6: Sources:
USA Patriot Act of 2001, October 2, 2001
International CIIP Handbook 2004. Miriam Dunn and Isabelle Wigert. Critical Information Infrastructure Protection. ETH, Zurich.
Graph Theory : Graph Theory In Graph Theory, which is a part of mathematics and computer science, a graph is the basic concept.
Informally speaking, a graph is a set of objects called points or vertices connected by links called lines or edges.
Slide8: In a simple graph, which is by default undirected, a line from point A to point B is considered to be the same thing as a line from point B to point A.
In a digraph (short for directed graph) the two directions are counted as being distinct arcs or directed edges. Typically, a graph is depicted in diagrammatic form as a set of dots (for the points, vertices, or nodes), joined by curves (for the lines or edges).
Slide9: Many critical-infrastructure sectors may be modeled as graphs.
Networks:
transportation networks,
energy transmission networks,
etc.
Computational approach: Computational approach Connected components:
A graph is connected if there is a path connecting every pair of vertices. A graph that is not connected can be divided into connected components (disjoint connected subgraphs).
Slide12: Cut vertex (articulation point)
A cut vertex or articulation point is a type of graph vertex, the removal of which causes an increase in the number of connected components.
If the graph was connected before the removal of the vertex, it will be disconnected afterwards.
Slide13: Bridge
A bridge is an edge analogous to a cut vertex; that is, the removal of a bridge increases the number of connected components of the graph.
Slide14: Shortest path
The single-source shortest path problem is the problem of finding a path between two vertices such that the sum of the weights of its constituent edges is minimized.
More formally, given a weighted graph (that is, a set V of vertices, a set E of edges, and a real-valued weight function f : E → R), and given further one element v of V, find a path P from v to each v' of V so that it is minimal among all paths connecting v to v' .
Slide15: A solution to the shortest path problem is sometimes called a pathing algorithm. The most important algorithms for solving this problem are:
Dijkstra's algorithm — solves single source problem if all edge weights are greater than or equal to zero.
Bellman-Ford algorithm — solves single source problem if edge weights may be negative.
Floyd-Warshall algorithm — solves all pairs shortest paths.
Slide16: Example: Shortest Path Problem
http://www.asu.edu/it/fyi/unix/helpdocs/statistics/sas/sasdoc/ sashtml/ormp/chap4/sect62.htm
Whole pineapples are served in a restaurant in London. To ensure freshness, the pineapples are purchased in Hawaii and air freighted from Honolulu to Heathrow in London. The following network diagram outlines the different routes that the pineapples could take.
Slide18: The cost to freight a pineapple is known for each arc:
Honolulu Chicago 105
Honolulu San Francisco 75
Honolulu Los Angeles 68
Chicago Boston 45
Chicago New York 56
San Francisco Boston 71
San Francisco New York 48
San Francisco Atlanta 63
Los Angeles New York 44
Los Angeles Atlanta 57
Boston Heathrow London 88
New York Heathrow London 65
Atlanta Heathrow London 76
Slide19: The best route for the pineapples is:
from Honolulu
to Los Angeles
to New York
to Heathrow London.
Slide20: Spanning tree
A spanning tree of a connected, undirected graph is a tree composed of all the vertices and some (or perhaps all) of the edges.
Informally, a spanning tree of a graph is a selection of edges of the graph that form a tree spanning every vertex. That is, every vertex is connected to the tree, but no cycles (or loops) are formed.
It follows, that every bridge of the graph must belong to the spanning tree.
A spanning tree of a connected graph can also be defined as a maximal set of edges that contains no cycle, or as a minimal set of edges that connect all vertices.
Slide22:
The first algorithm for finding a minimum spanning tree was developed by Czech scientist Otakar Borůvka in 1926.
Its purpose was an efficient electrical coverage of Bohemia.
There are now two algorithms commonly used, Prim's algorithm and Kruskal's algorithm
Network Resource SystemsCritical Infrastructure Assessment: Network Resource Systems Critical Infrastructure Assessment
Slide24: A theoretical model and an experimental computer interactive implementation are proposed for predicting critical behaviors of a large networks flow system.
A possible application is management of the critical infrastructure in a water supplying system or an electricity power submission network.
A model is based on linear programming approach to find solutions in multi-stage in time multi-criteria optimization of the involved graph flow problem. Due to the ability of interactive re-computing with different sets of input and control data, an expert using the proposed implementation can perform the adequate decision making.
EXAMPLE: MANAGEMENT OF WATER RESOURCE SYSTEM: EXAMPLE: MANAGEMENT OF WATER RESOURCE SYSTEM Minimization of the total shortage
Equalization of shortages among all demands node for all time periods
Maximization of available water
Minimization of total spillage
Minimization of the deviation of reservoir storage form its target storage
Etc.
Slide27: Model’s variables. The process involves several time steps t = 1, 2, ..., T. For each node j = 1, 2, ..., n and for each time moment t = 1, 2, ..., T, the following variables are introduced:
u(j,t) – amount by which the volume of j-th node increases at the t-th time step,
v(j,t) –amount by which the volume of j-th node decreases at the t-th time step,
r(j,t) – current volume.
Slide28: Some nodes are considered as sources. For them:
s(j,t) – inflow into the j-th node at the t-th time step.
Other nodes are sinks. For them:
d(j,t) – outflow from the j-th node at the t-th time step.
For each arc i=1, 2, …m, and for each time step t:
f(i,t) – flow through the i-th arc at the t-th time step.
Constrains in the Linear Model: Constrains in the Linear Model
1. Nodes accumulation: For those nodes j, that are reservoirs, and for any time step t:
r(j,t) = r(j, t0) + ∑{u(j,k)–u(j,k) : k = t0, ..., t}.
2. Continuity equations for each node j and for any time step t:
∑{f(i,t) : i A+(j)} – ∑{f(i,t) : i A-(j)} +
+ s(j,t) – d(j,t) + u(j,t) – v(j,t) = 0,
where:
A+(j) is the set of all such i, that the i-th arc is directed into the node j.
A-(j) is the set of all such i, that the i-th arc is directed off the node j.
Slide30: 3. Equality and inequality constrains for the variables:
3a. Storage of the reservoirs are within allowable limits:
rmin(j) ≤ r(j,t) ≤ rmax(j).
3b. Inflow from sources is equal to available quantities: s(j,t) = sconst(j,t).
3c. Demand values at any demand point: dmin(j) ≤ d(j,t) ≤ drequired(j).
3d. Pipe capacities (upper bounds) and operational limits (loewer bounds):
fmin(j) ≤ f(j,t) ≤ fmax(j).
Slide31: The goal function of the Linear programming problem:
min: {C1(j,t)d(j,t)} + {C2(j,t)f(j,t)} +
+ {C3(j,t)u(j,t)} + {C4(j,t)v(j,t)},
where C1(j,t), C2(j,t), C3(j,t) and C4(j,t) are constants. Their values are chosen by experts during the interactive mode communication with the modeling system. Typically:
C1(j,t) << 0 or >> 0, depending on node’s purpose, where the flows that go out the system. The other constants C2(j,t), C3(j,t) and C4(j,t) are taken close to the init values.
Slide32: Numerical Experiments:
Water: Calculations are made for a really existing system including the upper part of Iskar river (near Sofia).
Two main cases (scenarios) are considered: normal operation and situation of a shortage
Slide33: Electricity: High-voltage transmission network in Bulgaria.
Operation behavior is modeled to minimize shortages at some type of critical accidents.
Also some perspective planning for expansion of the system can be modeled.
Slide34: Thank you for your attention