Transcript INTERNETWORK

INTERNETWORK
SIMPLE INTERNETWORKING
INTERNETWORK
 Internetwork
or “internet” refers to an
arbitrary collection of network
interconnected to provide some sort of
host-to-host packet delivery service
 Internet is different from internet
 Also called “network of networks”  made
up of lots smaller networks
 Device: router or gateway
 used to interconnect the networks
SIMPLE INTERNETWORK
Host1
Host2
Host3
Host8
Net1 : Ethernet
Host4
Host9
Host10
Net4 : Ethernet
Router1
Router3
Net2 : Token-ring
Net3 : Pointto-point
Router2
Host5
Host6
Host7
Host11
SIMPLE INTERNETWORK
Protocol layers used to connect Host 3 to Host 9:
 ETH  Ethernet
 TR  Token Ring
 P2P  Point to Point
H3
H9
TCP
TCP
R1
IP
ETH
R2
IP
ETH
R3
IP
TR
TR
IP
P2P
P2P
IP
ETH
ETH
SERVICE MODEL
Packet Delivery Model
 Connectionless (datagram-based)
 Best-effort delivery (unreliable service)




packets are lost
packets are delivered out of order
duplicate copies of a packet are delivered
packets can be delayed for a long time
IPv4 Header: 192 bits (24 bytes)
DATAGRAM FORMAT (IPV4)
Version (4): currently 4
 Hlen (4): number of 32-bit words in header
 TOS (8): type of service (not widely used)
 Length (16): number of bytes in this datagram
 Ident (16): used by fragmentation
 Flags/Offset (16): used by fragmentation
 TTL (8): number of hops this datagram has travelled
 Protocol (8): demux key (TCP=6, UDP=17)
 Checksum (16): of the header only
 DestAddr & SrcAddr (32)

FRAGMENTATION & REASSEMBLY
 Each
network has some MTU
(Maximum Transfer Unit)
 Strategy
fragment when necessary (MTU < Datagram)
 try to avoid fragmentation at source host
 refragmentation is possible
 fragments are self-contained datagrams
 delay reassembly until destination host
 do not recover from lost fragments

EXAMPLE
H3
ETH
R1
IP
(1400)
R2
TR
IP
(1400)
R3
H9
P2P
IP
(512)
ETH
IP
(512)
P2P
IP
(512)
ETH
IP
(512)
P2P
IP
(376)
ETH
IP
(376)
Start of Header
a)
Ident = x
0
Offset = 0
Rest of Header
1400 Data bytes
Start of Header
b)
Ident = x
1
Offset = 0
Start of Header
Ident = x
1
Offset = 512
Start of Header
Ident = x
0
Offset = 1024
Rest of Header
Rest of Header
Rest of Header
512 Data bytes
512 Data bytes
376 Data bytes
GLOBAL ADDRESSES
 Properties
globally unique
 hierarchical: network + host
 Format
7
24

0
1
1
 Dot
Network Id
0
1
0
Host Id
14
16
Network Id
Host Id
21
8
Network Id
Host Id
notation
10.3.2.4 ; 128.96.33.81 ; 192.12.69.77
DATAGRAM FORWARDING
Strategy
 every datagram contains destination's
address
 if directly connected to destination
network, then forward to host
 if not directly connected to destination
network, then forward to some router
 forwarding table maps network number
into next hop
 each host has a default router
 each router maintains a forwarding table
EXAMPLE (ROUTER R2)
Host1
Host2
Host3
Host8
Net1 : Ethernet
Host4
Router3
Net2 : Token-ring
Next_Hop
1
Router1
2
Interface 0
3
Interface 1
4
Router3
Host10
Net4 : Ethernet
Router1
Network
Number
Host9
Net3 : Pointto-point
Router2
Host5
Host6
Host7
Host11
GLOBAL INTERNET
Scalability Issues
 IP “hides” hosts in address hierarchy, but...
 Inefficient use of address space
class C network with 2 hosts (2/255 = 0.78% efficient)
 class B network with 256 hosts (256/65535 = 0.39%
efficient)

 Too
many networks
today's Internet has tens of thousands of networks
 routing tables do not scale
 route propagation protocols do not scale

ADDRESS TRANSLATION
Map IP addresses into physical addresses
 destination host
 next hop router
