Transcript Satisfying Applications Requirements

Satisfying the Requirements of Applications
on a Single Packet Network
Yoram Ofek
Synchrodyne Networks, Inc.
E-mail: [email protected]
Phone: (917) 601-7180
May 2002
© 2002 Yoram Ofek
1
Applications - Generic Traffic Types
Person-to-Person
Communications
Typically with Rate
Single
Packet
Network
Machine-to-Machine
Communications
Typically No Rate
May 2002
© 2002 Yoram Ofek
2
Person-to-Person: with Rate

Applications with some notion of rate:

Most demanding: interactive - streaming media - voice/video
 end-to-end delay < 100 ms
 continuous play - i.e., periodic

Will satisfy also:
non-interactive: playback, large file transfers - Machine-to-Person
 The
transition from circuit to packet switching the rate
per person will increase 3-4 orders of magnitude:

from 104 b/s to 108 b/s
May 2002
© 2002 Yoram Ofek
3
Machine-to-Machine: No Rate

(Computing) Machines are still evolving rapidly


e.g., capabilities: “Moore’s Law” - new applications
General characteristic: bursty - unpredictable in time/space

All bits should be transferred correctly with no “shaping”:
 max. throughput (burst) AND min. delay & loss

e.g., distributed/parallel computing, data processing
Traffic shape
at the source
No
“Shaping”
t
Transfer with
Minimum Distortions
May 2002
© 2002 Yoram Ofek
Traffic shape
at the Destination
t
t
4
Outline

How to support the two generic traffic types:
Machine-to-Machine
 1. Ring networks
Person-to-Person
 2.
Convergence routing
 3.
Time-driven - switched networks
 4.
Dynamic optical networking
Machine-to-Machine
Person-to-Person
Integration of Machine-to-Machine using UTC
Person-to-Person
Integration of Machine-to-Machine using UTC
May 2002
© 2002 Yoram Ofek
5
Rings

First token ring was introduced (e.g., IBM, FDDI)
 Why token rings?

Can support:


May 2002
Machine-to-Machine
1) Bursty data (asynchronous) with
 no rate, (no) loss, (low) latency, fairness, multicast
2) Periodic real-time
Person-to-Person
 with rate and delay guarantees, multicast
© 2002 Yoram Ofek
6
Rings with Spatial Bandwidth Reuse

Packet are removed at destinations:
slotted or insertion ring


Concurrent transmission
Throughput grows with locality

all nodes can transmit
simultaneously
to their neighbors
1
12
11
3
10
4
9
5
8
7
May 2002
© 2002 Yoram Ofek
2
6
7
MetaRing: Fairness with Spatial Bandwidth Reuse



SAT (token) gives predefined transmission quota
Rotates in the opposite direction
Held intermittently if the node is not SATisfied
SAT
IB - Insertion Buffer
Node 1
Node 2
IB
IB
Node 3
IB
IB
May 2002
Node 6
Slotted or
insertion
ring
Node 4
© 2002 Yoram Ofek
Node 5
8
MetaRing: SAT Fairness Properties

Equal throughput after each SAT rotation - with multiple variants



SAT signal provides for:



Multiple SATs operations for simple fault recovery
SAT/SAT’ for graceful degradation to (multi) bus operation
Bounded delay with no loss of bursty data - Machine-to-Machine
Integration of real-time traffic with known rate - Person-to-Person
MetaRing is the underlying network for IBM storage area
network (SAN) products (also ANSI SSA - X3T10 standard)
Multi-billion business for IBM
Spatial reuse rings are currently very active:
Cisco SRP/DPT and IEEE 802.17
May 2002
© 2002 Yoram Ofek
9
Switched Network

Is MetaRing panacea? NO
May 2002
© 2002 Yoram Ofek
10
Traffic with No Rate
over Switched Network

To transfer with max. throughput (burst) AND min. delay and loss
Traffic shape
at the source
No
“Shaping”
t
Transfer with
Minimum Distortions
Traffic shape
at the Destination
t
t


TCP/IP: unstable/unpredictable throughput/delay/loss
Cannot be done with over fixed routes (congestion and loss)
 Dynamic routing:

May 2002
e.g., “Hot-Potato” (P. Baran),
Manhattan Street Network - deflection routing (N. Maxemchuk)
© 2002 Yoram Ofek
11
MetaNet Convergence Routing
with Sense of Direction


Invented by Yoram Ofek and Moti Yung
Virtual ring embedding
VN1
 Link types:



Sequential Numbering
of Virtual Nodes:
VN0, VN1, VN2, …
VN0
G
A
Ring - part of virtual ring/s
Thread - all other links
Embeddings methods - e.g.,:
 Simple Hamiltonian Circuit
 Euler tree traversal
VN2
B
VN6
I
VN8
E
Multiple partial virtual rings
VN7
May 2002
C
D
VN3

VN15
F
© 2002 Yoram Ofek
H
VN14
VN9
12
MetaNet Convergence Routing
over Switched Network

