الف – پرداخت وجه بحساب وب سایت ایران ترجمه(شماره حساب)ب- اطلاع جزئیات به ایمیل irantarjomeh@gmail.comشامل: مبلغ پرداختی – شماره فیش / ارجاع و تاریخ پرداخت – مقاله مورد نظر --مقالات آماده سفارش داده شده پس از تایید به ایمیل شما ارسال خواهند شد.
قیمت
قیمت این مقاله: 48000 تومان
(ایران ترجمه - Irantarjomeh)
توضیح
بخش زیادی از این مقاله بصورت رایگان ذیلا قابل مطالعه می باشد.
مسیریابی تحمل خرابی / خطا تطبیقی در مولتی کامپیوترهای ابر معکب
نام انگلیسی
Adaptive Fault Tolerant Routing in Hypercube Multicomputers
تعداد صفحه به فارسی
۵۱
تعداد صفحه به انگلیسی
۳۹
کلمات کلیدی به فارسی
ابر معکب منظم و مصدوم, ,مسیریابی تحمل خرابی تطبیقی توزیع شده, جستجوی عمقی, عوامل و تاثیرات ایجاد حلقه, جدول های تأخیر شبکه, اطلاعات مربوط به خرابی
کلمات کلیدی به انگلیسی
Injured and regular hypercubes, distributed adaptive fault tolerant routing, depth first search, looping effects, network delay tables, failure information
مرجع به فارسی
دپارتمان مهندسی برق و علوم کامپیوتر دانشگاه میشیگان
مرجع به انگلیسی
Department of Electrical Engineering and Computer Science- Michigan University
کشور
ایالات متحده
مسیریابی تحمل خطا / خرابی تطبیقی در مولتی کامپیوترهای ابر معکب
چکیده
یک ابر معکب متصل با لینک ها و/یا گره های معیوب، یک ابر معکب مصدوم نامیده می‌شود. برای قادرساختن یک گره سالم به برقراری ارتباط با هر گره سالم دیگر در یک ابر معکب معیوب، اطلاعات در مورد خرابی های مؤلفه ای باید در اختیار گره های سالم قرار گیرد به گونه ای که بتوانند پیام های اطرا ف مؤلفه های معیوب را مسیر دهی کنند.
در اینجا ابتدا یک نمودار مسیریابی تحمل خرابی سازگار توزیع شده برای یک ابر معکب مصدوم را ارائه می‌دهیم که در آن هر گره تنها باید شرایط لینک های خودش را بداند. با وجود سادگی آن، به نظر می‌رسد که این نمودار بتواند تا زمانیکه تعداد مؤلفه های معیوب کمتر از n باشد، پیام ها را با موفقیت در یک ابر معکب مصدوم مسیردهی کند. علاوه بر آن، ثابت شده که این نمودار پیام ها را با یک احتمال نسبتاً زیادی از طریق کوتاه ترین مسیرها ارسال می‌کند و طول مورد انتظار یک مسیر ایجاد شده به کوتاه ترین مسیر بسیار نزدیک است. از آنجا که فرض کمتر بودن تعداد مؤلفه های معیوب از n در یک ابر معکب n بعدی ممکن است قابلیت استفاده نمودار بالا را محدود کند، یک نمودار مسیریابی مبتنی بر جستجوی عمقی را نیز معرفی می‌کنیم، به گونه ای که در حضور تعداد دلخواهی از مؤلفه های معیوب کار کند.
با این حال، به دلیل ناکافی بودن اطلاعات در مورد مؤلفه های معیوب، مسیر های انتخاب شده توسط نمودار بالا ممکن است همیشه کوتاهترین نباشند. برای تضمین ارسال پیام ها از طریق کوتاه ترین مسیرها، پیشنهاد می‌کنیم که هر گره از اطلاعاتی بیش از آنچه بر روی لینک های آن قرار دارد، برخوردار باشد. تأثیر این اطلاعات اضافی بر کارآیی مسیریابی مورد تحلیل قرار می‌گیرد و اطلاعات اضافی که برای یافتن کوتاهترین مسیر در هر گره نگهداری می‌شود، تعیین می‌شود. چندین مثال و نکته برای روشن شدن نتایج ارائه می‌شود.
واژه های شاخص:ابر معکب منظم و مصدوم، مسیریابی تحمل خرابی تطبیقی توزیع شده، جستجوی عمقی، عوامل و تاثیرات ایجاد حلقه، جدول های تأخیر شبکه، اطلاعات مربوط به خرابی
مولتی کامپیوتر ابر معکب مسیریابی تحمل خطا
۱- مقدمه
در سالهای اخیر، پیشرفت های VLSI و تکنولوژی های ایجاد شبکه کامپیوتری، موجب جذابیت ساخت سیستم های کامپیوتری چندگانه یا مولتی کامپیوترها برای کاربرد های بزرگ شده است. کامپیوترهای چندگانه ابر معکب، در میان دیگر کامپیوترها، به دلیل ترتیب ساختاری خود در خصوص ساخت آسان مولفه‌ها و پتانسیل بالا برای اجرای موازی الگوریتم های گوناگون، توجه زیادی را به خود جلب کرده اند. بر این مبنا، پروژه های تحقیقی بزرگ مرتبط با معماریهای ابر معکب، سیستمهای عامل و زبان های برنامه نویسی در حال اجرا بوده و تعدادی از کامپیوترهای چندگانه ابر معکب تجاری و تحقیقی ساخته شده اند.
مسیریابی کارآمد پیام ها نقش کلیدی در اجرای یک سیستم کامپیوتری چند گانه دارد. خصوصاً، افزایش کاربرد سیستم های چند کامپیوتری برای کاربرد های بحرانی- قابلیت اطمینان، طراحی استراتژی های مسیریابی تحمل خرابی برای چنین سیستم هایی را ضروری کرده است. منظور ما از مسیریابی تحمل خرابی، هدایت موفق پیام ها بین هر جفت از گره های سالم در حضور مؤلفه های معیوب (لینک ها و/یا گره ها) می‌باشد. چندین نتیجه مهم بر مسیریابی تحمل خرابی در شبکه های گوناگون گزارش شده است. بر این اساس، تعداد کمی‌از معماری ها قابلیت های مسیریابی تحمل خرابی و پردازش متناسبی را ارائه می‌نمایند. زمانی که قرار است کامپیوترهای چندگانه ابر معکب برای کاربردهای قابل اطمینان استفاده شوند، باید قادر باشند پیام ها را حتی در حضور لینک ها و گره‌های معیوب، مسیردهی کنند.
یک ابر معکب متصل با مؤلفه های معیوب، ابر معکب مصدوم نامیده می‌شود، درحالیکه یک ابر معکب بدون مؤلفه معیوب یک ابر معکب منظم نامیده می‌شود. بدیهی است که مسیریابی در یک ابر معکب منظم توسط رویه سیستماتیک قابل انجام است. برخی نتایج درمورد توسعه کارآیی مسیریابی در ابر معکبها منظم در بخش (۱۹) گزارش شده اند. مسیریابی در یک ابر معکب ناقص بصورت مستقیم گزارش شده است ]۲۰]. در یک ابر معکب منظم، هر گره میانی می‌تواند جهش یا مسیر بعدی یک پیام را با استفاده از بررسی آدرس مقصد و انتخاب گرهی از بین تمام گره های همسایه که به مقصد نزدیک تر باشد، انتخاب کند. واضح است که این کار از طریق تطبیق آدرس گره مبدأ با آدرس گره مقصد از راست به چپ و به صورت بیت به بیت، انجام می‌شود. اما این نمودار در یک ابر معکب مصدوم نامعتبر است، زیرا پیام ممکن است به یک مؤلفه معیوب ارسال شود. برای آنکه گره‌های سالم بتوانند در یک ابر معکب مصدوم با یکدیگر ارتباط داشته باشند، باید اطلاعات شبکه‌ای کافی در اختیار آن پیام قرار گیرد تا مسیر دهی شود و یا در اختیار هر گره در شبکه قرار گیرد تا پیامها را اطراف مؤلفه های معیوب مسیر دهی کنند. با استفاده از سخت افزار اضافی به نام کلید هایپر، الگوریتم جستجوی عمقی برای مسیردهی پیام ها در یک ابر معکب در [۱۲] ایجاد می‌شود. چندین الگوریتم مسیریابی بسته سازگار یا انطباقی نیز در [۲۱] ارائه شده اند که بر اساس استراتژی های مسیریابی استفاده شده برای شبکه های کامپیوتری گسترده نظیر ARPANET عمل می‌کنند. علاوه بر آن، الگوریتم های گوناگونی برای انتشار اطلاعات درباره مؤلفه های معیوب به تمام گره های دیگر در یک ابر معکب در [۱۴،۲۲] پیشنهاد شده اند به گونه ای که پیام ها می‌توانند در اطراف مؤلفه های معیوب مسیردهی شوند. بدیهی است چنانچه هر گره، اطلاعاتی در مورد تمام گره های معیوب در اختیارداشته باشد، آنگاه می‌تواند یک مسیر بدون عیب برای هر پیام به مقصد پیدا کند. با اینحال مطلع کردن هر گره درمورد تمام گره های معیوب معمولا پرهزینه (از نظر زمان و مکان) است، خصوصاً زمانی که شبکه بزرگ باشد. در نتیجه، توسعه نمودارهای مسیریابی که در آن هر گره باید تنها اطلاعات خرابی ضروری برای یافتن مسیر درست را نگهداری کند، اهمیت زیادی خواهد داشت.
…
این مقاله به صورت زیر دسته بندی شده است. تعریف ها و نشانه گذاری ضروری در بخش ۲ ارائه شده است. در بخش ۳ یک نمودار مسیریابی تحمل خرابی سازگار را نشان می‌دهیم که در آن هر گره باید از شرایط لینک های خود آگاه باشد. یک نمودار مسیریابی دیگر بر اساس جستجوی عمقی هم در این بخش معرفی شده و مورد بحث قرار می‌گیرد. بخش ۴ دو نمودار مسیریابی تحمل خرابی را ارائه میدهد که در آن هر گره باید اطلاعاتی بیش از لینک های خودش در اختیار داشته باشد: یکی با انتشار اطلاعات خرابی و دیگری با جدول های تأخیر شبکه. نکات و مثال های توضیح دهنده یا روشن کننده هم ارائه می‌شوند. در بخش ۵ این مقاله به نتیجه گیری می‌پردازیم.
مولتی کامپیوتر ابر معکب مسیریابی تحمل خطا
۲- مقدمات اولیه
یک ابر معکبn بعدی (یا مکعب n یا Qn) به طور رسمی‌به صورت زیر تعریف می‌شود.
۳– مسیریابی به کمک اطلاعاتی در مورد خرابی های لینک محلی
در این بخش، ابتدا یک الگوریتم مسیریابی سازگار به نام A1 را ایجاد کرده و تحلیل می‌کنیم. در این الگوریتم هر گره تنها باید از شرایط لینک های خودش آگاه باشد. این الگوریتم برای مسیر دهی موفق پیام ها بین هر جفت از گره های سالم نشان داده می‌شود، البته تا زمانیکه تعداد مؤلفه های معیوب در Qn کمتر از n باشد. همانطور که قبلا هم بدان اشاره شد، این فرض که تعداد کل مؤلفه های معیوب در Qn کمتر از n باشد ممکن است کارآیی A1 را کاهش دهد. بنابراین باید نمودار مسیریابی دوم مبنی بر جستجوی عمقی که با وجود تعداد قراردادی از عناصر معیوب هم کار می‌کند. اما به دلیل ناکافی بودن اطلاعت در مورد مؤلفه های معیوب، مسیرهای انتخاب شده توسط این دو الگوریتم ممکن است همیشه کوتاهترین نباشند.
۱٫۳٫ توصیف الگوریتم A1
…
۲٫۳- تحلیل عملگرد الگوریتم A1
…
۳٫۳- مسیریابی جستجوی عمقی و دیگر نکات
توجه داشته باشید که در حضور بیش از n-1 مؤلفه معیوب در Qn ، الگوریتم A1 ، به دلیل سادگی اش، نمی‌تواند تضمین کند که یک مؤلفه معیوب بیش از یک بار ظاهر نشود و در نتیجه، همیشه نمی‌تواند یک پیام را با موفقیت مسیردهی کند. جستجوی عمقی می‌تواند برای حل مسئله ارسال پیام ها بین جفت های متصل گره های سالم در یک ابر معکب با تعداد اختیاری مؤلفه های معیوب استفاده شود. در چنین حالتی، مجموعه ای از مؤلفه های معیوب که قبلاً ظاهر شده اند باید به پیام اضافه شوند و یک روند پیچیده تر برای هدایت پیمایش معکوس برای هنگامی‌که مجبور به پیمایش معکوس از بن بست است، مورد نیاز است. به جای نگهداری رکوردی از تمامی‌مسیر های استفاده شده، میتوان مسیریابی جستجوی عمقی را با استفاده از یک پشته که در آن عملکرد های مورد نیاز برای پیمایش معکوس ساده شده اند،اجرا کرد.
مولتی کامپیوتر ابر معکب مسیریابی تحمل خطا
۴- مسیریابی با اطلاعات سراسری محدود شده
همانطور که قبلا هم اشاره شد، کارآیی مسیریابی با افزایش اطلاعات هر گره در مورد خرابی های مؤلفه اش افزایش می‌یابد. باید اثرات اطلاعات در مورد خرابی ها در هر گره بر کارآیی مسیریابی را بررسی کنیم. اول، در بخش ۱٫۴ یک نمودار مسیریابی را معرفی و بررسی می‌کنیم. نموداری که در آن شرایط هر مؤلفه تنها در اختیار گره های مجاورش قرار ندارد بلکه گره هایی که یک hop با آن مؤلفه فاصله دارند هم از آن آگاهند. گرچه این نمودار کارآیی مسیریابی را افزایش میدهد، تضمینی برای کوتاهترین مسیر بودن مسیرهای انتخاب شده وجود ندارد.
۱٫۴- انتشار اطلاعات خرابی به گره های همسایه
یک نمودار اصلاح شده ساده از الگوریتم A1 را در نظر بگیرید. هر گره، علاوه بر نگهداری رکوردی از شرایط لینک های خودش، این اطلاعات را در اختیار گره های همسایه هم قرار میدهد. بنابراین هر گره نه تنها اطلاعات لینک های خودش را در اختیار دارد، بلکه از شرایط لینک هایی که به فاصله یک هاب از آن قرار دارند هم آگاه است. برای استفاده از این اطلاعات، عبارت شرطی در A1 که با علامت مشخص شده است، به گونه ای تغییر می‌یابد که هر گره میانی یک هاب بیشتر در مجموعه مختصات هر پیام را بررسی کند و در صورت نیاز از یک بعد اضافی برای عبور از مؤلفه های معیوب استفاده کند.
۲٫۴- مسیریابی از طریق کوتاه ترین مسیرها
برای کاهش حجم اطلاعات لازم برای یافتن کوتاه ترین مسیر در هر گره ، باید از انتشار غیر ضروری اطلاعات مربوط به مؤلفه های معیوب پرهیز کرد. توجه کنید که یک گره معیوب را میتوان به عنوان یک گره با تمام لینک های معیوبش مشاهده کرد. بنابراین، اطلاعات شبکه ذخیره شده در هر گره را میتوان به صورت مجموعه ای از آدرس های لینک های معیوب نشان داد. همانطور که بعداً ثابت خواهیم کرد، زمانیکه تعداد مؤلفه های معیوب در یک Qn کمتر از n باشد، هر گره مجبور نیست اطلاعات مربوط به لینک های معیوب را به گره های همسایه اش منتشر کند، مگر اینکه این لینک های معیوب تمام مسیر های بهینه را از این گره به گره دیگر مسدود کنند.
۳٫۴- مسیریابی با جدول های تأخیر
در حضور بیش از n-1 مؤلفه معیوب در Qn ، مفهوم استفاده از جدول های تأخیر ،که قبلا در ARPAET استفاده شد، را می‌تون برای یافتن کوتاهترین مسیر به کار برد. بر اساس الگوریتم های موجود در [۲۳]، هر گره یک جدول تأخیر شبکه را نگهداری می‌کند تا کوتاهترین تأخیر را از طریق هر لینک گره به هر گره دیگر ذخیره کند. وقتی قرار است یک پیام به یک گره دیگر ارسال شود، جدول تأخیر شبکه آن را بررسی می‌کند و هاب بعدی پیام را برای یافتن کوتاهترین مسیر پیدا می‌کند. یک بردار تأخیر کمینه (حداقل) در یک گره، که شامل تأخیرات کوتاهترین مسیر ها از آن گره به تمام گره های دیگرمی‌باشد، هنگام ارسال اطلاعات، به صورت دوره ای از تمام گره های مجاور آن عبور می‌کند. پس از دریافت بردارهای تأخیر کمینه از گره های مجاور آن، هر گره جدول تأخیر شبکه خود را به روز رسانی می‌کند.
مولتی کامپیوتر ابر معکب مسیریابی تحمل خطا
۵- نتیجه گیری
در این مقاله، دو نمودار مسیریابی توزیع شده را معرفی و بررسی کرده (A1 و A2) و دو طرح دیگر (با استفاده از جستجوی عمقی و جدول های تأخیر شبکه) برای ارسال پیام در کامپیوترهای چندگانه ابر معکب مصدوم ، را نیز معرفی نمودیم. A1 بسیار ساده و قدرتمند است. در این الگوریتم، هر گره تنها نیاز دارد از خرابی لینکهای خود مطلع شود و از اتصالات فراوان در ابر معکبها استفاده کند. عملکرد این نمودار با دقت زیاد بررسی شد؛ بر این مبنا نشان داده شده که این نمودار نه تنها قادر است هنگامی‌که تعداد مؤلفه های معیوب در یک Qn مصدوم کمتر از n است، پیام ها را به خوبی هدایت کند، بلکه می‌تواند کوتاهترین مسیر را با احتمال خیلی زیاد انتخاب کند. برای کنترل حالتی که در آن تعداد کل خرابی ها در Qn بیشتر از n-1 است، یک نمودار مسیریابی بر اساس جستجوی عمقی معرفی کردیم. اما به دلیل کافی نبودن اطلاعات موجود در مورد مؤلفه های معیوب، آن دو نمودار همیشه یافتن کوتاهترین مسیر را تضمین نمی‌کنند.
برای تضمین یافتن کوتاهترین مسیر، A2 را پیشنهاد کردیم که در‌آن هر گره باید اطلاعاتی بیش اطلاعات مربوط به لینکهای خود را در اختیار داشته باشد. در نتیجه، هر گره باید تنها از شرایط تعداد نسبتا کمتری از مؤلفه ها در نزدیکی خود آگاه باشد. درحالتی که بیش از n-1 خرابی در Qn وجود داشته باشد، می‌توانیم از نمودار مسیریابی پرهزینه‌تر مبنی بر جدول های تأخیر شبکه استفاده کنیم.
لطفا به جای کپی مقالات با خرید آنها به قیمتی بسیار متناسب مشخص شده ما را در ارانه هر چه بیشتر مقالات و مضامین ترجمه شده علمی و بهبود محتویات سایت ایران ترجمه یاری دهید.
