โทเค็นบัคเก็ต (Token Bucket)เป็นอัลกอริทึมที่ใช้ในเครือข่ายแบบแพ็กเก็ตสวิตช์และ เครือข่ายโทรคมนาคม สามารถใช้ตรวจสอบว่าการส่งข้อมูลในรูปแบบแพ็กเก็ตนั้นเป็นไปตามข้อจำกัดที่กำหนดไว้สำหรับแบนด์วิดท์และความผันแปรของปริมาณการรับส่งข้อมูล ( burstiness ) นอกจากนี้ยังสามารถใช้เป็นอัลกอริทึมการจัดตารางเวลาเพื่อกำหนดเวลาการส่งข้อมูลที่จะเป็นไปตามข้อจำกัดที่กำหนดไว้สำหรับแบนด์วิดท์และความผันแปรของปริมาณการรับส่งข้อมูลได้อีกด้วย (ดู ที่ ตัวจัดตาราง เวลาเครือข่าย )

อัลกอริทึมถังโทเค็น (Token Bucket) อิงตามแนวคิดของถัง ที่มีความจุคงที่ ซึ่งโทเค็น (โดยปกติจะแทนหน่วยไบต์หรือแพ็กเก็ต เดียว ที่มีขนาดที่กำหนดไว้ล่วงหน้า) จะถูกเติมเข้าไปในอัตราคงที่ เมื่อต้องการตรวจสอบว่าแพ็กเก็ตนั้นเป็นไปตามข้อจำกัดที่กำหนดไว้หรือไม่ ระบบจะตรวจสอบถังว่ามีโทเค็นเพียงพอหรือไม่ หากมี โทเค็นจำนวนที่เหมาะสม เช่น เท่ากับความยาวของแพ็กเก็ตในหน่วยไบต์ จะถูกนำออก ("แลกเป็นเงินสด") และแพ็กเก็ตนั้นจะถูกส่งต่อไป เช่น เพื่อการส่ง แพ็กเก็ตที่ไม่เป็นไปตามข้อกำหนดจะมีโทเค็นไม่เพียงพอในถัง และเนื้อหาในถังจะไม่เปลี่ยนแปลง แพ็กเก็ตที่ไม่เป็นไปตามข้อกำหนดสามารถจัดการได้หลายวิธี:

• พวกมันอาจถูกทิ้งได้
• โทเค็นเหล่านั้นอาจถูกจัดคิวเพื่อส่งในครั้งต่อไปเมื่อมีโทเค็นสะสมในบัคเก็ตเพียงพอแล้ว
• ข้อมูลเหล่านั้นอาจถูกส่งไปได้ แต่จะถูกทำเครื่องหมายว่าไม่เป็นไปตามข้อกำหนด และอาจถูกตัดทิ้งในภายหลังหากเครือข่ายมีภาระมากเกินไป

ดังนั้น โฟลว์ที่สอดคล้องกับข้อกำหนดจึงสามารถรองรับปริมาณการรับส่งข้อมูลที่มีอัตราเฉลี่ยสูงสุดเท่ากับอัตราที่โทเค็นถูกเพิ่มเข้าไปในบัคเก็ต และมีลักษณะเป็นช่วงๆ ที่กำหนดโดยความลึกของบัคเก็ต ลักษณะเป็นช่วงๆ นี้อาจแสดงได้ในรูปของค่า ความคลาดเคลื่อนของความคลาดเคลื่อน ( jitter tolerance) กล่าวคือ แพ็กเก็ตอาจสอดคล้องกับข้อกำหนด (เช่น มาถึงหรือถูกส่ง) เร็วกว่าที่คาดหวังจากขีดจำกัดของอัตราเฉลี่ยมากน้อยเพียงใด หรือค่าความคลาดเคลื่อนของช่วง (burst tolerance) หรือขนาดช่วงสูงสุด (maximum burst size) กล่าวคือ ปริมาณการรับส่งข้อมูลที่สอดคล้องกับข้อกำหนดอาจมากกว่าระดับเฉลี่ยมากน้อยเพียงใดในช่วงเวลาที่จำกัด

