Parent Management

Introduction

This document defines a parent management protocol used by Marlin nodes to maintain a set of parent nodes from whom they wish to receive chunks or chunk IDs.

For the couterpart protocol that manages children, see the child management protocol.

Concepts

Chunks

Messages are broken into erasure-coded chunks for faster and more reliable transmission. Each chunk has a chunk ID associated with it.

Tiers

Peers are categorized into tiers based on proximity:

  • Tier 0: <5 ms
  • Tier 1: <50 ms
  • Tier 2: 50-100 ms
  • Tier 3: 100-150 ms
  • Tier 4: 150+ ms

Tier 0 peers allow super fast fetching of any missing chunks. Tier 3 and 4 peers are required to create overlapping intercontinental topological graphs, limiting children to just 1 or 2 ensures different parents are chosen for redundancies. Tier 1 and 2 peers are more in number to ensure dense local distribution.

Active, passive and tracked peers

Each peer is further categorized as an active, passive or a tracked peer.

Active peers transmit entire chunks and are the hot path used for fast propagation through the Marlin network.

Passive peers transmit only the chunk IDs of the chunks they receive and act as a backup for fetching chunks on request in case the node is missing any chunks needed to reconstruct the message.

Tracked peers do not transmit anything, their metrics are simply tracked for the purposes of our reinforcement learning algorithm.

Peer optimization routines periodically adjust nodes in these sets to provide an optimal balance between performance, reliability and efficiency.

Constants

Name Type Value
INITIAL_SCORE double 0.3
ACTIVE_PEERCOUNT_SOFTTARGET mapping(Tier => uint8) {0: 1, 1: 3, 2: 3, 3: 1, 4: 1}
PASSIVE_PEERCOUNT_SOFTTARGET mapping(Tier => uint8) {0: 5, 1: 15, 2: 15, 3: 5, 4: 5}
TRACKED_PEERCOUNT_SOFTTARGET mapping(Tier => uint8) {0: 5, 1: 15, 2: 15, 3: 5, 4: 5}

Data structures

Type aliases

Name Type Description Example
Tier uint8 Tier number 0, 1, 2, ..., 4
LocationId bytes32 Location ID
PeerId bytes32 Peer ID
Score double Score value indicating fitness for being a parent

ParentPeer

struct ParentPeer {
    PeerId peerId
    Score score
}

Storage

activeParentPeers

mapping((TierId, LocationId) => ParentPeer[]) activeParentPeers

passiveParentPeers

mapping((TierId, LocationId) => ParentPeer[]) passiveParentPeers

trackedParentPeers

mapping((TierId, LocationId) => ParentPeer[]) trackedParentPeers

Operations

Joining the network

Nodes initiate the discovery protocol on joining the network to initiate discovery of new peers in the network. A few beacon nodes are supplied to the discovery mechanism to bootstrap the process. The node also sets a recurring timer that triggers peer optimization.

func findParents(bytes[] beaconAddr) {
    DiscoveryProtocol::startDiscovery(beaconAddr)
    helpers::startPeerOptimizationTimer()
}

Leaving the network

The node unsubscribes from all its parents before leaving the network.

func disconnectParents() {
    for tier in tiers {
        for location in locations {
            for peer in activeParentPeers[(tier, location)] {
                activeParentPeers[(tier, location)].remove(peer)
                PubSubProtocol::unsubscribe(peer)
            }
            for peer in passiveParentPeers[(tier, location)] {
                passiveParentPeers[(tier, location)].remove(peer)
                PubSubProtocol::unsubscribe(peer)
            }
        }
    }
}

New peer discovery

On discovering a new peer, the active list is checked to see if there are vacancies and if yes, a subscribe message is sent to the peer. If not, the passive list is checked to see if there are vacancies and if yes, a subscribe message is sent to the peer. If both lists are full, the peer is simply ignored. On a succesful subscription, the peer is added to the corresponding list.

