Subject: [multipathtcp] Path selection by routers

From: Iljitsch van Beijnum <[email-masked]>
Date: Wed, 27 May 2009 13:11:26 +0200

I want to preface this message with the statement that I don't think  
this is something that should be part of the BoF or a prospective  
working group _at_ _this_ _time_ for fear of biting off more than we  
can chew. Having said that, I think it's an important issue that we  
need to deal with at some point if we start work on multipath  
transports, and perhaps thinking ahead a bit will make joining these  
two parts together easier when the time comes.

I'm going to assume that certain routers can reach a given destination  
over more than one path. For instance, in OSPF you can use multiple  
paths if they have the same cost and in BGP you can use multiple paths  
if you've configured your router for this and certain path attributes  
are the same (this is vendor specific). In these cases, you'll see  
multiple entries for a given destination in the RIB and FIB and the  
forwarding engine has to pick one for each packet. The usual way to do  
this is by doing a hash over a bunch of header fields (often  
addresses, ports and protocol) and then sending all the packets in the  
same hash bucket over the same path to avoid reordering sessions [ECMP  
= equal cost multipath, RFC2992].

Ideally, a multipath transport would simply use a different value for  
one of the fields used in the ECMP hash and have a good chance that  
those packets will take a different path. Unfortunately, none of the  
fields used for this are modifyable in transit. In IPv6 there is a  
chance that ECMP will look at the addresses and flow label rather than  
port numbers, but I haven't heard of any implementations that actually  
do this. The flow label is supposed to stay the same for a session but  
I think we can deviate from that without too much trouble.

In any event, just influencing ECMP is probably not sufficient for our  
purposes. A better solution would be to have an explicit path selector  
field in packets, where the path selector value directly maps to a  
path. First question: what if two or more routers look at the path  
selector? Would that be suboptimal if we use a single path selector,  
do we need to have multiple, possibly one for every hop? Wouldn't that  
make the path selector field too large, the processing too complex,  
the number of paths too large to probe? But the situation where one  
flipped bit means that 10 routers all change their path selection  
seems suboptimal, too. Also, what if we wrap around? I.e., path  
selector says path 4 but there are only 3. If only one router looks at  
the value it can drop the packet and the host won't try to use the  
path anymore after one or more additional attempts, if multiple  
routers look at the value then the packet can't be dropped.

Another issue is where to put the path selector. The first question  
here is whether the path selector needs to be something that's visible  
end-to-end. If it's end-to-end the path selector must be unmodifyable  
in transit and in the IP or transport header. This means an option.  
Although not completely impossible, using IP options in IPv4 or IPv6  
is an uphill battle, where we expect many routers to drop packets with  
options. Not to mention firewalls and the destination hosts  
themselves. (Note though that in our case that is not immediately  
lethal as we always have the default path so failure just means no  
extra paths, not loss of connectivity.) TCP options on the other hand  
seem much more doable, although not entirely impervious to firewall  
breakage. But do we want routers to have to look this deep into packets?

On the other hand, having a path selector that is only valid in part  
of the network could be attractive. We could use the DSCP bits in this  
case. There are 64 combinations so that would allow for 8 traffic  
classes and 8 paths or some other combination, retaining the original  
DSCP use along with the new multipath use. It would even be possible  
to make incompatible changes to IP or link layers as long as those are  
negotiated between a host and a router or two routers that are both  
upgraded and the original IP headers are restored when the packet  
leaves the upgraded part of the network. This would even allow for  
true multipath routing protocols. For instance, BGP could be upgraded  
to send multiple paths to its neighbors and then the desired path can  
be selected with the path selector in packets.