Switching algorithms

Buffering strategies are required for switches to cope with output port contention.

Output queues

• Input frames are immediately forwarded to output ports
• The size of each output queue must be equal to the number of input ports
• High performance memory must be used to store the output queues
• Underused output queues lead to inefficient usage of expensive memory

Input queues

• Input frames are stored in a FIFO queue at each input port
• Input frames are labelled in the FIFO queue with the output port
• Each input port has one input queue
• The size of each input queue may be different than the number of output ports
• High performance memory must be used to store the input queues
• No risk of underused input queues

Take-a-ticket scheduling algorithm used with input queues

1. Using a separate control bus, each input port issues a request to output ports for a connection
2. Using a separate control bus, each output port issues a grant ticket counter to the input port which has been selected to transmit a frame
3. The switch fabric enables the connections that have been granted tickets
4. Each input port that received a grant ticket transmits data to the output port that issued the grant ticket

Head of line (HOL) blocking with input queues

• Blocking caused by contention for the same output port by multiple input queues
• Statistical analysis of uniform traffic patterns reveal that HOL blocking limits the throughput to 58.6%
• The throughput could be worse with non-uniform traffic patterns

Virtual output queues (VOQ) are used to reduce HOL blocking with input queues

• Each input port has multiple logical FIFO output queues that correspond to the number of output ports
• Input frames are stored in a queue at each input port that corresponds to its destination output port
• Reduces HOL blocking by making more frames available for forwarding for each input port in the same clock cycle
• The size of each VOQ may be different than the number of output ports
• High performance memory must be used to store the input queues
• Lower risk of underused output queues

Virtual output queues (VOQ) with support for traffic priority

When using FIFO queues, separate queues are required for priority class.

Scheduling the transfer of frames across the switch fabric is a bipartite graph matching problem

• Vertices in the set on the left side represent input ports
• Vertices in the set on the right side represent output ports
• Edges connect one input port to one output port
• During each switch fabric data transfer slot, the matching problem is the task of selecting the maximum number of edges which do not share a common vertex (i.e. port or queue)
• Algorithms to solve the matching problem must consider the following issues:
  • Efficiency as expressed by the number of edges
  • Fairness as expressed by the coverage of vertices selected
  • Cost as expressed by the complexity of the hardware required to implement the algorithm

Maximum matching algorithms for bipartite graphs

Maximum weight matching algorithms

• Select the maximum number of edges that do not share a common vertex and has the highest total weight
• Longest Queue First (LQF) uses the number of frames in the queue as the weight of the edge
• Oldest Cell First (OCF) uses the waiting time of the head of line frame in the queue as the weight of the edge

Maximum size matching algorithms

• Select the maximum number of edges that do not share a common vertex
• This is a special case of maximum weight matching when the weight of each edge is 1
• Slightly faster than LQF or OCF, but, may lead to starvation (some input vertices not used)

Maximal matching algorithms for bipartite graphs

• Select the maximum number of edges by adding edges iteratively, without removing edges selected earlier in previous iterations
• Each iteration is simpler to implement in hardware, but, requires multiple iterations to find a matching graph
• Maximal match algorithms tend to select less edges than maximum match algorithms, which results in slightly lower throughput
• Two important maximal matching algorithms are:
  • Parallel iterative matching (PIM) algorithm
  • Iterative Round-Robin with SLIP (iSLIP) algorithm