Đồ án Nghiên cứu phân bổ tối ưu bộ chuyển đổi bước sóng trong mạng AON

ơng pháp gán tĩnh, việc thực hiện sẽ không phức tạp do không phải chạy bất kỳ một thuật toán RWA nào, nó chỉ việc gán ngay một đường đi và một bước sóng khi nhận được yêu cầu. Bài toán RWA động, việc định tuyến và gán bước sóng phù hợp được quyết định dựa vào thông tin trạng thái toàn mạng node phục vụ có được tại thời điểm đó. Thuật toán định tuyến và gán bước sóng RWA được hình thành từ hai thuật toán là: thuật toán định tuyến (lựa chọn một tuyến/ lối ra) và thuật toán gán bước sóng với yêu cầu là để giảm tối thiểu xác suất nghẽn. Dưới đây tác giả sẽ nêu tổng quát hoá các thuật giải định tuyến và gán bước bước sóng đã được đề xuất. Các thuật toán định tuyến Các thuật toán định tuyến cũng được phân ra hai loại: thuật toán định tuyến tĩnh (Static/fixed routing) và thuật toán định tuyến động ( Dynamic/adaptive routing). Định tuyến tĩnh có nghĩa là việc lựa chọn tuyến độc lập với trạng thái hiện thái của mạng. Ngược lại, định tuyến động lại dựa vào thông tin trạng thái toàn mạng để chọn ra một tuyến đi. Định tuyến có đường đi ngắn nhất (SPR- Shortest Path Routing) Là thuật toán định tuyến tĩnh đơn giản nhất. Các tuyến đi giữa bất kỳ hai router nào đều được xác định trước (thường là tuyến ngắn nhất) và không yêu cầu phải có thông tin về trạng thái mạng để thiết lập một lightpath. Song loại định tuyến này có xác suất nghẽn cao. Định tuyến thay thế cố định (FAR- Fixed -alternate Routing) So với thuật toán SPR, thuật toán định tuyến này sẽ cải thiện xác suất nghẽn rõ rệt. Theo thuật toán định tuyến này, mỗi cặp nguồn-đích được gán sẵn một tập các tuyến đi. Một giả thiết chung cho cá thuật toán định tuyến FAR đó là các tuyến thay thế (alternate routes) của mỗi cặp nguồn và đích không có link chung, để xác suất nghẽn xảy ra trên một tuyến này độc lập với xác suất nghẽn xảy ra trên các tuyến dự phòng khác. Các kết quả mô phỏng đã chỉ ra rằng, khi tải thấp và số lượng tuyến dự phòng (alternate routes) giữa nguồn và đích chưa tận dụng hết các kết nối của mạng, lợi ích về xác suất nghẽn từ việc thêm một tuyến dự phòng mới lớn hơn so với việc thêm vào khả năng chuyển đổi bước sóng. Có rất nhiều các công trình nghiên cứu đã chỉ ra rằng, các thuật toán định tuyến động hiệu quả hơn định tuyến tĩnh. Tuy nhiên, do cần phải có thông tin về trạng thái của mạng để thiết lập lighpath nên thuật toán định tuyến động cần sẽ gây ra trễ lớn hơn và điều khiển phức tạp. Định tuyến theo tải ít nhất (LLR- Least Loaded Routing) Karasan đã đề xuất một thuật toán RWA động có tên là định tuyến theo tải ít nhất LLR. Thuật toán này sẽ chọn ra cặp tuyến – bước sóng (Route-wavelength pair) đang có tải nhỏ nhất. Nó chọn tuyến bị nghẽn ít nhất và chọn một bước sóng trong tập các bước sóng rỗi từ k các đường đi ngắn nhất xác định trước. Việc lựa chọn này dựa trên thông tin về trạng thái hiện tại của mạng, để tránh các tuyến đã bị quá tải không bị tắc nghẽn thêm. Định tuyến theo tuyến nghẽn nhỏ nhất với các tuyến cố đinh ( FPLC -Fixed-Paths Least-Congestion Routing) FPLC là một thuật toán định tuyến động do Ling Li đề xuất. Khi nhận được một yêu cầu kết nối, thuật toán sẽ chọn tuyến có mức độ nghẽn nhỏ nhất trong số một tập các tuyến xác định trước. Tuyến được chọn sẽ là tuyến có số lượng bước sóng rỗi lớn nhất trong tập các tuyến tìm được kết nối nguồn-đích. Nếu không thể tìm ra tuyến nào, thì yêu cầu sẽ bị từ chối (blocked). Vì vậy thuật toán này yêu cầu node đang phục vụ phải có thông tin về các bước sóng đang rỗi trên tất cả các tuyến của tập dự phòng. Chất lượng của thuật toán FPLC được đánh giá bằng cách sử dụng các mô hình phân tích và công cụ mô phỏng. Phương pháp định tuyến FLPC được so sánh với các phương pháp định tuyến khác: FAR và SPR. Kết quả cho thấy, thuật toán FPLC tốt hơn nhiều so với FAR và SPR khi tải thấp. Để thiết lập một kết nối, thông tin về các bước sóng rỗi trên các link của tập tất cả các tuyến dự phòng phải được trao đổi giữa các node với nhau. Nhược điểm của thuật toán FPLC là gây ra trễ lớn và sinh ra lưu lượng mào đầu điều khiển cao hơn. Các thuật toán gán bước sóng Gán bước sóng là yếu tố chính quyết định đến xác suất nghẽn và kéo theo là chất lượng mạng. Việc gán hợp lý các bước sóng có thể làm giảm hoặc không sử dụng các bộ chuyển đổi bước sóng, do đó sẽ giảm được đáng kể chi phí. Cần lưu ý rằng, nếu tất cả các bộ định tuyến bước sóng (WR) đều có khả năng chuyển đổi bước sóng, thì bài toán gán bước sóng trở thành vô nghĩa. Vì vậy khi ta nghiên cứu bài toán gán bước sóng, ta phải giả thiết rằng mạng không sử dụng bộ chuyển đổi bước sóng. Tuy nhiên nếu là mạng có bộ chuyển đổi bước sóng được phân bố rải rác (Sparse wavelength conversion), chúng ta vẫn cần phải xem xét bài toán gán bước sóng. Thuật toán gán bước sóng được chia ra thành hai loại: thuật toán gán tĩnh (static assignemnt hay off-line) và thuật toán gán động (dynamic assignment hay on-line). Trong mô hình gán tĩnh, cùng môt bước sóng có thể được gán cho mọi yêu cầu đến một node với điều kiện bước sóng đó đang chưa được gán, nếu không cuộc yêu cầu đó sẽ không được phục vụ và xảy ra nghẽn mạng. Trong mô hình gán động, khi có yêu cầu lightpath đến node, node đó sẽ sử dụng một thuật toán gán xác định để chọn ra và gán bước sóng còn rỗi nào đó cho yêu cầu đó, nếu không xảy ra nghẽn tại node này. Hầu hết các thuật toán gán bước sóng đang hiện có thuộc loại gán động. Mọi thuật toán gán bước sóng đều lưu một danh sách các bước sóng đang sử dụng và đang rỗi tại một node. Bất cứ khi nào xuất hiện một yêu cầu tại node đó, nó sẽ chọn ra một bước sóng từ một tập hợp các bước sóng đang rỗi và gán nó cho yêu cầu đó. Có rất nhiều các nghiên cứu đánh giá và so sánh chất lượng của các thuật toán gán bước sóng khác nhau. Dưới đây là một số thuật toán gán bước sóng đã được đề xuất. Gán bước sóng ngẫu nhiên ( Random Wavelength Assigment) Theo thuật toán này, node sẽ giữ một danh sách các bước sóng đang rỗi được cập nhật sau một khoảng thời gian xác định. Khi có một cuộc gọi đến, Node sẽ chọn ra ngẫu nhiên một bước sóng từ một tập các bước sóng rỗi và gán bước sóng đó cho cuộc gọi. Tập các bước sóng đang rỗi được cập nhật qua việc xoá bước sóng ra khỏi danh sách. Khi cuộc gọi kết thúc, bước sóng đó được xoá khỏi danh sách các bước sóng đang được sử dụng và đưa vào danh sách các bươc sóng còn rỗi. Theo như vậy, danh sách các bước sóng rỗi sẽ được cập nhật mỗi khi cuộc gọi nhận được tín hiệu trả lời hoặc thời gian giữ cuộc gọi đã hết. Gán bước sóng động sẽ phân phối lưu lượng ngẫu nhiên để hiệu suất sử dụng bước sóng được cân bằng. Việc gán một bước sóng ngẫu nhiên dẫn tới tranh chấp sử dụng bước sóng đó thấp và kết quả là xác suất nghẽn cũng thấp hơn Gán bước sóng phù hợp đầu tiên (First-Fit Wavelength Assignment) Thuật toán được thực hiện bằng cách định nghĩa trước bậc (chỉ số) của các bước sóng. Danh sách các bước sóng đang sử dụng và danh sách bước sóng rỗi được cập nhật. Thuật toán gán bước sóng này luôn chọn bước sóng có chỉ só nhỏ nhất và gán nó cho yêu cầu. Khi cuộc gọi kết thúc, bước sóng này được đưa vào danh sách các bước sóng rỗi. Nhược điểm của phương pháp này là các bước sóng chỉ số thấp hơn bị sử dụng nhiều hơn so với các bước sóng khác. Bước sóng có bậc càng cao càng ít được sử dụng. Vì vậy sẽ có một số bước sóng có hiệu suất sử dụng rất thấp. Hơn nữa việc tăng số bước sóng trên một sợi quang cũng không cải thiện chất lượng của mạng khi các bước sóng có chỉ số cao ít khi được sử dụng. Vì vậy tất cả các node trong mạng sử dụng các bước sóng thấp dẫn đến tranh chấp bước sóng xảy ra nhiều sẽ làm tăng xác suất nghẽn. Gán bước sóng được sử dụng nhiều nhất (Most-used wavelength Assignment) Theo thuật toán này, bước sóng rỗi được sử dụng nhiều nhất trên các tuyến sợi quang sẽ được phân bổ cho yêu cầu. Nếu có vài bước sóng có cùng mức độ sử dụng cao nhất, thì bước sóng có chỉ số nào đó, ví dụ thấp nhất, sẽ được chọn để gán. Gán bước sóng sử dụng ít nhất ( Least- used wavelength Assignment) Thuật toán này cũng tương tự với thuật toán gán bước sóng được dùng nhiều nhiều nhất ở trên, chỉ khác ở đây là bước sóng được sử dụng ít nhất được gán. Mục đích chính của thuật toán là để đạt được phân bố tải gần như đồng đều trên tập tất cả các bước sóng. Trong các thuật toán gán bước sóng đề cập ở trên, thuật toán gán ngẫu nhiên và thuật toán phù hợp đầu tiên được sử dụng nhiều nhất trong thực tế vì chúng được thực hiện đơn giản. Không giống như các thuật toán gán bước sóng được sử dụng nhiều nhất, và ít nhất, các thuật toán này không yêu cầu phải biết thông tin về toàn mạng. Chúng chỉ phụ thuộc vào trạng thái của node tại thời điểm đó và chọn bước sóng từ tập các bước sóng rỗi trên tuyến sợi quang đầu ra. Vì không quan tâm đến trạng thái của mạng, nên các thuật toán gán này sẽ không đạt được kết quả tối ưu. Thuật toán gán ngẫu nhiên được đánh giá là tốt hơn thuật toán gán phù hợp đầu tiên vì nó có thể chọn bất kỳ bước sóng rỗi nào. Để thực hiện các thuật toán gán bước sóng sử dụng nhiều nhât và ít nhất, mỗi node phải biết thông tin về toàn mạng. Chất lượng của các thuật toán này phụ thuộc vào mức độ chính xác của thông tin về mạng mà mỗi node nắm được. Vì trạng thái của mạng thay đổi rất nhanh, rất khó để cập nhật chính xác thông tin mạng tại mọi thời điểm, sẽ ảnh hưởng đến việc gán bước sóng. Hơn nữa, các nodes phải trao đổi thông tin về trạng thái mạng với các node lân cận sau mỗi khoảng thời gian cố định. Các bản tin trao đổi này tiêu tốn đáng kể băng thông của mạng, làm giảm băng thông cung cấp cho lưu lượng cần truyền. Ngoài ra các thuật giải này phải lưu trữ trạng thái mạng và rất phức tạp để thực hiện.  NGHIÊN CỨU PHÂN BỔ TỐI ƯU BỘ CHUYỂN ĐỔI BƯỚC SÓNG Vai trò bộ chuyển đổi bước sóng Mạng WDM toàn quang định tuyến bằng bước sóng (Wavelength-routed all-optical WDM) được coi là ứng cử viên cho mạng đường trục diện rộng thế hệ thiếp theo. Mạng này được hình thành từ một tập các bộ định tuyến bước sóng (kí hiệu là WR- Wavelength Router)nối trực tiếp với nhau bằng tuyến sợi quang. Trên mỗi tuyến này có thể có hàng vài trục bước sóng truyền đồng thời trên đó nhờ sử kỹ thuật ghép kênh theo bước sóng WDM. Các WR có thể chuyển mạch các tín hiệu quang đầu vào dựa trên bước sóng của chúng. Hai bộ định tuyến bước sóng về mặt vật lý kết nối trực tiếp hoặc không, có thể trao đổi thông tin với nhau bằng cách thiết lập một lightpath giữa chúng (là một kết nối quang trực tiếp không qua bất kì một phần tử điện tử trung gian nào). Trong mạng WDM định tuyến bằng bước sóng, một chuỗi các yêu cầu thiết lập lightpath đến node, mỗi lightpath có một khoảng thời gian tồn tại (holding time) ngẫu nhiên. Do hạn chế về dung lượng của mạng nên một số yêu cầu lightpath không được đáp ứng, gây ra nghẽn. Một trong những mục tiêu của bài toán thiết kế mạng AON là giảm tối thiểu xác suất nghẽn này. Trong mạng WDM, để thiết lập một lightpath, mạng yêu cầu các tuyến truyền dẫn(link) dọc theo đường đi (path/route)từ nguồn đến đích phải tồn tại cùng một bước sóng còn rỗi trên đó. Yêu cầu này được gọi là ràng buộc về tính liên tục của bước sóng. Mạng định tuyến bằng bước sóng nhu vậy được gọi là mạng liên tục bước sóng (Wavelength- continuous network). Nó khác với mạng chuyển mạch kênh truyền thống (Circuit-switched network) chỉ từ chối phục vụ cuộc gọi khi không còn tài nguyên (timeslot) trên tất cả các tuyến có thể thiết lập được kết nối. Do đó so với mạng chuyển mạch kênh truyền thống, xác suất nghẽn cuộc gọi (hay kết nối) trong mạng WDM cao hơn rất nhiều do ràng buộc về tính liên tục bước sóng- “một lightpath phải sử dụng cùng một bước sóng từ nguồn đến đích “ Ví dụ sau sẽ giải thích rõ hơn về khả năng xảy ra không thể thiết lập lightpath. Thiết lập lightpath đơn giản Xét ví dụ ở hình trên, ta có 3 nodes định tuyến bước sóng (WR) được nối với nhau bằng hai tuyến sợi quang Link 1 và Link 2. Giả sử trên Link 1 các bước sóng và đều bận, trên Link 2 các bước sóng và cũng đang bận. Bây giờ có một yêu cầu thiết lập lightpath giữa node 2 và node 3 cần định tuyến qua Link 1 và Link 2. Rõ ràng, yêu cầu này sẽ bị từ chối vì các bước sóng còn rỗi trên hai tuyến Link 1 và Link 2 là khác nhau, và ta nói mạng xảy ra nghẽn. Do vậy mạng liên tục bước sóng có xác suất nghẽn cao hơn so với mạng chuyển mạch kênh truyền thống. Để giảm ảnh hưởng của điều kiện ràng buộc trên lên xác suất nghẽn, người ta loại bỏ yêu cầu ràng buộc này bằng cách sử dụng bộ chuyển đổi bước sóng (WC- Wavelength Converter) tại các node mạng. Bộ chuyển đổi bước sóng có thể chuyển đổi tín hiệu quang từ một bước sóng sang bước sóng khác. Trong ví dụ ở trên nếu node 2 có khả năng chuyển đổi tín hiệu có bước sóng trên Link 1 thành tín hiệu có bước sóng phát trên Link 2, thì yêu cầu thiết lập lighpath cho kết nối node 1 và node 3 sẽ được chấp nhận, vì vậy sẽ làm giảm xác suất nghẽn. Một node có khả năng chuyển đổi bước sóng được gọi là router có thể chuyển đổi bước sóng (WCR-Waveleng Convertible Router). Các mạng quang định tuyến bước sóng với khả năng chuyển đổi bước sóng được gọi là mạng có thể chuyển đổi bước sóng (Wavelength -convertible Networks). Khả năng chuyển đổi của một node WCR được đánh giá bằng số bộ WC mà nó có. Tại một thời điểm một bộ WC chỉ cho phép chuyển đổi được một bước sóng sang bước sóng khác. Vì vậy số chuyển đổi bước sóng đồng thời được thực hiện trong WCR được xác định bằng số bộ WC mà nó có. Tuy nhiên hiện nay giá thành của các bộ WC còn rất đắt, vì vậy có nhiều cấu trúc WCR được đề xuất để giảm chi phí chi phí thiết bị: WCR chuyển đổi bước sóng đầy đủ (Complete Wavelength Conversion) Hình 3.2 là ví dụ về bộ vWCR với khả năng chuyển đổi bước sóng đầy đủ, ở đó mỗi đầu ra của khối chuyển mạch quang gắn với với một bộ chuyển đổi bước sóng riêng. Loại WCR được coi là lý tưởng vì nó có khả năng chuyển đổi đồng thời tất cả các bước sóng đầu vào sang bất kỳ bước sóng đầu ra nào. Chú ý rằng, số lượng bộ WC bằng số sợi quang nhân với số bước sóng trên một sợi quang. Vì số bước sóng trên mỗi sợi quang có thể lên đến hàng trăm hoặc nhiều hơn, nên số lượng bộ WC trong mỗi node WCR rất lớn, kéo theo giá thành của node cấu trúc đó rất cao. WCR chuyển đổi bước sóng một phần (Partial Wavelength Conversion) Hình 3.3 là cấu trúc WCR với số lượng bộ chuyển đổi hạn chế và được dùng chung cho tất cả các cổng ra. Cấu trúc này cần rất ít số bộ chuyển đổi bước sóng mà mạng vẫn có thể đạt chất lượng gần bằng với cấu trúc chuyển đổi bước sóng đầy đủ nhờ việc phân bổ tối ưu bộ chuyển đổi tại các node mạng. Mặc dù vậy nó lại phức tạp hơn so với bộ định tuyến bước sóng không có WC, vì nó phải cần đến một khối chuyển mạch quang nhỏ (OSW). Vấn đề cần phải biết bao nhiêu bộ WC phải đặt ở mỗi node WCR để đạt được chất lượng mong muốn. Các cấu trúc node chuyển đổi bước sóng đầy đủ Cấu trúc node chuyển đổi bước sóng một phần Các mạng toàn quang WDM định tuyến bằng bước sóng thường được phân loại theo đặc điểm chuyển đổi bước sóng của toàn mạng. Có thể xem xét và đánh giá theo khả năng chuyển đổi bước sóng của từng node hoặc cả mạng. Khả năng chuyển đổi của node được chia thành 3 loại: đầy đủ, giới hạn, hoặc không có (complete, limited, no). Node được cho là có khả năng chuyển đổi đầy đủ (complete conversion capability) khi nó có thể chuyển đổi đồng thời tất cả các bước sóng đầu vào sang bất kỳ bước sóng khác ở đầu ra. Trong khi đó, nếu node chỉ có thể chuyển đổi một vài bước sóng tại một thời điểm, thì WCR được gọi là có khả năng chuyển đổi một phần (Partial conversion capability). Nếu xét tất cả các node của mạng quang, ta có thể chia ra làm hai loại mạng: mạng có tất cả các node là WCR (full), và mạng có một số node là WCR (Sparse). Loại mạng sau được để ý nhiều hơn vì nó có thể tiết kiệm đáng kể số bộWC, và là giải pháp mềm dẻo vì nó cho phép mạng được nâng cấp dần lên để có khả năng hỗ trợ chuyển đổi bước sóng. Kết hợp về phân bố WCR trên toàn mạng và khả năng chuyển đổi bước sóng của mỗi bộ WCR tại node, ta có một số cấu trúc mạng các node WC/WCR: full-complete, full-partial, sparse-complete, sparse-partial. Một mạng được gọi là có khả năng chuyển đổi full-complete khi tất cả các tuyến dọc theo mỗi lightpath không bị mạng bị từ chối thiết lập do ràng buộc liên tục bước sóng. Với đặc tính đó, mạng sẽ đạt được xác suất nghẽn thấp nhất (giới hạn dưới) trong trường hợp tải lưu lượng động. Trong mạng với khả năng chuyển đổi full-partial, tất cả các node đều là WCR, với khả năng chuyển đổi bước sóng partial. Khi mạng chỉ có một số node của mạng là WCR có khả năng chuyển đổi complete ta gọi mạng này là sparse-complete. Nếu một mạng các các node WCR phân bố rải rác với khả năng chuyển đổi bước sóng partial, thì mạng này được gọi là mạng SPWC (Sparse –Partial Wavelength Conversion) Mặc dù có những tiến bộ đáng kể trong công nghệ chế tạo bộ chuyển đổi bước sóng WC, nhưng giá thành vẫn còn rất cao. Chính vì vậy yêu cầu đối với bài toán thiết kế mạng quang là phải đưa ra phương pháp phân bổ tối ưu WC trên toàn mạng sao cho chất lượng của mạng đạt được tiến gần đến chất lượng mạng full-complete với yêu cầu sử dụng số WC cho toàn mạng là ít nhất. Theo kết quả của nhiều công trình nghiên cứu, hiệu quả của việc sử bộ chuyển đổi bước sóng trong mạng truyền dẫn quang phụ thuộc vào rất nhiều yêu tố. Cụ thể đó là: cấu trúc mạng (network topology), thuật toán RWA được sử dụng, số bước sóng, khả năng chuyển đổi bước sóng, và đặc tính của lưu lượng chạy trên mạng. Giới thiệu tổng quan Như đã nói ở trên, để giảm ảnh hưởng của điều kiện ràng buộc về tính liên tục bước sóng lên xác suất nghẽn cuộc gọi, bộ chuyển đổi bước sóng đã được sử dụng. Nếu các bộ chuyển đổi được đặt ở tất cả các node mạng, thì điều kiện này hoàn toàn được loại bỏ và xác suất nghẽn của mạng giảm rất nhiều. Tuy nhiên do các khó khăn về mặt kĩ thuật nên giá thành các bộ chuyển đổi còn rất đắt. Chính vì vậy, cộng đồng nghiên cứu đã tập trung nỗ lực nghiên cứu vào các mạng SPWC, ở đó chỉ có một số node là có khả năng chuyển đổi bước sóng. Hơn nữa các nghiên cứu trước đó đã chỉ ra rằng mạng Sparse-wavelength conversion cũng có thể đạt chất lượng nghẽn tương tự như mạng quang full-wavelength conversion nếu các bộ chuyển đổi được đặt một cách tối ưu. Bài toán đặt tối ưu bộ chuyển đổi (WCP) có liên quan chặt chẽ với bài toán RWA. Để chọn một thuật toán RWA phù hợp , giả thiết lưu lượng rất quan trọng. Ta có thể chia làm hai loại lưu lượng chính là tĩnh và động. Đối với lưu lượng tĩnh, tất cả các kết nối đều được cố định và biết trước, do đó mục tiêu phải giảm tối đa số bước sóng sử dụng để đáp ứng một yêu cầu đó. Còn đối với lưu lượng động, tất cả các yêu cầu kết nối đến/đi khỏi mạng một cách ngẫu nhiên, và mục tiêu của ta là phải giảm xác suất nghẽn kết nối. Trong tất cả các thuật giải định tuyến, thuật định tuyến theo tải nhỏ nhất (LLR) hay được sử dụng phổ biến hơn cả trong các mạng chuyển mạch kênh truyền thống. Định tuyến động xác định tuyến sau khi xem xét trạng thái toàn mạng tại thời điểm nhận được yêu cầu kết nối. Nói chung, chất lượng (xác suất nghẽn) của các thuật giải động tốt hơn rất nhiều (thấp hơn) so với các thuật giải định tuyến tĩnh. Lí do là định tuyến động đưa ra quyết định dựa trên trạng thái mạng hiện tại, vì vậy một tuyến, ở đó nghẽn đã được tránh, có thể được thiết lập. Còn trong những thuật giải gán bước sóng, gán bước sóng ngẫu nhiên và gán bước sóng phù hợp đầu tiên (FF) là các thuật giải được sử dụng nhiều nhất. Trong thuật giải gán ngẫu nhiên, các bước sóng rỗi được chọn ngẫu nhiên trong tất cả các kết nối dọc theo tuyến. Trong thuật giải gán FF các bước sóng được chọn dựa trên thứ tự được quy định trước (chỉ số từ thấp đến cao) từ một tập các bước sóng rỗi dọc theo tuyến. Thuật toán FF đạt được xác suất nghẽn thấp hơn so với gán ngẫu nhiên khi tăng độ phức tạp của mạng Lúc đầu các bài toán RWA và bài toán phân bổ bộ chuyển đổi bước sóng được nghiên cứu độc lập với nhau. Mặc dù gầy đây, người ta đã chứng minh được việc xem xét đồng thời đó sẽ cho kết quả tốt hơn, nhưng rất khó có thể đưa ra một mô hình tối ưu đồng thời cho cả hai vấn đề do tính phức tạp của nó. Do đó để cho dễ nghiên cứu và đánh giá, người ta đi xây dựng thuật giải WCP tối ưu cho một thuật toán RWA cụ thể, và trong một mạng quang có cấu trúc cụ thể (Mesh, Tree, Ring). Trong luận văn này, tác giả chỉ giới thiệu các thuật toán WCP được đề xuất cho mạng quang sử dụng định tuyến động LLR và gán bước sóng ngẫu nhiên hoặc FF. Thuật toán GA cho mạng Ring Thuật toán định tuyến LLR cho mạng SWC Để đơn giản, tất cả các bộ chuyển đổi trong mô hình mạng đều là bộ chuyển đổi toàn dải (Full-range Wavelength Converter). Tuyến gồm một tập các kết nối bắt đầu từ node nguồn và kết thúc tại node đích. Trong một mạng quang đặt các bộ chuyển đổi phân tán SWC- Sparse Wavelength Converters), ta định nghĩa đoạn (segment) trên tuyến gồm một tập con các kết nối có thể là : Bắt đầu từ node nguồn và kết thúc ở bộ chuyển đổi đầu tiên. Bắt đầu từ một bộ chuyển đổi và kết thúc ở bộ chuyển đổi tiếp theo Bắt đầu ở một bộ chuyển đổi và kết thúc tại node đích hoặc. Chính là cả tuyến nếu không có bộ chuyển đổi nào trên tuyến đó. Ràng buộc về liên tục bước sóng được bỏ qua tại điểm giữa các đoạn. Nếu không có bộ chuyển đổi nào trên một tuyến, thì đoạn của tuyến chính là tuyến đó. Một ví dụ về các tuyến bị phân đoạn bởi các bộ chuyển đổi bước sóng được minh họa ở hình 3.4. Node WC là node được trang bị một bộ chuyển đổi bước sóng. Đoạn đầu tiên của tuyến từ node S đến node D gồm hai kết nối và . Đoạn thứ hai gồm hai kết nối và . Trong đoạn đầu tiên, một bước sóng chung (cụ thể là ) được sử dụng để thiết lập lighpath do tính ràng buộc liên tục bước sóng. Với khả năng của bộ chuyển đổi tại node WC, đoạn thứ hai sử dụng bước sóng khác để thiết lập lightpath. Các đoạn trên tuyến từ nguồn (S) đến đích (D) Mô hình mạng và các hàm chi phí tuyến (Path Cost) được đề xuất Thuật toán LLR đã được sử dụng trong các mạng chuyển mạch kênh từ đầu những năm 1980. Trong [8], để chuyển sang dùng cho mạng quang, dựa trên khái niệm của thuật toán LLR, hai hàm chi phí tuyến được để xuất cho hai loại mạng khác nhau. Với mạng quang không có chuyển đổi bước sóng, tuyến được chọn nếu nó thỏa mãn: (1) (Trong đó là số sợi quang trên kết nối và là số sợi quang trên đó có bước sóng trên kết nối ) Đối với mạng quang có khả năng chuyển đổi đầy đủ, một tuyến được chọn nếu thỏa mãn: (2) (Trong đó K là số bước sóng trên một sợi quang. Tuy nhiên cả hai hàm chi phí tuyến đều không được áp dụng trực tiếp vào các mạng quang với chuyển đổi bước sóng rời rạc. Trong phần này, hai hàm chi phí tuyến có thể được sử dụng trọng các thuật giải định tuyến dựa trên LLR trong các mạng phân bố WC phân tán. Đối với mỗi cặp node nguồn-đích, để giảm không gian trạng thái, chúng ta chỉ xét tuyến ngắn nhất không cố cạnh chung (k edge-disjoint shortest path) Phân loại chúng theo hop-count (tổng số kết nối trong một tuyến) theo thứ tự tăng dần và theo số bước sóng trên tất cả các kết nối theo thứ tự giảm dần. Những tuyến không có cạnh chung là để đảm bảo rằng xác suất nghẽn dọc theo tuyến đó là độc lập với nhau. Một kênh của một tuyến (hay đoạn) được định nghĩa là một bước sóng rỗi cho truyền tin từ nguồn đến đích dọc theo tuyến (đoạn). Chú ý rằng có thể có nhiều hơn một kênh sử dụng cùng một bước sóng nếu tuyến có nhiều sợi quang. Hai hàm chi phí tuyến mới được đề xuất như là các mở rộng của (1) và (2) khi mạng có phân bố WC phân tán. Hàm thứ nhất kí hiệu là LLR-MMM (Least-Load Routing using Min-Max-Min) cho bởi công thức: (3) Trong đó là tuyến cho yêu cầu kết nối . Nếu trên tuyến này chỉ có một vài node có bộ chuyển đổi bước sóng, thì tuyến này được phân thành nhiều đoạn và chi phí của một đoạn được định nghĩa là số tối đa các kênh còn rỗi của tất cả các bước sóng trên tuyến này. Chú ý rằng hàm chi phí của tuyến này liên quan đến cả định tuyến và gán bước sóng. Hàm chi phí thứ hai được kí hiệu LLR-MSM (Least Load Routing using Min-Sum-Min): (4) Hàm chi phí này xem xét trường hợp có một số node dọc tuyến không có bộ chuyển đổi bước sóng nào. Nếu một số node trên tuyến này không được trang bị bộ chuyển đối, thì tuyến được phân làm nhiều đoạn và chi phí của một đoạn là tổng số kênh còn rỗi của tất cả các bước sóng trên đoạn đó. So với LLR-MMM, hàm chi phí tuyến này thể hiện tốt hơn với số kênh rỗi tổng cộng của một đoạn vì khái niệm tải nhỏ nhất được áp dụng cho tổng số kênh rỗi chứ không phải số lượng tối đa kênh rỗi trong một bước sóng. Điều này có thể vì hàm chi phí tuyến không liên quan đến bần kì thuật giải gán bước sóng nào trong mô hình toán học. Các thuật giải gán bước sóng khác nhau có thể làm việc với LLR-MSM. Giả sử ta có tuyến ngắn nhất cho yêu cầu kết nối R. Nếu gọi Z là tập k tuyến ngắn nhất này thì . Thuật toán định tuyến LLR được cho thuật giải 1. Chú ý thuật giải LLR này có hai loại LLR-MMM và LLR-MSM, phụ thuộc vào hàm chi phí nào được sử dụng. Các hàm chi phí dựa trên thuật LLR xem xét ảnh hưởng của các bộ chuyển đổi bước sóng trong quyết định định tuyến. Số bộ chuyển đổi là có hạn và bộ chuyển đổi giúp tháo gỡ ràng buộc liên tục bước sóng, vì vậy dễ tìm được một kênh rỗi trên tuyến có các bộ chuyển đổi h