Notesale: Turn your study into money

Document Preview

Extracts from the notes are below, to see the PDF you'll receive please use the links above

---

1 Scheduling, Resource Access Control and Synchronization
Thus far, we have ignored several realistic facts: Almost every system contains more than one
processor, control and data dependencies impose precedence constraints among jobs, and timing
constraints of jobs are usually not independent
...
1 Model of multiprocessor and distributed systems
The systems contains more than one processors
...
A multiprocessor system is tightly coupled so that
global status and workload information on all processors can be kept current at a low cost
...
When each processor has its own scheduler, the actions and
the decisions of the scheduler of all processors are coherent
...
The
schedulers on the different processors may make scheduling and resource access control decisions
independently
...

It is assumed that each processor has its own scheduler in this chapter
...

1
...
1

IDENTICAL VERSUS HETEROGENEOUS PROCESSORS

It is said that the processors are of the same type or identical, if the processors can be used
interchangeably
...
If any message from a source to a destination can be sent
on any of the data links connecting them, then the links are identical
...
Different types of processors may have
different functions
...

So, they cannot be used interchangeably
...
For
example, if the designer decides to use some CPUs for only some components of the system but not
others, then the CPUs are divided into different types according to the components that can execute
them
...
CPUs are viewed as µ different processors
...
According to this model, each job can execute on some types of
processors but, in general, not all types
...
The
execution times of each job on different types of processors are unrelated hence the name of the
model
...
Because CPU2 has better interrupt handling and I/O capabilities,
the execution time of an I/O intensive job is 10 seconds on CPU1 but is only 3 seconds in CPU2
...
The unrelated models allows us to characterize all system
...
the system contains µ types of processors
...
e Pi for i = 1, 2, 3,
...





Real Time System by Jane W S Liu
...
1
...
The jobs in each
task may have precedence constraints
...

1
...
2
...
The classical jobs shop and flow shop model captures this types of
concurrency
...
n(i) for all 1≤k≤n(i)
...
For example, the real-time
monitor task is a chain of three jobs
...
, Vi,n(i)) of the task
...
Therefore, the visit sequence of the real time monitor task is (field
processor, communication processor, and control processor)
...
T2 has five jobs and they execute in turn
on P2 then on P3, P4, P3 and finally on P1
...
For example,
suppose that all the tasks in a real-time monitor system are similar to the monitor task mentioned
above: each task samples, processes, and displays the reading of a different sensor
...

1
...
2
...
The first difference is a substantive one
...
Typically, the objective of classical job shop scheduling is to
maximize the throughput (i
...
the number of tasks completed per unit time) of the system or to
minimize the average response time of the tasks
...
Meeting hard deadlines is always our primary
objective
...
They give the release time and deadline of each task as a whole
...
The deadline di of the task is the deadline of its last job Ji,n(i)
...
The
executions of these jobs are constrained only by the dependencies between them and by the fact that
they must complete sufficiently early to allow the on-time completion of the last job
...





to-end release time and end-to-end deadline when we want to emphasize this point
...

1
...
2
...

Just like periodic tasks in uniprocessor environment, end-to-end tasks in a multiprocessor system may
be periodic
...
, Vi,n(i))
...

i

To be exact, the first subtask Ti,1 of an end-to-end periodic task Ti is a periodic task with period pi
...
Similarly, following the completion of the jth
job of the kth subtask Ti,k on processor Vi,k the jth job in the (k+1)st subtask Ti,k+1 can be released on
processor Vi,k+1
...
The period of an end to end periodic task is the period of its first
subtask
...

Similarly, execution time ei,k means the maximum amount of time required to complete any job in Ti,k
...
1
...
4 Parallelism
In addition to pipelined executions of jobs on different types of processors, parallel executions are
possible whenever there is more than one processor of the same type
...
Similarly, multiple links and switches between a sender and receiver pair
provide parallel paths that can be used to increase the throughput or reduce delays of messages
between them
...

1
...
3

Local versus Remote Resources

We assume that each resource resides on a processor
...

•

Resource models:
– MPCP (Multiprocessor Priority-Ceiling Protocol) Model
– End-to-end model

1
...
3
...
This model calls the processor on which each resource resides its synchronization processor
...
From the perspective of a job, a resource that also resides on the local processor of the job is a
local resource, and resource that resides on another processor is a remote resource
...


3




Notes by Roshan Pokhrel







Real Time System by Jane W S Liu
...
The system
shown here has three jobs, two processors, Pi
and P2, and two resources, printer and
fileServer
...
The jobs
J1 and J2 are local to P1, while J3 is a local
job on P2
...
It executes on P1 and uses
only the local resource printer
...

