Transcript 沒有投影片標題 - National Tsing Hua University

Chapter 5
The Network Layer



The Network Layer deals with the end-to-end transmission of packets,
possibly making many hops at intermediate routers along the way.
Types of subnet
 Datagram (connectionless)
 Virtual circuit (connection-oriented)
Services provided
 Connectionless: e.g. UDP
 Connection-oriented: e.g. TCP
© All rights reserved. No part of these slides may be reproduced, in any
form or by any means, without permission in writing from
Professor Wen-Tsuen Chen (email: [email protected]).
(C) All rights reserved by Professor Wen-Tsuen Chen
1
(C) All rights reserved by Professor Wen-Tsuen Chen
2
(C) All rights reserved by Professor Wen-Tsuen Chen
3
Design Issues:
Routing
 Congestion Control
 Internetworking
 Examples:

 The
Network Layer in the Internet
 The Network Layer in ATM networks
(C) All rights reserved by Professor Wen-Tsuen Chen
4
Routing

Requirements for routing
 Correctness
 Fairness
 Simplicity
 Optimality
 Robustness
 Efficiency
 Stability
(C) All rights reserved by Professor Wen-Tsuen Chen
5
Types of Routing

Static routing:


Dynamic routing (Adaptive routing):


routes to destinations is predetermined and is not
dependent on the current state (traffic, topology etc.) of
the network.
routes being learned via exchange of routing
information to reflect changes in the topology and
traffic.
Default Routing:

Traffic to destinations that are unknown to the router is
sent to a default “outlet”.
(C) All rights reserved by Professor Wen-Tsuen Chen
6
The Optimality Principle



If router J is on the optimal path from router I to
router K, then the optimal path from J to K also
falls along the same route.
This implies that the set of optimal routes from all
sources to a destination form a tree, called a sink
tree, rooted at the destination.
The goal of all routing algorithms is to discover
and use the sink trees for all routers.
(C) All rights reserved by Professor Wen-Tsuen Chen
7
The goal of all routing algorithms is to discover and use the sink
trees for all routers.
(C) All rights reserved by Professor Wen-Tsuen Chen
8
Static Routing Algorithms
Shortest Path Routing



Find the shortest path between a given pair of
routers.
Cost of a link may be a function of the distance,
bandwidth, average traffic, communication cost,
mean queue length, delay. etc.
Use Dijkstra’s algorithm
(C) All rights reserved by Professor Wen-Tsuen Chen
9
(C) All rights reserved by Professor Wen-Tsuen Chen
10
Dijkstra’s algorithm
to compute
the shortest path
(C) All rights reserved by Professor Wen-Tsuen Chen
11
Flooding
Every incoming packet is sent out on every
outgoing line except the one it arrived on.
 Generate vast numbers of duplicate packets
 For robustness
 Concurrent updates of databases
 Shortest path is always choosed

(C) All rights reserved by Professor Wen-Tsuen Chen
12
Flow-Based Routing
(C) All rights reserved by Professor Wen-Tsuen Chen
13
(C) All rights reserved by Professor Wen-Tsuen Chen
14
Dynamic Routing Algorithms

Distance Vector Routing



Distributed routing algorithms, first used in APPANET until 1979.
Used in RIP (Routing Information Protocol) and BGP (Border
Gateway Protocol)
Routing Algorithm:


Each router maintains a routing table (i.e, a vector) giving the best
known distance (number of hops, delay, queue length) to each
destination and which link is used to get there.
These tables are updated by exchanging information with the
(adjacent) neighbors.
(C) All rights reserved by Professor Wen-Tsuen Chen
15

To determine the best link from router i to
the destination j :
 For
each adjacent router k of router i , compute
Xik+Xkj , where Xik is the distance newly
measured by router i and Xkj is the most current
distance computed by router k and sent to router
j.
 The best link is (i,k) such that Xik+Xkj is
minimum among all adjacent routers.
(C) All rights reserved by Professor Wen-Tsuen Chen
16
(C) All rights reserved by Professor Wen-Tsuen Chen
17
The Count-to-Infinity Problem (cont.)
(C) All rights reserved by Professor Wen-Tsuen Chen
18
The Count-to-Infinity Problem



