Large-scale Network Survivability Association Model based on Set Pair Analysis Theory

Ruiqing Jing¹^* ,Jun Lu^1,2 ,Jun Li¹ ,Kang Wan¹,Haoyu Zhang^1,2

1.College of Computer Science and Technology, Heilongjiang University
Key Laboratory of Database and Parallel Computing of HeilongjiangProvince

Harbin, China

824705780@qq.com, lujun111_lily@sina.com, lijun890223@sina.com, wankang1004@163.com,15364542@qq.com

Abstract—Large-scale network has the characteristics of complex system, and its survivability is different from simple network. The current network survivability studies usually only aim for a specific network level or type, and seldom investigate survivability from a system perspective. In this paper, the concept of large-scale network survivability is defined from the perspective of complex system, the survivability association is analyzed based upon the correlation characteristics of complex system, and the structural model of large-scale network survivability association is established and its properties are analyzed. On the basis of survivability association properties, the survivability association function is defined based upon set pair analysis theory, which is utilized to characterize the survivability association degree among subsystems in large-scale network. Finally, the effectiveness of the model proposed in this paper is validated through case study.

Keywords—large-scale network; survivability association; set pair analysis theory; complex system

I. Introduction

Network survivability refers to the ability of a network to provide basic services when it subjects to attacks, hardware or software failures or accidental events, and can restore full services in a timely manner [1~3]. Currently the research and applications of network survivability mostly confines to the possible invasion threats to the system, trying to establish a unified survivability strategy and management control, which is actually a manner of solving the problems of the whole system from the local point of view. For large-scale network survivability, this research method usually has significant limitations, and it is difficult to fundamentally improve the robustness of large-scale network and self-recovery capabilities when encountered attacks.

As a complex information system, large-scale network has complex system properties, usually unable to implement the overall survivability strategy and unified management. For example, the backbone of Internet has no global policies in consideration, the reason is that it does not exist a global management. Therefore, simple network survivability structure does not apply to open complex systems. Large-scale network survivability mainly considers the system as a whole to provide the critical services survivability. The theories and methods of large-scale network survivability should be investigated and proposed from the essential characteristics of large-scale network as an open complex system.

In this paper, we study large-scale network survivability association based on the complex system characteristics, and construct survivability association model based upon the Pair Set Analysis (PSA) theory. The structure is organized as follows: Section 2 presents large-scale network survivability association structure model, and describes the natures of survivability association structure. Section 3 establishes large-scale network survivability association function based upon PSA theory, and performs case study. Finally, Section 4 concludes the paper and points out further work.

II. The Survivability Association Model of LArge-scale Network

A. The Concept of Large-scale Network

As a class of open complex system, we extend the concept of traditional network survivability to large-scale networks. For a large-scale network system S, when one or more subsystems S_i suffer internal or external disturbances such as external attack or system failure etc., S maintains continuous services through adaptation, configuration, restoration, and evolution etc., and make the entire network far away from failure status. This behavioral characteristic is called survivability.

Survivability is a fundamental characteristic of large-scale network, and would not disappear due to system evolution or external environment changes. In the large-scale network, there exists information exchange between the failed subsystems and other subsystems, and thus may cause the cascaded failures. The increase of failed subsystems may cause the whole large-scale network failure.

B. The Survivability Structure Model of Large-scale Network

For survivability association among each subsystems of large-scale network, when the variable characterizing the survivability status of subsystem changes at time , the variable characterizing the survivability status of another associated subsystem also changes, in which subsystem is attack source, and subsystem is attack target. In large-scale network, all of survivability associations consists of the set of survivability associations in large-scale network,, and the relationship between attack source and attack target is shown as Fig.1 (a).

The forms of large-scale network survivability associations.

The survivability associations among subsystems in large-scale network have transitive property, if subsystem has survivable effects on subsystemand has survivable effects on , then has survivable effects on. The survivability associations also have reflexivity, i.e. subsystem has survivable effects on its own. However, survivability associations generally do not have symmetrical property. The mutual survivability associations among subsystems are defined as bilateral survivability associations, as shown in Fig. 1(b).

