程序代写 COMP30023 – Computer Systems

PowerPoint Presentation

COMP30023 – Computer Systems

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

• 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

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”

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?

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

Link State Routing

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

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

Border Gateway Protocol (BGP)

• Typically based on
– customer/provider: I pay you for “transit” of traffic 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…

• 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

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代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts