BỘ GIÁO DỤC VẢ ĐÀO TẠO ˆ TRƯỜNG DẠI HỌC BÁCH KHOA IẢ NỘI TINHITLTINIG T1 1ê Đình Thịnh TÌM HIẾU VÉ CÁC CÔNG CU PHAN MEM HE PHAN TAN BA CÓ, VẢ KHẨU SÁT CÁC CƠ SỞ TRÔNG VIỆC MÔ PHÓNG VẢ ĐÊ XUẮT THIẾT KÉ THỨ NGHIỆM WN NY¥Hd LYOHL 44 LUẬN VĂN THẠC 8Ï KỸ THUAL Chuyên ngành Kỹ Thuật Phân Méin ‘dp ioe lc VỌHM Ha Noi —Nam 2017 _BQ GIAO DUC YA DAO TAO | TRUONG DẠI HỘC BÁCH KHOA HÀ NỘI Lê Dình Thịnh TÌM LIỂU VE CAC CONG CL PLAN MEM LAN ‘TAN DA CO, VA A NGVIEC MO PHONG VA DE XUAT 'THIẾT KẾ THỦ NGHUỆM. Chuyên ngành: Kỹ Thuật Phân Mm LUẬN VĂN THẠC SĨ KỸ THUẬT Chuyên ngành Kỹ Thuật Phân Mềm NGƯỜI HƯỚNG DẪN KHOA HỌC 1. Nguyễn Khanh Văn lảNội Năm 2017 CHUONG | —CO SG LY THUYET. bo 11 Mạng liên kết 1.1 Khải mệm mạng liễn kết.L2 __ Cáo thành phần cơ bảntrong mạng liên kết.2 Khải niệm đùng trong đành giá hiệu năng giải thuật định tuyên.
Đường kinhtrạng, độ dài trung bình của đường truyền 12 1. Cáo tiêu chí đánh giá hiệu năng khác.8 | Cac tae whan ảnh hưởng đến đánh giá hiệu năng trạng, 13 13 Một số câu trúc mạng co ban Ti 15 143.1 Phân loại cấu trủc mạng - 15 1.2 Cau tric mang Fat-tree.33 Cau tric mang Jellyfish 21 1. Câu trúc mạng liên kếtngẫu nhiên 2-].4 Giải thuật định tuyển trên mạng. 1⁄41 Phin loai giải thuật định tuyến.2 Giải thuật định tuyển đường đi ngắn nhất SPR.
Giải thuật dinh tuyén Thorup-Zwick (TZ).4 Giải tật địhtuyển BÙR. CHƯƠNG2 - PHƯƠNG PHÁP ĐẢNH GIÁ HIỆU NÃ2 G MẠNGI 2.1 Đánh giá chỉ phí.2 Đảnh giá liệu năng sử dụng lý thuyết đỗ thủ se 34 221 Thônglượng.23 Danh gid kha ning chin l6i - 35 1.3 _ Dánh giả hiệu năng sử dựng công cụ mô phỏng.4 Dánh giá hiệu năng sử dựng nhiều tiêu chí kết hợp CHUONG3 THIET KE CONG CU PHAN MEM SELASIM Hìmh 3.7; Quy tinh van hanh SetaSina 44 Hình 3.8: Giả mã phương pháp chọn tập ruấu.9: Giả md cach tính thông lượng.1 a) Kích thước bằng định myén của TZ, BbR, SPR với nhiễu kích thước mạng khác nhau b) So sảnh kích thước bảng định tuyển của 14 và BbR với kích thước từ 1024 đền 4096.2: Trưng bình chiều dài đường đi và độ trễ của mạng 1024 nút. 54 DANH MỤC CÁC BẰNG BăngL1: Một số mẫu trao đổi thêng tin.1: Su lién hệ giữa kích thước ñle SimGrid và số nút mạng.1: So sánh SelaSim và các phần mềm mồ phỏng khác.14: Kết quả chạy SelaSim với các kích thước k cho tập mãn.1b: Két quả chạy SelaSim với các kích thước k cho tap mau 5 vi DANH MỤC CAC KHAINIEM, KY HIEU, CAC CHU’ VIET TAT STT|Téntiéng Anh | Téntiéng Viet | Ky higu | Giải nghĩa 1 | Bandwidth Bang thong Bang thong , | Block Bridged | Giéithnatdinh) BbR | Giải thuật dink tuyén Block “| Routing tuyén BbR Bridged Routing. Số thiết bị| H | Số thiết bị trung gian trên trung gian đường truyền tham gia vào tham gia vào quả trìnhchuyển tiếp gói tin quá.
trình từ nút nguôn đến nút đích 3 | Hop count truyền tin Bộ chuyên mạch được tính là một thiết bị trung gian, tuy nhiên kênh truyền không được tính là một thiết bị trung gian 4 |Lateney Độ tre Đô tr của mạng liên kết. | Raa Bồ định tuyến Các bộ định tuyển trung gian trong mang Giai thuat dinh | SPR | Giai thuat dinh tuyén SPR la 6 Shortest Path | tuyen đường giai thuat dinh tuyen tim ra Routing di ngan nhat đường đi ngăn nhật giữa nút nguon va mut dich. 7 | switch Bộ chuyển Các bộ chuyên mạch trung mạch gian trong mạng _ | Thorup-Zwiek TZ |Giả thuat đỉnh tuyển compact routing Thorup-Zwick. a Thông lượng của mạng liên 9 | Throughput "Thông lượng 9 Kết 10 | Topology Cau4 tric mang Cau chatnic mang sian hinh tenhoclếtkhông copracke (BO chuyển| ToR | Bộ chuyển mạch của một tủ li |switch Topofrck | nach ToR mang,cae đùng đểSi kết nỗi giữa các tủ mạng với nhau.
DANH MỤC CAC KHAINIEM, KY HIEU, CAC CHU’ VIET TAT STT|Téntiéng Anh | Téntiéng Viet | Ky higu | Giải nghĩa 1 | Bandwidth Bang thong Bang thong , | Block Bridged | Giéithnatdinh) BbR | Giải thuật dink tuyén Block “| Routing tuyén BbR Bridged Routing. Số thiết bị| H | Số thiết bị trung gian trên trung gian đường truyền tham gia vào tham gia vào quả trìnhchuyển tiếp gói tin quá. trình từ nút nguôn đến nút đích 3 | Hop count truyền tin Bộ chuyên mạch được tính là một thiết bị trung gian, tuy nhiên kênh truyền không được tính là một thiết bị trung gian 4 |Lateney Độ tre Đô tr của mạng liên kết. | Raa Bồ định tuyến Các bộ định tuyển trung gian trong mang Giai thuat dinh | SPR | Giai thuat dinh tuyén SPR la 6 Shortest Path | tuyen đường giai thuat dinh tuyen tim ra Routing di ngan nhat đường đi ngăn nhật giữa nút nguon va mut dich.
7 | switch Bộ chuyển Các bộ chuyên mạch trung mạch gian trong mạng _ | Thorup-Zwiek TZ |Giả thuat đỉnh tuyển compact routing Thorup-Zwick. a Thông lượng của mạng liên 9 | Throughput "Thông lượng 9 Kết 10 | Topology Cau4 tric mang Cau chatnic mang sian hinh tenhoclếtkhông copracke (BO chuyển| ToR | Bộ chuyển mạch của một tủ li |switch Topofrck | nach ToR mang,cae đùng đểSi kết nỗi giữa các tủ mạng với nhau. DANH MỤC CÁC HÌNH VẼ, ĐỎ THỊ Hình 1.1: Mõ hình một mạng liên kết đơn giản.2: Phân loại mạng liên kết.3a: Đô thị liên hệ giữa thông lượng va dung lượng thông tin đầu vào.3b: Đỏ thị liên hệ giữa thông lượng vả dung lượng thông tin đầu vào 8 Hình 1.4: Đồ thị liên hệ giữa độ trễ và lưu lượng thông tin đầu vào.5: Một số câu trúc mạng cơ bân.6: Cấu trúc mạng ba tẳng.7: Cầu trúc mạng Fat-tree với bổn cụm chuyển mạch.8: Sơ đỏ kết oi tại một bộ chuyển mạch 6 tang Edge trong mang Fat-tree 20 Hình 1.9: Sơ đồ kết ¡ tại một bộ chuyển mach ở tầng Core trong mang Fat-tree.10: Cau trite mạng Fat-tree với k= 6 21 Hình 1.11a,b: So sánh cầu trúc mạng Fat-tree và Jellyfsh.11c: So sánh cầu trúc mang Fat-tree va Jellyfish.12: Kết nỗi ngẫu nhiên trong mạng GRID-2.13: Sơ đồ mô tả đường truyền có hai thiết bị trung gian tham gia vào qua trình truyền tin i Hinh 1.14: Gia ma thuat toan TZ 29 Hình 1.15: Sơ đồ mô tả quá trình định tuyên từ s đến d Hình 1.16: Định tuyển nội vùng và liên vùng trong mạng liên kết ngẫu nhiên.1: So 46 minh hoa mét data center 33 Hình 2.2: Đồ thị mô phỏng một mạng liên kết.3: Sơ đồ mạng liền kết với 4 nút và ñle SimGridcủa mạng.1: Nguyên lý hoạt động của SelaSim.2: Thiet ké etia cong cu SelaSim .c0:scsssssssessrssensensseerseeerineseeensee AO, Hinh 3.4: Eile câu trúc mạng của mạng 2-D random shortcut network. cesses Al Hình 3.7; Quy tinh van hanh SetaSina 44 Hình 3.8: Giả mã phương pháp chọn tập ruấu.9: Giả md cach tính thông lượng.1 a) Kích thước bằng định myén của TZ, BbR, SPR với nhiễu kích thước mạng khác nhau b) So sảnh kích thước bảng định tuyển của 14 và BbR với kích thước từ 1024 đền 4096.2: Trưng bình chiều dài đường đi và độ trễ của mạng 1024 nút.1 Nguyén ly host dong cia SckaSim _.2 Sơ đồ cáu trúc của 8slaSi - 40 3.3 Phương pháp mô phông - se 44 3.
Phương pháp chọn tập rút mạng mẫu.2 Mô phỏng, đánh giá thòng lượng se 46 3. Mô phỏng, đánh giá độ trễ trên mạng. Dánh giá đường kính mạng và độ đài trưng bình của đường truyền.4 So sánh SelaSim và các phan mém khác. CHUONG4 KET QUATHUC NGHIEM.
41 Kết quả thực nghiện với các kich thước của tập mẫu. 42 Kết quảithe nghiệm với các giải thuật định tuyén TZ, SPR va BUR KÉT LUẬN Thuê $5 $1 KếI qua dat được $5 5.2 Taw ché va hướng phát hiển - - $5 TẢI TIẾU THAM KITÃO _ - ST PUL LUC. - sy Zero-load Độ trễ không Lô tế của mạng ở trang thái latency tải không tải DANH MỤC CÁC HÌNH VẼ, ĐỎ THỊ Hình 1.1: Mõ hình một mạng liên kết đơn giản.2: Phân loại mạng liên kết.3a: Đô thị liên hệ giữa thông lượng va dung lượng thông tin đầu vào.3b: Đỏ thị liên hệ giữa thông lượng vả dung lượng thông tin đầu vào 8 Hình 1.4: Đồ thị liên hệ giữa độ trễ và lưu lượng thông tin đầu vào.5: Một số câu trúc mạng cơ bân.6: Cấu trúc mạng ba tẳng.7: Cầu trúc mạng Fat-tree với bổn cụm chuyển mạch.8: Sơ đỏ kết oi tại một bộ chuyển mạch 6 tang Edge trong mang Fat-tree 20 Hình 1.9: Sơ đồ kết ¡ tại một bộ chuyển mach ở tầng Core trong mang Fat-tree.10: Cau trite mạng Fat-tree với k= 6 21 Hình 1.11a,b: So sánh cầu trúc mạng Fat-tree và Jellyfsh.11c: So sánh cầu trúc mang Fat-tree va Jellyfish.12: Kết nỗi ngẫu nhiên trong mạng GRID-2.13: Sơ đồ mô tả đường truyền có hai thiết bị trung gian tham gia vào qua trình truyền tin i Hinh 1.14: Gia ma thuat toan TZ 29 Hình 1.15: Sơ đồ mô tả quá trình định tuyên từ s đến d Hình 1.16: Định tuyển nội vùng và liên vùng trong mạng liên kết ngẫu nhiên.1: So 46 minh hoa mét data center 33 Hình 2.2: Đồ thị mô phỏng một mạng liên kết.3: Sơ đồ mạng liền kết với 4 nút và ñle SimGridcủa mạng.1: Nguyên lý hoạt động của SelaSim.2: Thiet ké etia cong cu SelaSim .c0:scsssssssessrssensensseerseeerineseeensee AO, Hinh 3.4: Eile câu trúc mạng của mạng 2-D random shortcut network. cesses Al Hình 3.
4 LỠI CAM ĐOAN “Trước tiền tôi xin chân thành gín lời caro em va tong bichon sau sie ti PGS. “TS Nguyễn Khanh Văn — Viện Công nghệ Thông lin — Truyền thông, người đã tận tình hưởng dẫn, chỉ bảo tôi trong suối quá trình hoàn thiện luận văn. Đồng thời tôi cũng xin bày tỏ lòng biết ơn các thảy cô giáo trong Viện Công nghệ Thông tin Truyền thông nói rêng và Đại học Bách Khoa Hà Nội nói chung đã chỉ dạy, cung cấp những kiển thức quý báu cho tôi trong suốt quả trình học tập và nghiên cứu tại trường. Tôi xin gửi lời cảm ơn sâu sắc tới gia đình, ban bẻ, những người liôn quan tâm và giúp đỡ tôi trơng suốt thời gi học tập và hoần thành luận vấn, 'Tôi cam đoan đây là công trình nghiên cứu của riêng tôi.
Các số liêu, kết quả trong luận văn là trung thưc và chura từng được ai công bổ trong bắt kỳ công trinh nào khác.7; Quy tinh van hanh SetaSina 44 Hình 3.8: Giả mã phương pháp chọn tập ruấu.9: Giả md cach tính thông lượng.1 a) Kích thước bằng định myén của TZ, BbR, SPR với nhiễu kích thước mạng khác nhau b) So sảnh kích thước bảng định tuyển của 14 và BbR với kích thước từ 1024 đền 4096.2: Trưng bình chiều dài đường đi và độ trễ của mạng 1024 nút.