MỞ ĐẦU 1. Tổng quan Mô phỏng là phương pháp không thể thiếu để đặc tả, thiết kế và phân tích mạng máy tính và mạng truyền thông. Kỹ thuật này được sử dụng ở nhiều cấp độ từ nghiên cứu phần cứng đến mạng máy tính. Tuy nhiên, để những kết quả thu thập được dự báo chinh xác đáp ứng của một hệ thống thực, tất cả các tác động liên quan phải được cung cấp đầy đủ trong mô hình mô phỏng.
Tác vụ này luôn là một thách thức lớn vì rất khó có thể mô hình hóa và mô phỏng nhiều mức khác nhau một cách độc lập. Ngoài ra, việc tối ưu hóa hệ thống ở mức cao luôn làm cho các cấp độ của hệ thống phụ thuộc lẫn nhau. Để có thể nhận được tất cả kết quả thống kê có liên quan và phủ hết tất cả các trường hợp – thời gian mô phỏng phải đủ dài. Tuy nhiên, để tránh kéo dài thời gian mô phỏng thậm chí trên các máy tính mạnh, việc mô hình hóa không chỉ phải hợp lý mà còn cần phải hiệu quả.
Tìm kiếm một cách thức đúng đắn để kết hợp các mô hình mô phỏng của nhiều tầng là vấn đề chinh để giải quyết yêu cầu trên. Việc sử dụng các hệ thống xử lý song song đã cho phép thực hiện các mô phỏng đồng thời để đạt độ chinh xác cao tuy nhiên, thời gian mô phỏng hiện nay vẫn chưa đủ nhanh cho các mô phỏng phức tạp. Việc trừu tượng hóa các ảnh hưởng từ các tầng khác và việc mô hình hóa một cách hiệu quả là nhân tố chính để đạt tốc độ mô phỏng cao, tuy nhiên cần lưu ý thu thập đủ tất cả các dữ liệu liên quan để cung cấp cho hệ thống mô phỏng. Chính vì những lý do trên, các nhà nghiên cứu và nhà khoa học cần hiểu rõ các khái niệm mô hình hóa và mô phỏng áp dụng cho các tầng của một hệ thống mạng.
Kết quả của đề tài có thể làm tài liệu tham khảo cho các nghiên cứu viên thực hiện các nghiên cứu lý thuyết trên hệ thống mạng hoặc làm tài liệu tham khảo cho nghiên cứu sinh chuyên ngành hệ thống mạng. Đối tượng và phạm vi nghiên cứu Đối tượng nghiên cứu Tìm hiều NS và mô phỏng mạng máy tính 7 Luan van Đề tài NCKH cấp trường T2014-156 Lý thuyết mô phỏng biến cố rời rạc (Discrete-event simulation) ns-3 Phạm vi nghiên cứu Hệ thống phần mềm ns-3 Thư viện mô hình mạng (Network library model) Viết script mô phỏng trong ns-3 bằng C++ và Python Phân tích kết quả mô phỏng bằng tcpdump, wireshark hoặc các công cụ trên linux 1. Giới hạn và phạm vi đề tài Thư viện mô hình và các lớp đối tượng trợ giúp (Helper Objects) trong ns-3 Mô phỏng các sơ đồ mạng đơn giản: Point-To-Point link, mạng Ethernet (CSMA/CD), mạng không dây Phân tích kết quả từ PCAP trace file bằng tcpdump Tìm hiều NS và mô phỏng mạng máy tính 8 Luan van Đề tài NCKH cấp trường T2014-156 Chương 2: TỔNG QUAN VỀ MÔ PHỎNG Về mặt tổng quan có 3 kỹ thuật để đánh giá đáp ứng của một hệ thống, đó là: Phân tích toán học, đo lường và mô phỏng bằng máy tính. Tất cả các Phương pháp đều có ưu nhược điểm riêng.
Một câu hỏi lớn thường được đặt ra trong đánh giá hệ thống đó là nên thực hiện trên hệ thống thực hay trên một mô hình. Trong mô phỏng trên máy tính, một tiến trình hoặc một hệ thống được bắt chước hoặc hoạt động phỏng theo hệ thống thực trong một khoảng thời gian. Trong thực tế mô phỏng máy tính được ứng dụng tronng nhiều trường hợp như mô phỏng biến cố rời rạc (Discrete-event simulation), mô phỏng liên tục (continuous simulation), mô phỏng Monte Carlo … Trong lĩnh vực mạng máy tính, kỹ thuật mô phỏng chủ đạo là mô phỏng biến cố rời rạc. Đặc điểm chính của loại mô phỏng này là trạng thái của mô hình chỉ có thể thay đổi ở những thời điểm xác định còn được gọi là các sự kiện.
Cho đến hiện nay, mô phỏng biến cố rời rạc được ứng dụng nghiên cứu trên tất cả các tầng của mạng máy tính, từ các vấn đề về xử lý tín hiệu ở tầng vật lý, các vấn đề về truy xuất môi trường truyền ở tầng liên kết dữ liệu, định tuyến ở tầng network, vấn đề về giao thức ở tầng transport và các vấn đề về thiết kế ở tầng ứng dụng. Mô phỏng biến cố rời rạc 2. Các khái niệm và thành phần của hệ thống mô phỏng Hệ thống mô phỏng biến cố rời rạc sử dụng các thành phần sau: - Thực thể (Entity): Trừu tượng hóa của một đối tượng. Mỗi thực thể được mô tả bởi các thuộc tính của nó.
Ví dụ thực thể gói tin có các thuộc tính như kích thước, địa chỉ nguồn, địa chỉ đích… - Hệ thống (System) là một tập các thực thể và quan hệ giữa chúng, thực hiện một mục đích nào đó. Ví dụ một hệ thống mạng có thể được định nghĩa bởi các thực thể máy tính, router và đường truyền cung cấp kết nối điểm điểm. - Hệ thống ròi rạc là một hệ thống mà trạng thái của nó được định nghĩa bởi các trạng thái của tất cả các thực thể trong hệ thống đó, các trạng thái này chỉ thay đổi ở những thời điểm rời rạc xác định. Trạng thái thay đổi được kích hoạt bởi một biến cố.
Loại biến cố tác động phụ thuộc vào hệ thống và mục tiêu nghiên Tìm hiều NS và mô phỏng mạng máy tính 9 Luan van Đề tài NCKH cấp trường T2014-156 cứu, có thể là gửi một gói tin, nhận một gói tin hoặc lựa chọn liên kết trên một trang Web. Các hệ thống thực tế thường phức tạp, để đánh giá đáp ứng của hệ thống bằng mô phỏng trên máy tính, cần xây dung một mô hình là sự trừu tượng hóa của hệ thống thực. Công việc này bao gồm lựa chọn thực thể và xác định quan hệ giữa các thực thể đó. Nguyên lý mô phỏng biến cố rời rạc Ý tưởng của mô phỏng biến cố rời rạc là nhảy từ biến cố này sang biến cố kế tiếp.
Trong đó biến cố xảy ra có thể kích hoạt những thay đổi trạng thái hệ thống hoặc phát sinh những biến cố mới. Các biến cố được ghi nhận thành danh sách các biến cố sẽ xảy ra (FEL – Future Event List), thực chất là một cấu trúc dữ liệu phù hợp để quản lý tất cả các biến cố trong mô phỏng. Mỗi biến cố gồm ít nhất 2 dữ liệu (thời gian, loại) trong đó thời gian là thời điểm biến cố xảy ra và loại mô tả loại biến cố. FEL phải được cài đặt có các phương thức để chèn thêm, xóa bỏ hoặc tìm kiếm các biến cố.1 trình bày tiến trình mô phỏng biến cố rời rạc theo thời gian.
t1 t2 ti ti+1 ti+2 Hình 1.1: Nguyên lý mô phỏng biến cố rời rạc. Trong quá trình mô phỏng, trạng thái hệ thống chỉ thay đổi ở các thời điểm ti Tại mỗi thời điểm rời rạc ti , trạng thái của hệ thống được lưu lại. Thường tất cả các bộ mô phỏng biến cố rời rạc sử dụng các thành phần: - Trạng thái hệ thống (System state): Một tập các biến mô tả trạng thái hệ thống, - Đồng hồ (Clock): Thời gian hiện tại trong quá trình mô phỏng, - Danh sách biến cố (FEL): Cấu trúc dữ liệu phù hợp quản lý các biến cố, - Các Bộ đếm thống kê (Statistical Counters): Một tập biến chứa thông tin thống kê về đáp ứng của hệ thống, - Chương trình con khởi tạo (Initialization routine): Một chương trình con khởi tạo mô hình mô phỏng và đặt đồng hồ về 0, - Chương trình con định thời (Timing routine): Một chương trình con lấy ra biến cố kế tiếp từ FEL và chuyển đồng hồ sang thời điểm biến cố kế tiếp, Tìm hiều NS và mô phỏng mạng máy tính 10 Luan van Đề tài NCKH cấp trường T2014-156 - Chương trình con xử lý biến cố (Event routine/Handler): Chương trình con được gọi khi một biến cố xảy ra trong quá trình mô phỏng. Mỗi loại biến cố sẽ có một chương trình con xử lý biến cố tương ứng.
Giải thuật lập lịch sự kiện – thay đổi thời gian Đây là giải thuật lõi của một bộ mô phỏng biến cố rời rạc. Trong thời gian mô phỏng, trang thái hệ thống thay đổi theo thời gian. FEL chứa tất cả các biến cố sắp xếp tuần tự theo thời gian. 𝑓𝑒𝑙 = [𝑡1 , 𝑡2 , … 𝑡𝑘 ] 𝑡𝑟𝑜𝑛𝑔 đó 𝑡1 ≤ 𝑡2 ≤ … ≤ 𝑡𝑘 Lưu đồ của giải thuật được trình bày ở hình 1.2 gồm 3 phần: Khởi tạo, vòng lặp xử lý và xuất kết quả.
Start Initialization o Select next event Event routine 1 Event routine 2 Event routine 3 No Terminate Yes Output End Hình 1.2: Lưu đồ mô phỏng biến cố rời rạc. Thuật toán lập lịch sự kiện – thay đổi thời gian 2. Khởi động và kết thúc mô phỏng Khởi động: Thực hiện ở bước khởi tạo trên lưu đồ - các biến cố được phát sinh và chứa vào FEL. Kết thúc: Mô phỏng kết thúc khi một trong các điều kiện sau xảy ra: Tìm hiều NS và mô phỏng mạng máy tính 11 Luan van Đề tài NCKH cấp trường T2014-156 - Biến cố kết thúc: ví dụ thời gian trễ của gói tin lớn hơn 500ms, đã gửi được 1000 bytes hoặc số lượng gói tin mất nhiều hơn 50, - Sau một khoảng thời gian mô phỏng xác định: sau 1000s - Cho đến khi fel trống (không còn biến cố nào).
Các kiểu chạy mô phỏng Có 2 kiểu chạy mô phỏng: Mô phỏng quá độ (transient) và mô phỏng trạng thái ổn định (steady state). Việc lựa chọn loại mô phỏng đặc biệt quan trọng đối với việc phân tích kết quả mô phỏng. Mô phỏng quá độ còn được xem là mô phỏng dừng (terminating) vì mô phỏng này chỉ chạy trong một khoảng thời gian xác định. Thời gian chạy mô phỏng có thể cho trước bởi một biến cố kết thúc đặc biệt hoặc một thời điểm xác định trước.
Mô phỏng trạng thái ổn định còn được gọi là mô phỏng không dừng (non-terminating). Mục tiêu của mô phỏng loại này nhằm nghiên cứu đáp ứng trong thời gian dài của hệ thống, vì vậy thời gian chạy mô phỏng trong trường hợp này phải được thiết lập để các điều kiện ban đầu không làm ảnh hưởng đến kết quả mô phỏng. Vấn đề quan trọng là xác định số lần chạy mô phỏng phù hợp.