Matrice de permutation | EPFL Graph Search

Une matrice de permutation est une matrice carrée qui vérifie les propriétés suivantes :

les coefficients sont 0 ou 1 ;
il y a un et un seul 1 par ligne ;
il y a un et un seul 1 par colonne.

Ainsi : \begin{pmatrix} 1 & 0 & 0 & 0\ 0 & 0 & 1 & 0\ 0 & 0 & 0 & 1\ 0 & 1 & 0 & 0\end{pmatrix} est une matrice de permutation. Propriétés Lien avec le groupe symétrique Les matrices de permutations carrées de taille n sont en bijection avec les permutations de l'ensemble {1,2,...n}. Si σ est une telle permutation, la matrice correspondante est P_\sigma de terme général :\left[P_\sigma\right]{ij}=\delta{i,\sigma(j)}=\begin{cases} 1 & \hbox {si } i=\sigma(j)\ 0&\hbox{sinon.}\end{cases} Cette bijection est un morphisme de groupes : :P_\sigma P_\tau = P_{\sigma \circ \tau}. En utilisant cette identité avec deux permutations inverses l'une de l'autre, on obtient le fait qu'une matrice de permutat

Scheduling Reserved Traffic in Input-Queued Switches: New Delay Bounds via Probabilistic Techniques

Milan Vojnovic

We consider the problem of providing delay bounds to reserved traffic in high-speed input-queued switches. We assume that the matrix of bandwidth demands is known and we use the now standard approach of decomposing this matrix into a convex combination of permutation matrices. Our problem therefore reduces to the problem of constructing a schedule for these permutation matrices. In this paper we derive delay bounds for four algorithms that are based on probabilistic techniques. For each algorithm we first place tokens randomly in continuous time for each permutation matrix. If the

n

th token that appears corresponds to permutation matrix

M_k

then we schedule matrix

M_k

in the

n

th time slot. The algorithms differ in how the random token processes are defined. For two of the algorithms we are able to perform a derandomization so as to obtain deterministic schedules. We show through numerical computation that in many situations the resulting delay bounds are smaller than the previously best-known delay bounds of Chang, Chen, and Huang.

2003

Scheduling Reserved Traffic in Input-Queued Switches: New Delay Bounds via Probabilistic Techniques

Milan Vojnovic