(12)
`
`United States Patent
`Anderson, IV et al.
`
`(10) Patent No.:
`(45) Date of Patent:
`
`US 7,152,118 B2
`Dec. 19, 2006
`
`US007 152118B2
`
`(54) SYSTEM, METHOD AND COMPUTER
`PROGRAMI PRODUCT FOR CACHING
`DOMAN NAME SYSTEM INFORMATION
`ON ANETWORK GATEWAY
`
`(75) Inventors: Charles Edward Anderson, IV,
`Woodstock, GA (US); Thomas Carroll
`Willis, Jr., Westminister, CO (US);
`Jason Andrew Willis, Westminister,
`CO (US)
`
`c
`(*) Notice:
`
`(73) Assignee: Broadcom Corporation, Irvine, CA
`(US)
`Subject to any disclaimer, the term of this
`patent is extended or adjusted under 35
`U.S.C. 154(b) by 612 days.
`(21) Appl. No.: 10/080,676
`
`(22) Filed:
`
`Feb. 25, 2002
`O
`O
`Prior Publication Data
`US 2003/O172183 A1
`Sep. 11, 2003
`
`(65)
`
`(51) Int. Cl.
`(2006.01)
`G06F 5/16
`(52) U.S. Cl. ....................................... 709/245; 709/225
`(58) Field of Classification Search ................ 709/245,
`709/203, 202, 225
`See application file for complete search history.
`References Cited
`U.S. PATENT DOCUMENTS
`
`(56)
`
`1/2000 Huitema ..................... 709/245
`6,016,512 A
`6.256,671 B1* 7/2001 Strentzsch et al. .......... 709,227
`6,262.987 B1* 7/2001 Mogul ........................ 370/400
`6,532,490 B1* 3/2003 Lewis et al. ................ 709/217
`6,976,090 B1* 12/2005 Ben-Shaul et al. ......... TO9,246
`2002/0031102 A1
`3f2002 Wiedeman et al. ......... 370,316
`2002/0103783 A1* 8, 2002 Muhlestein .................... 707/1
`2003/0012147 A1
`1/2003 Buckman et al. ........... 370,260
`2004/0073707 A1* 4/2004 Dillon ........................ 709/245
`
`FOREIGN PATENT DOCUMENTS
`
`WO
`
`5, 2000
`WOOOf 27092
`OTHER PUBLICATIONS
`
`WO 00/27092; “DNS Relay Module in a Digital Network Modem”;
`Eicon Technology Corporation; May 11, 2000.*
`Mockapetris, P.; "Domain Names—Implementation and Specifica
`tion", RFC 1035, Nov. 1987.
`Kasser, Barbara; “Practical Internet'; 2000; Que; pp. 40-43.*
`Perry, Greg M.: “Sams Teach Yourself PCs in 24 Hours”: 1999;
`Sams Publishing; pp. 72 and 431.*
`Copy of European Search Report, dated Aug. 24, 2004, issued in EP
`application No. 03004067.9, 5 pages.
`Cohen et al. “Prefetching The Means For Document Transfer: A
`New Approach For Reducing Web Latency”.IEEE INFOCOM
`2000, Proceedings of the Nineteenth Annual Joint Conference of the
`IEEE Computer and Communications Societies, Tel Aviv, Israel.
`Mar. 26-30, 2000, pp. 854-863.
`(Continued)
`Primary Examiner William Vaughn
`Assistant Examiner Joseph Maniwang
`(74) Attorney, Agent, or Firm—Sterne, Kessler, Goldstein &
`FOX PL.L.C.
`
`(57)
`
`ABSTRACT
`
`A system, method and computer program product is pro
`vided for caching domain name system (DNS) information
`on a network gateway. In particular, a network gateway that
`interfaces one or more customer premises equipment (CPE)
`devices to an IP network maintains a centralized on-board
`cache for storing domain names and corresponding IP
`addresses. The domain names and IP addresses in the cache
`are used by the network gateway to resolve DNS queries
`generated by application programs running on the CPE
`devices in a manner that is transparent to the CPE devices
`and that does not expend CPE resources. The cache may be
`initially loaded by an attached CPE or an external network
`entity and is continuously populated with information
`extracted from DNS messages exchanged between a CPE
`device and the external IP network.
`
`31 Claims, 10 Drawing Sheets
`
`28
`
`
`
`
`
`
`
`“N-
`
`Gateway
`NS
`Cache
`
`
`
`P Network
`
`20a
`
`Domain
`Niarie
`Serwer
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1014, p. 1
`
`

