Mở Đầu
Chúng ta đang sống ở thế kỷ 21 là thế kỷ bùng nổ thông tin. Do con ngời
ngày càng có nhu cầu cao hơn về việc trao đổi thông tin. Để đáp ứng yêu cầu đó
thì các mạng tốc độ cao cũng đã phát triển rất nhanh, trong đó có hai khía cạnh tơng đối quan trọng là phơng pháp tính toán và chu kỳ phát triển sản phẩm. Điều
đó đã làm tăng nhanh tốc độ truy xuất các luồng thông tin khác nhau trên mạng,
việc nhận và gửi các thông báo Email sẽ trở nên nhanh hơn và rẻ hơn rất nhiều.
Ngày nay các mạng và các hệ thống thông tin truyền đợc thiết kế và xây dựng
tinh vi hơn trớc. Nhằm đáp ứng nhu cầu xử lý, chuyển tải thông tin của xã hội thì
một nhiệm vụ hết sức quan trọng đặt ra là phải phân tích, đánh giá đợc hiệu năng,
chất lợng cũng nh độ tin cậy của các hệ thống đó.
Lý thuyết xếp hàng có nguồn gốc từ đầu thế kỷ 20 với các nghiên cứu khởi
đầu của nhà toán học ngời Đan Mạch A.K.Erlang. Ngày nay lý thuyết xếp hàng
đợc dùng rộng rãi cho các ứng dụng khác nhau, hơn nữa nó vẫn đang đợc tiếp tục
nghiên cứu và phát triển. Để đánh giá hiệu năng của các mạng viễn thông ta có
thể chọn một trong hai phơng pháp: phơng pháp đo lờng hoặc phơng pháp thống
kê. Trong thực tế, đánh giá hiệu năng các hệ thống bằng phơng pháp thống kê đã
chiếm một vai trò ngày càng quan trọng bởi vì nó có thể đánh giá các thông số
hiệu năng dựa trên các mô hình toán học của các mạng đang trong giai đoạn
nghiên cứu. Trớc khi đi xây dựng một hệ thống cụ thể thì việc đi đánh giá các
thông số hiệu năng là vô cùng quan trọng. ở đây ta sử dụng lý thuyết xếp hàng
để làm cơ sở toán học cho việc đánh giá hiệu năng của mạng. Chính vì thế nên
luận văn lấy tên: Xây dựng các mô hình phần mềm để đánh giá hệ thống xếp
hàng.

1


Luận văn đợc trình bày trong ba chơng tơng ứng với những nội dung sau:
Chơng I, trình bày sơ lợc về một số độ đo hiệu năng. Sau đó các mô hình
xếp hàng đơn tổng quát đợc trình bày. Từ các mô hình tổng quát đó áp dụng cho
các mô hình xếp hàng đơn cụ thể (nh mô hình xếp hàng M/M/1 , mô hình xếp

hàng M/M/2, vv..., ) cùng với việc khảo sát các khái niệm có liên quan về phân
phối dòng khách hàng đến (phân phối Poisson, ...), phân phối thời gian phục vụ
khách hàng (phân phối mũ, ...) và các công thức xác định các độ đo hiệu năng
của các hệ thống này. Phần cuối của chơng I là nghiên cứu về các hệ thống xếp
hàng dạng phi Markov, chẳng hạn nh hệ thống xếp hàng M/G/1 (có phân phối
thời gian phục vụ khách hàng tuỳ ý).
Chơng II, trình bày các nghiên cứu ở dạng tổng quát của các hệ thống xếp
hàng đó là mạng xếp hàng. Các phân tích đều tập trung vào các mạng xếp hàng
dạng Markov . Trong phần này chúng ta nghiên cứu cả mạng xếp hàng đóng và
mạng xếp hàng mở trong đó có đề cập đến một khái niệm mới trong lý thuyết
xếp hàng đó là nghiệm dạng tích (PFS - Product Form Solution). Để làm giảm
bớt đi khối lợng tính toán khi xác định các độ đo hiệu năng cho mạng xếp hàng
PFS đóng trong chơng II này cũng đã đa ra thuật toán phân tích giá trị trung bình
MVA (Mean Value Analysis).
Chơng III, thiết kế phần mềm đánh giá hiệu năng các mô hình xếp hàng.
Do thời gian hạn hẹp và cha có điều kiện tiếp cận đối tợng nghiên cứu đợc
tốt nên luận văn không thể tránh đợc các sai sót. Vì vậy rất mong nhận đợc sự

2


thông cảm và góp ý của các thầy cô giáo và các bạn bè sinh viên để luận văn đợc
hoàn thiện hơn.
Tôi xin chân thành cảm ơn sự hớng dẫn và giúp đỡ nhiệt tình của thầy giáo
- ThS. Lê Anh Ngọc. Tôi cũng xin đợc cảm ơn toàn thể bạn bè trong lớp đã tạo
mọi điều kiện về thời gian và góp nhiều ý kiến quý báu trong quá trình thực hiện
luận văn này.

Vinh, ngày 5 tháng 5 năm 2003


3


