LỜI NÓI ĐẦU
Ngày nay cùng với các lĩnh vực công nghệ khác, hệ thống viễn thông cũng
đóng một vai trò rất quan trọng trong sự phát triển kinh tế của mọi quốc gia trên thế
giới. Đi đôi với sự phát triển của xã hội nhu cầu trao đổi nhu cầu sử dụng và truyền
số liệu của con người cũng không ngừng tăng lên. Khi số lượng khách hàng tham
gia vào mạng thông tin ngày càng lớn còn tài nguyên của mạng thông tin thì có hạn,
khi đó dẫn đến hiện tượng tắc nghẽn mạng thông tin. Do đó việc tránh tắc nghẽn
trong mạng thông tin nói chung và đặc biệt là ở hệ thống chuyển mạch nói riêng là
một vấn đề quan trọng cần được giải quyết nhằm đảm bảo chất lượng cũng như hiệu
quả của hệ thống thông tin Vì vậy đòi hỏi các nhà thiết kế mạng phải lập ra các
chương trình để giải quyết những yếu tố gây ra hiện tượng nghẽn trong hệ thống
chuyển mạch như: thuật toán tính chiều dài hàng đợi trung bình, tính xác suất hệ
thống ở trạng thái rỗi, xác suất hệ thống ở trạng thái đang hoạt động, xác suất khách
hàng có khả năng được phục vụ cũng như không được phục vụ trong một chu kỳ
phục vụ, cách phục vụ đối với khách hàng….Với mong muốn tìm hiểu về vấn đề
này em lựa chọn đề tài
“Nghiên cứu lý thuyết xếp hàng và ứng dụng cho chuyển mạch gói
trong thông tin”
Do Ts.Phạm Văn Phước hướng dẫn
Bố cục đề tài của em gồm có 3 chương:
Chương 1: Tổng quan về lý thuyết xếp hàng
Chương 2: Mô hình toán phân tích hệ thống thông tin theo lý thuyết xếp
hàng
Chương 3:Ứng dụng lý thuyết xếp hàng trong chuyển mạch gói cho thông tin
Trong chương 2 đã trình bày phương pháp tính xác suất trạng thái hệ thống rỗi
và hệ thống bận với mô hình đơn hàng đơn trạm, đa hàng đơn trạm. Mô hình đơn
hàng đơn trạm là sự đơn giản hóa của mô hình đa hàng đơn trạm. Với phương pháp
tính toán dựa vào hàm sinh xác suất, ta tính được xác suất hệ thống bận và rỗi cùng
với một biên sai số nhất định.
Do điều kiện thời gian và sự hiểu biết có hạn nên đề tài của em không tránh
khỏi sai sót. Em kính mong nhận được sự chỉ bảo của các thầy cô, sự góp ý nhiệt

thực tế.
Cho dù lý thuyết xếp hàng phức tạp về mặt toán học thì việc phân tích hoạt
động của một hệ thống mạng sử dụng mô hình xếp hàng có thể dơn giản đi rất
nhiều. Để có thể áp dụng vào thực tiễn, chúng ta cần những kiến thức về khái niệm
thống kê cơ bản và biết về việc ứng dụng lý thuyết xếp hàng.
2
1.2. ĐỊNH NGHĨA VÀ
CÁC KHÁI NIỆM TRONG LÝ THUYẾT XẾP HÀNG
1.2.1 Định nghĩa
Lý thuyết xếp hàng là 1 phần của lý thuyết xác suất thống kê, nó được định
nghĩa là 1 bộ các quy tắc và luật (discipline) đề cập đến việc tắc nghẽn và phương
pháp giải quyết tắc nghẽn như: dự đoán độ trễ, trễ bé nhất, độ dài hàng đợi và số
server cần thiết trong 1 hệ thống thông tin. Lý thuyết hàng đợi có rất nhiều ứng
dụng từ việc nghiên cứu lưu lượng xe cộ trên đường phố, phương thức phục vụ
khách hàng (tại các siêu thị, bệnh viện, nhà băng, ) cho đến các hệ thống thông tin.
ở đây chỉ tập trung nêu lên các ứng dụng của lý thuyết hàng đợi trong các hệ thống
thông tin nói chung và trong các chuyển mạch gói nói riêng.
Bảng sau đây nêu lên mối quan hệ giữa một số mô hình liên quan với nhau:
Mô hình Định nghĩa
Xác suất Là luật nghiên cứu các sự kiện mà đầu ra của
chúng không xác định
Hàng đợi Là luật nghiên cứu tắc nghẽn và trễ khi các yêu
cầu phục vụ đến hệ thống một cách ngẫu nhiên
Teletraffic Là lý thuyết nghiên cứu các hàng đợi trong môi
trường thông tin thoại và dữ liệu
Thống kê Là luật nghiên cứu việc tập hợp dữ liệu trong các
môi trường xác suất bất kỳ
Viễn thông, truyền thông số liệu, các hệ thống máy tính là các ví dụ trong đó
các nguồn tài nguyên của chúng là thiết bị, đường truyền, thường bé hơn số thực
thể yêu cầu sử dụng chúng, điều này có nghĩa là 1 số user sẽ phải đợi cho đến khi

