Transcript Address Resolution

Internet Application
Theory & Applications
Internet Application
- Ibrahim Otieno [email protected]
+254-0722-429297
SCI/ICT Building 2nd Floor Rm. 201
Binding Protocol Addresses
Protocol Addresses &Packet delivery




Application program generate packets to send
across internet, software place data in packet
that contains destination address
Software in each host / router uses destination
address to select a next hop for packet
Once next hop selected, software transfers
packet across network to selected host/ router
To provide illusion of one large network, s/w
works with IP addresses to forward packets
Protocol Addresses &Packet delivery




Protocol addresses can’t be used to transmit
across physical hardware
Hardware doesn’t understand IP addressing
Frame sent across physical network must use
hardware’s frame format
Addresses in frame must be h/w addresses
Protocol Addresses &Packet delivery

Protocol address for next hop must be
translated to equivalent hardware address
before a frame can be sent

In summary, protocol addresses are
abstractions provided by software;
Network hardware doesn't know to locate a
computer from protocol address.
Protocol address of next hop must be
translated to h/w address before packet is sent


Address Resolution




Translation from protocol address to hardware
address known as Address Resolution.
Address resolution is local to a network
Computer can resolve address of another only
if both are on the same physical network.
Illustrated by the example below:
Address Resolution





In fig, hosts A & B attach to same network
If application on A sends data to B, the
application uses B’s IP address as destination.
Protocol s/w on A resolves B’s IP address to B’s
h/w address and uses it to send frame directly
If application on A sends message to application
on F, software on A first determines that packet
must travel through router R1.
Software on A resolves address of R1 and sends
packet to R1
Address Resolution



Software on R1 determines that packet must
reach R2, resolves its address and sends packet
Finally R2 receives packet, determines that
destination F is attached to rightmost network
resolves address of F and delivers packet
From example, each computer handling packet
resolves next-hop address before sending
Address Resolution

In summary, mapping between protocol and
hardware address is address resolution

Host/router uses address resolution to send
packet to another computer on same network

Computer never resolves address of host on a
remote network
Address Resolution Techniques




Algorithm used by s/w to translate protocol
into hardware address depend on protocol
and h/w addressing schemes.
Example, method used to resolve an IP address
to Ethernet address differs from that used to
resolve it to an ATM address
Since router can connect to multiple types of
networks, it may use more than one type of
address resolution
Therefore, has more than one translation
module
Address Resolution Techniques

Address resolution algorithms grouped into
three categories:
1. Table Lookup
2. Closed-form computation
3. Message exchange
Address Resolution Techniques
1. Table Lookup
Bindings or mappings stored in a table in
memory that software searches to resolve
address
2. Closed-form computation
Protocol address chosen carefully so that
computer’s h/w address can be computed
from protocol address using basic Boolean
and arithmetic operation
Address Resolution Techniques
3. Message exchange
Hosts exchange messages to resolve address
One computer sends message requesting an
address translation, another computer sends
a reply containing requested information
Address Resolution with Table Lookup



Requires data structure to contain information
about address bindings
Table consists of entries that contain protocol
address and equivalent hardware address
Fig below shows example of address binding table
Address Resolution with Table Lookup

Each entry corresponds to one host on network


Separate address binding table used for each n/w
IP addresses in given table have same prefix

Main advantage is generality: table can store
address bindings for arbitrary set of computers
on a network
Protocol address map to arbitrary h/w address


Table lookup algorithm for address resolution is
straightforward and easy to program
Address Resolution with Closed-Form
Computation





Many networks technologies use static physical
addresses, some use configurable addressing network interface assigned a specific h/w address
In such networks, possible to chose addresses that
make closed-form address resolution possible
Resolver that uses closed-form, computes
mathematical function that maps an IP address to
a hardware address.
It is efficient for configurable networks because
both hardware and IP addresses can be changed,
thus values chosen to optimize translation
Possible to chose IP address identical to host’s
hardware address making translation trivial
Address Resolution with Message
Exchange



Computer that needs to resolve address sends a
message across network and receives a reply
Message carries request specifying protocol
address, and reply carries corresponding
hardware address
Address resolution request can be:
◦ sent to an address server which will then
send a reply
◦ Broadcasted to all machines & corresponding
machine responds
Address Resolution with Message
Exchange





Major advantage of first scheme is centralization
Few address resolution servers handle all address
resolution requests
Address resolution easier to configure & manage
Major advantage of second scheme is distributed
computation
Address resolution servers can be expensive and
can become a bottleneck on a large busy network
Address Resolution Protocol (ARP)

TCP/IP can use any of 3 resolution methods;

Method chosen for network depends on
addressing scheme used by underlying hardware

Table lookup used for resolution across a WAN,
closed-form computation with configurable
networks, and message exchange on LAN
hardware with static addressing
Address Resolution Protocol (ARP)




