BÁO CÁO môn học môn học CÔNG NGHỆ TRUYỀN tải QUANG đề tài ĐỊNH TUYẾN và gán bước SÓNG TRONG WDM

Giới thiệu chung

Các công nghệ truyền tải như SDH/SONET và ATM đang gặp khó khăn trong việc đáp ứng nhu cầu băng thông cao cho các dịch vụ như HDTV, hội nghị truyền hình và ứng dụng đa phương tiện Việc sử dụng cáp quang giúp khai thác tiềm năng lớn của truyền dẫn quang học, với tốc độ vượt trội so với các công nghệ điện tử truyền thống Để tối ưu hóa băng thông cáp quang, công nghệ ghép kênh phân chia theo bước sóng (WDM) đã được phát triển, cho phép chia phổ truyền dẫn thành nhiều kênh hoạt động đồng thời ở các bước sóng khác nhau Nhờ đó, mỗi kênh có thể cung cấp băng thông tương thích với tốc độ xử lý hiện tại và điều chế độc lập, giúp đạt được dung lượng liên kết lên đến Tbps trong mạng quang.

Giới thiệu định tuyến và gán bước sóng

Mạng WDM (Wavelength Division Multiplexing) đã nhanh chóng trở thành một lớp mạng mạnh mẽ cho các mạng diện rộng, sử dụng thiết bị chuyển mạch quang để định tuyến tín hiệu dựa trên nhận dạng cổng đầu vào và bước sóng tín hiệu Được gọi là mạng định tuyến theo bước sóng, WDM áp dụng kỹ thuật định tuyến này để tối ưu hóa hiệu suất truyền tải Các công tắc truy cập và công tắc đầu cuối đóng vai trò quan trọng trong việc chuyển đổi giữa tín hiệu điện tử và quang, giúp kết nối mạng quang với các trạm điện tử một cách hiệu quả.

SV thực hiện: Đoàn Quang Vinh Trương Văn Trường

Mai Phương Trâm Nguyễn Hiếu Hoài sóng cung cấp khả năng xác định và khoanh vùng luồng lưu lượng trong mạng, cho phép sử dụng lại bước sóng trong các phân đoạn không gian khác nhau Để truyền dữ liệu giữa các nút truy cập, cần thiết lập kết nối ở lớp quang, tương tự như chuyển mạch kênh trong mạng lưới Hoạt động này bao gồm việc xác định đường dẫn từ nút nguồn đến nút đích và phân bổ một bước sóng duy nhất trên các liên kết sợi trong đường dẫn Đường dẫn quang này, gọi là đường dẫn ánh sáng, có thể truyền dữ liệu với tốc độ cao nhất Tuy nhiên, công nghệ truyền dẫn và thiết bị quang học giới hạn số bước sóng khả dụng, làm cho việc thiết lập đường dẫn ánh sáng giữa mọi cặp nút không phải lúc nào cũng khả thi Các nút trung gian sử dụng công tắc nhạy cảm với bước sóng để định tuyến đường dẫn ánh sáng Một hạn chế chính của mạng quang định tuyến theo bước sóng là các đường ánh sáng phải nằm trên các bước sóng khác nhau để tránh giao thoa Mạng định tuyến theo bước sóng toàn quang, không có chuyển đổi quang-điện, mang lại nhiều lợi ích như khả năng đáp ứng băng thông cao, độ tin cậy tốt hơn, quản lý đơn giản và không phụ thuộc vào định dạng điều chế Trong mạng này, người sử dụng giao tiếp qua các kênh thông tin quang gọi là lightpath, là đường đi của tín hiệu ánh sáng từ nguồn đến đích Khi một lightpath được xác định, cần thực hiện việc định tuyến và gán bước sóng cho nó, tạo ra bài toán định tuyến và gán bước sóng.

Mai Phương Trâm Nguyễn Hiếu Hoài nghiên cứu việc tìm đường giữa hai node trong mạng để tối ưu hàm mục tiêu (cost function) Định tuyến trong IP thường sử dụng thuật toán Dijkstra với các metric như băng thông, độ trễ và chi phí tuyến Trong mạng quang, việc tìm đường được chia thành hai khía cạnh: tìm đường vật lý để mang lưu lượng (Routing) và xác định bước sóng phù hợp cho lưu lượng trên mỗi link (Wavelength Assignment), gọi tắt là RWA Khi xác định được một path vật lý và gán bước sóng cho các link, ta có một đường quang (lightpath - LP) Bài toán RWA đặt ra điều kiện quan trọng: một lightpath phải sử dụng chung một bước sóng trên tất cả các link từ nguồn đến đích.

