Таненбаум Э. Распределенные системы. Принципы и парадигмы

Подождите немного. Документ загружается.

Общий вес 128

Частичный вес |128|

4.3.

Удаление сущностей, на которые нет ссылок 261

Частичный вес

скелетона

Скелетон

Объект О

Частичный

вес

заместителя

Заместитель

/ снижен

Процесс Р X наполовиь

\М]\

LtJ

128h

"64l

Ч J

Процесс Р2 получает

половину веса

заместителя

из процесса Р1

Процесс Р1 передает

ссылку процессу Р2

Процесс Р2

[128]

[64]

' i

)Й^

Jc^

\ J

Общий и частичный

вес скелетона

остался прежним

Рис. 4.25. Исходное соотношение весов при взвешенном подсчете ссылок (а). Присвоение

веса при создании новой ссылки (б). Присвоение веса при копировании ссылки (в)

При уничтожении ссылки скелетону объекта посылается сообщение, умень-

шающее счетчик. Затем из общего веса вычитается частичный вес уничтоженной

ссылки. Как только общий вес станет равным нулю, объект можно удалять. От-

метим, что в этом случае также предполагается, что сообщения не теряются и не

дублируются.

Основная проблема взвешенного подсчета ссылок состоит в том, что количе-

ство создаваемых ссылок ограничено. Как только частичный вес скелетона и уда-

ленных ссылок достигнет нуля, создавать или копировать новые ссылки будет

невозможно. Решить проблему можно с помощью косвенных ссылок. Предполо-

жим, что процесс Р1 хочет передать ссылку процессу Р2, но частичный вес его

заместителя равен 1, как показано на рис. 4.26. В этом случае Р1 создает в своем

адресном пространстве скелетон s' с подходящим общим весом и частичным ве-

сом, равным общему. Это абсолютно аналогично созданию в адресном простран-

стве объекта скелетона

Затем процессу

Р2

пересылается заместитель, которому

передается половина частичного веса скелетона s'. Другая половина веса остает-

ся у 5' для раздачи другим заместителям.

Заметим, что если общий вес скелетона

установить в 1, этот подход превра-

тится в подобие передачи указателя из процесса Р1 в процесс Р2. Если, в свою

очередь, Р2 захочет передать свою ссылку, он может создать еще один передавае-

мый указатель. Наиболее серьезная проблема передачи указателей состоит в том.

262

Глава 4. Именование

что длинные цепочки существенно снижают производительность. Кроме того,

цепочки весьма уязвимы при сбоях.

У процесса Р1

исчерпан вес,

и он создает скелетон s'

Процесс Р1

Процесс Р2

У объекта исчерпан

частичный вес

Процесс Р2 \ Об] Общий вес

ссылается \^-^ частичный вес

на объект ^ '

через процесс Р1

Рис. 4.26. Создание косвенной ссылки

случае исчерпания частичного веса

Альтернативой косвенным ссылкам может быть подсчет поколений ссылок

{generation reference

counting).

Вновь предположим, что каждая удаленная ссылка

представляет из себя пару (заместитель, скелетон), причем скелетон принадле-

жит тому же адресному пространству, что и объект. Каждый заместитель хранит

счетчик копий и номер поколения. При создании новой ссылки вида (замести-

тель,

скелетон) номер поколения соответствующего заместителя устанавливает-

ся в ноль. Поскольку пока еще не было сделано копий заместителя, его счетчик

копий также равен нулю.

Копирование удаленной ссылки (заместитель, скелетон) в другой процесс

производится обычным образом

—

пересылкой ему копии заместителя. В этом

случае счетчик копий в исходном заместителе увеличивается на единицу, а счет-

чик копий в скопированном заместителе выставляется в ноль. Однако поскольку

этот заместитель был скопирован, он принадлежит к следующему поколению,

и по этой причине его номер поколения на единицу больше, чем у исходного за-

местителя, что и демонстрирует рис. 4.27.

Процесс Р2

Процесс Р1 передает

ссылку процессу Р2

Счетчик копий

Номер поколения

Рис. 4.27. Создание и копирование удаленных ссылок

при подсчете поколений ссылок

Скелетон поддерживает таблицу С, в которой

G[i]

обозначает число создан-

ных копий для поколения i. Если заместитель р удаляется, сообщение об удале-

4.3.

Удаление сущностей, на которые нет ссылок 263

НИИ

