WiFi's Hidden ____ Problem - Computerphile

so i thought one thing that'd be interesting to talk about is wi-fi's hidden node problem and this applies to any sort of wireless networks but it's a it's an interesting thing that appears when you start using wireless networks to communicate so let's start with a little diagram and we'll build this up as we're going typical wireless network we have a access point which will represent as an aerial and then we'll have our laptop or something that we want to connect to it so they can communicate via wireless networking so it sends a signal over a radio wave on a particular frequency to the access point and the access point can send one back on the same frequency wi-fi uses the same frequency to transmit and send so this machine is able to detect if anything else is sending on the network as well now as we all know because we've all fallen found of this is that we walk too far away from the access point and we suddenly lose signal there is a range on wi-fi as we move further away the signal drops off the intensity drops the signal strength drops and eventually it goes off a cliff and you lose connectivity now why is that a problem well the problem we've got is if we've got more than one node in our network let's just draw another person using a laptop or some device here then if they both try to transmit at the same time so let's call this machine a and let's call that one machine b if machine a tries to transmit that's fine it can use the shared medium the shared radio space to transmit and machine b could transmit at a different point it can use the same shared radio space to transmit and the data gets transmitted and received by the access point no problem but if these were to try to transmit at the same time then they would both use the same radio space and the signals would interact with each other interfere with each other they'd corrupt each other and so at the access point there'd be garbage received and the data wouldn't be transmitted so the way that wi-fi is designed it borrows from ethernet and quite a lot but the way it's designed is it before it transmits a device will listen on the network because it can receive on the same frequency unlike when we looked at aloha wi-fi transmission receives on the same frequency so we can hear what other devices are doing it'll listen on the network and ask the question is there anything being transmitted if there's something being transmitted then it thinks well okay if i transmit now it's going to corrupt that my data is not going to get through the other person's state it's not going to get through what it does is it waits for a certain amount of time and then after that certain amount of time we should pick a random delay it will then transmit its data if the network is saying clear if the wireless frequency is then clear at that point so if you've got multiple nodes in there it's not a problem because they can cooperate before any node sends it will listen to the wireless space and if it's empty of signals there's no carrier then it will transmit this is what we call carrier sense with multiple access it's used on wi-fi it's used on ethernet and things it's the idea that before you're transmitting something you listen to check that there's no carrier present before you send it because otherwise it's just gonna corrupt it which is quite how we do human speech yeah absolutely i waited till the break then before i said that yeah exactly that's a really good analogy um we've all sort of been in situations where if you wanna have a good conversation one person's talking then when they stop you start and things you don't start talking while someone else is talking otherwise it ends up as an intelligence you can't tell what exactly is it's happening now exactly exactly now the thing we have to remember is that each of these machines there's a range that the signal will go we said that at the beginning as you move away from the wireless access point signal drops off and so on so let's just draw a circle this is an arbitrary size circle it's not going to be a circle and there's going to be a similar one for this machine which is probably going to do something like let's label this this is the one for machine b and this is the one for machine a now both of these circles they go on bigger in the other side as well machine a and machine b are in those things so they can hear when the other one transmits not a problem let's suppose we have a third machine though let's call it machine c and it's right down here we'll call that machine see can you see that on the other camera yes you can hi and let's suppose though that its transmission circle the range it can get sort of just that now it can transmit perfectly fine to the access point and it can receive data a can transmit to the access point it can receive data b can transmit to the access point but the key problem we've got here is that machine c is out of range of both machine a and b so we could get the problem where machine a decides if the network's clear because he can't hear anything on there he can't sense anything on the wireless frequencies and machine c does exactly the same thing it can't sense anything on the wireless frequencies and they both try and transmit at the same time and what's actually received by the access point is just corrupted data neither packet got through this is what we call the hidden node problem because there's another node that this machine is not aware of that can transmit and vice versus another there's nodes that this machine is not aware of that can transmit but the actual thing they're transmitting to can hear both of them because it's sitting in this gap in the middle where it can hear all of them and so we need to have some way that we can organize these machines so that when they transmit they do so in a way so that the access point doesn't get corrupted data even though machine a and c can't see or hear each other they can't pick up each other's transmissions now you've got a similar problem on the original ethernet back when you had a shared physical piece of wire for each machine on ethernet they were all connected to that you had exactly the same problem and they used the same idea of carrier sense with multiple access in that they would wait until the network was clear but they could detect because the signal was on a piece of why it didn't drop off in the same way they could detect if another machine transmitted at the same time and so they could detect the collision stop transmitting wait a random amount of time and then re-transmit and as long as the random amount of times were different one of them would be able to transmit and the other would get it through you can't do that on wi-fi because it can't detect the carrier from this machine and vice versa this can't detect the carrier from that machine so we need to take a different approach so on ethernet they use the system called csma carrier sense multiple access with collision detection we should probably do a computer file on that at some point that was the original ether these days when it switched and things that problems disappeared but that's another computer file that someone needs to do at some point can't do that with wi-fi so we need a different approach and the approach we use is carrier sense multiple access with collision avoidance so we use this sort of this approach instead so with ethernet you detect the collision and recover from it with wi-fi you try and stop the collision happening in the first place so you do something with the three machines and the access point you've got here to stop the collision in the first place let's think about the problem we've got we've got a problem where machine a and machine c are transmitting at the same time the data's interfering with each other we need something to try and stop them transmitting at the same time so what we want is a mechanism where one of the machines let's use machine as an example can reserve the radio space while it sends a packet so he wants some way of reserving it so all the other machines know don't send anything at this point and so the way that we do this in wi-fi is we send out what's called a request to send or rts message from the machine that's trying to send to the access point so this sends out a request to send message and this message is designed to be very very short the idea being that it's very very short it's very unlikely to collide with anything and so we send a message out from machine a that's very very small it's received by the access point it's not received by machine c but it's received by the access point and it gets that request to send and then it sends back what's called a clear to send packet with details of which machine is clear to send and it sends that out over the wi-fi network and the beautiful thing about that is that when the clear to send messages sent out it'll go out to all the machines will also be picked up by machine c even though it's not in range of a and b and so didn't get the request to send packet it will still see the clear to send and so it knows at that point that hang on something's about to transmit on this network okay i was about to send something but i know it's been reserved for another machine i'll wait some specified period of time before i send out my request to send to the access point and sort of get the permission to use the shared radio space to send my messages so what we do with collision avoidance which stop the collision happening in the first place by getting each of the machines to reserve the radio space before they send their data you might think what happens if machine a and c both send a request to send at the same time well that's not a problem because if they both end at the same time then it'll either get corrupted in which case the access point doesn't receive it and doesn't send out the clear to send so neither of them receive the clear to send so never send out their data they'll just delay for some period of time and then try to send out the request to send again or one of these will get through fractionally before the other and when they receive the clear to send the other machine will see that it's not for them that they've received that clear to send so they don't send anyway so and then they can send the request to send anyway so this approach of just sending out a very small package means that it's very unlikely to collide anyway because it's so short and so the chances of two machines in that very small time period transmitting at the same time becomes very very small if you're sending out a 1500 byte packet much more chance of that colliding with something else i mean if you think about it if you're sending out 1500 bytes that'll take a certain amount of time and you're sending out another 1500 baht's that only has to sort of move back one byte of overlap when you've corrupted both packets even though most of them have actually got transmitted without any problem if you're sending sort of a very small 64 or less whatever size it is packet then the chances of them overlapping are far less example of this if you've ever seen a very big heavy goods vehicle going down the road what you'll often see first is that they don't just send that down in one go and sort of try and force it through waiting for the other bits of the traffic to get off the road you often see there's police dispatch riders and things that go ahead of it which sort of clear the road first so that the heavy goods vehicle could go through and things exactly the same thing here we're sending out the request to send which clears the way and then the big packet that we want to transmit goes through after it the only slight change from that that those actually does i think in wi-fi is that if the data you're sending is very very small then it's sort of bundled in with the request to send because otherwise it ends up using more bandwidth than you need to the chances are that the data will get there and again you're going to send out another request to send if you don't get it so if the date is very very small you can still send it out and sort of optimize things a bit there so that's the hidden node problem and the way that we use carrier sense multiple access with collision avoidance to solve it on wi-fi uh over and out yep over and out so you should never say over and out it's just out is it yeah because as soon as you say overly saying i'm not going to talk anymore so if you say over and out you're the first ever is sort of broken i think so just out okay i've never used cb radio but i have heard that but it is literally that's that's another shared medium isn't it yeah exactly sort of exactly you need some kind of protocol you need a protocol to sort of use this at the same time and things so yeah it's good analogy out out if we just scroll forward in time we can see that as things start to happen we get to this point where everything starts to reroute and rather than going directly to facebook you can start to see w this is some actual cypher text that we'll be breaking later does it honestly start with zoos as in conrad's views yeah the reality of random yeah

Channel: Computerphile

Views: 517,645

Keywords: computers, computerphile, computer, science, Computer Science, University of Nottingham, Dr Steve Bagley, WiFi, 4K, UHD, problem, hidden node

Id: UgQM0rVDIQE

Length: 12min 5sec (725 seconds)

Published: Tue Oct 19 2021