Similarly, the backup job J3 requires only
fileServer
...
(Critical sections during which the fileServer is used are shown
as black boxes
...
fileServer is a global resource
...
(Later, we will simply say that the global
critical section of J2 executes on P2
...

In summary, according to MPCP model, a job may require both local and remote resource
...
The
critical section during which the job uses a resource executes on the synchronization processor of the
resource
...
Requests for resources on
each processor may be from local jobs and remote jobs and the resource access-control protocol used
on the processor may handle these requests in different ways
...
A job may hold a resource on one
processor and then request resources on another processor
...

1
...
3
...
Stated another way, all the resources used by every job during every nested critical section
reside on the same processor
...

In Fig 9
...

•
•
•

The first one executes on its local processor and does not require any resource
Its remote critical section is the second component, and this component executes on the remote
processor P2
...


Since J1 and J3 do not require any remote resource, each of them consists of only one component
...


In general, each job that requires only local resources has only one component which executes on
local processor
...





the synchronization processor of the remote resources guarded by the critical section and the critical
sections nested in it
...
is before or after a remote critical section and
2
...

The scheduler of each processor can treat all requests for resources controlled by it as local requests
...
1
...
The reason is
that it is not necessary to account for the cost of interprocessor communication separately in an ad hoc
manner
...

A special-case of practical interest is where interprocessor communication is via shared memory
...
The implication is that the execution of a job is never adversely affected by memory
contention; therefore, the cost of interprocessor communication is negligible
...
When the assumption is not true, we can model shared memory explicitly
either as a resource or as a processor
...
2(a) shows a possible
configuration of a real-time monitor
system that has many field processors
...

Consumer jobs that correlate and display
the data execute on the control processor
...
Each field processor is
connected via a dedicated link to a port of
the memory that is shared by all field
processors
...
The system
contains three types of processors: field
processors, shared-memory processor and
the control processor
...

(Specifically, each producer is an end-toend job whose first component executes
on a field processor and whose memoryaccess component executes on the shared
memory
...
) In this way, the delay in the
completion of each job caused by memory contention is taken into account by the response time of the
5




Notes by Roshan Pokhrel







Real Time System by Jane W S Liu
...
Alternatively, you can model the shared memory as a global
resource whose synchronization processor is the shared-memory "processor," and both the producer
and consumer jobs require this resource
...

Specifically the network is a Controller Area Network (CAN)
...
Such a network can be modeled
as a processor on which message transmission jobs are scheduled nonpreemptively on a fixed-priority
basis
...

In general, communication networks can be modeled naturally as processors
...
5 token ring and CAN, more or less
resemble priority-driven algorithms used for CPU scheduling
...
In all cases, we can take into account
interprocessor communication costs by including net-work processor(s) and message-transmission
jobs in our model
...

Finally, CPUs may be connected via dedicated links
...
g
...
When a job sends a message, it is in a
critical section using this resource
...
In both cases, we can take into account the effect of interprocessor communication by
adjusting the execution time and blocking time parameters of all the jobs in the system accordingly
...
1
...
The end-to-end scheduling problem differs fundamentally from the
problems on multiprocessor and distributed scheduling
...
Many excellent
multiprocessor and distributed scheduling algorithms can be found in literature
...

Assumptions made in this chapter:
•
•
•

Each processor has its own scheduler
...

Schedulers on different processors may use different scheduling algorithms
...
2 Task assignment
Most of the hard real-time systems are static in nature
...
This process is called task assignment
...
In this case, it is necessary to perform an acceptance test to decide whether to execute each



Notes by Roshan Pokhrel

6





Real Time System by Jane W S Liu
...
There are three different types of task assignment methods
...
The first method
ignores both the cost of communication and the placement of resources
...

1
...
1

TASK ASSIGNMENT BASED ON EXECUTION TIME REQUIREMENTS

Sometimes, it is appropriate to consider only the processing time requirements of the jobs and tasks
and ignore communication costs
...
For some
applications (e
...
, signal processing), it is possible to provide a sufficient number of memory modules
and carefully lay out the address spaces of tasks to minimize memory contention
...

1
...
1
...
It is used to
determine whether the number and kinds of processors planned for the systems are adequate
...

Consider that the utilization of n periodic task is given and it is asked that the system should be
portioned into modules in such a way that the tasks in each module are schedulable in a process
according to a uniprocessor scheduling algorithm
...
We can say that the assignment requires ‘m’ processors if it partitions the ‘n’
task into ‘m’ schedulable modules
...
The smaller the number of processors required by an
assignment, the better the assignment
...
In this case, the utilization of all
the task is more than 1, therefore it is not possible to schedule feasibly on a single processor
...
, n of all the tasks
...
However,
it is constrained that the total utilization of all the tasks in each module should be less than or equal to
some value U<1
...
From this, we can formulate a task assignment problem as the
simple bin packing problem in which the sizes of all the bins are equal to U and the sizes of items to
be packed into the bins are u = 1, 2,
...
the number of bins required to pack all the item is the
number of processors required to feasibly schedule all the n tasks
...

i

•
•

In this situation, a more meaningful question is how large can the total utilization of the
periodic tasks be for the existence of a feasible assignment, that is, an assignment according to
which the tasks on every processor are schedulable?

•

7


Sometimes, we are given a fixed number m of processors
...





Note: In First fit algorithm tasks are assigned in processor one by one in an arbitrary order
...
After i-1 tasks have been assigned , the ith task Ti is assigned to
processor Pk if the total utilization of Ti and the tasks already assigned to Pk is equal to or less than U,
but assigning Ti to any of the processors P1,P2,…,Pk-1 would make the total utilization of tasks on the
processor larger than U
...


1
...
It is also assumed that the resources used by every job during nested critical sections lies on
the same processor
...
According to the
MPCP model, when a task uses a global resource, its global critical section executes on the
synchronization processor of the resource
...
For
preventing this, the multiprocessor priority ceiling protocol schedules all the global critical sections at
higher priorities than all the local tasks on every synchronization processor
...
The scheduler of each
synchronization processor schedules the global critical sections of a task with priority πi at priority πi πlowest
...
A global critical
section of a task with priority 5 is scheduled at priority 0, which is higher that priority 1
...

lowest

1
...
1

BLOCKING TIME DUE TO RESOURCE CONTENTION

The figure below shows the illustration that the types of blocking a job may suffer under the
multiprocessor priority ceiling protocol
...
Jobs J2, J4 and J5 are local to processor P1, which is the
synchronization processor of the resource dotted
...
Jobs J1 and J3 are local to processor P2, which is the synchronization processor
of the resource black
...
The jobs are
arranged in decreasing order
...





Notes by Roshan Pokhrel

8





Real Time System by Jane W S Liu
...
J1 is directly blocked by J3 when
J1 requests black at time 3
...
The preemption delay thus suffered by J2
must be taken into account when the schedulability of J2 is to be determined
...

At time 11, J1 exits from its critical section
...
As a result, J2 preempts J1 on P2 in the interval (11, 12]
...

Finally, a job can be delayed by a local higher priority job whose execution is suspended on the local
processor when the priority job executes on a remote processor
...
Here in this example, J2 is suspended at time 7
...
2 cannot start until time 14
...
4 Elements of Scheduling Algorithms for End-to-End Periodic Tasks
End to end scheduling has two essential components:
1
...

2
...

According to the end to end scheduling approach, the fact that no subtasks in the system ever requires
remote resource makes it possible for the scheduler on each processor to use any on uniprocessor
scheduling algorithms and resource access protocols to schedule subtasks on the processor and control
9




Notes by Roshan Pokhrel







Real Time System by Jane W S Liu
...
It is even possible for the system to use a mixture of more than one
scheduling strategy
...

Most of the real life systems use mixed scheduling strategies on different processors
...
The
computers at the two ends schedules the compression and decompression subtask differently from the
way the network schedules the transmission of the video
...
4
...

When should jobs in subsequent sibling subtasks be released?
This question doesn’t arise in uniprocessor systems, but is important in multiprocessor systems
because how jobs in sibling subtasks are released critically affects in multiprocessor systems because
how jobs in sibling subtasks are released critically affects the schedulability, completion-time jitter,
and average response time of end-to-end tasks
...
Since there is no ambiguity, we call it simply a synchronization protocol
...
Never releases jobs in any first subtask before the end to end release times of the jobs, and
2
...

There are two types of synchronization protocols:
1
...
Non-Greedy Synchronization Protocol (nonwork-conserving)
When sibling subtasks are synchronized according to the greedy synchronization protocol, the jth job
ji,k+1;j of a subtask Ti,k+1 is released on Vi,k+1 as soon as its immediate predecessor Ji,k;j completes on
Vi,k, for every k=1, 2, …, n(i)-1
...

1
...
2

GREEDY SYNCHRONIZATION PROTOCOL

It is a commonly used synchronization protocol, especially in real time system
...
It can be implemented as follows: when the jth job of Ti,k completes on Vi,k,
the scheduler of Vi,k sends a synchronization signal to the scheduler of Vi,k+1 on which the successor
subtask Ti,k+1 is executed
...
Since, the multiprocessor system model used here takes into
account interprocessor communication costs, the delay in synchronization signal delivery id let to be
0
...
It does not require any global clock
synchronization
...
The greedy synchronization protocol yields the shortest average end to end response
time of all tasks compared with non-greedy protocols
...





jobs in a later subtask can be shorter than the period of the subtask
...


(a) Greedy Synchronization

(b)nongreedy synchronization
Consider a system with two processor and three tasks: T1 = (6, 3), T3 = (6, 10, 4) do not have
subtasks, and they are executed on P1 and P2
...
The relative end to end deadlines of the tasks are equal to their respective
periods
...
T1 has higher priority on P1 and
T2,2 has a higher priority on P2
...


on the basis of greedy protocol
...
Since, the inter-release times of jobs in T2,2 can be as short
as 6, T3cannot meet its deadlines
...

T3 always meets its deadlines
...
Futhermore, there is yet no schedulability analysis method that can give sufficiently tight upper
bounds to end-to-end response times of greedily synchronized, fixed-priority tasks
...


1
...
We now remove this restrictive assumption
...
All but the simplest embedded systems contain different types of processors (e
...
CPUs,
disks, and networks)
...

Exactly which scheduling algorithms are used on individual processors and how these algorithms
work are unimportant here
...
e
...

Hereafter, by a real-time scheduling algorithm, we mean specifically one that meets this requirement
...
Without loss of
generality, it is assumed that the scheduler on every processor uses a real-time scheduling algorithm
...
The modified phase protocol (MPM) and release guard (RG) protocol are
examples of such protocols
...

Corollary

In a system where a real time algorithm is used to schedule sub-tasks on every processor, an upper
bound Wi to the end to end response time of any periodic task Ti synchronized to the MPM protocol or
the RG protocol is given by

Where n(i) is the number of subtasks in T and the upper bound W to the response time of every
subtask T is obtained by considering only subtasks on the same processor as T and by treating every
subtask T as a periodic task whose period is equal to the period P of the parent task T
...





1
...
If every job in J were to
execute for as long as its maximum execution time (or short as its minimum execution time), the
resultant schedule of J would be the maximal (or minimal) schedule
...
The actual
execution times of jobs are unknown, and therefore, the actual schedule of J is unknown
...
The start time of Ji is said to be unpredictable if this condition
13


Notes by Roshan Pokhrel







Real Time System by Jane W S Liu
...
Similarly, the actual completion time f(Ji) according to the actual schedule of J can be later
than its completion time f+(Ji) of Ji according to the maximum schedule
...
On the other hand, if s-(Ji) ≤ s(ji) ≤ s+(Ji) then Ji is start time predictable
and if f-(Ji) ≤ f(ji) ≤ f+(Ji), then Ji is completion time predictable
...
The execution behavior of the entire set J is
predictable if every job in J is predictable
...

According to the maximal and minimal schedules, when one of these conditions are satisfied, the
response time of each job gives the upper and lower bounds of the response time
...
6
...
Every job that can be dispatched to execute on any processor can
be preempted at any time and when preempted, they can be resumed on any processor
...
A condition for predictability of a preemptable or migratable
system is: the jobs have no precedence constraints and do not contend for resources
...

1
...
2

OTHER CONDITIONS FOR PREDICTABILITY

The system shown in above figure is a preemptable or migratable system
...

However, once a job starts on a processor, it is constrained to execute on that processor
...
Under the theorem stated below, the execution of preemptable or migratable, independent jobs is
predictable
...

Theorem 2
If according to the maximal schedule of a system of preemptable/nonmigratable independent jobs, no
job is preemptable and the jobs start in the same sequence according to the maximal and minimal
schedules, then their execution is predictable
...





2 Real-time Communication
2
...
The hosts are connected by a
communication network or several interconnected networks
...

2
...
1

ARCHITECTURAL OVERVIEW

We focus on message exchanged among applications on different hosts
...
The network
interface of each host contains an input queue and an output queue which can also be referred to as
input/output buffers or simply buffers
...
The TP handler interfaces with local applications and provides them with
message transport services
...


fig
...
The circles marked TPH and NACH are TP and NAC handlers, respectively
...
From there, each outgoing message is delivered to the network under the control of the source
NAC handler
...
Then, the destination TP handler
15


Notes by Roshan Pokhrel







Real Time System by Jane W S Liu
...

When there is no possibility of ambiguity or when there is no need to be specific; we use the terms
source and destinations endpoints (or simply source and destination) to mean either the source and
destination applications tasks, or the TP handlers, or the NAC handlers, or the entry and exit points of
the network
...
The source and destination applications are the predecessor and successor of this
chain, respectively
...
In between them, each job that accesses the network or transmits the message
becomes ready for execution after its immediately predecessor completes, possibly with some delay in
its readiness introduced by the execution synchronization protocol used along the path
...
1
...
Each segment is handled by the network as a basic transmission unit, and the transmission of
the unit is nonpreemptable
...
We use the name packet to refer to all these basic transmission units
...
In an IEEE 802
...
(The maximum length of a data frame in a token ring is limited by the length
of time a station is allowed to transmit each time it is polled
...
(We
include in this time the processing overhead, that is, the time required for packet header processing
and other operations performed on the packet in order to transmit it
...
24 microseconds and, hence, a time unit is 4
...
If the transmission rate of the link is 1 GHz, then a time
unit is 424 nanoseconds
...
For example, a message of length 100 has 100 x 53 = 5
...
On the other
hand, if the length of each packet is 10,000 bytes, then a message of length 100 has 1 Mbyte; still, its
transmission time is 100 time units
...

Furthermore, we measure the length of each transmission link by the number of packets that can be
transmitted within the length of time they take to traverse the link
...
24 = 23
...
but this delay
is only one time unit if the packet size is 10,000 bits
...
the same 100 microseconds
is 236 or 10 time units, respectively
...
Similarly, when our discussion focuses on one input or output link, the
absolute value of its bandwidth is irrelevant; only how this bandwidth is allocated among the message
streams on the link is
...

When we say that a message stream is allocated a bandwidth of û, we always mean that the message is
given the fraction û of the link bandwidth
...
1
...





REAL TIME TRAFFIC MODELS

In real-time communications literature, the term real-time traffic typically means isochronous (or
synchronous) traffic, consisting of message streams that are generated by their sources on a continuing
basis and delivered to their respective destinations on a continuing basis
...
which require some degree of guarantee for on-time delivery
...
Aperiodic messages have soft timing
constraints and expect the system to deliver them on a best-effort basis
...
We use interchangeably the
expressions that a message instance or packet arrives and that it is released for transmission
...

Periodic and Aperiodic Messages
...

Specifically, the transmission of a periodic message is a periodic task
...
Constant Bit-Rate (CBR ) digitized voices and videos are accurately modeled by
periodic messages
...
This means that the interarrival
(interrelease) times of instances in M, are never less than the period pi of the message, the maximum
length of the instances in M, is equal to ei packets, and each instance must be delivered to the
destination within Di units of time from its arrival at the source
...
This traffic model is called the peak rate model in real-time communication literature
...
Like aperiodic tasks, an aperiodic message stream does not have a relative deadline
...

Sporadic Messages
...
Similarly, a periodic message is an inaccurate
model of any sporadic message stream that some threshold miss rate is never exceeded; some statistics
and histograms on miss rate usually suffice
...
This assumption is usually valid for computation tasks but often not valid in
communication systems
...
When a queue is full or when the queue length reaches a certain (drop) threshold, some
packet(s) destined for the queue are dropped (i
...
, discarded)
...
The loss rate of a message stream or a set of message streams gives the fraction of all message
instances (or packets) in the stream(s) that are dropped en route for flow and congestion control
reasons
...
)
Delay Jitter, Buffer Requirement, and Throughput
...
g
...
For example, the performance of a video-on-demand system is not seriously
17


Notes by Roshan Pokhrel







Real Time System by Jane W S Liu
...
In contrast, delay jitter and
throughput are important
...
g
...
There is no
advantage to completing a job in a periodic or sporadic task early
...
In fact, it may be disadvantageous to do so
...
Hence, a larger delay jitter
of a message stream means that more buffers must be provided by the stream
...
Fortunately, these performance measures can be minimized
simultaneously by using some nongreedy synchronization protocol
...
Most of the
scheduling and flow-control algorithms are rate-based, meaning that they are designed to provide each
message stream with a guaranteed minimum throughput independent of the demands of the other
message streams
...
1
...
The
user is concerned with the on time delivery of periodic and sporadic messages and the average
response time of aperiodic messages
...

Loss rate: gives the fraction of all message instances in the stream that are dropped en route for flow

and congestion control reasons
...

Buffer Requirement: a packet that arrives too early to be processed by the destination must be

buffered
...

Throughput: the rate of each message stream measures the throughput of the stream
...
1
...
According to the
connection oriented approach, a logical simplex connection from the source to the destination is set up
for the transmission of each message stream (or set of message stream)
...
The chosen route remains in use until the connection is torn
down or when some adaptation mechanism is invoked to alter the route
...
As examples, high
speeds of modem networks make it impractical to route individual packets independently
...





endpoints, to set aside the required bandwidth and buffer space for the connection so the network can
provide some form of performance guarantee
...
g
...

To request a connection, the requesting client (or clients) declares the characteristics of the message
stream and the required performance of the connection
...
Collectively, these parameters are called the flow
specification
...
The admission controller of each handler and switch along the
chosen route uses these parameters as the basis of an acceptance test to determine whether to admit
the connection
...

Packet Switched Networks
The diagram in Figure 11-2(a) illustrates such a network
...
Figure 11-2(b) shows a m x m switch; it has m input links and m output links, both called
links 1, 2,
...
The switch routes packets on its input links to its output links
...
e
...
, m)
...
As an example, for a 4 x 4 switch, the 4tuple (2, 4, 1, 3) means that a packet on input link 2 goes to the queue of output link 1, a packet on
input link 4 goes to the queue of output link 2, and so on
...
The switch is nonblocking, meaning that every permutation represents a possible
switching pattern
...
At each switch, there is a
buffer pool for each of its output links, holding packets that are queued for transmission on the link
...
The amount of time the switch takes to route packets from its input links to its output links is
negligibly small
...
e
...
e
...

We call this sum the per hop delay of the packet
...





Service Discipline
The combination of an acceptance test and admission control protocol, and synchronization protocol
and a scheduling algorithm used for the purpose of rate control, jitter control and scheduling of
packets transmission is called a service discipline
...
Flow control is applied at endpoints and within the
communication network to prevent an entity upstream from overloading entities down-stream
...
) Traditional flow-control schemes, such as the sliding-window protocol are
inappropriate for real-time traffic for many reasons
...
Rate and jitter control mechanisms for real-time traffic are integral parts of
a service discipline, rather than being separated from scheduling and buffer management functions
...

Specifically, the term rate control is used in the communications literature to mean load management;
the purpose is to ensure that the bursty traffic and resulting overloads on any connection do not
adversely affect the performance of other connections
...
e
...
Overloads that arise can be
managed by exercising rate control at individual switches
...
Jitter control is usually done by
preserving the traffic pattern of the first switch at every switch
...
) As a result of
jitter control, not only the end-to-end delay jitter and required buffer space at each switch en route are
kept constant, rather than growing linearly with the number of hops from the source when there is no
jitter control, but also overloads at downstream switches and the destination are managed as
byproducts
...

