مدل سازی ازدحام شبکه با استفاده از زنجیره های مارکوف دو متغیره زمان- پیوسته
چکیده
ما یک مدل ازدحام برای شبکه‌های کامپیوتر براساس یک زنجیره‌ی مارکوف دو متغیره‌ی حالت محدود همگن زمان- پیوسته در نظر می‌گیریم. این مدل می‌تواند به همراه شبیه‌سازی کامپیوتر برای ارزیابی عملکرد پروتکل‌ها و کاربردها در یک شبکه که با تأخیر مسیر تصادفی و تلفات بسته به‌دلیل ازدحام ترافیک همراه است، مورد استفاده قرار گیرد. فقط یکی از فرآیندهای زنجیره‌ی مارکوف دو متغیره قابل مشاهده است. در کاربردهای ما، فرآیند بیانگر ازدحام ترافیکی پویا در راستای یک مسیر شبکه در عبارت‌های تأخیر بسته یا تلفات بسته می‌باشد. فرآیند اساسی دیگر بر روی ویژگی‌های استاتیکی فرآیند قابل مشاهده اثر می‌گذارد. بنابراین برای مثال، زمان بین دو ورود رویداد مشاهده شده از نوع فازی است. حالت کلی فرآیند دو متغیره‌ی مورد بررسی در این پژوهش، فرضیاتی بر روی ساختار مولد زنجیره ندارد و بنابراین هیچکدام از فرآیندهای اساسی و قابل مشاهده برای مارکوف ضروری نمی‌باشد. ما یک روند بیشینه کردن امید ریاضی برای ارزیابی کردن تولید در یک زنجیره‌ی مارکوف دو متغیره که یک مسیر نمونه در فرآیند قابل مشاهده فراهم می‌کند، ارائه می‌دهیم. ما عملکرد الگوریتم ارزیابی را جهت تقریب اولیه‌ی روند ارزیابی براساس یک نمونه‌گیری زمانی به‌دست می‌آوریم.
1- مقدمه
شبیه‌سازی کامپیوتر اغلب برای ارزیابی عمکلرد پروتکل‌ها و کاربردهای شبکه مورد استفاده قرار می‌گیرد. صحت ارزیابی عملکرد شبکه به‌شدت بر روی دقت رفتارهای شبکه‌ی مرتبط که به‌وسیله‌ی مدل شبیه‌سازی بیان شده است، بستگی دارد. در یک وضعیت مطلوب، مدل شبیه‌سازی باید ویژگی‌های برجسته‌ی شبکه که بر عملکرد پروتکل یا کاربردهای ارزیابی شده تأثیر می‌گذارد را خلاصه کند. همانطور که حائز اهمیت است، مدل شبیه‌سازی باید به‌اندازه‌ی کافی ساده باشد تا نتایج عملکرد بتواند در یک مقدار معقول زمان یا رویداد در زمان- واقعی به‌دست آید.
5- نتیجه‌گیری
ما یک مدل ازدحام شبکه براساس یک زنجیره‌ی مارکوف دو متغیره‌ی زمان- گسسته‌ی حالت محدود را در نظر گرفتیم و بازگشتی‌های صریح پیشرو- پسرو را برای تخمین زدن پارامتر این مدل در مفهوم درست‌نمایی بیشینه از طریق مشاهده کردن نمونه‌های به‌دست آمده در یک شبکه‌ی واقعی توسعه دادیم. داده‌های آموزشی یا قابل مشاهده شامل مقادیر تأخیری بسته یا نشان‌دهنده‌ی تلفات بسته می‌باشند که به‌وسیله‌ی بسته‌های پروب ارسالی در راستای مسیر یک شبکه به‌دست می‌آیند. پارامتر مدل زنجیره‌ی مارکوف دو متغیره می‌تواند جهت استخراج یک شبیه‌سازی رویدادگرای مؤثر برای ارزیابی عملکرد پروتکل‌ها و کاربردهای شبکه مورد استفاده قرار گیرد.
Abstract
We consider a model of congestion for computer networks based on a continuous-time finite-state homogeneous bivariate Markov chain. The model can be used to evaluate, via computer simulation, the performance of protocols and applications in a network with random path delays and packet losses due to traffic congestion. Only one of the processes of the bivariate Markov chain is observable. In our application, that process represents the dynamics of traffic congestion along a network path in terms of packet delay or packet loss. The other is an underlying process which affects statistical properties of the observable process. Thus, for example, the interarrival time of observed events is phase-type. The general form of the bivariate process studied here makes no assumptions on the structure of the generator of the chain, and hence, neither the underlying process nor the observable process is necessarily Markov. We present an expectation-maximization procedure for estimating the generator of a bivariate Markov chain given a sample path of the observable process. We compare the performance of the estimation algorithm to an earlier approximate estimation procedure based on time-sampling.
I. INTRODUCTION
Computer simulation is often used to evaluate the performance of network protocols and applications. The validity of network performance evaluation depends heavily on the accuracy to which the relevant network behaviors are represented by the simulation model. Ideally, the simulation model should abstract the salient features of the network that impact the performance of the protocol or application to be evaluated. Just as importantly, the simulation model should be sufficiently simple so that performance results can be obtained in a reasonable amount of time or even in real-time.
V. CONCLUSION
We considered a model of network congestion based on a finite-state continuous-time bivariate Markov chain and developed explicit forward-backward recursions for estimating its parameter in the maximum likelihood sense from observation samples obtained from a real network. The observation or training data consists of packet delay values or packet loss indications obtained by sending probe packets along a network path. The parameter of the bivariate Markov chain model can be used to drive an efficient event-driven simulation for evaluating the performance of network protocols and applications.
(جهت بزرگ نمایی روی عکس کلیک نمایید)
چکیده
1- مقدمه
2- زنجیره‌ی مارکوف دو متغیره‌ی زمان- پیوسته
الف) تراکم مسیر نمونه‌ی مشاهده شده
ب) بازگشت‌های پیشرو- پسرو
3- الگوریتم EM
الف) تخمین تعداد پرش‌ها
ب) تخمین زمان توقف
4- پیاده‌سازی و مثال عددی
الف) الگوریتم مبتنی بر بام
ب) الزامات محاسباتی و ذخیره‌سازی
ج) مثال عددی
5- نتیجه‌گیری
Abstract
I. INTRODUCTION
II. CONTINUOUS-TIME BIVARIATE MARKOV CHAIN
A. Density of observed sample path
B. Forward-backward recursions
III. EM ALGORITHM
A. Number of jumps estimate
B. Dwell time estimate
IV. IMPLEMENTATION AND NUMERICAL EXAMPLE
A. Baum-based algorithm
B. Computational and storage requirements
C. Numerical example
V. CONCLUSION
- ترجمه فارسی مقاله با فرمت ورد (word) با قابلیت ویرایش، بدون آرم سایت ای ترجمه
- ترجمه فارسی مقاله با فرمت pdf، بدون آرم سایت ای ترجمه