Emulating output queued behavior in a virtual output queue switch

A non-transitory computer-readable storage medium comprising instructions for causing one or more programmable processors to:

• receive time of arrival information associated with one or more network packets to be forwarded from virtual output queues (VOQs) of one or more ingress forwarding units, the VOQs associated with a first egress forwarding unit, the time of arrival information corresponding to an approximate time of arrival of the network packet at the ingress forwarding unit of the VOQ in which the network packet is stored;
• determine, based on the time of arrival information, a device resident time for one or more of the network packets stored at the head of the VOQs associated with the first egress forwarding unit;
• discard the network packets stored at the head of the VOQs if the network packets have device resident times greater than a maximum resident time;
• request, from one of the VOQs associated with the first egress forwarding unit and based on the device resident times, the network packet with the longest device resident time;
• and
• receive, at the output queue of the egress PFE of the first egress forwarding unit, the network packet with the longest device resident time.

In a device having ingress packet forwarding engines (PFEs) and egress PFEs, wherein each ingress PFE includes a virtual output queue (VOQ) associated with an output buffer of the egress PFE, a method comprising:

• determining, at a scheduler of the egress PFE, a device resident time for each network packet stored at the head of one of the VOQs associated with the output buffer of the egress PFE, wherein determining includes receiving, from each ingress PFE, information related to time of arrival, at the ingress PFE, of network packets stored in the VOQ of the ingress PFE;
• determining a longest device resident time from the device resident times of the network packets stored at the head of the VOQs associated with the output buffer of the egress PFE;
• if the longest device resident time is greater than a maximum device resident time, discarding one or more network packets stored at the head of one or more of the VOQs associated with the output buffer of the egress PFE;
• and
• requesting, at the scheduler of the egress PFE, that the network packet with the longest device resident time be transmitted from the VOQ in which the network packet is stored to the output buffer of the egress PFE.

A non-transitory computer-readable storage medium comprising instructions for causing one or more programmable processors to:

• determine a device resident time for each network packet stored in one of the virtual output queues (VOQs) associated with the output queue of the egress forwarding unit, wherein determining includes receiving, from each ingress forwarding unit, information related to time of arrival, at the ingress forwarding unit, of network packets stored in the VOQ of the ingress forwarding unit;
• discard the network packets stored at the head of the VOQs if the network packets have device resident times greater than a maximum resident time;
• determine a longest device resident time from the device resident times of the network packets stored at the head of the VOQs;
• and
• request, at a scheduler of the egress forwarding unit, that the network packet with the longest device resident time be transmitted from the VOQ in which the network packet is stored to the output buffer of the egress forwarding unit.

A network device comprising:

• a switch fabric;
• and
• a plurality of forwarding units, each forwarding unit connected to the switch fabric, wherein two or more ingress ones of the forwarding units forward network packets to an egress one of the forwarding units via the switch fabric, the egress forwarding unit including a scheduler and an output queue attached to a network interface, each ingress forwarding unit including a Virtual Output Queue (VOQ) connected to the output queue and a VOQ manager for the VOQ, each VOQ comprising a logical queue associated with the output queue of the egress forwarding unit, each VOQ manager determining when to discard network packets stored in its VOQ,
• wherein the scheduler receives time of arrival information for network packets stored at the head of the VOQs, determines, based on the time of arrival information for each network packet, a device resident time for the network packets stored at the head of the VOQs, determines if the network packets stored at the head of the VOQs have device resident times greater than a maximum resident time and conveys that information to the VOQ manager of one or more of the VOQs connected to the output queue;
• wherein the VOQ managers that receive the information discard the network packet at the head of their associated VOQ, and
• wherein the scheduler requests, from one of the VOQs and based on the device resident times, the network packet with the longest device resident time.