kbucket

package module
v0.5.0 Latest Latest
Warning

This package is not in the latest version of its module.

 Go to latest Published: Feb 8, 2023 License: MIT Imports: 20 Imported by: 5

README

go-libp2p-kbucket

Fork of libp2p/go-libp2p-kbucket by DAOT Labs.

Go Reference

A kbucket implementation for use as a routing table in go-libp2p-kad-dht

Documentation

API docs: Go Reference

Contribute

Feel free to join in. All welcome. Open an issue!

Want to hack on libp2p?

License

MIT

Copyright for the modified portions of this fork are held by [DAOT Labs, 2020]. All other portions of this fork are held by [Protocol Labs, 2016] as part of the original go-libp2p-kbucket project. All right reserved.

Documentation

Overview

package kbucket implements a kademlia 'k-bucket' routing table.

Index

Constants

View Source 
const (
	AvgRoundTripsPerStepWithNewPeer_TCP_TLS = 4.0
	AvgRoundTripsPerStepWithNewPeer_QUIC    = 2.0
)

Variables

View Source 
var ErrLookupFailure = errors.New("failed to find any peer in table")

ErrLookupFailure is returned if a routing table query returns no results. This is NOT expected behaviour

View Source 
var ErrPeerRejectedHighLatency = errors.New("peer rejected; latency too high")
View Source 
var ErrPeerRejectedNoCapacity = errors.New("peer rejected; insufficient capacity")

Functions

func Closer 

func Closer(a, b peer.ID, key string) bool

Closer returns true if a is closer to key than b is

func CommonPrefixLen 

func CommonPrefixLen(a, b ID) int

func EstimatedAvgBitsImprovedPerStepFromBucketSize 

func EstimatedAvgBitsImprovedPerStepFromBucketSize(bucketSize int) float64

EstimatedAvgBitsImprovedPerStepFromBucketSize calculates the estimated average number of bits improved per lookup step. Reference: D. Stutzbach and R. Rejaie, "Improving Lookup Performance Over a Widely-Deployed DHT," Proceedings IEEE INFOCOM 2006. For the basic Kademlia approach D(1,1,k), m(1,k) approaches log(2,k)+0.3327, the number of bits improved on average is 1+m(1,k)=1.3327+log(2,k)

func SortClosestPeers 

func SortClosestPeers(
	peers []peer.ID,
	target ID,
	considerLatency bool,
	metrics peerstore.Metrics,
	dialer network.Dialer,
	local ID,
	avgBitsImprovedPerStep float64,
	avgRoundTripsPerStepWithNewPeer float64,
	avgPeerRTTMicroSecs int64,
) ([]peer.ID, error)

Sort the given peers with SortClosestPeersByDistanceAndLatency if consideraLatency is true, otherwise sort them with SortClosestPeersByDistance.

func SortClosestPeersByDistance 

func SortClosestPeersByDistance(peers []peer.ID, target ID) []peer.ID

Sort the given peers by their ascending distance from the target. A new slice is returned.

func SortClosestPeersByDistanceAndLatency 

func SortClosestPeersByDistanceAndLatency(
	peers []peer.ID,
	target ID,
	metrics peerstore.Metrics,
	dialer network.Dialer,
	local ID,
	avgBitsImprovedPerStep float64,
	avgRoundTripsPerStepWithNewPeer float64,
	avgPeerRTTMicroSecs int64,
) ([]peer.ID, error)

Sort the given peers by their ascending closeness by taking into account both the distance to the target and the latency (measured by RTT) to the local peer. Fallback to SortClosestPeers if `metrics` is nil. A new slice is returned.

Types

type ID 

type ID []byte

ID for IpfsDHT is in the XORKeySpace

The type dht.ID signifies that its contents have been hashed from either a peer.ID or a util.Key. This unifies the keyspace

func ConvertKey 

func ConvertKey(id string) ID

ConvertKey creates a DHT ID by hashing a local key (String)

func ConvertPeerID 

func ConvertPeerID(id peer.ID) ID

ConvertPeerID creates a DHT ID by hashing a Peer ID (Multihash)

type PeerInfo 

type PeerInfo struct {
	Id peer.ID

	// LastUsefulAt is the time instant at which the peer was last "useful" to us.
	// Please see the DHT docs for the definition of usefulness.
	LastUsefulAt time.Time

	// LastSuccessfulOutboundQueryAt is the time instant at which we last got a
	// successful query response from the peer.
	LastSuccessfulOutboundQueryAt time.Time

	// AddedAt is the time this peer was added to the routing table.
	AddedAt time.Time
	// contains filtered or unexported fields
}

PeerInfo holds all related information for a peer in the K-Bucket.

type RoutingTable 

type RoutingTable struct {

	// notification functions
	PeerRemoved func(peer.ID)
	PeerAdded   func(peer.ID)
	// contains filtered or unexported fields
}

RoutingTable defines the routing table.

func NewRoutingTable 

func NewRoutingTable(bucketsize int, localID ID, latency time.Duration, m peerstore.Metrics,
	dialer network.Dialer, usefulnessGracePeriod time.Duration, df *peerdiversity.Filter,
	considerLatency bool, avgBitsImprovedPerStep float64, avgRoundTripsPerStepWithNewPeer float64,
) (*RoutingTable, error)

NewRoutingTable creates a new routing table with a given bucketsize, local ID, and latency tolerance.

