Tài liệu Nâng cao chất lượng dịch vụ trong mạng atm

ĐẠI HỌC QUỐC GIA HÀ NỘI KHOA CÔNG NGHỆ NGUYỄN VĂN TOẢN NÂNG CAO CHẤT LUỢNG DỊCH v ụ• TRONG MẠNG ATM • » • Chuyên ngành: Công nghệ Diện tử - Viễn thông Mã số: LUẬN VĂN THẠC s ĩ KHOA HỌC HUỚNG DẪN KHOA HỌC: TS. TRAN HONG quân y _ .f r / \ ......... / ____ ______ H À NỘI - 2 0 0 2 M ỤC L Ụ C LỜI MỞ ĐẦU........................................................................................................................................ 1 CHUONG 1: CÁC QUÁ TRÌNH NGẪU n h iê n v à m ô h ìn h h à n g đ ợ i ........................3 1.1. Các quá trình ngẫu nhiên...........................................................................................3 1.1.1. Quá trình M arkov................................................................................................ 4 1.1.2. Quá trình biến đ ổ i ...............................................................................................5 1.1.3.Quá trình Poisson.......................................................................................6 1.1.4. Phương trình Chapm an-Kolm ogrov...................................................... 8 1.1.5. Phương trình cân bằng toàn cụ c.....................................................................9 1.2. Các loại hàng đợi........................................................................................................ 10 1.2.1. K hái niệm và định nghĩa.................................................................................10 1.2.2. Đ ịnh luật số b é ....................................................................................................14 1.2.3. C ác hàng đợi đơn lớp........................................................................................ 15 1.3. Các loại mạng hàng đợi...........................................................................................21 1.3.1. Định tuyến xác suất và định tuyến tiền định...........................................21 1.3.2. Phân loại mạng hàng đợi...............................................................................22 1.4. Các mạng hàng đợi đóng....................................................................................... 24 1.4.1. Định lý Jackson đối với mạng hàng đợi đóng........................................25 1.4.2. Tỉ số đi qua...........................................................................................................26 1.4.3. Đ ộ hiệu dụng tương hỗ....................................................................................27 1.5. Kết luân.......................................................................................................................... 27 CHUƠNG 2: CHẤT LUỢNG DỊCH v ụ TRONG MẠNG ATM ...............................................28 2.1. Giới thiệu....................................................................................................................... 28 2.2. Các loại hình dịch vụ................................................................................................ 29 2.2.1. D ịch vụ tốc đô bit không đổi C B R ............................................................ 29 2.2.2. D ịch vụ tốc độ bit thay đổi V B R .............................................................. 30 2.2.3. D ịch vụ tốc độ bit khả dụng A B R ............................................................. 30 2.2.4. D ịch vụ tốc độ khung đảm bảo G F R ........................................................ 31 2.2.5. D ịch vụ tốc độ không định trước Ư B R .....................................................31 2.3. Các tham số của chất lượng dịch vụ................................................................ 31 2 .3 .1 . T ỉ số mất tế bào C L R ..................................................................................... 31 2 .3 .2 . T ỉ số tế bào bị lỗi C E R ..................................................................................32 2 .3 .3 . Trễ truyền tế bào cực đại M ax-C T D ..........................................................33 2 .3 .4 . Sự thay đổi trễ tế bào đỉnh - đỉnh P 2P - C D V ........................................35 2 .3 .5 . Dung sai trễ tế bào và bùng phát C D V T -B T .......................................... 35 2.3 .6 . K ích thước bùng phát cực đại M B S ........................................................... 35 2 .3 .7 . Tỉ số nhóm tế bào đã bịlỗi nhiều nhất S E C B R .................................... 36 2.3 .8 . Tỉ số tế bào đến sai đích C M R ...................................................................36 2.4. Bản mô tả lưu lượng T D ..........................................................................................36 2 .4 .1 . T ố c độ tế bào đỉnh P C R ................................................................................. 37 2 .4 .2 . T ố c độ tế bào ổn định S C R ........................................................................... 37 2 .4 .3 . T ốc độ tế bào cực tiểu M C R .........................................................................38 2 .4 .4 . K ích thước khung cực đại M F S ...................................................................39 2.5. Quản lý lưu lượng T M ............................................................................................. 39 2 .5 .1 . Điều khiển chấp nhận liên kết C A C ..........................................................39 2 .5 .2 . Điều khiển tham số sử dụng Ư PC .............................................................. 40 2.6. Điều khiển dòng trong mạng A T M ....................................................................42 2.6.1. Thuật toán lịch trình ảo........................................................................... 44 2 .6 .2 . Thuật toán gáo rò..............................................................................................46 2.7. Kết luận......................................................................................................................... 46 CHUƠNG 3: ĐIỀU KHlỂN LIẴJ LUỢNG TRONG MẠNG ATM ......................................... 47 3.1. Nguyên lý tác dụng tối thiểu Potriagin.............................................................47 3.2. Hệ thống không ổn định......................................................................................... 52 3 .2 .1 . Phương trình hệ thống động......................................................................... 52 3 .2 .2 . Các tham số lối ra không ổn định.............................................................. 53 3 .2 .3 . Các hàm mục tiêu không ổn định.............................................................. 56 3.3. Điều khiển luồng tối ưu trong mạng A TM bằng mô hình luồng động. ..........................................................................................................................58 3 .3 .1 . Các luồng tối ưu trong các mạng chuyển mạch g ó i........................... 58 3 .3 .2 . Đ iều khiển tốc độ lưu lượng tối ưutrong c á c m ạng gói và A TM . 60 3.4. Đ ịnh tuyến tối ưu bẳng m ô hình luồng đ ộ n g ................................................... 67 3 .4 .1 . C họn đường tối ưu ch o chuyển m ạch k ê n h ............................................67 3 .4 .2 . Đ ịnh tuyến tối ưu trong m ạng A T M ........................................................... 73 3.5. K ết lu ận...............................................................................................................................81 CHƯƠNG 4: THUẬT TOÁN MAXMIN CÓ ĐIỂU K IỆ N ....................................................82 4.1. G iới th iệu ...........................................................................................................................82 4.2. Bài toán M axm in có điều k iện ................................................................................ 83 4.2.1 T ố i ưu L ex ico g rap h ic.......................................................................................83 4 .1 .2 Phát biểu bài t o á n .............................................................................................84 4 .1 .3 . M ạng m ở rộ n g ........................................................................................................85 4 .1 .4 . M axm in có điều k iện ..........................................................................................87 4.2. Thuật toán C P G .............................................................................................................. 90 4 .2 .1 . Phương pháp dự đoán liên kết đơn...............................................................90 4 .2 .2 . Đ ổ hình C P G .......................................................................................................... 92 4 .2 .3 . Thuật toán C PG trong trườnR hợp đa liên k ế t...........................................93 4.3. K ết luận.............................................................................................................................. 97 KẾT LUẬN.............................................................................................................................................98 CÁC T ừ VIẾT TẮT TÀI LIỆU THAM KHẢO PHỤ LỤC LỜI MỞ Đ ẦU Các m ạng tích hợp dịch vụ số băng rộng (B -ISD N ) cần một phổ rộng cho các ứng dụng thời gian thực như hội nghị truyền hình, video theo nhu cầu, ... Một trong những đặc tính quan trọng của những ứng dụng này là chúng đòi hỏi các yêu cầu về chất lượng dịch vụ (Q oS) phải được đảm bảo, công nghệ truyền dẫn không đổng bộ A T M đã được chọn làm giải pháp. Các vấn đề vể trễ, rung pha hay phân phối băng thông trong các mạng liên kết xác định là các tham số ảnh hưởng trực tiếp tới Q oS và có quan hệ hữu cơ với nhau. A TM đã có một số eiao thức tương tác điều khiển ở cấp mạng (phân phối băng thông), điều khiển b cấp cuộc gọi (điều khiển chấp nhận liên kết) và điểu khiển ở cấp tế bào (thuật oán gáo rò). Tuy nhiên, vấn đề tối ưu độ hiệu dụng của toàn mạng là bài toán ihức tạp, phi tuyến và phân tán. D o đó, một số các điều kiện về tài nguyên nạng trên tuyến sử dụng phải được áp đặt. M ột trong c á c bài toán đó là tìm ra một kết nối thoả mãn những yêu cầu 'ề chất lượng dịch vụ dựa trên thuật toán phân phối băng thông M ax-m in cân tối. Đây là m ột phương pháp có độ hiệu dụng cao, được A TM forum (Version .0) khuyến nghị. Tuy nhiên, để có được băng thông M ax-m in cân đối trên toàn lạng ỉà điều khó thực hiện khi lưu lượng dòng trên mạng đã cân xứng. Tốc độ ịnh trước với đặc điểm thay đổi số lưu lượng dòng được chọn ỉà giải pháp cho ác bài toán loại này. Mục đích của luận văn này là trên cơ sở nghiên cứu các quá trình ngẫu hiên và một số loại hàng đợi để tìm hiểu các tham sô' ảnh hưởng tới chất lượng Ịch vụ trong mạng A T M . Trên c ơ sở nghiên cứu cá c mô hình dòng, đặc biệt ià 5ng động và áp dụng nguycn lí tác dụng tối thiểu Pontriagin để cực tiểu thời an trễ và xác suất tắc nghẽn trong m ột hệ thống suy hao. Dựa trên thuật toán 'i ini L exicog rap h ic, bài toán M axm in có điều kiện C M M (Constrained axim in problem ) đối với tốc độ áp đạt cực tiểu (M R C ) và tốc độ áp đặt đỉnh ’R C ) đã được phát triển. 2 Cấu trúc của luận văn này gồm 4 chương: Chương 1 trình bày những lý luận về quá trình ngẫu nhiên mà trọng tâm à qúa trình Possion, m ột số loại hàng đợi, một số định lí quan trọng trong nạng hàng đợi đóng. Chương 2 giới thiệu cá c tham số ành hưởng tới chất lượng dịch vụ trong nạng A T M và m ột số giao thức điều khiển. Chương 3 trình bày về m ô hình luồng động và nguyên lí tác dụng tối hiểu Pontriagin nhằm đạt hiệu xuất mạng. Chương 4 trình bày bài toán M axm in có điều kiện C M M và kết quả. Đây à chương quan trọng trong việc từ tiếp cận đến giải quyết vấn đề chất lượng lịch vụ trong m ạng A T M . Chất lượng dịch vụ trong m ạng A T M là vấn đề rộng đang cẩn rất nhiều ghiên cứu, việc hoàn thành luận văn này không tránh khỏi có những thiếu sót, long nhận được những ý kiến đóng góp của những người quan lâm. 3 Chương 1 C Á C Q U Á T R Ì N H N G Ẫ U N H IÊ N VÀ M Ô H ÌN H H À N G Đ ỢI 1.1. C á c quá trình ngảu nhiên. Chúng ta xem xét các hệ thống theo thời gian và quan tâm tới cá c đáp ứng theo theo thời gian của chúng [7], M ột quá trình ngẫu nhiên X , (hoặc X (t)) là một tập cá c biến ngẫu nhiên theo tham số t (thường là thòi gian). M ột cách chính xác hơn, quá trình ngẫu nhiên là một ánh xạ từ không gian mẫu s theo hàm của t, mỗi phần tử e Ihuộc s tương ứng với hàm x,(e) [20], như vậy: - Với mồi giá trị e cho trước, x,(e) là hàm của thời gian. - Với mỗi giá trị t cho trước, X t(e) là một biến ngẫu nhiên. - Với một cặp e và t cho trước, x,(e) là một số cố định. K í hiệu T là không gian tham số, nó là tập các giá trị khả dĩ của t và X t dược gọi là không gian trạng thái hay tập c á c giá trị khả dĩ, khi đó ta có các khái niệm sau: - C ác chuỗi thời gian liên tục: Khi đó T là chu kỳ và tất cả cá c thời điểm trong chu kỳ đều là nhĩmg giá trị khả d7 của t. - C ác chuỗi thời gian rời rạc: Khi đó T là tập cá c thời điểm rời rạc với X N = X (tn ). - Quá trình trạng thái liên tục: Khi đó X (t) có thể nhận một trong số các giá trị khả dĩ của một tập biết trước. - Quá trình trạng thái rời rạc: X (t) nhận một trong số cá c giá trị của một tập rời rạc. K í hiệu X (t) là quá trình ngẫu nhiên trong trạng thái X ở thời điểm t. Một quá trình ngẫu nhiên X (t) hoàn toàn xác định nếu phân bố kết hợp của các biến ngẫu nhiên X (t,), X ( t2), thời gian tuần tự tj, t2, t X (tk) có thể được xác định đối với mọi tập hữu hạn k, nghĩa là: F j ( x , ĩ ) = P { X ( t , ) < x ...... X (t n) < x „ Ị với X = ( X j , X 2,...,Xn) _ t = ( t l , t 2 , . . . , t n) (1.1.1) 4 Ị .1.1. Quá trình Markov. M ột quá trình ngẫu nhiên được gọi là quá trình M arkov khi có tính chất sau (gọi là tính M arkov). P|X (t„*,) = x „ l |X ( tn) = x n, . . . , X ( t 1) = x l )} = P {X (t„ + i) = x „ n I X (t„ ) = x n} Vn, vt| < . .. < t„+1 Như vậy, trạng thái hiện tại của quá trình tại thời điểm tn+| chỉ phụ thuộc vào trạng thái của quá trình ở thời điểm trước đó tn (m à không phụ thuộc vào cách thức mà trạng thái này đạt được). Trạng thái hiện tại chứa đựng tất cả cá c thông tin cần thiết để xác định đáp ứng trong tương lai của qúa trình. X ác suất chuyển dịch từ trạng thái i sang trạng thái j là pj j = P { X n+ị = jl X n = i }. Các xác suất chuyển dịch tạo thành một ma trận chuyển dịch Cp, j) = p , trong đó: % 0 p = PlO P0,1 Pll (1 .1 .3 ) Hàng thứ i là x á c suất quá trình từ trạng thái i chuyển sang các trạng thái j với j = 0, 1.... Ma trận với c á c phần tử không ủm và tổng m ỗi hàng bằng 1 gọi là ma trận ngẫu nhiên. M ột quá trình M arkov tạo thành một chuỗi M arkov thuần nhất khi các xác suất chuyển dịch P Ị X n+l = jix„ = i } là như nhau đối với mọi n. K í hiệu P { X ll+1= A I X n = A } = p P ị X n+1* A I X n = A } = l - p Khi đó chúng ta có : P{ Hệ thống sẽ ở trạng thái A trong N đơn vị thời gian I trạng thái hiện tại của hệ thống là A } — pN. P{ Hệ thống sẽ ở trạng thái A trong N đơn vị thời gian trước khi rời khỏi trạng thái này Ị = pN( l - p). Như vậy, trong thời gian rời rạc, phân bố trôn có dạng hình học và thể hiện tính không nhớ sẽ thảo luận chi tiết hơn ở phần 1.1.3. 5 Hình Ị . Ị . ì : Thời gian rời rạ c và m ỏ hình trạng thái Trong trường hợp thời gian liên tục, giả thiết rằng hệ thống ở trạng thái A tại thời điểm t và tốc độ rời khỏi trạng thái A là |i. X ét thời điểm t + T , xác suất đê hệ thống ở trong khoảng thời gian từ t đến T là: P (H ệ thống ở trong trạng thái A trong khoảng thời gian T I trạng thái hiện tại A } = ( l - |aAt)T/At = e 'MT. Như vậy, trong thời gian liên tục, hàm phân bố theo thời gian mà hệ thống sẽ tồn tại trong trạng thái A khi hiện tại nó đang trong trạng thái này có dạng hàm mũ. ỉ . 1.2. Quá trình biến đ ổ i. Hình ỉ . ỉ .2: Mỏ hình quá trình biến đổi Là một chuồi M arkov đặc biệt, rời rạc theo thời gian và có cá c tính chất: - Tồn tại m ột không gian trạng thái rời rạc - C ác trạng thái có thể đếm được. - Chuyển dịch chỉ có thể xảy ra giữa c á c trạng thái liền kề nhau với các tốc độ chuyển dịch là: Pl.j - < X, khi j X á c suất chuyển trong khoảng At tới A-iÀt ịiị khi j X á c suất chuyển trong khoảng At tới fi,At 0 cá c giá trị Khi hệ thống ở cá c trạng thái khác 6 Ị. 1.3. Q uá trinh P oisson. Poisson là một loại quá trình M arkov hay quá trình đếm số các sự kiện riêng lẻ xảy ra một cách ngẫu nhiên trong một khoảng thời gian xác định trước. Chúng ta thường xem những sự kiện này là quá trình đến hàng đợi của khách hàng. K í hiệu Ntt là số khách hàng đến hàng đợi trong khoảng thời gian (t,x], quá trình ngẫu nhiên |N0llt > 0 } là m ột quá trình Poisson nếu với t và T > 0 và có cá c đặc điểm sau: 1. L à m ột quá trình thời gian thuần nhất, nghĩa là với số nguyên không âm k, P(N t t+I = k) là độc lập với X hay m ột cách tương ứng NTT+1 là phân bố N,„. 2. Là m ột quá trình tăng độc lập, nghĩa là N()T và NTT+, là độc lập với nhau. 3. Là một quá trình tuần tự, nghĩa là P(NTT+l > 2)/t —> 0 khi t —> 0T rên cơ sở này quá trình Poisson có c á c tính chất sau: Tính không nhớ Một quá trình Poisson với tham số X , thời gian để khách hàng đầu tiên đi vào hàng đợi kí hiệu là A và thời gian giữa c á c khách hàng đi vào hàng đợi đều là cá c biến ngẫu nhiên theo luật hàm mũ. P(A > t) = P(N OI= 0 ) = e ?'t (1 .1 .4 ) Rõ ràng P(A < t) = 1- e xt. K í hiệu thời gian giữa cá c khách hàng đi vào hàng đợi là T. Đ ê tính P (T > t) chúng ta có thể chứng minh rằng, với m ột khách hàng đi vào hàng đợi tại thời điểm t thì số khách hàng đi vào hàng đợi trong khoảng thời gian [t,T + t] là bằng 0. Tuy nhiên, biến ngẫu nhiên NS1 mô tả số khách hàng đi vào hàng đợi trong khoảng thời gian (s ,tj. Do vậy chúng ta giả thiết rằng có một khách hàng đi vào hàng đợi tại thời điểm t , do đó 7 P ( T > l ) = l i m P ( N T+h.T+h+t= 0 | N M + h = l ) -H m P O W ^ -O ) (115) = P(Not=0) = e ^ Phân b ố thời gian giữa các khách hàng đi vào hàng đợi có dạng hàm mũ là một quá trình Poisson. Ngược lại, số khách hàng đi vào hàng đợi xác định trong bất kỳ m ột khoảng thời gian nào là một biến ngẫu nhiên. C ác biến ngẫu nhiên phân b ố hàm mũ là những m ô hình thường gặp và không nhớ là một tính chất quan trọng của quá trình Poisson. Chúng ta nói một biến ngẫu nhiên T ià có tính không nhớ hay phân bố xác suất của T là có tính không nhớ nếu P (T > t + t IT > x) = P (T > t). Đ iều này nghĩa là xác suất theo thời gian của một khách hàng tiếp theo đi vào hàng đợi là độc lập với thời gian đã trôi qua khi có một khách hàns đi vào hàng đợi. Ngược lại, một biến ngẫu nhiên (liên tục) là có tính không nhớ khi và chỉ khi nó có phân bố dạng mũ âm. Tính quan sát ngẫu nhiên Tính quan sát ngẫu nhiên (Random O bserver Property - ROP) còn được gọi là tính P A ST A (P oisson Arrivals S ee Time A verages - C ác quá trình đi vào hàng đợi có phân dạng hàm Poisson) là trọng tâm của lý thuyết xếp hàng. G iả thiết quá trình ngẫu nhiên { X ,} có m ột khách hàng đi vào hàng đợi tại thời đ iể m T, tran g th ái c h u y ể n từ X sang X T trạng thái là phân bố của X t” • T í n h q u a n sát n g ẫu n h iê n c ủ a c á c t + độc lập với sự kiện có một khách hàng đi vào hàng đợi tại thời điểm X. T heo cách nói khác m ột khách hàng đi vào hàng đợi “nhìn thấy” hộ thống có một phân bố giống như phân bố mà một khách hàng “nhìn thấy” khi rời khỏi hàng đợi. Ta có thể giải thích cụ thể hơn như sau: Sự kiện có một khách hàng di vào hàng đợi trong khoảng thời gian (x h,T| là tương ứng với Nx. hI > 1 (0 < t < t ) nhưng sự kiện NT. ht > 1 lại độc lập 8 với quá khứ cho tới khi tại thời điểm T - h do tính không nhớ của hệ thống. Đ ặc biệt cá c sự kiện x t . h = X và NT, h, > I là độc ỉập với nhau, do đó: ( 1. 1.6) P ( X T_ h = x | N T_ h l ) = P ( X T_h = x ) cho lì - » 0 , phía trái của phương trình trên tiến tới xác suất của sự kiện một khách hàng mới đi vào hàng đợi “nhìn thấy” trạng thái X ta có: P( X = X và do đó chúng = X I khách hàng đi vào hàng đợi tại thời điểm x) = P( X t “ ' = X ). T ' Thời gian ch ờ trung binh Dựa trên nghịch lý đi nhờ xe [6], người ta đã tính được thời gian chờ trung hình của một hàng đợi là: X » rr 2 2 X đối với phân bố dạng hàm mü, ta có: (X)2 do đó w = X l.ỉ.4 . Phương trình Chapman-Kolmogrov. X á c suất để một qúa trình (hệ thống) bắt đầu từ trạng thái i và kết thúc ở irang thái j sau hai bước chuyển là ] T p . p sau n bước chuyển, ta kí hiêu là I,k k,j k pin). Với F ' = F " . F m(0 < m < n) ta có : ( 1. 1.8) Hình 1 .ỉ .3: S ơ đ ồ chuyển dịch từ trạng thái i tới trạnạ thái j sau k bước 1.1.5. Phương trình càn bằng toàn cục. Phương trình n = 7tP hay 7Tj = Z jT t jP j j với V j thường được gọi là điều kiện cần bằng (toàn cụ c). Khi Z iP i.j = 1, xác suất để hệ thống trong trạng thái j thực hiện m ột chuyển dịch sang trạng thái khác chính là xác suất mà hệ thống trong trạng thái khác thực hiện một chuyển dịch tr'i trạng thái j , hay ta có: M ỗi phương trình trên được viết cho một trạng thái j . Ý nghĩa của phương trình toàn cục là có bao nhiêu chuyển dịch từ trạng thái j thì có bấy nhiêu chuyển dịch tới trạng thái này. J J Hình Ị .Ị .4: S ơ đ ổ m ô tả phương trình cân bằng toàn cục Nếu c á c phương trình cân bằng đã biết thoả mãn tất cả các trạng thái ngoại trừ m ột trạng thái nào đó thì chúng cũng sẽ tự thoả mãn trạng thái này do tính bảo toàn của xác suất của đồ hình. Chúng ta sẽ đi tìm lời giải của phương trình này như sau: 10 - V iết tất cả cá c điểu kiện cân bàng cho tất cả ngoại trừ một trạng thái (nghĩa là có n -1 phương trình). K hi đó, cá c phương trình được gán bằng giá trị tương ứng của các xác suất cân bằng và nghiệm dược xác định tuỳ thuộc vào một hằng số. - Phương trình cuối cùng (tự thỏa m ãn) được thay thế bằng điều kiện chuẩn hoá Zj7ij = 1. M ột cách thực hiện khác là việt II lần điều kiện cân bằng 7teT = 1, như vậy 71. E = e trong đó E là một ma trận đơn vị nxn. Như vậy, với phương trình cân bằng ta c ó 7I.P = 71 hay 7r.(P + E - 1) = e. Từ đó n = e .(P + E - 1 )'1. C ó thể chỉ ra được rằng, lời giải phương trình cân bàng thuần nhất chỉ có một nghiêm duy nhất [7]. C ách tiếp cận trực quan phương trình cân bằng toàn cục này dể hiểu nhưng lời giải của nó khá phức tạp. Chúng ta quan tâm thêm một cách tiếp cận khác ở phần 1.2.1 sau đây. 1.2. C á c loại hàng đựi. 1.2.1. Khái niệm và định nghĩa. M ôi trường hàng đợi là một hê thống mà trong đó tắc nghẽn có thể xuất hiện do thiếu khâu phục vụ so với tổng số yêu cầu tức thời ị 1 ]. Hàng đợi là một khái niệm chỉ hệ thống mà trong đó các gói dữ liệu, cu ộc gọi, thẻ bài LA N (được gọi chung là khách h à n g )... xếp hàng để chò được phục vụ và rời khỏi hàng đợi khi phục vụ đã được hoàn thành. khách hàng đến hàng đợi khách hàng rời hàng đợi khi đã được phục vụ Hình Ị .2.1 : M ô hình hàng đợi m ột khâu phụ c vụ, sô khách hàng không xác định C ác loại hàng đợi là vấn đề chính trong cá c m ô hình máy tính và hệ truyền thông vì chúng thể hiện dung lượng của một nguồn. Các server tương đương với cá c nguồn, khách hàng đi vào hàng đợi là công việc, cá c bản tin hay cá c gói tin tạo nên khối lượng công việc của một hệ thống vật lý. Nhìn chung, một m ô hình chính xác hơn được xem là một mạng mà cá c hàng đợi thể hiện cá c nguồn đã thực hiện m ột số công việc. Bất kỳ hàng đợi nào cũng bao gồm ba thành phần: Quá trình đến xác định các khách hàng đến hàng đợi lúc nào và khả năng xảy ra của chúng. Bộ đệm (thường được xem như là chính hàng đợi) là nơi khách hàng chờ để được phục vụ. Thời gian phục vụ là thời gian một khách hàng được server phục vụ. Thời gian phục vụ một khách hàng thường được xem xét ở hai khía cạnh: nhu cầu của khách hàng và tốc độ phục vụ của serv er (đo bằng khối lượng công việc trong một đơn vị thời gian). Thời gian phục vụ thường được chia theo tốc độ, m ột trong cá c đại lượng này hoặc cả hai là cá c biến ngẫu nhiên. C ác hàng đợi thường được phân loại theo kí hiệu của D .G Kedall theo dạng A /B /C /D /E , ví dụ một hệ thống có k í hiệu M /D /3 là m ột hàng đợi trong hệ thống khi cá c khách hàng đến hàng đợi theo quy luật phân bố hàm mũ, thời gian phục vụ là c ố định và có 3 server. G iả thiết rằng khi At - » 0 , Với X là tốc độ đi vào hàng đợi của khách hàng, ta có: À,At = P ịx á c suất một khách hàng đến trong khoảng thời gian At) ỉ - Ầ.At = P ịx á c suất không có khách hàng đến trong khoảng thời gian At} P ịx á c suất có hơn một khách hàng đến trong khoảng thời gian At} = 0 G ọ i |lI là t ố c đ ộ p h ụ c vụ c ủ a s e r v e r , k h i At - » 0 , ta c ó : ỊiÀt = P {x á c suất một khách hàng đến trong khoảng thời gian At Ị 1 - ịiAt = P Ịx á c suất không có khách hàng đến trong khoảng thời gian At} P ịx á c suất có hơn một khách hàng đến trong khoảng thời gian At} = 0 12 R õ ràng là l / ji là thời gian trung bình phục vụ m ột khách hàng và P {x á c suất có hơn một khách hàng đến trong khoảng thời gian Àt và có hơn một khách hàng đã được phục vụ rời khỏi hàng đợi Ị = 0 Trạng thái của hệ thống tại thời điểm t là số khách hàng trong hàng đợi kể cả khách hàng đang được phục vụ tại thời điểm đó, kí hiệu là pN(t), N = 1,2,... X é t hệ thống ở thời điểm t + At khi N = 0 , ta có: P o(t + A t ) = p0 (t)[l-A .A t] + p j(t)n A t (1 .2 .1 ) và khi N > 0 pN( t + At) = pN(t)[( 1- ẰAt)(l - nAt)] + P N _J (t)ẰAt + pN+1|j.At = p N( [ l - A . A t - n A t ] + pN_j(t)A.At + p N+InAt ( ' ' có bỏ qua cá c thành phần (A t)2 và cao hơn. Cho At —» 0 , ta có E ^ dt = l p 0 ( t ) + p i( t ) n (1.2.3) = -(Ằ . + n ) p N ( t ) + ^ p N_ i( t ) + HPN+i ( t ) (1.2.4) dt với điều kiện là X P ị ( t ) - 1 đối với t > 0. Vi Lời giải của phương trình này cho chúng ta hai loại phương trình vi phân trong trường hợp hệ chuyển dịch và khi hệ cân bằng. Như vậy, khi hệ là cân bằng, trên cách tiếp cận xác suất, chúng ta nhận lại phương trình cân bằng toàn cục. - N ghiệm trong trường hợp hệ đang chuyển dịch: Nếu hàng đợi bắt đầu từ trạng thái K ứng với điều kiện ban đầu là pK(0 ) = ôjk, cụ thể là -pk(0 ) = 1 và p,(0) = 0 đối với i k. - N ghiệm trong trường hợp hệ cân bằng: Khi hệ cân bằng, Pi(t) -> Pi độc lập với t và dpi(t)/dt = 0 đối với i = 1,2,... 00 . Trong trường hợp này định nghĩa p = ẰẠt, trong đó p < 1, ta có : Pi = p-p<> 13 P n+i = 0+p)pN — PP n-i = PN+1Po đối với N ^ 1 • Sử dụng diều kiện Y^L q Pi = 1 ta c ó: Pi - p‘( 1 - p) Trong trường hợp hàng đợi có m ột khâu phục vụ, số khách hàng trong hệ thống (hình 1.2.1): N = f i p , = Ễ í p - ( 1 - p) = —2 — 1=0 i=0 1- p (1.2.5) Số khách hàng trung bình trong hàng đợi trước khi được phục vụ: N q = Ễ ( i - l ) P i = - E— 1=0 1 -p ( l - P o ) = r i — P = 7^ l-p 1 -p (1.2.6) Wq Hình Ị .2.2: Phán bô' thời gian c h ờ trung bình trong hàng đợi Thời gian trung bình trong hàng đợi của một khách hàng với giả thiết nguyên tắc phục vụ là FC FS: w = Ị ( k + l)pkn“' = — k=0 1 ( .2.7) n (l - p) Tlìời gian trung bình trong hàng đợi của một khách hàng trước khi được phục vụ; w = w - - = ---- ■£— M - n (l-p ) (1.2 .8 ) 14 1.2.2. Định luật sô'bé. G iả sử một hệ thống hàng đợi trong trạng thái cân bằng, khi đó tồn tại c á c đại lượng hữu hạn sau: - T ố c độ đến trung bình của khách hàng Ằ, nghĩa là số khách hàng đến trong một đơn vị thời gian. - Số khách hàng trung bình (theo thời gian) trong hệ thống L. - Thời gian trung bình m ột khách hàng được phục vụ w . Khi đó tồn tại m ột phân b ố duy nhất đối với trạng thái của hệ thống và X = L.W (định lý số bé). Đ iều này được giải thích như sau: S ố khách hàng trong hàng đợi của m ột hệ thống tại thời điểm t chính là số khách hàng đã đến trước và đã đi sau thời điểm t. K í hiệu A uvl (0 < u < V < t) là số khách hàng đã đến trong khoảng thời gian [u,v] và dời đi sau thời điểm t, khi đ ó với V < t ta c ó P ( A o,v+dv,t = n ) = I p ( A 0vi = n - i ) P ( A VtV+dV)t = i ) i=0 (1.2.9) Nhân hai vế với n và lấy tổng trong khoảng 0 < n < co, ta có ky,v+dv,l ~ ~ l)P (A 0vt — n —l ) P ( A v,v+dv,t - 0 i = 0 n= i 00 + I (1 .2 .1 0 ) 00 Z i P ( A 0vt = n - i ) P ( A Vĩv+dv,t = i) i=0n=i trong đó L vl là số khách hàng đến trong khoảng [0,v], sau đó hệ thống ở tại thời điểm t. Do f s ( n - i ) P ( A 0v, = n - i ) = L v, và n=i | s P ( A „ +đVt, = i) = 1 do đó n=i biểu thức trên có thể viết lại thành: ^v+dv\t “ Lvt + ^ Ip (A v v+(jv>ị —1) ^ P(Aqvị —m) i=0 — L vt M ặt khác vì S ^ (^ v ,v + d v ,t — m=0 m=0 ( 1.2. 11) 15 00 I » P (A v.v+dv,t —*) n=i là số khách hàng đến trong khoảng thời gian dịch vụ sau đó rời khỏi hệ thống tại thời điểm t. Do vậy, hệ thống trong trạng thái cân bằng với số khách hàng đến trung bình là X dịch vụ, trong khoảng thời gian dịch vụ ta có: L v+dV(, - L v t= M l - F ( t - v ) ] d v trong đó F là hàm phân bố thời gian chờ phục vụ của khách hàng trong trạng thái ổn định, từ đó dL,' V t (1.2 .12) [1 - F (t - v)]Ằ dv Như vậy số khách hàng đến trong khoảng thời điểm t là t t Ltt = J[1 - F (t - v)]A,dv = À.t[l - F ( t ) ] + Ằ. Ju d F (u ) 0 (1 .2 .1 3 ) 0 khi L 0, = 0 và biến của tích phân u = t - V. K h i F có giá trị trung bình hữu hạn, w = J^udF(u) và [1 - F(t)]t —» 0 khi t -» 00, tương ứng ta có L tt - > 1.2.3. C ác h àn g đ ợi đơn lớp. H àn g đ(ri M ỈM /1 Ả Hình 1.2.3: Mô hình hàng đợi MíMI Ị và c á c qu á trình chuyển dịch Hàng đợi M /M /l là m ột quá trình biến đổi [1 7 ]. “Đ ến ” ià các khách hàng nhập vào hàng đợi và “đi” là các khách hàng rời khỏi hàng đợi sau khi đã được phục vụ. X ét hàng đợi trong trạng thái cân bằng. G iả thiết À.(n) và |i(n) tương 16 ứng là tốc độ đi vào hàng đợi và tốc độ phục vụ khi chiều dài hàng đợi là n (hàng đợi ớ trong trạng thái n) chúng ta có: p ( j) = n k=i n (k ) vứi .i > ° (1 .2 .1 4 ) Điều kiện cân bằng và cá c xác suất ở trạng thái ổn định như sau: Hàng đợi là cân bằng khi và chỉ khi I lk = o P ( k ) < c o (1 .2 .1 5 ) X á c suất tương ứng 7i(n) đối với trạng thái ổn định n trong hàng đợi cân bằng là p (n )/£p (k) k=0 (1.2.16) Khi khách hàng đi vào hàng đợi và tốc độ dịch vụ tương ứng là X và ji không đổi đôi với m ọi trạng thái n, chúng ta có loại hàng đợi M /M /l. V ới hàng đợi này p(k) = pk trong đó p = À. / |i và phân bố xác suất chiểu dài hàng đợi trong trạng thái n là: *(">=^=(1-P )P " ( l .2. 17) Xv k=0 Đ ây là hàm phân bố hình học, giá trị trung bình của hàng đợi là p /(l-p ). Độ hiệu dụng của server là u = 1 - 7t(0) = p và tốc độ trung bình rời khỏi hàng đợi là U(1, kết quả này tất nhiên tuân theo định luật L illte. V ì không c ó giả thiết gì vẻ nguyên tắc xếp hàng, cả quá trình đi vào hàng đợi và rời khỏi hàng đợi đều là quá trình Poisson. Do vậy, cá c điều kiện cân bằng và phân bố xác suất của chiều dài hàng đợi cùng có chung một nguyên tắc vớicá c giả thiết trên. Người ta có thể mở rộng loại hàng đợi này khi hệ thống có m server, kí hiệu là M /M /m . V ới ỉoại hàng đợi này, m server cùng có tốc độ dịch vụ bằng |i, các quá trình khách hàng đến có phân b ố dạng Poisson với tốc độ X và chiều dài hàng đợi ià n. Khi chiểu dài hàng đợi là n < m thì chỉ có n server đang phục vụ. Khi n > 1 server đang phục vụ, thời gian để hoàn thành một dịch vụ tiếp