Transcript Ethernet Switch

Introduction
to
Computer Networks
Lecture 6: Packet Switching
University of Tehran
Dept. of EE and Computer Engineering
By:
Dr. Nasser Yazdani
Univ. of Tehran
Introduction to Computer Network
1
outline




Store-and-Forward Switches
Bridges and Extended LANs
Packet switching
Cell Switching

Segmentation and Reassembly
Univ. of Tehran
Introduction to Computer Network
2
Scalable Networks

Limitation of directly connected networks.



Limit on the number of hosts; For example,
Ethernet is 1024 hosts.
Limit on the geographical area of LANs. 2500
m in Ethernet.
Solution: This is like telephone network.
Then, use Switches.
Univ. of Tehran
Introduction to Computer Network
3
Switches

forwards packets from input port to output port
T3
T3
STS-1
Input
ports


port selected based on address in packet header
If two packets are destined to the same output,
one must be buffered (queued). This is called
contention.


Switch
T3
T3
STS-1
Output
ports
Needs some kinds of scheduling for packet delivery.
If the buffer overflow, it will be a congestion.
Univ. of Tehran
Introduction to Computer Network
4
An Ethernet Network
Router
Problem:
Outside
world
Shared
network limits throughput.
Lots of collisions reduces efficiency.
Univ. of Tehran
Introduction to Computer Network
5
Ethernet Switch
Ethernet
Switch/Bridge
Router
• If
only one computer per port, no collisions can take
place (each cable is now a self-contained point-to-point
Ethernet link).
Problem? How to determine the output port?
Univ. of Tehran
Introduction to Computer Network
6
Ethernet Switching
Ethernet
Switch
Benefits:
Router Outside
world
 Number of collisions is reduced. If only one computer
per port, no collisions can take place (each cable is now a
self-contained point-to-point Ethernet link).
 Capacity is increased: the switch can forward multiple
frames to different computers at the same time.
Univ. of Tehran
Introduction to Computer Network
7
Interconnecting LANs



Bridges (aka Ethernet switches) were
introduced to allow the interconnection of
several local area networks (LANs) without a
router.
By partitioning a large LAN into multiple smaller
networks, there are fewer collisions, and more
parallel communications.
It is now common for the port of an Ethernet
switch to connect to just one (or a small
number of) hosts.
Univ. of Tehran
Introduction to Computer Network
8
Bridges and Extended LANs


LANs have physical limitations (e.g., 2500m)
Connect two or more LANs with a switch


accept and forward strategy
level 2 connection (does not add packet header)
A
B
C
Port 1
Bridge
Port 2
X

Y
Z
Ethernet Switch is called Bridge traditionally.
Univ. of Tehran
Introduction to Computer Network
9
One Ethernet Switch in
“Packard”
Univ. of Tehran
Introduction to Computer Network
10
Output ports? Learning Bridges


Maintain a forwarding table for hosts.
Port
Host
1
A
1
B
1
C
2
X
2
Y
2
X
A
B
C
Port 1
Bridge
Port 2
X
Y
Z
How to populate table.


Manually by system admin. (not good)
Learn table entries based on source address (flexible).
Univ. of Tehran
Introduction to Computer Network
11
Learning Bridges, (Forwarding)
1.
2.
3.



If the frame destination address is in the
routing table, forward the frame to the
corresponding port.
Otherwise, broadcast the frame.
Update the table if the source address is not in
the table.
The table is learned by examining the
Ethernet SA of arriving packets.
Table is an optimization; need not be
complete
Always forward broadcast frames
Univ. of Tehran
Introduction to Computer Network
12
Ethernet Switching
Learning addresses
B
A
C
2 3
1
Ethernet
Switch
6
I
J
Ethernet
Switch
Univ. of Tehran
4
5
K
D
J F
E
F
G
Ethernet
Switch
Switch learns that ‘F’ is
reachable through port 5
N
L
M
O
H
Outside
Q Router
world
P
Ethernet
Switch
Introduction to Computer Network
13
Ethernet Switching
Ethernet address
Port
A
1
Learning addresses
B
A
C
2 3
1
Ethernet
Switch
6
I
J
B
2
C
3
D
4
E, F, G, H, Q
5
I, J, K, L, M, N, O, P
6
D
E
F
4
5
K
G
Ethernet
Switch
L
M
N
H
Outside
Q Router world
O
P
Ethernet
Switch
Ethernet
Switch
Q: How do we prevent loops?
Univ. of Tehran
Introduction to Computer Network
14
Preventing loops
Spanning Tree Protocol


