[Nsi-wg] Pathfinding, Labels, and Topology (a bit long)

[Jerry Sobieski]

Hi everyone - this is long (sorry) but this is a long held response to 
the so called "label" issue.   We need to engage on this...

Our topology model works just fine for path finding.  Period.  As is.   
It is critical for people to understand this. It works for flat VLANs, 
it works for swapping, it works for essentially any network connection 
service.  Try to get away from conventional signaling ways of thinking 
and look at how NSI is positioned to do this and the power it brings.   
NSI is about *connections* - not VLANs, not waves, not LSPs...  The 
abstraction it presents to the user is a connection model that works 
regardless of underlying technologies.

We want to optimize it so that it is more efficient, but _/it does work 
now /_- make no mistake on this.  And if we want to optimize it, you 
need to make sure we understand what is happening and that we are 
optimizing where it will help. Not simply posing one technology specific 
nuance.

Given our present NSI topology, VLAN selection is not a problem.  Any 
application agent (uRA) that wishes to initiate a connection between two 
endpoints can issue a ReservationRequest specifying the STPs it wants as 
the endpoints.   Since that uRA is making the initial request - we 
*must* assume it knows the endpoints it wishes to connect.   There is no 
way for a PA to presume to know where the RA wants to connect except by 
the RA specifying the specific endpoints in the connection request.

If the uRA has some internal flexibility and is able to use any endpoint 
from of a custom set of useable endpoints, then the uRA can/should just 
choose one itself and ask for that endpoint in the connection request.  
We must presume that the requesting agent is also aware of which 
endpoints are available for its purposes if it knows which are usable.  
And why would any requesting agent say "oh - just give me a connection 
from anywhere to anywhere...I don't care..."  ???   Thats just odd...

So do we need to represent every possible label as an endpoint?  as an 
STP?  Maybe not... We don't necessarily define a host name for every IP 
address in our /8 - but those IP addresses nevertheless exist.  But we 
do define host names when we want to disassociate the name of the host 
from the particular IP address it may currently be using.     There are 
probably more efficient ways to represent the endpoint STPs than full 
enumeration, but _/the abstraction is critically important:  Connections 
need specific endpoints. /_  So we can either specify a symbolic name 
(STP) to represent the specifics of the topological point it represents, 
or we need to find another generic way to represent topological points 
that are [un-enumerated] STPs.   Perhaps an arbitrarily long tuple that 
describes the topological address: 
network/switch/blade/port/color/label/label/label/label...etc.?  ( this 
is similar to  using the IP address itself rather than a hostname, 
right?)  In this scenario, we can enumerate named STPs, or we could 
simply use the raw tuple itself in the ReservationReq (e.g. 
<network><switch><port><label>) to identify the desired endpoint.

This implies some added semantics are necessary in the topology 
relations, and at least a minor change to the CS protocol to accept 
either form of an endpoint specification,... but it does not break the 
high level connection abstractions.   This is very important.  Thoughts?

Another key aspect we must now be explicit about is how we do 
pathfinding.   Path selection is a process of selecting a sequence of 
hops through networks, nodes devices etc.   In order for a path finder 
to decide if a "hop" will work for a path request, the pathfinder must 
be able to "model" that hop, or predict its function - match a set of 
service constraints against the parameters that describe that object.  
For example:  In order to decide if a SONET circuit can be 
crossconnected through a device, one must be able to understand the 
functioning of that device- is it a Ethernet switch? SDH? Infinband? 
MPLS?   Likewise, if one wants to know if an NSI Network will form a 
valid component of a "connection", one must know something about how 
that NSI Network object functions.

We are no longer in a monolithic network where every switching device is 
implicitly the same.   So each topological element must have a Transit 
Function (TF) that describes it.  Ala "network", "GOLE", "node", a 
"switch", etc.   Without this, explicitly or implicitly, pathfinding 
cannot work.  End of story.    This TF may be a type code: such as 
F10E300, or C7609, etc. or a generic function: Node, Multiplexor, Demux, 
Encapsulater, de-encapsulator. switch, etc.  and those codepoints must 
be explicitly defined so that *all* pathfinders can interpret their TF 
consistently when they are found in a topology.    Is DToX ontology 
something that could function in this manner?  Could we tweek it to do so?

We can possibly define a set of basic "well known" Transfer Functions, 
but I doubt we will be able to define /all possible/ transfer functions, 
and at some point there will be some device or region which we will not 
know how to model...an opaque region of the topology.  In these cases, 
the only alternative is to have an agent written that models that 
particular device and ask that agent to model it for us and just give us 
a pass/fail for our constraints.    So while we may be able to model 
some generic topological functions, and maybe even some common complex 
devices, we won't be able to practically model in detail complex regions 
or the exact details of low level devices...so we need to identify an 
oracle or an agent associated with each such topological object that we 
can query to see if the object can/will work, and to reserve the 
resources for this request.