•
•



rate-allocating,
rate-controlled
Notes by Roshan Pokhrel

20





Real Time System by Jane W S Liu
...
e
...
A service
discipline is rate-controlled if it ensures each connection the guaranteed rate but never allows packets
on any connection to be sent above the guaranteed rate
...
The sporadic/background server and the total
bandwidth server are examples
...
So rate-allocating
algorithms are work-conserving (i
...
, greedy), while rate-controlled algorithms are nonworkconserving (i
...
, nongreedy)
...
2 Priority-based service disciplines for switched networks
According to the priority based service discipline, the transmission of ready packets are scheduled
priority driven manner
...

2
...
1

Weighted Fair Queuing Discipline

It is a packet by packet generalized processor sharing algorithm
...

Let n denote the number of established connections on the link
...
Let 𝑈 = ! û! denote the total link bandwidth allocated to all n
!!!
connections
...
(The implicit assumption is that the switch subjects
each new connection request to an acceptance test and rejects the request whenever the requested
bandwidth exceeds the available bandwidth
...
2
...
1 SCHEDULING PACKETS
Assume that the switch is output buffered
...
Each
connection-i packet is placed at the end of this queue upon arrival without scheduler attention
...
Each packet is removed from the
queue when its transmission completes
...

For the purpose of scheduling ready packets on backlogged connections, the scheduler keeps a priority
queue
...
The entry
gives the finish number fni of the connection, or more precisely, the finish number of the ready packet
on the connection
...
The entries are sorted in order of finish
numbers: the smaller the number, the earlier in the queue
...
The only exception to this order is the entry of the packet
currently being transmitted
...
Ready packets on backlogged connections are transmitted in the order given
by this queue
...





When the first packet in a busy interval of the output link arrives, the scheduler computes its
finish number and enters this number and connection ID in the SFN queue
...

• During a link busy interval, the scheduler computes the finish number of each packet that
arrives on an idle connection and inserts the corresponding entry into the SFN queue
...
The scheduler chooses the-next packet to transmit in the following manner
...

If connection i is still backlogged, the scheduler computes the finish number of its new
ready packet and inserts this number and connection ID in the SFN queue
...

It then commences the transmission of the ready packet on the connection identified by the
first entry in the SFN queue
...
2
...
2 Computing Finish Numbers
It is necessary for the scheduler to maintain the current values of the total bandwidth Ub of all
backlogged connections and the finish number FN of the link
...
There are n existing connections on
the output link of interest here
...
Also, we normalize time so that the maximum length
of all packets transmitted over the link is 1
...





The end-to-end delay of a packet of length e through ρ homogeneous switches under the WFQ
algorithm is given by

2
...

However, messages in a switched network are pipelined through the switches; earlier packets in a
message are sent from a switch without having to wait for the arrivals of later packets
...
Its major advantage over the timedriven scheme when used for end-to-end scheduling in a network or distributed system is that it does
not require globally synchronized clocks
...
These advantages make the WRR scheme
a good practical choice, especially for constant bit-rate traffic such as uncompressed voices
...

In a round-robin scheduling, the jobs are placed in a FIFO queue
...
If it does not complete within
a time slice, it is preempted and put at the back of the queue
...

But in the weighed round robin scheduling, each job gets a weight wti
...


23


Notes by Roshan Pokhrel







Real Time System by Jane W S Liu
...
3
...
In this discipline during
connection establishment, the scheduler at each switch assigns to the new connection i a weight of wti
...
Each slot has length 1, the
time to transmit a maximum-size packet
...
3
...

During each round, if more than wti packets on connection i are waiting, wti packets are transmitted
...
After the scheduler
completes the transmission of packets on connection i, it proceeds to transmit packets on connection i
+ 1 in the same manner; except, of course, the maximum number of packets on connection (i + 1)
transmitted per round is wti+1
...

A design parameter of each switch is the maximum number of slots RL (round length) per round
...
Each connection i is guaranteed the throughput rate of wti/RL, and this guarantee is
never violated due to overloads on other connections
...
A packet
may have to wait for an entire round even when there is no other packet on the connection waiting at
the switch when it arrives
...
7a

where Pmin is the minimum of the periods of messages on all existing connections
...

𝑤𝑡! >

!!

11
...
On the other hand, if connection i were assigned a smaller weight than the lower bound
in 𝑝𝑖/𝑅𝐿 , the throughput provided to connection i would be lower than the declared peak rate ei/pi of
its message
...

Since each message in Mi takes at most 𝑒𝑖/𝑤𝑡𝑖 rounds to complete, the delay of the message through
a switch is at most equal to 𝑒𝑖/𝑤𝑡𝑖 𝑅𝐿
...
Therefore, the message suffers this delay only at the first switch but
only one more additional round of delay through each of the subsequent switches
...





Notes by Roshan Pokhrel

24




2
...
3

Real Time System by Jane W S Liu
...
It would be too costly for the scheduler to
adjust the round length dynamically as a part of acceptance test and admission of new connections
...
In particular, the round length used for each output
link satisfies the constraint Eq
...
7a) for all anticipated connections
...
Again, the request for each new connection provides as part of the flow specification the
parameters pi, ei, and Di of the message stream Mi to be carried by the new connection i
...
(11
...
If the sum of weights assigned to all existing
connections is no more than 𝑅𝐿 − 𝑤𝑡𝑖, the scheduler accepts the connection and allocates wti slots
per round to the connection
...
If all ρ switches on the
route selected for the connection accept the connection and the end-to-end delay computed according
to Eq
...
8) does not exceed the end-to-end relative deadline Di of Mi, the connection is admitted and
established
...

