Communications - July 2009

in real time based on either the current state of the RNN in each node or on the most recent RL updates that have been made. A more sophisticated way of selecting paths could use the underlying RNN and RL but also make a further optimization decision based on the fact that at each source node, CPN maintains a set of paths with the most recent measured QoS metric for each path, as well as for each of the destinations with which the source communicates. Now suppose that two distinct paths SxIyD and SuIvD connect source S to destination D through the same intermediate node I, and these paths have been discovered by SPs and provide QoS metrics G(SxIyD) and G(SuIvD). Obviously SuIyD and SxIvD are also valid paths. If they were not previously discovered by SPs, one can still infer their estimated (not measured) QoS assuming the QoS data is additive. We denote the inferred QoS values by g(SuIyD) and g(SxIvD). Now suppose that one of the two inferred QoS values, say, g(SuIyD) is the “best” one (such as smallest delay, smallest loss, or best value of some other metric of interest). One can then use the hitherto untested path SuIyD to forward DPs, rather than the best of the two paths actually tested. Note that this operation of selecting new paths by combining prefixes and suffixes of previously discovered paths resembles the “crossover operation” in a genetic algorithm. ¹⁰ Experiments run with 1,024B DPs and varying the DP rate of 100 to 800 packets/sec showed that this additional optimization provided a small improvement in both packet loss rate and average packet delay.

However, when a significant amount of background traffic was added to each link, even with relatively low DP rate exceeding a certain value (300 packets/ sec), the original CPN algorithm performed significantly better, showing that the slower optimization process using older data introduced on top of CPN by the genetic algorithm-like approach is unable to respond quickly enough to changing network conditions.

Self-aware adaptation to failures. During experiments conducted in a 46-node testbed (see Figure 7), we observed that CPN can also protect a network against worm-like failures. In these experiments, failures begin at a given node that then randomly causes

figure 9: Adaptation reduces delay in the presence of failures.

Average end to end Delay for user 1 scanning rate = 0.04

▲ nonAdaptive CPN Current CPN Failure-Aware CPN

Rollback Recovery with Failure-Aware CPN

100

90

80

Packet Delay [ms]

70

60

▲▲

50

40

30

20

10

▲

0

0 10 20

▲

30 40

50 60

Time (s)

70

80 90 100 110 120

other nodes to fail. A node that fails is unable to forward traffic, causing neighbors to fail. Node failure is followed by recovery, representing cleaning and patching, at a constant rate of 1 node/sec. Figures 8 and 9 report the measured average packet loss and delay for 10 experiments where User 1 sent 7MB/sec CBR traffic from Node 6 to Node 24. When CPN is operating, the QoS is significantly better than when CPN is stopped after paths are established (top curves). Moreover, as further adaptive measures are taken (other curves), ²⁷ performance and QoS improve further.

Ant colony routing. Ant colony routing algorithms^{3, 4, 19} differ from CPN in the way they use RL, as well as in other respects. Inspired by the way ants use pheromones to mark their paths and communicate about sources of food, packets represent ants, nodes and links represent locations, and packets move toward their destinations based on paths with strong markings. When a packet reaches its destination, a corresponding “marking” packet heads back to the source by following the path in reverse or quasi-reverse order (or following the “strongly marked trail” and strengthening the marking at each link and node it visits). The markings degrade over time (“ forgetfulness”) if not reinforced by the passage of other packets. The algorithm is initiated by a random search until the destination node is found and the discovered path(s) is reinforced by the re-

turning packets. The returning packet from the destination is like the ACK packet in CPN, but ant colony routing algorithms use payload packets for both search and data delivery, while CPN separates the search role via SPs from the payload role via DPs; the resulting QoS is better when DPs specialize in payload conveyance and SPs are restricted to search. Thus CPN uses more packets, since SPs are constantly being sent forward to accomplish the search function, representing a constant fraction (such as 10%) of total traffic. Moreover, ant colony algorithms do not use a neural network (as in CPN) to store RL information inside a given node. CPN routers carry out route computation only for SPs and represent a small fraction of total traffic, but ACKs and DPs are source-routed, while ant colony algorithms typically require route computation for all packets. Clearly, ant colony algorithms are better adapted to networks that experience frequent disruption, since all packets are in a sense autonomous. In CPN, if a DP’s path is disrupted, the packet must be retransmitted at the source, with information brought back by a subsequent SP that finds another path. Thus CPN will be better at forwarding packets but slower in responding to changes in topology.