kết nối lớn hơn E. Số lượng khách hàng dôi ra cũng như khả năng hệ thông dôi ra ở
trên gọi là giá trị biến thiên V.
Bằng trực giác có thể thấy nếu lượng biến thiên số yêu cầu đến càng lớn thì trễ
sẽ càng lớn. Ví dụ nếu giá trị trung bình E là 20, và giá trị biến thiên là 2, thì tại một
số thưòi điểm lượng yêu cầu đến là 18, tại một số thời điểm khác lại là 22. ở đây
lượng quá tải là khá bé nên trễ chờ được phục vụ cũng bé. Tuy nhiên nếu giá trị
biến thiên tăng lên 10, thì lượng yêu cầu phải chờ tại một số thời điểm là 10, điều
này sẽ gây ra một trễ khá lớn. Biến thiên của các yêu cầu đến một hệ thống thông
tin được điều khiển bởi một luật được gọi là “ Phân bố thời điểm đến”
Ngoài việc phụ thuộc vào phân bố thời điểm đến của các yêu cầu, trễ thông tin
còn phụ thuộc vào hàm thời gian phục vụ của hệ thống. Tức phụ thuộc vào thời gian
phục vụ một yêu cầu là bao lâu, tuy nhiên thời gian phục vụ này là không giống
nhau đối với mọi yêu cầu. Sự phụ thuộc này được điều khiển bởi một luật gọi là “
4
Phân bố thời gian phục vụ”
a.Các thành phần của 1 hệ thống hàng đợi
• Môi trường hàng đợi là 1 hệ thống mà trong đó có tắc nghẽn xảy ra vì lượng
tài nguyên ít hơn số yêu cầu phục vụ đồng thời.
• Mô hình hàng đợi là 1 tóm tắt về toán học của 1 tình huống thực tế nào đó
với mục đích là cung cấp phương tiện biểu diển để định lượng hiệu suất của các
luồng thông tin ( Telephone call, Data packets, LAN token, ) khi đi qua các bộ
đệm.
Khi xem xét một hệ thống hàng đợi nói riêng mà một hệ thống tắc nghẽn nói
chung người ta quan tâm đến 7 tham số sau:
• Tổ hợp các loại yêu cầu khác nhau đến , nếu có nhiều hơn 1 loại yêu cầu đến
hệ thống hàng đợi. Ví dụ, tại một cửa hàng thì các khách hàng nữ tạo thành 1 loại
và khách hàng nam tạo thành 1 loại. Vì thời gian phục vụ của mỗi loại yêu cầu có
thể khác nhau
• Phân bố thời điểm đến của từng loại yêu cầu
• Độ lớn luồng lưu lượng đến của từng loại yêu cầu

- Tiến trình phục vụ là bất kỳ
- Chiều dài hàng đợi không giới hạn
Mô hình hàng đợi nghiên cứu trong luận văn là mô hình M/G/1
 M/D/1
