1229 words - 5 pages

3.1 denotation definition

Network topology can be formulated as an undirected graph G P P P P V , ( E ,W ) , where V P to be a node set comprised of IP routers or hosts and E P is a link set comprised of physical links. W P is the distance of physical link. In contrast, routing topology is formulated as an undirected graph G R R R R V , ( E ,W ) , where V R to be a node set comprised of traffic demand node pairs (source and

destination nodes) and E R is a link set comprised of routing links. W R is the traffic payload which the links

carry.

Notation definition:

N ：the number of network nodes.

L ：the number of network links.

P ：the set of serial number ...view middle of the document...

3) The link set ER of routing topology is achieved according to matrix C of network traffic demand and routing

e4(1)

E R ={e i

path matrix R ,

|( ei ∈E P )and(c j ×r ij = 1)}

4) The weight set W R of routing topology is achieved according to matrix C of network traffic demand and

routing path matrix R Load (e i ) =| P( ei)| ,iP( ei)={j |( j ∈P)and(c j × rj = 1)}. So a routing topology G R is constructed and an example is illustrated in Fig.1 (3) according to traffic demands in table

1.

4. INVULNERABILITY MODEL

4.1 The evaluating model of link effecting- value.

A concept of link effect value and the evaluating model of vital links set are given below:

[Definition 4] Link effect value: the extent to which network communication may be affected upon any link or links set failure for a given matrix of traffic. We denote the i th link effecting value as effect(e i ), which is the ratio of payload between the ith link and whole network.

(equations)

A measure expression of links set effect value is proposed below:

Now we give a definition of vital link set in order to achieve the link set which has the maximum link effect value.

[Definition 5] The vital link set includes some links, which have the minimum links and arrive at the maximum link effect value allowed by the capability of network communication. We denote K to represent this set. So the value of network invulnerability is represented as:

4.2 The algorithm of selecting vital link set:

According to definition 4, K ⊆E R so the problem of getting an exact vital link set is an NP -hard combinatorial optimization problem. We propose a heuristic algorithm, which can achieve a vital link set quickly.

The algorithm of getting vital link set is below:

Initialization. K ={}； sele _ links ={} // K is vital link set， sele _ links is a candidate vital link set.

Constructing routing topology G = {V,E,R} and nodes pair set P(ei) according to matrix of traffic demands and routing algorithm, E = E

3) While (E sele !={} and effect(K )< upper) // upper ： The constraint threshold value of network communication, 0≤upper≤1{sele _links ={e |(e ∈E )and(max(| P(e ) |))} sele ie sele ={ei | (ei∈sele _ links)and (min(i))}

K ⇐K+e ； K ⇐K+e ; sele _ links = {}sele seleP(e ) =P(e ) −P(e ) }i i sele

4) End

We give an instance to select a vital link set according to above algorithm. A NSFNET with 14 nodes is given[7] (Fig.2) and a traffic demand exists between every node pair. Some vital link sets are...

Get inspired and start your paper now!