Transcript chapter3

Advance Computer Networks
Chapter 3: Packet Switching
Packet Switching
• Directly connected networks limit the geographical area
covered and # of hosts
• Goal: Enable communication between hosts not directly
connected
• Solution: Use packet switches in a similar way that the
telephone network uses phone switches
2
Packet Switching
• A packet switch is a device with several inputs and
outputs leading to and from the hosts that the
switch interconnects
• Job of a switch is to take packets that arriver on an
input and forward them to right output
• There are number of possible ways in which a
switch can determine “right” output for packet
– Broad categories: Connectionless and Connection-Oriented
Packet Switching
• Key Problem: A switch must deal with finite
bandwidth of its outputs
– If packets destined for a certain output arrive at a
switch and their arrival rate exceeds the capacity of
that output then we have problem of contention
– Switch queues packets until contention subsides
– If the contention problem lasts too long then the
switch will run out of buffer space and forced to
discard packets
– When packets are discarded too frequently, the switch
is said to be congested.
Switching Topology
• A switch implements a star topology
• Switches are MIMO devices
• Ports (inputs and outputs)
are numbered
5
Connectionless (datagram) Networks
• No dedicated connection between communicating hosts
• Packets are sent to the switch at any time
• Source is not aware of the state of the destination
• Packets may follow independent paths to the destination
(out-of-order delivery, larger delays, etc.)
• Less prone to switch failures if alternative paths exist
6
Datagrams
• Packets sent to each switch containing the
destination address
Destination
Port
A
3
B
0
C
3
D
3
E
2
F
1
G
0
H
0
Routing table for Switch 2
7
A datagram network with four switches (routers)
Delay in a datagram network
9
Virtual Circuit Switching
• Also referred to as connection-oriented
• First a connection is setup, followed by a data transfer
• In virtual-circuit switching, all packets belonging to the
same source and destination travel the same path; but
the packets may arrive at the destination with different
delays if resource allocation is on demand
• VC table created for the connection setup
–
–
–
–
Incoming VC identifier (identifies the connection per link)
Outgoing VC identifier (possibly different than the incoming)
Incoming interface (different than the VC Identifier)
Outgoing interface a(different than the VC identifier)
10
VC Connection Setup
• Permanent VC (PVC): Administrator sets up a permanent
connection and configures VC table
• Switched VC (SVC): The host signals to the switches in
order to establish a VC, dynamically.
11
PVC Switching - Example
• Suppose administrator wants to manually create new VC
from host A to host B
• Administrator needs to identify a path from A to B
• Administrator then picks up a VCI that is currently unused
on each link for the connection
12
Example: PVC from A to B
• In the example, VCI value of
–
–
–
–
5 is chosen for the link from host A to the switch 1
11 is chosen for the link from switch 1 to the switch 2
7 is chosen for the link from switch 2 to the switch 3
4 is chosen for the link from switch 3 to the host B
• Note that the outgoing VCI value at one switch is the
incoming VCI value at next switch
Example: PVC from A to B
• Switching tables for the switches in Example
Switch 1
Incoming Interface
Incoming VCI
Outgoing Interface
Outgoing VCI
2
5
1
11
Switch 2
Incoming Interface
Incoming VCI
Outgoing Interface
Outgoing VCI
3
11
2
7
Switch 3
Incoming Interface
Incoming VCI
Outgoing Interface
Outgoing VCI
0
7
1
4
Data Transfer Stage
• To send a packet to host B, the
– Host A puts the VCI value of 5 in the header and send the
packet to switch 1
– Switch 1 receive the packet on interface 2
– It uses the combination of interface and incoming VCI to locate
the corresponding entry of outgoing VCI and VCI in the
switching table and forwards the packet to next hop
– The process is repeated at each hop till the packet arrives at the
host B
15
Data Transfer Stage
16
SVC Switching - Example
• A sends setup message to switch 1 indicating the address
of B
• Switch 1 setups incoming/outgoing interfaces and VCIs
• Connection setup message is forwarded like a datagram
to switch 2
• Switch 2 repeats the setup process
• Once data stage is over, connection is torn down
17
PVC Switching - Example
VCI=5
VCI=11
REQ
VCI=7
VCI=4
18
Example: PVC from A to B
• Partial switching tables for switches in setup phase
Switch 1
Incoming Interface
Incoming VCI
Outgoing Interface
2
5
1
Outgoing VCI
Switch 2
Incoming Interface
Incoming VCI
Outgoing Interface
3
11
2
Outgoing VCI
Switch 3
Incoming Interface
Incoming VCI
Outgoing Interface
0
7
1
Outgoing VCI
PVC Switching - Example
VCI=11
VCI=7
VCI=5
ACK
VCI=4
20
Example: PVC from A to B
• Switching tables after ACK signal is reaches back to host A
Switch 1
Incoming Interface
Incoming VCI
Outgoing Interface
Outgoing VCI
2
5
1
11
Switch 2
Incoming Interface
Incoming VCI
Outgoing Interface
Outgoing VCI
3
11
2
7
Switch 3
Incoming Interface
Incoming VCI
Outgoing Interface
Outgoing VCI
0
7
1
4
Virtual Circuit Switching
• As host A has to wait for the connection request to
reach the far side of the network and return before it
can send its first data packet, there is at least one RTT
of delay before data is sent
• Initial setup message contains the global address of
destination but data packets just contain VCI.
•Per-packet overhead reduced relative to datagram model
• If a switch or a link in a connection fails, the connection
is broken and a new one will need to be established.
Also, the old one needs to be torn down to free up
table storage space in the switches.
Virtual Circuit Switching
• The issue of building up the forwarding table for
datagram forwarding, which requires some sort of
routing algorithm
• Three-part strategy for a connection-oriented packet
switched model
• Buffers are allocated to each VC on initialization
• Sliding window protocol run between each pair of nodes
along the VC to keep the sending node from overrunning the
buffers allocated at the receiving node
• Circuit is rejected by a given node if not enough buffers are
available at that node when the connection request message
is processed
Source Routing
• Idea: Include the entire route to be followed in the header
• Nodes must know the network topology in advance
24
Possible Header Implementations
• Header has variable length
• Used in both datagram and VC switching (connection setup)
• May be “loose” or “strict” routing
25
Bridges
• Bridges are special switches that interconnect Ethernet networks
• Acts as a simple node on each Ethernet
• Early bridges forwarded all packets between the two networks
26
Bridges Vs. Repeaters
• Repeaters are analog amplifiers of the signal
– Monitor the existence of analog signal on the line
– Amplify and repeat the signal
– Physical layer function, no message parsing
• Bridges “repeat” frames rather than signals
– The forward received frames among different LANs
– Message parsing is performed to decide whether to fwd the packet or not
27
Limitations of Repeaters
• All hosts connected via repeaters belong to the same collision
domain
–
–
–
–
Every bit is sent everywhere
So, aggregate throughput is limited
E.g., three departments each get 10 Mbps independently
… and then connect via a hub and must share 10 Mbps
• Multiple LAN technologies not compatible
– No message parsing – analog process
– No interoperability between different rates and formats
– E.g., 10 Mbps Ethernet and 100 Mbps Ethernet
• Limited geographical distances and # of nodes
28
Advantages of Bridges
• Facilitate breaking of network into isolated collision domains
• Message parsing may avoid unnecessary packet forwarding
Collision domain 1
Collision domain 2
29
Bridge Forwarding Table
• Not all packets need to be forwarded. Eg., packets from A to B
need not be forwarded on port 2
• Bridges maintain a forwarding table
Host
Port
A
1
B
1
C
1
X
2
Y
2
Z
2
30
Forwarding Algorithm
Look up Destination
Address
Destination not found
Destination found
broadcast
Same as incoming port
Different port
Flood all ports but
incoming one
Forward designated
port
Discard
31
Problem with Flooding
32
Some Preliminaries on Graphs
• Graph G(V, E) : Collection of vertices and edges
– V: Set of vertices
– E: Set of edges, e(x, y) = 1, if x, y connected, 0 otherwise
• Path: sequence of vertices with an edge between subsequent
vertices (can be defined as sequence of edges as well)
Path: {V1, V3, V4}
V3
Vertex
V1
V4
V2
Edge
V5
V6
33
Connected Graph
• A graph is said to be connected, if there is a path from any node to
any other node
V3
V3
V1
V4
V1
V4
V2
V2
V5
V6
V5
V6
34
k-Connected Graph
• Vertex degree: # of edges adjacent to the vertex
• A graph is k-connected if the degree of each vertex is at least k.
Alternatively, if removal of any k-1 edges does not leave the graph
disconnected
• A graph of N vertices is fully connected if each node has a degree
(N – 1) (directly connected network)
Number of edges: N(N-1)/2
V3
V1
V4
V5
V6
35
(A)Cyclic Graphs
•
•
•
•
•
Cycle: a path with the same first and last vertex
Cyclic graph: A graph that contains at least one cycle
Acyclic graph: A graph with no cycles
Tree: An acyclic connected graph (spanning tree, spans all vertices)
Forest: A disconnected acyclic graph (a graph with many trees)
V3
V3
V1
V4
V5
V6
Cyclic graph
V1
V4
V5
V6
Tree
36
Mapping Extended LAN to a Graph
• Bridges and LANs become vertices, ports become edges
• Goal: Make a tree that spans only LANs (red vertices)
A
B
C
B3
B5
B7
D
B2
E
K
F
B1
G
H
B6
B4
J
I
37
Spanning Tree Algorithm(1)
• Each bridge has a unique identifier
• Pick bridge with smallest ID, make it the root of the tree
D
E
F
G
B1
H
38
Spanning Tree Algorithm(2)
• Compute shortest path (in terms of hops) from each bridge to root
A
B
C
B3
B5
B7
D
B2
E
K
F
B1
G
H
B6
B4
J
I
39
Spanning Tree Algorithm(3)
• Each LAN remains connected to the bridge with shortest path to
the root. In case of a tie use smallest ID
A
B
C
B3
B5
B7
D
B2
E
K
F
B1
G
H
B6
B4
J
I
40
Message Exchange
• Initially, all bridges consider themselves as roots
• Broadcast on all ports ID, root bridge, and distance to root
• If bridge hears a message from another bridge with smaller ID it
adjust root/distance, and forwards
• Ex., Let (Y, d, X) denote (root, distance, bridge ID)
–
–
–
–
–
–
B3 receives (B2, 0, B2)
B3 accepts B2 as root
B3 adds one on its distance to B2, and fwds to B5 (B2, 1, B3)
B2 accepts B1 as root and updates B3 with (B1, 1, B2)
B5 accepts B1 as root and updates B3 with (B1, 1, B3)
B3 accepts B1 as root, and note that both B2, B5 are closer to root in both
ports. Hence, B3 blocks all ports
41
3.3 Asynchronous Transfer Mode: ATM
• Connection-oriented, packet-switched
– (e.g., virtual circuits).
• Teleco-driven. Goals:
– Handle voice, data, multimedia
– Support both Permanent Virtual Circuits (PVCs) and Signaled or
Switched Virtual Circuits (SVCs).
– Replace IP. (didn’t happen…)
• Important feature: Cell switching
Cell Switching
• Small, fixed-size cells
[Fixed-length data][header]
• Why?
– Efficiency: All packets the same
• Easier hardware parallelism, implementation
– Switching efficiency:
• Lookups are easy -- table index.
– Result: Very high cell switching rates.
– Initial ATM was 155Mbit/s. Ethernet was 10Mbit/s at the same
time. (!)
• How do you pick the cell size?
ATM Features
• Fixed size cells (53 bytes).
– Why 53?
• Virtual circuit technology using hierarchical virtual circuits
• PHY (physical layer) processing delineates cells by frame
structure, cell header error check.
• Can manage delays better due to fixed (small) cell size
• Support for multiple traffic classes by adaptation layer.
– E.g. voice channels, data traffic
• Elaborate signaling stack.
– Backwards compatible with respect to the telephone
standards
• Standards defined by ATM Forum.
– Organization of manufacturers, providers, users
Why 53 Bytes?
• Small cells favored by voice applications
– delays of more than about 50 ms (approx) require echo
cancellation
– each payload byte consumes 125 s (8000 samples/sec)
• Large cells favored by data applications
– Five bytes of each cell are overhead
• France favored 32 bytes
– 32 bytes = 4 ms (32* 125s) packetization delay.
– France is 3 ms wide.
– Wouldn’t need echo cancellers!
• USA, Australia favored 64 bytes
– 64 bytes = 8 ms
– USA is 16 ms wide
– Needed echo cancellers anyway, wanted less overhead
• Compromise
Figure 3.16: ATM cell format at the UNI
3.3.2 Segmentation and Reassembly
•
•
•
•
•
Packets handed down from upper layers are often larger than 48 bytes
Need to “fragment” the high-level message into low-level packets.
Theses fragmented packets need to be reassembled at the destination.
Fragmentation and reassembly but in in ATM we call it SAR.
Layer responsible for this is known as ATM Adaptation Layer (AAL)
Figure 3.17: Segmentation and reassembly in ATM
ATM Adaptation Layers (AALs)
• Since ATM was designed to support all sorts of services, including voice,
video, and data: different AALs were defined
1
2
3
4
5
synchronous
asynchronous
constant
variable bit rate
connection-oriented
connectionless




