routing

Documentation

Overview

Package routing implements Kademlia hash tables with XOR distance metrics.

Index

• Constants
• func GetBucketIndexFromDifferingBit(id1, id2 []byte) int
• type HashTable
  • func NewHashTable(id id.ID, address *host.Address) (*HashTable, error)
  • func (ht *HashTable) DoesHostExistInBucket(bucket int, host []byte) bool
  • func (ht *HashTable) GetAllHostsInBucketCloserThan(bucket int, id []byte) [][]byte
  • func (ht *HashTable) GetClosestContacts(num int, target []byte, ignoredHosts []*host.Host) *RouteSet
  • func (ht *HashTable) GetRandomIDFromBucket(bucket int) []byte
  • func (ht *HashTable) GetRefreshTimeForBucket(bucket int) time.Time
  • func (ht *HashTable) GetTotalHostsInBucket(bucket int) int
  • func (ht *HashTable) Lock()
  • func (ht *HashTable) MarkHostAsSeen(host []byte)
  • func (ht *HashTable) ResetRefreshTimeForBucket(bucket int)
  • func (ht *HashTable) TotalHosts() int
  • func (ht *HashTable) Unlock()
• type IterateType
• type RouteHost
  • func NewRouteHost(host *host.Host) *RouteHost
  • func RouteHostsFrom(hosts []*host.Host) []*RouteHost
• type RouteSet
  • func NewRouteSet() *RouteSet
  • func (rs *RouteSet) Append(host *RouteHost)
  • func (rs *RouteSet) AppendMany(hosts []*RouteHost)
  • func (rs *RouteSet) Contains(host *RouteHost) bool
  • func (rs *RouteSet) FirstHost() *host.Host
  • func (rs *RouteSet) Hosts() []*host.Host
  • func (rs *RouteSet) Len() int
  • func (rs *RouteSet) Less(i, j int) bool
  • func (rs *RouteSet) Remove(host *RouteHost)
  • func (rs *RouteSet) RemoveMany(hosts []*RouteHost)
  • func (rs *RouteSet) Swap(i, j int)

Constants

const (
	// IterateStore is iteration type for Store requests.
	IterateStore = IterateType(iota)

	// IterateBootstrap is iteration type for Bootstrap requests.
	IterateBootstrap

	// IterateFindHost is iteration type for FindHost requests.
	IterateFindHost

	// IterateFindValue is iteration type for FindValue requests.
	IterateFindValue
)

const (
	// ParallelCalls is a small number representing the degree of parallelism in network calls.
	ParallelCalls = 3

	// KeyBitSize is the size in bits of the keys used to identify hosts and store and
	// retrieve data; in basic Kademlia this is 160, the length of a SHA1.
	KeyBitSize = 160

	// MaxContactsInBucket the maximum number of contacts stored in a bucket.
	MaxContactsInBucket = 20
)

Functions

func GetBucketIndexFromDifferingBit

func GetBucketIndexFromDifferingBit(id1, id2 []byte) int

GetBucketIndexFromDifferingBit returns appropriate bucket number for two host IDs.

Types

type HashTable

type HashTable struct {
	// The local host.
	Origin *host.Host

	// Routing table a list of all known hosts in the network
	// Hosts within buckets are sorted by least recently seen e.g.
	// [ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ][ ]
	//  ^                                                           ^
	//  └ Least recently seen                    Most recently seen ┘
	RoutingTable [][]*RouteHost // 160x20
	// contains filtered or unexported fields
}

HashTable represents the hash-table state.

func NewHashTable

func NewHashTable(id id.ID, address *host.Address) (*HashTable, error)

NewHashTable creates new HashTable.

func (*HashTable) DoesHostExistInBucket

func (ht *HashTable) DoesHostExistInBucket(bucket int, host []byte) bool

DoesHostExistInBucket checks if given Host exists in given bucket.

func (*HashTable) GetAllHostsInBucketCloserThan

func (ht *HashTable) GetAllHostsInBucketCloserThan(bucket int, id []byte) [][]byte

