Phục hồi mạng và phân bổ lại tài nguyên

CHƯƠNG III PHỤC HỒI MẠNG VÀ PHÂN BỔ LẠI TÀI NGUYÊN 3.1 Các khái niệm 3.1.1 Phục hồi Phục hồi là một phương thức sử dụng các tài nguyên dự phòng khả dụng để định tuyến lại lưu lượng sau khi xảy ra sự cố, theo tình trạng khi đó của mạng. Ở chương II ta đã nói tới vấn đề bảo vệ. Điểm phân biệt giữa hai phương thức bảo vệ và phục hồi là: các kỹ thuật bảo vệ dựa trên các kịch bản để xác định tuyến /đoạn bảo vệ cho mỗi tuyến /đoạn hoạt động cần bảo vệ trước khi xảy ra sự cố, còn các kỹ thuật phục hồi sử dụng các thuật toán định tuyến để tìm một tuyến /đoạn dự phòng khả dụng thay thế tạm thời cho tuyến /đoạn hoạt động bị ảnh hưởng sau khi xảy ra sự cố. Do đó các kỹ thuật bảo vệ thường đáp ứng thời gian hồi phục nhanh hơn các kỹ thuật phục hồi động nhưng bù lại các kỹ thuật phục hồi cho phép sử dụng các tài nguyên dự phòng mềm dẻo hơn. Như ta đã biết môi trường WDM được chia thanh 3 lớp; lớp kênh quang (OCh-Optical Channel), lớp đoạn ghép kênh quang (OMS- Optical Multiplex Section) và lớp đoạn truyền dẫn quang (OTS – Optical Transmisstion Section). Tương ứng với mỗi lớp ta có các cách phục hồi riêng biệt. Phương thức phục hồi kênh quang: phương thức này yêu cầu thay thế mỗi tuyến quang hoạt động bị ảnh hưởng bởi sự cố bằng một tuyến quang bảo vệ. Việc tìm tuyến bảo vệ có thể được thực thi băng điều khiển phân tán hoặc tập trung. Trường hợp áp dụng điều khiển tập trung, một nút điều khiển lưu giữ bản ghi trạng thái của mạng và tìm các tuyến bảo vệ rồi thông báo cho các nút mạng. Trường hợp áp dụng điều khiển phân tán, cả nút nguồng và đích sẽ rà soát động các bước sóng bảo vệ được yêu cầu để thiết lập lại tuyến đường bị đứt. Phương thức phục hồi đoạn ghép kênh quang: phương thức này yêu cầu tìm kiếm cục bộ một tuyến tạm thời khả dụng vòng qua đoạn bị sự cố. Phương thức này được thực thi tại các nút đầu cuối đoạn bị sự cố, sử dụng một thuật toán phân bổ để tìm tuyến thay thế tạm thời. Điểm phân biệt giữa phục hồi kênh quang và phục hồi đoạn ghép kênh quang là ở mức bảo vệ hay đơn vị bảo vệ. Trường hợp thứ nhất lấy đối tượng bảo vệ là tuyến quang nên bảo vệ kênh quang được gọi là bảo vệ tuyến, nó cho phép lựa chọn hồi phục các sự cố kết cuối đường dây quang (OLT). Trường hợp thứ hai lấy đối tượng bảo vệ ở mức tín hiệu tổng là tín hiệu ghép kênh của các kênh WDM truyền trên mỗi sợi quang nên bảo vệ đoạn ghép kênh còn được gọi là bảo vệ đoạn, nó sẽ hồi phục tất cả các tuyến quang hiện được mang trên đoạn sợi bị sự cố. Các kỹ thuật phục hồi quang có thể được thực thi ở mức kênh quang áp dụng cho cấu hình lưới với các nút OXC. Hiện nay trên thị trường chưa cung cấp các thiết bị OXC có hiệu năng cao nhưng một số nhà sản xuất đang phát triển các thiết bị kết nối chéo quang - điện được thiết kế đặc biệt cho phục hồi phân tán nhanh. Trong một hệ thống mạng viên thông có thể xảy ra các sự cố như; đứt đường truyền giữa hai nút mạng; sự cố tại nút mạng. Từ các sự cố này ta có ba phương pháp phục hồi mạng: phục hồi từ đầu cuối - tới - đầu cuối của tuyến hoạt động, phục hồi tại các nút kế cận với sự cố, và phục hồi tại nút trung gian. 3.1.1.1 Phục hồi đầu cuối - tới - đầu cuối Hình 3.1 Mô tả phục hồi đầu cuối-tới-đầu cuối đối với sự cố đoạn liên kết Đường kết nối giữa hai nút Tuyến hoạt động trước khi xảy ra sự cố Tuyến hoạt động sau khi xảy ra sự cố Hình 3.2 Mô tả phục hồi đầu cuối-tới-đầu cuối đối với sự cố nút Đường kết nối giữa hai nút Tuyến hoạt động trước khi xảy ra sự cố Tuyến hoạt động sau khi xảy ra sự cố Khi xảy ra sự cố thì phương pháp phục hồi này sẽ thực hiện định tuyến lại từ các nút đầu cuối của các kênh bị ảnh hưởng bởi sự cố. Phương pháp phục hồi này đảm bảo hiệu quả như nhau đối với cả sự cố nút và sự cố đoạn liên kết 3.1.1.2 Phục hồi tại nút kế cận sự cố Hình 3.3 Mô tả phục hồi tại nút kế cận Đường kết nối giữa hai nút Tuyến hoạt động trước khi xảy ra sự cố Tuyến hoạt động sau khi xảy ra sự cố Khi xảy ra sự cố thì phương pháp phục hồi này sẽ thực hiện định tuyến lại cho các kênh đi trên đoạn nối giữa hai nút kế cận với sự cố đoạn, phương pháp phục hồi này không hồi phục được lưu lượng trong trường hợp sự cố nút 3.1.1.3 Phục hồi tại nút trung gian Tuyến quang trước khi xảy ra sự cố Tuyến quang sau khi xảy ra sự cố Hình 3.4 Mô tả phục hồi tại nút trung gian đối với sự cố đoạn Đường kết nối giữa hai nút Tuyến hoạt động trước khi xảy ra sự cố Tuyến hoạt động sau khi xảy ra sự cố Khi xảy ra sự cố thì phương pháp phục hồi này sẽ thực hiện định tuyến lại các kênh bị ảnh hưởng bởi một sự cố giữ bất kỳ cặp nút trung gian nào. Phương pháp phục hồi này sử dụng dung lượng dự phòng rẩt hiệu quả vì nó cho phép định tuyến lại kết nối một cách tối ưu mà không có các ràng buộc như hai phương pháp trên, nhưng yêu cầu thuật toán phức tạp hơn. Trong các phương pháp phục hồi trên thì phương pháp phục hồi tại các nút biên thường cho đáp ứng tuyến phục hồi dài hơn so với phương pháp phục hồi tại nút kế cận sự cố. Tuy vậy phương pháp thứ hai lại yêu cầu phải tập trung nhiều dung lượng dự phòng gần các vị trí dễ gặp sự cố dẫn đến tổng dung lượng dự phòng mà nó yêu cầu cao hơn trong khi phương pháp đầu có thể lập kế hoạch dung lượng dự phòng vừa đủ để hồi phục các sự cố đơn phù hợp với qui mô mạng. Về khả năng khắc phục sự cố thì tất cả các phương pháp phục hồi đều áp dụng được cho một sự cố chặng. Riêng phương pháp phục hồi tại nút kế cận sự cố không có khả năng đối phó với sự cố nút. Về thời gian hồi phục thì phương pháp phục hồi tại nút kế cận sự cố có thể sử dụng ở mức đoạn ghép kênh quang (OMS), liên tới it nút hơn và thường cho tuyến đương phục hồi ngắn hơn nên đáp ứng hồi phục nhanh hơn. Dưới đây là bảng so sánh các phương pháp phục hồi Phương pháp phục hồi Nút kế cận sự cố Nút biên Dung lượng dự phòng yêu cầu Nhiều hơn Ít hơn Khả năng khắc phục sự cố Tồi hơn Tốt hơn Thời gian hồi phục Ngắn hơn Dài hơn Bảng 3.1 So sánh các phương pháp phục hồi 3.1.2 Cấp phát tài nguyên Phân bổ lại tài nguyên là một vấn đề cần thiết trong xây dưng, vận hanh và khai thác mạng, đặc biệt là khi khôi phục sự cố. Đối với các mạng quang, đặc biệt là mạng quang WDM thì phân bổ lại tài nguyên là rất quan trọng. Nó gồm cấp phát sợi quang, bước sóng, thiết bị WDM và thiết bị đầu cuối. Từ kết quả xử lý sẽ ước tính sược số lượng bước sóng và các thành phần mạng cần bổ sung. Hoạt động cấp phát một kết nối kênh quang cho các cáp và các sợi quang không có gì mới lạ đối với các nhà lập kế hoạch xây dựng mạng SDH trước đây, nhưng việc gán một bước sóng cho một kênh quang, định tuyến các bước sóng quang là một nhiện vụ mới khá phức tạp. Nếu mạng được hỗ trợ biến đổi bước sóng (sử dụng các bộ phát đáp hay bộ biến đổi bước sóng) thì vấn đề này được giải quyết đơn giản nhưng lại làm tăng chi phí xây dựng nút mạng. Do đó khi cấp phát tài nguyên cho các mạng WDM có hai khía cạnh cần phải xem xét Một là các hệ thống WDM thường được thiết kế với số lượng bước sóng xác định hưu hạn. Hai là vấn đề xung đột bước sóng có thể xảy ra nếu các kênh quang khác nhau hoạt động ở cùng bước sóng trên cùng một sợi. Vì hai vấn đề này mà các nhà thiết kế phải tối thiểu hoá số lượng bước sóng sử dụng để không vượt quá dung lượng của hệ thống WDM và tránh được xung đột bước sóng. Khi xem xét vấn đề cấp phát bước sóng cần biết rõ mạng có hỗ trợ biến đổi bước sóng hay không, từ đó có ba trường hợp cấp phát bước sóng: Cấp phát tuyến bước sóng ảo ( Virtual Wavelength Path - VWP): bước sóng được cấp phát có thể thay thế trên tuyến đường tơi nút đích. Trường hợp này tương tự như hoạt động cấp phát tài nguyên trong các mạng SDH Cấp phát tuyến bước sóng (Wavelength Path - WP): chỉ cấp phát một bước sóng duy nhất dọc theo tuyến đường từ nút nguồn tới nút đích. Trường hợp này dẫn đến nguy cơ xung đột bước sóng giữa hai tuyến chia sẻ cùng một sợi quang. Cấp phát tuyến bước sóng đường hầm (Tuneable Wavelength Path - TWP): cấp phát cố định hai bước sóng khác nhau cho các tuyến hoạt động và hồi phục. Phương pháp này là phương pháp trung gian của của hai phương pháp trước. Khi xem xét về đặc điểm lưu lượng tải trên mạng (tải tĩnh hay tải động ) chúng ta có hai cách thức cấp phát tài nguyên tương ứng: Cấp phát tài nguyên với lưu lượng tải tĩnh: có thể được thực hiện một lần hoặc theo kế hoạch nhiều chu kỳ (lưu lượng tải dự báo khá chính xác ở các thời điểm). Trong cả hai trường hợp lưu lượng đều có khuynh hướng tăng lên và có thể áp dụng các công cụ tối ưu để dự báo sự tăng trưởng này. Cấp phát tài nguyên với lưu lượng tải động (trong trường hợp lưu lượng tải bất định): lưu lượng dự báo chỉ có thể thống kê, ví dụ cường độ lưu lượng tối đa được mong đợi hay mức độ tập trung lưu lượng trong một ring. Người thiết kế phải làm sao đáp ứng được mức độ mềm dẻo của mạng cao nhất với chi phí thấp nhất. 3.1.3 Các phương thức thực thi cấp phát tài nguyên Sử dụng các thuật toán tối ưu: cách này có thể rất chậm nhưng thích hợp với các mạng lớn, lưu lượng tĩnh và nói chung cần dự báo lưu lượng chính xác. Chúng có thể được dùng để nghiên cứu so sánh các kiểu mạng khác nhau, phân tích mức độ nhạy cảm để đưa ra những kết quả có giá trị. Sử dụng các luật thiết lập kế hoạch đơn giản: cách này có thể thích ứng ngay cho thưc thi và vận hành các mạng thực tế (ví dụ khi cài đặt dung lượng mới cần định tuyến cho các nhu cầu mới). 3.1.4 Cấp phát tài nguyên trong các kỹ thuật bảo vệ mạng Trong mạng thông tin quang WDM vấn đề cấp phát tài nguyên cho mục đích bảo vệ lưu lượng và hồi phục mạng sau khi xảy ra sự cố rất quang trọng, có ý nghĩa quyết định đến việc lập dự án xây dựng mạng quang, dự tính chi phí và xác định cấu hình mạng khả thi. Hiện tại có ba trường hợp cấp phát tài nguyên sau. Chúng được phân biệt dựa trên số lượng bước sóng yêu cầu bổ sung cho mục đích bảo vệ. 3.1.4.1 Bảo vệ trên chính bước sóng của thực thể được bảo vệ (khi chỉ có các nút WR) Phân tập sợi quang: bằng cách tăng gấp đôi tài nguyên cần thiết để truyền tải lưu lượng mạng. Cách bảo vệ 1+1 này đảm bảo hồi phục 100% các sự cố tuyến nhưng không đảm bảo hồi phục các sự cố nút. Phân tập đường định tuyến: đối với mỗi đường định tuyến sẽ dành một đường định tuyến khác cho mục đích bảo vệ, để tối ưu hoá về mặt tài nguyên mạng thì việc xác định hai đường khác nhau với cùng bước sóng cho mỗi cặp nút phải được thưc hiện trong pha cấp phát tài nguyên bảo vệ. Cách này có thể bảo vệ mạng chống lại các sự cố trên đoạn, tuyến và tại các nút trung gian. Bảo vệ dựa trên ring: xác định các vòng ring tự bảo vệ trên mạng cấu hình lưới. Cách này cho phép sử dụng các kỹ thuật bảo vệ chia sẻ giống như bảo vệ ring SDH. Lập kế hoạch để các ring đi qua các nút trong mạng với các yếu tố ràng buộc (như độ trễ, số lượng các nút, và chiều dài tuyến...) 3.1.4.2 Bảo vệ trên các bước sóng khác nhau (trường hợp có sẵn các nút WC) Với cách này cho phép dùng các kỹ thuật bảo vệ riêng hay chia sẻ, và tối ưu hoá toàn bộ tài nguyên mạng theo cách: ban đầu dùng các WL chưa bị chiếm dụng sau đó thực hiện phân tập sợi quang. Điều này được thực hiện trong pha lập kế hoạch cấp phát tài nguyên mạng. Nếu muốn cung cấp bảo vệ trên cả sợi quang khi bị đứt thì kênh bảo vệ không nên ở trên cùng một sợi quang với kênh được bảo vệ. 3.1.4.3 Bảo vệ trên các tuyến đa bước sóng (trường hợp các nút WR khả dụng) Hình thức này dùng để tối ưu hoá tàon bộ tài nguyên mạng khi không có sự hạn chế về WL trên tuyến. Ban đầu sử dụng các bước sóng chưa bị chiếm dụng sau đó mới áp dụng phân tập sợi quang. Công việc này có thể thực hiện trong pha lập kế hoạch cấp phát tài nguyên mạng. Tương tự trương hợp trên để tránh ảnh hưởng khi bị đứt cáp kênh bảo vệ không nên chia sẻ cùng một sợi quang với kênh được bảo vệ. 3.2 Phân bổ lưu lượng trong quá trình hồi phục mạng Đầu tiên chúng ta nghiên cứu về vấn đề cấp phát tài nguyên với lưu lượng tải tĩnh trong các cấu hình ring, lưới, sau đó là vấn đề cấp phát tài nguyên với lưu lượng tải động trong cấu hình ring. Trong các trường hợp nghiên cứu, lưu lượng giả thiết là các khối. Một khối là một yêu cầu truyền tải thông tin giữa hai nút mạng quang trên một bước sóng. Khối quang có thể được định tuyến từ đầu cuối - tới - đầu cuối trên một bước sóng suốt tuyến đường đi hoặc trên các bước sóng khác nhau nếu sử dụng bước sóng. 3.2.1 Định tuyến lưu lượng và cấp phát tài nguyên cho các mạng quang WDM với lưu lượng tĩnh Phần này trình bày về cấp phát tài nguyên bước sóng cho các mạng WDM cấu hình ring có lưu lượng tĩnh thưo ba nhóm sau: nhóm ring WDM bảo vệ riêng, nhóm ring WDM bảo vệ chia sẻ và nhóm ring WDM không bảo vệ. Các ring WDM bảo vệ riêng đơn hướng hoặc hai hướng có các kênh quang hoạt động được bảo vệ đối phó với sự cố đứt cáp bởi các kênh bảo vệ dành riêng truyền ở hướng đối diện của ring. Do các kênh hoạt động và bảo vệ có thể cùng chia sẻ một bước sóng ở các hướng truyền dẫn khác nhau trên ring nên vấn đề cấp phát tài nguyên rất đơn giản, ta có thể cấp phát một bước sóng cho mỗi nhu cầu khối. Ví dụ trường hợp một ring WDM với N nút có đủ N*(N-1)/2 khối thì số lượng bước sóng yêu cầu trên ring WDM hai sợi bảo vệ riêng là N*(N-1)/2. Tương tự với ring WDM đơn hướng không bảo vệ, cả hai hướng truyền dẫn cho mỗi khối sử dụng một bước sóng trên tất cả các tuyến vòng quanh ring. Các ring WDM bảo vệ chia sẻ (thường là ring hai hướng, đôi khi cũng áp dụng định tuyến đơn hướng cho một số khối): khi cáp đứt tại một cung nó vân có đủ dung lượng dự phòng trên phần cùng bù để hồi phục cho nhưng khối quang bị đứt kết nối (ví dụ OMS - SPRing). Các ring WDM hai hướng không bảo vệ: nhiệm vụ bảo vệ có thể được chuyển lên các tầng khách sử dụng dung lượng trên chính ring đó hoặc trên các phần khác của mạng nhưng không cần dành riêng bất kỳ bước sóng nào cho mục đích bảo vệ. Các ring này cho phép tái sử dụng bước sóng để truyền các khối quang khác nhau nên về lý thuyến chúng yêu cầu ít bước sóng hơn. Nhưng bù lại các khối quang phải được định tuyến chính xác và được cấp phát các bước sóng sao cho đảm bảo khả năng tái sử dụng tối đa. Nếu các nút có hỗ trợ biến đổi bước sóng thì vấn đề trở nên đơn giản: nhưng nếu các nút sử dụng bộ ghép kênh xen/rẽ thụ động thì không có khả năng biến đổi bước sóng cho các kênh lưu lượng truyền qua, do đó mỗi nhu cầu quang phải được cấp phát một bước sóng từ đầu cuối - tới - đầu cuối khiến cho công việc này trở lên phức tạp. Khi đó phải tìm ra một phương thức cấp phát bước sóng tối ưu mà chỉ được sử dụng một số lượng bước sóng hạn chế như trong trường hợp có hỗ trợ biến đổi bước sóng. Ví dụ trường hợp ring WDM hai sợi bảo vệ chia sẻ có N nút, ta chỉ được yêu cầu [(N2 – 1)/4] bước sóng, khi số N lớn giá trị này gần bằng 50% so với trường hợp bảo vệ riên. Đối với ring bốn sợi bảo vệ chia sẻ hoặc ring WDM hai hướng không bảo vệ thì số lượng bước sóng yêu cầu là [(N2 - 1)/8] mà yêu cầu hỗ trợ biến đổi bước sóng thì không thích hợp. Nhìn chung nhu cầu lưu lượng hiếm khi đạt tới mức tối đa nhưng về lâu dài cần thiết phải tìm ra các công thức chung hoặc các luật cấp phát bước sóng đơn giản. Để tối thiểu hoá việc sử dụng các bước sóng rất cần các thuật toán cho đáp ứng nhanh. Trong thực tế đã áp dụng một luật cấp phát tài nguyên khá tốt theo hai giai đoạn liên tiếp sau. Giai đoạn một (giai đoạn định tuyến): định tuyến các khối quang để truyên cùng chiều hoặc ngược chiều kim đồng hồ nhằm tối thiểu hoá tổng số bước sóng sử dụng trên mỗi đoạn (với giả thiết có hỗ trợ biến đổi bước sóng). Các nhu cầu quang (các khối) đã được cấp nhiều bước sóng có thể được tách ra, và mỗi bước sóng được định tuyến riêng nếu yêu cầu. Sau đó sử dụng một thuật toán đáp ứng nhanh sẵn có để định tuyến tối ưu nhằm đạt được số lượng các bước sóng trên mỗi đoạn là ít nhất có thể. Giai đoạn hai: giai đoạn cấp phát bước sóng cho các tuyến đã được xác định khi kết thúc giai đoạn một: ta có thể sử dụng các thuật toán Stochastic hay các thuật toán phong đoán nhằm đạt được hiệu quả phân bổ tất cả các bước sóng như mong muốn . Giai đoạn đầu nhằm tạo ra một mức ngưỡng số lượng các bước sóng yêu cầu thấp hơn mà chưa xét tới việc không có hỗ trợ biến đổi bước sóng. Giai đoạn hai thực thi cấp phát bước sóng theo giới hạn đó 3.2.2 Định tuyến lưu lượng và cấp phát tài nguyên cho các mạng quang WDM với lưu lượng tải động Trong nhiều ứng dụng mạng thực tế không phải lúc nào cũng dự đoán được trước các mẫu lưu lượng, các nhu cầu quang (các khố) có thể tăng hoặc giảm bất kỳ nên cần thiết phải xem xét các mẫu lưu lượng động để xác định mức độ linh hoạt và hiệu quả của các mạng WDM. Các thuật toán phải thực thi định tuyến và cấp phát các bước sóng trong điều kiên lưu lượng động nên cần đảm bảo các yêu cầu sau: Đảm bảo mức độ sử dụng mạng cao mà biết nhu cầu lưu lượng ban đầu. Thuật toán vẫn đạt hiệu năng tốt ngay cả khi lưu lượng có sự biến động lớn Thuật toấn đơn giản để có thể dễ dàng liên kết giữa các mạng con của hệ thống quản lý mạng. Phần này ta sẽ xem xét lưu lượng động trong các mạng ring WDM bảo vệ chia sẻ với kịch bản như sau. Một ring kết nối N nút, ban đầu chưa có nhu cầu quang (khối) nào được định tuyến Các nhu cầu quang xuất hiện lần lượt và yêu cầu được phục vụ ngay lập tức. Các yêu cầu này xuất hiện ngẫu nhiên với xác suất như nhau giữa các nút trên ring, nên phải tính toán dựa trên trung bình mẫu lưu lượng toàn phần. Khi có một nhu cầu quang yêu cầu phục vụ phải tìm thấy ngay một bước sóng khả dụng. Hiệu nắng tái xắp xuất các bước sóng đã cấp phát cho lưu lượng trên ring phải đảm bảo mức độ sử dụng mạng cao hơn, nhưng vơi kỹ thuật ring WDM hiện nay yêu cầu xem xét cả khả năng can thiệp nhân công và đứt kênh dịch vụ khách hàng do không cho phép tai sắp xếp. Nếu có hiện tượng dao động lưu lượng có thể loại bớt các nhu cầu quang (trên các phần ring sử dụng) và bước sóng đã cấp phát cho nhu cầu quang bị laọi đó sẽ trở thành khả dụng đối với các nhu cầu quang mới có thể được địng tuyến trên phần ring đó. Có một số luật cấp phát tài nguyên liên quan tới hoạt động định tuyến và cấp phát bước sóng: thuật toán tìm đường ngắn nhất (SP), thuật toán tìm số lượng bước sóng it nhất. Để so sánh ta xem xét các ring WDM có hỗ trợ biến đổi bước sóng luôn nhằm định tuyến các nhu cầu quang lên tuyến ngắn nhất. Các nhu cầu quang được tạo ra ngâu nhiên và cấp cho ring WDM sử dụng luật đã chọn cho tới khi tất cả các bước sóng được sử dụng. Khi xảy ra hiện tượng tắc nghẽnthì phải tính toán lại các nhu cầu đã được phục vụ thành công. Để thấy được mức cấp phát tài nguyên tối ưu đạt được ta sử dụng một số công cụ cấp phát tài nguyên tĩnh thử thực hiện trên cùng các khối quang đó, nếu thức thi tốt hơn thì có thể có nhiều bước sóng khả dụng hơn. Vấn đề dao động tải động có ảnh hưởng xấu tới mạng ring WDM như hiện tượng phân mảnh trong ổ cứng của máy tính. Trong hiện tượng phân mảnh của máy tính thì nó xảy ra do ta tạo rồi lại xoá các tập tin, còn vấn đề dao động tải thì do các nhu cầu quang bị loại ngẫu nhiên khỏi ring WDM để lại một không gian bước sóng bị phân mảnh, dung lượng thừa được phân bố vòng quanh ring trên các bước sóng khác nau nhưng lại không có một bước sóng nào hoàn toàn khả dụng hết một vòng ring. Các tài nguyên khả dụng phân tán này lại được dùng để cấp phát cho các nhu cầu mới cần được định tuyến qua một số nút mà không được hộ trợ biến đổi bước sóng nên tất kho khăn. Ngược lại nếu hỗ trợ biến đổi bước sóng ta có thể dễ dàng tận dụng dung lượng thừa trên một vài bước sóng để định tuyến cho một nhu cầu quang. Một kết luận quan trọng là nếu mạng ring WDM có dao động tải cao, bảo vệ chia sẻ có thể đạt kết quả sử dụng thấp. Ngược lại các ring WDM bảo vệ riêng sử dụng các luật đơn giản hơn không nhậy cảm với các dao động tải: Ưu điểm của bảo vệ chia sẻ so với bảo vệ riêng về mặt yêu cầu bước sóng có thể bù đắp nhược điểm mức sử dụng. Để thực thi thiết kế mạng đạt được hiệu quả cao ta cần định cỡ mạng thưo các mẫu lưu lượng dự báo thích hợp, lấy chi phí làm đối tượng tính toán mức khả dụng và kiểm tra khả năng linh hoạt của mạng. Điều này dựa trên lưu lượng tĩnh sử dụng một số công cụ tối ưu. Ví dụ: định cơ OMS – SPRing sử dụng chiến lược định tuyến và cấp phát bước sóng theo hai bước. Chúng ta ta đã biết OMS – SPRing có nhiêu ưu điểm về yêu cầu dải thông tốt hơn các ring WDM bảo vệ riêng cúng giống như trường hợp SDH SPRing tốt hơn SNCP ring. Khả năng hỗ trợ biến đổi bước sóng không thích hợp lắm ngoại trừ trường hợp lưu lượng động không có dự báo trước, đặc biệt khi có dao động tải cao. Đối với các mạng lưới WDM, thực hiệ tách biệt các tác vụ định tuyến và cấp phát bước sóng là đơn giản nhất. Có thể sử dụng thuật toán tìm đường ngắn nhất cho định tuyến, một thuật toán heuristic hay các công cụ dựa trên SA và ILP cho cấp phát tài nguyên. Đối với lưu lượng động ta nên chọn các mạng ring WDM bảo vệ chia sẻ là thích hợp hơn cả. Nếu không thể dự báo trước được lưu lượng, và hoạt động định tuyến không thể tái sắp xếp động mà không xét đến QoS thì nên sử dụng luật SP sẽ đạt được hiệu quả sử dụng từ 90% tới 95% (khi không có dao động tải), và giảm xuống 70%(khi có giao động tải). Điều này khiến cho các ring WDM bảo vệ chia sẻ kém hẫm dẫn hơn các ring WDM bảo vệ riêng 1+1 sử dụng các luật đơn giản hơn nhiều. 3.2.3 Phương pháp định tuyến trong mạngWDM cấu trúc Ring Tương tự trong mạng cấu Ring SDH, khi xet về tính hiệu quả sử dụng băng tần quang, hiện nay các cấu trúc ring toàn quang có thể chia thành hai loại chủ yếu: Ring bảo vệ dùng chung SPRing (OMS-SPRing - Optical Multiplex Section Shared Protection Ring), tương ứng với công nghệ SDH có MS- SPRing hay ring hai hướng. Ring bảo vệ dành riêng DPRing (OCH/OMS DPRing – Dedicated Protection Ring hay OCH-SNCP Ring – Sub-Network Connection Protection Ring) tương ứng với công nghệ SDH là loại SNCP Ring hay Ring đơn hướng USHR. Trong loại ring bảo vệ dành riêng DPRing (1+1) tại lớp quang, luồng tín hiệu quang được gửi đi theo cả hai hướng của vòng ring để bảo vệ. Nguyên tắc cơ bản để phân bổ bước sóng là: mỗi một luồng quang điểm - điểm sẽ sử dụng một bước sóng riêng trên toàn ring. Mức độ phức tạp trong thiết kế mạng với cấu trúc DPRing sẽ không nằm ở phần quang mà chủ yếu ở phần giao diện quang và VC-4. Ví dụ, xác định sự xắp xếp logic các nút tốt nhất (cấu hình lớp SDH), hoặc cách ghép các VC-4 vào bước sóng là cần thiết. Đối với ring bảo vệ dùng chung SPRing, yêu cầu định cỡ phức tạp hơn. Nhà thiết kế phải quyết định hướng tuyến thuận/ngược chiều kim đồng hồ cho mỗi lưu lượng và sử dụng bước sóng nhất định nào đó. Do cơ chế bảo vệ dùng chung cho phép sử dụng bước sóng trên các luồng quang không chồng chéo nhau, nên sẽ không có nguyên tắc thiết kế đơn giản nào. Hơn nữa nhiệm vụ phân bổ các VC-4 vào từng bước sóng sẽ làm cho bai toán phức tạp hơn trong vòng ring có bảo vệ dùng chung. Phần này sẽ tập trung vào định tuyến và phân bổ bước sóng cho SPRing đáp ứng yêu cầu lưu lượng luồng quang đã xác định, mà không đề cập đến vấn đề nhóm, phân bổ các luồng VC-4 vào kênh quang – đây là phần quyết định của lớp mạng trên và thường thuộc nhà khai thác khác, độc lập với nhà khai thác mạng quang. Trong vấn đề phân bổ tài nguyên dự phòng nói chung là rất khó. Nhưng trong trường hợp cấu hình ring thì với loại DPRing mỗi một kênh OCh làm việc sẽ yêu cầu kênh bảo vệ theo hướng đối diện, và với cấu trúc loại SPRing, thì một nửa phần bước sóng trên mỗi chặng được sử dụng cho kênh bảo vệ và nửa còn lại sử dụng cho dự phòng. Về nguyên tắc khi có sự cố xảy ra phần bước sóng làm việc bị sự cố sẽ chuyển sang phần bảo vệ ở hướng ngược lại, do đó cần có chuyển đổi bước sóng. Tuy nhiên có thể tránh sử dụng chuyển đổi bước sóng nhờ bố trí hai hai phần bước sóng dành cho làm việc và dự phòng của hai sợi bù nhau. Ngoài ra, vấn đề định cơ cho mạng DPRing hoàn toàn phải được thông qua phương pháp tính đơn giản, bởi vì mỗi lưu lượng quang sẽ yêu cầu sử dụng một bước sóng trên mỗi chặng của ring (cho kênh bảo vệ và làm việc). Vì vậy dễ dàng định tuyến và gán bước sóng cho DPRing trong trường hợp ma trận lưu lượng quang có bảo vệ hoàn toàn. Tuy nhiên. DPRing có thể tải các lưu lượng quang không có bảo vệ; nhưng lưu lượng này sẽ làm cho phức tạp hơn khi định cỡ các DPRing. Đối với trường hợp này bài toán lại quay về giải bài toán SPRing. Do vây trong phần này chỉ cần tập trung về vấn đề định cỡ SPRing. 3.2.3.1 Định tuyến trong mạng ring đơn Định tuyến. Nhiệm vụ của bước này rất quan trọng, nó xác định định tuyến lưu lượng thuận hoặc ngược chiều kim đồng hồ với giả định có bộ chuyển đổi bước sóng. Bước này có thể giải cho cho kết quả gần hoặc tối ưu băng thuật toán tối di truyền (Genetic), Heuristic hoặc sử dụng thuât toán tối ưu, để xác định hướng tuyến của mỗi luồng lưu lượng. Có hai loại phương pháp phổ biến được sử dụng để định tuyến lưu lượng cho SPRing, đó là: Các phương pháp Heuristic. Heuristic thích nghi. Heuristic không thich nghi. Các phương pháp tối ưu. a) Các phương pháp định tuyến Rất nhiều nhà nghiên cứu trước đã đề xuất vài phương pháp định tuyến tối ưu cho mạng SPRing. Ý tưởng của các phương pháp này là tối thiểu chi phí ring bằng cách tối thiểu tải trọng trên chặng có tải cao nhất, trong đó tải là tổng các lưu lượng định tuyến qua chặng đó. Hầu hết các thuật toán đều phải giải quyết vấn đề cân bằng tải trọng, đó là các luồng quang được sắp xếp trên ring sao cho sự chênh lệch về tải giữa các chặng càng nhỏ càng tốt. Một trong những thuật toán được C.Y.Lee và S.G.Chang đề xuất và đã chỉ ra kết quả là tối ưu hoặc nhiều nhất là lớn hơn giá trị tối ưu một đơn vị (N=[LMAX/2]+1). * Bài toán Xét vòng ring có n nút (n cạnh/cung/chặng). Các nút được đánh số theo chiều kim đồng hồ và cạnh giữa nút I và i+1 gọi là ai. Cạnh giữa nút n và l là an. Mỗi một lưu lượng giữa hai nút là đối xứng và hai hướng. Ký hiệu: d = (d1, d2, d3, …dm) là véc tơ lưu lượng trong đó dj là tổng số luồng của lưu lượng j = {as, as+1, . . .at-2, at-1} là tập các cạnh mà tải lưu lượng j giữa nút s và t (t ≤ n) theo hướng kim đồng hồ = {as, as+1, . . .an, an-1, . . .at+1, at} là tập các cạnh mà tải lưu lượng j giữa nút s và t(t ≤ n) ngược chiều kim đồng hồ 1 nếu aj Î P(i, 2j-1) = 0 nếu aj Ï 1 nếu aj Î P(i, 2j) = 0 nếu aj Ï P là ma trận n×2m, trong đó: x là véc tơ kết quả, trong đó: là số luồng của lưu lượng j được định tuyến theo chiều kim đồng hồ là số luồng của lưu lượng j được định tuyến ngược chiều kim đồng hồ R là ma trận (n×2m) lưu lượng của cạnh, trong đó y là véc tơ tải với là tải trên cạnh được xác định là = z(x) = maxi {} là tải lớn nhất trong các cạnh ứng với kết quả x A ={ai/ yi ≥ z(x)-1} là tập các cạnh có tải cực đại nhỏ hơn 1 Bài toán cân bằng tải có thể được biểu diễn như sau: Tối thiểu hàm mục tiêu z(x). Thoả mãn điều kiện: với với , nguyên dương với mọi Hàm mục tiêu z(x) nhận được từ định tuyến và của mỗi lưu lượng sao cho tải lớn nhất là tối thiểu. Ràng buộc thứ nhất chỉ ra là tải của cạnh là tổng tất cả các lưu lượng định tuyến qua cạnh ai ở cả hai hướng (ngược /thuận chiều kim đồng hồ), ràng buộc thứ hai chỉ ra lưu lượng được định tuyến cả hai hướng phải bằng dj, còn ràng buộc thứ ba là việc tách lưu lượng theo 2 hướng phải nguyên dương. Để giải bài toán này Lee và Chang đề xuất thuật toán sau: Bước 1: khởi tạo x := (d1,0,d2,0, . . .,dm,0); Tính toán y, z(x),A; đặt :=1; Bước 2: kiểm tra điều kiện : nếu sai thì kết thúc Tạo danh sách các lưu lượng bắt nguồn từ nút và sắp xếp theo thứ tự giảm dần của giá trị , tức là luồng lưu lượng có số cạnh/chặng giảm dần. Gọi lưu lượng j:=lưu lượng đầu tiên trong danh sách của nút i Bước 3: lặp lại với bước này với điều kiện A(tức là xét các luồng jmà được định tuyến đi qua tất cả các cạnh có tải cực đại). Đặt Đặt ; (chia luồng lưu lượng j sao cho mỗi hướng có tải tương tự nhau) Tính toán lại y, z(x), A Chọn lưu lượng j:=lưu lượng tiếp theo trong danh sách Bước bốn: đặt i:=i+1 rồi thực hiện bước hai. Theo ông Chang và Lee đã chỉ ra, lời giải là tối ưu hoặc nhiều nhất là lớn hơn tối ưu một đơn vị. Thuật toán: Y Y Y Bắt đầu Sắp xếp dsd theo thứ tự tăng của s và d; j >n :=định tuyến các lưu lượng bắt đầu từ nút i; Đánh giá tải y=(y1, y2,…,yn ); Xác định tập A; Kết thúc drq: đi qua tất cả các cạnh thuộc A x:= x*; Chọn drq có số cạnh lớn nhất; x*:=định tuyến drq theo hướng ngược lại; Đánh giá tải y=(y1, y2,…,yn ); Xác định lại tập A: Hình 3.4 Lưu đồ giải bài toán tối ưu b) Các phương pháp định tuyến Heuristic Mặc dù bài toán định tuyến trên SPRing hoàn toàn có thể giải bằng một trong các thuật toán tối ưu ở trên, tuy nhiên một số thuật toán Heuristic cũng được sử dụng. Các thuật toán này có một số đặc điểm: Đơn giản hơn loại tối ưu mà vẫn cho kết quả tối ưu hoặc gần tối ưu trong hầu hết các trường hợp. Dễ dàng hơn cho việc duy trì liên tục giữa các quá trình lập qui hoạch và thiết lập luồng trong khai thác Các phương pháp Heuristic có thể được đưa thành hai nhóm, thích nghi và không thích nghi. *Các phương pháp định tuyến Heuristic không thích nghi Các thuật toán này tuân theo những qui tắc đơn giản và cố định khi quyết định hướng định tuyến thưo từng một lưu lượng một. Chúng được gọi là không thích nghi là bởi vì các qui tắc định tuyến là không thay đổi trong toàn bộ quá trình định tuyến. Có ba kiểu qui tắc định tuyến cơ bản sau: Luôn luôn định tuyến lưu lượng theo hướng có khoảng cách nhỏ nhất Luôn luôn định tuyến lưu lượng theo hướng có số chặng it nhất Luôn luôn định tuyến lưu lượng theo hướng có tải ít nhất Trong ba nguyên tắc định tuyến trên thì hai phương pháp đầu là tương tự nhau: mỗi lưu lượng quang hai hướng giữa hai nút của ring được định tuyến theo hướng hoặc là ngắn nhất hoặc có số chặng ít nhất. Ưu điểm chính của các nguyên tắc này là tính đơn giản, ngoài ra chúng cung cho kết quả rất tốt. Trong trường hợp ring có số nút là lẻ thì có thể xảy ra số chặng giữa hai nút như nhau, do vậy nguyên tắc số chặng ít nhất không thể quyết định được hướng tuyến cho các nút này. Trong trường hợp này hướng định tuyến có thể chọn ngẫu nhiên hoặc theo hướng định trước hoặc là định tuyến theo hướng có các chặng có tải ít hơn. Mặc dù các nguyên tắc tối thiểu khoảng cách/chặng rất phù hợp đối với ma trận lưu lượng quang có dạng Mesh hoàn toàn, nhưng chúng lại không phù hợp trong trường hợp tổng quát. Sự phân bố lưu lượng loại này thể hiện sự mất cân bằng tải lớn trên ring và khi đó cần thêm các tuyến phụ. Nguyên tắc tải tối thiểu: Mỗi lưu lượng luôn luôn định tuyến thưo hướng có tải nhỏ nhất (nghĩa là trên hướng có các chặng có tải nhỏ hơn) Lưu lượng hai hướng được định tuyến trên cùng một phía của ring (trên hai sợi khác nhau) Khi mà cả hai phía của ring có cùng độ tải, thì hướng có số chặng ngắn nhất được chọn Trong nguyên tắc này luôn cố gắng giữ cân bằng tải trên ring. Nguyên tắc này rất nhạy cảm với thứ tự chọn luồng để định tuyến và yêu cầu tài nguyên cao hơn nhiều so với kết quả tối ưu khi mà có các “cụm” lưu lượng quang giữa cùng cặp nút được định tuyến theo các cụm khác. Thực ra các lưu lượng quang có thể được định tuyến theo các hướng luân phiên (tức là, ban đầu là thuận chiều kim đồng hồ, tiếp ngược, thuận, ngược …) và có xu hướng là cùng yêu cầc về tài nguyên như DPRimg. Vấn đề xác định thứ tự định tuyến tối ưu các lưu lượng đã được xem như là NP - đầy đủ. Giải pháp có lẽ đơn giản, hiệu quả theo Heuristic để giải quyết bài toán này, là ngăn không cho xuất hiện các “cụm” lưu lượng quang bằng cách trộn các thứ tự các lưu lượng trước khi định tuyến. Theo cách này có thể nhận được: Tiết kiệm tài nguyên mạng so với DPRing cho các mẫu lưu lượng quang nói chung Sự tiết kiệm này có thể cao hơn nếu sử dụng các kỹ thuật trộn “thông minh” thứ tự các luồng được xét trong định tuyến Kỹ thuật trộn “thông minh” trước hết phải tránh các “cụm” lưu lượng quang và có hướng ưu tiên định tuyến các luồng quang dài nhất (tức là các lưu lượng giữa các cặp nút có khoảng cách chặng cao hơn) **Các phương pháp định tuyến Heuristic thích nghi Các thuật toán này tuân theo nguyên tắc đơn giản cố định để quyết định hướng định tuyến từng luồng quang một, trừ khi có sự kiện thiếu tài nguyên. Sự kiện này cho phép thay đổi chính sách định tuyến. Các thuật toán này được gọi là “thích nghi” bởi vì nguyên tắc định tuyến của chúng có thay đổi trong quá trình định tuyến . Nguyên tắc định tuyến thích nghi điển hình đó là chọn tuyến có hướng chặng tối thiểu, ngoại trừ khi chúng ta gặp phải thiếu tài nguyên trên ring. Điều này có nghĩa là thông tin về các bước sóng còn cho phép sử dụng trên mỗi chặng của mỗi ring cần xác định trước khi thực hiện quyết định định tuyến của luồng quang. Vì thông tin này chỉ có thể có sau khi quá trình phân bổ bước sóng, do đó chúng ta phải ghép hai chức năng định tuyến và gán bước sóng. Thuật toán thích nghi được đề xuất có bản chất kế thừa tính chất phụ thuộc vào thứ tự lưu lượng được định tuyến như thuật toán tải tối thiểu không thích nghi. Cách xử lý tương tự về trộn thứ tự luồng quang như đề xuất ở trên cũng có thể áp dụng ở đây. 3.2.3.2 Định tuyến trong mạng đa ring Khi thiết kế mạng quang có cấu trúc đa ring (phổ biến hiện nay ở Việt Nam), như ví dụ hình 3.5. Vị trí của các ring và cách kết nối chúng có ảnh hưởng rất lớn đến sử dụng bước sóng và sợi trong mạng. Đây là bài toán phức tạp, trong thực tế việc đặt các ring trong mạng ở đâu là do vị trí địa lý, topo, các mẫu lưu lượng và yêu cầu quản lý. Cách kết nối và cơ chế định tuyến giữa các ring phụ thuộc vào chi phí và phân cấp của mạng . A D C B Hình 3.5 Mạng cấu trúc theo đa ring Ngoài việc xác định định tuyến và phân bổ bước sóng lưu lượng trên từng ring, chúng ta se đối mặt với vấn đề định tuyến lưu lượng giữa các ring trog mạng quang có cấu trúc đa ring. Đối với cấu trúc này cần xác định: Mạng cấu trúc đa Ring có phân cấp hay không? Nếu trong mạng đa ring có phân cấp, thì ở lớp trên cùng sẽ có 1 hay nhiều các ring và câu hỏi đặt ra là định tuyến sẽ được thực hiện như thế nào giữa các ring ở lớp trên này Tiêu chuẩn định tuyến nào áp dụng giữa các ring Có chuyển đổi bước sóng, trạm lặp 3R, sắp xếp lại luồng ở lớp điện giữa các ring hay không? Các ring kết nối với nhau có cùng hay khác cấu trúc (DPRing hay SPRing)? Các ring được kết nối với nhau thông qua một hay nhiều nút? Trong trường hợp kết nối nhiều nút, thì cơ chế bảo vệ nào cho phép các lưu lượng được định tuyến thông qua các nút kết nối (Gateway) khác khi có sự cố? Một số công cụ đã được phát triển để tối ưu vị trí của các ring SDH trong mạng nhưng do bài toán rất phức tạp và phải xét đến một tập lớn các vị trí và khả năng kết nối ring, cho nên các công cụ này cũng không thể đưa ra kết quả tối ưu và nhanh đối với các mạng lớn Các công cụ này cũng phù hợp với thiết kế mạng ring quang và chỉ cần bổ xung, sửa đổi cho phù hợp với các đặc trưng của công nghệ quang. Trong đó, bài toán điển hình là phân bổ tài nguyên cho các ring đơn cần được giải với các thuật toán thích hợp trong quá trình định cỡ mạng đa ring Trong phần này ta sẽ mở rộng bài toán phân bổ luồng trong định cỡ mạng đa ring và chủ yếu tập chung vào cấu trúc mạng có các ring kết nối với nhau qua một nút mạng. Tiếp sau đây, chúng ta sẽ chỉ rõ các bước phổ biến trong việc lập qui hoạch mạng đa ring và mô tả nhiệm vụ bài toán phân bổ luồng quang trong mạng này và đề xuất phương án giải quyết. Mô tả bài toàn: Bước 1 - xác định vị trí các ring và các điểm kế nối Bước 2 - phân bổ và định tuyến lưu lượng cho mạng ring và nguyên tắc kết nối giữa các ring Bước 3 - Xác định luồng quang (gán bước sóng )cho từng mạng ring. Bước này có thể dùng các thuật toán ở chương trước Bước 4 - Xác định cấu hình và tài nguyên mạng. Trong phần này sẽ đề xuất phương pháp phân bổ luồng quang bao gồm bước 2 và 3 ở trên, ứng dụng trong quá trình lập qui hoạch mạng quang WDM với cấu trúc đa ring. Về nguyên tắc thì việc kết nối giữa các ring thông qua càng nhiều nút càng tốt. Tuy nhiên, trong thực tế số lượng nút kết nối giữa các ring phụ thuộc vào vị trí địa lý, quản lý và chi phí toàn mạng. Do vậy thông thường các ring được kết nối với nhau thông qua một nút hoặc hai nút ở gần nhau. Do đó việc phân bổ luồng quang giữa các ring thông qua một nút hoặc hai nút ở gần nhau là không khác nhau nhiều. Trong thời điểm hiện nay để cho đơn giản ta chỉ xét trường hợp các ring kết nối với nhau thông qua một nút trung gian Tương tự như cách tiếp cận phân bổ luồng cho mạng Ring đơn ,việc phân bổ luồng cho mạng đa Ring cũng được thực hiện theo hai bước : Định tuyến các lưu lượng trong và giữa các ring để xác định định tuyến cụ thể của từng lưu lượng quang trên mạng đa ring Phân bổ hay gán bước sóng cho các luồng quang Bài toán tổng thể cho phân bổ luồng trong mạng đa ring có thể mô tả như sau: Đầu vào Cấu hình mạng (lớp vật lý) Cấu trúc mạng đa ring: bao gồm các ring, điểm kết nối và ma trận lưu lượng. Cơ chế kết nối, bảo vệ các ring. Đầu ra Định tuyến lưu lượng trên mạng Gán bước sóng cho các luồng lưu lượng đã định tuyến Với cách tiếp cận giải hai bước thì vấn đề phân bổ luồng trong mạng đa ring chỉ còn là xác định cơ chế định tuyến các lưu lượng giữa các ring như thế nào. Bởi vì vấn đề định tuyến và gán bước sóng cho phần lưu lượng thuộc một ring đã được giải quyết nhờ các thuật toán như đã đề cập ở trên 3.2.4 Phương pháp định tuyến trong mạng quang WDM cấu trúc Mesh 3.2.4.1 Định tuyến cố định Cách tiếp cận đơn giản để định tuyến một kết nối là luôn lựa chọn một tuyến cố định như nhau cho một cặp nguồn-đích. Một ví dụ điển hình của cách tiếp cận này là định tuyến ngắn nhất cố định. Đường ngắn nhất tính cho mỗi cặp nguồn đích được tính trước (offline) sử dụng thuật toán đường ngắn nhất chuẩn như Dijkstra hoặc Bell-Ford. Do đó nút mạng không cần thiết lưu giữ toàn bộ trạng thái mạng. Bất kỳ kết nối nào giữa cặp các nút riêng được thiết lập sử dụng tuyến được xác định trước. Trong hình 3.6 đường ngắn nhất cố định minh họa từ nút 0 đến nút 2. Cách tiếp cận để thiết lập các kết nối này rất đơn giản, tuy nhiên sự bất lợi của cách tiếp cận này là nếu tài nguyên (bước sóng) dọc theo các đường bị tắc nghẽn, nó có thể có khả năng dẫn đến xác suất tắc nghẽn cao trong trường hợp lưu lượng động hoặc dẫn đến cần một số lượng lớn các bước sóng sử dụng trong mạng trong trường hợp lưu lượng tĩnh. Định tuyến cố định cũng không thể điều khiển các tình huống có sự cố trong một hay nhiều các tuyến sợi nào đó trong mạng. Để điều khiển các sự cố tuyến sợi, việc tổ chức định tuyến lại phải xem xét các đường lựa chọn tới đích hoặc phải có khả năng tìm thấy một tuyến động. Chý ý rằng trong hình 3.6, một yêu cầu kết nối từ nút 0 đến nút 2 sẽ bị khóa nếu bước sóng chung không thể sử dụng trên cả hai tuyến sợi trong tuyến cố định. 1 2 5 4 3 0 Hình 3.6 Đường ngắn nhất cố định 3.2.4.2 Định tuyến luân phiên cố định Một cách tiếp cận để xem xét định tuyến đa đường là định tuyến luân phiên cố định. Trong định tuyến luân phiên cố định, mối nút trong mạng được yêu cầu duy trì một bảng định tuyến chứa các danh sách chỉ thị của một số các tuyến cố định tới mỗi nút đích. Ví dụ, những nút này có thể bao gồm tuyến đầu tiên ngắn nhất, tuyến ngắn thứ hai nhất, tuyến ngắn thứ ba nhất….Một tuyến chính giữa một nút nguồn s và một nút đích d được định ra là tuyến đầu tiên trong danh sách các tuyến tới nút d trong bảng định tuyến tại nút s. Một tuyến thay thế giữa nút s và nút d là bất kỳ tuyến nào mà nó không dùng chung bất kỳ tuyến sợi nào với tuyến đầu tiên trong bảng định tuyến tại s. Thuật ngữ “tuyến thay thế “ cũng để thực hiện mô tả tất cả các tuyến (bao gồm cả tuyến chính ) từ một nút nguồn tới một nút đích. Hình 3.7 môt tả tuyến kết nối chính (đường liền) từ nút 0 đến nút 2, và tuyến thay thế (đường chấm) từ nút 0 đến nút 2. 1 2 5 4 3 0 Hình 3.7 Định tuyến luân phiên cố định Tuyến chính Tuyến thay thế Khi một kết nối yêu cầu đến, nút nguồn thử thiết lập kết nối liên tiếp trên mỗi tuyến từ bảng định tuyến đến khi có một tuyến với bước sóng gán hợp lệ. Nếu không có tuyến nào có thể dùng được từ danh sách các tuyến thay thế thì yêu cầu kết nối bị tắc nghẽn hoặc hủy. Trong hầu hết các trường hợp, các bảng định tuyến tại mỗi nút được chỉ thị bằng số các chặng tới đích. Như vậy tuyến ngắn nhất tới đích là đường đầu tiên trong bảng định tuyến. Khi có các ràng buộc về khoảng cách giữa các tuyến khác nhau, một tuyến có thể được lựa chọn ngẫu nhiên. Định tuyến thay thế cố định cung cấp điều khiển dễ dàng cho thiết lập và giải phóng các luồng quang và nó cũng có thể được sử dụng để tránh sự cố mạng. 3.2.4.3 Định tuyến thích nghi 1 2 5 4 3 0 1 1 1 ∞ 1 ∞ 1 1 Hình 3.8 Định tuyến thích nghi từ nút 0 đến nút 2 Trong định tuyến thích nghi, một tuyến từ một nút nguồn s đến một nút đích d được lựa chọn động phục thuộc vào trạng thái mạng. Trạng thái mạng được xác định bởi tập tất cả các kết nối hiện tại. Một loại định tuyến thích nghi là định tuyến đường chi phi ít nhất, nó là cách định tuyến tốt cho mạng có sử dụng chuyển đổi bước sóng. Với cách tiếp cận này, mỗi tuyến sợi được sử dụng có chi phí bằng ∞ và mỗi tuyến sợi sử dụng chuyển đổi bước sóng sẽ có chi phí là c đơn vị. Nếu chuyển đổi bước sóng không có thì c = ∞. Khi một kết nối đên, đường chi phí thấp nhất giưax nút nguồn và nút đích sẽ được xác định. Nếu có nhiều tuyến có cùng chi phi, một trong chúng sẽ được lựa chọn ngẫu nhiên. Bằng cách lựa chọn chi phi chuyển đổi bước sóng c thích hợp, chúng ta có thể đảm bảo rằng các tuyến có chuyển đổi bước sóng chỉ được lựa chọn khi không đảm bảo các đường bước sóng liên tục. Định tuyến thích nghi yêu cầu hỗ trợ mở rộng các giao thức điều khiển và quản lý để cập nhật liên tục các bảng định tuyến tại các nút. Ưu điểm của định tuyến thích nghi là có kết quả tắc nghẽn thấp hơn định tuyến cố định và định tuyến thay thế cố định. Với mạng trong hình 3.8, các tuyến sợi (1,2) và (4,2) trong mạng bận thì thuật toán định tuyến thích nghi có thể thiết lập qua một kết nối giữa nút 0 và nút 2. Trong khi cả hai định tuyến cố định và định tuyến thay thế cố định với các tuyến như hình 2.7 sẽ bị tắc nghẽn Một dạng khác của định tuyến thích nghi là định tuyến trên luồng có tắc nghẽn ít nhất (LCP- Least-Congested path).Giống định tuyến thay thế, với mỗi cặp nguồn-đích, một danh sách các tuyến được lựa chọn trước. Khi một yêu cầu kết nối đến, luồng tắc nghẽn ít nhất trong số các tuyến xác định trước được lựa chon. Sự tắc nghẽn trên một tuyến sợi được đo bằng số các bước sóng có thể sử dụng. 3.2.4.4 Định tuyến bảo vệ Khi thiết lập các kết nối trong một mạng cố định tuyến ghép kênh bước sóng sóng quang WDM, yêu cầu cung cấp một số mức độ bảo vệ tuyến sợi và nút để tránh sai hỏng trong mạng bằng cách dự trữ một số lượng dung lượng dự phòng [14,21]. Một cách tiếp cận phổ biến để bảo vệ là thiết lập 2 tuyến luồng quang phân tập mức luồng. Một luồng gọi là luồng chính cho sử dụng còn luồng kia được gọi là luồng quang dự phòng để hồi phục cho luồng quang chính bị hỏng. Cách tiếp cận này có thể hỏng, các đường chính và đường thay thế cũng có thể là phân về nút. Định tuyến thay thế cố định cung cấp một cách tiếp cận để thực hiện điều khiển bảo vệ. Bằng cách lựa chọn các đường thay thế phân tập với tuyến chính, ta có thể bảo vệ kết nối với bất cứ các sai hỏng tuyến sợi đơn nào bằng cách phân bổ một trong các đường thay thế là một đường hồi phục. Trong định tuyến thích nghi, có thể bổ sung một giải pháp bảo vệ có thể được trong các đường hồi phục nào đó để thiết lập ngay sau khi đường chính đã được thiết lập. Giao thức định tuyến có thể được sử dụng để xác định đường hồi phục, với việc loại trừ một bằng cách thiết lập c = ∞ nó đang được sử dụng trên đường chính. Việc sử dụng tuyến thay thế để phục hồi được xác định động sau khi sai hỏng xảy ra. Sự phục hồi sẽ chỉ thành công nếu đủ tài nguyên có thể sử dụng được trong mạng. Chú ý rằng, khi một sai hỏng xảy ra, việc tìm kiếm và thiết lập động của một đường phục hồi dưới cách tiếp cận hồi phục có thể mất thời gian đang kể so với chuyển mạch trên các đường hồi phục thiết lập trước theo cách tiếp cận bảo vệ (protection). 3.3 Kết luận Công nghệ WDM đem lại nhiều cơ hội cho các nhà khai thác mạng, giảm chi phí/bit và tăng dung lượng đáp ứng nhu cầu phát triển trong nhiều năm tới. Tuy nhiên, khi đưa công nghệ mới vào ứng dụng thì sẽ có nhiều thách thức cho việc ứng dụng hiệu quả các đặc tính tiên tiến mà vẫn duy trì được tính liên tục trong phát triển mạng lưới. Hiện nay, thực tế việc ứng dụng WDM chủ yếu trong mạng truyền tải với cấu trúc mạng định tuyến quang sẽ đáp ứng các lưu lượng kết nối điểm - điểm tốc độ cao. Do vậy thách thức trước mắt đối với các nhà lập quy hoạch và thiết kế mạng cần quyết định thời điểm và lựa chọn các cấu trúc mạng quang WDM phù hợp. Để giải quyết các vấn đề này trong quy hoạch mạng, thì một trong những bài toán đặc trưng điển hình của công nghệ WDM(so với công nghệ SDH) đó là phân bổ luồng quang trong mạng, bao gồm định tuyến và gán bước sóng cho các luồng lưu lượng trên mạng WDM vật lý. Do tầm quan trọng của bài toán này mà hiện có rất nhiều đề tài nghiên cứu và tìm ra các giải pháp mới phù hợp với những yêu cầu của từng bối cảnh cụ thể của mạng lưới: từ lưu lượng tĩnh tới lưu lượng động, ngẫu nhiên; từ các giải thuật ngoại tuyến đến trực tuyến xử lý tập trung và phân tán; từ lưu lượng song công đối xứng tới lưu lượng đơn công và bất đối xứng; từ không có chuyển đổi bước sóng đến có hay hạn chế chuyển đổi bước sóng; từ không có không có ràng buộc về độ dài trong suốt đến các rang buộc như nhiễu, xuyên âm, mức công suất.