Các đường dẫn ánh sáng là thành phần chuyển mạch quan trọng trong mạng WDM, vì chúng định tuyến theo bước sóng Việc thiết lập và sử dụng hiệu quả các đường dẫn này là cần thiết, do đó, cần có các thuật toán hiệu quả để lựa chọn tuyến cho các kết nối yêu cầu và phân bổ bước sóng cho từng liên kết trên các tuyến đó.

Sự thiết lập đường ảo (Virtual path)

Một đường ảo được định nghĩa là hành trình của ánh sáng từ nguồn đến đích Khi có yêu cầu cuộc gọi, nút sẽ sử dụng thuật toán định tuyến để xác định đường đi và gán bước sóng cho cuộc gọi Nút sẽ chỉ định bước sóng đã chọn cho cuộc gọi và chuyển tiếp nó đến nút kế tiếp Tại mỗi nút trung gian, bước sóng của lightpath sẽ được kiểm tra xem có sẵn để gán hay không, quyết định việc tiếp tục hành trình.

Mai Phương Trâm Nguyễn Hiếu Hoài sẵn, với khả năng sử dụng bộ chuyển đổi bước sóng, có thể định tuyến lightpath bằng cách chuyển sang bước sóng khác Đường đi này, được gọi là đường ảo, được thiết lập trước khi dữ liệu được truyền Trong khi đường vật lý bao gồm tất cả các liên kết từ nguồn đến đích, đường ảo có thể sử dụng các bước sóng giống hoặc khác nhau Hai cuộc gọi có cùng điểm đầu cuối có thể chia sẻ đường vật lý nhưng lại có đường ảo khác nhau Hình minh họa cho thấy sự hình thành của một lightpath, trong đó hai cuộc gọi từ nút 1 được thể hiện với các bước sóng khác nhau Cuộc gọi đầu tiên sử dụng bước sóng 1 từ nút 1 đến nút 2, nơi bước sóng 1 không khả dụng, nên nó chuyển sang bước sóng 2 để tiếp tục đến nút 3.

Đường ảo đầu tiên được thiết lập khi có sẵn và định tuyến lightpath đến đích Nếu một cuộc gọi thứ hai được thực hiện từ nút 1 ngay sau đó, một đường ảo thứ hai sẽ được tạo ra Mặc dù đường vật lý là giống nhau, nhưng các đường ảo lại khác nhau Số lượng đường ảo được thiết lập từ nguồn đến đích phụ thuộc vào số bước sóng có trên sợi cáp, và số đường ảo thực sự được thiết lập lại phụ thuộc vào tốc độ cuộc gọi Việc sử dụng các bộ chuyển đổi bước sóng cho phép thiết lập nhiều đường ảo hơn.

Định tuyến (Routing)

Phân loại định tuyến

Mạng viễn thông truyền thống thường sử dụng mô hình phân cấp, cho phép áp dụng định tuyến tĩnh trên quy mô lớn Định tuyến tĩnh được thực hiện thông qua việc người quản trị thủ công khai báo thông tin định tuyến cho các thiết bị Mô hình này có ưu điểm là dễ quản lý nhưng cũng tồn tại nhược điểm là thiếu tính linh hoạt và khó khăn trong việc điều chỉnh khi có thay đổi.

+Sử dụng ít băng thông

+Không tiêu tốn tài nguyên để tính toán và phân tích gói tin

+Dễ triển khai, cấu hình

+Không có khả năng tự động cập nhật

+Cấu hình thủ công khi mạng thay đổi

+Khả năng mở rộng kém, phù hợp với mô hình nhỏ Ưu và nhược điểm của Định tuyến tĩnh [13]

Sử dụng định tuyến tĩnh khi:

+ Đường truyền có băng thông thấp + Người quản trị cần kiểm soát kết nối hệ thống + Hệ thống có ít tuyến kết nối

+ Dùng làm đường dự phòng khi đường kết nối dùng giao thức định tuyến động.

Phương thức triển khai: có 2 phương thức:

+Next hop: thông tin sẽ chuyển đén Router kế tiếp nào trước khi đến đích.

