trờng đại học bách khoa hà nội
Khoa điện tử viển thông

Đề cơng bài giảng môn kỹ thuật chuyển mạch
Phần
Các Kỹ Thuật Chuyển Mạch Gói
Chơng 1
Lý thuyết xếp hàng
Tóm tắt
Xếp hàng là gì?
Các nguyên tắc cơ bản của lý thuyết xếp hàng
Các yếu tố trực giác
Các thành phần của 1 hàng đợi
Ký hiệu của hàng đợi
Author Nguyen Tai Hung Hanoi University of Technology
Tel 844 833 4400 Faculty of Electronic & Telecommunication
Fax 844 833 4372 Department of Communication Engineering
Handy Phone 84 9021 7248 http://www.hut.edu.vn
E.mail [email protected]
Hanoi University of Technology Faculty of Electronic & Telecommunication
Department of Communication Engineering
Các phân bố xác suất
Các phơng pháp phân tích hàng đợi
Giá trị trung bình và biến thiên
Các thông số đo lờng hiệu suất của một hàng đợi
Một số thuật ngữ chung về hàng đợi
Các hệ thống hàng đợi cơ bản
Mô hình hàng đợi M/M/1
Mô hình M/M/1/K, luật xếp hàng FIFO
M/M/c
M/M/c/K

bộ đệm và cách đọc chúng ra cũng nh các luật quản lý thông tin lu trong nó. Sau
Nguyen Tai Hung Packet Switching Engineering
2
Hanoi University of Technology Faculty of Electronic & Telecommunication
Department of Communication Engineering
đây sẽ nghiên cứu kỹ về các mô hình hàng đợi chủ yếu trong lĩnh vực thông tin và
viễn thông.
Trong khoá học này sinh viên sẽ hiểu biết và giải thích đợc các khái niệm cơ bản
về lý thuyết hàng đợi bao gồm: mật độ phân bố của một nguồn thông tin nói
chung, phân bố thời điểm đến của các yêu cầu trong một hệ thống thông tin, các
luật quản lý hàng đợi, cơ chế phục vụ, các kiểu hệ thống hàng đợi, và các chỉ số
đo hiệu suất của hệ thống. Ngoài ra sinh viên cũng sẽ đợc nghiên cứu về các mô
hình hàng đợi cơ bản cũng nh tiên tiến.
2. Định nghĩa & các khái niệm trong lý thuyết xếp hàng
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 lu 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

5% x 50%) thuê bao sử dụng các đờng trung kế nối 2 tổng đài theo mỗi hớng có
nghĩa là trung bình có tổng cộng 250 thuê bao sử dụng đờng trung kế cùng lúc, do
đó ngời thiết kế chỉ cần thiết kế hệ thống đảm bảo đợc yêu cầu trung bình này. Gọi
số đờng trung kế cần thiết này là E.
Tại một thời điểm bất kỳ khi mà số thuê bao cùng nhấc máy gọi lớn hơn giá trị E
này thì số lợng thuê bao lớn hơn đó sẽ phải đợi. Vì hệ thống chỉ đợc thiết kế để
phục vụ E thuê bao tại mỗi thời điểm. Tơng tự nh vậy cũng có một số thời điểm mà
số yêu cầu kết nối cuộc gọi đồng thời bé hơn giá trị E. Và điều không may là giá
trị d ra này lại không thể để dành để phục vụ số khách hàng dôi ra khi số yêu cầu
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à
Phân bố thời gian phục vụ

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.

Nguyen Tai Hung Packet Switching Engineering
5
Hanoi University of Technology Faculty of Electronic & Telecommunication
Department of Communication Engineering
Hình 1: Các hệ thống hàng đợi thông dụng trong viễn thông

Một số kiểu phân bố thờng gặp trong nhiều hệ thống viễn thông gồm:
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
Nguyen Tai Hung Packet Switching Engineering
6
Hanoi University of Technology Faculty of Electronic & Telecommunication
Department of Communication Engineering
có 1 yêu cầu đã đợi đợc T phút rồi). Điển hình của kiểu này là lu 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]
Và 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
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.
Hệ thống giống trờng hợp trên nhng 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

