[Nsi-wg] NML topology
Jerry Sobieski
jerry at nordu.net
Sat Feb 27 10:28:13 CST 2010
Hi Joan-
Yes...we have drifted a bit far from shore in these discussions - albeit
they do serve to show some of the prior work and "nuanced complexities"
(:-) of things we as humans think of as self evident and straightforward
when mapped to computational processes where nothing can be assumed and
everything must be explicitly addressed.
Let me elaborate on the iteration issue:
In order to form a valid sub-request, each sub-request must /at a
minimum/ specify its end points. Selecting the ingress point for each
segment depends upon knowing the egress point for the preceding segment.
So you have to resolve the previous segment first...and so on up the
line until you reach the local domain. However, if we receive a
request that has a set of intermediate STPs in the PO, we are required
to transit these STPs - they are *required* STPs. Since these are
necessary, the dependency on the adjacent segments is removed, and each
segment can be treated as a separate and independent Path Request and
can be performed asynchroously with the other sub-requests. All of the
sub-requests defined by the original PO can be performed in parallel and
*must* come back confirmed for the overall request to be complete and
confirmed back to the original requester. (Note: we still have to
sequentially go thru the PO to set up the individual tree
subrequests...but this is very cheap and fast.)
But this all relies on the fact that the STPs were present apriori in
the original request PO. Which begs the question how did the
requesting NSA know to select these STPs as transit points?
However, there is no assurance to the local provider NSA that the
transit STPs specified in the PO are the *only* interdomain links the
request will need to transit. So the local NSA decompose the original
request into the segments defined by the request, but then he still
needs to run the described psuedo code on each subsegment to discover
any additionional interdomain links.
If the local NSA decides to add an STP to the PO for any reason (say, to
decompose a subsegment into local and remote components) then that STP
is not a "required" STP under the constraints specified in the original
request. This STP is a *candidate* STP. And so, if both [candidate]
segments sharing that STP can not be confirmed, then that STP must be
discarded and another candidate STP must be selected and the process
repeated until all candidate STPs have been considered or a succesful
end-to-end Path was found. (This is pathfinding). Worse, in a
recursive fashion, a candidate STP cannot be confirmed if is part of a
segment that shares an endpoint with another unconfirmed candidate
segment. (Ugh!)
So... If we assert having [somehow] selected the domains you want to
transit (and selected the ingress and/or egress points for each) in some
process of high level PathFinding, you *can* make the reservation
requests in parallel. However, if any reservation fails, then the
adjacent segment reservations are of questionable utility and may
(probably) need to be torn down and alternate path(s) explored. This
topic of path planning involves issues like crankback, near/far bypass,
etc. For the time being, IMO, we should not endorse any cranlback or
alternate path discovery algorithms or any PathFinding algorithm at all
- We just need to support Tree and Chain handling.
Finally, if we try to parallelize the selection of downstream domains,
you have to ask yourself what is the selection criteria? From a
possibly very large and arbitrary set of domains, how do we sort them
out into relevant and irrelevant domains? Do we use reachability?
authorization? capacity? schedule? Random Guess? You need *all* of the
request criteria satisfied before confirming a Path so the order in
which you inspect the constraints is important and the only real choice
we have as NSA. This constraint ordering is found by Best Practice
(heuristics), and varies from network to network. The prefered (most
common) ordering is that which prunes the search space
earliest/fastest, This almost always means finding a candidate Path
with reachability from the starting point first - since this immediately
prunes 99% of the topology from consideration. And after each
candidate STP/segment is qualified and reserved, the search starts
over. The point I want to make here is that we need to really
appreciate the scope of the PathFinding process - even at this stage of
the NSI discussions. We need to be thinking how we organize the NSI to
aid the PF process with clarity and well defined concepts and architecture.
Hope this helps - enjoy the weekend!
Jerry
Joan A. García-Espín wrote:
> Hi Jerry, all,
>> id-PO = (ingress > egress); /* expand PO = (nextDomain/ingress >
>> nextDomain/exit > anotherDomain/exit > endDomain/egress) */
>> if(method==tree) then id-PO = InterdomainExpansion(ingress > egress);
>> PO[i] = ConnectRequest( NSA(ingressSTP), id-PO );
>>
>> If the local NSA elects to expand the remote PO, we get a tree model
>> PO. If the local NSA does not expand the PO we have a chain model
>> PO. Its up to the local NSA to decide which approach to use.
>
> Elegant way to fix it :). However, this means the process should be
> iterated up to the moment that the last expansion only provides local
> NSA as a result. Shouldn't it be faster to have the inter-domain path
> finding done at the very beginning, avoiding iteration? It seems to me
> that hierarchical (tree) deployments using this algorithm would follow
> a chain-like path finding model, loosing the advantage of being the
> whole-inter-domain-topology-knowing hierarchy parent.
>
> Anyway, I highly appreciate (and learn from!) the discussion we're
> having here but aren't we rowing far from the definition of the
> interface itself?
>
> Regards,
> --
> Joan A. García-Espín
> CTX, i2CAT Foundation
>
>
>
>
>
> El 25/02/2010, a las 7:32, Jerry Sobieski escribió:
>
>> Hi Tomohiro -
>> This is a very astute observation. Two changes/clarifications need
>> to be made to enable the tree/chain model option:
>>
>> 1.) In order to do tree processing, we need to expand the PO to
>> include the interdomain connector points. The local NSA can invoke an
>> interdomain PathFinder to expand the Path Object. This statement:
>> PO[i] = ConnectRequest( NSA(ingressSTP), ingress > egress);
>>
>> would change to read something like:
>>
>>
>> id-PO = (ingress > egress);
>> /* expand PO = (nextDomain/ingress > nextDomain/exit >
>> anotherDomain/exit > endDomain/egress) */
>> if(method==tree) then id-PO = InterdomainExpansion(ingress > egress);
>> PO[i] = ConnectRequest( NSA(ingressSTP), id-PO );
>>
>> If the local NSA elects to expand the remote PO, we get a tree model
>> PO. If the local NSA does not expand the PO we have a chain model
>> PO. Its up to the local NSA to decide which approach to use.
>>
>> 2.) The only other mod we need is to process each interation of the
>> outer "do{}" block asynchronously - i.e. in parallel. If we are
>> running tree mode, each sub-request is made in parallel; if we are
>> running in chain mode, we do the local reservation and then send teh
>> remaining request downstream. Selecting the correct method will be
>> based on available topo information, complexity of the topology, and
>> utilization rate (resource availability) of the transport plane - a
>> study in best practice.
>>
>>
>> There are some nuances associated with this defined process that I
>> won't elaborate on here, but I believe this pseudo code is [now]
>> basically correct, though there are a few things I would do to clean
>> it up if we were writing real code.
>>
>> I hope this addressed your issue.
>> Jerry
>>
>>
>> Tomohiro Kudoh wrote:
>>>
>>> Hi Jerry,
>>>
>>> I basically agree with your pseudo code. But this else clouse seems to
>>> be based on the chain model and not applicable for the tree model.
>>>
>>>
>>>> else { /* ingressSTP is remote, so forward the sub-request
>>>> to/towards the ingressNSA */
>>>> PO[i] = ConnectRequest( NSA(ingressSTP), ingress > egress);
>>>> }
>>>>
>>>
>>> Tomohiro
>>>
>>> On Tue, 23 Feb 2010 18:20:28 -0500
>>> Jerry Sobieski <jerry at nordu.net> wrote:
>>>
>>>
>>>> A couple things we should also put on a discussion agenda:
>>>> - NSA Connection request handling
>>>> - Connection decomposition and manipulation semantics.
>>>>
>>>> I think understanding these in a clearer detail will aid our
>>>> discussion
>>>> on our topology needs.
>>>>
>>>> So here is a long but hopefully useful proposal for NSA request
>>>> handling. Please try to wade thru the pseudo code below. I think
>>>> this will frame much of our disussions on both topology and
>>>> pathfinding.
>>>>
>>>>
>>>> Upon receiving a Connection Request...
>>>> - The local NSA examines the request and decomposes the request into a
>>>> set of /n/ sub-requests defined by explicit hops in the originating
>>>> PO.
>>>> Each sub-request has only an ingress and egress STP. For example:
>>>> PO={A>B>C>D} decomposes to (A>B, (B>C), (C>D) .
>>>> -
>>>> For each sub-request, do {
>>>> If ( ingressSTP is local )
>>>> then {
>>>> If (egressSTP is local )
>>>> then { /* subrequest is completely local */
>>>> PO[i]= reservePath (localRM, ingress > egress) /* local
>>>> PathFinding */
>>>> }
>>>> else { /* ingress is local, egress point is remote, */
>>>>
>>>> /* Here we split the sub-request into a local segment
>>>> and a
>>>> remote segment */
>>>> find local exitSTP towards remote egressSTP; /* this
>>>> is PF */
>>>> find neighbor entranceSTP == local exitSTP; /* a "Point"
>>>> would work nice here */
>>>> decompose request into LocalSeg:=(ingress>exit) and
>>>> RemoteSeg:=(entrance>egress);
>>>>
>>>> /* process local segment */
>>>> POlocal = reservePath (localRM, ingress > exit) /*
>>>> local
>>>> PathFinding */
>>>> if (POlocal != True) /* a local path was not found to the
>>>> selected exit point */
>>>> then { either try another exit point, or error; }
>>>>
>>>> /* process remote segment */
>>>> POremote = ConnectRequest( NSA(entrance), entrance >
>>>> egress); /* send to neighborNSA */
>>>> if ( POremote != True ) then error; /* the remote
>>>> path
>>>> failed */
>>>> PO[i] = POlocal : POremote; /* concatenate local and
>>>> remote POs */
>>>> }
>>>> }
>>>> else { /* ingressSTP is remote, so forward the sub-request
>>>> to/towards the ingressNSA */
>>>> PO[i] = ConnectRequest( NSA(ingressSTP), ingress > egress);
>>>> }
>>>> }
>>>> } /* end DO */
>>>> - If any PO[] is null/error, then release all good POs, and return
>>>> error
>>>> response to user. /* no complete end-to-end path */
>>>> - Finally, concatenate all the returned result POs = PO[0]:PO[1]: ...
>>>> :PO{n]; and return the result to the requester.
>>>>
>>>>
>>>> Note: the above handling only applies path decomposition semantics to
>>>> the requester's Path Object and distributes the resulting sub-requests
>>>> to/towards NSAs of the ingressSTPs in each sub-request. Except as
>>>> noted
>>>> below, there was really no PathFinding involved.
>>>>
>>>> The one trick in the pseudo code above is where a sub-request is split
>>>> between the local domain (ingressSTP) and a remote domain (egressSTP).
>>>> In this case, we want to decompose this segment further into a purely
>>>> local sub-request (which the local RM can handle), and a purely remote
>>>> sub-request (which we'll send to that NSA). These two segments must
>>>> share an edge point between the local domain and the next adjacent
>>>> domain. To do this, the local NSA must find an "exitSTP" leading
>>>> to the
>>>> remote STP, and insert it into the PO as an explicit intermediate hop.
>>>> Then the sub-request gets decomposed into a wholly local sub-request,
>>>> and a wholly remote sub-request.
>>>>
>>>> The only topology information required to do this local/remote
>>>> decomposition is to know a) which exit point to use, and b) what the
>>>> equivalent [entrance] STP is called in the adjacent domain. The
>>>> latter
>>>> is easy - its exchanged as part of bringing up each inter-domain
>>>> connection and is stored in the local topology DB or peering table.
>>>> But the former, choosing an exit point, is more involved: we could
>>>> either do an exhaustive PathFinder search of the global topology (very
>>>> expensive), or we could accumulate reachability information at each
>>>> edge
>>>> node incrementally as additional topology information is learned (i.e.
>>>> as new STPs and Domains come online.) the reachability info can
>>>> then be
>>>> used to prune the PF search tree vastly improving its effectiveness.
>>>>
>>>> ...how Reachability info gets distributed/learned is not important
>>>> right now, but reachability is one important means of pruning the
>>>> search
>>>> tree in path computations. We could punt and just say "PathFinding
>>>> [magicaly] chooses an exit point" and leave it to the PathFindng
>>>> working
>>>> group to decide the details....
>>>>
>>>> Nevertheless, for NSI, the local NSA must be able to a) map an STP to
>>>> its native domain and thus find and/or establish trust with its
>>>> NSA, or
>>>> b) map an STP to a directly connected intermediary NSA who offers
>>>> to act
>>>> on its behalf. The former method may still not provide enough
>>>> topology info to build a comlete and valid topology graph unless the
>>>> topology offered by the owner NSA is related somehow to topology
>>>> already
>>>> known to be contiguous to local domain. (I.e. a directory look up may
>>>> assign ownership, but doesn't necessarilly provide topology
>>>> information
>>>> relevant to the question at hand...how do I get there?)
>>>>
>>>> So: How does a local NSA find out which NSA "owns" an STP? I assert
>>>> this "ownership" information is really just "reachability"
>>>> information. All the local NSA really needs to now is what is the
>>>> relationship is between an STP and an NSA -> in their own local
>>>> topologyDB <-. To put it another way: the local NSA has some
>>>> view of
>>>> the world as represented in its local topology DB (hopefully this is
>>>> summarized somehow, but in any case, the local topologyDB
>>>> represents all
>>>> that the localNSA knows about the world. ) It may be the case that
>>>> the localNSA learned [somehow] that a domain "Far-Away" is
>>>> connected to
>>>> a domain "NeighborA" which is connected to local Domain. And thru the
>>>> same mechanism learned of a set of STPs that exist in Far-Away. So
>>>> localNSA has a trust relation with NeighborA, but may/maynot have such
>>>> with Far-Away's NSA. It doesn't really matter. When localNSA learns
>>>> of Far-Away, localNSA could try to establish trust. If FarAway
>>>> accepts
>>>> it, then local NSA could pose a tree decomposition across NeighborA
>>>> and
>>>> then across Far-Away. If FarAway does not trust localNSA (or vice
>>>> versa) we can still decompose a chain request to NeighborA who
>>>> evidently
>>>> *does* have a trust relationship with FarAway, and let them work
>>>> things
>>>> out.
>>>>
>>>> A lot of making the tree and chain model workable relies on topology
>>>> distribution protocol... Short of describing that protocol, we can
>>>> identify requirements, and assert that they exist, and based on that,
>>>> the NSI NSA can function thuswise...
>>>>
>>>> Thinks for reading so much technical details...
>>>>
>>>> Jerry
>>>>
>>>> Guy Roberts wrote:
>>>>
>>>>> Jerry,
>>>>>
>>>>>
>>>>>
>>>>> I like what you have done here -- the point is to first state clearly
>>>>> what the NSI 'Connection Service' needs to do, and then to derive the
>>>>> topology requirements from these service functions.
>>>>>
>>>>>
>>>>>
>>>>> Will you be able to make tomorrow's call? I would like to make this
>>>>> make this a topic for discussion.
>>>>>
>>>>>
>>>>>
>>>>> Guy
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> *From:* Jerry Sobieski [mailto:jerry at nordu.net]
>>>>> *Sent:* 23 February 2010 04:46
>>>>> *To:* Guy Roberts
>>>>> *Cc:* Freek Dijkstra; NSI WG
>>>>> *Subject:* Re: [Nsi-wg] NML topology
>>>>>
>>>>>
>>>>>
>>>>> Good idea Guy...I have a couple of posts...here is the first:.
>>>>>
>>>>> I suggest we focus on which NSI service request parameters or
>>>>> semantics have topological significance and what those are. For
>>>>> instance:
>>>>>
>>>>>
>>>>> *1. NSI: A Connection request must, at a minimum, specify the
>>>>> ingress point and the egress point. The Connection request may also
>>>>> specify intermediate transit points for the connection. The
>>>>> semantics of loose hop request is PO={A,B,C}, is equivalent to
>>>>> Connection A>B concatenated with Connection B>C. *
>>>>>
>>>>> Topo Requirement: Each of these "point" identifiers must uniquely
>>>>> determine and map to a location in the transport topology. What is
>>>>> the NSI definition of a "point"used in this context? It seems to
>>>>> correspond to our STP discussion...so we need to decide what a point
>>>>> in the Path Object really refers to topologically.
>>>>>
>>>>>
>>>>> *2. NSI: A Provider NSA is responsible for decomposing the
>>>>> Connection
>>>>> request (into piecewise segments defined by the PO) and forwarding
>>>>> sub-requests to other service agents as it deems appropriate or
>>>>> necessary, and insuring the returned sub-segments can be assembled
>>>>> into a single fully satisfied Connection and returning that
>>>>> Connection
>>>>> result to the Requesting NSA. *
>>>>>
>>>>> Requirement: Define how the NSA handles Connection requests.
>>>>> a) The NSA decomposes the request into a set of sub-segments as
>>>>> defined by the PO.
>>>>> b) The NSA must forward each sub-request to/towards the NSA that
>>>>> owns the ingress STP of the sub-request, /[Here is where topology
>>>>> comes into play - how do we know where to send a request? Must map
>>>>> STP to NSA owner or have reachability in the topology..] /
>>>>> c) If an NSA receives a request whose ingress STP is in the local
>>>>> Domain, the NSA invokes the PathFinder to reserve a Path towards the
>>>>> next STP [/NSA must be able to recognize STPs in its local domain/]
>>>>> d) Upon successful reservation, the returned POs of the
>>>>> sub-requests are merged into a single PO and returned to the
>>>>> originating Requester.
>>>>>
>>>>> *3. NSI: Upon successfull reservation, a Path Object is returned to
>>>>> the user describing the resulting Path. This PO will contain the
>>>>> STPs
>>>>> stipulated by the originating request, and will contain either a)
>>>>> STPs
>>>>> of the as-built Connection, or b) named Path Object(s) for opaque
>>>>> as-built information.*
>>>>>
>>>>> Requirement: Path Object definition. Including opaque Named POs
>>>>> that are only revealed to authorized requesters. A PO must contain
>>>>> STPs, but must also include a Named PO - which must carry some
>>>>> authorization policy. How do these Named POs get resolved? what do
>>>>> they look like, how are names constructed, etc.
>>>>>
>>>>> The above notion that we forward requests from one NSA to another
>>>>> based upon some ownership means we must define that ownership
>>>>> concept. Therein lies the notions of grouping resources into
>>>>> Networks, and a single NSA King for each Network kingdom :-) If STPs
>>>>> are part of that group, what are they and how do we summarize such
>>>>> info?
>>>>>
>>>>> However, we do not have a trust relationship with all NSAs - its
>>>>> scaling problem. We must assume that we will connect directly with
>>>>> some neighbor Networks, and have a trusted relationship with them.
>>>>> But we will not (cannot) directly connect to every network, and
>>>>> therefore some such "far-away" networks will not recognize and trust
>>>>> our local NSA. For these latter cases, the only way we will know of
>>>>> that far-away domain is if one of our direct neighbors offers to act
>>>>> as transit to to Far-Away domain by announcing all or some of
>>>>> Far-Away's topology. In this case, we see far-away, but we must
>>>>> rely
>>>>> on our neighbor to forward any requests to Far-Away. If our NSA
>>>>> encounters an STP that lives in Far-Away, and our peering table has
>>>>> no trust with Far-Away, then we must send our request to our neighbor
>>>>> who acts as intermediary. (In point of fact, our neighbor acts no
>>>>> differently than it would for any other request - it sees the
>>>>> Far-Away
>>>>> STP and forwards the request likewise.)
>>>>>
>>>>> This may generate another topology requirement- that of reachability.
>>>>> I.e. how do we describe the set of points (STPs) reachable within (or
>>>>> through) a given domain? We have to recognize that our reachable
>>>>> end
>>>>> systems or STPs will almost immediately be counted in the thousands.
>>>>> We probably need some sort of hierarchichal naming scheme.
>>>>>
>>>>> thoughts?
>>>>> Jerry
>>>>>
>>>>>
>>>>> Guy Roberts wrote:
>>>>>
>>>>>
>>>>> I suggest the following 10 requirements as a starter:
>>>>>
>>>>> Requirement 1: The model should be able to describe a grouping of
>>>>> network resources that are owned and controlled by a single
>>>>> provider or NSA. (I will call this a NETWORK for the moment)
>>>>>
>>>>>
>>>>> Requirement 2: The model should be able to describe a grouping
>>>>> of NETWORKs. (e.g. a federation of providers with shared policy)
>>>>>
>>>>> Requirement 3: The model should be able to describe resources
>>>>> (ports/points) in a NETWORK that are available for connecting to
>>>>> other NETWORKs. (I will call this a network connection point NCP
>>>>> for the moment)
>>>>>
>>>>> Requirement 4: These NPs should be able to be performed at the
>>>>> end of a link that is internal to the domain as well as to ports
>>>>> on a device. (in my opinion the NCP on a link requirement needs a
>>>>> use-case)
>>>>>
>>>>> Requirement 5: The model should be able to describe an
>>>>> arbitrary number of layers of logical ports within a NCP.
>>>>>
>>>>> Requirement 6: The model should be able to describe
>>>>> connectivity between NETWORKs. (I will call this inter network
>>>>> connection (INCs) for the moment)
>>>>>
>>>>> Requirement 7: The model should be able to describe groups of
>>>>> INCs.
>>>>>
>>>>> Requirement 8: The resources that make up INCs should have
>>>>> ownership by a clearly identifiable provider. (i.e. resources
>>>>> without NSA ownership are not allowed). (note: Does this also
>>>>> include the patch cord between providers?)
>>>>>
>>>>> Requirement 9: The model should allow policy to be assigned to
>>>>> INCs, even where the INC is wholly or partly made up of passive
>>>>> resources.
>>>>>
>>>>> Requirement 10: The model should be able to fully describe a
>>>>> circuit (i.e. NSI service) that transits the topology.
>>>>>
>>>>>
>>>>>
>>>>> Any thoughts on these and other requirements would be helpful.
>>>>>
>>>>>
>>>>>
>>>>> Guy
>>>>>
>>>>>
>>>>>
>>>>>
>>>>>
>>>>> -----Original Message-----
>>>>>
>>>>> From: Freek Dijkstra [mailto:Freek.Dijkstra at sara.nl]
>>>>>
>>>>> Sent: 22 February 2010 13:52
>>>>>
>>>>> To: NSI WG
>>>>>
>>>>> Cc: Guy Roberts; Jeroen van der Ham; John Vollbrecht
>>>>>
>>>>> Subject: Re: [Nsi-wg] NML topology
>>>>>
>>>>>
>>>>>
>>>>> Can I summarize this discussion as follows?
>>>>>
>>>>>
>>>>>
>>>>> Requirement: It should be possible to assign a policy to an
>>>>>
>>>>> (interdomain) link.
>>>>>
>>>>>
>>>>>
>>>>> Of course, I can think of a solution (e.g. make that link part
>>>>> of a
>>>>>
>>>>> topology, like John's second picture, assign the topology to a
>>>>>
>>>>> networkdomain, and assign a policy to that networkdomain).
>>>>> However, this
>>>>>
>>>>> seems out of scope. I think the best way forward is to
>>>>> describe this and
>>>>>
>>>>> other requirements and forward them to the NML and ask the NML
>>>>> folks to
>>>>>
>>>>> come up with a solution for the requirement. I also
>>>>> wholeheartedly
>>>>>
>>>>> invite all NSI group members to become a "NML folk" too by
>>>>> joining the
>>>>>
>>>>> NML list!
>>>>>
>>>>>
>>>>>
>>>>> Regards,
>>>>>
>>>>> Freek
>>>>>
>>>>> _______________________________________________
>>>>>
>>>>> nsi-wg mailing list
>>>>>
>>>>> nsi-wg at ogf.org <mailto: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
>>>
>> _______________________________________________
>> 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/20100227/0ceca7c8/attachment-0001.html
More information about the nsi-wg
mailing list