Ethernet's Binary Exponential Backoff Algorithm

Topics including TCP/IP, OSI, Netbios, exploiting share, proxies and much more
Post Reply
User avatar
Aiden
Administrator
Posts: 1080
Joined: Tue Oct 31, 2006 11:11 pm
Location: /usr/bin/perl

Ethernet's Binary Exponential Backoff Algorithm

Post by Aiden » Sun Dec 13, 2009 6:18 pm

The Binary Exponential Backoff algorithm is a method of avoiding congestion on an Ethernet network. The algorithm is evaluated by all participants in a collision.
  • At first, all computers in the collision continue transmitting a 48-byte "Jam Packet." This packet ensures that everyone involved in the collision are aware that there has been a problem, which otherwise might not be the case.
  • As the jam packets finish transmitting, each computer chooses a random number from the mathematical set {0, 1} and waits that many slot times, where a slot time is the time alotted to transmit one minimum-sized frame.
  • After a wait time is over, computers listen to the line again to determine whether it's free to transmit on or currently in use. If it's in use, the algorithm exits early and the computer transmits as normal when the line frees up (and the algorithm starts over in the event of a second collision). If the network is not busy, the computer tries to retransmit its data.
  • Now, assuming there were two computers involved in the initial collision, both computers will have chosen either 0 or 1 slot times to wait until they retransmit. This means that there is a 50% chance that a second collision will occur. With three initial computers in the first collision, there is a 100% chance for a second collision.
  • If a second collision is detected by the hosts trying to transmit data, they will send their jam packet again. They will follow the same steps as before to determine how many slot times to wait before transmitting, except this time their set of choices increases by a power of two -- instead of {0, 1}, they now choose randomly from {0, 1, 2, 3}.
  • After waiting for the selected amount of slot times, the process is the same as before: if the line is busy when a host finishes waiting, the algorithm stops and the host waits until the network is quiet. Otherwise, it tries to transmit again.
  • Each subsequent collision increases the mathematical set the computers choose from by a power of two, making the use of a busy Ethernet network extremely inefficient (compared to networks that handle congestion differently, such as token rings).
My first thoughts when I learned about this algorithm were something along the lines of, "So, can I knock a computer offline indefinitely by transmitting small packets every time slot? Can I overflow a router's buffer by increasing the number set enough?"

As for the first question, "So, can I knock a computer offline indefinitely by transmitting small packets every time slot?", it may be possible, but it'd be extremely difficult. First of all, the network would have to be one-hundred-percent quiet (which might prove difficult due to things like ARP) because if something was being transmitted when a computer stopped waiting after a collision, the algorithm would end. Secondly, the packets would have to be crafted to pulse on the slot times extremely precisely. They would have to be transmitted after the computer listens to determine if it's okay to transmit, but before the target's packet reaches it's destination. So, I guess it's possible, but highly impractical on any "normal" network.

The second question, "Can I overflow a router's buffer by increasing the number set enough?" can be answered much easier: for the most part, no. The algorithm in use by most Ethernet networks is called a Truncated Binary Exponential Backoff algorithm. The keyword, truncated, applies here: a limit is set on the number of times the number set can increase. After the limit has been reached, the computers continue to pick random numbers from it to determine how many slot times to wait, but it will not increase further. Additionally, Ethernet was designed to work the same in both home networks (with a few devices on the network) and in corporate networks (sometimes with thousands of devices). This means that they had to account for the times that enough computers will be caught in a collision to effectively DDoS themselves in a truncated number set. Because of this, hosts will stop trying to send their data after 16 consecutive collisions.
"When it takes forever to learn all the rules, no time is left for breaking them."

User avatar
foldingstock
htd0rg lieutenant
Posts: 300
Joined: Sat Aug 16, 2008 10:38 pm

Re: Ethernet's Binary Exponential Backoff Algorithm

Post by foldingstock » Tue Dec 15, 2009 1:47 am

drusepth wrote:My first thoughts when I learned about this algorithm were something along the lines of, "So, can I knock a computer offline indefinitely by transmitting small packets every time slot? Can I overflow a router's buffer by increasing the number set enough?"
On a hub, yes. On a switch, where each port is a collision domain, no. Collision domains were specifically designed to prevent this type of activity.
"If a man empties his purse into his head, no one can take it from him."
- Benjamin Franklin

guidj0s
Hacker in Training
Posts: 74
Joined: Sat Oct 10, 2009 11:29 pm
Contact:

Re: Ethernet's Binary Exponential Backoff Algorithm

Post by guidj0s » Sun Dec 20, 2009 10:59 am

Couldn't you just listen for jam packets and then, based on the number of computers involved in the collision, send 2^n small packets (one for each number of slot times in our set), thus knocking the whole network off (or at least the part of the network we can see, which varies according to the topology applied)? You wouldn't have to make the computers "think" they can transmit, just make the line occupied indefinitely.

Also, unless I'm very mitaken, this algorithm is also applied to treat jams in internal computer buses.

Post Reply