Trong phÇn m« pháng c¸c thuËt to¸n ®Þnh ®­êng kh«ng thÝch nghi ta sÏ xem xÐt ®Õn thuËt to¸n Dijkstra (1959) cßn gäi lµ thuËt to¸n Shortest Path Routing, thuËt to¸n Dijkstra c¶i tiÕn, thuËt to¸n ®Þnh luång c¬ së vµ mét sè øng dông cña chóng trong viÖc ®Þnh ®­êng tèi ­u.

6.1.1. Shortest Path Routing : (thuËt to¸n Dijkstra - 1959)

§å thÞ trong thuËt to¸n nµy gåm mçi ®iÓm ®¹i diÖn cho mçi router cña m¹ng, cung gi÷a 2 ®iÓm cña ®å thÞ lµ ®­êng ®i gi÷a 2 router trong m¹ng. ViÖc chän ®­êng ®i gi÷a 2 nót trong m¹ng lµ t×m ®­êng ®i ng¾n nhÊt gi÷a chóng. Mçi nót ®­îc g¸n nhËn víi kho¶ng c¸ch cña nã tíi nguån. B¾t ®Çu c¸c nót lµ v« tËn, råi nguån xÐt c¸c nót c¹nh nã, c¸c nót nµy sÏ cã nh·n hoÆc dù kiÕn hoÆc x¸c ®Þnh. C¸c nh·n cã thÓ thay ®èi, ph¶n ¸nh con ®­êng tèt h¬n, khi ph¸t hiÖn nh·n lµ con ®­êng ng¾n nhÊt têi nguån tíi nót, th× nã lµ cè ®Þnh (permanent) vµ sau ®ã kh«ng thay ®æi. Mçi nót cã chøa mét nh·n víi ®é dµi tõ nót nguån cho tíi nã. Lóc ban ®Çu, th× ®­êng ®i nµy ch­a ®­îc biÕt, v× vËy tÊt c¶ c¸c nót ®­îc g¸n lµ v« cùc. ThuËt to¸n sÏ t×m ra ®­êng ®i vµ xö lý chóng, mçi nh·n cã sù thay ®æi, ph¶n ¸nh ®­êng ®i. Mét nh·n sÏ chøa hoÆc lµ nh·n t¹m hoÆc lµ nh·n cè ®Þnh. §Çu tiªn, tÊt c¶ c¸c nh·n sÏ lµ nh·n t¹m, khi c¸c nh·n ®­îc t×m ra th× nã sÏ ®¹i diÖn cho mét nót trªn ®­êng ®i tõ nguån tíi nã, nh·n ®ã sÏ ®­îc g¸n nh·n cè ®Þnh vµ kh«ng thay ®æi vÒ sau.

VÝ dô: T×m ®­êng ®i ng¾n nhÊt tõ A ® D trong ®å thÞ sau:

                                 B              3              C

                            4                                        2

                        A                            3                   D

                            2                                           1

                                 F            3                 E

XuÊt ph¸t tõ A cã 2 ®Ønh B vµ F liªn thuéc víi A nªn chØ cã hai ®­êng ®i xuÊt phÊt tõ A lµ  A, B vµ A, F víi c¸c ®é dµi t­¬ng øng lµ 4 vµ 2. Do ®ã F lµ ®Ønh gÇn A nhÊt. B©y giê ta t×m ®Ønh tiÕp theo gÇn A nhÊt trong tÊt c¶ c¸c ®­êng ®i qua A vµ F (cho ®Õn khi ®¹t tíi ®Ønh cuèi cïng). §­êng ®i nh­ thÕ ng¾n nhÊt tíi B lµ A, B víi ®é dµi lµ 4 vµ ®­êng ®i nh­ thÕ ng¾n nhÊt tíi E lµ A, F, E ®é dµi 5. Do v©y ®Ønh tiÕp theo lµ B. §Ó t×m ®Ønh thø 3 gÇn A nhÊt, ta chØ xÐt c¸c ®­êng qua A, F vµ B. §ã lµ ®­êng ®i A, B, C ®é dµi lµ 7vµ ®­êng ®i A, F, E , D ®é dµi lµ 6. VËy D lµ ®Ønh tiÕp theo gÇn A nhÊt va ®é dµi cña ®­êng ®i ng¾n nhÊ tõ A tíi D lµ 6.

Tuy nhiªn ph­¬ng ph¸p nµy kh«ng thÓ dïng cho ng­êi vµ m¸y trong tr­êng hîp khi ®å thÞ cã nhiÒu c¹nh.

Thñ tôc m« pháng:

Khai b¸o:

Type nodelabel

    predecessor As Integer

             length As Long

                labl As Boolean

End Type

Dim so (1 To 6, 1 To 6) As Integer

Dim path (1 To 10) As Integer

Private Sub short(s As Integer, t As Integer, dd As Integer, kc As Integer)

Dim state(1 To 6) As nodelabel

Dim i,j,min,dem,infinity As Integer

infinity = 32767

For i = 1 To n

  For j = 1 To n

    If so(i, j) = -1 Then

      so(i, j) = infinity

    End If

  Next j

Next i

 If s = t Then

    dd = 1

    path(dd) = s

 Else

   For i = 1 To n

      state(i).predecessor = 0

      state(i).length = infinity

      state(i).labl = False

   Next i

    state(t).length = 0

    state(t).labl = True

    k = t

    Do While k <> s

      For i = 1 To n

       If (so(k, i) <> 32767) And (state(i).labl = False) Then

         If (state(k).length + so(k, i)) < state(i).length Then

               state(i).predecessor = k

               state(i).length = state(k).length + so(k, i)

         End If

       End If

      Next i

       min = infinity

       k = 0

    For i = 1 To n

     If (state(i).labl = False) And (state(i).length < min) Then

             min = state(i).length

             k = i

     End If

    Next i

       state(k).labl = True

    Loop

    k = s

    i = 0

    Do

      i = i + 1

      path(i) = k

      k = state(k).predecessor

    Loop While k <> 0

    dd = i

    kc = state(s).length

  End If

End Sub

Trong ®ã:  s : nót nguån

                   t : nót ®Ých

         so(i,j) : ma trËn ®å thÞ cña m¹ng

            path : m¶ng l­u ®­êng ®i

               dd : sè nót ®­êng ®i ng¾n nhÊt t×m ®­îc ®i qua

                 kc : kho¶ng c¸ch ng¾n nhÊt.

6.1.2. ThuËt to¸n Dijsktra : (sö dông cho ®Þnh ®­êng tËp trung)

Cïîng víi d÷ liÖu ®Çu vµo nh­ thuËt to¸n trªn, nh­ng thuËt to¸n nµy ®­îc m« t¶ nh­ sau: Gäi C lµ tËp hîp c¸c ®Ønh ch­a ®­îc chän, S lµ tËp hîp c¸c ®Ønh ®­îc chän. T¹i mçi thêi ®iÓm, tËp S chøa c¸c ®Ønh mµ kho¶ng c¸ch nhá nhÊt tõ nguån ®Õn chóng ®· ®­îc x¸c ®Þnh. Khi ®ã tËp C chøa c¸c ®Ønh cßn l¹i. Gi¶i thuËt b¾t ®Çu tËp S chøa ®Ønh nguån, khi gi¶i thuËt kÕt thóc th× tËp S  chøa tÊt c¶ c¸c ®Ønh cña ®å thÞ. T¹i mçi b­ãc ta chän mét ®Ønh cña tËp C mµ kho¶ng c¸ch tõ nguån ®Õn ®Ých nµy lµ nhá nhÊt vµ ®­a vµo tËp S. Ta nãi r»ng ®­êng ®i tõ nguån ®Õn ®Ých kh¸c lµ riªng biÖt nÕu tÊt c¶ c¸c ®Ønh trung gian trªn ®­êng nµy ®Òu n»m ë trong tËp S. T¹i mçi b­íc cña gi¶i thuËt, mét m¶ng 1 chiÒu D dïng ®Ó chøa  chiÒu dµi ®­êng ®i riªng biÖt.

Gi¶ sö c¸c ®Ønh cña ®å thÞ ®­îc ®¸nh sè tõ 1 ®Õn n, kh«ng mÊt tÝnh tæng qu¸t ta chän ®Ønh nguån lµ1 vµ L lµ ma trËn chøa chiÒu dµi c¸c cung.

Ma trËn ®­îc m« t¶:

L[i,i] = 0 víi "i = 1..n

L[i,j]>=0 nÕu tån t¹i cung tõ ®Ønh i ®Õn j

L[i,j] = ¥ nÕu kh«ng tån t¹i cung tõ ®Ønh i ®Õn j.

S¬ ®å thuËt to¸n:

Thñ tôc :

Dim L(1 To 6, 1 To 6) As Long

Dim d(1 To 6) As Integer

Dim P(1 To 6) As Integer

Dim cc(1 To 6) As Integer

Dim path(1 To 6) As Integer

Private Sub dijkstra()

Dim i,j,k,mk,min,x,n,mx As Integer

For i = 1 To n

  For j = 1 To n

     If L(i, j) = -1 Then

        L(i, j) = 32767

     End If

  Next j

