.

Алгоритми маршрутизації в мережах.(курсова)

Язык: украинский
Формат: реферат
Тип документа: Word Doc
3 5198
Скачать документ

Курсова робота на тему

“Алгоритми маршрутизації в мережах”

Зміст

1. Вступ ____________________________________________ст 2

2. Маршрутизаційні рішення __________________________ст 5

2.1. RIP : Алгоритм вектору відстані _______________ст 5

2.2. Dual IS-IS : Алгоритм відкриття найкоротшого

шляху _______________________________________ст 8

2.2.1. Огляд алгоритму __________________________ст 8

2.2.2. Реалізація алгоритму відкриття найкоротшого шляху в DUAL
IS-IS середовищі___________________________ст 9

Висновки_______________________________________ст 13

Глоссарій_______________________________________ст 13

5. Список літератури________________________________ст 14

6. Додаток_________________________________________ст 15

1. Вступ

В наш час комп’ютерні мережі перебувають в стані розвитку й набувають
широкого розповсюдження. Лише комп’ютерна мережа Internet в даний час
розрахована на 4.294.967.296 комп’ютерів, які матимуть IP адреси. До
цього числа слід додати чиленні локальні та корпоративні мережі. Всі ці
комп’ютери були з’єднані з метою обміну інформацією і власники
комп’ютерів жадають швидкої передачі великої кількості інформації на
значні відстані.

Вимоги користувачів мережі задовольняються покращенням якісті каналів
передачі даних на заміну телефонним дротам прийшлі оптично-волоконні
лінії, канали передачі даних за допомогою супутникового зв’язку тощо.
Але значну роль при такій кількості з’єднаних в мережу комп’ютерів
відіграє якість протоколів, за допомогою яких здійснюється передача
даних

між серверами, протоколів маршрутизації, алгоритмів на яких вони
побудовані.

Враховуючи, що 4-байтну адресацію в мережі Internet буде
замінено 8-байтною, тобто максимальна кількість комп’ютерів під’єднаних
до мережі зросте у 4.294.967.296 разів, слід зазначити, що найбільшу
роль відіграватиме покращення саме механізму маршрутизації пакетів даних
між серверами мережі Internet.

Маршрутизація – це задача знаходження шляху між комп’ютером, що
відсилає дані та комп’ютером-одержувачем, але в зв’язаній моделі IP ця
задача в основному зводиться до пошуку шляхів до шлюзів між мережами.
Поки пакети даних знаходяться на окремій мережі або підмережі проблеми
маршрутизації вирішуються за технологією, специфічною для інтерфейсу
цієї мережі. IP маршрутизація починається, коли потрібно передати дані
між різними мережами з різними інтерфейсами. Якщо мережі отримувача та
відправника безпосередньо зв’язані, то дані мають пройти через шлюз, що
з’єднує мережі. Якщо ці мережі не зв’язані шлюзом, дані мають пройти
через мережі, що знаходяться між відправником і одержувачем та шлюзами
що їх з’єднують.Як тільки дані доходять до шлюзу на мережі отримувача,
технологія маршрутизації цієї мережі спрямовує дані до отримувача.

Для знаходження маршруту до комп’ютера-отримувача система зберігає
таблиці маршрутизації, які використовуються протоколами мережного рівня
для вибору потрібного мережного інтерфейсу. Маршрутизаційна інформація
зберігається у вигляді двох таблиць: перша – для маршрутів до хостів,
друга – для маршрутів до мереж. Такий підхід дозволяє використовувати
універсальні механізми визначення маршрутів як для мереж із розподіленим
середовищем передачі даних , так і для мереж типу point-to-point.
Визначаючи маршрут, модуль мережного протоколу (IP) спочатку переглядає
таблиці для хостів, а потім для мереж. Якщо пошук не дає результату, то
використовується маршрут по замовчуванню.

Визначення маршруту може базуватися на різноманітних показниках або
комбінаціях показників. Програмні реалізації алгоритмів маршрутизації
вираховують вартість маршруту для визначення оптимальних маршрутів до

пункту призначення.

В таблиці 1 наведено приклад таблиці типу пункт призначення/наступний
об’єкт для пересилання пакетів.

Мережа призначення Наступний об’єкт

57 вершина С

24 вершина В

26 вершина В

18 вершина А

20 вершина С

34 вершина А

28 вершина А

Таблиця 1 : маршрутизаційна таблиця типу пункт призначення/наступний
об’єкт для пересилання пакетів

