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

การกำหนดเส้นทางแรงดันย้อนกลับเป็นอัลกอริทึมสำหรับการกำหนดเส้นทางการรับส่งข้อมูลแบบไดนามิกบนเครือข่ายหลายฮอปโดยใช้การไล่ระดับความแออัด อัลกอริทึมนี้สามารถนำไปใช้กับเครือข่ายการสื่อสารไร้สาย รวมถึงเครือข่ายเซ็นเซอร์เครือข่าย ad hoc เคลื่อนที่ ( MANETS ) และเครือข่ายแบบผสมที่มีส่วนประกอบไร้สายและมีสาย^{[ 2 ] [ 3 ]}

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

การกำหนดเส้นทางแบบ Backpressure ส่วนใหญ่ได้รับการศึกษาในบริบททางทฤษฎี ในทางปฏิบัติ เครือข่ายไร้สายแบบ ad hoc มักจะใช้วิธีการกำหนดเส้นทางทางเลือกโดยอาศัยการคำนวณเส้นทางที่สั้นที่สุดหรือการกระจายเครือข่าย เช่น Ad Hoc on-Demand Distance Vector Routing (AODV), การกำหนดเส้นทางตามภูมิศาสตร์และการกำหนดเส้นทางแบบฉวยโอกาสอย่างยิ่ง (ExOR) อย่างไรก็ตาม คุณสมบัติความเหมาะสมทางคณิตศาสตร์ของ Backpressure ได้กระตุ้นให้เกิดการสาธิตเชิงทดลองล่าสุดในการใช้งานบนแพลตฟอร์มทดสอบไร้สายที่มหาวิทยาลัยเซาท์เทิร์นแคลิฟอร์เนียและมหาวิทยาลัยนอร์ทแคโรไลนาสเตท^{[ 5 ] [ 6 ] [ 7 ]}

อัลกอริทึมแรงดันย้อนกลับดั้งเดิมได้รับการพัฒนาโดย Tassiulas และ Ephremides ^{[ 2 ]}พวกเขาพิจารณา เครือข่าย วิทยุแพ็กเก็ตแบบหลายฮอป ที่มีการมาถึงของแพ็กเก็ตแบบสุ่มและชุดตัวเลือกการเลือกลิงก์ที่กำหนดไว้ อัลกอริทึมของพวกเขาประกอบด้วย ขั้นตอน การเลือกลิงก์ที่มีน้ำหนักสูงสุดและ ขั้นตอน การกำหนดเส้นทางแบ็กล็อกแบบดิฟเฟอเรนเชียล อัลกอริทึมที่เกี่ยวข้องกับแรงดันย้อนกลับซึ่งออกแบบมาเพื่อคำนวณการไหลของเครือข่ายหลายสินค้าได้รับการพัฒนาใน Awerbuch และ Leighton ^{[ 8 ]} ต่อมาอัลกอริทึมแรงดันย้อนกลับได้รับการขยายโดย Neely, Modiano และ Rohrs เพื่อจัดการกับการจัดตารางเวลาสำหรับเครือข่ายมือถือ^{[ 9 ]} แรงดันย้อนกลับได้รับการวิเคราะห์ทางคณิตศาสตร์ผ่านทฤษฎีการเคลื่อนตัวของ Lyapunovและสามารถใช้ร่วมกับกลไกการควบคุมการไหลเพื่อให้ได้ ประโยชน์ สูงสุดของเครือข่าย^{[ 10 ] [ 11 ] [ 3 ] [ 12 ] [ 13 ]} (ดูเพิ่มเติมที่ แรงดันย้อนกลับพร้อมการเพิ่มประสิทธิภาพยูทิลิตี้และการลดค่าปรับ )

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

พิจารณาเครือข่ายแบบหลายฮอปที่มี โหนด Nโหนด (ดูรูปที่ 1 สำหรับตัวอย่างที่มีN  = 6) เครือข่ายทำงานในเวลาแบบแบ่งช่วงเวลาในแต่ละช่วงเวลา ข้อมูลใหม่สามารถเข้ามาในเครือข่ายได้ และจะมีการตัดสินใจเกี่ยวกับการกำหนดเส้นทางและการจัดตารางการส่งข้อมูลเพื่อส่งข้อมูลทั้งหมดไปยังปลายทางที่ถูกต้อง ให้ข้อมูลที่มีจุดหมายปลายทางที่โหนด n ถูกระบุว่าเป็นข้อมูลประเภท cข้อมูลในแต่ละโหนดจะถูกจัดเก็บตามประเภทของข้อมูล สำหรับและให้เป็นปริมาณข้อมูลประเภทc ปัจจุบัน ในโหนดnหรือเรียกว่าคิวค้างส่งรูปที่ 2 แสดงภาพขยายของคิวค้างส่งภายในโหนด หน่วยของขึ้นอยู่กับบริบทของปัญหา ตัวอย่างเช่น คิวค้างส่งอาจมีหน่วยเป็นจำนวนเต็มของแพ็กเก็ตซึ่งมีประโยชน์ในกรณีที่ข้อมูลถูกแบ่งออกเป็นแพ็กเก็ตที่มีความยาวคงที่ หรืออาจมีหน่วยเป็นจำนวนจริงของบิตสมมติว่าสำหรับทุกและทุกช่วงเวลาtเนื่องจากไม่มีโหนดใดจัดเก็บข้อมูลที่มีจุดหมายปลายทางสำหรับตัวเอง ในแต่ละช่วงเวลา โหนดต่างๆ สามารถส่งข้อมูลไปยังโหนดอื่นๆ ได้ ข้อมูลที่ส่งจากโหนดหนึ่งไปยังอีกโหนดหนึ่งจะถูกนำออกจากคิวของโหนดแรกและเพิ่มเข้าไปในคิวของโหนดที่สอง ข้อมูลที่ส่งถึงปลายทางแล้วจะถูกนำออกจากเครือข่าย นอกจากนี้ ข้อมูลยังสามารถเข้ามาจากภายนอกเครือข่ายได้ โดยข้อมูลใหม่นี้จะถูกกำหนดให้เป็นปริมาณข้อมูลที่เข้ามายังโหนดnในช่วงเวลาtซึ่งจะต้องถูกส่งต่อไปยังโหนดcใน ที่สุด${\displaystyle t\in \{0,1,2,\ldots \}}$${\displaystyle c\in \{1,\dots ,N\}}$${\displaystyle n\in \{1,\ldots ,N\}}$${\displaystyle c\in \{1,\ldots ,N\}}$${\displaystyle Q_{n}^{(c)}(t)}$${\displaystyle Q_{n}^{(c)}(t)}$${\displaystyle Q_{c}^{(c)}(t)=0}$${\displaystyle c\in \{1,\ldots ,N\}}$${\displaystyle A_{n}^{(c)}(t)}$