Chơng I. Các hệ thống xếp hàng đơn
1.1. các thông số hiệu năng:
Trớc khi đi vào cụ thể các hệ thống xếp hàng đơn, chúng ta cần phải
nghiên cứu qui luật xuất hiện của khách hàng, tính toán các thông số hiệu năng
để xác định mức độ xếp hàng vừa phải để không gây tắc nghẽn hay bất bình với
các khách hàng đồng thời đảm bảo đợc hệ số sử dụng một cách hợp lý. Để thực
hiện đợc nhiệm vụ đó ta cần phải đa ra đợc các thông số hiệu năng, sau đó trên
cơ sở các thông số đó có thể chọn ra đợc phơng án thiết kế hệ thống tối u. Các
chỉ tiêu đánh giá hay các thông số hiệu năng quan trọng thờng dùng khi phân tích
mạng đó là:
a) Tốc độ đến của khách hàng ( - arrival rate):
=

A
, trong đó A - số các khách hàng đến hệ thống
T

T - thời gian quan sát (thời gian đo)
Và đơn vị đo là: Khách hàng/ đơn vị thời gian.
b)Thông lợng (throughput) của hệ thống xếp hàng hay là tốc độ trung
bình của khách hàng chuyển qua hệ thống.
Throughput = X =

C
(với C là số khách hàng hoàn thành dịch vụ).
T


Dạng biểu diễn khác: Throughput = Y =



à (n) pn (khách hàng/giây), trong đó pn
n =1

là xác suất trạng thái cân bằng khi hệ thống có n khách hàng trong hệ thống.
c) Khách hàng trung bình trong hệ thống xếp hàng:


Q = n = np n (Khách hàng).
n =1

4


Dạng biểu diễn khác: Q =


T

trong đó: - tổng thời gian thờng trú của tất cả

khách hàng đã hoàn thành dịch vụ.
d) Thời gian đáp ứng (R - Response time)
R = =


C


( giây)

(với là tổng thời gian thờng trú của tất cả các khách hàng đã hoàn thành dịch
vụ)
Cách biểu diễn khác: R = S + W

(thời gian thờng trú bằng tổng thời gian

phục vụ và thời gian mà khách hàng đó phải đợi trớc khi đợc phục vụ)
e) Thời gian phục vụ (S - Server time): S =

B
, trong đó B - tổng thời
C

gian hệ thống bận trong khoảng thời gian T. Đại lợng này không phải là tốc độ
mà nó biểu diễn tổng thời gian trung bình để hoàn thành phục vụ một yêu cầu
đến.
f) Thời gian đợi (W - Waiting time): W = SQ, trong đó Q - số các khách
hàng trung bình trong hàng đợi và S - thời gian phục vụ.
g) Xác suất để hệ thống xếp hàng là rỗng: P0
h) Độ hiệu dụng hay là xác suất để hệ thống xếp hàng là không rỗng và
tất cả các sesver bận (trờng hợp nhiều sesver)
U = 1 - p0
i) Độ hiệu dụng trung bình (U - utilitization): U =

B
= S
T


j) Xác suất để tất cả các kênh phục vụ đến bận hay xác suất để 1 khách
hàng bị từ chối là PN hay P[queueing] (trong đó N - kích thớc hệ thống)
1.2 Cấu trúc hệ thống xếp hàng:
1.2.1 Mô hình xếp hàng:

5


Mô hình xếp hàng đơn giản nhất là chỉ có một hàng đợi đơn:
server
Queue
INPUT

OUTPUT

Hình I.1: Một mô hình hệ thống xếp hàng

Trong hệ thống xếp hàng này các khách hàng vào từ phía bên trái và ra
khỏi phía bên phải. Vòng tròn miêu tả server ( hệ thống phục vụ). Ví dụ trong
dãy quầy thanh toán tiền trong một siêu thị, server sẽ là các nhân viên thao tác
máy đếm tiền. Trong mạng dữ liệu, server là phơng tiện truyền dẫn liên kết đầu
ra, các đờng dây, trung kế,CPU,.. còn hàng chữ nhật mô tả hàng đợi (queue) mà
chứa các khách hàng trớc khi đợc vào phục vụ tại server. Đôi khi ta có thể gọi hệ
thống nh vậy là một hệ thống xếp hàng hay một hàng đợi phụ thuộc vào từng
hoàn cảnh cụ thể. Trong trờng hợp đó, khi dùng từ hàng đợi ta hiểu là toàn bộ hệ
thống xếp hàng bao gồm các yêu cầu đang đợi dịch vụ và các yêu cầu đang đợc
phục vụ. Do đó thuật ngữ độ dài hàng đợi đợc hiểu là số các yêu cầu đang đợi
cộng thêm các yêu cầu đang đợc phục vụ.
1.2.2 Các đặc trng của 1 mô hình xếp hàng:

Để phân tích 1 trung tâm hàng đợi, ta cần phải chỉ rõ các đặc trng sau:
- Tính chất của dòng khách hàng đến hàng đợi hay phân phối xác suất của
khoảng thời gian giữa các yêu cầu đến vào hàng đợi.
- Phân phối xác suất của khoảng thời gian dịch vụ cho mỗi yêu cầu trong
hàng đợi.
- Số các server tại hàng đợi.
- Dung lợng bộ đệm hay dung lợng lu trữ tại hàng đợi.

6