Існує багато підходів до задач пошуку оптимальних шляхів в мережі, що
реалізовані в протоколах, за якими відбувається маршрутизація, таких як
Interior Gateway Protocols: OSPF (Open Shortest Path First), Dual IS-IS
(Intermediate System to Intermediate System), RIP (Routing Information
Protocol), GGP (Gateway to Gateway Protocol); Exterior Gateway
Protocols: BGP (Border Gateway Protocol), EGP (Exterior Gateway
Protocol), Inter-AS Routing without Exterior Gateway; Static Routing.

Найрозповсюдженішими в Internet є реалізації алгоритмів вектору
відстані та відкриття найкоротшого шляху.

Алгоритми відкриття найкоротшого маршруту, також відомі як алгоритми
стану канала направляють потоки маршрутизаційної інформации до всіх
вузлів об’єднаної мережі. Але кожний маршрутизатор відсилає лише ту

частину маршрутизаційної таблиці, котра описує стан його власних
каналів. Алгоритми вектору відстані (також відомі, як алгоритми
Белмана-Форда) вимагають від кожногo маршрутизатора відсилки всієї або
частини своєї

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

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

В додатку наведено текст демону Routed, який реалізований у
маршрутизаційному протоколі RIP на основі алгоритму вектору відстані.

2. Маршрутизаційні рішення

2.1. RIP : Алгоритми вектору відстані

Алгоритми вектору відстані основані на обміні малої кількості
інформації. Кожний об’єкт (шлюз або хост), що приймає участь в
маршрутизації, має тримати інформацію про всі комп’ютери системі.
Кожний запис в таблиці маршрутизації включає наступний шлюз, на який
дані, напрямлені до об’єкту, мають бути відправлені. До того ж він має
містити значення, що характеризує загальну відстань до об’єкту. Відстань
– це узагальнена характеристика, що може відображати швидкість передачі
даних, грошову вартість передачі тощо. Алгоритми вектору вістані дістали
свою назву від того, що вони можуть обчислити оптимальний маршрут коли
змінюється лише список відстаней. Крім того, має місце обмін
маршрутизаційною інформацією між безпосередньо зв’язаними об’єктами,
тобто елементами спільної мережі. Записи в таблиці маршрутизації мають
містити таку інформацію про комп’ютер-отримувач:

адреса : в IP реалізації це має бути IP адреса хоста або мережі;

шлюз : перший шлюз на цьому маршруті;

інтерфейс : інтерфейс, що має бути використований, щоб досягти першого
шлюза;

ціна : число, що визначає відстань до комп’ютера-отримувача;

таймер : проміжок часу з того моменту коли інформація була востаннє
оновлена.

На додаток можуть бути додані різні флаги та інша інформація. Таблиця
починається з опису об’єктів, що прямо під’єднані до системи. Вона
оновлюється на основі інформації, що приходить від сусідніх шлюзів.
Найважливіша інформація, якою обмінюються хости та шлюзи міститься в
звітах оновлення. Кожний об’єкт, що бере участь в маршрутизації посилає
звіти оновлення, що описують таблиці маршрутизації в тому стані, в якому
вони знаходяться на даний момент. Можливо визначити оптимальний маршрут
користуючись лише інформацією отриманою від сусідніх об’єктів.

Алгоритми вектору відстані базуються на таблиці даючи найкращий маршрут
з міркувань ціни (будь-якої характериски,яку можна представити у вигляді
суми ребер графу) . Формально, якщо вершини i та j сусідні, тоді ціна
d(i,j) рівна ціні ребра між i та j. В нормальному випадку всі об’єкти
на даній мережі однакові, d(i,j) однакове для всіх об’єктів даноі мережі
і визначає ціну використовування цієї мережі. Щоб дістати ціну всього
маршруту, потрібно додати ціни всіх ребер, що складають цей маршрут. Для
зручності припустимо, що ціна – додатнє ціле. Нехай D(i,j) визначає ціну
кращого маршруту з вершини i до вершини j. Вона має бути визначена для
кожного ребра. d(i,j) визначатиме ціни окремих кроків. Формально,
нехай d(i,j) визначає ціну маршруту, йдучи прямо з вершини i до вершини
j. Це значення дорівнює нескінченності, якщо i та j не сусідні вершини.
(Слід зауважити, що d(i,i) – нескінченність. Це так, якщо не брати до
уваги, що вершина може мати пряме з’єднання до самої себе). Оскільки
ціни адитивні, то можна показати отримання кращого маршруту так :