ให้เป็นอัตราการส่งข้อมูลที่เครือข่ายใช้ผ่านลิงก์ ( a , b ) ในช่วงเวลาtซึ่งแสดงถึงปริมาณข้อมูลที่สามารถถ่ายโอนจากโหนดaไปยังโหนดbในช่วงเวลาปัจจุบัน ให้เป็นเมทริกซ์อัตราการส่งข้อมูล อัตราการส่งข้อมูลเหล่านี้จะต้องถูกเลือกภายในชุดตัวเลือกที่อาจเปลี่ยนแปลงตามเวลา โดยเฉพาะอย่างยิ่ง เครือข่ายอาจมีช่องสัญญาณและการเคลื่อนที่ของโหนดที่เปลี่ยนแปลงตามเวลา และสิ่งนี้อาจส่งผลต่อความสามารถในการส่งข้อมูลในแต่ละช่วงเวลา เพื่อจำลองสิ่งนี้ ให้S ( t ) แทนสถานะโทโพโลยีของเครือข่าย ซึ่งจับคุณสมบัติของเครือข่ายในช่วงเวลาtที่ส่งผลต่อการส่งข้อมูล ให้แทนชุดของตัวเลือกเมทริกซ์อัตราการส่งข้อมูลที่มีอยู่ภายใต้สถานะโทโพโลยีS ( t ) ในแต่ละช่วงเวลาtตัวควบคุมเครือข่ายจะสังเกตS ( t ) และเลือกอัตราการส่งข้อมูลภายในชุดการเลือกเมทริกซ์ที่จะเลือกในแต่ละช่วงเวลาtจะอธิบายในหัวข้อถัดไป ${\displaystyle \mu _{ab}(t)}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle \Gamma _{S(t)}}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle \Gamma _{S(t)}}$${\displaystyle (\mu _{ab}(t))}$

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

ในแต่ละช่องtตัวควบคุมแรงดันย้อนกลับจะสังเกตS ( t ) และดำเนินการ 3 ขั้นตอนต่อไปนี้:

• ขั้นแรก สำหรับแต่ละลิงก์ ( a , b ) ระบบจะเลือกสินค้าที่เหมาะสมที่สุด ที่จะใช้${\displaystyle c_{ab}^{opt}(t)}$
• ขั้นตอนต่อไปคือการพิจารณาว่าจะใช้เมทริกซ์ ใด${\displaystyle (\mu _{ab}(t))}$${\displaystyle \Gamma _{S(t)}}$
• สุดท้าย ระบบจะกำหนดปริมาณสินค้าที่จะส่งผ่านลิงก์ ( a , b ) (โดยมีค่าสูงสุดแต่ในบางกรณีอาจน้อยกว่านั้น)${\displaystyle c_{ab}^{opt}(t)}$${\displaystyle \mu _{ab}(t)}$

แต่ละโหนดaจะสังเกตคิวค้างของตนเองและคิวค้างของโหนดเพื่อนบ้านปัจจุบัน โหนดเพื่อนบ้านปัจจุบันของโหนดaคือโหนดbที่สามารถเลือกอัตราการส่งข้อมูลที่ไม่เป็นศูนย์ในช่องสัญญาณปัจจุบันได้ ดังนั้น เพื่อนบ้านจึงถูกกำหนดโดยเซตในกรณีสุดขั้ว โหนดหนึ่งสามารถมีโหนดอื่นทั้งหมดN  − 1 โหนดเป็นเพื่อนบ้านได้ อย่างไรก็ตาม โดยทั่วไปแล้วจะใช้เซตที่ป้องกันการส่งข้อมูลระหว่างโหนดที่อยู่ห่างกันเกินระยะทางทางภูมิศาสตร์ที่กำหนด หรือที่มีความแรงของสัญญาณที่แพร่กระจายต่ำกว่าเกณฑ์ที่กำหนด ดังนั้น จำนวนเพื่อนบ้านจึงมักน้อยกว่าN  − 1 มาก ตัวอย่างในรูปที่ 1 แสดงเพื่อนบ้านโดยการเชื่อมต่อลิงก์ ดังนั้นโหนด 5 จึงมีเพื่อนบ้านคือ 4 และ 6 ตัวอย่างนี้ชี้ให้เห็นถึงความสัมพันธ์แบบสมมาตรระหว่างเพื่อนบ้าน (ดังนั้นถ้า 5 เป็นเพื่อนบ้านของ 4 แล้ว 4 ก็เป็นเพื่อนบ้านของ 5) แต่โดยทั่วไปแล้วไม่จำเป็นต้องเป็นเช่นนั้นเสมอไป ${\displaystyle \mu _{ab}(t)}$${\displaystyle \Gamma _{S(t)}}$${\displaystyle \Gamma _{S(t)}}$

ชุดของโหนดข้างเคียงของโหนดที่กำหนด จะเป็นตัวกำหนดชุดของลิงก์ขาออกที่โหนดนั้นสามารถใช้สำหรับการส่งข้อมูลในช่องเวลาปัจจุบัน สำหรับแต่ละลิงก์ขาออก ( a , b ) สินค้าที่เหมาะสมที่สุด จะถูกกำหนดให้เป็นสินค้า ที่ทำให้ปริมาณ สินค้าคงคลังส่วนต่างต่อไปนี้มีค่าสูงสุด: ${\displaystyle c_{ab}^{opt}(t)}$${\displaystyle c\in \{1,\ldots ,N\}}$

${\displaystyle Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)}$

หากมีข้อขัดแย้งใดๆ ในการเลือกสินค้าที่เหมาะสมที่สุด การตัดสินใจจะใช้วิธีสุ่มเลือก

ตัวอย่างแสดงอยู่ในรูปที่ 2 ตัวอย่างนี้สมมติว่าแต่ละคิวมีสินค้าเพียง 3 ชนิด ได้แก่ สีแดงสีเขียวและ สีน้ำเงินโดยวัดเป็นหน่วยจำนวนเต็มของแพ็กเก็ต เมื่อพิจารณาลิงก์แบบมีทิศทาง (1,2) ค่า backlog ที่แตกต่างกันมีดังนี้:

${\displaystyle Q_{1}^{({\text{red}})}(t)-Q_{2}^{({\text{red}})}(t)=1}$

${\displaystyle Q_{1}^{({\text{green}})}(t)-Q_{2}^{({\text{green}})}(t)=2}$

${\displaystyle Q_{1}^{({\text{blue}})}(t)-Q_{2}^{({\text{blue}})}(t)=-1}$

ดังนั้น สินค้าที่เหมาะสมที่สุดที่จะส่งผ่านลิงก์ (1,2) ในช่วงเวลาtคือสินค้าสีเขียว ในทางกลับกัน สินค้าที่เหมาะสมที่สุดที่จะส่งผ่านลิงก์ย้อนกลับ (2,1) ในช่วงเวลาtคือสินค้าสีฟ้า

เมื่อกำหนดสินค้าที่เหมาะสมที่สุดสำหรับแต่ละลิงก์ ( a , b ) แล้ว ตัวควบคุมเครือข่ายจะคำนวณน้ำหนักต่อไปนี้: ${\displaystyle W_{ab}(t)}$

${\displaystyle W_{ab}(t)=\max \left[Q_{a}^{(c_{ab}^{\mathrm {opt} }(t))}(t)-Q_{b}^{(c_{ab}^{opt}(t))}(t),0\right]}$

น้ำหนักคือค่าของปริมาณงานค้างที่แตกต่างกันซึ่งเกี่ยวข้องกับสินค้าที่เหมาะสมที่สุดสำหรับลิงก์ ( a , b ) โดยมีค่าสูงสุดเป็น 0 จากนั้นตัวควบคุมจะเลือกอัตราการส่งข้อมูลเป็นคำตอบของปัญหา ค่าน้ำหนักสูงสุดต่อไปนี้(โดยจะตัดตัวเลือกที่มีค่าเท่ากันโดยพลการ): ${\displaystyle W_{ab}(t)}$

