Имитационное моделирование Преподаватель: Доцент Кафедры ВС, к.т.н. Поляков Артем Юрьевич © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» ФГОБУ ВПО "СибГУТИ" Кафедра вычислительных систем ЯЗЫКИ ПРОГРАММИРОВАНИЯ / ПРОГРАММИРОВАНИЕ

ИМИТАЦИОННОЕ МОДЕЛИРОВАНИЕ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 2

Имитационное моделирование © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 3 Имитационное моделирование – это метод исследования, при котором изучаемая система заменяется моделью, с достаточной точностью описывающей реальную систему. С моделью проводятся эксперименты с целью получения информации об исходной системе. Экспериментирование с моделью называют имитацией. C, C++, Java C, C++, Java

автомобиль движется по прямой на дистанцию S; задана частота γ вращения колеса и его начальный радиус R'. после каждого оборота происходит стирание покрышки согласно зависимости f(R', n), где n – количество оборотов, сделанное колесом. Функция f(R',n) имеет ступенчатый вид: необходимо построить график зависимости скорости автомобиля от пройденного пути Моделирование движения автомобиля © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 4

Выделение моделируемых процессов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 5 I II III

Математическое описание процесса © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 6 Входные данные: S – длина пути; R' – начальный радиус колеса; γ – частота вращения колеса; f(R', n) – радиус колеса на n-ом обороте. Описание процесса движения: За полный оборот колесо продвигается вперед на расстояние, равное длине внешней окружности: l = 2πR l

