Viện Đại Học Mở Hà Nội
Khoa Công Nghệ Thông Tin

Môn Mạng Và Truyền Thông
Đề tài: Tìm hiểu về mô hình hàng đợi ( Queueing theory)

•
•

Giảng viên hướng dẫn :
Sinh viên thực hiện :

ThS Nguyễn Thành Huy
Nguyễn Văn Bảo - Lớp 17a05
Trần Văn Hiếu

www.powerpoint.vn

- Lớp 17a02


NỘI DUNG BÁO CÁO

1

PYRAMID DIAGRAMS

Các khái niệm cơ bản

2

Các tham số , thông số

3

Một số hàng đợi cơ bản

4

Mạng các hàng đợi

PAGE
www.powerpoint.vn

2


1.Các khái niệm cơ bản
1.1 Nguồn Gốc của hàng đợi :

Hàng Đợi
Agner Krarup Erlang 

mô hình mô tả cuộc trao đổi điện thoại

PAGE
www.powerpoint.vn

3



1.Các khái niệm cơ bản
1.2 Định nghĩa về hàng đợi

Hàng đợi
(queue)
Khách hàng ra
(output)
khách hàng vào

hệ thống phục vụ

(input)

(server)

PAGE
www.powerpoint.vn

4


2.Các tham số, thông số
2.1 Tham số đặc trưng
Thời gian phục vụ
Nguyên tắc dịch vụ

Tổng các phần tử có trong Queue

SEVER


Xác suất khoảng thời gian
yêu cầu hàng đợi

Dung lượng của Queue
Số lượng sever

PAGE
www.powerpoint.vn

5


2.Các tham số, thông số
2.2 Các nguyên tắc dịch vụ
01

02
FIFO(fisrt in first out)
Khách hàng đến trước sẽ được phục vụ trước

03

LIFO(last in first out)
Khách hàng đến sau được phục vụ trước.

RR( Round Robin)
Khách hàng tham gia vào hàng đợi theo quy tắc FIFO nhưng được cấp một khoảng thời
gian phục vụ nhất định

04


05

PS(processor Shariny)
Khách hàng đến ngay lập tức được phục vụ

P
Khách hàng được ưu tiên sẽ được phục vụ trước

PAGE
www.powerpoint.vn

6


2.Các tham số, thông số
2.2 Các nguyên tắc dịch vụ

Cơ sở dịch vụ
1 sever

•Máy chủ đơn:
n sever

•Máy chủ song song:
•Hàng đợi Tandem:

N queue

N sever


Hành vi chờ đợi của khách hàng

•Quấy rối: khách hàng quyết định không tham gia hàng đợi nếu quá dài
•Đuốc: khách hàng chuyển đổi giữa các hàng đợi nếu họ nghĩ rằng họ sẽ được
phục vụ nhanh hơn bằng cách làm như vậy

•Reneging: khách hàng rời khỏi hàng đợi nếu họ phải đợi quá lâu để có dịch vụ
PAGE
www.powerpoint.vn

7


2.Các tham số, thông số
2.3 Các phân bố xác suất được sử dụng

•

=

Phân bố xác định (D – Deterministic)

=
Queue theory

•

•


second

first

Phân bố mũ ( M – exponantial)

Queue theory

sever

Phân bố erlang

Không có hàng đợi, yêu cầu tiếp theo không được đáp ứng
nếu yêu cầu trước đó không được hoàn thành

PAGE
www.powerpoint.vn

8


2.Các tham số , thông số
2.4 Các thông số hiệu năng thường dùng trong mô hình mạng hàng đợi

 

•

Tốc độ đến của khách hàng (λ) : λ=


A

A – số các khách hàng đến hệ thống.

Queue theory

T – thời gian quan sát để đi vào hàng đợi
T

 

•

Thông lượng thoughput X=
C là số khách hàng hoàn thành dịch vụ
T là thời gian.

Trong một số trường hợp tốc độ đến hệ thống của các khách hàng λ sẽ bằng với thông lượng X.

PAGE
www.powerpoint.vn

9


2.Các tham số, thông số
2.4 Các thông số hiệu năng thường dùng trong mô hình mạng hàng đợi
Sevice

Wait (Thời gian đợi)


(thời gianđược phục vụ)

•

Thời gian đáp ứng:

R

=

W

+

S

