figure 3: Total packet delay with 6.4Mbps background traffic carried out for sPs, that is,
for a small fraction of the traffic, resulting in reduced router computation overhead.
6.4Mbps background traffic
CPN Algorithm QoS Goal
× hops
ᐃ hops + delay
×
ᐃ
ᐃ×
Dumb Packet Delay (ms)
102
ᐃ
×
ᐃ×
×
×
ᐃ
×
ᐃ
ᐃ
101
ᐃ
×
1
ᐃ
×
ᐃ
×
2
3
45
Rate (Mbps)
6
7
8
figure 4: Total average delay for sPs (top) and DPs (bottom) and average delay
for all packets (center) as a function of the percentage of sPs.
Round trip delay
DP
avg
SP
Delay (ms)
22
20
18
16
14
12
10
8
6
4
2
0
10
20
30
40 50 60
Percentage of sP
70
80
90
100
lecting measurements based on three
complementary elements:
˲ Each node engaged in forwarding packets to some destination sends
out SPs that search for paths to the
destination(s) and gather measurement data about these paths. This data
is not limited to delay and packet loss
but may also include measurable information about power utilization by
nodes on those paths, the volume of
traffic on the paths, and the security of
the nodes and links on the paths. SPs
do not carry the actual traffic payload
but are used just for measurement and
exploration;
˲ Each node maintains a neural network to compute the next node an SP
from this node must go to. The weights
of the neural network are updated using an RL algorithm that uses data collected by the SPs. In CPN, the role of the
neural network is just to route the SPs,
and the “dumb packets” (DP) that carry
the payload are routed differently; and
˲ Each source node maintains an ordered list of paths to the destination(s)
they are concerned with. This list includes paths that are discovered by
the SPs and is updated using the QoS
information collected by the SPs. The
list is ordered with the best paths at the
top, so the payload or DB is forwarded
along the complete path (that is, they
are source-routed), and intermediate
nodes do not normally interfere with
them other than providing a store-and-forward capability.
When (and if) an SP arrives at its
destination, the destination generates
an acknowledgment (ACK) packet, and
the ACK stores the “reverse route,” as
well as the measurement data collected
by the SP. An SP that does not reach
its destination after a predetermined
number of hops (typically set as a multiple of the network’s diameter, here 30)
is destroyed. The ACK being returned
as a result of an SP will travel along the
“reverse route” obtained from the SP’s
route, examining it from right (
destination) to left (source), removing any
sequences of nodes that begin and end
in the same node. For instance, the path
< a, b, c, d, a, f, g, h, c, l, m > will result in
the reverse route < m, l, c, b, a >. Note that
the reverse route is not necessarily the
shortest reverse path nor the one resulting in the best QoS. Also ACKs deposit
QoS measurement data in mailboxes
(MBs) at the nodes they visit as they
move toward the SP’s source node. On
the other hand, DPs carry payload and
use dynamic source routing. The route
brought back by an ACK is used as a
source route by subsequent DPs of the
same QoS class with the same destination until a new route is brought back
by another ACK. An MB in each node
stores QoS information.
Each MB is organized as a least-re-cently-used (LRU) stack. The entries in
an MB are identified with the QoS class
and the destination. Since SPs are routed at each node using RL, they concentrate their search on the most promising paths for a given destination. Each
node contains one or more random
neural networks (RNNs), 15 where each
RNN corresponds to a QoS class and a
destination. In the RNN, the choice of
the output link of a node is represented
by a neuron, and the link corresponding to the “most excited” neuron is
used to forward a given SP. The RL algorithm operates as follows:
A “goal function” G is used to char-
acterize the objective one wishes to op-
timize for a given source to destination
connection; this objective may be hop
count (if one wants to minimize path
length), delay, packet loss rate, energy
utilization, and more, or a combination
of these factors. The reward R, which is
defined as R = 1 ÷ G, and successive val-
ues of R obtained from measurements
carried back by the ACK packets, are
denoted by R , l = 1, 2, · · · , and used to
l
compute a “historical value” of R:
T =∝T +( 1–∝) R
l l– 1 l
where ∝ is some constant (0 < ∝ < 1)
that determines the algorithm’s mem-
