1

MỤC LỤC

DANH MỤC TỪ, THUẬT NGỮ VIẾT TẮT
Từ viết tắt

Tiếng Anh

Tiếng Việt
Đường truyền thuê bao số bất
đồng bộ

API

Asymmetric Digital Subcriber
Line
Additive Increase Additive
Decrease
Additive Increase Multiplicate
Decrease
Application Program Interface

AGC

Access Gateway Controller

Bộ điều khiển cổng truy cập

ARWND


Visulization Tool

CSFQ

Core-Stateless Fair Queueing

CWND

Congestion Window

Công cụ mô phỏng tránh tắc
nghẽn
Xếp hàng bình đẳng không trạng
thái ở router lõi
Cửa sổ tắc nghẽn

EC

Efficiency Controller

Bộ điều khiển hiệu quả

ETCP

Enhanced TCP

TCP tăng cường

EWA


Mạng số tích hợp đa dịch vụ
Network
International Telecommunication
Hiệp hội viễn thông quốc tế
Union

FBA-TCP
FC
GPRS
GSM

ISDN
ITU

Từ viết tắt
MGW
MIAD
MIMD
MSS
NGN
PABX

Tiếng Anh

Giao thức Internet

Tiếng việt

Media Gateway
Multiplicate Increase Additive

3

QoS

Public Switched Telephone
Network
Quality of Service

Mạng chuyển mạch dữ liệu công
cộng
Mạng thoại chuyển mạch công
cộng
Chất lượng dịch vụ

QSR

Quick-Start Request

Yêu cầu bắt đầu nhanh

QS-TCP

TCP Quick-Start

TCP khởi đầu nhanh

RED

Random Early Detection


TCP

PSDN
PSTN

Public Switched Data Network

TTL

Telecommunications Management
Mạng giám sát viễn thông
Network
Time – To –Live
Thời gian tồn tại

UDP

User Datagram Protocol

Giao thức gói người dùng

VoIP

Voice over IP

Thoại trên IP

XCP

Explicit Control Protocol


Hình 3. 1 Hiện tượng xảy ra tắc nghẽn

28

Hình 3.2 Hiệu quả của việc điều khiển tắc nghẽn

29

Hình 3.3 Môi trường mạng hỗn tạp trong NGN

29

Hình 3.4 Hệ thống gồm n người dùng chia sẻ 1 mạng

34

Hình 3.5 AIDM hội tụ đến điểm tối ưu

39

Hình 3.6 AIAD không hội tụ

39

Hình 4.1 Tổng quan về NS dưới góc độ người dùng

41

Hình 4.2 Sơ đồ thuật toán tăng giảm


RTT2

Hình 4.10 Topo mạng sử dụng trong quá trình mô phỏng

49
50


5

Hình 4.11 Hiệu quả sử dụng đường truyền cao

51

Hình 4.12 Hiệu quả vẫn bảo đảm khi 1 luồng ngừng truyền đột ngột.

52

Hình 4.13 cwnd hội tụ nhanh đến lượng chia sẻ hợp lý

52

Hình 4.14 Số gói tại hàng đợi nhỏ.

53

Hình 4.15 Biểu diễn cwnd của 2 loại lưu lượng TCP và XCP.

54

giới hạn trong khi nhu cầu truyền thông tin ngày càng tăng. Chính vì vậy hiện tượng
tắc nghẽn mạng là khó tránh khỏi. Để giải quyết vấn đề này có hai hướng giải quyết
tổng quát nhất, đó là:
•

Tăng tài nguyên của mạng (mở rộng nút mạng, tăng các tuyến truyền dẫn,

tăng băng thông của mạng…)
• Điều khiển chống tắc nghẽn mạng.
Với cách thứ nhất chi phí đầu tư lớn, làm thay đổi phần cứng của mạng và
không thể thực hiện thường xuyên được.
Cách thứ hai sử dụng các thuật toán, các giao thức để điều khiển chống tắc
nghẽn mạng. Cách này đầu tư nhỏ, không ảnh hưởng đến phần cứng của mạng và


7

