СПОСОБ МАРШРУТИЗАЦИИ ВИРТУАЛЬНЫХ СОЕДИНЕНИЙ В СЕТИ С КОММУТАЦИЕЙ КАДРОВ

1. Способ маршрутизации виртуальных соединений в сети с коммутацией кадров, включающей в себя множество терминалов источника и/или назначения упомянутых кадров, в котором коммутаторы кадров соединены друг с другом с помощью физических соединений, при этом каждое виртуальное соединение определено для типа из точки в точку путем через упомянутую сеть между терминалом источника и терминалом назначения и для многоточечного типа по множеству путей через упомянутую сеть между терминалом источником и множеством терминалов назначения, причем упомянутый способ отличается тем, что, по меньшей мере, для одного виртуального соединения он включает в себя следующие этапы:
(a) выбирают (250) из набора возможных путей между терминалом источника и терминалом (терминалами) назначения поднабор путей, удовлетворяющих, по меньшей мере, одному заданному топологическому ограничению;
(b) определяют (260) среди упомянутого поднабора пути для виртуального соединения из точки в точку или множество путей для многоточечного виртуального соединения, минимизацию, по меньшей мере, одной заданной функции стоимости;
(c) выполняют маршрутизацию (295) упомянутого виртуального соединения в соответствии с путем (путями), определенным таким образом.
2. Способ маршрутизации по п.1, отличающийся тем, что, когда упомянутое виртуальное соединение представляет собой соединение из точки в точку, и сеть разделена на различные зоны, упомянутое топологическое ограничение представляет собой ограничение (435), запрещающее переход между зонами, если коммутаторы, соединенные, соответственно, с терминалом источником и терминалом назначения, принадлежат одной и той же зоне, и, в противном случае, представляет собой ограничение (437), позволяющее один переход между зонами, принадлежащими, соответственно, упомянутым терминалам источника и назначения.
3. Способ маршрутизации по п.1, отличающийся тем, что этап выбора учитывает дополнительные топологические ограничения (420) сегрегации и/или совместного расположения путей, возможных в отношении виртуальных соединений, маршруты которых уже проложены или должны быть проложены одновременно с упомянутым соединением или коммутаторами упомянутой сети.
sg
sg
sg
sg
4. Способ маршрутизации по п.1, отличающийся тем, что на этапе выбора учитывают дополнительные топологические ограничения, в которых каждое дополнительное топологическое ограничение относится к группе путей, формирующих набор виртуальных соединений, маршруты которых должны быть проложены одновременно, в котором упомянутая группа составлена из множества N подгрупп упомянутых путей, и упомянутые дополнительные ограничения выражают, что, самое большее, число n подгрупп такое, что 0≤n<N, может быть сделано недействительным, при этом подгруппу делают недействительной, если на все пути, принадлежащие ей, влияет отказ одного и того же коммутатора упомянутой сети.
5. Способ маршрутизации по пп.2, 3 или 4, отличающийся тем, что упомянутая функция (440) стоимости представляет количество коммутаторов, которые пересекают данный путь.
1
K
6. Способ маршрутизации по п.1, отличающийся тем, что, когда упомянутое виртуальное соединение представляет собой соединение многоточечного типа, и сеть разделена на различные зоны, ограничение (520,…,520) запрещающее переход между зонами, применяют для каждого возможного пути между упомянутым терминалом источника и терминалом назначения упомянутого соединения, если коммутаторы, подключенные, соответственно, к упомянутым терминалу источника и терминалу назначения, принадлежат одной и той же зоне, и, в противном случае, применяют ограничение, разрешающее однократный переход между зонами, принадлежащими, соответственно, упомянутым терминалам источника и назначения.
1
K
7. Способ маршрутизации по п.6, отличающийся тем, что на этапах (520,…,520) для каждого из возможных путей между упомянутым терминалом источника и назначения упомянутого соединения применяют дополнительные топологические ограничения сегрегации и/или совместного размещения этих путей относительно виртуальных соединений, для которых уже проложены маршруты или которые должны быть проложены одновременно с упомянутым соединением или коммутаторами.
sg
sg
sg
sg
8. Способ маршрутизации по п.6, отличающийся тем, что на этапе выбора учитывают дополнительные топологические ограничения, в которых каждое дополнительное топологическое ограничение относится к группе путей, формирующих набор виртуальных соединений, для которых должны быть проложены маршруты одновременно, в котором упомянутая группа состоит из множества N подгрупп упомянутых путей, и упомянутые дополнительные ограничения выражают, что, самое большее, количество n подгрупп такое, что 0≤n<N, могут быть сделаны недействительными, причем подгруппу делают недействительной, если на все пути, принадлежащие ей, влияет отказ одного и того же коммутатора упомянутой сети.
1
K
9. Способ маршрутизации по пп.6, 7 или 8, отличающийся тем, что упомянутая функция стоимости представляет собой количество коммутаторов, через которые проложен путь, и ее минимизируют (530…,530) по каждому набору возможных путей между упомянутым терминалом источника и терминалом назначения упомянутого соединения для обеспечения, по меньшей мере, одного пути - кандидата на терминал назначения.
10. Способ маршрутизации по п.9, отличающийся тем, что формируют (540) комбинации К путей-кандидатов, в котором К представляет собой количество терминалов назначения соединения, и каждая комбинация соответствует возможному решению маршрутизации упомянутого многоточечного соединения, и вторую функцию стоимости минимизируют (550) по набору упомянутых возможных, полученных таким образом, решений.
11. Способ маршрутизации по п.10, отличающийся тем, что вторая функция стоимости оценивает для каждого возможного решения количество коммутаторов, совместно используемых между его различными составляющими путями.
1
N
12. Способ маршрутизации по п.1, отличающийся тем, что, по меньшей мере, для одной группы соединений, используемых при выполнении одной и той же функции, которая называется связкой соединений, каждое соединение представляет собой соединение из точки в точку, и сеть разделена на различные зоны, при этом ограничения, запрещающие переход между зонами, применяют для каждого из соединений упомянутой связки (620,…,620), для каждого возможного пути между терминалом источника и терминалом назначения упомянутого соединения, если коммутаторы соединенные, соответственно, с терминалом источника, и терминалом назначения, принадлежат той же зоне, и, в противном случае, накладывают ограничение, позволяющее однократный переход между зонами, принадлежащими соответственно упомянутым терминалам источника и назначения.
1
K
13. Способ маршрутизации по п.12, отличающийся тем, что для каждого виртуального соединения и для каждого из возможных путей между терминалом источника и терминалом назначения упомянутого соединения, накладывают (620,…,620) дополнительные топологические ограничения сегрегации и/или совместного размещения этих путей относительно виртуальных соединений, для которых уже проложен маршрут или для которых должен быть проложен маршрут одновременно с упомянутым соединением или коммутаторами.
sg
sg
sg
sg
14. Способ маршрутизации по п.12, отличающийся тем, что на этапе выбора учитывают дополнительные топологические ограничения, в которых каждое дополнительное топологическое ограничение относится к группе путей, формирующих набор виртуальных соединений, для которых должен быть проложен маршрут одновременно, в котором упомянутая группа состоит из множества N подгрупп упомянутых путей, и упомянутые дополнительные ограничения выражают, что, самое большее, число n подгрупп такое, что 0≤n<N, может быть сделано недействительными, причем подгруппу делают недействительной, если на все пути, принадлежащие ей, влияет отказ одного и того же коммутатора упомянутой сети.
1
N
15. Способ маршрутизации по пп.12, 13 или 14, отличающийся тем, что упомянутая функция стоимости представляет собой количество коммутаторов, через которые проложен путь, и ее минимизируют (630,…,630), для каждого из соединений упомянутой связки, по каждому набору возможных путей между терминалом источника и терминалом назначения упомянутого соединения для обеспечения, по меньшей мере, одного пути-кандидата на соединение.
16. Способ маршрутизации по п.15, отличающийся тем, что формируют (640) комбинации N путей-кандидатов, где N представляет собой количество соединений упомянутой связки, при этом каждая комбинация соответствует возможному решению маршрутизации упомянутой связки, и третью функцию стоимости минимизируют (650) по набору упомянутых возможных решений, полученных таким образом.
17. Способ маршрутизации по п.16, отличающийся тем, что третья функция стоимости оценивает для каждого возможного решения маршрутизации в связке количество коммутаторов, совместно используемых между путями, комбинацию которых представляет упомянутое решение.
1
N
18. Способ маршрутизации по п.1, отличающийся тем, что, по меньшей мере, для одной группы соединений, участвующих в выполнении одной и той же функции, которая называется связкой соединений, причем каждое соединение представляет собой соединение многоточечного типа и сеть разделена на отдельные зоны, применяют ограничение, запрещающее переход между зонами, для каждого из соединений упомянутой связки (720,…,720), для каждого возможного пути между терминалом источника и терминалом назначения упомянутого соединения, если коммутаторы, соединенные, соответственно, с терминалом источника и с терминалом назначения, принадлежат одной и той же зоне, и, в противоположном случае, накладывают ограничение, разрешающее однократный переход между зонами, принадлежащими, соответственно, упомянутым терминалам источника и назначения.
1
N
19. Способ маршрутизации по п.18, отличающийся тем, что для каждого виртуального соединения и для каждого из возможных путей между терминалом источника и терминалом назначения упомянутого соединения применяют (720,…,770) дополнительные топологические ограничения сегрегации и/или совместного размещения этих путей относительно виртуальных соединений, для которых уже был проложен маршрут или будет проложен маршрут, одновременно с упомянутым соединением или коммутаторами упомянутой сети.
sg
sg
sg
sg
20. Способ маршрутизации по п.18, отличающийся тем, что на этапе выбора учитывают дополнительные топологические ограничения, в которых каждое дополнительное топологическое ограничение относится к группе путей, формирующих набор виртуальных соединений, для которых маршруты должны быть проложены одновременно, в котором упомянутая группа состоит из множества N подгрупп упомянутых путей, и упомянутые дополнительные ограничения выражают, что, самое большее, количество n подгрупп такое, что 0≤n<N, могут быть сделаны недействительными, причем подгруппу делают недействительной, если на все пути, принадлежащие ей, влияет отказ одного и того же коммутатора упомянутой сети.
1
N
21. Способ маршрутизации по пп.18, 19 или 20, отличающийся тем, что упомянутая функция стоимости представляет собой количество коммутаторов, через которые проложен путь, и ее минимизируют (730,…,730) для каждого из соединений упомянутой связки, по каждому набору возможных путей между терминалом источника и терминалом назначения упомянутого соединения для обеспечения, по меньшей мере, одного пути-кандидата на соединение и на терминал назначения.
1
2
N
i
22. Способ маршрутизации по п.21, отличающийся тем, что формируют (740) комбинации K+K+…+K путей-кандидатов, где K, 1<i≤N, представляют собой номера соответствующих путей N соединений упомянутой связки, причем каждая комбинация соответствует возможному решению маршрутизации упомянутой связки, и четвертую функцию стоимости минимизируют (750) по набору упомянутых возможных решений, полученных таким образом.
23. Способ маршрутизации по п.22, отличающийся тем, что четвертая функция стоимости оценивает для каждого возможного решения маршрутизации связки количество коммутаторов, через которые проложены соединения связки, соответствующие этому решению.
24. Способ маршрутизации по одному из пп.2, 6, 12 или 18, отличающийся тем, что упомянутые зоны сети получают питание от независимых источников питания.
25. Способ маршрутизации по п.1, отличающийся тем, что пятую функция стоимости, которая оценивает нагрузку трафика наиболее тяжело нагруженного коммутатора сети, минимизируют по набору решений маршрутизации, полученных, в результате минимизации одной из второй, третьей или четвертой функций стоимости.