[sip-comm-dev] GSoC 09 - Filtergraph


#1

Hi,
here is my progress report.

So far I have been working on finding path between formats using chain
of codecs. I have decided to do the filter graph builder from scratch
(sometimes getting inspiration from current version) and I have
already completed depth-first search and breadth-first search that are
in most cases able to find correct and (with breadth-first search)
also minimal path (there are cases in which negotiation of format is
needed and that is not handled yet). The speed of the search of course
depends on depth of shortest possible path, but on the whole is good
if up to 4 codecs has to be used, for 5 it is acceptable, but above 5
it just takes too long (I don't think there are any paths that would
require 6 or more codecs currently, I only tested on cases where path
could not be found due to negotiation of codecs). Speed will also be
addressed after negotiation is implemented, by adding a heuristic
function that will evaluate fitness of given codec considering initial
and final format and current format - creating best-first search that
would first try codecs with highest fitness factor.
I have also created test cases that evaluate the results and runtime
of both algorithms. After best-first search is implemented also tests
for it should be added that would compare how long it took to find
with depth-first vs. best-first. And of course the test should verify
if the same codec chain resulted from the search.
I am starting working on negotiation now and I also would like to do
some cleanup on the code. It shouldn't take too long and I can start
working on the evaluation function for fitness of codec.

···

--
Cheers, Martin Harvan
----
web:http://kane.sk
icq: 265 634 317
jabber: martinhrvn@gmail.com
Rita Rudner - "I was a vegetarian until I started leaning toward the
sunlight." - http://www.brainyquote.com/quotes/authors/r/rita_rudner.html

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@sip-communicator.dev.java.net
For additional commands, e-mail: dev-help@sip-communicator.dev.java.net


#2

Hey Martin,

Thanks for the update! Glad to know you are making progress. I have a
few quick questions:

1. Do you have any numbers (even approximative) on the performance tests
you describe. What do "good speed", "acceptable" and "takes too long"
mean? An estimation or even an order of magnitude would be fine.

2. When you talk about four or five codecs do you mean finding a path
between two codecs from a total of four or five, or do you mean a path
with a length of four or five?

3. If you have a bit more time then I'd love to see a short explanation
of how the process works? How do you look for your path, which part is
the most time consuming?

Cheers
Emil

Martin Harvan wrote:

···

Hi,
here is my progress report.

So far I have been working on finding path between formats using chain
of codecs. I have decided to do the filter graph builder from scratch
(sometimes getting inspiration from current version) and I have
already completed depth-first search and breadth-first search that are
in most cases able to find correct and (with breadth-first search)
also minimal path (there are cases in which negotiation of format is
needed and that is not handled yet). The speed of the search of course
depends on depth of shortest possible path, but on the whole is good
if up to 4 codecs has to be used, for 5 it is acceptable, but above 5
it just takes too long (I don't think there are any paths that would
require 6 or more codecs currently, I only tested on cases where path
could not be found due to negotiation of codecs). Speed will also be
addressed after negotiation is implemented, by adding a heuristic
function that will evaluate fitness of given codec considering initial
and final format and current format - creating best-first search that
would first try codecs with highest fitness factor.
I have also created test cases that evaluate the results and runtime
of both algorithms. After best-first search is implemented also tests
for it should be added that would compare how long it took to find
with depth-first vs. best-first. And of course the test should verify
if the same codec chain resulted from the search.
I am starting working on negotiation now and I also would like to do
some cleanup on the code. It shouldn't take too long and I can start
working on the evaluation function for fitness of codec.

--
Emil Ivov, Ph.D. 67000 Strasbourg,
Project Lead France
SIP Communicator
emcho@sip-communicator.org PHONE: +33.1.77.62.43.30
http://sip-communicator.org FAX: +33.1.77.62.47.31

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@sip-communicator.dev.java.net
For additional commands, e-mail: dev-help@sip-communicator.dev.java.net


#3

Hi Emil,

Hey Martin,

Thanks for the update! Glad to know you are making progress. I have a
few quick questions:

1. Do you have any numbers (even approximative) on the performance tests
you describe. What do "good speed", "acceptable" and "takes too long"
mean? An estimation or even an order of magnitude would be fine.

I attached log from current tests that shows from which format to
which format are the codecs searched, resulting chain of codecs and
time it took to find this path. Things to notice there - the first
part is for breadth-first search (first looking on all codecs that
accept the 'from' format and if none of their output formats is the
final format then continuing on all of codecs that accept their output
format) which due to its nature finds the minimal graph. The
depth-first search first goes as deep as it is permitted (this needs
to be limited, since in most cases it is possible to create infinite
chain of codecs) this fetches first found result, which in most cases
is not optimal (as you may see from the attached log). However if I
create the fitness evaluation method and use it with depth-first
search, the results should be a lot better (this would mean that
instead of taking codecs one by one from the array of codecs that
accept given format, the one with highest rating would be picked).

