FlexRay Switch Scheduling - A Networking

Concept for Electric Vehicles

Martin Lukasiewycz, Samarjit Chakraborty Paul Milbredt
TU Munich, Germany AUDI AG, Germany
{martin.lukasiewycz, samarjit.chakraborty}@rcs.ei.tum.de paul.milbredt@audi.de

Abstract—It is projected that the communication data volume

in electric vehicles will significantly increase compared to state- CC0 (Communication Cycle) CC1 ··· CC63
of-the-art vehicles due to additional functionalities like x-by-
wire and safety functions. This paper presents a networking
concept for electric vehicles to cope with the high data volume
in cases where a single FlexRay bus is not sufficient. We present Dynamic
a FlexRay switch concept that is capable of increasing the Static Segment Symbol Network
Segment Window Idle Time
effective bandwidth and improving the safety of existing FlexRay
buses. A prototype FPGA implementation shows the feasibility
of our approach. Further, a scheduling approach for the FlexRay Slot 1 Slot 2 Slo n
Slot
switch that obtains the optimal results based on Integer Linear payload payload ··· payload
Programming (ILP) is presented. Since the ILP approach be-
comes intractable for real-world problems, we present a heuristic
three-step approach that determines the branches of the network, Fig. 1. The FlexRay communication protocol. Each communication cycle
performs a local scheduling for each node, and finally assembles contains a static segment that comprises a set of equally sized slots.
the local schedules into a global schedule. Test cases and an entire
realistic in-vehicle network are used to emphasize the benefits of
the proposed approach.
The FlexRay communication is organized in 64 cycles,
I. I NTRODUCTION as illustrated in Figure 1. Each cycle is divided into four
segments of configurable duration: (1) The static segment
Next generation electric vehicles will radically change the enabling a guaranteed real-time transmission of critical data,
design paradigms in the automotive network domain. For the (2) the dynamic segment for low-priority and event-triggered
sake of simplicity, the legacy Control Area Network (CAN) [1] data, (3) the symbol window used to transmit special symbols,
buses shall be replaced by a homogeneous core network. A and (4) the network idle time used to perform a clock synchro-
strong candidate for this network is the standardized FlexRay nization. The focus of this paper is put on scheduling the static
protocol [2] that is tailored to the automotive domain. How- segment. The static segment is made up of n equally sized slots
ever, even current top-of-the-range cars already contain one where each slot is uniquely assigned to one node (or none).
FlexRay bus and several CAN buses such that the entire One node, however, may occupy more than one slot. Each
communication data would exhaust the capacity of a single slot consists of a header and trailer segment and a payload
FlexRay bus. One natural answer for this problem would be a segment that is statically configured to carry between 0 and
gateway that interconnects multiple FlexRay buses and, thus, 254 bytes. By a predefined schedule, each slot is filled with
increases the bandwidth of the network. However, this solution messages (also referred to as frames or protocol data units)
comes at a high price: The gateway leads to an additional delay of the applications. The size of each message is fixed and
since multiple FlexRay buses cannot be synchronized and given in bytes as the basic unit. The AUTomotive Open System
messages have to be buffered. This approach goes against the ARchitecture (AUTOSAR) FlexRay Interface Specification [5]
benefits of the time-triggered FlexRay bus and implementing suggests a multiplexing technique using the communication
distributed functions with strict real-time requirements might cycles to increase the utilization of the bus.
be hampered. As a remedy, we propose a FlexRay switch Contributions of the Paper:The proposed FlexRay switch
and a scheduling approach that is capable of increasing the is a central hardware device that is capable of connecting
effective bandwidth without introducing additional delays to multiple FlexRay branches transparently, i.e., a modification of
the communication. the FlexRay bus participants is not necessary. In comparison
FlexRay Protocol: The amount of communication in vehicle with the interconnection of buses using a gateway, the switch
networks is constantly increasing due to the growing number does not require data buffering and also does not introduce any
of safety, comfort, and entertainment functions. Most recently, additional delay to the communication. The proposed switch
several car manufacturers introduced the first FlexRay buses in separates communication branches such that each FlexRay
production vehicles to cope with the high data volume [3], [4]. slot may be used by different nodes concurrently on distinct
The FlexRay communication system [2] has been developed by branches. Hence, this approach increases the effective band-
an industrial consortium to cope with the ever increasing data width of the bus. Moreover, the switch might serve as a central
volume and real-time communication requirements of state- bus guardian, thereby increasing the safety of the network.
of-the-art vehicles. It offers a time-triggered and an event- As a proof-of-concept, the switch is implemented on an
triggered segment, a bandwidth of 10 Mbit/s, and supports Field Programmable Gate Array (FPGA) platform. Experi-
different topologies, i.e., linear bus, star and hybrid topolo- ments show that the prototype meets the FlexRay Electric
gies. Thus, FlexRay is the prospective automotive standard Physical Layer (EPL) Specification [6].
communication system. To capitalize on the advantages of the switched FlexRay, an
978-3-9810801-7-9/DATE11/2011
c EDAA
appropriate topology and scheduling determination becomes r1 r2 r3 r4
necessary. In this paper, we present an ILP approach that
m1 ,m2 m4 , m5 m3
is capable of determining the optimal network topology and
scheduling. Due to the exponential nature of ILP formulations, B1 B2
a heuristic approach becomes necessary to handle problems FlexRay Switch
of realistic size. This heuristic approach is performed in three
steps. The first step determines the network topology, i.e., the
Fig. 2. FlexRay network with four nodes R = {r1 , r2 , r3 , r4 } and a switch
branches. In the second step, the scheduling for each node is separating the bus into two branches B1 = {r1 , r2 } and B2 = {r3 , r4 }.
determined. In the third and last step, the schedules of each The messages M = {m1 , m2 , m3 , m4 , m5 } are scheduled on the network.
node are assembled into a global schedule.
Test cases of various sizes show the benefits of the proposed (a) Scheduling without FlexRay Switch
approach. Increasing the number of branches, significantly de-
creases the number of used slots and, thus, boosts the effective Slot 1 Slot 2 Slot 3
bandwidth. A scenario of a migration from a realistic in- B1 ∪ B2 m1 , m2 m3 m4 , m5 ...
vehicle network consisting of four CAN buses and a FlexRay
bus to a homogeneous FlexRay network is investigated. While (b) Scheduling with FlexRay Switch
a single FlexRay bus does not provide enough bandwidth, the
Slot 1 Slot 2
switch concept with the proposed scheduling approach allows
to determine a feasible schedule. B1 m1 , m2
Organization of the paper: The remainder of the paper m4 , m5 ...
is organized as follows: Section II discusses related work. B2 m3
The FlexRay switch concept and the scheduling problem
definition are presented in Section III. Section IV outlines Fig. 3. Schedules for the network in Figure 2 resulting in (a) three used
the FPGA implementation of the switch. In Section V, an slots without a switch and (b) two used slots by using the proposed FlexRay
exact scheduling approach using ILP is proposed as well as an switch.
heuristic three-step approach. Experimental results including
test cases and a realistic case study are presented in Section VI,
before concluding remarks are made in Section VII. problem that originates from using the FlexRay switch as
proposed in the work at hand.
II. R ELATED W ORK
III. S WITCH C ONCEPT
Today, the most prevailing bus system for in-vehicle com- In the following, the FlexRay switch concept is presented,
munication is the event-triggered CAN [1] which is restricted using a simple example. Additionally, the resulting scheduling
to a bit rate of 1Mbit/s only. A significantly higher bandwidth problem is introduced in a formal description.
with 10Mbit/s is provided by the FlexRay bus [2]. Moreover,
the FlexRay protocol allows a time-triggered communication A. Example
which is necessary for several control functions with real-time To illustrate the benefits of the FlexRay switch in terms of
requirements. In a dual channel mode, the FlexRay protocol an increased bandwidth, Figure 2 is introduced as an example
even allows to double the bandwidth. However, in this case architecture. Here, four nodes are connected to a FlexRay bus
the second channel cannot be used for error correction. On the that is separated into two branches using the proposed FlexRay
other hand, Ethernet [7] might be an alternative to cope with switch. Assuming that the messages m1 ,m2 and m4 ,m5 can be
the high data volume of upcoming electric vehicles. However, sent in a single slot (see Section I for an introduction of the
to ensure real-time properties, special implementations of FlexRay protocol), the schedule without the switch requires
the Ethernet protocol become necessary [8]. Moreover, the three slots as illustrated in Figure 3(a). Using the switch,
electromagnetic compatibility for Ethernet in the automotive the number of used slots is reduced to two by scheduling
domain is not as well researched as the FlexRay bus [6] and the messages m1 , m2 and m3 in parallel as illustrated in
hence Ethernet is only considered for non-critical multimedia Figure 3(b).
applications as a compensation for the cost-intensive Media This approach does not require any modifications of the
Oriented Systems Transport (MOST) [9]. Due to the stan- communication controllers of the FlexRay participants since
dardization of the FlexRay bus for the automotive domain it each branch has a local schedule that entirely meets the
is a strong candidate for upcoming (homogeneous) in-vehicle FlexRay specification. Compared to a solution using a gate-
networks that require a significantly higher bandwidth. way, the switch does not induce any additional delay. More-
A major challenge for the proposed FlexRay switch concept over, a gateway requires buffers to store and forward messages.
is the determination of an efficient schedule. In this paper, Hence, the FlexRay switch is a simple and cheap solution that
we focus on scheduling the static segment. An approach that increases the effective bandwidth while ensuring the real-time
optimizes the static segment with a Genetic Algorithm (GA) is properties of the FlexRay bus. Note that a branch might be
proposed in [10]. The work in [11] introduces an ILP approach cascaded using an active star. This becomes necessary if a
for a proposed custom software architecture. In [12], the branch consists of more than eight nodes as required in the
authors present a Mixed Integer Linear Programming (MILP) FlexRay specification [2].
approach for scheduling messages and tasks in a synchronous
architecture. Recent work on scheduling the static segment is B. Problem Formulation
proposed in [13] and [14] which consider the optimization To benefit from the FlexRay switch, an appropriate topology
of the schedule with respect to cycle multiplexing. However, and a schedule have to be determined. The system require-
these papers do not consider scheduling multiple FlexRay ments are defined as a set of communicating nodes R and a
buses and, therefore, are not applicable to the scheduling set of messages M :
 • The network consists of a set of communicating FlexRay
