Internet protocol packet router

Details Internet protocol packet router Internet protocol packet router

2000-07-11

2004-10-05

Nguyen, Chau (Department: 2663)

Multiplex communications

Pathfinding or routing

Combined circuit switching and packet switching

C370S392000

Reexamination Certificate

active

06801525

ABSTRACT:

TECHNICAL FIELD
This invention relates to telecommunications packet switches, and more specifically, to packet switches which perform a routing function.
PROBLEM
An Internet protocol packet (Datagram) router accepts input packets from many sources and headed for many destinations. Each packet has a header that includes a destination address. Since many of the destinations are frequently encountered in many packets, a router maintains, for a list of frequently used destination addresses, the identity of the output port of the router which is currently being used for routing packets toward that destination. In prior art packet routers, a content addressable memory is used for storing the output port corresponding to the most frequently encountered destination addresses. When this content addressable memory is accessed with the identity of a destination address, if the content addressable memory finds a match between that address and one of its entries, it will provide directly or indirectly the identity of the port to which the packet should be routed. For somewhat less frequently used addresses, a second level memory is provided which stores these destination addresses and the corresponding port identifications. The second level memory can be searched using techniques such as a hash access to find any particular entry.
If no entry is found in either the content addressable memory or the second level memory, a query is sent to neighboring Internet protocol routers to see if they have stored this destination address, and if so, to get some information as to how a packet to that destination address is to be routed. If this query fails, then the packet is sent to a backbone router which has access to a still larger set of destination addresses. Finally, if all else fails, the packet is simply discarded. The large variation in time required to process different packets results in a variation of delay in passing through a router. Further, the total throughput of a router is significantly decreased by the occasional hard-to-route packet.
The design of Internet protocol packet routers therefore presents two types of challenges. First, a simple technological challenge is to process the large number of packets that arrive every second in each module of a router. Second, there is a vast difference in the amount of processing required for packets whose identity is stored in the content addressable memory and which, therefore, can be processed very rapidly, and the packets which require much more extensive data processing. Once the technological problem of handling an adequate number of packets whose destination addresses are known has been solved, the remaining problem is how to process the remaining packets. A problem of the prior art is that there is no sound economic solution to the problem of processing such packets in an Internet protocol router or in any other router which processes data packets having a large number of different destination addresses.
SOLUTION
The above problem is alleviated in a major way in accordance with Applicants' invention, wherein a packet router such as an Internet protocol packet router has two kinds of routing modules: a simple routing module capable of routing packets whose addresses are stored in rapidly accessible memory, and which can, therefore, route such packets based on the result of this rapid memory search, and a default router module, which receives all other packets from the first type of routing modules and processes these packets. Advantageously, the default router module can have a very large memory, a sophisticated processing complex for processing such packets and for handling overall router functions, such as controlling the updating of the routing tables of the simpler routing modules, and can have a large buffer for storing the packets that it is processing during the time that queries to other routers are being made.
Advantageously, the simple routing modules can be designed to handle a very large number of packets without being concerned that a flurry of packets for which they have no routing information will swamp their ability to handle the bulk of their packets; packets for which they have no routing information are simply sent to the default router module for processing by that module. Advantageously, the overflow load from all of the simple routing modules is directed to the default routing module so that if one of the simple modules has an unusually large number of packets which it cannot process, (i.e., packets for which a destination port has not been stored in the router module), the default router can take advantage of the fact that not all of the simple modules are sending a heavy load simultaneously.
Since there is only one, or at most, a small number of default modules, the expense of the default module can be much higher and a more sophisticated processing complex can be provided for that default module without making the entire router excessively expensive.
In accordance with the preferred embodiment, the default module(s) control the updating of the forwarding tables of the simple modules.


REFERENCES:
patent: 5740175 (1998-04-01), Wakeman et al.
patent: 5938736 (1999-08-01), Muller et al.
patent: 6069895 (2000-05-01), Ayandeh
patent: 6157644 (2000-12-01), Bernstein et al.
patent: 6396833 (2002-05-01), Zhang et al.

Affiliated with

Also associated with

Rating

Internet protocol packet router does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Internet protocol packet router, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Internet protocol packet router will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3288561