We propose a novel way to consider the max-min fairness (MMF) paradigm in traffic engineering. Since MMF appears as a reference model for a fair capacity allocation when the traffic flows are elastic and rates are adapted based on resource availability, we consider it as a requirement due to the way resources are shared by the distributed rate control scheme (like that of the transport protocol), rather than the routing objective. In particular, we define the traffic engineering problem where, given a network topology with link capacities and a set of elastic traffic demands to route, we must select a single path for each demand so as to maximize a network utility function, assuming an MMF bandwidth allocation. We propose a compact mixed-integer linear programming formulation as well as a restricted path formulation. We show with computational experiments that the exact formulation can be solved in a reasonable amount of computing time for medium-size networks and that the restricted path model provides solutions of comparable quality much faster

چکیده

در این مقاله قصد داریم تا یک روش مدرنی را به منظور در نظر گرفتن پارادایم انصاف حداقلی-حداکثری (MMF) در فرآیند مهندسی ترافیک ارائه دهیم. با توجه به اینکه مدل MMF را می ‌توان به عنوان یک مدل رفرنس و اصلی برای تخصیص منصفانه‌ ی ظرفیت به جریان ‌های ترافیکی قابل ارتجاع در نظر گرفت و نسبت تخصیص منابع نیز بر اساس موجودیت این منابع صورت می ‌گیرد، و با توجه به اینکه منابع از طریق یک شِمای کنترل نسبت توزیع شده به اشتراک گذاشته می ‌شوند (مانند پروتکل حمل و نقل) و نه  با هدف مسیریابی، ما این مدل را به عنوان یک مدل ضروری در نظر می‌ گیریم. به طور خاص، مسئله‌ ی مهندسی ترافیک را تعریف خواهیم کرد که در این مسئله، یک توپولوژی شبکه مجهز به ظرفیت‌ های لینک بوده و یک مجموعه از تقاضاهای ترافیکی ارتجاعی را باید مسیریابی نمود، و از این رو باید یک مسیر تکی را به ازای هر تقاضای ترافیکی انتخاب کرده تا بتوان با تخصیص پهنای باند MMF، تابع مطلوبیتِ  شبکه به حداکثر سطح خود برسد. در همین راستا، یک فرمولاسیون برنامه‌ریزی خطی صحیح ترکیبی را به همراه یک تدوین مسیر محدود ارائه می‌ دهیم. با بهره‌ برداری از آزمایش ‌های محاسباتی نشان می ‌دهیم که می ‌توان در یک بازه‌ ی زمانی معقولانه، یک تدوین دقیقی از مسئله را برای شبکه ‌های متوسط اندازه به دست آورده و  همچنین نشان می ‌دهیم که مدل مسیر محدود شده می‌ تواند راهکارهایی را برای  حصول سریع تر کیفیت قابل قیاس پیش روی ما قرار دهد.

1-مقدمه

اخیراً، فعالیت‌ های گسترده ‌ای در رابطه با مسئله‌ ی تخصیص (یا جریان یا نسبت) منصفانه‌ ی پهنای باند در شبکه‌ های ارتباطی صورت گرفته است که بیشتر هم بر روی پارادایم انصاف حداکثری-حداقلی (MMF) متمرکز بوده ‌اند. (به مطالعه‌ ی [1] و رفرنس ‌های داخل آن رجوع کنید). به طور غیر رسمی، فرآیند تخصیص پهنای باند در صورتی به صورت منصفانه ‌ی حداکثری-حداقلی صورت می‌ گیرد که هیچ راهی برای تخصیص پهنای باند بیشتر به تقاضاهای ترافیکی و آن ‌هم بدون کاهش تخصیص پهنای باند به یک تقاضایی که پهنای باند کمتر یا برابری را دریافت می ‌کند،  وجود نداشته باشد. به عبارت دیگر، این به معنای بیشینه‌ سازی پهنای باند تخصیص داده شده به تقاضاهای مختلفی بوده که تقاضاها را از مرتبه ‌ی غیر کاهشی از پهنای باند در نظر می‌ گیرند...