посылается скелетону, содержащему номер поколения заместителя, скажем й,

и число копий, порожденных от заместителя р, скажем п. Скелетон приводит G

в соответствие с действительностью, сначала уменьшая на единицу

G[k]

и пока-

зывая, таким образом, что удалена ссылка ^-го поколения. Затем он увеличивает

G[^+l] на п, чтобы показать, что удаленная ссылка создала п потомков или, дру-

гими словами, что она была скопирована в п ссылок следующего поколения (от-

метим, что скелетон должен сначала создать элемент

G[^+l],

если ранее он ниче-

го не знал о поколении й+1). В том случае, если все элементы G[i\ равны нулю,

на объект больше нет ссылок и его можно удалить.

Подсчет поколений ссылок также требует надежных коммуникаций, но спо-

собен обеспечивать копирование ссылок, не обращаясь при создании копий к ске-

летону.

4.3.3. Организация списка ссылок

Другой подход к управлению ссылками состоит в том, чтобы заставить скелетон

отслеживать заместители, которые содержат ссылки на него. Другими словами,

вместо подсчета ссылок скелетон должен поддерживать полный список всех за-

местителей, которые на него указывают. Подобный

список ссылок {reference

list)

имеет следующие важные свойства. Добавление заместителя в список ссылок не

должно давать никакого результата, если этот заместитель в списке уже присут-

ствует. Точно так же попытка удаления заместителя, отсутствующего в списке, не

должна ни к чему вести. Добавление и удаление заместителей являются таким

образом

идемпотентными

(idempotent) операциями.

Идемпотентные операции характеризуются тем, что их многократное повто-

рение не влияет на конечный результат. В частности, при создании новой ссыл-

ки на объект создавший ссылку процесс может многократно отправлять сообще-

ния скелетону объекта, требуя добавить ссылку в список ссылок. Он прекращает

посылать сообщения после получения подтверждения о доставке. Соответствен-

но,

об удалении ссылки можно уведомлять посылкой (возможно, многократной)

скелетону сообщения с требованием исключить ссылку из списка ссылок. По-

нятно, что операции увеличения и уменьшения счетчика не являются идемпо-

тентными операциями.

Таким образом, список ссылок не требует от связи надежности, а также не ну-

ждается в механизмах обнаружения и отбрасывания повторных сообщений (од-

нако необходимо, чтобы добавление ссылок в список и удаление их из списка

подтверждались). Это серьезное преимущество по сравнению с механизмами под-

счета ссылок.

Списки ссылок, используемые в системе RMI языка Java, основаны на мето-

де,

описанном в [60]. Согласно этому методу, когда процесс Р создает удаленную

ссылку на объект, он посылает свой идентификатор скелетону объекта, который

добавляет Р в список ссылок. Когда приходит подтверждение, процесс создает

заместитель объекта в своем адресном пространстве.

Передача ссылки другому процессу, то есть посылка копии заместителя, об-

рабатывается сходным образом. Когда процесс Р1 посылает копию своего замес-

264 Глава 4. Именование

тителя объекта О процессу Р2, процесс Р2 сначала требует у скелетона объекта

добавить Р2 в список ссылок. Когда это сделано, процесс Р2 встраивает замести-

тель в свое адресное пространство.

Проблемы могут возникнуть в том случае, если процесс Р1 удалит свой за-

меститель до того, как Р2 подаст запрос на вставку в список ссылок. В этом слу-

чае если запрос на удаление, который Р1 посылает скелетону объекта, будет

обработан раньше запроса на вставку от Р2, список ссылок может оказаться пус-

тым, то есть скелетон может прийти к неправильному выводу о возможности

удаления объекта. Эта ситуация полностью аналогична ситуации из варианта

с подсчетом ссылок, показанного на рис. 4.24, а, и может быть решена таким же

способом.

Другим важным достоинством списка ссылок является простота сохранения

его непротиворечивости при сбоях процессов. Скелетон объекта регулярно про-

веряет, все ли имеющиеся в списке процессы в порядке. Это делается посредст-

вом посылки сообщения ping с запросом, живы ли они еще и сохраняют ли ссылку

на объект. Процесс должен немедленно ответить на это сообщение. Если ответ

не получен, возможно, даже после нескольких попыток, скелетон удаляет про-

цесс из списка.

Основной недостаток списка ссылок состоит в том, что он плохо масштабирует-

ся,

особенно если скелетон должен отслеживать много ссылок. Один из способов

сохранить управляемость состоит в том, чтобы указать скелетону на необходи-

мость регистрировать ссылки на ограниченный срок. Если заместитель до исте-

чения этого срока не подтверждает скелетону свою регистрацию, ссылка просто

удаляется из списка. Этот подход называется также

арендой

{lease).

Мы вернем-

ся к аренде в главе 6.

4.3.4. Идентификация сущностей,

на которые нет ссылок

Как уже было продемонстрировано с помощью рис. 4.22, набор сущностей в рас-

пределенных системах может содержать сущности со ссылками только друг на

друга, то есть недоступные из корневого набора. Такие сущности должны уда-

ляться. К сожалению, методы сборки мусора, описанные ранее, не в состоянии

выявить подобные сущности.

Нам необходим метод, который позволит отследить все сущности в распреде-

ленной системе. В основном он состоит в проверке доступности сущностей из

корневого набора с последующим удалением всех недоступных. Подобные мето-

ды носят общее название

трассировочной

сборки мусора

{tracing-based garbage

collection).

В противоположность распределенным ссылкам, которые мы рассмат-

ривали ранее, трассировочной сборке мусора присущи проблемы масштабируе-

мости, поскольку необходимо отслеживать все сущности распределенной системы.

Примитивная трассировка

распределенных системах

Чтобы разобраться в распределенной трассировочной сборке мусора, полезно об-

судить трассировку в однопроцессорных системах. Наиболее простой подход

4.3.

Удаление сущностей, на которые нет ссылок 265

к однопроцессорной трассировке представлен сборщиками типа «помечай и под-

метай». Эти сборщики работают в два приема.

В ходе фазы пометки сущности отслеживаются по существующим цепочкам

ссылок, исходящим из сущностей корневого набора. Каждая сущность, которая

может быть достигнута оттуда, помечается, например, путем записи сущности

в отдельную таблицу. Фаза подметания состоит из тщательной проверки памяти

для локализации «ничейных» сущностей. Эти сущности считаются мусором, ко-

торый должен быть удален.

Другой вариант работы сборщиков «помечай и подметай»

—

трехцветная по-

метка сущностей, Изнача.71ьно каждая сущность, которую следует проверить, ок-

рашена в белый цвет. К концу фазы пометки все сущности, доступные из корня,

помечаются черным, а недоступные остаются белыми. Серый цвет используется

для индикации хода фазы пометки. Сущность помечается серым, если она дос-

тупна, но ссылки, которые содержит эта сущность, еще нуждаются в проверке.

Когда все сущности, на которые ссылается данная сущность, окрашиваются се-

рым, сама она становится черной.

Распределенный вариант схемы «помечай и подметай» был реализована в сис-

теме Emerald, описанной в

[220].

В Emerald каждый процесс запускает локаль-

ный сборщик мусора, причем все сборщики работают параллельно. Сборщики

окрашивают заместители, скелетоны и сами объекты. Изначально все они поме-

чаются белым цветом. Когда объект, расположенный в адресном пространстве

процесса Р, доступен из корневого набора, объект помечается серым. При этом

все заместители, содержащиеся в этом объекте, также помечаются серым. Помет-

ка заместителя серым цветом означает, что его локальный сборщик мусора ука-

зывает на необходимость проверки ссылок данного удаленного объекта ассоции-

рованным с ним локальным сборщиком мусора.

Когда заместитель помечается серым, ассоциированному с заместителем ске-

летону посылается сообщение, маркирующее серым и его. Объект, к которому

относится скелетон, помечается серым вслед за своим скелетоном. Далее, рекур-

сивно, все заместители в этом объекте помечаются серым. В этот момент скеле-

тон и ассоциированный с ним объект помечаются черным, и соответствующее

сообщение посылается всем ассоциированным с ним заместителям. Отметим, что

хотя в этом подходе скелетону известны связанные с ним заместители, это не оз-

начает, что они достижимы из скелетона. Логически рассуждая, пара (замести-

тель,

скелетон)

—

это исключительно однонаправленная связь от заместителя

скелетону.

Когда заместитель получает сообщение о том, что ассоциированный с ним

скелетон стал черным, он тоже помечается черным. Другими словами, локаль-

ный сборщик мусора теперь знает, что удаленный объект, на который идет ссыл-

ка через заместитель, признан доступным.

Когда все локальные сборщики мусора заканчивают фазу пометки, каждый

из них по отдельности собирает все белые объекты, считая их мусором. Фаза по-

метки завершается, когда все объекты, скелетоны и заместители приобретут ли-

бо белый, либо черный цвет. Удаление белых объектов означает также удаление

ассоциированных с ними скелетонов, а также заместителей этих объектов.

266

Глава

Именование

Основной недостаток алгоритма «помечай и подметай» состоит в том, что он

требует, чтобы граф доступности в течение обоих фаз оставался неизменным.

Иначе говоря, выполнение программы, для которой изначально был создан про-

цесс,

должно быть временно приостановлено и система должна переключиться

на сборку мусора. Для распределенных систем это означает, что все процессы

должны быть синхронизированы. Каждый из них должен переключиться на сбор-

ку мусора, после чего все они смогут продолжить свою работу.

Такой сценарий, называемый также синхронизацией «все замри!», обычно

недоступен для распределенных сборщиков мусора. Усовершенствование может

заключаться в использовании инкрементных сборщиков мусора, которые позволя-

ют программе работать, перемежая ее выполнение со сборкой мусора. К сожалению,

подобные сборщики мусора в распределенных системах плохо масштабируются.

Поскольку они работают параллельно с программой, которая изменяет граф дос-

тупности, объекты часто должны помечаться серым, а это приведет к распро-

странению серых пометок по удаленным процессам. Результатом будет большой

трафик сообщений, способный снизить общую производительность системы.

Трассировка в группах

Рассматривая проблемы масштабируемости, присущие многим трассировочным

системам сборки мусора, разработчики придумали способ, в ходе которого про-

цессы (содержащие объекты) в больших распределенных системах собираются

в группы

[255].

Сборка мусора производится внутри групп путем сочетания ме-

тодов «помечай и подметай» и подсчета ссылок. Сосредоточимся на базовом ал-

горитме сборки мусора в группе процессов.

Группа

—

это просто набор процессов. Единственная причина работы с груп-

пами

—

масштабируемость. Базовая идея состоит в том, чтобы сначала собрать

весь мусор в группе, включая цепочки ссылок, полностью находящиеся внутри

группы. На следующем шаге выполняется переход к группе большего размера,

содержащей несколько подгрупп, каждая из которых была очищена сборщиком

мусора.

Чтобы понять трассировку в группе, предположим, что удаленные ссылки

вновь реализованы в виде пар (заместитель, скелетон). Для каждого объекта

существует лишь один скелетон, находящийся в адресном пространстве объекта,

и множество заместителей, способных связываться со скелетоном. Скелетон

поддерживает счетчик ссылок, описанный в пункте 4.3.2, который подсчитывает

число ассоциированных с этим скелетоном заместителей. Процесс может иметь

максимум один заместитель на каждый распределенный объект.

Как только будет сформирована группа процессов, вступает в работу базовый

алгоритм сборки мусора, состоящий из пяти шагов.

Первичная маркировка, помечаются только скелетоны.

Распространение маркировки внутри процессов со скелетонов на заместителей.

Распространение маркировки между процессами с заместителей на скелетоны.

Стабилизация путем многократного повторения двух предыдущих шагов.

Удаление мусора.

4.3.

Удаление сущностей, на которые нет ссылок 267

До начала каждого из этих шагов важно понять, что означает маркировка

сущности. Алгоритм относится в основном к маркировке заместителей и скеле-

тонов. Важно отметить, что ни заместители, ни скелетоны не относятся к корне-

вому набору.

Скелетоны могут помечаться как

нетвердые

или

твердые^

а заместители

—

как

отсутствующие,

нетвердые

или

твердые.

Если скелетон помечен как твер-

дый,

значит, он достижим либо из заместителя процесса, не входящего в группу,

либо из корневого объекта, входящего в группу, то есть объекта, содержащегося

в корневом наборе и входящего в группу процесса. Скелетон, помеченный как

нетвердый,

доступен только из заместителя внутри группы. Скелетон может быть

помечен только как

нетвердый

или твердый.

Заместитель, помеченный как

твердый,

достижим из объектов корневого на-

бора. Если заместитель помечен как

нетвердый,

он достижим из скелетона, также

помеченного как

нетвердый.

Такие скелетоны потенциально могут расположить-

ся цепочкой, к которой не будет доступа у объектов корневого набора. Замести-

тель,

помеченный как

отсутствующий,

недоступен ни из скелетонов, ни из объ-

ектов корневого набора. Только заместители, помеченные как

отсутствующие,

могут изменить маркировку на

твердые.

Как мы увидим, заместители, помечен-

ные как

нетвердые,

сохраняют эту маркировку и далее.

Первый шаг состоит в пометке одних скелетонов. Скелетон помечается как

твердый

или

нетвердый

в зависимости от того, доступен ли он для заместителей,

не входящих в группу. Эта доступность может быть легко проверена по счетчику

ссылок скелетона. Значение этого счетчика показывает, сколько заместителей дру-

гих процессов на него ссылаются. Некоторые из этих процессов входят в группу,

другие не входят. Если среди них имеются заместители процессов, не входящих

в группу, скелетон помечается как

твердый.

Просто пересчитав, сколько замести-

телей, ассоциированных со скелетоном, входят в группу, и вычтя это число из зна-

чения счетчика ссылок, мы можем решить, имеются ли у скелетона ассоцииро-

ванные с ним заместители вне группы. Это приводит нас к следующему алгоритму.

Для каждого заместителя внутри группы уменьшается счетчик ссылок соот-

ветствующего скелетона на единицу, в том случае, если скелетон также нахо-

дится внутри группы.

Скелетон внутри группы помечается как

нетвердый,

если его счетчик ссылок

сброшен в ноль. В противном случае он доступен из-за границ группы и по-

мечается как твердый.

Первый шаг иллюстрирует рис. 4.28, а, на котором все скелетоны, кроме од-

ного,

являются

нетвердыми.

Только один скелетон, который является твердым,

доступен заместителю из-за границ группы.

Второй шаг включает в себя переключение каждого из процессов на свой

сборщик мусора. Эти локальные сборщики работают независимо от глобального

сборщика мусора. Единственное, что от них требуется в ходе работы,

—

это рас-

пространить маркировку со скелетонов на заместителей. Конкретнее, мы полага-

ем,

что внутри одного процесса заместители достижимы из скелетона (отметим,

что заместитель и скелетон принадлежат разным объектам). В результате ло-

268 Глава 4. Именование

кального распространения пометок заместители будут помечены как минимум

так же, как и скелетон. Более того, если заместитель будет доступен объекту кор-

невого набора, он будет помечен как твердый.

Внешний процесс

Группа процессов

о Нетвердый

• Твердый

^т

"Ш;:.-

Рис. 4.28. Исходная маркировка скелетона (а). Ситуация после локального распространения

маркировки в каждом процессе (б). Итоговая маркировка (в)

4.3.

Удаление сущностей, на которые нет ссылок 269

Локальное распространение внутри процесса Р может происходить следую-

щим образом. Изначально все заместители помечаются как

отсутствующие.

Ло-

кальный сборщик мусора начинает трассировку с набора, в который входят ске-

летоны, которые ранее были помечены как

твердые,

а также объекты корневого

набора.

Твердые

пометки распространяются на все объекты (то есть на локаль-

ные объекты и заместители), доступные из этого набора. Второй проход осуще-

ствляется, начиная со скелетонов, помеченных как

нетвердые.

Если заместители,

доступные из этого набора, помечены как

отсутствующие,

их маркировка меня-

ется на

нетвердые.

Если достижимые заместители уже помечены как

твердые,

за

ними сохраняется эта маркировка. Таким образом, после локального распростра-

нения каждый заместитель процесса получает одну из трех маркировок — от-

сутствующий,

нетвердый или

твердый.

Рисунок 4.28, б отражает момент после

локального распространения маркировок в группе, изображенной на рис. 4.28, а.

Третий шаг состоит из распространения пометок от заместителей к ассоции-

рованным с ними скелетонам. Другими словами, пометки распространяются от

процесса к процессу. Так, если заместитель был помечен как

твердый,

ассоции-

рованному с ним скелетону посылается сообщение о том, что он также получает

пометку

твердый,

если этот скелетон раньше был маркирован иначе. Сообщение

посылается только тем скелетонам, которые входят в группу. Пометки нетвер-

дый распространять не нужно: исходная разметка уже привела к тому, что все

скелетоны группы имеют пометку

твердый

или

нетвердый.

Четвертый шаг приводит к глобальному распространению пометок твердый

предыдущего шага. Скелетон, скажем, процесса Р может при этом поменять свою

пометку с нетвердый на

твердый.

Эти изменения будут обусловлены тем фак-

том, что к скелетону получат доступ объекты, содержащиеся в корневом наборе

удаленного процесса. Соответственно, пометка

твердый

сначала распространит-

ся локально, на заместителей процесса

Р,

а затем глобально, на смежные процес-

сы.

Другими словами, второй и третий шаги будут повторяться до тех пор, пока

пометки не перестанут распространяться глобально или локально. Когда ситуа-

ция стабилизируется, то есть прекратятся изменения пометок в процессах, вхо-

дящих в группу, алгоритм перейдет к следующему шагу. В нашем примере ре-

зультат повторений шагов 2 и 3 приведет к итоговой разметке, показанной на

рис.

4.28, в.

Пятый и последний шаг состоит из удаления недоступных объектов, включая

недоступные заместители, а также те заместители и скелетоны, которые были

помечены как

нетвердые.

Важно отметить, что последние недоступны из-за пре-

делов группы или из объектов корневого набора. Другими словами, нетвердые

заместители и скелетоны ссылаются только друг на друга и могут быть удалены.

Сборка мусора может в действительности выполняться в виде вторичного эф-

фекта локального распространения. Вместо явного удаления сущностей на по-

следнем шаге скелетоны, помеченные как

нетвердые,

могут заменяться ссылкой

на нуль. Таким образом, они могут быть обработаны позже, при повторном за-

пуске локальных сборщиков мусора. Кроме того, если объект, ассоциированный

с подобным скелетоном, становится недоступным, он также может быть обрабо-

тан при повторном проходе. Если заместители, локально ссылающиеся на подоб-

270

Глава

Именование

ный объект, также становятся недоступными, они могут быть помечены как

отсутствующие

и обработаны точно так же. Поэтому для безопасного использо-

вания локальных сборщиков мусора следует обрабатывать заместители, поме-

ченные как

отсутствующие,

после отправки сообщения об уменьшении счетчи-

ка скелетону удаленного процесса, ассоциированному с заместителем.

В иерархически организованных процессах в группах необходимо использо-

вать более масштабируемое решение для распределенной сборки мусора. Основ-

ная идея состоит в том, что низкоуровневые группы собирают свой мусор, а анализ

ссылок между группами оставляют на группы более высокого уровня. Посколь-

ку количество объектов в низкоуровневых группах, которые необходимо отсле-

живать, уменьшается, группы верхнего уровня в основном работают со схожим

количеством объектов, которые просто распределены по большей сети. Мы опус-

тим детали, которые при необходимости можно найти в

[255].

4.4. Итоги

Имена используются для ссылок на сущности. По сути, существует три основных

типа имен. Адрес

—

имя точки доступа, ассоциированной с сущностью, часто на-

зываемый просто адресом сущности. Другой тип имени

—

идентификатор. Он

имеет три свойства: каждая сущность имеет только один идентификатор, иденти-

фикатор указывает на единственную сущность и не может быть переназначен

другой. И наконец, имена, удобные для восприятия, предназначены для исполь-

зования людьми и представляют собой строку символов.

Имена организованы в пространства имен. Пространство имен может быть

представлено в виде графа именования, в узлах которого расположены именуе-

мые сущности, а метки на ребрах представляет собой имена, под которыми эти

сущности известны. Узлы, из которых выходит несколько ребер, представляют

собой наборы сущностей и известны также под названием направляющих узлов.

Крупномасштабные графы именования часто организуются в виде корневых ацик-

лических направленных графов.

Графы именования подходят для структурирования имен, удобных для вос-

приятия. Доступ к сущности может осуществляться посредством пути. Разреше-

ние имен

—

это процесс прохода по графу именования в поисках компонентов,

входящих в путь, по одному за раз. Крупномасштабный граф именования реали-

зуется путем распределения узлов по нескольким серверам имен. При разреше-

нии пути путем обхода графа именования, если разыскиваемый узел находится

на следующем сервере имен, то разрешение имен продолжается на нем.

Системы именования для имен, удобных для восприятия, невозможно исполь-

зовать для высокомобильных сущностей. Локализация мобильных сущностей

более успешно может быть произведена с помощью не зависящих от местополо-

жения идентификаторов. Существует четыре основных подхода к локализации

мобильных сущностей.

Первый подход состоит в использовании широковещательных или групповых

рассылок. Идентификатор сущности посылается широковещательной посылкой