nodes R. A FlexRay node r ∈ R might be an Electronic host I/F HDT
Control Unit (ECU) or a gateway to other buses. Configuration
• Each message m ∈ M is defined by its size wm ∈ N Module
and repetition rm ∈ {2n |n ∈ {0, .., 6}} (the mes- reset DCM
sage m is sent each rm -th cycle). Given the period clock
of the a message pm , the repetition is determined by
rm = 2max(log2 p ,6) with p being the duration of
pm
Schedule Execution Module
a communication cycle. Each message has exactly one
sender defined by src : M → R and a set of a receivers FlexRay Switch
dest : M → 2R .
The topology and schedule are determined by three tasks: bus driver interface
(1) The determination of the branches B, (2) the packing of
Fig. 4. Block diagram of the FlexRay switch prototype.
messages in the slots S, and (3) the assignment of a slot-id
for each slot σ. Here, B defines the topology and (S, σ) the
schedule:
IV. S WITCH I MPLEMENTATION
• Each branch B ∈ B is a subset of the nodes. Hence, the
following holds: For the prototype of the FlexRay switch, an automotive
testing platform [15] based on an FPGA (Xilinx Spartan 3-
∀B ∈ B : B ⊆ R (1) 1500) with eight FlexRay transceivers was used. The proto-
type switch was programmed in VHDL at register transfer
On the other hand, all branches are disjoint sets and each level (RTL). A detailed introduction is given in [16], in the
resource is on exactly one branch: following the architecture of the switch prototype is outlined.
The behavior of the switch is primarily defined by the con-
∀B, B̃ ∈ B, B = B̃ : B ∩ B̃ = {} (2) figured schedule which controls routing during synchronous
 operation. In the dynamic segment or asynchronous operation