${\displaystyle {\text{(สมการ 1)}}\qquad {\text{เพิ่มค่าสูงสุด: }}\sum _{a=1}^{N}\sum _{b=1}^{N}\mu _{ab}(t)W_{ab}(t)}$

${\displaystyle {\text{(สมการ 2)}}\qquad {\text{ภายใต้เงื่อนไข: }}(\mu _{ab}(t))\in \Gamma _{S(t)}}$

ยกตัวอย่างการตัดสินใจโดยใช้ค่าน้ำหนักสูงสุด สมมติว่าในช่องเวลาปัจจุบันtปริมาณงานค้างที่แตกต่างกันในแต่ละลิงก์ของเครือข่าย 6 โหนด ส่งผลให้ค่าน้ำหนักของลิงก์เป็นดังนี้: ${\displaystyle W_{ab}(t)}$

${\displaystyle (W_{ab}(t))=\left[{\begin{array}{cccccc}0&2&1&1&6&0\\1&0&1&2&5&6\\0&7&0&0&0&0\\1&0&1&0&0&0\\1&0&7&5&0&0\\0&0&0&0&5&0\end{array}}\right]}$

แม้ว่าเซตดังกล่าวอาจมีเมทริกซ์อัตราการส่งข้อมูลที่เป็นไปได้จำนวนมหาศาลนับไม่ถ้วน แต่เพื่อความง่าย ให้สมมติว่าสถานะโทโพโลยีปัจจุบันมีเพียง 4 ตัวเลือกที่เป็นไปได้เท่านั้น: ${\displaystyle \Gamma _{S(t)}}$

${\displaystyle \Gamma _{S(t)}=\{{\boldsymbol {\mu }}_{a},{\boldsymbol {\mu }}_{b},{\boldsymbol {\mu }}_{c},{\boldsymbol {\mu }}_{d}\}}$

ภาพประกอบแสดงตัวเลือกอัตราการส่งข้อมูลที่เป็นไปได้ 4 แบบภายใต้สถานะโทโพโลยีปัจจุบันS ( t ) ตัวเลือก (a) เปิดใช้งานลิงก์เดี่ยว (1,5) ด้วยอัตราการส่งข้อมูลตัวเลือกอื่นๆ ทั้งหมดใช้ลิงก์สองลิงก์ โดยมีอัตราการส่งข้อมูล 1 บนลิงก์ที่เปิดใช้งานแต่ละลิงก์ ${\displaystyle \mu _{15}=2}$

ความเป็นไปได้ทั้งสี่ประการนี้แสดงในรูปแบบเมทริกซ์ได้ดังนี้:

${\displaystyle {\boldsymbol {\mu }}_{a}=\left[{\begin{array}{cccccc}0&0&0&0&2&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right],\quad {\boldsymbol {\mu }}_{b}=\left[{\begin{array}{cccccc}0&0&0&0&0&0\\0&0&1&0&0&0\\0&0&0&0&0&0\\0&0&0&0&1&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right]}$

${\displaystyle {\boldsymbol {\mu }}_{c}=\left[{\begin{array}{cccccc}0&0&0&0&0&0\\1&0&0&0&0&0\\0&0&0&0&0&0\\0&0&0&0&1&0\\0&0&0&0&0&0\\0&0&0&0&0&0\end{array}}\right],\quad {\boldsymbol {\mu }}_{d}=\left[{\begin{array}{cccccc}0&0&0&0&0&0\\0&0&0&0&0&0\\0&1&0&0&0&0\\0&0&0&0&0&0\\0&0&0&1&0&0\\0&0&0&0&0&0\end{array}}\right]}$

โปรดสังเกตว่าโหนด 6 ไม่สามารถส่งหรือรับข้อมูลได้ในทุกกรณีที่เป็นไปได้ นี่อาจเกิดขึ้นเนื่องจากโหนด 6 อยู่นอกระยะการสื่อสารในขณะนี้ ผลรวมถ่วงน้ำหนักของอัตราสำหรับแต่ละกรณีที่เป็นไปได้ทั้ง 4 กรณีมีดังนี้:

• ตัวเลือก (ก): .${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=12}$
• ตัวเลือก (ข): .${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=1}$
• ตัวเลือก (ค): .${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=1}$
• ตัวเลือก (ง): .${\displaystyle \sum _{ab}W_{ab}(t)\mu _{ab}(t)=12}$

เนื่องจากมีค่าน้ำหนักสูงสุดเท่ากันที่ 12 ตัวควบคุมเครือข่ายจึงสามารถตัดสินใจได้โดยพลการโดยเลือกตัวเลือกใดตัวเลือกหนึ่ง ${\displaystyle {\boldsymbol {\mu }}_{a}}$${\displaystyle {\boldsymbol {\mu }}_{d}}$

สมมติว่าขณะนี้ได้กำหนดสินค้าที่เหมาะสมที่สุด สำหรับแต่ละลิงก์แล้ว และอัตราการส่งข้อมูลก็ได้รับการกำหนดแล้วเช่นกัน หากผลรวมของปริมาณข้อมูลที่รอส่ง (backlog) สำหรับสินค้าที่เหมาะสมที่สุดบนลิงก์ ( a , b ) ที่กำหนดมีค่าเป็นลบ จะไม่มีการส่งข้อมูลผ่านลิงก์นี้ในช่องเวลาปัจจุบัน มิฉะนั้น เครือข่ายจะเสนอให้ส่ง ข้อมูล สินค้า ผ่านลิงก์นี้ โดยทำได้โดยการกำหนดตัวแปรการกำหนดเส้นทางสำหรับแต่ละลิงก์ ( a , b ) และแต่ละสินค้าcโดยที่: ${\displaystyle c_{ab}^{opt}(t)}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle \mu _{ab}(t)}$${\displaystyle c_{ab}^{\mathrm {opt} }(t)}$${\displaystyle \mu _{ab}^{(c)}(t)}$

${\displaystyle \mu _{ab}^{(c)}(t)={\begin{cases}\mu _{ab}(t)&{\text{ if }}c=c_{ab}^{opt}(t){\text{ and }}Q_{a}^{(c_{ab}^{opt}(t))}(t)-Q_{b}^{(c_{ab}^{opt}(t))}(t)\geq 0\\0&{\text{ otherwise}}\end{cases}}}$

ค่าของแสดงถึงอัตราการส่งข้อมูลที่เสนอให้กับข้อมูลสินค้าcผ่านลิงก์ ( a , b ) ในช่วงเวลาtอย่างไรก็ตาม โหนดอาจไม่มีสินค้าบางชนิดเพียงพอที่จะรองรับการส่งข้อมูลในอัตราที่เสนอในลิงก์ขาออกทั้งหมด สถานการณ์นี้เกิดขึ้นในช่วงเวลาtสำหรับโหนดnและสินค้าcหาก: ${\displaystyle \mu _{ab}^{(c)}(t)}$

${\displaystyle Q_{n}^{(c)}(t)<\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)}$