2
...
4

Delay Jitter and Buffer Requirements

The WRR discipline is greedy and, hence, rate allocating
...
Like all other greedy disciplines, the greedy WRR discipline does not
control delay jitters
...
(This occurs
when every packet is transmitted in 1 unit of time after its arrival at all p switches en route
...

At the kth switch from the source of a connection i, the end-to-end delay jitter is 𝑝𝑖 — 𝑒𝑖 +
(𝑘 — 1)(𝑅𝐿 — 1)
...
As expected, this
amount grows linearly with the number of hops from the source
...


2
...
" A Medium
Access-Control (MAC) protocol is a discipline for scheduling this type of processor
...
This is why
MAC protocols typically either look different or are in fact different from the scheduling algorithms
described earlier
...

We call the transmission medium of a network simply the network
...
Each basic unit of data is transmitted nonpreemptively
over the network a packet
...
Each station maintains its own outgoing and incoming queues as shown in Figure 111
...





address of the destination station (or the ID of the message)
...
It copies the packet into its buffer (i
...
, it receives the packet) when it hears its
own address in the packet header (or the ID of a message it is prepared to receive)
...

2
...
1

Medium Access Protocols in CAN and IEEE 802
...
If this ratio is small (say on the order of 10-2 or
smaller), every station can hear the transmission of every other station almost immediately after the
transmission starts
...
In a small network,
circulating control information among the stations takes a small fraction of packet transmission time
...
By so doing, they can carry out a centralized scheduling algorithm in a
distributed manner
...
4
...
1 FIXED-PRIORITY SCHEDULING IN CAN
Controlled Area Networks are the examples of small networks
...
For example, an automobile control system, whose components control the
engine, the brakes, the environment and so on
...
It means, within a fraction of a bit-time
after statin starts to transmit, all the stations on the network can hear the transmission
...
The output of all the stations are wire-ANDed together
by the bus: the bit on the network during a bit-time is a logical 0 if the output of any station is a 0 and
a logical 1 only when the outputs of all stations are 1
...

Each message stream transmitted in a network has a unique message ID
...
A station on the network determines whether to
receive a packet based on the ID number of the packet
...

CAN MAC protocol is a CSMA/CD (Carrier-Sense Multiple Access/Collision Detection) protocol
...
At the same time the station listens
...
This way, network
contention is resolved in favor of the packet with smallest ID among all contending packets
...
The smaller the ID the higher the priority
...

2
...
1
...
5 TOKEN RINGS
In an IEEE 802
...
A station transmits a packet by breaking the network and placing its packets on the
output link to the network
...
When the packet returns to the source
station, the station removes the packet from the network
...
For polling, each packet
has an 8-bit Access Control (AC) field in its header
...

A station can determine whether the network is busy or free by examining tokenbit
...





packet circulates around the ring, the stations are polled in a round robin manner in the order of their
physical locations on the ring
...

When a free token reaches a station that has outgoing packets waiting, it can seize the token (i
...
, stop
it from circulating) under the condition
...
When the station completes its transmission,
it generates a free token and transmits the free token downstream
...

Priority Scheduling
Prioritized access is made possible by using the two groups of 3 bits each in the AC field: Their values
represent the token priority ∏T and the reservation priority ∏R
...
A station can seize the free token only when its outgoing packet has an
equal or higher priority than the token priority ∏T
...
It then marks
the token busy and puts the token in the header of the packet and transmits the packet
...
As a data packet circulates around the ring, a station with outgoing
packets can make a reservation for future use of the network by setting the reservation priority bits in
the AC field to the highest priority π of its outgoing packets, if π is higher than ∏R
...

When a source station removes its own packet from the network, it saves the reservation priority
carried in the packet
...
In this case, the priority arbitration mechanism allows the stations to jointly carry
out any fixed-priority scheduling algorithm
...
e
...
e
...
Packets in messages of any class can be given the same priority
...

Schedulability Analysis
The amount of time each packet occupies the network is equal to its transmission time plus the roundtrip delay it takes to return to the source station
...
The round-trip delay includes the
propagation delay of the transmission medium itself, plus the delays introduced by stations on the
network
...
By
including this delay and the time used to transmit the packet header, the checksum, and the delimiting
bits in the execution time, the overhead introduced by framing the user data according the MAC
protocol can be taken into account
...

•

27


Context Switching: A context switching time is equal to the amount of time required to

transmit a free token, plus the round-trip delay of the network, which is an upper bound of the
time the token takes to reach the station whose outgoing packets has the highest priority
among all outgoing packets during the transmission of the latest data packet
...


•

•




Blocking: Since packets are transmitted non-preemptively, we need to take into account the

blocking time due to non-preemptivity
...
The blocking delay caused by this priority inversion must also be taken into
account
...

Limited priority levels: Since the network provides only eight priority levels, schedulability
loss should also be take into account
...
5 Internet and Resource Reservation Protocol
We know that rate and jitter control is an integral part of good service disciplines for real-time traffic
in switched networks
...
e
...
Similarly, in order to deliver the desired quality of service to users through interconnected
networks, hosts and routers must re-serve resources needed to ensure quality
...
Traditional congestion-control mechanisms do not work well,
whereas admission control and resource reservation provide an effective means to prevent congestion
...

2
...
1

Issues in Resource Reservation

There are four closely related issues that a resource-reservation protocol must deal with but we have
ignored thus far
...

1
...
In applications such as video-ondemand and teleconferencing, messages from a source
are broadcast to multiple destinations
...
In the former case, there is one source: The
communication is one-to-many
...

Many distributed applications and fault-tolerance
mechanisms also require multicast capabilities among
entities
...
The
common approach is to give each source a multicast tree connection to all destinations
...





switches) and hosts that form a spanning tree; the tree is rooted at the source and connects all the
destinations
...
The graph represents a multicast tree from the source
host H1
...
Each
directed edge in the tree represents a simplex connection
...

