Bài giảng Cơ sở truyền số liệu: Chương 2 - ĐH Bách Khoa Hà Nội

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:12

Thêm vào BST

Báo xấu

32
lượt xem 4
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Bài này cung cấp cho người học những kiến thức cơ bản về mạng hàng đợi. Những nội dung chính được trình bày trong chương này gồm có: Mạng Jackson/nối tiếp, dãy sự kiện ra, trạng thái mạng hàng đợi. Mời các bạn cùng tham khảo đề cương để biết thêm các nội dung chi tiết về môn học.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Bài giảng Cơ sở truyền số liệu: Chương 2 - ĐH Bách Khoa Hà Nội

om .c ng co an th Mạng hàng đợi ng o du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
Cơ bản • Trong thực tế, hệ thống viễn thông thường được om .c mô hình hóa bằng một tập hợp nhiều hàng đợi ng co • Một mạng hàng đợi được định nghĩa bằng k nút an th mạng, mỗi nút mạng i là một hệ thống hàng đợi ng o đơn bao gồm 1 hàng đợi và ci server. Các yêu cầu du u cu đi vào hàng đợi tại một số nút xác định và đi ra từ một số nút khác • Điều khiển luồng và kiểm soát tắc nghẽn trong CuuDuongThanCong.com https://fb.com/tailieudientucntt
Cơ bản • Giả thiết dòng lưu lượng đi vào nút i tuân theo phân bố Poisson với tham số γ i om • Tốc độ phục vụ của server tại nút mạng j tuân theo .c phân bố poisson với tham số μ j ng co • Xác suất để 1 yêu cầu sau khi rời nút i được gửi tới nút an j là rij (gọi là xác suất định tuyến); xác suất để nó rời th khỏi mạng là ri0 ng o du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
Mạng Jackson/nối tiếp • Mạng Jackson đóng: γi = 0; rj0 = 0 i, j om • Mạng Jackson mở: .c ng γi  0; rj0  0 i, j co • Mạng nối tiếp (serial network). Thực chất là trường hợp an riêng của mạng Jackson mở: th ng γi = λ, i =1 rij =1, j =i +1;1 i  k 1 o  du   p, i =k; j =1 u  cu  0, i 1 1 p, i =k; j =0 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Dãy sự kiện ra • Định lý: đối với hàng đợi M/M/c/∞, nếu tiến trình đến tuân theo phân bố mũ tham số λ thì thời gian giữa hai sự kiện liên om tiếp ở đầu ra cũng tuân theo phân bố mũ với cùng tham số. .c Tức là: ng P {T ≤ t }= 1 − e− λ t co an trong đó T là thời gian giữa 2 sự kiện ở đầu ra trong th khoảng thời gian cho trước ng Chứng minh: Đặt o FT (t)= PT  t du u  cu Có PT  t  1   PN (t )  n  T  t   n 0   PT t  CuuDuongThanCong.com https://fb.com/tailieudientucntt
Dãy sự kiện ra • Viết: P[N(t)= n] [T > t]= Fn(t) om • Có hệ phương trình: .c  Fn (t + dt ) = (1  dt )(1  cdt ).Fn (t )  dt (1  cdt ).Fn 1 (t ); n  c ng  Fn (t + dt) = (1  dt )(1  ndt ).Fn (t )  dt (1  ndt ).Fn1 (t ); 1  n < c co  F0 (t + dt ) = (1  λdt ) F0 (t ) an  th • Hay ng  dF n ( t ) =  ( λ + c μ ). F n ( t ) + λF n  1 ( t ) ; n  c o  du dt   dF n (t) u  =  ( λ + n μ ). F n t + λF n  1 ( t ) ; 1  n < c cu  dt  dF 0 ( t )  =  λF 0 ( t )  dt CuuDuongThanCong.com https://fb.com/tailieudientucntt
Dãy sự kiện ra • Từ đó: Fn(t)= pn.eλt   om • Nên: FT (t)=1  pn.eλt =1 eλt  pn =1 eλt .c n=0 n=0 ng co an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trạng thái mạng hàng đợi • Như vậy, có thể tách hệ thống hàng đợi nối tiếp thành tập hợp các hàng đợi đơn thông thường (tiến trình ra om của hàng đợi phía trước chính là tiến trình đến của .c hàng đợi ngay sau nó) ng • Định nghĩa trạng thái của hệ thống hàng đợi: co S n ,n ,... ,n = N 1 = n1 ; N 2 = n 2 ;... ; N k = n k  an 1 2 k th • Và: ng   o P S n ,n ,... ,n = p n ,n ,..., n du 1 2 k 1 2 k u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trạng thái mạng hàng đợi • Trong mạng Jackson mở, tổng lưu lượng đi vào nut i được tính theo công thức: om k λi = γ i +  r ji λ j .c j= 1 ng • Định nghĩa: λi co ρi = μi an th ng • Ta có: o du k u ni pn = pn ,n ,...,n =(1 ρi )ρ cu 1 2 k i i=1 CuuDuongThanCong.com https://fb.com/tailieudientucntt
Trạng thái mạng hàng đợi • Trong mạng Jackson đóng: k om ni pn = p n ,n ,...,n = C  ρ i 1 2 k .c i=1 • Trong đó: ng λi co ρi = μi an th • Và: ng o du 1 1 C= = u n1 n2 nk k ρ ρ ... ρ cu ni 1 n1 , n 2 ,..., n k 2 k  ρ n1 , n 2 ,..., n k i=1 i CuuDuongThanCong.com https://fb.com/tailieudientucntt
Bài tập om .c ng co Cho một hệ thống thông tin được mô hình hóa bằng mạng hàng đợi như hình vẽ. Mỗi trong số hai nguồn S1 và S2 phát ra các yêu cầu với số an lượng tuân theo phân bố Poisson. Các yêu cầu được đưa ra từ nguồn th S1 và S2 với tốc độ trung bình tương ứng là 25 và 40 yêu cầu/giây. Giá ng trị phần trăm (50% và 20%) ghi trên mỗi luồng cho biết tỉ lệ phần trăm o các yêu cầu thoát ra từ hàng đợi phía trước được đưa vào luồng đó. du Thời gian phục vụ mỗi yêu cầu tại mỗi đơn vị hàng đợi tuân theo phân u bố mũ, có trị trung bình là 0,012 giây tại Q1, 0,009 giây tại Q2 , 0,015 cu giây tại Q3, 0,01 giây tại Q4, và 0,008 giây tại Q5. Giả thiết không gian các hàng đợi là đủ lớn, hãy: 1.Tính chiều dài trung bình của mỗi hàng đợi; 2. Tính thời gian lưu lại trung bình của mỗi yêu cầu tại mỗi đơn vị. CuuDuongThanCong.com https://fb.com/tailieudientucntt
Lời giải om .c ng co an th o ng du u cu CuuDuongThanCong.com https://fb.com/tailieudientucntt