In the traditional IP scheme, both the packet forwarding and the routing protocols are source invariant, i.e., their decisions depend on the destination IP address and not on the source address. Recent protocols, such as MPLS, as well as traditional circuit based protocols like PNNI allow routing decisions to depend both on the source and destination addresses. In fact, much of the theoretical work on routing assumes per-flow forwarding and routing, i.e., the forwarding decision is based both on the source and destination addresses.
The benefit of per-flow forwarding is well-accepted, so is the practical implications of its deployment. Nevertheless, no quantitative study has been carried on the performance differences between the two approaches.
This work aims at investigating the toll in terms of performance
degradation that is incurred by source invariant schemes, as opposed
to the per-flow alternatives. We show, both theoretically and by
simulations, that source invariant routing can be significantly worse
than per-flow routing. Realizing that static shortest path algorithms
are not optimal even among the source invariant routing algorithms,
we develop novel routing algorithms that are based on dynamic weights, and
empirically study their performance in an Internet like environment.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-17.ps.gz
DIMACS Home Page