Tóm tắt 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

ĐẠI HỌC QUỐC GIA HÀ NỘI TRƯỜNG ĐẠI HỌC CÔNG NGHỆ HOÀNG TRỌNG THỦY ĐẢ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 LUẬN VĂN THẠC SĨ NGÀNH CÔNG NGHỆ THÔNG TIN GVHD: PGS TS Nguyễn Đình Việt Hà Nội - 2016 LỜI CAM ĐOAN Tôi xin cam đoan rằng đây là công trình nghiên cứu của cá nhân tôi dưới sự hướng dẫn giúp đỡ của PGS TS. Nguyễn Đình Việt. Các kết quả được viết chung với các tác giả khác đều được sự đồng ý của tác giả trước khi đưa vào luận văn. Trong toàn bộ nội dung nghiên cứu của luận văn, các vấn đề được trình bày đều là những tìm hiểu và nghiên cứu của chính cá nhân tôi hoặc là được trích dẫn từ các nguồn tài liệu có ghi tham khảo rõ ràng, hợp pháp. Trong luận văn, tôi có tham khảo đến một số tài liệu của một số tác giả được liệt kê tại mục tài liệu tham khảo. Hà nội, tháng 11 năm 2016 Tác giả luận văn Hoàng Trọng Thủy LỜI CẢM ƠN Để hoàn thành tốt luận văn này, đầu tiên tôi xin bày tỏ lòng biết ơn chân thành và sâu sắc đến Thầy Nguyễn Đình Việt, người đã tận tình và trực tiếp hướng dẫn tôi trong suốt quá trình triển khai và nghiên cứu đề tài, tạo điều kiện để tôi hoàn thành luận văn này. Thứ hai, tôi xin bày tỏ lòng biết ơn chân thành tới toàn thể các thầy cô giáo trong khoa Công nghệ thông tin, trường Đại học Công nghệ, Đại học Quốc gia Hà Nội đã dạy bảo tận tình tôi trong suốt quá trình tôi học tập tại khoa. Cuối cùng tôi xin chân thành cảm ơn tới gia đình, bạn bè, đồng nghiệp đã luôn bên em cổ vũ, động viên, giúp đỡ tôi trong suốt quá trình học tập và thực hiện luận văn. Mặc dù đã cố gắng hoàn thành luận văn trong phạm vi và khả năng cho phép nhưng chắc chắn sẽ không tránh khỏi những thiếu sót. tôi rất mong được sự góp ý chân thành của thầy cô và các bạn để tôi hoàn thiện luận văn của mình. Tôi xin chân thành cảm ơn! Hà Nội, tháng 11 năm 2016 Học viên Hoàng Trọng Thủy 1 MỞ ĐẦU 1. ĐẶT VẤN ĐỀ Sự phát triển mạnh mẽ của mạng Internet ngày này kéo theo sự sự phát triển của các ứng dụng trên Internet. Dữ liệu trao đổi trên mạng không chỉ đơn thuần là văn bản (text) nữa mà thêm vào đó là dữ liệu đa phương tiện (multimedia) bao gồm có hình ảnh (image), âm thanh (audio), phim, nhạc Các ứng dụng đa phương tiện phổ biến có thể kể đến như gọi điện qua mạng (Internet telephony), hội thảo trực tuyến (video conferencing) hoặc các ứng dụng xem video theo yêu cầu (video on demand) càng ngày càng được sử dụng rộng rãi. Vấn đề đảm bảo chất lượng dịch vụ (QoS) đang trở nên quan trọng hơn bao giờ hết. 2. MỤC ĐÍCH CỦA LUẬN VĂN Do sự bùng nổ mạng mẽ của mạng Internet như hiện nay khiến cho dữ liệu vận chuyển quan mạng Internet trở nên khổng lồ, nhu cầu quá lớn khiến cho việc tắc nghẽn xảy ra thường xuyên và vấn đề đặt ra là làm sao hạn chế tối đa tắc nghẽn trên mạng Internet và duy trì sự ổn định cao nhất cho mạng. Các kỹ thuật truyền thống nhằm giảm thiểu tắc nghẽn trên mạng ngày càng kém hiệu quả. Mục đích của luận văn là nghiên cứu một giải pháp quản lý và điều khiển nhằm hạn chế tối đa tắc nghẽ trên mạng Internet. Thay vì sử dụng hàng đợi FIFO truyền thống (Trong bộ mô phỏng NS2 được gọi với cái tên DropTail) luận văn này sẽ nghiên cứu sâu các chiến lược quản lý hàng đợi động mà tiêu biểu là RED (Random Early Detection of Congestion; Random Early Drop), Adaptive-RED, A-RIO (Adaptive – RED with In and Out). 3. BỐ CỤC CỦA LUẬN VĂN a) Chương 1: Giới thiệu b) Chương 2: Các chiến lược quản lý hàng đợi và khả năng áp dụng để đảm bảo QoS cho truyền thông đa phương tiện thời gian thực c) 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 2 Chương 1. GIỚI THIỆU 1.1. Tổng quan về bộ giao thức TCP/IP và sự phát triển của mạng Internet Giới thiệu chung Năm 1967 từ một thí nghiệm mạng do Robert L.G đề xuất. ARPA trực thuộc bộ quốc phòng Mỹ đã kết nối 4 địa điểm đầu tiên vào tháng 7 năm 1967 gồm: Viện nghiên cứu Standford, Đại học California tại Los Angeles, Đại học tổng hợp Utah và Đại học California tại Santa Barbara. Đó là mạng WAN đầu tiên được xây dựng được gọi là ARPANET sau này là mạng Internet [17] Bộ giao thức TCP/IP chính thức ra đời năm 1983 và được coi là chuẩn đối với ngành quân sự Mỹ và tất cả các máy tính nối với mạng ARPANET phải sử dụng theo chuẩn mới này. Sự phát triển như vũ bão khiến cho mọi trường đại học đều muốn gia nhập vào mạng này và việc quản lý mạng trở nên khó khăn. Chính vì lẽ đó mạng ARPANET được tách ra thành 2 phần là MILNET và ARPANET mới vào năm 1983, tuy tách rời nhưng hai mạng này vẫn liên kết với nhau nhờ giao thức liên mạng IP. Sự ra đời của TCP/IP đánh dấu mốc lịch sử quan trọng và càng ngày càng hiện rõ điểm mạnh của nó nhất là khả năng liên kết các mạng khác với nhau một cách dễ dàng. Vào thập kỷ 80 khi hội đồng Khoa học quốc gia Mỹ NSF (Nation Science Foundation) thành lập mạng liên kết các trung tâm máy tính lới với nhau gọi là NSFNET. Các doanh nghiệp đã chuyển từ ARPANET sang NSFNET. Sau gần 20 năm hoạt động ARPANET đã dừng hoạt động vào khoảng năm 1990. Sự phát triển của backbone NSFNET và những mạng khác đã tạo ra mội trường thuận lợi cho sự phát triển của Internet. Năm 1995 NSFNET thu lại thành một mạng nghiên cứu và Internet thì tiếp tục phát triển. Cùng với khả năng kết nối mở Internet đã trở thành một mạng lớn nhất thế giới, mạng của các mạng xuất hiện trong mọi linh vực thương mại, chính trị, quân sự, xã hội Ngày nay khi cơ sở hạ tầng của mạng Internet được nâng cao đã làm cho nhu cầu của các ứng dụng đa phương tiện qua mạng tăng lên nhanh chóng. 3 1.2. Tổng quan về truyền thông đa phương tiện (Multimedia) và chất lượng dịch vụ (QoS) 1.2.1. Giới thiệu chung về truyền thông đa phương tiện (Multimedia) Trước đây, khi mà Internet chủ yếu là truyền data thì người ta không cần quan tâm đến việc phân biệt và ưu tiên cho các gói tin bởi vì lúc này băng thông mạng và các tài nguyên khác đủ để cung cấp cho các ứng dụng trong mạng, vì vậy các ISPs sẽ cung cấp cho khách hàng của họ dịch vụ theo kiểu “Cố gắng tối đa” (Best-Effort - BE) khi đó tất cả các khách hàng sẽ được đối xử như nhau họ chỉ khác nhau ở loại kết nối. Đây là dịch vụ phố biến trên mạng Internet hay mạng IP nói chung. Các gói thông tin được truyền đi theo nguyên tắc “đến trước được phục vụ trước” mà không quan tâm đến đặc tính lưu lượng của dịch vụ là gì. Điều này dẫn đến rất khó hỗ trợ các dịch vụ đòi hỏi độ trễ thấp như các dịch vụ thời gian thực hay video. Cho đến thời điểm này, đa phần các dịch vụ được cung cấp bởi mạng Internet vẫn sử dụng nguyên tắc Best Effort này. Dữ liệu động ở đây thường là Audio hoặc Video và các ứng dụng truyền thông loại dữ liệu trên được gọi chung là ứng dụng đa phương tiện. Loại dữ liệu này rất nhạy cảm với độ trễ nhưng lại cho phép sự mất mát gói tin trong một ngưỡng chấp nhận được. Tính chất hoàn toàn trái ngược với các ứng dụng truyền thống nên nó đòi hỏi chất lượng dịch vụ khác hoàn toàn với các ứng dụng truyền thống. Tùy theo từng yêu cầu về chất lượng dịch vụ có thể chia ứng dụng đa phương tiện thành 3 lớp cơ bản sau:  Truyền audio và video đã được lưu trữ  Truyển audio và video thời gian thực  Ứng dụng tương tác audio và video thời gian thực 4 1.2.2. Giới thiệu chung về chất lượng dịch vụ (QoS) Quality of Service – QoS: chỉ khả năng cung cấp các dịch vụ mạng cho một lưu lượng nào đó. Mục đích chính là điều khiển băng thông, độ trễ và jitter. Giảm độ trễ, giảm tỉ lệ mất mát gói tin cho các ứng dụng thời gian thực và tương tác trong khi vẫn đảm bảo phục vụ tốt cho các luồng dữ liệu khác. Theo khuyến nghị của CCITT, E800 đưa ra một tính chất chung qua QoS: “Hiệu ứng chung của đặc tính chất lượng dịch vụ là xác định mức độ hài lòng của người sử dụng đối với chất lượng dịch vụ” Khuyến nghị ETR300003 của ETSI chia và cải tiến định nghĩa của ITU thành các định nghĩa nhỏ hơn, nó phù hợp với các yêu cầu và quan điểm của các nhóm khác nhau trong viễn thông đó là:  Yêu cầu QoS của người sử dụng.  Đề nghị QoS của nhà cung cấp dịch vụ.  Sử cảm nhận QoS từ khách hàng.  Việc thực hiện QoS của nhà cung cấp dịch vụ.  Yêu cầu QoS của nhà cung cấp dịch vụ. Các tham số QoS chính liên quan đến mạng bao gồm: a) Độ trễ (Delay) b) Thông lượng (Throughput): là khả năng truyền tin được tính bằng tổn số đơn vị dữ liệu truyền được trong 1 đơn vị thời gian ví dụ: packet/s c) Jitter: d) Tỉ lệ mất gói tin (Packet loss ratio) e) Độ khả dụng (Đáng tin cậy) f) Bảo mật g) Ngoài ra còn một số tham số như “Kích thước mất tin” hoặc “độ tin cậy” Mức QoS:  Best-Effort: Đây là mức thấp nhất, dịch vụ kết nối không đảm bảo đặc trưng bởi hàng đợi FIFO, không có sự phân loại giữa các luồng dữ liệu 5  QoS Cứng: là sự đặt trước tài nguyên phục vụ cho một luồng dữ liệu xác định trước thường được cung cấp bởi giao thức RSVP và CBR có trong kiến trúc IntServ  QoS Mềm: trong kiến trúc mạng phân loại (Differentiated service) dựa trên sự phân loại các luồng dữ liệu theo nhiều mức ưu tiên thì một luồng dữ liệu nào đó sẽ được ưu tiên phục vụ tốt hơn các luồn còn lại. Việc lựa chọn loại dịch vụ nào để triển khai trong mạng phụ thuộc vào các yếu tố sau:  Ứng dụng hoặc tính chất của bài toán cần giải quyết  Chi phí cho cài đặt và triển khai dịch vụ 1.3. Các mô hình đảm bảo chất lượng dịch vụ 1.3.1. Mô hình các dịch vụ được tích hợp IntServ 1.3.2. Mô hình các dịch vụ phân biệt DiffServ 6 Chương 2. CÁC CHIẾN LƯỢC QUẢN LÝ HÀNG ĐỢI VÀ KHẢ NĂNG ÁP DỤNG ĐỂ ĐẢM BẢO QOS CHO TRUYỀN THÔNG ĐA PHƯƠNG TIỆN THỜI GIAN THỰC Trong mạng chuyển mạch ip thì các gói tin thuộc các luồng dữ liệu khác nhau được truyền trên cùng đường truyền để đến trạm đích. Để việc phân phối băng thông đường truyền đạt hiệu quả cao nhất thì cần một cơ chế phục vụ công bằng tại các nút mạng hoặc Router. Router ở đây sẽ phục vụ các gói tin của luồng đã chọn và quyết định gói tin nào sẽ được phục vụ tiếp theo. 2.1. Các chiến lược quản lý hàng đợi truyền thống 2.1.1. Hàng đợi FIFO (First in first out) FIFO là hàng đợi mặc định được sử dụng trong hầu hết các router. FIFO không có sự phân loại vì tất cả các gói đều thuộc về cùng một lớp. Các gói đến từ các luồng khác nhau được đối xử công bằng bằng cách đưa vào hàng đợi theo trật tự đến (gói nào đến trước sẽ được đưa vào trước và được phục vụ trước) theo đúng nghĩa First-Come-First- Serve (FCFS) hay First-In-First-Out (FIFO) Hình 2.1: Cơ chế phục vụ FIFO 2.1.2. Chiến lược hàng đợi ưu tiên PQ ( Priority Queue ) Kĩ thuật này được sử dụng trong trường hợp đa hàng đợi, mỗi hàng đợi có một mức ưu tiên khác nhau, hàng đợi nào có mức ưu tiên cao nhất sẽ được ưu tiên phục vụ trước. Khi có tắc nghẽn xảy ra thì các gói trong các hàng đợi có độ ưu tiên thấp sẽ bị góisGói tin đến Hàng đợi Gói tin đi Link 7 loại bỏ. Nói cách khác, lưu lượng quan trọng sẽ được gán các mức ưu tiên cao và lưu lượng có mức ưu tiên cao nhất được truyền trước, còn lại các lưu lượng ít quan trọng hơn. Hình 2.2: Cơ chế phục vụ hàng đợi ưu tiên PQ 2.1.3. Chiến lược Packet-Based Round Robin Tương tự như chiến lược PQ đã trình bày ở phần trước. Chiến lược này cũng dựa vào việc phân loại các gói tin đến theo từng luồng khác nhau mỗi luồng được xếp vào một hàng đợi và được phục vụ lần lượt theo vòng. Tuy nhiên thay vì phục vụ theo mức ưu tiền thì PBRR lại phục vụ lần lượt quay vòng từng hàng đợi, mỗi hàng đợi chỉ phục vụ 1 gói tin. Nếu hàng đợi nào rỗng thì bộ lập lịch sẽ bỏ qua không phục vụ. góisGói tin đến Hàng đợi 1 Gói tin đi Link Hàng đợi 2 Phân loại 8 Hình 2.3: Cơ chế phục vụ hàng đợi PBRR (Packet-Based Round Robin) Bộ lập lịch PBRR sẽ đối xử với các luồng dữ liệu giống nhau, nghĩa là không có mức độ ưu tiên dành cho các luồng có mức ưu tiên cao và nó cũng không quan tâm đến độ dài hàng đợi hiện tại khiến cho những luồng có hàng đợi dài chứa nhiều gói tin cũng chỉ được cấp cho một lượng băng thông giống như các luồng khác. Làm giảm hiệu suất sử dụng đường truyền. Không đáp ứng được băng thông cho các luồng dữ liệu multimedia. 2.1.4. Chiến lược Flow-Based Weighted Fair Queuing (WFQ) Các chiến lược đã nói trong phần trước đều dựa trên packet-base nghĩa là nó áp dụng cho từng gói tin theo đó mỗi lần phục vụ server sẽ chọn 1 gói tin theo mức độ ưu tiên của nó. Ưu điểm của chiến lược này nó đạt được mức độ công bằng cao cho các gói tin nhưng lại chứa nhiều điểm hạn chế: Thứ nhất là chi phí gán nhãn cho từng gói tin là lớn và làm gia tăng độ phức tạp thuật toán và tiêu tốn tài nguyên của server. Thứ 2 là các gói tin của cùng 1 luồng sẽ không được phụ vụ cùng 1 lúc mà bị gián đoạn bởi các gói tin của các luồng khác, điều này không phù hợp với các ứng dụng truyền thông đa phương tiện thời gian thực trên Internet cần độ liền mạch các gói tin. Chính vì lẽ đó ta cần 1 cách tiếp cận hay 1 chiến lược khác là việc xác định và gán độ ưu tiên cho một luồng dữ liệu thay vì 1 gói tin riêng lẻ. Các gói tin trong cùng 1 luồng dữ liệu sẽ có cùng góisGói tin đến Hàng đợi 1 Gói tin đi Link Hàng đợi 3 Phân loại Hàng đợi 2 9 1 độ ưu tiên và được phục vụ liên tục. Server sẽ phục vụ các luồng theo tứ tự ưu tiên hoặc trọng số, các gói tin trong cùng 1 luống sẽ được phục vụ theo cơ chế FIFO nghĩa là gói tin nào đến trước được phục vụ trước. Chiến lược này được gọi là Flow-Base Weighted Fair Queuing. 2.1.5. Chiến lược Class-Based Weighted Fair Queuing (CBQ) Không giống như WFQ, CBQ được thiết kế nhằm đảm bảo băng thông cho các lớp lưu lượng do người dùng đặt trước mà vẫn đảm bảo phân phối công bằng cho các luồng trong lớp đó. CBQ cung cấp nhiều hàng đợi riêng biệt, mỗi hàng đợi có thể phân chia thành nhiều lớp, các luồng này có thể được xác định dựa vào các tiêu chi như giao thức (FTP, HTTP, Telnet, SSh..) hoặc danh sách điều khiển truy cập (Access list). Các gói tin thỏa mãn các tiêu chí được xếp chung vào 1 lớp 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 10 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 a. Hiện tượng Global Synchronization b. Hiện tượng hàng đợi đầy (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 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. 11 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. 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. b. 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ó 12 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. 2.2.4. Thuật toán RIO 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. 13 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. 2.2.5. 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. 14 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. 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ả: 15 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 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ổ 16 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 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. 17 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 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. Hình 3.4: Topo mạng mô phỏng 18 Hình 3.5: So sánh thông lượng các kết nối UDP Hình 3.6: So sánh kích thước hàng đợi trung bình 19 Hình 3.7: So sánh độ trễ hàng đợi trung bình 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 20 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 21 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 22 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 23 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 đó. 24 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. 25 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 26 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