The problem of multipath routing has received a considerable amount of attention due to its broad application in mitigating routing issues, such as addressing the problem of traffic distribution across a set of resources for which individual paths may not have the capacity to carry the load, achieving a higher resiliency through active backup paths, facilitating reliable network operation by routing and resource management, and meeting performance measures. Such problems can be formulated as a bimatrix game using game theory with different objective functions.;This dissertation studies how to solve a general multipath routing problem using game theory. Through studying and categorizing the costs for source and destination nodes, the interaction between the two distant independent nodes can be modeled as a non-cooperative game. When only considering single metric, the game can be further expressed as a cardinal potential game. Not only does this characteristic simplify the process of finding the Nash Equilibria (NEs) but also brings a multipath load sharing framework by using the potential value to evaluate the routing strategies.;In addition, a novel vectorized routing cost model, based on vector space and game theory, is defined to overcome the limitation of the previous model. The vectorized model provides the ability of considering multiple metrics simultaneously. To solve the vectorized routing model, a set of universal refinement tools is proposed through analyzing the rationale behind the behaviors of nodes under the context of game theory. In particular, one of refinement tools is proved as the extensive form of the potential value method. Through the refinement tools, a generalized multipath load sharing framework is achieved, which is applicable to more general settings since it does not depend on specific characteristics of the game.;Multi-criteria simulations on real instances show that significantly higher routing resiliency can be achieved through the generalized multipath load sharing framework.
展开▼