Next i

k = n - 1           'so phan tu cua tap C

For i = 2 To n

  cc(i - 1) = i     'C : tap cac dinh tu 2..n

  d(i) = L(1, i)

  P(i) = 1

Next i

For i = 1 To n - 2

  ' tim dinh  v thuoc C va D[v] nho nhat

  min = d(cc(1))

  mx = 1

  For j = 2 To k

    If d(cc(j)) < min Then

       min = d(cc(j))

       mx = j

    End If

  Next j

   'loai bo C[mx] ra khoi C

  mk = cc(mx)

  cc(mx) = cc(k)

  k = k - 1

  For j = 1 To k

    x = cc(j)

    If d(x) > d(mk) + L(mk, x) Then

       d(x) = d(mk) + L(mk, x)

       P(x) = mk

    End If

  Next j

Next i

End Sub

6.1.3.  ThuËt to¸n Dijkstra: (sö dông cho ®Þnh ®­êng ph©n t¸n)

ThuËt to¸n nµy dùa trªn mét d·y c¸c b­íc lÆp. Mét tËp ®Æc biÖt c¸c ®Ønh ®­îc x©y dùng b»ng c¸ch céng thªm mét ®Ønh trong mét b­íc lÆp. Thñ tôc g¸n nh·n ®­îc thùc hiÖn trong mçi lÇn lÆp ®ã. Trong thñ tôc g¸n nh·n nµy, ®Ønh w ®­îc g¸n nh·n b»ng ®é dµi ®­êng ®i ng¾n nhÊt tõ a ®Õn w chØ ®i qua c¸c ®Ønh thuéc tËp ®Æc biÖt. §Ønh ®­îc thªm vµo lµ ®Ønh cã nh·n nhá nhÊto víi c¸c ®Ønh ch­a cã trong tËp ®ã.

ThuËt to¸n Dijkstra ®­îc x©y dùng theo ph­¬ng ph¸p g¸n nh·n:

Procedure Dijkstra (G : ®å thÞ träng sè)

                                 {G cã c¸c ®Ønh a = v0 , v1 ...vn= z vµ träng sè w(vi , vj),

                                 víi w(vi , vj) = ¥ nÕu {vi , vj} kh«ng lµ c¹nh trong G}

for i:=1 to n

       L(vi) := ¥

       L(a) := 0

       S := Æ

{Ban ®Çu c¸c nh·n ®­îc khëi t¹o sao cho nh·n cña a b»ng 0, c¸c ®Ønh kh¸c b»ng ¥, S lµ tËp rçng}

while z Ï S

     begin

          u := ®Ønh kh«ng thuéc S cã nh·n L(u) nhá nhÊt

                   S := S È {u}

                   for tÊt c¶ c¸c ®Ønh v kh«ng thuéc S

                            if L(u) + w(u,v) < L(v) then L(v) := w(u,v)

                                    {thªm vµo S ®Ønh cã nh·n nhá nhÊt,

                                    vµ s÷a ®æi nh·n cña c¸c ®Ønh kh«ng thuéc S}

     end {L(z) = ®é dµi ®­êng ®i ng¾n nhÊt tõ a tíi z}

NhËn xÐt: Trong thuËt to¸n nµy khi tÝnh to¸n ®­êng ®i tõ nót nguån ®Õn nót n nµo ®ã, ta kh«ng cÇn biÕt gi¸ cña tÊt c¶ c¸c liªn kÕt trong m¹ng mµ chØ cÇn biÕt gi¸ tõ nót ®ã ®Õn c¸c nót l©n cËn cña nã vµ nh·n cña c¸c nót l©n cËn®ã. Nh­ vËy thuËt to¸n phï hîp víi ®Þnh ®­êng ph©n t¸n.

6.1.4. ThuËt to¸n ®Þnh luång c¬ së :

D÷ liÖu ®Çu vµo cña thuËt to¸n bao gåm :

·        Ma trËn luång c¬ së.

·        Ma trËn dung l­îng c¸c ®­êng.

KÕt qu¶ cho mét b¶ng th«ng tin bao gåm :

C¨n cø vµo, T (msec) (®é trÔ trung b×nh cña mçi ®­êng) vµ chän mét thuËt to¸n ®Þnh ®­êng (nh­ 2 thuËt to¸n nªu ë trªn) ta sÏ cã ®­êng ®i tõ nguån ®Õn ®Ých mµ cã xÐt ®Õn c¶ t¶i vµ topogoly.

6.2. ThuËt to¸n ®Þnh ®­êng thÝch nghi:

Trong phÇn nµy tr×nh bÇy ¸p dông cña thuËt to¸n §Þnh ®­êng vector kho¶ng c¸ch ®Ó cËp nhËt nh÷ng b¶ng ®Þnh ®­êng cho nh÷ng nót m¹ng vµ thuËt to¸n liªn kÕt tr¹ng th¸i.

ThuËt to¸n §Þnh ®­êng vector kho¶ng c¸ch:

D÷ liÖu vµo lµ b¶ng ®Þnh ®­êng nh÷ng nót l©n cËn ®èi víi mét nót muèn cËp nhËt b¶ng ®Þnh ®­êng vµ ®é trÔ tõ nót ®ã ®Õn nh÷ng nót l©n cËn. Mét b¶ng ®Þnh ®­êng míi sÏ ®­îc cËp nhËt cho nót nµy ®Õn tÊt c¶ c¸c nót kh¸c th«ng qua nh÷ng nót l©n cËn.

Gi¶ sö muèn cËp nhËt b¶ng ®Þnh ®­êng cho nót J, vµ gi¶ sö muèn cËp nhËt ®­êng ®i tõ J ®Õn C xem thö sÏ ®i qua tr¹m nµo, ta thÊy ®é trÔ tõ J qua nót I ®Õn C lµ ng¾n nhÊt, nªn ®­êng ®i tõ J ®Õn C ph¶i ®i qua nót I.

Trong m¹ng c¸c tr¹m cã mét b¶ng ®Þnh ®­êng nh­ vËy vµ th­êng ®­îc cËp nhËt th«ng qua c¸c b¶ng ®Þnh ®­êng cña c¸c tr¹m l©n cËn, sù cËp nhËt nµy cã thÓ ®­îc thùc hiÖn mét c¸ch tù ®éng th«ng qua mét giao thøc. ( vÝ dô giao thøc RIP - Routing Information Protocol th­êng ®­îc sö dông trong mét sè hÖ ®iÒu hµnh m¹ng nh­ : Windows NT Server ...,c¸c router ch¹y giao thøc nµy ®Òu ®Æng ph¸t qu¶ng b¸ b¶ng ®Þnh ®­êng cña nã 2 lÇn/phót, bÊt cø nót lµm viÖc nµo ch¹y RIP sÏ nhËn ®­îc th«ng tin nµy vµ tù ®éng cËp nhËt vµo b¶ng ®Þnh ®­êng cña m×nh).

V. GIAO THøC X.25 PLP

Cã chøc n¨ng qu¶n lý ghÐp nèi gi÷a DTE/ DTE ë 2 ®Çu nót m¹ng (end-to-end) vµ DTE/DCE trong ®ã DCE ®ãng vai trß nót m¹ng chuyÓn m¹ch gãi X.25. X25.PLP ®Þnh nghÜa 2 läai liªn kÕt logic:

- Liªn kÕt ¶o cã tÝnh t¹m thêi.

- Liªn kÕt ¶o ®­îc thiÕt lËp vÜnh viÔn.

1. D¹ng gãi tin X.25.PLP

0    0    0    1

§¸nh sè m¹ch ¶o

§¸nh sè m¹ch ¶o (12 bit)

Type (00001011)

Control (1)

§é dµi ®Þa chØ DTE

®­îc yªu cÇu

§é dµi ®Þa chØ DTE

yªu cÇu

§Þa chØ nguån

§Þa chØ ®Ých

§é dµi vïng khai b¸o thñ tôc phô

Khai b¸o lÇn l­ît c¸c thñ tôc sö dông

D÷ liÖu phô cã tÝnh chÊt th«ng b¸o(16bytes)

H×nh 3.9: §Þnh d¹ng gãi yªu cÇu thiÕt lËp liªn kÕt

                    1                                                                                   8

0    0    0    1

                            4bit

Sè hiÖu cña liªn kÕt logic 12 bits             8bit

Lo¹i th«ng tin

1

Th«ng tin bæ sung

H×nh 3.10 : §Þnh d¹ng gãi ®iÒu khiÓn

                  1                                                                                          8

Q

D

0      1     

 Sè hiÖu cña liªn kÕt logic 12 bit

Sè hiÖu gãi gëi

M

Sè hiÖu gãi ®ang chê ®Ó nhËn

0

D÷ liÖu

H×nh3.11: §Þnh d¹ng gãi d÷ liÖu

trong ®ã:M= 0 th× cßn tin vµ 1 lµ b¸o hÕt tin

D: ®Ó chØ thÞ vÒ c¬ chÕ b¸o nhËn gãi tin