+Exit interface: thông tin sẽ được đưa ra cổng nào trước khi đến đích.

Trong các hệ thống mạng nhỏ, bảng định tuyến có thể được cấu hình thủ công, nhưng với các mạng lớn và phức tạp, việc này trở nên khó khăn Để ngăn ngừa lỗi và nghẽn mạng, việc xây dựng bảng định tuyến tự động thông qua thông tin từ giao thức định tuyến được gọi là định tuyến động Phương pháp này có những ưu điểm và nhược điểm riêng.

+Tự động cập nhật thông tin bảng định tuyến nếu có sự thay đổi

+Tự tính toán và đưa ra tuyến đường tốt nhất

+Đơn giản trong việc cấu hình

Định tuyến động tiêu tốn băng thông và yêu cầu xử lý hệ thống cao hơn so với định tuyến tĩnh Định tuyến động có những ưu và nhược điểm riêng, và được chia thành hai loại khác nhau.

+Các giao thức định tuyến ngoài: EGP (Exterior Gateway Protocol)

Giao thức BGP (Border Gateway Protocol) là tiêu chuẩn chính được sử dụng để trao đổi thông tin định tuyến giữa các router thuộc các Hệ thống Tự trị (AS) khác nhau, giúp đảm bảo sự kết nối và truyền tải dữ liệu hiệu quả trong mạng lưới.

+Các giao thức định tuyến trong: IGP (Interior Gateway Protocol): là loại định tuyến chạy giữa các router nằm bên trong một AS.

 Gồm các giao thức tieu biểu như: RIP, OSPF là giao thức chuẩn quốc tế và EIGRP là giao thức chỉ chạy trên Cisco.

*RIP (Routing Information Protocol): giao thức định tuyến vector khoảng cách

*OSPF (Open Shortest Path First): giao thức định tuyến link-state

*EIGRP (Enhanced Interior Gateway Routing Protocol) [12]

Mai Phương Trâm Nguyễn Hiếu Hoài

Đồ thị là một cấu trúc toán học bao gồm các đỉnh và các cạnh, thể hiện mối quan hệ giữa các đối tượng được kết nối với nhau.

Với V là tập hợp các đỉnh

Đồ thị được định nghĩa là một tập hợp các cạnh, và để phân loại các loại đồ thị khác nhau, chúng ta dựa vào kiểu đồ thị cũng như số lượng cạnh nối giữa hai đỉnh bất kỳ trong đồ thị.

1 Đồ thị vô hướng: là đồ thị không có hướng trong các cạnh liên kết các đỉnh trong đồ thị.[14] a Đơn đồ thị vô hướng: là đồ thị trong đó một cạnh tương ứng với một cặp đỉnh G=(V,E)[14]

Với V là tập các đỉnh, E là tập các cạnh của các cặp không có thứ tự

Vì là vô hướng nên E cũng có thể viết là:

E= {(V2,V1), (V3,V2), (V1,V3)} b Đa đồ thị vô hướng: là đồ thị trong đó có thể có hai (hoặc nhiều) cạnh nối với một cặp đỉnh nào đó G=(V,E)[14]

Với V là tập các đỉnh và E là tập các cạnh của các cặp không có thứ tự

Trong Hình 1b, hai cạnh e1 và e2 được gọi là cạnh lặp hay cạnh song song Đồ thị vô hướng là loại đồ thị có khả năng chứa các khuyên và các cạnh lặp Khi một cạnh kết nối một đỉnh với chính nó, đồ thị đó được xem là có chứa khuyên.

Với V là tập hợp các đỉnh, E là tập hợp các cạnh của các cặp đỉnh không có thứ tự và không nhất thiết phải khác nhau.

Trong Hình 1c, ta có: V = {V1, V2, V3} và E {(V1,V2), (V2,V3), (V3, V1), (V1,V1)} hoặc E = {(V2,V1), (V3,V2), (V1,V3), (V1,V1)}

V1 ϵ V và (V1,V1) ϵ E thì ta nói có một khuyên tại đỉnh V1.

1 Đồ thị có hướng: Là đồ thị trong đó các cạnh liên kết các đỉnh có hướng.

[15] a) Đơn đồ thị có hướng: là đồ thị trong đó một cạnh có hướng tương ứng với một cặp đỉnh: G=(V,E)

Với V là tập các đỉnh, E là tập các cạnh của các cặp đỉnh theo thứ tự.

