Реферат: Алгоритми маршрутизації в мережах
Курсова робота
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 GatewayProtocols: OSPF (Open Shortest Path First), Dual IS-IS (Intermediate System toIntermediate System), RIP (Routing Information Protocol), GGP (Gateway toGateway 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, DualIS-IS: Алгоритм відкриття найкоротшого шляху
2.2.1. Огляд алгоритму.
Алгоритм відкриття найкоротшого шляху використовується як в IP, так і в OSI середовищі. Він має складність О(N2).
Основний алгоритм, що будує PATHS з нуля, починає додавання системз найвигіднішими маршрутами з оглядом на PATHS (не може існувати коротшогомаршруту до SELF ). Потім визначається TENT використовуючи локальні таблиці звідомостями про сусідні вершини.
Система не може бути розміщеною в PATHS до тих пір, поки недоведено, що не існує маршруту, коротшого за даний. Коли система N розміщуєтьсяв PATHS, перевіряється ціна маршруту до кожної вершини M сусідньої до N черезсаму вершину N. Цей маршрут визначається як сума ціни маршруту до N та ціниділянки NM. Якщо <M,*,*> розміщений в TENT та нове значення буде більшим,маршрут ігнорується.Якщо <M,*,*> розміщений в TENT та нове значення будеменшим, старий запис заміщується новим. Якщо <M,*,*> розміщений в TENT танове значення таке ж саме як те, що вже є в TENT то набір {Adj(M)}встановлюється як поєднання старого запису (того, що міститься в TENT) танового — {Adj(N)}. Якщо M не знаходиться в TENT, то даний маршрут додається вTENT.
Потім алгоритм знаходить триплети <N,x,{Adj(N)}> in TENT змінімальним x.
2.2.2. Реалізація алгоритмувідкриття найкоротшого шляху в DUALIS-ISсередовищі
Крок 0: Встановимо TENT та PATHS як пусті. Встановимо tentlength в0.
(tentlength – це довжина шляху досліджуваних елементів TENT.)
1) Додамо <SELF,0,W> до PATHS, де SELF – початкова система, W –спеціальна величина, що визначаєтрафік до SELF що пройдений, включаючи внутрішній процес.
2) Тепер загрузимо TENT локальними даними шляхів (Кожен запис вTENT має бути визначений як маршрутизатор або кінцева система OSI, щоб дозволити правильну перевірку в Кроці 2).
Для всіх суміжних вершин Adj(N) на всіх можливих каналах:
d(N) = ціна маршруту, що проходить через (N)
Adj(N) = кількість вершин сусідніх N.
3) Якщо триплет <N,x,{Adj(M)}> в TENT, то
Якщо x = d(N), то {Adj(M)} := {Adj(M)} U {Adj(N)}.
4) Якщо N – маршрутизатор або кінцева система OSI, і більше не існує суміжних вершин{Adj(M)} то видалимо надлишкову вершину.
5) Якщо x < d(N), нічого.
6) Якщо x > d(N), видалити <N,x,{Adj(M)}> з TENT і додатитриплет <N,d(N),{Adj(N)}>.
7) Якщо <N,x,{Adj(M)}> не в TENT, то додати<N,d(N),{Adj(N)}> в TENT.
8) Тепер додаються системи, для яких локальний маршрутизатор немає суміжних вершин, але вони згадані в сусідніх псевдовершинах LSP. Суміжність для таких систем визначаєтьсямаршрутизатором.
9) Для всіх широковєщательних каналів в активному стані, знайтипсевдовершину LSP для цього каналу. Якщо така існує, для всіх сусідів N, проякі згадувається на цій вершині і не визначені в TENT, додати запис:
<N,d(N),{Adj(N)}> 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) Якщо <N,d(N),{Adj(N)}> є в PATHS, нічого.
d(N) повинне бути меншим ніж dist(P,N), або N не повинне бути в PATHS. За бажанням можназробити додаткову перевірку чи є d(N)меншим за dist(P,N).
4) Якщо триплет <N,x,{Adj(N)}> в TENT, тоді:
a) Якщо x = dist(P,N) тоді {Adj(N)}:= {Adj(N)} U {Adj(P)}.
b) Якщо N – маршрутизатор або кінцева система OSI, і більше неіснує суміжних вершин {Adj(M)}, то видалимо надлишкову вершину.
c) Якщо x < dist(P,N), нічого.
d) Якщо x > dist(P,N), видалити <N,x,{Adj(N)}> з TENT, тадодати <N,dist(P,N),{Adj(P)}>
5) Якщо <N,x,{Adj(N)}> не в TENT, додати<N,dist(P,N),{Adj(P)}> в TENT.
Крок 2: Якщо TENT пустий, зупинитися. Інакше:
1) Знайти елемент <P,x,{Adj(P)}>, з мінімальним x такимчином:
a)Якщо елемент <*,tentlength,*> залишився в TENT в спискудля tentlength, вибрати цей елемент. Якщо в списку існує більше одногоелементу, вибрати один з цих елементів для системи, що є псевдовершиною,вибрати ту, що не є псевдовершиною. Якщо більше нема елементів в списку дляtentlength, збільшити tentlength і повторити Крок 2.
b)Видалити <P,tentlength,{Adj(P)}> з TENT.
c) Додати <P,d(P),{Adj(P)}> в PATHS.
d) Якщосистема тільки що додана в PATHS – кінцева система, то перейти в Крок 2. Інакше: перейти в Крок 1.
Позначення:
PATHS – представляє ациклічний граф найкоротших шляхів від системиS. Він представляється як набір триплетів <N,d(N),{Adj(N)}>, де Nідентифікатор системи. d(N) загальна відстань від N до S).
{Adj(N)} –набір працюючих сусідів S, що їх можна використати N.Якщо система є в PATHS, шляхи, що відповідають цьому місцю є найкоротшими.
TENT – список триплетів у вигляді <N,d(N),{Adj(N)}>, де N,d(N) та {Adj(N)} відповідають визначеним в PATHS.
TENT може бути інтуітивно представлений як місце системи в PATHS.Іншими словами, триплет <N,x,{A}> в TENT говорить, що, якщо N є в PATHS,d(N) відповідає x, але N не може бути розміщене в PATHS поки не доведено, що неіснує шляхів, коротших за x .
Так само <N,x,{A,B}> в 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 MulticastRouting Protocol. RFC 1075 Nov-01-1988.
R.W. Callon. Use of OSI IS-IS for routing in TCP/IP and dualenvironments.
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 RoutingArchitecture. RFC 2201September 1997.
Bellman, R. E., «Dynamic Programming», PrincetonUniversity Press, Princeton, N.J., 1957.
Bertsekas, D. P., and Gallaher, R. G., «DataNetworks»,Prentice-Hall, Englewood Cliffs, N.J., 1987.
Braden, R., and Postel, J., «Requirements for InternetGateways», 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 onCommunications, April 1980.
Clark, D. D., «Fault Isolation and Recovery,» MIT-LCS,RFC-816, July 1982.
Xerox Corp., «Internet Transport Protocols», XeroxSystem 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-DomainRouteing Exchange Protocol for use in Conjunction with the Protocol forProviding the Connectionless-mode Network Service (ISO 8473)», ISO DP10589, February 1990.
«Protocol for Providing the Connectionless-Mode NetworkService», ISO 8473, March 1987.
”End System to Intermediate System Routeing Exchange Protocol forUse in Conjunction with the Protocol for Providing the Connectionless-ModeNetwork 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, October1989.
Postel,J., «Internetwork Protocol», RFC 791, September1981.
Postel,J., «Internet Control Message Protocol», RFC 792,September 1981.
20. GOSIP Advanced Requirements Group, «Government OpenSystems
Interconnection Profile (GOSIP) Version 2.0 [Final Text]»,Federal Information Processing Standard, U.S. Department of Commerce, NationalInstitute of Standards and Technology, Gaithersburg, MD, October 1990.
21. «Standard for Local Area Networks and Metropolitan AreaNetworks: Overview and Architecture of Network Standards»,IEEE Standard802.1a-1990.
Додаток
#include «defs.h»
#include «pathnames.h»
#ifdef sgi
#include «math.h»
#endif
#include <signal.h>
#include <fcntl.h>
#include <sys/file.h>
pid_t mypid;
naddr myaddr; /*system address */
char myname[MAXHOSTNAMELEN+1];
int supplier; /* supplyor broadcast updates */
int supplier_set;
int ipforwarding = 1; /* kernelforwarding on */
int default_gateway; /* 1=advertisedefault */
int background = 1;
int ridhosts; /*1=reduce host routes */
int mhome; /*1=want multi-homed host route */
int advertise_mhome; /* 1=must continueadverising it */
int auth_ok = 1; /* 1=ignoreauth if we do not care */
struct timeval epoch; /* when started*/
struct timeval clk, prev_clk;
struct timeval now; /* current ideaof time */
time_t now_stale;
time_t now_expire;
time_t now_garbage;
struct timeval next_bcast; /* next generalbroadcast */
struct timeval no_flash = {EPOCH+SUPPLY_INTERVAL}; /* inhibitflash update */
fd_set fdbits;
int sock_max;
int rip_sock = -1; /* RIP socket*/
struct interface *rip_sock_mcast; /* current multicastinterface */
int rt_sock; /* routingsocket */
int rt_sock_seqno;
static int get_rip_sock(naddr, int);
static void timevalsub(struct timeval *, struct timeval *, structtimeval *);
int
main(int argc,
char *argv[])
{
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 extrahost routes */
ridhosts = 1;
break;
case 'm': /* advertise hostroute */
mhome = 1; /* on multi-homed hosts*/
break;
case 'A':
/* Ignore authentication if we do notcare.
* Crazy as it is, that is what RFC1723 requires.
*/
auth_ok = 0;
break;
case 't':
new_tracelevel++;
break;
case 'T':
tracename = optarg;
break;
case 'F': /* minimal routesfor SLIP */
n = FAKE_METRIC;
p = strchr(optarg,',');
if (p && *p != '\0') {
n = (int)strtoul(p+1,&q, 0);
if (*q == '\0'
&& n <=HOPCNT_INFINITY-1
&& 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("%sin \"%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] [-Ttracefile]»
" [-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) < 0)
LOGERR(«sysctl(IPCTL_FORWARDING)»);
if (!ipforwarding) {
if (supplier)
msglog("-s incompatible withipforwarding=0");
if (default_gateway) {
msglog("-g incompatible withipforwarding=0");
default_gateway = 0;
}
supplier = 0;
supplier_set = 1;
}
if (default_gateway) {
if (supplier_set && !supplier) {
msglog("-g and -qincompatible");
} else {
supplier = 1;
supplier_set = 1;
}
}
signal(SIGALRM, sigalrm);
if (!background)
signal(SIGHUP, sigterm); /* SIGHUP fatal duringdebugging */
signal(SIGTERM, sigterm);
signal(SIGINT, sigterm);
signal(SIGUSR1, sigtrace_on);
signal(SIGUSR2, sigtrace_off);
/* get into the background */
#ifdef sgi
if (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) < 0)
BADERR(0,«daemon()»);
#endif
mypid = getpid();
srandom((int)(clk.tv_sec ^ clk.tv_usec ^ mypid));
/* prepare socket connected to the kernel.
*/
rt_sock = socket(AF_ROUTE, SOCK_RAW, 0);
if (rt_sock < 0)
BADERR(1,«rt_sock = socket()»);
if (fcntl(rt_sock, F_SETFL, O_NONBLOCK) == -1)
logbad(1, «fcntl(rt_sock) O_NONBLOCK:%s», strerror(errno));
off = 0;
if (setsockopt(rt_sock, SOL_SOCKET,SO_USELOOPBACK,
&off,sizeof(off)) < 0)
LOGERR(«setsockopt(SO_USELOOPBACK,0)»);
fix_select();
if (background && new_tracelevel == 0)
ftrace = 0;
if (tracename != 0) {
strncpy(inittracename, tracename, sizeof(inittracename)-1);
set_tracefile(inittracename, "%s\n", -1);
} else {
tracelevel_msg("%s\n", -1); /* turn ontracing to stdio */
}
bufinit();
/* initialize radix tree */
rtinit();
/* Pick a random part of the second for our output to minimize
* collisions.
*
* Start broadcasting after hearing from other routers, and
* at a random time so a bunch of systems do not getsynchronized
* after a power failure.
*/
intvl_random(&next_bcast, EPOCH+MIN_WAITTIME,EPOCH+SUPPLY_INTERVAL);
age_timer.tv_usec = next_bcast.tv_usec;
age_timer.tv_sec = EPOCH+MIN_WAITTIME;
rdisc_timer = next_bcast;
ifinit_timer.tv_usec = next_bcast.tv_usec;
/* Collect an initial view of the world by checking theinterface
* configuration and the kludge file.
*/
gwkludge();
ifinit();
flush_kern();
/* Ask for routes */
rip_query();
rdisc_sol();
/* Loop forever, listening and broadcasting.
*/
for (;;) {
prev_clk = clk;
gettimeofday(&clk, 0);
timevalsub(&t2, &clk, &prev_clk);
if (t2.tv_sec < 0
|| t2.tv_sec > wtime.tv_sec + 5) {
/* Deal with time changes before otherhousekeeping to
* keep everything straight.
*/
dt = t2.tv_sec;
if (dt > 0)
dt -= wtime.tv_sec;
trace_act(«time changed by %dsec», 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 <= 0) {
wtime.tv_sec = 0;
ifinit();
rip_query();
continue;
}
/* If it is time, then broadcast our routes.
*/
if (supplier || advertise_mhome) {
timevalsub(&t2, &next_bcast,&now);
if (t2.tv_sec <= 0) {
/* Synchronize the agingand broadcast
* timers to minimizeawakenings
*/
age(0);
rip_bcast(0);
/* It is desirable to sendrouting updates
* regularly. So schedulethe next update
* 30 seconds after theprevious one was
* secheduled, instead of30 seconds after
* the previous update wasfinished.
* Even if we just startedafter discovering
* a 2nd interface or wereotherwise delayed,
* pick a 30-secondaniversary of the
* original broadcast time.
*/
n = 1 +(0-t2.tv_sec)/SUPPLY_INTERVAL;
next_bcast.tv_sec +=n*SUPPLY_INTERVAL;
continue;
}
if (timercmp(&t2, &wtime,<))
wtime = t2;
}
/* If we need a flash update, either do it now or
* set the delay to end when it is time.
*
* If we are within MIN_WAITTIME seconds of a fullupdate,
* do not bother.
*/
if (need_flash
&& supplier
&& no_flash.tv_sec+MIN_WAITTIME <next_bcast.tv_sec) {
/* accurate to the millisecond */
if (!timercmp(&no_flash, &now,>))
rip_bcast(1);
timevalsub(&t2, &no_flash,&now);
if (timercmp(&t2, &wtime,<))
wtime = t2;
}
/* trigger the main aging timer.
*/
timevalsub(&t2, &age_timer, &now);
if (t2.tv_sec <= 0) {
age(0);
continue;
}
if (timercmp(&t2, &wtime, <))
wtime = t2;
/* update the kernel routing table
*/
timevalsub(&t2, &need_kern, &now);
if (t2.tv_sec <= 0) {
age(0);
continue;
}
if (timercmp(&t2, &wtime, <))
wtime = t2;
/* take care of router discovery,
* but do it to the millisecond
*/
if (!timercmp(&rdisc_timer, &now, >)) {
rdisc_age(0);
continue;
}
timevalsub(&t2, &rdisc_timer, &now);
if (timercmp(&t2, &wtime, <))
wtime = t2;
/* wait for input or a timer to expire.
*/
trace_flush();
ibits = fdbits;
n = select(sock_max, &ibits, 0, 0, &wtime);
if (n <= 0) {
if (n < 0 && errno != EINTR&& errno != EAGAIN)
BADERR(1,«select»);
continue;
}
if (FD_ISSET(rt_sock, &ibits)) {
read_rt();
n--;
}
if (rdisc_sock >= 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 <= rt_sock)
sock_max = rt_sock+1;
if (rip_sock >= 0) {
FD_SET(rip_sock, &fdbits);
if (sock_max <= rip_sock)
sock_max = rip_sock+1;
}
for (ifp = ifnet; 0 != ifp; ifp = ifp->int_next) {
if (ifp->int_rip_sock >= 0) {
FD_SET(ifp->int_rip_sock,&fdbits);
if (sock_max <=ifp->int_rip_sock)
sock_max =ifp->int_rip_sock+1;
}
}
if (rdisc_sock >= 0) {
FD_SET(rdisc_sock, &fdbits);
if (sock_max <= rdisc_sock)
sock_max = rdisc_sock+1;
}
}
void
fix_sock(int sock,
char *name)
{
int on;
#define MIN_SOCKBUF (4*1024)
static int rbuf;
if (fcntl(sock, F_SETFL, O_NONBLOCK) == -1)
logbad(1, «fcntl(%s) O_NONBLOCK: %s»,
name, strerror(errno));
on = 1;
if (setsockopt(sock, SOL_SOCKET,SO_BROADCAST,&on,sizeof(on)) < 0)
msglog(«setsockopt(%s,SO_BROADCAST): %s»,
name, strerror(errno));
#ifdef USE_PASSIFNAME
on = 1;
if (setsockopt(sock, SOL_SOCKET, SO_PASSIFNAME,&on,sizeof(on)) < 0)
msglog(«setsockopt(%s,SO_PASSIFNAME):%s»,
name, strerror(errno));
#endif
if (rbuf >= MIN_SOCKBUF) {
if (setsockopt(sock, SOL_SOCKET, SO_RCVBUF,
&rbuf, sizeof(rbuf)) < 0)
msglog(«setsockopt(%s,SO_RCVBUF=%d):%s»,
name, rbuf, strerror(errno));
} else {
for (rbuf = 60*1024;; rbuf -= 4096) {
if (setsockopt(sock, SOL_SOCKET,SO_RCVBUF,
&rbuf, sizeof(rbuf))== 0) {
trace_act(«RCVBUF=%d»,rbuf);
break;
}
if (rbuf < MIN_SOCKBUF) {
msglog(«setsockopt(%s,SO_RCVBUF= %d): %s»,
name, rbuf,strerror(errno));
break;
}
}
}
}
/* get a rip socket
*/
static int /* <0 or filedescriptor */
get_rip_sock(naddr addr,
int serious) /* 1=failure to bind is serious*/
{
struct sockaddr_in sin;
unsigned char ttl;
int s;
if ((s = socket(AF_INET, SOCK_DGRAM, 0)) < 0)
BADERR(1,«rip_sock = socket()»);
bzero(&sin,sizeof(sin));
#ifdef _HAVE_SIN_LEN
sin.sin_len = sizeof(sin);
#endif
sin.sin_family = AF_INET;
sin.sin_port = htons(RIP_PORT);
sin.sin_addr.s_addr = addr;
if (bind(s, (struct sockaddr *)&sin,sizeof(sin)) < 0) {
if (serious)
BADERR(errno != EADDRINUSE,«bind(rip_sock)»);
return -1;
}
fix_sock(s,«rip_sock»);
ttl = 1;
if (setsockopt(s, IPPROTO_IP, IP_MULTICAST_TTL,
&ttl, sizeof(ttl)) < 0)
DBGERR(1,«rip_socksetsockopt(IP_MULTICAST_TTL)»);
return s;
}
/* turn off main RIP socket */
void
rip_off(void)
{
struct interface *ifp;
register naddr addr;
if (rip_sock >= 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 < 0) {
addr =((ifp->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)
LOGERR(«setsockopt(IP_ADD_MEMBERSHIPRIP)»);
}
}
/* Prepare socket used for RIP.
*/
void
rip_on(struct interface *ifp)
{
/* If the main RIP socket is already alive, only startreceiving
* multicasts for this interface.
*/
if (rip_sock >= 0) {
if (ifp != 0)
rip_mcast_on(ifp);
return;
}
/* If the main RIP socket is off and it makes sense to turn iton,
* 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 canopen
* the main socket. SO_REUSEPORT is not a solution,
* since that would let two daemons bind to thebroadcast
* 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 heardsomething
*/
if (next_bcast.tv_sec < now.tv_sec+MIN_WAITTIME)
next_bcast.tv_sec =now.tv_sec+MIN_WAITTIME;
for (ifp = ifnet; ifp != 0; ifp = ifp->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 < 0) {
/* RIP is off, so ensure there are sockets on which
* to listen for queries.
*/
ifp->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 afterthis 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) < 0){
t1->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 toooften.
* In the worst case, it is not practical to keep track of all badsystems.
* 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 10minutes.
*/
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 givensystem at
* most once an hour.
*/
if (ms->until > now.tv_sec)
ms = 0;
break;
}
if (ms->until < ms1->until)
ms = ms1;
}
if (ms != 0) {
ms->addr = addr;
ms->until = now.tv_sec + 60*60; /* 60minutes */
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);
}
Список литературы
Для подготовки данной работы были использованы материалы с сайта www.referaty.com.ua/