ĐỀ TÀI: GIAO THỨC ĐỊNH TUYẾN ĐỘNG OSPF

Ọ

Đ I H C KHOA H C - HU Ế B MÔN ĐI N T VI N THÔNG Ệ Ử Ễ

Ạ Ọ Ộ

Nhóm 12:

Nguy n Ng c Thanh Lê H ng Vi

ọ t ệ

ễ

ễ ồ Nguy n Đình Hoàng Nam ng Ph m Gia L ươ ạ Lê Tr n Qu c Đ t ạ ố

ầ

BÀI BÁO CÁO

A. GI I THI U CHUNG

ọ ế ự ườ ng đi trên m ng đ g i d ạ ể ử ữ

ứ ị

ng đi t t nh t t ế ướ ườ ế ị ỉ ấ ừ ế ngu n đ n ồ

ồ

Ệ Ớ 1. Khái ni m:ệ Đ nh tuy n là quá trình l a ch n đ ị li u.ệ 2. Ch c Năng Đ nh Tuy n: ng và đ Đ nh tuy n giúp ch ra h ố đích thông qua các node trung gian là các router 3. Phân lo i:ạ G m có 2 lo i: ạ ị ế ộ ạ

ế ụ ng ườ ậ c các router c p

ậ ị

1) Đ nh tuy n đ ng : là đ nh tuy n mà có tr ng thái đ ị đi (link State) thay đ i liên t c, đ ượ ổ nh t liên t c do đó mang tính linh đ ng cao ộ ố ị ườ ạ ả ấ ng đi là c đ nh khi có thay đ i ổ ớ i. Ch phù h p v i ợ ỉ

ụ 2) Đ nh tuy n tĩnh: đ ế trong m ng thì ph i c u hình l ạ ỏ m ng nh . ạ

ế i trong môi tr ng internet t n t ồ ạ ườ ể ế

ể ế

• Đ nh Tuy n: ị ộ i Các ki u đ nh tuy n đ ng Hi n t ị ệ ạ nh : RIP, IGRP, EIGRP, OSPF,ISIS, BGP các ki u đ nh tuy n này ị ư ng khác nhau chia thành hai nhóm sau: s d ng các thu t toán tìm đ ử ụ ườ ậ

- Distance vector : RIP, IGRP, EIGRP,BGP - Link State : OSPF, ISIS.

B. GIAO TH C Đ NH TUY N OSPF Ế

1. GI Ề

Ệ ứ ị ế

Ứ Ị I THI U V OSPF: Ớ - OSPF là giao th c đ nh tuy n đ ng s d ng giao th c “link state” đã ộ c chuy n hóa. Đ c phát tri n đ thay th thu t toán Distance ể ử ụ ể ứ ậ ượ ế ể

đ ượ vecto.

- OSPF s d ng thu t toán tìm đ ả ng Dijkstra đ tính toán ra qu ng ể

ng ng n nh t, s d ng cost đ làm metric. ử ụ ắ ậ ấ ử ụ

ủ ề ạ ứ ẽ

ầ ọ ườ ộ ề ạ ộ

ườ đ ườ ể M i router s có m t Database ch a thông tin đ y đ v m ng mà ỗ nó đang ch y OSPF đi u này cho phép nó ch n đ ng m t cách thông minh,nhanh chóng, linh ho t .ạ - OSPF phù h p v i m ng l n. ợ ạ ớ ớ

Ể

2. CÁC GIAI ĐO N PHÁT TRI N: Ạ c b t đ u nghiên t ắ ầ ừ năm 1987 cho đ n nay đã tr i qua ế ả

ề

OSPF đ ượ nhi u phiên b n khác: ả 1989: ver1 1991: ver2 1998: ver2u 1998: ipv6

Ộ Ỗ

ng Link state hi u qu cao ườ ệ ả

3. NH NG TÍNH NĂNG N I TR I: Ữ nhanh - T c đ h i t ố ộ ộ ụ ng theo tr ng thái đ - Ch n đ ạ ọ ườ - Đ ng đi linh ho t h n ườ ạ ơ - H tr mang con VLSM ỗ ợ ớ . - Có th áp d ng cho m ng l n ạ ụ ể

C. NGUYÊN LÝ HO T Đ NG C A GIAO TH C Đ NH TUY N Ộ Ủ Ứ Ạ Ế Ị

OSPF

•

ạ ơ ả ủ

ạ ộ c thì router s ạ các tr ng thái khác nhau, g m các tr ng ẽ ở ạ ồ

Quá trình ho t đ ng c a OSPF chia làm các giai đo n c b n sau : m i b Ở ỗ ướ thái sau :

ạ

- Down: là tr ng thái không liên l c v i các router khác. Init: tr ng thái thi ề ừ - - 2-way: tr ng thái thi ạ

