AN OVERLAY ARCHITECTURE FOR THROUGHPUTOPTIMAL 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.
EXISITNG SYSTEM:
We consider two problem areas for control of heterogeneousnetworks. First, we develop algorithms for choosing the placementof controllable nodes, where our goal here is to allocatethe minimum number of controllable nodes such that the fullnetwork stability region is available. Second, given any subsetof nodes that are controllable, we also wish to develop anoptimal routing policy that operates solely on these nodes.In the first problem area, we are given a graph G withnodes N supporting shortest-path routes between each pairof nodes. We wish to identify a minimal set of controllablenodes V⊆Nsuch that if only these nodes are allowedto bifurcate traffic, maximum throughput can be achieved.Ideally, (V) is the throughput region (i.e., the set of multicommodityarrival rate vectors that can be stably supported bythe network) for graph G when only nodes V are controllable,while Λ(N) is the throughput region when all nodes arecontrollable. Note that comparing throughput regions directlycan be difficult, so instead we identify a condition thatis necessary and sufficient to guarantee the full throughputregion, and then we search for the minimal V that satisfiesthis condition.GIn the second problem area, we consider the design ofdynamic network control policies that operate only at con-trollable nodes V. These controllable nodes are connectedby “tunnels” or paths through uncontrollable sections of thenetwork, where the control policy can choose when to injectpackets into a tunnel but the tunnel itself is uncontrollable.
PROPOSED SYSTEM:
Our solutions for the first and second problem areas arecomplementary, in the sense that they can be used togetherto solve the joint problem of providing maximum throughputwhen only a subset of nodes are controllable. However, oursolutions can also be used in isolation; our node placementalgorithm can be used with other control policies, and ourBP extensions can yield maximal stability with any overlaynode placement and legacy single-path routing.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.
[11] G. S. Paschos and E. Modia