Điều khiển lưu lượng và tắc nghẽn trong mạng atm

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. 3.1.4.8.2 Giaûi thuaät ERICA môû roäng: Nhöôïc ñieåm thöù nhaát cuûa giaûi thuaät ERICA cô baûn laø khi ba ñieàu kieän sau xaûy ra ñoàng thôøi noù seõ khoâng hoäi tuï veà coâng baèng max-min: + Heä soá taûi z=1. + Coù vaøi nguoàn bò taéc ngheõn coå chai ôû phía tröôùc. +Toác ñoä hieän haønh CCR cho taát caû caùc nguoàn khoâng bò ngheõn coå chia coøn laïi lôùn hôn FairShare. Neáu ñieàu naøy xaûy ra thì heä thoáng vaãn duy trì traïng thaùi hieän haønh cuûa noù bôûi vì giaù trò CRR/z (VCShare) lôùn hôn FairShare cho caùc nguoàn khoâng taéc ngheõn coå chai. Ñeå giaûi quyeát vaán ñeà naøy, giaûi thuaät ERICA môû roäng ñaõ theâm vaøo moät bieán goïi laø MaxAllocPreviuos ñeå giöõ ñoä phaân caáp lôùn nhaát trong khoaûng thôøi gian tröôùc vaø moät bieán MaxAllocCurrent ñeå tích luyõ ñoä phaân caáp lôùn nhaát trong khoaûng thôøi gian trung bình chuyeån maïch hieän haønh. Hai bieán naøy ñaûm baûo taát caû caùc nguoàn thích hôïp coù theå nhaän ñöôïc ñoä phaân caáp cao. Cuoái khoaûng thôøi gian trung bình Ñeám soá nguoàn kích hoaït trong khoaûng thôûi gian AI Dung löôïng ABR = Ñoä taän duïng ñích x Baêng thoâng lieân keát. Toác ñoä nhaäp ABR = Soá cell ABR ñeám ñöôïc / AI Heä soá taûi z = Toác ñoä nhaäp ABR / Dung löôïng ABR FairShare = Dung löôïng ABR/ Soá nguoàn kích hoaït trong khoaûng thôøi gian AI Khôûi ñoäng laïi soá cell ABR nhaäp vaø hoaït ñoäng cuûa VC Step 1 Step 2 Step 3 Step 4 Step 5 Khi nhaän moät cell Ñaùnh daáu VC kích hoaït Ñeám soá cell nhaäp Step 6 Step 7 Khi nhaän cell BRM VC’s Share hieän taïi = CCR cuûa VC / Heä soá taûi ER tính toaùn = Max( FairShare , VC’s FairShare ER tính toaùn = Min( ER tính toaùn, Dung löôïng ABR) ER trong cell RM = Min( ER tính toaùn, ER trong cell RM) Cheøn ER vaøo cell BRM Step 8 Step 9 Step 10 Step 11 Hình moâ taû löu ñoà giaûi thuaät ERICA cô baûn Trong giaûi thuaät ERICA môû roäng böôùc 9 ôû giaûi thuaät ERICA cô baûn ñöôïc thay ñoåi nhö hình trang beân. Ta söû duïng theâm haèng soá d laø moät soá nhoû hôn 1. Neáu z > 1+ d, thì chuùng ta söû duïng giaûi thuaät ERICA cô baûn. Neáu z £ 1+ d, ER ñöôïc tính nhö sau: ER tính toaùn = Max(FairShare, VCShare,MaxAllocPrevious) Ñieåm quan troïng laø thoâng soá VCShare chæ ñöôïc söû duïng ñeå ñaït hieäu quaû, coøn ñoä coâng baèng chæ ñaït ñöôïc baèng caùch cho caùc nguoàn ñang tranh giaønh baêng thoâng coù moät toác ñoä baèng nhau. Khôûi ñoäng MaxAllocPrevious :=0 MaxAllocCurrent := FairShare Cuoái khoaûng thôøi gian trung bình Laøm töø böôùc 1 ñeán 5 MaxAllocPrevious:= MaxAllocCurrent MaxAllocCurrent := FairShare Sau böôùc 8 Z > 1+d ER tính toaùn := Max(FairShare,VC’s Share hieän taïi) ER tính toaùn := Max( FairShare, VC’s Share hieän taïi, MaxAllocCurrent) Ñ S Laøm böôùc 10 Step 9 MaxAllocCurrent := Max(MaxAllocCurrent, ER tính toaùn Hình moâ taû giaûi thuaät ERICA môû roäng Giaûi phaùp cuûa chuùng ta laø phaân caáp ñoàng ñeàu cho caùc nguoàn trong thôøi gian döôùi taûi vaø chia CCR cuûa caùc nguoàn cho cuøng moät giaù trò z trong thôøi gian quaù taûi xaûy ra sau ñoù ñeå ñöa chuùng ñeán coâng baèng max-min. Heä thoáng ñöôïc xem laø ôû traïng thaùi quaù taûi khi heä soá taûi z ³ 1+ d. Muïc ñích cuûa vieäc giôùi thieäu thoâng soá d laø baét buoäc phaân caáp toác ñoä gioáng nhau khi heä soá taûi dao ñoäng quanh giaù trò 1, vì vaäy traùnh ñöôïc dao ñoäng toác ñoä khoâng mong muoán. Nhöôïc ñieåm thöù hai naûy sinh khi caùc cell BRM ñeán chuyeån maïch moät caùch baát ñoàng boä töø caùc nguoàn khaùc nhau daãn ñeán söï taêng ñoät ngoät trong ñoà thò ACR vaø khi nguoàn coù cell BRM ñeán chuyeån maïch chaäm hôn vaø nhaän ñöôïc ñoä chia seû coâng baèng cuûa noù thì haøng ñôïi taêng ñoät ngoät. Vaán ñeà naøy coù theå ñöôïc giaûi quyeát baèng caùch chia seû coâng baèng luùc ñaàu ñeå traùnh quaù taûi quaù ñoä. Khi ER tính toaùn lôùn hôn giaù trò fair share vaø toác ñoä nguoàn ñang taêng töø giaù tri CCR döôùi möùc fair share thì chuùng ta giôùi haïn toác ñoä taêng naøy ñeán giaù trò fair share. Chuyeån maïch coù theå quyeát ñònh khoâng ñöa hoài tieáp môùi khoâng ñöa hoài tieáp môùi veà nguoàn naøy trong moät khoaûng thôøi gian ño löôøng. Vieäc tính toaùn sau seõ ñöôïc ñöa theâm vaøo giaûi thuaät chuyeån maïch sau khi tính “ ER tính toaùn”: IF (( CCR < FairShare) AND ( ER tính toaùn ³ FairShare)) THEN ER tính toaùn := FairShare Chuùng ta cuõng coù theå khoâng cho pheùp hoài tieáp veà nguoàn naøy trong moät khoaûng thôøi gian ño löôøng. “ ER trong cell RM” vaãn ñöôïc tính nhö tröôùc. Choïn löïa caùc thoâng soá cho giaûi thuaät ERICA: Haàu heát caùc giaûi thuaät ñieàu khieån ñeàu cung caáp cho nhaø ñieàu haønh moät soá thoâng soá ñeå thích öùng hoaït ñoäng cuûa giaûi thuaät söû duïng. Moät giaûi thuaät toát phaûi coù ít thoâng soá nhöng cung caáp ñaày ñuû caùc möùc ñieàu khieån. Caùc thoâng soá naøy khoâng ñöôïc nhaïy vôùi nhöõng thay ñoåi nhoû trong maïng. Giaûi thuaät ERICA cung caáp moät soá thoâng soá raát deã daøng thieát laäp , maø vôùi moät söï maát phoái hôïp nheï giöõa caùc thoâng soá naøy vaãn khoâng laøm giaûm suùt hoaït ñoäng cuûa giaûi thuaät. Caùc thoâng soá naøy laø ñoä taän duïng ñích U(target Utilization) vaø khoaûng thôøi gian ño löôøng chuyeån maïch. + Ñoä taän duïng ñích U: Ñoä taän duïng ñích quyeát ñònh ñoä taän duïng ñöôøng truyeàn ôû traïng thaùi thieát laäp. Neáu toác ñoä nhaäp lôùn hôn ñoä taän duïng ñích x dung löôïng lieân keát thì chuyeån maïch yeâu caàu nguoàn giaûm toác ñoä ñeå ñöa toång toác ñoä nhaäp veà giaù trò mong muoán. Neáu haøng ñôïi taïi chuyeån maïch xuaát hieän taûi quaù ñoä thì (1-U) x Dung löôïng lieân keát ñöôïc söû duïng ñeå ruùt haøng ñôïi. Ngöôøi ta khoâng mong muoán ñoä taän duïng ñích coù giaù trò quaù lôùn bôûi vì noù daãn ñeán haøng ñôïi daøi vaø maát; nhöng neáu ñoä taän duïng ñích thaáp seõ khoâng taän duïng heát ñöôøng truyeàn. Aûnh höôûng cuûa ñoä taän duïng ñích phuï thuoäc vaøo ñoä treã hoài tieáp cuûa maïng. Quaù taûi quaù ñoä coù khaû naêng daãn ñeán haøng ñôïi daøi caøng daøi ñoái vôùi maïng coù ñoä treã hoài tieáp caøng lôùn. Do ñoù, ñoái vôùi maïng coù ñoä trì hoaûn lôùn thöôøng mong muoán ñoä taän duïng ñích nhoû. Thöïc teá cho thaáy giaù trò toái öu cuûa ñoä taän duïng ñích laø 0.95 cho maïng LAN vaø 0.9 cho maïng WAN. Khi löu thoâng coù tính chuøm cao thì ñoä taän duïng ñích nhoû seõ caûi thieän hoaït ñoäng cuûa giaûi thuaät. + Khoaûng thôøi gian trung bình chuyeån maïch AI: Khoaûng thôøi gian trung bình chuyeån maïch hay khoaûng thôøi gian ño löôøng quyeát ñònh ñoä chính xaùc cuûa hoài tieáp. Khoaûng thôøi gian naøy ñöôïc duøng ñeå ño möùa taûi , dung löôïng lieân keát vaø soá VC kích hoaït. Chieàu daøi khoaûng thôøi gian ño löôøng tao ra maâu thuaãn giöõa ñoä chính xaùc vaø hoaït ñoäng cuûa traïng thaùi xaùc laäp. Giaûi thuaät ERICA ño löôøng caùc thoâng soá caàn thieát sau khoaûng thôøi gian trung bình vaø söû duïng caùc giaù trò ño löôøng naøy ñeå tính toaùn hoài tieáp trong khoaûng thôøi gian trung bình keá tieáp. Vieäc laáy trung bình giuùp laøm trôn ñoä bieán ñoäng trong ño löôøng. Tuy nhieân, chieàu daøi khoaûng thôøi gian trung bình giôùi haïn löôïng bieán ñoäng coù theå ñöôïc loaïi tröø. Noù cuõng quyeát ñònh toác ñoä hoài tieáp ñöa veà nguoàn bôûi vì giaûi thuaät ERICA chæ ñöa toái ña moät hoài tieáp trong moät khoaûng thôøi gian ño löôøng. Khoaûng thôøi gian ño löôøng caøng nhoû thì ñoä bieán ñoäng caøng lôùn vaø coù theå ñaùnh giaù khoâng ñuùng möùc caùc thoâng soá ño löôøng. Heä soá taûi vaø dung löôïng coù saün laø caùc bieán ngaãu nhieân maø ñoä bieán ñoäng cuûa noù phuï thuoäc vaøo chieàu daøi cuûa khoaûng thôøi gian trung bình. Trong thöïc teá, khoaûng thôøi gian caàn thieát ñeå ño soá nguoàn kích hoaït cuõng ñuû ñeå ño heä soá taûi vaø dung löôïng coù saün. Caùc thoâng soá ñöôïc laáy trung bình naøy khaù chính xaùc vôùi loãi chæ khoaûng 1 cell / khoaûng thôøi gian trung bình. Thieát laäp ñoä taän duïng ñích döôùi 100% ñeå ruùt haøng ñôïi do loãi trong ño löôøng cuûa taát caû caùc thoâng soá. Baát cöù khi naøo giaûi thuaät gaëp phaûi maâu thuaãn do loãi trong ño löôøng thì chuùng ta phaûi giaûm thoâng soá ñoä taän duïng ñích. 3.1.4.9 Giaûi thuaät ERICA+: 3.1.4.9.1 Chieàu daøi haøng ñôïi laø moät thoâng soá ño löôøng thöù caáp: ERICA+ laø moät boå sung cho giaûi thuaät ERICA. Trong phaàn naøy vaø phaàn sau chuùng ta seõ mieâu taû caùc muïc tieâu, ñieåm vaän haønh ñích, giaûi thuaät vaø vieäc thieát laäp thoâng soá cho ERICA+. ERICA phuï thuoäc vaøo vieäc ño löôøng caùc thoâng soá nhö heä soá taûi vaø soá nguoán ABR kích hoaït. Neáu trong ño löôøng coù nhieàu loãi vaø ñoä taän duïng ñích ñöôïc thieát laäp quaù cao giaûi thuaät ERICA coù theå khoâng hoäi tuï coù nghóa laø chieàu daøi haøng ñôïi trôû neân khoâng coù giôùi haïn vaø dung löôïng ñeå ruùt haøng ñôïi trôû neân khoâng ñuû. Giaûi phaùp trong tröôøng hôïp naøy laø thieát laäp ñoä taän duïng ñích ñeán moät giaù trò nhoû hôn, cho pheùp nhieàu baêng thoâng hôn ñeå ruùt haøng ñôïi. Moät söï naâng caáp ñôn giaûn cho ERICA laø phaûi coù ngöôõng haøng ñôïi vaø giaûm ñoä taän duïng ñích neáu haøng ñôïi vöôït quaù ngöôõng naøy. Moät khi ñoä taän duïng ñích thaáp haøng ñôïi seõ ñöôïc ruùt nhanh choùng. Do ñoù söï boå sung naøy seõ duy trì ñoä taän duïng cao khi haøng ñôïi nhoû vaø ruùt haøng ñôïi nhanh choùng khi chuùng ñaày. Vì vaäy, chuùng ta caàn thieát phaûi söû duïng chieàu daøi haøng ñôïi nhö laø thoâng soá thöù caáp (thoâng soá sô caáp laø toác ñoä nhaäp). Trong giaûi thuaät ERICA, chuùng ta khoâng xem chieàu daøi haøng ñôïi hoaúc ñoä treã haøng ñôïi laø moät thoâng soá do ñoù khoâng ñöa chæ ñònh toác ñoä chính xaùc cuûa nguoàn. Trong giaûi thuaät ERICA+, söï phaân chia toác ñoä chính xaùc phuï thuoäc vaøo toång toác ñoä nhaäp hôn laø chieàu daøi haøng ñôïi. Tuy nhieân chuùng ta nhaän thaáy coù hai vaán ñeà veà haøng ñôïi : thöù nhaát haøng ñôïi khaùc 0 nguï yù raèng ñoä taän duïng laø 100%; thöù hai, heä thoáng vôùi haøng ñôïi quaù daøi seõ ñi xa ñieåm vaän haønh mong muoán. Vì vaäy trong giaûi thuaät ERICA+, neáu toác ñoä nhaäp vaø haøng ñôïi daøi ta caàn döï tröõ nhieàu dung löôïng hôn ñeå ruùt haøng ñôïi vaø phaân caáp toác ñoä moät caùch deø daët cho ñeán khi haøng ñôïi ñöôïc ñieàu khieån. Ñoái vôùi chieàu daøi haøng ñôïi chuùng ta vaãn duøng haøm lieân tuïc theo quy luaät thieát keá cuûa ERICA. Bôûi vì hoài tieáp veà nguoàn coù tính ñeàu ñaën(khi haøng ñôïi ñöôïc duy trì) do ñoù söï phaân caáp bôûi caùc haøm lieân tuïc seõ giaùm saùt ñöôïc hoaït ñoäng cuûa haøng ñôïi vaø phaûn aùnh noù trong phaân caáp toác ñoä. 3.1.4.9.2 ERICA+ vôùi ñoä taän duïng 100% vaø ruùt haøng ñôïi nhanh: Giaûi thuaät ERICA ñaït ñöôïc ñoä taän duïng cao ôû traïng thaùi thieát laäp nhöng ñoä taän duïng naøy ñöôïc giôùi haïn bôûi thoâng soá ñoä taän duïng ñích. Ñoái vôùi caùc ñöôøng truyeàn ñaét tieàn, chuùng ta mong muoán duy trì ñoä taän duïng naøy ôû möùc 100%. Phöông phaùp ñeå ñaït ñoä taän duïng 100% ôû traïng thaùi xaùc laäp vaø ruùt haøng ñôïi nhanh laø thay ñoåi toác ñoä ABR ñích moät caùch linh ñoäng. Trong thôøi gian xaùc laäp, toác ñoä ABR ñích ñaït ñöôïc laø 100% vaø giaù trò naøy seõ nhoû hôn trong luùc quaù taûi quaù ñoä. Heä soá taûi caøng cao daãn ñeán toác ñoä ñích caøng thaáp(do ñoù ruùt haøng ñôïi nhanh hôn). Noùi caùch khaùc, Toác ñoä ñích ABR = f ( chieàu daøi haøng ñôïi, toác ñoä cuûa lieân keát, toác ñoä VBR) Haøm treân phaûi laø haøm giaûm theo chieàu daøi haøng ñôïi. Chuù yù raèng giaûi thuaät ERICA coù ñoä taän duïng ñích coá ñònh coù nghóa laø toác ñoä ruùt haøng ñôïi ñoäc laäp vôùi kích thöôùc haøng ñôïi. 3.1.4.9.3 ERICA+: duy trì moät “tuùi” (pocket) haøng ñôïi: Dung löôïng ABR bieán ñoåi moät caùch linh ñoäng do söï xuaát hieän cuûa caùc lôùp dòch vuï coù ñoä öu tieân cao hôn (nhö CBR vaø VBR). Vì vaäy, neáu caùc lôùp dòch vuï naøy khoâng toàn taïi trong moät khoaûng thôøi gian ngaén (coù theå nhoû hôn ñoä treõ hoài tieáp) thì dung löôïng coøn laïi seõ khoâng ñöôïc taän duïng heát. Trong caùc tröôøng hôïp nhö vaäy, chuùng ta caàn coù moät “tuùi” ñöïng ñaày caùc cell ABR ñeå söõ duïng dung löôïng coøn laïi trong khi caùc cell RM ñang ñöa thoâng tin môùi veà nguoàn vaø yeâu caàu chuùng taêng toác ñoä. Moät phöông phaùp ñeå ñaït ñöôïc muïc ñích naøy laø phaûi ñieàu khieån caùc haøng ñôïi veà “chieàu daøi haøng ñôïi ñích” (target queue length). ÔÛ traïng thaùi xaùc laäp ñöôøng truyeàn ñöôïc taän duïng 100% vaø chieàu daøi haøng ñôïi baèng vôùi chieàu daøi haøng ñôïi ñích maø noù laø “ tuøi “ haøng ñôïi maø ta mong muoán. Neáu chieàu daøi haøng ñôïi rôùt xuoáng giaù trò naøy thì caùc nguoàn ñöôïc khuyeán khích taêng toác ñoä vaø ngöôïc laïi. Noùi caùch khaùc: Toác ñoä ñích = f(chieàu daøi haøng ñôïi, chieàu daøi haøng ñôïi ñích, toác ñoä lieân keát, toác ñoä VBR) 3.1.4.9.4 ERICA+ vôùi khaû naêng ñaït ñeán caùc toác ñoä lieân keát khaùc nhau: Haøm treân khoâng theå ñaït ñeán caùc toác ñoä lieân keát khaùc nhau do chieàu daøi haøng ñôïi tính theo cell seõ chuyeån sang caùc thôøi gian ruùt khaùc nhau ñoái vôùi caùc toác ñoä truyeàn khaùc nhau. Ví duï ñoái vôùi truyeàn T1, chieàu daøi haøng ñôïi laø 5 coù theå xem laø lôùn, trong khi chieàu daøi haøng ñôïi laø 50 ñoái vôùi ñöôøng truyeàn OC-3 ñöôïc xem laø nhoû. Vaán ñeà naøy khaù quan troïng do baûn chaát bieán ñoåi cuûa dung löôïng ABR, ñaëc bieät khi coù söï xuaát hieän cuûa caùc nguoàn VBR. Ñeå coù ñöôïc khaû naêng ñaït ñeán caùc toác ñoä lieân keát khaùc nhau (scalability to various link speeds), chuùng ta caàn phaûi ño taát caû chieàu daøi haøng ñôïi theo ñôn vò thôøi gian hôn laø ño theo cell. Tuy nhieân, haøng ñôïi laø thoâng soá duy nhaát coù theå ño löôøng tröïc tieáp taïi chuyeån maïch (ño theo cell). Ñoä treã haøng ñôïi sau ñoù ñöôïc öôùc ñoaùn baèng caùch söû duïng giaù trò dung löôïng ABR ño ñöôïc. Haøm toác ñoä ñích treân seõ trôû thaønh nhö sau: Toác ñoä ñích = f (ñoä treã haøng ñôïi, ñoä treã haøng ñôïi ñích, toác ñoä lieân keát, toác ñoä VBR) Trong caùc phaàn sau chuùng ta seõ ñònh nghóa vaø moâ taû moät haøm maåu ñeå tính toaùn toác ñoä ñích. 3.1.4.9.5 ERICA+ vôùi ñieåm vaän haønh muïc tieâu: Giaûi thuaät ERICA+ söû duïng moät ñieåm vaän haønh muïc tieâu môùi naèm giöõa ñieåm “khuyûu” (knee) vaø ñieåm “vaùch” (cliff). Ñieåm vaän haønh muïc tieâu môùi coù ñoä taän duïng 100% vaø ñoä trì hoaûn haøng ñôïi khaùc 0 coá ñònh. Ñieåm naøy khaùc vôùi ñieåm “khuyûu” (trong traùnh taéc ngheõn coù ñoä thoâng suaát 100% vaø ñoä trì hoaûn toái thieåu) ôû choå noù coù muïc tieâu ñoä treã khaùc 0 coá ñònh. Ñoù laø do ñoä treã haøng ñôïi taïi ñieåm vaän haønh luoân khaùc khoâng. Chuù yù raèng ñoä taän duïng duy trì 100% khi haøng ñôïi khaùc o vaø vaãn duy trì ôû möùc 100% cho duø coù traïng thaùi döôùi taûi ngaén trong taûi nhaäp vaøo hoaëc dung löôïng xuaát taêng. Giaù trò haøng ñôïi khaùc 0 ôû traïng thaùi xaùc laäp ñeå chæ ra raèng heä thoáng ñang ôû trong traïng thaùi caân baèng khoâng oån ñònh. Khi coù quaù taûi quaù ñoä haøng ñôïi seõ taêng ñoät ngoät. Ngöôïc laïi giaûi thuaät ERICA coù theå cho pheùp löôïng taêng taûi nhoû (töø 5% ñeán 10%) maø khoâng taêng chieàu daøi haøng ñôïi. Yeâu caàu cuûa giaûi thuaät ERICA+ laø phaûi duy trì traïng thaùi caân baèng khoâng oån ñònh vôùi haøng ñôïi khaùc khoâng vaø ñoä taän duïng 100%. Ñaëc bieät khi ñoä treã haøng ñôïi giaûm xuoáng giaù trò muïc tieâu To; ERICA+ taêng ñoä phaân caáp cho VC ñeå ñaït ñeán ñoä treã toái öu. Töông töï , khi ñoä treã haøng ñôïi taêng vöôït quaù To, phaân caáp cho VC bò giaûm xuoáng vaø dung löôïng theâm vaøo ñöôïc söû duïng ñeå ruùt haøng ñôïi trong chu kyø keá tieáp. Khi ñoä treã haøng ñôïi baèng To, 100% dung löôïng ABR ñöôïc phaân caáp cho caùc VC. Vì vaäy, ERICA+ giôùi thieäu moät thoâng soá môùi laø T0 thay theá cho thoâng soá ñoä taän duïng ñích trong giaûi thuaät ERICA. 3.1.4.9.6 Nhöõng thay ñoåi cuûa giaûi thuaät ERICA+: Nhö ñaõ ñeà caäp töø tröôùc, giaûi thuaät ERICA+ laø boå sung cho giaûi thuaät ERICA vaø coù nhöõng thay ñoåi sau: + Ñoä taän duïng ñöôøng truyeàn khoâng coøn laø muïc tieâu coá ñònh ôû möùc ñoä taän duïng ñích TU nhö trong ERICA. Thay vaøo ñoù dung löôïng ñöôøng truyeàn baèng toång dung löôïng ABR vaø dung löôïng VBR. + Dung löôïng ABR ñích laø moät phaân soá cuûa dung löôïng toång ABR: Dung löôïng ABR ñích ß f (Tq) x Dung löôïng toång ABR Haøm f (Tq) phaûi thoûa maûn caùc ñieàu kieän sau: a) f (Tq) ³ 1, khi ñoä treã haøng ñôïi Tq = 0. Luùc naøy haøng ñôïi ñöôïc pheùp taêng vaø Tq coù theå ñaït ñeán T0, ñaây laø giaù trò ngöôõng. Caùch choïn löïa ñôn giaûn laø giöõ giaù trò naøy baèng 1. Haøng ñôïi taêng do caùc loãi nheï trong ño löôøng. Moät phöông phaùp khaùc laø söû duïng moät haøm tuyeán tính vôùi heä soá goùc nhoû. Chuù yù raèng chuùng ta khoâng neân söû duïng haøm taêng maïnh (aggressive increase function). Do ñoä treã haøng ñôïi laø moät thoâng soá coù tính bieán ñoäng cao neân vôùi moät söï thay ñoåi nhoû trong giaù trò ñoä treã coù theå gaây ra söï thay ñoåi lôùn trong phaân caáp toác ñoä vaø coù theå daãn ñeán maát oån ñòng. b) f (Tq) < 1 , khi ñoä treã haøng ñôïi lôùn hôn T0. Luùc naøy haøng ñôïi baét buoäc phaûi giaûm vaø Tq xuoáng T0. Bôûi vì chieàu daøi haøng ñôïi taêng laø do caùc chuøm löu thoâng neân so vôùi tröôøng hôïp treân (ta döï ñoaùn dung löôïng cao hôn dung löôïng coù saün) trong tröôøng hôïp naøy ta caàn moät cô cheá ñieàu khieån cöùng raén hôn. Do chuùng ta döï ñoaùn dung löôïng thaáp hôn dung löôïng coù saün neân phaàn dung löôïng coøn laïi seõ ñöôïc söû duïng ñeå ruùt haøng ñôïi. c) Neáu haøng ñôïi taêng voâ taän thì chuùng ta mong muoán f (Tq) veà 0. Nhöng giaù trò f (Tq) baèng 0 hoaëc raát thaáp thì dung löôïng ABR khoâng theå chaáp nhaän ñöôïc; vì vaäy chuùng ta ñaët moät giaù trò ngöôõng (cutoff value) treân dung löôïng phaân caáp ñeå ruùt haøng ñôïi. Giaù trò ngöôõng naøy ñöôïc moâ taû bôûi thoâng soá goïi laø “heä soá giôùi haïn ruùt haøng ñôïi” QDLF (Queue Drain Limit Factor). Trong thöïc teá, QDLF = 0.5 laø thích hôïp. d) Khi ñoä treã haøng ñôïi Tq = To thì f (Tq) =1. Chuùng ta coù theå choïn f (Tq) laø haøm böôùc (step function), ñoù laø haøm giaûm dung löôïng theo töøng böôùc (xuoáng ñeán giaù trò ngöôõng) khi ñoä treã haøng ñôïi vöôït qua giaù trò ngöôõng. Haøm böôùc ñöôïc minh hoïa trong hình sau: Hình moâ taû haøm böôùc cho ERICA+ Haøm böôùc coù theå ñöôïc thay theá baèng haøm tuyeán tính töøng ñoaïn nhö hình sau: Haøm tuyeán tính töøng ñoaïn cho ERICA+ Haøm treã sau ñaây ñöôïc duøng thay cho caùch duøng ngöôõng ñôn ñeå taêng vaø giaûm dung löôïng. Noù duøng moät ngöôõng ñeå taêng dung löôïng vaø moät ngöôõng khaùc ñeå giaûm dung löôïng. Tuy nhieân, caùc haøm naøy ñoøi hoûi ña ngöôõng (ña thoâng soá) do ñoä treã haøng ñôïi coù tính bieán ñoåi cao. Hôn nöõa, caùc ngöôõng laø caùc ñieåm giaùn ñoaïn, coù nghóa laø hoài tieáp ñöôïc ñöa veà nguoàn seõ raát khaùc nhau neáu heä thoáng chuyeån töø ngöôõng naøy sang ngöôõng khaùc. Tuy nhieân, chuùng ta coù theå duøng haøm chæ vôùi hai thoâng soá cho hai vuøng khaùc nhau: (0,Qo) vaø (Qo, voâ cöïc). Hai haøm cung caáp söï ñieàu khieån cöùng raén toát nhaát khi haøng ñôïi taêng theo daïng cuûa hình hyperbol vuoâng goùc (rectangular hyperbol) vaø haøm muõ aâm (negative exponentail), trong ñoù haøm hyperbol vuoâng goùc laø haøm ñôn giaûn nhaát. Bôûi vì phaàn T < T0 yeâu caàu ñieàu khieån nheï hôn neân chuùng ta coù theå coù moät haøm hyperbol khaùc cho vuøng ñoù; haøm naøy yeâu caàu theâm moät thoâng soá cho vuøng naøy. Giaûi thuaät ñieàu khieån haøng ñôïi söû duïng thôøi gian trì hoaõn haøng ñôïi nhö moät giaù trò ngöôõng. Vì vaäy, tuøyï thuoäc vaøo dung löôïng haøng ñôïi coù saün luùc naøy giaù trò T0 chuyeån sang haøng ñôïi Qo nhö sau: Qo = Toång dung löôïng ABR x T0 Trong phaàn sau, chuùng ta seõ chæ xem xeùt Qo vaø haøng ñôïi maø Qo laø moät bieán phuï thuoäc vaøo dung löôïng coù saün. Thoâng soá coá ñònh laø T0 vaø haøm ñieàu khieån haøng ñôïi nhö sau: , khi q > Qo vaø , khi 0 £ q £ Qo Chuù yù raèng f(Tq) laø moät soá naèm giöõa 1 vaø 0 trong khoaûng töø Qo ñeán voâ cuøng vaø naèm giöõa b vaø 1 trong khoaûng töø 0 ñeán Qo. Caû hai ñöôøng naøy giao nhau taïi Qo vaø khi ñoù f(Tq) = 1. Haøm naøy coù caän döôùi laø heä soá giôùi haïn ruùt haøng ñôïi QDLF. , Khi q > Qo Hình moâ taû haøm ñieàu khieån haøng ñôïi cho ERICA+ 3.1.4.9.7 Aûnh höôûng cuûa söï bieán ñoäng leân giaûi thuaät ERICA: ERICA+ tính toaùn dung löôïng ABR ñích laø keát quaû cuûa f(Tq) vaø dung löôïng ABR. Ñaây ñeàu laø hai thoâng soá bieán ñoåi (bieán ngaãu nhieân) vaø keát quaû cuûa pheùp tính vôùi hai bieán ngaãu nhieân (ví duï A vaø B) laø moät bieán ngaãu nhieân coù ñoä bieán ñoäng lôùn hôn A vaø B. Hoài tieáp trôû neân ít tin caäy hôn khi dung löôïng taêng. Ví duï heä soá taûi phuï thuoäc vaøo dung löôïng ABR vaø ñöôïc söû duïng trong coâng thöùc ñeå ñaït coâng baèng max-min. Do giaûi thuaät ERIAC+ thay ñoåi dung löôïng ABR döïa treân chieàu daøi haøng ñôïi, coâng thöùc naøy caàn phaûi chòu chòu ñöïng caùc thay ñoåi nhoû trong heä soá taûi. Thaät vaäy, coâng thöùc aùp duïng haøm treã ñeå loaïi tröø bieán ñoäng do heä thoáng gaây ra. Caùc kyõ thuaät nhö haøm treã vaø laáy trung bình coù theå chòu ñöïng ñoä bieán ñoäng nhoû neân chuùng ta caàn giaûm bieán ñoäng trong dung löôïng ABR ñích. Tröôùc heát chuùng ta xem xeùt thoâng soá dung löôïng ABR. Thoâng soá naøy ñöôïc öôùc löôïng sau moãi khoaûng thôøi gian trung bình. Moät quaù trình öôùc löôïng ñôn giaûn coù theå keá thöøa töø vieäc ñeám soá cell VBR ñöôïc göûi, tính toaùn dung löôïng VBR vaø tröø noù ra khoûi dung löôïng ñöôøng truyeàn. Quaù trình naøy coù theå bò loãi moät cell trong moät khoaûng thôøi gian trung bình. Loãi naøy coù theå ñöôïc toái thieåu baèng caùch troïn khoaûng thôøi gian trung bình daøi hôn. Tuy nhieân dung löôïng ABR ño ñöôïc bieán ñoäng ít hôn chieàu daøi haøng ñôïi töùc thôøi. Ñoù laø do trung bình bieán ñoäng caùc maãu ít hôn chính caùc maãu ñoù vaø dung löôïng ABR ñöôïc laáy trung bình sau moãi khoaûng thôøi gian trong khi chieàu daøi haøng ñôïi thì khoâng. Giaù trò Qo = dung löôïng ABR x T0 bieán ñoäng gioáng nhö dung löôïng ABR. Baây giôø chuùng ta xem xeùt haøm f(Tq). Haøm naøy bò giôùi haïn döôùi bôûi QDLF vaø giôùi haïn treân bôûi b. Vì vaäy giaù trò cuûa noù naèm trong khoaûng (QDLF, b) hoaëc trong thöïc teá thì naèm trong khoaûng (0.5,1.05).Hôn nöõa noù cuõng bieán ñoäng do phuï thuoäc vaøo chieàu daøi haøng ñôïi q vaø Qo. bôûi vì haøm naøy coù tæ soá giöõa Qo vaø q neân noù bieán ñoäng lôùn hôn hai thoâng soá naøy. Moät phöông phaùp ñeå giaûm bieán ñoäng laø söû duïng giaù trò trung bình cuûa chieàu daøi haøng ñôïi (q), thay theá cho chieàu daøi haøng ñôïi töùc thôøi. Chuùng ta coù theå ñôn giaûn laáy trung bình haøng ñôïi taïi ñieåm ñaàu vaø ñieåm cuoái cuûa khoaûng thôøi gian ño löôøng. Caùch laáy trung bình naøy thích hôïp khi khoaûng thôøi gian ño löôøng nhoû. Neáu khoaûng thôøi gian ño löôøng daøi, moät phöông phaùp laáy trung bình toát hôn laø laáy maãu chieàu daøi haøng ñôïi trong suoát khoaûng thôøi gian ñoù vaø laáy trung bình caùc maãu naøy. Vieäc laáy maãu haøng ñôïi coù theå thöïc hieän ôû cheá ñoä neàn Moät phöông phaùp khaùc ñeå giaûm bieán ñoäng laø xaùc ñònh haèng soá Qo thay vì xaùc ñònh To neáu ñoä treã ñích naèm trong khoaûng coù theå chaáp nhaän ñöôïc. 3.1.4.9.8 Choïn löïa caùc thoâng soá ERICA+: Haøm ñieàu khieån haøng ñôïi trong giaûi thuaät ERICA+ coù 4 thoâng soá: To,a,b vaø QDLF. Trong phaàn naøy chuùng ta seõ giaûi thích caùch choïn giaù trò cho cho caùc thoâng soá vaø caùc kyõ thuaät ñeå giaûm bieán ñoäng giaù trò haøm f(Tq). Haøm f(Tq) coù ba phaàn : (1) haøm hyperbol moâ taû bôûi thoâng soá b (goïi laø b-hyperbol) coù ñoä trì hoaõn haøng ñôïi töø 0 ñeán To, (2) haøm a-hyperbol coù ñoä treã haøng ñôïi töø To ñeán khi f(Tq) baèng QDLF , (3) QDLF. Vì vaäy f(Tq) naèm trong khoaûng [QDLF,b]. +Thoâng soá a vaø b: a vaø b laø caùc phaàn bò chaén cuûa hai haøm a-hyperbol vaø b-hyperbol, coù nghóa laø giaù trò cuûa f(Tq) khi q=0.Thoâng soá b quyeát ñònh dung löôïng vöôït möùc quy ñònh seõ ñöôïc phaân caáp khi ñoä treã haøng ñôïi baèng 0. Hai thoâng soá a vaø b cuõng quyeát ñònh ñoä doác cuûa haøm hyperbol hay noùi caùch khaùc toác ñoä f(Tq) giaûm laø moät haøm cuûa ñoä treã haøng ñôïi. a vaø b caøng lôùn laûm giaûi thuaät caøng nhaïy vôùi ñoä treã haøng ñôïi, ngöôïc laïi a vaø b caøng nhoûseõ taêng thôøi gian caàn thieát ñeå ñaït ñeán ñieåm vaän haønh mong muoán. Tieâu bieåu thì b nhoû hôn a, b quyeát ñònh löôïng baêng thoâng phaân caáp vöôït quaù möùc quy ñònh ñeå ñaït ñeán ñoä trì hoaûn ñích nhanh choùng ôû traïng thaùi xaùc laäp.Baát cöù moät söï vöôït möùc phaân caáp nhoû treân 100% dung löôïng ABR ñeàu thích hôïp. Thoâng soá a chuû yeáu quyeát ñònh toác ñoä haøm f(Tq) giaûm. A khoâng neân quaù khaùc so vôùi b bôûi vì ñieàu naøy coù theå daãn ñeán baêng thoâng ñöïôc phaân caáp coù söï khaùc nhau lôùn khi ñoä treã khaùc To moät löôïng nhoû. Maët khaùc a cuûng phaûi ñuû lôùn ñeå ñieàu khieån haøng ñôïi nhanh choùng. Ngöôøi ta thaáy raèng a = 1.15 vaø b = 1.05 hoaït ñoäng toát ñoái vôùi taát caû caùc taûi laøm vieäc ñöôïc thöû nghieäm. Vì vaäy khi haøng ñôïi baèng 0 chuùng ta coù theå phaân caáp vöôït quaù 5% dung löôïng saün coù ñeå ñöa haøng ñôïi ñeán Q0. Giaù trò b caøng cao cho pheùp nguoàn quaù taûi trong phaïm vi caøng roäng. Ñieàu naøy coù theå daãn ñeán quaù taûi quaù ñoä vaø chieàu daøi haøng ñôïi seõ taêng ñoät ngoät. b = 1 cuõng coù theå chaáp nhaän ñöôïc khi bieán ñoäng lôùn, nhöng trong tröôøng hôïp naøy tuùi haøng ñôïi taêng raát chaäm. Caùc thoâng soá a vaø b ñoäc laäp töông ñoái vôùi To vaø QDLF. Neáu cho tröôùc giaù trò a vaø b thì haøm chæ phuï thuoäc vaøo caùch choïn To vaø QDLF maø seõ ñöôïc moâ taû döôùi ñaây. + Ñoä treõ haøng ñôïi ñích To: Khi f(Tq) laø moät trong hai haøm hyperbol, heä soá goùc cuûa noù (df/dq) tæ leä nghòch vôùi To. Khi a laø haèng soá, To caøng lôùn caøng laøm giaûm ñoä doác cuûa ñoà thò vì vaäy cuõng giaûm ñoä hieäu quaû. Ñoä treã haøng ñôïi caàn thieát ñeå giaûm dung löôïng ABR bôûi moät thoâng soá coá ñònh thì tæ leä thuaän vôùi To. Noù cuõng tæ leä thuaän vôùi dung löôïng ABR. Vì vaäy khi dung löôïng ABR lôùn ( trong tröôøng hôïp maïng OC-3 vaø maïng toác ñoä cao), haøng ñôïi caàn phaûi taêng ñeán moät giaù trò lôùn tröôùc khi ruùt. Do ñoù coøn tuøy thuoäc vaøo giaù trò To lôùn nhaát vaø toác ñoä xoùa haøng ñôïi quaù ñoä. Giaù trò To lôùn nhaát phuï thuoäc vaøo kích thöôùc haøng ñôïi taïi chuyeån maïch vaø phaûi ñöôïc thieát laäp ñeå cho pheùp ñieàu khieån haøng ñôïi tröôùc khi boä ñeäm bò giôùi haïn. Chuùng ta coù theå söû duïng moät cô cheá laø duy trì kích thöôùc boä ñeäm ít nhaát baèng toång cuûa ñoä treã hoài tieáp vaø 8 x To (giaû söû a = 1.15, QDLF = 0.5, dung löôïng ABR coá ñònh vaø caùc thoâng soá khaùc khoâng ñaùng keå). Ñoä treã hoài tieáp laø thôøi gian ñuû ñeå haøm ñaït ñeán QDLF. Ñoái QDLF coù giaù trò khaùc, kích thöôùc boä ñeäm ñöôïc ñeà nghò laø: . Giaù trò To lôùn nhaát ñöôïc tính baèng caùch laáy nghòch ñaûo haøm treân: Giaù trò To nhoû nhaát cuõng ñöôïc yeâu caàu ñeå vaän haønh oån ñònh. Neáu To quaù nhoû, haøm f(Tq) coù theå vöôït quaù khoaûng [QDLF,b] trong thôøi gian , vôùi giaû söû dung löôïng coá ñònh trong khoaûng thôøi gian naøy. Khoaûng thôøi gian naøy coù theå ngaén hôn ñoä treã hoài tieáp neân daãn ñeán nhöõng dao ñoäng khoâng mong muoán veà toác ñoä vaø haøng ñôïi. Ñoù laø do f(Tq) thay ñoåi töø b ñeán QDLF tröôùc khi hoài tieáp coù taùc duïng. Caùch hoaït ñoäng nhö vaäy khoâng ñöôïc mong muoán bôûi vì giaûi thuaät raát nhaïy caûm vôùi söï thay ñoåi trong chieàu daøi haøng ñôïi. Chieàu daøi haøng ñôïi chæ laø thoâng soá thöù caáp. Hôn nöõa giaù trò To toái thieåu baèng tuùi haøng ñôïi mong muoán. Ñoái vôùi maïng WANs, To ít nhaát baèng cuûa ñoä treã hoài tieáp (baèng 1/8) vôùi giaû söû a = 1.15, QDLF = 0.5. Ñoái vôùi maïng LANs, chuùng ta thieát laäp To ít nhaát baèng thôøi gian moät voøng hoài tieáp ñeå giaûm tính nhaïy chieàu daøi haøng ñôïi nhoû cuûa dung löôïng ABR. Trong tröôøng hôïp coù bieán ñoäng lôùn hay gaëp loãi trong ño löôøng, tuùi haøng ñôïi coù theå khoâng ñaït ñöôïc. Yrong tröôøng hôïp naøy muïc tieâu laø ñoä thoâng suaát cao vaø To neân ñöôïc thieát laäp gaàn vôùi giaù trò toái thieåu ñeå cho pheùp ruùt haøng ñôïi nhanh choùng. + Heä soá giôùi haïn ruùt haøng ñôïi QDLF: QDLF ñaûm baûo coù ñuû dung löôïng ñeå ruùt haøng ñôïi quaù ñoä vaø ñöôïc ñeà nghò giaù trò laø 0.5 cho chuyeån maïch WAN vaø 0.8 cho chuyeån maïch LAN. Chuyeån maïch LAN caàn coù dung löôïng ruùt haøng ñôïi nhieàu hôn do ñoä treã hoài tieáp cuûa caùc VC daøi hôn vaø do ñoù thôøi gian ñaùp öùng quaù taûi quaù ñoä cuõng daøi hôn. Caùc chuyeån maïch LAN coù theå nhaän hoài tieáp nhanh choùng vaø To nhoû, haøm f(Tq) coù theå dòch chuyeån nhanh choùng trong khoaûng [QDLF,b]. Vôùi caùc ñieàu kieän naøy, dung löôïng ruùt haøng ñôïi lôùn laø khoâng caàn thieát do do haøng ñôïi khoâng bao giôø taêng cao. Ñoái vôùi caùc caáu hình nhö vaäy, QDLF coù theå coù giaù trò cao hôn(ví duï 0.8). Thoâng soá QDLF xaùc ñònh caän döôùi cuûa haøm f(Tq) vaø giaù trò naøy chæ ñaït ñöôïc khi haøng ñôïi lôùn. Do To lôùn laøm giaûm ñoä hieäu quaû cuûa haøm f(Tq) neân phaûi choïn a nhoû. Ñaây cuõng laø moät trong nhöõng nhaân toá aûnh höôûng ñeán söï löïa choïn giaù trò a. 3.2 Ñieàu khieån thoâng soá söû duïng (UPC_Usage Parameter Control) vaø giaûi thuaät Leaky Bucket: Trong thöïc teá vieäc ñieàu khieån löu löôïng thoâng tin trong moät maïng toång quaùt ñoøi hoûi phaûi ñöôïc thöïc hieän ôû nhieàu caáp ñoä khaùc nhau vaø phöùc taïp. Caùc nguoàn keát noái vaøo maïng ñeàu coù caùc giôùi haïn löu löôïng thoâng tin göûi vaøo maïng; tuy nhieân chuùng thöôøng göûi thoâng tin nhieàu hôn möùc ñoä cho pheùp hay noùi caùch khaùc caùc nguoàn thöôøng xuyeân vi phaïm veà löu löôïng thoâng tin. Do ñoù caùc nhaø quaûn trò maïng phaûi coù caùc giaûi phaùp cho vieäc ñieàu khieån luoàng löu löôïng maø caùc user stations göûi vaøo maïng vaø caùc giaûi phaùp naøy ñöôïc xem nhö laø neàn taûng cho caùc giaûi phaùp ôû möùc ñoä cao hôn (ñöôïc thöïc thi beân trong maïng vaø coù tính chaát phöùc taïp hôn nhieàu) ñeå ñieàu khieån löu löôïng thoâng tin trong maïng. Trong phaàn naøy ta seõ ñeà caäp ñeán vieäc ñieàu khieån löu löôïng thoâng tin trong maïng thoâng qua vieäc ñieàu khieån löu löôïng cuûa caùc nguoàn keát noái vaøo maïng ñeå caùc nguoàn naøy thoaû maõn vaø khoâng vi phaïm caùc thoâng soá ñaõ ñöôïc thoaû thuaän trong hôïp ñoàng löu löôïng. Phöông phaùp ñieàu khieån naøy goïi laø ñieàu khieån thoâng soá söû duïng(UPC) maø ñaõ ñöôïc ñeà caäp ôû chöông 2. Ñieàu khieån thoâng soá söû duïng ñöôïc xaây döïng trong cell layer vaø thöôøng ñöôïc aùp duïng trong caùc boä ñieàu khieån ñaët taïi UNI(user network interface). Moät giaûi thuaät quen thuoäc ñöôïc ñöa ra nhaèm thöïc thi ñieàu khieån thoâng soá söû duïng laø giaûi thuaät Leaky Bucket. Trong phaàn naøy ta seõ khaùi quaùt laïi veà UPC vaø sau ñoù ta seõ ñöa ra caùc daïng cuûa giaûi thuaät Leaky Bucket; treân cô sôû ñoù seõ choïn ra giaûi thuaät LB hieäu quaû cho UPC. 3.2.1 Ñieàu khieån thoâng soá söû duïng(UPC): UPC ñöôïc ñònh nghóa laø moät taäp caùc hoaït ñoäng cuûa maïng ñeå giaùm saùt vaø ñieàu khieån löu löôïng tuaân theo hôïp ñoàng löu löôïng taïi ñieåm truy nhaäp cuûa ngöôøi söû duïng UNI. Trong thöïc teá taøi nguyeân maïng laø höõu haïn vaø ñöôïc phaân chia cho caùc user stations theo caùc tæ leä ñaõ ñöôïc thoaû thuaän thoâng qua baûng hôïp ñoàng löu löôïng. Nhö vaäy neáu moät user naøo ñoù vi phaïm löu löôïng ñaõ thoaû thuaän maø khoâng ñöôïc xöû lyù seõ laøm giaûm chaát löôïng dòch vuï maø maïng cung caáp cho caùc user khaùc. Muïc ñích chính cuûa ñieàu khieån thoâng soá keát noái laø ñeå baûo veä taøi nguyeân maïng khoûi caùc vi phaïm trong moät soá caùc luoàng löu löôïng maø coù theå laøm chaát löôïng dòch vuï cuûa caùc keát noái khaùc. Ñieàu naøy ñöôïc thöïc hieän baèng caùch phaùt hieän caùc vi phaïm ñoái vôùi caùc thoâng soá ñaõ thoaû thuaän vaø thöïc hieän caùc hoaït ñoäng caàn thieát. Coâng vieäc giaùm saùt cho ñieàu khieån thoâng soá söû duïng UPC ñöôïc thöïc hieän baèng caùch: + Kieåm tra söï hôïp leä cuûa caùc giaù trò VPI vaø VCI. + Giaùm saùt löu löôïng vaøo maïng töø moãi VCC vaø VPC ñeå ñaûm baûo caùc thoâng soá ñaõ thoaû thuaän khoâng bò vi phaïm. Hoaït ñoäng giaùm saùt naøy ñöôïc thöïc hieän taïi ñieåm keát thuùc cuûa lieân keát VC (VC link) ñaàu tieân ñoái vôùi caùc VCC vaø taïi VP link ñaàu tieân ñoái vôùi caùc VPC. Caùc giaûi thuaät ñieàu khieån thoâng soá söû duïng UPC: Moät giaûi thuaät xaùc ñònh cho caùc hoaït ñoäng cuûa UPC vaãn chöa ñöôïc chuaån hoùa. Tuy nhieân moät soá ñaëc ñieåm caàn phaûi coù cuûa giaûi thuaät ñieàu khieån coù theå ñöôïc xaùc ñònh nhö sau: + Khaû naêng phaùt hieän caùc vi phaïm baát kyø. + Söï choïn löïa treân giôùi haïn cuûa caùc thoâng soá ñöôïc kieåm tra(nghóa laø giaûi thuaät phaûi xaùc ñònh ñöôïc ngöôøi söû duïng coù hoaït ñoäng trong moät vuøng coù theå chaáp nhaän ñöôïc hay khoâng. + thôøi gian ñaùp öùng nhanh ñoái vôùi caùc vi phaïm veà thoâng soá. Ngoaøi ba yeâu caàu quan troïng ôû treân, caùc giaûi thuaät ñöa ra coøn phaûi thoûa maõn yeáu toá ñôn giaûn, kinh teá vaø coù tính khaû thi. Coù nhieàu giaûi thuaät ñöôïc ñöa ra ñeå ñieàu khieån toác ñoä ñænh, toác ñoä trung bình; tuy nhieân vì tính hieäu quaû, söï ñôn giaûn vaø khaû naêng ñaùp öùng nhanh cuûa noù maø giaûi thuaät Leaky Bucket(LB) ñöôïc söû duïng roäng raõi nhaát trong UPC. 3.2.2 Caùc giaûi thuaät Leaky Bucket: Trong phaàn naøy ta seõ ñöa ra caùc giaûi thuaät LB ñöôïc khuyeán nghò vaø sau ñoù ta seõ ñöa ra keát luaän cho moät giaûi thuaät hieäu quaû nhaát. Vieäc phaân chia caùc giaûi thuaät khaùc nhau laø coù tính chaát töông ñoái vì caùc giaûi thuaät khaùc nhau thöïc teá cuõng chæ khaùc nhau ôû vaøi ñieåm nhoû chuû yeáu laø soá löôïng buffer maø chuùng söû duïng. Vì söï khaùc nhau ôû soá löôïng buffer maø chuùng coù caùc tính chaát khaùc nhau vaø coù phaïm vi öùnh duïng khaùc nhau. 3.2.2.1 Leaky Bucket khoâng coù buffer: Hình 3.1 minh hoïa cho caáu taïo cuûa moät boä ñieàu khieån giaûi thuaät LB khoâng coù boä ñeäm. Trong hình veõ ta thaáy caùc cells vaø caùc token ñöôïc ñöa tröïc tieáp ñeán boä kieåm tra. Taïi boä kieåm tra naøy töøng cell chæ ñöôïc ñöa vaøo maïng khi chuùng ñeán cuøng vôùi moät token. Ñieàu naøy coù nghóa laø token ñoùng vai troø nhö moät giaáy thoâng haønh cho cell vaøo maïng. Ta goïi r laø toác ñoä taïo token vaø xeùt moät luoàng cell coù caùc thoâng soá sau: m: toác ñoä trung bình cuûa caùc cell. p: toác ñoä ñænh cuûa luoàng cell. Y: laø heä soá gia taêng cuûa toác ñoä trung bình Trong heä LB khoâng coù buffer thì toác ñoä cell vaøo maïng hoaøn toaøn phuï thuoäc vaøo toác ñoä taïo token r. Khi caùc nguoàn cell coù toác ñoä nhoû hôn r thì taát caû caùc cell ñeàu ñöôïc vaøo maïng. Khi caùc nguoàn cell phaùt cell ôû toác ñoä lôùn hôn r thì chæ coù moät phaàn caùc cell ñöôïc göûi vaøo maïng vôùi toác ñoä r coøn caùc cell laøm toác ñoä r seõ bò boû qua. Nhö vaäy toác ñoä cell göûi vaøo maïng seõ coù caän treân laø r vaø caän döôùi laø toác ñoä toái thieåu ñöôïc thoûa thuaän vôùi maïng. Tính chaát cuûa heä ñieàu khieån LB khoâng coù boä ñeäm (buffer) coù theå ruùt ra nhö sau: tæ leä maát cell lôùn khi toác ñoä nguoàn phaùt döôùi daïng nguoàn on-off trong ñoù toác ñoä cell trong thôøi gian ton coù giaù trò lôùn hôn r ; ñaây cuõng chính laø khuyeát ñieåm lôùn nhaát cuûa daïng LB naøy. Do khuyeát ñieåm naøy neân daïng LB khoâng coù buffer chæ ñöôïc söû duïng moät caùch haïn cheá nhö trong vieäc ñieàu khieån toác ñoä ñænh. Öu ñieåm cuûa boä LB khoâng coù buffer laø khoâng taïo thôøi gian treã (delay) cho luoàng cell vaøo maïng. Toác ñoä töùc thôøi vaø trung bình cuûa cell vaøo maïng seõ coù giaù trò nhoû hôn hay baèng giaù trò r. 3.2.2.2 Leaky Bucket coù data buffer: Boä ñieàu khieån LB coù data buffer ñöôïc trình baøy nhö trong hình 3.2. Boä ñieàu khieån LB naøy chæ khaùc boä ñieàu khieån LB khoâng coù buffer ôû choå noù coù moät vuøng ñeäm data cho caùc cell khi chuùng ñöôïc göûi ñeán laøm vöôït quaù toác ñoä taïo token r (caùc cell vi phaïm veà toác ñoä). Nhö vaäy ta coù theå toùm taét hoaït ñoäng cuûa boä ñieàu khieån coù data buffer nhö sau: khi luoàng cell ñöôïc göûi vaøo boä LB vôùi toác ñoä nhoû hôn r thì chuùng seõ khoâng ñöôïc löu vaøo boä ñeäm maø seõ ñöôïc göûi tröïc tieáp ñeán boä kieåm tra. Taïi boä kieåm tra caùc cell naøy seõ ñöông nhieân ñöôïc göûi vaøo maïng vì chuùng coù toác ñoä nhoû hôn r. Khi nguoàn phaùt ra luoàng cell coù toác ñoä lôùn hôn r thì chæ coù moät phaàn caùc cell ñöôïc vaøo maïng vôùi toác ñoä r, phaàn caùc cell coøn laïi seõ ñöôïc chöùa trong boä data buffer neáu nhö boä naøy coøn troáng. Neáu taïi thôøi ñieåm sau ñoù nguoàn laïi phaùt luoàng cell ôû toác ñoä nhoû hôn r thì caùc cell bò thöøa ñöôïc löu trong data buffer (ôû thôøi ñieåm vi phaïm tröôùc). Seõ ñöôïc tieáp tuïc göûi vaøo maïng. Nhö vaäy baèng caùch ñaët moät boä data buffer ta ñaõ coù theå thöïc hieän ñöôïc vieäc san baèng toác ñoä luoàng cell vaøo maïng ñeå toác ñoä trung bình cuûa luoàng cell vaøo maïng nhoû hôn hay baèng toác ñoä taïo token r. Toùm laïi boä data buffer coù tính chaát laøm trung bình hoùa toác ñoä cell, löu caùc cell thöøa ôû thôøi ñieåm vi phaïm toác ñoä ñeå phaùt chuùng ôû thôøi ñieåm maø luoàng cell coù toác ñoä nhoû hôn r. Dung löôïng boä ñeäm data buffer vaø toác ñoä taïo token quyeát ñònh chieàu daøi toái ña tính theo cell cuûa luoàng cell taïi moät toác ñoä rcell ñeå khoâng coù cell naøo bò maát khi phaùt coá ñònh taïi toác ñoä rcell ñoù. Neáu ta goïi B laø dung löôïng boä ñeäm (B tính theo cell ) thì ta coù: (*) Trong coâng thöùc treân CBSmax chính laø soá cell toái ña maø nguoàn phaùt coù theå phaùt lieân tuïc ôû toác ñoä rcell ñeå khoâng coù cell naøo bò maát. Nhö vaäy ta nhaän thaáy boä LB coù data buffer coù öu ñieåm laø san baèng toác ñoä luoàng cell phaùt vaøo maïng thoâng qua vieäc söû duïng data buffer. Taïi moät toác ñoä rcell > r thì soá cell toái ña maø nguoàn coù theå phaùt lieân tuïc ñöôïc tính theo coâng thöùc (*). Tuy data buffer laøm giaûm möùc ñoä maát cell moät caùch ñaùng keå thì chính data buffer laïi gaây neân cöï delay khoâng mong muoán cuûa luoàng cell; do ñoù boä ñieàu khieån LB coù data buffer chæ ñöôïc öùng duïngcho caùc dòch vuï khoâng coù yeâu caàu nghieâm ngaët veà möùc ñoä delay. 3.2.2.3 Leaky Bucket coù data buffer vaø token pool: Hình 3.3 theå hieän caáu truùc cuûa moät boä LB coù hai boä ñeäm laø data buffer vaø token pool. Boä LB naøy vaãn coù khuyeát ñieåm laø taïo neân thôøi gian delay cho luoàng cell vaøo maïng. Tuy nhieân neáu ta öùng duïng boä LB coù hai buffer vaøo caùc dòch vuï khoâng coù ñoøi hoûi gaét gao veà delay thì noù seõ coù öu ñieåm lôùn nhaát . Boä data buffer nhö ñaõ ñeà caäp ôû treân coù chöùc naêng san baèng toác ñoä luoàng cell vaøo maïng coøn buffer cho token coù chöùc naêng ñeå giaønh token khi chuùng chöa ñöôïc söû duïng heát luùc toác ñoä cell nhoû hôn toác ñoä taïo token. Thöïc vaäy khi moät luoàng cell coù toác ñoä cell laø rcell < r ñöa vaøo boä LB thì chæ coù moät soá token ñöôïc gaùn cho caùc cell vôùi toác ñoä rcell , soá token coøn laïi seõ ñöôïc chöùa trong boä token pool. Neáu nhö ôû thôøi ñieåm sau toác ñoä cell vöôït quaù toác ñoä taïo token thì caùc token tröôùc ñoù ñöôïc chöùa trong token pool seõ ñöôïc gaùn cho caùc cell laøm vöôït quaù toác ñoä. Nhö vaäy token pool coù chöùc naêng taän duïng toái ña caùc token ñöôïc phaùt cho caùc cell. Ta caàn chuù yù raèng vieäc theâm moät boä ñeäm token pool vaøo boä ñieàu khieån ñaõ laøm thay ñoåi tính chaát ñieàu khieån cuûa boä LB. ÔÛ hai loaïi LB treân thì toác ñoä cell vaøo maïng coù caän treân laø toác ñoä token r. Khi caùc cell coù toác ñoä lôùn hôn r thì chuùng seõ bò maát hay ñöôïc löu vaøo boä data buffer vaø chôø khi cho ñeán khi rcell < r thì seõ tieáp tuïc vaøo maïng. Vôùi tröôøng hôïp coù data buffer vaø token pool thì toác ñoä vaøo maïng cuûa caùc cell coù theå lôùn hôn toác ñoä taïo token vaø taïi moät thôøi ñieåm nhaát ñònh thì toác ñoä cell vaøo maïng coù theå ñaït toác ñoä ñænh. Söï kieän naøy xaûy ra khi tröôùc thôøi ñieåm ñoù nguoàn phaùt caùc cell coù toác ñoä cell rcell nhoû hôn r neân seõ coù caùc token löu vaøo löu vaøo trong token pool vaø nguoàn taêng toác ñoä ñeán toác ñoä ñænh . Tuy nhieân neáu quan saùt treân thôøi gian daøi thì ta coù theå thaáy raèng boä ñieàu khieån LB coù data buffer vaø token pool seõ coù chöùc naêng ñieàu khieån toác ñoä trung bình cuûa luoàng cell vaøo maïng, laøm cho toác ñoä trung bình naøy hoäi tuï veà toác ñoä token r. Ñaây laø tính chaát quan troïng cuûa LB coù hai buffer. 3.2.2.4 ÖÙng duïng caùc daïng Leaky Bucket: Töø caùc phaàn treân ta thaáy raèng: hai loaïi LB khoâng coù boä ñeäm vaø coù data buffer coù chöùc naêng ñieàu khieån toác ñoä cell phaùt vaøo maïng sao cho toác ñoä cell toái ña khoâng vöôït quaù toác ñoä token. Loaïi LB coù data buffer chæ ñôn thuaàn laø khaéc phuïc nhöôïc ñieåm maát cell khi toác ñoä cell lôùn hôn r cho loaïi LB khoâng coù buffer baèng caùch san baèng toác ñoä cell ñöa vaøo thoâng qua vieäc löu cell vaøo data buffer khi chuùng vöôït quaù toác ñoä token r. Vôùi giaûi thuaät coù hai buffer laø data buffer vaø token pool thì quaù trình ñieàu khieån mang moät yù nghóa khaùc ñoù laø toác ñoä trung bình vaøo maïng nhoû hôn hay baèng toác ñoä token r. Ta caàn chuù yù raèng taïi moät thôøi ñieåm nhaát ñònh thì toác ñoä cell vaøo maïng coù theå vöôït quaù toác ñoä token r vaø coù theå baèng toác ñoä toái ña p cuûa nguoàn. Döïa vaøo tính chaát treân cuûa caùc boä ñieàu khieån ta coù theå chia ñieàu khieån thoâng soá söû duïng thaønh hai daïng ñieàu khieån chính laø: ñieàu khieån toác ñoä ñænh vaø ñieàu khieån toác ñoä trung bình. Ñieàu khieån toác ñoä ñænh laø quaù trình laøm cho toác ñoä toái ña cuûa luoàng cell khoâng vöôït quaù toác ñoä giôùi haïn cho pheùp. Nhö vaäy ta chæ coù theå thöïc hieän vieäc ñieàu khieån toác ñoä ñænh thoâng qua boä LB khoâng coù buffer hay chæ coù data buffer. Vieäc löïa choïn coù hay khoâng coù data buffer laø tuøy thuoäc vaøo yeâu caàu delay vaø söï maát cell ñoái vôùi dòch vuï maø maïng cung caáp. Neáu dòch vuï laø thôøi gian thöïc (real time service) thì LB khoâng coù data buffer ñöôïc söû duïng. Neáu dòch vuï cung caáp yeâu caàu khaét khe veà tæ leä maát cell thì ta coù theå söû duïng loaïi LB coù data buffer. Chuù yù trong ñieàu khieån toác ñoä ñænh ta khoâng theå söû duïng LB coù hai boä ñeäm vì nhö phaân tích thì boä LB loaïi naøy coù theå cho pheùp caùc cell phaùt ra vöôït quùa toác ñoä ñænh quy ñònh. Ñieàu khieån toác ñoä trung bình laø quaù trình taùc ñoäng vaøo luoàng cell laøm cho toác ñoä tung bình cuûa luoàng cell khoâng vöôït quaù giôùi haïn cho pheùp. Caàn löu yù ôû ñaây söï mong muoán laø toác ñoä trung bình chöù khoâng phaûi laø toác ñoä ñænh. Do ñoù trong ñieàu khieån toác ñoä trung bình taïi moät thôøi ñieåm toác ñoä luoàng cell coù theå vöôït quaù toác ñoä token r tuy nhieân giaù trò toác ñoä trung bình cuûa luoàng cell naøy khoâng ñöôïc vöôït quaù giaù trò quy ñònh. Ñeå thöïc hieän vieäc ñieàu khieån toác ñoä trung bình ta phaûi söû dung boä LB coù hai boä ñeäm. Nhö vaäy ñeå toùm taét cho caùc öùng duïng ñieàu khieån ta coù theå quan saùt baûng sau: Ta nhaän thaáy trong hai daïng ñieàu khieån thoâng soá keát noái toác ñoä trung bình vaø toác ñoä ñænh treân thì ñieàu khieån toác ñoä ñænh töông ñoái ñôn giaûn. Trong caùc phaàn khaûo saùt veà sau ta chæ quan taâm ñeán vieäc ñieàu khieån toác ñoä trung bình thoâng qua boä LB coù hai buffer. 3.2.2.5 ÖÙng duïng moâ hình chaát loûng vaøo tính toaùn caùc thoâng soá trong giaûi thuaät LB: Trong phaàn naøy ta seõ döïa vaøo moâ hình chaát loûng (fluid-flow) ñeå tính toaùn caùc thoâng soá cho moâ hình LB coù data buffer vaø token pool. Trong moâ hình chaát loûng nguoàn coù tính chaát lieân tuïc coù nghóa laø caùc nguoàn seõ phaùt ra caùc cell moät caùch lieân tuïc vaø toác ñoä trung bình laø m. Tuy nhieân trong thöïc teá caùc nguoàn cell thöôøng ôû daïng on-off töùc laø chuùng seõ khoâng thöïc hieän vieäc phaùt caùc cell moät caùch lieân tuïc maø chuùng thöïc hieän phaùt cell trong caùc khoaûng thôøi gian ton vaø ngöng phaùt cell trong caùc khoaûng toff. Moâ hình chaát loûng seõ ñöôïc bieán ñoåi ñeå phuø hôïp vôùi ñaëc tính on-off cuûa caùc nguoàn trong thöïc teá. Caùc thoâng soá cuûa nguoàn thöïc teá maø ta quan taâm laø: p: toác ñoä ñænh laø toác ñoä toái ña maø nguoàn ñöôïc pheùp khi phaùt cell. m: toác ñoä trung bình cuûa nguoàn. ton: thôøi gian maø nguoàn lieân tuïc phaùt caùc cell. toff: thôøi gian maø nguoàn khoâng thöïc hieän phaùt moät cell naøo. Y: laø heä soá bieåu thò möùc ñoä gia taêng toác ñoä trung bình cuûa nguoàn. Boä LB coù caùc thoâng soá sau: BD: dung löôïng data buffer. M: dung löôïng cuûa boä token buffer. B = BD + M laø toång dung löôïng hai buffer. r: toác ñoä taïo token. Vôùi caùc thoâng soá treân cuûa nguoàn vaø cuûa boä LB ta coù bieåu thöùc tính dung löôïng (throughput) nhö sau: , trong bieåu thöùc naøy mo laø tæ soá toác ñoä trung bình cuûa nguoàn vôùi toác ñoä taïo token coøn DB laø moät haøm ñöôïc xaùc ñònh theo toác ñoä ñænh, thôøi gian ton, thôøi gian toff vaø toång dung löôïng boä nhôù B: Trong bieåu thöùc naøy z ñöôïc xaùc ñònh theo coâng thöùc sau: Döïa vaøo caùc thoâng soá treân ta coù theå xaùc ñònh ñöôïc caùc thoâng soá quan troïng cho boä ñieàu khieån LB nhö : + Xaùc suaát maát cell(CLP): + Chieàu daøi trung bình boä ñeäm döõ lieäu: + Chieàu daøi trung bình boä ñeäm token: + Thôøi gian taùc ñoäng trôû laïi trung bình: Trong coâng thöùc treân nc laø soá bit trong moät cell (424bit), E laø tæ soá giöõa toác ñoä taïo token vaø toác ñoä trung bình cuûa nguoàn, Y laø heä soá gia taêng toác ñoä trung bình cuûa nguoàn. 3.2.3 Xaây döïng löu ñoà cho quaù trình hoaït ñoäng cuûa LB 3.2.3.1 Söï kieän cell ñeán(cell arrival event): Söï kieän cell ñeán xaûy ra khi coù moät cell ñeán ngoõ vaøo cuûa heä thoáng leaky bucket cho ñeán khi data buffer xöû lyù xong söï ñeán cuûa cell naøy. Nhö vaäy ta coù theå moâ taû toaøn boä quaù trình xaûy ra töø luùc cell ñeán nhö sau: data buffer lieân tuïc thöïc hieän quaù trình kieåm tra xem coù cell ñeán hay khoâng, neáu coù cell ñeán thì LB baét ñaàu quaù trình cell ñeán. Neáu boä nhôù bò ñaày thì cell ñeán naøy bò boû qua (töùc laø cell bò maát) vaø giaù trò bufferlength giöõ nguyeân giaù trò buffersize, neáu boä nhôù coøn nhieàu hôn hay baèng moät oâ nhôù troáng thì cell naøy seõ ñöôïc löu vaøo moät oâ nhôù troáng vaø giaù trò bufferlength seõ taêng leân moät ñôn vò. Caàn chuù yù raèng trong luùc phaân tích ta luoân chuaån hoùa caùc giaù trò dung löôïng boä nhôù tính theo cell. Khi keát thuùc quaù trình naøy cuõng laø keát thuùc quaù trình cell ñeán. Ta coù theå moâ taû toaøn boä quaù trình naøy theo löu ñoà söï kieän cell ñeán nhö sau: 3.2.3.2 Löu ñoà giaûi thuaät cho söï kieän phaùt token(token generating event): Sau khi thöïc hieän söï kieän cell ñeán, heä thoáng tieán haønh söï kieän phaùt token. Trong quaù trình khaûo saùt ta seõ duøng töø tokentime ñeå aùm chæ thôøi gian maø heä thoáng mong ñôïi ñeå taïo ra moät token môùi. Nhö vaäy neáu thôøi gian mong ñôïi lôùn hôn böôùc thôøi gian hieän taïi thì seõ khoâng coù token ñöôïc taïo ra coøn neáu tokemtime nhoû hôn böôùc thôøi gian hieän taïi thì seõ coù moät token môùi ñöôïc taïo ra. Ta coù theå toùm taét cô cheá hoaït ñoäng cuûa LB cho söï kieän phaùt token nhö sau: sau khi keát thuùc söï kieän cell ñeán, heä thoáng LB chuyeån sang söï kieän phaùt token. Neáu tokentime coù giaù trò lôùn hôn thôøi gian hieän taïi thì seõ khoâng coù moät token naøo ñöôïc taïo ra vaø heä thoáng seõ keát thuùc söï kieän taïo token. Ngöôïc laïi neáu thôøi gian tokentime nhoû hôn böôùc thôøi gian hieän taïi thì seõ coù moät token ñöôïc taïo ra, neáu token pool khoâng coøn troáng thì topken vöøa taïo ra seõ bò maát vaø heä thoáng keát thuùc söï kieän taïo token; neáu tokenpool coøn troáng thì heä thoáng seõ löu token vöøa taïo vaøo tokenpool vaø taêng tokenlength leân moät ñôn vò. Sau khi coù moät token ñöôïc taïo ra thì heä thoáng seõ caäp nhaät tokentime thoâng qua vieäc coäng tokentime vôùi giaù trò D nhaän ñöôïc. Nhö vaäy toaøn boä söï kieän phaùt token coù theå ñöôïc minh hoïa nhö trong löu ñoà giaûi thuaät cho söï kieän taïo token nhö hình 3.5. 3.2.3.3 Söï kieän cell ñi (cell departure): Sau khi traûi qua söï kieän cell ñeán vaø söï kieän taïo token thì heä thoáng LB chuyeån sang söï kieän cell ñi. Trong söï kieän cell ñi heä thoáng seõ kieåm tra data buffer vaø token pool. Neáu caû hai boä ñeäm naøy coù cell vaø token thì heä thoáng seõ phaùt moät cell vaøo maïng. Neáu moät trong hai boä ñeäm khoâng coù döõ lieäu(cell hay token) thì seõ khoâng coù moät cell naøo ñöôïc ñöa vaøo maïng. Neáu coù moät cell ñöôïc dua vaøo maïng thì hai boä buffer seõ giaûm chieàu daøi ñi moät ñôn vò. Löu ñoà giaûi thuaät ñöôïc trình baøy nhö trong hình 3.6 trang beân. Nhö vaäy döïa vaøo ba löu ñoà cho ba söï kieän cell ñeán, phaùt token vaø cell ñi ta coù theå xaây döïng moät heä thoáng Leaky Bucket hoaøn chænh thoâng qua vieäc laäp voøng ba söï kieän treân moät caùch lieân tuïc.