निष्पक्ष पंक्तियन
फेयर क्यूइंग (निष्पक्ष पंक्तियन) कुछ शेड्यूलिंग (कंप्यूटिंग) और नेटवर्क अनुसूचक में उपयोग किए जाने वाले शेड्यूलिंग एल्गोरिदम का समूह है। एल्गोरिदम को सीमित संसाधन साझा किए जाने पर निष्पक्षता प्राप्त करने के लिए डिज़ाइन किया गया है, उदाहरण के लिए बड़े पैकेट या प्रक्रियाओं के साथ प्रवाह को रोकने के लिए जो अन्य प्रवाह या प्रक्रियाओं की तुलना में अधिक थ्रूपुट या सीपीयू समय का उपभोग करके छोटे कार्य उत्पन्न करते हैं।
कुछ उन्नत नेटवर्क स्विच और राउटर (कंप्यूटिंग) में फेयर क्यूइंग प्रयुक्त किया गया है।
इतिहास
फेयर क्यूइंग शब्द जॉन नागले द्वारा 1985 में गढ़ा गया था, जब दुर्व्यवहार करने वाले होस्ट से नेटवर्क व्यवधान को कम करने के लिए स्थानीय क्षेत्र नेटवर्क और इंटरनेट के मध्य गेटवे में राउंड-रॉबिन शेड्यूलिंग का प्रस्ताव दिया गया था।[1][2][3]
इस प्रकार 1989 में एलन डेमर्स, श्रीनिवासन केशव और स्कॉट शेन्कर द्वारा बाइट-वेटेड संस्करण प्रस्तावित किया गया था, और यह पहले के नागल फेयर क्यूइंग एल्गोरिदम पर आधारित था।[4][5] बाइट-वेटेड फेयर क्यूइंग एल्गोरिदम का लक्ष्य प्रत्येक पैकेट के लिए सैद्धांतिक प्रस्थान तिथि की गणना करके बिट-पर-बिट मल्टीप्लेक्सिंग की नकल करना है।
इस अवधारणा को आगे चलकर वेटेड फेयर क्यूइंग और यातायात को आकार देने की अधिक सामान्य अवधारणा में विकसित किया गया है, जहां सेवा लक्ष्यों की वांछित प्रवाह गुणवत्ता प्राप्त करने या कुछ प्रवाह में तेजी लाने के लिए पंक्तिबद्ध प्राथमिकताओं को गतिशील रूप से नियंत्रित किया जाता है।
सिद्धांत
फेयर क्यूइंग प्रति प्रवाह एक पंक्ति (कंप्यूटर नेटवर्किंग) का उपयोग करती है और उन्हें रोटेशन में सेवाएं देती है, जिससे प्रत्येक प्रवाह संसाधनों का समान अंश प्राप्त कर सकता है।[1][2]
पारंपरिक फर्स्ट इन फर्स्ट आउट (एफआईएफओ) या प्राथमिकता पंक्ति पर लाभ यह है कि उच्च-डेटा-दर प्रवाह, जिसमें बड़े पैकेट या विभिन्न डेटा पैकेट सम्मिलित हैं, लिंक क्षमता के अपने उचित भागो से अधिक नहीं ले सकता है।
फेयर क्यूइंग का उपयोग राउटर, स्विच और सांख्यिकीय मल्टीप्लेक्सर्स में किया जाता है जो बफर (कंप्यूटर विज्ञान) से पैकेट अग्रेषित करते हैं। बफ़र एक पंक्ति प्रणाली के रूप में काम करता है, जहां डेटा पैकेट अस्थायी रूप से प्रसारित होने तक संग्रहीत होते हैं।
आर की लिंक डेटा-दर के साथ, किसी भी समय एन सक्रिय डेटा प्रवाह (गैर-रिक्त पंक्ति वाले) को आर/एन की औसत डेटा दर के साथ सेवित किया जाता है। थोड़े समय के अंतराल में डेटा दर इस मूल्य के आसपास उतार-चढ़ाव कर सकती है क्योंकि पैकेट क्रमिक रूप से बदले में वितरित किए जाते हैं।
निष्पक्षता
नेटवर्क शेड्यूलिंग के संदर्भ में, निष्पक्षता की विभिन्न परिभाषाएँ हैं। नागेल का लेख पैकेटों के राउंड-रॉबिन शेड्यूलिंग का उपयोग करता है,[2] जो पैकेटों की संख्या के संदर्भ में उचित है, किंतु जब पैकेटों का आकार भिन्न-भिन्न होता है तो बैंडविड्थ के उपयोग पर नहीं होता है। निष्पक्षता माप की विभिन्न औपचारिक धारणाएँ परिभाषित की गई हैं जिनमें अधिकतम-न्यूनतम निष्पक्षता, सबसे खराब स्थिति वाली निष्पक्षता,[6] और निष्पक्षता सूचकांक सम्मिलित हैं।[7]
वेटेड शेयरिंग का सामान्यीकरण
प्रारंभिक विचार प्रत्येक प्रवाह को समान दर देता है। प्राकृतिक विस्तार में उपयोगकर्ता को प्रत्येक प्रवाह के लिए आवंटित बैंडविड्थ के भागो को निर्दिष्ट करने की अनुमति दी जाती है, जिससे वेटेड फेयर क्यूइंग और जेनेरालिज़ेड प्रोसेसर शेयरिंग होता है।
एक बाइट-वेटेड फेयर क्यूइंग एल्गोरिथ्म
यह एल्गोरिदम प्रतिस्पर्धी प्रवाह के मध्य लिंक संसाधनों के बिटवाइज़ राउंड-रॉबिन साझाकरण की निष्पक्षता का अनुकरण करने का प्रयास करता है। चूँकि, पैकेट-आधारित प्रवाह को पैकेट के अनुसार और क्रम में प्रसारित किया जाना चाहिए। बाइट-वेटेड फेयर क्यूइंग एल्गोरिदम प्रत्येक पैकेट के लिए समाप्ति समय को मॉडलिंग करके पैकेट के लिए ट्रांसमिशन ऑर्डर का चयन करता है जैसे कि उन्हें बिटवाइज़ राउंड रॉबिन प्रसारित किया जा सकता है। इस मॉडलिंग के अनुसार जल्द से जल्द समाप्ति समय वाला पैकेट ट्रांसमिशन के लिए अगला चुना जाता है।
एल्गोरिदम की सम्मिश्रता O(log(n)) है, जहां n पंक्ति/प्रवाहों की संख्या है।
एल्गोरिदम विवरण
वास्तविक समापन समय का मॉडलिंग, व्यवहार्य होते हुए भी, कम्प्यूटेशनल रूप से गहन है। जब पैकेट को ट्रांसमिशन के लिए चुना जाता है और प्रत्येक बार नया पैकेट किसी पंक्ति में आता है, तो मॉडल को अधिक सीमा तक पुन: गणना करने की आवश्यकता होती है।
कम्प्यूटेशनल भार को कम करने के लिए, आभासी समय की अवधारणा प्रस्तुत की गई है। प्रत्येक पैकेट के लिए समाप्ति समय की गणना इस वैकल्पिक नीरस रूप से बढ़ते वर्चुअल टाइमस्केल पर की जाती है। जबकि आभासी समय उस समय पैकेट के प्रसारण को पूरा करने का स्पष्ट मॉडल नहीं बनाता है, यह उस क्रम को स्पष्ट रूप से मॉडल करता है जिसमें पूर्ण-विशेषताओं वाले मॉडल के उद्देश्यों को पूरा करने के लिए प्रसारण होना चाहिए। वर्चुअल समय का उपयोग करते हुए, पहले से पंक्तिबद्ध पैकेटों के लिए समाप्ति समय की पुन: गणना करना अनावश्यक है। चूँकि आधुनिक पैकेटों के लिए समाप्ति समय, निरपेक्ष रूप से, संभावित रूप से नए आगमन से प्रभावित होता है, वर्चुअल टाइम लाइन पर समाप्ति समय अपरिवर्तित होता है - वर्चुअल टाइम लाइन किसी भी नए ट्रांसमिशन को समायोजित करने के लिए वास्तविक समय के संबंध में विकृत होती है।
नए पंक्तिबद्ध पैकेट के लिए वर्चुअल समाप्ति समय वर्चुअल प्रारंभ समय और पैकेट के आकार के योग द्वारा दिया जाता है। वर्चुअल प्रारंभ समय उसी पंक्ति के पिछले वर्चुअल समाप्ति समय और वर्तमान तत्काल के मध्य अधिकतम है।
सभी उम्मीदवार पैकेटों (अर्थात, सभी गैर-खाली प्रवाह पंक्ति के शीर्ष पर स्थित पैकेट) के आभासी समापन समय की गणना के साथ, निष्पक्ष पंक्ति आभासी समापन समय की तुलना करती है और न्यूनतम का चयन करती है। न्यूनतम वर्चुअल फिनिशिंग समय वाला पैकेट प्रसारित होता है।
स्यूडोकोड
Shared variables const N // Nb of queues queues[1..N] // queues lastVirFinish[1..N] // last virtual finish instant | |
receive(packet) queueNumm:= chooseQueue(packet) queues[queueNum].enqueue(packet) updateTime(packet, queueNum) |
updateTime(packet, queueNum) // virStart is the virtual start of service virStartr:= max(now(), lastVirFinish[queueNum]) packet.virFinishi:= packet.size + virStart lastVirFinish[queueNum]N:= packet.virFinish |
send() queueNumm:= selectQueue() packete:= queues[queueNum].dequeue() return packet |
selectQueue()
itt:= 1
minVirFinish =
while it ≤ N do
queuee:= queues[it]
if not queue.empty and queue.head.virFinish < minVirFinish then
minVirFinish = queue.head.virFinish
queueNumu:= it
it := it + 1
return queueNum
|
फ़ंक्शन रिसीव() को प्रत्येक बार पैकेट प्राप्त होने पर निष्पादित किया जाता है, और सेंड() को प्रत्येक बार तब निष्पादित किया जाता है जब भेजने के लिए पैकेट का चयन किया जाना चाहिए, अर्थात जब लिंक निष्क्रिय हो और पंक्तिें खाली न हों। यह छद्म कोड मानता है कि फ़ंक्शन now() है जो वर्तमान वर्चुअल समय लौटाता है, और फ़ंक्शन choiceQueue() है जो उस पंक्ति का चयन करता है जहां पैकेट संलग्न है।
फ़ंक्शन चयन क्यू () न्यूनतम वर्चुअल समाप्ति समय के साथ पंक्ति का चयन करता है। पठनीयता के लिए, यहां प्रस्तुत छद्म कोड रैखिक खोज करता है। किंतु क्रमबद्ध सूची को बनाए रखने को लॉगरिदमिक समय में प्रयुक्त किया जा सकता है, जिससे O(log(n)) सम्मिश्रता उत्पन्न होती है, किंतु अधिक सम्मिश्र कोड के साथ होती है।
यह भी देखें
- एक्टिव क्यू मैनेजमेंट
- बफ़रब्लोट
- डेफिसिट राउंड रोबिन की कमी
- निष्पक्षता माप
- जेनेरालिज़ेड प्रोसेसर शेयरिंग
- अधिकतम-न्यूनतम निष्पक्षता
- नेटवर्क शेड्यूलर
- सांख्यिकीय बहुसंकेतन
- वेटेड फेयर क्यूइंग
- वेटेड राउंड रोबिन
संदर्भ
- ↑ 1.0 1.1 John Nagle: "On packet switches with infinite storage," RFC 970, IETF, December 1985.
- ↑ 2.0 2.1 2.2 Nagle, J. B. (1987). "अनंत भंडारण के साथ ऑन पैकेट स्विच". IEEE Transactions on Communications. 35 (4): 435–438. CiteSeerX 10.1.1.649.5380. doi:10.1109/TCOM.1987.1096782.
- ↑ Phillip Gross (January 1986), Proceedings of the 16-17 January 1986 DARPA Gateway Algorithms and Data Structures Task Force (PDF), IETF, pp. 5, 98, retrieved 2015-03-04,
Nagle presented his "fair queuing" scheme, in which gateways maintain separate queues for each sending host. In this way, hosts with pathological implementations can not usurp more than their fair share of the gateway's resources. This invoked spirited and interested discussion.
- ↑ Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1989). "निष्पक्ष कतारबद्ध एल्गोरिदम का विश्लेषण और अनुकरण". ACM SIGCOMM Computer Communication Review. 19 (4): 1–12. doi:10.1145/75247.75248.
- ↑ Demers, Alan; Keshav, Srinivasan; Shenker, Scott (1990). "एक उचित कतारबद्ध एल्गोरिदम का विश्लेषण और सिमुलेशन" (PDF). Internetworking: Research and Experience. 1: 3–26.
- ↑ Bennett, J. C. R.; Hui Zhang (1996). "WF/sup 2/Q: Worst-case fair weighted fair queueing". Proceedings of IEEE INFOCOM '96. Conference on Computer Communications. Vol. 1. p. 120. doi:10.1109/INFCOM.1996.497885. ISBN 978-0-8186-7293-4. S2CID 17558577.
- ↑ Ito, Y.; Tasaka, S.; Ishibashi, Y. (2002). "Variably weighted round robin queueing for core IP routers". Conference Proceedings of the IEEE International Performance, Computing, and Communications Conference (Cat. No.02CH37326). p. 159. doi:10.1109/IPCCC.2002.995147. ISBN 978-0-7803-7371-6. S2CID 60787008.
