Новые методы, алгоритмы и теоретические оценки работы алгоритмов в дизайне сетевых элементовNew methods, algorithms, and theoretical guarantees for algorithms in network element design

Широкий спектр услуг, работающих на экспоненциально растущем числе взаимосвязанных сетевых устройств, делает сетевые операции более сложными, чем когда-­либо. Новое сложное поведение в масштабах сети, разнообразие желаемых целей, а также повышение уровней масштаби­руемости требуют, чтобы сетевая инфраструктура была более интеллектуальной, выразительной и надежной. Обычно эти требования приводят к значительной сложности эксплуатации и увеличению стоимости сетевой инфраструктуры. Уменьшение управляемого состояния сети за счет лучшего использования дорогостоящей сетевой инфраструктуры (эффективность) без ущерба для гибкости (выразительность) может преодолеть новые уровни операционной сложности и ограничений масштабируемости; поиск правильного баланса между ними и поиск способов эффективного представления управляемого состояния сети — это серьезные проблемы, требующие фундаментального понимания на основе аналитических наблюдений и теоретических исследований. Последние разработки в области программно-­определяемых сетей (software­defined networking, SDN) частично улучшают выразительность, добавляя новые уровни программируемости, но, к сожалению, не дают окончательного ответа в области фундаментального компромисса между выразительностью и операционной сложностью. В итоге возникает потребность в новых подходах к проектированию сетей, которые требуют эффективных реализаций управляемого состояния в сетевых элементах. В этой диссертации мы рассматриваем эффективные представления управляемого состояния одного сетевого элемента и рассматриваем два фундаментальных вопроса: как эффективно представлять программы обработки пакетов, решая задачу поиска фундаментального компромисса между эффективностью и выразительностью и как использовать существующие сетевые ресурсы в условиях наличия локальных ограничений, экспоненциально растущего числа взаимосвязанных устройств и увеличения степени детализации операций.