Method of routing a packet in a routing device

A method of routing a packet in a routing device having a main processor that includes a main cache table and an instant cache table is disclosed. The instant cache stores a recent address and a recent interface associated with the most recent packet transmission process made by the routing device. The method includes the steps of receiving a packet that includes its destination address, checking whether the destination address belongs to the routing device, checking whether the destination address is identical to the recent address if the destination address does not belong to the routing device, and transmitting the packet to the recent interface if the destination address is identical to the recent address. As a result, the core information related to the routing path determination is stored not only in the routing table of the protocol layer but also in the main and instant cache tables included in the main processor. Since the selection of the routing path for a given packet depends on the individual characteristic of the packet, the data processing time of the packet is greatly reduced. Consequently, the routing performance of the routing device is greatly enhanced.

This application claims the benefit of the Korean Application No. P2000-84709 filed on Dec. 28, 2000, which is hereby incorporated by reference.

BACKGROUND OF THE INVENTION

1. Field of the Invention

The present invention relates to method of routing a packet in a routing device, and more particularly, to a routing method being able to reduce the packet-processing time by setting a routing path that depends on the characteristic of each packet.

2. Discussion of the Related Art

In general, a device that connects two or more network systems having a same transmission protocol is often referred to as a routing device. A typical routing device included in a network system sets a node in the system itself or in another network system, and it transmits one or more packets received using a given transmission path.

FIG. 1illustrates a network system including a typical routing device10. The main processor1checks whether a packet is received through a port6. When the routing device10receives a packet, whose destination address is set to another node or another routing device (e.g., R2), the main processor1sends the packet to the protocol layer2included in the routing device10. The protocol layer2may be any one of the IP (Internet Protocol) layer2A, IPX (Internetwork Packet exchange) layer2B, Bridge layer2C, and many others.

For example, when the IP layer2A receives the packet from the main processor1, it initially determines whether to process the packet. Once it decides to process the packet, the IP layer2A sends the packets to the top application module3.

On the other hand, if it decides not to process the packet, it checks the destination address of the packet. For example, the IP layer2A obtains the interface number corresponding to the destination address of the packet by searching the IP routing table4A of the routing table4. And it sends the packets to the interface found. Then the packet gets transmitted to a node or routing device corresponding to the destination address of the packet.

As described above, the packet passes through a routing path that includes the main processor1and the IP layer2A, and this is shown inFIG. 2. Since such routing path is formed regardless of the individual characteristic of the packet, the packet-processing rate of the routing device10is low. Therefore, the performance of the routing device may be degraded.

Even though it is highly desirable to provide a method of setting a routing path that depends on the individual characteristic of each packet, such method is currently unavailable for the existing routing device.

SUMMARY OF THE INVENTION

An object of the present invention is to provide a method of routing a packet in a routing device, in which a routing path depends on the characteristic of each data packet.

Another object of the present invention is to provide a method of routing a packet that optimizes the routing performance of the routing device by minimizing the data processing time of each packet.

To achieve these objects and other advantages and in accordance with the purpose of the invention, as embodied and broadly described herein, a method of routing a packet in a routing device having a main processor that includes a main cache table and an instant cache table includes (a) receiving a packet that includes its destination address, (b) checking whether the destination address belongs to the routing device, (c) checking whether the destination address is identical to the recent address if the destination address does not belong to the routing device, and (d) transmitting the packet to the recent interface if the destination address is identical to the recent address.

The method further includes the steps of (e) calculating a Hashing Key value (N) of the destination address if it is determined from the step (c) that the destination address is not identical to the recent address, (f) checking whether the destination address is identical to an Nth cache address stored in the main cache table, and (g) transmitting the packet to a first interface corresponding to the Nth cache address if the destination address is identical to the Nth cache address.

Finally, the method includes the step of (h) resetting the recent address and recent interface stored in the instant cache table to the Nth cache address and the first interface, respectively.

In another aspect of the present invention, a method of routing a packet in a routing device having a main processor that includes a main cache table and an instant cache table includes the steps of (a) receiving a packet that includes its destination IP address, (b) checking whether the destination IP address belongs to the routing device, (c) checking whether the destination IP address is identical to the recent IP address if the destination IP address does not belong to the routing device, and (d) transmitting the packet to the recent IP interface if the destination IP address is identical to the recent IP address.

The method further includes the steps of (e) calculating a Hashing Key value (N) of the destination IP address if it is determined from the step (c) that the destination IP address is not identical to the recent IP address, (f) checking whether the destination IP address is identical to an Nth cache IP address stored in the main cache table, and (g) transmitting the packet to a first IP interface corresponding to the Nth cache IP address if the destination IP address is identical to the Nth cache IP address.

Finally, the method further includes the step of (h) resetting the recent IP address and recent IP interface stored in the instant cache table to the Nth cache IP address and the first IP interface, respectively.

DETAILED DESCRIPTION OF THE INVENTION

FIG. 3illustrates a network system including a routing device20according to the present invention. As it can be seen from the figure, the device includes a main processor11, a protocol layer12, a top application module13, and a routing table14.

The protocol layer12may include any one of the IP (Internet Protocol) layer12A, IPX (Internetwork Packet exchange) layer12B, Bridge layer12C, and many others.

The main processor11included in the routing device20of the present invention includes a main cache table11A and an instant cache table11B. The main cache table11A additionally stores some of the core information stored in the routing table14.

For example, in a case where the routing table14stores various information such as the destination Internet Protocol (IP) address, subset mask, gateway, metric, protocol, and interface, the main cache table11A additionally stores the core information including the cache IP addresses and interfaces. Of course, the cache IP addresses stored in the main cache table11A are equivalent to the destination addresses stored in the routing table14(e.g., IP routing table14A).

