Adaptive Reset Time In FISH Network For BFF

Adaptive Reset Time In FISH Network For BFF

Nilesh S. Sonawane

P.G. Student, PICT, Pune. darshan26486@gmail.com

Rekha Kulkarni

Asst. Prof., Computer Dept., PICT, Pune.

Kalyani Waghmare

Asst. Prof., Computer Dept., PICT, Pune.

Abstract

In fundamental interconnecting structured homogeneous (FISH) network Bypass Flow-Splitting Forwarding (BFF) algorithm was proposed to forward the packets and make full use of available bandwidth of multipath according to routing oscillation phenomenon in Internet Service Provider (ISP) digital ecosystems (DES) [1]. Constant reset_time considered caused under utilization of channel and thus increase in the packet loss ratio. By making adaptive reset_time for link and refreshing the bandwidth availability with respect to it reduces the packet loss ratio or increases the utilization throughput of channel. With this proposed work we try to optimize the reset_time by making it adaptive for refreshing the hash list for providing the bandwidth availability for each edge. It improves the throughout and reduces the latency.

1. Introduction

   A DIGITAL ecosystem is better as compared to client-server, peer-to-peer, grid, and web services. It is a newly networked architecture with collaborative environment [2][3][4][8][9][11]. Recent years have shown rapid development in underlying network technologies. Networks-based architectures research (NAR) has obtained a quick improvement and the link upgrade of backbone networks provides a core link foundation for NAR. NAR has considered the improvement of the interface hardware technology as an end link foundation. For deploying and implementing NAR the advent of programmable router (PR) has provided a platform foundation. With the infrastructure development of NAR collaboration is also the main challenge to the optimization of the digital ecosystem. The connectivity and traffic demands are not publicly available as no one wishes to share this kind of information for political or economic reasons. Development of BFF [1] was motivated by the lack of collaborations between digital ecosystems and appropriate use of PR improves negotiations and obtains a better collaboration performance in digital ecosystem. The drawbacks of single-path forwarding

   (which can lead to routing oscillation) and fixed granularity forwarding (which can lead to inefficient usage of network bandwidth) were investigated and a bypass flow-splitting forwarding (BFF) algorithm was proposed and it was evaluated using NS2 simulation. Constant reset_time considered causes the updating of available bandwidths for each edge to wait for finishing of the hashlist refreshing process. It has effect on utilization and increases the packet loss ratio. The hash list providing the available bandwidth for each edge is refreshed after reset_time. So every edge has to wait for retrieving its available bandwidth till the reset_time is over. But in this case if actual bandwidth is more than the computed bandwidth in hast list i. e. available bandwidth then there will be less utilization of edge. If the actual bandwidth is less than the available bandwidth in the hash list then more number of packets than the capacity will be sent and it will lead to loss of packets on the way increasing the packet loss ratio. It affects the throughput. We propose the idea of separate reset_time for each edge. The available bandwidth of each edge will be refreshed after respective interval of reset_time. The reset_time is reduced if the required bandwidth is greater than current bandwidth and it is increased in opposite case..

2. Fish network model

   The link-disjoint paths will become more than that in the past with the rapid increase both in bandwidth and links in recent years. These link-disjoint paths can be represented reasonably with the FISH network model. FISH networks are just the abstract model of ISP digital ecosystem and it is ubiquitous in many ISP networks today. Fig 1 shows the FISH network.

   Fig 1 FISH Network Model

   This topology has fish like shape. Nodes 0 and 1 are two hosts, and nodes 2, 3, 4, 5, and 6 are ISPs. In addition, node 2 can have other end users such as nodes 7 and 8. For different perspective, nodes 0 and 1 can also be ISPs. For example, node 1 may be an enterprise network, and it can have many customers itself. The destination address (DA), source address (SA), destination port (DP), and source port (SP) can consist of a flow. With the same DA, the other three can constitute eight combinations. The traditional single- path routing gets next-hop interface only through DA, which makes eight different flows forward to the same path. It is impossible for the single-path routing to provide differentiated services. With the same DA but different SP or DP under different application environment, the traditional single-path routing, such as open shortest path first (OSPF), makes flow-splitting characteristics impossible. With the rapid increase of Internet users, more users have more application requirements and the browsing habits of web users will produce more and more flows of the same destination..

3. Fixed granularity routing

   It is found that the unbalanced traffic causes the routing oscillation which wastes too much processing time of the control plane. This routing oscillation also leads to the increase of delay and jitter in data plane [10]. As the traditional single path cannot split the traffic the available bandwidth cannot be used effectively and concurrently. A fixed forwarding granularity improves the ability of flow splitting as compared to single-path forwarding [5][6][7] but it cannot adapt to diverse applications. Digital ecosystem aims at creating a digital environment supporting the cooperation and development of open and adaptive technologies. Because a fixed forwarding granularity cannot adapt to the unbalanced traffic, BFF algorithm was proposed to provide an adaptive forwarding to make full use of available bandwidth of multiple paths.

