Documentation: Decentralized Routing

Decentralized routing
=====================

Main idea: Each peer holds a local routing table, a matrix with probabilities that each friend
is a correct path for a given key ID.

The routing tables are updated as messages go back and forth. Successful
interactions feed the routing table with information of where to route the
packets.

The routing is kept probabilistic, meaning that the optimal route is not
always chosen, but the randomness helps updating the routing probabilities.

Services that might use the router (All services really...)
    - Messenger
       - sends/receives messages to distant peers
    - Channels, forums, posted, etc.
       - send messages to the origin of the channel/forum/posted

Decentralized routing algorithm:
   - message passing
      - upward:
         * Forward msg to friends according to probabilities.
         * If all equal, send to all friends (or a rando subset of them).
         * keep the local routing info in a cache that is saved (Which peer issued the msg)
            - which probability was used to chose this friend (will be useful
              to compute the routing contribution if the msg is ACK-ed)

Two probabilities are computed:
    - routing probabilities among connected friends
        * this is computed by the routing matrix
    - branching factor N
        * depends on the depth of the items. Currently branching is 3 at origin and 1 elsewhere.
        * depends on the distribution of probabilities (min and max)

Once computed,
    - the item is forwarded randomly to N peers drawn from the list of connected peers with the given probabilities.
    - the depth of the item is incremented randomly

• downward: look into routing cache. If info not present, drop the item. Forward item into stored direction.

• routing probability computation: count number of times a reliable info is obtained from which direction for which identity

  • the count is a floating point number, since weights can be assigned to each info (especially for importance sampling)

  • init: all friends have equal count of 0 (or 1, well, we’ll have to make this right).

  • We use importance sampling, meaning that when peer relays a msg from ID: count[ID, peer] += 1.0 / importance

    1. where importance was the probability of chosing peer for the route upward.

  • probability of forward is proportional to count.

• routing cache

  • this cache stores messages IDs (like turtle router) but is saved on disk

  • it is used to remember where to send back responses to messages, and with what probability the route was chosen.

  • cache items have a TTL and the cache is cleaned regularly.

• routing matrix

  • the structure is fed by other services, when they receive key IDs.

  • stores for each identity the count of how many times each peer gave reliable info for that ID. That information should be enough to route packets in the correct direction.

  • saved to disk.

  • all contributions should have a time stamp. Regularly, the oldest contributions are removed.

• Routed packets: we use a common packet type for all services:

  We need two abstract item types:

  • Data packet

• packet unique ID (sha1, or uint64_t)

• destination ID (for Dn packets, the destination is the source!)

• packet type: Id request, Message, etc.

• packet service ID (Can be messenging, channels, etc).

• packet data (void* + size_t)

• flags (such as ACK or response required, and packet direction)

• routed directions and probabilities

  • ACK packet.

• packet unique ID (the id of the corresponding data)

• flags (reason for ACK. Could be data delivered, or error, too far, etc)

• Data storage packets

  • We need storage packets for the matrix states.

  • General routing options info?

• Main difficulties:

  • have a good re-try strategy if a msg does not arrive.

  • handle peer availability. In forward mode: easy. In backward mode: difficult. We should wait, and send back the packet if possible.

  • robustness

  • security: avoid flooding, and message alteration.

    Data pipeline
    =============

    sendData()
      |
      +--> encrypt/sign ---> store in _pending_messages

    receiveTurtleData()
                |
                +-------------------------------------------------+
    tick()                                                        |
      |                                                           |
      +--> HandleLowLevelServiceItems()                           |
      |         |                                                 |
      |         +--> handleLowLevelServiceItem(item) <------------+
      |                     |
      |                     +--> handleIncomingTransactionAckItem()
      |                     |
      |                     +--> handleIncomingTransactionChunkItem()
      |                                |
      |                                +---> addDataChunk()
      |                                |
      |                                +---> push item to _incoming_items list
      |
      +--> handleIncoming()
      |            |
      |            +---> handleIncomingReceiptItem(GRouterSignedReceiptItem*)
      |            |                                                 |
      |            +---> handleIncomingDataItem(GRouterDataItem*)    |
      |                                 |                            |
      |                                 +----------------------------+
      |                                 |
      |                                 |
      |                             [for US?] ----<Y>----------------+-----> verifySignedData()
      |                                 |                            |
      |                                <N>                           +-----> notifyClient()
      |                                 |                            |
      |                                 |                            +-----> send Receipt item ---+
      |                                 |                                                         |
      |                                 +----> Store In _pending_messages                         |
      |                                                                                           |
      +--> routePendingObjects()                                                                  |
      |         |                                                                                 |
      |         +--> locked_collectAvailablePeers()/locked_collectAvailableTunnels()              |
      |         |                                                                                 |
      |         +--> sliceDataItem()                                                              |
      |         |                                                                                 |
      |         +--> locked_sendTransactionData() <-----------------------------------------------+
      |                         |
      |                         +--> mTurtle->sendTurtleData(virtual_pid,turtle_item)  /  sendItem()
      |
      +--> handleTunnels()
      |         |
      |         +---> mTurtle->stopMonitoringTunnels(hash) ;
      |         +---> mTurtle->monitoringTunnels(hash) ;
      |
      +--> autoWash()