Luận Văn Thạc Sĩ Về Phương Pháp Định Vị Liên Kết Lỗi Trên Mạng Quang

Luận văn thạc sĩ phân tích hay một số phương pháp định vị liên kết lỗi trên mạng quang, đánh giá thực trạng, chỉ ra hạn chế, đề xuất giải pháp khả thi cho thực tiễn.

• Tác giả: Vũ Thị Nam
• Người hướng dẫn: PGS. TS Lê Trọng Vĩnh
• Trường học: Đại học Thái Nguyên
• Chuyên ngành: Khoa Học Máy Tính
• Đề tài: Phương Pháp Định Vị Liên Kết Lỗi Trên Mạng Cáp Quang
• Loại tài liệu: Luận Văn Thạc Sĩ

Mục lục chi tiết

• MỞ ĐẦU
• 1. CHƯƠNG 1: MẠNG CÁP QUANG
• 1.1. Giới thiệu chung
• 1.2. Công nghệ WDM
• 1.3. Một số khái niệm trong mạng cáp quang
• 1.4. Định tuyến và gán bước sóng
• 1.5. Sự cần thiết của wavelength converter
• 1.6. Kỹ thuật chia sẻ dự phòng
• 1.7. Định tuyến công bằng
• 1.8. Vấn đề multicast
• 2. CHƯƠNG 2: MỘT SỐ PHƯƠNG PHÁP ĐỊNH VỊ LIÊN KẾT LỖI TRONG MẠNG QUANG
• 3. CHƯƠNG 3: KẾT QUẢ THỰC NGHIỆM

Tóm tắt

I. Tổng quan về Phương Pháp Định Vị Liên Kết Lỗi Trên Mạng Cáp Quang

Mạng cáp quang đã trở thành một phần quan trọng trong hạ tầng viễn thông hiện đại. Việc phát hiện và định vị lỗi trong mạng cáp quang là một thách thức lớn. Các phương pháp hiện có giúp cải thiện độ tin cậy và hiệu suất của mạng. Bài viết này sẽ trình bày các phương pháp định vị lỗi hiệu quả nhất.

1.1. Định nghĩa và Tầm quan trọng của Mạng Cáp Quang

Mạng cáp quang sử dụng ánh sáng để truyền tải dữ liệu, mang lại tốc độ cao và băng thông lớn. Việc phát hiện lỗi kịp thời giúp giảm thiểu thiệt hại và đảm bảo dịch vụ liên tục.

1.2. Các Thách Thức trong Định Vị Liên Kết Lỗi

Các lỗi trong mạng cáp quang có thể xảy ra do nhiều nguyên nhân như đứt cáp hoặc lỗi thiết bị. Việc phát hiện lỗi nhanh chóng là rất cần thiết để duy trì hiệu suất mạng.

II. Các Phương Pháp Định Vị Liên Kết Lỗi Trên Mạng Cáp Quang

Có nhiều phương pháp khác nhau để định vị lỗi trong mạng cáp quang. Mỗi phương pháp có ưu điểm và nhược điểm riêng. Việc lựa chọn phương pháp phù hợp sẽ giúp tối ưu hóa quá trình phát hiện lỗi.

2.1. Phương Pháp Kiểm Tra Cáp Quang

Phương pháp này sử dụng các thiết bị đo lường để kiểm tra tình trạng của cáp quang. Nó giúp phát hiện các lỗi vật lý như đứt cáp hoặc hư hỏng.

2.2. Kỹ Thuật Sửa Chữa Cáp Quang

Kỹ thuật này bao gồm việc sử dụng các công cụ và thiết bị để sửa chữa các lỗi trong mạng cáp quang. Điều này giúp khôi phục lại dịch vụ nhanh chóng.

III. Ứng Dụng Thực Tiễn của Các Phương Pháp Định Vị Lỗi

Các phương pháp định vị lỗi đã được áp dụng rộng rãi trong thực tế. Chúng không chỉ giúp phát hiện lỗi mà còn cải thiện hiệu suất mạng. Nhiều tổ chức đã áp dụng các phương pháp này để nâng cao chất lượng dịch vụ.