W=S.Q

 
S: Tốc độ dịch vụ

Q: Số Khách hàng trong hàng đợi

B: Tổng thời
gian hệ thống

S=

C Số khách hàng

hoàn thành dịch vụ

bận

PAGE
www.powerpoint.vn

10


2.Các tham số , thông số
2.4 Các thông số hiệu năng thường dùng trong mô hình mạng hàng đợi

•

Độ hiệu dụng (xs queue !=0 & sever bận)

•

Độ hiệu dụng trung bình
Tổng thời gian sever bị bận

P0 Xác suất để hệ thống xếp hàng là rỗng

U=1-p0
U=B/T

•

Đơn vị tính %


Xác suất để 1 khách hàng bị từ chối là
Thời gian quan sát T

PN :

N :Kích thước hệ thống

PAGE
www.powerpoint.vn

11


2.Các tham số , thông số
2.5 Một số thuyết được sử dụng trong tính toán hàng đợi

•

Quá trình Poisson: biến ngẫu nhiên mô tả quá trình tuân theo phân bố mũ

•

Tính chất đặc trưng :

Tính đơn nhất :

-Có 1 KH trong khoảng tg [t,t+Δt])= λΔt+ o(Δt)
-0 có KH trong khoảng tg[t,t+Δt]) = 1 – λΔt +
o(Δt).

-Có >1 KH trong khoảng tg[t,t+Δt])= 0

Tính không nhớ

Tính dừng

quá trình kết hợp các

Tính dừng

quá trình Poisson độc lập

xác suất xuất hiện khách hàng

khác là một quá trình

trong khoảng thời gian A.t

Poisson nhân với tốc độ

không phụ thuộc vào
điểm đặt của khoảng thời gian đó.

PAGE
www.powerpoint.vn

12


2.Các tham số , thông số

2.5 Một số thuyết được sử dụng trong tính toán hàng đợi

•

Tính chất của Quá trình Poisson:

+Tính chất phân tích ngẫu nhiên :

+Tính chất liên hợp : quá trình kết hợp các quá trình Poisson khác
là một quá trình Poisson nhân với tốc độ

•

Xác suất của quá trình Poisson:
n khách hàng đến trung bình trong khoảng thời gian t với tốc độ λ

n=λt.

PAGE
www.powerpoint.vn

13


2.Các tham số , thông số
2.5 Một số thuyết được sử dụng trong tính toán hàng đợi

•

Quy tắc Little

Q =λ. R

số khách hàng
trung bình trong
hệ thống xếp hàng

tốc độ đến
của khách hàng

thời gian thường trú
của khách hàng trong hệ thống.

PAGE
www.powerpoint.vn

14


3.Một số hàng đợi cơ bản
3.1 M/M/1 : Hàng đợi Markov đơn giản nhất

1 Sever

2 đặc trưng chủ yếu của hàng đợi M/M/1 :

Tiến trình đến : Là tiến trình Poisson

Thời gian dịch vụ cho mỗi khách hàng
là ngẫu nhiên tuân theo phân bổ mũ


PAGE
www.powerpoint.vn

15


3.Một số hàng đợi cơ bản
3.1 M/M/1 : Hàng đợi Markov đơn giản nhất

Tiến trình đến : Là tiến trình Poisson
- Xác suất để 1 khách hàng đến hệ thống trong khoảng thời gian [t, t+Δt] là λΔt

-

Xác suất để không có khách hàng nào đến hệ thống trong khoảng thời gian [t,t +Δt] là (1-λΔt)

- Xác suất để có n khách hàng đến hệ thống trong khoảng thời gian t (s) là :

- Số khách hàng trung bình đến hệ thống trong t(s) là : n=λ.t

PAGE
www.powerpoint.vn

16


3.Một số hàng đợi cơ bản
3.1 M/M/1 : Hàng đợi Markov đơn giản nhất

Thời gian phục vụ là các biến ngẫu nhiên tuân theo phân bố mũ nghĩa là :


-XS dịch vụ được hoàn thành trong khoảng thời gian [t, t+Δt] là : μΔt

-XS để không có 1 dịch vụ nào được hoàn thành trong khoảng thời gian [t, t+Δt] là

μΔt
μ là tốc độ
dịch vụ trung bình
của server
1/μ thời gian dịch vụ TB cho mỗi khách hàng của server
PAGE
www.powerpoint.vn

