Cho mô hình mạng các node sử dụng thuật toán Bellman-Ford như sau:
.png)
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)
Hãy xác định distance vector ban đầu của node w, d w(u,v,x,w,y)?
Đáp án đúng: D
Tài liệu đề thi cuối kỳ môn Mạng Máy Tính của Đại học Công nghệ Thông tin, ĐHQG TP.HCM. Bao gồm các câu hỏi trắc nghiệm về kiến thức mạng máy tính, giao thức, định tuyến, địa chỉ IP và cấu hình mạng.
Câu hỏi liên quan
.png)
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.
.png)
Để giải bài toán này, chúng ta cần thực hiện phép chia đa thức trong trường GF(2) để tìm phần dư, sau đó nối phần dư này vào cuối thông điệp gốc để tạo thành thông điệp cần truyền đi. Thông điệp gốc (M) là 11001001. Đa thức sinh (G) là 1001. Độ dài của G là 4 bit, nên chúng ta sẽ thêm (4-1) = 3 bit 0 vào cuối thông điệp gốc để thực hiện phép chia. Thông điệp mới (M') = 11001001000. Bây giờ, chúng ta thực hiện phép chia đa thức M' cho G: 11001000 ---------------- 1001 | 11001001000 -1001 ------ 1011 -1001 ------ 0100 -0000 ----- 1001 -1001 ----- 0000 -0000 ----- 0000 -0000 ----- 000 Phép chia này hơi phức tạp để trình bày bằng văn bản thuần túy, nhưng về cơ bản, chúng ta thực hiện phép XOR từng bước. Cách làm chuẩn hơn là: 1. Lấy thông điệp gốc: 11001001 2. Thêm 3 số 0 vào cuối: 11001001000 3. Chia 11001001000 cho 1001 bằng phép XOR: 11001001000 (M') ^ 1001 (G, dịch sang trái 3 bit) ------------- 01010001000 ^ 1001 (G, dịch sang trái 2 bit) ------------- 01000001000 ^ 1001 (G, dịch sang trái 1 bit) ------------- 01000000000 ^ 1001 (G, dịch sang trái 0 bit) ------------- 010000001000 <-- Sai vì số bit G nhiều hơn phần dư. Chúng ta cần thực hiện phép chia như sau: 11001000 ------------ 1001 | 11001001000 -1001 ------ 1011 -1001 ------ 0100 -0000 ----- 1001 -1001 ----- 0000 -0000 ----- 000 -0000 ----- 000 Phần dư là 000. Thông điệp cần truyền đi là thông điệp gốc nối với phần dư. Thông điệp cần truyền đi = 11001001 + 000 = 11001001000. Do đó, phương án 3 là đáp án đúng.
1. Tính dung lượng của một trang tài liệu:
* Số dòng trên mỗi trang: 24 dòng
* Số ký tự trên mỗi dòng: 80 ký tự
* Tổng số ký tự trên một trang: 24 dòng * 80 ký tự/dòng = 1920 ký tự
* Kích thước mỗi ký tự: 8 bit
* Tổng dung lượng dữ liệu của một trang: 1920 ký tự * 8 bit/ký tự = 15360 bit
2. Tính tốc độ truyền dữ liệu cần thiết (băng thông):
* Số trang cần tải mỗi giây: 100 trang/giây
* Tổng dung lượng dữ liệu cần truyền mỗi giây: 15360 bit/trang * 100 trang/giây = 1,536,000 bit/giây
3. Chuyển đổi sang đơn vị Mbps:
* 1 Mbps = 1,000,000 bit/giây
* Băng thông tối thiểu cần thiết: 1,536,000 bit/giây / 1,000,000 bit/Mbps = 1.536 Mbps
Vậy, băng thông tối thiểu của kênh truyền là 1.536 Mbps.
.png)
.png)
