Method and apparatus for predicting characteristics of incoming data packets to enable speculative processing to reduce processor latency

• US 8,077,734 B2
• Filed: 08/04/2008
• Issued: 12/13/2011
• Est. Priority Date: 08/22/2001
• Status: Expired due to Fees

• Current Assignee: ARM Finance Overseas Limited (SoftBank Group Corp.)
• Original Assignee: MIPS Technologies Incorporated (Wave Computing, Inc.)
• Inventors: Musoll, Enrique
• Primary Examiner(s): Grey, Christopher
• Application Number:
  US12/185,594
• Publication Number:
  US 20090073974A1
• Time in Patent Office: 1,226 Days
• Field of Search: 370229-231, 370/235, 370/252, 370/389, 370/392, 370/395.32, 370/413, 370/428, 709/238, 709/239, 709/240
• US Class Current: 370/428
• CPC Class Codes: H04L 45/00 Routing or path finding of packets in data switching networks routing or path finding in wireless networks H04W40/00

Abstract

A system for processing data packets in a data packet network has at least one input port for receiving data packets, at least one output port for sending out data packets, a processor for processing packet data, and a packet predictor for predicting a future packet based on a received packet, such that at least some processing for the predicted packet may be accomplished before the predicted packet actually arrives at the system. The system is used in preferred embodiments in Internet routers.

Claims

1. In a packet router, a packet prediction mechanism configured to predict a characteristic of a future data packet, the packet prediction mechanism comprising:

a characteristic predictor configured to compute the characteristic of the future data packet based on respective component histories from previously received data packets;

a speculative packet generator configured to construct a speculative packet portion based on the computed characteristic;

an output configured to communicate the speculative packet portion and a Packet identifier (ID) of the future data packet and store the speculative packet portion and the Packet ID in a position in a queue; and

logic configured to compare the speculative packet portion with the future data packet upon receipt, the logic adapted to either use the computed characteristic in the stored speculative packet portion or to invalidate the computed characteristic by storing a characteristic of the received data packet in the position of the queue.

2. The packet prediction mechanism of claim 1, wherein processing time for an arriving packet is reduced when the computed characteristic is used.

3. The packet prediction mechanism of claim 1, wherein the speculative packet portion is associated with the future data packet upon arrival.

4. The packet prediction mechanism of claim 1, wherein the speculative packet portion is abandoned if the logic determines that the computed characteristic of the speculative packet portion does not agree with a corresponding characteristic of the future data packet upon arrival.

5. The packet prediction mechanism of claim 1, wherein if the logic determines that the computed characteristic of the speculative packet portion does not agree with a corresponding characteristic of the future data packet upon arrival, the computed characteristic of the speculative data packet portion is abandoned and the remainder of the speculative packet portion is retained.

6. The packet prediction mechanism of claim 1, wherein packet prediction is initiated by detection of idle processor time.

7. The packet prediction control mechanism of claim 1, wherein packet prediction is initiated upon receipt of the future data packet.

8. The packet prediction control mechanism of claim 1,

wherein the characteristic predictor may be selectively disabled.

9. The packet prediction control mechanism of claim 1, further comprising:

at least one input port configured to receive data packets; and

at least one output port configured to send out speculative data packets.

10. In a packet router, a method for initiating a prediction of a future data packet, comprising:

organizing previously received same-sourced and destined packets into a packet flow;

predicting a packet characteristic for a future data packet in the packet flow;

generating a Packet identifier (ID) for the future data packet and storing the Packet ID in a position of a queue;

generating a speculative packet portion having the predicted packet characteristic;

storing the speculative packet portion in the position of the queue;

comparing the speculative packet portion with the future data packet upon receipt; and

based on the comparing, either;

using the predicted packet characteristic in the stored speculative packet portion, or

invalidating the predicted packet characteristic by storing a characteristic of the received data packet in the position of the queue.

11. The method of claim 10, wherein attempting predictions for the future packet is based on a last known history data.

12. The method of claim 10, wherein the predicted packet characteristic is invalidated if its comparison with historical data detects that the prediction would likely be in error.

13. The method of claim 10, wherein the predicted packet characteristic is invalidated if its comparison with historical data detects that the prediction does not meet a pre-set value threshold.

14. The method of claim 10, wherein the predictions are not invalidated prior to arrival of the actual packet upon which the prediction is based.