ROBINSON BENJAMIN CRAWFORD (US)
| US6483833B1 | 2002-11-19 | |||
| US6249820B1 | 2001-06-19 | |||
| US6393484B1 | 2002-05-21 | |||
| US6556574B1 | 2003-04-29 |
| 1. | A method for nondisruptive physical address resolution, the method comprising: (a) maintaining a cache of network to physical layer address bindings; (b) for each binding, maintaining a binding refresh timer and an age out timer, the binding refresh timer being less than the ageout timer; (c) in response to expiration of the binding refresh timer, sending a dataindependent binding refresh request over a network; and (d) in response to receiving a reply to the binding refresh request, updating the binding. |
| 2. | The method of claim 1 wherein maintaining a cache of network to physical layer address bindings includes maintaining an address resolution protocol (ARP) cache containing Internet protocol (IP) to media access control (MAC) address bindings. |
| 3. | The method of claim 1 wherein maintaining a binding refresh timer includes setting the binding refresh timer to a fixed value independent of whether data is being sent or received to a physical address of the binding. |
| 4. | The method of claim 1 wherein sending a dataindependent binding refresh request includes unicasting an address resolution protocol (ARP) request to a physical address of the binding. |
| 5. | The method of claim 1 comprising receiving an address resolution protocol (ARP) reply including a physical address corresponding to a network address in the binding refresh request. |
| 6. | The method of claim 1 wherein updating the binding includes indicating that the binding reply has been received. |
| 7. | The method of claim 6 comprising receiving data to be transmitted using the binding, and, in response, indicating that the binding is in use. |
| 8. | The method of claim 7 comprising detecting expiration of the ageout timer for the binding, and, in response to the expiration, the indication that the reply has been received, and the indication that the binding is in use, keeping the binding in the cache and resetting the binding refresh and ageout timers for the binding. |
| 9. | The method of claim 1 comprising detecting expiration of the ageout timer for the binding and the binding reply having not been received or the binding being unused, and, in response, deleting the binding from the cache. |
| 10. | The method of claim 1 comprising resending the binding request a predetermined number of times prior to expiration of the ageout timer. |
| 11. | The method of claim 10 comprising, in response to failing to receive a binding reply to any of the outstanding binding requests, deleting the binding from the cache. |
| 12. | A system for nondisruptive physical layer address resolution, the system comprising: (a) a cache for storing network to physical layer address bindings; and (b) a cache manager/binding request generator for maintaining, for each binding in the cache, an ageout timer and a binding refresh timer, the binding refresh timer being less than the ageout timer, and, upon expiration of the binding refresh timer, for sending a dataindependent binding refresh request to a node in the network corresponding to a physical address in the binding. |
| 13. | The system of claim 12 wherein the cache comprises an address resolution protocol (ARP) cache for storing Interne protocol (IP) to media access control (MAC) address bindings. |
| 14. | The system of claim 12 wherein the cache manager/binding request generator is adapted to maintain, for each binding, a first indicator for indicating whether the binding is in use by an application and a second indicator for indicating whether a reply has been received to an outstanding binding request. |
| 15. | The system of claim 14 wherein the cache manager/binding request generator is adapted to set the first indicator to a first value in response to receiving a reply to an outstanding binding request. |
| 16. | The system of claim 15 wherein the cache manager/binding request generator is adapted to set the second indicator to the first value in response to receiving data to be sent to a physical address in the binding. |
| 17. | The system of claim 16, wherein, in response to expiration of the age out timer for a binding and the first and second indicators having the first value, the cache manager/binding request generator is adapted to reset the binding request and ageout timers for the binding without deleting the binding from the cache. |
| 18. | The system of claim 16 wherein, in response to expiration of the ageout timer for a binding and the first indicator having a second value indicating that the binding is not in use or the second indicator having the second value indicating that the binding reply has not been received, the cache manager/binding request generator is adapted to delete the binding from the cache. |
| 19. | The system of claim 16 wherein the cache manager/binding request generator is adapted to resend the binding request a predetermined number of times prior to expiration of the ageout timer. |
| 20. | The system of claim 19 wherein the cache manager/binding request generator is adapted to maintain the binding in the cache in response to receiving a reply to any of the binding refresh requests for the binding and the binding being in use at the expiration of the ageout timer. |
| 21. | A computer program product comprising computer executable instructions embodied in a computer readable medium for performing steps comprising: (a) maintaining a cache of network to physical layer address bindings; (b) for each binding, maintaining a binding refresh timer and an age out timer, the binding refresh timer being less than the ageout timer; and (c) in response to expiration of the binding refresh request timer for an entry, sending a dataindependent binding refresh over a network ; (d) in response to receiving a reply to the binding refresh request, updating the binding. |
| 22. | The computer program product of claim 20 wherein maintaining a cache of network to physical layer address bindings includes maintaining an address resolution protocol (ARP) cache containing Internet protocol (IP) to media access control (MAC) address bindings. |
| 23. | The computer program product of claim 20 wherein maintaining a binding refresh timer includes setting the binding refresh timer to a fixed value independent of whether data is being sent or received to a physical address of the binding. |
| 24. | The computer program product of claim 20 wherein sending a data independent binding refresh request includes unicasting an address resolution protocol (ARP) request to a physical address of the binding. |
| 25. | The computer program product of claim 20 comprising receiving an address resolution protocol (ARP) reply including a physical address corresponding to a network address in the binding request. |
| 26. | The computer program product of claim 20 wherein updating the binding includes indicating that the reply has been received. |
| 27. | The computer program product of claim 20 comprising receiving data to be sent to a physical address in the reply and, in response, indicating that the binding is in use. |
| 28. | The computer program product of claim 26 comprising detecting expiration of the ageout timer for the binding, and, in response to the expiration, the indication that the reply has been received, and the indication that the binding is in use, keeping the binding in the cache and resetting the binding refresh and ageout timers for the entry. |
| 29. | The computer program product of claim 20 comprising detecting expiration of the ageout timer for the binding, and, in response to the expiration and the binding being unused or failing to receive a reply for the binding request, deleting the binding from the cache. |
| 30. | The computer program product of claim 20 comprising resending the binding request a predetermined number of times prior to expiration of the ageout timer. |
| 31. | The computer program product of claim 30 comprising, in response to failing to receive a binding reply to any of the outstanding binding requests, deleting the binding from the cache. |
Related Art In order for machines to communicate with each other over a network, it is necessary for each machine to know the physical address of other machines with which its user desires to communicate. In IP networks, the address resolution protocol (ARP) is used to map IP addresses to physical addresses.
According to the address resolution protocol, when machine A desires to communicate with machine B, machine A determines whether it knows the physical address of machine B by searching an ARP cache maintained by machine A. If the ARP cache maintained by machine A contains a network to physical address mapping for machine B, machine A encapsulates the network level packet in a physical layer frame addressed to the physical address of machine B and sends the frame to machine B.
If machine A does not have an entry in its ARP cache for machine B, machine A broadcasts an ARP request to all nodes on the same physical network as machine A. The ARP request includes the IP address of machine B. Each node on the network receives the ARP request. Machine B recognizes the request as being addressed to its IP address, and ARP software on machine B responds to the request with the physical address for machine B.
The response is referred to as an ARP reply. Machine A receives the ARP reply, updates its ARP cache to include the physical address of machine B, encapsulates the IP packet in a physical layer frame addressed to the physical address of machine B, and sends the frame to machine B.
The process of searching the ARP cache, broadcasting a request if no mapping is found, receiving a reply, and adding the mapping in the reply to the
cache is repeated for each data packet transmitted over the network. Each ARP reply adds or updates an entry in the ARP cache. Thus, the ARP cache can increase in size over time. In order to keep the ARP cache to a reasonable size, the ARP protocol specification includes a timeout period for ARP cache entries. In some exemplary ARP implementations, the ARP timeout period is set to 20 minutes. When the timeout period expires, the ARP entry is deleted without regard to whether the entry is being used by an application.
One problem with conventional address resolution protocol implementations is that when an ARP cache entry times out, if an application desires to send data to a remote application located at the endpoint corresponding to the aged out entry, IP packets may be overwritten. More particularly, if one IP packet arrives at the physical layer and the ARP entry corresponding the IP address for the packet has aged out, ARP software must resend an ARP request and receive an ARP reply with a mapping for the aged out entry before the packet can be sent. If the application generates multiple packets before the ARP reply is received, the packets will be overwritten in the sending machine because there is no mechanism in the TCP/IP protocol for buffering IP packets awaiting transmission. The loss of IP packets can result in retransmission of TCP segments, which significantly decreases throughput.
Figure 1 illustrates that age-out problem associated with conventional ARP implementations. As long as an ARP entry has not aged out, throughput exists at a maximum level Tmax. Once the entry ages out, throughput decreases to zero while the ARP software rebroadcasts the ARP request and waits for the reply. Once the reply is received, throughput may increase to the maximum value until the next age-out time. Such decreased throughput is unsuitable for connections that exist over long periods of time, such as connections used in telephony applications.
One conventional solution to this age-out problem is to increase the age- out time. Increasing the age-out time to a value greater than the 20 minute time period suggested by the ARP standard reduces the likelihood that an entry will age out during a communications session between two endpoints.
However, increasing the age-out time increases the size of the ARP cache.
Having a large ARP cache is inefficient because the time for searching the ARP cache is increased for each packet that is sent, and the memory storage requirements for the ARP cache are increased.
Another solution to the age-out problem with conventional address resolution protocol implementations is described at http://www. freebsd. orq/cqi/query-pr. cia ? pr=kern/25517 (hereinafter the"Free BSD Solution"). The Free BSD Solution specifies that a data-driven pre-age- out ARP request may be sent in order to increase the age-out time when entries are in use by an application. The additional ARP requests are data- driven, meaning that the additional ARP requests are only sent if data is waiting to be sent to the endpoint corresponding to an ARP cache entry. Such data- driven approaches can still result in decreased throughput because data can arrive at the physical layer just before the ARP age-out time, a pre-age-out ARP request may then be sent just before the age-out time, and the ARP cache entry may expire before the ARP reply is received. Packets arriving at the physical layer before the reply is received will be overwritten, and throughput of a communications session will decrease at each age-out time.
This decrease in throughput at each age-out time can be disruptive to long- term communications sessions, such as IP telephony sessions.
Thus, in light of the problems associated with conventional address resolution protocol implementations, there exists a need for improved methods and systems for resolving physical addresses that avoid the difficulties associated with conventional ARP implementations.
Disclosure of the Invention The present invention includes methods and systems for physical address resolution that avoid the difficulties associated with conventional address resolution protocol implementations. According to one aspect of the invention, a data independent re-ARP period is set to be less than the age-out period for an ARP cache entry. When the re-ARP period expires, a"cache entry used"Boolean variable and an"ARP reply received"Boolean variable for the entry are set to FALSE. A data independent uni-cast ARP request is then sent to the endpoint corresponding to the ARP cache entry. An ARP reply is
received. The"ARP reply received"Boolean variable is then set to TRUE.
When data arrives from an application desiring to use the newly updated entry, the"cache entry used"Boolean variable is set to TRUE. When the age-out timer expires, the entry is not aged out because both variables are set to TRUE. The re-ARP and age-out timers are then reset. Thus, because the present invention sends data independent re-ARP requests before the end of the age-out period, the throughput problems associated with conventional address resolution protocol implementations are avoided. As a result, address resolution protocol implementations according to the present invention are non- disruptive in that they do not adversely affect the throughput of a communications session. Such non-disruptive address resolution is advantageous for long-term communications sessions, such as IP telephony sessions.
Accordingly, it is an object of the invention to provide methods and systems for non-disruptive physical address resolution.
It is another object of the present invention to provide methods and systems for sending data independent re-ARP requests prior to the end of the ARP age-out time.
Some of the objects of the invention having been stated hereinabove, other objects will become evident as the description proceeds when taken in connection with the accompanying drawings as best described herein below.
Brief Description of the Drawings Preferred embodiments of the present invention will now be explained with reference to the accompanying drawings of which: Figure 1 is a graph of throughput verses time for conventional address resolution protocol implementations; Figure 2 is a block diagram of a plurality of endpoints connected to the same local area network; Figure 3 is a block diagram of an endpoint including an ARP cache manager/request generator according to an embodiment of the present invention;
Figure 4 is a flow chart illustrating exemplary steps that may be performed by the ARP cache manager/request generator in maintaining ARP cache entries according to an embodiment of the present invention; and Figure 5 is a graph of throughput verses time using non-disruptive address resolution according to an embodiment of the present invention.
Detailed Description of the Invention As stated above, the present invention includes methods and systems for non-disruptive address resolution. Figure 2 is a block diagram of network endpoints connected via a local area network in which the methods and systems of the present invention may be implemented. Referring to Figure 2, endpoints 100,102, 104, and 106 are connected to each other via local area network 108. Endpoints 100,102, 104, and 106 may be personal computers, workstations, or any other devices capable of communicating with other devices over a local area network. Local area network 108 may be any suitable type of local area network, such as an Ethernet. Each endpoint includes an IP address and a physical address, which may be a media access control (MAC) address if local area network 108 is an Ethernet. In the illustrated example, endpoint 100 includes an IP address IP1 and a MAC address MACi, endpoint 102 includes an IP address IP2 and MAC address MAC2, endpoint 104 includes an IP address IP3 and a MAC address MAC3, and endpoint 106 includes an IP4 and a MAC address MAC4.
Each endpoint 100,102, 104, and 106 includes a network interface 110, TCP/IP software 112, and one or more applications 114. Network interface 110 may include hardware and/or software for implementing non-disruptive address resolution according to the present invention. This functionality will be described in more detail below. TCP/IP software 112 implements data transport and network functions in accordance with the TCP and IP protocols.
Application 114 may be any suitable application for communicating over network 108. In one example, application 114 may be a telephony application.
In an alternative embodiment of the invention, software 112 may implement SCTP/IP.
Figure 3 is a block diagram of an endpoint 100 including an ARP cache manager/request generator for performing non-disruptive address resolution according to an embodiment of the present invention. Referring to Figure 3, network interface 110 includes a MAC layer 300 for sending and receiving physical layer frames over network 108. MAC layer 300 includes an ARP cache manager/request generator 302 for generating data independent ARP requests and maintaining entries in ARP cache 304. ARP cache 304 stores network to physical layer address mappings.
Figure 4 is a flow chart illustrating exemplary steps that may be used by ARP cache manager/request generator 302 in generating data independent ARP requests and maintaining entries in ARP cache 304. Referring to Figure 4, in step 400, ARP cache manager/request generator 302 sets a re-ARP period in the ARP cache to be less than the age-out period for each cache entry. In one exemplary implementation, the age-out time for an entry may be twenty minutes and re-ARP period may be set to 18 minutes. However, the present invention is not limited to either a 20-minute age-out period or an 18 minute re-ARP period. The age-out period is preferably selected to maintain a desired ARP cache size, which depends on the memory and processing capacity of network interface 110 and the number of entities with which the endpoint is communicating. The re-ARP period is preferably selected to allow sufficient time for an ARP reply to arrive before the end of the age-out period.
The time for an ARP reply to arrive may depend on the distance between machines in the network and the congestion level in the network. If the network has a high congestion level, the difference between the re-ARP period and the age-out period may be set to a sufficient value to allow a predetermined number of retransmissions of the ARP request in case the original request is lost.
In step 402, the re-ARP period expires. In step 404, APR cache manager/request generator 302 sets two Boolean variables, "cache entry used" and"APR reply received"to FALSE. The Boolean variable"cache entry used" indicates whether or not the ARP cache entry is in use by an application. The
Boolean variable"ARP reply received"indicates whether or not a reply has been received in response to an outstanding ARP request.
In step 406, ARP cache manager/request generator 302 generates a data independent, uni-cast ARP request. The ARP request is data independent in that it is sent independently of whether the ARP cache entry is in use by an application. The ARP request is uni-cast in that it is addressed to the MAC address in the ARP cache entry, rather than being the broadcast address of all of the endpoints on the network, as in conventional ARP implementations. In step 408, ARP cache manager/request generator 302 receives an ARP reply and updates the cache entry. In step 410, ARP cache manager/request generator 302 sets the"ARP reply received"Boolean variable to TRUE, indicating that the ARP reply has been received.
In step 412, MAC layer 300 receives an I P packet from the network layer and sends the packet to the target host using the MAC address in the ARP cache entry updated in step 408. In step 414, ARP cache manager/request generator 302 sets the"cache entry used"Boolean variable to TRUE, indicating that the entry is now in use. In step 416, the age-out timer expires. In step 418, the entry is not aged out or deleted because both Boolean variables are set to TRUE, indicating that the ARP reply has been received and the entry is in use. In step 420, ARP cache manager/request generator 302 resets the re- ARP and age-out timers.
If the age-out timer expires, and an ARP reply has not been received or the entry is not in use, ARP cache manager/request generator 302 deletes the entry from the ARP cache to maintain a desired ARP cache size. The next IP packet that arrives from the network layer addressed to the IP address corresponding to the deleted entry will result in a broadcast ARP request, as per the normal ARP protocol.
Thus, using the steps illustrated in Figure 4, the present invention avoids the throughput difficulties associated with conventional address resolution protocol implementations. For example, because data independent ARP requests are sent prior to the age-out period, the chance that a connection will be disrupted due to an entry aging out is reduced.
Figure 5 illustrates the throughput advantages of data independent re- ARPing according to the present invention. Referring to Figure 5, an ARP binding request is sent prior to the ARP age-out period. The binding response may arrive before the age-out period. When the age-out period expires, if the entry is in use, the entry is not deleted from the cache. As a result, throughput is maintained at the level Tmax. This re-ARPing occurs periodically so that maximum throughput is maintained throughout the life of a connection.
Although the present invention has been described primarily in terms of the ARP protocol, the present invention is not limited to the ARP protocol. The method and systems described herein are applicable to maintain network to physical layer address mappings in any dynamic address resolution protocol where cache entries have an age-out period.
It will be understood that various details of the invention may be changed without departing from the scope of the invention. Furthermore, the foregoing description is for the purpose of illustration only, and not for the purpose of limitation-the invention being defined by the claims.