Flexible mesh structure for hierarchical scheduling

A scheduling engine for scheduling packet transmission in a network communications device, comprising:

• a two dimensional memory mesh structure for storing a grouping of packets, the two dimensional memory mesh structure containing N columns, each column containing M packets, each of N and M being greater than 1;
• N sorters, each sorter configured to select a column best packet from the packets in each column;
• a memory structure containing a final row for storing N packets output from the N sorters;
• and
• a final best packet sorter configured to select a final best packet from the N packets in the final row and to promote the final best packet from the grouping of packets.

A system comprising:

• a network interface to facilitate communication with a network;
• and
• a network processor interfacing the network interface, the network processor including at least one scheduling engine for scheduling packet transmission, each scheduling engine including:
• a two dimensional memory mesh structure for storing a grouping of packets, the two dimensional memory mesh structure containing N columns, each column containing M packets, each of N and M being greater than 1;
• N sorters, each sorter configured to select a column best packet from the packets in each column;
• a memory structure containing a final row for storing N packets output from the N sorters;
• and
• a final best packet sorter configured to select a final best packet from the N packets in the final row and to promote the final best packet from the grouping of packets.