D(i,i) = 0, для всіх
i

D(i,j) = min [d(i,k) + D(k,j)], інакше k

і найкращий маршрут той, що починається з вершини i до тих вершин k,
для яких d(i,k) + D(k,j) мінімальне.

Ми можеме обмежити друге рівняння для тих k, що є сусідами i. Для
інших d(i,k) нескінченність, тому вони не можуть дати мінімального
значення.На основі цього можливо обчислити відстань. Об’єкт i примушує
його сусідів k прислати ціну шляху до об’єкту призначення j. Коли i
отримує ціну d(k,j) від всіх k, він додає d(k,j) до ціни шляху D(i,k).
Потім і порівнює значення від всіх сусідів і вибирає найменше.

Реальні реалізації алгоритму запам’ятовують найкращу ціну й
ідентифікацію сусіда, що її надіслав. Інформація заміщається, коли
надсилається менша ціна. Це дозволяє обраховувати мінімум, не зберігаючи
інформацію від всіх сусідів. Але в випадку, коли інформація надходить
від об’єкта, що був записаний в таблиці як найкращий, інформація
оновлюється в будь-якому випадку. Механізм визначення найкращого
маршруту передбачає крах об’єкту на ділянці цього маршруту. В зв’язку з
цим встановлено, що об’єкти мають відсилати оновлену інформаціію кожні
30 секунд. Якщо об’єкт, що дає кращу ціну, не відповідає протягом 180
секунд (враховується можливість втрати пакету), ціна шляху
встановлюється в дуже велике значення.

2.2. OSPF, Dual IS-IS: Алгоритм відкриття найкоротшого шляху

2.2.1. Огляд алгоритму.

Алгоритм відкриття найкоротшого шляху використовується як в IP, так і в
OSI середовищі. Він має складність О(N2).

Основний алгоритм, що будує PATHS з нуля, починає додавання систем з
найвигіднішими маршрутами з оглядом на PATHS (не може існувати коротшого
маршруту до SELF ). Потім визначається TENT використовуючи локальні
таблиці з відомостями про сусідні вершини.

Система не може бути розміщеною в PATHS до тих пір, поки не доведено,
що не існує маршруту, коротшого за даний. Коли система N розміщується в
PATHS, перевіряється ціна маршруту до кожної вершини M сусідньої до N
через саму вершину N. Цей маршрут визначається як сума ціни маршруту до
N та ціни ділянки NM. Якщо розміщений в TENT та нове значення
буде більшим, маршрут ігнорується.Якщо розміщений в TENT та нове
значення буде меншим, старий запис заміщується новим. Якщо
розміщений в TENT та нове значення таке ж саме як те, що вже є в TENT то
набір {Adj(M)} встановлюється як поєднання старого запису (того, що
міститься в TENT) та нового – {Adj(N)}. Якщо M не знаходиться в TENT,
то даний маршрут додається в TENT.

Потім алгоритм знаходить триплети in TENT з мінімальним
x.

2.2.2. Реалізація алгоритму відкриття найкоротшого шляху в DUAL IS-IS
середовищі

Крок 0: Встановимо TENT та PATHS як пусті. Встановимо tentlength в 0.

(tentlength – це довжина шляху досліджуваних елементів TENT.)

1) Додамо до PATHS, де SELF – початкова система, W
–спеціальна величина, що визначає трафік до SELF що пройдений,
включаючи внутрішній процес.

2) Тепер загрузимо TENT локальними даними шляхів (Кожен запис в TENT
має бути визначений як маршрутизатор або кінцева система OSI, щоб
дозволити правильну перевірку в Кроці 2).

Для всіх суміжних вершин Adj(N) на всіх можливих каналах:

d(N) = ціна маршруту, що проходить через (N)

Adj(N) = кількість вершин сусідніх N.

3) Якщо триплет в TENT, то

Якщо x = d(N), то {Adj(M)} := {Adj(M)} U {Adj(N)}.

4) Якщо N – маршрутизатор або кінцева система OSI, і більше не існує
суміжних вершин {Adj(M)} то видалимо надлишкову вершину.

5) Якщо x d(N), видалити з TENT і додати триплет
.

7) Якщо не в TENT, то додати в TENT.

8) Тепер додаються системи, для яких локальний маршрутизатор не має
суміжних вершин, але вони згадані в сусідніх псевдовершинах LSP.
Суміжність для таких систем визначається маршрутизатором.

