Civesnet, the citizens' network
Author, (c): Guido Winkelmann, 2005
rev. 0.1

A decentralized, scalable, self-organising network

This is a proposal for a potential routing algorithm that can be used to build
a world-spanning network with arbitrarily complex topology and several millions
of nodes. The actual potential of this algorithm will have to be determined in
simulations yet.
Many of the ideas in this document were inspired by the work of the freenet
project, http://www.freenetproject.org
This is only a first draft, many details still need to be filled in.
This is not targeted primarily at mobile/wireless devices, although wireless
transmission may be used as a transport medium.

The goals are:
- New nodes can be introduced by simply hooking them up to one or more
other nodes which already are connected to the net.
- Other than the above, no further manual configuration should be needed
- Every node should, after a short period of assimilation, be able to send a
data packet to any other node on the network at any time, provided a physical
path actually exists.
- The routes taken by a data packet should be as near as possible to the actual
best route available.
- If several sensible routes are available, they should all be used in order to
maximise data throughput and to minimise the load on a specific route.
- A big network should not be very vulnerable to a small number of malicious
nodes. (A small network is always vulnerable)

Assumptions:

- Some packet loss is considered tolerable, but if possible, it should be
detected.
- Every connection between two nodes is bidirectional.
- The underlying tranport protocol can directly adress a neighbor node that
is on the same network segment.
- The underlying network protocol may or may not support broadcasting.
- The likeliness of a physical network connection existing between two nodes
is inversely proportional to their geographical distance. (Not the case on
the current Internet)

0. Overview

