< draft-kapoor-rtgwg-dynamic-multipath-routing-00.txt   draft-kapoor-rtgwg-dynamic-multipath-routing-01.txt >
Network Working Group F. Devetak Network Working Group F. Devetak
Internet-Draft S. Kapoor Internet-Draft S. Kapoor
Expires: September 14, 2017 Illinois Institute of Technology Expires: March 16, 2018 Illinois Institute of Technology
March 13, 2017 September 12, 2017
Dynamic MultiPath Routing Dynamic MultiPath Routing
draft-kapoor-rtgwg-dynamic-multipath-routing-00 draft-kapoor-rtgwg-dynamic-multipath-routing-01
Abstract Abstract
In this draft we consider dynamic multipath routing and introduce two In this draft we consider dynamic multipath routing and introduce two
methods that use additive increase and multiplicative decrease for methods that use additive increase and multiplicative decrease for
flow control, similar to TCP. Our first method allows for congestion flow control, similar to TCP. Our first method allows for congestion
control and re-routing flows as users join in or leave the network. control and re-routing flows as users join in or leave the network.
As the number of applications and services supported by the Internet As the number of applications and services supported by the Internet
grows, bandwidth requirements increase dramatically so it is grows, bandwidth requirements increase dramatically so it is
imperative to design methods to ensure not only that network imperative to design methods to ensure not only that network
skipping to change at page 1, line 34 skipping to change at page 1, line 34
provided by an enhanced routing protocol. provided by an enhanced routing protocol.
Status of This Memo Status of This Memo
This Internet-Draft is submitted in full conformance with the This Internet-Draft is submitted in full conformance with the
provisions of BCP 78 and BCP 79. provisions of BCP 78 and BCP 79.
Internet-Drafts are working documents of the Internet Engineering Internet-Drafts are working documents of the Internet Engineering
Task Force (IETF). Note that other groups may also distribute Task Force (IETF). Note that other groups may also distribute
working documents as Internet-Drafts. The list of current Internet- working documents as Internet-Drafts. The list of current Internet-
Drafts is at http://datatracker.ietf.org/drafts/current/. Drafts is at https://datatracker.ietf.org/drafts/current/.
Internet-Drafts are draft documents valid for a maximum of six months Internet-Drafts are draft documents valid for a maximum of six months
and may be updated, replaced, or obsoleted by other documents at any and may be updated, replaced, or obsoleted by other documents at any
time. It is inappropriate to use Internet-Drafts as reference time. It is inappropriate to use Internet-Drafts as reference
material or to cite them other than as "work in progress." material or to cite them other than as "work in progress."
This Internet-Draft will expire on September 14, 2017. This Internet-Draft will expire on March 16, 2018.
Copyright Notice Copyright Notice
Copyright (c) 2017 IETF Trust and the persons identified as the Copyright (c) 2017 IETF Trust and the persons identified as the
document authors. All rights reserved. document authors. All rights reserved.
This document is subject to BCP 78 and the IETF Trust's Legal This document is subject to BCP 78 and the IETF Trust's Legal
Provisions Relating to IETF Documents Provisions Relating to IETF Documents
(http://trustee.ietf.org/license-info) in effect on the date of (https://trustee.ietf.org/license-info) in effect on the date of
publication of this document. Please review these documents publication of this document. Please review these documents
carefully, as they describe your rights and restrictions with respect carefully, as they describe your rights and restrictions with respect
to this document. Code Components extracted from this document must to this document. Code Components extracted from this document must
include Simplified BSD License text as described in Section 4.e of include Simplified BSD License text as described in Section 4.e of
the Trust Legal Provisions and are provided without warranty as the Trust Legal Provisions and are provided without warranty as
described in the Simplified BSD License. described in the Simplified BSD License.
1. Introduction 1. Introduction
Internet packet traffic keeps growing as the number of applications Internet packet traffic keeps growing as the number of applications
skipping to change at page 7, line 5 skipping to change at page 7, line 5
Add new path to list Add new path to list
ENDIF ENDIF
Increment shortest path flow by a Increment shortest path flow by a
ENDIF ENDIF
ENDFOR ENDFOR
If the number of paths become excessive then they can be curtailed. If the number of paths become excessive then they can be curtailed.
At that stage no additional flow is pushed until congestion is At that stage no additional flow is pushed until congestion is
relieved. relieved.
4. Conclusion 4. Experiments
We implemented [1] a discrete time version of the two algorithms We implemented [1] the two algorithms using the NS-3 simulation
using the NS-3 simulation environment. We modeled the network environment. We modeled the network topology on the network of a
topology on the network of a large service provider, with link large service provider, with link capacities proportional to
capacities proportional to capacities in the actual physical network. capacities in the actual physical network. In our implementation we
In our implementation we used, for routing, a combination of link- used, for routing, a combination of link-state routing protocol and
state routing protocol and source routing. For the link-state part source routing. For the link-state part we augmented the NS-3
we augmented the NS-3 implementation of the OSPF routing protocol by implementation of the OSPF routing protocol by adding link queue
adding link queue occupancy to the data exchanged by nodes in Link occupancy to the data exchanged by nodes in Link State Advertisement
State Advertisement (LSA) messages, a minimal increase in LSA data. (LSA) messages, a minimal increase in LSA data. That allows for more
That allows for more sophisticated monitoring of network status: if sophisticated monitoring of network status: if the queue occupancy
the queue occupancy for one of more links of a path exceeds a given for one of more links of a path exceeds a given threshold we conclude
threshold we conclude that the path is experiencing congestion and that the path is experiencing congestion and that the multiplicative
that the multiplicative decrease has to be applied to adjust the decrease has to be applied to adjust the allocation of flow to the
allocation of flow to the paths. The additive increase is applied at paths. The additive increase is applied at each iteration, if demand
each iteration, if demand is not met, to augment the sending rate. is not met, to augment the sending rate. Details of congestion
The source node uses OSPF to find the shortest path to the measurement are as follows: In a node-to-node connection (data link)
destination and, based on available network data, builds a source- both the source (originating) node and the sink (destination) node
routing vector that is inserted in the packet and used by have a PointToPointNetDevice. The PointToPointNetDevice at the
originating node is associated with a queue function of type
DropTailQueue. The queue function stores the number of packets in
the queue (waiting to be sent to the destination node). A
queueOccupancy parameter is calculated: numPacketsInQueue/
queueMaxSize and compared to a queueThreshold parameter. If
queueOccupancy> queueThreshold the path that uses the data link is
flagged as congested. queueThreshold is an input parameter declared
at the start of the simulation. At the same time path delay is also
calculated. The source node uses OSPF to find the shortest path to
the destination and, based on available network data, builds a
source-routing vector that is inserted in the packet and used by
intermediate nodes to route the packet to the destination. To intermediate nodes to route the packet to the destination. To
implement the source-routing function we augmented the NS-3 Nix- implement the source-routing function we augmented the NS-3 Nix-
Vector protocol that builds the source-routing vector from the list Vector protocol that builds the source-routing vector from the list
of nodes to be traversed, list that is obtained from OSPF. The main of nodes to be traversed, list that is obtained from OSPF. The main
process is iterative as we refresh LSA at a fixed interval: for our process is iterative as we refresh LSA at a fixed interval: for our
simulations we experimented with updating LSAs every 50 ms and 500 simulations we experimented with updating LSAs every 50 ms and 500
ms. ms.
Our results for the throughput improvement are presented below and
compared with throughput results for the standard TCP and TCP using
ECMP. We show the average throughput over multiple runs.
|------------------------------------------------------------|
|No of Commodities | TCP | TCPw ECMP | DMP |DMP/Fairness|
|------------------------------------------------------------|
| 5 | 4008 | 3330 | 7949 | 4139 |
|------------------------------------------------------------|
| 10 | 3275 | 2966 | 6017 | 5612 |
|------------------------------------------------------------|
| 15 | 2849 | 2715 | 5373 | 5090 |
|------------------------------------------------------------|
| 20 | 2912 | 2582 | 4633 | 3703 |
|------------------------------------------------------------|
5. Conclusion
In conclusion we found that our algorithm with fairness provides In conclusion we found that our algorithm with fairness provides
throughput improvement over both regular TCP and TCP with ECMP. In throughput improvement over both regular TCP and TCP with ECMP. In
addition, its ability to discover additional path dynamically addition, its ability to discover additional path dynamically
eliminates the need to set a preselected set of paths, allowing the eliminates the need to set a preselected set of paths, allowing the
spreading of the traffic load amongst a wider but still reasonable spreading of the traffic load amongst a wider but still reasonable
set of paths. The results may be found at set of paths. Further results may be found at
www.cs.iit.edu/~kapoor/papers/reducerate.pdf . www.cs.iit.edu/~kapoor/papers/reducerate.pdf .
5. References 6. References
5.1. References 6.1. References
[M75] Maxemchuk, N., "Dispersity Routing", IEEE ICC, 1975. [AP13] Amer, P. and F. Pang, "Non-renegable selective
acknowledgments (nr-sacks) for mptcp.", Proceedings of the
2013 27th International Conference on Advanced Information
Networking and Applications Workshops , 2013.
[CRS99] Cidon, I., Rom, R., and Y. Shavitt, "Analysis of multi- [CRS99] Cidon, I., Rom, R., and Y. Shavitt, "Analysis of multi-
path routing", IEEE/ACM Trans on Networking pages 885-896, path routing", IEEE/ACM Trans on Networking pages 885-896,
1999. 1999.
[ST92] Suzuki, H. and F. Tobagi, "Fast bandwidth reservation with
multiline and multipath routing in atm networks",
Proceedings of IEEE Infocom pages 2233-2240, 1992.
[DSAK11] Devetak, F., Shin, J., Anjali, T., and S. Kapoor, [DSAK11] Devetak, F., Shin, J., Anjali, T., and S. Kapoor,
"Minimizing path delay in multipath networks", IEEE ICC, "Minimizing path delay in multipath networks", IEEE ICC,
2011. 2011.
[SKDA13] Devetak, F., Anjali, T., Shin, J., and S. Kapoor, [GWH11] Greenhalgh, A., Wischik, D., Handley, M., and C. Raiciu,
"Concurrent multipath routing over bounded paths: "Design, implementation and evaluation of congestion
Minimizing delay variance", Globecom 2013 , 2013. control for multipath tcp.", 8th USENIX conference on
Networked systems design and implementation , 2011.
[M05] Internet Engineering Task Force, "Coupled congestion
control for multipath transport protocols", RFC 6356 ,
2011.
[M06] Internet Engineering Task Force, "Multipath tcp (mptcp)
application interface considerations", RFC 6897 , 2013.
[M07] Internet Engineering Task Force, "Tcp extensions for
multipath operation with multiple addresses", RFC 6824 ,
2013.
[M08] Internet Engineering Task Force, "Architectural guidelines
for multipath tcp development", RFC 6182 , 2011.
[M75] Maxemchuk, N., "Dispersity Routing", IEEE ICC, 1975.
[PU12] Popovic, M., Upadhyay, U., Le Boudec, J., Khalili, R., and [PU12] Popovic, M., Upadhyay, U., Le Boudec, J., Khalili, R., and
N. Gast, "Mptcp is not pareto-optimal: performance issues N. Gast, "Mptcp is not pareto-optimal: performance issues
and a possible solution", Proceedings of the 8th and a possible solution", Proceedings of the 8th
international conference on Emerging networking international conference on Emerging networking
experiments and technologies , 2012. experiments and technologies , 2012.
[RG10] Barre, S., Greenhalgh, A., Wischik, D., Handley, M., [RG10] Barre, S., Greenhalgh, A., Wischik, D., Handley, M.,
Raiciu, C., and C. Pluntke, "Data center networking with Raiciu, C., and C. Pluntke, "Data center networking with
multipath tcp.", 9th ACM SIGCOMM , 2010. multipath tcp.", 9th ACM SIGCOMM , 2010.
[GWH11] Greenhalgh, A., Wischik, D., Handley, M., and C. Raiciu,
"Design, implementation and evaluation of congestion
control for multipath tcp.", 8th USENIX conference on
Networked systems design and implementation , 2011.
[RH10] Raiciu, C., Handley, M., Barre, S., and O. Bonaventure, [RH10] Raiciu, C., Handley, M., Barre, S., and O. Bonaventure,
"Experimenting with multipath tcp.", Proceedings of the "Experimenting with multipath tcp.", Proceedings of the
ACM SIGCOMM 2010 conference , 2010. ACM SIGCOMM 2010 conference , 2010.
[AP13] Amer, P. and F. Pang, "Non-renegable selective [SKDA13] Devetak, F., Anjali, T., Shin, J., and S. Kapoor,
acknowledgments (nr-sacks) for mptcp.", Proceedings of the "Concurrent multipath routing over bounded paths:
2013 27th International Conference on Advanced Information Minimizing delay variance", Globecom 2013 , 2013.
Networking and Applications Workshops , 2013.
[M05] Internet Engineering Task Force, , "Coupled congestion
control for multipath transport protocols", RFC 6356 ,
2011.
[M06] Internet Engineering Task Force, , "Multipath tcp (mptcp)
application interface considerations", RFC 6897 , 2013.
[M07] Internet Engineering Task Force, , "Tcp extensions for
multipath operation with multiple addresses", RFC 6824 ,
2013.
[M08] Internet Engineering Task Force, , "Architectural [ST92] Suzuki, H. and F. Tobagi, "Fast bandwidth reservation with
guidelines for multipath tcp development", RFC 6182 , multiline and multipath routing in atm networks",
2011. Proceedings of IEEE Infocom pages 2233-2240, 1992.
5.2. URIs 6.2. URIs
[1] http:www.cs.iit.edu/~kapoor/papers/reducerate.pdf [1] http:www.cs.iit.edu/~kapoor/papers/reducerate.pdf
Authors' Addresses Authors' Addresses
Fabrizio Devetak Fabrizio Devetak
Illinois Institute of Technology Illinois Institute of Technology
10W 31 Street 10W 31 Street
Stuart Building Stuart Building
Chicago, IL 60565 Chicago, IL 60565
 End of changes. 18 change blocks. 
60 lines changed or deleted 88 lines changed or added

This html diff was produced by rfcdiff 1.45. The latest version is available from http://tools.ietf.org/tools/rfcdiff/