9) Для всіх широковєщательних каналів в активному стані, знайти
псевдовершину LSP для цього каналу. Якщо така існує, для всіх сусідів N,
про які згадувається на цій вершині і не визначені в TENT, додати
запис:

to TENT, where:

d(N) = ціна проміжку .

Adj(N) = кількість вершин, що стоять на шляху до заданого
маршрутизатора.

10) Перейти в Крок 2.

Крок 1: Визначити нульовий PDU в LSP ситеми, щойно доданої в PATHS

1)dist(P,N) = d(P) + metric.k(P,N) для кожного сусіда N (як для кінцевої
системи, так і для маршрутизатора) системи P.

2) Якщо dist(P,N) >максимальної ціни проміжку, нічого.

3) Якщо є в PATHS, нічого.

d(N) повинне бути меншим ніж dist(P,N), або N не повинне бути в PATHS.
За бажанням можна зробити додаткову перевірку чи є d(N) меншим за
dist(P,N).

4) Якщо триплет в TENT, тоді:

a) Якщо x = dist(P,N) тоді {Adj(N)}:= {Adj(N)} U {Adj(P)}.

b) Якщо N – маршрутизатор або кінцева система OSI, і більше не існує
суміжних вершин {Adj(M)}, то видалимо надлишкову вершину.

c) Якщо x dist(P,N), видалити з TENT, та додати

5) Якщо не в TENT, додати в TENT.

Крок 2: Якщо TENT пустий, зупинитися. Інакше:

1) Знайти елемент

, з мінімальним x таким чином:

a)Якщо елемент залишився в TENT в списку для
tentlength, вибрати цей елемент. Якщо в списку існує більше одного
елементу, вибрати один з цих елементів для системи, що є псевдовершиною,
вибрати ту, що не є псевдовершиною. Якщо більше нема елементів в списку
для tentlength, збільшити tentlength і повторити Крок 2.

b)Видалити

з TENT.

c) Додати

в PATHS.

d) Якщо система тільки що додана в PATHS – кінцева система, то перейти в
Крок 2. Інакше : перейти в Крок 1.

Позначення:

PATHS – представляє ациклічний граф найкоротших шляхів від системи S.
Він представляється як набір триплетів , де N
ідентифікатор системи. d(N) загальна відстань від N до S).

{Adj(N)} –набір працюючих сусідів S, що їх можна використати N. Якщо
система є в PATHS, шляхи, що відповідають цьому місцю є найкоротшими.

TENT – список триплетів у вигляді , де N, d(N) та
{Adj(N)} відповідають визначеним в PATHS.

TENT може бути інтуітивно представлений як місце системи в PATHS. Іншими
словами, триплет в TENT говорить, що, якщо N є в PATHS, d(N)
відповідає x, але N не може бути розміщене в PATHS поки не доведено, що
не існує шляхів, коротших за x .

Так само в TENT значить, що якщо N є в PATHS, тоді d(N)
буде дорівнювати x для маршрутів, що проходять через суміжну вершину A
або через суміжну вершину B.

Запропоновано в реальній реалізації таблиці TENT проводити сортування
за характеристикою d(N).

3. Висновки

Маршрутизаційні алгоритми реалізовані на різних типах мереж від
локальних до глобальних. Широко розповсюдженим є демон Routed з
дистриутиву університету Каліфорнії в Берклі він реалізований в
протоколі RIP. Також велике значення мають реалізації алгоритму
відкриття найкоротшого маршруту для подвійного середовища OSI та TCP/IP
в плані знаходження маршрутів між інтер-автономними системами та
маршрутизаторами TCP/IP архитектури.

Глоссарій

OSI – мережна модель, запропонована організацією по стандартизації ISO

IS – Interautonomous system – інтеравтономна система, система, що
приймає участь в маршрутизації в моделі OSI

ES – End System-кінцева система, система, що не приймає участі в
маршрутизації в моделі OSI

Router – маршрутизатор, об’єкт маршрутизації

Gateway – шлюз, система, що має декілька мережних інтерфейсів

RIP (Routing Information Protocol) – маршрутизаційний інформаційний
протокол

OSPF (Open Shortest Path First) – Маршрутизаційний протокол відкриття
найкоротшого шляху

Література :

C.L. Hedrick. Routing Information Protocol. RFC 1058 Jun-01-1988.

D. Waitzman, C.Partridge, S.E. Deering. Distance Vector Multicast
Routing Protocol. RFC 1075 Nov-01-1988.

