PowerPoint 演示文稿

PowerPoint 演示文稿

Message Sequence Chart Lei Bu MSCs Message sequence chart (MSC) is a graphical and te xtual language for the description and specification of the interactions between system components. The main area of application for MSCs is as overvie w specification of the communication behavior of re al-time systems, in particular telecommunication sw itching systems. MSCs represent typical execution scenarios, providi ng examples of either normal or exceptional executi ons of the proposed system.

The MSC standard as defined by ITU-T in Recomm endation Z.120 (International Telecommunication U nion - Telecommunication Standardization) basic MSCs and High-Level MSCs. Keyboard Send Key Click Click(digit) Click Sent Retrieve(digit) number Call(number) signal signal not busy msc call_set_up mobile_1

base_1 up_call_req call_ack down_resp network up_call_req base_2 down_req call_ack down_resp up_call_resp mobile_2 down_req up_call_resp

CPU mem req ack CPU Mem req nack addr val MSC 1 MSC 2 Concurrency modeling

Depicts concurrently executing processes (the vertic al lines). Processes communicate via a explicit message passi ng (instead of shared variables). Realistic MSCs will also contain data attributes as p art of the exchanged msg Message Attributes req ack Addr(a) v := lookup(a) val(v) CPU Mem Internal Computations

req Internal Action ack Addr(a) val(v) CPU v := lookup(a) Mem Basic MSCs A basic MSC describes exactly one scenario, which consists of a set of processes that run in parallel and exchange messages in a one to one, asynchronous fa shion MSC visual notation P1

P2 P3 M1 M2 M3 M4 M5 M6 MSC Textual form msc MSC; inst P1: process Root, P2: process Root, P3: process Root; instance P1; out M1 to P2; in M5 from P2; in M6 from P3; endinstance; instance P2; in M1 from P1; out M2 to P3;

out M3 to P3; in M4 from P3; out M5 to P1; endinstance; instance P3; in M2 from P2; in M3 from P2; out M4 to P2; out M6 to P1; endinstance; endmsc; P1 M1 M5 P2 P3 M2 M3 M4

M6 Visual order semantics s M1 r s r M2 r M3 s M4 s r r r

M5 s M6 s P1 P2 M1 M5 P3 M2 M3 M4 M6 A bMSC is a tuple where

P is a finite set of processes; E is a finite set of events corresponding to sending a message an d receiving a message. M is a finite set of messages. Each Message in M is of the form where e, ecorresponds to sending and receiving the message res pectively, and g is the message name which is a character string. is a labeling function which maps each event eto a process L(e) V is a finite set whose elements are a pair (e,e) where e, eand e precedes e, which is corresponding to a visual order; The semantics of a bMSC essentially consists of sequ ences (of traces) of messages that are sent and receive d among the concurrent processes in the bMSC. The order of communication events (i.e.message sendi ng or receiving) in a trace is deduced from the visual partial order determined by the flow of control within each process in the bMSC along with a causal depend

ency between the events of sending and receiving a m essage. We use event sequences to represent the traces of bMS Cs which are corresponding to the untimed behavior of bMSCs. Any event sequence is of the form , which re presents thattakes place after for any i (). Let be a bMSC. An event sequence is a trace of D i f and only if the following conditions hold: All events in E occur in the sequence, and each even t occurs only once, i.e. {}=E and for any i,j (); an d satisfy the visual order defined by V, i.e. for any , if () . Visual semantics Sends before corresponding receives.

Events on the same process line execute in order of appearance, from top to bottom. Visual order (wysiwyg) If some event (send, r eceive) is higher on th e line than another, it comes first. Sends precede matchi ng receives. P1 M1 M5

P2 P3 M2 M3 M4 M6 Visual order (wysiwyg) s M1 r s M2 r M3 r M4 r r

P2 M1 s s r M5 s M6 P1 s M5 P3 M2 M3 M4 M6 Causal Order and Races Causality: Sends before matching

receive. P1 Controlability: Receive or sends before sends of same process. FIFO order: Two receives on the same process sent from the same process. M1 M5 P2 P3 M2 M3 M4 M6 Races: check if every pair of events ordered by the visual order appears in the transitive closure of the causal order. Races

P1 M1 M5 P2 P3 M2 M3 M4 P1 P2 M1 M6 M5 P3 M2 M3 M4

M6 Finding races: P1 P1 P2 P3 P2 P3 M1 M1 M2 M2 M3 M3

M4 M5 M4 M6 Rules: order between - receive and a later send. - two sends from same process. - send and corresponding receive. - fifo order. M5 M6 Causal Order s M1 r s M2 r M3