17


3.Một số hàng đợi cơ bản
3.1 M/M/1 : Hàng đợi Markov đơn giản nhất

•

μ: mức dịch vụ trung bình

Độ hiệu dụng của hệ thống M/M/1 : U=1-p0=p

của một dịch vụ duy nhất

P=λ /μ

λ : Tốc độ đến của khách hàng


độ dài của hàng đợi
tại thời điểm khách hàng đó

•

đứng ở ngoài hàng đợi

Đối với khách hàng thứ k:
thời gian lưu trú trong hệ thống được tính bằng:

R=R+SQ.

thời gianđược phục vụ

PAGE
www.powerpoint.vn

18


3.Một số hàng đợi cơ bản
3.2 Các hàng đợi nhiều trạm dịch vụ: M/M/m

•

Xét với 2 sever
Sever

Xử lý


Sever

thời gianđược phục vụ

Thời gian thường trú

R=S+1/2 SpQ

độ dài của hàng đợi
tại thời điểm khách hàng đó

Độ hiệu dụng

đứng ở ngoài hàng đợi

của hệ thống

2
Thời gian phục vụ thực tế phụ thuộc vào xác suất bận của server R=S+p .R

 

R= hay Q=

PAGE
www.powerpoint.vn

19



3.Một số hàng đợi cơ bản
3.3 Các hàng đợi nhiều trạm dịch vụ: M/M/m

 

Xét hệ thống đa server, có dạng như sau:p
R=

và

m

Q= , với m là số server của hệ.

 

Thời gian đáp ứng chính xác của các hệ thống đa server:

R=S[

C(m, p) là xác suất mọi server đều bận và yêu cầu gửi đến sẽ được đặt vào hàng xếp.

hàm Erlang C.
PAGE
www.powerpoint.vn

20



2.Một số hàng đợi cơ bản
3.4 Các hàng đợi có số khách hàng hạn chế M/M/m/N/N (hàng đợi đóng)

Limit

sever

Time chuẩn bị vào ( Z )
Time đợi để được phục vụ

N số khách hàng

S: Thời gian được phục vụ
 

Thời gian lưu trú trong hệ thống: R=
Thông lượng

Khi thời gian chuẩn bị vào ngắn nhất và bằng 0, ta có R max=

www.powerpoint.vn

m là số server của hệ.

PAGE

21


3.Một số hàng đợi cơ bản

3.5 Hàng đợi M/G/1
Khách hàng ra khỏi hệ thống trong khi được phục vụ

k phần còn lại của khách hàng trong hệ thống

Thời gian lưu trú trong hệ thống

: R=S+SQ-(1-k)ρS.
P: độ hiệu dụng

S: Thời gian được phục vụ

Q số khách hàng

của hệ thống

trung bình trong
hệ thống xếp hàng
www.powerpoint.vn

PAGE

22


3.Một số hàng đợi cơ bản
3.5 Các hệ thống có phản hồi

Tốc độ đến của KH


Thông lượng

P: độ hiệu dụng

tốc độ yêu cầu tới hàng đợi là: λ1 = λ+ pλ1

của hệ thống

Lượng khách đến thăm sever là :
Yêu cầu dịch vụ là D = V.S
S: Thời gian được phục vụ

Thời gian lưu trú trong hệ thống :
PAGE
www.powerpoint.vn

23


4.1 Mạng các hàng đợi
4.1 Mạng các hàng đợi hàng đợi

Mạng đóng: Mạng đóng không kết nối với thế giới bên ngoài
trong khoảng thời gian khảo sát .do đó số khách hàng
trong hệ thống là cố định

Mạng mở:

Mạng mở thì nhận và gửi khách hàng ra bên ngoài
trong thời gian khảo sát, do vậy số khách hàng

trong hệ thống luôn biến đổi theo thời gian.

PAGE
www.powerpoint.vn

24


4.Mạng các hàng đợi
4.2Định lý đến

Đối với một hệ thống hàng đợi đóng có N công việc, thời gian lưu trú trung bình trong mỗi hàng đợi là
R=S+SQ(N-1).

Sevice
(thời gianđược phục vụ)
Thời gian lưu trú

Trong đó Q(N-1) :độ dài trung bình hàng đợi
Khi có N-1 công việc trong mạch.

PAGE
www.powerpoint.vn

25