R.W. Callon. Use of OSI IS-IS for routing in TCP/IP and dual
environments.

RFC 1195 Dec-01-1990.

P. Almquist, F. Kastenholz. Towards Requirements for IP Routers. RFC
1716 November 1994.

J. Moy. , OSPF Version 2. RFC 2178 July 1997.

A. Ballardie. Core Based Trees (CBT) Multicast Routing Architecture. RFC
2201September 1997.

Bellman, R. E., “Dynamic Programming”, Princeton University Press,
Princeton, N.J., 1957.

Bertsekas, D. P., and Gallaher, R. G., “Data Networks”,Prentice-Hall,
Englewood Cliffs, N.J., 1987.

Braden, R., and Postel, J., “Requirements for Internet Gateways”,
USC/Information Sciences Institute, RFC-1009, June 1987.

Boggs, D. R., Shoch, J. F., Taft, E. A., and Metcalfe, R. M.,”Pup: An
Internetwork Architecture”, IEEE Transactions on Communications, April
1980.

Clark, D. D., “Fault Isolation and Recovery,” MIT-LCS, RFC-816, July
1982.

Xerox Corp., “Internet Transport Protocols”, Xerox System Integration
Standard XSIS 028112, December 1981.

Ford, L.R. Jr., and Fulkerson, D.R.,”Flows in Networks”, Princeton
University Press, Princeton, N.J., 1962.

“Intermediate System to Intermediate System Intra-Domain Routeing
Exchange Protocol for use in Conjunction with the Protocol for
Providing the Connectionless-mode Network Service (ISO 8473)”, ISO DP
10589, February 1990.

“Protocol for Providing the Connectionless-Mode Network Service”,
ISO 8473, March 1987.

”End System to Intermediate System Routeing Exchange Protocol for Use in
Conjunction with the Protocol for Providing the Connectionless-Mode
Network Service (ISO 8473)”, ISO 9542, March 1988.

Braden,R., and Postel,J., “Requirements for Internet Gateways”, RFC
1009, June 1987.

Moy,J., “The OSPF Specification”, RFC 1131, October 1989.

Postel,J., “Internetwork Protocol”, RFC 791, September 1981.

Postel,J., “Internet Control Message Protocol”, RFC 792, September
1981.

20. GOSIP Advanced Requirements Group, “Government Open Systems

Interconnection Profile (GOSIP) Version 2.0 [Final Text]”,
Federal Information Processing Standard, U.S. Department of
Commerce, National Institute of Standards and Technology, Gaithersburg,
MD, October 1990.

21. “Standard for Local Area Networks and Metropolitan Area Networks:
Overview and Architecture of Network Standards”,IEEE Standard
802.1a-1990.

Додаток

#include “defs.h”

#include “pathnames.h”

#ifdef sgi

#include “math.h”

#endif

#include

#include

#include

pid_t mypid;

naddr myaddr; /* system address */

char myname[MAXHOSTNAMELEN+1];

int supplier; /* supply or broadcast updates */

int supplier_set;

int ipforwarding = 1; /* kernel forwarding on */

int default_gateway; /* 1=advertise default */

int background = 1;

int ridhosts; /* 1=reduce host routes */

int mhome; /* 1=want multi-homed host route */

int advertise_mhome; /* 1=must continue adverising it */

int auth_ok = 1; /* 1=ignore auth if we do not care */

struct timeval epoch; /* when started */

struct timeval clk, prev_clk;

struct timeval now; /* current idea of time */

time_t now_stale;

time_t now_expire;

time_t now_garbage;

struct timeval next_bcast; /* next general broadcast */

struct timeval no_flash = {EPOCH+SUPPLY_INTERVAL}; /* inhibit flash
update */

fd_set fdbits;

int sock_max;

int rip_sock = -1; /* RIP socket */

struct interface *rip_sock_mcast; /* current multicast interface */

int rt_sock; /* routing socket */

int rt_sock_seqno;

static int get_rip_sock(naddr, int);

static void timevalsub(struct timeval *, struct timeval *, struct
timeval *);

int

main(int argc,

$

0

¦

®

°

?

?

ntI

?

U

i

$

zaeZ

I

I

?

O

O

O

Oe

O

U

Ue

i

&

O‚”??????? ?c?¤?¦?????¬?®?°?????¶?????1/4?3/4?A?A?U?ooooeeeeeeeeeeeeeeee
eeeeTH

B*

oeoeeeeeeeeeoeTHTHTHTHTHIIIAeII

&

&

F

$

&

F

&

F

[])

