Re: [alto] Graph representation format deliverable as WG item

[Kai Gao <[e-mail]>]

Hi all,

I'd like to share with you some thoughts on the graph representation. 
Please see below.

As stated in RFC 7285 section 5.1:

>   The definition of ALTO network maps is based on the observation that,
>   in reality, many endpoints are near by to one another in terms of
>   network connectivity.  By treating a group of nearby endpoints
>   together as a single entity, an ALTO server indicates aggregation of
>   these endpoints due to their proximity.  This aggregation can also
>   lead to greater scalability without losing critical information when
>   conveying other network information (e.g., when defining cost maps).

A major motivation for introducing PID is to allow an ALTO server to 
"aggregate these endpoints due to their proximity". Thus, we should 
consider endpoints which belong to the same PID but are not "near" as a 
result of bad aggregation. In this case, not only a path vector cannot 
be represented in a reasonable way, all routing costs can become less 
useful.

Given that a bad aggregation harms the efficacy of ALTO, I think we 
should have a consensus that it SHOULD be avoided. At least, endpoints 
within the same PID SHOULD be "close" in terms of the cost types 
provided in an associated cost map.

Therefore, I feel the question should be asked in the opposite way: how 
do we aggregate the endpoints so that path vectors between these PIDs 
make sense?

For example, if path vectors represent AS paths, PIDs can be aggregated 
by prefixes with the same AS path. If path vectors represent paths in an 
L2 network, PIDs should probably be aggregated by the attachment point 
or gateways.

I think we can emphasize this as a "guideline" or "best practice" for 
servers providing path vectors, because the aggregation requires domain 
knowledge and may vary in different scenarios.

