BÁO cá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 ngày càng không đáp ứng được 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 chưa khai thác hết tiềm năng của công nghệ quang học, khi tốc độ của các công nghệ này chỉ đạt vài chục Gbps, trong khi một sợi quang đơn mode có thể truyền dữ liệu với tốc độ rất cao Để nâng cao băng thông cho cáp quang, công nghệ WDM (ghép kênh phân chia theo bước sóng) đã đượ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 Mỗi kênh có thể được điều chế độc lập, phù hợp với các định dạng dữ liệu và tốc độ bit khác nhau, giúp đạt được dung lượng liên kết lên tới Tbps trong mạng quang.

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

Mạng WDM phát triển nhanh chóng 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 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 truyền tải dữ liệu Công tắc truy cập và công tắc đầu cuối thực hiện chuyển đổi giữa điện tử và quang, tạo điều kiện giao tiếp hiệu quả giữa mạng quang và các trạm điện tử.

Mạng quang định tuyến theo bước sóng cho phép xác định và khoanh vùng luồng lưu lượng, sử dụng lại bước sóng trong các phân đoạn không gian của mạng Để 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 thông qua việc xác định đường dẫn nối nút nguồn với nút đích và phân bổ bước sóng tự do Đường dẫn toàn quang, hay còn gọi là lightpath, có khả năng mang dữ liệu với tốc độ cao, nhưng số lượng bước sóng khả dụng trên mỗi liên kết sợi có giới hạn, dẫn đến việc không phải lúc nào cũng có thể thiết lập lightpath giữa mọi cặp nút Một thách thức trong mạng quang định tuyến là đảm bảo rằng các lightpath không giao thoa bằng cách sử dụng các bước sóng khác nhau Mạng định tuyến theo bước sóng toàn quang 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 và quản lý mạng đơn giản hơn Lightpath là đường đi của tín hiệu ánh sáng từ nguồn đến đích qua các kết nối trung gian, và việc định tuyến và gán bước sóng cho lightpath là một bài toán quan trọng trong mạng này.

Trong mạng, việc tìm đường giữa hai node để tối ưu hàm mục tiêu (cost function) là rất quan trọng, 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à phân bổ bước sóng phù hợp cho lưu lượng trên mỗi link (Wavelength Assignment), được gọi tắt là RWA Khi xác định được một path vật lý và đánh dấu bước sóng trên các link, chúng ta có một đường quang (lightpath - LP) Bài toán RWA đặt ra điều kiện rằng một lightpath phải sử dụng chung một bước sóng trên tất cả các link dọc theo đường đi từ nguồn đến đích.

Các đường dẫn ánh sáng là thành phần chuyển mạch thiết yếu 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à rất quan trọng, do đó cần đề xuất các thuật toán tối ưu để 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à lộ trình ánh sáng từ nguồn đến đích Khi có yêu cầu cuộc gọi, nút khởi tạo sẽ sử dụng thuật toán định tuyến để xác định đường đi và bước sóng phù hợp Sau khi gán bước sóng cho cuộc gọi, nút sẽ chuyển tiếp thông tin đến nút tiếp theo Tại mỗi nút trung gian, khả năng sẵn có của bước sóng sẽ được kiểm tra để quyết định xem có thể tiếp tục lộ trình hay không Nếu bước sóng không khả dụng, quá trình sẽ bị gián đoạn.

Trong hệ thống mạng quang, khi nút có bộ chuyển đổi bước sóng, nó có khả năng chuyển đổi giữa các bước sóng để thiết lập lightpath Đườ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 khác nhau Hai cuộc gọi từ cùng một nguồn đến cùng một đích có thể chia sẻ đường vật lý nhưng lại có các đường ảo khác nhau Ví dụ, nếu nút 1 tạo ra hai cuộc gọi, mỗi cuộc gọi sẽ được gán các bước sóng khác nhau và gửi đến nút đích qua các đường ảo riêng biệt Tổng số đường ảo có thể thiết lập phụ thuộc vào số lượng bước sóng có sẵn trên sợi quang và tốc độ cuộc gọi Các bộ chuyển đổi bước sóng cho phép thiết lập nhiều đường ảo hơn, tối ưu hóa khả năng truyền tải dữ liệu.

Định tuyến (Routing)

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

