Generalized MultiProtocol Label Switched
Download
Report
Transcript Generalized MultiProtocol Label Switched
GMPLS networks
Malathi Veeraraghavan
University of Virginia
[email protected]
Tutorial at IEEE Globecom 2006
1
Acknowledgment to co-authors
• All co-authors are affiliated with the
University of Virginia (@virginia.edu)
–
–
–
–
–
Helali Bhuiyan (helali): OSPF-TE
Xiuduan Fang (xf4c): GFP, VCAT, LCAS
Tao Li (tl8g): LMP and OTN
Mark McGinley (mem5qf): MPLS, PWE
Xiangfei Zhu (xz4p): RSVP, Cheetah
2
Outline
• Principles
– Different types of connection-oriented
networks
• Technologies
– Single network
– Internetworking
• Usage
– Commercial networks
– Research & Education Networks (REN)
3
Principles
• Packet-switched vs. circuit switched
networks
• Connection-oriented vs.
connectionless modes of bandwidth
sharing
• Analytical models
4
A model for a single network
Link
Link
Host
Host
Switch
Host
Link
Link
Switch
Switch
Link
Host
• Hosts represent data sources and sinks
• A switch moves data units from one link to another
– enable sharing of a link's bandwidth
• My definition of "switch:" the multiplexing scheme
is the same on all the links (e.g., a network of
SONET TDM switches or a network of Ethernet
packet switches)
5
Types of switched networks
Switching type Circuit-switched
(CS)
Networking
type
Packet-switched
(PS)
Connectionless (CL)
Not an option
e.g., switched
Ethernet networks
Connection-oriented
(CO)
e.g., telephone
network, SONET
networks
e.g., MultiProtocol
Label Switching
(MPLS)
Virtual-circuit (VC)
networks
6
Analogy for connectionless packetswitched networks: roads
• The intersection point of two roads is analogous to a
connectionless packet switch
• Road signs at a traffic light are analogous to the
routing table at a packet switch
7
Analogy for
circuit switched networks
• Airlines networks
• Airports are analogous to circuit switches
• Procedure
– Call setup: comparable to an airline passenger
calling ahead to make reservations for a seat on
each leg of a multi-flight trip
– Reserved time slots on each link: similar to seat
assigments on each flight
– When trip actually starts and passenger arrives
on one flight at an airport, he/she simply moves
to assigned seat on next flight
8
Circuit switch vs. packet switch
• Depends upon multiplexing technique
used on interfaces
– Position based multiplexing (circuit
switch)
• "Position" means time or frequency
(wavelength)
– Packet based multiplexing (packet
switch)
9
Generic switch design
• Links connected to
the switch are
typically shared
– this means there is
multiplexing/MAC
function in the datalink layer
implementation at the
end of the link
D: Demultiplexer
M: Multiplexer
Input
interfaces
1
2
3
Q
.
.
.
Output
interfaces
D
D
M
M
D
M
Space
switch
D
M
1
2
3
.
.
.
Q
Unfolded view
of a switch
Crossbar or multistage space switch
10
Recall Time Division Multiplexing
Example: 12 OC1 signals multiplexed on to an OC12 signal
1
2
.
.
12
1
2
12
...........
90 x 9 x 8 bits
every 125s
12 x 90 x 9 x 8 bits
every 125s
RATE: 51.84Mbps - OC1
RATE: 622.08 - OC12
11
SONET/SDH rates
(number is the multiplier)
12
Tanenbaum
Example of a circuit switch (TDM): SONET
Controller
1
OC12
2
..
..
..
..
.
.
.
.
OC12
OC1
OC1
OC12
Q
..
..
Routing and
signaling
..
..
PxP
space
switch
(also called
switch fabric
or
interconnection
fabric)
OC12
1
OC12
..
..
..
..
demultiplexers
2
Q
.
.
.
.
OC12
multiplexers
Crossconnect rate: OC1
What is the relation between P and Q?
13
Example of a circuit switch: a SONET switch
Host A
OC3
Ports
or interfaces
a
b
Host B
OC3
SONET
switch
OC3
Host C
c
d
OC3
Host D
Create a bidirectional OC1 circuit between host A and host C
Use it for application 1 (e.g., web access)
Create another bidirectional OC1 circuit between host A and host B
Use it for application 2 (e.g., email)
14
Example of what happens inside a
SONET switch (crossbar assumed)
125s
Controller
OC1
A2 A1
Host A
a
B1
Host B
b
C1
Host C
c
Host D
d
OC3
a
Input ports
b
c
d
Host A
Host B
Host C
A1
15
A2
C1 B1
Output ports
Host D
Timeslot mapping table
Input
Output
Port
Timeslot Port
Timeslot
a
1
c
1
c
1
a
1
a
2
b
1
b
1
a
2
• We need to use timeslot 2 on port a to/from host A
for the AB OC1 circuit since timeslot 1 on this port
was already used for the AC OC1 circuit
16
Packet switch: header based
switching
“Unfolded” View of Switch
• Input line card functions
Controller
– Packet-based
demultiplexing
– Header processing
N
Line card
Line card
2
Line card
3
Line card
Line card
Input ports
• Output line card
functions
– Packet-based multiplexing
• Space switch
– Transfer packets between
line cards
– Close crosspoints on a
packet-by-packet basis
…
1
…
…
3
Line card
Space switch
2
Line card
…
1
Line card
N
Output ports
Data path
Control path
• Controller
– Next week's lectures
Folded view: 1 line card has
both input and output functions
17
Insides of a packet switch – unfolded
view (assuming crossbar space switch)
Controller
1
Input ports
2
3
4
Line card
Line card
Line card
Line card
Line card Line card Line card Line card
1.
2.
3.
4.
5.
Physical layer
Data link layer
1
2
3
Once a frame is received correctly, consult routing table with destination MAC address
Make appropriate crosspoint connection in fabric
Send frame to appropriate outgoing line card
4
Output ports
18
Example of a packet switch: an Ethernet switch
Destination MAC address: 05:a1:08:10:a4:3e
05:a1:08:10:a4:3e
Host 1
a
b
Host 2
Ethernet
switch
Host 3
Destination MAC address: 09:a5:08:10:a4:3d
c
d
Destination
Output Port
05:a1:08:10:a4:3e
c
09:a5:08:10:a4:3d
b
Host 4
09:a5:08:10:a4:3d
Routing table (called filtering database in Ethernet switches)
•
•
•
•
Headers of incoming packets are processed to extract destination address
Routing table is consulted for output port, O, corresponding to destination address
Corresponding space switch crosspoint connection is closed
Packet is sent from input port to the output port, O
19
Going back to circuit switch
• The space switch could be timeshared
• In which case, P = Q
• The switch is reprogrammed in each
time slot
– in the OC3 example, if the space switch
lines were operated at OC3, then every
125/3 s the switch fabric crosspoints
will need to be reprogrammed
20
Types of switched networks
Switching type Circuit-switched
(CS)
Networking
type
Packet-switched
(PS)
Connectionless (CL)
Not an option
e.g., IP networks;
Ethernet networks
Connection-oriented
(CO)
e.g., telephone
e.g., MultiProtocol
network, SONET
Label Switching
(Synchronous Optical (MPLS)
NETwork)
Next focus
21
Data plane vs. control plane
• Data plane: Functions, layers and
protocols needed for the actual
transfer of user data
• Control plane: Support functions and
protocols needed at each layer of the
data plane
22
Focus on the Network layer (NL)
• Data plane functions of the NL:
– Implementation of the NL at a switch:
• Moves data units from one link to another
– Implementation of the NL at end hosts (support role):
• Create/parse packet headers for packet-based NL
• Position user data units for circuit-based NL
• Control-plane (support) functions for the NL:
– Addressing for all three types of networks
– Routing for all three types of networks
– Signaling for connection-oriented networks
23
Mapping of control-plane (support)
functions to types of networks
Support function Addressing
Network
(in data or
control
type
plane?)
Routing
Signaling
Connectionless (CL) Data plane
Connectionoriented Circuit
Switched (CS)
Control plane
Connectionoriented Packet
Switched (CO PS)
Control plane
24
Sub-section outline
• Understand three support functions
– Addressing
– Routing
– Signaling
• Learn how these are used in the three
different types of networks
– Connectionless packet-switched networks
– Circuit-switched networks
– Connection-oriented packet-switched or virtualcircuit networks
25
Addressing
• Where are host interface addresses used:
– In connectionless packet-switched networks,
destination addresses are carried in packet
headers
• hence we place this function as being in the data plane
– In connection-oriented (circuit/VC) networks,
these addresses are used in signaling messages
(needed for call setup)
• hence we place this function as being executed in the
control plane
26
Summarized addresses
• What are summarized addresses?
• Why summarize addresses?
27
Summarized addresses
• What are summarized addresses?
– An address that represents a group of endpoint
addresses
– e.g., all 212 numbers, 128.238 IP addresses
• Why summarize addresses?
– Reduces routing table sizes – hold one entry for
a summarized address instead of a large
number of individual addresses
– Reduces routing message lengths that convey
reachability information
28
Functions related to addressing
• Techniques to assign addresses to
interfaces
– Hardwire as with MAC addresses
– Assign to interfaces as with IP
addresses
– Assign to nodes (hosts/switches)
29
Examples of addressing
schemes
• Ethernet switched network
– 6-byte MAC address
• IP-based networks
– 4-byte IP addresses
• Telephone networks
– 8-byte E.164 address (telephone
number)
30
Sub-section outline
• Understand three support functions
– Addressing
Routing
– Signaling
• Learn how these are used in the three
different types of networks
– CL
– CS
– CO PS
31
Goal of routing algorithms
• Goal is to allow for the calls or packets to
be routed on the "shortest" path, where
the shortest path is determined by some
metric, e.g.:
– minimum weight path (add link weights)
– minimum end-to-end delay
– path with the most available bandwidth
• The algorithm should adapt to changes in
– topology (includes administrator-set link
weights)
– reachability
– loading conditions
32
Types of routing algorithms
• Static or dynamic
– If changes are rare, static schemes
incur low overhead - not applicable in
production networks
– Dynamic algorithms add complexity, but
offer bandwidth utilization gains
• Centralized or distributed
– Centralized schemes allow for optimal
solutions
– Distributed schemes are scalable
33
Other classifications
• Hop-by-hop vs. source routing
– Hop-by-hop: Each switch determines
what the next-hop switch is toward
which to route the packet or the call
– Source: Ingress switch determines the
end-to-end route
• Loose source route: not all hops specified
• Strict source route: exact set of hops
specified
34
Distributed routing:
Routing protocols
• Two types:
– Distance vector protocols
• Each switch maintains a distance table (in addition to
the routing table). The distance table shows the
distances to all nodes in the network through each of
its neighbors. The shortest path is then computed and
the outgoing port information is stored in the routing
table.
– Link state protocols
• The whole topology of the network is kept at each
switch. Shortest path algorithms such as Dijkstra's
are then run to determine the routing tables.
35
Dijkstra’s algorithm
• Find shortest paths from source node s to
all other nodes.
– At each iteration, determine the "next closest
node" from the source s.
• For each node that is still not in set M (the set
containing nodes to which shortest paths from the
source have already been computed), determine if its
current distance from s is shorter than if the path
came through the selected "next closest node.“
• Find the “next closest node” after finding all the
distances.
• Move "next closest node" to set M.
– When the set M has all the nodes, stop.
36
Routing table precomputation:
Calculate shortest path for node s to all other nodes
given the link weights (w) for all links
Dijkstra’s shortest-path algorithm:
s
source node.
goal: find Dn
cost of the least-cost path from node s to node n for all n
M = {s};
for each n M
Dn = wsn;
while (M all nodes) do
Find i M for which Di = min{Dj ; j M};
Add i to M;
for each n M
Dn = mini [ Dn, Di + win ];
Update route;
enddo
37
Example
5
2
3
3
5
2
1
3
1
2
1
6
2
4
1
w56=2
5
38
List path weight and route
M
D2
D3
D4
D5
D6
0
{1}
2, {1-2}
5, {1-3}
1, {1-4}
1
{1,4}
2, {1-2}
4, {1-4-3}
1, {1-4} 2, {1-4-5}
2
{1,4,2,5}
2, {1-2}
3, {1-4-5-3}
1, {1-4} 2, {1-4-5} 4,{1-4-56}
3
{1,4,2,5,3}
2, {1-2}
3, {1-4-5-3}
1, {1-4} 2, {1-4-5} 4,{1-4-56}
4
{1,4,2,5,3,6 2, {1-2}
}
3, {1-4-5-3}
1, {1-4} 2, {1-4-5} 4,{1-4-56}
39
Resulting Routing Table
2
2
3
1
1
1
4
1
5
6
2
The tree is translated into a routing table at node 1:
Destination
2
3
4
5
6
Next Hop
2
4
4
4
4
40
Examples of routing protocols
• In Ethernet networks
– Address learning and the spanning tree
algorithm
• In the Internet:
– Link-state routing protocols, such as Open Path
Shortest First (OSPF)
– Distance-vector based routing protocols, such
as Border Gateway Protocol (BGP)
• In telephone networks:
– Real-Time Network Routing (RTNR)
41
Sub-section outline
• Understand three support functions
– Addressing
– Routing
Signaling
• Learn how these are used in the three
different types of networks
– CL
– CS
– CO PS
42
Purpose of signaling
(needed only in CO networks)
• Functions:
– Call setup:
• route selection
• bandwidth reservation on each link of endto-end connection
• switch fabric configuration of each switch
– Call release
• release bandwidth for use by others
43
Examples of signaling protocols
• ISDN User Part of the SS7 (Signaling
System No. 7) protocol stack
– to set up and release DS0 (64kbps) circuits in a
telephone (circuit-switched) network
• Resource reSerVation Protocol with
Traffic Engineering (RSVP-TE)
– used in CO PS networks such as MPLS/ATM
– used in CS networks such as SONET/SDH and
WDM
44
Sub-section outline
• Understand three support functions
– Addressing
– Routing
– Signaling
• Learn how these functions are used in the
three different types of networks
CL
– CS
– CO PS
45
Connectionless packet-switched networks
Phase 1: Routing protocol exchanges
+ routing table precomputation
II
4
5
I
III-B
III-C
III-B
III-C
Next hop
III-*
IV
Routing table
(will have other entries)
Host
III-B
III
1
Dest.
•
•
Next hop
1
Host
I-A
•
•
•
Dest.
1
IV
1
Dest.
Next hop
III-*
III
1
V
I, II, III, IV, V: switches
Link weights are shown next to links
Host interface addresses are derived from switch addresses (e.g.
I-A is connected to switch I)
Example routing table entries shown at switches I, III, IV
III-*: summarized address for all hosts connected to switch III
Host
III-C
46
Connectionless (CL) packet-switched networks
Phase 2: User-plane packet forwarding
Packet header Packet payload
III-B
II
III-B
Host
I-A
Next hop
III-*
IV
•
•
Next hop
III-B
III-C
III-B
III-C
III-B
III-B
I
Dest.
Dest.
Host
III-B
III
IV
V
Dest.
Next hop
III-*
III
Packet header carries destination host interface
address (unchanged as it passes hop by hop)
Each CL packet switch does a route lookup to
determine the outgoing next hop node or port
Host
III-C
47
Sub-section outline
• Understand three support functions
– Addressing
– Routing
– Signaling
• Learn how these are used in the three
different types of networks
– CL
CS
– CO PS
48
Circuit-switched networks
Phase 1: Routing protocol exchanges
+ routing table precomputation
II
Host
I-A
I
Dest.
Next hop
III-*
IV
Dest.
Next hop
III-B
III-C
III-B
III-C
Host
III-B
III
IV
V
Dest.
Next hop
III-*
III
• Same as the Phase 1 routing protocol exchanges
described for connectionless (CL) packetswitched networks
• More emphasis on exchanging loading information
Host
III-C
49
Circuit-switched networks
Phase 2: Signaling for call setup
Connection setup
(Dest: III-B;
BW: OC1;
Timeslot: a, 1)
II
a
b
Host
I-A
a
I
III
c
b
d
c
Routing
table
Dest.
Next hop
III-*
IV
IV
a
d
Host
III-B
b
c
V
Connection setup actions at each switch on the path:
1.
2.
3.
4.
5.
6.
Parse message to extract parameter values
Lookup routing table for next hop to reach destination
Read and update CAC (Connection Admission Control)
table
Select timeslots on output port
Configure switch fabric: write entry into timeslot
mapping table
Construct setup message to send to next hop
50
Circuit-switched networks
Phase 2: Signaling for call setup
Connection setup
(Dest: III-B;
BW: OC1;
Timeslot: a, 1)
II
b
a
a
Host
I-A
I
c
Connection
setup
b
III
d
c
Routing
table
CAC
table
Dest.
Next hop
III-*
IV
a
Interface (Port);
Next hop Capacity; Avail timeslots
IV
Timeslot
mapping table
c; OC12; 1, 4, 5
INPUT
Port /Timeslot
a/1
OUTPUT
Port/Timeslot
IV
d
Host
III-B
b
c
V
Connection setup actions at each switch on the path:
1. Parse message to extract parameter values
2. Lookup routing table for next hop to reach destination
3. Read and update CAC (Connection Admission Control)
table
4. Select timeslots on output port
5. Configure switch fabric: write entry into timeslot
mapping table
6. Construct setup message to send to next hop
c/4
Update to remove timeslot 1
from available list
51
Circuit-switched networks
Phase 2: Signaling for call setup
II
b
Host
I-A
a
a
I
c
b
Connection
setup
d
c
Time slot
could change
Connection setup
(Dest: III-B;
BW: OC1;
Timeslot: a, 4)
IV
a
III
Host
III-B
b
c
V
d
INPUT
OUTPUT
Port /Timeslot Port/Timeslot
a/4
c/2
Perform same set of 6 connection setup steps at switch IV
write timeslot mapping table entry, update CAC table and
send connection setup message to the next hop
52
Circuit-switched networks
Phase 2: Signaling for call setup
INPUT
OUTPUT
Port /Timeslot Port/Timeslot
II
d/2
b
Host
I-A
a
a
I
b/1
c
b
Connection
setup
d
c
a
IV
III
d
Host
III-B
b
c
V
Connection
setup
Circuit setup
complete
Perform same set of 6 connection setup steps at switch III
Reverse setup-confirmation messages typically sent
from destination through switches to source host
53
Circuit-switched networks
Phase 3: User-data flow
1
IN
OUT
Port /Timeslot Port/Timeslot
2
II
b
Host
I-A
1
d/2
2
1
2
a
I
b
d
c
a
IN
OUT
Port /Timeslot Port/Timeslot
a/1
c/4
a
III
c
IV
d
b/1
b
c
1
2
Host
III-B
V
IN
OUT
Port /Timeslot Port/Timeslot
a/4
c/2
• Bits arriving at switch I on time slot 1 at port a
are switched to time slot 1 of port c
54
Release procedure
• When a communication session ends,
there is a hop-by-hop release
procedure (similar to the setup
procedure) to release
timeslots/wavelengths for the next
call
55
Sub-section outline
• Understand three support functions
– Addressing
– Routing
– Signaling
• Learn how these are used in the three
different types of networks
– CL
– CS
CO PS - Virtual Circuit (VC) networks
56
CO packet-switched (VC) networks
Phase 1: Routing protocol exchanges
+ routing table precomputation
II
Host
I-A
I
Dest.
Next hop
III-*
IV
Dest.
Next hop
III-B
III-C
III-B
III-C
Host
III-B
III
IV
V
Dest.
Next hop
III-*
III
• Same as the Phase 1 routing protocol exchanges
described for connectionless (CL) packetswitched networks
• More emphasis on exchanging loading information
Host
III-C
57
CO packet-switched (VC) networks
Plane 2: Signaling
Connection setup
(Dest: III-B;
Traffic descriptor;
QoS; Label: a, 1)
IN
Port /Label
II
d/20
b
a
Host
I-A
I
c
CAC
table
Dest.
Next hop
III-*
IV
Next hop
IV
Switch
config.
table
IN
Port /Label
a/1
b/1
a
Connection
setup
Connection
setup
b
Interface (Port);
Capacity; Free BW/buffer;
Free labels
a
IV
IN
Port /Label
a/46
III
d
c
Routing
table
OUT
Port/Label
Host
III-B
b
c
V
d
Connection
setup
OUT
Port/Label
c/20
Virtual circuit
c; OC12; x/y; 10, 46, 50
OUT
Port/Label
c/46
Connection setup actions at each switch on the path:
1.
Message parsing to extract parameter values
2.
Route lookup for next hop to reach destination
3.
CAC (Connection Admission Control) for BW and
buffer
58
4.
Label selection
5.
Switch fabric configuration
6.
Message construction to send to next hop
CO packet-switched (VC) networks
Plane 3: User-data flow
Packet header
Label
Host
II-B
Packet payload
II
1
OUT
Port/Label
d/20
b
Host
I-A
a
I
c
46
III
20
b
a
2
Packet header
IV
a/46
a/1
a/1
a/2
d
d
b
1
c
V
Host
III-B
Packet payload
IN
Port /Label
IN
Port /Label
b/1
a
c
Switch
config.
table
IN
Port /Label
OUT
Port/Label
c/46
c/1
•
OUT
Port/Label
c/20
b/1
Virtual circuit
Packets sent by host I-A with the label field
in the packet header set to 1 are switched
according to entries in the switch
configuration tables at each switch following
59
the path of the established virtual circuit.
Let us not confuse
addresses with labels
• Addresses:
– numbers assigned to end hosts or end host interfaces
– globally unique
• Labels:
– assigned to identify a virtual circuit on a link
– unique just to the link (like seat assignments on a flight; same
seat numbers can be assigned on different flights)
• Scope for confusing the two:
– When the action performed by a packet switch is examined,
• a connectionless switch forwards packets based on addresses
• while a connection-oriented switch forwards packets based on
labels
60
Rationale for VC networks
• Combine
– QoS-guaranteed service of circuitswitched networks
– Ability of packet-switched networks to
handle bursty traffic
61
"Best" of both worlds
• Service guarantees to users
• High utilization: beneficial to service
providers
62
"Worst" of both worlds
• Complexity
– Control plane: Switch controllers need to
implement signaling protocols and handle
setup/release requests for bandwidth
• Inherits complexity of circuit switch controllers
– Data plane: Line cards need packet based
demultiplexing, space switch needs to be
reconfigured on a packet-by-packet basis, need
buffering
• Inherits complexity of packet switches
63
Principles
• Packet-switched vs. circuit switched
networks
• Connection-oriented vs.
connectionless modes of bandwidth
sharing
Analytical models
64
Bandwidth sharing
• The very purpose for the existence for
networks is to enable bandwidth sharing
• The purpose of a communication link is to
move data bits from one point to another
• But the purpose of a network of links
interconnected by switches is to enable
the sharing of bandwidth on these links
65
How is bandwidth shared on a connectionless
packet-switched network?
• Pre-1988 IP network:
– Just send data without reservations or any
mechanism to adjust rates
• Van Jacobson's 1988 contribution:
– Added congestion control to TCP
– TCP software at the sending end host adjusts
its sending rate based on estimates of
congestion in the router buffers
66
TCP throughput
B
•
•
•
•
•
1
2bp
3bp
RTT
T0 min(1,3
) p (1 32 p 2 )
3
8
B: Throughput, RTT: Round-trip time
b: an ACK is sent every b segments (b is typically 2)
p: packet loss rate on path
T0: initial retransmission time out in a sequence of retries
Interesting observation: throughput is independent of
bottleneck link rate
– congestion-avoidance algorithm model
– for low packet loss rate, it does matter, when file size is large
• Padhye, Firoui, Towsley, Kurose, ACM Sigcomm 98 paper
67
TCP throughput
Case
Input parameters
Packet loss rate
Case 1
0.0001
Bottleneck link rate
Round-trip delay
0.1ms
82.25
Case 2
5ms
89.45
Case 3
50ms
396.5
0.1ms
8.25
Case 5
5ms
39.6
Case 6
50ms
395.7
0.1ms
82.93
5ms
135.4
50ms
1293
0.1ms
8.64
Case 11
5ms
129.4
Case 12
50ms
1287
0.1ms
92.41
5ms
471.7
50ms
4417
0.1ms
12.43
Case 17
5ms
441.7
Case 18
50ms
4387
Case 4
Case 7
100 Mb/s
Mean transfer delay
for a 1GB file (s)
1Gbps
0.001
Case 8
100
Mbps
Case 9
Case 10
Case 13
Case 14
1Gbps
0.01
100
Mbps
Case 15
Case 16
1Gbps
~21Mbps
~2Mbps
68
How is bandwidth shared on a circuitswitched network?
• The signaling procedure described is
for immediate-request calls
• Example: telephone networks
• Send a call setup request:
– if requested bandwidth is available, it is
allocated to the call
– if not, the call is blocked (rejected)
• M/G/m/m model:
– m: number of circuits
69
ErlangB formula
: offered traffic load in Erlangs
: call arrival rate
1/: mean call holding time
m: number of circuits
Pb: call blocking probability
ub: utilization
m / m!
Pb m
k
/ k!
k 0
(1 Pb )
ub
m
For a 1% call blocking probability, i.e., Pb = 0.01
1
10
100
m
ua
4
17
117
24.8%
58.2%
84.6%
70
Delay model - to compare with
TCP approach
• What happens after the call is blocked?
• If user waits and tries again, then the call
does not simply go away
• A better model would be an M/M/m/
queueing system
– approximate, since "queueing" is distributed at
the end hosts, which have no idea when to try
again
– probability of an arriving call finding all m
circuits busy is much higher than in call
blocking model since calls linger
71
Impact of increasing m at different
values of link utilization Ud
1000
U =90%
d
U =90%
d
800
U =80%
d
U =80%
d
m=10
U =60%
d
0.4
U =60%
d
Pq=41%
U =40%
d
0 0
10
400
d
U =40%
0.2
600
0.6
PQ
Prob. of arriving job finding
all m circuits busy
0.8
200
1
2
10
10
03
10
m
Link capacity expressed in channels
High-rate per-call circuits
Low-rate per-call circuits
72
Offered load: call arrival rate/call departure rate
1
Impact of mean call holding time, 1 /
5
10
30
m=1000, =1call/hour
4
m=10
3
10
18
2
m=10, =1call/hour
10
12
1
m=10, =10calls/hour
10
6
0
10
0
Mean waiting time for
delayed calls
E[W d ] (minutes)
24
m=100, =1call/hour
N
Number of ports
aggregating traffic
on to the link
10
5
10
15
20
1/ (minutes)
' : per host call-generation rate
Ud: 90%
m=100
m=1000
0
25
30
E[Wd ]
1
m (1 U d )
73
BW sharing modes in
circuit/VC networks
Large m
Moderate throughput
Small m
immediate-request
with call blocking + retries
("call queueing")
Short calls
Bank teller
(video, gaming)
immediate-request
with delayed-start times
("call queueing")
(file transfers)
•
•
m is the link capacity
expressed in channels
e.g., if 1Gbps circuits
are assigned on a 10Gbps link,
m = 10
High throughput
Long calls
Doctor's office
book-ahead
Mean waiting time is proportional to mean call holding time
Can afford to have a queueing based solution when m is
small if calls are short
74
How is bandwidth shared on a
virtual-circuit network?
• In connection-oriented packetswitched networks,
– bandwidth allocation to a virtual circuit
is independent of label selection
• In circuit-switched networks,
– when "labels" are selected (e.g.,
timeslots are selected on a SONET link),
it means bandwidth allocation to the
circuit is immediately fixed
75
Savings in bandwidth allocation
over circuit-switched networks
peak bandwidth assignment C L NR p
Bandwidth
required
QoS specified
bandwidth assignment
CL
average bandwidth assignment
admissible region
N
Number of sources
76
Mischa Schwartz's 1996 textbook on broadband networks
Bandwidth allocation
for virtual circuits
• How is bandwidth allocated to a
virtual circuit?
– Call setup request carries
• traffic descriptor parameters
• desired quality-of-service parameters
– Call admission control algorithm is
executed at the switch controller to
determine
• bandwidth allocation for the virtual circuit
• buffer space allocation for the virtual circuit
77
Traffic descriptors
• Peak rate
• Sustained rate (average)
• Mean Burst Size
78
QoS measures
• Packet Loss Ratio
• Packet Transfer Delay
• Packet Delay Variance
79
Traffic source model
• On-off Markov model to characterize
the traffic source: fluid flow model
OFF
ON
Rp
OFF
ON
OFF
mean:
1/
mean:
1/
ON
OFF
time
probability that the source is the ON state: p /( )
80
Traffic descriptors values for
ON-OFF model
• Peak rate = Rp
• Sustained rate (average) = pRp
• Mean Burst Size = Rp/
81
N sources instead of
one source
• To compute bandwidth allocation, we set up the
problem assuming N homogeneous independent
sources, each of which can be represented by the
same ON-OFF model (with the same parameter
values)
1
N
CL
buffer length = x
82
"Equivalent bandwidth"
C min(Cs , C f )
• Two approximations (both conservative):
– Stationary approximation (buffer is ignored)
– Flow approximation (statistical multiplexing is
ignored)
• Seminal paper by Guerin, Ahmadi and
Naghshineh, JSAC 1991
83
Flow approximation
2
1 k
CL
1
k
Cf
Rp
kp
N
2
2
x
k
R p (1 p) ln(1 / PL )
•
•
•
•
•
•
x:
PL:
Rp:
p:
N:
1/:
buffer size
packet loss ratio
peak rate
probability of source being in ON state
number of sources
mean ON-state duration
84
Stationary approximation
peak bandwidth assignment:
C NR p
QoS-specified allocation: CS mR p
m pN
Np(1 p)
2
p
( )
more than average
C S ( m K ) R p
Cs m ln(2 ) 2 ln R p
•
•
•
•
m: average number of ON sources
2: variance of the number of ON sources
: probability of being in the overload region
Use binomial distribution to find m and 2
PL
85
Example
•
•
•
•
•
•
•
x: buffer size = 3 Mbits
PL: cell loss ratio = 10-5
Rp: peak rate = 4 Mbps
p: ON-state probability = 0.35
link capacity
CL: number of sources = 400Mbps
1/: mean ON-state duration = 100msec
k = 0.65/(1-p) = 1
CL
Cf
0.59 R p 2.36 Mbps
N
Therefore number of calls that can be admitted is:
CL
N
169
2.36
instead of 100 (peak-rate allocation)
86
Need data-plane algorithms to
achieve QoS guarantees
Call Admission Control
Scheduling
(example: weighted fair queueing)
Traffic shaping/policing
(example: leaky-bucket algorithm)
87
Outline
• Principles
– Different types of connection-oriented
networks
Technologies
– Single network
– Internetworking
• Usage
– Commercial networks
– Research & Education Networks (REN)
88
Technologies
• Connection-oriented (CO) networks
– Data-(user-) plane protocols
• packet-switched: MPLS, VLAN Ethernet, Intserv IP
• circuit-switched: SONET/SDH, WDM, SDM
– Control-plane protocols:
• RSVP-TE
• OSPF-TE
• LMP
• Internetworking
– GFP, VCAT, LCAS for SONET/SDH
– PWE3 for MPLS networks
– Digital wrapper for OTN
89
MPLS Architecture
1: Label Switched Path (LSP): Term used for virtual circuits in MPLS networks
Label Switched Path (LSP)
Label Ingress Router (LIR)
Entry point into MPLS network: isolating packets to map to LSP
Label Egress Router (LER)
●
Exit point, removes label and routes based
on native format
Label Switched Router (LSR)
Routers along the path that examine the top
label in stack and forward accordingly
MPLS header
MPLS Header
Label Value
20 Bits
CoS S
3
1
TTL
8
• Label Value
– (20 bits) Label used to identify the virtual circuit
• Class of Service (CoS)
– (3 bits) Experimental field, Used for QoS support
• S
– (1 bit) Identifies the bottom of the label stack
• TTL
– (8 bits) Time-To-Live value
MPLS label stacking
MPLS header
•
•
...
MPLS header
MPLS labels can be stacked
What does this mean?
– Create one virtual circuit (VC) on a link
– Say we allocate 100Mbps to this VC
– We can create another VC within this VC and allocate it a portion of this
100Mbps
•
Why is label stacking required?
– Expected to be required originally for scalability
– Most vendors support at least 4 levels (Malis' paper)
– Currently, this has become a useful feature for pseudo-wire services
(point-to-point services) and VPNs (multipoint)
Andy Malis paper in IEEE Comm. Mag., Sept. 2006
MPLS Label Stacking:
hierarchical packet forwarding
PoS
MPLS
MPLS
IP
...
PoS
MPLS
Eth
PoS
MPLS
IP
IP
IP
IP
...
Label for DC to Sunnyvale LSP
Label for St. Louis to Phoenix LSP
Label pushed on stack at Chicago LSR to route to Denver
...
...
...
IEEE 802.1Q Ethernet VLAN
new fields
Dest. MAC Source MAC
TPID TCI Type
Address
Address
/Len
Data
FCS
FCS: Frame
Check
Sequence
VLAN Tag
User
802.1Q Tag Type
CFI
Priority
2 Bytes
3 Bits
1 Bit
VLAN ID
12 Bits
VLAN Tag Fields
• Tag Protocol Identifier (TPID)
– (2 bytes) 802.1Q Tag Protocol Type – set to 0x8100 to
identify the frame as a tagged frame
• Tag Control Information (TCI)
– User Priority
• (3 bits) As defined in 802.1p, 3 bits represent eight priority
levels
– CFI
• (1 bit) Canonical Format Indicator, set to indicate the
presence of an Embedded-RIF
– VLAN ID
• (12 bits) VID uniquely identifies the frame's VLAN
Integrated services (Intserv)
IP network
• "Label" on which switch performs its
forwarding function:
–
–
–
–
–
Destination IP address
Source IP address
Protocol field in IP header: TCP or UDP
Destination TCP or UDP port number
Source TCP or UDP port number
96
SONET Equipment
• By Functionality
– Add/Drop Multiplexers (ADMs): dropping & inserting
tributaries
– Regenerators: digital signal regeneration
– Cross-Connects: interconnecting SONET streams
• By Signaling between elements
– Section Terminating Equipment (STE): span of fiber between
adjacent devices, e.g. regenerators
– Line Terminating Equipment (LTE): span between adjacent
multiplexers, encompasses multiple sections
– Path Terminating Equipment (PTE): span between SONET
terminals at end of network, encompasses multiple lines
97
Courtesy: Leon-Garcia and Widjaja's textbook
Section, Line, & Path in SONET
PTE
LTE
LTE
SONET
terminal
MUX
Section
STE
STE
STE
Reg
Reg
Reg
Section
Section
MUX
PTE
SONET
terminal
Section
STS Line
STS-1 Path
STE = Section Terminating Equipment, e.g., a repeater/regenerator
LTE = Line Terminating Equipment, e.g., a multiplexer
PTE = Path Terminating Equipment, e.g., a crossconnect
98
Courtesy: Leon-Garcia and Widjaja's textbook
Section, Line, & Path Layers in
SONET
Path
Path
Line
Line
Section
Section
Section
Section
Optical
Optical
Optical
Optical
Line
Line
Section
Section
Section
Optical
Optical
Optical
• SONET has four layers
– Optical, section, line, path
– Each layer is concerned with the integrity of its
own signals
• Each layer has its own protocols
– SONET provides signaling channels for
elements within a layer
Courtesy: Leon-Garcia and Widjaja's textbook
99
SONET STS Frame
• SONET streams carry two types of
overhead
• Path overhead (POH):
– inserted & removed at the ends
– Synchronous Payload Envelope (SPE) consisting
of Data + POH traverses network as a single
unit
• Transport Overhead (TOH):
– processed at every SONET node
– TOH occupies a portion of each SONET frame
– TOH carries management & link integrity
information
100
Courtesy: Leon-Garcia and Widjaja's textbook
STS-1 Frame
810x64kbps=51.84
Mbps
810 Octets per frame @ 8000 frames/sec
90 columns
A1 A2 J0
J1
B1 E1 F1 B3
1
Order of
2 transmission
D1 D2 D3 C2
H1 H2 H3 G1
9 rows
Special OH octets:
B2 K1 K2 F2
D4 D5 D6 H4
A1, A2 Frame Synch
B1 Parity on Previous Frame
(BER monitoring)
J0 Section trace
(Connection Alive?)
H1, H2, H3 Pointer Action
K1, K2 Automatic Protection
Switching
D7 D8 D9 Z3
D10 D11 D12 Z4
S1 M0/1 E2 N1
3 Columns of
Transport OH
Synchronous Payload Envelope (SPE)
1 column of Path OH + 8 data columns
Section Overhead
Path Overhead
Line Overhead
Data
Courtesy: Leon-Garcia and Widjaja's textbook
101
Optical transport networks
• ITU-T G.872 specifies an optical transport
network (OTN) architecture, which defines
two interface classes
– Inter-domain interface (IrDI): interface
between operators/vendors; defined with 3R
processing (retiming, reshaping, and
regeneration)
– Intra-domain interface (IaDI): interface within
an operator/vendor domain
• ITU-T G.709 is about the information
transferred across IrDI and IaDI
interfaces
– Defines several layers in the OTN hierarchy
102
Objective and features
• Need to support the transmission needs of today’s diverse
digital services on optical links
• Need to equip DWDM equipment with operational,
administration, and maintenance functionalities, similar to
those seen in SONET/SDH
• Advantages relative to SONET/SDH
– Management of optical signals in the optical domain
• without O/E/O conversion
– Transparent transport of client signals
– Stronger Forward Error Correction (FEC)
• G. 872 layers
– OTS: Optical Transmission Section
– OMS: Optical Multiplex Section
– OCh: Optical Channel
103
Layers within an OTN
104
Courtesy: T. Walker's tutorial
OTN Hierarchy
Low layer
Higher layers
• Electrical domain:
– OTU: Optical Channel Transport Unit
– ODU: Optical Channel Data Unit
– OPU: Optical Channel Payload Unit
Courtesy: T. Walker's tutorial
105
G. 709 Optical Channel frame structure
(digital wrapper)
OCh overhead
OCh payload
FEC
• Optical channel (OCh) overhead: support operations,
administration, and maintenance functions
• OCh payload: can be STM-N, ATM, IP, Ethernet, GFP
frames, OTN ODUk, etc.
• FEC: Reed-Solomon RS(255, 239) code recommended;
roughly introduces a 6.7% overhead
• Frame size: 4 rows of 4080 bytes
• Frame period:
– OTU1 – 48.971 μs (payload data rate: roughly 2.488 Gbps )
– OTU2 – 12.191 μs (payload data rate: roughly 9.995 Gbps )
– OTU3 – 3.035 μs (payload data rate: roughly 40.15 Gbps )106
References for OTN
• ITU-T G. 872 and G.709/Y.1331 Specifications
• T. Walker, “Optical Transport Network (OTN) Tutorial”,
Available online: http://www.itu.int/ITUT/studygroups/com15/otn/OTNtutorial.pdf
• Agilent, “An overview of ITU-T G.709,” Application Note
1379
• P. Bonenfant and A. Rodriguez-Moral, "Optical Data
Networking," IEEE Communications Magazine, Mar. 2000, pp.
63-70.
• E. L. Varma, S. Sankaranarayanan, G. Newsome, Z.-W. Lin,
and H. Esptein, “Architecting the Services Optical
Network,” IEEE Communications Magazine, Sept. 2001, pp.
80-87.
107
Technologies
• Connection-oriented (CO) networks
– Data-(user-) plane protocols
• packet-switched: MPLS, VLAN Ethernet, Intserv IP
• circuit-switched: SONET/SDH, WDM, SDM
– Control-plane protocols:
RSVP-TE: signaling protocol
• OSPF-TE: routing protocol
• LMP
• Internetworking
– PWE for MPLS networks
– GFP, VCAT, LCAS for SONET/SDH
– Digital wrapper for OTN
108
The evolution of
Resource reSerVation Protocol (RSVP)
• RSVP (RFC2205, 1997)
• RSVP-TE (RFC 3209, 2001)
• RSVP-TE GMPLS Extension (RFC 3471,
3473, 2003)
• RSVP-TE GMPLS Extension for
SONET/SDH (RFC 3946, 2004, RFC
4606, 2006)
109
RSVP-RFC 2205
• Designed to support integrated services on the Internet
• Reserve resources to meet required QoS measures for a
data flow
• Seven messages:
– Path, Resv, PathErr, ResvErr, PathTear, ResvTear, and
ResvConf (trigged by an optional object, RESV_CONFIRM,
in Resv messages)
• All messages begin with a common header, followed by a
body consisting of a variable number of “objects”
• Common header format
Vers Flags
Msg Type
RSVP Checksum
Send_TTL
(Reserved)
RSVP Length
110
Path message
• Three mandatory objects
– SESSION
• Carries the destination address of an LSP1
– RSVP_HOP
• Used to identify the GMPLS neighbor node
(sender/receiver of signaling message)
– TIME_VALUES
• Set refresh timer
• Optional objects
– SENDER_TEMPLATE
• Carries the source address of an LSP
– SENDER_TSPEC
• Carries traffic descriptor parameters (IntServ Tspec)
1: Label Switched Path (LSP): Term used for virtual circuits in MPLS networks
111
Key objects: destination
and label
• Session object:
– Carries the destination IP address
– IP protocol type field (TCP or UDP)
– Destination TCP or UDP port number
• Sender-template object
– Carries the source IP address
– Source TCP or UDP port number
Compare with principles slides for CO PS networks
112
Key objects: traffic descriptor
and QoS metrics
• Sender Tspec: Traffic descriptor
• AdSpec: QoS metrics
113
IntServ Tspec (RFC 2210)
Object format:
114
RSVP-TE (RFC 3209)
• RSVP extensions to support MPLS
• What is new?
– A new message, “Hello”, for node failure detection
– Change of the Path message
• Updates of some objects
– SESSION
– SENDER_TSPEC
– …
• A new mandatory object
– LABEL_REQUEST
• Two optional objects become mandatory
– SENDER_TEMPLATE
– SENDER_TSPEC
• A new optional object
– EXPLICIT_ROUTE object (ERO)
115
SESSION object
•
Original SESSION object (RFC 2205)
•
New SESSION object (RFC 3209)
– IPv4 tunnel end point address: IP address of the egress node for the
tunnel
– Tunnel ID: An ID that remains constant over the life of the tunnel
– Extended Tunnel ID: Can be set to the IP address of the ingress node
to narrow the scope of the session to the ingress-egress pair
116
SENDER_TEMPLATE object
• Original format (RFC 2205)
• New format (RFC 3209)
117
LABEL_REQUEST object
• Three types
– Without label range
– With an ATM label range
– With a Frame Relay label range
118
Explicit Route Object (ERO)
• A list of groups of nodes along the explicit
route (generically called "source route")
• Thinking: source routing is better for calls
than hop-by-hop routing (which is used for
packet forwarding) as it can take into
account loading conditions
• Constrained shortest path first (CSPF)
algorithm executed at the first node to
compute end-to-end route, which is
included in the ERO
119
Source routing
• Many papers describe the call setup
procedure as ingress node performing
CSPF or Routing and Timeslot
Allocation (RTA), and then sending an
RSVP message with an ERO
– contrast with the hop-by-hop approach
described in the Principles section
120
Source routing
Routing updates from Chicago to NYC about its link to SF
OC3 left
0 bandwidth left
Call setup Path
message from NYC to SF
OC12
Chicago
NYC
SF
ATL
•
•
NYC trusts the "OC3 left" message from Chicago and routes the call to
Chicago to reach SF
This works if call arrival rate is low; if this rate is high and Chicago to SF
calls could have used up the OC3 before the next update and the signaling
121
request arrives in between, this will not work.
RSVP-TE extension for GMPLS
(RFC 3471, 3473)
• RSVP-TE extension for Generalized MPLS
• What is new?
– A new message, “Notify”, for supporting fast failure
notification
– Update of objects
• Generalized LABEL_REQUEST
• Generalized LABEL
– Support labels to identify timeslots, wavelengths, etc
– The label “class” is implicit in the multiplexing capability of the
link
– Interface ID field added to RSVP-HOP object, ERO
– A new object
• UPSTREAM_LABEL – support bidirectional setup
122
Generalized LABEL_REQUEST
object
– LSP Encoding Type: encoding of the LSP being requested
• e.g.: Ethernet, SONET, Digital Wrapper… - lowest layer
– Switching Type: type of multiplexing
• e.g.: TDM, LSC, FSC …
– Generalized PID: identify the payload of the LSP - what
is carried on the LSP
• e.g.: SONET/SDH for Lambda encoding
DS1 /DS3 for SONET encoding
123
Need for Interface ID
• Separation of control plane from data
plane in GMPLS networks - out-of-band
Internet
IP router
IP router
Control-plane messages
Ethernet control ports
GMPLS Network
Ethernet control ports
Circuit
established
SONET
or WDM switch
Data-plane link
SONET
or WDM switch
124
Need for Interface ID
• Control plane separation:
– Requires upstream switch to identify on which data-plane
interface the virtual circuit should be routed
– Interface ID field defined in the tag-length-value
format
• Identifier types:
– IPv4 or IPv6 address ("numbered" link)
– Interface index ("unnumbered" link)
» Saves on IP addresses
» Little need to allocate a separate address to each
interface of a SONET switch
– Embedded within the RSVP-HOP object
125
Unnumbered Links (RFC 3477)
• Unnumbered links: links that are not
assigned IP addresses
• Two issues:
– How to carry TE information about unnumbered
links in IGP TE extensions (covered by GMPLSISIS and GMPLS OSPF)?
– How to specify unnumbered links in GMPLS
signaling?
• An unnumbered link has to be point-to-point
• The switch at each end assigns a 32-bit ID to the link
• Unnumbered interface IDs (IF_IDs) are supported in
RSVP_HOP object and ERO, etc.
126
Unidirectional vs. Bidirectional
• In RFC 3209, to set up a bidirectional LSP, two
unidirectional paths must be established
independently
• UPSTREAM_LABEL object
– Indicates the request of a bidirectional circuit
– Same format as the LABEL object
• Why do we need this?
– Reduce setup delay and control overhead
– Avoid race conditions in resource assignment
– Bidirectional optical LSPs are often required in optical
networking services (many vendors only support
bidirectional setup)
127
RSVP-TE GMPLS extension for
SONET/SDH (RFC 4606)
• Label and bandwidth parameters changed
– A new LABEL format for SONET/SDH –
SUKLM
– A new Tspec format for SONET/SDH Traffic
128
SONET_/SDH_Tspec
– Signaling type: the type of elementary signal
• Eg: VT1.5, STS-1, STS-12…
–
–
–
–
RCC: requested contiguous concatenation
NCC: number of contiguous components
NVC: number of virtual components
MT: number of identical signals requested
129
SONET/SDH LABEL - SUKLM
• Five parameters but only some of them are significant for
different multiplexing schemes
(Use SONET as an example)
– S=1->N: the index of a particular STS-3 inside an STS-N
multiplexed signal
– U=1->3: the index of a particular STS-1_SPE within an STS-3
– K=1->3: for SDH only
– L=1->7: the index of a particular VT_Group within an STS1_SPE
– M: the index of a particular VT1.5/2/3_SPE
130
RSVP-TE signaling procedures
• Distribute bandwidth management
functionality to each switch for its own
interfaces
• 5 steps of circuit setup processing at each
switch
–
–
–
–
–
Message parsing
Route determination
Connection admission control
Date-plane configuration
Message construction
131
RSVP-TE signaling procedures
• Data tables maintained at each switch
– Routing table
• Simplest: next-hop node to reach destination
• Precomputed after routing information is
collected by OSPF-TE
– Connectivity table
• Data-plane interfaces and interface IDs
• Control-plane address correlation
– CAC table
• Available bandwidth for each data-plane
interface
– State table
• Information about each live circuit or VC
132
Path message processing:
main step
SESSION
SENDER_TEMPLATE
Search State table to
check if session
exist
Yes
(Refresh)
No
assumes hop-by-hop routing
of the call
Search Routing table for next hop
Route found
From SENDER_TSPEC
No
PathErr
Yes
Allocate bandwidth on data-plane interface outgoing to the next hop (CAC)
Yes
Allocation
successful
No
PathErr
Yes
Update CAC table
133
DONE
Processing of Resv message:
main step
LABEL
Outgoing_label(s) <- Label(s)
From SESSION & FILTER_SPEC
Outgoing_Label(s)
in accordance with
Outgoing_assigned_Timeslo
ts
No
ResvErr
Yes
Update Outgoing CAC table if necessary
From SESSION & FILTER_SPEC
Program switch fabric with
Incoming/outgoing physical interface ID
and Incoming/outgoing labels
DONE
134
Technologies
• Connection-oriented (CO) networks
– Data-(user-) plane protocols
• packet-switched: MPLS, VLAN Ethernet, Intserv IP
• circuit-switched: SONET/SDH, WDM, SDM
– Control-plane protocols:
• RSVP-TE
OSPF-TE
• LMP
• Internetworking
– GFP, VCAT, LCAS for SONET/SDH
– PWE3 for MPLS networks
– Digital wrapper for OTN
135
OSPF-TE
• OSPF-TE adds more attributes to links in
OSPF link state advertisements (LSA).
• These LSAs are distributed in a given
OSPF area.
• Routers build an extended link database
based on these LSAs that can be used to
– Monitor the link attributes.
– Perform local constraint-based source routing.
– Global traffic engineering.
136
Purpose of OSPF-TE
• To advertise loading conditions
• RFC 3630 - for MPLS networks
137
OSPF-TE LSA
Link-state age
Options
Type
Link-state ID
Advertising Router
Link-state sequence number
Link-state checksum
Length
LSA Payload
(variable)
0
Common LSA header
31
138
TE-LSA Header
•
•
•
•
•
•
•
•
Link-state age: time since this LSA generation.
Options: optional functionality supported by the router.
Type: OSPF opaque LSA (=10) with area flooding scope.
Link-state ID: 1 in the first octet followed by an Instance
field in the remaining 3 octets.
Advertising router: router ID of the router generating this
LSA.
Link-state sequence number: Identifies a unique LSA to
detect losses and duplicates.
Checksum: Covering all except the age field.
Length: in bytes of the LSA including the LSA header.
139
TLV
• The TE-LSA payload carries one or more
nested Type/Length/Value (TLV) triplets
Type
Length
Value
(variable)
0
TLV format
31
• Type: either Router Address TLV (=1) or Link TLV (=2)
• Length: length of the value field in octets
140
TLV
• Router Address TLV
– Router ID of the advertising router
– Router ID is a loopback address that can be
reached via any interface (typically used in
routing protocols instead of a specific
interface IP address to avoid loss of
reachability to the router if the interface fails)
– The value field contains this IP address.
– It must appear in exactly one TE-LSA from a
router
– Purpose: assume it is to identify that the
router is a TE-capable router
141
TLV
• Link TLV
– It describes attributes of a single link.
– It is composed of a set of sub-TLVs.
– Each TE-LSA carries only one link TLV.
142
Sub-TLVs
• Contained in the value field of a Link TLV
• Multiple types of sub-TLVs are defined. Some of them are
–
–
–
–
–
–
–
–
–
Link type: Point-to-point or Multi-access.
Link id: identifies the other end of the link.
Local interface IP address
Remote interface IP address
Traffic engineering metric: typically assigned by the
administrator and could be different from the OSPF link metric
Maximum bandwidth: maximum bandwidth that can be used.
Maximum reservable bandwidth: can be greater than the
maximum bandwidth to support oversubscription
Unreserved bandwidth
Administrative group (4-byte mask: 1 bit per admin group for
link)
• Bandwidth fields (in bytes) are expressed in IEEE floating
point format
143
Link type
• Link type: point-to-point or multiaccess
• Link ID: identifies the other end of
the link as in a Router LSA
– point-to-point links: Router ID of the
neighbor
– multi-access links: interface address of
the designated router
144
OSPF-TE extensions for
GMPLS (RFC 4202 and 4203)
• New sub-TLVs for the Link TLV
–
–
–
–
Link Local/Remote Identifiers
Link Protection Type
Shared Risk Link Group
Interface Switching Capability
Descriptor (ISCD)
• main extension since GMPLS allows multiple
types of switching techniques
145
New sub-TLVs
• Link Local/Remote Identifiers
– Since GMPLS added interface IDs for
unnumbered links (i.e., links that are not
assigned IP addresses), this sub-TLV
carries those identifiers
• Link protection type: Extra, Shared,
dedicated 1:1, dedicated 1+1,
unprotected, enhanced
146
Shared risk link group (SRLG)
• SRLG: set of links that share a resource whose failure may
affect all links in the set.
– Example, two fibers in the same conduit would be in the same
SRLG.
• SRLG sub-TLV for a link is an unordered list of SRLGs that
the link belongs to. This could be more than 1.
• SRLG is identified by a 32 bit number that is unique within
an IGP domain.
147
Interface Switching Capability
Descriptor (ISCD)
Switching cap
Encoding
Reserved
Max LSP Bandwidth at priority 0
Max LSP Bandwidth at priority 1
.
.
.
Max LSP Bandwidth at priority 7
Switching Capability specific information
(variable)
0
ISCD format
31
148
Interface Switching Capability
Descriptor (ISCD)
• It describes the switching capability of the link
• Switching capability can be
–
–
–
–
–
Packet switch capable (PSC)
Layer-2 switch capable (L2SC)
Time-division-multiplex switch capable (TDM)
Lambda-switch capable (LSC)
Fiber-switch capable (FSC)
• Encoding: Same as LSP encoding in Generalized
label request object of RSVP-TE - see RFC 3471
149
Interface Switching Capability
Descriptor (ISCD)
• The maximum LSP bandwidth at priority p: the
smaller of the unreserved bandwidth at priority p
and a "Maximum LSP Size" parameter which is
locally configured on the link, and whose default
value is equal to the max link bandwidth.
150
ISCD Specific Information
• No ISCD specific information for L2SC,
and LSC.
• When the switching capability is PSC, the
following fields are generated
Minimum LSP bandwidth
Interface MTU
0
Padding
ISCD specific information for PSC
31
• Padding is used to make the ISCD 32-bits
aligned.
151
ISCD Specific Information
• For TDM switching capability, the following fields
are generated
Minimum LSP bandwidth
Indication
0
Padding
ISCD specific information for TDM
31
• Minimum LSP Bandwidth example: OC1 on a SONET interface if
the switch demultiplexes down to OC1 level
• The indication field takes a binary value stating whether the
interface supports standard or arbitrary SONET/SDH
• Optionally, how many time-slots are free on a TDM link can be
incorporated in the ISCD specific information field
– 32 bit tuple: <signal_type(8 bits), number of unallocated
timeslots(24 bits)>
152
References for OSPF-TE
•
•
•
•
•
•
•
•
RFC 2702 - Requirements for Traffic Engineering Over MPLS:
http://www.faqs.org/rfcs/rfc2702.html
RFC 3630 - Traffic Engineering (TE) Extensions to OSPF Version 2:
http://www.faqs.org/rfcs/rfc3630.html
RFC 4203 - OSPF Extensions in Support of Generalized Multi-Protocol Label
Switching (GMPLS) : http://www.ietf.org/rfc/rfc4203.txt
RFC 2328 - OSPF Version 2 : http://www.ietf.org/rfc/rfc2328.txt
OSPFv2 Routing Protocols Extensions for ASON Routing:
http://www.ietf.org/internet-drafts/draft-ietf-ccamp-gmpls-ason-routingospf-02.txt
RFC 4202 - Routing Extensions in Support of Generalized Multi-Protocol
Label Switching (GMPLS): http://www.ietf.org/rfc/rfc4202.txt
RFC 3471- Generalized Multi-Protocol Label Switching (GMPLS) Signaling
Functional Description: http://www.faqs.org/rfcs/rfc3471.html
Dimitri Papadimitriou, IETFInternet Draft, "OSPFv2 Routing Protocols
Extensions for ASON Routing," draft-ietf-ccamp-gmpls-ason-routing-ospf02.txt, October 2006.
153
Difference between labels in MPLS
and circuit-switched GMPLS
• In circuit-switched GMPLS networks, labels are
not carried in the data plane
– Labels in circuit-switched networks identify "position" of
data for the circuit - time or wavelength
• In circuit-switched GMPLS networks, cannot
assign labels without associated bandwidth
reservation
– In usage section, we will see the value of this feature in
MPLS networks
– See two applications: traffic engineering, VPLS
(addressing benefits)
154
Technologies
• Connection-oriented (CO) networks
– Data-(user-) plane protocols
• packet-switched: MPLS, VLAN Ethernet, Intserv IP
• circuit-switched: SONET/SDH, WDM, SDM
– Control-plane protocols:
• RSVP-TE
• OSPF-TE
LMP
• Internetworking
– PWE3 for MPLS networks
– GFP, VCAT, LCAS for SONET/SDH
– Digital wrapper for OTN
155
LMP procedures
• Control channel management
– Set up and maintain control channels between
adjacent nodes
• Link property correlation
– Aggregate multiple data links into a TE link
– Synchronize TE link properties at both ends
• Link connectivity verification (optional)
– Data plane discovery; If_Id exchange; physical
connectivity verification
• Fault management (optional)
– Fault notification and localization
156
Reference: IETF RFC 4204
What is a control channel?
• A control channel is a pair of mutually
reachable interfaces that are used to
enable communication between nodes
for routing, signaling, and link
management.
• Obvious question: bootstrap issue
– how do you exchange messages on a
control channel to create a control
channel?
157
Types of control channels
• LMP does not specify the exact
implementation of the control channel
• Examples of control channels:
– a separate wavelength or fiber
– an Ethernet link
– an IP tunnel through a separate
management network (e.g., Internet)
– the overhead bytes of a data link (e.g.,
DCC)
158
Control channel identifier
(CC_Id)
• A number from the space in which
unnumbered interface IDs are assigned by
a node
– a 32-bit integer unique to the node
• Assign IP addresses to control channel
ends
– Because LMP runs over UDP/IP (UDP port
number: 701)
– remote end IP address: manually configured or
automatically discovered
159
Automatic discovery
• How does a node automatically discover the
IP address assigned to remote end of one
of its control channels:
– Config message sent:
• source IP address: unicast address
• destination IP address: multicast 224.0.0.1
• Config ACK message returned with destination IP
address
– Used when control channel is a DCC channel
within a data link
160
Control channel management
• Config, ConfigAck, ConfigNack messages
– Specify
•
•
•
•
Control_Channel_ID
Node_ID (Router ID used in routing protocols)
Hello protocol parameters (hello interval and dead interval)
Message_ID - just for ARQ support for these LMP message
exchanges
– process used in RSVP too because RSVP runs on IP
• Hello messages - a lightweight keep-alive
mechanism
– Used to maintain control channel connectivity and detect
control channel failure
• Multiple control channels allowed
– Useful in case of control channel failure
161
Link property correlation
• Message LinkSummary
– Summarizes TE link information (data-plane interfaces);
Indicates support for fault management and link
verification procedures
• Message LinkSummaryAck
– Signals agreement on message LinkSummary
• Message LinkSummaryNack
– Indicates disagreement; may suggest alternative values
for negotiable parameters
– Example: if one end of a TE-link is assigned an IPv4
address and the other end is assigned an IPv6 or
unnumbered interface ID, there is a problem
162
Link connectivity verification
(optional)
• Obj: Verify physical connectivity of data links and dynamically learn
the TE link and interface ID associations.
– A node must be able to send message over any data link
• Procedure
– Exchange of a pair of BeginVerify and BeginVerifyACk message over a
control channel
– Upstream node sends Test messages with local If_Id on a data link
– Downstream node replies with TestStatusSuccess or TestStatusFailure
accordingly over the control channel
– If TestStatusSuccess, upstream node records the mapping of local
If_Id and remote If_Id, marks the link as “Up”, and then follows up
with a TestStatusAck message for acknowledgement. If
TestStatusFailure, marks the link as “Failed”.
– Use EndVerify message to complete the procedure when all data links
are tested.
163
Fault management (optional)
• For failure notification and localization only
– Assume fault detection done at lower layer, e.g., loss of light
observed at physical layer
• Purpose of procedure:
– "To avoid multiple alarms stemming from the same failure,
LMP provides failure notification through the ChannelStatus
message"
Reference: IETF RFC 4204
164
Fault management procedure
cb
a
Node 1
Node 2
Node 3
Node 4
Node 5
A failure occurs between Nodes 2 and 3:
a.
Node 3 (downstream node) will detect the failure and send a ChannelStatus message
to node 2 indicating the failure.
b.
Node 2 will immediately acknowledge this message by returning a ChannelStatusAck
message.
c.
Node 2 will then correlate the message to see if the failure is also detected locally
d.
If there is no problem on the input side to Node 2 and within Node 2, it means the
failure is localized
e.
Node 2 then sends a ChannelStatus message to node 3 indicating that the failure has
been localized and that the link is either failed or OK
165
•
Presumably, if there was a protection path, Node 2 could quickly restore the
channel and send an OK status.
Control-plane security
• Need authentication and integrity for
all control-plane exchanges
• Since RSVP, OSPF, LMP run over IP,
IPsec is a possible solution
166
Technologies
• Connection-oriented (CO) networks
– Data-(user-) plane protocols
• packet-switched: MPLS, VLAN Ethernet, Intserv IP
• circuit-switched: SONET/SDH, WDM, SDM
– Control-plane protocols:
• RSVP-TE
• OSPF-TE
• LMP
Internetworking
– GFP, VCAT, LCAS for SONET/SDH
– PWE3 for MPLS networks
– Digital wrapper for OTN
167
Why internetworking?
• GMPLS networks do not exist as standalone
entities
• Instead they are part of the Internet:
– Obvious usage: to interconnect IP routers
– Newer uses:
• Commercial: interconnect Ethernet switches in
geographically distributed LANs via point-to-point
links or VPNs
• Research & Education networks: connect GbE and
10GbE cards on cluster computers and storage
devices to GMPLS networks
168
Obvious usage
• Router-to-router circuits and virtual
circuits
Internet
IP router
IP router
GMPLS Network
SONET
or WDM switch
SONET
or WDM switch
169
Router-to-router usage
• OSPF-enabled usage
– simply treat MPLS virtual circuit or
GMPLS circuit as a link between routers
– allow routing protocol to include these in
routing table computations
• Data-plane
– IP over MPLS
– IP over PPP over SONET
• Packet-over-SONET (PoS)
170
IP over MPLS
PoS
MPLS
Eth.
Eth
Label Switched Path (LSP) from DC to
Sunnyvale, CA
IP
IP
IP
...
...
Newer uses
• Ethernet over MPLS/GMPLS
VC/circuits:
– port mapped
– VLAN mapped
172
Ethernet port mapped
over MPLS
SDM-to-MPLS gateway
IP router/MPLS switch
Pseudowire
Internet
II
I
Ethernet switch
SDM-to-MPLS gateway
IP router/MPLS switch
MPLS virtual
circuit
Ethernet switch
Mux scheme on this link: Ethernet
Enterprise 1
•
•
•
•
Gateway: interfaces have different MUX schemes
unlike switch ("my definition")
Enterprise 2
Send all Ethernet frames received on ports I and II on to the MPLS virtual
circuit
MPLS virtual circuit: Pseudo-wire
Enterprise can allocate IP addresses from one subnet: Virtual private LAN
Explains one use for MPLS virtual circuits with no bandwith allocation
SDM: Space Division Multiplexing
173
Ethernet VLAN mapped
over MPLS
VLAN-to-MPLS gateway
IP router/MPLS switch
Internet
II
I
Ethernet switch
Enterprise 1
VLAN-to-MPLS gateway
IP router/MPLS switch
MPLS virtual
circuit
Ethernet switch
Enterprise 2
• Extract frames carrying a specific VLAN ID tag on Ethernet
ports I and II and map only these frames on to the MPLS
virtual circuit
174
Ethernet port or VLAN mapped
over GMPLS circuits
SDM-to-SONET/WDM gateway
SONET or WDM switch
SDM-to-SONET/WDM gateway
SONET or WDM switch
II
I
Ethernet switch
Enterprise 1
•
•
SONET/SDH/WDM
circuit
Ethernet switch
Enterprise 2
Send all frames or frames matching a given VLAN ID tag from
Ethernet ports I and II on to the SONET/SDH/WDM circuit
SONET/SDH/WDM switches now have Fast Ethernet/GbE/10GbE
interfaces in addition to SONET/SDM or WDM interfaces
175
Commercial services
• EPL: Ethernet private line: map an
Ethernet port to a SONET/SDH
circuit
• Fractional-EPL: Map a GbE port to a
lower-rate SONET circuit
– Pause frames received from switch to
client node on the other side of the GbE
• V-EPL: Lower-rate VLAN mapped to
an equivalent rate SONET circuit
176
page 110 of GFP section reference: SONET focused
REN application
•
•
Cluster computers, disk arrays, visualization clusters have GbE/10GbE
interfaces
Network: SONET/SDH/WDM or MPLS, for rate-guaranteed service
LCD
panel
Computer cluster
Disk
array
Computer cluster
177
Technology
• So what technologies are required for
this type of internetworking:
– mapping Ethernet frames on to
MPLS/GMPLS virtual circuit/circuit
mapping?
178
Technologies
• Connection-oriented (CO) networks
– Data-(user-) plane protocols
• packet-switched: MPLS, VLAN Ethernet, Intserv IP
• circuit-switched: SONET/SDH, WDM, SDM
– Control-plane protocols:
• RSVP-TE
• OSPF-TE
• LMP
• Internetworking
GFP, VCAT, LCAS for SONET/SDH
– PWE for MPLS networks
– Digital wrapper for OTN
179
Reference
• IEEE Communications Magazine, May
2002, Special issue on "Generic
Framing Procedure (GFP) and Data
over SONET/SDH and OTN," Guest
Editors, Tim Armstrong and Steven S.
Gorshe
• 6 excellent papers
180
What is GFP?
• Generic Framing Procedure (GFP) is a
mechanism to transport packet-based
data streams or block-oriented data
streams over a synchronous
communications channel, such as
SONET/SDH
• My classification: It is a data-link
layer protocol
181
Protocol stacks for various data
transport applications
IP, IPX, MPLS, etc
PPP
RPP
FICON
Ethernet
ESCON
Fiber Channel
SANs
HDLC
GFPGFP
ATM
SONET/SDH
OTN
WDM
dark fiber
page 97 of reference
182
Why do we need GFP?
• Why do we need yet another data-link
layer protocol?
– More specifically, to transport data
packets over synchronous links?
183
Main reason
• The framing techniques used in other data-link layer
protocols have problems
• For example, IP packets are carried over SONET using
PPP/HDLC frames (called PoS)
– HDLC inserts idle frames because SONET is synchronous it
needs a constant flow of frames to avoid losing synchronization
• But, there is a problem:
– HDLC uses flags for frame delineation. The issue with this
framing technique is that if the flag pattern occurs in the
payload, an escape byte has to be inserted
– This causes an increase in the required bandwidth
– The amount of increase is payload-dependent
184
page 98 of reference
Other framing techniques
• HEC - Header Error Control
– this is the CRC framing technique used in ATM
– "A header CRC hunting mechanism is employed by the receiver
to extract the ATM cells from the bit/byte synchronous
stream. The HEC location is fixed and ATM cell length is fixed.
Starting from the assumed cell boundary, the ATM receiver
compares its computed HEC value for the assumed ATM cell
header against the HEC value indicated by the assumed HEC
field. Cell stream delineation is declared after positive
validations of the incoming HEC fields of a few consecutive
ATM cells."
• ATM cells are fixed in length, but Ethernet frames are
variable-length
• Therefore, we need a length field in order to implement this
HEC-based frame delineation mechanism
185
pages 96-97 of reference
Main features of the
GFP protocol
• Common aspects:
– HEC + Length based delineation
• Core header has payload length and HEC
– Error control: error detection
• Payload type HEC, payload Frame Check Sequence (CRC-32)
– Multiplexing: linear and ring extension headers
– Idle frames are sent to maintain synchronization as in
HDLC
– Scrambling as in ATM:
• core header + payload scrambling
– Client management - client fail signal
• Client-dependent aspects:
– Client-specific encapsulation techniques
page 68 of reference
186
GFP frame types
GFP frames
Client frames
Client data
frames (CDFs)
Control frames
Client management
frames (CMFs)
Idle frames
OA&M frames
• CDFs: client data.
• CMFs: information associated with the management of the
client signal or GFP connection
• Idle frames: 4-byte GFP control frames
• OA&M frames: operations, administration, and maintenance
187
page 65 of reference
GFP frame structure
Client data
frames
Payload length
MSB
Payload length
LSB
Core
header
Core HEC MSB
Payload
Area
Payload header
Payload
information
N [536,550]
or
variable length
packets
Payload FCS
Bit transmission
Byte order
transmission
order
Core HEC LSB
Payload type
MSB
Payload type
LSB
Type HEC MSB
Type HEC LSB
0-60 bytes of
extension
headers
(optional)
page 66 of reference
Payload FCS
MSB
Payload FCS
Payload FCS
Payload FCS
LSB
PTI PFI EXI
UPI
CID
Spare
Extension HEC
MSB
Extension HEC
LSB
Linear extension
Header shown
(others may apply)
Client control frames
0x00(0xB6)
0x00(0xAB)
0x00(0x31)
188
0x00(0xE0)
Idle frame (scrambled)
GFP core header
• Payload length indicator (PLI): 2 bytes
– the size of the payload area in bytes
– allows GFP frame delineation independent of the content of
higher-layer PDUs
• Core HEC (cHEC): 2 bytes
– CRC16 to enable delineation
Hunt
Correct
cHEC
Incorect cHEC
for M frames
Incorrect
cHEC
Sync
Correct cHEC
for N frames
Presync
189
page 68 of reference
GFP payload area
• Payload header: 4-64 bytes
– Payload type: mandatory field; 2 bytes; the content and
format of the payload
• Payload type identifier (PTI): 3 bits; the type of GFP client
frames (CDF or CMF)
• Payload FCS Indicator (PFI): 1 bit; the presence of the
payload FCS field
• Extension Header Identifier (EXI): 4 bits; the type of
extension header GFP (e.g., linear extension header)
• User Payload Identifier (UPI): 8 bits; the type of payload
– Type Hec (tHEC): 2 bytes; CRC-16 to protect the payload
type field
190
GFP payload area
• Payload header:
– Extension headers: 0-60 bytes (optional)
• Null Extension Header: 0 bytes; by default
• Linear Extension Header: 2 bytes; multi-access link
– Channel ID (CID): 1 byte; like MPLS label or VLAN ID
for multiplexing
– Spare field: 1 byte
• Ring Extension Header: sharing of the GFP payload
across multiple clients in a ring configuration
– Extension HEC (eHEC): mandatory; 2 byte; CRC16 to protect the extension header
191
GFP payload area
• Payload information field: 0 to
(65535 - X) bytes, where X is the
length of payload header and payload
FCS;
• Payload Frame Check Sequence (FCS):
optional (indicated by PFI); 4 bytes;
CRC-32 to protect payload
information field
192
GFP's location in protocol stack
Ethernet
IP/PPP
Other client signals
GFP-Client specific aspects
(payload-dependent)
GFP-Common aspects
(payload-independent)
SONET/SDH path
OTN OCh path
193
Main features of the
GFP protocol revisited
• Common aspects:
– HEC + Length based delineation
• Core header has payload length and HEC
– Error control: error detection
• Payload type HEC, payload Frame Check Sequence (CRC-32)
– Multiplexing: linear and ring extension headers
– Idle frames are sent to maintain synchronization as in
HDLC
Scrambling as in ATM:
• core header + payload scrambling
– Client management - client fail signal
• Client-dependent aspects:
– Client-specific encapsulation techniques
page 68 of reference
194
Need for scrambling
• Line coding used in SONET/SDH and OTN optical
communication links is NRZ (Non-Return to Zero)
– Laser is turned ON if bit is 1, and OFF if bit is 0
• Advantages of NRZ: simplicity and bandwidthefficiency
• Disadvantage: loss of synchronization possible at
the receiver by the clock and data recovery
circuits if there are many consecutive 0 bits in the
data stream
– could be caused by a malicious user sending such a
payload
195
page 92 of reference
Scrambling solution
• Self-synchronous payload scrambler
– Use a polynomial of x43+1: XOR bit with scrambler output bit
that preceeded it by 43 bits
– Drawback: error multiplication
Data
in
Data
out
+
Dn
…
D2
Data
in
+
D1
D1
D2
…
Data
out
Dn
xn + 1 descrambler
xn + 1 scrambler
• Solution to error multiplication
– Select a CRC generator polynomial with triple error detection
capability and have no common factor with scrambler
x16 x15 x12 x10 x 4 x3 x 2 x 1
page 93 of reference
196
GFP client-based aspects
• Frame-mapped GFP (GFP-F)
– 1-to-1 mapping: one client frame is mapped into
one GFP frame
– Applicable to most packet data types, e.g.,
Ethernet MAC frames, IP packets
• Transparent-mapped GFP (GFP-T)
– Many-to-1 mapping: a fixed # of client
characters are mapped into a GFP frame of
predetermined length
– Applicable to 8B/10B block-coded client signals
such as fiber channel, GbE (1Gb/s Ethernet)
197
Page 65 of reference
GFP-F frame
PLI
cHEC
2 bytes 2 bytes
GFP
header
Payload
header
4 bytes
Client PDU
(PPP, IP, Ethernet, RPR, etc)
0-65,531 bytes
GFP
payload
FCS
(optional)
4 bytes
GFP
FCS
198
GFP-T frame
PLI
cHEC
2 bytes 2 bytes
Payload
header
#1
8x64B/65B + 16
superblock bits
#N
4 bytes
FCS
(optional)
4 bytes
GFP
header
GFP
payload
0 CCL#n CCI
DCI #1
…
LCC: last control character
CCI: control code indicator
1 CCL#1 CCI
…
…
64B/65B #1
64B/65B #2
8 64/65 B block
67 bytes (minus flag)
superblock
64B/65B #7
64B/65B #8
1 bytes flag F1 … F8
2 bytes
CRC-16
LCC
GFP
FCS
n control
codeword
8 8-byte
block
8-n data
codeword
DCI #(8-n)
CCL: control code locator 199
DCI: data character identifier
GFP-T encoding steps
1.
2.
3.
4.
5.
6.
Decode 8B/10B code words into original 8-bit values
Map the eight decoded 8B/10B characters into a 64B/65B
block code and set a flag bit to indicate if the block
contains only data characters (DCI)
Create a superblock
1.
2.
3.
Group 8 64B/65B blocks
Rearrange leading bits at end
Generate and append CRC-16 check bits to form a superblock
–
N: minimum # of superblocks per GFP frame (e.g., 95 for GbE)
Repeat creating at least N such superblocks
Prepend with GFP core and payload headers
Scramble payload header and payload with x43+1
200
Comparing performance of
GFP-F & GFP-T
• GFP-F
– Efficient bandwidth utilization:
• only delivers client data frames (idle frames are
removed)
• if client signal is lightly loaded, GFP-F can map this
signal to a lower-rate circuit or GFP multiplex with
other signals
– Higher latency: associated with buffering an
entire client data frame at the ingress to the
GFP mapper
201
Pages 89, 101 of reference
Comparing performance of
GFP-F & GFP-T
• GFP-T
– Advantage: transparent transport of 8B/10B
control characters as well as data characters
• minimum protocol awareness
• a single hardware implementation can handle many
types of client signals (all that use 8B/10B coding)
– Lower bandwidth utilization: if client signal
contains idle frames, these are transported
through transparently
– Lower latency: only a few bytes of
mapper/demapper latency
202
Pages 89, 101 of reference
Virtual Concatenation (VCAT)
• Allows for SONET/SDH rates in-between the
rigid rates of the original hierarchy
• VT1.5-7v: means 7 virtually concatenated VT1.5 signals
• VCAT as an inverse multiplexing scheme
– It allows for individual components of the virtually
concatenated signal to be routed along different paths
before recombining them into a contiguous-bandwidth
signal at the far endpoint
– Need to compensate for delays differences on the
various paths used for the individual components
• Bandwidth partitioning
– It allows for a SONET/SDH link to be partitioned into
arbitrary units of bandwidth
203
Pages 74, 107 of reference
VCAT increased bandwidth
efficiency
Data signal
SONET/SDH payload mapping
and bandwidth efficiency
SONET/SDH with VCAT
payload mapping and bandwidth
efficiency
Ethernet
(10 Mb/s)
STS-1/VC-3 – 21%
VT1.5-7v/VC-11-7v – 89%
Fast Ethernet
(100 Mb/s)
STS-3c/VC-4 – 67%
VT1.5-64v/VC-11-64v – 98%
Gigabit Ethernet
(1000 Mb/s)
STS-48c/VC-4-16c – 42%
STS-3c-7v/VC-4-7v –95%
STS-1-21v/VC-3-21V –98%
204
Page 75 of reference
Inverse multiplexing in VCAT
Implementation of VCAT is only required at
select nodes (i.e., the edge nodes); not all
multiplexers need to support VCAT
Page 82 of reference
205
Bandwidth partitioning with VCAT
206
Page 82 of reference
Link Capacity Adjustment Scheme
(LCAS)
• LCAS is a mechanism to allow for automatic
bandwidth tuning of a virtually
concatenated signal
– The VCAT group of circuits should already be
established using a
• centralized NMS/EMS based procedure, or
• by a distributed RSVP-TE based procedure
• Note that bandwidth cannot be increased
beyond the aggregate value of the VCAT
signal without a GMPLS RSVP or NMS/EMS
procedure of circuit setup
207
Interaction between GMPLS
RSVP and LCAS
208
Page 77 of reference
Link Capacity Adjustment Scheme
(LCAS)
• LCAS is basically a synchronization procedure between the
two ends of a VCAT signal
– Unlike GMPLS RSVP, it is NOT a bandwidth reservation and
circuit setup or release procedure
• LCAS procedures (triggered by GMPLS or NMS/EMS):
– add or remove a member of a VCAT group
– renumber the members in a VCAT group
• Messages are exchanged between the originating and
terminating SONET/SDH nodes to execute these LCAS
procedures
– Add member (ChID, GID)
– Remove member (ChID, GID)
– Member status
• Messages are sent in the H4 byte for high-order VCAT
209
Hitless change
• Hitless capacity adjustment
– Without causing an errors during the process
– "Two ends of the link must agree precisely when the
VCAT group transitions to a new payload in which new
members have been added or some previous members
removed"
– "Needs hardware-level synchronization as to when the
SONET/SDH mappers should begin/stop
inserting/extracting a payload from a VCAT group
member"
• The link capacity adjustment does not impact user
traffic flow (what if that is the bottleneck link
for a TCP session?)
210
Pages 75 and 82 of reference
Applications of LCAS
• Adjusting bandwidth requirements on a time-ofday basis
– A GbE signal may only require on average a 200-300Mbps
SONET circuit
– Establish an STS-1-7v (388.688Mbps) VCAT circuit
– Then add/delete members as load increases or decreases
– Need buffering and PAUSE signals to handle bursts
– Can map two different GbE signals to one VCAT group
with different sets of members?
• Rerouting of traffic after failures
211
Data over SONET/SDH (DoS)
• Using GFP, VCAT, & LCAS, DoS provides a
set of mechanisms for efficient transport
of data packets on SONET/SDH circuits
– GFP: an efficient and standard data link layer
protocol
– VCAT: flexible bandwidth assignment scheme
requiring no modification to intermediate nodes
– LCAS: dynamic bandwidth adjustment of VCAT
signal
212
Technologies
• Connection-oriented (CO) networks
– Data-(user-) plane protocols
• packet-switched: MPLS, VLAN Ethernet, Intserv IP
• circuit-switched: SONET/SDH, WDM, SDM
– Control-plane protocols:
• RSVP-TE
• OSPF-TE
• LMP
• Internetworking
– GFP, VCAT, LCAS for SONET/SDH
PWE3 for MPLS networks
– Digital wrapper for OTN
213
Pseudo Wire Emulation
• Pseudo Wire Emulation Edge-to-Edge
(PWE3) is a mechanism for emulating
certain services across a packet-switched
network:
– Services: Frame-relay, ATM, Ethernet, TDM
services, such as SONET/SDH
– Packet-switched network:
• IP
• MPLS
Example of a PWE3 service:
Ethernet over MPLS
Ethernet
Ethernet
Tunnel
MPLS network
Customer
Edge (CE)
Provider
Edge (PE)
PE
Tunnel label
PW label
PW control word
Ethernet frame
CE
• PW control word:
– status
– sequencing
– timing - Real-time transport protocol
(RTP)
• PW label and tunnel label:
– MPLS label, L2TP session id, UDP port
number
Andy Malis paper in IEEE Comm. Mag., Sept. 2006
Ethernet over MPLS
PW
Eth
MPLS
Eth
Eth
Eth
IP
...
IP
IP
...
Example: NY to Chicago link is a point-to-point Ethernet link
● LSP encoding: Ethernet
● Switching type: PSC
● GPID: Ethernet
......
Digital wrapper
• ITU-T G. 709 provides a method to
carry Ethernet frames, ATM cells, IP
datagrams directly on a WDM
lightpath
217
Outline
• Principles
– Different types of connection-oriented
networks
• Technologies
– Single network
– Internetworking
Usage
– Commercial networks
– Research & Education Networks (REN)
218
Commercial uses
• Semi-permanent MPLS virtual circuits
– Traffic engineering
– Voice over IP
• QoS concerns: telephony has a 150ms oneway delay requirement (with echo cancellers)
– Business or service provider interconnect
• interconnecting geographically distributed
campuses of an enterprise
• interconnecting wide-area routers of an ISP
service provider
219
Traffic engineering (TE)
• Since BGP and OSPF routing protocols mainly
spread reachability information, routing tables are
such that some links become heavily congested
while others are lightly loaded
• MPLS virtual circuits are used to alleviate this
problem
– e.g., NY to SF traffic could be directed to take an MPLS
virtual circuit on a lightly loaded route avoiding all paths
on which more local traffic may compete
• This is an application of MPLS VCs without
bandwidth allocation
220
Goals of Traffic Engineering (TE)
• Monitor network resources and control traffic to
maximize performance objectives
– Goal of TE is to achieve efficient network operation with
optimized resource utilization in an Autonomous System
• Goals of TE can be:
– Traffic oriented
• Enhance the QoS of traffic streams
• Minimization of loss and delay
• Maximization of throughput
– Resource oriented
• Load balancing
• Minimize maximum congestion or minimize maximum
resource utilization
• Output – decreased packet loss and delay, increased
throughput
221
Business or service provider
interconnect
• Multiple options:
– TDM circuits (traditional private line,
T1, T3, OC3, OC12, etc.)
– Ethernet private line
• point-to-point (PWE3)
• VPNs (called Virtual private LAN service)
– MPLS VPNs
– WDM lightpaths
– Dark fiber
222
First option: buy OC192
between routers
Example: Internet2 purchased OC192s from Qwest
SONET
switch
IP router
SF PoP
DC PoP
OC192
OC192
Houston PoP
223
Second option: buy Ethernet
point-to-point private lines
Example: NLR Framenet service; also Pacificwave
Ethernet
switch
10GbE
IP router
SF PoP
10GbE
DC PoP
Point-to-point Ethernet
private lines
Houston PoP
224
Third option: buy multipoint
Ethernet VPN
VPLS: Virtual Private LAN service: an Ethernet
private LAN created over a wide-area network
Ethernet
switch
10GbE
IP router
SF PoP
10GbE
DC PoP
Multippoint Ethernet
VLAN (VPN)
Houston PoP
Can place all three ports in one VLAN
225
Dynamic circuits/VCs
(GMPLS control-plane)
• Commercial:
– fast restoration
• circuit/VC setup delay significant
– rapid provisioning
• similar to scheduled (book-ahead
reservations) of REN (research & education
networks)
226
Industry usage of dynamic capability of
GMPLS control-plane protocols
• Highly limited
• OIF interoperability testing focused on routers
sending SONET setup messages to SONET
switches
– OIF UNI 1.0R2 and ENNI support only SONET circuits
• In 2005:
– UNI 2.0 testing: to support GbE interfaces
– But signaling/routing support for GbE-SONET-GbE
circuits includes proprietary INNI solutions and no
ENNI solution
– GbE-SONET hybrid circuits important for REN
applications
227
Compare "wire" services
• Disadvantages of Ethernet based solutions:
– Spanning tree:
• convergence slow
• 7-hop limit
– Flat addressing:
• no summarization of MAC addresses
– VLAN tag:
• only 12 bits (only 4096 LANs)
• No VLAN ID swapping (unlike MPLS labels)
– contiguous requirement like lambdas in a WDM network
– Few diagnostic tools to trace problems
228
Andy Malis paper in IEEE Comm. Mag., Sept. 2006
Compare "wire" services
• WDM networks:
– Low power consumption
• SONET/SDH networks:
– Good error monitoring features
– Higher-rate interfaces are cheaper than
on IP routers
229
Research & Education
(G)MPLS networks
•
•
•
•
•
•
NSF-funded CHEETAH
NSF-funded DRAGON
DOE's Ultra Science Network (USN)
DOE's ESnet - Science Data Network
Next-generation Internet2
etc.
230
CHEETAH network - data plane links
GbEthernet and SONET
UVa
TN PoP
SN16000
CUNY
GbE
GbE
OC192 Control GbE/
10GbE
card
card
card
NCSU
End hosts
GbEs
GbE
OC-192
NC PoP
GA PoP
SN16000
End
GbE GbE/
Control OC192
10GbE card
hosts
cards
card
ORNL
GbE
SN16000
OC192 Control GbE/ GbE
10GbE
card
card
End
card
OC-192
hosts
GbE
231
Sycamore SN16000
SONET switch with GbE/10GbE interfaces
GaTech
CHEETAH network - control plane links
Design goal: scalable GMPLS network
SN16000
OC192 Control GbE/
10GbE
card
card
card
TN
UVa
Openswan
IPsec software
on Linux end hosts
CUNY
NCSU
End hosts
ns5
IPsec device
Call setup
messages
ns5
GA
End hosts
GbE/ Control
OC192
10GbE card
card
card
SN16000
ORNL
Internet2
ns5
OC192 Control GbE/
10GbE
card
card
card
NC
End
hosts
SN16000
232
GaTech
Networking software
• Sycamore switch comes with built-in GMPLS
control-plane protocols:
– RSVP-TE and OSPF-TE
• We developed CHEETAH software for Linux
end hosts:
– circuit-requestor
• allows users and applications to issue RSVP-TE
call setup and release messages asking for
dedicated circuits to remote end hosts
– CircuitTCP (CTCP) code
233
Network service
• On-demand circuit-switched service for 1Gb/s
dedicated host-to-host circuits
• Call setup delay: 1.5sec
– Sycamore implemented a proprietary build for hybrid
GbE-SONET-GbE circuits
– No standard yet for such hybrid circuits
– Sets up 7 STS-3c and VCATs them to carry a GbE signal
• In contrast, their GMPLS standards
implementation for pure-SONET circuits incurs a
call setup delay of 166ms (2-hop)
234
Applications
• eScience: Terascale Supernova Initiative
– File transfers
– Ensight remote visualization
• general-purpose:
– file transfers between CDN servers, web mirrors
– web caching
– video applications
235
Interesting design considerations
in the CHEETAH project
• Addressing: assignment of IP addresses to
the end host and switches in the network
• Enabling OSPF-TE automatic neighbor
discovery
• Security
236
Addressing
• Public vs. private? static vs. dynamic?
– Shortage of IPv4 addresses
– Enterprises often use private and/or dynamic IP
addresses (NAT, DHCP, etc)
– We assign static public IP addresses for both data-plane
and control-plane IP addresses, why?
• Data-plane
– Static: an end hosts need to be “called” by other hosts
– Public: the address need to be globally unique (Private IP
addresses sufficient if goal for CHEETAH is to create a small
eScience network)
• Control-plane
– Static: the control-plane IP addresses are configured in local
Traffic-Engineering link configuration
– Public: same global uniqueness reason for border switches
237
Address assignment example
Internet
198.124.42.20
zelda4
Data-plane address
198.123.28.172
128.109.34.20
Ethernet control port:
198.124.42.2
Ethernet control port:
130.207.252.2
Ethernet control port:
128.109.34.2
(routerID/switchIP:
198.124.43.2)
(routerID/switchIP:
130.207.253.2)
(routerID/switchIP:
128.109.35.2)
wukong
Data-plane address
152.48.249.102
TN SN16000
Control-plane links
130.207.252.20
Data-plane links
GA SN16000
NC SN16000
Unnumbered
Data-plane
Interface
ID 86000001
Data-plane address
152.48.249.2
Unnumbered
Data-plane
Interface
ID 85000002
zelda1
238
zelda1, zelda4, wukong: hosts
Impact of this addressing
• After dedicated circuit is setup:
– far end NIC has an IP address from a different subnet
• e.g.: zelda4 and wukong in the address assignment example
– Default setting of IP routing table entries will indicate
that such an address is only reachable through the
default gateway
• Our solution:
– Automatically update the routing table and ARP table
when circuit is set up as part of signaling code
• comparable to switch fabric programming in the switch
• ARP table is also automatically updated to avoid extra
round-trip propagation delay and potential broadcast storms
caused by ARP
• But how does the host find the remote MAC address?
239
Using DNS TXT
resource record
• Add a TXT record for the DNS entry of each CHEETAH end
host in the local DNS server
– Indicate that the host is in the CHEETAH network
– Record the MAC address of the host’s second NIC
• During circuit setup
– The two CHEETAH hosts execute DNS lookup to retrieve the
remote MAC address
– At the end of a CHEETAH circuit setup, the two CHEETAH
hosts
• Add a host-specific entry for the far-end second NIC’s IP address
into the IP routing table,
• Add an entry into the ARP table to map the far-end second NIC’s IP
address to its MAC address.
– When the CHEETAH circuit is released, these entries are
removed.
240
Enabling OSPF-TE automatic
neighbor discovery
• Automatic neighbor discovery of OSPF-TE
– Based on “Hello” messages
– Hello messages will not be forwarded by IP
routers
– If two switches are data-plane neighbors, we
need to ensure they are control-plane neighbors
as well
• Solution:
– IP-in-IP tunnels
• Outer datagram header carries the Ethernet control
port IP addresses
• Inner datagram header carries the Router ID and the
broadcast IP address as source and destination
241
Control-plane security
• Importance: a malicious user could tie up circuits
• Cannot use SSH, SSL, etc., because RSVP-TE and OSPF-TE
use raw IP
• Our solution – IPsec tunnels
– Use external security device (Juniper NS-5XT) for switches
– Use open-source software (openswan) on Linux end hosts
– Establish IPsec tunnels between adjacent switches and end
hosts
• Firewalls
– recall our static public IP address assignments
– Use Juniper NS-5XT for switches and iptables for Linux hosts
• Limitation: host-based instead of user-based
– Any user of the end host can request circuits after IPsec tunnel
is established
– Future plan: use the RSVP-TE INTEGRITY object
242
CHEETAH architecture
End Host
CHEETAH
software
Internet
DNS client
RSVP-TE module
Application
DNS client
SONET circuitswitched network
RSVP-TE module
TCP/IP
C-TCP/IP
End Host
CHEETAH
software
Application
TCP/IP
NIC 1
NIC 2
Circuit
Gateway
Circuit
Gateway
NIC 1
NIC 2
C-TCP/IP
243
CHEETAH end-host software
DNS
server
CHEETAH software
End host
CHEETAH daemon (CD)
Circuit-requestor
DNS client
socket
C-TCP API
Route/ARP
table update
• RSVPD
– CAC for UNI link
– Date-plane configuration
socket
User space
DNS lookup – to support
our scalability goal
Circuit-request setup
– Message parsing
RSVPD API
RSVP-TE Daemon
(RSVPD)
Kernel space
DNS lookup
•
CAC
CD API
•
RSVP-TE
messages
• Routing/ARP table
update
– Message construction
• RSVPD
C-TCP
Integrate CD API into web servers, FTP servers, etc., so that "elephant" flows
are automatically handled via a dynamically created dedicated circuit/VC
244
End-to-end signaling delay
measurements
•
Signaling delays incurred in setting up a circuit between zelda1 (in Atlanta,
GA) and wuneng (in Raleigh, NC) across the CHEETAH network.
Circuit type
End-tend circuit
setup delay (s)
Processing delay for
Path message at
the NC SN16000 (s)
Processing delay for
Resv message at
the NC SN16000 (s)
OC-1
0.166103
0.091119
0.008689
OC-3
0.165450
0.090852
0.008650
1Gb/s EoS
1.645673
1.566932
0.008697
Round-trip signaling message propagation plus emission delay between GA SN16000 and NC SN16000:
0.025s
•
Observations:
–
–
–
Delays for setting up SONET circuits for rates in the original SONET hierarchy
are very small (166ms)
Delays for other rates are much higher (1.6s) (vendor implementation)
Signaling message processing delay dominate the end-to-end circuit setup delay
245
Other R&E networks
• DRAGON:
– GbE and WDM (Movaz)
– VLSR code: external implementation of RSVP-TE and
OSPF-TE: popular
– per-domain route computation unit called NARB
• ESnet and Science data network
– OSCARS: an advance-reservation system
– MPLS network
• UltraScience Network
– Research network for DoE labs
– GbE and SONET (Ciena)
– Centralized scheduler for advance-reservation calls
246
How advance-reservation
systems work?
2: A new protocol (BW requested + time)
4. Answer
Advance-reservations
Scheduler
scheduler
5. Third-party Path message with ERO
(just before scheduled time)
1. Maintains bandwidth
availability over a time
horizon for all links in the
domain
3. When request for an advance reservation
arrives, try different routes and find one with
required bandwidth (centralized CAC)
7. Path message
6. Program switch fabric
GMPLSequipped
switch
GMPLSequipped
switch
GMPLS RSVP-TE signaling
used for "rapid provisioning"
GMPLSequipped
switch
247
Advantages of GMPLS
control-plane sacrificed
• RSVP-TE engines at switch controllers are
supposed to manage bandwidth for the interfaces
of the switch
– distributed bandwidth management
• Route computations are supposed to be
distributed to each switch
– distributed routing protocols
• Both these steps are centralized in a domain
scheduler because RSVP-TE and OSPF-TE do not
support parameters for advance-reservation calls
248
Wide-area REN
• HOPI (Hybrid Optical Packet
Infrastructure)
– Uses Ethernet switches to provide VLAN
based virtual circuit service
– Uses VLSRs and NARB for control-plane
• Next-generation Internet2
– Will offer a dynamic circuit service
– Wide-scale deployment of Ciena SONET
switches
249
PROVISIONAL TOPOLOGY
Courtesy: Rick Summerhill, Internet2 web site
250
PROVISIONAL TOPOLOGY
Courtesy: Rick Summerhill, Internet2 web site
251
References for REN projects
• IEEE Communication Magazine special
issue, March 2006
– DRAGON, USN, CHEETAH, several
other projects
• CHEETAH web site:
– http://www.ece.virginia.edu/cheetah/
– Papers in Opticomm 2003, IEEE JSAC
Oct. 2004, IEEE ICC 2006, IEEE
Globecom 2006, etc.
252
Summary
• Principles
– Different types of connection-oriented
networks
• Technologies
– Single network: MPLS, SONET, OTN
– Internetworking: GFP, PWE3, G.709
• Usage
– Commercial networks
– Research & Education Networks (REN)
253