Bài giảng Mạng máy tính - Chapter 4: Network Layer (Part II)

IP datagram format

IP protocol version

32 bits

total datagram

length (bytes)

number

header length

(bytes)

type of

service

head.

len

length

ver

for

fragment

“type” of data

fragmentation/

reassembly

flgs

16-bit identifier

offset

max number

remaining hops

(decremented at

each router)

upper

time to

Internet

layer

live

checksum

32 bit source IP address

32 bit destination IP address

Options (if any)

upper layer protocol

to deliver payload to

E.g. timestamp,

record route

taken, pecify

list of routers

to visit.

data

(variable length,

typically a TCP

or UDP segment)

4: Network Layer

4b-1

IP Fragmentation & Reassembly

 network links have MTU

(max.transfer size) - largest

possible link-level frame.

 different link types,

fragmentation:

in: one large datagram

out: 3 smaller datagrams

different MTUs

 large IP datagram divided

(“fragmented”) within net

 one datagram becomes

several datagrams

reassembly

 “reassembled” only at final

destination

 IP header bits used to

identify, order related

fragments

4: Network Layer

4b-2

IP Fragmentation and Reassembly

length ID

=4000 =x

fragflag offset

=0 =0

One large datagram becomes

several smaller datagrams

length ID

=1500 =x

fragflag offset

=1 =0

length ID

=1500 =x

fragflag offset

=1 =1480

length ID

=1040 =x

fragflag offset

=0 =2960

4: Network Layer

4b-3

ICMP: Internet Control Message Protocol

 used by hosts, routers,

Type Code description

gateways to communication

0

3

4

0

1

2

3

6

7

0

echo reply (ping)

network-level information

dest. network unreachable

dest host unreachable

dest protocol unreachable

dest port unreachable

dest network unknown

dest host unknown

source quench (congestion

control - not used)

 error reporting:

unreachable host, network,

port, protocol

 echo request/reply (used

by ping)

 network-layer “above” IP:

 ICMP msgs carried in IP

8

9

0

echo request (ping)

route advertisement

router discovery

datagrams

 ICMP message: type, code plus

first 8 bytes of IP datagram

causing error

10 0

11 0

12 0

TTL expired

bad IP header

4: Network Layer

4b-4

Routing in the Internet

 The Global Internet consists of Autonomous Systems

(AS) interconnected with each other:

 Stub AS: small corporation

 Multihomed AS: large corporation (no transit)

 Transit AS: provider

 Two-level routing:

 Intra-AS: administrator is responsible for choice

 Inter-AS: unique standard

4: Network Layer

4b-5

Internet AS Hierarchy

Intra-AS border (exterior gateway) routers

Inter-AS interior (gateway) routers

4: Network Layer

4b-6

Intra-AS Routing

 Also known as Interior Gateway Protocols (IGP)

 Most common IGPs:

 RIP: Routing Information Protocol

 OSPF: Open Shortest Path First

 IGRP: Interior Gateway Routing Protocol (Cisco

propr.)

4: Network Layer

4b-7

RIP ( Routing Information Protocol)

 Distance vector algorithm

 Included in BSD-UNIX Distribution in 1982

 Distance metric: # of hops (max = 15 hops)

 Can you guess why?

 Distance vectors: exchanged every 30 sec via

Response Message (also called advertisement)

 Each advertisement: route to up to 25 destination

nets

4: Network Layer

4b-8

RIP (Routing Information Protocol)

z

w

x

y

A

D

C

B

Destination Network Next Router Num. of hops to dest.

w

y

z

A

B

2

7

x

--

1

….

....

Routing table in D

4: Network Layer

4b-9

RIP: Link Failure and Recovery

If no advertisement heard after 180 sec -->

neighbor/link declared dead

 routes via neighbor invalidated

 new advertisements sent to neighbors

 neighbors in turn send out new advertisements (if

tables changed)

 link failure info quickly propagates to entire net

 poison reverse used to prevent ping-pong loops

(infinite distance = 16 hops)

4: Network Layer

4b-10

RIP Table processing

 RIP routing tables managed by application-level

process called route-d (daemon)

 advertisements sent in UDP packets, periodically

repeated

4: Network Layer

4b-11

RIP Table example (continued)

Router: giroflee.eurocom.fr

Destination

Gateway

Flags Ref Use Interface

-------------------- -------------------- ----- ----- ------ ---------

127.0.0.1

192.168.2.

193.55.114.

192.168.3.

224.0.0.0

default

127.0.0.1

UH

U

0 26492 lo0

13 fa0

3 58503 le0

192.168.2.5

193.55.114.6

192.168.3.5

193.55.114.6

193.55.114.129

2

3

25 qaa0

0 le0

UG

0 143454

 Three attached class C networks (LANs)

 Router only knows routes to attached LANs

 Default router used to “go up”

 Route multicast address: 224.0.0.0

 Loopback interface (for debugging)

4: Network Layer

4b-12

OSPF (Open Shortest Path First)

 “open”: publicly available

 Uses Link State algorithm

 LS packet dissemination

 Topology map at each node

 Route computation using Dijkstra’s algorithm

 OSPF advertisement carries one entry per neighbor

router

 Advertisements disseminated to entire AS (via

flooding)

4: Network Layer

4b-13

OSPF “advanced” features (not in RIP)

 Security: all OSPF messages authenticated (to

prevent malicious intrusion); TCP connections used

 Multiple same-cost paths allowed (only one path in

RIP)

 For each link, multiple cost metrics for different

TOS (eg, satellite link cost set “low” for best effort;

high for real time)

 Integrated uni- and multicast support:

 Multicast OSPF (MOSPF) uses same topology data base as

OSPF

 Hierarchical OSPF in large domains.

4: Network Layer

4b-14

Hierarchical OSPF

4: Network Layer

4b-15

Hierarchical OSPF

 Two-level hierarchy: local area, backbone.

 Link-state advertisements only in area

 each nodes has detailed area topology; only know

direction (shortest path) to nets in other areas.

 Area border routers: “summarize” distances to nets

in own area, advertise to other Area Border routers.

 Backbone routers: run OSPF routing limited to

backbone.

 Boundary routers: connect to other ASs.

4: Network Layer

4b-16

IGRP (Interior Gateway Routing Protocol)

 CISCO proprietary; successor of RIP (mid 80s)

 Distance Vector, like RIP

 several cost metrics (delay, bandwidth, reliability,

load etc)

 uses TCP to exchange routing updates

 Loop-free routing via Distributed Updating Alg.

(DUAL) based on diffused computation

4: Network Layer

4b-17

Inter-AS routing

4: Network Layer

4b-18

Internet inter-AS routing: BGP

 BGP (Border Gateway Protocol): the de facto

standard

 Path Vector protocol:

 similar to Distance Vector protocol

 each Border Gateway broadcast to neighbors

(peers) entire path (I.e, sequence of ASs) to

destination

 E.g., Gateway X may send its path to dest. Z:

Path (X,Z) = X,Y1,Y2,Y3,…,Z

4: Network Layer

4b-19

Internet inter-AS routing: BGP

Suppose: gateway X send its path to peer gateway W

 W may or may not select path offered by X

 cost, policy (don’t route via competitors AS), loop

prevention reasons.

 If W selects path advertised by X, then:

Path (W,Z) = w, Path (X,Z)

 Note: X can control incoming traffic by controling it

route advertisements to peers:

 e.g., don’t want to route traffic to Z -> don’t

advertise any routes to Z

4: Network Layer

4b-20

Bài giảng Mạng máy tính - Chapter 4: Network Layer (Part II) - Hồ Phương Đắc