Dynamic Routing
Download
Report
Transcript Dynamic Routing
Internet Applications
Theory & Applications
Internet Application
- Ibrahim Otieno [email protected]
+254-0722-429297
SCI/ICT Building 2nd Floor Rm. 201
Error Reporting Mechanism
Best-Effort Semantics and Error Detection
IP defines ‘best-effort’ communication service
Datagrams can be lost, duplicated, delayed or
delivered out of order
Nonetheless IP attempts to avoid errors and
report problems when they occur
Checksum used to detect transmission error
Host creates datagram, includes a checksum on
header and upon receipt, verified to ensure
header is intact
Best-Effort Semantics and Error Detection
In case of error, datagram discarded
Receiver does not send error message to sender
because it cannot trust source address in header
Likewise, receiver does not forward datagram
because cannot trust destination address in
header and therefore discards damaged datagram
Internet Control Message Protocol (ICMP)
Problems less severe than transmission errors
are reported
In case some path on the internet is broken;
datagram sent from a host to recipient cannot
be delivered
TCP/IP suite includes ICMP that IP uses to send
such error messages
ICMP required for standard implementation of IP
These two protocols are co-dependent: IP uses
ICMP to send error message, and ICMP uses IP
to transport messages
Internet Control Message Protocol (ICMP)
Examples of ICMP error messages include:
1. Source Quench – Router sends whenever it
has no more buffer space available for datagrams
Source reduces transmission rate upon receipt
2. Time Exceeded – Sent in two cases:
◦ When router reduces ‘time to live’ field in a
datagram to zero, it discards datagram and
sends a time exceeded message
◦ Send by host if reassembly timer expires
before all fragments from datagram arrives
Internet Control Message Protocol (ICMP)
3.
4.
5.
Destination Unreachable – Sent when a
router determines that datagram cannot be
delivered to final destination
Redirect – Sent when host creates a datagram
destined for a remote network and sends to
wrong router and a router realizes that it should
have been sent to different router
Parameter problem – One of the parameters
specified in a datagram is incorrect
Internet Control Message Protocol (ICMP)
1.
2.
ICMP defines information messages that include:
Echo Request/Reply - Echo request message
sent to ICMP software and ICMP software
required to send an ICMP echo reply message
The reply carries the same data as the request
Address Mask Request/Reply – Host
broadcasts address mask request when it boots,
and routers that receive request send address
mask reply containing correct 32-bit subnet mask
being used on the network
ICMP Message Transport
ICMP uses IP to transport messages
Router creates datagram and encapsulates ICMP
message in datagram
Datagram then sent by being encapsulated in
frame for transmission
ICMP messages created in response to datagram
Either datagram has a problem or datagram
carries an ICMP request message to which
destination replies
Both ways ICMP error message/reply sent to
source
ICMP Message Transport
Datagram carry source address
Router extracts source address from header of
datagram and places it in destination header of
datagram with ICMP message
Datagrams with ICMP message forwarded like
other datagram except if a an error is
encountered, no error message is sent
Avoids internet congestion with error message
ICMP Message Transport
Ping uses ICMP echo request/reply messages
When invoked, sends IP datagram containing
ICMP echo request message to specified
destination and waits for reply
If no reply, retransmits request and if no reply
arrives, declares that remote machine not
reachable
ICMP software on remote machine replies to
echo request
ICMP Message Transport
We can summarize that ICMP includes both
error and informational messages
ICMP is integrated with IP: ICMP encapsulates
messages in IP for transmission and IP uses ICMP
to report problems
TCP: Reliable Transport
The need for Reliable Transport
Reliability is fundamental in computers
Example, programmer application sending data to
I/O device does not have to verify that it is intact
Application relies on underlying computer system
for reliable transfer (no data loss, duplication or
delivery out of order)
Applications using internet require that too
Internet must provide same semantics as a
conventional computer system i.e. no data loss,
duplication or delivery out of order
The Translation Control Protocol
Reliability achieved by transport protocol;
Applications interact with it to send/receive data
In TCP/IP, TCP provides reliable transport service
TCP solves a difficult problem well – better than
other general-purpose protocols
Consequently, most internet applications built to
use TCP
The Translation Control Protocol
From application perspective, TCP has seven major
features:
1. Connection Orientation –provides
connection-oriented service in which
applications request a connection to a
destination, then use it to transfer data
2. Point-To-Point Communication – Each TCP
connection has exactly two end points
3. Complete reliability – guarantees that data
sent will be delivered exactly as sent, with no
data missing or out of order
4. Stream Interface–application sends
continuous sequence of bytes across connection
The Translation Control Protocol
5.
Full Duplex communication – allows data to
flow in either direction at any time
TCP can buffer data, making it possible for
application to send data then continue with
computation while data being transferred
6.
Reliable Connection Startup – requires both
applications agree to new connection; packets
used in previous connections will not interfere
with new connection
7.
Graceful Connection Shutdown - application
program open connection, send data, then
request connection be shut down gracefully
The Translation Control Protocol
In summary, TCP provides a completely reliable
connection-oriented, full-duplex stream service
Allows two applications to form a connection,
send data in either direction and then terminate
the connection
TCP connection started reliably and terminated
gracefully
End-to-End Service and Datagrams
TCP an end-to-end protocol; provides
connection from host to remote application
Applications request TCP to form a connection,
send, receive data, and close connection
Connections provided by TCP are virtual
TCP software module on two machines
exchange messages to achieve illusion of a
connection
TCP uses IP to carry messages
Datagram arrive on destination, IP passes to TCP
End-to-End Service and Datagrams
TCP uses IP to carry messages, IP doesn’t read
TCP treats IP as packet communication system
connecting hosts at two endpoints and
IP treats TCP message as data to be transferred
Fig below - internet with two hosts and router
illustrating relationship between TCP & IP
Achieving Reliability
Some problems in communication are: unreliable
delivery and computer reboot
Two communicating applications using TCP can
lose, duplicate, delay or deliver data out of order
Messages must be unambiguous, or duplicate
messages will be accepted from old connection &
interfere with new connection
Computer reboot poses challenge to TCP
Protocol should reject packets from previous
reboot
Packet Loss and Retransmission
TCP uses variety of techniques for reliability
A common technique is retransmission
Sender compensates for packet loss by
implementing a retransmission scheme
Receiver sends acknowledgement to the sender
TCP starts timer on sending and if timer expires
before acknowledgement, the sender retransmits
How long TCP should wait before retransmitting?
Time for LAN and WAN different
Complicated by bursts of data that cause
congestion, causing delays
Packet Loss and Retransmission
To summarize, delay for data to reach destination
and acknowledgement to return depends on:
◦ traffic in internet
◦ distance to destination
TCP allows multiple applications to communicate
with multiple destinations concurrently
Traffic conditions affect delay, TCP must handle a
variety of delays that can change rapidly
Adaptive Retransmission
Before TCP most protocols used fixed timeout
Designers realized that this would not operate
well for internet thus chose to make it adaptive
TCP monitors current delay connection, and
adapts retransmission timer to accommodate
changing conditions
TCP estimates round-trip delay, measuring time
needed to receive response and records time
TCP generates sequence of round-trip estimates
and uses statistical function to produce weighted
average
Adaptive Retransmission
In addition to weighted average, TCP keeps an
estimate of variance and uses linear combination
of estimated mean and variance as a value for
retransmission
Adaptive retransmission helps TCP react quickly
when delay:
◦
◦
increases following burst of packets
returns to a lower value after a temporary burst
Buffers, Flow Control and Windows
When connection established, each host allocates
buffer to hold data and send size to other end
As data arrives, receiver sends acknowledgement,
which also specify remaining buffer size
Amount of buffer space available at any time is
called window, and notification that specifies size
called window advertisement
If receiver reads data as fast as it arrives, will send
positive window advertisement
If sender operates faster than receiver data will
fill receiver’s buffer and advertise a zero window.
Sender that receives zero window must stop
sending until receiver advertises positive window
Three-Way Handshake
TCP uses a 3-way handshake – 3 messages
3-way exchange is necessary and sufficient to
ensure unambiguous agreement despite packet
loss, duplication and delay
TCP uses term synchronization segment to
describe messages used to create a connection
And to describe messages in a 3-way handshake
finish segment used to close a connection.
Three-Way Handshake
Figure below illustrate 3-way handshake used to
close connection
Three-Way Handshake
As other messages, TCP retransmit lost SYN or
FIN segments
Handshake guarantees TCP will not open or
close connection until both ends have interacted
3-way handshake for creating connection requires
each end to generate random 32-bit number
If application tries to establish new connection
after reboot,TCP chooses new random number
Pair of applications can use TCP to communicate,
close connection then establish new connection
without interference from duplicate or delayed
packets
Congestion Control
Packet loss or long delays more likely to be
caused by congestion than hardware failure
Protocol that retransmit can worsen congestion
by injecting additional copies of a message
Excessive retransmission, entire system can reach
state of congestion collapse (traffic jam).
TCP uses packet loss as measure of congestion,
and responds by reducing rate of retransmission
TCP starts congestion control if a message is lost
Instead of retransmitting data to fill the receiver’s
window size, TCP begins by sending a single
message containing data
Congestion Control
If acknowledgement arrives without loss, TCP
doubles data sent and sends two more messages
If acknowledgements arrive for those two, TCP
sends four more and so on
Exponential increase continues until TCP is
sending half of receiver’s advertised window then
slows down rate of increase
By backing off, TCP is able to alleviate congestion
Scheme avoids retransmissions to a congested
internet, helping prevent congestion collapse.
Internet Routing
Static vs. Dynamic Routing
IP routing divided into two: static and dynamic
Routes are static if they do not change
Static routing table loaded with values when
system boots, and routes do not change unless an
error detected
Dynamic routing refers to system that can
change routing table information over time
Internet Routing
Static vs. Dynamic Routing
Dynamic routing begins like static routing by
loading routes into routing table on booting
System also starts route propagation software
Routing software interacts with routing software
on other routers to learn about optimal routes
The software then updates the local routing table
to ensure that datagrams follow optimal routes
Static Routing in Hosts
Static routing does not require routing software
Does not consume bandwidth and no CPU cycles
Relatively inflexible; it cannot accommodate
network failures and changes in topology
Static routing used mostly in cases where host
has one network connection and a single router
connects network to rest of Internet
When application generates a datagram for
computer on local net, an entry in routing table
directs IP deliver datagram directly to destination
When a datagram is destined for any other
network, another entry in the table directs IP to
send the datagram to router
Static Routing in Hosts
Most PCs on internet use static routing
When configuring IP software on a PC, user
enters a network prefix, a subnet mask and the IP
address of the default router
The three items comprise the information
needed to create the static routing table
Host’s routing table contains two entries: one for
network to which network attaches and a default
entry that directs all other traffic to router
Internet Routing
The routing table is illustrated in the figure below:
Dynamic Routing and Routers
Most routers use dynamic routing
Assume figure above corresponds to a customer
of an ISP and traffic leaving customer’s site
through router R1 must travel to the ISP
Because routes never change, routing table in R1
can be static just as in the routing table of a host
Static routing & default routes do not suffice for
most routers
Dynamic Routing
•
•
When two ISPs interconnect, both need to
exchange routing information dynamically
Consider the figure below:
Dynamic Routing and Routers
Each of two routers belongs to a separate ISP
Network labeled Net 2 belongs to corporate
customer of ISP1 and network labeled Net 3
belongs to corporate customer of ISP2
Both routers know about network labeled Net 1
However, router R1 dos not know about Net 3
because there is no direct connection
Similarly, router R2 does not know about Net 2
Dynamic Routing and Routers
How can a router in one ISP have routes to
networks owned by customers of another ISP?
With only 3 networks, static routing suffices
However, scheme does not scale to ISPs with
thousands of customers
Each time a new customer is added, the
information must be passed to a person at the
other ISP, who then updates the routing table
Slow to accommodate failures/congestion
For example, if a network interface card fails or
router is accidentally unplugged, routing software
needs to detect this and find alternative path
Dynamic Routing and Routers
Example, assume that R1 & R2 in previous figure
each run routing software;
Routing software uses route propagation protocol
to exchange routing information across Net 1
Software running on R2 installs a route to Net 2.
If R2 crashes, the routing software in R1 will
detect that Net 3 is no longer accessible and will
remove the route from R1’s table.
Later when R2 comes back on line, the routing
software in R1 will determine that Net 3 is
reachable again and will reinstall the route.
Dynamic Routing and Routers
To summarize, each router runs routing software
that learns about destinations other routers can
reach, and informs other routers about
destinations that it can reach
The routing software uses incoming information
to update the local routing table continuously
Client-Server Interaction
Functionality of Application Software
Physical connections & communication protocols
useful but most useful function provided by
application software
Applications provide high-level services and
determine how users perceive the capabilities of
the internet e.g. email, browsing, transfer of files
Client-Server Interaction
Functionality of Application Software
Applications determine formatting and access of
information
They also define symbolic names used to identify
physical & abstract resources like computers,
printers, mailboxes etc
Symbolic names allow access or use of services
without understanding low-level details
Functionality of an Internet
Internet provides communication infrastructure
but does not specify services offered
Internet like a telephone system - provides ability
to communicate but doesn’t know what
computers do with communication service
Network h/w and protocol s/w do not know
when to initiate contact with remote computer
Communication across internet requires pair of
application programs to cooperate like placing a
telephone call and it is received on other side
The Client-Server paradigm
Network applications use client-server paradigm
Server wait passively for contact and client
initiate communication actively
Client and server refer to two applications
involved in a communication
In general, client s/w has following characteristics:
◦ Is application that becomes client temporarily
when remote access is needed, and performs
computations locally
The Client-Server paradigm
In general, client s/w has following characteristics:
◦
◦
◦
◦
◦
Invoked by user and executes for one session
it runs locally on a user’s personal computer
actively initiates contact with a server
actively contacts one remote server at a time
but can access many
Does not require special h/w or special O/S
The Client-Server paradigm
In contrast, server software:
◦ Is a special-purpose, privileged program
dedicated to providing one service, but can
handle multiple remote clients at same time
◦ invoked automatically at system boot
◦ runs on a shared computer
◦ waits passively for contact from remote clients
◦ Requires powerful h/w and a sophisticated O/S
Server is not computer (with power h/w, O/S etc)
on which the server process runs, the computer is
referred to as server-class computer
Requests, Responses and Direction of Data Flow
Info flows in either or both directions
For example, client may request a file and server
sends copy or it may send a copy of a file to
server for storage
Client may send series of requests & server
issues series of responses
Like most application programs, a client and
server use transport protocol to communicate
A server-class computer can offer multiple services
at same time to utilize resources; a separate
server program needed for each service
Client-Server Interaction
From figure, Client or Server application interacts
directly with transport layer protocol
Transport protocol uses lower layer protocols to
send and receive individual messages
Thus a computer needs a complete stack of
protocols to run either a client or server
Identifying a Particular Service
TP provides way for client to specify service
Mechanism assigns each service a unique id, and
requires both client and server to use the id
Server registers with local protocol software by
specifying identifier for service it offers
Client’s protocol specifies id for required service
TP software on server’s machine uses the id to
determine the server program to handle request
Identifying a Particular Service
TCP uses a 16-bit integer value known as protocol
port number (PPN) to identify services and client
specifies PPN of desired service.
A server computer can allow multiple copies of a
server for a single service, i.e. support concurrency
Concurrency is fundamental to client-server
model of interaction
Concurrent server offers service to multiple
clients at same time, without requiring each to
wait for clients to finish