[Nsi-wg] NML topology
"Joan A. García-Espín"
joan.antoni.garcia at i2cat.net
Thu Feb 25 12:43:27 CST 2010
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
More information about the nsi-wg
mailing list