Definition 1. For two subsystems with survivability associations in large-scale network, there exists the following equation

(1)

In formula (1), and represent the survivability status of subsystem and at time respectively.

The unilateral and bilateral survivability associations are two basic survivability association manners, the various survivability association structures in large-scale network can be seen as a combination of a number of unilateral and bilateral survivability structures. In many cases, multiple subsystems are linked through unilateral or bilateral survivability structures, and constitute survivability chain or ring:

(1) Unilateral survivability chain: multiple subsystems in large-scale network are only related through unilateral survivability association structure with the same direction, and form the survivability chain, as shown in Fig. 1(c).

(2) Bilateral survivability chain: the survivability chains composed of multiple subsystems in large-scale network at least contain one bilateral survivability association structure, the chain of invulnerability by a number of subsystems consisting of large-scale networks, including at least one bilateral invulnerability associated structure called the bilateral relations invulnerability chain, as shown in Fig. 1(d).

(3) Complete bilateral survivability chain: all of the survivability chains composed of multiple subsystems in large-scale network are bilateral associations. This is a special case of bilateral survivability chain, as shown in Fig. 1(e).

The bilateral survivability chain can be broken down into a combination of multiple unilateral survivability chains. For example, the bilateral survivability chain in Fig. 1(d) can be broken down into the following two bilateral survivability association forms, as shown in Fig. 2.

Bilateral survivability chain decomposed into unilateral survivability associations.

Accordingly, the survivability ring structures of large-scale network include the unilateral, bilateral and complete bilateral survivability ring forms. Like bilateral survivability chain, bilateral survivability ring can also be broken down into a combination of multiple unilateral survivability rings and chains. Similarly, complete bilateral survivability ring can be decomposed into a combination of two opposing unilateral survivability rings.

C. The Natures of Large-scale Network Survivability Association Structure

The relationships among attack events, survivability status and survivability risks in large-scale network can be defined as the following transformation forms based upon the input/output, transformation function and related definitions in classical control theory, as shown in Fig. 3.

The transformation of large-scale network survivability.

Where, refers to the form of attack event having effect on large-scale network. The overall survivability status refers to the status variable characterizing the overall survivability features of S. The survivability risk refers to the risk function of large-scale network failure. The survivability structure contains two aspects:

(1) Large-scale network survivability association refers to the survivability association manner among various subsystems in system S, ;

(2) Large-scale network survivability status refers to the status variables characterizing the survivability features of subsystems in S, , in which ，in which is the status variable describing the survivability of .

Definition 2. The overall survivability status of large-scale network can be depicted as

(2)

Definition 3. There exists the following equation based upon the input/output relationships of large-scale network

(3)

Definition 4. There exists the following equation based upon the input/output relationships of large-scale network

(4)

According to the survivability transformation model and related definitions of large-scale network, we can draw the following conclusions:

Theorem 1. The survivability status variable in large-scale network can be expressed as the function of attack event , the effect form of attack event on system S and survivability association form among subsystems.

Proof. First mark the subsystems on survivability chain, S_i is labeled as , the adjacent subsystem is labeled as , as so on. There are at least one another subsystem S_j that exists survivability association, as shown in Fig. 4.

The chain of large-scale network survivability associations.

According to definition 3, the following equations are established:

(5)

According to the above formulas, we can conclude that there exists equations making

(6)

In the formula (6), , that is

(7)

There is a relationship between survivability environment and subsystem S_i. We can use the same method to mark the subsystems on survivability chain, subsystem S_i is labeled as which is directly affected by attack event, the adjacent subsystem is labeled as , etc., shown as Fig. 5.

The large-scale network survivability chain.

Then, we have the following expressions:

(8)

According to the above expressions, we can obtain the following equation:

(9)

In formula (9),

That is,

(10)

Finally, we obtain the following equations by synthesizing the above two cases:

(11)

(12)

QED.

As can be seen from the above proof procedure, the survivability status in large-scale network is the function of attack event , the affect form of attack event on system, and survivability association R_s among subsystems. Therefore, the various elements on large-scale network survivability model are not isolated, they are interrelated and mutual restraint through attack events and their affect form. That is, there is a certain relationship among them.

