Chương 15: Giải thuật OSU
Giải thuật OSU(Ohio State University) được các tác giả Raj
Jain, Shiv Kayanaraman vàRam Viwanathan giới thiệu tải
trường đại học bang Ohio vào tháng 10/1994. Giải thuật OSU
yêu cầu các nguồn giám sát tải của mình và gửi đònh kỳ các cell
điều khiển mang thông tin về tải(tốc độ nguồn). Các chuyển
mạch cũng giám sát tải của chính mình và sử dụng nó kết hợp
với thông tin được cung cấp từ các cell điều khiển để tính toán
các hệ số mà các nguồn sử dụng để điều chỉnh tốc độ của mình.
Phía thu đơn giản chỉ cần gửi trả lại các cell điều khiển cho
nguồn và sau đó nguồn sẽ điều chỉnh tốc độ của mình. Cell điều
khiển chứa các trường : Tốc độ cell phát (TCR_Transmission
Cell Rate), Tốc độ trung bình đề nghò (OCR_Offer average Cell
Rate), Hệ số điều chỉnh tải (LAF_ Load Adjustment Factor),
Khoảng thời gian trung bình (AI_ Averaing Interval), Hướng hồi
tiếp (Dir_Direction of feedback) gồm 1 bit với Dir=0 chỉ hướng
đi và Dir=1 chỉ hướng về và Tem đònh thời (Timestamp).
Sau đây là các đặc tính của giải thuật OSU:
+ Tránh tắc nghẽn:
OSU là giải thuật tránh tắc nghẽn, nó cố gắng giữ mạng vận
hành ở tình trạng lưu lượng cao và trì hoãn thấp khi xác lập;
đồng thời duy trì những nơi tắc nghẽn cổ chai vận hành trong
TUB (dải tận dụng đích) và các dao động cũng được giới hạn
trong dải tận dụng đích(TUB_Target Utiliration Band). Cho dù
dao động trong TUB thì hệ số tải tại chuyển mạch luôn nhỏ hơn
1. Vì vậy hàng đợi của chuyển mạch gần bằng 0 nên độ trì hoản
được tối thiểu. Trong hầu hết các trường hợp, TUB được chọn
tối ưu là 90
. Độ tận dụng trong trường hợp này nằm trong
khoảng từ 81
 đến 99.

+ Các thông số :
Trong giải thuật OSU, người điều hành mạng chỉ cần đặt ba
thông số: khoảng thời gian trung bình cho chuyển mạch(AI),
mức tận dụng đích (TU_Target link Utilization) và hệ số chỉ
đònh phân nửa độ rộng dải tận dụng đích (TUB). Một đặc tính
quan trọng của giải thuật OSU về thông số là tính không quá
nhạy cảm với các giá trò của thông số. Các thông số của giải
thuật OSU không phụ thuộc vào chiều dài của kết nối hay
khoảng cách mà các quảng đường VC phải đi.
Ngoài ra việc cài đặt ba thông số này của OSU cũng dể dàng
hơn những dải thuật khác. Giá trò thông số TU cho phép cân
nhắc sự đánh đổi giữa mức độ hiệu quả và thời gian đạt được sự
công bằng. Giá trò TU lớn thì hiệu quả nhưng lâu đạt được sự
công bằng và chiều dài hàng đợi lớn. Thông số AI ảnh hưởng
đến sự ổn đònh của các tải mà giải thuật cần đo và cho phép cân
nhắc sự đánh đổi giữa sự dao động và thời gian đạt được sự tối
ưu. Giá trò AI nhỏ gây ra nhiều biến động cho hệ số tải z và do
đó có nhiều dao động. Giá trò AI lớn hơn gây ra sự chậm trễ
trong hồi tiếp và do đó lâu ổn đònh hơn.
+ sử dụng thao tác xác đònh quá tải thông qua đo lường chứ
không bằng khai báo:
Giải thuật OSU đo mức tải hiện hành và mọi dung lường
không dùng được phân chia cho các nguồn đang tranh chấp.
Chúng ta sử dụng tốc độ do khai báo để tính toán phân chia
băng thông trong trường hợp đặc biệt nhưng sử dụng mức tải
được đo tại chuyển mạch để quyết đònh tăng hay giảm tốc độ. Vì
vậy nếu nguồn khai báo không chính xác hoặc thông tin từ
nguồn đã lỗi thời , giải thuật có thể không đạt được công bằng
nhưng vẫn đạt đïc hiệu quả.
+ Hồi tiếp lưỡng cực:

Giải thuật OSU sử dụng hồi tiếp lưỡng cực gồm hồi tiếp âm
và hồi tiếp dương. Hồi tiếp dương yêu cầu nguồn tăng tốc độ
phát của mình và hồi tiếp âm yêu cầu nguồn giảm tốc độ phát
của mình.
Vấn đề chủ yếu đối với hồi tiếp đơn cực là mức tải thay đổi
liên tục(thường trên mỗi cell) tức là không tăng thì giảm mà
không có trạng thái ổn đònh. Điều này có thể không thích hợp
với một số ứng dụng (như lưu thông video nén). Mỗi khi hiệu
chỉnh tốc độ đòi hỏi ứng dụng phải hiệu chỉnh thông số của
mình. Hồi tiếp lưỡng cực tránh được những hiệu chỉnh không
cần thiết bằng cách cung cấp những chỉ thò rõ ràng đến nguồn
để thay đổi mức tải.
+ Đo lường dựa trên tốc độ thay vì dựa trên chiều dài
hàng đợi:
Trong khi chiều dài hàng đợi là một chỉ đònh tải tốt cho hàng
đợi được điều khiển theo cửa sổ thì tốc độ vào là lại chỉ đònh tải
đúng cho hàng đợi được điều khiển dựa theo tốc độ.
Giám sát tốc độ vào không chỉ cung cấp một chỉ cung cấp
mộy chỉ đònh mức tải tốt mà còn cung cấp một chỉ đỉnh chính
xác về tình trạng quá tải cũng như dưới tải. Ví dụ, nếu tốc độ
hàng đợi là 20 cell trên giây trong khi hàng đợi chỉ có thể phục
vụ được 10 cell trên giây. Để hiệu chỉnh thì trong trường hợp
này LAF =2, nghóa là tốc độ vào phải được giảm xuống hai lần.
Giải thuật OSU sử dụng tốc độ vào để tính toán mức độ quá
tải và hiệu chỉnh tốc độ nguồn. Mỗi chuyển mạch đếm số lượng
cell mà nó đã nhận trên mỗi liên kết trong mỗi chu kỳ cho trước,
tính toán tốc độ vào và hệ số quá ải đang sử dụng dung lượng
liên kết (cell/giây). Giải thuật cố gắng điều chỉnh tốc độ nguồn
bằng một hệ số bằng với mức quá tải và cố gắng mang mức quá
tải xuống mức hợp lý càng nhanh càng tốt.

