دانلود رایگان مقاله پیش بینی ترافیک آینده با استفاده از مدل های پنهان مارکوف

چکیده  

            تخمین و پیش بینی حجم ترافیک شبکه موضوع تحقیقاتی مهمی است که توجه مداوم انجمن شبکه و انجمن یادگیری ماشین را جلب کرده است. اگر چه کار زیادی بر روی تخمین و پیش بینی ماتریس ترافیک با استفاده از مدل های سری زمانی، تجزیه ماتریس با رنک پایین وجود دارد، بر اساس آنچه ما و همکاران می دانیم کارهای کمی برای بررسی این مسئله که آیا ما می توانیم حجم شبکه مبتنی بر برخی آمارگان (آماره های) های ترافیک که جمع آوری آنها، کم هزینه تر هستند مانند جریان شمارش flow count ، تخمین زده یا پیش بینی کنیم. در این مقاله، مدلی برای ارتباط بین حجم ترافیک و آمارگان (آماره های) های ساده  مانند جریان flows با استفاده مدل پنهان مارکف پیشنهاد می دهیم که بر اساس آن می توانیم از اندازه گیری مستقیم حجم داده اجتناب کنیم اما در عوض حجم ترافیک پنهان شده مبتنی بر آن آمارگان (آماره های) ساده جریان flow که به وسیله برخی تکنیک‌های طراحی جمع آوری شده اند، تخمین زده و پیش بینی کنیم. سادگی و تاثیرگذاری روش پیشنهادی را با استفاده از تعدادی شبه شبیه سازی و نتایج تجربی حاصل از داده واقعی نشان می دهیم.

1. مقدمه

              تخمین و پیش بینی حجم ترافیک شبکه  یک مسئله مهم تحقیقاتی شبکه است. تخمین و پیش بینی دقیق  حجم ترافیک ، به ویژه ماتریس ترافیک ، برای کنترل مسیریابی شبکه ، کنترل ازدحام ، تخصیص منابع شبکه و برنامه ریزی بلند مدت سودمند است و به این ترتیب در انجمن شبکه و انجمن یادگیری ماشین توجه زیادی را به خود جلب کرده است. در کارهای موجود عمدتا دو جریان اصلی از تحقیق وجود دارد. جریان اصلی اول فرض می کند که در هر بازه زمانی مشخص ، حجم ترافیک مجموع  (تعداد بایت) بین یک جفت منبع مقصد معین که می تواند اندازه گیری شود، اتفاق می افتد و سپس یک مدل آنالیز سری زمانی مانند مدل های خطی شامل AR ، ARMA، ARIMA ، FARIMA [6] ، [7] ، [16] ، [14] و مدل های غیر خطی شامل ANN ، RNN ، GARCH [10]، [17] ، [2]، [8] برای پیش بینی ترافیک آینده استفاده شده است. محدودیت این دسته از رویکردها این است که لازم است به طور مستقیم حجم ترافیک بازه های زمانی قبلی را به منظور پیش بینی حجم های ترافیک برای بازه زمانی آینده اندازه گیری نماییم. با این وجود، اندازه گیری مستقیم حجم داده برای عملی شدن به ویژه در شبکه با سرعت خیلی بالا  بسیار هزینه بر است، و بنابراین اگرچه این رویکرد ساده است اما در عمل، مقیاس‌پذیر نیست. مسیر اصلی دیگر رویکردها معمولاً توموگرافی شبکه نامیده می شوند [3] ، [1] ، [9] ، [4] که مکمل اولین رویکرد مسیر اصلی است. ایده توموگرافی شبکه برای  تخمین حجم ترافیک شبکه مبتنی بر مشاهدات دیگری مانند استفاده از لینک link utilization است. استفاده از لینک link utilization ، حجم ترافیک مجموع از جریان هایی flow است که از طریق آن لینک عبور می کنند. در نتیجه، معمولاً یک سیستم خطی معین (قطعی) برای توصیف رابطه بین کاربرد لینک و حجم ترافیک پنهان وجود دارد. با این حال ، یکی از محدودیت های مهلک رویکرد توموگرافی شبکه این است که سیستم خطی همیشه نامعین است زیرا در یک شبکه تعداد لینک ها به مراتب کمتر از تعداد جفت های منبع مقصد است. بازیابی حجم ترافیک پنهان با استفاده ازمقدار محدودی از استفاده در لینک link utilizations بسیار دشوار است.

              در این مقاله ، با توجه به محدودیت های قوی در کارهای موجود، احتمال حدس زدن حجم ترافیک را بر اساس برخی آمارگان (آماره های) های جریان مانند تعداد جریان های بازه زمانی معین که جمع آوری بسیار راحت تری دارند را بررسی می کنیم. می دانیم، کار ما در استخراج وابستگی بین شمارش های جریان flow count و حجم جریان به منظور تخمین و پیش بینی حجم ترافیک، پیشگام است. پیشنهاد می کنیم از مدل پنهان مارکف برای تشریح ارتباط شمارش جریان flow count و حجم جریان و هم چنین رفتار پویای موقت هر دو استفاده کنیم. ما از الکوریتم های بسیار جدیدی مانند قانون کرنل بیز و شبکه های عصبی بازگشتی با واحد حافظه طولانی کوتاه مدت (واحد LSTM) برای آموزش مدل و استفاده از مدل برای پیش بینی ترافیک آینده استفاده می کنیم.

               در ادامه این مقاله ، در بخش II، درباره کارهای موجودی که  برای تخمین و پیش بینی ترافیک شبکه نقش داشته اند، بحث می نماییم؛ در بخش III، مدل مارکوف پنهان خود را برای تخمین و پیش بینی ترافیک آینده با استفاده از قانون [5]Kernel Bayes [15] و همچنین شبکه عصبی بازگشتی پیشنهاد می کنیم. در بخش IV، آزمایش هایی را با استفاده از داده نیمه شبیه سازی شده و داده واقعی ترافیک شبکه انجام می دهیم؛ در بخش V از این مقاله نتیجه گیری می نماییم.

