Xem mẫu
- 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
2
Nguyen Tai Hung – Packet Switching Engineering
- 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
3
Nguyen Tai Hung – Packet Switching Engineering
- 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:
o Trễ trong các mạng Ethernet (LAN)
o Thời gian lổi trung bình của các card giao tiếp thuê bao của các PBX
o Các bộ đệm gói tại các PAD
o Hiệu suất của một máy chủ quản lý các printer trong 1 mạng LAN
o Các đường trung kế T1/E1 nối giữa các tổng đài PBX
o Xác suất tắc nghẽn cuộc gọi của một tổng đài PBX
o Các cuộc gọi chờ trong các tổng đài PBX với LCR (Least Cost Routing)
o Chấ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.
4
Nguyen Tai Hung – Packet Switching Engineering
- 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
5
Nguyen Tai Hung – Packet Switching Engineering
- Hanoi University of Technology – Faculty of Electronic & Telecommunication
Department of Communication Engineering
p : số yêu cầu tối đa mà một hệ thống hàng đợi có thể phục vụ
được ( ví dụ một cửa hàng bán mỹ phẩm ở Hà Nội lượng khách
tối đa là 100 người chẳng hạn)
Khi không cần thiết thì 1 hoặc 2 tham số cuối được bỏ đi
Sau đây minh hoạ một số kiểu hệ thống hàng đợi thường gặp trong các hệ thống
thông tin:
6
Nguyen Tai Hung – Packet Switching Engineering
- 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
7
Nguyen Tai Hung – Packet Switching Engineering
- Hanoi University of Technology – Faculty of Electronic & Telecommunication
Department of Communication Engineering
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]
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 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 là ngẫu nhiên, phân bố thời gian phục vụ cố định. Ví dụ, dịch
vụ các cổng ra trong 1 thiết bị chuyển mạch gói (Routers, Switches)
2.3. Các phân bố xác suất
Trong các hệ thống xác suất hoặc hệ thống hàng đợi ngẫu nhiên, các thời điểm
đến của các yêu cầu và thời gian phục vụ từng yêu cầu là không biết tr ước. Do
đó các thực thể đó hoàn toàn phải xác định bằng phân bố xác suất. Trong lý
thuyết xác suất thì một sự kiện không thể yêu cầu một kết quả duy nhất mà là
một số khả năng có thể. Phân bố xác suất liệt kê các trường hợp có thể đó.
Các phân bố thời gian đến và thời gian phục vụ trong các hệ thống hàng đợi chia
thành 2 kiểu: rời rạc và liên tục. Các phân bố rời rạc là các phân bố mà trong
khoảng thời gian xét có một số lượng sự kiện không thể đếm được ( ở đây khác
vô hạn). Còn các phan bố liên tục là các phân bố mà khoảng thời gian xét đ ược
tạo bởi vô hạn điểm. Các kiểu phân bố và đặc tính của chúng được mô tả trong
lý thuyết xác suất, ở đây không xét chi tiết.
Tất nhiên, chỉ xác định kiểu phân bố không thôi chưa đủ mà phải xác định tất cả
cả hoặc một số thông số mô tả phân bố đó. Ví dụ, có thể có hệ thống ngẫu
nhiên (Memoryless) với trung bình 5 hoặc 15 yêu cầu đến trong một đơn vị thời
gian. Một số phân bố yêu cầu nhiều hơn 1 thông số. Sau đây chúng ta xét một ví
dụ về phân bố xác suất:
8
Nguyen Tai Hung – Packet Switching Engineering
- Hanoi University of Technology – Faculty of Electronic & Telecommunication
Department of Communication Engineering
Ví dụ (phân bố rời rạc): Trễ trong một mạng LAN kiểu Ethernet
Hệ thống bus chung trong mạng LAN được chi khe thời gian với đ ộ dài
bằng nhau. Một khe tương ứng với thời gian để truyền một gói kích
thước cố định. Vì có nhiều user trên bus cùng cố gắng chiếm 1 khe thời
gian nên va chạm có thể xảy ra và khi đó sẽ không thể truyền dữ liệu. Khi
bộ điều khiển truyền thông của một user phát hiện ra rằng dữ liệu của nó
bị va chạm, nó sẽ định lại lịch trình phát của nó trong một khe thời gian
sắp tới ( trượt từ khe thời gian hiện thời một số khe). Giả sử rằng tại một
khe thời gian bất kỳ một bộ điều khiển sẽ truyền một gói đang ùn tắc của
nó với xác suất p = 0.1 và không truyền với xác suất là 0.9. Phân bố điều
khiển quá 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à 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 2 trường hợp gần đúng sau đây:
Phần lớn các yêu cầu đến theo 1 quy luật có thể biết trước, chỉ 1 số là
ngẫu nhiên.
9
Nguyen Tai Hung – Packet Switching Engineering
- Hanoi University of Technology – Faculty of Electronic & Telecommunication
Department of Communication Engineering
Các công cụ của lý thuyết xác suất đã chứng minh được rằng đối
xử của hệ thống đối với phần lớn các yêu cầu phục vụ là có thể
đoán trước 1 cách chính xác, gần với trường hợp xác định.
Giá trị trung bình và biến thiên
Trong lý thuyết xác suất thì xác suất xảy ra của một trong các sự kiện:
x [1] , x [2], x [3], ..., x [n]
Là:
p [1], p [2], p [ 3], ..., p [n]
Giá trị trung bình của phân bố các giá trị xác suất trên là E(X), gọi là giá trị mong
muốn được tính như sau:
E(X) = x [1]p [1] + x [2]p [2] + x [3 ]p [3] + ... + x [n] p [n] = x [i]p [i]
Dung sai của phân bố ( nghĩa là sai lệnh giữa 1 giá trị xác suất bất kỳ với giá tr ị
trung bình trên là:
V(X) = (E(X2) - E(X)2 )
Theo công thức trên ta có:
E(X2) = x [1]2 p [1] + x [2]2p [2] + x [3]2p [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:
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(X2) = 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ệ thống hàng đợi:
Thời gian đợi của mổi yêu cầu trong hàng đợi
10
Nguyen Tai Hung – Packet Switching Engineering
- Hanoi University of Technology – Faculty of Electronic & Telecommunication
Department of Communication Engineering
Số yêu cầu trong hàng đợi
Khoảng thời gian bận của hệ thống
Chiều dài thời gian rỗi
Các công việc đang bị ùn lại
Phân bố đầu ra (quan trọng đối với hệ thống hàng đợi gồm
nhiều bộ đệm nối tiếp nhau)
Một số thuật ngữ trong lý thuyết xếp hàng
• Hệ số sử dụng
Hệ số sử dụng là tỉ số giữa tốc độ công việc đưa vào hệ thống và tốc độ tối
đa (dung lượng) mà hệ thống có thể thực hiện công việc này. Tiếng hy lạp ký
hiệu tỉ số này là: rho (0 ≤ rho ≤ 1). rho là một thông số đặc tính quan
trọng của 1 hệ thống hàng đợi, khi nó tiến gần tới 1 thì trễ trong hàng đợi sẽ
trở nên rất lớn (vô cùng). Công việc mà một yêu cầu đưa đến cho hệ thống
bằng thời gian mà hệ thống phục vụ nó. Do đó đối với 1 hệ thống hàng đ ợi
đơn server chúng ta có:
rho = (tốc độ đến trung bình của các yêu cầu ) x (thời gian phục vụ trung
bình)
Phân bố thời gian đến của các yêu cầu A có giá trị mong muốn (trung bình) là
t[bar], là khoảng thời gian trung bình giữa các yêu cầu khác nhau đến hệ
thống, hàm nghịch đảo của nó là 1/ t[bar] được ký hiệu theo ký tự hy lạp λ là
tốc độ đến trung bình của các yêu cầu.
Do đó:
rho = (λ) x (thời gian phục vụ trung bình)
Để cho tiện người ta ký hiệu giá trị của thời gian phục vụ trung bình là x
[bar].
Nên:
rho = λ x (x [bar])
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
11
Nguyen Tai Hung – Packet Switching Engineering
- Hanoi University of Technology – Faculty of Electronic & Telecommunication
Department of Communication Engineering
Đố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]], [c -1]
khi
rho < 1, và p [0] = 1/{[10 (r) [n ]/n!] + (r [c]/c!)(K
- c + 1)},
p [n] = 1/(K + 1), khi rho = 1. n=0
L = (rho)(g/h), với khi s bằng 1.
g = [1 - (K + 1) Lq =
+ K(rho)K + 1], và (rho) [K]
Lq =
h = [1 - (rho) [K + 1]] (1 - rho).
{p [0][(c)(rho)] [c]rho}
h = [1 - (rho) [K + 1]] (1 - rho)
{1 - (rho) [K - c + 1] -
W = L/[(λ)(1 - p [K])]. (1 - rho)(K - c + 1)(rho) [K - c]}/
M/M/c {c!(1 - rho) [ 2]};
rho = λ/(c)(mu). L: the algebraic expression is too long
to show
pn = (λ)np0/[n!(mu)n], khi n nằm ở đây, xấp xĩ L [q] + c.
giữa 1 và c, và W [q ]= L [q] /[(λ)(1 - p [K])].
p [n] = (λ) [n]p [0]/[(c) [n - c]c!(mu) [n]], khi M/M/c/c
n
12
Nguyen Tai Hung – Packet Switching Engineering
- Hanoi University of Technology – Faculty of Electronic & Telecommunication
Department of Communication Engineering
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 M/G/1
and c, and
p [n] = [1/(c) [n - c] c!](r) [n]p [0], khi n nằm L = (rho) + [(rho) [2] + (λ) [2](s [B]
giữa c và K. [2])]/
[2(1 - rho)] với s [B] [2] = V(B) =
E(B [2] ) - E(B) [2]
W = L/(λ)
W [q ] = W - 1/(mu)
L [q] = L - (λ)/(mu)
4.1. M/M/1
Đây là hệ thống hàng đợi đơn server, các yêu cầu đến phân bố theo hàm mũ, luật
quản lý hàng đợi là FIFO. Do đó xác suất có n yêu cầu đến hệ thống là:
p [n] = (rho) [n](1 - rho)
Và số yêu cầu trung bình trong hệ thống là:
L = rho/(1 - rho)
Số yêu cầu trong hàng đợi là:
L [q] = (rho) [2]/(1 - rho)
Thời gian đợi trung bình trong hàng đợi là:
W [q] = (λ )/[mu(mu - λ )]
13
Nguyen Tai Hung – Packet Switching Engineering
- Hanoi University of Technology – Faculty of Electronic & Telecommunication
Department of Communication Engineering
Thời gian tổng cộng trung bình trong hệ thống là:
W = 1/(mu - λ )
Ví dụ: Xem xét 1 hệ thống hộp thư thoại (Voice Mail) của các tổng đài PBX. Có
một số lượng lớn user yêu cầu truy nhập hệ thống hộp thư thoại này, với phân
bố thời gian đến của các yêu cầu này là theo hàm mũ (ngẫu nhiên) và thời gian
trung bình giữa các yêu cầu là 500 ms. Thời gian trung bình truy nhập cơ sở dữ
liệu của hệ thống Voice Mail là 475 ms. Hỏi các user sẽ nhận được kiểu phục
vụ như thế nào?
ở đây, t [bar] = 0.500 và x [bar] = 0.475, do đó lambda = (1/t [bar]) = 2.0 và mu =
(1/x [bar]) = 2.105 vậy rho = λ/mu = 0.95
Xác suất để n user truy nhập hệ thống Voice mail cùng 1 lúc là:
p [n] = (rho) [n](1 - rho) = (0.95) [n](0.05)
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à:
14
Nguyen Tai Hung – Packet Switching Engineering
- Hanoi University of Technology – Faculty of Electronic & Telecommunication
Department of Communication Engineering
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, các bộ nhớ đệm trong các FEP (Front-End Processor),.... ở đây cần có
lý thuyết xếp hàng do các loại dịch vụ khác nhau trong hệ thống yêu cầu số vị trí
trong bộ đệm khác ngau, hơn nữa cũng có rất nhiều yêu cầu bị tắc nghẽn trong
hệ thống. Người thiết kế cần phải biết bao nhiêu yêu cầu không được phục vụ,
số server cần thiết,....
Xác suất có n yêu cầu đến hệ thống (tất nhiên n
- Hanoi University of Technology – Faculty of Electronic & Telecommunication
Department of Communication Engineering
( trực bàn điện thoại viên) ( ở đây K=5). Khi bàn điện thoại viên bận, các cuộc
gọi được chờ trong hàng đợi bằng các câu thông báo ( ví dụ, “ Xin quí khách vui
lòng chờ trong giây lát”); Tuy nhiên do chỉ có 5 đường trong vòng quay nên chỉ có
chỉ có nhiều nhất 5 khách hàng có thể chờ trong hệ thống tại một thời điểm bất
kỳ (1 được phục vụ và 4 nằm chờ). Các dữ liệu tập hợp được cho thấy:
λ = 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 ( nhưng 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.
Để 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,... .
Các phương trình để đo lường hiệu suất của hệ thống hàng đợi đa server này
mặc nhiên rất phức tạp, nhưng trong thực tế người ta đưa ra biểu thức đại s ố
đơn giản có thể lập chương trình để tính hệ số sử dụng của nó là:
rho = λ/(c)(mu)
16
Nguyen Tai Hung – Packet Switching Engineering
- Hanoi University of Technology – Faculty of Electronic & Telecommunication
Department of Communication Engineering
Lưu ý rằng: n! = n(n - 1)(n - 2)(n - 3) ... (3)(2)(1); ví dụ, 5! = (5)(4)(3)(2)(1) = 120.
Để tiện tính toán, ta định nghĩa r = λ/mu. Do đó các phương trình quản lý hàng
đợi kiểu FIFO là:
p [n] = (λ) [n]p [0]/[n!(mu) [n]], khi n nằm giữa 1 và c,
và
p [n] = (λ) [n]p [0]/[(c) [n - c]c!(mu) [n]], khi n > c
Trước hết phải tính p [o] :
po = 1/[(r [n]/n!) + cr [c] /c!(c - r)].
n=0
Ký hiệu r [n]/n! là viết tắt toán học của biểu thức:
1 + r + r [2]/2 + r [3 ]/6 + r [4]/24 + ... + r [c ] - 1/(c - 1)!.
Thời gian đợi trung bình trong hệ thống là:
W = {r [c](mu)/(c - 1)![c(mu) - λ] [ 2]}p [0] +1/mu;
Từ phương trình của Little thì số khách hàng trung bình trong hệ thống là:
L = (λ)W.
Ví dụ sau đây cho thấy các biểu thức trên hết sức đơn giản:
Một Server quản lý việc in ấn trong một mạng LAN có 3 máy in. Server này s ẽ
quản lý các yêu cầu in trên 3 máy in trên. Trung bình có 6 yêu cầu in trong 1 phút,
và mổi máy in có thể in trung bình 3 công việc trong 1 phút. Người ta cần xác
định 2 thông số sau đây:
1. Thời gian trung bình một công việc in tiêu tốn trên hệ thông server
2. Trung bình có bao nhiêu công việc in đang đợi
ở đâ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.
17
Nguyen Tai Hung – Packet Switching Engineering
- Hanoi University of Technology – Faculty of Electronic & Telecommunication
Department of Communication Engineering
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 đề nhưng lại không biết liệu một mô hình
nào đó đã được giải quyết rồi hay chưa 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, nhưng 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, nhưng 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, nhưng 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
6. Các ứng dụng
Các nhà lập kế hoạch và thiết kế mạng thường xuyên gặp 6 nhiệm vụ sau:
• Cung cấp 1 kết nối hiệu quả về chi phí giữa 2 vị trí
• Đánh giá và tham gia vào các công nghệ mới
• Xác định sự tương thích giữa các phần tử mạng
• Đảm bảo rằng mạng có đủ dung lượng để đảm bảo được băng thông yêu
cầu
• Đảm bảo độ trễ đầu cuối đến đầu cuối hoặc thời gian đáp ứng đủ bé.
•
7. Kết luận
8. Tham khảo
18
Nguyen Tai Hung – Packet Switching Engineering
nguon tai.lieu . vn