ในกรณีนี้ ข้อมูลทั้งหมดจะถูกส่งออกไป และข้อมูลว่างจะถูกใช้เพื่อเติมส่วนที่ไม่ได้ใช้ของอัตราที่เสนอ โดยจัดสรรข้อมูลจริงและข้อมูลว่างอย่างไม่เจาะจงไปยังลิงก์ขาออกที่เกี่ยวข้อง (ตามอัตราที่เสนอ) สถานการณ์นี้เรียกว่าคิวอันเดอร์โฟลว์อันเดอร์โฟลว์ดังกล่าวไม่ส่งผลกระทบต่อปริมาณงานหรือคุณสมบัติความเสถียรของเครือข่าย โดยทั่วไปแล้ว เนื่องจากอันเดอร์โฟลว์จะเกิดขึ้นก็ต่อเมื่อโหนดที่ส่งข้อมูลมีปริมาณงานค้างอยู่น้อย ซึ่งหมายความว่าโหนดนั้นไม่ได้อยู่ในภาวะเสี่ยงต่อความไม่เสถียร ${\displaystyle Q_{n}^{(c)}(t)}$

อัลกอริทึมแรงดันย้อนกลับ (backpressure algorithm) ไม่ได้ใช้เส้นทางที่กำหนดไว้ล่วงหน้า เส้นทางจะถูกเรียนรู้แบบไดนามิก และอาจแตกต่างกันสำหรับแพ็กเก็ตต่างๆ ความล่าช้าอาจมีขนาดใหญ่มาก โดยเฉพาะอย่างยิ่งเมื่อระบบมีภาระงานเบา ทำให้ไม่มีแรงดันเพียงพอที่จะผลักดันข้อมูลไปยังปลายทาง ตัวอย่างเช่น สมมติว่ามีแพ็กเก็ตหนึ่งเข้าสู่เครือข่าย และไม่มีแพ็กเก็ตอื่นเข้ามาเลย แพ็กเก็ตนี้อาจเดินทางเป็นวงกว้างผ่านเครือข่ายและไม่ถึงปลายทางเนื่องจากไม่มีแรงดันเกิดขึ้น อย่างไรก็ตาม นี่ไม่ได้ขัดแย้งกับคุณสมบัติความเหมาะสมของปริมาณงานหรือความเสถียรของแรงดันย้อนกลับ เนื่องจากเครือข่ายมีแพ็กเก็ตอย่างมากที่สุดเพียงหนึ่งแพ็กเก็ตในเวลาใดๆ ดังนั้นจึงมีความเสถียรอย่างมาก (อัตราการส่งมอบเป็น 0 เท่ากับอัตราการมาถึง)

นอกจากนี้ยังสามารถใช้แรงดันย้อนกลับกับชุดเส้นทางที่กำหนดไว้ล่วงหน้าได้ ซึ่งอาจจำกัดขอบเขตความจุ แต่อาจช่วยปรับปรุงการส่งมอบตามลำดับและลดความล่าช้าได้ อีกวิธีหนึ่งในการปรับปรุงความล่าช้าโดยไม่กระทบต่อขอบเขตความจุ คือการใช้ เวอร์ชัน ที่ได้รับการปรับปรุง ซึ่งให้น้ำหนักลิงก์ไปในทิศทางที่ต้องการ^{[ 9 ]} การจำลองการให้น้ำหนักดังกล่าวแสดงให้เห็นถึงการปรับปรุงความล่าช้าอย่างมีนัยสำคัญ^{[ 1 ] [ 3 ]} โปรดทราบว่าแรงดันย้อนกลับไม่จำเป็นต้องใช้บริการแบบเข้าก่อนออกก่อน ( FIFO ) ที่คิว มีการสังเกตว่าบริการแบบเข้าหลังออกก่อน ( LIFO ) สามารถปรับปรุงความล่าช้าสำหรับแพ็กเก็ตส่วนใหญ่ได้อย่างมากโดยไม่กระทบต่อปริมาณงาน^{[ 7 ] [ 14 ]}

โปรดทราบว่าเมื่อ เลือก อัตราการส่ง แล้ว ตัวแปรการตัดสินใจการกำหนดเส้นทาง สามารถคำนวณได้ในลักษณะกระจายอย่างง่าย โดยที่แต่ละโหนดต้องการเพียงความรู้เกี่ยวกับความแตกต่างของคิวค้างระหว่างตัวเองกับเพื่อนบ้าน อย่างไรก็ตาม การเลือกอัตราการส่งต้องใช้วิธีแก้ปัญหาค่าน้ำหนักสูงสุดในสมการ (1)-(2) ในกรณีพิเศษเมื่อช่องสัญญาณตั้งฉากกัน อัลกอริทึมมีการใช้งานแบบกระจายตามธรรมชาติและลดลงเหลือการตัดสินใจแยกกันที่แต่ละโหนด อย่างไรก็ตาม ปัญหาค่าน้ำหนักสูงสุดเป็นปัญหาการควบคุมแบบรวมศูนย์สำหรับเครือข่ายที่มีการรบกวนระหว่างช่องสัญญาณ นอกจากนี้ยังอาจยากมากที่จะแก้ไขได้แม้ในลักษณะรวมศูนย์ ${\displaystyle (\mu _{ab}(t))}$${\displaystyle \mu _{ab}^{(c)}(t)}$

วิธีการแบบกระจายสำหรับเครือข่ายการรบกวนที่มีอัตราลิงก์ที่กำหนดโดยอัตราส่วนสัญญาณต่อสัญญาณรบกวนบวกการรบกวน (SINR) สามารถดำเนินการได้โดยใช้การสุ่ม^{[ 9 ]} แต่ละโหนดจะตัดสินใจส่งในแต่ละช่วงเวลาtแบบสุ่ม (ส่งแพ็กเก็ต "ว่าง" หากในขณะนั้นไม่มีแพ็กเก็ตที่จะส่ง) อัตราการส่งจริงและแพ็กเก็ตจริงที่จะส่งจะถูกกำหนดโดยการจับมือ 2 ขั้นตอน: ในขั้นตอนแรก โหนดส่งสัญญาณที่เลือกแบบสุ่มจะส่งสัญญาณนำร่องที่มีความแรงของสัญญาณเป็นสัดส่วนกับการส่งจริง ในขั้นตอนที่สอง โหนดรับสัญญาณที่เป็นไปได้ทั้งหมดจะวัดการรบกวนที่เกิดขึ้นและส่งข้อมูลนั้นกลับไปยังตัวส่งสัญญาณ ระดับ SINR สำหรับลิงก์ขาออกทั้งหมด ( n , b ) จะเป็นที่รู้จักของทุกโหนดnและแต่ละโหนดnสามารถตัดสินใจตัวแปรของตนเองได้โดยอาศัยข้อมูลนี้ ปริมาณงานที่ได้ไม่จำเป็นต้องเหมาะสมที่สุด อย่างไรก็ตาม กระบวนการส่งข้อมูลแบบสุ่มสามารถมองได้ว่าเป็นส่วนหนึ่งของกระบวนการสถานะช่องสัญญาณ (โดยมีเงื่อนไขว่าในกรณีที่เกิดภาวะข้อมูลไม่เพียงพอ จะมีการส่งแพ็กเก็ตว่าง เพื่อให้กระบวนการสถานะช่องสัญญาณไม่ขึ้นอยู่กับการตัดสินใจในอดีต) ดังนั้น อัตราการส่งข้อมูลที่ได้จากการใช้งานแบบกระจายนี้ จึงเหมาะสมที่สุดเมื่อเทียบกับอัลกอริธึมการกำหนดเส้นทางและการจัดตารางเวลาอื่นๆ ที่ใช้การส่งข้อมูลแบบสุ่มดังกล่าว ${\displaystyle \mu _{nb}(t)}$${\displaystyle (\mu _{nb}^{(c)}(t))}$