3.1. Kết Quả Nghiên Cứu và Thực Nghiệm

Nghiên cứu cho thấy rằng việc áp dụng các phương pháp định vị lỗi giúp giảm thiểu thời gian ngừng hoạt động của mạng. Điều này mang lại lợi ích kinh tế lớn cho các nhà cung cấp dịch vụ.

3.2. Các Công Cụ Định Vị Lỗi Hiện Đại

Sự phát triển của công nghệ đã dẫn đến việc ra đời nhiều công cụ định vị lỗi hiện đại. Những công cụ này giúp tự động hóa quá trình phát hiện và sửa chữa lỗi.

IV. Kết Luận và Tương Lai của Phương Pháp Định Vị Liên Kết Lỗi

Phương pháp định vị lỗi trên mạng cáp quang đang ngày càng được cải tiến. Tương lai của công nghệ này hứa hẹn sẽ mang lại nhiều giải pháp hiệu quả hơn. Việc đầu tư vào nghiên cứu và phát triển sẽ giúp nâng cao chất lượng dịch vụ mạng.

4.1. Xu Hướng Phát Triển Công Nghệ

Công nghệ định vị lỗi sẽ tiếp tục phát triển với sự hỗ trợ của trí tuệ nhân tạo và học máy. Điều này sẽ giúp cải thiện độ chính xác và tốc độ phát hiện lỗi.

4.2. Tầm Quan Trọng của Đầu Tư Nghiên Cứu

Đầu tư vào nghiên cứu và phát triển các phương pháp mới sẽ giúp nâng cao khả năng cạnh tranh của các nhà cung cấp dịch vụ mạng.

Nội dung chính

Tổng quan nghiên cứu

Trong bối cảnh phát triển mạnh mẽ của công nghệ mạng cáp quang, đặc biệt là mạng quang toàn phần (All Optical Networks - AONs) sử dụng công nghệ ghép kênh theo bước sóng (Wavelength Division Multiplexing - WDM), việc phát hiện và định vị lỗi nhanh chóng trên mạng quang trở thành một vấn đề cấp thiết. Theo ước tính, mạng cáp quang có băng thông cực lớn khoảng 25 THz, gấp khoảng 1000 lần so với băng thông tổng cộng của sóng radio trên các vệ tinh trái đất, tuy nhiên tốc độ truy cập mạng của người dùng bị giới hạn bởi các tốc độ điện ở các nút mạng (vài Gb/s). Do đó, việc khai thác hiệu quả băng thông khổng lồ này đòi hỏi các giải pháp kỹ thuật tiên tiến, trong đó có phát hiện và định vị lỗi liên kết trên mạng quang.

Mục tiêu nghiên cứu của luận văn là tìm hiểu và phát triển các phương pháp định vị liên kết lỗi trên mạng cáp quang, tập trung vào các thuật toán xây dựng các cấu trúc giám sát như m-cycle, m-tree và m-trail nhằm giảm thiểu số lượng trạm kiểm soát, tối ưu hóa chi phí giám sát và tăng tốc độ phát hiện lỗi ở tầng quang. Phạm vi nghiên cứu tập trung vào mạng cáp quang WDM, với các mô hình lỗi đơn (single link fail) phổ biến trong thực tế vận hành mạng quang hiện nay.

Ý nghĩa của nghiên cứu được thể hiện qua việc nâng cao chất lượng dịch vụ (Quality of Service - QoS) bằng cách giảm thiểu thời gian dừng dịch vụ do lỗi, tránh mất mát dữ liệu lớn và tăng độ tin cậy của mạng cáp quang. Các chỉ số đánh giá hiệu quả bao gồm số lượng trạm kiểm soát cần thiết, tổng độ dài các m-cycle/m-tree/m-trail, và số bước sóng cảnh báo tối thiểu, góp phần giảm chi phí vận hành và nâng cao khả năng phục hồi mạng.

Cơ sở lý thuyết và phương pháp nghiên cứu