{

int n, mib[4], off;

size_t len;

char *p, *q;

struct timeval wtime, t2;

time_t dt;

fd_set ibits;

naddr p_net, p_mask;

struct interface *ifp;

struct parm parm;

char *tracename = 0;

/* Some shells are badly broken and send SIGHUP to backgrounded

* processes.

*/

signal(SIGHUP, SIG_IGN);

openlog(“routed”, LOG_PID | LOG_ODELAY, LOG_DAEMON);

ftrace = stdout;

gettimeofday(&clk, 0);

prev_clk = clk;

epoch = clk;

epoch.tv_sec -= EPOCH;

now.tv_sec = EPOCH;

now_stale = EPOCH – STALE_TIME;

now_expire = EPOCH – EXPIRE_TIME;

now_garbage = EPOCH – GARBAGE_TIME;

wtime.tv_sec = 0;

(void)gethostname(myname, sizeof(myname)-1);

(void)gethost(myname, &myaddr);

while ((n = getopt(argc, argv, “sqdghmAtT:F:P:”)) != -1) {

switch (n) {

case ‘s’:

supplier = 1;

supplier_set = 1;

break;

case ‘q’:

supplier = 0;

supplier_set = 1;

break;

case ‘d’:

background = 0;

break;

case ‘g’:

bzero(&parm, sizeof(parm));

parm.parm_d_metric = 1;

p = check_parms(&parm);

if (p != 0)

msglog(“bad -g: %s”, p);

else

default_gateway = 1;

break;

case ‘h’: /* suppress extra host routes */

ridhosts = 1;

break;

case ‘m’: /* advertise host route */

mhome = 1; /* on multi-homed hosts */

break;

case ‘A’:

/* Ignore authentication if we do not care.

* Crazy as it is, that is what RFC 1723 requires.

*/

auth_ok = 0;

break;

case ‘t’:

new_tracelevel++;

break;

case ‘T’:

tracename = optarg;

break;

case ‘F’: /* minimal routes for SLIP */

n = FAKE_METRIC;

p = strchr(optarg,’,’);

if (p && *p != ‘\0’) {

n = (int)strtoul(p+1, &q, 0);

if (*q == ‘\0’

&& n = 1)

*p = ‘\0’;

}

if (!getnet(optarg, &p_net, &p_mask)) {

msglog(“bad network; \”-F %s\””,

optarg);

break;

}

bzero(&parm, sizeof(parm));

parm.parm_net = p_net;

parm.parm_mask = p_mask;

parm.parm_d_metric = n;

p = check_parms(&parm);

if (p != 0)

msglog(“bad -F: %s”, p);

break;

case ‘P’:

/* handle arbirary, (usually) per-interface

* parameters.

*/

p = parse_parms(optarg, 0);

if (p != 0) {

if (strcasecmp(p,optarg))

msglog(“%s in \”%s\””, p, optarg);

else

msglog(“bad \”-P %s\””, optarg);

}

break;

default:

goto usage;

}

}

argc -= optind;

argv += optind;

if (tracename == 0 && argc >= 1) {

tracename = *argv++;

argc–;

}

if (tracename != 0 && tracename[0] == ‘\0’)

goto usage;

if (argc != 0) {

usage:

logbad(0, “usage: routed [-sqdghmAt] [-T tracefile]”

” [-F net[/mask[,metric]]] [-P parms]”);

}

if (geteuid() != 0)

logbad(0, “requires UID 0”);

mib[0] = CTL_NET;

mib[1] = PF_INET;

mib[2] = IPPROTO_IP;

mib[3] = IPCTL_FORWARDING;

len = sizeof(ipforwarding);

if (sysctl(mib, 4, &ipforwarding, &len, 0, 0) _daemonize(background ? 0 : (_DF_NOCHDIR|_DF_NOFORK),

new_tracelevel == 0 ? -1 : STDOUT_FILENO,

new_tracelevel == 0 ? -1 : STDERR_FILENO,

-1))

BADERR(0, “_daemonize()”);

#else

if (background && daemon(0, new_tracelevel) wtime.tv_sec + 5) {

/* Deal with time changes before other housekeeping to

* keep everything straight.

*/

dt = t2.tv_sec;

if (dt > 0)

dt -= wtime.tv_sec;

trace_act(“time changed by %d sec”, dt);

epoch.tv_sec += dt;

}

timevalsub(&now, &clk, &epoch);

now_stale = now.tv_sec – STALE_TIME;

now_expire = now.tv_sec – EXPIRE_TIME;

now_garbage = now.tv_sec – GARBAGE_TIME;

/* deal with signals that should affect tracing */

set_tracelevel();

if (stopint != 0) {

rip_bcast(0);

rdisc_adv();

trace_off(“exiting with signal %d\n”, stopint);

exit(stopint | 128);

}

/* look for new or dead interfaces */

timevalsub(&wtime, &ifinit_timer, &now);

if (wtime.tv_sec ))

