Алгоритмы прямой маршрутизации: различия между версиями

В главе 5 в [6] рассматривалась также дополнительная задача, касающаяся объема буферизации, необходимого для обеспечения малого времени маршрутизации. Было показано, что существует задача прямого планирования, для которой каждому прямому алгоритму требуется время маршрутизации <math>\Omega (C \cdot  D) \; </math>; в то же время <math>C + D = \Theta (\sqrt{C \cdot D} = o(C \cdot D)</math>. Если буферизация пакетов допускается, то существуют известные алгоритмы планирования пакетов ([11, 12]) с временем маршрутизации, очень близким к оптимальному <math>O(C + D) \; </math>. В [6] было показано, что в случае конкретной задачи планирования пакетов для того, чтобы превратить прямой план вброса с временем маршрутизации <math>O(C \cdot D) \; </math> в план пакетов с временем маршрутизации <math>O(C + D) \; </math>, необходимо выполнять буферизацию пакетов в узлах сети в сумме <math>\Omega (N^{4/3}) \; </math> раз. Здесь буферизация пакета заключается в хранении пакета в промежуточном буферном узле на протяжении одного временного такта; N – количество пакетов.