2. When you talk about four or five codecs do you mean finding a path
between two codecs from a total of four or five, or do you mean a path
with a length of four or five?

I was talking of path of length 4 or 5, of course. The search happens
among all of available codecs in FMJ. It would not be very impressive
if the search took this long with searching only among 5 codecs :slight_smile:

3. If you have a bit more time then I'd love to see a short explanation
of how the process works? How do you look for your path, which part is
the most time consuming?

The codecs can be thought of as tree where each codec has output
format (can have even more) that is accepted by one or more codecs. So
we get tree-like structure, where nodes are codecs and they have input
pin and output pin that connect to next codec (node).
The process works like this: First a list of codecs (that accep given
format as input format) is fetched. Then if the outputing format of
the given codec for the input format matches our destination format we
have our path, if not the search function is called recursively again
for each of codec's output formats, unless the current depth is
greater than max depth. This is a depth-first search. So in other
words, the whole depth of the tree (up to maximum depth that we allow)
is searched. If a path is found it is returned, if not we return
null). Breadth-first uses depth-first search to search at different
depths (from 1 to max depth) so while depth-first can (and most of the
time does) find non-optimal solutions, breadth-first finds optimal
solution, but depth-first with mentioned modifications can be faster.

filtergraph_log (74.4 KB)

···

On Wed, Jul 1, 2009 at 5:42 PM, Emil Ivov<emcho@sip-communicator.org> wrote:

--
Cheers, Martin Harvan
----
web:http://kane.sk
icq: 265 634 317
jabber: martinhrvn@gmail.com
Adrienne Gusoff - "Opportunity knocked. My doorman threw him out." -
http://www.brainyquote.com/quotes/authors/a/adrienne_gusoff.html


#4

Thanks for the extensive report Martin!

Emil

Martin Harvan wrote:

···

Hi Emil,

On Wed, Jul 1, 2009 at 5:42 PM, Emil Ivov<emcho@sip-communicator.org> wrote:

Hey Martin,

Thanks for the update! Glad to know you are making progress. I have a
few quick questions:

1. Do you have any numbers (even approximative) on the performance tests
you describe. What do "good speed", "acceptable" and "takes too long"
mean? An estimation or even an order of magnitude would be fine.

I attached log from current tests that shows from which format to
which format are the codecs searched, resulting chain of codecs and
time it took to find this path. Things to notice there - the first
part is for breadth-first search (first looking on all codecs that
accept the 'from' format and if none of their output formats is the
final format then continuing on all of codecs that accept their output
format) which due to its nature finds the minimal graph. The
depth-first search first goes as deep as it is permitted (this needs
to be limited, since in most cases it is possible to create infinite
chain of codecs) this fetches first found result, which in most cases
is not optimal (as you may see from the attached log). However if I
create the fitness evaluation method and use it with depth-first
search, the results should be a lot better (this would mean that
instead of taking codecs one by one from the array of codecs that
accept given format, the one with highest rating would be picked).

2. When you talk about four or five codecs do you mean finding a path
between two codecs from a total of four or five, or do you mean a path
with a length of four or five?

I was talking of path of length 4 or 5, of course. The search happens
among all of available codecs in FMJ. It would not be very impressive
if the search took this long with searching only among 5 codecs :slight_smile:

3. If you have a bit more time then I'd love to see a short explanation
of how the process works? How do you look for your path, which part is
the most time consuming?

The codecs can be thought of as tree where each codec has output
format (can have even more) that is accepted by one or more codecs. So
we get tree-like structure, where nodes are codecs and they have input
pin and output pin that connect to next codec (node).
The process works like this: First a list of codecs (that accep given
format as input format) is fetched. Then if the outputing format of
the given codec for the input format matches our destination format we
have our path, if not the search function is called recursively again
for each of codec's output formats, unless the current depth is
greater than max depth. This is a depth-first search. So in other
words, the whole depth of the tree (up to maximum depth that we allow)
is searched. If a path is found it is returned, if not we return
null). Breadth-first uses depth-first search to search at different
depths (from 1 to max depth) so while depth-first can (and most of the
time does) find non-optimal solutions, breadth-first finds optimal
solution, but depth-first with mentioned modifications can be faster.

------------------------------------------------------------------------

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@sip-communicator.dev.java.net
For additional commands, e-mail: dev-help@sip-communicator.dev.java.net

--
Emil Ivov, Ph.D. 67000 Strasbourg,
Project Lead France
SIP Communicator
emcho@sip-communicator.org PHONE: +33.1.77.62.43.30
http://sip-communicator.org FAX: +33.1.77.62.47.31

---------------------------------------------------------------------
To unsubscribe, e-mail: dev-unsubscribe@sip-communicator.dev.java.net
For additional commands, e-mail: dev-help@sip-communicator.dev.java.net