How does a router/switch know which queue a packet should be put in?

Question

In weighted fair queuing, how does the router/switch/multiplexer know which queue to put a packet into? For example does it read the headers of each packet to find out the sender and the intended application?

For example how does "classify arrivals" work?

Answer 1

A network device generally has 3-4 queues for traffic handling. WFQ is not strictly speaking a queuing algorithm, it's a egress traffic scheduling algorithm. It determines how the traffic placed in different queues is sent out of the device. The way fair queuing works is that traffic placed on different queues is served in order, for example in case of three queues they would be served 1-2-3-1-2-3 and so on. We can give double weight for queue 1, in which case the queues would be served 1-1-2-3-1-1-2-3.

"Classifying arrivals" refers to the way ingress packets are handled within the device itself. Generally network devices uphold the existing priority of the traffic, placing incoming packets to appropriate egress queue based on what priority it has. However in every case the device actually looks into the frame itself, either the L2 or L3 header.

Ingress frames can be prioritized several different ways. We can use the ingress interface, or determine it by Layer 2 frame information such as 802.1p/Q priority (Class of Service, CoS), L2 MAC address or VLAN ID. This is how a L2 device such as a switch works. For example the packet may arrive in a specific "Voice" VLAN (used for VOIP traffic), in which case it will be placed in high priority egress queue. Or the frame header's 802.1Q VLAN Tag may contain a 3-bit PCP (Priority Code Point) field which determines which queue the packet is placed in.

A router as L3 device would look at the IP packet header in the frame payload. There's a wide range of ways to prioritize the traffic, from the incoming interface to the IP address, subnet, TCP/IP port number and so on. Most commonly used is probably DiffServ (Differentiated Services). This uses 6-bit Differentiated Services Code Point (DSCP) in 8-bit DS field in the packet header. This allows much more granulated priority categorization, in theory 64 (2^6) different priority levels. In practice however most networks use commonly defined per-hop behaviors:

• Default PHB - typically best-effort traffic, used for normal PC data traffic
• Expedited Forwarding (EF PHB) - used for low-loss, low-latency traffic, for example VOIP
• Assured Forwading (AF PHB) - ensures delivery under certain pre-defined conditions
• Class Selector PHB - maintains backward compatibility with previously used ToS (Type of Service) field in IPv4 header

More in-depth descriptions how traffic priorization works can be found for example in Wikipedia. Type of Service, Class of Service, Quality of Service, 802.1p and 802.1Q are good starting points.

Answer 2

In queuing algorithms such as weighted fair queuing, how does the router/switch/multiplexer know which queue to put a packet into?

... For example how does "classify arrivals" work?

When wfq is enabled on an interface, the router builds a table of flows, and prioritizes low-bandwidth flows over high-bandwidth flows. By prioritizing flows, it classifies lower bandwidth flows into a higher priority queue; for more detail, see Cisco's QoS config guide:

WFQ provides traffic priority management that automatically sorts among individual 
traffic streams without requiring that you first define access lists. WFQ can 
also manage duplex data streams such as those between pairs of applications, 
and simplex data streams such as voice or video. There are two categories of WFQ 
sessions: high bandwidth and low bandwidth. Low-bandwidth traffic has effective 
priority over high-bandwidth traffic, and high-bandwidth traffic shares the 
transmission service proportionally according to assigned weights.

When WFQ is enabled for an interface, new messages for high-bandwidth traffic 
streams are discarded after the configured or default congestive messages threshold 
has been met. However, low-bandwidth conversations, which include control message 
conversations, continue to enqueue data. As a result, the fair queue may occasionally 
contain more messages than its configured threshold number specifies.

With standard WFQ, packets are classified by flow. Packets with the same source IP 
address, destination IP address, source TCP or User Datagram Protocol (UDP) 
port, or destination TCP or UDP port belong to the same flow. WFQ allocates 
an equal share of the bandwidth to each flow. Flow-based WFQ is also called 
fair queueing because all flows are equally weighted.

One should also remember that QoS disciplines never kick in until there is congestion on the interface. Finally, if possible, it's a good idea to manage queue depth with wred for all the reasons outlined in this question