Требуется проимитировать работу системы и оценить примерный выигрыш провайдера от установки прокси-сервера.

Попробуем формализовать ситуацию. Пусть к провайдеру подключено N пользователей. Их активность неравномерна: большинство делает запросы сравнительно редко, а активное меньшинство - очень часто (можно использовать нормальное распределение вероятностей, рис. 7.1).

Распределение активности среди множества пользователей считается постоянным. Так, если пользователь с идентификатором 12345 очень активен, он останется активным на протяжении всего процесса моделирования (хотя частота запросов и может несколько меняться).Точпо так же распределение запросов по сайтам не является равномерным.

С большей вероятностью пользователь заходит на какой-либо популярный ресурс (будем считать, что всего в интернете располагается S сайтов) и запрашивает с него М мегабайт данных. Как и в случае с активностью пользователей, мы полагаем, что популярность ресурса - величина в целом постоянная (хотя и подверженная колебаниям).

Вероятность того, что человек скачивает малый объём данных, высока. Вероятность скачивания большого объёма мала. Здесь можно воспользоваться правой частью кривой стандартного нормального распределения. Средний объём скачиваемой информации за один запрос оставляю на ваше усмотрение, но он, вообше говоря, не так уж и важен.

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

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

Изначально кэш сервера пуст. Первая итерация моделирования состоит из обработки Q запросов пользователей (значение Q выбирается произвольно), после чего прокси-сервер скачивает Р наиболее популярных страниц. Значение Р представляет собой объём сервера, измеряемый для простоты в страницах, а не в мегабайтах. Рекомендую поэкспериментировать с различными значениями Р.

Каждая последующая итерация состоит в обработке очередной порции из Q запросов. При поступлении очередного запроса производятся действия (не забывайте заодно считать доходы провайдера):

1. Адрес запрошенного ресурса запоминается (чтобы получить статисти-

ку по всем Q запросам).

2. Если сайт не находится в кэше, пользователю возврап1ается содержи-

мое сайта из глобальной сети.

3. Если сайт находится в кэше, определяется, устарела ли информация

(вероятность устаревания выше для популярных сайтов - действительно, если сайт редко обновляется, он не будет популярным).

4. Если информация устарела, сайт заново скачивается из интернета.

5. Если не устарела, пользователю возвращается локальная копия из

кэша.

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

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

Подсказка

Как видно из условия задачи, решение будет скорее громоздким, чем сложным. Поэтому я решил ох-раничиться подсказкой лишь в одном затрудне-1ШИ - в генерации случайных чисел, имеющих нормальное распределение.

Конкретный вид графика зависит от двух параметров - стандартного отклонения (standard deviation) и среднего (mean). Стандартное отклонение влияет на крутизну кривой, а среднее соответствует наиболее часто встречающейся случайной величине.

Итак, предгюложим, что требуется получить случайную величину, распределённую нормально с параметрами Mean и StdDev. Сделать это можно с помощью следующего алгоритма:

X = случайное число в промежутке [О, 1) у = случайное число в промежутке [О, 1) U = sqrt(-2 * Log(x)) * Cos(2 * Pi * у) результат = u * StdDev + Mean

Если провести несколько тысяч экспериментов, график частот появления различных генерируемых случайных величин будет соответствовать нормальному распределению (рис. 7.4).

7.2.5. Автострада

