Thoughts on a basic topology model for NSI
Hi all- Relative to our brief discussion last week about topology and the NSI... We want the NSI to offer more power and options to the "user" - to break out of the traditional carrier models for interacting with the user. And I think our notions of Requesting aAgents and Providing Agents does that nicely and in a very elegant and scalable fashion. However, we still have a lot of discussion about pathfinding - about how the agents will go about decomposing a path request into sub-paths for tree or chain model processing, or how we decide which NRMs are responsible for a particular end point, etc. These all deal with *topology*. There are quite a few notions we take for granted that require some sort of topology model. For instance: a Service Termination Point. Whatever we end up caling it, the semantics of an STP is that it represents a point in the topology where a service connection can terminate. We talk about capturing path information for monitoring...that requires a notion of how the topology is defined. There are lots of topologically based assumptions we need to be more explicit about. So this set of slides tries to capture some thoughts of mine on how we can pose a simple minimalist topological model sufficient for our NSI purposes. I think it is consistent wth our thoughts and discussions. And while it may bump into things that the NML WG is considering, I doubt a) we have come up with anything conflicting, and b) we certanly have not gone to the details of how to describe or distribute a topology database - we just assume we have a TopoDB and that is contains these basic constructs. Comments are welcome...Its only a draft for consideration... Jerry While the NSI protocol itself does not impose a particular topology on the transport plane or the agents that manage it, we do impose some notions on the Connections we construct - e.g. that the NSAs will, as a group, be able to construct and reserve a suitable path for the request.
Hi Jerry -- I modified your model description to fit my understanding, and the understanding some of us came to in conversations in SLC last week.. I think they map pretty well, with some differences. We should talk about it tomorrow. It would be good to have a description in these forms that we all agree to. Thanks - talk to you tomorrow. John On Feb 2, 2010, at 2:24 PM, Jerry Sobieski wrote:
Hi all-
Relative to our brief discussion last week about topology and the NSI...
We want the NSI to offer more power and options to the "user" - to break out of the traditional carrier models for interacting with the user. And I think our notions of Requesting aAgents and Providing Agents does that nicely and in a very elegant and scalable fashion.
However, we still have a lot of discussion about pathfinding - about how the agents will go about decomposing a path request into sub-paths for tree or chain model processing, or how we decide which NRMs are responsible for a particular end point, etc. These all deal with *topology*. There are quite a few notions we take for granted that require some sort of topology model. For instance: a Service Termination Point. Whatever we end up caling it, the semantics of an STP is that it represents a point in the topology where a service connection can terminate. We talk about capturing path information for monitoring...that requires a notion of how the topology is defined. There are lots of topologically based assumptions we need to be more explicit about.
So this set of slides tries to capture some thoughts of mine on how we can pose a simple minimalist topological model sufficient for our NSI purposes. I think it is consistent wth our thoughts and discussions. And while it may bump into things that the NML WG is considering, I doubt a) we have come up with anything conflicting, and b) we certanly have not gone to the details of how to describe or distribute a topology database - we just assume we have a TopoDB and that is contains these basic constructs.
Comments are welcome...Its only a draft for consideration... Jerry
While the NSI protocol itself does not impose a particular topology on the transport plane or the agents that manage it, we do impose some notions on the Connections we construct - e.g. that the NSAs will, as a group, be able to construct and reserve a suitable path for the request. <NSI Topology Sketch.pptx>_______________________________________________ nsi-wg mailing list nsi-wg@ogf.org http://www.ogf.org/mailman/listinfo/nsi-wg
Hi all. Here is my take on the topology issue: - We SHOULD describe the topology properties that we think we will need for pathfinding. - We SHOULD NOT assign too many semantics to the topology elements. - We MUST NOT design a new topology schema. Now for the things that I think are absolutely required properties for any topology: 1. The topology is a directed simple graph. Note: Directed graph means each edge is an arrow with a start vertex and an end vertex. Simple graph means there are no parallel edges i.e. going the same direction between the same two vertices. (I am on the fence for the "simple" requirement; do we need to make the topology a multigraph for some reason?) 2. We are allowed to separate the topology into mutually exclusive subgraphs. I will use Jerry's term "Network Domain" for these subgraphs. Note: A subgraph is an arbitrary set of vertices and edges. It may consist of only edges, only vertices, or a mix thereof. A Network Domain is not necessarily a connected graph. (i.e. there is not necessarily a path between any two of its vertices). 3. The union of all Network Domains MUST equal (cover) the entire topology. Rephrased: a given vertex or edge MUST belong to exactly one Network Domain. 4. A vertex belonging to a Network Domain MAY be connected to a vertex belonging to another Network Domain. In that case, that vertex for NSI purposes will be classified as a "Service Termination Point". 5. Edges and vertices MAY be annotated with attributes and metrics: i.e. framing, capacity, cost, etc. Note: We MUST NOT specify those - this is a job for NML. But we SHOULD specify what we think we will need from these attributes. 6. Each vertex and edge MUST BE addressable through a globally unique identifier. Note that in the above there are very few hard requirements for the topology graph - it can be as rich or as simple as necessary. I have intentionally avoided assigned any names (such as "node", "port", "link", "point" etc) to the edges and vertices of the topology graph. Finally, I think that the above requirements are enough to satisfy the needs of pathfinding. Can anyone think of any further requirements? Or is there a way we relax these even more somehow? Here are a couple of examples of graphs (attached also in .graffle). I will work on more complex ones if needed but really, they will be pretty much equivalent to the graphs on Jerry's slides.
I like this - As far as I can tell it is exactly right, and I learned what a directed graph is. Thanks John On Feb 10, 2010, at 8:09 PM, Evangelos Chaniotakis wrote:
Hi all.
Here is my take on the topology issue: - We SHOULD describe the topology properties that we think we will need for pathfinding. - We SHOULD NOT assign too many semantics to the topology elements. - We MUST NOT design a new topology schema.
Now for the things that I think are absolutely required properties for any topology:
1. The topology is a directed simple graph. Note: Directed graph means each edge is an arrow with a start vertex and an end vertex. Simple graph means there are no parallel edges i.e. going the same direction between the same two vertices. (I am on the fence for the "simple" requirement; do we need to make the topology a multigraph for some reason?)
2. We are allowed to separate the topology into mutually exclusive subgraphs. I will use Jerry's term "Network Domain" for these subgraphs. Note: A subgraph is an arbitrary set of vertices and edges. It may consist of only edges, only vertices, or a mix thereof. A Network Domain is not necessarily a connected graph. (i.e. there is not necessarily a path between any two of its vertices).
3. The union of all Network Domains MUST equal (cover) the entire topology. Rephrased: a given vertex or edge MUST belong to exactly one Network Domain.
4. A vertex belonging to a Network Domain MAY be connected to a vertex belonging to another Network Domain. In that case, that vertex for NSI purposes will be classified as a "Service Termination Point".
5. Edges and vertices MAY be annotated with attributes and metrics: i.e. framing, capacity, cost, etc. Note: We MUST NOT specify those - this is a job for NML. But we SHOULD specify what we think we will need from these attributes.
6. Each vertex and edge MUST BE addressable through a globally unique identifier.
Note that in the above there are very few hard requirements for the topology graph - it can be as rich or as simple as necessary.
I have intentionally avoided assigned any names (such as "node", "port", "link", "point" etc) to the edges and vertices of the topology graph.
Finally, I think that the above requirements are enough to satisfy the needs of pathfinding. Can anyone think of any further requirements? Or is there a way we relax these even more somehow?
Here are a couple of examples of graphs (attached also in .graffle). I will work on more complex ones if needed but really, they will be pretty much equivalent to the graphs on Jerry's slides.
<topo-examples.pdf>
<topo-examples.graffle>_______________________________________________ nsi-wg mailing list nsi-wg@ogf.org http://www.ogf.org/mailman/listinfo/nsi-wg
Evangelos, I think your simple graph described in #1 will not hold and we will need more than a single link between nodes. If we are supporting #5 then we could need multiple links to represent different values for the physical connections, especially if we are doing route diversity. In addition, there my be multiple links as a result of topology at different layers between the nodes (unless these are considered separate graphs). John. On 10-02-10 8:09 PM, Evangelos Chaniotakis wrote:
Hi all.
Here is my take on the topology issue: - We SHOULD describe the topology properties that we think we will need for pathfinding. - We SHOULD NOT assign too many semantics to the topology elements. - We MUST NOT design a new topology schema.
Now for the things that I think are absolutely required properties for any topology:
1. The topology is a directed simple graph. Note: Directed graph means each edge is an arrow with a start vertex and an end vertex. Simple graph means there are no parallel edges i.e. going the same direction between the same two vertices. (I am on the fence for the "simple" requirement; do we need to make the topology a multigraph for some reason?)
2. We are allowed to separate the topology into mutually exclusive subgraphs. I will use Jerry's term "Network Domain" for these subgraphs. Note: A subgraph is an arbitrary set of vertices and edges. It may consist of only edges, only vertices, or a mix thereof. A Network Domain is not necessarily a connected graph. (i.e. there is not necessarily a path between any two of its vertices).
3. The union of all Network Domains MUST equal (cover) the entire topology. Rephrased: a given vertex or edge MUST belong to exactly one Network Domain.
4. A vertex belonging to a Network Domain MAY be connected to a vertex belonging to another Network Domain. In that case, that vertex for NSI purposes will be classified as a "Service Termination Point".
5. Edges and vertices MAY be annotated with attributes and metrics: i.e. framing, capacity, cost, etc. Note: We MUST NOT specify those - this is a job for NML. But we SHOULD specify what we think we will need from these attributes.
6. Each vertex and edge MUST BE addressable through a globally unique identifier.
Note that in the above there are very few hard requirements for the topology graph - it can be as rich or as simple as necessary.
I have intentionally avoided assigned any names (such as "node", "port", "link", "point" etc) to the edges and vertices of the topology graph.
Finally, I think that the above requirements are enough to satisfy the needs of pathfinding. Can anyone think of any further requirements? Or is there a way we relax these even more somehow?
Here are a couple of examples of graphs (attached also in .graffle). I will work on more complex ones if needed but really, they will be pretty much equivalent to the graphs on Jerry's slides.
_______________________________________________ nsi-wg mailing list nsi-wg@ogf.org http://www.ogf.org/mailman/listinfo/nsi-wg
John, Thank you for reviewing. I of course agree with you that we need to represent multiple links between nodes. This can be done either by allowing parallel edges in the graph, and having the edges represent links, or by breaking each link down to "edge-vertex-edge-vertex-edge" constructs (that kindof look like the Points JV has been talking about), if we want to keep the graph simple. (By this I mean simple in the mathematical sense - it'll have more edges and vertices.) There are a couple of advantages to keeping the graph simple - it's easier to use some algorithms, for one. A more subtle implication is that in a simple graph, an edge can be uniquely identified by the two vertices it connects (because there are no parallels). This means that we can express a path as a sequence of vertices rather than vertices and edges. If we do multigraphs, the opposite holds true but the graph description and diagrams may be a lot more concise. Note that a multigraph can always be broken down to an equivalent simple graph with automated tools anyway. There is no big advantage either way, in my opinion. From the current topology schemas, NDL and NML take the simple-graph approach whereas NMWG allows multigraphs. On Feb 16, 2010, at 6:44 AM, John MacAuley wrote:
Evangelos,
I think your simple graph described in #1 will not hold and we will need more than a single link between nodes. If we are supporting #5 then we could need multiple links to represent different values for the physical connections, especially if we are doing route diversity. In addition, there my be multiple links as a result of topology at different layers between the nodes (unless these are considered separate graphs).
John.
On 10-02-10 8:09 PM, Evangelos Chaniotakis wrote:
Hi all.
Here is my take on the topology issue: - We SHOULD describe the topology properties that we think we will need for pathfinding. - We SHOULD NOT assign too many semantics to the topology elements. - We MUST NOT design a new topology schema.
Now for the things that I think are absolutely required properties for any topology:
1. The topology is a directed simple graph. Note: Directed graph means each edge is an arrow with a start vertex and an end vertex. Simple graph means there are no parallel edges i.e. going the same direction between the same two vertices. (I am on the fence for the "simple" requirement; do we need to make the topology a multigraph for some reason?)
2. We are allowed to separate the topology into mutually exclusive subgraphs. I will use Jerry's term "Network Domain" for these subgraphs. Note: A subgraph is an arbitrary set of vertices and edges. It may consist of only edges, only vertices, or a mix thereof. A Network Domain is not necessarily a connected graph. (i.e. there is not necessarily a path between any two of its vertices).
3. The union of all Network Domains MUST equal (cover) the entire topology. Rephrased: a given vertex or edge MUST belong to exactly one Network Domain.
4. A vertex belonging to a Network Domain MAY be connected to a vertex belonging to another Network Domain. In that case, that vertex for NSI purposes will be classified as a "Service Termination Point".
5. Edges and vertices MAY be annotated with attributes and metrics: i.e. framing, capacity, cost, etc. Note: We MUST NOT specify those - this is a job for NML. But we SHOULD specify what we think we will need from these attributes.
6. Each vertex and edge MUST BE addressable through a globally unique identifier.
Note that in the above there are very few hard requirements for the topology graph - it can be as rich or as simple as necessary.
I have intentionally avoided assigned any names (such as "node", "port", "link", "point" etc) to the edges and vertices of the topology graph.
Finally, I think that the above requirements are enough to satisfy the needs of pathfinding. Can anyone think of any further requirements? Or is there a way we relax these even more somehow?
Here are a couple of examples of graphs (attached also in .graffle). I will work on more complex ones if needed but really, they will be pretty much equivalent to the graphs on Jerry's slides.
_______________________________________________ nsi-wg mailing list nsi-wg@ogf.org http://www.ogf.org/mailman/listinfo/nsi-wg
_______________________________________________ nsi-wg mailing list nsi-wg@ogf.org http://www.ogf.org/mailman/listinfo/nsi-wg
While I agree simple is better, we should keep in mind that pathfinding algorithms are not nsi goal. Imo, our topo discussions should focus on how STPs map to topology, how NSAs define their areas, and how we denote and manipulate paths - all of which is not quite the same as pathfinding. PF is going to need detailed well thought out topology architecture - but we don't need to solve all that now. Just enough for NSI spec to clearly define our terms. Hope this helps. Jerry Sent from my iPhone On Feb 17, 2010, at 7:00 AM, Evangelos Chaniotakis <haniotak@es.net> wrote:
John,
Thank you for reviewing. I of course agree with you that we need to represent multiple links between nodes.
This can be done either by allowing parallel edges in the graph, and having the edges represent links, or by breaking each link down to "edge-vertex-edge-vertex-edge" constructs (that kindof look like the Points JV has been talking about), if we want to keep the graph simple. (By this I mean simple in the mathematical sense - it'll have more edges and vertices.)
There are a couple of advantages to keeping the graph simple - it's easier to use some algorithms, for one. A more subtle implication is that in a simple graph, an edge can be uniquely identified by the two vertices it connects (because there are no parallels). This means that we can express a path as a sequence of vertices rather than vertices and edges.
If we do multigraphs, the opposite holds true but the graph description and diagrams may be a lot more concise. Note that a multigraph can always be broken down to an equivalent simple graph with automated tools anyway.
There is no big advantage either way, in my opinion. From the current topology schemas, NDL and NML take the simple-graph approach whereas NMWG allows multigraphs.
On Feb 16, 2010, at 6:44 AM, John MacAuley wrote:
Evangelos,
I think your simple graph described in #1 will not hold and we will need more than a single link between nodes. If we are supporting #5 then we could need multiple links to represent different values for the physical connections, especially if we are doing route diversity. In addition, there my be multiple links as a result of topology at different layers between the nodes (unless these are considered separate graphs).
John.
On 10-02-10 8:09 PM, Evangelos Chaniotakis wrote:
Hi all.
Here is my take on the topology issue: - We SHOULD describe the topology properties that we think we will need for pathfinding. - We SHOULD NOT assign too many semantics to the topology elements. - We MUST NOT design a new topology schema.
Now for the things that I think are absolutely required properties for any topology:
1. The topology is a directed simple graph. Note: Directed graph means each edge is an arrow with a start vertex and an end vertex. Simple graph means there are no parallel edges i.e. going the same direction between the same two vertices. (I am on the fence for the "simple" requirement; do we need to make the topology a multigraph for some reason?)
2. We are allowed to separate the topology into mutually exclusive subgraphs. I will use Jerry's term "Network Domain" for these subgraphs. Note: A subgraph is an arbitrary set of vertices and edges. It may consist of only edges, only vertices, or a mix thereof. A Network Domain is not necessarily a connected graph. (i.e. there is not necessarily a path between any two of its vertices).
3. The union of all Network Domains MUST equal (cover) the entire topology. Rephrased: a given vertex or edge MUST belong to exactly one Network Domain.
4. A vertex belonging to a Network Domain MAY be connected to a vertex belonging to another Network Domain. In that case, that vertex for NSI purposes will be classified as a "Service Termination Point".
5. Edges and vertices MAY be annotated with attributes and metrics: i.e. framing, capacity, cost, etc. Note: We MUST NOT specify those - this is a job for NML. But we SHOULD specify what we think we will need from these attributes.
6. Each vertex and edge MUST BE addressable through a globally unique identifier.
Note that in the above there are very few hard requirements for the topology graph - it can be as rich or as simple as necessary.
I have intentionally avoided assigned any names (such as "node", "port", "link", "point" etc) to the edges and vertices of the topology graph.
Finally, I think that the above requirements are enough to satisfy the needs of pathfinding. Can anyone think of any further requirements? Or is there a way we relax these even more somehow?
Here are a couple of examples of graphs (attached also in .graffle). I will work on more complex ones if needed but really, they will be pretty much equivalent to the graphs on Jerry's slides.
_______________________________________________ nsi-wg mailing list nsi-wg@ogf.org http://www.ogf.org/mailman/listinfo/nsi-wg
_______________________________________________ nsi-wg mailing list nsi-wg@ogf.org http://www.ogf.org/mailman/listinfo/nsi-wg
_______________________________________________ nsi-wg mailing list nsi-wg@ogf.org http://www.ogf.org/mailman/listinfo/nsi-wg
Hi Jerry, all, Please mind the presentation Tomohiro and myself prepared for OGF27. You can find it in the forge, arch working docs section (direct download here [1]). My best regards, [1] http://forge.gridforum.org/sf/go/doc15857?nav=1 -- Joan A. García-Espín CTX, i2CAT Foundation El 02/02/2010, a las 20:24, Jerry Sobieski escribió:
Hi all-
Relative to our brief discussion last week about topology and the NSI...
We want the NSI to offer more power and options to the "user" - to break out of the traditional carrier models for interacting with the user. And I think our notions of Requesting aAgents and Providing Agents does that nicely and in a very elegant and scalable fashion.
However, we still have a lot of discussion about pathfinding - about how the agents will go about decomposing a path request into sub- paths for tree or chain model processing, or how we decide which NRMs are responsible for a particular end point, etc. These all deal with *topology*. There are quite a few notions we take for granted that require some sort of topology model. For instance: a Service Termination Point. Whatever we end up caling it, the semantics of an STP is that it represents a point in the topology where a service connection can terminate. We talk about capturing path information for monitoring...that requires a notion of how the topology is defined. There are lots of topologically based assumptions we need to be more explicit about.
So this set of slides tries to capture some thoughts of mine on how we can pose a simple minimalist topological model sufficient for our NSI purposes. I think it is consistent wth our thoughts and discussions. And while it may bump into things that the NML WG is considering, I doubt a) we have come up with anything conflicting, and b) we certanly have not gone to the details of how to describe or distribute a topology database - we just assume we have a TopoDB and that is contains these basic constructs.
Comments are welcome...Its only a draft for consideration... Jerry
While the NSI protocol itself does not impose a particular topology on the transport plane or the agents that manage it, we do impose some notions on the Connections we construct - e.g. that the NSAs will, as a group, be able to construct and reserve a suitable path for the request. <NSI Topology Sketch.pptx>_______________________________________________ nsi-wg mailing list nsi-wg@ogf.org http://www.ogf.org/mailman/listinfo/nsi-wg
Thanks! Jerry Joan A. Garcia-Espin wrote:
Hi Jerry, all,
Please mind the presentation Tomohiro and myself prepared for OGF27. You can find it in the forge, arch working docs section (direct download here [1]).
My best regards,
[1] http://forge.gridforum.org/sf/go/doc15857?nav=1 -- Joan A. García-Espín CTX, i2CAT Foundation
El 02/02/2010, a las 20:24, Jerry Sobieski escribió:
Hi all-
Relative to our brief discussion last week about topology and the NSI...
We want the NSI to offer more power and options to the "user" - to break out of the traditional carrier models for interacting with the user. And I think our notions of Requesting aAgents and Providing Agents does that nicely and in a very elegant and scalable fashion.
However, we still have a lot of discussion about pathfinding - about how the agents will go about decomposing a path request into sub-paths for tree or chain model processing, or how we decide which NRMs are responsible for a particular end point, etc. These all deal with *topology*. There are quite a few notions we take for granted that require some sort of topology model. For instance: a Service Termination Point. Whatever we end up caling it, the semantics of an STP is that it represents a point in the topology where a service connection can terminate. We talk about capturing path information for monitoring...that requires a notion of how the topology is defined. There are lots of topologically based assumptions we need to be more explicit about.
So this set of slides tries to capture some thoughts of mine on how we can pose a simple minimalist topological model sufficient for our NSI purposes. I think it is consistent wth our thoughts and discussions. And while it may bump into things that the NML WG is considering, I doubt a) we have come up with anything conflicting, and b) we certanly have not gone to the details of how to describe or distribute a topology database - we just assume we have a TopoDB and that is contains these basic constructs.
Comments are welcome...Its only a draft for consideration... Jerry
While the NSI protocol itself does not impose a particular topology on the transport plane or the agents that manage it, we do impose some notions on the Connections we construct - e.g. that the NSAs will, as a group, be able to construct and reserve a suitable path for the request. <NSI Topology Sketch.pptx>_______________________________________________ nsi-wg mailing list nsi-wg@ogf.org http://www.ogf.org/mailman/listinfo/nsi-wg
participants (5)
-
Evangelos Chaniotakis -
Jerry Sobieski -
Joan A. Garcia-Espin -
John MacAuley -
John Vollbrecht