So for now, all we have in the NSI topology are "NSI Networks".  These 
*DO* have a Transfer Function.  Its implicit, and may be the default, 
but it is the following: "Any [ingress] port can be crossconnected to 
any [egress] port - if resources are available."  The "any to any" is 
important, but the real rub is the "if resources are available".  So in 
our current model, the TF is implicit but clear nonetheless, and the 
"oracle" is the NSA.

As we stand now, all NSI Networks by default are assumed to have the 
"any-to-any" TF.  We use that fact to select a candidate path, and then 
we check resource availability with a ReservationRequest.  Since some of 
our networks cannot actually do "any-to-any" (i.e. they were advertising 
untruths about their capabilities), those NSAs simply reject the 
requests they cannot perform as if they had just run out of resources.   
A robust remote pathfinder will try alternate paths until all 
possibilities are exhausted.

Indeed, to indicate limited VLAN crossconnectivity we could in fact 
advertise separate networks - one for vlan 1780, one for vlan 1781, etc. 
   This works.  Quite well in fact. And short circuits the exhaustive 
search issue...as all crossconnects *can* actually be made if resources 
are available, and a remote PF simply has to choose the right egress 
from the preceding network.   IF they are advertising correctly, then 
the exhaustive VLAN search problem is solved.  For example: NL > SL;  if 
NL can swap and indicates so by offering all SDPs in one network, and SL 
splits into four networks SL80,SL81,SL82,and SL83 to indicate which 
crossconnects can be made by each service region - each terminating the 
right link from NL, then it all works...no changes necessary except to 
the topology description.  This may suck as a general solution due to 
the many VLAN planes required, but its really a flaw with the Ethernet 
switching capabilities at SL - it can not swap VLANs...no wishing will 
change that.  Further, such VLAN planes may not represent VLAN planes at 
all - they may represent other types of limitations...so simply because 
they rub the fur the wrong way doesn't mean they are inappropriate or an 
aberation that will never really be seen.   Its not the topology 
abstractions or the protocol abstractions at fault.

But admittedly, searching the space is slow - which is one problem, but 
not a fault of the architecture or the protocol.   We need to understand 
why such simple ReservationRequests with known available but limited 
resources like in the demos takes more than a couple milliseconds... 
(!)  Even latency across oceans cannot be held blameless here - as a 
more efficeint MTL might require far fewer handshakes...The NSI protocol 
itself is not chatty.

The false assumption we have is that by knowing topology that we will 
magically be able to speed everything up.  There is no free lunch - 
labels do not fundamentally remove the complexity of the processing and 
so will only speed things up in certain cases.  It would be a tragedy to 
throw away powerful abstractions for such a small gain. And Global 
topology won't speed things up either, indeed it is far more likely to 
overwhelm with deluge of detail.   What we *might* be able to do is 
provide a *better* solution...i.e. even though the complexity is high, 
we may be able to produce a more exacting path - one that is better in 
certain measurable ways over conventional hop-by-hop PF.

So let me reiterate:  Enumerating the STPs we wish to use to form a 
resource pool is *NOT* a scaling problem.  The size of the XML data 
representation is not the problem - if it were, we would not insist on 
using XML based representations.   Is it the size of the database that 
concerns us by representing each possible STP for each VLAN??...nah - we 
would have to do that anyway if each VLAN were actually used for 
circuits.  So that doesn't fly as a scaling issue either.    And in 
fact, the enumeration of every VLAN does not add computational 
complexity in itself - its linear with the number of VLANs available no 
matter how many networks there are.  And frankly, there is *no* 
requirement that the XML (OWL) representation must be retained internal 
to an NSA...we only stipulate that it be in RDF/OWL format for common 
exchange and common interpretation.  An NSA can store the info 
internally however it deems most efficient.  And any decent RDB can 
index millions of VLAN entries and/or connections and/or semantic 
relations in a DB effortlessly.   So just enumerating the VLANs (labels) 
as STPs is not really an issue...its just not.

Where we have a possible concern is the search space and the potential 
of an exhaustive search over a large space can in fact be huge.  So we 
want tread carefully, to do so efficiently.  But this complexity problem 
will not be solved with labels - The search space is still the same 
whether you pose labels as attributes or as enumerated items.  And since 
all you can minimally assume will be available in the topology are the 
STPs and SDP adjacencies, you might have to do the search anyway like it 
or not.

