“walker” is a packet being forwarded
from U to V, starting at U at time t = 0.
The packet’s remaining distance X at
t
time t is the length of the shortest path
to the destination, and the travel time
is the first instant T when X = 0. The
T

key question—whether there exists a finite T such that X = 0—is answered

T

by Gelenbe⁸ showing that:

λ 1 +

r

E[ T] = 2D

–b + b² + 2c(λ + r)

 

Here b is the “drift” parameter, so if b < 0 then the packet is on the average making progress toward the destination, while if b > 0 then it is moving away from it, and c is the variance per unit time or fluctuation related to the packet’s motion toward or away from the destination, so c > 0. 1/r is the average value of the time-out, and λ is the probability per unit time that the packet is lost. The expression above tells us, as expected, that if there is no time-out, that is, r = 0, and losses are possible, that is, λ > 0, then E[T] = + ∞, that is, a packet will never make it to its destination. If there are no packet losses, that is, λ = 0, and there is also no time-out, that is, r = 0, then E[T] < ∞ if b < 0, while if b > 0 then, as expected, E[T] = + ∞. The time-out is also thus a protection against packets that “lose their way” by traveling on and on through the infinite network without ever reaching their destination. Most interestingly, when c > 0, that is, there is randomness in the path, we have E[T] < ∞ as long as there are losses or a finite time-out. However, if the path is deterministic, that is, c = 0, then the travel time is infinite unless b < 0. Thus we establish that, even in the worst case of an infinitely large network in which individual nodes may lose packets and packets may lose their way by meandering indefinitely in the network, as long as there is randomness in the routing (c > 0) and a finite time-out is available (r > 0), the packet will reach its destination in finite time, even though no correct routing information is available at the nodes of the network. This model also covers the case of “wrong” routing information with b > 0, where packets are probabilistically sent away from the destination, and with uncertain or “partially correct” routing information with b < 0 where (on average)

interesting is that
the criterion that
combines delay
with number of
hops leads to
the best results,
though they are
comparable to the
results based on
using just the delay
as the Qos goal.

packets get closer to the destination at each step. The “ideal” case b = − 1 is when the packet makes the fastest possible progress to the destination.

self-Aware Routing

The second question (b) concerns the routing algorithms. Most routing techniques attempt to optimize one or more criteria in addition to the basic requirement of forwarding traffic from any source to any destination. The shortest-path routing algorithm is based on the premise that if a packet visits the smallest possible number of hops toward its destination, then the network overhead is minimized, as is most of the other criteria of interest (such as packet loss and packet delay). A SAN will attempt to optimize network performance through exploration, measurement, and adaptation, rather than through an a priori choice (such as the shortest path).

Much of the published work on SAN routing follows two approaches using reinforcement learning (RL), first proposed for packet routing by Boyan and Littman. The Cognitive Packet Net-

2 work (CPN) approach^{11, 13} uses “smart packets” (SP) for path discovery, together with RL and neural networks installed in each network node, adaptively selecting paths so as to offer “best effort” QoS to end users. SPs are sent out by nodes that are actively involved in forwarding packets to discover and assess paths that lead to destination nodes. The “Ant Colony” ^{3, 4, 19} paradigm searches for paths from source nodes to specific destination nodes by emulating the pheromone-based technique used by biological ants to mark their paths and communicate with fellow members of the same colony. Both CPN and Ant Colony algorithms include random search when information about suitable paths is unavailable, reinforcing the importance attributed to paths that appear to be best and using alternate paths when previously selected paths prove less desirable.

In CPN, SPs discover routes for connections to specific destinations. They are routed using RL based on a QoS “goal.” We use the term “goal” to indicate that there is no guaranteed QoS and that CPN provides a best effort to satisfy the desired QoS. SPs do not carry payload, finding routes and col-