Khung lý thuyết áp dụng

Luận văn dựa trên các lý thuyết và mô hình sau:

• Mạng cáp quang WDM: Công nghệ ghép kênh theo bước sóng cho phép tích hợp hàng trăm bước sóng trên một sợi quang đơn, tăng dung lượng truyền tải mà không cần tăng tốc độ bit hoặc số lượng sợi quang.

• Mô hình lỗi đơn (Single Link Fail): Giả định tại một thời điểm chỉ có tối đa một liên kết bị lỗi, phù hợp với thực tế vận hành mạng cáp quang có độ an toàn cao.

• Khái niệm giám sát liên kết quang: Sử dụng các trạm kiểm soát (monitor) đo năng lượng quang, phân tích quang phổ để phát hiện lỗi. Các phương pháp giám sát dựa trên liên kết, m-cycle, m-tree và m-trail nhằm tối ưu hóa số lượng trạm và kênh giám sát.

• Thuật toán xây dựng m-cycle, m-tree, m-trail: Các cấu trúc này là các chu trình hoặc cây quang học dùng để giám sát liên kết, giúp giảm số lượng điốt laser và bộ giám sát quang học cần thiết, đồng thời đảm bảo định vị lỗi chính xác.

• Chương trình tuyến tính nguyên (ILP): Được sử dụng để mô hình hóa và tối ưu hóa bài toán định vị lỗi, bao gồm việc xác định vị trí trạm kiểm soát, cấu trúc m-tree, m-cycle sao cho chi phí giám sát và băng thông được tối thiểu hóa.

Phương pháp nghiên cứu

• Nguồn dữ liệu: Mạng cáp quang WDM mô phỏng với các topologies tiêu biểu như mạng Deutsche Telekom gồm 14 nút và 23 liên kết.

• Phương pháp phân tích: Sử dụng mô hình đồ thị vô hướng biểu diễn mạng, áp dụng các thuật toán xây dựng m-cycle, m-tree, m-trail và giải bài toán ILP để tìm cấu trúc giám sát tối ưu.

• Cỡ mẫu và chọn mẫu: Mạng mô phỏng có kích thước từ nhỏ đến trung bình (khoảng 14-25 liên kết) để đảm bảo tính khả thi của giải pháp ILP và thuật toán heuristic.

• Timeline nghiên cứu: Nghiên cứu được thực hiện qua ba giai đoạn chính: tổng quan và xây dựng khung lý thuyết; phát triển và thử nghiệm thuật toán M2-CYCLE; đánh giá và so sánh kết quả với các phương pháp hiện có.

Kết quả nghiên cứu và thảo luận

Những phát hiện chính

1. Hiệu quả của thuật toán M2-CYCLE trong xây dựng m-cycle: Thuật toán M2-CYCLE cho phép xây dựng tập m-cycle bao phủ toàn bộ các liên kết trong mạng với số lượng m-cycle tối thiểu, đồng thời giảm tổng độ dài bao phủ và số bước sóng cảnh báo cần thiết. Ví dụ, trong mạng Deutsche Telekom, thuật toán này giảm số trạm kiểm soát cần thiết so với các phương pháp truyền thống khoảng 15-20%.

2. Tối ưu hóa số lượng bộ giám sát quang trong m-tree: Qua mô hình ILP, số bộ giám sát quang tối thiểu cần thiết để giám sát mạng với 14 nút và 23 liên kết được xác định là khoảng một nửa so với phương pháp giám sát dựa trên liên kết truyền thống. Điều này giúp giảm chi phí đầu tư thiết bị và vận hành.

3. So sánh giữa m-cycle, m-tree và m-trail: Mỗi phương pháp có ưu nhược điểm riêng. M-tree sử dụng một điốt laser duy nhất nhưng yêu cầu nhiều kênh giám sát quang học; m-trail cân bằng giữa số lượng điốt laser và kênh giám sát; m-cycle đơn giản nhưng có thể gây nhầm lẫn trong định vị lỗi nếu không được thiết kế kỹ. Thuật toán M2-CYCLE được chứng minh không kém hiệu quả hơn các thuật toán dựa trên spanning-tree.

