Группа 5100. Осень 2013

[DKirov]

Для объявлений, обсуждения организационных и учебных вопросов.

[DKirov]

Выкладываю материалы: 2 конспекта и небольшой русскоязычный мануал по Ptolemy II.
Теорию можно и нужно брать не только с лекций, но и отсюда (например, такие вопросы, как методы формирования сетевых пакетов).

LEC_TELCOM_PART6_2007.PDF

Конспект 1

(623.58 Кб) Скачиваний: 1350

Особое внимание уделить страницам 60-64 и 66-70 (механизмы коммуникационной системы, формирование сетевых пакетов, методы управления потоком)

lec_telcom2005LITE.pdf

Конспект 2

(825.74 Кб) Скачиваний: 645

Ptolemy II.pdf

Сведения о Ptolemy II (на русском)

(1.38 Мб) Скачиваний: 1701

Еще полезные материалы к курсу выкладывались тут:
viewtopic.php?f=48&t=572#p5497

и тут (для 1й лабы):
viewtopic.php?f=48&t=301#p2420

[DKirov]

Выкладываю задание на ЛР1.

LAB1_2013.pdf

Задание на ЛР1

(149.91 Кб) Скачиваний: 1020

В документе есть 2 задания - основное и дополнительное. Обязательным является только основное. При этом выполнение дополнительного задания дает прекрасную возможность получить "простой" вариант к ЛР2. Рекомендую выполнить, т.к. дальше будет сложнее, но будет уже поздно.

Дополнительное задание можно выполнять до занятия 8 октября, а после этого занятия я буду раздавать варианты на ЛР2 более рандомно.

ВНИМАТЕЛЬНО прочтите рекомендации в задании и следуйте им, чтобы не пришлось ничего переделывать (а часто приходится).

Защита включает в себя:
- демонстрацию работающей модели (+ пояснение при необходимости, что как работает)
- беседа по отчету (главным образом - по выводам!)
- несколько (1-3) теоретических вопросов. Список вопросов невелик, и все ответы можно найти в конспектах (см. выше).

Условием выдачи варианта на следующую ЛР является демонстрация работающей модели предыдущей.

p.s. Также выкладываю вольный перевод мануала к модели в ЛР1, сделанный вашими предшественниками. Поможет быстрее разобраться, что к чему.

ABP_rus.pdf

Мануал к ЛР1 (русский)

(288.09 Кб) Скачиваний: 884

[DKirov]

Добрый день.

Выкладываю задание на 2,3 и 4 лабораторки.
Напоминаю, что для допуска надо сдать 3 работы. ЛР4 - для желающих отхватить "автомат".

TELCOM_LABS.DOC

(61 Кб) Скачиваний: 983

Рекомендации к ЛР2 смотрите в этом посте:
viewtopic.php?f=48&t=676&p=6084#p6084

ВНИМАНИЕ!

1) Рекомендации являются добровольно-принудительными. Особенно те, что связаны с защитой работы и представлением результатов. Также обязательно - подтверждения могут теряться, реализация механизма NACK, варьирование параметра а от 0.1 до 1000 (как минимум).

2) Теоретический материал по работе (если еще не успели пройти его на лекциях, а работу уже сделать ух как хочется), можно почитать в конспектах, что я выкладывал ранее. На следующем занятии также постараюсь пояснить некоторые моменты.

3) НАПОМИНАЮ: последнее занятие (практическое) пройдет, скорее всего, 22 октября. То есть фактически семестровый практический курс сжимаем в 2 месяца (без потери академ. часов). Лекции будут идти до конца семестра. Каждую неделю у нас с вами 2 занятия (с 18.50 до 21.20). Это значит, что каждую неделю до этого времени (а то и немного дольше) я готов сидеть и принимать ваши работы.

Прошу внимательно отнестись ко всему этому.

[ipavel]

В конспекте как-то совсем непонятно описаны Go-Back-N и Selective Repeat, делюсь годными визуализаторами: http://www.ccs-labs.org/teaching/rn/animations/gbn_sr/

[DKirov]

В конспекте как-то совсем непонятно описаны Go-Back-N и Selective Repeat, делюсь годными визуализаторами: http://www.ccs-labs.org/teaching/rn/animations/gbn_sr/