router g i. ế ậ ư ạ ộ ử

ạ ớ t l p nh ng ch theo m t chi u t ỉ ế ậ t l p theo hai chi u ề

- Exstart: thi

ế ậ ệ ằ

- Exchange: thông tin đ nh tuy n s đ

ổ t l p quan h Master/slave b ng cách trao đ i database description(dd) packet. Router có router ID cao nh t sấ ẽ là master.

c trao đ i qua dd và ẽ ươ ế ị ổ

lsr(link state request)

- Loading : quá trình c p nh t thông tin LSA đ ậ ượ c b t đ u khi ắ ầ

ậ c g i đ n Neghibor

LSR đ - Full : t t c các LSA đã đ c đ ng b gi a các Adjacency. ượ ử ế ấ ả ươ ồ ộ ữ

1. BÌNH CH N ROUTER ID:

• Đ u tiên, khi m t router ch y OSPF, nó ph i ch ra m t giá tr dùng đ Ọ ộ ả ạ ộ ỉ ị

ạ ấ ồ

c g i là Router – id. ể ầ đ nh danh duy nh t cho nó trong c ng đ ng các router ch y OSPF. Giá ị ộ tr này đ ị ượ ọ

ạ ủ ỉ ị

ế ặ ị ầ

ấ ị ỉ

• Router – id trên router ch y OSPF có đ nh d ng c a m t đ a ch IP. ộ ị ạ ị M c đ nh, ti n trình OSPF trên m i router s t đ ng b u ch n giá tr ọ ẽ ự ộ ỗ ư router – id là đ a ch IP cao nh t trong các interface đang active, nh ng nó u tiên c ng loopback. ổ - Ta cùng làm rõ ý này thông qua ví d :ụ

• Ch đ a ch c a các interface đang active, t c là ầ

ỉ ị ỉ ủ ứ

ớ ượ ấ

ẽ ỉ

tr ng thái up/up ở ạ c tham gia b u ch n. Ta th y trên (status up, line protocol up) m i đ ọ hình , ch có hai c ng F0/0 và F0/1 c a R là up/up nên router R s ch ỉ ủ xem xét hai đ a ch trên hai c ng này là 192.168.1.1 và 192.168.2.1 ổ ỉ ổ ị

ị ị ể ế

ỉ ị ơ ả

ỉ ừ c xem là l n h n ầ • Đ xác đ nh trong hai đ a ch này, đ a ch nào là cao h n, R ti n hành so ỉ ị trái sang ph i, đ a ch nào có ừ ơ ỉ ớ ơ ượ

• Ta th y, v i cách so sánh này, đ a ch 192.168.2.1 đ sánh hai đ a ch này theo t ng octet t ị octet đ u tiên l n h n đ ớ ỉ ớ ơ c xem là l n h n ượ ớ ị

c s d ng đ làm router – id đ a ch 192.168.1.1 nên nó s đ ị ẽ ượ ử ụ ể

ẽ ậ

ị ủ ổ ị ỉ

ượ ư ấ ổ

ọ

ta xét router có thêm thành ph n c ng loopback: ầ - Bây gi ấ ỉ => V y R s tham gia OSPF v i giá tr ‘nick name’ – router id là ớ 192.168.2.1.. Tuy đ a ch 203.162.4.1 c a c ng serial S0/1/0 trên c tham router R là l n nh t nh ng vì c ng này down nên không đ ớ gia b u ch n. ờ ầ ổ

ầ ẽ ỏ

xét các đ a ch c a các interface v t lý • Vì l n này có các interface loopback nên Router s b qua, không xem ậ ỉ ủ ị

• Hai đ a ch c a hai interface loopback 1 và 2 s đ ị ỉ ủ ẽ ượ

ể ọ c so sánh đ ch n ra router – id cho router R, và ta th y rõ ràng 2.2.2.2 > 1.1.1.1 nên router ấ R s ch n 2.2.2.2 làm router – id khi tham gia OSPF ẽ ọ

ẽ ọ

c ti p theo là thi • Sau khi đã ch n xong router – id router ch y OSPF s chuy n qua ể ạ ế ố t l p quan h láng gi ng v i các router k t n i ế ậ ệ ề ớ

b ế ướ tr c ti p v i nó ự ế ớ

2. THI T L P QUAN H LÁNG GI NG Ậ Ế Ệ Ề

• Sau khi đã ch n xong router – id, router ch y OSPF s g i ra t t c các ẽ ử ạ ọ ấ ả

ạ

• Gói tin này đ ử ế

c g i đ n đ a ch multicast dành riêng cho OSPF là ạ t c các router ch y OSPF khác trên cùng phân đo n ỉ ạ

