A Landmark Compact Routing Scheme Based On Affinity Propagation Algorithm

As rapid growth of Internet leaded to the low efficiency of traditional routing scheme, researchers are devoting themselves designing new routing scheme which has very low stretch and shorten routing table size greatly. We proposed a new routing scheme called APCR (Affinity Propagation Compact Routing), which uses AP (affinity propagation) clustering algorithm for community-partition, and realized a compact routing scheme for Internet-AS graph.Our work consists of:Upon comparison among almost all kinds of classic routing schemes, especially compact routing schemes, landmark-routing-scheme was found to have broad prospects. The critical issue of this routing scheme is how to partition a network into communities appropriately while identifying landmark of each community. So we studied many clustering algorithms especially AP and found that AP not only partitions communities efficiently, but also identifies landmarks. So we proposed APCR by combined AP and landmark-routing-scheme.The similarity matrix of AP algorithm was obtained according to negative distance among r-nearest neighbors. The network was clustered into different communities with labeled landmark via AP algorithm.Routing performance was computed based on clustered networks. The proper value of self-similarity, or so-called Preference which is a key argument of AP, was determined through large numbers of experiments on Internet topology. In particular, the relationship between self-similarity and routing performance was analyzed. The results showed that our algorithm achieved both very low stretch and very short route table length simultaneously by forming landmark set with a new method and realized compact routing on Internet-AS Level.