The distance vector algorithm reacts rapidly to good
news, but leisurely to bad news. In Fig. 5-11(a), A is
down initially and them comes up. In Fig. 5-11(b), A
goes down.
Due to its slow convergence, it is usually used in
small networks.
In RIP, the metric of distance is hop counts. A finite
limit of hops (15) is used, after which a route is
considered unreachable.
(C) All rights reserved by Professor Wen-Tsuen Chen
19
Link State Routing



First used in ARPANET since 1979.
Used in IS-IS (Intermediate System - Intermediate
System), which was designed for DECnet and
later adopted by ISO for the connectionless
network layer protocol CLNP. IS-IS is also used in
IP, CDPD, IPX.
Also used in OSPF (Open Shortest Path First)
interior routing protocol.
(C) All rights reserved by Professor Wen-Tsuen Chen
20
Routing Algorithm
For each router:
Step 1. Discover its neighbors and learn their network
addresses.
Step 2. Measure the delay or cost to each of its neighbors.
Step 3. Construct
a link state packet.
(C) All rights reserved by Professor Wen-Tsuen Chen
21
Step 4. Broadcast the link state packet to all other
routers




Sequence number: For discarding duplicates
Age: Decreased once per second and discarded if the age hits
zero. When a router is down, its link state packet will age out.
Send flags: The packet must be sent on the indicated line.
Acknowledgement flags: It must be acknowledged at the
indicated routers.
(C) All rights reserved by Professor Wen-Tsuen Chen
22
Step 5. Construct a new routing table



Once the router has a full set of link state packets,
it knows all the link states in the network.
Use Dijkstra’s algorithm to compute the shortest
path to all possible destinations.
Update the routing table.
(C) All rights reserved by Professor Wen-Tsuen Chen
23
Hierarchical Routing

To avoid router routing tables grow too large as networks
grow in size.
(C) All rights reserved by Professor Wen-Tsuen Chen
24
Autonomous Systems in the Internet




An autonomous system is a set of routers having a single routing
policy, running under a single technical administration.
Interior Gateway Protocol vs.Exterior Gateway Protocol.
BGP4 is the de facto standard for exterior gateway protocol in the
Internet.
The main goal of an interior gateway protocol is to route efficiently,
while the exterior gateway protocols have to worry about “politics”.
(C) All rights reserved by Professor Wen-Tsuen Chen
25
Routing for Mobile Hosts

Mobility Support
(C) All rights reserved by Professor Wen-Tsuen Chen
26
Broadcast Routing


Flooding
Multi-destination routing
Each packet contains a list of desired destinations.
 When a packet arrives, the router checks all the
destinations to determine the set of output lines for
forwarding the packet. An output line is selected if it is
the best route to at least one of the destinations.
 The router generates a new copy of the packet for
selected output line, with a set of destinations that are to
use the line.

(C) All rights reserved by Professor Wen-Tsuen Chen
27
Spanning Tree Routing
Assume each router has knowledge of a
spanning tree (e.q. a sink tree) in the
network.
 Each router copies an incoming broadcast
packet onto all the spanning tree lines
except the one it arrives on.
 Use minimum number of packets.

(C) All rights reserved by Professor Wen-Tsuen Chen
28
Reverse Path Forwarding
H
(C) All rights reserved by Professor Wen-Tsuen Chen
29



No knowledge of a spanning tree.
When a broadcast packet arrives at a router, on the
line that is normally used for sending packets to
the source of the broadcast (It is very likely that
this is the first copy to arrive at the router).
If so, forward the packet onto all lines except the
one it arrived on; otherwise, discard it as a likely
duplicate.
(C) All rights reserved by Professor Wen-Tsuen Chen
30
Multicast Routing




Each router computes a spanning tree covering all
other routers in the subnet.
When a multicast packet for a group arrives, the
first router examines its spanning tree and prunes
it, removing all lines that do not lead to hosts in
the group.
Multicast packets are forwarded only along the
pruned tree.
For a network of n groups, each with an average
of m members, nm trees must be stored.
(C) All rights reserved by Professor Wen-Tsuen Chen
31
(C) All rights reserved by Professor Wen-Tsuen Chen
32
Core-base Tree for Multicast Routing




