# CPS lab 111-1
## 12/14
### Assumptions
1. All devices are schedulable.
2. Switch i has Qi queues and Si scheduled queues.
3. Each link has 3 attributes: transmission rate(speed), propagation delay(d), macrotick(m).
4. There are N critical streams in total, which each stream has three attributes: priority, period, size.
5. Period, size is a range?
### Guarantees
1. Every stream meets deadline.

## 11/16 & 11/30
### System Model for Critical Communication Scheduling
1. Both switches and end-systems are scheduled.
2. We denote the network model as a directed graph G(V,L).
-> Vs:switches, Ve:end-systems, L:links (bidirectional -> directed edge pairs)
3. Each switch has Q queues and Q_st of them are scheduled queues, which has highest priority.
4. Each link has 3 attributes: transmission rate(speed), propagation delay(d), macrotick(m).
5. We denote S as the set of all unicast periodic streams.
6. Each stream has 3 attributes: maximum end-to-end delay(e2e), size(L), period(T).
7. Each stream instance s_[va,vb] on link [va,vb] has corresponding queue number from va, which represents its priority.
8. Each stream consists of N frames and every frame has three attributes:
-> offset(phi), transmission time(len), period(same as the period of stream it belongs to.)

### Current Assumption
1. Clocks are synchronized.
2. All devices are scheduled.
-> Real-Time Traffic Guarantees in Heterogeneous Time-sensitive Networks
4. Non-critical traffic(AVB, Best-Effort) isn't important.
-> Synthesising Schedules to Improve QoS of Best-effort Traffic in TSN Networks
-> Delay Analysis of AVB traffic in Time-Sensitive Networks (TSN)
6. Routing constraints aren't important.
-> Heuristic List Scheduler for Time Triggered Traffic in Time Sensitive Networks
### Scheduling Constraints
##### Frame Constraints
(1) offset >= 0
(2) offset + transmission_time <= period
##### Link Constraints
Frames from two streams over the same link don't overlap on time domain.
##### Stream Constraints
delta: synchronization factor, denoting the worst-case drift between the clocks.
##### End-to-End Constraints
##### Stream Isolation Constraints
Len should also multiplies mt.
Avoid queuing delay and jitter.
##### Frame Isolation Constraints
#### Evaluation
NeSTiNg TSN simulation tool?

## 11/9
### Most of the researches related to TSN: ST class scheduling
#### Differences:
1. Porous scheduling.
2. Optimum routing at the same time.
3. Optimize bandwith allocated for low priorities.
4. Whether time synchronization stands.
#### Keywords left for search
1. Credit-based shaper: for critical class(class A, B)
2. Asynchronous traffic shaper
### Synthesising Schedules to Improve QoS of Best-effort Traffic in TSN Networks
(International Conference on Real-Time Networks and Systems, 2021)
#### Motivation
There are traffic that do not have strict deadlines to meet (not mapped to "schedulued traffic class"), yet achieving an acceptable level of Quality of Service (QoS) for them is expected.
#### Background

1. The critical traffic classes are defined as Classes A and B. Where Class A has a higher priority than Class B. Whereas, the non-critical traffic class is defined as the best-effort (BE) traffic class with the lowest priority.
2. The gates operation follows a pre-defined gate control list (GCL) that repeats periodically defining which gate on the queues should be open at each time slot.
3. The schedule synthesis approaches can be grouped into two branches: (i) Satisfiability Modulo Theorems (SMT) and Optimization Modulo Theorem (OMT), and (ii) heuristics and metaheuristic approaches.
4. The generic constraints of the solution include: frame, link, stream and end-to-end delay timing constraints.
#### System Model (same as the work read in last week)
1. For Best-Effort class, T is the minimum inter-arrival time, e2e is the deadline of BE stream.
2. Each BE frame is assumed to arrive at the start of its period, which in turn generates the worst-case situation for the BE frames.
#### Basic constraints (same as the work read in last week)
(i) frame constraint, (ii) link constraint, (iii) stream constraint(flow trasmission constraint), (iv) end-to-end constraint, (v) stream isolation constraint, and (vi) frame isolation constraint
#### Proposed constraints
Define Slack, which is a time interval after transmission of a ST frame, during which no ST frame can occupy the link’s bandwidth.
1. Porous link constraint: link constraint considering Slack.
2. Slack size constraint: The slack must be greater than or equal to zero but less than or equal to the difference between the frame period and its transmission time.
3. Hop Slacks constraint: total Slack is bounded.
4. Equal Slack constraint: (optional) evenly distribute Slacks on a link.
#### Objective
1. Minimize the offsets of the ST frames. (also the objective of previous works)
2. Schedule the transmission of the ST frames as close as possible to their deadlines.
3. Sparse schedule: Adjust the ST offsets implicitly by maximizing the sum of slacks between subsequent frames, that are scheduled on the same link.
4. Evenly Sparse Schedule

