tanenbaum_seti_all.pages (525408), страница 118
Текст из файла (страница 118)
Примвры таблиц указателей (б] 442 Глава 5. Сетевой уровень Если кто-то из пользователей затем захочет найти название записи (нате), он вычислит значение хэш-функции, получит ключ (йеу) и затем с помощью функции эиссеяог(яеу) сможет найти 1Р-адрес узла, хранящего кортежи индексов. Первый шаг осуществляется довольно просто, не в пример второму. Для того чтобы можно было найти 1Р-адрес узла, соответствующего какому-либо ключу, каждый узел должен поддерживать определенные служебные структуры данных. Одной из них является 1Р-адрес последователя. Например, на рис. 5,22 последователь узла 4 — это узел 7, а последователь узла 7 — узел 12. Теперь можно начинать поиск.
Запрашивающий узел посылает последователю пакет, содержащий его 1Р-адрес и ключ, который он ищет. Этот пакет пересылается по кругу до тех пор, пока не будет найден искомый узел. На нем проверяется соответствие имеющейся информации ключу, и при положительном результате проверки пакет возвращается напрямую запрашивающему узлу, чей 1Р-адрес содержится в запросе.
В качестве первой оптимизации алгоритма предлагается следующее: каждый узел должен знать 1Р-адрес не только последователя, но и предшественника, тогда запрос можно будет распространять одновременно в двух направлениях — по часовой стрелке и против часовой стрелки, в зависимости от того, какой из путей кажется более коротким. Например, на рис. 5.22 узел 7 может отправить пакет по часовой стрелке, если ищется узел 10, А если ищется узел 3, то логичнее направить пакет против часовой стрелки. Даже с этой возможностью выбора направления линейный поиск остается крайне неэффективным методом для больших равноранговых сетей, поскольку среднее число узлов, которое потребуется обойти для поиска записи, равно я,~2, Значительно ускорить поиск позволяет поддерживаемая каждым узлом специальная таблица„которая в методе хорд носит название таблицы указателей.
В ней имеется т записей, пронумерованных от О до и — 1. Каждая запись содержит два поля: начало и 1Р-адрес последователя — жссеякя(яшт), как показано на рис, 5.22, б, Значения полей записи ! на узле я равны: 5гягг = й + 2' (тоЫи!о2'"), 1Р-адрес эиссеатог (эгагг 1!1). Обратите внимание: на узлах хранится сравнительно небольшое число адресов, и большинство из них расположено довольно близко друг от друга в терминах идентификаторов узлов. С использованием таблицы указателей процесс поиска ключа на узле я выглядит следующим образом.
Если ключ попадает в диапазон между я и эиссеээог(Я), значит, он находится, на самом деле, на узле эиссеяюг(я), н поиск прекращается. В противном случае таблица указателей просматривается на предмет поиска записи, поле начало которой является ближайшим предшественником ключа. Запрос посылается напрямую по 1Р-адресу из таблицы указателей. Узел с этим адресом просят перенять инициативу поиска. Поскольку искомый ключ находится где-то рядом, но идентификатор имеет меньшее значение, велика вероятность того, что конечный ответ будет дан очень скоро, спустя всего несколько дополнительных запросов. Поскольку каждая итерация при поиске вдвое уменьшает Алгоритмы маршрутизации 443 последующую область рассмотрения (то есть оставшееся расстояние до пели), то можно доказать, что среднее число итераций равно 1ой, и. В качестве первого примера рассмотрим поиск ключа 4п~ = 3 на узле 1. Узел с идентификатором 1 знает, что 3 лежит где-то между ним самим и его последователем — узлом 4.
Он делает вывод о том, что ключ находится на узле 4, и поиск прекращается. Результатом является 1Р-адрес узла 4. Второй пример. Пусть узлу 1 теперь понадобилось найти ключ 7геу = 14. Число 14 не находится между 1 и 4, поэтому необходимо заглянуть в таблицу указателей. Ближайшим предшественником 14 является 9, поэтому запрос направляется на 1Р-адрес, хранящийся в записи с полем начало, равным 9. Конкретно, зто узел 12.
Последний видит, что 14 находится между ним самим и последователем — узлом 15, поэтому результатом поиска является 1Р-адрес узла 15, Третий пример. Допустим, узлу 1 нужно найти ключ яеу = 16. Запрос, как и в предыдущем примере, отправляется на узел 12. Но на этот раз узел не может самостоятельно ответить на него. Он пытается найти тот узел, который находится ближе всего к 16, но имеет меньший идентификатор. Им является узел 14, который ссылается, в свою очередь, на узел 15.
Запрос туда и посылается. Узел 15 видит, что 16 находится между ним самим и его последователем (20), поэтому он возвращает 1Р-адрес 20 просителю. Ответ возвращается сразу на узел 1. Поскольку узлы могут появляться в сети и исчезать нз нее в любое время, в методе хорд необходимо как-то обрабатывать подобные ситуации. Мы предполагаем, что когда система начинала работать, она была достаточно небольшой, н узлы могли обмениваться информацией напрямую, выстраивая первичный круг идентификаторов и таблицы указателей. После этого уже необходима автоматизированная процедура. Когда новый узел г собирается войти в сеть, он должен войти в контакт с какой-либо из уже находящихся в сети станций и попросить ее поискать для него 1Р-адрес зиссезтог(г). Затем новый узел выясняет, кто будет его предшественником (зиссеззог(г) для предшественника).
Все зто нужно для того, чтобы можно было определить свое место в круге идентификаторов, Например, если узел 24 на рис. 5.22 захочет войти в сеть, он может поинтересоваться у любого узла, чему равно значение зиссезтог(24). Выясняется, что оно равно 27. Затем у узла 27 надо узнать, кто является его предшественником (20), После того как обоим этим узлам сообщается о существовании нового узла, узел 20 помечает себе, что его последователем становится узел 24, а узел 27 — что этот узел становится его предшественником, Кроме того, узел 27 передает ключи диапазона 21-24 новичку.
С этого момента последний считается зарегистрированным в разноранговой сети. Тем не менее, ситуация изменилась, и многие таблицы указателей теперь содержат ошибки. Чтобы исправить их, все узлы запускают фоновые процессы, которые периодически пересчитывают таблицы указателей, обращаясь к функции зиссаиог. Когда какой-то из этих запросов наталкивается на новый узел, запись таблицы обновляется. Если узел уходит вежливо, он передает свои ключи последователю и информирует предшественника о своем скором отбытии. При этом в цепочке идентификаторного круга предшественник теперь оказывается непосредственным соседом последователя. Однако если с узлом происходит какая-то авария, возникают 444 Глава 5. Сетевой уровень проблемы у его предшественника, поскольку он не знает, кто является его последователем. Решение данной проблемы состоит в том, что узлы запоминают не только своего прямого последователя, но и еще з последователей.
Получается, что без тяжких последствий для окружаю|цих из сети могут выпасть г — 1 последовательных узлов, н круг при этом не разорвется. Метод хорд используется для создания распределенных файловых систем (?)аЬе!г и др., 2001Ъ) и других приложений; научные изыскания в этой области идут и сейчас. Одна из разноранговых систем, Разсгу, и ее приложения описаны в (Котезгоп апс! ЭгпзсЬе1, 2001а; Котузгоп апй ПгпзсЬе1, 2001Ь).
Еще одна система, Ргеепец обсуждается в (С!агйе и др., 2002). Наконец, четвертая система этого типа описана в (Каспазату и др., 2001). Алгоритмы борьбы с перегрузкой Когда количество пакетов, передаваемых одновременно по подсети (или ее части), превышает некий пороговый уровень, производительность сети начинает снижаться. Такая ситуация называется перегрузкой. График на рис.
5.23 изображает симптомы этого явления. Когда число пакетов, посылаемых хостами в сеть, не превышает ее пропускной способности, все они доставляются адресатам (кроме небольшого процента поврежденных ошибками передачи). При этом количество доставленных пакетов пропорционально количеству посланных. Однако по мере роста трафика маршрутизаторы перестают успевать обрабатывать все пакеты и начинают их терять. При дальнейшем увеличении числа отправляемых пакетов ситуация продолжмт ухудшаться.
Когда число пакетов достигает максимального уровня, производительность сети начинает снижаться, При очень высоком уровне графика производительность сети падает до совсем низкого уровня и практически никакие пакеты не доставляются. Посланные пакеты Рис. 6.23. При слишком высоком уровне трафика начинается перегрузка, и производительность сети резко снтскается Алгоритмы борьбы с перегрузкой 445 Перегрузка может быть вызвана несколькими факторами, Если вдруг потоки пакетов начинают прибывать на маршрутизатор сразу по трем или четырем входным линиям и всем им нужна одна и та же выходная линия, то образуется очередь. Когда у маршрутизатора закончится свободная память для буферизации всех прибывающих пакетов, их негде будет сохранять и они начнут теряться Увеличение объема памяти маршрутизаторов может в какой-то степени помочь, но Нэгл (Иай1е) в 1987 году показал, что даже если у маршрутизаторов будет бесконечное количество памяти, ситуация с перегрузкой не улучшится, а, наоборот, ухудшится, так как к тому времени, когда пакеты доберутся до начала очереди, они уже запоздают настолько, что источником будут высланы нх дубликаты, Все эти пакеты будут посланы следующему маршрутизатору, еще более увеличивая нагрузку на всем протяжении маршрута к получателю.
Медленные процессоры также могут служить причиной заторов, Если центральные процессоры маршрутизаторов слишком медленно выполняют свои задачи, связанные с учетом, управлением очередями, обновлением таблиц н т, д., то очереди будут появляться даже при достаточно высокой пропускной способности линий. Аналогично, линии с низкой пропускной способностью также могут вызывать заторы в сети, Если заменить линии более совершенными, но оставить старые процессоры, или наоборот, такие действия обычно немного помогают, но часто просто приводят к сдвигу узкого места, вызванного несоответствием производительности разных частей системы. Проблема узкого места сохраняется до тех пор, пока компоненты системы не будут должным образом сбалансированы. Необходимо пояснить, в чем состоит разница между борьбой с перегрузкой и управлением потоком.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
