निष्पक्ष पंक्तियन
फेयर क्यूइंग कुछ शेड्यूलिंग (कंप्यूटिंग) और नेटवर्क अनुसूचक में उपयोग किए जाने वाले शेड्यूलिंग एल्गोरिदम का समूह है। एल्गोरिदम को सीमित संसाधन साझा किए जाने पर निष्पक्षता प्राप्त करने के लिए डिज़ाइन किया गया है, उदाहरण के लिए बड़े पैकेट या प्रक्रियाओं के साथ प्रवाह को रोकने के लिए जो अन्य प्रवाह या प्रक्रियाओं की तुलना में अधिक थ्रूपुट या सीपीयू समय का उपभोग करके छोटे कार्य उत्पन्न करते हैं।
कुछ उन्नत नेटवर्क स्विच और राउटर (कंप्यूटिंग) में फेयर क्यूइंग प्रयुक्त किया गया है।
लना में अधिक थ्रूपुट या सीपीयू समय का उपभोग करके छोटे कार्य उत्पन्न करते हैं।
इतिहास
फेयर क्यूइंग शब्द जॉन नागले द्वारा 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.
