Tài liệu Tìm hiểu về các công cụ phần mềm hệ phân tán đã có, và khảo sát các cơ sở trong việc mô phỏng và đề xuất thiết kế thử nghiệm

  • Số trang: 70 |
  • Loại file: PDF |
  • Lượt xem: 93 |
  • Lượt tải: 0
thanhphoquetoi

Tham gia: 05/11/2015

Mô tả:

LÊ ĐÌNH THỊNH BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI --------------------------------------- Lê Đình Thịnh KỸ THUẬT PHẦN MỀM TÌM HIỂU VỀ CÁC CÔNG CỤ PHẦN MỀM HỆ PHÂN TÁN ĐÃ CÓ, VÀ KHẢO SÁT CÁC CƠ SỞ TRONG VIỆC MÔ PHỎNG VÀ ĐỀ XUẤT THIẾT KẾ THỬ NGHIỆM LUẬN VĂN THẠC SĨ KỸ THUẬT Chuyên ngành Kỹ Thuật Phần Mềm KHÓA 2014B Hà Nội – Năm 2017 BỘ GIÁO DỤC VÀ ĐÀO TẠO TRƯỜNG ĐẠI HỌC BÁCH KHOA HÀ NỘI --------------------------------------Lê Đình Thịnh TÌM HIỂU VỀ CÁC CÔNG CỤ PHẦN MỀM HỆ PHÂN TÁN ĐÃ CÓ, VÀ KHẢO SÁT CÁC CƠ SỞ TRONG VIỆC MÔ PHỎNG VÀ ĐỀ XUẤT THIẾT KẾ THỬ NGHIỆM Chuyên ngành: Kỹ Thuật Phần Mềm 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. PGS. TS. Nguyễn Khanh Văn Hà Nội – Năm 2017 MỤC LỤC MỞ ĐẦU ................................................................................................................ 1 CHƯƠNG 1 – CƠ SỞ LÝ THUYẾT....................................................................... 3 1.1 Mạng liên kết ............................................................................................. 3 1.1.1 Khái niệm mạng liên kết ...................................................................... 3 1.1.2 Các thành phần cơ bản trong mạng liên kết .......................................... 5 1.2 Khái niệm dùng trong đánh giá hiệu năng giải thuật định tuyến .................. 6 1.2.1 Thông lượng ........................................................................................ 7 1.2.2 Độ trễ................................................................................................. 10 1.2.3 Đường kính mạng, độ dài trung bình của đường truyền...................... 12 1.2.4 Các tiêu chí đánh giá hiệu năng khác ................................................. 12 1.2.5 Các tác nhân ảnh hưởng đến đánh giá hiệu năng mạng ...................... 13 1.3 Một số cấu trúc mạng cơ bản .................................................................... 15 1.3.1 Phân loại cấu trúc mạng ..................................................................... 15 1.3.2 Cấu trúc mạng Fat-tree....................................................................... 18 1.3.3 Cấu trúc mạng Jellyfish ..................................................................... 21 1.3.4 Cấu trúc mạng liên kết ngẫu nhiên 2-D .............................................. 23 1.4 Giải thuật định tuyến trên mạng................................................................ 24 1.4.1 Phân loại giải thuật định tuyến ........................................................... 24 1.4.2 Giải thuật định tuyến đường đi ngắn nhất SPR................................... 27 1.4.3 Giải thuật định tuyến Thorup-Zwick (TZ) .......................................... 28 1.4.4 Giải thuật định tuyến BbR ................................................................. 30 CHƯƠNG 2 – PHƯƠNG PHÁP ĐÁNH GIÁ HIỆU NĂNG MẠNG LIÊN KẾT .. 32 2.1 Đánh giá chi phí ....................................................................................... 32 2.2 Đánh giá hiệu năng sử dụng lý thuyết đồ thị ............................................. 34 2.2.1 Thông lượng ...................................................................................... 34 2.2.2 Độ trễ................................................................................................. 34 2.2.3 Đánh giá khả năng chịu lỗi................................................................. 35 2.3 Đánh giá hiệu năng sử dụng công cụ mô phỏng ........................................ 36 2.4 Đánh giá hiệu năng sử dụng nhiều tiêu chí kết hợp ................................... 38 CHƯƠNG 3 – THIẾT KẾ CÔNG CỤ PHẦN MỀM SELASIM ............................ 39 i 3.1 Nguyên lý hoạt động của SelaSim ............................................................ 39 3.2 Sơ đồ cấu trúc của SelaSim ...................................................................... 40 3.3 Phương pháp mô phỏng ............................................................................ 44 3.3.1 Phương pháp chọn tập nút mạng mẫu ................................................ 45 3.3.2 Mô phỏng, đánh giá thông lượng ....................................................... 46 3.3.3 Mô phỏng, đánh giá độ trễ trên mạng ................................................. 48 3.3.4 Đánh giá đường kính mạng và độ dài trung bình của đường truyền .... 49 3.4 So sánh SelaSim và các phần mềm khác................................................... 49 CHƯƠNG 4 – KẾT QUẢ THỰC NGHIỆM ......................................................... 51 4.1 Kết quả thực nghiệm với các kích thước của tập mẫu ............................... 51 4.2 Kết quả thực nghiệm với các giải thuật định tuyến TZ, SPR và BbR ........ 52 4.3 Kết luận .................................................................................................... 54 KẾT LUẬN ........................................................................................................... 55 5.1 Kết quả đạt được ...................................................................................... 55 5.2 Hạn chế và hướng phát triển ..................................................................... 55 TÀI LIỆU THAM KHẢO ..................................................................................... 57 PHỤ LỤC.............................................................................................................. 59 ii LỜI CAM ĐOAN Trước tiên tôi xin chân thành gửi lời cảm ơn và lòng biết ơn sâu sắc tới PGS. TS Nguyễn Khanh Văn – Viện Công nghệ Thông tin – Truyền thông, người đã tận tình hướng dẫn, chỉ bảo tôi trong suốt 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 riê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, bạn bè, những người luôn quan tâm và giúp đỡ tôi trong suốt thời gian 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à chưa từng được ai công bố trong bất kỳ công trình nào khác. iii DANH MỤC CÁC KHÁI NIỆM, KÝ HIỆU, CÁC CHỮ VIẾT TẮT STT Tên tiếng Anh Tên tiếng Việt Ký hiệu Giải nghĩa 1 Bandwidth Băng thông Băng thông 2 Block Bridged Giải thuật định Routing tuyến BbR BbR Giải thuật định tuyến Block Bridged Routing. H Số thiết bị trung gian trên đường truyền tham gia vào quá trình chuyển tiếp gói tin từ nút nguồn đến nút đích. 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. 3 Hop count Số thiết bị trung gian tham gia vào quá trình truyền tin 4 Latency Độ trễ Độ trễ của mạng liên kết. 5 Router Bộ định tuyến Các bộ định tuyến trung gian trong mạng. Giải thuật định Path tuyến đường đi ngắn nhất SPR 6 Shortest Routing 7 Switch Bộ chuyển mạch 8 Thorup-Zwick compact routing Giải thuật định tuyến TZ TZ 9 Throughput Thông lượng Θ 10 Topology Cấu trúc mạng 11 Top-of-rack switch Bộ chuyển mạch ToR iv Giải thuật định tuyến SPR là giải thuật định tuyến tìm ra đường đi ngắn nhất giữa nút nguồn và nút đích. Các bộ chuyển mạch trung gian trong mạng. Giải thuật định Thorup-Zwick. tuyến Thông lượng của mạng liên kết. Cấu trúc hình học không gian của mạng liên kết. ToR Bộ chuyển mạch của một tủ mạng, dùng để kết nối giữa các tủ mạng với nhau. 12 Zero-load latency Độ trễ không tải v Độ trễ của mạng ở trạng thái không tải DANH MỤC CÁC BẢNG Bảng 1.1: Một số mẫu trao đổi thông tin ................................................................ 14 Bảng 2.1: Sự liên hệ giữa kích thước file SimGrid và số nút mạng ........................ 37 Bảng 3.1: So sánh SelaSim và các phần mềm mô phỏng khác ............................... 50 Bảng 4.1a: Kết quả chạy SelaSim với các kích thước k cho tập mẫu...................... 51 Bảng 4.1b: Kết quả chạy SelaSim với các kích thước k cho tập mẫu ..................... 52 vi 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 ........................................................ 3 Hình 1.2: Phân loại mạng liên kết ............................................................................ 5 Hình 1.3a: Đồ thị liên hệ giữa thông lượng và dung lượng thông tin đầu vào ........... 8 Hình 1.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 ....................... 10 Hình 1.5: Một số cấu trúc mạng cơ bản ................................................................. 16 Hình 1.6: Cấu trúc mạng ba tầng ........................................................................... 18 Hình 1.7: Cấu trúc mạng Fat-tree với bốn cụm chuyển mạch ................................. 19 Hình 1.8: Sơ đồ kết nối tại một bộ chuyển mạch ở tầng Edge trong mạng Fat-tree 20 Hình 1.9: Sơ đồ kết nối tại một bộ chuyển mạch ở tầng Core trong mạng Fat-tree . 20 Hình 1.10: Cấu trúc 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à Jellyfish .................................... 22 Hình 1.11c: So sánh cấu trúc mạng Fat-tree và Jellyfish ........................................ 23 Hình 1.12: Kết nối ngẫu nhiên trong mạng GRID-2............................................... 24 Hình 1.13: Sơ đồ mô tả đường truyền có hai thiết bị trung gian tham gia vào quá trình truyền tin ....................................................................................................... 27 Hình 1.14: Giả mã thuật toán TZ ........................................................................... 29 Hình 1.15: Sơ đồ mô tả quá trình định tuyến từ s đến d ......................................... 30 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 ....... 31 Hình 2.1: Sơ đồ minh họa một data center ............................................................. 33 Hình 2.2: Đồ thị mô phỏng một mạng liên kết ....................................................... 35 Hình 2.3: Sơ đồ mạng liên kết với 4 nút và file SimGrid của mạng........................ 37 Hình 3.1: Nguyên lý hoạt động của SelaSim.......................................................... 39 Hình 3.2: Thiết kế của công cụ SelaSim ................................................................ 40 Hình 3.3: Module ITopology ................................................................................. 41 Hình 3.4: File cấu trúc mạng của mạng 2-D random shortcut network ................... 41 Hình 3.5: Module IRouting.................................................................................... 42 vii Hình 3.6: Module IEvaluator ................................................................................. 43 Hình 3.7: Quy trình vận hành SelaSim................................................................... 44 Hình 3.8: Giả mã phương pháp chọn tập mẫu ........................................................ 46 Hình 3.9: Giả mã cách tính thông lượng ................................................................ 47 Hình 4.1 a) Kích thước bảng định tuyế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 TZ và BbR với kích thước từ 1024 đến 4096 ......................................................................................... 53 Hình 4.2: Trung bình chiều dài đường đi và độ trễ của mạng 1024 nút .................. 54 viii MỞ ĐẦU Trong những năm gần đây, việc sử dụng các siêu máy tính, các trung tâm dữ liệu hiện đại nổi lên như một nhu cầu thiết yếu ở nhiều nước trên thế giới để xử lý và lưu trữ dữ liệu phục vụ cho công tác nghiên cứu khoa học, ứng dụng và kinh doanh. Đi kèm với nhu cầu sử dụng mạng liên kết là nhu cầu đánh giá hiệu năng của các mạng liên kết và so sánh chúng với nhau theo một số tiêu chí hiệu năng được định nghĩa trước. Hiệu năng của mạng liên kết có thể được đánh giá một cách chính xác khi mạng liên kết được đưa vào sử dụng. Tuy nhiên, do chi phí lắp đặt một trung tâm dữ liệu tương đối lớn, việc đánh giá chính xác hiệu năng của mạng gần như không khả thi. Chính vì vậy, các lý thuyết đồ thị và các công cụ mô phỏng đã được sử dụng một cách rộng rãi trong các nghiên cứu đánh giá hiệu năng của mạng liên kết. Với các mạng liên kết kích thước lớn, việc đánh giá hiệu năng mạng bằng lý thuyết là tương đối khó khăn do số lượng tham số cần đánh giá rất lớn. Trong những trường hợp như vậy, việc sử dụng các công cụ mô phỏng được coi như một giải pháp khả dĩ hơn. Một số công cụ mô phỏng có thể kể đến như SimGrid, NS2, OMNET++, OpNet v.v. Các công cụ mô phỏng này có khả năng tính toán và mô phỏng tương đối mạnh mẽ cũng như chính xác. Chúng hỗ trợ mô phỏng các hệ thống tính toán lớn như hệ thống tính toán song song, tính toán lưới, tính toán đám mây, cũng như tính toán hiệu năng cao v.v. Mặc dù vậy, các công cụ mô phỏng này đều có những hạn chế nhất định và trong một số trường hợp không đáp ứng được một yêu cầu đánh giá hiệu năng của một bài toán cụ thể. Có thể lấy ví dụ như công cụ mô phỏng SimGrid không hỗ trợ tính toán cho thuật toán định tuyến mà có nhiều hơn một đường đi giữa hai nút bất kỳ, sự hỗ trợ và tốc độ tính toán của công cụ mô phỏng SimGrid đối với các mạng siêu máy tính có hàng chục nghìn, trăm nghìn nút cũng rất hạn chế. Chính vì vậy, để khắc phục nhược điểm đó và để phục vụ mục đích nghiên cứu chuyên biệt, nhóm nghiên cứu của phòng SEDIC lab chúng tôi dưới sự hướng dẫn của thầy Nguyễn Khanh Văn đã phát triển một hệ thống mô phỏng riêng để phục vụ nhu cầu đánh giá 1 hiệu năng của mạng siêu liên kết với hàng chục nghìn, trăm nghìn nút. Trong quá trình làm việc tại phòng SEDIC lab, tác giả đã tham gia vào các buổi trao đổi, kiểm chứng kết quả chạy phần mềm mô phỏng và tiến hành xây dựng các bảng định tuyến cho các thuật toán được phòng SEDIC lab nghiên cứu. Trong quá trình làm việc này, tác giả nhận thấy đề tài luận văn đã đăng ký với nội dung “Tìm hiểu về các công cụ phần mềm hệ phân tán đã có, và khảo sát các cơ sở trong việc mô phỏng và đề xuất thiết kế thử nghiệm” vượt quả khả năng và thời gian cho phép. Thêm vào đó phần mềm mô phỏng được sử dụng tại phòng SEDIC lab được phát triển và đóng góp bởi nhiều người, bởi vậy việc hệ thống hóa các tài liệu, các phương pháp đo đạc được sử dụng cũng như việc kiểm chứng phương pháp lấy tập các nút mạng mẫu là chưa được thực hiện. Từ các nhu cầu thực tế đó, dưới sự hướng dẫn của thầy hướng dẫn, tác giả đã quyết định nghiên cứu và hoàn thành một phạm vi nhỏ của đề tài đã đăng ký ban đầu. Chính vì vậy trong luận văn này, tác giả sẽ tập trung vào việc trình bày và đề xuất phương pháp xây dựng công cụ phần mềm đánh giá và mô phỏng cho thuật toán định tuyến trên mạng liên kết kích thước lớn với mong muốn sẽ tổng quát hóa phần mềm mô phỏng hiện tại của SEDIC lab, trình bày cách thức các phương pháp đo đạc đang hoạt động thế nào và tiến hành phát biểu cũng như kiểm chứng phương pháp lấy tập các nút mẫu. 2 CHƯƠNG 1 – CƠ SỞ LÝ THUYẾT Trong mục này, người viết sẽ trình bày khái niệm mạng liên kết, một số tiêu chí được sử dụng trong đánh giá hiệu năng mạng liên kết như thông lượng, độ trễ. Người viết cũng trình bày một số cấu trúc mạng cơ bản cũng như giải thuật định tuyến trên mạng. Cấu trúc mạng và giải thuật định tuyến có liên quan đến hướng nghiên cứu của luận văn này sẽ được trình bày trong các mục 1.3 và 1.4. 1.1 Mạng liên kết Để có thể đánh giá được hiệu năng của mạng liên kết, chúng ta cần hiểu và định nghĩa được khái niệm mạng liên kết là gì, có những thành phần chủ yếu nào sẽ ảnh hưởng đến sự đánh giá hiệu năng của mạng. Mục 1.1.1 sẽ giải thích khái niệm thế nào là mạng liên kết, các thành phần chủ yếu của mạng sẽ được trình bày trong mục 1.1.2. 1.1.1 Khái niệm mạng liên kết Mạng liên kết (Interconnection Network) được hiểu một cách tổng quát là một hệ thống có thể lập trình được, và được sử dụng để vận chuyển dữ liệu giữa các thiết bị đầu cuối [1]. Hình 1.1: Mô hình một mạng liên kết đơn giản [1] Hình 1.1 mô tả cấu trúc mạng của một mạng liên kết điển hình, trong đó các thiết bị đầu cuối (kí hiệu từ TB1 đến TB6) kết nối với mạng liên kết. Các mũi tên 3 biểu diễn kết nối có hai chiều thể hiện khả năng vận chuyển dữ liệu vào và ra mạng liên kết. Khi thiết bị đầu cuối TB1 muốn trao đổi dữ liệu với TB5, TB1 gửi một gói tin chứa dữ liệu cần trao đổi đến mạng liên kết. Mạng liên kết sẽ thực hiện chuyển tiếp gói tin này đến TB5. Tính lập trình được của mạng liên kết được thể hiện ở việc mạng liên kết có thể tạo ra các kết nối khác nhau giữa các thiết bị đầu cuối ở các thời điểm khác nhau theo thời gian nhằm phục vụ nhu cầu truyền tin trong mạng. Tại một thời điểm, mạng liên kết trong Hình 1.1 có thể chuyển tiếp gói tin từ TB3 đến TB5, ngay sau đó cũng có thể sử dụng lại các tài nguyên này để chuyển tiếp gói tin từ TB3 đến TB1. Các hệ thống thỏa mãn định nghĩa về mạng liên kết được nêu lên ở trên được phân loại thành các loại mạng liên kết khác nhau tùy thuộc vào số lượng thiết bị kết nối và khoảng cách giữa các thiết bị. Theo [2] có bốn loại mạng liên kết chính được phân biệt như sau: • On-chip networks (OCN): Còn được nhắc tới với thuật ngữ network-onchip (NoC), OCNs được sử dụng để kết nối các đơn vị chức năng vi kiến trúc, các thanh ghi (register), bộ lưu trữ trung gian (caches), các bộ vi xử lý (processor) trong các con chip hoặc module đa chip. OCNs hỗ trợ các kết nối giữa vài chục thiết bị đặt trong các vi mạch với khoảng cách tối đa khoảng vài centimet. • System/storage area networks (SAN): Là mạng liên kết được sử dụng để kết nối các bộ vi xử lý liên kết (interprocessor) và các bộ nhớ (processor-memory) trong các hệ thống đa nhân (multiprocessor) và hệ thống đa máy tính (multicomputer). Mạng liên kết này cũng được sử dụng để kết nối các bộ lưu trữ và thiết bị đọc/ghi trong các môi trường máy chủ và trung tâm dữ liệu. Số lượng thiết bị được kết nối trong SAN có thể lên tới hàng nghìn thiết bị khác nhau phân bố trong khoảng cách từ vài chục đến vài trăm mét. • Local area networks (LAN): Là mạng liên kết được sử dụng để kết nối hệ thống máy tính cá nhân trong một phòng, một tòa nhà hoặc một khu vực. Các mạng LAN có thể kết nối hàng trăm hoặc hàng ngàn thiết bị nếu sử dụng thêm 4 các cầu nối (bridges). Khoảng cách kết nối tối đa trong mạng LAN có thể dao động trong phạm vi vài kilomet đến vài chục kilomet. • Wide area networks (WAN): Là mạng liên kết được sử dụng để kết nối các hệ thống máy tính phân bố phân tán trên toàn thế giới. WANs có thể kết nối hàng triệu máy tính trên một khoảng cách vài ngàn kilomet. Bốn loại mạng liên kết đã trình bày ở trên có thể được hiển thị một cách trực quan như trong Hình 1.2 với trục tung (trục đứng) thể hiện khoảng cách lớn nhất giữa các thiết bị và trục hoành (trục ngang) thể hiện số lượng thiết bị trong mạng liên kết. Hình 1.2: Phân loại mạng liên kết [2] 1.1.2 Các thành phần cơ bản trong mạng liên kết Để đáp ứng các yêu cầu hiệu năng của một hệ thống cụ thể, các yếu tố cấu trúc mạng, giải thuật định tuyến và giải thuật điều khiển luồng được thiết kế, xây dựng dựa trên sự cân nhắc đến các giới hạn, rành buộc kỹ thuật của mạng. Một điểm chính quyết định đến sự hiệu quả của mạng liên kết là việc chia sẻ các kết nối trong mạng, chính vì vậy, thay vì liên kết các thiết bị đầu cuối với nhau theo từng đôi một, các thiết bị đầu cuối sẽ được kết nối thông qua các bộ chuyển mạch và các kênh truyền chung. Các bộ chuyển mạch và các thiết bị đầu cuối được gọi chung là các nút mạng, cách thức hay mẫu thiết kế, cấu trúc hình học mà các nút mạng được liên kết với nhau 5 được gọi là cấu trúc mạng. Các cấu trúc mạng lần lượt được chia ra thành cấu trúc mạng đối xứng hoặc bất đối xứng. Các gói tin được truyền giữa các nút bằng cách di chuyển qua các kênh truyền hoặc các nút mạng dùng chung. Thông thường, với một cấu trúc mạng bất kỳ, một gói tin có thể được truyền đi theo nhiều con đường khác nhau từ nút nguồn đến nút đích. Định tuyến là quá trình lựa chọn một đường truyền trong số toàn bộ các đường truyền mà một gói tin có thể đi từ nguồn đến đích. Thuật toán định tuyến có thể được chia ra dựa trên vị trí thực hiện việc định tuyến thành các thuật toán định tuyến tại nguồn hoặc thuật toán định tuyến tại đích. Trong thuật toán định tuyến tại nguồn, nút nguồn sẽ xác định đường truyền mà một gói tin sẽ phải đi qua từ nút nguồn đến nút đích. Ngược lại, trong thuật toán định tuyến tại đích, nút nguồn sẽ chỉ gửi đi thông tin của nút đích mà một gói tin cần đến, việc xác định đường đi cụ thể của gói tin sẽ được thực hiện tại các bộ định tuyến trung gian. Thuật toán định tuyến cũng có thể được chia ra dựa trên thời điểm thực hiện định tuyến thành các thuật toán định tuyến tĩnh (static) hoặc động (dynamic). Trong thuật toán định tuyến tĩnh, đường đi của một gói tin cho một cặp nút nguồn – đích là cố định và được xác định khi khởi tạo cấu trúc mạng. Ngược lại trong thuật toán định tuyến động, đường đi của một gói tin sẽ chỉ được xác định khi cấu trúc mạng được đưa vào sử dụng trong thực tế. Điều khiển luồng là quá trình ra lệnh, lựa chọn gói tin nào được quyền truy cập vào một tài nguyên cụ thể tại một thời điểm trong mạng. Điều khiển luồng được thực hiện liên tục trong toàn bộ quá trình vận hành mạng và đóng vai trò quan trọng trong việc chuyển tiếp các gói tin với độ trễ nhỏ nhất, đảm bảo các tài nguyên không bị sử dụng quá tải, hoặc không được sử dụng trong thời gian dài. 1.2 Khái niệm dùng trong đánh giá hiệu năng giải thuật định tuyến Phụ thuộc vào nhu cầu và mục đích cụ thể của việc đánh giá, hai hay nhiều mạng liên kết bất kỳ và giải thuật định tuyến trên mạng liên kết sẽ được đánh giá và so sánh dựa trên một hoặc nhiều tiêu chí chung. Trong mục này, người viết sẽ trình 6 bày một số tiêu chí đánh giá hiệu năng chính như thông lượng, độ trễ và một số các tiêu chí khác ít sử dụng hơn. Một số tác nhân có ảnh hưởng đến hiệu năng mạng và đánh giá hiệu năng mạng cũng được mô tả trong phần cuối của mục này. 1.2.1 Thông lượng Thông lượng của một mạng được định nghĩa bằng lượng thông tin mà mạng có thể truyền được trong một đơn vị thời gian. Thông lượng thường được đo bằng số lượng bit được truyền đi trong một giây (bits per second – bps). Thông lượng lý tưởng của mạng được định nghĩa là thông lượng của mạng khi mẫu trao đổi thông tin (traffic pattern) trong mạng, thuật toán định tuyến và giải thuật điều khiển luồng (flow control) trong mạng đạt điều kiện lý tưởng. Điều này đồng nghĩa với việc các đường truyền tương đương trên mạng sẽ chịu một lượng tải bằng nhau, và các đường truyền sẽ được sử dụng với hiệu xuất cao nhất. Tuy nhiên, do thông lượng thực tế của mạng bị ảnh hưởng bởi nhiều yếu tố như cấu trúc mạng, thuật toán định tuyến v.v. thông lượng thực tế của mạng sẽ luôn nhỏ hơn thông lượng lý tưởng. Thông lượng lớn nhất của mạng đạt được khi các đường truyền trong mạng trở lên bão hòa. Khi các đường truyền trong mạng chưa bão hòa, thông lượng của mạng sẽ tăng dần lên khi dung lượng thông tin đầu vào (offered traffic) – lượng thông tin được sinh ra bởi các nút nguồn – tăng lên. Khi đạt đến điểm bão hòa, thông lượng sẽ không tăng lên mặc dù lượng thông tin đầu vào tăng lên như được mô tả trong Hình 1.3a. Trong trường hợp mạng ổn định, thông lượng của mạng sẽ gần như không thay đổi sau khi đạt đến điểm bão hòa điều này được thể hiện rõ trong Hình 1.3a khi giá trị của thông lượng đi ngang sau khi mạng đạt đến trạng thái bão hòa. Tuy nhiên trong thực tế, rất nhiều mạng không ổn định và thông lượng của chúng thường đi xuống sau khi đạt đến trạng thái bão hòa như mô tả trong Hình 1.3b. Nguyên nhân xảy ra tình trạng sụt giảm về thông lượng là do khi mạng đạt đến trạng thái bão hòa, các gói tin phải cạnh tranh về tài nguyên trong mạng, và một số gói tin bắt đầu bị mất. 7 Hình 1.3a: Đồ thị liên hệ giữa thông lượng và dung lượng thông tin đầu vào [1] Hình 1.3b: Đồ thị liên hệ giữa thông lượng và dung lượng thông tin đầu vào [1] 8 Để đơn giản hóa việc tính toán thông lượng, thông thường băng thông của các kênh truyền trên mạng được giả định bằng nhau và bằng b. Lượng tải trên một kênh truyền được tính theo công thức 1.1. = ă ă ℎô ℎô ê ầ ừ ê ℎ ề ủ đầ à 1.1 Đây chính là lượng thông tin sẽ cần truyền qua kênh truyền nếu mỗi đầu vào (input) gửi một đơn vị thông tin vào mạng. Lượng tải lớn nhất của mạng "#$ được tính bằng lượng tải lớn nhất trên toàn bộ các kênh truyền. Khi mạng trở lên bão hòa, lượng thông tin đầu vào sẽ bằng thông lượng của mạng, và lượng tải yêu cầu trên kênh truyền bị bão hòa (bottleneck channel) sẽ bằng băng thông của kênh truyền. Vì vậy thông lượng lý tưởng của mạng có thể được tính theo công thức 1.2 và 1.3 trong đó Θ&ý (ưở+, là thông lượng lý tưởng của mạng. "#$ = Θ&ý (ưở+, Θ&ý (ưở+, = "#$ 1.2 1.3 Trong điều kiện lý tưởng, một nửa gói tin trong mạng sẽ phải di chuyển qua lớp cắt mạng (bisection), và mỗi kênh truyền trong lớp cắt mạng có lượng tải bằng nhau. Vì vậy ta có công thức 1.4 và 1.5. "#$ ≥ Θ&ý (ưở+, ≤ 0 = 1 223 2 23 220 = 1 1 1.4 1.5 Trong đó BC (C viết hoa) là số lượng kênh truyền trong một lớp cắt mạng, BB là tổng băng thông của lớp cắt mạng và N là tổng số nút mạng. 9 1.2.2 Độ trễ Độ trễ của mạng được định nghĩa là khoảng thời gian cần thiết để một gói tin đi từ nút nguồn đến nút đích. Khoảng thời gian này được tính từ lúc thành phần dữ liệu đầu tiên của gói tin bắt đầu được gửi vào mạng đến khi thành phần dữ liệu cuối cùng của gói tin đến đích. Độ trễ của mạng ở trạng thái không tải là độ trễ có thể đạt được trên mạng khi các gói tin không phải cạnh tranh về tài nguyên trên mạng. Đây chính là độ trễ lý tưởng và được tính bằng tổng thời gian cần thiết để một gói tin được đẩy vào mạng một cách toàn bộ cộng với thời gian để thành phần dữ liệu đầu tiên của gói tin được truyền trên mạng. Hình 1.4: Đồ thị liên hệ giữa độ trễ và lưu lượng thông tin đầu vào [1] Để đánh giá hiệu năng của mạng, trong một số trường hợp, độ trễ của mạng được biểu diễn như một hàm phương trình của lưu lượng thông tin đầu vào như trong Hình 1.4. Do ảnh hưởng bởi cấu trúc mạng, giải thuật định tuyến và điều khiển luồng trên mạng, độ trễ thực tế ở trạng thái không tải T0 sẽ cao hơn độ trễ ở trạng thái không tải lý tưởng 7#8, 9 + ;⁄ và 7"=+ 9 + ;⁄ với Havg, Hmin, L, b lần lượt là số lượng 10
- Xem thêm -