Kỹ thuật truyền số liệu : Tìm đường trong mạng chuyển mạch part 3

• Distributed Adaptive Routing– Trong phương pháp này, thông tin về tình trạng hoạt động hiện hành của mạng sẽ được định kỳ trao đổi, cập nhật giữa các node trong toàn mạng. Sau đó thông tin này sẽ được phân bố về lại các node trong mạng hay một số node trong mạng làm nhiệm vụ tìm đường để các node này cập nhật lại bảng routing – Phương pháp này đáp ứng được với những thay đổi trạng thái của mạng, nhưng đồng thời cũng làm tăng lưu lượng thông tin trong mạng...
Nội dung trích xuất từ tài liệu:
Kỹ thuật truyền số liệu : Tìm đường trong mạng chuyển mạch part 3dce Isolated Adaptive Routing 2008 • Ví dụ • Đường ra được chọn là đường ra có Q+Bi nhỏ nhất Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 21dce Adaptive Routing 2008 • Distributed Adaptive Routing – Trong phương pháp này, thông tin về tình trạng hoạt động hiện hành của mạng sẽ được định kỳ trao đổi, cập nhật giữa các node trong toàn mạng. Sau đó thông tin này sẽ được phân bố về lại các node trong mạng hay một số node trong mạng làm nhiệm vụ tìm đường để các node này cập nhật lại bảng routing – Phương pháp này đáp ứng được với những thay đổi trạng thái của mạng, nhưng đồng thời cũng làm tăng lưu lượng thông tin trong mạng • Centralized Adaptive Routing – Trong phương pháp này, thông tin về tình trạng hoạt động hiện hành của mạng sẽ được định kỳ trao đổi, cập nhật giữa các node trong toàn mạng. Sau đó thông tin này sẽ được tập trung về một máy chủ trong mạng làm nhiệm vụ routing – Tuy đáp ứng được với những thay đổi tức thời trong mạng nhưng phương pháp này có nhược điểm là thông tin routing trong toàn mạng tập trung về một máy nên khi máy này không hoạt động thì toàn mạng sẽ không hoạt động được Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 22dce Giải thuật tìm đường ngắn nhất 2008 • Bài toán – Cho mạng các node được nối bởi các liên kết 2 chiều, mỗi chiều có giá trị chi phí riêng – Chi phí của đường đi giữa 2 node trong mạng là tổng các giá trị chi phí của các liên kết đi qua – Xác định đường đi ngắn nhất (chi phí thấp nhất) giữa 2 node • Tiêu chuẩn đường ngắn nhất – Số chặng đường đi • Giá trị mỗi liên kết là 1 – Giá trị liên kết • Tỉ lệ nghịch tốc độ liên kết • Tỉ lệ thuận tải trên liên kết • Tổ hợp các đại lượng trên • Giải thuật – Forward-search (Dijkstra) – Backward-search (Bellman-Ford) Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 23dce Giải thuật Dijkstra 2008 • Input – Đồ thị G(V, E) trong đó V là tập đỉnh, E là tập cạnh có trọng số không âm – Đỉnh nguồn S: S  V • Output – Đường đi ngắn nhất từ đỉnh nguồn S đến tất cả các đỉnh còn lại • Ký hiệu – Di : đường đi ngắn nhất từ node nguồn S đến node i tại bước chạy hiện hành của giải thuật – M: tập các đỉnh đã xét tại bước chạy hiện hành của giải thuật – dij: trọng số trên cạnh nối từ node i đến node j dij = 0 nếu i trùng j dij = Eij nếu i khác j Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 24dce Giải thuật Dijkstra 2008 • Giải thuật – Bước 1: khởi động • M = {S} • Di = dsi (các cạnh nối trực tiếp với S) – Bước 2: cập nhật đường đi ngắn nhất • Chọn đỉnh N  V sao cho: DN = min {Di} i  VM • M = M U {N} • Dj = min {Dj, DN + dNj} j  VM – Bước 3: lặp lại bước 2 cho đến khi M=V – Kết quả Di sẽ là đường đi ngắn nhất từ node nguồn S đến node i Data Communication and Computer Networks ©2008, Dr. Dinh Duc Anh Vu 25dce Giải thuật Dijkstra 2008 Laàn M Node 2 Node 3 Node 4 Node 5 Node 6 chaïy D2 Path D3 Path D4 Path D5 Path D6 Path   1 1 2 1–2 5 1–3 1 1–4 --- --- 2 1,4 2 1–2 4 1–4–3 1 1–4 2 1–4–5 ---  3 1,4,2 2 1–2 4 1–4–3 1 1–4 2 1–4–5 ---  4 1,4,2,5 2 1–2 3 1–4–5–3 1 1–4 2 1–4–5 4 1–4–5–6 5 1,4,2,5,3 2 1–2 3 1–4–5–3 1 1–4 2 1– ...