2. تخمین و پیش بینی ترافیک شبکه

              در دهه های گذشته، کارهای زیادی برای حل مشکل تخمین و پیش بینی ترافیک شبکه منتشر شده است. همانطور که در مقدمه بحث شد، آن کارها عمدتاً به دو دسته اصلی تقسیم می شوند. در یک مورد فرض می کنیم که ما می توانیم ترافیک شبکه مجموع در فواصل زمانی متوالی را مشاهده کنیم و یک مدل ریاضی برای پیش بینی ترافیک آینده را با روشی ساده به وجود آوریم[6]، [7]، [16]، [14]، [10 ] ، [17] ، [2] ، [8]. دسته دیگر روشهایی که به آن توموگرافی شبکه گفته می شود از اندازه گیری مستقیم ترافیک شبکه بین هر دو موردی که مورد مذکور جلوگیری می کند، اما در عوض سعی می کند با استفاده از برخی از link utilizations، حجم ترافیک پنهان را بازیابی کند. در این بخش، به طور مختصر در مورد فرمول ها و همچنین محدودیت های این دو گروه روش ها صحبت خواهیم کرد.

A. پیش بینی غلتان با استفاده از مشاهدات قبلی

              این گروه از روشها [3] ، [1] ، [9] ، [4] فرض می کنند که ما قادریم حجم ترافیک را به  صورت دنباله مشاهده کنیم. هدف ما پیش بینی ترافیک آینده بر اساس مشاهدات قبلی است. اساس این دسته از روشها، خود شباهتی در ترافیک شبکه است. به طور کلی، می توان از فرمول زیر برای توصیف روند پیش بینی استفاده کرد:
 xt+1 = f(xt, ··· , xt−p+1, t, ··· , t−q+1) + t+1,

  x_t حجم ترافیک منتقل شده در زمان t از آن دسته از جفت های مقصد است که مورد توجه است، ϵ_t خطای پیش بینی در زمان t است ، p تعداد مشاهدات قبلی است که برای پیش بینی استفاده می شود و q تعداد خطاهای پیش بینی قبلی است که برای تصحیح پیش بینی استفاده می شوند.

Abstract

          Network traffic volume estimation and prediction is an important research topic that attracts persistent attention from the networking community and the machine learning community. Although there has been extensive work on estimating or predicting the traffic matrix using time series models, low rank matrix decomposition et. al, to the best of our knowledge, there is few work investigating the problem whether we are able to estimate and predict the traffic volume based on some statistics of the traffic which are much less costly to collect, for example, the flow counts. In this paper, we propose to model the relationship between the traffic volume and simple statistics about flows using a Hidden Markov Model based on which we can avoid direct measurement of the traffic volume but instead we estimate and predict the hidden traffic volume based on those simple flow statistics which are collected by some sketch techniques. We demonstrate the feasibility and effectiveness of our proposed method using some semi-simulation and real data experimental results.