## 11/2
### Scheduling Real-Time Communication in IEEE 802.1Qbv Time Sensitive Networks
(International Conference on Real-Time Networks and Systems, 2016)
#### Introduction & Definition
1. Queue has a timed gate associated to it enabling or disabling the transmission of frames according to a predefined static schedule.
2. If multiple queues are opened at the same time, the queue priority determines which of the queues is allowed to forward frames.
3. Parameters that affect the timing properties of network flows.
(1) Device capabilities: if devices are scheduled or not.
(2) Queue configuration.
4. We focus on deterministic networks with scheduled end-systems and switches. **-> assumption 1**
5. We focus on creating schedules for the timed-gates of scheduled queues.
6. We denote the queue configuration by the tuple G(Q) = ⟨א, אtt, אprio⟩, where א is the total number of queues per port, אtt is the number of queues operating as scheduled (TT) queues, and אprio is the remaining number of priority queues.
7. The scheduled queues always have the highest priorities of all queues. **-> assumption 2**
8. Scheduled traffic is defined as having requirements on the maximum end-to-end latency as well as minimal jitter constraints, i.e., each periodic instance of the communication flow has to arrive at the same instant in time.
9. We model the network as a directed graph G(V , L), where the nodes (switches and end-systems) are the set of graph vertices (V) and the links between nodes are represented through the graph edges.
10. A physical link [va , vb ] is characterized by the tuple ⟨[va, vb].s, [va, vb].d, [va, vb].mt, [va, vb].c⟩, where [va , vb ].s is the speed of the link, [va , vb ].d is the propagation delay on the medium, [va , vb ].mt is the macrotick of the link, [va , vb ].c represents the number of available queues in the device.
11. A flow from sender to receiver is characterized by the tuple ⟨si.e2e, si.L, si.T ⟩, denoting the maximum allowed end-to-end latency, the data size in bytes, and the period of the flow, respectively.
12. An instance of a flow si∈S routed through link [va,vb]∈L is denoted by s[va,vb]. We denote the queue for the given flow instance in the egress port as a variable s[va,vb].p.
#### Scheduling Constraints (Basic Deterministic Ethernet Constraints)
1. Frame Constraint. The frame offset of any frame scheduled in the network has to be greater than or equal to 0. Additionally, the entire transmission window (offset plus frame duration) has to fit within the frame period.
2. Link Constraint. No two frames that are routed through the same physical link in the network can overlap in the time domain.
3. Flow Transmission Constraint. The propagation of frames of a flow must follow the sequential order along the routed path of the flow. -> The constraint imposes that a frame can only be scheduled on a subsequent link [vx , vb] after the complete reception on the previous link [va , vx].
4. End-to-End Constraint. The maximum end-to-end latency constraint.
#### Scheduling Constraints (802.1Qbv Constraints)
1. Egress Interleaving. (case c in this work)
2. Flow Isolation Constraint. if a frame of a given flow has entered a queue, no frame of another flow may arrive at the queue until all frames of the previous flow have been fully dispatched.
3. Frame Isolation Constraint. **(Used in this work, relaxed from previous constraint)** -> There are only frames of one flow in the queue at a time.
#### Aim of the scheduling
Find values for all individual frame offsets and queue assignments in each respective egress port of flows routed along the network such that the set of constraints are met.
#### Optimization Objective
Sum of the number of scheduled queues used per egress port.

## 10/19
### Security-Aware Mapping for CAN-Based Real-Time Distributed Systems

