Method and Apparatus for Predicting Characteristics of Incoming Data Packets to Enable Speculative Processing To Reduce Processor Latency

• US 20090073974A1
• Filed: 08/04/2008
• Published: 03/19/2009
• Est. Priority Date: 08/22/2001
• Status: Active Grant

• Current Assignee: ARM Finance Overseas Limited (SoftBank Group Corp.)
• Original Assignee: MIPS Technologies Incorporated (Wave Computing, Inc.)
• Inventors: Musoll, Enrique
• Granted Patent: US 8,077,734 B2
• Time in Patent Office: Days
• US Class Current: 370/389
• 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-20. -20. (canceled)

21. In a packet router, a packet prediction control mechanism for initiating a prediction of a future data packet, the packet prediction control mechanism comprising:

a component predictor to compute a predictable component based on previously received data packets;

a speculative packet generator for constructing a speculative packet portion based on the computed predictable component; and

logic to compare the speculative packet portion with the future data packet upon receipt, the logic adapted to either use the computed predictable component in the speculative packet portion or to invalidate the predictable component.

22. The packet prediction control mechanism of claim 21, wherein processing time for an arriving packet is reduced when the computed predictable component is accepted.

23. The packet prediction control mechanism of claim 21, wherein the speculative packet is associated with the predicted data packet upon arrival.

24. The packet prediction control mechanism of claim 21, wherein the speculative packet portion is abandoned if the logic determines that the computed predictable component of the speculative packet portion does not agree with a corresponding component of the future data packet upon arrival.

25. The packet prediction control mechanism of claim 21, wherein if the logic determines that the computed predictable component of the speculative packet portion does not agree with a corresponding component of the future data packet upon arrival, the selected predictable component of the speculative data packet is abandoned and other predictable components are retained.

26. The packet prediction control mechanism of claim 21, wherein packet prediction is initiated by detection of idle processor time.

27. The packet prediction control mechanism of claim 21, wherein packet prediction is initiated upon receipt of a real data packet.

28. The packet prediction control mechanism of claim 21, further comprising:

a plurality of component predictors, each of which is dedicated to computing a predictable component, wherein at least one of the plurality of component predictors may be selectively disabled.

29. The packet prediction control mechanism of claim 21, further comprising:

a plurality of component predictors, each of which is dedicated to computing a predictable component for a selected one of a plurality of predictable components, wherein at least one of the plurality of component predictors is enabled.

30. The packet prediction control mechanism of claim 21, further comprising:

at least one input port for receiving data packets; and

at least one output port for sending out speculative data packets.

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

initiating speculative processing on a next packet based on predicted attributes during slow periods inherent to the packet router;

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

predicting packet characteristics for each packet flow; and

beginning data packet processing before the future data packet actually arrives at the packet router.

32. The method of claim 31, wherein attempting predictions for every next future packet is based on a last known history data.

33. The method of claim 32, wherein a prediction is invalidated if its comparison with historical data detects that the prediction would likely be in error.

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

35. The method of claim 32, wherein predictions for every next future packet are attempted based on a consultation with a history and wherein the predictions are not invalidated prior to arrival of the actual packet that the prediction is based on.