อัลกอริทึมโทเค็นบัคเก็ตสามารถเข้าใจได้ในเชิงแนวคิดดังนี้:

• มีการเพิ่มโทเค็นลงในถังทุกๆวินาที${\displaystyle 1/r}$
• ถังนี้สามารถบรรจุโทเค็นได้สูงสุดหากมีโทเค็นมาถึงเมื่อถังเต็มแล้ว โทเค็นนั้นจะถูกทิ้งไป${\displaystyle b}$
• เมื่อแพ็กเก็ต ( PDU ระดับเครือข่าย ) ขนาดnไบต์มาถึง
  • หากมีโทเค็นอย่างน้อยnอยู่ในบัคเก็ต ระบบ จะนำโทเค็น nออกจากบัคเก็ต และส่งแพ็กเก็ตไปยังเครือข่าย
  • หาก มีโทเค็นเหลือน้อยกว่าn โทเค็น จะไม่มีการลบโทเค็นออกจากบัคเก็ต และแพ็กเก็ตนั้นจะถือว่า ไม่เป็นไปตามข้อกำหนด

ผู้ใช้งานอัลกอริทึมนี้บนแพลตฟอร์มที่มีความละเอียดของนาฬิกาไม่เพียงพอที่จะเพิ่มโทเค็นลงในบัคเก็ตทุกๆวินาที อาจต้องพิจารณาใช้สูตรอื่น เนื่องจากสามารถอัปเดตบัคเก็ตโทเค็นได้ทุกๆ S มิลลิวินาที จำนวนโทเค็นที่จะเพิ่มทุกๆ S มิลลิวินาที = . ${\displaystyle 1/r}$${\displaystyle (r*S)/1000}$

ในระยะยาว ปริมาณแพ็กเก็ตที่ส่งออกมาซึ่งเป็นไปตามข้อกำหนดจะถูกจำกัดด้วยอัตราการส่งโทเค็น ${\displaystyle r}$

ให้เป็นอัตราการส่งข้อมูลสูงสุดที่เป็นไปได้ในหน่วยไบต์/วินาที ${\displaystyle M}$

จากนั้นคือช่วงเวลาใช้งานสูงสุด ซึ่งก็คือช่วงเวลาที่อัตราการใช้งานถูกใช้ประโยชน์อย่างเต็มที่ ${\displaystyle T_{\text{max}}={\begin{cases}b/(Mr)&{\text{ ถ้า }}r<M\\\infty &{\text{ มิเช่นนั้น }}\end{cases}}}$${\displaystyle M}$

ดังนั้นขนาดการระเบิดสูงสุดคือ${\displaystyle B_{\text{max}}=T_{\text{max}}*M}$

โทเค็นบัคเก็ตสามารถใช้ได้ทั้งในการควบคุมการรับส่งข้อมูล (traffic shaping)หรือการควบคุมการจราจร (traffic policing) ในการควบคุมการจราจร แพ็กเก็ตที่ไม่เป็นไปตามข้อกำหนดอาจถูกทิ้ง (dropped) หรืออาจถูกลดลำดับความสำคัญลง (เพื่อให้ฟังก์ชันการจัดการการรับส่งข้อมูลปลายทางทิ้งหากเกิดความแออัด) ในการควบคุมการรับส่งข้อมูล แพ็กเก็ตจะถูกหน่วงเวลาจนกว่าจะเป็นไปตามข้อกำหนด การควบคุมการจราจรและการควบคุมการรับส่งข้อมูลมักใช้เพื่อป้องกันเครือข่ายจากการรับส่งข้อมูลที่มากเกินไปหรือกระจัดกระจายมากเกินไป ดูการจัดการแบนด์วิดท์และการหลีกเลี่ยงความ แออัด การควบคุม การรับส่งข้อมูลมักใช้ในอินเทอร์เฟซเครือข่ายในโฮสต์เพื่อป้องกันไม่ให้การส่งข้อมูลถูกทิ้งโดยฟังก์ชันการจัดการการรับส่งข้อมูลในเครือข่าย

