Đồ án Nguyên lý ghép kênh quang theo bước sóng WDM

bước sĩng. Một trong những phương thức hứa hẹn và được áp dụng rộng rãi là bảo vệ dùng chung, trong đĩ, 2 hay nhiều tuyến quang hoạt động sẽ sử dụng chung tuyến dự phịng miễn là các tuyến này tách rời nhau. 4.1.2. Phương thức khơi phục Phương thức khơi phục là một cách khác để phục hồi dữ liệu sau sự cố. Ở phương thức này, các đường dự phịng được xác định một cách linh động tuỳ thuộc vào sự cố xảy ra. Một khi đã thiết lập được tuyến quang dự phịng, lưu lượng trên tuyến quang hoạt động sẽ ngay lập tức được chuyển sang tuyến này. Khơng giống như phương thức bảo vệ, phương thức khơi phục khơng chiếm dụng tài nguyên bước sĩng cho tuyến dự phịng trước khi sự cố xảy ra. Bởi vậy hiệu quả sử dụng tần số sẽ lớn hơn rất nhiều nếu so sánh với phương thức bảo vệ. Tuy nhiên, phương thức này cĩ thể khơng thiết lập được tuyến dự phịng nếu nguồn tài nguyên bước sĩng đã sử dụng hết. Điều này cĩ nghĩa là phương thức khơi phục khơng thể đảm bảo được 100% khả năng khơi phục mạng khi gặp sự cố. Hơn nữa, ở phương thức này, do các tuyến dự phịng được xác định sau khi sự cố xảy ra nên cần cĩ thời gian để hồi phục dữ liệu. 4.1.3. Bảo vệ SLSP (Short Leap Shared Protection) a. Nhĩm liên kết cĩ chung rủi ro (SRLG) SRLG là tham số đặc trưng cho trạng thái của một liên kết, nĩ thể hiện mức độ sẵn sàng sử dụng (khả dụng) của nguồn tài nguyên dự phịng đối với một tuyến hoạt động. Người ta quy định rằng hai tuyến hoạt động cĩ cùng nguy cơ xảy ra sự cố thì khơng thể dùng chung cùng nguồn tài nguyên dự phịng. Tính tốn SRLG đối với một liên kết hoặc một nút là nhận dạng nguồn tài nguyên mạng khơng thể sử dụng cho mục đích dự phịng cho các tuyến hoạt động mới được thiết lập cĩ sử dụng nút hoặc liên kết đĩ. Mục đích của các ràng buộc SRLG là đảm bảo khả năng khơi phục 100% sự cố đối với các nút hoặc các liên kết của mạng. Đối với phương thức bảo vệ dùng chung, khi các tuyến hoạt động và dự phịng cĩ bước sĩng khác nhau, nghĩa là bước sĩng của các tuyến này ở các mặt phẳng bước sĩng khác nhau, ràng buộc SRLG làm hạn chế hiệu suất mạng hơn so với khi các tuyến này cĩ cùng bước sĩng. Rõ ràng là tình huống thứ nhất (nghĩa là trường hợp bước sĩng giống nhau) cho hiệu quả sử dụng tài nguyên tốt hơn trường hợp thứ 2 do việc sử dụng bước sĩng mềm dẻo hơn. Tuy nhiên trường hợp thứ nhất cần sử dụng thêm các bộ thu phát khả chỉnh (tunable) và các bộ khuếch đại quang tại mỗi nút nên chi phí cao. Ở trường hợp sau, ràng buộc SRLG chỉ tồn 47 tại nếu hệ thống cĩ nhiều sợi quang, khi đĩ hai hay nhiều bước sĩng trên cùng mặt phẳng bước sĩng cĩ thể cĩ cùng SRLG. b. Mơ tả SLSP SLSP là phương thức bảo vệ dùng chung đầu cuối-đến-đầu cuối được phát triển dựa trên phương thức bảo vệ dùng chung theo tuyến và theo liên kết để cung cấp dịch vụ chất lượng hơn và giảm nghẽn trên mạng. Ý tưởng chính của SLSP là chia nhỏ tuyến hoạt động thành các đoạn (segment) cĩ chiều dài bằng nhau và chồng lấn lên nhau, mỗi tuyến được gán (gán theo nút nguồn) một chỉ số nhận dạng miền bảo vệ (ID) như chỉ ra trên hình 4.2. Kích thước của miền bảo vệ (hay miền P) được định nghĩa bằng số chặng trên tuyến ngắn nhất giữa PSL và PML trong miền P. SLSP thực hiện tiến trình khơi phục chỉ trong phạm vi miền P xác định trước thay vì trên tồn tuyến. Với việc chia nhỏ tuyến hoạt động thành các đoạn thì việc khơi phục cĩ thể được đảm bảo bằng cách giới hạn kích thước (hay tổng khoảng cách của đoạn tuyến hoạt động và dự phịng) mỗi tuyến hoạt động của miền P. Hình 4.2. Miền bảo vệ P trong bảo vệ SLSP Hình vẽ 4.2 minh hoạ một tuyến được thiết lập chế độ bảo vệ SLSP. Nút A là nút nguồn và nút N là nút kết cuối. Miền P thứ nhất (miền bảo vệ 1) bắt đầu ở nút A và kết thúc ở nút F. Miền bảo vệ 2 từ nút E tới nút J và miền bảo vệ P thứ 3 là từ nút I tới nút N. Trong trường hợp này các cặp nút (A,F), (E,J) và (I,N) tương ứng với các cặp nút nguồn đích trong mỗi miền P. Do mỗi miền P chồng lấn với miền P lân cận nĩ nên một lỗi đơn xuất hiện trên một liên kết hoặc một nút trên tuyến đều cĩ thể được xử lý tại ít nhất một miền P. Sau khi xuất hiện một lỗi trên tuyến hoạt động, nút nguồn của miền P được thơng báo để kích hoạt chức năng chuyển lưu lượng sang hướng dự phịng. Chẳng hạn, lỗi xuất hiện trên liên kết C-D hoặc trên nút C thì sẽ được khoanh vùng bởi nút F. Lỗi xuất hiện trên liên kết E-F hoặc trên nút F được khoanh vùng bởi nút J. Trong trường hợp thứ nhất, nút F gửi thơng tin báo cho nút A biết rằng đã xuất hiện lỗi trong miền P. Trong trường hợp thứ 2, nút J sẽ gửi thơng tin báo cáo nút E về sự cố. Sau khi nhận được thơng tin sự cố, nút nguồn (A hoặc E) sẽ gửi gĩi tin kích hoạt hướng dự phịng cho tất cả 48 các nút trên hướng dự phịng trong miền P đĩ. Sau đĩ, lưu lượng sẽ được chuyển sang hướng dự phịng. c. Phân bổ miền bảo vệ Người ta thường sử dụng thuật tốn thay thế thích nghi FAR để xác định đường cho tuyến hoạt động. Mỗi nút được trang bị bảng định tuyến chứa thơng tin về các tuyến tới tất cả các nút khác trong mạng, các tuyến này dự kiến được sử dụng như là các tuyến thay thế, trong đĩ số lượng các tuyến được chuẩn bị trước này tuỳ thuộc vào kích cỡ mạng. Khi cĩ yêu cầu kết nối, nút nguồn sẽ kiểm tra lại trong bảng định tuyến các tuyến thay thế từ bản thân nĩ tới nút đích, thử các bước sĩng khả dụng cho các tuyến thay thế và gán PSL và PML cho các tập nút tuỳ thuộc vào yêu cầu về tốc độ và thời gian khơi phục kết nối. Các nút được coi là PSL sẽ truy vấn thuật tốn định tuyến để cấp phát tuyến dự phịng và hình thành nên miền P. Sử dụng hình 4.2 làm ví dụ minh hoạ. Giả sử rằng W1 là tuyến hoạt động đang sử dụng. Nút nguồn sẽ gán nút các PSL là nút E và I; các nút PML là F và J. Mỗi nút PSL, nghĩa là A, E và I sẽ tính tốn phần mạng dư thừa bằng cách loại bỏ khỏi mạng tồn bộ tuyến hoạt động (trừ nút PML tương ứng với nĩ) cũng như phần tài nguyên dự phịng khơng thoả mãn ràng buộc SRLG. Sau đĩ, PSL thực hiện thuật tốn tìm đường ngắn nhất để xác định đoạn tuyến bảo vệ trong miền P của nĩ. 4.1.4. Xác định định lượng chất lượng trong các phương thức hiện tại Đã cĩ rất nhiều nghiên cứu về cách thức thiết kế topo mạng cĩ tính đến bảo vệ. Phần lớn các nghiên cứu này đều tập trung tìm cách giảm thiểu số lượng bước sĩng cần thiết hoặc cực đại hố thơng lượng mạng. Phương thức bảo vệ dùng chung là một phương pháp hiệu quả để giảm số lượng bước sĩng cần sử dụng trong khi thiết kế mạng. Cĩ nhiều hướng nghiên cứu về vấn đề này, một trong những đề xuất cĩ thể là việc đưa ra các lớp đảm bảo (class) đặc trưng cho xác suất khơi phục lỗi. Một ý tưởng khác liên quan đến yêu cầu kết nối, theo đĩ, các kết nối cĩ yêu cầu lớp cao hơn sẽ được cung cấp dự phịng với xác suất khơi phục lỗi lớn hơn. Nếu định nghĩa về mặt bảo vệ, ta cĩ các lớp QoP sau: - Các tuyến quang phải được bảo vệ. - Các tuyến quang khơng phải bảo vệ. - Các tuyến quang cĩ thể bảo vệ hoặc khơng. - Các tuyến quang được bảo vệ với nỗ lực tốt nhất. - Các tuyến quang cĩ độ ưu tiên thấp. Nếu định nghĩa theo thời gian khơi phục, hay cịn gọi lại độ sẵn sàng, người ta phân ra các lớp QoP yêu cầu 99.999%, 99.99%, 99.9% hay 99% độ sẵn sàng. Như đã biết, rất nhiều tuyến dự phịng cĩ thể sử dụng chung tài nguyên mạng miễn là yêu cầu QoR của các kết nối được thoả mãn. Mỗi tuyến hoạt động Pm cĩ 49 thể cĩ 1 hoặc nhiều hoặc thậm chí khơng cĩ tuyến dự phịng. Mỗi tuyến dự phịng Qm được nhận dạng bởi số BLID (backup lighpath id) là bộ ba [nguồn, đích, số tuần tự]. Tuyến dự phịng cĩ các tham số sau: - Xác suất sử dụng (Um) là xác suất mà Qm được sử dụng, nĩ chính bằng xác suất lỗi βm của tuyến hoạt động tương ứng Pm. βm được tính bằng: ∏∏ − == −−−= 1 11 )1()1(1 N i mi N i mim µνβ với 0 ≤ νmi,µmi ≤ 1 (4.1) trong đĩ tuyến hoạt động Pm bao gồm N nút Vm1,Vm2,...,VmN và N-1 tuyến liên kết tương ứng là lm1,lm2,...,lmN. Khi đĩ νmi là xác xuất lỗi của Vmi và µmi là xác suất lỗi của lmi. Nếu bỏ qua khả năng sự cố xảy ra tại nút, ta cĩ: ∏− = −−= 1 1 )1(1 N i mim µβ với 0 ≤ µmi ≤ 1 (4.2) - Mức độ khơng sẵn sàng (bm) là tổng xác suất lỗi của các phần tử mạng trên tuyến dự phịng Qm đang xét và tổng xác suất sử dụng của các tuyến dự phịng khác dùng chung ít nhất một liên kết với Qm: ∑∏∏ = − == +−−−= M i i N i mi N i mim Ub 1 1 11 )1()1(1 µν với 0 ≤ νmi,µmi ≤ 1, m∉ [1..M] (4.3) trong đĩ Qm dùng chung tài nguyên với M tuyến khác. Nếu bỏ qua khả năng sự cố xảy ra tại nút, ta cĩ: ∑∏ = − = +−−= M i i N i mim Ub 1 1 1 )1(1 µ với 0 ≤ µmi ≤ 1, m∉ [1..M] (4.4) - Mức độ khơng sẵn sàng sai lệch (Bm) là sai số lớn nhất của xác suất ở đĩ tuyến Qm khơng sẵn sàng bảo vệ. Nếu gọi Am là mức độ sẵn sàng yêu cầu của kết nối và của tuyến hoạt động Pm và cĩ N ≥ 1 tuyến dự phịng độc lập thì khi đĩ Bm được cho bởi: ∑ ≠= −= N mmii mim m m b AB ,1 1 β (4.5) - Cân bằng khả dụng (Rm) là xác suất sử dụng bổ sung cực đại cĩ thể được các tuyến dự phịng khác dùng chung một phần của Qm thêm vào: mmmm bUBR −−= (4.6) Các tham số đối với tuyến quang bước sĩng l được định nghĩa như sau: - xác suất sử dụng (ul): ∑ ∈∀ = mQl ml Uu (4.7) - cân bằng khả dụng (rl): mQll Rr m∈∀= min (4.8) 50 - tuyến dự phịng bị chiếm được định nghĩa là tuyến dự phịng sử dụng bước sĩng l. Cũng cĩ thể cĩ sự tương quan giữa các tuyến hoạt động. Đối với 2 tuyến Pm và Pn, điều này được thể hiện bởi tham số rủi ro chung bậc 2, ξmn được định nghĩa là xác suất lỗi của các phần tử chung của Pm và Pn, Tương tự như vậy, cĩ thể tồn tại các tham số rủi ro chung bậc cao hơn. Dựa trên tham số rủi ro chung, tham số bảo vệ tương quan δmn được định nghĩa là ảnh hưởng của Qn đến mức độ khơng sẵn sàng của Qm và được cho bởi: m mnmnmmnm mn β ξξβξβδ +−−= ))(( (4.9) Khi cĩ yêu cầu sử dụng tuyến dự phịng, tất cả các liên kết chuẩn bị sử dụng tuyến dự phịng đĩ sẽ giảm độ cân bằng khả dụng (Rn) một lượng là δmn và tăng mức độ khơng sẵn sàng (bm) một lượng là δmn. Kết nối mới sẽ được chấp nhận nếu xác suất sử dụng (Um) của tuyến dự phịng mới Qm nhỏ hơn rl và độ khơng sẵn sàng (bm) của Qm nhỏ hơn Bm. Nghĩa là: mlm QlrU ∈∀≤ , (4.10) mm Bb ≤ (4.11) Bài luận này sẽ giới thiệu một đơn vị định lượng khác để định nghĩa QoS cĩ liên quan đến độ tin cậy. Đĩ là thời gian hồi phục tối đa giữa thời gian khi sự cố xảy ra cho đến khi lưu lượng được chuyển sang tuyến dự phịng. Đơn vị định lượng này được gọi là QoR (chất lượng tin cậy) và mục tiêu của bài tốn là cần xây dựng được cấu trúc mạng đảm bảo thời gian hồi phục cực đại tuỳ theo yêu cầu của người sử dụng. 4.2. QoR (chất lượng tin cậy) và xây dựng mơ hình thời gian hồi phục mạng 4.2.1. Phân loại QoS dựa trên thời gian hồi phục cực đại Theo định nghĩa QoR, mỗi lớp QoR được gắn liền với một thời gian hồi phục mạng nhất định. Và mỗi kết nối được đảm bảo mức bảo vệ với một thời gian khơi phục tương ứng. Người ta định nghĩa mức cao nhất của QoR, QoR1, là mức được đảm bảo với thời gian khơi phục tối thiểu. QoR∞ nghĩa là khơng cĩ bảo vệ. Mỗi mức QoRn được đảm bảo với một thời gian khơi phục nhất định ký hiệu RT(QoRn) và được xác định theo cơng thức sau: RT(QoRn) = a + b* f(n) (4.12) trong đĩ a, b và f(n) được xác định bởi nhà cung cấp mạng. Nhờ xác định f(n) mà các lớp QoR cĩ thể được diễn tả dưới dạng số học, hình học hoặc bất cứ dạng nào. Thơng thường, người ta diễn tả f(n) dưới dạng đơn giản sau: f(n) = n - 1 (4.13) 51 và a = Dmin chính là thời gian khơi phục cực tiểu, chỉ bao gồm thời gian chuyển mạch từ tuyến hoạt động sang tuyến dự phịng. b = Dscale là bước của thời gian khơi phục, bao gồm thời gian xử lý để truyền thơng tin sự cố và thời gian gán bước sĩng cho tuyến bảo vệ tại nút xuất hiện sự cố. Bảng 4.1. QoR (chất lượng tin cậy) QoR1 khơi phục lỗi trong thời gian Dmin QoR2 khơi phục lỗi trong thời gian Dmin + Dscale QoR3 khơi phục lỗi trong thời gian Dmin+ 2Dscale M M QoRn khơi phục lỗi trong thời gian Dmin+ (n-1)Dscale M M QoR∞ Khơng cĩ tuyến dự phịng Hình 4.3. Cấu hình topology của mạng với độ trễ 4.2.2. Chỉ tiêu QoR đối với mỗi cặp nút Cĩ 2 tuyến từ nút A đến nút F, ABCDEF và AGHF. Trễ truyền trên tuyến thứ nhất là 25ms cịn ở tuyến thứ 2 là 44ms. Trong trường hợp này, nếu cặp nút AF yêu cầu lớp QoR với thời gian khơi phục tối đa là 20ms thì khơng thể xác định được tuyến quang thoả mãn yêu cầu đặt ra. Bởi vậy, người ta mở rộng khái niệm QoR sao cho cĩ thể luơn xác định được lớp QoR đối với mỗi cặp nút ij. Trước hết, người ta xác định thời gian hồi phục tối thiểu cho nút ij. Nĩ được tính bằng thời gian truyền từ nút i đến j, trễ chuyển mạch bảo vệ tại các nút.... Sau đĩ, thời gian hồi phục tối thiểu được xác định bằng thời gian hồi phục cấp cao nhất đối với cặp nút 12 và được ký hiệu QoR12(1). Tiếp theo, thời gian hồi phục cho các lớp thấp hơn, QoR12(2), QoR12(3),... cũng được xác định. Trong ví dụ ở bảng 4.2, các lớp QoR ban đầu A B C D E F G H 5ms 5ms 5ms 5ms 5ms 20ms 20ms 4ms 52 được xác định bởi phương trình (1). Đầu tiên, QoR12(1) đối với cặp nút 12 được ánh xạ bằng QoR3. Sau đĩ, các lớp QoR12(n) sẽ tiếp tục được ánh xạ bằng QoRn+2. Tất cả các cặp nút khác cũng cần được tính tốn tương tự. Sau đĩ, các QoRij đã ánh xạ sẽ được cung cấp cho người sử dụng và người sử dụng sẽ chọn QoRij(.) thích hợp. Bảng 4.2: QoR phụ thuộc vào cặp nút QoR Thời gian khơi phục cực đại QoR12 QoRij QoR1 Dmin - - QoR2 Dmin + 1*Dscale - QoRij(1) QoR3 Dmin + 2*Dscale QoR12(1) QoRij(2) QoR4 Dmin + 3*Dscale QoR12(2) ... QoRij(3) ... QoR5 Dmin + 4*Dscale QoR12(3) QoRij(4) M M M M QoR∞ khơng bảo vệ QoR12(∞) QoRij(∞) 4.2.3. Xây dựng mơ hình thời gian khơi phục Phần này sẽ minh hoạ cách thức xác định thời gian khơi phục. Hình vẽ số 4.4 chỉ ra tuyến quang hoạt động L được bảo vệ bởi nhiều tuyến dự phịng Px (1 ≤ x ≤ B), trong đĩ, B nhiều nhất bằng số nút trung gian mà tuyến hoạt động đi qua. Người ta cũng định nghĩa segment x (hay protection domain) là một phần của tuyến hoạt động Px giữa nút nguồn Sx và nút đích Dx. Hình 4.4. Phương thức bảo vệ SLSP Để đưa ra QoR đã mơ tả ở trên, cần thiết lập nhiều tuyến dự phịng sao cho thời gian khơi phục cực đại trên mỗi đoạn khơng vượt quá giá trị ngưỡng. Để phục vụ mục đích này, chúng ta sử dụng phương thức SLSP. Ở SLSP, các tuyến dự phịng được thiết lập để bảo vệ tuyến hoạt động sao cho bất kỳ 2 tuyến dự phịng nào segment 2 A B C D E F G H I J K segment 1 segment 3 segment 4 53 cũng cĩ một phần chồng lấn lên nhau (hình vẽ 4.4). Khơng giống như phương thức bảo vệ dùng chung, SLSP cho phép khơi phục trong trường hợp cĩ sự cố về thiết bị tại nút. Chẳng hạn, nếu cĩ sự cố tại nút D, nút C sẽ chuyển mạch lưu lượng sang tuyến dự phịng nối trực tiếp tới nút H. Đơn vị định lượng được xác định nhờ việc quy định chiều dài cực đại của tuyến dự phịng sao cho nhỏ hơn giá trị ngưỡng. Ở đây, ta sẽ xác định thời gian khơi phục tối đa đối với tuyến hoạt động L. Phương thức QoR đề xuất ở đây dựa trên việc xác định các tuyến dự phịng sao cho sao cho thời gian hồi phục tối đa trên mỗi đoạn nhỏ hơn giá trị ngưỡng cho trước. Ở đây, 2 đoạn lân cận nhau cũng được yêu cầu chồng lấn lên nhau để đảm bảo cĩ thể khơi phục mạng khi cĩ sự cố tại nút. Tiếp theo ta sẽ xây dựng mơ hình khơi phục mạng dựa trên hình vẽ 4.4. Khi xuất hiện lỗi trên đoạn x, thì nút gần thành phần bị lỗi sẽ gửi thơng tin cho nút trước nĩ để thơng báo thơng tin sự cố. Khi thơng tin này đến nút Sx, Sx sẽ dự trữ bước sĩng trên tuyến dự phịng Px bằng cách gửi tín hiệu dự trữ tới nút Dx qua các nút k, k+1, ...., k+Hx với Hx là số chặng trên tuyến dự phịng. Khi việc kích hoạt sang tuyến dự phịng thành cơng, nút Sx sẽ chuyển lưu lượng từ tuyến hoạt động sang Px. Như đã đề cập ở trên, thời gian khơi phục khi xảy ra sự cố phụ thuộc vào 3 yếu tố sau: - Trễ truyền thơng tin lỗi tới nút Sx. - Thời gian thiết lập để dự trữ bước sĩng tại mỗi nút của tuyến dự phịng Px. - Thời gian chuyển mạch lưu lượng từ tuyến hoạt động lỗi sang tuyến dự phịng Px. Bởi vậy, thời gian hồi phục tối đa khi lỗi xảy ra tại đoạn x (ký hiệu là RTx) được tính tốn như sau: ∑ = + ++×+= α xSk confxnodekkx DHDdRT )1()1( (4.14) trong đĩ Dnode là thời gian sử dụng để dự trữ bước sĩng tại mỗi nút trên tuyến Px, Dconf là thời gian chuyển mạch tại nút Sx. Ở phương trình (4.14), dij là trễ truyền thơng tin giữa nút i và nút j, cịn α là số chặng cực đại trên đoạn x. Nghĩa là:   <<− ≤−= ++ + xxxx xxx DSSS SDD 11 1 ,1 ,1α (4.15) Thời gian khơi phục cực đại đối với tuyến hoạt động L là thời gian cực đại của RTx đối với đoạn x, và được xác định bằng: }{max)( 1max xBx RTLRT ≤≤ = (4.16) 4.3. Xây dựng bài tốn thiết kế đảm bảo an tồn mạng Xét mạng kết nối bởi các liên kết quang 2 chiều, mỗi liên kết là một sợi cáp cĩ khả năng sử dụng W bước sĩng. Mỗi nút quang được trang bị thiết bị OXC và giả thiết rằng các nút OXC này khơng được trang bị các bộ chuyển đổi bước sĩng. 54 Lưu lượng giữa các nút cĩ thể đối xứng hoặc khơng đối xứng và nhỏ hơn hoặc lớn hơn dung lượng của một bước sĩng. Nếu khơng thể xác định được tuyến quang mang lưu lượng yêu cầu thì phần lưu lượng được coi là bị nghẽn (blocked). Ta sẽ sử dụng các ký hiệu sau: i,j: nút bắt đầu và kết thúc của mỗi liên kết logic m,n: nút kết cuối của mỗi liên kết vật lý. Đối với các liên kết vật lý: N: số nút của mạng W: số bước sĩng sử dụng Pmn: cấu hình vật lý được xác định bởi tập {Pmn}. Nếu giữa nút m và n tồn tại kết nối sợi quang thì Pmn = 1, nếu khơng thì Pmn = 0. Đối với mạng logic: Vij: số tuyến quang giữa nút i và j. k ijR : tuyến quang từ nút i đến nút j sử dụng bước sĩng k. Nĩ bao gồm một tập các liên kết vật lý (i, m1), (m1, m2),.., (mp, j). k ijA : tuyến quang dự phịng cho tuyến hoạt động tương ứng từ nút i đến j. Nĩ bao gồm một tập các liên kết vật lý (i, n1), (n1, n2),.., (nq, j). k ijc : nếu tuyến hoạt động sử dụng bước sĩng k trên hướng từ i đến j thì kijc = 1, nếu khơng thì kijc = 0. kijc được xác định từ kijR . k imno : nếu tuyến hoạt động trên đường nối mn sử dụng bước sĩng k thì kimno = 1, nếu khơng kimno = 0. kimno cĩ thể được xác định từ kijR . ϕmn: số lượng cực đại các tuyến dự phịng trên liên kết vật lý mn. wmn: số tuyến hoạt động trên tuyến vật lý giữa m và n. bmn: số tuyến dự phịng trên tuyến vật lý giữa m và n. w mnm : nếu tuyến dự phịng sử dụng bước sĩng w trên liên kết vật lý mn thì wmnm = 1, nếu khơng wmnm = 0 wmn kpqijg , ,, : nếu tuyến quang từ i đến j sử dụng bước sĩng k trên liên kết vật lý pq và sử dụng bước sĩng k giữa nút m và n thì wmn kpqijg , ,, = 1, nếu khơng wmn kpqijg , ,, = 0. Như vậy, bài tốn thiết kế mạng đảm bảo tiêu chí QoR cho trước cĩ thể được xây dựng dựa trên bài tốn tối ưu như sau: Thiết kế cấu hình mạng logic (xác định tuyến đường đi và gán bước sĩng) cĩ bảo vệ dựa trên mạng vật lý cho trước với các điều kiện sau: Đầu vào: - Cấu hình mạng vật lý gồm danh sách các nút, tuyến và chiều dài tuyến… - Ma trận lưu lượng, là tập các nhu cầu kết nối điểm-điểm. - Yêu cầu về chất lượng tin cậy QoR. Đầu ra: 55 - Bảng định tuyến cho mỗi luồng lưu lượng và bước sĩng gán cho mỗi luồng. - Tổng số bước sĩng cần thiết để phục vụ cho mạng. Hàm mục tiêu: Tối thiểu hố số bước sĩng sử dụng, nghĩa là: ∑ + nm mnmn bw , )(min (4.17) với các ràng buộc: - Số tuyến quang hoạt động trên tuyến vật lý mn phải bằng tổng số tuyến quang sử dụng bước sĩng w trên liên kết vật lý đĩ, nghĩa là: ∑ ∈ = Ww w mnmn ow (4.18) - Tương tự, số tuyến quang dự phịng trên liên kết vật lý mn phải bằng tổng các bước sĩng sử dụng cho mục đích dự phịng trên liên kết đĩ, nghĩa là: ∑ ∈ = Ww w mn mn mb (4.19) - Trên liên kết Pmn, hoặc là một tuyến hoạt động, hoặc là một tuyến dự phịng sử dụng bước sĩng k, nghĩa là: mn k mn k mn Pmo ≤+ (4.20) - Tuyến quang giữa nút i và nút j phải được bảo vệ bởi tuyến dự phịng khi liên kết pq∈ kijR bị sự cố. Cũng cần chú ý rằng khơng cần phải sử dụng các bước sĩng khác nhau đối với tuyến hoạt động và tuyến dự phịng tương ứng: ∑ ∑ ∈ ∈ = Ww Ait wit kpqij k ij k ij gc , ,, (4.21) - Điều kiện liên tục về bước sĩng: Tuyến quang giữa nút i và j sử dụng bước sĩng w phải cĩ cùng bước sĩng trên tất cả các liên kết của tuyến dự phịng của nĩ: wtm kpqij wnt kpqij gg , ,, , ,, = với kijkij AtmntRpq ∈∀∈∀ ,, (4.22) - Một tuyến quang sử dụng bước sĩng k giữa 2 nút logic i và j phải sử dụng cùng bước sĩng w trên liên kết vật lý mn ∈ kijA cho tuyến dự phịng: wmn kqpij wmn kqpij gg , ,, , ,, 2211 = với kijRqpqp ∈∀ 2211 , (4.23) - Số lượng tuyến dự phịng sử dụng bước sĩng k trên liên kết vật lý phải bị giới hạn: ∑ ∑ ∑ ∈ ∈> ∈ ≥ Ww Amncji Rpq kmn wpqij k mnmn k ij k ij k ij gm ),0(:),( , ,,ϕ (4.24) - Thời gian khơi phục mạng phải trong phạm vi ngưỡng QoR: RT < QoR (4.25) 56 4.4. Các thuật tốn thiết kế topo mạng thoả mãn yêu cầu QoR Phần này sẽ khái quát các thuật tốn thực nghiệm để thiết kế cấu trúc topo mạng thoả mãn yêu cầu QoR. Mục đích của thuật tốn là giảm thiểu số lượng bước sĩng cần thiết trong quá trình xây dựng cấu hình mạng, với giả thiết rằng lưu lượng và yêu cầu QoR đã cho trước. Các thuật tốn hoạt động theo các nguyên tắc chung sau: - Bước 1: Đối với mỗi cặp nút ij, ta thiết lập một đơn vị định lượng βij dựa trên QoRij(.), đơn vị định lượng này sau đĩ sẽ được sử dụng để xác định thứ tự của cặp nút cần gán bước sĩng. - Bước 2: Định tuyến và gán bước sĩng theo thứ tự giảm dần của đơn vị định lượng βij. Tuyến dự phịng được xác định trên cơ sở số chặng nhỏ nhất giữa nút nguồn Sx và nút đích Dx và yêu cầu phải tách rời khỏi tuyến hoạt động L. Lý do cho việc thiết lập các tuyến dự phịng dựa trên số chặng là bởi vì trong mơ hình đang xét, thời gian khơi phục phụ thuộc rất nhiều vào số chặng như chỉ ra trong phương trình 4.14. Hình 4.6. Điều kiện liên tục về bước sĩng Tiếp theo, cần gán bước sĩng cho tuyến dự phịng. Cần chú ý rằng ở đây khơng sử dụng bộ chuyển đổi bước sĩng, và bởi vậy, mỗi tuyến dự phịng chỉ sử dụng duy nhất một bước sĩng (tính ràng buộc về điều kiện liên tục của bước sĩng). Khi một tuyến dự phịng được thiết lập để bảo vệ cho một đoạn của tuyến L, thì phải gán cho tuyến này cùng bước sĩng với bước sĩng đang hoạt động trên L bởi vì tuyến dự phịng này sẽ là một phần của tuyến hoạt động khi sự cố xảy ra (hình λ1 λ1 λ1 λ1 λ1 λ1 λ1 λ2 λ1 8 λ1 λ1 λ1 λ1 λ1 λ2 57 4.6). Tuy nhiên, khi nút nguồn và đích của tuyến dự phịng hồn tồn tách rời khỏi L thì yêu cầu gán cùng bước sĩng là khơng cần thiết và tuyến hoạt động và tuyến dự phịng khơng cĩ chung liên kết nào. 4.4.1. Thuật tốn First-Fit Thuật tốn First-Fit đầu tiên sẽ định tuyến cho tuyến hoạt động và tuyến dự phịng. Đây thực chất trở thành bài tốn tổ hợp xác định tuyến tối ưu cho cả tuyến hoạt động và tuyến dự phịng. Để đơn giản hố thuật tốn, tuyến hoạt động thường được xác định theo các tuyến cĩ trễ giữa các nút nhỏ nhất, trong khi tuyến dự phịng được thiết lập trên các tuyến cĩ số chặng là nhỏ nhất. Sau khi tuyến hoạt động và dự phịng đã được xác định, bước sĩng được gán cho mỗi tuyến dựa trên chính sách First-Fit (FF). Nguyên tắc FF cĩ thể được diễn dịch như sau: Khi thuật tốn tính tốn được cĩ nhiều bước sĩng {λi1, λi2, ...., λin, với i1 < i2 < .... < in} cĩ thể sử dụng cho tuyến, nĩ sẽ chọn bước sĩng cĩ chỉ số nhỏ nhất (như vậy trong trường hợp này bước sĩng λi1 sẽ được chọn). Cần chú ý rằng việc gán bước sĩng phụ thuộc vào việc nút nguồn và đích của tuyến dự phịng cĩ tách rời khỏi tuyến hoạt động hay khơng, nghĩa là: - Nếu nút nguồn và đích tách rời thì tuyến hoạt động và tuyến dự phịng tương ứng cĩ thể sử dụng các bước sĩng khác nhau. Bởi vậy, thuật tốn trước hết sẽ tìm kiếm các bước sĩng khả dụng cho tuyến hoạt động. Sau đĩ bước sĩng dành cho tuyến dự phịng sẽ được xác định độc lập với bước sĩng của tuyến hoạt động (hình 4.6) - Nếu tuyến dự phịng chỉ bảo vệ cho một phần của tuyến hoạt động thì cả tuyến hoạt động và tồn bộ các tuyến dự phịng bảo vệ cho tuyến hoạt động đĩ phải được cấp phát cùng một bước sĩng để thoả mãn điều kiện liên tục bước sĩng. 4.4.2. Thuật tốn Max-Shared Ở thuật tốn Max-Shared, tuyến hoạt động và tập tuyến dự phịng được xác định trước sau đĩ mới gán bước sĩng cho các tuyến này. Thuật tốn định tuyến cho tuyến hoạt động và dự phịng giống như trong trường hợp thuật tốn First-Fit nghĩa là xác định tuyến hoạt động theo trễ nhỏ nhất và tuyến dự phịng dựa trên số chặng ít nhất. Điểm khác biệt giữa 2 thuật tốn chính là ở cách gán bước sĩng. Ở thuật tốn Max-Shared, tât cả bước sĩng được kiểm tra để gán cho tuyến hoạt động và dự phịng, và bước sĩng tốt nhất được chọn. Ứng với mỗi bước sĩng, thuật tốn sẽ đếm số liên kết mới được sử dụng cho tuyến dự phịng và coi số đếm này là chi phí của bước sĩng đĩ. Thuật tốn Max-Shared được coi là cĩ thể cải thiện hiệu quả sử dụng tài nguyên bước sĩng so với thuật tốn Firts-Fit. Đĩ là do thuật tốn này lựa chọn bước sĩng cần gán cho mỗi tập của tuyến hoạt động và dự phịng từ tồn bộ các bước sĩng được sử dụng để cực đại hố số bước sĩng cĩ thể dùng chung giữa các tuyến trong khi thuật tốn First-Fit lựa chọn ngay bước sĩng đầu tiên. 58 4.4.3. Thuật tốn thiết kế topo mạng dựa trên đồ thị phân lớp. Một đồ thị phân lớp bao gồm một tập các đồ thị bước sĩng Gn (1 ≤ n ≤ W), mỗi đồ thị tương ứng với một đồ thị cho một bước sĩng λn. Các đồ thị bước sĩng độc lập với nhau nếu bộ chuyển đổi bước sĩng khơng được sử dụng. Đồ thị phân lớp cho phép đồng thời xác định đường đi và bước sĩng của các tuyến nhờ tính tốn đường đi ngắn nhất cho mỗi tuyến. Hình 4.7 chỉ ra ví dụ về đồ thị phân lớp trong đĩ số bước sĩng sử dụng bằng W. Trong hình vẽ, các hình nét liền trên mỗi bước sĩng Gn chỉ ra rằng bước sĩng λn chưa được sử dụng trên liên kết, các hình nét đứt thể hiện bước sĩng λn đã được dành cho tuyến hoạt động hoặc tuyến dự phịng. Đơn vị cho mỗi cạnh của Gn chính là trễ truyền trên liên kết tương ứng. Để xác định bước sĩng gán cho mỗi tập tuyến hoạt động và dự phịng, người ta đưa vào khái niệm chi phí Cn cho mỗi bước sĩng λn, chính bằng số liên kết mới sử dụng bước sĩng λn cho tuyến hoạt động hoặc dự phịng. Thuật tốn được mơ tả như sau: Hình 4.7. Đồ thị phân lớp với số bước sĩng W - Bước 0: Gán w, là số bước sĩng cần thiết, bằng 0 - Bước 1: Đối với mỗi đường đi cĩ thể từ nút i đến nút j, thực hiện từ bước 2 đến bước 4. physical topology đồ thị phân lớp layered graph λ1 λ2 λW .... G1 G2 GW .... Graph G 59 - Bước 2: Cập nhật lại w bằng cách tính tốn lại các bước sĩng đã được sử dụng tại các liên kết. - Bước 3: Từ λ1 tới λw+1, tiến hành các bước sau (mỗi bước tương ứng với λn) ƒ Bước 3.1: Kiểm tra xem liệu tuyến chỉ bao gồm các bước sĩng chưa sử dụng giữa nút i và j trên đồ thị Gn khơng. Nếu khơng tồn tại tuyến như vậy thì quay lại bước 3 và kiểm tra bước sĩng tiếp theo trên đồ thị Gn+1. Nếu cĩ thì tuyến hoạt động, ký hiệu Lij cĩ thể được thiết lập với bước sĩng hoạt động λn và cập nhật lại đơn vị trên các cạnh của Gn. Nghĩa là các liên kết tương ứng trên Lij bị xố khỏi Gn và đặt npC chính bằng số liên kết bị xố đi. ƒ Bước 3.2: Dựa trên SLSP, thiết lập tập các tuyến dự phịng {P1, P2,..., Pn} thoả mãn các yêu cầu QoRij. Để phục vụ cho mục đích này, đường đi của các tuyến dự phịng được xác định sao cho tuyến dự phịng tách biệt khỏi tuyến hoạt động Lij tương ứng và số chặng trên tuyến là tối thiểu. Để 2 điều kiện trên được thoả mãn, đầu tiên cần tính tốn chi phí nrC là chi phí để gán bước sĩng λn cho tuyến dự phịng Pr (1 ≤ r ≤ k) và xác định tập các tuyến dự phịng cho Lij. o Bước 3.2.1: Nếu nút nguồn và đích của của Pr là đồng nhất đối với các nút của Lij thì cĩ thể thử gán cho Pr bất kỳ bước sĩng λi nào (với 1 ≤ i ≤ w+1). Nếu tuyến dự phịng chỉ bảo vệ từng phần của Lij, tiến hành bước 3.2.2. của thuật tốn đối với đồ thị Gn để thoả mãn điều kiện liên tục của bước sĩng. o Bước 3.2.2: Nếu tuyến dự phịng Pr cĩ thể thiết lập trên đồ thị Ge, chi phí của Pr được xác định bằng số liên kết mới được sử dụng trên Ge, chi phí này được đặt bằng Ce. Sau khi kiểm tra tất cả các bước sĩng (nghĩa là từ G1 đến Gw+1), chọn e’ ở đĩ chi phí Ce’ tương ứng với Ge’ là tối thiểu. Sau đĩ, đặt Ce’ bằng n rC . ƒ Bước 3.3: Đặt ∑ = +← k r n r n p n CCC 1 , trong đĩ Cn là chi phí để thiết lập bước sĩng λn cho cả tuyến hoạt động và tuyến dự phịng giữa nút i và j. Quay trở lại bước 3. - Bước 4: Chọn a sao cho Ca là giá trị nhỏ nhất trong số {C1, C2,.....Cw+1} và gán bước sĩng λa cho Pa. Sau đĩ gán λe’ đã tính tốn ở bước 3.2.2 cho tuyến dự phịng. Thuật tốn sẽ lần lượt tính tốn chi phí của việc gán bước sĩng cho tuyến hoạt động và tuyến dự phịng ở bước 3.1 và 3.2. Bước 3.3 tính tốn chi phí nrC cho 60 tuyến r ở bước sĩng λn với chi phí ở đây là số bước sĩng mới được sử dụng. Bước 3 xác định số bước sĩng thực sự được sử dụng tương ứng với chi phí cho việc gán các tuyến hoạt động và dự phịng là nhỏ nhất, và thiết lập tuyến quang với bước sĩng λa. Cần chú ý rằng thuật tốn sẽ đếm số bước sĩng cần sử dụng w. Tuy nhiên, khi số bước sĩng cần sử dụng được cho trước bằng W thì từ bước 3.1 đến 3.4 sẽ thực hiện kiểm tra các bước sĩng từ λ1 đến λw. Tồn bộ thuật tốn được mơ tả dưới dạng lưu đồ như sau: 61 Hình 4.8. Lưu đồ của thuật tốn đồ thị phân lớp 62 4.5. Đánh giá thuật tốn 4.5.1. Mơ hình mạng Ở đây, ta sử dụng mơ hình NSFNET 14 nút (hình 4.9) và ma trận lưu lượng (bảng 4.3) để đánh giá 3 thuật tốn đã đưa ra. Ở đây, ta đưa ra hệ số biến đổi lưu lượng γ và coi rằng yêu cầu lưu lượng thực tế sẽ bằng ma trận đã cho nhân với hệ số γ. Đơn vị của ma trận lưu lượng ở bảng 4.3 được tính bằng Gbps. Dung lượng của mỗi bước sĩng là 10Gbps và các kết nối yêu cầu dung lượng lớn hơn mức này sẽ được gán nhiều hơn 1 bước sĩng để mang lưu lượng. Khi nhiều hơn một bước sĩng được gán cho một kết nối, các tuyến tương ứng với các bước sĩng sẽ được định tuyến theo cùng đường đi. Giả thiết rằng ta sẽ sử dụng các giá trị Dmin = 5ms, Dscale = 1ms, Dnode = 1ms và Dconf = 0ms. Hình 4.9. Mạng NSFNET 14 nút 63 Bảng 4.3. Ma trận lưu lượng cho mạng đang xét A B C D E F G H I J K L M N A 0.000 0.109 0.206 0.014 0.045 0.004 0.043 0.145 0.051 0.010 0.007 0.008 0.000 0.033 B 1.171 0.000 0.856 0.062 1.112 0.777 0.362 1.579 0.366 1.661 0.203 3.781 0.483 1.319 C 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 D 0.031 0.341 1.364 0.000 0.190 0.060 0.070 0.288 0.200 0.326 0.307 0.669 0.008 0.401 E 0.028 6.751 1.902 0.343 0.000 0.403 1.077 6.222 2.402 1.792 0.045 7.903 0.997 0.529 F 0.000 0.581 0.342 0.552 0.340 0.000 0.261 0.268 0.087 0.387 0.004 0.084 0.006 0.248 G 0.175 2.202 1.231 0.447 2.203 0.790 0.000 7.410 1.982 2.195 0.078 7.140 0.033 3.284 H 0.239 6.384 2.030 0.852 2.821 0.266 9.708 0.000 4.395 3.300 1.137 4.863 0.553 1.385 I 0.645 1.893 3.735 0.600 2.499 0.681 2.506 6.102 0.000 3.962 1.452 2.750 2.334 0.076 J 0.005 3.529 1.026 0.373 2.234 0.948 0.498 5.708 0.684 0.000 0.630 1.764 0.591 0.076 K 0.010 0.102 0.313 0.169 0.024 0.006 0.081 0.145 0.058 0.712 0.000 0.084 0.006 0.050 L 0.128 2.615 0.100 0.594 2.486 0.132 0.549 4.057 2.953 2.237 1.050 0.000 0.101 0.054 M 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 0.000 N 0.073 2.909 1.363 0.989 3.561 1.207 0.644 2.879 0.467 0.000 0.399 0.000 1.075 0.000 64 4.5.2. Đánh giá kết quả Đầu tiên chúng ta sẽ tính tốn số bước sĩng cần thiết theo mỗi thuật tốn trong trường hợp mỗi cặp nút ij yêu cầu cùng một QoRij. Cụ thể hơn, giả sử xét cặp nút 3,4 trong mạng NSFNET ở hình 4.9, nếu tuyến hoạt động được thiết lập là [D → E] và tuyến dự phịng là [D → B → C → F → E] thì thời gian khơi phục cực đại là: ∑ = + ++×+= α xSk confxnodekkx DHDdRT )1()1( = 2.8 + 1*4 + 0 = 6.8ms. Nếu tuyến quang được thiết lập theo đường khác thì thời gian khơi phục cực đại sẽ lớn hơn 6.8ms. Bởi vậy, 6.8ms là giá trị thời gian khơi phục cực đại nhỏ nhất mà vẫn đảm bảo cho cặp nút 3,4. Ở đây, nếu Dmin và Dscale lần lượt bằng 5ms và 1ms thì thời gian khơi phục cực đại để đảm bảo QoR2 là 6ms và ở QoR3 là 7ms. Như vậy, QoR34(1) được ánh xạ bằng QoR2. Số bước sĩng cần sử dụng so với QoRij 0 10 20 30 40 50 60 70 80 QoRij(1) QoRij(3) QoRij(5) QoRij(7) QoRij(9) QoRij(11) QoRij(13) QoRij(15) QoRij(17) QoRij(19) Graph No protection Hình 4.10. Số bước sĩng cần sử dụng tương ứng với từng mức QoRij Ở ví dụ này, tất cả các cặp nút ij được giả thiết là yêu cầu mức QoR đồng nhất để dễ dàng chỉ ra mối quan hệ giữa QoRij và số bước sĩng cần thiết. Trên hình vẽ 4.10, trục hồnh chỉ thị mức chỉ tiêu chất lượng mà các cặp nút ij yêu cầu cịn trục tung chỉ thị số bước sĩng cần thiết để thiết lập các tuyến hoạt động/dự phịng thoả mãn tiêu chuẩn QoR đĩ. Trong đĩ đường ký hiệu “No protection” chỉ thị số bước sĩng cần sử dụng khi hệ thống khơng cĩ dự phịng. Ta cĩ thể nhận thấy, hệ thống cĩ hiệu quả ở mức QoRij = 5. Đĩ là bởi vì khi yêu cầu thời gian khơi phục nhanh (mức QoRij nhỏ) thì miền bảo vệ (protection domain) của mỗi tuyến sẽ được thu hẹp dần dẫn đến tài nguyên mạng cần sử dụng phải lớn, tương tự khi thời gian khơi phục dài (QoRij lớn), thì số chặng của tuyến dự phịng sẽ tăng lên nhiều do vậy bước sĩng cần sử dụng trong trường hợp này cũng lớn. 65 Hệ thống đạt được sự thoả hiệp tối ưu ở mức QoRij = 5. Khi đĩ, số bước sĩng cần sử dụng là thấp nhất và xác suất từ chối thiết lập kết nối khi khơng cĩ đủ tài nguyên bước sĩng cũng là nhỏ nhất (hình 4.11). Số kết nối bị từ chối (blocked) 0 20 40 60 80 100 120 Qo Ri j(1 ) Qo Ri j(3 ) Qo Ri j(5 ) Qo Ri j(7 ) Qo Ri j(9 ) Qo Ri j(1 1) Qo Ri j(1 3) Qo Ri j(1 5) Qo Ri j(1 7) Qo Ri j(1 9) W=20 W=40 W=50 Hình 4.11. Số kết nối bị từ chối khi giới hạn tài nguyên bước sĩng Trên hình vẽ 4.11. trục hồnh chỉ thị mức tiêu chuẩn QoRij yêu cầu tại mỗi cặp nút, cịn trục tung chỉ số kết nối khơng được cấp phát tài nguyên bước sĩng (bị từ chối) khi giới hạn số bước sĩng sử dụng W lần lượt bằng 20, 40 và 50. 66 4.6. Kết luận và các hướng nghiên cứu tiếp theo Bài luận đã giới thiệu được QoR là một khái niệm mới của QoS xét về độ tin cậy của mạng WDM. Cùng với khái niệm QoR, việc bảo vệ mạng khơng chỉ đơn thuần là xác định các tuyến dự phịng đảm bảo an tồn cho mạng, mà cịn là xác định tuyến dự phịng đảm bảo thoả mãn yêu cầu hồi phục mạng sau khoảng thời gian được yêu cầu bởi người sử dụng.Tương ứng với mỗi cặp nút nguồn đích ij, bài luận cũng đưa ra chỉ tiêu QoRij và dựa trên khái niệm này để đề xuất một thuật tốn thực nghiệm để thiết kế cấu hình logic cho mạng WDM với các phương thức bảo vệ thoả mãn tiêu chí QoRij. Mục đích của thuật tốn là giảm thiểu số bước sĩng cần sử dụng để mang thơng tin cũng như phục vụ mục đích bảo vệ. Các kết quả tính tốn được với lưu lượng giả định dựa trên thuật tốn này cũng cho thấy ......... Đây là một hướng nghiên cứu thú vị và vẫn cịn rất nhiều vấn đề cần tiếp tục được giải quyết. Trong bài luận này, các cặp nút nguồn đích ij được giả thiết cĩ yêu cầu mức QoR giống nhau trong khi trên thực tế lưu lượng giữa các nút sẽ yêu cầu các lớp QoR khác nhau. Bởi vậy thuật tốn sẽ phải tiếp tục phát triển để cĩ thể thiết kế cấu hình logic cho mạng với các mức QoR khơng giống nhau thậm chí cho cùng một cặp nút ij. Bài luận hiện nay cũng giả thiết lưu lượng lưu thơng trong mạng ở mức thấp và khả năng của thiết bị là hồn tốn đáp ứng được. Trong tương lai, khi lưu lượng tăng lên vượt quá dung lượng của thiết bị hiện thời, khi đĩ cần phân bổ cho các hướng cĩ lưu lượng cao khơng chỉ một mà phải 2, 3 hay tổng quát hơn là n bước sĩng. Như vậy vấn đề gán bước sĩng cho tuyến hoạt động và dự phịng sẽ phức tạp hơn. Đây là một chủ đề cần tiếp tục nghiên cứu để hồn thiện. Việc áp dụng bài tốn thiết kế mạng logic thoả mãn tiêu chí QoR đối với mạng cĩ sử dụng các bộ chuyển đổi bước sĩng cũng là một hướng nghiên cứu cần được triển khai. Một hướng nghiên cứu khả thi khác là về các nâng cao độ tin cậy của các lớp phía trên của WDM. Bài luận này đưa ra giả thiết rằng việc bảo vệ được thực hiện hồn tồn ở lớp WDM. Tuy nhiên, các lớp phía trên WDM cũng cĩ khả năng thức hiện chức năng bảo vệ, chẳng hạn như chức năng khơi phục ở lớp IP. i CÁC TỪ VIẾT TẮT ADM Add Drop Multiplexer Thiết bị xen/rẽ lưu lượng APS Automatic Protection Swtching Chuyển mạch bảo vệ tự động ASE Amplified Spontanneour Emission Bức xạ tự phát khuếch đại BER Bit Error Rate Tỉ lệ lỗi bit BLID Backup lighpath id Số nhận dạng tuyến dự phịng DP Dedicated Protection Bảo vệ dành riêng DSF Dispersion Shifted Fiber Sợi dịch tán sắc DXC Digital Cross Connection Đấu nối chéo số EDFA Erbium-Doped Fiber Amplifier Khuyếch đại quang sợi FAR Fixed Alternative Routing Định tuyến thích nghi cố định FWM Four-way mixing Trộn bốn sĩng IEC International Electrotechnical Committee Uỷ ban kỹ thuật điện quốc tế ILP Integer Linear Programming Quy hoạch tuyến tính nguyên ITU-T International Telecommunication Liên minh viễn thơng quốc tế LSR Label Switch Router Router chuyển mạch nhãn MS Multiplex Section Đoạn ghép kênh MSDPRING Multiplex Section Delicated Protection Ring Ring bảo vệ riêng đoạn ghép kênh MSP Multiplex Section Protection Bảo vệ đoạn ghép kênh MSSPRING Multiplex Section Sharing Protection Ring Ring bảo vệ chung đoạn ghép kênh NE Network Element Phần tử mạng OA Optical Amplifier Khuyếch đại quang OADM Optical Add Drop Multiplexer Thiết bị xen / rẽ quang OAM Operation Adminitration and Maintenance Khai thác quản lý và bảo dưỡng OCh Optical Channel Kênh quang OCH- DPRing Optical Channel Dedicated Protection Ring Ring dành riêng bảo vệ mức kênh quang OMS Optical Multiplex Section Đoạn ghép kênh quang OMS- DPRing Optical Multiplex Section Dedicated Protection Ring Ring bảo vệ riêng mức đoạn ghép kênh quang OMS- SPRing Optical Multiplex Section Shared Protection Ring Bảo vệ chung mức đoạn ghép kênh quang OTN Optical Transport Network Mạng truyền tải quang OTS Optical Transmission Section Đoạn truyền dẫn quang OTU Optical Transport Unit Khối truyền tải quang ii OXC Optical Cross-Connect Nối chéo quang PMD Polarization Mode Dispersion Tán sắc mode phân cực PML Path Merge Label switched router LSR ghép tuyến PSL Path Switch Label switched router LSR chuyển mạch tuyến REG Regenerator Trạm lặp RS Regenerator Section Đoạn trạm lặp SDH Synchronous Digital Hierachy Phân cấp số đồng bộ SLSP Short Leap Shared Protection Bảo vệ chung bước ngắn SNCP Sub-Network Connection Protection Bảo vệ kết nối mạng con SOH Section OverHead Mào đầu đoạn SP Shared Protection Bảo vệ dùng chung SPM Self-Phase Modulation Tự điều chế pha SRLG Shared risk link group Nhĩm liên kết chung rủi ro SRS Stimulated Raman Scattering Tán xạ kích thích Raman STM Synchronous Transport Module Modul truyền dẫn đồng bộ TDM Time Division Multiplexing Ghép kênh phân chia theo thời gian TMN Telecommunications Management Network Mạng quản lý mạng viễn thơng WC Wavelength Conversion Chuyển đổi bước sĩng WDM Wavelength Division Multiplexing Ghép kênh phân chia theo bước sĩng WL Wavelength Bước sĩng WP Wavelength Path Luồng quang (bước sĩng) WRA Wavelength Routing Assignment Định tuyến và gán bước sĩng XPM Cross-Phase Modulation Điều chế pha chéo iii TÀI LIỆU THAM KHẢO [1] Helsiki University of Technology, 1998, “Wavelength division multiplexing; an overview” [2] P.S.Andre, A.L.Teixeira, “Nonlinear refractive index and chromatic dispersion simultanously measurement in non-zero dispersion shift optical fibres” [3] Erland Almstrưm (1999), “Reconfigurable and transparent wavelength division multiplexed Optical networks, experiments, evaluation and designs” [4] NPL report COEM by R Billington (1999), “A Report on Four-Wave Mixing in Optical Fibre” [5] Andre Richter (2002), “Timing Jitter In Long-haul WDM Return-To-Zero Systems” [6] Mansoor Sheik-Bahae and Michael P.Hasselbeck, Department of Physics and Astronomy (2000), “Third order optical nonlinearities” [7] George N.Rouskas, “Routing and Wavelength Assigment in Optical WDM network”. [8] Pin Han Ho and Hussein T.Mouftah, “A framework for Service-guaranteed shared protection in WDM mesh networks”. [9] Guido Maier, Achille Pattavina, Simone De Patre và Mario Martinelli, “Optical Network Survivability: Protection techniques in WDM layer”, 2002 [10] Adrea Fumagalli and Luca Valcarenghi, University of Texas at Dallas, “IP restoration vs. WDM protection: Is there an optimal choice”, 2000 [11] Shin’ichi ARAKAWA, Masayuki MURATA and Hideo MIYAHARA, “Functional Partitioning for Multilayer Survivability in IP over WDM networks”, 1999. [12] Ori Gerstel and Galen Sasaki, “Quality of Protection (QoP): A Quantitive unifying paradigm to protection service grades”. [13] Chadi Assi, Ahmad Khali, Nasir Ghani, Abdallah Shami and Mohamed Ali, “Performance evalution of efficient shared path protection in mesh networks”. [14] Shuvendu Kumar Dang, University of Texas, 2004, “Quality of Protection (QoP) in WDM mesh networks”. [15] Shengli Yuan and Jason P.Jue, Department of Computer and Sience, University of Texas at Dallas, “Shared protection routing algorithm for Optical Networks” [16] Junichi Katou (2002), Osaka University, “Design Method for Logical Topologies with Quality of Reliability in WDM Networks”. iv MỤC LỤC MỞ ĐẦU ......................................................................................................................1 CHƯƠNG 1. TỔNG QUAN VỀ GHÉP KÊNH THEO BƯỚC SĨNG WDM........3 1.1. Sự phát triển của truyền dẫn sợi quang. .........................................................3 1.2. Cơng nghệ ghép kênh theo bước sĩng WDM................................................4 1.2.1. Lớp quang ...............................................................................................4 1.2.2. Nguyên lý ghép bước sĩng .....................................................................5 1.2.3. Các thành phần cơ bản trong hệ thống WDM ........................................7 1.3. Xuyên nhiễu .................................................................................................14 1.3.1. Suy hao .................................................................................................15 1.3.2. Tán sắc ..................................................................................................15 1.3.3. Các hiệu ứng phi tuyến .........................................................................17 1.4. Vấn đề thiết kế kỹ thuật trong mạng WDM.................................................20 1.4.1. Thiết bị trong mạng WDM ...................................................................20 1.4.2. Vấn đề thiết kế kỹ thuật trong mạng WDM .........................................23 1.5. Kết cuối chương ...........................................................................................24 CHƯƠNG 2. MẠNG QUANG ĐỊNH TUYẾN THEO BƯỚC SĨNG .................25 2.1. Giới thiệu......................................................................................................25 2.2. Định tuyến và gán bước sĩng tĩnh ...............................................................28 2.3. Định tuyến và gán bước sĩng động..............................................................30 2.4. Kết cuối chương ...........................................................................................34 CHƯƠNG 3. CÁC PHƯƠNG THỨC BẢO VỆ TRONG MẠNG WDM .............35 3.1. Nâng cao độ tin cậy trong lớp quang ...........................................................35 3.2. Bảo vệ mạng ring WDM..............................................................................38 3.3. Bảo vệ mạng mesh WDM............................................................................39 3.4. Kết cuối chương ...........................................................................................44 CHƯƠNG 4. THIẾT KẾ MẠNG WDM ĐẢM BẢO CHỈ TIÊU CHẤT LƯỢNG TIN CẬY QoR 45 4.1. Các phương thức nâng cao an tồn trong mạng WDM ...............................45 4.1.1. Phương thức bảo vệ. .............................................................................45 4.1.2. Phương thức khơi phục.........................................................................46 4.1.3. Bảo vệ SLSP (Short Leap Shared Protection) ......................................46 v 4.1.4. Xác định định lượng chất lượng trong các phương thức hiện tại .........48 4.2. QoR (chất lượng tin cậy) và xây dựng mơ hình thời gian hồi phục mạng ..50 4.2.1. Phân loại QoS dựa trên thời gian hồi phục cực đại ..............................50 4.2.2. Chỉ tiêu QoR đối với mỗi cặp nút.........................................................51 4.2.3. Xây dựng mơ hình thời gian khơi phục ................................................52 4.3. Xây dựng bài tốn thiết kế đảm bảo an tồn mạng......................................53 4.4. Các thuật tốn thiết kế topo mạng thoả mãn yêu cầu QoR..........................56 4.4.1. Thuật tốn First-Fit ...............................................................................57 4.4.2. Thuật tốn Max-Shared ........................................................................57 4.4.3. Thuật tốn thiết kế topo mạng dựa trên đồ thị phân lớp.......................58 4.5. Đánh giá thuật tốn ......................................................................................62 4.5.1. Mơ hình mạng.......................................................................................62 4.5.2. Đánh giá kết quả ...................................................................................64 4.6. Kết luận và các hướng nghiên cứu tiếp theo................................................66 MỤC LỤC .................................................................................................................. iv DANH MỤC CÁC HÌNH VẼ .................................................................................... vi DANH MỤC CÁC BẢNG BIỂU.............................................................................. vii vi DANH MỤC CÁC HÌNH VẼ Hình 1.1. Vùng bước sĩng ...........................................................................................3 Hình 1.2 Phân cấp mạng quang theo lớp .....................................................................4 Hình 1.3. Kiến trúc mạng truyền tải quang..................................................................4 Hình 1.4. Hệ thống ghép bước sĩng một hướng ..........................................................6 Hình 1.5.Hệ thống ghép bước sĩng hai hướng ............................................................6 Hình 1.6 OXC chuyển mạch sợi (a), OXC chuyển mạch lựa chọn bước sĩng (b) và chuyển mạch trao đổi bước sĩng (c)...........................................................................22 Hình 2.1. Mạng định tuyến theo bước sĩng...............................................................25 Hình 2.2. OXC 3x3 với 2 bước sĩng trên 1 sợi quang...............................................26 Hình 2.3. Các kiểu biến đổi bước sĩng ......................................................................27 Hình 3.1 Phân loại các phương thức bảo vệ đảm bảo duy trì mạng ..........................37 Hình 3.5. Các cấu hình mạng khác nhau khi xảy ra sự cố đối với w1 và w2 ..............40 Hình 3.6. Bảo vệ theo tuyến trong mạng hình luới ....................................................41 Hình 3.7. Kỹ thuật bảo vệ double-cycle-cover ..........................................................42 Hình 3.8. Bảo vệ p-cycle............................................................................................43 Hình 3.9. Bảo vệ generalized loopback .....................................................................43 Hình 4.1. Các phương thức bảo vệ.............................................................................45 Hình 4.2. Miền bảo vệ P trong bảo vệ SLSP .............................................................47 Hình 4.3. Cấu hình topology của mạng với độ trễ .....................................................51 Hình 4.4. Phương thức bảo vệ SLSP..........................................................................52 Hình 4.6. Điều kiện liên tục về bước sĩng.................................................................56 Hình 4.7. Đồ thị phân lớp với số bước sĩng W .........................................................58 Hình 4.8. Lưu đồ của thuật tốn đồ thị phân lớp .......................................................61 vii DANH MỤC CÁC BẢNG BIỂU Bảng 1.1. Các tham số của sợi SMF ..........................................................................10 Bảng 1.2. Các tham số của sợi DSF ...........................................................................11 Bảng 1.3. Các tham số của sợi NZ-DSF ....................................................................11 Bảng 4.1. QoR (chất lượng tin cậy)............................................................................51 Bảng 4.2: QoR phụ thuộc vào cặp nút .......................................................................52 Bảng 4.3. Ma trận lưu lượng cho mạng xét................................................................63