W2 12 Routing Principles

Routing Principles

ALTTC/DX/AK/ROUTING_PRINCIPLES/1999

“DATA NETWORK” FOR JTOs PH-II : Routing Principles

Routing Principles Switching A typical electrical switch directs current to one of several wires of the electrical circuit. Once the connection is made, the switch appears as part of the wire - it (ideally) introduces no resistance, no attenuation, no delay. A networking switch is designed to behave in much the same way. Its primary feature is speed. Like an electrical switch, it is designed to appear much like a wire when relaying data signals. Networking Switches must implement a normal path selection algorithm; they just do it faster. Layer 2 switches bridge whereas layer 3 switches route. Normal Bridges and Routers will receive an entire packet, analyse its headers, make a forwarding decision, then transmit the packet. The packet is stored in the RAM (Random access Memory) while being processed. These RAM buffers can become bottlenecks in a busy network. Switches use special silicon chips than can forward packets directly from source to destination without passing through RAM buffers. Consider a typical Ethernet switch, which acts much like a standard IEEE 802.1d bridge. The difference is that as soon as an incoming packet's header has been received, a forwarding decision is immediately made, before the packet is completely received. If the destination Ethernet segment is idle, the packet begins transmission there immediately. As bits are received they are shunted through the switch fabric to the destination interface. On a 10 Mbps Ethernet, the net delay is perhaps one or two microseconds, as opposed to several milliseconds for a typical bridge. This is termed cut-through switching. With respect to Layer 3, the term switching implies, moving packets from one port to another port. This is different from Layer 2 switching functionality, which implies forwarding a packet from one port to another port based on the MAC address only.

Routing The primary function of a packet switching network is to receive packets from a source and deliver them to the destination. To achieve this, a path or route through the network has to be determined. More than one route may be possible. This requires a routing function/ algorithm to be implemented.

BRBRAITT Nov-2006

2

“DATA NETWORK” FOR JTOs PH-II : Routing Principles

The routing function must achieve the following requirements : • Correctness • Simplicity • Robustness • Stability • Fairness • Optimality • Efficiency Correctness and Simplicity are self explanatory. Robustness has to do with the routing of packets through alternate routes in the network in case of route failures or overloads. Stability is an important aspect of the routing algorithm. It implies that the routing algorithm must converge to equilibrium as quickly as possible, however some never converge, no matter how long they run. Fairness and optimality are competing requirements. A trade-off exists between the two. Some performance criteria may give a higher priority to transportation of packets between adjacent/ nearby stations in comparison to those between distant stations. This results in higher throughput but is not fair to the stations which have to communicate with distant stations. Efficiency of a routing technique/ algorithm gets decided by the quantum of overhead processing required. Of course these have to be kept to a minimum. Thus, Routing is essentially a method of path selection and is an overhead activity. Routing Table 100.3.4.0 100.1.1.5

ARP Table 7

100.1.1.5 3CE9... 100.1.1.9 3C76... 100.1.1.13 3C87...

100.3.6.0 100.1.1.9 100.3.7.0 100.1.1.13

6 5 4 3

BRBRAITT Nov-2006

Network

2

Data Link

1

Physical

3

“DATA NETWORK” FOR JTOs PH-II : Routing Principles

Fig.1

Routing & Switching

Routing & Network Layer Addresses Routers relay a packet from one data link to another. To relay a packet, a router employs two basic functions :

 a path determination function and  a switching function. Figure 2 illustrates how routers use the addressing for routing and switching functions. When a packet destined for network 100.1.0.0 arrives at Router 1, the router knows that the packet should be sent out on port S0.

ROUTER R1

100.2.0.0

S1

S2 S0

100.1.0.0 100.3.0.0 S0

Fig. 2

ROUTER PO RT

100.1.0.0 100.2.0.0 100.3.0.0 100.4.0.0

S0 S1 S2 S2

ROUTER R2

S1

100.4.0.0

DESTINATION NETW ORK ADDRESS

Use of Network Layer Addresses in Routing

Although the path determination function sometimes is capable of calculating the complete path from the router to the destination, a router is responsible only for passing the packet to the best network along the path. This best path is represented as a direction to a destination network. For example, in figure 2, if a packet that is destined for network 100.4.0.0 arrives at Router 1, the router knows that the best direction to send the packet out is interface S2. Router 2 is the next hop, or router, along the path. The router uses the network portion of the address to make these path selections. The switching function enables a router to accept a packet on one interface and forward it on a second interface. The path determination function enables the router to select the most appropriate interface for forwarding a packet. BRBRAITT Nov-2006

