A New QUERY-REPLY Driven Routing Protocol with Reachability Analysis for Mobile Networks: DAG based Approach

Published Online October 2013 in MECS DOI: 10.5815/ijcnis.2013.12.07

In recent time, rapid escalation of cellular telephony is combined with a need for improved and efficient routing strategies. A powerful messaging pattern with a two way conversation over a channel is also required at the same time. During congestion in the network, one of such strategies known as Call Admission Control (CAC) is used to restrict the amount of users utilizing the network. The rest of the users are not permitted to any slot during this period [1]. Subsequently, Quality of Service (QoS) can be ascertained for the admitted users. Hence, it establishes two near contradictory prerequisites – propagating packets as well as ensuring Quality of Service (QoS) when all users are sending packet at the same time [2].

There are various routing strategies used in mobile networks till date. Some of those have used request-reply approach to obtain routing paths. The Directed Acyclic Graph (DAG) [3] approach is used to predict the nature of routing in advance. One of DAG based approach in [4] provides a reliable routing path in terms of multiple segments between source and destination nodes. With effect, a group of routing protocols for a network of processes is presented in [5] to route data to each member of the family. A request-reply based method in [6] develops a DAG to present a framework for loop-free on demand routing. Another routing method [7] is operated by controlling the request and response zones of network nodes during the route search process in order to reduce the routing overhead and network load. Again, a DAG based routing method [8] was introduced to support various path direction among the nodes in the network. A different routing model proposed in [9] results improved communication delay with packet delivery. The independent DAGs were developed [10] to compute independency on links and corresponding nodes. In this context, a research in [11] establishes a reachability relation which subsequently reduces the network traffic with high attainability. To improve sustainability of the network against failure, a proactive routing method has been discussed in [12].

The model proposed in this paper provides a new routing protocol for mobile networks. The work begins with representing a network to its equivalent graph G . The alternative routing paths have been generated between source and destination nodes in G through QUERY-REPLY packets. The right path among the alternatives has been selected following certain criteria defined on the model. Hence a Directed Acyclic Graph (DAG) G' is developed from the right path. Further it establishes a reachability relationship between these two nodes. Thus a proactive routing approach has been introduced to reduce the time complexity for communication to the desired extent. In addition, an improved scalability is obtained with the proposed work for larger number of the nodes in the network. The improvements of the proposed model over the other approaches are discussed through the experimental results.

The rest of the paper is organized as follows. The model proposed here is described in section II. The experimental results for the proposed model are discussed in section III. The advantage of the work is concluded with its future scope in section IV.

• II.    Proposed Model

• A.    System Model and assumptions

The standard cellular structure [13] for mobile networks in Fig. 1 (a) is considered as the layout of the proposed system. Each cell in the layout is represented as Cpq , where p denotes the radial distance (r) from mobile switching centre (MT) and the sequence number of a cell in a specific radial distance (r)is denoted by q. This structure is alternatively represented here as a graph G = (n, e), where n is the set of nodes denoting base stations (BSs) and mobile switching centre (MT) participating in communication, and e denotes the set of edges representing the connectivity among the nodes. The equivalent G for r = 3 as a prototype is shown in Fig. 1(b).

Figure 1: Representation of mobile networks (a) Cellular layout, (b) Equivalent graph structure.

The flexibility in the structure of G is maintained in such a way that the cost (i) V i E n due to handoff and cabling cost (cost_ca (i, j)Vi, j E n) can be minimized. The detailed outline for such minimization is described as follows.

A location updates strategy [14] which includes mobility and call arrival pattern is applied when mobile users cross a position area (PA) boundary. Then two factors related to such updating are considered as– (i) the prob(PA(i)) is defined as the probability of the user being located in PA(i) and (ii) the avgCost(i) is expressed as the average cost in PA(i) with assuming call arrival following Poisson distribution. Thus the minimization of cost function ( cost (i) V i E n) is presented as follows.

n objective: minimize ^ prob (PA(i)).avgCost (i)

i =1