Математическое описание процесса © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 7 Входные данные: S – длина пути; R' – начальный радиус колеса; γ – частота вращения колеса; f (R', n) – радиус колеса на n-ом обороте. Описание процесса движения: За полный оборот колесо продвигается вперед на расстояние, равное длине внешней окружности: l = 2πR. Один оборот выполняется за (1/γ) с. Остаток дистанции уменьшается на текущую длину окружности: S = S – l После каждого оборота радиус колеса изменяется согласно закону: R = f (R', n). Движение продолжается до тех пор, пока S > 0.

Программа имитационного моделирования © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 8 #include #define PI double f(double R, int n, int w) { return R *(n/w); } int main() { double S, gamma, R1, R, dR, T = 0, v; int n = 0, i, w, ofr = 1000; FILE *out; printf("Input S, gamma, R, dR, wear: "); scanf("%lf %lf %lf %lf %d", &S, &gamma, &R1, &dR, &w); out = fopen("output.dat","w"); fprintf(out,"n\tR\t\tS\t\tT\t\tv\n"); R = R1; S *= 1000; while( S > 0 && (R >= (R1-dR)) ){ S = S - 2*PI*R; T = T + 1/gamma; v = 3.6*2*PI*R*gamma; if( n % ofr == 0) fprintf(out,"%d %.3lf %.3lf %.3lf %.1lf %.1lf %.1lf\n", n,R,S,v,T,T/3600,T/3600/24); n++; R=f(R1,n,w); } fclose(out); }

Программа имитационного моделирования (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 9 #include #define PI double f(double R, int n, int w) { return R *(n/w); } int main() { double S, gamma, R1, R, dR, T = 0, v; int n = 0, i, w, ofr = 1000; FILE *out; printf("Input S, gamma, R, dR, wear: "); scanf("%lf %lf %lf %lf %d",&S,&gamma,&R1,&dR,&w); out = fopen("output.dat","w"); fprintf(out,"n\tR\t\tS\t\tT\t\tv\n"); R = R1; S *= 1000;...

Программа имитационного моделирования (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 10 R = R1; S *= 1000; while( S > 0 && (R >= (R1-dR)) ){ S = S - 2*PI*R; T = T + 1/gamma; v = 3.6*2*PI*R*gamma; if( n % ofr == 0) fprintf(out,"%d %.3lf %.3lf " "%.3lf %.1lf %.1lf %.1lf\n", n,R,S,v,T,T/3600,T/3600/24); n++; R=f(R1,n,w); }

Результаты моделирования (зависимость скорости от числа оборотов) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 11 S = 7000 км, γ = 12,5 об./с R = 0,4; ΔR=0,3; износ 1мм/10 5 об. R = 0,4; ΔR=0,3; износ 1мм/10 5 об. R = 0,35; ΔR=0,2; износ 1мм/310 5 об. R = 0,35; ΔR=0,2; износ 1мм/310 5 об. R = 0,35; ΔR=0,4; износ 1мм/10 5 об. R = 0,35; ΔR=0,4; износ 1мм/10 5 об.

Зависимость скорости от пройденного пути © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 12 R = 0,4; ΔR=0,3; износ 1мм/10 5 об. R = 0,4; ΔR=0,3; износ 1мм/10 5 об.

Время в имитационном моделировании © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 13 При имитационном моделировании различают три вида времени. 1. Время реальной системы – это время, в котором функционирует моделируемая система. 2. Модельное время – это "искусственное" время, в котором "живет" модель или другими словами это время, которое является имитацией, прообразом (моделью) времени реальной системы. 3. Реальное время это время, в котором живет исследователь, компьютер или другими словами это время необходимое для моделирования (затратное время).

Продвижение модельного времени © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 14 R = R1; S *= 1000; while( S > 0 && (R >= (R1-dR)) ){ S = S - 2*PI*R; T = T + 1/gamma; [...] n++; R=f(R1,n,w); } Один оборот выполняется за (1/γ) с. l

АГРЕГИРОВАННЫЙ КАНАЛ ПЕРЕДАЧИ ДАННЫХ © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 15

Агрегированный канал передачи данных © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 16 Агрегация (агрегирование) (лат. aggregatio «присоединение») – процесс объединения элементов в одну систему Мб/с 10 Мб/с 100 Мб/с 1.Link_aggregation: 2.Bonding driver (Linux) Link Aggregation Control Protocol (LACP): IEEE 802.1ax/IEEE 802.3ad 4.Cisco EtherChannel (Port Aggregation Protocol – PAgP)

Канал TCP/IP © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 17 Входной поток байт Система 1 Выходной поток байт Система 2 NIC driver TCP/IP/Ethernet Поток пакетов TCP/IP/Ethernet NIC driver Поток пакетов

Стек протоколов TCP/IP © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 18

Формирование сетевых пакетов © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 19 Программа TCP Передаваемый буфер TCP сегменты n n... IP IP датаграмы n n Ethernet Ethernet кадры n n Среда передачи

Стек протоколов TCP/IP © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 20 Протокол IP (сетевой уровень модели ISO/OSI) обеспечивает негарантированную доставку пакета на узел-получатель, описываемый IP-адресом. Протокол TCP (транспортный уровень модели ISO/OSI) обеспечивает: 1. Гарантированную доставку данных (повторная передача при потерях). 2. Регулировка нагрузки на сеть. 3. Восстановление исходного порядка следования сетевых пакетов. Internet/LAN to: Internet/LAN

Агрегированный канал TCP/IP © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 21 Входной поток байт Система 1 Выходной поток байт Система 2 driver NIC 1 TCP/IP Распределение driver NIC 2 driver NIC N …... Канал 1 (b 1 Мб/c) Канал 2 (b 2 Мб/c) Канал N (b N Мб/c) driver NIC 1 driver NIC 2 driver NIC N … Объединение Ethernet MAC

Агрегированный канал TCP/IP (выделение моделируемых процессов) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 22 Входной поток байт Система 1 Выходной поток байт Система 2 NIC 1 TCP/IP Распределение NIC 2 NIC N NIC 1 Объединение NIC 2 NIC N ……... Канал 1 (b 1 Мб/c) Канал 2 (b 2 Мб/c) Канал N (b N Мб/c) пакеты Моделируемый фрагмент системы

Анализ агрегированного канала на физическом уровне © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 23 Дано Дана система из двух сетевых узлов, связанных N физическими каналами. Для каждого канала i известна его пропускная способность b i [b i ] = Мбит/с. Максимальный размер m сетевого пакета задается из промежутка [1500, 16000], [m] = байт. По описанному каналу выполняется передача информации размером S байт (S mod m = 0). Необходимо Определить пропускную способность агрегированного логического канала и количество инверсий в выходном потоке пакетов. Считать, что передаваемая информация разбивается на пакеты максимального размера (за исключением, быть может, последнего).

Схема агрегированного канала © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 24 Система 1 и Система 2 взаимодействуют через N физических каналов связи. Для каждого канала определена его пропускная способность b i, i = 1, …, N. Алгоритм распределения сопоставляет каждому передаваемому сетевому пакету один из доступных каналов. Алгоритм объединения извлекает пакеты по мере их поступления и помещает в выходной поток. Алгоритм распределения Система 1 Алгоритм объединения Выходной поток Система 2 Логический канал... Канал 1 (b 1 Мб/c) Канал 2 (b 2 Мб/c) Канал N (b N Мб/c) Входной поток

Программная имитация физического канала связи © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 25 Для взаимодействия операционной системы и сетевого адаптера обычно используются так называемые "кольцевые буферы", которые представляют собой структуру данных очередь, построенную на базе статического массива. NIC driver NIC driver

Кольцевой буфер © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 26 Дан статический массив Q, размер Q составляет n элементов. Требуется организовать на основе Q кольцевой буфер вместимостью (n – 1) элемент. Введем два дополнительных индекса: head и tail. head – индекс первого элемента очереди. tail – индекс первого свободного элемента очереди. Если head = tail, то очередь пуста. Если (tail mod n) + 1= head, то очередь заполнена. Изменение индексов tail и head производится только в одном направлении по модулю n: tail = (tail mod n) + 1, head = (head mod n) + 1 head tail head tail head tail

Кольцевой буфер (2) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 27 Дан статический массив Q, размер Q составляет n элементов. Требуется организовать на основе Q кольцевой буфер вместимостью (n – 1) элемент. Введем два дополнительных индекса: head и tail. head – индекс первого элемента очереди. tail – индекс первого свободного элемента очереди. Если head = tail, то очередь пуста. Если (tail mod n) + 1= head, то очередь заполнена. Изменение индексов tail и head производится только в одном направлении по модулю n: tail = (tail mod n) + 1, head = (head mod n) + 1 head tail head tail head tail

Кольцевой буфер (самостоятельно) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 28 Дан статический массив Q, размер Q составляет n элементов. Требуется организовать на основе Q кольцевой буфер вместимостью (n – 1) элемент. Введем два дополнительных индекса: head и tail. head – индекс первого элемента очереди. tail – индекс первого свободного элемента очереди. Если head = tail, то очередь пуста. Если (tail mod n) + 1= head, то очередь заполнена. Изменение индексов tail и head производится только в одном направлении по модулю n: tail = (tail mod n) + 1, head = (head mod n) + 1 Q 1.Вставка 5-ти элементов. 2.Извлечение одного. 3.Вставка 2-х элементов. 4.Извлечение 3-х элементов.

Программная имитация физического канала связи © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 29 Для взаимодействия операционной системы и сетевого адаптера обычно используются так называемые "кольцевые буферы", которые представляют собой структуру данных очередь, построенную на базе статического массива. При передаче данных через физический канал типа "точка-точка" кольцевые буферы будут работать синхронно. Поэтому для упрощения модели будем представлять физический канал связи, как одиночный кольцевой буфер: NIC driver NIC driver

Синхронная работа передающей и принимающей очереди взаимодействующих устройств © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 30 NIC driver NIC driver NIC driver NIC driver NIC driver NIC driver send_qreceive_q

Оценка времени передачи сетевых пакетов по физическому каналу связи © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 31 b=4 Для передачи пакета размером m байт по каналу связи с пропускной способностью b байт/с требуется время t ([t] = c), которое определяется по формуле : m 1 (12) m 1 (12) m 2 (24) m 2 (24) m 3 () m 3 () t

Функциональная схема системы моделирования © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 32 Узел 1 Канал 1 Канал 2 Канал N Узел 2 Таймер... 1) Узел 1 – передающий узел; 2) Узел 2 – принимающий узел; 3) Канал i – канал передачи данных; 4) Таймер – модельное время.

