Cho mô hình mạng các node sử dụng thuật toán Bellman-Ford như sau: Giả sử, distance vector ban đầu của các node u, v và x được ký hiệu và có giá trị như sau: du (u,v,x,w,y) =(0,4,∞,∞,∞), dv(u,v,x,w,y) =(4,0,5,1,∞), dx(u,v,x,w,y) =(∞,4,0,6,2) Sau khi node w nhận được thông tin d v từ node v và d x từ node x (như phần giả định phía trên), và tính toán với thuật toán Bellman-Ford thì distance vector của node w, d w(u,v,x,w,y) sẽ có giá trị thế nào?

Đáp án đúng: B

Để tính toán distance vector của node w sau khi nhận thông tin từ v và x, chúng ta cần áp dụng công thức cập nhật của thuật toán Bellman-Ford. Ban đầu, distance vector của node w là dw(u,v,x,w,y) = (∞,∞,∞,0,∞). Node w nhận được thông tin từ node v với dv(u,v,x,w,y) = (4,0,5,1,∞) và từ node x với dx(u,v,x,w,y) = (∞,4,0,6,2). Theo thuật toán Bellman-Ford, distance vector của node w tại một bước lặp sẽ được cập nhật dựa trên khoảng cách đến các nút lân cận. Trong trường hợp này, node w có các nút lân cận là v (với chi phí cạnh w-v là 1) và x (với chi phí cạnh w-x là 6). Khoảng cách mới đến các nút khác từ w sẽ được tính như sau: * **Đến u:** w có thể đi đến v (chi phí 1), rồi từ v đến u (khoảng cách dv(u)=4). Tổng cộng: 1 + 4 = 5. Hoặc w có thể đi đến x (chi phí 6), rồi từ x đến u (khoảng cách dx(u)=∞). Tổng cộng: 6 + ∞ = ∞. Giá trị nhỏ hơn là 5. Tuy nhiên, trong mô hình này, ta chỉ xem xét thông tin nhận được trực tiếp từ v và x. Khoảng cách từ w đến u qua v: dw(w,v) + dv(u) = 1 + 4 = 5. Khoảng cách từ w đến u qua x: dw(w,x) + dx(u) = 6 + ∞ = ∞. Do đó, d_w(u) = min(∞, 5, ∞) = 5. Tuy nhiên, thông tin ban đầu cho thấy khoảng cách đến u là vô cùng. Ta chỉ cập nhật nếu có đường đi ngắn hơn. * **Đến v:** w có thể đi đến v trực tiếp (khoảng cách dv(v)=0). Khoảng cách từ w đến v qua v: dw(w,v) + dv(v) = 1 + 0 = 1. Giá trị nhỏ hơn là 1. Tuy nhiên, node w đang nhận thông tin về khoảng cách từ v, nên dv(v) = 0. Khoảng cách từ w đến v là 1 (trực tiếp). Distance vector ban đầu của v là dv(u,v,x,w,y) =(4,0,5,1,∞). Tuy nhiên, w đang tính distance vector của chính nó. w có cạnh đến v với chi phí 1. Khoảng cách từ w đến v qua v là 1 + dv(v) = 1 + 0 = 1. Cập nhật dw(v) = min(∞, 1) = 1. * **Đến x:** w có thể đi đến x trực tiếp (khoảng cách dx(x)=0). Khoảng cách từ w đến x qua x: dw(w,x) + dx(x) = 6 + 0 = 6. Giá trị nhỏ hơn là 6. Distance vector ban đầu của x là dx(u,v,x,w,y) =(∞,4,0,6,2). Khoảng cách từ w đến x là 6 (trực tiếp). Cập nhật dw(x) = min(∞, 6) = 6. * **Đến w:** Khoảng cách luôn là 0. dw(w) = 0. * **Đến y:** w có thể đi đến v (chi phí 1), rồi từ v đến y (khoảng cách dv(y)=∞). Tổng cộng: 1 + ∞ = ∞. Hoặc w có thể đi đến x (chi phí 6), rồi từ x đến y (khoảng cách dx(y)=2). Tổng cộng: 6 + 2 = 8. Giá trị nhỏ hơn là 8. Cập nhật dw(y) = min(∞, 8) = 8. Vậy, sau khi cập nhật, distance vector của node w sẽ là dw(u,v,x,w,y) = (5, 1, 6, 0, 8). Tuy nhiên, nhìn lại các đáp án, có vẻ như cách diễn giải thông tin Distance Vector có chút khác biệt. Giả sử dv và dx là khoảng cách từ v và x đến các nút (u,v,x,w,y). Khi node w tính toán Distance Vector của nó, nó sẽ cập nhật giá trị của mình cho mỗi nút đích 'd' bằng công thức: d_w(d) = min(d_w(d), cost(w, v) + d_v(d), cost(w, x) + d_x(d)). Với cost(w,v) = 1 và cost(w,x) = 6. * **Đến u:** d_w(u) = min(∞, cost(w,v) + d_v(u), cost(w,x) + d_x(u)) = min(∞, 1 + 4, 6 + ∞) = min(∞, 5, ∞) = 5. * **Đến v:** d_w(v) = min(∞, cost(w,v) + d_v(v), cost(w,x) + d_x(v)) = min(∞, 1 + 0, 6 + 4) = min(∞, 1, 10) = 1. * **Đến x:** d_w(x) = min(∞, cost(w,v) + d_v(x), cost(w,x) + d_x(x)) = min(∞, 1 + 5, 6 + 0) = min(∞, 6, 6) = 6. * **Đến w:** d_w(w) = min(0, cost(w,v) + d_v(w), cost(w,x) + d_x(w)) = min(0, 1 + 1, 6 + 6) = min(0, 2, 12) = 0. * **Đến y:** d_w(y) = min(∞, cost(w,v) + d_v(y), cost(w,x) + d_x(y)) = min(∞, 1 + ∞, 6 + 2) = min(∞, ∞, 8) = 8. Vậy, distance vector mới của w là (5, 1, 6, 0, 8). Đáp án này tương ứng với phương án 2.

Prefix		Output interface ID
131.15.0.0/12		3
131.28.0.0/14		5
131.19.0.0/16		2
131.22.0.0/15		1

Đề thi kết thúc môn học Mạng máy tính có đáp án chi tiết

Câu hỏi liên quan

Bộ Đồ Án Tốt Nghiệp Ngành Trí Tuệ Nhân Tạo Và Học Máy

Bộ 120+ Đồ Án Tốt Nghiệp Ngành Hệ Thống Thông Tin

Bộ Đồ Án Tốt Nghiệp Ngành Mạng Máy Tính Và Truyền Thông

Bộ Luận Văn Tốt Nghiệp Ngành Kiểm Toán

Bộ 370+ Luận Văn Tốt Nghiệp Ngành Kế Toán Doanh Nghiệp

Bộ Luận Văn Tốt Nghiệp Ngành Quản Trị Thương Hiệu

ĐĂNG KÝ GÓI THI VIP