The real constraints are not choosing a label, its checking the 
availability of selected resources.  The only way to optimize the 
constraint based search problem to choose the order of your constraint 
checking so as to prune the search space effectively.   VLAN id is 
probably not an efficient primary constraint to accomplish that.    
Further, how you represent the topology internal to an NSA is a 
implementation issue.   If a remote pathfinder has to search by trial 
and error to find a successful VLAN...you are ignoring all the other 
constraints that could either themselves make the search space enormous 
or could significantly prune the search space apriori if chosen 
wisely.   We cannot dis an exhaustive search for a useable VLAN unless 
you also look at all the other constraints for their complexity as 
well.  Pathfinding *IS* hard.. but you must optimize the entire process 
- but label representation and selection is both a non-issue and the 
least of our concerns.

And having selected a path, there is *still* the reservation process - 
even if you had neon lights advertising the available VLANids at every 
boundary, you still need to access the oracle (NSA) to confirm any 
candiate path.   And so you could very easily find yourself in an 
exhaustive search looking for a VLAN that has the available capacity or 
adequate buffering or...etc.  Labels do not solve the search problem.  
The only way to solve it is to provide a full detailed topology to every 
pathfinder (not likely in real world or even the R&E world) or ask the 
local pathfinder with access to the local topology details and state to 
select a path for you (much more viable approach).   There is a middle 
ground also, where the remote pathfinder may have some partial (high 
level) topology view and can select some high level path, and then 
contact each object (network) along that path and ask them to confirm 
their portion of it with their internal detailed information.   This 
latter middle ground is IMO the best we can hope for.   But even our 
worst case on minimal topology knowledge works as we saw last week in 
Seattle.

Opaque topology regions are not evil.  They can be highly useful.  They 
are how the NSI Framework scales. And they are essential to enable each 
network to assert their own autonomy and to hide minutia details.  
Asserting that technology specific nuances are necessary for NSI remote 
pathfinders to work is simply not true.   These past demos are proof.  
You can't tell me that its a protocol scaling issue if the absolute 
worst case exhaustive search of a VLAN space consisting of roughly 1000 
combinations would take more than a few seconds ... if it does, on a 
network with 12 nodes, we have some very very poor implementations.   
And unfortunately, labels do not solve this problem.  The problem is the 
fact that you want to do tree segmentation (i.e. remotely choose the 
endpoints across each network) and at the same time want the target 
network to choose the endpoints for you so you don't have to try lots of 
reservations...duh!  What you are implicitly saying is that "I really 
want the local pathfinder would do the hard stuff because it is so much 
faster dealing with its own topology and has so much more state 
knowledge...hmmm....

Finally, I am unable to see a requirement where intermediate VLAN IDs 
that form a peering between two transit networks are of issue to the 
original connection request. If the transit network can swap vlans, then 
you can choose any intermediate vlan you want - i.e. any STP regardless 
of which VLAN it represents... And if it doesn't do vlan translation but 
implied it could because it advertised the functionality in the topology 
and now you are stuck doing an exhaustive search...who's fault is that?  
Its not a NSI problem if a network misrepresents what it can do or runs 
out of resource. If a PF simply cannot progress the connection - for 
VLAN reasons or other resources, its not going to be solved by 
labels.      As discussed above, a reservation can be rejected for lots 
of reasons leading to an exhaustive search for a viable STP..   In any 
case, picking an intermediate point because of its VLAN tag is IMO 
superfluous.    Its what old signaling protocols had to do because of 
the way they were designed.  NSI accomplishes this but in a highly 
structured manner.

We have an extremely novel and powerful architecture in NSI.   Don't 
trip over the conventional thinking of conventional protocols...if we 
want conventional - just use GMPLS. or Q2931 or Q2764... or IDCP (:-)

Best regards all- Thanks for reading...
Jerry


On 11/28/11 11:23 AM, ogf-nsi-project at googlecode.com wrote:
> Comment #2 on issue 50 by jmacau... at gmail.com: Pathfinding functionality
> review
> http://code.google.com/p/ogf-nsi-project/issues/detail?id=50
>
> At the NSI protocol currently stands we would have to fully qualify a
> reservation request at the root PA.  There is no mechanism in place for
> space based parameters to be negotiated down the tree since each child PA
> may select a different set.  Something to think about when designing the
> vlan capabilities.  The root PA will need to be able to select that target
> vlan.
>
> _______________________________________________
> nsi-wg mailing list
> nsi-wg at ogf.org
> http://www.ogf.org/mailman/listinfo/nsi-wg
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.ogf.org/pipermail/nsi-wg/attachments/20111128/0fdcee5f/attachment-0001.html