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Ỹ Ậ Ể Ạ
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 Hungnt@mail.hut.edu.vn
Hanoi University of Technology – Faculty of Electronic & Telecommunication
Department of Communication Engineering
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ệ ủ ợ
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
So sánh mô hình M/M/1 và M/M/c
Mô hình M/M/c/c ( ph ng trình Erlange B)ươ
Các hàng đ i v i ngu n h n chợ ớ ồ ạ ế
Các hàng đ i có lu t ph c v ph thu c tr ng thái (State Dependentợ ậ ụ ụ ụ ộ ạ
Service)
Các hàng đ i v i 2 ki u l u l ng đ nợ ớ ể ư ượ ế
Các hàng đ i Impatienceợ
Các mô hình Erlange (M/Ek/1 và Ek/M/1)
Các h th ng hàng đ i tiên ti nệ ố ợ ế
M/G/1
M/G/c và M/G/c/c
G/M/1
G/G/1
Các mô hình khác
Mô ph ng ỏ
Các ng d ngứ ụ
K t lu nế ậ
Tham kh oả
Các thu t ng và t vi t t t v hàng đ iậ ữ ừ ế ắ ề ợ
Nguyen Tai Hung – Packet Switching Engineering
2
Hanoi University of Technology – Faculty of Electronic & Telecommunication
Department of Communication Engineering
1. Đ t v n đặ ấ ề
Không gi ng các b chuy n m ch kênh, các chuy n m ch gói c n các b nhố ộ ể ạ ể ạ ầ ộ ớ
đ m đ l u các gói đ u vào không bi t tr c. Th m chí khi mà lu ng gói vàoệ ể ư ầ ế ướ ậ ồ
chuy n m ch là bi t tr c thì cũng r t c n có b đ m đ phòng tr ng h pể ạ ế ướ ấ ầ ộ ệ ề ườ ợ
tr ng chuy n m ch ( Switch Fabric) ho c các trung k ra b n đ đ m b oườ ể ạ ặ ế ậ ể ả ả
không m t gói. Các b đ m này có th đ c đ t tr c ho c sau tr ng chuy nấ ộ ệ ể ượ ặ ướ ặ ườ ể
m ch ho c t i m t v trí chung mà có th truy nh p đ c c t c ng vào l nạ ặ ạ ộ ị ể ậ ượ ả ừ ổ ẫ
c ng ra. Tuy nhiên m t v n đ quan tr ng là cách qu n lý các b đ m này nhổ ộ ấ ề ọ ả ộ ệ ư
th nào đ v a đ m b o m t chi phí th p (dung l ng b đ m) mà l i v a đ mế ể ừ ả ả ộ ấ ượ ộ ệ ạ ừ ả
b o đ c hi u su t cũng nh quy n u tiên c a t ng lo i l u l ng khác nhau.ả ượ ệ ấ ư ề ư ủ ừ ạ ư ượ
Ng i ta đã đ a ra m t lý thuy t g i là “ Lý thuy t x p hàng” ti ng anh làườ ư ộ ế ọ ế ế ế
“Queuing System” trong đó quy đ nh cách thông tin đ c l u vào b đ m và cáchị ượ ư ộ ệ
đ c chúng ra cũng nh các lu t qu n lý thông tin l u trong nó. Sau đâ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 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ậ ứ ệ ậ ợ ữ ệ
Nguyen Tai Hung – Packet Switching Engineering
3
Hanoi University of Technology – Faculty of Electronic & Telecommunication
Department of Communication Engineering
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 các user khác gi i phóng tài nguyên h đang chi m ho c có th b t ch iả ọ ế ặ ể ị ừ ố
ph c v . Phân tích hàng đ i đã tr thành c s cho vi c thi t k và qu n lý hụ ụ ợ ở ơ ở ệ ế ế ả ệ
th ng nh trên.ố ư
Sau đây li t kê tóm t t m t s ví d thông tin vi n thông và thông tin s li u ngệ ắ ộ ố ụ ễ ố ệ ứ
d ng lý thuy t x p hàng trong ho t đ ng c a chúng:ụ ế ế ạ ộ ủ
oTr trong các m ng Ethernet (LAN)ễ ạ
oTh i gian l i trung bình c a các card giao ti p thuê bao c a các PBXờ ổ ủ ế ủ
oCác b đ m gói t i các PADộ ệ ạ
oHi u su t c a m t máy ch qu n lý các printer trong 1 m ng LANệ ấ ủ ộ ủ ả ạ
oCác đ ng trung k T1/E1 n i gi a các t ng đài PBXườ ế ố ữ ổ
oXác su t t c ngh n cu c g i c a m t t ng đài PBXấ ắ ẽ ộ ọ ủ ộ ổ
oCác cu c g i ch trong các t ng đài PBX v i LCR (Least Cost Routing)ộ ọ ờ ổ ớ
oCh t l ng các h th ng tho i đ c gói hoáấ ượ ệ ố ạ ượ
.....
2.2. Các khái ni m & ký hi u c b n v hàng đ iệ ệ ơ ả ề ợ
Các nhân t nh n gi ng b ng tr c giác h th ng hàng đ iố ậ ạ ằ ự ệ ố ợ
Xem xét vi c thi t k m t nhóm các đ ng trung k gi a 2 t ng đài đi n tho i.ệ ế ế ộ ườ ế ữ ổ ệ ạ
M i t ng đài có th có hàng nghìn thuê bao. T t nhiên ng i ta s không dùngỗ ổ ể ấ ườ ẽ
hàng nghìn đ ng trung k đ n i 2 t ng đài này v i nhau. Mà th c t ng i taườ ế ể ố ổ ớ ự ế ườ
làm nh sau: trung bình ch có kho ng 5% khách hàng yêu c u đ c ph c vư ỉ ả ầ ượ ụ ụ
cùng 1 lúc, trong đó l i ch có kho ng 50% khách hàng c n k t n i v i các thuêạ ỉ ả ầ ế ố ớ
bao t ng đài bên kia và ng c l i. Ví d , n u m i t ng đài có 5000 đ ng thuêở ổ ượ ạ ụ ế ỗ ổ ườ
bao, thì ch có 125 (5000 x 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.
Nguyen Tai Hung – Packet Switching Engineering
4
Hanoi University of Technology – Faculty of Electronic & Telecommunication
Department of Communication Engineering
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.ộ ệ
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ộ ớ ồ ư ượ ế ủ ừ ạ ầ
Phân b th i gian ph c v c a các h th ng hàng đ i. Trong nhi u hố ờ ụ ụ ủ ệ ố ợ ề ệ
th ng thông tin, đi u này t ng đ ng v i phân b chi u dài cu c g iố ề ươ ươ ớ ố ề ộ ọ
Ph ng pháp qu n lý hàng đ i: FIFO, Random Order, Priorities,...ươ ả ợ
Chi u dài t i đa c a hàng đ i (liên quan đ n dung l ng b đ m)ề ố ủ ợ ế ượ ộ ệ
Ph n ng c a các yêu c u b tr (g i l i, hu yêu c u,...) ả ứ ủ ầ ị ễ ọ ạ ỷ ầ
Ký hi u c a các h th ng hàng đ iệ ủ ệ ố ợ
M t h th ng hàng đ i th ng đ c ký hi u nh sau:ộ ệ ố ợ ườ ượ ệ ư
A/B/m/K/p
A : tên mã c a phân b th i gian đ n hàng đ i c a các yêu c uủ ố ờ ế ợ ủ ầ
B : tên mã c a phân b th i gian ph c v c a hàng đ iủ ố ờ ụ ụ ủ ợ
m : là s server r i c a h th ng hàng đ iố ỗ ủ ệ ố ợ
K : s v trí r i trong b đ mố ị ỗ ộ ệ
Nguyen Tai Hung – Packet Switching Engineering
5