There are questions that come up regularly on the MailingLists and on the wiki.
How does a Point to Point link in this network work? What does the topology of the network look like? Why is it set up like that? What's the reasoning behind it?
These are important questions, and they need answering, unfortunately it's a bit complex. I'm going to do my best to answer them here. This is an attempt to munge a year and a halfs worth of planning and research into a single document. I dont generally write books and am best at whiteboard discussions, this is somewhat hard to write, so it's going to take me a little bit of time (I started this three days ago). There are some unanswered questions here, and it may not be in the best order yet. I will try to refactor it once I'm done with what I can stream out onto the page. Please refrain from asking questions inline for a while. Thanks. --MattWestervelt
First things first, A couple of things need to be explained.
![/!\](/moin_static180/modernized/img/alert.png "/!\"){kind=small}
Some of this is out of order, I'm shuffling it to make more sense.
Contents
TCP/IP, Layers
It helps to understand TCP/IP and the 7 layer OSI model or TCP/IP 5 Layer model before you go further. My definitions are brief and may lead to confusion right now.
OSI 7 layer and 5 layer http://www.gslis.utexas.edu/~l38613dw/readings/NotesOnInterconnection.html
A whole lot of information about TCP/IP http://www.garykessler.net/library/tcpip.html
What is Layer 5?
Applications. This is where netscape and other network applications live.
What is Layer 4?
Transport. TCP and UDP live here.
What is Layer 3?
Layer 3 is defined as the Network Layer. It provides addressing and routing. It defines how packets are broken up, sent and assembled over the Link layer.
This is where Internet Protocol (IP) lives.
For our discussion, routing that happens in this level will be referred to as IpRouting
What is Layer 2?
Layer 2 is defined as a Data Link layer. It is used for the physical transport of bits across a network. It is protocol independent. It can transfer TCP/IP packets or Banyan Vines, Novell, or Microsoft NetBUI. It can be Ethernet, Token Ring, Fiber Optic, Laser, or in our case, 802.11b
This where MAC addresses live.
For our discussion, routing that happens in this level will be referred to as ArpRouting
What is Layer 1?
Physical layer. copper, fiber or radio waves. Provides the medium in which the bits travel.
What is 802.11b
802.11b is a standards based Layer 2 protocol designed by the Institute of Electrical and Electronics Engineers (IEEE) to provide wireless connectivity between computers. Think of it like you would 802.3 ethernet. It does not provide anything other than an electronic link between computers. Adding network protocols on Layer 3 (IP) and Layer 4(TCP/UDP) allows those computers to talk to each other in a meaningful way. Because of the nature of Wireless communication, it is not as straightforward as ethernet (there is no wire connecting all the machines), and you run into problems.
One such problem is a hidden node.
What is a hidden node
Wireless link is created by a radio broadcasting a signalling beacon to another radio. If another radio picks up the signal, it also sends a beacon, and the conversation is initiated. Put a bunch of radios in one room, they can all talk to each other directly. There is no routing.
I guess it's time to start drawing diagrams.
We'll start with the basics.
A, B, and C are computers with wireless cards
Each computer is within range of every other computer.
A-----B | / | / | / | / C
If they are all within range of each other, communication is simple.
- A can establish a connection to B or C
- B can establish a connection to A or C
- C can establish a connection to A or B
A problem arises when all radios are not in range of each other.
A--------------B--------------C
A, B, and C are computers with wireless cards.
Each computer is just at the limit of the others range.
- A can establish a connection with B.
- B can establish a connection with either A or C
- C can establish a connection with B
A cannot establish a connection with C. It is out of range. It does not know it exists. This is a limitation of a wireless link layer.
What other problems can a hidden node cause?
A--------------B--------------C
Node A, B, and C are participating in a network.
When node A can see B, but not node C, and node C can see node B but not node A, a hidden node condition occurs. Since node A cannot see when node C is transmitting, they can cause excessive collisions at node B.
What can I do to help solve the blind node problem?
Implementation of a flow control system in 802.11 called RTS/CTS.
RTS = RequestToSend CTS = ClearToSend
Framing primer: Whenever an 802.11 frame is sent, a value is placed into something called the "NAV". This NAV is a virtual carrier detection system, and a value is provided in microseconds to keep the rest of the chatter down during an atomic operation.
RTS/CTS can also be given a threshold. This threshold is at what frame size an RTS should be made. If it is under this size, an RTS is not sent.
RTS is first transmitted over the air when the radio channel appears to be clear and after the DIFS (distributed InterFrameSpacing ). This RTS contains a NAV value which contains the expected duration of this atomic operation. All nearby stations take this value and stay off the medium for this period.
(A--------------B-)------------C In our hip ASCII diagram, node that this RTS message is received by any nodes in range, including node B.
After B receives this RTS, it sends a CTS message directed back towards node A. This CTS contains a slightly shorter value in the NAV, transmitted to all nodes in range to keep the medium clear for at least this time duration. This CTS is sent in the SIFS (short InterFrameSpacing ), which is the shortest time slot between two frames. SIFS is reversed for high priority traffic, such as CTS, ACK, fragments, etc. and other vital pieces of an atomic operation.
(A--------------B--------------C) In our hip ASCII diagram, node that this RTS message is received by any nodes in range, including node A and C. Everyone is now aware that a transmission is taking place.
After A receives a CTS from node B, A then transmits the data frame after the SIFS. If the frame is fragmented, each fragment is sent after the SIFS. The NAV is updated accordingly.
If data was intact, the last segment of data is ACK'ed by station B, which contains a low NAV value. If the data was corrupt at any given point, station B will not NAK or ACK the frame in any way. If A doesnt see an ACK, it will retransmit the frame until finally dropping it.
Once the NAV values given timeout, and after DIFS (distributed InterFrameSpace ), everyone is free to transmit.
RTS/CTS does reduce collisions in high usage environments, but the extra overhead will significantly reduce throughput. Especially if Node B is routing data between Node A and Node C with an omni directional antenna, as it will require a doubling of the operation above. This ultimately consumes radio time which will consume actual throughput.
IBSS Explained
IBSS is the simplest form of 802.11b link layer. It does not attempt to solve any hidden node issues. There is no Layer 2 routing involved. The only limitation is the limitation that is inherent in wireless networking.
BSS Explained
BSS is an IEEE specification designed to combat this hidden node problem in the Link layer. It creates a Master / Client routing relationship with the nodes on the network.
A--------------B--------------C
A, B, and C are computers with wireless cards.
Each computer is just at the limit of the others range.
If B is a BSS master and A and C are BSS Clients,
- A can establish a connection with B
- A can establish a connection with B which can route it to C
- B can establish a connection with either A or C
- C can establish a connection with B
- C can establish a connection with B which can route it to A
Lets try it again with different roles.
A--------------B--------------C
A, B, and C are computers with wireless cards.
Each computer is just at the limit of the others range.
If A is a BSS master, and B and C are BSS Clients,
- A can establish a connection with B
- B can establish a connection with A
C cannot establish a connection with B. They are both BSS Clients and must use an intermediary (A) to connect to each other. A is out of range. C requires a BSS Master to talk on the network.
This is a limitation of BSS.
Where should I route? Layer 2 or Layer 3?
This question should really be: Where Can I route?
Routing can happen in two places. Layer 2 and Layer 3. Using 802.11b standards based equipment, The only Layer 2 routing that we have available to us is BSS. BSS solves one problem. Hidden nodes.
This problem can also be solved using Layer 3.
Remember the original diagram? Lets modify it a little bit.
A--------------B--------------C
A, B, and C are computers with wireless cards
Each computer is just at the limit of the others range.
They are using Layer 3 (IP)routers and are in IBSS mode.
- A can establish a connection with B which can route it to C
- B can establish a connection with either A or C
- C can establish a connection with B which can route it to A
None of these computers are in a Master / Client relationship. They do not have the Layer 2 limitation because they use Layer 3 to overcome it.
Lets change something in the diagram.
A, B, and C are computers with wireless cards
Each computer is within range of every other computer.
They are using Layer 3 (IP)routers and are in IBSS mode.
A-------B | / | / | / | / | / | / C
- A can establish a connection with either C or B directly
- A can establish a connection with B which can route it to C
- A can establish a connection with C which can route it to B
- B can establish a connection with either A or C directly
- B can establish a connection with A which can route it to C
- B can establish a connection with C which can route it to A
- C can establish a connection with either A or B directly
- C can establish a connection with A which can route it to B
- C can establish a connection with B which can route it to A
Pretty cool right? Every machine can talk, and they all have two routes to get to each one.
OK. Lets try that again and add BSS mode.
A, B, and C are computers with wireless cards
Each computer is within range of every other computer.
They are using Layer 3 (IP)routers and are in BSS mode.
We'll say that A is the BSS Master and B and C are BSS Clients.
A-------B | / | / | / | / | / | / C
Remember, All packets have to pass through A on Layer 2.
- A can establish a connection with either C or B directly
- A can establish a connection with B which can route it to A and back to C
- A can establish a connection with C which can route it to A and back to B
- B can establish a connection with A directly
- B can establish a connection with A which can route it to C
- C can establish a connection with A directly
- C can establish a connection with A which can route it to B
This is somewhat limiting. All the machines can talk, but every route must include Machine A.
Layer 2 routing in 802.11b actually makes things less flexible. Also, if machine A goes down, no machine can talk
What does this mean to us?
OK. if you followed the above, it should be fairly obvious that IBSS is more flexible than BSS.
Flexible is good. We like flexibility. So... What's next?
If we want to turn every node into a router, we can look into adhoc routing protocols like Grid or MadHoc or MobileMesh. These network protocols are very interesting, and very experimental. It is possible to create a network made up purely of peers, however this can be problematic in practice, and is not the approach that we have decided to take.
Why not?
Like I said above ,building a completely adhoc layer 3 network is very interesting, but we have chosen to not go down this road. Why not?
First, Every machine on the network must be a router. This includes clients.
Second, Adhoc Layer 3 routing protocols are very experimental. They are being developed in tightly controlled university settings, and they still dont work.
Third, whether or not a completely peer based network can scale is an issue that is up to debate. If you look at some of the numbers on gnutella, you will see that as the network grows, traffic on that network grows exponentially. This may be solved by using Meta Nodes (like the music city network), but obviously, more work needs to be focused in this area. DARPA is very interested in adhoc networks and is working on this problem. It probably isn't something that we should focus on.
Fourth (and last for a moment) is the concept of abuse. Adhoc layer 3 networking in it's current implementations creates a flat network. This is a like putting the Internet on one giant hub. There are so many ways to kill a network like this, I could probably write a couple of pages more, but I'm trying to be somewhat brief.
What are we looking at doing then?
Well, According to our SeattleWirelessIdea page, we want to create a network where a client can walk around using a laptop or PDA and be able to connect to any other laptop or PDA in the network using a wireless connection.
We could do that using an adhoc solution, but for the reasons stated above, It doesn't strike us as the best way to do it. The technology is too new, and it requires something of our client devices that they are not designed for. Stuffing a router on a PDA seems like a bit of a hassle and probably isn't feasable.
The easiest way to do this is model it after an existing infrastructure that works well, The Internet.
The Internet is a resiliant network design that is hard to beat. It joins together many networks with redundant paths and time has shown that it is a model that works.
Simply put, We want to connect Local Area Networks (LANS) together using traditional IP Routing over point to point links. The LANs in this case are BSS based wireless LANs.
Didn't you just explain that IBSS needs to go on everything?
No. IBSS has it's place and BSS has it's place. BSS is a perfect technology for building LANS, That's what Client Nodes are expecting. IBSS will be used for creating the backbone which connects the LANS and and the combination of the two will be our Metropolitan Area Network, the MAN.
This doesn't sound very easy.
Nobody ever said this was going to be easy.
As stated above, we are building a two tiered network.
One part backbone, One part client access. Just like the Internet.
A ClientNode connects to a CxNode using BSS mode 802.11b. This is natural from the client perspective. All laptops and devices out there that talk Standards 802.11b are set to BSS Client mode by default. This is what 802.11b was created for. It's the easy part.
So, what's the difference between setting up an AccessPoint that talks to the Internet and a CxNode?
A CxNode does not set it's default gateway to the Internet. It's purpose is to get the client onto the wireless backbone, the BxNode ring. Think of the CxNode as a small ISP, and the wireless link between you and it as a phone line. It's dial up all over again. Being a client on this network is not the interesting part.
OK, tell me the interesting part
It's much more interesting to be at the core of the network, the backbone. To do this, you need to be a part of a BxNode ring.
A BxNode ring is about redundancy and resiliancy, just like the Internet. If part of the Internet goes down, it doesn't take the rest with it. The reason why is redundancy. Our model is the same. On each BxNode there are at least two upstream links to other BxNodes plus a downstream to CxNodes. Remember that IBSS Triangle with Layer 3 routing? That is a BxNode ring. Using RIPv2 or OSPF or some other smart routing protocol, we can decide which is the reliable path depending on how the network looks. If a node is down or a link is cut, it uses the alternate path.
Two upstream links and a downstream link?
For the sake of the BSS/IBSS argument, I drew the simplest design. One radio, One antenna.
This doesn't really represent the network we're trying to build very well. We want to put some distance between our links to make it across the city. We dont have the density to make it across the city using the antennas that come with our 802.11b cards, so we'll have to add antennas.
What kind of antennas?
Antennas come in a variety of shapes and sizes, and each provides a different type of coverage. The purpose of an antenna is to direct your signal in a particular direction. If you just have a device emitting radio waves, it will broadcast in a spherical pattern. At the frequency and wattage that we are emitting at, it wouldn't go very far at all.
--following antenna information added, but feel free to correct --
By using an external antenna connected to our radio sender, however, we can focus the energy to give our sender a better range. Using a directional antenna will allow BxNodes at a great distance apart(5-10 miles and up) to establish connections. Omni-directional antennas focus this same energy into a donut-shaped area which can create a coverage area up to a mile or so in radius for CxNodes or clients to connect to. CxNodes would use directional antennas to connect to the BxNode with. A BxNode and CxNode can connect using directional antennas on each end, but connecting a BxNode to several CxNodes will drastically increase the cost, as one antenna and radio sender per connecting CxNode would be necessary.
omnidirectional antennas
Omnidirectionals aren't really what they sound like. They dont send signal in all directions (like a sphere), but more like a pancake shape. The higher the gain, the flatter and wider the pancake.
directional antennas
Directional antennas squeeze the signal into a single direction into a football like shape. The higher the gain, the longer and skinnier the football, meaning the farther the signal can travel.
signal to noise
Obviously, for the most throughput, you want the best signal. What you dont want a lot of is noise. Noise breaks down your signal, and gives you less throughput. Noise is created by other devices or natural phenomenon crowding your band. 802.11b lives in 2.4gHz which is chock full of interference. Microwave ovens, cordless phones, X10 video senders, baby monitors and all sorts of other things use this unlicensed frequency. If they're in your antennas path, your signal degrades. The best thing to do to reduce this noise, is make sure that your radios antenna is only covering the area that you want signal from. The best way to do this is to use directional antennas.
OK, Directionals it is. This limits who I'm going to talk to doesn't it?
Sure does. If you really want to be redundant and keep your paths free of noise, you'll need more than one radio (It's doubtful that you're going to find your redundant paths in exactly the same direction). Not only that, you're going to need to have a router set up to pick which path you're going to use. This is not going to be a One Box Solution that you can throw up on the roof and forget about.. It's going to cost a bit more and be a tad more work than that to get your redundancy. But, If you look back at the Internet, which we're modeling our network after, it costs a bit more to have redundancy there too. If you compare the costs, This is much cheaper. Not to mention much cooler.
OK. I so need at least three radios and some antennas, and a router to pick where I'm sending my packets. I really only want one box, Can I do that?
You can do that. It's not terribly simple, but you can do it. Go buy a Soekris net4521 single board computer with two PCMCIA slots and a miniPCI and drop in your radios. Put some pigtails and antennas on the cards, and chuck it on your roof. Put something like a stripped down bsd or linux on the CF card for your routing and you're good to go. You'll still need to drop some ethernet down into your house for your access point or plug it into your LAN. We dont recommend this path though.
Why not?
For one, most single board computers aren't very powerful. You dont need a lot of horsepower to run a router (many cisco routers are 486's), but once you go down the embedded device path, you lose a lot of flexibility . There may come a time when you need to upgrade RAM in your device, need more disk space, need more CPU (in the case of encryption) or you want to upgrade the link technology to something like 802.11a or 802.11g or laser or something. Some say that it may be possible to just take out the PCMCIA card and put in an 802.11a card, and they may be right, but instead of pushing 11 megabits through that 486's bus, you're pushing 54 megabits. If you're running a really lightweight OS and you're not tagging the CPU with encryption or anything, this might not cause a single problem, but it's a really hard thing for us to rule out. I personally dont like being locked into things. Especially expensive things.
OK, what would you recommend?
We recommend that you keep the wireless link stuff as far away from the routing stuff as possible. Put the wireless up on the roof, and the routing down in the basement, phone closet, under your desk, or whatever. Why? Because there's really no reason for it to be on the roof. Also, we just dont think that a router should have to know about wireless. It's just a router. It takes bits on one interface and pushes them to another depending on it's ruleset. Another reason, and probably the best for this design, is that any link layer device can be replaced in the system without affecting the router. You could use an 802.11b link, an 802.11a link, lasers, whatever. The router can run linux, bsd, osx, ios, dos, windows 2000, etc... As long as it can route packets and interoperate with other routers on the network, it shouldn't matter what it is. Personally, I suggest that you use OpenBSD for your router using a commodity PC. You can use whatever you want, just remember that you probably want something you can upgrade and you'll probably want to do that somewhere warm. Keeping everything simple and flexible is key.
Here is a pretty flexible BxNode setup.
------------ -------
| |=-x-=| IBSS |++++++++ upstream to BxNode
| | -------
| | -------
| router |=-x-=| IBSS |++++++++ upstream to BxNode
| | -------
| | -----
| |=-x-=| iBSS |---\/\--- downstream to CxNode
| | -----
| |
----------------optional for your local network----------------
| | -----
| |=-x-=| BSS |---\/\--- OR --------> LAN
| | -----
| |
|----------|
legend:
+++++++ signifies directional antenna
--\/\-- signifies omni antenna
=--x--= signifies crossover cableThe ListOfDefinitions explains the difference between AxNode, BxNode, CxNode, and ClientNode. It might be a good idea to familiarize yourself with that before we go further.
I will be back to finish this. --MattWestervelt
I am going to continue this explanation --BobbyMoretti
To review: our network is modeled after the Internet. The Internet is a redundant scale-free network, meaning it consists of relatively few hubs with lots of links to local clients. This sort of network is remarkably resiliant to random failures (imagine the average home computer connected to the Internet failing... there is zero damage done to the overall network topology). We are not using some cool experimental peer-to-peer technology for several reasons, but the most blatant is that peer-to-peer technology does not make use of hubs. Imagine making an Internet where the end user was relied upon to pass data to other end users, and imagine one node going down. The network could be cut in two with just a few random failures.
So SeattleWireless is, at least for the time being, about building an Internet-in-miniature, complete with its own backbone, routing traffic at layer 3 (in IP). To help formalize our efforts, we classify the nodes making up the network into several categories:
A DxNode, which is an access point waiting to be connected to the SeattleWireless infrastructure.
A CxNode, which is a router with two network interfaces. One is an access point, providing 802.11 access in BSS mode. The other is an upstream link. This is usually a wireless point-to-point link, but does not have to be.
A BxNode, which is a router with three wireless interfaces. Two of them are directional, and connect to another BxNode or AxNode. The third is connected to a high-gain omnidirectional antenna, and services a local cloud of CxNodes.
An AxNode, or super BxNode, which is a router with four or more wireless interfaces routing traffic between AxNodes and BxNodes
I will be back to finish this. Soon. --BobbyMoretti
OK, How do I get IBSS Gear
Currently, all 802.11b compliant PCMCIA or MiniPci cards do IBSS.
Some USB devices or Ethernet Converters do IBSS
Access Points are designed to be BSS Masters. It is possible to hack an access point to be IBSS compatible, but it is not without cost.
There is firmware available from vendors like KarlNet that turns an AppleAirport or RG1000 into an IBSS mode device, but it carries a hefty license fee.
You can run linux on an AppleAirport or RG1000, but it requires running a TFTP and NFS Server on another machine.
You can buy devices from cisco or other high end vendors that do iBSS.
Udpate: The Linksys WRT54G, and WAP54G's can be set into IBSS (ad-hoc) mode quite easily. OpenWrt (an opensource firmware strain for the Linksys kit) makes it even easier.
