輻輳制御
輻輳制御の現代的理論は、Frank Kelly が先駆者である。彼は、ミクロ経済学と凸最適化理論を応用して、個々が自分のレートを制御することで最適なネットワーク転送レートを達成できることを示した。
最適な転送レートの例として、Max-Min公平性や Kelly が示唆した比例公平性があるが、他にもいろいろなものが考えられる。
最適転送レートの割り当てを数式で表すと次のようになる。フロー i {\displaystyle i} の転送レートを x i {\displaystyle x_{i}} 、リンク l {\displaystyle l} の容量を C l {\displaystyle C_{l}} とし、フロー i {\displaystyle i} がリンク l {\displaystyle l} を使う場合 r l i {\displaystyle r_{li}} を 1 とし、そうでなければ 0 とする。 x {\displaystyle x} 、 c {\displaystyle c} 、 R {\displaystyle R} を対応するベクトルおよび行列とする。 U ( x ) {\displaystyle U(x)} が増大する厳密な凸関数だとする。この関数を効用と呼び、あるユーザーがレート x {\displaystyle x} で送信したときに得られる利益を数値化したものである。