B=R (3) mode, e.g., startup, the switch behaves as a central bus
B∈B
guardian, protecting the branches from faulty nodes. The
switch is divided into several parts as illustrated in Figure 4.
• Each slot S ∈ S contains a set of messages. It holds: The switch configuration might be performed at run time by
the host via the host interface. For this purpose, the Host Data
∀S ∈ S : S ⊆ M (4) Translator (HDT) transforms incoming commands and data
from the platform-specific host interface to the internally used
All messages in a slot have the same sender: format. The Digital Clock Management (DCM) generates the
required 80 MHz clock for an eight times oversampling of the
∀S ∈ S, m, m̃ ∈ S : src(m) = src(m̃) (5) FlexRay transmission rate of 10 Mbit/s. The configuration of
In this paper, we assume an AUTOSAR [5] compliant the switch schedule is performed in the Configuration Module.
packing, i.e., each message is assigned a base cycle bm The Schedule Execution Module is responsible for switching
and offset xm : A message is sent in its slot in each the branches. This module has to implement the FlexRay clock
cycle (n · rm + bm )%64 with bm < rm and n ∈ N0 synchronization to be aware of the global time and the current
at the position xm which is the offset in bytes in a slot. slot-id. For each slot-id i, the module has a matrix Ai that
Depending on the messages in a slot, each slot occupies determines if a slot is forwarded from branch B to branch B̃.
a set of branches determined by the function b : S → 2B The matrix is defined as follows:

1 if ∃m ∈ S, S ∈ Si , src(m) ∈ B, dest(m) ∩ B̃ = {}
as follows: Ai (B, B̃) = 0
 otherwise
b(S) = {B|B ∈ B ∧ B ∩ src(m) ∪ dest(m) = {}} (8)
with
m∈S
(6) Si = {S|S ∈ S ∧ σ(S) = i}. (9)
• For each slot S ∈ S the function σ : S → N determines A major challenge in the implementation of the switch
a slot-id (FRIF SLOT ID in [5]). If two slots share the is the required compliance with the FlexRay EPL [6]: The
same slot-id, the occupied branches have to be disjoint: maximal delay between two communicating nodes is 250ns
which equals 2.5bits in case of a bandwidth of 10Mbit/s. Ex-
∀S, S̃ ∈ S, S = S̃ : σ(S) = σ(S̃) → b(S) ∩ b(S̃) = {} tensive tests revealed that the prototype FPGA FlexRay switch
(7) satisfies this constraint, see [16]. Moreover, a commercial off-
The determination of (B, S, σ) is performed with the goal of the-shelf FlexRay switch should have the same behavior as an
using as few slot-ids as possible. This optimization objective active star.
arises from the fact that there exists a limited number of slot-
ids for each schedule and the number of necessary slot-ids V. S WITCH S CHEDULING
determines the schedulability. This holds, in particular, in a In this paper, we use the industrially accepted
scenario with a high data volume, i.e., in upcoming electric AUTOSAR [5] compliant packing, i.e., each message is
vehicles. Note that additional constraints on S and σ might assigned a base cycle bm and offset xm in a slot as described
become necessary in order to consider synchronized ECUs, in Section III. The base cycle and offset have to be chosen
see [12]. such that two messages never overlap. In this work, we use
the transformation to bin packing. Thus, each message is −mi,l − rB + r̃B,i ≥ −1 (19)
assigned a width wm (the payload) and height
∀ r ∈ R, i ∈ {1, .., imax }, B ∈ B : −rB,i + i ≥ 0 (20)
hm = H/rm (10)
with W being the slot size in bytes and H = 64, i.e., the The objective function (14) of the ILP minimizes the
number of communication cycles. Instead of determining the number of used slot-ids. Here, imax is the minimal number of
base cycle, the goal is now to determine the y-offset ym which slot-ids necessary to solve the problem. This number is either
is determined by the minimal value of the available slots or an upper bound
determined by a heuristic for scheduling without the switch.
ym = lm · hm = t(bm , rm ) · hm (11) The constraints (15) state that each message m is placed in
exactly one slot with slot-id i at the specific level l. By adding
with ⎧ the sizes of the messages and restricting this sum by the size
⎨0, x=0
of a slot, the constraints (16) ensure that the size of each slot
t(x, y) = t( x2 , y2 ), x is even (12)
⎩ x−1 y is not exceeded. The constraints (17) state that each node is
t( 2 , 2 ) + y2 , x is odd assigned to exactly one branch as required in Equation (1)-
Here, lm denotes the level of a message m. Correspondingly, (3). The requirement that a slot-id on a specific branch can at
the base cycle bm is determined as follows: most be assigned to one node as given in Equation (5), is stated
in the constraints (18). Correspondingly to the requirement in
ym Equation (7), the constraints (19) ensure that for each message
bm = t(lm , rm ) = t( , rm ) (13)
hm that is assigned to a slot-id, the sender is using the slot-id on
The offset xm in the slot equals the x-offset in the bin. A the specific affected branch. The constraints (20) state that if a
detailed introduction on this transformation is given in [14]. slot-id is used on a specific branch by any resource, the slot-id
For the sake of completeness, an ILP formulation that solves is allocated for the schedule.
the presented scheduling problem optimally is presented in Solving this ILP, provides a slot-id i and level l for each
the following. However, experimental results reveal that this message m. Placing the elements starting from the highest
exact approach is only applicable to small problems due element to the most left void space in the bin at the level l
to the exponential runtime complexity. Hence, a heuristic results in a feasible solution of the bin packing problem. Each
approach becomes necessary for realistic problems where the bin packing solution is transformed to a slot packing S by
ILP becomes intractable. A three-step heuristic is presented determining the base cycle using the level of each message,
that is capable of delivering competitive schedules as shown see Equations (10) and (13). The slot-id assignment σ is
in the experimental results. deduced from the mi,l variables. The variables rB determine
the topology B.
A. Exact Solution with Integer Linear Programming
The ILP formulation relies on the following binary vari- B. Heuristic Solution
ables: Since the ILP approach becomes intractable for problems
• mσ,l : message m is placed at the level l in slot with of even moderate size, we propose a heuristic approach that
slot-id i provides a set of topologies and schedules for a network
• i : slot with slot-id i is used (imax is defined as the using the FlexRay switch. For the sake of simplicity and
maximal number of slot-ids) extensibility, the heuristic is separated in three steps: (1) The
• rB : node r ∈ R is on branch B ∈ B topology is determined by deducing a set of branches, (2) the
• rB,i : node r ∈ R is using the slot with id i on branch messages are packed into slots, (3) a slot-id is assigned to
B∈B each slot. This multi-step approach has the advantage that
The ILP is formulated as follows: some step might be performed manually, e.g., the topology
 might be already given by replacing an active star device by
min i (14) the proposed FlexRay switch.
i∈{1,..,imax } 1) Topology: The goal of the first step is to determine an
H appropriate set of branches. Here, nodes which have a high
−1
 h
m communication flow between each other shall be on same
∀m∈M : mi,l = 1 (15) branch to reduce the inter-branch communication. For this
i∈{1,..,imax } l=0 purpose, we provide an iterative algorithm that returns a set
of candidate topologies in Algorithm 1.
∀ r ∈ R, i ∈ {1, .., imax }, y ∈ {0, .., H − 1} :

wm · mi, y  ≤ W (16) Algorithm 1 Iterative algorithm to determine a set of candidate
hm topologies.
m∈M,src(m)=r
 1: procedure T(GR (R, E), ω : E → N)
∀r∈R: rB = 1 (17) 2: while |E| > 0 do
B∈B 3: select e with ω(e) = minẽ∈E (ω(ẽ))
 4: E = E\{e}
∀ i ∈ {1, .., imax }, B ∈ B : rB,i ≤ 1 (18) 5: B = wcc(GR (R, E))
r∈R 6: Bcandidates = Bcandidates ∪ {B}
H
7: end while
m∈M,i∈{1,..,imax },l∈{0,.., h −1}, 8: end procedure
∀ B∈B,r∈src(m)∪dest(m),r̃=src(m)
m
:
 test case slots runtime[s] |R| |M |