Techniques
 encode physical address in host part of IP address
 table-based
ARP
 table of IP to physical address bindings
 broadcast request if IP address not in table
 target machine responds with its physical address
 table entries are discarded if not refreshed
• table entries timeout in about 10 minutes
ARP OPERATION
ICMP
IP protocol is best-effort delivery service
 It has 2 deficiencies:

Lack of error controls (no error-correcting)
 Lack of assistance mechanisms (no error-reporting)

A host needs to determine if a another node is
alive  use ICMP
 ICMP is a companion to the IP protocol


Error Reporting messages :
 Destination unreachable
 Source quench
 Time exceeded
 Redirection
• Query :
– Echo request or reply
– Timestamp request and reply
– Address mask request
and reply
– Router solicitation and
advertisement
DYNAMIC HOST CONFIGURATION
PROTOCOL (DHCP)
Extension of BOOTP, and its compatible
 DHCP provides temporary IP addresses for a limited
period of time
 DCHP has 2 database:

1.
2.
Database that binds physical @ with IP @
Database with pool of available IP @
SUBNETTING
 Add
another level to address/routing
hierarchy: subnet
 Subnet masks define variable partition of host
part of class A and B addresses
 Subnets visible only within site
Network Id
Host Id
111111111111111111111111
00000000
Network Id
Subnet Id
Host Id
16
8
8
SUBNET EXAMPLE
Subnet mask : 255.255.255.128
Subnet number : 135.50.21.0
Subnet mask : 255.255.255.0
Subnet number : 135.50.45.0
135.50.21.1
135.50.45.1
Router1
Router2
135.50.21.130
Host1
135.50.50.33
135.50.21.129
Host2
135.50.21.139
Subnet mask : 255.255.255.128
Subnet number : 135.50.21.128
Host3
SUBNET EXAMPLE
 Forwarding
table at router R1
Subnet number
Subnet mask
Next_Hop
135.50.21.0
255.255.255.128
Interface 0
135.50.21.128
255.255.255.128
Interface 1
135.50.45.0
255.255.255.0
Router2
FORWARDING ALGORITHM
D = destination IP address
for each entry < SubnetNum, SubnetMask, NextHop>
D1 = SubnetMask & D
if D1 = SubnetNum
if NextHop is an interface
deliver datagram directly to destination
else
deliver datagram to NextHop (a router)
Notes:



Would use a default router if nothing matches
Can put multiple subnets on one physical network
Subnets not visible from the rest of the Internet
SUPERNETTING
 Assign
block of contiguous network numbers to
near-by networks
 Called CIDR: Classless Inter-Domain Routing
 Represent blocks with a single pair
<first_network_address, count>
 Restrict block sizes to powers of 2
 Use a bit mask (CIDR mask) to identify block
size
 All routers must understand CIDR addressing
ROUTE PROPAGATION
 Idea:
Impose a second hierarchy on the network that
limits what routers talk to each other.
(The first hierarchy is the address hierarchy that
governs how packets are forwarded.)
 Autonomous System (AS)
 corresponds to an administrative domain
 examples: University, company, backbone
 assign each AS a 16-bit number
network
 Two-level route propagation hierarchy
 interior gateway protocol (each AS selects its own)
 exterior gateway protocol (Internet-wide standard)
INTRA AS
ROUTING
Forwarding versus Routing

forwarding: to select an output port based on
destination address and routing table

routing: process by which routing table is
built
NETWORK AS A GRAPH
D
3
4
6
B
1
F
A
1
9
C
2
1
E
Problem: Find the lowest cost path between any
two nodes
ROUTING PROTOCOL
Factors:

Static: topology

Dynamic: load
Classes:

Distance Vector

Link State
DISTANCE VECTOR
Each node maintains a set of triples:
(Destination, Cost, NextHop)

Each node sends updates to (and receives updates
from) its directly connected neighbors



Each update is a list of pairs:
(Destination, Cost)

Update local table if receive a “better” route




