Autonomous Load Balancing Anycast Routing for Wireless Mesh Networks: VoIP Call Support
Sangsu Jung, Dujeong Lee, Malaz Kserawi, and June-Koo Kevin Rhee Department of Information and Communications Engineering Korea Advanced Institute of Science and Technology (KAIST)
Daejeon, Rep. of Korea
{s.jung, dj.lee, malaz, rhee.jk}@kaist.ac.kr
Abstract— Voice over IP (VoIP) over a wireless mesh network (WMN) is a killer application candidate of the next generation services over wireless and mobile network infrastructure. Yet, the routing and transport efficiencies in consideration of specific attributes of WMNs have been little emphasized. Distinctively from conventional networks, the major traffic pattern of WMNs is anycast (one-to-one-of-many). To fully utilize the service aspects of WMNs, load balancing and scalability should simultaneously be supported. For VoIP, one challenge is to maintain the perceived quality depending on both loss and delay.
In this paper, we assess autonomous load balancing anycast routing regarding VoIP supportability. The protocol is based on physics analogy and a distributed algorithm. We compare the protocol with shortest-path routing and back-pressure routing via simulations. Simulation results exhibit that autonomous load balancing of the protocol efficiently supports voice calls to guarantee the certain level of quality.
Keywords - wireless mesh network, anycast, routing, load balancing, VoIP
I. INTRODUCTION
A wireless mesh network (WMN) has been introduced as a consumer network to substitute wireless ad hoc networks (MANETs), which draws attention for commercial applications in the near future as one of the next generation consumer networks.
Because MANETs usually consist of arbitrary mobile nodes, it is difficult to stimulate the cooperation of nodes and to provide Internet connectivity through relaying. Furthermore, an energy-constraint worsens the construction of MANETs.
For a commercial purpose, WMNs are designed to provide Internet connectivity to users. Similar to MANETs, WMNs are infrastructure-less, scalable, and self-configured. However, the networks involve little mobility compared to MANETs.
Furthermore, the major traffic patterns for practical applications are formed from users to multiple Internet gateways and vice versa. Here, a specific communication type, that is, anycast (one-to-one-of-many communication) [1], can provide the same Internet access services through several mesh gateways, meaning that a mobile user can change its serving gateway for the same service provided that gateways can handle handovers of user services. In this way, a mobile user
can be always associated to a gateway with best forwarding performance.
Even though conventional shortest-path unicast routing protocols [2][3] could be used for WMNs, they are not scalable because control overhead increases super linearly as they establish an individual path per node-gateway pair. Anycast modified versions of them [4]-[8] still have similar limitations because they require association of gateways and mobile users should update whole path information. That is, they cannot properly react to traffic congestion on a path due to conveyed overhead.
One way to mitigate traffic congestion is back-pressure routing [9] where the queue length is used for routing metric.
However, this approach increases delay [10] and sometimes incurs more collisions, hence it degrades the performance of networks if it does not adopt specialized scheduling scheme.
In this paper, we assess our previously proposed protocol, ALFA [11][12], which overcomes the shortcomings of traditional shortest-path routing and back-pressure routing, on the viewpoint of VoIP supportability. In other words, the main contribution of the paper is the extended study of ALFA and the assessment of it on the consideration of an application, VoIP.
The rest of the paper is organized as follows. In section II, we explain the concept of our protocol which achieves autonomous load balancing with little control overhead. Then we evaluate our protocol compared to shortest-path routing and back-pressure routing and discuss the results in section III. In section IV, we describe related works. Finally, we conclude the paper in section V.
II. AUTONOMOUS LOAD-BALANCING FIELD-BASED ANYCAST ROUTING (ALFA)
We have introduced autonomous load-balancing field- based anycast routing (ALFA) [11][12] specially designed for anycast WMNs. Based on analogy to physics, especially, Poisson’s equation [13][14] for electrostatic systems, we develop field-based routing, where a node forwards a packet to neighbor node that has the lowest scalar potential value among its one-hop neighbor nodes. Every node is assigned a scalar potential value that satisfies Poisson’s equation with the help of
The 13th IEEE International Symposium on Consumer Electronics (ISCE2009)
Fig. 1. An example of ALFA routing in an anycast WMN.
a finite element method (FEM) [14] and a local equilibrium method (LEM) [15] for a distributed implementation. The distributed LEM formulation can be found as [11]:
( ) ( )
∑
∑
−
= +
−
= + + +
−
+
−
⋅
−
= 1
0
2 , 1 , 1
0 1, , , 1, , 1, ( )
)
( n
i iv i v
n
i i v iv iv i v iv i v
d d
v d
d d d
v r r
r r r
r φ ηρ
φ
φ (1)
where φ(v)is the potential of the v-th node in the mesh, φi,v is the potential of the i-th neighbor node of node v, whose geographic position is defined by the relative distance vector
v
dri,
with respect to the position of node v. Variable ρ(v) represents the number of packets in the queue of node v, which corresponds to an electrical charge in an electrostatic system.
As shown in Fig. 1, the potential metric reflects the degree of geographic proximity to a destination and the degree of congestion, simultaneously. The potential model governed by Poisson’s equation establishes a uniform gradient field so that packets are forwarded to steepest descent potentials reaching just any gateway for Internet access.
Surprisingly, local iterations of (1) among one-hop neighboring nodes quickly approaches the globally 90% steady state within tens of iterations in the mean-square-root-error sense.
On the other hand, ALFA utilizes loose source routing for downlink from a mesh gateway to a mesh node. In this routing, every node records the one-hop routing path for uplink and reuses it for downlink. This is similar to MAC address learning scheme in Ethernet [16] and a related work, HEAT routing [17].
The key properties of ALFA are to provide autonomous load balancing among multiple gateways and mesh nodes due to the nature of Poisson’s equation, scalability with an FEM,
C
G2 B
A
D E
G1
H Φ= 0
Φ= -11
Φ= -27 Φ= -14
Φ= -50
Φ= -23
Φ= -35
Φ= -42
Φ= -50
Mesh Node Mesh Gateway
Fig. 2. Route change of ALFA in traffic congestion.
D
Φ= 0
Φ= -11
Φ= -27 Φ= N/A
Φ= -50
Φ= -34 Φ= -16 A
B
C
D
G1 E G2
F Φ= -20
Φ= -50 Mesh Node
Mesh Gateway Failed Mesh Node
Fig. 3. Route change of ALFA in a node failure.
For example, if the potential of node C in Fig.2 changes from -27 to -14 due to increased congestion, the original route (A->B->C->G1) changes into another uncongested route (A-
>B->D->E->H->G2). According to the characteristics of Poisson’s equation, nodes around congested hot spots tend to have high potential; thereby, the probability to be selected as a path becomes lower and another less congested path is chosen, so called autonomous load balancing. In addition, when a node failure happens (ex. node C), the new path (A->B->D->E->G1) is rapidly reformed from the original path (A->B->C->G1) without any additional overhead. (Fig. 3) This property is similar to a face routing scheme of conventional geographic routing with voids, which pursues to find an alternative forwarding node tracking all available neighboring nodes.
However, ALFA does not have to track all available forwarding nodes; hence, it minimizes delays and contention degrees.
III. ASSESSMENT OF ALFA VIA VOIPSUPPORT We extensively study the performance of ALFA using NS2
5 9 3 7
11
2 6 1 8
4
10
Mesh Node Traffic Source Gateway #1 Gateway #2
Fig. 4. Simluation topology.
80 85 90 95 100
0 150 300 450 600 750 900
CDF (%)
End to End Delay (ms)
ALFA SPR BPR
Fig. 5. Delay CDF for VoIP packets of scenario #1,
with voice call services for nodes 1 through 3.
0 20 40 60 80 100
0 150 300 450 600 750 900
CDF (%)
End to End Delay (ms)
ALFA SPR BPR
Fig. 6. Delay CDF for VoIP packets of scenario #2, with voice call services for nodes 1 through 5.
0 20 40 60 80 100
0 150 300 450 600 750 900
CDF (%)
End to End Delay (ms)
ALFA SPR BPR
Fig. 7. Delay CDF for VoIP packets of scenario #3, with voice call services for nodes 1 through 7.
0 20 40 60 80 100
0 150 300 450 600 750 900
CDF (%)
End to End Delay (ms)
ALFA SPR BPR
Fig. 8. Delay CDF for VoIP packets of scenario #4, with voice call services for nodes 1 through 9.
0 20 40 60 80 100
0 150 300 450 600 750 900
CDF (%)
End to End Delay (ms)
ALFA SPR BPR
Fig. 9. Delay CDF for VoIP packets of scenario #5.
with voice call services for nodes 1 through 11.
0 20 40 60 80 100
ALFA SPR BPR
Load Ratio (%)
Gateway #1 Gateway #2
Fig. 10. Comparison for the load sharing of mesh gateways of scenario #3.
with anycast modified versions of traditional shortest-path routing (SPR) and back-pressure routing (BPR). For simulations, 100 mesh nodes are generated and two mesh gateways are constructed in a 2500m×2500m area. (Fig. 4) The transmission range of the nodes is set to 250m. The voice calls use G.729a with framing interval 20ms under the bandwidth of 2Mbit/s. All calls are one minute long and simultaneous up-stream and down-stream sessions correspond to each mesh node-gateway pair. To measure the VoIP supportability under three routing schemes, we adopt the quality metric of [19] defined by R-score. Here, 70 of R-score is for medium quality where all packets are delivered within 150ms or 98% of them have delays less than 100ms.
We consider five scenarios. For scenario #1, VoIP traffic is generated from up to 3 mesh nodes, 1, 2, and 3 of Fig. 4, where 6 voice call sessions between mesh nodes and gateways are engaged. For scenario #2, #3, #4, and #5, we increase mesh nodes generating traffic by a step of two to observe the performance change with respect to network loads.
In a relatively lightly loaded scenario #1, all voice call packets are arrived within 150ms in three schemes. (Fig. 5) However, the performance differences manifests as the traffic increases as in scenarios #2 through #4. (Fig. 6-8) Because SPR always selects the closest destination, gateway #1––except for scenario #5, mesh nodes 10 and 11 choose gateway #2—to make voice call connections, gateway #1 is heavily loaded and gateway #2 is idle even though it can accommodate voice calls which cannot be supported by gateway #1. This under- utilization of a network is prevented in ALFA and BPR due to their inherent congestion avoidance mechanisms. Here, BPR shows unstable but higher CDF values of packets delivered within 150ms than that of SPR. Because BPR conducts routing only based on queue differences among its one-hop neighbors, inefficiently long paths could be selected, even increases collisions and delay. Even though it slightly balances loads between the gateways (Fig. 10), the total number of packets successfully delivered is significantly less than those of ALFA and SPR as shown in Fig. 11. This interpretation can be also
0 2000 4000 6000 8000 10000 12000
ALFA SPR BPR
Number of Packets Received
Gateway #1 Gateway #2
Fig. 11. Comparison for the number of packets served by mesh gateways of scenario #3.
outperforms SPR and BPR. The reason can be attributed to that load balancing between two gateways is efficiently achieved in ALFA, and simultaneously, the proximity reflection contributes to minimizing delays when gateway #1 is overloaded beyond its capacity.
IV. RELATED WORKS
IP anycast was introduced for IPv4 in 1993 [20] and extended for IPv6 [21]. However, IP anycast has not been widely deployed due to its scalability limitations in the Internet infrastructure. Recently, anycast has received attentions by researchers with the boosting of hub-and-spoke type of network services such as wireless mesh networks with multiple gateways for Internet access and sensor networks with a few sinks to gather information from sensor nodes. In traditional anycast schemes [4]-[8], a communication is configured from a node to the nearest destination, that is, in the context of per- destination pair. They even require additional communication control overhead for re-association to balance the loads of service gateways or sinks since they are still based on unicast routing. V. Lenders et. al [22] propose distributed density- based anycast strategy in the framework of field-based routing to increase path diversity, hence, guaranteeing high packet delivery ratio. However, this approach cannot react to traffic congestion; hence, even a worse scenario may happen where highly dense groups cause more collisions and delay.
On the other hand, there has been little research on anycast considering VoIP. Different from typical UDP and TCP, VoIP requires the perceived quality of both delay and loss for service.
In a typical unicast scenario in WMNs, A. Kashyap et al. [23]
has dealt with the route selection issue for VoIP and developed a new routing method using call statistics in order to determine less-critical paths which can be utilized for a future network bandwidth usage to serve voice calls as many as possible.
Because it exploits multiple paths maximizing network throughput and tends to use less-critical paths, it is somewhat relevant to the purpose of autonomous load balancing of ALFA.
(CAC) decision problem considering interference over WMNs.
To maintain the QoS of existing calls, their scheme strives to provide less than 20% incorrect decisions for different types of linear multihop topologies. In ALFA, the autonomous load balancing property reduces interference to diversify paths considering congestions but it is possible to investigate sophisticated relationships among route-coupling, scheduling, delay, and voice call capacity bounds.
A recent trend to enhance VoIP performance is packet aggregations to increase voice call capacity [25][26] and analytical studies for VoIP via wireless networks are found in [27][28]. Several issues of VoIP over WMNs are summarized in [29].
V. CONCLUSIONS
In this paper, we assess our previous work, ALFA [11][12]
by analogy to physics, on the aspect of VoIP to investigate the feasibility of consumer service deployments in WMNs.
Through an extensive simulation study, we show that ALFA supports more VoIP calls compared with traditional shortest- path routing and back-pressure routing due to the inherent merits of ALFA, such as autonomous load balancing, scalability, and stateless property.
REFERENCES
[1] C. Metz, “IP anycast point-to-(any) point communication,” IEEE Internet Computing, Vol. 6(2), 2002, pp. 94-98.
[2] C. E. Perkins, E. Belding-Royer, and S. R. Das, “Ad hoc on-demand distance vector (AODV) routing,” http://www.ietf.org/rfc/rfc3561.txt, July 2003, RFC 3561.
[3] C. E. Perkins and P. Bhagwat, “Highly dynamic destination-sequenced distance-vector routing (DSDV) for mobile computers,” in Proc. of ACM Sigcomm, London, UK, 1994.
[4] V. Park and J. Macker, “Anycast routing for mobile services,” in Proc.
of CISS, 1999.
[5] J. Wang, Y. Zheng, and W. Jia, “An AODV-based anycast protocol in mobile ad hoc network,” in Proc. of IEEE PIMRC, 2003.
[6] J. Wang, Y. Zheng, and W. Jia, “A-DSR: a DSR-based anycast protocol for IPv6 flow in mobile ad hoc networks,” in Proc. of IEEE VTC, 2003.
[7] U. C. Kozat and L. Tassiulas, “Network layer support for service discorvery in mobile ad hoc networks,” in Proc. of IEEE INFOCOM, 2003.
[8] V. Park and J. Macker, “Anycast routing for mobile services,” in Proc.
of CISS, 1999.
[9] L. Tassiulas and A. Ephremides, “Stability properties of constrained queueing systems and scheduling polices of maximum throughput in multihop radio networks,” IEEE Trans. on Automatic Control, Vol.
37(12), 1992, pp. 1936-1948.
[10] L. Ying, S. Shakkottai, and A. Reddy, “On combining shortest-path and back-pressure routing voer multihop wireless networks,” in Proc. of IEEE INFOCOM, 2009.
[11] S. Jung et al., “Distributed potential field based routing and autonomous load balancing for wireless mesh networks,” IEEE Communications Letters, to appear.
[12] S. Jung et al., “Autnomous load balancing anycast routing protocol,” in Proc. of IEEE HotMesh, 2009.
[13] L. J. Segerlind, Applied finite element analysis, 2nd edition, Chap. 5, John Wiley&Sons, 1984.
[14] J. L. Volakis, A. Chatterjee, and L. C. Kempel, Finite element method for electromagnetics, Chap. 4, IEEE Press, 1998.
[15] Z. Li and M. B. Reed, “Convergence analysis for an element-by-element finite element method,” Computer Methods in Applied Mechanics and Engineering, Vol. 123, 1995, pp. 33-42.
[16] S. Halabi, Metro ethernet, 1st edition, Cisco Press, 2004.
[17] R. Baumann, S. Heimlicher, and B. Plattner, “Routing in large-scale wireless mesh networks using temperature fields,” IEEE Network, Vol.
22(1), 2008, pp. 25-31.
[18] NS-2, http://www.isi.edu/nsnam/ns/.
[19] R. G. Cole and J. H. Rosenbluth, “Voice over IP performance monitoring,” ACM Computer Communication Review, Vol. 3, 2001.
[20] C. Partidge, T. Mendez, and W. Milliken, “Host anycasting service,”
IETF RFC 1546, 1993.
[21] S. Deering and R. Hinden, “IP version 6 addressing architecture,” IETF RFC 2373, 1998.
[22] V. Lenders, M. May, and B. Plattner, “Density-based anycast: a robust routing strategy for wireless ad hoc networks,” IEEE/ACM Trans. on Networking, Vol. 16(4), 2008, pp. 852-863.
[23] A. Kashyap et al., “VoIP on wireless meshes: models, algorithms, and evaluation,” in Proc. of IEEE INFOCOM 2007.
[24] H. Wei et al., “On admisson of VoIP calls over wireless mesh network,”
in Proc. of IEEE ICC, 2006.
[25] W. Wang, S. C. Liew, and V. O. K. Li, “Solutions to performance problems in VoIP over 802.11 wireless LAN,” IEEE Transactions on Vehicular Technology, 2005.
[26] S. Ganguly et al., “Performance optimizations for deploying VoIP services in mesh networks,” IEEE Journal on Selected Areas in Communicastions, Vol. 24(11), pp. 2147-2158, 2006.
[27] D. Hole and F. Tobagi, “Capacity of an IEEE 802.11b wireless LAN supporting VoIP,” in Proc. of IEEE ICC, 2004.
[28] J. Yu, S. Choi, and J. Lee, “Enhancement of VoIP over IEEE 802.11 WLAN via dual queue strategy,” in Proc. of IEEE ICC, 2004.
[29] X. Wang, A. Patil, and W. Wang, “VoIP over wireless mesh networks:
challenges and approaches,” in Proc. of ACM WICON, 2006.
