Алгоритми маршрутизацii в мережах
Курсова робота
1. Вступ
В наш час комптАЩютернi мережi перебувають в станi розвитку й набувають широкого розповсюдження. Лише комптАЩютерна мережа Internet в даний час розрахована на 4.294.967.296 комптАЩютерiв, якi матимуть IP адреси. До цього числа слiд додати чиленнi локальнi та корпоративнi мережi. Всi цi комптАЩютери були зтАЩiднанi з метою обмiну iнформацiiю i власники комптАЩютерiв жадають швидкоi передачi великоi кiлькостi iнформацii на значнi вiдстанi.
Вимоги користувачiв мережi задовольняються покращенням якiстi каналiв передачi даних на замiну телефонним дротам прийшлi оптично-волоконнi лiнii, канали передачi даних за допомогою супутникового звтАЩязку тощо. Але значну роль при такiй кiлькостi зтАЩiднаних в мережу комптАЩютерiв вiдiграi якiсть протоколiв, за допомогою яких здiйснюiться передача даних мiж серверами, протоколiв маршрутизацii, алгоритмiв на яких вони побудованi.
Враховуючи, що 4-байтну адресацiю в мережi Internet буде замiнено 8-байтною, тобто максимальна кiлькiсть комптАЩютерiв пiдтАЩiднаних до мережi зросте у 4.294.967.296 разiв, слiд зазначити, що найбiльшу роль вiдiграватиме покращення саме механiзму маршрутизацii пакетiв даних мiж серверами мережi Internet.
Маршрутизацiя тАУ це задача знаходження шляху мiж комптАЩютером, що вiдсилаi данi та комптАЩютером-одержувачем, але в звтАЩязанiй моделi IP ця задача в основному зводиться до пошуку шляхiв до шлюзiв мiж мережами. Поки пакети даних знаходяться на окремiй мережi або пiдмережi проблеми маршрутизацii вирiшуються за технологiiю, специфiчною для iнтерфейсу цiii мережi. IP маршрутизацiя починаiться, коли потрiбно передати данi мiж рiзними мережами з рiзними iнтерфейсами. Якщо мережi отримувача та вiдправника безпосередньо звтАЩязанi, то данi мають пройти через шлюз, що зтАЩiднуi мережi. Якщо цi мережi не звтАЩязанi шлюзом, данi мають пройти через мережi, що знаходяться мiж вiдправником i одержувачем та шлюзами що iх зтАЩiднують.Як тiльки данi доходять до шлюзу на мережi отримувача, технологiя маршрутизацii цiii мережi спрямовуi данi до отримувача.
Для знаходження маршруту до комптАЩютера-отримувача система зберiгаi таблицi маршрутизацii, якi використовуються протоколами мережного рiвня для вибору потрiбного мережного iнтерфейсу. Маршрутизацiйна iнформацiя зберiгаiться у виглядi двох таблиць: перша тАУ для маршрутiв до хостiв, друга тАУ для маршрутiв до мереж. Такий пiдхiд дозволяi використовувати унiверсальнi механiзми визначення маршрутiв як для мереж iз розподiленим середовищем передачi даних , так i для мереж типу point-to-point. Визначаючи маршрут, модуль мережного протоколу (IP) спочатку переглядаi таблицi для хостiв, а потiм для мереж. Якщо пошук не даi результату, то використовуiться маршрут по замовчуванню.
Визначення маршруту може базуватися на рiзноманiтних показниках або комбiнацiях показникiв. Програмнi реалiзацii алгоритмiв маршрутизацii вираховують вартiсть маршруту для визначення оптимальних маршрутiв до пункту призначення.
В таблицi 1 наведено приклад таблицi типу пункт призначення/наступний обтАЩiкт для пересилання пакетiв.
| Мережа призначення | Наступний обтАЩiкт |
| 57 | вершина С |
| 24 | вершина В |
| 26 | вершина В |
| 18 | вершина А |
| 20 | вершина С |
| 34 | вершина А |
| 28 | вершина А |
Таблиця 1 : маршрутизацiйна таблиця типу пункт призначення/наступний обтАЩiкт для пересилання пакетiв
РЖснуi багато пiдходiв до задач пошуку оптимальних шляхiв в мережi, що реалiзованi в протоколах, за якими вiдбуваiться маршрутизацiя, таких як 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.
Найрозповсюдженiшими в Internet i реалiзацii алгоритмiв вектору вiдстанi та вiдкриття найкоротшого шляху.
Алгоритми вiдкриття найкоротшого маршруту, також вiдомi як алгоритми стану канала направляють потоки маршрутизацiйноi iнформации до всiх вузлiв об'iднаноi мережi. Але кожний маршрутизатор вiдсилаi лише ту частину маршрутизацiйноi таблицi, котра описуi стан його власних каналiв. Алгоритми вектору вiдстанi (також вiдомi, як алгоритми Белмана-Форда) вимагають вiд кожногo маршрутизатора вiдсилки всiii або частини своii маршрутизацiйноi таблицi, але лише своiм сусiдам. Алгоритми вiдкриття найкоротшого маршруту фактично направляють невеликi корекцii по всiх напрямках, в той час як алгоритми вектору вiдстанi вiдсилають бiльш великi корекцii лише до сусiднiх маршрутизаторiв.
Вiдрiзняючись бiльш швидкою сходимiстю, алгоритми вiдкриття найкоротшого маршруту трохи менше схильнi до утворення петель маршрутизацii, нiж алгоритми вектору вiдстанi. З iншого боку, алгоритми вiдкриття найкоротшого маршруту характеризуються бiльш складними розрахунками в порiвняннi з алгоритмами вектору вiдстанi, потребуючи бiльшоi процесорноi потужностi та памтАЩятi, нiж алгоритми вектору вiдстанi. В звтАЩязку з цим, реалiзацiя та пiдтримка алгоритмiв вiдкриття найкоротшого маршруту може бути бiльш дорогою. Не дивлячись на iхнi вiдмiнностi, обидва типи алгоритмiв добре функцiонують за самих рiзноманiтних умов.
В додатку наведено текст демону Routed, який реалiзований у маршрутизацiйному протоколi RIP на основi алгоритму вектору вiдстанi.
2. Маршрутизацiйнi рiшення
2.1.RIP : Алгоритми вектору вiдстанi
Алгоритми вектору вiдстанi основанi на обмiнi малоi кiлькостi iнформацii. Кожний обтАЩiкт (шлюз або хост), що приймаi участь в маршрутизацii, маi тримати iнформацiю про всi комптАЩютери системi. Кожний запис в таблицi маршрутизацii включаi наступний шлюз, на який данi, напрямленi до обтАЩiкту, мають бути вiдправленi. До того ж вiн маi мiстити значення, що характеризуi загальну вiдстань до обтАЩiкту. Вiдстань - це узагальнена характеристика, що може вiдображати швидкiсть передачi даних, грошову вартiсть передачi тощо. Алгоритми вектору вiстанi дiстали свою назву вiд того, що вони можуть обчислити оптимальний маршрут коли змiнюiться лише список вiдстаней. Крiм того, маi мiсце обмiн маршрутизацiйною iнформацiiю мiж безпосередньо звтАЩязаними обтАЩiктами, тобто елементами спiльноi мережi. Записи в таблицi маршрутизацii мають мiстити таку iнформацiю про комптАЩютер-отримувач:
адреса : в IP реалiзацii це маi бути IP адреса хоста або мережi;
шлюз : перший шлюз на цьому маршрутi;
iнтерфейс : iнтерфейс, що маi бути використований, щоб досягти першого шлюза;
цiна : число, що визначаi вiдстань до комптАЩютера-отримувача;
таймер : промiжок часу з того моменту коли iнформацiя була востаннi оновлена.
На додаток можуть бути доданi рiзнi флаги та iнша iнформацiя. Таблиця починаiться з опису обтАЩiктiв, що прямо пiдтАЩiднанi до системи. Вона оновлюiться на основi iнформацii, що приходить вiд сусiднiх шлюзiв. Найважливiша iнформацiя, якою обмiнюються хости та шлюзи мiститься в звiтах оновлення. Кожний обтАЩiкт, що бере участь в маршрутизацii посилаi звiти оновлення, що описують таблицi маршрутизацii в тому станi, в якому вони знаходяться на даний момент. Можливо визначити оптимальний маршрут користуючись лише iнформацiiю отриманою вiд сусiднiх обтАЩiктiв.
Алгоритми вектору вiдстанi базуються на таблицi даючи найкращий маршрут з мiркувань цiни (будь-якоi характериски,яку можна представити у виглядi суми ребер графу) . Формально, якщо вершини i та j сусiднi, тодi цiна d(i,j) рiвна цiнi ребра мiж i та j. В нормальному випадку всi обтАЩiкти на данiй мережi однаковi, d(i,j) однакове для всiх обтАЩiктiв даноi мережi i визначаi цiну використовування цiii мережi. Щоб дiстати цiну всього маршруту, потрiбно додати цiни всiх ребер, що складають цей маршрут. Для зручностi припустимо, що цiна тАУ додатнi цiле. Нехай D(i,j) визначаi цiну кращого маршруту з вершини i до вершини j. Вона маi бути визначена для кожного ребра. d(i,j) визначатиме цiни окремих крокiв. Формально, нехай d(i,j) визначаi цiну маршруту, йдучи прямо з вершини i до вершини j. Це значення дорiвнюi нескiнченностi, якщо i та j не сусiднi вершини. (Слiд зауважити, що d(i,i) - нескiнченнiсть. Це так, якщо не брати до уваги, що вершина може мати пряме зтАЩiднання до самоi себе). Оскiльки цiни адитивнi, то можна показати отримання кращого маршруту так :
D(i,i) = 0, для всiх i
D(i,j) = min [d(i,k) + D(k,j)], iнакше k
i найкращий маршрут той, що починаiться з вершини i до тих вершин k, для яких d(i,k) + D(k,j) мiнiмальне.
Ми можеме обмежити друге рiвняння для тих k, що i сусiдами i. Для iнших d(i,k) нескiнченнiсть, тому вони не можуть дати мiнiмального значення.На основi цього можливо обчислити вiдстань. ОбтАЩiкт i примушуi його сусiдiв k прислати цiну шляху до обтАЩiкту призначення j. Коли i отримуi цiну d(k,j) вiд всiх k, вiн додаi d(k,j) до цiни шляху D(i,k). Потiм i порiвнюi значення вiд всiх сусiдiв i вибираi найменше.
Реальнi реалiзацii алгоритму запамтАЩятовують найкращу цiну й iдентифiкацiю сусiда, що ii надiслав. РЖнформацiя замiщаiться, коли надсилаiться менша цiна. Це дозволяi обраховувати мiнiмум, не зберiгаючи iнформацiю вiд всiх сусiдiв. Але в випадку, коли iнформацiя надходить вiд обтАЩiкта, що був записаний в таблицi як найкращий, iнформацiя оновлюiться в будь-якому випадку. Механiзм визначення найкращого маршруту передбачаi крах обтАЩiкту на дiлянцi цього маршруту. В звтАЩязку з цим встановлено, що обтАЩiкти мають вiдсилати оновлену iнформацiiю кожнi 30 секунд. Якщо обтАЩiкт, що даi кращу цiну, не вiдповiдаi протягом 180 секунд (враховуiться можливiсть втрати пакету), цiна шляху встановлюiться в дуже велике значення.
2.2. OSPF, DualIS-IS: Алгоритм вiдкриття найкоротшого шляху
2.2.1. Огляд алгоритму.
Алгоритм вiдкриття найкоротшого шляху використовуiться як в IP, так i в OSI середовищi. Вiн маi складнiсть О(N2).
Основний алгоритм, що будуi PATHS з нуля, починаi додавання систем з найвигiднiшими маршрутами з оглядом на PATHS (не може iснувати коротшого маршруту до SELF ). Потiм визначаiться TENT використовуючи локальнi таблицi з вiдомостями про сусiднi вершини.
Система не може бути розмiщеною в PATHS до тих пiр, поки не доведено, що не iснуi маршруту, коротшого за даний. Коли система N розмiщуiться в PATHS, перевiряiться цiна маршруту до кожноi вершини M сусiдньоi до N через саму вершину N. Цей маршрут визначаiться як сума цiни маршруту до N та цiни дiлянки NM. Якщо розмiщений в TENT та нове значення буде бiльшим, маршрут iгноруiться.Якщо розмiщений в TENT та нове значення буде меншим, старий запис замiщуiться новим. Якщо розмiщений в TENT та нове значення таке ж саме як те, що вже i в TENT то набiр {Adj(M)} встановлюiться як поiднання старого запису (того, що мiститься в TENT) та нового - {Adj(N)}. Якщо M не знаходиться в TENT, то даний маршрут додаiться в TENT.
Потiм алгоритм знаходить триплети in TENT з мiнiмальним x.
2.2.2. Реалiзацiя алгоритму вiдкриття найкоротшого шляху в DUALIS-IS середовищi
Крок 0: Встановимо TENT та PATHS як пустi. Встановимо tentlength в 0.
(tentlength тАУ це довжина шляху дослiджуваних елементiв TENT.)
1) Додамо до PATHS, де SELF тАУ початкова система, W тАУспецiальна величина, що визначаi трафiк до SELF що пройдений, включаючи внутрiшнiй процес.
2) Тепер загрузимо TENT локальними даними шляхiв (Кожен запис в TENT маi бути визначений як маршрутизатор або кiнцева система OSI, щоб дозволити правильну перевiрку в Кроцi 2).
Для всiх сумiжних вершин Adj(N) на всiх можливих каналах:
d(N) = цiна маршруту, що проходить через (N)
Adj(N) = кiлькiсть вершин сусiднiх N.
3) Якщо триплет в TENT, то
Якщо x = d(N), то {Adj(M)} := {Adj(M)} U {Adj(N)}.
4) Якщо N тАУ маршрутизатор або кiнцева система OSI, i бiльше не iснуi сумiжних вершин {Adj(M)} то видалимо надлишкову вершину.
5) Якщо x < d(N), нiчого.
6) Якщо x > d(N), видалити з TENT i додати триплет .
7) Якщо не в TENT, то додати в TENT.
8) Тепер додаються системи, для яких локальний маршрутизатор не маi сумiжних вершин, але вони згаданi в сусiднiх псевдовершинах LSP. Сумiжнiсть для таких систем визначаiться маршрутизатором.
9) Для всiх широковiщательних каналiв в активному станi, знайти псевдовершину LSP для цього каналу. Якщо така iснуi, для всiх сусiдiв N, про якi згадуваiться на цiй вершинi i не визначенi в TENT, додати запис:
to TENT, where:
d(N) = цiна промiжку .
Adj(N) = кiлькiсть вершин, що стоять на шляху до заданого маршрутизатора.
10) Перейти в Крок 2.
Крок 1: Визначити нульовий PDU в LSP ситеми, щойно доданоi в PATHS
1)dist(P,N) = d(P) + metric.k(P,N) для кожного сусiда N (як для кiнцевоi системи, так i для маршрутизатора) системи P.
2) Якщо dist(P,N) >максимальноi цiни промiжку, нiчого.
3) Якщо i в PATHS, нiчого.
d(N) повинне бути меншим нiж dist(P,N), або N не повинне бути в PATHS. За бажанням можна зробити додаткову перевiрку чи i d(N) меншим за dist(P,N).
4) Якщо триплет в TENT, тодi:
a) Якщо x = dist(P,N) тодi {Adj(N)}:= {Adj(N)} U {Adj(P)}.
b) Якщо N тАУ маршрутизатор або кiнцева система OSI, i бiльше не iснуi сумiжних вершин {Adj(M)}, то видалимо надлишкову вершину.
c) Якщо x < dist(P,N), нiчого.
d) Якщо x > dist(P,N), видалити з TENT, та додати
5) Якщо не в TENT, додати в TENT.
Крок 2: Якщо TENT пустий, зупинитися. РЖнакше:
1) Знайти елемент
, з мiнiмальним x таким чином:
a)Якщо елемент <*,tentlength,*> залишився в TENT в списку для tentlength, вибрати цей елемент. Якщо в списку iснуi бiльше одного елементу, вибрати один з цих елементiв для системи, що i псевдовершиною, вибрати ту, що не i псевдовершиною. Якщо бiльше нема елементiв в списку для tentlength, збiльшити tentlength i повторити Крок 2.
b)Видалити
з TENT.
c) Додати
в PATHS.
d) Якщо система тiльки що додана в PATHS тАУ кiнцева система, то перейти в Крок 2. РЖнакше : перейти в Крок 1.
Позначення:
PATHS тАУ представляi ациклiчний граф найкоротших шляхiв вiд системи S. Вiн представляiться як набiр триплетiв , де N iдентифiкатор системи. d(N) загальна вiдстань вiд N до S).
{Adj(N)} тАУнабiр працюючих сусiдiв S, що iх можна використати N. Якщо система i в PATHS, шляхи, що вiдповiдають цьому мiсцю i найкоротшими.
TENT тАУ список триплетiв у виглядi , де N, d(N) та {Adj(N)} вiдповiдають визначеним в PATHS.
TENT може бути iнтуiтивно представлений як мiсце системи в PATHS. РЖншими словами, триплет в TENT говорить, що, якщо N i в PATHS, d(N) вiдповiдаi x, але N не може бути розмiщене в PATHS поки не доведено, що не iснуi шляхiв, коротших за x .
Так само в TENT значить, що якщо N i в PATHS, тодi d(N) буде дорiвнювати x для маршрутiв, що проходять через сумiжну вершину A або через сумiжну вершину B.
Запропоновано в реальнiй реалiзацii таблицi TENT проводити сортування за характеристикою d(N).
3. Висновки
Маршрутизацiйнi алгоритми реалiзованi на рiзних типах мереж вiд локальних до глобальних. Широко розповсюдженим i демон Routed з дистриутиву унiверситету Калiфорнii в Берклi вiн реалiзований в протоколi RIP. Також велике значення мають реалiзацii алгоритму вiдкриття найкоротшого маршруту для подвiйного середовища OSI та TCP/IP в планi знаходження маршрутiв мiж iнтер-автономними системами та маршрутизаторами TCP/IP архитектури.
Глоссарiй
OSI тАУ мережна модель, запропонована органiзацiiю по стандартизацii ISO
IS тАУ Interautonomous system тАУ iнтеравтономна система, система, що приймаi участь в маршрутизацii в моделi OSI
ES - End System-кiнцева система, система, що не приймаi участi в маршрутизацii в моделi OSI
Router тАУ маршрутизатор, обтАЩiкт маршрутизацii
Gateway тАУ шлюз, система, що маi декiлька мережних iнтерфейсiв
RIP (Routing Information Protocol) тАУ маршрутизацiйний iнформацiйний протокол
OSPF (Open Shortest Path First) тАУ Маршрутизацiйний протокол вiдкриття найкоротшого шляху
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,
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 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 <= 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("%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) < 0)
LOGERR("sysctl(IPCTL_FORWARDING)");
if (!ipforwarding) {
if (supplier)
msglog("-s incompatible with ipforwarding=0");
if (default_gateway) {
msglog("-g incompatible with ipforwarding=0");
default_gateway = 0;
}
supplier = 0;
supplier_set = 1;
}
if (default_gateway) {
if (supplier_set && !supplier) {
msglog("-g and -q incompatible");
} else {
supplier = 1;
supplier_set = 1;
}
}
signal(SIGALRM, sigalrm);
if (!background)
signal(SIGHUP, sigterm); /* SIGHUP fatal during debugging */
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 on tracing 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 get synchronized
* 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 the interface
* 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 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 <= 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 aging and broadcast
* timers to minimize awakenings
*/
age(0);
rip_bcast(0);
/* It is desirable to send routing updates
* regularly. So schedule the next update
* 30 seconds after the previous one was
* secheduled, instead of 30 seconds after
* the previous update was finished.
* Even if we just started after discovering
* a 2nd interface or were otherwise delayed,
* pick a 30-second aniversary 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 full update,
* 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 file descriptor */
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_sock setsockopt(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_MEMBERSHIP RIP)");
}
}
/* Prepare socket used for RIP.
*/
void
rip_on(struct interface *ifp)
{
/* If the main RIP socket is already alive, only start receiving
* 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 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 < 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 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) < 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 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 < ms1->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);
}
Для подготовки данной работы были использованы материалы с сайта http://" onclick="return false">
Вместе с этим смотрят:
9 сочинений для 9 класса /english/
A Farewell to Arms
A history of the english language
About England
Accommodation in St.Petersburg