Đề tài Định tuyến và gán bước sóng trong mạng quang WDM

bộ chuyển đổi bước sóng và số lượng luồng nhánh trên mỗi cạnh từ nguồn đến đích cần phải sử dụng bộ chuyển đổi bước sóng. Giải pháp tổng thể Chuyển đồ thị nhằm mục đích định tuyến. Xác định đường đi ngắn nhất. Chuyển đồ thị nhằm mục đích gán bước sóng. Thực hiện giải pháp gán bước sóng. Sau đây là một số bước thực hiện cụ thể: Thực hiện định tuyến nguồn đến đích Chuyển mạng gốc thành đồ thị bổ trợ, bằng cách dùng hai nút giả ngẫu nhiên S và D kết nối trực tiếp với hai nút nguồn đích trong mạng gốc với chi phí kết nối là 0. Sau đó thực hiện chuyển đổi tuyến trong mạng gốc thành đỉnh và cạnh trong đồ thị bổ trợ. S và D đóng vai trũ như các nút trung gian, không tham gia quá trình chuyển đổi này. Hình 2.2 (a) Đồ thị mạng gốc trong giải pháp WCA Hình 2.2 (b) Đồ thị bổ trợ trong giải pháp WCA Trong mạng WDM, đường quang động có thể khụng thiết lập qua một nút (node) có gán bước sóng đầu vào đầu ra cho phép, khi tại đầu đó không có bộ chuyển đổi bước sóng phù hợp với các bước sóng vào ra còn có thể sử dụng. Do đó khi thiết lập hàm tính toán tham số tải trọng của cạnh trên đồ thị bổ trợ, cần phải dựa vào tham số trạng thái của đường tuyến như số bước sóng đầu vào đầu ra cho phép, số lượng cũng như giải chuyển đổi cũng như dải chuyển đổi của các bộ chuyển đổi bước sóng tại nút. Tải trọng của một cạnh trên đồ thị bổ trợ được xác định bằng xác suất của các luồng nhánh cho phép đi qua cạnh đó. Giải thuật tỡm đường Dijkstra được áp dụng để tỡm đường đi ngắn nhất trong đồ thị bổ trợ (tải trọng của luồng nhánh là thấp nhất), tương ứng với đường đi từ nguồn đến đích trong mạng gốc. Trong đồ thị bổ trợ này, không quan tâm đến các kênh trên một tuyến giữa hai nút, mà chỉ quan tâm đến tải trọng của chúng. Gán bước sóng Các đường đi tối ưu được áp đặt trong biểu đồ bổ trợ để tạo ra đồ thị bổ trợ của bước sóng tiếp theo trong giải pháp tổng thể. Tại thời điểm này chỉ quan tâm đến các luồng nhánh tối ưu tìm được theo giải pháp trên và xét đồ thị bổ trợ trờn tập các luồng nhánh này. Các thuật toán được áp dụng - Thuật toán FFWF(First Fit Wavelength First) _ thuật toán gán bước sóng theo thứ tự bước sóng. Node nguồn sẽ thực hiện và gán bước sóng chưa dùng đầu tiên nó tìm thấy trên đường đi tối ưu từ nguồn tới đích xác định theo giải thuật định tuyến. Khi việc gán bước sóng thực hiện trên một tuyến, yêu cầu kết nối sẽ được gửi tới một node kế cận, và quá trình tiếp tục. Tại node thuật toán luồng ưu tiên sử dụng bộ chuyển đổi bước sóng nếu cho phép. Bản tin từ chối yêu cầu trả về trong hai trường hợp, hoặc không thể gán được trên toàn bộ tuyến, hoặc cho phép một bước sóng trên đường quang động được xác định. - Thuật toán LEC (Least Converter First ) – chuyển đổi bước sóng Giải thuật LEC được coi vấn đề gán bước sóng như vấn đề định tuyến và giải thuật Dijkstra để tìm giải pháp. Lý do đưa ra là số bộ chuyển đổi bước sóng tại node có thể rất nhỏ số bước sóng cho phép sử dụng tại node đó, nú có thể đưa tham số này vào để xem xét trong vấn đề gán bước sóng. Một biểu đồ bổ trợ cũng được lập ra tương tự, nhưng trong giải thuật này, chỉ quan tâm đường đi tối ưu tìm được trong giải thuật định truyến. Tải trọng LEC xác định theo cách tương tự, tức là một kênh có tải trọng hữu hạn nếu nó chưa sử dụng, và nó có tải trọng là vô hạn nếu nó đang sử dụng. Tải trọng của một cạnh chuyển đổi bằng g và lớn hơn tổng của bất kỳ đường nào chưa dùng mà có bộ chuyển đổi bước sóng tại node đạt bằng 0. LEC sẽ thiết lập một đường quang cho một yêu cầu kết nối với tối thiểu hóa các bộ chuyển đổi được sử dụng. Nếu không có đương quang nào được thiêt lập yêu cầu kết nối bị từ chối. - Thuật toán LCC (Least Converter Cost First) LCC tương tự như LEC nhưng hàm tải trọng xây dựng không tuyến tính. Nó đặt ra giả thiết rằng việc sử dụng các bộ chuyển đổi bước sóng tại các node có hiệu suất sử dụng chuyển đổi bước sóng cao sẽ phải trả với chi phí cao. 2.2 Topo vật lý Đặc điểm của topo vật lý đóng vai trũ chủ yếu là hoạt động kết nối sợi ở thiết bị đầu cuối là hiệu suất chủ yếu của mạng. Chúng ảnh hưởng nhiều đến chất lượng tín hiệu quang, hiệu suất quang, lưu lượng đưa vào lớn nhất và khả năng tồn tại của mạng. Biểu đồ đường kính D đưa ra khoảng cách giữa hai node mạng (bước nhảy quang). Bởi vỡ đường dẫn quang càng dài thỡ chất lượng tín hiệu càng xấu, mạng sẽ nghẽn. Như vậy topo tốt có thể thực hiện với độ dày đặc, trong hướng này sẽ cú bậc cao (số của node), và đường kính nhỏ. Giới hạn lớn nhất của biểu đồ Moore đưa ra NMoore (∆, D) độ ∆ lớn của một biểu đồ và đường kính D. NMoore(∆,D) = 1+∆ (∆-1)i = , ∆ >2 (2.1) Biểu đồ này đạt được giới hạn đó nhận biết qua biểu đồ Moore. Cú một số vụ hạn của đường kớnh 1 của biểu đồ Moore. Ngoài ra biểu đồ Moore của độ 2 và tồn tại của mọi đường kính . Tuy nhiên biểu đồ Moore đường kính nhỏ đạt tới điểm rất hiếm tăng thêm.Với D=2 chỉ có 1 biểu đồ Moore của độ 3. Biểu đồ Moore của đường kính 2 và 3 không thể tồn tại một vài độ khác được loại trừ ra một cách hợp lý ∆ =57 Hình 2.3 Biểu đồ 38 đỉnh Mục đích của topo vật lý là phác họa biểu diễn ước lượng nú là bản tin xóa bỏ tuỳ ý với công việc về topo này với độ đối xứng cao. 2.3 Định tuyến và gán bước sóng tĩnh Trong phần này mô tả bài toán thiết lập luồng quang tĩnh SLE. Trong bài toán SLE, các yêu cầu luồng quang được biết trước và việc định tuyến và gán bước sóng thực hiện ngoại tuyến (off-line). Đố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 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 tắc nghẽn) cho một số các bước sóng và các yêu cầu kết nối đưa ra. Với 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ể được áp dụng như quy hoạch 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ố các luồng quang qua từng liên kết riêng biệt. Bây giờ xây dựng bài toán SLE. Đặt lsdw biểu diễn lưu lượng (số các yêu cầu kết nối) từ nguồn s đến đích d trên bất kỳ bước sóng w nào. Ta giả sử rằng hai hoặc nhiều hơn các luồng quang có thể được thiết lập giữa cặp cùng nguồn- đích nếu cần, nhưng mỗi chúng phải dùng một bước sóng riêng biệt; do đó lsdw £ 1. Đặt biểu diễn lưu lượng (số các yêu cầu kết nối) từ nguồn s đến đích d trờn liên kết ij và bước súng w. khi một bước sóng trên một liên kết có thể được gán chỉ cho một tuyến. Dựa vào cấu hình mạng vật lý, một tập các luồng quang và ma trận lưu lượng trong đó biểu diễn số các kết nối cần thiết giữa nguồn s và đích d, bài toán được xây dựng như sau. MinimizeFmax (2.2) Nghĩa là: (2.3) (2.4) (2.5) = 0, 1 (2.6) (2.7) Cách tiếp cận như trên cũng có thể sử dụng đạt được tối thiểu số bước sóng yêu cầu cho một tập các yêu cầu kết nối bằng cách thực hiện một thuật tìm kiếm để đạt được số tối thiểu các bước sóng trong mạng. Với một số bước sóng đó biết, cú thể ỏp dụng bài toán quy hoạch ILP để biết nếu có một lời giải. Nếu lời giải không tìm ra thì khi đó số các bước sóng lớn hơn được thử. Quy trình này được lặp đi lặp lại cho đến khi đạt được số các bước sóng nhỏ nhất. Với bài toán cực đại số các kết nối được thiết lập cho số các bước sóng cố định và tập các yêu cầu kết nối đưa ra cũng có thể được xây dựng như bài toán quy hoạch ILP: Các tham số được xây dựng như sau: Nsd: Số các cặp nguồn-đích L: Số cỏc liờn kết W: Số các bước sóng trên một liên kết m = { mi }, i = 1, 2,.....Nsd: Số các kết nối thiết lập cho cặp nguồn - đích thứ i. r : Tải yêu cầu (tổng số các yêu cầu kết nối được định tuyến) q: = { qi }, i = 1, 2,.....Nsd: Phần chia của tải đến cho cặp nguồn đích i (như vậy qi r = số các kết nối được thiết lập cho cặp nguồn-đích i). P: Tập các luồng trên một kết nối nào đó có thể được định tuyến A= (aij): ma trận P ´ Nsd trong đó aij = 1 nếu luồng quang i giữa cặp nguồn-đích j, và khác đi aij=0. B= (bij): ma trận P ´ L, trong đó bij = 1 nếu liờn kết j là trờn luồng i, khác đi bij = 0. C= (Cij): ma trận định tuyến và gán bước sóng P ´ W, như vậy cij = 1 nếu bước sóng j được gán tới luồng i, trường hợp khác cij = 0. Hàm mục tiêu của bài toán định tuyến và gán bước sóng xây dựng ở đây là cực đại số các kết nối thiết lập, C0(r, q). Công thức quy hoạch ILP được xây dựng như sau: Maximize C0 (r, q) = (2.8) Điều kiện ràng buộc mi ³ 0 nguyên, i = 1,2,...., Nsd (2.9) cij Î i= 1,2,.....,P, j=1,2,.....,W (2.10) CTB £ 1W´ L (2.11) m£ 1W CTA (2.12) mi £ qi r , i = 1,2,...., Nsd (2.13) Phương trình (2.7) đưa ra tổng số các kết nối thiết lập trong mạng. Phương trình (2.10) đặc trưng cho một bước sóng có thể được sử dụng nhiều nhất một lần trên một liên kết đưa ra, trong đó 1W ´ L là ma trận W ´ L mà các phần tử là đơn vị. Phương trình (2.11) và (2.12) đảm bảo rằng số các kết nối thiết lập nhỏ hơn số các kết nối yêu cầu trong đó 1w là ma trận 1 ´ W trong đó các phần tử là đơn vị. 2.4 Định tuyến và gán bước sóng với bộ chuyển đổi bước sóng Trong mạng định tuyến ghép bước sóng WDM, điều kiện ràng buộc bước sóng liên tục có thể được loại ra nếu có thể sử dụng bộ chuyển đổi bước sóng (Wavelength Converter – WC) để chuyển đổi số liệu đến trên một bước sóng ở một liên kết thành bước sóng khác tại một nút trung gian trước khi truyền nó tới liên kết tiếp theo. Các mạng định tuyến bước sóng với khả năng này được gọi là các mạng hoán đổi bước sóng. Nếu một bộ chuyển đổi bước sóng cung cấp khả năng để chuyển đổi bất cứ bước sóng nào thành bất cứ bước sóng khác gọi là có dải chuyển đổi đầy đủ, và nếu có một bộ chuyển đổi bước sóng cho mỗi liên kết sợi quang trong mỗi nút của mạng, khi đó mạng được gọi là có khả năng chuyển đổi bước sóng đầy đủ. Một mạng hoán đổi bước sóng với khả năng chuyển đổi bước sóng đầy đủ tại mỗi nút là tương tương với một mạng điện thoại chuyển mạch kênh; như vậy khi đó chỉ còn tính bài toán định tuyến. Chú ý rằng một luồng quang đơn trong một mạng hoán đổi bước sóng có thể sử dụng một bước sóng khác dọc theo mỗi kiên kết trong các luồng của nó. Như vậy việc chuyển đổi bước sóng có thể cải thiện hiệu suất trong mạng do nó giải quyết được các xung đột các luồng quang. Thông thường với một kế hoạch định tuyến, việc chuyển đổi bước sóng cung cấp một giới hạn xác suất nghẽn có thể đạt được thấp cho bài toán gán bước sóng. Sau đây xây dựng bài toán RWA có sử dụng chuyển đổi bước sóng: Đặt là lưu lượng từ bất kỳ nguồn s nào đến bất kỳ đích d nào (số các yêu cầu kết nối). Đặt là lưu lượng từ nguồn s đến đích d trên liên kết ij. Công thức tính cho bài toán RWA có chuyển đổi bước sóng nghĩa là không có điều kiện ràng buộc bước sóng được xây dụng là: Minimize Nghĩa là (2.14) (2.15) Trong nhiều trường hợp, chuyển đổi bước sóng đầy đủ trong mạng không thể thực hiện và thực tế cũng không cần thiết do chi phí cao. Nó có thể hoặc là một tập con các nút cho phép chuyển đổi bước sóng (một bộ chuyển đổi bước sóng được dùng chung trên nhiều liên kết sợi) hoặc là nút dùng các bộ chuyển đổi mà nó chỉ có thể chuyển đổi một dải giới hạn các bước sóng. Các bộ chuyển đổi bước sóng có thể sử dụng trong mạng theo 3 hình thức sau: Các bộ chuyển đổi bước sóng đặt rải rác trong mạng: Khi các bộ chuyển đổi bước sóng cũn đắt, về mặt kinh tế nó không thể trang bị ở tất cả các nút trong mạng WDM. Do đó có thể đặt bộ chuyển đổi rải rác (chỉ có một số nút chuyển mạch trong mạng có thể chuyển đổi). Dùng chung các bộ chuyển đổi: Ngay cả trong số các chuyển mạch có khả năng chuyển đổi bước sóng, nó không thể chi phí hiệu quả để thiết lập tất cả các cổng lối ra của một chuyển mạch với khả năng này. Việc thiết kế kiến trúc nút chuyển mạch đó được đưa ra nó cho phép dùng chung các bộ chuyển đổi bước sóng theo các tín hiệu khác nhau tại một chuyển mạch. Chuyển đổi bước sóng giới hạn: Các bộ chuyển đổi bước sóng toàn quang dựa trên trộn 4 sóng chỉ cung cấp một dải giới hạn khả năng chuyển đổi bước sóng. Nếu dải được giới hạn tới k, thì một đầu vào bước sóng chỉ có thể được chuyển đổi từ bước sóng đến trong đó w là số các bước sóng trong hệ thống. 2.5 Định tuyến và gán bước sóng động Trong các mạng định tuyến quang WDM trong môi trường lưu lượng động, kỹ thuật gán bước sóng yêu cầu để thiết lập và giải phóng các kết nối quang. Khi có một yêu cầu kết nối, kỹ thuật gán bước sóng phải có khả năng lựa chọn một tuyến, gán một bước sóng cho kết nối và đặt cấu hình các chuyển mạch quang thích hợp trong mạng. Để giảm thiểu xác suất nghẽn, có thể trang bị cho các nút mạng với các bộ chuyển đổi bước sóng (Wavelength Converter) để giải quyết xung đột bước sóng. Đặc biệt, khi truyền tin gặp xung đột bước sóng trên một chặng, có thể sử dụng một bộ WC để chuyển đổi bước sóng của nó sang một bước sóng khác. Trong mạng WDM phải chịu thêm những ràng buộc trong việc gán bước sóng, nếu một nút định tuyến được trang bị một bộ chuyển đổi bước sóng, thì sau đó sự ràng buộc bước sóng liên tiếp mất đi và bài toán định tuyến giống với những mạng chuyển mạch kênh thông thường ở đó chỉ có một hệ số giới hạn là số kênh truyền khả thi trong mỗi liên kết. Tuy nhiên, nếu một luồng quang làm việc ở cùng một bước sóng truy nhập tất cả các tuyến sợi mà nó truyền, định tuyến và gán bước sóng (RWA) phải đáp ứng được điều kiện ràng buộc liên tục bước sóng. Sự ràng buộc này dẫn tới việc sử dụng không hiệu quả các kênh quang và dẫn đến làm tăng xác suất nghẽn. Ví dụ, một yêu cầu có thể phải loại bỏ mặc dù một tuyến đó có nhưng với bước sóng lại không khả thi trong tất cả các liên kết dọc theo đường của nó. Bởi vậy, bài toán RWA trở nên cấp bách trong các mạng định tuyến WDM ở đó mục tiêu là làm tối đa số lượng dữ liệu đưa vào bằng việc tối ưu hóa các luồng quang và các bước sóng được phân bổ để đưa ra một mô hình lưu lượng. Các thuật toán RWA động được đặc trưng bởi một số 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 kết nối đến và đi khỏi mạng xuất hiện từng yêu cầu một, theo một cách ngẫu nhiên. Thước đo đặc tính được sử dụng thường rơi và một trong 3 loại sau đây: + Số bước sóng yêu cầu; + Xác suất tắc nghẽn kết nối (số lượng 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 một trên tổng số các kết nối đến hoặc đi; + Số lượng các 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). Trong trường hợp lưu lượng động, mục tiêu là thiết lập các luồng quang và gán các bước sóng theo cách tối thiểu tắc nghẽn kết nối, hoặc làm cho số kết nối được thiết lập trong mạng là lớn nhất tại mọi thời điểm. Đây là bài toán thiết lập luồng quang động (DLE - Dynamic Lightpath Establishment). Một số phương pháp heuristic điển hình được đề xuất cho bài toán này là: Thuật toán gán bước sóng ngẫu nhiên (Random), thuật toán gán bước sóng theo thứ tự bước sóng (FF - First Fit), thuật toán gán bước sóng theo chiều dài luồng quang còn lại đầu tiên dài nhất (LF - Longest First), thuật toán gán bước sóng dựa trên bước sóng sử dụng ít nhất (LU - Least used), thuật toán gán bước sóng theo số bước sóng sử dụng nhiều nhất (MU - Most Used), thuật toán gán bước sóng theo tích số nhỏ nhất (MP - Min-Product), thuật toán gán bước sóng dựa trên tải ít nhất (LL - Least Loaded), thuật toán gán bước sóng dựa trên tổng dung lượng lớn nhất (Må - Max-Sum), thuật toán gán bước sóng dựa trên tổn thất dung lượng tương đối (RCL - Relative Capacity Loss), gán bước sóng đặt trước (Rsv- Wavelength Reservation), gán bước sóng dựa trên ngưỡng bảo vệ (Thr - Protecting Threshold). CHƯƠNG III: CÁC PHƯƠNG PHÁP ĐỊNH TUYẾN VÀ GÁN BƯỚC SÓNG TRONG MẠNG QUANG WDM 3.1 Phương pháp định tuyến Phương pháp định tuyến nói chung có thể phân làm 2 loại cố định và thích nghi có sử dụng thông tin trạng thái mạng lưới dưới dạng toàn cục hoặc cục bộ. Sau đây sẽ giới thiệu một số tiếp cận điển hình giải bài toán định tuyến trong mạng WDM được sử dụng trong các thuật toán định tuyến. 3.1.1 Phương pháp định tuyến trong mạng MESH 3.1.1.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 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 (ofline) sử dụng thuật toán đường ngắn 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ác cặp nút riêng được thiết lập sử dụng tuyến được xác định trước. Trong hình 3.1 đường ngắn nhất cố định minh hoạ từ nút 0 đến nút 2. 0 1 2 3 5 4 Hình 3.1 Đường ngắn nhất cố định 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ị nghẽn, có thể có khả năng dẫn đến xác xuất 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 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 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 hay 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.1 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 tuyến sợi trong tuyến cố định. 3.1.1.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 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à 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 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.2 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. 0 1 2 3 5 4 Hình 3.2 Tuyến chính (nét liền) và tuyến thay thế (nét chấm) từ nút 0 đến nút 2 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ị nghẽn hoặc bị huỷ. 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 đườ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 để tránh sự cố mạng. 3.1.1.3 Định tuyến thích nghi 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ụ 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 phí í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 không sử dụng trong mạng có chi phí bằng 1 đơn vị, 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ữa nút nguồn và nút đích sẽ được xác định. Nếu có nhiều tuyến có cùng chi phí, một trong chúng sẽ được lựa chọn ngẫu nhiên. Bằng cách lựa chọn chi phí 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 rằng 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 2.3 nếu 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.2 sẽ bị nghẽn. 0 1 2 3 5 4 ∞ 1 1 1 ∞ 1 1 Hình 3.3 Định tuyến thích nghi từ nút 0 đến nút 2 Một dạng khác của định tuyến thích nghi là định tuyến trên luồng có nghẽn ít nhất (LCP – Least Congested Path). Giống như đị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 có yêu cầu kết nối đến, luồng nghẽn ít nhất trong số các tuyến xác định trước được lựa chọn. Nghẽn trên một tuyến sợi được đo bằng số bước sóng có thể sử dụng. 3.1.1.4 Định tuyến bảo vệ Khi thiết lập các kết nối trong một mạng định tuyến ghép bước 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. 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 quang chính cho sử dụng còn một luồng kia được gọi là luồng quang dự phòng để phục hồi cho luồng quang chính bị hỏng. Cách tiếp cận này có thể được sử dụng để bảo vệ các tuyến sợi hỏng đơn trong mạng. Để bảo vệ nút sai hỏng, các đường chính và đường thay thế cũng có thể phân tập 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, 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á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ể 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 trục 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 đủ các tài nguyên sử dụng 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 đường phục hồi dưới cách tiếp cận hồi phục có thể mất thời gian đáng 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ệ. 3.1.2 Phương pháp định tuyến trong mạng cấu trúc RING WDM Tương tự như cấu trúc Ring SDH, khi xét 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 (BSHR- Bidirect Shelf Healing Ring). Ring bảo vệ dành riêng DPRing (OCH/OMS DPRing-Dedicated Protection Ring hoặc OCH-SNCP Ring Sub-Network Conection 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 đơn giản để phân bổ bước sóng là: mỗi 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 nằm ở phần giao diện quang và VC-4. Ví dụ, xác định sắp xếp logic các nút tốt nhất (cấu hình SDH) hoặc cách ghép các VC-4 vào bước sóng 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 lại 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 bài 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 chung vào định tuyến và gán 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. Đối với cấu hình Ring, mặc dù có sự khác nhau giữa hai quá trình trên nhưng cách định cỡ được thực hiện tương tự nhau. Bởi vì các bài toán con ở hai hình trên khi áp dụng cho mạng cấu hình Ring ở trở nên rất đơn giản nhờ cấu trúc bảo vệ vốn có của mạng Ring. Chẳng hạn 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 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 kia sử dụng cho kênh dự phòng.Về nguyên tắc khi có sự cố xảy