Subject: Re: [P2PSIP] reload-04 routing

From: jiangxingfeng 36340 <[email-masked]>
Date: Fri, 20 Jun 2008 14:33:23 +0800

> > As for partition, what I see the peer could do after he knows that is to
> > restart a join-like operation. The direct response and relay peer work in
> > the partition situation in the same way as in other situations. Am I missing
> > something?
> 
> You're right in that they work just as well as they do any other
> time---when they work they work fine, but if they don't work (due to NAT
> filtering, etc), you still need the fallback to symmetric routing.

It seems that symmetric routing could work in all cases. In chord algorithm, if the number of the nodes in the system above 1000, the possible largest hops for a request would be larger than 10 hops. IMO, symmetric routing will have lower success rate as the number of hops increases, although I have no real data to support my concern. On the other hand, the data to be looked up is distributed around the overlay, so the number of hops will h
ave an appropriate even distribution within (0, log(N)]. Are you sure symmetric routing could work well if the request need traverse long hops? Are you sure the end-2-end retransmission mechanism could make the transaction successful in the end? 

> 
> > What I suggest is to integrate symmetric routing mode, direct response,
> > relay peer into an integral routing mechanism and could work more efficient
> > than using a single  candidate mechanism.
> 
> The decision the WG will have to make is whether the complexity of
> additional routing mechanisms is worth the increased performance
> (removing a few hops on the return path). 

The benefit to me from direct response and relay peer alternatives is not only removing a few hops. The more important one is to improve the success rate of the transaction if the request need to be traversed with large hops. 

> We tried to apply Occam's
> Razor rather aggressively in evaluating features, and adding additional
> complexity to the protocol for these features seemed a bit questionable,
> at least for right now.

I don't see other alternatives introduce too much complexity. The simplest way to integrate the three routing mechanisms is: the original peer carries the relay peer and local interface address information in the request and sends the request; the intermediate peers record the via-list. When the destination receives the request, it could compute how many hops the request traversed. If the number of hops is large, it not only returns the res
ponse by using the symmetric routing, but also sends the response by using the direct response or relay peer respectively. 

> 
> Now if you work in a world where NATs and firewalls don't exist, the
> world would be different, of course.

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

---

From: Bruce Lowekamp <[email-masked]>
Date: Fri, 20 Jun 2008 12:11:07 -0400

> ave an appropriate even distribution within (0, log(N)]. Are you sure symmetric routing could work well if the request need traverse long hops? Are you sure the end-2-end retransmission mechanism c…

The question comes down to whether the return path is likely to fail 
over the interval of the response latency.

But before you answer that question, you have to consider whether the 
outbound path is likely to work.  That depends on the churn rate of the 
overlay and the refresh/keepalive rate used by the peers.  Regardless of 
the answer to those questions, the response latency of the return path 
is going to be lower than the keepalive rate*.  Therefore the outbound 
path is more likely to fail than the return path.

 From my survey of the literature, nearly all sources suggest that if 
the churn rate is sufficiently high that the outbound query is likely to 
be lost, the best solution is to fall back to iterative routing so that 
the querying peer can ensure that at least some progress is made in 
resolving the query.

So my answer to your question is that if the combination of churn rate, 
path length, and path latency is high enough that symmetric routing is 
likely to fail, you would already be having problems with recursive 
forwarding of requests regardless of the return method being used.

*I've seen some work on using incredibly fast keepalive timers to try to 
improve overlay stability.  I'm not convinced that the benefits of 
building an overlay with unstable peers is worth the benefit.  I would 
much rather use an overlay algorithm that is more careful in selecting 
which nodes can serve as peers.

> ponse by using the symmetric routing, but also sends the response by using the direct response or relay peer respectively. 

I'm not suggesting that this is monumentally complex (actually, I think 
locating a relay peer is very complex and needs a standalone draft). 
Merely that I think the WG needs to look at what the requirements for 
the protocol are and where it is worth adding additional 
complexity/message size.  This particular issue imposes some additional 
message size and some additional processing on the part of the 
responder, but it is merely one of quite a few such issues.

Bruce

---

From: Cullen Jennings <[email-masked]>
Date: Mon, 23 Jun 2008 14:05:39 -0700

My initial thoughts are pretty similar to Bruce's but more  
importantly, I think routing is one of the things we need to hash out  
as a WG and figure out what is best. I'm imagining a WG meeting where  
we had a few people talk about the various possibilities, the pros and  
cons of them, then made a sound engineering choice. I really look  
forward to meetings like that - designing the RELOAD as an individual  
draft is like working in a vacuum, which is fine other than you blood  
boils and your head explodes.

One general strategy the authors have been taking is keep the base  
protocol having the simplest of possible solutions but make sure that  
one could allow extensions that allow better performance.  The type of  
suggestion you are talking about here of forking responses so they are  
sent back on both a symmetric and direct path seems like something  
that could be added as extension. There be a lot of things to consider  
such as how much it improved the situation, congestion control, and  
the security issues around it contributing to DOS attacks - typically  
it is nice to design things to they don't have message amplification  
but perhaps there would be some way to mitigate that in the scheme you  
proposed.

Cullen <with my individual contributor hat on>

On Jun 20, 2008, at 9:11 AM, Bruce Lowekamp wrote:

>> It seems that symmetric routing could work in all cases. In chord  
>> algorithm, if the number of the nodes in the system above 1000, the  
>> possible largest hops for a request would be larger than 10 hops.  
>> IMO, symmetric routing will have lower success rate as the number  
>> of hops increases, although I have no real data to support my  
>> concern. On the other hand, the data to be looked up is distributed  
>> around the overlay, so the number of hops will h
>> ave an appropriate even distribution within (0, log(N)]. Are you  
>> sure symmetric routing could work well if the request need traverse  
>> long hops? Are you sure the end-2-end retransmission mechanism  
>> could make the transaction successful in the end?
>
> But before you answer that question, you have to consider whether  
> the outbound path is likely to work.  That depends on the churn rate  
> of the overlay and the refresh/keepalive rate used by the peers.   
> Regardless of the answer to those questions, the response latency of  
> the return path is going to be lower than the keepalive rate*.   
> Therefore the outbound path is more likely to fail than the return  
> path.
>
> the churn rate is sufficiently high that the outbound query is  
> likely to be lost, the best solution is to fall back to iterative  
> routing so that the querying peer can ensure that at least some  
> progress is made in resolving the query.
>
> So my answer to your question is that if the combination of churn  
> rate, path length, and path latency is high enough that symmetric  
> routing is likely to fail, you would already be having problems with  
> recursive forwarding of requests regardless of the return method  
> being used.
>
>
> *I've seen some work on using incredibly fast keepalive timers to  
> try to improve overlay stability.  I'm not convinced that the  
> benefits of building an overlay with unstable peers is worth the  
> benefit.  I would much rather use an overlay algorithm that is more  
> careful in selecting which nodes can serve as peers.
>
>> The benefit to me from direct response and relay peer alternatives  
>> is not only removing a few hops. The more important one is to  
>> improve the success rate of the transaction if the request need to  
>> be traversed with large hops.
>> I don't see other alternatives introduce too much complexity. The  
>> simplest way to integrate the three routing mechanisms is: the  
>> original peer carries the relay peer and local interface address  
>> information in the request and sends the request; the intermediate  
>> peers record the via-list. When the destination receives the  
>> request, it could compute how many hops the request traversed. If  
>> the number of hops is large, it not only returns the res
>> ponse by using the symmetric routing, but also sends the response  
>> by using the direct response or relay peer respectively.
>
> I'm not suggesting that this is monumentally complex (actually, I  
> think locating a relay peer is very complex and needs a standalone  
> draft). Merely that I think the WG needs to look at what the  
> requirements for the protocol are and where it is worth adding  
> additional complexity/message size.  This particular issue imposes  
> some additional message size and some additional processing on the  
> part of the responder, but it is merely one of quite a few such  
> issues.
>
> Bruce
>
>
>

---

From: jiangxingfeng 36340 <[email-masked]>
Date: Tue, 24 Jun 2008 09:20:24 +0800

Hi, Bruce:
sorry for late response. please see inline. 

Regards
JiangXingFeng

> > It seems that symmetric routing could work in all cases. In 
> chord algorithm, if the number of the nodes in the system above 
> 1000, the possible largest hops for a request would be larger than 
> 10 hops. IMO, symmetric routing will have lower success rate as 
> the number of hops increases, although I have no real data to 
> support my concern. On the other hand, the data to be looked up is 
> distributed around the overlay, so the number of hops will h
> sure symmetric routing could work well if the request need 
> traverse long hops? Are you sure the end-2-end retransmission 
> mechanism could make the transaction successful in the end? 
> > 
> 

Not only depends on the interval of the response latency, but also depends on the number of the immediate peers in the path. Peers have their respective uptime. 

> the 

>From this prospective, I think you are right. But in such a P2P algorithm as pastry, two or more candiate neighbor could be chosen for each entry, so that the sucess rate will be improved greatly, I think. In case of the failure of the request sent to a peer, the peer forwarding the request could try to use another candidate peer. 
> 
> likely to 

Itrative routing, as discussed in RELOAD-4, has trouble in using in the presence of NAT. 

> rate, 
> try to 

I have the same opinion as yours. But it seems it is not easy to select more powerful, more stable peer among all nodes.  

> 
> >>> What I suggest is to integrate symmetric routing mode, direct 
> response,>>> relay peer into an integral routing mechanism and 
> could work more efficient
> > The benefit to me from direct response and relay peer 
> alternatives is not only removing a few hops. The more important 
> one is to improve the success rate of the transaction if the 
> request need to be traversed with large hops. 
> > 
> >> Razor rather aggressively in evaluating features, and adding 
> additional>> complexity to the protocol for these features seemed 
> a bit questionable,
> >> at least for right now.
> > 
> > I don't see other alternatives introduce too much complexity. 
> The simplest way to integrate the three routing mechanisms is: the 
> > ponse by using the symmetric routing, but also sends the 
> response by using the direct response or relay peer respectively. 
> >
> 
> think 

The relay peer could be considered as a service, and later a peer could use the general service discovery mechanism to search one. 

> responder, but it is merely one of quite a few such issues.

I think our discussion is based mostly on our perception, not based on real data and real network enviroment. I have done a few work on compare different routing mode, but due to some reasons, the work was stopped right now. I try to resume the work ASAP. Do you have some experimental data to prove that symmetric routing could handle all cases? I am not holding my idea. What I want to see is the resulting peer protocol could be general enou
gh to be deployed in as many situations as possible. 

I admit there must be problems with direct response and relay peer. But I think it could be solved if the community and experiment think it is worth doing the work.

---

From: jiangxingfeng 36340 <[email-masked]>
Date: Tue, 24 Jun 2008 09:26:37 +0800

> boils and your head explodes.

right. I also hope the WG put more attention on this topic. I don't like the reason that the symmetric routing node is chosen is the symmetric has advantages over other routing modes in some aspects, not it handles all cases. We should put the routing as a open issue and leave the room for accepting other ideas. 

> but perhaps there would be some way to mitigate that in the scheme 

Yes, you are right. we could continue the issue. 

Regards!

JiangXingFeng
> >>>> As for partition, what I see the peer could do after he knows 
> 
> >>>> that is to
> >>>> restart a join-like operation. The direct response and relay 
> peer  
> >>>> work in
> >>>> the partition situation in the same way as in other 
> situations.  
> >>>> Am I missing
> >>>> something?
> >>> time---when they work they work fine, but if they don't work 
> (due  
> >>> to NAT
> chord  
> traverse  
> >>>> response,
> >>>> relay peer into an integral routing mechanism and could work 
> more  
> >>>> efficient
> alternatives  
> >>> additional
> The  
> response