Packet routing paradigm:
 1. Packets are forwarded to idle output link
“closer” to their destinations with:
“sense of direction” - along virtual ring(s)
 2. Virtual (buffer insertion) ring traffic gets
priority to continue on the virtual ring links
May 2002
© 2002 Yoram Ofek
13
MetaNet Convergence Routing
over Switched Network

SHORT-CUT Routing:
 Example: packet arrives
to VN6 on node C with
destination H, can shortcut to VN8
 Diametric routing in
light load
VN0
VN1
G
A
F
VN2
B
VN6
C
D
I
VN3
VN8
E
Short-cut
May 2002
VN7
© 2002 Yoram Ofek
VN15
H
VN14
VN9
14
MetaNet Convergence Routing
over Switched Network

Broadcast-with-feedback:

Requirements:



asynchronous - without arbitration
losslessness
correctness




complete coverage
packet copied only once
complete feedback to the source
When short-cuts or jumps
are possible the packets are
DUPLICATED
May 2002
VN0
VN1
G
A
F
VN2
VN15
B
C
D
I
VN3
© 2002 Yoram Ofek
E
VN7
H
VN14
VN9
15
MetaNet Convergence Routing
over Switched Network

Summary:
 Support traffic from bursty sources with no rates:
No packet loss
Machine-to-Machine
 Bounded delay
Person-to-Person
 Fairness
 Broadcast and multicast (with feedback)

However, still limitations:
1) on size - it is not a global network!
2) does not support person-to-person
communications with known rates
May 2002
© 2002 Yoram Ofek
16
Outline

How to support the two generic traffic types:
Machine-to-Machine
 1. Ring networks
Person-to-Person
 2.
Convergence routing
 3.
Time-driven - switched networks
 4.
Dynamic optical networking
Machine-to-Machine
Person-to-Person
Integration of Machine-to-Machine using UTC
Person-to-Person
Integration of Machine-to-Machine using UTC
May 2002
© 2002 Yoram Ofek
17
Time-Driven Priority
over Switched Network

How to support communications with known rate on a
Person-to-Person
global network?

Flow (congestion) control methods:



Rate control at the network’s boundaries - e.g., ATM (J. Turner)
 with statistical multiplexing inside the network
Inside the network with local clocks scheduling deadline scheduling (D. Ferari), GPS (A. Parekh, R. Gallager)
Inside the network with scheduling based on global time:

UTC - Coordinated Universal Time:
TIME-DRIVEN PRIORITY
 Based on pipeline forwarding
May 2002
© 2002 Yoram Ofek
18
Pipeline: From Henry Ford to the Internet
Pipeline: optimal method - independent of a specific realization successfully deployed with optimal efficiency in
 Factory (automotive), Computers (CPU)
NOW pipeline in global networks! Thanks to GPS that provides UTC
Time
Driven
Priority
Super-cycle - UTC second
with 80k Time-frames
Time
Cycle0
Tf
12
Time
Cycle1
Tf
1000 1 2
Time
Cycle 79
Tf
Tf
Tf
1000
12
1000
Time-of-Day or UTC
0
1
beginning
of a UTC second
beginning
of a UTC second
•Time-of-day or UTC – coordinated universal time - with accuracy of 5 s
May 2002
© 2002 Yoram Ofek
19
Time-driven Priority - Forwarding
1. Immediate forwarding
2. 2-frame forwarding
3. Arbitrary forwarding
Arrive to
Output
Port 1
Scheme
h - # of hops
Blocking
Probability
Small p
(q=1-p)
Immediate
(1-qh)k
hkpk+ O(pk+1
)
hpk+ O(pk+1)
2-frame
Arbitrary-frame
Time Cycle
2
i
1-(1-pk)h
hpk+ O(p2k)
Time Cycle
48 1 2
i
48
t
i
48
t
Arbitrary
2-frame
Forward from Immediate
Output
Port 1 2
i i+1
48 1 2
i+2
Time Cycle
May 2002
Time Cycle
© 2002 Yoram Ofek
20
Time-driven Priority
for Videoconferencing

Sender-receiver
synchronization
Complex
Periodicity
Scheduling: The size of successive
Frame
packets of Video
the same
flow
changes
in a repetitive manner
UTC
from GPS
MPEG
I picture
Sender
Capture
MPEG
I picture
MPEG
I picture
Videoconferencing
Node B
MPEG
P pictures
Node C
MPEG
P pictures
MPEG
P pictures
Receiver
Video Frame
t realDisplay
Time driven priority
videoconferencing with complex periodicity scheduling
Face-to-face quality
Scale the globe
May 2002
© 2002 Yoram Ofek
21
Time-driven Priority - Summary


IP and “Best Effort” service are unchanged
Time-driven priority scales the globe:
 Jitter: bounded by 2*Tf :

Independent of the network size, traffic load, flow rate
 End-to-end