4. BFF algorithm

   Different digital ecosystems constitute a digital environment which is the infrastructure of a digital ecosystem. Digital ecosystem includes hardware, together with its associated software. For BFF the Mirror Processing Machine (MPM) and Programmable Router (PR) are the hardware implementation. BFFs three modules contribute to the software implementations.

   Classification Module: It generates the hash index for transport layer packets. It checks if the index is existing in the hash list. If not then it makes new entry for it in the hash list.

   Statistics Module: It calculates the available bandwidth of each path. Then it gets the new forwarding ratio and updates the feedback information for the bypass forwarding module. It computes and resets the hash list at a certain period in order to get a variable flow- splitting.

   Bypass Forwarding Module: When a packet arrives at PR the instructions of the bypass forwarding module run. BFF combines cross-layer idea and revises the IP forwarding original code as the traditional IP protocol only operates on the IP header. BFF changes the strategy where traditional router chooses the next hop only through DA which cannot be achieved in a common router. CISCO and Juniper have opened their IOS and JUNOS. The advent of PR has provided the possibility for BFF bypass operations.

5. Mathematical Model

   Let S be the system considered

   S = {Ip, Op, Drt, RT, Crt, Rbw, Cbw, Is, Fs, Ss, E, N, F}

   Ip = Set of inputs.

   = {N, E, RT, Rbw}

   N = {n1, n2,, nn} Set of nodes

   E = {e1, e2, e3, , ee} Set f Edges Crt = Current Reset Time for each edge.

   RT = Reset time of edge. => compResetTime(edge), (10%Crt) < RT < (40%Crt)

   Drt = Default reset_time for all edges = compDrt(); Rbw = Required bandwidth

   Cbw = Current bandwidth Op = {utilization}

   Fs = Final State = {Cbw, RT, utilization} F = set of functions

   • resetResetTime()

     Reset all edges with default reset time.

   • compDrt()

     Returns the default reset time to be set for all edges initially.

     Avg End to End delay * No of connections/users If Bandwidth =1 Mb

     Packet interval = 10ms Packet size = 500 bytes

     End to End delay = (500 * 8)/1Mb= 14 ms

   • resetResetTime(edge)

     Reset single edge with its respective reset time.

     struct BFF {

     long hashIndex; long packetNum; long packetLenght; long startTime; long endTime; long aliveTime;

     int ratio;

   • resetBW()

     Resets bandwidth for all edges initially with required bandwidth.

   • compResetTime() temp_Crt = Crt

     RT = Crt + (0.02*Crt)

     If RT > (40 % Crt) then RT = temp_Crt

     temp_Crt = Crt

     RT = Crt (0.02*Crt)

     if RT < (10 % Crt) then RT = temp_Crt

   • Utilization is computed with constant reset time and adaptive reset time

   Trx = Receiving time, Ttx = Total transmission time, Tidle = Total idle time.

   U Trx Ttx Trx Ttx Tidle

6. Proposed algorithm

1. For i = 1 to e Do

2. resetBW() // Reset bandwidth for all edges

3. End For

4. compDrt() // Compute default reset time

5. For I = 1 to e Do

6. resetResetTime() // Sets the Reset time for all edges with Drt

7. End For

8. While (true) do

9. if Rbw > Cbw

10. compResetTime() //Reduce resetTime

11. else

12. compResetTime() //Increase resetTime

13. End While

The structure considered is given below.

};

Having constant reset_time affects the bandwidth availability for edges which caused either underutilization of edge or increase in the packet loss ratio. The proposed idea of separate reset_time for each edge adjusts the time required for updating bandwidth availability and thus reduces the underutilization of edge and improves its throughput and also helps in decreasing the packet loss ratio in FISH network model of digital ecosystem considered at ISP level. The performance of the system is observed in the form of latency and throughput mainly.

1. Implementation Details

   The Adaptive Reset Time system is implemented using network simulator NS2.34. Fedora 14 operating system is used. A single desktop machine with 1GB of RAM, 40GB of hard disk and 2.4GHz of processor is sufficient for this implementation. As shown in architecture the network creation and traffic generation module creates a network similar to fundamental interconnecting structured homogeneous network. Links are assigned with bandwidths and packet sizes. The traffic generators are assigned to specific nodes. Type of traffic to be sent over the links is specified. It also specifies the schedule for starting and stopping the traffic generation. The details of traffic generated are stored into trace file. Reset time variation includes the routing module which specifies the adjacency matrix for storing the next hop information.

   Network Creation and Traffic generation Module

   ResetTime Variation

   Throughput Evaluation

   Latency Evaluation

   Fig. 2 Architecture of ART system

   It mentions switchPath and granularity parameters. When switchPath is 1, based on the value of granularity the traffic is splitted on different links. When switchPath is 0, the flow is sent over only one link. It also specifies the compute_routes() method which decides the route to send the traffic over. It also mentions source and destination nodes.

   Throughput and latency evaluation contains the script for retrieving useful data from the trace file obtained from simulation. This data is used for comparing throughput and latency to analyze the performance of system.

