Predictive routing table cache population

Details Predictive routing table cache population Predictive routing table cache population

2000-08-07

2004-11-09

Patel, Alit (Department: 2664)

Multiplex communications

Data flow congestion prevention or control

Control of data admission to the network

C370S234000

Reexamination Certificate

active

06816457

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to telecommunications and computer networks in general, and, more particularly, to the design of a router for use in a packet network.
BACKGROUND OF THE INVENTION
In a packet network, the finite speed of light and the finite speed at which a router can operate precludes the traversal of a packet from one side of the network to another instantaneously. Therefore, there is always some delay between when a transmitting network terminal transmits a packet and when the receiving network terminal receives the packet.
In some cases, this delay is unimportant. For example, some data (e.g., most e-mail messages, etc.) is not perishable or highly time-sensitive and the sender and receiver of the data might consider it unimportant whether the packet takes 5 milliseconds, 5 seconds or even 5 minutes to traverse the network. In contrast, other data (e.g., voice, full-motion video, instant messaging, etc.) is perishable or highly time-sensitive, and, therefore, the sender and receiver of the data might consider it very important that the packets traverse the network quickly.
When packet networks were originally conceived and designed and constructed, little or no consideration was given to ensuring that a fixed number of packets could be sent across a packet network with a maximum delay. Average delays were considered, and packet networks were engineered to consider average delays, but little or no consideration was given to engineering the maximum delay. Increasingly, however, packet networks are being considered for carrying time-sensitive data for applications such as Internet telephony and television broadcasting.
Perhaps the most significant source of delay in a packet network is due to the speed at which the routers operate. It is well known in the prior art how to make and use fast routers, but their extra speed comes at a price, and, therefore, it is not typically economical to build them. In fact, it is well known in the prior art how to trade cost for performance when designing and building routers.
Nevertheless, the need exists for a router that is more powerful than comparatively expensive routers in the prior art.
SUMMARY OF THE INVENTION
The present invention is a router and routing table cache population technique that avoids some of the costs and disadvantages associated with techniques in the prior art. In particular, the illustrative embodiment routes packets through it more quickly than comparatively expensive routers in the prior art.
The present invention recognizes that a router with a small routing table cache can be fast if the routing table cache has a high hit ratio, and that a high hit ratio can be achieved by predicting which entries will be needed in the routing table cache in the future and by populating the routing table cache with those entries before they are needed. In accordance with the illustrative embodiment of the present invention, this is accomplished by: (i) building one or more temporal models of the occurrence of needed entries based on empirical data, (ii) by using the temporal model(s) to predict which entries are most likely to be needed at some time in the future, and (iii) by populating the router table cache with those entries before they are needed.
The illustrative embodiment of the present invention comprises: an input port for receiving a succession of packets, wherein each of the packets comprises a destination address; a plurality of output ports; a switching fabric for interconnecting the input port to each of the plurality of output ports; a processor or building a temporal model of the occurrence of the destination addresses at the input port, for populating the routing table cache based on the temporal model and at least one entry that is stored in a routing table, and for routing at least one of the packets from the input port to one of the output ports through the switching fabric based on the entry that is stored in the routing table cache.


REFERENCES:
patent: 5488608 (1996-01-01), Flammer, III
patent: 6118760 (2000-09-01), Zaumen et al.

Affiliated with

Also associated with

Rating

Predictive routing table cache population does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Predictive routing table cache population, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Predictive routing table cache population will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3291766