When there is more than one source host in a multicast group and all sources may transmit at the same
time, the only viable approach is to have a multicast tree for every host
...
) Oftentimes, however, only a subset of hosts in the group transmits
simultaneously
...
)
One can save a great deal of resources by having the sources share resources whenever possible
...
We use an undirected edge between a pair of
endpoints to represent one or more pairs of simplex connections in both directions between the
endpoints
...
Hosts H2 and 115 receive messages but never send any of their own
...
Hi never receives, and 1/4 sends and receives via different routers
...
We can sometimes reduce the bandwidth and buffer space reserved
for a multicast group at routers and links traversed by more than one multicast tree of the group by
using a resource-reservation protocol that considers the aggregate requirements of the multicast group
as a whole
...

2
...
A method to accommodate different quality of service requirements of
destinations is to have the source use a layered scheme to encode its messages
...
A destination may choose to receive
only packets that give it a poorer quality video and audio, rather than all the packets that the source
uses to encode high-resolution and -fidelity video and audio
...

As an example, suppose that the hosts H4 and H5 in Figure 11-11(a) can only receive and process a
low-resolution video stream
...
The other hosts demand a high-resolution
video transmitted by HI, and resources required to guarantee the timely delivery of the high-resolution
video must be reserved at entities represented by the subtree at and to the left of R2
...
Dynamic Multicast Group Membership
Another behavior of many multicast applications is that participants may join and leave a multicast
group
...
A viewer may preview or order a movie at any time
...
When there is more than one source in a multicast group, the destination may choose
to receive from different sources and make this choice dynamically
...





