טכניון מכון טכנולוגי לישראל
הטכניון מכון טכנולוגי לישראל - בית הספר ללימודי מוסמכים  
Ph.D Thesis
Ph.D StudentBanner Ron
SubjectMultipath Routing
DepartmentDepartment of Electrical Engineering
Supervisor Professor Ariel Orda
Full Thesis textFull thesis text - English Version


Abstract

Unlike traditional routing schemes that route all traffic along a single path, multipath routing strategies split the traffic among several different paths. In spite of some well known benefits of multipath routing, its properties in theory and in practice got relatively little attention from the research community. In this study, we investigate several fundamental aspects of multipath routing. We establish a number of theoretical results regarding the capabilities of multipath routing that give rise to its efficient deployment in practical settings.


Our study investigates multipath routing from several perspectives. One is the purpose of employing multipath schemes. We primarily focus on the major goals of congestion avoidance and enhanced survivability, from an algorithmic point of view. In addition, we consider other algorithmic issues of multipath routing, such as the need for topology control in wireless networks when multipath solutions are employed. Another aspect is the available information on the problem's input. While we mainly focus on offline multipath problems, we also consider their online versions, where there is no a-priori knowledge regarding future demands. A third aspect that is considered in this study is the cooperation (or lack thereof) among decision makers. While we mainly focus on global optimization, we also explore the fundamentally important case where multipath routing is performed by selfish decision makers. Finally, we have investigated the influence of the employment of multipath routing schemes on the design of the underlying network. In this context, we have investigated the savings in network resources when the users are allowed to employ multipath solutions in their routing decisions.