Cost efficient overflow routing for outbound ISP traffic

Multihomed Internet service providers (ISPs) are typically connected to several transit ISPs. If cost is assigned to interconnecting resources, multihomed ISPs face the problem of cost efficient outbound traffic routing. In particular, this is relevant if the ISPs form customer to provider relationships and alternative billing schemes are used, i.e. volume or time based. The border gateway protocol (BGP) is the de facto standard for inter-domain IP routing on the Internet but its traffic engineering capabilities are limited. This paper proposes a local overflow methodology that allows cost efficient outbound packet routing and is based on the scheme for alternative packet overflow routing (SAPOR). The paper identifies the underlying optimisation problem, introduces the modified SAPOR methodology and presents simulation results that verify the operation of the scheme.