Multi-path routing

from Wikipedia, the free encyclopedia

Multi-path routing or Multipath Routing ( engl. Multiway switching) is a switching technology by using a plurality of alternative paths through a network , which a number of advantages, such as fault tolerance , increased bandwidth or improved safety features. The calculated multiple paths can overlap or be disconnected.

Multipath switching in wireless networks

To improve performance or fault tolerance :

CMR (Concurrent Multi-Path Routing) is often understood as the simultaneous management and use of several available paths for the transmission of data streams from one or more applications. In this form, a separate path is assigned to each data stream if the number of available paths allows this. When there are more data streams than available paths, some data streams share paths. This results in a better use of the available bandwidth by creating several active transmission queues. Furthermore, this offers a higher degree of fault tolerance. If one path fails, only the data traffic on this path is impaired, the other paths continue to serve their data streams. In addition, in the ideal case, an alternative path is immediately available via which the interrupted data stream can be continued or resumed.

This method provides better transmission performance and fault tolerance by providing:

  • Simultaneous, parallel transmission over several carriers.
  • Load sharing across more available devices.
  • Avoiding path exploration when reassigning an interrupted data stream.

Disadvantages of this method are:

  • Some applications can be slower when sending data to the transport layer, so the assigned paths are not used enough.
  • Switching to an alternate path may cause an interruption while the connection is being re-established.

Real CMR

A more powerful form of CMR (true CMR) goes beyond simply showing paths that applications can bind to. Real CMR combines all available paths into a single, virtual path. All applications pass their packets to this virtual path, which is divided on the network layer. The packets are then sent over the actual paths using a special method, e.g. B. ring distribution or weighted queuing, transmitted. If a connection or a switching node should fail and therefore make one or more paths unusable, subsequent packets will not be routed via these paths. The data stream continues uninterrupted and transparently for the application. This method offers significant performance advantages over the previous one:

  • By constantly passing packets to all paths, these are used far better.
  • No matter how many nodes (and therefore paths) fail, as long as at least one path exists, the virtual path is still available and all sessions remain connected. This means that no data stream has to be restarted and there is no connection re-establishment delay.

It should be noted that due to its nature, the real CMR can lead to the delivery of the packets out of order (OOOD), which has a significant negative effect on standard TCP. Standard TCP , however, has proven to be completely unsuitable for use in demanding wireless environments and must in any case be supplemented by an element such as a TCP gateway that is able to cope with these requirements. One such gateway tool is SCPS-TP, which successfully handles the OOOD problem with its selective negative acknowledgment (SNACK) capability.

Another important advantage of real CMR, which is urgently needed for wireless network connections , is the support for extended security. In short, in order to compromise a data exchange, many of the routes through which it is routed must be compromised. Further information can be found in the section Itemized under " Improving network security".

Capillary mediation

In network planning and graph theory , capillary switching for a given network is a multipath solution between a pair of source and destination nodes. Unlike the shortest path or maximum flow mediation, there is only one solution for capillary mediation.

Capillary switching can be achieved through an iterative linear programming (LP) process that converts the flow of a single path into that of a capillary path.

  1. First, the maximum value of the load of all switch node connections is minimized
    • This is done by lowering the upper limit of the load value and applying it to all connections.
    • The total mass of the river is evenly divided between the possible parallel routes.
  2. The connection bottlenecks of the first layer (see below) are searched for and their load is set to the minimum found.
  3. The maximum load of the remaining connections is then reduced in a similar manner, but now without the connection bottlenecks of the first level.
    • This second iteration refines the path diversity.
  4. The second level connection bottlenecks are now being sought
    • Again, the maximum load of all remaining connections is minimized, but now also without the bottlenecks of the second level.
  5. This process is repeated until the entire interconnection footprint is within the bottlenecks of the layers.

