Bài giảng Mô hình hóa và mô phỏng mạng (Các hệ thống rời rạc nói chung) - Chương 1: Giới thiệu - Nguyễn Đức Tài

Nội dung text: Bài giảng Mô hình hóa và mô phỏng mạng (Các hệ thống rời rạc nói chung) - Chương 1: Giới thiệu - Nguyễn Đức Tài

1. TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TPHCM TS Nguyễn Đức Tài GIỚI THIỆU MÔN HỌC: MÔ HÌNH HÓA VÀ MÔ PHỎNG 1 MẠNG (CÁC HỆ THỐNG RỜI RẠC NÓI CHUNG)
2. THÔNG TIN GIẢNG VIÊN Giảng viên lý thuyết: Nguyễn Đức Tài Email: ndtai@fit.hcmus.edu.vn Văn phòng: phòng B11, trường ĐH CNTT Thời gian tiếp sinh viên: từ 09g15 đến 11g30, thứ năm Giảng viên thực hành: 1/ Trương Thị Mỹ Trang Email: ttmtrang@fit.hcmus.edu.vn 2/ Trương Phước Hưng Email: tphung@fit.hcmus.edu.vn 2
3. THÔNG TIN HỌC PHẦN Số tín chỉ: 4  Số lý thuyết: 45 (thuyết giảng và thảo luận)  Số thực hành: 30  Số tiết tự học: 120 Kết quả học tập được đánh giá trong suốt quá trình học, bao gồm: kiểm tra trên lớp (20%), báo cáo bài tập thực hành (30%), thi giữa kỳ (20%), thi cuối kỳ (30%). 3
4. TÓM TẮT NỘI DUNG MÔN HỌC Khái niệm cơ bản về mô hình hóa và mô phỏng hệ thống và mạng; Mô hình toán học các hệ thống rời rạc trong đó trọng tâm là sử dụng mô hình hàng đợi, mô hình mạng hàng đợi; Các phương pháp mô hình  mô hình hóa phân tích;  mô hình hóa số học (trong đó có tiến trình Markov, mô hình Markov);  mô hình hóa mô phỏng (GPSS World, NS-2/NS-3). 4
5. HỌC XONG BIẾT ĐƯỢC GÌ? Nền tảng toán học cơ bản của mô hình hệ thống, ý nghĩa trong thực tế những nền tảng đó; Nguyên lý mô hình hóa những hệ thống phức tạp trên cơ sở những ví dụ mô hình hàng đợi, mạng hàng đợi với việc sử dụng 3 phương pháp mô hình hóa chính: phân tích; số học; mô phỏng. Một bộ nhỏ nhất các mô hình, phương pháp và công cụ để nghiên cứu những hệ thống thực không phức tạp trong những lĩnh vực ứng dụng khác nhau. 5
6. MÔN HỌC MANG TÍNH CHẤT NGHIÊN CỨU NHIỀU HƠN SO VỚI TÍNH CHẤT CÔNG NGHỆ Mô hình hóa hướng đến việc nghiên cứu tính chất của hệ thống thực, đưa ra các khuyến cáo để cải tiến dựa trên các đánh giá; Việc thiết kế các mô hình toán học cần cơ sở của thuyết xác suất, thuyết hàng đợi. Các thuyết này cũng mang tính chất nghiên cứu. Kết quả của nghiên cứu thường được sử dụng để phát triển thành công nghệ, mô hình hóa cũng không ngoại lệ, đặc biệt khi thiết kế mô hình hoặc cải tiến hệ thống (công nghệ). 6
7. TẠI SAO LÀ MÔ HÌNH HÓA? Nghiên cứu tính chất, cải tiến hay thiết kế mới các hệ thống thực [vốn không thể dùng những phương pháp nghiên cứu hoặc thực nghiệm trực tiếp hoặc là không kinh tế khi dùng các phương pháp đó]. Tại sao là thuyết xác suất? Phần lớn các hệ thống kỹ thuật, trong đó có máy tính và mạng, được mô tả bằng những tiến trình ngẫu nhiên rời rạc với việc sử dụng các phương pháp xác suất. Phần lớn áp dụng những mô hình toán học được xây dựng trên cơ sở những mô hình thuộc thuyết hàng 7 đợi.
8. Tại sao là thuyết hàng đợi? Dung lượng buffer trong router bao nhiêu là tối ưu ? Tôi phải chờ bao lâu Mạng điện thoại bị trong khi sắp hàng ở siêu nghẽn vào lúc nào? thị? 8 QoS : Delay, Variation (jitter)? bị nghẽn, khắc phục thế nào?
9. LỊCH SỬ CỦA THUYẾT HÀNG ĐỢI Agner Krarup Erlang, a Danish engineer who worked for the Copenhagen Telephone Exchange, published the first paper on queueing theory in 1909; David G. Kendall introduced an A/B/C queueing notation in 1953. Important work on queueing theory used in modern packet switching networks was performed in the early 1960s by Leonard Kleinrock. 9
10. VẤN ĐỀ CƠ BẢN VỀ MÔ HÌNH HÓA 1. Được áp dụng trong hầu hết các lĩnh vực của cuộc sống: toán học, vật lý học, quang học, điện tử, kinh tế, xã hội, nghệ thuật, sinh học, y học, ; 2. Mô hình hóa có thể a) phân tích được những kết quả khác nhau; b) xác định khả năng (hiệu suất) làm việc và đánh giá tính tin cậy của hệ thống; c) đưa ra được điểm thắt nút cổ chai và những nơi [có] tải nhỏ; d) đưa ra những khuyến cáo về những thay đổi hợp lý những thành phân và cấu trúc hay 10 phương thức hoạt động của hệ thống.
11. CÁC KHÁI NIỆM CƠ BẢN (XEM SÁCH THÊM) Hệ thống (system)  Tính toàn vẹn (integrity)  Tính gắn kết (coherence)  Tính tổ chức (organization)  Tính tích hợp (intergrativity) Phần tử (element) Phức hệ (complex) Cơ cấu (cấu trúc, structure) Hoạt động (function) Tổ chức hệ thống  Tổ chức theo cơ cấu (structured organization);  Tổ chức theo hoạt động (functional organization). 11
12. LIÊN HỆ GIỮA THAM SỐ VÀ ĐẶC TÍNH Mô hình hóa hướng đến việc giải những bài toán sau: 1) phân tích(analysis) 2) tổng hợp (synthesis) Ví dụ: 1) Bài toán phân tích: tôi phải đợi bao nhiêu lâu trong khi sắp hàng; Tham số: số lượng người (tải ngoài), đặc tính: thời gian đợi; Dung lượng của buffer trong router là bao nhiêu ; QoS - xác định time delay, jitter khi cho trước các tham số về mạng ; 2) Bài toán tổng hợp: Xác định topology mạng, throughput của kênh truyền trong mạng khi biết trước giá thành . Tham số: topology, throughput; Đặc tính: giá thành; 12 QoS – xác định cấu trúc của mạng để thỏa mãn time delay, jitter;
13. LIÊN HỆ GIỮA THAM SỐ VÀ ĐẶC TÍNH Tham số (parameter) – được mô tả bởi tính chất ban đầu của hệ thống và là dữ liệu đầu vào khi giải quyết bài toán phân tích. Đặc tính (characteristics) – được mô tả bởi tính chất đứng thứ hai (đứng sau, kết quả) và được xác định trong quá trình giải bài toán phân tích như là một hàm của tham số: 13 đặc tính = f(tham số).
14. CÁC KHÁI NIỆM CƠ BẢN (XEM SÁCH THÊM) Tiến trình (process) – sự thay đổi tuần tự của những trạng thái của hệ thống theo thời gian. Trạng thái (state) của hệ thống được cho bởi tập hợp những giá trị các biến mô tả trạng thái đó. Hệ thống thực hiện một bước chuyển tiếp (transition) từ một trạng thái này sang trạng thái khác nếu các biến mô tả của nó thay đổi từ những giá trị, xác định một trạng thái này, sang những giá trị xác định một trạng thái khác. Nguyên nhân tạo nên một bước chuyển tiếp từ trạng thái này sang trạng thái khác, gọi là sự kiện (event) Phân loại hệ thống, tiến trình, mô hình • liên tục (continuous) hoặc rời rạc (discrete); • định trước (định mệnh) hoặc ngẫu nhiên (phân loại cho cả tham số); 14 • ổn định (stationary) hoặc không ổn định;
15. Những bài toán mô hình hóa Thiết kế (phát triển) mô hình;  chọn một công cụ toán học cụ thể;  các mô hình phải thể hiện được những khả năng có thể [các trường hợp có thể] của các tổ chức cơ cấu-hoạt động của hệ thống;  Tham số hóa mô hình; Phân tích đặc tính hệ thống; Tổng hợp hệ thống;  Tổng hợp theo cơ cấu;  Tổng hợp theo hoạt động;  Tổng hợp theo tải ngoài; Phân tích chi tiết hệ thống đã tổng hợp.  Đánh giá chất lượng giải quyết bài toán thiết kế hệ thống;  Đánh giá các tham số hệ thống trong quá trình tổng hợp;  đưa ra những khả năng tới hạn [chặn trên, chặn dưới] của 15 hệ thống, những điểm thắt nút cổ chai .
16. Các phương pháp mô hình hóa Phân tích (analytical) – (công cụ: thuyết xác suất, thuyết hàng đợi, thuyết các tiến trình ngẫu nghiên, các phương pháp tối ưu, ); Số học (numeral) – ( sử dụng các phương pháp phân tích số học để nhận được nhũng kết quả hữu hạn ở dạng số, khi mà không thể có được sự liên hệ phân tích của đặc tính vào tham số ở dạng thức rõ ràng. Thống kê (statistical) hay còn gọi là mô phỏng (simulation) (nghiên cứu trên máy tính, dựa vào phương pháp các phép thử thống kê và sử dụng các chương trình chuyên biệt và ngôn ngữ mô hình hóa: NS2, OPNET,Netsim, OMNeT++ (cho mạng máy tính), GPSS World, SIMULA, v.v Kết hợp các phương pháp trên 16
17. REFERENCES L. Kleirock, Queueing Systems Volume 1: Theory, A Wiley-Interscience Publication, 1975. L. Kleirock, "Queuing systems Volume 2: Computer applications," Wiley, Chichester, 1976. 17