טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
M.Sc Thesis
M.Sc StudentAsa Michael
SubjectOptimal Guaranteed-Routing Network
DepartmentDepartment of Electrical Engineering
Supervisor Professor Isaac Keslassy
Full Thesis textFull thesis text - English Version


Abstract

During the design of a network we face many dilemmas regarding the tradeoff between its performance and its cost. One of these dilemmas revolves around the bandwidth of the links. High bandwidth on the links enables to increase the data transmission throughput and decrease the delay. This, on one hand, makes communication faster and improves the performance of the whole system. On the other hand, high bandwidth usually raises the cost of each link, hence, the cost of the network. This research suggests an algorithm to minimize the bandwidth on the links while maintaining a guaranteed throughput between all endpoints. 


Measuring the cost of each network depends on its application. Each application requires different characteristics from the network and defines different cost functions. Nevertheless, usually the cost function is monotonic with the bandwidth of the links, i.e. high bandwidth means high cost. For example in a computer network, we wish to increase throughput and decrease delay. This can be achieved by adding more cables, or in other words increasing the bandwidth of the links. In this case the cost function is simply the cost of the cables. Another example comes from the NoC (Network on Chip). In this case the designer strives, on the one hand, to lower the frequency of the links, in order to save power. But, on the other hand, lowering the frequency also reduces the throughput of the network. These two examples demonstrate the same need for links with high bandwidth, while minimizing their specific cost.


In this research we will focus on the case of enabling guaranteed throughput, i.e. designing the network such that every endpoint in the network could send and receive a certain rate of data independently of the state of the network. This guarantee will be fulfilled while taking into account the network cost function - minimum usage of link-bandwidth in the case of computer networks or minimum power consumption in the case of NoC. We first find an algorithm that provides a minimum-cost guaranteed routing for all traffic patterns, given some general link-capacity convex cost function. To do so, we show how to compute the total cost for a given routing function, and then how to minimize this cost among all routing functions.