2. Experimental results

   An awk script is executed to obtain data from trace file. This data is used to get throughput and latency. Corresponding graphs are shown in figures. Table 1 shows the data obtained for throughput in both static reset time and adaptive reset time. As we can observe from graph there is improvement in throughput with the use of adaprive reset time in fundamental interconnecting strauctured homogeneous network.

   Row Labels	BFF	EBFF	Grand Total
   4	2.5	3.5	6
   5	2.3	3.3	5.6
   6	2.5	3.5	6
   7	2.3	3.3	5.6
   8	2.6	3.6	6.2
   9	2.3	3.3	5.6
   10	2.7	3.7	6.4
   11	2.4	3.4	5.8
   12	2.8	3.8	6.6
   13	2.4	3.4	5.8
   14	2.9	3.9	6.8
   15	2.5	3.5	6
   16	3	4	7
   Grand Total	33.2	46.2	79.4

   Table 1. Throughput data

   Table 2 shows the data obtained for latency in both static reset time and adaptive reset time. As we can observe from graph there is improvement in latency

   with the use of adaptive reset time in fundamental interconnecting structured homogeneous network.

   Row Labels	BFF	EBFF	Grand Total
   4	0.00965	0.00985	0.0195
   5	0.00964	0.00983	0.01947
   6	0.00963	0.00981	0.01944
   7	0.00962	0.00979	0.01941
   8	0.00961	0.00977	0.01938
   9	0.0096	0.00975	0.01935
   10	0.00959	0.00973	0.01932
   11	0.00958	0.00971	0.01929
   12	0.00957	0.00969	0.01926
   13	0.00956	0.00967	0.01923
   14	0.00955	0.00965	0.0192
   15	0.00954	0.00963	0.01917
   16	0.00953	0.00961	0.01914
   Grand Total	0.12467	0.12649	0.25116

   Table 2. Latency data

   It can be seen from gaph that there is improvement in latency.

   Fig. 2 Throughput vs. Time

   Fig. 3 Latency vs. Time

3. Conclusion

   The proposed Adaptive Reset Time system provides variable reset_time for links to get their available bandwidth in fundamental interconnecting structured homogeneous (FISH) network considered in Digital Ecosystem (DES). The Adaptive Reset Time system dynamically changes the reset_time by considering the fixed interval. To measure the performance of proposed ART, it is implemented on a popular open source simulator, NS2.34. The ART decreases the latency time and improves the throughput in FISH network compared to default method of considering constant reset_time.

4. References

1. L. Han, J. Wang, X. Wang, and C. Wang, Bypass Flow- Splitting Forwarding in FISH Networks, IEEE Trans. on INDUSTRIAL ELECTRONICS, VOL. 58, NO. 6, , pp. 2197- 2204, June 2011.

2. E. Chang and M. West, Digital ecosystems: A next generation of the collaborative environment, in Proc. 8th iiWAS, Dec. 2006, pp. 2141.

3. H. Boley and E. Chang, Digital ecosystems: Principles and semantics, in Proc. IEEE-IES DEST, Feb. 2007, pp. 398403.

4. P. Ferronato, Architecture for digital ecosystems, beyond service oriented architecture, in Proc. DEST, Feb. 2007, pp. 660665.

5. L. Han, J. Wang, and C. Wang, Connection-oriented concurrent multipath forward algorithm, J. Southeast Univ. (Natural Science Edition), vol. 38, no. 9, pp. 1216, 2008, Suppl. 1.

6. L. Han, J. Wang, and C. Wang, A novel single-hop delay probe algorithm in multi-homed host, in Proc. 1st ICINIS, Wuhan, China, 2008, pp. 217220.

7. L. Han, J. Wang, and C. Wang, A crosslayer concurrent multipath random forward algorithm, in Proc. 9th ICYCS, Zhangjiajie, China, 2008, pp. 270275.

8. R. Teixeira, K. Marzullo, S. Savage, and G. M. Voelker, Characterizing and measuring path diversity of Internet

   topologies, in Proc. ACM SIGMETRICS Int. Conf. Meas. Modeling Comput. Syst., 2003, pp. 304305.

9. N. Basher, A. Mahanti, C.Williamson, and M. Arlitt, A comparative analysis of web and peer-to-peer traffic, in Proc. 17th WWW, 2008, pp. 287296.

10. R. Musunuri and J. Cobb, An overview of solutions to avoid persistent BGP divergence, IEEE Netw., vol. 19, no. 6, pp. 2834, Nov./Dec. 2005.

11. M. Hadzic, E. Chang, and T. Dillon, Methodology framework for the design of digital ecosystems, in Proc. IEEE Int. Conf. Syst., Man Cybern. ISIC, Oct. 2007, pp. 7 12.