Và E= {(V2,V1), (V1,V3), (V2, V3)} b) Đa đồ thị có hướng: là đồ thị trong đó có hai hoặc nhiều cạnh có hướng nối với một cặp đỉnh: G= (V,E) [15]

Với V là tập các đỉnh, E là tập các cạnh của các cặp đỉnh theo thứ tự.

Trong Hình 2b, hai cung e1 và e2 tương ứng với cùng một cặp đỉnh được gọi là cung lặp.

Bài toán định tuyến gán bước sóng liên quan mật thiết đến bài toán tô màu các nút trong đồ thị Cụ thể, việc tô màu các nút G cần đảm bảo rằng hai nút kề nhau phải có màu sắc khác nhau, điều này thể hiện trạng thái của từng nút.

Các thuật toán thường gặp trong định tuyến

Thuật toán định tuyến trạng thái liên kết LSA

Tóm tắt định tuyến trạng thái liên kết: Các giao thức định tuyến thuộc loại này như OSPF, IS-IS Link State không gửi bảng định tuyến của mình ,

Trong giao thức Link State, các router chỉ gửi tình trạng của các đường link trong cơ sở dữ liệu trạng thái liên kết (link-state database) cho các router khác Các router sẽ áp dụng thuật toán SPF (shortest path first) để tự xây dựng bảng định tuyến (routing table) riêng cho mình Khi mạng đã hội tụ, giao thức Link State sẽ không gửi cập nhật định kỳ, mà chỉ gửi thông tin khi có sự thay đổi trong mạng, chẳng hạn như khi một đường truyền bị gián đoạn hoặc cần sử dụng đường dự phòng.

Hệ thống có khả năng thích nghi với đa số các cấu hình, cho phép các nhà thiết kế tạo ra mạng linh hoạt và phản ứng nhanh với các tình huống phát sinh Việc không gửi interval-update giúp công nghệ link state đảm bảo băng thông cho các đường mạng.

 Do router phải sử lý nhiều , nên chiếm nhiều bộ nhớ , tốc độ CPU chậm hơn nên tăng delay[8].

 Link State khá khó cấu hình để chạy tốt [8]

Thuật toán Dijkstra, được phát triển bởi nhà khoa học máy tính Hà Lan Edsger Dijkstra vào năm 1956 và công bố năm 1959, là một phương pháp hiệu quả để tìm đường đi ngắn nhất giữa hai đỉnh trong đồ thị.

Thuật toán Dijkstra cho phép các node trong mạng thông tin xác định giá trị liên kết với các node xung quanh Sau khi thu thập thông tin giá trị, tất cả các node sẽ hiểu rõ cấu trúc mạng Thuật toán này được sử dụng để tính toán con đường ngắn nhất đến node đích.

Cho đồ thị có hướng với N đỉnh (đánh số từ 0 đến N−1) và M cạnh có trọng số không âm, bài toán yêu cầu tìm đường đi ngắn nhất từ đỉnh nguồn S đến tất cả các đỉnh khác, hoặc xác định nếu không tồn tại đường đi.

Thuật toán Dijkstra cũng tối ưu hóa đường đi bằng cách xét các cạnh (u,v), so sánh hai đường đi S→v sẵn có với đường đi S→u→v.

Thuật toán hoạt động bằng cách duy trì một tập hợp các đỉnh mà chúng ta đã xác định được đường đi ngắn nhất Ở mỗi bước, thuật toán sẽ chọn một đỉnh u mà không thể tối ưu hơn nữa, sau đó sẽ tối ưu hóa các đỉnh v khác dựa trên các cạnh (u,v) xuất phát từ đỉnh u.

N bước, tất cả các đỉnh đều sẽ được chọn, và mọi đường đi tìm được sẽ là ngắn nhất [5].

Thuật toán duy trì đường đi ngắn nhất đến tất cả các đỉnh bằng cách chọn đường đi S→u có tổng trọng số nhỏ nhất ở mỗi bước Sau đó, nó tối ưu hóa các đường đi S→v bằng cách kéo dài thành S→u→v như đã được mô tả trong tài liệu.

Cách thức hoạt động của thuật toán như sau:

Thuật toán Dijkstra xác định đường đi ngắn nhất từ đỉnh A đến đỉnh D, với nguyên tắc rằng bất kỳ đoạn đường con nào từ B đến D trong lộ trình này cũng sẽ là đường đi ngắn nhất giữa B và D.