rất mềm dẻo linh hoạt và đây cũng là phương án khả thi, thích hợp với điều kiện ở
Việt Nam.
Sau một thời gian nghiên cứu và tìm hiểu, được sự giúp đỡ và hướng dẫn của
thầy giáo Ts. Nguyễn Chiến Trinh em đã nắm bắt được những kiến thức cơ bản về
mạng NGN nói chung và vấn đề tắc nghẽn trong NGN nói riêng.Đến nay, em đã
hoàn thành đồ án với đề tài “Nghiên cứu các phương pháp điều khiển tắc nghẽn
trong mạng NGN”. Nội dung của bài được chia làm 4 phần chính:
Chương 1 : Tổng quan về tắc nghẽn trong mạng
Chương 2 : Các phương pháp điều khiển tắc nghẽn
Chương 3 : Phương pháp điều khiển tắc nghẽn trong mạng NGN
Chương 4: Mô phỏng phương pháp điều khiển tắc nghẽn
Do đây là một đề tài phức tạp và trình độ hiểu biết còn nhiều hạn chế nên bài
làm của em không tránh khỏi những sai sót. Em rất mong nhận được sự chỉ dẫn và

dịch vụ mới : dữ liệu, âm thanh và hình ảnh được tích hợp truyền trên 1 mạng duy
nhất gây ra tắc nghẽn tại các đường truyền dẫn băng thông nhỏ.
5. Lưu lượng lớn, thay đổi đột biến và biến đổi động.


9

6. Tính biến động của mạng, topo mạng: Đây là một đặc tính mới của mạng
NGN so với mạng truyền thống. Các nút mạng có thể dịch chuyển làm topo mạng
thay đổi gây ra những biến đổi về phân chia lưu lượng trên mạng.

1.1.2 Nguyên lý chung của điều khiển tắc nghẽn
Điểm gãy

(knee)

Điểm vách
(cliff)

Thông lượng
(Throughput)

Lưu lượng đầu vào (offered load)

Hình 1.1 Quá trình diễn ra tắc nghẽn

Quá tải làm thông lượng (throughput) suy biến như được chỉ ra trên hình 1.4.
Đồ thị biểu diễn mối quan hệ giữa thông lượng với lưu lượng đưa vào (offered
load). Ở mức lưu lượng đưa vào nhỏ (phía trái của điểm gãy - Knee), thông lượng
tăng tuyến tính với lưu lượng đưa vào. Đó là lúc băng thông chưa sử dụng hết.

•

Kiểm soát (Policing): Kiểm tra kết nối nào vi phạm các mô tả về lưu lượng
để đưa ra xử lý trừng phạt bằng cách:
1) Xóa các gói vi phạm mô tả
2) Gán cho chúng quyền ưu tiên thấp hơn

•

Điều khiển luồng lưu lượng (Flow control) là những hoạt động của mạng để
tránh xảy ra tắc nghẽn. Ngoài ra điều khiển lưu lượng còn nhằm sử dụng tối ưu tài
nguyên mạng để đạt được một hiệu suất mạng thực sự.

1.2.2 Phân loại
Theo các đặc điểm chung nêu trên, các phương pháp điều khiển tắc nghẽn có
thể được phân loại như sau:


11

Điều khiển tắc nghẽn vòng hở (Open-loop congestion control) là sự kết hợp
của điều khiển tiếp nhận, kiểm soát và nguyên lý thùng rò (leaky bucket). Trong đó
không có thông tin phản hồi từ mạng hoặc phía nhận.
Điều khiển chống tắc nghẽn vòng kín (Close-loop congestion control) là dựa
trên trạng thái của mạng với sự giám sát tắc nghẽn và điều khiển lưu lượng dựa trên
thông tin phản hồi. Trong đó, thông tin phản hồi có thể là:
•

Phản hồi ẩn (implicit feedback) nguồn phát sử dụng thời gian chờ (time-out)
để xác định liệu có xảy ra tắc nghẽn hay không. Ví dụ: điều khiển chống tắc nghẽn

X (t ) = ∑ xi (t )

, thì tính hiệu quả được xác định bởi tỉ số:
η=

X (t )
X goal

(1.1)

( X (t ) < X )

( X (t ) > X )
goal

Quá tải

goal

hay dưới mức tải

đều không mong muốn