In addition, the instant cache table11B stores the recent address and its corresponding interface associated with the most recent packet transmission made by the routing device20.

When the routing device20receives a packet from another node or routing device, the main processor11is able to complete its packet transmission process using both tables (11A and11B) even without transmitting the packet to the protocol layer12(e.g., IP protocol layer12A).

In the existing routing device shown inFIG. 1, all the core information is stored in the routing table4. Therefore, each packet must be transmitted through a routing path that includes both of the main processor1and the IP layer2A.

On the other hand, in the routing device of the present invention, the core information related to the routing path determination of a packet is stored not only in the routing table14coupled to the protocol layer12but also in the main cache table11A and instant cache table11B included in the main processor11.

Therefore, a routing path including the main processor11only or another routing path including both of the main processor11and the protocol layer12can be selected for transmitting a packet. The selection depends on the individual characteristic of the packet.

For example, as shown inFIG. 4, a routing path including the main processor11only can be used for transmitting a packet. Consequently, the required time for processing the packet will be reduced.

Reference will now be made in detail to a method of routing a packet in a routing device in accordance with the present invention, examples of which are illustrated inFIG. 5.

First of all, the main processor11of the routing device20periodically checks whether a packet is received for each port16(S1). If no packet is received, it waits until a predetermined period is lapsed (S2), and repeats the step S1again for each port.

If it is determined from the step S1that a packet is received through a port, the main processor11checks whether the destination address (e.g., destination IP address) of the packet belongs to the routing device (S3). That is, the main processor11checks whether if the packet should be transmitted to another node or routing device. For example, the main processor11obtains the destination address (e.g. IP address) of the packet by searching the data region following the fourteenth byte of the IP header.

If the destination address (e.g. IP address) of the packet received belongs to the routing device20, in which the main processor11is included, the main processor11determines that the packet should be processed in the protocol layer12(e.g., IP layer12A). Therefore, it sends the packet to the protocol layer12(e.g., IP layer) (S20).

When the protocol layer12receives the packet from the main processor11, the IP layer12initially determines whether the packet is subject to be processed (routing) in the protocol layer (e.g., IP layer)12(S21).

If it is not, the protocol layer12sends the packet to the top application module (TAM)13(S22). Otherwise, the protocol layer12finds the interface corresponding to the destination address of the packet by searching the routing table14(e.g., IP routing table14A) (S23), and it transmits the packet to the interface found (S24).

Referring back to the step S3, if the destination address of the packet corresponds to another routing device, the main processor11checks whether the destination address of the packet is Unicast (S4).

If it is not (e.g., multicast, broadcast, and etc.), the main processor11sends the packet to the protocol layer12(S20). Then the protocol layer12repeats the steps S21to S24.

Otherwise, the main processor11searches the core information stored in the instant cache table11B (S5) and checks whether the destination address of the packet is identical to the recent address stored in the instant cache table11B (S6). As described earlier, the recent address represents the address associated with the most recent packet transmission process made by the routing device.

If the destination address of the packet is identical to the recent address stored in the instant cache table11B, the main processor11finds the interface corresponding to the recent address and sends the packet to the interface found (S7).

On the other hand, if the destination address of the packet is not identical to the recent address stored in the instant cache table11B, the main processor11obtains a Hashing key corresponding to the destination address using a Hashing function (S8).

For example, the Hashing key can be obtained by [Equation 1]
K=(N1+N2+N3+N4)/T,
where K and T represent the Hashing key and the size of the main cache table11A, and N1, N2, N3, and N4represent the first, second, third, and fourth bytes of the destination address of the packet.

Thereafter, main processor11finds the cache address corresponding to the calculated Hashing key by searching the main cache table11A (S9). For example, if the Hashing key is4, the cache address is found in the fourth entry of the main cache table11A. And if the Hashing key is15, the cache address is found in the fifteenth entry of the main cache table11A.

Next, the main processor11checks whether the destination address of the packet is identical to the cache address found in the step S9(S10).

For instance, if the Hashing key turns out to be4, then the main processor11checks whether the cache address that belongs to the fourth entry of the main cache table11A is identical to the destination address of the packet.

If the destination address of the packet is not identical to the cache IP address found in the step S9, the main processor11concludes that the destination address does not exist in the main cache table11A. Therefore, it sends the packet to the protocol layer12A (S30).

When the protocol layer12receives the packet, the protocol layer12initially determines whether the packet is subject to be processed in the protocol layer12(S31).

If it is not, the protocol layer12sends the packet to the top application module (TAM)13(S32). Otherwise, the protocol layer12finds the interface corresponding to the destination address of the packet by searching the routing table14(e.g., IP routing table14A) (S33), and it sends the packet to the interface found (S34).

Next, the main processor11stores the address and interface associated with the packet transmission process made in the step S34in the main cache table11A (S35). And it also stores the same information in the instant cache table11B (S36). Accordingly, the instant cache table11B includes the recent address and interface associated with the most recent packet transmission information.

Referring back to the step S10, if it is determined from the step S10that the destination address of the packet is identical to the cache address found in the step S9, the main processor11sends the packet to the interface corresponding to the cache address (S1).

Similarly, the main processor11stores the interface and the cache address associated with the packet transmission process made in the step S11in the instant cache table11B (S12).

In conclusion, the core information related to the routing path determination is stored not only in the routing table14of the protocol layer12but also in the main and instant cache tables (11A and11B) included in the main processor11. Since the selection of a routing path for a given packet depends on the individual characteristic of the packet, the data processing time of the packet is reduced. Consequently, the routing performance of the routing device is enhanced.

It will be apparent to those skilled in the art than various modifications and variations can be made in the present invention. Thus, it is intended that the present invention covers the modifications and variations of this invention provided they come within the scope of the appended claims and their equivalents.