Продвижение модельного времени (проблема различия в пропускных способностях) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» m 1 (24) m 2 (24) m 3 (16) m 4 (16) m 4 (16) b=4 b=2b=2 m 1, m 2, m 3, m 4, … m 2, m 4, m 1, m 3, …

Продвижение модельного времени (влияние пропускных способностей) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» m 1 (24) m 2 (24) m 3 (16) m 4 (16) m 4 (16) b=4 b=2b=2 m 1, m 2, m 3, m 4, … На i-м шаге извлекается i-й кадр и время изменяется на время его доставки

Функциональная схема системы моделирования © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 35 Узел 1 Канал 1 Канал 2 Канал N Узел 2 Таймер (время отправки)... T T T1T1 T1T1 T2T2 T2T2 T3T3 T3T3 Продвижение времени при получении кадра Используется для определения времени отправки кадра Расчет времени доставки кадра размером s по i-му каналу: t отпр = max(T, T i ) t дост = t отпр + s/b i Расчет времени доставки кадра размером s по i-му каналу: t отпр = max(T, T i ) t дост = t отпр + s/b i T i = t дост if T i > T then T = T i T i = t дост if T i > T then T = T i

Пример продвижения модельного времени © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 36 Шаг Входные кадры, Б Состояние модели (длина очереди = 2 кадра) Замечания , 30, 50, 90, 200 v 1 = 10 B/c, T 1 = 0 c v 2 = 5 B/c, T 2 = 0 c T = 0 c Исходное состояние v 1 = 10 B/c, T 1 = 0 c v 2 = 5 B/c, T 2 = 0 c T = 0 c Кадры распределены по алгоритму RoundRobin (0с,50), (0с,100) (0с,90), (0с,30)