r M4 r r M6 s M1 s s r M5 P1 s M5

P2 P3 M2 M3 M4 M6 Calculating the transitive closure Structure (E, R). E Events, R E E. R* The transitive closure. Defined as follows: a R*b if there is a sequence x1 x2 xn where a=x1, b=xn, and xi R xi+1 for 1i

Models a single scenario and states its possible execution in t he system implementation. How could we use MSCs to model the behavior of a concurr ent system ? One attempt is to describe the system behavior as a graph of MSCs. Each node of this graph is a MSC. We call such graphs as Message Sequence Graphs (MSG). P1 P2 P3 P2 P3

P2 P3 approve connect P1 P1 P2 P3 fail report P1 req_service A

B Execution: ACACD approve connect connect fail report connect fail Req_service report fail report Req_service C D MSG - Visually

req M1 M3 M2 ack addr val nack Choice and Concatenation Choice of scenarios at a certain point in system execution mo deled by several outgoing branches

M1 M2 and M1 M3 Concatenation of MSCs (by following the edges in the MS G) produces infinite execution traces. Client Server More on concatenation Synchronous concatenation All processes synchronize at the end of each MSC (a nod e of the MSG) For any edge M1 M2 All events in M1 happen before all events in M2 Costly to implement since the natural control flow in a pr ocess is disrupted by the termination of a MSC (requiring handshake with other processes).

Synchronous concatenation r1 s1 s1 < r1 < s2 < r2 r2 s2 An alternative concentation Asynchronous concatenation If M1 M2 is an edge in the MSG, then concatenate M1 and M2 process by process If a process finishes its role in M1 ahead of others, it can start executing M2 Amenable to efficient distributed implementation. Asynchronous concatenation r1 s1

s1 < r1 s2 < r2 s1 < s2 Is r1 < s2 ?? r2 s2 Hierarchical MSC (HMSC) Improves MSGs by incorporating hierarchy. A graph, each node of which is: a Message Sequence Chart, or a HMSC Clearly a MSG can appear as a node of HMSC. Different nodes in the graph can be labeled by the same HM SC The HMSC is like a subprogram which is invoked in vari ous contexts.

HMSC example Th1 CPU Th2 CPU-Mem MSG CPU-Mem MSG can be invoked in another context involving thread Th2. Th1 CPU data MSG - Recap req M1

M3 M2 ack addr val nack High-Level MSCs msc call_blocking References can be to basic MSCs or high-level MSCs start point end point reference branching looping parallel (not shown) guards (not shown) Single telecom. feature may have >100 basic MSCs

structured through 3 levels of high-level MSCs initiate_call call_set_up call_proceeding terminate_call call_refused Extended/Related Models UML Sequence Diagram Live Sequence Chart Timed MSC In-Line Expressions Structuring event behaviour within an MSC msc MyLife

In-line expressions: alternative parallel optional loop exceptional Operands: non-deterministic choice may be guarded events interleaved with those outside expression infra call_req mobile_1 t(5) alt when idle call_ack t

call_accept otherwise t req_refused mobile_2 Time Constraints/Data Real-Time Constraints Message Contents Data Dependent Behaviour Time Constraints: absolute (tracing) relative (specification) single point, intervals constrain regions Data: static variables - parameterises MSC - global to MSC - also instances, etc. dynamic variables

- local to instance - assigned in actions - declared MSC Document underspecification - dont care values msc call_expiration(time_out: time) base network manager initiate ready x := f(_, 5) set_up(time_out + 3) expired (z1, _, x) terminate @10:00

[5, 10] Instance Decomposition Splitting an Instance Into Constituent Processes msc call base network decomposed as network_call manager initiate ready set_up Hierarchical view of processes Instance structure defined in enclosing MSC Document Internal messages hidden in upper view msc network_call

base_handler manager_handler ready initiate initiate_set_up set_up LSC Scenario-based Stories about the system MSCs: (Message Sequence Charts) inter-object behavior (one story for all relevant objects) But, we need richer requirements may/must; can/always;

fragmental and overlapping scenarios; anti-scenarios; etc. Live sequence charts (LSCs) LSCs: Breathing Life into Message Sequence Charts (Damm & Harel, 98 ) A natural extension of classical MSCs, with modalities (universal/existential, hot/cold, etc.) and structure (subcharts, conditionals, loops, etc.) Basic form of an LSC prechart (if) main chart (then)

Subcharts Loops Cold conditions enable control structures Hot conditions enable anti-scenarios: MSG - Recap req M1 M3 M2

