"Résolution de la contention dans les canaux à accès multiples"

Résumé :

Un canal ``à accès multiples'' (multiple-access channel en anglais) est un canal de communication sans contrôle, tel Ethernet. Les utilisateurs communiquent en envoyant des messages sur le canal. Si deux ou plusieurs utilisateurs envoient des messages en même temps, les messages interfèrent les uns avec les autres (ils entrent en collision) et les messages ne parviennent pas à être transmis. Pour parer à ces collisions on utilise un protocole de gestion de la concurrence : après une collision, chaque utilisateur en cause doit attendre avant de renvoyer son message qu'une certaine durée tirée au hasard par le protocole soit passée.

Informellement, un protocole est dit ``stable'' si les messages parviennent à être délivrés sans accumulation de phases d'attente (la définition donnée pendant le cours est plus précise).

On ne connaît pas encore très bien quels protocoles sont stables et lesquels ne le sont pas. Après une revue des résultats connus et des méthodes qui sont utilisées dans ce domaine, des problèmes ouverts seront exposés.
 

Abstract:

A multiple-access channel is an uncontrolled communication channel such as an Ethernet. Users communicate by sending messages to the channel. If two or more users simultaneously send messages, then the messages interfere with each other (collide), and the messages are not transmitted successfully. The users use a contention-resolution protocol to resolve collisions. Thus, after a collision, each user involved in the collision waits a random amount of time (which is determined by the protocol) before re-sending.

Informally, a protocol is said to be "stable" if the messages get delivered as they arrive, without a big backlog building up. (I'll be more precise about this in the talk.)

It is still not fully understood which protocols are stable and which are not. I will survey the known results and the methods which are used in the area, and will discuss open problems.
 

Related survey: Notes on Contention Resolution