They present our adaptive routing and scheduling algorithm. Packet-by-Packet Adaptive Routing for Networks—PARN for ease for repeated reference later. A introduce the queue structure that is used in PARN. The back-pressure algorithm introduced in has been widely studied in the literature. While the ideas behind scheduling using the weights suggested in that paper have been successful in practice in base stations and routers, the adaptive routing algorithm is rarely used. The main reason for this is that the routing algorithm can lead to poor delay performance due to routing loops. Additionally, the implementation of the back-pressure algorithm requires each node to maintain per-destination queues that can be burdensome for a wireline or wireless router. Motivated by these considerations, we reexamine the back-pressure routing algorithm in this paper and design a new algorithm that has much superior performance and low implementation complexity the importance of doing shortest-path routing to improve delay performance and modified the back-pressure algorithm to bias it toward taking shortest-hop routes. A part of our algorithm has similar motivating ideas. In addition to provably throughput-optimal routing that minimizes the number of hops taken by packets in the network, In additional to real queues, each node also maintains a counter, which is called shadow queue, for each destination . Unlike the real queues, counters are much easier to maintain even if the number of counters at each node grows linearly with the size of the network. A back-pressure algorithm run on the shadow queues is used to decide which links to activate. The statistics of the link activation are further used to route packets to the per-next-hop neighbor queues mentioned earlier. The details are explained next.
You are here: Home / ieee projects 2013 / PACKET-BY-PACKET ADAPTIVE ROUTING AND SCHEDULING ALGORITHM FOR NETWORKS