- Tiến trình đến Markov, tham số λ
- Tiến trình phục vụ là bất biến , tức σ
2
y
=0
b. Một số kiểu phân bố thường gặp trong nhiều hệ thống viễn thông
• Kiểu “không nhớ” và có tên mã là M (cũng được gọi là kiểu phân bố theo
hàm mũ): phân bố này có nghĩa là xác suất mà một yêu cầu đến và đã đợi được T
phút phải đợi thêm Z phút nửa cũng bằng xác suất mà 1 yêu cầu khác vừa mới đến
cũng phải đợi Z phút (có nghĩa nó không nhớ rằng có 1 yêu cầu đã đợi được T phút
rồi). Điển hình của kiểu này là lưu lượng Internet (các gói đến 1 Router)
• Phân bố kiểu Erlange tầng r , tên mã là E[r]: giống quy luật các cuộc gói đến
tổng đài PSTN hàm xác suất Erlange
• Phân bố kiểu Hyperexponential tầng r, tên mã là H[r]
• Kiểu phân bố xác định, tên mã D ( quy luật đến đã biết trước)
• Một phân bố chung thường được gọi là G
c. Một số mô hình hàng đợi điển hình liên quan đến các hệ thống viễn thông
• Hệ thống hàng đợi 1 server với phân bố thời gian đến ngẫu nhiên
(memoryless), phân bố thời gian phục vụ ngẫu nhiên. Ví dụ, các hệ thống
Communication Servers như: hệ thông hộp thư thoại (Voice Mail Server) trong các
tổng đài PBX, hay một hệ thống thư điện tử trong các mạng LAN.
6
• Hệ thống giống trường hợp trên nhưng có c server. Ví dụ, nhóm gồm c
đường trung kế Tie line nối giữa các PBX hoặc các cổng quay số trong các hệ thống
modem truy nhập từ xa của các nhà cung cấp dịch vụ Internet.
• Hệ thống hàng đợi có một server với phân bố thời gian đến của các yêu cầu

x
~
~
. Nếu
, ,,
2
~
1
~
xx
có phân bố chung F thì
( )
xFxxPxxPxxP
x
n
~
~~
2
~
=






≤=








≤






≤=






≤
nnn
xxPxxPxxxxP
~
1
~
121
~
1
, ,,
.
* Định nghĩa : Quá trình đếm.

Quá trình đếm
%
( )
{ }
, 0n t t ≥
được gọi là quá trình Poisson với tốc độ
0
λ
>
nếu:
%
( )
0 0n =
và số các sự kiện xuất hiện trong bất kỳ khoảng thời gian t có phân bố
Poisson với tham số
t
λ
đó là:
%
( )
%
( )
{ }
( )
.
!
n
t
t e
P n t s n s

