Transcript CS221: IPv6

Routing, Addressing, and Naming
Switching in the Internet
Christophe Jelger
Post-doctoral researcher
[email protected]
Christophe Jelger – CS221 Network and Security - Universität Basel - 2005
1
Today's lecture
MPLS: MultiProtocol Label Switching.
Metropolitan Ethernet.
The Spanning Tree Protocol (SPT) for Ethernet networks.
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
2
MPLS: MultiProtocol Label Switching (1)
What is it all about?
The Internet grew from circuit-switched (telephone) networks to packet
switched networks.




Telcos were offering leased lines to inter-connect networks located at
different locations (e.g. the world-wide branches of a large company).
Circuit-switching was very well known and provided a clear separation of
services with different levels of quality.
Circuit-switching was offering a higher level of control in the core of the
ISPs' networks.
Technologies like ATM were offering virtual circuits and a relatively high
level of traffic enginneering capabilities.
With the growth of IP, telcos/ISPs needed a new technology to provide
this kind of services in an IP-friendly manner.
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
3
MPLS: MultiProtocol Label Switching (2)
History: MPLS was hence initially designed to:
Provide a more IP-friendly data-carrying technology than ATM.

Running IP over ATM was complex, and ATM small cells (53 bytes) were
becoming an overhead when carrying potentially large IP packets.
Allow the creation of simple high-speed "IP switches".


At that time, IP forwarding was not entirely feasible in hardware (because
of the longest-prefix-match forwarding scheme).
No longer an issue in modern routers, although "switching is still faster
than routing".
Create a "shim" 2.5 layer to unify data-carrying technologies.


MPLS used over existing ATM and FrameRelay infrastructures.
IP used directly over MPLS.
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
4
MPLS: MultiProtocol Label Switching (3)
What is the goal of MPLS today?
ISPs need to separate/isolate different kinds of traffic (IP, voice, video,
business-critical applications, etc) in their core network(s). In practice,
MPLS is used to provide:



Virtual Private Networks (VPNs).
Quality of Services (e.g. guaranteed bandwidth between some points in the
network).
Traffic Enginnering (e.g. load balance traffic over all links of a network).
To do this, MPLS introduces the notion of FEC: Forwarding
Equivalence Class.


A FEC is a group of IP packets which are forwarded in the same manner
inside an MPLS network.
In practice, a classifier inspects each IP packet entering an MPLS network
and decides to which FEC it belongs.
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
5
MPLS: MultiProtocol Label Switching (4)
How does it work?
MPLS uses label switching to forward packets.


Fowarding is based on "exact match": this is much faster than IP's longestprefix match.
A label is a short (4 bytes) locally-significant identifier used to identify a
Forwarding Equivalence Class (FEC). MPLS labels have the following
format:
label value
exp S
TTL
32 bits




label value: 20 bits, unstructured (flat)
exp: 3 bits, currently used as Class of Service (CoS) field
S bit: "bottom of stack" indicator (when labels are stacked)
Time To Live: 8 bits.
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
6
MPLS: MultiProtocol Label Switching (5)
The forwarding of packets inside an MPLS network.
Labels are used to identify Label-Switched Paths (LSPs).
The mapping between IP packets – FECs and LSPs is done by Label
Switched Routers (LSRs) at the edges of the MPLS network.
13 → pop, oif:1
Packets for
10.1.2.3.0/24 (blue)
10.1.2.4.0/24 (red)
Forwarding is
based on label
1
13
Ingress LSR
17
1
subnet
10.1.2.0/24
21
Assigns each IP packet
to the appropriate FEC
and adds appropriate
label to IP packet
subnet 10.1.3.0/24
1
2
17 → swap(13), oif:1
21 → swap(44), oif:2
10.1.3.0/24 → push(17), oif:1
10.1.4.0/24 → push(21), oif:1
Egress LSR
44
1
44 → pop, oif:1
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
subnet 10.1.4.0/24
7
MPLS: MultiProtocol Label Switching (6)
The forwarding of packets inside an MPLS network.
FECs can be encasulated inside other FECs: we end up with stacks of
labels. This is useful to create "trunks" and reduce state in the core
MPLS network.
Packets for
10.1.2.3.0/24 (blue)
10.1.2.4.0/24 (red)
13 → pop, oif:1
Forwarding is
based on label
17
1
13
11 17
6 17
subnet 10.1.3.0/24
1
1
21
1
6 21
11 21
6 → swap(11), oif:1
17 → push(6), oif:1
21 → push(6), oif:1
2
44
11 → pop
17 → swap(13), oif:1
21 → swap(44), oif:2
1
44 → pop, oif:1
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
subnet 10.1.4.0/24
8
MPLS: MultiProtocol Label Switching (7)
The distribution of labels.
For each hop, the label is chosen by the downstream LSR and passed to
the upstream LSR. Hence labels are distributed "against the flow of
packets".
The distribution of labels can be done "in collaboration" with an intradomain routing protocol like OSPF or IS-IS.
There are currently 2 protocols to distribute labels:


LDP: Label Distribution Protocol.
RSVP-TE: Resource reSerVation Protocol for Traffic Engineering.
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
9
MPLS: MultiProtocol Label Switching (8)
The distribution of labels.
A simplified example.
The LSR chooses a label
Request PATH:
Reply RESV:
10.1.3.0/24
label 13
Ingress
LSR
Reply RESV:
Request
PATH:
label 17
10.1.3.0/24
subnet
10.1.2.0/24
1
1
1
13 → pop, oif:1
subnet 10.1.3.0/24
Egress LSR
2
17 → swap(13), oif:1
The LSR chooses a label
1
10.1.3.0/24 → push(17), oif:1
subnet 10.1.4.0/24
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
10
MPLS: MultiProtocol Label Switching (9)
MPLS in the Internet today.
MPLS is used extensively by most ISPs. An extended version called
GMPLS (Generalized MPLS) is also used to setup LSPs over optical
fiber technologies (SONET/SDH and DWDM).
With "Metro Ethernet" networks, MPLS is used to provide
"pseudowires" between Ethernet switched networks.
MPLS is still evolving: the IETF mpls working group is very active, with
many internet drafts still active and various mechanisms still being
standardized (e.g. lsp-ping, security, network management, etc).
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
11
Metro/Carrier Ethernet (1)
According to some studies, 95% of today's Internet traffic starts and
ends as Ethernet (end-sites are using Ethernet networks).
In the mean time, ISPs/carriers used everything but Ethernet in their
backbone networks.
Ethernet is becoming extremely cheap with very high data rates.
In contrast, data carrying technologies (SONET/SDH, MPLS) are
relatively expensive.
10 Gb/s already there, 40 Gb/s and 100 Gb/s are on their way.
However, Ethernet is too "dumb" for carriers.
Backbone networks require advanced services like QoS, network
management, traffic engineering, etc.
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
12
Metro/Carrier Ethernet (2)
Metro/Carrier Ethernet is a set of technologies and products.
The terms "metro" and "carrier" are more or less used to describe the
same technologies. However "metro" is targeted more at customers
networks, while "carrier" is targeted more at ISPs.
Many manufacturers, standards, and deployment styles.
Common denominator is Ethernet: for example, one typical obejctive is
to inter-connect Ethernet VLANs via a backbone network (e.g. to interconnect the networks located at different branches of a large
organization).
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
13
Metro/Carrier Ethernet (3)
Metro/Carrier Ethernet: some protocols.
IEEE 802.1Q tunneling, or "tag stacking", or "QinQ".

Very similar to MPLS labeling and label stacking, but with Ethernet VLAN
tagging technologies: the goal is to inter-connect customers' VLANs
without any "collision of VLAN ids/tags".
Image from: http://www.cisco.com/warp/public/cc/pd/si/casi/ca6000/prodlit/65met_wp.htm
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
14
Metro/Carrier Ethernet (4)
Metro/Carrier Ethernet: some protocols.
IEEE 802.1Q tunneling, or "tag stacking", or "QinQ".

CPE = Customer
Premises Equipment
PE = Provider Edge
Also known as 802.1ad or "Provider bridges".
Image from: http://www.cisco.com/warp/public/cc/pd/si/casi/ca6000/prodlit/65met_wp.htm
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
15
Metro/Carrier Ethernet (5)
Metro/Carrier Ethernet: scalability.
QinQ is limited to 4094 tags/customers, and there is a scalability issue
with the size of forwarding tables.
To remediate this, new standards have been defined:

IEEE 802.1ah or "Backbone Provider Bridges" or "MAC-in-MAC".




Introduces encapsulation techniques of Ethernet in Ethernet.
IEEE 802.1Qay-TE: a carrier grade extension of 802.1ah with traffic
engineering, MPLS compatibility, deterministic delivery.
HVLAN: proposed extension to introduce hierarchical VLAN tagging with
a CIDR-style "bast match" forwarding.
Sound like re-inventing the wheel?

