برخی از این وظایف با هم در ارتباط هستند. هر ارتباط با شش مشخصه نشان داده می شود که عبارتند از:
: این مشخصه شماره مربوط به وظیفهی مبدا ارتباط مورد نظر را نشان میدهد.
: این مشخصه شماره مربوط به وظیفهی مقصد ارتباط مورد نظر را نشان میدهد.
: مهلت اتمام ارتباط میباشد که بیانگر آن است که همه بستههای متعلق به این ارتباط باید در طول یک حد تاخیر مشخصی حتی در بدترین موقعیتها، از مسیریاب مبدا به مسیریاب مقصد تحویل داده شوند.
: فاصله زمانی بین آزاد شدن بستههای متوالی یک ارتباط را دوره آن ارتباط میگویند. این معیار ثابت است و برای هر ارتباط با نشان داده می شود.
: این معیار مقدار دادهای که باید در یک ارتباط منتقل شود را نشان میدهد. این مشخصه می‌تواند براساس تعداد بیت هر بسته یا تعداد فلیتها باشد.
: این معیار اولویت هر ارتباط را نشان میدهد که در این جا هر ارتباط یک اولویت یکتا دارد و میباشد. عدد ۱ بالاترین اولویت را نشان میدهد و هر چه عدد بزرگتر می شود اولویت کمتر می شود.
هنگامی که این ارتباطات بر روی معماری شبکه بر تراشه نگاشت شوند به آنها جریانهای ترافیکی گفته می شود که در واقع جریانی از بستهها میباشد که مسیر یکسانی را از وظیفه مبدا تا وظیفه مقصد طی می کنند و در طول مسیر به میزان سرویس یکسانی نیاز دارند. بنابراین تنها تفاوت یک جریان ترافیکی با ارتباط متناظرش آن است که جریان ترافیکی شامل مسیری از وظیفه مبدا به وظیفه مقصد میباشد. از این رو هر جریان ترافیکی علاوه بر همان مشخصههای مربوط به ارتباط متناظرش دو ویژگی دیگر نیز دارد که عبارتند از:
: این معیار بیشترین تاخیر شبکه برای جریان ترافیکی مورد نظر با در نظر گرفتن هیچگونه تداخلی میباشد که در بخش ۴-۳-۳ بیشتر در مورد آن توضیح داده خواهد شد.
: میزان تاخیر آزاد شدن است که این معیار برای یک جریان ترافیکی بیانگر بیشترین انحراف بستههای متوالی آزاد شده از دوره تناوبشان است. اگر یک بسته از جریان ترافیکی در زمان a ایجاد شود آنگاه آن بسته برای انتقال در زمان a+ ، آزاد خواهد شد و دارای مهلت اتمام، a+ است.
طبق [۴۹] مدل کاربرد همچنین دارای فرضیات زیر میباشد:
چون در پایان اجرای وظیفه مبدا، ارتباط با فرستادن بستههای اطلاعاتی شروع می شود بنابراین مهلت اتمام و دوره ارتباط برابر با مهلت اتمام و دوره وظیفه مبدا میباشد.
مهلت اتمام یک وظیفه یا یک ارتباط کوچکتر یا مساوی با دوره تناوب آن میباشد .
اولویت هر جریان ترافیکی وابسته به اولویت وظیفه مبدا آن جریان میباشد به عبارتی اگر وظیفه i اولویت بالاتر از وظیفه j داشته باشد، جریان ترافیکی که از وظیفه i شروع می شود اولویت بالاتری نسبت به جریان ترافیکی که از وظیفه j شروع می شود، دارد.
بدترین زمان اجرا یا همان برای هر وظیفه بستگی به نوع هسته پردازشی که وظیفه مورد نظر بر روی آن اجرا می شود، دارد.
همه وظایف در یک زمان آزاد میشوند. به این زمان لحظه بحرانی[۱۴۰] گفته می شود. طبق تعریف ارائه شده در [۴۸] لحظه بحرانی زمانی است که یک وظیفه همزمان با درخواستهای همه وظایف با اولویت بالاتر، درخواست میدهد. در واقع این فرض به خاطر آن است که بتوان تحلیلهای مربوط به بدترین تاخیر شبکه بسته را انجام داد زیرا بدترین تاخیر شبکه بسته[۱۴۱] زمانی اتفاق میافتد که بسته جریان ترافیکی موردنظر هم زمان با همه بستههای جریانهای ترافیکی اولویت بالاتر آزاد شود.
فرض می شود که جریانهای ترافیکی توسط یک سیاست تخصیص اولویت ممکن اولویت بندی شده اند. سیاست تخصیص اولویت می تواند براساس روشهای متفاوتی باشد مثلا در [۱۲] از روش نرخ یکنواخت[۱۴۲] استفاده شده است که براساس این روش، برای دو وظیفه یا جریان ترافیکی L و M اگر period(L) > period(M) باشد آنگاه priority(L) < priority(M) خواهد بود. بحث تخصیص اولویت در اینجا مطرح نشده است
وظایف و جریانهای ترافیکی مستقل از یکدیگر هستند و هیچگونه وابستگی داده بین آنها وجود ندارد.
مدل معماری شبکه بر تراشه
معماری شبکه بر تراشه که در اینجا در نظر گرفته شده است دارای هستههای پردازشی ناهمگن است یعنی عناصر پردازشی متفاوت میباشند زیرا سیستم ناهمگن علی رغم اینکه انعطافپذیری و قابلیت استفاده مجدد کمتری نسبت به حالت همگن دارد اما دارای کارایی بهتر و مصرف توان کمتری میباشد [۱۱].
با توجه به ساختار ساده و قابلیت پیادهسازی آسان همبندی توری، این نوع از همبندی برای شبکه بر تراشه در نظرگرفته شده است. متناسب با همبندی توری، در اینجا از الگوریتم مسیریابی قطعی xy استفاده شده است که مطابق با این الگوریتم بستههای متعلق به یک جریان ترافیکی همیشه یک مسیر یکسان کمینه را بین مبدا تا مقصد طی می کنند که این مسیر در زمان طراحی مشخص شده است.
در حال حاضر روش راهگزینی خزشی در بسیاری از پیادهسازیهای شبکه روی تراشه مانند Æthereal و HERMES استفاده می شود اما راهگزینی خزشی به خودی خود در برابر رقابت در شبکه آسیبپذیر است و اثرات آن قابل پیش بینی نیست [۷۵]. بنابراین از راهگزینی خزشی مبتنی بر اولویت استفاده می شود. در واقع در روش راهگزینی خزشی معمول، فلیتهای داده در مسیریابها براساس سیاستهای اول ورود-اول سرویس[۱۴۳] یا نوبت گردشی[۱۴۴] به درگاه خروجی دسترسی پیدا می کنند اما این سیاستها به دلیل عادلانه بودن[۱۴۵] و میانگین کارایی نسبتاً خوب، برای حالتهایی غیر از بیدرنگ بودن مناسب است اما در اینجا که ارتباطات به صورت بیدرنگ میباشد شبکه باید تضمین کند که هر بسته بیدرنگ محدودیتهای زمانیاش را رعایت کند [۷۵]. بنابراین در این مسئله از سیاست داوری براساس اولویت[۱۴۶] در مسیریابهای شبکه استفاده می شود. مسیریابها برای استفاده از این سیاست، دارای کانالهای مجازی میباشند و همانطور که در شکل ۴-۲ نشان داده شده است، به تعداد سطوح اولویت در هر درگاه خروجی کانال مجازی وجود دارد. در واقع همانند جریانهای ترافیکی که دارای اولویت میباشند، به کانالهای مجازی نیز اولویت تخصیص داده می شود و هر کانال مجازی اولویت مربوط به خودش را دارد[۴۸]. بنابراین یک بسته با اولویت i تنها به کانال مجازی با اولویت i دسترسی دارد.
با توجه به شکل ۴-۲ در هر لحظه داور[۱۴۷] فلیتهایی که متقاضی یک پیوند خروجی مشترک هستند، متناسب با اولویتشان به سمت درگاه خروجی هدایت می کند. همچنین برای اطمینان از فضای میانگیر کافی برای نگهداری دادهای که به مسیریاب بعدی فرستاده می شود، از سیگنالهای Credit استفاده می شود. اگر بسته با اولویت بالاتر به دلیل آنکه در جای دیگری در شبکه بلاک شده است نتواند داده بفرستد، بسته با اولویت بالاتر بعدی به پیوند خروجی دسترسی پیدا می کند. بنابراین زمان سرویس مجاز برای یک جریان ترافیکی، برابر تمامی زمانهایی است که هیچ جریان ترافیکی با اولویت بالاتر برای همان پیوند مشترک رقابت نکند[۶۶].
شکل ۴‑۲- درگاه خروجی مسیریاب در داوری براساس اولویت[۴۸]
مدل تحلیلی بررسی قابلیت زمانبندی
برای بررسی قابلیت زمانبندی وظایف و ارتباطات بین آنها از دو مدل تحلیلی استفاده شده است. یک مدل برای بررسی زمان پاسخ وظایف و مدلی دیگر برای محاسبه بدترین تاخیر شبکه بستههای یک جریان ترافیکی میباشد.
مدل تحلیلی بررسی زمان پاسخ وظایف:
در اینجا فرض شده است که هر هسته پردازشی می تواند چندین وظیفه را اجرا کند. در واقع هر هسته برای انجام زمانبندی وظایف، دارای صفهای اولویتدار میباشد و از داوری انحصاری اولویتی[۱۴۸] استفاده می کند. به عبارتی وظیفه با اولویت بالاتر برای اجرا شدن توسط هسته مربوطه نسبت به وظایف اولویت پایینتر حق تقدم دارد. بنابراین برای بررسی زمانبندی دقیق وظایف بر روی یک هسته، از مدل تحلیلی ارائه شده در [۱۲] جهت محاسبه بدترین زمان پاسخ وظایف استفاده شده است که در این مدل زمانبندی انحصاری با اولویتهای ثابت به کار برده شده است.
۴‑۱
در این مدل با توجه به معادله ۴-۱، بدترین زمان پاسخ وظیفه با نشان داده می شود که این معیار برابر است با فاصله زمانی بین آزاد شدن وظیفه تا هنگامی که با در نظر گرفتن تداخل ناشی از وظایف اولویت بالاتر وظیفه مورد نظر اجرایش تمام شود. تابع نشاندهنده تمام وظایف با اولویت بالاتر از وظیفه i میباشد که همه این وظایف بر روی یک هسته یکسان اجرا میشوند. وظیفه i درصورتی قابلیت زمانبندی بر روی هسته مورد نظر را دارد که باشد. همان طور که در معادله فوق ملاحظه می شود، متغیر در دو طرف معادله مشاهده می شود بنابراین برای حل آن از یک روش تکرار شونده استفاده می شود. در این روش بیانگر مقدار در تکرار nام و میباشد. این تکرار تا هنگامی که شرط برقرار گردد،ادامه مییابد. لازم به ذکر است که در تکرارهای این معادله اگر شود، تکرارها متوقف می شود و به مفهوم آن است که وظیفه مورد نظر بر روی آن هسته قابل زمانبندی نمی باشد.
مدل تحلیلی محاسبه بدترین تاخیر شبکه یک جریان ترافیکی:
هر جریان ترافیکی دارای یک تاخیر شبکه پایهای بیشینه[۱۴۹] میباشد که با نشان داده می شود و برابر با مدت زمان لازم برای رسیدن بستههای یک جریان ترافیکی به مقصدشان، بدون حضور هیچ گونه رقابتی میباشد. این تاخیر با بهره گرفتن از مسافت مسیریابی بین مبدا و مقصد، اندازه بسته، پهنای باند پیوند و … مشخص می شود. برای محاسبه تاخیر شبکه پایهای بیشینه با توجه به [۷۵] از معادله ۴-۲ استفاده می شود.
۴‑۲
در این رابطه H مشخصکننده تعداد گامهای مسیر بین گره مبدا و مقصد میباشد. . لازم به ذکر است که تعداد گامهای مسیر در واقع همان تعداد پیوندهای طی شده مسیر میباشد. پارامتر بیانگر تاخیر لازم برای عبور از یک پیوند و تاخیر مورد نیاز برای پردازش در هر مسیریاب است. در این رابطه پهنای باند پیوند است که اگر در فرضیات مسئله برابر با تعداد بیتهای بسته باشد، عبارت نشان دهنده تعداد فلیتهای بسته میباشد. بنابراین دو عبارت اول بیانگر مدت زمان لازم برای عبور فلیت سرآیند از مسیریاب مبدا تا مسیریاب مقصد و عبارت آخر بیانگر زمان مورد نیاز برای عبور سایر فلیتهای بسته از مسیر فعلی ایجاد شده میباشد. در اینجا بیشینه حالت تاخیر شبکه پایه در نظر گرفته شده است زیرا اگر یک جریان ترافیکی بیدرنگ، تحت این حالت بیشینه، مهلت اتماماش را رعایت کند آنگاه آن جریان ترافیکی حتما برای هر تاخیر شبکه پایه دیگری نیز مهلت اتماماش را رعایت می کند. لازم به ذکر است که در این حالت محاسبه تاخیر شبکه، رقابتها در نظر گرفته نشده است و طبیعتا در نظر گرفتن آنها موجب افزایش تاخیر شبکه میشوند. بنابراین برای مشخص کردن حد بالای تاخیر شبکه برای یک جریان ترافیکی بیدرنگ، لازم است که علاوه بر تاخیر شبکه پایهای بیشینه، تداخلهای ناشی از رقابتها نیز در نظر گرفته شوند.
مهمترین عامل موثر در تعیین حد بالای تاخیر در شبکه تداخلها میباشند. با توجه به سیاست داوری بر اساس اولویت، تنها جریانهای ترافیکی که دارای اولویت بالاتری نسبت به جریان ترافیکی فعلی هستند موجب تداخل میشوند. در [۴۸] دو نوع تداخل برای بررسی ارتباط بین جریانهای ترافیکی معرفی شده است : تداخل مستقیم[۱۵۰] و تداخل غیر مستقیم[۱۵۱] که برای جریان ترافیکی ، با مجموعههای و نشان داده میشوند. در حالت تداخل مستقیم جریان با اولویت بالاتر حداقل یک پیوند مشترک با جریان مورد بررسی دارد. بنابراین این جریانهای اولویت بالاتر یک رقابت مستقیمی را به جریان فعلی تحمیل می کنند. شامل همه جریانهای ترافیکی است که شرایط زیر را داشته باشند :
در حالت تداخل غیرمستقیم، دو جریان ترافیکی هیچ پیوند فیزیکی مشترکی ندارند اما یک سری جریانهایی بین این دو جریان ترافیکی وجود دارد. بنابراین شامل جریانهای ترافیکی اولویت بالاتری میباشد که هیچ پیوند مشترکی با ندارند اما حداقل یک پیوند مشترک با یک جریان ترافیکی در دارد.
برای هر جریان ترافیکی مجموعه Si شامل همه جریانهای ترافیکی با تداخل مستقیم یا غیرمستقیم است و به عبارتی Si=+. در مثال شکل ۴-۳ جریانهای ترافیکی اولویت بندی شده از اولویت بالا به پایین عبارتند از ، ، و . جریانهای و هیچ پیوند مشترکی با جریان اولویت بالاتر ندارند و بنابراین هیچ تداخل مستقیم و غیرمستقیمی ندارند .
جریان ترافیکی با و رقابت می کند و و . جریان ترافیکی به طور مستقیم با و رقابت می کند و به طور غیرمستقیم با تداخل دارد. بنابراین و و . لازم به ذکر است که اگر یک جریان ترافیکی با جریان ترافیکی مورد بررسی هم رقابت مستقیم و هم رقابت غیرمستقیم داشته باشد، آنگاه اینگونه در نظر گرفته می شود که این جریان ترافیکی تنها رقابت مستقیم ایجاد می کند.
حال برای ارزیابی همه تداخلهای رقابتی اعمال شده توسط جریانهای ترافیکی اولویت بالاتر، در اینجا مفهوم بدترین تاخیر شبکه[۱۵۲] مطرح است. با توجه به [۴۸] بدترین تاخیر شبکه زمانی اتفاق میافتد که بسته جریان ترافیکی موردنظر هم زمان با همه بستههای جریانهای ترافیکی اولویت بالاتر با بیشترین نرخ آزادشدنشان، آزاد شود.
شکل ۴‑۳- مثال تداخل مستقیم و غیرمستقیم جریانهای ترافیکی [۴۸]
برای محاسبه بدترین تاخیر شبکه یک جریان ترافیکی، علاوه بر تاخیر شبکه پایهای بیشینه، تداخلهای مستقیم و غیر مستقیم ناشی از جریانهای ترافیکی اولویت بالاتر نیز در نظر گرفته می شود. در واقع تاخیر شبکه یک بسته آزاد شده از جریان ترافیکی ، برابر است با :
۴‑۳
در این رابطه مجموع تداخلهای ناشی از فلوهای ترافیکی اولویت بالاتر است و همان تاخیر شبکه پایهای بیشینه میباشد که یک معیار ثابت است و از قبل توسط تحلیل ایستا طبق معادله ۴-۲ مشخص شده است. پارامتر B نشان‌دهنده‌ی بیشترین زمان انسداد[۱۵۳] است که توسط هر جریان ترافیکی اولویت پایینتر که اکنون انتقالش را شروع کرده است، ایجاد می شود. بیشترین انسداد زمانی اتفاق میافتد که یک بسته با اولویت بالاتر درست بعد از اینکه یک بسته با اولویت پایینتر سرویس خود را شروع کرده است، وارد شود. در روش زمانبندی انحصاری در سطح فلیت، یک بسته با اولویت بالاتر در هر درگاه خروجی هر مسیریاب ، حداکثر به اندازه زمان یک فلیت صبر می کند و سپس انتقالش را شروع می کند. بنابراین بیشترین زمان انسداد عبارت است از . پس از پیکربندی شبکه روی تراشه، اندازه فلیت و پهنای باند پیوند ثابت است. بنابراین زمان انسداد می تواند به عنوان یک معیار ثابت در نظر گرفته شود و در داخل گنجانده شود. حال معادله ۴-۳ برای تاخیر شبکه به صورت زیر خلاصه می شود.
۴‑۴
همان گونه که در [۴۸] اشاره شده است، تا زمان یعنی زمانی که بسته به طور کامل توسط گیرنده دریافت می شود، بیشترین تداخل مستقیم حاصل از جریانهای ترافیکی اولویت بالاتر موجود در و تداخل غیرمستقیم ناشی از جریانهای ترافیکی اولویت بالاتر موجود در برای یک بسته از عبارت است از :
۴‑۵
چون جریان ترافیکی بلافاصله بعد از اجرای وظیفه مبدا، ایجاد می شود بنابراین در این رابطه که بیانگر تاخیر آزاد شدن بستههای جریان ترافیکی است برابر با زمان پاسخ وظیفه مبدا این جریان میباشد . همچنین به دلیل در نظر گرفتن تداخلهای غیرمستقیم، بدترین تاخیر شبکه هنگامی که بسته یک جریان ترافیکی هم زمان با بستههای اولویت بالاترآزاد شود، اتفاق نمیافتد بلکه هنگامی اتفاق میافتد که بسته جریان مورد بررسی در همان زمانی که بستههای اولویت بالاتر زمان انتظارشان تمام می شود و شروع به دریافت سرویس می کنند، آزاد شود. این انحراف ایجاد شده ناشی از تداخل جریانهای اولویت بالاتر بین آزاد شدنهای متوالی را تاخیر تداخل[۱۵۴] میگویند که برای نمایش این معیار جریان ترافیکی از سمبل استفاده می شود. در واقع تاخیر تداخل یک جریان ترافیکی، بیشترین انحراف بین دو زمان متوالی شروع سرویس است که با محاسبه اختلاف بین بیشینه و کمینه مقدار زمان شروع سرویس بسته[۱۵۵] به دست می آید. زمانی که در یک دوره هیچ بسته اولویت بالاتری نیاید، کمترین زمان شروع سرویس بسته صفر است. بنابراین تاخیر تداخل جریان ترافیکی برابر است با بیشینه عدد زمان شروع سرویس که با بهره گرفتن از یک حد بالایی به صورت به دست می آید. لازم به ذکر است که همه جریانهای ترافیکی تاخیر تداخل ندارند و این تاخیر تنها هنگامی اتفاق میافتد که جریان ترافیکی مورد بررسی ، تداخل غیرمستقیم دارد. به عبارتی وجود دارد اگر و فقط اگر .
با قرار دادن رابطه ۴-۵ در رابطه ۴-۴، بیشترین تاخیر شبکه برای بستههای یک جریان ترافیکی ، برابر است با :
۴‑۶
همان طور که در رابطه فوق ملاحظه می شود، متغیر در هر دو طرف معادله ظاهر شده است. بنابراین برای حل آن از یک روش تکرار شونده استفاده می شود[۱۲]. در واقع مقدار متغیر در n+1 امین تکرار میباشد. تکرار با شروع می شود و هنگامی خاتمه مییابد که باشد. همچنین اگر گردد، این تکرار متوقف می شود که بیانگر این است که مهلت اتمام بسته‌ی جریان مورد بررسی رعایت نشده است.
مدل تحلیلی توان
در مدل پیشنهادی، به دلیل آنکه هستههای پردازشی ناهمگن هستند، توان مصرفی ناشی از اجرای وظایف مختلف بر روی هر یک از این هستهها متفاوت است. بنابراین دو نوع اتلاف توان وجود دارد: ۱) اتلاف توان حاصل از اجرای وظایف بر روی هستههای پردازشی مختلف. این مشخصه به صورت یک بردار از قبل برای هر وظیفه تعیین شده است . ۲) توان تلف شده برای انتقال بستههای داده در سطح شبکه. برای تخمین این توان مصرفی از مدل ارائه شده در [۷۶] استفاده شده است. مطابق با این مدل، هر یک از اجزای شبکه شامل واسط شبکه، مسیریاب و پیوند برای انتقال یک بسته در طول یک مسیر مشخص، دارای اتلاف توان میباشند. در [۷۶] فرض بر این است که اتلاف توان در مسیریاب برای انتقال یک فلیت سرآیند و سایر فلیتها متفاوت است اما در اینجا برای سادگی فرض شده است که اتلاف توان در مسیریاب برای انتقال یک فلیت سرآیند و سایر فلیتها مشابه است. معادله ۴-۷ توان مصرفی در هر یک از اجزای شبکه برای انتقال یک بسته را نشان میدهد.
۴‑۷
فرم در حال بارگذاری ...
