:

19

.

, . , , , . 12 . 12 ; , E:

  • E F , [E], B, D.
  • B: B F A [E, B].
  • D: D F C [E, D].
  • C: C F A [E, D, C]

A? , , . . , , , , . , , ( , ). , E B, A . .

. 12

,

  • .
  • , .
  • , .
  • , .
. , . , . .

, .

:

  • E F B [E] 100.
  • B F A [E, B] 100.
  • E F D [E] 100.
  • D F C [E, D] 100.
  • C F A [E, D, C] 100.

A , , , , , , . A [E, B]. A , , C, C , 100, [E, B, A], [E, D, C]. , C . , , . , C, F . , , :

  • E F B [E] 100.
  • B F A [E, B] 100.
  • E F D [E] 50.
  • D F C [E, D] 50.
  • C F A [E, D, C] 50.

A : 100, 50.

:

  • A , [E, B], C
  • C , [E, B, A], D.
  • D , [E, B, A, C], E.
  • E , E .

, () , .


, , , , , . , , , , , ( ), . , - , . ?

, , ( ) , - , , P. , P, , () . NP- , NP-, , . , .

NP-complete, , , , , , .


, , . , , , , , , jitter , . . , , , .

, , (QoS) , . , , (LFA / rLFA). , :

, ( ), (, )?

, (, , ) .


- , , () (). :

  • ; .
  • , - .

. 13 , .

. 13

A X F:

  • [X, A, B, E, F] [X, C, F]
  • [X, A, B, F] [X, C, F]

B G L: [G, K, L] [G, H, L]. Z , . F G , . [F, G] . , 13, X Z.


1974 . , , SPF- . SPF , , SPT, SPF . , , , SPT. 14-18.

14 SPF SPT. . , SPT , , . F X, , .

. 14       ,  1

( ) SPT , ( ), SPT, . . 14 , - .

15.

15 ; , SPT ( , ), , , , SPT (, , ), . , ; . :

  • u, v. , .
  • v u v.
  • u.
. 15       ,  2

s: d[sp](u,v) = d(u,v) ? d(s,v) + d(s,u)

, 0, , [B, E]:

  • B - u, E - v, A - s
  • d(u,v) = 2, d(s,v) = 3, d(s,u) = 1
  • 2 ? 3 + 1 = 0

, , ( ) . 15:

[B, A] ( [A, B] ):

  • B - u, A - v, A - s
  • d(u,v) = 0, d(s,v) = 0, d(s,u) = 1
  • 0 ? 0 + 1 = 1

[E,B]:

  • E u, B v, A - s
  • d(u,v) = 2, d(s,v) = 1, d(s,u) = 3
  • 2 ? 1 + 3 = 4

[C,A]:

  • C u, A v, A s
  • d(u,v) = 2, d(s,v) = 0, d(s,u) = 2
  • 2 ? 0 + 2 = 4

[F,D]:

  • F u, D v, A s
  • d(u,v) = 1, d(s,v) = 4, d(s,u) = 5
  • 1 ? 4 + 5 = 2

[D,B]:

  • D u, B v, A s
  • d(u,v) = 1, d(s,v) = 1, d(s,u) = 2
  • 1 ? 1 + 2 = 2

, 16, , , , SPT ( Z), () , SPF , SPT .

SPT, X Z [A,B,D,F]. , ( ), , , . [A, B,D,F] . , [A,B] A B, B A. - SPF , , . 17.

17 , . [B,D], . X Z:

  • [A,B,D,F]
  • [A,C,D,B,E,F]
. 16       ,  3 . 17       ,  4

, , , , , ; : [A->B, B->E, E->F, A->C, C->D, D->F]

- , [B-> D] [D-> B]. : [A, B, E, F] [A, C, D, F].

, , , .


(Maximally Redundant Trees-MRT). MRT - Depth First Search (DFS), DFS. 18 .

. 18    Depth First Search

18 . - , DFS. , DFS, , , :

01 main {
02 dfs_number = 1
03 root.number = dfs_number
04 recurse_dfs(root)
05 }
06 recurse_dfs(current) {
07 for each neighbor of current {
08 child = left most neighbor (not visited)
09 if child.number == 0 {
10 dfs_number++
11 child.number = dfs_number
12 if child.children > 0 {
13 recurse_dfs(child)
14 }
15 }
16 }
17 }

- , , . 18:

  • recurse_dfs A root.
  • recurse_dfs, A B.
  • B , if 09 .
  • B DFS ( 11).
  • B ( 12), recurse_dfs B .
  • ( ) recurse_dfs, B, E.
  • E DFS, if 09 .
  • E DFS (3)
  • E , .
  • F B, , .
  • F , if 09 .
  • F DFS (4).
  • B , for 07 , recurse_dfs .
  • recurse_dfs - , 14. A.
  • C - A, , C.

18 :

  • A , D, [A, C,G,D].
  • D DFS, A, [D, A].
  • .

, DFS: , , , . , MRT . DFS , . - , ( Minimum Spanning Tree MST), DFS. , MRT , , . 19 .

MRT ( SPF ). A, [A, B, C, D]. , , . [A, D, C, B] , , . .

. , [A, D, F, E, B], - [A, B, E, F, D]. : , - ? DFS.

. 19     MRT

, - . . DFS , , , .

, , DFS. , , . , B , C, [A, B, C, D] . , B C, , B C, . . , , MRT .


( ) . - . , . , , . , .

. . , , , , - , . , , . , .

, , - .

:

  • , , , - , , .
  • . , . .
  • , . , , ( ) , .

>