การใช้งานแบบกระจายทางเลือกสามารถจัดกลุ่มได้คร่าวๆ เป็นสองประเภท: ประเภทแรกของอัลกอริทึมจะพิจารณาการประมาณค่าตัวคูณคงที่สำหรับปัญหาน้ำหนักสูงสุด และให้ผลลัพธ์ปริมาณงานคงที่ ประเภทที่สองของอัลกอริทึมจะพิจารณาการประมาณค่าแบบบวกสำหรับปัญหาน้ำหนักสูงสุด โดยอาศัยการอัปเดตโซลูชันสำหรับปัญหาน้ำหนักสูงสุดเมื่อเวลาผ่านไป อัลกอริทึมในประเภทที่สองนี้ดูเหมือนจะต้องการเงื่อนไขช่องสัญญาณคงที่และเวลาการบรรจบกันที่ยาวนานกว่า (มักจะไม่ใช่พหุนาม) แม้ว่าจะสามารถพิสูจน์ได้ว่าสามารถบรรลุปริมาณงานสูงสุดภายใต้สมมติฐานที่เหมาะสม^{[ 15 ] [ 4 ] [ 13 ]}การประมาณค่าแบบบวกมักมีประโยชน์สำหรับการพิสูจน์ความเหมาะสมของแรงดันย้อนกลับเมื่อนำไปใช้กับข้อมูลคิวที่ล้าสมัย (ดูแบบฝึกหัด 4.10 ของตำรา Neely) ^{[ 13 ]}

ส่วนนี้แสดงให้เห็นว่าอัลกอริทึมแรงดันย้อนกลับเกิดขึ้นได้อย่างไร ซึ่งเป็นผลตามธรรมชาติของการลดขอบเขตของการเปลี่ยนแปลงในผลรวมของกำลังสองของคิวค้างจากช่องหนึ่งไปยังอีกช่องหนึ่งอย่างโลภ^{[ 9 ] [ 3 ]}

พิจารณาเครือข่ายแบบหลายฮอปที่มี โหนด Nโหนด ดังที่อธิบายไว้ในส่วนด้านบน ในแต่ละช่วงเวลาtตัวควบคุมเครือข่ายจะสังเกตสถานะโทโพโลยีS ( t ) และเลือกอัตราการส่งข้อมูลและตัวแปรการกำหนดเส้นทาง ภายใต้ข้อจำกัดต่อไปนี้: ${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

${\displaystyle {\text{(Eq. 3)}}\qquad (\mu _{ab}(t))\in \Gamma _{S(t)}}$

${\displaystyle {\text{(Eq. 4)}}\qquad 0\leq \mu _{ab}^{(c)}(t)\qquad \forall a,b,c,\forall t}$

${\displaystyle {\text{(Eq. 5)}}\qquad \sum _{c=1}^{N}\mu _{ab}^{(c)}(t)\leq \mu _{ab}(t)\qquad \forall (a,b),\forall t}$

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

${\displaystyle {\text{(Eq. 6)}}\qquad Q_{n}^{(c)}(t+1)\leq \max \left[Q_{n}^{(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{(c)}(t),0\right]+\sum _{a=1}^{N}\mu _{an}^{(c)}(t)+A_{n}^{(c)}(t)}$

โดยที่คือปริมาณข้อมูลสินค้าc ใหม่แบบสุ่ม ที่มาถึงโหนดnในช่วงเวลาtและคืออัตราการส่งข้อมูลที่จัดสรรให้กับปริมาณการรับส่งข้อมูลสินค้าcบนลิงก์ ( n , b ) ในช่วงเวลาtโปรดทราบว่าอาจมีมากกว่าปริมาณข้อมูลสินค้าcที่ส่งจริงบนลิงก์ ( a , b ) ในช่วงเวลาtเนื่องจากอาจมีคิวรอส่งไม่เพียงพอในโหนดnด้วยเหตุผลเดียวกันนี้ สมการ (6) จึงเป็นอสมการ ไม่ใช่สมการ เพราะ อาจมีมากกว่าปริมาณสินค้าc ที่ มาถึงโหนดnในช่วงเวลาt ที่เกิดขึ้นจริง คุณสมบัติที่สำคัญของสมการ (6) คือ สมการนี้ยังคงใช้ได้แม้ว่าตัวแปรการตัดสินใจจะถูกเลือกโดยอิสระจากคิวรอส่งก็ตาม ${\displaystyle A_{n}^{(c)}(t)}$${\displaystyle \mu _{nb}^{(c)}(t)}$${\displaystyle \mu _{nb}^{(c)}(t)}$${\displaystyle \sum _{a=1}^{N}\mu _{an}^{(c)}(t)}$${\displaystyle \mu _{ab}^{(c)}(t)}$

ถือว่าสำหรับช่องt ทั้งหมด และทั้งหมดเนื่องจากไม่มีคิวใดเก็บข้อมูลที่มุ่งไปยังตัวมันเอง ${\displaystyle Q_{c}^{(c)}(t)=0}$${\displaystyle c\in \{1,\ldots ,N\}}$

กำหนดให้เป็นเมทริกซ์ของปริมาณงานค้างในคิวปัจจุบัน กำหนดฟังก์ชันที่ไม่เป็นลบต่อไปนี้ ซึ่งเรียกว่าฟังก์ชัน Lyapunov : ${\displaystyle {\boldsymbol {Q}}(t)=(Q_{n}^{(c)}(t))}$

${\displaystyle L(t)={\frac {1}{2}}\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)^{2}}$

นี่คือผลรวมของกำลังสองของคิวค้าง (คูณด้วย 1/2 เพื่อความสะดวกในการ วิเคราะห์ ในภายหลังเท่านั้น) ผลรวมข้างต้นเหมือนกับการรวมค่าnและc ทั้งหมด โดยที่เพราะสำหรับทุกและทุกช่องt${\displaystyle n\neq c}$${\displaystyle Q_{c}^{(c)}(t)=0}$${\displaystyle c\in \{1,\ldots ,N\}}$

นิยาม ของค่าเบี่ยงเบน Lyapunov แบบมีเงื่อนไข มีดังนี้: ${\displaystyle \Delta (t)}$

${\displaystyle \Delta (t)=E\left[L(t+1)-L(t)\mid {\boldsymbol {Q}}(t)\right]}$

โปรดทราบว่าอสมการต่อไปนี้เป็นจริงสำหรับทุกค่า, , : ${\displaystyle q\geq 0}$${\displaystyle a\geq 0}$${\displaystyle b\geq 0}$

${\displaystyle (\max[q-b,0]+a)^{2}\leq q^{2}+b^{2}+a^{2}+2q(a-b)}$

โดยการยกกำลังสองสมการการอัปเดตคิว (สมการ (6)) และใช้ความไม่เท่าเทียมกันข้างต้น ก็ไม่ยากที่จะแสดงให้เห็นว่าสำหรับช่องt ทั้งหมด และภายใต้อัลกอริทึมใด ๆ สำหรับการเลือกตัวแปรการส่งและการกำหนดเส้นทาง และ: ^{[ 3 ]}${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

${\displaystyle {\text{(Eq. 7)}}\qquad \Delta (t)\leq B+\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)E\left[\lambda _{n}^{(c)}(t)+\sum _{a=1}^{N}\mu _{an}^{(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)|{\boldsymbol {Q}}(t)\right]}$

โดยที่Bเป็นค่าคงที่จำกัดซึ่งขึ้นอยู่กับโมเมนต์ที่สองของการมาถึงและโมเมนต์ที่สองสูงสุดที่เป็นไปได้ของอัตราการส่งผ่าน

อัลกอริทึมแรงดันย้อนกลับได้รับการออกแบบมาเพื่อสังเกตและ S ( t ) ในแต่ละช่องtและเลือกและเพื่อลดด้านขวาของขอบเขตการเลื่อนสมการ (7) เนื่องจากB เป็นค่าคงที่และเป็นค่าคงที่ ดังนั้นสิ่งนี้จึงเท่ากับการเพิ่มค่าสูงสุด: ${\displaystyle {\boldsymbol {Q}}(t)}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$${\displaystyle \lambda _{n}^{(c)}}$

${\displaystyle E\left[\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)\left[\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)-\sum _{a=1}^{N}\mu _{an}^{(c)}(t)\right]|{\boldsymbol {Q}}(t)\right]}$

โดยที่ผลรวมจำกัดได้ถูกผลักดันผ่านความคาดหวังเพื่อส่องสว่างการตัดสินใจที่เพิ่มสูงสุด ตามหลักการของการเพิ่มความคาดหวังอย่างฉวยโอกาสความคาดหวังข้างต้นจะถูกเพิ่มสูงสุดโดยการเพิ่มฟังก์ชันภายในให้สูงสุด (โดยพิจารณาจากค่าที่สังเกตได้) ดังนั้น จึงเลือกและ ภายใต้ข้อจำกัดสมการ (3)-(5) เพื่อเพิ่มค่าให้สูงสุด: ${\displaystyle {\boldsymbol {Q}}(t)}$${\displaystyle S(t)}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

${\displaystyle \sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)\left[\sum _{b=1}^{N}\mu _{nb}^{(c)}(t)-\sum _{a=1}^{N}\mu _{an}^{(c)}(t)\right]}$

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