III. The Association Function of Large-scale Network Survivability

When a subsystem in large-scale network fails due to the impact of internal or external disturbances, the effects on other subsystems can be analyzed by utilizing the survivability association function among multiple subsystems. For the large-scale network, the degree of survivability transmission and expansion among subsystems is related with survivability association function among them. Typically, the variables of survivability association function contains the similarity degree of survivability status among subsystems in large-scale network. Below, we investigate and propose the survivability association function of large-scale network.

A. Overview of Set Pair Analysis Theory

Set Pair Analysis (SPA) is a system analysis method widely used in system control, decision making, fuzzy mathematics, artificial intelligence, entropy theory and other aspects of social science research [4~6]. Set pair refers to the pair of two set with a certain relationship.

We can obtain N features by analyzing the characteristics of the argued two set, in which there are Q features shared by two set in the set pair, P features opposed and the rest features neither opposite nor unified. Then,

(1) refers to the unified degree of these two set under issue W, represented as a;

(2) refers to the opposite degree of these two set under issue W, represented as b;

(3) refers to the diversity degree of these two set under issue W, represented as c.

The unified, opposite and diversity degree under the argued issue is represented as

(13)

Where, a is the unified degree, b is the opposite degree, c is the diversity degree, , .

In the above definition, variables all should satisfy the normalization condition, namely

(14)

Since a and b in formula (14) are determined, and c is uncertain, set pair analysis can effectively express the relationships of unity of opposites in the certain or uncertain systems.

B. Survivability Association Function

Assuming there are two subsystems X and Y in large-scale network S, we inspect the set of status vectors of two subsystems, in which the status vector of subsystem X is depicted as , , and the status vector of subsystem Y is depicted as , . If both subsystems have n measurable status, then the variation degree of these status vectors under interference would be able to play a key role in the normal operation of the whole subsystem.

If subsystem X fails under interference and subsystem Y has survivability association with X, the status vector of Y at least has a status y_j that is affected by survivability association and is changed catastrophically, that is it reaches the range of subsystem not function normally corresponding with this status changes, then we call that y_j is survivability identical with subsystem X. And other status not affected at all are called survivability opposite with subsystem X. If some status tend to identical or opposite with the evolution of time, then these status are called survivability fluctuant with subsystem X.

Definition 5. The identical degree of survivability of subsystem Y at time t is , if there is no status identical with subsystem X, then .

Definition 6. The opposite degree of survivability of subsystem Y at time t is , if there is no status opposite with subsystem X, then .

Definition 7. The fluctuant degree of survivability of subsystem Y at time t is , if there is no status fluctuant with subsystem X, then .

Definition 8. The survivability weight coefficient vector , which are corresponding with each status variable in subsystem Y respectively. They mean that if subsystem X fails, the degree of influence on the whole system if each status variable in subsystem Y fails separately.

The survivability weight coefficient is 1 when is survivability identical with subsystem X, the survivability weight coefficient is 0 when is survivability opposite with subsystem X, and the survivability weight coefficient is in [0, 1] when is survivability fluctuant with subsystem X. Therefore, the survivability status association function of large-scale network can be measured with identical, opposite and fluctuant degree of survivability between subsystems.

Definition 9. The large-scale network survivability status association function F is:

(15)

Where, a, b, c are the identical, opposite and fluctuant degree of survivability between two subsystems respectively, and is a function of the time t. Therefore, the change rate of large-scale network survivability status association function with the evolution of time is denoted with , i.e.

(16)

The change rate of survivability association reflects the change degree of survivability association between subsystems. When , the survivability association between subsystems would become closer; when , it would gradually lose contact; and when , it would keep unchanged.

For two subsystems with close survivability associations, if one of them suffers attack and fails, then another one would inevitably suffer a devastating impact. By reducing the survivability association degree among each subsystem, the collapse of the entire large-scale network can be avoided even if one subsystem suffers attack. The survivability association among each subsystem in large-scale network can be analyzed based on the above proposed concepts including large-scale network survivability association function, and the identical, opposite and fluctuant degree of survivability, etc.

C. Case Study

