IP Routing Principles
MADURAI NIB
Router
Application Transport Network Data Link Physical HD IP TCP Data TR Router Application Transport Network Data Link Physical
MADURAI NIB 2
IP Routing..
[Link] [Link]
Ethernet
FDDI
Serial
TOKEN RING
DATA
DATA
MADURAI NIB 3
IP Routing
Data link layer provide communications across a physical path Certain information about data link identifiers and encapsulation must be aquired and stored in a database such as ARP cache Network layer provide communications across logical or virtual path Information about network layer is stored in routing table or forwarding table
MADURAI NIB 4
IP Routing.
When a framed packet arrives at one of a routers interfaces: At layer-2 (Data Link Layer)
The frame will be accepted by a router only if Data link identifier in destination address contains Identification of the routers interface or a broadcast identifier FCS field is checked for error detection, if any
If FCS is bad, frame is discarded If FCS is good, frame header and trailer are stripped off and IP Datagram is handed over to layer-3
MADURAI NIB 5
IP Routing..
At Layer-3 (Network layer) the destination IP address is examined If the destination IP address is:
IP address of a routers interface or an all host broadcast address
The protocol field of the packet is examined and the enclosed data is sent to the appropriate internal process
IP address of a host on a directly connected network
The packet will be delivered after encapsulation
MADURAI NIB 6
IP Routing
IP address of a host on a network not directly connected to the router
The packet will be routed after doing a route table lookup
Each route entry must contain two items
The address of the network the router can reach A pointer to the destination
the pointer will indicate the address of another router on a directly connected network or the address of another router which is one hop closer to the destination, known as next hop router
MADURAI NIB 7
IP Routing.
Direct Routing
If the datagram is routed locally i.e. if the destination is on the same subnet as the originator.
Indirect Routing
If the use of a forwarding device such as router is invoked i.e. if the destination is remote
MADURAI NIB 8
IP Routing..
[Link]
[Link]
E0 E1 [Link]
[Link]
[Link]
[Link]
[Link]
[Link]
Direct Routing
Indirect Routing
MADURAI NIB 9
IP Routing
[Link].2F.C4 [Link] [Link].2F.C1 [Link] E0 E1 [Link] [Link].2F.C6
[Link] [Link].2F.C2
[Link]
[Link] [Link].2F.C5
[Link] [Link].2F.C7
[Link]
[Link].2F.C3
[Link].2F.C4 [Link].2F.C1 [Link]
[Link].2F.C8
[Link] DATA CRC
Routing Table [Link]/24 [Link] [Link]/24 [Link]
[Link].2F.C8 [Link].2F.C5 [Link] [Link] DATA CRC
MADURAI NIB 10
Route Table Updation
Route table aquires information in two ways:
Manually
Static route entries
Automatically
Dynamic routing protocols
MADURAI NIB 11
Static Routing
Routes to destinations are set up manually Network reachability is not dependent on the existence and state of the network Route may be up or down but static routes will remain in the routing tables and traffic would still be sent towards the route Not suitable for large networks Also known as Non-adaptive routing
MADURAI NIB 12
Dynamic Routing
Routes are learnt via an internal or external routing protocols Routing Protocol is a language a router speaks with other routers to share information about the reachability and status of the network Routing Protocol messages do not carry end user traffic from network to network Routing Protocol uses the routed protocol to pass information between routers RIP & OSPF are routing protocols
MADURAI NIB 13
Dynamic Routing
Routing decisions change to reflect the changes in topology Network reachability is dependent on the existence and state of the network If a router is down, its entry will be deleted from the routing table and traffic to that will not be forwarded Also known as Adaptive routing
MADURAI NIB 14
Routed Protocol
Contains sufficient network layer addressing information for user traffic to be directed from one network to another network 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 inter network Internet Protocol is a routed protocol
MADURAI NIB 15
Router Table Lookup
The router will match the most specific address it can in the descending order of specificity as below:
A A A A A A host address subnet group of subnets major network number group of major network numbers default route
MADURAI NIB 16
Default Route..
When a router receives a packet and its table does not contain the network address indicated in the packet, it is forwarded to default router The default router, too, may have a default router Easiest form of routing for a domain connected to a single exit point Default router is indicated as [Link] with no subnet mask
MADURAI NIB 17
Default Route
If there is no route or default route at any stage, the router will send a control message (through ICMP) to the originating station Refers to last resort outlet
MADURAI NIB 18
Static and Default Routes
[Link] WAN R1 R2
Traffic to network [Link] (Static Route). All outgoing traffic from network [Link] (Default Route).
MADURAI NIB 19
Dynamic Routing Protocols
All dynamic routing protocols are built around an algorithm, which must specify:
A procedure for passing network reachability information about networks to other routers A procedure for receiving reachability information from other routers A procedure for determining optimal routes based on the reachability information it has and for recording this information in a route table A procedure for reacting to and advertising topology changes in an network
MADURAI NIB 20
Convergence
[Link]
.2
[Link] .1 .2
[Link]
.1 .2
[Link] .1
Routing Table-A
NW [Link] [Link] VIA HOP ---------0 ---------0 1 2
Routing Table-B
NW [Link] [Link] VIA HOP ---------0 ---------0 1 1
Routing Table-C
NW [Link] [Link] VIA HOP ---------0 ---------0 1 2
[Link] [Link] [Link] [Link]
[Link] [Link] [Link] [Link]
[Link] [Link] [Link] [Link]
All the routing tables contains information about all.
MADURAI NIB 21
Convergence
The process of bringing all route tables to a state of consistency is called convergence. The time it takes to share information across an internetwork and for all routers to calculate best paths is convergence time.
MADURAI NIB 22
Path Determination
Routing Table of Router-A Network Next Hop Router
[Link] [Link] [Link] [Link] [Link] [Link] [Link]
Direct Direct Direct B,C B,C B,C B,C
[Link]
B [Link]
C
[Link]
[Link] [Link]
[Link] [Link]
Networks192.168.4.0 to [Link] can be reached via either router B or C, which path is preferable? Metrics are needed to rank the alternatives.
MADURAI NIB 23
Metrics
A metric is a variable assigned to routes as a means of ranking them. Different routing protocols use different, and sometimes multiple metrics.
RIP defines the best route as one with minimum number of hops. IGRP defines the best route on a combination of lowest bandwidth along the route and the total delay of the route.
MADURAI NIB 24
Metrics
Hop Count Bandwidth Load Delay Reliability
MADURAI NIB 25
Metrics
Hop Count
A hop count metric simply count router hops. From router-A it is 1 hop to network [Link] if packets are sent out interface [Link] and 2 hops if sent out [Link]
[Link]
[Link] B
[Link]
[Link] [Link]
[Link] [Link]
MADURAI NIB 26
Metrics
Bandwidth
A bandwidth metric would choose a higher bandwidth over a lower bandwidth. A packet from router A to C will follow path A-B-C.
[Link] A B [Link] [Link] A-C: 64kbps A-B: 2mbps B-C: 2mbps
[Link] [Link]
[Link] [Link]
MADURAI NIB 27
Metrics
Speed
>= 100Mbps Ethernet/802.3 E1(2.048Mbps)
Cost
1 10 48
64Kbps
1562
Metric=108/Interface Speed in bits per sec. e.g. 100000000/2048000=48.828125
MADURAI NIB 28
Metrics
Load
The metric reflects the amount of traffic utilising the links along the path. The best path is the one with the lowest load. Unlike hop count and bandwidth, the load on a route changes and therefore the metric will change and is called route flapping. Route flaps have adverse effects on routers CPU and the overall stability of the network.
MADURAI NIB 29
Metrics
Delay
Delay is the measure of time a packet takes to traverse a route A protocol using delay as a metric would choose the path with the least delay as the best path
Reliability
Reliability measures the likelihood that the link will fail in some way The path with highest reliability would be selected as the best
MADURAI NIB 30
Metrics
Cost
The term cost is often used as a generic term when speaking of router choices
RIP chooses the lowest-cost path based on the hop count.
Another generic term is Shortest
RIP chooses the shortest path based on the hop count.
MADURAI NIB 31
Dynamic Routing Protocols
Distance Vector Routing Protocols
Distance vector algorithms are based on the work done of [Link], [Link] and [Link] Often known as Bellman-ford or Ford-fulkerson algorithms
Link State Advertisement Protocols
Built around a well known algorithm from graph theory, [Link] shortest path algorithm Called as Shortest path first or Distributive database protocols
MADURAI NIB 32
Distance Vector Routing Protocols
MADURAI NIB 33
Distance Vector Routing Protocols
Routes are advertised <Distance, Direction> as vectors of
Distance is defined in terms of a metric Direction is defined in terms of next hop router
Each router learns routes from its neighboring routers perspective and then advertises the routes from its own perspective Sometimes referred to as Routing By Rumor
MADURAI NIB 34
Distance Vector Routing Protocols
Routing Information Protocol (RIP) for IP. Xerox Networking Systems XNS RIP. Novells IPX RIP. Ciscos Internet Gateway Routing Protocol (IGRP). DECs DNA Phase IV. Apple Talks Routing Maintenance Protocol (RTMP).
MADURAI NIB 35
Routing Loops
Routing are loops
A condition in which a packet is continuously transmitted within a series of routers without ever reaching its destination.
Routing Loops
Routing loops may be caused by:
Incorrectly configured static routes Incorrectly configured route redistribution Slow convergence Incorrectly configured discard routes Routing loops can create the following issues: Excess use of bandwidth CPU resources may be strained Network convergence is degraded Routing updates may be lost or not processed in a timely manner
Routing Loops
Count to Infinity
This is a routing loop whereby packets bounce infinitely around a network
Routing Loops
Setting a maximum Distance Vector routing protocols set a specified metric value to indicate infinity
Once a router counts to infinity it marks the route as unreachable
Routing Loops
Preventing loops with holddown timers
Holddown timers allow a router to not accept any changes to a route for a specified period of time Point of using holddown timers
Allows routing updates to propagate through network with the most current information
Routing Loops
The Split Horizon Rule is used to prevent routing loops Split Horizon rule:
A router should not advertise a network through the interface from which the update came
Routing Loops
Split with reverse horizon poison
The rule states that once a router learns of an unreachable route through an interface, advertise it as unreachable back through the same interface
Summary
D.V. routing protocols maintains routing tables by
RIP sending out periodic updates RIP using 4 different timers to ensure information is accurate and convergence is achieved in a timely manner EIGRP sending out triggered updates
D.V. routing protocols may be prone to routing loops
routing loops are a condition in which packets continuously traverse a network Mechanisms used to minimize routing loops include defining maximum hop count, holddown timers, split horizon, route poisoning and triggered updates
Summary
Routing Information Protocol (RIP)
A distance vector protocol that has 2 versions
RIPv1 - a classful routing protocol RIPv2 - a classless routing protocol
Enhanced Interior Gateway Routing Protocol (EIGRP)
A distance vector routing protocols that has some features of link state routing protocols A Cisco proprietary routing protocol
Link state Routing Protocols
Each router originates information about itself, its directly connected links and state of those links The information is passed around from router to router, each router making a copy of it, but never changing it Every router has identical information about the internetwork Each router will independently calculate its own best paths
MADURAI NIB 45
Link state Routing Protocols
Link State Routing protocols are built around well known algorithm from graph theory [Link] shortest path algorithm. Examples of LSR are:
Open Shortest Path First (OSPF) The ISOs Intermediate System to Intermediate System (IS-IS) for IP DECs DNA Phase V Novells Netware Link State Protocol (NLSP)
MADURAI NIB
46
Link-State Routing Protocols
Advantages Protocol
Routing protocol
of
Link-State
Routing
Use of LSP
Builds Router can Topologica independentl Convergenc l y determine e map the shortest path to every network. No No Slow
A periodic/ event driven routing updates
Distance vector Link State
Generally No
No
Yes
Yes
Fast
Generally Yes
Yes
Link-State Routing Protocols
Requirements for using a link state routing protocol Memory requirements Typically link state routing protocols use more memory Processing Requirements More CPU processing is required of link state routing protocols Bandwidth Requirements Initial startup of link state routing protocols can consume lots of
Link-State Routing Protocols
2 link state routing protocols used for routing IP -Open Shortest Path First (OSPF) -Intermediate System-Intermediate System (IS-IS)
Summary
Link State Routing protocols are also known as Shortest Path First protocols Summarizing the link state process -Routers 1ST learn of directly connected networks -Routers then say hello to neighbors -Routers then build link state packets -Routers then flood LSPs to all neighbors -Routers use LSP database to build a network topology map & calculate the best path to each destination
Link An interface on the router Link State Information about an interface such as -IP address -Subnet mask -Type of network -Cost associated with link -Neighboring routers on the link
Summary
Summary
Link State Packets After initial flooding, additional LSP are sent out when a change in topology occurs
Examples of link state routing protocols -Open shortest path first -IS-IS
Autonomous System
Old definition
An autonomous system is a group of routers under a common administrative domain running a common routing protocol
Contemporary definition
An autonomous system is an internetwork under a common administration
MADURAI NIB 53
Interior-Exterior Gateway Protocols
Interior Gateway Protocols
Routing Protocols which run within Autonomous System are IGPs IGPs discover paths between networks an
Exterior Gateway Protocols
Routing Protocols that route between Autonomous System are EGPs EGPs discover paths between autonomous systems
MADURAI NIB 54
IGPs-EGPs
AS-0
BGP
AS-1
IGP
BGP
AS-2
BGP
IGP
IGP
MADURAI NIB 55
Administrative Distances
Metrics are assigned to the routes to determine the most preferred route.
RIPs metric is hop count IGRP uses bandwidth and delay OSPF uses cost EIGRP uses composite metric
Diversity of metrics poses problems in routers running more than one routing protocol.
MADURAI NIB 56
Administrative Distances
Router may learn a route to the same destination from each of the protocols Which route should be selected? The answer to the problem is administrative distance Administrative distances are the route sources to determine most preferred source Administrative distance is a measure of believability
MADURAI NIB 57
Administrative Distances
The administrative distance protocols is as below:
Connected Interface Static Route EIGRP summary route External BGP EIGRP IGRP -0 -1 -5 - 20 - 90 - 100
of
various
MADURAI NIB 58
Administrative Distances
OSPF IS-IS RIP EGP External EIGRP Internal BGP Unknown - 110 - 115 - 120 - 140 - 170 - 200 - 255
The lower the administrative distance, the more believable the protocol.
MADURAI NIB 59
Flow Chart of a Packet
Packet Received NO Header & Checksum Valid YES Decrement TTL; TTL>=0 NO Send ICMP error message Discard original Packet NO Route Found YES Build new packet with MAC address and route through port found in routing table Received ARP reply, insert MAC and IP address into ARP table MAC Address Found NO Send ARP request and wait for a response NO If route available, search MAC in ARP cache Received ARP Reply YES
YES
Route table lookup on Dest. Add.
YES
NO
Default route available YES
MADURAI NIB
60
MADURAI NIB 61