Transcript Real-Time Database

Real-Time
Communication
In embedded systems…
 Data flows :
• from the sensors and control panels to the
central cluster of processors
• between processors in the central cluster
• from processors to the actuators and output
displays
 Communication overhead adds to the
computer response time
Sistem Waktu Nyata (CS4613)
In hard & soft RTS…
 Hard: use communication protocols that
allow the communication overhead to be
bounded
 Soft: (exp: MulMed & video conf.)
• excessive delays in message delivery can
significantly degrade the quality of service
• occasional failure to meet message-delivery is
not fatal
Sistem Waktu Nyata (CS4613)
Comm. key performance
 Traditional  system throughput
• How much data can be transferred over the
network in one unit time from source to
destination
 RTS  probability of delivering a message
by a certain deadline
• Lost message = infinite delivery time
• Measures:
• the speed with which messages are delivered
• the probability of losing messages
Sistem Waktu Nyata (CS4613)
Overheads causing delay
 Formatting and / or packetizing the
message
 Queueing the message, as it waits for
access to the communication medium
 Sending the message from the source to
the destination
 Deformatting the message
Sistem Waktu Nyata (CS4613)
Real-Time Traffic
 Typically classified by:
• Its deadline
• Arrival pattern
• Priority
 In hard RTS (exp: embedded appl.): the
deadline of the traffic is related to the deadline of
the task to which that communication belongs
 In soft RTS (exp: MulMed appl.): the deadline is
related directly to the application
Sistem Waktu Nyata (CS4613)
Real-Time Traffic (cont’d)
 Priority is based on the importance of that
message class to the application
 If there is an overload traffic, message
priority can be used to determine which
message are dropped to ensure that the
more important traffic is delivered in a
timely fashion
Sistem Waktu Nyata (CS4613)
RT Traffic Rates
 Constant rate: fixed-size packets are generated
at periodic intervals
• Many sensors produce such traffic
• Smooth and not bursty  easy to handle, small buffer
 Variable rate: fixed-size packet being generated
at irregular intervals (exp: voice –talkspurt–) or
variable-sized packet being generated at regular
intervals (exp: video)
• Bursty traffic  greater demands on buffer space
Sistem Waktu Nyata (CS4613)
Traffic characteristics may change
Class 1
n
Rate
Class 2
Class 2
Class 1
0
a
c
b
Time
Sistem Waktu Nyata (CS4613)
 Class 1 has priority at
node n
 Class 2 will piled up
over the intervals [0,a]
and [b,c]
 The output of class 2
from node n will also
bursty
Communications media
 Three most important media:
• Electrical
• Optical
• Wireless
 Each medium has a distinct set of
properties:
• Bandwidth
• Distance
• Fault / interference etc.
Sistem Waktu Nyata (CS4613)
Network Topologies
 Must be carefully chosen, since it affects
the system response time and reliability
 Broadly classified: point-to-point & shared
 Popular topologies: bus, ring, dual-ring,
star, n-dimensional hypercube, multistage
network
 Physical topology vs logical topology
Sistem Waktu Nyata (CS4613)
Important features of topology
 Diameter: max distance (number of hops)
between any two nodes
 Node degree: number of edges adjacent to each
node  determine the number of I/O port per
node and the number of links in the system
 Fault-tolerance: measure the extent to which the
network can withstand the failure of individual
links and nodes while still remaining functional
Sistem Waktu Nyata (CS4613)
Sending message
 Packet switching
 Circuit switching
 Wormhole routing  require less node buffer
• Pipelining packet transmission in a multihop network
• Each packet is broken down into a train of flits, each
about one or two bytes long
• The sender transmits one flit per unit time, and the
flits are forwarded from node to node until they reach
their destination
• Only the header flit in a train has the destination
information; each node is simply forwards the next flit
to the same node that it sent the previous flit to in the
train
Sistem Waktu Nyata (CS4613)
Protocols
 Contention-based protocols
• Virtual-Time Carrier-Sensed Multiple Access
(VTCSMA)
• Window protocol
 Token-based protocols
• Timed-token protocol
• Token-Ring protocol (IEEE 802.5)




Stop-and-Go Multihop protocol
Polled bus protocol
Hierarchical round-robin protocol
Deadline-based protocols
Sistem Waktu Nyata (CS4613)
CSMA
 CSMA is an efficient communication
scheme when the end-to-end transmission
delay is much less than the average time
to transmit a packet and when the load is
not very high
 CSMA is a truly distributed algorithm: each
node deciding when it will transmit
 Q: Is it possible to implement a priority
algorithm using CSMA?
Sistem Waktu Nyata (CS4613)
Exploiting CSMA
 Facts:
• Nodes do see a consistent time if their clocks are
synchronized
• Nodes observe the same channel
 Each node has information about:
• The state of the channel
• The priorities of the packets waiting in its transmission
buffer to be transmitted over the network
• The time according to the synchronized clock
Sistem Waktu Nyata (CS4613)
Exploiting CSMA (cont’d)
 Node does not have any idea of the
priorities of any packets that may be
awaiting transmission at the other nodes
 Simply using the state of the channel and
the priorities of its packets is not sufficient;
the time information must also be used
Sistem Waktu Nyata (CS4613)
Road to VTCSMA
 The key to VTCSMA: if the priority of the
packet can be computed as a function of
the current time, as well as of some other
parameter, it may be possible to use the
time information to implicitly arrive at some
global ordering of priorities.
• Exp: we can strive to serve packets according
to their deadlines, arrival times, and laxities
Sistem Waktu Nyata (CS4613)
Clocks in VTCSMA
 Uses two clocks at each node:
• The real clock (RC)
• tells the ‘real time’
• is synchronized with the clocks at the other nodes
• The virtual clock (VC)
• when the channel is busy, the VC freeze
• when the channel become free, the VC is reset
and then runs at the rate  >1
• VC runs faster than RC when the channel is free,
and not at all when it is busy
Sistem Waktu Nyata (CS4613)
RC & VC ( = 2 )
t4'
VC
t3'
channel busy
t2'
channel idle
t1'
0
t1
t3
t2
RC
Sistem Waktu Nyata (CS4613)
t4
VTCSMA algorithm
No
Is the channel idle?
Yes
Initialize the VC and start
it running at the
prescribed rate
Discard any message
that have missed their
transmission deadlines
Yes
Is there M such
that VSX(M)≤VC?
No
No
Is the channel idle?
Freeze VC
Yes
Transmit the highest
priority M at that node
Yes
Collision?
No
Sistem Waktu Nyata (CS4613)
Retransmit immediately
with probability p, or
(with probability 1-p)
modify VSX(M)
Some notations
 : Propagation time from one end of the
network to the other
 AM: Arrival time of message M
 TM: Time required to transmit message M
 DM: Deadline by which message M must
be delivered to its destination
 LM: Latest time by which the message
must be sent to be able to meet the
deadline; LM = DM – TM - 
Sistem Waktu Nyata (CS4613)
VSX(M)
 Virtual time to start transmission of
message M
 AM
T
 M
VSX ( M )  
 LM
 DM
Sistem Waktu Nyata (CS4613)
for VT CSMA - A
for VT CSMA - T
for VT CSMA - L
for VT CSMA - D
When collision occur…
 Retransmits M immediately, with
probability p
 Modify VSX(M): random number drawn
from the interval I
(current VC, L M )
(0, T )

M
I 
(current RC, L M )
(current RC, D M )
Sistem Waktu Nyata (CS4613)
for VT CSMA - A
for VT CSMA - T
for VT CSMA - L
for VT CSMA - D
When the channel switches
state from busy to idle…
 VC is initialized as follows:
no change for VT CSMA - A

VC  0
for VT CSMA - T
RC
for VT CSMA - L and VT CSMA - D

Sistem Waktu Nyata (CS4613)
Example
 VTCSMA-L;  = 2
 TM = 15;  = 1
 Messages:
Node
M
RC at arrival
DM
LM
1
1
0
32
16
2
2
10
36
20
3
3
20
56
40
4
4
20
72
56
Sistem Waktu Nyata (CS4613)
Example (cont’d)
64
M4
transmission
56
48
M3
transmission
VC
40
32
24
16
M1
transmission
M2
discarded
8
0
8
16
Sistem Waktu Nyata (CS4613)
24
32
40
48
56
64
72
RC
List of protocols
Protocol
DL guarantees?
Network
VTCSMA
Window
Timed token
IEEE 802.5
No
No
Yes
Yes
Broadcast
Broadcast
Ring
Ring
Stop-and-Go
Polled bus
Hierarchical
round-robin
Yes
No
Yes
Point-to-point
Bus
Point-to-point
Deadline-based
No
Point-to-point
Sistem Waktu Nyata (CS4613)
Project:
 Is a community-oriented environment for
distributed live musical performances
 It allows people in different cities to:
• connect musical instruments and video cameras to
computers
• find other musicians
• organize virtual music bands (up to four musicians)
• finally, play together over broadband Internet with
high quality sound and see the video picture of all the
members, as if they were in the same room
Sistem Waktu Nyata (CS4613)
LiveConcert
Main problem:
DELAY
(<50 ms)
Sistem Waktu Nyata (CS4613)
Sistem Waktu Nyata (CS4613)
omniMusic technical overview
 For RT audio & video transmission the smart
clients use peer-to-peer approach and multicast
technology
 omniMusic commits to deliver high quality sound
and ultra-low latency (<50 ms)
• Fast audio capturing with ASIO drivers
• Fast audio rendering to network with self-developed
kernel-mode driver using Kernel Streaming
technology
• Fast audio compression with self-developed codec
• Fast audio transmission with Real-Time Transfer
Protocol, on top of MSR Conference platform RTP
implementation
Sistem Waktu Nyata (CS4613)
Sistem Waktu Nyata (CS4613)
 omniMusic won the first prize in the
Software Design Invitational
 Russia:
Sistem Waktu Nyata (CS4613)
ITU H.323
Audio
CoDec
Video
CoDec
Terminal Control Interface
RTP
Transport
Call Setup
(H225/
Q931)
System
Control
(H245)
Video
Interface
RAS
(H225)
Application
Standards
Audio
Interface
RTCP
User
interface
Unreliable Transport (UDP)
Network
interface
standards
Sistem Waktu Nyata (CS4613)
Physical Layer
User data
application
(T120)
MCS
Reliable Transport (TCP)
Network Layer (IP)
Link Layer
User data
interface
RTP & RTCP
 RTP: Real-Time Transport Protocol
 RTCP: RTP Control Protocol
 H. Schulzrinne, S. Casner, R. Frederick,
V. Jacobson, RTP: A Transport Protocol
for Real-Time Applications, IETF RFC
1889
Sistem Waktu Nyata (CS4613)
QoS support
 Two levels of congestion control: global
internetwork level and operates at router
level
 Two schemes:
• Integrated Services (IntServ)
• Resource Reservation Protocol (RSVP)
• RFC 2205 - 2216
• Differentiated Services (DiffServ)
• RFC 2474, 2475
Sistem Waktu Nyata (CS4613)