Integrated IP address management

[0002] 1. Field of the Invention

[0003] The present invention relates to management of data communications networks. More particularly, the present invention relates to an IP (Internet Protocol) address management system and method for managing IP addresses on a data communications network utilizing dynamic IP address assignment.

[0004] 2. The Background

[0005] Data communications networks are widespread and there are many different types of networks, including LANs (Local Area Networks), MANs (Metropolitan Area Networks), and WANs (Wide Area Networks). They are used for providing numerous services, both for companies and for individuals. They provide a powerful communication mechanism and allow access to various kinds of remote information. Two or more networks connected together form an internetwork (or internet). The “Internet” is a worldwide internet widely used to connect universities, government offices, companies, and private individuals. Every host (or end-user's machine running user applications) and router interface on the Internet has an IP address, which encodes its network number and host number. The combination is unique and no two machines have the same IP address. IP addresses are typically 32 bits long and are used in the source address and destination address fields of IP packets. The Source Address is the ultimate source of the IP packet; the Destination Address is the ultimate destination of the IP packet.

[0006] FIG. 1 illustrates IP address formats well known to those of ordinary skill in the art. The IP address formats are divided into five classes. The class A format, which begins with a “0” bit for indicating the class and has a 7-bit network address field and a 24-bit host address field, allows up to 126 networks with 16 million hosts each. The class B format beginning with the bit pattern “10” allows 16382 networks with up to 64K hosts each. The class C format beginning with the bit pattern “110” allows 2 million networks (e.g., LANS) with up to 254 hosts each. The class D format beginning with “1110” is for multicast in which a packet is directed to multiple hosts. Finally, the Class E format beginning with the bit pattern “11110” is reserved for future use. Network numbers are assigned by the InterNIC (Internet Network Information Center) or another administrative body in order to avoid conflicts.

[0007] These binary IP addresses are, however, rarely used by computer programs and humans to refer to hosts, mailboxes (for email), and other resources. Instead of binary numbers, ASCII strings, such as “company.com” are used. In order to avoid host name conflicts, these names are managed by the Domain Name System (DNS) (central to a domain), the Internet's official naming system. The DNS provides a hierarchical, domain-based naming scheme and a distributed database system for implementing this naming scheme. That is, conceptually, the Internet is divided into several hundred top-level domains, where each domain covers many hosts. Each domain is partitioned into subdomains, which are further partitioned, and so on.

[0008] In the hierarchical scheme, each domain controls how it allocates its subdomains (i.e., the domains under it). To create a new domain, permission is required of the domain in which it will be included. Once a new domain has been created and registered, it can create subdomains without permission from any higher domain, and keep track of all of its own subdomains. The DNS is primarily used for mapping host names to IP addresses, but it can be used for other purposes.

[0009] Every domain, whether it represents a single host or is a top-level domain, can have a set of resource records associated with it. A resource record is, for example, a five-tuple including the fields of Domain_name, Time_to_live, Class, Type, and Value. The Domain_name field tells the domain to which the record applied, and thus the primary search key used to satisfy queries. When a query is made about a domain, all the matching records of the class requested are returned by the DNS. The Time_to_live field gives an indication of how stable the record is. Information that is highly stable is assigned a large value, such as 86400 (the number of seconds in one day). Information that is highly volatile is assigned a small value, such as 60 (one minute). For Internet information, the Class field is always “IN”. The Type field tells what kind of record this is. The important types are, for example, SOA (Start of Authority), A (Address), MX (Mail exchange), NS (Name Server), PTR (Pointer), HINFO (Host information), TXT (Text), and the like. Finally, the Value field provides an actual value for the record. For example, an SOA record provides the name of the primary source of information about the name server's zone (described below), and its value is parameters of this zone. The most important record type is the A (Address) record. It holds a 32-bit IP address for a certain host. Every Internet host must have at least one IP address, so that other machines can communicate with it. Some hosts have two or more network connections (through different interfaces), in which case they will have one type A resource record (e.g., IP address) per network connection.

[0010] The naming scheme of the DNS is implemented as a corresponding hierarchical database system. The DNS name space is divided up into non-overlapping zones. Each zone contains name servers holding the authoritative information about the zone. Normally, a zone has one primary name server and one or more secondary name servers. The primary server gets its information from a file on its disk, and secondary servers get their information from the primary name server.

[0011] To obtain resource records for a domain name, for example, to get the IP address for a host name, an application program calls a library procedure called the resolver, passing it the domain name as a parameter. The resolver sends a UDP (User Datagram Protocol) packet to one of the local name servers. For example, to map a host name onto an IP address, a resolver can send a query about the host name to a local name server. If the local name server has resource records for the domain (that is, the local name server has jurisdiction over the host name being sought), it returns the authoritative resource records. The “authoritative” record is one that comes from the authority that manages the record and thus is always correct.

[0012] If, however, the domain is remote and no information about the requested domain is available locally, the name server sends a query message to the top-level name server for the domain requested. For example, when a user (DNS client) in San Francisco (SF) makes a query about John.rd.company.com for a local name server in SF, which does not have records for the host, the SF name server sends a UDP packet to the server for corn given in its database, com-server.net. It is unlikely that the com-server.net knows John.rd.company.com or rd.company.com, but it definitely knows company.com that is one of its own subdomains. Thus, com-server.net forwards the inquiry to company.com. In turn, company.com forwards the request to rd.company.com, which must have the authoritative resource records. The resource records requested are sent backward from rd.company.com to the SF name server.

[0013] Once these records get back to the SF name server, they will be entered into a cache there (local cache), in case they are needed later. However, this information is not authoritative, since changes made at rd.company.com will not be propagated to all the caches of local name servers that may know about it. For this reason, entries in a local cache should not live too long (i.e., the Time_to_live field is set to a small value).

[0014] The above query method is recursive, since each server that does not have the requested information goes and finds it somewhere, then reports back. Alternatively, when one local name server fails to find the desired records, it may return the name of the next local name server along the line to try. For example, SF name server may give the name of the San Jose name server when it cannot find a resource record for John.rd.company.com. This gives a DNS client more control over the search process.

[0015] The growth of the Internet appears to be exponential. Tens of thousands of networks are now connected to the Internet, and the number is close to doubling every year. Unfortunately, however, IP addresses are not infinite and it is rather expensive to procure more IP addresses. With the increase in the number of users of the Internet, Telcos (Telecommunication companies) and ISPs (Internet Service Providers) are faced with an increasing shortage of IP addresses.

[0016] The Dynamic Host Configuration Protocol (DHCP) has been developed to provide an automated assignment of IP addresses and to help solve the shortage of IP addresses. Conventional DHCP operation is as follows: When a DHCP client computer attempts an Internet connection, it broadcasts a DHCP request asking for any DHCP server on the network to provide it with an IP address and configuration parameters. A DHCP server on the network that is authorized to configure this client will offer an IP address by sending a reply to the client. Upon receiving this offer, the client may decide to accept it or wait for additional offers from other DHCP servers on the network. At the end, the client chooses and accepts one offer, and the chosen DHCP server sends an acknowledgement with the offered IP address having an associated “lease” time (and any other configuration parameters the client might have requested). During the lifetime of the lease, the client will repeatedly ask the server to renew. If the client chooses not to renew or if the client machine is shut down, the lease eventually expires. Once the lease expires, the IP address can be “recycled” and given to another machine.

[0017] The same IP address may not be issued to more than one user on the network. DHCP servers commonly verify addresses by using a “ping” service to determine that an IP address is not already in use. The ping utility broadcasts packets with a specific IP destination address. If there is a computer using that IP address on the network, it sends back a reply. However, this ping utility only works effectively in a small system such as a LAN and when all users on the network are running their computers. Also, depending upon the network load, routers are not obliged to respond to pings, hence ping is an unreliable mechanism. Ping is governed by the KMP protocol known to those of ordinary skill in the art.

[0018] Currently, the only solution for Telcos and ISPs to manage the shortage of IP addresses is to configure a Network Access Server (NAS) in each PoP (point of presence) so as to implement DHCP-like functionality with IP address pools so as to dynamically allocate IP addresses. That is, the NAS hands out IP addresses to users (end-users of the Telco or ISP) when the users log-in, and revokes them when the users log-out, making those IP addresses available to other users. Such mechanisms make it impossible to reliably (a) locate users by name; and (b) account for usage. A distributed DHCP server, for example, in a PoP, leases IP addresses from its IP address pool to be assigned to hosts on a temporary basis. This mechanism is more “granular” and addresses the problems stated above. These “dynamic” IP addresses are compared with “static” IP addresses that are practically permanently allocated and recorded, typically, in DNS servers.

[0019] A DHCP server may maintain the lease information of IP addresses allocated to users. However, when a user logs-out, the IP address and the user name are removed from that lease information. Therefore, a user (or one machine) may be assigned more than one IP address on any given day. In cases where the address is managed by a NAS, the allocated address is not dynamically recorded in the DNS. In cases where a DHCP server hands out the IP address, the IP address record in the DNS may be dynamically updated. Such information on dynamic IP addresses is locally handled by respective DNS servers, for example, in respective PoPs, and is always changing. Therefore, when a dynamic IP address is handed to a user at a local NAS in a PoP, Telcos and ISPs, as well as any other NAS and peer users, have no way to reliably identify or account for network usage of the user (usually known by a fully-qualified domain name).

[0020] Some systems handle dynamic updates of IP addresses in DNS servers, in which DHCP servers automatically send IP address lease information to DNS servers. However, these “Dynamic DNS” solutions are not scaleable for dealing with multiple DHCP servers spread across multiple PoPs. Because DHCP servers are currently all centralized servers, all IP requests and updates from the physically distributed users are back-hauled to the centralized DHCP server. Hence, apart from handling the IP address allocations, the DHCP servers also have to deal with updating the DNS server for every transaction.

[0021] Thus, a primary DNS server has no way to reliably identify users by their fully qualified domain names or IP addresses if the IP addresses are handed out by the NAS. This inability to identify users by their respective fully-qualified domain names or IP addresses is constantly being exacerbated because of (a) the increasing demand for network access; (b) the desire to use private IP addresses; and (c) the requirements of mobile or roaming users.

[0022] Accordingly, there is a need for a much more scaleable and distributed solution for managing dynamic IP addresses. Further, it is required that any solution use open and well-understood standards.

[0023] A method and apparatus for managing dynamic IP address allocation in a data communications network having a point of presence, a network access device associated with said point of presence, and user connections to users formed through the network access device. The system includes a protocol gateway in communication with the network access device, an authentication, authorization and accounting (AAA) server in communication with the protocol gateway, a dynamic IP allocation server in communication with the protocol gateway, a local memory in communication with the protocol gateway; and a local memory publisher, which periodically publishes the contents of the local memory over an information bus so that the contents may be received by subscribing entities.

[0024] FIG. 1 is a diagram illustrating typical IP address formats having 32 bits.

[0025] FIG. 2 is a schematic diagram illustrating an IP address management system on a data communications network according to a presently preferred embodiment of the present invention.

[0026] FIG. 3 is a schematic diagram illustrating an exemplary architecture of the IP address management system according to a presently preferred embodiment of the present invention.

[0027] FIG. 4 is a diagram showing an example of an IP address database in accordance with a presently preferred embodiment of the present invention.

[0028] FIG. 5 is a diagram showing an example of a user record database in accordance with a presently preferred embodiment of the present invention.

[0029] FIGS. 6A and 6B are process flow diagrams illustrating the data flow in the IP address management system in accordance with a presently preferred embodiment of the present invention when a user logs in and off the data communications network.

[0030] FIGS. 7A and 7B are flow charts illustrating update operations based on the IP address allocation events in accordance with a presently preferred embodiment of the present invention.

[0031] FIGS. 8A and 8B are flow charts illustrating update operations based on the user accounting events in accordance with a presently preferred embodiment of the present invention.

[0032] FIG. 9 is a flow chart illustrating update operations in DNS based on the user accounting events in accordance with a presently preferred embodiment of the present invention.

[0033] FIGS. 10A and 10B are flow charts illustrating exemplary operations producing a database for the IP address revoke events in accordance with a presently preferred embodiment of the present invention.

[0034] FIG. 10C is a flow chart illustrating operations publishing the IP address revoke events in accordance with a presently preferred embodiment of the present invention.

[0035] FIG. 11 a process flow diagram illustrating update operations based on the IP address revoke events in accordance with a presently preferred embodiment of the present invention.

[0036] Those of ordinary skill in the art will realize that the following description of the present invention is illustrative only and not in any way limiting. Other embodiments of the invention will readily suggest themselves to such skilled person after a perusal of this specification.

[0037] In the following description, a preferred embodiment of the invention is described with regard to preferred process steps and data structures. However, those skilled in the art will recognize, after perusal of this application, that embodiments of the invention may be implemented using at least one general purpose computer operating under program control, and that modification of the general purpose computer to implement the components, process steps, and/or data structures described herein would not require undue invention.

[0038] In accordance with a presently preferred embodiment of the present invention, the components, process steps, and/or data structures are implemented using C++ programs running on an Enterprise 2000 server™ running SunSolaris™ as its operating system. The Enterprise 2000 server™ and SunSolaris™ operating system are available from Sun MicroSystems, Inc. of Mountain View, Calif. This implementation is not intended to be limited in any way. Different implementations may be used and may include other types of operating systems, computing platforms, and/or computer programs. In addition, those of ordinary skill in the art will readily recognize that devices of a less general purpose nature, such as hardwired devices or devices relying on FPGA or ASIC technology, may also be used without departing from the scope and spirit of the inventive concepts disclosed herewith.

[0039] FIG. 2 schematically illustrates an IP address management system on a data communications network according to one embodiment of the present invention. In this specification, the term “data communications network” is used in a broad meaning including regional networks and the Internet or other networks, as shown in FIG. 2. The IP address management system in accordance with one presently preferred embodiment of this invention includes a network access device (NAD) 2 in a point of presence (PoP) for providing user access to the data communications network, a gateway device 4 coupled to the network access device 2, a gateway memory 6 associated with the gateway device 4, a dynamic IP address service 8 coupled to the gateway device 4 and to the data communications network, and an authentication, authorization and accounting (AAA) service 10 coupled to the protocol gateway 4 and to the data communications network. The Domain Name System (DNS) on the network is illustrated with its hierarchical structure having a primary (top-level) DNS server 12, a secondary (lower-level) DNS server 14a, and a local DNS server 14b.

[0040] A protocol gateway is a device which performs protocol conversion between different types of networks or applications. The term gateway is not meant to be limited to a single type of device, as any device, hardware or software, that may act as a bridge between the user and the networks may be considered a gateway for purposes of this application.

[0041] The network access device 2 may be a conventional Network Access Server (NAS) for the dial-up platform, the “Vega” product for the xDSL platform (available from Cisco Systems, Inc. of San Jose, Calif.), “Gatekeeper” product for the Voice Over Internet Protocol (also available from Cisco Systems, Inc.), or the like. The user may reach the network access device 2 in a PoP via a PSTN (Public Switched Telephone Network) or ISDN (Integrated Services Digital Network), or in another conventional manner. The protocol gateway 4 is a product, device, or collection of devices and software products that can host a variety of industry-standard protocols such as RADIUS (Remote Authentication Dial-In User Service), DHCP (Dynamic Host Configuration Protocol), TACACS+ (Terminal Access Concentrator Access Control Server PLUS), SNMP (Simple Network Management Protocol), and the like. The protocol gateway 4 is preferably implemented using a computer (gateway server). The local cache memory 6 is preferably a cache memory which may be distributed and/or part of the protocol gateway 4. The dynamic IP address server 8 maintains a pool 22 of IP addresses and leases the IP addresses of the pool 22. In accordance with a preferred embodiment, the dynamic IP address server 8 is a DHCP server. The dynamic IP address server 8 may be implemented in the same machine as that of the protocol gateway 4, or may be a different server coupled to the machine. The dynamic IP address server 8 may adapt a protocol other than the standard DHCP so long as necessary IP address lease functions are provided. The AAA service 10 provides user authentication, authorization and accounting information to the protocol gateway 4. The AAA service 10 is implemented in a computer, preferably the same machine or server as that of the protocol gateway 4, using any necessary communication means such as RADIUS, TACACS+, or the like to access and retrieve user profiles or user identification information stored, typically, in caches (in-memory databases). An AAA service may be provided, for example, using any authentication, authorization and accounting (AAA) server, such as Cisco ACS or Cisco Secure, both available from Cisco Systems, Inc. of San Jose, Calif.

[0042] FIG. 3 schematically illustrates an exemplary architecture of the IP address management system according to a presently preferred embodiment of the present invention. The IP address management system further includes a database adapter 16 for periodically publishing the contents of the local cache 6. The present invention uses a publisher-subscriber system for transferring data. In accordance with one presently preferred embodiment, the IP management system uses a publisher-subscriber system including a CORBA-based information broker, such as ActiveWeb from Active Software Inc. of Santa Clara, Calif., so as to deliver or transmit events published by a publisher to one or more subscribers.

[0043] The publisher-subscriber system typically includes adapters and brokers. Adapters integrate information resources such as databases, applications, and the like, into the publisher-subscriber system, enabling the information resources to work with events. An “Event” is a unit of information (or message) exchanged between publisher and subscriber. Events are exchanged over any appropriate data communications link such as an internet and the Internet. Each event is categorized or typed, to distinguish one event from others, and is self-describing. Thus, each event can be filtered by its contents. To send an event, an information resource publishes the event. To receive events of a particular type, an information resource subscribes to that type of event. A broker mediates the delivery of events among publishers and subscribers, and serves as a central point for administration. Brokers are the hubs through which all events flow. In FIG. 3, one broker 20 is shown.

[0044] The protocol gateway 4 creates an event (data to be transmitted) and then invokes the publishing operation of the database adapter 16. The protocol gateway 4 controls the database adapter 16 so as to periodically publish specific type of events (described later). Publishing an event is the act of transmitting the event to the broker 20. The broker 20 delivers to subscriber(s) of this type of events. A publisher does not have to send (or “multicast”)the events to all subscribers. The broker 20 is “transparent” for the publishers and subscribers implementing adapters configured to send/receive certain type(s) of events.

[0045] When a user attempts to log-in to the data communications network through the network access device 2, the protocol gateway 4 queries the AAA service 10 in order to determine if the user is an authorized user and if an IP address is already allocated to the user. The AAA service 10 returns user authentication, authorization and accounting information of the user in response to the query of the protocol gateway device 4. The AAA service 10 returns an IP address to the protocol gateway 4 if the user is authorized to access the data communications network and an IP address is already allocated to said user. If the user is authorized to access the data communications network, but an IP address is not already allocated to the user, the dynamic IP address server 8 leases an available IP address of the IP address pool 22 to the protocol gateway 4. Then the protocol gateway 4 allocates the returned or leased IP address to the user, and maintains a database for IP address allocation events in the local cache 6. Then, the adapter 16 periodically publishes the IP address allocation events to an information bus 24. That is, the adapter 16 implements an interface for IP address information called as IP Address Information Interface (IPAII).

[0046] Each of the IP address allocation events includes an IP address allocated to a user and associated user identification information. According to a presently preferred embodiment of the invention, the IP address allocation event includes a user name, an IP address allocated to the user, the time at which the IP address was allocated (or the lease grant time), expiry time of the IP address (or the lease time), and a home PoP ID for the user. In addition, the IP address allocation event may include a session number for the IP address and other information.

[0047] When a user logs into and logs out of the data communications network using the allocated IP address, the network access device 2 reports the user's log-in and log-out to the protocol gateway 4. The protocol gateway 4 also maintains this information as a database for user accounting events in its own buffer memory internal to protocol gateway 4 until the adapter 16 periodically publishes these user accounting events. Thus, the adapter 16 also implements an interface for user accounting information called a User Accounting Interface (UAI). The user accounting events include at least users' log-on and log-off records. The user accounting events are preferably categorized into two types of events, namely, accounting start events each including a user name, an IP address, and the time at which the user logged in, and accounting stop events each including a user name, IP address, and time at which the user logged out. The user accounting events may include other user information.

[0048] In accordance with one presently preferred embodiment of the present invention, the adapter 16 may publish these events as lists or with lists, for example, a first list collecting the IP addresses allocation events, a second list collecting the accounting start events, and a third list collecting the accounting stop events.

[0049] In order to periodically publish the contents of its internal memory, the protocol gateway 4 may use a timer. For example, the IP address allocation events are periodically published based on a timer associated with the database for the IP address allocation events, or associated with the IP Address Information Interface implemented by the adapter 16. The periodicity and timing of the publication of the IP address allocation events and that of the user accounting events may be different. The publication cycle of the user accounting events may be longer than that of the IP address allocation events. However, in accordance with a presently preferred embodiment of this invention, in addition to this timer-based publication, the protocol gateway 4 requests the publication of the IP address allocation event of the adapter 16 each time before publishing the user accounting events. This prevents the log-in (and log-out) information of a user from being received by a subscriber before receiving the IP address allocation information of that user, making the published information reliable (that is, the subscriber always receives the information in a “proper” time order).

[0050] Each protocol gateway 4 operates within a single PoP and has a single PoP ID associated therewith. In accordance with a presently preferred embodiment of the present invention, IP address allocation events are published when a PoP ID received from the network access device 2 upon a user's attempted log-in is different from the home Pop ID contained in the user profile of that user.

[0051] This works as follows. When a user attempts to log-in to the data communications network, the network access device 2 sends user information entered by the user including a user name and a password in the form of an access request to the protocol gateway 4. In order to authorize the user, the protocol gateway 4 sends an authentication request to the AAA service 10. In response, if the user is authenticated, the AAA service 10 responds with an authentication packet which includes certain user identification information from the user profile maintained at the AM service 10. This information includes the home PoP ID of the user. If the PoP ID of the attempted log-in is different from home Pop ID of the user, the user is logging-in from some different PoP which would occur, for example, in the case of a roaming user. This publication realizes a timely update of IP address information for users moving from one PoP to another.

[0052] In accordance with a presently preferred embodiment of the invention, as shown in FIGS. 2 and 3, the IP address management system includes a network controller 30 located within a Network Operation Center (NOC) coupled to the protocol gateway 4 via the information bus 24, a primary mother cache memory 32 (backed up by a secondary mother cache memory 34) associated with the network controller 30, and a database adapter 38 associated with the network controller 30. The network controller 30 centrally manages IP addresses. The adapter 38, controlled by the network controller 30, periodically publishes the contents of the primary mother cache 32. The network controller 30, through the adapter 38, subscribes to the IP address allocation events and the user accounting events published from the local cache 6 in each PoP. The network controller 30 updates its records based on the subscribed events and produces a database for IP address revoke events that includes IP addresses to be revoked. The network controller 30 maintains the database for the IP address revoke events in the primary mother cache 32 until the adapter 38 publishes the IP address revoke events. Thus, the adapter 38 implements an interface for revoking IP addresses called an IP Management Interface (IPMI), as well as implementing IPAII and UAI for subscribing to the IP address allocation events and user accounting events.

[0053] The primary mother cache 32 is a memory storage device which centrally maintains databases for the network system. In order to backup the information stored in the primary mother cache 32, the secondary mother cache 34 obtains the information from the primary mother cache 32 and stores it, preferably in a separate machine. The secondary mother caches may be distributed in some locations in addition to one in the network controller 30, though this is not shown in FIG. 3.

[0054] In accordance with a presently preferred embodiment of this invention, the primary mother cache 32 maintains an IP address database holding IP address information including IP addresses currently allocated to users (for example, an IP address table), and a user record database holding user identification information (for example, a user table, or user profile) for all PoPs covered by this IP address management system. In accordance with a presently preferred embodiment, the IP address information of the IP address database (IP Address Table) includes IP addresses currently allocated, user names to whom the IP addresses are allocated, and respective expiry time of the IP addresses, as shown in FIG. 4. The user identification information (User Table) includes user name, user's home PoP ID that defines which PoP the user normally belongs to, information on IP address allocation to the user, and other associated information and records, as shown in FIG. 5.

[0055] The local cache 6 in each PoP also maintains information on IP addresses allocated and user identification records for that PoP. In accordance with a presently preferred embodiment, the local cache 6 maintains an IP address database holding IP address information including IP addresses currently allocated to users (for example an IP address table for PoP), and a user record database holding user identification information for users having a home PoP ID of that PoP (for example, user profiles for PoP). The basic data held in the IP address database and the user record database in the local cache 6 is the same as that held in the primary mother cache 32. However, the local cache 6 only maintains information concerning users having that PoP as their home PoP and IP addresses included in the IP address pool 22 for that PoP, while the primary mother cache 32 maintains information concerning all users and IP addresses managed by this IP address managing system.

[0056] In a PoP, the local cache 6 subscribes, through the adapter 16, to the IP address allocation events published from peer PoPs and the IP address revoke events published by the network controller 30. In accordance with a presently preferred embodiment, the adapter 16 filters users' home PoP IDs on its own PoP ID, so that the local cache 6 at a PoP receives events for the users having a home PoP ID of that PoP. For example, an IP address allocation event of one local user having a home PoP ID of a PoP is received by the local cache 6 in that PoP and by the network controller 30.

[0057] When the local cache 6 receives the published events, it updates the IP address database and the user record database in the local cache 6. In accordance with a presently preferred embodiment, the local cache 6 receives the IP address allocation events and the IP address revoke events, and updates the contents of the IP address database (IP address table) and the user record database (user profile) based on the received events. For example, an entry is added to the IP address database when an IP address is reported by the IP address allocation event, and the entry is removed when the IP address is reported by the IP address revoke event. Fields in the user record database such as the IP address allocation field are checked and updated in accordance with the update/change in the IP address database. By checking and comparing the entry of the IP table and the corresponding IP address allocation field in the user table, errors, if any, in both tables are corrected and logged, in addition to updating the records in both tables.

[0058] The local cache 6 may further subscribe, through the adapter 16, to the accounting start events and update the contents of the IP address database based on the accounting start events. The local cache 6 may further subscribe to the accounting stop events, and further update the contents of the user record database based on the accounting start events and accounting stop events. For example, the expiry time of an IP address allocated will be replaced by the time the user logged out. However, it should be noted that the allocated IP addresses on the IP address database are revoked only when they are reported by the IP address revoke events published by the network controller 30, but not when reported by the accounting stop events published from the protocol gateway 4 in a PoP. This realizes that the IP address databases distributed among PoPs are centrally managed by the network controller 30.

[0059] In updating the IP address database, in accordance with a further preferred embodiment of the invention, the protocol gateway 4 may maintain a temporary database (or temporary table) for IP addresses allocated. The temporary database or table holds IP addresses that are reported by the IP address allocation events until the IP addresses are reported by the accounting start events. When an IP address on the temporary database is reported by the accounting start event, the protocol gateway 4 removes the IP address from the temporary database and adds it to the IP address database. In this implementation, the IP address is allocated to a user but the user's log-in is not yet confirmed (these IP addresses are referred to as “indeterminate” IP addresses). This is stored on the temporary database, and the IP address database contains only allocated IP addresses for which the users'log-in is confirmed.

[0060] The updating of information on IP addresses allocated and user identification records in the primary mother cache 32 in the network controller 30 is similar to that in the protocol gateway 4 described above. The network controller 30 updates the IP address database and user record database based on the IP address allocation events and the user accounting events subscribed. In a presently preferred embodiment implementing the primary mother cache 32, the disk memory 36 of the network controller 30 is updated according to the update of the primary mother cache 32. The secondary mother cache 34 is also updated in accordance with the update of the primary mother cache 32. The secondary mother cache 34 may subscribe to the published events from the primary mother cache 32 and the local cache 6 by implementing its adapter so as to update the contents.

[0061] The network controller 30 produces the database of IP address revoke events and publishes the IP address revoke events through the adapter 38. In accordance with one presently preferred embodiment, the database of IP address revoke events is produced based on a timer associated with the IP address database in the primary mother cache 32. The network controller 30 periodically examining the IP address database (IP address table) when the timer so indicates, and determines if IP addresses on the IP address table have expired.

[0062] In a further preferred embodiment of the invention, the network controller 30 may maintain in the primary mother cache 32 a temporary database for “indeterminate” IP addresses that are allocated but when the user's log-in is not yet confirmed. That is, the temporary database contains IP addresses that are reported by the IP address allocation events but not yet by the accounting start events. The IP address table contains IP addresses only after they are reported by the accounting start events. In this case, examining the expired IP addresses on the IP address table is significantly expedited. Picking up the expired IP addresses on the IP address database, the network controller 30 looks up the user record database and confirms that a user having the expired IP address logged out. If the user logged out, the network controller 30 removes the expired IP address from the IP address database and adds it to the database for IP address revoke events.

[0063] In accordance with another presently preferred embodiment of the invention, the network controller 30 may produce the database of IP address revoke events based on the accounting stop events subscribed. The network controller 30 verifies the expiry time of IP addresses on the IP address database when the IP addresses are reported by the accounting stop events. If the expiry time is verified, the network controller 30 removes the reported IP addresses from the IP address database, and adds it to the database for IP address revoke events.

[0064] In accordance with a presently preferred embodiment of the invention, the dynamic IP address server 8 is provided with a database adapter 18 so as to subscribe to at least the IP address revoke events published from the network controller 30. Thus, the database adapter 18 implements the interface for the user accounting information (User Accounting lnterface:UAI). The dynamic IP address server 8 leases an IP address from its pool 22 when requested by the protocol gateway 4, and revokes the lease when the leased IP address is reported by the IP address revoke event so as to make the IP address available to another user. The dynamic IP address server 8 may maintain a database (or list) of available IP addresses.

[0065] In accordance with a presently preferred embodiment of this invention, the primary domain name system (DNS) server 12 and lower level DNS server(s) 14 subscribe to at least the accounting start events and the IP address revoke events, and update their information (i.e., association between users' domain names and IP addresses) based on the subscribed events. This is realized by providing the DNS servers with database adapters similar to that for the dynamic IP address server 8. As shown in FIG. 3, a lower level DNS server 14 may includes a memory 40 such as a cache memory and a database adapter 42 for subscribing the events. Similarly, the primary DNS server 12 may have a primary memory 44 such as a mother cache and a database adapter 50 for subscribing to the accounting start events and IP address revoke events. Thus, each one of the adapters 42 and 50 implements the User Accounting Interface and IP Management Interface, though, in accordance with one presently preferred embodiment, they do not have to subscribe to accounting stop events.

[0066] The primary DNS server 12 may include a disk memory 46 from which the primary cache 44 obtains the data, and a secondary cache memory 48 that obtains its information from the primary cache 44. In order to back-up the information, the secondary cache memory 48 is preferably implemented by a different machine from that of the primary cache memory 44. When an IP address is reported by the accounting start event, each one of the DNS servers 12 and 14 adds an entry of the association for the IP address if the IP address is not already on the records. If the IP address already exists on the record and is associated with a different domain name, the existing domain name is replaced with a newly reported name, logging the error. If the IP address exists and is associated with the same domain name as the reported name, the DNS server may ignore that record (the record remains unchanged).

[0067] Next, the data flow and operation of the IP address management system in accordance with a presently preferred embodiment of the present invention is described. FIGS. 6A and 6B are diagrams illustrating the data flow in the system shown in FIGS. 2 and 3 when a user accesses the data communications network from a network access device 2 in a PoP. In the following description, the network access device 2 is referred to as a NAD. The protocol gateway includes operations of the protocol gateway 4 through the adapter 16. The local cache 6 and the primary mother cache 32 are both referred to as caches, unless otherwise specified. “Caches” also includes operations by the protocol gateway 4 and by the network controller 30 on the IP address databases and the user record databases maintained in the respective memories. For example, “caches update the records” means that the local cache 6 or the primary mother cache 32 updates the contents of the IP address database and/or the user record database. The Primary Mother Cache refers to the primary mother cache 32 and the corresponding operations thereon. In addition to the Primary Mother Cache, there may be some secondary mother caches at the network controller 30 and some distributed points such as main access points or routers. These mother caches maintain the information obtained from the Primary Mother Cache. The dynamic IP address server 8 is referred to as a DHCP server, including the IP address pool 22 and the operations of the adapter 18. The authentication, authorization and accounting service 10 is referred to as AAA service.

[0068] When a user logs-in on a NAD, attempting to access the data communications network, PPP (Point-to-Point Protocol) is initiated (S100). The NAD generates an access request and directs the request to the Gateway (S102). For example, in a presently preferred embodiment of the invention, a RADIUS Access-Request is generated and directed to the protocol gateway. However, other protocols can be used so long as the NAD and PG communicate. The protocol gateway directs the access request to an AAA service (S104). The AAA service then directs the request to multiple caches to retrieve the user's profile (S106). This query by the AAA service may be implemented using, for example, a Translation Service that load balances and sends packets to caches. The MA service may direct the request to a local cache 6 in the PoP, and if the user cannot be identified by the local cache 6, then it may direct the request to the primary mother cache 32.

[0069] In accordance with one presently preferred embodiment, the returned packet from the cache contains the information to identify the user and accounting information of the user. The returned packet also contains an IP address if the user is already assigned an unexpired IP address. In accordance with a further preferred embodiment, the returned packet from the cache may contain three parts: (1) a logical part that containing attributes that the Translation Service uses to perform some consistency checking and reply processing. For example, the User-Session-ID is used to identify which session is free for the incoming user; (2) a check part containing attributes that the MA service should use to verify incoming attributes with the values carried in this session. For example, one of the check attributes may be the Port-ID attribute carrying a specific value. The AAA service will then check with the incoming packet to figure out if the check attribute value matches the port into which the user has been connected; and (3) a reply part containing attributes that are lightly touched by the AAA service and the protocol gateway. For example, if a user already has an unexpired IP Address (a framed IP address), the cache will return that IP address as the Framed-IP-Address attribute.

[0070] The Translation Service then returns the pre-processed packet to the AM service. With the retrieved data, the AAA service uses various criteria such as time of the day, number of open sessions, etc., and determines if the user should be allowed to access the data communications network or not (S108). Then the AAA service returns to the protocol gateway an Access-Accept or Access-Reject packet based on the determination. If an Access-Reject is returned, the protocol gateway merely returns the information of “Access-Reject” back to the NAD (S110). If an Access-Accept packet is returned, the protocol gateway checks the reply portion of the returned Access-Accept packet to see if it can find a Framed-IP-Address attribute (S112). If the Framed-IP-Address attribute is not found or contains a value indicating a need to use dynamic IP addressing, then the protocol gateway assumes that it needs to procure an IP address for this user and does so.

[0071] Before procuring an IP address from the DHCP server, the protocol gateway ensures that mandatory reply attributes are included in the Access-Accept packet. The mandatory attributes include the User-Home-PoP-ID that is a number defining which PoP the user normally belongs to, and other associated information such as that specifying aspects of the user's agreement with the network service provider. If any of the necessary reply attributes are not supplied, the protocol gateway logs the error with the User-Name attribute that did not have the mandatory attributes and silently discards the packet. If the mandatory attributes are satisfied, the protocol gateway sends an IP address request to the DHCP server. The request is made using, for example, a RADIUS handler. The DHCP server returns an offer with an IP address to the protocol gateway (S114).

[0072] When the protocol gateway receives the offer with the IP address, it allocates that IP address to the user, and adds the allocated IP, lease grant time, the PoP ID of the user, and the expiration time to a database for IP address allocation event (S116). The database or a link list collecting events is called a collector. The database for IP address allocation events is coupled with the IP address information interface (IPAII) of the adapter 16.

[0073] The protocol gateway then strips the Access-Accept packet of the mandatory attributes such as User-Home-PoP-ID, and returns the Access-Accept packet to the NAD (S118). In the meantime, a timer associated with the database of IP address allocation events (or IP Address Information Interface) expires and the protocol gateway publishes the IP address allocation events (S120). When the IP address allocation events are received, the caches update their records accordingly (S122).

[0074] When the Access-Accept packet is successfully received by the NAD and the user has successfully logged into the system (S124), the NAD sends an Accounting Start packet including the information of User-Name, Framed-IP-Address, time logged in, etc., attributes (S126). The protocol gateway relays this information to the AAA (S128). The protocol gateway also adds this information to the database for user accounting events (Accounting Collector) (S130). When the AAA sends an acknowledgement (ACK) back to the protocol gateway, this ACK is returned to the NAD (S131). The protocol gateway may need to keep the ACK information around for a while to see if the NAD has received it. If the NAD has not received the ACK, the NAD would retransmit the Accounting Start packet to the protocol gateway, and the protocol gateway can just return this ACK again. If, after a pre-configured number of retries, the NAD has not received the ACK, the protocol gateway logs this information. These procedures make the user accounting records reliable and error tolerant.

[0075] Similarly, when a user logs out, the NAD sends an Accounting Stop packet to the protocol gateway (S132). The protocol gateway again adds this information to the Accounting Collector and forwards the Accounting Stop packet to the AAA (S133). The protocol gateway does the same acknowledge operations that it does for the Accounting Start packet.

[0076] In the meanwhile, a timer associated with the database of user accounting events (or User Accounting Interface) expires, and the protocol gateway initiates publishing the user accounting events. Before the user accounting events are published, as shown in FIG. 6B, the protocol gateway first publishes the contents of the database of IP address allocation events (S134). This may be realized by explicitly requesting the publication of the IP address allocation events through the IP Address Information Interface. Then the user accounting events are published through the User Accounting Interface (S136). When the user accounting events are received, the caches and DNS update their records accordingly (S138 and S139). However, since the user accounting event will not have the Home PoP ID information, this event goes to all caches. Caches receive this event but discard it if they cannot find the user in their user record databases (user profiles).

[0077] In a PoP, the protocol gateway collects the information about user's IP address, time it was allocated, when this IP will expire, Home PoP ID for the user and maintains this information in the database of IP address allocation events. The IP address allocation events are periodically published via the IP Address Information Interface (implemented in the adapter 16). The logic for the publication of the IP address allocation events separates the allocated IP addresses by the User-Home-PoP-ID attribute. Hence, the protocol gateway publishes the IP address allocation events whenever it sees a different PoP ID from the one it last received, when a timer expires, and when it is going to publish the user accounting events.

[0078] Next, the operations regarding IP address allocation events are described referring to FIGS. 7A and 7B.

[0079] The caches implement the IP Address Information Interface (in adapters 16 and 38), and hence subscribe to the IP address allocation events. Since the local caches at PoPs filter the events on their PoP ID, only the caches on which the protocol gateway is publishing and the Mother Caches (primary and secondary) will receive this event. As shown in FIG. 7A, when the cache receives this event, for each transmitted record, it first identifies the user in the user record database (user profile or User Table) and gets the context record (S140). Then it tries to locate the allocated IP address in the IP address database (IP Address Table) (S142). If the IP address is found in the IP Address Table, the system is in error, since this newly allocated IP address should not be found in the IP address table containing IP addresses that have been allocated to users. The cache then logs that error with details on which user's record has been impacted and then overwrites the IP address record with the new information (S144). If no record of the IP address is found in the IP Address Table, a new record is added to the IP Address Table with a short default revoke time (S146). In either case, the cache associates the user context record with this IP address record (S147). Note that only the Mother caches need to implement the IP table logic.

[0080] In accordance with a presently preferred embodiment, as shown in FIG. 7B, in the user's record in the User Table, the cache may find the session ID for the allocated IP address in the Session Info field (S148). The cache then proceeds to set that slot to a state of “Indeterminate” (S150), since the cache does not know if the user's Access-Accept packet reached the NAD successfully and the user has indeed logged on. The protocol gateway (or the network controller 30) then finds the session slot in the IP Addresses Allocated field (S152). If that slot contains a different IP address from the one that is being transmitted, the cache logs an error with details on which IP address will be impacted (S154). The cache then overwrites this slot with the new IP address (S156). If that slot does not contain an IP address, the cache fills the slot with the new IP address (S158).

[0081] In accordance with a further preferred embodiment, the Mother Caches may implement a temporary table that is used to hold these indeterminate IP addresses. This strategy will greatly speed up the IP address revoke operation that is initiated based on timers.

[0082] Next, the operations regarding the user accounting events are described referring to FIGS. 8A, 8B, and 9.

[0083] The caches implement the User Accounting Interface (in adapters 16 and 38), and therefore subscribe to the user accounting event. As shown in FIG. 8A, on receipt of this event, for each transmitted record in this event, the caches identify the user by looking up the user name in the User table (S160). If the user is not found in the User Table, the cache ignores the record (S162). When the user name is found in the User Table, the cache will identify the IP address in the IP Address Allocated field in the User Table (S164). If the IP address is not found, the cache logs the error with information on the user record that is incorrect and the IP address that is affected and ignore the record (S166).

[0084] When the IP Address is found in the IP Address Allocated field, the cache gets the offset of this IP address in the field and uses the same offset on the Session Information field (S168). It changes that session slot to logged in or out depending on what the record is carrying (accounting start or stop). For example, upon receiving an accounting start event, the time at which the IP address allocated (lease grant time) may be changed into the time at which the user logged in with this IP address (log-in time). Upon receiving the accounting stop event, the actual session time of the user may be recorded instead of lease time of the IP address.

[0085] The above operations are performed in local caches and mother caches. However, in the mother caches there are additional operations. As shown in FIG. 8B, the mother caches try to locate the IP address reported by the accounting event in the IP Address Table (S170). If the IP address is not found in the IP Address Table, the mother cache logs the error (S171). If found, the mother cache changes the expiry time of the IP address returned by the DHCP server into the real expiry time upon the user's log-off (S172).

[0086] The DNS server also implements the User Accounting Interface (in the adapter 50). However, the DNS server is obliged to subscribe to only the accounting start events. The DNS server waits for the IP revoke event from the primary mother cache to remove an entry of association between IP address and domain name. As shown in FIG. 9, on receiving the user accounting events, the DNS server only processes the accounting start event (S174). The DNS server first tries to locate the IP address which is being reported (S176). If the name associated with the IP address is not the same as the one reported by the event, the DNS server logs the error and overwrites the existing entry (S178). If the name associated with the IP address is the same as the one supplied in this event, the DNS server may ignore that record (S180). When a record is not found for the IP address, the DNS server adds a new entry for the IP address and sets the name by converting the fully qualified domain name to “host” format (S182).

[0087] In accordance with a further preferred embodiment, the mother caches implement a temporary table to hold indeterminate IP addresses. In this case, when the mother cache receives the user accounting events confirming the user's log-in, it will move the IP address records to the main IP Address Table.

[0088] Next, IP address revoke operations are described. While all the mother caches may maintain the IP Address Table, only the network controller having the Primary Mother Cache is responsible for revoking the IP addresses. The NOC may use different algorithms to revoke IP addresses. For example, in accordance with one presently preferred embodiment, the IP address revoke operation may be performed based on a timer, and in accordance with another, the IP address revoke operation may be performed when an accounting stop event is received for a user whose IP address has expired.

[0089] FIG. 10A illustrates one presently preferred embodiment of the IP address revoke operation. The network controller 30 implements a timer and associates the timer with the IP Address Table maintained in the Primary Mother Cache. When the timer expires (S184), the network controller 30 examines the IP address Table to identify IP addresses that may need to be revoked. The network controller 30 adds the expiry time (seconds) allocated for the IP address (plus a configured grace time) to the time the IP address was allocated, and compares that time with the present time (S186). If the IP address has expired, the network controller 30 looks up the associated user record in the User Table to determine if the user has logged on or not (S188). If the user is not logging on, the network controller 30 then moves that IP address to a database for IP address revoke events (S190). In accordance with a presently preferred embodiment, this database may be a table of IP addresses that need to be revoked (IP Address Revoke Table). The network controller 30 also updates the correct offset in the IP Address Allocated field of the User Table to reflect that the IP address has been revoked and adjusts the same offset in the Session Information field to reflect that this session is now available (S192). Then, as shown in FIG. 10C, based on a timer, the network controller 30 periodically publishes the IP address revoke events through the IP Address Management Interface (S200).

[0090] FIG. 10B illustrates another presently preferred embodiment of the IP address revoke operation. In this embodiment, when a user accounting event is received (S193), the network controller 30 determines that the event is an accounting start or accounting stop (S194). When an accounting start event is received, the network controller 30 updates the log-in status of the user based on each record that is transmitted (S196). However, when the network controller 30 receives an accounting stop event, it immediately verifies that the session's IP address has not expired (S197). If the IP address for the session has expired, the network controller 30 moves the IP address to the database for IP address revoke events (or IP Address Revoke Table) (S198). The following operations of updating the User Table are the same as for the previous embodiment (S199). Then, as shown in FIG. 10C, based on a timer, the network controller 30 periodically publishes the IP address revoke events through the IP Address Management Interface (S200).

[0091] As shown in FIG. 11, the IP address revoke events published by the network controller (S201) are subscribed to by the DHCP server, DNS server, secondary mother caches, and local caches (preferably associated with protocol gateways in each PoP). In accordance with a further preferred embodiment, the IP address revoke events are published with a list of IP addresses to be revoked and home PoP IDs of the IP addresses where they are stored (i.e., the home PoP ID of a DHCP server having an IP pool in which the IP address is included). The DHCP server, DNS server, secondary mother caches, and local caches implement the IP Address Management Interface via their adapters, so as to subscribe to the IP address revoke event. On receipt of this event, the DHCP server revokes the lease and marks that lease as available (S202). The DNS server removes the record for (or removes the name association with) the IP address (S204). The secondary mother caches receive all these events, as they do not filter on the Home Pop ID. They update their records by removing the IP address reference in the User Table and in the IP Address Table (S206). Since the local caches filter the events on their Home PoP ID, they would only receive events that concern users in their respective PoPs. On receipt of this record, the local cache removes the reference of the IP address from the user's record in the User Table (S208).

[0092] Accordingly, the present invention provides a scaleable solution for managing dynamic IP addresses in an integrated way, which deals with multiple DHCP servers spread across multiple PoPs. Further, according to the present invention the solution is realized using open and well understood standards.

[0093] The present invention provides IP address management whereby information on IP addresses that are dynamically assigned to users is automatically made available. The present invention also provides IP address management enables distributed DHCP servers to contain pools of IP addresses that are centrally managed. Further, the IP allocation and revocation algorithm provides the update of user profiles in distributed databases such as caches in reliable and fault-tolerant manner.

[0094] While embodiments and applications of this invention have been shown and described, it would be apparent to those skilled in the art that many more modifications than mentioned above are possible without departing from the inventive concepts herein. The invention, therefore, is not to be restricted except in the spirit of the appended claims.