Abstract

Knödel graphs W d,n of even order n and degree d , 1 {600} d {600} [Special characters omitted.] log 2 n [Special characters omitted.] , was introduced by W. Knödel for broadcasting and gossiping information in interconnected networks. It has been proved that the diameter of the Knödel graphs W d,2 d is [Special characters omitted.] . In recent years, peer-to-peer (P2P) computing has attracted a lot of attention from the researchers and application developers. With the development of mobile networks, mobile peer-to-peer (MP2P) computing may become a potential "killer application" of the mobile carriers. In this thesis, we present a P2P network structure based on the Knödel graphs. The routing algorithm takes advantage of the routing heuristics in the Knödel graphs and reduces the routing length of P2P network by half, compared with the currently studied P2P network structures (CHORD and CAN). Given that most mobile devices have limited computing resources, another advantage of the proposed P2P network structure is that it can be flexibly configured to adapt to different MP2P application scenarios, taking into the fact that most mobile devices have limited computing resources. With this model, each mobile node maintains a fixed-size routing table regardless of the size of the whole network, while the tradeoff on routing hops is still acceptable in many MP2P applications. Some practical heuristics for real mobile network are also proposed in this thesis