Годно, однако ж непонятно, почему в Go-Back-N повторная передача происходит исключительно по таймауту (не используются отрицательные подтверждения), а происходит она почему-то всей пачкой (одновременно передается сразу несколько пакетов).

[ipavel]

Одновременная отправка, очевидно, бага. Ну и там версия без NACK.
Вообще, по разным источникам в сети этот протокол может быть реализован совсем по-разному:
1. без NACK (как в визуализаторе)
2. с NACK, который отправляется только один раз на первый неверный пакет, а затем приемник просто молчит
3. с NACK, который отправляется только один раз на первый неверный пакет, а затем приемник отвечает ACK на последний успешно принятый пакет
4. c NACK на каждый ошибочный пакет, пока всё не будет хорошо.
По идее самый эффективный вариант - 2-й. Его предполагается реализовать?

[DKirov]

Одновременная отправка, очевидно, бага. Ну и там версия без NACK.
Вообще, по разным источникам в сети этот протокол может быть реализован совсем по-разному:
1. без NACK (как в визуализаторе)
2. с NACK, который отправляется только один раз на первый неверный пакет, а затем приемник просто молчит
3. с NACK, который отправляется только один раз на первый неверный пакет, а затем приемник отвечает ACK на последний успешно принятый пакет
4. c NACK на каждый ошибочный пакет, пока всё не будет хорошо.
По идее самый эффективный вариант - 2-й. Его предполагается реализовать?

Любой, на Ваше усмотрение. Кроме первого, пожалуй. Главное, чтобы правильно работало, и это можно было наглядно продемонстрировать.

[ipavel]

Можно ли вообще в Go-Back-N с использованием NACK и канала, теряющего подтверждения, подобрать таймаут правильно? Возможна следующая ситуация:
1. Передатчик послал пакеты 1, 2, 3, 4
2. Приемник принял пакеты 1, 2, 3, 4 и соответственно послал ack 1, 2, 3, 4.
3. До передатчика дошел только ack 1, остальное потерялось.
4. Передатчик по таймауту пересылает заново пакеты 2, 3, 4
5. Приемник получает пакет 2 и ругается, отсылая NACK. Теперь приемник не отвечает, пока ему не придет пакет 5.
6. Передатчик, получив NACK снова пересылает пакеты 2, 3, 4 ни на один из них не дождется ответа и будет циклически отваливаться на таймауте, передача заглохнет.
Пока что склоняюсь к тому, что таймаут должен быть больше, чем (размер_окна * RTT). Тогда 100% приемник рано или поздно получит тот пакет, который ждёт.
UPD: на самом деле точнее должно быть что-то вроде: размер_окна*(Tack+Tпак) + RTT

UPD2: на самом деле всё намного хуже Если были приняты все пакеты, но потерялись все ack, то передатчик перепошлёт заново всё окно, однако приемник его выплюнет, ибо будет ждать уже следующего пакета. Реальный случай в работе

[DKirov]

Можно ли вообще в Go-Back-N с использованием NACK и канала, теряющего подтверждения, подобрать таймаут правильно? Возможна следующая ситуация:
1. Передатчик послал пакеты 1, 2, 3, 4
2. Приемник принял пакеты 1, 2, 3, 4 и соответственно послал ack 1, 2, 3, 4.
3. До передатчика дошел только ack 1, остальное потерялось.
4. Передатчик по таймауту пересылает заново пакеты 2, 3, 4
5. Приемник получает пакет 2 и ругается, отсылая NACK. Теперь приемник не отвечает, пока ему не придет пакет 5.
6. Передатчик, получив NACK снова пересылает пакеты 2, 3, 4 ни на один из них не дождется ответа и будет циклически отваливаться на таймауте, передача заглохнет.
Пока что склоняюсь к тому, что таймаут должен быть больше, чем (размер_окна * RTT). Тогда 100% приемник рано или поздно получит тот пакет, который ждёт.
UPD: на самом деле точнее должно быть что-то вроде: размер_окна*(Tack+Tпак) + RTT

UPD2: на самом деле всё намного хуже Если были приняты все пакеты, но потерялись все ack, то передатчик перепошлёт заново всё окно, однако приемник его выплюнет, ибо будет ждать уже следующего пакета. Реальный случай в работе