Пример продвижения модельного времени © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 37 Шаг Входные кадры, Б Состояние модели (длина очереди = 2 кадра) Замечания 4. v 1 = 10 B/c, T 1 = 0 c v 2 = 5 B/c, T 2 = 6 c T = 6 c (0с,50), (0с,100) (0с,90) v 1 = 10 B/c, T 1 = 0 c v 2 = 5 B/c, T 2 = 0 c T = 0 c τ i = s i / v i + max(T i,t i ) τ 1 = 100/10+max(0,0) = = 10 c τ 2 = 30/5+max(0,0) = = 6 c => Первым приходит кадр из 2-го канала (0с,50), (0с,100) (0с,90), (0с,30) τ i = s i / v i + max(T i,t i ) τ 1 = 100/10+max(0,0) = = 10 c τ 2 = 90/5+max(6,0) = = 24 c => Первым приходит кадр из 1-го канала 200

Пример продвижения модельного времени © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 38 Шаг Входные кадры, Б Состояние модели (длина очереди = 2 кадра) Замечания 6. v 1 = 10 B/c, T 1 = 10 c v 2 = 5 B/c, T 2 = 6 c T = 10 c (10с,200), (0с,50) (0с,90) τ i = s i / v i + max(T i,t i ) τ 1 = 50/10+max(10,0) = = 15 c τ 2 = 90/5+max(6,0) = = 24 c => Первым приходит кадр из 1-го канала 5. v 1 = 10 B/c, T 1 = 10 c v 2 = 5 B/c, T 2 = 6 c T = 10 c (10с,200), (0с,50) (0с,90) Пакет размером 200 байт распределяется алгоритмом RoundRobin на первый канал 200

Пример продвижения модельного времени © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 39 Шаг Входные кадры, Б Состояние модели (длина очереди = 2 кадра) Замечания 8. v 1 = 10 B/c, T 1 = 15 c v 2 = 5 B/c, T 2 = 24 c T = 24 c (10с,200) τ i = s i / v i + max(T i,t i ) τ 1 = 200/10+max(15,10) = = 35 c 7. v 1 = 10 B/c, T 1 = 15 c v 2 = 5 B/c, T 2 = 6 c T = 15 c (10с,200) (0с,90) τ i = s i / v i + max(T i,t i ) τ 1 = 200/10+max(15,10) = = 35 c τ 2 = 90/5+max(6,0) = = 24 c => Первым приходит кадр из 2-го канала

