Transcript ppt

Introduction to Computer
Networks
CMPE 150
Fall 2005
Lecture 23
CMPE 150- Introduction to Computer Networks
1
Announcements
• Homework 4 due on Wed.,11.23.05.
• No class on Friday, 11.25.05.
• We will have a “real” lab next week.
CMPE 150- Introduction to Computer Networks
2
Last Class…
•
•
•
•
Routing (cont’d).
Finished DV.
Link State.
Hierarchical routing.
CMPE 150- Introduction to Computer Networks
3
Today
• Finish routing.
– Many-to-many routing.
• Broadcast.
• Multicast.
• Internetworking.
CMPE 150- Introduction to Computer Networks
4
Many-to-Many Routing
• Support many-to-many communication.
• Example applications: multi-point data
distribution, multi-party teleconferencing.
CMPE 150- Introduction to Computer Networks
5
Broadcasting
• Send to ALL destinations.
• Several possible routing mechanisms to broadcasting.
• Simplistic approach: send separate packet to
each destination.
– Simple but expensive.
– Source needs to know about all destinations.
• Flooding:
– May generate too many duplicates (depending on
node connectivity).
CMPE 150- Introduction to Computer Networks
6
Multidestination Routing
•
•
Packet contains list of destinations.
Router checks destinations and determines on
which interfaces it will forward packet.
–
–
Router generates new copy of packet for each output
line and includes in packet only the appropriate set of
destinations.
Eventually, packets will only carry 1 destination.
CMPE 150- Introduction to Computer Networks
7
Spanning Tree Routing
• Use spanning tree (sink tree) rooted at
broadcast initiator.
• No need for destination list.
• Each on spanning tree forwards packets
on all lines on the spanning tree (except
the one the packet arrived on).
• Efficient but needs to generate the
spanning tree and routers must have that
information.
CMPE 150- Introduction to Computer Networks
8
Reverse Path Forwarding
•
•
Routers don’t have to know spanning tree.
Router checks whether broadcast packet
arrived on interface used to send packets to
source of broadcast.
–
–
If so, it’s likely that it followed best route and thus not
a duplicate; router forwards packet on all lines.
If not, packet discarded as likely duplicate.
CMPE 150- Introduction to Computer Networks
9
Broadcast Routing
Reverse path forwarding. (a) A subnet. (b) a Sink tree. (c) The
tree built by reverse path forwarding.
CMPE 150- Introduction to Computer Networks
10
Multicasting
• Special form of broadcasting:
– Instead of sending messages to all nodes, send
messages to a group of nodes.
• Multicast group management:
– Creating, deleting, joining, leaving group.
– Group management protocols communicate group
membership to appropriate routers.
CMPE 150- Introduction to Computer Networks
11
Multicast Routing
• Each router computes spanning tree covering all
other participating routers.
– Tree is pruned by removing branches that do not
contain any group members.
2
2
1
1,2
1,2
2
1
1
2
1
2
2
2
2
1
1
2
1
1
1
1
1,2
1,2
2
1
CMPE 150- Introduction to Computer Networks
2
12
Shared Tree Multicasting
• Source-rooted tree approaches don’t
scale well!
– 1 tree per source, per group!
– Routers must keep state for m*n trees, where m
is number of sources in a group and n is number
of groups.
• Core-based trees: single tree per group.
– Host unicast message to core, where message is
multicast along shared tree.
– Routes may not be optimal for all sources.
– State/storage savings in routers.
CMPE 150- Introduction to Computer Networks
13
Internetworking
CMPE 150- Introduction to Computer Networks
14
Internetworking
• What is it?
– Connecting networks together forming a single
“internet”.
CMPE 150- Introduction to Computer Networks
15
Connecting Networks
• A collection of interconnected networks.
CMPE 150- Introduction to Computer Networks
16
How Networks Differ
5-43
CMPE 150- Introduction to Computer Networks
17
How Networks Can Be Connected
•
•
(a) Two Ethernets connected by a switch.
(b) Two Ethernets connected by routers.
CMPE 150- Introduction to Computer Networks
18
How to Internet?
• Connection-oriented versus connectionless
internetworking.
• Connection oriented internetworking:
– Based on VC concatenation.
• Connectionless internetworking follows the
datagram model.
CMPE 150- Introduction to Computer Networks
19
Concatenated Virtual Circuits
Gateway
. Builds VC crossing the different networks.
. Use of gateways to perform necessary conversions.
CMPE 150- Introduction to Computer Networks
20
Connectionless Internetworking
. Follows datagram model.
. Packets from Host X to Host Y may follow different routes.
. Gateways make routing decisions and perform translations.
CMPE 150- Introduction to Computer Networks
21
Translating versus “Gluing”
• Translation: converting between different
protocols.
• Hard!
• Alternative: “gluing”.
– I.e., using the same network layer protocol
everywhere.
– That’s what IP does!
CMPE 150- Introduction to Computer Networks
22
Tunneling
• Interconnecting source and destination on
separate networks but of the same type.
S
D
CMPE 150- Introduction to Computer Networks
23
Tunneling Analogy
CMPE 150- Introduction to Computer Networks
24
More Tunneling …
CMPE 150- Introduction to Computer Networks
25
Internetwork Routing: Example
• (a) An internetwork. (b) A graph of the internetwork.
CMPE 150- Introduction to Computer Networks
26
Internetwork Routing
• Inherently hierarchical.
– Routing within each network: interior gateway
protocol (IGP).
– Routing between networks: exterior gateway
protocol (EGP).
• Within each network, different routing
algorithms can be used.
• Each network is autonomously managed
and independent of others: autonomous
system (AS).
CMPE 150- Introduction to Computer Networks
27
Internetwork Routing (Cont’d)
• Typically, packet starts in its LAN. Gateway
receives it (broadcast on LAN to “unknown”
destination).
• Gateway sends packet to gateway on the
destination network using its routing table. If it
can use the packet’s native protocol, sends
packet directly. Otherwise, tunnels it.
CMPE 150- Introduction to Computer Networks
28
Fragmentation
• Happens when internetworking.
• Network-specific maximum packet size.
– Width of TDM slot.
– OS buffer limitations.
– Protocol (number of bits in packet length field).
• Maximum payloads range from 48 bytes (ATM
cells) to 64Kbytes (IP packets).
CMPE 150- Introduction to Computer Networks
29
Problem
• What happens when large packet wants to
travel through network with smaller
maximum packet size? Fragmentation.
• Gateways break packets into fragments;
each sent as separate packet.
• Gateway on the other side have to
reassemble fragments into original packet.
• 2 kinds of fragmentation: transparent and
non-transparent.
CMPE 150- Introduction to Computer Networks
30
Types of Fragmentation
• (a) Transparent fragmentation.
Nontransparent fragmentation.
CMPE 150- Introduction to Computer Networks
(b)
31
Transparent Fragmentation
• Small-packet network transparent to other
subsequent networks.
• Fragments of a packet addressed to the
same exit gateway, where packet is
reassembled.
– OK for concatenated VC internetworking.
• Subsequent networks are not aware
fragmentation occurred.
• ATM networks (through special hardware)
provide transparent fragmentation.
CMPE 150- Introduction to Computer Networks
32
Problems with Transparent
Fragmentation
• Exit gateway must know when it received
all the pieces.
– Fragment counter or “end of packet” bit.
• Some performance penalty but requiring
all fragments to go through same gateway.
• May have to repeatedly fragment and
reassemble through series of small-packet
networks.
CMPE 150- Introduction to Computer Networks
33
Non-Transparent
Fragmentation
• Only reassemble at destination host.
– Each fragment becomes a separate packet.
– Thus routed independently.
• Problems:
– Hosts must reassemble.
– Every fragment must carry header until it reaches
destination host.
CMPE 150- Introduction to Computer Networks
34
Keeping Track of Fragments
•
•
Fragments must be numbered so that
original data stream can be
reconstructed.
Tree-structured numbering scheme:
–
–
–
–
Packet 0 generates fragments 0.0, 0.1, 0.2, …
If these fragments need to be fragmented later
on, then 0.0.0, 0.0.1, …, 0.1.0, 0.1.1, …
But, too much overhead in terms of number of
fields needed.
Also, if fragments are lost, retransmissions can
take alternate routes and get fragmented
differently.
CMPE 150- Introduction to Computer Networks
35
Keeping Track of Fragments
(Cont’d)
• Another way is to define elementary
fragment size that can pass through every
network.
• When packet fragmented, all pieces equal
to elementary fragment size, except last
one (may be smaller).
• Packet may contain several fragments.
CMPE 150- Introduction to Computer Networks
36
Fragmentation: Example
•
•
•
•
Fragmentation when the elementary data size is 1 byte.
(a) Original packet, containing 10 data bytes.
(b) Fragments after passing through a network with maximum
packet size of 8 payload bytes plus header.
(c) Fragments after passing through a size 5 gateway.
CMPE 150- Introduction to Computer Networks
37
Keeping Track of Fragments
• Header contains packet number, number of first
fragment in the packet, and last-fragment bit.
Last-fragment bit
E F G H I
27 0 1 A B C D
Number of
first fragment
Packet number
27 0
0 A B
C D
E
F
G
H
1 byte
J
(a) Original packet
with 10 data bytes.
27 8
1 I
J
(b) Fragments after passing through network
with maximum packet size = 8 bytes.
CMPE 150- Introduction to Computer Networks
38
The Internet
CMPE 150- Introduction to Computer Networks
39