Distribution of on line Contents on Servers with
GA Approach

Neha Mangla

Distribution of on line Contents on Servers with GA Approach

Neha Mangla
Associate Professor, Atria institute of Technology, Bangalore, India

Related article at Pubmed, Scholar Google

Visit for more related articles at International Journal of Advanced Research in Electrical, Electronics and Instrumentation Engineering

Abstract

All the traffic seen by the internet is treated equally which is generally known as Internet neutrality. Internet Neutrality enforces that all network traffic should be treated as equal and Best effort routing policy should be followed. But with the advent of smart applications this is drastically changing. Each network application has its own bandwidth requirement. We face the problem when required bandwidth of critical applications does not match with internet bandwidth. Because of network neutrality principle, core router can’t priorities one traffic over other and critical applications may get impacted. Such types of problems are still in re- search phase As a solution here we will see how application level routing optimization mechanism with GA approach at edge routers can be useful for such types of application.

Keywords

GA, QoS, QoE, Bandwidth, Delay

INTRODUCTION

In recent years, real time applications are widely used. In additions, real-time embedded systems are found in many diverse application areas including electronics, , telecommunications, space systems, medical imaging, and consumer electronics. The transport of real time video streams over the Internet by using wired multimedia delivery faces several challenges such as bandwidth scarcity and limited storage capacity . In addition, there are different applications have various QoS requirements to achieve user’s satisfaction. QoS depends on some of the parameters such as: throughput, bandwidth, delay, error rate control, and packet loss . According to those parameters, the transportation paths are chosen. So the quality of experience in routing algorithms must be adaptable, flexible, and intelligent enough to make a fast decision. To achieve this, a Genetic Algorithm (GA) based on the computational strategies that inspired by natural processes is used. GA is a global optimization technique derived from the principle of nature selection and evolutionary computing or technique. GAtheoretically and empirically-has been proven to be a robust search technique. Each possible point in the search space of the problem is encoded into a suitable representation for applying GA. In GA, each population of individual solutions with fitness value is transformed to a new generation of the population, depending on the Darwinian principle of the survival of the fitness. By applying genetic operators, such as crossover and mutation, GA produces better approximations to the solutions. Many routing algorithms based on GA have been proposed. Selection and reproduction processing at each iteration produces a new generation of approximations.

The stages of a GA are:

• Select initial population.

• Determine the fitness of all initial individuals of the population

• Select the best-ranking individuals to reproduce.

• Breed a new generation through crossover and mutation (genetic operations) and give birth to offspring.

• Evaluate the individual fitness of the offspring.

• Replace the lowest ranked part of population with offspring.

While (terminating Condition)

Here, we propose a new approach based on genetic algorithm to get the ability to use the past experiences to improve current decision-making to choose the efficienct paths.

ROUTING HISTORY

Generally in all Routing algorithms we construct routing tables to forward communication packets to destination and Routing table: for each destination, route(s) or next hop(s) is specified. Problems with these routing methods to be adaptive. RIP and OSPF employ static distance measure such as hop count metric and Uncertainty due to delayed information. Adaptive algorithms may cause oscillation, unreachable routes, etc. To be adaptive, we need to observe frequently and it is unable to observe frequently by broadcasts. Overheads of observation changes network status. However we can reduce overhead as: Broadcast as less frequent as possible. Restrict observations i.e. perform observations of limited routes that is frequently employed (and is worth observation overheads) and by Autonomous control i.e. each node should determines routes independently employing locally obtained information. For that intelligent control needed i.e. prediction algorithm, learning scheme, constructing solution database, etc. Evolutionary computation (EC) is a promising answer. As Evolution is essentially a distributed process. Adaptation in evolutionary process needs less frequent communications (eg. no broadcast is necessary) among individuals. Evolution is considered robust to environmental changes.

Key Idea

In the proposed algorithm, we will exploit existing network routing protocols like BGP. We will learn alternative routes for a content and route application data according to network characteristics and media characteristics. For a video, continuity in video is more important than total download time. In networking terms we say it Quality of Experience. A video requirement for continuous play is dependent on its bandwidth. A Media bandwidth is size of content in one second of video. For example a 800 Kbps video means that each second of this media is 800 Kb bytes in size. The algorithm considers the media bandwidth and network bandwidth of alternate routes and then optimally route requests so that user get best quality of experience.

Assuming Following terminology

C_i - ith content request

Si - Size of contents

fsz - Size of fragment

Bi : Content Bandwidth requirement

So, Ci can be divided into n fragments such that

Ci = Ci0, Ci1, Ci2 .... CSi )/fsz

Ri : ith route

Rbi : Bandwidth of ith route

The user will get the best experience when the rate of fetching the content from network will match the media bandwidth requirement.

It is the fitness function. The objective function is for maximum bandwidth utilization. To implement algorithm requirements are:

