| Response time prediction method for frames on a serial bus -> Monitor Keywords |
|
|
 
Response time prediction method for frames on a serial busRelated Patent Categories: Multiplex Communications, Diagnostic Testing (other Than Synchronization), Determination Of Communication ParametersResponse time prediction method for frames on a serial bus description/claimsThe Patent Description & Claims data below is from USPTO Patent Application 20070189179, Response time prediction method for frames on a serial bus. Brief Patent Description - Full Patent Description - Patent Application Claims
FIELD OF TECHNOLOGY [0001] The present invention relates to a method for predicting the worst case response time for a fixed priority frame in a frame queuing system in a serial bus network, such as a CAN. BACKGROUND [0002] In many applications, serial bus networks are used for communication between digital devices; one example is a CAN network in a vehicle. Further, the communication between these devices is typically associated with specific timing requirements, stating a maximum delay from the time a certain event takes place to the time when a corresponding function is performed. For example, it is normally appreciated if the automatic breaking system (ABS) responds quickly to a sensor signal even when the network is occupied with several other tasks (like engine control, transmission control, etc). [0003] Such timing requirements translate into a maximum response time for frames, i.e. a maximum time period between arrival of a frame transmission request and completed transmission of the same frame. [0004] Consequently, when designing such a network, it is critical to be able to guarantee transmission of messages (frames) within the timing requirements. In order to enable such guarantees, the network is modulated in a software design tool, and maximum response times are predicted. If the network is deemed to be too slow under present circumstances, it will have to be redesigned, or, if possible, the band width of the network bus can be improved. [0005] The mechanism assigning priorities and handling the distribution of frames on a serial bus is referred to as scheduling, and resembles the process of scheduling tasks in e.g. a centralized computer processing system. The design tools mentioned above are based on response time analysis, in short a way to mathematically determine the delay between a request (e.g. for sending a frame on a serial bus) is made and when it is treated. [0006] An algorithm where the task or frame currently being processed can be interrupted by a new request is referred to as a preemptive scheduling algorithm. An algorithm where the current task or frame is completed before a new request is treated is called non-preemptive. [0007] An example of scheduling analysis for preemptive scheduling is given in the article "Finding response times in a real time system" by M. Joseph and P. Pandya, BCS Computer Journal, vol. 29, no. 5, pp. 390-395, Oct. 1986. The analysis was based on the assumptions that the worst case response time for tasks occurs when all types of requests enter the scheduling process simultaneously. [0008] Often, however, a given set of requests will have offset constraints, i.e. different types, of requests will be constrained to execute at fixed offsets in relation to each other. Therefore, the assumption of simultaneous requests results in a pessimistic prediction. [0009] The article "Adding time-offsets to schedulability analysis" by Ken Tindell, published as Report YCS 221, Department of Computer Science, University of York, 1994, presents a scheduling analysis for tasks in a processor allowing for such offsets. Here, tasks which have interrelated time dependencies are grouped together in so called transactions. [0010] While this approach improves the accuracy of the predictions and reduces the pessimism, each task is restricted to have a period that is an integer multiple of the corresponding transaction period. However, when considering frames on a serial bus, frame periods can only be guaranteed to be a multiple of the frame processing period. As the offset of a task is restricted to be shorter than the transaction period, this places severe restrictions on the applicability of the method. [0011] Therefore, despite the prior art put forward above, known scheduling analysis models still fail to provide accurate predictions of frame response times on serial bus in a digital network. [0012] As a consequence, the available computer models of a serial bus network, such as a CAN network, are in general too pessimistic. This overly pessimistic approximation leads to unnecessary redesign, or even implementation of unnecessary band width. [0013] Further, the nodes in a serial bus network may be restricted to only enter a given number of frames into the arbitration process. Such restrictions, normally referred to as node budgets, are imposed in order to allow the node processor to handle other tasks apart from scheduling and transmitting frames. These budgets are not considered in conventional scheduling analysis. SUMMARY OF THE INVENTION [0014] An object of the present invention is therefore to provide a more correct way to estimate delivery times of frames on a serial bus network, and to overcome at least some of the shortcomings of prior art methods. [0015] This and other objects are achieved by a method of the kind mentioned by way of introduction, comprising the steps of: defining the period of the transaction as the least common multiplier (LCM) of the frame periods of the included frames; identifying a set of starting points, representing the latest possible release times for all frames in the transaction having higher or equal priority as said frame; for each starting point (s), determining a maximum duration of a sequence of frames having a higher priority as said frame that can occur starting at this starting point, identifying the next frame instance having a latest possible release time equal to or greater than this starting point, and calculating the difference between the end of said sequence and the arrival time of said frame instance, and selecting the longest of said differences for determining the frame response time. [0016] In order to achieve an analysis that better models the transactions present in the serial bus network, the transaction concept has been redefined compared to prior art, resulting in a different approach when implementing the analysis. According to the invention, the transaction period is longer than the frame periods comprised therein, and is defined as the LCM of the frame periods. As a result, several instances of a frame of a given priority may occur in one transaction, which alters the process of estimating response time. [0017] While conventional estimations are based on one specific instance of a frame, the method according to the invention considers all instances in the transaction. [0018] By adjusting the prior art response time analysis schemes to the conditions of a serial bus network, the method according to the invention provides a more accurate prediction of frame response times in different stages of the processing, enabling a more efficient utilization of the network. [0019] The queuing system can for example be the serial bus of a serial bus network, or a transmit or receive queue connected to this bus. In a complete system response time analysis, several different contributions to the application-to-application response time will have to be considered. [0020] The step of determining the frame response time can include calculating a sum of the longest of said differences and a frame transmission time. [0021] According to one embodiment, the set of starting points is divided into subsets, each being associated with one frame instance, and said difference is then calculated for the starting points in one such subset at a time. This leads to a somewhat different implementation, but the end result remains unchanged. Continue reading about Response time prediction method for frames on a serial bus... Full patent description for Response time prediction method for frames on a serial bus Brief Patent Description - Full Patent Description - Patent Application Claims Click on the above for other options relating to this Response time prediction method for frames on a serial bus patent application. ###  How KEYWORD MONITOR works... a FREE service from FreshPatents1. Sign up (takes 30 seconds). 2. Fill in the keywords to be monitored. 3. Each week you receive an email with patent applications related to your keywords. Start now! - Receive info on patent apps like Response time prediction method for frames on a serial bus or other areas of interest. ### Previous Patent Application: Multiplexing of ds1 traffic across wired and wireless ethernet devices Next Patent Application: System for using cellular phones as traffic probes Industry Class: Multiplex communications ### FreshPatents.com Support Thank you for viewing the Response time prediction method for frames on a serial bus patent info. IP-related news and info Results in 0.13023 seconds Other interesting Feshpatents.com categories: Medical: Surgery , Surgery(2) , Surgery(3) , Drug , Drug(2) , Prosthesis , Dentistry 174 |
 * Protect your Inventions * US Patent Office filing 
PATENT INFO |
|
