Multipath routing has been considered that it can improve the communication network in termes of the reliability (failure recovery) and the available bandwidth. Past works, however, did not provide sufficient number of multipaths. This work provides MARA, a new multipath routing algorithm that produces a number of multipaths. MARA calculates routes using every link in the network (for a destination). It runs in a sub-one second time for moderate sized networks.
Y. Ohara, S. Imahori, R. Van Meter, "MARA: Maximum Alternative Routing Algorithm," IEEE INFOCOM 2009, April 2009 (Rio de Janeiro, Brazil) [pdf]
"©2009 IEEE. Personal use of this material is permitted. However, permission to reprint/republish this material for advertising or promotional purposes or for creating new collective works for resale or redistribution to servers or lists, or to reuse any copyrighted component of this work in other works must be obtained from the IEEE."
"This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author's copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder."
We propose a new routing architecture that can leverages the many alternative paths produced by MARA. It is called Drouting architecture. Drouting architecture enables the use of many multipaths, by a really simple way. It enables to switch the communication path stochastically, by only changing of the random packet tag. Routers map packet tags to nexthops deterministically, so enables also not to change paths (e.g. for a TCP session). Drouting architecture achieves high probability of failure avoidance, with scalability. It is further expected that Drouting architecture enables ad-hoc "QoS routing" and employment of "network optimization".
Y. Ohara, H. Kusumoto, O. Nakamura, and J. Murai, “Drouting architecture: Improvement of failure avoidance capability using multipath routing.” IEICE Transactions, vol. 91-B, no. 5, pp. 1403–1415, 2008. [link]
Y. Ohara, “Routing Architecture for the Dependable Internet,” Ph.D. dissertation, Keio University, 2008. [pdf]
Simple simulation, analysis, and evaluation of routing algorithms and routing systems were tough tasks because past network simulators mainly targets on the simulation of complex (multi-layered) protocol operation. A new simulation tool, SimRouting, takes Graph theoretic way, disregards the details such as protocol header overhead, and targets to evaluate routing systems easily. Evaluation of MARA and Drouting architecture was conducted using the SimRouting.
Drouting architecture reserves rooms to load balance the traffic on multipath routes. Dynamic programming, along with the Drouting architecture, is expected to enable off-line network optimization as a simple, reasonable, straightforward approach.
This work investigated the effects of oscillating network events to OSPF. It showed that the communication path can excessively be unstable, even though there is an alternative stable path. Also in this work, BGP route flap damping technology is applied to avoid this problem, and showed significant improvements. This work was summarized in the SAINT 2003 workshop paper.
Y. Ohara, M. Bhatia, N. Osamu, and J. Murai. Route Flapping Effects on OSPF. In Proceedings of the 2003 Symposium on Applications and the Internet Workshops, 2003. [pdf]
Due to lack of open OSPFv3 implementation managing native IPv6 Network was hard task. We implemented an open OSPFv3 implementation from early days in GNU Zebra. It accelerated many vendors to provide interoperable OSPFv3 implementations.
... read more