trình trên là phân bố hình học. Phân bố này có không gian xét là tập các số nguyên
(danh sách các đầu ra có thể ); xác suất xảy ra số nguyên i là p(1-p)[i], với p là
Nguyen Tai Hung Packet Switching Engineering
7
Hanoi University of Technology Faculty of Electronic & Telecommunication
Department of Communication Engineering
thông số cho trớc giữa 0 và 1. Giả sử rằng chiều dài khe thời gian là 50ms. Ta sẽ
có:
Xác suất gói đợc truyền lại trong khe thời gian 0 là:
(0.1)(0.9)[0] = 0.100
Xác suất gói đợc truyền lại trong khe thời gian 1 là:
(0.1)(0.9)[1] = 0.090
Xác suất gói đợc truyền lại trong khe thời gian 2 là:
(0.1)(0.9)[2] = 0.081
Xác suất gói đợc truyền lại trong khe thời gian 3 là:
(0.1)(0.9)[3] = 0.072
Xác suất gói đợc truyền lại trong khe thời gian 4 là:
(0.1)(0.9)[4] = 0.065, vv
( Truyền lại trong khe thời gian 0 có nghĩa là khe thời gian theo sau ngay lập tức
khe thời gian vời xảy ra va chạm ).
Số lợng khe thời gian trung bình trớc khi truyền lại sẽ là (1-p)/p = 0.9/0.1 = 9. Do
đó tổng thời gian trung bình cho một cố gắng truyền lại sẽ là 9 x 45 = 450ms.
Kỹ thuật này cũng đợc sử dụng trong các hệ thống thông tin dạng cụm của Motorola.
Nó cũng đợc sử dụng trong các hệ thống VSAT (Very Small Aperturre Terminal)
truyền thoại và dữ liệu.

3. Các phơng pháp phân tích 1 hệ thống hàng đợi
Khi phân tích 1 hệ thống hàng đợi thì tuỳ thuộc vào kiểu phân bố thời gian đến của
các yêu cầu và phân bố thời gian phục vụ là xác định trớc hay ngẫu nhiên mà có
phơng pháp phân tích cụ thể. Tuy nhiên các hệ thống thực tế đợc phân tích dựa vào

p [3 ] + + x [n]
2
p [n] = x [i]
2
[Pi].
Ví dụ: Tung con súc sắc, phân bố sự kiện này nh sau:
Nguyen Tai Hung Packet Switching Engineering
8
Hanoi University of Technology Faculty of Electronic & Telecommunication
Department of Communication Engineering
Sự kiện (số của mặt) Xác suất
1 1/6
2 1/6
3 1/6
4 1/6
5 1/6
6 1/6
Giá trị trung bình (giá trị mong muốn) của một số (từ 1 đến 6) trên mặt con súc sắc
là:
E(X) = 1 x 1/6 + 2 x 1/6 + 3 x 1/6 + 4 x 1/6 + 5 x 1/6 + 6 x 1/6 = 3.5
Giá trị biên thiên đợc tính nh sau: trớc hết tính
E(X
2
) = 1x1 x 1/6 + 2 x 2 x 1/6 + 3 x3 x 1/6 + 4 x 4 x 1/6 + 5 x 5 x 1/6 + 6 x 6 x
1/6 = 15.16
V(X) = 15.16 (3.5)
2
= 2.91
Các yếu tố đánh giá hiệu suất của 1 hệ thống hàng đợi
Ngời ta dựa vào các thông số sau để đánh giá hiệu suất hoặc tính hiệu quả của 1 hệ

Hanoi University of Technology Faculty of Electronic & Telecommunication
Department of Communication Engineering
Một hệ thống hàng đợi đơn server có dung lợng tối đa để thực hiện công việc mà t-
ơng đơng với 1 giây mỗi giây, và mỗi yêu cầu đến mang theo 1 lợng công việc
bằng x [bar] giây.
Có thể viết:
rho = x (1/x [bar])
Ký hiệu: mu = 1/ x [bar]
rho = /mu
Đối với 1 hệ thống hàng đợi có m server thì:
rho = x (x [bar])/m
4. Một số mô hình hàng đợi điển hình trong viễn thông và chuyển mạch gói
Các hệ thống hàng đợi cơ bản đợc tóm tắt trong bảng sau:
Tóm tắt một số kết quả
L = Chiều dài trung bình của hàng đợi W = Trễ trung bình

