BIND - sorting of reverse domain.

[Mark_Andrews at isc.org]

> 
> On 4 Jul 2002 Mark_Andrews at isc.org wrote:
> >> On 3 Jul 2002, Kevin Darcy wrote:
> >> >"D. Stussy" wrote:
> >> >> Older versions of BIND did not.  However, BIND-9 does - but someone els
> e
> >> >> indicated that this is a side effect of its memory image of the data an
> d n
> >> ot
> >> >> intentionally done.  If truly not intentional, that could moot my quest
> ion
> >> .
> >> >>
> >> >> I do note that someone also indicated that BIND arranges the data in
> >> >> alphabetical/machine order so as to abort early with an NXDOMAIN error 
> if
> >> it
> >> >> passes the point where the target query name would be.  Such a search i
> s
> >> >> potentially an O(n/2) on the average - while a balanced binary tree sea
> rch
> >>  would
> >> >> be O(log2(n)) (and the worst case unbalanced tree - O(n/2)).  Except fo
> r n
> >> =1 or
> >> >> n=2, log2(n) < (n/2) for postive integers, so why choose a non-optimal 
> sea
> >> rch?
> >> >> [This goes beyond my original question/comment, so responses aren't nec
> ess
> >> ary.]
> >> >
> >> >BIND stores zone data in memory in a hashed structure which has little or
>  no
> >>  relationship to the format in which it writes out
> >> >zonefiles.
> >>
> >> If true, then it must actively sort the zone file in order for it to be wr
> itt
> >> en
> >> out in alphabetical order (which is occuring with this version).  It is
> >> obviously bothering to take the time to do this, so while we're at it, why
>  no
> >> t
> >> write out the reverse domain files in numerical order where possible?  [We
> 're
> >> back to my original question!]
> >>
> >	BIND 8 uses a hash.
> 
> Nor did it have this behavior.
> 
> >	BIND 9 sorts in DNSSEC order because it *needs* the zone to be
> >	sorted this way to able to find the correct NXT record to be
> >	returned with a NXDOMAIN response.
> 
> Perhaps in the current implementation, but such need not be the case.  I have
> already indicated why this is inefficient.

	Did you really think the zone was stored as single array?

	You get told why the order is as it is, yet you still persist
	in saying that it is deliberately sorted on output.  It is not.
	You are looking at simple tree traversal.  This is true for both
	BIND 8 and BIND 9.  BIND 8 is a tree of hashes.

> >	Both BIND 8 and BIND 9 dump zones in internal order though they
> >	do put the SOA and NS RRsets for the zone first.
> 
> Placing the SOA record first is obvious.  As compared to the other entries
> within the domain, it effectively has a <null> name because all the other
> entries have at least one more name element.

	Actually putting the SOA first is NOT obvious as it doesn't
	sort first when sorting a zone in DNSSEC order.  The A
	records come first (type = 1).  As for BIND 8 there is no order
	to the records at a node.

	Mark
--
Mark Andrews, Internet Software Consortium
1 Seymour St., Dundas Valley, NSW 2117, Australia
PHONE: +61 2 9871 4742                 INTERNET: Mark.Andrews at isc.org