A spanning tree for a group, with the root ( the
core) near the middle of the group.
To send a multicast packet, send it to the core,
which then does the multicast along the spanning
tree.
The tree is not optimal. However only n trees need
to be stored.
RFC 2189 , 2201.
(C) All rights reserved by Professor Wen-Tsuen Chen
33
Congestion Control
(C) All rights reserved by Professor Wen-Tsuen Chen
34
Policies that Affect Congestion
(C) All rights reserved by Professor Wen-Tsuen Chen
35
Congestion Control Schemes

Traffic Shaping
 Forcing
the packets to transmitted at a more
predicatable rate.

Admission Control
 usually
used in virtual circuit subnets, such as ATM
networks.
 A virtual circuit is admitted only when it will not cause
congestion.
(C) All rights reserved by Professor Wen-Tsuen Chen
36
Congestion Control Schemes (cont.)

Choke Packets




If congested, the router sends a choke packets back to
the source, with the packet destination.
When the source gets the choke packet, it is required to
reduce the traffic send to the specified destination by a
certain percent.
Load shedding
Drop packets when routers are over drown.
(C) All rights reserved by Professor Wen-Tsuen Chen
37
Internetworking





Repeaters
Bridges
Multiprotocol Routers
Transport gateways
Application gateways
(C) All rights reserved by Professor Wen-Tsuen Chen
38
(C) All rights reserved by Professor Wen-Tsuen Chen
39
(C) All rights reserved by Professor Wen-Tsuen Chen
40
Two Styles of Internetworking
(C) All rights reserved by Professor Wen-Tsuen Chen
41
(C) All rights reserved by Professor Wen-Tsuen Chen
42
Tunneling Packets

Using encapsulation of IP packets
(C) All rights reserved by Professor Wen-Tsuen Chen
43
Internetwork Routing

Interior gateway protocol vs. Exterior gateway
protocol
(C) All rights reserved by Professor Wen-Tsuen Chen
44
Fragmentation

IP protocol uses nontransparent fragmentation scheme.
(C) All rights reserved by Professor Wen-Tsuen Chen
45
Firewalls


Packet filter router is a router equipped with some extra functionality that allows
every incoming or outgoing packet to be inspected.
Application gateway (e.g.a mail gateway) may examine headers and/or contents of
messages.
(C) All rights reserved by Professor Wen-Tsuen Chen
46
The Network Layer in the Internet
(C) All rights reserved by Professor Wen-Tsuen Chen
47
(C) All rights reserved by Professor Wen-Tsuen Chen
48
The IP Protocol




IHL: Header length in 32 bit words.
Type of Service: Contains three-bit precedence field (packet priority), three flags, D(delay),
T(throughput),and R(reliability), and 2 unused bits.
Total length: Length of header plus data with the maximum length 64K bytes.
Identification: To identify a datagram that the fragment belongs to.
(C) All rights reserved by Professor Wen-Tsuen Chen
49







DF: Don’t fragment.
MF: More fragment.
Fragment Offset: Position of the fragment in the datagram.All fragments
except the last one must be a multiple of 8 bytes.
Time to live: Packet lifetimes in seconds. Decremted on each hop and in
queue in a router.
Protocol: Indicate the transport process that a datagram is given to.
Header checksum: One’s complement computation on the header.
Source address and Destination address indicate the network number and
host number.
(C) All rights reserved by Professor Wen-Tsuen Chen
50
Options
(C) All rights reserved by Professor Wen-Tsuen Chen
51
IP Addressing



Network numbers are assigned by the NIC (Network Information Center) to avoid conflicts.
NIC: InterNIC in US, RIPE in Europe,and APNIC (in Asia Pacific rim).
Each router only has to keep track of other network and local hosts , not(network,host)
pairs,greatly reducing the size of its routing table.
(C) All rights reserved by Professor Wen-Tsuen Chen
52
(C) All rights reserved by Professor Wen-Tsuen Chen
53
Subneting