${\displaystyle \sum _{a=1}^{N}\sum _{b=1}^{N}\sum _{c=1}^{N}\mu _{ab}^{(c)}(t)[Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)]}$

น้ำหนัก ดังกล่าวเรียกว่า ผลต่างปริมาณสินค้าคงค้างปัจจุบันของสินค้าcระหว่างโหนดaและbแนวคิดคือการเลือกตัวแปรการตัดสินใจเพื่อให้ผลรวมถ่วงน้ำหนักข้างต้นมีค่าสูงสุด โดยที่น้ำหนักคือผลต่างปริมาณสินค้าคงค้าง โดยทั่วไปแล้ว หมายความว่าควรจัดสรรอัตราที่สูงกว่าในทิศทางที่มีผลต่างปริมาณสินค้าคงค้างสูงกว่า ${\displaystyle Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

เห็นได้ชัดว่าควรเลือก เมื่อใดก็ตามที่เหมาะสม นอกจากนี้สำหรับลิงก์เฉพาะหนึ่งลิงก์ การแสดงให้เห็นว่า การเลือกที่เหมาะสมที่สุดภายใต้สมการ (3)-(5) นั้นกำหนดได้ดังนี้: ขั้นแรกให้หาสินค้า ที่ ทำให้ ค่า backlog ที่แตกต่างกันสูงสุดสำหรับลิงก์ ( a , b ) หากค่า backlog ที่แตกต่างกันสูงสุดเป็นค่าลบสำหรับลิงก์ ( a , b ) ให้กำหนดให้กับสินค้าทั้งหมด ในลิงก์ ( a , b ) มิฉะนั้น ให้จัดสรรอัตราลิงก์เต็มจำนวนให้กับสินค้าและอัตราศูนย์ให้กับสินค้าอื่นๆ ทั้งหมดในลิงก์นี้ ด้วยการเลือกนี้ จึงสรุปได้ว่า: ${\displaystyle \mu _{ab}^{(c)}(t)=0}$${\displaystyle Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)<0}$${\displaystyle \mu _{ab}(t)}$${\displaystyle (a,b)}$${\displaystyle \mu _{ab}^{(c)}(t)}$${\displaystyle c_{ab}^{opt}(t)\in \{1,\ldots ,N\}}$${\displaystyle \mu _{ab}^{(c)}(t)=0}$${\displaystyle c\in \{1,\ldots ,N\}}$${\displaystyle \mu _{ab}(t)}$${\displaystyle c_{ab}^{opt}(t)}$

${\displaystyle \sum _{c=1}^{N}\mu _{ab}^{(c)}(t)[Q_{a}^{(c)}(t)-Q_{b}^{(c)}(t)]=\mu _{ab}(t)W_{ab}(t)}$

โดยที่ค่าความคลาดเคลื่อนของสินค้าที่เหมาะสมที่สุดสำหรับลิงก์ ( a , b ) ในช่องt (สูงสุดที่ 0) คือ เท่าใด${\displaystyle W_{ab}(t)}$

${\displaystyle W_{ab}(t)=\max[Q_{a}^{(c_{ab}^{opt}(t))}(t)-Q_{b}^{(c_{ab}^{opt}(t))}(t),0]}$

เหลือเพียงแค่เลือกเท่านั้นซึ่งทำได้โดยการแก้โจทย์ต่อไปนี้: ${\displaystyle (\mu _{ab}(t))\in \Gamma _{S(t)}}$

${\displaystyle \mathrm {Maximize:} \sum _{a=1}^{N}\sum _{b=1}^{N}\mu _{ab}(t)W_{ab}(t)}$

${\displaystyle \mathrm {Subjectto:} (\mu _{ab}(t))\in \Gamma _{S(t)}}$

