Unformatted text preview:

6 263 Data Communication Networks Application of Optimal Routing An Application of Optimal Routing MATE Multipath Adaptive Traffic Engineering 1 Shortest Path vs Optimal Routing Internet routing uses shortest path Why Shortest path is simple because it decouples congestion from routing Optimal routing Needs to know traffic demands between all OD pairs rw Needs to know the paths Paths and rw should be stable enough Should find a distributed version of the algorithm 3 What s Traffic Engineering ISPs are in the business of mapping traffic demands onto the underlying topology Good mapping removes hot spots and congestions The job of traffic engineering is to find a good mapping The mapping adapts to deal with changing network conditions i e congestion and failures How do you do it 4 2 We need to address multiple sub problems 1 2 3 Given an optimal routing X p force the traffic along the desired paths Find the optimal traffic split X p i e the optimal routing Split the traffic Traffic is not fluid it is packets and flows 5 Sub Problem 1 Given a balanced traffic split force the traffic along the desired paths Solution Ingress Egress Routing Agent An optimal routing agent per OD pair at ingress node Agent knows the paths between OD pair which are computed offline Paths are pinned using MPLS tunnels These are like virtual circuits discussed in lecture 1 6 3 Sub Problem 2 Find the optimal traffic splits X p Solution Define cost as delay in an M M 1 queue C Fij 1 Cij Fij Derivatives need to be measured Periodically send time stamped probe packets from ingress to egress and measure one way delay compute change in delay Also can incorporate losses in the cost function as very large delays Need to solve the optimization in a distributed way See the MATE paper in your reading list for a distributed approach 7 Sub Problem 3 Split traffic according to desired X p Solution Each flow should stick to one path because TCP reacts badly to packet reordering For each incoming packet hash src IP dst IP src port dst port to some large space use hash to assign packet to a specific bin Assign bins to paths according to X p 8 4 Outline Gradient and Hessian Descent algorithms Step size Convergence Constraints MIT Gradient and Hessian f x x 1 Gradient of some function f f x f x x n Descent direction 2 f x 2 f x x 1 x n x 1 2 Hessian 2 f x 2 f x 2 f x x n x 1 x n 2 Optimum point Convex function the Hessian is positive semidefinite and symmetric MIT 1 Positive semi definiteness Matrix A is positive semi definite if for any vector x xTAx 0 A symmetric matrix is positive semi definite iff all of its eigenvalues are positive non negative A square symmetric positive semi definite matrix has a symmetric square root Q such that Q2 A The inverse of a positive definite symmetric matrix is also symmetric and positive definite the eigenvalues of the inverse matrix are the inverses of the eigenvalues of the original matrix MIT Choice of step General set up x p k 1 x p k k B k D x k 1 We may vary the choices of B and Example steepest descent B I x p k 1 x p k k D x k 1 All vectors Other choices Newton s method MIT 2 Choice of step size Minimization rule choose k that minimizes along some direction dk D x k k d k min D x k d k 0 Armijo rule successive stepsize reduction Select a step size If the ensuing vector is not an improvement reduce the step size Need to do so in a way that is guaranteed to work fix s 0 1 0 1 pick mk to be smallest non negative m such that T D x k D x k m sd k m s D x k d k select k m s k MIT Convergence Convergence results exist for many of these systems The eigenvalues of the Hessian are often crucial in determining how different various directions are For a quadratic function method of steepest descent and chosen to minimize D at each step 2 D x k 1 D M m D x k D M m M is the largest eigenvalue of the Hessian m is the smallest eigenvalue of the Hessian For large spread in eigenvalues a large change in x may translate into small cost difference MIT 4 Convergence Proof relies on Kantorovich inequality 2 y y 4 Mm y Qy y Q y M m T T T 1 2 Q positive definite and symmetric y any non zero real vector Further results when the direction approaches the Newton method and the Armijo step size rule is followed for s 1 0 5 then convergence is super linear and for large enough k the step size is unity MIT What about our constraints All of these methods are concerned with reducing cost However we must also remain feasible F W maintained feasibility by restricting the step size to be of a type that maintained feasibility at the expense of flexibility and the ensuing speed of convergence Can we make use of the more sophisticated step size methods while maintaining feasibility Let us first consider a very simple example we need to maintain non negativity MIT 5 Optimizing over the positive orthant We consider a steepest descent method with the modification that we project onto the positive orthant x p k 1 x p k k D x k 1 Most of the methods carry through Let us transform our problem into a positive orthant problem We use the constraint to turn it into a new problem with no dependence on the MFDL paths MIT Optimizing over the positive orthant D F i j i j subject to the constraints F i j x p all paths p containing i j x p r w for al OD pairs w in W p in P w x p 0 we create x by expressing the MFDL paths in terms of the other path flows x p r w x p p p minimize D x s t x p 0 for p not MDFL MIT 6 Optimizing over the positive orthant When taking derivatives with respect to x p all terms with non MDFL x p originally in D remain but terms corresponding to a MDFL path now have terms in all the non MDFL path k x D x k D x k D for non MDFL p x p x p x p D x d recall D i j all paths p containing x p p i j x p all links i j on path p k 2 D x D i j x p H p links i j on path p all paths p containing i j x p 2 allor correspond ing MDFL but not both MIT Optimizing over the positive orthant Use the second …


View Full Document

MIT 6 263 - Application of Optimal Routing

Download Application of Optimal Routing
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Application of Optimal Routing and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Application of Optimal Routing 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?