Difference between revisions of "Маршрутизация"

From Ilianko
 
(23 intermediate revisions by the same user not shown)
Line 1: Line 1:
 +
===Какво е маршрутизация===
 
Маршрутизация или рутиране е процес на избиране на път в дадена мрежа, по който да се изпрати мрежовия трафик.   
 
Маршрутизация или рутиране е процес на избиране на път в дадена мрежа, по който да се изпрати мрежовия трафик.   
  
−
Рутиране има в различни мрежи - телефонни мрежи (), транспортни мрежи, компютърни мрежи.
+
Рутиране има в различни мрежи - телефонни мрежи (комутационни вериги), транспортни мрежи (логистика), компютърни мрежи (пакетна комутация).
  
−
В компютърните мрежи информацията се предава на пакети, затова рутирането се занимава с препращането на пакет от нод (routers, bridges, gateways, firewalls, or switches) към друг нод, за да бъде пренесен пакетът от началната точка до крайната цел.
+
В компютърните мрежи информацията се предава на пакети, затова рутирането се занимава с препращането на пакет от комуникационна точка към друга комуникационна точка (нод - възел, който в частност може да е router, bridge, gateway, firewall, switch или host). Целта е информационният пакет да бъде пренесен от началната точка до крайната точка.
  
−
In packet switching networks, routing directs packet forwarding, the transit of logically addressed packets from their source toward their ultimate destination through intermediate nodes, typically hardware devices called routers, bridges, gateways, firewalls, or switches. General-purpose computers can also forward packets and perform routing, though they are not specialized hardware and may suffer from limited performance. The routing process usually directs forwarding on the basis of routing tables which maintain a record of the routes to various network destinations. Thus, constructing routing tables, which are held in the router's memory, is very important for efficient routing. Most routing algorithms use only one network path at a time, but multipath routing techniques enable the use of multiple alternative paths.  
+
Всеки компютър с подходящ софтуер може да изпълнява роля на някои от тези устройства, но при големи натоварвания се препоръчва специализиран хардуер.
  
−
Routing, in a more narrow sense of the term, is often contrasted with bridging in its assumption that network addresses are structured and that similar addresses imply proximity within the network. Because structured addresses allow a single routing table entry to represent the route to a group of devices, structured addressing (routing, in the narrow sense) outperforms unstructured addressing (bridging) in large networks, and has become the dominant form of addressing on the Internet, though bridging is still widely used within localized environments.
+
Рутиращата машина препраща пакети според своята рутираща таблица, в която са описани пътищата до различни дестинации (мрежи). Оптималното конструиране на рутиращата таблица е много важно за ефективно рутиране. 
  
  
−
In packet switching networks, routing directs [[packet forwarding]], the transit of logically addressed packets from their source toward their ultimate destination through intermediate [[Node (networking)|nodes]], typically hardware devices called [[Router (computing)|routers]], [[Bridging (networking)|bridges]], [[gateway (telecommunications)|gateways]], [[Firewall (computing)|firewalls]], or [[network switch|switches]]. General-purpose [[computer]]s can also forward packets and perform routing, though they are not specialized hardware and may suffer from limited performance. The routing process usually directs forwarding on the basis of [[routing table]]s which maintain a record of the routes to various network destinations. Thus, constructing routing tables, which are held in the router's [[Computer storage|memory]], is very important for efficient routing. Most routing algorithms use only one network path at a time, but [[multipath routing]] techniques enable the use of multiple alternative paths.
 
  
−
Routing, in a more narrow sense of the term, is often contrasted with [[bridging (networking)|bridging]] in its assumption that [[network address]]es are structured and that similar addresses imply proximity within the network. Because structured addresses allow a single routing table entry to represent the route to a group of devices, structured addressing (routing, in the narrow sense) outperforms unstructured addressing (bridging) in large networks, and has become the dominant form of addressing on the Internet, though bridging is still widely used within localized environments.
+
== Трафик според дестинация ==
 +
*anycast - до всеки от група нодове
 +
*broadcast - до всички нодове
 +
*multicast - до група от нодове
 +
*unicast - до точно определен нод
 +
*geocast - до географска област
  
−
==Delivery semantics==
+
== Видове рутиране==
−
{{routing scheme}}
 
−
Routing schemes differ in their delivery semantics:
 
−
* [[unicast]] delivers a message to a single specific node
 
−
* [[Broadcasting (computing)|broadcast]] delivers a message to all nodes in the network
 
−
* [[multicast]] delivers a message to a group of nodes that have expressed interest in receiving the message
 
−
* [[anycast]] delivers a message to any one out of a group of nodes, typically the one nearest to the source
 
−
* [[geocast]] delivers a message to a geographic area
 
  
−
Unicast is the dominant form of message delivery on the Internet, and this article focuses on unicast routing algorithms.
+
===Статично рутиране ===
 +
На практика малки мрежи могат да използват ръчно конфигурирани рутиращи таблици, това се нарича '''[[static routing|статично рутиране]]''' (не адаптивно).  
  
−
==Topology distribution==
+
Приципно цялата мрежа може да бъде конфигурирана статично, но по този начин мрежата не е устойчива на повреда в даден нод. Ако има промяна и повреда в мрежата трафика няма да може да се пренасочи. Трябва да бъдат обновени съответните рутиращи таблици или да бъде отсранена повредата, за да може мрежата да функционира нормално.  
−
In a practice known as [[static routing]] (or non-adaptive routing), small networks may use manually configured routing tables. Larger networks have complex [[network topology|topologies]] that can change rapidly, making the manual construction of routing tables unfeasible. Nevertheless, most of the [[Public Switched Telephone Network|public switched telephone network]] (PSTN) uses pre-computed routing tables, with fallback routes if the most direct route becomes blocked (see [[routing in the PSTN]]). [[Adaptive routing]], or dynamic routing, attempts to solve this problem by constructing routing tables automatically, based on information carried by [[routing protocol]]s, and allowing the network to act nearly autonomously in avoiding network failures and blockages.
 
  
−
Examples of adaptive-routing algorithms are the Routing Information Protocol ([[Routing Information Protocol|RIP]]) and the Open-Shortest-Path-First protocol ([[OSPF]]). Adaptive routing dominates the Internet. However, the configuration of the routing protocols often requires a skilled touch; networking technology has not developed to the point of the complete automation of routing.{{Citation needed|date=October 2011}}
+
При някои обстоятелства статичното рутиране би могло да е от полза - stub networks, default routes
 +
 
 +
====Пример ====
 +
 
 +
To configure a static route to network 10.10.20.0/24, pointing to a next-hop router with the IP address of 192.168.100.1, type:
 +
 
 +
Cisco IOS
 +
ip route 10.10.20.0 255.255.255.0 192.168.100.1
 +
Linux
 +
route add -net 10.10.20.0 netmask 255.255.255.0 gw 192.168.1.100
 +
 
 +
The other option is to define a static route with reference to the outgoing interface which is connected to the next hop towards the destination network.
 +
 
 +
Cisco IOS
 +
ip route 10.10.20.0 255.255.255.0 FastEthernet 0/0
 +
Linux
 +
route add -net 10.10.20.0 netmask 255.255.255.0 dev eth0
 +
 
 +
===Динамично рутиране ===
 +
Големите мрежи имат сложна топология, която своевременно може многократно да се променя. Това прави ръчната конфигурация неприложима.  Динамичното (адаптивното) рутиране позволява автоматична настройка на рутиращата таблица. Последната се променя според информацията, която се обменя между нодовете посредством рутиращи протоколи и заложениете локални предпочетания за всеки нод.
 +
 
 +
Примери за такива протоколи са RIP - Routing Information Protocol и OSPF (Open-Shortest-Path-First protocol). Дънамичното рутиране пробладава в Интернет, но изисква съответните познания за правилното му конфигуриране.
 +
 
 +
Adaptive routing describes the capability of a system, through which routes are characterized by their destination, to alter the path that the route takes through the system in response to a change in conditions.[1] The adaptation is intended to allow as many routes as possible to remain valid (that is, have destinations that can be reached) in response to the change.
 +
 
 +
People using a transport system can display adaptive routing. For example, if a local railway station is closed, people can alight from a train at a different station and use another method, such as a bus, to reach their destination. Another example of adaptive routing can be seen within financial markets. For example, ASOR or Adaptive Smart Order Router (developed by Quod Financial), takes routing decisions dynamically and based on real-time market events.
 +
 
 +
The term is commonly used in data networking to describe the capability of a network to 'route around' damage, such as loss of a node or a connection between nodes, so long as other path choices are available. There are several protocols used to achieve this:
 +
RIP
 +
OSPF
 +
IS-IS
 +
IGRP/EIGRP
 +
 
 +
== Алгоритми на рутиращи протоколи ==
  
 
===Distance vector algorithms===
 
===Distance vector algorithms===
−
{{main|Distance-vector routing protocol}}
+
Вектор на разстоянието.
−
Distance vector algorithms use the [[Bellman-Ford]] algorithm. This approach assigns a number, the ''cost'', to each of the links between each node in the network. Nodes will send information from point A to point B via the path that results in the lowest ''total cost'' (i.e. the sum of the costs of the links between the nodes used).
+
 
 +
На всяка връзка между два нода се дава някаква стойност. Всеки нод ще препаща съобщение от точка А към точка B по пътя, който има най малка сумарна стойност.
 +
 
 +
При първоначалното включване на един нод, той знае единствено за връзките със своите съседи и стойността на тези връзките. Той прави таблица на тези връзки .
 +
 
 +
(This information, the list of destinations, the total cost to each, and the next hop to send data to get there, makes up the routing table, or distance table.)
 +
 
 +
 
 +
Процеса се извършва в следните две стъпки:
 +
*На определено време всеки нод изпраща до своите съседи таблица, в която са описани пътища с най-ниска стойност до мрежите, които са му известни.
  
−
The algorithm operates in a very simple manner. When a node first starts, it only knows of its immediate neighbours, and the direct cost involved in reaching them. (This information, the list of destinations, the total cost to each, and the ''next hop'' to send data to get there, makes up the routing table, or ''distance table''.) Each node, on a regular basis, sends to each neighbour its own current idea of the total cost to get to all the destinations it knows of. The neighbouring node(s) examine this information, and compare it to what they already 'know'; anything which represents an improvement on what they already have, they insert in their own routing table(s). Over time, all the nodes in the network will discover the best next hop for all destinations, and the best total cost.
+
*Всеки нод, който получи такава таблица е сравнява със своята таблица.  
 +
**Ако открие път до мрежа, която той не знае я добавя в собствената си таблица
 +
**Ако открие път с по-ниска стойност до дадена мрежа от колкото пътя записан в локалната таблица, той замества този запис с този от получената таблица.
 +
**Ако открие път в своята таблица, който минава минава през нода, чиято таблица е получена, но този път не съществува в получената таблица, този път се премахва от локалната таблица.  
  
−
When one of the nodes involved goes down, those nodes which used it as their next hop for certain destinations discard those entries, and create new routing-table information. They then pass this information to all adjacent nodes, which then repeat the process. Eventually all the nodes in the network receive the updated information, and will then discover new paths to all the destinations which they can still "reach".
+
След време всички нодове ще са открили пътя с най-ниска стойност до всяка мрежа.
−
eg RIPV1,RIPV2
+
 
 +
Когато някой нод спре да функционира, неговите съседи ще разберат по това, че той не праща съобщения и ще обновят своите таблици. При промяна на топологията.
  
 
===Link-state algorithms===
 
===Link-state algorithms===
−
{{main|Link-state routing protocol}}
 