Установка таймаута соразмерного времени передачи всего окна выглядит, скорее, как прикручивание костылей. Представьте себе ситуацию, когда размер окна на канальном уровне задан, к примеру, 65536. Система встанет. Если Вы вообще задумываетесь об этом, то искать надо косяк в протоколе (точнее не в протоколе, а в том, как Вы его поняли).

Есть еще такой пакет, называемый "запрос подтверждения" (RR). Почитайте, как метод Go back N описан в лекциях, которые я выкладывал. Страница 69. Насчет Вашего вопроса - почитайте правило номер 2. Там, кстати, и про отрицательный подтверждения есть. Только они называются REJ, а не NACK. Суть одна.

[ipavel]

1. Какие стратегии рекомендуется применять в л.р. 3? Если использовать стратегию повторной передачи только первого сегмента (согласно условию л.р.), стратегию приёма сегментов по порядку и одиночные подтверждения (как самые простые), то мы сталкиваемся с двумя проблемами:
а) После потери какого-либо пакета передатчик будет вынужден переотправлять всё из очереди "отправленных пакетов, не получивших подтверждения" по-одному, причём каждое - только по таймауту.
Пример: отправили пакеты 1, 2 ,3. Пакет 1 потерялся. Прошёл таймаут, отправляем только пакет 1. В ответ приходит подтсверждение и квитанция на отправку пакета 4. Отправляем пакет 4, но на него нет ответа, ибо приёмник ждёт пакет 2. Опять таймаут и так далее... В общем все-все последующие передачи будут повторными и делаться по таймауту каждая.
б) Теряется смысл в кредитах, по факту каждое подтверждение будет выдавать кредит на ещё один пакет.

2. Т.к. видимо использовать самые простые стратегии скорее всего не будет разрешено (см. первый вопрос), то очень хочется услышать пару советов, как в ptolemy можно организовать альтернативные стратегии малой кровью.

3. Как лучше всего передавать в рамках одного события несколько значений (номер подтверждения, выданные кредиты)? Попробовал сделать через массивы (по докам прошлогодних тем тут), не очень получилось. Any other ways?

[DKirov]

1. Какие стратегии рекомендуется применять в л.р. 3? Если использовать стратегию повторной передачи только первого сегмента (согласно условию л.р.), стратегию приёма сегментов по порядку и одиночные подтверждения (как самые простые), то мы сталкиваемся с двумя проблемами:
а) После потери какого-либо пакета передатчик будет вынужден переотправлять всё из очереди "отправленных пакетов, не получивших подтверждения" по-одному, причём каждое - только по таймауту.
Пример: отправили пакеты 1, 2 ,3. Пакет 1 потерялся. Прошёл таймаут, отправляем только пакет 1. В ответ приходит подтсверждение и квитанция на отправку пакета 4. Отправляем пакет 4, но на него нет ответа, ибо приёмник ждёт пакет 2. Опять таймаут и так далее... В общем все-все последующие передачи будут повторными и делаться по таймауту каждая.

Стратегия повторной передачи только первого сегмента - довольно эффективна вещь, если присмотреться. Гляньте, к примеру, тут: http://citforum.ru/nets/tcp/optimize02.shtml (ищите "только первый").
Другое дело, что в подобном случае политика приема сегментов "по порядку" вызовет большие задержки (фактически stop&wait получится в некотором роде), и потому неэффективна. Поэтому, как Вы правильно предположили, стоит воспользоваться более сложной стратегией "прием в окне". Здесь это оправдано.

б) Теряется смысл в кредитах, по факту каждое подтверждение будет выдавать кредит на ещё один пакет.

Тоже верно. Да, вот так все неинтересно. В простейшем случае и в условиях стабильного потока данных только от одного соединения это так и работает. Другой вопрос, что в реальных случаях так редко бывает. Хотите поинтереснее - поиграйтесь с кумулятивными подтверждениями. По крайней мере мне будет интересно

2. Т.к. видимо использовать самые простые стратегии скорее всего не будет разрешено (см. первый вопрос), то очень хочется услышать пару советов, как в ptolemy можно организовать альтернативные стратегии малой кровью.

Скажем так: "прием в окне" - обязательно, кумулятивные подтверждения - по желанию. Что касается приема в окне малой кровью - используйте массивы. Либо держите массив номеров сегментов и массив данных, либо по порядковому номеру байта вычисляйте нужный индекс в массиве (окне приемника), либо сдвигайте/раздвигайте массив при необходимости получить сегмент "между" уже полученными. Либо еще как-нибудь. Можно и посредством FSM все это сделать, можно на акторах.

3. Как лучше всего передавать в рамках одного события несколько значений (номер подтверждения, выданные кредиты)? Попробовал сделать через массивы (по докам прошлогодних тем тут), не очень получилось. Any other ways?

Токены могут передавать самые различные типы данных. Несколько значений в одной структуре данных - это запись (record). Поищите акторы RecordAssembler и RecordDisassembler. Должно помочь.

[ipavel]

Это то неловкое чувство, когда вроде всё понятно уже, но упираешься в инструментарий. Крайне туго с реализацией двух вещей внутри конечного автомата в ptolemy:
1. очередь с возможностью удалять элементы из середины (причем не по индексу в очереди, а самому элементу). В принципе, это можно организовать с помощью Actor'ов ArrayAppend и ArrayRemoveElement, но тогда придется всё это выносить из автомата. Да и интуиция подсказывает, что это очень корявая реализация.
2. для правильной реализации приёма в окне логика работы над массивом сильно сложнее:
а) Если пришел пакет в начале окна, то сдвигаем окно на столько, сколько принятых пакетов с начала окна было (например, если пришло всё окно кроме первого пакета, а потом он переслался как раз. тогда окно сдвигается совсем целиком и выдаётся огромный кредит)
б) Иначе надо как-то в середину массива вставить элемент.
И вот с такой логикой неясно, куда копать.

http://ptolemy.eecs.berkeley.edu/ptolem ... ssions.pdf
Согласно этому доку в ptolemy есть массивы, но там же вообще не описаны операции над ними, как над структурами данных И в общем-то непонятно, это именно java-массивы или это всё же java-списки с возможностью удаления из середины.

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

[DKirov]

Это то неловкое чувство, когда вроде всё понятно уже, но упираешься в инструментарий. Крайне туго с реализацией двух вещей внутри конечного автомата в ptolemy:
1. очередь с возможностью удалять элементы из середины (причем не по индексу в очереди, а самому элементу). В принципе, это можно организовать с помощью Actor'ов ArrayAppend и ArrayRemoveElement, но тогда придется всё это выносить из автомата. Да и интуиция подсказывает, что это очень корявая реализация.
2. для правильной реализации приёма в окне логика работы над массивом сильно сложнее:
а) Если пришел пакет в начале окна, то сдвигаем окно на столько, сколько принятых пакетов с начала окна было (например, если пришло всё окно кроме первого пакета, а потом он переслался как раз. тогда окно сдвигается совсем целиком и выдаётся огромный кредит)
б) Иначе надо как-то в середину массива вставить элемент.
И вот с такой логикой неясно, куда копать.

http://ptolemy.eecs.berkeley.edu/ptolem ... ssions.pdf
Согласно этому доку в ptolemy есть массивы, но там же вообще не описаны операции над ними, как над структурами данных И в общем-то непонятно, это именно java-массивы или это всё же java-списки с возможностью удаления из середины.

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

Насчет операций с массивами именно в автомате ничего бодрящего предложить не могу. Могу поискать маны, но сдается мне, что гуглить Вы умеете не хуже меня
Что могу сказать навскидку: попробуйте завести в автомате несколько переменных. Допустим, номер последнего подтвержденного сегмента, номер последнего полученного пакета + какой-нибудь буферный индекс/номер. Может помочь. Необязательно также мутить сортировку или сдвигание/раздвигание массива. Можете попробовать сделать окно приемника небольшим (к примеру, 10 сегментов). И класть каждый сегмент по тому индексу, по которому нужно (сразу).
Если не получится, то попробуйте действительно вынести эту логику из автомата и сделать на акторах. В конце концов

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

Еще всегда можно написать свою собственную логику в виде джава-кода. Сделать свой актор со своей логикой. С джавой, думаю, знакомы. Оператор switch (если хотите сами написать автомат), думаю, тоже знаете.

Если совсем упретесь, то можете сделать прием по порядку. Работать будет не столь эффективно, но будет. К тому же в задании надо экспериментировать с потерями 0 и 0.1 (в принципе достаточно реальные значения и в жизни)

[DKirov]

Добрый день.

Напоминаю для тех, кто не знает либо плохо понял: у вас осталось 4 практических занятия - сегодня (8 октября), 15го, 22го и 29го.
После этого занятий НЕ БУДЕТ.

Для допуска к экзамену надо сдать 3 (три) лабораторные работы.

Пока результаты как-то не очень:

- Варианты на ЛР1 получили: 24 (все)
- Защитили ЛР1: 10
- Защитили ЛР2: 4
- Защитили ЛР3: 0

Настоятельно рекомендую сдавать работы.

[DKirov]

Здравствуйте.

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

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

p.s. В связи с наметившимся большим количеством желающих сдать ЛР4 и рассчитывающих на автомат, напоминаю: одно лишь наличие отчета не является достаточным для получения автомата. Неспособность объяснить результаты или ответить на теор. вопросы сводит эту вероятность к минимуму. Готовьтесь.

[ipavel]

Павел Валерьевич, у нас конструктивное предложение.
В связи с тем, что курс лабораторных проходил в очень активном режиме и завершился, многие темы мы были вынуждены изучать самостоятельно, забегая вперед паровоза.
* Ряд личностей заработали оценку 5 автоматом по итогам сдачи 4 л/р.
* Также ряд личностей, насколько я понял, рекомендован к получению оценки 4 автоматом (народ интересуется, кому выпала такая радость).
Вышеобозначенные личности скорее всего готовы на автоматы, и поэтому особого смысла в дальнейшем совместном отнимании времени немного.

Предложение заключается в следующем: чтобы не отнимать в первую очередь Ваше время на проведение лекций по изученным нами самостоятельно темам (вместо этого можно, например, устроить консультацию в начале лекции, и, если вопросов не окажется, пропустить эти разделы). Вообще, многое ли еще есть в лекционном курсе, что не было затронуто в практикуме?
Ещё люди спрашивают, можете ли Вы принимать лабораторные работы (возможно, в лекционные часы, если они сократятся согласно предложению выше)

[kustarev]

Добрый день.

1) Принимать лабораторные работы буду, но через 2-3 недели, к концу ноября.
2) То, что было на лабораторных работах, на лекциях уже также было. Следующий материал - о методах управления потоком и предотвращения перегрузки в сетях TCP (еще должен быть материал по сетям с коммутацией пакетов (типа ATM), но до них по времени не доберемся).
3) Если посещение лекций Вам не очень удобно по времени и не хочется затягивать процесс (учитывая невысокую эффективность лекционного "начитывания" материала), могу предложить список вопросов с указанием соответствующих глав в книге (за основу возьму книгу Столлингса). Вы готовите вопросы, сдаете по ним экзамен (исключение - "автоматчики", см.ниже). Но это должно быть согласованное решение всей группы.
4) Получение "автомата" не означает полное отсутствие необходимости знать теоретический материал. "Автоматчик", в том числе отличник, должен пройти несложное устное собеседование. Если он ответит на несложные вопросы по выполненному лабораторному курсу, то подтверждает свой уровень и получает "автомат". Нет - сдает экзамен.
5) Сегодня было занятие по расписанию, а Вас не было. Почему?

ЖДУ РЕАКЦИЮ!!!

С уважением,
Кустарев П.В.

[DKirov]

На всякий случай: обязательным условием защиты каждой лабораторной работы (1-4) для каждого студента был ответ на 2-3 вопроса из соответствующей области теории. Поэтому каждый, кто рекомендован на автомат, уже продемонстрировал знание теории на соответствующую оценку.

[ipavel]

Посовещались с группой, вариант со списком вопросов и самостоятельной подготовкой нас устраивает. Спасибо.
Когда можно подходить подтверждать свои знания - во время лекции на ближайшем занятии или на зачетной неделе/консультации/экзамене? Как говорилось выше, по теории нас тоже погоняли при защите, так что мы вполне готовы.
Я отсутствовал ввиду несколько иного понимания автомата до Вашего ответа на пост выше. За группу отвечать не могу, полагаю, у всех возникло схожее расхождение в понимании условий сдачи курса.
Прошу простить за долгую реакцию.