ปัญหาข้างต้นเหมือนกับปัญหาน้ำหนักสูงสุดในสมการ (1)-(2) อัลกอริทึมแรงดันย้อนกลับใช้การตัดสินใจน้ำหนักสูงสุดสำหรับและจากนั้นเลือกตัวแปรการกำหนดเส้นทางผ่านปริมาณงานค้างที่แตกต่างกันสูงสุดตามที่อธิบายไว้ข้างต้น ${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

คุณสมบัติที่โดดเด่นอย่างหนึ่งของอัลกอริทึมแรงดันย้อนกลับคือ มันจะทำงานอย่างโลภในทุกช่วงเวลาtโดยอาศัยเพียงสถานะโทโพโลยีที่สังเกตได้S ( t ) และปริมาณคิวค้างสำหรับช่วงเวลานั้นเท่านั้น ดังนั้นจึงไม่จำเป็นต้องทราบอัตราการมาถึงหรือความน่าจะเป็นของสถานะโทโพโลยี ${\displaystyle {\boldsymbol {Q}}(t)}$${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle \pi _{S}=Pr[S(t)=S]}$

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

ให้เป็นเมทริกซ์ของการมาถึงจากภายนอกในช่วงเวลาtสมมติว่าเมทริกซ์นี้เป็นตัวแปรสุ่มอิสระและมีการกระจายเหมือนกัน (iid) ในช่วงเวลาต่างๆ โดยมีโมเมนต์อันดับสองจำกัด และมีค่าเฉลี่ยดังนี้: ${\displaystyle (A_{n}^{(c)}(t))}$

${\displaystyle \lambda _{n}^{(c)}=E\left[A_{n}^{(c)}(t)\right]}$

ถือว่าสำหรับทุกค่าเนื่องจากไม่มีข้อมูลใดมาถึงซึ่งมีจุดหมายปลายทางเป็นของตัวเอง ดังนั้น เมทริกซ์ของอัตราการมาถึงจึงเป็นเมทริกซ์ของจำนวนจริงที่ไม่เป็นลบ โดยมีค่าเป็นศูนย์บนแนวทแยงมุม ${\displaystyle \lambda _{c}^{(c)}=0}$${\displaystyle c\in \{1,\ldots ,N\}}$${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle N\times N}$

สมมติว่าสถานะโทโพโลยีS ( t ) เป็นแบบ iid เหนือสล็อตด้วยความน่าจะเป็น (ถ้าS ( t ) มีค่าอยู่ในเซตเวกเตอร์อนันต์ที่นับไม่ได้ซึ่งมีค่าเป็นจำนวนจริง แสดงว่าเป็นการแจกแจงความน่าจะเป็น ไม่ใช่ฟังก์ชันมวลความน่าจะเป็น ) อัลกอริทึมทั่วไปสำหรับเครือข่ายจะสังเกตS ( t ) ในแต่ละสล็อตtและเลือกอัตราการส่งข้อมูลและตัวแปรการกำหนดเส้นทางตามข้อจำกัดในสมการ (3)-(5) ขอบเขตความจุของเครือข่ายคือการปิดของเซตของเมทริกซ์อัตราการมาถึงทั้งหมดซึ่งมีอัลกอริทึมที่ทำให้เครือข่ายมีเสถียรภาพ ความเสถียรของคิวทั้งหมดหมายความว่าอัตราการรับส่งข้อมูลทั้งหมดเข้าสู่เครือข่ายเท่ากับอัตราข้อมูลทั้งหมดที่ส่งไปยังปลายทาง สามารถแสดงได้ว่าสำหรับเมทริกซ์อัตราการมาถึงใดๆในพื้นที่ความจุจะมีอัลกอริทึมแบบคงที่และสุ่มที่เลือกตัวแปรการตัดสินใจและ ช่อง t ทุกช่องโดยอาศัยS ( t ) เท่านั้น (และด้วยเหตุนี้จึงเป็นอิสระจากคิวค้าง) ซึ่งให้ผลลัพธ์ดังต่อไปนี้สำหรับทุก: ^{[ 9 ] [ 13 ]}${\displaystyle \pi _{S}=Pr[S(t)=S]}$${\displaystyle \pi _{S}}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$${\displaystyle \Lambda }$${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle \Lambda }$${\displaystyle (\mu _{ab}^{*}(t))}$${\displaystyle (\mu _{ab}^{*(c)}(t))}$${\displaystyle n\neq c}$

${\displaystyle {\text{(Eq. 8)}}\qquad E\left[\lambda _{n}^{(c)}+\sum _{a=1}^{N}\mu _{an}^{*(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{*(c)}(t)\right]\leq 0}$

อัลกอริทึม แบบอยู่กับที่และสุ่มที่ตัดสินใจโดยอาศัยS ( t ) เท่านั้น เรียกว่าอัลกอริทึมแบบ S-only โดยทั่วไปแล้ว การสมมติว่า t อยู่ภายใน t จะเป็นประโยชน์ ดังนั้นจึงมี t ที่ ทำให้ t = t(t) โดยที่ t(t) มี ค่าเป็น 1 ถ้า t( t) = t(t) และเป็น 0 ถ้าไม่ใช่ t(t) = t(t) ในกรณีนั้น จะมี อัลกอริทึมแบบ S -only ที่ให้ผลลัพธ์ต่อไปนี้สำหรับทุก t( t) = t(t ) : ${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle \Lambda }$${\displaystyle \epsilon >0}$${\displaystyle (\lambda _{n}^{(c)}+\epsilon 1_{n}^{(c)})\in \Lambda }$${\displaystyle 1_{n}^{(c)}}$${\displaystyle n\neq c}$${\displaystyle n\neq c}$

${\displaystyle {\text{(Eq. 9)}}\qquad E\left[\lambda _{n}^{(c)}+\sum _{a=1}^{N}\mu _{an}^{*(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{*(c)}(t)\right]\leq -\epsilon }$

ตามข้อกำหนดทางเทคนิค ถือว่าโมเมนต์ที่สองของอัตราการส่งข้อมูลมีค่าจำกัดภายใต้อัลกอริทึมใดๆ สำหรับการเลือกอัตราเหล่านี้ ซึ่งเป็นจริงโดยปริยายหากมีอัตราสูงสุดที่มีค่าจำกัด ${\displaystyle \mu _{ab}(t)}$${\displaystyle \mu _{max}}$

เนื่องจากอัลกอริธึมแรงดันย้อนกลับสังเกตและS ( t ) ในแต่ละช่องtและเลือกการตัดสินใจเพื่อลดด้านขวาของขอบเขตการเลื่อนสมการ (7) ให้เหลือน้อยที่สุด เราจึงได้ว่า: ${\displaystyle {\boldsymbol {Q}}(t)}$${\displaystyle (\mu _{ab}(t))}$${\displaystyle (\mu _{ab}^{(c)}(t))}$

${\displaystyle {\text{(Eq. 10)}}\qquad \Delta (t)\leq B+\sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)E\left[\lambda _{n}^{(c)}(t)+\sum _{a=1}^{N}\mu _{an}^{*(c)}(t)-\sum _{b=1}^{N}\mu _{nb}^{*(c)}(t)|{\boldsymbol {Q}}(t)\right]}$

โดยที่และ คือการตัดสินใจทางเลือกอื่นใดที่ตรงตามสมการ (3)-(5) รวมถึงการตัดสินใจแบบสุ่ม ${\displaystyle (\mu _{ab}^{*}(t))}$${\displaystyle (\mu _{ab}^{*(c)}(t))}$

ตอนนี้สมมติว่า. จากนั้นจะมี อัลกอริทึม S -only ที่สอดคล้องกับสมการ (8) การแทนค่านี้ลงในด้านขวาของสมการ (10) และสังเกตว่าค่าคาดหวังแบบมีเงื่อนไขที่กำหนด ภายใต้อัลกอริทึม S -only นี้เหมือนกับค่าคาดหวังแบบไม่มีเงื่อนไข (เนื่องจากS ( t ) เป็น iid เหนือสล็อต และ อัลกอริทึม S -only ไม่ขึ้นอยู่กับปริมาณคิวค้างในปัจจุบัน) จะได้ผลลัพธ์ดังนี้: ${\displaystyle (\lambda _{n}^{(c)})\in \Lambda }$${\displaystyle {\boldsymbol {Q}}(t)}$

${\displaystyle \Delta (t)\leq B\,}$

ดังนั้น การเคลื่อนตัวของฟังก์ชัน Lyapunov กำลังสองจึงน้อยกว่าหรือเท่ากับค่าคงที่Bสำหรับช่องt ทั้งหมด ข้อเท็จจริงนี้ ร่วมกับสมมติฐานที่ว่าการมาถึงของคิวมีโมเมนต์ที่สองที่จำกัด บ่งบอกถึงสิ่งต่อไปนี้สำหรับคิวเครือข่ายทั้งหมด: ^{[ 16 ]}

${\displaystyle \lim _{t\rightarrow \infty }{\frac {Q_{n}^{(c)}(t)}{t}}=0{\text{ with probability 1}}}$

เพื่อให้เข้าใจขนาดคิวเฉลี่ยได้ดียิ่งขึ้น เราสามารถสมมติว่าอัตราการมาถึงอยู่ภายในดังนั้นจึงมีค่าที่ทำให้สมการ (9) เป็นจริงสำหรับ อัลกอริธึม S -only ทางเลือกบางอย่าง การแทนสมการ (9) ลงในด้านขวาของสมการ (10) จะได้ผลลัพธ์ดังนี้: ${\displaystyle (\lambda _{n}^{(c)})}$${\displaystyle \Lambda }$${\displaystyle \epsilon >0}$

${\displaystyle \Delta (t)\leq B-\epsilon \sum _{n=1}^{N}\sum _{c=1}^{N}Q_{n}^{(c)}(t)}$

ซึ่งจะได้รับทันที (ดู^{[ 3 ] [ 13 ]} ):

${\displaystyle \limsup _{t\rightarrow \infty }{\frac {1}{t}}\sum _{\tau =0}^{t-1}\sum _{n=1}^{N}\sum _{c=1}^{N}E\left[Q_{n}^{(c)}(\tau )\right]\leq {\frac {B}{\epsilon }}}$

ขอบเขตขนาดคิวเฉลี่ยนี้จะเพิ่มขึ้นเมื่อระยะห่างจากขอบเขตของพื้นที่ความจุเข้าใกล้ศูนย์ นี่คือประสิทธิภาพเชิงคุณภาพเดียวกันกับคิว M/M/1 เดี่ยวที่มีอัตราการมาถึง และอัตราการให้บริการโดยที่ขนาดคิวเฉลี่ยเป็นสัดส่วนกับโดย ที่${\displaystyle \epsilon }$${\displaystyle \Lambda }$${\displaystyle \lambda }$${\displaystyle \mu }$${\displaystyle 1/\epsilon }$${\displaystyle \epsilon =\mu -\lambda }$

การวิเคราะห์ข้างต้นถือว่ามีคุณสมบัติ iid เพื่อความง่าย อย่างไรก็ตาม สามารถแสดงให้เห็นได้ว่าอัลกอริทึมแรงดันย้อนกลับแบบเดียวกันทำงานได้อย่างแข็งแกร่งในสถานการณ์ที่ไม่ใช่ iid เมื่อกระบวนการมาถึงและสถานะโทโพโลยีเป็นแบบเออร์โกดิก แต่ไม่จำเป็นต้องเป็น iid แรงดันย้อนกลับยังคงทำให้ระบบมีเสถียรภาพเมื่อใดก็ตามที่[ ^{9 ] โดย} ทั่วไปแล้ว การใช้ แนวทาง การจัดตารางเวลาแบบสากลได้แสดงให้เห็นว่ามีคุณสมบัติเสถียรภาพและความเหมาะสมที่สุดสำหรับเส้นทางตัวอย่างใดๆ (อาจไม่ใช่แบบเออร์โกดิก) ^{[ 17 ]}${\displaystyle (\lambda _{n}^{(c)})\in \Lambda }$

แรงดันย้อนกลับได้รับการพิสูจน์แล้วว่าทำงานร่วมกับการควบคุมการไหลผ่านเทคนิคการเลื่อนบวกค่าปรับ^{[ 10 ] [ 11 ] [ 3 ]} เทคนิคนี้จะเพิ่มผลรวมของการเลื่อนและนิพจน์ค่าปรับแบบถ่วงน้ำหนักให้สูงสุดอย่างโลภ ค่าปรับจะถูกถ่วงน้ำหนักด้วยพารามิเตอร์Vที่กำหนดการแลกเปลี่ยนประสิทธิภาพ เทคนิคนี้รับประกันว่าประโยชน์ด้านปริมาณงานจะอยู่ภายในO (1/ V ) ของค่าที่เหมาะสมที่สุด ในขณะที่ความล่าช้าเฉลี่ยคือO ( V ) ดังนั้น ประโยชน์สามารถถูกผลักดันให้เข้าใกล้ค่าที่เหมาะสมที่สุดได้ตามอำเภอใจ โดยมีการแลกเปลี่ยนที่สอดคล้องกันในความล่าช้าเฉลี่ย คุณสมบัติที่คล้ายกันนี้สามารถแสดงให้เห็นได้สำหรับการลดพลังงานเฉลี่ยให้เหลือน้อยที่สุด^{[ 18 ]} และสำหรับการเพิ่มประสิทธิภาพคุณลักษณะเครือข่ายทั่วไปมากขึ้น^{[ 13 ]}

อัลกอริทึมทางเลือกสำหรับการรักษาเสถียรภาพของคิวในขณะที่เพิ่มประโยชน์ใช้สอยของเครือข่ายให้สูงสุดได้รับการพัฒนาโดยใช้การวิเคราะห์แบบจำลองของไหล^{[ 12 ]}การวิเคราะห์ของไหลร่วมและการวิเคราะห์ตัวคูณลากรางจ์^{[ 19 ]}การเพิ่มประสิทธิภาพแบบนูน^{[ 20 ]}และการไล่ระดับแบบสุ่ม^{[ 21 ]}แนวทางเหล่านี้ไม่ได้ให้ ผลลัพธ์ด้านประโยชน์ใช้สอย-ความล่าช้า O (1/ V ), O ( V )

• เอโอดีวี
• การกำหนดเส้นทางแรงดันย้อนกลับแบบหลากหลาย (DIVBAR) ^{[ 1 ]}
• การเบี่ยงเบนบวกค่าปรับ
• เอ็กซ์ออร์
• การกำหนดเส้นทางตามภูมิศาสตร์
• รายชื่อโปรโตคอลการกำหนดเส้นทางแบบเฉพาะกิจ
• การปรับให้เหมาะสมของ Lyapunov

• L. Tassiulas และ A. Ephremides, "คุณสมบัติความเสถียรของระบบคิวที่มีข้อจำกัดและนโยบายการจัดตารางเวลาเพื่อปริมาณงานสูงสุดในเครือข่ายวิทยุแบบหลายฮอป" IEEE Transactions on Automatic Control , เล่มที่ 37, ฉบับที่ 12, หน้า 1936–1948, ธันวาคม 1992
• L. Georgiadis, MJ Neely และ L. Tassiulas, "การจัดสรรทรัพยากรและการควบคุมข้ามเลเยอร์ในเครือข่ายไร้สาย" Foundations and Trends in Networking , เล่ม 1, ฉบับที่ 1, หน้า 1–149, 2006
• MJ Neely. การเพิ่มประสิทธิภาพเครือข่ายแบบสุ่มด้วยการประยุกต์ใช้กับระบบการสื่อสารและระบบคิว , Morgan & Claypool, 2010.