- Tổng số các yêu cầu hiện có mặt tại hàng đợi.
- Các kiểu dịch vụ.
Một số các phân phối thời gian chung đợc sử dụng để mô hình hoá khoảng
thời gian giữa các khách hàng đến và đợc phục vụ bao gồm các phân phối sau:
+) Phân phối xác định (D - Determistic): Khoảng thời gian giữa 2 khách
hàng đến hay rời liên tiếp bằng nhau.
+) Phân phối mũ (M - Exponential): khoảng thời gian giữa 2 khách hàng
hoàn toàn độc lập với khoảng thời gian đến trớc đó. Do đó các khoảng thời gian
là không tơng quan với nhau về thời gian. Và biến ngẫu nhiên mô tả các khoảng
thời gian đó có phân phối mũ (tuân theo luật chỉ số). Quá trình ngẫu nhiên tơng
ứng đợc gọi là quá trình có tính chất không nhớ (đây là đặc trng của một quá
trình ngẫu nhiên Poisson). Phân phối này đợc sử dụng khắp nơi trong các mô
hình xếp hàng của các máy tính.
+) Phân phối đều (U - Uniform): Các khoảng thời gian đến và khoảng
thời gian dịch vụ đợc giới hạn bởi một số các giá trị hữu hạn. Các đặc trng xếp
hàng nằm giữa các phân phối mũ và phân phối xác định.
+) Phân phối tổng quát (G - General): Các khoảng thời gian đến hay rời
không đợc đặc trng bởi bất kỳ một phân phối nào bởi vì quá trình đến hay rời
là một quá trình hoàn toàn tuỳ ý.

1.2.3 Trật tự phục vụ khách hàng
Hầu nh các hệ thống xếp hàng ngày nay đợc sử dụng để phục vụ các khách
hàng theo trình tự mà chúng tới. Trình tự phục vụ đó gọi là FIFO (First in First
out) hay FCFS (Fist Come First Server). Bên cạnh đó còn một số kiểu dịch vụ
khác nh LIFO, FIFOPR, ...

7


Theo kí pháp của Kendall một trung tâm xếp hàng hay nói chung là hàng
đợi đợc phân loại qua các kí hiệu của bộ mô tả Kendall tổng quát có dạng:
/ / m / / N /Q

Trong đó:
. - phân phối xác suất của khoảng thời gian giữa các khách hàng đến
hàng đợi.
. - phân phối xác suất của khoảng thời gian yêu cầu để phục vụ cho các
khách hàng trong hệ thống xếp hàng.
. m - số các server trong hệ thống xếp hàng.
. - kích cỡ bộ đệm hoặc dung lợng lu trữ tại một hệ thống xếp hàng.
. N - số lợng khách hàng cho phép chuyển qua hệ thống.
. Q - phơng thức phục vụ (FIFO, LIFO)
Qui ớc: khi và N là vô hạn và kỷ luật xếp hàng là FIFO khi đó bộ mô tả
có thể đợc rút ngắn lại thành M/M/m.
1.3 Các hệ thống xếp hàng đơn:
1.3.1 Hệ thống xếp hàng M/M/1.
Hệ thống M/M/1 này có 2 đặc trng chủ yếu:
- Có tiến trình đến là một quá trình phân phối Poisson.
- Hệ thống phục vụ (Server) có thời gian dịch vụ là một biến ngẫu nhiên
phân phối mũ.

Tiến trình Poatxông

Server phân phối mũ
Queue

INPUT

OUTPUT

Hình I.2: Hệ thống xếp hàng M/M/1

8


Mô hình này rất tiện dụng và hợp lý để mô phỏng cho nhiều hệ thống
trong thực tế. Vì thế, chúng ta đi khảo sát 2 đặc trng của mô hình này:
1.3.1.1 Quá trình Poisson:
Quá trình Poisson là một quá trình ngẫu nhiên cơ bản nhất nó thờng đợc áp
dụng cho kiểu đáp ứng của hàng đợi. Ngoài ra nó cũng đợc sử dụng rộng rãi
trong lu lợng thoại cũng nh trong việc định giá trị của chuyển mạch thoại và
mạng máy tính.
Chúng ta xem xét đặc tính của quá trình này nh sau: giả sử trục thời gian
đợc chia thành vô số các khoảng thời gian nhỏ có độ rộng là t ( t 0 ) và xác
suất của 1 khách hàng đến trong một khoảng thời gian nh vậy tỷ lệ với độ dài t
với một hằng số tỷ lệ (mô tả tốc độ đến của quá trình đến).

t
t + t

t


Hình I.3: Trục thời gian đợc phân chia

Khi đó, điều kiện để nhận biết một quá trình Poisson gồm các tính chất:
1. Tính đơn nhất.
Prob(có một khách hàng đến trong đoạn[t,t+t])=t+(t)
Prob(không có khách hàng nào đến trong đoạn [t,t+t] )= 1- t+(t)
Prob(có hơn 1 khách hàng đến trong đoạn [t,t+t] ) = (t)
(ở đây (t) - là một vô cùng bé của t và t <<1)

9


Một dòng các khách hàng đến có tính đơn nhất nếu trong một khoảng thời
gian đủ nhỏ hầu nh chắc chắn là có không quá 1 khách hàng xuất hiện.
2. Tính không nhớ (memoryless): Một dòng khách hàng đến có tính
không nhớ nếu xác suất xuất hiện x khách hàng trong khoảng thời gian [t,t+t]
không phụ thuộc vào việc trớc thời điểm t đã có bao nhiêu khách hàng đến. Nh
vậy có nghĩa là biến cố có x khách hàng đến với hệ thống trong khoảng thời gian
[t,t+t] và biến cố có x khách hàng đến trong khoảng thời gian [t,t+t] mà trớc
đó đã có k khách hàng đến là 2 biến cố độc lập với nhau với mọi k:
Px(t, t)= Px(t, t/ đã có k khách hàng đến trớc đó), với mọi k.
Dòng khách hàng nh vậy có xác suất xuất hiện x khách hàng trong khoảng thời
gian [t,t+t] đợc tính theo công thức Poisson sau:
a (t , t ) x e a ( t ,t )
Px(t, t)=
x!

