Експоненцијално одустајање () је алгоритам који користи повратну спрегу за мултипликативно смањење учесталости неког процеса, како би се постепено пронашла прихватљива учесталост. Ови алгоритми налазе примену у широком спектру система и процеса, при чему су посебно значајне радио и рачунарске мреже.
Алгоритам експоненцијалног одустајања Алгоритам експоненцијалног одустајања је облик система са затвореном петљом који смањује учесталост контролисаног процеса као одговор на неповољне догађаје. На пример, ако се апликација на смартфону не успе повезати са својим сервером, може покушати поново након 1 секунде, затим, ако поново не успе, након 2 секунде, затим 4, итд. Сваки пут се пауза множи фиксним износом (у овом случају 2). У овом случају, неповољан догађај је неуспешно повезивање са сервером. Други примери неповољних догађаја укључују сударе мрежног саобраћаја, одговор грешке са сервиса или експлицитни захтев за смањење учесталости (тј. „odustati” — ).
Смањење учесталости може се моделирати као експоненцијална функција:
или
Овде, представља временско кашњење примењено између радњи, је мултипликативни фактор или osnova, је број уочених неповољних догађаја, а је учесталост (или проток) процеса (тј. број радњи по јединици времена). Вредност се повећава сваки пут када се уочи неповољан догађај, што води до експоненцијалног пораста кашњења и, самим тим, обрнуто пропорционалне учесталости. Експоненцијални алгоритам одустајања где је назива се бинарним експоненцијалним алгоритмом одустајања.
Када се учесталост смањи као одговор на неповољан догађај, обично не остаје на том смањеном нивоу заувек. Ако се током одређеног периода не примете неповољни догађаји, често називаног „време опоравка” или „period за хлађење”, учесталост се поново може повећати. Временски период који мора проћи пре новог покушаја повећања учесталости такође може бити одређен алгоритмом експоненцијалног одустајања. Типично, опоравак учесталости се одвија спорије од њеног смањења због одустајања и често захтева пажљиво подешавање како би се избегло осциловање учесталости. Тачно понашање при опоравку је специфично за имплементацију и може бити условљено бројним факторима из окружења.
Механизам путем кога се смањење учесталости практично постиже у систему може бити сложенији од једноставног временског кашњења. У неким случајевима, вредност може се односити на горњу границу временског кашњења, а не на специфичну вредност временског кашњења. Назив „експоненцијално одустајање” односи се на карактеристику експоненцијалног раста одустајања, а не на тачан нумерички однос између броја неповољних догађаја и времена кашњења.
Ограничавање протока Експоненцијално одустајање се често користи као део механизама за ограничавање протока у рачунарским системима као што су веб сервиси, како би се помогло у спровођењу праведне дистрибуције приступа ресурсима и спречио прекомерно оптерећење мреже. Сваки пут када сервис обавести клијента да шаље захтеве сувише често, клијент смањује своју учесталост за неки предодређени фактор све док учесталост захтева клијента не достигне прихватљиву равнотежу. Сервис може спроводити ограничавање протока тако што ће одбити да одговори на захтеве када их клијент шаље сувише често, како се „лоши” клијенти не би препустили својим додељеним ресурсима.
Предност коришћења алгоритма експоненцијалног одустајања у односу на фиксирано ограничење протока је та што се ограничења протока могу постићи динамички без提供给ња икаквих претходних информација клијенту. У случају да се ресурси неочекивано суже, нпр. због великог оптерећења или прекида рада сервиса, захтеви за одустајање и одговори грешке са сервиса могу аутоматски смањити учесталост захтева од клијената. Ово може помоћи у одржавању одређеног нивоа доступности уместо претераног оптерећивања сервиса. Поред тога, квалитет услуге може имати приоритет за одређене клијенте на основу њихове појединачне важности, нпр. смањењем одустајања за хитне позиве на телефонској мрежи током периода високог оптерећења.
У једноставној верзији алгоритма, поруке се одлажу за предодређено (нерандомно) време. На пример, у SIP протоколу преко непоузданог транспорта (као што је UDP), клијент поново шаље захтеве у интервалима који почињу од Т1 секунди (обично , што је процена времена повратног пута) и удвостручавају се након сваког поновног слања све док не достигну Т2 секунде (које се подразумевају као ). Ово резултује интервалима поновног слања од , , , , , , итд.
Избегавање судара Алгоритми експоненцијалног одустајања се могу користити за избегавање судара у мрежи. У тачка-ка-више тачака или мултиплексираној мрежи, више пошиљалаца комуницира преко јединственог дељеног канала. Ако се два пошиљаоца покушају одаслати поруку у исто време, или „препричају” један другог, долази до судара и поруке се оштећују или губе. Сваки пошиљалац се затим може повући пре него što покуша да пошаље поново исту поруку.
Детерминистички алгоритам експоненцијалног одустајања није погодан за ову употребу, јер би се сваки пошиљалац повукао за исти период, што би их довело до поновног слања у исто време и изазвало нови судар. Уместо тога, у сврху избегавања судара, време између поновних слања се рандомизује, а алгоритам експоненцијалног одустајања поставља опсег вредности кашњења које су могуће. Временско кашњење се обично мери у слотовима, који су периоди фиксиране дужине (или „исечци”) времена на мрежи. У бинарном експоненцијалном алгоритму одустајања (тј. оном где је ), након судара, свако поновно слање се одлаже за случајан број времена слота између и . Након првог судара, сваки пошиљалац ће чекати 0 или 1 време слота. Након другог судара, пошиљаоци ће чекати било где од 0 до 3 времена слота (укључујући). Након трећег судара, пошиљаоци ће чекати било где од 0 до 7 времена слота (укључујући), и тако даље. Како се број покушаја поновног слања повећава, број могућности за кашњење експоненцијално расте. Ово смањује вероватноћу судара, али повећава просечно кашњење.
Експоненцијално одустајање се користи током поновног слања оквира у мрежама са носилачко осетљивим приступом са избегавањем судара (CSMA/CA) и носилачко осетљивим приступом са откривањем судара (CSMA/CD), где је овај алгоритам део методе приступа каналу који се користи за слање података на овим мрежама. У Етернет мрежама, алгоритам се често користи за заказивање поновног слања након судара. Поново слање се одлаже за износ времена изведен из времена слота (на пример, време потребно за слање 512 битова; тј., 512 бит-времена) и броја покушаја поновног слања.
Пример Овај пример је из Етернет протокола, где домаћин који шаље може да зна када је дошло до судара (тј. да је други домаћин покушао да преноси), када шаље оквир. Ако оба домаћина покушају да поново пошаљу чим дође до судара, поново би дошло до судара — и тај образац би се наставио унеколико. Домаћини морају изабрати случајну вредност унутар прихватљивог опсега kako би осигурали да се ова ситуација не догоди. Зато се користи алгоритам експоненцијалног одустајања. Вредност 51,2 μs се овде користи као пример јер је то време слота за Етернет линију. Међутим, може бити замењено било којом позитивном вредношћу у пракси.
Када се први пут деси судар, пошаљи прекидни сигнал да би се спречило даље слање података. Поново пошаљи оквир након 0 секунди или , изабрано насумице. Ако то не успе, поново пошаљи оквир након , , или . Ако то и даље не успе, поново пошаљи оквир након · , где је случајни цео број између 0 и . За даље неуспехе, након c-тог неуспелог покушаја, поново пошаљи оквир након · , где је случајни цео број између 0 и .
Историја и теорија У семиналном раду објављеном у AFIPS 1970., Норман Абрамсон је представио идеју о више корисника, на различитим острвима, који деле један радио канал (тј. једну фреквенцију) за приступ главном рачунару на Универзитету на Хавајима без било какве временске синхронизације. Судари пакета на пријемнику главног рачунара се третирају од стране пошиљаоца након истека времена као откривене грешке. Сваки пошиљалац који не прими позитивну потврду од главног рачунара поново би слао свој изгубљени пакет. Абрамсон је претпоставио да је низ пакета послат у дељени канал Поасонов процес са протоком , који је збир протока нових долазака пакета пошиљаоцима и протока поново послатих пакета у канал. Претпостављајући стационарно стање, показао је да је проток канала са максималном вредношћу од 1/(2) = 0,184 у теорији.
Лари Робертс је разматрао ALOHA канал подељен на временске слотове, при чему је сваки временски слот довољно дугачак за време преноса пакета. (Сателитски канал који користи TDMA протокол је подељен на временске слотове.) Користећи исте Поасонове процесе и претпоставке стационарног стања као Абрамсон, Лари Робертс је показао да је максимални проток 1/ = 0,368 у теорији. Робертс је био менаџер програма истраживачког пројекта ARPANET. Инспирисан идејом ALOHA са слотовима, Робертс је покренуо нови пројекат ARPANET Satellite System (ASS) да би укључио сателитске везе у ARPANET.
Резултати симулације Абрамсона, његових колега и других показали су да ALOHA канал, са слотовима или не, није стабилан и да би се понекад дешавао колапс због препуњења. Колико времена до колапса због препуњења зависило је од протока нових пакета као и од других непознатих фактора. Године 1971., Лари Робертс је замолио професора Леонарда Клајнрока и његовог докторанда, Сајмона Лама, са UCLA-е да се придруже пројекту Сателитски систем ARPANET-а. Сајмон Лам би радио на стабилности, оцени перформанси и адаптивној контроли ALOHA са слотовима за свој истраживачки рад докторске дисертације. Први рад који је написао заједно са Клајнроком био је ARPANET Satellite System (ASS) Note 12, дистрибуиран групи ASS у августу 1972. У овом раду, слот случајно изабран у интервалу од слотова је коришћен за поновно слање. Нови резултат из модела је да повећање повећава проток канала, који конвергира ка 1/ када се повећава на бесконачност. Овај модел је задржао претпоставке о Поасоновим доласцима и стационарном стању и није био намењен за разумевање статистичког понашања и колапса због препућења.
Стабилност и адаптивно одустајање Да би разумео стабилност, Лам је креирао дискретни временски Марковљев ланац за анализу статистичког понашања ALOHA са слотовима у поглављу 5 своје дисертације. Модел има три параметра: , и . је укупан број корисника. У било ком тренутку, сваки корисник може бити неактиван или блокиран. Сваки корисник има највише један пакет за слање у следећем временском слоту. Неактиван корисник генерише нови пакет са вероватноћом и шаље га у следећем временском слоту одмах. Блокирани корисник шаље свој пакет у резерви са вероватноћом , где 1/ = (+1)/2 kako би се просечни интервал поновног слања задржао исти. Резултати протока-кашњења два метода поновног слања су упоређени екстензивним симулацијама и утврђено је да су у суштини исти.
Ламов модел даје математички rigorозне одговоре на питања стабилности ALOHA са слотовима, као и ефикасан алгоритам за израчунавање перформанси протока-кашњења за било који стабилан систем. Постоје 3 кључна резултата, приказана испод, из Ламовог Марковљевог ланца модела у поглављу 5 његове дисертације (такође заједно објављено са професором Леном Клајнроком у часопису IEEE Transactions on Communications.) ALOHA са слотовима са Поасоновим доласцима (тј. бесконачно ) је инхерентно нестабилан, јер не постоји стационарна расподела вероватноће. (Достизање стационарног стања је била кључна претпоставка коришћена у моделима Абрамсона и Робертса.) За ALOHA са слотовима коначног и коначног , Марковљев ланац модел се може користити за одређивање да ли је систем стабилан или нестабилан за дати улазни проток (×) и, ако је стабилан, за израчунавање његовог просечног кашњења пакета и протока канала. Повећање повећава максимални број корисника који могу бити смештени у стабилан ALOHA канал са слотовима.
Последица За коначни (), нестабилан канал за тренутну вредност може се учинити стабилним повећањем на довољно велику вредност, која ће се називати (,).