Splitting a network into several subnets for internal use, but the
network acts as a single network to the outside world.
To reduce the size of the routing tables. An entry in a routing table is
of the form(this-network, subnet, 0) and (this-network, this-subnet,
host).
(C) All rights reserved by Professor Wen-Tsuen Chen
54
Number of routes in the internet
50,000
42,000
40,000
Routing Table Growth
34,000
30,000
20,500
20,000
8,500
10,000
350
0
88
92
94
95
(C) All rights reserved by Professor Wen-Tsuen Chen
96
55
CIDR:Classless Inter-Domain Routing




To solve the IP address depletion problem and the routing table
explosion problem
RFC 1519
The Basic idea behind CIDR is to allocate the remaining class C
networks in variable size blocks
The world was partitioned into zones, each given a portion of the class
C address space:
Addresses 194.0.0.0 to 195.255.255.255 for Europe
Addresses 196.0.0.0 to 197.255.255.255 for Others
Addresses 198.0.0.0 to 199.255.255.255 for North America
Addresses 200.0.0.0 to 201.255.255.255 for Central and South America
Addresses 202.0.0.0 to 203.255.255.255 for Asia and Pacific
Addresses 204.0.0.0 to 207.255.255.255 for Others
Addresses 208.0.0.0 to 223.255.255.255 reserved for future use
(C) All rights reserved by Professor Wen-Tsuen Chen
56
The address entry in a CIDR routing table contains a base address and
a variable length mask.For example 2048 addresses from 194.24.0.0
to 194.24.7.255

base address:
11000010 00011000 00000000 00000000
mask:
11111111 11111111 11111000 00000000
ie. 194.24.0.0 255.255.248.0 or 194.24.0.0/21

(C) All rights reserved by Professor Wen-Tsuen Chen
57
Prefix length
Prefix
0
8
16
24
Class C: 198.32.1.0
11000110 00100000 00000001 00000000
Mask 255.255.255.0
Mask 255.255.0.0
11111111 11111111 11111111 00000000
11111111 11111111 00000000 00000000
Supernet
Natural mask
198.32.1.0 255.255.255.0 <==> 198.32.1.0/24
198.32.0.0 255.255.255.0 <==> 198.32.0.0/16
A network is called a supernet when the prefix boundary contains fewer bits
than the network’s natural mask.
(C) All rights reserved by Professor Wen-Tsuen Chen
58
IP Address Allocation





Class A address allocation is restricted.
Class B address are also restricted .They will be allocated
only if the need for them is justified.
class C addresses are allocated with a contiguous block of
addresses which consists of several contiguous class C
addresses.Class C addresses are being distributed to ISPs
so that the allocation could last at least two years.
If a subscriber has a requirement for more than 4096 IP
address, a Class B network number may be allocated.
Organizations are encouraged to use Variable Length
Subnet Mask for efficient use of address space.
(C) All rights reserved by Professor Wen-Tsuen Chen
59
Internet Control Protocols
 ICMP(Internet Control Message Protocol)
 RFC 792

ARP(Address Resolution Protocol)



RARP




RFC 826
For an IP address , find its hardware address.
RFC 903
For a hardware address , find its IP address.
RARP server is needed on each network.
Bootp

RFC 951,1048,1084….
(C) All rights reserved by Professor Wen-Tsuen Chen
60
Internet Control Message Protocol

To report unexpected events or test the Internet
(C) All rights reserved by Professor Wen-Tsuen Chen
61
(C) All rights reserved by Professor Wen-Tsuen Chen
62
RARP:Reverse Address Resolution Protocol
Allow a newly-booted (diskless)
workstation (with a DLL address) to
discover its IP address
 Need a RARP server on each network
 Bootp:

 Use
UDP messages which are forwarded over
routers to find the file server that holds the
mapping
(C) All rights reserved by Professor Wen-Tsuen Chen
63
ARP: Address Resolution Protocol




To map an IP address onto data link layer address , such
as Ethernet.
An IP host runs the ARP protocol to inquiry the unknown
data link layer address of a destination IP address before
a datagram is sent.
The ARP of a host may maintain a cache to record known
IP address and DLL address pairs.
The ARP may broadcast its own mapping when it boots.
(C) All rights reserved by Professor Wen-Tsuen Chen
64