This encourages the use of higher-quality wireless links. In this case, the route-generating protocol determines a loop-free subset of the relevant routing links that is, a spanning tree by which each routing node can reach the root or one of the roots. This tree-building process does not attempt to find best paths between pairs of non-root nodes, though such nodes can use the on-demand mode as necessary.
In the first, on-demand, mode, HWMP implements a change to classic AODV in that if a node receives a RouteRequest message and then later receives a second RouteRequest message with the same sequence number but a lower-cost route, then the second route replaces the first. In the proactive mode, the designated root node — typically the node with wired Internet access — periodically sends out specially marked RouteRequest messages. These are sent to the broadcast address, rather than to any specific destination, but otherwise propagate in the usual way.
Routing nodes receiving two copies from two different neighbors pick the one with the shortest path. Once this process stabilizes, each routing node knows the best path to the root or to a root ; the fact that each routing node chooses the best path from among all RouteRequest messages received ensures eventual route optimality.
Routing nodes that have traffic to send can at any time generate a RouteReply , which will immediately set up a reverse route from the root to the node in question. Finally, reversing each link to the root allows the root to send broadcast messages. These let other routing nodes know what the root is, but are not meant to result in the creation of routes to the root. As with DSDV, it eliminates the risk of routing loops, even ephemeral ones.
EIGRP is an actual protocol; we present here only the general algorithm. Our discussion follows [CH99]. Each router R keeps a list of neighbor routers N R , as with any distance-vector algorithm. Each R also maintains a data structure known somewhat misleadingly as its topology table. It contains, for each destination D and each N in N R , an indication of whether N has reported the ability to reach D and, if so, the reported cost c D,N.
Now suppose R receives a distance-vector report from neighbor N 1 that it can reach D with cost c D,N 1. We omit the argument that this process — and thus the network — must eventually converge. Link-state routing is an alternative to distance-vector. In distance-vector routing, each node knows a bare minimum of network topology: it knows nothing about links beyond those to its immediate neighbors. In the link-state approach, each node keeps a maximum amount of network information: a full map of all nodes and all links.
Routes are then computed locally from this map, using the shortest-path-first algorithm. The existence of this map allows, in theory, the calculation of different routes for different quality-of-service requirements. The map also allows calculation of a new route as soon as news of the failure of the existing route arrives; distance-vector protocols on the other hand must wait for news of a new route after an existing route fails.
Link-state protocols distribute network map information through a modified form of broadcast of the status of each individual link. This broadcast process is called reliable flooding. In general, broadcast mechanisms are not compatible with networks that have topological looping that is, redundant paths ; broadcast packets may circulate around the loop endlessly. Link-state protocols must be carefully designed to ensure that both every router sees every LSP, and also that no LSPs circulate repeatedly.
It is possible for ephemeral routing loops to exist; for example, if one router has received a LSP but another has not, they may have an inconsistent view of the network and thus route to one another. However, as soon as the LSP has reached all routers involved, the loop should vanish. The link-state flooding algorithm avoids the usual problems of broadcast in the presence of loops by having each node keep a database of all LSP messages.
The originator of each LSP includes its identity, information about the link that has changed status, and also a sequence number. Other routers need only keep in their databases the LSP packet with the largest sequence number; older LSPs can be discarded. When a router receives a LSP, it first checks its database to see if that LSP is old, or is current but has been received before; in these cases, no further action is taken.
If, however, an LSP arrives with a sequence number not seen before, then in typical broadcast fashion the LSP is retransmitted over all links except the arrival interface.
Suppose the A—E link status changes. It is important that LSP sequence numbers not wrap around. OSPF uses lollipop sequence-numbering here: sequence numbers begin at -2 31 and increment to 2 31 At this point they wrap around back to 0.
Thus, as long as a sequence number is less than zero, it is guaranteed unique; at the same time, routing will not cease if more than 2 31 updates are needed. Other link-state implementations use bit sequence numbers. Actual link-state implementations often give link-state records a maximum lifetime; entries must be periodically renewed.
The next step is to compute routes from the network map, using the shortest-path-first SPF algorithm. This algorithm computes shortest paths from a given node, A in the example here, to all other nodes. Below is our example network; we are interested in the shortest paths from A to B, C and D. The algorithm builds the set R of all shortest-path routes iteratively. Initially, R contains only the 0-length route to the start node; one new destination and route is added to R at each stage of the iteration.
At each stage we have a current node, representing the node most recently added to R. The initial current node is our starting node, in this case, A. We will also maintain a set T , for tentative, of routes to other destinations.
This is also initialized to empty. At each stage, we find all nodes which are immediate neighbors of the current node and which do not already have routes in the set R.
For each such node N, we calculate the cost of the route from the start node to N that goes through the current node.
We see if this is our first route to N, or if the route improves on any route to N already in T ; if so, we add or update the route in T accordingly.
Doing this, the routes will be discovered in order of increasing or nondecreasing cost. At the end of this process, we choose the shortest path in T , and move the route and destination node to R. The destination node of this shortest path becomes the next current node. Ties can be resolved arbitrarily, but note that, as with distance-vector routing, we must choose the minimum or else the accurate-costs property will fail.
No path through C or D can possibly have lower cost. The lowest-cost route in T is that to C, so we move this node and route to R and set C to be current. This is not generally the case; here is a similar example but with different lengths in which current jumps from B to D:. At that point this route is added to R and the algorithm is completed. A link-state source node S computes the entire path to a destination D in fact it computes the path to every destination.
But as far as the actual path that a packet sent by S will take to D, S has direct control only as far as the first hop N. While the accurate-cost rule we considered in distance-vector routing will still hold, the actual path taken by the packet may differ from the path computed at the source, in the presence of alternative paths of the same length.
Link-state routing allows calculation of routes on demand results are then cached , or larger-scale calculation. Link-state also allows routes calculated with quality-of-service taken into account, via straightforward extension of the algorithm above.
Because the starting node is fixed, the shortest-path-first algorithm can be classified as a single-source approach. If the goal is to compute the shortest paths between all pairs of nodes in a network, the Floyd-Warshall algorithm is an alternative, with slightly better performance in networks with large numbers of links.
There is sometimes a desire to route on packet attributes other than the destination, or the destination and QoS bits. For example, we might want to route packets based in part on the packet source, or on the TCP port number. This kind of routing is decidedly nonstandard, though it is often available, and often an important component of traffic engineering.
This option is often known as policy-based routing , because packets are routed according to attributes specified by local administrative policy. Policy-based routing is not used frequently, but one routing decision of this type can have far-reaching effects.
If an ISP wishes to route customer voice traffic differently from customer data traffic, for example, it need only apply policy-based routing to classify traffic at the point of entry, and send the voice traffic to its own router. After that, ordinary routers on the voice path and on the separate data path can continue the forwarding without using policy-based methods. Sometimes policy-based routing is used to mark packets for special processing; this might mean different routing further downstream or it might mean being sent along the same path as the other traffic but with preferential treatment.
For two packet-marking strategies, see On Linux systems policy-based routing is part of the Linux Advanced Routing facility, often grouped with some advanced queuing features known as Traffic Control; the combination is referred to as LARTC.
As a simple example of what can be done, suppose a site has two links L1 and L2 to the Internet, with L1 the default route to the Internet. Perhaps L1 is faster and L2 serves more as a backup; perhaps L2 has been added to increase outbound capacity. A site may wish to route some outbound traffic via L2 for any of the following reasons:. In the first two cases, routing might be based on the destination port numbers; in the third, it might be based on the source IP address.
Note that nothing can be done in the inbound direction unless L1 and L2 lead to the same ISP, and even there any special routing would be at the discretion of that ISP. The trick with LARTC is to be compatible with existing routing-update protocols; this would be a problem if the kernel forwarding table simply added columns for other packet attributes that neighboring non-LARTC routers knew nothing about.
One of these tables is the main table, and is the table that is updated by routing-update protocols interacting with neighbors. Before a packet is forwarded, administratively supplied rules are consulted to determine which table to apply; these rules are allowed to consult other packet attributes.
The collection of tables and rules is known as the routing policy database. Here is one such Linux rule, applying to traffic from host This is harder; Linux provides no support here for routing based on port numbers. The mark is known as the forwarding mark, or fwmark ; its value is 0 by default. The fwmark is not actually part of the packet; it is associated with the packet only while the latter remains within the kernel.
Equal-Cost MultiPath routing, or ECMP, is a technique for combining two or more routes to a destination into a single unit, so that traffic to that destination is distributed not necessarily equally among the routes. In channel bonding, two parallel Ethernet links are treated as a single unit. In many cases it is simpler and cheaper to bond two or three 1 Gbps Ethernet links than to upgrade everything to support 10 Gbps. Channel bonding applies, however, in limited circumstances; for example, the two channels must both be Ethernet, and must represent a single link.
In the absence of channel bonding, equal-cost does not necessarily mean equal-propagation-delay. Even for two short parallel links, queuing delays on one link may mean that packet delivery order is not preserved. As TCP usually interprets out-of-order packet delivery as evidence of packet loss For this reason, ECMP is usually configured to send all the packets of any one TCP connection over just one of the links as determined by a hash function ; some channel-bonding implementations do the same, in fact.
A consequence is that ECMP configured this way must see many parallel TCP connections in order to utilize all participating paths reasonably equally.
In special cases, however, it may be practical to configure ECMP to alternate between the paths on a per-packet basis, using round-robin transmission; this approach typically achieves much better load-balancing between the paths.
See At this point we have concluded the basics of IP routing, involving routing within large relatively homogeneous organizations such as multi-site corporations or Internet Service Providers. Every router involved must agree to run the same protocol, and must agree to a uniform assignment of link costs.
At the very largest scales, these requirements are impractical. The next chapter is devoted to this issue of very-large-scale IP routing, eg on the global Internet. Exercises are given fractional floating point numbers, to allow for interpolation of new exercises. Suppose the network is as follows, where distance-vector routing update is used. Now suppose the configuration of routers has the link weights shown below. Each router again initially has entries in its forwarding table only for its immediate neighbors.
For each entry that changes, give a brief explanation. For each entry that changes, give a brief explanation, in the style of At the start of Example 3 This meant that C had a valid route to D at the start.
Give a sequence of reports that leads to correct routing between D and E. In the following exercise, A-D are routers and the attached subnets N1-N6, which are the ultimate destinations, are shown explicitly. In the case of N1 through N4, the links are the subnets. Routers still exchange distance-vector reports with neighboring routers, as usual.
Distance-vector routing update is used. In the network below, A receives alternating reports about destination D from neighbors B and C. Suppose A uses a modified form of Rule 2 of Consider the network in All link costs are 1. Suppose the network of Distance-vector update is used; again, the D—A link breaks. The distance-vector forwarding tables for A and F are below. Give the network with the fewest links that is consistent with these tables. Hint: any destination reached at cost 1 is directly connected; if X reaches Y via Z at cost 2, then Z and Y must be directly connected.
Explain why the loop may be removed more quickly if A and B both use poison reverse with split horizon Suppose A and B send reports to each other advertising their routes to D, and immediately afterwards the C—D link breaks and C reports to A and B that D is unreachable. Explain why the network is now in the state described in part a. Suppose the distance-vector algorithm is run on a network and no links break so by the last paragraph of It was mentioned in Give a concrete scenario illustrating creation and then dissolution of such a loop.
Then B gets some news. There are also several other possible scenarios. Show the sets R and T , and the node current , after each step. From laptop to LAN there are now two routes. Which route will be preferred? How can you tell which way traffic is flowing?
How can you configure your OS to prefer one path or another? See also Navigation index next previous An Introduction to Computer Networks, desktop edition 2. Table of Contents 13 Routing-Update Algorithms A updates its own table according to the following three rules: New destination : D is a previously unknown destination. Because this is a cost increase from the neighbor N that A is currently using to reach D, A must incorporate the increase in its table.
There are several well-known other fixes: We now prove that, in distance-vector routing, the network will have accurate costs, provided each router selects what it believes to be the shortest path to the final destination, and the network is stable, meaning that further dissemination of any reports would not result in changes To see this, suppose the actual route taken by some packet from source to destination, as determined by application of the distributed distance-vector algorithm, is longer than the cost calculated by the source.
As an example, consider the following arrangement of routers: Suppose the A—E link status changes. We repeat this process until all nodes have routes in the set R. We now have routes in R to all nodes, and are done. Proof that SPF paths are shortest : suppose, by contradiction, that, for some node, a shorter path exists than the one generated by SPF.
Let A be the start node, and let U be the first node generated for which the SPF path is not shortest. Let T be the Tentative set and let R be the set of completed routes at the point when we choose U as current , and let d be the cost of the new route to U. At some strictly earlier stage in the algorithm, we must have added a route to node X, as the route to X is in R. This route must still be in T at the point we chose U as current , as there is no route to Y in R , but this means we should instead have chosen Y as current , contradicting the choice of U.
A site may wish to route some outbound traffic via L2 for any of the following reasons: the traffic may involve protocols deemed lower in priority eg email the traffic may be real-time traffic that can benefit from reduced competition on L2 the traffic may come from lower-priority senders; eg some customers within the site may be relegated to using L2 because they are paying less a few large-volume elephant flows may be offloaded from L1 to L2 In the first two cases, routing might be based on the destination port numbers; in the third, it might be based on the source IP address.
Suppose each router creates a report from its initial configuration and sends that to each of its neighbors. The exchanges, in other words, are all conducted simultaneously; each router first sends out its own report and then processes the reports arriving from its two neighbors.
Hint: for each router, this step will add one additional destination entry. This new destination entry can be determined without going through the table exchanges in detail.
Count the answer to part a as the first iteration. Give the initial tables for A through D, before any distance-vector exchanges. Give the tables after each router A-D exchanges with its immediate neighbors simultaneously and in parallel. What additional reports a pair should suffice will lead to the formation of the routing loop? What single additional report will eliminate the possibility of the routing loop?
Routing algorithms can be broadly categorized into two types, adaptive and nonadaptive routing algorithms. Adaptive routing algorithms, also known as dynamic routing algorithms, makes routing decisions dynamically depending on the network conditions. It constructs the routing table depending upon the network traffic and topology. They try to compute the optimized route depending upon the hop count, transit time and distance. So, it is also known as global routing algorithm.
Non-adaptive Routing algorithms, also known as static routing algorithms, construct a static routing table to determine the path through which packets are to be sent.
The static routing table is constructed based upon the routing information stored in the routers when the network is booted up. Flooding may be uncontrolled, controlled or selective flooding.
0コメント