<http://lib.cnfolio.com/ENG653SwitchingAlgorithms>
WAN and VLAN Solutions

Switching algorithms



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




Output queues








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








Virtual output queues (VOQ) are used to reduce HOL blocking with input 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








Maximum matching algorithms for bipartite graphs


Maximum weight matching algorithms







Maximum size matching algorithms






Maximal matching algorithms for bipartite graphs