Báo cáo nghiên cứu khoa học " ẢNH HƯỞNG CỦA CÁC THAM SỐ TRONG QUẢN LÝ HÀNG ĐỢI VÀ TRÁNH TẮC NGHẼN TRÊN INTERNET "

ẢNH HƯỞNG CỦA CÁC THAM SỐ TRONG QUẢN LÝ HÀNG ĐỢI VÀ

TRÁNH TẮC NGHẼN TRÊN INTERNET

Võ Thanh Tú

Trường Đại học Khoa học, Đại học Huế

1. Mở đầu:

Sự bùng nổ thông tin đã dẫn đến lưu lượng tin trên đường truyền Internet

ngày càng lớn, sự quá tải xử lý tại các nút mạng trung tâm càng cao, có nguy cơ

dẫn đến tắc nghẽn. Sự tắc nghẽn có khuynh hướng tác động lại chính nó và trở

nên tồi tệ hơn nếu một bộ định tuyến không còn bộ đệm tự do, nó sẽ bỏ qua

những gói tin mới đến khi mà khả năng xử lý của các nút yếu sẽ dẫn đến tắc

nghẽn ở trạm nhận và buộc trạm gửi tự dừng lại để giải phóng bộ nhớ đệm tự do.

Trong thời gian vừa qua đã có một số kết quả nghiên cứu để hạn chế sự tắc

nghẽn dựa vào việc tổ chức lại hàng đợi phù hợp hơn, như theo cơ chế tổ chức

hàng đợi DropTail, Fair Queue, RED [1],[3],[4]. Đồng thời có nhiều cải tiến về

giao thức TCP Tahoe, TCP Reno, TCP Vegas, để điều khiển luồng tránh tắc

nghẽn [5]. Trong bài báo này chúng tôi phân tích ảnh hưởng của các tham số

trong cơ chế quản lý hàng đợi tích cực để hạn chế tình trạng dẫn đến tắc nghẽn

xãy ra tại nút mạng và ổn định lưu thông trong khoảng thời gian ngắn bùng nổ

thông tin trên hệ thống mạng.

27

2. Cơ chế điều khiển luồng để tránh tắc nghẽn

Điều khiển luồng được xét đến ở đây là quá trình điều khiển gói báo nhận

hoặc điều chỉnh kích thước cửa sổ trượt. Việc sử dụng cửa sổ trượt có kích thước

thay đổi là hỗ trợ việc điều khiển tốc độ truyền dữ liệu cũng như là việc truyền

đáng tin cậy. Để tránh việc nhận nhiều gói tin hơn khả năng lưu trữ, nơi nhận sẽ

gửi đi thông báo cửa sổ nhỏ hơn và ngược lại. Trường hợp xấu nhất, nơi nhận sẽ

gửi đi thông báo cửa sổ có kích thước là zero để ngưng tất cả việc truyền. Nhưng

việc nhiều lần ngưng truyền với những đợt ngắn do tràn hàng đợi tạm thời là

không cần thiết, điều này làm tăng sự dao động thông lượng. Vì vậy cần có cơ

chế điều khiển hợp lý giữa luồng gói tin đến và cơ chế xử lý tại nút nhận thích

hợp.

Thông thường các điểm đầu cuối thường không nhận biết sự tắc nghẽn và

tại sao chúng xảy ra. Bởi vì tắc nghẽn là do sự trì hoãn gia tăng, nên hầu hết các

phần mềm giao thức sử dụng bộ đếm thời gian và truyền lại. Việc truyền lại có

ảnh hưởng lớn đến hệ thống vì nó sẽ làm tăng thêm sự nghẽn mạch, và đến một

lúc nào đó mạng sẽ trở nên vô dụng. Vấn đề này được gọi là sự sụp đổ do

nghẽn mạch. Giải quyết toàn diện vấn đề này là vô cùng phức tạp, liên quan

nhiều tầng giao thức khác nhau và nhiều dịch vụ khác nhau. Thông thường việc

điều khiển sự tắc nghẽn được thực hiện qua 3 bước như sau:

Bước 1: Làm chủ hệ thống để phát hiện khi nào và xảy ra ở đâu. Khi xác

định được tắc nghẽn ở đâu, lúc đó bước thứ 2 sẽ được thực hiện.

Bước 2: Chuyển thông tin đến những nút mạng (router) khác mà ở đó có

thể tiến hành giải quyết được công việc đồng thời thông báo tắc nghẽn (ECN:

Explicit Congestion Notification)[3] cho các router khác. Tất nhiên, các gói tin

28

phụ sẽ làm tăng tải vào thời điểm nhiều tải không cần thiết.

Một phương pháp khác là máy chủ hay router gửi các gói tin thăm dò để

biết rõ ràng về sự tắc nghẽn. Thông tin có thể được sử dụng chỉ lưu thông quanh

