Bài giảng Cơ sở truyền số liệu - Chương 7: Điều khiển luồng và chống tắc nghẽn

Điều khiển luồng và chống tắc nghẽn
 Cơ bản
 B
 16 Kbps
 Y
 56 Kbps
 32 Kbps 16 Kbps
 X Z C
 8 Kbps
 8 Kbps
 A
 D
• Trường hợp 1.BA 7KbpsCD 0 thông tin được truyền hết
• Trường hợp 2. BA 8 kbps X hủy δ kbps. Truyền lại 
 do mất gói tại X khiến liên kết Y-X phải truyền tải 8+2 kbps 
 rồi tiếp tục tăng. Cuối cùng, các liên kết từ B đến X bị chiếm 
 hết băng thông phải khống chế tốc độ phát của B !
 Cơ bản
 B
 16 Kbps
 Y
 64 Kbps
 32 Kbps 16 Kbps
 X Z C
 8 Kbps
 8 Kbps
 A
 D
• Trường hợp 3. BA 7KbpsCD 7Kbps các gói được truyền 
 hết, mỗi liên kết truyền 7kbps tốc độ tổng cộng là 14kbps
  8
• Trường hợp 4. BA kbps CD 7 X bị tràn đệm, mất gói. 
 Truyền lại khiến các liên kết từ B và C đến X bị chiếm hết 
 băng thông. Tốc độ Y-X gấp đôi Z-Y nên X cấp đệm để X-A là 
 8kbps, X-D là 4kpbs tốc độ tổng cộng kém hơn trường 
 hợp 3 
 Cơ bản
 B
 16 Kbps
 Y
 64 Kbps
 32 Kbps 16 Kbps
 X Z C
 8 Kbps
 8 Kbps
 A
 D
• Trường hợp 4 cho thấy hai vấn đề:
 – Tốc độ tổng cộng bị giảm so với trường hợp 3 trong khi tải đưa vào 
 tăng. 
 – Luồng thông tin C-D bị thiệt. Để khắc phục, phân chia bộ đệm công 
 bằng. Điều này làm giảm hiệu quả chuyển mạch gói.
 Cơ bản
• Điều khiển luồng là chức năng không thể thiếu trong 
 các mạng thông tin
• Nếu thiếu điều khiển luồng, tắc nghẽn cục bộ tại một nút 
 mạng sẽ gây ra phát lại gói, ảnh hưởng đến các nút và liên 
 kết lân cận, có thể dẫn đến lan truyền tắc nghẽn trên toàn 
 mạng
• Phía thu sử dụng bộ đệm để lưu gói trước khi gửi lên 
 lớp trên. Do đó phải khống chế tốc độ phía phát để 
 không bị mất gói
• Các cơ chế điều khiển luồng lớp 2: HDLC, ISDN, 
 X.25, LLC
• Các cơ chế điều khiển luồng và chống tắc nghẽn ở 
 lớp truyền như TCP
 Cơ bản
g
n
ạ Lý tưởng
m
a
ủ
c
g
n Có kiểm soát
ợ
ư
l
g
n
ô Không kiểm soát
h
T
 Deadlock
 Lưu lượng thông tin
 Hai kỹ thuật điều khiển luồng
 Điều khiển luồng giữa hai nút đầu cuối (end-
 to-end): nhằm đảm bảo nút nguồn thực hiện 
 truyền thông tin không vượt quá khả năng xử 
 lý của nút đích 
 Điều khiển luồng giữa hai nút trong mạng 
 (hop-by-hop): là việc thực hiện điều khiển 
 luồng giữa hai nút liên tiếp trên đường đi từ 
 nguồn đến đích
 Hai kỹ thuật chống tắc nghẽn
 Điều khiển truy nhập mạng (network 
 access): kiểm soát và điều khiển lượng thông 
 tin có thể đi vào trong mạng
 Điều khiển cấp phát bộ đệm (buffer 
 allocation): là cơ chế thực hiện tại các nút 
 mạng nhằm đảm bảo việc sử dụng bộ đệm là 
 công bằng và tránh việc không truyền tin 
 được do bộ đệm của tất cả các nút bị tràn 
 (deadlock)
 Deadlock
 A B
 (a): Direct Deadlock
 B
 A C
 D
 (b): Indirect Deadlock
• Trong hình (a), bộ đệm của nút A đã được điền đầy bởi thông tin đến từ 
 B và ngược lại. Hệ quả là A và B không nhận được thêm thông tin từ 
 nhau 
• Trong hình (b), bộ đệm của A đầy các gói thông tin của B, bộ đệm của B
 đầy thông tin của C và bộ đệm của C đầy các thông tin của A. Việc 
 truyền tin cũng không thực hiện được do tràn bộ đệm.
 Mục đích
• Tối ưu hóa thông lượng sử dụng của mạng 
• Giảm trễ gói khi đi qua mạng 
• Đảm bảo tính công bằng cho việc trao đổi thông 
 tin trên mạng 
• Đảm bảo tránh tắc nghẽn trong mạng
 Điều khiển luồng ám chỉ cả kỹ thuật điều 
 khiển luồng và chống tắc nghẽn, trừ khi có 
 chú thích rõ ràng ! 
 Tính công bằng
• Tính công bằng là khả năng đảm bảo cho các người 
 dùng, các ứng dụng khác nhau được sử dụng tài nguyên 
 mạng với cơ hội như nhau.
• Tính công bằng về mặt băng truyền thể hiện ở khả năng 
 chia sẻ băng truyền công bằng cho tất cả người dùng hoặc 
 kết nối
 Tính công bằng băng thông
 Kết nối 1
 Kết nối 2 Kết nối 3 Kết nối 4
• Giả định các liên kết đều có dung lượng 1Mbps 
• Thông lượng của mạng sẽ đạt cực đại (bằng 3Mbps) nếu 
 các kết nối 2, 3 và 4 được sử dụng toàn bộ 1 Mbps băng 
 thông và kết nối 1 không được cung cấp lượng băng thông 
 nào cả
• Cho mỗi kết nối sử dụng 0,5Mbps băng thông. Lúc này 
 tổng thông lượng của mạng sẽ là 2Mbps.
• Nếu cung cấp lượng tài nguyên mạng (băng thông) cho tất 
 cả các kết nối là như nhau, lúc ấy các kết nối 2, 3, 4 sẽ 
 được sử dụng 0,75Mbps và kết nối 1 sử dụng 0,25 Mbps 
 (và được sử dụng trên toàn bộ đường truyền)
 Tính công bằng
• Tính công bằng về mặt bộ đệm là khả năng đảm bảo 
 việc sử dụng bộ đệm của các người dùng, các ứng dụng 
 hay kết nối là công bằng
• Xét trường hợp 4. 
 Tính công bằng: bộ đệm
 Kết nối 2
 D
 1
 10
 A B C
 Kết nối 1 1
 1
 E
• Giả sử nút mạng B có dung lượng bộ đệm hữu hạn
• Liên kết 1 (từ A đến B) có tốc độ 10Mbps, liên kết 2 (từ D 
 đến B) có tốc độ 1 Mbps.
• Nếu không có cơ chế điều khiển luồng và quản lý bộ đệm, 
 tỷ lệ sử dụng dung lượng bộ đệm tại B của hai liên kết 1 và 
 2 sẽ là 10:1 (do tốc độ thông tin đến B tương ứng là 
 10MbpsMbps) và 1
 Cơ chế điều khiển
• Điều khiển luồng áp dụng cơ cho các ứng dụng phi thời 
 gian thực (FTP, HTTP, SMTP) được kết hợp với kỹ thuật 
 ARQ (Automatic Repeat Request)
• Điều khiển luồng áp dụng cơ cho các ứng dụng thời gian 
 thực (video, audio) đi kèm theo việc khống chế tốc độ phát 
 (rate-based flow control)
 Điều khiển luồng kết hợp ARQ
• Cho ứng dụng phi thời gian thực
 – Cơ chế dừng và đợi (stop-and-wait)
 – Cơ chế phát lại gói (go-back-N) 
 – Phát lại có chọn lọc (selective repeat)
• Cho ứng dụng thời gian thực 
 – Cơ chế điều khiển luồng theo lưu lượng đầu vào (traffic policing
 1. ứng dụng yêu cầu mạng cấp băng thông end-to-end
 2. các nút mạng kiểm tra tài nguyên đường truyền, nếu đủ thì dành 
 trước
 3. kiểm soát lưu lượng đưa vào, nếu thấy vượt quá mức được cấp thì 
 các gói tin bị hủy nếu không đủ băng thông
 – Cơ chế định thời biểu gói (packet scheduling), ví dụ WFQ