4

“DATA NETWORK” FOR JTOs PH-II : Routing Principles

Routing assumes that addresses have been assigned to network elements to facilitate data delivery. In particular, routing assumes that addresses convey at least partial information about where a host is located. This permits routers to forward packets without having to rely either on broadcasting or a complete listing of all possible destinations. At the IP level, routing is used almost exclusively, primarily because the Internet was designed to construct large networks in which heavy broadcasting or huge routing tables are not feasible. Three general prerequisites must be met to perform routing : •

Design : A plan must exist by which addresses are assigned. Typically, addresses are broken into fields corresponding to levels in a physical hierarchy. At each level of the hierarchy, only the corresponding field in the address is used, permitting addresses to be handled in blocks. In IP, the most common designs are IP Address Classes, Sub-netting, and CIDR.

•

Implementation : The design plan must be implemented in switching nodes, which must be able to extract path information from the addresses. Since router programming is generally not under a designer's control, designs must be limited by the features provided by manufacturers. Subnetting's great appeal lies in its great flexibility, while using a fairly simple implementation model.

•

Enforcement : The plan must be enforced in host addressing. A design is useless unless addresses are assigned in accordance with it. Addressing authority must be centralised.

In the Internet environment, routing is almost always used at the IP level, and bridging almost always used at the Data Link Layer. For new network installations, the best approach is to plan for routing even if it's not used at first. This requires some advanced planning to design an addressing scheme that will work. However, the overhead is all human hardware won't know the difference between organised and haphazard addressing schemes. Network should be planned for the ability to put routers in strategic locations, even if those locations will initially use bridges or just signal boosters (such as Ethernet hubs and repeaters). In this manner, routers can be easily added later.

Routed Protocol A routed protocol is a protocol that contains sufficient network-layer addressing information for user traffic to be directed from one network to another network. Routed protocols define the format and use of the fields within a packet. Packets that use a routed protocol are conveyed from one end system to another end system through an internetwork. The internet protocol IP and Novell’s IPX are examples of routed protocols. BRBRAITT Nov-2006

5

“DATA NETWORK” FOR JTOs PH-II : Routing Principles

Routing Protocol A routing protocol provides mechanisms for sharing routing information. Routing protocol messages move between the routers. A routing protocol allows the routers to communicate with other routers to update and maintain routing tables. Routing protocol messages do not carry end-user traffic from network to network. A routing protocol uses the routed protocol to pass information between routers.

Types of Routing : Static, Default, Dynamic Static routing : refers to routes to destinations being setup manually in the router. Network reachability in this case is not dependent on the existence and state of the network itself. Whether a destination is up or down, the static routes would remain in the routing table, and traffic would still be sent towards that destination. Static routing generally is not sufficient for large or complex networks because of the time required to define and maintain static route table entries. Default routing : refers to a “last resort” outlet – traffic to destinations that are unknown to the local router are sent to the default outlet router. Default routing is the easiest form of routing for a domain connected to a single exit point. A default route is a path on which a router should forward a packet if it does not have specific knowledge about the packet’s destination. Figure 3 below illustrates the concept of Static and default Routing.

Static Routing

10.1/16

Traffic to 10.1

R1

WA N

Fig.3

R2

Send all traffic to R1 Default Routing

Static and Default Routing

Dynamic routing : refers to routes being learnt via an internal or external routing protocol. Network reachability is dependent on the existence and state of the network. If a destination is down, the route would disappear from the routing table, and traffic will not be sent toward the destination. BRBRAITT Nov-2006

6

“DATA NETWORK” FOR JTOs PH-II : Routing Principles

Dynamic routing is used to enable routers to build their routing tables automatically and make the appropriate forwarding decisions. This concept is illustrated in Figure 4 below. R2 Routing update : I can reach 100.1

X R2

R3

R1 100.1

Routing update : I can reach 100.1

Fig. 4

Dynamic Routing

Static and default routing are not our enemy. The most stable (but not so flexible) configurations are the ones based on static routing. Many people feel that they are not technologically up-to-date because they are not running dynamic routing. Trying to force dynamic routing on situations that do not really need it is just a waste of bandwidth, effort, and money. As networks keep on growing in size, the routing tables also grow proportionately. Considerable amount of router memory is consumed by these ever increasing tables. In addition, the processor time is eaten up in scanning these tables and bandwith is consumed in sending status reports about the updated routing tables. At a certain stage, the network size becomes so large that it becomes impossible to have every router keep an entry of every other router in the network. Ultimately, the routing has to be done hierarchically, similar to a telephone network.

