準可逆性(quasi-reversibility)
準可逆性是排隊站的一種結構性質,它解釋了為何乘積形式網路(如傑克森網路)擁有美妙的分解平穩分配。由弗蘭克·凱利(Frank Kelly)所發展,它是針對具有多顧客類別與路由的網路而對完全可逆性的弱化:一個站在時間上倒著看不必相同,但其到達與離開流必須具有特定的馬可夫結構。它是一大類乘積形式結果背後的統一原理。
一個佇列,視為帶有各類別之標記到達與離開事件的馬可夫過程,若在任何固定時刻其狀態與各類別未來的到達時間獨立、且與各類別過去的離開時間獨立,則為準可逆——等價地,到達過程與(時間反轉後的)離開過程皆為速率不依賴狀態的卜瓦松過程。關鍵收穫:對一個餵以卜瓦松輸入的準可逆站,每一類別的離開過程亦為卜瓦松(這是伯克定理的抽象形式),故準可逆站可串接起來,卜瓦松進/卜瓦松出的性質得以傳播。當你組裝一個準可逆站的網路時,全域平穩分配分解為各站之乘積,每站承載它在孤立時所具有的平穩律。準可逆性由完全可逆性(細緻平衡)所蘊含,但嚴格更弱;它依賴一種「部分平衡」條件,即流量逐類別平衡而非逐邊平衡。
準可逆性之所以重要,是因為它大幅擴展了可解網路的世界:多類別佇列、某些處理器共享與對稱服務規則、以及 BCMP 網路(Baskett-Chandy-Muntz-Palacios)皆適用,遠超單類別 M/M 傑克森設定。誠實的告誡:準可逆性是真正的假設,並非天上掉下的午餐。它釘定了允許的服務規則與類別結構;許多自然的排隊特徵——非指數服務的先到先服務、製造相關性的狀態相依路由、帶溢出的阻塞與有限緩衝——都會破壞準可逆性,此時乘積形式失效,網路必須以其他(通常是數值)方法求解。
M/M/1 佇列是準可逆的:由伯克定理,其離開過程是卜瓦松(lambda),與其卜瓦松到達同速率,且在任何時刻佇列長度與未來到達及過去離開獨立。這正是讓你能把 M/M/1 站串成具乘積形式平衡的傑克森網路的性質。
準可逆性=卜瓦松進/卜瓦松出加上恰當的獨立性;串接這類站即得乘積形式。
準可逆性嚴格弱於可逆性(細緻平衡),但仍是真正的假設:它約束了服務規則與類別結構。非指數服務的先到先服務、製造相關性的狀態相依路由、以及有限緩衝阻塞通常都會破壞它,此時乘積形式不成立。