Bài giảng Mô hình hóa và mô phỏng mạng - Mô hình toán học những hệ thống rời rạc - Nguyễn Đức Tài

Nội dung text: Bài giảng Mô hình hóa và mô phỏng mạng - Mô hình toán học những hệ thống rời rạc - Nguyễn Đức Tài

1. TRƯỜNG ĐẠI HỌC KHOA HỌC TỰ NHIÊN TPHCM MÔ HÌNH HÓA VÀ MÔ PHỎNG MẠNG Mô hình toán học những hệ thống rời rạc 1 TS. Nguyễn Đức Tài
2. MÔ HÌNH HỆ THỐNG HÀNG ĐỢI (HTHĐ) Yêu cầu (application, request), nhu cầu (demand), cuộc gọi (call), khách hàng (customer) ) Luồng yêu cầu - Tập hợp các yêu cầu phân bố theo thời gian; Thiết bị phục vụ (hay đơn giản gọi là thiết bị, kênh (channel), đường dây (line) – phần tử của HTHĐ, chức năng là phục vụ các yêu cầu. Phục vụ - sự kéo dài [trì hoãn] (delay) thời gian của một yêu cầu trong thiết bị phục vụ. (ví dụ: thời gian truyền packet trên kênh truyền, ví dụ minh họa) Thiết bị lưu trữ (buffer) – tập hợp các chỗ để đợi các yêu cầu [phía] trước thiết bị phục vụ. Số lượng chỗ để đợi gọi là dung lượng lưu trữ. 2 Số lượng các yêu cầu chờ đợi để phục vụ nằm trong thiết bị lưu trữ xác định chiều dài hàng đợi.
3. MÔ HÌNH HỆ THỐNG HÀNG ĐỢI Quy luật đệm (QLĐ, buffering discipline) – quy tắc đưa yêu cầu vào thiết bị lưu trữ (bộ đệm, buffer). Quy luật phục vụ (QLPV, service discipline) – quy tắc chọn các yêu cầu từ hàng đợi để phục vụ trong thiết bị. Độ ưu tiên – đặc quyền cho việc đưa yêu cầu vào thiết bị lưu trữ hoặc chọn yêu cầu một loại nào đó từ hàng đợi để phục vụ Các giả định:  Yêu cầu đi vào hệ thống, lập tức đưa vào phục vụ nếu thiết bị rảnh;  Trong thiết bị phục vụ mỗi một thời điểm chỉ có một yêu cầu;  Sau khi hoàn thành việc phục vụ một yêu cầu nào đó, yêu cầu trong hàng đợi được chọn để phục vụ là lập tức (thiết bị làm việc không nghỉ, nếu trong hàng đợi có ít nhất một yêu cầu);  Việc đi đến của yêu cầu vào HTHĐ và thời gian phục vụ của chúng là không phụ thuộc vào việc có bao nhiêu yêu cầu đang có trong hệ thống, hoặc là những nhân tố khác; 3  Thời gian phục vụ các yêu cầu là không phụ thuộc vào tốc độ đến của yêu cầu vào hệ thống.
4. MÔ HÌNH MẠNG HÀNG ĐỢI (MHĐ) Nút của mạng hàng đợi là hệ thống hàng đợi. Nguồn (Generator)– nguồn phát các yêu cầu đến MHĐ và các yêu cầu cần một số xác định các bước phục vụ trong những nút của mạng. Sự chuyển tiếp các yêu cầu giữa các nút MHĐ 4 có thể được cho ở dạng xác suất truyền (ở dạng ma trận)
5. LUỒNG YÊU CẦU Tập hợp những sự kiện phân bố theo thời gian được gọi là luồng (traffic). Nếu sự kiện là sự xuất hiện các yêu cầu, thì gọi là luồng yêu cầu. Mô tả: đưa ra những khoảng thời gian giữa những thời điểm lân cận và việc các yêu cầu đến với số thứ tự (k-1) và k tương ứng (k=1,2, ; thời điểm bắt đầu). Đặc tính cơ bản của luồng yêu cầu là cường độ – số yêu cầu trung bình đi qua trong một đơn vị thời gian. Giá trị xác định khoảng thời gian trung bình giữa hai yêu cầu liên tiếp. Giá trị :  định trước (deterministic, định mệnh);  : đều đặn (regular);  Luồng, mà trong đó những khoảng thời gian giữa các yêu cầu liên tiếp là biến ngẫu nhiên thì gọi là [luồng] ngẫu nhiên. 5
6. LUỒNG YÊU CẦU ĐƠN GIẢN NHẤT Luồng yêu cầu được gọi là tĩnh (statical) nếu cường độ và luật phân bố những khoảng thời gian giữa các yêu cầu không thay đổi theo thời gian. Nếu ngược lại thì luồng yêu cầu gọi là không tĩnh (non-statical). Luồng yêu cầu gọi là thông thường (ordinary) nếu ở mỗi thời điểm có thể xuất hiện chỉ một yêu cầu. Nếu ở một thời điểm nào đó xuất hiện hơn một yêu cầu thì gọi là luồng yêu cầu không thông thường hay gọi là theo nhóm (group). Luồng yêu cầu gọi là không có phản ảnh (hậu quả) nếu các yêu cầu đến không phụ thuộc vào nhau, nghĩa là thời điểm đến các yêu cầu theo thứ tự không phụ thuộc vào việc, khi nào và đã có bao nhiêu yêu cầu đã đến trước thời điểm đó. Luồng tĩnh-thông thường-không có phản ảnh được gọi là [luồng] đơn giản nhất. 6
7. LUỒNG YÊU CẦU ĐƠN GIẢN NHẤT Những khoảng thời gian giữa các yêu cầu trong luồng đơn giản nhất phân bố theo dạng mũ với hàm phân bố: trong đó – tham số của phân bố, là cường độ của luồng yêu cầu. Luồng đơn giản nhất thường được gọi là [luồng] Poisson, bởi vì số yêu cầu k đi vào trong một khoảng thời gian t cho trước phân bố theo luật Poisson: Trong đó – xác suất k yêu cầu đi đến trong một khoảng thời gian cố định t; Điểm đặc biệt:  Tính cộng (kết hợp) các luồng. 7  Tính phân tách luồng theo xác suất.  Tính đơn giản.
8. THỜI GIAN PHỤC VỤ YÊU CẦU Thời gian phục vụ – thời gian yêu cầu nằm trong thiết bị phục vụ - biến ngẫu nhiên và được mô tả bởi hàm phân bố hoặc hàm mật độ phân bố Trong trường hợp các luồng không đồng nhất thì thời gian phục vụ yêu cầu có thể được phân biệt bởi các hàm phân bố khác nhau hoặc chỉ là giá trị trung bình. Thường thì thời gian phục vụ yêu cầu sử dụng luật mũ, điều này làm đơn giản đáng kể vấn đề về toán học. Cường độ phục vụ: . Ví dụ: Cho trước thời gian phục vụ của một luồng yêu cầu nào đó, các yêu cầu được sắp xếp đi vào HTHĐ như thế nào để tổng thời gian đợi của tất 8 cả các yêu cầu là nhỏ nhất?
9. CÁC QUY LUẬT ĐỆM Sự có mặt của độ ưu tiên giữa các yêu cầu:  Không có ưu tiên;  Có ưu tiên. Phương thức thay thế các yêu cầu từ hàng đợi:  Không có thay thế: khi yêu cầu đi vào hàng đợi đã đầy sẽ bị mất;  Với sự thay thế yêu cầu với cùng một loại (một lớp);  Với sự thay thế yêu cầu thuộc loại (lớp) hoặc thuộc vào nhóm có độ ưu tiên thấp nhất; Quy luật thay thế hoặc chọn yêu cầu để phục vụ:  Thay thế ngẫu nhiên;  Thay thế yêu cầu đến cuối cùng, nghĩa là yêu cầu đến muộn nhất; (ví dụ-?)  Thay thế yêu cầu lâu nhất, nghĩa là yêu cầu nằm trong thiết bị lưu trữ lâu nhất; (ví dụ-?) 9 Khả năng thay đổi độ ưu tiên (Ví dụ-?).
10. CÁC QUY LUẬT PHỤC VỤ Theo số lượng:  Đơn;  Nhóm;  Phối hợp đơn và nhóm. Không có độ ưu tiên:  FIFO – First In First Out;  LIFO - Last In First Out;  Phục vụ theo thứ tự ngẫu nhiên;  Phục vụ theo thứ tự luân phiên (khi có nhiều thiết bị phục vụ, việc phục vụ theo thứ tự luân phiên các hàng đợi từ 1,2, H, H – số lượng các thiết bị lưu trữ hay hàng đợi) Có độ ưu tiên:  Ưu tiên tương đối;  Ưu tiên tuyệt đối;  Ưu tiên hỗn tạp: phối hợp giữa phục vụ không ưu tiên, hay ưu tiên tương đối và ưu tiên tuyệt đối;  Ưu tiên luân phiên: giống như trường hợp ưu tiên tương đối nhưng dành cho một nhóm các yêu cầu;  Phục vụ theo lịch (kế hoạch): theo kế hoạch nào đó, được cho bởi chuỗi chất vấn hàng đợi các yêu cầu , ví dụ trong trường hợp có 3 loại10 (lớp) yêu cầu thì lịch (hay kế hoạch) có thể có dạng: {1,2,1,3,1,2}
11. PHÂN LOẠI CÁC MÔ HÌNH HÀNG ĐỢI Giả định về dung lượng lưu trữ vô hạn có thể được sử dụng để mô hình hóa những hệ thống thực, trong đó xác suất mất mát yêu cầu vì tràn thi t b l u tr (tràn b đ m) có dung l ng gi i ế ị ư ữ ộ ệ ượ ớ 11 hạn nhỏ hơn ).
12. CÁC YÊU CẦU ĐƯỢC PHÂN LOẠI TRONG HTHĐ Trong HTHĐ, vốn là mô hình toán học trừu tượng, các yêu cầu thuộc về những loại (lớp) khác nhau trong trường hợp nếu chúng trong hệ thống thực được mô hình hóa khác nhau chỉ một trong những nhân tố sau:  Thời gian phục vụ;  Độ ưu tiên. Nếu các yêu cầu không khác nhau về thời gian phục vụ và độ ưu tiên thì, trong HTHĐ chúng có thể được xem như các yêu cầu cùng một loại (lớp), không phụ thuộc vào bản chất vật lý. 12
13. PHÂN LOẠI CÁC MẠNG HÀNG ĐỢI Phụ thuộc vào đặc trưng của tiến trình phân thành:  Định trước  Ngẫu nhiên Phụ thuộc vào sự liên hệ giữa các cường độ luồng ở các nút:  Tuyến tính - hệ số tỷ lệ (hệ số truyền, transfer coefficient), chỉ ra cường độ luồng yêu cầu ở nút j gấp bao nhiêu lần so với ở nút i Ví dụ: hệ số truyền của nút nào đó bằng 3: bất kỳ một yêu cầu nào trong thời gian ở trong mạng có trung bình 3 lần rơi vào phục vụ ở nút đó.  Không tuyến tính Sự mất mát các yêu cầu trong mạng, Sự nhân lên của các yêu cầu, ví dụ như sự hình thành một số các yêu cầu mới sau khi hoàn thành phục vụ 13
14. PHÂN LOẠI CÁC MẠNG HÀNG ĐỢI MHĐ mở:  Nguồn phát không phụ thuộc;  Số lượng yêu cầu trong mạng từ 0 đến vô cùng;  Môi trường bên ngoài được ký hiệu bằng nút ‘0’ , mà từ đó các yêu cầu đi vào mạng, cũng từ đó mà từ mạng đi ra sau khi được phục vụ trong mạng ; MHĐ đóng:  Không có những nguồn phát ngoài ;  số lượng không đổi các yêu cầu M;  ‘cung’ đặc biệt mô tả quá trình hoàn thành phục vụ yêu cầu 14 trong mạng và lập tức hình thành một yêu cầu mới với cùng những tham số phục vụ
15. PHÂN LOẠI CÁC MẠNG HÀNG ĐỢI Việc phân chia nút ‘0’ trong MHĐ đóng theo đuổi được 2 mục đích:  Đạt được sự thống nhất trong việc thể hiện và mô tả toán học của MHĐ mở và MHĐ đóng;  Đảm bảo khả năng xác định được đặc tính thời gian của MHĐ đóng tương đối so với nút ‘0’. Nói cụ thể là, thời gian ở lại của yêu cầu trong MHĐ đóng được xem như khoảng thời gian giữa hai thời điểm cận kề nhau của yêu cầu khi qua điểm ‘0’. MHĐ đóng-mở là phối hợp của HMĐ đóng và MHĐ mở, ngoài số lượng không đổi M* các yêu cầu lưu chuyển trong mạng, thì từ nguồn phát bên ngoài các yêu cầu cùng một lớp đi vào hệ thống, tổng số yêu cầu trong mạng là M>M*. 15
16. PHÂN LOẠI CÁC MẠNG HÀNG ĐỢI Phụ thuộc vào loại các yêu cầu lưu chuyển trong mạng  Đồng nhất: trong đó chỉ lưu chuyển một lớp các yêu cầu;  Không đồng nhất: trong đó lưu chuyển một vài lớp các yêu cầu mà được phân biệt bởi một trong các nhân tố sau: Thời gian phục vụ trong nút; Độ ưu tiên; Định tuyến. 16
17. KÝ HIỆU HỆ THỐNG HÀNG ĐỢI (KÝ HIỆU G. KENDALL) A/B/N/L A – luật phân bố của luồng yêu cầu vào B – Luật phân bố thời gian phục vụ N - số lượng các thiết bị phục vụ trong hệ thống; L – số lượng chỗ trong thiết bị lưu trữ, có thể nhận các giá trị 0,1,2, 17
18. CÁC KÝ HIỆU CỦA LUẬT PHÂN BỐ TRONG HTHĐ G (General) – bất kỳ phân bố nào (chung chung); M (Markovian) – phân bố mũ; D (Deterministic) – phân bố định trước (định mệnh); U (Uniform) – phân bố thống nhất (phân bố đều liên tục); (Erlang) – phân bố Erlang bậc k, (với k các pha [phân bố] mũ liên tục giống nhau); (HypoExponential) – phân bố HypoExponential bậc k (với k các pha [phân bố] mũ liên tục không giống nhau); (HyperExponential) – phân bố siêu mũ bậc r (với r các pha [phân bố] mũ song song); g (gamma) – phân bố Gamma; P (Pareto) – phân b Pareto; ố 18
19. THAM SỐ VÀ ĐẶC TÍNH CỦA HỆ THỐNG HÀNG ĐỢI Tham số cơ cấu  Số lượng các thiết bị phục vụ K;  Số lượng thiết bị lưu trữ k và dung lượng lưu trữ Tham số tải  Số lượng lớp các yêu cầu H đi vào hệ thống  Luật phân bố luồng yêu cầu  Luật phân bố thời gian phục vụ Đặc tính:  Tải ngoài của hệ thống:  Tải trong:  Tỷ lệ [thời gian] nghỉ: ;  Xác suất mất mát:  Xác suất phục vụ các yêu cầu:  Hiệu suất hệ thống, chính là cường độ của luồng các 19 yêu cầu được phục vụ:  Cường độ luồng yêu cầu bị mất mát
20. ĐẶC TÍNH CỦA HỆ THỐNG HÀNG ĐỢI Thời gian đợi trung bình trong hàng đợi: w; Thời gian ở trung bình của yêu cầu trong hệ thống: u=w+b; Chiều dài trung bình của hàng đợi: l= ; Số lượng trung bình các yêu cầu trong l= hệ thống (Các công thức Little ) ĐiỀU KiỆN ĐỂ HTHĐ hoạt động ổn định: Không bị quá tải: 20
21. CÁC ĐẶC TÍNH CỦA HTHĐ VỚI LUỒNG YÊU CẦU KHÔNG ĐỒNG NHẤT (TƯƠNG TỰ, XEM SÁCH) Theo mỗi một loại (lớp) yêu cầu Đặc tính luồng yêu cầu tổng  Cường độ tổng luồng các yêu cầu đi vào hệ thống  Tổng tải ngoài Y và tổng tải trong R:    Thời gian đợi trung bình W và thời gian ở lại U các yêu cầu nối thành một luồng trong hệ thống 21
22. THAM SỐ VÀ ĐẶC TÍNH CỦA MẠNG HÀNG ĐỢI (TƯƠNG TỰ, XEM SÁCH) Tham số:  Số nút trong mạng: n;  Số thiết bị phục vụ trong các nút của mạng:  Ma trận xác suất truyền  Cường độ nguồn phát yêu cầu, đi vào MHĐ mở hoặc số lượng yêu cầu M lưu chuyển trong MHĐ đóng;  Thời gian phục vụ trung bình của yêu cầu trong các nút mạng;  Đặc tính (chia thành 2 lớp: cho từng nút và cho mạng nói chung)  Tổng tải ngoài  Tổng tải trong  Thời gian chờ trung bình của yêu cầu  Thời gian ở trung bình trong mạng  Hiệu suất của MHĐ đóng 22
23. CƠ CHẾ HOẠT ĐỘNG CỦA HTHĐ VÀ MHĐ Ổn định Không ổn định 23