Trong đó a(t,t) là số khách hàng đến trung bình trong khoảng thời gian [t,t+t].
3. Tính dừng: Dòng các khách hàng có tính dừng nếu xác suất xuất hiện x

khách hàng trong khoảng thời gian t không phụ thuộc vào điểm đặt của khoảng
thời gian đó:
Px(t, t)=Px(t)
Nói cách khác, mật độ dòng khách hàng là không đổi: a(t)=t và khi đó:
(t ) x e t
Px(t)=
x!

(với đợc gọi là số khách hàng đến trung bình trong một đơn vị thời gian hay
còn gọi là tốc độ đến trung bình).
Nhận xét:

10


Từ đó ta thấy, quá trình Poisson cũng tơng tự nh quá trình tung đồng xu.
Mỗi đoạn t tơng ứng giống nh một lần tung đồng xu với t là xác suất của có
một khách hàng đến trong đoạn thời gian này (tơng ứng mặt ngửa của đồng xu
xuất hiện) và 1 - t là xác suất để không có khách hàng đến trong đoạn t (tơng ứng với mặt sấp của đồng xu xuất hiện). Khi các khoảng chia t0 , ta sẽ
có tiến trình Poisson thời gian liên tục. Qua tính tơng tự với quá trình tung đồng
xu, ta có thể thấy rằng các khách hàng đến là độc lập với các khách hàng khác và
vào một thời điểm bất kỳ chỉ có tối đa 1 khách hàng đến hệ thống vì chúng chỉ là
kết quả của một số rất lớn các phép thử độc lập tung đồng xu.
Ví dụ: Một trong những ứng dụng cơ bản nhất của quá trình Poisson trong
truyền thông là mô hình các cuộc gọi đến một tổng đài điện thoại. Mỗi cuộc gọi
điện thoại có thể đợc mô hình nh là một quá trình Poisson. Chúng đợc kết hợp
thành một dòng các cuộc gọi có phân phối Poisson tại tổng đài. Mô hình này rất
phù hợp cho việc mô hình hoá việc kết hợp của một số lớn những ngời dùng độc
lập theo cách này. Tuy nhiên không phải bao giờ nó cũng có hiệu lực. Ví dụ nh
trờng hợp mà tổng đài quá tải. Các cuộc gọi bị tắc nghẽn (đó là trờng hợp đa đến

từ những lần thử gọi lặp đi lặp lại của ngời sử dụng để đợc thông tuyến) hay có
những sự tơng quan giữa một cuộc gọi của cá nhân gọi điện thoại. Trong trờng
hợp này mô hình trở nên rất phức tạp.
1.3.1.2

Các đặc trng của quá trình Poisson

a. Kỳ vọng của quá trình Poisson
Giả sử n là số các khách hàng đến trung bình trong một khoảng thời gian
t. Khi đó:


n = nPn (t )
n =0

11


Trong đó Pn ( t ) là xác suất để có khách hàng đến hệ thống tại thời điểm t là n và
pi , j ( t ) là xác suất để hệ thống có i khách hàng chuyển đến có j khách hàng trong

khoảng thời gian t giây.
Thay giá trị của Pn (t) vào biểu thức trên, ta có:
n




(t ) n t
( t ) n

(t ) n +1
( t )
n = n
e = e t n
= e t
= e t t
= e t te t = t
n!
(n 1)!
n!
n=0
n =1
n =0
n = 0 n!


Do vậy: n =t
b. Phơng sai của quá trình Poisson:
Đối với phơng sai (độ phân tán), đầu tiên chúng ta tính:


E ( n( n 1)) = n(n 1)
n =0


(t ) n t
(t ) n t
e =
e
n!

n = 2 ( n 2)!

(t ) n
= e t (t ) 2 e t = (t ) 2
n!
n =0


E ( n( n 1)) =e t (t ) 2

suy ra:
E ( n( n 1)) = E (n 2 ) E (n) = (t ) 2 hay E ( n 2 ) = (t ) 2 + t

Ta cũng dùng định nghĩa phơng sai của số khách hàng n là:
n2 = E (n n) 2 = E (n 2 ) + E (n) 2 2nE (n) = E (n 2 ) n 2

Do vậy:

n2 = (t ) 2 + t (t ) 2 = t

Nh vậy, kỳ vọng và phơng sai của phân phối Poisson đều là t
1.3.1.3

Qui luật về thời gian giữa các khách hàng đến với hệ thống

Ta xem xét về phân phối khoảng thời gian giữa các khách hàng đến với hệ
thống. Đối với một quá trình đến là dòng Poisson thì các khoảng thời gian đó là
các biến ngẫu nhiên có phân phối mũ độc lập với nhau. Có thể nhận thấy điều

12



