Điều khiển lưu lượng và tắc nghẽn trong mạng ATM, chương 15

Chia sẻ: Minh Anh | Ngày: | Loại File: PDF | Số trang:7

0
123
lượt xem
35
download

Điều khiển lưu lượng và tắc nghẽn trong mạng ATM, chương 15

Mô tả tài liệu
  Download Vui lòng tải xuống để xem tài liệu đầy đủ

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. ...

Chủ đề:
Lưu

Nội dung Text: Điều khiển lưu lượng và tắc nghẽn trong mạng ATM, chương 15

  1. Chương 15: Giaûi thuaät OSU Giaûi thuaät OSU(Ohio State University) ñöôïc caùc taùc giaû Raj Jain, Shiv Kayanaraman vaøRam Viwanathan giôùi thieäu taûi tröôøng ñaïi hoïc bang Ohio vaøo thaùng 10/1994. Giaûi thuaät OSU yeâu caàu caùc nguoàn giaùm saùt taûi cuûa mình vaø göûi ñònh kyø caùc cell ñieàu khieån mang thoâng tin veà taûi(toác ñoä nguoàn). Caùc chuyeån maïch cuõng giaùm saùt taûi cuûa chính mình vaø söû duïng noù keát hôïp vôùi thoâng tin ñöôïc cung caáp töø caùc cell ñieàu khieån ñeå tính toaùn caùc heä soá maø caùc nguoàn söû duïng ñeå ñieàu chænh toác ñoä cuûa mình. Phía thu ñôn giaûn chæ caàn göûi traû laïi caùc cell ñieàu khieån cho nguoàn vaø sau ñoù nguoàn seõ ñieàu chænh toác ñoä cuûa mình. Cell ñieàu khieån chöùa caùc tröôøng : Toác ñoä cell phaùt (TCR_Transmission Cell Rate), Toác ñoä trung bình ñeà nghò (OCR_Offer average Cell Rate), Heä soá ñieàu chænh taûi (LAF_ Load Adjustment Factor), Khoaûng thôøi gian trung bình (AI_ Averaing Interval), Höôùng hoài tieáp (Dir_Direction of feedback) goàm 1 bit vôùi Dir=0 chæ höôùng ñi vaø Dir=1 chæ höôùng veà vaø Tem ñònh thôøi (Timestamp). Sau ñaây laø caùc ñaëc tính cuûa giaûi thuaät OSU: + Traùnh taéc ngheõn: OSU laø giaûi thuaät traùnh taéc ngheõn, noù coá gaéng giöõ maïng vaän haønh ôû tình traïng löu löôïng cao vaø trì hoaõn thaáp khi xaùc laäp; ñoàng thôøi duy trì nhöõng nôi taéc ngheõn coå chai vaän haønh trong TUB (daûi taän duïng ñích) vaø caùc dao ñoäng cuõng ñöôïc giôùi haïn trong daûi taän duïng ñích(TUB_Target Utiliration Band). Cho duø dao ñoäng trong TUB thì heä soá taûi taïi chuyeån maïch luoân nhoû hôn 1. Vì vaäy haøng ñôïi cuûa chuyeån maïch gaàn baèng 0 neân ñoä trì hoaûn ñöôïc toái thieåu. Trong haàu heát caùc tröôøng hôïp, TUB ñöôïc choïn toái öu laø 90. Ñoä taän duïng trong tröôøng hôïp naøy naèm trong khoaûng töø 81 ñeán 99.
  2. + Caùc thoâng soá : Trong giaûi thuaät OSU, ngöôøi ñieàu haønh maïng chæ caàn ñaët ba thoâng soá: khoaûng thôøi gian trung bình cho chuyeån maïch(AI), möùc taän duïng ñích (TU_Target link Utilization) vaø heä soá chæ ñònh phaân nöûa ñoä roäng daûi taän duïng ñích (TUB). Moät ñaëc tính quan troïng cuûa giaûi thuaät OSU veà thoâng soá laø tính khoâng quaù nhaïy caûm vôùi caùc giaù trò cuûa thoâng soá. Caùc thoâng soá cuûa giaûi thuaät OSU khoâng phuï thuoäc vaøo chieàu daøi cuûa keát noái hay khoaûng caùch maø caùc quaûng ñöôøng VC phaûi ñi. Ngoaøi ra vieäc caøi ñaët ba thoâng soá naøy cuûa OSU cuõng deå daøng hôn nhöõng daûi thuaät khaùc. Giaù trò thoâng soá TU cho pheùp caân nhaéc söï ñaùnh ñoåi giöõa möùc ñoä hieäu quaû vaø thôøi gian ñaït ñöôïc söï coâng baèng. Giaù trò TU lôùn thì hieäu quaû nhöng laâu ñaït ñöôïc söï coâng baèng vaø chieàu daøi haøng ñôïi lôùn. Thoâng soá AI aûnh höôûng ñeán söï oån ñònh cuûa caùc taûi maø giaûi thuaät caàn ño vaø cho pheùp caân nhaéc söï ñaùnh ñoåi giöõa söï dao ñoäng vaø thôøi gian ñaït ñöôïc söï toái öu. Giaù trò AI nhoû gaây ra nhieàu bieán ñoäng cho heä soá taûi z vaø do ñoù coù nhieàu dao ñoäng. Giaù trò AI lôùn hôn gaây ra söï chaäm treã trong hoài tieáp vaø do ñoù laâu oån ñònh hôn. + söû duïng thao taùc xaùc ñònh quaù taûi thoâng qua ño löôøng chöù khoâng baèng khai baùo: Giaûi thuaät OSU ño möùc taûi hieän haønh vaø moïi dung löôøng khoâng duøng ñöôïc phaân chia cho caùc nguoàn ñang tranh chaáp. Chuùng ta söû duïng toác ñoä do khai baùo ñeå tính toaùn phaân chia baêng thoâng trong tröôøng hôïp ñaëc bieät nhöng söû duïng möùc taûi ñöôïc ño taïi chuyeån maïch ñeå quyeát ñònh taêng hay giaûm toác ñoä. Vì vaäy neáu nguoàn khai baùo khoâng chính xaùc hoaëc thoâng tin töø nguoàn ñaõ loãi thôøi , giaûi thuaät coù theå khoâng ñaït ñöôïc coâng baèng nhöng vaãn ñaït ñuôïc hieäu quaû. + Hoài tieáp löôõng cöïc:
  3. Giaûi thuaät OSU söû duïng hoài tieáp löôõng cöïc goàm hoài tieáp aâm vaø hoài tieáp döông. Hoài tieáp döông yeâu caàu nguoàn taêng toác ñoä phaùt cuûa mình vaø hoài tieáp aâm yeâu caàu nguoàn giaûm toác ñoä phaùt cuûa mình. Vaán ñeà chuû yeáu ñoái vôùi hoài tieáp ñôn cöïc laø möùc taûi thay ñoåi lieân tuïc(thöôøng treân moãi cell) töùc laø khoâng taêng thì giaûm maø khoâng coù traïng thaùi oån ñònh. Ñieàu naøy coù theå khoâng thích hôïp vôùi moät soá öùng duïng (nhö löu thoâng video neùn). Moãi khi hieäu chænh toác ñoä ñoøi hoûi öùng duïng phaûi hieäu chænh thoâng soá cuûa mình. Hoài tieáp löôõng cöïc traùnh ñöôïc nhöõng hieäu chænh khoâng caàn thieát baèng caùch cung caáp nhöõng chæ thò roõ raøng ñeán nguoàn ñeå thay ñoåi möùc taûi. + Ño löôøng döïa treân toác ñoä thay vì döïa treân chieàu daøi haøng ñôïi: Trong khi chieàu daøi haøng ñôïi laø moät chæ ñònh taûi toát cho haøng ñôïi ñöôïc ñieàu khieån theo cöûa soå thì toác ñoä vaøo laø laïi chæ ñònh taûi ñuùng cho haøng ñôïi ñöôïc ñieàu khieån döïa theo toác ñoä. Giaùm saùt toác ñoä vaøo khoâng chæ cung caáp moät chæ cung caáp moäy chæ ñònh möùc taûi toát maø coøn cung caáp moät chæ ñænh chính xaùc veà tình traïng quaù taûi cuõng nhö döôùi taûi. Ví duï, neáu toác ñoä haøng ñôïi laø 20 cell treân giaây trong khi haøng ñôïi chæ coù theå phuïc vuï ñöôïc 10 cell treân giaây. Ñeå hieäu chænh thì trong tröôøng hôïp naøy LAF =2, nghóa laø toác ñoä vaøo phaûi ñöôïc giaûm xuoáng hai laàn. Giaûi thuaät OSU söû duïng toác ñoä vaøo ñeå tính toaùn möùc ñoä quaù taûi vaø hieäu chænh toác ñoä nguoàn. Moãi chuyeån maïch ñeám soá löôïng cell maø noù ñaõ nhaän treân moãi lieân keát trong moãi chu kyø cho tröôùc, tính toaùn toác ñoä vaøo vaø heä soá quaù aûi ñang söû duïng dung löôïng lieân keát (cell/giaây). Giaûi thuaät coá gaéng ñieàu chænh toác ñoä nguoàn baèng moät heä soá baèng vôùi möùc quaù taûi vaø coá gaéng mang möùc quaù taûi xuoáng möùc hôïp lyù caøng nhanh caøng toát.
  4. 3.1.4.7 Giaû thuaät EPRCA+vaø EPRCA+ +: Giaûi thuaät EPRCA+(Enhanced Proportional Rate Control Algorithm) ñöôïc phaùt trieån döïa treân cô sôû giaûi thuaät vôùi moät soá thay ñoåi. Trong ñoù quaù trình phaùt hieän döïa treân söï öôùc ñoaùn thay vì söû duïng giaù trò ngöôõng trong haøng ñôïi cell. Chuyeån maïch tieán haønh ñeám soá cell nhaän ñöôïc trong moät khoaûn thôøi gian ñònh tröôùc. Nguoàn cuoái cuõng ñöôïc trang bò moät boä ñònh thôøi thay cho boä ñeám soá cell RM göûi. Toác ñoä cuûa nguoàn ñöôïc giöõ khoâng ñoåi cho ñeán khi noù nhaän ñöôïc cell BRM mang theo giaù trò toác ñoä töôøng minh ER ñöôïc xaùc ñònh bôûi chuyeån maïch Moät ñaëc ñieåm haáp daãn cuûa giaûi thuaät EPRCA+ laø soá löôïng caùc thoâng soá ñieàu khieån ít vaø deã daøng caøi ñaët bôûi ngöôøi quaûn lí maïng. Nhieàu thoâng soá trong giaûi thuaät EPRCA ñaõ ñöôïc giaûm bôùt trong giaûi thuaät EPRCA+. Hôn nöõa, trong giaûi thuaät EPRAC+ thì giaûi taän duïng ñích(TUB) ñöôïc caøi töï do. TUB cuûa chuyeån maïch coù theå döôùi 95% ñoä taän duïng ñöôøng truyeàn. Do ñoù, kích thöôùc chieàu daøi haøng ñôïi taïi chuyeån maïch nhoû hôn vaø ñoä treã cell thaáp hôn.Maëc duø phaûi toán theâm chi phí cho boä ñònh thôøi vaø baûng VC nhöng EPRCA+ cung caáp ñoä coâng baèng toát hôn, ñoàng thôøi coù ñaùp öùng nhanh hôn EPRCA. Coù moät vaán ñeà ñaõ neâu trong giaûi thuaät EPRCA ñoù laø khi öôùc ñoaùn ACR(Allowed Cell Rate) khoâng toát nguoàn seõ nhanh choùng giaûm toác ñoä vôùi heä soá RDF(Rate Decrease Factor) cho ñeán khi ñaït ñeán MCR(Minimum Cell Rate). Ñieàu naøy laø caàn thieát nhöng seõ maát coâng trong tröôøng hôïp maïng nhanh choùng ñaït ñöôïc traïng thaùi oån ñòng. Moät caûi tieán tieáp theo laø giaûi thuaät EPRCA++. Giaûi thuaät naøy söû duïng moät boä ñeám taïi nguoàn cuoái cho caùc cell FRM(Forward RM cell) thay cho boä ñònh thôøi cuûa giaûi thuaät EPRCA+. Hôn nöõa nguoàn cuoái heä thoáng chæ giaûm toác ñoä ACR khi khoâng coù cell BRM(backward RM cell) trong k.Nrm cell,
  5. trong ñoù k laø moät giaù trò caøi ñaëtvaø Nrm laø soá cell toái ña truyeàn giöõa hai cell RM. Söï thay ñoåi naøy cho pheùp giaûi thuaät EPRCA++ hoaït ñoäng toát hôn EPRCA+, ñaëc bieät trong traïng thaùi quaù ñoä. 3.1.4.8 Giaûi thuaät ERICA(Explicit Rate Indication Congestion Avoidance): Giaûi thuaät ERICA ñöôïc xaây döïng döïa treân yù töôûng cuûa giaûi thuaät OSU. Giôùi haïn chuû yeáu cuûa giaûi thuaät OSU laø khoâng töông thích vôùi caùc tieâu chuaån cuûa ATM Forum vaø trong caùc caáu hìng phöùc taïp thôøi gian hoäi tuï töø caùc ñieàu kieän ban ñaàu tuøy yù ñeán traïng thaùi thieát laäp thì keùo daøi(ñaùp öùng quaù ñoä). Giaûi thuaät ERICA vaø ERICA+ ñaõ khaéc phuïc caùc giôùi haïn cuûa giaûi thuaät OSU trong khi vaãn giöõ ñöôïc caùc ñaëc tính öu vieät cuûa noù. Ngoaøi ra, chuùng laø nhöõng giaûi thuaät mang tính laïc quan coù nghóa laø chuùng phaân caáp toác ñoä ñeå toái öu hoùa hoaït ñoäng quaù ñoä cuõng nhö traïng thaùi xaùc laäp. Do caùc maïng treân thöïc teá thì phaàn lôùn thôøi gian laø ôû trong traïng thaùi quaù ñoä (nguoàn göûi vaø ngöøng göûi , dung löôïng ABR thay ñoåi) neân giaûi thuaät aùp duïng cho caùc chuyeån maïch trong heä thoáng thöïc teá caàn hoaït ñoäng toát ôû caû hai ñieàu kieän xaùc laäp cuõng nhö quaù ñoä. 3.1.4.8.1 Giaûi thuaät ERICA cô baûn: Giaûi thuaät ERICA cô baûn söû duïng caùc thoâng soá sau: + Heä soá taûi z: laø tæ soá giöõa toác ñoä nhaäp(input rate) ñöôïc ño taïi coång(port) vaø dung löôïng ñích(target capacity) taïi ngoõ ra cuûa lieân keát. Noù chæ ñònh möùc taéc ngheõn cuûa lieân keát. Giaù trò quaù taûi cao khoâng ñöôïc mong muoán bôûi vì noù cho bieát taéc ngheõn quaù möùc ; coøn giaù trò quaù taûi thaáp noùi leân lieân keát döôùi ñoä taän duïng. Ñieåm hoaït ñoäng toái öu laø ñieåm maø taïi ñoù heä soá taûi baèng 1. Muïc tieâu cuûa chuyeån maïch laø duy trì maïng taïi löôïng quaù taûi ñôn vò(z=1). Toác ñoä nhaäp ABR z Dung löôïng ABR
  6. + Dung löôïng ABR: Baèng ñoä taän duïng ñích x baêng thoâng lieân keát + Toác ñoä nhaäp: laø giaù trò ñöôïc ño sau moãi khoaûng thôøi gian ñöôïc goïi laø khoaûng thôøi gian trung bình chuyeån maïch (switch averaring interval). Caùc böôùc treân ñöôïc thöïc thi taïi cuoái moãi khoaûng thôøi gian chuyeån maïch. + Ñoä taän duïng ñích: (U-target utiliration) laø phaân soá nhoû hôn 100% cuûa dung löôïng coøn laïi. Giaù trò tieâu bieåu laø 0.9 vaø 0.95. + Heä soá chia seû coâng baèng: (fair share) heä soá chia seû coâng baèng cuûa moãi VC ñöïôc tính nhö sau: Dung löôïng ABR Fair Share  Soá nguoàng kích hoaït Chuyeån maïch cho pheùp chia moãi nguoàn göûi ôû toác ñoä döôùi heä soá chia seû coâng baèng ñeå taêng leân giaù trò naøy(fair share) moãi khi noù göûi hoài tieáp veà nguoàn. Neáu nguoàn khoâng söû duïng heát giaù trò fair share naøy thì chuyeån maïch seû phaân caáp coâng baèng löôïng baêng thoâng coøn laïi cho caùc nguoàn coù theå söû duïng. Ñeå ñaït ñöôïc muïc ñích naøy, chuyeån maïch phaûi tính toaùn thoâng soá sau: CCR (Current Cell Rate) VCShare  z Neáu taát caû caùc VC thay ñoåi toác ñoä cuûa chuùng ñeán giaù trò VCShare thì trong chu kyø voøng maïng keá tieáp chuyeån maïch seû ñaït ñöôïc taûi ñôn vò (z=1). Vì vaäy muïc tieâu cuûa thoâng soá VCShare laø ñöa heä thoáng ñeán ñieåm vaän haønh hieäu quaû , coù theå khoâng caàn thieát phaûi coâng baèng; coøn heä soá chia seû coâng baèng(fair share) nhaèm ñaûm baûo ñoä coâng baèng maø coù theå daãn ñeán quaù taûi(vaän haønh khoâng hieäu quaû). Do ñoù chuùng ta coù theå keát hôïp caû hai thoâng soá naøy ñeå ñöa heä thoáng ñeán ñieåm vaän haønh nhanh nhaát. ER tính toaùn = Max(FairShare, VCShare)
  7. Nguoàn ñöôïc pheùp göûi ôû toác ñoä ít nhaát baèng FairShare trong thôøi gian voøng maïng ñaàu tieân ñeå ñaûm baûo ñoä coâng baèng toái thieåu giöõa caùc nguoàn. Neáu giaù trò VCShare lôùn hôn FairShare nguoàn ñöôïc pheùp göûi ôû toác ñoä VCShare nhaèm ñaûm baûo lieân keát khoâng döôùi ñoä taän duïng. Böôùc naøy cuõng cho pheùp nguoànñaït ñöôïc toác ñoäï coâng baèng max-min. Ñaây laø moät trong nhöõng ñieåm caùch taân cuûa giaûi thuaät ERICA bôûi vì noù caûi thieän ñoä coâng baèng ôû moåi böôùc cho duø ñang trong ñieàu kieän quaù taûi. Giaù trò ER tính toaùn khoâng theå lôùn hôn dung löôïng ABR maø ñaõ ñöôïc ño tröôùc ñoù.do ñoù: ER tính toaùn = Min (ER tính toaùn, dung löôïng ABR) Ñeå ñaûm baûo giaù trò ER taïi ñieåm coå chai ñaït ñeán ngöôõng thì moãi chuyeån maïch phaûi tính toaùn giaù trò toái thieåu cuûa ER maø noù ñaõ tính tröôùc kia vaø ER trong cell RM. Giaù trò naøy ñöôïc cheøn vaøo tröôøng ER trong cell RM vôùi: ER trong cell RM = Min(ER trong cell RM, ER tính toaùn) Löu ñoà cuûa giaûi thuaät ERICA cô baûn ñöôïc ñöa ra trong hình trang beân. Löu ñoà chæ ra töôøng böôùc thöïc hieän ôû ba söï kieän sau: taïi cuoái moãi khoaûng thôøi gian trung bình, khi nhaän moät cell(cell döõ lieäu hoaëc cell RM) vaø khi nhaän moät cell BRM. Giaûi thuaät ERICA cô baûn coù moät soá nhöôïc ñieåm: + Khoâng ñaït ñöôïc ñoäï coâng baèng max-min trong moät soá tröôøng hôïp phöùc taïp. + Coù theå daãn ñeán toác ñoä vaø haøng ñôïi taêng ñoät ngoät khi coù söï baát ñoàng boä trong chuyeån maïch. Moät soá thay ñoåi trong giaûi thuaät ERICA môû roäng seõ giaûi quyeát vaán ñeà naøy.

CÓ THỂ BẠN MUỐN DOWNLOAD

Đồng bộ tài khoản