We might see in practice that some packages from so-called real-time ones sent
arrived “almost” to their destination and thus can sit for a while in a queue before
the last jump. Other packages in the middle of their journey might need “emergency
treatment” and served first making their passing as smooth as possible.
We easily can generate different situations and suggest another dozen of algorithms [18–20] to address examples presented. But this is not practical—a performance [21] of the system as a whole requires thinning of service routines and
relieve more time and space for user data (packages).
One of the solutions proposed here is to merge algorithm of forward tracing
using weighted relative cost of the links with standard routing table existing in each
router. An introducing the relative weight of path defined inside the routing table
for chosen package.
Indeed, the size of Internet in numbers of nodes exceed 7 billion nodes, therefore, considering Internet as a set of nodes we can get a cardinal of this set—i.e. a
number of elements in the set. Surprisingly, due to hierarchical organization
between the most distant nodes there are no more than 20–25 routers, (from our
examples using Ping we observed 11–14 routers). Additionally—assuming “round
the Earth” distance of tracing one might for each router “weight” the share of this
router in the path of a package d i /D where d i is a distance known from internal
routing table and D is a “diameter” of an Internet.
19.7 Comparative Analysis of Proposed Algorithm and A*
Here we present an experiment and simulation of desperation control algorithm as
described with known widely used in networking as Dijkstra and further modification as A* algorithm.
Let us repeat a Fig. 19.3, expanding it to our convenience as Fig. 19.4.
Dijkstra algorithm is based on need of expanding a horizon if visibility at each
iteration of interaction with neighbors, gaining distances for steps to the further
destinations. Knowledge about the network obtained at each step contacting
neighbors. What we see, sitting at node a? the distances 5, 7, 2, 4, to our direct
neighbors: nodes e, d, c, b. What we chose knowing these numbers? Obviously, a
link with cost 2, to the node c.
Taking first step and considering that next searching of distance will be produced
from the node c we create further list of distance from c, taking into account (reading
backward) a distance accumulated from starting point—node a. If we aiming node
f as our final destination we have to consider two distances—to node f directly—cost
8 and to node b, cost 3 with further unknown length written usually as:
(b, 3, ∞)
Because a distance to b is shorter than distance of straight f step—(costs 8) it is
possible to appoint as next marked node from where we will seek next step a node b:
b ! f : 5.
19.6 Desperation—Proposed Algorithms for Handling
279
arrived “almost” to their destination and thus can sit for a while in a queue before
the last jump. Other packages in the middle of their journey might need “emergency
treatment” and served first making their passing as smooth as possible.
We easily can generate different situations and suggest another dozen of algorithms [18–20] to address examples presented. But this is not practical—a performance [21] of the system as a whole requires thinning of service routines and
relieve more time and space for user data (packages).
One of the solutions proposed here is to merge algorithm of forward tracing
using weighted relative cost of the links with standard routing table existing in each
router. An introducing the relative weight of path defined inside the routing table
for chosen package.
Indeed, the size of Internet in numbers of nodes exceed 7 billion nodes, therefore, considering Internet as a set of nodes we can get a cardinal of this set—i.e. a
number of elements in the set. Surprisingly, due to hierarchical organization
between the most distant nodes there are no more than 20–25 routers, (from our
examples using Ping we observed 11–14 routers). Additionally—assuming “round
the Earth” distance of tracing one might for each router “weight” the share of this
router in the path of a package d i /D where d i is a distance known from internal
routing table and D is a “diameter” of an Internet.
19.7 Comparative Analysis of Proposed Algorithm and A*
Here we present an experiment and simulation of desperation control algorithm as
described with known widely used in networking as Dijkstra and further modification as A* algorithm.
Let us repeat a Fig. 19.3, expanding it to our convenience as Fig. 19.4.
Dijkstra algorithm is based on need of expanding a horizon if visibility at each
iteration of interaction with neighbors, gaining distances for steps to the further
destinations. Knowledge about the network obtained at each step contacting
neighbors. What we see, sitting at node a? the distances 5, 7, 2, 4, to our direct
neighbors: nodes e, d, c, b. What we chose knowing these numbers? Obviously, a
link with cost 2, to the node c.
Taking first step and considering that next searching of distance will be produced
from the node c we create further list of distance from c, taking into account (reading
backward) a distance accumulated from starting point—node a. If we aiming node
f as our final destination we have to consider two distances—to node f directly—cost
8 and to node b, cost 3 with further unknown length written usually as:
(b, 3, ∞)
Because a distance to b is shorter than distance of straight f step—(costs 8) it is
possible to appoint as next marked node from where we will seek next step a node b:
b ! f : 5.
19.6 Desperation—Proposed Algorithms for Handling
279