(12) Ulllted States Patent
`(10) Patent N0.:
`US 6,449,657 132
`
`Stanbach, Jr. et al.
`(45) Date of Patent:
`*Sep. 10, 2002
`
`U8006449657B2
`
`(54)
`
`INTERNET HOSTING SYSTEM
`
`(75)
`
`Inventors: Francis J. Stanbach, Jr., Menlo Park;
`Daniel G. Hoflman; Bruce R. Keiser,
`both of Los Gatos, all of CA (US)
`,V
`j
`.
`(73) Ass1gnee: Namezer0.c0m, IIIC., LOS (Jatos, LA
`(US)
`
`(*) Notice:
`
`This patent issued on a continued pros-
`ecution application filed under 37 CFR
`153(d)’ and 15 51111169 [O the twenty year
`patent
`term prov151ons of 35 U.S.C.
`15400(2)
`Subject to any disclaimer, the tern] of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 0 days.
`
`(21) Appl. No.: 09/369,770
`,
`Aug. 6’ 1999
`F1led:
`(22)
`Int. Cl.7 ................................................ G06F 15/16
`(51)
`
`(52) US. Cl.
`..
`. 709/245; 709/203, 705/14
`(58) Field of Search ................................. 709/245, 201,
`709/207, 203; 705/14; 707/203
`
`('56)
`
`References Cited
`
`
`
`6,016,512 A *
`6,119,234 A *
`
`1/2000 Huitema ..................... 709/245
`9/2000 Aziz etal.
`.................. 709/229
`
`(List continued on next page.)
`
`DP
`JP
`JP
`
`FOREIGN PATENT DOCUMENTS
`817444 A2 *
`1/1998
`........... IIO4L/29/06
`10320314 A
`12/1998
`2000242582 A
`9/2000
`
`(“St continued on next page.)
`OTHER PUBLICATIONS
`Mosher, The Microsoft Exchange User’s Handbook, 1997,
`Duke Press, 1st ed., PP- 412_419.4
`F. Manon, Free E—Mail Is Here But With Ads Aplenty, New
`York Post, Business, Jul. 27, 1995.
`Freemark, Juno Online Plan to Offer Free Electronic Mail
`Accounts for Those Prepared to Receive Ads With Mail,
`Information Access Company, Aug. 24, 1995.
`
`(List continued on next page.)
`Primary Examiner—Glenton B. Burgess
`Assistant Examiner—Bradley Edelman
`(74) Attorney. Agent, or Firm—Irell & Manella LLP
`(57)
`ABSTRACT
`
`Amethod and apparatus for providing domain name services
`includes a multi-threaded name server which concurrently
`handles multiple domain name resolution requests and is
`particulary well suited for an Internet host system control—
`ling information relating to a very large number of domain
`names. Adatabase coherency thread continuously refreshes
`a host name cache that is utilized by the multi-threaded name
`server. The multi-threaded name server may comprise a
`request dispatcher thread capable of spawning multiple child
`threads, resulting in a multi-threaded, non-blocking name
`server. One or more additional network services are also
`-
`<
`,
`Eiilfifiiil’ydiliai’émfi} 115$}??? 11133513155511.1112?
`.
`'
`.
`’
`.
`.
`’
`electromc message forwardmg serv1ces are ~prov1ded.
`In
`another embodlment, web serv1ces are prowded wherem
`hypertext markup language (HTML) pages are dynamically
`generated from data in the database corresponding to the
`requested host name,
`
`8 Claims, 9 Drawing Sheets
`
`U'S' PATENT DOCUMENTS
`5 377 354 A 4 12/ 994 Scannell et aL ____________ 709/207
`,, 395/325
`5:408:619 A
`4/ 995 Oran
`
`7/ 995 Fraser ................. 379/219
`5,434,914 A
`9/ 997 Landfield et al.
`.. 707/1041
`5,664,185 A *
`
`----- 709/228
`5,729,089 A *
`3/ 998 Allard 9t al—
`392/3393
`37:26:: 2
`g; 33: £036“ ill al’
`1”
`
`,
`,
`elmso
`e a.
`c
`.
`9/ 998 36W“ et at
`-
`-------- 709/225
`528059820 A *
`
`. 395/200.47
`5,809,242 A
`9/ 998 Shaw et al.
`.....
`
`11/ 998 McAuliffe et a1.
`5,838,790 A
`..... 380/4
`
`5,848,397 A
`12/ 998 Marsh et 81.
`....... 705/14
`5,884,038 A
`3/ 999 Kapoor
`395/200.56
`5,937,162 A
`8/ 999 Funk et al.
`............ 395/200.36
`5,937,392 A
`8/ 999 Alberts ........................ 705/14
`5,938,733 A *
`8/ 999 I-Ieimsoth et al.
`,. 709/230
`5,948,061 A *
`9/ 999 Merriman et al.
`.......... 709/219
`.m
`
`ms,
`names
`Nx—g
`
`
`was \am
`m.
`
`, -
`bur
`1
`1
`(1., .
`
`.
`Hrws
`,m
`,
`
` VN‘ ,, . "we . mm, 4 W: 4, yam.
`
`
`
`1L\
`' thtNMk
`;
`l
`2
`1
`v
`
`.
`1qu
`.
`,
`
`
`“““““
`.
`7
`2 mm
`m ,
`.
`1 m
`1
`
`-
`0W
`,
`_
`4 ,\
`mu
`
`,
`7
` m
`
`
`m , /A m
`1 ms—
`,
`
`
`
`
`i A
`A
`m\
`mr
`,
`\A 2
`\
`345.5% mm
`r
`
`v
`man 37*
`,
`
`w
`
`mossy/1R
`
`'
`
`.
`.
`1
`
`,
`41.4
`2W.
`mus:
`.
`EEG/Est ‘\7t/'
`Manon?
`was
`
`\
`
`
`
`tea/r
`mm A
`m/
`«‘m
`/
`umaasg
`£0107:ch
`V mm
`
`w ’
`
`)
`
`H M
`
`amt/Est
`mum.
`mm
`
`
`
`J
` ,w
`
`
`
`
`New Bay Capital, LLC-EX.1007
`
`New Bay Capital, LLC-EX.1007
`
`

`

`US 6,449,657 132
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`3/2001 Cobb ......................... 709/206
`6,199,102 B1
`3/2001 Gabbard et al.
`705/14
`6,205,432 B1
`
`.. 709/206
`9/2001 Dezonno
`6,289,373 B1
`................. 709/217
`10/2001 Cohn et al.
`6,308,202 B1
`FOREIGN PATENT DOCUMENTS
`
`JP
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`W0
`
`*
`
`2000270013 A
`W0 96/24213
`W0 98/12643
`WO 98/26558
`W0 99/09726
`W0 99/17505
`W0 99/18515
`W0 99/23571
`W0 99/27680
`
`9/2000
`8/1996
`3/1998
`6/1998
`2/1999
`4/1999
`4/1999
`5/1999
`6/1999
`
`........... H04L/29/06
`..
`G06F/l3/00
`
`........... H04L/29/12
`
`........... H04L/12/58
`......... G06F/15/177
`........... GO6F/15/l7
`........... H04L/12/00
`
`OTHER PUBLICATIONS
`
`S. Mohan, ‘Free Mail’ On the 'Net Forces Users to Trade 01f
`Privacy, Computerworld, vol. 29, No. 48, Nov. 27, 1995.
`D. Williamson, This EiMail Messge is Brought to You
`By .
`.
`.
`, Advertising Age, Apr. 17, 1995.
`Free E—Mail With Postage Stamp “Ads”, Post—Newsweek
`Business Information, Inc., Jul. 3, 1995.
`
`P.V. Mockapetris, et al., Development of the Domain Name
`System, Communications Architectures & Protocols, Aug.
`16—19, 1988, pp. 123—133.
`PB. Danzig, et al., An Analysis of Wide—Area Name Server
`Traffic, ACM, Aug., 1992, pp. 281—292.
`P. Mockapetris, Domain Names—Implementation and
`Specification, Internet RFC 1035, Nov. 1987.
`
`P. Mockapetris, Domain Names—Concepts and Facilities,
`Internet RFC 1034, Nov. 1987.
`
`A Brief History of BIND, Internet Software Consortium,
`<http://www.isc.org/vicw.cgi?/products/BIND—hist0ry-
`.phtml>, 1999.
`ISC BIND Plans, Internet Software Consortium, <http://
`www.isc.org/view.cgi?/products/BIND/plans.phtml>, 1999.
`
`BIND for NT (freeware), Softwarecom, <http://WWW.s0ft-
`ware.com/products/bindnt.html>, 1999.
`BIND Version 8.2XHighlights, Internet Software Consor-
`tium,
`<http://www.isc.org/view.cgi‘I/products/BIND/docs/
`bind8.2ihighlights.phtml>, 1999.
`
`* cited by examiner
`
`New Bay Capital, LLC-EX.1007
`
`New Bay Capital, LLC-EX.1007
`
`

`

`U.S. Patent
`
`Sep. 10, 2002
`
`Sheet 1 0f 9
`
`US 6,449,657 B2
`
`LOCAL HOST
`
`;
`
`FOREIGN
`
`USER
`QUERIES
`USER - RESOLVER
`PROGRAM
`
`USER
`RESPONSES
`
`QUERIES
`
`:
`:
`:
`RESPONSES -
`'
`
`
`
`FOREIGN
`NAME SERVER
`
`CACHE
`ADDITIONS
`
`REFERENCES
`
`SHARED
`
`DATABASE
`
`REFRESHES
`
`REFERENCES
`
`MASTER
`FILES
`
`NAME
`SERVER
`
`R-ESPONSES
`
`Q-UERIES
`
`FOREIGN
`RESOLVER
`
`'
`
`Flg' 1
`(PRIOR ART)
`
`MAINTENANCE
`UER
`Q
`IE8
`
`MAINTENANCE
`RESPONSES
`
`,
`;
`;
`-
`
`FOREIGN
`NAME
`SERVER
`
`
`
`New Bay Capital, LLC-EX.1007
`
`New Bay Capital, LLC-EX.1007
`
`

`

`U.S. Patent
`
`Sep. 10, 2002
`
`Sheet 2 0f 9
`
`US 6,449,657 B2
`
`276
`
`DATABASE
`
`LOCAL
`
`NETWORK
`
`INTERFACE
`
`REQUEST
`
`DISPATCHER
`
`ADDRESS
`TABLE
`
`NETWORK
`
`INTERFACE
`
`DATABASE
`
`COHERENCY
`
`MANAGER
`
`Fig. 2
`
`New Bay Capital, LLC-EX.1007
`
`New Bay Capital, LLC-EX.1007
`
`

`

`U.S. Patent
`
`Sep. 10, 2002
`
`Sheet 3 0f 9
`
`US 6,449,657 B2
`
`REQUEST
`DISPATCHER
`THREAD
`
`304
`
`312
`
`REQUEST1
`
`
`
`REQUESTn
`
`$9
`
`DATABASE
`COHERENCY
`THREAD
`
`
`
`340
`
`316
`
`332
`
`
`
`DATABASE
`
`344
`
`Iii-"'1:.......
`
`
`
`REQUEST
`THREAD
`
`HANDLER1
`
`REQUEST
`THREAD
`
`HANDLER 2
`
`REQUEST
`THREAD
`
`HANDLER n
`
`336
`
`'
`ADDRESS
`TABLE
`
`
`
`Fig. 3
`
`New Bay Capital, LLC-EX.1007
`
`New Bay Capital, LLC-EX.1007
`
`

`

`U.S. Patent
`
`Sep. 10, 2002
`
`Sheet 4 0f 9
`
`US 6,449,657 B2
`
`REQUEST
`DISPATCHER
`
`THREAD
`
`m
`/
`
`1 RECEIVE A MAIL
`OR INTERNET
`REQUEST
`
`
`
`SPAWN A
`THREAD FOR
`THE REQUEST
`
`Fig. 4
`
`DATABASE
`COHERENCY
`THREAD
`
`
`SCAN DOMAINS
`
`
`604
`TABLE FOR NEWLY
`
`
`ENTERED DOMAIN
`
`
`INFORMATION
`
`
`
`STORE NEWLY
`
`
`608
`ENTERED DOMAIN
`
`
`INFORMATION IN
`
`
`MEMORY
`
`
`
`Fig. 6
`
`REQUEST
`m
`HANDLER /
`
`THREAD
`
`
`504
`
` PARSE
`REQUEST
`
`508
` QUERY
`
`HASH TABLE
`
`
`
`
`
`
` VALID
`
`HOST NAME
`
`RETURN
`
`
`N0
`ADDRESS
`
`
` TERMINATE
`REQUEST HANDLER
`
`
`THREAD
`
`
`Fig. 5
`
`New Bay Capital, LLC-EX.1007
`
`New Bay Capital, LLC-EX.1007
`
`

`

`U.S. Patent
`
`Sep. 10, 2002
`
`Sheet 5 0f 9
`
`US 6,449,657 B2
`
`720
`
`“alice@
`
`704
`
`-'
`
`
`
`732
`
`f//
`
`4
`
`70
`
`744
`
`
`
`
`
`"aliceQS7@
`
`hOImaIIcom"
`
`724
`
`
` THEATRE
`'JUSASSIC
`AD
`PARK"
`
`
`
` MAIL
`TRANSFER
`AGENT
`
`
`716
`
`DATABASE
`
`MAIL
`TRANSFER
`AGENT
`
`
`
`744
`
`Fig. 7
`
`820
`
`KEYWORDS
`
`
`
`
`
`BORDER _.-'
`
`812
`
`816
`
`HTTP RESPONSE
`
`DESCRIPTION 808
`
`
`
`
` ADVERTISING
`
`
`DATABASE
`
`
`
`806
`
`HTTP RESPONSE
`
`Fig.8
`
`New Bay Capital, LLC-EX.1007
`
`New Bay Capital, LLC-EX.1007
`
`

`

`U.S. Patent
`
`Sep. 10, 2002
`
`Sheet 6 0f 9
`
`US 6,449,657 B2
`
`stanbachmmfindexmml
`
`DATABASE
`
`COHERENCY
`MANAGER
`
`DATABASE
`
`LOCAL
`
`NETWORK
`
`INTERFACE
`
`brucekeisermm | valid I pointer
`
`danhoffmanmm I valid I pointer I
`stanbach I valid I pointer ’ ‘
`1-—
`‘ danhoffman.oomfindex.html
`
`Fig. 9
`
`New Bay Capital, LLC-EX.1007
`
`New Bay Capital, LLC-EX.1007
`
`

`

`U.S. Patent
`
`Sep. 10, 2002
`
`Sheet 7 0f 9
`
`US 6,449,657 B2
`
`moi)
`
`TEMPLATE
`TABLE 1052
`
`AD KEYWORD
`TABlE1066
`
`“’38
`
`1062
`
`ADSTABLETOGO
`
`HTML
`
`V
`
`P“
`
`ADID
`
`1058
`
`KEYWORD
`ADCOUNTER
`TABLE 1068
`111-»
`
`1064
`
`USAGE
`HTML
`TEKT
`
`WEBSOURCE
`TABLE 1014
`
`“"E
`KEYWORDS
`
`DESCRIPTION
`TEMRLATETD
`SUURCEURL
`USAGE
`
`4
`
`<
`
`1038
`‘040
`1042
`
`1043
`10‘”
`‘046
`
`1072
`
`1020
`
`ngm‘gg4
`
`BACKGROUND
`
`1050
`
`MA
`”’20 w 1008
`
`A
`
`<—
`
`MATLTABLE1015
`
`PASSWORD
`TABLE1076
`
`CLIENTIABLE
`1012
`
`1070
`
`1082
`
`1084
`
`””3
`
`1010
`
`4_ 91°22
`‘024
`1023
`
`..........................................
`
`010005
`
`TABLE1064
`—
`
`1030
`
`“334
`
`Fig. 10
`
`New Bay Capital, LLC-EX.1007
`
`New Bay Capital, LLC-EX.1007
`
`

`

`U.S. Patent
`
`Sep. 10, 2002
`
`Sheet 8 0f 9
`
`US 6,449,657 B2
`
`/
`1108
`
`
`mg
`
`..
`
`INTERFACE
`
`xx
`
`4
`
`708
`
`HEADER
`
`BODY
`
`RESPONSE
`
`704
`
`BODY
`
`
`
`804
`808
`
`
`
` 70
`:'
`3
`808
`
`
`5
`E
`
`
`
`
`
`
`1104
`
`MAW
`
`TRANSFER
`
`AGENT
`
`716
`
`MAR
`
`TRANSFER
`AGENT
`
`
` 1E
`
`716
`
`’f/
`
`DATABASE
`
`REQUEST1
`
`304
`
`D$PATCHER
`THREAD
`
`3
`
`‘g.
`
`2 COHERENCY
`E
`THREAD
`
`"
`
`
`
`..........
`
`-
`
`.5
`
`‘- ......i ...... .--
`-'
`
`
`
`
` 308
`
`
`312
`
`REQUEST
`THREAD
`
`HANDLER,
`
`REQUEST
`
`THREAD
`HANDLER 2
`
`REQUEST
`THREAD
`
`HANDLER n
`
`Fig. 11
`
`ADDRESS
`TABLE
`
`335
`
`New Bay Capital, LLC-EX.1007
`
`New Bay Capital, LLC-EX.1007
`
`

`

`U.S. Patent
`
`Sep. 10, 2002
`
`Sheet 9 0f 9
`
`US 6,449,657 B2
`
`SERVER
`
`1230
`
`1228
`
`1226
`
`LOCAL
`NEUNORK
`
`
`
`1222
`
`HOST
`
`1224
`
`NETWORK LINK
`1220
`
`PROCESSOR
`1204
`
`MAIN
`MEMORY
`1 206
`
`1210
`
`COMMUNICATION
`INTERFACE
`1218
`
`STORAGE
`DEVOCE
`
`DISPLAY
`1212
`
`1216
`
`INPUT
`DEVICE
`
`1214
`
`CURSOR
`CONTROL
`
`FIG. 12
`
`New Bay Capital, LLC-EX.1007
`
`New Bay Capital, LLC-EX.1007
`
`

`

`US 6,449,657 B2
`
`1
`INTERNET HOSTING SYSTEM
`
`CROSS REFERENCE TO RELATED
`APPLICATIONS
`
`This application is related to US. patent application Ser.
`No. 09/369,647, entitled “MULTI-THREADED NAME
`SERVER” and 09/370,094, entitled “E-MAIL ADVER-
`TISEMENT SELECTION METHOD AND APPARATUS”,
`both filed on the same day herewith, and both of which are
`incorporated herein by reference in their entirety.
`FIELD OF THE INVENTION
`
`The field of the present invention generally relates to
`networking, and more particularly,
`to methods and tech-
`niques for hosting internet services on a network.
`BACKGROUND
`
`The Internet has become a very popular global electronic
`communication network that has brought about a wide
`variety of on-line services and development of the World
`Wide Web (WWW). The number of computers and users
`accessing the Internet continues to increase rapidly.
`Computers on the Internet generally exchange informa-
`tion in the form of packets or datagrams with each other
`using unique addresses, known as host addresses. The most
`common form of a host address is an Internet Protocol (IP)
`address, which is presently a four part sequence of numbers
`that uniquely identify a particular computer on the Internet.
`An example of a host address is the IP address
`“206.71.200.33”.
`
`Users commonly access the Internet through one or more
`clients and servers. Each client and server generally consists
`of hardware equipment executing one or more software
`processes that maintain connections to various networked
`computers. Perhaps the most common tool employed by
`users for connecting to the Internet is a client or user
`program called a “browser”. Netscape Corporation’s Navi-
`gator and Microsoft Corporation’s Internet Explorer are two
`forms of browsers, also known as “web clients”. Other
`forms of interaction on the Internet include electronic mail
`(e-mail), wherein one user sends electronic messages
`addressed to another user, usually through a mail client such
`as Qualcomm’s Eudora Lite mail client.
`Users generally do not use host addresses to connect their
`clients to remote computers or servers on the Internet.
`Rather, users employ host names, or “domain names” to
`access a particular computer or server on the Internet. In
`current Internet parlance, domain names are generally com—
`prised of alphanumeric characters that correspond to a host
`address on the Internet. An example of a domain name is
`“yahoo.com”.
`Domain names generally comprise multiple parts. A root
`name or top level domain is the ending sufiix on a domain
`name. Examples of top level domains, or root names,
`include “edu”, “com”, and “org”. Second level domains
`immediately follow a top level domain (generally a period,
`also known as “dot”, separates levels of a domain).
`Examples of second level domains include “mit”, “yahoo”
`and “icann”. Multiple additional domain levels can be added
`to a domain to yield a complete domain name, such as
`“www.yahoo.com.”
`the domain name might be
`As used in a web client,
`“http://www.yahoo.com” (the “http://” portion specifying
`the hypertext transfer protocol (HTTP) proxy), whereas in a
`mail client, the domain might be in the format of an e-mail
`
`10
`
`20
`
`30
`
`40
`
`50
`
`60
`
`0‘LIA
`
`2
`address, such as “mailto:alice@smith.com” (the “mailtoz”
`portion specifying the simple mail transfer protocol (SMTP)
`proxy).
`To provide a transparent mapping between host names
`and host addresses to users, a domain name system is
`employed. The domain name system, or DNS, in current use
`on the Internet is generally described in a technical speci—
`fication known as Internet RFC 1034, entitled “Domain
`Names—Concepts and Facilities,” and additional features
`thereof are described in a related technical specification
`known as Internet RFC 1035, entitled “Domain Namesi
`Implementation and Specification,” both of which are
`authored by P. Mockepetris.
`The domain name system described in RFC 1034 has
`three major components:
`(1) domain name space and
`records, which collectively comprise a tree-type data struc-
`ture used for the mapping; (2) name servers, which are
`server programs that hold information about the tree struc-
`ture and point to other name servers that hold information
`about the tree structure; and (3) resolvers, which are client
`programs that extract information from name servers in
`response to client requests.
`One configuration for a domain name system (DNS), and
`the DNS envisioned by RFCs 1034 and 1035, is depicted as
`a flow diagram in FIG. 1. A shared database holds domain
`space data for a local name server and a resolver that are
`associated with a local host.
`
`The contents of the shared database will typically be a
`mixture of authoritative data maintained by periodic refresh
`operations from master files by the name server, and non-
`authoritative cached data from previous resolution requests
`or maintenance queries that were answered by one or more
`foreign name servers. The contents of the shared database
`are generally in the form a flat file comprising a plurality of
`resource records (RRs). Resource records correlate a par-
`ticular host name or domain name with its host address and
`other protocol information on the Internet. As such, resource
`records generally comprise a number of fields. It should be
`noted that the name server is responsible for maintaining
`current resource records for the domain names for which it
`is the authority and any other non-authoritative domain
`names specified by the domain name system.
`The shared database is generally not a typical database.
`The shared database is called such because it represents a
`plurality of resource records distributed among various
`computer systems (or other domain name systems) through-
`out the Internet. Although the shared database might have
`somewhat current
`resource records for which it
`is the
`
`authority (or in its “zone”), the resource records for which
`it
`is not
`the authority must be periodically updated or
`“refreshed” from multiple foreign resolvers or from foreign
`name servers. Theses refresh operations are performed to
`account for changes in the mappings between host names
`and host addresses. This process occurs for authoritative
`resource records too. The shared database is thus a distrib-
`uted resource record database and is inextricably tied to
`other authoritative domain name systems on the Internet in
`order to operate in view of RFC 1034 and 1035. As such, a
`highly coherent or synchronized view of the database is
`unlikely, given the highly distributed nature of the Internet
`and the number of domains therein.
`
`When a user program, such as the browser, requests
`information from, or attempts to send information to a
`particular host name, a resolution request is passed in the
`form of a query to the resolver. The query uses as arguments
`a proxy, a host name, and other data. The resolver will check
`
`New Bay Capital, LLC-EX.1007
`
`New Bay Capital, LLC-EX.1007
`
`

`

`US 6,449,657 B2
`
`
`
`3
`he shared database for a corresponding host address to the
`lost name in the shared database or from the name server.
`If a corresponding resource record exists in the shared
`database, it will be returned to the resolver and then to the
`user program. However, if a resource record does not exist,
`hen the resolution request is passed on to a local name
`server (for authoritative data) or to a foreign name server
`(for non-authoritative data).
`The set of domains for which a particular name server is
`he authority is commonly referred to as a zone. Data outside
`he zone is the responsibility of another name server. When
`a resolution request is made for non—authoritative data—data
`hat is also not present in the shared database—the response
`is handled as a “zone transfer”. To resolve the resolution
`request, the request is passed on to a foreign name server,
`3referably the name server that is the authority for the
`domain name. Various techniques can be employed to
`resolve such requests for non-authoritative data.
`In particular, it is noted that because a foreign name server
`will resolve such requests, the latency between the query and
`the response can be great. The prior domain name system, as
`described in RFC 1034, envisions that zone transfers should
`be non-blocking, meaning that zone transfers should be
`handled immediately—that a second zone transfer should
`not wait for a first zone transfer to be completed before
`handling the second zone transfer. Thus, valuable execution
`processing cycles will not be wasted while the foreign name
`server performs the work.
`However, when authoritative requests are made or
`requests for non—authoritative data that is contained in the
`shared database, known domain name systems block con-
`current or subsequent requests until earlier requests have
`been handled. This is likely so because the name server can
`be responding to either local or
`foreign resolvers and
`because the authoritative name server must perform the
`work dictated by the request, such as checking resource
`records and formulating a response. The responses, of
`course, can vary depending on the type of the request, such
`as a mail exchange, hypertext transfer protocol, etc. Han—
`dling the resolution request can also involve querying for-
`eign resolvers and/or foreign name servers. The varied
`nature of the work performed by the name server suggests
`that it is either not efficient, or not prudent to share execution
`memory or resources when responding to resolution requests
`where the name server must perform the work. Moreover,
`the existing domain name system was designed to be
`portable, meaning it is capable of running on a variety of
`operating systems, However,
`there is no good portable
`multi-threaded application programming interface available
`on the market today. Furthermore, the overhead involved
`with multi-threading simply is not effectively amortized
`over the small number of domain names most domain name
`systems support.
`One option to overcome the drawbacks of overworking a
`domain name system is to employ multiple name servers and
`attempt to balance the workload on each name server. A
`separate computer system, a load balancer,
`is disposed
`between remote systems and multiple name servers. The
`load balancer intercepts incoming resolution requests and
`assigns those requests in a round-robin fashion to one of the
`multiple name servers. Such a technique, however, can
`further drain existing system resources, and it can require
`additional hardware (e.g., a separate computer system for
`each name server) to implement. Additionally, redundant
`information must be stored in each of the multiple name
`servers such that each name server is capable of handling the
`same sets of authoritative and non-authoritative resolution
`requests.
`
`10
`
`20
`
`30
`
`40
`
`50
`
`55
`
`60
`
`0‘LIA
`
`4
`Perhaps the most common domain name system software
`used today is the Berkeley Internet Name Domain, com-
`monly referred to as “BIND”. BIND (the most current
`version of BIND is Ver. 8.2) is an open source, general
`purpose implementation of a domain name system protocol.
`Whereas BIND may be adequate for most large-scale
`hosts supporting a limited number of domains, BIND may
`not be suitable, or may prove to be inadequate, for systems
`in which the host is designed to be a name server for many
`domains—particularly in the order of the thousands or more
`of domain names.
`
`For example, one drawback to BIND is that when
`resource records are updated, the host software often needs
`to be restarted, causing undesirable delays or down time.
`Another drawback or limitation is that BIND is a blocking
`server, meaning that only one “thread” exists for answering
`queries to resolve a domain name in the server’s zone. (As
`used herein, a “thread” refers to a part of a computer
`software code that can execute independently relative to
`other parts of the code.) The BIND system described above,
`“single threaded”, meaning that its code may activate more
`than one processor, but it does so in a way that at any given
`time only a single processor is active40n1y one thread is
`allowed to answer queries in the server’s zone at a particular
`time. If a name server using BIND serves hundreds, or
`thousands, of domain names, the latency between a resolve
`request and the response can be significant.
`These limitations or drawbacks to BIND are compounded
`by the fact that growth of the Internet is continuing to
`expand at a very rapid rate, which results in the constant
`addition of a large number of new domain names on a daily
`basis. This rapid growth of domain names is stressing the
`infrastructure of the Internet. Resource records need to be
`frequently updated, and IP addresses sometimes change.
`Since BIND often requires the host software to be restarted
`when resource records are updated, a system based on BIND
`is not well suited to maintaining an ever-expanding collec-
`tion of domain names. Further, BIND,
`in its present
`implementations, lacks a suitable mechanism for handling
`the potentially large number of queries to resolve domain
`names where the system has hundreds or thousands of
`domain names and is continuously expanding.
`Given the growth of the Internet and the fact that many
`casual users of the Internet would like to maintain domain
`names, but are often unable to do so due to costs associated
`therewith, the inventors have recognized that it would be
`advantageous to provide an improved name server and
`domain name hosting system that is scalable and that is able
`to answer simultaneous requests for thousands of different
`domain names, and to implement such a system on a single
`computer system or network.
`SUMMARY OF THE INVENTION
`
`A method and apparatus for providing domain name
`services is provided. According to one aspect of the
`invention, a multi-threaded name server handles multiple
`concurrent name requests, and is particularly well suited for
`a host system controlling information relating to a large
`number of domain names. In a preferred embodiment as
`described herein, a multi-threaded name server comprises a
`request dispatcher thread capable of spawning multiple child
`threads. For each name request received by the request
`dispatcher thread,
`the request dispatcher spawns a child
`thread to handle the request. The child threads query a host
`name cache to determine whether the host name cache
`comprises a host name matching a host name in the name
`
`New Bay Capital, LLC-EX.1007
`
`New Bay Capital, LLC-EX.1007
`
`

`

`US 6,449,657 B2
`
`5
`request. The result is a multi-threaded, non-blocking name
`server capable of handling multiple concurrent name
`requests for a large number of domain names.
`In one embodiment, one or more additional network
`services are also provided, preferably using a centralized
`database. For example,
`in a particular embodiment, elec-
`tronic message forwarding services are provided wherein an
`advertisement
`is associated with an electronic message
`based on the message contents. In another embodiment, web
`services are provided wherein hypertext markup language
`(HTML) pages are dynamically generated. In still another
`embodiment, both electronic message forwarding services
`and web services are provided on by the same system using
`the centralized database.
`
`Further embodiments, enhancements and variations of the
`foregoing are also described herein.
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`The figures in the accompanying drawings depict details
`of the invention by way of example and not by way of
`limitation, in which like reference numerals refer to like
`parts, in which:
`FIG. 1 is a block diagram illustrating a configuration for
`a domain name system as known in the prior art.
`FIG. 2 is a diagram of a multi-threaded name server in
`accordance with a preferred embodiment as described
`herein.
`
`10
`
`20
`
`FIG. 3 is a diagram illustrating operation of a multi—
`threaded name server.
`
`30
`
`FIG. 4 is a flowchart depicting acts performed by a
`request dispatcher thread.
`FIG. 5 is a flowchart depicting acts performed by a
`request handler thread.
`FIG. 6 is a flowchart depicting acts performed by a
`database coherency thread.
`FIG. 7 is a diagram depicting an e-mail forwarding and
`advertisement insertion system in accordance with a pre—
`ferred embodiment as described herein.
`
`40
`
`FIG. 8 is a diagram depicting a hypertext transfer protocol
`services system.
`FIG. 9 is a block diagram of a web server including a web
`cache system.
`FIG. 10 depicts a database schema according to a pre-
`ferred embodiment as described herein.
`
`FIG. 11 is a diagram depicting an integrated internet
`domain hosting system.
`FIG. 12 is a block diagram of a computer system which
`may be utilized in connection with one or more preferred
`embodiments as described herein.
`
`50
`
`DETAILED DESCRIPTION OF THE
`PREFERRED EMBODIMENTS
`
`Multi-threaded Name Server
`
`FIG. 2 is a conceptual diagram of a multi-threaded name
`server 275 according to a presently preferred embodiment as
`described herein. As shown in FIG. 2, the multi—threaded
`name server 275 comprises a database 291 which may store,
`among other things, IP addresses and related information.
`The multi-threaded name server 275 further comprises a
`random-access memory 290 comprising an address table
`292 and a cache 293. A database coherency manager 283
`interacts between the information stored in the database 291
`and the cache 293. A request dispatcher 282 accesses infor-
`
`60
`
`0‘LIA
`
`6
`mation from the memory 290, and particularly the cache 293
`and/or address table 292, to respond to queries or foreign
`requests as further described herein.
`It will be appreciated by those skilled in the art that many
`possible physical arrangements of memory for the database
`291 and random access memory 290 exist, and the present
`invention is not to be limited by the conceptual depiction in
`FIG. 2. For example,
`the database 291 may,
`in certain
`embodiments, be physically located at a site remote from the
`physical location of the multi-threaded name server 275, so
`long as it is accessible to the database coherency manager
`283. Further,
`the address table 292 and cache 293 are
`conveniently depicted as sharing the same random access
`memory 290, but it is not necessary that they are physically
`stored in the same memory hardware. Those skilled in the art
`will understand that
`there are many equivalent ways of
`arranging and implementing the features depicted in FIG. 2.
`A network interface 284 connects the multi-threaded
`domain server 275 to an electronic communication network,
`such as the Internet 276. A local network interface 281
`connects the multi-threaded domain server 275 to a local
`network or system controller 280, whereby the multi-
`threaded domain server 275 may be maintained or repro—
`grammed.
`In operation, resolution requests are received by the
`multi-threaded name server 275 over the Internet 276 from
`resolver software on a remote domain name system. The
`request dispatcher 282 spawns a new child thread to process
`each new resolution request received by the multi-threaded
`name server 275. The child threads (referred to herein as
`“request handler threads”) handle resolution requests and
`returns information (e.g.,
`the desired host name) to the
`request dispatcher 282, which may pass the information
`back to the source from which the resolution requests were
`initiated.
`
`FIG. 3 is a block diagram depicting in more detail
`operation of a multi-threaded name server 300 according to
`a presently preferred embodiment as described herein.
`Shown in FIG. 3 are a database 344, address table 336 and
`hash table 332, which are generally analogous to the ele-
`ments having the same descriptors shown in FIG. 2, the hash
`table 332 being an implementation of the cache 293.
`As shown in FIG. 3, incoming resolution requests 304,
`308 and 312 are received by the multi-threaded name server
`300. The resolution requests 304, 308, and 312, as noted,
`typically originate from resolver software on remote client
`systems. A continuously running request dispatcher thread
`316 spawns a new child thread (i.e., a request handler
`thread) to process each new resolution request 304, 308 and
`312. Thus, request handler threads 320, 324 and 328 are
`spawned by the request dispatcher thread 316 in response to
`resolution requests 304, 308 and 312, respectively. The
`request dispatcher thread 316 may be managed, for example,
`by an appropriate software management routine such as
`request dispatcher 282 shown in FIG. 2.
`Information
`retrieved from the inbound resolution request, such as the
`host name, is passed to the particular request handler thread
`320, 324 or 328 spawned by the request dispatcher thread
`316.
`
`The child threads (e.g., request handler threads 320, 324
`and 328) spawned by the request dispatcher thread 116 are
`executed concurrently, that is, they are “multi-threaded”.
`(As used herein, “multi-threaded” refers to a technique for
`thread execution whereby the program execution code is
`shared by more than one concurrently running, or “active”
`thread. Whereas the program variables and pointers can vary
`
`New Bay Capital, LLC-EX.1007
`
`New Bay Capital, LLC-EX.1007
`
`

`

`US 6,449,657 B2
`
`7
`between two or more threads, they are executing the same
`block of program code. Generally speaking, more than one
`process or processor can be active at any given time. This is
`in contrast to single threaded programming where only a
`single process or processor is allowed to be active at a
`particular time.) According to one embodiment,
`the pro—
`cesses are executed concurrently by a single processor.
`However, in other embodiments, multiple processors per-
`form the threads concurrently. In a preferred embodiment,
`the multiple processors can not only execute concurrently,
`but also simultaneously. Thus,
`the name server is non-
`blocking.
`FIG. 4 is a flowchart depicting steps performed by the
`request dispatcher thread 316 in accordance with a preferred
`process flow. Represented by the flowchart in FIG. 4 is
`processing of multiple request handler threads correspond-
`ing to resolution requests 304, 308 and 312 (see FIG. 3). In
`step 404, the request dispatcher thread 316 receives one or
`more resolution requests (e.g., resolution requests 304, 308
`and/or 312). In response, in step 408, a new child thread
`(e.g.,
`request handler
`thread 320, 324 and/or 328,
`respectively) is spawned to handle the request. Preferably
`the resolution request 304, 308 or 312, or at least the host
`name and type associated with the resolution request 304,
`308 or 312, is passed to the child (i.e., request handler)
`thread 320, 324 or 328 as part of process of spawning a new
`request handler thread 320, 324, 328 (step 408).
`the
`According to a presently preferred embodiment,
`multi-threaded name server 275 only responds to resolution
`requests fo