Mạng viễn thông truyền thống chủ yếu được thiết kế theo 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ủ công, trong đó người quản trị nhập thông tin định tuyến cho các thiết bị định tuyến.

+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

+Bảo mật tốt Ư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, là cần thiết.

+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 Ưu và nhược điểm của Định tuyến tĩnh [13] Định tuyến động chia thành 2 loại:

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

Giao thức BGP (Border Gateway Protocol) là một giao thức quan trọng đượ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 AS là tập hợp các router có chung một chính sách định tuyến, giúp tối ưu hóa quá trình truyền tải dữ liệu trên mạng.

+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]

Đồ thị là một cấu trúc toán học bao gồm các đỉnh và cạnh, trong đó các đỉnh đại diện cho một tập hợp đối tượng, còn các cạnh thể hiện các liên kết giữa chúng.

Kí hiệu là G = (V,E) Với V là tập hợp các đỉnh

Đồ thị được xác định bởi 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 các đỉ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ự

SV thực hiện: Đoàn Quang

Trong Hình 1b, hai cạnh e1 và e2 được gọi là cạnh lặp (bội hay song song) c Đồ thị vô hướng là loại đồ thị có thể chứa khuyên và các cạnh lặp, trong đó nếu một cạnh nối một đỉnh với chính nó thì đồ 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.

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ự.

SV thực hiện: Đoàn Quang Vinh e1

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 e 1vàe 2t ương

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

Trong giao thức định tuyến OSPF, các router chỉ gửi tình trạng của các đường link trong cơ sở dữ liệu linkstate của mình đến các router khác Các router sau đó sẽ sử dụng thuật toán SPF (shortest path first) để xác định đường đi ngắn nhất.

Để xây dựng bảng định tuyến riêng, khi mạng hội tụ, giao thức Link State sẽ không gửi cập nhật định kỳ mà chỉ thông báo khi có sự thay đổi trong mạng, như khi một kết nối bị ngắt hoặc cần sử dụng đường dự phòng.

Hệ thống này có khả năng thích nghi với đa số mạng, 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 duy trì băng thông cho các đường mạng, đảm bảo hiệu suất hoạt động ổn định.

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 Edsger Dijkstra vào năm 1956 và công bố vào năm 1959, là một phương pháp tìm đường đi ngắn nhất giữa hai đỉnh bất kỳ 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 Khi thông tin giá trị được thu thập, tất cả các node sẽ nắm 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 còn lại Nếu không tồn tại đường đi, cần thông báo điều đó.

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 Trong mỗi bước, thuật toán chọn một đỉnh u mà không thể tối ưu hơn nữa, và sau đó tối ưu hóa các đỉnh v khác thông qua 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 sẽ giữ lại đườ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 Tiếp theo, thuật toá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 tham khảo.

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

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

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 dựa trên nguyên tắc Neighbor Theo đó, mỗi router sẽ gửi bảng định tuyến của mình đến tất cả các router được 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à cập nhật các tuyến đường tối ưu hơn 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 hiệu quả để tìm đường đi ngắn nhất từ một nguồn trong đồ thị có hướng và trọng số, bao gồm cả các cung có trọng số âm Mặc dù thuật toán Dijkstra có thời gian chạy nhanh hơn, nhưng nó chỉ áp dụng cho đồ thị có trọng số không âm Vì vậy, Bellman-Ford thường được lựa chọn trong các trường hợp có 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ẽ thực hiện nhiều lần lặp 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 rồi đến v.

Ví dụ đồ thị sau:

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

Giả sử chúng ta có đường đi từ 1 đến 3 với độ dài 4 và từ 1 đến 2 với độ dài 2 Bằng cách sử dụng cạnh (2,3), chúng ta có thể mở rộng đường đi từ 1 đến 2 thành 1→2→3 với tổng độ dài 3, điều này cho thấy đường đi này ngắn 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 trong đồ thị không có đỉnh nào được đi lại quá một lần, do đó số cạnh tối đa trong đường đi này là N−1 Việc tính toán Dv=Du+Wu,v cho thấy rằng mỗi lần thêm một cạnh u→v vào hành trình từ s đến v, giá trị Du chỉ có thể được tối ưu tối đa N−1 lần Từ lần tối ưu thứ N trở đi, không thể cải thiện thêm 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.4 Đồ thị ví dụ cho thuật toán Bellman-Ford.

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.

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

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.

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

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.7 Duyệt lại tìm trường hợp xấu nhất 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ó.

