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

• US 7,415,531 B2
• Filed: 08/22/2001
• Issued: 08/19/2008
• Est. Priority Date: 08/22/2001
• Status: Expired due to Term

• Current Assignee: ARM Finance Overseas Limited (SoftBank Group Corp.)
• Original Assignee: MIPS Technologies Incorporated (Wave Computing, Inc.)
• Inventors: Musoll, Enrique
• Primary Examiner(s): Cardone, Jason
• Assistant Examiner(s): CHOUDHURY, AZIZUL Q
• Application Number:
  US09/935,446
• Publication Number:
  US 20030041168A1
• Time in Patent Office: 2,554 Days
• Field of Search: 709/238, 370/94.1, 364/900
• US Class Current: 709/238
• 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. A packet buffering system for predictively processing data packets in a data packet network, the data packets associated with a plurality of data flows, the data flows from of a plurality of protocols, the system comprising:

at least one input port for receiving data packets from a plurality of sources, wherein the received data packets arrive from the plurality of data flows, interspersed;

at least one output port for sending out data packets to a plurality of destinations;

a packet predictor, coupled to said at least one input port, for predicting information about a future packet in any one of the plurality of data flows based on history of previously received packets from the plurality of data flows, said history stored in a memory coupled to said packet predictor;

a plurality of queues for storing packets received from said plurality of sources, and for storing said predicted information about said future packet;

direction logic, coupled to said packet predictor, for generating a Packet ID for said future packet, wherein said Packet ID is stored in one of said plurality of queues;

buffer logic, coupled to said packet predictor, for accessing said memory and for validating said predicted information about said future packet based on said access to said memory; and

a processing core, coupled to said plurality of queues, wherein if said buffer logic validates said predicted information, notification is made to said direction logic which passes said Packet ID for said future packet to said processing core to initiate speculative processing.

2. The system of claim 1 wherein the data packet network is the Internet network.

3. The system of claim 1 wherein the packet predictor utilizes a history record periodically updated by the system, to generate predicted data.

4. The system of claim 3 wherein the history record comprises characteristics of recently received data packets.

5. The system of claim 4 wherein the history record further comprises results of past predictions.

6. The system of claim 1 wherein said packet predictor predicts specific characteristics, comprising one or more of packet type, packet flow identification, sender information, destination information, and packet size for said future packet.

7. The system of claim 1 comprising a packet router.

8. The system of claim 1 comprising a data server.

9. A packet predictor system for predicting information about future packets to be received within a data packet processor, the future packets associated with a plurality of data flows, the data flows associated with a plurality of protocols, the predicted information being processed by a processing core prior to the future packets being received, the processing reducing latency in routing the future packets to their destinations, the system comprising:

an input for receiving information about non-predicted packets received for processing;

a packet predictor, coupled to said input, for predicting information about the future packets, based upon the information received about the non-predicted packets;

a plurality of queues, coupled to said input and said packet predictor, for storing the predicted information;

direction logic, coupled to said packet predictor, for generating a Packet ID for said future packet, wherein said Packet ID is stored in one of said plurality of queues; and

a processing core, coupled to said plurality of queues, for processing the predicted information before the future packets are received by said input;

wherein by processing the predicted information before the future packets are received, latency for delivering the future packets to an output is reduced.

10. The packet predictor system of claim 9 wherein the data packet processor comprises a data router operating on the Internet network.

11. The packet predictor system of claim 9 comprising a history record consulted each time a prediction is made.

12. The packet predictor system of claim 11 wherein the history record comprises history of real packets received and processed.

13. The packet predictor system of claim 11 wherein the history record comprises history of prediction and results of the predictions.

14. The packet predictor system of claim 9 wherein the history record is stored in a memory accessible to the system.

15. The packet predictor system of claim 9 wherein said packet predictor predicts specific characteristics, comprising one or more of packet type, packet flow identification, sender information, destination information, and packet size.

16. The packet predictor system of claim 9 wherein the data packet processor comprises a data server.

17. A method for reducing latency in packet processing within a packet processor, comprising the steps of:

receiving packets associated with a plurality of data flows, the data flows from a plurality of protocols, developing and storing a history of packet information from the received packets;

predicting future information about future packets from the stored history;

validating the future information about the future packets responsive to the stored history, and if validated;

generating a Packet ID for said future packet and storing said Packet ID in one of a plurality of queues;

processing the future information about the future packets before the future packets are received;

wherein by processing the future information about the future packets before the future packets are received, latency in delivering the future packets to their destinations is reduced; and

wherein the information comprises one or more of packet type, packet flow identification, source information, destination information, and packet size.

18. The method of claim 17 wherein the packet processor is coupled with a data packet network.

19. The method of claim 18 wherein the data packet network is the Internet network.

20. The method of claim 17 comprising the step for maintaining a history of either or both of packets actually received and results of prior predictions.

21. The method of claim 17 wherein said step of processing is abandoned if it is determined not to agree with the real data once it arrives.

22. The method of claim 17 wherein in, if some of the results from processing the predicted future information are wrong they are abandoned, and results which are corrected are retained, to reduce processing for an arriving packet based on the prediction.