Nghiên cứu kĩ thuật điều khiển tắc nghẽn mạng và mô phỏng, đánh giá trên Network Simulator-2 - pdf 25

Link tải luận văn miễn phí cho ae Kết nối
Nghiên cứu và khảo sát một số thuật toán điều khiển tắc nghẽn điển hình trên TCP (giao thức điều khiển truyền dẫn) và trên gateway. Đưa ra những ưu nhược điểm và so sánh các thuật toán này với nhau trong quá trình tránh tắc nghẽn. Từ đó khảo sát hoạt động của các thuật toán bằng chương trình mô phỏng và đưa ra một số kết quả mô phỏng với các thuật toán điều khiển tắc nghẽn trên TCP. Đồng thời đưa ra kết quả mô phỏng với các thuật toán DropTail, RED và RED thích nghi nhằm đánh giá hoạt động của thuật toán này
Luận văn ThS. Kỹ thuật vô tuyến điện tử và thông tin liên lạc -- Trường Đại học Công nghệ. Đại học Quốc gia Hà Nội, 2006

Chương 1: Các thuật toán điều khiển tắc nghẽn mạng trên lớp TCP ...........
1.1 Cơ chế cửa sổ trượt..........................................................................
1.2 Tính toán thời gian phát lại..............................................................
1.2.1 Tính trung bình đơn giản..........................................................
1.2.2 Tính trung bình theo hàm mũ ..................................................
1.3 Quan hệ giữa điều khiển luồng và điều khiển tắc nghẽn trên TCP...
1.3.1 đoán phương sai RTT.........................................................
1.3.2 Exponential RTO backoff .........................................................
1.3.3 Thuật toán Karn ......................................................................
1.4 Thuật toán Tahoe ............................................................................
1.4.1 Kĩ thuật slow-start....................................................................
1.4.2 Kĩ thuật Congestion Avoidance ................................................
1.4.3 Kĩ thuật fast retransmit ............................................................
1.5 Thuật toán Reno ..............................................................................
1.5.1 Kĩ thuật fast recovery...............................................................
1.5.2 Thuật toán NewReno ...............................................................
1.6 Thuật toán Vegas .............................................................................
1.6.1 Cơ chế phát lại mới..................................................................
1.6.2 Cơ chế Congestion Avoidance..................................................
1.6.3 Thay đổi cơ chế slow-start .......................................................
Chương 2: Các thuật toán điều khiển tắc nghẽn mạng trên Gateway...........
2.1 Random Early Detection .................................................................
2.1.1 Thuật toán RED .......................................................................
2.1.2 Tính toán kích thước hàng đợi trung bình ................................
2.1.3 Tính toán xác xuất loại bỏ gói tin.............................................
2.1.4 Ưu nhược điểm của RED .....................................................
2.2 RED thích nghi (Adaptive RED)...................................................
2.2.1 Thuật toán RED thích nghi...................................................
2.2.2 Khoảng giới hạn của các thông số ......................................
2.2.3 Ưu nhược điểm của RED thích nghi.....................................
Phần 2: Mô phỏng và đánh giá...............................................................
Chương 3: Giới thiệu về chương trình mô phỏng mạng NS-2 ..................
3.1 Tổng quan về NS-2.......................................................................
3.2 Một số lớp đối tượng trong NS-2 ..................................................
3.2.1 Lớp tcp.................................................................................
3.2.2 Lớp tcp-sink .........................................................................
3.2.3 Lớp link................................................................................
3.2.4 Lớp trace .............................................................................
3.3 Các bước xây dựng một chương trình mô phỏng ..........................
3.4 Khảo sát và đánh giá kết quả mô phỏng .......................................
Chương 4: Mô phỏng và đánh giá các thuật toán
điều khiển tắc nghẽn trên TCP.......
4.1 Thuật toán Tahoe .........................................................................
4.2 Thuật toán Reno...........................................................................
4.3 Thuật toán NewReno ....................................................................
4.4 Thuật toán Vegas..........................................................................
Chương 5: Mô phỏng và đánh giá các thuật toán điều khiển
tắc nghẽn trên Gateway ........
5.1 RED cơ bản..................................................................................
5.1.1 So sánh hoạt động của RED với DropTail............................
5.1.2 Sự nhạy cảm của RED với mức độ tải dữ liệu lên mạng .......
5.1.3 Sự nhạy cảm với thông số của RED......................................
5.2 RED thích nghi.............................................................................
Kết luận...................................................................................................
Tài liệu tham khảo...................................................................................
Phụ lục ....................................................................................................TCP/IP là hệ thống giao thức thống trị trên mạng ngày nay. Là giao
thức lớp giao vận (transport) TCP cung cấp một giao diện giữa lớp ứng dụng
và lớp mạng mà qua đó các ứng dụng có thể sử dụng các dịch vụ mạng với
chất lượng dịch vụ (QoS) mong muốn. Chất lượng dịch vụ được xác định dựa
vào một loạt thông số như thông lượng, tốc độ mất gói tin, hiệu suất sử dụng
mạng, độ trễ, độ công bằng (fairness).... Các thông số này không chỉ phụ
thuộc vào cấu trúc vật lí của mạng, mà còn phụ thuộc nhiều vào cách thức tổ
chức hoạt động của các thành phần của mạng. Các thuật toán cổ điển như
DropTail trên Gateway [3,18] hay Tahoe [25] trên TCP đã được triển khai rất
rộng trên mạng do tính đơn giản và khá hiệu quả của chúng. Tuy nhiên yêu
cầu ngày càng cao về chất lượng dịch vụ như thông lượng truyền dẫn cao, độ
trễ thấp, hiệu suất sử dụng mạng cao,... đã khiến cho các thuật toán cổ điển
này ngày càng không đáp ứng được yêu cầu. Mặt khác chúng còn gây ra
nhiều vấn đề lớn làm hạn chế chất lượng dịch vụ. Đặc biệt hiện tượng tắc
nghẽn mạng xảy ra tại các Gateway khi tổng thông lượng truyền đến quá cao
làm ảnh hưởng đến một loạt yếu tố quyết định chất lượng dịch vụ như tăng độ
trễ, tăng tốc độ mất gói tin, giảm hiệu suất mạng, giảm thông lượng truyền tin,
tính công bằng không được bảo đảm,... Độ trễ tăng lên không chỉ gây mất thời
gian chờ đợi cho người dùng mà còn sẽ làm cho mạng không thể đáp ứng
được một số loại dịch vụ yêu cầu mà độ trễ phải được giới hạn (delay-limited)
như thoại. Tốc độ mất gói tin tăng lên làm tăng sự lãng phí tài nguyên mạng
vì một gói tin bị mất có nghĩa là hàng loạt tài nguyên đã dùng để truyền nó trở
thành vô ích. .v.v. Chính vì vậy mà yêu cầu về kiểm soát tắc nghẽn mạng
ngày càng trở nên quan trọng và trở thành chủ đề nghiên cứu, mô phỏng, thử nghiệm và ứng dụng trong nhiều năm gần đây. Các cơ chế kiểm soát hay điều
khiển tắc nghẽn mạng có thể phân ra hai hướng chính : điều khiển tắc nghẽn
dựa trên TCP và điều khiển tắc nghẽn dựa trên Gateway. Mục tiêu cơ bản
nhất của mọi cơ chế điều khiển tắc nghẽn mạng là nhằm hạn chế lượng dữ
liệu đưa lên mạng ở mức mà mạng có thể truyền được. Chỉ khi đạt được mục
tiêu đó thì mới có thể kiểm soát được tắc nghẽn mạng.
Kiểm soát tắc nghẽn mạng dựa trên TCP gặp rất nhiều khó khăn [34]:
1. IP là giao thức không kết nối, không trạng thái do đó không cung
cấp công cụ gì cho phát hiện tắc nghẽn, và rất ít cho điều khiển
tắc nghẽn.
2. TCP chỉ cung cấp các công cụ cho điều khiển luồng đầu cuối
(end-to-end) và chỉ có thể suy ra sự tắc nghẽn thông qua các
phương pháp gián tiếp (trừ khi sử dụng ECN – Explicit
Congestion Notification [12]). Thêm nữa độ trễ trên mạng có thể
biến đổi nên các điều kiện mạng mà TCP tính ra được có thể
khổng đủ tin cậy.
3. Không có một thuật toán phân tán nào có thể kết nối và phối hợp
hoạt động của được hàng loạt các thực thể TCP. Do đó các thực
thể TCP không thể phối hợp với nhau để duy trì tổng thông lượng
ở một mức nào đó, thay vào đó chúng hoạt động giống như cạnh
tranh các tài nguyên mạng một cách ích kỉ.
Công cụ duy nhất trong TCP liên quan đến kiểm soát tắc nghẽn là cơ chế
điều khiển luồng bằng cửa sổ trượt (sliding-window [34]) và cơ chế điều
khiển lỗi. Hàng loạt giải pháp được đưa ra để sử dụng các cơ chế này cho việc
phát hiện xung đột, tránh xung đột và phục hồi sau tắc nghẽn. Nói chung các
giải pháp ra đời sau thường là nhằm khắc phục các giới hạn của các giải pháp
trước đó và sau một thời gian nghiên cứu, thử nghiệm đã trở thành tiêu chuẩn
hay khuyến nghị cho TCP. Tahoe là giải pháp cổ điển nhất, bao gồm các cơ
chế nhỏ như khởi động chậm (slow-start), tránh tắc nghẽn (congestion
avoidance- CA) và phát lại nhanh (fast-retransmit). Tahoe sử dụng các ACK
lặp hay đồng hồ phát lại (retransmit timer) để xác định sự mất gói tin hay sự
tắc nghẽn trên mạng. Reno [28] cải tiến cơ chế fast-retransmit của Tahoe
thành hồi phục nhanh (fast-recovery) và đạt được sự cải tiến tốt khi không có
quá một gói tin trong cùng một cửa sổ dữ liệu bị mất. Tuy nhiên hiệu quả có
thể giảm đi khi có nhiều hơn một gói tin trong cùng một cửa sổ dữ liệu bị mất,
hay chính xác hơn là có nhiều hơn một gói tin bị mất trước khi fast-retransmit
được khởi động. NewReno [17] là một cải tiến của Reno nhằm giải quyết tình
huống trên. Tuy nhiên hiệu quả vẫn có thể giảm đi rất nhiều khi quá nhiều gói
tin trong cùng cửa sổ dữ liệu bị mất, thậm chí hoạt động không bằng Tahoe
trong một vài trường hợp.
Khác với tính chất reactive (phản ứng lại) của các thuật toán trên, tính
chất mà TCP phải làm mất gói tin thì mới xác định được điều kiện của mạng,
Vegas [4,5] là một thuật toán proactive (chủ động), cho phép TCP dự đoán
được điều kiện tắc nghẽn của mạng mà không cần làm mất gói tin. Vegas dựa
vào sự so sánh thông lượng tức thời và thông lượng trung bình để dự đoán
điều kiện tắc nghẽn mạng và cho phép TCP hoạt động hiệu quả hơn, duy trì
giai đoạn CA dài hơn, tăng thông lượng và giảm tốc độ gói tin mất.
Các thuật toán trên chỉ cần thay đổi TCP nguồn mà không thay đổi gì
đến TCP đích. SACK [28] là một thuật toán cần sự thay đổi cả ở TCP đích -
tạo ra SACK - và TCP nguồn - phản ứng với SACK. SACK có thể hoạt động
tốt ngay cả khi có nhiều gói tin trong cùng cửa sổ bị mất. Veno [36,37] là sự
kết hợp của Vegas và Reno để thích hợp với môi trường mạng không dây -
môi trường mà tỉ lệ gói tin mất do lỗi khá cao. Ngoài ra còn có một số thuật
toán khác như Westwood, Westwood+[30] ,... cũng đã được đưa ra.
Các thuật toán trên chạy trên TCP đã cải thiện rất tốt khả năng kiểm soát
tắc nghẽn mạng cũng như nâng cao chất lượng dịch vụ. Nhưng kiểu Gateway
DropTail vẫn còn hạn chế nhiều đến sự kiểm soát tắc nghẽn cũng như gây ra
một số hiện tượng không tốt khác. Gateway DropTail sử dụng một bộ đệm
hữu hạn làm hàng đợi và hoạt động kiểu vào trước - ra trước (First In First
Out - FIFO). Các gói tin đến khi bộ đệm đã đầy sẽ lập tức bị loại bỏ. Hàng
loạt gói tin đến từ các TCP nguồn khác nhau có thể bị loại bỏ gần như đồng
thời, do đó hàng loạt TCP sẽ gần như đồng thời thực hiện phát lại và giảm
thông lượng của mình xuống đồng loạt một cách không cần thiết. Do vậy gây
ra hiệu ứng đồng bộ toàn cục (global synchronization) làm giảm hiệu suất
mạng, hơn nữa còn có thể dẫn đến một chu kì đồng bộ mới. Bộ đệm có thể
tăng lên để làm giảm xác suất mất gói tin, tăng thông lượng, nhưng sẽ kéo
theo độ trễ trung bình tăng lên. Mặt khác sự tăng bộ đệm có thể là không giới
hạn được và trở nên bất khả thi. Cơ chế quản lí hàng đợi tích cực (Active
Queue Management - AQM) được đưa ra nhằm giải quyết các vấn đề trên.
Nhiều kĩ thuật được đưa ra như ERD (Early Random Drop)[21], DECbit [27],
IP Source Quench [32], RED (Random Early Detection) [18],... trong đó khả
quan nhất là RED. RED loại bỏ gói tin ngay từ khi hàng đợi chưa đầy với xác
suất loại bỏ tỉ lệ với kích thước hàng đợi trung bình. RED được thiết kế với
các mục tiêu chính là tránh tắc nghẽn, tránh đồng bộ toàn cục, cho phép khả
năng truyền burst và giới hạn kích thước hàng đợi trung bình. RED thực hiện
khá tốt các mục tiêu này, nhưng có nhược điểm lớn là khả năng hoạt động phụ
thuộc nhiều vào các thông số hoạt động và mức độ tải dữ liệu lên mạng. Cũng
có nhiều giải pháp được đưa ra để khắc phục yếu điểm này của RED như cơ
chế quản lí từng luồng (per-flow scheduling) [7], RED loại bỏ ưu tiên (RED
PD)[19], RED thích nghi (Adaptive RED)[16],... trong đó RED thích nghi tỏ
ra hiệu quả và đơn giản hơn hẳn. RED thích nghi tự động điều chỉnh một số thông số của RED để phù hợp với điều kiện mạng và đảm bảo vùng hoạt động
xác định cho hàng đợi. RED thích nghi hoạt động tốt hơn RED, và đặc biệt là
nó cho phép thao tác cấu hình đơn giản hơn nhiều.
Nghiên cứu các kĩ thuật trên đòi hỏi một quá trình mô phỏng, kiểm định
rất cẩn thận trước khi đưa thành khuyến nghị hay triển khai thực tế. Network
Simulator (NS) [13,23] là một công cụ mô phỏng mạng rất mạnh và phù hợp
cho công việc này. NS dựa trên ngôn ngữ lập trình hướng đối tượng (object
oriented) là C++ và ngôn ngữ lập trình kịch bản (script) là OTcl để thực hiện
các chương trình mô phỏng hướng đối tượng và hướng sự kiện (even
oriented). Trải qua nhiều phiên bản, tới nay đã là NS2-30, NS tích hợp sẵn rất
nhiều thí nghiệm mô phỏng mạng, tạo điều kiện cho những người đi sau có
thể xây dựng hay lặp lại các thí nghiệm một cách dễ dàng hơn. NS2 nay đã
trở thành sự bảo đảm về công cụ mô phỏng cho các thí nghiệm về mạng.
Trong luận văn này trước hết sẽ nghiên cứu, tìm hiểu về một số kĩ thuật
tránh tắc nghẽn mạng nêu trên, sau đó sẽ tiến hành mô phỏng trên NS2 để
khảo sát và khẳng định lại những gì tìm hiểu, nghiên cứu được.


/file/d/0B7oUCI ... sp=sharing
Music ♫

Copyright: Tài liệu đại học © DMCA.com Protection Status