Dijkstra đã áp dụng thuộc tính này theo cách ngược lại, tức là chúng ta ước lượng khoảng cách từ đỉnh đầu tiên đến từng đỉnh khác Sau đó, chúng ta sẽ truy cập từng nút và các nút lân cận của nó.

Mai Phương Trâm Nguyễn Hiếu Hoài cận của nó để tìm đường đi con ngắn nhất đến các nút lân cận đó [5].

Thuật toán áp dụng phương pháp tham lam, trong đó chúng ta lựa chọn giải pháp tốt nhất tại mỗi bước, với hy vọng rằng điều này sẽ dẫn đến kết quả tối ưu cho toàn bộ vấn đề.

5.1.5 Ví dụ về thuật toán Dijkstra.

Bài toán yêu cầu tìm đường đi ngắn nhất từ node A đến các node B, C, D, E, F trong một đồ thị trọng số, với các khoảng cách giữa các nodes được thể hiện qua các cạnh.

Hình 5.2 Ví dụ về thuật toán Dijkstra.

Sau khi giải bài toán, ta được kết quả như sau Đường đi ngắn nhất từ

Từ A -> B : A - B, tổng độ dài đường đi = 2

Từ A -> C : A-D- C, tổng độ dài đường đi = 4

Từ A -> D : A - D, tổng độ dài đường đi = 1

Từ A -> E : A - D - E, tổng độ dài đường đi = 2

Từ A -> F : A - D - E - F, tổng độ dài đường đi = 4

Thuật toán định tuyến vectơ khoảng cách DV

Định tuyến vector khoảng cách, bao gồm các giao thức như RIP và IGRP, hoạt động theo nguyên tắc Neighbor, trong đó mỗi router sẽ gửi bảng định tuyến của mình đến tất cả các router kết nối trực tiếp Các router nhận được sẽ so sánh bảng định tuyến của mình với thông tin mới và kiểm tra lại các tuyến đường, từ đó lựa chọn tuyến đường tối ưu hơn để cập nhật vào bảng định tuyến của mình.

 Dễ cấu hình , router không phải xử lý nhiều nên không tốn nhiều dung lượng bộ nhớ và CPU có tốc độ xử lý nhanh hơn [8].

 Hệ thống metric quá đơn giản (như rip chỉ là hop-count ) dẫn đến việc các tuyến đường được chọn vào routing-table chưa phải tuyến đường tốt nhất [8]

 Vì các gói tin update được gửi theo định kỳ nên một lượng bandwidth đáng kể sẻ bị chiếm (mặc dù mạng không gì thay đổi nhiều)

 Do Router hội tụ chậm , dẫn đến việc sai lệch trong bảng địn tuyến gây nên hiện tượng loop [8].

Thuật toán Bellman-Ford là phương pháp tính toán đường đi ngắn nhất từ một nguồn trong đồ thị có hướng và trọng số, cho phép các trọng số âm Mặc dù thuật toán Dijkstra có thời gian chạy nhanh hơn, nó chỉ áp dụng cho đồ thị có trọng số không âm Vì lý do này, Bellman-Ford thường được sử dụng trong trường hợp có cung trọng số âm.

Tương tự như bài toán của Dijkstra, bài toán mà thuật toán Bellman-Ford phải giải quyết là tương tự.

Trong trường hợp đơn giản khi đồ thị không có trọng số âm, thuật toán Bellman-Ford sẽ lặp lại nhiều lần Mỗi vòng lặp, thuật toán sẽ kiểm tra tất cả các cạnh (u,v) trên đồ thị để so sánh đường đi từ S đến v với đường đi từ S đến u và sau đó đến v.

Ví dụ đồ thị sau:

Nếu chúng ta có đường đi từ 1 đến 3 với độ dài 4 và đường đi từ 1 đến 2 với độ dài 2, ta có thể sử dụng cạnh (2,3) để mở rộng đường đi 1→2 thành 1→2→3 với tổng độ dài chỉ 3, điều này cho thấy rằng đường đi gián tiếp này hiệu quả hơn so với đường đi trực tiếp từ 1 đến 3.

Có thể chứng minh được rằng, vòng lặp trên cần thực hiện N−1 lần, mỗi lần đi qua toàn bộ M cạnh, là sẽ đủ để tìm đường đi ngắn nhất.