func onNewPeer(Peer peer) {
    peerLocationId = LocationProtocol::getLocation(peer)
    selfLocationId = LocationProtocol::getLocation(self)
    tier = helpers::getTier(selfLocationId, peerLocationId)

    for locationId in LocationProtocol::allLocations() {
        if activeParentPeers[(tier, locationId)].size() < ACTIVE_PEERCOUNT_SOFTTARGET[tier] {
            PubSubProtocol::subscribe(peer, locationId, CHUNKS)
        } else if passiveParentPeers[(tier, locationId)].size() < PASSIVE_PEERCOUNT_SOFTTARGET[tier] {
            PubSubProtocol::subscribe(peer, locationId, CHUNK_IDS)
        }
    }
}

func onSubscribeSuccess(Peer peer, LocationId locationId, SubscriptionType subscriptionType) {
    if subscriptionType == CHUNKS {
        activeParentPeers[(tier, locationId)].insert(peer, INITIAL_SCORE)
    } else if subscriptionType == CHUNK_IDS {
        passiveParentPeers[(tier, locationId)].insert(peer, INITIAL_SCORE)
    }
}

func onSubscribeFailure(Peer peer, LocationId locationId, SubscriptionType subscriptionType) {
    // Nothing
}

Peer close

When a peer closes the connection, it is removed from all the active and passive sets.

func onClose(Peer peer) {
    for tier in tiers {
        for location in locations {
            activeParentPeers[(tier, location)].remove(peer)
            passiveParentPeers[(tier, location)].remove(peer)
        }
    }
}

New chunk

On receiving a new chunk the peer's score is updated based on a scoring function.

func onNewChunk() {
    updatePeerRanking(
        from,
        contentCache[contentType+contentId].size() +
            idCache[contentType+contentId].size(),
        MIN_CHUNKS[contentType+contentId]
    );
}

Invalid chunk

On receiving an invalid chunk, the peer is removed from the active set and a passive peer is promoted to active status.

func onInvalidChunk(Peer peer) {
    peerLocationId = LocationProtocol::getLocation(peer)

    activeParentPeers[(tier, peerLocationId)].remove(peer);

    bestPassivePeer, passiveMetric = passiveParentPeers[(tier, location)].getBestPeer()

    activeParentPeers[(tier, peerLocationId)].insert(bestPassivePeer, passiveMetric);
    passiveParentPeers[(tier, peerLocationId)].remove(bestPassivePeer);
}

New chunk ID

On receiving a new chunk the peer's score is updated based on a reinforcement learning algorithm.

func onNewChunkId() {
    updatePeerRanking(
        from,
        contentCache[contentType+contentId].size() +
            idCache[contentType+contentId].size(),
        MIN_CHUNKS[contentType+contentId]
    );
}

Invalid chunk ID

On receiving an invalid chunk ID, the peer is removed from the passive set and a tracked peer is promoted to passive status.

func onInvalidChunkId(Peer peer) {
    peerLocationId = LocationProtocol::getLocation(peer)

    passiveParentPeers[(tier, peerLocationId)].remove(peer);

    bestTrackedPeer, trackedMetric = trackedParentPeers[(tier, location)].getBestPeer()

    passiveParentPeers[(tier, peerLocationId)].insert(bestTrackedPeer, trackedMetric);
    trackedParentPeers[(tier, peerLocationId)].remove(bestTrackedPeer);
}

Optimizing active peers

On a timer event, the node optimizes its active peers by exchanging a peer in the active and passive lists if the passive list has a significantly better peer.

func onTimerEvent() {
    for tier in tiers {
        for location in locations {
            bestPassivePeer, passiveMetric = passiveParentPeers[(tier, location)].getBestPeer()
            worstActivePeer, activeMetric = activeParentPeers[(tier, location)].getWorstPeer()
            if passiveMetric * 0.9 > activeMetric {  // Damping factor to prevent excessive swaps
                passiveParentPeers[(tier, location)].remove(bestPassivePeer)
                activeParentPeers[(tier, location)].remove(worstActivePeer)
                passiveParentPeers[(tier, location)].add(worstActivePeer)
                activeParentPeers[(tier, location)].add(bestPassivePeer)

                unsubscribe(worstActivePeer)
                subscribe(bestPassivePeer)
            }
        }
    }
}

Optimizing passive peers

On a timer event, the node optimizes its passive peers by exchanging a peer in the passive and tracked lists based on a reinforcement learning algorithm.