Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
BỘ GIÁO DỤC VÀ ĐÀO TẠO
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC KỸ THUẬT CÔNG NGHIỆP
LUẬN VĂN THẠC SỸ KỸ THUẬT
NGÀNH KỸ THUẬT ĐIỆN TỬ ỨNG DỤNG GIẢI THUẬT DI TRUYỀN MỜ CHO
BÀI TOÁN QUẢN LÝ HÀNG ĐỢI TÍCH CỰC
(AQM) TRONG VIỄN THÔNG LÊ HOÀNG
Thái Nguyên, 2010
Trang i
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
ĐẠI HỌC THÁI NGUYÊN
TRƢỜNG ĐẠI HỌC
KỸ THUẬT CÔNG NGHIỆP
CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM
Độc lập - Tự do - Hạnh phúc
THUYẾT MINH
LUẬN VĂN THẠC SỸ KỸ THUẬT
Học viên: Lê Hoàng
Lớp: Cao học - K11
Chuyên ngành: Kỹ thuật Điện tử
Người hướng dẫn khoa học: PGS.TS Lê Bá Dũng
Ngày giao đề tài: 20 tháng 01 năm 2010.
Ngày hoàn thành: 5 tháng 9 năm 2010.
CÁN BỘ HƢỚNG DẪN KHOA HỌC
Trang iii
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
LỜI CẢM ƠN
Trong suốt quá trình học tập và tốt nghiệp, tôi đã nhận được sự giúp đỡ tận
tình của các thầy cô giáo và tôi đặc biệt muốn cảm ơn:
Thầy giáo PGS. TS. Lê Bá Dũng, Viện công nghệ thông tin, Viện khoa học và
công nghệ Việt Nam. [email protected].
Thầy giáo ThS. Nguyễn Phương Huy, Bộ môn Điện tử viễn thông, Khoa Điện
tử, Trường Đại học Kỹ thuật Công nghiệp Thái Nguyên.
[email protected].
đã tận tình giúp đỡ, hướng dẫn tôi trong thời gian thực hiện đề tài, cảm ơn sự
giúp đỡ của gia đình, bạn bè và các đồng nghiệp trong thời gian qua.
Vì đề tài liên quan tới nhiều lĩnh vực mới với kiến thức rất rộng, bản thân tôi
phải tham khảo rất nhiều tài liệu và các bài báo quốc tế. Mặc dù đã cố gắng, song do
điều kiện về thời gian và kinh nghiệm thực tế còn nhiều hạn chế nên không thể
tránh khỏi thiếu sót (nhất là trong quá trình biên tập và dịch tài liệu thành tiếng
Việt). Vì vậy, tôi rất mong nhận được sự đóng góp ý kiến của các thầy cô cũng như
Nội dung chính của luận văn này tập trung vào nghiên cứu việc xây dựng nên
phương pháp để giải quyết các bài toán điều khiển lưu lượng thông minh trên mạng
viễn thông hiện tại. Nhằm giải quyết được vấn đề tránh tắc nghẽn và tối ưu hoá thời
gian truyền nhận các gói dữ liệu thông qua các router trên mạng. Nội dung chính
của luận văn là ứng dụng giải thuật di truyền mờ vào bài toán AQM trên mạng hiện
nay, cấu trúc luận văn bao gồm các chương sau:
Chƣơng 1: Các kiến thức tổng quan.
Chƣơng 2: Bài toán quản lý hàng đợi tích cực trong viễn thông.
Chƣơng 3: Ứng dụng giải thuật di truyền mờ cho bài toán quản lý hàng đợi
tích cực trong viễn thông.
Cuối cùng là kết luận và hướng phát triển của đề tài. Trang v
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
MỤC LỤC
Trang
Thuyết minh luận văn thạc sỹ kỹ thuật i
Lời cam đoan ii
Lời cảm ơn iii
Lời nói đầu iv
Mục lục v
Danh mục các bảng biểu viii
Danh mục các hình vẽ ix
Các thuật ngữ viết tắt xi
CHƢƠNG 1: CÁC KIẾN THỨC TỔNG QUAN
1.1 Giới thiệu 1
1.1.1 Điều khiển tắc nghẽn trên mạng internet 1
1.1.2 Chất lượng dịch vụ trên internet 2
2.2 Kỹ thuật chống mất gói trong các mạng TCP/IP tắc nghẽn 26
2.2.1 Giới thiệu 26
2.2.2 Quản lý hàng đợi tích cực (AQM) 26
2.2.2.1 Lưu lượng tải và phát hiện sớm 27
2.2.2.2 Tránh thông báo tắc nghẽn xác định 30
2.2.2.3 RED thích nghi (ARED) 31
2.2.2.4 Độ nhạy RTT 34
2.2.2.5 Sự đánh giá 36
2.2.2.6 Sử dụng gói mất để thông báo tắc nghẽn 38
2.2.3 Điều khiển tắc nghẽn máy chủ cuối 41
2.2.3.1 Điều chỉnh tốc độ truyền tối thiểu 41
2.2.3.2 Điều chỉnh tăng tuyến tính 44
2.2.4 Điều chỉnh hiệu suất tối ưu 48
2.2.5 Kết luận và công việc tương lai 50
2.3 BLUE phương pháp mới cho AQM 51
2.3.1 Giới thiệu 51
2.3.2 Sự hạn chế của RED 52
2.3.3 Blue 54
2.3.3.1 Thuật toán Blue 55
2.3.3.3 Tìm hiểu về Blue 56
2.3.3.4 Hiệu quả của ECN timeouts 59
2.3.3.5 Sự đánh giá 61
2.3.4 Blue cân bằng ngẫu nhiên (SFB) 63
2.3.4.1 Thuật toán SFB 63
2.3.4.2 Sự đánh giá 66
2.3.4.3 Sự hạn chế của SFB 68
2.3.4.4 SFB với hàm hash động 71
Trang vii
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Trang viii
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
DANH MỤC CÁC BẢNG BIỂU
Bảng 1.1 Kết quả tính toán cho các nhiễm sắc thể 15
Bảng 1.2 Quần thể mới 16
Bảng 1.3 So sánh đặc điểm giữa logic mờ và giải thuật di truyền 19
Bảng 1.4 Phân loại việc kết hợp giữa các hệ thống di truyền mờ 20
Bảng 1.5 Các ứng dụng kỹ thuật FL-GA cho hệ thống điều khiển 21
Bảng 1.6 Ví dụ về hệ thống FL-GA ứng dụng giải bài toán phân tích dữ liệu 21
Bảng 1.7 Những ứng dụng của hệ thống kết hợp di truyền mờ 23
Bảng 2.1 Tỷ lệ mất gói của SFB theo Mbs (1 luồng không đáp ứng) 66
Bảng 2.2 Tỷ lệ mất của SFB (một luồng không đáp ứng, một luồng dao động) 73
Bảng 3.1 Cơ sở luật – các luật ngôn ngữ 80
Hình 2.17 Mạng ví dụ 40
Hình 2.18 Thuật toán SUBTCP 42
Hình 2.19 Topo mạng 42
Hình 2.20 Tốc độ gửi tối thiểu và hiệu suất của TCP 43
Hình 2.21 Đồ thị hàng đợi để giảm kích thước segment và tăng kích thước cửa sổ 44
Hình 2.22 Thuật toán SUBTCP dựa trên băng thông 46
Hình 2.23 Thuật toán dựa trên băng thông SUBTCP 46
Hình 2.24 Hiệu suất của thuật toán tăng tuyến tính đã sửa đổi 47
Hình 2.25 Hiệu suất tuyến tính phụ SUBTCP 48
Hình 2.26 Hiệu suất thông qua lưu lượng lải 49
Hình 2.27 So sánh hiệu suất 50
Hình 2.28 Sự mở rộng cho ARED 51
Hình 2.29 Ví dụ về RED 53
Hình 2.30 Thuật toán Blue 55
Hình 2.31 Topo mạng 56
Hình 2.32 Đồ thị chiều dài hàng đợi của RED và BLUE 57
Hình 2.33 Hành vi đánh dấu của RED 58
Hình 2.34 Hành vi đánh dấu của BLUE (p
m
) 59
Trang x
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Hình 2.35 Đồ thị chiều dài hàng đợi của RED và BLUE với ECN timeouts 60
Hình 2.36 Hành vi đánh dấu với ECN timeouts 60
Hình 2.37 Hiệu suất của RED và BLUE với ECN timeouts 61
Hình 2.38 Thí nghiệm mô phỏng 62
Hình 2.39 Hiệu suất quản lý hàng đợi 62
Hình 2.40 Thuật toán SFB 64
Hình 2.41 Ví dụ về SFB 65
Hình 3.21 Tỷ lệ mất gói của RED, BLUE và Fuzz-GA-AQM 92
Hình 3.22 Hiệu suất quản lý hàng đợi của Red, Blue và Fuzz-GA-AQM 94
Trang xi
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
CÁC THUẬT NGỮ VIẾT TẮT
Viết tắt
Tên gốc
Giải thích
ACK
ACKnowledgments
xác nhận, báo nhận
AED
Aggressive Early Detection
Phát hiện sớm tích cực
AQM
Active Queue Management
Quản lý hàng đợi tích cực
ARED
Adaptive Random Early Detection
RED thích nghi
ARIO
Adaptive Random Early Detection
with Input/Output
RED với cổng vào ra thích nghi
Besteffort
Best-effort network
Mạng nỗ lực tốt nhất
CBQ
Class Based Queue
Exponentially Weighted Moving
Average
Trung bình dịch chuyển luỹ thừa
hàm trọng
GA
Genetic Alogrymth
Giải thuật di truyền
IETF
Internet Engineering Task Force
Nhóm đặc trách kỹ thuật Internet
InteServ
Intergrated Services
Dịch vụ tích hợp
ICN
Implicit Congestion Notification
Thông báo tắc nghẽn ẩn
IP
Internet Protocol
Giao thức Internet
IS
Intergrated Service
Dịch vụ tích hợp
ISP
Internet Service Provider
Nhà cung cấp dịch vụ Internet
LAN
Local Area Network
Mạng nội vùng
NS
Network Simulator
Chu kỳ truyền nhận
SACK
Selective ACKnowledgments
Xác nhận lựa chọn
SFB
Stochastic Fair BLUE
Blue công bằng ngẫu nhiên
SFQ
Stochastic Fair Queueing
Hàng đợi công bằng ngẫu nhiên
SUBTCP
SUBTCP
Thuật toán TCP sửa đổi
SRED
Statis RED
RED tĩnh
TCP
Transport Control Protocol
Giao thức điều khiển truyền thông
TOS
Type Of Service
Kiểu dịch vụ
UDP
User Data Protocol
Giao thức dữ liệu người sử dụng
WFQ
Weighted Fair Queue
Hàng đợi cân bằng có trọng số
WRED
Weighted RED
1.1.1 Điều khiển tắc nghẽn trên mạng internet
Sự thành công chủ yếu của TCP/IP trong thập kỷ qua là khả năng cung cấp
dịch vụ theo nhu cầu rất cao của người dùng. Lý do chính ở đây chính là cơ chế
điều khiển tắc nghẽn của TCP [57]. Ý tưởng phía sau điều khiển tắc nghẽn TCP là
để điều khiển tải mạng bởi có thể điều chỉnh tốc độ nguồn theo mức độ tắc nghẽn
trong mạng. Cụ thể hơn, nếu nguồn TCP phát hiện hay thấy gói mất dựa trên các
thông tin về các gói đã gửi, nó giảm tốc độ gửi để tránh mất gói thêm và tránh tắc
Trang 2
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
nghẽn. Nếu nguồn TCP quan sát thấy tất cả các gói dữ liệu đang được chuyển đi, nó
dần dần tăng tốc độ gửi để tận dụng tối đa khả năng của mạng. Nhờ cơ chế điều
khiển tắc nghẽn, tài nguyên mạng được chia sẻ giữa các luồng trong thời gian xảy ra
tắc nghẽn. Việc chia sẻ này cho phép các luồng với RTT (Round trip Time là thời
gian từ lúc truyền tới lúc nhận thông báo đã nhận) giống nhau đạt thông lượng như
nhau và tránh việc một luồng bị tắc nghẽn hoàn toàn. Bằng cách này, TCP có thể
giảm thiểu mất gói với hiệu quả đáng kể trong khi sử dụng mạng tối đa trong suốt
thập kỷ qua.
Gần đây, khi nhu cầu của người dùng tăng nhanh hơn khả năng nâng cấp hạ
tầng mạng của các nhà cung cấp, khả năng cung cấp dịch vụ nỗ lực tối đa (Best-
effort) của TCP bị kém đi. Đặc biệt là sự gia tăng đáng báo động liên quan đến tỷ lệ
mất gói đã được quan sát trên một số kết nối mạng [80]. Gói mất tăng dẫn đến sự
kém ổn định và hiệu quả của mạng vì nguồn và các router liên tục tạo ra và chuyển
tiếp các gói dữ liệu mà sau đó lại bị mất. Để giải quyết vấn đề tăng tỷ lệ mất gói
trong mạng Internet, nhóm đặc trách kỹ thuật Internet (Internet Engineering Task
Force - IETF) đang xem xét việc triển khai các Thông báo tắc nghẽn tường minh
(Explicit Congestion Notification - ECN) [43, 82] và Quản lý hàng đợi tích cực
(Active Queue Management - AQM) [20, 46] nhằm ngăn ngừa mất gói. Ý tưởng
phía sau ECN là cung cấp cho mạng khả năng thông báo tường minh về tắc nghẽn
của nguồn TCP và để nguồn TCP giảm tốc độ truyền của chúng nhằm đáp ứng lại
đáp ứng sự thay đổi mạng. Ngoài ra, hỗ trợ cho các dịch vụ như vậy có thể cần thêm
một lượng đáng kể trong tiêu đề gói tin trong hệ thống. Vì vậy, IETF cũng xem xét
một cách tiếp cận tiến hóa hơn để cung cấp các dịch vụ phân biệt trên Internet. Với
phương pháp này, như đã nêu do các dịch vụ phân biệt Differentiated Services
(DiffServ) làm việc theo nhóm, sử dụng bit kiểu dịch vụ (Type of Service- ToS)
trong tiêu đề IP [16, 31, 81, 86] nhằm cung cấp dịch vụ chất lượng khác nhau cho
các ứng dụng. Mục tiêu của DiffServ là xác định một tập tối thiểu các khối có thể
được sử dụng để xây dựng các dịch vụ cho các ứng dụng đang phát triển.
1.1.3 Cấu trúc luận văn
Nội dung chính của luận văn này tập trung vào nghiên cứu việc xây dựng
phương pháp để giải quyết các bài toán điều khiển lưu lượng thông minh trên mạng
viễn thông hiện tại. Nhằm giải quyết được vấn đề tránh tắc nghẽn và tối ưu hoá thời
gian truyền nhận các gói dữ liệu thông qua các router trên mạng. Nội dung chính
của luận văn là ứng dụng giải thuật di truyền mờ cho bài toán AQM trên mạng viễn
thông hiện nay, cấu trúc luận văn bao gồm các chương sau:
Chƣơng 1: Trình bày về các kiến thức tổng quan liên quan tới các lĩnh vực mà
đề tài cần sử dụng bao gồm: TCP và AQM, giải thuật di truyền. Mô hình kết hợp
giữa giải thuật di truyền và logic mờ nhằm giải quyết một số bài toán phức tạp.
Đánh giá được ưu điểm nổi trội của giải thuật di truyền mờ nhằm tối ưu hoá luật mờ
và vét cạn các lời giải.
Trang 4
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
Chƣơng 2: Tìm hiểu về bài toán quản lý hàng đợi tích cực (AQM) trong mạng
viễn thông hiện nay. Những phương pháp và thuật toán đã và đang được sử dụng,
đánh giá được ưu nhược điểm của từng phương pháp. Minh chứng về những điểm
yếu trong AQM hiện nay. Đề xuất một phương pháp sửa đổi thuật toán điều khiển
tắc nghẽn nhằm đạt kết quả tốt hơn.
Chƣơng 3: Tiếp tục giải quyết bài toán trong chương 2 bằng việc sử dụng mô
hình mới kết hợp giữa giải thuật di truyền và logic mờ, đưa ra đánh giá thông qua
truyền tới 2 segment dữ liệu mới. Khi mỗi ACK của các segment này được nhận,
cwnd được tăng thành 4. Việc tăng này gần với hàm mũ, cho thấy số lượng các gói
tin được đưa vào mạng tăng lên khá nhanh. Bên gửi giữ nguyên trạng thái khởi đầu
chậm tới khi kích thước của cwnd đạt tới một mức ngưỡng (ssthresh), khi đó sẽ kích
hoạt TCP chuyển sang trạng thái tránh tắc nghẽn, hoặc cho tới khi phát hiện gói mất.
Giải thuật tránh tắc nghẽn (congestion avoidance)
Giai đoạn tránh tắc nghẽn được sử dụng khi kích thước cửa sổ cwnd bằng
hoặc lớn hơn ngưỡng ssthresh để thăm dò khả năng của mạng. Khi giá trị cwnd và
ssthresh bằng nhau, bên gửi có thể sử dụng khởi đầu chậm hoặc tránh tắc nghẽn.
Trong một vài biến thể TCP, ssthresh có thể có giá trị cao, hoặc được cấu hình bằng
với kích thước cửa sổ do bên nhận thông báo. Trong pha tránh tắc nghẽn, kích
thước cửa sổ cwnd tăng lên tuyến tính và chậm hơn so với trong pha slow start, do
cwnd được tăng lên một segment cho mỗi RTT (chu kỳ truyền nhận (round-trip
time), tức là đối với mỗi ACK không bị lặp, cwnd được tăng thêm 1/cwnd. Việc
tăng này diễn ra cho đến khi cwnd đạt tới kích thước cửa sổ mà bên nhận thông báo,
hoặc tới khi xảy ra mất gói. Khoảng thời gian để cwnd đạt được giá trị cửa sổ mà
bên nhận thông báo tính theo công thức: slowstart_time=RTT x log
2
W
S
, trong đó W
S
là kích thước cửa sổ bên nhận thông báo tính bằng số segment.
Giải thuật truyền lại nhanh (Fast Retransmit)
Một segment được truyền lại khi quá thời gian chờ gửi lại (timeout là khoảng
thời gian chờ gói tin hồi đáp). TCP có thể truyền lại segment bị mất nhanh hơn bằng
cách sử dụng giải thuật truyền lại nhanh, dựa trên nguyên tắc khuyến cáo bên nhận
nên gửi ngay một ACK lặp lại khi nhận được một gói dữ liệu sai thứ tự. Khi nhận
được 3 ACK lặp lại, giải thuật truyền lại nhanh sẽ lập tức truyền lại segment bị mất
ACK đối với dữ liệu được truyền thành công, bên gửi tăng tốc độ truyền nhờ tăng
kích thước cửa sổ tắc nghẽn. Tại một số thời điểm, tốc độ gửi các gói tin TCP cuối
cùng vượt quá khả năng của mạng. Khi điều này xảy ra, hàng đợi trong các router
mạng tăng lên và tràn hàng đợi, dẫn đến mất các gói. TCP giả định rằng tất cả các
gói dữ liệu bị mất là do tắc nghẽn và nó giảm cửa sổ tắc nghẽn khi phát hiện gói mất.
Thuật toán điều khiển tắc nghẽn của TCP là khá đơn giản. Khi một kết nối khởi
động, nó cố gắng đạt tới tốc độ truyền nhanh chóng bằng cách gia tăng theo cấp số
mũ của cửa sổ tắc nghẽn cho đến khi nó đạt tới một giá trị ngưỡng cụ thể
(SSTHRESH).
Giai đoạn này được gọi là khởi đầu chậm (Slow-start) và cho phép các nguồn
gửi tăng gấp đôi cửa sổ tắc nghẽn, và đó là tốc độ gửi đi sau mỗi RTT. Để tránh mất
gói quá nhiều do tốc độ gửi tăng theo cấp số nhân, TCP bên gửi thường sử dụng
phương pháp gọi là các thuật toán tránh tắc nghẽn [57, 89], sự sửa đổi TCP lần đầu
tiên triển khai trên Reno biến thể của TCP. Trong thuật toán này, TCP sử dụng giá
trị SSTHRESH gần bằng kích thước cửa sổ mà mạng có thể hỗ trợ. Khi kích thước
Trang 7
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
cửa sổ vượt quá ngưỡng này, TCP bước vào giai đoạn tránh tắc nghẽn. Trong giai
đoạn này, cửa sổ được tăng với tốc độ chậm hơn một segment sau mỗi RTT. Khi tải
tăng trên khả năng của mạng, các gói tin cuối cùng bị mất. Một trong những cách
thức mà TCP phát hiện một gói mất là thông qua việc nhận một số ACK lặp tích lũy
từ bên nhận [58]. Khi nhận được một số lượng nhất định các ACK lặp, TCP suy
luận rằng đã xảy ra mất một gói và ngay lập tức giảm tốc độ truyền xuống một nửa
do giảm một nửa cửa sổ tắc nghẽn và thiết lập SSTHRESH với giá trị mới của cửa
sổ tắc nghẽn. Các cơ chế này được gọi là truyền lại nhanh (fast retransmit) và phục
hồi nhanh (fast recovery).
Khi tắc nghẽn là đủ nghiêm trọng việc mất gói không thể được suy ra theo
cách như vậy, TCP hoạt động dựa trên cơ chế truyền lại timeout để kích hoạt truyền
lại gói tiếp theo cho các gói đã mất. Khi việc truyền lại timeout xảy ra, TCP giảm
bên gửi. Rất nhiều đề xuất sửa đổi TCP tập trung vào phục hồi từ tắc nghẽn. Nhịp
xác nhận (ACK-clocked), thường được gửi chỉ sau khi nhận được ACK đối với các
gói tin được truyền trước đó. Khi các gói dữ liệu thiếu hoặc đang gửi ACK để trả lời
phía TCP gửi, việc truyền lại timeout phải xảy ra trước khi nguồn TCP có thể gửi
lại. Bởi vì Reno biến thể của TCP giữ nguyên cửa sổ trong khi phục hồi từ tắc
nghẽn, nó thường gây ra sự truyền lại timeout tới khi nguồn không gửi gói tin ACK
trong giai đoạn phục hồi. Để giải quyết vấn đề này, một thí nghiệm đơn giản được
thực hiện. Khi bên gửi TCP nhận được bất kỳ loại ACK nào, là dấu hiệu cho biết
một gói dữ liệu đã bị mất và do đó cho phép bên gửi TCP gửi thêm một gói bổ sung
mà không gây tắc nghẽn hơn.
Sự sửa đổi này cho phép TCP duy trì ACK-clocking và ngăn không cần thiết
truyền lại timeouts. Cả FACK [70] và NewReno [44, 53] sửa đổi sử dụng cách thức
này để cải thiện hiệu năng TCP. Cuối cùng, những thay đổi cơ bản hơn cho các
thuật toán điều khiển tắc nghẽn TCP đã được đề xuất. Trong phiên bản hiện tại của
TCP, cửa sổ tắc nghẽn giống như mô hình răng cưa, tại đây cửa sổ tắc nghẽn liên
tục tăng cho đến khi mất gói xảy ra. Trong khi điều này cho phép TCP thăm dò
băng thông bổ sung, như vậy hành vi cuối cùng gây ra mất gói. Ý tưởng phía sau
Tri-S [94, 95] và Vegas [23] sửa đổi là thay đổi giai đoạn tránh tắc nghẽn vì thế nó
chỉ thực hiện tăng tuyến tính khi mạng không bị tắc nghẽn. Trong cả hai thuật toán,
nếu RTT biểu thị sự tăng độ trễ do hàng đợi đang tăng lên trong mạng, các nguồn
TCP sẽ giảm hoặc sửa kích thước cửa sổ tắc nghẽn thay vì tăng nó. Các cơ chế này,
có khả năng cải thiện tỷ lệ mất gói trong Internet, nó không tường minh như thực
Trang 9
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
hiện từng phương pháp mỗi khi tắc nghẽn kéo dài. Ngoài ra, bằng cách sửa đổi
thuật toán tăng-tuyến tính/giảm-luỹ thừa của TCP, các sửa đổi không thể đảm bảo
việc chia sẻ công bằng giữa các kết nối được ghép kênh trên tuyến [24, 61].
Ngoại trừ Tri-S và Vegas, một trong những vấn đề với thuật toán điều khiển
tắc nghẽn TCP trên các mạng hiện nay là nguồn gửi giảm tốc độ truyền của chúng
3-bit flags
13-bit fragment offset
8-bit time to live (TTL)
8-bit protocol
16-bit header checksum
32-bit source IP address
32-bit destination IP address
IP header
16-bit source port number
16-bit destination port number
32-bit sequence number
32-bit acknowledgment number
4-bit
header
length
4-bit
Reserved
C
W
R
ECN Echo
U
R
G
A
C
K
P
S
H
Kết hợp với ECN, IETF cũng ủng hộ việc sử dụng AQM. Ý tưởng phía sau
AQM là để phát hiện sớm tắc nghẽn và để chuyển tải thông báo tắc nghẽn đến máy
chủ cuối, cho phép chúng giảm tốc độ truyền của mình trước khi tràn hàng đợi và
mất gói xảy ra. Một dạng AQM được IETF đề nghị để triển khai trong mạng là nhận
biết ngẫu nhiên sớm RED (Random Early Detection) [20, 46]. Red duy trì một trung
bình dịch chuyển luỹ thừa hàm trọng (Exponentially Weighted Moving Average -
EWMA) của chiều dài hàng đợi mà nó sử dụng để phát hiện tắc nghẽn. Red phát
hiện sự tăng chiều dài hàng đợi trung bình và sử dụng nó để xác định có hay không
mất hoặc đánh dấu ECN cho mỗi gói.
Hình 1.3 Các hành vi mất gói/đánh dấu gói của Red
Cụ thể hơn, sơ đồ hình 1.3 xác suất mất gói/đánh dấu của Red như là một hàm
của chiều dài hàng đợi trung bình. Như hình vẽ cho thấy, khi chiều dài hàng đợi
trung bình vượt quá ngưỡng tối thiểu (min
th
), các gói bị mất hoặc đánh dấu ngẫu
nhiên bằng một xác suất cho trước. Một kết nối nhận được thông báo tắc nghẽn
trong một form ECN-mark, nó giảm cửa sổ tắc nghẽn đi một nửa nếu phát hiện một
gói mất. Xác suất một gói đến tại hàng đợi RED phụ thuộc vào gói mất hay đánh
Trang 11
Số hóa bởi Trung tâm Học liệu – Đại học Thái Nguyên http://www.lrc-tnu.edu.vn
dấu, nói cách khác, chiều dài hàng đợi trung bình và thông số xác suất ban đầu
(max
p
). Như hình 1.3 cho thấy, cách tính xác suất mất gói/đánh dấu là một hàm
tuyến tính của chiều dài hàng đợi trung bình. Xác suất là 0 khi chiều dài hàng đợi
trung bình là nhỏ hơn hoặc bằng min
th
và tăng tuyến tính tới max
cấp một nền tảng vững chắc cho việc cung cấp các lớp dịch vụ khác nhau trên
Internet, nó có nhiệm vụ quan trọng nhằm thay đổi cơ sở hạ tầng mạng Internet. Vì
vậy, một cách tiếp cận tiến hóa hơn để cung cấp các dịch vụ phân biệt trong Internet
bằng cách sử dụng các bit kiểu dịch vụ (ToS) trong tiêu đề IP [16, 31, 81, 86] gần
đây đã thu hút được rất nhiều sự quan tâm.
Copyright: Tài liệu đại học ©