RoutingTable
The Kademlia k-bucket routing table. This is the pure-Kotlin port of libtorrent's routing_table (include/libtorrent/kademlia/routing_table.hpp, src/kademlia/routing_table.cpp).
The table is a list of buckets, each holding up to k (bucketSize) live nodes plus a small replacement cache. Bucket 0 is the one furthest from our own id; every time the bucket closest to us fills up it is split in two, doubling the resolution of the part of the keyspace nearest to us. This is the standard Kademlia structure that lets a lookup converge on any target in O(log n) hops.
What this port covers (the faithful core):
addNode and addNodeImpl: the full insert and replace state machine, including the "same IP, new ID" eviction, replacement-cache promotion, and the bucket-split decision (canSplit).
nodeSeen and heardAbout: the two public entry points, for a pinged node and for a node we have only been told about.
findNode: gather the
countnodes closest to a target id by XOR distance.splitBucket, fillFromReplacements and nodeFailed: bucket maintenance.
classifyPrefix, allInSameBucket, mostlyVerifiedNodes and replaceNodeImpl: the free functions the table is built on.
Deliberate omissions / simplifications (each noted at its call site):
Endpoints are
host: String+port: Int(no socket types incommonMain), matching NodeEntry. IP identity for de-duplication and the BEP 42verifiedflag come from NodeEntry.addr (PeerAddress).restrict_routing_ipsis honoured via compareIpCidr and IpSet, but a node whose host is not a parseable IP literal (soaddr == null) is treated as having no IP identity. It never collides in IpSet and is never rejected by the CIDR-closeness check. Real libtorrent always has a numeric address here.RTT-based refresh scheduling (
next_refresh) and the logging/dht_loggerplumbing are not ported; they don't affect the routing structure that findNode returns.Time-based fields (
last_queried,first_seen) are not modelled. The one place upstream useslast_queriedto influence structure is the malicious-node "schedule a re-ping" loop, which we collapse to a fail-count reset (see addNodeImpl).
Settings come from RoutingTableSettings, which mirrors the five DHT settings_pack booleans/int the routing table reads, with libtorrent's exact defaults.
Parameters
our own node id (m_id).
the constant k from the Kademlia paper (m_bucket_size); must be a power of two.
the DHT routing knobs (see RoutingTableSettings).
Types
Properties
our own node id (m_id). Read-only from outside; mutated by updateNodeId.
Functions
The core insert state machine. Port of routing_table::add_node_status_t routing_table::add_node_impl(node_entry e). Returns one of AddNodeStatus; addNode drives the splitting loop on AddNodeStatus.NEED_BUCKET_SPLIT.
Register a router node by endpoint (add_router_node).
The per-bucket size limit. Port of int routing_table::bucket_limit(int). With the extended routing table (the default), the first four buckets are larger (k*{16,8,4,2}) so the table gets closer to us in fewer hops.
Number of live nodes in bucket bucket (bucket_size(int)).
The number of bits down we have full buckets. Port of int depth(). This uses (and updates) depthCache exactly like the upstream mutable m_depth.
Invoke f for every live node, then (optionally) every replacement node.
We heard about a node (e.g. in another node's find_node response) but have not confirmed it ourselves. Port of void heard_about(...): the entry is created un-pinged, and if its bucket is full it is simply ignored.
true if the table has no live nodes at all. This is a KiteTorrent convenience (libtorrent has no single need_bootstrap() function; the DHT node decides to bootstrap based on routing_table::size() and the return value of nodeSeen). A freshly-constructed table that has never seen a node is empty and therefore needs bootstrapping.
Record that a request to a node timed out. Port of void routing_table::node_failed(node_id const&, udp::endpoint const&). After enough failures (or for a never-pinged node) the entry is removed and the bucket back-filled from its replacement cache.
We saw a verified sign of life from a node (a response with a matching transaction id). Port of bool routing_table::node_seen(...): the node is created as pinged and added; the return value is true if the table wants a refresh (i.e. a findNode on our own id should be issued). The node is only considered if it passes verifyNodeAddress.
The number of active buckets (num_active_buckets).
The set of router endpoints, each as "host:port" (begin()/end()).
Change our node id and rebuild the whole table around it. Port of void routing_table::update_node_id(node_id const& id).