Một đường đi ngắn nhất sẽ không có đỉnh nào được đi lại quá một lần, do đó số cạnh tối đa trong hành trình này chỉ là N−1 Việc tính toán Dv=Du+Wu,v cho thấy rằng thêm một cạnh u→v vào hành trình từ s đến v chỉ có thể tối ưu hóa giá trị Du tối đa N−1 lần Từ lần tối ưu hóa thứ N trở đi, không thể đạt được giá trị tối ưu hơn nữa.

Thuật toán gồm các bước sau:

 Mỗi nút tính khoảng cách giữa nó và tất cả các nút khác trong hệ thống tự chủ và lưu trữ thông tin này trong một bảng [9]

 Mỗi nút gửi bảng thông tin của mình cho tất cả các nút lân cận [9]

Khi một nút nhận thông tin từ các nút lân cận, nó sẽ tính toán các tuyến đường ngắn nhất đến tất cả các nút khác và cập nhật bảng thông tin của mình.

5.2.5 Ví dụ về thuật toán Bellman-Ford.

Ta có đồ thị như sau:

Hình 5.3 Ví dụ đồ thị cho giải thuật Bellman-For

Bước 1: Thực hiện chọn đỉnh bắt đầu và gán các giá trị vô cực cho đường đi của tất cả các đỉnh khác.

Bước 2:Thực hiện duyệt qua từng cạnh và nới lỏng khoảng cách đường đi nếu không chính xác

Bước 3: Ta cần thực hiện V lần bởi trong trường hợp xấu nhất, độ dài đường đi của một đỉnh có thể bị thay đổi V lần.

Hình 5.4 Đồ thị ví dụ cho thuật toán Bellman-Ford.

Hình 5.5: Gián giá trị ∞ vào các đỉnh đồ thị trong thuật toán Bellman-Ford.

Hình 5.6 Duyệt qua từng cạnh đồ thị trong thuật toán Bellman-Ford.

Bước 4: Lưu ý rằng đỉnh nằm ở góc trên bên phải đã thay đổi độ dài đường đi của nó.

Bước 5: Sau khi xác định độ dài đường đi cho tất cả các đỉnh, chúng ta cần kiểm tra sự tồn tại của vòng lặp có trọng số âm.

Bảng 4.1: Kết quả chạy của thuật toán Bellman-Ford.

5.2.6 Nhược điểm của thuật toán Bellman-Ford.

Nhược điểm chính của thuật toán Bellman-Ford trong cấu hình này là:

 Các thay đổi của tô-pô mạng không được ghi nhận nhanh do các cập nhật được lan truyền theo từng nút một.

Khi một nút trong mạng bị tách rời do liên kết hỏng hoặc sự cố mạng, các nút còn lại vẫn tiếp tục ước lượng khoảng cách đến nút đó và giá trị sẽ dần tăng lên.

Hình 5.7 Duyệt lại tìm trường hợp xấu nhất trong thuật toán Bellman-Ford.

Hình 5.8 Kết quả của lần duyệt cuối cùng trị tính được, trong khi đó còn có thể xảy ra việc định tuyến thành vòng tròn) [9]

Mô Phỏng

Định tuyến là một công việc quan trọng trong mạng quang WDM, giúp tìm đường cho lightpath mang lưu lượng thông tin từ nguồn đến đích nhằm tối ưu hóa mạng Trong chương này, tôi mô phỏng quá trình định tuyến cho các lightpath bằng phần mềm Java, cho phép tùy chọn hàm mục tiêu như chi phí, độ trễ và lưu lượng Thuật toán Dijkstra được sử dụng để thực hiện định tuyến, với trọng số trên các tuyến không chỉ dựa vào độ dài mà còn phụ thuộc vào các tiêu chí như chi phí, độ trễ, băng thông và lưu lượng thông tin Nếu tiêu chí là chi phí thấp nhất, trọng số trên các tuyến sẽ là chi phí của từng tuyến đó.

Thuật toán sẽ xác định đỉnh u trong tập hợp Q có giá trị d[u] nhỏ nhất Sau đó, đỉnh này sẽ được loại bỏ khỏi Q và đưa vào tập S Tập S chứa các đỉnh tạo thành một trong những đường đi ngắn nhất từ đỉnh nguồn s đến đỉnh đích t.

