Abstract:
A method used for routing a data packet in a router having a first table used for recording a plurality of destination IP address and second table used for recording destination MAC address, wherein the plurality of destination IP address are different. The method includes: receiving a data packet and retrieving a destination IP address from the data packet; looking up an indication value corresponding to the destination IP address from the first table; selecting a destination MAC address from the second table according to the indication value as a nexthop for the data packet; and transmitting the data packet to the nexthop.

Description:
BACKGROUND OF INVENTION 
     1. Field of the Invention 
     The present invention relates to a communication system, and more particularly, to a routing device. 
     2. Description of the Prior Art 
     With the rapid development of networks, the routing technique and the application of routers become more and more important. 
     A router is typically connected to several networks, and the connection situations between the networks are recorded in a routing table. In a conventional router, each row of the routing table represents a route of a data packet that is to be transmitted outward from the router. The destination information of the route, such as a destination IP address, network mask (or subnet), and nexthop are recorded in the row. When a data packet is received, the router looks up a nexthop for the data packet from the routing table according to the destination IP address recorded in the header of the data packet. The router then transmits the data packet to the nexthop. Being continually transmitted through different routers, the data packet is eventually transmitted to the destination IP address. 
     However, there may be many alternative routes to transmit the same data packet, i.e. a single destination IP address may correspond to a plurality of alternative nexthops. In the prior art, the router records the relationship between the destination IP address and the plurality of nexthops in a plurality of rows of the routing table, respectively. As a result, the routing table of the prior art is recorded with duplicate destination IP addresses and network masks so that the usage efficiency of the memory in the router is thereby decreased. 
     SUMMARY OF INVENTION 
     It is therefore an objective of the claimed invention to provide a routing method to improve the usage efficiency of the memory in a router. 
     Another objective of the claimed invention is to provide a routing method capable of supporting multi nexthop, multi default gateway, or/and multi NAPT (Network Address Port Translation) IP. 
     Another objective of the claimed invention is to provide a routing method capable of allocating networking bandwidth according to load balance rules. 
     The present invention discloses a method for routing a packet in a router having a first table for recording a plurality of unrepeated destination IP addresses and a second table for recording a plurality of MAC addresses. The method includes: receiving the packet and reading a destination IP address from the packet; looking up an indication value from the first table according to the destination IP address; selecting one of the MAC addresses as a nexthop for the packet from the second table according to the indication value; and transmitting the packet to the nexthop. 
     According to a preferred embodiment, an apparatus for routing a packet is disclosed. The apparatus includes: a first table recording a plurality of unrepeated destination IP addresses; a second table recording a plurality of MAC addresses; a receiving circuit receiving the packet and reading a destination IP address from the packet; a control circuit looking up an indication value from the first table according to the destination IP address and selecting one of the MAC addresses as a nexthop from the second table according to the indication value; and a transmitting circuit coupled to the control circuit for transmitting the packet to the nexthop. 
     These and other objectives of the present invention will no doubt become obvious to those of ordinary skill in the art after reading the following detailed description of the preferred embodiment that is illustrated in the various figures and drawings. 
    
    
     
       BRIEF DESCRIPTION OF DRAWINGS 
         FIG. 1  is a schematic diagram of a routing device according to the present invention. 
         FIG. 2  is a flowchart of a routing method according to the present invention. 
         FIG. 3  is a schematic diagram of a first table according to the present invention. 
         FIG. 4  is a schematic diagram of a second table according to the present invention. 
     
    
    
     DETAILED DESCRIPTION 
       FIG. 1  depicts a schematic diagram of a routing device  100  according to the present invention. The routing device  100  comprises a first storage medium  110 , a second storage medium  120 , a receiving circuit  130 , a control circuit  140 , and a transmitting circuit  150 . In practical implementations, the control circuit  140  can be a microprocessor, an ASIC (application specific integrated circuit), or other control units. 
       FIG. 2  depicts a flowchart of the routing operation of the routing device  100  according to the present invention. In step  204 , the routing device  100  records destination IP addresses (DIP), network mask (Netmask), and other associated data in a first table  300 , as shown in  FIG. 3 , according to its routing rules. The first table  300  is stored in the first storage medium  110 . In addition, the routing device  100  further records destination MAC addresses (DMAC), corresponding to the destination IP addresses recorded in the first table  300 , in a second table  400  as shown in  FIG. 4 . The second table  400  is stored in the second storage medium  120 . In practice, the first storage medium  110  and the second storage medium  120  can be different sections of a memory. In another embodiment, each of the two storage mediums can be either a volatile or a non-volatile memory, respectively. 
     As the first table  300  shown in  FIG. 3 , the data recorded in each row corresponds to the routing rule of the routing device  100 . Each row records a destination IP address (in a column  301 ) and a corresponding network mask (in a column  302 ). A set of a destination IP address and a network mask defines a destination network. In each row of the first table  300 , the connection relationship between the destination network and the routing device  100  is recorded in a column  303 . For example, the routing type recorded in a row  310  is “Direct,” meaning that the destination network 192.168.1.0/24 is directly connected to the routing device  100 . The routing type recorded in another row  320  is “Indirect,” meaning that the destination network 140.114.0.0/16 is not directly connected to the routing device  100 . 
     The second table  400  shown in  FIG. 4  records the destination MAC address (DMAC) and source MAC address (SMAC) for transmitting the data packet. In practice, the second table  400  can further record the source IP address (SIP) for use in network address translation (NAT) or network address/port translation (NAPT). The relationship between the second table  400  and the first table  300  is recorded as a start point of nexthop—NextHopStart—and a number of associated nexthops—NextHopNum. The start point of nexthop—NextHopStart—is recorded in a column  304  and the number of nexthops—NextHopNum—is recorded in a column  305 . For example, in row  310  of the first table  300 , the NextHopStart is 0 and the NextHopNum is 1. This means that the routing rule recorded in row  310  only corresponds to row  0  of the second table  400 . In row  320 , the NextHopStart is 1 and the NextHopNum is 2. This represents that the routing rule of row  320  corresponds to row  1  and row  2  of the second table  400 . 
     In step  204 , when the routing rule of a specific destination network allows a multi-nexthop setting, the routing device  100  of the present invention records the destination IP address and network mask in the first table  300  and records a plurality of nexthops corresponding to the destination network in the second table  400  to save the required memory space. In other words, the first table  300  does not record repeated data associated with the destination network. 
     In step  206 , the routing device  100  receives a data packet Packet_A via the receiving circuit  130  and reads a destination IP address DIP_A from the header of the Packet_A. 
     Next, in step  208 , the control circuit  140  looks up the routing type of the destination IP address DIP_A from the first table  300 . For example, the DIP_A is assumed as 192.168.1.0. As shown in  FIG. 3 , the routing type of DIP_A recorded in row  310  of the first table  300  is “Direct.” The control circuit  140  then looks up a destination MAC address DMAC_A corresponding to the destination IP address DIP_A from an address resolution protocol (ARP) table and replaces the SMAC in the header of the Packet_A with the SMAC recorded in row  0  of the second table  400 . Preferably, the routing device  100  then directly performs step  212  to transmit the Packet_A to a machine corresponding to DMAC_A via the transmitting circuit  150 . 
     However, suppose now that the receiving circuit  130  receives another data packet—Packet_B—in step  206  and the destination IP address DIP_B is assumed as 140.114.0.0. According to row  320  of the first table  300 , it is known that the routing type of DIP_B is “Indirect.” Therefore, the control circuit  140  looks up the NextHopStart_B and NextHopNum_B recorded in row  320  from the first table  300  in step  208  and then looks up the corresponding data from the second table  400  according to the indication value recorded in the above two columns of the first table  300 . 
     In step  210 , since the NextHopStart_B recorded in row  320  of the first table  300  is 1 and the NextHopNum_B is 2, the control circuit  140  looks up the data recorded in two rows, which begins from row  1  of the second table  400  and selects a DMAC recorded in one of the two rows as the DMAC_B for use in the transmission of the Packet_B. In one embodiment, for example, the control circuit  140  selects either row  1  or row  2  of the second table  400  as the nexthop of the Packet_B according to a load balance rule recorded in the column  306  of the first table  300 . The control circuit  140  can configure a load balance rule, such as round robin, source IP based, or session based etc. for each routing rule recorded in the first table  300 . In addition, the control circuit  140  can also use a default load balance setting to implement routing process. 
     In this embodiment, since the load balance rule recorded in the row  320  of the first table  300  is round robin, the control circuit  140  alternates between using the DMAC recorded in row  1  and the DMAC recorded in row  2  of the second table  400  to route data packets to be transmitted to the destination network 140.114.0.0/16. 
     For each routing rule, the data of destination networks and data of corresponding nexthops are recorded in the first table  300  and the second table  400 , respectively, according to the present invention. This method can support multi-nexthop and multi NAPT IP setting and can also greatly reduce the required memory space by avoiding recording repeated data in a single table. In addition, the routing method of the present invention can also support the setting of multi-gateway. For example, if the routing device  100  has two alternative gateways, one has a bandwidth of 1.5 Mbps and the other one has a bandwidth of 512 Kbps, the routing device  100  can configure a plurality of nexthops in the second table  400  based on the bandwidth ratio of the two gateways. For example, the route with 1.5 Mbps can be configured as three identical nexthops and the route with 512 Kbps can be configured as one nexthop. As shown in  FIG. 4 , rows 3, 4, and 5 correspond to the route with 1.5 Mbps while row  6  corresponds to the route with 512 Kbps. As a result, the routing device  100  balances the bandwidth usages of different gateways. 
     Those skilled in the art will readily observe that numerous modifications and alterations of the device and method may be made while retaining the teachings of the invention. Accordingly, the above disclosure should be construed as limited only by the metes and bounds of the appended claims.