1 Achieving Near-Optimal Traffic Engineering Solutions for Current OSPF/IS-IS Networks Ashwin Sridharan,Roch Gu´e rin,Christophe Diot
ashwin,guerin@ee.upenn.edu,christophe.
Abstract—Traffic engineering aims to distribute traffic so as to“optimize”some performance criterion.This optimal distribution of traffic depends on both the routing protocol and the forwarding mechanisms in u in the network.In IP networks running the OSPF or IS-IS protocols,routing is over shortest paths,and forwarding mechanisms distribute traffic“uniformly”over equal cost shortest paths.The constraints often make achieving an optimal distribution of traffic impossible.In this paper, we propo and evaluate an approach that can realize near optimal traffic distribution without changes to routing protocols and forwarding mechanisms.In addition,we explore the trade-off that exists between performance and the configuration overhead that our solution requires.The paper’s contributions are in formulating and evaluating an approach to traffic engineering in IP networks that achieves near-optimal performance while prerving the existing infrastructure.
怎么用气息唱歌Index Terms—Routing,Networks,Traffic Engineering, Aggregation.
I.I NTRODUCTION
As the amount and criticality of data being carried on IP networks grows,managing network resources to ensure reliable and acceptable performance be-comes increasingly important.Furthermore,this should be accomplished while minimizing or defer-ring costly upgrades.One of the techniques that is being evaluated by many Internet Service Providers to achieve this goal is traffic engineering.Traf-fic engineering us information about the traffic entering and leaving the network to generate a routing scheme that optimizes network performance. Most often the output of traffic engineering is an “optimal”t of paths and link loads that produce the best possible performance given the available resources.However,explicitly tting up such paths Dept.of Elec.Eng.,Univ.of Pennsylvania,Philadelphia,PA19104. Intel Rearch,Cambridge,UK
The work of A.Sridharan and R.Gu´e rin was supported in part by NSF Grant ANI-9902943and(optimally)assigning traffic to them,typically calls for changes to both the routing protocols and the forwarding mechanism they rely , through the introduction of new technology such as MPLS[15].
Currently,two of the most widely ud Interior Gateway routing protocols are OSPF[14]and IS-IS[4],and devising solutions that allow the protocols to emulate“optimal routing,”is therefore desirable.There are two main difficulties in doing so.Thefirst is that the protocols u shortest path
routing with destination bad forwarding.The cond is that when the protocols generate multiple equal cost paths or next hops for a given desti-nation routing prefix,the forwarding mechanism equally splits the corresponding traffic across them to balance the load.This“equal”splitting is an approximation that depends on the lection of which next hop to u for a given packet.This lection is bad either on the value(one for each possible next hop)of a hash function applied to the packet header(source and destination address and port numbers),or on the state of a simple round-robin scheme that cycles through the possible next hops.Although the latter option is occasionally ud and provides for a more even distribution of load across possible next hops,the former option is the more commonly ud in practice.This is becau it prerves packet ordering within aflow, and becau the large number offlows that modern routers handle results in a good approximation of equal splitting([5]).For simplicity,in the paper we assume that traffic is split in exactly equal fractions across equal cost next hops.敖丙漫画图片
The constraints impod by the u of both short-est path routing and equal splitting across equal cost paths make it difficult or even impossible to achieve optimal traffic engineering link loads.One of the first works to explore this issue was[7],where a local arch heuristic was propod for optimizing
2
OSPF weights assuming knowledge of the traffic matrix.[7]showed that in spite of the constraints, properly lecting OSPF weights could yield sig-nificant performance improvements.However,the paper also showed that for some topologies,per-formance could still differ substantially from the optimal solution.Subquently,a result from linear programming([2][Chap.17,Sec.17.2])was ud in[21]to prove that any t of routes can be converted into a t of shortest paths bad on some link weights that matches or improves upon the performance of the original t of routes.This establishes that the shortest path limitation is in itlf not a major hurdle.However,the result of [21]assumes forwarding decisions that are specific to each ingress-egress pair,and more importantly, the ability to split traffic in an arbitrary ratio over different shortest paths.Both of the assumptions are at odds with current IP forwarding mechanisms. Compatibility with destination bad forwarding can be achieved through a simple extension to the result of[21],simply by taking advantage of a property of shortest paths([17]),or by readjusting the program formulation itlf([1])1.Accommo-dating the constraint of uneven splitting of traffic across multiple shortest paths is a more challeng-ing task.It is typically not supported with the forwarding path implementations that accompany most routing protocols(some limited support is available with Cisco’s proprietary routing protocol EIGRP2).A new
protocol,OSPF-OMP,was pro-pod in[19]that circumvents this constraint by modifying the hash function in the router to allow unequal load balancing.However,this will require significant changes to the forwarding mechanisms in the router’s data path,which is typically not some-thing that can be accomplished through a simple software upgrade.
The solution we propo leverages the fact that prent day routers have thousands of route entries (destination routing prefixes)in their routing table. Instead of changing the forwarding mechanism re-sponsible for distributing traffic across equal cost paths,we plan to control the actual(sub)t of shortest paths(next hops)assigned to routing prefix entries in the forwarding table(s)of a router.In 1This is explained in detail in Section II-A
2Cisco’s specification of EIGRP allows unequal load balancing across shortest paths and her words,for each prefix we define a(sub)t of allowable next hops by carefully lecting this subt from the t of next hops corresponding to the shortest paths computed by the routing algorithm. This allows us to control how traffic is distributed without modifying routing protocols such as OSPF or IS-IS,and without requiring changes to the data path of current ,their forwarding mechanism.It does,however,require some changes to the control path of routers in order to allow the lective installment of next hops in the forwarding table.
Our initial focus is on gaining a better understand-ing of how well the lective installment of next hops for different routing prefixes can approximate an optimal traffic allocation(t of link loads). We show that this problem is NP-complete and hence one must resort to heuristics.Toward this end,we propo a simple local arch heuristic for implementing the solution.We obtain a bound on the gap between the heuristic and optimal allocation, and also demonstrate its efficacy through veral experiments.Even though we study the heuristic in the context of a routing problem,we believe that it is generic enough to be of potential u in other load balancing scenarios.The mainfinding from our investigation is that the performance achieved by this approach is esntially indistinguishable from the optimal.
This being said,an obvious drawback of“hand-crafting”the t of next hops that are to be installed for each routing prefix in a router’s forwarding table,is the configuration overhead it introduces. The potential magnitude(proportional to the size of the routing/forwarding table)of this overhead could make this approach impractical.As a result, our next step is to investigate a solution that can help mitigate this overhead,albeit at the cost of a possible degradation in performance.Specifically, we limit the number of routing prefixes for which we perform the propod lective installment of next hops.Our results indicate that a significant reduction in configuration overhead can be achieved without a major loss of performance.
The rest of the paper is structured as follows. Section II introduces the linear program formulation ud in[21]to generate an”optimal”t of shortest paths,and introduces the propod modifications to make it compatible with existing IP routers. Section III prents a heuristic for approximating
3 an optimal traffic distribution by manipulating the
t of next hops assigned to each routing prefix.A performance bound is also derived(e Appendix). Section IV prents veral experiments thatfirst establish the efficacy of the heuristic of Section III, and then explore the impact on performance of low-ering configuration overhead.Section V provides a brief summary of the paper’s contributions and outline directions for future work.
II.F ROM O PTIMAL R OUTING TO S HORTEST
P ATH R OUTING
In this ction,wefirst briefly review the clas-sic result from linear programming[2][Chap.17, Sec.17.2]that was cast in the context of routing in communication networks in[21]to show how optimal routing can be achieved using only shortest paths.We then discuss why this result is not directly usable in current IP networks,andfinally propo solutions that allow us to implement the result under the existing paradigm.
The network is modeled as a directed graph
with routers and
directed links.We assume the existence of a traffic matrix where entry denotes the average intensity of traffic entering the network at ingress router and exiting at egress router for commodity.A good reference on how to construct such a traffic matrix can be found in[6]. Assume that an optimal allocation bad on some network wide cost function yields a t of paths for each commodity(ingress-egress router pair),so that the total bandwidth consumed by the paths3on link is.It can be shown that the same performance,in terms of the bandwidth consumed on each link,can be achieved with a t of shortest paths by formulating and solving a linear program and its dual.The linear program can be formulated as([21]):
subject to
3The bandwidth consumed on a link is assumed to be the sum of the traffic on all paths that u the link
(1) where is the fraction of traffic for commodity thatflows through link.Solving the linear pro-gram gives a traffic allocation that consumes no more than amount of bandwidth on any link .Note that the formulation is not dependent on the original network cost function ud to ob-tain the paths.Instead it achieves the same performance by matching the desired bandwidths .In order to obtain link weights for shortest path routing,the dual of the linear program as formulated in[21]needs to be solved:
subject to
(2) The dual gives a t of link weights, from which a t of shortest paths can be con-structed.
It is however important to understand that al-though routing can now be done over shortest paths, this is still quite different from the forwarding paradigm currently deployed in existing OSPF and IS-IS networks.The reasons are two-fold and both can be traced to the output of the primal LP, Eqn.(1),namely,the traffic allocation.They govern the fraction of traffic forwarded on each next-hop.
Firstly,obrve that the traffic allocation is for each commodity or ingress-egress router pair.This means that the routing protocol could possibly gen-erate different t of next hops for each ingress-egress pair on which traffic is to be forwarded.This would impact the forwarding mechanism on the data path,as the router would need to make decisions on the basis of both ingress and egress router
s. Clearly,this is at odds with the current paradigm of destination-bad forwarding.
The cond problem relates to the fact that current forwarding mechanisms support only equal splitting of traffic on the t of equal cost next hops.The linear program yields a traffic allocation that is not guaranteed to obey this constraint.Modifying the
4 forwarding engine to support unequal splitting(e,红包做灯笼手工
for example,[19])of traffic would involve changes
to the data path,namely modification of the hash
function to allow for controllable hash boundaries. In the next two sub-ctions we suggest methods that overcome both the problems.
A.Destination Bad Aggregation of Traffic
Thefirst problem of translating a traffic alloca-tion that distinguishes between ingress-egress router pairs into one that only depends on egress point is relatively straightforward.It can be achieved simply by transforming the individual splitting ratios of ingress-egress pairs that share a common egr
ess router into a possibly different splitting ratio for the aggregate traffic associated with the common egress router.The reason this is possible is becau all chon routes are shortest paths.Shortest paths have the property that gments of shortest paths are also shortest paths,so that once twoflows headed to the same egress point meet at a common node they will subquently follow the same t of shortest paths. This means that we need not distinguish between the packets bad on their source address,and can make splitting and forwarding decisions simply bad on their destination address.
The aggregation offlows headed to a common egress could either be done after the optimal traffic allocation for each commodity has been computed (for example by the LP in Eqn.(1))or in the formulation of the linear program itlf.Thefirst method is prented in[17].The cond scheme was prented in[1]and illustrated below.Since traffic allocation is done bad only on the egress router,we can aggregate all commodityflow vari-ables headed toward a common egress point and then suitably modify the conrvation constraints.
莫泊桑读音A re-formulation of Eqn.(1)and Eqn.(2)in the destination aggregated form as prented in[1]is reproduced below.
The primal Linear Program is given by: subject to
otherwi where
(3) Note that the variables of the Primal,,repre-nt traffic on link headed toward egress router .Also,theflow conrvation constraints have been modified to accommodate the aggregation,where reprents all traffic headed toward destination .
The dual is given by:
subject to
(4) where reprents the right hand side array in theflow conrvation constraints of the primal,Eqn. (3),that is:
otherwi
and as before,still reprent link weights for shortest path computation.The above formu-lation is not only conformal to the paradigm of destination bad forwarding,but also reduces the number of variables by a factor of through removal of information regarding ingress-egress
router pairs.This greatly improves the computa-tion complexity involved in obtaining an optimal solution and will be ud henceforth throughout the remainder of the paper to compute the optimal traffic allocation and link weights.
B.Approximating Unequal Split of Traffic
In the previous sub-ction,we saw that solving the problem of source-destination bad forwarding decisions was relatively straightforward.Unfortu-nately,the same does not hold for the uneven
5
splitting issue,and as mentioned earlier providing such a capability is a significant departure from current operations.Our proposal to overcome this problem is to take advantage of the fact that today’s routing tables are relatively large,with multiple routing prefixes associated with the same egress router.By controlling the(sub)t of next hops that each routing prefix is allowed to u,we ca
n control the traffic headed toward a particular egress router(destination).In other words,instead of the current operation that has all routing prefixes u the full t of next hops,we propo to lectively control this choice bad on the amount of traffic associated with each routing prefix and the desired link loads for an optimal traffic allocation.
The following example illustrates the idea behind the approach.Assume that at some node,there are four routing prefixes,and that map to a common destination and have traffic intensities
and.Let there be three shortest paths associated with destina-tion,so that the routing table has3possible next hops to,and assume that the optimal distribution of traffic to the three next hops is
and.We can then intuitively match this traffic distribution by the following next hop assignment:
Hops1,3塌鼻子怎么办
Hop1
Hop3
Hop2
The resulting traffic distribution is
台本, which matches the optimal allocation.
The advantage of the above approach is that the forwarding mechanism on the data path remains unchanged,as packets are still distributed evenly over the t of next hops assigned to a routing prefix. This means that a clo approximation of an optimal traffic engineering solution might be feasible even in the context of existing routing and forwarding technologies.There are,however,a number of chal-lenges thatfirst need to be addresd.Thefirst is the need for traffic information at the granularity of a routing prefix entry instead of a destination(egress router).This in itlf is not an insurmountable task as most of the techniques currently ud to gather traffic ,router mechanisms’like Cisco’s Netflow or Juniper’s cflowd,can be readily adapted to yield information at the granularity of a routing prefix.
The cond issue concerns the configuration over-head involved in communicating to each router the subt of next hops to be ud for each routing pre-fix.This can clearly reprent a substantial amount of configuration data,as routing tables are large and the information that needs to be conveyed is typically different for each router.The approach we propo and study is to identify a sm
all t of prefixes for which careful allocation of next hops is done and rely on default behavior for the remaining prefixes.The trade-off will then be in terms of how clo one can get to an optimal traffic distribution,while configuring the smallest possible number of routing prefixes.We investigate this trade-off in Section IV,where wefind that near optimum performance can often be achieved by configuring only a small number of routes(routing prefixes).
The third and last challenge is to actually for-mulate a method for determining which subt of next hops to choo for each routing prefix in order to approximate an optimal allocation.The goal of any solution will be to minimize some metric that measures discrepancy between the optimal traf-fic allocation and the one achieved under equal-splitting constraints on any hop.In this work,we u the maximum load on any hop as a measure of performance,where the load on a hop is the ratio of the allocated traffic to the optimal traffic.Details regarding the u of another metric,the gap between optimal traffic and allocated traffic can be found in [17].
III.H EURISTIC FOR T RAFFIC S PLITTING Ideally,one should consider the problem of -lective next-hop allocation at the global level,that is,do a concurrent optimal assignment of next hops for each routing prefix at each node.However,even the single node allocation problem is NP-complete4, and hence may not be computationally tractable. Conquently,we propo heuristics that perform in
dependent computations for each routing prefix at each node.The computations are bad only on the incoming traffic at the node and the desired outgoing traffic profile.A potential problem with this approach is that the traffic arriving at a node 4See Appendix for proof.
6
may not match the optimal profile due to the heuris-tic decisions at some upstream node.Conquently, the profile of the outgoing traffic from the node in question,could further deviate from the desired one.However,in our experiments we obrve that usually the heuristic is able to track the optimal load profile and hence incoming traffic en at any node and the resultant outgoing traffic have a near-optimal profile.We have propod three heuristics that are greedy in nature and try to minimize one of the two metrics mentioned in Section II-B.Since the heuristics are similar in nature,we shall limit our discussion to only one of them,namely the MIN-MAX LOAD heuristic,becau in all our ex-periments,this heuristic performed the best.Details regarding the other two heuristics can be obtained from[17].
The heuristic we propo works broadly in the following fashion.When performing computation at an arbitrary node
1)Sort routing prefixes destined to a particular
egress router in decreasing order of traffic
intensity,
2)Sequentially assign each routing prefix to a
subt of next hops so as to minimize the
given metric.
For clarity we u the following notation in our subquent discussion:
At an arbitrary node,when assigning routing prefixes associated with an arbitrary egress router (destination)to next hops:
1)Denote the t of next hops to egress router
by.
2)Denote the desired(optimal)traffic load(for
天色已晚egress router)on hop by. 3)Denote the traffic intensity of routing prefix
by.Denote the collective t of the routing
prefixes(at for)that need to be assigned
to next hops by.Let.
4)Denote the traffic load on hop after heuris-
tic has assigned routing prefixes by.
Assume for.
A.The MIN-MAX LOAD heuristic
The Min-Max Load heuristic is similar to a work conrving scheduling algorithm which tries to minimize the maximum load on any processor (the maximum makespan,[10]).Heuristic MIN-MAX LOAD tries to minimize the maximum ratio of assigned traffic to the optimal traffic load over all hops.The difference now is that each task(stream) can be split equally among multiple processors (n
ext hops)and the processors(next hops)can have different speeds(optimal traffic loads). Algorithm MIN-MAX LOAD:
1)Sort the t of prefixes in descending
order of traffic intensity.千分之一是零点几
2)For each prefix choo a subt of
next hops,with cardinality
which minimizes
Step2)can be achieved in two stages.First,for each index,do a virtual assign-ment of routing prefix to a t of hops which yields the smallest maximum.This can be done by
simply sorting the t
