Hello, One of my action points for the NSI meeting was to draft a use-case for topology descriptions. The goal is to have both proposals describe in detail the approach for topology description and how that would support pathfinding. My proposal is that both approaches outline the following: - Define a topology description for the Automated GOLE topology as was used during SC11 (10 networks, 4 VLANs, and their interconnections), diagram attached. - Describe how a pathfinding algorithm would consume the above-mentioned topologies, and then find path candidates from UvA to KRLight, and finally how to select one of the listed candidates in the following three scenarios: 1) none of the networks have VLAN retagging, 2) Only Netherlight supports VLAN retagging, 3) All network support VLAN retagging. - A *short* analysis of how complex this solution is for the topology. - A *short* analysis of how the solution would extend to multi-layer descriptions. The goal of these proposals is to inform the NSI group on the proposals, their complexity, and their future-proofness. I propose that we have a 3 page limit on the descriptions in order not to burden the rest of the group too much. Suggestions? Jeroen.
On Thu, 15 Dec 2011, Jeroen van der Ham wrote:
Hello,
One of my action points for the NSI meeting was to draft a use-case for topology descriptions. The goal is to have both proposals describe in detail the approach for topology description and how that would support pathfinding.
My proposal is that both approaches outline the following: - Define a topology description for the Automated GOLE topology as was used during SC11 (10 networks, 4 VLANs, and their interconnections), diagram attached. - Describe how a pathfinding algorithm would consume the above-mentioned topologies, and then find path candidates from UvA to KRLight, and finally how to select one of the listed candidates in the following three scenarios: 1) none of the networks have VLAN retagging, 2) Only Netherlight supports VLAN retagging, 3) All network support VLAN retagging. - A *short* analysis of how complex this solution is for the topology. - A *short* analysis of how the solution would extend to multi-layer descriptions.
The goal of these proposals is to inform the NSI group on the proposals, their complexity, and their future-proofness. I propose that we have a 3 page limit on the descriptions in order not to burden the rest of the group too much.
Suggestions?
I very much like the idea of a practical task. 3 pages sounds like a bit much actually, but as long as there is reasonable limit, it should be good. I am missing something about what to do in the case where the complete topology is not available, either due to size/performance/scaling constraints or not being published. Being able to demonstrate how cases with multiple technologies are handled. E.g., the case where both ethernet and sonet exists in the same network and mpls can be popped/pushed on sonet, but ethernet vlans cannot, and ethernet can be carried over sonet, but not vice versa. Maybe I am getting a bit too much ahead here. Best regards, Henrik Henrik Thostrup Jensen <htj at ndgf.org> NORDUnet / Nordic Data Grid Facility.
On 15 Dec 2011, at 14:13, Henrik Thostrup Jensen wrote:
3 pages sounds like a bit much actually, but as long as there is reasonable limit, it should be good.
There are four different points to be addressed here, one of which has 3 subpoints, so I think it's reasonable.
I am missing something about what to do in the case where the complete topology is not available, either due to size/performance/scaling constraints or not being published.
Being able to demonstrate how cases with multiple technologies are handled. E.g., the case where both ethernet and sonet exists in the same network and mpls can be popped/pushed on sonet, but ethernet vlans cannot, and ethernet can be carried over sonet, but not vice versa. Maybe I am getting a bit too much ahead here.
I'm not sure whether these are main requirements right now. I agree they are important, but perhaps we should defer them for now, and keep them on the radar. Perhaps make tickets? I think it's more important to make a decision now and think about how to solve these issues once we have made a decision. I don't think that these are differentiating points though. Jeroen.
Hi all- Attached is rather detailed discussion of the performance of Path Finding on the SC topology. I hope you find it useful. BTW- it is 4 pages, 12 pt font. So sue me. If you do not want to read it because exceeds the arbitrary 3 page limit, then just reduce the font to 10 or 8 and it will be fine. :-) I will post a separate short document describing how our current topology model allows NSI to deal with multi-layer pathfinding. Give me a day or two to let my brain cool off from the previous exercise....:-) (And I will keep this short as well:-) If you have any questions about the use-case, skype me or we can touch them on the call. thanks! Jerry
On Wed, 21 Dec 2011, Jerry Sobieski wrote:
Attached is rather detailed discussion of the performance of Path Finding on the SC topology.
It is actually possible to optimize the worst case chain mode for scenario #2 from 10 reservation calls to 7 by putting a bit of intelligence into netherlight: After the first reservation failure from starlight/kreolight, netherlight switches away from "silly brute force" method to "backtracking" method for pathfinding. Instead of connecting NL-SL first, it will ask krlight to reserve the dest stp to the port reserved for the uvalight source stp. Other stuff: We didn't really agree on an metrics... In distributed systems one usually count message hops. For best case this can be achived by multiplying with 2 to get the answers for a messages based protocol, and multyplying with 4 in our current "lets answer twice" protocol. For worst case, it becomes slightly more ticky, but something like reservations*3-reservationSuccess messages might do it for messages, and multiply with 6 for the current protocol (people wanting to "optimize" stuff should start here :-)). Worst and best case scenario are presented, but average and deviation are more usefull IMHO. This however involves quite a bit more math :-). IMHO, chaining reservations also solve what is perhaps a more overlooked side of topology, i.e., resource availablity. Topology description tend be fairly static while resource availability is not. Even if one knows all the topology, one would have to know which links and ports are available and all their schedules. Delegating this the NSA/NRM means that we can abstract this away. Also, +1 grouping/sets of STPs in some way. Best regards, Henrik Henrik Thostrup Jensen <htj at ndgf.org> NORDUnet / Nordic Data Grid Facility.
Hi, How do you go from a best-case scenario where you have a 1 in 256 chance of guessing it right to a worst-case scenario with 13 messages? Jeroen. On 21 Dec 2011, at 06:26, Jerry Sobieski wrote:
Hi all-
Attached is rather detailed discussion of the performance of Path Finding on the SC topology. I hope you find it useful.
BTW- it is 4 pages, 12 pt font. So sue me. If you do not want to read it because exceeds the arbitrary 3 page limit, then just reduce the font to 10 or 8 and it will be fine. :-)
I will post a separate short document describing how our current topology model allows NSI to deal with multi-layer pathfinding. Give me a day or two to let my brain cool off from the previous exercise....:-) (And I will keep this short as well:-)
If you have any questions about the use-case, skype me or we can touch them on the call.
thanks! Jerry <NSI over AutoGOLE Use Case JS2.docx>_______________________________________________ nsi-wg mailing list nsi-wg@ogf.org https://www.ogf.org/mailman/listinfo/nsi-wg
This is why my head was smoking after writing this.... The best case is 4 Reservations. But those were simply a lucky guess, and i guessed all four segments correctly on the first try at each. The *odds* of doing that is 1:256. The worst case is 13 Reservations. But this is the result of a breadth first search in which the path is guarranteed to be found. i.e 1:1 odds. j Sent from my iPad3g On Dec 21, 2011, at 9:36 AM, Jeroen van der Ham <vdham@uva.nl> wrote:
Hi,
How do you go from a best-case scenario where you have a 1 in 256 chance of guessing it right to a worst-case scenario with 13 messages?
Jeroen.
On 21 Dec 2011, at 06:26, Jerry Sobieski wrote:
Hi all-
Attached is rather detailed discussion of the performance of Path Finding on the SC topology. I hope you find it useful.
BTW- it is 4 pages, 12 pt font. So sue me. If you do not want to read it because exceeds the arbitrary 3 page limit, then just reduce the font to 10 or 8 and it will be fine. :-)
I will post a separate short document describing how our current topology model allows NSI to deal with multi-layer pathfinding. Give me a day or two to let my brain cool off from the previous exercise....:-) (And I will keep this short as well:-)
If you have any questions about the use-case, skype me or we can touch them on the call.
thanks! Jerry <NSI over AutoGOLE Use Case JS2.docx>_______________________________________________ nsi-wg mailing list nsi-wg@ogf.org https://www.ogf.org/mailman/listinfo/nsi-wg
Hi, Attached is my approach to describing the use-case. I managed to stay well within the (arbitrary) limit of 3 pages ;) Jeroen. On 15 Dec 2011, at 12:47, Jeroen van der Ham wrote:
Hello,
One of my action points for the NSI meeting was to draft a use-case for topology descriptions. The goal is to have both proposals describe in detail the approach for topology description and how that would support pathfinding.
My proposal is that both approaches outline the following: - Define a topology description for the Automated GOLE topology as was used during SC11 (10 networks, 4 VLANs, and their interconnections), diagram attached. - Describe how a pathfinding algorithm would consume the above-mentioned topologies, and then find path candidates from UvA to KRLight, and finally how to select one of the listed candidates in the following three scenarios: 1) none of the networks have VLAN retagging, 2) Only Netherlight supports VLAN retagging, 3) All network support VLAN retagging. - A *short* analysis of how complex this solution is for the topology. - A *short* analysis of how the solution would extend to multi-layer descriptions.
The goal of these proposals is to inform the NSI group on the proposals, their complexity, and their future-proofness. I propose that we have a 3 page limit on the descriptions in order not to burden the rest of the group too much.
Suggestions?
Jeroen.
_______________________________________________ nsi-wg mailing list nsi-wg@ogf.org http://www.ogf.org//mailman/listinfo/nsi-wg
participants (3)
-
Henrik Thostrup Jensen -
Jeroen van der Ham -
Jerry Sobieski