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.

- 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 CÔNG NGHỆ THÔNG TIN Hà Nội - Năm 2015 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƢỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI.
- 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 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.TS.
- Huỳnh Thị Thanh Bình Hà Nội - Năm 2015 CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập – Tự do – Hạnh phúc BẢN XÁC NHẬN CHỈNH SỬA LUẬN VĂN THẠC SĨ Họ và tên tác 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 giả đã sửa chữa, bổ sung luận văn theo biên bản họp Hội đồng ngày với các nội dung sau: Bỏ các cụm từ “luận văn đề xuất”.
- 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 Học viên thực hiện: Nguyễn Thành Đô 4 MỤC LỤC MỤC LỤC.
- Mục đích nghiên cứu.
- Đối tƣợng nghiên cứu.
- Phạm vi nghiên cứu.
- Phƣơng pháp nghiên cứu.
- Các nghiên cứu liên quan.
- Ảo hóa mạng.
- Mô hình mạng vật lý.
- Mô hình mạng ảo.
- 23 Đề 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 Học viên thực hiện: Nguyễn Thành Đô 5 2.1.8.
- Nhúng mạng ảo (Virtual Network Embedding.
- Cơ chế ánh xạ mạng ảo vào mạng vật lý.
- 33 CÁC THUẬT TOÁN ÁNH XẠ MẠNG ẢO.
- Thuật toán ánh xạ mạng ảo SID (Subgraph Isomorphism Detection )33 3.2.
- Thuật toán ánh xạ GNM.
- Thuật toán EGNM.
- Thuật toán PCANM.
- Nhƣng phƣơng pháp này chỉ hiệu quả với các mạng ảo có cấu trúc giống nhau.
- Với các mạng ảo có cấu trúc khác nhau, ta cần xem xét mạng ảo ở các mức node.
- Ánh xạ hàng xóm.
- 52 Đề 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 Học viên thực hiện: Nguyễn Thành Đô 6 LỜI CẢM ƠN Để đạ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 cảm ơn thầy hƣớng dẫn PGS.TS.
- Tôi xin trân trọng cảm ơn! Hà Nội, ngày… Tháng … năm 2015 Tác giả luận văn Nguyễn Thành Đô Đề 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 Học viên thực hiện: Nguyễn Thành Đô 7 LỜI CAM ĐOAN Tôi xin cam đoan: 1.
- Hà nội, ngày … tháng … năm 2015 Tác giả luận văn Nguyễn Thành Đô Đề 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 Học viên thực hiện: Nguyễn Thành Đô 8 DANH MỤC CÁC KÝ HIỆU, CÁC CHỮ VIẾT TẮT VIẾT TẮT VIẾT ĐẦY ĐỦ Ý NGHĨA VM Virtual Machine Máy ảo.
- VNE Virtual Network Embedding Bài toán ánh xạ mạng ảo vào mạng vật lý.
- VNM Virtual Network Mapping Bài toán ánh xạ mạng ảo ISP Internet Service Provider Nhà cung cấp dịch vụ Internet.
- QoS Quality - of - Service Dịch vụ cho thuê tài nguyên đảm bảo chất lƣợng hơn.
- End user Ngƣời yêu cầu tạo mạng ảo.
- SN Substrate Node Đại diện cho một máy tính vật lý.
- SL Substrate Link Đại diện cho một liên kết giữa hai máy vật lý VN Virtual Node Đại diện cho một node trong mạng ảo.
- VL Virtual Link Đại diện cho một liên kết giữa hai node trong mạng ảo.
- GNM Greedy Node Mapping Thuật toán cấp phát tài nguyên trong môi trƣờng mạng GNM.
- EGNM Enhance Greedy Node Mapping Thuật toán cấp phát tài nguyên trong môi trƣờng mạng EGNM.
- Đề 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 Học viên thực hiện: Nguyễn Thành Đô 9 PCANM Checking Adjacency Node Mapping Thuật toán cấp phát tài nguyên trong môi trƣờng mạng PCANM.
- Network interface Card mạng Gs Mạng vật lý Ns Các node của mạng vật lý Ls Các link của mạng vật lý ANs Các thuộc tính của node trong mạng vật lý ALs Các thuộc tính của liên kết trong mạng vật lý Ps Các Path trong mạng vật lý PP Tập hợp các đƣờng dẫn có thể ánh xạ GV Mạng ảo NV Các node trong mạng ảo LV Các liên kết trong mạng ảo CNV Node constraint của mạng ảo CLV Link constraint của mạng ảo RN Tài nguyên phân bổ cho các node trong mạng ảo RL Tài nguyên đƣợc phân bổ cho các liên kết trong mạng ảo Đề 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 Học viên thực hiện: Nguyễn Thành Đô 10 DANH MỤC CÁC CÔNG THỨC Công thức 2.1: Tính substrate node.
- 32 Công thức 3.1: Tính tài nguyên cn.
- 37 Công thức 3.2: Tính tài nguyên băng thông cv.
- 39 Công thức 3.3: Hàm đánh giá tài nguyên tƣơng quan CPU và băng thông.
- 39 Đề 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 Học viên thực hiện: Nguyễn Thành Đô 11 DANH MỤC BẢNG BIỂU Bảng 3.1: Giải thuật SID.
- 35 Bảng 3.4: Tóm tắt thuật toán của giai đoạn ánh xạ node.
- 38 Bảng 3.5: Tóm tắt thuật toán của giai đoạn ánh xạ liên kết.
- 50 Đề 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 Học viên thực hiện: Nguyễn Thành Đô 12 DANH MỤC CÁC HÌNH VẼ Hình 2.1: Mô hình mạng vật lý.
- 22 Hình 2.2: Mô hình mạng ảo.
- 23 Hình 2.3 Ánh xạ mạng ảo vào mạng vật lý.
- 27 Hình 2.5Mô tả cấu trúc mạng vật lý S.
- 28 Hình 2.6 Tập các mạng ảo R.
- 29 Hình 2.7 Mô hình mạng ảo với node và link.
- 29 Hình 2.8: Tập đồ thị đƣợc ánh xạ.
- 30 Hình 2.9: Đồ thị ánh xạ giữa mạng ảo và mạng vật lý.
- 30 Hình 2.10: Ví dụ ánh xạ giữa 1 mạng ảo vào mạng vật lý.
- 30 Hình 2.11: Đầu ra tập các cạnh ánh xạ.
- 31 Hình 3.1: Mô hình ánh xạ mạng ảo trong SID.
- 37 Hình 3.3: Đồ thị mạng vật lý S.
- 42 Hình 3.5: Mạng ảo đƣợc yêu cầu.
- 42 Hình 3.6: Chọn node ảo có yêu cầu tài nguyên lớn nhất.
- 43 Hình 3.7: Tìm node vật lý thích hợp theo bậc và tài nguyên.
- 43 Hình 3.8: Kiểm tra khả năng ánh xạ của liên kết lần 1.
- 44 Hình 3.9: Kiểm tra khả năng ánh xạ của liên kết lần 2.
- 44 Hình 3.10: Kiểm tra khả năng ánh xạ của liên kết lần 3.
- 50 Đề 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 Học viên thực hiện: Nguyễn Thành Đô 13 MỞ ĐẦU 1.
- Trong ảo hóa mạng, các tài nguyên vật lý: node vật lý và liên kết vật lý đƣợc chia sẻ cho các mạng ảo đƣợc yêu cầu.
- Một vấn đề quan trong trong hoạt động của mạng ảo là sự phân bố các node và các liên kết đến các yêu cầu tạo mạng ảo.
- Trong khi có rất nhiều thuật toán ánh xạ mạng ảo khác nhau, do đó rất khó đánh giá hiệu quả của các thuật toán đó.
- Các tài nguyên vật lý: phần cứng và băng thông liên kết là hữu hạn do đó tồn tại một vấn đề quan trọng trong ảo hóa mạng là vấn đề phân chia tài nguyên cho các node ảo và các liên kết giữa các node của mạng ảo.
- Vì vậy ta cần một thuật toán cấp phát tài nguyên cho các mạng ảo mà vẫn phải đảm bảo tối đa lợi nhuận và tối thiểu chi phí.
- Hơn nữa ta còn phải tăng tỉ lệ tiếp nhận mạng ảo.Luận văntrình bày một thuật toán tối ƣu hàm mục tiêu, tăng giá trị lợi nhuận dựa trên các thuật toán đã có.
- Mục đích nghiên cứu Luận văntập trung tìm hiểu và đƣa ra một thuật toán ánh xạ mạng ảo vào mạng vật lý mà từ đó hàm mục tiêu đƣợc cải thiện.
- Để đạt đƣợc các mục tiêu này, luận văn tập trung vào các nhiệm vụ cụ thể sau: -Tìm hiểu khái niệm, mô hình hoạt động của mạng ảo, cơ chế ánh xạ mạng ảo vào mạng vật lý.
- Tìm hiểu các thuật toán ánh xạ mạng ảo hiện tại.
- Tìm hiểu cơ chế và các ƣu nhƣợc điểm của các thuật toán đó.
- Từ đó đƣa ra cải tiến nhằm tăng giá trị Đề 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 Học viên thực hiện: Nguyễn Thành Đô 14 mục tiêu, tăng tỉ lệ chấp nhận và tăng giá trị lợi nhuận thu đƣợc khi ánh xạ mạng ảo.
- Đƣa ra thuật toán ánh xạ mạng ảo vào mạng vật lý nhằm đáp ứng tối đa các nhu cầu và hàm lợi nhuận dựa trên hạ tầng mạng vật lý hiện tại đã có.
- Đối tƣợng nghiên cứu Luận văn tập trung vào tìm hiểucácthuật toán ánh xạ mạng ảo vào mạng vật lý.
- Luận văn tập trung vào nghiên cứu mạng vật lý, các mạng ảo đƣợc yêu cầu có mô hình tƣơng tự nhau.
- Phạm vi nghiên cứu Luận văn tìm hiểu và trình bày một thuật toán sử dụng tài nguyên hợp lý nhất cho mạng ảo.
- Luận văn tập trung nghiên cứu các mạng ảo có cấu trúc tƣơng tự nhau từ đó so sánh đƣợc các ƣu điểm, khả năng cải thiện các yêu cầu so với các thuật toán ánh xạ hiện tại.
- Tổng hợp các tài liệu lý thuyết về các thuật toán ánh xạ mạng ảo vào mạng vật lý.
- Nghiên cứu các thuật toán ánh xạ mạng ảo đã có và phân tích các thuật toán đó.
- Từ đó đƣa ra các các cải thiện so với thuật toán đã có.
- Chƣơng 2: Cơ sở lý thuyết: Chƣơng này nhằm giới thiệu những lý thuyết, khái niệm chung nhất liên quan: Mạng ảo, cơ chếchia sẻ tài nguyên của nhiều mạng ảo trên một mạng vật lý.
- Đề 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 Học viên thực hiện: Nguyễn Thành Đô 15 Chƣơng 3: Giải bài toán cấp phát tài nguyên trong môi trƣờng ảo hóa mạ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 Học viên thực hiện: Nguyễn Thành Đô 16 Chƣơng1: GIỚI THIỆU CHUNG 1.1.
- Trên thế giới đã có nhiều nghiên cứu để giải quyết bài toán ánh xạ mạng ảo vào mạng vật lý.
- Nhƣng các nghiên cứu trƣớc đó đều tập trung vào giải quyết bài toán tăng giá trị lợi nhuận, giảm chi phí.
- Hơn nữa, các nghiên cứu trƣớc đó đều giải quyết vấn đề ánh xạ mạng ảo sau khi các yêu cầu mạng ảo đến.
- Điều này đã làm tiêu tốn thời gian tính toán để có thể ánh xạ một mạng ảo vào mạng vật lý: kiểm tra tài nguyên CPU của node, băng thông của các liên kết vật lý để đáp ứng đƣợc các yêu cầu.
- Một yêu cầu mạng ảo khi đến mới đƣợc kiểm tra, do đó không kiểm tra khả năng tài nguyên của node và liên kết trƣớc khi đến để tránh tình trạng yêu cầu đến mà không đáp ứng đƣợc chi phí nhiều thời gian xử lý các yêu cầu.
- Luận văn này đã tiếp cận bài toán theo một cách mới, đó là kiểm tra tài nguyên trƣớc khi yêu cầu đến.
- So với các giải thuật trƣớc đó, luận văn đã cải tiến bằng cách nhóm các node theo bậc thay vì nhóm tất cả các node vào cùng một bậc và kiểm tra tài nguyên.
- Với cách làm nhƣ vậy, các node trong cùng một bậc có khả năng cung cấp tài nguyên trong cùng một bậc là tƣơng đƣơng nhau.
- Nhƣ vậy, nếu một node trong bậc không có khả năng cung cấp tài nguyên thì xác suất các node còn lại trong bậc cũng không có khả năng cung cấp tài nguyên là rất cao.
- Ngoài ra luận văn cũng cải tiến bằng cách tích hợp kiểm tra khả năng ánh xạ liên kết nhằm giảm thời gian quay lui và thu đƣợc đƣờng đi có độ dài ngắn nhất.
- Các thuật toán ánh xạ mạng ảo vào mạng vật lý trƣớc đó đều có tỉ lệ đáp ứng thấp, hàm mục tiêu chƣa đạt đƣợc giá trị cao.
- Các nghiên cứu thuật toán ánh xạ mạng ảo hiện tại đều có các nhƣợc điểm nhất định.
- Nghiên cứu thuật toán ánh xạ mạng ảo của Jens Lischka và Holger Karlđƣợc đăng trên tạp chí [7].
- Trong nghiên cứu của Jens Lischka và Holger Karl đã sử dụng thuật toán quay lui để giải quyết bài toán ánh xạ mạng ảo.
- Nhƣợc điểm của thuật toán ánh xạ mạng ảo này là mất nhiều thời gian để thực hiện thuật toán quay lui.
- Trong nghiên cứu [5] do Minlan Yu và các đồng nghiệp phát triển đã cải tiến từ thuật toán [7],

Xem thử không khả dụng, vui lòng xem tại trang nguồn
hoặc xem Tóm tắt