Optimal scheduling of switched FlexRay networks
Authors:
- 1 March 2011
- conference paper
- Published by Institute of Electrical and Electronics Engineers (IEEE)
- p. 1-6
Abstract
This paper introduces the concept of switched FlexRay networks and proposes two algorithms to schedule data communication for this new type of network. Switched FlexRay networks use an intelligent star coupler, called a switch, to temporarily decouple network branches, thereby increasing the effective network bandwidth. Although scheduling for basic FlexRay networks is not new, prior work in this domain does not utilize the branch parallelism that is available when a FlexRay switch is used. In addition to the novel exploitation of branch parallelism, the scheduling algorithms proposed in this paper also support all slot multiplexing options as defined in the FlexRay v 3.0 protocol specification. This includes support for the newly added repetition rates and support for multiplexing frames from different sending nodes in the same slot. Our first algorithm quickly produces a schedule given the communication requirements, network topology and FlexRay parameters, but cannot guarantee an optimal schedule in terms of the bandwidth efficiency and extensibility. Therefore, a second, branch-and-price algorithm is introduced that does find optimal schedules.Keywords
This publication has 8 references indexed in Scilit:
- Switched FlexRay: Increasing the effective bandwidth and safety of FlexRay networks2010
- FlexRay schedule optimization of the static segment2009
- Message Scheduling for the FlexRay Protocol: The Static SegmentIEEE Transactions on Vehicular Technology, 2008
- A GA-based scheduling method for FlexRay systems2005
- Progress in Linear Programming-Based Algorithms for Integer Programming: An ExpositionINFORMS Journal on Computing, 2000
- Branch-and-Price: Column Generation for Solving Huge Integer ProgramsOperations Research, 1998
- Solving binary cutting stock problems by column generation and branch-and-boundComputational Optimization and Applications, 1994
- Decomposition Principle for Linear ProgramsOperations Research, 1960