4. Tính khả thi của ILP trong mạng kích thước lớn: Việc mở rộng ILP cho mạng lớn hơn (khoảng 25 liên kết) gặp khó khăn do các tham số trở nên rất lớn hoặc rất nhỏ, gây mất ổn định trong tính toán. Giải pháp chia nhỏ mã cảnh báo thành các khối 20 bit và chuyển đổi sang dạng thập phân giúp cải thiện tính ổn định và khả năng giải quyết bài toán.

Thảo luận kết quả

Nguyên nhân của các kết quả trên xuất phát từ việc tận dụng đặc tính vật lý của mạng cáp quang và khả năng phát sóng, nhân bản tín hiệu quang tại các nút mạng. Việc sử dụng các cấu trúc m-cycle, m-tree, m-trail giúp giảm thiểu số lượng thiết bị giám sát cần thiết, từ đó giảm chi phí và tăng hiệu quả vận hành.

So sánh với các nghiên cứu trước đây, thuật toán M2-CYCLE và mô hình ILP được đề xuất trong luận văn cho thấy sự cải tiến rõ rệt về mặt chi phí và tốc độ phát hiện lỗi. Các biểu đồ so sánh số lượng trạm kiểm soát, tổng độ dài m-cycle và số bước sóng cảnh báo minh họa rõ ràng sự vượt trội của phương pháp này.

Ý nghĩa của kết quả nằm ở khả năng ứng dụng thực tiễn trong các mạng cáp quang hiện đại, giúp nâng cao độ tin cậy và chất lượng dịch vụ, đồng thời giảm thiểu thời gian gián đoạn do lỗi mạng.

Đề xuất và khuyến nghị

1. Triển khai thuật toán M2-CYCLE trong hệ thống giám sát mạng quang: Đề nghị các nhà quản lý mạng và kỹ sư vận hành áp dụng thuật toán M2-CYCLE để xây dựng hệ thống giám sát lỗi, nhằm giảm thiểu số lượng trạm kiểm soát và tối ưu chi phí vận hành trong vòng 6-12 tháng.

2. Phát triển phần mềm hỗ trợ giải bài toán ILP mở rộng: Khuyến nghị phát triển công cụ phần mềm chuyên dụng sử dụng kỹ thuật phân mảnh mã cảnh báo và chuyển đổi thập phân để giải quyết bài toán ILP cho mạng lớn, nâng cao khả năng mở rộng và tính ổn định trong 1-2 năm tới.

3. Nâng cao khả năng phát sóng và nhân bản tín hiệu tại các nút mạng: Đề xuất các nhà sản xuất thiết bị mạng quang cải tiến công nghệ phát sóng đa hướng và nhân bản tín hiệu để hỗ trợ hiệu quả hơn cho các cấu trúc m-tree và m-trail, giảm thiểu số lượng điốt laser cần thiết trong 2-3 năm.

4. Tích hợp các phương pháp định vị lỗi vào hệ thống quản lý mạng tự động: Khuyến nghị tích hợp các thuật toán định vị lỗi vào hệ thống quản lý mạng tự động (NMS) để tự động phát hiện, định vị và xử lý lỗi nhanh chóng, nâng cao chất lượng dịch vụ và giảm thiểu thời gian gián đoạn trong vòng 1 năm.

Đối tượng nên tham khảo luận văn

1. Kỹ sư và quản lý mạng cáp quang: Giúp hiểu rõ các phương pháp phát hiện và định vị lỗi tiên tiến, từ đó áp dụng vào thiết kế và vận hành mạng nhằm nâng cao độ tin cậy và giảm chi phí.

2. Nhà nghiên cứu và phát triển công nghệ mạng quang: Cung cấp cơ sở lý thuyết và thuật toán mới để phát triển các giải pháp giám sát mạng quang hiệu quả hơn, đồng thời mở rộng nghiên cứu về các cấu trúc m-cycle, m-tree, m-trail.

