De la probabilité de creuser un tunnel

Un tunnel est une portion d'un chemin ou un protocole de communication est encapsule dans un autre. Les tunnels sont de plus en plus presents dans les reseaux. Ils sont utilises pour la securite, l'interoperabilite, les reseaux virtuels, etc. Un chemin contenant un tunnel doit etre faisable, c'est-a-dire qu'il doit respecter l'ordre des encapsulations et des desencapsulations, parfois imbriquees. Les algorithmes de calcul de chemins avec prise en compte de tunnels ne sont pas les memes que dans un reseau classique. Afin de tester ces algorithmes, il serait utile de disposer d'un generateur de topologies aleatoires avec tunnels. Ce generateur devra produire des topologies ayant certaines caracteristiques (par exemple, que la probabilite qu'un chemin soit faisable soit un parametre p quelconque). Il se trouve que ce probleme est lie aux chemins de Dyck et de Motzkin en combinatoire. En effet, une encapsulation peut etre vue comme un pas montant et une desencapsulation peut etre vue comme un pas descendant. La question qui se pose est donc de savoir quelle est la probabilite qu'un chemin de Dyck ou de Motzkin ait certaines proprietes. Dans ce travail, en utilisant des outils de combinatoire analytique, nous donnons la probabilite qu'un chemin soit faisable en fonction de la distribution des encapsulations et des desencapsulations sur les sommets.