[c - 1]
M/M/1 p [0] = 1/{[ 1/{[(r) [n]/n!] + [r [c] /c!]
L = /(mu - ).
[n = 0]
W = 1/(mu - ).
[1 - s [K - c + 1]]/[1 - s]}, khi s không
M/M/1/K
bằng 1,
p [n] = (rho) [ n] (1 - rho)/[1 - (rho) [K+1]],
khi
[c -1]
rho < 1, và
p [0] = 1/{[10 (r) [n ]/n!] + (r [c]/c!)
(K - c + 1)},

M/M/c/c
vợt quá c.
(Erlang B)
c 1 c
p [0] = 1/[(;bccf10r [n]n!) + cr [c]/c!(c - r)]. pc = {[(c)(rho)] [ c]/c!}/{[10[(c)
(rho)] [n]/n!], with
[n = 0] [n = 0]
W = (r [ c](mu)/(c - 1)![c(mu) - ] [2] }p [0]
+
rho = ()/[(c)(mu)].
1/mu;
M/E [k ]/1
L = ()W. Wq = [(k + 1)/(2k)] [/(mu)
M/M/c/K
(mu )].
r = /mu, và Lq = ()W [q] (from Little's result).
s = /(c)(mu) = rho.

p [n] = [1/n!](r) [n]p [0], when n is between 1
and c, and
M/G/1
p [n] = [1/(c) [n - c] c!](r) [n]p [0], khi n nằm
giữa c và K.
L = (rho) + [(rho) [2] + () [2](s [B]
[2])]/

[2(1 - rho)] với s [B] [2] = V(B) =

E(B [2] ) - E(B) [2]


Do đó:
- Xác suất mà 0 có user nào truy nhập là: p [0] = 0.05
- Xác suất mà 1 có user nào truy nhập là: p [1] = 0.0475
- Xác suất mà 0 có user nào truy nhập là: p [0] = 0.0451

Số user trung bình đợi trong hệ thống là:
L = rho/(1 - rho) = 0.95/0.05 = 19
Thời gian tổng cộng trung bình trong hệ thống là:
W = 1/(mu - ) = 1/(0.500 - 0.475) = 40 giây
Thời gian này là khá dài vì một user sẽ rất bực mình khi phải đợi đến 40 s mới
nghe đợc 1 thông bào từ hệ thống sau khi ấn một phím trên máy điện thoại hoặc
máy tính.
Giải pháp là ngời quản trị hệ thống có thể mua thêm ổ cứng hoặc bộ điều khiển để
giảm thời gian phục vụ xuống còn 0.350 ms. Khi đó tính toán lại ta sẽ có:
= (1/t [bar]) = 2.0 và = (1/x [bar]) = 2.85 nên rho = /mu = 0.7.
Số yêu cầu trung bình trong hệ thống bây giờ là:
L = rho/(1 - rho) = 0.7/0.3 = 2.3.
Tổng thời gian trung bình trong hệ thống là:
W = 1/(mu - ) = 1/(0.500 - 0.350) = 6.6 giây.
Thời gian đợi bây giờ đã giảm đáng kể xuống còn 6.6 giây do đó rõ ràng với ổ
cứng mới đã cải thiện đáng kể hiệu suất làm việc của hệ thống Voice Mail. Đây là
lý do tại sao một kỹ s viễn thông phải rất thành thạo về lý thuyết hàng đợi khi thiết
kế các hệ thống thông tin.
4.2. Mô hình M/M/1/K , với luật hàng đợi là FIFO ( K là số vị trí rỗi trong hàng
đợi)
M/M/1/K là hệ thống có số lợng vị trí trong hàng đợi có giới hạn: chỉ có K vị trí rổi
( theo định nghĩa K cũng bao gồm số server). Mô hình này gặp rất nhiều trong thực
tế, đặc biệt trong các hệ thống thông tin: các đờng trung kế Tie Line giữa 2 tổng
đài PBX, các thanh ghi trong chuyển mạch điện thoại, các cổng quay số tới 1 PAD,
Nguyen Tai Hung Packet Switching Engineering

= 5 mổi phút ( là số khách hàng đến trong 1 phút)
mu = 6 mổi phút ( số khách đợc phục vụ trung bình trong 1 phút)
Trớc khi quyết định tăng thêm số đờng trong vòng quay ( nhng vẫn chỉ 1
Operator), ngời chủ cửa hàng cần biết : kích thớc trung bình của hệ thống, chiều
dài hàng đợi trung bình, thời gian đợi trung bình để đợc phục vụ, và thời gian đợi
trung bình đối với những khách hàng đang chờ bằng các câu thông báo.
Ngời chủ sẽ tính nh sau:
rho = 5/6 = 0.833;
L = 0.833[1 - 6(0.833) [5] + 5(0.833) [6 ]]/[0.833(1 - 0.833 [6])] = 1.97;
L [q] = 1.97 - (0.833)[1 - (0.833) [5 ]]/[1 -
(0.833) [6]] = 1.22;
p [5] = (0.833) [5](1 - 0.833)/[1 - (0.833) [6]] = 0.10,
Từ đó
W = 1.97/[(5)(1 - 0.1)] = 0.438 phút;
W [q] = 0.438 - 0.167 = 0.271 phút.
Nguyen Tai Hung Packet Switching Engineering
13
Hanoi University of Technology Faculty of Electronic & Telecommunication
Department of Communication Engineering
Để xác định trung bình có bao nhiêu khách hàng bị mất, phải xác định xác suất mà
một cuộc gọi đến thì thấy có 4 khách hàng khác đang chờ thao tác viên (Operator)
và nhân xác suất này với tốc độ đến trung bình . Nh sau:
()(p [5]) = (5)(0.10) = 0.5 khách hàng/phút,
Hoặc 1 khách hàng trong 2 phút. Do đó, ngời chủ cửa hàng phải đầu t thêm 1 số đ-
ờng trong vòng quay nữa, vì tỉ lệ này là tơng đối cao ( 10% khách hàng đến bị
mất).
4.3. Hệ thống hàng đợi đa server M/M/c : c là số server
Kiểu hệ thống hàng đợi đa server này có rất nhiều ứng dụng trong thực tế, ví dụ:
nhóm các đờng trung kế nối giữa 2 tổng đài, 1 PAD (Packet
Assembler/Disassembler) với nhiều cổng vào, .

Department of Communication Engineering
ở đây c = 3, mu = 3, = 6. Do đó r = / mu = 2. Vậy nên ta có:

p [o]= 1/[(1 + 2 + 2 [2] /2!) + 3(2) [3]/3!(3 - 2)] = 0.11;
Do đó:
W = 1/3 + {3(2) [3]/2![(3)(3) - 6] [2 ]}(0.11) = 0.48 phút
và
L = (6)(0.48) = 2.88.
Tơng tự xét các mô hình khác. (thực hiện sau)
5. Mô phỏng
Khi phân tích các loại mô hình hàng đợi ở trên, chúng ta có thể thấy các mô hình
đó có những hạn chế sau:
Ngời kỹ s cần giải quyết 1 vấn đề nhng lại không biết liệu một mô hình nào đó
đã đợc giải quyết rồi hay cha và có thể tìm giải pháp ở đâu
Thứ 2 các mô hình này có thể tìm thấy trong các tài liệu, nhng giải pháp lại
không nằm dới dạng các phơng trình đại số.
Thứ 3, mô hình có thể tìm thấy, nhng giải pháp lại quá phức tạp để có thể thực
hiện nó
Thứ 4, có những mô hình tơng tự đã đợc giải quyết rồi, nhng những mô hình
này lại không hoàn toàn phù hợp với yêu cầu.
Có một cách để vợt qua các hạn chế đó là sử dụng mô phỏng. Mô phỏng là một
luật đã đợc phát triển cho phép các kỹ s xây dựng các mô hình vi mô của hệ thống
thực tế trên máy tính và sau đó để cho máy tính tìm ra giải pháp. Nó yêu cầu các
chuyên gia thiết kế, các nhà lập trình để đạt đợc giải pháp cho những vấn đề cực
kỳ phức tạp.
Chơng trình mô phỏng có thể đợc viết bằng những ngôn ngữ bậc cao, tuy nhiên ng-
ời ta thờng dùng những ngôn ngữ chuyên dụng cho mô phỏng. Thông dụng nhất là
các hệ thống: GPSS (General Purpose Simulation System), 1 sản phẩm của IBM,
hoặc SIMSCRIPT, Có thể tìm thông tin về các phần mềm trên tại:
http://ww.isye.gatech.edu/informs-sim/comm.html