• M c đích c a gói tin hello là giúp cho router tìm ki m láng gi ng, thi c ng ch y OSPF gói tin Hello. ổ ị ượ 224.0.0.5, đ n t ế ấ ả m ng.ạ ụ ủ

ế t ề c g i theo đ nh kỳ ế ượ ử ị ệ

l p và duy trì m i quan h này. Gói tin hello đ ậ ố m c đ nh 10s/l n. ặ ị ầ

• Có nhi u thông tin đ ề ượ ế

ắ ộ

c quan h láng gi ng v i nhau. c hai router k t n i tr c ti p trao đ i v i ổ ớ ế ố ự ạ c trao đ i, có 5 lo i nhau qua gói tin hello. Trong các lo i thông tin đ ổ ượ ạ thông tin sau b t bu c ph i match v i nhau trên hai router đ chúng có ể ớ th thi ề ể t l p đ ế ậ ượ ả ệ ớ

• Hello Packet:

ị

ỏ

- Area – id - Hello timer và Dead timer - Hai đ a ch IP đ u n i ph i cùng subnet ấ ố ả ỉ - Th a mãn các đi u ki n xác th c. ề - Cùng b t ho c cùng t ự t c stub ệ ắ ờ ậ ặ

Ổ

ơ ở ữ ệ ườ ả ạ

3. TRAO Đ I LSDB ( link state database) LSDB – Link State Database – B ng c s d li u tr ng thái đ ng link là ng link c a m i router trong m t b ng trên router ghi nh m i tr ng thái đ ọ ớ ọ ạ ộ ả ườ ủ

ộ ả ư ồ ạ ứ ẽ

ị vùng. Ta xem LSDB nh là m t “t m b n đ m ng” mà router s căn c ấ vào đó đ tính toán đ nh tuy n ế

ể

ữ ố

ể • Đ c đi m : ặ - LSDB ph i hoàn toàn gi ng nhau gi a các router cùng vùng - LSDB đ ả ượ ữ ỏ ơ

c chia nh ra thành nh ng đ n v thông tin LSA (link ộ i ch a trong m t ư ạ ơ ị

ị state advertisment) các đ n v thông tin này l gói tin c th g i là LSU(link state update)

ấ ệ ễ ừ ụ ể ọ ổ

ẽ

ử ụ ạ ế ố ể

ữ ứ ể ể ạ ặ

ậ ứ ử ề ẽ

ế ố ệ ừ ể

ạ - Vi c trao đ i thông tin di n ra r t khác nhau tùy theo t ng lo i network – type gán cho link gi a hai router, ta s nói qua 2 lo i ạ ữ network s d ng trong OSPF là: point to point, và multibroadcast. • Point to point : Lo i link point – to – point đi n hình là k t n i serial đi m – đi m ch y giao th c HDLC ho c PPP n i gi a hai router. hai router láng gi ng s ngay l p t c g i toàn b b ng LSDB cho nhau qua k t n i point – to – point và chuy n tr ng thái quan h t 2 – WAY sang m t m c đ m i g i là quan h d ng FULL ố ộ ả ạ ệ ạ ứ ộ ớ ọ ộ

ế ố ự ng này, m i router đ u k t n i tr c ỗ

• Broadcast multiacess: V i môi tr ti p v i nhau và đ u ph i thi t l p quan h 2 – WAY v i nhau ườ ế ậ ớ ả ế ề ớ ệ ề ớ

• Các router s không trao đ i thông tin tr c ti p v i nhau mà thông qua ự ế ớ ổ

ộ ệ

m t router đ i di n là DR(Designate router ) & BDR(Back DR). ẽ ượ ậ

c ch n làm DR cao th 2 là - Router có đ a ch IP cao nh t đ ọ ấ ượ c ch n nh th nào ?? ư ế ọ ứ ẽ ạ V y DR & BDR s đ ỉ ị

BDR.

- Khi đã có DR &BDR thì các router khác trong local network đó

- Các b n tin LSA(link state acknownledment: mô t s tr thành DRother. ẽ ở ả ả

ủ ỉ ử ươ ế

ị

ượ ử ế

c do DR&BDR phân ph i l các tr ng thái ạ c đ n các DR & BDR c c p dành cho giao th c OSPF là ứ ẽ i theo đ a ch multicast là ỉ ố ạ

và các interface c a các router) ch g i đ theo đ a ch multicast đ ấ ỉ 224.0.0.6 ch không g i đ n các DR other ( các router này s ứ đ ị ượ 224.0.0.5 ) nh m tránh tình tr ng flooding LSA ằ ạ

Ị Ế

ng đi 4. TÍNH TOÁN B NG Đ NH TUY N. Ả • Tr ị ế ề ể ướ ườ

ẽ

• Metric trong OSPF đ ị

ng truy n theo công th c nh sau: ị ủ ườ c xác đ nh d a vào ư ự ứ