3. Sinh viên và học viên cao học chuyên ngành Khoa học Máy tính, Mạng máy tính và Truyền thông quang: Là tài liệu tham khảo chuyên sâu về kỹ thuật định vị lỗi trong mạng cáp quang, giúp nâng cao kiến thức và kỹ năng nghiên cứu.

4. Nhà sản xuất thiết bị mạng quang: Hỗ trợ trong việc thiết kế các thiết bị giám sát quang học tối ưu, phù hợp với các thuật toán định vị lỗi hiện đại, từ đó nâng cao tính cạnh tranh và hiệu quả sản phẩm.

Câu hỏi thường gặp

1. Phương pháp m-cycle là gì và ưu điểm của nó?
   M-cycle là các chu trình quang học dùng để giám sát liên kết trong mạng cáp quang, giúp giảm số lượng trạm kiểm soát cần thiết. Ưu điểm là đơn giản trong thiết kế và triển khai, tuy nhiên có thể gây nhầm lẫn trong định vị lỗi nếu không được thiết kế kỹ.

2. Tại sao cần sử dụng ILP trong bài toán định vị lỗi?
   ILP giúp mô hình hóa bài toán tối ưu vị trí trạm kiểm soát và cấu trúc giám sát sao cho chi phí tổng thể được tối thiểu, đồng thời đảm bảo định vị lỗi chính xác. Đây là phương pháp chính xác và hiệu quả cho các mạng có kích thước vừa và nhỏ.

3. Thuật toán M2-CYCLE có điểm gì nổi bật?
   M2-CYCLE là thuật toán heuristic xây dựng tập m-cycle tối ưu, giảm thiểu số lượng trạm kiểm soát và tổng độ dài bao phủ, đồng thời đảm bảo khả năng định vị lỗi chính xác. Thuật toán này có hiệu suất không kém hơn các phương pháp dựa trên spanning-tree.

4. Làm thế nào để giảm số lượng bộ giám sát quang trong mạng?
   Sử dụng các cấu trúc m-tree và m-trail tận dụng khả năng phát sóng và nhân bản tín hiệu tại các nút mạng giúp giảm số lượng điốt laser và bộ giám sát cần thiết, từ đó giảm chi phí đầu tư và vận hành.

5. Phương pháp nào phù hợp cho mạng cáp quang lớn?
   Đối với mạng lớn, việc sử dụng ILP truyền thống gặp khó khăn do tính toán phức tạp. Giải pháp là áp dụng các thuật toán heuristic như M2-CYCLE kết hợp với kỹ thuật phân mảnh mã cảnh báo và chuyển đổi thập phân để đảm bảo tính khả thi và hiệu quả.

Kết luận

• Luận văn đã nghiên cứu và phát triển các phương pháp định vị liên kết lỗi trên mạng cáp quang WDM, tập trung vào các cấu trúc m-cycle, m-tree và m-trail.
• Thuật toán M2-CYCLE được đề xuất cho phép xây dựng tập m-cycle tối ưu, giảm thiểu số lượng trạm kiểm soát và tổng độ dài bao phủ.
• Mô hình ILP giúp xác định vị trí bộ giám sát quang tối ưu, giảm chi phí vận hành và nâng cao khả năng định vị lỗi chính xác.
• Kết quả nghiên cứu có ý nghĩa thực tiễn cao, hỗ trợ nâng cao chất lượng dịch vụ và độ tin cậy mạng cáp quang.
• Đề xuất các bước tiếp theo bao gồm phát triển phần mềm hỗ trợ giải bài toán ILP mở rộng, tích hợp thuật toán vào hệ thống quản lý mạng tự động và nâng cao công nghệ thiết bị giám sát quang.

Các nhà nghiên cứu và kỹ sư mạng nên áp dụng và thử nghiệm các thuật toán này trong môi trường thực tế để đánh giá hiệu quả và tiếp tục cải tiến giải pháp.

Trích đoạn nội dung tài liệu

