Chương 4: Chương trình mô phỏng điều khiển tắc nghẽn dùng thuật toán tăng giảm
Chương 4
CHƯƠNG TRÌNH MÔ PHỎNG ĐIỀU KHIỂN TẮC
NGHẼN DÙNG THUẬT TOÁN TĂNG GIẢM
4.1 Giới thiệu chương
Nội dung chương 4 mô phỏng thuật toán tăng giảm. Mục đích chính là phân
tích sự hội tụ đến tính bình đẳng và hiệu quả của các thuật toán. Ở đây ta chỉ đề cập
đến thuật toán tăng giảm tuyến tính, từ đó thấy rằng AIMD là thuật toán đảm bảo hội
tụ đến tính hiệu quả và bình đẳng so với các thuật toán tăng giảm khác. Mô phỏng
cho thuật toán này được phân tích trong 4.3.1. Ngoài ra chương 4 còn mô phỏng tính
bình đẳng, hiệu quả của giao thức điều khiển tắc nghẽn TCP và XCP. Trên thực tế
tính bình đẳng, hiệu quả còn chịu nhiều ảnh hưởng khác nhau như thời gian vòng
truyền RTT không đồng nhất, sử dụng các dịch vụ khác nhau, số lượng luồng đang
truyền dữ liệu,... Công cụ mô phỏng là NS2, kết quả mô phỏng là các đồ thị và minh
họa mạng NAM được phân tích trong 4.3.2.
4.2 Phương pháp và công cụ mô phỏng
4.2.1 Phương pháp phân tích
Trong đề tài này, sinh viên chọn phương pháp mô phỏng trên máy tính với
CAVT và NS-2 (Network Simulation v.2). CAVT [12] là ứng dụng Java nhỏ được
Michael Welzl xây dựng dựa trên biểu đồ vectơ Chiu/Jain [7] đã được đề cập trong
chương 2, nó cung cấp giao diện người dùng mà ta có thể thiết lập điểm bắt đầu và
quan sát quỹ đạo tương ứng bằng cách kích chuột vào biểu đồ.
NS-2 là phần mềm mã nguồn mở, mô phỏng các sự kiện rời rạc nhằm mục
đích nghiên cứu mạng, nó hỗ trợ các giao thức mạng như TCP, UDP, hoạt động của
những tài nguyên mạng như FPT, Telnet, Web, CBR và VBR, các cơ chế quản lý
51
Chương 4: Chương trình mô phỏng điều khiển tắc nghẽn dùng thuật toán tăng giảm
hàng đợi như Drop Tail, RED và CBR, các thuật toán định tuyến ... NS-2 được viết
bằng C++ và OTcl.
Hình 4.1 Tổng quan về NS dưới góc độ người dùng
• OTcl Script Kịch bản OTcl

4.3.1 Mô phỏng thuật toán tăng giảm
Như trong chương 2, tài nguyên phân bố của 2 người dùng bất kỳ
})(),({
21
txtx
có thể biểu diễn như điểm {x
1
, x
2
} trong không gian 2 chiều. Khi
chúng ta đang hoạt động tại hay gần điểm gãy (Knee) (mạng có tài nguyên X
goal
) mọi
tài nguyên yêu cầu bởi người dùng đều được chấp nhận. Thuật toán tăng giảm mong
muốn hội tụ đến bình đẳng và hiệu quả, tức là x
1
+x
2
=X
goal
/2
53
Chương 4: Chương trình mô phỏng điều khiển tắc nghẽn dùng thuật toán tăng giảm
Hình 4.2 Sơ đồ thuật toán tăng giảm
Trong hình 4.3, trục Y (trục đứng) mô tả phân phối (allocation) cho người
dùng 1 x
1
, và trục X (trục ngang) mô tả phân phối cho người dùng 2 x
2
. Tất cả sự

“đường hiệu quả” (đường màu đỏ). Tất cả phân phối mà x
1
= x
2
là phân bố bình đẳng.
Nó tương ứng với đường thẳng được gọi là “đường bình đẳng” (đường màu xanh).
Hai đường này cắt nhau tại điểm (X
goal
/2, X
goal
/2) là điểm tối ưu. Mục tiêu của
phương pháp điều khiển là làm cho hệ thống đến hoạt động tại điểm này mà không
quan tâm đến vị trí bắt đầu. Tất cả các điểm bên dưới đường hiệu quả mô tả hệ thống
“không đủ tải” và một cách lý tưởng hệ thống sẽ yêu cầu người dùng tăng tải. Tương
tự, tất cả các điểm trên đường hiệu quả mô tả hệ thống quá tải.
Hình 4.3 Giao diện công cụ mô phỏng thuật toán tăng giảm
Khi ta chọn đồng bộ ngõ vào tức là 2 người dùng sử dụng thuật toán như
nhau. Ta có thể thay đổi các hệ số tăng giảm a, b, thay đổi thời gian vòng truyền (là
tổng thời gian mất do mạng khi phát gói đi từ luồng đến phía nhận và phát phúc đáp
đến phía gởi). Phụ thuộc vào thuật toán lựa chọn, các hệ số thay đổi đến các giá trị
cho phép. Thêm vào đó ta có thể vẽ đồ thị tốc độ người dùng theo thời gian, khoảng
cách đến điểm tối ưu và tạo ra file dưới dạng text để dùng với các công cụ vẽ đồ thị
thông thường như xgraph hay gnuplot.
55
Chương 4: Chương trình mô phỏng điều khiển tắc nghẽn dùng thuật toán tăng giảm
Mô phỏng thuật toán AIMD và MIAD với 2 người dùng có cùng thời gian
vòng truyền RTT=1s, khoảng thời gian mô phỏng là 50s, các hệ số a=0.1 và b=0.5.
Giá trị x, y lần lượt là tốc độ của người dùng.
Hình 4.4 Biểu đồ vector của thuật toán AIMD
Hình 4.5 Đồ thị biểu diễn theo thời gian