To guarantee computers agree on format and
meaning of messages used to resolve addresses,
TCP/IP suite uses Address Resolution Protocol (ARP)
ARP standard defines 2 basic message types:
1. request and
2. response
Request message contains IP address and
requests corresponding hardware address;
Reply contains both the IP address sent in
request and hardware address
IP Datagrams and Datagram Forwarding


Goal of internet to provide system that allows
application send data to another computer
In well-designed internet, application program is
unaware of:
1.
2.
3.

underlying network to which it connects
remote network to which destination connects
interconnection between them
Designers must decide whether to offer
application connection-oriented service or
connectionless service, or both
IP Datagrams and Datagram Forwarding

TCP/IP designers chose to include both
connectionless and connection-oriented services

Chose to make fundamental delivery service
connectionless, and add reliable connectionoriented service that uses underlying
connectionless service

Design successful, and often emulated by other
protocols
Virtual Packets

Connectionless internet service an extension of
packet-switching

Allows a sender to transmit individual packets of
data across internet

Each packet travels independently and has info
identifying intended recipient

Routers forward packets from one n/w to another
Virtual Packets

Source host creates packet, places destination
address in header, then sends to nearby router

Router use destination address to select next
router on path to destination then sends packet

Eventually, packet reaches router that can deliver
packet to final destination
IP Datagrams and Datagram Forwarding

To overcome heterogeneity, IP software defines
packet format independent of underlying h/w

Result is universal virtual packet that can be
transferred across underlying hardware

Virtual implies protocol software handles
packets in a way not understood by hardware

Router connects heterogeneous networks;
cannot transmit a copy of a frame that arrives
on one network across another

To accommodate heterogeneity, internet defines
hardware-independent packet format.
The IP Datagram







TCP/IP protocols use ‘IP datagram’ to refer to
internet packets.
Amount of data carried in datagram not fixed
Sender chooses amount of data
Size of datagram determined by sending
application as appropriate for particular purpose
Allowing size of datagrams vary makes IP
adaptable to variety of applications
Datagram can contain as little as 1 byte of data
and at most 64 KB including header
Header contains info to route datagram across
internet e.g. it contains both sender and
destination IP addresses
Forwarding an IP Datagram

Each router along path to destination receives
datagram, extracts destination address from
header and uses it to determine next hop

Router forwards datagram to the next hop:
either final destination or another router

To make selection of next hop efficient, each IP
router keeps information in a routing table

Routing table initialized when router boots
and updated if topology changes or h/w fails

Routing table contains set of entries each
specifying destination and next hop to reach
that destination
Best-Effort Delivery



IP defines semantic of communication, and use
term best-effort to describe the service it offers
The standard specifies that although IP makes
best-effort attempt to deliver datagrams, does
not guarantee that it will handle problems of:
◦ Data duplication
◦ Delayed or out-of-order delivery
◦ Corruption of data
◦ Datagram loss
Additional layers of protocol software are
needed to handle each of these errors
IP Encapsulation, Fragmentation & Reassembly

Datagram Transmission and Frames

To forward datagram IP software in router/host
selects next hop, N, then transmits datagram
across physical network to N.
Hardware doesn’t understand datagram format
or internet addressing
Each technology defines frame format and
physical addressing scheme and will only accept
packets that adhere to specified format and
addressing scheme.
Internet contains heterogeneous technology,
frame format needed to cross a network may
differ from frame format of previous network.



Encapsulation



Encapsulation is used to transmit datagram across
physical network that does not understand
datagram format
When IP datagram is encapsulated in a frame,
entire datagram is placed in data area of frame
Network hardware treats frame containing
datagram exactly like any other frame.
Encapsulation





To identify a frame whose data area contains an
IP datagram sender and receiver agree on value
used in frame type field.
When sender places datagram in frame, it assigns
frame type field a special value reserved for IP
Frame arriving with special value in type field,
receiver know data area contains IP datagram
Encapsulation requires sender to supply physical
address of next computer to receive datagram
To compute IP address, software on computer
must do address binding as described earlier.
Encapsulation



In summary, a datagram is encapsulated in a frame
for transmission across a physical network.
The destination address in frame is address of
next hop to which the datagram should be sent;
Address is obtained by translating IP address of
the next hop to an equivalent hardware address.
Transmission across an Internet




Encapsulation applies to a transmission at a time
Sender selects next hop, encapsulates datagram
in frame and transmits result across network
When frame reaches, recipient removes IP
datagram and discards frame
If datagram must be forwarded to another
network, new frame is created
Transmission across an Internet

Fig below shows datagram encapsulated & unencapsulated as it travels from source to
destination through 3 networks and 2 routers