teleconference, a destination with limited resources may choose to receive only videos from a subset
of the multicast group
...

4
...
Good utilization of network resources can be
achieved only if the resources required by the connection are taken into account in the choice of the
route
...

An alternative is to treat resource reservation as a separate function from routing and admission
control
...
Modularity is an obvious advantage
...
Rather, it makes use of the routing and admission-control functions provided by the network or
interconnected networks
...
" With this approach, the routers
used by each multicast tree are chosen by the routing protocol based on partial knowledge of the
resource requirement (e
...
, maximum and average demands) of the multicast group
...
However, resources reserved for a multicast group can be reclaimed if they
are not needed later, so it is not obvious that modularity can be gained only at the expense of
significant performance penalty
...

Design Objectives
...
At any time, the total resource demand
of the multicast group as whole is usually smaller than the sum of the demands of individual members
because the members may not use their resources at the same time
...


2
...
Yet these protocols are unsuitable for real-time applications for many
reasons
...
Previously, we have argued that the connection-oriented approach is
more advantageous for real-time applications because of the ability to reserve resources, manage
quality of service, and provide isolation in an end-to-end manner for each flow
...
STII is such an alternative
...
However, its error-control,
flow-control, and sequencing mechanisms are designed to provide users with reliable, sequenced data
delivery; they can introduce large delay and jitter and severely limit end-to-end throughput
...
For these applications,
the cost in real-time performance is too high for the gain in reliability
...
RTP is a data transport protocol for real-time applications
...

