Thuật toán Distance Vector là lặp đi lặp lại, không đồng bộ và phân tán.
Phân tán: Nó được phân phối trong đó mỗi nút nhận thông tin từ một hoặc nhiều nút lân cận trực tiếp của nó, thực hiện tính toán và sau đó phân phối kết quả trở lại các nút lân cận của nó.
Lặp lại: Nó lặp đi lặp lại trong đó quá trình của nó tiếp tục cho đến khi không còn thông tin nào có sẵn để trao đổi giữa các nước láng giềng.
Không đồng bộ: Nó không yêu cầu tất cả các nút của nó hoạt động ở bước khóa với nhau.
Thuật toán Distance Vector là một thuật toán động.
Nó chủ yếu được sử dụng trong ARPANET và RIP.
Mỗi bộ định tuyến duy trì một bảng khoảng cách được gọi là Vector.
Các bài viết liên quan:
- Sử dụng tính toán Vector trong R
- 50 + câu hỏi trắc nghiệm về testing software
- Phân tích Nonlinear Regression trong R
- Network Layer trong TCP/IP hay OSI
- Computer Network là gì? kiến thức cơ bản
Cách hoạt động thuật toán Định tuyến Distance Vector:
- Kiến thức về toàn bộ mạng: Mỗi bộ định tuyến chia sẻ kiến thức của mình thông qua toàn bộ mạng. Bộ định tuyến gửi kiến thức thu thập được của nó về mạng cho các nước láng giềng.
- Chỉ định tuyến cho hàng xóm: Bộ định tuyến chỉ gửi kiến thức về mạng cho những bộ định tuyến có liên kết trực tiếp. Bộ định tuyến gửi bất cứ thứ gì nó có về mạng thông qua các cổng. Thông tin được nhận bởi bộ định tuyến và sử dụng thông tin đó để cập nhật routing của chính nó.
- Chia sẻ thông tin đều đặn: Trong vòng 30 giây, bộ định tuyến sẽ gửi thông tin đến các bộ định tuyến lân cận.
Thuật toán định tuyến Distance Vector
Gọi d x (y) là chi phí của con đường tốn ít chi phí nhất từ nút x đến nút y. Chi phí ít nhất liên quan đến phương trình Bellman-Ford,
d x (y) = min v {c (x, v) + d v (y)}
Trong đó minv là phương trình được lấy cho tất cả x lân cận. Sau khi đi từ x đến v, nếu chúng ta coi con đường có chi phí thấp nhất từ v đến y, chi phí đường đi sẽ là c (x, v) + d v (y). Chi phí nhỏ nhất từ x đến y là chi phí tối thiểu của c (x, v) + d v (y) được tính trên tất cả các lân cận.
Với thuật toán Định tuyến theo Distance Vector, nút x chứa thông tin định tuyến sau:
- Đối với mỗi láng giềng v, chi phí c (x, v) là chi phí đường đi từ x đến láng giềng gắn trực tiếp, v.
- Distance Vector x, tức là, D x = [D x (y): y tính bằng N], chứa chi phí của nó tới tất cả các điểm đến, y, tính bằng N.
- Distance Vector của mỗi lân cận của nó, tức là, D v = [D v (y): y in N] đối với mỗi lân cận v của x.
Định tuyến Distance Vector là một thuật toán không đồng bộ, trong đó nút x gửi bản sao của Distance Vector đến tất cả các nút lân cận. Khi nút x nhận được Distance Vector mới từ một trong các vectơ lân cận của nó, v, nó sẽ lưu Distance Vector của v và sử dụng phương trình Bellman-Ford để cập nhật Distance Vector của chính nó. Phương trình được đưa ra dưới đây:
d x (y) = min v {c (x, v) + d v (y)} cho mỗi nút y trong N
Nút x đã cập nhật bảng Distance Vector của chính nó bằng cách sử dụng phương trình trên và gửi bảng đã cập nhật của nó tới tất cả các nút lân cận để họ có thể cập nhật các Distance Vector của riêng mình.
Xem thêm Routing là gì? Các loại Routing
Thuật toán mã giả
Tại mỗi nút x,
Lưu ý: Trong thuật toán Distance Vector, nút x cập nhật bảng của nó khi nó thấy bất kỳ thay đổi chi phí nào trong một nút được liên kết trực tiếp hoặc nhận được bất kỳ cập nhật vectơ nào từ một số hàng xóm.
Xem thêm Các nền tảng thiết kế website bán hàng miễn phí
Hãy hiểu qua một ví dụ:
Chia sẻ thông tin
- Trong hình trên, mỗi đám mây đại diện cho mạng và số bên trong đám mây đại diện cho ID mạng.
- Tất cả các mạng LAN được kết nối bằng bộ định tuyến và chúng được biểu diễn trong các hộp có nhãn là A, B, C, D, E, F.
- Thuật toán định tuyến theo Distance Vector đơn giản hóa quá trình định tuyến bằng cách giả định chi phí của mọi liên kết là một đơn vị. Do đó, hiệu quả của quá trình truyền tải có thể được đo lường bằng số lượng liên kết để đến đích.
- Trong Định tuyến Distance Vector, chi phí dựa trên số bước nhảy.
Trong hình trên, chúng ta quan sát thấy rằng bộ định tuyến gửi kiến thức đến những người hàng xóm trực tiếp. Những người hàng xóm bổ sung kiến thức này vào kiến thức của riêng họ và gửi bảng cập nhật cho những người hàng xóm của họ. Bằng cách này, các bộ định tuyến nhận được thông tin của riêng nó cộng với thông tin mới về các nước láng giềng.
Xem thêm Cách đưa ra ý tưởng nội dung tiếp tuyến
Routing
Hai quá trình xảy ra:
- Tạo bảng
- Cập nhật bảng
Tạo bảng
Ban đầu, routing được tạo cho mỗi bộ định tuyến chứa ít nhất ba loại thông tin như ID mạng, chi phí và bước tiếp theo.
- NET ID: ID Mạng xác định đích cuối cùng của gói tin.
- Chi phí: Chi phí là số bước nhảy mà gói tin phải thực hiện để đến đó.
- Bước tiếp theo: Đây là bộ định tuyến mà gói tin phải được chuyển đến.
- Trong hình trên, routing ban đầu được hiển thị cho tất cả các bộ định tuyến. Trong routing, cột đầu tiên đại diện cho ID mạng, cột thứ hai đại diện cho chi phí của liên kết và cột thứ ba để trống.
- Các routing này được gửi đến tất cả các hàng xóm.
Ví dụ:
- A gửi routing của nó tới B, F & E.
- B gửi routing của nó tới A & C.
- C gửi routing của nó tới B & D.
- D gửi routing của nó tới E & C.
- E gửi routing của nó cho A & D.
- F gửi routing của nó tới A.
Cập nhật bảng
- Khi A nhận được một routing từ B, thì nó sẽ sử dụng thông tin của nó để cập nhật bảng.
- routing của B cho thấy cách các gói có thể di chuyển đến mạng 1 và 4.
- B là hàng xóm của bộ định tuyến A, các gói từ A đến B có thể truy cập trong một bước. Vì vậy, 1 được thêm vào tất cả các chi phí cho trong bảng B và tổng sẽ là chi phí để tiếp cận một mạng cụ thể.
- Sau khi điều chỉnh, A sau đó kết hợp bảng này với bảng của chính nó để tạo ra một bảng kết hợp.
- Bảng kết hợp có thể chứa một số dữ liệu trùng lặp. Trong hình trên, bảng kết hợp của bộ định tuyến A chứa dữ liệu trùng lặp, vì vậy nó chỉ giữ lại những dữ liệu có chi phí thấp nhất. Ví dụ, A có thể gửi dữ liệu đến mạng 1 theo hai cách. Đầu tiên, không sử dụng bộ định tuyến tiếp theo, vì vậy nó tốn một bước. Bước thứ hai yêu cầu hai bước nhảy (A đến B, sau đó B đến Mạng 1). Lựa chọn đầu tiên có chi phí thấp nhất, do đó nó được giữ lại và lựa chọn thứ hai bị loại bỏ.
- Quá trình tạo routing tiếp tục cho tất cả các bộ định tuyến. Mỗi bộ định tuyến nhận thông tin từ các hàng xóm và cập nhật routing.
routing cuối cùng của tất cả các bộ định tuyến được đưa ra dưới đây:
Xem thêm Cách sử dụng các thư mục có liên quan, được nhắm mục tiêu để xây dựng liên kết