I. INTRODUCTION

             Network traffic volume estimation and prediction is a very important research problem in networking. Accurate estimation and prediction of the traffic volume, especially the traffic matrix, is beneficial to network routing control, congestion control, network resource allocation and long term planning, and thus it has attracted extensive attention in the networking community and the machine learning community. There are mainly two main streams of research in existing works. The first main stream assumes that at any given time slot, the aggregated traffic volume (the number of bytes) transmitted between a certain source destination pair can be measured, and then a time series analysis model such as linear models including AR,ARMA,ARIMA,FARIMA [6], [7], [16], [14] and nonlinear models including ANN,RNN,GARCH [10], [17], [2], [8] is applied to predict the future traffic. The limitation of this category of approaches is that we need to directly measure the traffic volume of the previous time intervals in order to predict the traffic volumes for the future time interval. However, direct measurement of the traffic volume is too expensive to be feasible, especially in the large scale high speed network, and thus although this approach is simple but in practice, it is not well scalable. The other main stream of approaches is usually termed network tomography [3], [1], [9], [4] which is complementary to the first main stream approach. The idea of network tomography is to estimate the network traffic volume based on other observations such as the link utilizations. Link utilization is the aggregated traffic volume of those flows going through that link. Consequently, usually there is a deterministic linear system to describe the relationship between the link utilizations and the hidden traffic volumes. However, one of the fatal limitation of the network tomography approach is that the linear system is always underdetermined as the number of links is far less than the number of source destination pairs in a network. Recovering the hidden traffic volume from the limited amount of link utilizations is extremely difficult.

               Realizing the strong limitations of existing works, in this paper, we investigate the possibility of inferring the hidden traffic volume based some flow statistics which are much easier to collect such as the number of flows in a certain time interval. To the best of our knowledge, our work is the pioneer work exploiting the dependence between the flow counts and the flow volume to estimate and predict the traffic volume. We propose to use a Hidden Markov Model to describe the relationship of the flow count and the flow volume and also the temporal dynamic behavior of both. We use the stateof-the-art algorithms such as Kernel Bayes Rule (KBR) and Recurrent Neural Network (RNN) with Long Short Term Memory unit(LSTM unit) to train the model and apply the model to predict the future traffic.

               In the rest of this paper, in Section II, we discuss the existing works which are contributed to estimating and predicting the network traffic; in Section III, we propose our hidden Markov model to estimate and predict the future traffic using Kernel Bayes Rule [5], [15] as well as Recurrent Neural Network; in Section IV, we conduct experiments using semi-simulated data and real network traffic data; in Section V, we conclude this paper.

II. NETWORK TRAFFIC ESTIMATION AND PREDICTION

               In the past decades, there are large amounts of works published to solve the network traffic estimation and prediction problem. As discussed in the introduction, those works are mainly divided into two main categories. One is to assume that we are able to observe the network traffic aggregated in sequential time intervals and we build mathematical model to predict the future traffic in a rolling way[6], [7], [16], [14], [10], [17], [2], [8]. The other category of methods termed network tomography avoid direct measurement of network traffic transmitted between any two end hosts in which we are interested, but instead try to recover the hidden traffic volume using some link utilizations. In this section, we will briefly discuss the formulations as well as the limitations of these two categories of methods.

A. Rolling Prediction Using Past Observations

              This category of methods [3], [1], [9], [4] assume that we are able to observe the traffic volume in a sequential way. Our goal is to predict the future traffic based on the past observations. The foundation of this category of methods is the self-similarity of the network traffic. In general, we can use the following formulation to describe the prediction process:

xt+1 = f(xt, ··· , xt−p+1, t, ··· , t−q+1) + t+1,

where xt is the traffic volume transmitted at time t of those source destination pairs in which we are interested, t is the prediction error at time t, p is the number of past observations that are used for prediction and q is the number of past prediction errors that are used to correct the prediction.

چکیده  
1. مقدمه
2. تخمین و پیش بینی ترافیک شبکه
A. پیش بینی غلتان با استفاده از مشاهدات قبلی
B. توموگرافی شبکه
3. حدس زدن و پیش بینی حجم ترافیک با استفاده از HMM ها
A. آمارگان (آماره های) ساده جریان و تکنیک طراحی
B. مدل های پنهان مارکف 
4. آزمایشات 
A. شبه شبیه سازی
B. ترافیک شبکه واقعی 
5. نتیجه گیری
منابع

Abstract
1. INTRODUCTION
2. NETWORK TRAFFIC ESTIMATION AND PREDICTION
A. Rolling Prediction Using Past Observations
B. Network Tomography
3. INFERRING AND PREDICTING TRAFFIC VOLUME USING HMMS
A. Simple Flow Statistics and Sketch Technique
B. Hidden Markov Models
4. EXPERIMENT
A. Semi-Simulation
B. Real Network Traffic
5. CONCLUSION
REFERENCES