Luận văn Đảm bảo chất lượng dịch vụ cho truyền thông đa phương tiện thời gian thực trên Internet

tối thiểu đủ để hoạt động Xét 1 ví dụ có một luồng thoại thời gian thực yêu cầu băng thăng tối thiểu bằng một nửa dung lượng đường truyền T1 (1.544Mbps). Nếu chỉ có 2 luồng dữ liệu ta hoàn toàn có thể sử dụng WFQ để phân phối. Tuy nhiên vấn để xảy ra khi có thêm nhiều luồng dữ liệu tham gia vào đường truyền khi đó đặc tính của WFQ sẽ phân phối giải thông công bằng cho các luồng, như vậy luồng thoại thời gian thực ban đầu sẽ không có đủ lượng băng thông yêu cầu là một nữa đường truyền T1. Khác với WFQ khi sử dụng 28 CBQ thì hoàn toàn có thể cấu hình dành 1 nửa đường truyền T1 cho luồng dữ liệu thoại thời gian thực này. Luồng này được đưa vào 1 lớp và có đủ băng thông để hoạt động, các luồng còn lại được xếp vào một lớp khác và chia sẻ một nửa băng thông còn lại. CBQ còn hỗ trợ chia sẻ băng thông giữa các lớp bằng cách sử dụng cấu trúc cây phân lớp, để hiểu rõ hơn chúng ta cùng xét ví dụ dưới đây. Tại mức cao nhất người quản trị chia sẻ đường truyền cho 3 người dùng khác nhau. Tại mức này từng người đùng sẽ chia sẻ băng thông họ nhận được cho các ứng dụng theo một tỉ lệ nào đó, quá trình lặp lại cho đến khi ứng dụng nhận được phần băng thông được cấp phát để truyền. Hình 2.6: Chia sẻ băng thông trong CBQ Trong quá trình hoạt động có những lớp không sử dụng hết băng thông được cấp phát, lượng băng thông này sẽ được chia sẻ cho các lớp còn lại, các lớp cùng cấp có thể mượn số băng thông này thông qua lớp cha của nó, lớp nào có ưu tiên cao hơn sẽ mượn được nhiều bằng thông hơn. CBQ đã được cài đặt trên linux bằng cách dùng thuật toán từ bộ mô phỏng NS2. Cài đặt ban đầu của CBQ là WRR (Weighted Round Robin), trong linux là DRR links Agency A 40% Agency B 30% Agency C 30% HTTP 20% FTP 10% POP3 10% TCP 10% IP 20% HTTP 20% SSH 10% RTP 10% FTP 10% 29 (Deficit Round Robin). Chính sách chia sẻ băng thông được sử dụng trong DRR như sau: Khi lớp A có độ ưu tiên cao hơn lớp B, cả 2 đang mượn băng thông từ lớp C thì A sẽ lấy phần băng thông nó cần sau đó phần băng thông còn lại sẽ dành cho B, nếu độ ưu tiên của lớp A và B bằng nhau thì 2 lớp sẽ cùng nhận được 1 lượng băng thông chia sẻ giống nhau. 2.2. CÁC CHIẾN LƯỢC QUẢN LÝ HÀNG ĐỢI ĐỘNG Trong lý thuyết hàng đợi người ta chứng minh được rằng thời gian trung bình mà các gói tin đi qua hàng đợi bao gồm thời gian các gói tin phải chờ trong hàng đợi cộng với thời gian chúng được phục vụ, tỉ lệ thuận với chiều dài hàng đợi, tỉ lệ nghịch với tốc độ gói tin đến hàng đợi trung bình. Mục tiêu chính của các chiến lược quản lý hàng đợi là giữ cho chiều dài hàng đợi trung bình đủ nhỏ và ổn định. Đảm bảo độ trễ trung bình của các gói tin không vượt quá ngưỡng cho phép đồng thời đạt được hệ số sử dụng đường truyền cao. Hai yêu cầu này là trái ngược nhau chính vì vậy cần có một sự thỏa hiệp. Để biểu diễn đại lượng này người ta đưa ra một đại lượng là “Công suất”, đó là tỉ lệ giữa thông lượng và độ trễ. Điểm tối ưu là điểm có hiệu suất cực đại. Trong chương này sẽ trình bày về các chiến lược quản lý hàng đợi động AQM và một số thuật toán tiêu biểu. Các chiến lược này nhằm đáp ứng các mục tiêu đã nêu phía trên. Trước khi tìm hiểu về các chiến lược quản lý hàng đợi động chúng ta hãy xem xét chiến lược quản lý hàng đợi truyền thống và các nhược điểm của nó. 2.2.1. Chiến lược quản lý hàng đợi truyền thống và hệ quả Các cách tiếp cận quản lý hàng đợi truyền thống đều dựa trên cơ chế FIFO như đã trình bày ở phần trước. Với các cơ chế này thì gói tin khi tới gateway hoặc router sẽ được xếp vào hàng đợi, khi hàng đợi đầy thì các gói tin tới sau sẽ bị loại bỏ. Các gói tin tới trước sẽ được phụ vụ trước và hàng đợi này được mô phỏng trong bộ mô phỏng NS2 với tên gọi “DropTail”. Do tính đơn giản và dễ cài đặt mà nó được sử dụng trong nhiều năm trên Internet tuy nhiên do sự phát triển mạnh mẽ của mạng Internet ngày nay nó xuất hiện nhiều nhược điểm mà nổi bật nhất là hai nhược điểm sau đây 30 a. Hiện tượng Global Synchronization Theo cơ chế FIFO, chúng ta nói rằng các luồng khác bị “Lock Out” tại một thời điểm khi xuất hiện một luồng lưu lượng bùng nổ khiến cho hàng đợi bị chiếm độc quyền, các gói tin của các luồng lưu lượng khác không được nhận vào vì hàng đợi đầy. Khi xảy ra hiện tượng lockout nếu các thực thể sử dụng giao thức TCP để truyền thì chúng sẽ bị TimeOUT. Theo thuật toán tránh tắc ngẽn của TCP chúng sẽ đồng loạt giảm cửa số phát, thực hiện rút lui theo hàm mũ làm cho lưu lượng trên mạng đồng loại giảm nhanh chóng gây lãng phí băng thông đường truyền, làm giảm hiệu suất sử dụng. Hiện tượng đồng loạt giảm lưu lượng đó được gọi là hiện tượng đồng bộ toàn cầu – Global synchronization. b. Hiện tượng hàng đợi đầy (Full Queue) Hàng đợi FIFO có thể thường xuyên nằm trong trạng thái đầy trong trong thời gian dài nếu có nhiều luồng lưu lượng, vì cơ chế FIFO chỉ loại bỏ gói tin khi hàng đợi đã đầy. Lưu lượng trên mạng thường xuyên có sử bùng nổ và các gói tin tới các node mạng thường theo cụm nên bộ đệm tại các node mạng phải đủ lớn để hấp thu các lưu lượng bùng nổ này. Nhược điểm của nó là khi tăng kích thước bộ đêm để hấp thu các lưu lượng bùng nổ đồng thời sẽ làm gia tăng độ trễ và thăng giáng độ trễ. Ưu tiên sẽ là lựa chọn một cơ chế quản lý hàng đợi tốt thay vì tăng kích thước hàng đợi tại node mạng. Ngoài “DropTail” còn có 2 phương pháp khác có thể được sử dụng là loại bỏ gói tin ngẫu nhiên “Random Drop” và loại bỏ gói tin ở đầu “Drop Front”. Tư tưởng của Random Drop là các router sẽ loại bỏ ngẫu nhiên các gói tin trong hàng đợi để dành chỗ cho các gói tin đến. Còn với phương pháp Drop Front thì router sẽ loại bỏ các gói tin ở đầu hàng đợi. Cả 2 phương pháp này đều có thể khắc phục được hiện tượng “Lock-out” nhưng không khắc phục được hiện tượng đầy hàng đợi (Full Queue). 2.2.2. Ưu điểm các chiến lược quản lý hàng đợi động Như đã nói ở trên thì các chiến lược quản lý hàng đợi truyền thống sẽ loại bỏ gói tin khi hàng đợi đầy, điều nay không hợp lý vì đôi khi hàng đợi đầy thì hiện tượng tắc nghẽn đã trở nên khó kiểm soát. Giải pháp hợp lý cho trường hợp này là loại bỏ gói tin 31 trước khi hàng đợi đầy khi đó các thực thể gửi và nhận sẽ nhận biết và phản ứng với tắc nghẽn ngay khi hiện tượng tắc nghẽn bắt đầu xảy ra. Đây chính là tư tưởng chính của các chiến lược quản lý hàng đợi động – Active Queues Managerment AQM. Điểm cần chú ý rằng các chiến lược quản lý hàng đợi động này chỉ có hiệu quả đối khi được gắn với các giao thức vận chuyển có cơ chế kiểm soát lưu lượng (Flow control) như TCP, và nó không có hiệu quả đối với các giao thức như UDP. Các chiến lược quản lý hàng đợi động sẽ đem lại những ưu điểm sau: a. Giảm độ trễ và giảm thăng giáng độ trễ Việc loại bỏ sớm các gói tin khi tắc nghẽn chưa xảy ra sẽ giữ kích thước hàng đợi ở mức trung bình đủ nhỏ và làm giảm độ trễ một cách đáng kể. Điều này vô cùng quan trọng với các ứng dụng thời gian thực như voice, video thời gian thực b. Làm giảm số lượng gói tin bị loại bỏ tại các node mạng Mạng Internet ngày nay sự bùng nổ lưu lượng các gói tin là không thể tránh khỏi. Với chiến lược quản lý hàng đợi truyền thống kích thước hàng đợi tăng rất nhanh khi lưu lượng bùng nổ, các gói tin bị loại bỏ sẽ tăng nhanh khi hàng đợi đầy. Việc sử dụng các chiến lược quản lý hàng đợi động sẽ giúp cho kích thước hàng đợi nằm trong một khoảng trung bình đủ nhỏ, hàng đợi sẽ hấp thu các thăng giáng lưu lượng dễ dàng hơn khiến cho số gói tin bị loại bỏ giảm, hệ số sử dụng đường truyền tăng, việc khôi phục các gói tin bị mất đơn lẻ cũng dễ dàng hơn với TCP. c. Tránh hiện tượng Lock-out Hiện tượng lock-out xảy ra khi hàng đợi đầy, gói tin khi đi tới node mạng sẽ không được xếp vào hàng đợi vì không còn chỗ trống. AQM sẽ đảm bảo cho hàng đợi luôn luôn có chỗ trống dành cho các gói tin tới do đó tránh được hiện tượng này. Chúng ta sẽ tiến hành nghiên cứu 1 số thuật toán quản lý hàng đợi động tiêu biểu như RED, A-RED và RIO. 32 2.2.3. Thuật toán RED trong chiến lược quản lý hàng đợi động a. Giới thiệu thuật toán RED Khi có dấu hiệu của tắc nghẽn xảy ra trong mạng, hàng đợi tài router đầy thì router bắt đầu loại bỏ các gói tin đến. Đối với các luồng lưu lượng TCP thì đây là tín hiệu thông báo tắc nghẽn xảy ra và báo hiệu các nguồn phát giảm lưu lượng để giảm bớt tắc nghẽn. Có hai vấn đề quan trọng cần giải quyết: Thứ nhất là đối với các luông TCP thì các gói tin bị loại bỏ sẽ được truyền lại, điều này làm tăng tải trong mạng đồng thời phát sinh thêm độ trễ. Thứ hai là hiện tượng đồng bộ toàn cầu đã nói ở phân trên. Năm 1993 hai nhà khoa học của phòng thí nghiệm Lawrence Berkeley thuộc đại học California, Mỹ là Sally Floyd và Van Jacobson đã đề xuất thuật toán quản lý hàng đợi động AQM – một trong những thuật toán quản lý hàng đợi đầu tiên là RED – Random Early Detection of congestion, Random Early Drop. Với như ưu điểm vượt trội so với các thuật toán quản lý hàng đợi truyền thống nên RED đã được triển khai rộng rãi trên mạng Internet. Việc phát hiện sớm tắc nghẽn và phản ứng lại để giữ đường truyền ổn định thường được thực hiện trên các gateway. Các thực thể nguồn cũng có thể làm điều này thông qua thời gian phục vụ ước lượng tại gateway, thông qua độ trễ end-to-end, qua sự thay đổi thông lượng hoặc số lượng các gói tin bị loại bỏ. Tuy nhiên khung nhìn của một kết nối cụ thể bị giới hạn bởi thời gian phát tin và số lượng dữ liệu phát, ngoài ra nó cũng không thể biết được gateway nào đang tắc nghẽn, không phân biệt được độ trễ lan truyền và độ trễ hàng đợi. Chỉ có các Gateway là có cái nhìn đúng đắn nhất về trạng thái của hàng đợi, sự chia sẻ đường truyển của các kết nối đi qua nó tại mọi thời điểm cũng như yêu cầu chất lượng dịch vụ của các dòng lưu lượng. Các RED gateway sẽ theo dõi độ dài trung bình của hàng đợi để dựa vào đó phán đoán sớm tắc nghẽn sắp xảy ra (chiều dài của hàng đợi vượt quá một ngưỡng được định trước) và phản ứng một cách thích hợp đối với các gói tin đến theo hai cách:  Loại bỏ các gói tin đến theo một xác suất nhất định được định trước nhằm gián tiếp thông báo cho nguồn về sự tắc nghẽn đồng thời giữ kích thước hàng đợi nằm trong một ngưỡng đủ nhỏ  Đánh dấu cờ “có tắc nghẽn” theo một xác suất nhất định vào trường ECN trong header của các gói tin để báo cho bên nguồn biết. 33 b. Tư tưởng và nguyên tắc thiết kế thuật toán Mục đích chính của các RED gateway là điều khiển kích thước hàng đợi nằm trong một vùng đủ nhỏ được định nghĩa trước và ổn định. Ngoài ra nó còn tránh hiện tượng Global-Synchronization và không chống lại các luồng có lưu lượng đột biến, Duy trì kích thước hàng đợi ngay cả khi không có sự hợp tác từ các giao thức tầng giao vận Để đạt được những mục tiêu trên RED gateway phải làm được các công việc sau: - Phát hiện sớm tắc nghẽn và giữ kích thước hàng đợi trung bình đủ nhỏ làm cho mạng hoạt động ở vùng có độ trễ thấp, thông lượng cao, trong khi vẫn cho phép hàng đợi giao động trong một miền nhất định để hấp thu các luồng có lưu lượng đột biến hoặc độ thăng giáng cao. RED gateway là nơi thích hợp nhất để phát hiện tắc nghẽn và cũng là nơi thích hợp nhất để quyết định chọn kết nối cụ thể nào để thông báo tắc nghẽn. - Thông báo tới nguồn phát về tắc nghẽn có thể xảy ra. Việc này được thực hiện bằng cách đánh dấu và thông báo cho nguồn phát giảm lưu lượn xuống. Thông thường RED gateway sẽ loại bỏ gói tin, tuy nhiên nếu tắc nghẽn được phát hiện sớm thì thay vì loại bỏ nó RED gateway sẽ có 2 lựa chọn là đánh dấu hoặc loại bỏ gói tin. Việc đánh dấu gói tin được thực hiện bằng cách đánh dấu vào trường ECN trong header của gói tin với một xác suất nhất định để báo hiệu cho nguồn giảm lưu lượng đưa vào mạng. - Mục tiêu quan trọng cần đạt được là tránh hiện tượng Global-synchronization và không chống lại các luồng có lưu lượng đột biến. Như đã trình bày ở các phần trước hiện tượng này xảy ra khi các thực thể phát đồng loại giảm kích thước cửa sổ phát làm lưu lượng giảm nhanh trong cùng một thời điểm. Các chiến lược như Droptail hoặc Random Drop rất nhạy cảm với các luồng lưu lượng đột biến tức là các hàng đợi tại gateway thường sẽ bị tràn khi các gói tin của luồng này tới. Để tránh hiện tượng này các RED gateway phải chọn các gói tin ngẫu nhiên tới để đánh dấu. Với phương pháp này xác suất đánh dấu một gói tin từ một kết nối cụ thể tỉ lệ với phần băng thông được chia sẻ cho kết nối đó tại gateway. - Một mục tiêu quan trọng nữa của RED gateway cần đạt được đó là giữ kích thước hàng đợi trung bình ngay cả khi không có sự hợp tác từ các thực thể nguồn phát (nguồn phát sử dụng giao thức UDP). Có thể thực hiện điều này bằng cách loại bỏ 34 gói tin khi kích thước trung bình của hàng đợi vượt qua ngưỡng trên thay vì đánh dấu nó. Phương pháp này là cần thiết trong trường hợp hầu hết các kết nối có khoảng thời gian phát nhỏ hơn thời gian đợi gói tin khứ hồi hoặc các thực thể nguồn không có các cơ chế kiểm soát lưu lượng để phản ứng với việc đánh dấu hay loại bỏ gói tin (như các luồng UDP) c. Giải thuật và các tham số cho thuật toán RED RED gateway tính kích thước hàng đợi trung bình bằng cách sử dụng bộ lọc thông thấp LPF (Low Pass Filter). Kích thước hàng đợi trung bình được so sánh với hai ngưỡng : Ngưỡng dưới 𝑚𝑖𝑛𝑡ℎ và ngưỡng trên 𝑚𝑎𝑥𝑡ℎ. Khi kích thước hàng đợi trung bình nhỏ hơn ngưỡng dưới thì không gói tin nào bị đánh dấu hoặc loại bỏ, Khi kích thước hàng đợi trung bình nằm trong khoảng 𝑚𝑖𝑛𝑡ℎ đến 𝑚𝑎𝑥𝑡ℎ thì RED gateway sẽ đánh dấu các gói tin đến với một xác suất 𝑝𝑎. Trong đó 𝑝𝑎 là một hàm theo kích thước hàng đợi trung bình avg. Xác suất đánh dấu một gói tin của một kết nối cụ thể tỉ lệ với phần băng thông chia sẻ của kết nối đó tại gateway. Giải thuật được mô tả trong giải mã sau: Hình 2.7: Giải thuật tổng quát cho RED gateway Như vậy giải thuật tại RED gateway được chia thành hai thuật toán tách biệt: Thuật toán tính kích thước hàng đợi trung bình quyết định mức độ bùng nổ cho phép trong hàng đợi tại gateway và Thuật toán tính xác suất đánh dấu quyết định mức độ thường xuyên đánh dấu gói tin của gateway. Giải thuật đánh dấu gói tin phải đảm bảo sao cho các gói tin đánh dấu tại những khoảng thời gian đều nhau để tránh hiện tượng đồng bộ toàn cầu trong khi vẫn giữ kích thước hàng đợi trunh bình ở một khoảng nhất định Giải thuật chi tiết được mô tả dưới đây: Với mỗi gói tin đến gateway Tính toán kích thước hàng đợi trung bình avg Nếu 𝑚𝑖𝑛𝑡ℎ < kích thước hàng đợi trung bình avg < 𝑚𝑎𝑥𝑡ℎ Tính xác xuất 𝑝𝑎 Với 𝑝𝑎: Đánh dấu các gói tin đến Nếu 𝑚𝑎𝑥𝑡ℎ < kích thước hàng đợi trung bình avg Đánh dấu gói tin đến 35 Hình 2.8: Giải thuật RED chi tiết Khởi tạo: avg ← 0 count ← -1 for mỗi gói tin đến Tính kích thước hàng đợi trung bình avg: if hàng đợi không rỗng avg ← (1- 𝑤𝑞) avg + 𝑤𝑞*q else m ← f(time – q_time) avg ← (1-𝑤𝑞)m avg if 𝑚𝑖𝑛𝑡ℎ≤ avg < 𝑚𝑎𝑥𝑡ℎ count ++ Tính xác suất 𝑝𝑎: 𝑝𝑎 ← 𝑚𝑎𝑥𝑝 (agv – 𝑚𝑖𝑛𝑡ℎ)/( 𝑚𝑎𝑥𝑡ℎ - 𝑚𝑖𝑛𝑡ℎ) 𝑝𝑎 ← 𝑝𝑏 / (1 – count. 𝑝𝑏) với xác suất 𝑝𝑎: đánh dấu gói tin đến count ← 0 else if avg ≥ 𝑚𝑎𝑥𝑡ℎ đánh dấu gói tin đến count ← 0 else count ← -1 Khi Khi hàng đợi trở nên rỗng q_time ← time 36 Hình 2.9 Các tham số thuật toán RED Theo giải thuật, mỗi khi có một gói tin đi đến hàng đợi, RED gateway sẽ tính kích thước hàng đợi trung bình bằng bộ lọc: avg ← (1- 𝑤𝑞) avg + 𝑤𝑞*q trong đó : q là kích thước hàng đợi trung bình hiện thời; 𝑤𝑞 là trọng sô của hàng đợi và nhận giá trị trong khoảng 0..1. 𝑤𝑞 còn gọi là hệ số làm trơn và quyết định độ lớn và độ kéo dài cho phép của sự bùng nổ lưu lượng. Xác suất đánh dấu gói tin 𝑝𝑎 tăng chậm khi số gói tin từ gói cuối cùng được đánh dấu count tăng lên. Điều này đảm bảo cho gateway không phải chờ quá lâu trước khi đánh dấu một gói tin. RED gateway đánh dấu tất cả các gói tin nếu như kích thước hàng đợi trung bình avg vượt quá 𝑚𝑎𝑥𝑡ℎ Thêm 1 tùy chọn trong RED để đảm bảo xác suất để một gói tin bị loại bỏ tỉ lệ với thông lượng tính bằng bit/s chứ không phải packet/s. Trong trường hợp này thì một gói tin lớn sẽ dễ bị loại bỏ hơn một gói tin có kích thước nhỏ. 𝑝𝑏 = 𝑃𝑎𝑐𝑘𝑒𝑡𝑆𝑖𝑧𝑒 𝑀𝑎𝑥𝑃𝑎𝑐𝑘𝑒𝑡𝑆𝑖𝑧𝑒 ∗ 𝑚𝑎𝑥𝑝 ∗ 𝑎𝑣𝑔−𝑚𝑖𝑛𝑡ℎ 𝑚𝑎𝑥𝑡ℎ−𝑚𝑖𝑛𝑡ℎ Các biến thay đổi: avg: kích thước hàng đợi trung bình q_time: thời gian hàng đợi bắt đầu rỗng count: số gói tin từ gói cuối cùng bị đánh dấu Các tham số cố định: 𝑤𝑞: trọng số hàng đợi 𝑚𝑖𝑛𝑡ℎ: ngưỡng dưới của hàng đợi 𝑚𝑎𝑥𝑡ℎ: ngưỡng trên của hàng đợi 𝑚𝑎𝑥𝑝: xác suất loại bỏ tối đa Các tham số khác: 𝑝𝑎: xác suất đánh dấu gói tin hiện tại q: kích thước hàng đợi hiện tại time: thời gian hiện tại f(t): một hàm tuyến tính của thời gian t 37 Có bốn tham số cố định cần đặt trước trong thuật toán RED. Việc thiết lập các thuật toán này là rất quan trọng vì nó ảnh hưởng tới chất lượng cũng như hiệu suất thuật toán. Để mang lại hiệu quả cao nhất cho thuật toán chúng tôi sẽ trình bày song song hai cách thiết lập các tham số: Định tính và định lượng (bằng mô phỏng) để có thể chọn ra một bộ tham số hợp lý và đêm lại hiệu quả cao nhất. Tất cả mô phỏng trong luận văn này đều được thực hiện trên bộ mô phỏng NS-2. Các tham số đầu vào được tác giả trong [3] nghiên cứu rất kỹ bằng mô phỏng, sau khi lặp lại các mô phỏng đó và thấy rằng các kết quả đó là hoàn toàn chính xác. d. Trọng số hàng đợi 𝒘𝒒 Kích thước hàng đợi trung bình trong thuật toán RED được RED gateway tính toán bằng cách sử dụng bộ lọc thông thấp. Sự gia tăng kích thước hàng đợi hiện tại do luồng lưu lượng bùng nổ hoặc sử tắc nghẽn ngắn hạn sẽ không ảnh hưởng tới kích thước hàng đợi kích thước hàng đợi trung bình: avg ← (1- 𝑤𝑞) avg + 𝑤𝑞*q trong đó trọng số hàng đợi 𝑤𝑞 đóng vai trò quyết định giá trị của avg. Nhìn vào công thức trên có thể thấy răng nếu 𝑤𝑞 quá lớn thì kích thước hàng đợi trung bình avg sẽ bám sát kích thước hàng đợi vào thời điểm hiện tại, khiến cho hàng đợi trống rất ít. RED gateway sẽ không thể hấp thu được các luồng có lưu lượng bùng nổ. Cận trên cho 𝒘𝒒 Giả sử ban đầu hàng đợi rỗng (kích thước trung bình bằng 0), sau đó khi có các gói tin đến, số gói tin trong hàng đợi sẽ tăng từ 0 đến L (giả sử có L gói tin đi đến hàng đợi) lúc này kích thước hàng đợi trung bình sẽ được tính như sau: 𝑎𝑣𝑔𝐿 = ∑ 𝑖𝑤𝑞(1 − 𝑤𝑞) 𝐿−𝑖𝐿 𝑖=1 =𝑤𝑞(1 − 𝑤𝑞) 𝐿 ∑ 𝑖( 1 1−𝑤𝑞 )𝑖𝐿𝑖=1 = L + 1 + (1−𝑤𝑞) 𝐿−𝑖−1 𝑤𝑞 Với ngưỡng 𝑚𝑖𝑛𝑡ℎ cho trước và chúng ta muốn cho phép RED gateway hấp thu bùng nổ đến L gói tin thì kích thước hàng đợi trung bình 𝑎𝑣𝑔𝐿 < 𝑚𝑖𝑛𝑡ℎ L + 1 + (1−𝑤𝑞) 𝐿−𝑖−1 𝑤𝑞 < 𝑚𝑖𝑛𝑡ℎ 38 Cận dưới cho 𝒘𝒒 Thuật toán RED được thế kế sao cho RED gateway luôn giữ hàng đợi ở mức trung bình nằm dưới một ngưỡng nào đó. Tuy nhiên nếu giá trị 𝑤𝑞 được thiết lập quá thấp thì avg sẽ phản ứng rất chậm với sự thay đổi nhanh của hàng đợi thực khiến cho gateway không thế phát hiện được sự bắt đầu của tắc nghẽn. Theo các nghiên cứu và thực nghiệm về thuật toán RED người ta khuyến cáo 𝑤𝑞 ≥ 0.001. Tùy điều kiện của mạng thực tế có thể lựa chọn 𝑤𝑞 nằm trong khoảng (0.002,0.003). e. Xác suất loại bỏ gói tin 𝒎𝒂𝒙𝒑 Số lượng gói tin bị loại bỏ tại RED gateway phụ thuộc vào giá trị của 𝑚𝑎𝑥𝑝 và sẽ quyết định kích thước hàng đợi trung bình avg sẽ nằm trong khoảng nào giữa 𝑚𝑖𝑛𝑡ℎ và 𝑚𝑎𝑥𝑡ℎ. Vì thế tùy từng yêu cầu của mạng trong thực tế mà chúng ta lựa chọn giá trị 𝑚𝑎𝑥𝑝 phù hợp. Đối với mạng ít xảy ra tắc nghẽn thì nên thiết lập giá trị 𝑚𝑎𝑥𝑝 nhỏ để tận dụng tối đa đường truyền và giảm số gói tin bị loại bỏ. Giá trị phù hợp ở đây thường là 𝑚𝑎𝑥𝑝 = 0.02. Tuy nhiên đối với mạng hay xảy ra tắc nghẽn thì giá trị 𝑚𝑎𝑥𝑝 thường được thiết lập lớn hơn. Giá trị thường được chọn là 𝑚𝑎𝑥𝑝 = 0.1 f. Thiết lập ngưỡng 𝒎𝒊𝒏𝒕𝒉 và 𝒎𝒂𝒙𝒕𝒉 Để thiết lập được giá trị tối ưu cho 𝑚𝑖𝑛𝑡ℎ và 𝑚𝑎𝑥𝑡ℎ cần xem xét tới rất nhiều yếu tố, trong đó có kích thước hàng đợi trung bình mong muốn avg. Giá trị 𝑚𝑖𝑛𝑡ℎ và 𝑚𝑎𝑥𝑡ℎ cần phải thoải mãn các yêu cầu sau: - Để tận dụng tối đa đường truyền thì 𝑚𝑖𝑛𝑡ℎ và 𝑚𝑎𝑥𝑡ℎ cần được thiết lập giá trị cao trong trường hợp lưu lượng trên mạng ít đột biến - Nếu lưu lượng trong mạng thường xuyên có đột biến thì 𝑚𝑖𝑛𝑡ℎ và 𝑚𝑎𝑥𝑡ℎ cần được thiết lập giá trị nhỏ để có thể hấp thu các lưu lượng này. Tuy nhiên khi thiết lập giá trị nhỏ cho 𝑚𝑖𝑛𝑡ℎ và 𝑚𝑎𝑥𝑡ℎ khiến cho hiệu suất sử dụng đường truyền thấp gây lãng phí dải thông, số gói tin bị loại bỏ không cần thiết sẽ cao hơn. Vì vậy cần cân bằng giữa việc tận dụng tối đa đường truyền và khả năng hấp thu lưu lượng bùng nổ sao cho hiệu suất sử dụng đường truyền là cao nhất. 39 - Khoảng giá trị 𝑚𝑖𝑛𝑡ℎ và 𝑚𝑎𝑥𝑡ℎ ảnh hưởng tới biến thiên độ trễ, thông lượng và khả năng hấp thu các đột biến tạm thời tại hàng đợi. Để tránh hiện tượng đồng bộ toàn cầu thì không nên đề khoảng giá trị này quá nhỏ. Theo khuyến nghị thì nên thiết lập 𝑚𝑎𝑥𝑡ℎ gấp đôi giá trị 𝑚𝑖𝑛𝑡ℎ 2.2.4. Thuật toán A-RED Điều khiển tắc nghẽn đầu cuối được sử dụng rộng rãi trong các mạng ngày này để ngăn chặn tắc nghẽn xảy ra. Tuy nhiên do lưu lượng dữ liệu đến các router dưới dạng luồng nên các router cần được cung cấp hàng đợi lớn để hấp thu các lưu lượng bùng nổ giúp duy trì việc sử dụng các kết nối. Khi tắc nghẽn xảy ra tại các router các gói tin sẽ bị gia tăng độ trễ hàng đợi. Do đó cần phải chọn lựa giữa hiệu suất sử dụng đường truyền cao (Kích thước hàng đợi lớn) hay độ trễ hàng đợi nhỏ (Kích thước hàng đợi nhỏ). Thuật toán quản lý hàng đợi RED thì tích cực hơn do sử dụng quá trình loại bỏ ngẫu nhiên bằng việc thay đổi kích thước hàng đợi trung bình. Mục tiêu chính của RED là phối hợp giữa kích thước hàng đợi trung bình và thông báo tắc nghẽn sớm để đạt được độ trễ hàng đợi trung bình thấp và thông lượng cao Chiến lược quản lý hàng đợi động bằng cách sử dụng thuật toán RED cho phép mạng đồng thời đạt được cả thông lượng cao và độ trễ thấp. Tuy nhiên RED có hai yếu điểm cơ bản cần phải được khắc phục. Thứ nhất là kích thước hàng đợi trung bình nhạy cảm với các cấp đội tắc nghẽn và các tham số đầu vào thiết lập trên router. Đối với mạng có sự thay đổi lớn về các cấp độ tắc nghẽn thì việc thiết lập một bộ tham số đầu vào cho RED gateway là khó. Độ trễ là một thành phần chính của QoS cấp phát cho người dùng, để đạt được độ trễ trung bình có thể đoán trước thì cần phải liên tục hiệu chỉnh các tham số đấu vào của thuật toán RED đáp ứng sự thay đổi liên tục của lưu lượng dữ liệu trên mạng. Điểm yếu thứ hai của RED là thông lượng cũng nhạy cảm với tải và các thông số đầu vào của RED. Thường thì khi kích thước hàng đợi trung bình avg lớn hơn 𝑚𝑎𝑥𝑡ℎ thì thuật toán RED không còn hiệu quả dẫn tới việc giảm đáng kể thông lượng và tăng tỷ lệ loại bỏ gói tin. Để tránh hiện tượng này thì cũng cần liên tục điều chỉnh các tham số đầu vào của thuật toán RED. 40 a. Giải thuật A-RED A-RED ra đời nhằm khắc phục hai nhược điểm của RED nguyên bản được đề xuất bởi Feng từ năm 1997[17]. Cấu trúc RED vẫn được giữ nguyên và chỉ hiệu chỉnh thông số 𝑚𝑎𝑥𝑝 để duy trì kích thước hàng đợi trung bình trong khoảng 𝑚𝑖𝑛𝑡ℎ đến 𝑚𝑎𝑥𝑡ℎ. Có nhiều phiên bản A-RED được đưa ra tuy nhiên trong giới hạn luận án này chúng tôi giới thiệu một phiên bản thuật toán A-RED trong đó người quản trị viên có thể lựa chọn chế độ tự động thiết lập các tham số đầu vào cho RED gateway dựa trên độ trễ mong muốn và kích thước miền hàng đợi trung bình mong muốn. Như vậy thuật toán A-RED này có thể tự động thiết lập tất cả các tham số đầu vào của thuật toán RED dựa trên kết quả mong muốn đạt được tránh trong những hạn chế lớn của RED 𝑚𝑎𝑥𝑝 được hiểu chỉnh không chỉ cho kích thước hàng đợi trung bình nằm trong ngưỡng 𝑚𝑖𝑛𝑡ℎ, 𝑚𝑎𝑥𝑡ℎ mà còn giữ kích thước hàng đợi trung bình nằm trong một dải cho phép nằm trong khoảng 𝑚𝑖𝑛𝑡ℎ, 𝑚𝑎𝑥𝑡ℎ. Giá trị 𝑚𝑎𝑥𝑝 được duy trì nằm trong khoảng từ 0.01 đên 0.5. Bằng mô phỏng có thể thấy rằng A-RED đạt được độ dài hàng đợi trung bình đích với một miền rộng các kịch bản, có nghĩa là nó giữ nguyên được những ưu điểm của RED. Điều này giúp quản trị viên dự đoán được độ trễ hàng đợi trung bình và hạn chế khả năng kích thước hàng đợi trung bình vượt quá ngưỡng 𝑚𝑎𝑥𝑡ℎ từ đó giảm tỉ lệ mất gói tin và sự thăng giáng độ trễ hàng đợi. b. Giải thuật và các tham số trong thuật toán A-RED Thuật toán A-RED cơ bản chia làm hai thuật toán chính la: Thuật toán RED và thuật toán hiệu chỉnh 𝑚𝑎𝑥𝑝, 𝑚𝑖𝑛𝑡ℎ, 𝑚𝑎𝑥𝑡ℎ. Sau đó 𝑚𝑎𝑥𝑝 lại được dùng trong thuật toán RED. Thuật toán hiệu chỉnh 𝑚𝑎𝑥𝑝 được trình bày như Hình 2.10: 41 Hình 2.10: Giải thuật tổng quát cho A-RED gateway Giới hạn trên của giá trị 𝑚𝑎𝑥𝑝 = 0.5 có thể được chỉnh sửa theo cách cố gắn tối ưu RED để tốc độ loại bỏ gói tin nhỏ hơn 50% 2.2.5. Thuật toán RIO Giới thiệu chung Phần này chúng ta sẽ nghiên cứu về việc áp dụng các thuật toán quản lý hàng đợi động trong kiến trúc các dịch vụ phân loại Diffserv. Kiến trúc này được định nghĩa bời IETF nhằm cung cấp cho mạng IP sự đảm bảo chất lượng dịch vụ cho các lưu lượng khác nhau cùng chia sẻ kênh truyển chung. Bằng việc sử dụng cờ đánh dấu trong một số trường đặc biệt của gói tin IP để báo cho Router biết cách xử lý nào được áp dụng cho mỗi gói tin. Điển hình của thuật toán quản lý hàng đợi động được áp dụng cho kiến trúc mạng dịch vụ phân loại DiffServ là thuật toán A-RIO (Adaptive RED with IN and OUT). Thuật toán này là sự kết hợp của A-RED và thuật toán RIO được đề xuất bởi Julio Orozco, David Ros với mục đích chính bao gồm: - Áp dụng cho kiến trúc mạng DiffServ nhằm đảm bảo chất lượng dịch vụ cho các dịch vụ trong trường hợp nhiều luồng lưu lượng cùng chia sẻ một kênh truyền bằng việc sử dụng các bit trong trường TOS của gói tin ip. Every interval giây: if (avg > target and 𝑚𝑎𝑥𝑝 ≤ 0.5) tăng 𝑚𝑎𝑥𝑝: 𝑚𝑎𝑥𝑝 = 𝑚𝑎𝑥𝑝 + α; elseif (avg < target and 𝑚𝑎𝑥𝑝 ≥ 0.01) giảm 𝑚𝑎𝑥𝑝: 𝑚𝑎𝑥𝑝 = 𝑚𝑎𝑥𝑝 * β; Biến: avg: kích thước hàng đợi trung bình Các tham số cố định: interval: thời gian; 0.5 giây target: target for avg: [𝑚𝑖𝑛𝑡ℎ + 0.4 * (𝑚𝑎𝑥𝑡ℎ – 𝑚𝑖𝑛𝑡ℎ), 𝑚𝑖𝑛𝑡ℎ + 0.6 * (𝑚𝑎𝑥𝑡ℎ – 𝑚𝑖𝑛𝑡ℎ)] α: hệ số tăng; min(0.01, maxp / 4); β: hệ số giảm; 0.9 42 - Đơn giản hóa cấu hình cho Router bằng việc tính toán tự động để chuyển đổi các tham số đầu vào sang tham số routers. - Cố gắng giữ hàng đợi ở mức trung bình ổn định quanh một giá trị khi tải nặng không phụ thuộc vào hiện trạng lưu lượng a. Ý tưởng Thuật toán RIO Đối với các thuật toán như RED, A-RED router chỉ thực hiện tính toán hàng đợi trung bình sau đó tiến hành đánh dấu hoặc loại bỏ gói tin, các gói tin đều được đối xử bình đẳng với nhau và không có sự phân biệt ưu sự ưu tiên. Tuy nhiên trong thực tế hiện nay khi mà tốc độ phát triển mạnh của Internet khiến cho sự đa dạng trong dịch vụ cũng tăng. Người dùng hoàn toàn có thể yêu cầu nhà cung cấp để được sự ưu tiên cao hơn và chấp nhận trả chi phí lớn hơn. Nếu sử dụng thuật toán RED hoặc A-RED cho trường hợp này thì không thể giải quyết được bài toán, các luồng (ứng dụng) đã trả nhiều tiền hơn cũng chỉ được cung cấp 1 lượng dịch vụ như những luồng khác. Chính vì lẽ đó thuật toán RIO ra đời dựa trên sự cải tiến của thuật toán RED bằng cách phân chia các gói tin đến theo hai mức ưu tiên là “In” và “Out”. Việc gắn thẻ cho mỗi gói tin phụ thuộc vào thỏa thuận giữa khách hàng và nhà cung cấp dịch vụ theo đó, các gói tin có gắn thẻ “In” nghĩa là các gói tin này nằm trong dịch vụ đã được thỏa thuận trước, các gói tin có gắn thẻ “Out” có nghĩa là không nằm trong hồ sơ dịch vụ. Khi tắc nghẽn xảy ra các router sẽ ưu tiên loại bỏ các gói tin có gắn thẻ “Out” nhanh hơn. Tuy nhiên RIO không phân tách các luồng thành các lớp hoặc các hàng đợi khác nhau mà gộp tất cả chung vào một hàng đợi. RIO là viết tắt của RED with In/Out bit. Vì được cải tiến từ RED nên nó có đầy đủ các ưu điểm của RED như đạt thông lượng cao, hiệu suất sử dụng đường truyền lớn, độ trễ thấp, kích thước hàng đợi trung bình nhỏ ngoài ra nó còn phân biệt các gói tin theo hai mức ưu tiên là “In” và “Out”. Việc sử dụng bộ đôi thuật toán RED cho các gói tin “In” và “Out” với thiết lập thông số khác nhau khiến cho các gói tin “Out” bao giờ cũng bị loại bỏ sớm hơn khi tắc nghẽn xảy ra. b. Giải thuật Tương tự như RED nhưng RIO được thiết lập hai bộ tham số riêng biệt, một bộ dành cho các gói tin với thẻ “In” và một bộ tham số dành cho gói tin thẻ “Out”. Khi một 43 gói tin đi tới RIO gateway nó sẽ kiểm tra xem gói tin này có gắn thẻ “In” hay “Out” và tính toán hàng đợi trung bình tương ứng với các gói tin. Nếu gói tin đi tới có gắn cơ “In” thì RIO gateway sẽ tính avg_in, ngược lại nếu gói tin đi tới có gắn thẻ Out thì RIO gateway sẽ tính avg_total. Xác suất loại bỏ gói tin “In” phụ thuộc vào kích thước hàng đợi trung bình avg_in và xác suất loại bỏ gói tin “Out” phụ thuộc vào kích thước hàng đợi trung bình avg_total. Giải thuật được mô tả như Hình 2.11 dưới đây: Hình 2.11 Giải thuật RIO RIO gateway sẽ loại bỏ hầu hết các gói tin có gắn thẻ “Out” khi tắc nghẽn bắt đầu xảy ra và khi tắc nghẽn kéo dài sẽ loại bỏ toàn bộ các gói tin “Out”, Các gói tin “In” rất ít khi bị loại bỏ trừ trường hợp tắc nghẽn xảy ra do toàn bộ các gói tin “In”. Tuy nhiên với mạng được điều khiển tốt thì trường hợp này rất ít khi xảy ra và nếu xảy ra trường hợp đó thì mạng có thể coi là không chấp nhận được. Chưa có bất cứ chuẩn mực nào trong việc lựa chọn avg_total sao cho hợp lý. Nếu ta chọn avg_out dành cho các gói tin “Out” thì việc lựa chọn tham số cho hàng đợi trung For mỗi gói tin đến if nó là gói tin In tính kích thước trung bình hàng đợi In: avg_in; tính kích thước trung bình hàng đợi tổng avg_total; if nó là gói tin In if min_in < avg_in < max_in tính xác suất 𝑃𝑖𝑛; loại bỏ gói tin này với xác suất 𝑃𝑖𝑛; else if max_in < avg_in loại bỏ gói tin này. if nó là gói tin Out if min_out <avg_total < max_out tính xác suất 𝑃𝑜𝑢𝑡; loại bỏ gói tin này với xác suất 𝑃𝑜𝑢𝑡; else if max_out <avg_total loại bỏ gói tin này; 44 bình này rất khó và không có sự tương quan rõ ràng nào giữa các tham số dành cho gói in “In”. Việc sử dụng avg_total dành cho cả hai loại gói tin giúp cho RIO gateway có thể giữ được kích thước hàng đợi trung bình đủ nhỏ và đạt được thông thượng cao bất kể lưu lượng nào trộn lẫn vào. 2.2.6. Thuật toán A-RIO Đây là một mở rộng trực tiếp từ thuật toán A-RED và RIO. A-RIO đi theo cách tiếp cận của thuật toán A-RED, các thông số đầu vào của thuật toán được hiệu chỉnh online một cách tự động nhằm đạt được hiệu suất mong muốn đã đặt trước, có nhiều cách tiếp cận được đưa ra nhằm hiệu chỉnh các thông số thuật toán RED theo kết quả mong muốn đạt được, A-RED được chọn vì tính đơn giản trong cài đặt của nó. Giống như A-RED, A-RIO chỉ cần một tham số đầu vào là độ trễ mà người dùng mong muốn đạt được, A-RIO sẽ tự động ánh xạ sang tập các tham số đầu vào. Đặc trưng này rất có ý nghĩa đối với nhà cung cấp dịch vụ phân loại cấu hình router theo độ trễ - một độ đo QoS liên quan trực tiếp đến đặc tả dịch vụ và đặc tả yêu cầu người dùng, dễ hiểu hơn rất nhiều so với các tham số trìu tượng như các ngưỡng hàng đợi, xác suất loại bỏ gói tin hoặc trọng số trung bình. Do là mở rộng trực tiếp từ thuật toán A-RED nên A-RIO vẫn giữ được những ưu điểm và đặc trung của A-RED như:  Xác suất loại bỏ gói tin 𝑚𝑎𝑥𝑝 chạy từ 0.01 đến 0.5  Ngưỡng dưới 𝑚𝑖𝑛𝑡ℎ được tính theo độ trễ hàng đợi mong muốn (đích) 𝑑𝑡 và dung lượng đường truyền C (packet/s) với cận dưới là 5 gói tin thì: 𝑚𝑖𝑛𝑡ℎ = max (5, 𝑑𝑡 . 𝐶/2). Ngưỡng 𝑚𝑎𝑥𝑡ℎ luôn được tính cố định bằng 3. 𝑚𝑖𝑛𝑡ℎ  𝑤𝑞 cũng được tính theo dung lượng đường truyền: 𝑤𝑞 = 1 − exp (−1/𝐶)  Nếu tải thay đổi một cách đột ngột thì kích thước hàng đợi trung bình có thể nằm ngoài khoảng mục tiêu, khi đó các tham số α, β được chọn cố định sao cho kích thước hàng đợi trung bình sẽ quay trở lại miền mục tiêu trong vòng 25 giây. 45  Hàm hiệu chỉnh 𝑚𝑎𝑥𝑝 (𝑖) được tính theo luật AIMD (tăng theo cấp số cộng, giảm theo cấp số nhân) nhằm tránh sự thay đổi đột ngột của 𝑚𝑎𝑥𝑝 (𝑖) dẫn tới sự dao động mạnh của kích thước hàng đợi. Trên đây là một số thuật toán quản lý hàng đợi động điển hình, ngoài ra còn nhiều thuật toán khác là biến thể từ các thuật toán trên nhưng không được đề cập trong nội dung luận văn, các thuật toán đều có ưu, nhược điểm riêng tùy vào từng trường hợp mạng cụ thể mà người ta có thể chọn chiến lược sao cho đạt được hiệu quả cao nhất. Chương tiếp theo sẽ trình bày mô phỏng để đánh giá các thuật toán quản lý hàng đợi động RED và FIFO truyền thống, áp dụng thuật toán RED trong kiến trúc mạng DiffServ nhằm đảm bảo chất lượng dịch vụ cho các ứng dụng đa phương tiện thời gian thực trên Internet. 46 Chương 3. ĐÁNH GIÁ HIỆU QUẢ ĐẢM BẢO QOS CHO TRUYỀN THÔNG ĐA PHƯƠNG TIỆN THỜI GIAN THỰC CỦA MỘT SỐ CHIẾN LƯỢC QUẢN LÝ HÀNG ĐỢI 3.1. Đánh giá bằng mô phỏng hiệu quả của thuật toán RED Các mô phỏng trong luận văn này được thực hiện trên bộ mô phỏng NS-2 đã được cộng đồng nghiên cứu và sử dụng rộng rãi đặc biệt là trong các trường đại học và các viện nghiên cứu. Sau đây là phần trình bày mô phỏng của tôi nhằm đánh giá và so sánh hiệu suất của thuật toán RED so với DropTail Hình 3.1: Cấu hình mạng mô phỏng DropTail & RED Mô phỏng đánh giá hiệu suất của thuật toán RED so với DropTail, mỗi loại tôi đưa ra 3 đồ thị biểu diễn đó là : Kích thước hàng đợi trung bình, thông lượng, và kích thước cửa sổ của mỗi kết nối TCP để tìm ra ưu nhược điểm của 2 giải thuật quản lý hàng đợi này. Mạng mô phỏng bao gồm 6 nút, các luồng tcp1, tcp2, tcp3 được gắn vào các nút 1, 2, 3. Luồng udp được gắn vào nút 4, đường truyền chia sẻ từ nút 0 đến nút 5, tại đây sử dụng hàng đợi RED hoặc DropTail, tất cả các kết nối đều là full-duplex và mặc định không lỗi. 47  Kết nối từ nút 0 đến nút 1, 2, 3 có băng thông 10Mbps, độ trễ 1ms.  Kết nối từ nút 0 đến nút 4 có băng thông 2Mbps, độ trễ 10ms.  Kết nối từ nút 0 đến nút 5 có băng thông 2Mbps, độ trễ 20ms. Sử dụng hàng đợi RED hoặc DropTail  Các thực thể gắn với 3 luồng TCP ở đây là giao thức FTP (ftp1, ftp2, ftp3). Kích thước các gói tin TCP được gửi đỉ là 1000byte với kích thước cửa sổ tối đa là 100 gói tin. Các thực thể này phát gói tin theo thời gian ngẫu nhiên trong khoảng từ 0 – 3s từ lúc bắt đầu chạy mô phỏng.  Thực thể gắn với luồng udp ở đây là nguồn phát CBR (Nguồn phát sinh lưu lượng không đổi có tốc độ phát là 2Mbps). Thực thể udp bắt đầu sinh lưu lượng vào khoảng 5 – 7s và từ 8 – 10s để tạo lưu lượng đột biến  Hàng đợi được đặt trên kết nối từ node 0 đến node 5 kích thước 100 gói tin. Toàn bộ mô phỏng được chạy trong khoảng thời gian 50s.  Các tham số được thiết lập cho RED như sau: minth = 5, maxth = 15, maxp = 0.1 và wq = 0.002. Sau khi chạy mô phỏng 2 thuật toán trên với cùng một kích bản mô phỏng chúng thu được kết quả: Chiến lược Số gói tin (packet) Kích thước hàng đợi trung bình (packet) Độ trễ hàng đợi trung bình (ms) Hệ số sử dụng đường truyền (%) DropTail 11944 73.00 389.33 95.55 RED 11728 8.00 42.67 93.82 Bảng 3.1: So sánh RED với DropTail 48 Hình 3.2: Mô phỏng DropTail Hình 3.3: Mô phỏng RED a) Kích thước hàng đợi trung bình a) Kích thước hàng đợi trung bình b) Kích thước cửa sổ b) Kích thước cửa sổ c) Thông lượng trung bình các kết nối c) Thông lượng trung bình các kết nối 49 Nhận xét về kết quả mô phỏng chiến lược DropTail: Nhìn đồ thị có thể thấy được rằng hiện tượng lockout xảy ra khi có lưu lượng đột vào khoảng thời gian từ 5 – 7s và từ 8 – 10s (Nguồn CBR sinh lưu lượng có tốc độ cao hơn dung lượng đường truyền tại nút 0) dẫn tới việc các kết nối TCP đồng loạt giảm kích thước cửa sổ phát, dẫn tới việc thông lượng của các kết nốt TCP giảm đột ngột về gần bằng 0. Ngay cả khi nguồn CBR đã ngừng hoạt động vào khoảng 10 - 12s thì thông lượng của các luồng TCP vẫn giảm về gần 0 do cơ chế rút lui theo hàm mũ của TCP trong khi đó thì hàng đợi vẫn đầy. DropTail đã không tránh khỏi hiện tượng Global Synchronization. Ngay cả khi nguồn CBR không hoạt động thì hiện tượng Global Synchronization vẫn xảy ra vào các khoảng thời gian 24s, 34s, 44s, khi các kết nối TCP cùng tăng kích thước cửa sổ phát đạt đến ngưỡng và đồng loạt giảm. Kích thước trung bình của hàng đợi luôn giữ ở mức rất cao. Nhận xét về kết quả mô phỏng chiến lược RED: Trong gian đoạn 12s đầu tiên khi có lưu lượng đột biến vào mạng thì các kết nối TCP giảm kích thước cửa sổ phát dẫn tới việc thông lượng của các kết nối này giảm tuy nhiên ngay sau đó chúng đã tăng kích thước cửa sổ phát và thông lượng cũng tăng ngay sau đó, kích thước hàng đợi có tăng nhưng nhanh chóng giảm và giữ ở mức ổn định. Trong khoản thời gian còn lại không có đột biến lưu lượng thì RED luôn duy trì kích thước hàng đợi trung bình trong 1 khoảng nhỏ trong khoảng từ 6 – 10 gói tin. Nhận xét: Nhìn chung có thể thấy rằng chiến lược DropTail không tránh được hiện tượng Global synchronization không hỗ trợ chia se băng thông công bằng giữa các kết nối nhất là khi có lưu lượng bùng nổ vào mạng thì không giữ được các kết nối đã có sẵn. RED tránh được hiện tượng lockout và Global synchronization. Việc giữ kích thước hàng đợi đủ nhỏ nên đạt được độ trễ hàng đợi nhỏ hơn nhiều lần so với DropTail trong khi vẫn giữ được hệ số sử dụng đường truyền cao. 3.2. Đánh giá bằng mô phỏng việc áp dụng kiến trúc mạng Diffserv có sử dụng RED Việc mô phỏng đảm bảo chất lượng dịch vụ cho các ứng dụng thời gian thực trên Internet dựa trên kiến trúc mạng DiffServ được thực hiện trên bộ mô phỏng NS2. Trong kết nối TCP việc mất mát một số gói tin thường ảnh hưởng nhiều tới hiệu năng của phiên 50 kết nối so với đa số các gói tin còn lại. Những gói tin này thường là những gói tin điều khiển thiết lập kết nối, điều khiển lưu lượng, kiểm soát lỗi. Ta gọi những gói tin này là những gói tin có độ ưu tiên cao. Việc đánh dấu các gói tin này và cung cấp chất lượng dịch vụ cao hơn trong kiến trúc DiffServ sẽ làm hiệu suất của TCP được cải thiện đáng kể. Tuy nhiên việc đánh dấu gói tin yêu cầu các thành phần lớp mạng biết về thông tin lớp vận chuyển. Mục đích của mô phỏng mà chúng tôi giới thiệu để chỉ ra rằng có thể đánh dấu ưu tiên các gói tin quan trọng mà không cần bất kỳ thông tin nào của lớp vận chuyển, vì vậy sẽ đơn giản hóa các việc thực hiện đánh dấu các gói tin TCP. Về phân loại dịch vụ thường có 3 mức ưu tiên được định nghĩa. Mức ưu tiên cao nhất thường được gọi là “in policy” hay Green packets, mức ưu tiên thấp hơn chia thành 2 mức là Yellow Packets và thấp nhất là Red packets hay “Out policy”. Thuật toán RED được sử dụng trong hàng đợi nhằm tránh tắc nghẽn còn trong kiến trúc mạng DiffServ thì thuật toán RED được sử dụng để loại bỏ các gói tin có đánh dấu “Out Policy” 3.2.1. Cấu hình mạng mô phỏng Chúng ta sẽ xem xét một topo mạng đơn giản để mô phỏng mạng DiffServ trong đó ký hiệu các router biên là EDGE1 và EDGE2, còn router lõi là Core, hàng đợi sử dụng giữa router biên và router core là hàng đợi MRED, Các thực thể gửi và nhận là UDP sender và UDP Rec. Nguồn phát là nguồn CBR (nguồn sinh lưu lượng với tốc độ không đổi), băng thông và độ trễ được mô tả đầy đủ trong Hình 3.4 Hàng đợi được sử dụng giữa các Router EDGE và các thực thể gửi, nhận là hàng đợi DropTail. Topo mạng này có một nút cổ chai tại hàng đợi từ router EDGE1 đến router CORE. 51 Hình 3.4: Topo mạng mô phỏng Mỗi node gửi sẽ được kết nối với node nhận tương ứng với lưu lượng được đánh dấu theo các tham số đã chỉ rõ. Có 3 node nguồn, mỗi node sẽ liên tục gửi các gói tin UDP tới các node đích (được ghi nhãn với số thứ tự tương ứng). Tổng tốc độ gửi của 3 node là (600,000bps*3)=1,800,000bps. Mô phỏng trên mạng LAN có tốc độ cao, độ trễ thấp và đường truyền đối xứng. Mô hình lưu lượng: Đảm bảo chất lượng dịch vụ cho node UDP Sender 0  Node UDP Sender 1 sẽ bắt đầu truyền từ 0.1s  Node UDP Sender 0 sẽ bắt đầu truyền từ 5.0s  Nodd UDP Sender 2 sẽ bắt đầu truyền từ 15.0s Hàng đợi MRED được xây dựng tại router EDGE1, do băng thông đường truyền giữa Router EDGE1 với router CORE chỉ có 1Mbps nên nhỏ hơn tổng tốc độ truyền của 3 Node nên ở đây sẽ xảy ra tắc nghẽn. Hàng đợi MRED tại đây sử dụng mode RIO-C và chia thành 3 hàng đợi vật lý, mỗi hàng đợi vật lý lại chia thành 3 hàng đợi ảo, các tham số hàng đợi là giống nhau. Mục đích của việc này không phải để tìm một bộ tham số tối ưu để đạt được hiệu năng cần thiết cho mô phỏng, thay vào đó ta sẽ thử nghiệm dựa trên các điều kiện tham số đầu vào để nghiên cứu ảnh hưởng của Kiến trúc Diffserv đến việc đảm bảo chất lượng dịch vụ cho các ứng dụng có dộ ưu tiên cao. 52 Có 3 mức ưu tiên được định nghĩa dựa trên chính sách Single Rate Three Color Marker (srTCMPolicer): Sử dụng các tham số CIR, CBS, EBS để phân loại và đánh dấu các gói tin thành “Green packets”, “Yellow packets”, “Red packets”. Gói tin được đánh dấu là Green khi chưa vượt qua ngưỡng CBS, được đánh dấu là Yellow khi vượt qua ngưỡng CBS nhưng chưa vượt qua ngưỡng EBS và được đánh dấu là Red khi vượt qua ngưỡng EBS. Mô phỏng dựa trên 3 hàng đợi vật lý, mỗi kết nối từ node nguồn đến node đích được gán trên một hàng đợi vật lý riêng. Chế độ lập lịch cho hàng đợi sử dụng trong mô phỏng là WIRR với các trọng số lần lượt là 6, 3, 1 cho hàng đợi 0, 1, 2. Kết quả mô phỏng đối với trường hợp tắc nghẽn thấp tại do tốc độ truyền của nguồn UDP Sender 0 thấp. Hình 3.5: So sánh thông lượng các kết nối UDP 53 Hình 3.6: So sánh kích thước hàng đợi trung bình Hình 3.7: So sánh độ trễ hàng đợi trung bình 54 Code Point Gói tin nhận Gói tin gửi Drop RED Drop All 9743 5889 689 3165 10 333 333 0 0 11 500 500 0 0 12 2542 2542 0 0 20 167 142 25 0 21 200 98 52 50 22 2258 1078 109 1071 30 174 174 0 0 31 200 200 0 0 32 3369 822 503 2077 Bảng 3.2: Thông kê gói tin Source Packet send Packet loss Lost rate (%) UDP Sender 0 3368 0 0 UDP Sender 1 2587 1289 49.7 UDP Sender 2 3666 2487 67.38 Bảng 3.3: Thống kê Từng kết nối 55 Kết quả mô phỏng 2: Thay đổi tốc độ truyền của UDP Sender 0 từ 600.000bps lên 1.000.000bps Hình 3.8: So sánh thông lược các kết nối UDP Hình 3.9: So sánh kích thước hàng đợi trung bình 56 Hình 3.11: So sánh độ trễ hàng đợi trung bình Thống kê các gói tin CP Gói tin nhận Gói tin gửi Drop RED Drop All 11993 6029 1027 4937 10 333 333 0 0 11 500 368 0 132 12 4792 2994 0 1798 20 167 140 27 0 21 200 99 68 33 22 2258 1072 108 1078 30 174 171 3 0 31 200 200 0 0 32 3369 652 821 1896 Bảng 3.4: Thông kê gói tin trường hợp tắc nghẽn nhiều 57 Source Packet send Packet loss Lost rate (%) UDP Sender 0 5601 1922 34.3 UDP Sender 1 2592 1296 50.0 UDP Sender 2 3627 2640 72.7 Bảng 3.5: Thống kê Từng kết nối Nhận xét về các kết quả mô phỏng được: Việc sử dụng bộ lập lịch WIRR để đảm bảo băng thông tối thiểu cho hàng đợi 0 khiến cho thông lượng kết nối UDP Sender 0 – UDP Rec 0 luôn giữ ở mức trung bình khoảng 600Bps, kết nối có kích thường hàng đợi trung bình và độ trễ hàng đợi rất thấp. Với việc thiết lập tốc độ truyển của UDP Sender 0 là 600.000bps ngang bằng với phần băng thông được chia sẻ của hàng đợi 0 (0.6Mbps) khiến cho kích thước hàng đợi trung bình gần như bằng 0, các packet sau khi tới hàng đợi được xử lý luôn. Sau khi thiết lập tốc độ truyền tăng cường lên 1Mbps thì tại hàng đợi 0 bắt đầu xảy ra tắc nghẽn do băng thông chia sẻ không đáp ứng kịp tốc độ truyền. Khi đó thuật toán RED trên hàng đợi bắt đầu có tác dụng. Việc áp dụng kiến trúc Diffserv để phân loại gói tin thành các mức ưu tiên loại bỏ khác nhau, hàng đợi RED bắt đầu loại bỏ các gói tin có độ ưu tiên thấp để giữ kích thước hàng đợi năm trong ngưỡng đã thiết lập và độ trễ hàng đợi thấp. Không có gói tin Green nào bị loại bỏ. Mô phỏng việc đánh dấu và đảm bảo chất lượng dịch vụ sử dụng kiến trúc DiffServ có thể chưa đem lại sự cải thiện đáng kể trong một vài trường hợp. Có thể thấy rằng việc DiffServ bảo vệ rất tốt các gói tin có ưu tiên cao (Green packets) thường được gọi là các goi tin nhạy cảm. Việc mất mát các gói tin này thường dẫn tới giảm hiệu suất đang kể của phiên kết nối. Trong một số trường hợp mất gói tin đồng bộ sẽ dẫn tới thời gian timeout 3s hoặc 6s đối với các kết nối TCP. Việc cam kết băng thông tối thiểu dành cho một người dùng cụ thể có thể thực hiện được bằng cách gán người dùng đó với một hàng đợi riêng biệt và cấp phát một lượng băng thông như đã cam kết cho hàng đợi đó. Như vậy ta có thể đạt được cả hai mục tiêu đó là vừa đảm bảo được băng thông tối thiểu cho người dùng đặt trước và vừa bảo vệ được luồng dữ liệu nhạy cảm khi tắc nghẽn xảy ra tại chính người dùng đó. 58 3.3. Kết luận và hướng nghiên cứu tiếp theo A. KẾT LUẬN RED là một trong những thuật toán AQM đầu tiên và được nghiên cứu rất nhiều trên thế giới, hầu hết các nghiên cứu đó đều công nhận hiệu quả của nó đạt được. tuy nhiên nó vẫn có những nhược điểm cố hữu là nhạy cảm với các tham số đầu vào và điều kiện của mạng. Ngoài ra RED không đảm bảo được sự công bằng cho các luồng dữ liệu khác nhau. Mục tiêu chính của RED là giữ hàng đợi trung bình đủ nhỏ trong một miền định trước nhằm hấp thu đột biến tức thời giúp mạng đạt được thông lượng cao và độ trễ thấp. Các thuật toán A-RED, RIO, A-RIO ra đời nhằm khắc phục các nhược điểm của RED với việc đơn giản hóa các tham số đầu vào và cố gắng đạt được sự công bằng cho một lớp lưu lượng riêng. Kiến trúc mạng IntServ ra đời nhằm đảm bảo chất lượng dịch vụ cho một lớp lưu lượng đặt trước bằng cách đặt trước tài nguyên từ nguồn tới đích tuy nhiên lại có nhiều nhược điểm như khả năng mở rộng kém trong mạng lõi, chi phí cao, cài đặt phức tạp. Kiến trúc mạng DiffServ được phát triển với những ưu điểm trái ngược với kiến trúc IntServ, với việc phân loại gói tin thành các mức độ ưu tiên khác nhau và áp dụng những chính sách khác nhau cho từng mức ưu tiên đó khiến cho DiffServ đạt được tính linh động rất tốt, dễ cài đặt và mở rộng. Việc áp dụng chiến lược RED trong mô hình kiến trúc mạng DiffServ giúp người quản trị có thể vừa đạt được công bằng cho các luồng dữ liệu, bảo vệ các luồng dữ liệu nhạy cảm vừa đạt được thông lượng và độ trễ cao nhờ thuật toán RIO. B. HƯỚNG NGHIÊN CỨU TIẾP THEO. Chúng tôi sẽ tiếp tục nghiên cứu sâu hơn về kiến trúc mạng DiffServ cụ thể là: Ảnh hưởng của việc thay đổi thuật toán lập lịch giữa các hàng đợi trong kiến trúc mạng DiffServ. Ảnh hưởng của các lưu lượng cũng như các gói tin khác nhau đến hiệu năng của thuật toán RIO. 59 TÀI LIỆU THAM KHẢO 1. Nguyễn Đức Thắng, Nguyễn Ngọc Chân, Trần Công Hùng, Giải pháp đảm bảo chất lượng dịch vụ (QoS) cho mạng lõi. 2. Nguyễn Thị Thu Huyền, Đồ án: Nghiên cứu về QoS và định hướng phát triển mạng viễn thông Việt Nam 3. Vũ Duy Lợi, Nguyễn Đình Việt, Ngô Thị Duyên, Lê Thị Hợi (2004), “Đánh giá hiệu suất chiến lược quản lý hàng đợi RED bằng bộ mô phỏng NS”, Kỷ yếu Hội thảo Khoa học Quốc gia lần thứ hai về Nghiên cứu, Phát triển và Ứng dụng Công nghệ Thông tin và Truyền thông (ICT.rda'04), (Hà nội, 2425/9/2004). NXB Khoa học và Kỹ thuật, Hà Nội, 5/2005, trang 394-403. 4. Lê Đình Danh(2007), Luận văn cao học: Thuật toán quản lý hàng đợi A-RIO 5. Sally Floyd and Van Jacobson, “Random Early Detection Gateways for Congestion Avoidance” Lawrence Berkeley Laboratory University of California 6. Eitan Altman, Tania Jimenez, “NS Simulator for Beginners” 7. RFC: 2474, 2475, 2597, 2598, 3260, 2697 8. Luigi Alcuri, Francesco Saitta , Telephony Over IP: A QoS Measurement-Based End to End Control Algorithm and a Queue Schedulers Comparison 9. D. Stiliadis, A. Varma (1998), “Efficient Fair Queuing Algorithms for PacketSwitched Networks”, IEEE Trans. Networking, Vol. 6, No. 2, pp. 175-185 10. David D.Clark, Wenjia Fang (1998), “Explixit Allocation of Best Effort Packet Delivery Service”, Labratory for Computer Sciences Computer Science Department, Massachusetts Institute of Technology Princeton University A. Demers, S. Keshav and S. Shenkar (1989), “Analysis and Simulation of a Fair Queuing Algorithms” 11. Ns2 Document, 12. Luigi Alcuri, Francesco Saitta, “Telephony Over IP: A QoS Measurement-Based End to End Control Algorithm and a Queue Schedulers Comparison” Viale delle Scienze 9, 90128 Palermo Italy 13. Jia-Shiang Jou, Xiaobo Tan and John S. Baras, “A Parallel Virtual Queue Structure for Active Queue Management” Department of Electrical and Computer 60 Engineering and Institute for Systems Research University of Maryland, College Park, MD 20742 USA 14. Mikko Vanhala, “Differentiated Services – architecture” 44368D Teknillinen korkeakoulu Teletekniikan laboratorio 15. Oyetunji M.O, Oladeji F.A Emuoyinbofarhe O.J, “Performance Evaluation of Traffic Meters: Token Bucket Marker and Two Rate Three Color Marker (trTCM) QoS Admission Control” 16. Rong Pan, “Active Queue Management” Cisco System EE384y Spring Quarter 2006 17. W. Feng, D. Kandlur, D. Saha, and K. G. Shin (1999), “A Self-Configuring RED Gateway”, In Proceedings of IEEE INFOCOM, pages 1320-1328. 18. Andrew s. Tanenbaum, The Netherlands Computer networks fifth edition, Vrije Universiteit Amsterdam, The Netherlands