Subject: RE: [arch-d] On scaling of flat identifier spaces (was Re:On identifiers: what is virtual and what is global)

From: <[email-masked]>
Date: Tue, 28 Nov 2006 13:10:21 -0000

-----Original Message-----
From: Pekka Nikander [mailto:[email-masked]] 
Sent: 28 November 2006 11:28
To: Brian E Carpenter
Cc: [email-masked]
Subject: Re: [arch-d] On scaling of flat identifier spaces (was Re:On identifiers: what is virtual and what is global)

>> Hence, my tentative conclusions are that for a very large flat name  
>> space, you need
>> - enough of bits in the identifier, in order to make the probability  
>> of random collisions considerably smaller than the probability of  
>> double-assignment due to human errors.
>
> Surely the risk you need to evaluate is the probability of double 
> assignment due to random loss of messages in a distributed assignment 
> system?

Thanks, I missed that!  Fool me still thinking that the system would be reliable...

>> So, what I am missing?  Why do identifier systems necessarily need to  
>> be structured?
>
> That depends whether "look-up times in the order of 1-2 seconds"
> are considered sufficient. If, for example, that is 6 orders of 
> magnitude too long, you'd have a problem.

Yes.  :-)

Flat identifier spaces do not seem to be very suitable for large- 
scale routing.  IIRC, the ROFL paper had some numbers.  Checking...   
Yes, from "Summary of results": "host can join across all providers and peers ... with ∼445 control messages.  An average [routing] stretch of 2.5. .... [Possible to] reduce [host] join overhead to ∼100 messages, but requires 74 Mbits of bloom filter state per AS."

 From that, the stretch of 2.5 seems pretty bad.  I don't have any numbers for the stretch in the current system, though.  (stretch = the ratio between the traversed path and the shortest path.)

[alb] From what I read, stretch  is pretty bad today then
[alb] www.eecs.umich.edu/~zmao/eecs589/notes/lec5_6.pdf
[alb] http://citeseer.ist.psu.edu/cache/papers/cs/18034/http:zSzzSzwww.isi.eduzSz~hongsudazSzpublicationzSzinfo2001.pdf/tangmunarunkit01impact.pdf

[alb] Also, I would suspect that change management rather than absolute size would be the issue with a flat system

[alb] I am rather of the feeling that a one off look-up time (say resolving a flat name to a locator) might be possible, but [alb] you might want to stick with structure in the locator for routing purposes

[alb] Louise

--Pekka Nikander

_______________________________________________
Architecture-discuss mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/architecture-discuss
_______________________________________________
Architecture-discuss mailing list
[email-masked]
https://www1.ietf.org/mailman/listinfo/architecture-discuss