BRBRAITT Nov-2006

7

“DATA NETWORK” FOR JTOs PH-II : Routing Principles

Routing Algorithms Routing algorithms and protocols form the core of the hacker's Internet, because it is here that all the decisions get made. Network engineers assign costs to network paths, and routing protocols select the least-cost path to the destination. Routing protocols bear a resemblance to capitalist market economics. In both systems, there is a large group of "nodes", the decisions of each being driven by a cost-minimisation algorithm. The end result is a reasonably efficient distribution of "resources". Furthermore, cost determination is done in similar ways. A router, like an import/export firm, will compute its cost, add on profit for its part in the transaction, and pass this cost along to customers. Both systems use this method to achieve reasonable efficiency. Routing is the main process used by Internet hosts to deliver packets. Internet uses a hop-by-hop routing model, which means that each host or router that handles a packet examines the Destination Address in the IP header, computes the next hop that will bring the packet one step closer to its destination, and delivers the packet to the next hop, where the process is repeated. To make this work, two things are needed : • •

First, routing tables match the destination addresses with next hops. Second, routing protocols determine the contents of these tables.

Routing algorithms can be grouped into two major classes :

 Non-Adaptive or Static  Adaptive or Dynamic Non-Adaptive algorithms do not base their routing decisions on measurements or estimates of the current traffic and topology. Instead, the choice of the route to use to get from I to J (for all I to J) is computed in advance, off-line, and downloaded to the routers when the network is booted. This procedure is also called as Static Routing. Adaptive algorithms change their routing decisions to take into account changes in the topology, and sometimes the traffic as well. Adaptive algorithms will be classified depending on : •

where it gets the information from - whether locally, from adjacent Routers, or from all Routers

•

When does the algorithm decide to change the routes - whether every ∆T sec, when the load changes, or when the topology changes, and

BRBRAITT Nov-2006

8

“DATA NETWORK” FOR JTOs PH-II : Routing Principles

•

what metric (parameter) is used for optimisation i.e. either distance, number of hops, or estimated transit time.

Dynamic Routing Operations The success of dynamic routing depends on two basic router functions : • •

Maintenance of a routing table Timely distribution of knowledge – in the form of routing updates – to other routers

Dynamic routing relies on a routing protocol to disseminate knowledge. A routing protocol defines the set of rules used by a router when it communicates with neighbouring routers. Typically, a routing protocol describes: • • • •

How updates are conveyed What knowledge is conveyed When to convey this knowledge How to locate recipients of the updates

Convergence Information about the network topology needs to be very accurate and also consistent from Router to Router. This consistency and accuracy is referred to as Convergence. The network is considered to have converged when all the Routers contain consistent information.

Representing Distance with Metrics When a routing algorithm updates the routing table, its primary goal is to determine the best information to include in the table. Each routing algorithm will interpret “best” in its own way. The algorithm generates a number – called the metric- for each path through the network. Typically, the smaller the metric, the better is the path. Metrics can be calculated based on a single characteristic of the path or by combining several key characteristics such as : 1) Hop Count : Refers to the number of routers a packet must go through, to reach a destination. The lower the hop count, the better is the path. Path length is used to indicate the sum of the hops to a destination. 2) Cost : Path cost is the sum of cost associated with each link to a destination. Costs are assigned (automatically or manually) to the process of crossing a network. Slower networks typically have a higher cost than BRBRAITT Nov-2006

9

“DATA NETWORK” FOR JTOs PH-II : Routing Principles

faster networks. The lowest ‘cost” route is the one believed to be the fastest route available. 3) Bandwidth : The rating of a link’s throughput. Routing through links with greater bandwidth does not always provide the best routes. For example, if a high-speed link is busy, sending a packet through a slower link might be faster. 4) Delay : Depends on many factors, including the bandwidth of network links, the length of queues at each router in the path, network congestion on links, and the physical distance to be travelled. A conglomeration of variables that change with internetwork conditions, delay is common and useful metric. 5) Load : Dynamic factor that can be based on a variety of measures, including CPU and packet processed per second. Monitoring these parameters on a continual basis can be resource intensive. Modern computer networks generally use dynamic routing algorithms rather than the static ones. Two dynamic algorithms in particular,

 distance vector routing and  link state routing are the most popular.

