Bài giảng Mạng máy tính: Chương 8

Chương 8

GIẢI THUẬT ĐỊNH TUYẾN (ROUTING ALGORITHM)

Giải thuật định tuyến

4-1

NỘI DUNG

(cid:1) Tổng quan (cid:1) Link state (cid:1) Distance Vector (cid:1) Hierarchical routing

Giải thuật định tuyến

4-2

Tổng quan: Phối hợp giữa routing và forwarding

routing algorithm

local forwarding table header value output link

3 2 2 1

0100 0101 0111 1001

Tham số trong header của gói đến

0111

Giải thuật định tuyến

4-3

Tổng quan: Đồ thị mạng

5 2

2 1 3 1 2

Graph: G = (N,E) 1

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

Giải thuật định tuyến

4-4

Ví dụ: P2P, với N là tâp các peer và E là tập các kết nối TCP

Tổng quan: Chi phí liên kết (cost)

5 • c(x,x’) = chi phí của liên kết (x,x’)

5 - ví dụ c(w,z) = 5 2

2 1 3 1 2

• chi phí được xác định tùy theo các yếu tố như băng thông, mức độ nghẽn... 1

Chi phí của đường đi (x1, x2, x3,…, xp) = c(x1,x2) + c(x2,x3) + … + c(xp-1,xp)

Giải thuật định tuyến sẽ xác định đường đi có chi phí nhỏ nhất

Giải thuật định tuyến

4-5

Câu hỏi: Đâu là đường đi có chi phí nhỏ nhất giữa u và z ?

Tổng quan: Phân loại giải thuật định tuyến

Thông tin toàn cục hay

phân tán?

Tĩnh hay động? Tĩnh: r Các tuyến được xác lập và thay đổi bởi người quản trị

Toàn cục: r Tất cả các router biết toàn bộ topo với thông tin về chi phí

Động: r Các tuyến thay đổi nhanh,

r Các giải thuật “link state” Phân tán: r router biết các láng giềng và

chi phí nối đến đó

r Quá trình tính toán lặp lại, trao đổi thông tin với các láng giềng

tự động m Cập nhật theo thời gian m Thích ứng với các thay đổi của chi phí trên liên kết

r Các giải thuật “distance

vector”

Giải thuật định tuyến

4-6

NỘI DUNG

(cid:1) Tổng quan (cid:1) Link state (cid:1) Distance Vector (cid:1) Hierarchical routing

Giải thuật định tuyến

4-7

Một giải thuật Link-State

Giải thuật Dijkstra r Các node biết tất cả topo

Ký hiệu: r c(x,y): chi phí từ node x đến y; = ∞ nếu không nối trực tiếp

mạng m Có được qua "quảng bá trạng thái liên kết

r D(v): chi phí hiện hành từ

m Tất cả các node có cùng

nguồn đến node v

thông tin

r p(v): nút ngay trước nút v trên đường đi từ nguồn tới đích

r Tính toán các đường đi có chi phí thấp nhất từ một node đến tất cả các node khác m Tạo forwarding table cho

r N: Tập các nút mà đường đi ngắn nhất đã được xác định

node đó

r Lặp : sau k lần lặp, biết đường đi có chi phí thấp nhất đến k node đích

Giải thuật định tuyến

4-8

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'

Giải thuật định tuyến

4-9

Ví dụ (1)

D(x),p(x) 1,u

D(y),p(y) ∞ 2,x

D(v),p(v) 2,u 2,u 2,u

D(w),p(w) 5,u 4,x 3,y 3,y

D(z),p(z) ∞ ∞ 4,y 4,y 4,y

Bước 0 1 2 3 4 5

N u ux uxy uxyv uxyvw uxyvwz

5 2

2 1 3 1 2

Giải thuật định tuyến 4-10

Ví dụ (2)

Kết quả có cây SPT (shortest-path tree) từ u:

Xây dựng forwarding table cho u:

đích link

(u,v) (u,x) v x

y (u,x)

(u,x) w

Giải thuật định tuyến 4-11

z (u,x)

NỘI DUNG

(cid:1) Tổng quan (cid:1) Link state (cid:1) Distance Vector (cid:1) Hierarchical routing

Giải thuật định tuyến 4-12

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) }

Trong đó min lấy tất cả các láng giềng v của x

để xét

Giải thuật định tuyến 4-13

Ví dụ Bellman-Ford

Đã biết, dv(z) = 5, dx(z) = 3, dw(z) = 3

Theo phương trình B-F:

5 2

2 1 3 1 2

