Hi Bruce,
On Dec 23, 2007 4:33 AM, Gonzalo Camarillo
<[EMAIL PROTECTED]> wrote:
Regarding your question about Sections 3.2 and 3.3 when RELOAD is
the peer protocol and HIP BONE is used for connection management,
the idea is to use HIP, instead of RELOAD, to perform connection
management. All the other functions RELOAD typically performs are
still performed by RELOAD.
RELOAD defines the CONNECT primitive and the TUNNEL primitive. If
HIP is being used, you would use the CONNECT primitive of HIP
(i.e., an I1 packet) *instead* of the CONNECT primitive of RELOAD.
The same way, you would use the TUNNEL primitive of HIP (i.e., a
HIP message) *instead* of the TUNNEL primitive of RELOAD.
On 9 Jan 2008, at 00:16, Bruce Lowekamp wrote:
This is where I still get confused, and I think this is a pretty
big architectural issue. The combination of 3.2, 3.3, and 6 still
leave some questions in my mind as to exactly what is being
proposed, so let me try to form up an example for discussion purposes.
Briefly, what I had in mind when writing the HIP BONE draft was your
"HIP routing table" approach below. While I agree with you that at
the architectural level the question is relatively big, I think that
when you go to the implementation level the actual difference between
the "HIP routing table" and "HIP link layer" approaches will be quite
small. The key issue here is whether it is possible to divide the
work between a "routing table" and a "forwarding table". I don't
know the proposed peer protocols well enough to be able to answer
that question. If it indeed is possible to make such a division,
then I think the difference between "HIP routing table" and "HIP link
layer" almost disappears. Otherwise the situation gets hairier, as
you apparently suggest below.
But let's have a look at your example:
Suppose I have an overlay with the following connections between
peers (labeled with their peerid):
1 ------ 5 ------ 10
So 1 has 5 in its routing table (and thus a direct connection) but
not 10. 5 has direct connections to 1 and 10. I'm assuming
recursive routing and am not being precise with a DHT algorithm for
the purposes of this example.
10 is responsible for a resource, 9, that 1 wants to query for. In
a non-HIP DHT implementation, 1 sends a query "to" 9. It looks up
for the closest match in its routing table and discovers it is 5,
then it sends the message to 5. 5 performs a similar lookup and
discovers that its closest match is 10, so it forwards the query to
10.
Going with the HIP-BONE, approach, as I understand the "HIP is IP
and the peer protocol is OSPF" idea, I see two approaches that
would meet that requirement:
- the peer protocol loads enough information into the HIP layer
that the HIP layer on peer 1 knows that the next hop for a message
bound for "9" is 5. I will refer to this as the hip routing table
approach.
In this approach I would call the "information loaded into the HIP
layer" as the forwarding table.
- the peer protocol sets the next-hop for the query to "5" based on
its own routing table, and lets the HIP layer forward it. I will
refer to this as the hip link layer approach.
The only difference that I can see between the previous one and this
one is that here there are no explicit routing table. Hence, instead
of doing the typical thing routers do, i.e., to compute a forwarding
table from the routing table as a "batch job" the forwarding decision
is performed "lazily" on demand.
The hip routing table approach looks great from a layering
perspective, but implementation looks to be very hard.
Why? Do you allude that the various overlay routing protocols are
sufficiently different from the IP routing protocols so that one
cannot compute a forwarding table? Or is there some other
implementation problem that you are thinking about?
Since there are multiple DHT (and unstructured overlay) algorithms
with different routing rules, there would have to be a pluggable
routing algorithm loaded into the HIP layer by the DHT algorithm or
there needs to be
an upcall from the HIP layer into the peer protocol layer to query
for the next-hop for messages.
So, you do seem to be saying that it is impossible to process the DHT-
layer routing information into a consistent forwarding table format
that can be used by a single look-up algorithm. Now, I have to
confess that I don't understand this argument at all. Given that for
each packet the forwarding decision has to eventually be made, the
time complexity of computing a forwarding decision must be manageable
(sub-linear w.r.t the number of nodes in the overlay). Hence, are
you saying that there is no reasonable representation of the
forwarding table, i.e., that the space complexity will be
overwhelming? But then I don't understand either, as my
understanding is that with e.g. Bloom filters you can represent an
random collection of sets with in a relatively small space. [In the
case of Bloom filters we of course have the question of false
positives, but I cannot see a big problem if some packets get briefly
duplicated on the overlay. Intuitively, That doesn't seem to add
much to the already pretty high inefficiency of the overlay.]
In the hip link layer approach, the peer protocol layer knows that
the current set of next-hop candidates are, and it runs the DHT
routing algorithm in the conventional sense, telling the HIP layer
what the next hop for a message is. This seems like a much simpler
approach to implement, but limits the usefulness of HIP.
I agree with you that this would limit the usefulness of HIP.
However, if there is a forwarding table, then the practical level
difference between the "HIP routing table" and "HIP link layer" boils
down to on which layer you store the forwarding table.
So the first question is whether HIP-BONE is intended to specify
one of these approaches, and if so, which one? I believe it's the
hip routing table approach.
Well, at the time of writing I couldn't see such a difference.
Hence, perhaps the "right" answer to this question is "neither".
Instead, while HIP BONE in its current form doesn't specify either of
the approaches, it alludes towards a "third" approach, i.e., towards
separating the routing and forwarding tables, which makes the
implementation-level difference very small. Hence, from that point
of view, HIP BONE would allow either architectural choice.
Next, let's take the case of 3.3, "lightweight message exchange."
As I understand 3.3, it should work fine in the hip routing table
approach for both application and peer protocol message exchanges.
In the hip link layer approach, peer protocol messages can be
delivered this way, but application messages cannot (they would
require a direct connection).
I don't quite understand what you are saying. Would you please clarify?
Next, how about CONNECT messages. Suppose that now peer 1 wants to
establish a direct connection to peer 10 for some reason. Your
email indicates that there will be no CONNECT messages as in
RELOAD, but instead there will only be I1 etc messages. Let's just
assume that the peer protocol has some way of indicating that it
wants to be able to send messages directly to another peer rather
than over the overlay.
I'm following so far.
So in the hip routing table approach, the I1 etc messages are
routed via 5 using HIP to 10 and eventually a new direct connection
is established.
Well, depending on many factors, it may be only a subset of the HIP
base exchange messages that would be routed over the overlay (through
node 5); some of them (like perhaps R2) could perhaps be sent
directly, at least in some cases. So, there is some flexibility
here, but at least I don't quite understand the situation in cases
where both 1 and 10 are behind NATs.
In the hip link layer approach, the peer protocol would have to
insert the I1 into a peer message and forward
it itself. That would work, but it's a bit cumbersome.
Again, I don't understand. Why would the peer protocol need to
insert I1 into a peer message?
What continues to confuse me, and what I think is the hardest
architectural question here, is how the issue I mentioned above:
"there would have to be a pluggable routing algorithm loaded into
the HIP layer by the DHT algorithm or there needs to be an upcall
from the HIP layer into the peer protocol layer to query for the
next-hopfor messages" is solved.
As I indicated above, my idea was to separate the routing table and
forwarding table. Right now I cannot see why it would not work, but
maybe I'm just ignorant about the various overlay routing protocols.
<snipping the rest>
--Pekka Nikander
_______________________________________________
P2PSIP mailing list
[email protected]
https://www1.ietf.org/mailman/listinfo/p2psip
