BO GIAO DUC VA DAO TAO TRUONG DAI HOC BACH KHOA HA NOI NGUYÊN THÀNH ĐÔ NGHIÊN CỨU BÀI TOÁN CÁP PHÁT TÀI NGUYÊN TRONG MÔI TRƯỜNG ẢO HÓA MẠNG LUẬN VĂN THẠC SĨ KỸ THUẬT CONG NGHE THONG TIN Ha N6i - Nam 2015 BO GIAO DUC VA DAO TAO TRUONG DAI HOC BACH KHOA HA NOI NGUYEN THANH DO NGHIEN CUU BAI TOAN CAP PHAT TAI NGUYEN TRONG MOI TRUONG AO HOA MANG Chuyên ngành: Công Nghệ Thông Tin LUẬN VĂN THẠC SĨ KỸ THUẬT Công Nghệ Thông Tin NGƯỜI HƯỚNG DẪN PGS. Huỳnh Thị Thanh Bình Hà Nội - Năm 2015 CỘNG HIÒA XÃ IIOI CIIU NGIIIA VIET NAM Độc lập — Tự do — Ilạnh phúc BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ Họ và tên tac giá luận văn : Nguyễn Thành Đồ ĐỀ tài luận văn: Nghiễn cửu bài toán cấp phát tải nguyên trong môi trường ảo hóa mạng Chuyên ngành: Công nghệ thông tin Mã số SV:CB121353 Tác giả, Người hướng dẫn khoa học và Hội đồng chấm luận văn xác nhận tác piả dã sửa chữa, bỗ sung luận văn theo biên bản họp Hội đẳng ngày 25/04/2015 với các nội dưng sau: Hỗ các cụm tử “luận văn đề xuât”, Ngày tháng năm 2015 Giáo viên hướng dẫn Tác giả luận văn PGS. Huỳnh Thị Thanh Bình Nguyễn Thành Đô CHIỦ TỊCTI HỘI ĐỎNG TS. Nguyễn Thị Thu Hương Để tài: Nghiên cửu bài toán cắp phát tải nguyên trong mỗi trường áo hóa mạng, DANH MUC CAC KY HIỆU, CÁC CHỮ VIẾT TÁT VIẾT TẤT | VIẾT ĐÂY ĐỦ |Ý NGHĨA VM Virtual Machine May áo Virtual Machine - - _ VM-based Phương pháp đựa trên máy ảo.
Bascd Virtual Network ay 3a gà 2t 16 VNH AIẠ/ NGHVGY Bải toán ánh xạ mạng ảo vào mạng vật lý. Embedding Virtual Network ne 7 VNM Tài toán ánh xạ mạng âo Mapping Internet Servi : ISP nermerperviee hả cưng câp dịch vụ Internet. Provider Infrastructur : › InP —__ hả cung cấp hạ tẳng Provider SP Service Provider | Nhà cung cấp dịch vụ Quality - of- Dich vu cho thué tai nguyén dam bao Qos. A Service chất lượng hơn.
InaS Tastnenre88" | Coy sé ha tầng như là một địch vụ Infrastructure-as- a-Service End user Người yêu cầu tạo mang ao SN Substrate Node Đại diện cho một máy tính vật ly Đại diện cho một liên kết giữa hai máy SL Substrate Link 1. vật lý VN Virtual Node Dai dién cho một node trong mạng ảo. Đại diện cho một liên kết giữa hai node VL Virtual Link „ trong mang 40 Là bài toán cần giải quyél ma 161 da ham AP-Hard a lợi nhuận. Greedy Kode Thuật toán cấp phát tài nguyên trong môi GNM Mapping traimg mang GNM.
Knhance Cireedy Thuật toán cap phát tải nguyên trong môi TGNM - Node Mapping trường mạng BGNM. Hoe viên thục hiện: Nguyễn Thành Đô 8 Để tài: Nghiên cửu bài toán cắp phát tải nguyên trong mỗi trường áo hóa mạng, ĐANH MỤC CÁC CÔNG THỨC Công thức 2.1 Tinh substrate node.2 ‘Vinh substrate link 25 Công thức 2.3 Tối đa hàm lợi nhuận.4 Tối thiểu ham chi phi 31 Công thức 2.5 Ham muc tiéu.1 Tinh tai nguyên c„ 37 Công thức 3.2 Tinh tải nguyễn băng thông cụ.3 Hàm đánh giá tài nguyên tương quan CPU và băng thông 39 Học viên thực hiện: Nguyễn Thành Đô 10 Để tài: Nghiên cửu bài toán cắp phát tải nguyên trong mỗi trường áo hóa mạng, MỤC LỤC MỤC LỤC.61 CAM ON LOI CAM DOAN, H He Hee DANH MỤC CÁC KÝ HIỂU, CÁC CHỮ V DANH MỤC CÁC CÔNG THỨC. DANH MỤC BẢNG BIÊU DANH MỤC CÁC HÌNH VẼ. Lý do chọn đề tài.
Mục đích nghiên cứu. Pai tượng nghiên cứu Le 4. Phạm vi nghiên cứu 5. Phương pháp nghiên cứu 6.
Nội dung của luận văn Chương!: GIỚI THIỆU CHUNG 1. Các nghiên cứu liên quan.2 Phát biểu bài toán 1. Ý nghĩa của đề tài. Chương 2: CƠ SỞ LÝ TIUYÉT 2.Các thuật ngữ liên quan.
InP (nha cung cấp hạ tầng 2. Người ding cudi (end user) 2. Mô hinh mạng vật lý. Mô hinh mạng ảo.
Hoe viên thục hiện: Nguyễn Thành Đô 4 Để tài: Nghiên cửu bài toán cắp phát tải nguyên trong mỗi trường áo hóa mạng, DANH MUC CAC KY HIỆU, CÁC CHỮ VIẾT TÁT VIẾT TẤT | VIẾT ĐÂY ĐỦ |Ý NGHĨA VM Virtual Machine May áo Virtual Machine - - _ VM-based Phương pháp đựa trên máy ảo. Bascd Virtual Network ay 3a gà 2t 16 VNH AIẠ/ NGHVGY Bải toán ánh xạ mạng ảo vào mạng vật lý. Embedding Virtual Network ne 7 VNM Tài toán ánh xạ mạng âo Mapping Internet Servi : ISP nermerperviee hả cưng câp dịch vụ Internet. Provider Infrastructur : › InP —__ hả cung cấp hạ tẳng Provider SP Service Provider | Nhà cung cấp dịch vụ Quality - of- Dich vu cho thué tai nguyén dam bao Qos.
A Service chất lượng hơn. InaS Tastnenre88" | Coy sé ha tầng như là một địch vụ Infrastructure-as- a-Service End user Người yêu cầu tạo mang ao SN Substrate Node Đại diện cho một máy tính vật ly Đại diện cho một liên kết giữa hai máy SL Substrate Link 1. vật lý VN Virtual Node Dai dién cho một node trong mạng ảo. Đại diện cho một liên kết giữa hai node VL Virtual Link „ trong mang 40 Là bài toán cần giải quyél ma 161 da ham AP-Hard a lợi nhuận.
Greedy Kode Thuật toán cấp phát tài nguyên trong môi GNM Mapping traimg mang GNM. Knhance Cireedy Thuật toán cap phát tải nguyên trong môi TGNM - Node Mapping trường mạng BGNM. Hoe viên thục hiện: Nguyễn Thành Đô 8 Để tài: Nghiên cửu bài toán cắp phát tải nguyên trong mỗi trường áo hóa mạng, MỤC LỤC MỤC LỤC.61 CAM ON LOI CAM DOAN, H He Hee DANH MỤC CÁC KÝ HIỂU, CÁC CHỮ V DANH MỤC CÁC CÔNG THỨC. DANH MỤC BẢNG BIÊU DANH MỤC CÁC HÌNH VẼ.
Lý do chọn đề tài. Mục đích nghiên cứu. Pai tượng nghiên cứu Le 4. Phạm vi nghiên cứu 5.
Phương pháp nghiên cứu 6. Nội dung của luận văn Chương!: GIỚI THIỆU CHUNG 1. Các nghiên cứu liên quan.2 Phát biểu bài toán 1. Ý nghĩa của đề tài.
Chương 2: CƠ SỞ LÝ TIUYÉT 2.Các thuật ngữ liên quan. InP (nha cung cấp hạ tầng 2. Người ding cudi (end user) 2. Mô hinh mạng vật lý.
Mô hinh mạng ảo. Hoe viên thục hiện: Nguyễn Thành Đô 4 Để tài: Nghiên cửu bài toán cắp phát tải nguyên trong mỗi trường áo hóa mạng, LOT CAM ON Dể đạt được kết quả nghiên cứu của luận văn, đầu tiên tôi xin trân trọng cam ơn thầy hướng dẫn PGS. Huỳnh Thị Thanh Binh — Bộ môn Khoa học máy tính - Viện Công nghé ‘Thong tin -‘Truyén thông. lrường Dại học Bách Khoa Hà Nội, người đã tận tỉnh hưởng dẫn, giúp đỡ tôi trong quả trình thục hiện luận văn.
Dồng thời xin gửi lời cảm ơn tới Quý thầy cô giáo Trường Dại học Bách Khoa Hà Nội, đã tận tỉnh giắng dạy, truyền đạt chơ chúng tôi những kiến thức võ cùng quý giá trong suốt hai năm học qua. Tôi xin chân thành cảm ơn tới Ban giám hiệu Trường Dại học Kỹ thuật Tiậu cần CAND, nơi tôi công tác, dã tạo diễu kiện thuận lợi cho tôi hoàn thành khoá học nảy và toàn thể các dỗng chí trong đơn vị phòng Quản lý học viên, gia đình, bạn bẻ, đẳng nghiệp,. đã động viên giúp đỡ vả chia sẻ những khó khăn trong thời gian tôi tham gia khóa học Dù đã có rất nhiều cô gắng, song luận văn không tránh khỏi những hạn chế, thiểu sói. Kinh mong nhận được si chia sẽ và những dòng góp quý báu của các thấy cô giáo, bạn bè và đồng nghiệp.
Tôi xin trân trọng cắm ơn! Hà Nội, ngàu. năm 2015 Tác giả luận văn Nguyễn Thành Đô Hoe viên thục hiện: Nguyễn Thành Đô 6 Để tài: Nghiên cửu bài toán cắp phát tải nguyên trong mỗi trường áo hóa mạng, DANH MUC CAC KY HIỆU, CÁC CHỮ VIẾT TÁT VIẾT TẤT | VIẾT ĐÂY ĐỦ |Ý NGHĨA VM Virtual Machine May áo Virtual Machine - - _ VM-based Phương pháp đựa trên máy ảo. Bascd Virtual Network ay 3a gà 2t 16 VNH AIẠ/ NGHVGY Bải toán ánh xạ mạng ảo vào mạng vật lý. Embedding Virtual Network ne 7 VNM Tài toán ánh xạ mạng âo Mapping Internet Servi : ISP nermerperviee hả cưng câp dịch vụ Internet.
Provider Infrastructur : › InP —__ hả cung cấp hạ tẳng Provider SP Service Provider | Nhà cung cấp dịch vụ Quality - of- Dich vu cho thué tai nguyén dam bao Qos. A Service chất lượng hơn. InaS Tastnenre88" | Coy sé ha tầng như là một địch vụ Infrastructure-as- a-Service End user Người yêu cầu tạo mang ao SN Substrate Node Đại diện cho một máy tính vật ly Đại diện cho một liên kết giữa hai máy SL Substrate Link 1. vật lý VN Virtual Node Dai dién cho một node trong mạng ảo.
Đại diện cho một liên kết giữa hai node VL Virtual Link „ trong mang 40 Là bài toán cần giải quyél ma 161 da ham AP-Hard a lợi nhuận. Greedy Kode Thuật toán cấp phát tài nguyên trong môi GNM Mapping traimg mang GNM. Knhance Cireedy Thuật toán cap phát tải nguyên trong môi TGNM - Node Mapping trường mạng BGNM. Hoe viên thục hiện: Nguyễn Thành Đô 8 Để tài: Nghiên cửu bài toán cắp phát tải nguyên trong mỗi trường áo hóa mạng, Checking ¬ ce ans ˆ xã Ad Nod Thuật toán cầp phát tai nguyên trong môi PCANM jacency Nods | ne mang PCANM Mapping Ketwork interface | Card mạng, œŒ Mạng vật lý N Các nodo của mạng vật lý TỶ Các link của mạng vật lý 4At iCac thude tinh cia node rong mang vat Ag Các thuộc tính của liên kết trong mang : vật lý TẺ Các Path trong mạng vật lý Pp 'Tâp hợp các đường dẫn có thể ánh xạ a Mạng ảo NY Cc node trong mạng ảo LY Các liên kết trong mạng ão roe Node constraint của mạng ảo CY Link constraint ctla mang do Ry Tai nguyén phân bồ cho các node trong mang do Rt Tài nguyên được phân bố cho các liên kết trong mạng áo Hoe viên thục hiện: Nguyễn Thành Đô 9 Để tài: Nghiên cửu bài toán cắp phát tải nguyên trong mỗi trường áo hóa mạng, MỤC LỤC MỤC LỤC.61 CAM ON LOI CAM DOAN, H He Hee DANH MỤC CÁC KÝ HIỂU, CÁC CHỮ V DANH MỤC CÁC CÔNG THỨC.
DANH MỤC BẢNG BIÊU DANH MỤC CÁC HÌNH VẼ. Lý do chọn đề tài. Mục đích nghiên cứu. Pai tượng nghiên cứu Le 4.
Phạm vi nghiên cứu 5. Phương pháp nghiên cứu 6. Nội dung của luận văn Chương!: GIỚI THIỆU CHUNG 1. Các nghiên cứu liên quan.2 Phát biểu bài toán 1.
Ý nghĩa của đề tài. Chương 2: CƠ SỞ LÝ TIUYÉT 2.Các thuật ngữ liên quan. InP (nha cung cấp hạ tầng 2. Người ding cudi (end user) 2.
Mô hinh mạng vật lý. Mô hinh mạng ảo. Hoe viên thục hiện: Nguyễn Thành Đô 4 Để tài: Nghiên cửu bài toán cắp phát tải nguyên trong mỗi trường áo hóa mạng, LOT CAM DOAN Tôi xm cam đoan: 1.