the KshortestPaths Algorithm in ONOS has a bug

[sh.attarha]

Hello
I want to use Kshortestpath Algorithm in my project, but it has an exception and when i saw the karaf log it has problem in this line of kshortestpath algorithm

for(int k = 1; k < maxPaths; ++k) {
for(int i = 0; i < ((Path)resultPaths.get(k - 1)).edges().size() - 1; ++i) {
Vertex spurNode = ((Edge)((Path)resultPaths.get(k - 1)).edges().get(i)).src();
List rootPathEdgeList = ((Path)resultPaths.get(k - 1)).edges().subList(0, i);
Iterator spurPath = resultPaths.iterator();
and has problem by k ,
Can You please resolve this problem ?
Best Regards

[Thomas Vachuska]

Can you please post the entire exception stack trace?

Thomas

--
You received this message because you are subscribed to the Google Groups "ONOS Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to onos-dev+u...@onosproject.org.
To post to this group, send email to onos...@onosproject.org.
Visit this group at https://groups.google.com/a/onosproject.org/group/onos-dev/.
To view this discussion on the web visit https://groups.google.com/a/onosproject.org/d/msgid/onos-dev/29db6044-8bf6-4211-8cbb-79d82b0d42d1%40onosproject.org.

[ShaD Attarha]

I attach my topology that i use it,

thanks for your attention

On Tue, Oct 25, 2016 at 9:48 PM, Thomas Vachuska <t...@onlab.us> wrote:

Can you please post the entire exception stack trace?

Thomas

On Oct 25, 2016, at 1:47 AM, sh.attarha <sh.at...@gmail.com> wrote:

Hello
I want to use Kshortestpath Algorithm in my project, but it has an exception and when i saw the karaf log it has problem in this line of kshortestpath algorithm

for(int k = 1; k < maxPaths; ++k) {
               for(int i = 0; i < ((Path)resultPaths.get(k - 1)).edges().size() - 1; ++i) {
                   Vertex spurNode = ((Edge)((Path)resultPaths.get(k - 1)).edges().get(i)).src();
                   List rootPathEdgeList = ((Path)resultPaths.get(k - 1)).edges().subList(0, i);
                   Iterator spurPath = resultPaths.iterator();
and has problem by k ,
Can You please resolve this problem ?
Best Regards



--
You received this message because you are subscribed to the Google Groups "ONOS Developers" group.

To unsubscribe from this group and stop receiving emails from it, send an email to onos-dev+unsubscribe@onosproject.org.

[田健]

Hi ShaDAttarha,

        I read your log (stacktrce.txt), and try to share my opinions.

        1.  It is the 'maxPaths' (in the search method of KShortestPathsSearch) caused the exception, not the 'k'.  You can take a look of the source code in KShortestPathsSearch.java at line 48. The 'maxPaths' was expected to be greater than 0, but -1 which was set defaultly with ALL_PATHS (in GraphPathSearch).

        2.  ALL_PATHS means trying to search all the path, but the KShortestPathsSearch considers it as illegal. 

        

        I think you can post this bug on the jira.

       

田健 Tian Jian

软件开发工程师  Software Development Engineer
预研标准部/有线研究院/有线产品经营部 Standard Preresearch Dept./Wireline Product Operation Division

武汉市东湖高新技术开发区华师园路6号中兴通讯  430223  2/F, R&D Building, ZTE Corporation Huashi Park Road, Donghu Hi-tech District, Wuhan, P.R.China, 430223 M: +86 15243616864  E: tian...@zte.com.cn www.zte.com.cn

原始邮件

发件人：ShaDAttarha

收件人：Thomas Vachuska;

抄送人：ONOS Developers;

日 期 ：2016年10月26日 18:06

主 题 ：Re: [onos-dev] the KshortestPaths Algorithm in ONOS has a bug

To unsubscribe from this group and stop receiving emails from it, send an email to onos-dev+u...@onosproject.org.

To post to this group, send email to onos...@onosproject.org.
Visit this group at https://groups.google.com/a/onosproject.org/group/onos-dev/.

To view this discussion on the web visit https://groups.google.com/a/onosproject.org/d/msgid/onos-dev/CANH7vgPcHo0%3DZDj8nPvTQdyrhPkCpG-moMZ_qQUFq9FuEXoiOg%40mail.gmail.com.

[Aaron kruglikov]

Hello ShaDAttarha and Tian Jian,

Blocking the use of ALL_PATHS in this search was deliberate because in the case of a fully connected graph of N NE's the number of paths grows as Summation i = 0 to N-2 of ((N-2)!)/(i!).  This means when N = 10 there are over 109,000 possible paths.  For this reason it didn't appear practical to allow the use of ALL_PATHS.  I will be adding a comment and explicit check that the maxPaths argument cannot be ALL_PATHS.

Best,

Aaron

On Oct 27, 2016, at 7:16 AM, 田健 <tian...@zte.com.cn> wrote:

Hi ShaDAttarha,

        I read your log (stacktrce.txt), and try to share my opinions.

        1.  It is the 'maxPaths' (in the search method of KShortestPathsSearch) caused the exception, not the 'k'.  You can take a look of the source code in KShortestPathsSearch.java at line 48. The 'maxPaths' was expected to be greater than 0, but -1 which was set defaultly with ALL_PATHS (in GraphPathSearch).<zMail_snapScreen_tmp.jpg>

        2.  ALL_PATHS means trying to search all the path, but the KShortestPathsSearch considers it as illegal. <zMail_snapScreen_tmp.jpg>

        

        I think you can post this bug on the jira.

       

田健 Tian Jian

软件开发工程师  Software Development Engineer
预研标准部/有线研究院/有线产品经营部 Standard Preresearch Dept./Wireline Product Operation Division

<9ae3e214c17d49ed935d87c674ba3ee2.jpg>

<24242e5637af428891c4db731e7765ad.jpg>

To view this discussion on the web visit https://groups.google.com/a/onosproject.org/d/msgid/onos-dev/201610271316365342597%40zte.com.cn.
<zMail_snapScreen_tmp.jpg>

[Aaron kruglikov]

Hello Hadi,

I believe you are correct and I will look into it, I think a means of specifying the number of paths returned by get paths or allowing KShortestPaths to provide a fixed number of results even when ALL_PATHS is specified may be appropriate.

Best,

Aaron

On Nov 4, 2016, at 9:01 AM, Hadi Kahraman <hadi.k...@gmail.com> wrote:

Hello Aaron,

Attharta simply wants to configure KShortestPath algorithm instead of the default Dijkstra. It seems that this is impossible without modifying DefaultTopology.getPaths(...) method, which passes ALL_PATHS to the configured algorithm.

Aaron

原始邮件

To view this discussion on the web visit https://groups.google.com/a/onosproject.org/d/msgid/onos-dev/CANH7vgPcHo0%3DZDj8nPvTQdyrhPkCpG-moMZ_qQUFq9FuEXoiOg%40mail.gmail.com.

--
You received this message because you are subscribed to the Google Groups "ONOS Developers" group.

To unsubscribe from this group and stop receiving emails from it, send an email to onos-dev+unsubscribe@onosproject.org.
To post to this group, send email to onos...@onosproject.org.
Visit this group at https://groups.google.com/a/onosproject.org/group/onos-dev/.

To view this discussion on the web visit https://groups.google.com/a/onosproject.org/d/msgid/onos-dev/201610271316365342597%40zte.com.cn.
<zMail_snapScreen_tmp.jpg>

--
You received this message because you are subscribed to the Google Groups "ONOS Developers" group.
To unsubscribe from this group and stop receiving emails from it, send an email to onos-dev+unsubscribe@onosproject.org.
To post to this group, send email to onos...@onosproject.org.
Visit this group at https://groups.google.com/a/onosproject.org/group/onos-dev/.

To view this discussion on the web visit https://groups.google.com/a/onosproject.org/d/msgid/onos-dev/0A202528-1F1A-4578-A703-E859FCB6AC01%40onlab.us.

[Aaron kruglikov]

Hello Hadi,

This problem has been resolved, default topology now provides a method where the user can specify an argument for maxPaths.

Best,

Aaron 

[Hadi Kahraman]

Thanks Aaron.

[Angelos Mimidis]

Hey,
I am too trying to use the KShortestPath algorithm instead of Dikstra. But i am unable to somehow specify the maxpath value. GetPaths() from the topology service does not have a maxpaths field.
As a result ALL_PATHS is passed as the default argument and the search fails, since K-shortest path complains.

Any clues on how to specify the maxpath?

BR Angelos

> Donghu Hi-tech District, Wuhan, P.R.China, 430223M: +86 15243616864 

> To unsubscribe from this group and stop receiving emails from it, send an email to onos-dev+u...@onosproject.org.

> To post to this group, send email to onos...@onosproject.org.
> Visit this group at https://groups.google.com/a/onosproject.org/group/onos-dev/.
> To view this discussion on the web visit https://groups.google.com/a/onosproject.org/d/msgid/onos-dev/29db6044-8bf6-4211-8cbb-79d82b0d42d1%40onosproject.org.
>
>
>
>
> --
> You received this message because you are subscribed to the Google Groups "ONOS Developers" group.

> To unsubscribe from this group and stop receiving emails from it, send an email to onos-dev+u...@onosproject.org.

> To post to this group, send email to onos...@onosproject.org.
> Visit this group at https://groups.google.com/a/onosproject.org/group/onos-dev/.
> To view this discussion on the web visit https://groups.google.com/a/onosproject.org/d/msgid/onos-dev/CANH7vgPcHo0%3DZDj8nPvTQdyrhPkCpG-moMZ_qQUFq9FuEXoiOg%40mail.gmail.com.
>
>
>
>
>
>
>
>
> --
>
> You received this message because you are subscribed to the Google Groups "ONOS Developers" group.
>

> To unsubscribe from this group and stop receiving emails from it, send an email to onos-dev+u...@onosproject.org.

>
> To post to this group, send email to onos...@onosproject.org.
>
> Visit this group at https://groups.google.com/a/onosproject.org/group/onos-dev/.
>
> To view this discussion on the web visit https://groups.google.com/a/onosproject.org/d/msgid/onos-dev/201610271316365342597%40zte.com.cn.
>
> <zMail_snapScreen_tmp.jpg>
>
>
>
>
> --
>
> You received this message because you are subscribed to the Google Groups "ONOS Developers" group.
>

> To unsubscribe from this group and stop receiving emails from it, send an email to onos-dev+u...@onosproject.org.

[Hadi Kahraman]

See class DefaultTopology. Methods setDefaultGraphPathSearch and
public Set<Path> getPaths(DeviceId src, DeviceId dst, LinkWeight weight, int maxPaths)

Note that Dijkstra search method also accepts maxPaths parameter, but returned paths must have equal cost. i.e. if maxPaths=3 but there are only 2 shortest paths with equal cost, Dijkstra returns 2 paths only.

To unsubscribe from this group and stop receiving emails from it, send an email to onos-dev+unsubscribe@onosproject.org.

To post to this group, send email to onos...@onosproject.org.
Visit this group at https://groups.google.com/a/onosproject.org/group/onos-dev/.

To view this discussion on the web visit https://groups.google.com/a/onosproject.org/d/msgid/onos-dev/9173a500-a1d0-4412-bba2-00c96ff6fb35%40onosproject.org.