อัลกอริทึมโทเค็นบัคเก็ตยังใช้ในการควบคุมการไหลของ IO ของฐานข้อมูลด้วย^{[ 1 ]}ในอัลกอริทึมนี้ ข้อจำกัดไม่ได้ใช้กับIOPSหรือแบนด์วิดท์ แต่ใช้กับผลรวมเชิงเส้นของทั้งสองอย่าง โดยการกำหนดโทเค็นให้เป็นผลรวมปกติของน้ำหนักคำขอ IO และความยาว อัลกอริทึมนี้จะทำให้มั่นใจได้ว่าอนุพันธ์เวลาของฟังก์ชันดังกล่าวจะต่ำกว่าเกณฑ์ที่ต้องการ

อัลกอริทึมถังโทเค็นสามารถเปรียบเทียบได้โดยตรงกับอัลกอริทึม ถังรั่วหนึ่งในสองเวอร์ชันที่อธิบายไว้ในเอกสาร^{[ 2 ] [ 3 ] [ 4 ] [ 5 ]}เวอร์ชันที่เปรียบเทียบได้ของถังรั่วนี้อธิบายไว้ในหน้าวิกิพีเดียที่เกี่ยวข้องในชื่ออัลกอริทึมถังรั่วเป็นมิเตอร์ซึ่งเป็นภาพสะท้อนของถังโทเค็น โดยที่แพ็กเก็ตที่สอดคล้องกันจะเพิ่มของเหลว ซึ่งเทียบเท่ากับโทเค็นที่ถูกนำออกโดยแพ็กเก็ตที่สอดคล้องกันในอัลกอริทึมถังโทเค็น ลงในถังที่มีความจุจำกัด จากนั้นของเหลวนี้จะไหลออกไปในอัตราคงที่ ซึ่งเทียบเท่ากับกระบวนการที่โทเค็นถูกเพิ่มในอัตราคงที่

อย่างไรก็ตาม ยังมีอัลกอริทึมถังรั่วอีกเวอร์ชันหนึ่ง^{[ 3 ]}ซึ่งอธิบายไว้ในหน้าวิกิพีเดียที่เกี่ยวข้องว่าเป็นอัลกอริทึมถังรั่วในรูปแบบคิวนี่เป็นกรณีพิเศษของถังรั่วในรูปแบบมิเตอร์ ซึ่งสามารถอธิบายได้ด้วยแพ็กเก็ตที่สอดคล้องกันที่ผ่านถัง ดังนั้นถังรั่วในรูปแบบคิวจึงใช้ได้เฉพาะกับการปรับรูปร่างการจราจร และโดยทั่วไปจะไม่อนุญาตให้สตรีมแพ็กเก็ตเอาต์พุตเป็นแบบเป็นชุด กล่าวคือ ไม่มีการกระตุก ดังนั้นจึงแตกต่างจากอัลกอริทึมถังโทเค็นอย่างมาก

อัลกอริทึมถังรั่วทั้งสองเวอร์ชันนี้ได้รับการอธิบายไว้ในเอกสารทางวิชาการภายใต้ชื่อเดียวกัน ซึ่งนำไปสู่ความสับสนอย่างมากเกี่ยวกับคุณสมบัติของอัลกอริทึมนั้นและการเปรียบเทียบกับอัลกอริทึมถังโทเค็น อย่างไรก็ตาม โดยพื้นฐานแล้ว อัลกอริทึมทั้งสองเหมือนกัน และหากนำไปใช้อย่างถูกต้องและใช้พารามิเตอร์เดียวกัน ก็จะมองเห็นแพ็กเก็ตที่สอดคล้องและไม่สอดคล้องเหมือนกันทุกประการ

