ITO4137

Introduction to Computer
Architecture and Networks
Module 4: Network and Transport Layers (Part 2)
Dr. Abdul Malik Khan

ITO4137
 Unit
Topics

ITO4137 2
 Toda
y
Recap: TCP segmentation
• congestion control, window size
Routing
• how routers determine the path to a destination
address
• how routers exchange information about the network
to find good paths

ITO4137 3
 TCP
parameters
TCP implements segmentation

• large application layer messages are split into

segments

How fast to send segments?

• Sending too many at once may overload receiver or

intermediate path with lower bandwidth

How to decide the segment size?

• Sending too large segments requires IP to fragment

• Large segments also increase errors

ITO4137 4
 TCP segment
size
Two approaches:
• use “reasonable” MTU, accept that IP sometimes
needs to fragment
• use Path MTU Discovery (PMTUD):
• send IP packets to destination, asking routers to
never fragment
• if router would have to fragment, it sends back an
error message
• increase packet length until error occurs, then use
last known error-free MTU
ITO4137 5
 TCP congestion control
How fast to send?
• Receiver transmits its maximum buffer size
• Sender sends segments without waiting for ACK up
to buffer size
What if network cannot cope?
• Start slow: wait for ACK after each segment
• Increase with every ACK: send two, four etc
segments after each ACK
• Fall back to slower speed when no ACK arrives

ITO4137 6
 The Network Layer:
Routing

ITO4137
 Recap: Subnets
130.194.76.192 Backbone
network
130.194.76.253
130.194.40.13

130.194.76.191
Gateway routers
Gateway routers

130.194.66.61
130.194.40.22

130.194.66.43

ITO4137 8
 Routers
Routers connect networks

• Internet is a network of networks!

• Most important piece of Internet

infrastructure

A router is a layer 3 device

• one IP address per interface, i.e. typically per subnet it is
connected to

• Clients send packets to routers if destination is outside

their own subnet

Routers use IP address to determine over where the packet

•
is sent next

ITO4137 9
 Routing
For each incoming packet, the router
• looks at the packet's destination IP
address

• consults the routing table:

to which other router should I send a
packet for this destination, or can I deliver
it directly?

• if destination not in table: send to default

gateway

• if no default gateway configured: packet

can't be routed

ITO4137 10
 Routing
Three components:
• The routing protocol:
how to find the best route between a sender and a
receiver through the network
• The routing table:
the best routes currently known are stored in a
lookup table for fast access
• The routing decisions:
deciding for each incoming packet where it is sent
next

ITO4137 11
 Routing example
Dest. Next Dest. Next
A A A C
dest: H
A G D G G G
H E H H
K E K C
Dest. Next
default C
C D

Dest. Next

B E F default F

Dest. Next Dest. Next

A C A D
K G F G D H
H F H H
dest: A
K B K E
ITO4137 12
 Types of
Centralizedrouting
• All clients connect to central computer, which makes
the routing decisions
• Used on small, host-based networks
Decentralized
• Each device makes its own decisions
• Information needs to be exchanged to prepare routing
tables
• Used on the Internet

ITO4137 13
 Types of decentralised routing
Static routing
• Network manager prepares fixed routing tables

• Manually updated when the network changes

• Used in simple networks that don't change a lot

ITO4137 14
 Dynamic Routing

ITO4137
 Question: Router administration

Routers are typically managed by logging in via SSH and then

configuring the router using command line tools.
What are the risks of this approach?

1. Remote operation is always risky, because someone could

eavesdrop on the connection, find out the router password and
then change its configuration.

1. Two admins could be logged in simultaneously and set up

conflicting configurations.
FK2HL1
3. None, because SSH is a secure
protocol.
4. When you modify the routing table, you risk locking yourself
out.

ITO4137 16
 Question: Router administration

Routers are typically managed by logging in via SSH and then

configuring the router using command line tools.
What are the risks of this approach?

1. Remote operation is always risky, because someone could

eavesdrop on the connection, find out the router password and
then change its configuration.

1. Two admins could be logged in simultaneously and set up

