System and method for reducing broadcast traffic wireless access-point networks

A method, apparatus, and article of manufacture for reducing broadcast traffic in a wireless backbone network. In operation, a wireless access point receives an address resolution protocol (ARP) message from a network device. The wireless access point determines the destination of the ARP message and attempts to identify the Ethernet address associated with the destination network device. If the Ethernet address cannot be determined, the access point sends an ARP request message to the other wireless access points on the network, requesting them to transmit ARP packets to the network device. When the desired network device comes within range of the network, the access points discontinue transmitting ARP packets and a message acknowledging the device's presence is transmitted to the original access point. This method of having access points periodically broadcast ARP packets to network devices reduces ARP broadcasting across the wireless backbone, thereby increasing network throughput.

FIELD OF THE INVENTION

The invention relates generally to network communication systems, such as local area networks (LANs), and more particularly to network communication systems which are accessed by one or more mobile communication units. Even more particularly, the present invention relates to network communication systems which are efficient at handling broadcast network traffic.

DESCRIPTION OF THE RELATED ART

The use of wireless network communication systems that permit mobile units to communicate via an optical or radio link has become widespread. Retail stores and warehouses use such systems to track inventory and replenish stock. Employees enter inventory information using a handheld or portable communication unit which can be carried throughout the store or warehouse. In manufacturing facilities, such systems are useful for tracking parts, completed products and defects. In a medical environment, these systems can reduce the time needed to fill out forms and eliminate inaccuracies by allowing medical personnel to transmit data directly from a mobile communication unit carried by the medical personnel. One of the greatest challenges of wireless networks is that most wireless devices have a limited range in which they can communicate with other devices. Traditionally, this problem has been solved by populating an area with wireless “access points” which are all connected to a wired “backbone network”. A wireless device is free to roam around as long it is in range of at least one of these access points. Two wireless network devices only need to be in range of access points connected to a backbone network in order to communicate. They do not have to be in range of each other and they do not have to be in range of the same access point.

One major limitation of the above network is the access points need to be connected to a wired backbone network. By replacing the wired backbone network with a wireless backbone network, an access point did not need to have any wires attached to it (except perhaps a power cable). In order for a wireless backbone network to be useful however, it had to provide a mechanism for access points not within wireless range of each other to communicate. One approach to solving this problem is for intermediate access points to relay network traffic for access points that are out of range of each other. Unfortunately, two access points that were especially far apart may require several intermediate access points to relay network traffic between them. The goal became to design network communication systems in which relaying could be efficiently performed such that only the minimum number of intermediate access points were used to relay network traffic between two out-of-range access points.

While a wireless backbone network can efficiently handle network traffic between any two nodes, it is less efficient at handling broadcast network traffic (i.e., network traffic that originates at one network device and is transmitted to every other device in the network). Most broadcast network traffic on Internet Protocol (IP) networks is in the form of Address Resolution Protocol (ARP) network traffic.

The ARP protocol is the means by which a network device learns the hardware address of another network device given that device's IP address. Each network device that supports the Internet Protocol has (at least) two addresses: a hardware address and an IP address. The hardware address is not location-dependent and is most often assigned when the network interface hardware is manufactured. The hardware address is usually permanent and associated with a physical device such that when the device is physically moved it keeps the same hardware address. An IP address, by contrast, is usually not bound to a physical device. IP addresses are usually assigned through software. While some devices keep the same IP addresses for extended periods of time, other devices change IP addresses regularly.

For reasons that are beyond the scope of this summary, a given network device can not communicate with a target network device if it does not know the target network device's hardware address. Therefore, the ARP protocol is used frequently on networks that support the IP protocol. Furthermore, ARP network traffic can often comprise the vast majority of broadcast network traffic on networks that support the IP protocol. The performance of networks that are inefficient at handling broadcast network traffic can be substantially increased by reducing ARP network traffic on these networks. Consequently, there is a need in the art for a network that can greatly reduce ARP broadcast traffic.

SUMMARY OF THE INVENTION

The present invention satisfies the above-described need by providing a mechanism for reducing broadcast traffic in a wireless backbone network by reducing ARP broadcast traffic. One method for reducing ARP broadcast traffic is to cache Ethernet/IP address pairs in each access point. In operation, an access point caches ARP responses from responding network devices. By utilizing the cache, the access point can then broadcast an ARP request to the wireless backbone network once for each out-of-range network device. When a wireless network device broadcasts an ARP packet for a particular network device, the access point can also look up the destination IP address in its cache and send a reply without having to broadcast the request throughout the wireless backbone network.