CHƯƠNG 1 – MẠNG CÁP QUANG 1.1 Giới thiệu chung Mạng cáp quang hoạt động dựa trên hiện tượng phản xạ toàn phần trong sợi quang. Nó nhanh hơn mạng truyền thống vì dữ liệu được truyền qua sợi quang dưới dạng các photon, còn trong mạng truyền thống dữ liệu được truyền qua cáp đồng dưới dạng các electron. Photon có trong lượng nhỏ hơn electron, và hơn nữa giữa các photon không có sự tương tác như giữa các electron. Mặt khác, ánh sáng có tần số cao hơn nên bước sóng cũng ngắn hơn, do đó với cùng chiều dài, cáp quang truyền được nhiều thông tin hơn cáp đồng.

Cùng với những đặc tính ưu việt như: cung cấp băng thông cực lớn, chi phí thấp, tỉ lệ lỗi bít cực thấp, độ nhiễu tín hiệu rất nhỏ, yêu cầu không gian nhỏ, khả năng bảo mật cao…, hiện nay mạng cáp quang đang là công nghệ hứa hẹn cho tương lai và được sử dụng rộng rãi trong mạng truyền thông backbone (mạng truyền thông đường trục).2 Công nghệ WDM Xác định lỗi là một trong những nhiệm vụ quan trọng trong việc đạt được khả năng tồn tại mạng all-optical WDM (phân chia đa hợp bước sóng). Để đảm bảo chất lượng cho người sử dụng dịch vụ (Qos) yêu cầu, thời gian dừng dịch vụ do một lỗi nên được giảm đến mức tối thiểu để tránh mất dữ liệu lớn. Trong những lỗi kế hoạch sống sót phụ thuộc, điều đó là cấp bách mà lỗi có thể được xác định một cách kịp thời, như kết nối dịch vụ bị phá vỡ có thể ngay lập tức được định tuyến lại để bỏ qua các thành phần lỗi. Để giảm thiểu thời gian xác định lỗi, chương trình giám sát lỗi quang học được xem xét để tránh tín hiệu phức tạp.

Mục đích là xác định được lỗi liên kết nhanh và rõ ràng nhất, và trong lúc ấy giảm thiểu đến mức thấp nhất cả thời gian ước tính cho mỗi lỗi liên kết có thể và tài nguyên giám sát yêu cầu. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] 6 Theo lý thuyết, sợi quang có băng thông cực lớn (khoảng 25THz), gấp khoảng 1000 lần so với băng thông tổng cộng của sóng radio trên các vệ tinh trái đất. Tuy nhiên do tốc độ truy cập mạng của người dùng bị giới hạn bởi các tốc độ điện ở các nút mạng (vài Gb/s ). Sự không tương đồng về băng thông giữa quang và điện này làm cho việc khai thác hết băng thông khổng lồ của một sợi cáp quang mà chỉ dùng một kềnh truyền song là rất khó khăn.

Rất may cho người sử dụng là công nghệ WDM (wavelength division multiplexing ) cùng với EDFA (erbium doped fiber amplifer ) ra đời đã giải quyết vấn đề này. WDM là phương thức ghép kênh quang theo bước sóng. Thông thường trong tuyến thông tin quang điểm nối điểm, mỗi sợi quang cho một tia laser với một bước sóng ánh sáng truyền qua, tại đầu thu, bộ tách sóng quang tương ứng sẽ nhận tín hiệu từ sợi này. Mỗi một sóng laser mang một số tín hiệu điện với một phổ nhất định.

Từ những năm 1980, công nghệ sợi quang có nhiều tiến bộ nên phương thức ghép kênh quang theo bước sóng được ứng dụng trong mạng viễn thông đường trục và quốc tế. Ở đây, WDM cho phép ta tăng dung lượng kênh mà không cần tăng tốc độ bít của đường truyền và cũng không dùng thêm sợi dẫn quang. Nó cho phép khai thác một cách đơn giản và kinh tế lượng thông tin vào một sợi quang đơn (sợi quang chỉ cho một chùm laser truyền qua lõi của nó, còn sợi quang đa chế độ thì do nhiều chùm laser truyền qua lõi của nó dưới các góc khác nhau ) trên cự ly dài và tăng độ mềm dẻo của cấu trúc phân phối. Những đường truyền dẫn thử nghiệm đã đạt được tốc độ lưu lượng 160Gbit/s phân phối trên 8 kênh ghép theo bước sóng.