ถังโทเค็นแบบลำดับชั้น (HTB) เป็นระบบคิวแบบคลาส (CBQ) ที่ทำงานได้เร็วขึ้น ในLinux ^{[ 6 ]}มีประโยชน์ในการจำกัด อัตรา การดาวน์โหลด / อัปโหลด ของไคลเอนต์แต่ละราย เพื่อไม่ให้ไคลเอนต์ที่ถูกจำกัดนั้นใช้แบนด์วิดท์ทั้งหมดจน เต็ม

โดยหลักการแล้ว HTB คือกลุ่มโทเค็นบัคเก็ตจำนวนหนึ่งที่จัดเรียงเป็นลำดับชั้น ตัวควบคุมคิวขาออกหลัก ( qdisc ) บนอุปกรณ์ใดๆ เรียกว่า root qdisc root qdisc จะมีคลาสเดียว คลาส HTB เดียวนี้จะถูกกำหนดด้วยพารามิเตอร์สองตัว คืออัตรา (rate)และค่าสูงสุด (ceil ) ค่าเหล่านี้ควรเหมือนกันสำหรับคลาสระดับบนสุดและจะแสดงถึงแบนด์วิดท์ทั้งหมดที่มีอยู่บนลิงก์

ใน HTB (Hierarchical Token Bucket) คำว่า rateหมายถึงแบนด์วิดท์ที่รับประกันสำหรับคลาสที่กำหนด และceil (ย่อมาจาก ceiling) ระบุแบนด์วิดท์สูงสุดที่คลาสนั้นสามารถใช้ได้ เมื่อคลาสร้องขอแบนด์วิดท์มากกว่าที่รับประกัน คลาสนั้นอาจยืมแบนด์วิดท์จากคลาสแม่ได้ ตราบใดที่ยังไม่ถึงค่า ceil ทั้งสองค่า ระบบ Hierarchical Token Bucket ใช้กลไกการจัดคิวแบบคลาสสำหรับระบบควบคุมการจราจรของ Linux และให้ค่า rate และ ceil เพื่อให้ผู้ใช้สามารถควบคุมแบนด์วิดท์โดยรวมสำหรับคลาสการจราจรเฉพาะ รวมถึงระบุอัตราส่วนการกระจายแบนด์วิดท์เมื่อมีแบนด์วิดท์ส่วนเกิน (สูงสุดเท่ากับค่า ceil)

ในการเลือกแบนด์วิดท์สำหรับคลาสระดับสูง การจัดการปริมาณการรับส่งข้อมูลจะช่วยได้เฉพาะบริเวณคอขวดระหว่างเครือข่าย LAN กับอินเทอร์เน็ตเท่านั้น โดยทั่วไปแล้ว กรณีนี้มักเกิดขึ้นในสภาพแวดเจิงเครือข่ายภายในบ้านและสำนักงาน ซึ่งเครือข่าย LAN ทั้งหมดให้บริการโดยการเชื่อมต่อ DSL หรือ T1

• การจำกัดอัตรา
• การควบคุมการจราจร
• การนับสัญญาณธง

• John Evans, Clarence Filsfils (2007). การใช้งาน IP และ MPLS QoS สำหรับเครือข่ายมัลติเซอร์วิส: ทฤษฎีและการปฏิบัติ . Morgan Kaufmann. ISBN 978-0-12-370549-5.
• เฟอร์กูสัน พี., ฮัสตัน จี. (1998). คุณภาพของการบริการ: การส่งมอบ QoS บนอินเทอร์เน็ตและในเครือข่ายองค์กร . จอห์น ไวลีย์ แอนด์ ซันส์ อิงค์. ISBN 0-471-24358-2.