TRƯỜNG ĐẠI HỌC QUỐC GIA HÀ NỘI
KHOA CÔNG NGHỆ
____
000
_____
PHẠM VÀN THUƠNG
NGUYÊN TẮC VÀ HIỆU SUẤT
■
CỦA MỘT SỐ C ơ CHÊ' ĐIỂU KHIÊN Lưu LƯỢNG
■ •
TRONG MẠNG MẢY TÍNH
■
CHU YẾN NG ÀN H : TIN HỌC
MÃ SỐ:
LUẬN VÃN THẠC sĩ KHOA HỌC
Người hướng dẫn khoa học: TS v ũ DUY LỢI
Hà Nội - 2001
Mở dáu
MỤC LỤC
1
Chương 1:
Giới thiệu rông quan 3
1.1 Sự cần thiết cúa việc điều khiển lưu lượn» và điều khicn tấc nghẽn
3
1.2 Điều khiến lưu lượng và điểu khiển tắc nghẽn 8
1.3 Mội số khái niệm dùng trong luận vã n 10
Chương 2: Cơ chế điều khiển lưu lượng và điều khiển tắc nghẽn
2.1 Điều khiển lưu lượng dựa trên timeout và cơ chế cửa sổ
15
1
MỞ ĐẦU
Một trong những ưu điểm của mạng máy tính là giá thành của hệ thống hạ do có thể
dùmz chung các tài nguyên trên mạng như băng thông của đường truyền, các thiết bị
trẽn mạng. Việc chia xẻ các tài nguyên cho nhiểu người dùng là thế mạnh cùa các
mạng chuyên mạch gói. Mộl kết nối trên mạng có thể được chia xẻ cho các cặp trạm
neuổn - đích khác nhau trao đổi thông tin. Bộ xử lý và bộ đệm của các trạm trung gian
cũng được chia xẻ và dùng chung cho các cặp nguồn - đích đó. Tuy nhiên, sự chia xẻ
này có thể dẫn lới các vấn đề tắc nghẽn trên mạng, chẳng hạn khi có quá nhiều gói bị
lỗi phải truyền lại dẫn tới sổ' lượng gói thực sự được chuvển qua mạng giảm (thậm chí
bàng 0). Để'đối phó với vấn đề tắc nghẽn, mạng cần được thiết kế sao cho khả năng
tắc nghẽn là thấp nhất. Trong trường hợp mục đích tránh tấc nghẽn không đạt được thì
chúng ta cần có phương thức đẻ phục hổi hộ thống từ trạng thái tắc nghẽn. Điều đó đòi
hỏi phải có những ihủ tục và chính sách trong điều khiển lưu lượng và điều khiển tắc
nghẽn để tránh, phát hiện và phục hồi hoạt động của mạng từ trạng thái tắc nehẽn. Các
cơ chế điều khiển còn được lựa chọn sao cho các thông tin điều khiển không trờ thành
tải trên mạng, để tãng hiệu quả của kênh truyền.
Những tiến bộ gần đây của cả công nghệ chuyển mạch tốc độ cao và công nghệ cáp
quang về mặt vật lý đã cho phép thực hiện mạng máy tính chuyển mạch gói giữa 2
điểm với tốc độ cỡ Gbit/s. Những kết quả của công nghệ nàv là thực hiện các giao dịch
bãng rộng, gồm kích cỡ gói âm thanh, video và dữ liệu, trên một mạng tích hợp. Dựa
trên điểm này, sự tảng tốc độ chuyển mạch và truyền thổng tin thay đổi một số nền
tảng tiền đé cùa công nghệ mạng diện rộng chuyển mạch gói. Một trong các vấn đề
cần nghiên cứu là điều khiển lưu lượng vì các lý do sau:
- Thứ nhất là tỉ lệ cùa tốc độ truyền với tốc độ tính toán tảng rất nhanh đòi hỏi một cơ
chế điều khiển lưu lượng thích hợp.
- Thứ hai là tỉ lệ giữa độ trễ của gói dữ liệu với thời gian truyền tăng, đặc biệt đối với
mang diện rộng WAN do đó cần một cơ chế điều khiển lưu lượng để thời gian trễ đáp
ứng được yêu cầu.
Trong các mạng chuyển mạch gói không hướng kết nối, các kết nối thường có dung
2
GIỚI THIỆU TỔNG QUAN
3
Chưong1
1.1 Sự CẦN THIẾT CỦA VIỆC ĐIỂU KHIÊN lưu l ư ợ n g v à điểu kh iến
TẮC NGHẼN
Một mạng máy tính với các thiết bị phần cứng là cỏ' định, hiệu suất hoạt động của
mạng phụ thuộc vào sự hiệu quả của giao thức truyền thông trên mạng. Trong mỗi
giao thức thì phần quan trọn® góp phần tăng hiệu quả hoạt động cùa mạng chính là các
cơ chê diều khiển lưu lượng và điều khiển tắc nghẽn.
1.1.1 Vấn để điều khiển lưu lượng và tránh tắc nghẽn trong mạng máy tính
Chúng ta xem xét khả nãng trao đổi thông tin trên mạng: Mối quan hệ giữa yêu cầu
trao đổi thõng tin và số lượng thỏng tin được trao đổi trên một phân mạng.
Sự trao đổi thông tin trong mạng máy tính dựa trên những kênh truyền dẫn có dung
lượng giới hạn, nó chi đáp ứng được một sô' lượng giao dịch yêu cầu nhất định. Và khi
các yêu cầu quá khả năng chấp nhận của mạng thì sự tấc nghẽn cũng có thể xảy ra. Ta
xem xét mạng máy tính trong các trường hợp cụ thể sau:
*
Lý tưởng:
Ta giả thiết là quá trình truyền trên mạng không có lỗi. Đường biểu diễn
sự phụ thuộc của thông lượng qua mạng và tải yêu cầu như sau [2]:
H ình 1 .ì : Thônq lượng qua mạng trong trường hợp lý tưởììg
Trong đó:
-
X
là dung lượng đưa vào mạng, hay tổng số gói đưa vào mạng trong một đơn vị thời
gian.
- Ỵ(Ằ) là thông lượng qua mạng, hav số gói được chuyên qua mạng trong một đơn vị
thời gian.
Ầ() là giá trị nhỏ nhất của dung lượng đưa vào mạng mà tại đó thông lượng qua mạng
Trước khi xem xét các thú tục và chính sách điểu khiến lưu krợng và điều khiển lắc
nghẽn, chúng ta xem xét sự hoạt động của một mạng không thực hiện các thù tục đó.
Có hai vấn đé trong mạng khôn» điều khiển: Sự giảm thòng lượng và sự không còng
bẳn tị trong việc cấp phát băng thông.
1.1.2 Nhận xét
Hình 1.3: Một mạng bị tắc nghẽn do không có điêu khiển
Mỏt mang dưn gián trong hình giúp chúng la minh hoa các vấn dé trẽn. Các con sỏ
trên kết nòi chi dung lượng cùa kết nối đó, đơn vị là kbps. Ta siá sứ cần thực hiện hai
1 Lions si ao dịch:
- Từ trạm B đén trạm A : '-BA Kbps, với các giao dịch đi theo đường B ->Ỵ -> X ->A
- Từ trạm c đến trạm D: ^CD kbps. với các giao dịch đi theo đường C->Z->X->D
Ta già sử rằng mạng không được điếu khiến, nahîa là các giao dịch trẽn mạng có thể
sir dụng các tài nsuyẽn trên mạng, các trạm nguồn khỏng bị giới hạn tốc độ phát, và
dặc biệt là các bộ đệm gói trên các trạm trung gian X, Y. z (phần bộ nhớ trên các nút
trung gian dùng để lưu các gói được chuyển đến) có thể bị chiếm giữ bời tất cả các
gói. Các gói bị huỷ khi không còn bộ đệm tại trạm mà chúng được chuyên đến. Các
tĩỏi bị huý sẽ được truyền lại khi hết thời gian timeout mà khổng được xác nhận. Một
bán sao cùa mỏi gói được giữ tại trạm nguồn khi trạm đó chưa nhận được ack từ tram
tiếp theo dọc theo đường truyền của gói.
Sự siàm thỏim lượng và sự khòng công bằng thê hiện trong các trường hợp sau đây:
Trường fĩỢỊj !
Kr.\ = 7 kbps và ^'CD = 0
Trạng thái này khòng tắc nghẽn, do giao dịch đòi hỏi từ B đến A nhỏ hơn dung lượng
của mạng. Các kết nòi B Y, Y -> X. X -> A đểu truyền 7 kbps.
Trường hợp 2:
'-BA = 8+^ kbps và *-CD = 0 >0)
Các gói đề nghị chuyến đến A iớn hơn khá năng của kết nối X A, do đó bộ đệm ở
nút X có thế bị đầy do các gói chuyến đến X chờ đê được chuyến từ X -> A. Khi bộ
đệm tại X đầy, các gói tiếp theo gửi từ Y đến X bị huỷ bỏ và không được xác nhận.
Nứt Y văn phái giữ các gói để chừ xác nhận, vì vậy bộ đệm cúa nó sẽ chứa các gói
truyền từ Y -> X gấp 2 lần dung lượng đường truyền z -> X) nên số lượng các gói đến
từ B được chấp nhận bằng 2 lần các gói đến từ c được chấp nhận. Như vậy, khi tốc độ
truyền X -> A tối đa là 8 kbps thì tốc độ truyền từ X -> D là 4 kbps.
So sánh với trường hợp 3 ta thấy, khi /-BA tăng từ 7 lên 8+k thì:
7
- Tổng thông lượng từ X truyền tới A và D giảm từ 14 kbps xuống còn 12 kbps.
- Trạm c bị đối xử không công bằng. Tốc độ truyền từ c tới D giảm từ 7 xuống còn 4
kbps. trong khi nauyèn nhân cùa vấn để là do các gói đến từ B.
Đế giải quyết vấn đé này, ta có thể dùng các phương pháp như trong trường hợp 2.
Phương pháp thứ ba là dành ra một sô bộ đệm của X để phục vụ cho việc chuyển các
gói tới D. Như vậy sẽ đàm bảo sự công bằng cho dù các gói đến từ B có làm mạng bị
tắc nghẽn hay không. Tuy nhiên việc đặt trước bộ đệm làm giảm khả năng chia xẻ của
mạng chuyên mạch gói. Nhưng điểu này cho thấy cần định ra một mức chia xẻ tắc
nghẽn một cách hợp lý đê vừa đảm bảo cho sự công bằng và giá cả hợp lý.
1.1.3 Kết luận
Đê đảm báo cho hoạt động của mạng thông suốt, tránh tắc nghẽn khi số lượng giao
dịch đầu vào tăng nhanh, và để tăng hiệu suất của mạng, chúng ta cần sử dụng phương
pháp điểu khiển lưu lượng trong mạng thông tin máy tính.
1.2 ĐIỂU KHIỂN LƯU LƯỢNG VÀ ĐỉỂU KHIÊN t r á n h t a c n g h ẽ n
Trong quá trình truyền số liệu giữa một trạm nguồn và một trạm đích, hai trạm có sự
thống nhất trong cách truyền và cách nhận sao cho dữ liệu được truyền và nhận đúng.
Khi trạm đích chưa nhận được dữ liệu một cách chính xác thì trạm nguồn sẽ truyền lại
dữ liệu đó. Dữ liệu có thể bị mất do trạm nhận không còn bộ đệm thu, hoăc có thể bị
lỏi trong khi truyền. Các gói dữ liệu bị mất hoặc hỏng sẽ làm cho số lượng các gói cần
truyền qua mạng tàng lên.
Quá tải là hiện tượng có quá nhiều gói dữ liệu được truyền lại, làm cho số lượng gói
được chuyển thành công giảm đột ngột, thậm chí giảm tới 0.
Để iránh hiện tượng quá tải, cần sử dụng cơ chế điều khiển lưu lượng và điểu khiển
tránh tắc nghẽn trong quá trình truyền thông tin trên mạng.
- Điều khiến htu lượng: Là sự thống nhất giữa trạm nguồn và trạm đích về dòng dữ
H àng đ ợ i M IM I1 IK :
Các gói đến một trạm theo quá trình Poisson, sự phục vụ theo
hàm mũ, và có một server, trạm có K bộ đệm (hàng đợi có độ dài lớn nhất là K).
G ó i ack (acknowledgem ent
packet): Gói xác nhận. Trong cơ chế truyền có xác nhận,
khi trạm nguồn truyền dữ liệu đến trạm đích, nếu trạm đích nhận đúng gói dữ liệu thì
sẽ trà lời trạm nguồn bằng gói ack.
Thời gian trễ (delay): Là thời gian lan truyền tín hiệu trên môi trường truyén dẫn từ
trạm nguồn đến trạm đích, thời gian các gói phải chờ trong bô đệm, hoăc thời gian
phát gói.
Thời gian trẻ toàn phần (RTT): Bằng thời gian từ khi trạm nguồn phát gói dữ liệu cho
đến khi nó nhận được gói ack.
Thòng lượng (throughput): Số lượng thông tin tính bàng bit hoặc byte truyển từ trạm
nguồn đến trạm đích thành công trong một đơn vị thời gian.
Hop: Đường đi giữa hai trạm cuối trao đổi dữ liệu cho nhau thông qua nhiều đoạn
đường, mỗi đoạn được gọi là 1 hop.
Cổ chai: Là yếu tô' quyết định đến thông lượng qua mạng. Trên một kênh truyền thì
nút có tốc độ xừ lý chậm nhất, các gói qua đây phải chờ lâu nhất gọi là nút cổ chai.
Tấc nghẽn (deadlock). Là trạns thái không có giao dịch nào được thực sự chuyển qua
mang. Các gói được truyén lại trên mạng mà không truyền được gói mới, hoặc tất cả
các trạm đều hết bộ đệm. Thông lượng qua mạng bằng 0 và thời gian trễ vô cùng lớn.
Chuyên mạch kênh (circuit switching): Tồn tại một đường kết nối riêng, cố định giữa
hai thiết bị cuối irong toàn bộ quá trinh trao đổi dữ liệu.
Chuyên mạch gói (packet switching): Chia dữ liệu được truyén thành các gói có độ
dài thav đổi, và chuvển qua các đường (có thể) khác nhau trong hệ thống truyền dẩn.
Sử dụng phương thức lưu và chuyển (store and forward) để lưu gói nhận được, phân
tích phần tiêu đé của gói để thực hiện chuyển tiếp.
10
Chuyển mạch gói kết nối: Tương tự chuyển mạch kênh, kết nối được thiết lập trước khi
trao đổi dữ liệu và được huỷ bỏ sau khi trao đổi xong. Nhưng trong quá trình truvén,
Khi gói đến cuối hàng đợi, nó được truyền qua kết nối tới router tiếp theo, hoặc đến
đích cuối cùng.
Chức năng chọn gói có thể chọn một gói bất kỳ trong bộ đệm vào để chuyển cho chức
năng định tuyến. Thường thì theo thứ tự FIFO, nhưng cũng có thể là theo một cách
khác.
Có hai yêu tố ảnh hưởng quyết định đến khả năng hoạt động của router. Thứ nhất là
thời gian tối thiểu để router giải mã phần tiêu để của gói đến, để quyết định đường đi
cho gói đó và chuyển gói đó tới đường ra để truyền nó đi. Thứ hai là thời gian các gói
phải chờ trong bộ đệm (vào, ra) của router.
Bộ đệm vào và bộ đệm ra của router là có hạn, khi một bộ đệm đầy, không gói nào
được nhận nữa và router phải huv bỏ chúng. Đây là nguyên nhân mất dòng dữ liệu từ
nguồn đến đích, và do đó trạm nguồn truyền lại dữ liệu đó.
Router không thể đưa gói vào hàng đợi ra nếu bộ đệm tương ứng bị đầy, nhưng nó có
thể chọn huỷ bỏ gói đã ở trong bộ đệm và đưa gói mới vào thế chỗ. Lựa chọn này được
thực hiện bời chức năng gửi gói. Việc này không thực hiện được đối với bộ đệm vào vì
một gói không được đưa vào bộ nhớ của router, nếu nó chưa được đưa vào hàng đợi
vào. Do vậy gói vào có thể bị mất ngoài sự kiểm soát của router.
Cuối cùng, các bộ đệm được cấp phát cho các đường vào và các đường ra của router có
thể dùng chung không gian bộ nhớ, hoặc chúng dùng bộ nhớ riêng biệt. Nếu dùng
chung thì không bộ đệm nào bị đầy khi toàn bộ bộ nhớ của router chưa được sử dụng
hết. Nếu dùng riêng, bộ nhớ được cấp phát cô' định cho mỏi đường vào, ra do đó việc
sử duns bộ đệm của một đường vào, ra rỗi sẽ không hiệu quả.
M ạng A R PA N E T :
được nghiên cứu, thiết kế và thực hiện cuối những năm 1960 ở
bang California, Mỹ. Đây là mạng thông tin máy tính đầu tiên sử dụng công nghệ
chuyển mach gói. Mạng ARPANET là tién thản của mạng Internet hiện nay.
12
13
Mò hình kênh ào:
^•mt
4. Các gói có kích thước không cô' định được chuyển từ kết nối này đến kết nối khác
dựa vào các nút, thường gọi là các switch, gateway hoậc router. Router đưa vào bộ
đệm các gói đến trước khi truvền chúng đi tiếp.
5. Mạng sử dụng cách định tuyển nửa tĩnh.
6. Mạng không ràng buộc băng thông đối với nguồn dữ liệu. Một trạm nguồn có thể
truyền dữ liệu với tốc độ tăng tối đa trên các kêĩ nối giữa nó và trạm đích.
7. Các kết nối được già thiết là có băng thông cố định. Tuy nhiên các gói có thể bị lỗi
hoặc điều khiển lưu lượng bị lỗi khi truyền qua mỗi kết nối.
8. Mạng không
đảm bâo quá
trình truyền. Các kết nối trên mạng có băng thông giới
hạn và các nút có bộ đệm giới hạn cho các gói đang chờ được chuyển đi. Nếu các
thành phần của mạng không thể chuyển tiếp các gói tới đích vì một lý do nào đó gói có
thê bị huỷ bỏ.
14
15
Chương 2
MỘT SỐ Cơ CHẾ ĐIỀU KHIỂN lư u l ư ợ n g v à ĐIỀư
KHIỂn t r á n h tắ c n g h ẽ n
2.1 ĐIỂU KHIỂN LƯU LƯỢNG DựA TRẼN TIMEOUT VÀ c o CHẾ CỬA s ổ
2.1.1 Thời gian timeout và hiện tượng tắc nghẽn
a) Thời gian timeout
Trong việc truyền có xác nhận giữa hai trạm, nếu trạm đích nhận đúng gói dữ liệu thì
sẽ trả lời trạm nguồn bằng gói ack. Như vậy khi gói dữ liệu bị mất, trạm đích không
nhận được và không phát gói ack tương ứng cho gói đó. Sau một khoảng thời nào đó
mà không nhận được gói ack thì trạm nguồn biết rẳng gói dữ liệu đã bị mất, và phát
lại. Khoảng thời gian đó gọi là thời gian timeout. Hình vẽ sau minh hoạ cách tính
khoảng thời gian timeout:
Trạm nguồn Trạm đích
• •
chuyển đến đích.
Tắc nghẽn có thể thể hiện bởi một số yếu tố: Nếu trạm thực hiện các nhiệm vụ của nó
quá chậm (xử lý và phát gói tin, cập nhật các bảng định tuyến,. . .) thì hàng đợi được
tạo ra (ngay cà khi dung lượng của đường truyền dư thừa).
Mặt khác thậm chí nếu CPU của trạm có tốc độ nhanh vô hạn, hàng đợi sẽ vẫn được
tạo ra mỗi khi tốc độ gói vào vượt quá dung lượng của đường ra.
Ví du: Có 3 đường vào chuyển các gói với tốc độ cao nhất. Tất cả các gói đểu chuyển
đến một đường ra. Nếu Ci+C2+Q>Coui thì dù cho khả nâng xử lý của trạm là rất nhanh,
hàng đợi vẫn được thiết lập do dung lượng đường ra không đáp ứng được. Nếu duy trì
tốc độ vào như vậy thì dẫn đến trạm khổng đủ bộ đệm.
16
17
c,
Cj
c,
^ H àn g đơi
> 11lim 111
^ Trạm
Hình 2.2: Hàng cìợi được thiết lập khi dung lượng vào lớn hơn dung lượng ru tối đa
Trong cơ chế truyền có xác nhận, một trạm không còn bộ đệm sẽ huý bỏ các gói mới
đến. Khi gói bị huý bỏ, trạm gửi gói đó sẽ nhận được timeout và truyền lại gói đó. Nếu
có tắc nghẽn, trạm gửi có thể phải gửi lại gói đó nhiều lần. Do trạm gửi không thể huỷ
bỏ gói cho đến khi nó được xác nhận, tắc nghẽn tại trạm nhận bất buộc trạm gửi phải
giữ lại bộ đệm mà thông thường sẽ được giải phóng.
2.1.2 Chiến lược điều khiển tránh tắc nghẽn
Để khắc phục hiện tượng tắc nghẽn, ta có thể dùng 5 chiến lược sau:
1 ) Định vị trước các tài nguyẽn để tránh xung đột.
2) Cho phép trạm trung gian huỷ bỏ gói dữ liệu nếu cần.
3) Cấm một sô' gói dữ liệu trên phân mạng.
4) Sử dụng phương pháp điểu khiển lưu lượng.
bộ đệm vào mới.
Nếu tắc nghẽn được tránh bằng cách huỷ bỏ các gói, thì cần một luật để biết rằng khi
nào cần phải giữ gói và khi nào có thể huỷ bỏ nó. Nếu không có một luật rõ ràng thì
đường vào đơn cũng có thể sử dụng hết tất cả các bộ đệm trong một trạm trung gian,
khi nó xử lý đơn giàn theo cách phục vụ FCFS (gói đến trước được phục vụ trước).
Chiến lược quản lý bộ đệm:
18
a) b)
Hình 2.3: Phân chia bộ đệm cho các đường ra
Hình a) mô tả một trạm với tổng 10 bộ đệm, 3 trong sô' đó thường xuyên dùng cho các
đường vào, 7 còn lại lưu giữ hàng đợi các gói để gửi đi một trong các đường ra. Thậm
chí khi hai đường ra rỗi, bất kỳ một gói nào đến cho các đường này cũng đéu bị huý bỏ
vì không còn bộ đệm.
Có thế giới hạn bộ đệm cho mỗi hàng đợi. Ví dụ nêu giới hạn đó là 4, trong điéu kiện
như hình b) thì sẽ còn 3 bộ đệm rỗi. Một gói mới đến cho đường ra thứ nhất sẽ bị huỷ
bỏ chứ không tăng bộ đệm cho hàng đợi của đường ra này lên 5. Chiến lược này không
thưc sự có hiệu quà như mong muôn. Đường ra đã hoạt động hết dung lượng của nó.
Hàng đợi 7 gói thay cho 4 sẽ không cho các bit ra nhanh hơn, mà nó sẽ cho giao dịch
cùa các đường ra khác được chuyển tiếp ngay lập tức, có thể gấp hai hoặc ba lần tốc độ
đường ra của trạm trung gian. Trong bất kỳ trường hợp nào, gói bị huỷ sẽ được chuyển
lại ngay.
Giải thuật xác định độ dài lớn nhất cùa hàng đợi (m) cho trạm có k bộ đệm (không
tính những bộ đệm thường xuyên dùng cho các kênh vào):
- Trường hợp chỉ có một đường ra thì m=k.
- Trường hợp có s đường ra thì mỗi đường ra được cấp phát bộ đệm có độ dài tối đa là
m = k ỉ yís (2.2).
Không đường nào có thể mượn dù chỉ một bộ đệm từ một đường vào rỗi. Cách này
khổne thực sự hiệu quả. Xác định giá trị thích hợp của m là một việc khó. Cho dù trạm
trung gian có thể cố gắng để đo số lượng giao dịch và tiếp tục điều chỉnh m, nhưng nếu
giao dịch nhiều thì có thể hộ thống hoạt động không tốt. Sử dụng công thức 2.2 trong
Người ta đề xuất giải pháp cho vấn đề
lưu và chuyển.
Trong chiến lược này, một đổ thị
định hướng được thành lập, với các bộ đệm trở thành các nút của đồ thị.
Các cung của đổ thị nôi từng cặp bộ đệm trong trạm hoặc các trạm liền kề. Đồ thị đó
được cấu trúc theo cách nếu tất cả các gói chuyển từ bộ đệm đến bộ đệm dọc theo các
cung của đồ thị, thì không xảy ra bế tắc.
Một ví dụ đơn giàn của phương pháp này là xem xét một phân mạng với N trạm trong
đó đường đi dài nhất từ mỗi nguồn đến mỗi trạm đích dài m hop. Mỗi trạm cần m+1
bộ đệm được đánh số từ 0 đến m. Đổ thị bộ đệm bây giờ được kiến trúc bằng cách vẽ
một cung từ bộ đệm i trong mổi nút tới bộ đệm i+1 trong mỗi nút lân cận. Đường đi
hợp lệ từ mồi bộ đệm i tại trạm A là đường đi tới bộ đệm nhãn i+1 tại mỗi trạm lân cận
của A. và do đó bộ đệm nhãn i+2 tại các trạm dài 2 hop từ A.
Một gói từ trạm có thể được thu nhân tới phân mạng nếu bộ đêm 0 của trạm nguồn còn
trống. Mỗi khi được thu nhận, gói này chi có thể chuvển tới bộ đệm nhãn 1 trong một
trạm lân cận, và tiếp tục cho đến khi nó tới đích và bị loại ra khỏi phân mạng, hoặc nó
tới bộ đệm nhãn m. mà trường hợp đó nó bị huỷ bỏ (nếu m được chọn dài hơn đường
dài nhất, thì đây chỉ có thể là các gói được chuyển lặp lại, và sẽ bị huỷ bỏ). Một gói
trong bộ đệm i của một vài trạm có thể bị chuyển nếu bộ đệm i+1 trong trạm đã chọn
bời giải thuậl còn trống. Chú ý ràng việc đánh sô' các bộ đệm không cấm sự lựa chọn
của giải thuật chọn đường tĩnh hoặc động.
Để chứng minh giải thuật này tránh được bế tắc, ta xét trạng thái của tất cả các bộ đệm
nhãn m tại một số thời điểm. Mỗi bộ đệm ở một trong ba trạng thái: Rỗng, đang gửi
một gói để chuyển tới trạm cục bộ, hoặc đang gửi gói để chuyển cho trạm ở xa. Trong
trường hơp thứ 2, gói có thể được phân phát, trong trường hợp thứ 3, gói đang bị quay
vòng và cần phải loại bỏ. Trong tất cả ba trường hợp, bộ đệm có thể được giải phóng.
Nói chung, tất cả các gói trong bộ đệm m-1 bây giờ đều có thể được chuyển tiếp, và
mỗi lần như vậy chúng được truyền tới đích hoặc hủy bỏ. Khi tất cả các bộ đệm có
nhãn m-1 được giải phóng, thì các gói trong các bộ đệm có nhãn m-2 có thể được
chuyển tiếp hoặc huỷ bỏ. Cuối cùng, tất cả các gói được chuyên tiếp hoặc huỷ bỏ. Nếu
là sỏ lượng tối đa các gói có thể đưa vào đường ống đó trong một thời điểm (hay số
lượng tối đa các gói đang được chuyển trên mạng theo đường ống).
Trong các mạng điều khiển lun lượng của sổ, tham số chính để xác định tải trên mạna
và do đó xác định khả nâng của nó là kích thước cửa sổ dùng cho các trạm. Khi người
dùng tãng kích Ihước cửa sổ, thồng lượng tãng. Người dùng tiếp tục tãng sô' gói đưa
vào mạng. Tuy nhiên khi cửa sổ có kích thước lớn hơn một giới hạn nào đó (phụ thuộc
bộ đệm ờ các nút trung gian), thông lượng giảm do các gói bị mất. Kích thước cửa sổ
tại điểm tắc nghẽn bằng tổng số bộ đệm của kết nối. Trường hợp nhiều người dùng,
tổng kích thước cửa sổ của tất cả các trạm nguồn chuyển qua một nút trung gian luôn
nhỏ hơn dung lượng bộ đệm của nút trung gian đó.
- Số lượng của bộ đêm tại nút cổ chai quyết định dung lượng của đường truyển.
Copyright: Tài liệu đại học ©