du(z) = min { c(u,v) + dv(z), c(u,x) + dx(z), 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

Giải thuật định tuyến 4-14

Giải thuật Distance Vector (2)

r Dx(y) = ước lượng chi phí nhỏ nhất từ x đến y r Node x biết chi phí đến mỗi láng giềng v của

nó: c(x,v)

r Node x lưu giữ một distance vector:

Dx = [Dx(y): y є N ]

r Node x cũng lưu giữ các distance vector của

các láng giềng m Đối với mỗi láng giềng v, x lưu giữ:

Dv = [Dv(y): y є N ]

Giải thuật định tuyến 4-15

Giải thuật Distance vector (3)

Cơ sở: r Theo thời gian, mỗi node gửi ước lượng distance

vector của nó đến các láng giềng

r Bất đồng bộ r 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 nodey ∊ N

r Dưới các điều kiện tự nhiên, ước lượng Dx(y) hội tụ

dần về chi phínhỏ nhất thực sự dx(y)

Giải thuật định tuyến 4-16

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: r Thay đổi chi phí liên kết

cục bộ

Chờ (Thay đổi trong DV của nút bên cạnh)

Tính lại ước lượng DV

Nếu DV thay đổi, Báo cho nút bên cạnh

r Thông điệp cập nhật (DV update message) từ láng giềng Phân tán: r Mỗi node chỉ thông báo cho láng giềng khi thay đổi DV của nó m Đến lượt các láng giềng thông báo cho các láng giềng của chúng nếu cần

Giải thuật định tuyến 4-17

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 x y z cost to x y z

m o r f

0 0 2 7 32

x y z x y z 2 0 1 7 1 0 ∞ ∞ ∞ ∞ ∞ ∞

node y table

cost to x y z 2 1

∞ ∞

m o r f

x y z ∞ 2 0 1 ∞ ∞ ∞

node z table

cost to x y z

m o r f

∞ ∞ ∞

x y z ∞ ∞ ∞ 7 1 0

Giải thuật định tuyến 4-18

time

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 x y z cost to x y z cost to x y z

m o r f

0 2 7 0 2 3 0 2 3

x y z x y z 2 0 1 7 1 0 ∞ ∞ ∞ ∞ ∞ ∞ x y z 2 0 1 3 1 0 node y table

cost to x y z cost to x y z cost to x y z 2 1

∞ ∞ 0 2 7 0 2 3

m o r f

x y z x y z 2 0 1 7 1 0 2 0 1 3 1 0 ∞ 2 0 1 ∞ ∞ ∞ x y z

node z table

cost to x y z cost to x y z cost to x y z

0 2 7 ∞ ∞ ∞

m o r f

0 2 3 2 0 1

x y z x y z 2 0 1 3 1 0 3 1 0 x y z ∞ ∞ ∞ 7 1 0

Giải thuật định tuyến 4-19

time

Thay đổi chi phí liên kết

Các thay đổi chi phí liên kết: r node phát hiện thay đổi chi phí liên

kết nội bộ

r Cập nhật thông tin định tuyến, tính

toán lại distance vector

4 1

r Nếu DV thay đổi, thông báo cho láng

giềng

Tại t0, yphá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.

Giải thuật định tuyến 4-20

Tại t2, ynhậ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

NỘI DUNG

(cid:1) Tổng quan (cid:1) Link state (cid:1) Distance Vector (cid:1) Hierarchical routing

Giải thuật định tuyến 4-21

Hierarchical Routing

Nhu cầu tự quản: r internet = mạng của

các mạng

r Mỗi quản trị mạng

Qui mô: với hàng trăm triệu đích: r Không thể lưu tất cả các đích trong bảng định tuyến!

muốn kiểm soát định tuyến bên trong mạng của họ

r Việc trao đổi bảng định tuyến sẽ làm tràn ngập các liên kết!

Định tuyến phân cấp

Giải thuật định tuyến 4-22

Hierarchical Routing

r Tập hợp các router vào các vùng, “autonomous systems” (AS)

Gateway router r Kết nối trực tiếp đến router trong AS khác

r Các router trong cùng

AS m “intra-AS” routing

protocol: giao thức định tuyến nội vùng

m Các router trong AS khác nhau chạy các intra-AS routing protocol khác nhau

Giải thuật định tuyến 4-23

Liên kết giữa các AS

3a AS3

AS1

Intra-AS Routing algorithm

Inter-AS Routing algorithm

Forwarding table

r forwarding table được xây dựng nhờ vào giao thức định tuyến nội vùng và liên vùng (intra-AS và inter-AS routing protocol) m intra-AS cài đặt các mục cho các đích nội vùng m inter-AS & intra-As cài

AS2

Giải thuật định tuyến 4-24

đặt các mục cho các đích nằm bên ngoài

Các tác vụ liên AS r Giả sử router trong

AS1 nhận datagram có đích nằm ngoài AS1: m router nên chuyển gói đến gateway router, nhưng đến gateway nào?

AS1 phải: 1. Học để biết các đích nào có thể đến được thông qua AS2, đích nào có thể đến được thông qua AS3 2. Phát tán thông tin về khả năng đến được này đến tất cả các router trong AS1

Đây là một nhiệm vụ của giao thức định tuyến inter-AS

3a AS3

AS1

Giải thuật định tuyến 4-25

AS2

Ví dụ: thiết lập forwarding table trong router 1d

r Giả sử AS1 học và biết được (thông qua giao thức inter-AS) subnet xcó thể đến được thông qua AS3 (gateway 1c), không thể thông qua AS2.

r Giao thức inter-AS phát tán thông tin này đến tất cả các router bên

trong.

r Từ giao thức intra-AS mà router 1d xác định được giao tiếp I của nó

là tiếp tục con đường có chi phí nhỏ nhất đến 1c. m Ghi vào forwarding table một mục (x,I)