và được coi là không có hiệu quả như nhau. Thuật toán hiệu quả khi η tiến gần tới
1, nghĩa là X(t) tiến gần tới Xgoal.
Chú ý, tính hiệu quả chỉ có liên quan đến tổng lượng phân phối và do đó 2
lượng phân phối khác nhau có thể cả hai đều hiệu quả miễn là tổng lượng phân phối
là gần đến “goal”. Sự phân bố của tổng lượng phân phối giữa các người dùng được
đo bởi chỉ tiêu bình đẳng.



bằng nhau)

có tính bình đẳng là 1 và lượng phân phối không bình đẳng (với tất cả các tài
nguyên chỉ dùng cho một người) có tính bình đẳng là 1/n đạt đến 0 khi n tiến tới vô
cùng.


13

Tính bình đẳng độc lập vào thang đo, tức là, đơn vị đo là không quan

•

trọng.
Tính bình đẳng là hàm liên tục. Một vài sự thay đổi nhỏ trong lượng phân

•

bố cũng thấy trong tính bình đẳng.
Nếu chỉ có k trong n người dùng chia sẻ tài nguyên như nhau với (n - k)

•

người dùng không nhận tài nguyên nào, thì tính bình đẳng là k/n.
Ta có các đặc tính khác:
Thuật toán bình đẳng khi F tiến gần tới 1. Tuy nhiên, chỉ số này chỉ biểu diễn
tính bình đẳng giữa các người dùng mạng nói chung mà chưa thể hiện được bản
chất đa dịch vụ trong mạng thế hệ mới. Trong mạng NGN sẽ có nhiều lớp dịch vụ
khác nhau, sử dụng nhiều hệ giao thức vận chuyển khác nhau. Vì vậy, cần thiết phải


•

Thời gian cần thiết để thuật toán hội tụ đến Xgoal .

•

Biên độ của dao động xung quanh giá trị Xgoal nhỏ dần.
Thời gian để đạt được trạng thái cân bằng (equilibrium) xác định độ nhạy

(responsiveness) và độ dao động xác định độ mịn (smoothness) của phương pháp
điều khiển. Một cách lý tưởng, chúng ta muốn thời gian cũng như sự dao động phải
nhỏ. Do đó, điều khiển với thời gian nhỏ và biên độ nhỏ của dao động gọi là nhạy
hơn và mịn hơn, như trong hình 1.5.

1.3.4 Thời gian đáp ứng nhanh (Small response time)
Thuật toán phải nhanh chóng phát hiện được tắc nghẽn và thời gian kể từ khi
phát hiện tắc nghẽn đến khi có tác động của điều khiển chống tắc nghẽn phải càng
nhanh càng tốt: Tresp ≤ Tgoal - trong đó Tgoal là cơ sở để so sánh các thuật toán điều
khiển.
Độ nhạy

“Goal”
Độ mịn

Tổng lưu lượng mạng

Thời gian

Hình 1.2 Độ nhạy (responsiveness) và độ mịn (smoothness).

tải thông qua bit phản hồi nhị phân. Thông tin khác như X goal và số lượng người
dùng cùng chia sẻ nguồn tài nguyên được giả thiết là không được biết bởi người
dùng. Điều này hạn chế phương pháp khả thi.
Như vậy, mô hình có thể xây dựng để đánh giá các phương pháp điều khiển
chống tắc nghẽn cho mạng NGN có thể được thiết kế dựa trên sáu tiêu chí cơ bản
nêu trên.


16

Kết luận chương
Hiện tượng tắc nghẽn xảy ra trong mạng là vấn đề khó tránh khỏi, do đó điều
khiển tắc nghẽn ngày càng trở nên cấp thiết. Chương 1 đã nêu tổng quan về nguyên
lý, phân loại các phương pháp điều khiển tắc nghẽn, tiêu chí đánh giá những
phương pháp điều khiển.


17

CHƯƠNG 2
CÁC PHƯƠNG PHÁP ĐIỀU KHIỂN TẮC NGHẼN
Trong chương này, chúng ta sẽ hệ thống hóa lại một số phương pháp điều
khiển tắc nghẽn điển hình nhất, phân tích đánh giá chúng dựa trên cơ sở những
tiêu chí đã đề xuất trong chương 1. Đó là các phương pháp điều khiển tắc nghẽn
truyền thống như DECbit, và một vài phương pháp mới như EWA, ETCP, FBATCP, QS- TCP để cải thiện hiệu suất hoạt động mạng. Trong đó đặc biệt đi sâu vào
phương pháp điều khiển tắc nghẽn sử dụng TCP phổ biến hiện nay (đặc biệt là
trong mạng Internet) và XCP là ứng cử viên cho mạng dựa trên cơ sở IP sau này.