`

`US 7,152.118 B2
`Page 2
`
`OTHER PUBLICATIONS
`Cohen et al., “Proactive Caching Of DNS Records: Addressing A
`Performance Bottleneck”. Applications and the Internet, 2001 Pro
`ceedings, San Diego, CA. Jan. 8-12, 2001, pp. 85-94.
`
`CableHome 1.0 Network Management and Provisioning Specifica
`tion (CH-SP-NMP-W01-101201), Cable Television Laboratories,
`Inc., Oct. 12, 2001, 125 pages.
`* cited by examiner
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1014, p. 2
`
`

`

`U.S. Patent
`
`Dec. 19, 2006
`
`Sheet 1 of 10
`
`US 7,152,118 B2
`
`JLSOH
`
`
`
`!
`
`|-
`
`(~~~~);
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1014, p. 3
`
`

`

`U.S. Patent
`
`Dec. 19, 2006
`
`Sheet 2 of 10
`
`US 7,152,118 B2
`
`
`
`803
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1014, p. 4
`
`

`

`US 7,152,118 B2
`
`U.S. Patent
`
`B012
`
`902
`
`
`
`
`
`909
`
`e?OZ
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1014, p. 5
`
`

`

`U.S. Patent
`
`Dec. 19, 2006
`
`Sheet 4 of 10
`
`US 7,152,118 B2
`
`202a
`1.
`
`
`
`
`
`
`
`( )
`
`PrOCeSSOr 444
`
`(
`
`) Main Memory 446
`
`(
`
`) Display Interface 402
`
`Display 430
`
`
`
`Secondary Memory 448
`
`Communication
`Infrastructure
`442
`
`Hard Disk Drive 450
`
`Removable Storage
`Drive 452
`
`Interface 460
`
`Removable
`Storage Unit
`454
`
`Removable
`Storage Unit
`462
`
`
`
`466
`
`Communications
`Interface 464
`
`To NetWork
`Gateway
`204a
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1014, p. 6
`
`

`

`U.S. Patent
`
`Dec. 19, 2006
`
`Sheet 5 of 10
`
`US 7,152,118 B2
`
`839
`
`
`
`
`
`
`
`
`
`
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1014, p. 7
`
`

`

`U.S. Patent
`
`Dec. 19, 2006
`
`Sheet 6 of 10
`
`US 7,152,118 B2
`
`
`
`
`
`
`
`
`
`
`
`1. 600
`
`Load Gateway DNS
`Cache at Start-up
`(Optional)
`
`Receive DNS Query
`from CPE
`
`602
`
`604
`
`614
`
`616
`
`606
`
`Unresolved
`Domain Name From
`DNS Query Stored in
`DNS Cache
`
`
`
`Yes
`
`Obtain PAddress
`Corresponding to
`Unresolved Domain
`Name From DNS
`Cache
`
`Generate Response to
`DNS Query that
`includes PAddress
`
`NO
`
`Send DNS Query to IP
`NetWork For Resolution
`
`Receive Response to
`DNS Query From IP
`NetWOrk
`
`608
`
`60
`
`
`
`
`
`DNS Query
`ReSolved?
`
`Provide DNS Response
`to CPE
`
`612
`
`Store Domain Name and
`Corresponding IPAddress
`from Response in DNS
`Cache
`
`FIG. 6
`
`Forward Response to
`CPE
`
`
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1014, p. 8
`
`

`

