Đề tài Phương pháp định tuyến, mô phỏng bài toán định tuyến và gãn bước sóng dựa trên kỹ thuật gmpls

iển phải có độ mềm dẻo về mặt chức năng và cung cấp các điều kiện hoạt động về cấu hình. 1.5.6 Kiến trúc các thành phần của mặt phẳng điều khiển GMPLS 1.5.6.1 Yêu cầu của mặt phẳng điều khiển Mặt phẳng điều khiển và mặt phẳng số liệu hoạt động đảm bảo độ tin cậy là vấn đề sống còn đối với mạng quang. Mặt phẳng điều khiển phải được thiết kế sao cho khi xảy ra các sự cố thì các kết nối cũng không bị ảnh hưởng. Và ngay cả khi các kết nối bị hỏng trong trường hợp mặt phẳng số liệu có sự cố thì mặt phẳng điều khiển cũng phải có khả năng định tuyến lại. Nhìn chung mặt phẳng điều khiển GMPLS cần: Có khả năng đáp ứng cho tất cả các mạng chuyển mạch gói và mạng chuyển mạch kênh như IP, ATM, OTN, SONET/SDH. Đủ linh hoạt để thích nghi với các kịch bản mạng khác nhau (các mô hình kinh doanh của các nhà cung cấp dịch vụ). Mục tiêu này đạt được bằng cách chia mặt phẳng điều khiển thành các thành phần chức năng khác nhau. Mỗi thành phần có thể yêu cầu nhiều công cụ cho các kịch bản mạng khác nhau. Mỗi công cụ cần có khả năng cấu hình và mở rộng. Điều này cho phép các nhà cung cấp thiết bị và các nhà cung cấp dịch vụ quyết định sắp xếp logic các thành phần này, và cũng cho phép nhà cung cấp dịch vụ thực hiện các chính sách cũng như vấn đề an toàn mạng. Về mặt chức năng, mặt phẳng điều khiển GMPLS có thể chia thành các thành phần như: Khám phá tài nguyên lân cận và quản lý kết nối, định tuyến, báo hiệu. Mặt phẳng điều khiển GMPLS cần một mạng trao đổi số liệu để tạo các bản tin điều khiển. Nó có các giao diện cho mặt phẳng quản lý và phần tử mạng như bộ điều khiển hệ thống, cơ cấu chuyển mạch. 1.5.6.2 Mạng thông tin số liệu hỗ trợ mặt phẳng điều khiển GMPLS Mặt phẳng điều khiển GMPLS bao gồm các bộ điều khiển phân tán để trao đổi và phối hợp với nhau nhằm hoàn tất các hoạt động kết nối. Mạng thông tin số liệu (DCN) cần thiết để trao đổi các bản tin điều khiển giữa các bộ điều khiển. Đối với mạng IP truyền thống, không có mặt phẳng điều khiển riêng vì điều khiển và lưu lượng số liệu User dùng chung một mạng. Đối với các mạng mạch, cần một mạng số liệu độc lập vì một chuyển mạch kênh điển hình không xử lý lưu lượng User trong mặt phẳng truyền tải của nó. Để mặt phẳng điều khiển GMPLS có khả năng đáp ứng các mạng mạch, khái niệm DCN phải được giới thiệu. DCN hỗ trợ mặt phẳng điều khiển GMPLS có thể sử dụng các loại môi trường vật lý: Lưu lượng điều khiển có thể được truyền qua một kênh thông tin trong số các liên kết mạch mang số liệu giữa các LSR. Chẳng hạn môi trường có thể là các byte tiêu đề SONET/SDH hoặc OTN. Lưu lượng điều khiển có thể được truyền qua kênh thông tin riêng, chia sẻ cùng liên kết vật lý với các kênh số liệu. Chẳng hạn, môi trường có thể là bước sóng riêng, một STS-1 hoặc một DS-1. Lưu lượng điều khiển có thể truyền qua một liên kết thông tin riêng giữa các LSR, riêng biệt so với các liên kết mang số liệu. Chẳng hạn môi trường có thể là một LAN riêng biệt hoặc một liên kết điểm-điểm. Các yêu cầu mặt phẳng điều khiển GMPLS đối với DCN Các hoạt động của mặt phẳng điều khiển GMPLS phụ thuộc nhiều vào DCN khi trao đổi các bản tin điều khiển. Do đó, DCN phải đáp ứng các yêu cầu sau: DCN hỗ trợ mặt phẳng điều khiển GMPLS cũng phải hỗ trợ IP. DCN phải cung cấp thông tin (trực tiếp hoặc gián tiếp) giữa bất kỳ hai LSR nào cần trao đổi lưu lượng điều khiển DCN phải an toàn: Yêu cầu này xuất phát từ hai khía cạnh định tuyến và báo hiệu. Thực tế, thông tin định tuyến được trao đổi qua mặt phẳng điều khiển là đặc trưng của nhà cung cấp dịch vụ. Nhà cung cấp dịch vụ không muốn tiết lộ các thông tin trong mạng ra ngoài biên mạng của họ, thậm chí cho chính các khách hàng của họ. Trong khi đó, mạng mặt phẳng điều khiển phải ngăn chặn tất cả tấn công của các dịch vụ kết nối. DCN phải tin cậy và cung cấp khả năng chịu đựng lỗi. DCN là hệ thống truyền tải cho các bản tin mặt phẳng điều khiển GMPLS. Nếu DCN lỗi, không bản tin GMPLS nào được trao đổi giữa các bộ điều khiển GMPLS. Độ tin cậy của DCN phải được đảm bảo ngay cả khi mạng truyền tải dịch vụ có các lỗi nặng xảy ra. DCN phải hỗ trợ chức năng ưu tiên phát chuyển bản tin. Quá trình thựchiện tổng thể của mặt phẳng điều khiển GMPLS phụ thuộc nhiều vào việc truyền tải các bản tin điều khiển của chúng. Các hoạt động nhạy cảm với thời gian như chuyển mạch bảo vệ cần đảm bảo QoS ở mức cơ bản. Hơn nữa, việc truyền các bản tin cần được đảm bảo hoặc khôi phục nhanh chóng ngay cả khi mạng có sự cố DCN cần có khả năng mở rộng, nâng cấp: Độ thực hiện của DCN không nên phụ thuộc vào kích cỡ mạng v. mặt phẳng điều khiển hỗ trợ mạng có thể được mở rộng khi triển khai mạng mới Việc phối hợp hoạt động DCN mặt phẳng điều khiển là bước đầu tiên để hướng đến tích hợp mặt phẳng điều khiển. Nhu cầu cần có một kiến trúc DCN mặt phẳng điều khiển chung và ngăn xếp giao thức để mặt phẳng điều khiển của các mạng khác nhau có thể thông tin với nhau. Tách riêng mặt phẳng điều khiển và mặt phẳng truyền tải Mặt phẳng điều khiển GMPLS không nên có bất cứ giả định nào về loại môi trường vật lý sử dụng cho DCN của nó, mà cần hàm ý rằng mặt phẳng điều khiển GMPLS và mặt phẳng truyền tải của nó cần phải tách nhau ra, ít nhất cũng về mặt logic. Điều này ảnh hưởng đến thiết kế mặt phẳng điều khiển GMPLS ở một số khía cạnh: DCN mặt phẳng điều khiển có thể có một topo vật lý khác so với mạng truyền tải của nó Việc khám phá tài nguyên lân cận mặt phẳng điều khiển có thể cần phải phụ thuộc các cơ chế khác với việc khám phá lân cận dựa trên DCN. Giao diện điều khiển và truyền tải có thể được tách riêng nhau. Do đó, hai mặt phẳng điều khiển gần nhau không yêu cầu phải có một kênh điều khiển trực tiếp miễn là chúng trao đổi được với nhau qua DCN. Điều này hàm ý rằng việc định tuyến các bản tin mặt phẳng điều khiển trong DCN mặt phẳng điều khiển được tách về mặt logic so với định tuyến các LSP trong mặt phẳng truyền tải. Khả năng hoạt động của mặt phẳng điều khiển và mặt phẳng truyền tải cần duy trì độc lập nhau. Điều này yêu cầu tách biệt giữa các thông báo và các mã trạng thái cho mặt phẳng điều khiển và mặt phẳng truyền tải. Trong trường hợp sự cố mặt phẳng điều khiển (chẳng hạn lỗi kênh thông tin hoặc lỗi thực thể điều khiển), các hoạt động kết nối LSP mạch mới có thể không được chấp nhận nhưng các kết nối đã tồn tại sẽ không bị hỏng. Các bản tin báo hiệu không nhất thiết truyền dọc theo đường số liệu. Vì thế một số khái niệm cơ bản trong MPLS cần định nghĩa lại trong một phạm vi lớn hơn. Cả báo hiệu dựa trên IP và các giao thức định tuyến cần phải được tăng cường để phù hợp với sự thay đổi này. 1.5.7 Báo hiệu trong GMPLS Báo hiệu là một trong các chức năng quan trọng của mặt phẳng điều khiển GMPLS. Các chức năng cơ bản bao gồm: Tạo LSP, loại bỏ LSP, thay đổi LSP, thông báo lỗi LSP, xử lý lỗi LSP, khôi phục LSP. Để tạo ra giao thức báo hiệu mặt phẳng điều khiển GMPLS hiệu quả và tin cậy, cần tuân thủ một số nguyên tắc cơ bản. 1.5.7.1 Các chức năng cơ bản Mặt phẳng điều khiển GMPLS giả sử hỗ trợ các mạng IP và mạng truyền tải. GMPLS cần thừa hưởng những giao thức báo hiệu của MPLS, chẳng hạn như tạo LSP, xoá LSP,... Ngoài ra, giao thức báo hiệu GMPLS còn một số yêu cầu khác. Vì mạng truyền tải mang lượng băng tần khổng lồ và hỗ trợ nhiều ứng dụng, một sự cố về mạng như đứt cáp sẽ gây ra hậu quả rất nghiêm trọng. Việc phát hiện lỗi và khôi phục LSP nhanh trở thành yêu cầu cơ bản đối với mạng truyền tải. Tóm lại, báo hiệu mặt phẳng điều khiển GMPLS cần hỗ trợ: Tạo LSP Xoá LSP Thay đổi LSP Khôi phục LSP Xử lý loại bỏ LSP Tạo LSP Hoạt động tạo LSP bắt đầu khi nút GMPLS đầu vào nhận một yêu cầu LSP. Nút này thường thực hiện các quá trình cấp phép chính gồm điều khiển tiếp nhận và kiểm tra tài nguyên. Nếu cấp phép được xác nhận, nút GMPLS vào cần chọn một đường cho LSP với các thông tin có thể và bắt đầu quá trình. Một bản tin tạo LSP sẽ chuyển từ nút vào và di chuyển dọc theo đường được chọn. Trong mạng truyền tải, một bản tin xác nhận được yêu cầu từ nút ra đến nút vào. Đối với LSP hai hướng, bản tin bắt tay ba hướng sẽ cung cấp trong giao thức báo hiệu để thực hiện cả hai phía của quá trình thiết lập LSP. Trong khi tạo LSP, tài nguyên có thể được cấp phát trước hoặc sau khi toàn bộ đường đã được đăng ký trước. Xoá LSP Khi LSP không cần nữa hoặc LSP mà mạng đã loại bỏ, tài nguyên do các LSP này sở hữu cần được giải phóng. Một bản tin yêu cầu xoá được tạo ra trong giao thức báo hiệu. Hoạt động xoá có thể bắt đầu từ một nút GMPLS bất kỳ, báo hiệu xoá cần được thiết kế sao cho xử lý được ba trường hợp. Trong mạng truyền tải, LSP được xoá từng phần sẽ gây phức tạp. Trong khi xoá LSP, một nút GMPLS lỗi dọc theo LSP sẽ dẫn đến không hoàn thành được việc xoá LSP. Một bản tin xác nhận xoá do nút đề xuất xoá yêu cầu để đảm bảo đã hoàn tất thủ tục xoá. Trong hoạt động xoá, có thể xuất hiện các tình trạng chạy đua giữa bản tin yêu cầu xoá và việc cấp phát lại tài nguyên. Dựa vào tình trạng này, các cảnh báo có thể xuất hiện tại các nút dọc theo LSP. Để hỗ trợ một môi trường như vậy, cần một cơ chế để cho phép hoặc không các cảnh báo kết hợp với LSP trước để cấp phát lại tài nguyên. Có hai giải pháp để tránh tình trạng này: Các nút dọc theo đường sẽ thông báo cơ cấu LSP, gần như tín hiệu ASP SONET. Các nút dọc theo đường sẽ được khai báo nhờ một phần trong bản tin xoá. Sau khi xác nhận, chúng sẽ cấp phát lại tài nguyên. Thay đổi LSP Một LSP có thể yêu cầu được thay đổi các đặc tính của nó, chẳng hạn như băng tần. Yêu cầu cơ bản của việc thay đổi LSP được gọi là “thay đổi trước khi không đáp ứng được” (made - before – break). Giao thức báo hiệu cần được thiết kế để hỗ trợ chức năng này. Một giải pháp thực hiện được có thể bao hàm việc chia sẽ tài nguyên giữa LSP cũ và LSP mới. 1.5.7.2 Hỗ trợ phục hồi Phục hồi nhanh các sự cố mạng là một khía cạnh rất quan trọng của mạng truyền tải hiện tại và tương lai. Các nhà cung cấp mạng truyền tải yêu cầu khả năng phục hồi nhanh để đảm bảo độ tin cậy và tính sẵn sàng cho các kết nối của khách hàng. Việc chọn chính sách phục hồi cần có sự cân bằng giữa việc sử dụng tài nguyên mạng và thời gian gián đoạn dịch vụ. Các sơ đồ phục hồi khác nhau hoạt động với sự cân bằng khác nhau giữa các yêu cầu dung lượng dư và thời gian ngắt dịch vụ. Lược đồ phục hồi GMPLS cần bao gồm ít nhất là bảo vệ tuyến, bảo vệ đường riêng, khôi phục đường dùng chung, định tuyến lại động. 1.5.7.3 Hỗ trợ xử lý loại trừ Các mức khác nhau của việc loại trừ có thể xuất hiện trong mạng GMPLS ở cả mặt phẳng số liệu và mặt phẳng điều khiển. Một số loại trừ cần xem xét trong thiết kế báo hiệu GMPLS gồm: Nút vào, nút trung gian, nút ra có thể từ chối việc tạo LSP. Nếu tài nguyên được cấp phát trước khi xác nhận LSP, việc từ chối tạo thành LSP có thể phải cấp phát lại những tài nguyên này. Một nút phát hiện sự cố của thủ tục phục hồi, việc loại trừ này sẽ dẫn đến phục hồi tuyến LSP. Nếu một quá trình phục hồi LSP lỗi, và các lý do như mặt phẳng điều khiển GMPLS dọc theo đường hồi phục có sự cố hoặc thiếu tài nguyên dọc theo đường hồi phục. Điều này có thể dẫn đến cấp phát lại các tài nguyên đã được cấp phát từng phần cho LSP hồi phục này ngay để những tài nguyên này được dùng cho việc khởi tạo và khôi phục các LSP khác. Một quá trình xoá LSP bị lỗi do lỗi mặt phẳng điều khiển dọc theo đường LSP. 1.5.7.4 Phối hợp báo hiệu Tất cả các bản tin báo hiệu không tồn tại độc lập. Những chức năng và hoạt động cần được phối hợp với nhau. Nếu không một bản tin báo hiệu có thể làm cho một bản tin báo hiệu khác không được xử lý đúng. Báo hiệu GMPLS cần phân biệt giữa thiết lập đường hoạt động và thiết lập đường phục hồi. Báo hiệu MPLS có thể thiết lập 2 LSP tách riêng liên kết/nút cùng lúc cho mỗi yêu cầu. Lưu lượng số liệu có thể được chia vào các LSP hoặc chuyển vào một đường. Một đường khác được sử dụng chỉ khi đường đầu tiên bị lỗi. Điều này có tính khả thi vì LSP thứ hai không chiếm băng tần nếu không có số liệu phát trong đường này. Trong mạng truyền tải, vấn đề lại khác. Để sử dụng hiệu quả băng tần, đường hồi phục có thể cần được thiết lập sau khi đường dịch vụ bị lỗi. Đường hồi phục được tính toán trước hoặc ngay lúc đó. Một điểm khác nữa giữa thiết lập đường hoạt động và đường phục hồi là vấn đề trễ thời gian. Cụ thể là thiết lập đường hồi phục yêu cầu trễ thời gian lâu hơn. GMPLS cần có khả năng hỗ trợ cả các LSP đơn hướng và LSP hai hướng. Các mạng viễn thông truyền thống điển hình là hai hướng. Các nghiên cứu gần đây cho thấy lưu lượng số liệu trên Internet là không đối xứng. Các LSP đơn hướng cho lưu lượng số liệu là hợp lý hơn. Mặc dù các dịch vụ dùng cả LSP đơn hướng và đa hướng hiện nay chưa xác định, giao thức báo hiệu GMPLS cần phải chuẩn bị để hỗ trợ cả các ứng dụng trong cùng một cấu trúc. Điều này tạo ra sự tranh giành nhau giữa LSP đơn hướng và LSP hai hướng cũng như giữa các LSP hai hướng từ hai hướng khác nhau. Hoạt động xoá LSP và quá trình hồi phục nhanh LSP có thể phối hợp tốt với nhau. Mặt phẳng điều khiển GMPLS là một hệ thống phân tán. Hoạt động của một nút sẽ không làm cho nút khác khó hiểu. Mặt phẳng điều khiển GMPLS có thể xảy ra sự cố. Sau khi khôi phục, giao thức báo hiệu sẽ thiết kế một số cơ chế để đồng bộ các cơ sở thông tin quản lý LSP và các tài nguyên liên kết với tài nguyên lân cận của chúng. Trong thời gian mặt phẳng điều khiển bị lỗi, LSP có thể bị xoá bỏ và tài nguyên liên kết được cập nhật. Hai giải pháp thực hiện có thể là: Sử dụng bản tin thẩm vấn lân cận để đồng bộ hoá cơ sở thông tin của nó. Sử dụng bản tin làm mới LSP để đồng bộ cơ sở thông tin của nó. 1.5.8 Các lợi ích của GMPLS GMPLS mang lại nhiều lợi ích nổi bật, thể hiện cụ thể trong các vấn đề sau: Thiết kế lưu lượng qua lớp Tích hợp việc khôi phục và bảo vệ Cung cấp dịch vụ nhanh chóng Tăng lợi nhuận Cho phép thực hiện các quá tr.nh linh hoạt, tự động và có tính mềm dẻo cao trong môi trường mạng quang tĩnh Các tiêu chuẩn mở: GMPLS có thể hoạt động trong môi trường đa nhà cung cấp thiết bị, đa lớp và đa nhà khai thác. Các mạng đồng nhất: Các mạng quang và mạng số liệu có thể được giám sát, quản lý, bảo dưỡng như một mạng đơn sử dụng một hệ thống quản lý đơn. Xử lý các sự cố và bảo dưỡng: Nhà cung cấp dịch vụ nhanh chóng cô lập và xử lý các sự cố về mạng nhờ các cảnh báo tự động của hệ thống quản lý cũng như các sự cố giữa mạng truyền tải và mạng số liệu 1.5.9 Các vấn đề còn tồn tại của GMPLS Bên cạnh những ưu điểm vượt trội của GMPLS mang lại so với các phương thức điều khiển hiện tại, nó cũng bộc lộ một số vấn đề cần dược bổ sung như: An toàn: Định tuyến IP truyền thống kiểm tra nội dụng header của gói nhận được để xác định trạm kế tiếp. Bước này tuy mất thời gian nhưng cho phép thiết lập được các firewall, và các thông tin cần thiết trong tiêu đề gói như địa chỉ đích, địa chỉ nguồn là không đổi trong cả quá trình. Ngược lại, các nhãn MPLS/GMPLS được sử dụng để thúc đẩy quá trình phát chuyển và chỉ có giá trị trong nội bộ, chẳng hạn nhãn được hiểu và sử dụng chỉ trong các thiết bị GMPLS. Những nhãn này không thể được dùng để điều khiển truy nhập hoặc cho mục đích bảo mật mạng. Chỉ một cách để thiết lập bảo mật trong mạng GMPLS là bắt buộc bảo mật truy nhập trong thời gian thiết lập kết nối, như các mạng hướng kết nối khác. Vấn đề phối hợp hoạt động: Sự thành công của GMPLS phụ thuộc vào khả năng thông tin với nhiều cơ sở hạ tầng mạng hiện tại như ATM, FR. Phối hợp hoạt động với mạng ATM và FR sẽ cho phép truyền tải các thông tin mặt phẳng số liệu và điều khiển được trao đổi giữa hai mạng giống nhau (ví dụ hai mạng ATM) thông qua một mạng khác (ví dụ GMPLS). Việc thực hiện chức năng phối hợp hoạt động giữa những mạng này gặp một số vấn đề: Phối hợp ở mặt phẳng điều khiển là rất phức tạp vì mỗi mạng sử dụng một tập các giao thức khác nhau (ví dụ định tuyến, giao diện mạng đến mạng riêng (PNNI) trong mạng ATM so với giao diện OSPF-TE trong mạng GMPLS) Chuyển mạch GMPLS có thể dựa trên gói, TDM, bước sóng, sợi, băng tần. Điều này tạo ra một vài kết hợp trong việc phối hợp mặt phẳng số liệu giữa mạng GMPLS và mạng ATM hoặc mạng FR. Một số diễn đàn công nghiệp hiện đang thực hiện một số vấn đề cụ thể về phối hợp hoạt động giữa các mạng (ví dụ MPLS Forum, ATM Forum, ...). Các giải pháp thực tế phải giúp nhà quản lý mạng quản lý cả mạng MPLS và mạng truyền thống. Những giải pháp này hiện tại vẫn chưa được xác định. Sự cân bằng mạng: Khi các tài nguyên mới được gỡ bỏ hoặc thêm vào mạng GMPLS, tập các thông tin điều khiển được trao đổi lớn hơn đối với mạng IP truyền thống. GMPLS sử dụng mô hình thiết kế lưu lượng bao gồm giới thiệu một số tham số lưu lượng, kết hợp với các liên kết số liệu, định tuyến dựa trên các ràng buộc thực hiện, LSP,...Vấn đề này tuy chưa được kiểm nghiệm tuy nhiên về mặt lý thuyết mạng MPLS/GMPLS sẽ cần thời gian tương quan lớn hơn so với một mạng IP truyền thống khi mạng bị sự cố. Hệ thống quản lý mạng: Tham số quan trọng nhất trong việc quản lý một mạng IP truyền thống, ví dụ mạng Internet là địa chỉ đến. Ngược lại, hệ thống quản lý mạng GMPLS cần lưu vết của hàng nghìn (thậm chí hàng triệu) LSP cho trạng thái hoạt động của chúng, các đường định tuyến, thiết kế lưu lượng,... Điều này dẫn đến hệ thống quản lý mạng GMPLS phức tạp hơn so với mạng Internet truyền thống. 1.6. TÓM TẮT CHƯƠNG 1 Việc sử dụng nhãn ngắn, đơn giản đã làm cho việc chuyển tiếp gói tin một cách nhanh chóng, hiệu quả. Kỹ thuật chuyển mạch nhãn đa giao thức MPLS đã kết hợp những đặc điểm nổi bật của chuyển mạch lớp 2 và lớp 3 một cách tốt nhất. GMPLS với những cải tiến và đạt được nhiều thuận lợi hơn so với MPLS. Nhờ vậy GMPLS sẽ là một công nghệ đáng được quan tâm cho việc truyền dẫn lưu lượng ngày càng cao của thế giới hiên nay. GMPLS không chỉ hộ trợ cho chuyển mạch gói như MPLS, GMPLS còn có thể gán nhãn cho bước sóng, khe thời gian… do đó, được áp dụng vào trong mạng truyền dẫn quang đường trục WDM rất tốt. GMPLS là một công nghệ mới, đã và đang được nghiên cứu để có thể áp dụng được trong thực tế. Mạng MPLS, và đặc biệt là WDM đã được triển khai trên thực tế, tạo ra một hệ cơ sở để có thể ứng dụng GMPLS khi mà lưu lượng thông tin ngày càng tăng vọt. Đây là một hướng nghiên cứu rất hay trong giai đoạn này. CHƯƠNG 2 GIỚI THIỆU BÀI TOÁN ĐỊNH TUYẾN VÀ GÁN BƯỚC SÓNG TRONG MẠNG QUANG 2.1. GIỚI THIỆU Qua một vài năm gần đây, DWDM (Dense Wavelenght Division MultIPlexing) trở thành một công nghệ chủ đạo cho mạng quang thế hệ sạu. Việc sử dụng DWDM đa kênh được phân biệt bởi các bước sóng khác nhau có thể được truyền trên một sợi quang, với mỗi kênh hoạt động ở tốc độ đỉnh của nó. Mỗi bước sóng của mỗi sợi của một tuyến liên kết là một kênh con hoàn toàn độc lập với các bước sóng khác trên cùng một sợi. Một khái niệm như vậy thường được gọi là mạng quang và mạng quang thông minh ION, đó là nơi lớp quang vật lý trở nên nhận biết được các kết nối bằng việc xác định các bước sóng của chúng. Một công nghệ điển hình của mạng DWDM và các kênh liên kết khác của nó được biết đến như các bước sóng được cho trên hình 2.1. Hình 2.1. Mạng DWDM định tuyến bước sóng [13] Trong mạng định tuyến, người sử dụng này thông tin với người sử dụng khác qua kênh toàn quang, các kênh này được xem như là các luồng quang. Một luồng quang được sử dụng để hỗ trợ một kết nối trong mạng đinh tuyến bước sóng và có thể liên kết các sợi quang. Trong trường hợp không sử dụng bộ chuyển đổi, một luồng quang chiếm cùng bước sóng trên tất cả các liên kết sợi mà nó đi qua. Đặc tính này gọi là điều kiện ràng buộc bước sóng liên tục. Giả sử rằng mỗi chuyển mạch quang được nối tới một nút truy nhập như là một nút. Khi đưa ra một tập kết nối, bài toán thiết lập các luồng quang bằng định tuyến và gán bước sóng mỗi kết nối được gọi là bài toán định tuyến và gán bước sóng (RWA- Routing and Wavelength Assignment). 2.2. CÁC LOẠI BÀI TOÁN RWA Thông thường, có hai loại lưu lượng mạng là tĩnh hoặc động. Do vậy bài toán RWA gồm hai loại tĩnh và động. Điều này dẫn đến hai kiểu thiết lập luồng quang: Bài toán thiết lập luồng quang tĩnh và thiết lập luồng quang động. 2.2.1 Thiết lập luồng quang tĩnh (SLE) Trong bài toán này tất cả các yêu cầu kết nối được biết trước và không thay đổi. Đó là yêu cầu cho việc thiết lập một tập hợp các đường quang được đưa ra đầu tiên. Các đường quang này không bị giải phóng ngay khi chúng được thiêt lập. Các đường quang được giả sử là các luồng quang, đó là ràng buộc bước sóng liên tục. Bài toán tối ưu là tối thiểu số bước sóng cho một cấu hình mạng nhất định, số sợi quang, và tập hợp các đưòng quang đã yêu cầu. 2.2.2 Thiết lập luồng quang động (DLE) Trong bài toán này tất cả các yêu cầu kết nối đến một cách động và luồng quang được giải phóng sau một thời gian hạn định. Bài toán tối ưu là tối thiểu xác suất tắc nghẽn yêu cầu cho một số bước sóng nhất định và hoặc tối thiểu giá thành mạng. Bài toán thiết lập luồng quang tĩnh có thể đạt được nhiều hơn với công nghệ hiện nay và sẽ là giải pháp tương lai gần trong mạng quang thông minh ION. Nhưng khi lưu lượng trong mạng lõi sẽ trở nên động hơn thì thiết lập luồng quang động sẽ phải được thực hiện trong mạng ION. Do vậy đồ án này sẽ tập trung chủ yếu vào việc giải quyết bài toán DLE. 2.3. CÁC PHƯƠNG PHÁP GIẢI BÀI TOÁN Bài toán RWA liên quan đến các phần khác nhau, thường được giải quyết riêng biệt để đơn giản hoá bài toán. Với bài toán định tuyến thì có ba phương pháp định tuyến cơ bản: Định tuyến cố định, định tuyến thay thế cố định và định tuyến thích nghi. Trong định tuyến cố định, chỉ có một tuyến cố định (ví dụ như đường ngắn nhất) giữa cặp nút nguồn và đích. Trong định tuyến thay thế cố định, mỗi nút duy trì một bảng định tuyến mà chứa một danh sách các tuyến cố định được yêu cầu tới mỗi nút đích. Ví dụ như, các tuyến này có thể bao gồm tuyến ngắn nhất đầu tiên, tuyến ngắn nhất thứ hai, tuyến ngắn nhất thứ ba vv.. Tuyến thực tế cho một yêu cầu kết nối chỉ có thể được chọn lựa từ tập các tuyến này. Trong định tuyến thích nghi, định tuyến dựa trên bước sóng có thể sử dụng hiện có trên mỗi tuyến liên kết. Bất kỳ tuyến khả thi nào từ nút nguồn tới nút đích có thể ứng cử như tuyến thực tế cho một yêu cầu kết nối. Việc lựa chọn tuyến phụ thuộc vào chính sách mạng được sử dụng như đường đầu tiên chi phí ngắn nhất hoặc đường đầu tiên tắc nghẽn ít nhất. Nói chung, định tuyến cố định là đơn giản nhất trong khi định tuyến thích nghi mang lại đặc tính tốt nhất. Định tuyến thay thế cố định đem lại sự thoả hiệp giữa sự phức tạp và đặc tính mạng. Bài toán gán bước sóng là một phần khác của bài toán RWA. Nói chung, nó dễ dàng hơn nhiều so với bài toán định tuyến, nhưng cũng phụ thuộc vào kết quả của giải pháp định tuyến. Tuy nhiên nó thường ảnh hưởng tới kết quả hiệu suất của giải thuật RWA. 2.4. CƠ SỞ LÝ THUYẾT 2.4.1. Giới thiệu lý thuyết đồ thị Trong lý thuyết đồ thị, cấu hình mạng có thể được biểu diễn như đồ thị G (V, E), ở đó V biểu thị tập các đỉnh (các nút mạng) và E là tập hợp các biên (Các tuyến liên kết mạng). V thể hiện số nút trong đồ thị và thường được gọi là biên độ của đồ thị. Mỗi tuyến liên kết (i, j) E có thể được kết hợp với một hàm trọng W mà biểu diễn bằng một phương pháp nào đó để xác định chi phí sử dụng tuyến liên kết (i, j). Bậc của nút iV là số nút lân cận của nút i. Đề tài chỉ xét bài toán đường đi ngắn nhất trong đồ thị. Cho đồ thị G(V, E) bài toán đặt ra là tìm đường đi trong đồ thị mà tối thiểu tổng trọng lượng của tất cả các tuyến liên kết diễn ra giữa hai đỉnh. Lý thuyết đồ thị cung cấp nhiều cách để giải quyết bài toán đó. Giải thuật phổ biến nhất là giải thuật Dijkstra và Bellman- Ford. Dưới đây chỉ giới thiệu về giải thuật Dijkstra. 2.4.2. Giải thuật DIJKSTRA Giải thuật Dijkstra được giới thiệu vào năm 1959 cung cấp một giải thuật hiệu quả nhất cho việc giải quyết bài toán đường đi ngắn nhất. Nó tìm đường đi ngắn nhất từ một đỉnh nguồn s đã cho tới mỗi đỉnh d trong V bằng việc triển khai các đường đi theo thứ tự độ dài đường đi tăng dần. Mỗi nút được dán nhãn bằng khoảng cách của nó từ nút nguồn dọc theo đường được xem là tốt nhất. Đầu tiên không đường đi nào được biết đến do vậy tất cả các nút được dán nhãn là ∞. Khi giải thuật tiến hành và các đường đi được tìm ra thì các nhãn có thể thay đổi tương ứng với các đường đi tốt hơn. Nhãn có thể là thăm dò hoặc cố định. Ban đầu tất cả các nhãn là thăm dò. Khi nó được khám phá ra mà nhãn thể hiện đường đi ngắn nhất có thể từ nguồn tới nút đó thì nó đựoc tạo cố định và không bao giờ đựoc thay đổi sau đó. 2.5. BÀI TOÁN RWA TRONG THIẾT LẬP LUỒNG QUANG TĨNH (SLE) Bài toán SLE có thể được giải như bài toán quy hoạch tuyến tính nguyên, nó là bài toán NP đầy đủ. Để giải bài toán này dễ dàng hơn, bài toán SLE có thể chia thành 2 bài toán nhỏ Định tuyến Gán bước sóng Mỗi bài toán này giải theo những cách khác nhau. Một số giải thuật gần đúng được dùng để giải bài toán SLE cho các đường mạng lớn và thuật toán tô màu đồ thị được dùng để gán bước sóng tới các luồng quang một khi các luồng quang được định tuyến đúng. Đối tượng của hàm mục tiêu là tối thiểu số bước sóng cần thiết để thiết lập một tập hợp các bước sóng nào đó ch