Show simple item record

dc.contributor.authorGao, Ruomeien_US
dc.contributor.authorDovrolis, Constantinos
dc.contributor.authorZegura, Ellen W.
dc.date.accessioned2005-06-17T17:34:29Z
dc.date.available2005-06-17T17:34:29Z
dc.date.issued2005en_US
dc.identifier.urihttp://hdl.handle.net/1853/6479
dc.description.abstractIn Interdomain Ingress Traffic Engineering (INITE), a "target" Autonomous System (AS) aims to control the ingress link through which the traffic of one or more upstream source networks flows to the target network or to its customers. Currently, there are few methodologies for systematic INITE. In practice, ISPs often attempt to manipulate, mostly in a trial-and-error manner, the AS-Path length attribute of upstream routes through a simple technique known as prepending (or padding). In this paper, we focus on prepending and propose a polynomial-time algorithm (referred to as OPV) that determines the optimal padding for an upstream route at each ingress link of the target network. Specifically given a set of "elephant" source networks for a particular customer of the target network, and a set of maximum load constraints on the ingress links of the latter, OPV determines the minimum padding at each ingress link so that the load constraints are met, when it is feasible to do so. OPV requires as input an AS-Path length estimate from each source to each ingress link. We describe how to estimate this matrix, leveraging the BGP Looking Glass Servers that are abundant today for monitoring interdomain routing. To deal with unavoidable inaccuracies in the AS-Path length estimates, and also to compensate for the generally unknown BGP tie-breaking process in upstream networks, we develop a robust variation (RPV) of the OPV algorithm. We show that RPV manages to identify a padding vector that meets the given maximum load constraints, when it is feasible to do so, even in the presence of inaccurate AS-Path lengths and unknown BGP tie-breaking behavior.en_US
dc.format.extent448627 bytes
dc.format.mimetypeapplication/pdf
dc.language.isoen_US
dc.publisherGeorgia Institute of Technologyen_US
dc.relation.ispartofseriesCC Technical Report; GIT-CC-05-02en_US
dc.subjectInterdomain Ingress Traffic Engineering (INITE)
dc.subjectAutonomous-system (AS) level Internet topology
dc.subjectPrepending
dc.subjectPolynomial time algorithms
dc.titleInterdomain Ingress Traffic Engineering through Optimized AS-Path Prependingen_US
dc.typeTechnical Reporteng_US


Files in this item

Thumbnail

This item appears in the following Collection(s)

Show simple item record