💻 computer science

Queue-Aware Task Offloading in the ComputingContinuum under Dynamic Workloads

यह शोध पत्र कंप्यूटिंग कॉन्टिनम के लिए एक कतार-जागरूक (queue-aware) टास्क ऑफलोडिंग विधि प्रस्तावित करता है जो परिवर्तनशील वर्कलोड के तहत कार्यों को गतिशील रूप से असाइन करने के लिए विश्लेषणात्मक रूप से सुधारा गया G/G/c विलंब सन्निकटन (delay approximation) को वास्तविक समय के कतार अवलोकनों के साथ संकरित (hybridize) करता है, जिससे बिना किसी प्रशिक्षण या अंशांकन (calibration) के मौजूदा बेसलाइन की तुलना में विलंबता और अनुमान त्रुटि को महत्वपूर्ण रूप से कम किया जा सकता है।

मूल लेखक: Lluis Mas, Jordi Mateo, Jordi Vilaplana, Josep Rius

प्रकाशित 2026-07-09

📖 5 मिनट में पढ़ें🧠 गहराई से पढ़ें

CC BY 4.0

मूल लेखक: Lluis Mas, Jordi Mateo, Jordi Vilaplana, Josep Rius

मूल पेपर CC BY 4.0 (https://creativecommons.org/licenses/by/4.0/) के तहत लाइसेंस किया गया है। ✨ नीचे दिए गए पेपर की यह व्याख्या AI से तैयार की गई है। इसे लेखकों ने न तो लिखा है, न इसका समर्थन किया है। तकनीकी सटीकता के लिए मूल पेपर देखें। पूरा डिस्क्लेमर पढ़ें

कल्पना कीजिए कि आप एक व्यस्त डिलीवरी सर्विस चला रहे हैं जिसमें तीन प्रकार के ड्राइवर हैं:

लोकल राइडर (Local Rider): एक साइकिल सवार जो ठीक आपके दरवाजे के बाहर है (जल्दी पहुँच सकता है, लेकिन एक बार में केवल एक ही पैकेज ले जा सकता है)।
एज वैन (Edge Van): एक छोटी डिलीवरी ट्रक जो सड़क के नीचे पार्क है (दो पैकेज ले जा सकती है, थोड़ी दूर है)।
क्लाउड फ्लीट (Cloud Fleet): एक विशाल गोदाम जहाँ सैकड़ों ट्रक हैं (हजारों पैकेज ले जा सकती है, लेकिन यह बहुत दूर है)।

हर बार जब एक नया पैकेज (एक "टास्क") आता है, तो आपको तुरंत निर्णय लेना होता है: इस पैकेज को कौन सा ड्राइवर ले जाएगा?

यदि आप सब कुछ लोकल राइडर को भेज देते हैं, तो वे काम के बोझ से दब जाते हैं और लाइन लंबी हो जाती है। यदि आप सब कुछ क्लाउड फ्लीट को भेज देते हैं, तो यात्रा का समय बहुत अधिक हो जाता है। लक्ष्य यह है कि पैकेज को यथासंभव तेज़ी से डिलीवर करने के लिए सही संतुलन बनाया जाए।

समस्या: "अनुमान लगाने का खेल" (The Guessing Game)

वास्तविक दुनिया में, ट्रैफिक अप्रत्याशित होता है। कभी-कभी अचानक ऑर्डर्स की बाढ़ (एक "बर्स्ट") आ जाती है, और कभी-कभी किसी पैकेज को प्रोसेस करने में बहुत लंबा समय लग जाता है (जैसे कि एक भारी बॉक्स जिसे लोड करने में बहुत समय लगता है)।

पिछले तरीकों ने इसे दो तरह से हल करने की कोशिश की, जिनमें दोनों की अपनी कमियाँ थीं:

"गणितीय सिद्धांतकार" (The Mathematical Theorist): यह तरीका जटिल सूत्रों का उपयोग करता है अनुमान लगाने के लिए कि औसत ट्रैफिक के आधार पर लाइनें कितनी होनी चाहिए। यह तब बहुत अच्छा होता है जब ट्रैफिक स्थिर हो, लेकिन यदि अचानक भीड़ आ जाए, तो गणित प्रतिक्रिया देने में बहुत धीमा होता है। यह कल के मौसम के पूर्वानुमान को देखकर आज छाता ले जाने का निर्णय लेने जैसा है।
"देखने और समझने" वाला तरीका (The Look-and-See Method): यह तरीका बस अभी की लाइन को देखता है। यदि लाइन छोटी है, तो यह पैकेज वहां भेज देता है। लेकिन लाइनें पेचीदा हो सकती हैं; एक छोटी लाइन अगले ही सेकंड बहुत बड़ी हो सकती है। यह तरीका उस ड्राइवर की तरह है जो हरा सिग्नल देखकर तेज़ हो जाता है, लेकिन एक पल बाद लाल सिग्नल पर टकरा जाता है।

समाधान: "स्मार्ट हाइब्रिड" ड्राइवर (The Smart Hybrid Driver)

लेखकों ने एक नया तरीका बनाया जिसे क्यू-अवेयर टास्क ऑफलोडिंग (Queue-Aware Task Offloading) कहा गया है। इसे एक सुपर-स्मार्ट डिस्पैचर के रूप में समझें जो दोनों दुनियाओं के सर्वश्रेष्ठ गुणों को जोड़ता है।

यहाँ उनका "स्मार्ट हाइब्रिड" कैसे काम करता है:

"गणित" वाला हिस्सा (क्रिस्टल बॉल): यह एक विशेष सूत्र (जो एलन-कनीन फॉर्मूला पर आधारित है) का उपयोग करता है कि लाइन कितनी लंबी होगी इसका अनुमान लगाने के लिए। यह स्थिरता के लिए बहुत अच्छा है। यह जानता है कि यदि लाइन लंबी हो रही है, तो यह वास्तव में लंबी होने वाली है, इससे पहले कि लाइन वास्तव में बढ़े।
"आँखों" वाला हिस्सा (कैमरा): यह वास्तविक समय में लाइन को भी देखता है। यदि लाइन में 10 लोग खड़े हैं, तो यह 10 लोगों को देखता है।
"मिक्सिंग" का जादू: यह जादू है। डिस्पैचर केवल एक को नहीं चुनता, बल्कि यह दोनों को एक स्मूदी की तरह मिला देता है।
- जब लाइन खाली होती है: यह गणित (क्रिस्टल बॉल) पर भरोसा करता है क्योंकि कैमरा कुछ नहीं देख पाता, लेकिन गणित जानता है कि ट्रैफिक आने वाला है।
- जब लाइन भरी होती है: यह आँखों (कैमरा) पर भरोसा करता है क्योंकि गणित शायद अराजकता देखने में एक सेकंड की देरी कर दे।
- द स्विच (The Switch): जैसे-जैसे लाइन अधिक भीड़भाड़ वाली होती जाती है, डिस्पैचर कैमरे पर अधिक भरोसा करता है। जैसे-जैसे भीड़ कम होती जाती है, वह गणित पर अधिक भरोसा करता है। यह बिना किसी मानवीय हस्तक्षेप के अपने आप होता है।

यह बेहतर क्यों है?

लेखकों ने इस तरीके का परीक्षण दो तरीकों से किया:

एक कंप्यूटर सिमुलेशन: एक वर्चुअल दुनिया जहाँ वे लाखों पैकेज और अचानक लगने वाले ट्रैफिक जाम का अनुकरण (simulate) कर सकते थे।
एक वास्तविक दुनिया का टेस्टबेड: उन्होंने वास्तविक वेब सर्वर और HTTP अनुरोधों का उपयोग करके एक वास्तविक सिस्टम बनाया ताकि यह सुनिश्चित हो सके कि कंप्यूटर सिमुलेशन झूठ नहीं बोल रहा है।

परिणाम:

कम देरी: स्मार्ट हाइब्रिड विधि ने "केवल गणित" या "देखने और समझने" वाले तरीकों की तुलना में औसतन तेजी से पैकेज डिलीवर किए।
निष्पक्षता (Fairness): यह विशेष रूप से "भारी" पैकेज (ऐसे टास्क जिन्हें लंबा समय लगता है) को संभालने में बहुत अच्छा था। पुराने तरीके छोटे और तेज़ पैकेज के प्रवाह के पीछे फंस जाते थे। स्मार्ट हाइब्रिड ने महसूस किया, "अरे, यह बड़ा पैकेज बहुत समय लेने वाला है, चलिए इसे बड़े फ्लीट में भेजते हैं ताकि यह छोटे पैकेजों को न रोके।"
गति: निर्णय लेने की प्रक्रिया अविश्वसनीय रूप से तेज़ (माइक्रोसेकंड में) थी, जिसका अर्थ है कि इसने सिस्टम को धीमा नहीं किया।

निष्कर्ष

यह पेपर सिद्ध करता है कि एक पूर्वानुमानित सूत्र को वास्तविक समय के अवलोकन के साथ जोड़कर, और सिस्टम को यह तय करने देकर कि उसे प्रत्येक पर कितना भरोसा करना चाहिए, आप अपनी डिलीवरी सर्विस को सुचारू रूप से चला सकते हैं, भले ही ट्रैफिक अराजक और अप्रत्याशित हो। यह एक "दोनों दुनियाओं के सर्वश्रेष्ठ" दृष्टिकोण का उपयोग करता है जिसे काम करने के लिए किसी इंसान द्वारा प्रशिक्षित करने या महंगे सुपरकंप्यूटर की आवश्यकता नहीं होती है।

तकनीकी सारांश: गतिशील वर्कलोड के तहत कंप्यूटिंग कॉन्टिनम में क्यू-अवेयर टास्क ऑफलोडिंग

समस्या विवरण

कंप्यूटिंग कॉन्टिनम स्थानीय उपकरणों, एज नोड्स और क्लाउड सिस्टम को एक एकीकृत आर्किटेक्चर में एकीकृत करता है। इस वातावरण में एक केंद्रीय चुनौती टास्क ऑफलोडिंग (task offloading) है: यह निर्णय लेना कि आने वाले कार्य (task) को स्थानीय रूप से, एज पर, या क्लाउड में निष्पादित किया जाए। यह निर्णय ऑनलाइन, गतिशील और साझा स्थितियों के तहत लिया जाना चाहिए जहाँ सिस्टम का व्यवहार अनुमान लगाना कठिन होता है।

मुख्य कठिनाइयाँ शामिल हैं:

क्यूइंग प्रभाव (Queueing Effects): जैसे-जैसे उपयोग क्षमता के करीब पहुँचता है, प्रतीक्षा समय (waiting time) विलंबता (latency) का प्रमुख घटक बन जाता है।
सेवा परिवर्तनशीलता (Service Variability): सेवा समय अक्सर हेवी-टेल्ड वितरण (जैसे, पारेटो/Pareto) प्रदर्शित करता है, जिसे मानक घातांकीय मॉडल (M/M/c) पकड़ने में विफल रहते हैं, जिससे देरी का काफी कम अनुमान लगता है।
गतिशील वर्कलोड (Dynamic Workloads): ट्रैफ़िक अक्सर अचानक उछाल (bursty) वाला और समय के साथ परिवर्तनशील होता है, जिससे स्थिर-अवस्था (steady-state) विश्लेषणात्मक मॉडल तात्कालिक निर्णय लेने के लिए अपर्याप्त हो जाते हैं।
मौजूदा दृष्टिकोणों की सीमाएँ:
- विश्लेषणात्मक मॉडल (Analytical Models): स्थिर स्थितियों और निश्चित मापदंडों को मानते हैं, जो तात्कालिक भीड़भाड़ के प्रति प्रतिक्रिया करने में विफल रहते हैं।
- क्यू-स्टेट अवलोकन (जैसे, JSQ): तुरंत प्रतिक्रिया करते हैं लेकिन शोर युक्त (noisy) होते हैं, अल्पकालिक उतार-चढ़ाव के प्रति संवेदनशील होते हैं, और सेवा-समय परिवर्तनशीलता को अनदेखा करते हैं।
- लर्निंग-आधारित विधियाँ (जैसे, DRL): व्यापक प्रशिक्षण की आवश्यकता होती है, उच्च सैंपल कॉम्प्लेक्सिटी से जूझती हैं, और औपचारिक प्रदर्शन गारंटी या व्याख्यात्मकता (interpretability) का अभाव होता है।

कार्यप्रणाली (Methodology)

यह शोध पत्र एक क्यू-अवेयर ऑफलोडिंग विधि प्रस्तावित करता है जो प्रति-कार्य निर्णय लेने के लिए एक हाइब्रिड डिले एस्टिमेटर का उपयोग करता है। मुख्य नवाचार विश्लेषणात्मक क्यूइंग मॉडल और वास्तविक समय के क्यू अवलोकनों का एक अनुकूली मिश्रण (adaptive blending) है।

1. सिस्टम मॉडल

टियर्स (Tiers): सिस्टम में लोकल ( $L$ ), एज ( $E$ ), और क्लाउड ( $C$ ) टियर्स शामिल हैं।
आगमन (Arrivals): इन्हें समय-परिवर्ती दरों के साथ एक पॉइसन प्रक्रिया (Poisson process) के रूप में मॉडल किया गया है। विषम ट्रैफ़िक वितरण से पूर्वाग्रह से बचने के लिए प्रति-टियर आगमन दर ( $\lambda_i$ ) का ऑनलाइन स्लाइडिंग विंडो का उपयोग करके अनुमान लगाया जाता है।
सेवा समय (Service Times): भारी-पूंछ वाली परिवर्तनशीलता (heavy-tailed variability) को दर्शाने के लिए पारेटो वितरण (आकार $\alpha > 2$ ) का उपयोग किया गया है।
विलंब घटक (Delay Components): कुल विलंब $T_i$ , प्रतीक्षा समय ( $W_i$ ), सेवा समय ( $1/\mu_i$ ), और संचार विलंब ( $D_i$ ) का योग है।

2. हाइब्रिड डिले एस्टिमेटर

यह विधि दो पूरक स्रोतों को मिलाकर प्रतीक्षा समय ( $W_i$ ) का अनुमान लगाती है:

विश्लेषणात्मक घटक ( $W^{model}_i$ ): G/G/c क्यू के लिए प्रतीक्षा समय को अनुमानित करने के लिए एलन-कुनी (Allen–Cunneen) फॉर्मूला का उपयोग करता है। यह पारेटो सेवा वितरण से प्राप्त स्क्वेयर्ड कोएफिशिएंट ऑफ वेरिएशन ( $C^2_s$ ) का उपयोग करके मानक M/M/c एरलैंग-सी (Erlang-C) फॉर्मूले को सुधारता है। यह भीड़भाड़ का एक स्थिर, भविष्योन्मुखी अनुमान प्रदान करता है।
क्यू-स्टेट घटक ( $W^{queue}_i$ ): सक्रिय सर्वरों ( $n_i$ ) की संख्या के सापेक्ष प्रतीक्षा कर रहे कार्यों ( $q_i$ ) की संख्या पर आधारित एक रिएक्टिव अनुमान। यह तात्कालिक भीड़भाड़ को पकड़ता है लेकिन शोर युक्त (noisy) होता है।

3. अनुकूली मिश्रण तंत्र (Adaptive Blending Mechanism)

एक निश्चित मिश्रण पैरामीटर के बजाय, प्रस्तावित विधि एक लोड-डिपेंडेंट ब्लेंडिंग वेट $\beta_i(t)$ का उपयोग करती है:
$\beta_i(t) = \min\left(1, \frac{q_i(t)}{c_i}\right)$
अंतिम अनुमान है:
$W_i(t) = (1 - \beta_i(t)) \cdot W^{model}_i(t) + \beta_i(t) \cdot W^{queue}_i(t)$

तर्क: जब कोई टियर खाली होता है ( $q_i=0$ ), तो अनुमान पूरी तरह से विश्लेषणात्मक मॉडल पर निर्भर करता है। जैसे-जैसे बैकलॉग क्षमता ( $c_i$ ) के सापेक्ष बढ़ता है, वेट रैखिक रूप से रिएक्टिव क्यू अवलोकन की ओर स्थानांतरित हो जाता है। एक बार जब बैकलॉग क्षमता से अधिक हो जाता है, तो अनुमान पूरी तरह से प्रेक्षित अवस्था पर निर्भर करता है।
उपयोगिता दंड (Utilization Penalty): यदि उपयोगिता $\rho_i(t)$ एक थ्रेशोल्ड (0.9) से अधिक हो जाती है, तो लगभग संतृप्त टियर्स को हतोत्साहित करने के लिए एक गुणात्मक दंड (multiplicative penalty) लागू किया जाता है।

4. निर्णय नियम (Decision Rule)

कार्यों को उस टियर को सौंपा जाता है जो अनुमानित कुल विलंब को कम करता है:
$i^*(t) = \arg \min_{i \in T} \left[ \hat{W}_i(t) + \frac{1}{\mu_i} + D_i(t) \right]$
अल्प-चयनित टियर्स के लिए दर अनुमानकों के ढहने (collapse) को रोकने के लिए एक $\epsilon$ -greedy एक्सप्लोरेशन स्टेप ( $\epsilon=0.05$ ) शामिल किया गया है।

मुख्य योगदान

क्यू-अवेयर डिले एस्टेमेशन: एक ऐसा फॉर्मूलेशन जो हेवी-टेल्ड सर्विस टाइम्स के लिए G/G/c एप्रोक्सिमेशन (एलन-कुनी के माध्यम से) को विश्लेषणात्मक रूप से सुधारता है और उन्हें वास्तविक समय के क्यू अवलोकनों के साथ मिश्रित करता है।
प्रति-टियर आगमन दर अनुमान: एक स्लाइडिंग-विंडो एस्टिमेटर जो प्रत्येक टियर के लिए आगमन दरों को अलग-अलग ट्रैक करता है, जिससे एकल वैश्विक दर प्रॉक्सी का पूर्वाग्रह बचता है।
अनुकूली प्रेडिक्टिव-रिएक्टिव हाइब्रिड रूटिंग: एक ब्लेंडिंग तंत्र जहाँ वेट वर्तमान क्यू बैकलॉग का एक नियतात्मक फलन (deterministic function) है, जिसके लिए किसी निश्चित मिक्सिंग हाइपरपैरामीटर या ऑफलाइन ट्यूनिंग की आवश्यकता नहीं है।
दोहरा सत्यापन: एक डिस्क्रीट-इवेंट सिम्युलेटर और एक HTTP-आधारित इम्यूलेशन टेस्टबेड दोनों का उपयोग करके मूल्यांकन, जिसमें वास्तविक एसिंक्रोनस रिक्वेस्ट डिस्पैच, क्यू कंटेंशन और वॉल-क्लॉक मेजरमेंट शामिल हैं।
अनुमान सटीकता का विश्लेषण: प्रदर्शन कि हाइब्रिड एस्टिमेटर सभी लोड स्तरों पर मॉडल-ओनली या क्यू-ओनली घटकों की तुलना में कम प्रेडिक्शन एरर (MAPE) प्राप्त करता है।

प्रयोगात्मक परिणाम

विधि का मूल्यांकन बढ़ते भार, उछाल वाले आगमन (bursty arrivals) और बदलते एज क्षमताओं के तहत, स्टैटिक बेसलाइन्स (Edge-First, Random), डायनेमिक बेसलाइन्स (JSQ, JSQ-S) और एक ऑरेकल पॉलिसी के विरुद्ध किया गया।

विलंबता में कमी (Latency Reduction): प्रस्तावित विधि सभी लोड स्तरों पर स्टैटिक (Edge-First) और विश्लेषणात्मक रूप से सरल (Model-Only) बेसलाइन्स की तुलना में औसत विलंबता को काफी कम करती है।
टेल लेटेंसी और फेयरनेस: जबकि औसत विलंबता के लिए ग्रीडी क्यू-लेंथ ह्यूरिस्टिक्स (JSQ) अच्छा प्रदर्शन करते हैं, प्रस्तावित विधि बड़े, हेवी-टेल्ड कार्यों के लिए बेहतर टेल लेटेंसी (P95) प्रदर्शित करती है। यह शुद्ध JSQ रूटिंग में देखे जाने वाले बड़े कार्यों के व्यवस्थित स्टार्वेशन (starvation) को रोकता है।
प्रेडिक्शन एरर: हाइब्रिड एस्टिमेटर सभी लोड के तहत सबसे कम मीन एब्सोल्यूट रिलेटिव एरर (MAPE) बनाए रखता है, जिससे मॉडल-ओनली एस्टिमेटर्स की हाई-लोड गिरावट और क्यू-ओनली एस्टिमेटर्स की लो-लोड अस्थिरता से बचा जा सका।
अनुकूलन क्षमता (Adaptability): बर्स्ट परिदृश्यों में, नीति तेजी से अनुकूलित होती है और एज कंजेशन बढ़ने के साथ कार्यों को क्लाउड में पुनर्वितरित करती है, जिससे स्टैटिक नीतियों की तुलना में विलंबता तेजी से स्थिर होती है।
ओवरहेड: निर्णय लेने के लिए कम्प्यूटेशनल ओवरहेड लो-माइक्रोसेकंड रेंज में है (औसत ~7.4 µs सिमुलेशन में), जो संसाधन-बाधित एज नोड्स के लिए उपयुक्तता की पुष्टि करता है।
सत्यापन: HTTP-आधारित इम्यूलेशन ने पुष्टि की कि सिम्युलेटर की गतिशीलता वास्तविक रिक्वेस्ट प्रोसेसिंग के तहत भी पुनरुत्पादित होती है, जिसमें विसंगतियां सिस्टमैटिक नेटवर्क-डिली डिले कैलिब्रेशन ऑफसेट्स के कारण थीं, न कि पॉलिसी की विफलता के कारण।

महत्व और दावे

यह शोध पत्र दावा करता है कि प्रस्तावित विधि उस अंतर को संबोधित करती है जो मौजूदा साहित्य में मौजूद है, और व्यावहारिक कॉन्टिनम ऑफलोडिंग के लिए आवश्यक तीन गुणों को एक साथ पूरा करती है:

बिना प्रशिक्षण के ऑनलाइन प्रति-टास्क निर्णय लेना।
G/G/c एप्रोक्सिमेशन के माध्यम से गैर-घातांकीय (non-exponential) सेवा-समय परिवर्तनशीलता का स्पष्ट मॉडलिंग।
प्रति-टियर कंजेशन जागरूकता के साथ लाइटवेट, ट्रेनिंग-फ्री ऑपरेशन।

लेखक इस बात पर जोर देते हैं कि इस विधि के लिए किसी ऑफलाइन कैलिब्रेशन या निश्चित हाइपरपैरामीटर की आवश्यकता नहीं है, क्योंकि ब्लेंडिंग वेट सीधे सिस्टम स्टेट से प्राप्त होता है। परिणाम बताते हैं कि विश्लेषणात्मक स्थिरता को रिएक्टिव अवलोकन के साथ मिलाने से केवल एक ही स्रोत पर निर्भर रहने की तुलना में अधिक मजबूत निर्णय प्राप्त होते हैं, विशेष रूप से उन वातावरणों में जहाँ हेवी-टेल्ड सर्विस टाइम्स और गतिशील वर्कलोड होते हैं।

स्वीकृत सीमाएँ (Limitations Acknowledged):

इम्यूलेशन सिंथेटिक पारेटो सर्विस टाइम्स का उपयोग करता है, न कि प्रोडक्शन ट्रेसेस का।
यह माना गया है कि कार्य स्वतंत्र और स्टेटलेस (stateless) हैं (कोई डेटा लोकैलिटी या डिपेंडेंसी नहीं)।
विधि सेवा दरों और क्यू लंबाई की दृश्यता (observability) मानती है, जिसके लिए वितरित सेटिंग्स में इंस्ट्रुमेंटेशन की आवश्यकता हो सकती है।
ऊर्जा खपत वर्तमान में अनुकूलन उद्देश्य का हिस्सा नहीं है।
JSQ पर लाभ मुख्य रूप से टेल लेटेंसी और फेयरनेस में केंद्रित है, न कि परीक्षण किए गए कॉन्फ़िगरेशन में कुल औसत विलंबता में।