• Get the number of total media Requests.

• Get the media bandwidth for each request.

• Get total number o alternate paths/servers.

• Collate the network bandwidth of each path.

• Create Initial population.

• Get total generations.

• Get the crossover point.

• Apply fitness function to each solution and select best solutions.

• Create next generation using elitism ( best solution) and crossover ( solutions)

• repeat last step till either we get optimal solution ( 0 delay ) or till maximum number of generations . The output will be the delay as perceived by user.

Algorithm For Fitness Function

Fitness function will take a proposed solution and will return back the delay as perceived by user. The algorithm for objective function will be

1. For Each server Traverse the media requests queued on it

2. Calculate the total load on server

3. Check how much content will be delivered by the server as per total load and network bandwidth

4. Calculate the total content delivered by all servers for each request.

5. Calculate the difference between content required ( Media bandwidth ) and content delivered for each content.

6. Calculate delay perceived by user ( dividing difference by Media bandwidth)

7. Add the delay for each media request and divide by total request to get average delay perceived by user/

8. Return average delay.

Algorithm For Initial Population

For each content

• Generate a random number between 1 to 100.

• Put the content chunk in proportion to random number on server 1.

• Repeat the same process on remaining servers

• Generate n such solution. Apply fitness function

While (max initial solution)

Algorithm For Crossover

• Select two solutions.

• For each server, switch the content beyond crossover point for both solutions.

Encoding Scheme For Contents On Server

Here we are assuming n servers and m contents. Each content is divided as:

Xa ,Ya…….Za

Xb,Yb…….Zb

Xm, Ym……..Zm

Encoding For Other Solution

There can be many solutions for dividing the contents. Here I am taking representation for two solutions. One was above and second is here.

Crossover In Content Distribution

Here I am showing only one point crossover. In my implementation however I have considered all. In this we will see first fragmented content from both solutions will remain same. Rest will interchange.

Mutation For Content Distribution

Generate any random number.

Random number <= probability chosen

Then

Reduce the portion from 1^st chunk according to random number.

Else

Reduced portion in any other chunk according to random number.

RESULT ANALYSIS

Inputs taken as:

Enter Total content:8

Enter quality of each conent:100 120 60 90 150 70 80 95

Enter Total servers: 4

Enter BW of each server: 180 70 160 40

Enter Total Generation: 5

Enter cross over point: 1

Enter mutation Probability (prob*100): 0.2

Here I am not showing coding and output logs for the inputs with crossover point 1, crossover point 2, crossover point 3. The above part is only a sample for input with crossover point 1.

We have analyzed by taking same inputs with all three crossover operator point. . We have taken the data from 5th generation outputs with crossover one, crossover two and crossover three point operators.

We analyzed these three graphs. We see the best result with crossover point one.

CONCLUSION

QoE is defined as the measure of how well a system or an application meets the user’s expectations. This concept is different from quality of service, which focuses on measuring performance from a network perspective. For instance, QoE focuses on user-perceived effects, such as degradation in voice or video quality, whereas QoS focuses on network effects such as end-to-end delays or jitter. Another important point to note is that measurements in individual nodes may indicate acceptable QoS, but end users may still be experiencing unacceptable QoE.

FUTURE SCOPE

Next generation routing protocols needs to be changed and need to move towards QoE rather than QoS. As Quality of experience is dynamic phenomenon and depends on feedback by different stakeholders, so next generation routing protocols should adapt to dynamic condition and evolve with time.

References

