• Status: Solved
• Priority: Medium
• Security: Public
• Views: 475

# flow deviation - principle

solving questions regarding "optimized flow" using Flow Deviation algorithm is very hard.
Is there any principle (something with derivatives, the lecturer said) which helps solving such questions more easily?
0
eimoah
• 2
1 Solution

Author Commented:
Adjusted points to 60
0

Commented:
consider a "penalty function h(f)" where h(f) is the penalty (as a function of the flow f in an edge) of putting flow on an edge.

suppose yuou have a source S and a destination D and you have two paths p1 and p2 in which you can route flow from S to D.

derivating the funciton h(f) by f we get dh/df.
let's sign L by dh/fd.

Lets say that f(i) is the flow in edge i and that L(i) is the new metric for the edge i (with respect to the penalty function).

Say that source S has a total of Z units of flow to route towards D, and we decide to route X of that flow through p1 and the rest Z-X of the flow via p2.

if you're asked what is the optimized routing of the flow such that the penalty is reduced to it's minimum then you'd have to solve the following equation:

sum all L(i)'s (where i represents every edge in path in path p1) and equate it with the sum of all L(j) (where j represents every edge in path in path p2).

solving that equation for X you find the optimized routing for our case.

Sorry for the complex explenation, but since I can't use math-notations with these fonts, it's hard to give you verbaly a general explenation.

you can email me at shlomoy@poboxes.com for more information.

0

Author Commented:
Thanks.
I think I've got it.
I hope you didn't mind gettinbg my emails.

0
Question has a verified solution.

Are you are experiencing a similar issue? Get a personalized answer when you ask a related question.

Have a better answer? Share it in a comment.

## Featured Post

• 2
Tackle projects and never again get stuck behind a technical roadblock.