Lecture Notes #6

Lecture Notes #6

CMPT 408/765 – Sep 30, 2009 & Oct 2, 2009

Taken by: Yvonne Cheng

IntServ (Integrated Service)

Properties of intServ are as follow:

ü  Provide per flow guarantees

ü  Provider has to keep the state of each flow

ü  Resource reservation: reserve bandwidth along the path

Note: For resource reservation, the provider needs to define a path and reserve bandwidth along the path.

Problems

1.  It may give poor utilization since the expected data flow may not be there all the time

2.  It is not very resilient towards faults. If one link of the path is broken, the provider needs to do everything from scratch again (e.g. identify another feasible path, bookkeeping the path, reserving resources, etc)

3.  It does not scale very well. If there are lots of connections, the cost for overhead and bookkeeping will be very high.

4.  It may be theoretically hard to solve (most problems NP Hard).

Observation

ü  IntServ is desireable for user, but is very hard to implement and maintain.

ü  RSVP is mostly IntServ. It defines signalling scheme for making reservations along the path, but it doesn’t talk about how to find a path.

QoS (Quality of Service) Routing

We want to do reservations and also need to define carefully how to choose a path.

Goal: To find a path from s to t, which satisfies certain properties.

For example: find the shortest path from s to t. The cost is O(m log n) if we use Dijkstra algorithm.

Example 1:

We like to find the least cost path from s to t that there is b bandwidth along the path.

G = (V, E) where |V| = n, |E| = m

For each edge e in E,

b (e): bandwidth of e

w (e): cost of e

Note: Certain link will have more value/weight than the others since it has greater effects if it is broken.

Goal: Find a path P, from s to t, such that the available bandwidth is greater than or equal to b along P, and the cost of P is at low as possible.

More Formally Goal: Find minimum cost path P

Subject to

Solution: Go over all edges, remove all e such that

Run Dijkstra over the new graph using as weights.

(Note: is weight function)

Cost: Go over all edges takes.

Run Dijkstra algorithm takes

Therefore, the total cost is + =

Example 2:

Consider another example here.

where ,

For all edges ,

: delay of e

: cost of e

Goal: Find a path P, from s to t, such that the end-to-end delay is at most 50 ms (or D) and P is as low as possible.

More Formally Goal: Find minimum cost path P such that

(or )

Decompose:

ü  Find minimum cost path: It takes

ü  Find a path of delay: Returns the lowest delay path if the delay. If the lowest delay path, then there is no satisfying solution exist. If we run Dijkstra and use d as weight, it takes.

Analysis:

Although the 2 components Q are easy, but the combined problem is NP-Complete (or NP-Hard). The combinations of the 2 components can have exponential paths.

The alternative is to use approximation method.

Before that, let’s take a look on parameters and explore the parameter types which can make the problems to be hard.

Parameter Analysis

Why are some parameters intrinsically harder?

How do we go from per-link parameters to path constraint (i.e. end-to-end constraints)?

Let’s take a look on types of parameters:

ü  Class of bottleneck parameters:

Ø  It can be done by having some pre-processing using the result to reconstruct a smaller graph

Ø  For example: bandwidth. We might need to look for:

ü  Additive parameters

Ø  For example: jitter.

Ø  For example, we might look for delay d of a path P:

ü  Multiplicative parameters

Ø  For example, we might want to compute a success probability r:

Note:

Additive parameters and multiplicative parameters are similar since we can have the following formula:

In order to minimize , we can minimize , which is the same as minimize each .

By the way, always consider the worst case when we compute parameter problems.

After understanding the parameters, let’s look at some problems with two additive parameters and solved by dynamic programming (DP).

Dynamic Programming (DP)

We need to know what is dynamic programming first.

Dynamic Programming

What is a dynamic programming formulation?

It takes the solutions of smaller version of the problem to solve a bigger version of the problem later.

Comparing to recursion, recursive solutions sometimes are waste since it repeats solving the smaller instances. By using DP, we can avoid the problem.

For example, let’s consider shortest path problem.

The dynamic programming formula for shortest path: for any node, find the best path to all its neighbors. From that point, we pick the best choice of previous node. We assume local optimization will lead us to global optimization.

Dijkstra is an implicit form of dynamic programming.

Cost Delay: DP Formulation

Let’s consider an example with two additive parameters here:

where ,

For all edges ,

: delay of e

: cost of e

(Note: It is bad to have negative delay. If there is a link in loop with negative delay, looping in the loop infinitely will lead to lowest cost.)

: The minimum cost for going from s to v with delay (at most d).

Objective: For a given D, we want to find and also the path.

Base Cases:

for (for all d and all v)

for (There is no path with 0 cost delay for all v when v is not s)

Inductive Steps:

We are going to write a table containing for and

Note:

The optimal solution is same as the “Objective”, but the feasible solution needs to change the Objective to “Find any path from s to t with delay” in order to solve the problem.

When D is increased to 2D, more paths are included (i.e. include paths with delays from D to 2D). There are more paths to explore, and as a result we may find a better solution. When there is less constraint, the problem is easier.

Feasible Solution:

We are trying to find here.

Assume triangle inequality property is preserved on delay and cost.

Let,

Let,

Let,

For node u, we need where

There are 3 feasible solutions:

= +

= +

= +

Þ  We will take the minimum of the 3 as solution.

Due to the triangle inequality property is preserved, the other solutions cannot be better. Any path not going through u or v or w cannot be better.

Example 1

We want to find a path from s to t with delay ≤ 6

We can get from s Þ t Þ w.

Note that we don’t have. In order to get, we need and. However, we do not have since we knowfrom base cases.

Example 2

We want to find

In order to get, we need and.

However and, and therefore which means there is no feasible solution.

Base Case:

2.