GetAllHostsInBucketCloserThan returns all hosts from given bucket that are closer to id then our host.

func (*HashTable) GetClosestContacts

func (ht *HashTable) GetClosestContacts(num int, target []byte, ignoredHosts []*host.Host) *RouteSet

GetClosestContacts returns RouteSet with num closest Hosts to target.

func (*HashTable) GetRandomIDFromBucket

func (ht *HashTable) GetRandomIDFromBucket(bucket int) []byte

GetRandomIDFromBucket returns random host ID from given bucket.

func (*HashTable) GetRefreshTimeForBucket

func (ht *HashTable) GetRefreshTimeForBucket(bucket int) time.Time

GetRefreshTimeForBucket returns Time when given bucket must be refreshed.

func (*HashTable) GetTotalHostsInBucket

func (ht *HashTable) GetTotalHostsInBucket(bucket int) int

GetTotalHostsInBucket returns number of Hosts in bucket.

func (*HashTable) Lock

func (ht *HashTable) Lock()

Lock locks internal table mutex.

func (*HashTable) MarkHostAsSeen

func (ht *HashTable) MarkHostAsSeen(host []byte)

MarkHostAsSeen marks given Host as seen.

func (*HashTable) ResetRefreshTimeForBucket

func (ht *HashTable) ResetRefreshTimeForBucket(bucket int)

ResetRefreshTimeForBucket resets refresh timer for given bucket.

func (*HashTable) TotalHosts

func (ht *HashTable) TotalHosts() int

TotalHosts returns total number of hosts in HashTable.

func (*HashTable) Unlock

func (ht *HashTable) Unlock()

Unlock unlocks internal table mutex.

type IterateType

type IterateType int

IterateType is type of iteration.

type RouteHost

type RouteHost struct {
	*host.Host
}

RouteHost represents a host in the network locally a separate struct due to the fact that we may want to add some metadata here later such as RTT, or LastSeen time.

func NewRouteHost

func NewRouteHost(host *host.Host) *RouteHost

NewRouteHost creates new RouteHost.

func RouteHostsFrom

func RouteHostsFrom(hosts []*host.Host) []*RouteHost

RouteHostsFrom creates list of RouteHosts from a list of Hosts.

type RouteSet

type RouteSet struct {
	// contains filtered or unexported fields
}

RouteSet is used in order to sort a list of arbitrary hosts against a comparator. These hosts are sorted by xor distance.

func NewRouteSet

func NewRouteSet() *RouteSet

NewRouteSet creates new RouteSet.

func (*RouteSet) Append

func (rs *RouteSet) Append(host *RouteHost)

Append adds single RouteHost to RouteSet.

func (*RouteSet) AppendMany

func (rs *RouteSet) AppendMany(hosts []*RouteHost)

AppendMany adds a list of RouteHosts to RouteSet.

func (*RouteSet) Contains

func (rs *RouteSet) Contains(host *RouteHost) bool

Contains checks if RouteSet contains given RouteHost.

func (*RouteSet) FirstHost

func (rs *RouteSet) FirstHost() *host.Host

FirstHost returns first Host from RouteSet.

func (*RouteSet) Hosts

func (rs *RouteSet) Hosts() []*host.Host

Hosts returns list of RouteSet hosts.

func (*RouteSet) Len

func (rs *RouteSet) Len() int

Len returns number of hosts in RouteSet.

func (*RouteSet) Less

func (rs *RouteSet) Less(i, j int) bool

Less is a sorting function for RouteSet.

func (*RouteSet) Remove

func (rs *RouteSet) Remove(host *RouteHost)

Remove removes host from RouteSet.

func (*RouteSet) RemoveMany

func (rs *RouteSet) RemoveMany(hosts []*RouteHost)

RemoveMany removes list of RoutHosts from RouteSet

func (*RouteSet) Swap

func (rs *RouteSet) Swap(i, j int)

Swap swaps two hosts in RouteSet.