Mesh routing

Proposed model for routing

Serval primarily communicates over Ad Hoc Wi-Fi by sending broadcast packets. Each packet must identify the source device and contain a sequence number.

Each node should use the receipt of packets to track the quality of the link. This information should be periodically transmitted in the form “node A has a link to node B of cost C”. Link costs should be versioned to allow recipients to keep the most recent record. The protocol should allow for multiple different cost metrics to be collected and distributed.

Peer selection

To fight buffer bloat on the outgoing network interface, each node should only send WINDOW_SIZE packets at a time. Some number of local neighbours should periodically ACK packets to confirm successful delivery. Since we are mainly using broadcast packets, the network layer does not provide any delivery guarantees. In the event of packet collision or interference, the packet will not arrive. Each node should remember the content of the last WINDOW_SIZE packets they have sent. On receiving a NACK, the payloads should be requeued and transmitted in another frame. We don't want every neighbour to send a NACK packet when a collision is detected. Instead some smaller number of peers should be selected to send NACK's immediately when they notice a packet was missed.

Efficient flooding

By collecting link cost packets we can build a picture of our entire 2-hop neighbourhood. Similar to olsr's MPR selection process, we should determine which neighbours MUST repeat our broadcast messages so that all 2-hop neighbours hear the message. Other neighbours should not repeat these messages to ensure we don't overload the network layer unnecessarily.

Medium scale routing

Each node will broadcast the entire set of link records that they are actively using to build their routing table. These records will be the same as the link cost records above. By recording these link records from your neighbours you can choose which of your neighbours has the best path to each node on the network. By only re-transmitting information about links that you are using, information about useless links in the network will be hidden. When a link in the network dies, and you no longer have a viable path to a node. An unreachable record should be created and published. These unreachable records will need to spread to all nodes that are currently using this link in their routing table. Only then can a node with an alternative path begin to spread this information.

Internet gateways

Serval network addresses do not map directly to either IPv4 or IPv6 equivalents. Even though network hosts are identified by their full 256bit ECC key, I believe that we should adopt a network prefix scheme compatible with IPv6. Any device with an internet connection should advertise an IPv6 prefix. Any gateway with only a public IPv4 address might announce an 2002:X:X::/48 prefix. Every device within N hops should claim an address in these subnets. Source and Destination addresses in network payloads should include the network prefix. Any packet destined for an internet address, should be routed to the appropriate gateway based on the source subnet that the packet was sent from.

Huge scale routing

While link tracking is essential for the local mesh topology, tracking links to each node individually will only scale so far. Eventually you would consume all available bandwidth talking about link changes. Beyond a certain scale, it must be possible to aggregate routes together. While serval is using ECC keys as host identifiers, we need to introduce a network prefix based on physical or topological location. http://tools.ietf.org/html/draft-hain-ipv6-geo-addr-01 outlines a scheme of deriving a network prefix based on Lat/Long coordinates. But not every device will know their own location. Similar to the way that routes to IPv6 internet gateways are announced, a small set of nodes with a known location should announce their geo-address. Nearby devices can then claim this network prefix as their own, and use these prefixes to route packets. These announcements would also serve to provide a coarse location service.


Login