The algorithm receives the fully-meshed graph GR (R, E) tc1 28 8.2 8 217
for all nodes R and the function ω : E → N which is tc2 58 130 16 464
determined as the data volume between two nodes as follows: tc3 114 362 32 923

ω(e = (r, r̃)) = wm · rHm TABLE I
m∈M
T HE THREE TEST CASES PROVIDED FOR A SCALABILITY ANALYSIS .
(r=src(m),r̃∈dest(m)∨r̃=src(m),r∈dest(m)) G IVEN IS THE OPTIMAL SOLUTION IN CASE A SINGLE F LEX R AY BUS IS
(21) USED AS WELL AS THE REQUIRED RUNTIME . A DDITIONALLY, THE
NUMBER NODES AND MESSAGES ARE GIVEN .
The algorithm iteratively removes the edge e ∈ E with
the lowest data volume (line 3,4). The weakly connected
components (wcc), i.e., the graphs that are not connected, are
determined and the corresponding nodes of each unconnected
graph form a branch (line 5). The obtained topology B is added same color or slot-id, respectively. For the vertex coloring,
to the candidate topologies (line 6). Note that this algorithm we use a heuristic approach in [17]. The used contraction-
generates exactly |R| candidate topologies. The worst-case based Recursive-Largest-First (RLF) algorithm has a worst-
complexity of the algorithm is O(|R|4 +|M |) since the number case complexity of O(|S|3 ).
of edges is in O(|R|2 ), the determination of the weakly VI. E XPERIMENTAL R ESULTS
connected components requires O(|R|2 ), and the function ω
is determined in O(|M |). This section discusses our experimental results based on
2) Slot Packing: We use an iterative heuristic algorithm as three test cases and one realistic case study. All experiments
given in Algorithm 2. were carried out on an Intel Core i5 2.53 GHz with 4 GB
RAM. The FlexRay bus was configured such that the cycle
duration is 5ms and the duration of one static segment is
Algorithm 2 Fast greedy heuristic for slot packing. 4.03ms. The static segment consists of 62 slots with each slot
1: S = {} having a payload of 42 bytes (one byte is reserved for update
2: for m ∈ M do bits).
3: for S ∈ S with ∀m̃ ∈ S : src(m) = src(m̃) do
4: if place(m, S) then A. Test cases
5: continue with next m In order to illustrate the benefits of the FlexRay switch
6: end if scheduling, a set of test cases is first presented. The proposed
7: end for three test cases are sampled from the distribution of message
8: create new S and add it to S lengths and periods as given in the realistic case study of
9: place(m, S) an existing FlexRay bus. The size of messages ranges from
10: end for 1byte to 32bytes and the periods range from 5ms to 320ms,
see [14]. The ratio of multicast messages is approximately
The algorithm starts with an empty set of slots S (line 1). 50%. The number of ECUs and messages are given in Table I.
Each message m ∈ M is tried to be placed subsequently in The data volume of the first test case equals a state-of-the-art
a slot S ∈ S if the sender of the message equals the sender FlexRay bus in the automotive domain. The second test case
of the slot (line 2,3). Here, the function place(m, S) tries to embodies the data volume that is common in a modern in-
place each message m in slot S with the minimal offset and vehicle network. The third test case shall serve as an example
base cycle and returns true if the placing is successful, and of an upcoming electric vehicle network with an increased
false otherwise (line 1). If a message is not placed in any of bandwidth due to x-by-wire and additional safety functions.
the slots in S, a new slot S is allocated, added to S, and the For a very small example with six nodes (|R| = 6) and 42
message m is placed into this new empty slot (line 8,9). messages (|M | = 42), the ILP approach is able to find the
The order of the messages in M is determined lexicograph- optimal FlexRay switch schedule within 1142s. However, the
ically by three attributes that are determined as follows: optimal solution using 8 slots and 2 branches is also found with
the proposed heuristic in 29ms. Moreover, for the proposed test
• messages that affect a higher number of nodes determined
cases, the exact ILP approach failed to deliver results within
by  a reasonable amount of time: The optimization was aborted
|B| (22) after 24 hours. Thus, the ILP approach is only applicable for
B∈B,(src(m)∪dest(m))∩B={} small problems such that a heuristic becomes necessary for
problems of realistic size.
are ordered to the front The optimal results obtained for a network consisting of a
• messages with a lower repetition are ordered to the front single FlexRay bus without the switch are given in Table I.
• messages with a higher payload are ordered to the front Here, the presented ILP approach is applied separately for
This ensures that slots are filled first with messages that affect each sender node and, finally, the results are assembled in
a high number of nodes. Hence, the subsequent packed slots a global schedule. Note that this approach is significantly
affect a less number of nodes such that a parallel scheduling more efficient, since the resulting ILP formulations are more
of these slots is more likely and, thus, bandwidth might be compact and may be solved separately. While the first test
saved. The complexity of this algorithm is in O(|M | · |S|) case allows a FlexRay schedule without a switch, the second
3) Slot Assignment: Finally, each slot requires the assign- test case already results in a utilization of 93% (58/62 slots),
ment of a slot-id. In case the number of slot-ids is minimized, prohibiting almost any scope for substantial further extensibil-
this problem equals the vertex coloring problem for the graph ity. The third test case cannot be scheduled on a FlexRay bus
GS (S, ES ) with (S, S̃) ∈ ES ↔ b(S) ∩ b(S̃) = {}. Each since the required number of slots clearly exceeds the number
pair of slots that share at least one branch cannot have the of available slots.
 tc1 replaced by the proposed FlexRay switch, i.e., the branches