Пример продвижения модельного времени © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 40 Шаг Входные кадры, Б Состояние модели (длина очереди = 2 кадра) Замечания 9. v 1 = 10 B/c, T 1 =35c v 2 = 5 B/c, T 2 = 24 c T = 35 c (0с,90) Все каналы пусты, нет новых кадров для передачи. Общее время передачи – T = 35 c.

Продвижение модельного времени (один канал) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 41 Каждый кадр описывается парой: (t, s), где t – модельное время отправки, а s – размер. Пусть необходимо передать кадры: 100 Б, 50 Б, 90 Б, 30 Б, 200 Б (0c,50B) 10 B/c 0 c T1T1 100 Б50 Б90 Б (0c,100B)... I. 10 c T (0c,50B) v = 10 B/c 10 c T1T1 (0c,100B) II. 0 c T 100 Б T 1 = s/v + max(T 1,t) T 1 = 100/10 + max(0,0) = 10c T = max(T 1, T)

Продвижение модельного времени (один канал) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 42 (10c,90B) 10 B/c 10 c T1T1 90 Б90 Б30 Б200 Б (0c,50B) III. 15 c T v = 10 B/c 15 c T1T1 IV. 10 c T 100 Б T 1 = s/v + max(T 1,t) T 1 = 50/10 + max(10,0) = 15c T = max(T 1, T) (10c,90B) (0c,50B) 50 Б50 Б Каждый кадр описывается парой: (t, s), где t – модельное время отправки, а s – размер. Пусть необходимо передать кадры: 100 Б, 50 Б, 90 Б, 30 Б, 200 Б

Продвижение модельного времени (один канал) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 43 (15c,30B) 10 B/c 15 c T1T1 30 Б200 Б (10c,90B) V. 24 c T v = 10 B/c 24 c T1T1 VI. 15 c T 100 Б T 1 = s/v + max(T 1,t) T 1 = 90/10 + max(15,10) = 24c T = max(T 1, T) (15c,30B) (10c,90B) 50 Б50 Б Каждый кадр описывается парой: (t, s), где t – модельное время отправки, а s – размер. Пусть необходимо передать кадры: 100 Б, 50 Б, 90 Б, 30 Б, 200 Б 90 Б90 Б

Продвижение модельного времени (один канал) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 44 (24c,200B) 10 B/c 24 c T1T1 200 Б (15c,30B) VII. 27 c T v = 10 B/c 27 c T1T1 IV. 24 c T 100 Б T 1 = s/v + max(T 1,t) T 1 = 30/10 + max(24,15) = 27c T = max(T 1, T) (24c,200B) (15c,30B) 50 Б50 Б Каждый кадр описывается парой: (t, s), где t – модельное время отправки, а s – размер. Пусть необходимо передать кадры: 100 Б, 50 Б, 90 Б, 30 Б, 200 Б 90 Б90 Б30 Б30 Б

Продвижение модельного времени (один канал) © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 45 (24c,200B) 10 B/c 24 c T1T1 200 Б (15c,30B) VII. 27 c T v = 10 B/c 27 c T1T1 IV. 24 c T 100 Б T 1 = s/v + max(T 1,t) T 1 = 30/10 + max(24,15) = 27c T = max(T 1, T) (24c,200B) (15c,30B) 50 Б50 Б Каждый кадр описывается парой: (t, s), где t – модельное время отправки, а s – размер. Пусть необходимо передать кадры: 100 Б, 50 Б, 90 Б, 30 Б, 200 Б 90 Б90 Б30 Б30 Б

Литература 46 © Кафедра вычислительных систем ФГОБУ ВПО «СибГУТИ» 1.Вирт Н. Алгоритмы и структуры данных. Новая версия для Оберона / Пер. с англ. Ткачев Ф.В. – М.: ДМК Пресс, 2012 г. – 272 с. 2.Linux Ethernet Bonding Driver HOWTO. – URL: Поляков, А.Ю. Адаптивный подход к распределению информационных блоков по каналам передачи данных / А.Ю. Поляков // М.: Электросвязь., – 6. – C. 32 – Таненбаум Э. Компьютерные сети (Computer Networks) : Пер. с англ. – СПб:Питер, – 992 с. (Серия: Классика Computer Science).