Regards,
Kai
On 03/07/2017 08:32 AM, Jensen Zhang wrote:
> Hi all,
>
> We almost finish the update of path-vector draft. But here is a 
> question I feel we need to discuss:
>
> Shall we query the path vector between PIDs?
>
> Because PIDs can be defined for many different reasons. The endpoints 
> in the same PID may not be nearby. Even we consider the simplest use 
> case, every PID is an AS, there may be still different routings 
> between different ASes for loading balancing. So how to return the 
> routing information by just using a path vector?
>
> A simple solution is to introduce a new cost-mode (Maybe "path-graph" 
> as Sabine proposed). But I believe the cost value of path-graph will 
> be complex.
>
> In my opinion, if we want to provide the routing information, i2rs has 
> done a good job. So I think the advantage of ALTO is simple. 
> Applications can query the necessary routing state information from 
> ALTO in a very simple way.
>
> Any comments?
>
> Thanks,
> Jensen
>
> On Sun, Mar 5, 2017 at 12:34 PM, Jensen Zhang 
> <[e-mail] <mailto:[e-mail]>> wrote:
>
>     And I want to involve Wendy into this discussion since I remember
>     we discussed the unified cost schema. About the cost schema for
>     path-vector, I have three options here:
>
>     Option1: (Legacy schema)
>
>     ---
>     pids:
>       srcs: [PID1, PID2]
>       dsts: [PID1, PID2, PID3]
>
>     Option2: (Basic flow-based schema)
>
>     ---
>     pid-flows:
>       - src: PID1
>         dst: PID1
>       - src: PID1
>         dst: PID2
>       - src: PID2
>         dst: PID3
>
>     Option3: (Advanced flow-based schema)
>
>     ---
>     flows:
>       flow1:
>         ip_src: 10.10.1.0/24 <http://10.10.1.0/24>
>         tcp_port_src: 54321
>         ip_dst: 10.10.101.0/24 <http://10.10.101.0/24>
>         tcp_port_dst: 8080
>       flow2:
>         ip_src: 10.10.2.0/24 <http://10.10.2.0/24>
>         tcp_port_src: 54321
>         ip_dst: 10.10.102.0/24 <http://10.10.102.0/24>
>         tcp_port_dst: 8081
>
>     Option1 and Option2 are acceptable for CM/FCM/ECS now because it
>     will not change the schema of response. But I think Option2 and
>     Option3 are more useful for path-vector. Do you have some good
>     suggestions?
>
>     Thanks,
>     Jensen
>
>     On Sun, Mar 5, 2017 at 12:14 PM, Jensen Zhang
>     <[e-mail] <mailto:[e-mail]>>
>     wrote:
>
>         Hi Sabine,
>
>         Wonderful! Actually, I'm working with Dawn recently and hoping
>         to update the draft-yang-alto-path-vector. About your
>         suggestions, I have some comments. See below.
>
>         Best,
>         Jensen
>
>         On Sat, Mar 4, 2017 at 1:44 AM, Randriamasy, Sabine (Nokia -
>         FR) <[e-mail]
>         <mailto:[e-mail]>> wrote:
>
>             Hi Dawn and Jensen, path-vector authors and all,
>
>             Thanks a lot for resuming the discussion on the
>             “path-vector” mode. I also read your e-mails on the
>             “Problems of encoding path-vector in multi-cost”
>             discussions. Before answering, I needed to clarify on the
>             proposed designs on path-vector.
>
>             So below I have some suggestions for the path-vector
>             extensions design on which I would like your feedback.
>
>             I will feel more comfortable to resume the discussion on
>             “Problems of encoding path-vector in multi-cost”, if I
>             rely on the proposed design. I do not yet include the
>             RSADE in this discussion.
>
>             Thanks,
>
>             Sabine
>
>             I rely on the presentation that was done at the IETF96
>             ALTO session in Berlin last July and exposes a different
>             design for the , see
>             https://www.ietf.org/proceedings/96/slides/slides-96-alto-6.pdf
>             <https://www.ietf.org/proceedings/96/slides/slides-96-alto-6.pdf>
>
>
>             Slides 16 and 17 expose responses with particular fields
>             for the Filtered Cost Map service:
>
>             ------------------------------------------------------------------
>
>             …
>
>             "cost-type" : {“cost-metric”: *“ane”*, *"cost-mode" :
>             ”path-vector” *}
>
>             …
>
>             "cost-map" : {
>
>             "PID1": { "PID1":[], "PID2":["ne56", "ne67"], "PID3":[],
>             "PID4":["ne57”]},
>
>             "PID2": { "PID1":["ne75"], "PID2":[], "PID3":["ne75"],
>             "PID4":[]}, …
>
>             ….
>
>             “nep-map”: (full nep values or reference to map in “meta”)
>
>             ------------------------------------------------------------------
>
>
>         I think "ane" in slides 16 and 17 means the abstract network
>         element. It should be computed by the RSA algorithm.
>
>             The design of the "cost-type" field looks more in line
>             with the ALTO logics. A Cost Map exposing a sequence of
>             “anes” hints that “the requested metric was “ane”.
>             However, I understand that the motivation of the design
>             proposed in
>             https://tools.ietf.org/html/draft-yang-alto-path-vector-03
>             <https://tools.ietf.org/html/draft-yang-alto-path-vector-03>
>             is to condense “bw” information with path vectors and
>             avoid a separate query for “ane” properties.
>
>
>         As I mentioned above, "ane" is computed by RSA.
>
>         If we don't use RSA here, let's think about the basic
>         path-vector. I think the result of path-vector is independent
>         of the cost-metric like "bw" or "delay". So I suggest we just
>         define "ne" or "link" as the cost-metric when we use
>         path-vector as the cost-mode.
>
>             So how about requesting sets of “ane” properties such as
>             e.g. “bw” and “delay” by adding a filtering constraint in
>             a Filtered Cost Map request? I think the same would hold
>             for the Endpoint Cost Service.
>
>
>         If we use RSA, (it's that we use "ane" as the cost-metric)
>         "ane-properties" is an acceptable solution. But the problem is
>         how to handle "constriants". I'm glad to borrow the design of
>         multi-cost. So we can use "testable-cost-types" instead of
>         "ane-properties". Is it acceptable?
>
>             The query for a FCM with the path-vector specific input
>             could look as follows.
>
>             Forgive syntax errors and field names are examples.
>
>             ------------------------------------------------------------------
>
>             POST /path-vector/costmap/filtered HTTP/1.1
>
>                Host: alto.example.com <http://alto.example.com>
>
>             Accept:
>             application/alto-costmap+json,application/alto-error+json
>
>             Content-Type: application/alto-costmapfilter+json
>
>             Content-Length: ###
>
>                {
>
>             "cost-type" :
>
>                    {"cost-mode": "path-vector", "cost-metric": "ane"},
>
>             "ane-properties" : ["bw", "delay"],
>
>             "pids" : {},
>
>             "path-pids" : [
>
>             {"srcs" : [ "PID1" ], "dsts" : [ "PID1", "PID2", "PID3",
>             "PID4" ]},
>
>             {"srcs" : [ "PID2" ], "dsts" : [ "PID1", "PID2", "PID3",
>             "PID4" ]}
>
>                  ]
>
>                }
>
>             ------------------------------------------------------------------
>
>             The response would be as suggested by Richard’s
>             presentation mentioned above.
>
>             With several (src, dsts) pairs in the input, we would not
>             avoid introducing a new mime type, but the differences
>             would be reasonable.
>
>             As for the option between including the “nep-map” and
>             values or referencing it in the meta, it depends on the
>             “nep-map” size. Specifying the input member names in
>             accordance with the Unified Properties extensions proposed
>             in
>             https://tools.ietf.org/html/draft-roome-alto-unified-props-01
>             <https://tools.ietf.org/html/draft-roome-alto-unified-props-01>
>             may allow a fast generation of request for “ane”
>             properties values.
>
>
>         Agree. Actually, we are going to use the unified-props to
>         define "nep-map". So we can query "bw" or "delay" by Filtered
>         Property Map service. If we use "constraints" and
>         "testable-cost-types" in FCM, the property names in "nep-map"
>         should match the names in "testable-cost-types".
>
>         But for "ane", every query may generate a new "anep-map".
>         Although you may send the same query by twice, the ALTO server
>         may have to generate two different "anep-map"s rather than
>         only updates the "ane" properties values. That's the only
>         consideration from me. However, it is implementation-related.
>         We can ignore this issue first.
>
>             *From:*Jensen Zhang [mailto:[e-mail]
>             <mailto:[e-mail]>]
>             *Sent:* mardi 28 février 2017 13:22
>             *To:* Randriamasy, Sabine (Nokia - FR)
>             <[e-mail]
>             <mailto:[e-mail]>>
>             *Cc:* Gurbani, Vijay (Nokia - US)
>             <[e-mail]
>             <mailto:[e-mail]>>; Y. Richard
>             Yang <[e-mail] <mailto:[e-mail]>>;
>             [e-mail]
>             <mailto:[e-mail]>;
>             [e-mail]
>             <mailto:[e-mail]>;
>             IETF ALTO <[e-mail] <mailto:[e-mail]>>
>             *Subject:* Re: [alto] Graph representation format
>             deliverable as WG item
>
>             Hi Sabine,
>
>             I just noticed your were trying to resume this discussion.
>             Thanks a lot for your effort! And I really would like to
>             share my opinion about issue 2 since it is related to the
>             flow-based design. See below:
>
>             On Sat, Nov 19, 2016 at 1:45 AM, Randriamasy, Sabine
>             (Nokia - FR) <[e-mail]
>             <mailto:[e-mail]>> wrote:
>
>                 Hello authors of path vector and RSADE extensions and all,
>
>                 Both drafts address several emerging use cases, in
>                 particular, the multi-path 1st hop, where each hop
>                 corresponds to a different choice of access technology.
>
>                 I'd like to resume the discussion started in
>                 IETF96-Berlin upon Richard's presentation, see
>                 https://www.ietf.org/proceedings/96/slides/slides-96-alto-6.pdf
>                 <https://www.ietf.org/proceedings/96/slides/slides-96-alto-6.pdf>
>
>                 - issue 2 slide 12: multiple (S,D) pairs (with S and D
>                 = sets) in a query is more than useful.
>                 Is there a way to allow this as well for "regular" ECS
>                 and F/CM ? Can we apply this to both "flows/endpoints"
>                 and "PID-paths" ?
>
>                 - issue 2 design choices: a smooth transition would be
>                 using native cost maps with multiple input several
>                 (S,D) pairs.
>
>             If I get your point, you are suggesting to use the
>             solution like this: (right?)
>
>             "cost-map": {
>
>             "SPID1": {
>
>             "DPID1": xxx
>
>             },
>
>             "SPID2": {
>
>             "DPID2": yyy
>
>             }
>
>             }
>
>             If so, it still cannot handle the fine-grained flow (such
>             as L4 routing). Although Richard's presentation did not
>             mention the fine-grained flow, it is the actual motivation
>             of introducing flow-based design.
>
>             I think the most important use case of flow-based design
>             is the central flow-level scheduling. It will often appear
>             in the central controlled network like SDN. So the flow is
>             usually fine-grained. I know introducing flow-based design
>             is a big change for ALTO. But if it is really important, I
>             think we need to try it out.
>
>                 - Cost metric and mode for "ane-aware paths":
>                 Slide 17 illustrates for a (S,D) pair: metric = "ane",
>                 mode = "path-vector" = array of N >= 1 "ane"
>                 Other modes could be:
>                 - mode = "path-graph", (multiple path-vectors - for
>                 RSADE or multi-choice paths)
>                 - mode = "path-e2e" (single switch N=0 base ALTO mode
>                 usually not used),
>
>             You mean (mode = "path-graph") === (mode = "path-vector",
>             metric = "ane")?
>
>
>                 - conveying ane costs and properties (slides 15, 16,
>                 17) on multi-hop maps:
>                 In any case, ane property/cost services need to be
>                 specified and indicated in the IRD so that the client
>                 understands what "ne24" points to. So I suggest the
>                 anep-map to be systemetically referenced in the
>                 dependent-vtags. As for nep-map values:
>                 - inline: information is self-contained and saves
>                 round trips but response may be heavy
>                 - reference: ALTO Client gets anep map separately if
>                 needed.
>
>             If we don't use ane, "reference" can be accepted. Because
>             every query can share the same network elements. But ane
>             is computed from the query input of RSADE. e.g. Query1 may
>             send request [(s1, d1), (s2, d2)] and get the response
>             {f1: [ane1, ane2], f2: [ane2, ane3]}; Query2 may send
>             request [(s1, d1), (s3, d3)] and get the response {f1:
>             [ane1', ane2', ane3'], f3: [ane1', ane4']}. For f1, [ane1,
>             ane2] and [ane1', ane2', ane3'] should be the same route,
>             but the result computed by ALTO server may be different.
>             So it is hard to be referenced in the "dependent-vtags".
>
>                 How about letting a Server decide what option to propose?
>                 A Server may even directly integrate the cost values
>                 in a multi-cost response, provided it has specified a
>                 anep-map and references it in its response.
>
>             I am thinking about this approach. But how can a client
>             know which option the server are using? Maybe add this
>             claim into the "capability" of the IRD entity?
>
>
>                 If for instance a client requests metric "BW" in
>                 "path-vector" mode, the protocol may request that it
>                 also requests metric "ane" in this mode (same for
>                 "path-graph" mode).
>
>             I think "ane" is not designed clearly. Let me resume the
>             discussion about issue 1 here: how to encode the
>             cost-type? Maybe we really need a unified cost schema.
>
>
>                 Does this make sense ?
>
>                 Thanks,
>                 Sabine
>
>             Looking forward to receiving comments from authors. I
>             think both drafts are still valuable. We need to update them.
>
>             Best,
>
>             Jensen
>
>
>
>