Bài giảng mạng máy tính: Giải thuật định tuyến

Chia sẻ: MAI TAT DAT | Ngày: | Loại File: PDF | Số trang:0

Thêm vào BST

Báo xấu

259
lượt xem 40
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Tham khảo bài thuyết trình 'bài giảng mạng máy tính: giải thuật định tuyến', công nghệ thông tin, quản trị mạng phục vụ nhu cầu học tập, nghiên cứu và làm việc hiệu quả

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng mạng máy tính: Giải thuật định tuyến

Chương 8 GI I THU T NH TUY N (ROUTING ALGORITHM) 4-1 Gi i thu t nh tuy n
N I DUNG T ng quan Link state Distance Vector Hierarchical routing 4-2 Gi i thu t nh tuy n
T ng quan: Ph i h p gi a routing và forwarding routing algorithm local forwarding table header value output link 0100 3 0101 2 0111 2 1001 1 Tham s trong header c a gói n 1 0111 32 4-3 Gi i thu t nh tuy n
T ng quan: th m ng 5 3 v w 5 2 u z 2 1 3 1 2 x y 1 Graph: G = (N,E) N = t p các router = { u, v, w, x, y, z } E = t p các liên k t={ (u,v), (u,x), (v,x), (v,w), (x,w), (x,y), (w,y), (w,z), (y,z) } th m ng cũng h u d ng trong các ng c nh m ng khác Ví d : P2P, v i N là tâp các peer và E là t p các k t n i TCP 4-4 Gi i thu t nh tuy n
T ng quan: Chi phí liên k t (cost) 5 • c(x,x’) = chi phí c a liên k t (x,x’) 3 v w 5 - ví d c(w,z) = 5 2 u z 2 1 3 • chi phí ư c xác nh tùy theo 1 các y u t như băng thông, m c 2 x y ngh n... 1 Chi phí c a ư ng i (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp) Câu h i: âu là ư ng i có chi phí nh nh t gi a u và z ? Gi i thu t nh tuy n s xác nh ư ng i có chi phí nh nh t 4-5 Gi i thu t nh tuy n
T ng quan: Phân lo i gi i thu t nh tuy n Thông tin toàn c c hay Tĩnh hay ng? phân tán? Tĩnh: Toàn c c: Ì Các tuy n ư c xác l p và Ì T t c các router bi t toàn thay i b i ngư i qu n tr b topo v i thông tin v chi ng: phí Ì Các gi i thu t “link state” Ì Các tuy n thay i nhanh, Phân tán: t ng Ì router bi t các láng gi ng và H C p nh t theo th i gian chi phí n i n ó H Thích ng v i các thay Ì Quá trình tính toán l p l i, i c a chi phí trên liên trao i thông tin v i các láng gi ng kt Ì Các gi i thu t “distance vector” 4-6 Gi i thu t nh tuy n
N I DUNG T ng quan Link state Distance Vector Hierarchical routing 4-7 Gi i thu t nh tuy n
M t gi i thu t Link-State Gi i thu t Dijkstra Ký hi u: Ì Các node bi t t t c topo Ì c(x,y): chi phí t node x m ng n y; = ∞ n u không n i H Có ư c qua "qu ng bá tr c ti p tr ng thái liên k t Ì D(v): chi phí hi n hành t H T t c các node có cùng ngu n n node v thông tin Ì p(v): nút ngay trư c nút v Ì Tính toán các ư ng i có chi trên ư ng i t ngu n t i phí th p nh t t m t node ích n t t c các node khác Ì N: T p các nút mà ư ng i H T o forwarding table cho ng n nh t ã ư c xác nh node ó Ì L p : sau k l n l p, bi t ư ng i có chi phí th p nh t n k node ích 4-8 Gi i thu t nh tuy n
Gi i thu t Dijsktra 1 Initialization: 2 N = {u} 3 for all nodes v 4 if v adjacent to u 5 then D(v) = c(u,v) 6 else D(v) = ∞ 7 8 Loop 9 find w not in N such that D(w) is a minimum 10 add w to N 11 update D(v) for all v adjacent to w and not in N : 12 D(v) = min( D(v), D(w) + c(w,v) ) 13 /* new cost to v is either old cost to v or known 14 shortest path cost to w plus cost from w to v */ 15 until all nodes in N' 4-9 Gi i thu t nh tuy n
Ví d (1) D(v),p(v) D(w),p(w) D(x),p(x) D(y),p(y) Bư c N D(z),p(z) ∞ 2,u 1,u 5,u ∞ 0 u ∞ 2,u 4,x 2,x 1 ux 4,y 2,u 3,y 2 uxy 4,y 3,y 3 uxyv 4,y 4 uxyvw 5 uxyvwz 5 3 v w 5 2 u z 2 1 3 1 2 x y 1 nh tuy n 4-10 Gi i thu t
Ví d (2) K t qu có cây SPT (shortest-path tree) t u: v w u z x y Xây d ng forwarding table cho u: ích link (u,v) v (u,x) x y (u,x) (u,x) w z (u,x) 4-11 Gi i thu t nh tuy n
N I DUNG T ng quan Link state Distance Vector Hierarchical routing nh tuy n 4-12 Gi i thu t
Gi i thu t Distance Vector (1) Phương trình Bellman-Ford (qui ho ch ng) nh nghĩa: If dx(y) := chi phí nh nh t t x n y Then dx(y) = min {c(x,v) + dv(y) } v Trong ó min l y t t c các láng gi ng v c a x xét 4-13 Gi i thu t nh tuy n
Ví d Bellman-Ford 5 ã bi t, dv(z) = 5, dx(z) = 3, dw(z) = 3 3 v w 5 2 Theo phương trình B-F: u z 2 1 3 du(z) = min { c(u,v) + dv(z), 1 2 x y c(u,x) + dx(z), 1 c(u,w) + dw(z) } = min {2 + 5, 1 + 3, 5 + 3} = 4 Node t min là ch ng k ti p trên ư ng i ng n nh t, dùng l p b ng forwarding table nh tuy n 4-14 Gi i thu t
Gi i thu t Distance Vector (2) Ì Dx(y) = ư c lư ng chi phí nh nh t t x ny Ì Node x bi t chi phí n m i láng gi ng v c a nó: c(x,v) Ì Node x lưu gi m t distance vector: Dx = [Dx(y): y є N ] Ì Node x cũng lưu gi các distance vector c a các láng gi ng i v i m i láng gi ng v, x lưu gi : H Dv = [Dv(y): y є N ] nh tuy n 4-15 Gi i thu t
Gi i thu t Distance vector (3) Cơ s : Ì Theo th i gian, m i node g i ư c lư ng distance vector c a nó n các láng gi ng ÌBt ng b Ì Khi node x nh n m t ư c lư ng DV m i t láng gi ng, nó c p nh t DV c a nó b ng phương trình B-F: Dx(y) ← minv{c(x,v) + Dv(y)} cho m i node y ∊ N i u ki n t nhiên, ư c lư ng Dx(y) h i t Ì Dư i các d n v chi phí nh nh t th c s dx(y) nh tuy n 4-16 Gi i thu t
Gi i thu t Distance vector (4) L p, b t ng b : m i ho t M i node: ng l p c c b là do: Ì Thay i chi phí liên k t Ch (Thay i trong DV c a c cb nút bên c nh) Ì Thông i p c p nh t (DV update message) t láng gi ng Tính l i ư c lư ng DV Phân tán: Ì M i node ch thông báo cho láng gi ng khi thay i DV i, Báo cho N u DV thay c a nó nút bên c nh n lư t các láng gi ng H thông báo cho các láng gi ng c a chúng n u c n nh tuy n 4-17 Gi i thu t
Dx(z) = min{c(x,y) + Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} Dy(z), c(x,z) + Dz(z)} = min{2+0 , 7+1} = 2 = min{2+1 , 7+0} = 3 node x table cost to cost to xyz xyz x02 7 x 02 3 from from y ∞∞ ∞ y201 z ∞∞ ∞ z710 node y table cost to y xyz 2 1 x ∞∞∞ z x from y201 7 z ∞∞ ∞ node z table cost to xyz x ∞∞ ∞ from y ∞∞ ∞ z 71 0 time nh tuy n 4-18 Gi i thu t
Dx(z) = min{c(x,y) + Dx(y) = min{c(x,y) + Dy(y), c(x,z) + Dz(y)} Dy(z), c(x,z) + Dz(z)} = min{2+0 , 7+1} = 2 = min{2+1 , 7+0} = 3 node x table cost to cost to cost to xyz xyz xyz x02 7 x02 3 x02 3 from from from y ∞∞ ∞ y201 y201 z ∞∞ ∞ z710 z 31 0 node y table cost to cost to cost to y xyz xyz xyz 2 1 x ∞∞∞ x02 7 x02 3 z x from from from y201 y 20 1 7 y 20 1 z ∞∞ ∞ z710 z 31 0 node z table cost to cost to cost to xyz xyz xyz x02 7 x02 3 x ∞∞ ∞ from from from y 20 1 y 20 1 y ∞∞ ∞ z 31 0 z 31 0 z 71 0 time nh tuy n 4-19 Gi i thu t
Thay i chi phí liên k t Các thay i chi phí liên k t: Ì node phát hi n thay i chi phí liên 1 y k tn ib 4 1 Ì C p nh t thông tin nh tuy n, tính x z toán l i distance vector 50 Ì N u DV thay i, thông báo cho láng gi ng T i t0, y phát hi n thay i link-cost, c p nh t DV c a nó, và thông báo cho các láng gi ng c a nó. T i t1, z nh n c p nh t t y và c p nh t b ng c a nó. Nó tính l i chi phí nh nh t n x và g i DV m i cho các láng gi ng. T i t2, y nh n c p nh t t z và c p nh t b ng c a nó. Chi phí nh nh t c a y không thay i và do ó y không g i b t kỳ thông i p nào n z nh tuy n 4-20 Gi i thu t