2
...
1

Data Transport

RTP is designed to support multicast communication in interactive multimedia applications, such as
audio and video teleconferencing and distributed simulation
...





uses services (e
...
, multicast routing, resource reservation and quality of service guarantee) provided
by lower-layer protocols
...
It uses
UDP's multiplexing and error-control services and compensates UDP with its own sequencing
function
...

RTP is designed to be scalable from a few participants to thousands of participants in multicast
communication and to be able to accommodate heterogeity of sources, receivers, and networks
...
In contrast with TCP, which is
separate from applications, RTP is often integrated with applications
...
the protocol can be tailored by applications
...
According to RTP, their audio and video data are transmitted separately
...
The combination of the network address and a port is a destination
transport address, so each medium uses a pair of transport destination addresses
...
In the
case where the underlying layer supports only unicast, each participant has its own transport
destination address
...
Thus their multicast session is established
...
6
...
1 RTP Packets
During the conference, each chunk of audio or video data (e
...
, a segment of audio-or an image) from
each participant is framed by an RTP header to form an RTP packet
...
A participant may
have multiple microphones and cameras
...
Headers of
data packets from the same SSRC (synchronization source) have the same SSRC identifier: the
identifier helps a receiver separate data packets from the SSRC from data packets generated by other
SSRCs
...
The header of each
RTP packet contains the time stamp and sequence number of the packet
...
The latter gives the order of the packet with respect to
other packets in the same data stream
...
(UDP packets are routed
through the network independently of each other, so, if RTP runs on top of UDP, there is no guarantee
against lost and out-of-sequence packets
...
g
...

Examples of encoding methods are PCM (Pulse Code Modulation) for audio and JPEG for image
...
The flexibility of using different
encoding methods enables the applications to trade off between quality and resource demands
...
This is also a way for a multicast group to accommodate a new
participant who is resource poor and is constrained to use a lower-quality/required bandwidth scheme
...





2
...
1
...

In addition to hosts, there are also mixers and translators; both are RTP relays
...
To a relay
...
g
...

Each translator relays streams of RTP packets from different sources separately, that is, without
altering their SSRC identifiers
...

Translators may be used as filters that forward packets to destinations protected by firewalls for
security reasons
...
g
...

In contrast to translators, a mixer receives data streams from one or more sources, combines the
streams in some manner, possibly changes the data encoding, and then forwards the combined stream
onward
...
The mixer is the SSRC of the combined stream
...
Each packet in the combined
stream contains in its header a CSRC list, which gives the identifiers of the contributing sources of the
data contained in the packet
...

Often, mixers are used to support heterogeity among destinations
...
To accommodate such a destination
without forcing all destinations to accept poorer quality, a mixer may be used to forward the lowerbandwidth audio stream on low bandwidth links
...
g
...
)
2
...
2