`U.S. Patent
`
`Dec. 19, 2006
`
`Sheet 7 of 10
`
`US 7,152,118 B2
`
`-1
`
`16
`
`31
`
`le
`169
`
`1-ty
`
`1- (2
`
`0
`
`
`
`
`
`
`
`
`
`
`
`F 6. -- A
`
`Bit of PARAMETER field
`
`
`
`-4
`
`9-1
`125
`
`Operation:
`0 Query,
`t Response
`QueryType:
`O Standard
`inverse
`2Completion 1 (now obsolete)
`3 Completion 2 (now ebsolete
`Settfanswer authoritative
`Sett message truncated
`Set it recursion destred
`Set if recursion available
`Reserved
`Response type:
`ONo error
`Fortmaterror in query
`2 Server faiture
`3 Natne does not exist.
`
`re, f2
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1014, p. 9
`
`

`

`U.S. Patent
`
`Dec. 19, 2006
`
`Sheet 8 of 10
`
`US 7,152,118 B2
`
`1-4s
`
`O
`
`16
`QUERYDOMAN NAME
`autRYTYPE
`aUERY CLASS
`
`31
`
`sal
`
`21-11-0
`
`31
`
`2-au
`
`O
`
`16
`
`RESOURCE DOMAN NAME
`
`TYPE
`
`CLASS
`
`
`
`
`
`TME TO LIVE
`RESOURCE DATALENGTH
`
`
`
`RESOURCE DATA
`
`2
`
`6. ii)
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1014, p. 10
`
`

`

`U.S. Patent
`
`Dec. 19, 2006
`
`Sheet 9 of 10
`
`US 7,152,118 B2
`
`800
`1.
`
`CPE application is executed
`
`802
`
`
`
`
`
`
`
`
`
`
`
`
`
`CPE application searches CPE
`files to identify frequently accessed
`domain names
`
`804
`
`Frequently accessed domain names are
`provided from CPE to network gateway
`
`806
`
`Network gateway generates DNS
`queries based on domain names in list
`
`808
`
`Network gateway transmits DNS
`queries to IP network for resolution
`
`810
`
`Network gateway receives responses to
`DNS queries
`
`812
`
`Network gateway stores domain names
`and corresponding IP addresses from
`responses in DNS cache
`
`814
`
`FIG. 8
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1014, p. 11
`
`

`

`U.S. Patent
`
`Dec. 19, 2006
`
`Sheet 10 of 10
`
`US 7,152,118 B2
`
`900
`1.
`
`CPE application is executed
`
`902
`
`
`
`
`
`
`
`
`
`CPE application searches CPE
`files to identify frequently accessed
`domain names
`
`904
`
`CPE application generates a DNS
`request to resolve each frequently
`accessed domain names
`
`906
`
`CPE provides DNS requests to network
`gateway for resolution purposes
`
`908
`
`Network gateway transmit DNS queries
`to P network for resolution
`
`910
`
`Network gateway receives responses to
`DNS queries
`
`912
`
`Network gateway stores domain names
`and corresponding IP addresses from
`responses in DNS cache
`
`914
`
`FIG. 9
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1014, p. 12
`
`

`

`US 7,152,118 B2
`
`1.
`SYSTEM, METHOD AND COMPUTER
`PROGRAMI PRODUCT FOR CACHING
`DOMAN NAME SYSTEM INFORMATION
`ON ANETWORK GATEWAY
`
`CROSS-REFERENCE TO RELATED
`APPLICATIONS
`
`This application is related to co-pending utility applica
`tion entitled “System and Method for Selectively Caching
`Domain Name System Information on a Network Gateway.”
`application Ser. No. 10/080,671, filed concurrently herewith
`and incorporated by reference herein in its entirety.
`
`BACKGROUND OF THE INVENTION
`
`10
`
`15
`
`2
`depicted in FIG.1. As shown in FIG. 1, a customer premises
`equipment (CPE) 102 is interfaced to an IP network 106 via
`a network gateway device 104. The CPE 102 may comprise
`a personal computer, data terminal equipment, or other user
`device capable of executing applications that send and
`receive packets over the IP network 106 via the network
`gateway 104. As used herein, the term “network gateway’
`refers to any device that interfaces one or more CPE devices
`to a network, including but not limited to an IP network. The
`IP network 106 facilitates the routing of packets between the
`network gateway 104 and other network entities, such as a
`DHCP server 108, a plurality of domain name servers 110a
`through 110m, and a host machine 112.
`The CPE 102 is assigned a primary domain name server
`from the plurality of domain name servers 110a through
`110m. The primary domain name server is the domain name
`server that CPE 102 will access in the event that it needs to
`resolve an IP address. The primary domain name server may
`be assigned to the CPE 102 in a variety of ways. For
`example, the primary domain name server may be dynami
`cally assigned during an exchange of Dynamic Host Con
`figuration Protocol (DHCP) messages that occurs between
`the CPE 102 and the DHCP server 108 when the CPE first
`accesses the network 106 to receive its initial IP address
`assignment. The CPE 102 may also be assigned additional
`domain name servers that may be accessed in the event that
`the primary domain name server is unavailable or, in some
`modes of operation, when a DNS look-up to the primary
`domain name server fails.
`In the present example, an application program running
`on CPE 102 is presented with a domain name for the host
`machine 112 for the purpose of transmitting IP packets to
`and/or from the host machine 112. In response, the appli
`cation program invokes a Software routine, sometimes called
`a resolver, to ascertain the IP address that corresponds to the
`domain name. Once invoked, the resolver generates a DNS
`query to the primary domain name server assigned to the
`CPE 102. If the DNS database in the primary domain name
`server contains the IP address associated with the domain
`name, then the primary domain name server will send a DNS
`response to the CPE 102 including that information.
`However, if the primary domain name server does not
`have access to the necessary information, several additional
`network transactions must occur, the nature of which will
`depend on whether the DNS look-up is being performed in
`accordance with a recursive resolution protocol or an itera
`tive resolution protocol.
`If recursive resolution is being utilized, the primary
`domain name server will forward the DNS query to one or
`more alternate domain name servers via the IP network 106
`to resolve the domain name. These alternate domain name
`servers may, in turn, generate requests to further domain
`name servers to resolve the query. If the domain name
`cannot be resolved after a predetermined number of queries,
`a message will be sent to the CPE 102 indicating that the
`DNS lookup has failed. Alternately, if the domain name is
`resolved, then a DNS response will be sent to the CPE 102
`providing the necessary IP address information. This propa
`gation of DNS queries between domain name servers will
`have the undesired effects of generating latency for TCP/IP
`applications running on CPE 102 and wasting bandwidth
`within the IP network 106.
`Alternately, in accordance with an iterative resolution
`protocol, if the primary domain name server cannot provide
`the necessary mapping information, a failure message is sent
`to the CPE 102, which then sends a new query to additional
`assigned domain name servers (e.g., a secondary domain
`
`1. Field of the Invention
`The present invention is generally related to data net
`works. More specifically, the present invention is related to
`a system and method for temporarily storing digital infor
`mation in one or more components of a data network, Such
`as a network gateway.
`2. Background
`An Internet Protocol (IP) address comprises a compact
`numeric identifier for a computer or other device residing on
`a TCP/IP network. Conventional TCP/IP applications utilize
`IP addresses to assign a source and destination to packets for
`routing across a network. IP addresses are typically format
`ted as 32-bit numeric addresses that are written as four
`numbers, each of which can be between 0 and 255, separated
`by periods. For example, 140.252.1.54 may constitute a
`valid IP address. N-bit IP addresses of other lengths may be
`utilized as well.
`However, to achieve an improved human interface to
`networks, users prefer to assign network devices pronounce
`able, easily remembered names. To this end, the Domain
`Name System (DNS) provides a hierarchical naming scheme
`for assigning high-level domain names to devices on a
`TCP/IP network. A typical domain name consists of a
`sequence of Sub-names separated by a period, which serves
`as a delimiter character. Each individual section of the
`domain name is termed a label, and any suffix of a label in
`a domain name may be referred to as a domain. Domain
`names are typically written with the local label first and the
`top domain last (e.g. uspto.gov).
`DNS also provides a distributed database system and
`protocol that is used by TCP/IP applications to map between
`high-level domain names and IP addresses. The database
`system is distributed in the sense that no single machine on
`a network holds all the mapping information. Rather, each
`site (e.g., university department, campus, company, or
`department within a company) maintains its own database of
`domain names and corresponding IP addresses and runs a
`server program that permits other devices on the network to
`query the database. The server program is typically referred
`to as a domain name server. Often, where the server program
`is executed on a dedicated processor, the machine itself is
`called the domain name server. The process by which a
`TCP/IP application utilizes one or more domain name serv
`ers to map a domain name to an IP address may be referred
`to as domain name resolution.
`Because no single network machine holds all DNS map
`ping information, an application program executing a DNS
`lookup may experience lag while waiting for resolution of a
`domain name. To better understand this concept, an exem
`plary domain name resolution process will now be described
`in reference to a conventional network configuration 100
`
`25
`
`30
`
`35
`
`40
`
`45
`
`50
`
`55
`
`60
`
`65
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1014, p. 13
`
`

`