periodically (on the order of several seconds)
whenever its table changes (called triggered update)
smaller cost
came from next-hop
Refresh existing routes; delete if they time out
D
F
C
EXAMPLE
B
E
A
G
Distance to reach node
Information at
node
A
B
C
D
E
F
G
A
0
1
∞
∞
1
∞
∞
B
1
0
1
1
∞
1
∞
C
∞
1
0
∞
∞
∞
∞
D
∞
1
∞
0
∞
1
∞
E
1
∞
∞
∞
0
∞
1
F
∞
1
∞
1
∞
0
1
G
∞
∞
∞
∞
1
1
0
D
F
C
…. CONT’D
B
E
G
Distance to reach node
A
Information at node
A
B
C
D
E
F
G
A
0
1
2
2
1
2
2
B
1
0
1
1
2
1
2
C
2
1
0
2
3
2
3
D
2
1
2
0
3
1
2
E
1
2
3
3
0
2
1
F
2
1
2
1
2
0
1
G
2
2
3
2
1
1
0
TOPOLOGY CHANGES
D
F
C
B
E
A
G
Example 1
 A detects that link to E has failed
 A sets distance to E to infinity and
sends update to B
 B sets distance to E to infinity
since it uses A to reach E
 B receives periodic update from F
with 2-hop path to E
 B sets distance to E to 3 and sends
update to A
 A decides it can reach E in 4 hops
via B
ROUTING LOOPS
….CONT’D
D
F
C
B
E
A
G
Example 2:
 Link from B to C fails
 B advertises distance of
infinity to C
 D and F advertise a distance
of 2 to C
 D decides it can reach C in 3
hops; advertises this to B
 B decides it can reach C in 4
hops; advertises this to F
 F decides that it can reach C
in 5 hops......
ROUTING LOOPS
….CONT’D
Heuristics to break routing loops:

set infinity to 16

split horizon

split horizon with poison reverse

hold-down timer
LINK STATE
 Strategy:
Send to all nodes (not just neighbors)
information about directly connected links (not
entire routing table).
 Link
State Packet (LSP)
id of the node that created the LSP
 cost of link to each directly connected neighbor
 sequence number (SEQNO)
 time-to-live (TTL) for this packet

LINK STATE
…CONT’D
Reliable Flooding:





store most recent LSP from each node
forward LSP to all nodes but one that
sent it
generate new LSP periodically;
increment SEQNO
start SEQNO at 0 when reboot
decrement TTL of each stored LSP;
discard when TTL=0
LINK STATE
…CONT’D
Route Calculation (in theory)
 Dijkstra's shortest path algorithm
 N denotes set of nodes in the graph
 l(i,j) denotes non-negative cost (weight)
for edge (i,j)
 s in N denotes this node
 M denotes the set of nodes incorporated
so far
 C(n) denotes cost of the path from s to
node n
DIJKSTRA'S ALGORITHM
M = {s}
for each n in N - {s}
C(n) = l(s,n)
while (N ≠ M)
M = M  {w} such that C(w)
is the minimum for all w in (N-M)
for each n in (N-M)
C(n) = MIN (C(n), C(w)+l(w,n))
LINK STATE
Route Calculation (in practice)
Forward search algorithm
 Each switch maintains two lists:

Tentative and Confirmed

