Subject: [alto] Comment on http://www.ietf.org/id/draft-roome-alto-incr-updates-01.txt

From: "Y. Richard Yang" <[email-masked]>
Date: Thu, 3 Jul 2014 01:57:12 -0400

Hi Wendy, Nico,

Thank you so much for posting
http://www.ietf.org/id/draft-roome-alto-incr-updates-01.txt

I read the document and it is a quite interesting design. In particular, I
enjoyed reading the new design of Sec. 3 and the discussions on alternative
design, in particular on JSON Patch, in Sec. 6.

A key issue that your draft investigates and hence contributes to is an
encoding scheme for updates, i.e., how to convey the diff between two
versions of the same information resources. Since IETF has already defined
JSON Patch as a general mechanism for this purpose (a patch is a sequence
of operations applied on a tree to obtain a second tree), it will be a
major candidate. However, for both Network Map and Cost Maps, your document
makes a case that JSON Patch may not be a good match.

One suggestion is whether we can identify the general issues on JSON Patch
so that the document provides a principled design that others may use as
well, given the wide use of JSON.

Here is my understanding of some principles:

- Type preservation: JSON Patch allows arbitrary transformation from one
data tree and another tree. This is reasonable for a Web doc as it changes
its layout. But for most network systems, I do not see the need. As someone
who prefers strong-typed systems, I do not like this capability. Hence, a
JSON Patch based design needs to forbid many of the operations allowed by
JSON Patch to preserve the type system. Your design achieves this goal. In
particular, I found the idea of using the same tree to transport update
operations interesting.

- Completeness: Assume type-preservation, we should be able to change from
one valid object of a given type to another of the same type. Does the
current system achieves completeness? First consider Network Map. Below is
an example.

========network map=========
{
     "meta" : {
       "vtag" : {
          "resource-id": "my-default-network-map",
          "tag": "c0ce023b8678a7b9ec00324673b98e54656d1f6d"
       }
     },
     "network-map" : {
       "PID1" : {
         "ipv4" : [
           "192.0.2.0/24",
           "198.51.100.0/24"
         ]
       },
       "PID2" : {
         "ipv4": [
           "198.51.100.128/24"
         ]
       }
     }
   }

I see that in a type-preserving setting, we need to support only the
following:
1. change the vtag value
2. change the values under network-map. I see that {add_PID and delete PID}
will be a complete set already, and you have more. Hence, your design is
complete.

- Efficiency: Do you allow efficient encoding to change from one to the
other?

Consider the operation of renaming a PID. This can be achieved by delete
old and then add back with a new name. But this is inefficient. It is not
clear to me that your design achieves efficiency, for example, for this
operation. Of course, if you consider this as an uncommon operation, then
there is no need to add shortcuts for this. See more discussion below.

Consider the operation of moving a set S1 of prefixes from PID1 to PID2. I
believe that this can be a common type of operation. I see that your design
can use
network-map-add(PID1, S1) and network-map-delete(PID2, S1) to achieve the
goal.

- Generics. My main concern is that the operators introduced in this
document (network-map-add, and network-map-delete) are too type (i.e.,
network-map) specific. Hence, for each new type (Network Map, Cost Map,
...), there might be a need to introduce new operators. Can we have a
generic-based design?

Assume that we have a data tree T, and we want to change it to T'. Assume
the following:
1. type-preservation (T and T' are the same type);
2. unambiguity key (for each node in T or T', its direct children all have
distinct value)

Consider node n. For each child of n, say nc, there is an edge labeled with
the key (if n is an array, we consider the label as the value of the child
in this setting).
All keys should be different under our unambiguous key assumption.

We need to encode three cases:
- add the new nc and its edge
- delete nc and the edge
- change the edge label (key) from n to nc

 Hence, the example in your doc becomes (// is my comment):

{
     "meta" : {
       "vtag" : {
          // deleted as no change below "resource-id":
"my-default-network-map",
          "tag": "newc0ce023b8678a7b9ec00324673b98e54656d1f6d"
       }
     },
     "network-map" : {
       "PID1" : {
         "ipv4" : [
           -"192.0.2.0/24",
         ]
       },
       "#PID2#PIDX" : {   // rename PID1 as PIDX
         "ipv4": [
           + "192.0.2.0/24",
         ]
       }
     }
   }

In other words, just appearance of a leaf value indicates overwrite, +/-
indicates add/delete, and #OLD#NEW indicates change key. Hence, your Cost
Map design still works (see below).

Does the preceding make sense?

Richard

======cost map=========
HTTP/1.1 200 OK
   Content-Length: 435
   Content-Type: application/alto-costmap+json

   {
     "meta" : {
       "dependent-vtags" : [
         {"resource-id": "my-default-network-map",
          "tag": "3ee2cb7e8d63d9fab71b9b34cbf764436315542e"
         }
       ],
       "cost-type" : {"cost-mode"  : "numerical",
                      "cost-metric": "routingcost"
       }
     },
     "cost-map" : {
       "PID1": { "PID1": 1,  "PID2": 5,  "PID3": 10 },
       "PID2": { "PID1": 5,  "PID2": 1,  "PID3": 15 },
       "PID3": { "PID1": 20, "PID2": 15  }
     }
   }

---

From: "Y. Richard Yang" <[email-masked]>
Date: Thu, 3 Jul 2014 02:04:54 -0400

On Thu, Jul 3, 2014 at 1:57 AM, Y. Richard Yang <[email-masked]> wrote:

> 2. change the values under network-map. I see that {add_PID and delete
> PID} will be a complete set already, and you have more. Hence, your design
> is complete.
>
> Consider node n. For each child of n, say nc, there is an edge labeled
> with the key (if n is an array, we consider the label as the value of the
> child in this setting).
A comment is that one may look at the preceding design as combining two
ideas: (1) encoding the diff tree using common prefix; and (2) using the
original data schema (with some omissions) to enforce type. If the overall
scheme is OK, we need to hammer out the details of encoding +, -, and ##.

Cheers,

Richard