`US 7,152,118 B2
`
`10
`
`15
`
`25
`
`30
`
`35
`
`3
`name server, a tertiary domain name server, and so on) until
`Such time as the name is resolved or until a predetermined
`query limit is reached. As a result, an iterative resolution
`protocol also has the undesired effects of generating latency
`and wasting network bandwidth.
`To alleviate the latency and reduced bandwidth that
`results from performing domain name resolution, some
`conventional domain name servers employ a cache of
`recently resolved domain names and IP addresses as well as
`a record of where the mapping information was obtained.
`When a client device queries the domain name server to
`resolve a name, the domain name server first determines if
`the name resides in the server database. If not, the domain
`name server examines its cache to see if the name has been
`recently resolved. If the required information resides in the
`cache, the domain name server will report the cached
`information to the client device along with an identification
`of the server from which the mapping was obtained. The
`client may then either use the IP address provided by the
`domain name server or query the server from which the
`mapping was originally obtained to determine that the
`mapping between domain name and IP address is still valid.
`While the above-described caching mechanism may
`improve the latency and bandwidth reduction associated
`with some DNS look-ups, it suffers from disadvantages. For
`example, because the cache resides on the domain name
`server, it must store name and address mappings for numer
`ous client devices. However, because server resources are
`finite, only a subset of the DNS mappings handled by the
`domain name server may be stored in the cache at any given
`point in time. As a result, the cached information may not
`always be relevant to every client on the network. In
`particular, where a network is very busy, a CPE on the
`network that transmits a DNS query may experience a high
`likelihood of a cache miss.
`Additionally, the caching mechanism described above is
`selective only in the sense that it will store DNS information
`corresponding to the most recently queried domain names.
`However, this is generally not the most efficient caching
`algorithm for a particular CPE residing on the network or for
`a particular application program being executed by a net
`work client. Furthermore, the above-described mechanism
`still requires, at a minimum, an exchange of messages
`between a client and a domain name server over the network
`which, by necessity, will result in Some lag and reduction in
`bandwidth.
`What is needed, then, is a system and method for per
`forming domain name resolution that avoids the latency and
`reduced bandwidth associated with conventional DNS look
`ups. The desired system and method should utilize domain
`name caching in a manner that is customized to the needs of
`a particular CPE or application program to reduce cache
`misses. Furthermore, the desired system and method should
`perform caching in a manner that is transparent to the CPE
`and does not require an access to the IP network for every
`instance of domain name resolution.
`
`4
`received from a CPE over the CPE interface. The DNS query
`includes an unresolved domain name. The processor deter
`mines if the unresolved domain name is stored in the cache.
`If the unresolved domain name is stored in the cache, the
`processor obtains an IP address corresponding to the unre
`Solved domain name from the cache, generates a response to
`the query that includes the IP address corresponding to the
`unresolved domain name, and provides the response to the
`CPE interface for transmission to the CPE. If the unresolved
`domain name is not stored in the cache, the processor
`provides the query to the network interface for transmission
`to a network for resolution of the query.
`In further embodiments, the network interface receives a
`DNS response from the network. The response includes a
`response domain name and an IP address corresponding to
`the response domain name. The processor stores the
`response domain name and the IP address corresponding to
`the response domain name in the cache. The processor also
`provides the response to the CPE interface for transmission
`to the CPE.
`The invention is advantageous in that it provides a cen
`tralized DNS cache for resolving DNS queries generated by
`one or more CPE devices attached to a network gateway in
`a manner that is transparent to the CPE devices and that does
`not expend CPE resources.
`The invention is also advantageous in that it permits
`caching of DNS information that is most relevant to one or
`more CPE devices attached to a network gateway.
`The invention is further advantageous in that it permits
`the resolution of DNS queries without requiring access to an
`IP network.
`Additional features and advantages of the invention will
`be set forth in the description that follows, and in part will
`be apparent from the description, or may be learned by
`practice of the invention. The objectives and other advan
`tages of the invention will be realized and attained by the
`system and method particularly pointed out in the written
`description and claims hereof as well as the appended
`drawings.
`
`BRIEF DESCRIPTION OF THE
`DRAWINGSFFIGURES
`
`The accompanying drawings, which are incorporated
`herein and form a part of the specification, illustrate the
`present invention and, together with the description, further
`serve to explain the principles of the invention and to enable
`a person skilled in the pertinent art to make and use the
`invention.
`FIG. 1 is a depiction of a conventional network configu
`ration that Supports domain name resolution in accordance
`with the Domain Name System (DNS).
`FIG. 2 illustrates an example environment in which
`embodiments of the present invention may operate.
`FIG. 3 illustrates an example environment in which
`embodiments of the present invention may operate.
`FIG. 4 depicts an example customer premises equipment
`(CPE) in accordance with embodiments of the present
`invention.
`FIG. 5 depicts an example network gateway device in
`accordance with embodiments of the present invention.
`FIG. 6 depicts a flowchart of a method for caching DNS
`information on a network gateway in accordance with
`embodiments of the present invention.
`FIG. 7A illustrates an example format for DNS messages
`generated in accordance with embodiments of the present
`invention.
`
`40
`
`45
`
`50
`
`55
`
`BRIEF SUMMARY OF THE INVENTION
`
`The present invention provides a system, method and
`computer program product for caching domain name system
`(DNS) information on a network gateway. In embodiments,
`the network gateway includes a customer premises equip
`ment (CPE) interface, a network interface, a cache for
`storing domain names and corresponding IP addresses, and
`a processor coupled to the CPE interface, the network
`interface, and the cache. In embodiments, a DNS query is
`
`60
`
`65
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1014, p. 14
`
`

`

