Backpressure routing
সম্ভাব্যতার গাণিতিক তত্ত্বের একটি শাখা, সারি তত্ত্বে, ব্যাকপ্রেসার রাউটিং অ্যালগরিদম হল একটি সারি নেটওয়ার্কের চারপাশে ট্র্যাফিক পরিচালনা করার একটি পদ্ধতি যা সর্বাধিক নেটওয়ার্ক থ্রুপুট অর্জন করে, যা লিয়াপুনভ ড্রিফ্টের ধারণা ব্যবহার করে প্রতিষ্ঠিত হয়। ব্যাকপ্রেসার রাউটিং এমন পরিস্থিতি বিবেচনা করে যেখানে প্রতিটি কাজ নেটওয়ার্কের একাধিক পরিষেবা নোডে যেতে পারে। এটি সর্বাধিক ওজনের সময়সূচীর একটি সম্প্রসারণ যেখানে প্রতিটি কাজ শুধুমাত্র একটি পরিষেবা নোডে যায়। পরিচিতি ব্যাকপ্রেসার রাউটিং হল যানজট গ্রেডিয়েন্ট ব্যবহার করে মাল্টি-হপ নেটওয়ার্কের মাধ্যমে ট্র্যাফিককে গতিশীলভাবে রাউটিং করার জন্য একটি অ্যালগরিদম। অ্যালগরিদমটি সেন্সর নেটওয়ার্ক, মোবাইল অ্যাডহক নেটওয়ার্ক (MANETS) এবং ওয়্যারলেস এবং ওয়্যারলাইন উপাদান সহ বৈচিত্র্যময় নেটওয়ার্ক সহ ওয়্যারলেস যোগাযোগ নেটওয়ার্কগুলিতে প্রয়োগ করা যেতে পারে। ব্যাকপ্রেসার নীতিগুলি অন্যান্য ক্ষেত্রেও প্রয়োগ করা যেতে পারে, যেমন পণ্য সমাবেশ ব্যবস্থা এবং প্রক্রিয়াকরণ নেটওয়ার্কের অধ্যয়নে। এই নিবন্ধটি যোগাযোগ নেটওয়ার্কগুলির উপর দৃষ্টি নিবদ্ধ করে, যেখানে একাধিক ডেটা স্ট্রিম থেকে প্যাকেটগুলি আসে এবং যথাযথ গন্তব্যে সরবরাহ করা আবশ্যক। ব্যাকপ্রেসার অ্যালগরিদম নির্দিষ্ট সময়ে কাজ করে। প্রতিবার স্লট করার সময় এটি পার্শ্ববর্তী নোডগুলির মধ্যে ডিফারেনশিয়াল ব্যাকলগকে সর্বাধিক করে এমন দিকে ডেটা রুট করতে চায়। এটি চাপের গ্রেডিয়েন্টের মাধ্যমে পাইপের নেটওয়ার্কের মধ্য দিয়ে জল যেভাবে প্রবাহিত হয় তার অনুরূপ। যাইহোক, ব্যাকপ্রেসার অ্যালগরিদম মাল্টি-কমোডিটি নেটওয়ার্কগুলিতে (যেখানে বিভিন্ন প্যাকেটের বিভিন্ন গন্তব্য থাকতে পারে) এবং এমন নেটওয়ার্কগুলিতে প্রয়োগ করা যেতে পারে যেখানে সংক্রমণের হারগুলি (সম্ভবত সময়-পরিবর্তিত) বিকল্পগুলির একটি সেট থেকে নির্বাচন করা যেতে পারে। ব্যাকপ্রেসার অ্যালগরিদমের আকর্ষণীয় বৈশিষ্ট্যগুলি হ 'লঃ (i) এটি সর্বাধিক নেটওয়ার্ক থ্রুপুটের দিকে পরিচালিত করে, (ii) এটি সময়-পরিবর্তিত নেটওয়ার্ক অবস্থার জন্য প্রমাণযোগ্যভাবে শক্তিশালী, (iii) ট্র্যাফিক আগমনের হার বা চ্যানেল রাজ্যের সম্ভাবনা না জেনে এটি প্রয়োগ করা যেতে পারে। যাইহোক, অ্যালগরিদমটি বড় বিলম্বের প্রবর্তন করতে পারে এবং হস্তক্ষেপ সহ নেটওয়ার্কগুলিতে ঠিক প্রয়োগ করা কঠিন হতে পারে। ব্যাকপ্রেসারের পরিবর্তনগুলি যা বিলম্ব হ্রাস করে এবং বাস্তবায়নকে সহজতর করে তা ইম্প্রোভিং ডিলে এবং ডিস্ট্রিবিউটেড ব্যাকপ্রেসারের অধীনে নীচে বর্ণনা করা হয়েছে। ব্যাকপ্রেসার রাউটিং মূলত একটি তাত্ত্বিক প্রসঙ্গে অধ্যয়ন করা হয়েছে। বাস্তবে, অ্যাডহক ওয়্যারলেস নেটওয়ার্কগুলি সাধারণত সংক্ষিপ্ততম পথ গণনা বা নেটওয়ার্ক বন্যার উপর ভিত্তি করে বিকল্প রাউটিং পদ্ধতি প্রয়োগ করেছে, যেমন অ্যাডহক অন-ডিমান্ড ডিস্টেন্স ভেক্টর রাউটিং (এ. ও. ডি. ভি), ভৌগলিক রাউটিং এবং অত্যন্ত সুবিধাবাদী রাউটিং (এক্স. ও. আর)। যাইহোক, ব্যাকপ্রেসারের গাণিতিক অনুকূল বৈশিষ্ট্যগুলি সাউদার্ন ক্যালিফোর্নিয়া বিশ্ববিদ্যালয় এবং নর্থ ক্যারোলিনা স্টেট ইউনিভার্সিটিতে ওয়্যারলেস টেস্টবেডে এর ব্যবহারের সাম্প্রতিক পরীক্ষামূলক প্রদর্শনকে অনুপ্রাণিত করেছে। মূল ব্যাকপ্রেসার অ্যালগরিদম তৈরি করেছিলেন তাসসিউলাস এবং এফ্রেমাইডস। তারা এলোমেলো প্যাকেট আগমন এবং লিঙ্ক নির্বাচনের বিকল্পগুলির একটি নির্দিষ্ট সেট সহ একটি মাল্টি-হপ প্যাকেট রেডিও নেটওয়ার্ক বিবেচনা করেছিল। তাদের অ্যালগরিদম একটি সর্বাধিক ওজনের লিঙ্ক নির্বাচন পর্যায় এবং একটি ডিফারেনশিয়াল ব্যাকলগ রাউটিং পর্যায় নিয়ে গঠিত। মাল্টি-কমোডিটি নেটওয়ার্ক প্রবাহ গণনা করার জন্য ডিজাইন করা ব্যাকপ্রেসার সম্পর্কিত একটি অ্যালগরিদম আওয়ারবুচ এবং লেইটনে তৈরি করা হয়েছিল। ব্যাকপ্রেসার অ্যালগরিদমটি পরে নেলি, মোদিয়ানো এবং রোহার্স দ্বারা মোবাইল নেটওয়ার্কের সময়সূচীর জন্য প্রসারিত করা হয়েছিল। ব্যাকপ্রেসার গাণিতিকভাবে লিয়াপুনভ ড্রিফ্ট তত্ত্বের মাধ্যমে বিশ্লেষণ করা হয় এবং নেটওয়ার্ক ইউটিলিটি সর্বাধিককরণ প্রদানের জন্য প্রবাহ নিয়ন্ত্রণ ব্যবস্থার সাথে যৌথভাবে ব্যবহার করা যেতে পারে। (ইউটিলিটি অপ্টিমাইজেশন এবং পেনাল্টি মিনিমাইজেশনের সাথে ব্যাকপ্রেসারও দেখুন)। এটি কীভাবে কাজ করে ব্যাকপ্রেসার রাউটিং এমন সিদ্ধান্ত নেওয়ার জন্য ডিজাইন করা হয়েছে যা (মোটামুটিভাবে) নেটওয়ার্কে সারি ব্যাকলগের বর্গক্ষেত্রের যোগফলকে এক টাইম স্লট থেকে অন্য টাইম স্লটে কমিয়ে দেয়। এই কৌশলটির সুনির্দিষ্ট গাণিতিক বিকাশ পরবর্তী বিভাগগুলিতে বর্ণনা করা হয়েছে। এই বিভাগটি সাধারণ নেটওয়ার্ক মডেল এবং এই মডেলের সাথে সম্পর্কিত ব্যাকপ্রেসার রাউটিংয়ের ক্রিয়াকলাপ বর্ণনা করে। মাল্টি-হপ সারি নেটওয়ার্ক মডেল এন নোড সহ একটি মাল্টি-হপ নেটওয়ার্ক বিবেচনা করুন (চিত্র দেখুন। N = 6 সহ একটি উদাহরণের জন্য 1)। নেটওয়ার্কটি নির্দিষ্ট সময়ে কাজ করে। প্রতিটি স্লটে, নতুন ডেটা নেটওয়ার্কে পৌঁছতে পারে এবং সমস্ত ডেটা তার সঠিক গন্তব্যে পৌঁছে দেওয়ার প্রয়াসে রাউটিং এবং ট্রান্সমিশন সময়সূচী সিদ্ধান্ত নেওয়া হয়। নোডের জন্য নির্ধারিত ডেটা পণ্য সি ডেটা হিসাবে লেবেল করা যাক। প্রতিটি নোডে ডেটা তার পণ্য অনুযায়ী সংরক্ষণ করা হয়। এবং এর জন্য, ধরা যাক নোড এন-এ পণ্য সি ডেটার বর্তমান পরিমাণ, যাকে কিউ ব্যাকলগও বলা হয়। একটি নোডের ভিতরে সারির ব্যাকলগের একটি ক্লোজআপ চিত্রে দেখানো হয়েছে। 2. এর এককগুলি সমস্যার প্রেক্ষাপটের উপর নির্ভর করে। উদাহরণস্বরূপ, ব্যাকলগ প্যাকেটের পূর্ণসংখ্যা একক নিতে পারে, যা ডেটা নির্দিষ্ট দৈর্ঘ্যের প্যাকেটগুলিতে বিভক্ত করার ক্ষেত্রে কার্যকর। বিকল্পভাবে, এটি বিটের প্রকৃত মূল্যবান একক নিতে পারে। এটি ধরে নেওয়া হয় যে সমস্ত এবং সমস্ত টাইমস্লট টি-এর জন্য, কারণ কোনও নোড নিজের জন্য নির্ধারিত ডেটা সঞ্চয় করে না। প্রতিটি টাইম স্লটে, নোডগুলি অন্যদের কাছে তথ্য প্রেরণ করতে পারে। একটি নোড থেকে অন্য নোডে প্রেরিত তথ্য প্রথম নোডের সারি থেকে সরানো হয় এবং দ্বিতীয় নোডের সারিতে যোগ করা হয়। যে তথ্য তার গন্তব্যে প্রেরণ করা হয় তা নেটওয়ার্ক থেকে সরিয়ে ফেলা হয়। ডেটা নেটওয়ার্কে বহির্জাগতিকভাবেও পৌঁছতে পারে এবং স্লট টি-তে নোড এন-এ আসা নতুন ডেটার পরিমাণ হিসাবে সংজ্ঞায়িত করা হয় যা শেষ পর্যন্ত নোড সি-তে সরবরাহ করা আবশ্যক। ধরা যাক স্লট টি-তে লিঙ্ক (এ, বি)-এর মাধ্যমে নেটওয়ার্ক দ্বারা ব্যবহৃত সংক্রমণ হার, যা বর্তমান স্লটে নোড এ থেকে নোড বি-তে স্থানান্তর করতে পারে এমন ডেটার পরিমাণকে উপস্থাপন করে। ধরা যাক ট্রান্সমিশন রেট ম্যাট্রিক্স। এই সংক্রমণ হারগুলি অবশ্যই সম্ভাব্য সময়-পরিবর্তিত বিকল্পগুলির একটি সেটের মধ্যে নির্বাচন করা উচিত। বিশেষত, নেটওয়ার্কটিতে সময়-পরিবর্তিত চ্যানেল এবং নোড গতিশীলতা থাকতে পারে এবং এটি প্রতিটি স্লটে এর সংক্রমণ ক্ষমতাকে প্রভাবিত করতে পারে। এটি মডেল করার জন্য, এস (টি) নেটওয়ার্কের টপোলজি অবস্থার প্রতিনিধিত্ব করে, যা স্লট টি-তে নেটওয়ার্কের বৈশিষ্ট্যগুলি ধারণ করে যা সংক্রমণকে প্রভাবিত করে। আসুন টপোলজি অবস্থা এস (টি)-এর অধীনে উপলব্ধ ট্রান্সমিশন রেট ম্যাট্রিক্স বিকল্পগুলির সেটটি উপস্থাপন করি। প্রতিটি স্লট টি, নেটওয়ার্ক নিয়ন্ত্রক এস (টি) পর্যবেক্ষণ করে এবং সেটের মধ্যে সংক্রমণ হার নির্বাচন করে। প্রতিটি স্লট টি-তে কোন ম্যাট্রিক্স নির্বাচন করতে হবে তা পরবর্তী উপধারায় বর্ণনা করা হয়েছে। এই সময়-পরিবর্তিত নেটওয়ার্ক মডেলটি প্রথম সেই ক্ষেত্রে তৈরি করা হয়েছিল যখন প্রতিটি স্লট টি-র সংক্রমণ হার একটি চ্যানেল স্টেট ম্যাট্রিক্স এবং একটি পাওয়ার বরাদ্দ ম্যাট্রিক্সের সাধারণ ফাংশন দ্বারা নির্ধারিত হয়। এই মডেলটি ব্যবহার করা যেতে পারে যখন অন্যান্য নিয়ন্ত্রণ সিদ্ধান্ত, যেমন সার্ভার বরাদ্দ, সাব-ব্যান্ড নির্বাচন, কোডিং প্রকার ইত্যাদি দ্বারা হার নির্ধারণ করা হয়। এটি ধরে নেয় যে সমর্থনযোগ্য সংক্রমণ হার জানা আছে এবং কোনও সংক্রমণ ত্রুটি নেই। বহু-প্রাপক বৈচিত্র্যের মাধ্যমে বেতার সম্প্রচারের সুবিধা কাজে লাগানো নেটওয়ার্কগুলি সহ সম্ভাব্য চ্যানেল ত্রুটি সহ নেটওয়ার্কগুলির জন্য ব্যাকপ্রেসার রাউটিংয়ের বর্ধিত সূত্রগুলি ব্যবহার করা যেতে পারে। ব্যাকপ্রেসার নিয়ন্ত্রণের সিদ্ধান্তগুলি প্রতিটি স্লট টি ব্যাকপ্রেসার নিয়ন্ত্রক এস (টি) পর্যবেক্ষণ করে এবং নিম্নলিখিত 3 টি পদক্ষেপ সম্পাদন করেঃ প্রথমত, প্রতিটি লিঙ্কের (এ, বি) জন্য, এটি ব্যবহারের জন্য একটি সর্বোত্তম পণ্য নির্বাচন করে। এরপরে, এটি নির্ধারণ করে যে কোন ম্যাট্রিক্সটি ব্যবহার করতে হবে। পরিশেষে, এটি পণ্যের পরিমাণ নির্ধারণ করে যা এটি সংযোগের মাধ্যমে প্রেরণ করবে (ক, খ) (সর্বাধিক, তবে সম্ভবত কিছু ক্ষেত্রে কম)। সর্বোত্তম পণ্য নির্বাচন করা প্রতিটি নোড তার নিজস্ব সারির ব্যাকলগ এবং তার বর্তমান প্রতিবেশীদের ব্যাকলগ পর্যবেক্ষণ করে। নোড a-এর একটি বর্তমান প্রতিবেশী হল একটি নোড b যাতে বর্তমান স্লটে একটি অ-শূন্য সংক্রমণ হার বেছে নেওয়া সম্ভব। সুতরাং, প্রতিবেশীরা সেট দ্বারা নির্ধারিত হয়। চরম ক্ষেত্রে, একটি নোডে প্রতিবেশী হিসাবে সমস্ত এন-1 অন্যান্য নোড থাকতে পারে। যাইহোক, এমন সেট ব্যবহার করা সাধারণ যা একটি নির্দিষ্ট ভৌগলিক দূরত্বের চেয়ে বেশি দ্বারা পৃথক হওয়া নোডগুলির মধ্যে সংক্রমণকে বাধা দেয়, বা যার একটি নির্দিষ্ট প্রান্তিকের নিচে প্রচারিত সংকেত শক্তি থাকবে। সুতরাং, প্রতিবেশীদের সংখ্যা N−1-এর তুলনায় অনেক কম হওয়া সাধারণ। চিত্রের উদাহরণ। 1 লিঙ্ক সংযোগের মাধ্যমে প্রতিবেশীদের চিত্রিত করে, যাতে নোড 5-এর প্রতিবেশী 4 এবং 6 থাকে। উদাহরণটি প্রতিবেশীদের মধ্যে একটি প্রতিসম সম্পর্কের পরামর্শ দেয় (যাতে 5 যদি 4-এর প্রতিবেশী হয়, তবে 4 হল 5-এর প্রতিবেশী), তবে সাধারণভাবে এটি হওয়ার দরকার নেই। প্রদত্ত নোডের প্রতিবেশীদের সেট বর্তমান স্লটে সংক্রমণের জন্য ব্যবহার করা যেতে পারে এমন আউটগোয়িং লিঙ্কগুলির সেট নির্ধারণ করে। প্রতিটি বহির্গামী সংযোগের (ক, খ) জন্য, সর্বোত্তম পণ্যকে এমন পণ্য হিসাবে সংজ্ঞায়িত করা হয় যা নিম্নলিখিত ডিফারেনশিয়াল ব্যাকলগ পরিমাণকে সর্বাধিক করেঃ সর্বোত্তম পণ্য বেছে নেওয়ার ক্ষেত্রে যে কোনও সম্পর্ক নির্বিচারে ভেঙে যায়। একটি উদাহরণ ছবিতে দেখানো হয়েছে। 2. উদাহরণটি ধরে নেয় যে প্রতিটি সারিতে বর্তমানে মাত্র 3টি পণ্য রয়েছেঃ লাল, সবুজ এবং নীল, এবং এগুলি প্যাকেটের পূর্ণসংখ্যা এককে পরিমাপ করা হয়। নির্দেশিত লিঙ্ক (1,2)-এর উপর দৃষ্টি নিবদ্ধ করে, ডিফারেনশিয়াল ব্যাকলগগুলি হলঃ অতএব, স্লট টি-তে লিঙ্ক (1,2) পাঠানোর জন্য সর্বোত্তম পণ্য হল সবুজ পণ্য। অন্যদিকে, স্লট টি-তে বিপরীত লিঙ্কে (2,1) পাঠানোর জন্য সর্বোত্তম পণ্য হল নীল পণ্য। প্রতিটি লিঙ্ক (এ, বি)-এর জন্য সর্বোত্তম পণ্য নির্ধারণ করা হয়ে গেলে, নেটওয়ার্ক নিয়ন্ত্রক নিম্নলিখিত ওজনগুলি গণনা করেনঃ ওজন হল লিঙ্ক (এ, বি)-এর জন্য সর্বোত্তম পণ্যের সাথে যুক্ত ডিফারেনশিয়াল ব্যাকলগের মান, যা 0 দিয়ে সর্বাধিক করা হয়। নিয়ন্ত্রক তারপর নিম্নলিখিত সর্বোচ্চ-ওজন সমস্যার সমাধান হিসাবে সংক্রমণ হার বেছে নেয় (নির্বিচারে বন্ধন ভাঙা): সর্বাধিক-ওজন সিদ্ধান্তের উদাহরণ হিসাবে, ধরুন যে বর্তমান স্লট টি-তে, 6 নোড নেটওয়ার্কের প্রতিটি লিঙ্কের ডিফারেনশিয়াল ব্যাকলগগুলি লিঙ্ক ওজনের দিকে পরিচালিত করেঃ যদিও সেটটিতে অগণিত সংখ্যক সম্ভাব্য সংক্রমণ হার ম্যাট্রিক্স থাকতে পারে, সরলতার জন্য ধরে নিন যে বর্তমান টপোলজি অবস্থা শুধুমাত্র 4 টি সম্ভাব্য পছন্দ স্বীকার করেঃ বর্তমান টপোলজি অবস্থা এস (টি)-এর অধীনে 4 টি সম্ভাব্য সংক্রমণ হার নির্বাচনের চিত্র। অপশন (ক) একক লিঙ্ক (1,5) সক্রিয় করে। অন্যান্য সমস্ত বিকল্প দুটি লিঙ্ক ব্যবহার করে, প্রতিটি সক্রিয় লিঙ্কের উপর 1 এর সংক্রমণ হার সহ। এই চারটি সম্ভাবনাকে ম্যাট্রিক্স আকারে উপস্থাপন করা হয়েছেঃ লক্ষ্য করুন যে নোড 6 এই সম্ভাবনার কোনওটির অধীনে পাঠাতে বা গ্রহণ করতে পারে না। এটি দেখা দিতে পারে কারণ নোড 6 বর্তমানে যোগাযোগ সীমার বাইরে। 4টি সম্ভাবনার প্রত্যেকটির জন্য হারের ওজনযুক্ত যোগফল হলঃ পছন্দ (ক): পছন্দ (খ): পছন্দ (গ): পছন্দ (ঘ): যেহেতু সর্বোচ্চ 12 ওজনের জন্য একটি টাই রয়েছে, তাই নেটওয়ার্ক নিয়ন্ত্রক বিকল্প বা বিকল্প বেছে নিয়ে নির্বিচারে টাই ভাঙতে পারে। রাউটিং ভেরিয়েবলগুলি চূড়ান্ত করা ধরুন এখন প্রতিটি লিঙ্কের জন্য সর্বোত্তম পণ্য নির্ধারণ করা হয়েছে এবং সংক্রমণের হারও নির্ধারণ করা হয়েছে। যদি প্রদত্ত লিঙ্কে (ক, খ) সর্বোত্তম পণ্যের জন্য ডিফারেনশিয়াল ব্যাকলগ ঋণাত্মক হয়, তবে বর্তমান স্লটে এই লিঙ্কে কোনও তথ্য স্থানান্তর করা হয় না। অন্যথায়, নেটওয়ার্কটি এই লিঙ্কের মাধ্যমে পণ্যের তথ্যের একক পাঠানোর প্রস্তাব দেয়। এটি প্রতিটি লিঙ্ক (এ, বি) এবং প্রতিটি পণ্য সি-এর জন্য রাউটিং ভেরিয়েবল সংজ্ঞায়িত করে করা হয়, যেখানেঃ এর মান স্লট টি-তে পণ্য সি ডেটা ওভার লিঙ্ক (এ, বি)-কে দেওয়া ট্রান্সমিশন হারকে উপস্থাপন করে। তবে, নোডগুলিতে তাদের সমস্ত আউটগোয়িং লিঙ্কে প্রস্তাবিত হারে ট্রান্সমিশন সমর্থন করার জন্য পর্যাপ্ত নির্দিষ্ট পণ্য নাও থাকতে পারে। এটি নোড এন এবং কমোডিটি সি-এর জন্য স্লট টি-তে উদ্ভূত হয় যদিঃ এই ক্ষেত্রে, সমস্ত ডেটা পাঠানো হয়, এবং প্রস্তাবিত হারের অব্যবহৃত অংশগুলি পূরণ করতে নাল ডেটা ব্যবহার করা হয়, প্রকৃত ডেটা এবং নাল ডেটা সংশ্লিষ্ট বহির্গামী লিঙ্কগুলির উপর নির্বিচারে বরাদ্দ করা হয় (প্রস্তাবিত হার অনুযায়ী)। একে বলা হয় সারি আন্ডারফ্লো পরিস্থিতি। এই ধরনের আন্ডারফ্লো নেটওয়ার্কের থ্রুপুট বা স্থিতিশীলতার বৈশিষ্ট্যগুলিকে প্রভাবিত করে না। স্বজ্ঞাতভাবে, এর কারণ হল আন্ডারফ্লো তখনই উদ্ভূত হয় যখন ট্রান্সমিটিং নোডে কম পরিমাণে ব্যাকলগ থাকে, যার অর্থ নোডটি অস্থিতিশীলতার ঝুঁকিতে নেই। বিলম্বের উন্নতি ব্যাকপ্রেসার অ্যালগরিদম কোনও পূর্ব-নির্দিষ্ট পথ ব্যবহার করে না। পথগুলি গতিশীলভাবে শেখা হয় এবং বিভিন্ন প্যাকেটের জন্য ভিন্ন হতে পারে। বিলম্ব খুব বড় হতে পারে, বিশেষত যখন সিস্টেমটি হালকাভাবে লোড করা হয় যাতে গন্তব্যের দিকে ডেটা ঠেলে দেওয়ার জন্য পর্যাপ্ত চাপ না থাকে। উদাহরণস্বরূপ, ধরুন একটি প্যাকেট নেটওয়ার্কে প্রবেশ করে এবং অন্য কিছুই প্রবেশ করে না। এই প্যাকেটটি নেটওয়ার্কের মধ্য দিয়ে হেঁটে যেতে পারে এবং কখনই তার গন্তব্যে পৌঁছতে পারে না কারণ কোনও চাপের ঢাল তৈরি হয় না। এটি ব্যাকপ্রেসারের থ্রুপুট অপ্টিমালিটি বা স্থিতিশীলতার বৈশিষ্ট্যগুলির বিরোধিতা করে না কারণ নেটওয়ার্কের যে কোনও সময়ে সর্বাধিক একটি প্যাকেট থাকে এবং তাই এটি তুচ্ছভাবে স্থিতিশীল (0 এর ডেলিভারি হার অর্জন, আগমনের হারের সমান)। পূর্ব-নির্দিষ্ট পথের একটি সেটে ব্যাকপ্রেসার প্রয়োগ করাও সম্ভব। এটি ক্ষমতা অঞ্চলটিকে সীমাবদ্ধ করতে পারে, তবে ইন-অর্ডার ডেলিভারি এবং বিলম্বের উন্নতি করতে পারে। ক্ষমতা অঞ্চলকে প্রভাবিত না করে বিলম্বের উন্নতির আরেকটি উপায় হল একটি বর্ধিত সংস্করণ ব্যবহার করা যা পক্ষপাতদুষ্টভাবে ওজনকে কাঙ্ক্ষিত দিকের সাথে সংযুক্ত করে। এই ধরনের পক্ষপাতের অনুকরণগুলি উল্লেখযোগ্য বিলম্বের উন্নতি দেখিয়েছে। মনে রাখবেন যে ব্যাকপ্রেসারের জন্য লাইনে ফার্স্ট-ইন-ফার্স্ট-আউট (এফআইএফও) পরিষেবার প্রয়োজন হয় না। দেখা গেছে যে লাস্ট-ইন-ফার্স্ট-আউট (এল. আই. এফ. ও) পরিষেবা থ্রুপুটকে প্রভাবিত না করে বেশিরভাগ প্যাকেটের জন্য বিলম্বকে নাটকীয়ভাবে উন্নত করতে পারে। ডিস্ট্রিবিউটেড ব্যাকপ্রেসার নোট করুন যে একবার সংক্রমণের হার নির্বাচন করা হয়ে গেলে, রাউটিং সিদ্ধান্তের ভেরিয়েবলগুলি একটি সহজ বিতরণ পদ্ধতিতে গণনা করা যেতে পারে, যেখানে প্রতিটি নোডের কেবল নিজের এবং তার প্রতিবেশীদের মধ্যে সারি ব্যাকলগের পার্থক্য সম্পর্কে জ্ঞানের প্রয়োজন হয়। যাইহোক, সংক্রমণ হার নির্বাচনের জন্য EQs-এ সর্বাধিক ওজনের সমস্যার সমাধান প্রয়োজন। (1)-(2)। বিশেষ ক্ষেত্রে যখন চ্যানেলগুলি অর্থোগোনাল হয়, তখন অ্যালগরিদমটির একটি প্রাকৃতিক বিতরণ বাস্তবায়ন থাকে এবং প্রতিটি নোডে পৃথক সিদ্ধান্তে হ্রাস পায়। যাইহোক, আন্তঃ-চ্যানেল হস্তক্ষেপ সহ নেটওয়ার্কগুলির জন্য সর্বাধিক ওজনের সমস্যাটি একটি কেন্দ্রীভূত নিয়ন্ত্রণ সমস্যা। কেন্দ্রীভূত উপায়েও এর সমাধান করা খুব কঠিন হতে পারে। সংকেত-থেকে-শব্দ-যোগ-হস্তক্ষেপ অনুপাত (এস. আই. এন. আর) দ্বারা নির্ধারিত লিঙ্ক হার সহ হস্তক্ষেপ নেটওয়ার্কগুলির জন্য একটি বিতরণ পদ্ধতি র্যান্ডমাইজেশন ব্যবহার করে করা যেতে পারে। প্রতিটি নোড এলোমেলোভাবে প্রতিটি স্লট টি প্রেরণ করার সিদ্ধান্ত নেয় (বর্তমানে পাঠানোর জন্য কোনও প্যাকেট না থাকলে একটি "নাল" প্যাকেট প্রেরণ করা হয়)। প্রকৃত সংক্রমণ হার এবং পাঠানোর জন্য সংশ্লিষ্ট প্রকৃত প্যাকেটগুলি 2-ধাপের হ্যান্ডশেক দ্বারা নির্ধারিত হয়ঃ প্রথম ধাপে, এলোমেলোভাবে নির্বাচিত ট্রান্সমিটার নোডগুলি একটি প্রকৃত সংক্রমণের আনুপাতিক সংকেত শক্তি সহ একটি পাইলট সংকেত পাঠায়। দ্বিতীয় ধাপে, সমস্ত সম্ভাব্য রিসিভার নোডগুলি ফলাফলের হস্তক্ষেপ পরিমাপ করে এবং সেই তথ্য ট্রান্সমিটারগুলিতে ফেরত পাঠায়। সমস্ত বহির্গামী লিঙ্কের (এন, বি) এস. আই. এন. আর স্তরগুলি তখন সমস্ত নোড এন-এর কাছে পরিচিত হয় এবং প্রতিটি নোড এন এই তথ্যের উপর ভিত্তি করে এর এবং ভেরিয়েবলগুলি নির্ধারণ করতে পারে। ফলস্বরূপ থ্রুপুট অগত্যা সর্বোত্তম নয়। যাইহোক, র্যান্ডম ট্রান্সমিশন প্রক্রিয়াটিকে চ্যানেল স্টেট প্রক্রিয়ার একটি অংশ হিসাবে দেখা যেতে পারে (যদি আন্ডারফ্লো-র ক্ষেত্রে নাল প্যাকেট পাঠানো হয়, যাতে চ্যানেল স্টেট প্রক্রিয়াটি অতীতের সিদ্ধান্তের উপর নির্ভর করে না)। অতএব, এই বিতরণ বাস্তবায়নের ফলস্বরূপ থ্রুপুট সমস্ত রাউটিং এবং সময়সূচী অ্যালগরিদমের শ্রেণীর উপর সর্বোত্তম যা এই ধরনের র্যান্ডমাইজড ট্রান্সমিশন ব্যবহার করে। বিকল্প ডিস্ট্রিবিউটেড বাস্তবায়নকে মোটামুটিভাবে দুটি শ্রেণীতে ভাগ করা যেতে পারেঃ প্রথম শ্রেণীর অ্যালগরিদমগুলি সর্বাধিক ওজনের সমস্যার জন্য ধ্রুবক গুণক ফ্যাক্টর আনুমানিক বিবেচনা করে এবং ধ্রুবক-ফ্যাক্টর থ্রুপুট ফলাফল দেয়। দ্বিতীয় শ্রেণীর অ্যালগরিদমগুলি সময়ের সাথে সাথে সর্বাধিক ওজনের সমস্যার সমাধান আপডেট করার উপর ভিত্তি করে সর্বাধিক ওজনের সমস্যার যোগাত্মক অনুমান বিবেচনা করে। এই দ্বিতীয় শ্রেণীর অ্যালগরিদমগুলির জন্য স্ট্যাটিক চ্যানেল শর্ত এবং দীর্ঘতর (প্রায়শই অ-বহুপদী) অভিসারের সময় প্রয়োজন বলে মনে হয়, যদিও তারা যথাযথ অনুমানের অধীনে সর্বাধিক থ্রুপুট অর্জন করতে পারে। পুরানো সারি ব্যাকলগ তথ্যের সাথে প্রয়োগ করা হলে যোগাত্মক অনুমানগুলি প্রায়শই ব্যাকপ্রেসারের অনুকূলতা প্রমাণ করার জন্য কার্যকর হয় (নীলি পাঠ্যের অনুশীলন 4.10 দেখুন)। লিয়াপুনভ ড্রিফ্টের মাধ্যমে গাণিতিক নির্মাণ এই বিভাগটি দেখায় যে কীভাবে ব্যাকপ্রেসার অ্যালগরিদমটি একটি স্লট থেকে অন্য স্লটে সারি ব্যাকলগের বর্গক্ষেত্রের যোগফলের পরিবর্তনের উপর লোভের সাথে একটি সীমা হ্রাস করার প্রাকৃতিক পরিণতি হিসাবে উদ্ভূত হয়। সিদ্ধান্তের সীমাবদ্ধতা এবং সারি আপডেট সমীকরণ নিয়ন্ত্রণ করুন উপরের বিভাগে বর্ণিত এন নোড সহ একটি মাল্টি-হপ নেটওয়ার্ক বিবেচনা করুন। প্রতিটি স্লট টি, নেটওয়ার্ক নিয়ন্ত্রক টপোলজি অবস্থা এস (টি) পর্যবেক্ষণ করে এবং নিম্নলিখিত সীমাবদ্ধতার সাপেক্ষে সংক্রমণ হার এবং রাউটিং ভেরিয়েবলগুলি বেছে নেয়ঃ একবার এই রাউটিং ভেরিয়েবলগুলি নির্ধারিত হয়ে গেলে, সংক্রমণ করা হয় (প্রয়োজনে নিষ্ক্রিয় ভরাট ব্যবহার করে), এবং ফলস্বরূপ সারি ব্যাকলগগুলি নিম্নলিখিতগুলিকে সন্তুষ্ট করেঃ নতুন পণ্য সি ডেটার এলোমেলো পরিমাণ কোথায় যা স্লট টি-তে নোড এন-এ বহিরাগতভাবে আসে এবং স্লট টি-তে লিঙ্ক (এন, বি)-তে পণ্য সি ট্র্যাফিকের জন্য বরাদ্দ সংক্রমণ হার। নোট করুন যে পণ্য সি ডেটার পরিমাণের চেয়ে বেশি হতে পারে যা আসলে স্লট টি-তে লিঙ্ক (এ, বি)-তে প্রেরণ করা হয়। এটি কারণ নোড এন-এ পর্যাপ্ত ব্যাকলগ নাও থাকতে পারে। এই একই কারণে, ইক্যু। (6) সমতার পরিবর্তে একটি অসমতা, কারণ স্লট টি-তে পণ্য সি থেকে নোড এন-এর প্রকৃত অন্তঃসত্ত্বা আগমনের চেয়ে বেশি হতে পারে। ইক্যু-এর একটি গুরুত্বপূর্ণ বৈশিষ্ট্য। (6) সিদ্ধান্তের চলকগুলি সারির ব্যাকলগ থেকে স্বাধীনভাবে বেছে নেওয়া হলেও এটি বহাল থাকে। এটি ধরে নেওয়া হয় যে সমস্ত স্লট টি এবং সকলের জন্য, যেহেতু কোনও সারি নিজের জন্য নির্ধারিত ডেটা সঞ্চয় করে না। লিয়াপুনভ ড্রিফ্ট বর্তমান সারি ব্যাকলগের ম্যাট্রিক্স হিসাবে সংজ্ঞায়িত করুন। নিম্নলিখিত অ-ঋণাত্মক ফাংশনটিকে সংজ্ঞায়িত করুন, যাকে লিয়াপুনভ ফাংশন বলা হয়ঃ এটি সারি ব্যাকলগের বর্গগুলির সমষ্টি (পরবর্তী বিশ্লেষণে সুবিধার জন্য শুধুমাত্র 1/2 দ্বারা গুণিত)। উপরের যোগফলটি সমস্ত n, c-এর যোগফলের সমান, কারণ সমস্ত এবং সমস্ত স্লট t-এর জন্য। শর্তাধীন লিয়াপুনভ প্রবাহকে সংজ্ঞায়িত করা হয়েছেঃ লক্ষ্য করুন যে নিম্নলিখিত অসমতা সকলের জন্য রয়েছে,,: সারি আপডেট সমীকরণ (Eq। (6)) এবং উপরের অসমতা ব্যবহার করে, এটি দেখানো কঠিন নয় যে সমস্ত স্লট টি এবং যে কোনও অ্যালগরিদমের অধীনে সংক্রমণ এবং রাউটিং ভেরিয়েবল বেছে নেওয়ার জন্য এবংঃ যেখানে বি একটি সীমাবদ্ধ ধ্রুবক যা আগমনের দ্বিতীয় মুহুর্ত এবং সংক্রমণের হারের সর্বাধিক সম্ভাব্য দ্বিতীয় মুহুর্তের উপর নির্ভর করে। ব্যাকপ্রেসার অ্যালগরিদমটি প্রতিটি স্লট টি পর্যবেক্ষণ এবং নির্বাচন করার জন্য এবং ড্রিফ্ট বাউন্ড ইক্যু-এর ডান দিকটি হ্রাস করার জন্য ডিজাইন করা হয়েছে। (7)। যেহেতু বি একটি ধ্রুবক এবং ধ্রুবক, এটি সর্বাধিককরণের সমানঃ যেখানে সীমাবদ্ধ যোগফলগুলি সর্বাধিককরণের সিদ্ধান্তকে আলোকিত করার জন্য প্রত্যাশার মধ্য দিয়ে ঠেলে দেওয়া হয়েছে। সুযোগসন্ধানীভাবে একটি প্রত্যাশাকে সর্বাধিক করার নীতি দ্বারা, উপরের প্রত্যাশাটি তার অভ্যন্তরে ফাংশনকে সর্বাধিক করে সর্বাধিক করা হয় (পর্যবেক্ষিত, দেওয়া)। সুতরাং, একজন Eqs নির্বাচন করে এবং সীমাবদ্ধতার সাপেক্ষে। (3)-(5) সর্বাধিক করাঃ কোন সিদ্ধান্তগুলি উপরের সিদ্ধান্তগুলিকে সর্বাধিক করে তোলে তা তাৎক্ষণিকভাবে স্পষ্ট নয়। যোগফল পরিবর্তন করে এটি আলোকিত করা যেতে পারে। প্রকৃতপক্ষে, উপরের অভিব্যক্তিটি নীচের মত একইঃ ওজনকে নোড a এবং b-এর মধ্যে পণ্য c-এর বর্তমান ডিফারেনশিয়াল ব্যাকলগ বলা হয়। ধারণাটি হল সিদ্ধান্তের চলকগুলি বেছে নেওয়া যাতে উপরের ওজনযুক্ত যোগফলকে সর্বাধিক করা যায়, যেখানে ওজনগুলি ডিফারেনশিয়াল ব্যাকলগ হয়। স্বজ্ঞাতভাবে, এর অর্থ বৃহত্তর ডিফারেনশিয়াল ব্যাকলগের দিকে বৃহত্তর হার বরাদ্দ করা। স্পষ্টতই যে কোনও সময় বেছে নেওয়া উচিত। উপরন্তু, একটি নির্দিষ্ট লিঙ্কের জন্য দেওয়া, এটি দেখানো কঠিন নয় যে সর্বোত্তম নির্বাচন, Eqs সাপেক্ষে। (3)-(5), নিম্নরূপ নির্ধারণ করা হয়ঃ প্রথমে এমন পণ্যটি খুঁজে বের করুন যা লিঙ্ক (এ, বি)-এর জন্য ডিফারেনশিয়াল ব্যাকলগকে সর্বাধিক করে। যদি সর্বাধিক ডিফারেনশিয়াল ব্যাকলগ লিঙ্ক (এ, বি)-এর জন্য ঋণাত্মক হয়, তবে লিঙ্ক (এ, বি)-এ সমস্ত পণ্যের জন্য বরাদ্দ করুন। অন্যথায়, এই লিঙ্কে পণ্যের জন্য সম্পূর্ণ লিঙ্ক হার এবং অন্যান্য সমস্ত পণ্যের জন্য শূন্য হার বরাদ্দ করুন। এই পছন্দের সাথে, এটি নিম্নরূপঃ স্লট টি-তে (0 দিয়ে সর্বাধিক) লিঙ্ক (এ, বি)-এর জন্য সর্বোত্তম পণ্যের ডিফারেনশিয়াল ব্যাকলগ কোথায়ঃ এটি শুধুমাত্র বেছে নেওয়ার জন্য রয়ে গেছে। এটি নিম্নলিখিত সমাধানের মাধ্যমে করা হয়ঃ উপরের সমস্যাটি Eqs-এর সর্বোচ্চ ওজনের সমস্যার অনুরূপ। (1)-(2)। ব্যাকপ্রেসার অ্যালগরিদম সর্বাধিক ওজনের সিদ্ধান্তগুলি ব্যবহার করে এবং তারপরে উপরে বর্ণিত সর্বাধিক ডিফারেনশিয়াল ব্যাকলগের মাধ্যমে রাউটিং ভেরিয়েবলগুলি বেছে নেয়। ব্যাকপ্রেসার অ্যালগরিদমের একটি উল্লেখযোগ্য বৈশিষ্ট্য হল যে এটি শুধুমাত্র পর্যবেক্ষিত টপোলজি অবস্থা এস (টি) এবং সেই স্লটের জন্য সারি ব্যাকলগের উপর ভিত্তি করে প্রতিটি স্লট টি লোভের সাথে কাজ করে। সুতরাং, এর জন্য আগমনের হার বা টপোলজি অবস্থা সম্ভাব্যতা সম্পর্কে জ্ঞানের প্রয়োজন হয় না। কর্মক্ষমতা বিশ্লেষণ এই বিভাগটি ব্যাকপ্রেসার অ্যালগরিদমের থ্রুপুট অপ্টিমালিটি প্রমাণ করে। সরলতার জন্য, পরিস্থিতি যেখানে ঘটনাগুলি স্বাধীন এবং অভিন্নভাবে বিতরণ করা হয় (অর্থাৎ) ওভার স্লট বিবেচনা করা হয়, যদিও একই অ্যালগরিদম non-i.i.d এ কাজ করতে দেখানো যেতে পারে। পরিস্থিতি (নীচে Non-i.i.d-এর অধীনে দেখুন। অপারেশন এবং সর্বজনীন সময়সূচী)। গতিশীল আগমন ধরা যাক স্লট টি-তে বহির্জাগতিক আগমনের ম্যাট্রিক্স। ধরে নিন যে এই ম্যাট্রিক্সটি স্বাধীন এবং অভিন্নভাবে বিতরণ করা হয়েছে (অর্থাৎ) সীমাবদ্ধ দ্বিতীয় মুহূর্ত এবং উপায় সহ স্লটগুলির উপরঃ এটি ধরে নেওয়া হয় যে সকলের জন্য, যেহেতু কোনও তথ্য আসে না যা নিজের জন্য নির্ধারিত। সুতরাং, আগমনের হারের ম্যাট্রিক্স হল অ-ঋণাত্মক বাস্তব সংখ্যার একটি ম্যাট্রিক্স, যার তির্যকে শূন্য থাকে। নেটওয়ার্ক ক্ষমতা অঞ্চল ধরে নিন টপোলজি অবস্থা এস (টি) হল আই. ডি। সম্ভাব্যতা সহ স্লটগুলির উপর (যদি এস (টি) বাস্তব-মূল্যবান এন্ট্রি সহ ভেক্টরগুলির একটি অগণিত অসীম সেটে মান নেয়, তবে এটি একটি সম্ভাব্যতা বিতরণ, কোনও সম্ভাব্যতা ভর ফাংশন নয়)। নেটওয়ার্কের জন্য একটি সাধারণ অ্যালগরিদম প্রতিটি স্লট টি পর্যবেক্ষণ করে এবং Eqs-এর সীমাবদ্ধতা অনুযায়ী সংক্রমণ হার এবং রাউটিং ভেরিয়েবল নির্বাচন করে। (3)-(5)। নেটওয়ার্ক ক্ষমতা অঞ্চল হল সমস্ত আগমনের হার ম্যাট্রিক্সের সেটের সমাপ্তি যার জন্য একটি অ্যালগরিদম বিদ্যমান যা নেটওয়ার্ককে স্থিতিশীল করে। সমস্ত সারির স্থিতিশীলতা বোঝায় যে নেটওয়ার্কে ট্র্যাফিকের মোট ইনপুট হার তার গন্তব্যে বিতরণ করা মোট তথ্যের হারের সমান। এটি দেখানো যেতে পারে যে ক্ষমতা অঞ্চলে যে কোনও আগমনের হার ম্যাট্রিক্সের জন্য, একটি স্থির এবং এলোমেলো অ্যালগরিদম রয়েছে যা শুধুমাত্র এস (টি)-এর উপর ভিত্তি করে সিদ্ধান্তের ভেরিয়েবল এবং প্রতিটি স্লট টি বেছে নেয় (এবং তাই স্বাধীনভাবে সারি ব্যাকলগ থেকে) যা সকলের জন্য নিম্নলিখিত ফলাফল দেয়ঃ এমন একটি স্থির এবং এলোমেলো অ্যালগরিদম যা শুধুমাত্র এস (টি)-এর উপর ভিত্তি করে সিদ্ধান্ত নেয় তাকে এস-অনলি অ্যালগরিদম বলা হয়। এটি অনুমান করা প্রায়শই দরকারী যে এটি অভ্যন্তরীণ, যাতে এমন একটি থাকে যে, যেখানে 1 যদি, এবং শূন্য অন্য। সেক্ষেত্রে, একটি এস-অনলি অ্যালগরিদম রয়েছে যা সকলের জন্য নিম্নলিখিত ফলাফল দেয়ঃ একটি প্রযুক্তিগত প্রয়োজনীয়তা হিসাবে, এটি ধরে নেওয়া হয় যে এই হারগুলি বেছে নেওয়ার জন্য যে কোনও অ্যালগরিদমের অধীনে সংক্রমণের হারের দ্বিতীয় মুহুর্তগুলি সীমাবদ্ধ। একটি সীমাবদ্ধ সর্বোচ্চ হার থাকলে এটি তুচ্ছভাবে প্রযোজ্য। এস-অনলি অ্যালগরিদমের সাথে তুলনা করা হচ্ছে কারণ ব্যাকপ্রেসার অ্যালগরিদম পর্যবেক্ষণ করে এবং এস (টি) প্রতিটি স্লট টি এবং সিদ্ধান্তগুলি বেছে নেয় এবং ড্রিফ্ট বাউন্ড ইক্যু-এর ডান দিকটি হ্রাস করে। (7), আমাদের আছেঃ কোথায় এবং কোথায় এমন কোনও বিকল্প সিদ্ধান্ত রয়েছে যা ইক্যু-কে সন্তুষ্ট করে। (3)-(5), এলোমেলো সিদ্ধান্ত সহ। এখন ধরে নিন। তারপর একটি এস-অনলি অ্যালগরিদম রয়েছে যা ইক্যু-কে সন্তুষ্ট করে। (8)। এটিকে Eq-এর ডান দিকে প্লাগ করা। (10) এবং উল্লেখ করা যে এই এস-অনলি অ্যালগরিদমের অধীনে প্রদত্ত শর্তাধীন প্রত্যাশা নিঃশর্ত প্রত্যাশার মতোই (কারণ এস (টি) হল আই. আই. ডি। স্লটগুলির উপর, এবং এস-অনলি অ্যালগরিদম বর্তমান সারি ব্যাকলগগুলির থেকে স্বাধীন) ফলন দেয়ঃ সুতরাং, একটি দ্বিঘাত লিয়াপুনভ ফাংশনের প্রবাহ সমস্ত স্লট টি-এর জন্য একটি ধ্রুবক বি-এর চেয়ে কম বা সমান। এই সত্যটি, এই ধারণার সাথে যে সারি আগমনগুলি দ্বিতীয় মুহুর্তে সীমাবদ্ধ রয়েছে, সমস্ত নেটওয়ার্ক সারির জন্য নিম্নলিখিতগুলি বোঝায়ঃ গড় সারির আকার সম্পর্কে আরও ভাল বোঝার জন্য, কেউ অনুমান করতে পারে যে আগমনের হারগুলি অভ্যন্তরীণ, তাই একটি Eq রয়েছে। (9) কিছু বিকল্প-শুধুমাত্র অ্যালগরিদমের জন্য প্রযোজ্য। Eq প্লাগ করা হচ্ছে। (9) Eq এর ডান দিকে। (10) ফলনঃ যা থেকে একজন অবিলম্বে অর্জন করে (দেখুন): ক্ষমতা অঞ্চলের সীমানার দূরত্ব শূন্যে যাওয়ার সাথে সাথে এই গড় সারির আকার বৃদ্ধি পায়। এটি আগমনের হার এবং পরিষেবার হারের সাথে একক এম/এম/1 সারির মতো একই গুণগত কর্মক্ষমতা, যেখানে গড় সারির আকার কোথায়, তার সাথে আনুপাতিক। উপরের সূত্রের এক্সটেনশন Non-i.i.d। অপারেশন এবং সার্বজনীন সময়সূচী উপরের বিশ্লেষণটি ধরে নেয় অর্থাৎ সরলতার জন্য বৈশিষ্ট্য। যাইহোক, একই ব্যাকপ্রেসার অ্যালগরিদমকে non-i.i.d-এ শক্তিশালীভাবে কাজ করতে দেখানো যেতে পারে। পরিস্থিতি। যখন আগমনের প্রক্রিয়া এবং টপোলজি অবস্থা এরগোডিক হয় তবে অগত্যা নয় অর্থাৎ, ব্যাকপ্রেসার তখনও সিস্টেমকে স্থিতিশীল করে। আরও সাধারণভাবে, একটি সর্বজনীন সময়সূচী পদ্ধতি ব্যবহার করে, এটি নির্বিচারে (সম্ভবত অ-আর্গোডিক) নমুনা পথের জন্য স্থিতিশীলতা এবং অনুকূল বৈশিষ্ট্য সরবরাহ করতে দেখানো হয়েছে। ইউটিলিটি অপ্টিমাইজেশন এবং পেনাল্টি মিনিমাইজেশন সহ ব্যাকপ্রেসার একটি ড্রিফ্ট-প্লাস-পেনাল্টি কৌশলের মাধ্যমে প্রবাহ নিয়ন্ত্রণের সাথে একত্রে কাজ করে বলে দেখানো হয়েছে। এই কৌশলটি লোভের সাথে প্রবাহ এবং একটি ওজনযুক্ত পেনাল্টি অভিব্যক্তি সর্বাধিক করে তোলে। পেনাল্টি একটি প্যারামিটার ভি দ্বারা ওজন করা হয় যা একটি পারফরম্যান্স ট্রেডঅফ নির্ধারণ করে। এই কৌশলটি নিশ্চিত করে যে থ্রুপুট ইউটিলিটি সর্বোত্তমতার ও (1/ভি) এর মধ্যে রয়েছে যেখানে গড় বিলম্ব ও (ভি)। সুতরাং, গড় বিলম্বের একটি সংশ্লিষ্ট বিনিময় সহ, উপযোগিতাকে ইচ্ছাকৃতভাবে অনুকূলতার কাছাকাছি ঠেলে দেওয়া যেতে পারে। গড় শক্তি হ্রাসকরণ এবং আরও সাধারণ নেটওয়ার্ক বৈশিষ্ট্যগুলির অনুকূলকরণের জন্য অনুরূপ বৈশিষ্ট্যগুলি দেখানো যেতে পারে। তরল মডেল বিশ্লেষণ, যৌথ তরল বিশ্লেষণ এবং ল্যাগ্রেঞ্জ গুণক বিশ্লেষণ, উত্তল অপ্টিমাইজেশন এবং স্টোকাস্টিক গ্রেডিয়েন্ট ব্যবহার করে একটি নেটওয়ার্ক ইউটিলিটি সর্বাধিক করার সময় সারিগুলিকে স্থিতিশীল করার জন্য বিকল্প অ্যালগরিদম তৈরি করা হয়েছে। এই পদ্ধতিগুলি ও (1/ভি), ও (ভি) উপযোগিতা-বিলম্বের ফলাফল প্রদান করে না। আরও দেখুন এ. ও. ডি. ভি ডাইভারসিটি ব্যাকপ্রেসার রাউটিং (ডি. আই. ভি. বি. এ. আর) ড্রিফ্ট প্লাস পেনাল্টি এক্সওআর জিওগ্রাফিক রাউটিং অ্যাডহক রাউটিং প্রোটোকলের তালিকা লিয়াপুনভ অপ্টিমাইজেশন রেফারেন্স প্রাথমিক উৎস এল. তাসসিউলাস এবং এ. এফ্রেমিডিস, "মাল্টিহপ রেডিও নেটওয়ার্কে সর্বাধিক থ্রুপুটের জন্য সীমাবদ্ধ সারি ব্যবস্থা এবং সময়সূচী নীতির স্থিতিশীলতা বৈশিষ্ট্য", স্বয়ংক্রিয় নিয়ন্ত্রণে আই. ই. ই. ই লেনদেন, খণ্ড। 37, না। 12, পিপি। 1936-1948, ডিসেম্বর 1992। এল. জর্জিয়াডিস, এম. জে. নেলি, এবং এল. তাসসিউলাস, "রিসোর্স অ্যালোকেশন অ্যান্ড ক্রস-লেয়ার কন্ট্রোল ইন ওয়্যারলেস নেটওয়ার্কস", ফাউন্ডেশনস অ্যান্ড ট্রেন্ডস ইন নেটওয়ার্কিং, খণ্ড। 1, না। 1, পিপি। 1-149,2006। এম. জে. নীলি। যোগাযোগ এবং ক্যুইং সিস্টেমে অ্যাপ্লিকেশন সহ স্টোকাস্টিক নেটওয়ার্ক অপ্টিমাইজেশন, "মরগান এবং ক্লেপুল, 2010। নেটওয়ার্কিং অ্যালগরিদম সারি তত্ত্ব রাউটিং অ্যালগরিদম