B. M. Leiner, V. G. Cerf, D. D. Clark, R. E. Kahn, L. Kleinrock, D. C. Lynch, J. Postel, L. G. Roberts, and S. S. Wolff, “The Past and Future History of the Internet”, Communications of the ACM, vol. 40, pp. 102.108, February 1997.
D. Awduche, A. Chiu, A. Elwalid, I. Widjaja, and X. Xiao, “Overview and principles of Internet traffic engineering,” IETF, RFC 3272, May 2002.
J. Moy, “OSPF version 2,” IETF, RFC 2328, Apr. 1998. A. Zinin, ‘Cisco IP Routing. Boston, MA” : Addison-Wesley, 2002.
G. Iannaccone et al., “Analysis of Link Failures in an IP Backbone,” Proc. ACM IMW, 2002, pp. 237.
Z. Wang et al., “Quality of Service Routing for Supporting Multimedia Applications,” IEEE JSAC, vol. 14, no. 7, Sept. 1996, pp. 1228–34.
G. Pallis, and A. Vakali, “Insight and Perspectives for Content Delivery Networks,” Communications of the ACM, Vol. 49, No. 1, ACM Press, NY, USA, pp. 101-106, January 2006
G. Peng, “CDN: Content Distribution Network,” Technical Report TR-125, Experimental Computer Systems Lab,Department of Computer Science, State University of New York, Stony Brook, NY, 2003. http://citeseer.ist.psu.edu/peng03cdn.html
M. Day, B. Cain, G. Tomlinson, and P. Rzewski, “A Model for Content Internetworking (CDI),” Internet Engineering Task Force RFC 3466, February 2003. www.ietf.org/rfc/rfc3466.txt
M. Hofmann, and L. R. Beaumont, Content Networking: Architecture, Protocols, and Practice, Morgan Kaufmann Publishers, San Francisco, CA, USA, pp. 129-134, 2005.
T. Plagemann, V. Goebel, A. Mauthe, L. Mathy, T. Turletti, and G. Urvoy-Keller, “From Content Distribution to Content Networks– Issues and Challenges,” Computer Communications, Vol. 29, No. 5, pp. 551-562, 2006.
J. Ni, D. H. K. Tsang, I. S. H. Yeung, and X. Hei, “Hierarchical Content Routing in Large-Scale Multimedia Content Delivery Network,” In Proceedings of IEEE International Conference on Communications, 2003 (ICC ’03), Vol. 2, pp. 854-859, May 2003.
B. Huffaker, M. Fomenkov, D. J. Plummer, D. Moore and K. Claffy, “Distance Metrics in the Internet,” In Proceedings of IEEE International Telecommunications Symposium, IEEE CS Press, Los Alamitos, CA, USA, 2002.
B. Krishnamurthy, C. Willis, and Y. Zhang, “On the Use and Performance of Content Distribution Network,” In Proceedings of 1st International Internet Measurement Workshop, ACM Press, pp. 169-182, 2001.
A. Barbir, B. Cain, R. Nair, and O. Spatscheck, “Known Content Network Request-Routing Mechanisms,” Internet Engineering Task Force RFC 3568, July 2003. www.ietf.org/rfc/rfc3568.txt
M. Howarth et al., “End-to-end Quality of Service Provisioning Through Inter-provider Traffic Engineering,” Comp. Commun., [110] T.C. Bressoud et al., “Optimal Configuration for BGP Route Selection,” Proc. IEEE INFOCOM 2003, pp. 916–26.
A. Riedl, “A hybrid genetic algorithm for routing optimization in IP networks utilizing bandwidth and delay metrics,” presented at the IEEE Workshop on IP Operations and Management (IPOM), Dallas, TX,Oct. 2002.
Fraser, A. P. (1994). Genetic Programming in C++. Technical report 040, University of Salford.
Goldberg, D. E. & Smith, R. E. (1987) Nonstationary Function Optimization using Genetic Algorithms with Diploidy and Dominance. In J.J Grefenstette, editor, Proceedings of the Second International Conference on Genetic Algorithms, 59–68. Lawrence Erlbaum Associates.
Koza, J.R. (1992). Genetic Programming: On the Programming of Computers by Means of Natural Selection. Cambridge, MA:MIT Press.
Cisco white paper, “BGP Bandwidth Link,” http://www.cisco.com/univercd/cc/td/doc/product/software/ios122/122newft/122t /122t2/ftbgplb.htm
T. Bates et al., “Multiprotocol Extensions for BGP-4,” IETF RFC 4760, Jan. 2007.
S. Agarwal et al., “The Impact of BGP Dynamics on Intradomain Traffic,” ACM SIGMETRICS Perf. Eval. Rev., vol. 32, no. 1, June 2004, pp. 319–30.
S. Kalyanaraman, “Load Balancing in BGP Environments using Online Simulation and Dynamic NAT,” presented at the Internet Statistic and Metrics Analysis Wksp. 2001.
M. Howarth et al., “End-to-end Quality of Service Provisioning Through Inter-provider Traffic Engineering,” Comp. Commun., [110] T.C. Bressoud et al., “Optimal Configuration for BGP Route Selection,” Proc. IEEE INFOCOM 2003, pp. 916–26. vol. 29, no. 6, Mar. 2006, pp. 683–02.
Cisco Systems, “BGP Multipath Load Sharing for Both eBGP and iBGP in an MPLS-VPN,” 2005.
Tutorial about Detecting User Agent Types and Client Device Capabilities http://www.developershome.com/wap/detection/
Mobile browser id http://www.zytrax.com/tech/web/mobile_ids.html
Composite Capability/Preference Profiles (CC/PP): A user side framework for content Negotiation .http://www.w3.org/TR/NOTE-CCPP/
CC/PP exchange protocol based on HTTP Extension Framework http://www.w3.org/TR/NOTE-CCPPexchange
RDF Vocabulary Description Language 1.0: RDF Schema http://www.w3.org/TR/rdf-schema/
Mozilla Developer Center – User Agent String Reference –https://developer.mozilla.org/en/User_Agent_Strings_Reference