`US 7,152,118 B2
`
`5
`FIG. 7B is a table that defines the bits of the parameter
`field of the example DNS message format of FIG. 7A.
`FIG. 7C depicts an example question section entry cor
`responding to the example DNS message format of FIG. 7A.
`FIG. 7D depicts an example answer section entry corre
`sponding to the example DNS message format of FIG. 7A.
`FIG. 8 depicts a flowchart of a method for selectively
`caching DNS information on a network gateway in accor
`dance with embodiments of the present invention.
`FIG. 9 depicts a flowchart of a method for selectively
`caching DNS information on a network gateway in accor
`dance with embodiments of the present invention.
`The present invention will now be described with refer
`ence to the accompanying drawings. In the drawings, like
`reference numbers indicate identical or functionally similar
`elements. Additionally, the left-most digit(s) of a reference
`number identifies the drawing in which the reference num
`ber first appears.
`
`10
`
`15
`
`6
`customer devices may be attached. For example, in alternate
`example environments, only a single CPE 202 is connected
`to the network gateway 204.
`The representative CPE devices 202, 212, and 214 may
`each comprise a personal computer, data terminal equip
`ment, or any other user device capable of executing appli
`cations that send and receive packets over the IP network
`206 via the network gateway 204. The IP network 206 routes
`packets between the network gateway 204 and other net
`work devices, such as a DHCP server 208 and a plurality of
`domain name servers 210a through 210n. In embodiments,
`at least a portion of the IP network 206 routes IP packets in
`accordance with well-known TCP/IP protocols.
`The network gateway 204 comprises an interface between
`the CPE devices 202, 212 and 214 and the IP network 206.
`In part, the network gateway 204 facilitates the bi-direc
`tional transfer of IP packets between the CPE devices 202,
`212 and 214 and the IP network 206 by performing essential
`physical and link layer conversions between CPE-side and
`network-side transmission protocols. In embodiments, the
`network gateway 204 may comprise a cable modem, analog
`modem, DSL modem, ISDN adapter, Ethernet card, or any
`other interface that facilitates the transmission of IP packets
`between a CPE and an IP network. In accordance with
`embodiments of the present invention, the network gateway
`204 further comprises a DNS cache 216 for caching DNS
`information that is relevant to applications running on one or
`more of the attached CPE devices 202, 212, and 214, as will
`be described in more detail below.
`FIG. 3 illustrates a more particularized example of an
`environment 300 in which embodiments of the present
`invention may operate. In the example operating environ
`ment 300, a computer system 202a, which is one embodi
`ment of CPE 202, is interfaced to the IP network 206
`through a network gateway device 204a, which is one
`embodiment of the network gateway 204. The network
`gateway device 204a includes a cable modem 302 for
`transferring IP packets between the computer system 202a
`and the IP network 206.
`The IP network 206 of the example operating environ
`ment 300 includes a hybrid fiber coaxial (HFC) network
`304, a cable headend 306, and a wide area network 310. The
`cable headend 306 includes a cable modem termination
`system (CMTS) 308 that receives packets sent from the
`cable modem 302 over the HFC network 304. The cable
`headend 306 operates to transfer IP packets between the
`HFC network 304 and the wide area network 310, thus
`enabling communication between the computer system 202a
`and other network devices, such as the DHCP server 208 and
`the plurality of domain name servers 210a through 210n. In
`an embodiment, IP packets are transferred between the cable
`modem 302 and the CMTS 308 in accordance with standard
`DOCSIS or EuroDOCSIS protocols for cable modem sys
`tems, which are well-known in the art.
`1. Example CPE in Accordance with Embodiments of the
`Present Invention
`FIG. 4 provides a more detailed example of the computer
`system 202a, which is one example of a CPE 202. As shown
`in FIG. 4, the example computer system 202a includes a
`processor 444 for executing software routines in accordance
`with embodiments of the present invention. Although a
`single processor is shown for the sake of clarity, the com
`puter system 202a may also comprise a multi-processor
`system. The processor 444 is connected to a communication
`infrastructure 442 for communication with other compo
`nents of the computer system 202a. The communication
`
`DETAILED DESCRIPTION OF THE
`INVENTION
`
`Table of Contents
`
`A. Introduction
`B. Exemplary Operating Environment
`1. Example CPE in Accordance with Embodiments of the
`Present Invention
`2. Example Network Gateway in Accordance with
`Embodiments of the Present Invention
`C. DNS Caching on a Network Gateway in Accordance with
`Embodiments of the Present Invention
`D. Selective DNS Caching on a Network Gateway Based on
`CPE Input in Accordance with Embodiments of the
`Present Invention
`E. Conclusion
`
`25
`
`30
`
`35
`
`A. Introduction
`The present invention utilize a system, method and com
`puter program product for caching Domain Name System
`40
`(DNS) information on a network gateway. In an embodi
`ment, a network gateway maintains a centralized DNS cache
`that stores domain names and corresponding IP addresses.
`The network gateway utilizes the DNS cache to resolve
`DNS queries generated by application programs running on
`one or more attached CPE devices. In particular, the network
`gateway intercepts DNS queries directed from the one or
`more CPE devices to a network and resolves them using
`information from the DNS cache in a manner that is trans
`parent to the CPE devices and that does not expend CPE
`50
`resources. The DNS cache may be pre-loaded by an attached
`CPE device or external network entity and/or populated with
`information extracted from DNS messages exchanged
`between a CPE device and the external IP network. In an
`embodiment, the DNS cache is selectively loaded based on
`a list of frequently accessed domain names generated by an
`application program running on an attached CPE and pro
`vided to the gateway.
`B. Exemplary Operating Environment
`FIG. 2 depicts an exemplary environment 200 in which
`embodiments of the present invention may operate. The
`example operating environment 200 includes a plurality of
`customer premises equipment (CPE) devices 202, 212 and
`214 interfaced to an IP network 206 via a network gateway
`204. In this example, three CPE devices are shown con
`nected to the network gateway 204; however, any number of
`
`45
`
`55
`
`60
`
`65
`
`Petitioners Microsoft Corporation and HP Inc. - Ex. 1014, p. 15
`
`

`