khu vực có sự cố.

Bước 3: Khi nhận được thông tin về sự tắc nghẽn, máy chủ có những hành

động thích hợp để giảm sự tắc nghẽn như: Sắp xếp lại tuyến đường truyền tin,

hạn chế không cho truyền gói tin vào những đường xảy ra tắc nghẽn… Các

phương pháp có thể hoạt động ở trạm nguồn hoặc ở trạm đích.

Hoạt động ở trạm nguồn: Bao gồm gói tin được gửi đi, trở lại từ điểm tắc

nghẽn báo cho nguồn hoặc nguồn suy đoán về sự tồn tại của tắc nghẽn bằng việc

quan sát thời gian cần thiết cho sự báo nhận đi trở lại.

Hoạt động ở trạm đích: Sự hiện diện của tắc nghẽn có nghĩa tải (tạm thời)

là lớn hơn lượng tin (một phần hệ thống) có thể quản lý. Hai giải pháp có thể

thực hiện để giải quyết là tăng tài nguyên (lượng thông tin có thể lưu trữ) hoặc

giảm tải.

Tuy nhiên, đôi khi không thể tăng khả năng tài nguyên lên được hoặc nếu

tăng thì chỉ tăng đến một giới hạn nhất định. Cách duy nhất để tác động sự tắc

nghẽn là giảm tải. Để giảm tải có thể phủ nhận dịch vụ với nơi sử dụng, giảm bớt

dịch vụ từ các trạm gửi đến hoặc cải tiến giao thức điều khiển phù hợp, cải tiến

cơ chế xử lý gói tin tại hàng đợi của các nút mạng trung tâm theo một trực tự ưu

tiên phù hợp.

29

3. Ảnh hưởng của tham số điều khiển trong cơ chế quản lý hàng đợi

3.1. Phương pháp luận

Khi các gói tin gửi đến nhanh hơn là chúng được chuyển đi thì hàng đợi sẽ

dài ra hay các gói tin chuyển đến chậm hơn thì hàng đợi thu ngắn lại. Nhưng vì

bộ nhớ là hữu hạn, hàng đợi không thể dài ra quá hạn. Vì vậy để quản lý hàng

đợi bị tràn phần mềm của bộ định tuyến sử dụng chiến lược cắt bớt phần

đuôi (DropTail). Chiến lược này có ảnh hưởng đáng kể với TCP, làm cho TCP

đi vào trạng thái khởi động chậm, nghĩa là giảm bớt tốc độ truyền cho tới khi

TCP bắt đầu nhận các báo nhận và gia tăng kích thước cửa sổ nghẽn mạch.

Ngoài ra việc hủy các gói tin đến sau khi hàng đợi bị đầy có thể ảnh hưởng đến

toàn bộ Internet, điều này đòi hỏi phải có một mô hình khác để thay thế đó là

mô hình hủy bỏ sớm ngẫu nhiên (Random Early Discar) [5], thường được gọi

tắt là RED. Cơ chế này dựa vào việc tính toán xác suất gói tin rơi trong giới hạn

ngưỡng kích thước hàng đợi maxth, minth và tính toán kích thước hàng đợi trung

bình kˆ tại nút mạng. Giá trị của kˆ được cập nhật mỗi khi có datagram gửi đến,

theo công thức sau:

(1)

kˆ

:= (1 - ) * kˆ +  * k

Với  là hệ số 0    1, k: kích thước hàng đợi tức thì.

Cơ chế quản lý bộ đệm RED dựa vào gói tin bị đánh rơi với một xác suất

tăng dần theo hàm p( kˆ ) của kích thước hàng đợi trung bình kˆ , có kích thước bộ

đệm của K gói tin. Việc tính hàm xác suất p là một trong những giai đoạn phức

30

tạp của RED.

Gọi p( kˆ ) là hàm xác suất gói tin rơi ta có:

ˆ( k



max

- (1 (





max

p

th

th

+ kˆ* ) max

= (2) p ( kˆ ) =

)min th  min

max

)min -k *  thmin

th

th

th

Hiệu số (maxth - minth) càng cao thì xác suất rơi gói tin thấp, khi hàng đợi

d(k)

1

maxp

k

minth

maxth K

rỗng thì xác suất hủy gói tin ngẫu nhiên p( kˆ ) = 0.

Hình 1: Xác suất rơi gói tin trên mô hình hàng đợi RED

p( kˆ ) = 0 nếu kˆ < minth, p( kˆ ) = 1 nếu kˆ > maxth,

Mặc dù mô hình tuyến tính hình thành nên cơ sở của phép tính xác suất cho

RED, cần phải có những hiệu chỉnh trọng số  để tránh tình trạng phản ứng “quá

vội”. Sở dĩ cần có những thay đổi là bởi vì giao thông trên mạng là theo từng

