M.Sc Student | Guez Dan |
---|---|

Subject | Scheduling Time-Constrained Communication in Input Queued Switches |

Department | Department of Computer Science |

Supervisor | Mr. Adi Rosen |

We consider the problem
of packet-mode scheduling of input queued switches. Packets have variable
lengths, being divided into cells of unit length. Each packet arrives to the
switch with a given deadline by which it must traverse the switch. A packet
successfully passes the switch if the sequence of cells comprising it is *contiguously*
transmitted out of the switch before the packet's deadline expires. A packet transmission
may be preempted and restarted from the beginning later. The scheduling policy
has to decide at each time unit which packets to serve. The problem is online
in nature, and thus we use competitive analysis to measure the performance of
our scheduling policies.

First we consider the
case where the goal of the switch policy is to maximize the total number of
successfully transmitted packets. We derive two algorithms achieving the competitive
ratios of *2^(2*sqrt(log L)) +1)* and *N+1*, respectively, where *L*
is the ratio between the longest and the shortest packet length and *N* is
the number of input/output ports. We also show that any deterministic online
algorithm has competitive ratio of at least *min{log L +1,N)*.

Then we study the general case in which each packet has an intrinsic value representing its priority, and the goal is to maximize the total value of successfully transmitted packets. We derive an algorithm which achieves a competitive ratio of $2\kappa+2\sqrt{\kappa+1/2}+\frac{2\kappa+\sqrt{\kappa+1/2}+1}{\sqrt{\kappa+1/2}}+3$, where $\kappa$ is the ratio between the maximum and the minimum value per cell.

We complement our results by studying the offline version of the problem, which is NP-hard. We give a pseudo-polynomial $3$-approximation algorithm for the general case and a %strongly polynomial $3$-approximation algorithm for the case of unit value packets.