Bài giảng Mô hình hóa và mô phỏng mạng - Mô hình hóa phân tích (Phần 2) - 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 hóa phân tích (Phần 2) - 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 hóa phân tích Phần (2) – Tính toán 1 mạng hàng đợi TS. Nguyễn Đức Tài
2. MẠNG HÀNG ĐỢI MỞ CÓ DẠNG MŨ VỚI LUỒNG ĐỐNG NHẤT • Thời gian phục vụ yêu cầu trong tất cả các nút là biến ngẫu nhiên, phân bố theo luật mũ; • Một nút có thể là một HTHĐ một kênh hoặc là HTHĐ nhiều kênh; 2 • Trong mỗi một nút của MHĐ mở các thiết bị lưu trữ có dung lượng vô hạn,
3. MẠNG HÀNG ĐỢI MỞ CÓ DẠNG MŨ VỚI LUỒNG ĐỐNG NHẤT Mô tả MHĐ mở-tuyến tính-đồng nhất cần cho những tham số sau: Số nút trong mạng: n; Số thiết bị phục vụ trong các nút mạng: ; Ma trận xác suất truyền: , trong đó xác suất truyền phải thỏa mãn điều kiện: tổng các phần tử mỗi hàng phải bằng 1; Cường độ của nguồn phát yêu cầu đi vào MHĐ mở; Các thời gian phục vụ trung bình của các nút . 3
4. MẠNG HÀNG ĐỢI MỞ CÓ DẠNG MŨ VỚI LUỒNG ĐỐNG NHẤT Tính toán các đặc tính hoạt động của MHĐ mở-tuyến tính-đồng nhất dựa trên việc biến đổi mạng tương đương và thực thi theo 4 bước sau:  Tính toán các hệ số truyền và cường độ các luồng yêu cầu trong mỗi nút ;  Kiểm tra điều kiện không có quá tải trong MHĐ;  Tính các đặc tính của các nút;  Tính các đặc tính của mạng; 4
5. 1. TÍNH HỆ SỐ TRUYỀN VÀ CƯỜNG ĐỘ LUỒNG . YÊU CẦU TRONG MỖI NÚT CỦA MHĐ MỞ • Chế độ làm việc ổn định • Giả định rằng các cường độ các luồng yêu cầu đi vào các nút 0,1, ,n được xác định bằng những xác suất truyền • Hệ số được gọi là hệ số truyền và xác định số lượng trung bình các yêu cầu ‘rơi vào’ nút i trong khi nó ở trong mạng, trong khi đó 5
6. 2. KIỂM TRA ĐIỀU KIỆN KHÔNG CÓ SỰ QUÁ TẢI TRONG MHĐ Nếu điều kiện trên không được thực thi, thì từ đó suy ra rằng, chế độ ổn định trong MHĐ mở có thể được thực hiện bởi một trong những cách thức sau:  Giảm cường độ từ nguồn phát bên ngoài đến giá trị mà ở đó điều kiện trên được thực thi;  Tăng số lượng các thiết bị phục vụ trong các nút bị quá tải;  Giảm thời gian phục vụ các yêu cầu ở các nút bị quá tải;  Giảm hệ số truyền ở các nút bị quá tải. 6
7. 3. TÍNH CÁC ĐẶC TÍNH CỦA NÚT TRONG MHĐ MỞ (KHÁI NIỆM ‘BIẾN ĐỔI’) Khái niệm ‘biến đổi’: Một đối tượng được xem xét [nghiên cứu] ở mức độ chi tiết hóa khác nhau, có thể thể hiện bởi những mô hình hàng đợi khác nhau, mà các đặc tính của chúng là giống nhau hoặc là khác nhau với một giá trị không vượt quá sai số cho trước nào đó. Khi thực thi được những điều kiện xác định thì những mô hình đó dễ dàng biến đổi lẫn nhau. Các mô hình có thể biến đổi lẫn nhau.  Biến đổi tương đương;  Biến đổi tương tự; Hai mô hình mạng được gọi là tương đương nếu các đặc tính được so sánh của những mô hình này là không khác nhau. Hai mô hình mạng được gọi là tương tự nếu giá trị các đặc 7 tính xác định là khác nhau với một giá trị không vượt quá một giá trị cho trước.
8. 3. TÍNH CÁC ĐẶC TÍNH CỦA NÚT TRONG MHĐ MỞ (BIẾN ĐỔI MHĐ THÀNH CÁC HTHĐ) Sử dụng các tính chất các mô hình tương đương và tương tự tạo điều kiện làm đơn giản việc tính toán các đặc tính của các mô hình bằng cách thay những mô hình mạng phức tạp bằng các mô hình mạng đơn giản hơn. Tính các đặc tính hoạt động của MHĐ mở-tuyến tính-đồng nhất dựa trên biến đổi mạng tương đương, bao gồm việc biểu diễn MHĐ mở với n nút ở dạng n các HTHĐ có dạng mũ M/M/N và không phụ thuộc lẫn nhau. Cường độ đi vào của luồng yêu cầu vào HTHĐ (mà mô tả nút trong mạng) được xác định bởi hệ phương trình thông qua cường độ của luồng yêu cầu đi vào mạng và hệ số truyền: , còn thời gian phục vụ trung bình trong HTHĐ bằng thời gian phục vụ trong các nút tương ứng trong MHĐ. 8 Đặc tính của tất cả n HTHĐ= đặc tính của các nút trong MHĐ
9. 3. TÍNH CÁC ĐẶC TÍNH CỦA NÚT TRONG MHĐ MỞ Thời gian đợi trung bình của yêu cầu trong hàng đợi được tính bằng biểu thức cho trường hợp HTHĐ nhiều kênh dạng M/M/N hoặc cho HTHĐ một kênh dạng M/M/1. Tải ngoài của nút j, biểu thị số lượng trung bình các thiết bị bận: ; Tải trong của nút j: Hệ số [thời gian] nghỉ của nút j: Thời gian ở của yêu cầu trong nút j: Chiều dài hàng đợi các yêu cầu trong nút: Số lượng các yêu cầu (trong hàng đợi và trong thiết bị phục vụ): . 9
10. 3. TÍNH CÁC ĐẶC TÍNH CỦA MẠNG TRONG MHĐ MỞ Số lượng trung bình các yêu cầu chờ đợi [để] phục vụ trong mạng : Số lượng trung bình các yêu cầu có trong mạng: Thời gian đợi trung bình của yêu cầu trong mạng: Thời gian ở trung bình của yêu cầu trong mạng: 10
11. VÍ DỤ TÍNH MẠNG HÀNG ĐỢI MỞ Kết quả: 11
12. VÍ DỤ TÍNH MẠNG HÀNG ĐỢI MỞ 12
13. PHÂN TÍCH TÍNH CHẤT CỦA MHĐ MỞ Điều quan tâm nhất là tính chất của toàn thể mạng. Đặc tính cơ bản của MHĐ mở - thời gian ở trung bình U Để tránh việc quá tải trong MHĐ mở cần giảm tải cho điểm ‘thắt nút cổ chai’, điều này có thể được thực hiện bằng 2 cách:  Tăng tốc độ hoạt động của thiết bị phục vụ;  Tăng số lượng thiết bị phục vụ trong nút. Bất kỳ cách nào [trong 2 cách] nói trên đều tạo điều kiện làm tăng hiệu suất của MHĐ trên tổng thể. Đối với hệ thống thực: →tăng giá thành của hệ thống thực. Một phương pháp khác để giảm tải cho điểm thắt nút cổ chai: giảm xác suất truyền yêu cầu đến điểm (nút) đó. Ví dụ: Ổ cứng: những file 13 thường được sử dụng nhất nằm ở những ổ cứng nhiều tải nhất được chuyển sang ổ cứng có ít tải nhất. (Phân phối các file giữa các ổ cứng)
14. VÍ DỤ: TẢI TRONG TIẾN ĐẾN 1 ρ→1 Thời gian ở U tăng 4 lần, số yêu cầu tăng 6.5 lần Nút 1: Thời gian ở u1 tăng 4 lần, số yêu cầu M1 tăng 7 lần Nút 1 → NÚT THẮT NÚT CỔ CHAI 14
15. GIẢM TẢI NÚT THẮT CỔ CHAI – GIẢM THỜI GIAN PHỤC VỤ Giảm thời gian phục vụ đi 2 lần: Thời gian ở U giảm 9 lần (U=23.6); số yêu cầu trong các hàng đợi – giảm gần 20 lần; W=10.1 Chỉ dẫn đến sự thay đổi các đặc tính nút 1; Hệ quả của hoạt động không phụ thuộc lẫn nhau của các nút trong MHĐ mở-có dạng mũ. Sử dụng phương pháp tính toán các đặc tính của mạng dựa trên việc phân nhỏ (Decomposition) 15
16. GIẢM TẢI NÚT THẮT CỔ CHAI – TĂNG SỐ THIẾT BỊ PHỤC VỤ Giảm thời gian phục vụ đi 2 lần: Thời gian ở U = 26.78 (tăng 10% vì thời gian phục vụ lớn ); W=9.28 Chỉ dẫn đến sự thay đổi các đặc tính nút 1; 16
17. TÍNH MẠNG HÀNG ĐỢI ĐÓNG CÓ DẠNG MŨ VỚI LUỒNG ĐỒNG NHẤT Để mô tả MHĐ đóng-tuyến tính-đồng nhất-có dạng mũ cần cho những tham số giống như các tham số của MHĐ mở, chỉ một chỗ khác biệt:  Số yêu cầu M, lưu chuyển trong MHĐ đóng;  Cường độ các yêu cầu trong mạng không phải là tham số, mà là đặc tính, là hiệu suất của MHĐ đóng. Tính các đặc tính hoạt động của MHĐ đóng-tuyến tính-đồng nhất-có dạng mũ với các nút một kênh dựa vào định lý có tên gọi là ‘định lý về sự đi vào’ và được thực hiện với sự sử dụng phương pháp các giá trị trung bình chia thành 2 bước:  Tính các hệ số truyền trong các nút của mạng hàng đợi đóng 17  Tính các đặc tính của mạng hàng đợi đóng
18. TÍNH CÁC HỆ SỐ TRUYỀN TRONG CÁC NÚT CỦA MẠNG HÀNG ĐỢI ĐÓNG khi chia cả 2 vế cho : Cho , có thể tìm ra nghiệm của hệ phương trình 18
19. TÍNH CÁC ĐẶC TÍNH MẠNG HÀNG ĐỢI ĐÓNG Thời gian ở nút i Thời gian ở trongmạng: Hiệu suất của mạng: Số lượng yêu cầu trong nút i: 19
20. ĐỊNH LÝ VỀ SỰ ĐI VÀO Trong MHĐ đóng-có dạng mũ với các nút một kênh, trong đó có lưu chuyển M yêu cầu, xác suất ổn định của trạng thái của bất cứ nút nào trong thời điểm có yêu cầu mới đi vào nút là trùng với xác suất ổn định của chính trạng thái ấy của nút được xét trong mạng, trong đó số yêu cầu lưu chuyển nhỏ hơn 1 đơn vị, nghĩa là (M-1) yêu cầu. Điều này nghĩa là, trong mạng với M yêu cầu thì số yêu cầu trung bình là nằm trong nút i trong thời điểm có một yêu cầu mới đến (đi vào) nút này là bằng Lúc đó thời gian ở trung bình trong nút i của yêu cầu đã đến sẽ được cộng bởi thời gian phục vụ trung bình của tất cả của những yêu cầu đã đi vào trước và ở trong nút i với thời gian phục vụ trung bình của yêu cầu đang xét: 20
21. VÍ DỤ TÍNH TOÁN MẠNG HÀNG ĐỢI ĐÓNG Giả sử rằng điểm “0” mô tả việc kết thúc phục vụ yêu cầu trong mạng và hình thành tức thời một yêu cầu mới, điểm này nằm trên cung của nút 1, đi ra từ nút 1 rồi sau đó đi vào lại nút 1 Hiệu suất (흀0(M)) Thời gian ở 0.14 60 0.12 50 0.1 40 0.08 30 0.06 20 0.04 21 0.02 10 0 0 1 2 3 4 5 6 1 2 3 4 5 6
22. VÍ DỤ TÍNH TOÁN MẠNG HÀNG ĐỢI ĐÓNG 22
23. PHÂN TÍCH TÍNH CHẤT MHĐ ĐÓNG Sự tăng số lượng yêu cầu trong MHĐ đóng dẫn đến sự tăng các giá trị của tất cả các đặc tính mạng, bao gồm hiệu suất . Đến lượt mình, sự tăng hiệu suất dẫn đến sự tăng các tải trong của các nút của MHĐ, gắn liền với cường độ bởi biểu thức sau: Điểm M=M0 đặc trưng cho giá trị số lượng yêu cầu giới hạn nào đó. Việc tăng sau đó của số này dường như không có thích hợp nữa, bởi vì điều đó dẫn đến việc tăng đột ngột của thời gian ở trong khi chỉ tăng hiệu suất không đáng kể. Khi số yêu cầu trong MHĐ đóng đạt đến giá trị M0 nào đó, tải trong của một trong các nút sẽ tiến gần đến 1, khi đó thực tế là ngừng việc tăng hiệu suất, mà khi M→∞ đạt đến giá trị giới hạn của mình – băng thông . Nút như vậy gọi là “nút thắt cổ chai” của mạng. 23 Giá trị băng thông được xác định bởi băng thông của nút thắt cổ chai từ điều kiện là tải trong của nút này bằng 1
24. PHÂN TÍCH TÍNH CHẤT MHĐ ĐÓNG Khi tải trong của nút thắt cổ chai bằng 1, việc tăng hiệu suất sau đó khi tính đến việc tăng số lượng yêu cầu trong MHĐ đóng là không thể. Để tăng hiệu suất của MHĐ đóng, cũng như trong MHĐ mở, cần thiết phải giảm tải của nút thắt cổ chai. Trong một số trường hợp sự giảm tải của nút thắt cổ chai không dẫn đến việc làm cải thiện các đặc tính của MHĐ, (ví dụ làm tăng hiệu suất). Thường thì điều này liên hệ đến việc rằng trong MHĐ có thể tồn tại một số nút là những nút thắt cổ chai. Trong trường hợp này để cải thiện các đặc tính của MHĐ đóng cần thiết là 24 phải giảm tải ở tất cả các nút thắt cổ chai này.
25. KIỂM TRA ? Pr=80% 25