search algorithm in DNS

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
6 messages Options
Reply | Threaded
Open this post in threaded view
|

search algorithm in DNS

Bind-Users forum mailing list
I am Munkhbaatar, a master course student studying on mechanism and algorithm of DNS.
I want to search algorithm in DNS, but i have not found the documents clearly explaining this on the web.
I guess it's just a "list search", but I am not sure.
Please tell me the details of the search algorithm. 

_______________________________________________
Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe from this list

bind-users mailing list
[hidden email]
https://lists.isc.org/mailman/listinfo/bind-users
Reply | Threaded
Open this post in threaded view
|

Re: search algorithm in DNS

John Levine
In article <[hidden email]> you write:
>-=-=-=-=-=-
>
>I am Munkhbaatar, a master course student studying on mechanism and algorithm of DNS.I want to search algorithm in DNS, but
>i have not found the documents clearly explaining this on the web.I guess it's just a "list search", but I am not
>sure.Please tell me the details of the search algorithm. 

There is no search algorithm, only exact match.  See RFCs 1034, 1035, and 2181.

R's,
John
_______________________________________________
Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe from this list

bind-users mailing list
[hidden email]
https://lists.isc.org/mailman/listinfo/bind-users
Reply | Threaded
Open this post in threaded view
|

Re: search algorithm in DNS

Paul Kosinski-2
Exact matching needs a search algorithm too.

If the DNS server in only authoritative for a couple of domains (and
subdomains), a simple linear search would be adequate (or even optimal,
due to its low overhead). Many DNS servers, however, are authoritative
for multiple domains, and so might need something like a binary search
or hash table.

Reverse DNS (PTR resolution) could also need a similar algorithm, as an
ISP's server could easily cover a lot of disparate domains with its
block of assigned IP addresses. (Although the IP address, being part of
a dense range, could be converted to an index number, I suppose.)


On 9 Nov 2017 02:28:48 -0000
"John Levine" <[hidden email]> wrote:

> In article <[hidden email]> you
> write:
> >-=-=-=-=-=-
> >
> >I am Munkhbaatar, a master course student studying on mechanism and
> >algorithm of DNS.I want to search algorithm in DNS, but i have not
> >found the documents clearly explaining this on the web.I guess it's
> >just a "list search", but I am not sure.Please tell me the details
> >of the search algorithm. 
>
> There is no search algorithm, only exact match.  See RFCs 1034, 1035,
> and 2181.
>
> R's,
> John
_______________________________________________
Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe from this list

bind-users mailing list
[hidden email]
https://lists.isc.org/mailman/listinfo/bind-users
Reply | Threaded
Open this post in threaded view
|

Re: search algorithm in DNS

Tony Finch
Paul Kosinski <[hidden email]> wrote:

> Exact matching needs a search algorithm too.

Maybe Munkhbaatar is after something like:
http://www.zytrax.com/books/dns/ch2/#queries

Tony.
--
f.anthony.n.finch  <[hidden email]>  http://dotat.at/  -  I xn--zr8h punycode
Biscay, Fitzroy: North 4 or 5, occasionally 3 at first. Rough. Occasional rain
or drizzle. Moderate or good.
_______________________________________________
Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe from this list

bind-users mailing list
[hidden email]
https://lists.isc.org/mailman/listinfo/bind-users
Reply | Threaded
Open this post in threaded view
|

Re: search algorithm in DNS

Reindl Harald
In reply to this post by Paul Kosinski-2


Am 09.11.2017 um 15:55 schrieb Paul Kosinski:
> Exact matching needs a search algorithm too

no it don't - unless you call everything "search"
https://en.wikipedia.org/wiki/Hash_table

> On 9 Nov 2017 02:28:48 -0000
> "John Levine" <[hidden email]> wrote:
>
>> In article <[hidden email]> you
>> write:
>>> -=-=-=-=-=-
>>>
>>> I am Munkhbaatar, a master course student studying on mechanism and
>>> algorithm of DNS.I want to search algorithm in DNS, but i have not
>>> found the documents clearly explaining this on the web.I guess it's
>>> just a "list search", but I am not sure.Please tell me the details
>>> of the search algorithm.
>>
>> There is no search algorithm, only exact match.  See RFCs 1034, 1035,
>> and 2181

_______________________________________________
Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe from this list

bind-users mailing list
[hidden email]
https://lists.isc.org/mailman/listinfo/bind-users
Reply | Threaded
Open this post in threaded view
|

Re: search algorithm in DNS

Paul Kosinski-2
I don't call *everything* a search, but I would claim that any
practical mapping of a relatively sparse set of keys into values in
another set would require a search at some point. Only direct indexing
of sub-sequences of characters in domain names into sub-trees whose
eventual leaves were IP addresses would not involve at least simple
searches (such as in B-trees). And such trees with fully branching --
index-only, no search required -- nodes would tend asymptotically to
take exponential storage space.

(This behavior might be somewhat mitigated by the fact that domain
names are not random strings of characters, but rather follow certain
linguistic statistics.)


On Thu, 9 Nov 2017 17:56:03 +0100
Reindl Harald <[hidden email]> wrote:

>
>
> Am 09.11.2017 um 15:55 schrieb Paul Kosinski:
> > Exact matching needs a search algorithm too
>
> no it don't - unless you call everything "search"
> https://en.wikipedia.org/wiki/Hash_table
>
> > On 9 Nov 2017 02:28:48 -0000
> > "John Levine" <[hidden email]> wrote:
> >
> >> In article <[hidden email]> you
> >> write:
> >>> -=-=-=-=-=-
> >>>
> >>> I am Munkhbaatar, a master course student studying on mechanism
> >>> and algorithm of DNS.I want to search algorithm in DNS, but i
> >>> have not found the documents clearly explaining this on the web.I
> >>> guess it's just a "list search", but I am not sure.Please tell me
> >>> the details of the search algorithm.
> >>
> >> There is no search algorithm, only exact match.  See RFCs 1034,
> >> 1035, and 2181

_______________________________________________
Please visit https://lists.isc.org/mailman/listinfo/bind-users to unsubscribe from this list

bind-users mailing list
[hidden email]
https://lists.isc.org/mailman/listinfo/bind-users