conflicting configurations.
3. None, because SSH is a secure protocol. (Correct
Answer)
4. When you modify the routing table, you risk locking yourself
out.

ITO4137 17
 Types of decentralised routing
Static routing
• Network manager prepares fixed routing tables

• Manually updated when the network changes

• Used in simple networks that don't change a lot

Dynamic routing
• Routers exchange information to build routing
tables dynamically
• Initial tables can be set up by network managers

ITO4137 18
 Dynamic routing algorithms
Distance vector
• Exchange information about distance to destination,
choose shortest route
• EIGRP (Enhanced Interior Gateway Routing
•
Protocol) RIP (Routing Information Protocol)
•
BGP (Border Gateway Protocol)
Link state
• Exchange information about quality of links, choose
fastest route
• OSPF (Open Shortest Path First)
ITO4137 19
 Distance vector routing
A Network A
Distance: 0 hops
G
Direction: interface 0
0
1 0 1
3 C D
2 3 2
Network G
Distance: 1 hop
Direction: interface 1 Network K
0 Distance: 2 hops
Direction: interface 0
B 2 E 1 F

K Interface number H

ITO4137 20
 Routing Information
Dest. Dist. Interf. Protocol
Dest. Dist. Interf. (RIP)
A 0 0 C 0 0
A B 0 1 G 0 1 G
E 0 2 H 0 2
D 0 3 F 0 3
K 1 1 A 1 0
G 1 C3 B D1 0
H 1 3 E 1 0
F 1 3 K 2 0

B E F
Dest. Dist. Interf.
A 0 0
All routers send their routing
C 0 1
K tables to all other routers. H
E 0 2
K 0 3 Tables converge after some time.
ITO4137 21
 Routing Information Protocol (RIP)

Distance = hop count

• Max. hop count 15
• Avoids loops
Only used in small networks
• At most 15 hops
• Updates transmit whole routing table
•
Can be slow to converge

ITO4137 22
 RIP
demo

ITO4137
 RIP
demo

ITO4137
 Link-state routing protocols
Routers exchange information about connectivity
• not just routing table (best routes)

• but all of the network it knows about

• use a metric (usually link speed) to describe the

quality of each connection
Each router creates a topological map
• a map of the entire network
• each router can independently compute best route
to every subnet using a shortest path first algorithm

ITO4137 25
 Dijkstra's Shortest Path Algorithm
A tentative distance ∞ G
5 5
∞ 0 ∞
C 5 D metric
2 (lower=better)
1 1 2
20
∞ ∞ ∞
B 1 E 1 F
5
5
H
K ∞ ∞
ITO4137 26
 Dijkstra's Shortest Path Algorithm
A 5 ∞ G
5 5
0 5
C 5 D
2
1 1 2
20
1 1 ∞
B 1 E 1 F
5
5
K H
∞ ∞
ITO4137 25
 Dijkstra's Shortest Path Algorithm
A 5 ∞ G
5 5
0 5
C 5 D
2
1 1 2
20
1 1 ∞
B 1 E 1 F
5
5
H
K ∞ ∞
ITO4137 26
 Dijkstra's Shortest Path Algorithm
A 5 ∞ G
5 5
0 5
C 5 D
2
1 1 2
20
1 1 2
B 1 E 1 F
5
5
H
K ∞ ∞
ITO4137 29
 Dijkstra's Shortest Path Algorithm
A 3 ∞ G
5 5
0 5
C 5 D
2
1 1 2
20
1 1 2
B 1 E 1 F
5
5
H
K 6 ∞
ITO4137 30
 Dijkstra's Shortest Path Algorithm
A 3 ∞ G
5 5
0 4
C 5 D
2
1 1 2
20
1 1 2
B 1 E 1 F
5
5
K H
6 7
ITO4137 29
 Dijkstra's Shortest Path Algorithm
A 3 ∞ G
5 5
0 4
C 5 D
2
1 1 2
20
1 1 2
B 1 E 1 F
5
5
K H
6 7
ITO4137 30
 Dest. Route
