Transcript Ch4. Network Layer and Routing

Hierarchical routing

Two issues in practice
–
–




Scale
Administrative autonomy
Autonomous system (AS) or region
Intra autonomous system routing protocol
Gateway routers
Inter-autonoumous system routing protocol
1

Fig 4.11
2
The Internet Protocol (IP)

Fig 4.13

IPv4, IP version 6
Internet Control Message Protocol (ICMP)

3

IPv4 addressing
–
–
–
–
–
An IP address is associated with an interface rather than with the host
or router containing the interface.
32 bits long
Dotted-decimal notation (pp. 322)
Fig 4.14
223.1.1.0/24 where /24 -> a network mask, network prefix, an IP
network, a network
4

Fig 4.15
5




Classful addressing: A, B, C, D
Fig 4.17
Classless Interdomain Routing (CIDR): e.g., a.b.c.d/21 for 2000
hosts
Corporation for Assigned Names and Numbers (ICANN)
–
–
–
–
Allocate IP address
Manage the DNS root servers
Assign domain names
Resolve domain name disputes
6

Obtaining a host address
–
–
Manual configuration
Dynamic Host Configuration Protocol (DHCP)
7
8
Addressing, Routing, and Forwarding

Fig 4.21
9

Fig 4.22
10
IPv4 datagram format

Fig 4.23

Type of service: differentiated service (e.g., Cisco)
IPv6: no fragmentation at routers
Why does TCP/IP perform error checking at the both layers?
IP options were dropped in the IPv6 header.



11
IP datagram fragmentation



MTU(max transfer unit): max amount of data that a link-layer
packet can carry, e.g., 1,500 bytes for Ethernet, 576 bytes for
wide-area links
Fragment
The designers of IPv4 decided to put the job of datagram
reassembly in the end systems rather than in network routers.
12

Fig 4.24
13

Table 4.3
14
ICMP



Error reporting
Above IP
Fig 4.25
15
DHCP

For a newly arriving host, the DHCP does
–
–
–
–

DHCP server discovery: broadcasting
DHCP server offer(s): the proposed IP address for the client, the
network mask, and an IP address lease time
DHCP request
DHCP ACK
From a mobility aspect, how about DHCP?
16

Fig 4.27
17
Network Address Translators (NATs)



The NAT-enabled router does not run an Inter-AS routing
protocol.
The NAT-enabled router behaves to the outside world as a
single device with a single IP address. (port numbers)
Fig 4.28
18
Routing in the Internet


Intra-AS routing: RIP and OSPF
Routing Information Protocol
–
–
–
–

Distance vector protocol
Hop count as a cost metric
Max cost of a path: 15
Every 30 seconds for RIP advertisements
Open Shortest Path First
–
–
–
Link state protocol
Once every 30 minutes
Adv.: security, multiple same-cost paths, integrated support for
unicast and multicast routing, and support for hierarchy within a
single routing domain.
19

Fig 4.35
20

Inter-AS routing: BGP
–
–
–
–
Path vector protocol
Exchange path information than cost information
Routing policy
On TCP
21
Router

Fig 4.38 (router arch)

Fig 4.39 (input port)
22

Given the need to operate at today’s high link speeds, a number
of ways to find out an appropriate forwarding table entry.
–
–
–
–
A linear search
Store the forwarding table entries in a tree data structure
Content addressable memories
Forwarding table entries in a cache
23

Fig 4.40 (switching fabric)
24

Fig 4.41 (output ports)

Packet queues at both the input ports and the output ports ->
packet loss depending on the traffic load, the relative speed of
the switching fabric, and the line speed.
25

Fig 4.42

Packet scheduler: choose one packet among queued for
transmission
–
–
–
First-come-first-served (FCFS) scheduling
Weighted fair queueing (WFQ)
Important for quality-of-service guarantees.
26



Drop a packet before the buffer is full in order to provide a
congestion signal to the sender -> active queue management
(Random Early Detection (RED))
Head-of-the-line (HOL) blocking in an input-queued switch
Fig 4.43
27
IPv6

