1Provably Competitive Adaptive RoutingBaruch Awerbuch David Holmer Robert Kleinberg Herbert RubensAbstract—An ad hoc wireless network is an au-tonomous self-organizing system of mobile nodes con-nected by wireless links where nodes not in direct rangecommunicate via intermediary nodes. Routing in ad hocnetworks is a challenging problem as a result of highlydynamic topology as well as bandwidth and energyconstraints. In addition, security is critical in thesenetworks due to the accessibility of the shared wirelessmedium and the cooperative nature of ad hoc networks.However, none of the existing routing algorithms canwithstand a dynamic proactive adversarial attack. Therouting protocol presented in this work attempts toprovide throughput competitive route selection againstan adaptive adversary. A proof of the convergence timeof our algorithm is presented as well as preliminarysimulation results.I. BACKGROUNDThe basic service offered by every node in an ad-hoc network is that of routing packets from theirsource to their ultimate destination. In general, rout-ing protocols are susceptible to a wide variety ofattacks. For example, a malicious node may perform adenial of service attack by selectively jamming someareas of the network.A great deal of work has been done in termsof guaranteeing practical security considerations inexisting network protocols (see description of existingwork provided in Section II). In practice, adversarialattacks observed and documented in ad hoc networksmight not be overly sophisticated. The ease of accessto the medium has allowed extremely basic attacksto cause a great deal of damage. Consequently, suchattacks can be thwarted by simple yet effective meth-ods.Existing work in the literature considered a numberof strong adversary models. For example, [1] consid-ers a random fault pattern; [2] deals with a static faultpattern and [3] deals with an oblivious (non-adaptive)pattern.Our goal is to design routing protocols for net-works that are provably tolerant of arbitrary adaptiveDOS attacks. The adversary that we will considerselectively attacks packets on a given node or link.This adversary benefits from knowledge of the trafficpattern (including packet contents); this includes allcurrent traffic and all past traffic history.As a result, the algorithms and analysis techniquesused in the previous work will not apply. Existingmethods that do not ignore sophisticated adaptiveattacks either use brute force (flooding) or assumethe existence of some trusted servers or routers (seesection II). We do not wish to make such restrictingassumptions. As a result, the task of designing athroughput competitive routing algorithm is muchharder.It may appear that our adversarial routing modelmay lead to impractical algorithms in benign (non-adversarial) settings. However, routing algorithmssimilar to the one studied here were developedand tested in real network environments by BritishTelecomm and NTT for both wired and wirelessnetworks with superior results [6], [20], [9], [7], [17],[18], [5], [10]. AntNet, a particular such algorithm,was tested in routing for data communication net-works [6]. The algorithm performed better than OSPF,distributed Bellman-Ford with various dynamic met-rics, and various modifications of shortest path witha dynamic cost metric [4], [17].Our contribution: We propose a new algorithmfor adaptively selecting routing paths in a networkwith dynamic adversarial edge failures, and we givea rigorous mathematical analysis of this algorithm,proving that its packet loss will match the minimalcumulative loss of any path, up to an additive errorwhich is sublinear in the number of trials. The generalframework we propose is appropriate for analyzingrouting protocols for networks operating under theextremely strong adversarial model specified above.Such strong models have not been considered inthe literature to the best of our knowledge. In fact,adaptive dynamic denial of service attacks are suf-ficient to break most existing algorithmic work. (InSection III, we briefly describe why DoS attacks areso devastating.)2What distinguishes the present work is our in-sistence on proving that under completely arbitraryadversarial behavior, with essentially no assumptionsabout the network, the packet loss of our protocol willessentially match the minimal cumulative loss (i.e.,sum of losses of individual links) of any path. Whileit may seem counter-intuitive that such a goal can beachieved, the key is that although we assume an ar-bitrary dynamic adversary, we compare the algorithmagainst the best static path; if the adversary workshard to damage the algorithm’s throughput, it mustnecessarily inflict a large cumulative loss on everypath in the network.At this point, one could debate whether such so-phisticated adversaries are ever going to surface inreality, or whether they are only monsters in ourimagination. Our counter-argument is that if, as wetheorize, ubiquitous wireless networks become theunderlying fabric that binds our society together, wecannot afford not to plan against an adversary witharbitrary powers.The rest of this paper is organized as follows.In Sections II and III, we review some of the ex-isting work in this area and survey some of thechallenges which illustrate why our problem is notsolved by simpler approaches. In Sections IV weoutline the main ideas underlying our algorithm,which is specified precisely in Section V, analyzedmathematically in Section VI, and experimentallytested in Section VII. The algorithm contains sometunable parameters, e.g. a “sampling rate” δ and a“learning rate” β. Adjusting β allows one to smoothlyinterpolate between the greedy algorithm (β near 0)and algorithms which are less responsive but morerobust against an adaptive adversary (β near 1). Themathematical analysis in Section VI indicates thatsetting β very close to 1 guarantees good performanceagainst an arbitrary adaptive adversarial attack; how-ever in many circumstances (e.g. random edge fail-ures) greedy approaches achieve faster convergence,which leads one to expect superior performance froma smaller value of β in such circumstances. Thesetheoretical considerations are substantiated by theexperiments in Section VII, where the algorithm istested in a variety of network topologies with randomedge failures, and smaller values of β indeed achievefaster convergence.II. EXISTING WORKa) Algorithmic Work: The only algorithmic re-sults that possibly work