The present invention further satisfies the above described need by providing a mechanism for reducing broadcast traffic in a wireless backbone network that often must re-broadcast ARP traffic throughout the network. In this embodiment, a first network device seeking to discover the hardware address of a second (out of range) network device periodically broadcasts ARP request packets to an in-range access point. This in-range access point shall be designated at Access Point1. Upon receipt of ARP packets, Access Point1determines whether it knows the hardware address of the second network device. If so, Access Point1forwards the ARP packet to the first network device. If Access Point1does not know the hardware address of the second network device, it forwards an ARP request packet to all other access points on the backbone network. These intermediate access points in turn periodically forward the ARP request to all in-range network devices for a predetermined period of time. During this period of time, Access Point1will not forward any more ARP requests it receives for the hardware address of the second network device. If the second network device responds prior to the termination the predetermined time, the response is transmitted via its in-range access point back to Access Point1, which then forwards the response back to the original network device. If there is no response from the desired network device in the predetermined period of time, the intermediate access points terminate their periodic broadcasting of ARP requests. The advantage of this system is it limits the frequency that broadcast packets are sent over the wireless backbone network. Without this system, ARP packets for absent network devices can create unnecessary network traffic.

DETAILED DESCRIPTION

A distributed network in accordance with the present invention, comprises a plurality of access points that communicate with a wireless backbone network via an optical or radio link. The distributed network may comprise any one of a number of types of networks over which client computers and server computers communicate, including local area networks (LANs), wide area networks (WANs), the Internet and any other networks that distribute processing and share data among a plurality of nodes. Moreover, it will be appreciated that the access points provide wireless LAN access to the wireless backbone network for one or more mobile network devices.

Referring now to the drawings, in which like numerals represent like elements throughout the several figures, the present invention will be described.

InFIG. 1, a network communications system in accordance with the invention is generally designated10. A plurality of access points200a-dare coupled to network10via an optical or radio link30. Each access point200a-dhas a cell or service area240(shown inFIG. 4) which is defined as the area surrounding the access point200a-dwithin which it has the ability to transmit and receive relatively error-free data from a mobile network device300(shown inFIG. 4) within the area. WhileFIG. 1only depicts four access points, it is understood by those of skill in the art that the number of access points200is only limited by the size and complexity of network10.

FIG. 2shows a detailed block diagram of access point200. As shown, access point200is comprised of a transceiver202, memory204, central processor206, and RF section208. RF section208is further comprised of an antenna212, RF receiver214and modulator216. The components of access point200communicate together via bus210. Transceiver202is configured according to conventional network adaptor transceiver techniques to allow access point200to communicate over network10. Central processor206is adapted to control access point200and to properly route messages from access point200. Processor206may include any of a variety of microprocessors, including PENTIUM™ based microprocessors operating on Windows/NT, UNIX and/or Windows/CE operating systems. Memory204stores program code executed by processor206to control the other elements of access point200. As shown inFIG. 2, memory204also contains Current Location Table220and ARP Status Table230. Antenna212receives radio and optical signals from, and transmits signals to, network devices within its cell area. Information transmitted from a network device300is received via antenna212and processed by RF receiver214which demodulates the signal and converts the information into a digital signal. Information transmitted by access point200is formatted in processor206, modulated by modulator216and then transmitted to antenna212for eventual transmission to an in-range network device300and access point200. Information from the network device300is typically in the form of packets comprising data, a source identifier (i.e., the particular network device sending the information), and a destination identifier (i.e., the location to which the network device wishes to transmit the data). When the information from the mobile unit comprises an ARP packet, the destination identifier will cause the information to be “broadcast” to all other mobile units in the network.

FIG. 3shows a detailed block diagram of a typical network device300. Like access points200a-d, network devices300are comprised of a memory304, central processor306, RF section308, and bus310. Like RF section208in access point200, RF section308is comprised of a modulator316, receiver314and antenna312. Network devices300additionally comprise a display320, and an operator input terminal318. Memory304, central processor306, RF section308, and bus310perform functions similar to identical components in access point200. Display320serves as a means for displaying information stored within the network device or received over network10via access point200. Display320can be a flat panel liquid crystal display with alphanumeric capabilities, for example, or any other type of display as will be appreciated by those skilled in the art. Operator input terminal318may include a keyboard, microphone, touch sensitive display, etc. to allow an operator to input data to be communicated to the network10such as text, voice, image data, etc.

