Packet forwarding throughput with partial packet ordering
AssigneeCisco Technology, Inc.
InventorsJohn H. Hughes, Jr., Hema Kapadia, Rajiv Kane
Life of this patent
Estimating the term…
Abstract
The present invention describes a system and method of improving packet forwarding throughput in a router by reducing head of line blocking. In one embodiment of the present invention, incoming packets are stored in a packet reorder buffer. The packets are reordered for forwarding while maintaining the order of packets in a distinct flow. Packets belonging to a distinct flow require to be forwarded in the order that the router receives them. Packets from different flows are reordered such that their forwarding order can be different than the order in which they were received. Packets from the same flow are sent out in the same order as the router receives them.
Claims71
A method for routing packets in a router, the method comprising:
- receiving a plurality of packets in a first order;
- storing said plurality of packets in a packet reorder buffer;
- forwarding said plurality of packets in a second order from said packet reorder buffer;
- determining a plurality of hash values using information contained in said plurality of packets;
- storing said plurality of hash values in said packet reorder buffer;
- and
- using said plurality of hash values to determine said second order.
A network element comprising:
- a processor;
- said processor is configured to receive a plurality of incoming packets in a first order;
- separate said plurality of incoming packets into a plurality of subsets of incoming packets, wherein
- said plurality of incoming packets is separated according to
- a plurality of characteristics of said plurality of incoming packets;
- and
- forward said plurality of subsets of incoming packets in a second order.
A network element for routing packets in a router comprising:
- means for receiving a plurality of packets in a first order;
- means for storing said plurality of packets in a packet reorder buffer;
- means for forwarding said plurality of packets in a second order from said packet reorder buffer;
- means for determining a plurality of hash values using information contained in said plurality of packets;
- means for storing said plurality of hash values in said packet reorder buffer;
- and
- means for using said plurality of hash values to determine said second order.
A computer readable medium comprising a set of instructions executable on a computer system, wherein said set of instructions is configured to:
- receive a plurality of packets in a first order;
- store said plurality of packets in a packet reorder buffer;
- forward said plurality of packets in a second order from said packet reorder buffer;
- determine a plurality of hash values using information contained in said plurality of packets;
- store said plurality of hash values in said packet reorder buffer;
- and
- use said plurality of hash values to determine said second order.
Dependencies are inferred from the claim text.