ack addr val nack M1 req Mem.busy Mem.busy CPU Mem M3 M2 ack nack addr val

CPU Mem CPU Mem A Universal chart Mem.busy 1. Mem.busy is the activation condition (AC) 2. If the AC holds, then this chart must be executed. nack 3. But the AC need not be true in every execution. CPU Mem

Pre-charts The trigger of a universal chart need simply be an activation condition. Can be an activation message: when it is received the chart is required to be activated. Can even be another full blown chart (a pre-chart). This chart can contain msg send/recv, conditions. Once the pre-chart is executed, the universal chart is required to follow. Example of Pre-chart CP U req

Mem Mem.busy = true Pre-chart Concatenation CPU Mem nack Univ. chart Timed extension Scenario-based specifications (SBSs) offe r an intuitive and visual way of describin g design requirements.

Message sequence charts(MSCs) UML interaction models For real-time systems, timing constraints are introduced into SBSs to describe tim ed behaviors. SBSs SBSs consist of UML sequence diagrams (SDs) and UML 2.0 interaction overview diagrams (IODs). We use the SD to describe exactly one scenario without al ternatives and loops, and the IOD which combines refere nces to SDs to describe sequential, iterating and non-det erministic executions of SDs. Case Study ATM Motivation

Describing timing constraints related to the sep aration in time between two events. timers , interval delays, timing marks To describe timing constraints which are about the relation among multiple separations in time between events. Checking SBSs for timing consistency To check more properties properties about the accumulated delays on the trace s of systems

Timing Constraints The timing constraints enforced on SD s describe the relations among multipl e separations in time between events. a c0(e0-e0)+c1(e1-e1)++cn(en-en) b separation separation separation Timing Constraints The timing constraints enforced on SDs d escribe the relations among multiple sep arations in time between events. a c0(e0-e0)+c1(e1-e1)++cn(en-en) b The timing constraints enforced on IODs

describe the timed relations between two events from different sequence diagrams . a e-e b Reachability analysis To check if a given scenario of an SBS is reachable alo ng a behavior of the SBS with regard to all the timing constraints. Constraint conformance anal ysis To check if the given several scenarios, which occur co nsecutively in the behavior of an SBS, satisfy a given ti ming constraint. a c0(e0-e0)+c1(e1-e1)+ +cn(en-en) b Bounded delay analysis

To check if the separation in time between two given e vents, which may occur in different sequence diagram s, is not smaller or greater than a given real number in any behavior of an SBS. Consistency Checking Existency Checking UK USA MSCs in the Lifecycle RMTR air_in taxi_in taxi_out MSCs Used Formally Throughout Lifecycle

air_out System/Integration Testing ITU, ETSI Standards UK USA RMTR UK air_in USA RMTR air_in taxi_in taxi_in

Test Generation taxi_out air_out START MEETING always takes too long PRESENT ARGUMENTS taxi_out COMPANY X OPINION air_out COMPANY Y OPINION MOTOROLA OPINION

AGREE WITH MOTOROLA SUPERIOR ARGUMENT THROW OUT IDEA where the real work is done COFFEE BREAK - PROPOSE DECISION MEETING AGREES well deserved

LUNCH System Requirements Automation Requires Formal Languages TTCN UK UK USA COMPANY X OPINION air_in THR OW OUT IDEA RMTR

START MEETING COMPANY Y OPINION AGREE WITH MOTOROLA taxi_in SUPERIOR ARGUMENT COFFEE BREAK where the real work is done taxi_out PROPOSE DECISION

air_out Test Generation MEETING AGREES LUNCH RMTR taxi_in always takes too long MOTOROLA OPINION - USA air_in

START MEETING PRESENT ARGUMENTS taxi_out air_out always takes too long PRESENT ARGUMENTS COMPANY X OPINION COMPANY Y OPINION MOTOROLA OPINION THR OW OUT IDEA well

deserved AGREE WITH MOTOROLA SUPERIOR ARGUMENT COFFE E BREAK where the real work is done Box Testing PROPOS E DECISION MEE TING AGR EES LUNCH

Box Requirements well deserved TTCN Code Generation START MEETING always takes too long PRES ENT ARGUMENTS SDL Design Specification and Description Language COMPANY X OPINION COMPANY Y

OPINION MOTOROLA OPINION THROW OUT IDEA - AGREE WITH MOTOROLA SUPERIOR ARGUMENT COFFEE BREAK where the real work is done PROPOSE DECISION MEETING AGREES

LUNCH well deserved Code Generation Code MSC Uses Formality Enables Useful Tool Support UK USA Verification & Validation: feature interactions race conditions tracing RMTR air_in taxi_in