“đợt”, và gây ra những dao động quá nhanh của hàng đợi trong bộ định tuyến.

Nếu RED sử dụng một mô hình tuyến tính đơn giản, những gói tin đến sau trong

mỗi đợt sẽ bị gán xác suất cao cho khả năng bị loại bỏ (bởi vì chúng đến khi hàng

đợi đã có nhiều gói tin). Nếu gặp một đợt (các gói tin) ngắn, ít có khả năng bị

loại bớt gói tin bởi vì hàng đợi chưa bị đầy thì bộ định tuyến không nên hủy bỏ 31

những gói tin này một cách không cần thiết, bởi vì làm như thế sẽ tác động xấu

đến hiệu suất của TCP. Dĩ nhiên, RED không thể tạm hoãn việc hủy bỏ vô thời

hạn bởi vì một đợt dài sẽ làm đầy hàng đợi, kết quả chẳng khác nào chiến lược

“cắt bớt phần đuôi”, và sẽ gây ra ảnh hưởng đến toàn bộ Internet.

3.2. Đánh giá qua mô phỏng hệ thống quản lý hàng đợi

Cơ chế điều khiển tắc nghẽn là một trong những vấn đề nghiên cứu chính

của đánh giá hiệu năng mạng TCP/IP. Nhưng việc cài đặt thử nghiệm trên mạng

đang hoạt động thực tế là khó thực hiện. Ở đây chúng tôi sử dụng phương pháp

mô phỏng để đánh giá khả năng hoạt động của cơ chế quản lý RED trên mô hình

đề xuất có nhiều nguồn đến tại nút mạng trung tâm với băng thông đường truyền

không đối xứng.

3.2.1. So sánh cơ chế DropTail và RED

Sử dụng NS-2 là công cụ mô phỏng mạng cài đặt trên hệ điều hành Linux

Router

Nơi gửi

Nơi nhận

Router

2Mb/s, 20ms

10Mb/s, 2ms

FTP

10Mb/s, 2ms

S1

10M/2

Rec

R1

R2

2Mb/s, 20ms

10Mb/2

S5

FTP

S6

Exp

[2]. Giả thiết mô hình thiết kế mạng mô phỏng được xây dựng như sau:

32

Hình 2: Mô hình hệ thống mô phỏng

Hệ thống có 5 nguồn gởi tin S1 đến S5 theo dịch vụ FTP cài đặt TCP và 1

nguồn gửi tin S6 theo dịch vụ có cấu hình thay đổi tỷ suất truyền thích nghi

(on/off) trên giao thức không yêu cầu báo nhận UDP. Bên nhận (Rec) được cài

đặt giao thức giao vận TCP. Cơ chế điều khiển hàng đợi được tổ chức tại hàng

đợi ra của Router (R1). Mô phỏng ứng dụng trong mạng có băng thông không

đồng bộ giữa các cung truyền, đoạn từ R1(Router) đến R2 (Router) có băng

thông 2Mb/s, độ trễ đường truyền là 20ms (tương ứng với tốc độ mạng WAN),

băng thông các cung còn lại là 10Mb/s và độ trễ là 2ms (tương ứng với tốc độ

của mạng LAN hiện tại).

Giới hạn hàng đợi tại các nút là 20 gói. Thứ tự mô phỏng tổ chức hàng đợi

tràn ở các bộ định tuyến trung tâm. Đồng hồ TCP là 100ms. Quy luật dùng hàng

đợi Drop Tail cho Router R2 và các trạm từ đầu cuối đến đầu cuối. Sử dụng hàng

đợi RED tại đầu ra R1 (ngưỡng tối thiểu minth= 5, ngưỡng tối đa maxth= 15, =

0.002).

Qua quá trình theo dõi mô phỏng NS của mô hình trên, chúng tôi đã ghi lại

toàn bộ hoạt động trong thời gian mô phỏng 20s, thời gian bắt đầu gửi của S1 đến

S5 lần lượt cách nhau 0,1ms, kết quả ghi lại được phân tích bằng chương trình

TRGRAPH dựa trên thư viện toán học Matlab để tính toán với kết quả như sau.

Bảng 1: Bảng kết quả phân tích trên các mô hình

Mô hình DropTail RED(5/15) RED(10/18 RED(2/18)

33

)

Số gói tin gửi 18071 18638 19999 19999

Số gói tin rớt 145 78 77 81

Số gói tin mất 209 132 145 122

Độ trễ TB(ms) 0.0566 0.0569 0.0600 0.0567

34

Hình 3: Biểu đồ mô tả thông lượng của hệ thống cài đặt DropTail

Hình 4: Biểu đồ mô tả thông lượng của hệ thống có cài đặt RED

Qua kết quả thể hiện trên các hình 3, hình 4 với trục tung là thông lượng của