này là đúng. Thật vậy, gọi X - biến ngẫu nhiên liên tục biểu diễn thời gian giữa
các khách hàng đến, ta có:
P(X t) =1-P( X> t)
P(X t) = 1-P0(t)
P(X t) = 1 - e t
Nếu ta lấy vi phân của đẳng thức trên, ta có hàm mật độ của biến ngẫu nhiên X
(thời gian giữa các khách hàng đến): f (t ) = e t
Đây chính là hàm mật độ của biến ngẫu nhiên có phân phối mũ.
Nhận xét:
- Một biến ngẫu nhiên phân phối mũ chỉ là một biến ngẫu nhiên liên tục
mà có tính không nhớ. Nói một cách không chặt chẽ lắm thì điều đó có nghĩa là
quá khứ của biến ngẫu nhiên không giúp đợc gì cho việc đoán trớc tơng lai
của nó.
- Dới dạng quá trình đến Poisson, tính không nhớ có nghĩa là phân phối
thời gian cho tới sự kiện tiếp theo là giống nhau tại bất kỳ thời điểm quan sát nào.
Để chứng minh rằng điều này là đúng, ta trở lại với sự lý giải quá trình
Poisson thông qua quá trình tung đồng xu trong một khoảng thời gian vô cùng
bé. Khi thời gian tiếp tục trôi đi ta sẽ có đợc một số rất lớn các lần tung đồng xu.
Với quá trình Poisson trong hoàn cảnh này, dễ dàng thấy rằng phân phối thời
gian cho đến kết quả tiếp theo không phụ thuộc vào bất kỳ kết quả nào vừa mới
xảy ra. Có nghĩa là không thể đoán trớc đợc khi nào sẽ tung đợc mặt ngửa trong
khi biết rằng vừa mới tung đợc mặt ngửa.
1.3.1.4

Tính chất Markov của quá trình ngẫu nhiên

13



Tính không nhớ đợc xem xét một cách chính xác hơn nh là tính Markov.
Một cách trực quan, nó nói rằng ta có thể đoán trớc trạng thái tơng lai của hệ
thống dựa trên trạng thái hiện tại cũng nh nếu ta có tập các trạng thái có thể có
của quá khứ.
Dới dạng thời gian T là biến ngẫu nhiên không âm liên tục, tính chất
Markov có thể đợc biểu diễn: P(T>t + t0/T>t0) = P( T> t) với mọi t, t0 > 0
Dới dạng một biến ngẫu nhiên rời rạc X (Tn ) chúng ta có thể phát biểu rằng:
P(X(tn+1)= xn+1/ X(tn)=xn, X(tn-1) = xn-1, ..., X(t1) = x1) =P(X(tn+1) = xn+1/ X(tn)=xn)
với ti là một dãy tăng đều và xn nhận một số giá trị từ không gian trạng thái rời
rạc.
Các hệ thống Markov đều là các hệ thống không nhớ. Điều này khiến
chúng tơng đối đơn giản khi phân tích do khi ta mô tả trạng thái của hệ thống ta
không cần đa vào các giá trị thời gian tính từ khách hàng vừa đến hoặc thời gian
dịch vụ đang thực hiện. Khi dòng khách hàng đến không phải là dòng Poisson
hoặc thời gian dịch vụ không phải là phân phối mũ thì ta mới phải quan tâm tới
các giá trị đó. Điều này khiến ta biết đợc hành vi của hệ thống xếp hàng đơn
ngay cả dới các điều kiện không tầm thờng.
1.3.1.5

Thời gian dịch vụ phân phối mũ

Trong một hệ thống xếp hàng M/M/1, thời gian dịch vụ là các biến ngẫu
nhiên độc lập có phân phối mũ. Có nghĩa là chúng xuất hiện theo mật độ xác suất
àe-àt với à là tốc độ dịch vụ trung bình là 1/à là thời gian dịch vụ trung bình. Nh
đã xét ở trên, hệ thống phục vụ kiểu này là không nhớ và do vậy rất tiện dụng khi
phân tích.
Vậy một server phân phối mũ trên thực tế nh thế nào? Nó đợc xem là mô
hình hợp lý cho việc mô hình hoá thời gian của các cuộc gọi điện thoại. Nhng nó


14


cũng đợc dùng trong các tình huống mà cơ sở hạ tầng vật lý cho việc sử dụng
các thiết bị là yếu dần( đợc sử dụng để mô hình tuổi thọ của các thiết bị vật lý).
Ví dụ: thời gian chuyển các gói tin có độ dài cố định trong mạng máy tính thờng
đợc mô hình hoá bởi biến ngẫu nhiên phân phối mũ.
1.3.1.6

Phơng pháp phân tích hệ thống xếp hàng M/M/1:

Nh đã biết, khi xét quá trình Poisson ta có 2 biến cố xảy ra:
- Xác suất để một khách hàng đến trong đoạn [t,t+t] là t
- Xác suất để không có khách hàng nào đến trong đoạn [t,t+t] là (1- t)
Với hệ thống M/M/1 thêm vào đó ta có 2 biến cố nữa:
- Xác suất để một dịch vụ hoàn thành trong đoạn [t,t+t] là àt
- Xác suất để không có dịch vụ hoàn thành trong đoạn [t,t+t] là(1-àt)
Tơng tự nh trớc đây, ta định nghĩa:
Gọi Pn(t) là xác suất để có số khách hàng đến tại thời điểm t là n và gọi p i,j
(t) là xác suất để hệ thống từ i khách hàng chuyển thành có j khách hàng trong
khoảng thời gian t giây.
Trong khi trớc đây, trạng thái của hệ thống đợc xem là số các hàng đến với
hệ thống theo dòng Poisson. Thì giờ đây số các khách hàng trong hệ thống lại
bao gồm cả khách hàng đang đợc dịch vụ. Ta có:
Pn (t + t ) = Pn (t ) p n ,n (t ) + Pn 1 (t ) p n 1,n (t ) + Pn +1 (t ) p n +1,n (t )