rip_bcast(1);

timevalsub(&t2, &no_flash, &now);

if (timercmp(&t2, &wtime, )) {

rdisc_age(0);

continue;

}

timevalsub(&t2, &rdisc_timer, &now);

if (timercmp(&t2, &wtime, = 0 && FD_ISSET(rdisc_sock, &ibits)) {

read_d();

n–;

}

if (rip_sock >= 0 && FD_ISSET(rip_sock, &ibits)) {

read_rip(rip_sock, 0);

n–;

}

for (ifp = ifnet; n > 0 && 0 != ifp; ifp = ifp->int_next) {

if (ifp->int_rip_sock >= 0

&& FD_ISSET(ifp->int_rip_sock, &ibits)) {

read_rip(ifp->int_rip_sock, ifp);

n–;

}

}

}

}

/* ARGSUSED */

void

sigalrm(int s)

{

/* Historically, SIGALRM would cause the daemon to check for

* new and broken interfaces.

*/

ifinit_timer.tv_sec = now.tv_sec;

trace_act(“SIGALRM”);

}

/* watch for fatal signals */

void

sigterm(int sig)

{

stopint = sig;

(void)signal(sig, SIG_DFL); /* catch it only once */

}

void

fix_select(void)

{

struct interface *ifp;

FD_ZERO(&fdbits);

sock_max = 0;

FD_SET(rt_sock, &fdbits);

if (sock_max = 0) {

FD_SET(rip_sock, &fdbits);

if (sock_max int_next) {

if (ifp->int_rip_sock >= 0) {

FD_SET(ifp->int_rip_sock, &fdbits);

if (sock_max int_rip_sock)

sock_max = ifp->int_rip_sock+1;

}

}

if (rdisc_sock >= 0) {

FD_SET(rdisc_sock, &fdbits);

if (sock_max = MIN_SOCKBUF) {

if (setsockopt(sock, SOL_SOCKET, SO_RCVBUF,

&rbuf, sizeof(rbuf)) = 0 && !mhome) {

trace_act(“turn off RIP”);

(void)close(rip_sock);

rip_sock = -1;

/* get non-broadcast sockets to listen to queries.

*/

for (ifp = ifnet; ifp != 0; ifp = ifp->int_next) {

if (ifp->int_state & IS_REMOTE)

continue;

if (ifp->int_rip_sock int_if_flags & IFF_POINTOPOINT)

? ifp->int_dstaddr

: ifp->int_addr);

ifp->int_rip_sock = get_rip_sock(addr, 0);

}

}

fix_select();

age(0);

}

}

/* turn on RIP multicast input via an interface

*/

static void

rip_mcast_on(struct interface *ifp)

{

struct ip_mreq m;

if (!IS_RIP_IN_OFF(ifp->int_state)

&& (ifp->int_if_flags & IFF_MULTICAST)

#ifdef MCAST_PPP_BUG

&& !(ifp->int_if_flags & IFF_POINTOPOINT)

#endif

&& !(ifp->int_state & IS_ALIAS)) {

m.imr_multiaddr.s_addr = htonl(INADDR_RIP_GROUP);

m.imr_interface.s_addr = ((ifp->int_if_flags & IFF_POINTOPOINT)

? ifp->int_dstaddr

: ifp->int_addr);

if (setsockopt(rip_sock,IPPROTO_IP, IP_ADD_MEMBERSHIP,

&m, sizeof(m)) = 0) {

if (ifp != 0)

rip_mcast_on(ifp);

return;

}

/* If the main RIP socket is off and it makes sense to turn it on,

* then turn it on for all of the interfaces.

*/

if (rip_interfaces > 0 && !rdisc_ok) {

trace_act(“turn on RIP”);

/* Close all of the query sockets so that we can open

* the main socket. SO_REUSEPORT is not a solution,

* since that would let two daemons bind to the broadcast

* socket.

*/

for (ifp = ifnet; ifp != 0; ifp = ifp->int_next) {

if (ifp->int_rip_sock >= 0) {

(void)close(ifp->int_rip_sock);

ifp->int_rip_sock = -1;

}

}

rip_sock = get_rip_sock(INADDR_ANY, 1);

rip_sock_mcast = 0;

/* Do not advertise anything until we have heard something

*/

if (next_bcast.tv_sec int_next) {

ifp->int_query_time = NEVER;

rip_mcast_on(ifp);

}

ifinit_timer.tv_sec = now.tv_sec;

} else if (ifp != 0

&& !(ifp->int_state & IS_REMOTE)

&& ifp->int_rip_sock int_rip_sock = get_rip_sock(ifp->int_addr, 0);

}

fix_select();

}

/* die if malloc(3) fails

*/

void *

rtmalloc(size_t size,

char *msg)

{

void *p = malloc(size);

if (p == 0)

logbad(1,”malloc() failed in %s”, msg);

return p;

}

/* get a random instant in an interval

*/

void

intvl_random(struct timeval *tp, /* put value here */

u_long lo, /* value is after this second */

u_long hi) /* and before this */

{

tp->tv_sec = (time_t)(hi == lo

? lo

: (lo + random() % ((hi – lo))));

tp->tv_usec = random() % 1000000;

}

void

timevaladd(struct timeval *t1,

struct timeval *t2)

{

t1->tv_sec += t2->tv_sec;

if ((t1->tv_usec += t2->tv_usec) > 1000000) {

t1->tv_sec++;

t1->tv_usec -= 1000000;

}

}

/* t1 = t2 – t3

*/

static void

timevalsub(struct timeval *t1,

struct timeval *t2,

struct timeval *t3)

{

t1->tv_sec = t2->tv_sec – t3->tv_sec;

if ((t1->tv_usec = t2->tv_usec – t3->tv_usec) tv_sec–;

t1->tv_usec += 1000000;

}

}

/* put a message into the system log

*/

void

msglog(char *p, …)

{

va_list args;

trace_flush();

va_start(args, p);

vsyslog(LOG_ERR, p, args);

if (ftrace != 0) {

if (ftrace == stdout)

(void)fputs(“routed: “, ftrace);

(void)vfprintf(ftrace, p, args);

(void)fputc(‘\n’, ftrace);

}

}

/* Put a message about a bad system into the system log if

* we have not complained about it recently.

*

* It is desirable to complain about all bad systems, but not too often.

* In the worst case, it is not practical to keep track of all bad
systems.

* For example, there can be many systems with the wrong password.

*/

void

msglim(struct msg_limit *lim, naddr addr, char *p, …)

{

va_list args;

int i;

struct msg_sub *ms1, *ms;

char *p1;

va_start(args, p);

/* look for the oldest slot in the table

* or the slot for the bad router.

*/

ms = ms1 = lim->subs;

for (i = MSG_SUBJECT_N; ; i–, ms1++) {

if (i == 0) {

/* Reuse a slot at most once every 10 minutes.

*/

if (lim->reuse > now.tv_sec) {

ms = 0;

} else {

ms = ms1;

lim->reuse = now.tv_sec + 10*60;

}

break;

}

if (ms->addr == addr) {

/* Repeat a complaint about a given system at

* most once an hour.

*/

if (ms->until > now.tv_sec)

ms = 0;

break;

}

if (ms->until until)

ms = ms1;

}

if (ms != 0) {

ms->addr = addr;

ms->until = now.tv_sec + 60*60; /* 60 minutes */

trace_flush();

for (p1 = p; *p1 == ‘ ‘; p1++)

continue;

vsyslog(LOG_ERR, p1, args);

}

/* always display the message if tracing */

if (ftrace != 0) {

(void)vfprintf(ftrace, p, args);

(void)fputc(‘\n’, ftrace);

}

}

void

logbad(int dump, char *p, …)

{

va_list args;

trace_flush();

va_start(args, p);

vsyslog(LOG_ERR, p, args);

(void)fputs(“routed: “, stderr);

(void)vfprintf(stderr, p, args);

(void)fputs(“; giving up\n”,stderr);

(void)fflush(stderr);

if (dump)

abort();

exit(1);

}

PAGE 23

Нашли опечатку? Выделите и нажмите CTRL+Enter

Похожие документы
Обсуждение

Ответить

Курсовые, Дипломы, Рефераты на заказ в кратчайшие сроки
Заказать реферат!
UkrReferat.com. Всі права захищені. 2000-2020