Bé gi¸o dôc vµ ®µo t¹o
Tr-êng ®¹i häc b¸ch khoa Hµ Néi
Ph¹m ®øc thuËn
c«ng nghÖ chuyÓn m¹ch nh·n ®a giao thøc
Chuyªn ngµnh : §iÖn tö viÔn th«ng
LuËn v¨n th¹c sü ®iÖn tö viÔn th«ng
Ng-êi h-íng dÉn khoa häc:
TS §ç Hoµng TiÕn
Hµ Néi-2004
C¸c tõ viÕt t¾t
ViÕt t¾t
TiÕng Anh
TiÕng ViÖt
aal
ATM Adaption Layer
Líp thÝch øng ATM
as
Autonomous System
HÖ thèng tù trÞ
Atm
Asynchronous Transfer Mode
ChÕ ®é truyÒn kh«ng ®ång bé
Bgp
Boder Gateway Protocol
Giao thøc ®Þnh tuyÕn biªn
cbr
Contrain Based Routing
§Þnh tuyÕn Ðp buéc
Dlci
Data Link Circuit Identifier
NhËn d¹ng kªnh liªn kÕt d÷ liÖu
egp
Exterior Gateway Protocol
Giao thøc ®Þnh tuyÕn cæng ngoµi
Fec
Forwarding Equivalence Class
Líp chuyÓn tiÕp t-¬ng ®-¬ng
Fib
Forwarding Information Base
C¬ së th«ng tin chuyÓn tiÕp
Ftn
FEC to NHLFE Map
S¾p xÕp FEC vµo NHLFE
glsp
Generalized Label Switched
Path
§-êng chuyÓn m¹ch nh·n tæng
qu¸t
gmpls
Generalized Multiprotocol
Label Switching
ChuyÓn m¹ch nh·n ®a giao thøc
tæng qu¸t
ietf
Internet Engineering Task
Force
Tæ chøc tiªu chuÈn kü thuËt
Internet
Igp
Interior Gateway Protocol
Giao thøc ®Þnh tuyÕn cæng trong
Ilm
Income Label Map
¸nh x¹ nh·n ®Õn
Ip
Internet Protocol
Giao thøc Internet
isp
Internet Service Provider
Nhµ cung cÊp dÞch vô Internet
lan
Local Area Network
M¹ng côc bé
Ldp
Label Distribution Protocol
Giao thøc ph©n phèi nh·n
lfa
Label swaping Forwarding
Alorithm
ThuËt to¸n chuyÓn tiÕp trao ®æi
nh·n
lmp
Link Management Protocol
Giao thøc qu¶n lý liªn kÕt
lsdb
Link State Database
C¬ së d÷ liÖu tr¹ng th¸i liªn kÕt
lsr
Label Switched Router
Bé ®Þnh tuyÕn chuyÓn m¹ch nh·n
Lsp
Label Switched Path
§-êng chuyÓn m¹ch nh·n
mpls
Multiprotocol Label Switching
ChuyÓn m¹ch nh·n ®a giao thøc
NGN
Next Generation Network
M¹ng thÕ hÖ sau
ospf
Open Shortest Path First
Giao thøc ®Þnh tuyÕn më ®-êng
ng¾n nhÊt ®Çu tiªn
Ppp
Point to Point Protocol
Giao thøc ®iÓm ®iÓm
PVC
Permanent Virtual Circuit
Kªnh ¶o cè ®Þnh
QoS
Quality of Service
ChÊt l-îng dÞch vô
rip
Routing Information Protocol
Giao thøc th«ng tin ®Þnh tuyÕn
rsvp
Resouce Reservation Protocol
Giao thøc dµnh tr-íc tµi nguyªn
SDH
Synchronous Digital Hierachy
Ph©n cÊp sè ®ång bé
Sonet
Synchronous Optical Network
M¹ng quang ®ång bé
Svc
Switched Virtual Circuit
Kªnh chuyÓn m¹ch ¶o
Svp
Switched Virtual Path
§-êng chuyÓn m¹ch ¶o
te
Traffic Engineering
Kü thuËt l-u l-îng
Tcp
Transmission Control Protocol
Giao thøc ®iÒu khiÓn truyÒn t¶i
Tdm
Time Division Multiplexing
GhÐp kªnh ph©n chia theo thêi
gian
tt
Trafic Trunk
Trung kÕ l-u l-îng
Ttl
Time to Live
Thêi gian sèng
Vc
Virtual Circuit
Kªnh ¶o
Vp
Virtual Path
§-êng ¶o
Vci
Virtual Circuit Identifier
NhËn d¹ng kªnh ¶o
Vpi
Virtual Path Identifier
NhËn d¹ng ®-êng ¶o
Danh môc h×nh vÏ vµ b¶ng
H×nh 1.1
12
H×nh 1.2
14
H×nh 1.3
16
H×nh 1.4
17
H×nh 1.5
19
H×nh 1.6
22
H×nh 2.1
26
H×nh 2.2
26
H×nh 2.3
31
H×nh 2.4
38
H×nh 2.5
39
H×nh 2.6
47
H×nh 3.1
53
H×nh 3.2
74
H×nh 3.3
75
H×nh 3.4
75
H×nh 4.1
78
H×nh 4.2
82
H×nh 4.3
90
H×nh 4.4
91
H×nh 4.5
92
H×nh 4.6
94
H×nh 4.7
96
B¶ng 1.1
9
B¶ng 1.2
10
B¶ng 4.1
101
Môc lôc
Danh môc c¸c tõ viÕt t¾t
Danh môc h×nh vÏ vµ b¶ng
Lêi nãi ®Çu
1
Ch-¬ng 1 tæng quan
3
1.1-Më ®Çu
3
1.2-C¸c thuËt to¸n vµ giao thøc ®Þnh tuyÕn IP
4
1.2.1-C¸c thuËt to¸n ®Þnh tuyÕn
4
1.2.1.1-ThuËt to¸n chän ®-êng tÜnh
5
1.2.1.2-ThuËt to¸n chän ®-êng ®éng
5
1.2.2-C¸c giao thøc ®Þnh tuyÕn
6
1.2.2.1-Giao thøc ®Þnh tuyÕn IGP
7
1.2.2.2-Giao thøc ®Þnh tuyÕn EGP
9
1.3-Sù ph¸t triÓn cña chuyÓn m¹ch ®a líp
11
1.3.1- C¬ së x©y dùng c¸c khèi chung trong chuyÓn m¹ch ®a líp
12
1.3.1.1-Ph©n t¸ch khèi ®iÒu khiÓn vµ chuyÓn tiÕp
12
1.3.1.2-ThuËt to¸n chuyÓn tiÕp trao ®æi nh·n
13
1.3.2-M« h×nh IP over ATM
15
1.3.3-Sù gièng nhau gi÷a c¸c gi¶i ph¸p chuyÓn m¹ch ®a líp
17
1.3.4-Sù kh¸c nhau c¬ b¶n gi÷a c¸c gi¶i ph¸p chuyÓn m¹ch ®a líp
20
1.3.5-VÊn ®Ò c¬ b¶n ®èi víi gi¶i ph¸p chuyÓn m¹ch ®a líp
21
1.4-ChuyÓn m¹ch nh·n ®a giao thøc
22
1.5-KÕt luËn
24
Ch-¬ng 2-chuyÓn m¹ch nh·n ®a giao thøc
25
2.1- C¸c bé phËn cña hÖ thèng MPLS
25
2.1.1-Gãi ®¸nh nh·n
25
2.1.2-Bé ®Þnh tuyÕn chuyÓn m¹ch nh·n
28
2.1.2.1-C¬ së d÷ liÖu chuyÓn tiÕp
29
2.1.2.2- Khèi x¸c ®Þnh tuyÕn
30
2.1.2.3- Khèi chuyÓn tiÕp
30
2.1.3- §-êng chuyÓn m¹ch nh·n
31
2.2-C¸c chøc n¨ng cña hÖ thèng MPLS
33
2.2.1-Ph©n phèi nh·n
33
2.2.2- Gép
36
2.2.3-Thao t¸c ng¨n xÕp nh·n
38
2.2.4- Lùa chän ®-êng
40
2.3-C¸c chÕ ®é ho¹t ®éng MPLS
41
2.3.1-ChÕ ®é cÊp ph¸t nh·n
41
2.3.2- ChÕ ®é ph©n phèi nh·n
41
2.3.3-C¸c chÕ ®é l-u gi÷ nh·n
42
2.3.4-ChÕ ®é ®iÒu khiÓn
44
2.3.5- Kh«ng gian nh·n
45
2.3.6-Ho¹t ®éng khi chuyÓn mét gãi qua MPLS
46
Ch-¬ng 3-ChÊt l-îng dÞch vô vµ
kü thuËt l-u l-îng trong MPLS
50
3.1-ChÊt l-îng dÞch vô
50
3.1.1-QoS trong m¹ng IP
50
3.1.1.1-IntServ
50
3.1.1.2-DiffServ
52
3.1.2-ChÊt l-îng dÞch vô trong MPLS
54
3.1.2.1-Sö dông m« h×nh IntServ.
54
3.1.2.2-Sö dông m« h×nh DiffServ
55
3.2-Kü thuËt l-u l-îng
56
3.2.1-Tæng quan
56
3.2.1.1-§èi t-îng thùc hiÖn kü thuËt l-u l-îng
57
3.2.1.2- §iÒu khiÓn tµi nguyªn vµ l-u l-îng
58
3.2.1.3-H¹n chÕ cña c¸c c¬ chÕ ®iÒu khiÓn IGP hiÖn nay
58
3.2.2-MPLS vµ kü thuËt l-u l-îng
59
3.2.2.1-VÊn ®Ò c¬ b¶n cña kü thuËt l-u l-îng sö dông MPLS
60
3.2.2.2-C¸c kh¶ n¨ng t¨ng thªm cho kü thuËt l-u l-îng
61
3.2.2.3-Giao thøc b¸o hiÖu
70
3.2.2.4-Thay ®æi tham sè cña LSP
71
3.2.2.5-Kh¾c phôc sù cè víi LSP
72
3.2.2.6-KÕt luËn
76
Ch-¬ng 4-gmpls
77
4.1-Giíi thiÖu
77
4.2-GMPLS
79
4.2.1-Ph©n cÊp chuyÓn m¹ch vµ chuyÓn tiÕp
80
4.2.2-M¶ng ®iÒu khiÓn GMPLS
83
4.2.2.1-Ph©n t¸ch m¶ng ®iÒu khiÓn vµ d÷ liÖu
83
4.2.2.2 M¶ng ®iÒu khiÓn GMPLS
83
4.2.3-M« h×nh ®Þa chØ vµ ®Þnh tuyÕn
87
4.2.4 C¸c ®Þnh d¹ng liªn quan ®Õn nh·n
90
4.2.5-LSP hai chiÒu
96
4.2.6 §iÒu khiÓn nh·n t-êng minh
98
4.2.7- GMPLS vµ MPLS-TE
98
4.2.8 GMPLS trong m¹ng truyÒn t¶i
99
4.2.9 So s¸nh mét sè ®Æc tÝnh cña GMPLS vµ kiÕn tróc ATM/SDH
101
4.2.10-Kh¶ n¨ng triÓn khai vµ chuÈn ho¸ cña GMPLS
102
4.2.11-KÕt luËn
103
KÕt luËn
104
Tµi liÖu tham kh¶o
1
Lêi nãi ®Çu
Trong nh÷ng n¨m gÇn ®©y, ®· nh÷ng thay ®æi lín trong h×nh l-u
l-îng liªn m¹ng. §Çu tiªn, ®· bïng cña Internet ph-¬ng diÖn
ph¹m vi dung l-îng. Thø hai, ®· gia t¨ng l-îng c¸c øng dông
thêi gian thùc ®a ph-¬ng tiÖn trong m¹ng. c thay ®æi nµy g©y ¸p lùc lªn
m¹ng nh»m trî b¨ng th«ng lín h¬n cung cÊp ®¶m b¶o chÊt l-îng dÞch
vô. Cho ®Õn nay IP ®· lµm viÖc kh¸ tèt ph-¬ng diÖn réng ph¹m vi do
b¶n chÊt kh«ng nèi th«ng a nã. Tuy nhiªn m« h×nh chuyÓn göi d÷ liÖu tõng
chÆng cña IP nh÷ng h¹n chÕ nh-: ph¶i dùa vµo giao thøc ®Þnh tuyÕn ®Ó
ph©n bè th«ng tin ®Þnh tuyÕn, viÖc thùc hiÖn qu¸ tr×nh chuyÓn tiÕp chØ dùa trªn
®Þa chØ ®Ých gãi tin kh«ng thÓ dùa trªn tham chÊt l-îng dÞch , mçi
nót ®Òu ph¶i thùc hiÖn viÖc t×m kiÕm th«ng tin ®Þnh tuyÕn.
§Ó ®¸p øng yªu cÇu cña m¹ng còng nh- gi¶i quyÕt nh÷ng n chÕ cña
m¹ng IP hiÖn nay, ngµnh c«ng nghiÖp viÔn th«ng ®· ®ang t×m ra mét
ph-¬ng thøc chuyÓn m¹ch cã thÓ kÕt hîp -u ®iÓm cña IP (nh- cÊu ®Þnh
tuyÕn) cña ATM (th«ng l-îng chuyÓn m¹ch), c«ng nghÖ chuyÓn m¹ch
nh·n ®a giao thøc (MPLS) kÕt qu¶ cña kÕt hîp nµy. MPLS ®-a ra mét
gi¶i ph¸p nh- mét cÇu nèi cho tÝch hîp ®iÒu khiÓn cña ®Þnh tuyÕn IP víi
®¬n gi¶n cña chuyÓn m¹ch líp hai. C«ng nghÖ MPLS c«ng nghÖ chuyÓn
m¹ch IP triÓn väng øng dông rÊt cao. Nhê ®Æc tÝnh cÊu ®Þnh tuyÕn cña
m×nh, MPLS kh¶ n¨ng n©ng cao chÊt l-îng dÞch cña m¹ng IP truyÒn
thèng. Bªn c¹nh ®ã th«ng l-îng cña m¹ng còng ®-îc c¶i thiÖn rÖt. HiÖn
nay, nhiÒu nhµ khai th¸c ®Þnh h-íng hoÆc ®· triÓn khai m¹ng thÕ sau
trªn c«ng nghÖ MPLS. ViÖc t×m hiÓu b¶n chÊt c«ng nghÖ còng nh- xu
h-íng ph¸t triÓn kh¶ n¨ng øng dông cña c«ng nghÖ MPLS hiÖn nay rÊt
cÇn thiÕt. LuËn v¨n nµy xin tr×nh bµy c¸c néi dung sau:
- Qu¸ tr×nh h×nh thµnh vµ ph¸t triÓn cña MPLS
2
- C¸c vÊn ®Ò c¬ b¶n cña MPLS
- ChÊt l-îng dÞch vô vµ kü thuËt l-u l-îng trong MPLS
- GMPS b-íc ph¸t triÓn më réng cña MPLS
thêi gian tr×nh ®éh¹n, luËn v¨n ch¾c ch¾n cßn nhiÒu sai sãt. T«i
mong nhËn ®-îc sù gãp ý chØ b¶o cña c¸c thÇy c« gi¸o, ®ång nghiÖp vµ b¹n bÌ
®Ó cã thÓ hoµn thiÖn h¬n.
T«i xin bµy lßng biÕt ¬n sau s¾c ®Õn TS §ç Hoµng TiÕn ng-êi ®· tËn
t×nh h-íng dÉn chØ b¶o quý b¸u ®Ó t«i thÓ hoµn thµnh luËn v¨n tèt
nghiÖp nµy. T«i xin ch©n thµnh c¶m ¬n ThS D-¬ng Thanh Ph-¬ng, c¸c c¸n
ë Trung t©m ®µo t¹o båi d-ìng sau ®¹i häc, c¸c thÇy gi¸o, ®ång nghiÖp,
b¹n ®· gióp ®ì t¹o ®iÒu kiÖn thuËn lîi nhÊt cho t«i hoµn thµnh b¶n luËn
v¨n nµy.
Ph¹m §øc ThuËn
3
Ch-¬ng 1 tæng quan
1.1-Më ®Çu
C¸c nhµ cung cÊp dÞch Internet lu«n gÆp ph¶i th¸ch thøc thÝch øng
m¹ng ®Ó hç trî sù ph¸t triÓn nhanh chãng vµ yªu cÇu kh¸ch hµng cho c¸c dÞch
vô tin cËy vµ ®a d¹ng h¬n. Gi÷a nh÷ng n¨m 90, IP over ATM ®· cung cÊp cho
c¸c nhµ cung cÊp dÞch mét gi¶i ph¸p cho ph©n ph¸t ®-îc thùc hiÖn hiÖu
qu¶ vµ kh¶ n¨ng ®iÒu khiÓn l-u l-îng. H¬n thÕ n÷a c¸c nhµ cung cÊp thÊy
®-îc hiÖu qu¶ khi ghÐp l-u l-îng Internet nh- mét trong nhiÒu dÞch ®-îc
mang trªn ng lâi ATM. Ngµy nay, ph¸t triÓn cña dÞch Internet
WDM t¹i cÊp ®é sîi quang ®· cung cÊp mét lùa chän kh¸c hiÖu qu¶ h¬n
ATM cho ghÐp ®a dÞch vô qua kªnh riªng. Thªm vµo ®ã, chuyÓn m¹ch ATM
trong b¨ng nhanh h¬n cao h¬n ®ang n»m ngoµi sù ®¸p øng cña c¸c ®Þnh
tuyÕn x-¬ng sèng Internet. MPLS ®-a ra t chÕ ®¬n gi¶n h¬n cho ®iÒu
khiÓn l-u l-îng h-íng gãi vµ chøc n¨ng ®a dÞch vô.
Trong tÊt c¸c ngµnh c«ng nghÖ tÝnh chÊt quyÕt ®Þnh cho ho¹t
®éng thµnh c«ng vµ tiÕp tôc ph¸t triÓn cña Internet, sù tiÕn triÓn cña chøc n¨ng
®Þnh tuyÕn thiÕt u. MPLS b-íc ph¸t triÓn gÇn ®©y nhÊt cña c«ng nghÖ
®Þnh tuyÕn chuyÓn tiÕp cho m¹ng lâi Internet. MPLS ®-a ra mét gi¶i ph¸p nh-
mét cÇu nèi cho tÝch hîp ®iÒu khiÓn cña ®Þnh tuyÕn IP víi ®¬n gi¶n cña
chuyÓn m¹ch líp hai. H¬n thÕ n÷a, MPLS cung cÊp mét ®Ó trî cho
viÖc triÓn khai c¸c dÞch ®Þnh tuyÕn tiªn tiÕn gi¶i quyÕt mét n ®Ò
phøc t¹p nh- sau:
- §Þa cMPLS ®-îc kÕt hîp i triÓn khai hiÖn t¹i cña chÕ ®é chång
lÊp IP over ATM.
- MPLS t¹o ®iÒu kiÖn cho viÖc ph©n ph¸t c¸c kh¶ n¨ng ®Þnh tuyÕn míi ®Ó
c¶i tiÕn kü thuËt ®Þnh tuyÕn IP truyÒn thèng.
4
- MPLS gi¶m sù phøc t¹p cña ho¹t ®éng m¹ng.
- MPLS ®-a ra gi¶i ph¸p tiªu chuÈn, thóc ®Èy phèi hîp ho¹t ®éng cña
nhiÒu nhµ s¶n xuÊt.
§Ó hiÓu ®Çy ®ñ vÒ MPLS vµ vai trß cña nã, chóng ta xem xÐt sù ph¸t triÓn
cña chuyÓn m¹ch ®a líp vµ chóng ®-îc tÝch hîp vµo MPLS nh- thÕ nµo.
1.2-C¸c thuËt to¸n vµ giao thøc ®Þnh tuyÕn IP
Trong ®Þnh tuyÕn truyÒn thèng, mét gãi ®-îc chuyÓn tiÕp qua m¹ng theo
tõng chÆng dông giao thøc IGP nh- RIP, OSPF hoÆc EGP nh- BGP. Mçi
®Þnh tuyÕn sÏ ph©n tÝch phÇn ®Çu cña gãi liÖu, vµ mçi ®Þnh tuyÕn
thùc hiÖn mét thuËt to¸n ®Þnh tuyÕn tÇng m¹ng. Mçi ®Þnh tuyÕn ®éc lËp
chän chÆng tiÕp theo cho gãi, dùa trªn viÖc ph©n ch header cña gãi kÕt
qu¶ cña thuËt to¸n ®Þnh tuyÕn.
1.2.1-C¸c thuËt to¸n ®Þnh tuyÕn
Chøc n¨ng b¶n cña tÇng m¹ng dÉn ®-êng c¸c gãi liÖu nguån
®Õn ®Ých. Trong ®a m¹ng con, c¸c gãi ®i theo hµnh tr×nh tõng chÆng. ChØ
ngo¹i trõ víi m¹ng qu¶ng b¸, nh÷ng ®-êng dÉn ë ®©y bao gåm cnguån
®Ých kh«ng ng n»m trong mét m¹ng. ThuËt to¸n chän ®-êng cÊu tróc d÷
liÖu vÊn ®Ò b¶n cña thiÕt lËp tÇng m¹ng. ThuËt to¸n chän ®-êng mét
phËn cña c¸c phÇn mÒm tÇng m¹ng chÞu tr¸ch nhiÖm x¸c ®Þnh ®-êng ra
nµo mét gãi liÖu ®Õn ®-îc chuyÓn ®i. NÕu m¹ng con dông c¸c
datagram bªn trong, th× mçi quyÕt ®Þnh ph¶i ®-îc lµm víi mçi gãi d÷ liÖu ®Õn.
NÕu m¹ng con dông kªnh ¶o, quyÕt ®Þnh chän ®-êng ®-îc thùc hiÖn chØ
khi mét kªnh ¶o míi ®-îc thiÕt lËp, sau ®ã c¸c gãi liÖu ®i theo ®-êng thiÕt
lËp tõ tr-íc. Tr-êng hîp sau gäi chän ®-êng theo phiªn, v× ®-êng ®-îc g
nguyªn t¸c dông ®èi víi phiªn hiÖn thêi cña ng-êi dông. C¸c thuËt to¸n
chän ®-êng thÓ nhãm thµnh hai lo¹i chÝnh : thuËt to¸n chän ®-êng tÜnh vµ
®éng.
5
1.2.1.1-ThuËt to¸n chän ®-êng tÜnh (thuËt to¸n kh«ng thÝch nghi)
Kh«ng dùa trªn quyÕt ®Þnh chän ®-êng phô thuéc vµo viÖc ®¸nh gi¸ t¶i
hiÖn thêi kiÕn tróc h×nh häc hiÖn thêi. Thay vµo ®ã viÖc chän ®-êng ®-îc
tÝnh to¸n tr-íc, ®-îc chuyÓn ®Õn ®Þnh tuyÕn khi ®Þnh tuyÕn ®-îc
khëi ®éng. C¸c thuËt to¸n chän ®-êng tÜnh nh- :
Chän ®-êng ng¾n nhÊt : ý t-ëng lµ x©y dùng mét ®å thÞ cña mét m¹ng
con mçi nót lµ mét bé ®Þnh tuyÕn, vµ mçi c¹nh cña ®å thÞ lµ mét ®-êng truyÒn
th«ng kÕt nèi c¸c ®Þnh tuyÕn. §Ó chän ®-êng gi÷a hai ®Þnh tuyÕn nµo
®ã , gi¶i thuËt chän ®-êng ®i ng¾n nhÊt gi÷a chóng trªn ®å thÞ. Kh¸i niÖm
ng¾n nhÊt ë ®©y cÇn hiÓu lµ : Sè chÆng, kho¶ng c¸ch ®Þa lý theo km, trÔ truyÒn
t¶i. Gi¶i thuËt Dijikstra ®-îc ¸p dông cho tÝnh to¸n ®-êng ®i ng¾n nhÊt gi÷a
hai nót trªn ®å thÞ.
Trót ®æ: Nh÷ng gãi tin vµo ®-îc göi trªn tÊt c¸c ®-êng trõ ®-êng
võa ®Õn vµ ®-êng ®· bÞ chiÕm. Nh- vËy trót ®æ t¹o ra mét sè l-îng lín c¸c gãi
tin trïng lÆp. Mét biÖm ph¸p ®-îc ®-a ra ®Ó kh¾c phôc nh- : Dïng
®Õm chÆng chøa trong phÇn ®Çu gãi tin, ®¸nh sè thø cho gãi tin g¸n
tr-êng tuæi (age) cho tõng gãi tin.
Chän ®-êng theo dßng: Trong mét sè m¹ng, b×nh qu©n dßng d÷ liÖu gi÷a
tõng cÆp nót t-¬ng ®èi æn ®Þnh t®o¸n ®-îc. thÓ ph©n t¸ch c¸c
dßng mét c¸ch to¸n häc ®Ó tèi -u viÖc chän ®-êng. §Ó dïng thuËt nµy,
th«ng tin ph¶i ®-îc biÕt tr-íc nh-: Bè trÝ cña Subnet, ma trËn giao th«ng, c
®é cho phÐp cña ®-êng.
1.2.1.2-ThuËt to¸n chän ®-êng ®éng (thuËt to¸n thÝch nghi )
Thay ®æi quyÕt ®Þnh chän ®-êng theo thay ®æi cña u tróc h×nh häc,
còng nh- l-u l-îng. ThuËt to¸n nµy lÊy th«ng tin ( mét c¸ch côc bé, c¸c
chän ®-êng l©n cËn hoÆc tÊt c¶ c¸c chän ®-êng) khi chóng thay ®æi c¸c
®-êng (sau mét thêi gian ng¾n khi t¶i thay ®æi, khi cÊu tróc h×nh häc thay ®æi)
th-íc ®o ®-îc dông cho viÖc tèi -u (kho¶ng c¸ch, chÆng hoÆc thêi
6
gian chuyÓn dÞch). C¸c m¹ng m¸y tÝnh hiÖn ®¹i nãi chung dông c¸c thuËt
to¸n ®éng h¬n tÜnh. C¸c thuËt to¸n chän ®-êng ®éng ®-îc sö dông réng r·i
lµ:
Chän ®-êng theo vector kho¶ng c¸ch: Mçi ®Þnh tuyÕn duy tr× mét
b¶ng ®Þnh tuyÕn ( b¶ng vector) mang néi dung vÒ ®-êng truyÒn thÝch hîp ®Õn
®Ých vµ -íc l-îng thêi gian hay kho¶ng c¸ch ®Õn ®Ých ®ã. Cã hai ®¹i l-îng
thÓ ¸p dông ®Ó tÝnh ®-êng dÉn tèt nhÊt ®o b»ng chÆng nnhÊt ®o
b»ng ®é trÔ nhá nhÊt. C¸c b¶ng ®Þnh tuyÕn ®-îc cËp nhËt bëi trao ®æi th«ng
tin víi c¸c bé ®Þnh tuyÕn l©n cËn.
Chän ®-êng theo tr¹ng th¸i ®-êng kÕt nèi : C¸c thuËt to¸n tr-íc ®©y
kh«ng quan t©m ®Õn ®é réng b¨ng th«ng trong viÖc chän ®-êng. ý t-ëng cña
thuËt to¸n chän ®-êng theo tr¹ng th¸i kÕt nèi ®-îc ph¸t biÓu nh- sau, mçi
®Þnh tuyÕn ph¶i :
+ Ph¸t hiÖn ra c¸c hµng xãm vµ häc ®Þa chØ cña chóng
+ §o ®é trÔ hay chi phÝ cho tõng ®é trÔ cña ®-êng truyÒn
+ X©y dùng c¸c gãi d÷ liÖu ®Ó trao ®æi th«ng tin thu ®-îc tõ viÖc häc.
+ Göu c¸c gãi tin nµy ®Õn c¸c bé ®Þnh tuyÕn kh¸c.
+ TÝnh to¸n c¸c ®-êng dÉn ng¾n nhÊt ®Õn mçi bé ®Þnh tuyÕn kh¸c.
Ngay khi ®Þnh tuyÕn thu nhËn ®-îc ®Çy c¸c gãi d÷ liÖu tr¹ng th¸i
®-êng kÕt nèi, x©y dùng nªn kiÕn tróc h×nh häc cña m¹ng (mét ®å thÞ)
gi¸ trªn c¸c ®-êng ®i gi÷a c¸c nót. Sau ®ã thuËt to¸n Dijikstra thÓ ®-îc
dông ®Ó chän ®-êng ®i ng¾n nhÊt ®Õn mçi bé ®Þnh tuyÕn .
1.2.2-C¸c giao thøc ®Þnh tuyÕn
C¸c giao thøc ®Þnh tuyÕn ph¶i ®¹t ®-îc ®ång thêi c¸c yªu cÇu sau:
- Kh¸m ph¸ ®éng topo cña m¹ng
- X©y dùng c¸c c©y ®-êng ng¾n nhÊt
- KiÓm so¸t tãm t¾t th«ng tin vÒ c¸c m¹ng bªn ngoµi
7
- Ph¶n øng nhanh víi thay ®æi topo cña m¹ng cËp nhËt c¸c c©y
®-êng ng¾n nhÊt
- Lµm tÊt c¶ c¸c ®iÒu trªn theo ®Þnh kú thêi gian.
Giao thøc ®Þnh tuyÕn IGP (Interior Gateway Protocol) giao thøc ®Þnh
tuyÕn ®-îc sö dông trong ph¹m vi mét m¹ng. Giao thøc EGP (Exterior
Gateway Protocol) giao thøc ®Þnh tuyÕn ®-îc dông gi÷a c¸c m¹ng.
thèng trÞ (AS) thèng ®-îc qu¶n ®éc lËp bëi c¸c chñ h÷u kh¸c
nhau vµ cã thÓ cã c¸c thuËt to¸n riªng bªn trong nã. AS lµ mét tËp c¸c bé ®Þnh
tuyÕn cña mét nhµ qu¶n duy nhÊt, dông cïng mét giao thøc ®Þnh tuyÕn
IGP, gi÷a c¸c AS dïng giao thøc EGP
1.2.2.1-Giao thøc ®Þnh tuyÕn IGP
RIP( Routing Information Protocol)
§©y giao thøc ®Çu tiªn cña Internet, giao thøc nµy dông thuËt to¸n
chän ®-êng theo vector kho¶ng c¸ch víi ®¹i l-îng ®o chÆng. RIP göu
mét th«ng b¸o cËp nhËt theo chu kú 30 gi©y mét lÇn vµ khi cÊu tróc m¹ng thay
®æi, th«ng b¸o gåm toµn b¶ng ®-êng truyÒn ®Õn c¸c ®Þnh tuyÕn. Tr¸nh
lÆp (loop) b»ng c¸ch giíi h¹n sè chÆng (hop) cho phÐp truyÒn trªn mét ®-êng
tõ nguån ®Õn ®Ých lµ 15. ¦u ®iÓm : thuËt to¸n ®¬n gi¶n, thêi gian sö lý nhanh.
Nh-îc ®iÓm : l-îng chÆng n nhÊt mµ RIP cung cÊp ®Ó truyÒn 15, ®iÒu
nµy cã nghÜa lµ RIP chØ phï hîp víi hÖ thèng nhá.
IGRP(Interior Gateway Routing Protocol)
giao thøc dông thuËt to¸n chän ®-êng theo vector kho¶ng c¸ch víi
®¹i l-îng ®o tæng hîp cña nhiÒu biÕn nh- b¨ng th«ng, ®é t, t¶i träng, ®é
tin cËy,thêi gian chiÕm kªnh . IGRP chØ cã trªn c¸c bé ®Þnh tuyÕn cña Cisco.
EIGRP(Enhanced Interior Gateway Routing Protocol)
phiªn b¶n c¶i tiÕn cña IGRP, cung cÊp c¸c tiÕn tr×nh cËp nhËt t¹i c¸c
thêi kho¶ng kh¸c nhau ®Ó ph¶n ¸nh nh÷ng thay ®æi cña m¹ng nh-: t¶i, cÊu
tróc.
8
IS-IS ( Intermediate System- Intermediate System )
giao thøc theo tr¹ng th¸i ®-êng kÕt nèi, ®-îc thiÕt bëi DECnet
sau ®ã ®-îc chÊp nhËn bëi ISO ®-îc dông víi giao thøc tÇng ng kh«ng
kÕt nèi.
OSPF( Open Shortest Path First )
giao thøc theo tr¹ng th¸i ®-êng kÕt nèi . Ra ®êi n¨m 1988 vµ thµnh
chuÈn n¨m 1990. NhiÒu nhµ s¶n xuÊt hç trî giao thøc nµy vµ ®· trë thµnh giao
thøc phæ biÕn hiÖn nay.
OSPF hç trî 3 lo¹i kÕt nèi vµ m¹ng:
+ C¸c ®-êng nèi ®iÓm gi÷a 2 bé ®Þnh tuyÕn,
+ C¸c m¹ng ®a truy nhËp víi qu¶ng b¸
+ C¸c m¹ng ®a truy nhËp kh«ng qu¶ng b¸
M¹ng ®a truy nhËp: m¹ng thÓ nhiÒu ®Þnh tuyÕn trªn ®ã, mçi
®Þnh tuyÕn thÓ truyÒn th«ng ®-îc víi tÊt c¸c ®Þnh tuyÕn kh¸c,
LAN vµ WAN cã tÝnh chÊt nµy.
OSPF lµm viÖc b»ng c¸ch lËp mét ®å tc¸c ®Þnh tuyÕn nh÷ng
®-êng truyÒn. nhiÒu AS trong Internet rÊt lín vµ khã qu¶n lý, OSPF cho
phÐp chia chóng thµnh c¸c khu vùc ®¸nh , trong ®ã i khu vùc mét
m¹ng hay mét tËp hîp m¹ng. Trong cïng mét AS c¸c ®Þnh tuyÕn cïng
liÖu tr¹ng th¸i kÕt nèi ch¹y cïng thuËt to¸n ®-êng dÉn ng¾n nhÊt.
NÕu mét bé ®Þnh tuyÕn kÕt nèi ®Õn hai khu vùc cÇn cã c¬ së d÷ liÖu cho c¶ hai
khu vùc ph¶i ch¹y thuËt to¸n chän ®-êng cho tõng c¸i riªng rÏ. C¸ch thøc
OSPF qu¶n c¸c lo¹i dÞch chän ®-êng mçi mét ®Þnh tuyÕn l-u gi÷
nhiÒu ®å thÞ. ®Þnh tuyÕn dùa vµo nh÷ng ®å thÞ nµy ®Ó ph©n tÝch c¸c ®-êng
dÉn tèi -u vÒ c¶ ®é trÔ, th«ng l-îng vµ ®é tin c©y.
C¸c lo¹i th«ng ®iÖp cña OSPF
9
Hello
Dïng ®Ó kh¸m ph¸ ai lµ l¸ng giÒng
Data Base Description
M« t¶ c¬ së d÷ liÖu
Link State Request
Yªu cÇu tr¹ng th¸i kÕt nèi
Link State Update
CËp nhËt tr¹ng th¸i kÕt nèi
Link State Ack
X¸c nhËn tr¹ng th¸i kÕt nèi
B¶ng 1.1-C¸c lo¹i th«ng ®iÖp cña OSPF
1.2.2.2-Giao thøc ®Þnh tuyÕn EGP
BGP(Borde Gateway Protocol)
BGP giao thøc ®Þnh tuyÕn gi÷a c¸c AS, chøc n¨ng chÝnh cña thèng
BGP lµ trao ®æi th«ng tin m¹ng “cã thÓ tíi ®îc ”gi÷a c¸c hÖ thèng. Th«ng tin
m¹ng thÓ tíi ®-îc nµy bao gåm th«ng tin trªn danh s¸ch cña c¸c AS
th«ng tin “cã thÓ tíi ®îc ®i ngang qua. Th«ng tin y ®ñ ®Ó x©y dùng mét
graph cña liªn kÕt AS ®ã c¸c tuyÕn lÆp ®-îc c¾t tØa mét quyÕt ®Þnh
chÝnh s¸ch t¹i møc AS thÓ ®-îc b¾t buéc. Mçi BGP Router duy tr× mét
b¶ng ®Þnh tuyÕn duyÖt ra tÊt c¸c ®-êng thÓ ®-îc ®Ó tíi mét m¹ng.
Th«ng tin ®Þnh tuyÕn nhËn tõ c¸c ®Þnh tuyÕn vïng liªn kÕt ®-îc gi÷ l¹i cho
®Õn khi t cËp nhËt míi ®-îc nhËn. Khi nµo mét ®Þnh tuyÕn n ®Çu tiªn
®-îc nèi víi m¹ng, BGP Router trao ®æi toµn bé b¶ng ®Þnh tuyÕn BGP. T-¬ng
khi b¶ng ®Þnh tuyÕn thay ®æi, c¸c ®Þnh tuyÕn göi phÇn b¶ng ®Þnh tuyÕn
cña chóng bÞ thay ®æi. C¸c BGP router kh«ng lËp lÞch tr×nh cho viÖc cËp nhËt
th«ng tin ®Þnh tuyÕn ®Þnh tuyÕn BGP cËp nhËt th«ng b¸o chØ nh÷ng ®-êng
tèt nhÊt tíi m¹ng.
BGP thùc hiÖn 3 lo¹i ®Þnh tuyÕn
- Inter-Autonomous System Routing: gi÷a hai hay nhiÒu BGP router
trong c¸c AS kh¸c nhau
- Intra-Autonomous System Routing: gi÷a hai hay nhiÒu BGP router
trong ph¹m vi cïng mét AS
10
- Pass-though Autonomous System Routing: gi÷a hai hay nhiÒu BGP
router ngang hµng trao ®æi l-u l-îng qua mét AS trung gian kh«ng
ch¹y BGP
BGP duy tr× mét b¶ng ®Þnh tuyÕn t¹i mçi ®Þnh tuyÕn. c b¶n tin trao
®æi gi÷a c¸c bé ®Þnh tuyÕn :
Open
Mang c¸c th«ng tin chung vÒ bé ®Þnh tuyÕn göi
Keepalive
Bªn nhËn x¸c nhËn ®· nhËn ®-îc Open
Update
Sau ®ã nã göi ®Õn tÊt c¶ c¸c hµng xãm
Notification
Th«ng b¸o mét kÕt nèi BGP bÞ lçi
B¶ng 1.2 -C¸c b¶n tin trao ®æi gi÷a c¸c bé ®Þnh tuyÕn trong BGP
C¸c b¶ng th«ng tin ®Þnh tuyÕn trong BGP :
+ B¶ng Adj-RIB-In(Adjacency Routing Information Base Input):
CSDL l-u th«ng tin ®Þnh tuyÕn ®Þnh tuyÕn BGP nhËn ®-îc c¸c hµng
xãm cña nã. ®Þnh tuyÕn BGP l-u trong c¸c b¶ng Adj-RIB-In kh¸c nhau
t-¬ng øng víi c¸c hµng xãm kh¸c nhau.
+ B¶ng Local-RIB (Local Routing Information Base): CSDL l-u c¸c
tuyÕn tèi -u nhËn ®-îc trªn thùc hiÖn thuËt to¸n chän tuyÕn tèi -u víi
c¸c ®Çu vµo lµ c¸c b¶ng CSDL Adj-RIB-In.
+ B¶ng Adj-RIB-Out(Adjacency Routing Information Base Output):
CSDL l-u th«ng tin ®Þnh tuyÕn ®Þnh tuyÕn BGP nµy göi tíi c¸c hµng
xãm cña nã.
BGPv4 cung cÊp mét tËp hîp c¸c chÕ míi cho viÖc hç trî c¸c líp ®Þnh
tuyÕn ®a miÒn. C¸c c¬ chÕ nµy bao gåm viÖc trî cho th«ng b¸o mét tiÒn
IP h¹n chÕ kh¸i niÖm líp m¹ng trong ph¹m vi BGP. BGP4 còng giíi thiÖu
c¬ chÕ cho phÐp tËp hîp c¸c tuyÕn, kÓ c¶ tËp hîp c¸c ®-êng AS.
Trªn ®©y tr×nh bÇy c¸c giao thøc ®Þnh tuyÕn trong tÇng m¹ng, mét sè giao
thøc ta sÏ thÊy ®-îc sö dông trong MPLS.