Changes in IPv6
–
–
–
–
Expanded addressing capabilities (32 to 128 bits), anycast address
A streamlined 40-byte header
Flow labeling and priority
Fig 4.44
28

IPv6 vs IPv4
–
–
–

ICMP for IPv6
–
–

Fragmentation/reassembly: IPv6 does not allow for fragmentation
and reassembly at intermediate routers.
Header checksum: IPv4 header checksum needed to be
recomputed at every router.
Options: next headers pointer in IPv6
Packet too big, unrecognized IPv6 options error codes
IGMP
Transitioning from IPv4 to IPv6
–
–
–
Flag day
Dual-stack: DNS to determine whether another node is IPv6 or IPv4
Tunneling
29

Fig 4.45

Fig 4.46
30
Multicast routing




Unicast vs multicast
The sending of a packet from one sender to multiple
receivers with a single send operation.
Network-layer aspects of multicast
Handle multicast groups
–
–
–

How to identify the receivers of a multicast datagram?
–

One-to-all unicast
Application-level multicast
Explicit multicast at the network layer
Address indirection: a single identifier is used for the group
of receivers -> class D
How to address a datagram sent to these receivers?
31

Fig 4.47
32

Fig 4.48
33

IGMP
–
–
–
–

Network-layer multicast algorithms (PIM, DVMRP, MOSPF)
–

Group membership protocol
Locally between a host and an attached router
Means for a host to inform its attached router that an application
running one the host wants to join a specific multicast group
Joining a multicast group is receiver-driven
Coordinate the multicast routers so that multicast datagrams are
routed to their final destinations
Table 4.4
34

Fig 4.50
35

Fig 4.51
36
Multicast routing: the general case


The goal of multicast routing is to find a tree of links
that connects all of the routers that have attached
hosts belonging to the multicast group.
Fig 4.52
37


Two approaches: whether a single “group-shared” tree is used
to distribute the traffic for all senders in the group, or whether a
source-specific routing tree is constructed for each individual
sender.
Fig 4.53
38

Multicast routing using a group-shared tree
–
Fig 4.54
–
Steiner tree problem: None of the existing Internet multicast
routing algs has been based on this approach: information about
all links is needed, rerun whenever link costs change and
performance.
Center-based approach: center node, rendezvous point or core:
how to select the center
–
39

Multicast routing using a source-based tree
–
–
–
Reverse path forwarding (RPF)
Fig 4.56
If there were thousands of routers downstream from D, … ->
pruning
40
Multicast routing in the Internet

DVMRP: Distance Vector Multicast Routing Protocol
–
–
–
Source-based trees with reverse path forwarding and
pruning
Small fraction of the Internet routers are multicast-capable > Tunneling, e.g., Mbone
Fig 4.57
41
Multicast routing in the Internet

PIM: Protocol Independent Multicast
–
–
–
–


Dense mode: a flood-and-prune reverse path forwarding
Sparse mode: a center-based approach
The ability to switch from a group-shared tree to a sourcespecific tree after joining the rendezvous point.
UUNet
Multicast Open Shortest Path First (MOSPF)
DVMRP has been the de facto inter-AS multicast
routing protocol
42
Mobility and the Network layer

An Internet application needs to know the IP address
and port number of the remote entity with which it is
communicating.
Fig 4.58

Ad hoc networking

43

Figure 4.59
44

Indirect routing to a mobile node
–
–
–
Triangle routing problem
Encapsulation/decapsulation = tunneling
Fig 4.60
45
–
Fig 4.61
–
The occasional datagram loss within a connection when a
node moves between networks.
46

Direct routing to a mobile node
–
Fig 4.62
–
GSM
47
Mobile IP




Agent discovery, registration with the home agent,
and indirect routing of datagram
Security: authentication
An agent receiving the solicitation will unicast an
agent advertisement directly to the mobile node.
Fig 4.63
48
–
Fig 4.64
49