RTCP Control Protocol

As stated earlier, there is a control port associated with each data port
...
Specifically,
reception quality is fed back to every participant in a multicast group, as well as to a network service
provider or monitor when there is one
...
This information is needed to support adaptive encoding and congestion control
...

2
...
2
...
e, a destination) periodically sends RTCP report packets, simply called reports
hereafter
...
This block provides the values of performance measures (e
...
,
fraction and cumulative number of packets lost, interarrival jitter, and delay) used to measure the
quality of the data from the source
...
A receiver
report contains only reception blocks
...
Otherwise, if it has sent some data, it sends a sender
report, which contains a sender information section, in addition to reception blocks
...




Notes by Roshan Pokhrel

32





Real Time System by Jane W S Liu
...
For example, usually only one or two people talk
and only a few images are sent and displayed at a time during a teleconference independent of the
group size
...
To constrain the growth in control traffic, RTCP
keeps the total bandwidth consumed by control packets from all participants in a multicast group
constant
...
This 5 percent is further divided among
senders (i
...
, those sending sender reports) and nonsenders, with 1
...
75 percent for nonsenders
...

2
...
2
...
e
...
The information it maintains for the purpose of this
computation include the following:
•
•
•
•
•
•

tp: the previous transmission time of a RTCP packet;
tn: the next scheduled transmission time of a RTCP packet;
members: the most recent estimate of group size;
senders: the most recent estimate of the number of senders in the session;
rtcp_bw: the total bandwidth to be used for RTCP packets by all participants; and
avg _rtcp _size: the average RTCP packet size, in octets, over all RTCP packets sent and
received by participants
...

While the average retransmission interval of each participant is chosen deterministically, the next
transmission time tn is chosen randomly
...
Specifically,
the value of the retransmission interval p is computed in two steps
...
The average retransmission interval pd is computed deterministically according to 𝑝𝑑 =
𝑚𝑎𝑥(𝑃𝑚𝑖𝑛, 𝑛𝐶) with the parameters pmin , C and n determined according to the rules given
below
...
The retransmission interval p is computed from pd by first randomly choosing a number x from
a uniform distribution in the range [0
...
5pd]
...
21828
...

The parameter pmin used in step I is the minimum average retransmission interval
...
However, it is desirable to enable a participant (an application) to quickly send
a sender report when it starts up and begins to send data
...
5
...

The value of the parameter C is a function of members, senders, and avg_rtcp_size
...
When 0 < 𝑠𝑒𝑛𝑑𝑒𝑟𝑠 <
0
...
Hence, the average retransmission interval of a participant depends on
whether the participant is a sender
...





avg_rtcp_size divided by 25 percent of the RTCP bandwidth, and n is equal to the number of senders
...
size
divided by 75 percent of the RTCP bandwidth, and n is equal to the number of nonsenders
...
25 members, all participants are treated equally
...

To estimate the number of participants, each participant keeps a member table containing the SSRCs
of participants known to it
...
It deletes
the SSRC of a participant and decrements member when it receives a BYE packet from the
participant
...
Similarly, each
participant keeps a sender table and updates the table and the estimate sender each time it receives an
RTP packet from the sender
...
6
...
3 Collision Resolution and Intermedia Synchronization
One of the functions of RTCP is to support collision resolution and intermedia synchronization
...
This identifier is chosen randomly by the
source when the source starts
...
e
...
Although the probability of
a collision is small (less than 10-4 when there are 1000 sources), the fact that it can occur makes it
necessary for all the sources to be able to detect collisions
...

In addition to the above reason, the SSRC identifier of a source also changes when the source restarts
...
This function is provided by RTCP
...
When a source starts, its CNAME
is sent to all participants in its sender reports
...
Intermedia synchronization also requires that the network time-stamp
and RTP time-stamps be included in the RTCP packets of data senders
...
7 Communication in Multicomputer Systems
Like packet switched networks, multihop networks used to interconnect processors in massively
parallel machines also consist of crossbar switches connected by full duplex links
...

2
...
1

WORMHOLE NETWORKS

In a wormhole network, messages are segmented into very small flow control units called flits
...
The buffer is there in order to decouple the input link from the output links
...
7
...
1 Routing and Transmission
Only one flit can occupy a link at each time step; while a message is using a link, another message
that also needs the link must wait
...
Specifically, when the header (i
...
, the first flit) of a message reaches a switch, the switch



Notes by Roshan Pokhrel

34





Real Time System by Jane W S Liu
...
If the output
link is free at the time, the header moves forward on that link to the next switch, leaving the input link
it used to reach the current switch to the second flit in the message
...
On the other hand, if an output link chosen for a
message is in use, the header is buffered and waits at the switch until the output link becomes free
...
The associated input links (i
...
, output links of the corresponding upstream switches) are
not available to other messages
...
The
routing of a message starts when its header leaves the source processor and completes when the
header reaches the destination processor
...
Each link is occupied by one of the message's flits
...
e
...
Thus,
the message "worms" its way nonpreemptively through the network without being queued at any
switch
...
In short,
the message delay through a wormhole network is the sum of its routing time and transmission time
...
The time
required to route a message depends on the overall network traffic and is the nonpredictable
component of message delay
...
7
...
2 Path Selection and Scheduling
To make the network scalable with the number of processors in the system, algorithms used to select
paths for messages are typically simple
...
It is common to use one-bend paths for unicast
messages
...
If the path of every message traverses a column segment first and then a
row segment (or vice versa), there is no deadlock
...

Typically, algorithms used to schedule nonreal-time messages do not prioritize messages
...
According to a greedy algorithm, each message is
routed along a deadlock-free path as soon as it is ready for transmission at the source
...
This intentional
delay to start routing serves a purpose similar to traffic shaping in packet-switched networks, that is,
to reduce the worst-case delay

---