2.1 Một số phương pháp điều khiển tắc nghẽn truyền thống
2.1.1 DECbit

gần nhất. Ví dụ, giả sử phía nhận nhận gói từ 1 đến 5, và gói 6 bị mất. Khi phía
nhận nhận gói 7, nó gửi dupack cho gói 5. Phía gửi TCP xét các sự tới của 3 bản sao
phúc đáp (3 dupack) như dấu hiệu của 1 gói mất.
Kết nối TCP qua 2 pha: khởi đầu chậm và pha AIMD. Hình 2.1 cho ta thấy
quỹ đạo điển hình của cửa sổ chống tắc nghẽn.


Khởi đầu chậm: TCP đi vào mô hình khởi đầu chậm khi bắt đầu kết nối.
Trong suốt quá trình khởi đầu chậm, phía gửi tăng tốc độ gửi theo hàm mũ. Cụ thể,
khi bắt đầu khởi đầu chậm cửa sổ tắc nghẽn thiết lập là 1 đoạn, là MSS khởi tạo bởi
phía gửi trong suốt giai đoạn thiết lập kết nối. Do đó, phía gửi gửi 1 đoạn và đợi cho
tới khi phía nhận xác nhận nó. Một khi ACK đến phía gửi, phía gửi tăng cửa sổ
chống tắc nghẽn của nó bởi 1, gửi 2 đoạn, và đợi ACK tương ứng. Mỗi khi ack đến,
phía gửi có thể gửi 2 đoạn, 4 đoạn, ... gấp đôi lên dẫn đến tăng theo hàm mũ của cửa


19

sổ chống tắc nghẽn. TCP thoát khỏi khởi đầu chậm khi đoạn bị mất. Khi đó phía
gửi giảm cửa sổ tắc nghẽn đi 1 nửa và đi vào giai đoạn AIMD.

Hình 2.1 Cửa sổ tắc nghẽn


AIMD: Trong mô hình này, miễn là không có đoạn nào bị mất, phía gửi TCP
tăng cửa sổ tắc nghẽn của nó bởi 1 MSS mỗi RTT. Khi gói bị mất, TCP giảm cửa sổ
tắc nghẽn đi một nửa. Như kết quả, thông lượng biểu thị 1 dãy tăng cộng theo sau
bởi giảm nhân. Trạng thái này thường được xem như “TCP sawtooth” hình 2.1.
Điều khiển chống tắc nghẽn trong TCP có những nhược điểm cơ bản là:


Sau mỗi khoảng đo i với thời gian tồn tại không đổi phụ thuộc vào băng
thông của tuyến mà router có khả năng EWA được nối, chẳng hạn, 10ms, router
với khả năng EWA đo độ dài hàng đợi hiện thời của nó Q i và tính toán độ dài hàng

trung bình hiện thời

Q i Qi , Q i

.

và độ dài hàng trung bình trước đó

Qi −1

được dùng

để tính toán cửa sổ gửi mới cho mỗi kết nối TCP đi qua router:
Cửa sổ gửi

= max{ MSS , α . log 2 ( B − Qi ).MSS }

(2.1)

Trong đó, B là độ dài hàng lớn nhất trong router (tức là, tại cùng 1 thời điểm
nhiều nhất B+1 gói có thể lưu trữ và được chuyển đi trong router), MSS là kích cỡ
đoạn của tất cả các kết nối TCP đi qua router, và

α

là hệ số động được tính toán như


Qi

>

Qi

(2.2)

với
Qi =

127
1
Q i −1 +
Qi
128
128

Giá trị khởi tạo của hệ số sử dụng
cộng) và

ω down

α

(2.3)
ωup

được thiết lập là 1, tham số

