Đại Học Quốc Gia Tp Hồ Chí Minh TRƯỜNG ĐẠI HỌC BÁCH KHOA ……………… CHU CÔNG HẠNH ỨNG DỤNG MẠNG NEURON DỰ ĐỐN BĂNG THƠNG NHẰM CẢI TIẾN THUẬT TỐN CSPF, NÂNG CAO HIỆU SUẤT SỬ DỤNG TÀI NGUYÊN MẠNG MPLS CHUYÊN NGHÀNH: KỸ THUẬT ĐIỆN TỬ MÃ SỐ NGHÀNH: 60.52.50 LUẬN VĂN THẠC SĨ TP HỒ CHÍ MINH, tháng 01 năm 2011 CƠNG TRÌNH ĐƯỢC HỒN THÀNH TẠI TRƯỜNG ĐẠI HỌC BÁCH KHOA ĐẠI HỌC QUỐC GIA TP HỒ CHÍ MINH Cán hướng dẫn khoa học: TS LƯU THANH TRÀ Cán chấm nhận xét 1: TS LÊ TIẾN THƯỜNG Cán chấm nhận xét 2: TS PHẠM HỒNG LIÊN Luận văn thạc sĩ bảo vệ tại: HỘI ĐỒNG CHẤM BẢO VỆ LUẬN VĂN THẠC SĨ TRƯỜNG ĐẠI HỌC BÁCH KHOA TP.HCM Ngày 09 tháng 03 năm 2011 TRƯỜNG ĐẠI HỌC BÁCH KHOA CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM PHÒNG ĐÀO TẠO SĐH ĐỘC LẬP – TỰ DO – HẠNH PHÚC TP.HCM, ngày… tháng … năm 2011 NHIỆM VỤ LUẬN VĂN THẠC SĨ Họ tên học viên: CHU CÔNG HẠNH Phái: Nam Ngày, tháng, năm sinh: 07/08/1981 , Nơi sinh: Kiên Giang Chuyên ngành:Kỹ thuật Điện tử MSHV: 09140009 I TÊN ĐỀ TÀI: Ứng dụng mạng Neural dự đốn băng thơng mạng nhằm cải tiến thuật toán CSPF, nâng cao hiệu suất sử dụng tài nguyên mạng MPLS II NHIỆM VỤ VÀ NỘI DUNG: Nhiệm vụ: ứng dụng mạng Neuron để dự đốn thơng tin băng thơng mạng, thơng tin băng thơng dự đốn ứng dụng để cải tiến thuật toán CSPF mạng MPLS/IP, nhằm nâng cao tỷ lệ thiết lập LSP, giảm tỷ lệ từ chối băng thông mạng, nâng cao hiệu sử dụng tài nguyên mạng sẵn có Nội dung: Đề tài tập trung vào nội dung ứng dụng kết dự đốn băng thơng từ mạng Nơron để cải tiến thuật toán CSPF Phần đầu, tác giả trình bày vấn đề ứng dụng mạng neuron việc dự đốn băng thơng mạng MPLS, giải pháp Eswadarass chứng minh Việc dự đốn băng thơng tương lai mạng MPLS có vai trị quan trọng ứng dụng vào nhiều mục đích khác Phần thứ hai đề tài nghiên cứu ứng dụng kết dự đoán vào để cải tiến thuật toán CSPF nhằm đưa thuật toán cải tiến mới, có hiệu suất sử dụng tài nguyên mạng tốt hơn, giảm tỷ lệ từ chối LSP MPLS, tối thiểu vấn đề nghẽn mạng III NGÀY GIAO NHIỆM VỤ: 20/09/2010 IV NGÀY HOÀN THÀNH NHIỆM VỤ: 28/01/2011 V CÁN BỘ HƯỚNG DẪN: TS LƯU THANH TRÀ CÁN BỘ HƯỚNG DẪN ( Học hàm, học vị, họ tên, chữ ký) CN BỘ MÔN QL CHUYÊN NGÀNH TS LƯU THANH TRÀ TS ĐỔ HỒNG TUẤN Nội dung đề cương luận văn thạc sĩ hội đồng chuyên ngành thơng qua Ngày TRƯỞNG PHỊNG ĐT-SĐH tháng năm 2011 TRƯỞNG KHOA QL NGÀNH LỜI CẢM ƠN Trước hết Em xin bày tỏ lòng biết ơn sâu sắc Thầy Lưu Thanh Trà Thầy Trần Trung Tính, người tận tình hướng dẫn, cung cấp kiến thức vô quý giá giúp đỡ Em suốt trình nghiên cứu thực luận văn Xin chân thành cảm ơn quý Thầy Cô trường ĐHBK TP.HCM giảng dạy, truyền đạt tri thức khoa học giúp Em trưởng thành suốt khóa học sống Xin chân thành cảm ơn Anh Chị, bạn bè lớp Kỹ thuật Điện tử, khố 2009 giúp đỡ q trình học tập sống Do thời gian có hạn, Đề tài khơng thể tránh sai sót, hạn chế mà đề tài chưa kịp đề cập tới, mong Quý thầy cô, đồng nghiệp anh chị đóng góp để đề tài hồn thiện TP.HCM, tháng 01 năm 2011 CHU CÔNG HẠNH TÓM TẮT LUẬN VĂN THẠC SĨ Trong năm gần đây, mạng internet ngày phát triển nhiều lĩnh vực khác Có nhiều ứng dụng mạng phát triển dựa tảng nguồn tài nguyên hữu hạn mạng Tuy nhiên, tài nguyên mạng sử dụng chung lượng băng thông mạng thời điểm khác nhau, đó, việc định routing dựa vào “đường ngắn nhất” giao thức có khơng tối ưu, đặc biệt mạng có lưu lượng đột biến… Dự đốn băng thơng mạng vấn đề nhiều người quan tâm Dựa vào thơng tin này, thiết bị mạng đưa định cho routing, điều khiển lưu lượng… cách tốt Trong đề tài này, tác giả tập trung trình bày vấn đề ứng dụng kết việc dự đoán băng thơng vào cải tiến lại thuật tốn CSPF có Nhằm mục đích đưa thuật tốn cải tiến mới, có khả sử dụng hiệu nguồn tài nguyên mạng có, giảm tỷ lệ từ chối thiết lập đường hầm (hay LSP-label switch path) Do vấn đề xây dựng mạng Neural phức tạp, nên đề tài trình bày sơ lược vấn đề dự đốn băng thơng giải pháp xây dựng mạng neuron Đề tài sử dụng kết xây dựng dự đốn [6] Trên thực tế, thơng tin dự đốn băng thơng được ứng dụng rộng rãi nhiều ứng dụng khác Đề tài trình bày tập trung việc ứng dụng thông tin dự đoán để cải tiến thuật toán CSPF, nhằm khắc phục nhược điểm CSPF tại, nâng cao hiệu sử dụng mạng MPLS/IP Đề tài trình bày gồm sáu phần chính: Chương trình bày tổng quan đề tài cơng trình khoa học liên quan Chương hai trình bày sơ lược cơng nghệ MPLS Chương ba trình bày chi tiết thuật tốn CSPF, vấn đề tồn thuật toán Nội dung chương bốn tập trung xây dựng mạng Neural ứng dụng việc dự đốn băng thơng mạng MPLS/IP Chương năm triển khai việc cải tiến CSPF dựa thơng tin băng thơng dự đốn từ mạng Neural xây dựng chương Và cuối xây dựng mơ hình mơ kết đạt được, hướng phát triển đề tài Cải tiến CSPF dựa thơng tin dự đốn băng thông GVHD: TS Lưu Thanh Trà MỤC LỤC MỤC LỤC DANH MỤC CÁC HÌNH VẼ, BIỂU ĐỒ CHƯƠNG 1: GIỚI THIỆU VỀ LUẬN VĂN VÀ CÁC CT KHOA HỌC LIÊN QUAN 11 1.1 Sơ lược toán dự đốn băng thơng 11 1.2 Sơ lược CSPF vấn đề tồn 12 1.3 Một số cơng trình khoa học liên quan 12 1.4 Giới thiệu luận văn 14 1.4.1 Mục đích nhiệm vụ luận văn 14 1.4.3 Tính thực tiễn luận văn 15 CHƯƠNG 2: GIỚI THIỆU CÔNG NGHỆ MPLS/IP 17 2.1 Sơ lược MPLS thuật toán CSPF 17 2.2 MPLS TE ( Traffic Eginneering) 18 2.2.1 Những hạn chế chế điều khiển IGP tại: 18 2.2.2 Tổng quan quản lý lưu lượng MPLS 20 2.2.3 Hoạt động MPLS TE 22 CHƯƠNG 3: THUẬT TOÁN CONSTRAINT SHORTEST PATH FISRT 24 3.1 Giới thiệu chung 24 3.2 Thuật toán SPF 25 3.3 Giải thuật CSPF: 26 3.4 Giao thức chiếm trước tài nguyên (RSVP - Resource Reservation Protocol) 31 CHƯƠNG 4: ỨNG DỤNG MẠNG NEURON TRONG DỰ ĐOÁN BĂNG THÔNG 39 4.1 Giới thiệu 39 4.2 Tổng quát mạng Neuron nhân tạo: 41 4.2.1 Cấu trúc mạng Neuron 41 4.2.2 Hàm hoạt động 42 4.2.3 Tiến trình học 43 4.2.4 Giải thuật lan truyền ngược (Back Propagation) 44 4.2.5 Ứng dụng mạng Neuron 44 4.3 Mạng Neuron vấn đề dự đốn băng thơng 47 4.3.1 Quá trình thống kê tiền xử lý liệu 49 4.3.2 Huấn luyện mạng Neuron 49 4.3.3 Dự đốn băng thơng mạng Neuron 49 SVTH: Chu Công Hạnh Cải tiến CSPF dựa thơng tin dự đốn băng thơng GVHD: TS Lưu Thanh Trà 4.3.4 Mơ hình hóa mạng hỗ trợ dự đốn băng thông: 51 CHƯƠNG 5:CẢI TIẾN CSPF DỰA TRÊN THƠNG TIN DỰ ĐỐN BĂNG THÔNG 55 5.1 Giới thiệu 55 5.2 Các tiêu chí đánh giá hiệu thuật toán định tuyến: 56 5.3 Thuật toán CSPF cải tiến: 56 5.3.1 Các bước thuật tốn: 58 5.3.2 Các phương pháp định CSPF mở rộng 61 5.3.3 Tối ưu hóa lại tunnel CSPF-ex: 63 CHƯƠNG 6: MÔ PHỎNG VÀ KẾT LUẬN 64 6.1 Phạm vi giới hạn Đề tài: 64 6.2 Mơ hình mạng: 64 6.2.1 Mô thuật tốn với mơ hình 08 router: 64 6.2.2 Mô thuật tốn với mơ hình 16 router: 69 6.2.3 Mô thuật tốn với mơ hình 20 router 73 6.3 Kết luận 77 6.4 Hướng phát triển Đề tài 77 MỤC LỤC 1: CHƯƠNG TRÌNH MƠ PHỎNG VỚI 08 ROUTER 79 MỤC LỤC 2: CHƯƠNG TRÌNH MƠ PHỎNG VỚI 16 ROUTER 86 MỤC LỤC 3: CHƯƠNG TRÌNH MƠ PHỎNG VỚI 20 ROUTER 95 References: 107 SVTH: Chu Công Hạnh Cải tiến CSPF dựa thơng tin dự đốn băng thơng GVHD: TS Lưu Thanh Trà DANH MỤC CÁC HÌNH VẼ, BIỂU ĐỒ Hình 2.1: Chức kỹ thuật điều khiển lưu lượng Hình 3.1: Lưu đồ thuật tốn CSPF Hình 3.2: Mơ hình mạng đơn giản minh họa thuật tốn CSPF Hình 3.3: Mơ tả q trình tối ưu hóa lại đường hầm Hình 3.4: Quá trình thiết lập đường RSVP Hình 3.5: Cơ chế Make-Before-Break Hình 3.6: Sự cần thiết cho Make-Before-Break Hình 4.1: Các bước dự đốn băng thơng Hình 4.2: Cấu trúc mạng Neural Hình 4.3: Tiến trình học mạng nơron Hình 4.4: Mơ tả Giải thuật lan truyền ngược Hình 4.5: Mơ hình điều khiển dự đốn Hình 4.6: Mơ hình điều khiển mạng NARMA-L2 Hình 4.7: Mơ hình áp dụng mạng neural dự đốn băng thơng Hình 4.8: Mơ hình áp dụng neural TE Hình 4.9: Mơ hình server tập trung hỗ trợ dự đốn băng thơng Hình 4.10: Dự đốn băng thơng mạng neural Hình 4.11: Mơ hình mạng neural dự đốn băng thơng Hình 5.1: Mơ hình chức CSPF mở rộng router Hình 5.2: Mơ hình lưu đồ giải thuật CSPF mở rộng Hình 5.3: Mơ hình mơ tả hoạt động thuật tốn CSPF mở rộng Hình 5.4: Mơ hình mạng với u cầu băng thơng ràng buộc 10bps Hình 6.1: Mơ hình mạng mơ cho thuật tốn với 08 router SVTH: Chu Cơng Hạnh Cải tiến CSPF dựa thơng tin dự đốn băng thơng GVHD: TS Lưu Thanh Trà Hình 6.1a Mơ hình 08 router thiết lập ns-2 Hình 6.1b Kết so sánh số LSP thiết lập Hình 6.1c Kết so sánh xác xuất thiết lập LSP thành công hai thuật tốn Hình 6.1d Kết so sánh tỷ lệ Bandwith reject ration hai thuật tốn Hình 6.1e Kết so sánh thời gian thực thi hai thuật tốn Hình 6.2: Mơ hình mạng mơ cho thuật tốn với 16 router Hình 6.2a Mơ hình mạng 16 router thiết lập ns-2 Hình 6.2b Kết so sánh số LSP thiết lập Hình 6.2c Kết so sánh xác xuất thiết lập LSP thành công hai thuật tốn Hình 6.2d Kết so sánh tỷ lệ Bandwith reject ration hai thuật tốn Hình 6.2e Kết so sánh thời gian thực thi hai thuật tốn Hình 6.3: Mơ hình mạng mơ cho thuật tốn với 16 router Hình 6.3a Mơ hình mạng 20 router thiết lập ns-2 Hình 6.3b Kết so sánh số LSP thiết lập Hình 6.3c Kết so sánh xác xuất thiết lập LSP thành cơng hai thuật tốn Hình 6.3d Kết so sánh tỷ lệ Bandwith reject ration hai thuật toán Hình 6.3e Kết so sánh thời gian thực thi hai thuật tốn SVTH: Chu Cơng Hạnh 10 ... Chuyên ngành:Kỹ thuật Điện tử MSHV: 09140009 I TÊN ĐỀ TÀI: Ứng dụng mạng Neural dự đốn băng thơng mạng nhằm cải tiến thuật toán CSPF, nâng cao hiệu suất sử dụng tài nguyên mạng MPLS II NHIỆM VỤ... thứ hai đề tài nghiên cứu ứng dụng kết dự đoán vào để cải tiến thuật toán CSPF nhằm đưa thuật tốn cải tiến mới, có hiệu suất sử dụng tài nguyên mạng tốt hơn, giảm tỷ lệ từ chối LSP MPLS, tối thiểu... được ứng dụng rộng rãi nhiều ứng dụng khác Đề tài trình bày tập trung việc ứng dụng thơng tin dự đốn để cải tiến thuật toán CSPF, nhằm khắc phục nhược điểm CSPF tại, nâng cao hiệu sử dụng mạng MPLS/ IP