Subject: [P2PSIP] More thoughts on clients, peers, and services, and service routing

From: Dean Willis <[email-masked]>
Date: Wed, 21 Nov 2007 16:03:17 -0600

In the voluminous discussion of the last 36 hours, I think I'm seeing  
an alternative emerge that I will try and restate.

One way to divide the problem space is to differentiate the tasks of  
"finding", "routing", and "everything else".

Several people have proposed that peers exclusively provide "finding  
and routing" services. Clients use the "finding and routing" services  
of peers. Both clients and peers can also offer other services, such  
as STUN relay (although some might say that peers offering other  
services are acting as clients when they do so).  I think this model  
works fairly well, and it continues in the principle that peers are a  
superset of clients -- that is, that clients and peers are pretty  
much similar, but peers do a few things that clients can't. For each  
service that a client or peer provides, that node would "put" a  
service entry in to the database, and these services are completely  
distinct from the nodes role as peer or client

Is this the only way to divide the problem? Maybe clients and peers  
are very different things, neither subsets nor supersets of each other.

What if peers deal exclusively with "finding", and we think of  
message routing as a separate service entirely?

In this approach, one could ask a peer "Please store this resource  
record" or "Please fetch this resource record", but not "Please send  
this message to [email-masked]".

How would this facilitate setting up SIP sessions?

Alice might request that the overlay store as a resource record, a  
route to "[email-masked]", where that route might include not only  
Alice's "contact", but also hops for nodes that have agreed to serve  
as relays for sending messages to Alice. This is somewhat analogous  
to the "path" and "service route" terminology in SIP. We can think of  
this as a "put" operation against the distributed database.

To call Alice, Bob would then simply do a "get" operation, requesting  
a route to "[email-masked]". He would then use the result as a SIP  
route vector to send an INVITE request to Alice.

Both of these require some sort of convention for constructing the  
resource-ID for the route record, but that's fairly trivial.

The harder parts: How would Alice discover an appropriate vector? And  
how do we compensate for the fact the ideal route between Bob and  
Alice might be different than the route between Charlie and Alice?

Of course, before Alice can find "routing" nodes in the database,  
those nodes have to list themselves. Each one might start by finding  
a primal node (a "routing bootstrap", if you will) and making ICE  
checks against that node. If they can reach it and it can reach them,  
they consider themselves "tier-1" nodes, and "put" resource records  
listing themselves as tier-1 nodes. If not, then they query the  
database for tier-1 nodes, perform ICE checks against them, and add  
resource records listing themselves as tier-2 nodes adjacent to the  
tier-1 nodes which which they have mutual reachability. If they  
aren't adjacent to any tier-1 nodes, then they repeat for tier-2,  
then tier-3, and so on. Of course, it would be nice if the  
distributed database offered some technique for automagically scoping  
the candidates, but it isn't required for the algorithm to terminate.  
Optionally, routing nodes could do persistent "outbound"-like  
bindings with some higher-tier node selected as the most-adjacent  
node they can reach, thereby either short-circuiting the search  
process or achieving connectivity across NAT/FW boundaries that block  
reverse-path checks. One could further short-circuit the process by  
using broadcast and multicast to find neighbors that have already  
established their vectors, then copying those vectors rather than  
finding new ones.

Alice might begin by querying the distributed database for nodes  
offering the "routing" service, thereby obtaining a list of candidate  
nodes. She might then do something like an ICE-like evaluation to  
find one or more acceptable candidates, and would select the lowest- 
tiered node she could reach. Of course it would be nice if the  
distributed database could help narrow this search, but it isn't  
absolutely required. Alice would continue working up the tiers until  
reaching tier-1, then "put" a vector or into the database, where that  
vector lists Alice's contact plus the URIs of each routing node up to  
and including her tier-1 contact.

Bob, when calling Alice, would "get: her vector, then run a shortest- 
path calculation between his vector and her vector, then use the  
result as a SIP route to reach Alice.

What we get out of this is a system where the distributed database  
can be any off-the-shelf DHT (such as OpenDHT), and where SIP  
messages are routed according to what is in effect a minimum spanning  
tree calculation against the sip-routing topology of the network.

Alternatively, we could do subtree and named-subtree (dynamic  
aggregation) approaches that would provide absolutely optimal routes  
but have higher overheads. Think OSPF, but where aggregations (OSPF  
areas) are defined dynamically vice ICE-like adjacency checks.

This is a little different from the current proposals, which seem to  
require a customized DHT algorithm and and routes messages across  
that DHT based on the dynamic topology of the DHT itself and is  
likely to give a much less efficient a route. Of course, the route  
discovery process (especially in the event of a topology change) is  
much easier. On the other hand, the DHT topology tells us little or  
nothing about net-path efficient routing, which is CRITICAL for media- 
path relay, and the model proposed here would provide much better  
selection mechanisms for net-path efficient media relays.

But haven't we, for all practical purposes, developed a net-path  
optimized routing database that we bootstrapped into using a  
conventional DHT? Do we need to reinvent path-efficient routing for  
messaging, media relay, and every service? Would it have been more  
efficient just to start with a path-efficient DHT to start with? I  
don't know yet. I do know that thinking about application-aware  
routing at Internet scales is giving me a severe head pain, and  
historically, the complexity of this is why we have the "thin- 
waisted" routing model of the Internet. I just wished it worked in  
the real world of NATs and firewalls and other annoying stuff.

--
Dean

_______________________________________________
P2PSIP mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/p2psip

---

From: "Henry Sinnreich" <[email-masked]>
Date: Thu, 22 Nov 2007 06:48:46 -0800

These are excellent thoughts and require IMHO not to be solved in the
SIP space alone, but in the broader context of p2p. 

Thanks Dean for stimulating some home work!
It includes some research on what the p2p industry (who else is
generating all this R&D and Internet traffic?) has done here already.
Maybe P2PSIP can reuse some of this work.

Henry

-----Original Message-----
From: Dean Willis [mailto:[email-masked]] 
Sent: Wednesday, November 21, 2007 4:03 PM
To: P2PSIP Mailing List
Subject: [P2PSIP] More thoughts on clients, peers, and services,and
service routing

--
Dean

---

From: Cullen Jennings <[email-masked]>
Date: Fri, 23 Nov 2007 11:08:50 -0800

Dean, I have read this 3 times now and I can't figure it out in the  
slightest.  Can you relate this is a concrete way to what would need  
to be changed on any of the draft proposed solutions. That might help  
me understand. I'm also very confused if "finding" has to do with  
peers doing storage or with peers doing routing or something else all  
together.

Thanks, Cullen <with my individual hat on>

On Nov 21, 2007, at 2:03 PM, Dean Willis wrote:

>
> In the voluminous discussion of the last 36 hours, I think I'm  
> seeing an alternative emerge that I will try and restate.
>
> One way to divide the problem space is to differentiate the tasks  
> of "finding", "routing", and "everything else".
>
> Several people have proposed that peers exclusively provide  
> "finding and routing" services. Clients use the "finding and  
> routing" services of peers. Both clients and peers can also offer  
> other services, such as STUN relay (although some might say that  
> peers offering other services are acting as clients when they do  
> so).  I think this model works fairly well, and it continues in the  
> principle that peers are a superset of clients -- that is, that  
> clients and peers are pretty much similar, but peers do a few  
> things that clients can't. For each service that a client or peer  
> provides, that node would "put" a service entry in to the database,  
> and these services are completely distinct from the nodes role as  
> peer or client
>
>
> record" or "Please fetch this resource record", but not "Please  
> send this message to [email-masked]".
>
> route to "[email-masked]", where that route might include not  
> only Alice's "contact", but also hops for nodes that have agreed to  
> serve as relays for sending messages to Alice. This is somewhat  
> analogous to the "path" and "service route" terminology in SIP. We  
> can think of this as a "put" operation against the distributed  
> database.
>
> To call Alice, Bob would then simply do a "get" operation,  
> requesting a route to "[email-masked]". He would then use the  
> result as a SIP route vector to send an INVITE request to Alice.
>
> The harder parts: How would Alice discover an appropriate vector?  
> And how do we compensate for the fact the ideal route between Bob  
> and Alice might be different than the route between Charlie and Alice?
>
> those nodes have to list themselves. Each one might start by  
> finding a primal node (a "routing bootstrap", if you will) and  
> making ICE checks against that node. If they can reach it and it  
> can reach them, they consider themselves "tier-1" nodes, and "put"  
> resource records listing themselves as tier-1 nodes. If not, then  
> they query the database for tier-1 nodes, perform ICE checks  
> against them, and add resource records listing themselves as tier-2  
> nodes adjacent to the tier-1 nodes which which they have mutual  
> reachability. If they aren't adjacent to any tier-1 nodes, then  
> they repeat for tier-2, then tier-3, and so on. Of course, it would  
> be nice if the distributed database offered some technique for  
> automagically scoping the candidates, but it isn't required for the  
> algorithm to terminate. Optionally, routing nodes could do  
> persistent "outbound"-like bindings with some higher-tier node  
> selected as the most-adjacent node they can reach, thereby either  
> short-circuiting the search process or achieving connectivity  
> across NAT/FW boundaries that block reverse-path checks. One could  
> further short-circuit the process by using broadcast and multicast  
> to find neighbors that have already established their vectors, then  
> copying those vectors rather than finding new ones.
>
> offering the "routing" service, thereby obtaining a list of  
> candidate nodes. She might then do something like an ICE-like  
> evaluation to find one or more acceptable candidates, and would  
> select the lowest-tiered node she could reach. Of course it would  
> be nice if the distributed database could help narrow this search,  
> but it isn't absolutely required. Alice would continue working up  
> the tiers until reaching tier-1, then "put" a vector or into the  
> database, where that vector lists Alice's contact plus the URIs of  
> each routing node up to and including her tier-1 contact.
>
> Bob, when calling Alice, would "get: her vector, then run a  
> shortest-path calculation between his vector and her vector, then  
> use the result as a SIP route to reach Alice.
>
> messages are routed according to what is in effect a minimum  
> spanning tree calculation against the sip-routing topology of the  
> network.
>
> aggregation) approaches that would provide absolutely optimal  
> routes but have higher overheads. Think OSPF, but where  
> aggregations (OSPF areas) are defined dynamically vice ICE-like  
> adjacency checks.
>
> This is a little different from the current proposals, which seem  
> to require a customized DHT algorithm and and routes messages  
> across that DHT based on the dynamic topology of the DHT itself and  
> is likely to give a much less efficient a route. Of course, the  
> route discovery process (especially in the event of a topology  
> change) is much easier. On the other hand, the DHT topology tells  
> us little or nothing about net-path efficient routing, which is  
> CRITICAL for media-path relay, and the model proposed here would  
> provide much better selection mechanisms for net-path efficient  
> media relays.
>

---

From: Dean Willis <[email-masked]>
Date: Fri, 30 Nov 2007 15:22:48 -0600

On Nov 23, 2007, at 1:08 PM, Cullen Jennings wrote:
>> so).  I think this model works fairly well, and it continues in  
>> the principle that peers are a superset of clients -- that is,  
>> that clients and peers are pretty much similar, but peers do a few  
>> provides, that node would "put" a service entry in to the  
>> database, and these services are completely distinct from the  
>> nodes role as peer or client
>>
>>
>> Is this the only way to divide the problem? Maybe clients and  
>> peers are very different things, neither subsets nor supersets of  
>> each other.
>>
> slightest.  Can you relate this is a concrete way to what would  
> need to be changed on any of the draft proposed solutions. That  
> might help me understand. I'm also very confused if "finding" has  
> to do with peers doing storage or with peers doing routing or  
> something else all together.

"Finding" is the old "SIP location service problem" -- given a SIP  
URI (or perhaps a resource identifier), how do we know where to send  
SIP requests to in order to establish a multimedia session? Clearly  
"clients" ask some other nodes ("peers"?) for this information.

"Routing" is the old SIP "proxy" function -- it happens when nodes  
accept requests that are not targeted to themselves, and pass them  
along to other nodes that may either be the target or closer to the  
target.

Some models of P2PSIP distinguish the two functions, others conflate  
them, and others provide only one function.

For example, assume we have a model where a client (alice) wishes to  
send a message to Bob (sip:[email-masked]). So Alice asks (a "get"  
operation) a peer "Please give me the node ID at which I can reach  
sip:[email-masked]" (or perhaps she first hashes said string into a  
resource ID). The peer tells her "sip:[email-masked] can be reached  
at node 0xA14578AB18EDF5". So then Alice asks the peer for routing,  
saying "Send this message (or connect me) to node 0xA14578AB18EDF5".  
In this model, we have both "finding" and "routing", and they are  
discrete operations (note that "routing" may mean passing discrete  
messages, or it might establish a tunnel between the nodes -- that's  
another issue).

Another model (as proposed by Henry), Alice would simply get "the  
Contact: for sip@[email-masked]" and would receive  
"sip:[email-masked]". Alice would then connect using SIP to  
128.194.18.1 and send an INVITE request. Here we have "finding", but  
no "routing" being provided by the P2P layer.

In yet another model, Alice would start by saying "Send this message  
to sip:[email-masked]". The peer would then (possibly after  
resolving the target it to a node ID, or perhaps just by following   
next-hop pointer) forward the request on. This model conflates  
"finding" and "routing" -- that is, there is no "get", only "send".

The important distinction here is that there is some service or set  
of services (such as "finding" and/or "routing")  being provided by  
the peers that are not being provided by the clients, and that there  
is some functionality other than that provided by SIP happening  
between the clients and the peers. For example, a SIP client  
certainly wouldn't know how to hash a resource name like  
"sip:[email-masked]" into a resource ID. A P2PSIP client might or  
might not know how to do this, depending on the exact model.

We seem to be converging on a model where the overlay itself offers  
both finding and routing, with both occurring along the connectivity  
graph of a DHT. I'm suggesting that this may not be the only viable  
model, and that we might get different results if we used the DHT  
only for the "finding" operations, and use some other mechanism (as  
yet undefined) for the "routing" operations. In fact, it might be  
possible to have "routing" as a service that is completely apart from  
the DHT, perhaps by clients, or perhaps by nodes that aren't even  
aware of the DHT. One might "find" a nearby routing node, then use  
some other mechanism to send the SIP request through that routing  
node (and perhaps other routing nodes) to the target.

Here's an example. Alice still wants to call Bob.

Alice does a "get" on sip:[email-masked], and receives a route- 
vector like "<sip:proxy01.example.org>, <sip:192.168,34,2>,  
<sip:[email-masked]">. Alice then sends an INVITE using this route- 
vector as a preloaded Route: header field.

In this example, all the message-passing work is done at the SIP  
level. What the P2P overlay did was 1) establish a reachability graph  
between the proxies participating in the overlay, and 2) calculate an  
efficient path through that reachability graph to the target.

Does that help explain my pondering?

This leads me to also wonder about what may be another functional  
split: "routing" as we have used it above conflates both the  
determination of a path and the forwarding of a message. It doesn't  
have to, as my last example shows. The mechanism used to find the  
path between two nodes does not necessarily transfer a message  
between those two nodes.

--
Dean

---

From: "Henry Sinnreich" <[email-masked]>
Date: Fri, 30 Nov 2007 14:16:35 -0800

>"finding", "routing", and "everything else"

Dean and Cullen make excellent points, though what do we put "Under
everything else"?

There are also all kind of system design items, such as in Bamboo that
must be accomplished in the real world:

Modules
* Router: routing-table, leaf-set, cache. Iterative + recursive, 
* Messages: join-request/response, leaf-set-changed,
routing-table-request, ping-request, neighbor-announce, ...
* DHT: put, get, remove. Fairness for disk quota
* Gateway: for clients to use the service
* Data manager: replication of stored data on leaf set
* DB: high-performance, embedded database library from Berkeley
* Network: congestion controlled UDP
* Async event architecture
* ReDiR: client side library for the service interface

Soft-state: Failures and smart timeouts for neighbor recovery

Proximity neighbor selection for various metrics:
* Latency
* Routing hops
* Bandwidth
...etc., ...

I have borrowed these items from a paper by Kundan Singh.

Henry

-----Original Message-----
From: Dean Willis [mailto:[email-masked]] 
Sent: Friday, November 30, 2007 3:23 PM
To: Cullen Jennings
Cc: P2PSIP Mailing List
Subject: Re: [P2PSIP] More thoughts on clients, peers, and services,and
service routing

--
Dean

---

From: Paul Kyzivat <[email-masked]>
Date: Fri, 30 Nov 2007 18:00:40 -0500

Dean,

Very interesting stuff you wrote below.

A related question:

in a regular sip network, UAs often "hide behind" a proxy - the proxy 
acts as a screening device. It also acts as a policy agent for selecting 
which of possibly several UAs for the AOR gets a call. (It may also do 
callerprefs but typically callee policy takes precedence.)

Is any of this behavior in scope for P2PSIP? Is it part of the finding 
function, the routing function, or some new function?

	Thanks,
	Paul

Dean Willis wrote:
> "Finding" is the old "SIP location service problem" -- given a SIP URI 
> (or perhaps a resource identifier), how do we know where to send SIP 
> requests to in order to establish a multimedia session? Clearly 
> accept requests that are not targeted to themselves, and pass them along 
> to other nodes that may either be the target or closer to the target.
> 
> resource ID). The peer tells her "sip:[email-masked] can be reached at 
> node 0xA14578AB18EDF5". So then Alice asks the peer for routing, saying 
> "Send this message (or connect me) to node 0xA14578AB18EDF5". In this 
> model, we have both "finding" and "routing", and they are discrete 
> operations (note that "routing" may mean passing discrete messages, or 
> it might establish a tunnel between the nodes -- that's another issue).
> 
> 128.194.18.1 and send an INVITE request. Here we have "finding", but no 
> "routing" being provided by the P2P layer.
> 
> In yet another model, Alice would start by saying "Send this message to 
> sip:[email-masked]". The peer would then (possibly after resolving the 
> target it to a node ID, or perhaps just by following  next-hop pointer) 
> forward the request on. This model conflates "finding" and "routing" -- 
> that is, there is no "get", only "send".
> 
> The important distinction here is that there is some service or set of 
> services (such as "finding" and/or "routing")  being provided by the 
> peers that are not being provided by the clients, and that there is some 
> functionality other than that provided by SIP happening between the 
> clients and the peers. For example, a SIP client certainly wouldn't know 
> how to hash a resource name like "sip:[email-masked]" into a resource 
> ID. A P2PSIP client might or might not know how to do this, depending on 
> the exact model.
> 
> We seem to be converging on a model where the overlay itself offers both 
> finding and routing, with both occurring along the connectivity graph of 
> a DHT. I'm suggesting that this may not be the only viable model, and 
> that we might get different results if we used the DHT only for the 
> "finding" operations, and use some other mechanism (as yet undefined) 
> for the "routing" operations. In fact, it might be possible to have 
> "routing" as a service that is completely apart from the DHT, perhaps by 
> clients, or perhaps by nodes that aren't even aware of the DHT. One 
> might "find" a nearby routing node, then use some other mechanism to 
> send the SIP request through that routing node (and perhaps other 
> routing nodes) to the target.
> 
> Alice does a "get" on sip:[email-masked], and receives a route-vector 
> like "<sip:proxy01.example.org>, <sip:192.168,34,2>, 
> <sip:[email-masked]">. Alice then sends an INVITE using this 
> route-vector as a preloaded Route: header field.
> 
> In this example, all the message-passing work is done at the SIP level. 
> What the P2P overlay did was 1) establish a reachability graph between 
> the proxies participating in the overlay, and 2) calculate an efficient 
> path through that reachability graph to the target.
> 
> This leads me to also wonder about what may be another functional split: 
> "routing" as we have used it above conflates both the determination of a 
> path and the forwarding of a message. It doesn't have to, as my last 
> example shows. The mechanism used to find the path between two nodes 
> does not necessarily transfer a message between those two nodes.
> 
> -- 
> Dean
> 
>

---

From: Dean Willis <[email-masked]>
Date: Fri, 30 Nov 2007 20:27:16 -0600

> Very interesting stuff you wrote below.

Thanks. I think "interesting" is a good adjective. Far more polite  
than "deranged", which probably came to mind for at least a few readers.

>
> A related question:
>
> in a regular sip network, UAs often "hide behind" a proxy - the  
> proxy acts as a screening device. It also acts as a policy agent  
> for selecting which of possibly several UAs for the AOR gets a  
> call. (It may also do callerprefs but typically callee policy takes  
> precedence.)
>
> Is any of this behavior in scope for P2PSIP? Is it part of the  
> finding function, the routing function, or some new function?
>

I've been pondering that question for some time.

Either we lose much of the functionality built into SIP proxies  
(which includes what you list above along with, to my mind, the far  
more important function of hiding the UA's IP address unless proxy  
policy lets the request through), or we have to find a new way to  
provide those functions.

I think this could take two forms, one novel, one conventional.

In the conventional approach, the "peer" that would be found using a  
"get" on a AOR resource is a SIP proxy, and once it gets a SIP  
request, it applies the usual policy decisions before passing the  
request on to the end UA. This "passing on" could be done using  
conventional SIP, or it could be done using the overlay. What makes  
it work is the same sort of indirection that maps AOR to Contact to  
User. We'd just introduce an intermediary resource ID. In effect,  
Alice might insert her two phones "[email-masked]" and  
"[email-masked]" into the overlay, and her proxy peer might  
insert "[email-masked]" and be configured with a policy table that  
applies "contact routing" towards the phones. We can even think of  
using a SIP REGISTER request, routed over the overlay, to inform the  
proxy peer about the downstream bindings. Perhaps there is even a way  
to apply CPL in this sort of model.

A more novel approach would be to put the traditional "proxy policy"  
functions into the overlay.  One approach would be to have a "policy  
language", and for each AOR, put a policy resource into the overlay.  
Before sending a message, a peer would first do a "get" on the policy  
resource, then interpret the policy resource before dispatching the  
request. For example, the policy resource for "[email-masked]"  
might indicate that she's busy next week and all calls should be  
retargeted to "[email-masked]". Alice's various devices  
(assuming she has more than one) might achieve the effect of SIP  
contact-registration by amending Alice's policy resource to add  
themselves to the policy.

I think the current models rather naively assume "one AOR, one  
device" and that any policy enforcement can be done in the  
terminating device. There's probably an underlying assumption that  
any more complex policy gets handled by something analogous to a  
B2BUA, but I don't think it really has to work that way. Indeed, I  
expect to see all sorts of policy-driven indirection models working  
their way into the overlay once we get the basic functions sorted  
out. But that does raise the question of the system being more  
effective if we  build these functions in up front.

Here's a nifty use case: Let's say Alice only wants Bob and Charlie  
to be able to deduce her location from the overlay. The resource  
"[email-masked]" might, instead of returning a Contact, instead  
return only a policy object. That policy object might contain  
sections encrypted with Bob and Charlie's public keys. Each section,  
when decrypted, would provide a retargeting to an anonymous resource  
ID that Alice minted for temporary use. Bob "calls" alice, "getting"  
the resource record "[email-masked]", finds it to be a policy  
object that has a section keyed for him, decrypts it, finds that it  
contains instructions to retarget to another resource, does a  
"connect" on that resource, and is connected to Alice's phone.

These are the kinds of things that can happen when we start thinking  
of the overlay as a distributed database, not just as a distributed  
proxy-registrar.

--
Dean