The general idea is to have network which is constantly rewriting itself as it
goes along, to reflect the structure of a small-world network. [TODO: This
doesn't really say much. Should be rewritten.]

A node's address consists of two parts, one of which is completely static and is
used for routing in the very near vicinity (up to than 2 or 3 hops away) of the
node, and one dynamic part (the routing key), which changes over time and is
used for routing over large distances.
There is no fixed border between any parts of the network.
The protocol tries to exploit the characteristics of small-world networks
(which usually form by themselves in larger emergent networks of any kind) by
moving the routing key of every node around so that routing keys of two nodes
which are very near to each other are generally a lot closer than those of two
distant nodes. The basic idea behind routing decisions in this kind of network
is to move each packet to the peer with the routing key closest to that of the
destination.

1. Node addresses

Each node has a static 128-bit node-id and a dynamic 128-bit (64-bit?) routing
key. A node's address consists of its id and its routing key. The id is
sufficient to identify a node, but in order to actually communicate with it,
the routing key is needed, too. To form a working address, the routing key
should be as close as possible to the actual current routing key of the target
node, but it doesn't necessarily need to be exactly the same.

The routing algorithm is aware of variable overflow for the routing key,
meaning a value of 1 is closer to $MAXVALUE-1 than to a value of 10, where
$MAXVALUE is the maximum value the routing key can take before overflowing.
(This basically makes the routing key space a circle.)

The id is, at the same time, a public key for a public-/private- key
cryptography scheme. This is not intended for end-to-end encryption (although it
might be used for this) but rather to help catch cheater nodes, that is, nodes
who claim to route the traffic they are handed but secretly just throw it away.
(This might become important in a network where peers pay each other to route
each others traffic.)
It might also be used to sign a routing key, so that it is possible to build a
P2P routing-key exchange network on top of this network using existing DHT
technologies to make it possible for nodes to search for a new routing key to a
given node id if the one they have is too old already.

2. Routing Key Drift

The routing key of a node needs to drift towards those of its neighbor-nodes
and away from those of distant nodes in order to make the routing work. (This
is what is meant by "The network constantly rewrites itself".) The speed of
this drift is proportional to the ratio between successfully routed traffic and
unsuccessfully routed traffic. (Meaning the better the routing already works,
the less a node will drift.)
Every node knows all the routing keys of all its direct neighbor nodes. Every
neighbor node's routing key causes a "force" attracting this node's key towards
it. This "force" is directly proportional to the distance between the routing
keys and the importance of the corresponding neighbor node. The importance of a
node is defined as the percentage of the successful traffic that has come
or gone through that node (which is calculated/stored as a decaying average).

This will cause heavy nodes (:= nodes which have a large number of connections
and handle a lot of traffic) to drift a lot slower than lighter nodes. Also, if
a heavy node starts drifting, it'll soon drag the lighter nodes in its vicinity
with it, while a drifting light node will not have much impact.
Large parts of the net will generally drift slower than smaller parts.

2.1 Collisions of networks

It can happen that two distant parts of the net will end up on overlapping
ranges of routing keys. In this case, both these parts will start receiving a
lot of packets intended for the other part which they will be unable to route
properly. Should this happen, these parts of the net should start drifting away
from each others routing key space. To achieve this, each packet a node sees
that could not be routed properly creates a repulsive force on the nodes routing
key which is inversely proportional to the number of successfully routed packets
and the distance between the routing key of the unsuccessful packet and the
nodes routing key.

As a consequence, a small part of the net that trespasses on the routing key
space of a larger part will not have much impact. A large part that drifts into
the routing key space of a smaller part, however, will push the smaller part in
the opposite direction.

[TODO: Exact calculation and execution of drift]

3. Routing Tables

Every node has two routing tables, one for nodes in the near vicinity which
contains every node that is reachable in 1 or 2 (or 3) hops, and one for
distant routing, which contains statistical data about which direct neighbor
node is the best choice for routing to a certain routing key space.

3.1 Local Routing Table, LRT

Every node keeps a local routing table in which it stores entries for every
single node that can be reached in up to 2 (or 3) hops.

When a node acquires a new physical link, it sends out a broadcast packet over
this link announcing its presence and asking for other nodes. (Whether the
receiving nodes should send back an answer can be controlled by a flag.) This
packet is routed at most 2 hops and contains the originating node's id and
current routing key and whether it has any other physical links apart from this
one.
Every router node which forwards this packets increases the "hops" number
of this packet by one and appends its own address to the packet, so that
receiving nodes will know exactly how to reach the source node. If the "hops"
value is anything besides 1, 2 or 3, or if the "hops" value exceeds the
packets "htl" (hops to live) value, the packet will not be forwarded.
Every node which receives this packet (including the routers) will add the
source node to their LRT. If the "answer_req" flag is set, it will also send
back a (unicast) packet to the source node containing the same the set of
general information about it.

After a node has sent this initial announcement packet, it'll send it again
once every 60 minutes, but with the "answer_req" flag unset.

If it turns out that less than 50 nodes are reachable in up to 2 hops, a node
may increase its horizon for local nodes to 3 hops.
The LRT will never grow beyond 1000 entries (That value may be configurable). If
a node receives a packet with node information that would exceed this limit, it
will either discard it or, if the least recently used entry in the table has
been used more than 30 minutes ago, purge the least recently used entry and take
in the new one instead.
A node will have to keep its LRT clean of outdated entries anyway, especially
if it is moving between networks. [TODO: more about purging here]

[TODO: Maybe the horizon for "local" nodes should be completely dynamic.]

3.2 Distant Routing Table, DRT

Here's where the fun starts. Every node has four curves for every directly
reachable neighbor node that it wants to/can use as a router. The routing table
for distant routing is calculated dynamically, on demand, from these curves.
These curves indicate, respectively, the routing probability, the routing price,
the average round-trip time and the estimated throughput capacity for every
possible routing key when going through that particular router. (Routing
probability is a value indicating how likely it is that this routing key can be
reached at all over this route.)

Obviously, it is not possible to store one entry for every possible routing key
out of a routing key space of 128 Bit (or even 64 Bit), not to mention that all
this information would be rather hard to get by and would be outdated rather
soon. To work around this, each of these curves is defined by only 50 stored
points which may be arbitrarily placed in the available 2-dimensional space of
that curve. The y-value to any given x-value (which corresponds to one routing
key) is defined as the point where a straight line between the nearest stored
point to the left of this x-value and the nearest stored point to the right of
this x-value intersects with this x-value. As the routing key space is treated
as a circle, there is always a stored point to the left and a stored point to
the right of any x-value.

The idea is that, this way, the available information about a part of the net
that is very near to this node or that this node communicates with very often
is very exact, while information on distant parts of the network is blurry in
comparison, but still sufficient to push the packet in roughly the correct
direction. This way, the nearer a packet gets to its destination, the better
the nodes handling it will be able to make routing decisions.

4. Routing

4.1 Local Routing

Every outgoing packet, forwarded or generated locally, is first put through
local routing. This is straight-forward: Look up the destination's id in the
LRT, if it is there, route the packet according to the routing information
found there, if not pass it to the distant routing procedure.

4.2 Distant Routing

When a packet can not be delivered using the LRT, the node will extract the
corresponding values for the destination's routing key from the four curves
associated with each local router connection, including the connection this
packet came from, if it is a forwarded packet. For every existing
connection, these values are weighed according to the node administrator's
preferences and then used to calculate the probability at which this packet
is routed in that direction. After this, a random value is applied to these
probabilities to determine where this packet is actually routed to.

The fact that this is just a probability means that, in rare cases, a packet
might be routed against the odds. This helps to find new routes that
otherwise would go unnoticed for a long time. This also means that if there
are two or more routes with a similarly high probability for routing of a
certain key space, packets with a destination address in that routing key
space will be evenly distributed over those connections.

A packet is (of course) never routed to the connection from which it came.
If this connection has the highest calculated routing probability off all
available connections, this hop is considered a "bad hop" (regardless of
where it is actually routed to). In this case, the "bad_hops" field is
increased by one. If this would cause the "bad_hops" field to go over a
value of 6, this packet is considered unroutable. (See 5.1 for more about
that.)

5. Backwards Routing, Loop Detection

Sometimes a packet or a notice about a packet has to be routed backwards 
along the exact route it came a packet from. To make this possible, each
node stores a reference struct or each packet it sends out. This struct
contains the packets source address, destination's id (not the entire
address), the "ttl" field (which is an unsigned 32 Bit Unix timestamp, set by
the source to five minutes in the future) and the packets "serial" field
(which is a 16 Bit value set by the source node that is required to be unique
for every combination of source id, destination id, the packets ttl [TODO:
This means that any node can send at most 65535 packets to any single
destination node per second. Maybe it should be 24 or 32 Bit?]), the id of the
router node it came from (where applicapable) and the id of the node it went
to. Each of these references needs to be stored until at least the packets ttl
value plus six minutes.