#### Questions
1. How to calculate path latency?
2. How to calculate response time?
#### Constraints
1. Allocation and Packing
(1) A task is allocated to exact one ECU.
(2) A signal from task i to task j is packed into exact one message from ECU k if task i is allocated to ECU k and task j isn't.
(3) The period of a signal is equal to the period of the message in which the signal is packed into.
(4) Each branch of a multicast signal is mapped to the same message.
(5) Exactly one branch of a multicast signal adds its length to the message.
2. End-to-End Latency
(1) Task response time.
(2) Total length of a message.
(3) Message response time.
(4) Signal response time = (I) reponse time of the message it's allocated to or (II) 0 (source ECU = target ECU).
(5) Path latency.
### Security-Aware Mapping for TDMA-Based Real-Time Distributed Systems
#### The switch uses a TDMA-based model for scheduling, in which each time slot in the schedule can be assigned to one message. Several time slots form a cycle, and the network switch repeats the same scheduling sequence after each cycle.
#### Definition
1. (1)Sending Time -> (2)Receiving Time -> (3)Key Releasing Time -> (4)Key Receiving Time
2. (2)-(1)=transmission delay
3. (4)-(2)=authentication delay
4. (4)-(1)=latency
#### Task Allocation and Priority Assignment
1. Tasks are distributed as evenly as possible.
2. The tasks that appear in more time-critical paths are assigned with higher priorities.
3. During simulated annealing, two random operations may be performed.
(1)The first one is to allocate a task to another node.
(2)The second one is to switch the priorities of two tasks.
#### Signal Mapping
1. It's assumed that each signal is packed into its own message in this work.
2. In this work, if a signal is time-critical (the signal is on at least one time-critical path), then its message is assigned as a synchronous message; otherwise, its message is assigned as an asynchronous message.
#### Network Scheduling
1. A scheduler may schedule each sender’s first packet within an interval.
2. A scheduler may try to schedule a packet earlier to ensure that it is received before the end of the interval. As a result, the sender can release keys one interval earlier without violating the security requirement.
3. A scheduler may minimize the worst-case transmission delay of packets.
4. The scheduler schedules synchronous messages as early as possible and asynchronous messages as evenly as possible.
#### Worst-Case Transmission Delay Analysis
1. For synchronous message, a round is a time period whose length is the least common multiple of p and q and we only need to consider two rounds for the worst-case transmission delay of the packet arrival pattern.
2. For unsynchronous message, if the worst-case transmission delay happens when packet Pi is assigned to time slot Sj , then
(1) One of Pi itself and the packets arriving before Pi must have just missed a time slot.
(2) There must be no unused time slot between the arriving time of the packet just missing a time slot and the starting time of Sj .

## 10/12
### Hardware Virtualization and Task Allocation for Plug-and-Play Automotive Systems
#### Solving task allocation problems on a hypervisor-based platform for plug-and-play automotive systems.
#### Phase 1 (scenarios at the dealership)
1. Inputs
(1) A set of tasks where each task is associated with its period T and excution time C.
(2) A set of operation systems.
2. Outputs
(1) The allocation of each task.
(2) The priority of each task.
(3) The schedule of the OS hypervisor.
3. Constraints
(1) Different tasks on the same operating system should have different priorities.
(2) The worst-case response time of each task <= the period of the task.
4. Algorithm
(1) A task with a smaller period has a higher priority.
(2) A task with a smaller period will be processed first to be allocated to a operating system (with smallest worst-case response time for the task).
(3) A step size (delta_j) is defined as the minimum period of tasks allocated to operating system w_j.
(4) Select the operating system with the minimum accumulated step size and assign the next lambda time units as a new partition to the operating system when scheduling.
(lamda: minimum allowed length for a partition)
(5) Increase the accumulated step size of the operating system by one step size after (4).
5. No objective in Phase 1.
#### Post-Processing Algorithm
1. Maintain a lookup table for Cjk.
2. Cjk is the maximum allowed execution time of a task if
(1) The task is allocated to w_j.
(2) The task has the period Theta_k.
(3) The task has the lowest priority on w_j.
#### Phase 2 (during driving)
1. Similar to Phase 1, but the objective is to maximize the number of allocated tasks.
2. When allocating task t_i, find Cjk in the lookup table which
(1) Period k <= period T_i and it has to be as large as possible.
(2) Find largest Cjk.
(3) Task t_i is allocated to w_j only if Cjk >= Ci (execution time of task t_i).
-> All elements corresponding to w_j in the lookup table is set to 0.

## 9/28 & 10/5
### Contract-Based Integration of Automotive Control Software
#### The approach derives system-level timing constraints from the domain knowledge of component designers.
#### Definition:
1. An implementation of a component consists of a set of behaviors and ports, also called interfaces.
2. Each behaviour assigns values to output ports y based on inner states and the values on the input ports u.
3. The sampling ports s and actuation ports z provide a link to the physical environment.
4. x is a placeholder for any port while x addresses the jth interface of the component c.
5. Each occurrence of a read, write, sampling or actuation operation at the respective interface x is called an event Xk.
6. Xk = (Value-k, Tag-k, Timestamp-k).
7. A tag describes the time of the occurrence of the event.
8. Logical timestamps are derived from the tags of sampling events and propagated in the system according to a set of rules.
9. A signal x= x1,...,xn is an ordered set of all events that occur at a single interface. To each signal a set of signal paths ex={e1x,...,enx} can be attributed.
10. The logical timestamp is the sum of the tag tkx and the set of algorithmic delays dkx, which exist in the signal path.
11. The logical sampling rate Δtx is the nonzero difference of the logical timestamp of two consecutive read events in a signal.
12. The logical band limit lx is a measure for the highest frequency fmax in which a signal x can have an amplitude that is nonzero. lx = 1/(2fmax)
13. The logical data age ax of a signal is the difference between the tag t and the logical timestamp tx.
#### Assumption:
1. Data age: for all events k in a signal x(i,j), amin ≤ ak_x(i,j) ≤ amax.
(This type can be used to constraint the input delays of control functions.)
2. Data Synchronicity: for all events k,s in a signal pair (x(i,j),x(i,h)), amin ≤ ak_x(i,j) − as_x(i,h) ≤ amax
3. Logical Sampling Rate: for all events k in a signal x(i,j), Δtmin ≤ Δtk_x(i,j) ≤ Δtmax
4. Logical Band Limit: for all events k in a signal x(i,j), lmin ≤ lk_x(i,j) ≤ lmax
5. No-Aliasing: for every (output/input) pair y(k,l), u(s,t) in the signal path ex(i,j), ly(k,l) ≥ Δtu(s,t).
(Aliasing occurs when the logical band limit of an output signal is larger than the logical sampling rate of the input signal.)
#### Guarantee:
1. Delay: tky(i,j) = tku(i,k) + dy(i,j)
2. Resampling: for the output signal y(i,j), l_y(i,j) (logical band limit) = 1/(2fmax_y(i,j)) (band limiting frequency)

