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