Each list contains a set of triples:
(Destination, Cost, NextHop)
FORWARD SEARCH ALGORITHM
1. Initialize Confirmed with entry for me; cost = 0.
2. For the node just added to Confirmed (call it Next)
select its LSP.
3. For each Neighbor of Next, calculate the Cost to
reach this Neighbor as the sum of the cost from
me to Next and from Next to Neighbor
3.1. If Neighbor is currently in neither Confirmed or
Tentative, add (Neighbor, Cost, NextHop) to
Tentative, where NextHop is the direction to reach
Next.
3.2. If Neighbor is currently in Tentative and Cost is
less that current cost for Neighbor, then replace current
entry with (Neighbor, Cost, NextHop), where
NextHop is the direction to reach Next.
4. If Tentative is empty, stop. Otherwise, pick entry
from Tentative with the lowest cost, move it to
Confirmed, and return to step 2.
EXAMPLE:
B
5
3
A
10
D
11
2
C
Langkah-langkah pembentukan tabel ruting untuk node C:
Step
Confirmed
1
(C,0,-)
Tentative
Comments
Karena C merupakan satu-satunya anggota baru
dari Confirmed, maka dilihat LSP-nya
(C,0,-)
(B,11,B)
(D,2,D)
LSP dari C menyatakan bahwa B dapat dicapai
melalui B dengan biaya 11, yang lebih baik (kecil)
dibanding entri lain dalam list sehingga
dimasukkan dalam Tentative. Hal yang sama juga
berlaku untuk D
(B,11,B)
3
(C,0,-)
(D,2,D)
Masukkan entri Tentative dengan biaya terkecil (D)
ke Confirmed. Kemudian lihat LSP dari anggota
Confirmed yang baru tersebut (D)
4
(C,0,-)
(D,2,D)
(B,5,D)
(A,12,D)
Biaya untuk mencapai B melalui D adalah 5,
sehingga entri (B,11,B) digantikan oleh (B,5,D).
LSP dari C juga memberikan informasi bahwa A
dapat dicapai dengan biaya 12.
(A,12,D)
5
(C,0,-)
(D,2,D)
(B,5,D)
Pindahkan anggota Tentative dengan biaya terkecil
(B) ke Confirmed, kemudian lihat LSP-nya
(A,10,D)
6
(C,0,-)
(D,2,D)
(B,5,D)
Karena A dapat dicapai dengan biaya 5 dari B
maka entri dari Tentative di-update
7
(C,0,-)
(D,2,D)
(B,5,D)
(A,10,D)
2
Pindahkan anggota Tentative dengan biaya terkecil
(A) ke Confirmed. Karena Tentative telah kosong
(jalur terbaik ke seluruh node telah diketahui)
maka eksekusi algoritma selesai
INTER AS
INTER AND INTRA AS
EGP: EXTERIOR GATEWAY PROTOCOL
Overview
 designed for tree-structured Internet
 concerned with reachability, not optimal routes
Protocol messages
 neighbor acquisition: one router requests that another
routers could be its peer; peers exchange reachability
information
 neighbor reachability: one router periodically tests to
see if the other router is still reachable; exchange
HELLO/ACK messages;
 routing updates: peers periodically exchange their
routing tables (similar to distance-vector)
Formal specification : RFC-904
BGP-4: BORDER GATEWAY PROTOCOL
Assumes the Internet is an arbitrarily interconnected
set of AS's.
 Define local traffic as traffic that originates at or
terminates on nodes within an AS, and transit traffic as
traffic that passes through an AS
 We can classify AS's into three types:

Stub AS: an AS that has only a single connection to one
other AS; such an AS will only carry local traffic.
 Multi-homed AS: an AS that has connections to more
than one other AS, but refuses to carry transit traffic.
 Transit AS: an AS that has connections to more than one
other AS, and is designed to carry both transit and local
traffic.

BGP-4: BORDER GATEWAY PROTOCOL

Each AS has:
One or more border routers
 One BGP speaker that advertises:

local networks
 other reachable networks (transit AS only)
 gives path information


BGP-4 : RFC-1771
BGP EXAMPLE
Customer A
(AS 4)
128.96
192.4.153
Customer B
(AS 5)
192.4.32
192.4.3
Customer C
(AS 6)
192.12.69
Customer D
(AS 7)
192.4.54
192.4.23
Provider X
(AS 2)
Backbone
(AS1)
Provider Y
(AS 3)



Speaker for AS 2 advertises reachability to A and B
Network 128.96, 192.4.153, 192.4.32, and 192.4.3, can be reached
directly from AS 2.
Speaker for backbone network then advertises
Networks 128.96, 192.4.153, 192.4.32, and 192.4.3 can be reached
along the path <AS 1, AS 2>.
Speaker can also cancel previously advertised paths
EXERCISE
 Suppose
a TCP message that contains 2028
bytes of data and 20 bytes of TCP header is
passed to IP for delivery across two networks
of the Internet. The first network uses 14
bytes headers and has an MTU of 1024 bytes;
the second uses 8-byte header with an MTU
of 512. Each network’s MTU gives the sizes of
largest IP datagram that can be carried in a
link-layer frame. Give the sizes and offsets of
the sequence of fragment delivered to the
network layer at the destination host.
Assume all IP headers are 20 bytes.
REFERENCES
1.
2.
Peterson, Larry L. Computer Networks: A
Systems Approach. 5th edition. Morgan
Kaufmann.
Forouzan, Behrouz A. TCP/IP Protocol Suite.
Mc Graw Hill.