International Journal of Scientific & Engineering Research, Volume 5, Issue 9, September-2014 575
ISSN 2229-5518
Efficient Adaptive Routing Packet Transmission in Wireless Networks P. V. S. Srinivas1, D. Naga Swetha2
—————————— ——————————
Wireless Communication rebellion is bringing primary changes to data networking, telecommunication and is building integrated networks a reality. By freeing the user from the cord, personal communications networks, wireless LANs, mobile radio networks and cellular systems, harbour the promise of fully distributed mobile computing and communications, anytime, anywhere. Focusing on the networking and user aspects of the field, wireless networks provides a global form for archival value contributions documenting these fast growing areas of interest. Availability, cost, reliability, security, speed, scalability and topology can be considered as important characteristics in network design. Several Adaptive Routing protocols have been developed for different purposes. Like, (IS-IS) protocol is designed to route data through large networks namely Internet backbones. The (RIP) is exceptional for small distance transport. With deterministic adaptive routing strategies good quality results can be achieved [1]. Here, in this paper, we deal with the high delay and
queuing convolution issues. Due to routing loops the
routing algorithm leads to poor delay performance and to overcome this drawback a new algorithm designed which has much superior performance and low implementation complexity. By throughput- optimal routing, the number
• P.V.S. Srinivas1 is presently serving as Professor & Head in the Department of Computer Science and Engineering at TKR College of Engineering & Technology, Hyderabad, India.
• D. Naga Swetha2 is currently pursuing her masters degree program in
the Department of Computer Science and Engineering at TKR College of
Engineering & Technology, Hyderabad, India.
E-mail: dswetha806@gmail.com
of hops taken by packet in the network can be
minimized[11]. A new concept named as Shadow Queues used here to decouple routing and scheduling in the network with the help of probabilistic routing tables. To update a probabilistic routing table a shadow network is used. The same shadow network, with back-pressure algorithm, is used to activate transmissions between nodes. However, first, actual transmissions send packets from first-in–first-out (FIFO) per-link queues, and second, potentially more links are activated, in addition to those activated by the shadow algorithm.[2]The major difference between the previous and present enhanced back-pressure algorithm is performing partial decoupling of shadow backpressure and real packet transmission allows us to activate more links. This difference results in good delay performance. The proposed algorithm is applicable to wire line and wireless networks.
By the way of specified in back pressure based adaptive routing algorithms that each packet is directed along a feasibly improved path, in addition such algorithms characteristically effect in deprived interval concert and associate high application complexity. The outmoded process groups the scheduling and routing functions well-balanced and conserves a queue for every target at each node. Consequently the number of targets can be as hefty as the number of nodes, this each-target queue up constraint can be relatively hefty for practical
implementation in a network. On every link, the
IJSER © 2014 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 5, Issue 9, September-2014 576
ISSN 2229-5518
algorithm allocates a weight to every probable target that is called back pressure [2]. This feature stops further blocking nodes that remain earlier blocked, as a result provided that the adaptivity of the algorithm in contrast, can be useful in wired network only [3]. The back- pressure over a link should be positive that is contained in the selected schedule to transmit the packets over a link and this queue managing constraint possibly will be an excessive overhead for a huge network.
The constancy of a queuing network through
dependent servers is reflected. The dependence amongst the servers is achieved by defining their subsets which can be activated concurrently. The performance measure of a scheduling strategy is characterized by its constancy region, that is, the set of routes of arrival and facility rates for which the system is constant[2]. A strategy is achieved which is finest, in the sense that its constancy region is considered where it is a superset of every other scheduling policy region. The performance of the network is considered for arrival rates that lie exterior to the constancy region and the effects of the outcomes in certain forms of concurrent database and parallel processing systems are discussed. Multihop radio networks offer a stimulus for considering this system, where the problem of scheduling the server stimulation under the restraints carried out by the dependence amongst servers is considered.
The network abides of power controlled nodes which can be transmitted through wireless links along adaptive transmission rates. The packets access the system at every node randomly and remain within output queues to reach the target in the network. We set up the capacity region of all rate matrices (λij ) that the system can steadily support[11]. Here, (λij ) represent the rate of traffic induced at node ‘i’ and intended for node ‘j’. The dynamic routing and power allocation intended for a wireless network policy is developed with time changing channels which stabilize the system. It yields defined average delay covenant, at any time the input rates are within this capacity region [4]. We subsequently relate this control algorithm to an ad-hoc wireless network where channel changes are owed to user mobility, and its performance is correlated with the Grossglauser-Tse relay model. Such performance influence for common arrival and channel state process, despite processes are anonymous to the network controller.
The back-pressure algorithm is considered as a most eminent favourable algorithm but its delay concert
possibly will be relatively poor, even when the traffic load is not nearest to network capacity because of two reasons. Primary, every node has to sustain a sovereign queue for every asset in the network in addition only one queue is provided at a point. Secondary, this algorithm possibly will route a few packets across very long routes. The elucidation for multi-rate multicast is based on scheduling virtual traffic that moves in reverse direction from targets to origin. This shadow scheduling algorithm can also be used to manage setbacks in wireless networks [3]. In this paper, we specify elucidation to consign the above issues and decrease the complication of the queuing data structures which is maintained at every node in the case of a fixed-routing network scenario where the route of each flow is selected upon arrival [2].
Fig 1: System Architecture
3.1 Efficient Adaptive Routing Packet Transmission In the traditional methodology, a queue for each destination has to be maintained by every node. Every pair of nodes is communicated along a path connecting them and with this approach more number of queues has to be maintained. To overcome this snag, that is maintaining a queue for every destination, a queue for every neighbour, called a real queue is maintained by every node. By this, maintaining the number of queues at each node will be less when we compare it with traditional approach. Along with these real queues at each node, a counter is maintained called as Shadow Queue at the destination[11]. It is easier to maintain the counters at each node but the link activation has to be
decided to route packets to the neighbour queues.
Here are the algorithms made the Efficient Adaptive Routing Packet Transmission in an effective way.
are modernized based on the crusade of fabricated
IJSER © 2014 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 5, Issue 9, September-2014 577
ISSN 2229-5518
entities as an interchange of control messages for the purposes of routing and schedule called shadow packets in the network. Same as like real packets, the shadow packets arrive from outside the network and eventually exit the network and runs on the shadow queuing system with an arrival rate marginally larger than the real external arrival rate of packets [5]. The shadow queue is basically a counter that is incremented by 1 upon a shadow packet arrival and decremented by 1 upon a departure and there is no necessity to implicate in any
queuing data structure at each node. The algorithm track
on the shadow queues is used to stimulate the links that are triggered to serve packets to a specific destination.
Fig 2: Comparison between Back-pressure algorithm and
Adaptive Routing algorithm
B) Maintenance of Counters set: Each node maintains a set of counters, which are called shadow queues, for each previous hop and each destination and for external flows destined for at node. Each node also maintains a real queue, denoted by, for each previous hop and each next- hop neighbor, and for external flows with their next hop [8]. The shadow queues at each node are notable by their previous hop and their destination, then only accepts the packets from previous hop with destination. The related rule should be trailed when packets are shattered from the shadow queue.
shadow queues, we partially decouple routing and scheduling. A shadow network is used to up-date a probabilistic routing table that packets use upon arrival at a node. The same shadow network, with back-pressure algorithm, is used to trigger transmissions amongst nodes[9]. First, actual transmissions send packets from first-in–first-out (FIFO) per-link queues, and second, potentially more links are stimulated, in addition to those actuated by the shadow algorithm.
must be less than the token generation rate because of
IJSER © 2014 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 5, Issue 9, September-2014 578
ISSN 2229-5518
random processes[11]. The token-based algorithm is an approximation due to the occurrence of breaks for prolonged periods of time.
capacity at a link is determined by the shadow scheduling algorithm[5]. This capacity is assured to be at least equal to the shadow arrival rate of real packets which is obviously smaller. The difference between the link capacity and arrival rate could be proportional to epsilon, that should be sufficiently large to ensure small delays while also sufficiently small to ensure that the capacity region is not moderated ominously.
First, we compare the performance of three algorithms: the traditional back-pressure algorithm, the basic shadow queue routing/scheduling algorithm without the extra link activation enhancement, and Efficient Adaptive Routing Packet Transmission. Without extra link activation, to ensure that the real arrival rate at each link is less than the link capacity delivered by the shadow algorithm, links with back-pressure less than will not be scheduled and thus can contribute to further delays.
Fig 3: Delay performance of Efficient Adaptive Routing
Packet Transmission and shortest path routing.
Because we exaggerate the shadow traffic and the throughput region of the algorithm without extra link
activation is smaller than the throughput region of the
traditional back-pressure algorithm. We also compare the delay performance of Efficient Adaptive Routing Packet Transmission with that of the shortest path routing for each pair of source and destination, we find a shortest path between them by using Dijkstra’s algorithm[11].
Fig 4: Packet delay performance without network coding
Fig 5: Comparison of probabilistic splitting and token bucket algorithms
Efficient Adaptive Routing Packet Transmission can obtain similar delay performance as the shortest-path routing at light traffic[9]. A wireline network does not capture the scheduling aspects inherent to wireless networks. In the case of wireless networks, even with extra link activation, to confirm stability even when the arrival rates are within the capacity region. Extra link activation can be used to decrease delays significantly for especially in light traffic region.
In this paper, Efficient Adaptive Routing Packet Transmission routes the packets most probably on shortest hops and decouples routing and scheduling using a probabilistic splitting algorithm based on shadow queues. This can be maintained with the help of probabilistic routing table which slowly changes over
IJSER © 2014 http://www.ijser.org
International Journal of Scientific & Engineering Research, Volume 5, Issue 9, September-2014 579
ISSN 2229-5518
time. Efficient Adaptive Routing Packet Transmission provides efficient throughput and delays are reduced by extra link activation methodology.
We extend our approach to consider networks where network coding is used to increase throughput. This type of network coding reduces the number of transmissions. By enhancing the algorithm features, we can find the right trade-off between using possibly long routes to provide network coding opportunities delay incurred by using long routes. We can also allow broadcast transmission in our wireless network model, the total broadcast rate at which packets are scheduled.
[1] L.Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling policies for maximum throughput in multihop radio networks,” IEEE Trans. Autom. Control, vol. 37, no. 12, pp. 1936–1948, Dec. 1992.
[2] M. J. Neely, E. Modiano, and C. E. Rohrs, “Dynamic power allocation and routing for time varying wireless networks,” IEEE J. Sel. Areas Commun., vol. 23, no. 1, pp. 89–103, Jan. 2005.
[3] L. Bui, R. Srikant, and A. L. Stolyar, “Novel architectures and algorithms for delay reduction in back-pressure scheduling and routing,” in Proc. IEEE INFOCOM Mini-Conf., Apr. 2009, pp.
2936–2940.
[4] H. Seferoglu, A. Markopoulou, and U. Kozat, “Network coding-aware rate control and scheduling in wireless networks,” in Proc. ICME Special Session Netw. Coding Multimedia Streaming, Cancun, Mexico, Jun. 2009, pp. 1496–1499.
[5] S. B. S. Sengupta and S. Rayanchu, “An analysis
of wireless network coding for unicast sessions:
The case for coding-aware routing,” in Proc. IEEE INFOCOM, Anchorage, AK, May 2007, pp. 1028–
1036.
[6] A. Dimakis and J. Walrand, “Sufficient conditions for stability of longest-queue-first scheduling: Second-order properties using fluid limits,” Adv. Appl. Probab., vol. 38, no. 2, Jun.
2006.
[7] S. Katti, H. Rahul, W. Hu, D. Katabi, M. Medard, and J. Crowcroft, “XORs in the air: Practical wireless network coding,” Comput. Commun. Rev., vol. 36, pp. 243–254, 2006
[8] A. Brzezinski, G. Zussman, and E. Modiano,
“Enabling distributed throughput maximization in wireless mesh networks: A partitioning approach,” in Proc. ACM Mobicom, Sep. 2006, pp.
26–37.
[9] T. Ho and H. Viswanathan, “Dynamic algorithms for multicast with intra-session network coding,” IEEE Trans. Inf. Theory, vol. 55, no. 2, pp. 797–815, Feb. 2009.
[10] X. Lin and N. B. Shroff, “Joint rate control and
scheduling in multihop wireless networks,” in
Proc. 43rd IEEE Conf. Decision Control, Dec. 14–17,
2004, vol. 2, pp. 1484–1489.
[11] Srinivas MRSP, P.V.S. Srinivas “Efficient Power Allocation Strategy based Cooperative Network” American Journal of Engineering Research, vol. 2
Issue 9, ISSN(E): 2320-0847, ISSN(P): 2320-0936,
pp. 100-102.
IJSER © 2014 http://www.ijser.org