At each functional level, after minimizing the maximum load of the connection, bottlenecks are identified via a discovery loop.

  1. With each iteration of the loop, the load on the data throughput is minimized over all connections that are under maximum load and represent potential bottlenecks.
  2. Connections that are unable to keep their throughput at their maximum are removed from the candidate path list.
  3. The bottleneck detection process stops when no more connections can be removed because the best path is now known.

See also

Individual evidence

  1. ↑ Min Chen, Yiming Miao, Iztok Humar: OPNET IoT Simulation . ISBN 978-981-3291-70-6 , pp. 468 .
  2. ↑ Srinivasan Murali: Designing Reliable and Efficient Networks on Chips . ISBN 978-1-4020-9756-0 , pp. 164 .
  • S.-J. Lee, M. Gerla: Split Multipath Routing with Maximally Disjoint Paths in Ad Hoc Networks . In: Proc. ICC 2001 . tape 10 , June 2001, p. 3201-3205 , doi : 10.1109 / ICC.2001.937262 .
  • A. Nasipuri, R. Castaneda, SR Das: Performance of Multipath Routing for On-Demand Protocols in Mobile Ad Hoc Networks . In: Mobile Networks and Applications . tape 6 , August 2001, p. 339-349 , doi : 10.1023 / A: 1011426611520 .
  • MK Marina, SR Das: On-Demand Multi Path Distance Vector Routing in Ad Hoc Networks . In: Proc. ICNP 2001 . September 2001, p. 14-23 , doi : 10.1109 / ICNP.2001.992756 .
  • A. Tsirigos, ZJ Haas: Multipath Routing in the Presence of Frequent Topological Changes . In: IEEE Communications Magazine . tape 39 , no. 11 , November 2001, p. 132-138 , doi : 10.1109 / 35.965371 .
  • H. Lim, K. Xu, M. Gerla: TCP Performance over Multipath Routing in Mobile Ad Hoc Networks . In: Proc. ICC 2003 . tape 2 , May 2003, p. 1064-1068 , doi : 10.1109 / ICC.2003.1204520 .
  • A. Tsirigos, ZJ Haas: Analysis of Multipath Routing — Part I: The Effect on the Packet Delivery Ratio . In: IEEE Trans. Wireless Communications . tape 3 , no. 1 , January 2004, p. 138-146 , doi : 10.1109 / TWC.2003.821207 .
  • S. Card, F. Tims: Concurrent Multipath Routing & Transport in a Mobile Wireless Gateway . In: MILCOM 2004, www.critical.com . Monterey, California, USA 2004.
  • N. Kammenhuber: Traffic-Adaptive Routing . S. Chapter 6.2 "Related Work" ( tum.de [PDF]).

The network security improvements:

  • W. Lou, Y. Fang: A Multipath Routing Approach for Secure Data Delivery . In: Proc. MILCOM 2001 . tape 2 , October 2001, p. 1467-1473 , doi : 10.1109 / MILCOM.2001.986098 .
  • CK-L. Lee, X.-H. Lin, Y.-K. Kwok: A Multipath Ad Hoc Routing Approach to Combat Wireless Link Insecurity . In: Proc. ICC 2003 . tape 1 , May 2003, p. 448-452 , doi : 10.1109 / ICC.2003.1204217 .
  • S. Bouam and J. Ben-Othman: Data Security in Ad Hoc Networks Using Multipath Routing . In: Proc. PIMRC 2003 . tape 2 , September 2003, p. 1331-1335 , doi : 10.1109 / PIMRC.2003.1260329 .
  • P. Papadimitratos, ZJ Haas: Secure Data Transmission in Mobile Ad Hoc Networks . In: Proc. ACM WiSe 2003 . September 2003, p. 41-50 , doi : 10.1145 / 941311.941318 .
  • Zhi Li, Yu-Kwong Kwok: A New Multipath Routing Approach to Enhancing TCP Security in Ad Hoc Wireless Networks . In: Proc. ICPP workshops . June 2005, p. 372-379 , doi : 10.1109 / ICPPW.2005.11 .

Web links

  • Prof. Dijiang Huang's multipath routing bibliography: [1]