AAL 1: audio, uncompressed video
AAL 2: compressed video
AAL 3: long term connections
AAL 4/5: data traffic
 AAL5 is most relevant to us…
ATM A Adaptation Layer 5
data
pad ctl len CRC
...
ATM
header
payload
(48 bytes)
includes EOF flag
Pertinent part: Packets are spread across multiple ATM cells. Each
packet is delimited by EOF flag in the ATM header.
ATM Packet Shredder Effect
• Cell loss results in packet loss.
– Cell from middle of packet: lost packet
– EOF cell: lost two packets
– Just like consequence of IP fragmentation, but VERY small
fragments!
• Even low cell loss rate can result in high packet loss rate.
– E.g. 0.2% cell loss -> 2 % packet loss
– Disaster for TCP
• Solution: drop remainder of the packet, i.e. until EOF cell.
– Helps a lot: dropping useless cells reduces bandwidth and
lowers the chance of later cell drops
– Slight violation of layers
– Discovered after early deployment experience with IP over
ATM.
3.3.3 Virtual Paths
• When sending IP packets over an ATM network, set up a VC to
destination.
– ATM network can be end to end, or just a partial path
– ATM is just another link layer
• Virtual connections can be retained
– After a packet has been sent, the VC is maintained so that
later packets can be forwarded immediately
– VCs eventually times out
• Properties.
– Overhead of setting up VCs (delay for first packet)
– Complexity of managing a pool of VCs
+ Flexible bandwidth management
+ Can use ATM QoS support for individual connections (with
appropriate signaling support)
IP over ATM Static VCs
• Establish a set of “ATM pipes” that
defines connectivity between
routers.
• Routers simply forward packets
through the pipes.
– Each statically configured VC looks like
a link
• Properties.
– Some ATM benefits are lost (per flow
QoS)
+ Flexible but static bandwidth
management
+ No set up overheads
ATM Discussion
• At one point, ATM was viewed as a replacement for IP.
– Could carry both traditional telephone traffic (CBR circuits) and other
traffic (data, VBR)
– Better than IP, since it supports QoS
• In General a Complex technology.
–
–
–
–
But switching core is fairly simple
Support for different traffic classes
Signaling software is very complex
Technology did not match people’s experience with IP
• deploying ATM in LAN is complex (e.g. broadcast)
• supporting connection-less service model on connection-based
technology
– With IP over ATM, a lot of functionality is replicated
• Currently used as a datalink layer supporting IP.
CBR and VBR: Constant Bit Rate and Variable Bit RAte
3.3.4. Physical Layers for ATM
• ATM is a switched technology, whereas Ethernet was
originally envisioned as shared-media technology.
• Theoretically ATM can run on top of any point to point
link
• Practically ATM switches comes with some physical
medium
• Early process of standardization it was assumed that
ATM would run on top of Synchronous Optical Network
(SONET)
• ATM is also used over Digital Subscriber Line (DSL)
3.4. Implementation and Performance
• Simple way to build a switch is to equip a general purpose a
PC or a workstation with a number of network interfaces.
• With a suitable software this device can receive packets on
one of its interfaces and send them out on another of its
interfaces.
3.4.1. Implementation and Performance Contd.
• The figure on the previous slide shows a path that the
packet might take from the time it arrives on interface 1
until it is output on interface 2.
• We have assumed here that the workstation has a
mechanism to move data directly from an interface to
its main memory without having to be directly copied
by the CPU, that is, direct memory access (DMA)
• Once the packet is in memory, the CPU examines its
header to determine which interface the packet should
be sent out on.
• The packet does not go to the CPU because the CPU
inspects only the header of the packet; it does not have
to read every byte of data in the packet.
3.4.1. Implementation and Performance Contd.
• The main problem with using a workstation as a switch is
that its performance is limited by the fact that all packets
must pass through a single point of contention.
• In the example shown, each packet crosses the I/O bus
twice and is written to and read from main memory once.
• A workstation with a 33-MHz, 32-bit-wide I/O bus can
transmit data at a peak rate of a little over 1 Gbps. Since
forwarding a packet involves crossing the bus twice, the
actual limit is 500 Mbps, which is enough to support
maximum of five 100-Mbps Ethernet interface cards.
• For short packets, the cost of processing each packet—
parsing its header and deciding which output link to
transmit it on—is likely to dominate.
3.4.1. Implementation and Performance Contd.
• Suppose, for example, that a workstation can perform all
the necessary processing to switch 500,000 packets each
second.
• This is sometimes called the packet per second (pps) rate.
(This number is representative of what is achievable on
today’s highend PCs.) If the average packet is short, say,
64 bytes, this would imply:
Throughput = pps × (BitsPerPacket)
= 500000 × 64 × 8 = 256Mbps
• A throughput of 256 Mbps—substantially below the
range that users are demanding from their networks
today.
3.3.1. Implementation and Performance Contd.
• Thus, for example, a 10-port switch with this aggregate
throughput would only be able to cope with an average
data rate of 25.6 Mbps on each port.
• To address this problem, hardware designers have come up
with a large array of switch designs that reduce the amount
of contention and provide high aggregate throughput.
• Note that some contention is unavoidable: If every input
has data to send to a single output, then they cannot all
send it at once.
• However, if data destined for different outputs is arriving at
different inputs, a well-designed switch will be able to
move data from inputs to outputs in parallel, thus
increasing the aggregate throughput.
3.3.2. Ports
• Conceptually a switch consists of a number of input ports
and output ports and a fabric. There is usually at least one
control processor in charge of the whole switch that
communicates with the ports either directly or, as shown
here, via the switch fabric.
3.3.2. Ports Contd.
• The ports communicate with the outside world.
• The fabric has a very simple and well-defined job: When
presented with a packet, deliver it to the right output port.
• In general, when a packet is handed from an input port to
the fabric, the port has figured out where the packet needs
to go, and the port sets up the fabric accordingly by
communicating some control information to it.
• Information can also be attached to the packet itself (e.g.,
an output port number) to allow the fabric to do its job
automatically.
• Fabrics that switch packets by looking only at the
information in the packet are referred to as “self-routing,”
3.3.2. Ports Contd.
• The input port is the first place to look for performance
bottlenecks.
• For example, 64-byte packets arriving on a port connected
to an OC-48 link have to process packets at a rate of
2.48 × Giga ÷ (64 × 8) = 4.83 Mpps
• The input port has approximately 200 nanoseconds to
process each packet.
• Another key function of ports is buffering. Observe that
buffering can happen in either the input or the output port;
it can also happen within the fabric (sometimes called
internal buffering).
3.3.2. Ports Contd.
• Consider an input buffer implemented as a FIFO. As packets
arrive at the switch, they are placed in the input buffer.
• The switch then tries to forward the packets at the front of
each FIFO to their appropriate output port.
• However, if the packets at the front of several different
input ports are destined for the same output port at the
same time, then only one of them can be forwarded; the
rest must stay in their input buffers.
• The drawback of this feature is that those packets left at
the front of the input buffer prevent other packets further
back in the buffer from getting a chance to go to their
chosen outputs, even though there may be no contention
for those outputs.
3.3.2. Ports Contd.
• This phenomenon is called head-of-line blocking. A simple
example of head-of-line blocking is given in the figure,
where we see a packet destined for port 1 blocked behind a
packet contending for port 2.
3.3.3. Fabrics
• A switch fabric should be able to move packets from input
ports to output ports with minimal delay and in a way that
meets the throughput goals of the switch.
• A sample of fabric types includes the following:
i) Shared-bus: This is the type of “fabric” found in a
conventional workstation used as a switch, as
described above. Because the bus bandwidth
determines the throughput of the switch, high
performance switches usually have specially designed
busses rather than the standard busses found in PCs.
3.3.3. Fabrics
ii) Shared-memory: In a shared-memory switch,
packets are written into a memory location by an input
port and then read from memory by the output ports.
Here it is the memory bandwidth that determines
switch throughput, so wide and fast memory is
typically used in this sort of design. A shared-memory
switch is similar in principle to the shared-bus switch,
except it usually uses a specially designed, high-speed
memory bus rather than an I/O bus.
iii) Crossbar: A crossbar switch is a matrix of pathways
that can be configured to connect any input port to
any output port.
3.3.3. Fabrics Contd.
• The main problem with crossbars is that, in their simplest form, they
require each output port to be able to accept packets from all inputs at
once, implying that each port would have a memory bandwidth equal to
the total switch throughput.
A 4X4 Switch
3.3.3. Fabrics Contd.
iv) Self-routing: As noted above, self-routing fabrics rely on
some information in the packet header to direct each
packet to its correct output.
Usually, a special “self-routing header” is appended to the
packet by the input port after it has determined which
output the packet needs to go to, as illustrated in figure on
the next slide. The extra header is removed before the
packet leaves the switch.
A self-routing header is applied to a
packet at input to enable the fabric
to send the packet to the correct
output, where it is removed. (a)
Packet arrives at input port. (b) Input
port attaches self-routing header to
direct packet to correct output. (c)
Self-routing header is removed at
output port before packet leaves
switch.
3.3.3. Fabrics Contd.
• Self-routing fabrics are often built from large numbers of
very simple 2 × 2 switching elements interconnected in
regular patterns, such as the banyan switching fabric shown
in the figure below.