Documentation
¶
Overview ¶
Package tree is an implementation of a tree-based routing algorithm.
The router creates a routing table for each protocol that will progressively build a tree. The tree will adapt to unresponsive participants but it is not resilient to faults happening after the table has been generated.
The resulting tree will be balanced to limit the number of hops you need to send a message, while also trying to limit the number of connections per node. The routes are built upon requests so that the interior nodes of the tree are the first participants to be contacted.
Documentation Last Review: 06.10.2020
Index ¶
Examples ¶
Constants ¶
This section is empty.
Variables ¶
This section is empty.
Functions ¶
This section is empty.
Types ¶
type AddrSet ¶
AddrSet is a set of unique addresses.
type Branches ¶
Branches is a partial representation of a tree which shows only the direct branches of the node and children's branch, but unstructured.
type Router ¶
type Router struct {
// contains filtered or unexported fields
}
Router is an implementation of a router producing routes with an algorithm based on tree.
- implements router.Router
func NewRouter ¶
func NewRouter(f mino.AddressFactory, options ...RouterOption) Router
NewRouter returns a new router
func (Router) GenerateTableFrom ¶
GenerateTableFrom implements router.Router. It creates the routing table associated with the handshake that can contain some parameter.
func (Router) GetHandshakeFactory ¶
func (r Router) GetHandshakeFactory() router.HandshakeFactory
GetHandshakeFactory implements router.Router. It returns the handshake factory.
func (Router) GetPacketFactory ¶
func (r Router) GetPacketFactory() router.PacketFactory
GetPacketFactory implements router.Router. It returns the packet factory.
func (Router) New ¶
New implements router.Router. It creates the routing table for the node that is booting the protocol. This node will be the root of the tree.
Example ¶
router := NewRouter(session.AddressFactory{})
addrA := session.NewAddress("127.0.0.1:2000")
addrB := session.NewAddress("127.0.0.1:3000")
players := mino.NewAddresses(addrA, addrB)
table, err := router.New(players, addrA)
if err != nil {
panic("routing table failed: " + err.Error())
}
routes, voids := table.Forward(table.Make(addrA, []mino.Address{addrB}, []byte{}))
fmt.Println(voids)
for to := range routes {
fmt.Println(to)
}
Output: map[] grpcs://127.0.0.1:3000
type RouterOption ¶
type RouterOption func(*Router)
RouterOption is the signature of the option constructor
func WithHeight ¶
func WithHeight(maxHeight int) RouterOption
WithHeight allows to specify the maximum height of the tree when calling NewRouter
type Table ¶
type Table struct {
// contains filtered or unexported fields
}
Table is a routing table that is using a tree structure to communicate between the nodes.
- implements router.RoutingTable
func (Table) Forward ¶
Forward implements router.RoutingTable. It takes a packet and split it into the different routes it should be forwarded to.
func (Table) Make ¶
Make implements router.RoutingTable. It creates a packet with the source address, the destination addresses and the payload.
func (Table) OnFailure ¶
OnFailure implements router.Router. The tree will try to adapt itself to reach the address, but it will return an error if the address is a direct branch of the tree.
func (Table) PrepareHandshakeFor ¶
PrepareHandshakeFor implements router.RoutingTable. It creates a handshake message that should be sent to the distant peer when opening a relay to it. The peer will then generate its own routing table based on the handshake.
Example ¶
routerA := NewRouter(session.AddressFactory{})
addrA := session.NewAddress("127.0.0.1:2000")
addrB := session.NewAddress("127.0.0.1:3000")
players := mino.NewAddresses(addrA, addrB)
table, err := routerA.New(players, addrA)
if err != nil {
panic("routing table failed: " + err.Error())
}
handshake := table.PrepareHandshakeFor(addrB)
// Send the handshake to the address B..
routerB := NewRouter(session.AddressFactory{})
tableB, err := routerB.GenerateTableFrom(handshake)
if err != nil {
panic("malformed handshake: " + err.Error())
}
packet := tableB.Make(addrB, []mino.Address{addrA}, []byte{})
fmt.Println(packet.GetSource())
fmt.Println(packet.GetDestination())
Output: grpcs://127.0.0.1:3000 [grpcs://127.0.0.1:2000]
type Tree ¶
type Tree interface {
// GetMaxHeight returns the maximum height for this tree.
GetMaxHeight() int
// GetRoute returns the address to route the provided target. It will return
// a nil value if no route is found in this tree.
GetRoute(to mino.Address) (mino.Address, error)
// GetChildren returns the children of a direct branch of this tree. It
// represents the list of routable addresses for a given branch.
GetChildren(to mino.Address) []mino.Address
// Remove marks the address as unreachable and fixes the tree if
// appropriate.
Remove(addr mino.Address)
}
Tree is the interface used by the router to determine the routes.
Source Files
Directories