Топология сети, алгебра и комбинаторика
Вопрос из книги Таненбаума про компьютерные сети к главе 1 «Введение», цитата:
8. Пять маршрутизаторов необходимо соединить в подсеть с двухточечным соединением. Каждые два маршрутизатора разработчики могут соединить высокоскоростной, среднескоростной, низкоскоростной линией или никак не соединять. Предположим, компьютеру требуется 100 мс для моделирования и анализа каждой топологии. Сколько компьютерного времени понадобится для выбора варианта, лучше всего соответствующего ожидаемой нагрузке?
В математике есть такое понятие, как «граф» (ссылка) - это множество вершин (точек) и ребер (соединений между парами вершин). Топология сети (ссылка) - это конфигурация графа, вершинам которого соответствуют конечные узлы сети (компьютеры) и коммуникационное оборудование (маршрутизаторы), а ребрам - соединения (линии) между вершинами.
В реальной жизни линия сети характеризуется еще и своей длиной (особенно это важно в проводных сетях - для прокладки линии необходимо знать, сколько провода (кабеля) нужно закупить). Но в вышеуказанном тексте вопроса длине линии значения не придается.
У нас есть пять маршрутизаторов (вершин графа), между которыми требуется проводить линии (ребра графа). Для работы с графами и множествами в математике существует раздел под названием «комбинаторика» (ссылка). Комбинаторика является частью дискретной математики (это раздел математики, имеющий дело с конечным числом значений, в отличие от непрерывной математики). Как следует из названия, комбинаторика имеет дело с комбинациями значений (объектов).
Сначала посчитаем, сколько линий можно провести между каждыми двумя вершинами (маршрутизаторами) нашей сети. Конечно, это можно сделать прямым перебором на рисунке. Ниже я нарисовал сеть, в которой обозначил маршрутизаторы точками А, Б, В, Г и Д. Все точки я попарно соединил линиями:
При подсчете прямым перебором получается 10 линий.
Но, в принципе, можно попробовать найти формулу для любого количества вершин. Рассмотрим наш случай с пятью вершинами. Начнем проводить линии из точки А. Из этой точки мы сможем провести 4 линии: АБ, АВ, АГ и АД. Теперь проведем линии из точки Б. Из этой точки мы сможем теперь провести лишь три линии: БВ, БГ, БД (линия БА уже проведена ранее под названием АБ). Теперь проведем линии из точки В. Из этой точки мы сможем теперь провести лишь две линии: ВГ и ВД (линии ВА и ВБ уже проведены ранее под названиями АВ и БВ). Теперь проведем линии из точки Г. Из этой точки мы сможем теперь провести лишь одну линию: ГД (линии ГА, ГБ и ГВ уже проведены ранее). Из оставшейся точки Д мы не сможем теперь провести ни одной линии (линии ДА, ДБ, ДВ и ДГ проведены ранее).
То есть при количестве вершин в 5 штук для нахождения числа линий между этими вершинами нам нужно последовательно сложить числа 4, 3, 2, 1 и 0. Или наоборот: 0, 1, 2, 3 и 4. Это арифметическая прогрессия (ссылка) с шагом 1. (Арифметическую прогрессию изучают в школьном курсе алгебры в 9 классе). Сумма первых N членов арифметической прогрессии вычисляется по следующей формуле:
Сумма = (а1 + аN) * N / 2,
где а1 - первый член прогрессии, аN - N-й член прогрессии.
В нашем случае а1 = 0, а аN = N - 1, при этом получается следующая формула:
Сумма = (N - 1) * N / 2
Проверим.
Для одной вершины: (1 - 1) * 1 / 2 = 0 (точка)
Для двух вершин: (2 - 1) * 2 / 2 = 1 (линия)
Для трех вершин: (3 - 1) * 3 / 2 = 3 (треугольник)
Для четырех вершин: (4 - 1) * 4 / 2 = 6 (прямоугольник)
Для пяти вершин (наш случай): (5 - 1) * 5 / 2 = 10
Для шести вершин: (6 - 1) * 6 / 2 = 15 и так далее.
Теперь подсчитаем общее количество возможных топологий сети при указанных в тексте вопроса условиях. Итак, при 5 маршрутизаторах у нас может быть 10 линий, каждая из которых может быть одного из 4-х видов: высокоскоростная, среднескоростная, низкоскоростная и линии вообще может не быть.
Как я понимаю, подразумевается, что при моделировании и анализе топологии указанной сети компьютер должен перебрать все варианты топологии сети, отбрасывая при этом те, которые не будут работать вообще и те, которые будут работать, но окажутся неэффективными.
Как подсчитать это количество? Для этого можно использовать одно из основных правил комбинаторики - правило умножения (ссылка). Первую линию можно сделать одного из перечисленных выше 4-х видов. При каждом из этих 4-х выборов вида линии следующую линию тоже можно сделать одного из 4-х видов. То есть на каждом следующем шаге дерева выборов количество его веточек умножается на 4:
Получается, что общее количество вариантов топологии сети будет равно произведению 4 * 4 * 4 * ... и так далее, то есть равно 410. В терминах комбинаторики это называется «нахождением количества размещений с повторениями из 4 по 10» (ссылка).
Таким образом, компьютер при моделировании и анализе топологии данной сети должен перебрать 410 вариантов, затратив на каждый вариант 100 мс. А это значит, что всего компьютер затратит на эту работу следующее количество времени:
410 * 100 мс = 1 048 576 * 0,1 с = 104 857,6 с = 29,127 ч
Это и есть ответ.
В заключение отмечу, что в этот миллион с хвостиком вариантов входят и «нерабочие» варианты топологии сети. Например, вариант вообще без линий, или варианты, при которых какие-то из маршрутизаторов окажутся не присоединенными к сети, или варианты, при которых будут существовать несколько не соединенных друг с другом частей сети. «Рабочими» вариантами топологии сети я считаю такие варианты, при которых от одного маршрутизатора по линиям можно добраться до любого другого маршрутизатора в сети, даже если и не напрямую, а через один или несколько промежуточных маршрутизаторов. В нашем случае предполагается, что компьютер тупо перебирает все варианты, откидывая нерабочие. Не знаю, можно ли этот прямой перебор как-то оптимизировать, чтобы уменьшить время на отбор нужной топологии.
8. Пять маршрутизаторов необходимо соединить в подсеть с двухточечным соединением. Каждые два маршрутизатора разработчики могут соединить высокоскоростной, среднескоростной, низкоскоростной линией или никак не соединять. Предположим, компьютеру требуется 100 мс для моделирования и анализа каждой топологии. Сколько компьютерного времени понадобится для выбора варианта, лучше всего соответствующего ожидаемой нагрузке?
В математике есть такое понятие, как «граф» (ссылка) - это множество вершин (точек) и ребер (соединений между парами вершин). Топология сети (ссылка) - это конфигурация графа, вершинам которого соответствуют конечные узлы сети (компьютеры) и коммуникационное оборудование (маршрутизаторы), а ребрам - соединения (линии) между вершинами.
В реальной жизни линия сети характеризуется еще и своей длиной (особенно это важно в проводных сетях - для прокладки линии необходимо знать, сколько провода (кабеля) нужно закупить). Но в вышеуказанном тексте вопроса длине линии значения не придается.
У нас есть пять маршрутизаторов (вершин графа), между которыми требуется проводить линии (ребра графа). Для работы с графами и множествами в математике существует раздел под названием «комбинаторика» (ссылка). Комбинаторика является частью дискретной математики (это раздел математики, имеющий дело с конечным числом значений, в отличие от непрерывной математики). Как следует из названия, комбинаторика имеет дело с комбинациями значений (объектов).
Сначала посчитаем, сколько линий можно провести между каждыми двумя вершинами (маршрутизаторами) нашей сети. Конечно, это можно сделать прямым перебором на рисунке. Ниже я нарисовал сеть, в которой обозначил маршрутизаторы точками А, Б, В, Г и Д. Все точки я попарно соединил линиями:
При подсчете прямым перебором получается 10 линий.
Но, в принципе, можно попробовать найти формулу для любого количества вершин. Рассмотрим наш случай с пятью вершинами. Начнем проводить линии из точки А. Из этой точки мы сможем провести 4 линии: АБ, АВ, АГ и АД. Теперь проведем линии из точки Б. Из этой точки мы сможем теперь провести лишь три линии: БВ, БГ, БД (линия БА уже проведена ранее под названием АБ). Теперь проведем линии из точки В. Из этой точки мы сможем теперь провести лишь две линии: ВГ и ВД (линии ВА и ВБ уже проведены ранее под названиями АВ и БВ). Теперь проведем линии из точки Г. Из этой точки мы сможем теперь провести лишь одну линию: ГД (линии ГА, ГБ и ГВ уже проведены ранее). Из оставшейся точки Д мы не сможем теперь провести ни одной линии (линии ДА, ДБ, ДВ и ДГ проведены ранее).
То есть при количестве вершин в 5 штук для нахождения числа линий между этими вершинами нам нужно последовательно сложить числа 4, 3, 2, 1 и 0. Или наоборот: 0, 1, 2, 3 и 4. Это арифметическая прогрессия (ссылка) с шагом 1. (Арифметическую прогрессию изучают в школьном курсе алгебры в 9 классе). Сумма первых N членов арифметической прогрессии вычисляется по следующей формуле:
Сумма = (а1 + аN) * N / 2,
где а1 - первый член прогрессии, аN - N-й член прогрессии.
В нашем случае а1 = 0, а аN = N - 1, при этом получается следующая формула:
Сумма = (N - 1) * N / 2
Проверим.
Для одной вершины: (1 - 1) * 1 / 2 = 0 (точка)
Для двух вершин: (2 - 1) * 2 / 2 = 1 (линия)
Для трех вершин: (3 - 1) * 3 / 2 = 3 (треугольник)
Для четырех вершин: (4 - 1) * 4 / 2 = 6 (прямоугольник)
Для пяти вершин (наш случай): (5 - 1) * 5 / 2 = 10
Для шести вершин: (6 - 1) * 6 / 2 = 15 и так далее.
Теперь подсчитаем общее количество возможных топологий сети при указанных в тексте вопроса условиях. Итак, при 5 маршрутизаторах у нас может быть 10 линий, каждая из которых может быть одного из 4-х видов: высокоскоростная, среднескоростная, низкоскоростная и линии вообще может не быть.
Как я понимаю, подразумевается, что при моделировании и анализе топологии указанной сети компьютер должен перебрать все варианты топологии сети, отбрасывая при этом те, которые не будут работать вообще и те, которые будут работать, но окажутся неэффективными.
Как подсчитать это количество? Для этого можно использовать одно из основных правил комбинаторики - правило умножения (ссылка). Первую линию можно сделать одного из перечисленных выше 4-х видов. При каждом из этих 4-х выборов вида линии следующую линию тоже можно сделать одного из 4-х видов. То есть на каждом следующем шаге дерева выборов количество его веточек умножается на 4:
Получается, что общее количество вариантов топологии сети будет равно произведению 4 * 4 * 4 * ... и так далее, то есть равно 410. В терминах комбинаторики это называется «нахождением количества размещений с повторениями из 4 по 10» (ссылка).
Таким образом, компьютер при моделировании и анализе топологии данной сети должен перебрать 410 вариантов, затратив на каждый вариант 100 мс. А это значит, что всего компьютер затратит на эту работу следующее количество времени:
410 * 100 мс = 1 048 576 * 0,1 с = 104 857,6 с = 29,127 ч
Это и есть ответ.
В заключение отмечу, что в этот миллион с хвостиком вариантов входят и «нерабочие» варианты топологии сети. Например, вариант вообще без линий, или варианты, при которых какие-то из маршрутизаторов окажутся не присоединенными к сети, или варианты, при которых будут существовать несколько не соединенных друг с другом частей сети. «Рабочими» вариантами топологии сети я считаю такие варианты, при которых от одного маршрутизатора по линиям можно добраться до любого другого маршрутизатора в сети, даже если и не напрямую, а через один или несколько промежуточных маршрутизаторов. В нашем случае предполагается, что компьютер тупо перебирает все варианты, откидывая нерабочие. Не знаю, можно ли этот прямой перебор как-то оптимизировать, чтобы уменьшить время на отбор нужной топологии.