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

Scheduling algorithms



Take a ticket scheduling algorithm


  1. Each input port issues one REQUEST to the output port for which it has a queued frame.
  2. Each output port reviews all requests received and randomly GRANTS to the lowest input port.
  3. Each input port reviews all grants received and randomly ACCEPTS the lowest output port.







Parallel iterative matching (PIM) scheduling algorithm


  1. Each unmatched input port sends a REQUEST to every output port for which it has a queued frame.
  2. Each unmatched output port reviews all requests received and randomly GRANTS to the lowest input port.
  3. Each unmatched input port reviews all grants received and randomly ACCEPTS the lowest output port.







Iterative round-robin with SLIP (iSLIP) scheduling algorithm


  1. Each unmatched input port sends a REQUEST to every output port for which it has a queued frame.
  2. Each unmatched output port reviews all requests received and GRANTS to the LOWEST input port that is equal to or greater than its current GRANT POINTER.
  3. Each unmatched input port reviews all grants received and ACCEPTS the LOWEST output port that is equal to or greater than its current ACCEPT POINTER.
  4. The grant pointer of output ports that received a frame in the first iteration are INCREMENTED to one location AFTER the granted input port number using modulus N (where N is the number of the input ports).
  5. The accept pointer of input ports that transmitted a frame in the first iteration are INCREMENTED to one location AFTER the accepted output port number using modulus N (where N is the number of the output ports).







iSLIP is the current industry standard


  1. It is cost effective to implement the algorithm in hardware.
  2. Its worst performance is no worse than other algorithms and its best performance under optimal traffic conditions can reach 100% throughput.
  3. The most recently made connection is assigned the lowest priority, therefore, no port is starved because each port only waits at most N-1 cycles before it receives a grant, where N is the number of input ports.
  4. The algorithm can be adjusted to handle priority traffic.