انتخاب زيرگراف كدگذاري شده بهينه تحت محدوديت پايداري

Optimal Coding Subgraph Selection under Survivability Constraint

امروزه با توجه به نياز روزافزون كاربران شبكه‌هاي مخابراتي براي افزايش پهناي باند، كاهش تاخير و هزينه انتقال، لزوم استفاده بهينه از امكانات شبكه ضروري است. كدگذاري شبكه روش جديدي در شبكه‌هاي مخابراتي است كه در آن برخي از گره‌هاي مياني علاوه بر انتقال و تكثير اطلاعات قادر به انجام عمليات جبري بر روي داده‌هاي دريافتي و تركيب آن‌ها مي‌باشند. همچنين اهميت بسيار بالاي ظرفيت فيزيكي در شبكه‌هاي مخابراتي، مثلا بالا بردن توانايي اين شبكه‌ها در مقابل شكست مسير توسط بريدگي كابل‌ها يا قطعي‌هاي الكتريكي در مراكز تعمير باعث شده است كه طراحان به‌دنبال مدل‌هاي پايداري باشند تا بتوانند قسمت‌هاي آسيب‌ديده شبكه را بازسازي كنند. پايداري به‌عنوان كسري از تقاضا درنظر گرفته مي‌شود كه مي‌تواند پس از يك سناريوي شكست يا مجموعه‌اي از سناريوي شكست برآورده شود. در اين مقاله، سعي مي‌شود زيرگرافي با حداقل هزينه براي ارسال اطلاعات در شبكه كدگذاري با يك ارتباط چندپخشي تحت محدوديت پايداري انتخاب گردد. بعد از مدل‌بندي مساله، مدل پيشنهادي خود را با استفاده از الگوريتم توزيع شده آزادسازي لاگرانژ حل مي‌كنيم. نهايتا، با ارايه نتايج عددي، چگونگي بهبود عملكرد شبكه را با استفاده از مدل پيشنهادي خود نسبت به مدل پايداري فاقد كدگذاري نشان خواهيم داد.

Nowadays communication networks have become an essential and inevitable part of human life. Hence, there is an ever-increasing need for expanding bandwidth, decreasing delay and data transfer costs. These needs necessitate the efficient use of network facilities. Network coding is a new paradigm that allows the intermediate nodes in a network to create new packets by combining the packets received on their incoming edges. Also, in communication network, the extensive use of high capacity physical media like fiber increases the potential damage to network services due to failures in links or nodes (cable cuts, electronic failures on switching centers, etc.). Since quality of service has become a competitive advantage for services in the industry, planners are looking for end-to-end survivable designs that are robust with respect to failure in network components. Survivability is considered as a fraction of the demand that can still be satisfied after each failure scenario. In this paper, attempt has been made to select minimum-cost coding sub-graphs in a single or multiple multicasts over coded packet networks under survivability constraint. First, mathematical optimization models are presented for the problem. Then, the proposed model is solved by using Lagrangian relaxation method. Finally, the efficiency of the proposed model is evaluated through simulation results.