công của một sự kiện trong môt khoảng thời gian nhất định. Giá trị trung bình này
được gọi là lamda, kí hiệu là λ.
Phân phối Poisson còn được dùng cho khoảng mà đơn vị khác thời gian như:
khoảng cách, diện tích hay thể tích. Một ví dụ cổ điển là sự phân rã hạt nhân của
Theo đó, nếu xem xét một biến ngẫu nhiên N nào đó, và đếm số lần xuất hiện (rời
rạc) của nó trong một khoảng thời gian cho trước. Nếu giá trị kì vọng (hay số lần
trung bình mà biến ngẫu nhiên đó xảy ra trong khoảng thời gian đó là λ, thì xác suất
để cũng chính sự kiện đó xảy ra k lần (k là số nguyên không âm, k = 0, 1, 2, ) sẽ
được tính theo công thức
với
• e là cơ số của logarit tự nhiên (e = 2.71828 )
• k là số lần xuất hiện của một sự kiện - mà xác suất của nó là cho bởi công
thức trên
• k! là giai thừa của k
. λ là số thực dương, bằng với giá trị kì vọng xuất hiện của sự kiện trong một
khoảng cho sẵn.
Quá trình Poisson là một quá trình ngẫu nhiên được định nghĩa theo sự xuất hiện
8
của các biến cố. Một quá trình ngẫu nhiên N(t) là một quá trình Poisson (thời gian-
thuần nhất, một chiều) nếu:
• N(0) = 0
• Số các biến cố xảy ra trong hai khoảng con không giao nhau là các biến ngẫu
nhiên độc lập.
• Xác suất của số biến cố trong một khoảng con [t,t + τ] nào đó được cho bởi
công thức
Trong đó số λ dương là một tham số cố định, được gọi là tham số tỉ lệ (rate
parameter). Có nghĩa là, biến ngẫu nhiên N(t + τ) − N(t) mô tả số lần xuất hiện
trong khoảng thời gian [t,t + τ] tuân theo một phân bố Poisson với tham số λτ.
Tổng quát hơn, một quá trình Poisson là một quá trình gán cho mỗi khoảng
thời gian bị chặn hay mỗi vùng bị chặn trong một không gian nào đó (chẳng hạn,

9
Chương II
MÔ HÌNH TOÁN PHÂN TÍCH HỆ THỐNG THÔNG TIN
THEO LÝ THUYẾT XẾP HÀNG
Trong thực tế hệ thống viến thông thường được mô hình hóa bằng một tập hợp
nhiều hàng đợi.
Một mạng hàng đợi được định nghĩa bằng k nút mạng , mỗi nút mạng i là một
hệ thống hàng đợi đơn bao gồm một hoặc nhiều hàng đợi và một server. Các yêu
cầu đi vào hàng đợi tại một số nút nhất định và đi tới một số nút khác.
Trước hết chúng ta xem xét một số mạng xếp hàng và phương thức xếp hàng
được ứng dụng trong thực tế.
2.1. CÁC MẠNG XẾP HÀNG VÀ
MỘT SỐ PHƯƠNG THỨC XẾP HÀNG
2.1.1. Các mạng xếp hàng
Một hệ thống có thể được biểu diễn bằng một mạng các xếp hàng. Một công
việc có thể nhận được dịch vụ tại nhiều hàng trước khi nó ra khỏi hệ thống. Một mô
hình trong đó các công việc rời khỏi một hàng để sang hàng khác gọi là mạng xếp
hàng.Có 2 cáh để phân loại mạng xếp hàng đó là các mạng mở hoặc mạng đóng.
a. Mạng xếp hàng mở
Mạng xếp hàng mở là một mạng có các cuộc đến và đi phụ thuộc vào bên
ngoài. Như vậy số lượng các công việc trong hệ thống biến đổi theo thời gian.Sơ đồ
biểu diễn hình 2.1:
Hình 2.1: Mạng xếp hàng mở
Khi phân tích một hệ thống mở người ta giả thiết là đã biết được tốc độ đến
Máy chủBộ đệm
Bộ đệm
Máy chủ
Bộ đệm
Ra
Vào

Hình 2.4: Hiện tượng nghẽn đầu vào
Quan sát hình 2.9, các con số ghi trong hàng đợi nếu các ngõ mà tế bào đang
cần đến, cả 3 hàng đợi đều có tế bào đầu hàng đợi mong muốn được ra ngõ ra 3.
Hàng đợi ngõ vào đang được phục vụ nên chỉ tế bào đầu hàng đợi ngõ vào được
chuyển ra ngõ 3 (nét liền đậm ), các hàng đợi khác phải chờ đợi, không được phục
vụ. Ở hàng đợi ngõ vào thứ 2, chỉ có tế bào đầu hàng cần ra ngõ 3 các tế bào sau nó
đều không cần ngõ 3 mà là ngõ ra 2, ngõ ra 1là các ngõ đang hoàn toàn rảnh rỗi chỉ
vì một tế bào đầu hàng mà nhiều tế bào sau phải chờ đợi theo trong khi tại thời điểm
đó các tế bào ấy hoàn toàn có thể được phục vụ tiết kiệm được thời gian mà vẫn
không gây tắc nghẽn. Hàng đợi ngõ vào 3 cũng xảy ra hiện tượng tương tự. Đó la
hiện tượng nghẽn đầu hàng.Trong hiện tượng này dẫn đén nhược điểm của phương
pháp hàng đợi ngõ vào, không tận dụng tối ưu khả năng của mạng liên kết trong
chuyển mạch.
Để khắc phục nhược điểm này , các hàng đơi theo nguyên lý vào trước ra
12
trước có thể thay thế bằng bộ nhớ truy xuất ngẫu nhiên RAM. Nếu tế bào đầu tiên
của hàng đợi phải đứng chờ các tế bào kế tiếp trong hàng đợi muốn ra những ngõ ra
đang rảnh rỗi sẽ được chọn để phục vụ. Để thực hiện được như vậy bộ điều khiển
chắc chắn sẽ phải phức tạp hơn để tìm ra tế bào nào muốn tìm ra ngõ còn trống, vừa
đảm bảo được thứ tự các tế bào cho ngõ ra đó.
Nếu xét về khía cạnh kích thước hàng đợi với một tỉ lệ mất tế bào cho trước
phương pháp hàng đợi đầu vào đòi hỏi chiều dài hàng đợi lớn hơn.
b. Hàng đợi đầu ra
Trong phương pháp hàng đợi đầu ra các hàng đợi được đặt tại các điều, phươ
khiển ngõ ra đã được giới thiệu trong hình 2.10 .
Hình 2.5 : Hàng đợi đầu ra
Khi có nhiều tế bào từ các điều khiển ngõ vào muốn đi qua mạng liên kết đến
cùng ngõ ra , phương pháp này đòi hỏi một sự chuyển rời nội bộ tốc độ cao để lần
lượt chuyển các tế bào này đến các điều khiển ngõ ra mong muốn để đảm bảo
không nghẽn, mạng lien kết và các đầu ra phải có khả năng xử lý N tế bào trong

liệu “ATM netword”:
Hàng đợi Phần tử chuyển mạch
16 x 16
Phần tử chuyển mạch
32 x 32
Hàng đợi trung tâm 113 (tế bào) 199 (tế bào)
Hàng đợi đầu vào 320(tế bào) 640 (tế bào)
Hàng đợi đầu ra 896 (tế bào) 1824 (tế bào)
Bảng số liệu trên cho thấy phương pháp hàng đợi trung tâm đòi hỏi ít bộ nhớ
14
nhất , kế tiếp là hàng đợi đầu vào và cuối cùng là hàng đợi đầu ra.Đó là vì trong
phương pháp hàng đợi đầu vào , khi có nhiều tế bào đến cùng một lúc và không
cùng chọn một ngõ ra thì sẽ có hơ một tế bào có thể được chuyển đi cùng một lúc
còn trong phương pháp hàng đợi đầu ra thì chỉ có một tế bào được chuyển đi tại một
thời điểm. Nhưng ngược lại, độ trễ truyền trong phương pháp hàng đợi đầu ra lại
nhỏ hơn phương pháp hàng đợi đầu vào vì trong các hệ thống dùng phương pháp
đêm đầu vào , các tế bào không đến được ngõ ra mong muốn thường được giải
quyết bằng cách là quay ngược về qua một vòng tạo trễ để chờ cơ hội thứ hai, tránh
gây tắc nghẽn đầu hàng cho các tế bào sau.
Tốc độ bộ nhớ được đánh giá qua thời gian truy xuất bộ nhớ. Thời gian truy
xuất bộ nhớ càng ngắn nghĩa là đòi hỏi tốc độ nhớ phải càng cao. Thời gian truy
xuất bộ nhớ dài hay ngắn còn tùy vào phương pháp xếp hàng được sử dụng, số ngõ
vào, số ngõ ra và tốc độ luồng ngõ vào và ngõ ra. Để so sánh được thời gian truy
xuất bộ nhớ chúng ta xét cả ba phươn pháp với cùng một điều kiện như sau:
Số ngõ vào/ ra N = 16
Tốc độ ngõ vào hay ngõ ra là: F = 150Mps
Dung lượng bộ nhớ W = 16 bits
Bộ nhớ có thể là một cổng ( không thể đọc và ghi đồng thời) hay hai cổng
( cho phép đọc ghi đồng thời).
 Đối với hàng đợi đầu vào, trong thời gian một tế bào, một bộ nhớ được truy

Nếu dùng bộ nhớ hai cổng, để đảm bảo không mất tế bào, yêu cầu tốc độ truyền bên
trong chuyển mạch là:
F’ = N.F = 150.16 = 2400(Mbps)
Thời gian truy xuất bộ nhớ là:
T = W/F’ = 16/(2400.10
6
) = 6,67.10
-9
(s) = 6,67(ns).
 Đối với hàng đợi đầu ra, trong thời gian một tế bào, công việc của bộ nhớ là
nhận tế bào từ N đầu vào và xuất một tế bào tại một đầu ra. Nếu dùng bộ nhớ một
cổng, để đảm bảo không mất tế bào, yêu cầu tốc độ truyền bên trong chuyển mạch
là:
F’ = F(N+1) = 150(16+1) = 2550( Mbps)
Thời gian truy xuất bộ nhớ là:
T = W/F’ = 16/(2550.10
6
) = 6,27.10
-9
(s) = 6,27(ns).
Nếu dùng bộ nhớ hai cổng, để đảm bảo không mất tế bào, yêu cầu tốc độ truyền bên
trong chuyển mạch là:
16
F = NF = 150.16 = 2400(Mbps)
Thời gian truy xuất bộ nhớ là:
T = W/F’ = 16/(2550.10
6
) = 6,27.10
-9
(s) = 6,27(ns).

kiện đặc trưng.
Có rất nhiều kỹ thuật được sử dụng, trải rộng từ việc giải đến các thuật mô
17
phỏng đầy thông minh . Với tất cả những kỹ thuật đó, Những phí tổn về thời gian
giải và những yêu cầu về bộ nhớ máy tính rất đáng quan tâm. Chi phí giải một hệ
thống có mức độ phức tạp bình thường có thể vẫn cực kỳ cao đối với kỹ thuật cụ
thể. Vì vậy vẫn có thể tìm mô hình đại diện cho một hệ thống theo mong muốn và
kèm theo là tìm các giải pháp cho mô hình đó. Có thể tính các số đo hiệu năng của
mạng với n khách hàng , đưa vào các kết quả trước đó tính cho n-1 khách hàng. Một
số giải pháp cụ thể là: thủ thuật nhân chập, phân tích giá trị trung bình . Trong đó
giải pháp thủ thuật nhân chập hay còn gọi là phép đệ qui thông minh của các hằng
số tiêu chuẩn hóa cho mật độ khách hàng gia tăng. Ưu điểm của phương pháp này là
rất nhiều các số đo hiệu năng có thể được viết ra như các hàm số của các hằng số
tiêu chuẩn hóa. Còn phương pháp phân tích giá trị trung bình ưu điểm của nó cũng
như phương pháp thủ thuật giải nhân chập không phải tính toán các xác suất trạng
thái bình quân , không phải tính toán các hằng số tiêu chuẩn hóa. Giải pháp này dựa
trên nhiều trên nhiều phép đệ qui xuất phát từ những khái niêm căn bản của lý
thuyết xếp hàng .
Mục tiếp theo sẽ nghiên cứu mô hình một hàng đợi- một trạm phục vụ và đa
hàng đợi – một trạm phục vụ. Sở dĩ ta xét mô hình một hàng đợi là để giảm độ phức
tạp trong tính toán, từ đó ta phát triển công thức ấy cho mô hình đa hàng đợi. Hay
nói cách khác mô hình đơn hàng là nền móng cho mô hình đa hàng. Trong thực tế
hệ thống hàng chờ của hệ thống thông tin là mô hình đa hàng đợi .Trong luận văn
này chúng ta đi sâu tính toán xác suất trạng thái của các hàng đợi khi sever chuyển
mạch tới nó. Khi các hàng khác thì có nhiều công việc đang đợi nhưng sever chuyển
mạch đến hàng rỗng (không có công việc nào đang đợi trong hàng ) sẽ gây lãng phí
thời gian của sever. Do đó ta đi tính toán xác suất các trạng thái của các hàng rỗng
khi sever chuyển mạch tới nó để từ đó có thể chọn trật tự chuyển mạch sao cho thời
gian chuyển mạch lãng phí là nhỏ nhất, việc sử dụng sever là cao nhất.
2.2.MÔ HÌNH TOÁN PHÂN TÍCH HỆ THỐNG

nhau. Do đó khi phân tích hệ thống này rất phức tạp vì phân bố của các hàng là các
chuỗi thông tin ngẫu nhiên, nhiều hàng đợi tạo nên tổng và tích chập của nhiều
chuỗi cho nên các tính toán rất khó đạt được độ chính xác tuyệt đối trừ khi ta chấp
nhận một số giới hạn biên nào đó hoặc điều kiện ràng buộc và chấp nhận sai số
trong một giới hạn cho phép nào đó.

2.2.1. Mô hình đơn hàng đơn trạm
Trong lý thuyết xếp hàng người ta sử dụng các khái niệm sau đây: các cuộc
gọi tới là công việc (job). Các hàng tại đầu vào của hệ thống được gọi là – các hàng
(queues), thời gian xử lý các công việc cuộc gọi trong hệ thống được gọi là thời
gian dịch vụ ( service time), việc chuyển từ hàng này sang hàng khác được gọi là
thời gian chuyển mạch (walking time), số lần chuyển mạch từ kênh / hàng 1 đến N
gọi là walk times.
19
Đầu tiên hãy xét một mô hình hàng đợi đơn giản, mô hình một hàng đơn một
trung tâm chuyển mạch. Xét hệ thống xử lý tại một trung tâm chuyển mạch như một
server và khách hàng ( các gói số liệu trong hệ thống thông tin số) đang đợi trong hệ
thống là hàng chờ.
Giả sử vào thời điểm 0 không có khách hàng. Vào thời điểm
τ
1
khách hàng
đầu tiên C
1
thực hiện cuộc gọi đến trung tâm chuyển mạch. Lúc này hệ thống sang
trạng thái bận, thời gian dịch vụ phụ thuộc vào cuộc gọi đó. Thời gian dịch vụ cho
khách hàng C
1
kí hiệu là x
1

τ
2
và thời gian cần phục vụ là x
2
. Khi đó
khách hàng thứ 2 ra khỏi hệ thống vào thời điểm
τ
2
+ x
2
+
ω
2
;
ω
2
là thời gian
C2 đợi để cho C
1
đi ra, chính là thời gian giữa
τ
2
và
τ
1
+ x
1.
Nếu C
1
ra khỏi hệ thống trước

đến hệ thống (nhỏ nhất bằng 0).
Khi đó t
n+1
=
τ
n+1
–
τ
n
được gọi là khoảng cách của thời gian đến
20
x
1
Thời gian
1
+x
1
1

C1 đến C1 đi ra
Hình 2.2 Các thời điểm của khách hàng 1
Khách hàng vào
hệ thống
Hàng
chờ
Trạm
đơn
Khách hàng ra
khỏi hệ thống
Hình 2.1. Hệ thống xếp hàng một server đợi

hiệu là G, tốc độ đến của các hàng không giống nhau. Các hàng được phục vụ theo
thứ tự từ 1 đến hàng N, hàng j + 1 sau hàng j. Khi đến hàng, trạm trung tâm phục vụ
tất cả các công việc đã ở hàng. Các công việc đang đến phải đợi đến chu kỳ sau.
Việc phân tích hệ thống như vậy thường trong khoảng xấp xỉ giá trị trung bình tùy
theo mức thông số của hệ thống.
Trong hệ thống tổng quát N hàng, hàng thứ i có quá trình đến của các hàng có
phân bố theo phân bố Poisson với khoảng thời gian trung bình của các lần đến là
1
i
λ
( một số nhà nghiên cứu gọi là cường độ đến – interarrival intensity). Mỗi một
hàng được phục vụ theo cơ chế cổng. Phân bố xác suất thời gian cần phục vụ một
công việc trên hàng thứ i ký hiệu bằng B
i
(t). Thời điểm thứ k
th
của phân bố này
được ký hiệu là b
ki
. Giữa kết thúc hàng j và khởi đầu hàng dịch hàng i, trạm chuyển
mạch từ hàng j đến hàng i. Khoảng thời gian cho chuyển mạch là ngẫu nhiên và
được phân bố theo quy luật xác suất chung. Hàm phân bố xác suất của thời gian để
21
x
n
n+1
x
n+1
n
Thời gian

công việc ở trên hàng thứ i. Trong phạm vi đề tài này chỉ xem xét các hệ thống hoạt
động trong trạng thái ổn định. Điều kiện xảy ra trạng thái cân bằng hay ổn định là
bất đẳng thức:
i
1
1
N
i
i
β λ
=
∑
p
Nhiệm vụ nghiên cứu là xác định trạng thái vector trên với giới hạn sai số nhất
định tại các thời điểm hoàn thành chuyển mạch. Các kết quả có thể được sử dụng để
phân tích và đánh giá hệ thống.
Trước khi bước vào tính toán xác suất đối với mô hình một hàng đơn, chúng ta
sẽ xem xét các công thức toán học sử dụng trong lý thuyết xếp hàng.
- Mô men thứ nhất của phân bố thời gian dịch vụ
( )
1
β
được xác định như sau:
0
`( ) `(0)
st
s
e B t dt
β β
∞

Trong đó p
m
là xác suất dừng/ ổn định của trạng thái m
Ta có:
( )
( )
0
!
m
m
P
m
π
=
trong đó
( )
m
π
là đạo hàm bậc m của
( )
x
π
.
Chúng ta sẽ phân tích
m
P
(là phân bố xác suất trạng thái dừng của số công việc
ở một hàng vào thời điểm trạm chuyển mạch đến). Vào các thời điểm hoàn thành
chuyển mạch, hệ thống có thể được xử lý như chuỗi Markov với số trạng thái giới
hạn. Điều kiện của chuỗi được biểu diễn dưới dạng bất đẳng thức

i
là xác suất dừng ở trạng thái i

( )
k
B t
: là phân bố dịch vụ và dấu * là tích chập của hai phân bố.
Thông qua hàm sinh
( )
0
i
i
i
x p x
π
∞
=
=
∑
có thể nhận được:
22

( ) ( )
( )
( )
( )
( )
1 1x x x
π γ λ π β λ
= − −

( )
1
. 0
!
m
m
m
d
P x x
m dx
π
= =
Lấy đạo hàm m lần của biểu thức (2.1) chúng ta được biểu thức sau:
( ) ( )
( )
( )
( )
( )
( )
( )
0
1 1
m
m k
k
m k
m
k
x C x x
π γ λ π β λ

π γ λ π β λ γ λ π β λ
−
=
   
 
= − − + − −
 
   
∑
Với
( ) ( )
m
m
m
d
x x
dx
π π
=
Trong đó ta có:
( )
( )
( )
( )
( )
( )
( )
( )
( )
( )

m
k
m k
k
m
k
x C x x
β
γ λ λβ λ π β λ
−
− −
−
=
 
 
− − − +
 
 
∑
( )
( )
( )
( )
( )
( )
( )
( )
( )
1 ` 1 1
m

=
 
 
= − − +
 
 
∑
( )
( )
( )
( )
( )
( )
( )
( )
( )
1
1
`
1
0
1 ` 1 1
m
k
m k
k
m
k
x C x x
β

;
k
x
k = 0,1,2…;
0 1x
≤ ≤
Có các thành phần quan hệ theo:
( )
( )
1
1
k k
x x
β λ
+
= −
(2.4)
Chuỗi này hội tụ về 1 với mọi
0
0 1x≤ ≤
nếu
k
→ ∞
, vì là các kết quả của hàm
( )
S
β
.
23
( )

( )
{ }
m
k
x
π
có thể lấy từ (2.1) bằng cách thay thành phần
{ }
k
x
và lấy đạo
hàm m lần, và thay hai biểu thức đầu của vế phải bằng (2.3) bằng R(x
k
,x
k+1
).
( )
( ) ( )
( )
( )
( )
( )
( )
1 1
( , ) 1 ` 1
m
m m
k k k k k
x R x x x x x
π γ λ λβ λ π

j
x R x x R x x x x
π γ λ λβ λ
−
+
=
=
 
= + − − +
 
 
∑
∏
+
( )
( )
( )
( )
( )
1
0
1 `
m
k
m
m
i k
i
x x
γ λ β λ π

1
0
( , ) ( , ) 1 ` 1
i
m
m
i i j j
i
j
x R x x R x x x x
π γ λ λβ λ
∞
+
=
=
 
= + − −
 
 
∑
∏
(2.6)
Chuỗi này hội tụ vì:
1
( , ) (1,1) ons
i i
R x x R c t
+
≤ <
và

π γ λ λβ λ
−
+
=
=
 
= + − −
 
 
∑
∏
(2.7)
Xét sự khác nhau giữa (2.6) và (2.7) là :
( )
( )
( )
( ) ( )
( )
( )
( )
( )
1
0 0 1
1
0
0 ( , ) 1 ` 1
i
m
m k
i i j j

ρ
+
∞
+
= +
<
−
∑
, ( trong đó
1
ρ λβ
=
) (2.8)
Bất đẳng thức (2.8) cho phép ước lượng sai số khi tính P
m
sử dụng (2.7).

a. Tính xác suất ở trạng thái 0
Để tính
0
P
, sử dụng (2.5), với trường hợp m = 0
( ) ( )
( )
( )
1
1
m
k k k
x x x

Từ (2.9) ta tính được:
( ) ( )
( )
( )
0 1
0
1
k
i k
i
x x x
π γ λ π
+
=
= −
∏
(2.10)
Giới hạn
k
→ ∞
và với điều kiện
1
1
λβ
<
, chúng ta có ( với
( )
1 1
π
=

π
được tính bằng công thức:
( ) ( )
( )
0 0
0
1
k
k i
i
x x
π γ λ
=
= −
∏
(2.12)
Rõ ràng chuỗi
( )
{ }
0 0k
x
π
hội tụ về
( )
0
x
π
như một hàm của k sử dụng (2.12).
Từ (2.4) ta có thể nhận được:
( )

( )
1k
x
π
+
ta có thể chỉ ra được là:
( ) ( ) ( )
1 1 1k k k k
x x x x M
π π
+ +
≤ + −
hoặc
( ) ( ) ( )
1 1 0 1
k
k k
x x x x M M
π π
+
≤ + −
Trong đó:
( )
{ }
( )
1
1
ax ` ` 1
1
M m x

25