Hơn nữa, ghép kênh theo bước sóng WDM không chỉ giảm bớt ảnh hưởng của tán sắc mà còn chống được tổn hao do phân cực. Các hệ thống tin quang hiện đại có sử dụng bộ khuếch đại quang để ghép nhiều kênh theo WDM. Nếu với lưu lượng là 2,5Gbit/s, ghép theo WDM từ 8 đến 16 luồng thì ta thực hiện được một đường thông tin quang với lưu lượng là 20Gbit/s đến 40Gbit/s trên một sợi đơn mà vẫn dùng lại được cá thiết bị ghép kênh và phân kênh Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add luanvanchat@agmail. Nói một cách khác, WDM cho phép tăng tích số lưu lượng nhân với cự ly trên một sợi quang 1.3 Một số khái niệm trong mạng cáp quang 1.1 Định tuyến và gán bước sóng Trong mạng cáp quang, một kết nối được thực hiện bởi một lightpath.

Thuật toán để chọn tuyến (path) và bước sóng (wavelength) cho việc thiết lập các lightpath được gọi là thuật toán định tuyến và ấn định bước sóng (RWA). Yêu cầu kết nối (hay lưu lượng) mạng có thể là tĩnh hoặc động. Đối với lưu lượng mạng là tĩnh, những yêu cầu kết nối thường được biết trước. Lưu lượng mạng được xác định theo những cặp nguồn-đích dựa trên sự đánh giá chiều dài liên kết giữa chúng.

Chúng ta cần chọn các tuyến và các bước sóng sao cho tất cả các nhu cầu được đáp ứng với số bước sóng cần sử dụng ít nhất, hoặc cực đại số nhu cầu được thỏa mãn với số bước sóng cố định. Vấn đề này nằm trong bài toán thiết lập các lightpath tĩnh (SLE). Bài toán SLE đã được chứng minh là NP đầy đủ, do vậy các thuật toán giải gần đúng với thời gian đa thức thường được sử dụng. Khi nhu cầu lưu lượng mạng là động, những yêu cầu kết nối mạng là ngẫu nhiên.

Các lightpath được thiết lập chỉ tồn tại trong một khoảng thời gian có hạn. Khi nhu cầu lưu lượng mạng thay đổi hoặc một thành phần nào đó của mạng bị hỏng, một số lightpath đang tồn tại có thể bị loại bỏ, và một số lightpath mới được thiết lập để phù hợp với sự thay đổi đó. Không giống như bài toán RWA tĩnh, bất cứ lời giải nào cho bài toán RWA động cũng đều là những tính toán đơn giản, vì những yêu cầu cần được xử lý trực tuyến. Thuật toán RWA động thực hiện đơn giản hơn thuật toán RWA tĩnh vì nó không biết những yêu cầu kết nối trong tương lai, trong khi tất cả những yêu cầu kết nối đều được biết trước trong thuật toán RWA tĩnh.

Thuật toán RWA động xử lý các yêu cầu kết nối hoàn toàn theo thứ tự mà chúng đến, trong khi thuật toán RWA tĩnh Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] 8 xử lý các yêu cầu đó theo thứ tự được quyết định bởi một vài thuật toán heuristic. Các thuật toán Heuristic gán các bước sóng cho các tuyến theo trật tự không tăng chiều dài hop của chúng (hop là một bước truyền, 2 nút mạng được kết nối trực tiếp với nhau bởi một lightpath tạo nên một hop), vì những kết nối có số hop lớn hơn thường khó tìm được một bước sóng rỗi trên toàn tuyến của nó so với các kết nối có số hop nhỏ. Ví dụ sau đây sẽ chứng minh cho những vấn đề đã nói ở trên. Ví dụ: Xét mạng với 4 nút và 2 bước sóng w0 và w1 như trong hình 1.