Hình 5.8 Kết quả của lần duyệt cuối cùng

Bước 5: Khi tất cả các đỉnh đã được tính toán độ dài đường đi, 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à:

Không nhân rộng tốt là một vấn đề trong mạng, khi các thay đổi về tô-pô không được ghi nhận kịp thời do quá trình cập nhật chỉ diễn ra từng nút một Nếu một liên kết hoặc nút mạng bị hỏng, nó có thể khiến một nút bị tách khỏi nhóm các nút khác, dẫn đến việc các nút còn lại vẫn tiếp tục ước tính khoảng cách đến nút đó và dần dần làm tăng giá trị ước lượng.

T r a n g | 19 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 trong mạng quang WDM đóng vai trò quan trọng trong việc tìm đường cho lightpath, giúp tối ưu hóa mạng bằng cách chuyển tải thông tin từ nguồn đến đích Trong chương này, tôi sử dụng phần mềm Java để mô phỏng quá trình định tuyến cho các lightpath với các hàm mục tiêu tùy chọn như chi phí, độ trễ và lưu lượng qua các tuyến Thuật toán Dijkstra được áp 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í được chọn là chi phí thấp nhất, trọng số trên các tuyến sẽ phản ánh điều đó.

(cạnh) là chí phí của tuyến đó.

Thuật toán tìm đỉnh u trong tập hợp Q với giá trị d[u] nhỏ nhất, sau đó loại bỏ đỉnh này khỏi Q và thêm vào tập S Tập S sẽ bao gồm 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

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

7Q := 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âpp̣ 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

The cost to travel from point A to A is 0, with the direct path being A Traveling from A to B incurs a cost of 2, following the path A > B For a journey from A to C, the cost is 1, taking the route A > C The cost to reach point D from A is 3, which involves the path A > C > F > B Lastly, the journey from A to E costs 2, utilizing the path A > C > E.

The cost from A to F is 4 Path : A > C > E > F Hình sau đây sẽ cho ta thấy kết quả mô phỏng và các đường đi thuât toán qua 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 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 để tính toán 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 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

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

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

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 tin định tuyến được gửi cho tất cả các router bằng cách flooding

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 nhằm 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 ngẫu nhiên một bước sóng để gán cho lightpath đó.

Khi nhận được yêu cầu từ một nút, nút đó sẽ xác định các bước sóng còn khả dụng 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 khả dụng được xác định bằng cách loại bỏ những bước sóng đã được sử dụng Khi cuộc gọi kết thúc, bước sóng λ i sẽ được xóa 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 thực hiện gán bước sóng Khi thiếu thông tin về tình trạng bước sóng, phương pháp này vẫn có thể 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, các bước sóng được đánh số theo thứ tự ưu tiên từ thấp đến cao Cụ thể, các bước sóng rỗi sẽ được sắp xếp và đánh số, với bước sóng đầu tiên được chọn có giá trị thấp nhất.

Giải thuật FF, tương tự như Giải thuật Random, không yêu cầu thông tin về trạng thái 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 Khi có đầy đủ thông tin về trạng thái mạng, giải thuật FF thường cho hiệu quả tốt hơn so với Random Tuy nhiên, trong những trường hợp thông tin 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 nhằm cân bằng tải trên mạng bằng cách lựa chọn những bước sóng ít được sử dụng nhất Để thực hiện điều này, nó cần thông tin trạng thái mạng để xác định bước sóng tối ưu Tuy nhiên, phương pháp này yêu cầu chi phí lưu trữ và tính toán cao.

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 sử dụng 2 liên kết, W2 sử dụng 1 liên kết và W3 sử dụng 3 liên kết Do đó, lựa chọn W2 là phù hợp với giải thuật LU.

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

Giải thuật này là phương pháp ngược lại với 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ép gán Least-used, giải thuật này cho hiệu quả tốt hơn so với giải thuật Least-used.

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 được thiết kế đặc biệt 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 cho các sợi quang, nhằm giảm thiểu số lượng sợi quang sử dụng trong mạng.

Giải thuật MP thực hiện tính tích ∏ D lj cho mỗi bước sóng j, với điều kiện 1≤ l ∈ π j