Towards Optimal Prepending for Incoming Traffic Engineering

One of the main concerns for an Internet Service Provider (ISP) is to optimize the distribution of network traffic among its upstream providers, for example to balance bandwidth usage, or to distribute link costs evenly. While outgoing traffic can be easily controlled, influencing the volumes of incoming traffic is more challenging. An effective and widely used technique to influence the distribution of incoming traffic is AS-path prepending, which consists in artificially inflating the length of the AS-path of BGP announcements. Since shorter AS-paths are often preferred, this can force incoming traffic to use different links. ISPs usually search for the optimal amount of prepending on a trial-and-error basis. In this work, we formulate the problem of finding the optimal amount of prepending as an Integer Linear Programming problem, which permits to consider several optimality criteria and to embody many constraints. We also show how efficient algorithms for the problem can be devised by considering it from a Computational Geometry perspective. We believe that, under reasonable assumptions, this theoretic approach can have interesting practical impacts.