Referring now toFIG. 4, it is shown that mobile network devices may be located nearby and interface with access points200on network10. Network device300ais in range of access point200aas indicated by the coverage area240aof access point200a. Furthermore, network device300ais also “registered” with access point200a, meaning that communication between network device200aand all out of range network devices (devices that are not in coverage area240a) will be via access point200a. A network device300may be in range of several access points but may only be registered with one access point200at any one instance in time. As the location of the network device300changes, it may register with a second access point200thereby resulting in a termination of the registration with the first access point. Registration may also be terminated if there is no communication between the network device and its corresponding access point for a predetermined period of time.

As mentioned above in connection withFIG. 2, the memory204in each access point200includes a “current location” table220. The current location information for access point200aand access point200bare shown in the following table is represented at time t1which occurs when network devices300aand300bare in the locations shown inFIG. 4. It should be noted that in practice, the Current Location table may identify each network device by its hardware address.

Each access point200includes a Current Location table220that has an entry for each network device300currently registered with the access point200. The information in Current Location table220is constantly updated in a manner well known to one of skill in the art. For that reason, and in the interest of brevity, the process for updating the Current Location table220will not be explained here.

At time t1as shown inFIG. 4, network device300ais registered with access point200a, and network device300bis registered with access point200b. In the Current Location table220of access point200a, network device300ais indicated as registered with access point200a(identified as AP1). Also, network device300bis indicated as registered with access point200b(identified as AP2). This is accomplished by setting an appropriate flag, or the like, in memory204. It will be appreciated that while the information stored in the respective tables is intended to represent IP addresses and Ethernet addresses, for ease of understanding it is shown in the respective tables as alphanumeric shorthand (e.g., AP1, AP2,300a,300b, etc.)

Referring now toFIG. 5, a detailed flow diagram is shown that describes the process of “unicast” communication between a first network device and a second network device when both network devices are associated with network10. Unicast communication is communication in which there is a single source and a single destination. As shown in step510, network device300atransmits a packet addressed to network device300bto access point200a(the access point to which network device300ais currently registered). Next, in step520, processor206in access point200aidentifies the destination of the packet as network device300b. Processor206, in step530then searches memory204for the location of the desired network device. If processor206finds the desired network device (step540), it reads the information (step550) from Current Location table220to determine the access point on network10that the destination network device is registered with. Once the second access point is identified, the packet is forwarded to the second access point (step560), which in turn forwards the packet to the destination network device (step570).

If the desired network device is not found (step540), processor206determines whether the packet is an ARP packet (step580). If the packet is not an ARP packet, processing terminates. If the packet is an ARP packet, the present invention processes the ARP packet (step590) and processing terminates.

The ARP protocol is a standard, well-defined protocol that permits a network device to discover the hardware address of another network device, given the IP address of the other network device. Referring toFIG. 6, the basic format of an ARP packet is shown. The ARP packet is generally designated600and includes a “type” field610. As shown inFIG. 6, an ARP packet may either be “Request” or “Response” packet. The packet600may also include fields for destination and source hardware addresses (620and630, respectively) and destination and source IP addresses (640and650, respectively). It should be noted that these addresses are separate and in addition to the source and destination addresses that may comprise a portion of the header of every packet transmitted by a network device.

Referring toFIG. 7, there is shown a flow diagram that briefly describes the ARP protocol. A more detailed description of the protocol may be obtained from literature describing the technical workings of the Internet (i.e., Internetworking With TCP/IP, by Douglas Comer, published by Prentice Hall, 1988). A network device generates an ARP Request packet containing the IP address of the network device whose hardware address it wishes to discover (step700) and broadcasts it to all other network devices (step720). Upon receiving the ARP packet (step730) each network device compares the destination IP address640with its own IP address (step740). Network devices whose IP addresses do not match the destination IP address640ignore the packet and processing terminates. If a network device's IP address matches the destination IP address640in the ARP packet, that network device creates an ARP Response packet that contains its hardware and IP addresses (step750) and sends it to the original network device (step760). The original network device receives this packet and discovers the hardware address of the second network device (step770).