If a routing node finds the incoming ttl value of a packet to be more than 7
and a half minutes in the future, it resets it to five minutes in the future.
(This requires that every node have a roughly correctly set clock. It also
means that every packet must be delivered within six minutes.)

This packet reference table is also used to detect loopings.

To route back a notice, a node looks up the packet the notice is about in
its reference table and sends the notice to the neigbor node it got that
packet from. If an entry isn't found, the notice is discarded. After a
notice has been sent, the corresponding entry is deleted. (This is to make
network flooding with notice packets impractical.) Notice packets are to be
routed with raised priority.

(The presence of this table means that every router node will need a very
large amount of main memory for fast and often used connections. A way
to reduce this might be to increase the general MTU on the network. As most
underlying transport protocols don't usually support MTUs over 1500, this
would make packet splitting and reassembling necessary.)

A node may also decide to cache the entire packet instead, which might be
useful if it has been routed against the odds.

5.1 Unsuccessful Routing

In some cases a packet can not be properly routed to its destination. This
includes cases where a router simply doesn't find any more neighbor routers
it can hand the packet to, where a packet has exceeded its "ttl" or
"bad_hops" value, a router has detected a looping or where a certain
connection is saturated with traffic. In these cases, a not_routeable notice
is routed backwards along the original route, which includes all the
necessary information about the unrouteable packet and the reason for which
this packet couldn't be routed, which can be one of "ttl_exceeded",
"bad_hops_exceeded", "dead_end", "looping_detected", "connection_saturated",
"connection_problems", "node_problems" or "packet_too_large".

Nodes receiving (and forwarding) such a notice will use it to update their
curves for routing probability and, in the case of the reason given being
"connection_saturated", estimated throughput capacity for the node they got
this packet from. If the node receiving this notice has the packet in question
cached, it'll retry sending it, this time using a different route (and won't
route the notice packet).

Every packet sent is automatically considered to be routed successfully
until such a notice is received.

5.2 Successful Routing

When a data packet reaches its target, the target node has a 1% chance of
routing back a cryptographically signed success notice. This is used to catch
router nodes that simply discard traffic forwarded to them without routing
back an unsuccessful notice. If a node receives significantly less than 1
success notice from a neighbor node for every 100 hundred packets sent to
this node over a longer timeframe, then something's wrong there. (Sligtly
less than 1% should be normal - some packet loss is simply undetectable.)

A node receiving a success notice will not check the signature right away;
this only needs to be done if there is reason to suspect that someone is
faking them.

6. Pricing

[TODO]

7. Multicast

[TODO]

8. Anycast

[TODO]