| Routing plays a crucial role in the network interconnection. It aims at finding the optimal paths and reducing the overhead caused by routing as far as possible. Nowadays, multiple routing schemes have been widely studied. From the aspect of the information utilized by routing, the existing schemes can be classified into two main groups:graph topology routing and geographical routing mechanisms.For graph topology routing, it can guarantee the optimal path with the cost of the massive entries in the routing tables. For geographical routing, the size of the routing tables is fairly small compared with those in graph topology routing. However, the latter can not find the global optimal path in general. This paper aims to improve on the existing routing mechanism, combines the advantages of the two routing mechanisms, while avoiding the disadvantages of both. The main contribution of the dissertation is as follows:Propose a Quadtree-based Optimal Path Routing mechanism——It can guarantee the optimal path using the graph topology routing method. Besides, by utilizing the geographical location information and the quadtree structure, the routing table size can be reduced to the information-theoretic lower bound. To guarantee the optimal path and compress the routing table as far as possible, a large number of schemes have been proposed in the literature. By using geographical location information, our results are even better than the best compression result which is based on IP address compression up to now. Our routing mechanism has two advantages. Firstly, our coding scheme is more intuitive than IP address. The destination in our routing table is encoded by quadtree which can divide and encode nodes intuitively. Secondly, the routing table size we get are superior to the existing literature’s. Simulation results show that, in general, the performace of routing table’s construction and lookup outperforms those in IP-based compression.Propose a QOPR+routing mechanism——Aiming at the shortage of routing updates (inserting a new node) in QOPR routing mechanism, on the basis of QOPR, we propose a QOPR+routing mechanism. By utilizing a novel proper quadtree bitmap hybrid structure (pqbh(T)) as routing table, it can further diminish the update complexity, which gives consideration to both lookup speed and update performance. In addition, we theoretically prove that pqbh(T) is a space-efficient data structure as well. The size of the routing table in QOPR and QOPR+barely differs by a small constant factor. Simulation results show that, in general, the performace of routing table’s construction, lookup and update outperforms those in QOPR routing mechanism with the cost of sacrificing part of the routing table size. |
