Chapter 9
IFN507 Lecture 5
Routing
1
Outline
Routing
Static routing
Dynamic routing
7. Application
6. Presentation
5. Session
4. Transport
3. Network
2. Data Link
1. Physical
2
Core components of Internet Connections
Addressing
IP addresses
Naming
Domain names — IP addresses
Routing
Relay packets from one network to another
3
3
Routing
Introduction
In networking, the process of forwarding packets from source to destination.
Routing is usually performed by a dedicated device called a router.
Routing is one of fundamental features of the Internet because it enables packets to pass from one device to another and then reach the final destination.
Each intermediary node performs routing by passing along the packet to the next node.
The routing process involves selecting the best route to reach the final destination
5
5
Routers
Routers operate at the Network layer (Layer 3)
Connect separate logical networks to form an internetwork
Broadcast frames are not forwarded to other router ports (other networks)
Routers can be used to create complex internetworks with multiple paths creating fault tolerance and load sharing
Routers must have two or more interfaces (ports) in order to forward packets to other networks
6
Routers in Depth
Routers operate at the Network layer (Layer 3) and work with packets
Connect separate logical networks to form an internetwork
Broadcast frames are not forwarded to other router ports (other networks)
Routers can be used to create complex internetworks with multiple paths creating fault tolerance and load sharing
6
Router interfaces
7
Router Configuration
IP Assignment and routing
8
Routing (continued)
How does a router decide which line to transmit on?
A router must select the best path to the destination
Often many possible routes exist between sender and receiver
9
9
Routing (continued)
A
C
B
E
D
G
F
What is the best path from A to G?
10
10
Routing (continued)
The communications network with its nodes and telecommunication links is essentially a weighted network graph.
The edges, or telecommunication links, between nodes, have a cost associated with them.
The cost could be a hop count, delay cost, a queue size cost, a limiting speed, or simply a dollar amount for using that link.
11
11
The router uses its routing table to determine the best path to forward packets
Brisbane
San Francisco
Cheaper, faster, better
Tokyo
12
Routing Administration
Assign IP addresses to router interfaces
Select Routing protocols
Build/enable routing tables
Test and monitor routing
13
13
Routing Process between Networks
A
B
C
Application
Presentation
Session
Transport
Network
Data Link
Physical
Network
Data Link
Physical
Network
Data Link
Physical
Network
Data Link
Physical
Application
Presentation
Session
Transport
Network
Data Link
Physical
14
The router performs three major steps
Step 1: De-encapsulates the Layer 2 frame header and trailer to expose the Layer 3 packet.
Step 2: Examines the destination IP address of the IP packet to find the best path in the routing table.
Step 3: If the router finds a path to the destination, it encapsulates the Layer 3 packet into a new Layer 2 frame and forwards the frame out the exit interface.
15
Algorithm for Routing Process
When the router receives a packet, it evaluates the TTL.
If the TTL = 0, then
the router drop packet and sends
an ICMP Time Exceeded Message to the source
Else (If the TTL >0), then the router
Decrements the TTL by 1
Examines its destination IP address
Searches for the best match with a network address in the routing table.
If a match is found, the router
Encapsulates the IP packet into a new data link frame of the outgoing interface and then forward the packet
Else
Issues an ICMP Destination Unreachable and drop the packet
TTL= Time-to-live
ICMP =Internet Control Message Protocol
16
Router Interfaces
Routers must have two or more interfaces (ports) in order to forward packets to other networks
When a router interface receives a frame it compares the destination MAC address with the interface’s MAC address
If they match, the router strips the frame header and trailer and reads the packet’s destination IP address
If the IP address matches it processes the packet
If the IP address does not match, the router consults its routing table to determine how to get the packet to the its destination
Process of moving a packet from the incoming interface to the outgoing interface is called packet forwarding
16
Router Interfaces
17
Router Interfaces
17
Routing Table
Routing tables are composed of network address and interface pairs that tell the router which interface a packet should be forwarded to
18
Routing Table (continued)
Most routing tables entries contain:
Destination network
usually expressed in CIDR notation such as 172.16.0.0/16
Next hop
The next hop indicates an interface name or the address of the next router in the path to the destination
Metric
Numeric value that tells the router how “far away” the destination network is (also called cost or distance)
Total number of routers a packet must travel through is called the hop count
Timestamp
Tells the router how long it has been since the routing protocol updated the dynamic route
19
Routing Table (continued)
Types of routing table entries:
Directly connected network
A directly connected network is a network that is directly attached to one of the router interfaces
The network address/subnet mask of the interface, along with the interface type and number, are entered into the routing table as a directly connected network. .
Remote network
A remote network is a network that is not directly connected to the router. Namely, a remote network is a network that can only be reached by sending the packet to another router.
Default routes (quad-zero route)
All packets for destinations not established in the routing table are sent via the default route as the last resort
Expressed as 0.0.0.0/0
20
How do we keep a routing table simple and concise?
4 Principles for routing tables
Route summarisation
Next hop
Destination network
Default route
21
Routing Protocols
Routing tables can contain directly connected, manually configured static routes and routes learned dynamically using a routing protocol.
Routing protocol (static and dynamic routing)
A set of rules that routers use to exchange information so that all routers have accurate information about an internetwork to populate their routing tables
22
22
Outline
Routing
Static routing
Dynamic routing
7. Application
6. Presentation
5. Session
4. Transport
3. Network
2. Data Link
1. Physical
23
Static routing
A network administrator, with knowledge of the network topology, builds and updates the routing table manually
The advantage of being predictable and simple to set up and manage in small-sized networks
Do not scale well for large or dynamically changing networks
24
When to use static routing
A network consists of only a few routers
The ISP represents the only exit point to the Internet
A network is configured in hub-and-spoke topology
A central location (the hub)
Each branch has only one path to given destination via the central location
Accessing a single default route
It is used to represent a path to any network that does not have a specific match with another route in the routing table
25
Static routing (continued)
R2
Destination Network Next hop
192.0.3.0/24 Directly Connected
192.0.2.0/24 Directly Connected
192.0.0.0/24 Directly Connected
192.0.1.0/24 192.0.0.1
The Internet 192.0.0.1
R2
Destination Network Next hop
192.0.3.0/24 Directly Connected
192.0.2.0/24 Directly Connected
192.0.0.0/24 Directly Connected
0.0.0.0/0
(Default route) 192.0.0.1
For a directly connected route, no configuration is required!
26
26
Static routing (continued)
R1
Destination Network Next hop
192.0.0.0/24 Directly Connected
192.0.1.0/24 Directly Connected
200.0.0.0/24 Directly Connected
192.0.2.0/24 192.0.0.2
192.0.3.0/24 192.0.0.2
The Internet 200.0.0.2
R1
Destination Network Next hop
192.0.0.0/24 Directly Connected
192.0.1.0/24 Directly Connected
200.0.0.0/24 Directly Connected
192.0.2.0/23
(192.0.2.0/24+192.0.3.0/24) 192.0.0.2
0.0.0.0/0 200.0.0.2
For a directly connected route, no configuration is required!
27
ISP
Destination Network Next hop
200.0.0.0/24 Directly Connected
192.0.0.0/24 200.0.0.1
192.0.1.0/24 200.0.0.1
192.0.2.0/24 200.0.0.1
192.0.3.0/24 200.0.0.1
Static routing (continued)
ISP
Destination Network Next hop
200.0.0.0/24 Directly Connected
192.0.0.0/22 =
(192.0.0.0/24+192.0.1.0/24+
192.0.2.0/24+192.0.3.0/24) 200.0.0.1
For a directly connected route, no configuration is required!
28
Outline
Routing
Static routing
Dynamic routing
7. Application
6. Presentation
5. Session
4. Transport
3. Network
2. Data Link
1. Physical
29
Dynamic Routing
A dynamic routing protocol is used by routers to exchange routing information with each other.
The process of dynamic routing involve three stages:
initialisation, sharing and updating
Before the router processes and calculates received routing information, the network administrator needs to define which routes are to be advertised on a router.
the directly connected networks to the router
30
Dynamic Routing (continued)
Suited for medium-sized and large-sized networks
Automatic updating of routing table entries
Ongoing communication and dynamic updating of routing tables
Facilitated by a routing protocol
Periodic or on-demand routing exchange
Ability to sense and recover from network faults
To reflect the new topology
Convergence is achieved when a set of routers have the same topological information from each other
31
Dynamic Routing protocol
Routing category
Routing algorithm
Routing protocol
32
Dynamic Routing Protocols
Interior Gateway protocol
(IGP)
Exterior Gateway Protocol
(EGP)
Path vector algorithm
Distance Vector algorithm
RIP
EIGRP
Link State Algorithm
OSPF
BGP
IGP and EGP
Interior Gateway Routing Protocols (IGP)
For routing inside an autonomous system (AS)
e.g. RIP, EIGRP, OSPF
Exterior Routing Protocols (EGP)
For routing between autonomous systems
E.g: BGP
An AS is a collection of networks that are administered by a single entity or organization
33
Distance Vector Algorithm
Distance Vector algorithm
Based on the Bellman Ford Algorithm
When it boots, a router initializes its routing table to contain an entry for each directly connected network.
Each router periodically shares its knowledge about the entire routing table to its all interfaces
Routers each report their own knowledge, i.e.,
“I can reach destination V at distance D via X”
Distance vector routers periodically broadcast/multicast their route information on directly connected links periodic update
35
Routing Examples
Routing Information Protocol (RIP)
1st routing protocol used on the Internet
A form of distance vector routing
During an initialisation process, a router sends out a copy of its own routing table to through its all interfaces.
Then each node kept its own table and updated routing information with its neighbors at every 30 seconds.
36
36
Routing Examples (continued)
Suppose that Router A has leant 4 routes to Networks BNE-SYN, SYN-MEL, MEL-ADL, and ADL-PER
A’s current routing table:
A’s routing
Destination Network Metrics
(cost) Next
Hop
BNE-SYN 8 B
SYN-MEL 5 C
MEL-ADL 6 C
ADL-PER 10 D
37
37
Routing Examples (continued)
Now suppose Router D sends out the following routing information
D’s routing
Destination
Network Metrics
(cost)
BNE-SYN 4
MEL-ADL 5
BNE-CBR 7
ADL-PER 10
38
38
Routing Examples (continued)
Router A will look at each entry in Router D’s table and make the following decisions:
Router D says Network BNE-SYN is 4 hops away (from Router D).
Since Router D is 1 hop away from Router A, Network BNE-SYN is actually 5 hops away from Router A.
That is better than the current entry of 8 hops in Router A’s table, so Router A will update the entry for Network BNE-SYN.
Router D says Network MEL-ADL is 6 hops away (5 hops from Router D plus the 1 hop between Router A and Router D).
That is currently the same hop count as shown in Router A’s table for Network MEL-ADL, so Router A will not update its table.
39
39
Routing Examples (continued)
Router D says Network BNE-CBR is 8 hops away (7 hops from Router D plus the 1 hop between Router A and Router D).
Since Router A has no information about Network BNE-CBR, Router A will add this entry to its table. And since the information is coming from Router D, Router A’s Next Router entry for network BNE-CBR is set to D.
Router D says Network ADL-PER is 11 hops away (10 hops from Router D plus the 1 hop between Router A and Router D).
Router A to Network ADL-PER through D and D’s distance to Network ADL-PER has changed. A will update its table.
40
40
Routing Examples (continued)
Router A’s updated routing table
A’s old routing table
Destination Network Metrics
(cost) Next Hop
BNE-SYN 8 B
SYN-MEL 5 C
MEL-ADL 6 C
ADL-PER 10 D
D’s routing table
Destination Network Metrics
(cost)
BNE-SYN 4
MEL-ADL 5
BNE-CBR 7
ADL-PER 10
Routing table from D
after increment
Destination Network Metrics
(cost)
BNE-SYN 5
MEL-ADL 6
BNE-CBR 8
ADL-PER 11
+1
A’s updated routing table
Destination Network Metrics
(cost) Next Hop
BNE-SYN 5 D
SYN-MEL 5 C
MEL-ADL 6 C
BNE-CBR 8 D
ADL-PER 11 D
41
Updated
Link State Algorithm
Link State Algorithm
Based on the Dijkstra’s Least-Cost Algorithm
The algorithm finds all possible paths between two locations
By identifying all possible paths, it also identifies the least cost path
The algorithm can be applied to determine the least cost path between any pair of nodes
43
43
Dijkstra’s Least-Cost Algorithm
A
C
B
E
D
G
F
4
5
3
1
4
2
4
2
5
5
1
7
Path A-D-G = 9
Path A-B-G = 9
Path A-B-E-G = 8
What is the shortest path ?
….
44
44
Link State Routing
Uses the Dijkstra’s algorithm to compute the paths
Each router generates information about only its directly connected links
build adjacencies with neighbouring routers
Does not periodically send out the entire routing table
only send an update when a link state changes
Routers establish a relationship with neighbours
Hello messages are used to maintain adjacency with neighbours
Most common implementation: Open Shortest Path First (OSPF)
45
45
Link State
Exchanges link state advertisements (LSAs) throughout the network to update routing tables
LSAs
A router’s attached network prefixes their assigned costs
Calculate the optimal routes to add to the routing table
LSAs are advertised
Upon startup
Changes in the network topology are detected
(updates not periodic)
Advantage
Low network overhead and convergence time
The ability to scale to large networks
Disadvantage
More complex and difficult to configure
46
Routing Examples
Open Shortest Path First (OSPF)
A form of link state routing based on Dijkstra’s least cost algorithm
It too was adaptive and distributed but more complicated than RIP and performed much better
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 and calculate the best path to each destination
47
Link State Packet (LSP) is generated by a network router in a link state routing protocol that lists the router’s neighbors.
47
Summary – Static routing
Advantages
Easy to implement and maintain in a small network
Very little overhead, no routing algorithm or update are required, so no extra resources (CPU and memory) required
Disadvantages
Not easy to implement in a large network
If a link fails, a static route cannot reroute traffic
When to use
A network consists of only a few routers
The ISP represents the only exit point to the Internet
A network is configured in hub-and-spoke topology
Accessing a single default route
48
Summary – Dynamic routing
Advantages:
Suitable in all topologies where multiple routers are required
Automatically adapts topology to reroute traffic if possible
Disadvantages:
Can be more complex to initially implement
Requires additional resources such as CPU, memory, and link bandwidth for routing updates
49
End of Lecture
next Lecture
ICMP, ARP, TCP and UDP
50
50
/docProps/thumbnail.jpeg