There are three subsystems in a large-scale network which have complete survivability associations among them, and any of them suffers failures would affect the other two subsystems. Suppose that subsystem X fails under internal and external interferences, we investigate the survivability associations between subsystems Y, Z and X respectively. And the unified, opposite and diversity degree of associations are established respectively based on set pair analysis theory:

(17)

(18)

Where, refer to the degree of survivability association between subsystems Y, Z and X; refer to the unified degree of survivability between subsystems Y, Z and X; refer to the opposite degree of survivability between subsystems Y, Z and X; refer to the fluctuant degree of survivability between subsystems Y, Z and X; and ,.

Suppose subsystems Y, Z are described by 10 status vectors. Due to the failure of subsystem X, there are 5 status vectors of subsystem Y and 4 status vectors of subsystem Z whose values exceed the normal working ranges. There are 3 vectors of subsystem Y and 2 status vectors of subsystem Z that operate normally, which are not affected by the failure of subsystem X. And there are 2 status vectors of subsystem Y and 4 status vectors of subsystem Z whose values are fluctuant between normal and abnormal operation ranges. The unified, opposite and fluctuant degree of survivability of subsystems Y, Z are shown as Table 1.

The unified, opposite and fluctuant degree of survivability of subsystems Y, Zwith X

a_XY	a_XZ	b_XY	b_XZ	c_XY	c_XZ
0.5	0.4	0.3	0.2	0.2	0.4

According to the values of Table 1, formula (17) and (18) can be written as follows

(19)

(20)

Let , and consider the role of opposite degree in survivability association, then

(21)

(22)

Due to the effect of opposite degree of survivability, subsystems Y, Z will reduce the unified degree of survivability after the failure of subsystem X. Formula (21) and (22) shows that the final survivability association degree of large-scale network depends on the fluctuant degree of survivability. If subsystems Y, Z obtain the external support in timely manner, so as to maintain the normal operation, then the status of large-scale network would transform to the opposition of subsystem X failure. At this time , and the degree of survivability association would decrease accordingly. Let , then , which indicates that survivability association degree between Y and X is 0.1. And , which indicates that survivability association degree between Z and X is 0. The smaller of I means that the smaller of survivability association. Therefore, the survivability association degree between Y, Z and X can be analyzed by utilizing the concept of association degree.

IV. Conclusions

In this paper, we clarify the concept of large-scale network survivability from the perspective of complex system, analyze the survivability association of large-scale network based upon the association characteristics of complex system, and establish large-scale network survivability association structure model and analyze its natures. Then, we define the survivability association function of large-scale network based upon set pair analysis theory, which is used to depict the degree of survivability association among subsystems in large-scale network. Finally, we validate the effectiveness of the proposed model through case study. The future research work includes the dynamics of survivability association in large-scale network and the application of survivability association model to large-scale network analysis.

Acknowledgment

This work was supported by the National Natural Science Foundation of China under Grant No.61272518 and Research of the Information Access Technology for Complex Information System under Grant No.2013RC0208.

References

J. Ellison, D.A. Fisher, and R.C. Linger, Survivable Network System: An Emerging Discipline. Technical Report, CMU/SEI-97-TR-013, Carnegie Mellon University, 1997.
J. Ellison, D.A. Fisher, and R.C. Linger, “Survivability: Protectiong Your Critical Systems,”IEEE Internet Computing, vol. 3, issue 6, pp. 55-63, 1999.
Dan, Y.Q. Zhang, “Research on Definition of Network Survivability,” Journal of Computer Research and Development, vol. 43(Suppl.), pp. 525-529, 2006.
Q. Zhao, Set pair analysis and its preliminary applicatio. Hangzhou, Zhejiang Science and Technology Press, 2000.
Q. Zhao, A.L. Xuan, “Set Pair Theory – A New Theory Method of Non-Define and Its Applications,” System Engineering, vol. 14, issue 1, pp. 18-23, 1996.

Y.L. Jiang, C.F. Xu, “Advances in Set Pair Analysis Theory and its Applications,” Computer Science, vol. 33, issue 1, pp. 205-209, 2006.

文章版权归作者所有，未经允许请勿转载。

THE END