Q: dïng ®Ó ®Þnh tÝnh th«ng tin chøa trong gãi tin

2. Trao ®æi gãi tin ë X 25.PLP

X25.PLP cã c¸c thñ tôc chÝnh nh­ sau :

- ThiÕt lËp, xãa, khëi ®éng l¹i liªn kÕt.

- TruyÒn d÷ liÖu th­êng, khÈn.

- Khëi ®éng l¹i mét giao diÖn.

Qu¸ tr×nh trao ®æi gãi tin ®­îc m« t¶ b»ng h×nh sau:

Local DTE

DTE/DCE

DTE/DCE

DTE

Call setup

phase

Data Transfer

phase

Call cleaning

phase

Call request

Call connected

Data packet

Incoming data

Clear Request

Clear Confirm

t

i

m

e

Incoming call

Call accepted

Incoming data

Data packet

Clear Indication

Clear Respond

H×nh 3.12: ho¹ût ®éng cña giao thøc X.25 PLP

Cã thÓ x¶y ra tr­êng hîp c¶ hai phÝa cïng chän mét yªu cÇu, dÉn ®Õn viÖc ®ông ®é gi÷a c¸c cuéc gäi (call collision)

§å thÞ tr¹ng th¸i cña qu¸ tr×nh nèi-t¸ch:

Qóa

®é

G©y bëi

Gãi tin göi

1

2

3

4

5

6

7

DTE

DCE

DCE

DTE

DCE

DTE

DCE

Call Request

Call Connected

Incoming Call

Call Accepted

Incoming Call

Call Request

Call Connected

VI. VÊN §Ò T¾C NGHÏN

1. T¾c nghÏn

Khi cã qu¸ nhiÒu gãi tin trong m¹ng hay mét phÇn cña m¹ng lµm cho hiÖu xuÊt cña m¹ng gi¶m ®i v× c¸c nót m¹ng kh«ng cßn ®ñ kh¶ n¨ng l­u tr÷, xö lý, g÷i ®i vµ chóng b¾t ®Çu bÞ mÊt c¸c gãi tin. HiÖn t­îng nµy gäi lµ sù t¾c nghÏn trong m¹ng.

- Khi sè gãi tin dùa vµo m¹ng Ýt h¬n kh¶ n¨ng vËn chuyÓn cña nót m¹ng th× gãi tin dùa vµo m¹ng sÏ b»ng sè gãi tin ®­îc g÷i ®i.

- NÕu sè gãi tin dùa vµo m¹ng cµng nhiÒu h¬n kh¶ n¨ng vËn chuyÓn cña nót m¹ng th× gãi tin chuyÓn ®i cµng chËm vµ cuèi cïng dÉn ®Õn t¾c nghÏn.

Nguyªn nh©n:

- Hµng ®îi sÏ bÞ ®Çy (ph¶i l­u tÖp, ph¶i t¹o c¸c b¶ng ...), nÕu kh¶ n¨ng xö lÝ cña nót yÕu.

- Hµng ®îi bÞ ®Çy khi th«ng tin vµo nhiÒu h¬n kh¶ n¨ng cña ®­êng ra, mÆc dï tèc ®é xö lÝ cña nót nhanh.

CÇn ph©n biÖt hai kh¸i niÖm:

- §iÒu khiÓn dßng d÷ liÖu lµ xö lý giao th«ng gi÷a ®iÓm víi ®iÓm, gi÷a tr¹m ph¸t víi tr¹m thu.

- §iÒu khiÓn tr¸nh t¾c nghÏn lµ mét vÊn ®Ò tæng qu¸t h¬n bao gåm viÖc t¹o ra ho¹t ®éng hîp lý cña c¸c m¸y tÝnh cña c¸c nót m¹ng, qu¸ tr×nh l­­ tr÷ bªn trong nót, ®iÒu khiÓn tÊt c¶ c¸c yÕu tè lµm gi¶m kh¶ n¨ng vËn chuyÓn cña toµn m¹ng.

2. Chèng t¾c nghÏn

MÆc dï sinh ra c¬ chÕ kiÓm so¸t luång d÷ liÖu nh»m tr¸nh t×nh tr¹ng ïn t¾c trªn m¹ng nh­ng trong thùc tÕ th× nã vÉn cø x¶y ra vµ ng­êi ta ph¶i dù kiÕn c¸c gi¶i ph¸p thÝch hîp. NhiÖm vô gi¶i quyÕt ïn t¾c nµy th­êng dµnh cho tÇng M¹ng. Cã thÓ dïng mét sè biÖn ph¸p sau ®©y:

- Dµnh s½n c¸c bé ®Öm chØ ®Ó dïng khi xÈy ra ïn t¾c. Ph­¬ng ph¸p nµy ®· ®­îc dïng trong m¹ng ARPANET nh­ng hiÖu qu¶ kh«ng cao v× b¶n th©n bé nhí ®Öm råi còng nhanh chãng ïn t¾c.

- G¾n cho c¸c gãi tin mét thêi gian “sèng” x¸c ®Þnh tr­íc, nÕu qu¸ thêi gian ®ã th× chóng bÞ hñy. Tuy nhiªn gi¶i ph¸p nµy kh¸ nguy hiÓm v× cã thÓ hñy bá c¸c gãi tin ngay khi chóng võa ®¹t ®Ých. Nh­ng dÉu sao th× nã cung cã Ých trong viÖc ng¨n chÆn hiÖn t­îng ïn t¾c nªn ng­êi ta còng th­êng hay dïng. §¬n gi¶n h¬n, ta cã thÓ lo¹i bá c¸c gãi tin muèn ®i qua mét liªn kÕt ®· qu¸ t¶i. Giao thøc tÇng Giao VËn sÏ chÞu tr¸ch nhiÖm truyÒn l¹i c¸c gãi tin bÞ lo¹i bá ®ã.

- Trong c¸c m¹ng dïng m¹ch ¶o nh­ lµ m¹ng X25, sù ïn t¾c cã thÓ do më ra qu¸ nhiÒu VC qua mét nót. CÇn ph¶i ®ãng bít mét sè ®Ó tr¸nh ïn t¾c. TÇng m¹ng chÞu tr¸ch nhiÖm më l¹i c¸c VC ®ã th× kh«ng cßn nguy c¬ ïn t¾c n÷a.

Ngoµi ra cßn cã c¸c biÖn ph¸p sau:

- Bè trÝ kh¶ n¨ng vËn chuyÓn, l­u tr÷, xö lý cña m¹ng d­ so víi yªu cÇu.

- Hñy bá c¸c gãi tin bÞ t¾c nghÏn qu¸ thêi h¹n.

- H¹n chÕ sè gãi tin vµo m¹ng nhê c¬ chÕ cña sæ.

-   ChÆng ®­êng vµo khi cña c¸c gãi tin khi m¹ng qu¸ t¶i.

3. §iÒu khiÓn t¾c nghÏn ë m¹ng con m¹ch ¶o :

Nh÷ng ph­¬ng ph¸p ®iÒu khiÓn t¾c nghÏn ®­îc m« t¶ ë trªn vÒ c¬ b¶n lµ vßng më : chóng ng¨n ngõa t¾c nghÏn x¶y ra ë n¬i ®Çu tiªn h¬n lµ viÖc xö lý t¾c nghÏn sau nµy. Trong phÇn nµy sÏ m« t¶ vµi ph­¬ng ph¸p n¨ng ®éng ®Ó ®iÒu khiÓn trong m¹ng con m¹ch ¶o.

Mét kü thuËt ®­îc sö dông réng r·i ®Ó gi÷ cho t¾c nghÏn võa x¶y ra kh«ng diÔn biÕn xÊu ®ã lµ ®iÒu khiÓn n¬i nhËn (admission control). ý t­ëng lµ ®¬n gi¶n : mét khi cã tÝn hiÖu t¾c nghÏn, mét mét m¹ch ¶o nµo ®­îc thiÕt lËp cho tíi khi vÊn ®Ò ®­îc gi¶i quyÕt. Do ®ã, viÖc cè g¾ng thiÕt lËp mét tÇng giao vËn míi lµ kh«ng x¶y ra. Mét ph­¬ng ph¸p ®¬n gi¶n dÔ thùc hiÖn nh­ trong hÖ thèng ®iÖn thoaüi, khi chuyÓn m¹ch cã sù qu¸ t¶i, nã còng ¸p dông ®iÒu khiÓn ®Çu nhËn, cho ngõng quay sè.

Ph­¬ng ph¸p thay thÕ lµ cho phÐp thiÕt lËp m¹ch ¶o nh­ng cÈn thËn tÊt c¶ c¸c m¹ch ¶o nµy khi di chuyÓn quanh khu vùc cã sù cè. VÝ dô xem m¹ng con h×nh (a) bªn d­íi, cã 2 router bÞ t¾c nghÏn nh­ m« t¶.

A                                                            A

                                    T¾c nghÏn        

                                                    B                                                               B

                      T¾c nghÏn

           (a). M¹ng con                      (b). M¹ng con sau kh lo¹i bá t¾c nghÏn

                                                                           vµ m¹ch ¶o tõ A ®Õn B

