Đề tài Chuyển mạch nhãn đa giao thức tổng quát GMPLS

được kết hợp nhiều luồng từ các mạng biên khác nhau để đưa vào mạng cự ly dài. Đường đi đặt trước được sử dụng để đưa dữ liệu tới đích của nó. Các mạng này và các thiết bị điển hình được thể hiện trên hình 1.10. 1.5.1. NHÃN TỔNG QUAN CỦA GMPLS Để có thể hỗ trợ các thiết bị chuyển mạch trong các miền khác nhau, GMPLS đưa vào nhưng bổ sung mới cho khuôn dạng của các nhãn. Khuôn dạng nhãn mới gọi là “ nhãn tổng quát “, nó chứa thông tin cho phép các thiết bị thu lập chương trình chuyển mạch và chuyển tiếp dữ liệu bất kể cấu trúc của nó (gói, TDM, Lambda …..). Nhãn tổng quát có thể biểu diễn cho một bước sóng đơn, một sợi quang hoặc một khe thời gian. Nó cũng thể hiện các nhãn MPLS truyền thống, ví dụ như ATM, VCC hoặc shim IP. Thông tin được gắn vào nhãn tổng quát gồm: Kiểu mã hoá LSP mà thể hiện loại nhãn đang được mang (gói, bước sóng SONET…). Loại chuyển mạch thể hiện nút có khả năng chuyển mạch hoặc gói, khe thời gian, bước sóng hoặc sợi quang. 3. Bộ nhận dạng tải trọng chung để thể hiện loại tải đang được mang bởi LSP (ví dụ như nhánh ảo VT, DS-3, ATM, Ethernet, …..) Giống như MPLS, sự phân bổ nhãn bắt đầu từ LSR phía trước yêu cầu một nhãn từ LSR phía sau. GMPLS thực hiện điều này tốt hơn bằng việc cho phép LSR phía trước đề nghị nhãn cho LSP mà có thể được ưu tiên bởi LSR phía sau. 1.5.2. BỘ GIAO THỨC GMPLS Cuộc cách mạng của MPLS sang GMPLS đã mở rộng các giao thức báo hiệu (RSVP- TE, CR – LDP) và các giao thức định tuyến (OSPF-TE, IS-IS-TE). Các mở rộng thích nghi với những đặc tính của TDM/SONET và các mạng quang. Một giao thức mới, giao thức quản lý liên kết LMP (Link Management Protocol) đã được đưa vào áp dụng để quản lý và bảo trì hoạt động mặt phẳng và dữ liệu, điều khiển giữa hai nút lân cận. Giao thức quản lý liên kết LMP là giao thức dựa trên IP, bao gồm RSVP mở rộng và CR-LDP mở rộng. Ngăn xếp giao thức định tuyến IS-IS-TE giống với OSPF-TE ngoại trừ thay vì IP, một giao thức mạng phi kết nối (CLNP – Connectionless Network Protocol) được sử dụng để mang thông tin IS-IS-TE. Hình 1.10 : Ngăn xếp giao thức GMPLS 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, DDWM (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 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. 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 luận vă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. Ta 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 đó cho một cấu hình vật lý đưa ra. Bài toán thay thế bài toán tối thiểu số bước sóng trong mạng là bài toán với mục tiêu là cực đại số các kết nối có thể được thiết lập (tối thiểu số tắc nghẽn) cho một số bước sóng và các yêu cầu kết nối đưa ra. Bài toán SLE với điều kiện ràng buộc bước sóng liên tục có thể áp dụng như quy hoạch lập tuyến tính nguyên ILP (Integer Linear Program) trong đó hàm mục tiêu là tối thiểu lưu lượng trên mỗi liên kết, lần lượt nó tương ứng với tối thiểu số luồng quang qua từng liên kết riêng biệt. Thuật toán heuristic cho bài toán gán bước sóng cho một tập luồng quang tĩnh thông thường liên quan đến trình tự bước sóng, và gán cùng bước sóng cho càng nhiều luồng quang càng tốt trước khi chuyển sang bước sóng tiếp theo. Hơn nữa tập các luồng quang có thể được xếp theo thứ tự theo độ dài, để các bước sóng được gán cho các luồng quang dài hơn trước khi các bước sóng được gán cho luồng quang ngắn hơn. Tất cả các phương pháp heuristic đó chiếm rất nhiều CPU và chúng là các giải pháp không thiết thực cho thực thi bởi tính phức tạp thông thường của nó. Tiêu chuẩn xác định RWA là tối thiểu số các bước sóng cho một cấu hình mạng đã cho, số sợi quang, và tập các đường quang yêu cầu. Mặc dù đã tìm ra các giải pháp để giải quyết bài toán SLE nhưng chúng hầu như đều dựa vào những phương pháp phức tạp và do vậy không thực sự phù hợp cho những thực thi thực tế. Hơn nữa, vấn đề SLE không quan tâm đến lưu lượng động. Điều này có thể phù hợp cho mạng đường trục ngày nay; nhưng trong tương lai rất gần, việc quản lý luồng quang tự động đáp ứng các nhu cầu cho lưu lượng động phải được cung cấp. Đây là mục tiêu của các bài toán DLE mà được giới thiệu sau đây. BÀI TOÁN RWA TRONG THIẾT LẬP LUỒNG QUANG ĐỘNG (DLE) Khi các luồng quang được thiết lập và loại bỏ một cách động thì các quyết định RWA phải được thực hiện khi các yêu cầu kết nối đến mạng. Với một yêu cầu kết nối nhất định có thể tài nguyên mạng không đủ để thiết lập một luồng quang, trong trường hợp đó yêu cầu kết nối sẽ bị nghẽn. Việc kết nối cũng có thể bị nghẽn nếu không có bước sóng chung có thể sử dụng trên tất cả các tuyến dọc theo tuyến đã được chọn (ràng buộc bước sóng liên tục - WCC). Do vậy, mục tiêu trong trường hợp lưu lượng động là chọn tuyến và bước sóng mà tối đa khả năng thiết lập kết nối đã cho, trong khi cùng lúc nỗ lực tối thiểu tắc nghẽn cho các kết nối tương lai. Các thuật toán RWA động được đặc trưng bởi các tham số và thước đo điển hình phù hợp với môi trường lưu lượng động. Trong đó các yêu cầu đến và đi ra khỏi mạng xuất hiện từng yêu cầu theo một cách ngẫu nhiên. Thước đo đặc tính được sử dụng thường rơi vào một trong ba loại sau đây: Số bước sóng yêu cầu; Xác xuất tắc nghẽn kết nối (lưu lượng đưa vào) được tính bằng tỷ số giữa những kết nối bị tắc nghẽn trên tổng số các kết nối đến hoặc đi; - Số lượng tài nguyên sợi quang được nắm giữ tại các nút định tuyến (chi phí sợi quang). Giống với trường hợp luồng quang tĩnh, bài toán RWA động cũng có thể chia thành bài toán định tuyến và bài toán gán bước sóng. Phương pháp để giải quyết bài toán định tuyến có thể phân loại theo hoặc cố định hoặc thích nghi, và theo sử dụng thông tin trạng thái mạng hoặc tổng thể cục bộ. Một số phương pháp heuristic điển hình đề xuất cho bài toán này như sau: 2.6.1. BÀI TOÁN ĐỊNH TUYẾN A.Đị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 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 2.2 đường ngắn nhất cố định minh hoạ từ nút 0 đến nút 2. 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 tắc nghẽn, nó có thể dẫn đến các xác xuất tắc nghẽn cao trong trường hợp lưu lượng động hoặc dẫn đến một số lượng lớn các bước sóng đang 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 sai hỏng trong một hay nhiều các liên kết nào đó trong mạng hỏng. Để điều khiển các sai hỏng liên kết, việc tổ chức định tuyến hoặc 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. Trong hình 2.2, một yêu cầu kết nối từ nút 0 đến nút 2 sẽ bị khoá nếu một bước sóng chung không thể sử dụng trên cả hai liên kết trong tuyến cố định HÌNH 2.2: Đường ngắn nhất cố định B. Định tuyến thay thế cố định Một cách tiếp cận để xem xét định tuyến là định tuyến thay thế cố định. Trong định tuyến thay thế 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 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 thứ hai ngắn nhất, tuyến thứ ba ngắn 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ỳ liên kết nào (là liên kết độc lập) với tuyến đầu tiên trong bảng định tuyến tại nút 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 2.3 mô tả tuyến kết nối nút 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. Hình 2.3. Tuyến chính (nét liền) và tuyến thay thế (nét chấm) 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 một tuyến nối mỗi bước sóng gán hợp lệ tìm thấy. Nếu không có tuyến nào có thể dùng được tìm thấy từ danh sách các tuyến thay thế thì yêu cầu kết nối bị khoá hoặc mất. 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 đoạn liên kết sợi quang (chặng) tới đích. Như vậy đường 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 với một số mức độ lỗi chấp nhận được trên các liên kết hỏng C. Định tuyến thích nghi dựa trên thông tin tổng thể Phương pháp định tuyến thích nghi tăng khả năng xảy ra thiết lập kết nối bằng việc đưa vào tính toán thông tin trạng thái mạng. Với trường hợp thông tin tổng thể là có thể sử dụng thì các quyết định định tuyến có thể thực hiện với thông tin đầy đủ về mặt các bước sóng có thể sử dụng trên mỗi tuyến liên kết trong mạng. Định tuyến thích nghi dựa trên thông tin tổng thể có thể thực hiện hoặc bằng phương pháp tập trung hoặc bằng phương pháp phân tán. Có các loại định tuyến thích nghi sau đây: C.1. Định tuyến đường thay thế cố định Định tuyến đường thay thế dựa vào tập các tuyến cố định được quyết định trước giữa nút nguồn và nút đích. Khi yêu cầu kết nối đến thì một tuyến được lựa chọn từ tập các tuyến đã quyết định trước, và luồng quang được thiết lập trên tuyến này. Tiêu chuẩn lựa chọn tuyến thường dựa trên hoặc độ dài tuyến hoặc tắc nghẽn trên tuyến. + Lựa chọn tuyến dựa trên độ dài Ví dụ của giải thuật định tuyến dựa trên độ dài là giải thuật K đường ngắn nhất, trong đó K đường ngắn nhất được duy trì cho mỗi cặp nguồn – đích, và các đường lựa chọn theo thứ tự chiều dài từ ngắn nhất tới dài nhất. Kết nối ngắn nhất được thử trên đường ngắn nhất. Nếu tài nguyên không thể sử dụng trên đường này thì đường ngắn nhất tiếp theo sẽ được thử. + Định tuyến dựa trên tắc nghẽn đường đi Phương pháp lựa chọn tuyến dựa trên tắc nghẽn xác định tài nguyên có thể sử dụng trên mỗi đường thay thể, và chọn lựa đường mà trên đó số lượng tài nguyên lớn nhất có thể được sử dụng. Lựa chọn tuyến đường ngắn nhất chi phí tài nguyên mạng ít hơn có thể dẫn tới tải trọng cao trên một số tuyến liên kết trong mạng. Trong khi lựa chọn đường với tắc nghẽn ít nhất dẫn tới các đường dài hơn, nhưng phân bổ tải đều hơn qua mạng. C.2. Định tuyến không ràng buộc Phương pháp định tuyến thich nghi khác mà sử dụng thông tin tổng thể là định tuyến không ràng buộc. Định tuyến này xem xét tất cả các đường có thể giữa một nút nguồn và một nút đích. Để lựa chọn một tuyến tối ưu, một chi phí được gán cho mỗi đường liên kết trong mạng dựa trên thông tin trạng thái mạng hiện tại, như bước sóng có thể sử dụng được trên các tuyến liên kết. Giải thuật định tuyến chi phí ít nhất sau đó được thực hiện để tìm tuyến chi phí ít nhất. Bất cứ khi nào kết nối được thiết lập hoặc giải phóng, thì thông tin trạng thái mạng phải được cập nhật. Hai ví dụ về định tuyến không ràng buộc là định tuyến trạng thái liên kết và định tuyến vectơ khoảng cách. + Đinh tuyến trạng thái liên kiết Trong phương pháp định tuyến trạng thái liên kết phân tán, mỗi nút trong mạng phải duy trì đầy đủ thông tin trạng thái mạng. Mỗi nút sau đó có thể tìm tuyến cho yêu cầu kết nối bằng phương pháp phân tán. Bất cứ khi nào trạng thái của mạng thay đổi thì tất cả các nút phải được cung cấp thông tin. Do đó, việc thiết lập hoặc giải phóng một luồng quang trong mạng có thể dẫn tới quảng bá thông tin cập nhật tới tất cả các nút trong mạng. Nhu cầu quảng bá bản tin cập nhật có thể dẫn đến tổng chi phí điều khiển đáng kể. Hơn nữa, một nút có thể có thông tin bị lỗi thời làm cho nút thực hiện quyết định định tuyến dựa trên thông tin này không đúng. Một số khắc phục đã được thực hiện để nâng cao các giải thuật tuyến chung ngắn nhất bằng việc sử dụng đinh tuyến trạng thái liên kết. Từ đó đã chỉ ra rằng thước đo dựa trên sử dụng chặng trung gian thấp nhất và tổng hợp của tổng số bước sóng và bước sóng có thể sử dụng cho kết quả xác xuất tắc nghẽn ít nhất. Sau đây giới thiệu các thước đo hàm trọng được sử dụng trong mạng WDM có thể được sử dụng bằng giải thuật Dijkstra. Gọi là số bước sóng có thể sử dụng trên tuyến liên kết và là tổng số các bước sóng có thể trên tuyến liên kết đó. Khi đó hàm trọng dựa trên tổng số bước sóng có thể sử dụng (Total Wavelength and Avaiable – TWA) được mô tả như sau: Gọi W là hàm trọng của tuyến . Trong TWA, W được định nghĩa như sau: W= - log E Gọi P là xác xuất mà một bước sóng được sử dụng trên một tuyến liên kết. Nếu và đã biết, p có thể được tính: P = 1 - Khi xác suất mà tất cả các bước sóng sẽ được sử dụng tại một thời điểm trong tương lai có thể được viết là p. Khi đó xác xuất mà ít nhất một bước sóng có thể sử dụng được trên một liên kết trong tương lai được đưa ra bằng (1 - P) . Với một tuyến bao gồm nhiều liên kết, mục tiêu là tối đa khả năng mà một bước sóng có thể sử dụng trong tương lai, tức là cực đại giá trị (1 - P) của tất cả các liên kết có thể tạo thành tuyến. Chúng ta sử dụng – log (1 - P) như một hàm trọng tương ứng và thực hiện tối thiểu giá trị này. Đây là một hàm trọng động cho bước sóng luôn thay đổi. Định tuyến vectơ khoảng cách Phương pháp véc tơ khoảng cách có thể định tuyến với thông tin tổng thể. Phương pháp này không đòi hỏi mỗi nút duy trì đầy đủ thông tin trạng thái liên kết ở mỗi nút, nhưng thay vì mỗi nút lưu giữ một bảng chuyển tiếp dành riêng cho mỗi đích và mỗi bước sóng, chặng tiếp theo tới đích và khoảng cách tới đích. Phương pháp này dựa vào giải thuật Bellman- Ford phân tán để duy trì các bảng định tuyến. Giống với định tuyến trạng thái liên kết, bài toán cũng yêu cầu các nút cập nhật thông tin bảng định tuyến của chúng bất cứ khi nào một kết nối được thiết lập hoặc giải phóng. Việc cập nhật này được thực hiện bằng việc mỗi nút gửi một bản tin cập nhật định tuyến tới các nút lân cận chúng theo chu kỳ hoặc bất cứ khi nào trạng thái các tuyến liên kết lối ra của nút thay đổi. Mặc dù mỗi nút duy trì thông tin ít hơn định tuyến trạng thái liên kết và cập nhật không quảng bá tới tất cả các nút nhưng bài toán này có thể vẫn chịu mức độ chi phí điều khiển cao. Giải thuật vectơ cũng rất hay ở chỗ, bằng một số cách nó có thể thực hiện định tuyến ràng buộc dựa trên số chặng và các loại thước đo khác nhau. Thực vậy, các giải thuật định tuyến tiêu chuẩn thường tối ưu một mục tiêu, tức là chúng có thể tối thiểu số chặng trung gian, hoặc tối thiểu loại thước đo khác nào đó nhưng không thể là cả hai. Tối ưu mục tiêu kép là nhiệm vụ phức tạp hơn và nói chung nó là một bài toán khó giải. Giải thuật đường đi ngắn nhất Bellman-Ford được dùng cho việc tính đường đi của một thước đo tối thiểu cho tất cả các chặng trung gian. Đây là một tính chất của giải thuật Bellman – Ford mà ở h lần lặp lại của nó, nó xác định đường tối ưu giữa nguồn và đích, giữa các đường đi ở hầu hết h chặng. Tuy nhiên, bởi vì giải thuật Bellman-Ford tiến hành bằng việc tăng chặng số chặng trung gian nên nó cần cung cáp cho chặng trung gian rỗi một đường đi như một tiêu chuẩn tối ưu thứ hai. Đây có thể là một tính năng đặc biệt thú vị nếu mục tiêu là tìm đường ngắn nhất (với một thước đo cụ thể) trong khi vẫn tìm một đường “ tương đối “ ngắn, đó là đường cũng tối thiểu chặng trung gian. + So sánh giữa định tuyến vectơ khoảng cách và định tuyến Trạng thái liên kết trong bài toán RWA Định tuyến trạng thái liên kết và véctơ khoảng cách là hai khả năng có thể xử lý toàn bộ tin tức về mạng. Tuy nhiên, việc lựa chọn cả hai giải thuật gây ra các chế độ rất khác nhau khi xem xét vấn đề RWA. Hiệu suất của hai phương pháp cho việc thiết lập luồng quang động thì trạng thái liên kết làm tốt hơn với tải trọng thấp. Định tuyến phân tán cho xác xuất tắc nghẽn thấp hơn với tải trọng cao. Tuy nhiên, khuyết điểm cơ bản của giải thuật vectơ khoảng cách là ở chỗ chúng không phù hợp nhiều bằng giải thuật liên kết khi xem xét vấn đề xử lý lưu lượng. Đặc biệt, ưu điểm chính của giải thuật trạng thái liên kết là mỗi nút có một tin tức tổng thể về mạng. Điều này làm cho nó dễ dàng tìm các tuyến rõ ràng từ một nút nguồn tới một nút đích, do vậy tăng xác xuất mắc lỗi hơn cho mạng. Ví dụ có thể tăng khả năng khôi phục khi các nút đầy tin về mạng. Mặc dù bài toán định tuyến dựa trên tin tức tổng thể phải giải quyết nhiệm vụ duy trì một số lượng lớn thông tin trạng thái đang thay đổi liên tiếp, nhưng bài toán này thường thực hiện các quyết định tuyến tối ưu nhất nếu thông tin trạng thái là mới nhất. Do vậy, bài toán dựa trên thông tin tổng thể có thể rất phù hợp cho các mạng mà trong đó luồng quang là khá tĩnh và không thay đổi nhiều theo thời gian. D. Định tuyến thích nghi dựa trên thông tin cục bộ Ưu điểm của thông tin cục bộ là các nút không phải duy trì một số lượng lớn thông tin trạng thái; tuy nhiên, các quyết đinh định tuyến có khuynh hướng kém tối ưu hơn so với trường hợp thông tin tổng thể. Hai ví dụ về bài toán định tuyến thích nghi dựa trên thông tin cục bộ là định tuyến thay thế với thông tin cục bộ và định tuyến lệch. D.1. Định tuyến thay thế dựa trên thông tin cục bộ Trong khi các bài toán định tuyến thay thế thường dựa trên thông tin tổng thể thì khác với hiện nay chỉ dùng thông tin cục bộ. Trong bài toán định tuyến thay thế tắc nghẽn ít nhất, việc lựa chọn một tuyến được xác định bởi bước sóng có thể sử dụng dọc theo tuyến thay thế. Hai bài toán khác nhau được xem xét: Trường hợp trong đó thông tin bước sóng có thể sử dụng được biết đến dọc theo toàn bộ tuyến, và trường hợp đó chỉ có thông tin bước sóng là có thể sử dụng được biết đến dọc theo toàn bộ tuyến, và trường hợp trong đó chỉ có thông tin cục bộ là có thể sử dụng. + Nhận biết bước sóng đầu cuối - đầu cuối Trong phương pháp đầu tiên, thực thể thực hiện định tuyến nhận thấy thông tin bước sóng có thể sử dụng cho tất cả các tuyến liên kết trong các đường thay thế. Trong trường hợp này, tuyến được chọn là tuyến có bước sóng lớn nhất có thể sử dụng dọc theo toàn bộ các tuyến liên kết trong đường đi của nó. Ví dụ như, trong hình 2.4, nếu hai tuyến thay thế từ nút nguồn A tới nút đích D được xem xét với các bước sóng có thể sử dụng như được chỉ trên mỗi tu