4 ms·

Now I'm curious. I thought collision avoidance generally meant giving each machine a more or less constant allocation of 1/N of the total bandwidth, efficient w

Now I'm curious. I thought collision avoidance generally meant giving each machine a more or less constant allocation of 1/N of the total bandwidth, efficient when every machine wants to transmit all the time, but in the usual case where traffic is unpredictably bursty and most machines are idle most of the time, collision detection is in practice better. But you say collision avoidance is strictly better. Why?

Gibbon1 7y ago
One issue you have is it's difficult for everyone to see the same line condition. There is always a small chance you'll see a collision anyways. When the network gets busy that small chance becomes no longer small. And every time you have a collision you have a retransmission. Eventually the network begins to thrash. What I've seen with wireless stuff is simple algorithms can only get you to about 20% network utilization.
- rwallace 7y ago
  There is some theorem that says network utilization with collision detection can be as low as 1/e^2, though in practice it rarely approaches that. 20% sounds like a plausible bad case if the network is heavily loaded and the stars are not lining up right. But how do you get dramatically better with collision avoidance? If you've allocated most of the available bandwidth to machines that are leaving it unused, utilization could well drop substantially below 20%.
  - Gibbon1 7y ago
    If you look at token ring, idle machines just pass the token on if they don't have a packet to send. Other systems have central coordination and assign 'channels'. I think Bluetooth tries to do that for audio. (unsure)
    - archi42 7y ago
      BT channel-hops 1600 times/second - at least that's what it did years ago when I memorized this for an exam. I don't recall audio getting some special handling, but it was only SBC and maybe AptX back then. Yes, WiFi can run some coordination function, but can't recall the details. Maybe it's called DCF/Distributed coordination function (same exam, I think 54 or 108MBit was the norm back then. So probably terribly outdated - but indeed: coordination isn't new for WiFi). (Yes, I could look up everything, but don't have the time right now ;-)
deleted 7y ago
[deleted]
jcrawfordor 7y ago
While simple or naive TDMA is the most obvious solution to collision avoidance (every node gets a fixed-length turn), there are more efficient methods available. Typically this takes the form of some sort of "channel reservation" scheme where each node gets a turn not to transmit, but to report whether or not it wants to transmit (and perhaps how much). Then either a coordinating point or a distributed algorithm decides how to allocate transmission time to the nodes who want it. This is often called "dynamic TDMA" and is used in various real wireless networks. There are also tricks you can pull with CDMA, OFDMA, and other flavors of multiple access. I suspect there's some mathematical upper bound on the efficiency of these schemes but I'm not sure what it is. As I understand it --- and this comes with the grain of salt that my detailed knowledge of network protocols tends to be out of historical interest and so intrinsically out of date --- WiFi does not use any collision avoidance tricks right now besides CSMA/CA which is only partially effective. There are plenty of papers you can find about improved systems but none of them seem to have been adopted, besides 802.11ax introducing OFDM and 'coloring' which mitigate but do not eliminate the problems with CSMA/CA. I only know a bit about this stuff but I think the hidden node problem makes collision avoidance fundamentally difficult and is very common for WiFi due to the short range and buildings interiors etc - which is why non-collision schemes like TDMA are used with WiFi, but generally only in more specialized situations where the network operator controls everything and can make certain guarantees about all devices being aware of each other. So when I think about it more, saying that 'collision avoidance is strictly better than collision detection' is probably actually untrue in a situation where you have to cope with hidden nodes. At least that's my non-expert thinking.

Gibbon1 7y ago

One issue you have is it's difficult for everyone to see the same line condition. There is always a small chance you'll see a collision anyways. When the network gets busy that small chance becomes no longer small. And every time you have a collision you have a retransmission. Eventually the network begins to thrash. What I've seen with wireless stuff is simple algorithms can only get you to about 20% network utilization.

rwallace 7y ago
There is some theorem that says network utilization with collision detection can be as low as 1/e^2, though in practice it rarely approaches that. 20% sounds like a plausible bad case if the network is heavily loaded and the stars are not lining up right. But how do you get dramatically better with collision avoidance? If you've allocated most of the available bandwidth to machines that are leaving it unused, utilization could well drop substantially below 20%.
- Gibbon1 7y ago
  If you look at token ring, idle machines just pass the token on if they don't have a packet to send. Other systems have central coordination and assign 'channels'. I think Bluetooth tries to do that for audio. (unsure)
  - archi42 7y ago
    BT channel-hops 1600 times/second - at least that's what it did years ago when I memorized this for an exam. I don't recall audio getting some special handling, but it was only SBC and maybe AptX back then. Yes, WiFi can run some coordination function, but can't recall the details. Maybe it's called DCF/Distributed coordination function (same exam, I think 54 or 108MBit was the norm back then. So probably terribly outdated - but indeed: coordination isn't new for WiFi). (Yes, I could look up everything, but don't have the time right now ;-)

deleted 7y ago

[deleted]

jcrawfordor 7y ago

While simple or naive TDMA is the most obvious solution to collision avoidance (every node gets a fixed-length turn), there are more efficient methods available. Typically this takes the form of some sort of "channel reservation" scheme where each node gets a turn not to transmit, but to report whether or not it wants to transmit (and perhaps how much). Then either a coordinating point or a distributed algorithm decides how to allocate transmission time to the nodes who want it. This is often called "dynamic TDMA" and is used in various real wireless networks. There are also tricks you can pull with CDMA, OFDMA, and other flavors of multiple access. I suspect there's some mathematical upper bound on the efficiency of these schemes but I'm not sure what it is. As I understand it --- and this comes with the grain of salt that my detailed knowledge of network protocols tends to be out of historical interest and so intrinsically out of date --- WiFi does not use any collision avoidance tricks right now besides CSMA/CA which is only partially effective. There are plenty of papers you can find about improved systems but none of them seem to have been adopted, besides 802.11ax introducing OFDM and 'coloring' which mitigate but do not eliminate the problems with CSMA/CA. I only know a bit about this stuff but I think the hidden node problem makes collision avoidance fundamentally difficult and is very common for WiFi due to the short range and buildings interiors etc - which is why non-collision schemes like TDMA are used with WiFi, but generally only in more specialized situations where the network operator controls everything and can make certain guarantees about all devices being aware of each other. So when I think about it more, saying that 'collision avoidance is strictly better than collision detection' is probably actually untrue in a situation where you have to cope with hidden nodes. At least that's my non-expert thinking.