PowerPoint Presentation
COMP30023 – Computer Systems
Copyright By PowCoder代写加微信 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 organization’s 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, we’ll see that this doesn’t 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 Dijkstra’s 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 won’t change again
16/05/22© University of Melbourne 20
Dijkstra’s 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 neighbour’s current label set
the label to the lower value.)
16/05/22© University of Melbourne 22
Dijkstra’s 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 G’s 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
– Don’t send traffic through certain companies or countries
• Can’t always say one route is “better” than another
– Better in some respects, worse in others
– Bellman’s optimality principle doesn’t 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
Dijkstra’s Algorithm
Shortest Path
Dijkstra’s 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.