When access point200receives an ARP Request packet, the destination of the packet will not refer to any particular network device but instead will be “broadcast”. In order for the ARP protocol to function correctly, access point200must forward the ARP Request packet to all other access points in network10, so that the packet may be relayed to all possible network devices.

In the prior art, when a network device created an ARP Request packet that did not illicit an ARP Response packet, the network device repeatedly retransmitted the ARP Request packet a predetermined number of times or until a response was received. This can cause an unnecessarily large amount of traffic across network10.

In the present invention, three procedures referred to as “ARP caching,” “responseless ARP reduction,” and “ARP response waiting,” allow access points200to reduce the unnecessary broadcasting of ARP traffic over a wireless backbone network. For the purpose of explanation these procedures will be described separately, although it is understood they are actually incorporated together in the invention.

“Caching” is a method by which an access point200utilizes an “Address Table” to maintain a record of IP addresses and hardware addresses associated with each network device300. By way of example, suppose network device300a, as shown inFIG. 8, wishes to discover the hardware address of network device300b, given only its IP address. Suppose that network devices300a,300b, and300c, as shown inFIG. 8, have IP addresses IP1, IP2, and IP3, respectively, and hardware addresses HW1, HW2, and HW3, respectively. A detailed flow diagram shown inFIG. 9describes how ARP traffic is processed when caching is employed.

As shown inFIG. 9, network device300acreates an ARP Request packet containing the target IP address (IP2), as well as its own IP address (IP1) and hardware address HW1(step910). This packet is then broadcast throughout its local coverage area240a(step911). For purposes of this example, it is assumed that Access Point200a's Address Table is empty. The ARP packet is received by network device300cand access point200a(which represent all devices in coverage area240a) (step912). Upon receiving the ARP packet, access point200aadds the source IP address/hardware address pair to its Address Table (step913). Following this addition, the Address Table in access point200awill read:

Access point200athen checks its Address Table for the target IP address (IP2). (step914) Since the IP Address associated with the network device is not in its Address Table, access point200abroadcasts the ARP Request packet to all other access points200(step930). Upon receipt of the ARP Request packet, these access points200add IP address (IP1) and hardware address HW1(read from the packet) to their respective Address Tables in much the same manner access point200apreviously did (step931). They also broadcast the ARP Request packet to their local coverage areas240(step932). If the IP address associated with the network device is in access point200a's Address Table (step915), processing flows to step920where access point200areads the target hardware address from its Address Table. Next, access point200alooks up the target hardware address in its Current Location Table (step921). If the target hardware address is in the Current Location Table (step922), processing flows to step923. If it is not, processing terminates. In step923, access point200adetermines (from the Current Location Table) if the target network device is registered to it. If it is, processing flows to step925. If it is not, processing terminates. In step925, access point200acreates an ARP response packet that contains the destination hardware address, and in step926, access point200asends the ARP response packet to the source network device.

When network device300breceives the ARP Request packet from access point200b(step933), it compares the target IP address in the packet with its own IP address, (step934). If the target IP address is different, processing terminates. If it is the same, it creates an ARP Response packet containing its hardware address (11W2), and its IP address (IP2) (step935). It then transmits the ARP Response packet to network device200b(step936). In step937, access point200bthen determines whether IP address/hardware address pair is already in its Address Table. If it is, processing flows to step938. If the IP address/hardware address pair is not in the Address Table, access point200badds the address pair to its Address Table. In step938, access point200bidentifies the destination network device from the packet, and then searches its Current Location Table for the destination network device. If the destination network device is found, processing flows to step941. If it is not found, processing terminates. In step941, access point200bidentifies the access point to which the destination network device is registered, and in step942, access point200bforwards the packet to the destination access point. Processing then flows to step943, where the destination access point receives the packet and then determines whether to add the IP address/hardware address of the target network device to its Address Table. If the address pair is not present in the Address Table, the access point adds the address pair to its Address Table. If the address pair is already present in the Address Table, processing flows to step944where the destination access point forwards the packet to the source network device. Next, processing flows to step945where the source network device processes the packet and discovers the hardware address that matches the IP address in the ARP Request packet that was previously sent. Following this processing, the Address Table of access point200awill read:

Now, suppose that network device300cinFIG. 8wishes to discover the hardware address of network device300b. It will create an ARP Request packet containing the target IP address (IP2) in addition to its own IP address (IP3) and hardware address (HW3). This packet will be broadcast and received by access point200a, which will add IP address (IP3) and hardware address (HW3) to its Address table. Access point200awill then look up the target IP address (IP2) in its Address Table, and identify the hardware address (HW2) associated with it. Access point200awill then look up hardware address (HW2) in its Current Location table, which reads:

By reading its Current Location Table, access point200awill learn that the target network device (HW2) is registered with another access point. It will then create an ARP Reply packet containing the IP address (IP2) and hardware address (HW2) of the target network device and send the packet to network device300b. Therefore, by storing, or caching, hardware address (HW2) in its Address Table, access point200ahas eliminated the need to broadcast the ARP Request packet across backbone network10. At this point in time, the Address Table in access point200areads as follows:

As a final example, suppose network device300ainFIG. 8wishes to discover the hardware address of network device300c. In operation, both access point200aand network device300creceive an ARP Request packet from network device300a. Access point200alooks up target IP address (IP3) in its Address Table to identify the hardware address (HW3) of network device300c. It then looks up the target hardware address (HW3) in its current location table to determine that network device300cis registered with it (as opposed to with another access point). Upon learning this, access point200awill ignore the ARP Request packet. Network device300cwill send an ARP Response directly to Network device300a, as both network devices are in the same coverage area. As in the previous example, by using the Address Table, access point200ahas eliminated the need to broadcast the ARP Request across backbone network10.

Sometimes a network device will broadcast an ARP request packet for a target network device that can not respond (for example, if it is powered down or is out of range of an access point.) When a network device transmits an ARP request packet and does not receive an ARP response packet, it will typically retransmit the ARP request packet until it receives a response. If the retransmissions occur frequently enough, this can cause many unnecessary ARP packets to be broadcast across the backbone network. “Responseless ARP Reduction” is a process that limits that number of ARP packets that are broadcast across the backbone network when the target device of the ARP is not responding.

Suppose that network device300atransmits an ARP request packet to a network device that is not in range of any access point200. In that case, network device300awill never receive an ARP response packet and, after some delay, will retransmit the ARP request packet. Each time access point200areceives the ARP request packet from network device300a, it will look up the target IP address in its Address Table. Since the IIP Address of the out-of-range network device is not in access point200a's Address Table, it will broadcast the packet across the backbone network to other access points. If network device300agenerates ARP request packets for the out-of-range network device at a high enough rate, the broadcasting will overwhelm the backbone network with ARP broadcast network traffic. One solution to this problem is to limit the rate that access point200atransmits ARP packets across the backbone network by having the other access points periodically rebroadcast ARP request packets for the out-of-range network device in their local coverage area. More specifically, when access point200afirst receives the ARP request packet from network device300a, it broadcasts the request across the backbone network to the other access points200. Each access point200that receives the ARP request packet then sends a packet back to the originating access point200asignifying that it will periodically broadcast the ARP request packet to its local coverage area for a specified amount of time (e.g., 5 minutes) unless it receives an ARP response packet. During this time, if network device300aretransmits the ARP request packet, access point200awill not re-broadcast it across the backbone network. Suppose the out-of-range network device (e.g., Network Device300d-IP Address IP4, Hardware Address HW4) enters access point200b's coverage area 3 minutes after network device300atransmitted its first ARP request packet. Access point200band network device300ahave been periodically broadcasting ARP request packets for network device300d, only the first one being transmitted by access point200aover the backbone network. When network device300denters access point200b's coverage area, it will receive an ARP request packet from access point200a. It will then send an ARP response packet via access points200band200ato network device300aas previously described in steps935through945(FIG. 9). As a result, while network device300aperiodically broadcasts ARP request packets for 3 minutes, only one packet is transmitted across the backbone network. This solution exploits the assumption that broadcast network traffic on the backbone network is relatively expensive in comparison to broadcast network traffic in the local coverage areas.

One way to implement this capability is for each Access Point200to keep track of three tables, which shall be designated as the Local ARP Table, the Remote ARP Table, and Network Device ARP Table. The Local ARP Table has an entry for each target network device300that the access point200is broadcasting ARP packets for in its local coverage area. Associated with each table entry is a list of the other Access Points200that have sent ARP requests for the target network device300, as well as a “timeout” value, after which ARP packets will not longer be broadcast to the local coverage area for the target network device. The Remote ARP Table has an entry for each target network device300being ARPed for by other access points. For each target network device300being ARPed for, the Remote Table keeps track of which access points are broadcasting ARP packets to their local coverage area for the target network device300, and how long each one will do so (the same “timeout” value as in the Local Table). The Network Device Table keeps track of which local network devices have transmitted requests for each target network device being ARPed for by other access points.

The use of these tables is illustrated below. Referring toFIG. 8, suppose that network devices300aand300care in the local coverage area of access point200a, and that network device300bis in the local coverage area of access point200b. Further, suppose that network devices300a,300b, and300care all periodically broadcasting ARP request for the network device300d, which is out of range of all access points. Referring now toFIG. 10, it is shown that when access point200areceives the first ARP request from network device300a(step1012), it will add network device300a's IP/hardware address pair to its address table (step1013). After this, access point200a's address table reads as follows:

Access point200awill then look up the target IP address (IP4), in its Address Table (step1014). If the target IP address is in its Address Table (1015), processing flows to step1020, where access point200areads the target IP address from its Address Table. Processing then flows to step1021where access point200adetermines whether the target hardware address is in its Current Location Table. If it is (step1022), processing flows to step1023. If it is not, processing terminates. In step1023, access point200auses the Current Location Table to determine whether the target network device is registered to it. If the target network device is registered to the access point (step1024), processing flows to step1025. If the target network device is not registered to the access point, processing terminates. In step1025, access point200acreates an ARP response packet that contains the destination hardware address. Processing then flows to step1026where access point200atransmits the ARP response packet to the destination network device. Since IP4is not in its address table (step1015), access point200awill add the following entry in its Network Device Table (step1030):

The purpose of the Network Device Table is to keep track of the devices that have ARPed for another device. When access point200aeventually receives a reply from another access point, it will use the Network Device Table to determine which network devices to forward the reply to.

After adding the entry to its Network Device Table, processing flows to step1031, where access point200alooks up the target IP address (IP4) in its Remote ARP Table (step1031). If the target IP address is in the Remote ARP Table, processing flows to step1033, where access point200auses the Remote ARP Table to determine which access points are currently ARPing for the target network device. Next, access point200asends an ARP Request packet to all access points that are not currently ARPing for the network device. Since at this point in time access point200a's Remote ARP Table is empty, processing flows to step1040where the access point then forwards the ARP request to all other access points.

Referring now toFIG. 11, the process for maintaining the Local ARP Table will now be explained. When another access point receives an ARP request from access point200a(step1131), it adds the IP/Hardware address to its address table (step1132). The other access points then determine whether the target IP address (IP4) is in its address table (step1133). If the target IP address is in the Address Table (step1134), processing flows to step1135where access point200acreates an ARP reply packet containing the hardware address of the target network device. Processing then flows to step1136where access point200aforwards the ARP response packet to the originating access point. If the target IP address is not the Address Table, processing flows to step1150where access point200adetermines whether the target network device is in its local ARP Table. If the target network device is in the Local ARP Table, processing flows to step1154. If it is not, processing flows to step1152where an new entry is created in the Local ARP Table that associates the source access point the target network device. Processing then flows to step1153where Access Point200adetermines from its Current Location table if the target network device is registered with the access point. If this is indeed the case, processing flows to step1154where the access point creates an ARP response packet containing the destination hardware address of the target network device. Otherwise, processing flows to step1155where the access point transmits ARP request packets to its local coverage area for the network device with IP address (IP4) and registers the target network device before proceeding to step1154. For example, it is assumed that none of the access points have the target IP address (IP4), in either their address tables or their local ARP tables. Therefore, each other access point adds the following entry to its local ARP table:

For illustration purposes, the timeout value in the local ARP table has been specified as 5 minutes. However, any value may be used within the scope of the present invention. Each other access point periodically sends ARP request packets to its local coverage area for the network device with IP address (IP4) for the next 5 minutes (step1155). Also each other access point sends a “periodic notify” packet to access point200a, specifying the target IP and the timeout value remaining (step1154). Access point200areceives these “periodic notify” packets, and updates its Remote ARP table accordingly. In the present example, ARP Table for access point200awill read as follows:

Now, suppose that network device300c, which is located in the coverage area of access point200a, transmits an ARP request packet for the network device with IP address IP4. The ARP request packet is received by access point200a. As previously mentioned, access point200awill add an entry to its address table and network device table (Steps1012-1030). These tables will then read as follows:

Access point200athen looks up the target IP address (IP4) in its Remote ARP table (step1031). According to its Remote ARP table, all other access points (access point200band access point200c) are currently ARPing for the target network device. Therefore, access point200awill not broadcast the ARP request across the backbone network. (steps1033and1034). Even though network devices300aand300cmay periodically broadcast ARP request packets for the target network device, only the first request packet was broadcast across the backbone network. When network device300b, which is in access point200b's coverage area, transmits an ARP request packet, access point200bwill perform the same steps (1012-1040) that access point200aperformed when network device300atransmitted its first ARP request. At this point in time, each access point is periodically broadcasting ARP request packets to its local coverage area, however ARP request packets are not being broadcast across the backbone network.

When the target network device appears in a local coverage area, processing depicted inFIG. 12will be performed. Suppose that the target network device appears in the local coverage area of access point200c. The target network device will receive the ARP request packet from access point200c, and will respond with an ARP reply packet. Access point200cwill in turn, receive the ARP reply packet (step1260). Next, access point200creads the IP address and hardware address of the source network device and adds them to its address table (step1261). Access point200cthen looks up the IP address of the source device in the Local ARP Table (step1262). At this point in time, the access point's local ARP table reads as follows:

The local table includes two entries for IP4because access point200aand access point200bsent ARP request packets to access point200c(due to the ARP request packets respectively sent by network devices300aand300b). If the source IP address is in the Local ARP Table, processing flows to step1264. If the source IP address is not in the local ARP table, processing terminates. In step1264, the access point determines from its Local ARP Table, which access points have sent requests for the source of an ARP reply and removes them from the Local ARP Table (Step1265). Access point200cthen forwards an ARP reply packet to all access points that sent ARP requests for the source of an ARP reply.

Referring now toFIG. 13, there is shown a flowchart depicting the process performed when access point200areceives the ARP reply packet from access point200c. As shown inFIG. 13, access point200afirst reads the IP address and hardware address of the source network device from the ARP packet and adds them to its Address Table (step1361). Access point200athen looks up the IP address of the source device in the Network Device Table (step1362). As previously noted, access point200a's network device table reads as follows:

Access point200athen determines if the source IP address is in the Network Device Table (step1363). If it is, processing flows to step1364. If it is not, processing terminates. In step1364, access point200adetermines from the Network Device Table, which access points have sent ARP requests. Next, access point200aremoves the source IP address from the Network Device Table in step1365, and in step1366, access point200aforwards an ARP reply packet to all network devices in its local coverage area that sent ARP requests for the source address of the ARP reply. Since the source IP address (IP4) (which is the original source of the ARP reply packet, and the original target network device) is in the network device table, access point200aforwards the ARP reply packets to network devices300aand300c(step1366), and removes the entries from the table (step1365). Likewise, access point200bforwards the ARP request packet to network device300b. Therefore, network devices300a,300band300chave all received the ARP reply packets, and the number of ARP request packets broadcast across the backbone network is greatly reduced.

From the foregoing description, it will be appreciated that the present invention provides an efficient system and method for minimizing traffic on a wireless backbone network. The present invention has been described in relation to particular embodiments which are intended in all respects to be illustrative rather than restrictive. Those skilled in the art will appreciate that many different combinations of hardware will be suitable for practicing the present invention. Many commercially available substitutes, each having somewhat different cost and performance characteristics, exist for each of the components described above.

Although aspects of the present invention are described as being stored in memory, one skilled in the art will appreciate that these aspects can also be stored on or read from other types of computer-readable media, such as secondary storage devices, like hard disks, floppy disks, or CD-ROMs; a carrier wave from the Internet; or other forms of RAM or ROM. Similarly, the method of the present invention may conveniently be implemented in program modules that are based upon the flow charts inFIGS. 5,7, and9-13. No particular programming language has been indicated for carrying out the various procedures described above because it is considered that the operations, steps and procedures described above and illustrated in the accompanying drawings are sufficiently disclosed to permit one of ordinary skill in the art to practice the instant invention. Moreover, there are many computers and operating systems which may be used in practicing the instant invention and therefore no detailed computer program could be provided which would be applicable to these many different systems. Each user of a particular computer will be aware of the language and tools which are most useful for that user's needs and purposes.

Alternative embodiments will become apparent to those skilled in the art to which the present invention pertains without departing from its spirit and scope. Accordingly, the scope of the present invention is defined by the appended claims rather than the foregoing description.