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

ong [5] người ta đã chứng tỏ rằng, khi không có bộ chuyển đổi chiều dài của tuyến là yếu tố quan trọng nhất ảnh hưởng đến xác suất nghẽn của tuyến. Bộ chuyển đổi bước sóng có thể cải thiện xác suất nghẽn của mạng chủ yếu bởi vì bộ chuyển đổi đã chia tuyến này thành nhiều đoạn và vì vậy đã giảm được ràng buộc về tính liên tục bước sóng. Do đó xác suất nghẽn của tuyến có liên quan phần lớn đến chiều dài cực đại của đoạn trên tuyến đó. Điều này dẫn đên một thuật giải nội suy mới tên là WMSL với mục tiêu giảm tối thiểu tổng các chiều dài đoạn cực đại tính trên toàn mạng. Thuật giải này được mô tả như sau: Bước 1: Tìm tập các tuyến cho cặp node : theo thuật giải định tuyến theo tuyến có tải nhỏ nhất (LL- Least-Loaded Routing) Bước 2: Coi lưu lượng giữa cặp node phân bố đều trên tất cả các tuyến. Giả sử là tuyến bất kì trong tập , là lưu lượng trên tuyến của cặp node , thì ta có thể lấy xấp xỉ: Bước 3: Tính giá trị trọng lượng cho mỗi node ứng cử . là chiều dài đoạn tối đa của tuyến , và là chiều dài đoạn tối đa của tuyến sau khi đặt bộ chuyển đổi tại node . Hàm trọng lượng được xác định như sau: Sau khi tính cho tất cả các node ứng cử, ta đặt một bộ WC tại node có giá trị trọng số lớn nhất. Bước 4: Nếu vẫn còn bộ chuyển đổi, thì quay trở lại bước 3 cho vòng mới. Tính phức tạp về thời gian tính toán của thuật WMSL có thể phân tích như sau. Ta có M bước, trong mỗi bước ta phải tính các giá trị trọng lượng cho từng node ứng cử. Mối giá trị trọng lượng có thể được tính trong O (N2) đơn vị thời gian. Nên tổng thời gian của thuật giải WMSL là O(MN3). Đánh giá chất lượng thuật toán MBPF và WMSL qua mô phỏng Trong [3] đầu tiên lợi ích của việc sử dụng bộ chuyển đổi được đánh giá qua mô phỏng mạng ring 8 node và mạng mesh-torus 25 node. Sau đó, các tác giả đã thực hiện nhiều mô phỏng trên các mạng các mạng 14-node NSFNet và 19-node EON và 38-node CTNet để đánh giá xác suất nghẽn của các thuật phân bổ MBPF và WMSL được đề suất. Trong các mô phỏng này, người ta dùng giả thiết: Yêu cầu kết nối đến theo phân bố Poisson, thời gian chiếm kênh tuân theo phân bố hàm mũ, các cặp node nguồn-đích có tải như nhau, mỗi link có 40 kênh bước sóng, với hai đường đi ngắn nhất có thể sử dụng cho mỗi cặp nguồn-đích và giả thiết xác suất nghẽn trên hai đường đó độc lập với nhau. Đánh giá lợi ích sử dụng WC Đầu tiên [3] thực hiện mô phỏng trên các mạng ring 8 node và mạng mesh-torus 25 node để đánh giá lợi ích của chuyển đổi bước sóng. Để đơn giản, người ta sử dụng thuật toán RWA FAR-FF và thuật phân bổ MBPF cho mạng ring; sử dụng thuật toán RWA LLR-FF và thuật toán WCP WMSL cho mạng mesh-torus. Thực hiện mô phỏng chô tất cả các trường hợp có thể về số lượng bộ chuyển đổi, cụ thể từ không có WC đến hàng chục bộ WC được sử dụng. X/s nghẽn theo số node WCR trong mạng ring, FAR-FF "Nguồn: [3], trang 48" Từ hình 3.11 ở trên ta có nhận xét là khi số node WCR tăng, xác xuất nghẽn trung bình giảm. Với chỉ một vài WCR, xác suất nghẽn có thể giảm xuống mức rất lớn. Khi số node vWCR tăng vượt qua một mức ngưỡng nào đó, xác suất nghẽn sẽ bắt đầu giảm rất chậm. Vì vậy, chúng ta có thể kết luận, phân bố bộ chuyển đổi rải rác có ý nghĩa rất quan trọng nhờ việc chỉ cần đầu từ 20-50% là có thể đạt 80-90% chất lượng tốt nhất. Đối với mạng mesh-torus, lợi ích của chuyển đổi bước sóng còn rõ ràng hơn, như ở hình 3.12 dưới đây chỉ ra. Điều này chứng tỏ mạng có mạng độ node cao sẽ hưởng lợi nhiều hơn từ bộ chuyển đổi bước sóng so với mạng mạng có ít node. X/s nghẽn theo số node WCR trong mạng mesh-torus, LLR-FF "Nguồn: [3], trang 49" Như vậy cũng từ hình 3.12 ta đưa ra nhận xét rằng, với chỉ một phần nhỏ số node được trang bị bộ chuyển đổi bước sóng, xác suất nghẽn đã giảm một lượng đáng kể. Đánh giá chất lượng của thuật toán FAR-FF và MBPF Trong phần này chất lượng của các thuật giải FAR-FF và MBPF được xem xét. Đầu tiên, xác suất nghẽn của mạng SWC được so sánh với mạng NWC và FWC. Sau đó, so sánh xác suất nghẽn của thuật giải MBPF với thuật giải phân bố ngẫu nhiên, TOT (Total Outgoing Traffic), và WMSL. Mục đích là để chứng tỏ rằng, một thuật giải phân bổ tốt là hết sức quan trọng để mạng đạt được chất lượng cao. Mô phỏng được thực hiện trong hai trường hợp: 2 node WCR, và 5 node WCR. Đối với thuật phân bổ ngẫu nhiên, người ta thực hiện mô phỏng cho một số lượng lớn các trường hợp đặt khác nhau, sau đó tính giá trị nghẽn trung bình. Khi có 2 node WCR, người ta thực hiện mô phỏng cho tất cả các trường hợp đặt bộ chuyển đổi, và trong trường hợp 5 node WCR, người ta chọn ngẫu nhiên 100 trường hợp đặt, sau đó tính giá trị xác suất nghẽn trung bình. Thuật giải TOT đặt bộ chuyển đổi tại các node có lưu lượng đi ra lớn nhất. Thuật giải WMSL được xây dựng cho thuật giải LLR, tuy nhiên cần đánh giá chất lượng cho thuật giải FAR. Hình 3.13 là xác suất nghẽn theo tải lưu lượng tổng cộng tính cho mạng NSFNET 14 node. Cách đặt các bộ chuyển đổi được cho trong bảng 3.2, trong đó M là số node WCR. Trường hợp NWC và FWC cũng được xem xét. Ta thấy rằng, chuyển đổi bước sóng cải thiện đáng kể xác suất nghẽn khi lưu lượng thấp. Khi lưu lượng tăng lên, lợi ích của chuyển đổi bước sóng cũng giảm xuống. Điều này có thể giải thích như sau: khi lưu lượng mạng thấp , yêu cầu kết nối bị từ chối chủ yếu vì ràng buộc tính liên tục bước sóng, vì vậy chuyển đổi bước sóng có thể cải thiện chất lượng đáng kể vì nó đã giúp phá vỡ ràng buộc này. Tuy nhiên khi tải lưu lượng lớn, yêu cầu kết nối bị từ chối chủ yếu vì thiếu bước sóng. X/s nghẽn theo lưu lượng trong mạng NSFNET 14 node, FAR-FF "Nguồn: [3], trang 52" Từ hình 3.13 ta cũng quan sát thấy rằng, chất lượng của thuật phân bổ bộ chuyển đổi ngẫu nhiên rất hạn chế. Tuy nhiên, các thuật giải TOT, WMSL, MBPF có thể đạt được chất lượng tốt hơn rất nhiều. Điều này khẳng định, thuật giải phân bổ là một vấn đề hết sức quan trọng. Một cách bố trí 2 bộ chuyển đổi phù hợp có thể đạt được chất lượng tôt hơn so với mạng có 5 node WCR bố trí không tốt. Trường hợp mạng có 2 node WCR, các kết quả MBPF và WMSL cho cách bố trí giống nhau. Ngoài ra ta còn thấy rằng, thuật giải MBPF đạt chất lượng tốt hơn TOT và cả WMSL. Các kết quả mô phỏng chỉ ra rằng thuật giải MBPF có thể giảm xác suất nghẽn từ 10-20% so với thuật phân bổ TOT. Chất lượng của thuật giải WMSL thậm chí còn tồi hơn cả TOT khi mạng có 5 node WCR. Một nhận xét nữa là, mạng được trang bị chỉ có 5 bộ WCR (35% tổng số node mạng) có thể đạt chất lượng gần như tương đương mạng FWC. Thực hiện mô phỏng tương tự như trên nhưng cho mạng EON 19 node, người ta thu được kết quả so sánh trên hình 3.14. Xác xuất nghẽn theo tải Erlang của mạng EON 19 node, FAR-FF "Nguồn: [3], trang 53" So sánh hình 3.13 và 3.14 ta thấy, với cùng một xác suất nghẽn, mạng EON mang được nhiều tải hơn so với mạng NSFNET. Đó là bởi vì mạng EON có mật độ node dày hơn: bậc node trung bình của EON là 4, trong khi NSFNET là 2.86. Lợi ích của chuyển đổi bước sóng là rất quan trọng. Mạng chỉ có 2 WCR được đặt một cách hợp lý, là có thể giảm xác suất nghẽn xuống một nửa. Nếu sử dụng 5 bộ WCR (khoảng 25% tổng số node), chất lượng của thuật giải MBPF sẽ tiến rất gần tới chất lượng mạng FWC. Ngoài ra một lần nữa ta thấy được, nếu đặt bộ chuyển đổi tùy ý thì mạng có chất lượng cực kém trong cả hai trường hợp có 2WCR và 5 WCR. Trong topo này với cả hai trường hợp 2 WCRvà 5 WCR, các thuật giải MBPF và WMSL có cùng một cách đặt bộ chuyển đổi. Kết quả mô phỏng cho thấy MBPF giảm xác suất nghẽn xuống từ 10-20% so với TOT. Dưới đây là bảng kết quả phân bổ các bộ chuyển đổi của các thuật phân bổ WCP với 2 trường hợp mạng có 2 WCR và 5 WCR "Nguồn: [3], trang 54" Số WC TOT MPBF WMSL 2 (6,10) (4,6) (4,6) 5 (3,4,6,7,10) (3,4,6,9,10) (3,4,6,10,12) Vị trí đặt các WC trong 14-node NSFNet với 2 và 5 bộ WC Số WC TOT MPBF WMSL 2 (1,9) (1,7) (1,7) 5 (1,2,4,9,6 (1,2,4,7,9) (1,2,4,7,9) Vị trí đặt các WC trong mạng 19-node EON với 2 và 5WC Đánh giá chất lượng của thuật toán LLR-FF và WMSL Thuật toán WMSL được thiết kế cho thuật giải định tuyến LLR. [3] thực hiên các mô phỏng cho mạng sử dụng thuật toán RWA LLR-FF . Chất lượng WMSL được so sánh các thuật giải phân bổ ngẫu nhiên, TOT, MBPF, và với trường hợp mạng NWC và FWC. Kết quả của các thuật toán phân bổ cho các mạng NSFNET 14node và EON 19 node được cho trong bảng 3.6 và 3.7 ở trên. Xác suất nghẽn mạng NSFNET 14 node, LLR-FF "Nguồn: [3], trang 57" X/s nghẽn mạng EON 19 node, LLR-FF "Nguồn: [3], trang 59" Từ hình 3.15 và 3.16 ta rút ra một số nhận xét sau: Chuyển đổi bước sóng làm giảm xác suất nghẽn đáng kể khi lưu lượng thấp khi thuật toán LLR-FF được sử dụng. Khi lưu lượng lớn, lợi ích của chuyển đổi bước sóng giảm Mức độ giảm xác xuất nghẽn trung bình của thuật phân bổ ngẫu nhiên là không đáng kể. Tuy nhiên thuật TOT và WMSL đạt chất lượng tốt hơn rất nhiều. Trong cả hai trường hợp có 2 và 5 node WCR chất lượng của thuật toán WMSL tốt hơn TOT, cụ thể là có thể giảm xác xuất nghẽn từ 10-20% đối với mạng NSFNET,và 20-30% đối với mạng EON 19 node so với thuật phân bổ TOT. Chỉ với 5 node WCR (chiếm 35% tổng số node- NSFNET 14 node, và 25% tổng số node mạng EON 19 node), mạng đã đạt chất lượng gần sát với trường hợp mạng FWC. WCP với thuật toán RWA WLCR-FF Xác suất nghẽn là chỉ số chất lượng quan trọng trong thiết kế một mạng toàn toàn quang định tuyến bước sóng. Các nghiên cứu hiện tại chỉ ra rằng thuật toán RWA và thuật toán phân bổ tối ưu bộ chuyển đổi là hai nhân tố quyết định đến chất lượng mạng (làm giảm xác suất nghẽn). Một thuật toán RWA hiệu quả cần phải xét cùng với chuyển đổi bước sóng với hai lí do: 1) việc đặt hay trang bị bộ chuyển đổi bước sóng thường được thực hiện ở đầu tiên trong quá trình quy hoạch dung lượng hệ thống; 2) một trong những lợi thế của mạng toàn quang là khả năng cấu hình lại Topo logic của mạng trong quá trình định tuyến và gán bước sóng. Trong phần này tác giả giới thiệu đồng thời thuật toán RWA mang tên WLCR-FF (Weighted Least-Congestion Routing and First-Fit Wavelength Assignment), và thuật toán WCP đi kèm với nó là MBPF (được đề xuất trong[2]). Thuật toán MBPF tính đến cả phân bố các bước sóng rỗi và phân bố chiều dài của mỗi tuyến. Khi không có bộ chuyển đổi, thuật toán WLCR-FF vẫn đạt được chất lượng tương tự như thuật giải LLR-FF. Thuật toán định tuyến và gán bước sóng WLCR-FF Các thuật giải định tuyến và gán bước sóng đóng một vai trò quan trọng cải thiện xác suất nghẽn của các mạng định tuyến bước sóng. Các thuật toán định tuyến động được chứng minh là mang lại xác suất nghẽn nhỏ hơn so với định tuyến tính và định tuyến dự phòng cố định (FAR) khi mạng không có chuyển đổi bước sóng. Trong thuật toán RWA động, nó tìm đồng thời một tập các tuyến nối node nguồn-đích, và tuyến có số lượng bước sóng lớn nhất được chọn để thiết lập lightpath. Thuật toán WLCR-FF là thuật toán RWA động xem xét đồng thời phân bố bước sóng rỗi và chiều dài của mỗi tuyến. Nó kết hợp các đặc điểm tốt nhất của thuật toán định tuyến WLCR và thuật toán gán bước sóng FF. Các tham số hệ thống và giả thiết - Mạng gồm N node và J kết nối. Mối kết nối có W bước sóng được đánh nhãn từ 1 đến W. - Các yêu cầu thiết lập lightpath đến cặp node tuân theo phân bố Poisson với tốc độ (cũng là lưu lượng đến), thời gian giữ kết nối theo hàm mũ với đơn vị thời gian.là lưu lượng được phục vụ, tức là thiết lập lightpath thành công. - Một tuyến R là một tập con các kết nối . Chiều dài của tuyến R kí hiệu là . - kí hiệu số bước sóng rỗi trên kết nối J. - {} là tập các tuyến được tính toán trước cho cặp node . Yêu cầu các tuyến này không có kết nối nào chung để các sự kiện nghẽn trên các tuyến này độc lập với nhau. - Số bước sóng rỗi trên tuyến kí hiệu là . Trong trường hợp không có chuyển đổi bước sóng, là số bước sóng chung còn rỗi trên tất cả các kết nối của tuyến này. Trong trường hợp Full-wavelength conversion, được định nghĩa là , trong đó kết nối j nằm trong tuyến . Trong trường hợp Sparse-Wavelength Conversion, giả sử có bộ chuyển đổi trên tuyến (không tính hai node đầu và cuối), ta có thể chia tuyến này thành đoạn. Đoạn thứ kí hiệu là . Số bước sóng còn rỗi trên đoạn kí hiệu là . Số bước sóng rỗi trên tuyến được định nghĩa là giá trị nhỏ nhất của trong số các đoạn thuộc tuyến này, cụ thể là - là xác suất nghẽn của tuyến Mô tả thuật toán RWA WLCR-FF Trong thuật toán WLCR-FF, một tập các tuyến được tính toán trước cho mỗi cặp node nguồn-đích. Các tuyến này sẽ được tính toán lại khi topo của mạng thay đổi. Nếu có một yêu cầu thiết lập lightpath đến một cặp node, node đó sẽ quyết định chọn một tuyến từ tập các tuyến, sau đó gán bước sóng rỗi cho tuyến này. Mục tiêu của thuật giải này cho phép mạng mang được nhiều lưu lượng nhất mà vẫn giữ xác suất nghẽn thấp. Giả sử là tập các tuyến được xác định trước cho cặp node . Khi nhận được một yêu cầu kết nối cho cặp node a, một tuyến được chọn từ tuyến ứng cử trên. Thuật giải WLCR sẽ đưa ra quyết định chọn tuyến như sau: - Đối với mỗi một tuyến ứng cử ta gán một giá trị trọng lượng (Weight Value) được định nghĩa như sau: Sau khi tính được giá trị trọng lượng cho tất cả các tuyến, ta chọn một tuyến có giá trị cực đại để thiết lập lightpath. Nếu tất cả các tuyến đều không có bước sóng rỗi nào, cụ thể , thì yêu cầu thiết lập kết nối bị từ chối (nghẽn). Khi một lightpath được thiết lập, thuật giả gán bước sóng FF được sử dụng trên mỗi đoạn của tuyến được chọn, cụ thể đối với mỗi đoạn, bước sóng rỗi được dán nhãn (label) nhỏ nhất sẽ được gán cho tất cả các kết nối của đoạn đó. Việc lựa chọn hàm trọng lượng dựa trên nhận xét sau: Khi chọn một tuyến, hai yếu tố quan trọng cần xem xét là số bước sóng rỗi và chiều dài của tuyến. Một cách trực quan, tuyến có nhiều bước sóng rỗi hơn sẽ được chọn, và đồng thời chiều dài của tuyến đó không quá dài. Nếu không có chuyển đổi bước sóng, hai yếu tố này có mối liên quan với nhau, cụ thể, tuyến có chiều dài ngắn hơn sẽ có nhiều bước sóng rỗi hơn so với tuyến có chiều dài lớn hơn. Do vậy các thuật toán RWA truyền thống làm việc rất tốt trong mạng không có chuyển đổi bước sóng bằng cách chọn tuyến có nhiều bước sóng hơn. Tuy nhiên nếu mạng có khả năng chuyển đổi bước sóng, mỗi liên hệ giữa số bước sóng rỗi và chiều dài của tuyến sẽ lỏng đi theo nghĩa tuyến dài hơn có thể có nhiều bước sóng hơn tuyến ngắn. Vì vậy nếu ta chọn tuyến có nhiều bước sóng hơn, thì có thể xảy ra các tuyến đó dài hơn và có khả năng xác suất nghẽn lớn hơn. Về nguyên tắc, hàm trọng lượng tỉ lệ thuận với số bước sóng rỗi, và tỉ lệ nghịch với chiều dài của tuyến. Đây là lí do chính để chọn hàm trọng lượng. Mô hình phân tích thuật giải định tuyến WLCR-FF Mô hình phân tích gồm mô hình cho phân tích định tuyến và mô hình cho phân tích nghẽn tuyến. Mô hình phân tích định tuyến gồm một tập các biểu thức xác định lưu lượng kết nối phục vụ, từ các xác suất nghẽn tuyến. Mô hình phân tích nghẽn tuyến gồm một tập các biểu thức xác định xác xuất nghẽn tuyến từ lưu lượng kết nối phục vụ. Để đơn giản đầu tiên ta giả sử rằng đối với mỗi cặp node , chỉ có hai tuyến được sử dụng , và . Ta có thể mở rộng kết quả cho trường hợp có nhiều hơn hai tuyến. Xác suất nghẽn tổng cộng P là tỉ số giữa lưu lượng bị từ chối (blocked traffic) và lưu lượng được phục vụ (offered traffic): (3-1) Yêu cầu kết nối cho node sẽ bị từ chối chỉ khi kết nối này bị từ chối trên cả hai tuyến . Vì các sự kiện nghẽn của mỗi tuyến được coi la độc lập với nhau, ta có: (3-2) Để tính được xác suất số bước sóng rỗi trên mỗi kết nối khi mạng ở trạng thái ổn định, ta sử dụng phương pháp xấp xỉ tải giảm được giới thiệu trong [7]. Kí hiệu là biến ngẫu nhiên thể hiện số bước sóng còn rỗi tren két nối thứ . Giả sử các biến ngẫu nhiên , độc lập với nhau. Yêu cầu kết nối xuất hiện ở kết nối j theo phân bố Poisson với tốc độ . - kí hiệu xác suất có bước sóng rỗi trên kết nối . Ta có thể rút ra: (3-3) ở đó: (3-4) Lưu lượng đến kết nối là tổng của lưu lượng của tất cả cả tuyến chứa kết nối . Nếu gọi lần lượt là các xác suất một yêu cầu kết nối cho cặp node được phục vụ trên tuyến thứ nhất và thứ hai. Ta có: (3-5) Trong đó: là ma trận chỉ số kết nối-tuyến , - xác suất có bước sóng còn rỗi trên kết nối , và có bước sóng còn rỗi trên đoạn chứa kết nối . - Là xác suất có bước sóng còn rỗi trên đoạn Ta có : (3-6) Một tuyến có thể được thiết lập nếu mỗi đoạn của tuyến đó có bước sóng rỗi. Với giả thiết tương đối rằng các sự kiện nghẽn trên các đoạn là độc lập với nhau. Ta có thể rút ra xác suất nghẽn của bất kì tuyến nào : (3-7) Để xác định , ta cần đưa ra hai kí hiệu nữa : và - lần lượt là xác suất có bước sóng còn rỗi trên tuyến và , cụ thể là và . Do đó ta có : (3-8) Theo thuật giải định tuyến WLCR, ta có : , trong đó (3-9) Và: , trong đó (3-10) Gọi tập các kết nối của đoạn là , xác suất cho bởi biểu thức sau: (3-11) Trong đó - xác suất tồn tại bước sóng còn rỗi trên đoạn n-hop được xác định như sau: (3-12) Xác suất có điều kiện là xác suất tồn tại bước sóng còn rỗi với điều kiện có x và y bước sóng còn rỗi trên hai kết nối liên tiếp. Từ [7], được tính: (3-14) Các bước tính toán của thuật giải Để xác định xác suất nghẽn tổng cộng, ta thực hiện các phép toán theo các bước sau: Bước 1: Có thể gọi là bước khởi tạo giá trị ban đầu cho các biến. Khởi tạo các biến:=0 cho tất cả các tuyến, =0 cho tất cả các kết nối, . Bước 2: Tính dùng công thức (3-5) cho tất cả các kết nối. Bước 3: Tính sử dụng (3-3) va (3-5) cho tất cả các kết nối. Bước 4: Tính và cho tất cả các đoạn sử dụng (3-6) và các công thức từ (3-11)-(3-14). Sau đó tính và sử dụng các công thức (3-8)-(3-10). Bước 5: Tính cho tất cả các tuyến sử dụng (3-7). Nếu giá trị mới hội tụ về giá trị cũ thì quá trình lặp kết thúc và chuyển sang bước (6). Ngược lại quay trở về bước (2) cho quá trình lặp tiếp theo. Bước 6: Tính xác suất nghẽn tổng cộng sử dụng công thức (3-1) và (3-2). Thuật toán WCP cho WLCR-FF Thuật toán định tuyến và gán bước sóng WLCR-FF được xây dựng làm việc với thuật toán phân bổ MBPF dùng trong mạng Mesh. Nội dung của thuật phân bổ MBPF đã được giới thiệu ở các phần trên Đánh giá chất lượng thuật toán qua mô phỏng Rất nhiều các mô phỏng đã được thực hiện trong [3] để đánh giá chất lượng của thuật giải WCLR-FF trên các Topo mạch vòng 8 node, mạng mesh-torus 25 nodes, mạng NSFNet 14 node và mạng EON 19 node. Yêu cầu thiết lập lightpath xuất hiện theo quá trình Poisson, thời gian chiếm kết nối phân bố theo hàm mũ. Giả thiết tất cả các cặp node nguồn-đích có phân bố tải đồng đều theo đơn vị Erlangs. Mỗi sợi quang mang 40 kênh bước sóng, khoảng cách kênh được định nghĩa bởi ITU. Trong các mô phỏng này, chỉ dùng một trong hai tuyến ngắn nhất không có cạnh chung (để các sự kiện nghẽn trên hai tuyến này độc lập với nhau, bên cạnh một lí do tránh lỗi xảy ra tại cạnh chung đó)cho mỗi cặp nguồn-đích. Nếu một tuyến bị hỏng, kết nối được định tuyến sang tuyến khác. Đối với mỗi topo, các tác giả đã so sánh chất lượng của thuật toán WLCR-FF với các thuật toán SP-FF, FA-FF, và LLR-FF trong các điều kiện các nhau: NC, SWC và FWC. Trong trường hợp SWC, thuật giải MBPF được sử dụng để đặt một số lượng hạn chế bộ chuyển đổi vào mạng. Chất lượng mạng topo Ring Hình 3.17a là kết quả mô phỏng xác suất nghẽn của các thuật giải RWA khác nhau trong mạng ring 8 node không sử dụng chuyển đổi bước sóng. Chúng ta thấy rằng, mạng sử dụng các thuật toán FAR-FF, LLR-FF, và WLCR có chất lượng tốt hơn rất nhiều so với SP-FF. Điều này có thể giải thích như sau: khi tải lưu lượng còn thấp, nguyên nhân gây ra nghẽn là không có bước sóng rỗi chung giữa các kết nối dọc theo tuyến. Khi ta sử dụng hai tuyến ứng cử cho một cặp node, các sự kiện nghẽn của hai tuyến này hoàn toàn độc lập. Vì vậy xác suất nghẽn sẽ được giảm đi rất nhiều. Một nhận xét khác là chất lượng của thuật toán WLCR-FF rất gần với LLR-FF (có chất lượng tốt hơn FA-FF). Các thuật toán RWA động có thể cải thiện xác suất nhẽn nhờ tiết kiệm được nhiều bước sóng cho các kết nối sắp đến, và tại một thời điểm mạng không sử dụng quá nhiều tuyến dài. Hỡnh 3.17b vẽ xỏc suất nghẽn theo tải tổng cộng của mạng Ring sử dụng 4 bộ WC. Theo như MBPF, 4 bộ này được đặt ở cỏc vị trớ (1, 3, 5, 7). Một nhận xột quan trong đú là xỏc suất nghẽn của thuật giải LLR-FF tăng nhanh khi tải tăng. Chất lượng của thuật giải LLR-FF thậm chớ cũn tồi hơn so với FAR-FF. Tuy nhiờn, thuật giải WLCR-FF vẫn đạt chất lượng tốt hơn so với FA-FF. Điểm yếu của thuật giải LLR-FF trong mạng SWC đú là nú đưa ra quyết định chọn tuyến dựa trờn thụng tin của cỏc bước súng rỗi mà khụng quan tõm đến chiều dài của mỗi tuyến. Trong topo Ring, đều cú một tuyến rất ngắn và một tuyến rất dài. Thuật toỏn LLR-FF đó sử dụng quỏ nhiều tuyến dài và vỡ vậy sử dụng quỏ nhiều tài nguyờn mạng. Trong khi đú, WLCR-FF xem xột đến cả chiều dài của mỗi tuyến và trỏnh sử dụng quỏ nhiều tuyến dài nờn nú đạt chất lượng cao hơn. Chất lượng của cỏc thuật toỏn RWA trong trường hợp full-conversion được cho ở hỡnh 3.17c. Trong mạng full-conversion, khụng cũn tồn tại ràng buộc liờn tục bước súng. Cũng tương tự như lập luận ở trờn, LLR-FF sử dụng quỏ nhiều tuyến dài, nờn đó làm tăng vọt xỏc suất nghẽn. Ta cú thể thấy, chất lượng của LLR-FF kộm hơn SP-FF khi tải lơn hơn 100Erlangs. WLCR-FF hoạt động rất tốt với chuyển đổi bước súng đầy đủ. Chất lượng của mạng SWC sử dụng MBPF rất sỏt với mạng Ring FWC. Xác suất nghẽn mạng Ring 8 node và mesh-torus 25 node "Nguồn: [3], trang 76" Chất lượng mạng NSFNET Hỡnh 3.18a là xỏc suất nghẽn so với tải trong mạng NSFNet khụng cú chuyển đổi bước súng. Ta cú thể thấy rằng, chất lượng của FAR-FF tốt hơn rất nhiều so với thuật giải SP-FF. Cỏc thuật giả LLR-FF và WLCR-FF cũn cải thiện chất lượng hơn nữa. Xác suất nghẽn của mạng NSFNET-14 node "Nguồn: [3], trang 79" Trong SWC, cỏc tỏc giả đó đặt 5 bộ chuyển đổi bước súng vào cỏc node (3, 4, 6 ,10, 12) theo thuật giải MBPF. Từ hỡnh 3.18b ta thấy chất lượng thuật giải LLR-FF tốt hơn thuật giảI FAR-FF. Thuật giải WLCR-FF có thể giảm xác suất nghẽn hơn nữa. Hình 3.18c là xác suất nghẽn của mạng FWC. Thuật giải LLR-FF hoạt động không tốt trong trường hợp này. Khi tải tăng, xác suất nghẽn của LLR-FF rất gần và thạm chí còn lớn hơn FAR-FF. Ngược lại thuật giải WLCR-FF lại có thể đạt xác suất nghẽn thấp hơn rất nhiều so với cả FAR-FF và LLR-FF. Giới thiệu phân bổ tối ưu trong mô hình mạng SPWC Như đã nói ở trên, kiến trúc mạng SPWC mang lại ưu điểm: thứ nhất là giảm đáng kể số WC phải sử dụng, và thứ hai là thuận lợi cho quá trình nâng cấp mạng lên hỗ trợ chuyển đổi bước sóng bằng cách mở rộng thêm các bộ chuyển đổi tại node WCR hoặc thay thế bộ định tuyến cũ bằng bộ WCR mới. Các kết quả lý thuyết và từ mô phỏng được công bố trong [3] đã cho thấy rằng, chỉ với 1-5% số bộ WC, nếu được đặt tối ưu là có thể đạt được chất lượng tương đương với mạng Full-Complete. Trong mục này tác giả chỉ muốn giới thiệu các mô hình toán học mà công trình [3] đã sử dụng để ta nắm cụ thể được cách giải quyết bài toán phân bổ tối ưu bộ WC, đặc biệt là thấy được mối liên hệ giữa các thuật toán RWA và thuật toán phân bổ. Mô hình mạng full -complete Dưới đây là một số giả thiết , khái niệm, và kí hiệu sử dụng trong mô hình mạng SPWC: Mạng mesh toàn quang sử dụng WDM gồm N node, và J kết nối (links). Các node được đánh kí hiệu từ 1 đến N, các kết nối được đánh kí hiệu từ 1 đến J Bậc của node kí hiệu là , Số bộ chuyển đổi bên trong node n: F(n) Để đơn giản, coi các kết nối đều là 2 chiều, mỗi kết nối hỗ trợ W bước sóng ở mỗi chiều Giả thiết các yêu cầu thiết lập lightpath giữa cặp node tuân theo quá trình Poisson với tốc độ, thời gian giữ kết nối là hàm mũ theo thời gian. Tổng lưu lượng mà mạng có thể cung cấp là T (Erlang) Để đơn giản, giả thiết sử dụng thuật giải định tuyến Fixed Shortest. Tuyến (route) giữa cặp node a kỹ hiệu là , và chiều dài của tuyến tính theo đơn vị Hop-count là . Kết nối thứ của tuyến kí hiệu là , Xác suất nghẽn của tuyến kí hiệu là: A- Tính xác suất nghẽn cho mạng Full-complete Đối với nhà khai thác, điều quan trọng là phải dự đoán được khả năng bao nhiêu lượng mạng có thể phục vụ với xác suất nghẽn cho trước. Thông thường mạng có chuyển đổi bước sóng full-complete sẽ đạt được chất lượng tốt nhất theo nghĩa xác suất nghẽn. Mục đích của mục này là giới thiệu một mô hình để tính bao nhiêu lưu lượng mạng có thể phục vụ để đảm bảo mạng có xác suất nghẽn thấp cho trước (giả sử là 2%). Trong công trình [2] tác giả đã sử dụng một mô hình đơn giản để tính xác suất nghẽn của mạng WDM với khả năng chuyển đổi bước sóng full-complete. Trong mạng như vậy, mỗi node là một WCR với khả năng chuyển đổi đầy đủ (Complete), cụ thể là số bộ chuyển đổi trong node -được kí hiệu là , được tính bằng công thức: . Mạng sẽ không chịu sự ràng buộc tính liên tục bước sóng. Xác suất nghẽn toàn mạng được định nghĩa là tỉ số giữa lưu lượng bị nghẽn và tổng lưu lượng mà mạng đang phục vụ. Cụ thể là (4-1) Để đạt được xác suất ở trạng thái ổn định số các bước sóng còn rỗi trên mỗi kết nối, người ta sử dụng phương pháp xấp xỉ tải giảm được giới thiệu trong [2]. kí hiệu số bước sóng còn rỗi trên kết nối j. Giả sử rằng các biến ngẫu nhiên Xj, độc lập với nhau, và yêu cầu thiết lập kết nối trên kết nối j là đến theo quá trình Poisson với tốc độ . kí hiệu xác suất có bước sóng còn rỗi trên kết nối j. Hình 3: Chuối Markov cho phân bố các bước sóng rỗi trên kết nối j Theo như các giả thiết đó, các yêu cầu đến và khả năng phục vụ trên kết nối tạo thành hệ thống M/M/m/m (m server) và chuối Markov được mô tả ở hình 3. Giải chuối Markov, sẽ tính được kết quả sau: (4-2) Và (4-3) Theo như cách lấy xấp xỉ trong [6] cho lưu lượng trên kết nối j, ta xác định được theo công thức sau: , trong đó kết nối j thuộc (4-4) Một lightpath có thể được thiết lập nếu và chỉ nếu mọi kết nối trên tuyến từ node nguồn đến node đích có bước sóng rỗi. Vì vậy, ta có thể tính được xác suất nghẽn của một tuyến theo công thức sau: (4-5) Công thức trên dẫn đến một loạt các phương trình phi tuyến, có thể giải được bằng cách thay thế lặp như sau: Bước 1: Khởi tạo cho tất cả các tuyến, và cho tất cả các liên kết. Bước 2: Xác định sử dụng công thức (4-4) cho tất cả các kết nối Bước 3: Xác định sử dụng công thức (4-2) và (4-3) cho tất cả các kết nối. Bước 4: Xác định cho tất cả các tuyến sử dụng công thức (4-5). Nếu các giá trị mới của hội tụ vào các giá trị cũ, thì quá trình lặp này dừng lại và ta chuyển sang bước (5), nếu không ta chuyển sang bước (2) cho quá trình lặp tiếp theo. Bước 5: Cuối cùng ta xác định được xác suất nghẽn B sử dụng công thức (4-1) Chúng ta sử dụng phương pháp trên để tính xác suất nghẽn mạng full-complete. Trong công trình [2], các tác giả đã tính xác suất nghẽn cho mạng 14 NSFNET, với giả thiết tải được phân bố đồng đều cho tất cả các cặp node. Nếu kí hiệu L là chiều dài trung bình của tuyến, thì ta có thể dễ dàng tính được hiệu suất sử dụng bước sóng trung bình . Dựa theo thuật toán định tuyến đường đi ngắn nhất, với chiều dài trung bình là 2.18, ta thu được kết quả về tải lưu lượng mà mạng có thể phục vụ với xác suất nghẽn 2%. Chúng ta có thể thấy hệ số sử dụng bước sóng trung bình chỉ khoảng 60%. Lưu lượng mạng NSFNET có thể phục vụ với x/s nghẽn 2% B- Phân tích lưu lượng đi qua mỗi node Sau khi biết được mạng có thể xử lý được bao nhiêu lưu lượng, ta sẽ phân tích được lưu lượng được đi qua mỗi node. Điều ta quan tâm bây giờ là số lượng chuyển đổi bước sóng đồng thời tại mỗi node. Giả thiết quá trình yêu cầu thiết lập lightpath đến node n tuân theo phân bố Poisson với tốc độ . Rễ ràng suy ra: , trong đó tuyến đi qua node n (4-6) Gọi là xác suất có lightpath được chuyển đổi đồng thời tại node n. Do đó biến thiên từ 0 đến F(n) vì tại một thời điểm node n có thể hỗ trợ tối đa F(n) chuyển dổi đồng thời. Dựa trên các giả thiết đó, ta có bài toán lưu lượng theo mô hình M/M/m/m. Giải chuỗi Markov này, ta thu được: , (4-7) Trong trường hợp này, xác suất nghẽn của hệ thống M/M/m/m rất thấp, hệ thống M/M/m/m có thể được coi xấp xỉ như hệ thống M/M/. Vì vậy, số lightpath cần chuyển đổi bước sóng trung bình có thể xấp xỉ bằng , vì thời gian phục vụ được tính theo phân bố hàm mũ. Vẫn mô phỏng cho mạng NSFNET với 40 bước sóng , yêu cầu xác suất nghẽn là 2% hoặc nhỏ hơn. Từ kết quả ở bảng 3.6, lưu lượng thổng cộng là 208Erl, và mỗi cặp node có 2.286Erl yêu cầu thiết lập lightpath, ta tính được tải chuyển đổi bước sóng tại mỗi node sử dụng công thức (4-6) được cho ở bảng 3.7. Chúng ta thấy rằng tỉ sốdao động từ 0 đến 28.6% và trong hầu hết các trường hợp nó chỉ có giá trị từ 10-15%. Điều đó có nghĩa là số lightpath yêu cầu chuyển đổi bước sóng đồng thời tại mỗi node là rất nhỏ so với dung lượng của node. Giá trị và của mạng NSFNET có tổng lưu lượng 208Erlangs Như vậy có rất nhiều lưu lượng đi qua node nhưng không cần chuyển đổi bước sóng. Chính vì chỉ có một lượng nhỏ lưu lượng đi qua node cần chuyển đổi bước sóng, nên chỉ cần trang bị một số lượng vừa đủ số bộ chuyển đổi bước sóng tại mỗi node mà vẫn đạt được chất lượng như mong muốn. Các mô phỏng tiếp theo trong công trình [3] cũng còn chỉ rõ, nếu sử dụng thuật toán gán bước sóng thích hợp, ta còn giảm được nữa số chuyển đổi bước sóng đồng thời thực hiện tại mỗi node. Bài toán WCP cho mạng SPWC Hiện tại công nghệ chuyển đổi bước sóng vẫn còn ở thời kì bắt đầu, giá thành của các bộ chuyển đổi bước sóng vẫn còn rất, nên sẽ không khả thi nếu các nhà khai thác mạng thay tất cả các node định tuyến bước sóng bằng WCR. Mặc khác người ta đã kết luận cho rằng mạng phân bố WC rải rác có thể đạt được chất lượng tốt gần bằng với mạng trang bị đầy đủ WC. Công trình [2] đã đề xuất một kiến trúc SPWC, kết hợp các ưu điểm của mạng chuyển đổi bước sóng một phần và phân bố bộ chuyển đổi rải rác. Có hai loại node trong mạng này: các node không có khả năng chuyển đổi bước sóng, và các bút có khả năng chuyển đổi bước sóng hạn chế. Bằng cách kết hợp như vậy, chỉ cần một số lượng nhỏ các bộ chuyển đổi bước sóng là mạng có thể đạt được chất lượng tương đương với mạng Full-complete. Điều này sẽ mang lại sự lựa chọn dễ dàng đối với nhà khai thác khi phát triển mạng hiện tại lên hỗ trợ chuyển đổi bước sóng. Mạng này hoạt động như sau: khi nhận được yêu cầu thiết lập lightpath, nếu có bất kì kết nối nào của tuyến được chọn không có bước sóng rỗi, thì mạng không thể thiết lập lightpath cho tuyến đó được. Nếu không, đầu tiên mạng sẽ phải tìm một bước sóng chung còn rỗi trên tất cả các kết nối của tuyến đã chọn. Tất cả các lightpath được thiết lập theo kiểu này sẽ không cần sử dụng chuyển đổi bước sóng. Nếu không có một bước sóng chung, rỗi, thì mạng phải kiểm tra liệu bộ chuyển đổi bước sóng có thể giúp. Một lightpath được chia thành nhiều đoạn (segment) bằng các bộ WCR như hình 3.19 mô tả. : Node đầu cuối : Node hiện không có bộ WC còn rỗi : Node hiện có bộ WC còn rỗi Một lightpath và các phân đoạn của nó Chú ý rằng, một WCR sẽ không có khả năng chuyển đổi bước sóng khi tất cả các bộ WC của nó đều đang bận. Mỗi đoạn chịu sự ràng buộc về tính liên tục bước sóng. Một lightpath có thể được thiết lập thành công nếu và chỉ nếu mọi segment đều tồn tại một bước sóng chung còn rỗi. Vì vậy mạng phải kiểm tra xem mỗi đoạn còn bước sóng rỗi chung không. Sau đó các bộ chuyển đổi sẽ được phân bổ nếu cần thiết. Khi lightpath kết thúc, các bộ WC phục vụ cho lightpath này được chuyển sang trạng thái rỗi. A- Mô hình phân tích tính xác suất nghẽn Để tính toán xác suất nghẽn của mạng WDM định tuyến bước sóng có cấu trúc SPWC, công trình [3] đã đề xuất một mô hình phân tích như sau: Số lượng node WCR trên tuyến là D (không tính hai node nguồn và đích của tuyến ) Vì mỗi WCR chỉ có hai trạng thái: (1) Không còn bộ chuyển đổi bước sóng rỗi, và (2) Còn một hoặc nhiều. Vì vậy, kết hợp ta có 2D trạng thái khác nhau của tuyến Ra. Đối với mỗi trạng thái chuyển đổi X, ta kí hiệu số WCR ở trạng thái (2) là Ex, trong đó . Như vậy, ở trạng thái X, tuyến Ra được chia thành (Ex+1) đoạn : S0, S1, S3,..,SEx. Mỗi đoạn sử dụng một cùng một bước sóng trên tất cả các kết nối thuộc đoạn này. : là xác suất có bước sóng chung còn rỗi trên đoạn . Một lightpath sẽ được thiết lập trên tuyến thành công nếu và chỉ nếu mỗi đoạn còn ít nhất một bước sóng chung còn rỗi. : kí hiệu xác suất nghẽn của tuyến cho trạng thái chuyển đổi X. được tính như sau: (4-8) Từ đó ta tính được xác suất nghẽn tuyến: (4-9) Trong đó P(X) là xác suất nghẽn ở trạng thái chuyển đổi X. Vì vậy để tính , ta phải tính và P(X). Đâu tiên ta xem xét cách tính- là xác suất có bước sóng chung còn rỗi trên đoạn . Nếu là đoạn có hai kết nối và thì xác suất có x bước sóng rỗi là và xác suất có y bước sóng rỗi . Giả sử biết trước, và , thì xác suất để tồn tại bước sóng chung kí hiệu là được tính theo công thức sau: (4-10) Trong đó: (4-11) Từ đó ta tính được cho đoạn chỉ có 2 bước nhảy : (4-12) Phân tích ở trên có thể mở rộng áp dụng để xác định cho đoạn có nhiều hai hai bước nhảy (h). Giả sử tập các kết nối Sk là . Dùng để biểu thị đoạn con (sub-segment) gồm các kết nối . Bằng cách coi đoạn Sk gồm đoạn con và kết nối , ta có thể tính được sử dụng công thức hồi quy sau: (4-13) Bây giời ta xem làm cách nào để tính P(X)- xác suất của trạng thái X trên tuyến Ra. Giả sử xác suất WCR thứ trên tuyến không có bộ chuyển đổi nào còn rỗi là , ta định nghĩa : (14)ố ta có : (4-15) Biến duy nhất mà ta chưa biết giá trị là . Đối với bất kỳ yêu cầu lightpath nào được chuyển đổi bước sóng tại node WCR thứ , có hai trường hợp xảy ra : (1)Trên tất cả các kết nối dọc theo tuyến đều còn một bước sóng chung rỗi, (2) không còn bước sóng chung còn rỗi, nhưng mỗi đoạn có một bước sóng chung còn rỗi. Chỉ có trường hợp thứ hai, bộ WC mới được đặt ở tại WCR, và chúng ta gọi các lightpath yêu cầu thiết lập chuyển đổi là lưu lượng chuyển đổi. Gọi là lưu lượng chuyển đổi tổng cộng qua node WCR thứ . Theo như thuật toán gán bước sóng, một lightpath được chấp nhận sử dụng chuyển đổi bước sóng được con là lưu lượng chuyển đổi. Hơn nữa xác suất không có bước sóng chung còn rỗi nào trên tất cả các kết nối của tuyến là , nếu ta coi tuyến là một đoạn đơn. Do vậy có thể được tính theo công thức : (4-16) Giả sử số bộ chuyển đổi tại node WCR thứ n là , ta có lấy xấp xỉ lưu lượng chuyển đổi đến node WCR thứ n theo quá trình Poisson với tốc độ , tạo thành hệ thống M/M/m/m với servers. Từ đó ta rút ra được xác suất - xác xuất node WCR thứ n không có bộ chuyển đổi bước sóng còn rỗi : (4-17) Thuật toán số học dùng để giải các phương trình phi tuyến như sau : - Bước 1 : Khởi tạo =0 cho tất cả các tuyến, và cho tất cả các kết nối - Bước 2 : Xác định từ biểu thức (4-4) cho tất cả các kết nối - Bước 3 : Xác định sử dụng biểu thức (4-2) và (4-3) cho tất cả các kết nối - Bước 4 : Xác định cho tất cả các tuyến sử dụng các biểu thức (4-8)-(417). Nếu giá trị mới của hội tụ vào fias trị cũ, thì quá trình lặp dừng lại và chuyển sang bước (5), nếu không quay lại bước 2 cho một quá trình lặp tiếp theo - Bước 5 : Cuối cùng xác định xác suất nghẽn tổng cộng B sử dụng biểu thức (4-1) B- Thuật toán phân bổ cho mạng SPWC Một vấn đề rất quan trong trong cấu trúc mạng SPWC là việc đặt các bộ chuyển đổi bước sóng. Thông thường, bài toán này chỉ được đặt vào trường hợp mạng có bộ chuyển đổi bước sóng đặt rời rạc, với khả năng chuyển đổi đầy đủ (Sparse-complete). Trong cấu trúc SPWC, bài toán xác định vị trí đặt tối ưu gồm hai bài toán con: (1)- Xác định các node sẽ được đặt WCR, và (2)- Với tổng số M bộ chuyển đổi, thì mỗi node được đặt bao nhiêu bộ chuyển đổi. Dưới đây là mô hình dựa trên mô phỏng để giải hai bài toán này. ý tưởng cơ bản để giải bài toán: Đầu tiên ta thực hiện mô phỏng cho mạng Full-Complete. Từ kết quả mô phỏng ta quan sát được có bao nhiêu chuyển đổi bước sóng được thực hiện tại mỗi node. Từ đó, ta thu được kết quả thống kê hai tham số cho mỗi node thứ sau: 1) : Số bộ chuyển đổi bận trung trình 2) : Số bộ chuyển đổi cực đại Từ đó ta dễ dàng quyết định sẽ đặt nhiều bộ chuyển đổi hơn lên các node có các giá trị A(n) và P(n) lớn. Thuật toán RWA được sử dụng để thiết lập một lightpath cho mạng là thuật tìm đường đi ngắn nhất và gán bước sóng phù hợp đầu tiên (Shortest Path Routing and First Fit) được mô tả như sau qua các bước sau: Bước 1: Khi nhận được yêu cầu thiết lập lightpath giữa hai node (nguồn và đích), mạng sẽ tìm đường đi ngắn nhất giữa hai node đó. Bước 2: Trên tuyến ngắn nhất này, nếu có bất kì kết nối nào không còn bước sóng rỗi, thì yêu cầu lightpath sẽ bị từ chối (nghẽn). Bước 3: Nếu tồn tại bước sóng chung rỗi trên tất cả các kết nối của tuyến, thì mạng sẽ chọn bước sóng chung còn rỗi có chỉ số nhỏ nhất cho mỗi kết nối để thiết lập lightpath yêu cầu (thuật gán bước sóng First-Fit) Bước 4: Nếu không, đối với mỗi liên kết, sử dụng mô hình gán bước sóng phù hợp đầu tiên. Nếu hai kết nối liên tiếp sử dụng các bước sóng khác nhau, thì mạng phải sử dụng một bộ chuyển đổi bước sóng tại node WCR trung gian giữa hai kết nối này. Đánh giá chất lượng thuật toán qua mô phỏng Trong [3] đã thực hiện mô phỏng mạng NSFNET 14 node, mỗi kết nối mang 40 bước sóng, yêu cầu thiết lập lightpath 1.000.000 được sinh ra liên tục. Tổng lưu lượng của mạng 200Erlangs được phân bố đều cho tất cả các cặp node. Thuật toán định tuyến và gán bước sóng SP-FF được thực hiện như mô tả ở trên. Kết quả mô phỏng được cho ở bảng 3.10 dưới đây. Thống kê chuyển đổi bước sóng của mạng NSFNET 14 node Từ các giá trị A(n) và P(n) trong bảng 3.8, ta có thể thấy rằng hiệu suất sử dụng các bộ chuyển đổi bước sóng rất thấp. Nhìn chung, một node bậc cao hơn có nhiều lưu lượng cần chuyển đổi (bypassing traffic) hơn, nên cần sử dụng nhiều bộ chuyển đổi hơn. Mặc dù giá trị đỉnh của số bộ chuyển đổi bước sóng sử dụng đồng thời rất lớn, nhưng trong hầu hết thời gian mô phỏng chỉ một phần nhỏ trong số đó là bận. Để minh họa điều này, [3] đã đưa ra phân bố xác suất của số bộ chuyển đổi bận cho node 4 cho ở hình 3.20. Phân bố xác suất số bộ chuyển đổi Một trong những ưu điểm của SPWC là nó mang lại cho nhà khai thác dịch vụ khả năng nâng cấp dần dần lên FWC. Từ bảng 3.10, ta thấy rằng tại các node 4, 6, 7, 10 có nhiều chuyển đổi bước sóng xảy ra nhất. Các node 2, 9, 11, 12, 1, 5, 3 ít quan trọng hơn. Các node 8, 13, 14 gần như không cần chuyển đổi bước sóng. Dựa vào các thông tin này, nhà khai thác sẽ biết node cần đặt WC. Ví dụ ta chọn K={4, 6, 7, 10} để đặt WCR. Trong bước 2, đơn giản ta chỉ gán các bộ chuyển đổi vào các node trong tập K với số lượng tỉ lệ với A(n). Ví dụ ta có 50 bộ chuyển đổi, theo thuật phân bổ này các bộ chuyển đổi này được đặt như sau: Node n 4 6 7 10 Số WC đặt 16 13 11 10 Phân bổ các bộ chuyển đổi tại các node WCR Xác suất nghẽn mạng NSFNET với M=50 và M=100 "Nguồn: [3], trang 119" Hình 3.21a là xác suất nghẽn của mạng FPWC (Full-Partial Wavelength Converter) và SPWC trong các điều kiện tải khác nhau. Ta nhận thấy chuyển đổi bước sóng có thể làm giảm xác suất nghẽn xuống một mức rất lớn. So với 1.6000 bộ chuyển đổi sử dụng trong mạng FCWC (Full-Complete Wavelength Conversion), thì mạng FPWCvà mạng SPWC chỉ cần sử dụng có 50 bộ chuyển đổi là các thể đặt được chất lượng gần như ngang bằng. Chất lượng của mạng FPWC và SPWC gần như giống nhau trong trường hợp M=50. Tuy nhiên, rõ ràng là chất lượng của SPWC còn nằm dưới chất lượng mạng SCWC. Để minh họa cho điều này, [3] tiếp tục chuyển thêm một số node thành WCR, và thực hiện mô phỏng. Kết quả ở hình 3.21b cho thấychất lượng của mạng SPWC khi M=100 gần như trùng với M=50. Tuy nhiên chất lượng của FPWC được cải thiện và rất gần với chất lượng mạng FCWC. Thực tế nếu ta đưa thêm bộ chuyển đổi vào các node WCR, chất lượng của mạng FPWC sẽ tiến gần đến chất lượng của mạng FCWC. Nhận xét chung về các thuật giải phân bổ Thuật toán GA dựa trên cơ sở chọn một tổ hợp bất kì các bộ chuyển đổi bước sóng rồi so sánh các tổ hợp với nhau để tìm ra một tổ hợp tối ưu. Thuật toán sẽ rất phức tạp nếu số lượng các node lớn và sẽ mất rất nhiều thời gian để có được kết quả như mong muốn. Từ các nghiên cứu ở trên ta thấy rằng, để giải quyết một cách chính xác bài toán phân bổ bộ chuyển đổi bước sóng, chúng ta phải xem xét thuật toán RWA được sử dụng. Như thuật toán MBPF sử dụng tốt nhất với thuật toán định tuyến và gán bước sóng FAR, WMSL là cho LLR. Hai thuật toán phân bổ này khổng chỉ mang lại chất lượng tốt hơn nhiều so với các thuật giải tồn tại trước đó, mà còn đạt được chất lượng tương đương so với mạng FWC sử dụng cùng thuật toán RWA. Khi có mặt bộ chuyển đổi bước sóng trong mạng truyền dẫn toàn quang, kết quả mô phỏng cho thấy các thuật toán định tuyến động hiện đang có không tận dụng tài nguyên tuyến quang một cách hiệu quả. Thuật toán định tuyến WLCR là loại định tuyến động, xem xét kết hợp cả phân bố các bước sóng rỗi và chiều dài mỗi tuyến để đưa ra đường đi phù hợp nhất. Kết quả mô phỏng chỉ ra rằng, thuật giải WLCR-FF đạt được xác suất nghẽn tốt hơn nhiều trong mạng SWC hoặc FWC. Để tiết kiệm số bộ chuyển đổi bước sóng phải sử dụng, mô hình mạng SPWC (Sparse-Partial Wavelength Conversion) đã được chứng minh là mang lại chất lượng tốt với hiệu quả chi phí cao nhờ sự kết hợp các ưu điểm của mạng SWC và bộ chuyển đổi bước sóng một phần. Trong mạng này chỉ một số node là có khả năng chuyển đổi bước sóng, mỗi node này chỉ cố một số lượng hạn chế bộ chuyển đổi được trang bị. Bài toán gán bước sóng và bài toán đặt bộ chuyển đổi là hai yếu tố quan trong tiết kiệm số bộ chuyển đổi phải sử dụng. Cụ thể là chỉ sử dụng 1-5% số bộ chuyển đổi cần sử dụng trong FCWC, mạng SPWC có thể đạt được chất lượng gần sát với mạng FCWC. KếT LUậN Các mạng WDM toàn quang định tuyến bằng bước sóng đang trở thành kiến trúc đầy hứa hẹn tận dụng băng thông lớn của sợi quang, cung cấp các dịch vụ kênh bước sóng trong suốt (Transparent Lighpath Service). Để sử dụng hiệu quả các tài nguyên mạng, bao gồm tài nguyên bước sóng và tài nguyên chuyển mạch, các thuật toán định tuyến và gán bước sóng RWA phải được thiết kế cẩn thận. Chuyển đổi bước sóng được sử dụng chứng minh có thể cải thiện chất lượng mạng nhờ việc loại bỏ ràng buộc về tính liên tục bước sóng. Chi phí đầu tư và triển khai sẽ rất tốn kém nếu không sử dụng một thuật giải phân bổ bộ chuyển đổi bước sóng một cách hợp lí. Luận văn được trình bày gồm 3 chương: Chương 1: Tổng quan mạng truyền dẫn toàn quang Chương này trình bày tổng quan cấu trúc và một số công nghệ ứng dụng trong mạng toàn quang. Các công nghệ được đề cập đến như công nghệ chuyển mạch quang, công nghệ ghép kênh quang WDM. Chương 2: Định tuyến và gán bước sóng Do chất lượng của mạng phụ thuộc vào cả thuật toán định tuyến và gán bước sóng và thuật toán phân bổ bộ chuyển đổi. Do đó trước khi tìm hiểu các thuật toán phân bổ bộ chuyển đổi bước sóng, chương này sẽ trình bày bày nội dung của một số các thuật toán định tuyến và thuật toán gán bước sóng. Chương 3: Nghiên cứu phân bổ tối ưu bộ chuyển đổi bước sóng Trong chương này tác giả đã nêu ra vai trò của chuyển đổi bước sóng trong mạng truyền dẫn toàn quang, giới thiệu một số mô hình phân bổ bộ chuyển đổi và giới thiệu một số thuật giải phân bổ tối ưu đã được công bố. Tác giả có đưa ra một số kết quả nghiên cứu của các công trình nghiên cứu trên thế giới để có sự so sánh về chất lượng của các thuật giải này. Ngoài việc giới thiệu tổng quan về cấu trúc và một số công nghệ quan trọng trong mạng toàn quang, luận văn đã khái quát một cách tương đối đầy đủ các thuật giải phân bổ bước sóng được sử dụng với các thuật toán định tuyến và gán bước sóng cho các mô hình mạng Mesh và mạng Ring. Tác giả đã giới thiệu cách mô hình toán học mạng, cách tính xác suất nghẽn toàn mạng, và thuật toán phân bổ bộ chuyển đổi bước sóng. Sau khi nghiên cứu chi tiết từng thuật giải trên, tác giả đã rút ra một số nhận xét quan trọng khi xem xét bài toán phân bổ bộ chuyển đổi bước sóng trong mạng truyền dẫn toàn quang như sau: Phải xây dựng một thuật giải phân bổ riêng cho mỗi cấu trúc mạng (mesh, ring, ..) Chất lượng mạng phụ thuộc vào cả thuật toán RWA và thuật toán WCP. Tuy nhiên thuật toán RWA quyết định chủ yếu đến chất lượng mạng. Cấu trúc mạng full-complete có xác suất nghẽn nhỏ nhất. Tuy nhiên chỉ với số lượng bộ chuyển đổi hạn chế, được phân bố hợp lý tại các node mô hình mạng SPWC cũng có thể đạt chất lượng rất gần với mạng full-complete. TàI LIệU THAM KHảO [1]- Andre Soares, Jose Maranhao, William Giozza, Paulo Cunha, Fist Load Priority: A Wavelength Converter Placement Scheme for Optical Networks with Sparse-Partial Wavelength Conversion [2] Xiaowen Chu, Jiangchuan Liu, Zhensheng Zhang, Analysis of Sparse-Partial Wavelength Conversion in Wavelength-Routed WDM Networks. [3]- Chu, X. (2003). RWA and Wavelength Conversion in Wavelength-Routed All-Optical WDM Networks. PhD thesis, Hong Kong University. [4]- X.W. Chu, Bo Li, Zhensheng Zhang, A Dynamic RWA Algorithm in a Wavelength-Routed All-Optical Network with Wavelength Converter, 2003. IEEE INFOCOM. [5]- Xiao Hei, Jun Zhang, Chi-Chung Cheung, Brahim Bensaou “Wavelength Converter Placement in Least-Load Routing based Optical Networks using Genetic Algorithms”, 2003. [6]- A. Arora and S. Subramaniam, “Converter placement in wavelength routing mesh topologies,” in Proceedings of ICC, vol. 3, 2000, pp. 1282 –1288. [7]- X.W. Chu and B.Li, “Wavelength Converter Placement under the Fixed-Alternate Routing and First-Fit Wavelength Assignment Algorithm in All-Optical Networks”, SPIE/Kluwer Optical Networking Magazine, Special Issue on Engineering the Next Generation Optical Internet. [8]- E.Karasan and E. Ayanoglu, “Effects of Wavelength routing and selection algorithms on wavelength conversion gain in WDM optical networks”, IEEE/ACM Trans. Netw.6, 186-196 (1998). [9]- Achyut K.Dutta, Niloy K.Dutta, Masahiko Fujiwara, WDM Technologies Optical Networks, 2004, ELSEVIER Academic Press. Mục lục Lời cam đoan Mục lục Danh mục từ viết tắt Danh mục hình vẽ Danh mục bảng Mở đầu KếT LUậN Tài liệu tham khảo Danh mục hình vẽ Hình 1.1: Phổ suy hao của sợi quang - 5 - Hình 1.2: Bộ lọc và bộ ghép kênh - 9 - Hình 1.3: Bộ kết nối chéo cố định - 9 - Hình 1.4: Chuyển đổi bước sóng - 13 - Hình 1.5: Cấu tạo bộ khuêch đại EDFA - 15 - Hình 1.6: Đường cong độ lợi khuếch đại theo bước sóng - 16 - Hình 1.7: Sơ đồ khối của một bộ khuếch đại bán dẫn - 17 - Hình 1.8: Cấu trúc mạng định tuyến bước sóng DWDM - 19 - Hình 1.9: Cấu trúc một thiết bị đầu cuối OLT - 20 - Hình 1.10: Cấu tạo của một bộ OADM sử dụng FBG và hai bộ Circulator - 21 - Hình 1.11: Vai trò của OADM trong mạng 3 node - 22 - Hình 1.12: Các loại ROADM trong mạng toàn quang có thể cấu hình lại - 23 - Hình 1.13: Kết nối OXC với các phần tử khác - 26 - Hình 1.14: Một số cấu trúc OXC được triển khai - 27 - Hình 1.15: Node kết nối các bộ kết nối chéo lõi quang và chuyển mạch điện - 28 - Hình 1.16: Cấu trúc OXC cải tiến - 29 - Hình 1.17: Cấu trúc OXC mới nhất - 30 - Hình 1.18. Ung dụng của đường dẫn quang - 33 - Hình 1.19: IP over WDM - 35 - Hình 1.20: Giảm chi phí với hệ thống XC đường dẫn quang - 36 - Hình 1.21: Mở rộng dung lượng hệ thống chuyển mạch quang - 36 - Hình 1.22: Mô hình phân lớp với sự lặp lại chức năng - 37 - Hình 1.23: So sánh mạng định tuyến tín hiệu điện với mạng truyền dẫn quang - 38 - Hình 1.24: So sánh WP và VWP - 39 - Hình 1.25: Cấu hình chức năng của một node OXPC - 41 - Hình 1.26: Sơ đồ phát triển công nghệ điều khiển đường dẫn quang - 42 - Hình 1.27: Cấu trúc hệ thống chuyển mạch WP - 43 - Hình 1.28: Cấu trúc hệ thống chuyển mạch WP/VWP - 44 - Hình 1.29: Cấu trúc chuyển mạch song song - 45 - Hình 1.30: Cấu trúc chuyển mạch ma trận đầy đủ - 46 - Hình 1.31: Sơ đồ khối chức năng của một nút chuyển mạch gói - 47 - Hình 1.32: Các loại chuyển mạch không gian - 48 - Hình 1.33: Một ví dụ về cấu trúc chuyển mạch gói quang 3x3 - 50 - Hình 1.34: Một ví dụ về chuyển mạch gói đệm đầu ra - 51 - Hình 1.35: Cấu trúc chuyển mạch gói quang đầy đủ - 51 - Hình 2.1: Định tuyến và gán bước sóng lightpath trong mạng toàn quang - 53 - Hình 3.1: Thiết lập lightpath đơn giản - 61 - Hình 3.2: Các cấu trúc node chuyển đổi bước sóng đầy đủ - 63 - Hình 3.3: Cấu trúc node chuyển đổi bước sóng một phần - 63 - Hình 3.4: Các đoạn trên tuyến từ nguồn (S) đến đích (D) - 67 - Hình 3.5: Mạng 6 node, chỉ có một node là WCR - 70 - Hình 3.6: So sánh chất lượng của các thuật toán RWA và WCP - 78 - Hình 3.7: Chất lượng mạng thuật toán GA với số WC khác nhau - 78 - Hình 3.8: Cách phân bổ bộ chuyển đổi bước sóng theo MBPF - 79 - Hình 3.9: Một tuyến và các đoạn dọc theo - 81 - Hình 3.10: Chuỗi Markov cho phân bố bước sóng rỗi trên kết nối thứ j - 82 - Hình 3.11: X/s nghẽn theo số node WCR trong mạng ring, FAR-FF - 89 - Hình 3.12: X/s nghẽn theo số node WCR trong mạng mesh-torus, LLR-FF - 90 - Hình 3.13: X/s nghẽn theo lưu lượng trong mạng NSFNET 14 node, FAR-FF - 92 - Hình 3.14: Xác xuất nghẽn theo tải Erlang của mạng EON 19 node, FAR-FF - 93 - Hình 3.15: Xác suất nghẽn mạng NSFNET 14 node, LLR-FF - 95 - Hình 3.16: X/s nghẽn mạng EON 19 node, LLR-FF - 95 - Hình 3.17: Xác suất nghẽn mạng Ring 8 node và mesh-torus 25 node - 105 - Hình 3.18: Xác suất nghẽn của mạng NSFNET-14 node - 106 - Hình 3.19: Một lightpath và các phân đoạn của nó - 113 - Hình 3.20: Phân bố xác suất số bộ chuyển đổi - 118 - Hình 3.21: Xác suất nghẽn mạng NSFNET với M=50 và M=100 - 119 - Danh mục bảng Bảng 1.1: So sánh các loại ROADM - 24 - Bảng 1.2: Các công nghệ kênh ghép kênh - 32 - Bảng 3.1: Chi phí các đoạn, tuyến cho lightpath từ node S đến node D - 71 - Bảng 3.2: Trao đổi đồng nhất không hợp lệ - 74 - Bảng 3.3: Trao đổi đồng nhất hợp lệ - 75 - Bảng 3.4: Hoán đổi một vị trí - 75 - Bảng 3.5: Phân bổ WC đưới các thuật giải TOT, K-MDS và GA - 77 - Bảng 3.6: Vị trí đặt các WC trong 14-node NSFNet với 2 và 5 bộ WC - 94 - Bảng 3.7: Vị trí đặt các WC trong mạng 19-node EON với 2 và 5WC - 94 - Bảng 3.8: Lưu lượng mạng NSFNET có thể phục vụ với x/s nghẽn 2% - 110 - Bảng 3.9: Giá trị và của mạng NSFNET có tổng lưu lượng 208Erlangs - 112 - Bảng 3.10: Thống kê chuyển đổi bước sóng của mạng NSFNET 14 node - 118 - Bảng 3.11: Phân bổ các bộ chuyển đổi tại các node WCR - 119 -