Gi¶ sö 1 m¸y chñ g¾n víi router A muèn kÕt nèi víi m¸y chñ g¾n víi router B. Th«ng th­êng, ®©y lµ liªn kÕt sÏ ®i qua mét trong nh÷ng router bÞ t¾c nghÏn. §Ó tr¸nh t×nh tr¹ng nµy, chóng ta cã thÓ vÏ mét m¹ng con nh­ h×nh (b), bá qua nh÷ng router t¾c nghÏn vµ tÊt c¶ c¸c ®­êng cña chóng. §­êng g¹ch (h×nh b) cho biÕt ®­êng cã thÓ ®i cña m¹ch ¶o ®Ó tr¸nh nh÷ng router t¾c nghÏn.

Mét chiÕn l­îc kh¸c liªn quan ®Õn m¹ch ¶o lµ tháa thuËn gi÷a m¸y chñ vµ m¹ng con khi thiÕt lËp m¹ch ¶o. Sù tháa thuËn nµy th­êng chØ ®Þnh râ dung l­îng vµ h×nh d¹ng l­u th«ng, chÊt l­îng dÞch vô yªu cÇu vµ mét sè tham sè kh¸c. §Ó gi÷ phÇn cña m×nh trong tháa thuËn, m¹ng con sÏ l­u gi÷ nguån tin theo däc ®­êng dÉn khi m¹ch ®­îc thiÕt lËp. Nh÷ng nguån tin ®ã cã thÓ bao gåm b¶ng, kho¶ng bé nhí ®Öm cña nh÷ng router vµ gi¶i th«ng trªn c¸c ®­êng. Theo c¸ch nµy t¾c nghÏn ch¾c ch¾n kh«ng x¶y ra ë nh÷ng m¹ch ¶o míi bëi v× tÊt c¶ c¸c nguån tin cÇn thiÕt ®­îc b¶o ®¶m cã s¼n.

Ph­¬ng ph¸p nµy ®­îc thùc hiÖn mäi thêi gian nh­ lµ tiÕn tr×nh vËn hµnh chuÈn hoÆc chØ khi m¹ng x¶y ra t¾c nghÏn. Sù bÊt lîi cho viÖc thùc hiÖn ®iÒu nµy lµ tiªu phi nguån tin. NÕu 6 m¹ch ¶o sö dông 1 Mbps, tÊt c¶ ®Òu qua mét ®­êng 6 Mbps, th× ®­êng nµy ®­îc xem nh­ lµ ®Çy, thËm chÝ hiÕm khi x¶y ra tÊt c¶ 6 m¹ch ¶o l¹i ®­îc truyÒn cïng mét lóc. KÕt qu¶, gi¸ trÞ cña ®iÒu khiÓn t¾c nghÏn lµ gi¶i th«ng v« dông.

VII. C¸C C«NG NGHÖ CHUYÓN M¹CH NHANH Tõ X.25 §ÕN ATM

1. Frame Relay

Trong X.25 chøc n¨ng dån kªnh ®èi víi c¸c liªn kÕt ¶o chØ ®¶m b¶o sù kiÓm so¸t lçi cho c¸c khung gëi ®i qua giao tiÕp DTE/DCE côc bé. §iÒu nµy lµm t¨ng ®é phøc t¹p trong viÖc phèi hîp c¸c thñ tôc gi÷a hai tÇng kÒ nhau, dÉn ®Õn th«ng l­îng bÞ h¹n chÕ do tæng chi phÝ xö lÝ c¸c gãi tin t¨ng lªn. Do ®ã sù xuÊt hiÖn cña c«ng nghÖ Frame Relay ®­îc phï hîp h¬n ®Ó sö dông víi bé giao thøc TCP/IP.

Tr¸i l¹i, víi Frame Relay chøc n¨ng dån kªnh, chän ®­êng ®­îc thùc hiÖn ë tÇng hai. H¬n n÷a viÖc chän ®­êng cho c¸c Frame rÊt ®¬n gi¶n lµm cho th«ng l­îng cã thÓ cao h¬n nhiÒu so víi kü thuËt chuyÓn m¹ch gãi vµ ®ång thêi frame Relay kh«ng cã tÝnh n¨ng söa lçi v× c¸c ph­¬ng tiÖn phÇn cøng phôc vô dÞch vô th«ng tin sè ngµy nay ®· trë nªn rÊt tinh cËy nªn nh÷ng quy tr×nh söa lçi tr­íc ®©y kh«ng cÇn thiÕt do ®ã tèc ®é chuyÓn m¹ch nhanh.

