📊 statistics

Experimentation for Different Scheduling Policies on Queues: Mixed Differences-in-Q Estimators Based on Little's Law

यह शोध पत्र डेटा सेंटर शेड्यूलिंग नीतियों के लिए A/B टेस्टिंग में मार्कोवियन इंटरफेरेंस (Markovian interference) को कम करने हेतु लिटल्स लॉ (Little's Law) पर आधारित मिश्रित डिफरेंस-इन-Q (Differences-in-Q) एस्टिमेटर्स का प्रस्ताव करता है, जो व्यापक सिमुलेशन के माध्यम से यह प्रदर्शित करता है कि यह दृष्टिकोण मानक विधियों की तुलना में पूर्वाग्रह (bias) और विचरण (variance) को महत्वपूर्ण रूप से कम करता है।

मूल लेखक: Nanshan Jia, Ramesh Johari, Nian Si, Zeyu Zheng

प्रकाशित 2026-05-29

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

CC BY 4.0

मूल लेखक: Nanshan Jia, Ramesh Johari, Nian Si, Zeyu Zheng

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

कल्पना कीजिए कि एक विशाल, हाई-टेक सुपरमार्केट है जिसमें हजारों चेकआउट लेन (सर्वर) हैं और हर सेकंड ग्राहकों (टास्क) की भारी भीड़ उमड़ रही है। स्टोर मैनेजर का लक्ष्य लाइनों को यथासंभव तेज़ चलाना है। इसे करने के लिए, वे एक "शेड्यूलिंग पॉलिसी" (scheduling policy) का उपयोग करते हैं—यानी यह तय करने के लिए नियमों का एक सेट कि किस ग्राहक को किस लेन में भेजा जाए।

कभी-कभी, मैनेजर एक नया नियम आज़माना चाहता है (जैसे "ग्राहकों को उस लेन में भेजें जहाँ सबसे कम लोग हों") यह देखने के लिए कि क्या यह पुराने नियम से बेहतर है। इसका परीक्षण करने के लिए, वे यादृच्छिक रूप से (randomly) कुछ ग्राहकों को "नए नियम" वाली लेन में और अन्य को "पुराने नियम" वाली लेन में भेजते हैं, और फिर औसत प्रतीक्षा समय (average wait times) की तुलना करते हैं।

समस्या: "रिपल इफेक्ट" (The Ripple Effect)

यह पेपर बताता है कि व्यस्त प्रणालियों में साधारण A/B टेस्ट अक्सर "मार्कोवियन इंटरफेरेंस" (Markovian interference) नामक चीज़ के कारण विफल हो जाते हैं।

इसे इस तरह सोचें: यदि आप किसी विशिष्ट लेन में एक ग्राहक को भेजते हैं, तो आप उस लेन की लंबाई को बदल देते हैं। यह परिवर्तन केवल उस एक ग्राहक को प्रभावित नहीं करता; यह पूरे स्टोर की स्थिति को अगले ग्राहक और उसके बाद आने वाले व्यक्ति के लिए बदल देता है।

यदि "नया नियम" किसी लाइन को छोटा करता है, तो अगला ग्राहक तेज़ी से सेवा पा सकता है, इसलिए नहीं कि नियम स्वाभाविक रूप से बेहतर था, बल्कि इसलिए क्योंकि लाइन अस्थायी रूप से खाली हो गई थी।
इसके विपरीत, यदि "पुराना नियम" किसी लेन को जाम कर देता है, तो यह उसके बाद आने वाले सभी लोगों के समय को बिगाड़ देता है।

क्योंकि दोनों समूह (नया नियम बनाम पुराना नियम) लगातार एक-दूसरे के वातावरण को प्रभावित कर रहे हैं, इसलिए प्रतीक्षा समय की एक साधारण तुलना एक पक्षपाती (biased) परिणाम देती है। यह दो धावकों की गति को मापने की कोशिश करने जैसा है जबकि वे एक-दूसरे के पैरों से टकरा रहे हों।

पुराना समाधान: "लॉन्ग मेमोरी" (Long Memory) दृष्टिकोण

पिछले शोधकर्ताओं (Farias et al.) ने इसे डिफरेंसेस-इन-क्यू (DQ) नामक विधि से ठीक करने का प्रयास किया।
कल्पना करें कि आप एक धावक को आंकने की कोशिश कर रहे हैं, लेकिन केवल उसके वर्तमान लैप (lap) का समय लेने के बजाय, आप देखते हैं कि उसका प्रदर्शन अगले 100 लैप को कैसे प्रभावित करता है। आप एक एकल निर्णय के कारण होने वाले सभी भविष्य के "पुरस्कारों" (rewards) या "दंडों" (penalties) को जोड़ते हैं।

अच्छी खबर: यह विधि पक्षपात (bias) को हटाने में बहुत अच्छी है। यह "रिपल इफेक्ट" को ध्यान में रखती है।
बुरी खबर: यह अविश्वसनीय रूप से शोर भरी (noisy/high variance) है। क्योंकि आप कई भविष्य की घटनाओं को जोड़ रहे हैं, एक एकल यादृच्छिक उतार-चढ़ाव आपके पूरे कैलकुलेशन को बिगाड़ सकता है। यह हर एक बादल को देखकर अगले एक साल के मौसम की भविष्यवाणी करने की कोशिश करने जैसा है; आपको बहुत सारा डेटा मिलता है, लेकिन सिग्नल शोर में दब जाता है।

नया समाधान: "लिटल्स लॉ" (Little's Law) के साथ मिश्रण

इस पेपर के लेखक इन दोनों दुनियाओं के सर्वश्रेष्ठ गुणों को मिलाने का एक चतुर तरीका प्रस्तावित करते हैं। वे क्यूइंग थ्योरी (queueing theory) के एक प्रसिद्ध सिद्धांत का उपयोग करते हैं जिसे लिटल्स लॉ (Little's Law) कहा जाता है।

उपमा (Analogy):
लिटल्स लॉ एक तराजू की तरह है। यह कहता है कि एक स्थिर प्रणाली में, तीन चीजें आपस में जुड़ी होती हैं:

स्टोर में कितने लोग हैं (कतार की लंबाई/Queue Length)।
लोग कितनी तेज़ी से आ रहे हैं (आगमन दर/Arrival Rate)।
वे कितनी देर तक रुकते हैं (प्रतिक्रिया समय/Response Time)।

यदि आप दो चीज़ें जानते हैं, तो आप तीसरी का पता लगा सकते हैं। लेखकों ने महसूस किया कि "कतार की लंबाई" और "प्रतिक्रिया समय" एक ही सिक्के के दो पहलू हैं। वे अत्यधिक सह-संबंधित (highly correlated) हैं।

नवाचार: "मिक्स्ड" एस्टिमेटर (The Mixed Estimator)
केवल "लॉन्ग मेमोरी" के रिस्पॉन्स टाइम (जो शोर भरा है) या केवल "लॉन्ग मेमोरी" के कतार की लंबाई (जो शोर भरा है) को देखने के बजाय, वे उन्हें एक साथ मिक्स (mix) करते हैं।

इसे एक शेफ द्वारा सूप चखने के रूप में सोचें।

केवल नमक (Response Time) चखना बहुत नम या बहुत फीका हो सकता है क्योंकि इसमें एक रैंडम दाना हो सकता है।
केवल काली मिर्च (Queue Length) चखना बहुत तीखा हो सकता है।
लेकिन यदि आप दोनों को चखते हैं और उन्हें सही अनुपात में मिलाते हैं, तो यादृच्छिक त्रुटियां (random errors) एक-दूसरे को रद्द कर देती हैं, और आपको एक सटीक स्वाद मिलता है।

लेखक इन दो मापों को मिलाने के लिए एक "परफेक्ट रेश्यो" (एक भार जिसे $\alpha$ कहा जाता है) की गणना करते हैं। यह एक मिक्स्ड डिफरेंसेस-इन-क्यू एस्टिमेटर (Mixed Differences-in-Q Estimator) बनाता है।

परिणाम

पेपर ने इस विचार का परीक्षण करने के लिए अराजक स्थितियों के तहत हजारों कंप्यूटर सिमुलेशन चलाए:

व्यस्त समय: जब स्टोर भरा हुआ होता है (उच्च आगमन दर)।
धीमे कर्मचारी: जब कुछ सर्वर दूसरों की तुलना में धीमे होते हैं (heterogeneous rates)।
अव्यवस्थित देरी: जब सूचना को मैनेजर और सर्वर के बीच यात्रा करने में समय लगता है (communication delays)।
अनिश्चित ग्राहक: जब सेवा का समय स्मूथ और अनुमानित नहीं होता (non-exponential times)।

फैसला:
हर परिदृश्य में, उनका नया मिक्स्ड एस्टिमेटर (Mixed Estimator) विजेता रहा।

कम पक्षपात (Low Bias): इसने नई पॉलिसी के वास्तविक मूल्य को सही ढंग से पहचाना, उन "रिपल इफेक्ट्स" को अनदेखा किया जिन्होंने साधारण टेस्ट को धोखा दिया था।
कम विचरण (Low Variance): यह पिछले "लॉन्ग मेमोरी" तरीकों की तुलना में बहुत अधिक स्थिर और विश्वसनीय था। यह एक टेस्ट से दूसरे टेस्ट में बेतहाशा नहीं बदला।

सारांश

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

तकनीकी सारांश: विभिन्न कतार नीतियों (Scheduling Policies) पर प्रयोग

समस्या विवरण

आधुनिक डेटा केंद्रों में, वर्कलोड को सर्वर नेटवर्कों में वितरित करने और रिस्पॉन्स टाइम एवं कंप्यूटेशनल लागत के बीच संतुलन बनाने के लिए शेड्यूलिंग एल्गोरिदम अत्यंत महत्वपूर्ण हैं। एक नई शेड्यूलिंग नीति को तैनात करते समय, विशेषज्ञ इसके वास्तविक प्रभाव का मूल्यांकन करने के लिए आमतौर पर A/B टेस्टिंग पर भरोसा करते हैं। हालाँकि, कतार प्रणालियों (queueing systems) में मानक A/B परीक्षण मार्कोवियन इंटरफेरेंस (जिसे इंटरटेम्पोरल इंटरफेरेंस भी कहा जाता है) के प्रति संवेदनशील होते हैं।

एक मानक रैंडमाइज्ड A/B टेस्ट में, जहाँ कार्यों को ट्रीटमेंट और कंट्रोल समूहों में सौंपा जाता है, सिस्टम की स्थिति (जैसे कतार की लंबाई) गतिशील रूप से विकसित होती है। एक समूह पर लागू की गई शेड्यूलिंग नीति सर्वर लोड को प्रभावित करती है, जो बाद में दूसरे समूह के कार्यों के रिस्पॉन्स टाइम और कतार की स्थिति को प्रभावित करती है। यह इंटरफेरेंस "नाइफ" (naive) एस्टिमेटर्स को—जो केवल समूहों के बीच औसत परिणामों की तुलना करते हैं—एक व्यवस्थित पूर्वाग्रह (systematic bias) उत्पन्न करता है। विशेष रूप से, नाइफ एस्टिमेटर ट्रीटमेंट प्रभाव को कम करके आंकता है क्योंकि कंट्रोल ग्रुप में एक अधिक कुशल नीति की उपस्थिति ट्रीटमेंट ग्रुप के लिए कतारों को कृत्रिम रूप से छोटा कर देती है, और इसके विपरीत भी।

जबकि Farias et al. [2022] द्वारा प्रस्तुत डिफरेंसेस-इन-Q (DQ) एस्टिमेटर्स का उपयोग भविष्य के रिवार्ड्स को Q-वैल्यूज़ का अनुमान लगाने के लिए किया गया है, ये एस्टिमेटर्स अक्सर लंबे होराइजन्स (horizons) पर शोर के संचय के कारण उच्च विचरण (high variance) से ग्रस्त होते हैं।

कार्यप्रणाली

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

लेखक डेटा सेंटर को $N$ सर्वरों वाले एक समानांतर-सर्वर कतार नेटवर्क (जिसे "सुपरमार्केट मॉडल" कहा जाता है) के रूप में मॉडल करते हैं। कार्य एक पॉइसन स्ट्रीम (Poisson stream) के रूप में आते हैं और लोड-बैलेंसिंग नीतियों (जैसे Power-of- $d$ ) के आधार पर सर्वरों में रूट किए जाते हैं। सिस्टम की स्थिति को कतार की लंबाई के वेक्टर द्वारा परिभाषित किया जाता है। लेखक दो प्राथमिक प्रदर्शन मेट्रिक्स परिभाषित करते हैं:

रिस्पॉन्स टाइम ( $C_w$ ): वह समय जो एक कार्य सिस्टम में बिताता है (प्रतीक्षा + सेवा)।
कतार की लंबाई ( $C_q$ ): सिस्टम में कार्यों की औसत संख्या।

उद्देश्य ग्लोबल ट्रीटमेंट इफेक्ट (GTE) का अनुमान लगाना है, जिसे एक ट्रीटमेंट पॉलिसी (जैसे Power-of- $d_2$ ) और एक कंट्रोल पॉलिसी (जैसे Power-of- $d_1$ ) के बीच दीर्घकालिक औसत प्रदर्शन के अंतर के रूप में परिभाषित किया गया है।

2. सैद्धांतिक आधार: लिटल्स लॉ (Little's Law)

एक मुख्य सैद्धांतिक योगदान एस्टिमेशन फ्रेमवर्क में लिटल्स लॉ का अनुप्रयोग है। लिटल्स लॉ बताता है कि एक स्थिर प्रणाली में, दीर्घकालिक औसत कतार की लंबाई, आगमन दर (arrival rate) और औसत रिस्पॉन्स टाइम के गुणनफल के बराबर होती है।
लेखक सिद्ध करते हैं कि रिस्पॉन्स टाइम के माध्यम से परिभाषित GTE ( $GTE_w$ ), आगमन दर $\lambda$ द्वारा स्केल किए गए कतार लंबाई के माध्यम से परिभाषित GTE ( $GTE_q$ ) के समान है:
$GTE_w = GTE_q = \frac{C_{1,q}(\lambda) - C_{0,q}(\lambda)}{\lambda}$
यह समानता लेखकों को आगमन दर का हिसाब रखते हुए, कतार की लंबाई और रिस्पॉन्स टाइम को ट्रीटमेंट इफेक्ट के विनिमेय प्रॉक्सी (interchangeable proxies) के रूप में उपयोग करने की अनुमति देती है।

3. मिक्स्ड डिफरेंसेस-इन-Q एस्टिमेटर

मानक DQ एस्टिमेटर्स के उच्च विचरण को संबोधित करने के लिए, लेखक एक मिक्स्ड डिफरेंसेस-इन-Q एस्टिमेटर का प्रस्ताव करते हैं।

मानक DQ: एक ट्रंकेटेड होराइज $L$ के लिए सभी भविष्य के कार्यों के लिए लागत (रिस्पॉन्स टाइम या कतार की लंबाई) के अंतर को जोड़कर GTE का अनुमान लगाता है।
मिक्स्ड दृष्टिकोण: यह पहचानते हुए कि कतार-लंबाई आधारित Q-फंक्शंस और रिस्पॉन्स-टाइम आधारित Q-फंक्शंस अत्यधिक सह-संबंधित (strongly correlated) होते हैं, लेखक एक कंट्रोल वेरिएट तकनीक का उपयोग करते हैं। वे एक मिक्स्ड Q-फंक्शन का निर्माण करते हैं:
$\hat{Q}^{\alpha, L}_{mix} = \alpha \hat{Q}^L_w + (1-\alpha) \frac{\hat{Q}^L_q}{\lambda}$
जहाँ $\alpha$ एक अनुकूलित भार (optimal weight) है जिसे मिक्स्ड एस्टिमेटर के विचरण को कम करने के लिए चुना जाता है। अनुकूलित $\alpha^*$ को व्यक्तिगत एस्टिमेटर्स के विचरण और सह-प्रसरण (covariance) के आधार पर विश्लेषणात्मक रूप से प्राप्त किया जाता है।

यह विधि DQ दृष्टिकोण के बायस-रिडक्शन गुणों से समझौता किए बिना, विचरण को कम करने के लिए कतार प्रणालियों के संरचनात्मक गुणों (विशेष रूप से लिटल्स लॉ) का लाभ उठाती है।

मुख्य योगदान

डेटा सेंटरों के लिए A/B टेस्टिंग फ्रेमवर्क: यह पेपर सुपरमार्केट मॉडल के भीतर एक कठोर A/B टेस्टिंग फ्रेमवर्क स्थापित करता है, जो रैंडमाइज्ड प्रयोगों के तहत वैकल्पिक शेड्यूलिंग रणनीतियों के प्रदर्शन प्रभाव को स्पष्ट रूप से कैप्चर करता है।
मिक्स्ड डिफरेंसेस-इन-Q एस्टिमेटर: लेखक एक नया एस्टिमेटर प्रस्तावित करते हैं जो Farias et al. [2022] के DQ एस्टिमेटर का सामान्यीकरण करता है। लिटल्स लॉ के माध्यम से कतार-लंबाई और रिस्पॉन्स-टाइम Q-फंक्शंस को जोड़कर, यह विधि कम बायस बनाए रखते हुए काफी कम विचरण प्राप्त करती है।
व्यापक सिमुलेशन सत्यापन: अध्ययन विविध और चुनौतीपूर्ण परिदृश्यों में प्रस्तावित पद्धति को मान्य करता है, जिसमें शामिल हैं:
- हेटेरोजेनियस (विषम) सर्विस रेट्स।
- गैर-स्थिर (non-stationary) आगमन दरें (चक्रीय पैटर्न)।
- डिस्पैचर और सर्वरों के बीच संचार विलंब (communication delays)।
- गैर-एक्सपोनेंशियल सर्विस टाइम (स्थिर और हेवी-टेल्ड पारेटो वितरण दोनों)।
- स्विचबैक प्रायोगिक डिजाइनों के साथ तुलना।

परिणाम

संख्यात्मक प्रयोग (विभिन्न आगमन दरों के साथ $N=20$ सर्वरों के साथ आयोजित) दर्शाते हैं कि:

बायस रिडक्शन (पूर्वाग्रह में कमी): इंटरफेरेंस के कारण नाइफ एस्टिमेटर महत्वपूर्ण पूर्वाग्रह प्रदर्शित करता है (ट्रीटमेंट प्रभाव को कम करके आंकना)। मानक DQ एस्टिमेटर्स (कतार-लंबाई और रिस्पॉन्स-टाइम आधारित) और मिक्स्ड DQ एस्टिमेटर दोनों ही इस पूर्वाग्रह को सफलतापूर्वक कम करते हैं।
विचरण में कमी (Variance Reduction): जबकि मानक DQ एस्टिमेटर्स पूर्वाग्रह को कम करते हैं, वे अक्सर नाइफ एस्टिमेटर की तुलना में 50–500 गुना अधिक मानक विचलन प्रदर्शित करते हैं। मिक्स्ड DQ एस्टिमेटर इस समस्या को काफी हद तक कम करता है। होमोजेनियस सेटिंग्स में, यह मानक DQ एस्टिमेटर्स की तुलना में मानक विचलन को 2 से 5 गुना तक कम कर देता है।
मीन स्क्वेर्ड एरर (MSE): परीक्षण किए गए सभी परिदृश्यों (होमोजेनियस, हेटेरोजेनियस, नॉन-स्टेशनरी, डिलेड, और नॉन-एक्सपोनेंशियल सर्विस टाइम) में, मिक्स्ड DQ एस्टिमेटर लगातार तुलना किए गए सभी एस्टिमेटर्स (Naive, Group, qDQ, wDQ, और Switchback) में सबसे कम MSE प्राप्त करता है।
मजबूती (Robustness): विधि हेवी-टेल्ड सर्विस टाइम और संचार विलंब के तहत भी प्रभावी बनी रहती है। नॉन-स्टेशनरी सेटिंग्स में, मिक्स्ड DQ एस्टिमेटर स्विचबैक डिजाइनों से बेहतर प्रदर्शन करता है, भले ही आगमन दर आवधिक (periodic) हो (एक सेटिंग जो स्विचबैक के लिए सैद्धांतिक रूप से अनुकूल है)।
ट्रंकेशन सेंसिटिविटी: ट्रंकेशन लेंथ $L$ पर एक एब्लेशन स्टडी (ablation study) एक बायस-विचरण ट्रेड-ऑफ प्रकट करती है। लेखक पाते हैं कि $L = 30N\lambda$ एक मजबूत संतुलन प्रदान करता है, और मिक्स्ड DQ एस्टिमेटर छोटे $L$ के साथ भी अपने समकक्षों की तुलना में तेजी से अभिसरित (converge) होता है।

महत्व और दावे

यह पेपर दावा करता है कि इस कार्य का प्राथमिक महत्व यह प्रदर्शित करना है कि डोमेन ज्ञान को शामिल करना—विशेष रूप से लिटल्स लॉ जैसे कतार प्रणालियों के संरचनात्मक गुणों को—A/B टेस्टिंग में प्रदर्शन मूल्यांकन की विश्वसनीयता में पर्याप्त सुधार कर सकता है।

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

पेपर विनम्रतापूर्वक समाप्त होता है, यह नोट करते हुए कि हालांकि कार्यप्रणाली को सुपरमार्केट मॉडल पर प्रदर्शित किया गया है, यह सामान्य कतार नेटवर्क सेटिंग्स के लिए व्यापक रूप से लागू है। भविष्य के कार्य के रूप में एस्टिमेटर के लिए कठोर इन्फरेंस प्रक्रियाओं को विकसित करना और जटिल परिदृश्यों जैसे कि लार्ज लैंग्वेज मॉडल (LLM) इन्फरेंस तक फ्रेमवर्क का विस्तार करना पहचाना गया है।

समस्या: "रिपल इफेक्ट" (The Ripple Effect)

पुराना समाधान: "लॉन्ग मेमोरी" (Long Memory) दृष्टिकोण

नया समाधान: "लिटल्स लॉ" (Little's Law) के साथ मिश्रण

परिणाम

सारांश

तकनीकी सारांश: विभिन्न कतार नीतियों (Scheduling Policies) पर प्रयोग

समस्या विवरण

कार्यप्रणाली

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

2. सैद्धांतिक आधार: लिटल्स लॉ (Little's Law)

3. मिक्स्ड डिफरेंसेस-इन-Q एस्टिमेटर

मुख्य योगदान

परिणाम

महत्व और दावे

इसी तरह के और पेपर