Luận văn Thạc sĩ Khoa học máy tính: Một số phương pháp định vị liên kết lỗi trên mạng quang

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:70

Thêm vào BST

Báo xấu

16
lượt xem 3
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Luận văn này tìm hiểu các thuật toán xây dưng cc m-cycle, m-tree, m-trail với độ dài nhỏ nhất nhằm nhanh chóng phát hiện lỗi ở tầng quang. Trình bày các phương pháp định vị liên kết lỗi trên mạng quang, phát biểu bài toán, thuật toán xây dựng m- cycle, m - trail, m - tree. Mời các bạn cùng tham khảo!

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Luận văn Thạc sĩ Khoa học máy tính: Một số phương pháp định vị liên kết lỗi trên mạng quang

1 ĐẠI HỌC THÁI NGUYÊN TRƯỜNG ĐẠI HỌC CÔNG NGHỆ THÔNG TIN VÀ TRUYỀN THÔNG VŨ THỊ NAM MỘT SỐ PHƯƠNG PHÁP ĐỊNH VỊ LIÊN KẾT LỖI TRÊN MẠNG QUANG Mã số: 60 48 01 01 Chuyên ngành: KHOA HỌC MÁY TÍNH LUẬN VĂN THẠC SĨ KHOA HỌC MÁY TÍNH NGƯỜI HƯỚNG DẪN KHOA HỌC PGS. TS LÊ TRỌNG VĨNH Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
2 MỞ ĐẦU Trong vài thập kỷ qua, ảnh hưởng của “mạng” ngày càng rõ rệt trong việc tổ chức hệ thống máy tính. Mạng máy tính là một hệ thống những máy tính độc lập được kết nối với nhau nhằm đáp ứng công việc chung của tổ chức. Mạng đem lại những thuận tiện trong cuộc sống như: cung cấp phương tiện liên lạc, chia sẻ những tài nguyên sẵn có, cải tiến sự tin cậy của dịch vụ, giảm thiểu chi phí… Mạng thông tin phát triển một cách ma ̣nh mẽ cùng với sự phát triể n nhanh chóng của các công nghê ̣ quang ho ̣c, thiết bị giao tiế p liên tu ̣c phát triể n hướng đế n ma ̣ng cáp quang (AONs). Trong những ma ̣ng cáp quang WDM (phương thức ghép kênh theo bước sóng), hàng trăm bước sóng đươ ̣c tić h hợp trên mô ̣t sơ ̣i quang đơn. Vì vâ ̣y mô ̣t sơ ̣i quang bi ̣đứt sẽ làm mấ t mát một lươ ̣ng dữ liệu lớn. Chính vì thế mà việc phát hiê ̣n và đinh ̣ vị lỗi nhanh chóng là mô ̣t trong những vấn đề rất quan trọng trong quá trình vận hành và khai thác mạng cáp quang. Phát hiện lỗi liên kế t trong ma ̣ng cáp quang có thể đươ ̣c thực hiê ̣n ở nhiều tầ ng khác nhau: tầ ng quang, tầ ng vật lý, tầ ng mạng,… và hầ u hết các phương pháp đinh ̣ tuyế n đều có cơ chế phát hiện lỗi. Để đẩ y nhanh tố c đô ̣ phát hiê ̣n lỗi, người ta cũng đề xuấ t thiế t kế các tầ ng liên kết chéo (cross-layer). Tuy vậy, với kỹ thuật này thời gian phát hiê ̣n lỗi trong vài giây và lâu hơn so với yêu cầ u đă ̣c trưng của mạng quang. Do đó người ta hướng đến việc phát hiện lỗi ở tầ ng quang. Nói cách khác, các phương thức đã thiế t kế cho ma ̣ng cáp quang truyề n thố ng không thể áp dụng trực tiếp cho ma ̣ng cáp quang hoàn toàn( AONs). Ở tầ ng quang, mô ̣t lỗi có thể đươ ̣c phát hiê ̣n bằ ng viê ̣c đo năng lươ ̣ng quang, phân tích quang phổ ,... Điề u này đươ ̣c thực hiê ̣n bởi mô ̣t thiế t bi ̣ quang đă ̣c biê ̣t đươ ̣c go ̣i là tra ̣m kiể m soát (monitor). Phương pháp kiể m soát dựa trên kênh sử du ̣ng trên mỗi kênh bước sóng của mô ̣t liên kế t mô ̣t tra ̣m kiể m soát. Điều này yêu cầu quá nhiều trạm kiểm Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
3 soát. Phương thức kiể m soát trên liên kế t là khái niê ̣m tố t hơn, nhưng vẫn yêu cầ u mỗi liên kết một tra ̣m kiể m soát. Để giảm thiể u số lươ ̣ng trạm kiể m soát cầ n thiế t phải có, các tác giả đã đưa ra khái niê ̣m monitoring-cycle (m-cycle), m-tree, m-trail. Ý tưởng chính của các cách tiếp cận này là: Đối với: m - cycle tìm tâ ̣p M các m-cycle {c1, c2,… cM} sao cho tập này bao phủ tấ t cả các liên kết trong mạng, và gán cho mỗi m-cycle mô ̣t trạm kiểm soát. Mỗi liên kết có thể được bao phủ bởi nhiề u m-cycle. Nế u mô ̣t liên kế t bi ̣lỗi nó sẽ gây ra mỗi mã cảnh báo trên tấ t cả các m-cycle bao phủ lên liên kế t này. Đối với m-tree chỉ cần một diot laser duy nhất thường là đủ để theo dõi tất cả các mạng. Diot laser này được đặt tại một nút và truyền tín hiệu giám sát một hướng duy nhất của mình trên một liên kết duy nhất được gọi là "ngọn của cây" (head of the tree). Tại một nút dọc theo một liên kết đầu vào, tín hiệu giám sát có thể bị dừng và chuyển tiếp qua một liên kết ra duy nhất, nhân bản và gửi qua hai hay nhiều liên kết ra. Đối với m-trail: Cho một bộ các nút giám sát MN ={MN0, . . ., MNn}, chúng ta cần thiết kế một giải pháp m-trail với số lượng nhỏ nhất các bước sóng cần cho việc giám sát, như mỗi MN có thể thực hiện nhanh và định vị rõ liên kết lỗi dựa trên tín hiệu báo động quang thu được một cách cục bộ. Trên cơ sở ý tưởng trên, đã có nhiề u thuâ ̣t toán xây dựng các m-cycle, m-tree, m- trail để phát hiê ̣n và đinh ̣ vi ̣ lỗi. Luận văn này là tìm hiểu các thuâ ̣t toán xây dựng các m-cycle, m-tree, m-trail với đô ̣ dài nhỏ nhấ t nhằ m nhanh chóng phát hiê ̣n lỗi ở tầ ng quang. Bố cu ̣c vủa luâ ̣n văn được trình bày như sau: Chương 1: Mạng cáp quang Giới thiệu tổng quan về mạng quang, kiến trúc của mạng quang và các vấn đề trong mạng quang. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
4 Chương 2: Một số phương pháp đinh vị liên kết lỗi trong mạng quang Trình bày các phương pháp định vị liên kết lỗi trên mạng quang, phát biể u bài toán, thuật toán xây dựng m- cycle, m - trail, m - tree. Chương 3: Kết quả thực nghiệm Thực nghiệm bằng thuâ ̣t toán M2-CYCLE . Chương trình minh họa kết quả thực nghiệm, đánh giá, nhận xét. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
5 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. Nó 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 có 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 đó 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). 1.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 só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 đó 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.lrc.tnu.edu.vn
6 Theo lý thuyết, sợi quang có 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 khó 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 sóng quang tương ứng sẽ 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 só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 nó 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 só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.lrc.tnu.edu.vn
7 hiện có. 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.3.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 đ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 đó. 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.lrc.tnu.edu.vn
8 xử lý các yêu cầu đó 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 sẽ chứng minh cho những vấn đề đã nó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.3. Cần thiết lập các lightpath giữa những cặp nút ,,,. 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.4(a). 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.1(b). 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ự ,,,. Hình 1.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 nó 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.lrc.tnu.edu.vn
9 Có 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 đó 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 nó 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 sóng được chia thành bốn loại: bước sóng được sử dụng nhiều nhất (most used), bước só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 só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 só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 só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 nó. 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 só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. Theo các tài liệu báo cáo khoa học, với một thuật toán định tuyến, hiệu quả của các phương pháp ấn định các bước sóng là như nhau. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
10 1.3.2. Sự cần thiết của wavelength converter Nếu không có các thiết bị chuyển đổi bước sóng (wavelength converters), thì một lightpath sẽ yêu cầu sử dụng duy nhất một wavelength trên tất cả các liên kết mà nó trải qua. Điều này được biết như là sự ràng buộc liên tục của bước sóng. Và sự rằng buộc này làm giảm hiệu năng sử dụng các tài nguyên mạng. Chúng ta có thể thấy rõ điều này qua ví dụ đơn giản sau đây: 2 4 w1& w0 w0 w1 w1 w0 w1 1 3 w0 Hình 1.2: Mạng quang không có wavelength converter Ví dụ: Giả sử chúng ta có mạng quang như hình 1.2 và không có các wavelength converters ở trên mạng. Mỗi một liên kết có hai wavelength là w0 và w1. Giả sử chúng ta có 2 kết nối giữa các cặp nút (1, 4) và (2, 3). Giả sử kết nối giữa cặp nút (1,4) sử dụng lightpath theo đường (1, 3, 4) với wavelength w0. Kết nối giữa cặp nút (2, 3) sử dụng lightpath theo đường (2, 1, 3) với wavelength w1. Bây giờ, giả sử có một yêu cầu kết nối mới giữa nút (1, 3). Rõ ràng chúng ta không thể thiết lập được kết nối cho yêu cầu này bởi vì: Liên kết (1,3) đang bận (cả w0 và w1 đều đang sử dụng), đường (1,2,4,3) thì không tồn tại một wavelength cho tất cả các liên kết vì liên kết (3,4) và liên kết (1,2) có hai wavlength rỗi lại khác nhau là w0 và w1 tương ứng. Rõ ràng, trong trường hợp này tài nguyên mạng đang còn rỗi nhưng lại không phục vụ được nhu cầu kết nối. Bây giờ ta lại giả sử mạng có wavelength converter tại nút số 2. Khi đó, yêu cầu kết nối giữa nút (1, 3) trong ví dụ trên như hình vẽ 1.3 dưới đây. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
11 Hình 1.3: Mạng quang với wavelength converters Mạng cáp quang có bị lỗi do đứt cáp vật lý hay lỗi vật lý các nút mạng. Do vậy, để an toàn cho dữ liệu người ta thường phải sử dụng hai lightpaths cho mỗi kết nối. Một lightpath dùng chính (primary) và một dùng làm dự phòng (backup). Điều này được biết như là bài toán định tuyến và gán bước sóng trong mạng quang đàm bảo tính chịu lỗi. Hình 1.4: Kỹ thuật chia sẻ dự phòng Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
12 Trong thực tế, các nút mạng hoặc các liên kết giữa chúng bởi các sợi quang có thể hỏng bởi các hiện tượng tự nhiên. Khi sự hỏng hóc này xảy ra, các lightpath liên quan đến chúng cũng sẽ bị hỏng theo, và như hệ một hệ quả, truyền thông dựa trên các lightpath này cũng bị cắt và thông tin có thể bị mất mát. Vì vậy, để trách sự mất mát thông tin, truyền thông giữa hai nút mạng thường được xây dựng dựa trên hai lightpath khác nhau. Ví dụ, truyền thông giữa hai nút (0, 5) sẽ được thiết lập theo hai lightpath dọc theo hai tuyến (0, 1, 4, 5) và (0, 2, 3, 5). Với cách thiết lập như vậy, truyền thông giữa nút 0 và 5 luôn luôn được đảm bảo. Mặt khác, các mạng cáp quang thường có độ an toàn cao, vì vậy, rất hiếm khi nút mạng hoặc hai liên kết mạng cùng hỏng đồng thời, vì vậy các đường backup có thể chia sẽ các liên kết nếu các đường primary của chúng rời nhau (ko có liên kết nào chung). Kỹ thuật này được biết đến như kỹ thuật chia sẻ dự phòng (backup multiplexing technique). Ví dụ, trong hình 1.4, lightpath thứ nhất sử dụng đường primary P1 (0, 1, 4) và lightpath thứ hai sử dụng đường primary P2 (0,4,5). Hai đường primary này là rời nhau, do vậy chúng có thể sử dụng hai đường backup B1 (0, 2, 3, 4) và B2 (0, 2, 3, 5) có hai liên kết chung là 0-2 và 2-3. 1.3.4. Định tuyến công bằng Trong một mạng máy tính đa người sử dụng cùng sử dụng các dịch vụ được cung cấp bởi hệ thống mạng thông qua các kết nối vật lý khác nhau. Mỗi kết nối vật lý có thể trải qua nhiều lần chuyển mạch, và mỗi lần chuyển mạch như vậy gọi là một hop. Rõ ràng, các kết nối vật lý có nhiều hops sẽ có nguy cơ không được phục vụ bằng các kết nối có ít hợp hơn (dễ tắc nghẽn hơn). Điều này có nghĩa, những người ở xa có nguy cơ không được phục vụ như là những người ở gần. Vì vậy, việc định ra các mức độ ưu tiên lại là một bài toán vô cùng khó khăn. Vì vậy, bài toán fairness trong mạng máy tính vẫn là một vấn đề còn nhiều thách thức đối với các nhà nghiên cứu và phát triển công nghệ. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
13 1.3.5. Vấn đề multicast Như đã trình bày ở trên, mạng cáp quang dựa trên công nghệ WDM đã và đang được xem như là công nghệ chính cho việc xây dựng thế hệ tiếp theo của Internet (Next-Generation Internet Backbone). Vì vậy các mạng này phải có khả năng để hỗ trợ cả truyền thông unicast (điểm - điểm) và các truyền thông multcast (điểm - nhiều điểm) để thích hợp với nhiều ứng dụng Internet như là audio và video theo yêu cầu, các hệ thống điều khiển thời gian thực, bán hàng trực tuyến, ... Mỗi truyền thông multicast sẽ liên quan đến một nút tài nguyên và một tập các nút đích. Đưa ra một nút tài nguyên và một tập các nút đích, bài toán multicast là tìm một tập các liên kết và bước sóng trên các liên kết này để thiết lập các kết nối từ tài nguyên tới tất cả các nút đích sao cho tổng chi phí là nhỏ nhất. Tổng chi phí có thể được định nghĩa như là tổng số các bước sóng phải dùng trên mỗi liên kết. Để tránh việc gửi riêng rẻ các bản sao tới mỗi đích, một truyền thông multicast thường được thực hiện bởi một cây multicast (multicast tree) với gốc là nút tài nguyên và các nhánh vươn tới tất cả các nút đích. Một cây multicast như vậy được gọi là light- tree nếu có đúng một bước sóng được ấn định tới mọi liên kết. Chú ý rằng, nó thường là khó để xây dựng một cây multcast đơn cho một truyền thông multcast, vì vậy thường một tập các light-tree (mỗi cái được ấn định một bước sóng khác nhau) sẽ được xây dựng để phục vụ cho một truyền thông multicast. Tập các light-trees được gọi là rừng (light-forest). Để hỗ trợ truyền thông multicast được hiểu quả, mỗi nút trong mạng WDM cần có khả năng của việc phân chia bước sóng (light splitting). Một nút với khả năng này có thể chuyển một tín hiệu ở cổng đến thành nhiều tín hiệu ở nhiều cổng ra trên cùng một bước sóng và được gọi là Multicast-Capable (MC). Bởi vì xây dựng một nút mạng với khả năng MC là rất đắt, nên trong các mạng quang chỉ có một số nút mạng chiến lược là có khả năng này. Các nút mạng khác không có khả năng MC được gọi là Multicast Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
14 Incapable (MI). Các nút mạng MI chỉ chuyển một tín hiệu từ cổng đến đến đúng một cổng ra. Một mạng cáp quang như vậy được biết như là mạng cáp quang với khả năng chia bước sóng thưa (optical network with sparse light splitting). Thêm nữa, một nút MI có thể là trích - hoặc – tiếp tục (Tap-or-Continue -ToC) hoặc trích – và – tiếp tục (Tap-and-Continue -TaC), nghĩa là ToC không thể vừa trích hiệu năng quang từ cổng đến vừa chuyển tín hiệu tới cổng ra. Một nút MC với khả năng chuyển đổi bước sóng (wavelength conversion) được gọi là tài nguyên ảo (Virtual Source -VS) nút bởi nó có khả năng chuyển tìn hiệu từ một cổng đến tới bất kỳ cổng ra nào sử dụng một bước sóng bất kỳ. 1.3.6. Định vị liên kết lỗi Như mục 1.3.3 đã đề cập, các lỗi trong mạng quang có thể là dây dẫn bị đứt (nếu một sợi bị lỗi thì tất cả những sợi khác được nối với sợi này cũng sẽ bị lỗi), các thiết bị đầu cuối bị lỗi, nút mạng bị lỗi (có thể là do lỗi của WXC), các kênh bước sóng đang dùng bị lỗi (do lỗi chuyển đổi bước sóng được kết nối trong WXC). Khi một thành phần bị lỗi thì tất cả lightpath sử dụng thành phần lỗi đó đều bị lỗi và dữ liệu có thể mất mát. Chính vì thế mà viê ̣c phát hiê ̣n và đinh ̣ vi ̣lỗi nhanh chóng là mô ̣t trong những vấn đề rất quan trọng trong quá trình vận hành và khai thác mạng cáp quang. Phát hiê ̣n lỗi liên kế t trong ma ̣ng cáp quang có thể được thực hiê ̣n ở nhiề u tầ ng khác nhau: tầ ng quang, tầ ng vật lý, tầ ng mạng,… Để đẩ y nhanh tốc đô ̣ phát hiê ̣n lỗi, người ta cũng đề xuất thiế t kế các tầ ng liên kết chéo (cross-layer). Tuy vâ ̣y, với kỹ thuâ ̣t này thời gian phát hiê ̣n lỗi trong vài giây và lâu hơn so với yêu cầu đă ̣c trưng của mạng quang. Do đó người ta hướng đến việc phát hiện lỗi ở tầ ng quang. Nói cách khác, các phương thức đã thiế t kế cho mạng cáp quang truyề n thố ng không thể áp dụng trực tiếp cho ma ̣ng cáp quang hoàn toàn (AONs). Ở tầ ng quang, mô ̣t lỗi có thể dươ ̣c phát hiê ̣n bằ ng viê ̣c đo năng lươ ̣ng quang, phân tích quang phổ ,... Điề u này đươ ̣c thực hiê ̣n bởi mô ̣t thiế t bi ̣ quang đă ̣c biê ̣t đươ ̣c go ̣i là Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
15 tra ̣m kiể m soát (monitor). Phương pháp kiể m soát dựa trên kênh sử du ̣ng trên mỗi kênh bước sóng của mô ̣t liên kế t mô ̣t tra ̣m kiể m soát. Điều này yêu cầu quá nhiều trạm kiểm soát. Phương thức kiể m soát trên liên kế t là khái niê ̣m tố t hơn, nhưng vẫn yêu cầ u mỗi liên kết một tra ̣m kiể m soát. Để giảm thiể u số lươ ̣ng trạm kiể m soát cầ n thiế t phải có, các tác giả trong [17] đã đưa ra khái niê ̣m monitoring-cycle (m-cycle), monitoring-Tree (m-Tree), monitoring- Trail (m-Trail). Trên cơ sở ý tưởng trên, đã có nhiề u thuâ ̣t toán xây dựng các m-cycle, m-tree, m-trail để phát hiê ̣n và đinh ̣ vi ̣ lỗi. Luận văn này tìm hiểu các phương pháp định vị liên kết lỗi trên mạng quang, đặc biệt quan tâm đến thuật toán xây dựng các m- cycle. CHƯƠNG 2 – MỘT SỐ PHƯƠNG PHÁP ĐỊNH VỊ LIÊN KẾT LỖI TRÊN MẠNG QUANG 2.1 Lỗi và định vị lỗi Mạng thông tin phát triển một cách ma ̣nh mẽ cùng với sự phát triể n nhanh chóng của các công nghệ quang học, thiê ̣t bi ̣giao tiế p liên tu ̣c phát triể n hướng đế n ma ̣ng toàn quang (AON – All Optical Networks). Trong những ma ̣ng toàn quang sử dụng công nghệ ghép kênh theo bước sóng WDM (Wavelength Division Multiplexing) cho phép hàng trăm bước sóng đươ ̣c tích hợp trên mô ̣t sơ ̣i quang đơn. Vì vâ ̣y lỗi mạng quang có thể gây ra sự mấ t mát mô ̣t lươ ̣ng dữ liê ̣u lớn. Chiń h vì thế mà viê ̣c phát hiê ̣n và đinh ̣ vi ̣ lỗi nhanh chóng là một trong những vấn đề rất quan trọng trong quá trình vận hành và khai thác mạng cáp quang. Lỗi mạng quang có thể gây ra bởi sự lỗi của các nút mạng, sự đứt của các liên kết quang giữa các nút. Bởi tính an toàn trong thiết kế, các nút mạng thường có các thiết bị dự phòng (backup), do vậy, khi lỗi xảy ra hệ thống sẽ được chuyển qua (switch) chạy ở chế độ dự phòng. Thêm nữa, các liên kết quang thường chuyển một Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
16 lượng thông tin khổng lồ, vì vậy để xảy ra việc đứt nhiều liên kết cùng lúc là khó xảy ra. Chính vì vậy, trong thực tế, người ta thường chỉ quan tâm đến mô hình lỗi mạng quang là: lỗi liên kết đơn (single link fail). Nghĩa là tại một thời điểm chỉ có nhiều nhất một liên kết có thể bị lỗi. Ở tầ ng quang, một lỗi có thể dươ ̣c phát hiê ̣n bằ ng viê ̣c đo năng lượng quang, phân tích quang phổ,... Điều này đươ ̣c thực hiê ̣n bởi mô ̣t thiế t bi ̣ quang đă ̣c biê ̣t được go ̣i là tra ̣m kiể m soát (monitor). Phương pháp kiểm soát dựa trên kênh sử dụng trên mỗi kênh bước sóng của mô ̣t liên kết mô ̣t tra ̣m kiể m soát. Điều này yêu cầu quá nhiều trạm kiểm soát. Phương thức kiể m soát trên liên kế t là khái niê ̣m tố t hơn, nhưng vẫn yêu cầ u mỗi liên kết một tra ̣m kiể m soát. Để giảm thiể u số lươ ̣ng tra ̣m kiể m soát cầ n thiế t người ta thường xây dựng m-trail, m-tree, hay m - cycle, để phát hiện và định vị lỗi. Hầu hết các phương pháp tiếp cận hiện [10] -[13] bao gồm trong việc triển khai giám sát quang chịu trách nhiệm tạo ra báo động khi có lỗi liên kết. Bộ giám sát (monitor) sẽ đưa ra các cảnh báo cho hệ thống điều khiển để bất kỳ thực thể định tuyến có thể định vị lỗi liên kết và thực hiện phục hồi lưu lượng truy cập thời gian thực. Trong các tiếp cận được đề xuất thì các kênh giám sát chuyên dụng được sử dụng cho mục đích giám sát tại các lỗi của lightpath hoạt động. Nói cách khác, các kênh giám sát không thể mang lưu lượng mạng của người sử dụng. Cơ chế giám sát như vậy được hiểu là giám sát ngoài luồng (out-of-band), trái ngược với giám sát bên trong (in-band), bộ giám sát sẽ giám sát hoạt động của các lightpath. Mục đích chính của các phương pháp này là để tối thiểu hóa chi phí giám sát khi định vị được lỗi cụ thể. Các chi phí giám sát thường bao gồm số lượng bộ giám sát quang học, số lượng điốt-laser cũng như số lượng của các kênh giám sát được yêu cầu. Việc giám sát truyền thống dựa vào liên kết thì vị trí của các điốt laser / bộ giám sát là đơn giản. Mỗi liên kết quang (fiber-link) được trang bị với một điốt laser và một bộ giám quang học tại mỗi đầu của nó. Như vậy, một kênh giám sát quang duy nhất Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
17 được dành riêng trên mỗi liên kết hai chiều để phát hiện bất kỳ một lỗi nào xảy ra trên cả hai hướng của liên kết đó. Do đó, phương pháp này có thể phát hiện và xác định vị trí mà không cần bất kỳ sự không rõ ràng nào về lỗi liên kết duy nhất cũng như nhiều liên kết lỗi trong mạng. Mặc dù phương pháp này sử dụng số lượng tối thiểu các kênh giám sát quang học, nhưng nó sử dụng một số lượng quá nhiều điốt laser và bộ giám sát quang học, vì vậy, làm cho nó không được quan tâm nhiều đối với các mạng lớn. Một cách tiếp cận tinh vi hơn nhằm giảm số lượng bộ giám sát trong mạng trong khi đạt được định vị liên kết cụ thể. Vào những năm cuối năm 2000, hai mô hình cho phát hiện lỗi và định vị đã được đề xuất, cụ thể là m-cycles và m-trail. Các m-cycles [10] -[11] đã được đề xuất với mục tiêu để giảm số lượng các yêu cầu điốt laser và bộ giám sát quang học, và sau đó để giảm chi phí giám sát mạng. M- cycle là một kết nối cycle quang sử dụng một kênh quang giám sát trên mỗi đường nó đi qua, với một điốt laser và một bộ giám sát quang học đặt tại bất kỳ nút dọc theo cycle. Tuy nhiên, nhược điểm chính của m-cycles là không có khả năng để phân biệt trong một số trường hợp giữa lỗi liên kết liên kết đơn xảy ra trên các liên kết khác nhau. Để khoanh vùng từng lỗi liên kết mà không cần bất kỳ sự nhập nhằng, thêm bộ giám sát liên kết được yêu cầu. Các m-trails [12] - [13] đã được đề xuất như là một thay thế cho m-cycle với mục tiêu rõ ràng địa phương hóa mà không với bất kỳ sự nhập nhằng nào của lỗi liên kết đơn trong khi vẫn giảm số lượng các yêu cầu điốt laser và bộ giám sát quang. Một m- trail hoạt động trong cùng một cách như là một m-cycle, nhưng kết nối quang học của các kênh giám sát không phải là nhất thiết phải là một cycle. Như vậy, các điốt laser và bộ giám sát quang của một m-trail không nhất thiết phải đặt ở cùng một nút. Kết quả là, cả hai giám sát dựa trên liên kết và và m-cylce có thể được coi là trường hợp đặc biệt của m- rail. Tuy nhiên số điốt laser càng thấp và bộ giám sát quang được triển khai trong mạng, cao hơn số lượng kênh giám sát quang học cần thiết cho việc phát hiện rõ Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
18 ràng. Vì vậy, cách tiếp cận m-trail cố gắng để tìm một sự cân bằng giữa chi phí bất lợi khi thêm các kênh giám sát quang học và chi phí có lợi khi giảm số lượng các điốt laser và bộ giám sát quang. Cách tiếp cận m-tree, lợi dụng các khả năng quảng bá của một nút mạng quang để tối ưu chi phí giám sát trong khi vẫn phát hiện được các lỗi rõ ràng. Các vấn đề của thiết kế m-tree được xây dựng như một chương trình nguyên tuyến tính (ILP). 2.2 Định vị lỗi dựa vào m-trail 2.2.1 Phát biểu bài toán Cho một tập các nút giám sát {MN0, . . ., MNn}, chúng ra cần thiết kế một giải pháp m-trail với số lượng nhỏ nhất tổng bước sóng giám sát, sao cho mỗi MN có thể thực hiện nhanh và rõ định vị liên kết lỗi chỉ dựa trên tín hiệu báo động quang cục bộ của nó. Nếu hai giải pháp đều có số bước sóng như nhau, thì giải pháp với số m-trail ít hơn sẽ được ưu tiên. Mỗi nút giám sát được phục vụ bằng tập m-trail đi qua nó. Nó xác định các lỗi liên kết bằng cách tham chiếu đến bảng mã báo động cục bộ (local alarm code table - LACT). Mỗi hàng trong LACT lưu trữ một mã báo động cục bộ (local alarm code - LAC) cho mỗi liên kết và mỗi cột được gọi là mã trail cho một m-trail. Ví dụ trong hình 2.1b, liên kết (0,1) của LAC là "001" và m-trail t0 có mã trail là "0001111". Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
19 L.kết t0, t1, t2 Phần thập phân (a) Giải pháp m-trail (b)Bảng mã báo động Hình 2.1.M - Trail Demo 2.2.2 Nguyên lý bước sóng nhỏ thông tin lớn Xét một tập các bộ giám sát {MN0, . . ., MNn}. Sau khi một m-trail mới được sinh ra, nó giúp xác định một vài liên kết lỗi mà có thể không phân biệt được (không với m-trail này). Do đó mã báo động khác nhau trong mỗi MN LACT có thể tăng bởi số δi , nó được định nghĩa như độ lợi thông tin cho MNi. Do đó thông tin toàn cục lấy được từ m-trail là δ = . Dường như, thông tin lấy được là tỷ lệ thuận với sự đóng góp m-trail cho việc định vị lỗi liên kết. Nguyên lý bước sóng nhỏ thông tin lớn có nghĩa là một m-trail với lượng thông tin thu được và giá trị bước sóng thấp là thích hợp hơn. Do vậy, hiệu suất của trail : η = được tính và nó phục vụ như là một độ đo để chọn những m-trail tốt, khi mà ω biểu diễn cho giá trị bước sóng của trail hiện tại . Trong hình 2.3 sau khi thêm một mã trail "0101001", giải pháp có thể phân biệt một kịch 1 liên kết lỗi MN0 và 2 hay nhiều Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn
20 kịch bản cho MN1. Nếu trail có 4 bước nhảy (có thể nếu một liên kết được đi qua 2 lần) hiệu suất của nó có thể tính bằng = 2.2.3 Thuật toán xác định m-trail 2.2.3.1 Ý tưởng của thuật toán Thuật toán xác định m-trail trong [12] được mô tả như hình 2.2 dưới đây. Chúng ta xét tuần tự mỗi MN dựa trên giải pháp chưa hoàn chỉnh giành được đối với tất cả những MNs được xem xét trước đó. Với những MN đang được xét, một LACT trước tiên được sinh ra với mã ngẫu nhiên. Nó bao gồm một tập các liên kết, mỗi một bộ bao gồm đồ thị con để biểu thị một trail. Trail sau đó chia thành các phần liên thông (CC) bằng tìm kiếm theo chiều sâu ngẫu nhiên (RDFS) trong đồ thị con, và những ứng cử trail (TC) trải qua MN hiện tại được rút từ CCs. Sau khi cải tiến TCs bằng việc tách trail và lặp trail, những trail hợp lệ cho MN hiện tại đã được thu lại. Nếu một trail có thể đạt được thông tin có lợi lớn nhất, nó được chọn dựa trên nguyên lý bước sóng nhỏ thông tin lớn. Ngược lại, nó bị xóa bỏ. Với mỗi trail được chọn, LACTs của tất cả MNs được phục vụ bởi nó được cập nhật. Kế tiếp, mã ngẫu nhiên được phát lại để tìm được nhiều ứng cử trail và thủ tục ở trên được lặp lại cho đến khi MN hiện tại có thể xác minh tất cả các liên kết lỗi. Sau đó thủ tục fix-zero được gọi để điều chỉnh giải pháp nếu LAC của một số liên kết bằng 0, và thủ tục code-shringking sẽ loại bỏ những trail dư thừa. Số hóa bởi Trung tâm Học liệu – ĐHTN http://www.lrc.tnu.edu.vn