Dijkstra's SA ort
B est Path Algorithm
K B
A 3 hGH EE 9 G
5 5
0 4
C 5 D
2
1 1 2
20
1 1 2
B 1 E 1 F
5
5
K H
6 Shortest Path First (SPF) tree 7
ITO4137 33
 Open Shortest Path First
(OSPF)
Widely used in large enterprise
networks
• OSPFv1 1987, OSPFv2 1991/1998, OSPFv3 for
IPv6 1999
Link-state routing protocol
• router builds and maintains a link-state database (LSDB)

• link cost calculated based on bandwidth

• routers exchange information about their LSDB using

multicast and unicast messages
• LSDB is used to create a SPF tree
• best routes from SPF tree are placed in routing table
ITO4137 34
 OSPF
demo

ITO4137
 OSPF
demo

ITO4137
 Dynamic routing algorithms
Distance vector
• Exchange information about distance to destination,
choose shortest route
• EIGRP (Enhanced Interior Gateway Routing
•
Protocol) RIP (Routing Information Protocol)
•
BGP (Border Gateway Protocol)
Link state
• Exchange information about quality of links, choose
fastest route
• OSPF (Open Shortest Path First)
ITO4137 37
 FLUX Question: WIFI
Routers
Your WiFi/ADSL modem at home is often called a WiFi
Router. What kind of routing does it perform?

1. Static routing, all packets are routed to my ISP.

1. BGP routing, it connects my AS at home to the internet.

1. Link-state routing, to compensate for sometimes poor quality

of ADSL connections.

1. No routing, the name is just used for marketing

reasons.

ITO4137 38
 FLUX Question: WIFI
Routers
Your WiFi/ADSL modem at home is often called a WiFi Router.
What kind of routing does it perform?

1. Static routing, all packets are routed to my ISP. (Correct Answer)

1. BGP routing, it connects my AS at home to the internet.

1. Link-state routing, to compensate for sometimes poor quality of

ADSL connections.

1. No routing, the name is just used for marketing reasons.

ITO4137 39
 Autonomous Systems
Networks operated by a single organisation
• e.g. Monash University’s or your ISP’s network
Interior routing
• for routing packets within an AS
• uses RIP, OSPF, EIGRP
Exterior routing
• for routing packets between different AS

• Internet uses BGP (Border Gateway Protocol)

ITO4137 40
 Internet Architecture
Interior routing
AS1
OSPF
BGP AS3

Border router
BGP
BGP BGP

AS4

RIP BGP

AS2 BGP
BGP
OSPF
AS5
AS6
ITO4137 41
 FLUX Question: OSPF for the Internet?

Why isn’t OSPF used for routing between autonomous systems?

1. This would be a security concern, because it would expose

internal AS network structure to the outside.

1. This would be a scalability issue, because routers would

have to communicate the entire structure of the internet.

1. This would be impossible to manage for network

administrators.

1. This would be impossible because OSPF only routes in

subnets, not in general networks.

ITO4137 42
 FLUX Question: OSPF for the Internet?

Why isn’t OSPF used for routing between autonomous systems?

1. This would be a security concern, because it would expose

internal AS network structure to the outside.

1. This would be a scalability issue, because routers would

have to communicate the entire structure of the internet.

1. This would be impossible to manage for network

administrators. (Correct Answer)

1. This would be impossible because OSPF only routes in

subnets, not in general networks.

ITO4137 43
 Putting it all together
(demo)

ITO4137
 Summary
Recap: TCP Segmentation
• congestion control makes TCP adapt to the network
conditions
IP Routing
• routers determine next hop of a packet through the network
• routing tables map destinations to their next hop

• can be configured statically or dynamically

• distance-vector routing (RIP)

• link-state routing (OSPF)

• BGP to connect autonomous systems
ITO4137 46
 Lab Week 9
Overview

• Routing Table

ITO4137 47
 Next week: Application Layer

• Architectures: client-server, multi-tier, peer-to-peer

• World Wide Web: HTTP and HTML

• Email: SMTP, POP,

IMAP

ITO4137 48