`7
`infrastructure 442 may comprise, for example, a communi
`cations bus, cross-bar, or network.
`Computer system 202a further includes a main memory
`446, Such as a random access memory (RAM), and a
`secondary memory 448. The secondary memory 448 may
`include, for example, a hard disk drive 450 and/or a remov
`able storage drive 452, which may comprise a floppy disk
`drive, a magnetic tape drive, an optical disk drive, or the
`like. The removable storage drive 452 reads from and/or
`writes to a removable storage unit 454 in a well known
`manner. Removable storage unit 454 may comprise a floppy
`disk, magnetic tape, optical disk, or the like, which is read
`by and written to by removable storage drive 452. As will be
`appreciated by persons skilled in the art, the removable
`storage unit 454 includes a computer usable storage medium
`having Stored therein computer Software and/or data.
`In alternative embodiments, secondary memory 448 may
`include other similar means for allowing computer programs
`or other instructions to be loaded into computer system
`202a. Such means can include, for example, a removable
`storage unit 462 and an interface 460. Examples of a
`removable storage unit 462 and interface 460 include a
`program cartridge and cartridge interface (such as that found
`in video game console devices), a removable memory chip
`(such as an EPROM, or PROM) and associated socket, and
`other removable storage units 462 and interfaces 460 which
`allow software and data to be transferred from the remov
`able storage unit 462 to computer system 202a.
`Computer system 202a further includes a display inter
`face 402 that forwards graphics, text, and other data from the
`communication infrastructure 442 or from a frame buffer
`(not shown) for display to a user on a display unit 430.
`Computer system 202a also includes a communication
`interface 464. Communication interface 464 allows software
`and data to be transferred between computer system 202a
`and external devices via a communication path 466. In an
`embodiment of the present invention, the communication
`interface 464 permits IP packets to be transferred between
`the computer system 202a and the network gateway device
`204a (see FIG. 3), which is coupled to the communication
`path 466. The communication interface 466 may comprise,
`for example, a Home Phone Network Alliance (HPNA)
`interface for communicating over an HPNA network, an
`Ethernet interface for communicating over an Ethernet, or a
`Universal Serial Bus (USB) interface for communicating
`over a USB. However, these examples are not limiting, and
`any communication interface 464 and any suitable 4 com
`munication path 466 may be used to transfer data between
`the computer system 202a and the network gateway device
`204a.
`As used herein, the term “computer program product’
`may refer, in part, to removable storage unit 452, removable
`storage unit 454, a hard disk installed in hard disk drive 450,
`or a carrier wave carrying software over a communication
`path 466 (wireless link or cable) to communication interface
`464. A computer useable medium can be a storape medium,
`including a magnetic media, optical media, or other record
`able media, or a transmission media that transmits a carrier
`wave or other signal. These computer program products are
`means for providing software to computer s