3 d[v] := infinity // Gán các giá trị ban đầu

5 d[s] := 0 // Khoảng cách từ s đến s bằng 0

6 S := empty set // Thiết lập S là tập hợp rỗng

7 Q := V[G] // Tập Q chứa tất cả các node của đồ thị

8 while Q is not an empty set

11 for each edge (u,v) outgoing from u

Bài toán đặt ra cho mô phỏng: tìm đường đi ngắn nhất đến các đỉnh còn lại.

Ta cài đặt phần mềm phù hợp với bài toán của mình.

Các chức năng của phần mền:

+ Map type : loại đồ thị mô phỏng có hướng hoặc vô hướng với

Undirected là vô hướng còn Directed là có hướng.

+ Input Method : Phương pháp nhâp đồ thị chúng ta có hai sự lựa chọn là tự thiết kế Draw và chọn có sẵn Demo

+ Pont : Điểm muốn mô phỏng ta chọn tùy ý từ 1 điêm bất kỳ là Begin đến các điểm còn lại trong mạng hoặc tất cả các điểm trong mạng End

+ Run: Chạy thuật toán ta cũng có sự lựa chon là chạy toàn bộ Run all hay chạy từng bước một Run step

Các nút chức năng khác sẽ được mô tả trong hình 5.9

Hình 5.9: Chức năng của phần mền mô phỏng

Ta tiến hành thiết lâ ̣p mô phỏng bài toán như trong phần trình bày cụ thể hình 5.10

Hình 5.10: Bài toán mô phỏng trên Java

Kết quả mô phỏng: Đường đi ngắn nhất từ đỉnh A đến các đỉnh còn lại

Chi phí từ A đến A là 0 với đường đi: A Chi phí từ A đến B là 2 với đường đi: A > B Chi phí từ A đến C là 1 với đường đi: A > C Chi phí từ A đến D là 3 với đường đi: A > C > F > B Chi phí từ A đến E là 2 với đường đi: A > C > E Chi phí từ A đến F là 4 với đường đi: A > C > E > F Hình dưới đây sẽ minh họa kết quả mô phỏng và các đường đi thuật toán qua các node.

Hình 5.11: Kết quả mô phỏng thuật toán Dijkstra

Kết luận

Cả hai thuật toán Dijkstra và Bellman-Ford đều cho ra kết quả giống nhau trong điều kiện tĩnh của topo mạng và chi phí định tuyến Tuy nhiên, khi có sự thay đổi về các node trong mạng, các thuật toán này sẽ điều chỉnh lại đường đi Nếu chi phí định tuyến phụ thuộc vào lưu lượng và đường dẫn được chọn, điều này có thể dẫn đến sự không ổn định trong mạng.

Phức tạp Đơn giản dễ cài đặt

Hiểu cấu hình của mạng hiện tại bằng các tích lũy tất cả các LSA

Lấy dữ liệu cấu hình mạng từ thông tin trong bảng định tuyến của các láng giềng

Mỗi router làm việc một các độc lập để tính con đường ngắn nhất của nó tới mạng đích

Mỗi router xác định con đường tối ưu bằng cách cộng các giá trị đo, thường là số hop, nhận được từ thông tin định tuyến được chuyển từ router này sang router khác.

Chỉ cập nhật khi có sự thay đổi về cấu hình mạng

Cập nhật thông tin định tuyến một cách định kỳ

Chỉ gửi những thông tin cập nhập cần thiết, túc chỉ gửi những thay đổi mà thôi

Thông điệp cập nhật thông tin đinh tuyến lớn, do sao chép toàn bộ bảng định tuyến

Thông tin định tuyến được gửi cho tất cả các router bằng cách flooding

Thông tin định tuyến trao đổi với láng giềng bằng cách broastcast.

Bảng 4.2 Bảng tóm tắt LS và DV [2]

Gán bước sóng động trong IP/WDM (D-RWA)[3]

Giải thuật Random

Giải thuật gán bước sóng đơn giản nhất cho phép nút nguồn tìm kiếm tất cả các bước sóng để xác định tập bước sóng rỗi trên đường đi đã được xác định trước Sau khi xác định, nó sẽ chọn một bước sóng ngẫu nhiên để gán cho lightpath tương ứng.

