Abstract:
An address resolution protocol (ARP) cache management method. An ARP cache comprises a plurality of ARP tables. Each ARP table comprises a plurality of updatable entries. The method comprises: receiving an ARP message; looking up the pluralities of ARP tables to find a message-matching entry; choosing an ARP table for storing new entries; creating a new entry to overwrite an existing entry in the chosen ARP table if no message-matching entry is found after looking up the ARP tables.

Description:
BACKGROUND OF THE INVENTION 
       [0001]    1. Field of the Invention 
         [0002]    The present invention relates to computer communication techniques, and more particularly to address resolution protocol (ARP) cache management methods and devices. 
         [0003]    2. Description of the Related Art 
         [0004]    In order to transmit a datagram to a destination host through a local network, a sender host must retrieve at least a hardware address, such as a media access control (MAC) address, of the destination host, and fill the hardware address in a link layer frame carrying the datagram.  FIG. 1  shows a link layer frame  100  with datagram  101  and header  102  comprising a next-hop&#39;s hardware address and a sender hardware address. The protocol address in the datagram  101 , such as an Internet protocol (IP) address, is utilized to identify the destination host of the frame and utilized for determining a route thereof to the destination host. When the frame is sent from the sender host through a network, the next hop in the route is determined based on a routing table. To transmit the frame hop by hop, the next-hop&#39;s hardware address must be filled in the link layer header to identify the next hop of the frame. A hardware address in the link layer header enables a server to determine its frame destination. 
         [0005]    Address resolution protocol (ARP) is utilized to obtain a hardware address (such as a MAC address) of a network node from its protocol address (such as an IP address). Generally, each network node has an ARP cache (a kind of memory) for storing and maintaining its own ARP table. The ARP table comprises a plurality of entries. Each entry comprises a mapping relationship between the protocol and hardware addresses corresponding to a specific network node. Table 1 illustrates an example of the ARP table: 
         [0000]    
       
         
               
               
               
               
             
           
               
                   
                 TABLE 1 
               
               
                   
                   
               
               
                   
                 Protocol address 
                 Hardware address 
                   
               
               
                   
                 (IP address) 
                 (MAC address) 
                 Other information 
               
               
                   
                   
               
             
             
               
                   
                 172.16.0.2 
                 00.01.22.33.E3.98 
                 . . . 
               
               
                   
                 172.16.0.35 
                 00.01.45.86.23.8F 
                 . . . 
               
               
                   
                 172.16.0.254 
                 00.01.02.35.63.7E 
                 . . . 
               
               
                   
                   
               
             
          
         
       
     
         [0006]    When frame transmission is required, the sender host looks up its own ARP table first for resolving the next-hop&#39;s hardware address. If no matching entry is found in the ARP table of the sender host, an ARP request is broadcasted to retrieve an ARP reply from the destination host, the next hop. When the ARP reply is retrieved, a corresponding entry thereof is added to the ARP table of the sender host for further reference. Thus, ARP entries are cached in an ARP table for the address resolution process. 
         [0007]    From the above description, we can understand that an ARP entry is added to an ARP table upon receipt of an ARP reply. However, an ARP entry may be added upon receipt of an unsolicited ARP message destined to the target host from any host in a network. Newly received unsolicited ARP message destined to the target host may result in an existing ARP entry being overwritten by a new entry corresponding to the ARP message regardless of the significance of these two entries. A frequently referenced entry may be overwritten by a useless entry. This may lower an ARP cache hit ratio. In a worst case scenario, the ARP entries may be flushed by malicious attacks. Devices with limited ARP table capacity are especially susceptible to malicious message attacks. Further, downgraded hit ratios may generate mass ARP requests and replies and reduce device and network performance. On the other hand, as a large ARP table capacity may increase the hit ratio of ARP entry queries, it may also consume time looking up the table. 
       BRIEF SUMMARY OF THE INVENTION 
       [0008]    A detailed description is given in the following embodiments with reference to the accompanying drawings. 
         [0009]    An exemplary embodiment of an address resolution protocol (ARP) cache management method is implemented in a communication device with an ARP cache. The ARP cache comprises a plurality of ARP tables and each table comprises updatable entries. The method comprises: receiving an ARP message; looking up the pluralities of ARP tables to find a message-matching entry; choosing an ARP table for storing new entries; creating a new entry to overwrite an existing entry in the chosen ARP table if no message-matching entry is found after looking up the ARP tables. 
         [0010]    An exemplary embodiment of a communication device capable of managing an address resolution protocol (ARP) cache. The ARP cache comprises a plurality of ARP tables and each table comprises updatable entries. The communication device further comprises a network interface unit and a processor. The network interface unit receives ARP messages or transmits frames to a target host. The processor creates a new entry to overwrite an existing entry in a chosen ARP table if necessary. 
         [0011]    An exemplary embodiment of an address resolution protocol (ARP) cache management method for managing an ARP cache with updatable entries in a communication device comprises the following steps. An entry operation is performed on a first entry in the ARP cache in response to a frame-based communication request. The first entry is classified into one of a plurality of ARP tables in the ARP cache according to the entry operation and the frame-based communication. 
         [0012]    An exemplary embodiment of a communication device capable of managing address resolution protocol (ARP) cache with updatable entries comprises a network interface unit and a processor. The network interface unit receives a request for frame-based communication. The processor performs an entry operation on a first entry in the ARP cache in response to the request and classifying the first entry into one of a plurality of ARP tables in the ARP cache according to the entry operation and the frame-based communication. 
         [0013]    An exemplary embodiment of an address resolution protocol (ARP) cache management method is implemented in a communication device with an ARP cache. The ARP cache comprises at least a reserved and an unreserved ARP table, each comprising updatable entries. The method comprises the following steps. When the communication device receives an ARP message, it is determined if the ARP cache comprises a message-matching entry comprising a cache protocol address matching the sender protocol address included in the received ARP message. If not, and when the ARP message is destined to the communication device, a new entry is restricted to be created in an unreserved ARP table to respond to the ARP message. 
         [0014]    An exemplary embodiment of an address resolution protocol (ARP) cache management method is implemented in a communication device with an ARP cache. The ARP cache comprises a reserved and an unreserved ARP table, each comprising updatable entries. The method comprises the following steps. When the communication device is to send a frame, the reserved ARP table is first searched to locate a transmission matching entry of the frame. The cache protocol address in the transmission matching entry matches the protocol address of a next hop of the frame. When no transmission matching entry exists in the reserved ARP table, the unreserved ARP table is then searched to locate a transmission matching entry. When no transmission matching entry exists in the ARP cache, a new entry is restricted to be created in the reserved ARP table. 
         [0015]    An exemplary embodiment of an address resolution protocol (ARP) cache management method is implemented in a communication device with an ARP cache. The ARP cache comprises updatable entries. The method comprises the following steps. When the communication device receives an ARP message, it is determined if the ARP cache comprises a message-matching entry comprising a cache protocol address matching the sender protocol address included in the received ARP message. When the ARP cache has no such matching entry, and the ARP message is destined to the communication device, a new entry is created in ARP cache to respond the ARP message reception with the restriction that the number of created entries in response to ARP message reception is less than the total number of all the updatable entries of the ARP cache. 
         [0016]    An exemplary embodiment of an address resolution protocol (ARP) cache management method is implemented in a communication device with an ARP cache. The ARP cache comprises updatable entries. The method comprises the following steps. New entries are created in ARP cache to respond ARP message reception when the condition of entry creation is satisfied. The number of created entries in response to ARP message reception is restricted to be less than the total number of all the updatable entries of the ARP cache. 
     
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         [0017]    The invention can be more fully understood by reading the subsequent detailed description and examples with references made to the accompanying drawings, wherein: 
           [0018]      FIG. 1  is a schematic diagram of an example of a link layer frame; 
           [0019]      FIG. 2  is a block diagram of the configuration of an exemplary embodiment of a communication device and a network system; 
           [0020]      FIG. 3  is a schematic diagram of an exemplary embodiment of an ARP cache; 
           [0021]      FIG. 4  is a schematic diagram of a second exemplary embodiment of an ARP table allocation; 
           [0022]      FIG. 5  is a schematic diagram of a third exemplary embodiment of an ARP table allocation; 
           [0023]      FIG. 6  is a flowchart of an exemplary ARP cache operation for ARP message reception; and 
           [0024]      FIG. 7  is a flowchart of an exemplary ARP cache operation for packet transmission. 
       
    
    
     DETAILED DESCRIPTION OF THE INVENTION 
       [0025]    The following description is of the best-contemplated mode of carrying out the invention. This description is made for the purpose of illustrating the general principles of the invention and should not be taken in a limiting sense. The scope of the invention is best determined by reference to the appended claims. 
         [0026]    ARP cache management methods and devices are provided in the following with exemplary embodiments thereof organized as: 
         [0027]    1. Hardware configuration 
         [0028]    2. ARP cache configuration 
         [0029]    3. ARP messages Reception 
         [0030]    4. Frame transmission 
         [0031]    5. Conclusion 
       1. HARDWARE CONFIGURATION 
       [0032]      FIG. 2  shows a typical network system in which several devices are connected by various networks. Each of network  30  and network A  50  may comprise a local area network (LAN) or a wide area network (WAN), such as the Internet. The communication device  10  is connected to other communication devices, such as the mobile device  20  and computer  22 , through network  30 . Mobile device  20  may comprise a mobile phone, a personal digital assistant (PDA), a tablet personal computer (PC), or a similar portable device. The router  40 , also connected to network  30 , routes network data packets between network  30  and another network, network A  50 . The communication device  10  comprises processor  11 , memory controller  12 , memory  13 , timer  14 , network interface unit  15 , and DMA controller  16 . Processor  11  controls the operation of the entire system as it fetches and executes software codes stored in memory  13 . Memory controller  12  serves as the bridge between processor  11  and memory  13  to transfer data therebetween. ARP cache  18  may be stored in memory  13  and its content is maintained and updated according to the ARP management method described later. An ARP cache may be located in other memory units, such as an on-chip memory, an on-board memory, or storage devices, such as a flash memory, an electrically erasable programmable read-only memory (EEPROM) built on a motherboard or in NIU  15 , or a hard disk. Timer  14  provides timing information to processor  11  so that processor  11  can obtain the time when certain events happen, such as when an ARP cache entry is added. 
         [0033]    Network interface unit (NIU)  15 , the communication unit of device  10 , connects with network  30  via TCP/IP network protocol. Common NIUs include Ethernet network interface devices and wireless local area network (WLAN) devices which may be implemented in any wireless network, such as WLAN or IEEE 802.11 network. The connection with network  30  can be wire-lined or wireless, depending on the NIU technology employed. NIU  15  transfers and receives data packets to and from Network  30 . Data packets outgoing to network  30  may be prepared and provided by processor  11 , or preferably by DMA controller  16 , which obtains packet data from memory  13  through memory controller  12  without intervention of processor  11 . 
         [0034]    When communication device  10  is going to send an ARP request to network  30 , processor  11  composes the ARP request packet in memory  13 , and then programs DMA controller  16  to transfer the packet through NIU  15  to network  30 . In the opposite direction, when an ARP request packet is received from Network  30 , the packet can go through NIU  15 , DMA controller  16  and memory controller  12  to memory  13 . Processor  1  may then access the packet data in memory  13  to perform necessary operations. 
         [0035]    Communication device  10  capable of ARP cache management may comprise a cell phone, a personal digital assistant (PDA), a laptop or desktop computer, or other devices. Processor  11  maintains the ARP cache  18  in response to ARP requests and acknowledgements. Note that an ARP cache may be managed by other processors, such as memory controller  12 , DMA controller  16 , or a processor in NIU  15 . In some embodiments of the communication device, any pair of components (such as processor  11 , memory controller  12 , memory  13 , or DMA controller  16 ) may be integrated into a single chip. 
       2. ARP CACHE CONFIGURATION 
       [0036]    With reference to  FIG. 3 , the ARP cache  18  comprises a plurality of ARP tables T in  and T out . Each ARP table comprises a plurality of entries (e.g.  183  and  184  in table T in  and  193  and  194  in table T out ). Please note that the size of each table can be different if required. For example, the size of table T out  can be larger than that of table T in . Also note that the number of ARP tables is not taken to be a limitation. The entry in each ARP table comprises at least a protocol address field, a hardware address field, and other information fields. The protocol address field and the hardware address field store a protocol address and a hardware address associated with each other and typically owned by a network node (i.e. a device connected to a network). The other information field in an entry may be utilized to find a least useful entry in the ARP table. The other information field may store the latest reference time or the created time of the entry provided by timer  14  or, alternatively, the reference count of the entry. For example, assumed that there are three entries in the ARP table, the corresponding latest reference times of the three entries are respectively T1=one hour ago, T2=two hours ago, and T3=three hours ago, the corresponding generation times of the three entries are respectively T4=March 2006, T5=April 2004, and T6=January 2005, and the reference count of the three entries are respectively C1=five, C2=twelve, and C3=thirty. If the other information field stores the latest reference time of the entry, the least useful entry is determined to be the third entry whose latest reference time is T3. If the other information field stores the generation time of the entry, the least useful entry is determined to be the second entry whose generation time is T5. If the other information field stores the reference count of the entry, the least useful entry is determined to be the first entry whose reference count is equal to C1. Note that an entry may comprise both the latest reference time and the reference count which records the number of reference operations for the entry. In this situation, the least useful entry may be determined according to both of the latest reference time and the reference count. A detailed description of the functionality and operation of the ARP tables T in  and T out  is provided in the following. 
         [0037]    The entries in the first table (T in ) are restricted to those created in response to ARP message receipt, and the entries in the second table (T out ) are restricted to those created in response to packet (or frame) transmission. In other words, entries created in response to ARP message receipt are stored and classified into T in  and entries created in response to frame transmission are stored and classified into T out . Thus, communication device  10  classifies the updatable entries and prevents T in  and T out  from unconditional entry creation. Some entries (least useful entries) in one table may be removed or overwritten according to latest reference time, generation time, or the reference count. Some entries in one table may be further moved to another table according to the precedence of each table (e.g. from a table of lower precedence to another table of higher precedence) and the specific attribute (utilized to determine which entry belongs to which ARP table). Furthermore, different tables may be located in different areas of the ARP cache or discretely distributed with each entry thereof identified by an associated class ID. A detailed description of table allocation is provided in the following. 
         [0038]      FIGS. 4 and 5  are examples of ARP caches with different table allocation. In  FIG. 4 , T in  and T out  are respectively located in different areas of the ARP cache  18 A, for which two different ranges of addresses are allocated. Table T out  locates from ADDRESS_ 1  to ADDRESS_ 2  in the ARP cache  18 A while Table T in  locates from ADDRESS_ 3  to ADDRESS_ 4  in the ARP cache  18 A. In  FIG. 5 , whether one entry belongs to T in  or T out  is determined based on an attribute (such as a value in class ID field  180 ) associated with the entry. Entries with class ID “1” belong to table T in , and entries with class ID “2” belong to table T out . Note that the attribute and the ARP cache may be separated and stored anywhere in communication device  10 . In some embodiments, ARP caches may be configured in other data structure, such as linked lists. A variable C (not shown) listed as other information in  FIG. 5  may serve as a counter recording the number of entries in T in , and a variable S (not shown) may be preset as the upper limit of the variable C, thus limiting the number of entries in T in  to be less than the total number of updatable entries in the ARP cache. For example, assumed that the variable S is set to be 5 and the variable C is 3. Since the variable C is not larger than the variable S, new entries can still be added to table T in . Once the variable C increments to 5, no more new entry can be added to table T in  (the new entry can still overwrite an existing entry). 
         [0039]    T in  and T out  may be respectively prioritized in that T in  is first referenced in response to ARP message receipt prior to other tables in ARP cache  18 , and T out  is first referenced in response to frame transmission prior to other tables in ARP cache  18 . Alternatively, T out  may be respectively prioritized to be first referenced prior to other tables in ARP cache  18  in response to frame transmission and ARP message receipt. 
         [0040]    The ARP cache management method performs an entry operation on an entry in the ARP cache in response to a request for frame-based communication and classifies the entry into one of a plurality of tables in the ARP cache according to the entry operation and the frame-based communication. The frame-based communication comprises ARP message receipt and frame transmission, and the frame-based communication request may be delivered by an application in communication device  10  or other devices coupled thereto. Details of the ARP cache management in the following are set forth with respect to ARP message receipt and frame transmission. 
       3. ARP MESSAGES RECEPTION 
       [0041]    Communication device  10  performs ARP cache operations when receiving an ARP message. With reference to  FIG. 6 , when NIU  15  receives an ARP message (step S 2 ), processor  11  first searches table T out  for a matching entry of the ARP message (step S 4 ), which comprises a protocol address matching the sender protocol address included in the received ARP message. In other words, the matching entry is an entry whose protocol address is the same as that of the ARP message. Processor  11  determines if such a matching entry of the ARP message is located in table T out  (step S 6 ). If so, processor  11  updates the matching entry in T out  by utilizing the ARP message (step S 8 ). Processor  11  may update the matching entry by filling a hardware address field of the matching entry with the sender hardware address included in the ARP message. 
         [0042]    If T out  does not have a matching entry (no in step S 6 ), processor  11  searches T in  for an entry matching the ARP message (step S 10 ) and determines if the matching entry is located in table T in  (step S 12 ). If so, processor  11  updates the matching entry in table T in  utilizing the ARP message (step S 14 ). Similarly, processor  11  may update the matching entry by filling a hardware address field of the matching entry with the sender hardware address included in the ARP message. Note that communication device  10  does not change the classification of the matching entry. 
         [0043]    If table T in  does not have such a matching entry, processor  11  determines if the ARP message is destined to communication device  10  (step S 116 ). When ARP cache  18  has no such matching entry, and the ARP message is destined to communication device  10 , processor  11  creates a new entry and restricts the new entry to be created as a member of table T in  to respond to the ARP message (step S 18 ). Processor  11  may fill a protocol address field and a hardware address field of the new entry with the sender protocol address and the sender hardware address included in the ARP message. When table T in  is full, the least useful entries therein may be removed or overwritten by the new entry. The number of entries of table T in  is limited to less than the total number of all the updatable entries of the ARP cache, thus to prevent arbitrary entry creation. In a worst case scenario, the malicious attack provides ARP flooding messages, which causes a huge amount of useless new entries to remove or overwrite not only the least useful entries but also other useful entries in table T in  (almost all entries in table T in  are removed or overwritten). Please note that the malicious attack can only affect the table T in ; the other tables (e.g. T out ) still operate normally since the table T in  is prioritized to be first referenced in response to ARP message receipt. In other words, even if communication device  10  continuously receives malicious ARP flooding messages, overwriting of entries in other tables (e.g. T out ) is prevented. Processor  11  prevents entry creation to table T in  until the communication device receives an ARP message destined thereto, and no matching entry of which is found in the ARP cache. Time information stored in the other information field of each entry may be utilized to determine the age of the entry and further to locate the least useful entry. 
         [0044]    When the ARP message is not destined to communication device  10  (no in step S 16 ), processor  11  discards the ARP message (step S 20 ). Processor  11  may identify the target protocol address in the frame header (i.e. the L2 header) of the ARP message to determine if the ARP message is destined to communication device  10 . If the target protocol address in the frame header of the ARP message is the protocol address of communication device  10 , processor  11  determines that the first message is destined to communication device  10  and responds as previously described. 
         [0045]    In some embodiments, note that processor  11  may search table T in  for the matching entry prior to table T out . Communication device  10  also performs ARP cache operations when preparing to send a packet. Additionally, an example of ARP message reception is provided in the following. 
         [0046]    Taking IP address and MAC address as examples, assume that communication device  10  receives an ARP message, whose source IP and MAC addresses are 172.16.0.2 and 00.01.22.33.E3.98, respectively. After receiving the ARP message (step S 2 ), processor  11  searches whether there is a matching entry (whose IP address is equal to 172.16.0.2) in any ARP table (steps S 4  and S 10 ). Preferably, processor  11  looks up table T out  first rather than table T in . Various cases of searching result are provided in the following:
       Case 1: Processor  11  finds there is a matching entry in table T out  (yes in step S 6 ). Table T out  is shown in the following.       
 
         [0000]    
       
         
               
               
               
             
           
               
                 TABLE T out   
               
               
                   
               
               
                   
                   
                 Other 
               
               
                 IP address 
                 MAC address 
                 information 
               
               
                   
               
             
             
               
                 172.16.0.2 
                 00.01.45.86.23.8F 
                 . . . 
               
               
                 . . . 
                 . . . 
                 . . . 
               
               
                   
               
             
          
         
       
       
         
           
              After finding the matching entry in table T out , processor  11  updates the MAC address of the matching entry from 00.01.45.86.23.8F to 00.01.22.33.E3.98, the MAC address of the ARP message (step S 8 ). The modified Table T out  is shown in the following. 
           
         
       
     
         [0000]    
       
         
               
             
               
               
               
             
           
               
                 TABLE T out   
               
             
             
               
                   
               
               
                 (matching entry updated) 
               
             
          
           
               
                 IP address 
                 MAC address 
                 Other information 
               
               
                   
               
               
                 172.16.0.2 
                 00.01.22.33.E3.98 
                 . . . 
               
               
                 . . . 
                 . . . 
                 . . . 
               
               
                   
               
             
          
         
       
       
         
           
             Case 2: Processor  11  finds there is a matching entry in table T in  (yes in step S 12 ). Table T in  is shown in the following. 
           
         
       
     
         [0000]    
       
         
               
               
               
               
             
           
               
                   
                 TABLE T in   
               
               
                   
                   
               
               
                   
                 IP address 
                 MAC address 
                 Other information 
               
               
                   
                   
               
             
             
               
                   
                 172.16.0.2 
                 00.01.02.35.63.7E 
                 . . . 
               
               
                   
                 . . . 
                 . . . 
                 . . . 
               
               
                   
                   
               
             
          
         
       
       
         
           
              After finding the matching entry in table T in , processor  11  updates the MAC address of the matching entry from 00.01.02.35.63.7E to 00.01.22.33.E3.98, the MAC address of the ARP message (step S 14 ). The modified Table T in  is shown in the following. 
           
         
       
     
         [0000]    
       
         
               
             
               
               
               
             
           
               
                 TABLE T in   
               
             
             
               
                   
               
               
                 (matching entry updated) 
               
             
          
           
               
                 IP address 
                 MAC address 
                 Other information 
               
               
                   
               
               
                 172.16.0.2 
                 00.01.22.33.E3.98 
                 . . . 
               
               
                 . . . 
                 . . . 
                 . . . 
               
               
                   
               
             
          
         
       
       
         
           
             Case 3: Processor  11  can not find a matching entry in any table (no in step S 12 ). Tables T in  and T out  are shown in the following. 
           
         
       
     
         [0000]    
       
         
               
               
               
             
           
               
                 TABLE T in   
               
               
                   
               
               
                 IP address 
                 MAC address 
                 Other information 
               
               
                   
               
             
             
               
                 172.16.0.1 
                 00.03.45.86.23.5F 
                 . . . 
               
               
                 . . . 
                 . . . 
                 . . . 
               
               
                   
               
             
          
         
       
     
         [0000]    
       
         
               
               
               
             
           
               
                 TABLE T out   
               
               
                   
               
               
                 IP address 
                 MAC address 
                 Other information 
               
               
                   
               
             
             
               
                 172.16.0.3 
                 00.53.47.89.27.5A 
                 . . . 
               
               
                 . . . 
                 . . . 
                 . . . 
               
               
                   
               
             
          
         
       
       
         
           
              If the ARP message is destined (no in step S 16 ), processor  11  does nothing to any ARP table (S 20 ). Otherwise (yes in step S 16 ), processor  11  adds a new entry to table T in . The IP and MAC addresses of the new entry are 172.16.0.2 and 00.01.22.33.E3.98, the same as those of the ARP message (step S 18 ). If table T in  is already full, the least useful entry therein may be removed or overwritten by the new entry. The modified Table T in  is shown in the following. 
           
         
       
     
         [0000]    
       
         
               
             
               
               
               
             
           
               
                 TABLE T in   
               
             
             
               
                   
               
               
                 (matching entry added) 
               
             
          
           
               
                 IP address 
                 MAC address 
                 Other information 
               
               
                   
               
               
                 172.16.0.1 
                 00.03.45.86.23.5F 
                 . . . 
               
               
                 172.16.0.2 
                 00.01.22.33.E3.98 
                 . . . 
               
               
                   
               
             
          
         
       
     
       4. FRAME TRANSMISSION 
       [0050]    Before communication device  10  transmits any frame to a target host which would be the next hop&#39;s host, the communication device  10  must obtain the protocol address (e.g. IP address) and hardware address (e.g. MAC address) of the target host. Generally, the protocol address of the target host is already known by the communication device  10  and the hardware address of the target host must be further searched in the ARP table of the communication device  10 . With reference to  FIG. 7 , when communication device  10  is to send a frame (step S 602 ), Processor  11  first searches table T out  for a matching entry of the frame (step S 604 ). The matching entry is an entry whose protocol address is the same as that of the target host. If a matching entry is found in T out  (step S 606 ), processor  11  further checks whether the hardware address of the matching entry is valid before filling the outgoing frame with the hardware address of the matching entry (step S 608 ). 
         [0051]    If the hardware address of the matching entry is valid (yes in step S 608 ), processor  11  fills the header of outgoing frame with the matching entry&#39;s hardware address (step S 610 ), and transmits the frame through NIU  15  (step S 611 ). Otherwise (no in step S 608 ), NIU  15  transmits an ARP request to acquire the target host&#39;s hardware address (step S 612 ). Upon receipt of ARP reply carrying the hardware address, processor  11  accordingly updates the matching entry&#39;s hardware address (step S 613 ) and fills the header of outgoing frame with the matching entry&#39;s hardware address (step S 615 ). Finally, NIU  15  transmits the frame (step S 611 ). 
         [0052]    When no matching entry of the frame is located in table T out , processor  11  searches another table T in  for such a matching entry of the frame (step S 614 ). Processor  11  determines if such a matching entry exist in T in  (step S 616 ). If so, processor  11  moves the matching entry of the frame from T in  to T out  (step S 618 ) and fills the header of outgoing frame with the matching entry&#39;s hardware address (step S 610 ). Thus, the matching entry is moved to the table of higher precedence and prevented from being overwritten by incoming ARP messages. After filling in the hardware address (step S 610 ), NIU  15  transmits the frame (S 611 ). If table T in  is fall, the least useful entry therein may be removed or overwritten by the matching entry of the frame. Alternatively, the capacity of T in  can be enlarged for accommodating the matching entry. 
         [0053]    When no matching entry of the frame exists in the ARP cache (no in step S 616 ), processor  11  adds a new entry to table T out  (step S 620 ), fills a protocol address field of the new entry with the protocol address of the target host, and directs NIU  15  to transmit an ARP request to acquire a hardware address associated with the protocol address of the target host (step S 622 ). Upon receipt of ARP reply carrying the hardware address associated with the protocol address of the target host, processor  11  accordingly fills a hardware address field of the new entry and the header of the frame with the retrieved hardware address (step S 624 ) and directs NIU  15  to transmit the frame (step S 626 ). An example of frame transmission is provided in the following. 
         [0054]    Still Taking IP address and MAC address as examples, assume that communication device  10  wants to send frames to a target host, whose IP address is 172.16.0.35 and MAC address is unknown. Before transmitting, processor  11  searches whether there is a matching entry (whose IP address is equal to 172.16.0.35) in any ARP table (steps S 604  and S 614 ) to found out the target host&#39;s MAC address. Preferably, processor  11  looks up table T out  first rather than table T in . Various cases of searching result are provided in the following:
       Case 1: Processor  11  finds a matching entry in table T out  (yes in step S 606 ). Table T out  is shown in the following.       
 
         [0000]    
       
         
               
               
               
             
           
               
                 TABLE T out   
               
               
                   
               
               
                 IP address 
                 MAC address 
                 Other information 
               
               
                   
               
             
             
               
                 172.16.0.35 
                 00.08.45.86.23.8F 
                 . . . 
               
               
                 . . . 
                 . . . 
                 . . . 
               
               
                   
               
             
          
         
       
       
         
           
              If the MAC address of the matching entry is valid (e.g. 00.08.45.86.23.8F) (yes in step S 608 ), communication device  10  fills the frame&#39;s MAC address field with the valid value 00.08.45.86.23.8F and transmits the frame (steps S 610  and S 611 ). Otherwise (no in step S 608 ), processor sends an ARP request for the target host&#39;s MAC address to update the matching entry&#39;s MAC address (step S 613 ). 
             Case 2: Processor  11  finds there is a matching entry in table T in  (yes in step S 616 ). Table T in  is shown in the following. 
           
         
       
     
         [0000]    
       
         
               
               
               
             
           
               
                 TABLE T in   
               
               
                   
               
               
                 IP address 
                 MAC address 
                 Other information 
               
               
                   
               
             
             
               
                 172.16.0.35 
                 01.23.46.87.23.5C 
                 . . . 
               
               
                 . . . 
                 . . . 
                 . . . 
               
               
                   
               
             
          
         
       
       
         
           
              Similarly, communication device  10  fills the frame&#39;s MAC address field with the matching entry&#39;s MAC address (e.g. 01.23.46.87.23.5C) and transmits the frame (steps S 610  and S 611 ). The key difference with case 1 is that the matching entry further moves form table T in  to table T out  (step S 618 ). 
           
         
       
     
         [0000]    
       
         
               
             
               
               
               
             
           
               
                 TABLE T in   
               
             
             
               
                   
               
               
                 (matching entry moved) 
               
             
          
           
               
                 IP address 
                 MAC address 
                 Other information 
               
               
                   
               
               
                 . . . 
                 . . . 
                 . . . 
               
               
                   
               
             
          
         
       
       
         
           
             Case 3: Processor  11  can not find a matching entry in any table (no in step S 616 ). Tables T in  and T out  are shown in the following. 
           
         
       
     
         [0000]    
       
         
               
               
               
             
           
               
                 TABLE T in   
               
               
                   
               
               
                 IP address 
                 MAC address 
                 Other information 
               
               
                   
               
             
             
               
                 172.16.0.33 
                 00.03.45.86.23.5F 
                 . . . 
               
               
                 . . . 
                 . . . 
                 . . . 
               
               
                   
               
             
          
         
       
     
         [0000]    
       
         
               
               
               
             
           
               
                 TABLE T out   
               
               
                   
               
               
                 IP address 
                 MAC address 
                 Other information 
               
               
                   
               
             
             
               
                 172.16.0.28 
                 00.53.47.89.27.5A 
                 . . . 
               
               
                 . . . 
                 . . . 
                 . . . 
               
               
                   
               
             
          
         
       
       
         
           
              Processor  11  adds a new entry in table T out  and fills its IP address with 172.16.0.35, and sends an ARP request to fills its MAC address (steps S 620 , S 622  and S 624 ). After the IP and MAC addresses of the frame are filled according to the responded ARP reply, communication device  10  sends the frame (step S 626 ). The modified Table T out  is shown in the following. 
           
         
       
     
         [0000]    
       
         
               
             
               
               
               
             
           
               
                 TABLE T out   
               
             
             
               
                   
               
               
                 (matching entry added) 
               
             
          
           
               
                 IP address 
                 MAC address 
                 Other information 
               
               
                   
               
               
                 172.16.0.28 
                 00.53.47.89.27.5A 
                 . . . 
               
               
                 172.16.0.35 
                 00.01.22.33.E3.98 
                 . . . 
               
               
                   
               
             
          
         
       
     
       5. CONCLUSION 
       [0058]    Implementation of entry movement from table T in  to table T out  may be different in the various ARP cache configurations. Specifically, when tables T out  and T in  are respectively located in different areas of ARP cache  18 , processor  11  may generate a copy of the matching entry of the frame in T out  and delete the matching entry of the frame in T in . When classification of the matching entry of the frame is identified based on an associated class ID, processor  11  may modify the class ID to implement the movement of the matching entry of the frame from T in  to T out . According to the ARP management method, unsolicited ARP entry destined to the target host are stored in T in , and moved to T out  when referenced for frame transmission. Thus, malicious ARP flooding messages are prevented from overwriting recently referenced ARP entries in T out . Table 2 in the following summarizes operations of communication device  10 . 
         [0000]    
       
         
               
               
             
               
               
               
             
               
               
               
               
               
             
               
               
               
             
           
               
                   
                 TABLE 2 
               
             
             
               
                   
                   
               
               
                   
                 Search result 
               
             
          
           
               
                   
                 Found in T out   
                   
               
             
          
           
               
                   
                   
                 Without 
                   
                   
               
               
                 Frame 
                   
                 hardware 
                 With hardware 
               
               
                 Operation 
                 Not found 
                 address 
                 address 
                 Found in T in   
               
               
                   
               
               
                 Frame 
                 1. Adding a new 
                 1. Replacing 
                 1. Filling 
                 1. Moving the 
               
               
                 transmission 
                 entry without 
                 the held frame 
                 hardware 
                 located entry 
               
               
                   
                 hardware 
                 2. Sending an 
                 address in the 
                 from T in  to T out   
               
               
                   
                 address to T out   
                 ARP request if 
                 header of the 
                 2. Filling 
               
               
                   
                 2. Holding the 
                 allowed 
                 frame 
                 hardware 
               
               
                   
                 frame 
                   
                 2. Sending the 
                 address in the 
               
               
                   
                 3. Sending an 
                   
                 frame 
                 header of the frame 
               
               
                   
                 ARP request 
                   
                   
                 3. Sending the frame 
               
             
          
           
               
                 ARP 
                 Adding a new 
                 Updating matching ARP entry located in T out  or T in   
               
               
                 message 
                 ARP entry to T in  if 
               
               
                 receipt 
                 the ARP message 
               
               
                   
                 is destine to 
               
               
                   
                 device 10 
               
               
                   
               
             
          
         
       
     
         [0059]    When NIU  15  receives a request for frame-based communication, processor  11  searches ARP cache  18  for a matching entry corresponding to the frame-based communication and if locating the matching entry, classifies the matching entry into T in  or T out  according to the frame-based communication. For example, when the matching entry is located in T in  in response to a request for transmitting a frame, processor  11  classifies the matching entry into T out . When the matching entry is located in T in  in response to a request for receiving an ARP message, processor  11  does not change classification of the matching entry, thus, the matching entry remains in T in . When the matching entry is located in T out  in response to a request for receiving an ARP message or transmitting a frame, processor  11  does not change classification of the matching entry. 
         [0060]    If no entry corresponding to the frame-based communication has been located, processor  11  creates a corresponding new entry in response to the frame-based communication, and classifies the new entry according to the frame-based communication. When the new entry is created in response to a request for transmitting a frame, processor  11  classifies the entry into T out . When the new entry is created in response to a request for receiving an ARP message, processor  11  classifies the entry into T in . 
         [0061]    Generally, when NIU  15  receives a request for frame-based communication, processor  11  performs an entry operation on a matching entry in the ARP cache in response to the request and classifies the matching entry into of T in  or T out  according to the entry operation and the frame-based communication. 
         [0062]    The ARP management method may be implemented in other devices connected to network  30  and network A  50 , such as mobile device  20 , computer  22 , and router  40 . 
         [0063]    In conclusion, at least two tables, T in  and T out , are allocated in an ARP cache, and updatable ARP entries are respectively classified thereto. The number of entries in T in  is limited to less than the total number of all the updatable entries of the ARP cache. An ARP entry currently referenced for frame transmission is stored in table T out  and is first referenced in response to a subsequent frame transmission, thus to improve time efficiency of ARP lookup. Unsolicited ARP entries are stored in table T in , and moved to T out  once referenced for frame transmission. Thus, malicious ARP flooding messages are prevented from overwriting recently referenced ARP entries in table T out . 
         [0064]    While the invention has been described by way of example and in terms of the preferred embodiments, it is to be understood that the invention is not limited to the disclosed embodiments. To the contrary, it is intended to cover various modifications and similar arrangements (as would be apparent to those skilled in the art). Therefore, the scope of the appended claims should be accorded the broadest interpretation so as to encompass all such modifications and similar arrangements.