Phơng trình này thể hiện rằng, hệ thống có thể rơi vào tình huống với nkhách hàng đến hệ thống tại thời điểm (t+t) trong khi hoặc đã có n-1 hoặc n
hoặc (n+1) khách hàng tại thời điểm t. Do vậy đây là quá trình huỷ và sinh nên
chúng chỉ là các khả năng. Tại trạng thái 0 (thời điểm t0) ta có phơng trình sau:
P0 (t + t ) = P0 (t ) p 0,0 (t ) + P1 (t ) p1, 0 (t )


15


Ta sẽ thay thế các biểu thức trớc đây về xác suất của các biến cố khác nhau
trong khoảng thời gian [t,t+t] vào phơng trình trên, ta có:
Pn (t + t ) = Pn (t )(1 t )(1 àt ) + Pn 1 (t )(t ) + Pn +1 (t )( àt )
P0 (t + t ) = P0 (t )(1 t ) + P1 (t )( àt )

Tơng tự trớc đây, bằng cách nhân các biểu thức sắp xếp lại và cho t 0, ta có:
dPn (t )
= ( + à ) Pn (t ) + Pn 1 (t ) + àPn +1 (t ), n 1
dt
dP0 (t )
= P 0 (t ) + àP 1 (t )
dt

Các phơng trình vi phân này mô tả sự thay đổi theo thời gian của các xác suất
trạng thái của hệ thống xếp hàng M/M/1.
Tính toán các xác suất trạng thái trong trờng hợp cân bằng:
Chúng ta có thể tính toán đợc các xác suất ở trạng thái cân bằng của bất kỳ
hệ thống xếp hàng nào với một số lợng các trạng thái hữu hạn theo cách sau:
Thuật toán
Bớc1: Tơng tự với mỗi trạng thái, ta viết một phơng trình cân bằng toàn cục của
nó. Do vậy ta có N phơng trình tuyến tính với N cha biết. Chú ý rằng, bất kỳ một
phơng trình nào trong tập các phơng trình đó cũng d thừa và có thể thay thế bằng
một phơng trình:
p 0 + p1 + p 2 + ... + p N = 1 (phơng trình chuẩn hoá)

Bớc2: Sau đó, nghiệm của tập N phơng trình tuyến tính trên có thể tìm ra bằng

các phơng pháp số thông thờng.
Chú ý:
Việc tính toán các xác suất trạng thái là rất quan trọng vì rất nhiều độ đo
hiệu năng quan trọng phụ thuộc vào các xác suất trạng thái.

16


Trên thực tế cho thấy, cách tiếp cận này là rất khó vì thông thờng các mô
hình xếp hàng có không gian các trạng thái là rất lớn nên các tính toán bằng các
phơng pháp số thông thờng là khó có thể thực hiện đợc.
Bây giờ ta xét một hệ thống xếp hàng M/M/1 cụ thể hơn theo cách nh
trên.
1.3.1.7

Công thức Little

Chúng ta hãy xem xét một kết quả đơn giản đợc ứng dụng rộng rãi trong
nhiều tình huống trong thực tế, đó là công thức Little. Công thức này thiết lập
mối quan hệ giữa các đại lợng:
n - số khách hàng trung bình trong hệ thống xếp hàng
- tốc độ đến trung bình của các khách hàng tới hệ thống xếp hàng.
- thời gian đợi trung bình của mỗi khách hàng cho tới khi đợc phục vụ
xong (chính là tổng thời gian đợi để đợc phục vụ và thời gian phục vụ).
Khi đó:

n =

Nhận xét:
Công thức này còn đợc áp dụng cho chỉ riêng hàng đợi (không có server):

nQ = Q ( trong đó nQ , Q là các đại lợng tơng tự nh trên đối với hàng đợi).

Công thức Little đã có trớc khi đợc phát biểu và chứng minh bởi J. D. C
Little. Theo kí pháp Little đa ra luật đó thờng đợc viết dới dạng: L = W
(L - độ dài hàng đợi, W thời gian đợi)
Để tính thời gian đợi trung bình trong một hệ thống xếp hàng M/M/1.
Ta có :
Do vậy:

n=


1
=

1/ à
1

17

(theo công thức Little)


Nh đã biết, dòng vào một hệ thống xếp hàng M/M/1 là dòng Poisson, vậy
câu hỏi đặt ra là dòng khách hàng sau khi đợc phục vụ sẽ có tính chất gì? Theo
Burke (1956) thì cũng chính là một quá trình Poisson. Định lý Burke phát biểu
rằng: Dòng khách hàng sau khi rời khỏi hệ thống xếp hàng M/M/1 trong trạng
thái cân bằng cũng là dòng Poisson.
1.3.1.8 Tính toán chi tiết với hệ thống xếp hàng đơn (M/M/1)
Để hiểu đợc dễ dàng hơn thì trớc hết chúng ta đi xem xét một quầy bán

hàng tạp phẩm. Khi bạn đến cửa hàng để mua một đồ gì đó? Muốn đợc phục vụ
thì bạn phải chờ để những ngời đến trớc bạn đợc phục vụ xong. Lúc đó thời gian
phục vụ trung bình sẽ đúng bằng S.
Thời gian ở lại cửa hàng của bạn là R (thời gian thờng trú bằng số thời
gian phục vụ khách hàng đến trớc bạn cộng với thời gian phục vụ riêng bạn khi
bạn đợc phục vụ).
Khi đó thời gian c trú đợc viết chính thức bằng
R = S + SQ (1)
Hay

R = S + W (2)

Sử dụng Q = XR ta có:

R = S + S(XR)

Giải (3) chúng ta có kết quả R là:

R=

S
1 ( XS )

(3)
(4)

Chúng ta còn có thể làm đơn giản hơn biểu thức trên hơn nữa. Nếu chúng ta sử
dụng phiên bản khác của qui luật Little thay U = XS. Khi đó kết quả cuối cùng
là:


R=

S
1U

(5)

Chú ý: ở trong biểu thức trên thì thời gian phục vụ trung bình và thông lợng là
các đại lợng có thể đo đợc trực tiếp.

18


- Nếu nhân cả 2 vế của biểu thức trên với thông lợng X thì khách hàng
trung bình trong hệ thống sẽ là:
Q=

U
1U

(6)

- Nếu nhân cả 2 vế của biểu thức trên với thời gian phục vụ trung bình thì
ta có biểu thức cho thời gian đợi là:
W =

SU
1U

(7)


VD1: Phép đo của việc gửi các gói tin vào cổng của mạng trung bình là 125 gói
(PPS) với thời gian phục vụ trung bình là 2ms. Từ thông tin này chúng ta có thể
xác định theo chế độ làm việc riêng biệt của cổng vào
Performance metric
Thông lợng trung bình, X
Thời gian phục vụ, S
Sử dụng, U = XS
Thời gian trung bình gửi gói tin trong

Value
125
2
25
2.66

Unit
PPS
Ms
Percent
ms

cổng vào, R
Số trung bình trong cổng vào, Q

0,33

Pkts

Ví dụ 2: Cho thời gian phục vụ trung bình là S = 1 giây và cho thời gian quan sát

là 2 giây. Tìm thời gian đáp ứng và chiều dài trung bình của hàng đợi?
Từ công thức ta có:
U = S
A 1
= = 0.5
T 2

trong đó:

=

Khi đó:

U = 0.5 * 1 = 0.5

Trung bình là 50% Server đang bận. Vậy thời gian đáp ứng là:

19


R=

S
1
=
= 2.0( s )
1 U 1 0.5

Và khách hàng trung bình trong hệ thống là:
Q=


U
= 1.0
1U

1.3.2 Hệ thống xếp hàng M/M/1 phụ thuộc trạng thái:
Cho tới bây giờ ta mới chỉ xem xét hệ thống xếp hàng có tốc độ và dịch vụ
là không đổi và ngoài ra chúng còn độc lập với nhau về số khách hàng trong hệ
thống. Tuy nhiên, trong thực tế có rất nhiều hệ thống xếp hàng đợc xây dựng
bằng cách cho tốc độ đến hoặc tốc độ dịch vụ phụ thuộc vào số các khách hàng
trong hệ thống:
Server phân phối mũ
Tiến trình Poátxông

n

(n)

à (n)

Hình I.4: Hệ thống xếp hàng M/M/1

Đối với hệ thống dạng này, ta cũng có thể thiết lập công thức với các xác
suất trạng thái. Thật vậy, bằng cách vẽ các biên giữa các cặp trạng thái và sau đó
cân bằng các xác suất luồng qua các biên, ta đợc tập các phơng trình cân bằng
cục bộ sau:
(i ) pi = à (i + 1) p i +1 , i = 0, n 1




pi +1 =

(i )
pi , i = 0, n 1
à (i + 1)

Từ đó ta tìm đợc xác suất cân bằng trạng thái:
n (i 1)
p n =
p0
i =1 à (i )



p0 =

1


n

1 +
n =1 i =1

(i 1)
à (i)

20



Xác định các độ đo hiệu năng
Các công thức trên cho phép ta xác định đợc xác suất trạng thái cân bằng.
Nhng câu hỏi đặt ra là tại sao nó lại quan trọng nh vậy? Lý do chủ yếu vì rất
nhiều các độ đo hiệu năng là các hàm của các xác suất trạng thái đó. Chẳng hạn
nh:
Thông lợng của hệ thống xếp hàng hoặc tốc độ trung bình mà tại đó các
khách hàng đợc chuyển qua:


Y = à (n) p n (số khách hàng/giây)
n =1

(ở đây n bắt đầu từ 1 do tại n = 0 thì hệ thống xếp hàng là rỗng nên không xét tới
thông lợng. Thông lợng trung bình là trung bình hệ số của các tốc độ dịch vụ à (n) mà các xác suất trạng thái - p n đợc xem nh các hệ số).

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


n = np n (số khách hàng)
n =1

(đây là một giá trị trung bình hệ số các khách hàng trong hệ thống xếp hàng với
các xác suất trạng thái đợc dùng nh các hệ số).
Vì đối với hệ thống xếp hàng M/M/1 có hàng đợi vô hạn thông lợng
trung bình bằng với tốc độ đến (theo định lý Burke), do đó ta có thể dùng công
thức Little để viết ra biểu thức đối với độ trễ thời gian trung bình.


n
= =

Y

np
n =1

n

(giây)



à ( n) p
n =1

n

21


(trong công thức trên, tử số có đơn vị là số khách hàng và mẫu số có đơn vị là số
các khách hàng trên giây nên có đơn vị là giây).
Độ đo hiệu dụng hay là xác suất để hệ thống xếp hàng là không rỗng và
server bận:
U = 1 p0

Nhắc lại rằng hệ thống M/M/1 có độ dài hàng đợi vô hạn và có các tốc độ đến và
dịch vụ không phụ thuộc trạng thái, khi đó, độ hiệu dụng:
U=




