5th International ICST Conference on Broadband Communications, Networks, and Systems

Research Article

Routelet Placement for Multipath Transport

  • @INPROCEEDINGS{10.1109/BROADNETS.2008.4769159,
        author={Mihaela Enachescu and Ravi Kokku},
        title={Routelet Placement for Multipath Transport},
        proceedings={5th International ICST Conference on Broadband Communications, Networks, and Systems},
        keywords={Multipath Node Placement Linear Programming Rounding Algorithms Edge Services Network Utilization Path Diversity},
  • Mihaela Enachescu
    Ravi Kokku
    Year: 2010
    Routelet Placement for Multipath Transport
    DOI: 10.1109/BROADNETS.2008.4769159
Mihaela Enachescu1,*, Ravi Kokku2,*
  • 1: Stanford University Stanford, CA
  • 2: NEC Laboratories America Princeton, NJ
*Contact email: mihaela@cs.stanford.edu, ravik@nec-labs.com


In this paper, we address the placement of relay service agents (routelets) in the Internet to assist multipath transport protocols; these protocols are designed to achieve better network utilization and fairness by exploiting path diversity in the Internet. We identify three different routelet deployment scenarios, provide LP formulations for routelet placement in each of the scenarios, and prove that the placement problem is NP-hard in two of the scenarios. We provide rounding algorithms with provable properties for a subset of the scenarios, and compare their performance through simulations on several BRITE topologies of varying scales. We observe that our rounding algorithm leads to a 2-5 fold increase in bandwidth utilization compared to the default single path routing. This closely matches the performance of the optimal LP throughput in the several topologies tested.