New variants (with new names) of MPLS, IP, SONET, ATM?
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
16
Metro/Carrier Ethernet (6)
Currently an extremely active area.
Plenty standards on their way.
IETF vs. IEEE battle.
Vendors battle with competing technologies and protocols.
Development seems to be fully driven by the market (and not always
by technical advances).
ISPs want to save cost to extend their infrastructures.
Customers want to pay less.
Vendors want to sell new equipments.
Network deployments is really becoming "à la carte":
e.g. MPLS over Ethernet? Eth. over MPLS? Eth. over MPLS over Eth.?
A palette of technologies, costs, and services. Not clear who wins …
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
17
The spanning tree protocol (SPT).
A spanning tree of a graph is a sub-graph that contains all the
vertices (nodes) and is a tree.
Note that a given graph usually have multiple spanning trees.
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
18
The spanning tree protocol (2).
In a bridged Ethernet network, the main objective of STP is to
prevent loops in a topology with redundant paths.
How? Redundant links are de-activated (for forwarding).
One goal is to prevent the "broadcast storm problem".
Broadcast loop
Loop is prevented
A
A
ARP REQ B?
ARP REQ B?
B
B
Ethernet switch.
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
19
The spanning tree protocol (3).
Another goal is to prevent duplicate frames to be received.
A
data sent to B
B
Ethernet switch.
Duplicate frame is received!
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
20
The spanning tree protocol (4).
Loops also generate inconsistent and unstable states.
e.g. a switch learns on which port a machine is connected by looking at
the source MAC address of Ethernet frames.
Switch learns A
Switch
A
is onlearns
right port
is on left port
A
data sent to B
B
Ethernet switch.
Also note: Ethernet frames have no TTL !
i.e. they can potentially re-circulate forever!
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
21
The spanning tree protocol (5).
Centralized algorithms are not desirable in practice but are interesting
to study the problem.
E.g. Kruskal, Prim, Boruvka, and Dijkstra algorithms.
Challenges for distributed algorithms:
To converge (!): only one active spanning tree during steady-state.
To converge rapidly after topology change (Rapid STP).
Should remain simple for low-cost implementation.
Very old and well studied algorithm.
For Ethernet, it is standardized today by IEEE 802.1D (1990).
Since 2004, RSTP replaces STP in the standard.
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
22
The spanning tree protocol (6).
Basic operation of STP: All switches participating in STP gather
information on other switches in the network through an exchange
of data messages.
These messages are bridge protocol data units (BPDUs). This
exchange of messages results in the following:
The election of a unique root switch.
The election of a designated switch for every switched LAN segment.
The removal of loops in the switched network by placing redundant
switch ports in a backup state.
The root switch is the logical center of the spanning-tree topology.
All paths that are not needed to reach the root switch from anywhere
in the switched network are placed in backup mode.
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
23
The spanning tree protocol (7).
Electing a root bridge.
Each switch has a MAC address and a configurable priority number;
both of these numbers make up the Bridge Identification or BID.
The BID is used to elect a root bridge based upon the lowest priority
number; if this is a tie then the numerically lowest MAC address wins.
Upon startup all bridges send BPDUs. Once found, only the root bridge
sends BPDUs (e.g. every 2 seconds).

Typical forwarding algo:
Forward a BPDU if and only if BID < my_BID.
Stop sending my own BPDUs if I see BPDUs with BID < my_BID.
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
24
The spanning tree protocol (8).
Format for the BID.
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
25
The spanning tree protocol (9).
Finding shortest paths to the root bridge.
Each bridge must keep one and only one active link to the root bridge.
Link with lowest cost is kept as root link (root port).
Redundant links are blocked.
Shortest path is based on cumulative link cost.
Link costs are based on the speed of the link.
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
26
The spanning tree protocol (10).
Root port
Root port
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
27
The spanning tree protocol (11).
Electing a designated port for each segment.
Port announcing lowest cost is elected as designated port for segment.
Root port
Root port
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
28
The spanning tree protocol (12).
After convergence is reached there is:
One spanning tree per Ethernet network.
One root bridge.
One root port per non-root bridge.
One designated port per segment.
All other ports are blocked.
Note that it's possible to have one spanning tree per Ethernet VLAN.
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
29
The spanning tree protocol (13).
In 2004 STP is replaced in the standard by Rapid STP.
Convergence of STP takes up to 50 seconds.



Detection of lost BPDUs = 20 seconds (=root bridge lost).
Listening phase (no data forwarding) = 15 seconds.
Learning phase (no data forwarding) = 15 seconds.
Changes introduced by RSTP are
All bridges periodically generate BPDUs: costs are updated more
rapidly.
Links are point-to-point, edge-type, shared: failures are detected more
rapidly (e.g. non bridge-to-bridge ports are ignored).
Network convergence is up to 15 seconds.
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
30
The rapid spanning tree protocol (14).
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
31
Thank you
Questions?
Christophe Jelger – cs321 Autonomic Computer Systems – Universität Basel - 2009
32