ĐẠI HỌC QU Ố C G IA HÀ NỘI
KHOA CÔNG N G H Ệ
N G U YỄN HOÀNG LINH
PHÂN TÍCH, ĐÁNH GIÁ H IỆU Sư Ấ T H O Ạ T Đ Ộ N G C Ủ A M Ộ T s ố
TH U ẬT TOÁN Đ IỀ U KH IEN t ắ c n g h ẽ n s ố L IỆ U TC P
Chuyên ngành : Công nghệ Thông tin
Mã số :
LUẬN VĂN THẠ C s ĩ KH O A HỌC
Người hướng dẫn khoa học :
Tiến sĩ VŨ DUY LỘI
HÀ NỘI NĂM 2001
ỊĨÍU ỈN 5 ■'
:[
V i ị
Điều khiển tắc nghẽn TCP
Trang 2
NỘI DƯNG
MỞ ĐẦ U 4
CHƯƠNG 1 : GIÓI TH IỆU C H U N G
6
1.1 Điều khiển lưu lượng số liệu trong Internet 6
1.1.1 Giới thiệu chung về mạng Intern et 6
1-1.2 Điều khiển lưu lượng và tắc nghẽn số liệu trên mạng TTMT
10
1.1.3 Điểu khiển lưu lượng và tắc nghẽn số liệu TCP trong mạng Internet
.
14
Cơ chế cửa sổ động 16
Cơ chế phát lại thích nghi 16
Cơ chế điều khiển tắc nghẽn dữ liệu 17
3.1.4 New-Reno T C P 52
3.1.5 SACK T C P 55
3.2 Mô phỏng 60
3.2.1 Kịch bản mô phỏng 60
3.2.2 Một gói dữ liệu bị m ấ t 61
3.2.3 Ba gói dữ liệu bị m ấ t 65
3.3 Kết quả mô phỏng 69
K Ế T LU Ậ N 73
Bảng một số từ viết tắt 78
Tài liệu tham khảo 80
Phụ lục 82
Điều khiển tắc nghẽn TCP Trang 3
Nguyễn Hoàng Linh
Điều khiển tắc nghẽn TCP Trang 4
M Ở Đ Ầ U
Nội dung chính cua luận văn là nghiên cứu cơ chế hoạt động của một số
thuật toán điều khiển tắc nghẽn số liệu TCP, cụ thể là các thuật toán “K h ở i
độn g ch ậ m ” (S low StartX é‘Tránh tắc n g h ẽn ” (C ongestion A voidance), ‘T h át lại
nhanh ” (F ast Retransm it) và “P hụ c h ồ i nhanh (Fast R ecov ery). Đây là bốn thuật
toán c ơ s ở đã được nghiên cứu, công bố và đưa ra cho mọi người trong cộng
đồng Internet (Internet Society) cùng thảo luận và đánh giá. Sau đó một hệ
chương trình mô phỏng mạng máy tính có tên NS được sử dụng để kiểm tra, so
sánh và đánh giá hiệu suất của bốn thuật toán tổng th ể điều kh iển tắc nghẽn s ố
liệu TCP dựa trên bốn thuật toán c ơ s ở ở trên. Đó là các Tahoe, R eno, N ew -
R eno và SA C K TCP.
Bài luận văn được chia thành 3 chương.
Chương I giới thiệu tóm tắt những nội dung chính của luận văn, những vấn
đề mà chúng ta sẽ trình bày chi tiết ở các chương sau. Chương này giới thiệu
tổng quan về Internet, về cấu trúc mạng Internet và bộ giao thức TCP/IP cũng
như về điều khiển lau iượng số liệu trên Internet. Qua đó nêu lên sự cần thiết
■ 1977 : Thử nghiệm thành công việc kết nối ba mạng TTM T của ba trường
đại học lớn ở Mỹ thông qua giao thức TCP/IP.
■ 1986 : V iệc đưa vào sử dụng mạng N SFNET - mạng xương sống Internet tốc
độ cao (45 Mbit/s) - phục vụ cho việc nghiên cứu và giảng dạy đã có ảnh
hưởng tích cực đến sự phát triển mạnh mẽ của Internet trong cộng đồng
nghiên cứu khoa học và giáo dục ở M ỹ và các nước Tây Âu.
Nguyễn Hoàng Linh
Điều khiển tắc nghẽn TCP
Trang 7
■ 1990-1991 : Internet được thương mại hoá với sự ra đời của tổ chức khuyến
khích phát triển và sử dụng Internet “Internet Society” và bắt đầu thời kỳ
phát triển bùng nổ của Internet. Từ đây Internet trở thành mạng TTM T toàn
cầu.
* 1997 : Đ ã có hơn 100000 mạng TTMT được kết nối trong Internet với hơn
15 triệu máy chủ và 50 triệu người sử dụng.
Những nhân tô' chính thúc đẩy sự phát triển của Internet (thực chất là việc
mở rộng mạng thông qua các kết nối các máy tính và các mạng máy tính với
nhau trên cơ sở bộ giao thức trao đổi dữ liệu TCP/ IP) :
■ Với việc sử dụng bộ giao thức TCP/IP trong hệ điều hành UNIX để thực
hiện trao đổi dữ liệu giữa các tiến trình trên một máy và giữa các máy được
kết nối trong mạng. UNIX là hệ điều hành được sử dụng rông rãi từ năm
1983 trong các trường đại học và các viện nghiên cứu ở Mỹ.
■ Kỹ thuật vi xử lý và các máy tính các nhân PC ra đời vào những năm 1980
ngày càng được hoàn thiện và nâng cao vé công suất tính toán và tiện lợi cho
người sử dụng đã rút ngắn khoảng cách giữa người dùng và máy tính, máy
tính ngày càng thâm nhập sâu vào các lĩnh vực của đời sống xã hội và thúc
đẩy nhu cầu kết nối máy tính và mạng máy tính.
■ NFSNET, mạng xương sống Internet ra đời năm 1986 ở Mỹ với tốc độ truy
nhập đường trục là 45 Mbit/s, đã nâng cao cơ bản về giải thông và chất
lượng truy cập mạng, đáp ứng nhu cầu trao đổi thông tin trong cộng đồng
ppp
Physical
Coax, Twisted Pairs, Fiber Optic, WMess
FTP - File Transfer Protocol
HTTP - HyperText Transfer Protocol
SMTP - Simple Mail Transfer Protocol
DNS - Domain Name System
TCP - Transmision Control Protocol
UDP - User Datagram Protocol
SLIP - Serial Line Internet Protocol
ppp - Point to Point protocol
Hình 1.1 Bộ giao thức trên mạng Internet
Khác với mô hình IOS/OSI, tầng liên mạng Internet sử dụng giao thức kết
nối mạng “không liên kết” (connectionless) IP (Internet Protocol) tạo thành hạt
nhân hoạt động của hệ thống truyền dẫn Internet. Cùng với các thuật toán định
tuyến tầng liên mạng IP cho phép kết nối một cách linh hoạt các loại mạng vật
lý khác nhau như : Ethenet, Token Ring, X25 dựa trên địa chỉ IP (bao gồm địa
chỉ phân mạng IP và địa chỉ của thiết bị cuối thuộc phân mạng đó). Giao thức
lièn mạng IP bao gồm các chức năng chính sau :
■ Định nghĩa cấu trúc gói dữ liệu là đơn vị cơ sở của dữ liệu được trao đổi trên
Internet.
■ Định nghĩa phương thức đánh địa chỉ IP.
Nguyễn Hoàng Linh
Điều khiển tắc nghẽn TCP
Trang 9
■ Truyền dữ liệu giữa mức vận chuyển và mức truy nhập mạng (Access
Network) .
■ Định tuyến đường đi của các gói dữ liệu trong mạng.
■ Thực hiện việc phân mảnh (fragmentation) và hợp nhất (reassembly) các
gói dữ liệu và nhúng / tách chúng trong các gói dữ liệu ở mức liên kết.
(DNS) không chỉ tích hợp các dịch vụ của các tầng chức năng như tầng phiên
(session), tầng thể hiện (presentation), và tầng ứng dụng (application) trong một
thực thể thống nhất mà còn được cài đặt phổ biến như là những bộ phận cấu
thành của các hệ điểu hành thông dụng như U N IX (của nhiều nhà cung cấp
khác nhau), Windows 9X /N T, Novell Netware
Chi tiết về bộ giao thức TCP/IP cũng như một số giao thức điều khiển và
nhất là giao thức TC P được trình bày chi tiết trong [Loi99, Ste94, Pos81 ].
1.1.2 Điều khiển lưu lượng và tắc nghẽn số liệu trên mạng TTMT
Như đă trình bày ở trên, mạng TTM T đầu tiên trên thế giới là mạng
APARNET được thiết kế và xây dựng trên cơ sở công nghệ chuyển mạch gói.
Kỹ thuật chuyển mạch gói cho phép chuyển tiếp dữ liệu giữa các thiết bị cuối
trôn cơ sở chia chúng thành các gói có độ dài thay đổi và chuyển dữ liệu qua
các đoạn đường khác nhau trong hệ thống truyền dẫn. Đ ặc trưng của công nghệ
chuyển mạch gói là :
■ Dữ liệu được chuyển tiếp trên cơ sở các gói có độ dài khác nhau.
* Phần tiêu đề (header) chứa các dữ liệu điều khiển cần thiết cho việc chọn
đường và chuyển tiếp chính xác đến địa chỉ đích. Hệ chuyển mạch nhận toàn
bộ gói dữ liệu, lưu trữ tạm thời trong bộ nhớ đệm để phân tích dữ liệu điều
khiển, chọn đường và thực hiện chuyển tiếp. Kỹ thuật này còn được gọi là
"lưu và chuyển" (store-and-forward).
Nguyễn Hoàng Linh
Điều khiển tắc nghẽn TCP
Trang 11
■ Công nghệ chuyển mạch gói có cả hướng kết nối (connection oriented) trên
cơ sở các kênh truyền dẫn ảo và không hướng kết nối (connectionless) trên
cơ sở các gói dữ liệu độc lập (datagram).
Mạng chuyển mạnh gói bắt nguồn từ hiệu quả của việc chia xẻ tài nguyên
mạng cho những người sử dụng khác nhau. M ột kết nối mạng có thể được sử
dụng cho việc truyền dữ liệu giữa nhiều cặp nút mạng nguổn/đích khác nhau.
Tron? trường hợp này thì cả dung lượng vùng đệm của nút cũng như bộ vi xử lý
xuất vượt quá khả năng đó, mạng phải tiếp tục chuyển giao các gói dữ liệu với
đúng khả năng của nó. Đường cong được gán nhãn id e a l (lý tưởng) phản ánh
khả năng này.
Trong thực tế, nếu mạng không được điều khiển, mạng sẽ chuyển giao tất cả
tải đ ề xuất (ứng với trường hợp lý tưởng) chỉ cho những gía trị của tải đ ề xuất
dưới một mức nhất định. Khi tải đ ề xu ất tăng bên ngoài điểm này, thông lượng
thực tế (mặc dù vẫn còn tăng như là một hàm của tải đ ề xuất ) bắt đầu đi trệch
khỏi đường “lý tưởng“. Trong khi tải đ ề xuất tăng thêm nữa trong một mạng
không có điều khiển, thông lượng bắt đầu giảm (xem Hình 1.2). Lưu lượng
mạnc đề xuất càng lớn, nó sẽ chuyển giao dữ liệu càng nhỏ.
Nguyễn Hoàng Linh
Điều khiển tắc nghẽn TCP
Trang 13
Những thủ tục diều khiển lưu lượng và tắc nghẽn s ố liệu được sử dụng để
đảm bảo một nút mạng nguồn không làm tràn một nút mạng đích với quá lun
lượng mà nó cho phép (có thể xử lý). Sau đây là tóm tắt việc phân loại điều
khiển lưu lượng và tắc nghẽn số liệu trong mạng TTM T nói chung :
Điéu khiển lưu lương
■ E nd-to-end : đảm bảo một máy chủ (host) nguồn gửi các gói dữ liệu tới máy
chủ đích với tốc độ không vượt quá tốc độ mà máy chủ đích nhận các gói dữ
liệu đó.
■ H op-by-hop : điểu khiển tốc độ lưu lượng dữ liệu được thực hiện giữa hai
nút liên tiếp nhau trên đường từ một máy chủ nguồn tới một máy chủ đích.
Diều khiển tác nghẽn được sử dụng để đảm bảo mạng là một khối thống
nhất không thể được yêu cầu truyền quá số lượng dữ liệu hơn là nó có khả năng
xử lý :
■ Truy cập m ạng (network access) : Các thủ tục này được sử dụng để điều
khiển tổng lưu lượng mà một máy chủ có thể đưa vào mạng con
(subnetwork).
* Cấp p h át vùng đệm (buffer allocation) : Các thủ tục cấp phát vùng đệm được
Điéu khiển tắc nghẽn TCP Trang 15
dẫn bị sụp đổ hoàn toàn; không một gói dữ liệu nào được thực sự chuyển qua hệ
thốns truyền dẫn.
Một số nguyên nhân chính dưới đây làm dữ liệu chuyển tiếp bị mất, buộc
các thực thể giao thức ở mức tương ứng phải kích hoạt việc xử lý lỗi bằng cách
phát lại dữ liệu bị mất, dẫn đến hiện tượng tắc nghẽn dữ liệu như mô tả ở trên.
■ Công suất tính toán của hệ thống chuyển mạch không đáp ứng được yêu cầu
nhận, phân tích, quyết định và chuyển tiếp dữ liệu khi lưu lượng dữ liệu cần
được chuyển tiếp trong mạng tăng.
■ Dữ liệu ở nhiều kênh vào cùng được chuyển tiếp tới một kênh ra.
■ Dung lượng bộ đệm thu nhỏ không đủ để lưu giữ tạm thời các gói dữ liệu
trước khi có quyết định chuyển tiếp.
Để khắc phục, người ta đề ra các biện pháp hạn chế lưu lượng dữ liệu cần
chuyển tiếp, phù hợp với khả năng xử lý và chuyển tiếp của hệ thống truyền
dẫn:
■ Cung cấp đủ dung lượng bộ nhớ đệm cho các hệ thống chuyển mạch.
* Phân chia bộ nhớ đệm hợp lý cho các kênh vào/ra. Cho phép loại bỏ sớm dữ
liệu vào khi không có khả năng lưu giữ tạm thời và xử lý.
■ Hạn chế lưu lượng dữ liệu ở ngay đầu vào của hệ thống truyền dẫn.
■ Điều khiển lưu lượng dữ liệu (ví dụ bằng cơ chế cửa sổ) để tránh xảy ra mất
dữ liệu, ngăn chặn khả năng xảy ra hiện tượng tắc nghẽn dữ liệu.
Nội đung của bài luận văn này chỉ tập chung vào một số thuật toán điều
khiển tắc nghẽn số liệu của giao thức TCP trong mạng Internet. Sau đây chúng
ta sẽ trình bày các cơ chế điều khiển lưu lượng và tắc nghẽn số liệu của TCP.
Nguyễn Hoàne Linh
Điều khiển tắc nghẽn TCP
Trang 16
Cơ chế cửa sổ động
Cơ chế cửa sổ là một trong các phương pháp điều khiển lưu lượng và tắc
nghẽn dữ liệu trong mạng TTM T. Đ ộ lớn cửa sổ chính bằng số lượng gói dữ
định [JA C88],
Cơ chế điều khiển tắc nghẽn dữ liệu
Hiện tượng tắc nghẽn dữ liệu thể hiện trước hết ở việc gia tăng thời gian trẻ
của dữ liệu khi chuyển qua mạng. Để hạn chế vấn để này, người ta điều khiển
lưu lượng dữ liệu trao đổi dựa trên việc thay đổi độ lớn cửa sổ phát. Có 4 quá
trình để điểu khiển tấc nghẽn dữ liệu : "Khởi động chậm " (slow start), "Tránh
tắc nghẽn" (congestion avoidance), "Phát lại nhanh" (fast retransmit), "Phục hổi
nhanh" (fast recovery). Việc nghiên cứu, phân tích và mô tả thuật toán các quá
trình này là một phần nội dung chính của bài luận văn và được trình bày chi tiết
troníĩ chương 2.
Data
RTT
Hình ỉ.4 : Thời gian trễ toàn phần RTT
Nguyễn Hoàng Linh
Điều khiển tắc nghẽn TCP Trang 18
1.2 Phân tích đánh giá hiệu suất
1.2.1 Sự cần thiết
Trong những năm gần đây các mạng máy tính đã trải qua một thời kỳ phát
triển nhanh chóng. Với sự phát triển đó không tránh khỏi phát sinh một số vấn
đề
về thất thoát dữ liệu trên mạng. Chẳng hạn như các cổng Internet nhìn chung
thất thoát khoảng 10 % các gói dữ liệu được gửi đến với lí do là vùng đệm cục
bộ bị tràn. Theo sự điều tra nghiên cứu về một số vấn để đã chỉ ra rằng nhiều
nguyên nhân nằm trong các sự thực hiện giao thức ở tầng vận chuyển (transport
layer) có thể dẫn đến sự ùn tắc trên mạng. Những thuật toán được bắt nguồn từ
ý tưởng của việc đạt được sự ổn định của mạng bởi sự bắt buộc kết nối tuân
theo nguyên tắc bả o toàn c ấ c g ó i dữ liệu. Chúng ta sẽ chỉ ra các thuật toán bắt
nguồn từ nguyên lý này và tác động của nó đối với việc giải quyết vấn đề tắc
nghẽn trên mạng như thế nào.
1.2.2 Các phương pháp
để ra, không cần chi phí tốn kém mà vẫn có thể tiến hành nghiên cứu một cách
độc lập và hiệu quả. Việc xây dựng các chương trình mô phỏng đã được nhiểu
trường đại học và các tổ chức trên thế giới thực hiện. Hệ mô phỏng máy tính NS
mà ta sử dụng trong phạm vi bài luận văn này là một công cụ tốt và hiệu quả để
thực hiện trắc nghiệm và đánh giá một số thuật toán điều khiển tắc nghẽn số
liệu TCP được đề cập ở phần trên.
Hệ thống mô phỏng NS
NS là hệ mô phỏng máy tính được xây dựng và phát triển bởi dự án VINT
của phòng thí nghiệm quốc gia Lawrence Berkeley National Laboratory. NS là
Nguyễn Hoàng Linh
Điểu khiển tắc nghẽn TCP
Trang 20
một hệ mô phỏng có cấu trúc hướng đối tượng. Nó được xây dựng trên hai ngôn
ngữ C + + và Otcl và có thể được mở rộng bởi người sử dụng (người sử dụng có
thể lập trình được trên nền của hệ mô phỏng NS). Với cách tiếp cận này thì ta
có thể coi mỗi một mô phỏng như một chương trình hơn là các mô hình cứng
nhắc, tĩnh, không thể thay đổi. Một mô phỏng gồm các đối tượng có thể cấu
hình tuỳ ý để có thể đạt được mục đích mô phỏng đề ra.
Do vậy những người thiết kế NS đã không chọn một ngôn ngữ duy nhất để
xây dựng môi trường mô phỏng, bởi có những đòi hỏi khác nhau về mục đích
của việc mô phỏng. Khi cần mô phỏng những tầng thấp của mạng máy tính, xử
lý ở mức độ byte hay tiêu đề (header) các gói tin thì cần đòi hỏi một hiệu quả
tính toán cao, do đó nhân của hệ mô phỏng được viết bằng c++ . Còn phần định
nghĩa, cấu hình và điều khiển mô phỏng được viết bằng ngôn ngữ script Tel.
Cách tiếp cận này mang lại hiệu quả rất cao vì nó chia mục đích của việc mô
phỏng thành những phần nhỏ và giải quyết chúng bằng những ngôn ngữ phù
hợp. Nó cung cấp cho người lập trình khả năng sử dụng dễ dàng hơn, mềm dẻo
và linh hoạt hơn.
Vì C ++ là ngôn ngữ hướng đối tượng mà Tel thì không, nên người ta phải
xây dựng những đối tượng m acro bậc cao cho phù hợp với các lớp của c++. Sau
phát minh trong [Jac88] và [Jac90].
Để thực hiện việc nghiên cứu, phân tích và mô tả chi tiết bốn thuật toán trên
trước tiên chúng ta phải đưa ra một số định nghĩa, những khái niệm và qui ước
mà chúng ta sẽ sử dụng trong suốt phần còn lại của bài luận văn.
2.1 M ột số định nghĩa và khái niệm quan trọng
SEG M ENT : Một segment là một gói dữ liệu (gói tin) TCP/IP hay một gói
ACK trả lời nào đó (hoặc cả hai).
SENDER M A X IM U M SEGM EN T SIZ E (SM SS) : SWISS là độ dài tối đa của
một segment (gói dữ Liệu) mà thực thể gửi có thể truyền đi. Giá trị này được dựa
trên “đơn vị truyền tối đa” (the maximum transmission unit) của mạng, thuật
toán phát hiện đường đi M TU [M D 90], R M SS (xem nội dung tiếp sau), hay các
Nguyễn Hoàng Linh
Điểu khiển tắc nghẽn TCP Trang 23
yếu tố khác. Độ lớn này không bao gồm các tiêu đề TCP/IP và các tuỳ chọn
(options).
R E C EIV E R M A XIM U M SEGM ENT SIZE (RM SS) : RM SS là độ lớn của
một segment lớn nhất mà thực thể nhận có thể (sẵn sàng) nhận. Giá trị này được
định rõ trong sự lựa chọn M SS và được gửi bởi thực thể nhận trong quá trình
khởi tạo kết nối. Hoặc nó sẽ là 536 bytes (giá trị được chấp nhận do qui định
của các mạng vật lý) nếu M SS không được lựa chọn [Bra89]. Kích thước này
không bao sồm các tiêu đề TCP/IP (TCP/IP headers) và các tuỳ chọn (options).
FU LL-SIZED SEGM ENT : M ột g ó i dữ liệu chứa độ dài tối đa của các byte
dữ liệu được phép (ví dụ như là một g ó i d ữ liệu chứa SM SS byte dữ liệu). Ta
viết ngắn gọn là gói-tối-đa.
R E C E IV E R W INDOW (rwnd) : Cửa sổ thu của thực thể nhận được thông
báo mới đây nhất (viết ngắn gọn : cửa s ổ thu).
CONGESTION W INDOW (cwnd) : Một biến trạng thái TCP, nó qui định
tổng số dữ liệu mà một TCP có thể truyền hay còn gọi là cửa sổ tắc nghẽn. Vào
bất cứ thời điểm quy định đã cho nào, một TCP không được gửi dữ liệu với một
số tuần tự ỉón hơn tổng của số tuần tự đã được trả lời lớn nhất và giá trị tối thiểu
(3) Sự cân bằng không thể đạt được do tài nguyên bị hạn chế (thiếu bộ nhớ
đệm chẳng hạn).
Nguyễn Hoàng Linh
Điẻu khiển tắc nghẽn TCP Trang 25
2.2.1 Các thuật toán “Khởi động chậm” và “Tránh tắc nghẽn”
"Khởi động chậm"
Các phiên bản TCP trước đây bắt đầu một kết nối với việc thực thể gửi phát
nhiều gói dữ liệu một lúc vào mạng, cho đến khi đạt được kích thước cửa sổ đã
được thông báo bởi thực thể nhận (cửa sổ thu). Điều đó không có vấn đề gì khi
hai máy chủ (host) cùng nằm trên cùng một mạng LAN, và nếu có các bộ định
tuyến (router) và các liên kết tốc độ thấp giữa thực thể gửi và thực thể nhận thì
vấn đề có thể nảy sinh. Ở một số bộ định tuyến trung gian các gói dữ liệu khi
được vận chuyển qua phải xếp hàng (trong một hàng đợi) để chờ đến lượt, và
vấn đề rất có thể xảy ra là bộ định tuyến này bị tràn bộ nhớ đệm do không còn
đủ chồ để lưu giữ các gói dữ liệu tiếp theo. [JAC88] cho thấy cách tiếp cận này
có thể làm giảm thông lượng của một kết nối TCP.
Thuật toán để giải quyết vấn đề trên được gọi là "Khởi động chậm". Nó hoạt
động bởi việc quan sát tốc độ mà với nó thực thể gửi phát các gói dữ liệu mới
vào mạng cũng là tốc độ mà với nó các gói ACK trả lời được trả lại bởi thực thể
nhận.
Nguyền Hoàng Linh
Copyright: Tài liệu đại học ©