The Internet infrastructure can be broken down into inter-connected zones of administrative control known as autonomous systems (AS). An AS has total control over the routing policies within its network. Each AS determines where to forward packets according to its internal policies and information it can gain from its neighbours about the state of the network as a whole. Network instability happen when an AS switches its best route rapidly. This can lead from delays to whole portions of the Internet becoming unreachable.
This talk will be about modelling Interdomain Routing with game theory. While game theory has been used in the context of Internet research, it is mainly used where the players are users of the network. Here, it is network nodes themselves that are the players. Using game theoretic ideas, it maybe possible to come up with a set of winning strategies for ASes to avoid creating instabilities or at least to minimise their impact.
In simple routing games, each player (network node) tries to route packets according to its preferred route with full knowledge of the network topology. To model Interdomain routing realistically, the game becomes Bayesian in nature where each player has some a priory notion of what other may do. Some simple examples of both games will be given.
This is a work in progress and comments are welcome.