Solving Inter-AS Bandwidth Guaranteed Provisioning Problems with Greedy Heuristics
Kin-Hon Ho, Ning Wang, George Pavlou · InTech eBooks · 2008
Advances in Greedy Algorithms 504 reachability information, each AS receives from adjacent downstream ASes a set of what we call bandwidth offers to designated remote AS destinations.If an AS decides to accept a bandwidth offer, an SLA is established between the two ASes.The AS can then in turn make bandwidth offers to its upstream (customer) ASes; these offers reflect both the AS' own resources and the SLAs established with the downstream ASes.The full set of SLAs enables all the ASes to support traffic with end-to-end bandwidth guarantees.However, the AS' tasks of making appropriate decisions on which bandwidth offers to accept, how much bandwidth to purchase and how to allocate the bandwidth among traffic aggregates are non-trivial.Inappropriate bandwidth offer selection or traffic assignment could result in respectively high cost or poor resource utilization.In order to obtain the best solutions, we propose a network dimensioning system that incorporates optimization modules that solve the two following problems: • how to determine an appropriate amount of bandwidth to be purchased from each bandwidth offer so that the total cost of the bandwidth is minimized; • given the knowledge of the available intra-AS bandwidth and the bandwidth purchased from downstream ASes, how to assign routes to the predicted traffic aggregates so that bandwidth demand is met while optimizing resource utilization.We call these two problems the Inter-AS Bandwidth Provisioning and Traffic Assignment problems respectively.Our proposed network dimensioning system enables ASes to move from trial-and-error to a systematic approach for provisioning their end-to-end bandwidth guarantees.More specifically, we propose two efficient greedy heuristics to solve these optimization problems.It has been a long history that greedy heuristics are used for solving network optimization problems, such as traffic engineering (Sridharan et al., 2005), multicast routing (Shi & Turner, 2002) etc.Nevertheless, the optimization problems of end-to-end bandwidth guarantees provisioning across multiple ASes has not been addressed until recently, and in this chapter we will illustrate how greedy heuristics can gracefully solve these novel problems.The main contributions of this chapter can be summarized as follows: •We propose a systematic network dimensioning system that can be used by ASes to achieve effective provisioning of end-to-end bandwidth guarantees.The network dimensioning system formulates two problems that respectively provide economic and engineering optimization, namely the inter-AS bandwidth provisioning and traffic assignment problems.•We show that a heuristic approach can be used to solve the inter-AS bandwidth provisioning problem.To illustrate this, we use an efficeint genetic algorithm embedded with two problem-specific greedy heuristics.Our proposed algorithm optimizes the bandwidth provisioning with 5%-30% and 75%-90% less cost than a conventional heuristic and a random-based algorithm respectively.•We use a greedy-penalty heuristic algorithm to solve the traffic assignment problem.The proposed greedy-penalty heuristic results in 10% less total bandwidth consumption than a random-based algorithm.