Transcript Computer Networks (CS 778)

Computer Networks (CS 778)
Chapter 4, Internetworking


This chapter examines issues of connecting networks together.
We have considered building networks using pt-to-pt links, shared media
and LAN bridges. Now we consider interconnecting different networks.
There are two important problems that must be addressed.

Heterogeneity Users of one type of network want to communicate with users
of another type of network



Scaling: The Internet doubles in size every year.




Possibly having to go through several other types of networks in the process.
The challenge of heterogeneity is to provide a useful and fairly predictable hostto-host service over many different networks.
This causes the routing problem: How can we find efficient loop - free paths
through a network with millions of nodes?
Also there is a unicast and multicast addressing problem - providing suitable
identifiers for all nodes.
We consider a series of approaches to interconnecting networks.
We trace the evolution of the TCP/IP Internet.
Simple Internet Protocol (IP)
How do we go beyond the (scalability) limitations of bridged networks?
(I.e., How do we build inter-networks?)
The terminology we will use is:


H1
Network = directly connected or bridged network (AKA: physical network)
Internetwork = interconnected collection of such networks (AKA: logical network
or network of networks)
H8
TCP
R1
IP
IP
ETH
R2
ETH
IP
FDDI
FDDI
TCP
R3
IP
PPP
PPP
IP
ETH
ETH
Network 1 (Ethernet)
Protocol layers used in
connecting these networks
H7
H2
H1
Routers (aka Gateways) = nodes
interconnecting networks (e.g., R1, R2, R3)
H3
Network 4
(point-to-point)
Network 2 (Ethernet)
IP key tool for scalable, heterogeneous
internetworks (originally: Kahn-Cerf
Protocol after its inventors)
R1
R2
H4
Network 3 (FDDI)
H5
R3
H6
H8
IP Service Model (host-host services over an internet)
IP Service Model can’t guarantee packet delivery within a deadline since the
underlying network technologies can arbitrarily delay packets.
IP philosophy: Be undemanding so any technology in Internet can provide services
IP Service Model has two parts:

An addressing scheme (provides a way to identify all hosts in the internetwork)

A best effort datagram service (connectionless) for data delivery
0
4
8
16
19
31

packets can be lost
TOS
Length
Version HLen

packets can be delivered out of order

packets can be delivered in duplicate
Ident
Flags
Offset

packets can experience long delays
TTL
Protocol
Checksum
Datagram format
SourceAddr

Fields align on 32-bit boundaries
DestinationAddr

Version (specifies which IP version, e.g., IPv4)
Pad
Options (variable)
(variable)

Hlen (length of header in 32-bit words (5 or 6)
Data

TOS (type of service – for requesting some QoS)

Length (length in bytes – max = 216 = 65,535)

The 2nd word is for fragmentation-reassembly

TTL (time-to-live: A hop-count limit used to stop looping packets)

Protocol (demux key; id’s next prot); Checksum (1s-comp sum of 16-bit-header-words)

Addrs (IP defines its own global address space (indep of physical nets); Options (not used)
Fragmentation and Reassembly
Each underlying network has its own max transmission unit (MTU) size
e.g., Ethernet: 1500B; FDDI: 4500B; Wireless (802.11): 2312B, …
Most are shorter than the 65,535B of an IP datagram.
Two choices:
Make maximum IP datagram size small enough to fit in any MTU or provide
Fragmentation & Reassembly. (latter chosen – since new protocols always possible)

When a host sends an IP datagram it can be any size (up to 65,535B).

Strategy
 fragment when necessary (when MTU size is less than Datagram size)
 try to avoid fragmentation at source host (Host chooses a datagram size
which fits the MTU of the first network protocol)
 re-fragmentation is possible (at any router– when In-MTU > Out-MTU)



Each fragment is treated as a self-contained datagrams
use AAL-CS-PDU (not ATM-cells) for ATM
delay reassembly until destination host

if there is a missing fragment, destination gives up on reassembly
Fragmentation &Reassembly
H1
R1
ETH IP (1400)
Start of header
Ident= x
0
Offset= 0
Rest of header
R2
FDDI IP (1400)
R3
H8
PPP IP (512)
ETH IP (512)
PPP IP (512)
ETH IP (512)
PPP IP (376)
ETH IP (376)
1400 data bytes
Assume MTU= 1500B Ethernet; 4500 FDDI; 532 for PPP.
Start of header
Ident= x
1
Offset= 0
Rest of header
512 data bytes
Start of header
Ident= x
1 Offset= 512
Rest of header
512 data bytes
Start of header
Ident= x
0 Offset= 1024
Rest of header
376 data bytes
H1 sends 1420B datagram (20B header + 1400B data) to H8.
Datagram goes thru 1st Ethernet & FDDI without fragmentation.
But is fragmented into 3 datagrams for the PPP network.
each fragment is a self-contained datagram indep of others,
each IP datagram is re-encapsulated for each physical net.
The headers: Flag=1 means there are more fragments to follow.
Offset = how far into packet the 1st fragment byte is.
Addressing example
Application (eg, HTTP) data becomes
TCP payload (TCP discussed in cpt 5,
for now think of it as a
process-to-process transport protocol)
Header contains source and
destination port numbers, since
TCP transports data to processes
at hosts, not just to hosts.
Header contains: source and
destination IP addresses;
Transport layer protocol type
Header contains:
source & destination
physical addresses and Ethernet
network protocol type Header
HTTP Request
TCP
Header
IP
Header
Frame
ChkSum
Globally unique 32-bit IP Addrs (4 3-digit decimals separated by .’s)

IP addresses are hierarchical (which belong to interfaces, not hosts)

Network part (identifies the network; Routers have interfaces on multiple nets)

Host part (identifies each host uniquely within the network)

Different layouts for different size networks (classical scheme: class addresses)
 Class A (for large WANs): ½ of all IP addrs (126 nets (0, 127 reserved), ~2 billion hosts
 Class B (for Campuses): ¼ of all addrs.
Class C (for LANs) 1/8 of all addresses.
 Class D (for specifying multicast grp)
Class E (for experimental or future)
Bit position:
Class A
0 1 2 3
0
1
Class B
8
16
Net ID
Host ID
7
1 0
31
24
Net ID
Host ID
14
Class C
1 1 0
16
Net ID
21
Class D
1 1 1 0
Class E
1 1 1 1
Multicast address
Reserved for experiments
Host ID
8
Datagram Forwarding






Every datagram contains destination’s address
If destination is directly connected to source’s network, it is forwarded directly
If not, forwarded to nexthop router, else forward to default router
forwarding table maps network number into next hop
each host has a default router
each router maintains a forwarding table
Network 1 (Ethernet)
H7
Example (R2 forwarding table):
Network Num. Next Hop
1
R3
2
R1
3
interface 1
4
interface 0
H2
H1
R3
H8
H3
Network 4
(point-to-point)
Network 2 (Ethernet)
R1
Interface 0
R2
Interface 1
H4
Network 3 (FDDI)
Roughly speaking:
Device Level Forwards what?
Bridge
Switch
Router
H5
link
frames
(layer-2 device)
network packets
(layer-2 device)
internet datagrams (layer-3 device)
H6
How is direct forwarding done?? ARP
Address Translation & Address Resolution Protocol (ARP)
We have discussed how to get IP datagrams to the right physical network.
How does datagrams, once on network, get to right node on that network (host/router)?
Datagrams have IP adrs. Physical hardware interfaces have other addrs. (eg, 48-bit Ethernet adr)

In a few nets, physical address is encoded as host-part of IP addr (only possible if format is right).

In most networks, each host/router maintains a table of IP to physical address bindings called
ARP_table or ARP-cache (IP_Addr, Physical_Link_Addr).

One way: Centrally created by a system administrator then copied to each host/router?

Better way: Each host/router dynamically builds table contents using the network.

Mapping changes over time (new Ethernet card or ?), so all entries time-out (eg, ~15 min)
The protocol to build a translation table is called Address Resolution Protocol or ARP
 If an IP address is not in the ARP-cache, host/router broadcast an ARP query.


Has source’s IP and link_adr, so every host/router can enter it (& refresh timeout).
Target machine responds with its physical address
ARP
Request Format





HardwareType: type of physical network (e.g., Ethernet)
ProtocolType: type of higher layer protocol (e.g., IP)
HLEN & PLEN: length of physical and protocol addresses
Operation: request or response
Source/Target-Physical/Protocol addresses
Destination will update sender’s ARP-cache entry (even if it already has an entry for
sender) since sender is likely to be sending a packet soon to which it may need to send
and ACK (and timeout should be avoided as far as possible).
If a node is not the destination and it does not have a sender entry, it does not enter one.
(no reason to clutter cache 0
8
16
31
Since there is no reason to
Hardware type = 1
ProtocolT ype = 0x0800
think a packet is going to
be sent from the sender any
HLen = 48
PLen = 32
Operation
time soon.)
SourceHardwareAddr (bytes 0 – 3)
SourceHardwareAddr (bytes 4 – 5) SourceProtocolAddr (bytes 0 – 1)
SourceProtocolAddr (bytes 2 – 3) TargetHardwareAddr (bytes 0 – 1)
TargetHardwareAddr (bytes 2 – 5)
TargetProtocolAddr (bytes 0 – 3)
Request Format continued
ARP
HardwareType: Physical net type
0
ProtocolType: Higher layer
protocol type (eg IP)
8
16
31
Hardware type = 1
ProtocolType = 0x0800
HLen = 48
PLen = 32
Operation
SourceHardwareAddr (bytes 0– 3)
SourceHardwareAddr (bytes 4– 5) SourceProtocolAddr (bytes 0– 1)
SourceProtocolAddr (bytes 2– 3) TargetHardwareAddr (bytes 0– 1)
TargetHardwareAddr (bytes 2– 5)
TargetProtocolAddr (bytes 0– 3)
HLEN & PLEN: Hardware/Protocol adr lengths
Operation: request or response
Source/Target-Physical/Protocol addresses
H1
H2
150.100.76.20
150.100.76.21
H3
H4
150.100.76.22
150.100.76.23
ARP request (what is the MAC address of 150.100.76.22?)
H1
H2
H3
H4
ARP response (my MAC address is 08-00-5A-C5-3B-94)
IP-over-ATM and ATMARP
R
IP is the dominant internetworking layer, while
12.0.0.3
10.0.0.2
ATM is an economical high-speed backbone.
H1
Great interest in overlaying IP on top of ATM.
10.0.0.1
The only problem in using ARP as defined is
ATM net
that there is no broadcast capability
LIS10 LIS12
Three IP-over-ATM approaches
12.0.0.5
(CLIP, LANE, NHRP)
H2
CLIP (Classical IP over ATM; RFC 2255) (Need efficient broadcast)
Uses the LIS (Logical IP Subnet) abstraction (an ATM ARP Server resides on each LIS)
ATM ARP server builds DB of (IP-addr, ATM-addr) pairs for its LIS; hosts ask for IP-addr)
Allows a large ATM net to be subdivided into smaller nets (so ATM ARP service is efficient)
Nodes on the same subnet have the same IP network-address and send datagrams directly.
Nodes on different subnets have different IP network-address send datagrams through a
router.
IP
Protocol stack change using LANE
MAC
IP
LANE
AAL5
ATM
LANE
LANE (LAN Emulation enables a host to resolve ATM address from MAC address)
LEC: LAN Emulation Client (host, bridge or router)
LECS: LAN Emulation and Configuration Server
(New LEC finds LECS: gets LANE info, frame size, LES address)
LES: LAN Emulation Server
(New LEC sends MAC & ATM address to LES. LES returns the ATM address of the BUS to LEC)
BUS: Broadcast and Unknown Server
(maintains pt-multipt Virtual Connection to all clients for broadcast purposes)
LEC
LES
LEC
ATM network
BUS
LECS
LEC
LEC
NHRP (NextHop Resolution Protocol

Allows host/router to determine the dest ATM address from an IP address in direct manner.

Main objective is to find shortest path through all LISs.


Recall, CLIP ATM ARP severs resolves only ATM address in same LIS (requires router between LISs).
Bascially, in NHRP, an ATM address which is outside the source’s LIS is resolved all the way to the
destination, avoiding CLIP packet forwarding between adjacent LISs.
NHRP uses a client-server approach (NHC-NHS pair replaces ATM ARP Servers):




Next-Hop Clients (NHC) responsible for initiating NHRP resolution, in each LIS
Next-Hop Servers (NHS) responsible for answering NHRP in each LIS
NHCs & NHSs maintiain addr resolution cache or table.
NHRP and CLIP Compared:
LIS1
LIS2
Shortcut path
(NHRP)
ATM network
LIS3
LIS4
LIS5
LIS6
Source
(S)
Destination
(D)
Router
Router
Router
Router
Router
Default path
(CLIP)
More like the virtual Circuit approach (set up a path all the way thru maze of LISs first)
IP basic mechanisms for dealing with
heterogeneity and scale (summary)
Heterogeneity: IP defines a best effort service model making minimal assumptions
about the underlying networks (which is based on unreliable datagrams)
 A common packet format (fragmentation/reassemble used to make it work with
different MTUs.)

A global address space identifying all hosts (ARP makes it work with different
underlying physical addresses)


Scale: IP uses hierarchical aggregation to reduce the amount of information needed to
forward packets.


IP addresses are partitioned into network and host components
 Packets are first routed to the destination network
 Then delivered to the correct host on that network.
DHCP (Dynamic Host Config Protocol)
IP addrs cannot be configured once into a NIC by manufacturer (as in Ethernet)



IP addresses need to be reconfigurable
Also hosts need a default router IP address to send outside their network.


Most O.S.s allow manual configuration of IP info on a host (by user or system admin)
Drawbacks to manual configuration:



host is not reachable until it is configured,
error-prone (maintain uniqueness),
volatility.

Each administrative domain has one DHCP server providing configuration info to hosts.

Instead of sys admin walking around to each host, the DHCP server stores configuration info
from which it is automatically retrieved at host boot or connect time using one of two models:



Sys Adm puts host config info (IP addr, default router..) in DHCP-tbl indexed on, eg, Ethernet-addr).
DHCP server hands out info from a range of configurations on demand (all with same network addr)
Would defeat “automatic” purpose if each host had to be preconfigured with DHCP-server adr.

DHCP-server discovery: (booted/attached host broadcasts DHCPDISCOVER (to 255.255.255.255)



Routers don’t forward (If there is 1 DHCP server for multiple domains – a relay agent router forwards to server
DHCP-server uni-casts a reply to host with IP address
IP addresses are leased from DHCP-Sever (must be renewed before lease expires).
ICMP (Internet Control Message Protocol)
IP may drop datagrams, but a message (NACK) gets sent to host/router on failure (by ICMP).





Destination is unreachable
Reassembly failed
TTL timed out
IP header checksum failed
ICMP also defines control messages (router to host), e.g.,

ICMP-redirect (tells source host that there is a better route to destination)


Used when there is more than one router in network (eg, R1 default and R2 also)
When R1 gets datagram for which it knows R2 would be better choice,
 Sends ICMP-redirect back to sending host, instructing to use R2 in future
for that destination.
 Host then adds this info to its forwarding table.
VPN (Virtual Private Network)




For situations where controlled connectivity is required (security…).
Like a private network, but made available virtually over a public net.
IP tunnel implements a VPN (with encryption, provides a secure pipe)
In IP tunneling, virtual link is created
at entrance router (R1) and given
virtual interface number (which
spccifies R2’s IP-address)





Interface 0
Interface 1
Virtual interface 0
R1 gets datagram for R2 (dest=2.x),
adds IP header with dest = 10.0.0.1,
sends it out default so arrives at R2
(all datagrams for R2 go to default).
R2 gets datagram, strips header,
Forwards to destination on Network 2
Provides:
secure private network
virtual net of same capabilities
(Mbone uses VPNs between
multicast servers)
R1 Forwarding Table
.
Network Number Next Hop
1
Interface 0
2
Virtual interface 0
Default
Interface 1
Routing
Forwarding vs Routing

forwarding: selecting output port based on dest address and forwarding table



Rows contain mapping from net# to Output interface or MAC info.
Structure to optimize for net# lookup (may be hardware implmented), e.g.,
Network #
NextHop
10
171.69.245.10
routing: process by which the forwarding table is built (using routing table)




Table built by routing alg as precursor to forwarding table (rows = Net#, NextHop..)
Table can be in same data structure as forwarding table, but that is rare.
Structured to optimize for calculating changes in topology. (rarely impl in hdwre)
Network #
Interface
MAC Address
10
if0
8:0:2b:e4:b1:2

Routing Protocol Problem: Find lowest cost path between two nodes

Intradomain routing protocols first




A
(interior gateway protocols or IGPs)
Domain: nodes under same admin control
3
Interdomain routing later (EGPs)
Network as a Graph



6
1
4
C
2
1
B
9
E
F
1
D
Nodes are hosts, switches, routers, or networks (initial focus, hosts or routers)
Edges are network links (edge costs indicate desirability of the link).
Routing achieved by running a routing protocol among the nodes (distributed dynamic way to solve
the problem of finding the lowest-cost path in the presence of link failures and changing edge costs)
Distance Vector Algorithm

Each node maintains a set of triples (vector) (Destination, Cost, NextHop)

E.g., initially (assuming each cost=1, so least cost means fewest hops) Each routing table reflects dist=1
for ngbrs and infinity of non-ngbrs.
Initial Distance Vectors:
Intitial Routing Table at A:
Info Stored |Distance to reach Node
Dest Cost
NextHop
at Node | A | B | C | D | E | F | G
B
1
B
A
0 1 1 inf 1 1 inf
C
1
C
B
1 0 1 inf inf inf inf
D
infinity
C
1 1 0 1 inf inf inf
E
1
E
D
inf inf 1 0 inf inf 1
F
1
F
E
1 inf inf inf 0 inf inf
G
infinity
F
1 inf inf inf inf 0 1
G
inf inf inf 1 inf 1 0



Final Routing Table A (converged)
Dest Cost
NextHop
B
1
B
C
1
C
D
2
C
E
1
E
F
1
F
G
2
F
Every nodes sends distance vector to directly connected neighbors

periodically (on the order of every several seconds)

whenever table changes (called triggered update)
Update local table when receive a “better” route
A

smaller cost
Refresh existing routes; delete if they time out
B
C
D
E
F
G
Routing Problems


Example 1: Reaching stablility again after:

F detects that link to G has failed

F sets distance to G to infinity and sends update t o A

A sets distance to G to infinity since it uses F to reach G

A receives periodic update from C with 2-hop path to G

A sets distance to G to 3 and sends update to F

F decides it can reach G in 4 hops via A
Example 2 (looping)

link from A to E fails

A advertises distance of infinity to E (C gets)

B and C advertise a distance of 2 to E (B gets first)

B decides can reach E in 3 hops thru C; advertises to A

A decides it can read E in 4 hops; advertises this to C

C decides that it can reach E in 5 hops…
Loop breaking heuristics

Set infinity to 16

Split horizon (don’t send routes learned from ngbr x to x)

Split horizon with poison reverse (send to x but with inf)
Dest Cost NextHop
F-tbl: G
1
G
F-tbl: G
inf
-
A-tbl: G
inf
-
A-tbl: G
3
C
F:-tbl: G
4
A
A-tbl: E
inf
-
C-tbl: E
inf
-
B-tbl: E
3
C
A-tbl: E
4
B
C:-tbl: E
5
A
B
C
A
D
E
F
G
Routing Information Protocol (RIP)




One of the most widely used routing protocols in IP.
Distributed with Unix BSD (accounts for its popularity to some extent)
Canonical example of routing protocol built on Distance Vector alg.
Only difference from the algorithm described is that nodes are networks, not
routers.





Routers using RIP send advertisements every 30 seconds.
Router sends update when it receives a change causing update from another.
Takes simple approach that the cost of every link is 1 (counts hops).
Valid distances are 1 – 15.
16 represents infinity

This limits RIPs usefulness to small networks (where there always exists routes with
less than 16 hops)
Link State Alg and Open Shortest Path First Protocol (OSPF)




Link State Algorithm Strategy

send to all nodes (not just ngbrs) info about direct connected links (not entire routing tbl
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
Reliable flooding

store most recent LSP from each node

forward LSP to all nodes but the one that sent it

generate new LSP periodically with incremented SEQNO

start SEQNO at 0 when reboot

decrement TTL of each stored LSP
 discard when TTL=0
OSPF uses Link State with added features (authentication, added hierarchy of domains
being divided into areas, load balancing)

Nodes calculate routes using this info and, e.g., Dijkstra’s shortest path algorithm

Routing protocols such as LinkState and RIP do not scale to global Internet numbers.
Global Internet Structure
NSFNET backbone
Stanford
ISU
Internet is not just random Ethernets.
BARRNET
MidNet
regional
regional
Westnet
Recent Past (~1990)
regional
Berkeley
UNL
PARC NCAR
KU
UNM
Consisted of end user nets (each
UA
multiple physical nets with bridges/routers)
connected to regional service provider nets
(BARRNET, Westnet, MidNet..) built from pt-pt links (e.g., T3, DS-3, OC-3) & routers
connected to national backbone (funded by NSF, originated out of ARPANET)
Each service-provider and end-user net is independently administered (Autonomous System AS).
We need to deal with two related scaling issues in the Global Internet (basically using hierarchy):
Scalability of routing: minimize network-numbers carried in routing protocols & stored in tbls.
Address uitilization: make sure IP address space does not get consumed too quickly.
Internet Today:
Interconnection of multiple
backbone service provider nets
(private; interconnected in arbitrary ways)
some large corps connect directly
others to non-backbone service
providers (often aggregate
connection at peering points)
Large corporation
AT&T,
MCI
Sprint…
Backbone service provider
Peering
point
“Consumer ” ISP
“ Consumr ” ISP
Large corporation
Small
corporation
“Consumer”ISP
Peering
point
Subnetting

Original intent of IP addresses: uniquely identify one physical network

Has drawbacks (numbers wasted)


2-host-net gets Class C and wastes 253 addresses;
If ever  255 sites, need Class B – very popular – but 256-host-net wastes ~64,000)


Instead of adding more network numbers (making forwarding tables larger),
alternatively add another level to address/routing hierarchy: subnetting:

Take a single IP network number, allocate the host numbers to several physical nets




Only 214 or ~16,000 Class B net addresses altogether
Subnets need to be close to each other (so they look like the same network to a distant router)
Perfect subnetting situation is large campus or corportation
Subnet masks define variable partition of host part
Subnets visible only within site (covered by the whole network number)
16
16
Network number
Host number
Class B address
111111111111111111111111
00000000
Subnet mask (255.255.255.0)
Network number
Subnet ID
Subnetted address
Host ID
Subnet Example
Subnet mask: 255.255.255.128
Subnet number: 128.96.34.0
128.96.34.15
Next Hop
interface 0
interface 1
R2
Bitwise AND: IP-Addr AND Subnet Mask
gives the subnet number.
128.96.34.1
Interface 0
H1
Forwarding table at router R1
Subnet Number Subnet Mask
128.96.34.0
255.255.255.128
128.96.34.128 255.255.255.128
128.96.33.0
255.255.255.0
R1
Interface 1
128.96.34.130
Subnet mask: 255.255.255.128
Subnet number: 128.96.34.128
128.96.34.139
128.96.34.129
H2
R2
H3
128.96.33.14
128.96.33.1
Subnet mask: 255.255.255.0
Subnet number: 128.96.33.0
128 mask: 1000 0000 128-255 or 0-127
192 mask: 1100 0000 four segments
192-255, 128-191,
64-127, 0-63
Subnetting continued

What is the proper subnet mask, given you want to create n subnets?

In a class B network (16 bit network address) e.g., 131.107.0.0 and 6 subnets:
6=110 (3 bits  use 3 highorder 1-bits)  1110 0000 0000 0000 = 224, 0
Subnet mask is 255,255,224,0 (acts as a filter to hide all but the host-id part of any subnet,
i.e., 1-bit in a mask is like a “pipe” letting bits flow thru and a 0-bit is like a sponge
trapping bits (leaving a 0-bit) ).
Note, we use a default subnet mask for standard Class networks (e.g., for Class A nets use
subnet mask = 255,0,0,0; Class B = 255,255,0,0 and Class A = 255,255,255,0.
So, e.g., for Class B IP address, 131.107.16.200 ANDed with Class B subnet mask,
255,255,0,0 give network address = 131.107 and leaving host address of 16.200.

Back to Class B subnet mask 255,255,224,0, how assign the 6 subnet addresses?
Use highorder bits: 001 010 011 100 101 110 (can’t use all 3 zeros or all 3 1’s),
so subnet ids are 0010 0000=32; 0100 0000= 64; 0110 0000=96;
1000 0000=128; 1010 0000=160; 1100 0000=192

So, eg., to send to host 12 on subnet 64 use IP 131.107.64.12. Then ANDing with
subnet mask, 255,255,224 gives 131.107.64.0 = the correct subnet on the correct net.
Subnetting continued2

At the other extreme:


In a class B network (16 bit network address) e.g., 131.107.0.0 and 125 subnets:
125=111 1101 (7 bits  use 7 highorder 1-bits) 
1111 1110 0000 0000 = 254, 0
Subnet mask is 255,255,254,0.
With a Class B subnet mask of 255,255,254,0,
how do we assign the 125 subnet addresses?
Start with highorder 7-bit: 0000 001  add low order  0000 0010 = 2 
add 2 until you get 125 subnets (each will accommodate only 2 nodes however
with host numbers, 0 and 1))
So subnet ids are: 2 4 6 8 10 …250

To send to host 1 on subnet 244 use IP 131.107.244.1 Then ANDing with
subnet mask, 255,255,254 gives 131.107.244.1 = the correct subnet on the correct net.
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 D (do ARP and deliver)
else (NextHop is a router)
deliver datagram to NextHop (don’t do ARP yet)

Use a default router if nothing matches
Can put multiple subnets on one physical network (forcing hosts on same physical
network to talk through a router for security, departmentalizing..)
Subnets not visible from the rest of the Internet (outside the subnet domain)

Bottom line is subnetting helps scalability in two ways:




Improves address assignment efficiency by not using up entire net address for every
physical network
Helps aggregate information (from a distance, complex internet looks like one net)
Supernetting (CIDR classless Inter-domain routing)

Addresses two scaling concerns:


Growth of backbone routing tables (as more net numbers need to be stored)
Potential for 32-bit IP address space exhaustion well before 4 billionth host is attached


Called CIDR: Classless Inter-Domain Routing






Breaks rigid boundarries between network and host numbers
Assign block of contiguous net numbers (2n) to a group of nearby networks
and give the group one net number (more flexibly than the fixed Class A,B,C scheme does).
Represent blocks with a single pair (length, value)


Tries to minimize the number of routes a router needs to know
Tries to hand out addresses efficiently by:
Aggregating routes: Lets us use single entry in forwarding table to reach lots of nets


This problem centers on Class B addresses (with only 2 14 = 16,384 network numbers)
Length gives # bits in network number (2 - 32)
Value is the actual resulting network number
Typically, a service provider or large corporation is given a block of addresses with one
CIDR address (hands out addresses within that block)
All routers must understand classless CIDR addressing (net #’s from 2 – 32)

Problem: Now net#’s in a forwarding table may overlap


e.g., 171.68 (16 bit) and 171.68.10 (24 bit).
Principle of “longest match” applies (e.g., IP addr: 171.68.10.5 matches 171.68.10)
Route Propagation

Autonomous System (AS) (AKA: routing domain)
 corresponds to an administrative domain
 examples: University, company, backbone network

Two-level route propagation hierarchy
 interior gateway protocol




for intra-domain routing
each AS selects its own
Goal: finding optimal paths (OPTIMALITY)
exterior gateway protocol




For inter-domain routing
Internet-wide standard
Goal: find any path (REACHABILITY)
Two major interdomain routing protocols


EGP (Exterior Gateway Protocol) was first
 used when Internet was a simpler tree with one backbone
BGP (Border Gateway Protocol)
th version, so BGP-4
 In its 4
 Accomodates non-tree structure of current Internet
Popular Interior Gateway Protocols

RIP: Route Information Protocol




distributed with Unix
distance-vector algorithm
based on hop-count
OSPF: Open Shortest Path First




recent Internet standard
uses link-state algorithm
supports load balancing
supports authentication
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
be its peer; peers exchange reachability information
neighbor reachability: one router periodically tests if
the another is still reachable; exchange HELLO/ACK
messages.
routing updates: peers periodically exchange their
routing tables (using a distance-vector algorithm)
BGP-4: Border Gateway Protocol

AS Types
stub AS: has a single connection to one other AS


multihomed AS: has connections to more than one AS


refuses to carry transit traffic
transit AS: has connections to more than one AS



carries local traffic only
carries both transit and local traffic
Each AS has:


one or more border routers
one BGP speaker per AS that advertises:


local networks
other reachable networks


Large corporation
(transit AS only)
gives path information
“Consumer ” ISP
Peering
point
Backbone service provider
“ Consumr ” ISP
Large corporation
Small
corporation
“Consumer”ISP
Peering
point
BGP Example

Speaker for AS2 advertises reachability to


P and Q
networks 128.96, 192.4.153, 192.4.32, and 192.4.3, can be reached
directly from AS2
Customer P
(AS 4)
128.96
192.4.153
Customer Q
(AS 5)
192.4.32
192.4.3
Customer R
(AS 6)
192.12.69
Customer S
(AS 7)
192.4.54
192.4.23
Regional provider A
(AS 2)
Backbone network
(AS 1)
Regional provider B
(AS 3)

Speaker for Backbone advertises


networks 128.96, 192.4.153, 192.4.32, and 192.4.3 can be reached along
the path (AS1, AS2).
Speaker can cancel previously advertised paths
IP Version 6

(originally: IPng (next generation)
Motivation for a new IP version is same as motivation for, e.g., Subnetting, CIDR


Address depletion (if set-top-boxes, electric meters, toasters get IP addrs, is 4 billion enough?)
Routing Information problem (growth of routing table info needed in internet routers)
Require new software for every host/router?? (IETF wants it as upward compatible as possible)

While the IPng is at it, in addition to solving the 2 problems above, also considering;





Support of real-time services (video conferencing etc. - RSVP QoS, etc.)
Security support
Auto-configuration (hosts automatically configure themselves)
Enhanced routing functionality (e.g., for mobile hosts, etc.)
Some of the specific changes from IPv4 to IPv6 include:

Longer address fields (3.4 * 1038 128 bits: eg, 47CD:1243:AC09:0022:1432:A456:0123.B387



8 16-bit fields, instead of 4 8-bit fields.
Classless
Simplified header format (e.g., no checksum – reduces packet processing time in routers)





Checking already done at the link layer and transport layer anyway
Flexible support for options (more efficient, flexible)
Flow label capability (for specifying QoS)
Large Packet size (longer than 64KB – called jumbo packets up to 4 billion bytes)
Fragmentation at the source only
MBone
(Multicast
Backbone)
Can be thought of as Internet Radio/TV (broadcasts live A/V in digital)



Virtual overlay network on top of the Internet
Mbone consists of multicast islands (with special Mrouters connected by IP tunnels)


Each island (typically a LAN) supports hardware multicast.
Currently uses Distance Vector Multicast Routing Protocol or DVMRP:
When an island wants to join
(e.g., G) its administator
sends message to the
Mbone mailing list.
Nearby admin(s) contact G
to setup tunnel(s).
Typically each country has
a backbone. Tunnels cross
the Atlantic and Pacific,
making it world-wide.
Tunnels can be reshuffled.