AuthorsR. Lorentzen
TitleSome Tools for Finding Deadlock-free Routings in Computer Networks Based on Linear Programming and Extensions
AfilliationCommunication Systems
Project(s)No Simula project
Publication TypeTechnical reports
Year of Publication2016
PublisherSimula Research Laboratory
Place PublishedFornebu, Oslo

We consider an uncapacitated directed network where the nodes are

switches or CPU-s and the arcs are channels going from a port on one

switch/CPU to a port on another switch/CPU. The ports are assumed

to have sufficient bandwidth capacity to accommodate any traffic that

one may choose to route through them. There may be more than one

channel in each direction connecting two ports, and each physical chan-
nel may have subchannels called virtual channels. We describe several

approaches based on linear programming and some other approachesfor

finding deadlock-free short routes for a given set of required connections

between pairs of CPU-s. Some routes may have been specified before-
hand. We also consider extension of the models to reflect limits on the

maximal use of a single channel. Then we describe an approach to reroute

requirements when a single channel fails. Finally we look into the problem

of coupling together two or more networks where deadlock-free routings

exist for each subnetwork.

Keywords: directed networks, deadlocks, linear programming

Citation Key25119