Transcript Computer Networks(Routing and IPv6).

Computer Networks
Section1. Routing Algorithms and
Network Layer Protocol
Presenter: Shu-Ping Lin
Outline
• Routing Algorithms
• The Network Layer in The Internet
Outline
• Routing Algorithms
• The Network Layer in The Internet
Store-and-Forward Packet Switching
Routing Algorithm
• Routing algorithm
– Datagram
– Virtual circuit
• Differences between routing and forwarding
• Routing versus forwarding
Routing Algorithm (cont’d)
• Requirement of routing algorithm
–
–
–
–
–
Correctness and Simplicity
Robustness
Stability
Fairness
Optimality
Datagram Routing
Virtual-Circuit Routing
Comparison
Routing Algorithm (cont’d)
• Nonadaptive (static routing)
– Do not base routing decisions on measurement
of the current traffic and topology.
– The route used to get from node to node is
computed in advance.
• Adaptive (dynamic routing)
– Change routing decisions to reflect changes in
topology and traffic.
Optimality Principle
• If router J is on the optimal path from router
I to router K, the the optimal path from J to
K also falls along the same route.
• Sink tree
– The set of optimal routes from all sources to a
given destination
• The goal of all routing algorithms is to
discover and use the sink trees for all
routers.
Sink Tree
Shortest Path Routing
• Link metric
• Dijkstra algorithm
Flooding
• Every incoming packet is sent out on every
outgoing link except the one it arrived on.
• Termination of flooding process
– Hop counter
– Record of packet which has been flooded
• Applications of flooding
– Military application
– Comparison
Distance Vector Routing
• Each router maintains a table giving the best
known distance to each destination and
which line to be used.
• Tables are updated by exchanging
information with the neighbors.
• Items in the table
– Preferred outgoing line
– Estimate of the distance to that distance
Distance Vector Routing (cont’d)
Distance Vector Routing (cont’d)
• Converge to the correct answer, but do so
slowly.
• It reacts rapidly to good news, but leisurely
to bad news.
• The count-to-infinity problem
Count-to-Infinity Problem
Problem of DVR
• Does not take line bandwidth into account.
• Take too long to converge.
Link State Routing
• Learning about the neighbors
– Sending a special HELLO packet on each
point-to-point line
• Measuring line cost to each of its neighbors
– Round-trip time
– Traffic load
– Line bandwidth
Link State Routing (cont’d)
• Building link state packet
Link State Routing (cont’d)
• Distributing the link state packets
– Flooding is used to distribute the link state
packet.
– Each packet contains a sequence number that is
incremented for each new packet sent.
• Computing the new routes
– Dijkstra’s algorithm can be run locally to
construct the shortest path to all destinations.
Hierarchical Routing
• As networks grow in size, the router routing
tables grow proportionally.
• Each router has responsible for its region
and knows nothing about the internal
structure of other router.
Hierarchical Routing (cont’d)
Hierarchical Routing (cont’d)
• Penalty of increased path length
• The optimal number of levels for an N
router subnets is ln N.
Broadcasting Routing
• The source simply send a distinct packet to
each destination.
– Waste bandwidth
– Have to know complete list of all destinations
• Flooding
– Generate too many packets
– Consume too much bandwidth
Broadcasting Routing (cont’d)
• Multidestination routing
– Each packet contains a list of destinations.
– The destination set is partitioned among the
output lines.
• Using spanning tree
– Routers must know which of its lines belong to
the spanning tree in advance.
– Copy an incoming packet onto all the spanning
lines except the on it arrived on.
Broadcasting Routing (cont’d)
• Reverse path forwarding
– Router checks to see if the packet arrived on the
line that is normally used for sending packets to
the source of the broadcast.
Multicast Routing
• Each router computes a spanning tree
covering all other routers.
• When a process sends a multicast packet to
a group
– Examining the spanning tree of this group
– Removing all lines that do not lead to hosts that
are members of group
Multicast Routing (cont’d)
Multicast Routing (cont’d)
• Pruning spanning tree
– Reverse path forwarding
– Router with no hosts interested in a particular
group sends a PRUNE message.
– The subnet is recursively pruned.
Multicast Routing (cont’d)
• Disadvantage of algorithm, suppose that
network has n groups, each with an average
of m members.
– For each group, m pruned spanning trees must
be stored
– Total of mn trees
• Core-based tree
– A host wanting to multicast sends packets to the
core, which does the multicast along the
spanning tree.
Routing for Mobile Hosts
Routing for Mobile Hosts (cont’d)
• Mobile host
– Migratory hosts
– Roaming hosts
• All hosts are assumed to have a permanent
home location that never changes.
• Hosts also have a permanent home address
that can be used to determine their home
location.
Routing for Mobile Hosts (cont’d)
• Each area has a home agent which keeps
track of hosts whose home is in the area, but
who are currently visiting another area.
• Each area has foreign agent which keeps
track of all mobile hosts visiting this area.
Routing for Mobile Hosts (cont’d)
• Registration procedure
– Foreign agent searching
– Registration
– Foreign agent contacts the mobile host’s home
agent.
– Verification of mobile host’s home agent
– Acknowledgement from the mobile host’s
home agent
Routing for Mobile Hosts (cont’d)
• Tunneling
• Encapsulate the original packet in the
payload field of an outer packet and sends
the latter to the foreign agent.
Routing for Mobile Hosts (cont’d)
Routing in Ad Hoc Networks
• AODV (Ad hoc On-demand Distance
Vector)
– Distant relative of the Bellman-Ford distance
vector algorithm
– Considering the limited bandwidth and low
battery life
– On-demand algorithm
Routing in Ad Hoc Networks (cont’d)
• AODV algorithm maintains a table at each
node, keyed by destination and which
neighbor to send packets in order to reach
destination.
• Route request packet
Routing in Ad Hoc Networks (cont’d)
• When a route request packet arrives at a
node
– The (Source address, request ID) pair is looked
up in a local history table too see if this request
has already been seen and processed.
– Receiver looks up the destination in its route
table.
– If receiver does not know a fresh route to the
destination, it increments the Hop count field
and rebroadcast the REQUEST packet.
Routing in Ad Hoc Networks (cont’d)
Routing in Ad Hoc Networks (cont’d)
• Destination constructs a ROUTE REPLY
packet which follows the reverse path to
source.
• Each intermediate node enters this packet
into local routing table when
– No route to destination is known.
– Sequence number for destination in REPLY is
greater than the value in the routing table.
– Sequence number is equal but the new route is
shorter.
Routing in Ad Hoc Networks (cont’d)
• Problem of mobility
• Route maintenance
– Periodically, each node broadcasts a Hello
message.
– If no response is returned, router prune this link.
• Active neighbor
Routing in Ad Hoc Networks (cont’d)
Routing in Ad Hoc Networks (cont’d)
• Critical difference between AODV and
DVR
– Nodes do not send out periodic broadcasts
containing their entire routing table.
Node Lookup in Peer-to-Peer Networks
• One of p2p routing algorithm—Chord
• Each user node has an IP address that can
be hashed to an m-bit number call node
identifier.
• Successor (k) is the node identifier of the
first actual node following k around the
circle clockwise.
Node Lookup in Peer-to-Peer Networks
(cont’d)
• Finger table
– Start field = k +2i (modulo 2m)
– If key falls between k and successort (k), then
the node holding information about key is
successor (k).
– Otherwise, the entry whose start field is the
closest predecessor of key is tried.
Node Lookup in Peer-to-Peer Networks
(cont’d)
Node Lookup in Peer-to-Peer Networks
(cont’d)
• Node r joining
– New node r asks successor (r) for its predecessor.
– Insert r in between successor and predecessor.
– Successor should hand over those keys in the range
predecessor (r)-r, which now belong to r.
• Every node runs a background process that
periodically recomputes each finger by calling
successor.
Outline
• Routing Algorithm
• The Network Layer in The Internet
The Network Layer in The Internet
• Principles for network design
–
–
–
–
–
–
–
Make sure it works.
Keep it simple.
Make clear choices.
Exploit modularity.
Expect heterogeneity.
Avoid static options and parameters.
Look for a good design; it need not be perfect.
The Network Layer in The Internet
(cont’d)
– Think about scalability.
– Consider performance and cost.
• Network layer provides best-efforts way to
transport datagrams from source to
destination.
The IP Protocol
• The IPv4 header
IP Address
• IP address formats
IP Address (cont’d)
• Special IP address
Subnet
• Split a network into several parts for
internal use.
Subnet (cont’d)
• Some bits are taken away from the host
number to create a subnet number.
• For example, a university can use a 6-bit
subnet number and a 10-bit host number,
allowing fro up to 64 subnets.
• Outside the network, the subnet is not
visible, so allocating a new subnet does not
require contacting ICANN.
Subnet (cont’d)
• Subnet mask indicates the split between
network + subnet number and host.
Network Address Translation
• Shortage of IP address
• Within the company, every computer gets a
unique IP address, which is used for routing
intramural traffic.
• An address translation takes place when a
packet exits the company.
Network Address Translation (cont’d)
Network Address Translation (cont’d)
• Use TCP port to distinguish the traffic.
• TCP source port field is replaced by an
index into the NAT box’s translation table.
• Each entry contains original IP address and
original source port.
Network Address Translation (cont’d)
• Violation of the architectural model of IP
– Every IP address uniquely identifies a machine.
• NAT changes the Internet from a
connectionless network to a kind of
connection-oriented network.
• Violation of protocol layering
– layer k may not make any assumptions about
what layer k+1 has put into the payload field.
Internet Control Protocols
• Internet Control Message Protocol (ICMP)
Address Resolution Protocol
• How do IP address get mapped onto data
link layer addresses, such as Ethernet?
• Configuration file
• ARP
– Broadcast a packet onto the Ethernet asking:
Who owns IP address xxx.xxx.xxx.xxx.
– Correspondent will reply with its Ethernet
address
Address Resolution Protocol (cont’d)
Address Resolution Protocol (cont’d)
• Make ARP work more efficiently
– Local cache
– ARP request with requestor’s Ethernet address
• Transmit data to remote network.
RARP, BOOTP, and DHCP
• When a computer is booted how does it get
the IP address.
• RARP
– Broadcast a packet to ask RARP server.
– Packet cannot be forwarded by routers, so
RARP server is needed on each network.
RARP, BOOTP, and DHCP (cont’d)
• BOOTP
– Use UDP message, which are forwarded over
routers.
– Require manual configuration of tables
mapping IP address to Ethernet address.
• DHCP
– Both manual IP address assignment and
automatic assignment
RARP, BOOTP, and DHCP (cont’d)
• DHCP
OSPF—The Interior Gateway Routing
Protocol
• Routing algorithm within as autonomous
system (AS) is called an interior gateway
protocol.
• The original Internet interior gateway
protocol was distance vector protocol (RIP).
• Link state protocol replaced RIP in 1979.
• OSPF began work in 1988.
OSPF—The Interior Gateway Routing
Protocol (cont’d)
• Internet is made up of a large number of
autonomous systems.
• Each AS is operated by a different
organization and can use its own routing
algorithm.
• Every AS has a backbone area.
• All areas are connected to the backbone and
can communicate each other via backbone.
OSPF—The Interior Gateway Routing
Protocol (cont’d)
OSPF—The Interior Gateway Routing
Protocol (cont’d)
• Using flooding, each router informs all the
other router in its area of its neighbors and
costs.
• This information allows each router to
construct the graph for its area and compute
the shortest path.
• Backbone routers accept information from
the area border routers in order to compute
the best route from each backbone router to
every other router.
BGP—The Exterior Gateway Routing
Protocol
• All interior gateway protocol has to do is to move
packets as efficiently as possible without worrying
about politics.
• Exterior gateway protocol routers have to worry
about politics.
– No transit traffic through certain ASes.
– Traffic starting or ending at IBM should not transit
Microsoft.
• Policies are typically manually configured into
each BGP router and are not part of protocol.
BGP—The Exterior Gateway Routing
Protocol (cont’d)
• Stub networks
– Has only one connection to BGP graph and
cannot be used for transit traffic.
• Multiconnected networks
– Could be used for transit traffic, except that
they refuse
• Transit networks
– Willing to handle third-party packet
BGP—The Exterior Gateway Routing
Protocol (cont’d)
• Border Gateway Protocol (BGP)
– Fundamentally a distance vector protocol, but
each BGP router keeps track of the path used.
Internet Multicasting
• IP uses class D address to support multicast.
• Two kinds of group address
– Permanent address
– Temporary address
Internet Multicasting (cont’d)
•
•
•
•
224.0.0.1 All systems on a LAN
224.0.0.2 All routers on a LAN
224.0.0.5 All OSPF routers on a LAN
224.0.0.6 All designated OSPF routers on a
LAN
• Temporary groups must be created before
they can be used.
Internet Multicasting (cont’d)
• Multicasting routing is done using spanning
tree.
• Each multicast router exchanges
information with its neighbors, using a
modified distance vector protocol.
Mobile IP
• Increment of portable computers.
• Major goals
– Mobile host must be able to use its home IP
address anywhere.
– Changes to software and router are not
permitted.
– No overhead should be incurred when a mobile
host is at home.
Mobile IP (cont’d)
• See section 5.2.9 (Routing for Mobile Hosts)
• When foreign shows up at a foreign site, it
contacts the foreign host there and registers.
• The foreign host contacts the user’s home
agent and gives it a care-of-address.
Mobile IP (cont’d)
• Each foreign agent periodically broadcast
its address and type of service, which called
advertisement.
• Registration for impolite mobile hosts that
leave without saying goodbye.
IPv6
• While NAT may buy a few more years’
time, IP in its current form (IPv4) is
numbered.
• IETF issued a call for proposal and
discussion in RFC 1550.
• IPv6 is not compatible with IPv4, but it is
compatible with other auxiliary Internet
protocol.
IPv6 (cont’d)
• Main features
–
–
–
–
–
Longer addresses
Simplification of the header
Better support for options
Security
Quality of service
IPv6 (cont’d)
• The IPv6 fixed header
IPv6 (cont’d)
• New notation of 16-byte address
– 8000:0000:0000:0000:0123:4567:89AB:CDEF
– 8000::123:4567:89AB:CDEF
• IPv4 can be written as ::192.168.20.46
• Vanishment of IPv4 headers
– IHL
– Protocol
– Checksum
IPv6 (cont’d)
• Extension header is encoded as (Type,
Length, Value) tuple.
– Type is a 1-byte field telling which option this
is.
– Length is a 1-byte field telling how long the
value is.
– Value is any information required.
IPv6 (cont’d)
• IPv6 extension header
IPv6 (cont’d)
• Controversies
–
–
–
–
Hop limit field length
Maximum packet size
Checksum
Mobile issue
Section2. The Internet Transport Protocols:
TCP
Introduction to TCP
• Function of providing reliable end-to-end
byte stream over an unreliable internetwork.
• Lack of IP
– No guarantee that packets will be delivered
properly.
– Packets may arrive in the wrong order.
TCP Service Model
• TCP service is obtained by both sender and
receiver creating sockets.
• Each socket has IP address and a 16-bit
number called port.
• Port number below 1024 are called wellknown ports and reserved for standard
service.
TCP Service Model (cont’d)
• Well-Known Ports
TCP Service Model (cont’d)
• Characteristics of TCP connections
– Full duplex
– Point-to-point
– Byte stream, not a message stream
TCP Service Model (cont’d)
• A key feature of TCP is that every packet
on a TCP connection has its own 32-bit
sequence number.
• TCP segment consisting of fixed 20-byte
header is used for exchanging data between
sender and receiver.
TCP Service Model (cont’d)
• Segment size issue
– Fit in the 65515-byte IP paylo.ad
– Can’t exceed maximum transfer unit (MTU).
– MTU is generally 1500 bytes.
• The basic protocol used by TCP is the
sliding window protocol.
– Timer
– Acknowledgement number
TCP Segment Header
TCP Connection Establishment
• Three-way handshake.
TCP Connection Release
• To release a connection , either party can
send a TCP segment with the FIN bit set.
• When the FIN is acknowledged, that
direction is shut down for new data.
• Normally, four TCP segments are required
to release a connection.
TCP Connection Management
Modeling
TCP Transmission Policy
TCP Transmission Policy (cont’d)
• When the window size is 0, the sender stop
sending data to receiver except
– Urgent data may be sent.
– Send a 1-byte segment to make the receiver
reannounce the next byte expected and window
size.
TCP Transmission Policy (cont’d)
• Consider the worst case in performance
issue.
• For receivers
– Delay acknowledgements and window updates
for 500 msec in the hope of acquiring some
data.
• For senders
– Nagle’s algorithm
TCP Transmission Policy (cont’d)
• Silly window syndrome
– Data are passed to the sending TCP entity in
large blocks, but an interactive application on
the receiving side reads data 1 byte at a time.
TCP Transmission Policy (cont’d)
• Clark’s algorithm
– It forces window update to wait until it has a
decent amount of space available.
• Combination of Nagle’s and Clark’s
algorithm.
TCP Congestion Control
• When the load offered to any network is
more than it can handle, congestion builds
up.
• TCP achieves congestion control by
dynamically manipulating the window size.
• First step of congestion control: detection.
• All the Internet TCP algorithms assume that
timeouts are caused by congestion.
TCP Congestion Control (cont’d)
TCP Congestion Control (cont’d)
• Two potential problems—network capacity
and receiver capacity.
• Each sender maintains two windows—
receiver window and congestion window.
• The number of bytes that may be sent is the
minimum of the two windows.
TCP Congestion Control (cont’d)
• Slow start
TCP Timer Management
• Retransmission timer
• Difficulties of setting retransmission timer
TCP Timer Management (cont’d)
• Estimate RTT
RTT  TRR  (1   ) M