delay: 2* h*Tf + prop. Delay
 No


loss
Person-to-Person
Can easily integrated with:
Machine-to-Machine
 MetaNet convergence routing
Optimized for interactive streaming media
May 2002
© 2002 Yoram Ofek
22
Fractional  Switching
for Dynamic Optical Networking

Objective: to utilize UTC in the optical domain

In static optical networking all data units on the optical
channel are switched in the same way
while,

In dynamic optical networking each data unit on the
optical channel may be switched differently
May 2002
© 2002 Yoram Ofek
23
Problems of Static  Switching: N 2 ’s
SEA
STL
NYC
5 s
SF
LA
May 2002
© 2002 Yoram Ofek
24
What: Fractional  Switching
Save s & Grooming & Small or No Memory
SEA
1   5 Fractional  Pipes (FPs)
STL
NYC
SF
Number of s =
Aggregate capacity needed
10 Gb/s
LA
May 2002
© 2002 Yoram Ofek
25
Time-based Grooming and Degrooming
Header processing only at the edges
Server Farm
(web, VoD)
Wireless Base
Station
Small 
fractions
ADSL DSLAM
(central office)
IP
 Switching
Large  fractions
IP/MPLS
May 2002
© 2002 Yoram Ofek
Small 
fractions
Edge/Access
Router (POP)
Cable Modem
Head-end
26
Dynamic: Fractional  Switching
 Pipeline
forwarding of whole time frames
No header processing
 Banyan based switch structure - optimal

Super-cycle - UTC second
with 80k Time-frames
Time
Cycle0
Tf
12
Time
Cycle1
Tf
1000 1 2
See pipeline forwarding - PF
animation over FlPs
Time
Cycle 79
Tf
Tf
Tf
1000
12
1000
Time-of-Day or UTC
0
1
beginning
of a UTC second
beginning
of a UTC second
May 2002
© 2002 Yoram Ofek
27
Why: Dynamic: Fractional  Switching
The Optical Links are Memory



A mesh of linear delay lines
How to preserve pipeline forwarding?
Delay between switches =
integer number of time frame
May 2002
© 2002 Yoram Ofek
UTC
28
The Optical Links are the Memory
Time-of-Day
or UTC
Input 1
Idle time:
Safety margin
between two
time frames
Switch Controller
Output 1
Optical
Alignment
Optical
Switching
Fabric
Input N
Idle time:
Safety margin
between two
time frames
Output N
Optical
Alignment
Tf
t+2
Tf
t+1
Tf
t
t-1
Tf
t-2
t-3
Time-of-Day or UTC
Tf : Time frame
: Time frame payload – with a predefined number of data units
May 2002
© 2002 Yoram Ofek
29
Low Complexity Switching Fabric
Optimal Speedup of 1
Switching elements
For N=256, a=4
For N=1024, a=4
Multistage
a*N*lgaN
4K
20K
Scalability
Crossbar
N2
64K
(factor of 16)
1,000K (factor of 50)
Blocking
Multiple time frames  low blocking probability
DWDM  many parallel routes  low blocking probability
May 2002
© 2002 Yoram Ofek
31
Blocking Probability
Four Channels per Link
80%
Blocking Probability [% ]
70%
60%
50%
40%
30%
20%
10%
0%
50%
55%
60%
65%
70%
75%
80%
85%
90%
95%
100%
Average Utilization [% ]
May 2002
1 TF
4 TFs
TFsYoram 32
TFs
©16
2002
Ofek
64 TFs
1000 TFs
32
Scheduling and Switching
with UTC Alignment
Periodic
Schedule
on Switch i
Periodic
Schedule
on Switch j
Schedule s
TF1
TF1
TF8
TF8
TF7
TF3
TF6
TF2
TF7
TF2
TF3
TF4
TF4
TF5
TF5
Always aligned with a bounded error (typically < 1 second)
Thus, delay (memory)
May 2002
© 2002 Yoramper
Ofek switch = 1 TF
33
Scheduling and Switching without UTC Alignment
Circuit Switching, e.g., SONET
Periodic
Schedule
on Switch i
Schedule s
Periodic
Schedule
on Switch j
No alignment
Thus, delay (memory) per switch = 1 Time Cycle
May 2002
© 2002 Yoram Ofek
34
Service Interfaces
IP/MPLS
OC-12/OC-48
UTC
FP 1
Network
Processor
(MPLS)
Port
FP 2
FP i
MPLS Packets
See Animation
SONET STS-1 frames
SONET
OC-12/OC-48
UTC
FP 1
SONET
DMUX
(STS-1)
Port
May 2002
© 2002 Yoram Ofek
FP 2
FP i
35
Conclusion
Person-to-Person
Typically with Rate
Fractional  Switching
Time-driven Priority
Single
Network
MetaNet Convergence
Routing
Machine-to-Machine
Typically No Rate
May 2002
© 2002 Yoram Ofek
36