The network of bridges is a graph.
The Spanning Tree Protocol finds a subgraph
that spans all the vertices without loops.



Spanning => all bridges are included.
Tree => the topology has no loops.
The distributed protocol runs:


To determine which bridge is the root of the
tree, and
Each bridge turns off ports that are not part of
the tree.
Univ. of Tehran
Introduction to Computer Network
15
Spanning Tree Algorithm

A
Spanning tree
B
B3
C
B5
D
B2
B7
E
K
F
B1
G
H
B6
B4
I

A distributed spanning tree algorithm
select which bridges actively forward
 developed by Radia Perlman
 Univ.
now
IEEE 802.1 specification
of Tehran
Introduction to Computer Network
J

16
Example Spanning Tree
B8
B3
Protocol operation:
B5
B7
B2
3.
B1
B6
Univ. of Tehran
1.
2.
B4
Introduction to Computer Network
Picks a root
For each LAN,
picks a designated
bridge that is closest
to the root.
All bridges on a LAN
send packets towards
the root via the
designated bridge.
17
Example Spanning Tree
B8
Spanning Tree:
B3
B5
B1
B7
B2
B2
B4
B5
B7
B1
Root
B6
Univ. of Tehran
B8
B4
Introduction to Computer Network
18
Algorithm Overview




Each bridge has unique id (e.g., B1, B2, B3)
Select bridge with smallest id as root
Select bridge on each LAN closest to root as
designated bridge (use id to break ties)
Each bridge forwards
frames over each LAN
for which it is the
designated bridge
A
B
B3
C
B5
D
B2
B7
E
K
F
B1
G
H
B6
B4
I
J
Univ. of Tehran
Introduction to Computer Network
19
Algorithm Details

Bridges exchange configuration messages





id for bridge sending the message
id for what the sending bridge believes to be root
bridge
distance (hops) from sending bridge to root bridge
Each bridge records current best
configuration message for each port
Initially, each bridge believes it is the root
Univ. of Tehran
Introduction to Computer Network
20
Algorithm Detail (cont)

When learn not root, stop generating config
messages


in steady state, only root generates configuration
messages
When learn not designated bridge, stop
forwarding config messages

in steady state, only designated bridges forward
config messages
Root continues to periodically send config
messages
 If any bridge does not receive config message
after a period of time, it starts generating
Univ.
of Tehranmessages
Introduction
to Computer
21
config
claiming
toNetwork
be the root

Spanning Tree Protocol
1. Each bridge periodically sends a configuration message out of every
port. A message contains: (ID of sender, ID of root, distance from
sender to root).
2. Initially, every bridge claims to be root and sends a distance field of 0.
3. A bridge keeps sending the same message (periodically) until it hears a
“better” message. “Better” means:
•
•
•
A root with a smaller ID
A root with equal ID, but with shorter distance
The root ID and distance are the same as we already have, but the
sending bridge has a smaller ID.
4. Once a bridge hears a better configuration message, it stops
generating its own messages, and just forwards ones that it receives
(adding 1 to the distance).
5. If the bridge realizes that it is not the designated bridge for a LAN, it
stops sending configuration messages to that LAN.
Eventually:
•
•
Only the root bridge generates configuration messages,
Other bridges send configuration messages to LANs for which they are the
designated bridge.
Univ. of Tehran
Introduction to Computer Network
22
Broadcast and Multicast

Forward all broadcast/multicast frames



current practice
Learn when no group members
downstream
Accomplished by having each member of
group G send a frame to bridge multicast
address with G in source field
Univ. of Tehran
Introduction to Computer Network
23
Limitations of Bridges

Do not scale


