Exponential backoff (original) (raw)
Exponential backoff is an algorithm that uses feedback to multiplicatively decrease the rate of some process, in order to gradually find an acceptable rate. These algorithms find usage in a wide range of systems and processes, with radio networks and computer networks being particularly notable.
| Property | Value |
|---|---|
| dbo:abstract | Der Binary Exponential Backoff ist ein Stauauflösungsmechanismus im Ethernet nach IEEE 802.3. Wird von Stationen im Ethernet eine Kollision erkannt, beenden diese Stationen ihre Sendung und versuchen sofort oder nach einer Slot-Time von 51,2 µs (entspricht 512 Bit, gilt nur für 10/100 MBit/s Ethernet, 4,096 µs und 4096 Bit bei 1 GBit/s) erneut ihre Sendung über das Ethernet zu übertragen. Dabei kann es erneut zu einer Kollision kommen, wenn beide Stationen zufällig die gleiche Wahl treffen. Beim nächsten Versuch wird nun jede der beiden Stationen wieder per Zufallsentscheidung einen neuen Starttermin auswählen, diesmal aber aus vier Möglichkeiten: 0, 1, 2 oder 3 Slot-Times, also 22.Bei einer erneuten Kollision sind es dann 23 = 8 Möglichkeiten, dann 16, 32, 64, 128, 256, 512 und schließlich 1024. 1024 (210) stellt auch die Maximalgrenze der Möglichkeiten dar (truncated).Nach insgesamt 16 erfolglosen Übertragungsversuchen mit Kollision wird mit einer Fehlermeldung des Ethernet-Controllers abgebrochen. (de) Exponential backoff is an algorithm that uses feedback to multiplicatively decrease the rate of some process, in order to gradually find an acceptable rate. These algorithms find usage in a wide range of systems and processes, with radio networks and computer networks being particularly notable. (en) Le binary exponential backoff (BEB) est un algorithme utilisé dans le protocole Ethernet pour limiter la charge du réseau quand une collision se produit entre deux messages émis simultanément par deux stations. * Portail des télécommunications (fr) In telecomunicazioni l'algoritmo di backoff esponenziale è un algoritmo utilizzato nel protocollo di accesso multiplo CSMA/CD per decidere il tempo di subentro in trasmissione su mezzo condiviso da parte di una o più stazioni (host) trasmittenti una volta che è stata riscontrata una collisione. L'algoritmo si applica in seguito alla ricezione della sequenza di jamming che definisce il messaggio di interruzione della trasmissione del pacchetto. Come è ben noto Ethernet utilizza il protocollo CSMA/CD, cioè il canale sul quale vengono trasmessi i frame viene condiviso da più stazioni (Multiple Access) che sono in grado di vedere quando il canale è libero o meno (rilevamento della portante o Carrier Sense) e di rilevare le collisioni (Collision Detection).La caratteristica principale del protocollo CSMA/CD è che una volta rilevata una collisione, si attende un intervallo casuale prima di ritrasmettere, questo intervallo viene calcolato ogni volta tramite l'algoritmo di backoff esponenziale. (it) Экспоненциальная выдержка — это алгоритм, использующий обратную связь для мультипликативного уменьшения частоты некоторого процесса, чтобы постепенно найти приемлемую частоту. (ru) BEB (ang. Binary Exponential Backoff) – algorytm wykorzystywany przez metodę CSMA/CD w sieci Ethernet. Algorytm ten po kolizjach losuje liczbę z przedziału Liczba ta w jednostce zwanej „slot time” oznacza czas, jaki stacja będzie musiała odczekać, zanim powtórnie rozpocznie nadawanie. Algorytm ten dostosowuje się do natężenia w sieci – wraz z jego wzrostem, a zatem i liczbą kolizji w sieci, losowana jest liczba z szerszego przedziału. Górna granica przedziału jest przeważnie ograniczona do 10, co daje maksymalny czas oczekiwania 1023 jednostek „slot time”. (pl) |
| dbo:wikiPageID | 1148272 (xsd:integer) |
| dbo:wikiPageLength | 12481 (xsd:nonNegativeInteger) |
| dbo:wikiPageRevisionID | 1106690929 (xsd:integer) |
| dbo:wikiPageWikiLink | dbr:Algorithm dbr:Upper_and_lower_bounds dbr:Deterministic_algorithm dbc:Ethernet dbr:Computer_network dbr:Radio_network dbr:Point-to-multipoint_communication dbr:Control_theory dbr:Collision_(telecommunications) dbr:Closed-loop_controller dbr:Time-division_multiplexing dbr:Time dbr:Web_service dbr:Rate_limiting dbr:Expected_value dbr:Exponential_function dbr:Feedback dbr:Discrete_uniform_distribution dbr:Network_congestion dbr:Quality_of_service dbr:Retransmission_(data_networks) dbr:Round-trip_time dbc:Scheduling_algorithms dbr:Interval_(mathematics) dbc:Network_scheduling_algorithms dbr:Law_of_large_numbers dbr:Bit_time dbr:Telephone_network dbr:Data_frame dbr:Carrier-sense_multiple_access_with_collision_avoidance dbr:Carrier-sense_multiple_access_with_collision_detection dbr:Randomized_algorithm dbr:Session_Initiation_Protocol dbr:Multiplexing dbr:User_Datagram_Protocol dbr:Ethernet dbr:Exponential_growth dbr:IEEE_802.3 dbr:Media_access_control dbr:Slot_time dbr:Oscillator |
| dbp:wikiPageUsesTemplate | dbt:Cite_book dbt:Math dbt:Mvar dbt:Reflist dbt:Short_description dbt:Use_dmy_dates dbt:Wiktionary dbt:FS1037C |
| dct:subject | dbc:Ethernet dbc:Scheduling_algorithms dbc:Network_scheduling_algorithms |
| gold:hypernym | dbr:Algorithm |
| rdf:type | dbo:Software yago:WikicatNetworkProtocols yago:WikicatNetworkingAlgorithms yago:Abstraction100002137 yago:Act100030358 yago:Activity100407535 yago:Algorithm105847438 yago:Communication100033020 yago:Direction106786629 yago:Event100029378 yago:Message106598915 yago:Procedure101023820 yago:Protocol106665108 yago:PsychologicalFeature100023100 yago:YagoPermanentlyLocatedEntity yago:Rule105846932 yago:Rule106652242 yago:WikicatAlgorithms |
| rdfs:comment | Exponential backoff is an algorithm that uses feedback to multiplicatively decrease the rate of some process, in order to gradually find an acceptable rate. These algorithms find usage in a wide range of systems and processes, with radio networks and computer networks being particularly notable. (en) Le binary exponential backoff (BEB) est un algorithme utilisé dans le protocole Ethernet pour limiter la charge du réseau quand une collision se produit entre deux messages émis simultanément par deux stations. * Portail des télécommunications (fr) Экспоненциальная выдержка — это алгоритм, использующий обратную связь для мультипликативного уменьшения частоты некоторого процесса, чтобы постепенно найти приемлемую частоту. (ru) BEB (ang. Binary Exponential Backoff) – algorytm wykorzystywany przez metodę CSMA/CD w sieci Ethernet. Algorytm ten po kolizjach losuje liczbę z przedziału Liczba ta w jednostce zwanej „slot time” oznacza czas, jaki stacja będzie musiała odczekać, zanim powtórnie rozpocznie nadawanie. Algorytm ten dostosowuje się do natężenia w sieci – wraz z jego wzrostem, a zatem i liczbą kolizji w sieci, losowana jest liczba z szerszego przedziału. Górna granica przedziału jest przeważnie ograniczona do 10, co daje maksymalny czas oczekiwania 1023 jednostek „slot time”. (pl) Der Binary Exponential Backoff ist ein Stauauflösungsmechanismus im Ethernet nach IEEE 802.3. Wird von Stationen im Ethernet eine Kollision erkannt, beenden diese Stationen ihre Sendung und versuchen sofort oder nach einer Slot-Time von 51,2 µs (entspricht 512 Bit, gilt nur für 10/100 MBit/s Ethernet, 4,096 µs und 4096 Bit bei 1 GBit/s) erneut ihre Sendung über das Ethernet zu übertragen. Dabei kann es erneut zu einer Kollision kommen, wenn beide Stationen zufällig die gleiche Wahl treffen. Beim nächsten Versuch wird nun jede der beiden Stationen wieder per Zufallsentscheidung einen neuen Starttermin auswählen, diesmal aber aus vier Möglichkeiten: 0, 1, 2 oder 3 Slot-Times, also 22.Bei einer erneuten Kollision sind es dann 23 = 8 Möglichkeiten, dann 16, 32, 64, 128, 256, 512 und schließlic (de) In telecomunicazioni l'algoritmo di backoff esponenziale è un algoritmo utilizzato nel protocollo di accesso multiplo CSMA/CD per decidere il tempo di subentro in trasmissione su mezzo condiviso da parte di una o più stazioni (host) trasmittenti una volta che è stata riscontrata una collisione. L'algoritmo si applica in seguito alla ricezione della sequenza di jamming che definisce il messaggio di interruzione della trasmissione del pacchetto. (it) |
| rdfs:label | Binary Exponential Backoff (de) Exponential backoff (en) Algoritmo di backoff esponenziale binario (it) Binary exponential backoff (fr) Binary Exponential Backoff (pl) Экспоненциальная выдержка (ru) |
| owl:sameAs | freebase:Exponential backoff yago-res:Exponential backoff wikidata:Exponential backoff dbpedia-de:Exponential backoff dbpedia-fr:Exponential backoff dbpedia-hu:Exponential backoff dbpedia-it:Exponential backoff dbpedia-pl:Exponential backoff dbpedia-ru:Exponential backoff https://global.dbpedia.org/id/RXvG |
| prov:wasDerivedFrom | wikipedia-en:Exponential_backoff?oldid=1106690929&ns=0 |
| foaf:isPrimaryTopicOf | wikipedia-en:Exponential_backoff |
| is dbo:wikiPageRedirects of | dbr:Exponential_back-off dbr:Truncated_binary_exponential_back-off dbr:Truncated_binary_exponential_backoff dbr:Binary_exponential_backoff dbr:Exponential_backoff_algorithm dbr:TBEB |
| is dbo:wikiPageWikiLink of | dbr:List_of_algorithms dbr:Spinlock dbr:Computer_network dbr:Collision_avoidance_(networking) dbr:Compare-and-swap dbr:Beb dbr:Transmission_Control_Protocol dbr:Network_congestion dbr:List_of_exponential_topics dbr:Windows_Vista_networking_technologies dbr:Thundering_herd_problem dbr:Exponential_back-off dbr:IEEE_802.15.4 dbr:Carrier-sense_multiple_access_with_collision_detection dbr:Multiple_Access_with_Collision_Avoidance_for_Wireless dbr:Service_mesh dbr:Truncated_binary_exponential_back-off dbr:Truncated_binary_exponential_backoff dbr:Binary_exponential_backoff dbr:Exponential_backoff_algorithm dbr:TBEB |
| is rdfs:seeAlso of | dbr:Exponential_decay |
| is foaf:primaryTopic of | wikipedia-en:Exponential_backoff |