,     (1, for update in PA(i)     „ subject to  bt = К                          (2)

ⁱ (.0,             otherwise

In (2), the update per user is represented by a binary string {b_n ,....., b 1 }Vi E n.

Generally, the perpendicular bisectors for each edge in a symmetric hexagonal cell intersect at a fixed point. The placement of a BS as a node (n) in G at that fixed point reduces the cabling cost [15] (cost_ca (i, j)Vi, j E n) rather than placing it in any other position within the cell. Thus the minimization of the factors including cost (i) V i E n and (cost_ca (i,j)Vi, j E n) are dependent on placing a node (n) in a cell.

• B.    Problem Statement

The problem addressed in this work can be stated as – given a G = (n, e), find a Directed Acyclic Graph (DAG) (G' = (n', e')) obtained from right path p (i, j), among multiple valid routing paths (P: V p (i, j) E P) generated by applying a procedure on G , such that G ‘ presents a reachability relation between i and j, w h ere i, j E n.

For instance, the reachability relation between i and j provides knowledge of a legitimate connection guaranteeing confirmation of data flow which subsequently reduces the time complexity of routing. However, the main hypothesis considered over the problem is presented next.

• C.    Main Hypothesis

By using G, with its corresponding ‘ for all (i,;) E n, it is possible to minimize the routing time with the help of rechability relation between i and j.

Before describing the detailed framework of the proposed model, some useful terminologies with respect to the model are defined as follows.

• D.    Terminologies used

(a) QUERY and REPLY Packets : Two packets named as QUERY and REPLY are used by the nodes to send data as well as receiving acknowledgement respectively.

(b) Node’s unique ID : Each node in the network is identified with its unique ID to identify specific source and destination respectively.

(c) Hop-metric : Two Hop metrics known as H_Query and H_Reply are associated with each node in the network to find the valid routing paths between specific source and destination respectively.

• E.    Steps of the Proposed Work

• (i)    Generation of Routing Paths:

The set of routing paths (P) have been generated as a result of execution of the Routing Path Generation algorithm. Initially, the source node (n^o) broadcasts the QUERY packet with the unique ID (IDnDE) of the destination node (nDE). Here, the H_Query values are initialized with the following instances.

u n f 0,        f°r ⁿ DE              _m

^_Quer^y -|^^££,      °therwise

The destination node (n_DE ) having H_Query value as 0 would receive the QUERY packet. After that, n_DE sets its H_Reply value to its H_Query value. Further n_DE sends a REPLY packet as an acknowledgment along with its own H_Reply value and ID (ID_nso ) of n_so ■ Each intermediate node (n_RE ) in the path receiving and passing the REPLY sets its H_Reply value with incrementing H_Reply from the previous n_RE by one. This process is continued until ID_nso matches with7D_nRE. The procedure is described by the following algorithm 1.

Algorithm 1: Routing path Generation

Input : A graph G = (n, e)

Output : A set of routing paths(P).

Functions Used:

Broadcast_packet (Packet, ID_nDE ): n_so broadcasts packet along with ID_nDE .

Receive_packet (Packet, n_DE ): Node n_DE receives the packet.

Send_packet (Packet, ID_nso , (H_Reply) n_DE ): Node n_DE sends out the Packet along with its H_Reply value.

Method:

begin for all node n except nDE

(H_Query)n = NULL; /* (H_Query)n is the

H_Query value of n */

(H_Query) nDE = 0; /* (H_Query) nDE is the

H_Query value of nDE */

Broadcast_packet (QUERY, IDnDE );

for a node nq         /*nq is the intermediate node while sending the QUERY*/ if ((H_Query)nq==0) /* it is possible only for nDE , so here nq = nDE */

Receive_packet (QUERY, nDE );

(H_Reply) n DE =(H_Query) n DE    ,

Send_packet (REPLY, IDnSO , (H_Reply) nDE );

end if for node nRE , nPRE    /* nPRE is the previous

REPLY sender */

While (nRE ! =nSO )    /* termination condition*/ if(Receive_packet(REPLY, nRE ))

(H_Reply) n RE =(H_Reply) n PRE +1;

/* (H_Reply) nRE is the H_Reply value of nRE */

/* (H_Reply) nPRE is the H_Reply value of nPRE */

Send_packet (REPLY, (H_Reply) nRE );

end if end while while(Receive_packet(REPLY, nSO ))

(H_Reply) n SO = (H_Reply) n RE +1;

end while end for end for end for end

• (ii)    Selection of Right Path:

The right path p (i, j^^i, j E n is selected among the set P by following rules.

Rule 1 : If there are different (H_Reply) n_so values for various routing paths (P) , then the right path p (i, j"yVi, j E n is with minimum (H_Reply) n_so value.

Rule 2 : If there are more than one routing paths (P) obtained with same minimum (H_Reply) n_so values, then the concept of logical clock [16] is used to evaluate the right one.

Thus the selection of the right path based on that concept is discussed as- a logical clock C_i (a) at a node i, ( i E n) in the G is assigned as the timestamp of a specific REPLY sending event (a). Again the REPLY passes through a node j and subsequently this event (b) is assigned a timestamp C j (b) . When i sends out a REPLY through a path as an acknowledgement for the source node n_so , then t_REPLY is assigned to the value of C (a). This REPLY passes through j as said before. Hence the value of C j would become as follows.

C j = max(Cj- (b), t RE _P LY + d), d > 0            (4)

Where, d is the communication delay between sending and receiving the packet.

In this way, there is a timestamp value C_so at n_so for every routing path. Subsequently these values are compared and the corresponding routing path with the minimum value among all is considered as the right path p (i, j)Yi, j E n.

• (iii)    DAG Representation:

A DAG is used in the proposed work to find the rechability relation between   nso and nDE - which subsequently reduces the  time complexity for communication. To obtain a DAG from the selected right path, initially, nso with a min (H_Reply) nso value is considered as an initial condition. Then the nodes пЕо and nDE are linked through a series of intermediate nodes ( n[N) on the basis of sequential decrement of H_Reply values. This process is continued until H_Reply value becomes zero. The procedure is described by the algorithm 2 as follows.

Algorithm 2: DAG Representation

Input: A right path p (i, j)Yi, j E n.

Output: A graph G = (n', e ).

Method:

begin

M = min (H_Reply)nSO; /* Initialize a variable M for nSO*/ for a node nIN if ((H_Reply)niN = M - 1)

then join link between nSO and nIN ;

While ((H_Reply)n NIN == 0 )

/*nNIN is the next intermediate node to nIN and loop terminates if nNIN = nDE */ repeat if ((H_Reply)nNiN = (H_Reply)niN - 1)

then join link between nIN and nNIN ;

end

Remark: If the entire network having a total number of nodes N is divided into m layers with n_; nodes in each of them i.e., Ej=1 H ; = N , then the number of possible DAGs over that network is expressed as follows:

D(N

N N-m +1 N-m +1-n1    ^N-m +1-S^m =1 ⁿ k m-1

= 2 2  2 -•  2№"]

m=1 n1=1    n2=1            nm =1

• - 2[;-1])(5)

(iv)Introduction of Reachability relation:

A G' provides a directed path between n_so and n_DE . Moreover, a transitive closure is developed as a result for such computation. Hence it introduces a reachability relation between n_so and n_DE . The reachability relation obtained from G’ represents a strict partial order among the nodes. Generally, the transitive reduction is an inverse process of transitive closure with maintaining the connectivity. In this context, the transitive reduction is unique for each G' in the entire network. Naturally the reachability relation represents the transitive closure of its edge set.

Let us assume G'nso nDE = 1, if and only if nDE is reachable from nso through k number of intermediate nodes. Here, if any path with G'^ „ = 1 is previously selected, then there is no need to check again that path as a candidate solution for further analysis. Thus it reduces time complexity for routing in advance. In such a way it enhances Quality of Service (QoS) for the network. A salient feature of introducing such reachability relation is concluded with the following lemma.

Lemma: Every reachability relation G' „ „ has a unique transitive skeleton (o"(G '„ „ )) with polynomial time reduction.

Proof: There is an algorithm A for constructing G which can be considered as an event X . Henceforth reachability relation obtained on the basis of the transitive closure property from G is considered as an event Y. Some properties are considered regarding these events as follows.

• (a)    Given an instance I_x of X , A produces an instance I_y of Y.

• (b)    A executes in polynomial time i.e., |I_X |.

• (c)    Answer to I_y yes iff answer to I_x is yes.

Obviously, with satisfying these properties, it is concluded that Y is polynomial time reducible from X (X < Y).

• F.    Example of the Proposed Model

The performance for the proposed model has been analyzed with an example on the basis of Fig. 1(b). Here, n 00 and n 34 are considered as the source node and the destination node respectively. In between these two nodes, there are several possible alternative paths for communication. The five paths among these alternatives have been shown in Fig. 2 along with (H_Query, H_Reply) values respectively.

Figure 2: Alternative routing paths for n00 and n34 as source and destination nodes

The path 3 shown in Fig. 2 is selected as the right path according to the criteria with least value of H_Reply, that is 3. Hence the DAG is shown in Fig. 3(a) and 3(b) based on path 3.

Figure 3: DAG representation: (a) QUERY and REPLY shown separately, (b) Final G ’ for path 3

After the establishment of G for path 3, the reachability relation has been introduced for nodes n₀₀ and n₃₄. In addition, the reachability relationship for the entire network (r = 3) is shown in Fig. 4 for the source as n 00 .

Figure 4: The reachability relations for n₀₀in r = 3

• III. Experimental Results

  This work is analyzed with MATLAB version 7.6.0.324 (R2008a) on processor Intel(R) Core(TM) i5-2410M CPU@ 2.30 GHz and RAM 4.00 GB. The following four performance metrics have been introduced here to evaluate the effectiveness for the proposed model.

• A.    Speedup Performance

The dedicated path has been established as a result of our proposed model. So, it is not required any searching delay to finding path for further analysis. In effect, the speed up is increased for the proposed model accordingly rather than traditional [17] one. Speed up here is calculated in terms of transmitting packet through a dedicated path. The behavioral representation between speed up performance and the number of nodes in the network is shown in Fig. 5.

Figure 5: Characteristic curve on speed up Vs. and the number of nodes in the network

• B.    Quality of Service (QoS):

The delay is considered as the QoS metric for the proposed model. Generally, the delay is increased due to the lack of connectivity in end-to-end paths. In our work, the DAG provides the right path for communication in advance. Therefore, the QoS of the network is improved in the aspect of minimized delay. For example, the time s required to traverse n number of hops with a factor 1/p(n), where p(n) denotes QoS metric of the network, is presented as p(n) = ^n log n . Here, the delay D is proportional to s and it is expressed as a function of (;y^=). Therefore, the improved QoS for the proposed model is obtained than the traditional approach [18] as shown in Fig. 6.

Figure 6: Improved QoS of the proposed model

• C.    Dropped Packet Rate (DPR)

It is proportional to the total number of packets dropped in the network. As the dedicated path established in previous, the possibility of dropped packet is less. Therefore, the reduced DPR results for increased transmission as shown in Fig.7.

Figure 7: DPR Vs transmission

• D.    Routing Overhead

Routing overhead is dependent on the total number of packets sent during the transmission. Due to the follow up of the proactive routing approach by the proposed model, the reduced routing overhead is obtained for the number of nodes in the network than the traditional approach [19] as shown in Fig. 8.

Figure 8: Reduced Routing overhead obtained for the proposed model

• VI. Conclusions

The procedure of establishing the reach ability relation through DAG in mobile networks is described in this work. This protocol reduces time complexity for the routing method. The importance of the transitive reduction is discussed to make it more significant in finding the right path. It increases the flexibility of dynamic call routing. Further study on extending this work to construct the routing table is in progress. .