hệ thống và trục hoành là thời gian mô phỏng, chúng ta thấy thông lượng ở mô

hình có cài đặt RED ở R1 tăng lên rõ rệt ở thời điểm t=7s, t=10s và độ dao động

của biểu đồ thông lượng ổn định ở các thời điểm có lượng gói tin đến vượt khả

năng tiếp nhận của hàng đợi. Trên bảng 1 chúng ta thấy số gói tin rớt và mất

giảm mạnh của RED (minth=5, maxth=15) so với cơ chế quản lý hàng đợi

DropTail, cụ thể số gói tin rớt giảm 53,8% và số gói tin mất giảm 63,15%. Kết

quả là thông lượng hệ thống sử dụng cơ chế RED ở những thời điểm ban đầu

giảm nhưng sau đó tăng dần và ổn định hơn so với mô hình sử dụng hàng đợi

DropTail. Đồng thời việc thay đổi giới hạn ngưỡng minth, maxth của cơ chế RED

thì tỷ lệ gói tin rơi và mất thay đổi rất nhỏ.

3.3.2. Ảnh hưởng của tham số hàng đợi đến sự rơi các gói tin tại nút

mạng

Dựa trên mô hình đang xét, chúng tôi tiến hành khảo sát sự thay đổi tham số

 của cơ chế RED trong thời gian mô phỏng 5s. Kết quả thu được trên bảng 2

35

cho thấy tham số hàng đợi  có ảnh hưởng rất lớn đến kết quả rơi các gói tin tại

nút mạng.

(RED)

0.00 0.001 0.001 0.00 0.000 0.000 0.000 0.005 0.004 0.002 0.0001 3 7 5 1 9 5 2

Số gói tin 34 35 29 22 18 18 14 16 14 10 7 rơi

Số gói tin

được 3567 3623 3718 3541 3628 3714 3806 3856 3904 3975 4053

huyển

Bảng 2: Kết quả đo được sau khi mô phỏng

Dựa vào bảng 2 ta xác định hàm tương quan giữa các tham số  với số gói

tin bị rơi và số gói tin đến R1. Trên cơ sở lý thuyết xác suất thống kê, chúng tôi

tính được hệ số tương quan giữa tham số hàng đợi RED với số gói tin rơi là

tương quan mạnh.

Vì vậy việc cài đặt cơ chế quản lý hàng đợi RED có cơ chế điều khiển tự

động tham số hàng đợi thích hợp với sự chuyển biến của các đợt bùng nổ

thông tin trong thời gian dài tại những thời điểm lưu lượng gói tin đến nút

mạng tăng nhanh là rất có ý nghĩa, đã làm ổn định lưu thông trên mạng khi có

nhiều nguồn đến nút mạng đồng thời, đảm bảo thông lượng chung toàn hệ thống

và hạn chế được gói tin rơi đáng kể.

36

4. Kết luận:

Qua bài báo này chúng tôi đã nghiên cứu đựơc các phương pháp điều khiển

lưu thông mạng một cách tích cực, xây dựng được mô hình mạng mô phỏng quá

trình truyền dữ liệu kết hợp với cơ chế tránh tắc nghẽn. Với phương pháp quản lý

hàng đợi RED, qua mô phỏng đã chứng minh được tính ưu việt hơn so với

DropTail trong mô hình đã xét, đồng thời xác lập được mối tương quan giữa

tham số hàng đợi với số gói tin rơi, có tác động mạnh đến quá trình điều khiển

lưu thông trên mạng Internet.

TÀI LIỆU THAM KHẢO

1. B. Suter et al., Efficient Active Queue Management for Internet Routers,

Proc. Eng. Conf. at Interop 98, Las Vegas, NV (1998).

2. Http:// www. isi.edu/nsnam/ns/ns-documentation.html

3. M. Borden, V. Firoiu, Queue Management for Congestion Control, IEEE

INFOCOM, (2000).

4. S. Floyd and V. Jacobson, Random Early Detection Gateways for Conges-

tion Avoidance, IEEE/ACM Trans. Net., vol. 1, no. 4 (1993) 397 - 413.

5. Sally Floyd, A Report on Some Recent Developments in TCP Congestion

37

Control, IEEE Magazine (2001).

TÓM TẮT

Trong bài báo này chúng tôi tập trung phân tích ảnh hưởng của các tham

số trong cơ chế quản lý hàng đợi tích cực trên mô hình mạng Internet.

THE EFFECT OF PARAMETERS ON QUEUE MANAGEMENT

AND CONGESTION AVOIDANCE ON INTERNET

Vo Thanh Tu

College of Sciences, Hue University

SUMMARY

In this paper, we focus our study on analyzing the effects of parameters on

38

active queue management schemes and congestion avoidance on Internet.