Cần thiết lập các lightpath giữa những cặp nút <0,1>,<2,3>,<1,3>,<0,2>. Giả thiết rằng các yêu cầu đến theo thứ tự trên. Một thuật toán RWA động thiết lập các lightpath p0, p1, p2 cho 3 yêu cầu đến đầu tiên như trong hình 1. Thuật toán này sử dụng bước sóng rỗi đầu tiên cho tuyến được chọn.

Các lightpath p0, p1 sử dụng w0, p2 sử dụng w1. Không có lightpath được thiết lập giữa nút 0 và nút 2, vì tuyến giữa 2 nút này không đảm bảo sự liên tục bước sóng. Một thuật toán RWA tĩnh thiết lập các lightpath q0, q1, q2 và q3 cho 4 cặp nút như trong hình 1. Thuật toán này xét các kết nối trong thứ tự không tăng chiều dài hop, và bước sóng rỗi đầu tiên được gán cho một kết nối.

Ở đây các cặp nút được xét theo thứ tự <1,3>,<0,2>,<0,1>,<2,3>.1: Các lightpath được thiết lập với a) RWA động b) RWA tĩnh Bài toán RWA là bài toán NP-đầy đủ, vì vậy để giải nó người ta thường được chia thành hai bài toán con: Định tuyến và ấn định các bước sóng. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.vn LUAN VAN CHAT LUONG download : add [e-mail] 9 Có 3 phương pháp định tuyến quan trọng: định tuyến cố định (fixed routing), định tuyến luân phiên (fixed alternate routing), và định tuyến đầy đủ (exhaust routing). Phương pháp định tuyến cố định chọn một tuyến duy nhất giữa một cặp nút, và thông thường tuyến đó là tuyến ngắn nhất giữa cặp nút này. Phương pháp định tuyến luân phiên dùng hai hay nhiều tuyến giữa một cặp nút.

Những tuyến này được tìm lần lượt theo một thứ tự định trước, thường là theo thứ tự không tăng chiều dài hop của chúng. Phương pháp định tuyến đầy đủ tìm kiếm trên tất cả các tuyến có thể giữa một cặp nút và chọn tuyến ngắn nhất (cái mà có thể ấn định được một wavelength) theo trạng thái của mạng. Phương pháp định tuyến đầy đủ có tính khả thi cao hơn hai phương pháp kia nhưng nó lại yêu cầu sự tính toán phức tạp hơn. Tương tự phương pháp định tuyến cố định yêu cầu tính toán đơn giản hơn phương pháp định tuyến chọn lọc, nhưng tính khả thi của nó lại thấp hơn.

Phương pháp ấn định bước sóng được chia thành bốn loại: bước sóng được sử dụng nhiều nhất (most used), bước sóng được sử dụng ít nhất (least used), thứ tự các bước sóng là cố định (fixed oder) và thứ tự các bước sóng là ngẫu nhiên (random oder). Trong phương pháp thứ nhất, các bước sóng được tìm theo thứ tự không tăng khả năng tận dụng nó trong mạng. Các lightpath được nhóm lại để có nhiều bước sóng sẵn sàng cho những yêu cầu kết nối sau. Trong phương pháp thứ hai, các bước sóng cũng được tìm theo thứ tự không tăng khả năng tận dụng nó trong mạng.

Phương pháp này ấn định bước sóng cho các lightpath để sự khác nhau về bước sóng giữa chúng là nhiều nhất có thể. Ý tưởng ở đây là một yêu cầu mới có thể tìm được một tuyến ngắn nhất với một bước sóng còn rỗi trên nó. Phương pháp thứ ba ấn định các bước sóng theo một thứ tự cố định. Mỗi bước sóng được gán một chỉ số, bước sóng với chỉ số thấp nhất được kiểm tra đầu tiên.

Trong phương pháp thứ tư, các bước sóng được gán theo một thứ tự ngẫu nhiên.