(metric), sau đó s tìm hi u thu t toán Dijkstra. ượ ọ bandwidth danh đ nh c a đ Metric = cost = 10^8/Bandwidth (đ n v bps).

c h t ta cùng tìm hi u cách xác đ nh chi u dài đ ể ậ c g i là cost, đ ượ ề ơ ị • D a vào công th c metric đã nêu trên, ta có giá tr cost default ở ứ ị

ộ ố ạ ổ

ỏ ầ ậ

ự c a m t s lo i c ng: ủ Ethernet (BW = 10Mbps) -> cost = 10. Fast Ethernet (BW = 100Mbps) -> cost = 1. Serial (BW = 1.544Mbps) -> cost = 64 (b ph n th p phân trong phép chia).

 Xét ví d :ụ

ng đi • Yêu c u đ t ra v i s đ trên là tính path – cost (metric) cho đ ặ ầ ườ

ế t ừ

ể ủ ổ ừ ộ

ng (path) nào đó, ta th c hi n l n ng ớ ơ ồ R1 đ n m ng 192.168.3.0/24 c a R3. • Nguyên t c c ng cost : Đ tính t ng cost t ự

ệ ầ ộ ắ

ạ ạ m t router đ n m t m ng ộ ế ắ ộ ầ đích l n đích theo m t đ c t ượ ừ ộ ườ v và c ng d n cost theo quy t c đi vào thì c ng, đi ra thì không c ng. ộ ồ ộ ề áp d ng cho ví d trên

ụ ạ ị

ả ậ ỏ ờ

ụ B n nào có th tính giúp mình giá tr này ? ể ế ộ ộ ố ụ

• Thu t toán SPF ti n hành tính toán đòi h i m t kho ng th i gian th i ờ gian này ph thu c vào tính ch t c a vùng (s router, đ l n c a d ộ ớ ủ ữ ấ ủ li u………….). ệ

ậ ể ử ụ

ể ả ử ị

t c s ta có U0 là đi m ngu n ta cân xác đ nh tu n t ồ nh đ n l n . g i V là t p ch a t ọ ừ ậ ầ ự ậ ỏ ế ớ ế ể

ế

c tiên đi m có kho ng cách nh nh t đ n U0 là U0 hay chính ỏ ể ướ ấ ế ể ả

• OSPF s d ng thu t toán Dijkstra đ tìm SPF. Thu t toán nh sau :. ) ư • Gi kho ng cách ả ứ ấ ả c a các đi m khác đ n UO t ủ các đi m có liên k t nhau. - Tr nó.

ế ỏ

- Trong t p V\{U0} tìm đi m có kho ng cách đ n U0 nh ể ề ớ ậ ể ể ấ ả

- Trong V\{U0,U1} tìm đi m có kho ng cách đ n U0 nh ả nh t( đi m này ph i là đi m k v i U0) gi ả ử ả s là đi m U1. ể ế ể ỏ

ể ắ

U0 nh t( đi m này ph i k v i U0 ho c U1) gi ả ề ớ - Ti p t c nh v y cho đ n khi nào tìm đ ế ư ậ ả ử ượ s đó là U2 c kho ng cách t ả ừ

ấ ế ụ đ n m i đ nh. ế ọ ỉ

 chú ý : T ngu n t i chính nó thì kho ng cách =0 ồ ớ ừ ả

ệ

ế ả ồ t kê trong danh sach thì tính ế ng ng n nh t, n u ọ ườ ắ ấ

N u có các nút k v i các nút đã li ề ớ xem kho ng cách là bao nhiêu r i sau đó ch n đ không có thì xem nh b ng vô cùng ư ằ

ả ư ả ử

s các kho ng cách nh sau : ế ế ế

Gi 1 đ n 3 = 2 ;1 đên 2 = 3; 2 đ n 4= 4; 2 đ n 5= 4; 3 đ n 6 =1; 4 đ n ế ế 5=3; 5 đ n 6= 2; ế T p V={1,2,3,4,5,6} ậ

D2 D3 D4 D5 D6

3 √ √ 3

∞ 3 √

5 4 4 √

∞ ∞ 7 5 √

D V\{i} Ban đ uầ 1 1 2 3 4 5 1,3 1,3,2 1,3,2,6 1,3,2,6,4 1,3,2,6,4,5

• Duy trì thông tin LSD và b ng đ nh tuy n ế ả ị

• Khi có m t s thay đ i nào đó v tr ng thái đ ổ

ộ ự ườ

ậ ứ ề ạ ọ

ộ ộ ị

ng liên k t. router ế ờ ngay l p t c phát ra thông báo cho m i router khác trong m ng. th i ạ gian Deadinterval là m t thông s đ xác đ nh xem m t router láng ố ể gi ng còn ho t đ ng hay không. ạ ộ ề