AN ALGORITHM FOR SUBOPTIMAL ROUTEING IN SERIES-PARALLEL QUEUING-NETWORKS

The optimal routeing problem of maximizing system throughput in series -parallel networks with finite buffers is studied in this paper. The p roblem is extremely difficult to solve since closed form expressions a re not easily constructed for throughput in finite networks. A piece-w ise linear upper bound on the throughput of a tandem network is used t o develop a throughput approximation in series-parallel networks. Base d on this approximation we are able to specify a suboptimal range for routeing probabilities at each junction in the network as a function o f the arrival rate to this junction. We also specify a unique value fo r the routeing probability at each junction, independent of the arriva l rate to that junction. We then construct an O(N) algorithm to analys e general series-parallel networks with more than one junction and spe cify the sub-optimal routeing probabilities at each junction.