Distance Vector Routing Distance Vector Routing algorithms require that each router maintain a table (a vector) indicating the best known distance to each destination and which line/ port to use to reach there. These tables are constantly updated by exchanging information with the neighbours. The algorithms periodically pass copies of a routing table from router to router. Updates between routers also communicate topology changes immediately when they occur. The distance vector routing is also known by other names, viz; the distributed Bellman-Ford routing algorithm and the Ford-Fulkerson algorithm, after the researchers who developed it (Bellman, 1957; and Ford and Fulkerson, 1962). It was the original ARPANET routing algorithm and was also used in the Internet under the name RIP and in early versions of DECnet and Novell’s IPX. In distance vector routing, each router maintains a routing table containing one entry for, each router in the subnet. This entry consists of two parts : 1) the preferred outgoing line/ port to use for that destination, and

BRBRAITT Nov-2006

10

“DATA NETWORK” FOR JTOs PH-II : Routing Principles

2) an estimate of the time or distance to that destination. The metric used might be number of hops, time delay in milliseconds, total number of packet queued along the path, or something similar. The router is assumed to know the “distance” to each of its neighbours. If the metric is hops, the distance is just one hop. If the metric is queue length, the router simply examines each queue. If the metric is delay, the router can measure it directly with special ECHO packets that the receiver just time-stamps and sends them back as fast as it can.

B

A

C

D

D

C

Routing Table

Routing Table

B Routing Table

A Routing Table

Fig. 5 Distance Vector Routing Updates

Each router receives a routing table from other routers connected to the same network, as shown in Figure 5. For example, in the figure, router B receives information from router A, its neighbouring router across the WAN link. Router B adds a distance vector number (such as the number of hops) thereby increasing the distance vector, and then passes the routing table to

BRBRAITT Nov-2006

11

“DATA NETWORK” FOR JTOs PH-II : Routing Principles

its other neighbouring router C. This Step-by-step process occurs in all directions between directly connected neighbour routers. In this way, the algorithm accumulates network distances sothat it can maintain a database of network topology information. Distance vector algorithms do not allow a router to know the exact topology of an internetwork. Distance vector information is similar to the information found on signs at a highway intersection. A sign points toward a road leading away from the intersection and indicates the distance to the destination. Further down the highway, another sine also points towards the destination, but now the distance to the destination is shorter. As long as each successive point on the path shows that the distance to the destination is successively shorter, we know that the traffic is following the best path. Examples of distance vector routing protocols are IPX RIP and IP RIP.

Distance Vector Network Discovery Each router using distance vector routing begins by identifying its own neighbours. In Figure 6 the interface to each directly connected network is shown in the routing tables as having a distance of 0. D

B

S2

S1

Routing Table

C

100.2.0.0 S2

100.3.0.0 100.1.0.0 S1

Routing Table

S0

S1

Routing Table

100.1.0.0

S1

0

100.2.0.0

S2

0

100.3.0.0

S0

0

100.2.0.0

S2

0

100.3.0.0

S1

0

100.4.0.0

S1

0

100.3.0.0

S2

1

100.4.0.0

S1

1

100.2.0.0

S0

1

100.4.0.0

S2

2

100.1.0.0

S2

1

100.1.0.0

S0

2

Fig. 6 Distance Vector Route Discovery

As the distance vector network discovery process proceeds, routers discover the best path to destination networks based on accumulated metrics from each neighbour.

BRBRAITT Nov-2006

12

“DATA NETWORK” FOR JTOs PH-II : Routing Principles

For example, router A learns about other networks based on information it receives from router B. Each of the other network entries learnt from router B are placed in router A’s routing table.

Link State Routing Link State Routing replaced the Distance Vector Routing (used in the ARPANET) in 1979. Two problems caused the demise of Distance Vector algorithm. First, since the delay metric was queue length, it did not take line bandwidth into account when choosing the routes. It would have been possible to change the delay metric to take into account the line bandwidth, but a second problem existed, namely, the algorithm often took too long to coverage, even with enhancements like split horizon. For these reasons, it was replaced by an entirely new algorithm now called link state routing. Variants of link state routing are now widely used. The 5 step concept is stated below : 1. 2. 3. 4. 5.

Discover the neighbors and learn their network addresses Measure the delay or cost to each of the neighbors Construct a packet telling all that has just been learnt Send this packet to all other routers Compute the shortest path to every other router

When a router is booted, its first task is to learn who its neighbours are. This task is accomplished by sending a special HELLO packet on each point-to-point line. The router on the other end is expected to send back a reply telling who it is. Link-state routing algorithms - also known as shortest path first (SPF) algorithm maintain a complex database of topology information. Whereas the distance vector algorithm has entries for distant networks and a metric value to reach those networks but no knowledge of distant routers, a link state routing algorithm maintains full knowledge of distant routers and how they interconnect. Examples of link-state routing protocols are : NLSP, OSPF, and IS-IS. Link state routing is widely used in actual networks. The OSPF protocol, which is increasingly being used in the Internet, uses a link state algorithm.

