ĐẠ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)
góisGói tin đến Gói tin đi
Hàng đợi Link
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ị
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àng đợi 1
góisGói tin đến Gói tin đi
Phân loại Link
Hàng đợi 2
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ụ.
8
Hàng đợi 1
Gói tin đi góisGói tin đến
Hàng đợi 2
Phân loại
Link
Hàng đợi 3
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
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 Kích thước hàng Độ trễ hàng đợi Hệ số sử dụng
(packet) đợi trung bình trung bình (ms) đường truyền
(packet) (%)
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 142 167 0 25
21 98 200 50 52
22 2258 1078 1071 109
30 174 174 0 0
31 200 200 0 0
32 822 3369 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
Gói tin nhận Gói tin gửi Drop RED Drop CP
11993 6029 1027 4937 All
333 333 0 0 10
500 368 0 132 11
4792 2994 0 1798 12
167 140 27 0 20
200 99 68 33 21
2258 1072 108 1078 22
174 171 3 0 30
200 200 0 0 31
3369 652 821 1896 32
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, http://www.isi.edu/nsnam/ns/doc/
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
