Transcript ppt format

Packet Switching
Outline
Store-and-Forward Switches
Bridges and Extended LANs
Cell Switching
Segmentation and Reassembly
CS380
Int. to Comp. Networks
Switching – Part I
1
Packet Switching
• Problem: “Not all networks are Directly Connected”
• Directly connected networks have two limitations:
- number of hosts that can be accommodated
- geographic limitation
• Goal – networks that are global in scale
• Like Telephone using (circuit) switches,
we use packet switches(store-and-forward) that take
packets that arrive on an input and forward (switch) them
to the right output. Two ways to do it:
- connection
- connectionless
CS380
Int. to Comp. Networks
Switching – Part I
2
Packet Switching
• Key problems that a switch must deal with:
• Contention – packet arrival exceeds packet dispatch (in this chapter)
• Congestion – packets discards (due to running out of buffer space) too
frequently (in future chapter)
• Key issues covered
- forwarding
- contention
• Two switching technologies
- LAN switching – Popular in LAN, evolved from
Ethernet bridging
- Asynchronous Transfer Mode(ATM) – popular in WAN
CS380
Int. to Comp. Networks
Switching – Part I
3
Star Topology
• Large numbers of switches can be connected
• Connecting switches/hosts using Point-to-Point links
• Scaling doesn’t always mean performance  (switches
designed with enough aggregate capacity)
CS380
Int. to Comp. Networks
Switching – Part I
4
Scalable Networks
• Switch
– forwards packets from input port to output port, this is referred to as
either switching or forwarding. In terms of the OSI architecture, it is
the main function of the network layer.
– port selected based on address in packet header
T3
T3
STS-1
Input
ports
Switch
T3
T3
STS-1
Output
ports
• Advantages
– cover large geographic area (tolerate latency)
– support large numbers of hosts (scalable bandwidth)
CS380
Int. to Comp. Networks
Switching – Part I
5
Switches
Q. How does the switch determine output port?
A. By looking at an identifier in the packet header
Three approaches:
Virtual Circuit (connection-oriented)
Datagram (connectionless)
Source Routing
CS380
Int. to Comp. Networks
Switching – Part I
6
Virtual Circuits
0 Switch 1
1
3
2
3
5
2 Switch 2
1
11
•Explicit connection setup
(and tear-down) phase
•Subsequence packets
follow same circuit
•Sometimes called
connection-oriented model
0
Host A
•Two types:
- PVC Permanent Virtual Circuit
•Need network administrator
configure the state
- SVC “Signalled” Virtual Circuit
•Send a message into the
network(signalling)
• Analogy: phone call
• Each switch maintains a VC table
CS380
Int. to Comp. Networks
Switching – Part I
7
1
0 Switch 3
3
4
2
Host B
7
Virtual Circuits Tables
0 Switch 1
1
3
Incoming
Interface
2
1
VC Table
for Switch 1
2
2
5
3
Outgoing
VCI
3
1
1
0
VC Table for Switch 2
Incoming
Interface
3
1
Host A
VCI Virtual Circuit Identifier (0, 1, 2, …)
• combined with incoming/outgoing
interface (e.g. 0, 1, 2, 3)can uniquely
identify the virtual connection (VC)
• assigned whenever a new connection
is created
• not a globally significant identifier
for the VC; rather, only on a given link
CS380
Int. to Comp. Networks
Outgoing
Interface
1
3
...
11
Switch 2
Incoming
VCI
0
2
Switching – Part I
Incoming
VCI
11
2
Outgoing
Interface
0
0
Outgoing
VCI
0
2
...
7
1
0 Switch 3
3
4
2
Host B
8
Example: Give Virtual Circuit
Tables for all switches
Host C
0 Switch 1
1
3
Host B
Host D
2
0
Host A
Connections
Established
in the order of
(a) to (d)
Switch
(a) Host A
connects to
Host E
Host H
Incoming
Interface# VCI#
Outgoing
Interface# VCI#
1
2
3
2
0
3
0
0
0
1
2
2
0
0
0
(b) Host C
connects to
Host G
1
2
3
0
0
3
0
1
1
1
2
0
1
1
0
(c) Host G
connects to
Host A
1
2
3
1
2
0
2
2
1
2
0
3
1
2
2
(d) Host D
connects to
Host E
2
3
1
3
0
3
2
2
3
1
CS380
Int. to Comp. Networks
Host E
1 Switch 2
2
0
Host G
3
VC Table
for Switch 1
VC Table
for Switch 2
VC Table
for Switch 3
Switching – Part I
2 Host F
1
Switch 3
3
Incoming
Interface#
Incoming
VCI#
Outgoing
Interface#
Outgoing
VCI#
0
1
2
0
2
0
1
2
1
1
1
0
Incoming
Interface#
Incoming
VCI#
Outgoing
Interface#
Outgoing
VCI#
0
0
1
2
0
1
0
2
2
2
2
0
0
1
3
2
Incoming
Interface#
Incoming
VCI#
Outgoing
Interface#
Outgoing
VCI#
0
3
3
3
1
0
1
3
3
2
0
2
2
0
0
1
9
Virtual Circuit Model
• Typically wait full RTT for connection setup before
sending first data packet.
• While the connection request contains the full address for
destination, each data packet contains only a small
identifier, making the per-packet header overhead small.
• If a switch or a link in a connection fails, the connection is
broken and a new one needs to be established.
• Connection setup provides an opportunity to reserve
resources(QoS reservations).
• ATM utilizes virtual circuits
CS380
Int. to Comp. Networks
Switching – Part I
10
Datagrams
•Idea – provide just
Host D
Host E
0 Switch 1
3
Host C
Host F
1
2 Switch 2
2
3
1
0
Host A
Forwarding
table for
Switch 2
destination
Port
A
3
B
0
C
3
D
3
E
2
F
1
G
0
H
0
CS380
Int. to Comp. Networks
Host G
1
0 Switch 3 Host B
3
2
enough information for the
switch to forward the
packet
• No setup time
• Independent forwarding
packets
• Analogy – postal system
• Each switch maintains a
forwarding (routing) table.
More routing in the next
chapter
Host H
Switching – Part I
11
Workstation Used As a Switch
I/O bus
CPU
Interface 1
Interface 2
Interface 3
Main memory
Main problem: all packets must pass through a single point of
contention. (I/O bus, read to/write from the main memory)
CS380
Int. to Comp. Networks
Chapter 3, Figure 9Switching – Part I
Forwarding Table for Nodes
D
A
B
C
E
• Give the datagram forwarding table for each node:
Node A
Node B
Node C
Node D
Node E
Destination
Next Hop
Destination
Next Hop
Destination
Next Hop
Destination
Next Hop
Destination
Next Hop
B
B
A
A
A
B
A
C
A
C
C
B
C
C
B
B
B
C
B
C
D
B
D
C
D
D
C
C
C
C
E
B
E
C
E
E
E
C
D
C
CS380
Int. to Comp. Networks
Switching – Part I
13
Datagram Model
• There is no round trip time delay for connection setup; a
host can send data as soon as it is ready.
• Source host has no way of knowing if the network is
capable of delivering a packet or if the destination host is
even up.
• Since packets are treated independently, it is possible to
route around link and node failures.
• Since every packet must carry the full address of the
destination, the overhead per packet is higher than for the
connection-oriented model.
CS380
Int. to Comp. Networks
Switching – Part I
14
Source Routing
0 Sw itch 1
3
0
1
3
2 Sw itch 2
2
3 0 1
3
1
1
2
1 3 0
0
Host A
0 1 3
1
0 Sw itch 3
3
2
Host B
• Source host contains all
information
- rotates data
CS380
Int. to Comp. Networks
Switching – Part I
• Does not need to use either
VCs or Datagrams although
can be used in combination
with
- IP for instance uses
datagrams but has a
source routing option
- Can be used for VC
setup
15