程序代写CS代考 algorithm Network Layer COMP90007 Internet Technologies – cscodehelp代写

Network Layer COMP90007 Internet Technologies
Lecturer: Semester 2, 2021
© University of Melbourne 2021

Outline
◼ Network layer in the Internet
◼ Types of services
◼ Internetworking
❑ Tunneling
❑ Fragmentation
❑ Path MTU discovery
◼ Internet Protocol ❑ Addressing
❑ Subnetting
◼ Routing algorithms
46

Routing
Consider the network as a graph of nodes and links: ◼ Routing is the process of discovering network paths
◼ Decide what to optimise: hops, delay, etc.
◼ Update routes for changes in topology (e.g., router failures)
ISP’s equipment
A’s table (initially) A’s table (later) C’s Table E’s Table
47

Routing Algorithms (1)
◼ The routing algorithm is responsible for deciding on which output line an incoming packet should be transmitted
◼ Non-Adaptive Algorithms
❑ Static routing, static decision-making process
◼ Adaptive Algorithms
❑ Dynamic routing, dynamic decision-making process ❑ Changes in network topology, traffic, etc.
48

Routing Algorithms (2)
◼ Non-adaptive
❑ Shortest path routing ❑ Flooding
◼ Adaptive
❑ Distance vector routing ❑ Link state routing
◼ Hierarchical routing
◼ Broadcasting routing
◼ Multicasting routing
49

Optimality Principle
◼ If router B is on the optimal path from router A to router C, then the optimal path from B to C also falls along the same route.
C r2
r3
ArB 1
50

Sink Tree
◼ Sink Tree: the set of optimal routes from all sources to a given destination forms a tree rooted at the destination
◼ Goal of a routing algorithm: discover and utilise the sink trees for all routers
Network Sink tree of best paths to router B
51

Shortest Path Routing
◼ A non-adaptive algorithm
◼ Shortest path can be determined by building a graph with each node representing a router, and each arc representing a communication link
◼ To choose a path between 2 routers, the algorithm finds the shortest path between them on the graph
◼ Metrics: number of hops, distance, delay etc.
52

Shortest Path: Dijkstra’s Algorithm (1)
◼ Computes a sink tree on the graph:
❑ Each link is assigned a non-negative weight/distance ❑ Shortest path is the one with lowest total weight
❑ Using weights of 1 gives paths with fewest hops
◼ Algorithm:
1) Create a set P, tracking the nodes added in the tree. Initialise it as empty.
2) For each node, assign a distance value d from the node to sink. Initialise the distance for all nodes as infinity.
3) Start from the sink node, assign distance as 0.
4) RepeatwhenPdoesn’tincludeallnodes:
i. For all the nodes not in P, compare distance d
ii. Pick a node v with min distance and add it to P
iii. Update d for all the adjacent nodes of v (newly added node)
53

Shortest Path: Dijkstra’s Algorithm (2)
Distance to A Set P
{A}
{A, B} {A, B, E}
n
A
B
C
D
E
F
G
H
1
0
∞
∞
∞
∞
∞
∞
∞
2
—
2
∞
∞
∞
∞
6
∞
3
—
—
9
∞
4
∞
6
∞
54

Distance to A
Set P
{A} {A, B}
{A, B, E}
{A, B, E, G}
{A, B, E, G, F}
{A, B, E, G, F, H}
{A, B, E, G, F, H, C}
{A, B, E, G, F, H, C, D}
n
A
B
C
D
E
F
G
H
1
0
∞
∞
∞
∞
∞
∞
∞
2
—
2
∞
∞
∞
∞
6
∞
3
—
—
9
∞
4
∞
6
∞
4
—
—
9
∞
—
6
5
∞
5
—
—
9
∞
—
6
—
9
6
—
—
9
∞
—
—
—
8
7
—
—
9
10
—
—
—
—
8
—
—
—
10
—
—
—
—
D (∞,-)
…
55

Flooding
◼ A non-adaptive algorithm
◼ Every incoming packet is sent out on every outgoing
line except the one on which it arrived
◼ Inefficient: generates a large number of duplicate packets
◼ Selective flooding is an improved variation
❑ Routers send packets only on links which are approximately in the right direction
56

Distance Vector Routing (1)
◼ A dynamic algorithm
❑ Each router maintains a table which includes the best-known
distance to each destination and which line to use to get there
❑ Tables are updated by exchanging information with neighbouring routers
❑ Global information shared locally
◼ Algorithm:
1) Each node knows distance of links to its neighbors
2) Each node advertises vector of lowest known distances to all neighbors
3) Each node uses received vectors to update its own
4) Repeat periodically
57

Distance Vector Routing (2)
Network
JA = 8, JI = 10, JH = 12, JK = 6
Vectors received from neighbors A, I, H and K
New vector for J
58

Link State Routing
◼ A dynamic algorithm
❑ An alternative to distance vector: too long to converge after the
network topology changed
❑ Widely used in the Internet, e.g. Open Shortest Path First (OSPF)
❑ More computation than distance vector
❑ Local information shared globally, using flooding
◼ Algorithm: each router has to
1) Discover neighbours and learn network addresses
2) Measure delay or cost to each neighbour
3) Build link state packet
4) Send this packet to all other routers
5) Compute the shortest path to every other router, e.g. using Dijkstra’s algorithm
59

Building Link State Packets
◼ Link State Packet (LSP) for a node lists neighbours and the distance to reach them
Network LSP for all nodes
◼ When to build new LSP?
➢ Periodically at regular intervals
➢ Build them when some significant event occurs
60

Hierarchical Routing (1)
◼ As networks grow in size, routing tables expand and this impacts CPU and memory requirements
◼ Dividing all routers into regions increases
efficiencies
❑ Each router knows everything about other routers in its region but nothing about routers in other regions
❑ Routers which connect to two regions act as exchange points for routing decisions
61

Hierarchical Routing (2)
◼ Hierarchical routing reduces the work of computation but may result in slightly longer paths than flat routing
62

Broadcast Routing (1)
◼ Broadcast routing allows hosts to send messages
to all other hosts.
❑ Single distinct packet to each destination: inefficient, and source needs all destination addresses
❑ Multi-destination routing: a router copies the packet for each outgoing line. Use bandwidth more efficiently, but source needs to know all the destination addresses
❑ Flooding
❑ Reverse path forwarding
63

Broadcast Routing (2)
D1
A
B
D2
C
D3
64

Broadcast Routing (3)
◼ Reverse path forwarding
The router checks if the broadcast packet is arrived on the line normally used for sending packets to the source of the broadcast
❑ Yes: there is a high probability that the route used to transmit this packet is the best, and this packet is the first copy. The router then copies the packet and forwards them onto all other lines.
❑ No: the packet is discarded as a likely duplicate.
65

Multicast Routing (1)
◼ Multicast routing allows hosts to send a message to a well-defined group within the whole network
◼ Each router computes a spanning tree covering
all other routers
❑ Spanning tree: subset of the graph that includes all nodes, but no loops.
❑ Prunes the spanning tree to eliminate all lines which do not lead to members of the group
66

Multicast Routing (2)
A
network spanning tree for router A AA
multicast tree for Group 1
multicast tree for Group 2
67

Summary
◼ Network layer in the Internet
◼ Types of services
◼ Internetworking
❑ Tunneling
❑ Fragmentation
❑ Path MTU discovery
◼ Internet Protocol ❑ Addressing
❑ Subnetting
◼ Routing algorithms
68