3.1.4.7 Giả thuật EPRCA+và EPRCA+ +:
Giải thuật EPRCA+(Enhanced Proportional Rate Control
Algorithm) được phát triển dựa trên cơ sở giải thuật với một số
thay đổi. Trong đó quá trình phát hiện dựa trên sự ước đoán thay
vì sử dụng giá trò ngưỡng trong hàng đợi cell. Chuyển mạch tiến
hành đếm số cell nhận được trong một khoản thời gian đònh
trước. Nguồn cuối cũng được trang bò một bộ đònh thời thay cho
bộ đếm số cell RM gửi. Tốc độ của nguồn được giữ không đổi
cho đến khi nó nhận được cell BRM mang theo giá trò tốc độ
tường minh ER được xác đònh bởi chuyển mạch
Một đặc điểm hấp dẫn của giải thuật EPRCA+ là số lượng
các thông số điều khiển ít và dễ dàng cài đặt bởi người quản lí
mạng. Nhiều thông số trong giải thuật EPRCA đã được giảm bớt
trong giải thuật EPRCA+. Hơn nữa, trong giải thuật EPRAC+ thì
giải tận dụng đích(TUB) được cài tự do. TUB của chuyển mạch
có thể dưới 95% độ tận dụng đường truyền. Do đó, kích thước
chiều dài hàng đợi tại chuyển mạch nhỏ hơn và độ trễ cell thấp
hơn.Mặc dù phải tốn thêm chi phí cho bộ đònh thời và bảng VC
nhưng EPRCA+ cung cấp độ công bằng tốt hơn, đồng thời có
đáp ứng nhanh hơn EPRCA.
Có một vấn đề đã nêu trong giải thuật EPRCA đó là khi ước
đoán ACR(Allowed Cell Rate) không tốt nguồn sẽ nhanh chóng
giảm tốc độ với hệ số RDF(Rate Decrease Factor) cho đến khi
đạt đến MCR(Minimum Cell Rate). Điều này là cần thiết nhưng
sẽ mất công trong trường hợp mạng nhanh chóng đạt được trạng
thái ổn đòng. Một cải tiến tiếp theo là giải thuật EPRCA++. Giải
thuật này sử dụng một bộ đếm tại nguồn cuối cho các cell
FRM(Forward RM cell) thay cho bộ đònh thời của giải thuật
EPRCA+. Hơn nữa nguồn cuối hệ thống chỉ giảm tốc độ ACR
khi không có cell BRM(backward RM cell) trong k.Nrm cell,

trong đó k là một giá trò cài đặtvà Nrm là số cell tối đa truyền
giữa hai cell RM. Sự thay đổi này cho phép giải thuật EPRCA++
hoạt động tốt hơn EPRCA+, đặc biệt trong trạng thái quá độ.
3.1.4.8 Giải thuật ERICA(Explicit Rate Indication
Congestion Avoidance):
Giải thuật ERICA được xây dựng dựa trên ý tưởng của giải
thuật OSU. Giới hạn chủ yếu của giải thuật OSU là không tương
thích với các tiêu chuẩn của ATM Forum và trong các cấu hìng
phức tạp thời gian hội tụ từ các điều kiện ban đầu tùy ý đến
trạng thái thiết lập thì kéo dài(đáp ứng quá độ).
Giải thuật ERICA và ERICA+ đã khắc phục các giới hạn của
giải thuật OSU trong khi vẫn giữ được các đặc tính ưu việt của
nó. Ngoài ra, chúng là những giải thuật mang tính lạc quan có
nghóa là chúng phân cấp tốc độ để tối ưu hóa hoạt động quá độ
cũng như trạng thái xác lập. Do các mạng trên thực tế thì phần
lớn thời gian là ở trong trạng thái quá độ (nguồn gửi và ngừng
gửi , dung lượng ABR thay đổi) nên giải thuật áp dụng cho các
chuyển mạch trong hệ thống thực tế cần hoạt động tốt ở cả hai
điều kiện xác lập cũng như quá độ.
3.1.4.8.1 Giải thuật ERICA cơ bản:
Giải thuật ERICA cơ bản sử dụng các thông số sau:
+ Hệ số tải z: là tỉ số giữa tốc độ nhập(input rate) được đo tại
cổng(port) và dung lượng đích(target capacity) tại ngõ ra của
liên kết. Nó chỉ đònh mức tắc nghẽn của liên kết. Giá trò quá tải
cao không được mong muốn bởi vì nó cho biết tắc nghẽn quá
mức ; còn giá trò quá tải thấp nói lên liên kết dưới độ tận dụng.
Điểm hoạt động tối ưu là điểm mà tại đó hệ số tải bằng 1. Mục
tiêu của chuyển mạch là duy trì mạng tại lượng quá tải đơn
vò(z=1).


ABRlượngDung
ABR
nhập
độ
Tốc
z
+ Dung lượng ABR: Bằng độ tận dụng đích x băng thông liên
kết

