Distributed out-bound load balancing in inter-AS routing by random matchings

    loading  Checking for direct PDF access through Ovid

Abstract

The Internet is composed of a collection of inter-connected and self-administered Autonomous Systems (ASms). Inter-AS routing is accomplished by having neighboring ASms exchange reachability information via the Border Gateway Protocol. An AS is said to be a transit AS if it allows traffic from other ASms to cross through it. In particular, transit ASms provide transit services for traffic between customer and provider ASms. In this article, we focus on maximizing the utilization of resources at transit ASms. In particular, inter-AS links have been shown to be a bottleneck. To make better use of inter-AS links, we consider the problem of balancing the load among inter-AS links. We refer to this problem as the Balanced-Flow Assignment ProbleM (B-FAPM). We show that the B-FAPM is NP-hard, and thus, likely intractable. We then present a heuristic protocol, the Balanced-Flow Assignment ProtocoL (B-FAPL), that balances the out-bound traffic loads on inter-AS links. We show via simulation that the B-FAPL effectively balances outgoing traffic over inter-AS links. Our solution is fully distributed and uses random matchings to assign in-bound flows to out-bound inter-AS links.

Related Topics

    loading  Loading Related Articles