(vì) U = 1 p 0 = =
à
à

1.3.3 Hệ thống xếp hàng M/M/1/N:
Đây là hệ thống xếp hàng M/M/1 có dung lợng bộ đệm giới hạn có tối
đa N khách hàng trong hệ thống.Trờng hợp có N khách hàng trong hệ thống
(gồm cả một khách hàng đang đợc dịch vụ), khi đó nếu có một khách hàng đến
với hệ thống sẽ đợc xem là bị bỏ đi hoặc mất hoặc từ chối. Điều đó có
nghĩa là khách hàng đến thực sự bị mất đi và không quay trở lại lần sau đó
(không phản hồi lại). Nếu các khách hàng đó quay trở lại hệ thống sau đó thì quá
trình đến sẽ không phải là dòng Poisson nữa. Các tốc độ đến và dịch vụ phụ
thuộc vào trạng thái của hệ thống này là:
(n) = , n = 0, N 1, à (n) = à , n = 1, N

Bây giờ ta đi tìm các xác suất trạng thái, ta có:
n


p n = p 0 ,0 n N
à

22


p0 =

1


1



n =0 à
N

n

=


à


1
à

N +1

Xem xét công thức đối với p0 nhận xét thấy: Tử số cũng giống nh p0 trong
hệ thống xếp hàng M/M/1 có bộ đệm vô hạn (số khách hàng trong hệ thống là vô
hạn). Mẫu số giải thích rằng không gian trạng thái đã đợc rút gọn lại thành một
số hữu hạn các trạng thái. Chú ý rằng p n tăng hoặc giảm đều theo n còn phụ
thuộc tơng ứng vào các giá trị và à


Do vậy: p n = à



1

n


à


1
à

N +1

= n

1
,0 n N
1 N +1

Ví dụ: Nếu cần phải xác định xác suất tắc nghẽn ( PN hay P [queueing] )
là xác suất mà hệ thống xếp hàng là đầy. Khi đó số khách hàng bị từ chối trong 1
giây sẽ là PN . Trong đó PN đợc xác định:
pN = N

1
1 N +1

Nhận thấy, khi tăng dần thì khả năng từ chối của hệ thống sẽ cao hơn. Nếu =
1 phải dùng luật LHopital để xác định PN . Đối với hệ thống M/M/1 với bộ đêm
vô hạn, có thể không lớn hơn à do đó có thể không lớn hơn 1, dẫn đến hàng

đợi cứ tăng mãi. Với hệ thống M/M/1 có vùng đệm hữu hạn thì có thể lớn hơn
à, do vậy số khách hàmg nếu vợt quá giới hạn thì đơn giản là sẽ bị hệ thống từ
chối.

23


Nhận thấy rằng các phân tích hệ thống xếp hàng đơn có từ chối là tơng đối
dễ. Tuy nhiên đối với mạng các hệ thống xếp hàng có từ chối thì vấn đề sẽ trở
nên khó hơn.
Theo trên chúng ta đã đợc tìm hiểu hệ thống xếp hàng M/M/1 có dung lợng bộ
đệm giới hạn có tối đa N khách hàng trong hệ thống. Trờng hợp có N khách
hàng trong hệ thống, khi đó nếu có 1 khách hàng đến với hệ thống sẽ đợc xem là
bị bỏ đi hoặc bị từ chối. Điều đó có nghĩa khách hàng đến thực sự bị mất đi
và không quay trở lại lần sau đó. Còn bây giờ, chúng ta sẽ đi xem xét 1 hệ thống
ngợc lại hệ thống nh vậy. ở trong hệ thống này, trờng hợp nếu khách hàng đến
cha đợc dịch vụ thì khách hàng đó không bị mất đi mà sẽ quay trở lại để đợi đến
khi đợc phục vụ.
Trong hệ thống này đợc gọi là tốc độ chuyển động của khách hàng. Còn
khách hàng đến hệ thống cha đợc phục vụ phải quay lại hàng đợi là . Khách
hàng quay trở lại lập thành dòng 1 cùng với tốc độ mới đến của khách hàng,
nh vậy hàng đợi mới đến có kết quả sẽ là:
1 = + 1

hay

1 =


1

U = 1 S

Nh vậy độ hiệu dụng lúc này sẽ là:

Mặt khác ta có tốc độ đến thăm trung bình là:
V =

Và dịch vụ yêu cầu sẽ là:

1
1
D = VS

Từ đó ta có tổng thời gian gửi đi trong hệ thống sẽ bằng:
R=

D
1 D

24


1.3.4 Hệ thống xếp hàng M/M/ : (hệ thống xếp hàng có vô số server)
Trong hệ thống này, mỗi khách hàng đến sẽ đợc phục vụ bởi một server
với tốc độ phục vụ là à
Do đó, nếu có n khách hàng đến với hệ thống thì tốc độ phục vụ tổng cộng
của hệ thống lên tới nà .
ở đây, tốc độ đến và tốc độ phục vụ phụ thuộc trạng thái:
n = , , à n = à , (n = 0,1,2,...)
à

à
à




Hình I.4 : Hệ thống xếp hàng M/M/

Tơng tự nh trớc đây, ta đi xác định các xác suất trạng thái cân bằng. Khi đó theo
công thức xác định các xác suất tổng quát, ta có:
n (i 1)
p n =
p0
i =1 à (i )
p0 =

1


n

1 +
n =1 i =1

(i 1)
à (i )

Nên ta có:

25