Abstract
We formalize the construction of fault blocks by a state transition model based on finite state automata. Based on the model, a boundary diffusion method is presented for the rectilinear-monotone orthogonal convex fault model such as the rectangular fault model and minimal-connected-component (MCC) faulty model, whereby an adaptive fault-tolerant routing algorithm, called X-Y boundary routing algorithm (X-YBRA), is presented for deadlock-free fault-tolerant adaptive routing outside the fault blocks. To improve the network resources utilization, we put forward a routing diffusion method in the fault block, which completely solves the routing problem in the fault block. The experiment result shows that the diffusion overhead of our method is far lower than that of the traditional routing algorithms such as distance vector and link state routing algorithms with the light loss in convergence time. For the occurrence and recovery of random faults, the expansion and shrinkage of the fault block are also discussed. Accordingly, the dynamic boundary and routing updating methods are put forward to respond to these cases. Based on these methods, we develop low earth orbit satellite networks into an adaptive fault-tolerant system in routing. Our works can be also applied to other 2D mesh networks such as the interconnect multiprocessor computer systems
چکیده
در این مقاله ما ساختار بلاک های خطا را بوسیله مدل گذر حالت بر مبنای اتوماتای حالت متناهی فرمالیزه کرده ایم. بر مبنای مدل، یک متد انتشار مرزی برای مدل های محدب متعامد راست-یکنواخت خطا نظیر مدل خطای مستطیلی، مدل خطای مولفه همبند مینیمال(MMC)، ارائه شده است که بوسیله آن یک الگوریتم مسیریابی تطبیق پذیر تحمل پذیر خطا که الگوریتم مسیریابی مرزی X-Y نامیده می شود(X-YBRA)، برای مسیریابی تطبیق پذیر تحمل پذیر خطای بدون بن بست خارج از بلاک های خطا، ارائه شده است. برای بهبود بکارگیری منابع شبکه، ما یک متد انتشار مسیریابی را در بلاک های خطا طراحی کردیم که کاملا مسئله مسیریابی را در بلاک خطا حل می کند. نتایج آزمایشات نشان می دهد که سربار انتشار متد ما بسیار کمتر از الگوریتم های مسیریابی سنتی نظیر الگوریتم های مسیریابی حالت لینک و بردار فاصله با زیان کم در زمان همگرایی است. برای رخ دادن و بازیابی خطاهای تصادفی، انبساط و انقباض بلاک خطا نیز در اینجا مورد بحث و بررسی قرار گرفته است. از این رو، متدهای به روزرسانی مسیریابی و مرزی پویا برای پاسخ گویی به این حالات طراحی شده اند. بر مبنای این متدها، ما شبکه های ماهواره ای مدارتوان پایین در یک سیستم تحمل پذیر تطبیقی در مسیریابی، توسعه دادیم. اقدامات انجام شده در این مقاله را می توان در شبکه های مش دوبعدی نظیر سیستم های کامپیوتری چندپردازنده ای متصل بکار برد.
1-مقدمه
شبکه های ماهواره ای یک بخش حیاتی از نسل بعدی اینترنت و اینترنت بین سیاره ای، بدلیل قابلیت ارتباط سراسری منعطف آن، می باشد. در بین شبکه های ماهواره ای، شبکه های ماهواره ای مدار ارتفاع پایین (LEO)، در مقایسه با مدار ارتفاع متوسط و سیستم های ماهواره ای ثابت که دارای تاخیر انتشار پایین تر، نیازهای قدرت انتقال پایین تر و توان عملیاتی بالاتر هستند، دسترسی به پهنای باند گسترده ای برای کاربران نهایی را فراهم می نماید. اکثر شبکه های ماهواره ای LEO از لینک های بین ماهواره ای (ISL) برای ساخت یک شبکه پویا که ویژگی هایی از آن نظیر توپولوژی پویای بالا، قابلیت پردازش محدود، فضای ذخیره سازی، و مانند آن مشکلات زیادی را در طراحی الگوریتم های مسیریابی قابل اطمینان ایجاد کرده است، استفاده می کنند. علاوه بر این، در جهان پیچیده، تداخلات الکترومغناطیسی، شکست فیزیکی، محدودیت انرژی، حمله نظامی و مانند آن، ممکن است منجر به شکست ماهواره شود که تاثیر مهمی بر ارتباطات شبکه های ماهواره ای LEO دارد...