−
When applying link-state algorithms, each node uses as its fundamental data a [[map]] of the network in the form of a [[graph (mathematics)|graph]]. To produce this, each node floods the entire network with information about what other nodes it can connect to, and each node then independently assembles this information into a map. Using this map, each router then independently determines the least-cost path from itself to every other node using a standard [[Shortest path problem|shortest paths]] algorithm such as [[Dijkstra's algorithm]]. The result is a [[Tree (graph theory)|tree]] rooted at the current node such that the path through the tree from the root to any other node is the least-cost path to that node. This tree then serves to construct the routing table, which specifies the best next hop to get from the current node to any other node.
 
  
−
===Optimised Link State Routing algorithm===
+
When applying link-state algorithms, each node uses as its fundamental data a map of the network in the form of a graph. To produce this, each node floods the entire network with information about what other nodes it can connect to, and each node then independently assembles this information into a map. Using this map, each router then independently determines the least-cost path from itself to every other node using a standard shortest paths algorithm such as Dijkstra's algorithm. The result is a tree rooted at the current node such that the path through the tree from the root to any other node is the least-cost path to that node. This tree then serves to construct the routing table, which specifies the best next hop to get from the current node to any other node.
−
{{main|Optimized Link State Routing Protocol}}
+
 
−
A link-state routing algorithm optimised for [[mobile ad-hoc network]]s is the ''Optimised Link State Routing Protocol (OLSR)''.<ref>RFC 3626</ref> OLSR is proactive; it uses Hello and Topology Control (TC) messages to discover and disseminate link state information through the [[mobile ad-hoc network]]. Using Hello messages, each node discovers 2-hop neighbor information and elects a set of ''[[multipoint relay]]s'' (MPRs). MPRs distinguish OLSR from other link state routing protocols.
+
===Optimised Link State Routing algorithm ===
 +
 
 +
A link-state routing algorithm optimised for mobile ad-hoc networks is the Optimised Link State Routing Protocol (OLSR).[1] OLSR is proactive; it uses Hello and Topology Control (TC) messages to discover and disseminate link state information through the mobile ad-hoc network. Using Hello messages, each node discovers 2-hop neighbor information and elects a set of multipoint relays (MPRs). MPRs distinguish OLSR from other link state routing protocols.
  
 
===Path vector protocol===
 
===Path vector protocol===
−
{{main|Path vector protocol}}
 
−
Distance vector and link state routing are both intra-domain routing protocols. They are used inside an [[Autonomous system (Internet)|autonomous system]], but not between autonomous systems. Both of these routing protocols become intractable in large networks and cannot be used in [[Inter-domain]] routing. Distance vector routing is subject to instability if there are more than a few hops in the domain. Link state routing needs huge amount of resources to calculate routing tables. It also creates heavy traffic due to flooding.
 
−
 
−
Path vector routing is used for inter-domain routing. It is similar to distance vector routing. In path vector routing we assume there is one node (there can be many) in each autonomous system which acts on behalf of the entire autonomous system. This node is called the speaker node. The speaker node creates a routing table and advertises it to neighboring speaker nodes in neighboring autonomous systems. The idea is the same as distance vector routing except that only speaker nodes in each autonomous system can communicate with each other. The speaker node advertises the path, not the metric of the nodes, in its autonomous system or other autonomous systems.
 
−
Path vector routing is discussed in RFC 1322; the path vector routing algorithm is somewhat similar to the distance vector algorithm in the sense that each border router advertises the destinations it can reach to its neighboring router. However, instead of advertising networks in terms of a destination and the distance to that destination, networks are advertised as destination addresses and path descriptions to reach those destinations. A route is defined as a pairing between a destination and the attributes of the path to that destination, thus the name, path vector routing, where the routers receive a vector that contains paths to a set of destinations.
 
−
The path, expressed in terms of the domains (or confederations) traversed so far, is carried in a special path attribute that records the sequence of routing domains through which the reachability information has passed.
 
  
−
===Comparison of routing algorithms===
+
Distance vector and link state routing are both intra-domain routing protocols. They are used inside an autonomous system, but not between autonomous systems. Both of these routing protocols become intractable in large networks and cannot be used in Inter-domain routing. Distance vector routing is subject to instability if there are more than a few hops in the domain. Link state routing needs huge amount of resources to calculate routing tables. It also creates heavy traffic due to flooding.
−
[[Distance-vector routing protocols]] are simple and efficient in small networks and require little, if any, management. However, traditional distance-vector algorithms have poor [[Convergence (routing)|convergence]] properties due to the [[count-to-infinity problem]].
 
  
−
This has led to the development of more complex but more scalable algorithms for use in large networks. Interior routing mostly uses [[link-state routing protocol]]s such as [[OSPF]] and [[IS-IS]].
+
Path vector routing is used for inter-domain routing. It is similar to distance vector routing. In path vector routing we assume there is one node (there can be many) in each autonomous system which acts on behalf of the entire autonomous system. This node is called the speaker node. The speaker node creates a routing table and advertises it to neighboring speaker nodes in neighboring autonomous systems. The idea is the same as distance vector routing except that only speaker nodes in each autonomous system can communicate with each other. The speaker node advertises the path, not the metric of the nodes, in its autonomous system or other autonomous systems. Path vector routing is discussed in RFC 1322; the path vector routing algorithm is somewhat similar to the distance vector algorithm in the sense that each border router advertises the destinations it can reach to its neighboring router. However, instead of advertising networks in terms of a destination and the distance to that destination, networks are advertised as destination addresses and path descriptions to reach those destinations. A route is defined as a pairing between a destination and the attributes of the path to that destination, thus the name, path vector routing, where the routers receive a vector that contains paths to a set of destinations. The path, expressed in terms of the domains (or confederations) traversed so far, is carried in a special path attribute that records the sequence of routing domains through which the reachability information has passed.
  
−
A more recent development is that of loop-free [[distance-vector protocols]] (e.g., [[EIGRP]]). Loop-free distance-vector protocols are as robust and manageable as native distance-vector protocols, but avoid counting to infinity, and have good worst-case [[Convergence (routing)#Convergence time|convergence times]].
+
Each entry in the routing table contains the destination network, the next router and the path to reach the destination.
  
−
==Path selection==
+
===Сравнение на рутиращи алгоритмни===
−
Path selection involves applying a [[Metrics (networking)|routing metric]] to multiple routes, in order to select (or predict) the best route.
 
  
−
In the case of computer networking, the metric is computed by a routing algorithm, and can cover such information as [[Bandwidth (computing)|bandwidth]], [[network delay]], [[hop count]], path cost, load, [[MTU (networking)|MTU]], reliability, and communication cost (see e.g. [http://rainer.baumann.info/public/tik262.pdf this survey ] for a list of proposed routing metrics). The routing table stores only the best possible routes, while [[link-state]] or topological databases may store all other information as well.
 
  
−
Because a routing metric is specific to a given routing protocol, multi-protocol routers must use some external heuristic in order to select between routes learned from different routing protocols. [[Cisco]]'s routers, for example, attribute a value known as the [[administrative distance]] to each route, where smaller administrative distances indicate routes learned from a supposedly more reliable protocol.
+
Distance-vector routing protocols are simple and efficient in small networks and require little, if any, management. However, traditional distance-vector algorithms have poor convergence properties due to the count-to-infinity problem.
  
−
A local network administrator, in special cases, can set up host-specific routes to a particular machine which provides more control over network usage, permits testing and better overall security. This can come in handy when required to debug network connections or routing tables.
+
This has led to the development of more complex but more scalable algorithms for use in large networks. Interior routing mostly uses link-state routing protocols such as OSPF and IS-IS.
  
−
==Multiple agents==
+
A more recent development is that of loop-free distance-vector protocols (e.g., EIGRP). Loop-free distance-vector protocols are as robust and manageable as native distance-vector protocols, but avoid counting to infinity, and have good worst-case convergence times.
−
In some networks, routing is complicated by the fact that no single entity is responsible for selecting paths: instead, multiple entities are involved in selecting paths or even parts of a single path. Complications or inefficiency can result if these entities choose paths to optimize their own objectives, which may conflict with the objectives of other participants.
 
  
−
A classic example involves traffic in a road system, in which each driver picks a path which minimizes their own travel time. With such routing, the [[Nash equilibrium|equilibrium]] routes can be longer than optimal for all drivers. In particular, [[Braess paradox]] shows that adding a new road can ''lengthen'' travel times for all drivers.
+
==Рутиращи протоколи==
 +
===RIP ===
 +
RIP (routing information protocol) e широко използван маршрутизиращ протокол с вектор на разстоянието. Той е подходящ предимно за малки мрежи, в които относително рядко настъпват промени в топологията.
 +
Всеки ред в маршрутната таблица на RIP маршрутизаторите съдържа информация за направлението, следваща стъпка към това направление и метрика. Метриката обозначава разстоянието в стъпки до местоназначението, т.е. метриката използвана от RIP протокола е брой хопове.
 +
Както повечето маршрутизиращи протоколи, RIP също използва таймери. Обикновено на всеки 30 секудни се изпраща копие на маршрутната таблица към съседните маршрутизатори. Този интервал се задава от таймера за обновяване (route update timer) и е общ за всички маршрути. Таймерът за невалиден маршрут (route timeout timer) определя интервала от време, след който даден маршрут се счита за невалиден, ако маршрутизаторът не е получил съобщения за него. Когато даден път бъде отбелязан като невалиден, се изпращат съобщения с тази информация към съседните маршрутизатори и се преустановява използването му. Тези съобщения се изпращат до изтичането на таймера за изтриване на маршрут (garbage-collection timer), след което пътя се изтрива от маршрутната таблица.
 +
Първата версия на RIP не поддържа подмаски, т.е. от гледна точка на IP не поддържа подмрежи, затова в края на 80-те години се разработва втора версия на RIP. Формата на пакетите на версия RIP-2 е следния:
  
−
In another model, for example used for routing [[automated guided vehicle]]s (AGVs) on a terminal, reservations are made for each vehicle to prevent simultaneous use of the same part of an infrastructure. This approach is also referred to as context-aware routing.<ref>
+
Първите три полета Command, Version и Routing domain представляват заглавната част на пакета, а останалите шест полета съдържат данни за маршрути и комбинация от тях може да се повтаря до 25 пъти в един RIP-2 пакет. За пренасяне на информацията от по-големи маршутни таблици се използват няколко RIP-2 пакета.
−
Jonne Zutt, Arjan J.C. van Gemund, Mathijs M. de Weerdt, and Cees Witteveen (2010). [http://www.st.ewi.tudelft.nl/~mathijs/publications/intinfra09.pdf Dealing with Uncertainty in Operational Transport Planning]. In R.R. Negenborn and Z. Lukszo and H. Hellendoorn (Eds.) Intelligent Infrastructures, Ch. 14, pp. 355-382. Springer.</ref>
+
Полето Command указва дали пакетът съдържа заявка или отговор. Командата “Заявка” изисква отговарящата система да изпрати цялата или част от маршрутната си таблица. Командата “Отговор” представлява отговор на получена команда “Заявка” или периодично съобщение за обновяване на маршрутите, в което се включва цялата маршрутна таблица.
 +
Полето Version указва версията на протокола, за RIP-2 тази стойност е 2.
 +
Полето Routing domain не се използва.
 +
Полето Address family е идентификатор на адресна фамилия. Въвежда се идентификация на група от маршрутизатори. Всички маршутизатори в една група имат една и съща адресна фамилия.
 +
Полето Route tag указва дали информацията за даден маршрут произхожда от RIP или от друг вътрешен или външен маршутизиращ протокол.
 +
Полето IP address съдържа IP адреса на мрежа или хост, която представлява местоназначението на описвания маршрут.
 +
Полето Net mask е мрежовата маска, отнасяща се за горния IP адрес.
 +
Полето Next hop IP address съдържа IP адрес на най-близкия машрутизатор, към който ще се изпрати пакета.
 +
Полето Metric указва броя хопове до съответното местоназначение и може да има стойност от 1 (директно свързана мрежа) до 16 (недостъпен маршрут – безкрайност).
  
−
The Internet is partitioned into [[autonomous system (Internet)|autonomous systems]] (ASs) such as [[internet service provider]]s (ISPs), each of which has control over routes involving its network, at multiple levels. First, AS-level paths are selected via the [[Border Gateway Protocol|BGP]] protocol, which produces a sequence of ASs through which packets will flow. Each AS may have multiple paths, offered by neighboring ASs, from which to choose. Its decision often involves business relationships with these neighboring ASs,<ref>Matthew Caesar and Jennifer Rexford. [http://www.cs.princeton.edu/~jrex/papers/policies.pdf BGP routing policies in ISP networks]. IEEE Network Magazine, special issue on Interdomain Routing, Nov/Dec 2005.</ref> which may be unrelated to path quality or latency. Second, once an AS-level path has been selected, there are often multiple corresponding router-level paths, in part because two ISPs may be connected in multiple locations. In choosing the single router-level path, it is common practice for each ISP to employ [[hot-potato routing]]: sending traffic along the path that minimizes the distance through the ISP's own network—even if that path lengthens the total distance to the destination.
+
В първия от 25-те записа на RIP-2 пакета полето Address family може да има стойност 0xFFFF, която указва че следва идентификационна информация за подателя на пакета. В този случай полето Route tag определя използвания алгоритъм, а следващите 16 байта съдържат парола. Използването на този механизъм намалява максималния брой маршрути в един RIP-2 пакет на 24.
  
−
Consider two ISPs, ''A'' and ''B'', which each have a presence in [[New York City|New York]], connected by a fast link with latency 5 [[millisecond|ms]]; and which each have a presence in [[London]] connected by a 5 ms link. Suppose both ISPs have trans-Atlantic links connecting their two networks, but ''A''<nowiki>'s</nowiki> link has latency 100 ms and B's has latency 120 ms. When routing a message from a source in ''A''<nowiki>'s</nowiki> London network to a destination in ''B''<nowiki>'s</nowiki> New York network, ''A'' may choose to immediately send the message to ''B'' in London. This saves ''A'' the work of sending it along an expensive trans-Atlantic link, but causes the message to experience latency 125 ms when the other route would have been 20 ms faster.
+
При промяна в топологията на мрежата се налага всички маршрутизатори да преизчислят своите вектори на разстоянията и да достигнат до непротиворечиво описание на новата топология. За увеличаване на скоростта на сходимост на RIP се използват различни методи, например разделяне на хоризонта. Тези методи намаляват вероятността за поява на цикли в маршрутите, но не могат да гарантират отсъствието им.
 +
Максималният брой хопове в RIP е 15. Всяко местоназначение, което е на разстояние над 15 хопа се приема за недостижимо. Това прави невъзможно прилагането на RIP в мрежи с диаметър над 15 хопа, но ограничава ситуацията “броене до безкрайност”, при която могат да се получат цикли в маршрутите.
  
−
A 2003 measurement study of Internet routes found that, between pairs of neighboring ISPs, more than 30% of paths have inflated latency due to hot-potato routing, with 5% of paths being delayed by at least 12 ms. Inflation due to AS-level path selection, while substantial, was attributed primarily to BGP's lack of a mechanism to directly optimize for latency, rather than to selfish routing policies. It was also suggested that, were an appropriate mechanism in place, ISPs would be willing to cooperate to reduce latency rather than use hot-potato routing.<ref>Neil Spring, Ratul Mahajan, and Thomas Anderson. [http://www.cs.washington.edu/research/networking/rocketfuel/papers/sigcomm2003.pdf Quantifying the Causes of Path Inflation]. Proc. [[SIGCOMM]] 2003.</ref>
+
Във версията RIP-2 са избегнати някои от недостатъците на RIP-1, но тя продължава да бъде приложима само в малки мрежи поради ниския максимален брой хопове и сравнително ниската и скорост на сходимост. Въпреки наследените от RIP-1 недостатъци и наличието на протоколи, в които те са избегнати, протоколът RIP-2 продължава да се използва, тъй като е лесен за реализация и конфигуриране и се нуждае от сравнително малко машинни и мрежови ресурси.
  
−
Such a mechanism was later published by the same authors, first for the case of two ISPs<ref>Ratul Mahajan, David Wetherall, and Thomas Anderson. [http://research.microsoft.com/en-us/um/people/ratul/papers/nsdi2005-nexit.pdf Negotiation-Based Routing Between Neighboring ISPs]. Proc. [[NSDI]] 2005.</ref> and then for the global case.<ref>Ratul Mahajan, David Wetherall, and Thomas Anderson. [http://research.microsoft.com/en-us/um/people/ratul/papers/nsdi2007-wiser.pdf Mutually Controlled Routing with Independent ISPs]. Proc. [[NSDI]] 2007.</ref>
+
Internet е съвкупност от физически различни мрежи, които са обединени посредством общ протоколен стек, така че логически да се формира една обща мрежа. Най-лесният начин да се изгради такава мрежа е чрез свързване на две или повече мрежи чрез маршрутизатор (router). Маршрутизаторът представлява специализирано устройство, което дава възможност за свързване на различни типове физически мрежи. Основни функции на маршрутизатора са определяне за всеки получен пакет на най-добрия маршут до хоста-получател на пакета и препредаване на този пакет към следващия маршрутизатор по този маршрут. Последният маршрутизатор от пътя препредава пакета директно към хоста-получател. Информацията за най-добрите маршрути се съхраняват в маршрутни таблици. За определяне на най-добрия маршрут маршрутизаторите обменят помежду си информация, като за оценка използват различна метрика. Обикновено тази метрика включва следните величини: дължина на пътя, надеждност, закъснение на пакета при предаването от източника до получателя, пропусквателна способност на комуникационните линии, натоварване на маршрутизаторите, цена на комуникационните линии.
  
−
==Route analytics==
+
=== OSPF ===
−
As the Internet and IP networks become [[mission critical]] business tools, there has been increased interest in techniques and methods to monitor the routing posture of networks. Incorrect routing or routing issues cause undesirable performance degradation, flapping and/or downtime. Monitoring routing in a network is achieved using [[route analytics]] tools and techniques.
 
  
−
==See also==
+
Протоколът OSPF (open shortest path first) е разработен за IP мрежи и използва алгоритъма за маршрутизиране със следене състоянието на връзката (link state).
 +
OSPF маршрутизаторите поддържат топологични бази данни с информация за състоянието на връзките в мрежата. Тези бази данни периодично се обновяват посредством обмен на съобщения за състоянието на връзките и съдържат входните данни за алгоритъма на Дейкстра, който се изпълнява от всеки маршрутизатор. В резултат от неговото изпълнение, всеки OSPF маршрутизатор намира най-късите от своя гледна точка пътища до всички известни местоназначения в мрежата.
  
−
===Routing algorithms and techniques===
+
Важна особеност на OSPF е йерархичното разделяне на автономните системи на области (area). Връзките между различните области се осъществяват задължително през опорна мрежа (backbone), която е особена област с номер 0. Според принадлежността към OSPF областите различаваме 4 вида маршрутизатори:
−
<div style="-moz-column-count:2; column-count:2;">
+
вътрешни маршрутизатори (internal routers), всичките интерфейси на които са свързани към мрежи от една OSPF област;
−
* [[Inter domain routing algorithm]]
+
областни гранични маршрутизатори (area border routers), интерфейсите на които са свързани към мрежи от две или повече OSPF области, една от които задължително е опорната мрежа. Тези маршрутизатори поддържат топологични бази данни с информация за състоянието на връзките в областите, към които са свързани, и изпълняват алгоритъма на Дейкстра поотделно за всяка от тях;
−
* [[Intra domain routing algorithm]]
+
опорни маршрутизатори (backbone routers), на които поне един от интерфейсите е свързан с опорната мрежа на област 0. Опорните маршрутизатори могат да бъдат областни гранични маршрутизатори, но това не е задължително;
−
* [[Adaptive routing]]
+
гранични за автономната система маршрутизатори (AS boundary routers), които са свързани към поне две различни автономни системи и изпълняват освен OSPF друг външен маршрутизиращ протокол (например BGP).
−
* [[Alternative-path routing]]
 
−
* [[Deflection routing]]
 
−
* [[Edge Disjoint Shortest Pair Algorithm]]
 
−
* [[Dijkstra's algorithm]]
 
−
* [[Fuzzy routing]]
 
−
* [[Geographic routing]]
 
−
* [[Heuristic routing]]
 
−
* [[Hierarchical routing]]
 
−
* [[IP forwarding algorithm|IP Forwarding Algorithm]]
 
−
* [[Multipath routing]]
 
−
* [[Overlay network]] routing schemes
 
−
** [[Key-based routing]] (KBR)
 
−
** [[Decentralized object location and routing]] (DOLR)
 
−
** [[Group anycast and multicast]] (CAST)
 
−
** [[Distributed hash table]] (DHT)
 
−
* [[Path computation element]] (PCE)
 
−
* [[Policy-based routing]]
 
−
* [[Quality of Service]] in routing
 
−
* [[Static routing]]
 
−
* [[Backward learning routing]]
 
−
</div>
 
  
−
===Routing in specific networks===
+
Опорните маршутизатори могат същевременно да бъдат вътрешни, ако всичките им интерфейси са свързани към опорната мрежа.
−
* [[Open Source Routing Machine]] (Road map routing)
+
В рамките на една област всички маршрутизатори имат една и съща топологична база данни. Нейното предназначение е да се изчислят най-късите пътища между дадения маршрутизатор и всички останали маршутизатори в областта.
−
* [[Route assignment]] in transportation networks
+
Йерархичните области в OSPF мрежите увеличават скоростта на сходимост на протокола и намаляват натоварването на необходимите за работата му мрежови и изчислителни ресурси.
−
* [[Routing in the PSTN]]
+
OSPF поддържа три вида различни връзки:
−
* [[Small world routing]] - the internet is approximately a small world network
+
връзка от тип “точка-точка” между два маршрутизатора;
 +
многоточкови мрежи с broadcast (например, повечето LAN);
 +
многоточкови мрежи без broadcast (например, повечето WAN с комутация на пакети).
  
−
===Routing protocols===
+
OSPF работи чрез обмяна на информация между прилежащи маршрутизатори, което не е същото като съседни маршрутизатори. Това се прави, тъй като не е ефективно всеки два маршрутизатора да обменят данни. За целта се избира един титулярен маршрутизатор (designated router), който става прилежащ към всички останали маршрутизатори и всеки от тях синхронизира топологичната си база данни с неговата. Ако настъпи промяна в състоянието на връзките на даден маршрутизатор, той изпраща съобщение на титулярния маршрутизатор, а от своя страна той съобщава промяната на всички останали маршрутизатори в мрежата. При отпадане на титулярния маршрутизатор има заместник, който е в състояние веднага да поеме неговите функции.
−
* [[Routing protocol]]
 
−
* [[Classless inter-domain routing]] (CIDR)
 
−
* [[Multiprotocol Label Switching|MPLS]] routing
 
−
* [[Asynchronous Transfer Mode|ATM]] routing
 
−
* [[RPSL]]
 
−
* [[RSMLT]]
 
−
* Routing in [[optical mesh network]]s
 
  
−
===Alternative methods for network data flow===
+
Форматът на OSPF пакета е следния:
−
* [[Peer-to-peer]]
 
−
* [[Network coding]]
 
  
−
===Router Software and Suites===
+
Полето Version number съдържа номера на версията на OSPF, която се използва.
−
* [[GNU Zebra]]
+
Полето Type определя типа на съобщението. Има няколко типа съобщения:
−
* [[Quagga (software)]]
+
“ехо” пакет (hello packet) – той се използва при откриване на съседни маршрутизатори, за проверяване на работоспособността на връзките и за избор на титулярен маршрутизатор;
−
* [[Iproute2]]
+
описание на база данни (database description) – разменят се при първоначално установяване на връзка между два маршрутизатора и служат за обмен на информация за състоянието на връзките в областта от техните топологични бази данни;
−
* [[Bird Internet routing daemon]]
+
пакет за запитване (link-state request) – чрез него даден маршрутизатор може да поиска информация от друг маршрутизатор за част от записите в неговата топологична база данни за състоянието на връзките;
 +
пакет за обновяване (link-state update) – тези пакети се изпращат периодично от всеки маршрутизатор и съдържат данни за неговото състояние и за цените, използвани в топологичната база данни; разпространяват се по метода на наводняването към всички останали маршрутизатори в границите на дадена област;
 +
пакет за потвърждение (link-state acknowledgement) – механизмът за надеждно доставяне на пакетите за обновяване изисква при получаването им да се изпращат потвърждения.
 +
Полето Packet length съдържа общата дължина на OSPF пакета, включват се заглавната част и данните.
 +
Полето Router ID съдържа уникален за автономната система идентификатор на маршрутизатора, изпратил пакета.
 +
Полето Area ID съдържа номера на областта, към която е свързан интерфейса на маршрутизатора-подател на пакета.
 +
Полето Check sum е контролна сума, която се изчислява върху цялото съдържание на OSPF пакета. Служи за проверка дали пакета е бил предаден правилно.
 +
Полето Authentication type указва вида на използвания механизъм за идентифициране на подателя на пакета. Проблемът е, че в мрежата може да проникнат фалшиви пакети, които дублират информацията за състояние на връзките на някой маршрутизатор. За това трябва да се установява автентичността на пакетите.
 +
Полето Authentication съдържа автентицираща информация.
  
−
===Router Platforms===
+
===BGP===
−
* [[Network operating system]] - NOS
+
В рамките на една автономна система се използват вътрешни протоколи за маршрутизиране, например RIP или OSPF. Тяхната цел е максимално бързо и ефективно да предават пакети от източника до получателя.
−
* [[XORP]] - the eXtensible Open Router Platform
+
За маршрутизиране между различни автономни системи се използват външни маршрутизиращи протоколи. Такъв протокол е BGP (border gateway protocol). В него се залага на политиката на маршрутизация – например, най-прекият път между две автономни системи не винаги е разумен. В политиката се включват икономически, административни и други фактори. Примери за политически ограничения:
−
* [[FTOS]] - Dell's Force 10 firmware family
+
да не се позволява транзитен трафик през дадена автономна система;
−
* [[Junos]]
+
трафикът за Пентагона да не минава през Ирак;
−
* [[Cisco IOS]]
+
трафикът, започващ или свършващ в IBM да не минава през Microsoft.
−
* [[NX-OS]]
+
Политическите ограничения се конфигурират ръчно и не са част от BGP протокола.
−
* [[CatOS]]
 
  
−
==References==
+
От гледна точка на един BGP маршрутизатор, светът се състои от автономни системи, свързани с линии. Две автономни системи са свързани, ако има линия между гранични маршрутизатори във всяка от тях. От гледна точка на транзитния трафик BGP мрежите се делят на три вида:
−
{{reflist}}
+
stub мрежи – те имат само една връзка в BGP графа и не могат да се използват за транзитен трафик;
−
{{more footnotes|date=October 2011}}
+
multiconnected мрежи – те могат да се използват за транзитен трафик, но самите те отказват да го правят;
−
{{refbegin}}
+
transit networks – например опорните мрежи, които пренасят транзитен трафик, обикновено срещу заплащане.
−
* {{cite book | author=Ash, Gerald | title=Dynamic Routing in Telecommunication Networks | publisher=McGraw-Hill | year=1997 | isbn=0-07-006414-8}}
 
−
* {{cite book | author=Doyle, Jeff and Carroll, Jennifer | title=Routing TCP/IP, Volume I, Second Ed. | publisher=Cisco Press | year=2005 | isbn=1-58705-202-4}}[http://www.ciscopress.com/title/1587052024 <nowiki>Ciscopress ISBN 1-58705-202-4</nowiki>]
 
−
* {{cite book | author=Doyle, Jeff and Carroll, Jennifer | title=Routing TCP/IP, Volume II, | publisher=Cisco Press | year=2001 | isbn=1-57870-089-2}}[http://www.ciscopress.com/title/1578700892 <nowiki>Ciscopress ISBN 1-57870-089-2</nowiki>]
 
−
* {{cite book | author=Huitema, Christian | title=Routing in the Internet, Second Ed. | publisher=Prentice-Hall | year=2000 | isbn=0-321-22735-2}}
 
−
* {{cite book | author=Kurose, James E. and Ross, Keith W. | title=Computer Networking, Third Ed. | publisher=Benjamin/Cummings | year=2004 | isbn=0-321-22735-2}}
 
−
* {{cite book | author=Medhi, Deepankar and Ramasamy, Karthikeyan | title=Network Routing: Algorithms, Protocols, and Architectures | publisher=Morgan Kaufmann | year=2007 | isbn=0-12-088588-3}}
 
−
{{refend}}
 
  
−
==External links==
+
BGP протокола се базира на алгоритъма с вектор на разстоянието, но се различава доста от него. Вместо да се поддържа само цената към всяко местоназначение, всеки BGP маршрутизатор поддържа целия път към местоназначението. Освен това, вместо периодично да подава на съседите си цените до местоназначенията, всеки BGP маршрутизатор подава на съседите си целите пътища, които те използват. Това има смисъл, тъй като графът с възли автономните системи не е безмерно голям.
−
* [http://wiki.uni.lu/secan-lab/Count-To-Infinity+Problem.html Count-To-Infinity Problem]
+
Като пример да разгледаме следната мрежа от BGP маршрутизатори:
−
* [http://wwwlehre.dhbw-stuttgart.de/~schulte/htme/55024.htm#HDR3 "Stability Features"] are ways of avoiding the "count to infinity" problem.
 
−
* [http://www.cisco.com/web/about/ciscoitatwork/case_studies/routing.html Cisco IT Case Studies] about Routing and Switching
 
−
* [http://www.eventhelix.com/Realtimemantra/Networking/ip_routing.htm good example at event-helix]
 
−
{{Routing protocols}}
 
  
−
[[Category:Компютърни мрежи]]
+
По-конкретно да разгледаме маршрутизатора F. Той получава от съседите си следните пътища до D – път BCD от B, път GCD от G, път IFGCD от I и път EFGCD от E. F преглежда тези пътища за да определи кой е най-добрия. Той премахва пътищата от I и E, тъй като минават през него. Изборът е между B и G. Всеки BGP маршрутизатор съдържа модул, който изследва пътищата до дадено местоназначение и ги оценява. Път, който нарушава политическо ограничение автоматично получава оценка безкрайност. Маршрутизаторът избира пътят с най-ниска оценка. Оценяващата функция не е част от BGP протокола.
 +
При BGP лесно се решава проблемът “броене до безкрайност”. Например, да предположим, че G пропадне или, че линията FG става недостъпна. Тогава F получава маршрути от останалите си три съседа. Тези маршрути са BCD, IFGCD и EFGCD. F бързо премахва последните два пътя, тъй като те са безсмислени – преминават през него и за това избира FBCD като нов маршрут. Другите алгоритми с вектор на разстоянието често правят погрешен избор, тъй като те не могат да съобщят кой от съседите има независим маршрут до местоназначението и кой няма.

Latest revision as of 11:38, 7 January 2013

Какво е маршрутизация

Маршрутизация или рутиране е процес на избиране на път в дадена мрежа, по който да се изпрати мрежовия трафик.

Рутиране има в различни мрежи - телефонни мрежи (комутационни вериги), транспортни мрежи (логистика), компютърни мрежи (пакетна комутация).

В компютърните мрежи информацията се предава на пакети, затова рутирането се занимава с препращането на пакет от комуникационна точка към друга комуникационна точка (нод - възел, който в частност може да е router, bridge, gateway, firewall, switch или host). Целта е информационният пакет да бъде пренесен от началната точка до крайната точка.

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

Рутиращата машина препраща пакети според своята рутираща таблица, в която са описани пътищата до различни дестинации (мрежи). Оптималното конструиране на рутиращата таблица е много важно за ефективно рутиране.


Трафик според дестинация

  • anycast - до всеки от група нодове
  • broadcast - до всички нодове
  • multicast - до група от нодове
  • unicast - до точно определен нод
  • geocast - до географска област

Видове рутиране

Статично рутиране

На практика малки мрежи могат да използват ръчно конфигурирани рутиращи таблици, това се нарича статично рутиране (не адаптивно).

Приципно цялата мрежа може да бъде конфигурирана статично, но по този начин мрежата не е устойчива на повреда в даден нод. Ако има промяна и повреда в мрежата трафика няма да може да се пренасочи. Трябва да бъдат обновени съответните рутиращи таблици или да бъде отсранена повредата, за да може мрежата да функционира нормално.

При някои обстоятелства статичното рутиране би могло да е от полза - stub networks, default routes

Пример

To configure a static route to network 10.10.20.0/24, pointing to a next-hop router with the IP address of 192.168.100.1, type: 

Cisco IOS
ip route 10.10.20.0 255.255.255.0 192.168.100.1 
Linux
route add -net 10.10.20.0 netmask 255.255.255.0 gw 192.168.1.100

The other option is to define a static route with reference to the outgoing interface which is connected to the next hop towards the destination network. 

Cisco IOS
ip route 10.10.20.0 255.255.255.0 FastEthernet 0/0
Linux
route add -net 10.10.20.0 netmask 255.255.255.0 dev eth0

Динамично рутиране

Големите мрежи имат сложна топология, която своевременно може многократно да се променя. Това прави ръчната конфигурация неприложима. Динамичното (адаптивното) рутиране позволява автоматична настройка на рутиращата таблица. Последната се променя според информацията, която се обменя между нодовете посредством рутиращи протоколи и заложениете локални предпочетания за всеки нод.

Примери за такива протоколи са RIP - Routing Information Protocol и OSPF (Open-Shortest-Path-First protocol). Дънамичното рутиране пробладава в Интернет, но изисква съответните познания за правилното му конфигуриране.

Adaptive routing describes the capability of a system, through which routes are characterized by their destination, to alter the path that the route takes through the system in response to a change in conditions.[1] The adaptation is intended to allow as many routes as possible to remain valid (that is, have destinations that can be reached) in response to the change.

People using a transport system can display adaptive routing. For example, if a local railway station is closed, people can alight from a train at a different station and use another method, such as a bus, to reach their destination. Another example of adaptive routing can be seen within financial markets. For example, ASOR or Adaptive Smart Order Router (developed by Quod Financial), takes routing decisions dynamically and based on real-time market events.

The term is commonly used in data networking to describe the capability of a network to 'route around' damage, such as loss of a node or a connection between nodes, so long as other path choices are available. There are several protocols used to achieve this: RIP OSPF IS-IS IGRP/EIGRP

Алгоритми на рутиращи протоколи

Distance vector algorithms

Вектор на разстоянието.

На всяка връзка между два нода се дава някаква стойност. Всеки нод ще препаща съобщение от точка А към точка B по пътя, който има най малка сумарна стойност.

При първоначалното включване на един нод, той знае единствено за връзките със своите съседи и стойността на тези връзките. Той прави таблица на тези връзки .

(This information, the list of destinations, the total cost to each, and the next hop to send data to get there, makes up the routing table, or distance table.)


Процеса се извършва в следните две стъпки:

  • На определено време всеки нод изпраща до своите съседи таблица, в която са описани пътища с най-ниска стойност до мрежите, които са му известни.
  • Всеки нод, който получи такава таблица е сравнява със своята таблица.
    • Ако открие път до мрежа, която той не знае я добавя в собствената си таблица
    • Ако открие път с по-ниска стойност до дадена мрежа от колкото пътя записан в локалната таблица, той замества този запис с този от получената таблица.
    • Ако открие път в своята таблица, който минава минава през нода, чиято таблица е получена, но този път не съществува в получената таблица, този път се премахва от локалната таблица.

След време всички нодове ще са открили пътя с най-ниска стойност до всяка мрежа.

Когато някой нод спре да функционира, неговите съседи ще разберат по това, че той не праща съобщения и ще обновят своите таблици. При промяна на топологията.

Link-state algorithms

When applying link-state algorithms, each node uses as its fundamental data a map of the network in the form of a graph. To produce this, each node floods the entire network with information about what other nodes it can connect to, and each node then independently assembles this information into a map. Using this map, each router then independently determines the least-cost path from itself to every other node using a standard shortest paths algorithm such as Dijkstra's algorithm. The result is a tree rooted at the current node such that the path through the tree from the root to any other node is the least-cost path to that node. This tree then serves to construct the routing table, which specifies the best next hop to get from the current node to any other node.

Optimised Link State Routing algorithm

A link-state routing algorithm optimised for mobile ad-hoc networks is the Optimised Link State Routing Protocol (OLSR).[1] OLSR is proactive; it uses Hello and Topology Control (TC) messages to discover and disseminate link state information through the mobile ad-hoc network. Using Hello messages, each node discovers 2-hop neighbor information and elects a set of multipoint relays (MPRs). MPRs distinguish OLSR from other link state routing protocols.

Path vector protocol

Distance vector and link state routing are both intra-domain routing protocols. They are used inside an autonomous system, but not between autonomous systems. Both of these routing protocols become intractable in large networks and cannot be used in Inter-domain routing. Distance vector routing is subject to instability if there are more than a few hops in the domain. Link state routing needs huge amount of resources to calculate routing tables. It also creates heavy traffic due to flooding.

Path vector routing is used for inter-domain routing. It is similar to distance vector routing. In path vector routing we assume there is one node (there can be many) in each autonomous system which acts on behalf of the entire autonomous system. This node is called the speaker node. The speaker node creates a routing table and advertises it to neighboring speaker nodes in neighboring autonomous systems. The idea is the same as distance vector routing except that only speaker nodes in each autonomous system can communicate with each other. The speaker node advertises the path, not the metric of the nodes, in its autonomous system or other autonomous systems. Path vector routing is discussed in RFC 1322; the path vector routing algorithm is somewhat similar to the distance vector algorithm in the sense that each border router advertises the destinations it can reach to its neighboring router. However, instead of advertising networks in terms of a destination and the distance to that destination, networks are advertised as destination addresses and path descriptions to reach those destinations. A route is defined as a pairing between a destination and the attributes of the path to that destination, thus the name, path vector routing, where the routers receive a vector that contains paths to a set of destinations. The path, expressed in terms of the domains (or confederations) traversed so far, is carried in a special path attribute that records the sequence of routing domains through which the reachability information has passed.

Each entry in the routing table contains the destination network, the next router and the path to reach the destination.

Сравнение на рутиращи алгоритмни

Distance-vector routing protocols are simple and efficient in small networks and require little, if any, management. However, traditional distance-vector algorithms have poor convergence properties due to the count-to-infinity problem.

This has led to the development of more complex but more scalable algorithms for use in large networks. Interior routing mostly uses link-state routing protocols such as OSPF and IS-IS.

A more recent development is that of loop-free distance-vector protocols (e.g., EIGRP). Loop-free distance-vector protocols are as robust and manageable as native distance-vector protocols, but avoid counting to infinity, and have good worst-case convergence times.

Рутиращи протоколи

RIP

RIP (routing information protocol) e широко използван маршрутизиращ протокол с вектор на разстоянието. Той е подходящ предимно за малки мрежи, в които относително рядко настъпват промени в топологията. Всеки ред в маршрутната таблица на RIP маршрутизаторите съдържа информация за направлението, следваща стъпка към това направление и метрика. Метриката обозначава разстоянието в стъпки до местоназначението, т.е. метриката използвана от RIP протокола е брой хопове. Както повечето маршрутизиращи протоколи, RIP също използва таймери. Обикновено на всеки 30 секудни се изпраща копие на маршрутната таблица към съседните маршрутизатори. Този интервал се задава от таймера за обновяване (route update timer) и е общ за всички маршрути. Таймерът за невалиден маршрут (route timeout timer) определя интервала от време, след който даден маршрут се счита за невалиден, ако маршрутизаторът не е получил съобщения за него. Когато даден път бъде отбелязан като невалиден, се изпращат съобщения с тази информация към съседните маршрутизатори и се преустановява използването му. Тези съобщения се изпращат до изтичането на таймера за изтриване на маршрут (garbage-collection timer), след което пътя се изтрива от маршрутната таблица. Първата версия на RIP не поддържа подмаски, т.е. от гледна точка на IP не поддържа подмрежи, затова в края на 80-те години се разработва втора версия на RIP. Формата на пакетите на версия RIP-2 е следния:

Първите три полета Command, Version и Routing domain представляват заглавната част на пакета, а останалите шест полета съдържат данни за маршрути и комбинация от тях може да се повтаря до 25 пъти в един RIP-2 пакет. За пренасяне на информацията от по-големи маршутни таблици се използват няколко RIP-2 пакета. Полето Command указва дали пакетът съдържа заявка или отговор. Командата “Заявка” изисква отговарящата система да изпрати цялата или част от маршрутната си таблица. Командата “Отговор” представлява отговор на получена команда “Заявка” или периодично съобщение за обновяване на маршрутите, в което се включва цялата маршрутна таблица. Полето Version указва версията на протокола, за RIP-2 тази стойност е 2. Полето Routing domain не се използва. Полето Address family е идентификатор на адресна фамилия. Въвежда се идентификация на група от маршрутизатори. Всички маршутизатори в една група имат една и съща адресна фамилия. Полето Route tag указва дали информацията за даден маршрут произхожда от RIP или от друг вътрешен или външен маршутизиращ протокол. Полето IP address съдържа IP адреса на мрежа или хост, която представлява местоназначението на описвания маршрут. Полето Net mask е мрежовата маска, отнасяща се за горния IP адрес. Полето Next hop IP address съдържа IP адрес на най-близкия машрутизатор, към който ще се изпрати пакета. Полето Metric указва броя хопове до съответното местоназначение и може да има стойност от 1 (директно свързана мрежа) до 16 (недостъпен маршрут – безкрайност).

В първия от 25-те записа на RIP-2 пакета полето Address family може да има стойност 0xFFFF, която указва че следва идентификационна информация за подателя на пакета. В този случай полето Route tag определя използвания алгоритъм, а следващите 16 байта съдържат парола. Използването на този механизъм намалява максималния брой маршрути в един RIP-2 пакет на 24.

При промяна в топологията на мрежата се налага всички маршрутизатори да преизчислят своите вектори на разстоянията и да достигнат до непротиворечиво описание на новата топология. За увеличаване на скоростта на сходимост на RIP се използват различни методи, например разделяне на хоризонта. Тези методи намаляват вероятността за поява на цикли в маршрутите, но не могат да гарантират отсъствието им. Максималният брой хопове в RIP е 15. Всяко местоназначение, което е на разстояние над 15 хопа се приема за недостижимо. Това прави невъзможно прилагането на RIP в мрежи с диаметър над 15 хопа, но ограничава ситуацията “броене до безкрайност”, при която могат да се получат цикли в маршрутите.

Във версията RIP-2 са избегнати някои от недостатъците на RIP-1, но тя продължава да бъде приложима само в малки мрежи поради ниския максимален брой хопове и сравнително ниската и скорост на сходимост. Въпреки наследените от RIP-1 недостатъци и наличието на протоколи, в които те са избегнати, протоколът RIP-2 продължава да се използва, тъй като е лесен за реализация и конфигуриране и се нуждае от сравнително малко машинни и мрежови ресурси.

Internet е съвкупност от физически различни мрежи, които са обединени посредством общ протоколен стек, така че логически да се формира една обща мрежа. Най-лесният начин да се изгради такава мрежа е чрез свързване на две или повече мрежи чрез маршрутизатор (router). Маршрутизаторът представлява специализирано устройство, което дава възможност за свързване на различни типове физически мрежи. Основни функции на маршрутизатора са определяне за всеки получен пакет на най-добрия маршут до хоста-получател на пакета и препредаване на този пакет към следващия маршрутизатор по този маршрут. Последният маршрутизатор от пътя препредава пакета директно към хоста-получател. Информацията за най-добрите маршрути се съхраняват в маршрутни таблици. За определяне на най-добрия маршрут маршрутизаторите обменят помежду си информация, като за оценка използват различна метрика. Обикновено тази метрика включва следните величини: дължина на пътя, надеждност, закъснение на пакета при предаването от източника до получателя, пропусквателна способност на комуникационните линии, натоварване на маршрутизаторите, цена на комуникационните линии.

OSPF

Протоколът OSPF (open shortest path first) е разработен за IP мрежи и използва алгоритъма за маршрутизиране със следене състоянието на връзката (link state). OSPF маршрутизаторите поддържат топологични бази данни с информация за състоянието на връзките в мрежата. Тези бази данни периодично се обновяват посредством обмен на съобщения за състоянието на връзките и съдържат входните данни за алгоритъма на Дейкстра, който се изпълнява от всеки маршрутизатор. В резултат от неговото изпълнение, всеки OSPF маршрутизатор намира най-късите от своя гледна точка пътища до всички известни местоназначения в мрежата.

Важна особеност на OSPF е йерархичното разделяне на автономните системи на области (area). Връзките между различните области се осъществяват задължително през опорна мрежа (backbone), която е особена област с номер 0. Според принадлежността към OSPF областите различаваме 4 вида маршрутизатори: вътрешни маршрутизатори (internal routers), всичките интерфейси на които са свързани към мрежи от една OSPF област; областни гранични маршрутизатори (area border routers), интерфейсите на които са свързани към мрежи от две или повече OSPF области, една от които задължително е опорната мрежа. Тези маршрутизатори поддържат топологични бази данни с информация за състоянието на връзките в областите, към които са свързани, и изпълняват алгоритъма на Дейкстра поотделно за всяка от тях; опорни маршрутизатори (backbone routers), на които поне един от интерфейсите е свързан с опорната мрежа на област 0. Опорните маршрутизатори могат да бъдат областни гранични маршрутизатори, но това не е задължително; гранични за автономната система маршрутизатори (AS boundary routers), които са свързани към поне две различни автономни системи и изпълняват освен OSPF друг външен маршрутизиращ протокол (например BGP).

Опорните маршутизатори могат същевременно да бъдат вътрешни, ако всичките им интерфейси са свързани към опорната мрежа. В рамките на една област всички маршрутизатори имат една и съща топологична база данни. Нейното предназначение е да се изчислят най-късите пътища между дадения маршрутизатор и всички останали маршутизатори в областта. Йерархичните области в OSPF мрежите увеличават скоростта на сходимост на протокола и намаляват натоварването на необходимите за работата му мрежови и изчислителни ресурси. OSPF поддържа три вида различни връзки: връзка от тип “точка-точка” между два маршрутизатора; многоточкови мрежи с broadcast (например, повечето LAN); многоточкови мрежи без broadcast (например, повечето WAN с комутация на пакети).

OSPF работи чрез обмяна на информация между прилежащи маршрутизатори, което не е същото като съседни маршрутизатори. Това се прави, тъй като не е ефективно всеки два маршрутизатора да обменят данни. За целта се избира един титулярен маршрутизатор (designated router), който става прилежащ към всички останали маршрутизатори и всеки от тях синхронизира топологичната си база данни с неговата. Ако настъпи промяна в състоянието на връзките на даден маршрутизатор, той изпраща съобщение на титулярния маршрутизатор, а от своя страна той съобщава промяната на всички останали маршрутизатори в мрежата. При отпадане на титулярния маршрутизатор има заместник, който е в състояние веднага да поеме неговите функции.

Форматът на OSPF пакета е следния:

Полето Version number съдържа номера на версията на OSPF, която се използва. Полето Type определя типа на съобщението. Има няколко типа съобщения: “ехо” пакет (hello packet) – той се използва при откриване на съседни маршрутизатори, за проверяване на работоспособността на връзките и за избор на титулярен маршрутизатор; описание на база данни (database description) – разменят се при първоначално установяване на връзка между два маршрутизатора и служат за обмен на информация за състоянието на връзките в областта от техните топологични бази данни; пакет за запитване (link-state request) – чрез него даден маршрутизатор може да поиска информация от друг маршрутизатор за част от записите в неговата топологична база данни за състоянието на връзките; пакет за обновяване (link-state update) – тези пакети се изпращат периодично от всеки маршрутизатор и съдържат данни за неговото състояние и за цените, използвани в топологичната база данни; разпространяват се по метода на наводняването към всички останали маршрутизатори в границите на дадена област; пакет за потвърждение (link-state acknowledgement) – механизмът за надеждно доставяне на пакетите за обновяване изисква при получаването им да се изпращат потвърждения. Полето Packet length съдържа общата дължина на OSPF пакета, включват се заглавната част и данните. Полето Router ID съдържа уникален за автономната система идентификатор на маршрутизатора, изпратил пакета. Полето Area ID съдържа номера на областта, към която е свързан интерфейса на маршрутизатора-подател на пакета. Полето Check sum е контролна сума, която се изчислява върху цялото съдържание на OSPF пакета. Служи за проверка дали пакета е бил предаден правилно. Полето Authentication type указва вида на използвания механизъм за идентифициране на подателя на пакета. Проблемът е, че в мрежата може да проникнат фалшиви пакети, които дублират информацията за състояние на връзките на някой маршрутизатор. За това трябва да се установява автентичността на пакетите. Полето Authentication съдържа автентицираща информация.

BGP

В рамките на една автономна система се използват вътрешни протоколи за маршрутизиране, например RIP или OSPF. Тяхната цел е максимално бързо и ефективно да предават пакети от източника до получателя. За маршрутизиране между различни автономни системи се използват външни маршрутизиращи протоколи. Такъв протокол е BGP (border gateway protocol). В него се залага на политиката на маршрутизация – например, най-прекият път между две автономни системи не винаги е разумен. В политиката се включват икономически, административни и други фактори. Примери за политически ограничения: да не се позволява транзитен трафик през дадена автономна система; трафикът за Пентагона да не минава през Ирак; трафикът, започващ или свършващ в IBM да не минава през Microsoft. Политическите ограничения се конфигурират ръчно и не са част от BGP протокола.

От гледна точка на един BGP маршрутизатор, светът се състои от автономни системи, свързани с линии. Две автономни системи са свързани, ако има линия между гранични маршрутизатори във всяка от тях. От гледна точка на транзитния трафик BGP мрежите се делят на три вида: stub мрежи – те имат само една връзка в BGP графа и не могат да се използват за транзитен трафик; multiconnected мрежи – те могат да се използват за транзитен трафик, но самите те отказват да го правят; transit networks – например опорните мрежи, които пренасят транзитен трафик, обикновено срещу заплащане.

BGP протокола се базира на алгоритъма с вектор на разстоянието, но се различава доста от него. Вместо да се поддържа само цената към всяко местоназначение, всеки BGP маршрутизатор поддържа целия път към местоназначението. Освен това, вместо периодично да подава на съседите си цените до местоназначенията, всеки BGP маршрутизатор подава на съседите си целите пътища, които те използват. Това има смисъл, тъй като графът с възли автономните системи не е безмерно голям. Като пример да разгледаме следната мрежа от BGP маршрутизатори:

По-конкретно да разгледаме маршрутизатора F. Той получава от съседите си следните пътища до D – път BCD от B, път GCD от G, път IFGCD от I и път EFGCD от E. F преглежда тези пътища за да определи кой е най-добрия. Той премахва пътищата от I и E, тъй като минават през него. Изборът е между B и G. Всеки BGP маршрутизатор съдържа модул, който изследва пътищата до дадено местоназначение и ги оценява. Път, който нарушава политическо ограничение автоматично получава оценка безкрайност. Маршрутизаторът избира пътят с най-ниска оценка. Оценяващата функция не е част от BGP протокола. При BGP лесно се решава проблемът “броене до безкрайност”. Например, да предположим, че G пропадне или, че линията FG става недостъпна. Тогава F получава маршрути от останалите си три съседа. Тези маршрути са BCD, IFGCD и EFGCD. F бързо премахва последните два пътя, тъй като те са безсмислени – преминават през него и за това избира FBCD като нов маршрут. Другите алгоритми с вектор на разстоянието често правят погрешен избор, тъй като те не могат да съобщят кой от съседите има независим маршрут до местоназначението и кой няма.

Retrieved from "https://ilianko.com/index.php?title=Маршрутизация&oldid=3879"