[Nsi-wg] Topology properties for NSI - a minimalistic approach

[Evangelos Chaniotakis]

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 at ogf.org
>> http://www.ogf.org/mailman/listinfo/nsi-wg
>>
>
> _______________________________________________
> nsi-wg mailing list
> nsi-wg at ogf.org
> http://www.ogf.org/mailman/listinfo/nsi-wg