TRƯỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP
KHOA ĐIỆN TỬ
BỘ MÔN ĐIỆN TỬ VIỄN THÔNG
BÀI THẢO LUẬN
TỔ CHỨC MẠNG VIỄN THÔNG
Sinh viên : Nguyễn Mạnh Tuấn
MSSV
: DTK0851030289
Lớp
: K44DVT02
THÁI NGUYÊN – 2011
1
NHẬN XÉT CỦA GIÁO VIÊN
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
....................................................................................................................................
2
YÊU CẦU
1. Chất lượng dịch vụ QoS.
2. Các kỹ thuâ tâ hàng đợi.
3. Phân tích mô ât hàng đợi đơn.
4. Tổng kết và so sánh các thuâ ât toán.
I. Chất lượng dịch vụ QoS
Chất lượng dịch (QoS) vụ là một thành phần quan trọng của các mạng gói đa dịch vụ.
Các mạng hỗ trợ QoS có thể cung cấp đồng thời các loại dịch vụ khác nhau bằng cách xử
lý hợp lý lưu lượng ở các điểm tắc nghẽn.
Để đánh giá chất lượng dịch vụ của mạng IP người ta dựa vào các tham số sau
đây:
Tỷ lệ mất gói: tham số này cho biết tỷ lệ phần trăm số gói IP bị mất trên
tổng số toàn bộ số gói IP đầu gửi đã chuyển vào mạng cho phía đầu nhận.
Độ trễ gói: tham số này cho biết khoảng thời gian gói IP được chuyển từ
đầu gửi đến đầu nhận.
Độ biến thiên trễ (jitter): tham số này cho biết sự dao động về độ lớn của độ
trễ gói.
Khả năng đáp ứng của dịch vụ: tham số này cho biết xác suất sử dụng thành
công dịch vụ.
Để đảm bảo chất lượng dịch vụ cho mạng IP người ta đưa ra các biện pháp khắc
phục sau:
Cải thiện băng thông: Nâng cấp đường truyền vật lí; Xác định mức độ ưu
tiên các gói tin; Nén các packet or frame cho nhỏ gọn
3
Độ trễ: Chia nhỏ links hoặc nén chúng lại; Áp dụng thuật toán hàng đợi
Độ tin cậy: Nâng cấp đường truyền vật lý, tránh tắc nghẽn; Đảm bảo băng
thông cho các gói tin quan trọng; Loại bỏ ngẫu nhiên các gói tin không quan trọng
gây tắc nghẽn.
Các giải pháp QoS:
Cấu trúc Best-Effort: dữ liệu đi vào mạng đều tuân theo quy tắc FIFO.
Không có sự đối xử nào của QoS đối với dữ liệu
Cấu trúc Guaranteed Services: dữ liệu đi qua mạng được dành riêng 1 băng
thông chắc chắn cho dữ liệu. Thực hiện thông qua cơ chế RSVP và CBWFQ của
QoS.
Cấu trúc Differentiated Services: dữ liệu đi vào mạng được phân loại thành
các lớp khác nhau để phân loại cách đối xử của mạng đối với dữ liệu. Thực hiện
thông qua các tool QoS là PQ, CQ, WFQ và WRED.
Cơ chế thực hiện QoS
Classificaion: phân loại gói tin theo mức độ quan trọng của dịch vụ, mức
ưu tiên từ thấp đến cao
Making: Đánh dấu các gói tin thuộc lớp thông tin nào, dùng 3 bits header
của gói tin để đánh dấu
Congestion Management: Áp dụng các thuật toán hàng đợi
Congestion Avoidance: Thực hiện loại bỏ ngẫu nhiên 1 số gói tin khi mà
hàng đợi đạt đến 1 con số định trước nhưng chưa đầy.
Policing & Shaping: sử dụng một giỏ đựng thẻ tại nút, số lượng thẻ được
qui định trước theo khả năng của nút, mỗi gói tin sẽ được cấp 1 thẻ, sau khi được
xử lí xong thì trả lại thẻ cho giỏ. Nếu gói tin đến mà trong giỏ không còn thẻ thì:
+ Cơ chế policing bỏ gói tin đó đi và yêu cầu ruyền lại sau
+ Cơ chế Shaping chuyển gọi tin đó vào hàng đợi -> cần bộ đệm lớn
4
Link Fragmentaion & Interleaving: Phân nhỏ các gói tin thành nhiều gói tin
nhỏ hơn để giảm đỗ trễ trong khoảng thời gian truyền các gói tin
Compression: các gói tin có thể có các header giống nhau nên việc xử lí
gói tin có thẻ giam bằng cách chỉ đọc header của gói đầu.
II. Các kỹ thuâ ât hàng đợi
a. Hàng đợi trong Router
Lý thuyết hàng đợi nảy sinh một cách tự nhiên trong việc nghiên cứu các chuyển mạch
kênh, và chuyển mạch gói. Trong các mạng chuyển mạch kênh, cuộc gọi đến chuyển
mạch ngẫu nhiên, mỗi cuộc gọi sẽ giữ kênh trong một khoảng thời gian ngẫu nhiên nào
đó. Trong mạng chuyển mạch gói, các gói tin với các chiều dài khác nhau đi qua mạng,
tài nguyên mạng (các chuyển mạch,kết nối sẽ được chia sẻ cho các gói). Các bản tin được
định tuyến đến các node tiếp theo. Thời gian sử dụng bộ đệm (trễ hàng đợi) là một vấn
đề quan trọng trong truyền dẫn thông tin. Thời gian này phụ thuộc vào các thời gian xử
lý, độ dài bản tin hay thời gian chờ xử lý khi chưa có tài nguyên sử dụng.
Trong các ứng dụng tương tác và thời gian thực thì thời gian trả lời trung bình được
xem như một tiêu chuẩn quan trọng còn trong các ứng dụng khác thì thông lượng lại là
điều quan trọng nhất. Việc mô tả hàng đợi theo lý thuyết toán học rất phức tạp nên ta chỉ
mô tả chúng theo mô hình đơn giản được sử dụng trong các mạng IP:
arrivals
Dispatching
Queue
departure
s
discipline
Server
λ =arrival rate
Ts= service time
w=items wait
P= utilization
Tw=wait time
q= items in queuing system
Tq = queuing time
Mô hình hàng đợi đơn giản trong mạng
5
Tin tức (có thể là gói tin hay bản tin) đến hệ thống để yêu cầu phục vụ. Nếu server rỗi
thì gói tin sẽ được phục vụ ngay lập tức, ngược lại chúng sẽ được lưu giữ trong các hàng
đợi. Khi rời khỏi hàng đợi các gói sẽ được xử lý.
Các tham sốố cơ bản liên quan tới hang đ ơi
Tham số
Kí
hiệu
Chú thích
Tốc độ đến TB
λ
Thời gian gói tin đến hệ thống hàng đợi với
vận tốc λ trên một đơn vị thời gian(s)
Tốc độ rời khỏi TB
μ
Các gói tin rời khỏi hệ thống với tốc độ μ
trên một đơn vị thời gian
p
Là khoảng thời gian server bận do phải xử lý
lý,đo bằng P= λ /μ
Lw
Là số gói nằm trong hàng đợi trung bình
Hiệu suất sử dụng
dịch vụ
Độ dài TB
tại tất cả các thời điểm t
Thời gian đợi TB
Tw
Có hai định nghĩa:
Thứ nhất: được tính bằng tất cả thời gian gói
tin đến xử lý (bao gồm cả các gói không phải
chờ trong hàng đợi)
Thứ hai: chỉ tính TB thời gian các gói tin
phải chờ trong hàng đợi
Thời gian phục vụ TB
Ts
Thời gian TB giữa thời điểm gửi gói tới
server và thời điểm rời khỏi server
Độ dài hàng đợi TB
Lq
Số gói trung bình trong hệ thống, bao gồm
các gói đang được sử dụng và các gói đang
chờ trong hàng đợi.
Thời gian xếp hàng TB
TB
Tq
Thời gian các gói ở trong hệ thống.
Bảng các tham số cơ bản của hàng đợi
6
Các gói đến hàng đợi với tốc độ thay đổi λ và đây là một quá trình poisson, thời giạ
phục vụ có phân bố mũ tốc độ μ (thực chất là thời gian trung bình mà các gói tin rời khỏi
hàng đợi). Khi các gói đến hệ thống tăng thì hiệu suất sử dụng hệ thống cũng tăng, dẫn
tới tắc nghẽn có khả năng xảy ra. Với p =1 thì các server bão hoà do đó tốc lớn nhất theo
lý thuyết mà hệ thống có thể xử lý được là:
λmax= 1/Ts
Tại λmax thì kích thước hàng đợi rất dài không thể kiểm soát được. Trong thực tế thời
gian trả lời và những yêu cầu kích thước hàng đợi giới hạn tốc độ đầu vào của thông tin
là 70-90% so với λmax theo lý thuyết.
Để hiểu rõ về các hàng đợi được sử dụng trong có chế điều khiển tắc nghẽn ta phải trả
lời các câu hỏi:
Các gói sẽ được lắp đặt như thế nào trong hàng đợi.
Thứ tự hay cách thức nào mà các thiết bị mạng phục vụ các hàng đợi
của chúng.
Các hoạt động nào của mạng để đối xử với các bó lưu lượng và hàng
đợi bị tràn.
Router được xem như hộp lớn, trong đó có các thành phần thực hiện việc truyền thông
tin. Trong ví dụ này ta xét router có 2 giao diện. Gói tin đi từ mạng A tới mạng B. Mạng
A tiếp xúc với router qua giao diện IF0, mạng B tiếp xúc với router qua giao diện IF1.
Sau khi các gói được đưa đến từ giao diện IF0 sẽ được đặt vào trong hàng đợi queue 0
(hàng đợi đầu vào). Tiếp theo các gói đi vào trong router và được định hướng tới router
kế tiếp dựa trên địa chỉ đích lưu giữ trong phần header của gói tin,một số gói tin đi ra từ
hàng đợi queue 0 được đưa vào hàng đợi queue 1 kết nối với giao diện IF1. Hàng đợi
queue1 còn gọi là hàng đợi đầu ra.
Có rất nhiều kĩ thuật hàng đợi: FIFO (first in first out), PQ (priority queue-hàng đợ ưu
tiên), FQ (fair queue-hàng đợi cân bằng). FIFO đây là kĩ thuật xếp hàng vào trước ra
trước cơ bản. Các gói đến trước sẽ là các gói đầu tiên được xử lý. Khi hàng đợi đầy và có
tắc nghẽn xảy ra thì các gói đến sẽ bị loại bỏ. Hàng đợi FIFO dựa vào hệ thống đầu cuối
để điều khiển tắc nghẽn thông qua cơ chế điều khiển tắc nghẽn. Do loại hàng đợi này rất
7
đơn giản nhiều khi không điều khiển được tắc nghẽn nên ta thường xét các loại hàng đợi
hiệu quả hơn: hàng đợi ưu tiên(PQ), hàng đợi cân bằng (FQ), hàng đợi có trọng số (WQ).
b. Hàng đợi FIFO (First In First Out)
FIFO là hàng đợi mặc định được sử dụng trong hầu hết các router trên thế giới. Hoạt
động của FIFO. Các gói đến từ các luồng khác nhau được đối xử công bằng bằng cách
đưa vào các hàng đợi theo trật tự đến (gói nào đến trước sẽ được đưa vào trước và được
phục vụ trước).
Hoạt đô ông của hàng đợi FIFO
của cisco, khi không có kế hoạch hàng đợi nào khác được cấu hình, thì tất cả các giao
diện(ngoại trừ các giao diện có tốc độ bằng hoặc nhỏ hơn luồng E1) đều sử dụng hàng
đợi FIFO mặc định. Tốc Hàng đợi hoạt động như một nơi lưu giữ các gói để tránh việc
loại bỏ các gói không cần thiết khi có dấu hiệu của tắc nghẽn. Khi có tắc nghẽn xảy ra, và
hàng đợi tràn thì tất cả các gói đến sẽ bị loại bỏ. Hàng đợi FIFO được sử dụng hầu hết
trong các router, nó đơn giản do không phải định cấu hình cho nó mà chỉ việc sử dụng
luôn. Trong các router độ xử lý gói phải nhanh hơn tốc độ các gói đến hàng đợi IF0 thì
mới tránh được hiện tượng tắc nghẽn trong mạng (hàng đợi IF1 rỗng), khi tốc độ xử lý
quá thấp hơn so với tốc độ các gói vào, có nghĩa là tốc độ ra nhỏ hơn tốc gói vào (hàng
đợi đầu ra dễ bị tràn) thì sẽ xảy ra tắc nghẽn khi có quá nhiều gói đi vào trong mạng, và
khi vấn đề này xảy ra thì các gói đến sau sẽ bị loại bỏ.
8
c. Hàng đợi ưu tiên PQ (Priority Queue)
Kĩ thuật này được sử dụng trong trường hợp đa hàng đợi, mỗi hàng đợi có một mức ưu
tiên khác nhau, hàng đợi nào có mức ưu tiên cao nhất sẽ được ưu tiên phục vụ trước. Khi
có tắc nghén xảy ra thì các gói trong các hàng đợi có độ ưu tiên thấp sẽ bị loại bỏ. Có một
vấn đề đối với kĩ thuật này: khi các hàng đợi có độ ưu tiên cao quá nhiều thì các gói trong
hàng đợi có độ ưu tiên thấp sẽ không bao giờ được phục vụ. Các gói được phân loại và
được sắp xếp vào hàng đợi tuỳ thuộc vào thông tin bên trong các gói. Tuy nhiên kĩ thuật
này dễ bị lạm dụng bởi người sử dụng hay các ứng dụng do ấn định các độ ưu tiên không
cho phép.
Cơ chế hàng đợi đầu ra ưu tiên có thể được sử dụng để quản lý lưu lượng từ tất cả các
giao thức trong mạng. PQ cung cấp cách đối sử ưu tiên cho các luồng lưu lượng có độ ưu
tiên cao, chắc chắn rằng các luồng lưu lượng then chốt khi qua các kết nối WAN sẽ đạt
được độ ưu tiên cao.
Cơ chế làm viê ôc của PQ
Các gói được phân loại như thế nào trong kĩ thuật PQ
Danh sách ưu tiên là một tập các luật lệ mô tả các gói sẽ được ấn định các độ ưu tiên
như thế nào trong các hàng đợi. Ngoài ra nó cũng có thể mô tả độ ưu tiên mặc định hoặc
giới hạn kích thước hàng đợi của các hàng đợi ưu tiên.
Các gói được phân loại theo:
9
Loại giao thức hoặc giao thức con
Giao diện đầu vào
Kích thước các gói tin
Các Fragment
Danh sách truy nhập
Tất cả các lưu lượng dùng để quản lý và điều khiển mạng đều được ấn định độ ưu tiên
cao nhất để trong trường hớp có tắc nghẽn xảy ra thì chúng được ưu tiên truyền trước.
Các lưu lượng không được ấn định mức ưu tiên nào thì được đưa vào các hàng đợi bình
thường.
PQ cung cấp thời gian đáp ứng nhanh hơn so với các kĩ thuật hàng đợi khác. Mặc dù
có thể ấn định các độ ưu tiên cho các hàng đợi tại bất kì giao diện đầu nào nhưmg nó
thường được sử dụng cho các lưu lượng có băng thông thấp.
d. Hàng đợi cân bằng FQ (Fair Queue)
Kĩ thuật này giải quyết vấn đề một số hàng đợi không được phục vụ trong một thời
gian dài do tài nguyên dùng để phục vụ cho các hàng đợi có độ ưu tiên cao hơn. Thuật
toán Round Robin trong lập lịch được dùng để phục vụ tất cả các hàng đợi một cách công
bằng. Kĩ thuật này ngăn chặn một số nguồn dùng quá nhiều tài nguyên của mạng mà
không chia sẻ cho các nguồn khác. Các vấn đề có thể xảy ra khi các gói có chiều dài thay
đổi, và các hàng đợi chỉ được cho phép giải phóng một gói tại một thời điểm. Lược đồ
định hướng một byte có thể được sử dụng để cân bằng các hàng đợi. Thêm vào đó một số
hàng đợi có thể bị đầy hơn các hàng đợi khác và chúng yêu cầu phải được phục vụ nhiều
hơn nhưng kĩ thuật hàng đợi cân bằng sẽ phục vụ mỗi hàng đợi công bằng
e. Hàng đợi cân bằng có trọng số WFQ (Weighted Fair Queue)
Thuật toán hàng đợi cân bằng có trọng số là một thuật toán nằm trong họ các thuật
toán hàng đợi cân bằng (FQ). Kĩ thuật này có thể được xem là sự phối hợp của hai kĩ
thuật hàng đợi cân bằng và hàng đợi ưu tiên. Tất cả các hàng đợi đều được phục vụ do đó
có thể tránh được tình trạng bỏ đói hàng đợi, tuy nhiên sẽ có một số hàng đợi được ưu
10
tiên phục vụ nhiều hơn. Một trọng số sẽ được gán cho một số hàng đợi để ấn định chỉ số
ưu tiên cao hơn cho chúng.
Hoạt động của hàng đợi WFQ
Khi các gói đến nó sẽ được phân loại bởi bộ phân loại và được ấn định tới một cửa.
Cửa này là một thực thể của hàng đợi mà cùng với các cửa khác được sắp xếp theo trật tự
của thuật toán round robin có trọng số. Chỉ theo cách này thì dịch vụ mới thực sự được
đối sử công bằng cho mỗi hàng đợi. Chìa khoá của sự phân loại là đàm thoại, điều này có
nghĩa là việc thể hiện trọng số để phân loại phụ thuộc vào thông tin nằm trong phần tiêu
đề gói tin (địa chỉ nguồn, địa chỉ đích, giao thức cổng nguồn, IP precedence). Bởi vì trong
thực tế không thể áp dụng một hàng đợi cho một cuộc đàm thoại, WFQ sẽ sử dụng thuật
toán Băm để chia cắt luồng lưu lượng ra thành các luồng nhỏ rồi đưa vào một số gới hạn
các hàng đợi được lựa chọn bởi người sử dụng hay được cố định bởi mặc định. Cách này
làm tăng số lượng lớn nhất có thể của các hàng đợi, thể hiện sự cân bằng của thuật toán.
Điều này có nghĩa là ta có thể có rất nhiều luồng cùng chia sẻ trong cùng một hàng đợi
(được thể hiện dựa trên màu sắc khác nhau của các gói trong hàng đợi). Khi các gói đến,
bộ phân loại sẽ kiểm tra thông tin trong phần header của gói tin và sử dụng các thông tin
này, tính toán số lượng nằm giữa 1 và số hàng đợi. Sau đó lắp đặt các gói này vào các
hàng đợi định nghĩa bởi các số này.
WFQ cung cấp sự quản lý ưu tiên lưu lượng động theo từng loại lưu lượng bên trong
các gói. WFQ có thể quản lý các luồng dữ liệu duplex, ví dụ như giữa các cặp ứng dụng,
và các luồng dữ liệu đơn giản như thoại và thoại và video. WFQ cung cấp giải pháp cho
11
các trường hợp yêu cầu thời gian nhất quán cho các người sử dụng mạng có tải nặng và
nhẹ giống như là không cung cấp thêm băng thông thừa. WFQ tự động tương thích để
thay đổi các điều kiện lưu lượng của mạng.
˖So sánh các kĩ thuật hàng đợi
Cơ
sở so
sánh
Hoạt
động
WFQ
PQ
+Ấn định trọng
số cho hàng đợi.
Luồng lưu lượng
có độ ưu tiên cao
được truyền trước
FQ
FIFO
+Ấn định độ ưu tiên
khác nhau cho từmg
hàng đợi phù hợp với
từng loại lưu lượng.
Hàng đợi có độ ưu tiên
+Hạn chế được cao nhất được truyền đầu
hiện tượng bỏ đói tiên
các hàng đợi có +Xảy ra trường hợp bỏ
độ ưu tiên thấp
đói các hàng đợi có độ
ưu tiên thấp
Loại Không được ấn Ưu tiên sử dụng cho các
lưu
định cho loại lưu loại lưu lượng yêu cầu độ
lượng lượng có độ trễ trễ latency thấp, do các
latency thấp. Do gói quan trọng sẽ được
thời gian phục vụ ấn định độ ưu tiên cao và
của hàng đợi luôn được truyền trước.
phục thuộcvào số
lượng gói có
trong hàng đợi
+Các hàng đợi +Gói
nào
được đối xử đến
trước
như nhau
được phục vụ
+Không xảy ra trước không
hiện tượng bỏ phân biệt loại
dịch vụ
đói hàng đợi
Cấu
hình
Không yêu cầu
thiết lập cấu
hình danh sách
truy nhập khi
Không yêu cầu
thiết lập cấu hình
danh sách truy
nhập khi quyết
Có yêu cầu cấu hình
12
Không được ấn
định cho loại
lưu lượng có độ
trễ latency thấp.
Do thời gian
phục vụ của
hàng đợi phục
thuộcvào
số
lượng gói có
trong hàng đợi
+Không có
hiện tượng
bỏ đói hàng
đợi
Sử dụng cho
mọi loại lưu
lượng, cung
cấp cách xếp
hàng nhanh
nhất và hiệu
quả đối với
các kết nối
có độ tắc
nghẽn
nhỏ
nhất.
Không yêu
cầu cấu hình
Bộ
lập
lịch
định luồng lưu
quyết
định
lượng nào sẽ
luồng
lưu
được truyền tại
lượng nào sẽ
cổng serial
được truyền
Sử dụng trong bộ Sử dụng trong bộ lập Sử dụng trong Ít sử dụng
lập lịch tương lịch ưu tiên chặt
bộ lập lịch trong bộ lập
thích
tương thích
lịch
So sánh các loại hàng đợi
III. Phân tích mô ât hàng đợi đơn
a. Ký hiệu Kendall
Ký hiệu Kendall được sử dụng rộng rãi để mô tả hệ thống xếp hàng
A/S/m/B/K/SD
A :phân bố của tiến trình đến
S :Phân bố của phục vụ
m :số kênh phục vụ
B :Kích thước bộ đệm
K : Quy mô mật độ (số các cuộc gọi đến)
SD :Thứ tự phục vụ các cuộc gọi đến hệ thống như thế nào! (Quy tắc phục
vụ). VD: FCFS, LCFS, SIRO....
Thời gian giữa các lần đến A và thời gian phục vụ S thường được giả
thiết là các biến số ngẫu nhiên độc lập và được phân bố đồng nhất, ký hiệu là
IID (Independent Identycaly Distributed)
ü Các tiến trình thông dụng :
13
M : Tiến trình mũ Markov (không nhớ)
D : Tiến trình tất định (thời gian như nhau)
G : Tiến trình chung
Er : Tiến trình Erlang bậc r
VD: hàn đợi thông dụng nhất như :M/M/1.M/D/1.M/M/h
M/D/1 :
- Tiến trình đến là hàm mũ
- Tiến trình phục vụ D
- Số Server là m=1
b. Quá trình Sinh-Tử (Birth-Death)
Trạng thái của hệ thống được biểu diễn bằng số các công việc n trong một hệ
thống
Khi có một công việc mới đến thì trạng thái của hệ thống sẽ thay đổi sang
n+1, khi có một công việc ra đi thì trạng thái hệ thống sẽ thay đổi sang n-1, ta
có lược đồ chuyển tiếp trạng thái là quá trình sinh tử.
n : Tốc độ của lần đến n
: Tốc độ của lần đi
Pn
01...n
P
0 1...n 0
14
Pn : Xác suất ổn định trạng thái n
c. Hàng đợi M/M/1
Lược đồ :
Tất cả các tốc độ đến đều là l , m
: Tốc độ của lần đến
: Tốc độ của lần đi
n
Pn
P0 n.P0
Pn : Xác suất ổn định trạng thái n
Po : Xác suất ổn định trạng thái 0
: Mật độ lưu lượng
Trong trừng hợp này số kênh phục vụ bằng 1, chỉ có 1 server
Các công thức tính toán :
-
Xác suất có n job trong hê â thống.
Pn 1 n ; n 1, 2, 3,...
P0 1
15
-
Số lượng trung bình các job trong hệ thống
L E n
2
Phương sai: n
1
2
1
Tham số thời gian :
-
Thời gian trung bình của 1 job trong hệ thống :W
W
-
1
1
Thời gian phục vụ trung bình cho một job : WS
Ws
-
L
1
Thời gian trung bình của job trong hàng đợi
Wq W Ws
2
1 1
Chiều dài hàng đợi :
-
Số lượng trung bình các job trong hệ thống
L
-
1
Số lượng trung bình các job trong server : L S
Ls P n 1 1 P n 0 1 1
-
Số lượng trung bình của các công việc trong hàng đợi L q
16
2
Lq L Ls
1
d. Hàng đợi M\M\1\K
Với số công việc (job) là k:
n
Pn P0 ; 0 n k
Pn 2 1 1 k 1
k 1 k 1
L
1
1 k 1
Xác suất job đến hệ thống bị từ chối là PK
Tốc độ thực tế đến hệ thống ' 1 Pk
Mật độ lưu lượng '
1 Pk
e. Hàng đợi M\M\C
17
n
1
Pn P0 ;0 n C
n!
n
1
Pn
P
C !C nc 0
1
c
c 1
cp
n 1
P0 cp
n ! c ! 1
n 0
c
-
P cp
Xác suất xuất hiện hàng đợi Pq 0
; công thức Erlang
c ! 1
-
Độ dài hàng đợi : Lq Pq
-
Thời gian đợi : Wq
1
Lq
IV. Các thuâ ât toán tìm đường
a. Thuâ ât toán kruskal
Các bước của thuật toán:
- Cho đồ thị có các tập các nút và các cạnh (cạnh……)
Bước 1: Sắp xếp tất cả liên kết theo giá thấp tới cao vào bảng giá liên kết
Bước 2: Kiểm tra tất cả các nút đã kết nối với nhau chưa?
+)Nếu có thì dừng
+)Nếu không thì tiếp tục
Bước 3: Đánh dấu liên kết đầu tiểntong bảng liên kết
Bước 4: Nếu không còn liên kết nào mà chưa kết nối thì dừng.
18
Bước 5: Kiểm tra liên kết đánh dấu có tạo vào hay không?
+)Nếu có thì bỏ ra khỏi bảng liên kết
+)Nếu không thì thêm vào đồ thị, bỏ khỏi bảng liên kết. Quay trở lại bước 2.
b. Thuâ ât toán Prim
Mục đích: Tìm cây MST
Các bước:
- Phát triển cây từ một nút ban đầu trong mạng.
- Có các bước kế tiếp nhau.
- Ở mỗi 1 bước tìm nút mới thêm vào cây bằng cách chọn 1 liên kết có độ dài nhỏ nhất
(liên kết nối giữa nút thuộc cây và 1 nút không thuộc cây)
c. Thuâ ât toán Dijkstra
Mục đích là tìm cây PTS (path shortest tree)
Xây dựng cây nối từ nút nguồn đến tất cả các nút khác trong mạng sao cho đường đi từ
nút nguồn đến mọi nút là ngắn nhất.
Điều kiện :
N = tập các nút trong mạng
C : nút nguồn ( trung tâm)
M :tập các nút đã xác định được đường dẫn ngắn nhất
dij :giá liên kết từ nút i j ;dij=0, dij=nếu i,j không nối trực tiếp với nhau
Ln: giá của đường dẫn ngắn nhất từ nút C đến nút N
Các bước :
1)Khởi tạo M= C
Ln =dCn cho nc
2)Với mọi wN ; Lw =m.n.Lj với jM thêm w vào M
19
3) Tính toán :Ln=m.n(Ln, Lw+dwn) với mọi n không thuộc M
d. Thuâ ât toán Mentor
- Dùng thiết kế mạng Backbone, mạng đa dịch vụ, mạng phân tán.
- Là thuật toán lai ghép giữa MSTvà pST
-Bước 1:tìm tâm c của mạng :
Mi =Cijwj
Mi =min =>i là tâm C của mạng
N : số nút của mạng
wj: trọng số của nút j
Cij :giá liên kết (i;j)
Wj = (r kj +r jk ) r jk :lưu lượng từ nút jk
rkj :lưu lượng từ nút kj
-Bước 2: Tìm các nút Back bone trong mạng
- So sánh tất cả các Wi với W, nếu thoả mãn WjW thì gán i là nút Back bone
- Lấy i làm tâm quay vòng tròn tâm i bán kính R, thì các nút sau đây là nút truy nhập
của nút i .
Xét hàm:
Fj = Pc.D/Cjc + (1-Pc)W/wj
Cjc :giá từ nút j đến tâm c
D : đường kính mạng (khoảng cách giữa 2 nút trong mạng)
wj :trọng số
W :mức ngưỡng ; Pc=01
- Tính toán giá trị Fj cho tất cả các nút thuộc tập U nếu Fj lớn nhất thì chọn nút nút j
làm nút Back bone và lại quay vòng tròn tâm j bán kính r, các nút thuộc vòng tròn này là
các nút truy nhập và quá trình lại tiếp tục cho tới khi các nút nằm trong mạng
-Bước 3: Xây dựng cây kết nối giữa các nút Back bone với nhau.
Cây MST : Total Length = min
20
- Xem thêm -