spanning tree algorithm does not scale
broadcast does not scale

Do not accommodate heterogeneity

Caution: beware of transparency
Univ. of Tehran
Introduction to Computer Network
24
Packet Switching Schemes


Learning bridges are a special case. We need
a general form for packet switching or
specifying the output in the packet.
They are three format for specifying the
output in the a packet



Source routing: List entire path in the packet
Virtual circuits: like telephone circuit, identify
packets with ids.
Datagram: Put only destination address in
packets’ headers.
Univ. of Tehran
Introduction to Computer Network
25
Source Routing

List entire path in packet


Router processing, one option




Driving directions (north 3 hops, east, etc..)
Examine first step in directions
Strip first step from packet
Forward to step just stripped off
Or the address can be implemented by a
linked list in the packet header.
Univ. of Tehran
Introduction to Computer Network
26
Source Routing Example
Packet
4,3
3,4,3
2
Sender
1
2
R1
4
3
1
R1
3
4
3
2
1
R2
4
3
Receiver
All routing information is provided by the source.
Univ. of Tehran
Introduction to Computer Network
27
Source Routing

Advantages


Disadvantages



Switches can be very simple and fast
Variable (unbounded) header size
Sources must know or discover topology (e.g.,
failures)
Typical use

Debugging and management
Univ. of Tehran
Introduction to Computer Network
28
Virtual Circuits/Tag Switching



Use the telephone model virtual circuits
Each flow is identified by a Virtual Circuits Identifier (VCI).
Connection setup phase, Signaling




Each packet carries connection ID


Use other means to route setup request
Each router allocates flow ID on local link
Creates mapping of inbound flow ID/port to outbound flow ID/port
Sent from source with 1st hop connection ID
Router processing




Lookup flow ID – simple table lookup
Replace flow ID with outgoing flow ID
Forward to output port
Swap labels
Univ. of Tehran
Introduction to Computer Network
29
Virtual Circuit
Connection setup establishes a path through switches



A virtual circuit ID (VCI) identifies path
Uses packet switching, with packets containing VCI
VCIs are often indices into per-switch connection tables;
change at each hop
VC1
VC2
1
2
VC1
In, VC Out, VC
1, 1
4, 1
1, 2
4, 3
Univ.2,
of 1
Tehran 4, 2
4
VC1
VC2
3
4
1
VC3
2
VC1
3
VC2
VC1
….
Introduction to Computer Network
30
Virtual Circuits Examples
In-port
Lookup table for
Switch R1
Packet
Sender
In-VCI
Out-port
Out-VCI
1
5
3
7
4
11
0
8
5
7
1
2
2
R1
R2
4
3
1
4
1,7  4,2
3
2
1,5  3,7
2
1
R3
4
3
Receiver
6
2,2  3,6

Subsequence packets follow the same circuit
Univ. of Tehran
Introduction to Computer Network
31
Virtual Circuits

Advantages






Disadvantages



More efficient lookup (simple table lookup)
More flexible (different path for each flow)
Can reserve bandwidth at connection setup
Easier for hardware implementations
Small per-packet header overhead.
Still need to route connection setup request
More complex failure recovery – must recreate
connection state
Typical uses


ATM – combined with fix sized cells
MPLS – tag switching for IP networks
Univ. of Tehran
Introduction to Computer Network
32
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
Univ.
of Tehran resources.
Introduction to Computer Network
33
Datagram Switching





No connection setup phase since it is costly.
Each packet is forwarded independently
Sometimes called connectionless model
Analogy:
postal
system Packet
Each switch
maintains a
forwarding
(routing)
table
Univ. of Tehran
Sender
R
R
1
2
R1
4
3
1
2
R1
4
R4
3
R3
R
2
1 R2
3
4
Receiver
R
R3
Introduction to Computer Network
34
Datagram Model




There is no round trip time delay waiting 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.
Univ. of Tehran
Introduction to Computer Network
35
Cell Switching (ATM)





Connection-oriented packet-switched network
Used in both WAN and LAN settings
Signaling (connection setup) Protocol: Q.2931
Specified by ATM forum
Packets are called cells


