  We consider the shortest path routing (SPR) of a network with stochastically
time varying link metrics under potential adversarial attacks. Due to potential
denial of service attacks, the distributions of link states could be stochastic
(benign) or adversarial at different temporal and spatial locations. Without
any \emph{a priori}, designing an adaptive SPR protocol to cope with all
possible situations in practice optimally is a very challenging issue. In this
paper, we present the first solution by formulating it as a multi-armed bandit
(MAB) problem. By introducing a novel control parameter into the exploration
phase for each link, a martingale inequality is applied in the our
combinatorial adversarial MAB framework. As such, our proposed algorithms could
automatically detect features of the environment within a unified framework and
find the optimal SPR strategies with almost optimal learning performance in all
possible cases over time. Moreover, we study important issues related to the
practical implementation, such as decoupling route selection with multi-path
route probing, cooperative learning among multiple sources, the "cold-start"
issue and delayed feedback of our algorithm. Nonetheless, the proposed SPR
algorithms can be implemented with low complexity and they are proved to scale
very well with the network size. Comparing to existing approaches in a typical
network scenario under jamming attacks, our algorithm has a 65.3\% improvement
of network delay given a learning period and a 81.5\% improvement of learning
duration under a specified network delay.