taxi_out air_out Requirements V&V UK START MEETING AGREE WITH MOTOROLA SUPERIOR ARGUMENT where the real work is done COFFEE BREAK - RMTR

taxi_in COMPANY Y OPINION MOTOROLA OPINION THROW OUT IDEA USA air_in always takes too long PRESENT ARGUMENTS COMPANY X OPINION SDL Tracing taxi_out

air_out PROPOSE DECI SION MEETING AGREES LUNCH UK well deserved USA RMTR START MEETING air_in always takes too long

PRESENT ARGUMENTS taxi_in taxi_out air_out COMPANY X OPINION SDL Verification COMPANY Y OPINION MOTOROLA OPINION AGREE WITH MOTOROLA SUPERIOR ARGUMENT THROW OUT

IDEA where the real work is done COFFEE BREAK - PROPOSE DECISION MEETING AGREES USA RMTR air_in taxi_in taxi_out air_out START

MEETING TTCN Generation always takes too long PRESENT ARGUMENTS COMPANY X OPINION COMPANY Y OPINION MOTOROLA OPINION THROW OUT IDEA - AGREE WITH MOTOROLA

SUPERIOR ARGUMENT COFFEE BREAK where the real work is done PROPOSE DECISION MEETING AGREES LUNCH Design Verification: model checking SDL upholds MSCs well deserved

LUNCH UK Tracing: model validation application code validation test validation well deserved Test Generation: conformance testing test purposes (one-2- many) test specification (one-2-one) Summary MSC is a rich language suitable for requirements specification many uses across lifecycle

engineer friendly language used in telecom standards Good tool support getting more sophisticated industrial use integrated with SDL, TTCN tools Standardisation Continues interesting problems to work on good forum for insight, new ideas learn latest methods/technology

Recently Viewed Presentations

  • EH&amp;S Coordinator

    EH&S Coordinator

    Lisa Coen, x.2107 Celina Gauthier, x.2104 . SPCCPLAN (Oil) Spill Prevention, Control & Countermeasures. SPCC: Oil Spill Prevention. Requires Management address oil spill prevention and containment of oil discharges via . written procedures, work practices, and .
  • Unsaturated Hydrocarbons Alkenes

    Unsaturated Hydrocarbons Alkenes

    Structure Of Alkenes (Olefines) They are unsaturated hydrocarbons - made up of C and H atoms and contain one or more C=Cdouble bond somewhere in their structures.. Their general formula is C n H 2n. - for non-cyclic alkenes. Their...
  • Gail Napper Centre Development Worker & Jackie Foster

    Gail Napper Centre Development Worker & Jackie Foster

    Gail Napper Centre Development Worker & Jackie Foster Training Manager Aughton Early Years Centre was designated Early Excellence Centre in December 1999 Childrens Centre in September 2003 Integrated care and education for 0 - 4 years and additional services for...
  • Présentation PowerPoint

    Présentation PowerPoint

    EUT440 ENGINEERS IN SOCIETY Knowledge Sincerity Excellence
  • Encyclopédie, ou Dictionnaire Raisonné des Sciences, des Arts ...

    Encyclopédie, ou Dictionnaire Raisonné des Sciences, des Arts ...

    Oxford, England. Language. 1884. 1. 19Book. 5. Johannes Gutenberg. introduces movable type printing. ... Giovanni Gherardo di Rossi was a playwright, poet, and minister of finance. 18History. 3. Giampietro Vieusseux founded the oldest still operating journal of Italian history.
  • Evidence-Based EMail Management at UNC: A Search for

    Evidence-Based EMail Management at UNC: A Search for

    Lots of folks are filing their messages electronically (perhaps only electronically). We need to know how folks are filing. Conclusions We may need instruction/resources available in how to name and organize files. With so many folks filing messages electronically we...
  • Lecture 4: Ethics and professional responsibility

    Lecture 4: Ethics and professional responsibility

    Panopticon in popular culture Big Brother Truman show The Sims Second Life The 21st century panopticon What you've done Archived data What you're doing Real-time data and media What you'll do Profiling Surveillant Assemblage convergence and integration Surveillant Assemblage Evidence...
  • The Joy of Wires: an introduction to Netduino, .NET Micro ...

    The Joy of Wires: an introduction to Netduino, .NET Micro ...

    The Joy of Wires: an introduction to Netduino, .NET Micro Framework and the Internet of Things. Iain Angus. agenda. ... used to prevent bounce, true to enable, false to disable. ResistorMode. InterruptMode. ... zero G approximately 1.65V with Aref 3.3V.