|
In this talk I will talk about a network problem that showcases the kind of research problems I work on. A routing scheme $\Rr$ in a network $G=(V,E)$ is an algorithm that allows to send messages from one node to another in the network.
Given the location of the nodes, we first consider a preprocessing phase in which we construct the network (if possible, we also assing\emph{routing table} with additional information to each node). After this preprocessing, we give a local routing (i.e., we can only use the information from the label of the target and the routing table of the node that we are currently at).
We present a network construction algorithm paired with a routing scheme in the presence of obstacles: if we are not allowed a routing table, each node stores a constant amount of information and the messages are guaranteed to arrive. If we are allowed a routing table of size of size $\Oe(\eps^{-1}\log n)$ per node, the routing scheme provides a stretch of $1+\eps$ for any $\eps > 0$. is $\Oe(n^2+\eps^{-1}n)$. This improves the best known strategies for general graphs by Roditty and Tov (Distributed Computing 2016).
|