Khi nhận yêu cầu từ một nút, nút đó sẽ xác định các bước sóng còn rỗi và ngẫu nhiên chọn một bước sóng λ i để gán cho yêu cầu Các bước sóng rỗi được xác định bằng cách loại bỏ những bước sóng đã sử dụng khỏi danh sách Khi cuộc gọi kết thúc, bước sóng λ i sẽ được loại ra khỏi danh sách bận và trở lại danh sách bước sóng rỗi ban đầu.

- Phép gán này phân phối lưu lượng 1 cách tùy ý

Phương pháp này không yêu cầu thông tin đầy đủ về trạng thái của mạng khi gán bước sóng Khi thiếu thông tin về tình trạng bước sóng trong mạng, phương pháp này vẫn giúp cân bằng số lượng bước sóng được sử dụng, từ đó giảm thiểu xác suất nghẽn mạng.

Giải thuật First-Fit(FF)

Trong giải thuật này, tất cả các bước sóng được đánh số theo thứ tự ưu tiên từ thấp đến cao Bước sóng đầu tiên được chọn sẽ có giá trị thấp nhất trong số các bước sóng rỗi.

Giải thuật FF, giống như giải thuật Random, không yêu cầu thông tin về trạng thái của mạng và có chi phí tính toán thấp hơn do không cần duyệt qua tất cả các bước sóng Trong trường hợp có đủ thông tin về trạng thái mạng, giải thuật FF sẽ hiệu quả hơn so với Random Tuy nhiên, khi thông tin bị hạn chế hoặc cập nhật không kịp thời, giải thuật Random lại tỏ ra ưu việt hơn trong việc cấp phát bước sóng.

Giải thuật này gặp hạn chế khi các bước sóng có chỉ số nhỏ được sử dụng phổ biến, trong khi các bước sóng cao lại ít được áp dụng hoặc gần như không được sử dụng.

Hình 6.2: Ví dụ về Giải thuật First-Fit

Ta có hình vẽ như trên là thứ tự các liên kết được đặt vào ở từng bước sóng

Giải thuật Least-Used(LU)

Giải thuật này lựa chọn những bước sóng ít được sử dụng nhất trong mạng nhằm mục đích cân bằng tải trên tất cả các bước sóng Để xác định bước sóng ít sử dụng, giải thuật yêu cầu thông tin trạng thái mạng, tuy nhiên, phương pháp này có thể gây tốn kém về chi phí lưu trữ và tính toán.

Hình 6.3: Ví dụ về Giải thuật Least-Uesd

Để thiết lập kết nối {4,5}, trong bài toán này, W1 được sử dụng ở 2 liên kết, W2 ở 1 liên kết, và W3 ở 3 liên kết Do đó, W2 là lựa chọn phù hợp nhất theo giải thuật LU.

Giải thuật Most-Used(MU)

Giải thuật này hoạt động ngược lại với phương pháp Least-used, tập trung vào việc chọn lựa những bước sóng được sử dụng nhiều nhất trong mạng Để xác định bước sóng này, giải thuật cần thông tin về trạng thái mạng Mặc dù chi phí thực hiện tương tự như trong phương pháp Least-used, nhưng nó mang lại hiệu quả tốt hơn trong việc tối ưu hóa việc sử dụng bước sóng.

Hình 6.4: Ví dụ Giải thuật Most-Used

Cũng với bài toán như trên, ta sẽ chọn W3 vì nó sử dụng nhiều liên kết nhất (3 liên kết)

Giải thuật Min-Product(MP)

Giải thuật này chủ yếu được áp dụng cho các mạng đa sợi, tương đương với giải thuật FF Mục tiêu chính là gán bước sóng vào các sợi quang để giảm thiểu số lượng sợi sử dụng trong mạng.

- Để thực hiện việc này, giải thuật MP tính tích ∏ l ∈ π

Mỗi bước sóng j (1≤ j

Tiêu đề	Định Tuyến Và Gán Bước Sóng Trong WDM
Tác giả	Đoàn Quang Vinh, Mai Phương Trâm, Trương Văn Trường, Nguyễn Hiếu Hoài
Người hướng dẫn	TS. Lê Quốc Cường
Trường học	Học Viện Công Nghệ Bưu Chính Viễn Thông
Chuyên ngành	Công Nghệ Truyền Tải Quang
Thể loại	báo cáo
Năm xuất bản	2021
Thành phố	Thành Phố Hồ Chí Minh

Định dạng
Số trang	36
Dung lượng	786,7 KB