Subject: RE: [Simple] collection template

From: Adam Roach <[email-masked]>
Date: Tue, 17 Sep 2002 10:58:25 -0500

> -----Original Message-----
> From: Paul Kyzivat [mailto:[email-masked]]
> 
> > > It could be improved vastly in some cases if many collections
> > > have elements in common, and the server is permitted to
> > > multiplex one subscription to a collection element across
> > > many containing collections. Moreso if the lifetime of the
> > > subscriptions the collection server makes are independent of
> > > those to the collections it serves.
> > 
> > After studying this problem for an extended period of time, I
> > have reached the conclusion that this sort of aggregation doesn't
> > generally work. The permissions problems that arise from doing
> > this are pretty much intractible unless you make some walled-
> > garden type assumptions about how servers are going to protect
> > the data they receive in this way.
> 
> I'm inclined to agree, but I keep looking for a way to make 
> it work, because otherwise there are significant scaling 
> problems with highly interconnected collections of users - 
> its something like O(n^2).

That's true. It's a general truth that comes with any model of
presence that allows users to set policy that is different
for different sets of watchers, regardless of whether you
use collections. Let's consider a system of two servers,
each of which has three clients. Each client has a subscription
to all five other clients.

With collections, the number of subscriptions between each
node is as follows:

        +----+        18        +----+
        | S1 |------------------| S2 |
        +----+                  +----+
     2 / 2|  2\               2/ 2|  2\
      /   |    \              /   |    \
+----+  +----+  +----+  +----+  +----+  +----+
| C1 |  | C2 |  | C3 |  | C4 |  | C5 |  | C6 |
+----+  +----+  +----+  +----+  +----+  +----+

Each client has a collection subscription to its server; each
server has either a non-collection subscription to each of its
clients or a publication relationship. I'm going to consider them
to be about as heavy as each other. I'm making an assumption that
clients trust their own server to honor their privacy policies,
instead of implementing all privacy at the peer level.

Given these assumptions, we have a total of 30 subscriptions
in the system. It should also be obvious, as you state, that
the number of subscriptions in the system increases at the rate
of about O(n^2).

Now, let's look at the same system without collection subscriptions.
(Sorry; the limitations of ASCII art show up here).

                 ----------------------
                /3                     \
               /        +----+  +----+  +----+
              /  -------| C4 |  | C5 |  | C6 |
             /  /3      +----+  +----+  +----+
            /  /             3\/ 3|   3/
           /  /            3  /\  |   /
        +----+----------------  +----+
        | S1 |   ---------------| S2 |
        +----+  /3      --------+----+
      3/ 3|  3\/       /3      /
      /   |   /\      /       /
+----+  +----+  +----+       /
| C1 |  | C2 |  | C3 |      /
+----+  +----+  +----+     /
      \                  3/
       -------------------

Here, each client has two subscriptions to its local server
(one for each other client attached to that server), and the
server has either a subscription to or a publication relationship
with each of its clients. Each client additionally has three
subscriptions to the remote server (one for each of its clients),
leading to 18 interdomain subscriptions (exactly like before).
In total, then, this system -- the one without collections --
has 36 total subscriptions. It should also be obvious that this
system will increase the total number of subscriptions at the
rate of approximately O(n^2).

So, yes, you've hit on the fundamental scaling problem inherent
in presence systems. Collections neither worsen nor significantly
improve this. What collections *do* accomplish is reduction of
the traffic from the client to the server. If you go through
the excercise of increasing the size of the systems I've diagrammed
above, you'll notice that the system with collections keeps the
relationship between the client and the server(s) to 2
subscriptions (or one subscription and one publication relationship),
while the system without collections increases this realationship
linearly as you add users.

> There is a permissions problem even if you don't aggregate 
> this way. In order for the permissions to be evaluated in a 
> straightforward way, the server for a collection will need to 
> represent itself as the user who subscribed to the 
> collection, or as an agent that has been explicitly 
> authorized to act on behalf of that user. I don't see an 
> obvious way to do that other than for each user to provide 
> the collection server with one of his secret keys, or else to 
> have the end user sign a certificate for the collection server.

Now this *is* an interesting problem. If this problem is
tractible (and it feels like it should be), then we're home
free. I'll leave it to the security guys to comment on whether
this sort of limited delegation is something that's feasible.

/a

---

From: Paul Kyzivat <[email-masked]>
Date: Tue, 17 Sep 2002 14:29:07 -0400

Adam,

Nice ascii art! (It's too much work, so I avoid it when I can.)

I've extracted portions of your message and commented on them below.

	Paul

> this sort of limited delegation is something that's feasible.

I think you partially misunderstood me, or else I misunderstand you. I think there is a problem getting the setup from your first picture to work at all.

> Let's consider a system of two servers,

If I understand your intent, S1 is both a presence server for C1..C3 and a server for the collections that C1..C3 use, and similarly for S2 and C4..C6.

So lets pick one case out of this. C1 has a subscription to a collection hosted by S1 that references the presence of C2...C6. To honor this one of the things S1 does is make a subscription to S2 regarding C4.

Now S2 is acting on behalf of C4 in this case, and needs to identify who the subscriber is in order to decide whether to accept it and what information to divulge. S1, acting on behalf of C1, needs to identify who is making the request, presumably using the From header and some credentials.

So, what does S1 put in the From header, and what credentials does it use? 

For the From header there are two obvious possibilities: the URI of C1 or the URI of S1. The credentials could be unique to C1, or might only identify S1. There are then four possible combinations of these:

	From	Credentials
	----	-----------
1)	C1	C1
2)	C1	S1
3)	S1	C1
4)	S1	S1

At least one of the two needs to identify C1, so the proper access decision can be made, which excludes (4).

Case (2) is appealing because it doesn't require S1 to hold separate credentials for every client it serves. But it is pretty dicey too because it is difficult for S2 to know whether to accept it as a valid credential for C1.

For either (1) or (3) S1 must hold credentials and the corresponding secret for each client serves. (This starts to get into the area that John Ramsdell has been concerned with.) If C1 is going to let S1 have such credentials, there probably must be limitations on them. C1 isn't going to want to let S1 do anything and everything on its behalf. It is going to want to restrict S1 to doing certain things - in this case simply subscribing to presence, possibly with further restrictions.

Then of course S1 must obtain the credential it uses to act on behalf of C1 somewhow, and S2 must know how to recognize such a credential and decide whether to honor it. This all adds complexity to the use of collections. (Whether they are templates or not.)

Do you see a reasonable way to approach this problem of credentials? 

An alternative is to simple have collection servers act on their own behalf. The server could use its own identity to subscribe to the members of a collection, and could make its own decisions about who to accept collection subscriptions from. Done this way, the members of all the collections it serves can be pooled, with a single subscription to each regardless of how many clients it serves. The major limitation of this approach is that all clients of the same collection server don't have their own identity exposed to and taken into account by the specific collection members. The main advantages are a simplification in the security model and possibly a large reduction in the total number of subscriptions and notifications in the system.

Clearly this model wouldn't work for all applications. But it might work in some important cases. Whether these cases are important enough to pursue is questionable.

> this sort of limited delegation is something that's feasible.

I'd like to hear from them too, because I am pretty naive about security.

But I don't see what your plan of attack is if this *isn't* tractible.

	Paul