120 are defined by the given topology such that each CAN bus
tc2
forms a branch and the FlexRay bus forms a branch. In this
tc3
slot-ids |{σ(S)|S ∈ S}|

100 case, the proposed heuristic reduced the number of required

slots to 35 and hence the resulting schedule is feasible. Our
last example used two branches, i.e., the (Body,Comfort)-
80 branch and the (Powertrain,Chassis,FlexRay)-branch. Here,
the obtained number of used slots was 45 which is still
60 sufficient, respecting the upper bound of 62 slots.
VII. C ONCLUSION
40 This paper presents a novel concept for upcoming in-vehicle
networks, using a FlexRay switch to increase the safety and
20 effective bandwidth of the network. The prototype FlexRay
switch was implemented on an FPGA and tested extensively
2 4 6 8 in terms of compliance with the FlexRay EPL specification.
In order to benefit from the FlexRay switch architecture,
branches |B| an approach for determining the topology and scheduling of
the network becomes necessary. In this paper, we proposed
Fig. 5. Results of the test cases for a switched FlexRay scheduling with the an exact approach based on ILP and a three-step heuristic
proposed three-step heuristic. For the given bus configuration, 62 slots exist approach. Since the exact approach is intractable for problem
in the static segment.
of realistic size, the heuristic becomes necessary. The heuristic
is capable of delivering competitive results as shown for
branches slot-ids runtime[s]
1 (Powertrain,Chassis,Body,Comfort,FlexRay) 63 1.4 the presented test cases and a realistic case study where it
5 (Powertrain)(Chassis)(Body)(Comfort)(FlexRay) 35 0.28 significantly decreases the number of required slots such that
2 (Powertrain,Chassis,FlexRay)(Body,Comfort) 45 0.25 a feasible schedule may be obtained.
TABLE II R EFERENCES
R ESULTS OF THE REALISTIC CASE STUDY.
[1] CAN, “Controller Area Network,” http://www.can.bosch.com/.
[2] FlexRay Communications System, Protocol Specification Version 2.1
Revision A, FlexRay Consortium, Dec. 2005. [Online]. Available:
http://www.flexray.com
[3] J. Berwanger, M. Peteratzinger, and A. Schedl, “FlexRay startet
The results obtained with the proposed heuristic are il- durch - FlexRay-Bordnetz für Fahrdynamik und Fahrerassistenzsysteme
lustrated in Figure 5. For the first test case, the number of (in German),” in Elektronik automotive: Sonderausgabe 7er BMW,
2008, available at http://www.elektroniknet.de/home/automotive/bmw-
slots is reduced to 18 slot-ids saving 10 slots in the case 7/flexray-startet-durch/.
where four branches are used. The second test case shows [4] G. Linn, W. Sichert, P. Milbredt, and G. Kistler, “Serieneinfhrung
that the number of used slots may be reduced to 28 using five eines weckfhigen FlexRay-Bussystems,” Elektronik Automotive, vol.
branches. The most significant gain is achieved for the third Sonerausgabe Audi A8, pp. 102–104, Februar 2010, in German.
[5] AUTOSAR, Specification of the FlexRay Interface Version 3.0.2, 2008,
test case using eight branches. Here, the number of used slots http://www.autosar.org.
is reduced to 40 allowing a feasible schedule which cannot be [6] FlexRay Communications System, Electrical Physical Layer
obtained without the presented FlexRay switch. The runtime Specification, Version 2.1, FlexRay Consortium, May 2005. [Online].
Available: http://www.flexray.com
of the scheduling for a given approach ranges from 24ms to [7] R. Daoud, H. Amer, H. Elsayed, and Y. Sallez, “Ethernet-based car
113ms for tc1, 35ms to 175ms for tc2, and 77ms to 265ms for control network,” in Proc. of CCECE ’06, 2006, pp. 1031–1034.
tc3. Hence, the heuristic is capable of delivering competitive [8] D. Jansen and H. Buttner, “Real-time Ethernet: the EtherCAT solution,”
results always within less than 1s. This short runtime enables Computing and Control Engineering, vol. 15, p. 16, 2004.
[9] MOST, “Media Oriented Systems Transport,”
an iterative optimization of the FlexRay parameters like the http://www.mostcooperation.com/.
communication cycle duration, slot number, or slot size. [10] S. Ding, N. Murakami, H. Tomiyama, and H. Takada, “A ga-based
scheduling method for flexray systems,” in Proc. of EMSOFT ’05. New
B. Case Study York, NY, USA: ACM, 2005, pp. 110–113.
[11] K. Schmidt and E. Guran Schmidt, “Message Scheduling for the
Finally, a realistic case study of a state-of-the-art entire FlexRay Protocol: The Static Segment,” IEEE Transactions on Vehicular
Technology, vol. 58, no. 5, pp. 2170–2179, 2009.
in-vehicle network is used to emphasize the benefits of [12] H. Zeng, W. Zheng, M. Di Natale, A. Ghosal, P. Giusto, and
the proposed FlexRay switch. The used network consists of A. Sangiovanni-Vincentelli, “Scheduling the FlexRay Bus Using Op-
four CAN buses (Powertrain,Chassis,Body,Comfort) and one timization Techniques,” in Proc. of DAC ’09, 2009, pp. 874–877.
FlexRay bus interconnected by a central gateway. The number [13] M. Grenier, L. Havet, and N. Navet, “Configuring the communication
on flexray: the case of the static segment,” in Proc. of ERTS 2008, 2008.
of ECUs is 56 with a total number of 370 messages that [14] M. Lukasiewycz, M. Glaß, P. Milbredt, and J. Teich, “FlexRay Schedule
are transmitted on the static segment (diagnosis, calibration, Optimization of the Static Segment,” in Proc. of CODES+ISSS ’09,
maintenance data were not considered since they are not 2009, pp. 363–372.
[15] P. Milbredt, A. Steininger, and M. Horauer, “Automated Testing of
critical and are usually scheduled on the dynamic segment). FlexRay Clusters for System Inconsistencies in Automotive Networks,”
If all ECUs are interconnected by a single FlexRay bus using in Proc. of DELTA ’08, Hong Kong, China, 2008.
a cascaded active star topology, an optimal schedule with 63 [16] P. Milbredt, B. Vermeulen, G. Tabanoglu, and M. Lukasiewycz,
slots was obtained, see Table II. This schedule is not feasible “Switched FlexRay Increasing the Effective Bandwidth and Safety of
FlexRay Networks,” in Proc. of EFTA ’10, Bilbao, Spain, 2010.
since the static segment in the investigated scenario has only [17] A. Hertz, “A Fast Algorithm for Coloring Meyniel Graphs,” Journal of
62 slots. Combinatorial Theory, Series B, vol. 50, no. 2, pp. 231–240, 1990.
In order to achieve a feasible schedule, the gateway was