Each n/w can use different hardware technology
from others, meaning frame formats can differ.
Transmission across an Internet

An IP datagram as it appears at each step during a trip across an
internet. Whenever it travels across a physical network, the datagram is
encapsulated in a frame appropriate to the network.
Transmission across an Internet





As the figure shows, hosts & routers store
datagram in memory with no additional header
When datagram passes across network it is
encapsulated in a frame suitable for the network
Size of header on a datagram depends on
network technology
Example, if network 1 is an Ethernet, header in
frame 1 is Ethernet header.
Similarly, if network 2 is FDDI ring, header in
frame 2 is FDDI header
Transmission across an Internet




Note that frame headers do not accumulate
during a trip through the internet.
Datagram is encapsulated and frame header
appended before it is transmitted across n/w
When frame arrives at next hop, datagram is
removed from frame before being routed and
encapsulated in outgoing frame.
When datagram reaches final destination, frame
carrying datagram is discarded and it appears the
same original size before being sent
MTU, Datagram Size and Encapsulation





Each hardware technology specifies maximum
amount of data that a frame can carry - Maximum
Transmission Unit (MTU)
Network hardware not designed to transfer
frames that carry more data than MTU allows
Datagram must be smaller or equal to n/w MTU
or it cannot be encapsulated for transmission
Problem in Internets with heterogeneous n/w s
Router can connect networks with different
MTU, it can receive datagram from n/w that
cannot be sent over another
MTU, Datagram Size and Encapsulation





Fig below illustrates router interconnecting two
networks with MTU values of 1500 and 1000
Host H2 attaches to network with MTU of 1000
H2 transmits datagrams of 1000 bytes or less
H1 attaches to network with MTU of 1500 bytes,
can transmit datagrams that contain up to 1500
If H1 sends 1500 datagram to H2 , router R will
receive datagram, but not be able to send it to net2
MTU, Datagram Size and Encapsulation





IP router uses technique known as fragmentation
to solve problem of heterogeneous MTUs
A datagram larger than MTU of network over
which it must be sent is divided into smaller bits
called fragments by router and sent independently
Fragment has same format as other datagrams
A bit in the flags field of the header identifies a
fragment and full datagram.
Other fields in the header are assigned
information to assist reassemble the fragment.
MTU, Datagram Size and Encapsulation

In summary, datagram cannot be larger than
MTU of a network over which it is sent

A router receiving a datagram larger than MTU
of network over which it is sent, it divides it into
smaller pieces called fragments

Each fragment uses the IP datagram format, but
carries only part of the data.
Reassembly





Process of creating copy of original datagram
from fragments is called reassembly
Since each fragment has a copy of original
datagram header all fragments have same
destination address as original datagram
Final fragment has an additional bit set in header
Thus, a receiver performing reassembly can tell
whether all fragments have arrived successfully
IP specify that ultimate destination host
reassemble fragments
Reassembly



In fig, if H1 sends a 1500-byte datagram to host
H2, router R1 will divide datagram into 2
fragments then forward to R2.
R2 does not reassemble fragments, instead uses
destination address to forward fragments
Final destination host, H2, collects fragments and
reassembles them to produce the original
Reassembly
Advantages of destination reassembling include:
1. Reduces amount of state info in routers
2. It allows routes to change dynamically
IP is free to pass fragments in different routes

To reassemble fragments arriving out of order,
sender laces unique id no in id field of datagram

Router puts id no into each fragment when
fragmenting

Receiver uses id no and source IP address in
fragment to determine datagram to which
fragment belongs and fragment offset field tells
receiver how to order fragments

Fragment Loss



IP doesn’t guarantee datagram delivery – if
network drop a packet, encapsulated datagram or
fragment can be lost
When all fragments arrive, datagram can be
reassembled
A problem arises when one or more fragments
arrive, and some are delayed or lost
Fragment Loss

Although datagram cannot be reassembled

Receiver must save fragments in case missing
fragments are only delayed

Receiver cannot hold fragments indefinitely to
avoid exhausting memory

IP specifies a maximum time to hold fragments.
When first fragment arrives, receiver starts timer



If all fragments arrive before timer expires,
receiver cancels timer and reassembles datagram
Fragment Loss




If timer expires before all fragments arrive,
receiver discards fragments that have arrived
Result of IP’s reassembly timer is all-or-nothing:
All fragments arrive and datagram assembled or
all discarded
In poorly designed internet where networks are
arranged in sequence of decreasing MTUs, each
router along the path must further fragment each
fragment
Fragment Loss




IP doesn’t distinguish between fragments and subfragments
Receiver cannot know whether fragment was
result of a router fragmenting datagram or
routers fragmenting fragments
Advantage is that receiver can perform
reassembly of original datagram without
reassembling sub-fragments
Reduces amount of info needed in headers &
saves CPU time