Tècniques de processament de text pel disseny d'algoritmes de baixa complexitat

Els grafs de Cayley (CG, per les seves sigles en anglès) són una representació geomètrica de grups algebraics. Aquests grafs han estat utilitzats com topologies d'una gran varietat de xarxes de comunicacions, com ara xarxes d'interconnexió de processadors, xarxes sense fils de sensors, xarxes de centres de dades, etc. Això és principalment per les seves propietats de transitivitat de node, connectivitat d'enllaç i baixa distància mitjana entre nodes que fan que xarxes de mides molt grans tinguin un bon rendiment i siguin robustes.
En aquest treball d'investigació s'utilitzen tècniques de processament de text junt amb SASs per a dissenyar algoritmes de baixa complexitat que trobin: el camí més curt, els camins mínims, els camins de longitud limitada, els K camins més curts, els camins disjunts, i el camí més curt que exclou un conjunt de nodes i enllaços. Amb base a aquests algoritmes s'ha proposat un esquema d'encaminament genèric per a CGs que té baixa complexitat d'espai i temporal, garanteix el lliurament de paquets, i proveeix: encaminament mínim, diversitat de camins i tolerància a fallades.
Tant l'esquema d'encaminament com els algoritmes de cerca de camins proposats són avaluats mitjançant una anàlisi de complexitat i una comparació amb les propostes més modernes en encaminament genèric per a CGs. També s'inclou un marc teòric per estudiar i resoldre problemes relacionats amb la cerca de camins i encaminament en CGs, des d'un enfocament de processament de text, i una anàlisi de les propietats topològiques dels CGs i el seu impacte en el rendiment i la robustesa de xarxes que els utilitzen com a topologia.

Lectura de la tesi: 17/05/2019