ĐẠ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 • » • Chun 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 - 0 M ỤC L Ụ C LỜI MỞ ĐẦU CHUONG 1: CÁC QUÁ TRÌNH NGẪU n h iê n v m h ìn h h n g đ ợ i 1.1 Các trình ngẫu nhiên 1.1.1 Quá trình M arkov 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 1.1.5 Phương trình cân tồn cụ c 1.2 Các loại hàng đợi 10 1.2.1 K hái niệm đị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 đị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 mạng hàng đợi đóng 25 1.4.2 Tỉ số 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ố chất lượng dịch vụ 31 T ỉ số tế bào C L R 31 T ỉ số tế bào bị lỗi C E R 32 3 Trễ truyền tế bào cực đại M ax-C T D 33 Sự thay đổi trễ tế bào đỉnh - đỉnh P 2P - C D V 35 Dung sai trễ tế bào bùng phát C D V T -B T 35 2.3 K ích thước bùng phát cực đại M B S 35 Tỉ số nhóm tế bào bịlỗi nhiều S E C B R 36 2.3 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 T ố c độ tế bào đỉnh P C R 37 T ố c độ tế bào ổn định S C R 37 T ốc độ tế bào cực tiểu M C R 38 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 Điều khiển chấp nhận liên kết C A C 39 Điều khiển tham số sử dụng Ư PC 40 2.6 Điều khiển dòng mạng A T M 42 2.6.1 Thuật tốn lịch trình ảo 44 Thuật tố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 Phương trình hệ thống động 52 2 Các tham số lối không ổn định 53 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 mạng A TM mơ hình luồng động 58 3 Các luồng tối ưu mạng chuyển mạch g ó i 58 3 Đ iều khiển tốc độ lưu lượng tối ưutrong c c m ạng gói A TM 60 3.4 Đ ịnh tuyến tối ưu bẳng m ô hình luồng đ ộ n g 67 C họn đường tối ưu ch o chuyển m ạch k ê n h 67 Đ ịnh tuyến tối ưu m ạng A T M 73 3.5 K ết lu ận .81 CHƯƠNG 4: THUẬT TỐN MAXMIN CĨ ĐIỂU K IỆ N 82 4.1 G iới th iệu 82 4.2 Bài tố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 Phát biểu t o n .84 M ạng m rộ n g 85 4 M axm in có điều k iện 87 4.2 Thuật toán C P G 90 Phương pháp dự đoán liên kết đơn .90 2 Đ ổ hình C P G 92 Thuật toán C PG 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 phổ rộng cho ứng dụng thời gian thực hội nghị truyền hình, video theo nhu cầu, Một đặc tính quan trọng ứng dụng chúng đòi hỏi yêu cầu chất lượng dịch vụ (Q oS) phải đảm bảo, công nghệ truyền dẫn không A T M 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 mạng liên kết xác định tham số ảnh hưởng trực tiếp tới Q oS có quan hệ hữu với A TM có 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 gọi (điều khiển chấp nhận liên kết) điểu khiển cấp tế bào (thuật ốn gáo rị) Tuy nhiên, vấn đề tối ưu độ hiệu dụng toàn mạng toán ihức tạp, phi tuyến phân tán D o đó, số điều kiện tài nguyên nạng tuyến sử dụng phải áp đặt M ột c c tốn tìm kết nối thoả mãn yêu cầu 'ề chất lượng dịch vụ dựa thuật toán phân phối băng thông M ax-m in cân tối Đây m ột phương pháp có độ hiệu dụng cao, A TM forum (Version 0) khuyến nghị Tuy nhiên, để có băng thơng M ax-m in cân đối tồn lạng ỉà điều khó thực lưu lượng dòng 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 chọn ỉà giải pháp cho ác toán loại Mục đích luận văn sở nghiên cứu trình ngẫu hiên số loại hàng đợi để tìm hiểu tham sơ' ảnh hưởng tới chất lượng Ịch vụ 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 áp dụng nguycn lí tác dụng tối thiểu Pontriagin để cực tiểu thời an trễ xác suất tắc nghẽn m ột hệ thống suy hao Dựa thuật toán 'i ini L exicog rap h ic, toán M axm in có điều kiện C M M (Constrained axim in problem ) tốc độ áp đạt cực tiểu (M R C ) tốc độ áp đặt đỉnh ’R C ) phát triển Cấu trúc luận văn gồm chương: Chương trình bày lý luận trình ngẫu nhiên mà trọng tâm qúa trình Possion, m ột số loại hàng đợi, số định lí quan trọng nạng hàng đợi đóng Chương giới thiệu cá c tham số ành hưởng tới chất lượng dịch vụ nạng A T M m ột số giao thức điều khiển Chương trình bày m hình luồng động ngun lí tác dụng tối hiểu Pontriagin nhằm đạt hiệu xuất mạng Chương trình bày tốn M axm in có điều kiện C M M kết Đây chương quan trọng việc từ tiếp cận đến giải vấn đề chất lượng lịch vụ m ạng A T M Chất lượng dịch vụ m ạng A T M vấn đề rộng cẩn nhiều ghiên cứu, việc hồn thành luận văn khơng tránh khỏi có thiếu sót, long nhận ý kiến đóng góp người quan lâm Chương 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 trình ngảu nhiên Chúng ta xem xét hệ thống theo thời gian quan tâm tới cá c đáp ứng theo theo thời gian chúng [7], M ột trình ngẫu nhiên X , (hoặc X (t)) tập cá c biến ngẫu nhiên theo tham số t (thường thòi gian) M ột cách xác hơn, q trình ngẫu nhiên ánh xạ từ không gian mẫu s theo hàm t, phần tử e Ihuộc s tương ứng với hàm x,(e) [20], vậy: - Với mồi giá trị e cho trước, x,(e) hàm thời gian - Với giá trị t cho trước, X t(e) biến ngẫu nhiên - Với cặp e t cho trước, x,(e) số cố định K í hiệu T khơng gian tham số, tập giá trị t X t dược gọi không gian trạng thái hay tập c c giá trị khả dĩ, ta có khái niệm sau: - C ác chuỗi thời gian liên tục: Khi T chu kỳ tất cá c thời điểm chu kỳ nhĩmg giá trị khả d7 t - C ác chuỗi thời gian rời rạc: Khi T 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) nhận số giá trị tập biết trước - Quá trình trạng thái rời rạc: X (t) nhận số cá c giá trị tập rời rạc K í hiệu X (t) trình ngẫu nhiên trạng thái X thời điểm t Một trình ngẫu nhiên X (t) hoàn toàn xác định phân bố kết hợp biến ngẫu nhiên X (t,), X ( t2), thời gian tj, t2, t X (tk) xác định 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 , , t n) (1.1.1) Ị 1.1 Quá trình Markov M ột trình ngẫu nhiên gọi q trình M arkov có tính chất sau (gọi 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 trình thời điểm tn+| phụ thuộc vào trạng thái q 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 đạt được) Trạng thái chứa đựng tất cá c thông tin cần thiết để xác định đáp ứng tương lai qúa trình X ác suất chuyển dịch từ trạng thái i sang trạng thái j pj j = P { X n+ị = jl X n = i } Các xác suất chuyển dịch tạo thành ma trận chuyển dịch Cp, j) = p , đó: % p = PlO P0,1 Pll (1 ) Hàng thứ i x c suất trình từ trạng thái i chuyển sang trạng thái j với j = 0, Ma trận với c c phần tử không ủm tổng m ỗi hàng gọi ma trận ngẫu nhiên M ột trình M arkov tạo thành chuỗi M arkov xác suất chuyển dịch P Ị X n+l = jix„ = 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 có : P{ Hệ thống trạng thái A N đơn vị thời gian I trạng thái hệ thống A } — pN P{ Hệ thống trạng thái A N đơn vị thời gian trước rời khỏi trạng thái Ị = pN( l - p) Như vậy, thời gian rời rạc, phân bố trơn có dạng hình học thể tính khơng nhớ thảo luận chi tiết phần 1.1.3 Hình Ị Ị ì : Thời gian rời rạ c m ỏ hình trạng thái Trong trường hợp thời gian liên tục, giả thiết hệ thống trạng thái A thời điểm t tốc độ rời khỏi trạng thái A |i X ét thời điểm t + T , xác suất đê hệ thống khoảng thời gian từ t đến T là: P (H ệ thống trạng thái A khoảng thời gian T I trạng thái A } = ( l - |aAt)T/At = e 'MT Như vậy, thời gian liên tục, hàm phân bố theo thời gian mà hệ thống tồn trạng thái A trạng thái có dạng hàm mũ ỉ 1.2 Quá trình biến đ ổ i Hình ỉ ỉ 2: Mỏ hình trình biến đổi Là chuồi M arkov đặc biệt, rời rạc theo thời gian có cá c tính chất: - Tồn m ột không gian trạng thái rời rạc - C ác trạng thái đếm - Chuyển dịch xảy c c trạng thái liền kề với tốc độ chuyển dịch là: Pl.j - < X, j X c suất chuyển khoảng At tới A-iÀt ịiị j X c suất chuyển khoảng At tới fi,At cá c giá trị Khi hệ thống cá c trạng thái khác Ị 1.3 Q uá trinh P oisson Poisson loại trình M arkov hay trình đếm số kiện riêng lẻ xảy cách ngẫu nhiên khoảng thời gian xác định trước Chúng ta thường xem kiện trình đến hàng đợi khách hàng K í hiệu Ntt số khách hàng đến hàng đợi khoảng thời gian (t,x], trình ngẫu nhiên |N0llt > } m ột trình Poisson với t T > có cá c đặc điểm sau: L m ột trình thời gian nhất, nghĩa với số nguyên không âm k, P(N t t+I = k) độc lập với X hay m ột cách tương ứng NTT+1 phân bố N,„ Là m ột trình tăng độc lập, nghĩa N()T NTT+, độc lập với Là trình tuần tự, nghĩa P(NTT+l > 2)/t —> t —> 0T rên sở q trình Poisson có c c tính chất sau: Tính khơng nhớ Một q trình Poisson với tham số X , thời gian để khách hàng vào hàng đợi kí hiệu A thời gian c c khách hàng vào hàng đợi cá c biến ngẫu nhiên theo luật hàm mũ P(A > t) = P(N OI= ) = e ?'t (1 ) Rõ ràng P(A < t) = 1- e xt K í hiệu thời gian cá c khách hàng vào hàng đợi T Đ ê tính P (T > t) chứng minh rằng, với m ột khách hàng vào hàng đợi thời điểm t số khách hàng vào hàng đợi khoảng thời gian [t,T + t] Tuy nhiên, biến ngẫu nhiên NS1 mô tả số khách hàng vào hàng đợi khoảng thời gian (s ,tj Do giả thiết có khách hàng vào hàng đợi thời điểm t , 93 4.2.3 Thuật tốn CPG trường hợp đa liên kết Thuật toán C PG mạng đa liên kết L = 1; V ới m ỗi liên kết đơn Nj mạng N, thi hành toán C M M đơn liên kết (Nj) để nhận Rị ĩị với i Vy V ới m ỗi liên kết j mạng N thực hiện: Nếu R j = m in {R k I liên kết j liên kết k chia sẻ m ột V C ) thêm liên kết j vào tập L V ới m ỗi liên kết j tập L thực hiện: Thêm liên kết j nút đồ hình CPG liên kết L -1 mà chia sẻ m ột v c với liên kết j 4.1 Cập nhật C k k chia sẻ m ột v c với liên kết j thực hiện: c k= c k4 £ r ieVjnVfc Loại bỏ liên kết j tất cá c v c sử dụng liên kết j Nếu N ỉà không rỗng, thực L = L + quay lại bước 2, không dừng Hình 2.4: Thuật tốn CPG đ ối với mạng đ a liên kết Thuật toán CPG phát biểu hình (4 ) thuật tốn tồn phần (thuật tốn song song), khác biệt chủ yếu thuật tốn số thuật toán khác nghiên cứu số báo toán m ax-m in Chú ý rằng, bước thực song song liên kết tập L Hơn nữa, cần ý thuật toán không phụ thuộc vào điểu kiện ch í điều kiện cân đối C ác điều kiện phụ thuộc tóm gọn lại toán C M M đơn liên kết điều thể thuật tốn giải cho toán C M M lưu ý cách sử dụng lời giải trường hợp đơn liên kết Ngoài trường hợp cần ý rằng, thuật tốn đơn liên kết khơng bao gồm điều kiện theo nghĩa M R C P R C (lĩii Mị) điều kiện cân 94 đối theo nghĩa tốc độ chia sẻ cân đối M ột ưu điểm thuật toán nhiều điểu kiện cân đối áp đặt cách thay đổi phần toán C M M liên kết đơn Có thể chứng minh cá c tốc độ tính tốn theo thuật tốn CPG hội tụ thành nghiệm toán C M M sau m ột số hữu hạn bước T a xét hai điều kiện sau: Tính xác: Nếu thuật tốn CPG xảy tới kết thúc cá c tốc độ lối tối ưu Tính hữu hạn: Thuật toán kết thúc sau số bước hữu hạn Nếu thủ tục C M M đem liên kết thi hành trọn vẹn bước iặp thuật tốn CPG có liên kết loại bỏ, trường hợp thuật toán kết thúc với n lẩn lặp, n số liên kết mạng N Từ đó, ta thấy cần chứng minh thủ tục C M M đơn liên kết thi hành mà không xung đột T a kiểm tra hoạt động thuật toán giả mã hình (4 ) Có thể thấy hoạt động cách xác cá c điều kiện tốc độ tối thiểu • ieV (4 ) Do cần tốc độ c ố định bước c c liên kết cịn lại thoả mãn (4 ) thủ tục đơn liên kết thực bước Đ ể hiểu rõ hơn, xét m ột liên kết j bước m ột liên kết k không thuộc bước từ đến Chú ý Rị' < R k' I thê số bước mà cá c tốc độ định trước tính tốn Nếu Vj n V k = điều kiện (4 ) thoả mãn, cá c tốc v c liên kết k không thay đổi Nếu Vj n V k ^ , gọi r;(l,j) tốc độ phân phối cho v c i bước thứ thuật toán CPG thực đơn liên kết j v c i sử dụng liên kết j k v c i liên kết j mạng Khi có hai trường hợp (1 ) r,(l,j) = nij (2 ) r,(l,j) = RjJ X é t trường hợp (1 ), tốc độ cực tiểu r|(l,j) < fjOJk) X é t trường hợp (2), ta c ó fi(l j ) = Rj' > rrij, nghĩa r|(l,k) = R k' 95 T điều kiện lồi có rị(l,k) = R k', nghĩa ỵ j d j ) < rj(l,k) Như điều kiện đảm bảo bước + vc k thiết lập tốc độ r,(l,j) không lớn tập cá c tốc độ thoả mãn rj(l,k) V VC3 _yjgay c = 7u ^ k V C lv y ^ = ^ c= cL^= 2U 50 I ĩr õ T õ k ’rck ^ ầ; ỉ Ị VC2 -, J 120 KX = C = =W iu u C < -x -5 I A I Link r ï 0y Link f N I VC4 VC5 ) MRC PRC 60 00 00 00 55 00 70 Hình 4.2.5: Cấu hình m ạng với cá c tốc đ ộ MRC vù PRC X ét cấu hình mạng hình (4 ), tính tốn nghiệm tốn C M M thuật tốn C PG thiết lập đồ hình CPG Ngồi ra, để kiểm tra tính xác nghiệm, hai điều kiện tối ưu tắc nghẽn điều kiện tối ưu lồi kiểm tra Đ ể áp dụng thuật toán CPG, cần phải mở rộng mạng Sử dụng định nghĩa có mạng m rộng hình (4 ) V MRC PRC 60 00 00 00 55 00 00 Hình 4.2.6: Cấu hình m ạng với cá c tốc đ ộ MRC PRC 96 Áp dụng thuật tốn CPG đỏi với m ạng hình (4 ) có nghiệm sau r, = ; r2 = 10; r3 = ; r4 = ; r5 = (M bps) (4 2 ) N goài ra, c c tốc độ định trước nghiệm toán C M M R , = 10; R = 40; R = 60; R = oo; R s = (M bps) (4 ) Đ hình CPG hình (4 ) Chú ý rằng, đồ hình khơng có liên kết bị loại bỏ liên kết giả bão hồ (bất kỳ v c sử dụng liên kết bị áp đặt liên kết khơng hồn tồn sử dụng) Chiều dài đổ hình cho ta biết nghiệm C M M tính tốn ba vịng lặp Có thể nhận thấy việc tính tốn nhanh tính tốn nghiệm C M M Trong hình (4 ), đồ hình CPG m ô tả liên kết liên kết thuộc bước lặp, điều nghĩa tố c độ định trước tính tốn m ột thời điểm mà không ảnh hưởng tới cá c tốc độ khác, điều làm cực tiểu số bước tính tốn (thuật tốn có tính song song) Hình : C ấu hình mạng với c c tốc đ ộ MRC PRC V ới nghiệm (4 ) kiểm tra tối un theo hai cách C ách thứ sử dụng điều kiện tắc nghẽn tối ưu Trong trường hợp này, ý V C M R C liên kết 1, v c B L C liên kết 1, v c B L C liên kết 2, vc B L C liên kết vc B L C liên kết Khi liên kết B L C M R C số liên kết, thấy (5 ) m ột nghiệm C M M Chú ý khơng có v c B L C M R C 97 liôn kết liên kết giả bão hồ Đ iều chứng minh tối ưu nghiệm điếu kiện tối ưu lồi C ó thể kiểm tra rằng, v c , phân phối tốc độ cực đại tốc độ cực tiểu cực đại tốc độ định trước, nhiệm C M M K ết luận Trong chương tìm hiểu thuật tốn m ax-m in có điều kiện sở thuật tốn Lexicographic M hình bao gồm cá c điều kiện điều kiện X em xét điều kiện tối ưu tương đương C ác kết lý thuyết rõ ràng chúng đóng vai trò quan trọng cá c điều kiện tự động tối ưu tốc độ định trước Lý thuyết toán tắc nghẽn đơn giải quyết, toán mạng đa liên kết giải sở áp dụng toán đơn liên kết Lý thuyết M ax-m in trình bày sử đụng để phát triển giao thức điều khiển dòng phân tán [27][1 l j Trong thực tế, điều kiện tối ưu xảy cách tự động để kiển tra nghiệm toán C M M 98 K ẾT LUẬN ♦ Mạng thơng tin hăng rộng dựa nịng cốt chuyển mạch ATM dang mối quan tâm hàng đầu cho nhà hoạch địch chiến lược phát triển mạng viễn thông ISDN băng rộng Một vấn đề cốt lõi thiết kế mạng ATM chất lượng mạng Mạng có đặc tính khác so với mạng PSTN tại, đặc trưng xác suất lỗi bit đây, chuyển mạch dạng gói làm nên đạc trưng cho nghẽn trễ gói Luận văn nghiên cứu cặn kẽ vấn đề xếp hàng gói tin nút ATM, sở nghiên cứu đặc tính chất lượng mạng thơng qua đặc tính nghẽn trễ tế bào chờ xử l ý nút ATM Qua nghiên cứu đặc tính chất lượng mạng ATM, luận văn giới thiệu biện pháp để nâng cao chất lượng dịch vụ mạng ATM, phương pháp điều khiển lun lượng mạng sở thuật toán Pontriagin, điều khiển luồng tối ưu sở luồng động, định tuyến tối ưu mơ hình luồng động Cuối cùng, luận văn tư tưởng thuật toán tối ưu để giảm hệ thốne động, phát triển sử dụng thuật toán Maxmin có điều kiện Đây phát triển lĩnh vực này, làm cho thuật toán đơn giản thuật toán dùng trước CÁC TỪ VIẾT TẢT ABR Available Bit Rate D ịch vụ tố c độ bit c ó thể thay đổi ALL ATM Adapter Layer L p tương th ích A T M ATM Asynchrnous Transfer Mode M o d e tru yền dẫn k h ô n g đồng B -IS D N Broadband Intergrated Service M ạn g tích hợp d ịch vụ số băng D ig ita l Network rộ n g BT Burst To! ere nee B ù n g phát CAC C o n n ectio n Admission Control Đ iề u k h iển ch ấ p nhận liên kết CBR Constant Bit Rate Service D ịc h vụ tố c độ bit k h ô n g đổi CDV Cell Delay■ s Variation T h a v đổi trễ củ a tế bào C D V T -B T Cell Delay Tolerance and Burst D u n g sai trễ tế bào bùng phát T o le r a n c e CER Cell Error Ratio T ỉ s ố tế bào bị lỗi CLR C ell Loss Rate T ỉ số m ất tế bào CMM Constrained Maximin Probelm B i tốn M a x m in c ó điều kiện CM R C ell Misinsertion Rale T ỉ số tế b o đốn sai đích CPG Constrained Precedence Graph Đ hình ưu tiên có điều kiện GCRA Generalized Cell Rate Algorithm T h u ậ t toán điều khiển tố c độ tế b o tổ n g quát GFR Guaranteed Frame Rate D ịch vụ tố c đ ộ khung đảm bảo IP Internet Protocol G ia o thức m ạn g M a x -C T D Maximum Cell Transfer Delay T r ễ tru yền tế bào cực đại MBS Maximum Burst Size K íc h Ihư ớc bùng phát cự c đại MCR Minimum Cell Rate Tốc độ tế bào cực tiểu MFS Maximum Frame Size K íc h thước k h u n g cự c đại MRC Minimum Rate Constrained Tốc độ áp đặt cực tiểu n rt-V B R Non Real T im e -VBR V B R th ời g ian k h ô n g thực P2P - Peak-to-Peak C ell Delay Sự thay đổi trẻ tế bào đỉnh - đỉnh CDV V a ria tio n PASTA Poisson Arrivals See Time Các trình vào hàng đợi có Averages phân dạng hàm Poisson PCR Peak C ell Rate Tốc độ tế bào đính PDU P rotocol Data Units Đơn vị liệu giao thức CPL C ell Loss Priority Quyền tổn thất tế bào PRC Pick rate Constrained Tốc độ áp đặt đỉnh PVC Permanent Vitiial Connection Liên kết ảo cố định QoS Quality o f Service Chất lượng dịch vụ RM-Cells Resource Management - Cells Các tế bào quản lí nguồn ROP Random Observer Property Tính quan sát ngẫu nhiên rt-VBR Real time-VBR VBR thời gian thực SCR Sustained Ceỉỉ Rate Tốc độ tế bào cố định SECBR Severely Errored Cell Block Tỉ số nhóm tế bào bị lỗi nhiều R a tio TD Traffic Descriptor Bản mô tả lưu lượng TDM Time Division Multiplexing Hợp kênh phân chia theo thời gian TM Traffic M an ag em en t Quản lý lưu lượng UBR Unspecified Bit Rate Dịch vụ tốc độ không định trước UNI User-Network Interface Giao diện người sử dụng-mạng UPC Usage Param eter Control Điều khiển tham số sử dụng VBR V ariable Bit Rate Dịch vụ tốc độ bit thay đổi vcc Vitu Channel Connection Kết nối kênh ảo VCI Vitual Chanel Indicator Chỉ số kcnh ảo VC-S\v V irtu a l Channel Sw itching Thủ tục chuyên mạch kênh ảo Function VPC Vituaỉ P ath Connection Kết nối đường ảo VPỈ Vitnal Path Indicator Chỉ số đường ảo VP-Sw Virtual Path Switching Function Thủ tục chuyển mạch đường ảo T À I L IỆ U T H A M K H Ả O ] D anienl M inoli, Queuing Fundam entals fo r T elecom m u n ication s , Section 1, http://wheat.uwaterloo.ca E G elenbe (1 ), Introduction to Q ueuing N etw orks , John W iley & Sons, tr 45 F Bonom i, “T he A vailable Bit R ate Service”, Z eitnet Inc, http://palgong.kyungpook.ac.ler/~rcsearch/abr.html http://w w w cisco.com /univercd/cc/td/doc/cisnitw k/ito_doc/qos.htm #33035, “Quality of Service (QoS) Networking” J V irtam o, Q ueing T heory: The M IG/I Q ueue , tr 6 J V irtam o, Q ueuingT heoi-y: P ossion P rocesses, tr 15 J V irtam o, Queuing T heory: S tochastic P rocesses, tr J V irtam o, Queuing T heory: S tochastic P rocesses, tr 21 Johdi R os and W ei K Tsai (2 0 ), “A Theory o f M axm in Bottleneck O rdering”, T ech n ical rep ort , University o f C alifornia, Irvine, CA 9 10 Johdi R os and W ei K T sai, “ An Optimal Distributed Protocol for Fast C onvergence to M axm in R ate A llocation” , T ech n ical rep ort , University o f C alifornia, Irvine, CA 9 11 Jordi R o s and W ei K T sai, “ A G eneral theory o f Constrained M ax-m in Rate A llocation for M ulticast Networks”, T ech n ical rep ort , University o f C alifornia 12 L G eorgiadis, K Floros, “L exicographically Optimal Balanced Networks”, A C T S project, T ech n ical rep ort , A ristotle University 13 M atthieu V erdier, David G riffin , “ D ynam ic Bandwith M anagem ent in A TM N etw orks” , EU ACTS P ro ject AC20S, U niversity C ollege London 14 N atalie G iroux, Sudhakar Ganti (1 9 ), Q uality o f S ervice in ATM N etw orks: S tate o f the Art T raffic M anagem ent , Prentice H all, tr 1-2 15 N atalie G iroux, Sudhakar Ganti ( 1991 ), Q uality o f S ervice in ATM N etw orks: S tate o f the Art T raffic M anagem ent , Prentice H all, tr 14 16 N atalie G iroux, Sudhakar Ganti (1 9 ), Q uality o f S ervice in ATM N etw orks: S tate o f the Art T raffic M anagem ent , Prentice H all, tr 19 17 Peter G Harrion (1 9 ), P erform an ce M odelling o f C om m unication N eru'orks an d C om puter A rchitectu res , A ddion-W esley Publishing Company, tr 172 18 Peter G Harrion ( 1993), P erform an ce M odelling o f C om m unication N etw orks an d C om puter A rchitectu res, A ddion-W esley Publishing Company, tr 174 19 R Ja in (1 9 ), “Congestion Control and T ffic M anagem ent in A TM N etw orks: R ecen t Advances and A Survey” , OH JO, T he Ohio State I U niversity, Columbus 20 Sanjay K Bose, Q ueuing System s , E E , tr 21 Serge Plotkin, “Com petitive Rounting o f Virtual C ircuits in A TM Networks”, N SF C C R -9304971 , Standford University 22 Sudeep Bhatnagar and Badri Nath, “Theory o f 6-Fairness and an Edge Router Based Protocol for its Im plem entaion” , N -6Ổ 600I-00-Ỉ-8954, Rutgers University 23 Sudeep Bhatnagar and Badri Nath, “Theory o f s-F a im e ss and an Edge Router Based Protocol for its Im plem entaion” , N -6Ố 600Ỉ-00-1-8954, Rutgers U niversity 24 The A T M Forum T echnical Com m ittee (1 9 ), T ech n ical C om m ittee T raffic M anagem ent S pecification , V ersion , tr 25 The A T M Forum T ech nical Com m ittee (1 9 ), T raffic M anagem ent S p ecification s, V ersio n 4.0 26 The A T M Forum -Technical com m ittee ( 1996), T raffic M am gem an i S p ecification , V ersion , tr -2 , -6 27 Y iw ei Thom as Hou, Herry H -Y Tzeng and Shivendra s Panwar (1 9 ), “A Genelized M ax-m in R ate A llocation Policy and Its Distributed Im plem entation Using the A B R Flow Control M echanism ” , 0-78034386-7/98/$10.00 @ IE E E PH Ụ LỤ C fu n c tio n % c : [A,S,CPG] Capacity % VCM: % p: Vector N e tw o rk crosses link = CPG(C,VCM,p,method) (each to p o lo g y m atrix is a link (V C M (i,j)=l cap aci m eans VCi j) fa irn e ss+ fe a sib ility % method: com p onent "ordinary", p a m e te rs "tax", "penalty", "constrained" % A : GCMM r a t e a l l o c a t i o n % Link S a t i s f a c t i o n % CPG: CPG G r a p h % In p u t Sample: % c = [150] % VCM= [ ; ; ] % [A , s , CP G] = CPG(C,VCM, [ , , ; 0 , , / 0 , 0 , 0 ] % in itia liz a tio n L = : s i z e ( V C M , 2) ; VC = : s i z e ( V C M , ) ; % Set of A = z e r o s ( ,size(VCM ,1 )); s z e r o s (1 ,len g th (C )); = 1c o n s t r a i n e d ' ) Set of L in k s VC s % Set of rates % Set of advertized % CPG satisfa ctio n s CPG = zeros(size(V C M ,2 )); VCMp = % C o p y o f VCM V C M; C u rren t le v e l = 0; % algorithm while size(L) ~= le v e l= le v e l+ l; % S o lv e th e s e t for j S(j) = = level of CPG of single links L SA Tsinglelink(C ,VC M p,p,V C ,j, m ethod); end %s, pau se th e % Find for i m o st bottleneck d isjo in t links = L m in im u m = fo r L ( [ : f i n d ( L = = i ) - , f i n d ( L = = i ) +1 : l e n g t h ( L ) ]) j = 1; %VCMp, j , i , s if VCMp ( : , i ) ' *VCMp ( : , j ) 6c S ( i ) > S ( j ) minimum = 0; end end i f minimum CPG(i , i ) = l e v e l ; A = RA TESinglelink(C ,V C M p,p,VC ,A ,s(i ), i , m ethod); %A, p a u s e end end for if i = L CPG (i,i) == % Subtract level settled rates for j = L ( [1 : f i n d ( L = = i ) - , f i n d ( L = = i ) + : l e n g t h ( L ) ] ) for k = : length(VC) if VCMp(k,i) C (j) = c (j ) == - & VCM p(k,j) == A(VC(k)); %j , k , i , c , p a u s e end end end % Add n o d e s fo r j = to CPG [1 : i - , i + : s i z e ( V C M , ) ] i f V C M ( : , i ) 1* V C M ( : , j ) CPG(i , j ) = ; C P G ( j , ) = & C PG (j,])== l e v e l -1 ; end end % R em ove Links L = L ( [1 : (f i n d ( L = = i ) - ) , (f in d ( L = = i)+1) : le n g t h ( L ) ] ) ; % R em ove V C ' s vcp fo r = VC; j = VCp if VCMp(find(vc==j),i )~= VCMp = VCM p( [1 : f i n d (v c = = j ) - , f i n d ( v c = = j ) + : s i z e ( V C M p , )] , :) ; VC = V C ([1 :find(vc==j)-1,find(vc==j)+1 :length(VC) ]); %VCMp,VC,pause end end end end end fu n ctio n S = SA Tsinglelink(c,V C M p,p,V C ,j, method); % ( F u n c t i o n c a l l e d b y C PG ) sw itch lower(method) case 'ord in ary ', s = c (j )/s u m (V C M p ( :,j ) ) ; case ’ c o n s t r a i n e d 1, s = c (j ) /sum(VCMp( : , j ) ) ; case ’ta x ’ % p is the v e c to r su m = fo r i = l : length(VC) ta x ; sum=sum+VCMp( i , j ) * p ( V C ( i ) ) ; end s = c ( j ) / sum; case 'p en alty % binari N=0; v e c to r p indicates penalty over VC M= ; fo r i = l : length(VC) N=N+VCMp( i , ] ) ; M= M+ V C Mp ( i , ) * p ( V C ( i ) ) / end if M ~ = Sic M ~=N s = ( -M + s q r t(M ^ + * C (j) *M*(N-M)) ) / / M / (N-M); else S=C (j)/N ; end otherw ise, e r r o r ( ' Unknown m e t h o d ' ) end fu n ctio n A = RA TEsinglelink(C,V C M p,p,VC ,A ,s, j , m ethod); % ( F u n c t i o n c a l l e d b y C PG ) c , VCM p, p , V C , A , s , j , m e t h o d , p a u s e sw itch case for if lower(method) ' o r d i n a r y 1, i = l : length(VC) VCMp( i , j ) = = A (VC(i ))= s ; end end case for if 'tax' i = l : length(VC) VCMp( i , j ) = = A (VC(i ) ) = S * p ( V C ( i ) ) ; end end case 'pen alty' M=0; N= ; for i = l : length(VC) M = M+ V C Mp ( i , ] ) * p ( V C ( i ) ) ; N=N+VCMp( i , j ) ; end for i = l : length(VC) i f VCMp( i , j ) = = if p (V C (i) ) ==1 A(VC(i ) ) = s ; else if M ~=0 A(VC(i))= s A2 *M ; else A(VC(i ) ) = s ; end end end end case 'con strain ed ' % p (1,:): Nw = for w e ig h ts / p (2 ,:): ; i = l : length(VC) Nw = Nw + end V C M p (i,j) * p (1 ,VC(i) ) ; r=zero s(1 ,length(V C))-2 ; done = ; while -d o n e Nwc ; Fc MRC / = = ; p( fo r if i =l : length(VC) VCMp( i , j ) Nwc = Fc = Nwc Fc + + & (r(i) == p ( , V C (i )) I r(i) == p ( , VC(i ))) p ( , VC(i ) ) ; r (i ) ; end end for if i =l : length(VC) VCMp ( i , j ) 5c ( r ( i ) ~ = p ( , VC ( i ) ) ) & (r(i) ~= p ( , VC(i ))) r(i) = p ( , V C ( i ) ) * ( C (j ) - F c ) / ( Nw- Nwc) ; end end R=0 ; for i =l : length(VC) if VCMp( i , j ) R * p ( l , V C ( i ) )) & & (r(i) > p ( , VC(i ))) & (r(i) > ( r ( i ) < p ( , V C ( i ) )) R = r (i ) /p (1, VC (i) ) ; end end done fo r = ; i = l : length(VC) if VCMp (i ,j ) Sc (r(i) ~= min(max(R*p( , VC(i ) ) , p ( , VC(i ) ) ) , p ( , V C ( i ) ) ) ) done = ; r(i) = m i n (m a x ( R * p ( , VC ( i ) ) , p ( , VC ( i ) ) ) , p ( , VC ( i ) ) ) ; end end end for i = l : length(VC) A (VC(i )) = r ( i ) ; end otherw ise, end e r r o r ( ' Unknown m e t h o d ' ) ... 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 đô... n mạng hàng đợi đóng lý luận trình ngẫu nhiên hàng đợi cho việc nghiên cứu đặc tính chất lượng mạng ATM chương 28 Chương CH ẤT LUỢNG DỊCH v ụ TRONG MẠNG ATM 2. 1 Giới thiệu Chất lượng dịch vụ. .. 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 độ