Updates as of October 2001
* Check out WIRP: [link] http://www.maokhian.com/wireless/
* More defined information as to what has been done so far
* Double destination/double gateway solution
* Political and trust issues with a meshed network (anyone can change the routing table)
Project Goal:
Create a routing protocol that can discover network nodes, create a dynamically updatable network topology map, exchange route information on changes, and manage load balancing, diverse routes, and frequency coordination. It should also discover backbones, and send the smallest routing updates possible. It should allow routing of roaming users. This routing protocol also should allow the network to be split into multiple networks (NetSplit) and allow merging of two or more seperate networks into one (NetMerge). The routing protocol should not require any configuration on the user part, other then assignment of a unique ID number.
Project Goal in Hacker Terms:
Allow a bunch of cars driving on a freeway, each with a 802.11 radio. The protocol should discover all these vehicles, including the ones turning on and off the freeway, route data between all the nodes, and converge within seconds. If redundant links exist; load balance. If multiple P2P links are on the frequency, detect and coordinate band plans. If CaseyHalverson is rollerblading or driving with his palm pilot, his IRC session needs to work seamlessly. This network should require little to no configuration on the user's part, and each node requires a unique ID -- either assigned or derived from a serial number or MAC address unique to that computer.
Project Progress:
The protocol has been fully developed and has entered the testing phase. A software "suite" which allows virtual simulation of a network has been developed. Anyone who is interested in this piece of software can contact me at commando@wolfenet.com.
Implementation of the WirelessInterRoutingProtocol has begun virtually. The routing update and network merging structures are currently being implimented. This allows the network to pass routing information dynamically and efficiently, taking in consideration that nodes will be added and removed at random. Routing loops are nearly impossible during network convergence, since they are corrected within milliseconds. Entire network convergence can take place in less then a second or two, depending on network size (-- at least in theory)
Once the foundation has been fully tested and completed, other higher level functions such as backbone discovery, load balancing, channel selection, diverse routes, etc. will be then implimented.
After the routing protocol has been fully tested virtually, implimentation will then be made in the real world. Hopefully someone with Unix C skills can assist in development. Otherwise, everyone will have to deal with a crappy rexx hack.
What it does so far:
Each node scans all of its channels for a "HELLO" packet which each node sends when first enters the world. Every n seconds (not yet defined) the node originates a "HELLO" packet. Once a "HELLO" packet is intercepted, the node responds with a "HELLO_ACK" packet which contains various information pieces about the node. One critical piece is weather the node whichs to operate as a mobile unit (not part of the routing mesh) or a fixed unit (part of the routing mesh). This avoids sending routing tables to nodes who will use every other node as a default route. If this is a mobile unit, the unit's route is advertised and is handled by the mobile routing portion of WIRP. If this unit requests to be part of the fixed infrastructure, it begins negociation. This involves exchanging each unit's unique identification number, and further results in configuration of the serial link IP addresses. Routing tables are exchanged, and the node is then converged into the network. All route tables use a very smart update routine. Once a full routing table is exchanged, routes are then updated in a consolidated packet containing routes to be added, removed, changed, or flagged (reliability ratings, gateway availability, etc). This packet is only sent when an change takes place, in order to reduce bandwidth usage. All routes are summarized. In order to reduce packet size, all routes a node owns are locally associated with a node number. That way, node numbers just need to be included instead of sending all of the routes associated with that node. If a node does not know what routes a node owns, the master node will provide this information. If a route update is received on two interfaces at once, a packet can be sent to block that routing update origination from the slowest node. If a failure in the mesh results in a route update being lost, the blocked node will originate route updates until a shorter route update path is discovered.
The next step is to handle double destination routing. This is a "double gateway" senerio where multiple internet gateways exist. Providing a choice to the client will increase relibility, speed, and permit load-balancing among the scarce resources available when collective sharing of cable and DSL modems occurs. Although the specifics have not yet been designed, the packet's destination address consists of the NAT gateway it wishes to use. The NAT server then disects the packet for the destination external network address (say, an ip address for the yahoo website) -- possibly stored in the ip options header, and forwards that packet (and session) to the internet. Placing two destination IP addresses in the packet will be called double destination routing or a double gateway until a better word is devised.
(Wheel-already-invented notice: Encapsulation is a good way to do the sort of onion-skin routing you're talking about, where the gateway peels off a layer and forwards the rest. Another approach to multiple-hop source routing is the Type-Length-Value header format used by Metricom and others, which allows different types of addresses (IP, MAC, Gateway name, etc) to be mixed in the path. Add a pointer to indicate the current field in the TLV string, and you don't need to strip off any bits, just change the pointer. This allows each node in the route to know the full route, and remember it if need be. Onion-skin encapsulation is more suited to networks where each gateway might not speak the same protocols as the others, whereas TLVs only work when the header will be understood by all nodes in the routing mesh.)
Current Problems:
The two major problems with this protocol (and one new political issue at the bottom) are:
First, the protocol needs a node to "kick" the rest of the network, this allows the network to converge in a very efficient manner, which should take a matter of seconds -- depending on network size. This can probably be done by some sort of lottery, but without this "kick", it would greatly increase the network merge time. Multiple "kicks" can be done, which would result into multiple networks merging once they reach each other's borders, exact provisions have not yet been decided on. NEW: One suggestion is to send out a multicast and udp broadcast as a heart beat on bootup, and every X seconds. This sounds like a good idea. (Bootstrap aggressively for a few moments after waking up, then ease off?)
Second, I would like suggestions on how to obtain the unique number of each node (mcmahon_kevin@hotmail.com: simple comment - you may want to identify each node by a matched pair of identities such that the network can know the specifics of the physical node and the node provider, each allowed to have long-lived relationships such as quality of service, availability, range, etc...which will have dependancies on both aspects - the physical node as it relates to the provider of the node). Should this be assigned by the SeattleWireless group, be derived from the first interface in the computer (Ethernet MAC), or something else? One suggestion is to use names instead of numbers, this is another good idea. I will be using numbers for the simulation, but I will just allow it to be any sort of text string with a certain character limit.
Third, a political issue, authentication issues. Any node can be part of the routing mesh and infrastructure. This means that, if someone really wanted to cause trouble, they could introduce bad routing information. Do we want nodes to authenticate onto the network? Do we want to fully trust those who are part of SW? Should a probationary period be placed on a node that is not known? Should a database consist of nodes we can fully trust, and those who we'd rather not have full control of the routing table but restricted to certain routes? By creating a central server, we will sacrifice the freedom and non-centralized service aspects of this network.
This would probably work, but I don't know if it's the best way. Sign the routing data and include the certificate ID with it (the full certificate should be available upon request). Allow each nodes to categorize certificates into some system of trust categories. By default, when routing information arrives with an unknown key id, the certificate is automatically requested and stuck into some default category -- probaby either neutral or untrusted.
