PowerPoint Presentation
COMP30023 Computer Systems
Copyright By Assignmentchef assignmentchef
University of Melbourne 2022
Internet (Network) Layer Routing
Internet is a hierarchy of nested networks
Levels of the hierarchy look similar
Subnetting is subdividing an organizations network
into smaller networks
NAT (Network address translation)
Tweaking IP packet fields to allow private addresses
internally and public addresses externally
Many problems, but simplifies management
Fragmentation
Break packets into smaller pieces within the network
16/05/22 University of Melbourne 2
Forwarding vs Routing
Routing within networks / domains
Interdomain routing (BGP)
16/05/22 University of Melbourne 3
16/05/22 4
Packet forwarding
TN 6th 5-2
University of Melbourne
Each router has a forwarding table (or routing table).
This maps destination addresses to outgoing interfaces.
Upon receiving a packet:
inspect the destination IP address in the header
index into the table
determine the outgoing interface
forward the packet out that interface
Then, the next router in the path repeats the process
The packet travels along the path to the destination.
16/05/22 University of Melbourne 5
Packet forwarding
How do these forwarding tables get created?
The routing algorithm decides which output line an incoming
packet should be transmitted on
Combination of
an algorithm local to each router
a protocol to gather the network information needed by the algorithm
16/05/22 University of Melbourne 6
Properties of a good routing algorithm
Correctness finds a valid route between all pairs of nodes
Simplicity
Robustness a router crash should not require a network reboot
Stability a stable algorithm reaches equilibrium and stays there
Fairness
Efficiency
Flexibility to implement policies
16/05/22 University of Melbourne 7
Routing Algorithm
If there is enough traffic between A and A, B and B, and C
and C, to saturate the horizontal link, what is the most
efficient course of action for handling traffic between X and
X? (i.e., what maximizes network throughput?)
16/05/22 University of Melbourne 8
Fairness vs. Efficiency
TN 6th 5-5
What is being optimised?
Mean packet delay?
Max network throughput?
Simplest approach
Minimise the number of hops a packet has to make
Tends to reduce per packet bandwidth and improve delay
Hopefully also reduces the distance travelled but not guaranteed
Crossing the Pacific is one IP hop
Actual algorithms give a cost to each link
More flexible, but still cannot express all routing preferences
16/05/22 University of Melbourne 9
Delay vs. Bandwidth
Non-adaptive (static routing)
Does not adapt to the network topology
Calculated offline and uploaded to the router at boot
Does not respond to failure
Reasonable where there is a clear or implicit choice
Think about your home router, a static route out of your network is perfectly
reasonable, since it is the only choice
Adaptive
Dynamic routing, adapts to changes in topology and potentially even
traffic levels
Optimise some property: distance, hops, estimated transit time, etc.
May get information from adjacent routers, or all routers in the network
16/05/22 University of Melbourne 10
Routing Algorithm
Simplest adaptive routing
Guarantees shortest distance and minimal delay
Useful benchmark in terms of speed
Extremely robust if there is a path it will find it
Highly inefficient generates many duplicate packets
Have to have a way of discarding packets (TTL)
If unknown can be set to diameter of network
16/05/22 University of Melbourne 11
Send a packet from A to D
16/05/22 University of Melbourne 12
16/05/22 University of Melbourne 13
16/05/22 University of Melbourne 14
E receives two copies
16/05/22 University of Melbourne 15
E forwards only one copy
Must keep track of packets it has forwarded
We need something more efficient than flooding
Should adapt to network topology and changes
If we have complete knowledge of the network topology
(what is connected to what) how can we determine an
optimal route?
16/05/22 University of Melbourne 16
Adaptive Routing
If router J is on the optimal path from router I to K, then the
optimal path from J to K also falls along the same route.
If a better route existed for J to K it would be combined with the one
from I to J, which would contradict our initial condition that our
route from I to K was optimal
When we study BGP, well see that this doesnt always apply
16/05/22 University of Melbourne 17
Optimality Principle (Bellman 1957)
The optimality principle means that a set of optimal routes
from all sources form a tree rooted at the destination
16/05/22 University of Melbourne 18
network sink tree for router B
TN 6th 5-6
View as a labelled graph
Label weight based on delay, distance, cost, etc.
A number of algorithms, most famous is Dijkstras algorithm
Finds the shortest path between a sink and all sources or vice versa
At each step, each node is labelled with its distance (sum of
costs on edges) from the source, and the best known path
Distances must be non-negative
16/05/22 University of Melbourne 19
Shortest Path Algorithm
Divide nodes into three groups: unseen, open, closed
unseen: Not a neighbour of any node we have processed
Open: We have visited a neighbour, but not it.We know a path
Closed: We have visited it.We know the best path to it
The algorithm moves nodes:unseen -> open -> closed
Initially no paths are known so all nodes have a value of
infinity (unseen)
As the algorithm proceeds, labels will be updated
Tentative (open) initial state
Permanent (closed) once a shortest path is found label is
permanent and wont change again
16/05/22 University of Melbourne 20
Dijkstras Algorithm
Send a packet from A to D
16/05/22 University of Melbourne 21
Shortest Path
Visit the source node: Open all of its neighbours and set their
labels as the distance to them.
Repeat until all nodes visited, or destination found:
1. Examine adjacent nodes to the working node, calculate
distance, update labels if improved
2. Examine all tentative/open nodes in the graph and pick the one
with the lowest distance and visit it
make that permanent/closed,
mark it as the working node
Go to step 1.(i.e., Open all of its neighbours and calculate the distance
to them via this path.If it is less than the neighbours current label set
the label to the lower value.)
16/05/22 University of Melbourne 22
Dijkstras Algorithm
Send a packet from A to D
16/05/22 University of Melbourne 23
Shortest Path
Make A permanent
16/05/22 University of Melbourne 24
Shortest Path
Open adjacent nodes (B,G): recalculate their weights
16/05/22 University of Melbourne 25
Shortest Path
Select lowest distance tentative node (B) and make permanent
16/05/22 University of Melbourne 26
Shortest Path
Recalculate distance for adjacent nodes (C,E)
16/05/22 University of Melbourne 27
Shortest Path
Select lowest distance tentative node (E) and make permanent
16/05/22 University of Melbourne 28
Shortest Path
Recalculate distance for adjacent nodes (F, G).Lower Gs cost
16/05/22 University of Melbourne 29
Shortest Path
Select lowest distance tentative node (G) and make permanent
16/05/22 University of Melbourne 30
Shortest Path
Recalculate distance for adjacent nodes (H)
16/05/22 University of Melbourne 31
Shortest Path
Select lowest distance tentative node (F) and make permanent
16/05/22 University of Melbourne 32
Shortest Path
Recalculate distance for adjacent nodes (H drops, C stays)
16/05/22 University of Melbourne 33
Shortest Path
Select lowest distance tentative node (H) and make permanent
16/05/22 University of Melbourne 34
Shortest Path
Recalculate distance for adjacent nodes (D)
16/05/22 University of Melbourne 35
Shortest Path
Select lowest distance tentative node (C) and make permanent
16/05/22 University of Melbourne 36
Shortest Path
Recalculate distance for adjacent nodes (D, stays)
16/05/22 University of Melbourne 37
Shortest Path
We can now stop because the lowest cost tentative node is the
destination
16/05/22 University of Melbourne 38
Shortest Path
LS is a distributed algorithm that replaced Distance Vector
Routing (Bellman-Ford), which converged slowly
Variants of Link State Routing used today
Simple 5 step process at each router:
1. Discover its neighbours and learn their network address
2. Set the distance or cost metric to each of its neighbours
3. Construct a packet containing all it has just learned
4. Send the packet to, and receive packets from, all other routers
5. Compute the shortest path to every other router
16/05/22 University of Melbourne 39
Link State Routing
Centralized
To discover neighbours, a router on boot sends out a HELLO
packet on each interface. The router on the other end must
reply with its unique ID
Slightly more complicated on LANs
Cost can be set automatically or manually
Common technique is 1/bandwidth: 1 Gbps = 1, 100 Mbps = 10
Could use delay as well calculated using an ECHO packet
Many networks manually choose preferred routes and then look for
link costs to make those routes the shortest.Traffic engineering
16/05/22 University of Melbourne 40
Link State Routing
A Link State packet consists of ID, sequence number, age, and a
list of neighbours and their respective costs
Building the packet is easy, deciding when to build them is
At intervals?
When a change occurs link disconnect?
16/05/22 University of Melbourne 41
Link State Routing
TN 6th 5-12
To send packets to all other routers, flooding is used
To be precise, reliable flooding which uses acknowledgements to
guarantee every other router receives the packet
To avoid waste, when a router receives a Link State Packet it
compares the sequence number to the one it previously received (if
any). If the sequence number is not larger it discards it and does not
forward on the flood
Sequence numbers are 32 bits to avoid wrap-around
Still a problem if a router crashes and restarts its sequence number
Solution is the age field, which is reduced by 1 each second, when the
age hits zero the information is discarded
16/05/22 University of Melbourne 42
Link State Routing
16/05/22 University of Melbourne 45
Border Gateway Protocol (BGP)
Recall that the internet is constructed by internetworking
independently administered networks
Autonomous System (AS) collection of routers under the same
administrative control
Bigger than the network part of IP address
Each network will have
A protocol for internal routing
(usually based on linked state)
A protocol for external routing
between ASes
Must be the same for all ASes
16/05/22 University of Melbourne 46
Border Gateway Protocol (BGP)
In contrast to the internal routing,
BGP needs to consider politics as well
Companies not willing to have their network used by others
ISPs not wanting other ISPs traffic on their networks
Not carrying commercial traffic on academic networks
Use one provider over another because they are cheaper
Dont send traffic through certain companies or countries
Cant always say one route is better than another
Better in some respects, worse in others
Bellmans optimality principle doesnt always apply
16/05/22 University of Melbourne 47
Border Gateway Protocol (BGP)
Typically based on
customer/provider: I pay you for transit oftraffic I send or receive
or peering agreements: we carry each others traffic without charge
Provider advertises routes for the entire internet
Customer only advertises routes for their network to avoid transiting
other traffic
Valley free
TN 6th 5-68
BGP is also a prime target for attack
A malicious AS can advertise routes for
networks at extremely low cost, causing traffic
to re-routed through that AS
2017 Russian AS advertised routes for Google,
Apple, Facebook, Microsoft, Twitter, etc.
2008 Pakistan attempted to block YouTube, but
inadvertently blocked it for the entire internet
Sometimes an innocent mistake, but also an
effective way to divert traffic for monitoring or
disruption
16/05/22 49
And finally
University of Melbourne
The slides were Adapted by from those
prepared by based on material developed
previously by:,,,
Some of the images included in the notes were supplied as
part of the teaching resources accompanying the text books
listed in lecture 1.
(And also) Computer Networks, 6th Edition, Tanenbaum A., Wetherall. D.
https://ebookcentral.proquest.com/lib/unimelb/detail.action?docID=6481879
Textbook Reference: Ch 5.1-5.4
16/05/22 University of Melbourne 50
Acknowledgement
https://ebookcentral.proquest.com/lib/unimelb/detail.action?docID=6481879
Internet (Network) Layer Routing
Packet forwarding
Packet forwarding (2)
Routing Algorithm
Fairness vs. Efficiency
Delay vs. Bandwidth
Routing Algorithm (2)
Flooding (2)
Flooding (3)
Flooding (4)
Flooding (5)
Adaptive Routing
Optimality Principle (Bellman 1957)
Shortest Path Algorithm
Dijkstras Algorithm
Shortest Path
Dijkstras Algorithm (2)
Shortest Path (2)
Shortest Path (3)
Shortest Path (4)
Shortest Path (5)
Shortest Path (6)
Shortest Path (7)
Shortest Path (8)
Shortest Path (9)
Shortest Path (10)
Shortest Path (11)
Shortest Path (12)
Shortest Path (13)
Shortest Path (14)
Shortest Path (15)
Shortest Path (16)
Shortest Path (17)
Link State Routing
Link State Routing (2)
Link State Routing (3)
Link State Routing (4)
Border Gateway Protocol (BGP) (2)
Border Gateway Protocol (BGP) (3)
Border Gateway Protocol (BGP) (4)
And finally
Acknowledgement
CS: assignmentchef QQ: 1823890830 Email: [email protected]
Reviews
There are no reviews yet.