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

0
156
lượt xem
37
download

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

Mô tả tài liệu
  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ủ đề:
Lưu

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

  1. Chương 8 GI I THU T NH TUY N (ROUTING ALGORITHM) 4-1 Gi i thu t nh tuy n
  2. N I DUNG T ng quan Link state Distance Vector Hierarchical routing 4-2 Gi i thu t nh tuy n
  3. 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
  4. 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
  5. 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
  6. 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
  7. N I DUNG T ng quan Link state Distance Vector Hierarchical routing 4-7 Gi i thu t nh tuy n
  8. 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
  9. 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
  10. 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
  11. 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
  12. N I DUNG T ng quan Link state Distance Vector Hierarchical routing nh tuy n 4-12 Gi i thu t
  13. 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
  14. 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
  15. 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
  16. 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
  17. 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
  18. 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
  19. 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
  20. 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

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản