Задачка про пропускную способность канала

[Nadir Zaitov]

Эту задачку описал пользователь, которого собеседовали на позицию senior systems engineer. Он отметил в описании задачи, что у него был свой ответ, по поводу которого он долго спорил с человеком, проводившим собеседование.

Предположим, у нас происходит 10 пакетных передач данных по беспроводной сети. Канал не очень качественный, так что есть вероятность 1/10, что пакет данных не будет передан. Трансмиттер всегда знает, удачно или неудачно был передан пакет данных. Когда передача неудачная, трансмиттер будет передавать пакет до тех пор, пока не преуспеет.
Вопрос: Какую пропускную способность канала получаем?

По версии пользователя, ответ должен был быть: 9 пакетов в секунду. Но человек, проводивший интервью, с ним не согласился, правда, ответа не назвал.

Предлагаю решить. Весьма простая задачка.

[German Stimban]

Предлагаю решить. Весьма простая задачка.
10-1-0,1-0,01-0,001... ?

[Nadir Zaitov]

Предлагаю решить. Весьма простая задачка.
10-1-0,1-0,01-0,001... ?а дорешать?

[Nadir Zaitov]

Игра состоит из одинаковых и независимых конов, в каждом из которых выигрыш происходит с вероятностью p. Когда игрок выигрывает, он получает 1 доллар, а когда проигрывает — платит 1 доллар. Как только его капитал достигает величины N долларов, он объявляется победителем и удаляется из казино.

Вопрос: Найдите вероятность того, что игрок рано или поздно проиграет все деньги, в зависимости от его стартового капитала K.

[Tadano]

а дорешать?8/9

[akai]

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

Не указано, за какое время происходит. Исходя из ответа пользователя, за 1 секунду? Тогда ответ - пропускная способность 9 пакетов в секунду.

Если это была математическая задачка, то совершенно зря приплели сюда сеть.

[YUU]

Если это была математическая задачка, то совершенно зря приплели сюда сеть.Это была практическая задача, собеседование же.

[akai]

Если это была математическая задачка, то совершенно зря приплели сюда сеть.Это была практическая задача, собеседование же.

Тогда следует выгнать интервьюера.

[Nadir Zaitov]

а дорешать?80/9

[Rooslan Khayrov]

10-1-0,1-0,01-0,001... ?
Т.е. если вероятность потери пакета p=0,5, средняя пропускная способность равна 0? А если p>0,5? ;-)
Можешь сформулировать, что именно ты пытался посчитать этой последовательностью? (А также прикинуть, что происходит с длиной очереди повторной передачи в сценарии, который ты рассматривал).

Мой ответ: мат. ожидание количества пакетов, необходимых для успешной передачи одного m = 1 + p + p^2 + ... = 1 + p / (1 - p) = 1 / (1 - p).
Соответственно, при базовой скорости передачи N пакетов/секунду средняя пропускная способность N' = N / m = N * (1 - p) пакетов/секунду.
Разумеется, всё в предположении, что пакеты независимы, что неверно для большинства реальных протоколов.

[Nadir Zaitov]

Мой ответ: ... N * (1 - p) пакетов/секунду.На самом деле все выкладки были излишни. Если прошло в секунду пакетов 9 и один обвалился, то прошло ровно 9 пакетов и скорость не может упасть дальше. (я так понят трансмиттер узнает о доставке по другому каналу и типа нас это не интересует).
Разумеется, всё в предположении, что пакеты независимы, что неверно для большинства реальных протоколов.Вы о чем? О том, что факт доставки прибежит обратно по тому же каналу?

[Rooslan Khayrov]

Вы о чем? О том, что факт доставки прибежит обратно по тому же каналу?
О том, что возможность отправки очередного пакета зависит от того, были ли успешно доставлены предыдущие. Т.е. если взять некое идеальное приближение TCP с окном, уже всё будет гораздо веселее.

[Евгений С]

О том, что возможность отправки очередного пакета зависит от того, были ли успешно доставлены предыдущие. Т.е. если взять некое идеальное приближение TCP с окном, уже всё будет гораздо веселее.

По мне, тут больше подходит Fibre Channel с его буфер кредитами, хотя и не совсем :)

[Nadir Zaitov]

О том, что возможность отправки очередного пакета зависит от того, были ли успешно доставлены предыдущие.Так ответ в любом случае придет так? Успешно прошел пакет или не успешно. Т.е. условное ожидание есть в любом случае. Если не прошел пакет, то этот пакет и будет очередным в очереди. При небольших потерях я думаю зависимости, точнее влияния такой зависимости на ширину канала на самом деле нет. Или я неправильно рассуждаю?

[Rooslan Khayrov]

Nadir Zaitov, в случае независимых пакетов можно не принимать во внимание время между отправкой пакета и получением подтверждения о доставке (неважно, получаем ли мы его по тому же каналу). Если это подтверждение не мгновенно, возможен полный простой канала в течение какого-то времени.

[Nadir Zaitov]

Игра состоит из одинаковых и независимых конов, в каждом из которых выигрыш происходит с вероятностью p. Когда игрок выигрывает, он получает 1 доллар, а когда проигрывает — платит 1 доллар. Как только его капитал достигает величины N долларов, он объявляется победителем и удаляется из казино.

Вопрос: Найдите вероятность того, что игрок рано или поздно проиграет все деньги, в зависимости от его стартового капитала K.
А задачка осталась.

[Nestik]

Эмм сори, а какая пропускная способность тут считается?
ИМХО
Потому как постановка задачи:
Какую пропускную способность канала получаем?
Совершенно не верна и сбивает с толку. В данном случае мы можем только оценить вероятность получить ту или иную пропускную способность причём любую от 0 и до 10.

[Евгений С]

Эмм сори, а какая пропускная способность тут считается?
ИМХО
Потому как постановка задачи:
Какую пропускную способность канала получаем?
Совершенно не верна и сбивает с толку. В данном случае мы можем только оценить вероятность получить ту или иную пропускную способность причём любую от 0 и до 10.

Больше стажу, в условиях задачи начисто отсутствует номинальная скорость канала, поэтому откуда отвечающие взяли за основу 10 пакетов в секунду, в корне неясно :)

[Nadir Zaitov]

За что куплено - за то и продано. Я формулировку не менял. Но из соображения логики, речь видимо шла о 10 пакетах в секунду. Иначе задача вообще не имеет смысла. Нет?

[dmazin]

ребят, а вы перепосылать пакет собираетесь? :)