2 Считается, что эта операция достаётся провайдеру бесплатно (что недалеко от истины: про-

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

*г1ппт 11 I I I I I 11 1 I I I I 111 I гI I I I I I I I I I I I 11 I I I 11 I I I I I I I I [ I

......II lllll T 1*1

Рис 7.4. Распределение сгенерированных случайных чисел

Моделирование автомобильных пробок

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

Автомобильные пробки - не самое приятное явление. Думаю, жители крупных городов легко со мной согласятся. Центр обычно и так перегружен транспортом, а ведь и какую-нибудь улицу могут перекрыть или авария посреди дороги произойдёт. Однако не только в городе случаются пробки. Оживлённая скоростная автострада тоже может стать источником заторов. Но если в центре пробки можно сократить при помощи грамотного управления потоками автомобилей, то на загородном шоссе большое значение приобретает контроль скорости.

На первый взгляд скорост?) движения транспорта по автостраде мало связана с вероятностью возникновения пробок, но на самом деле это не так.

Рассмотрим для простоты узкую однополосную дорогу Если машин немного, ехать по такой трассе одно удовольствие. Если даже машин предостаточно, они спокойно проезжают, выстроившись в колонну и держа предусмотренную правилами дистанцию (маловероятно в наших условиях, но пусть будет так). Теперь представьте себе, что на дорогу выбежала собака. Или человек. Или у водителя что-то забарахлило в двигателе, и он начал резко сбавлять скорость, чтобы съехать на обочину Короче говоря, предположим,

3 Charles Wetherell. Etudes for programmers. Prenticie-Hall, N J, 1978 (русский перевод: Ч. Уэзе-

релл. Этюды для программистов. Москва, Мир, 1982).

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

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

Притормозившая машина образует за собой огромный хвост . Со временем плотность этого хвоста (то есть количество машин на единицу расстояния) уменьшается, а длина - растёт. Спустя какое-то время плотность машин в окрестности затора приближается к нормальной плотности движения, и пробка рассасывается.

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

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

В программе моделируется фиксированный участок автострады, скажем. Length километров (типичное значение - 10-15). С помощью генератора автомобилей в начале трассы создаётся очередной автомобиль каждые Interval секунд (5-10). Машина движется со скоростью Speed км/ч (тут уж фантазию можно проявить в полной мере!)

Генератор помех раз в TInterval секунд с какой-то вероятностью устраивает помеху случайно выбранному автомобилю. Помеха приводит к тому, что скорость этого автомобиля равномерно снижается до нуля (за каждую секунду машина сбавляет 15 км/ч), а затем возрастает до Speed (опять же, с каждой секундой скорость растёт на 15 км/ч).

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

7 Зак.772

Когда впереди идущий автомобиль начинает разгон, водитель следующей машины реагирует на это, и спустя 0.2 секунды тоже увеличивает скорость, если расстояние между автомобилями составляет Distance метров или больше. Если же автомобили находятся слишком близко, водитель сначала дожидается, пока впереди идущая машина не отъедет на расстояние Distance, и лишь после этого начинает разгон.

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

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

Решение

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

Во-первых, мы полагаем, что поломка у машины длится фиксированное время. Во-вторых, время реагирования у любого водителя одно и то же. В-третьих, скорость изменения скорости всех машин всегда одна и та же.

Перейдём теперь к программной реализации. Для начала введём некоторые глобальные переменные:

int highway length = 10000; int car interval = 500; int trouble interval = 1000; double max speed = 140; float car distance = 20.; int trouble counter = 0; int counter = 0; int car number = 0; int ininute counter = 0; int minute interval = 600;

int ininutes passed = 0; int cars on way = 0; int cars passed = 0; float traffic = 0; int modeling speed = 1;

длина участка в метрах sec/100 sec/100 km/h m

счётчик генератора помех счётчик генератора автомобилей номерной знак авто (идентификатор) счётчик долей минут количество итераций таймера для истечения одной минуты счётчик прошедших минут машин на трассе машин прошло трассу пропускная способность скорость моделирования

Тип данных Автомобиль представлен классом ТСаг:

class ТСаг {

public:

ТСаг(const double speed, const int nm); -TCar(){}

void UpDate(); void MakeTrouble()

В этой функции будут происходить все изменения

Создать помеху автомобилю

Стоит пояснить назначение переменных timer on и reaction tiine. Как было сказано в постановке задачи, водитель реагирует не сразу, а спустя некоторое время (в условии указано конкретное значение - 0.2 секунды). Флаг timeron включает обратный отсчёт времени, спустя которое водитель отреагирует на уже произошедшие изменения на дороге. Переменная reactiontime представляет собой длительность реагирования, обратный счётчик. Как только его значение станет равным нулю, водитель отреа-- гирует на события на дороге.

Объявим теперь возможные состояния автомобиля на нашей автостраде:

enum TCarState {csNormal, csTroubleSolved, csTrouble,

csTroubleNoticed, csOvertake}; Кратко поясню каждое:

csNormal - ОНО И есть нормальное, ничего не делаем;

csTrouble - что-то случилось с автомобилем (работа генератора помех);

csTroubleSolved - проблема решилась; csTroubleNoticed - машина впереди сбрасывает скорость;