задание по предмету телекоммуникационные технологии

Алгоритм «дырявого ведра» разработан для проверки соответствия поступающего потока ячеек принятому соглашению по трафику. Под «дырявым ведром» понимается аналогия с ведром, имеющим течь. Скорость течи соответствует скорости потока ячеек, установленного трафик-контрактом. Объем ведра – глубине стека, которая определяет допуск на неравномерность поступления ячеек. Прибытие каждой ячейки ассоциируется с поступлением чаши воды, которая должна вылиться в «дырявое ведро». Порции воды в чаше являются неделимыми. Переполнение ведра не допускается. Если чаша может вылиться в ведро без его переполнения, то такая ячейка называется конформной, если ячейка теряется, т.е. выливается мимо ведра, чтобы избежать его переполнения, то такая ячейка называется неконформной. Считается, что в каждом интервале времени, который будем называть тактом, из ведра выливается одна единица объема, т.е. расход составляет R = 1 ед/такт. Таким образом, при выполнении задания требуется формализовать задачу, рассчитать объем воды в ведре по тактам и разделить общий поток поступающих ячеек на две части: поток конформных и поток неконформных ячеек. Прежде чем приступить к решению задачи сделаем замечание относительно так называемой проблемы «пустого ведра», которая связана с тем, что в одном такте происходят два неразличимых во времени события: поступлением в ведро чаши с водой и расходом порции воды. Понятно, что из пустого ведра вылиться ничего не может, т.е. остаток воды в ведре не может быть отрицательным. Поэтому в зависимости от соотношения моментов наступления событий остаток воды в ведре на конец такта будет различаться. В первом варианте момент поступления чаши с водой приходится на конец такта, поэтому остаток воды, вылитой в пустое ведро, будет равен объему чаши. Во втором варианте, порция воды из чаши выливается в начале такта и остаток воды в ведре равен (Vяч – R). Различие между двумя вариантами проявляется в случае сравнительно редкого потока ячеек, когда ведро значительную часть времени остается пустым, и при соизмеримых объемах Vв и Vяч, как в нашем случае. Для определенности далее будем рассматривать первый вариант, при котором Vост = Vяч для нулевых начальных условий V0 = 0.