lớn của các điều kiện tải.
Chính vì hạn chế đó EWA mờ (FEWA – Fuzzy EWA) đã phát triển, khác
với EWA cũ chủ yếu ở việc tính toán α. FEWA sử dụng một bộ điều khiển mờ để
tính α dựa theo giá trị hiện tại và một giá trị gần nhất của bộ đệm bộ định tuyến. Với
các thay đổi này trong việc tính toán phản hồi bên trong bộ định tuyến, hiệu suất từ
đầu cuối đến đầu cuối có thể đạt được lớn hơn so với EWA.

2.2.2 ETCP (Enhanced TCP)
Ý tưởng của ETCP [5] là sử dụng phản hồi FEWA (dựa trên sự điều khiển
thích ứng lưu lượng-AWND) để tính cửa sổ gửi mới (SWND). ETCP phía gửi
không thực hiện chu trình bắt đầu chậm (slow start) và tránh tắc nghẽn (congestion
avoidance), mà bắt đầu với 1 cửa sổ gửi khởi tạo và cập nhật cửa sổ gửi theo các
cách sau:
- Nếu cửa sổ gửi hiện tại lớn hơn cửa sổ điều khiển lưu lượng thì cửa sổ gửi
mới được thiết lập bằng cửa sổ điều khiển lưu lượng:

SWND ← AWND

- Nếu cửa sổ gửi hiện tại nhỏ hơn cửa sổ điều khiển lưu lượng thì cửa sổ gửi
được tính như sau:

SWND ← SWND.( AWND / SWND )

1 / SWND

Với tính toán này cửa sổ của phía gửi ETCP được tăng theo hàm mũ để tiệm
cận với cửa sổ điều khiển lưu lượng. Với các thay đổi nhỏ này có thể thu được sự
cải thiện đáng kể về khả năng thực hiện.

2.2.3 XCP (Explicit Control Protocol)


trong mào đầu có thể tính toán như sau:
H _ feedback = ( γ .rtt − cwnd ) /
số gói trong cửa sổ tắc nghẽn

(2.5)

Trong gói đầu tiên của kết nối XCP, H_feedback được khởi tạo bằng 0, khi
XCP phía gửi có RTT ước lượng hiện thời không hợp lệ trong đường dẫn.
XCP phía nhận sao chép mào đầu chống tắc nghẽn của gói dữ liệu đến sang
xác nhận ACK và gửi xác nhận bao gồm mào đầu chống tắc nghẽn đến XCP phía
gửi. Sau khi xác nhận ACK đến nơi, XCP phía gửi sửa lại cửa sổ chống tắc nghẽn
mới theo phản hồi router chứa trong mào đầu chống tắc nghẽn:


24

cwnd = max{cwnd + H _ feedback , s}

(2.6)

với s là kích cỡ gói.

2.2.3.2 Bộ điều khiển chống tắc nghẽn.
Như đã đề cập, bộ điều khiển chống tắc nghẽn trong router có khả năng XCP
được chia thành điều khiển hiệu quả (EC) và điều khiển bình đẳng (FC) [8]. Nhiệm
vụ của bộ điều khiển hiệu quả là tận dụng kết nối lớn nhất, tốc độ mất gói nhỏ nhất
và hàng của đường dẫn ổn định. Chỉ đề cập đến EC khi lưu lượng đường truyền ổn
định và không quan tâm sự bình đẳng giữa các luồng có lưu lượng ổn định. Đây là
nhiệm vụ của bộ điều khiển bình đẳng. Dùng thông tin phản hồi chống tắc nghẽn

được tính trong mỗi khoảng điều khiển:
φ = α .d .S − β .Q

(2.7)

Với d là RTT ước lượng trung bình cho kết nối, S là băng thông dự trữ (spare
bandwidth) của đường truyền được định nghĩa là hiệu số giữa tốc độ lưu lượng vào
và dung lượng đường truyền. Và Q là kích cỡ hàng ổn định của đường truyền (tính
theo bytes) với kích cỡ hàng không tiêu hao trong thời gian trễ truyền (đi và về). Q
được ước tính như là giá trị nhỏ nhất trong tất cả kích cỡ hàng bởi vài gói. α và β là
tham số hằng có giá trị lần lượt là
tắc nghẽn tổng

φ

α = 0 .4

và

β = 0.226

trong [6]. Phản hồi chống

phải tỉ lệ với S, bởi nếu đường truyền sử dụng khôg đúng mức

(S>0) hay tắc nghẽn (S