• Where  is a smothing
factor that
determines how much weight is given to the
old value.
• TCP uses ßRTT to estimate retransmission
timer.
TCP Timer Management (cont’d)
• Jacobson proposed proposed to use mean
deviation as a cheap estimator of the
standard deviation.
• D  D  (1   ) | RTT  M |
Timeout  RTT  4  D
TCP Timer Management (cont’d)
• Potential problem
– When the ack of retransmission packet comes
in, it is unclear whether the ack refers to the
first transmission or a later one.
– Karn’s algorithm
• Persistence timer is design to prevent the
deadlock.
• Keepalive timer.
Wireless TCP and UDP
• Problem due to congestion control.
• TCP assumes that timeouts are caused by
congestion, not by lost packets.
• A packet is lost on a wired network, the
sender should slow down.
• When one is lost on a wireless network, the
sender should try harder.
Wireless TCP and UDP (cont’d)
• Bakne and Badrinath propose indirect TCP
which split the TCP connection into two
separate connections.
Wireless TCP and UDP (cont’d)
• The advantage of this scheme is that
bothconnections are now homogeneous.
• Timeouts on the first connection can slow
the sender down, whereas timeouts on the
second one can speed it up.z
• The disadvantage of the scheme is that it
violates the semantics of TCP.
Transactional TCP
• Efficiency problem of TCP