title: Advanced Algorithms for Local Routing Strategy on Complex Networks.
abstract: Despite the significant improvement on network performance provided by global routing strategies, their applications are still limited to small-scale networks, due to the need for acquiring global information of the network which grows and changes rapidly with time. Local routing strategies, however, need much less local information, though their transmission efficiency and network capacity are much lower than that of global routing strategies. In view of this, three algorithms are proposed and a thorough investigation is conducted in this paper. These algorithms include a node duplication avoidance algorithm, a next-nearest-neighbor algorithm and a restrictive queue length algorithm. After applying them to typical local routing strategies, the critical generation rate of information packets Rc increases by over ten-fold and the average transmission time 〈T〉 decreases by 70-90 percent, both of which are key physical quantities to assess the efficiency of routing strategies on complex networks. More importantly, in comparison with global routing strategies, the improved local routing strategies can yield better network performance under certain circumstances. This is a revolutionary leap for communication networks, because local routing strategy enjoys great superiority over global routing strategy not only in terms of the reduction of computational expense, but also in terms of the flexibility of implementation, especially for large-scale networks.
authors.affiliation: Department of Modern Physics, University of Science and Technology of China, Hefei, China.
authors.forename: Benchuan
authors.initials: B
authors.lastname: Lin
authors.affiliation: School of Computing, National University of Singapore, Singapore, Singapore.|Faculty of Information Technology, Macau University of Science and Technology, Macau, China.
authors.forename: Bokui
authors.initials: B
authors.lastname: Chen
authors.affiliation: School of Physical Electronics, University of Electronic Science and Technology of China, Chengdu, China, Chengdu, China.
authors.forename: Yachun
authors.initials: Y
authors.lastname: Gao
authors.affiliation: Department of Electronic and Information Engineering, Hong Kong Polytechnic University, Hung Hom, Kowloon, Hong Kong.
authors.forename: Chi K
authors.initials: CK
authors.lastname: Tse
authors.affiliation: Department of Atmospheric, Oceanic and Space Science, University of Michigan, Ann Arbor, United States of America.
authors.forename: Chuanfei
authors.initials: C
authors.lastname: Dong
authors.affiliation: Division of Logistics and Transportation, Graduate School at Shenzhen, Tsinghua University, Shenzhen, China.|Center of Environmental Science and New Energy Technology, Tsinghua-Berkeley Shenzhen Institute, Shenzhen, China.
authors.forename: Lixin
authors.initials: L
authors.lastname: Miao
authors.affiliation: Department of Modern Physics, University of Science and Technology of China, Hefei, China.
authors.forename: Binghong
authors.initials: B
authors.lastname: Wang
mesh_terms: D000465:Algorithms; D003195:Computer Communication Networks / Q000706:statistics & numerical data*; D006801:Humans; D015233:Models, Statistical; D012984:Software