AN OVERLAY ARCHITECTURE FOR THROUGHPUT OPTIMAL MULTIPATH ROUTING

 ABSTRACT

Legacy networks are often designed to operate withsimple single-path routing, like the shortest path, which is knownto be throughput suboptimal. On the other hand, previouslyproposed throughput optimal policies (i.e., backpressure) requireevery device in the network to make dynamic routing decisions.In this paper, we study an overlay architecture for dynamicrouting, such that only a subset of devices (overlay nodes) need tomake the dynamic routing decisions. We determine the essentialcollection of nodes that must bifurcate traffic for achievingthe maximum multi-commodity network throughput. We applyour optimal node placement algorithm to several graphs andthe results show that a small fraction of overlay nodes issufficient for achieving maximum throughput. Finally, we proposea threshold-based policy (BP-T) and a heuristic policy (OBP),which dynamically control traffic bifurcations at overlay nodes.Policy BP-T is proved to maximize throughput for the case whenunderlay paths do no overlap. In all studied simulation scenarios,OBP not only achieves full throughput but also reduces delay incomparison to the throughput optimal backpressure routing.

EXISTING SYSTEM:

Backpressure (BP) routing, first proposed in, is athroughput optimal routing policy that has been studied fordecades. Its strength lies in discovering multipath routes andutilizing them optimally without knowledge of the networkparameters, such as arrival rates, link capacities, mobility,fading, etc. Nevertheless, the adoption of this routing policyhas not been embraced for general use on the Internet. This isdue, in part, to an inability of backpressure routing to coexistwith legacy routing protocols. With few exceptions, backpressurerouting has been studied in homogeneous networks,where all nodes are dynamically controllable and implementthe backpressure policy across all nodes uniformly. As willbe shown, backpressure routing — as proposed is suboptimal when applied only to a subset of nodes in thenetwork.Techniques to provide throughput-optimal multipath routinghave been explored in various contexts. The work considers the problem of setting link weights provided to theOpen Shortest Path First (OSPF) routing protocol such that,when coupled with bifurcating traffic equally a shortestpaths, the network achieves throughput equal to the optimalmulticommodity flow. The authors of use an entropy maximizationframework to develop a new throughput-optimal linkstate routing protocol where each router intelligently bifurcatestraffic for each destination a its outgoing links. Thesetechniques all require centralized control, universal adoptionby all network nodes, or both; thus none of these techniquescould provide incremental deployment of throughput optimalrouting to wireless networks. Moreover, these techniques cannotbe used in conjunction with throughput optimal dynamiccontrol schemes, such as backpressure.

PROPOSED SYSTEM:

Our contributions are summarized below.• We formulate the problem of placing the minimum numberof overlay (controllable) nodes in a legacy networkin order to achieve the full multicommodity throughputregion and provide an efficient placement algorithm.• We apply our placement algorithm to several scenariosof interest including regular and random graphs, showingthat in some cases, only a small fraction of overlay nodesis sufficient for maximum throughput.• We propose a threshold-based control policy — BP-T —as a modification of BP for use at overlay nodes, andprove this policy to stabilize all arrival rates in Λ(V)when tunnels do not overlap.• We propose a heuristic overlay BP policy — OBP — foruse at overlay nodes on general topologies. We show viasimulation that OBP can outperform BP when limited tocontrol at overlay nodes, and that OBP also has betterdelay performance compared to BP with control at allnodes.

CONCLUSIONS

We study optimal routing in legacy networks where only asubset of nodes can make dynamic routing decisions, whilethe legacy nodes can forward packets only on pre-specifiedshortest-paths. This model captures evolving heterogeneousnetworks where intelligence is introduced at a fraction ofnodes. We propose a necessary and sufficient condition forthe overlay node placement to enable the full multicommoditythroughput region. Based on this condition, we devise analgorithm for optimal controllable node placement. We runthe algorithm on large random graphs to show that veryoften a small number of intelligent nodes suffices for fullthroughput. Finally, we propose dynamic routing policies tobe implemented in a network overlay. We provide a thresholdbasedpolicy that is optimal for overlays with non-overlappingtunnels, and provide and alternate policy for general networksthat demonstrates superior performance in terms of boththroughput and delay.

REFERENCES

[1] D. Andersen, H. Balakrishnan, F. Kaashoek, and R. Morris, “Resilientoverlay networks,” in Proc. ACM SOSP, Oct. 2001, pp. 131–145.[Online]. Available: http://doi.acm.org/10.1145/502034.502048

[2] L. Bui, R. Srikant, and A. Stolyar, “Novel architectures and algorithmsfor delay reduction in back-pressure scheduling and routing,” in Proc.IEEE INFOCOM, Apr. 2009, pp. 2936–2940.

[3] B. Fortz and M. Thorup, “Internet traffic engineering by optimizingOSPF weights,” in Proc. IEEE INFOCOM, Mar. 2000,pp. 519–528.

[4] L. Georgiadis, M. J. Neely, and L. Tassiulas, “Resource allocationand cross-layer control in wireless networks,” Found. Trends Netw.,vol. 1, no. 1, pp. 1–144, 2006. [Online]. Available: http://dx.doi.org/10.1561/1300000001

[5] J. Han, D. Watson, and F. Jahanian, “Topology aware overlay networks,”in Proc. IEEE INFOCOM, Mar. 2005, pp. 2554–2565. [Online]. Available:http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=1498540

[6] N. M. Jones, “Practical algorithms for distributed network control,”Ph.D. dissertation, Dept. Aeronautics Astronautics Massachusetts Inst.Technol., Cambridge, MA, USA, 2013.

[7] N. M. Jones, G. S. Paschos, B. Shrader, and E. Modiano, “An overlayarchitecture for throughput optimal multipath routing,” in Proc. ACMMobiHoc, Aug. 2014, pp. 73–82.

[8] W. Khan, L. B. Le, and E. Modiano, “Autonomous routing algorithmsfor networks with wide-spread failures,” in Proc. IEEE MILCOM,Oct. 2009, pp. 1–6. [Online]. Available: http://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=5379792

[9] M. J. Neely, E. Modiano, and C. E. Rohrs, “Dynamic power allocationand routing for time-varying wireless networks,” IEEE J. Sel. AreasCommun., vol. 23, no. 1, pp. 89–103, Jan. 2005. [Online]. Available:http://ieeexplore.ieee.org/search/srchabstract.jsp?tp=&arnumber=1208724%&queryText%3Djsac+neely+modiano+rhors%26openedRefinements%3D*%26searchField%3D%Search+All

[10] M. E. J. Newman, Networks: An Introduction. New York, NY, USA:Oxford Univ. Press, 2010.