5-byte header + 48-byte payload
Commonly transmitted over SONET

other physical layers possible
Univ. of Tehran
Introduction to Computer Network
36
Variable vs Fixed-Length
Packets

No Optimal Length



if small: high header-to-data overhead
if large: low utilization for small messages
Fixed-Length Easier to Switch in
Hardware


simpler
enables parallelism
Univ. of Tehran
Introduction to Computer Network
37
Big vs Small Packets

Small Improves Queue behavior

finer-grained pre-emption point for scheduling link






maximum packet = 4KB
link speed = 100Mbps
transmission time = 4096 x 8/100 = 327.68us
high priority packet may sit in the queue 327.68us
in contrast, 53 x 8/100 = 4.24us for ATM
near cut-through behavior





two 4KB packets arrive at same time
link idle for 327.68us while both arrive
at end of 327.68us, still have 8KB to transmit
in contrast, can transmit first cell after 4.24us
at end of 327.68us, just over 4KB left in queue
Univ. of Tehran
Introduction to Computer Network
38
Big vs Small (cont)

Small Improves Latency (for voice)





voice digitally encoded at 64Kbps (8-bit samples at
8KHz)
need full cell’s worth of samples before sending cell
example: 1000-byte cells implies 125ms per cell (too
long)
smaller latency implies no need for echo cancellors
ATM Compromise: 48 bytes = (32+64)/2
Univ. of Tehran
Introduction to Computer Network
39
Cell Format


User-Network Interface (UNI)
4
8
16
3
1
8
384 (48 bytes)
GFC
VPI
VCI
Type
CLP
HEC (CRC-8)
Payload
host-to-switch format







GFC: Generic Flow Control (still being defined)
VCI: Virtual Circuit Identifier
VPI: Virtual Path Identifier
Type: management, congestion control, AAL5
(later)
CLP: Cell Loss Priority
HEC: Header Error Check (CRC-8)
Network-Network Interface (NNI)
switch-to-switch format
Univ.
Tehranbecomes part
Introduction
to Computer
 ofGFC
of VPI
fieldNetwork

40
Segmentation and Reassembly

ATM Adaptation Layer (AAL)



AAL 1 and 2 designed for applications that need
guaranteed rate (e.g., voice, video)
AAL 3/4 designed for packet data
AAL 5 is an alternative standard for packet data
AAL
AAL
…
…
ATM
Univ. of Tehran
ATM
Introduction to Computer Network
41
AAL 3/4

Convergence Sublayer Protocol Data Unit (CSPDU)




8
8
16
< 64 KB
CPI
Btag
BASize
User data
0– 24
8
8
16
Pad
0
Etag
Len
CPI: common part indicator (version field)
Btag/Etag:beginning and ending tag
BAsize: hint on amount of buffer space to allocate
Length: size of whole PDU
Univ. of Tehran
Introduction to Computer Network
42
Cell Format
40
ATM header






4
10
Type
SEQ
MID
352 (44 bytes)
Payload
6
10
Length
CRC-10
Type


2
BOM: beginning of message
COM: continuation of message
EOM end of message
SEQ: sequence of number
MID: message id
Length: number of bytes of PDU in this cell
It uses 4 extra bytes for SAR, not good!
Univ. of Tehran
Introduction to Computer Network
43
AAL5

CS-PDU Format




< 64 KB
0– 47 bytes
16
16
32
Data
Pad
Reserved
Len
CRC-32
pad so trailer always falls at end of ATM cell
Length: size of PDU (data only)
CRC-32 (detects missing or misordered cells)
Cell Format

end-of-PDU bit in Type field of ATM header
Univ. of Tehran
Introduction to Computer Network
44
ATM Layers
Aplication
PHY in ATM is usually
SONET.
TCP
Higher
Layers
IP
AAL
DLL
ATM
PHY
PHY
TCP/IP
ATM
• Sending IP over ATM is done by address translation.
• ATM is also used in LAN. Then, It tries to emulate LAN.
• The Technology is called LANE.
Univ. of Tehran
Introduction to Computer Network
45