Routing

Routing --- маршрутизация

A routing [math]\displaystyle{ \rho }[/math] in a graph or digraph [math]\displaystyle{ G }[/math] assigns to every pair of different vertices a path (a chain) [math]\displaystyle{ \rho(x,y) }[/math] from [math]\displaystyle{ x }[/math] to [math]\displaystyle{ y }[/math]. The paths [math]\displaystyle{ \rho(x,y) }[/math] are called routes. Given a graph [math]\displaystyle{ G }[/math], it is assumed that all communications between vertices are done through the routes of a fixed routing. Two parameters have been proposed to measure the efficiency and fault tolerance of a fixed routing in a graph or a digraph: the forwarding index and the diameter of the surviving route digraph. The vertex-forwarding index of a routing [math]\displaystyle{ \rho }[/math] in a graph or a digraph [math]\displaystyle{ G }[/math], [math]\displaystyle{ \xi(G,\rho) }[/math], is the maximum number of routes passing through a vertex. The edge- or arc-forwarding index, [math]\displaystyle{ \pi(G,\rho) }[/math], is defined analogously.

For a given set [math]\displaystyle{ F }[/math] of faulty vertices and/or arcs, the vertices of the surviving route digraph are the non-faulty vertices and there is an arc between two vertices if and only if there are no faults on the route between them. Fault-tolerant routings are such that the diameter of the surviving route digraph is small for any set of faults of a bounded size.