+ Tốc độ nhập: là giá trò được đo sau mỗi khoảng thời gian
được gọi là khoảng thời gian trung bình chuyển mạch (switch
averaring interval). Các bước trên được thực thi tại cuối mỗi
khoảng thời gian chuyển mạch.
+ Độ tận dụng đích: (U-target utiliration) là phân số nhỏ hơn
100% của dung lượng còn lại. Giá trò tiêu biểu là 0.9 và 0.95.
+ Hệ số chia sẻ công bằng: (fair share) hệ số chia sẻ công
bằng của mỗi VC đựơc tính như sau:

hoạt kíchnguồngSố
ABR
lượng
Dung
ShareFair 
Chuyển mạch cho phép chia mỗi nguồn gửi ở tốc độ dưới hệ
số chia sẻ công bằng để tăng lên giá trò này(fair share) mỗi khi
nó gửi hồi tiếp về nguồn. Nếu nguồn không sử dụng hết giá trò
fair share này thì chuyển mạch sẻ phân cấp công bằng lượng
băng thông còn lại cho các nguồn có thể sử dụng. Để đạt được
mục đích này, chuyển mạch phải tính toán thông số sau:


z
Rate)
Cell
(Current
CCR
VCShare 
Nếu tất cả các VC thay đổi tốc độ của chúng đến giá trò
VCShare thì trong chu kỳ vòng mạng kế tiếp chuyển mạch sẻ
đạt được tải đơn vò (z=1). Vì vậy mục tiêu của thông số
VCShare là đưa hệ thống đến điểm vận hành hiệu quả , có thể
không cần thiết phải công bằng; còn hệ số chia sẻ công
bằng(fair share) nhằm đảm bảo độ công bằng mà có thể dẫn
đến quá tải(vận hành không hiệu quả). Do đó chúng ta có thể
kết hợp cả hai thông số này để đưa hệ thống đến điểm vận hành
nhanh nhất.
ER tính toán = Max(FairShare, VCShare)
Nguồn được phép gửi ở tốc độ ít nhất bằng FairShare trong
thời gian vòng mạng đầu tiên để đảm bảo độ công bằng tối
thiểu giữa các nguồn. Nếu giá trò VCShare lớn hơn FairShare
nguồn được phép gửi ở tốc độ VCShare nhằm đảm bảo liên kết
không dưới độ tận dụng. Bước này cũng cho phép nguồnđạt
được tốc độï công bằng max-min. Đây là một trong những điểm
cách tân của giải thuật ERICA bởi vì nó cải thiện độ công bằng
ở mổi bước cho dù đang trong điều kiện quá tải.
Giá trò ER tính toán không thể lớn hơn dung lượng ABR mà
đã được đo trước đó.do đó:
ER tính toán = Min (ER tính toán, dung lượng
ABR)
Để đảm bảo giá trò ER tại điểm cổ chai đạt đến ngưỡng thì
mỗi chuyển mạch phải tính toán giá trò tối thiểu của ER mà nó

đã tính trước kia và ER trong cell RM. Giá trò này được chèn vào
trường ER trong cell RM với:
ER trong cell RM = Min(ER trong cell RM,
ER tính toán)
Lưu đồ của giải thuật ERICA cơ bản được đưa ra trong hình
trang bên. Lưu đồ chỉ ra tường bước thực hiện ở ba sự kiện sau:
tại cuối mỗi khoảng thời gian trung bình, khi nhận một cell(cell
dữ liệu hoặc cell RM) và khi nhận một cell BRM.
Giải thuật ERICA cơ bản có một số nhược điểm:
+ Không đạt được độï công bằng max-min trong một số trường
hợp phức tạp.
+ Có thể dẫn đến tốc độ và hàng đợi tăng đột ngột khi có sự
bất đồng bộ trong chuyển mạch.
Một số thay đổi trong giải thuật ERICA mở rộng sẽ giải
quyết vấn đề này.