Tóm tắt luận án tiến sĩ Khoa học máy tính: Nghiên cứu một số phương pháp lập lịch trong mạng chuyển mạch chùm quang

ĐẠI HỌC HUẾ<br /> TRƯỜNG ĐẠI HỌC KHOA HỌC<br /> <br /> NGUYỄN HỒNG QUỐC<br /> <br /> NGHIÊN CỨU MỘT SỐ PHƯƠNG PHÁP LẬP LỊCH<br /> TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG<br /> <br /> CHUYÊN NGÀNH: KHOA HỌC MÁY TÍNH<br /> MÃ SỐ: 62.48.01.01<br /> <br /> TÓM TẮT LUẬN ÁN TIẾN SĨ KHOA HỌC MÁY TÍNH<br /> <br /> Người hướng dẫn khoa học:<br /> 1. PGS.TS. Võ Viết Minh Nhật<br /> 2. TS. Nguyễn Hoàng Sơn<br /> <br /> HUẾ, NĂM 2017<br /> <br /> Luận án được hoàn thành tại Trường Đại học Khoa học, Đại học Huế.<br /> <br /> Người hướng dẫn:<br /> 1. PGS. TS. Võ Viết Minh Nhật. Đại học Huế, Việt Nam.<br /> 2. TS. Nguyễn Hoàng Sơn. Trường Đại học Khoa học, Đại học Huế., Việt Nam.<br /> <br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> ....................................................................................................................................<br /> <br /> MỞ ĐẦU<br /> 1. Tính cấp thiết của đề tài<br /> Mạng sợi quang từ khi ra đời vào thập niên 90 cho đến nay, đã trải qua nhiều thế hệ<br /> phát triển: từ những mô hình định tuyến bước sóng (Wavelength-Routed, WR) ban đầu<br /> dựa trên những đường quang (lightpath) đầu-cuối dành riêng, cho đến các mô hình chuyển<br /> mạch gói quang (Optical Packet Switching, OPS) được đề xuất gần đây, với ý tưởng xuất<br /> phát từ các mô hình mạng chuyển mạch gói điện tử. Tuy nhiên với một số hạn chế về<br /> công nghệ, như chưa thể sản xuất các bộ đệm quang (tương tự bộ nhớ RAM trong môi<br /> trường điện tử) hay các chuyển mạch ở tốc độ nano giây, mô hình chuyển mạch gói quang<br /> chưa thể trở thành hiện thực. Một giải pháp thỏa hiệp được đề xuất là chuyển mạch chùm<br /> quang (Optical Burst Switching, OBS) đã mở ra một hướng nghiên cứu mới và được xem<br /> là công nghệ hứa hẹn cho mạng Internet thế hệ tiếp theo.<br /> Một đặc trưng tiêu biểu của mạng chuyển mạch chùm quang (mạng OBS) là phần<br /> (gói) điều khiển (Burst Header Packet, BHP) được tách rời với phần (chùm) dữ liệu<br /> (Data Burst, DB). Nói một cách khác, để thực hiện việc truyền một chùm vào trong<br /> mạng lõi, gói điều khiển BHP được tạo ra và được gửi đi trước một khoảng thời gian<br /> offset(offset-time). Thời gian offset này phải được tính toán đủ để đặt trước tài nguyên<br /> và cấu hình các chuyển mạch tại các nút trung gian dọc theo hành trình của chùm quang<br /> từ nguồn đến đích. Tuy nhiên, cách truyền tải này cũng đặt ra áp lực là làm thế nào để<br /> một gói điều khiển BHP kịp lập lịch đặt trước tài nguyên và cấu hình chuyển mạch tại<br /> các nút lõi, đảm bảo việc truyền tải chùm quang theo sau; đó chính là nhiệm vụ của hoạt<br /> động lập lịch đặt trước tài nguyên tại các nút lõi mạng. Vì vậy vấn đề lập lịch rất cần<br /> được quan tâm và nghiên cứu nhằm tối đa hiệu suất băng thông, giảm mất mát dữ liệu<br /> và nâng cao hiệu suất hoạt động của mạng OBS.<br /> <br /> 2. Động lực nghiên cứu<br /> Lập lịch là một trong những hoạt động quan trọng trong mạng chuyển mạch chùm<br /> quang. Khi gói điều khiển của một chùm đến tại một nút lõi mạng, dựa vào thông tin<br /> được chứa trong gói điều khiển như thời điểm đến, thời điểm kết thúc của chùm, lúc này<br /> một giải thuật lập lịch sẽ được gọi để tìm kênh bước sóng ra khả dụng để lập lịch cho<br /> chùm đến.<br /> Mục đích chính của giải thuật lập lịch sắp xếp các chùm đến trên các kênh bước sóng<br /> ra, nhằm tối đa hiệu suất băng thông sử dụng, giảm số lượng chùm bị loại bỏ và nâng<br /> cao hiệu suất hoạt động của mạng OBS.<br /> Hiện đã có nhiều giải thuật lập lịch được đề xuất mà có thể được phân vào trong hai<br /> nhóm tiếp cận chính:<br /> • Phương pháp lập lịch trực tiếp.<br /> • Phương pháp lập lịch nhóm.<br /> Đối với phương pháp lập lịch trực tiếp khi một gói điều khiển đến một nút lõi mạng,<br /> một trong các giải thuật lập lịch trực tiếp sẽ được gọi ngay để tìm kênh bước sóng khả<br /> dụng lập lịch cho chùm của nó; nếu có nhiều hơn một kênh bước sóng khả dụng thì giải<br /> thuật lập lịch này sẽ chọn một kênh lập lịch mà tối ưu tiêu chí đặt ra của giải thuật.<br /> 1<br /> <br /> Nghiên cứu một số phương pháp lập lịch trong mạng chuyển mạch chùm quang<br /> Trong số các giải thuật lập lịch trực tiếp, BF-VF là giải thuật lập lịch tốt nhất về hiệu<br /> suất sử dụng băng thông. Tuy nhiên hiệu quả của lập lịch trực tiếp phụ thuộc vào tình<br /> trạng băng thông của các kênh ra mà trong đó các chùm đã lập lịch phân bố. Một số giải<br /> pháp kết hợp lập lịch trực tiếp với lập lịch lại và phân đoạn chùm đã được đề xuất. Cụ<br /> thể khi lập lịch trực tiếp không tìm thấy kênh khả dụng, thay vì chùm đến sẽ bị đánh<br /> rơi hoàn toàn, lập lịch lại sẽ sắp xếp lại các chùm đã được lập lịch trên các kênh bước<br /> sóng nhằm tìm kiếm vị trí băng thông rỗi để lập lịch cho chùm đến hoặc thực hiện phân<br /> đoạn chùm nhằm chỉ đánh rơi một phần của chùm đến bị tranh chấp. Tuy nhiên lập lịch<br /> trực tiếp và lập lịch trực tiếp kết hợp chỉ tối ưu việc lập lịch cho chùm đến hiện thời mà<br /> không quan tâm đến các chùm đến sau đó. Nên sự phân mãnh băng thông được tạo ra<br /> do việc lập lịch chùm hiện thời và có thể ảnh hưởng đến hiệu quả của các lập lịch sau đó.<br /> Phương pháp lập lịch nhóm do đó được đề xuất, trong đó các gói điều khiển đến trong<br /> một khoảng thời gian sẽ tiến hành lập lịch đồng thời các chùm tương ứng của chúng. Tuỳ<br /> thuộc vào các nút lõi mạng có được trang bị bộ chuyển đổi bước sóng đầy đủ hay không,<br /> các giải thuật lập lịch nhóm có thể chia thành hai nhóm: Lập lịch nhóm trên đơn kênh<br /> trong trường hợp không sử dụng bộ chuyển đổi và lập lịch nhóm trên đa kênh khi được<br /> trang bị các bộ chuyển đổi bước sóng đầy đủ.<br /> Tuy nhiên các giải thuật lập lịch nêu trên vẫn bộc lộ những tồn tại sau:<br /> • Giải thuật lập lịch kết hợp: chưa sử dụng giải thuật lập lịch trực tiếp tối ưu<br /> nhất ở giai đoạn 1 để lập lịch cho chùm đến. Việc lập lịch lại của các giải thuật ở<br /> giai đoạn 2 chỉ xem xét đối với chùm sau cùng nhất trên các kênh ra. Đoạn chồng<br /> lấp khi sử dụng kỹ thuật phân đoạn chùm ở giai đoạn 3 bị loại bỏ.<br /> • Giải thuật lập lịch nhóm trên đơn kênh: Độ phức tạp tính toán của các giải<br /> thuật cao; chưa tận dụng các khoảng trống băng thông được tạo ra giữa các chùm<br /> đã được lập lịch để lập lịch cho các chùm đến và khe thời gian chờ lập lịch được<br /> thiết lập với một giá trị cố định mà chưa quan tâm lưu lượng các chùm đến.<br /> • Giải thuật lập lịch nhóm trên đa kênh: Các giải thuật theo hướng tiếp cận<br /> heuristic chưa đưa ra tiêu chí chọn tối ưu lập lịch cho các chùm đến mà chỉ dựa vào<br /> thứ tự sắp xếp. Các giải thuật lập lịch tối ưu làm tăng số lượng gói điều khiển, yêu<br /> cầu hệ thống phải có sự thay đổi về mặt giao thức. Hơn nữa việc gỡ hết các chùm<br /> đã được lập lịch trên các kênh để đưa về bài toán lập lịch trên máy đồng nhất là<br /> không thực tế trên mạng thật.<br /> Những tồn tại nêu trên chính là động lực để Luận án tập trung nghiên cứu, cải tiến và<br /> đề xuất mới các giải thuật lập lịch nhằm tối thiểu mất mất dữ liệu, tối đa băng thông sử<br /> dụng, giảm thời gian chờ lập lịch, giảm độ phức tạp tính toán và nâng cao hiệu quả hoạt<br /> động mạng OBS.<br /> <br /> 3. Mục tiêu nghiên cứu của luận án<br /> Mục tiêu của Luận án là nghiên cứu, cải tiến và đề xuất một số giải thuật lập lịch<br /> nhằm nâng cao hiệu năng của mạng chuyển mạch chùm quang bao gồm: tối thiểu mất<br /> mát dữ liệu, tối đa hiệu suất băng thông, giảm độ trễ và giảm độ phức tạp tính toán.<br /> Mục tiêu cụ thể của Luận án là:<br /> • Nghiên cứu, cải tiến giải thuật lập lịch trực tiếp kết hợp với lập lịch lại và phân<br /> đoạn chùm.<br /> 2<br /> <br /> Nghiên cứu một số phương pháp lập lịch trong mạng chuyển mạch chùm quang<br /> <br /> • Nghiên cứu, cải tiến và đề xuất mới giải thuật lập lịch nhóm trên đơn kênh.<br /> • Nghiên cứu, cải tiến và đề xuất mới giải thuật lập lịch nhóm trên đa kênh.<br /> Trên cơ sở mục tiêu nghiên cứu, Luận án được triển khai theo ba vấn đề nghiên cứu chính:<br /> • Vấn đề 1 : Cải tiến giải thuật kết hợp lập lịch trực tiếp với lập lịch lại và phân đoạn<br /> chùm.<br /> • Vấn đề 2 : Cải tiến và đề xuất mới giải thuật lập lịch nhóm trên đơn kênh.<br /> • Vấn đề 3 : Cải tiến và đề xuất mới giải thuật lập lịch nhóm trên đa kênh.<br /> <br /> 4. Đóng góp của Luận án<br /> Các đóng góp chính của Luận án bao gồm:<br /> • Đề xuất giải thuật lập lịch trực kết hợp lập lịch lại và phân đoạn chùm iCSA[CT2].<br /> • Đề xuất giải thuật lập lịch nhóm trên đơn kênh LGS[CT8] và các cải tiến LGSVF[CT4], LAGS[CT5], LAGS-VF[CT7].<br /> • Đề xuất giải thuật lập lịch nhóm trên đa kênh OPT-GS theo hướng tiếp cận tối<br /> ưu và LGS-MC[CT6], LGS-MC-VF[CT3], MWC-GS[CT1], MWC-VF-GS[CT1] theo<br /> hướng tiếp cận heuristic.<br /> <br /> CHƯƠNG 1: TỔNG QUAN VỀ LẬP LỊCH<br /> TRONG MẠNG CHUYỂN MẠCH CHÙM QUANG<br /> 1.1. Tóm lược lịch sử phát triển của truyền thông quang<br /> 1.2. Các mô hình chuyển mạch quang<br /> Các mô hình chuyển mạch quang có thể được chia thành 3 loại: chuyển mạch kênh<br /> quang, chuyển mạch gói quang và chuyển mạch chùm quang.<br /> <br /> 1.2.1. Chuyển mạch kênh quang<br /> 1.2.2. Chuyển mạch gói quang<br /> 1.2.3. Chuyển mạch chùm quang<br /> <br /> 1.3. Mạng chuyển mạch chùm quang<br /> Mạng OBS được xem như là một công nghệ hứa hẹn cho mạng Internet toàn quang thế<br /> hệ kế tiếp bởi nó có nhiều chức năng và ưu điểm hơn so với các mạng chuyển mạch quang<br /> khác. Một số đặc trưng của mạng OBS như sau: Tách biệt giữa kênh truyền gói điều khiển<br /> và kênh truyền chùm; Dành riêng một chiều; Độ dài chùm thay đổi được; Không cần bộ<br /> đệm quang.<br /> <br /> 1.3.1. Kiến trúc mạng OBS<br /> Một mạng OBS bao gồm các nút chuyển mạch chùm quang (nút OBS) kết nối với nhau<br /> bởi các sợi quang. Mỗi sợi quang có khả năng hỗ trợ các kênh đa bước sóng. Có hai kiểu<br /> nút trong mạng OBS: nút biên và nút lõi.<br /> <br /> 3<br /> <br />