Link-State Network Discovery Link-state network discovery mechanisms are used to create a common picture of the entire internetwork. All routers employing the link state routing algorithm share this common view of the internetwork. In Figure 7, four networks (W,X,Y, and Z) are connected by three link-state routers (A,B, and C).

BRBRAITT Nov-2006

13

“DATA NETWORK” FOR JTOs PH-II : Routing Principles

A

B

C

X

W

Y

S1

S0

S0 S1

Routing Table

Z S1

Routing Table

Routing Table

W

S0

0

X

S1

0

Y

S1

0

X

S1

0

Y

S0

0

Z

S0

0

Fig. 7 Link State Routing

Link-State Network discovery proceeds as follows : •

Routers learn about their neighbours; that is, other routers that are on directly connected networks with them. This process is often referred to as neighbour notification. In link-state routing, each router connected to a network keeps track of its neighbours.

•

Routers transmit LSPs (Link State Packets) on the network. The LSPs contain information about networks to which the routers are connected.

•

Then, routers constructed their topological databases consisting of all the LSPs from the internetwork.

•

The SPF algorithm computes network reachability, determining the shortest path from a router to each other network in the link-state protocol internetwork. The router uses the Dijkstra algorithm to construct this logical topology of shortest paths as an SPF tree with itself as root. The SPF tree expresses paths from the router to all destinations.

•

The router computes its best paths and the ports to these destination networks and enters them in the routing table.

After the routers dynamically discover the details of their internetwork, they can use the routing table for switching packet traffic. Comparison of Distance Vector Routing & Link-State Routing You can compare distance-vector routing to link-state routing in several key areas, as listed in Table 1.

BRBRAITT Nov-2006

14

“DATA NETWORK” FOR JTOs PH-II : Routing Principles

Table 1 Distance Vector Network Topology is neighbours perspective

viewed

Link State from Entire Network Topology is common to all Routers

Metrics are incremented as the update Shortest Path to other Routers is crosses one Router calculated Periodic & Frequent Updates results in Updates are triggered by slow convergence Results in faster convergence

events.

Copies of Routing Tables are passed Link State Packets are passed to other to neighbouring Routers Routers

Interior Routing

Interior routing occurs within an autonomous system. Most common interior routing protocols are RIP and OSPF. The basic routable element is the IP network or subnetwork, or CIDR prefix for newer protocols.

Exterior Routing

Exterior routing occurs between autonomous systems, and is of concern to service providers and other large or complex networks. The basic routable element is the Autonomous System, a collection of CIDR prefixes identified by an Autonomous System number. While there may be many different interior routing schemes, a single exterior routing system manages the global Internet, based primarily on the BGP-4 (Border Gateway Protocol Version 4) exterior routing protocol. IGP

Autonomous Systems Autonomous Systems BGP

BGP

IGP

IGP BGP

Fig. 8 General illustration of Protocol relationships

BRBRAITT Nov-2006

15

“DATA NETWORK” FOR JTOs PH-II : Routing Principles

Distance Vector Protocols : 1) D-V Protocols such as RIP Version 1 were mainly designed for small network topologies. 2) The term Distance Vector derives from the fact that the protocol includes in its routing updates a vector of distances (hop counts). 3) Low speed links are treated equally or sometimes preferred over a highspeed link, depending on the calculated hop count in reaching a destination. This may lead to inefficient routing behaviour. 4) Count to infinity restriction : D-V Protocols have a finite limit of hops (15) after which a route is considered unreachable. This would restrict the propagation of routing updates and would cause problems for large networks. 5) The reliance on hop counts is one deficiency of distance vector protocols; another deficiency is the way that the routing information gets updated. 6) D-V Protocols work on the concept that routers exchange all the network numbers they can reach via periodic broadcasts of the entire routing table. In large networks, the routing table exchanged between routers becomes very hard to maintain, leading to slower convergence. 7) D-V Protocols are considered to be Flat. They present a lack of hierarchy, which translates into a lack of aggregation. This flat nature has made D-V Protocols incapable of scaling to larger and more efficient enterprise networks.

Link State Protocols : 1) Link State Protocols work on the basis that routers exchange information elements, called link states, which carry information about links and nodes. 2) This means that routers running link state protocols do not exchange routing tables. Each router inside a domain will have enough bits and pieces of the big puzzle that it can run a shortest path algorithm and build its own routing table.

BRBRAITT Nov-2006

16