#### System-level analysis:
1. The signal paths are determined at the system-level using a graph-based (directed graph) analysis methodology.
2. At construction of this graph starts with the definition of all interfaces as nodes.
3. Then for each communication between two interfaces an edge is added.
4. Edges are added for intra-component dependencies. These are derived from the linking information that is included in the guarantees of the timing contracts.

### Contract based Design of Symbolic Controllers for Vehicle Platooning
#### Assumption:
for a line of m cars on a straight or circular road in
1. 0 <= V1(t) <= Vmax
2. for i = 2,...,m, di' = Vi - Vi-1
(di <=0 is the relative distance of the i-th car and the (i-1)-th car)
4. MVi' = Fi - f0 - f1Vi - f2Vi^2 (Fi is a control input)
5. V0 = Vm on the circular road.
#### Guarantee:
for i = 2,...,m:
1. 0 <= Vi(t) <= Vmax
2. di(t) <= 0

#### Results:
1. The vehicles do not distribute uniformly on the road.
2. The vehicles with larger sampling period need to keep a larger distance.

### Scenario-Oriented Contract Based Design for Safety of Autonomous Vehicles

#### Generate 3 contracts base on 3 scenarios of collision and test it on these 3 scenarios and other 3 more complicated scenarios.
#### Assumption:
For two cars which are front car (Cf) and rear car (Cr) in the the same:
1. 𝐶𝑓 should accelerate if the distance between 𝐶𝑓 and 𝐶𝑟 is less than 30 m.
2. 𝐶𝑟 will reduce its speed when the minimum distance between 𝐶𝑟 and 𝐶𝑓 approaches to 30 m.
3. 𝐶𝑟 will brake while the distance between 𝐶𝑓 and 𝐶𝑟 is less than 10 m.
#### Guarantee:
1. Safe distance of 10 m should be maintained between 𝐶𝑓 and 𝐶𝑟.
2. Safe distance of 30 m should be maintained between 𝐶𝑓 and 𝐶𝑟?

### Linear Temporal Logic
###### https://people.eecs.berkeley.edu/~sseshia/fmee/lectures/TemporalLogicIntro.pdf
1. Globally p (G p): p holds at all states.
2. Eventually p (F p): p holds at some state along the path.
3. Next p (N p): p holds at the next state of the starting state of a path.
4. p Until q (p U q):
(1) q is true in some state reachable from s.
(2) p is true in all states until q holds.

## 9/7
### Taming Dr. Frankenstein: Contract-Based Design for Cyber-physical Systems
1. Component: implementations and contracts
2. Implementation: a set of ports(variables) and a set of behaviors(runs)
3. Contract: a pair of assertions, which express its assumptions and promises
4. Assertion: a set of behaviors over ports
5. An implementation M satisfies an assertion E whenever they are defined over the same set of ports and all the behaviors of M satisfy the assertion, i.e., when M ⊆ E.
6. An implementation of a component satisfies a contract whenever it satisfies its promise, subject to the assumption.
7. For E an assertion, and P′ ⊆ P a subset of its ports, E is said to be P′-receptive if and only if for all runs σ′ restricted to ports belonging to P′, there exists a run σ ∈ E such that σ′ and σ coincide over P′
8. Composite contract: A = (A1 ∩ A2) ∪ ¬(G1 ∩ G2), G = G1 ∩ G2
9. C = (A, G) dominates C′ = (A′, G′), written C ≼ C′, if and only if A ⊇ A′ and G ⊆ G′
10. C1 ⊓ C2 = (A1 ∪ A2, G1 ∩ G2) , C1 ⊔ C2 = (A1 ∩ A2,G1 ∪ G2)
11. For a contract C and an implementations M with profile π = (u, c) , we say that C is consistent if G is u-receptive, and compatible if A is c-receptive
12. Verification: Horizontal contract -> Vertical contract