func (*RoutingTable) AvgPeerRTTMicroSecs 

func (rt *RoutingTable) AvgPeerRTTMicroSecs() int64

AvgPeerRTTMicroSecs computes average RTT of peers in the RoutingTable to the local peer in microseconds.

func (*RoutingTable) Close 

func (rt *RoutingTable) Close() error

Close shuts down the Routing Table & all associated processes. It is safe to call this multiple times.

func (*RoutingTable) Find 

func (rt *RoutingTable) Find(id peer.ID) peer.ID

Find a specific peer by ID or return nil

func (*RoutingTable) GenRandPeerID 

func (rt *RoutingTable) GenRandPeerID(targetCpl uint) (peer.ID, error)

GenRandPeerID generates a random peerID for a given Cpl

func (*RoutingTable) GetDiversityStats 

func (rt *RoutingTable) GetDiversityStats() []peerdiversity.CplDiversityStats

GetDiversityStats returns the diversity stats for the Routing Table if a diversity Filter is configured.

func (*RoutingTable) GetPeerInfos 

func (rt *RoutingTable) GetPeerInfos() []PeerInfo

GetPeerInfos returns the peer information that we've stored in the buckets

func (*RoutingTable) GetTrackedCplsForRefresh 

func (rt *RoutingTable) GetTrackedCplsForRefresh() []time.Time

GetTrackedCplsForRefresh returns the Cpl's we are tracking for refresh. Caller is free to modify the returned slice as it is a defensive copy.

func (*RoutingTable) ListPeers 

func (rt *RoutingTable) ListPeers() []peer.ID

ListPeers takes a RoutingTable and returns a list of all peers from all buckets in the table.

func (*RoutingTable) MarkAllPeersIrreplaceable 

func (rt *RoutingTable) MarkAllPeersIrreplaceable()

MarkAllPeersIrreplaceable marks all peers in the routing table as irreplaceable This means that we will never replace an existing peer in the table to make space for a new peer. However, they can still be removed by calling the `RemovePeer` API.

func (*RoutingTable) NPeersForCpl 

func (rt *RoutingTable) NPeersForCpl(cpl uint) int

NPeersForCPL returns the number of peers we have for a given Cpl

func (*RoutingTable) NearestPeer 

func (rt *RoutingTable) NearestPeer(id ID) peer.ID

NearestPeer returns a single peer that is nearest to the given ID

func (*RoutingTable) NearestPeers 

func (rt *RoutingTable) NearestPeers(id ID, count int) []peer.ID

NearestPeers returns a list of the 'count' closest peers to the given ID.

#DAOT If rt.considerLatency is enabled, this will take into account not only the xor distance to the target, but also the latency to the local peer (measured in RTT).

For algorithm details, see section 3.7.3 of the paper "Design and Implementation of Low-latency P2P Network for Graph-Based Distributed Ledger" by Wang Xiang. "面向图式账本的低延迟P2P 网络的设计与实现" by 向往

func (*RoutingTable) Print 

func (rt *RoutingTable) Print()

Print prints a descriptive statement about the provided RoutingTable

func (*RoutingTable) RemovePeer 

func (rt *RoutingTable) RemovePeer(p peer.ID)

RemovePeer should be called when the caller is sure that a peer is not useful for queries. For eg: the peer could have stopped supporting the DHT protocol. It evicts the peer from the Routing Table.

func (*RoutingTable) ResetCplRefreshedAtForID 

func (rt *RoutingTable) ResetCplRefreshedAtForID(id ID, newTime time.Time)

ResetCplRefreshedAtForID resets the refresh time for the Cpl of the given ID.

func (*RoutingTable) Size 

func (rt *RoutingTable) Size() int

Size returns the total number of peers in the routing table

func (*RoutingTable) SortClosestPeers 

func (rt *RoutingTable) SortClosestPeers(peers []peer.ID, target ID) ([]peer.ID, error)

SortClosestPeers just calls kbucket.SortClosestPeers() with the options of the RoutingTable.

func (*RoutingTable) TryAddPeer 

func (rt *RoutingTable) TryAddPeer(p peer.ID, queryPeer bool, isReplaceable bool) (bool, error)

It returns a boolean value set to true if the peer was newly added to the Routing Table, false otherwise. It also returns any error that occurred while adding the peer to the Routing Table. If the error is not nil, the boolean value will ALWAYS be false i.e. the peer wont be added to the Routing Table it it's not already there.

A return value of false with error=nil indicates that the peer ALREADY exists in the Routing Table.

func (*RoutingTable) UpdateLastSuccessfulOutboundQueryAt 

func (rt *RoutingTable) UpdateLastSuccessfulOutboundQueryAt(p peer.ID, t time.Time) bool

UpdateLastSuccessfulOutboundQuery updates the LastSuccessfulOutboundQueryAt time of the peer. Returns true if the update was successful, false otherwise.

func (*RoutingTable) UpdateLastUsefulAt 

func (rt *RoutingTable) UpdateLastUsefulAt(p peer.ID, t time.Time) bool

UpdateLastUsefulAt updates the LastUsefulAt time of the peer. Returns true if the update was successful, false otherwise.

Source Files

View all Source files

Directories

Path Synopsis

Jump to

Keyboard shortcuts

? : This menu
/ : Search site
f or F : Jump to
y or Y : Canonical URL
go.dev uses cookies from Google to deliver and enhance the quality of its services and to analyze traffic. Learn more.