Frame Relay cho phÐp ®a cuéc gäi ®Õn c¸c ®Þa chØ kh¸c nhau trong tiÕn tr×nh ®­êng hiÖn hµnh. Khi mçi cuéc gäi ®Çu tiªn ®­îc thiÕt lËp sö dông kªnh D ®Ó tr¶ lêi cho dÞch vô nguyªn thñy L-CONNECT request gäi lµ DLCI (data link connection identifier). TÊt c¶ c¸c yªu cÇu truyÒn d÷ liÖu liªn tôc, liªn quan víi cuéc gäi nµy th× DLCI xem nh­ lµ mét tham sè. DLCI ®­îc g¾n vµo phÇn ®Çu cña c¸c Frame cuèi ®Ó chän ®­êng c¸c Frame ®Õn c¸c ®Ých cña chóng.

1.1. Khu«n d¹ng b¶ng tin

+ Khu«n d¹ng tæng qu¸t dïng trong kü thuËt Frame Relay còng gièng nh­ HDLC, chØ kh¸c trong néi dung cña vïng th«ng tin ®iÒu khiÓn. Khung d÷ liÖu cã kÝch th­íc gãi tõ 64bytes ®Õn 1500 bytes

Flag

Header

Data

CRC

Flag

                                                                                                     (CF)

8

7

6

5

4

3

2

1

DLCICI(msbsb)

CC/RR

EAEA0

DLCICI(msbsb)

FECNCN

BECNCN

DEDE

EAEA1

                                                  (CB)

H×nh 3.14: Khu«n d¹ng cña mçi frame ®­îc truyÒn trong kªnh B

DLCI  : Data Link Connection Identifier: §Þnh danh kÕt nèi liªn kÕt d÷ liÖu.

EA      : Extended Address

C/R     : Command/Response: Thùc hiÖn lÖnh/Tr¶ lêi

FECN :  Forward Explicit Congestion Notification  (CF)

BECN : Backward Explicit Congestion Notification (CB)

DE      : Discard elegibility

1.2. Ph­¬ng thøc ho¹t ®éng

Trong vïng Header cña frame cã chøa tham sè DLCI ®Ó ®Þnh danh c¸c liªn kÕt d÷ liÖu ®­îc thiÕt lËp. Mçi khi mét liªn kÕt d÷ liÖu ®­îc thiÕt lËp th× nã ®­îc g¸n 1 DLCI vµ gi¸ trÞ nµy sÏ lu«n ®­îc khai b¸o trong tÊt c¶ frame d÷ liÖu vµ frame ®iÒu khiÓn liªn quan ®Õn liªn kÕt ®ã. Còng gièng nh­ tham sè VCI trong X.25 PLP, DLCI chØ cã ý nghÜa côc bé vµ ®­îc dïng ®Ó chän ®­êng (chuyÓn tiÕp cho frame tíi ®Ých cña nã).

ë mçi nót khi nhËn ®­îc 1 frame d÷ liÖu, ch­¬ng tr×nh ®iÒu khiÓn ®­îc cµi ë ®ã sÏ ®äc gi¸ trÞ DLCI trong vïng header vµ kÕt hîp víi sè liÖu cña ®­êng truyÒn vµo ®Ó x¸c ®Þnh ®­êng truyÒn ra vµ gi¸ trÞ DLCI ®i vaß t­¬ng øng. Gi¸ trÞ DLCI míi nµy sÏ ®­îc ghi vµo header cña frame vµ frame sÏ ®­îc ®­a vµo hµng ®îi ®Ó gëi tiÕp ®i trªn ®­êng ra ®­îc chän. TrËt tù c¸c frame ®­îc chuyÓn tiÕp, do ®ã ®­îc b¸o tr­íc vµ lé tr×nh cña nã cùc nhanh.                    

Link 1 routing table

Link 2 routing table

Link 3 routing table

DLCI-in

Link-out

DLCI-out

DLCI-in

Link-out

DLCI-out

DLCI-in

Link-out

DLCI-out

   1

3

3

      2

3

2

2

1

2

3

2

1

      5

3

6

6

1

5

H×nh 3.15:  Frame routing

V× nhiÒu liªn kÕt d÷ liÖu cã thÓ ®ång thêi ph©n chia cho mét ®­êng truyÒn vËt lý, mÆt kh¸c c¸c frame liªn quan ®Õn mét liªn kÕt d÷ liÖu nµo ®ã l¹i cã thÓ ®­îc t¹o ra ë c¸c thêi ®iÓm ngÉu nhiªn nªn hiÖn t­îng t¾c nghÏn cã thÓ x¶y ra ®èi víi