Source: https://patents.google.com/patent/US7281036B1/en
Timestamp: 2019-05-19 15:40:37
Document Index: 697207657

Matched Legal Cases: ['Application No. 60', 'Application No. 60', 'art 205', 'Application No. 60', 'Application No. 60', 'Application No. 60']

US7281036B1 - Method and apparatus for automatic network address assignment - Google Patents
Method and apparatus for automatic network address assignment Download PDF
US7281036B1
US7281036B1 US09/535,279 US53527900A US7281036B1 US 7281036 B1 US7281036 B1 US 7281036B1 US 53527900 A US53527900 A US 53527900A US 7281036 B1 US7281036 B1 US 7281036B1
US09/535,279
1999-04-19 Priority to US09/294,836 priority Critical patent/US6345294B1/en
1999-10-20 Priority to US16053599P priority
2000-01-24 Priority to US17806300P priority
2000-03-24 Application filed by Cisco Technology Inc filed Critical Cisco Technology Inc
2000-03-24 Priority to US09/535,279 priority patent/US7281036B1/en
2000-09-06 Assigned to CISCO SYSTEMS, INC. A CORPORATION OF CALIFORNIA reassignment CISCO SYSTEMS, INC. A CORPORATION OF CALIFORNIA MERGER (SEE DOCUMENT FOR DETAILS). Assignors: SIGHTPATH, INC. A CORPORATION OF DELAWARE
2000-12-18 Assigned to SIGHTPATH, INC. reassignment SIGHTPATH, INC. ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: KAASHOEK, M. FRANS, LU, GANG, O'TOOLE, JAMES
2001-03-23 Assigned to CISCO TECHNOLOGY, INC. reassignment CISCO TECHNOLOGY, INC. ASSIGNMENT OF ASSIGNORS INTEREST (SEE DOCUMENT FOR DETAILS). Assignors: CISCO SYSTEMS, INC.
2007-10-09 Publication of US7281036B1 publication Critical patent/US7281036B1/en
The present invention includes a method and apparatus for automatically assigning a network address to a network device in an electronic communications network carrying inter-device communication packets to and from electronic devices located at assigned network addresses. The network device, also referred to as an appliance, communicates with at least one other network device to collect information from inter-device communication packets, which contain network address assignment information. From the network address assignment information in the communication packets, the appliance determines an available network address. The appliance assumes the available network address. The appliance may access a remote network device to retrieve an available, permanent, network configuration, including IP address.
This application is a Continuation-in-Part of application Ser. No. 09/294,836 filed Apr. 19, 1999 now U.S. Pat. No. 6,345,294, granted Feb. 5, 2002. This application claims priority to U.S. Provisional Application No. 60/160,535 filed Oct. 20, 1999 entitled “Automatic Network Address Assignment and Translation Inference” (now expired) and U.S. Provisional Application No. 60/178,063 filed Jan. 24, 2000 entitled “Method and Apparatus for Automatic Network Address Assignment” (now expired). The contents of the above applications are incorporated herein by reference in their entirety.
A typical networking appliance product, such as a computer or personal communication unit, which might or might not have a keyboard or monitor and which might not yet have configured except for some factory standard material incorporated into it, must boot when installed into a local area network (LAN). Then, a person near that appliance can configure the appliance by filling out forms or typing in parameters into screens or into a terminal.
This well-known technology has been used by many people, companies, and organizations for computers that are booting, even for simple things such as sending network configuration information to a user's personal computer. When a personal computer on a LAN boots up, one of the first things that it might do is to send out a DHCP (dynamic host configuration protocol) request message or a boot request message, and a DHCP server or boot server on the LAN, configured by an information systems department, will reply to that request and authoritatively tell the personal computer its network configuration and a set of network parameters to use. This common technique for booting machines that require assistance in booting was employed by Sun Microsystems'® network workstations during the mid 1980s.
These five or six pieces of information can go a long way in configuring the network communication part of the software on the appliance. This is well-known technology. For example, in every Microsoft® Windows® 95, 98, or Windows® NT® operating system, there is an option in the network control panel that allows a user, rather than specify the IP address of the computer manually by typing into a box, to tell the computer using a dialog check box that every time it boots it should broadcast a message and try to obtain the IP address from a DHCP server. Microsoft® Windows® NT® servers are provided with a built-in DHCP server that can provide this IP address to other computers upon request.
There are also products being sold into business locations or office environments that, instead of being configured by a boot server, can be configured by a person with a computer, such as a so-called “lap top” computer, that is attached through some kind of cable to configure the appliance. Other products can be configured through use of an LCD panel and buttons. For example, a printer or photocopy machine, when it is booted up, might display a small message on a screen saying that the user must proceed through menus and select certain options for printer or copier. Similarly, a telefacsimile machine might require a user to set the phone number and the number of rings after which the telefacsimile machine will auto-answer. These configuration settings are typically stored within the product itself. If a printer, photocopying machine, or telefacsimile machine is damaged and needs to be replaced, it will be necessary for a knowledgeable person to configure a new machine.
The prior art requires a network product to be installed by someone familiar with and highly skilled in configuring the network product onto the network/subnet on which the network product is to operate. One of the major costs of owning and operating network products/appliances is, on an ongoing basis, having someone trustworthy and knowledgeable to keep the configuration of the network appliances such that reconfiguration may be done in the event of a system crash, network appliance failure, or other such event to cause a network appliance to lose its network configuration. Further, in networks/subnets not having a local server operating as a DHCP (dynamic host configuration protocol) server or boot server, then the process of installing a network appliance becomes a manually intensive task.
FIG. 1 is an example of a network 100 in which the present invention is deployed. The network 100 includes a network (WAN) 140 (e.g., the Internet), central appliance server (CAS) 150, appliance alias 160, router 130, and subnet 180. The subnet 180 couples to and communicates with the WAN 140 through the router 130.
The subnet 180 includes an ethernet 125. Coupled to the ethernet are three computers, C1 120 a, C2 120 b, and C3 120 c. Also coupled to the subnet ethernet 125 is an appliance (A) 110 and router 130. Every electronic device 110, 120, 130 coupled to the ethernet 125 includes an ethernet card 170. For simplicity, the ethernet cards are all depicted as being the same type. Note that the router (R) 130 has two ethernet cards 170—one coupled to the ethernet 125 in the subnet 180 and the other coupled to the WAN 140.
As described in application Ser. No. 09/294,836, now U.S. Pat. No. 6,345,294, granted Feb. 5, 2002, incorporated herein by reference, the appliance 110 seeks to establish an IP address on the ethernet 125 in the subnet 180. The appliance 110 has limited knowledge about its “world” when it is first connected to the ethernet 125. For example, the appliance 110 typically knows about the central appliance server 150, Before shipping to a customer, the appliance 110 is loaded with processing routines and limited network information such as the CAS 150 address on the WAN 140, but it does not know about the computers 120 nor router 130 on the ethernet 125.
The appliance 110 is depicted as a stand-alone “box”. However, the appliance 110 may be deployed in other forms. For example, the appliance 110 may be reduced to a circuit board residing in a computer 120, software in a personal communication unit (PCU, not shown), single chip integrated into a network device including wireless phones, or incorporated or retrofitted into a network device such as the router 130.
Communication among the devices 110, 120, 130, 150 is transacted through information/communication/data packets 190 (also referred to as information packets, data packets, communication packets, or just “packets”) traveling on the network 100 (e.g., ethernet 125). The packets 190 are individual packets 190 a-j, where the packets 190 include header information for traveling across the network 140 and subnet 180. The header information follows standardized, packet, communication protocols specified by the local network configuration information. Examples of standardized, packet, communication protocols are the U.S. TCP/IP protocol and the European ISO protocol. The present invention is described as using the physical layer and the IP layer of a standardized, packet, communication protocol in carrying out its operations. However, the principles of the present invention is not limited to requiring the physical and IP layering information; the present invention is adaptable and suitable for future communication protocol changes and improvements. This description is based on having the ability to manipulate any field in an ETHERNET packet, which includes (source ETHER, destination ETHER) and/or (source iP, destination iP). Note that ETHERNET and ETHER are used interchangeably in this discussion. Further, the present invention is not bounded by a particular software language or data structure, as will be apparent from the following discussion.
The main processor routine 200 initiates operation of the automatic network assignment process in step 205. Typically, initialization/start 205 occurs during a power-up sequence of the appliance 110, during a soft-boot or hard-boot operation, or upon an externally supplied start command from a subnet device (e.g., computer 120 or router 130). Step 205 includes initializing software variables and hardware subsystems in the appliance 110 and may also provide for certain power and data communication port checks, such as determining the status of the appliance 110 ethernet interface 170 coupling the appliance 110 to the ethernet 125. Each device 110, 120, 130, etc. has a unique ETHERNET address because every ethernet card 170 includes a universally unique ethernet address. For the purpose of this discussion, MAC and ETHER mean the same thing. Both refer to an ETHERNET address, for example, “00:90:57:90:1d:ef”.
In general, the collect_packets routine 210 follows the following process. (1) The collect_packets routine 210 “listens” to network packet 190 traffic on the ethernet 125 through the appliance 110 ethernet interface 170 for a period of time, e.g. one minute. From the collected packets 190, many pairs of (ether, iP) associations are collected. (2) The collect_packets routine 210 tries to get more packets by using an ICMP contact to the following addresses: 255.255.255.255 and 224.0.0.1, a broadcast address and an “all systems on this subnet,” respectively 255.255.255.255 is a broadcast address. When one machine tries to “ping” that address, generally many machines will respond (except some machines, such as machines running the Microsoft® WINDOWS® operating system) 224.0.0.1 means, “all systems on this subnet.” When one machine tries to “ping” this address, generally many machines will reply. However, some machines, such as machines running the Microsoft® WINDOWS® operating system still do not like it. (3) The collect_packets routine 210 exits if no packets 190 are collected during any phase of its process and asserts “no local traffic” in such an event. The “no local traffic” message is issued to an interface, where the interface may be a machine-human or machine-machine interface.
However, in the event packets 190 are collected by the appliance 110, the collect_packets routine 210 does the following. Based on information included in headers of the collected packets 190, the routine 210 initializes and assigns the MAC and IP address information to one or more lists, in this embodiment, including: a watched_ip_list, watched_ether_list, used_ip_mac_table, and used_mac_ip_table, discussed later in detail in reference to FIG. 4. The watched_ip_list includes all ips but 0.0.0.0 (an address unused by any device but which may be used to indicate “self” in a packet, such as ARP or ICMP), and those IP addresses in the self-forwarding message (source and destination ether addresses describe the appliance 110 itself) and ICMP messages. In the used_ip_mac_table and used_mac_ip_table, only (source_ether, source_ip) pairs are collected from ARP request messages. Note that ARP reply messages might be intentionally misleading (i.e., bogus) because of the possibility of a so-called “proxy” ARP. Other processing routines 220-260 use the MAC and IP addresses accumulated in these tables.
After entering the collect_packets routine 210 in step 305, in step 310, the routine 210 “listens” for packets 190 traveling on the subnet ethernet 125. As discussed above, in one embodiment, step 310 lasts for one minute; in an alternate embodiment, the duration adapts depending on the amount of network packet 190 traffic occurring.
The appliance 110 collects all the packets 190 “heard” during the listening step, step 310. “Listening” for packets 190 includes collecting packets 190, which results in getting many packet (ether, iP) pairs. In one embodiment, step 310 retains all duplicate packet pairs. In an alternate embodiment, step 310 filters duplicate packet pairs. In yet another embodiment, a pre-filter (not shown) is used to store only MAC and IP addresses, dispensing with the rest of the packet 190 in a real-time manner.
In step 325, lists of so-called known and “possible” subnet devices (e.g., computers 120) are begun (i.e., initialized, defined, allocated, etc.), where the lists are initially filled with the data captured during the listening and parsing steps 310, 320, respectively. Recalling that ARP and ICMP messages (and others) have both request and reply types, it should be understood that not all (ether, iP) pairs are deterministic. In other words, in at least one ARP or ICMP message type—ARP request—the (mac/ether, iP) pairs are indeed pairs (i.e., the mac/ether address of the ether card 170 is in the same device 120 a as the IP address assigned to that device 120 a); in other ARP or ICMP message types, the (mac/ether, iP) pairs are indeterminate, not necessarily belonging to the same physical device 120 a. Therefore, in one embodiment, the processor routine 200 uses multiple lists for storing deterministic and indeterminate MAC and IP addresses.
The watched_ip_list 410 includes IP address data from the packets 190 “heard” and parsed during the listening and parsing steps 310, 320 (FIG. 3), respectively. The term “watched” indicates “indeterminate” or “probable.” As an IP address (e.g., IP1, IP2, IP3, and so on) becomes associated with a particular respective MAC address, the IP address is added to a “used” list 430, 440. The watched_ip_list 410 includes all P addresses, but 0.0.0.0 and those IP addresses in a self-forwarding message and ICMP messages.
The watched_ether list 420 includes ether/mac address data from the packets 190 “heard” and parsed during the listening and parsing steps 310, 320 (FIG. 3), respectively. Like the watched_ip_list 410, the term “watched” indicates “indeterminate.” As an ether address (e.g., ether 1, ether 2, ether 3, and so on) becomes associated with a respective IP address, the ether address is added to one or both of the “used” lists 430, 440.
The used_ip_mac_table 430 stores mappings from a unique IP address to its corresponding MAC address. The term “used” indicates that the address mapping has been determined to be assigned to a device 200. For our purposes, a MAC address is equivalent to an ether address and is being used to distinguish between indeterminate ether addresses and deterministic (i.e., determined) ether/mac addresses. In the used_ip_mac_table 430, the collect_packets routine 210 only stores (source_ether, source_ip) pairs to the “used” lists 430 found in ARP request messages because an ARP reply message might be “bogus” because of a so-called “proxy” ARP.
The used_mac_ip_table 440 stores mappings from a unique MAC address to its corresponding IP address. The term “used” is the same as for the used_ip_mac_table 430.
Step 335 causes network 100 and subnet 180 packet 190 traffic; in other words, devices 120, 130, etc. responsively put packets onto the network 100, where packets traveling between devices on a network is loosely referred to as “traffic.” In one embodiment, the excite local network devices 120 (FIG. 1) step 335 sequences through the IP addresses stored in the watched_ip_list 410 (FIG. 4). Pseudocode statements to excite (generate packets 190 from) the devices 120, 130 may include:
(i) send ICMP request using (my_ether, IP) to (‘ff:ff:ff:ff:ff:ff’, 255.255.255.255),
(ii) send ICMP request using (my_ether, IP) to (‘ff:ff:ff:ff:ff:ff’, 224.0.0.1)},
where my_ether is the appliance 110 ethernet 125 address, IP is an IP address retrieved from the watched_ip_list 410, (‘ff:ff:ff:ff:ff:ff’, 255.255.255.255) is a broadcast address, and (‘ff:ff:ff:ff:ff:ff’, 224.0.0.1) is an address that means “all systems and subsystems on this subnet 180.”
The appliance 110 uses the pseudocode statements to provoke/elicit address information from the other network devices 120. So here statement (i) “pings” the broadcast address, which causes many machines 120, except some machines such as machines using the Microsoft® Windows® operating system, to respond. Using the 224.0.0.1 address, statement (ii) “pings” all systems 120, 130 on the subnet 180. Many machines 120, except some machines such as those employing the Windows® operating system, generally respond. From the response packets 190 captured by the appliance 110, the collect_packets routine 210 parses network device 120, 130 address data.
In step 340, the collect_packets routine 210 stops listening for packets from the computers 120, router 130, and possibly other devices not shown and devices elsewhere in the network 100. Like steps 320 and 325, the captured packets 190 are parsed and added to the lists 400 (FIG. 4) in steps 345, 350, respectively. An “any packets captured” query 355 tests, by scanning the lists 400 or checking a software flag, to determine if any packets 190 were captured during steps 310-350. A “no packets captured” determination indicates that the appliance 110 may not be connected to the subnet ethernet 125; the collect_packets routine 210 in turn asserts a “no local traffic” message in step 360, then returns to the main processor routine 200 (FIG. 2). If packets 190 have been captured, the collect_packets routine 210 returns to the main processor routine 200 for further processing.
Referring again to FIG. 2, if packets are unable to be collected in the collect_packets routine 210, then the main processor routine 200 exits in step 270. A higher-level routine (not shown) restarts the main processor routine 200 after a specified period of time to retry automatic network configuration. If, however, packets 190 are collected in the collect_packets routine 210, the appliance 110 main processor routine 200 next attempts to determine at least one IP address on the same subnet 180. The “get one ip_A on the same subnet” routine 220, or, simply, get_ip_A routine 220, is used to do this. Note, the term “ip_A” indicates a determined address, on the same subnet 180 in this case.
FIG. 5 is a detailed flow diagram of a process embodiment of the get_ip_A routine 220. This routine 220 looks for a used “slot” (i.e., computer/device 120 definitely on the IP subnet 180) with which the appliance 110 may locally communicate during later, main processor routine 200, process steps 230-260 (FIG. 2).
The get_ip_A routine 220 begins in step 505, where initialization occurs. The routine 220 then begins “listening” to network traffic in step 510. Between steps 510 and 545, the routine 220 communicates with IP addresses stored in the watched_ip_list 410 to elicit/provoke communication packet 190 traffic. The communication packets 190 potentially include information for adding more IP addresses and/or ether addresses from the so-called indeterminate lists 410, 420 to the so-called determined lists 430, 440 (FIG. 4).
A loop begins in step 515, which sets up a counter ip_X to traverse through the watched_ip_list 410 IP addresses. If the loop is determined to be “done,” the FOR loop terminates listening for packets 190 in step 545. If the FOR loop is “not done,” then the body of the loop (steps 520-540) is performed. In step 520, an “external” ARP request for ip_X is sent from the appliance 110. By external, it is meant that the appliance pretends to be (my_ether, ext_ip), where my_ether is the appliance 110 ethernet 170 address, and ext_IP is a known, unassigned IP address that is not an IP address in the range of IP addresses of the subnet 180. For example, if the subnet 180 has an IP address range between A.B.C.D1-A.B.C.D2, where letters A, B, and C range from 0 to 255 and D1-D2 represent a range between 64 and 127, then IP addresses such as A.B.C.D3 or A.B.C.D4, where D3 and D4 range from 0 to 63, such as 45 or 0, are potential external addresses used as the appliance alias 160 IP address, or the CAS 150 IP address may be used as ext_IP during these communication steps.
Proxy_arp or ARP_fake means that one machine (e.g., router 130) might reply to an ARP request message from an internal machine (e.g., C1 120 a) to outside_subnet machines. Generally, machines that reply for (i.e., representing, doing the ARP_fake) outside_subnet machines are routers. For example, assume a subject subnet includes IP addresses in the range, A.B.C.D1-A.B.C.D2. One machine, A.B.C.D3, on the subject subnet might request, “who has A.B.C.D4, tells A.B.C.D3”. In this message, IP address A.B.C.D4 is clearly outside of the subject subnet, and no machine on the subject subnet is supposed to reply to that ARP request message. But, if a router on the subject subnet, A.B.C.D5, where D5 has a value between the range of 64 and 127 such as 65, (MAC is gg:hh:ii:jj:kk:ll, where g, h, i, j, k and l have a value between the range of O-f in hexidecimal), is doing ARP_fake, it will send out an ARP reply saying “A.B.C.D3 is at gg:hh:ii:jj:kk:ll”. In this way, if machine_X wants to send a message to A.B.C.D3, it will send the message to the router, which is correct in reality. One exception for that is no ARP_fake router will do that for any reply from an outside_subnet IP address (i.e., outside the subject subnet). For example, if a machine sends out an ARP request saying “who has A.B.C.D6, where D6 has a value between the range of 0 to 63 such as 43, tells A.B.C.D4”, the router, A.B.C.D5, will not do ARP fake (if it is doing that), since A.B.C.D4 is an outside_subnet IP address.
To have more chances (i.e., evoke more responses) to find router 130, in step 535, the appliance 110, again posing to be a device external from the subnet 180 (e.g., central appliance server 150), sends an “external” ICMP request to the address (ether_X, ip_X). If the (ether_X, ip_X) address is an address/node (e.g., C1 120 a) on the local subnet, that node must send a response to the router 130 in order to communicate with that “external” device. Such a determination is made in step 540, where the ICMP reply to the “external” device or ARP reply from the router 130 is determined from communication packets issued by either the computers 120 or the router 130. Since determining either an ICMP reply to, for example, (ether_router, CAS 150) or an ARP reply from (ether_router, ip_router) is deterministic (i.e., confirming (ether_A, ip_A) from step 530), then the loop is done and exits to step 545 to terminate listening for network communication packet 190 traffic. Otherwise, the loop continues at step 515.
Following step 560, the get_ip_A routine 220 returns control to the main processor routine 200 (FIG. 2) in step 565. If no ether_router is identified during the get_ip_A routine 220, then an assertion is made in step 555 that “no machine has been found on the same hub.” After such assertion, the get_ip_A routine 220 is completed in step 565, returning control to the main processor routine 200 (FIG. 2).
Referring again to FIG. 2, if an ip_A was not found by the get_ip_A routine 220, then no machine/node is determined to be on the same subnet, and the main processor routine 200 exits in step 270. However, if an ip_A is determined to be on the same subnet by the get_ip_A routine 220, then packets 190 have been collected in the collect_packets routine 210, and an IP address on the local subnet has been determined in the get_ip_A routine 220. Now, using the determined subnet address, ip_A, one unused IP on the subnet is determined in the “find one unused IP based on ip_A” routine 230, also referred to as the find_unused_IP routine 230.
FIG. 6 is a flow diagram of an embodiment of a process used to determine an unused IP address based on the “known” IP address, ip_A, determined during the get_ip_A routine 220. In general, the find_unused_IP routine 230 seeks to determine an unused IP address over a certain range of IP addresses that are possibly located in the subnet 180 to which the appliance 110 is coupled. The following discussion includes usage of ARP and ICMP communication packets, so a short description of each is provided now.
For machine_X to confirm if one IP address is in use or which machine owns a specific IP address, machine_X generally sends out a broadcast packet saying: “who has ip_Y tell (mac_X, ip_X)”. If some machine has that ip_Y, an ARP reply is sent to mac_X as “ip_Y is at mac_Y telling mac_X”. If there is no ARP reply after an ARP request, generally it means no other machine owns that IP address. To confirm that conclusion, machine_X may send out the broadcast packet two or three times.
A disadvantage to sending out an ARP message, such as “who has ip_X tell (mac_X, ip_X),” is that it might cause IP conflict if the IP address is really being used by another machine. Note, however, to avoid bad information from polluting ARP caches on the network, a host sending an ARP message (probe) may set its own IP address in the ARP packet to 0.0.0.0. An advantage for sending out an ARP message is that it is the most deterministic way to determine if one IP address is in use or not. No machine intends to delay a reply to an ARP request.
An ICMP contact is familiarly known as what a so-called “ping” does. Here, machine_X sends out an ICMP request saying “(mac_Y, ip_Y), please respond to (mac_X, ip_X).” If ip_Y is outside machine X's subnet, mac_Y will be the subnet router's MAC address. Generally, ip_Y will reply as “(mac_X, ip_X), (mac_Y, ip_Y) is responding to you”. Again, if ip_Y is outside machine_X's subnet, mac_Y is the router's ETHER address. One valuable point to this process is that if ip_Y thinks ip_X is the same subnet and there is no ARP entry in its ARP table, it will first send out an ARP request. This provides a way for determining if ip_Y thinks one IP is in the same subnet or not. The snap shot of the ARP table is provided again for easy reference:
Internet (IP) Address Physical (mac/ether) Address Type
W1.X1.Y1.Z1 gg:hh:ii:jj:kk:ll Dynamic
W2.X2.Y2.Z2 gg:hh:ii:jj:kk:ll Dynamic
where W1, X1, Y1, Z1, W2, X2, Y2 and Z2 range from 0 to 255.
An IP address located absolutely outside the subnet 180 is calculated in step 610. In one embodiment, calculating an IP address absolutely outside the subnet 180 on which the determined IP address device (e.g., computer 120 a, which for the purposes of this discussion will be used as the so-called “determined IP address device,” ip_A). In one embodiment, the routine 230 determines a so-called “external” address, which is depicted in FIG. 1 as the appliance alias 160, by calculating a bit-AND with (224.0.0.0+random(400)). In alternate embodiments, other calculations may be performed to determine a subnet address external from the subnet.
Using the appliance alias 160 IP address, the routine 230 in the appliance 110 sends an ICMP request to the ip_A 120 a in step 615. A query 620 determines if an ARP request is generated by the ip_A 120 a to the appliance alias 160. If the ip_A 120 a issues an ARP request for the appliance alias 160, then the ip_A 120 a does not know the subnet 180 mask on which it resides. Responsively, the routine 230 confesses in step 625 that “ip_A does not know the subnet mask,” and the routine 230 returns control back to the main processor routine 200 (FIG. 2) in step 650. If there is no ARP request from the ip_A 120 a, as determined by the query 620, then the process continues in step 630.
where, << is defined to mean “insert” here.
After creating the candidate subnet address list in step 635, a second loop is set up in step 640 where a process loops once for each candidate subnet address. While the loop is not done, the loop performs a query 655, checking several conditions with regard to the candidate subnet address. The conditions may include: (i) is the candidate IP address (ip_Y) in the watched_ip_list 410 (FIG. 4), (ii) is ip_Y=IP_A, or (iii) is ip_Y=ip_router? If the query 655 answers “yes” to any of the three conditions listed, the process returns to the top of the loop 640. If the candidate IP address meets none of the conditions of query 655, then processing continues in step 660.
The immediate action provided by the find_unused_IP routine 230 is the following. First the routine 230 makes twenty so-called “helper” addresses based on the candidate address ip_Y in step 740. Next, the routine 230 sends an ICMP request from the helper addresses (note, the appliance 110 is actually performing the issuance of the ICMP requests) to the candidate address ip_Y 115 in step 745. In this case, however, the candidate address is (ether_Y, ip_Y), rather than all the previous addresses, (my_ether, ip_Y) which use the ether address of the appliance 110. Therefore, ip_Y, such as the router 130, may react to the ICMP request from (my_ether, the twenty addresses) to (ether_Y, ip_Y). In other words, because ip_Y does not know at least one of those twenty addresses, possibly, then it will seek to update its internal ether and IP address tables by issuing an ARP request for such information. All other devices, 110, 120, 130 update their internal ether and IP address tables with the information from within the ARP request, indicating the real router 130 ether and IP addresses. So, if an ARP request is seen, then the query 750 returns control back to the top of the loop 640 (FIG. 6). If no ARP request is seen, then query 750 proceeds to step 755.
Referring again to FIG. 6, once each candidate subnet IP address has been tested for whether or not each is unused, as determined by loop query 640, a query 645 is performed to determine if an unused IP address has been found. If an unused IP address has not been found, then processing continues in the outer loop, begun in step 630, where additional candidates subnet addresses based on ip_A 120 a, determined in step 635, continues. If the unused IP address found query 645 is answered “yes”, then the routine 230 returns control to the main processor routine 200 in step 650. Also, if the outer loop that started in step 630 is complete, then the process of routine 230 has not found an unused IP address and returns control back to the main processor routine 200 in step 650.
Referring again to FIG. 2, if the find_unused_IP routine 230 determines that ip_A does not know the subnet mask or an unused IP address is not found, then the main processor routine 200 exits in step 270. Otherwise, if an unused IP address has been found in the routine 230, then the next device IP address (and corresponding ether address) to locate is the router 130. Finding the router 130 is performed in a “find (ether_router, ip_router)” routine 240, also referred to as the find_router routine 240. Before discussing the details of the find_router routine 240, a brief, broad overview is discussed. First, the find_router routine 240 tries to use the ip_unused address determined from the find_unused_IP routine 230 to provoke some responses from the subnet 180 devices 120, 130. This step is done by ARP contacting many different IP addresses. Generally, routers are located at an IP address at the lower end of the subnet 130, where “lower end” means low number in the sequence of possible IP addresses dedicated to the subnet 180. Although the main processing routine 200, and subroutines contained therein, do not know the subnet 180 mask, each possible subnet mask based on ip_A 120 a may be tried. In this way, many other ether addresses can be collected for further processing, where collection continues to occur in the tables 400 (FIG. 4).
Next, the find_router routine 240 tries to UDP-contact each possible ether address that has been collected so far in the tables 400 (FIG. 4). A UDP (User Datagram Protocol) packet allows for an entry in a field that indicates the TTL (time-to-live) to a device supporting this option/feature, such as a router. If a UDP packet with TTL=0 is sent to an IP-forwarding machine, that machine will respond with an ICMP time_exceeded reply immediately. That is how traceroute works. (An example of traceroute is, using a Web-based traceroute server, a user can trace the route through the Internet from the server to the user's own IP address. This is an invaluable aid to Internet connectivity troubleshooting, since it allows the user to check whether different parts of the Internet are using the expected route to the user's IP address.) Therefore, sending a UDP packet can be used to detect if one machine is a router or not. So, if one possible ether/mac address sends a reply to the UDP contact, then that is an indication that the reply was issued by the router 130. So, the appliance 110, via the find_router routine 240, gets the routers 130 IP and ether addresses from that reply message. If no device 120, 130 responds to the UDP contact with a reply, then the find_router routine 240 confesses “failed this time”.
FIGS. 8 and 9 are flow diagrams of an embodiment of a process for the find_router routine 240. After entering the find_router routine 240 in step 805, which performs parameter receiving and local variable initialization, the located unused IP address is assigned to a “known” IP address variable, ip_A (for example, C1 120 a) in step 810. Then, the find_router routine 240 starts to listen to the network for network packets 190 in step 815, similar to packet 190 collection in collect_packets routine 210 (FIG. 3).
netmask = netmask ^ (1<<i);
base_IP = ip_A & netmask;
possible_router_ip_list [base_IP + j]= 1; # reduce redundancy }
put all [iP−5, iP+5] into possible_router_ip_list;
put 10 random IP addresses based on IP into
possible_router ip_list; }
At this point, it is possible at this point that the IP address of the router 190 has been determined by the find_router routine 240, therefore, the determination query 840 checks if the router IP address has been determined. If the answer to the IP address determined query 840 is “yes”, then, in step 845, control is returned to the main processor routine 200 (FIG. 2) with the router ether and IP address information. If the router IP address determined query 840 has answered “no”, then a router ether address determined query 850 is performed.
If the router ether address determined query 850 is answered “no”, then process continues in FIG. 9, at point G. If the query 850 is answered “yes”, then the ether address of the router 130 is put into the watched_ether_list 420 (FIG. 4) in step 855. Following step 855, the process continues at point G (FIG. 9).
FIG. 9 continues with the process of the find_router routine 240 begun in FIG. 8. Point G is the entry point from FIG. 8. If the process reaches this point, then the IP address of the router 130 has yet to be determined. To begin the determination process for the router 130 IP address, a loop is set up for testing each ether address in the watched_ether_list 420 (FIG. 4) in step 905. If the loop is not done, then step 910 is performed. Step 910 sends a UDP packet from (my_ether, ip_unused), (note, my_ether is the ether address of the appliance 110), to the central appliance server 150. But, rather than using the CAS 150 ether address, one at a time, the ether addresses stored in the watched_ether_list 420 (FIG. 4) are used, the UDP therefore taking on the form of (watched_ether, ip_CAS). The UDP packet provides a means for eliciting (or generating) a router-specific response. The UDP packet is issued by the appliance 110 with a TTL (time-to-live) parameter set to a value so small (e.g., zero) so that the router cannot possibly send and receive a response in the parameter time resulting from the UDP packet, forcing the router to tell the sending address (i.e., the appliance 110) that the packet is “too old.”
If the appliance 110 sees an ARP reply from the asked IP address, as determined by query 940, then in step 945, the ip_router address is parsed out of the reply and used later in the main processor routine 200 (FIG. 2). If the query 940 does not see the ARP reply from the asked IP address, then, if the find_router routine 240 in step 950 finds the ether_router in the used_mac_ip_table 440 (FIG. 4), the corresponding IP address is taken from the used_mac_ip_table 440 and assigned to a corresponding ip_router variable in step 955 for future processing. If the ether_router is not found by query 950 (and inherent search of the used_mac_ip_table 440), then, in step 960, a confession is made indicating the find_router routine 240 has “failed to find the local router.” Note that this and other such confessions are issued to an interface, possibly machine-to-human or machine-to-machine, or both.
In general, the find_subnet_mask routine 250 performs the following process. First, the routine 250 assumes that the 32-bit subnet mask is regular, which is all ones and then all zeros (i.e., 11..100..0). Second, the find_subnet_mask routine 250 tries to find the boundary between the ones and zeros. Also, the routine 250 assumes, in one embodiment, that each subnet 180 to which the appliance 110 is coupled is greater than 224.0.0.0 and less than or equal to 255.255.255.252. Third, the routine 250 starts to search, using a binary search technique or other search technique that accomplishes the same result, for the boundary between the subnet mask ones and zeros. For each bit tested that is on the boundary between the ones and zeros of the subnet mask, that bit of ip_A is XOR'd to get another IP address. Fourth, the routine 250 uses the calculated IP address to ICMP contact ip_A. If there is an ARP request from ip_A, the routine 250 confirms that the subnet mask bit being tested should be a “0”. Otherwise, that bit is determined to be a “1”. In this way, the routine 250 figures out the boundary quite fast.
FIG. 15 is a 5-bit linear scale illustrating the relationship between a 5-bit subnet mask and 5-bit subnet addresses. A subnet mask indicates which bits are shared by all nodes in a subnet. Subnet masks are typically viewed in hexadecimal or binary forms. Viewed in binary form, the subnet mask directly indicates all address bits that must match in a packet address such that a network node employing the network mask considers the address to be associated with the subnet. For subnet mask bit positions having a ‘1’, corresponding bits in the address are relevant to a determination of whether an address is within the subset's range of addresses. For all subnet mask bit positions having a ‘0’, all corresponding bits in the address are inconsequential to a determination of whether an address is within the subnet's range of addresses.
Four subnet masks are provided above the scale: ‘10000’, ‘11000’, ‘11100’, and ‘11110’. As indicated, the range of addresses corresponding to each subnet mask varies inversely with the number of ‘1's’ in the subnet mask. For example, subnet mask ‘10000’ has the widest range of matching addresses; subnet mask ‘11110’ has the narrowest range of matching addresses.
Different packet types—ARPs and ICMPs—may be used to evoke a response from nodes also on the local subnet. Even if the source is on the same subnet as the known node, a response to those packets is only evoked if the source is unknown to the known node. To ensure that a least one source address is unknown, random source addresses within the possible subnet regions are used. It is assumed that one of the random sources is not known to the nodes on the subnet, so that at least one of the nodes issues a response to learn the source of the unknown address(es).
For example, still referring to FIG. 15, let the subnet span from positions 23 to 20 and employ a subnet mask ‘11100’. Let the node located at the known address be located at position 21. ARP packets issued from unknown addresses in the region covered by subnet mask ‘11110’ to the known node evoke ARP requests. ARP packets issued from unknown addresses in the region covered by subnet mask ‘11100’ to the known node also evoke ARP requests. So, no deterministic information about the subnet mask transition point is learned from communications from addresses within these two subnet mask address ranges since both sets evoke responses. However, ARP packets issued from just outside the subnet mask ‘11100’ subnet region (e.g., position 19) do not evoke responses from the known node. The subnet mask may be determined by finding the bit at which responses are evoked from an address having the bit in one binary state and not the other binary state, which supports communications from just within the subnet mask transition point and not from just outside the transition point. Since no response is evoked from addresses ‘110xx’, ‘100xx’, or ‘0xxxx’ (where x's are “Don't Care's”, the process determines the third bit in the subnet mask to be the transition point; hence, subnet mask ‘11100’ is determined.
known address 0 1 1 0 0 0 1 0 1 1
subnet mask to be determined 1 1 1 1 1 0 0 0 0 0
response addresses 0 1 1 0 0 x x x x x
(a) if send packet from 0 1 0 0 0 0 1 0 1 1
(b) and send packet from 0 1 1 1 0 0 1 0 1 1
(c) if send packet from 0 1 1 0 1 0 1 0 1 1
(d) and send packet from 0 1 1 0 0 1 1 0 1 1
(e) if send packet from 0 1 1 0 0 0 0 0 1 1
(f) and send packet from 0 1 1 0 0 0 1 1 1 1
ip1 = ip_A^ (1<< pointer);
ip1_base = ip1 & current_netmask1;
where the ^ indicates an operation that performs an XOR function, the <<indicates an operation that performs a left shift of the number 1 “pointer” number of times, and the “&” indicates to perform a Boolean-AND function on the operands.
In FIG. 11, point J begins the continued process of the find_subnet_mask routine 250 begun in FIG. 10. For brevity, all steps depicted in FIG. 11 parallel for a second set of variables and subnet masks, etc., the process depicted and described in FIG. 10 beginning at step 1030. Differences may be determined empirically. The process of FIG. 11 tests the subnet mask having one more “1” bit than the process beginning in step 1030 of FIG. 10. This is indicated in step 1115, wherein the left shift step is performed for “pointer−1”. The process of FIG. 11 proceeds to point K in FIG. 12.
The last condition, an ELSE statement in step 1205, covers a case where the submask has not been found and there are no conditions above which satisfy the state of the flag1 and flag2 variables. Therefore, a warning, “failed to guess a subnet mask,” is presented to the user, transmitted to an interface, or used by other processes in the processing routine 200 (FIG. 2). This case again breaks out of the loop started in step 1015 (FIG. 10), jumping to point L in FIG. 10.
If the ELSE IF condition is step 1205 is Boolean-true, then step 1210 is performed. In step 1210, the pointer is set halfway between the lower and upper subnet guess boundaries. This is part of the binary search procedure used by the find_subnet_mask routine 250. Following step 1210, the process returns to point M (FIG. 10), where the “tested all rightmost mask bit locations” query 1015 is performed. If all rightmost mask bit locations have been tested, as determined by query 1015, then the last subnet mask position is used as the net mask in step 1020. Processing control returns to the main processor routine 200 (FIG. 2) in step 1025.
Referring again to FIG. 2, if the find_subnet_mask routine 250 fails to guess a subnet mask, then a default subnet mask, 255.255.255.255 is used, and the main processor routine 200 exits in step 270. Otherwise, after trying to figure out the subnet mask in the find_subnet_mask routine 250, a final check is performed to ensure an unused IP address has been determined in the subnet 180. A “final conflict check” routine 260 is used to test the candidate unused IP address that will be temporarily assigned to the appliance 110.
FIG. 13 is a flow diagram of a process of the final_conflict_check routine 260. Variables are initialized and parameters are passed in step 1305. A check to determine if an unused subnet IP address is found is performed in query 1310. If query 1310 is answered “no,” then, in step 1315, the final_conflict_check routine 260 makes a confession is made that the appliance 110 is “unable to get an unused subnet IP address.” Following 1315, control is returned back to the main processing routine 200 (FIG. 2) in step 1360.
If the ARP reply query 1325 is answered “yes”, then the IP conflict procedure, discussed in steps 740 through 755 (FIG. 7) is used to recover from the IP conflict. Step 1355 confesses that, in the event of the IP conflict, the final_conflict_check routine 260 has “failed aggressive ARP check.” Step 1360 then returns control back to the main processing routine 200 (FIG. 2).
The principles of the present invention are capable of operating and automatically assigning IP addresses to each appliance 110, 1420, 1425, even in the face of the network switch 1410 and proxy/NATS 1430 a, 1430 b. In the case of the proxy/NATS 1430 a, 1430 b, the central appliance server 150 uses information determined by a process to overcome network address translation systems, as described in U.S. Provisional Patent Application Ser. No. 60/260,535 filed Oct. 20, 1999 entitled “Automatic Network Address Assignment and Translation Inference” (now expired), U.S. patent application Ser. No. 09/294,837 filed Apr. 19, 1999 entitled “Replica Routing” (now issued as U.S. Pat. No. 6,505,254 and entitled “Methods and Apparatus for Routing Requests in a Network”), and U.S. patent application Ser. No. 08/779,770 filed Jan. 7, 1997 entitled “Replica Routing” (now issued as U.S. Pat. No. 6,052,718); the entire teachings of all are incorporated herein by reference. With regard to the network switch 1410, the appliance 1420 is still able to use the process described in FIGS. 1-13 for the reasons to follow.
Many appliances may be distributed across the WAN 140, forming an appliance network. The appliance network incorporates other unique forms of functionality that may be implemented to work in combination with the teachings of the present invention. The other forms of functionality are described in related applications, including: co-pending application Ser. No. 09/294,837, filed Apr. 19, 1999 entitled “Replica Routing” (now issued as U.S. Pat. No. 6,505,254 and entitled “Methods and Apparatus for Routing Requests in a Network”); co-pending application Ser. No. 08/779,770 filed Jan. 7, 1997 entitled “Replica Routing” (now issued as U.S. Pat. No. 6,052,718); co-pending Provisional Application No. 60/178,063 filed Jan. 24, 2000 entitled “Method and Apparatus for Determining a Network Topology in the Presence of Network Address Translation” (now expired); co-pending Provisional Application No. 60/177,415 filed Jan. 21, 2000 entitled “Method and Apparatus for Minimalist Approach to Implementing Server Selection” (now expired); and co-pending Provisional Application No. 60/177,985 filed Jan. 25, 2000 entitled “Fast-Changing Network Status and Load Monitoring and Feedback” (now expired). The contents of the above applications are incorporated herein by reference in their entirety.
US09/535,279 1999-04-19 2000-03-24 Method and apparatus for automatic network address assignment Expired - Lifetime US7281036B1 (en)
US09/294,836 US6345294B1 (en) 1999-04-19 1999-04-19 Methods and apparatus for remote configuration of an appliance on a network
US16053599P true 1999-10-20 1999-10-20
US17806300P true 2000-01-24 2000-01-24
US09/535,279 US7281036B1 (en) 1999-04-19 2000-03-24 Method and apparatus for automatic network address assignment
US11/879,687 US7899889B2 (en) 1999-04-19 2007-07-18 Method and apparatus for determining a subnet mask based on presence or absence of responses to plural communication packets issued during a search iteration
US11/899,743 US7624164B2 (en) 1999-04-19 2007-09-07 Method and apparatus for retrieving network configuration from a remote network node
US09/294,836 Continuation-In-Part US6345294B1 (en) 1999-04-19 1999-04-19 Methods and apparatus for remote configuration of an appliance on a network
US11/879,687 Division US7899889B2 (en) 1999-04-19 2007-07-18 Method and apparatus for determining a subnet mask based on presence or absence of responses to plural communication packets issued during a search iteration
US11/899,743 Continuation US7624164B2 (en) 1999-04-19 2007-09-07 Method and apparatus for retrieving network configuration from a remote network node
US7281036B1 true US7281036B1 (en) 2007-10-09
ID=38562239
US09/535,279 Expired - Lifetime US7281036B1 (en) 1999-04-19 2000-03-24 Method and apparatus for automatic network address assignment
US11/879,687 Active 2019-06-20 US7899889B2 (en) 1999-04-19 2007-07-18 Method and apparatus for determining a subnet mask based on presence or absence of responses to plural communication packets issued during a search iteration
US11/899,743 Active 2019-05-28 US7624164B2 (en) 1999-04-19 2007-09-07 Method and apparatus for retrieving network configuration from a remote network node
US (3) US7281036B1 (en)
US20080316932A1 (en) * 2007-06-21 2008-12-25 Arcadyan Technology Corporation Identifying method for network device
US20150081853A1 (en) * 2013-09-13 2015-03-19 Netapp Inc. Network address assignment with duplication detection
CN105577853A (en) * 2016-03-09 2016-05-11 上海斐讯数据通信技术有限公司 Method and device for automatically solving IP network segment conflict
FR2936387B1 (en) * 2008-09-25 2016-01-08 Canon Kk A method of managing address spaces at an opening of a communication tunnel, tunnel header, and computer program product corresponding storage means.
US8812694B2 (en) * 2011-12-22 2014-08-19 Blackberry Limited Dialog establishment over a peer-to-peer architecture
US9143929B1 (en) * 2012-12-14 2015-09-22 Western Digital Technologies, Inc. Methods and devices configured for IP address conflict detection and resolution upon assignment of WAN IP address
US9667592B2 (en) * 2014-01-15 2017-05-30 Gilat Satellite Networks Ltd. Efficient utilization of internet protocol addresses
2000-03-24 US US09/535,279 patent/US7281036B1/en not_active Expired - Lifetime
2007-07-18 US US11/879,687 patent/US7899889B2/en active Active
2007-09-07 US US11/899,743 patent/US7624164B2/en active Active
Comer, D.E., "Bootstrap and Autoconfiguration (BOOTP, DHCP)." In Internetworking with TCP/IP, vol. 1: Principles, Protocols and Architecture, (NJ: Prentice Hall), pp. 372, 373 (1995).
US9432329B2 (en) * 2013-09-13 2016-08-30 Netapp, Inc. Network address assignment with duplication detection
US7899889B2 (en) 2011-03-01
US20070266125A1 (en) 2007-11-15
US20070299942A1 (en) 2007-12-27
US7624164B2 (en) 2009-11-24
JP4142960B2 (en) 2008-09-03 System and method for searching a device on a local area network
Free format text: ASSIGNMENT OF ASSIGNORS INTEREST;ASSIGNORS:LU, GANG;O TOOLE, JAMES;KAASHOEK, M. FRANS;REEL/FRAME:011387/0555;SIGNING DATES FROM 20001020 TO 20001212