HANDS-ON ZIGBEE IMPLEMENTATION

By D. MASID

C O N T E N TS CHAPTER INTRODUCTION 11 OVERVIEW 12 DIMENSIONS OF THE PROBLEM SPACE: SPECIFICATION, VERIFICATION, PERFORMANCE ESTIMATION, AND IMPLEMENTATION 121 THE SPECIFICATION PROBLEM 122 THE VERIFICATION PROBLEM 123 “CORRECTNESS” AND PERFORMANCE 124 RELATING ABSTRACT MODELS TO IMPLEMENTATION 13 ABSTRACT SERVICES AND THE OSI PROTOCOL “STACK” 14 AN APPROACH TO INTEGRATING PROTOCOL DESIGN DISCIPLINES 15 SUMMARY OF CONTRIBUTIONS 16 OUTLINE OF THE DISSERTATION CHAPTER INFORMAL SPECIFICATION OF PROTOCOL SYSTEM REQUIREMENTS 21 OVERVIEW 22 AN INFORMAL HIGH-LEVEL DESCRIPTION OF THE INFOPAD SYSTEM 23 A “MESSAGE-PASSING” ARCHITECTURAL PARTITIONING 231 THE INFONET NETWORK INFRASTRUCTURE 2311 MOBILITY SUPPORT 2312 MULTIMEDIA I/O SUPPORT 232 ARCHITECTURE OF THE INFOPAD TERMINAL 24 SERVICE REQUIREMENTS: PERFORMANCE ASPECTS VS FUNCTIONAL ASPECTS 25 FOLLOWING THE METHODOLOGY THROUGH TO IMPLEMENTATION: THE DESIGN OF THE INFOPAD TERMINAL 251 HARDWARE SUPPORT FOR REMOTE I/O 2511 DESIGN TRADE-OFFS 2512 IPBUS DESCRIPTION 252 WIRELESS INTERFACE SUBSYSTEM TX INTERFACE RX INTERFACE FPGA INTERFACE 253 MICROPROCESSOR SUBSYSTEM 254 MICROPROCESSOR INTERFACE CHIP 255 USER INTERFACE I/O PERIPHERALS 2551 GRAPHICS SUBSYSTEM 2552 PEN SUBSYSTEM 2553 AUDIO SUBSYSTEM 2554 VIDEO INTERFACE 256 EVALUATION AND MEASUREMENTS 2561 ARCHITECTURAL EVALUATION PROCESSOR UTILIZATION REMOTE-I/O PROCESSING LATENCY COMMUNICATIONS PROTOCOL SUPPORT 2562 IMPLEMENTATION EVALUATION POWER CONSUMPTION FORM FACTOR 26 SUMMARY PROTOCOL DESIGN AND FORMAL SPECIFICATION LANGUAGES 31 OVERVIEW 32 SPECIFICATION OF PROTOCOLS 321 A FORMAL MODEL OF PROTOCOL SYSTEMS 322 MODELS OF CONCURRENCY AND COMMUNICATION 3221 SEMANTICS OF EVENT ORDERING 3222 TRUE- AND QUASI-PARALLELISM 3223 COMMUNICATION SYNCHRONY 323 FORMAL LANGUAGES FOR PROTOCOL SPECIFICATION 3231 STANDARDIZED FDTS FOR PROTOCOL SPECIFICATION ESTELLE SDL LOTOS 3232 SPECIALIZED LANGUAGES 3233 THE SYNCHRONOUS LANGUAGES 324 SUMMARY OF FORMAL LANGUAGES PRACTICAL APPROACHES TO THE FORMAL VERIFICATION OF COMMUNICATION PROTOCOLS 41 OVERVIEW OF FORMAL VERIFICATION 42 MODEL CHECKING 421 SYMBOLIC MODEL CHECKING 422 PARTIAL ORDER REDUCTION 423 SYMMETRY REDUCTION 424 COMPOSITIONAL REFINEMENT VERIFICATION A HARDWARE IMPLEMENTATION METHODOLOGY USING REFINEMENT VERIFICATION 51 OVERVIEW 52 REFINEMENT AND VERIFICATION OF A GENERALIZED DATA TRANSFER NETWORK 53 ZEN AND THE ART OF PROTOCOL ABSTRACTION 531 A DIVIDE-AND-CONQUER APPROACH 532 GENERALIZED INTERFACES 5321 SPECIFICATIONS, IMPLEMENTATIONS, AND ABSTRACT VARIABLES ABSTRACT VARIABLES SYMMETRY REDUCTIONS 5322 THE ROLE OF REFINEMENT MAPS AND WITNESS FUNCTIONS 54 REFINEMENT VERIFICATION IN SMV 541 LAYERS 542 REFINEMENT 543 ABSTRACT SIGNALS 544 SYMMETRY REDUCTION TECHNIQUES 5441 RESTRICTIONS ON SCALARSETS 5442 DEALING WITH ASYMMETRY 55 SDL SPECIFICATION OF A PACKET MULTIPLEXING SYSTEM 56 SEQUENTIAL IMPLEMENTATION OF THE SWITCH 57 OUTLINE OF THE PROOF 58 SMV SPECIFICATION 581 SPECIFYING DATA INTEGRITY AT THE ATOMIC TRANSFER LEVEL 5811 THE ATOMICSEND LAYER 5812 THE INPUT_SPEC LAYER 5813 THE OUTPUT_SPEC LAYER 5814 THE RECV_SPEC LAYER 5821 THE SEQSEND LAYER 5822 THE SEQSTORE LAYER 5823 PROVING SEQUENTIAL TRANSFERS IMPLY ATOMIC TRANSFERS 583 SWITCH OUTPUT REFINEMENT 5831 THE SEQFETCH LAYER 5832 PROVING SEQUENTIAL OUTPUT MEETS THE SPECIFICATION 584 RECEIVER SPECIFICATION 585 PROVING COMPLETENESS AND ORDERING AT THE RECEIVER 5851 BREAKING SYMMETRIC STRUCTURES 59 VERIFICATION RESULTS AN IMPLEMENTATION METHODOLOGY FOR EMBEDDED SYSTEMS 61 OVERVIEW 62 THE RELATIONSHIP BETWEEN SPECIFICATION LANGUAGES AND IMPLEMENTATION 63 AN ARCHITECTURAL TEMPLATE FOR WIRELESS SYSTEMS 631 A DOMAIN-SPECIFIC IMPLEMENTATION TEMPLATE A TEMPLATE FOR COMPUTATION AND COMMUNICATION IN MIXED HARDWARE/SOFTWARE IMPLEMENTATIONS 633 PARTITIONING STRATEGY: THE SDL PROCESS AS THE SMALLEST PARTITIONING UNIT 6331 SYSTEM PARTITIONING AND CODE GENERATION 64 INTERPROCESS COMMUNICATION SUPPORT 641 SUPPORTING THE HARDWARE/HARDWARE INTERFACE 6411 HARDWARE-TO-HARDWARE MESSAGE PASSING 6412 HARDWARE-TO-HARDWARE IMPORT/EXPORT 6413 HARDWARE-TO-HARDWARE REMOTE-PROCEDURE CALL 642 MAPPING THE SDL MODEL TO SOFTWARE 6421 SCHEDULING POLICIES 6422 ADVANCING TIME 65 IPOS: OPERATING SYSTEM SUPPORT IN THE INFOPAD SYSTEM 651 DATA SOURCES, SINKS AND STREAMS 6511 HARDWARE-HARDWARE AND SOFTWARE-SOFTWARE SOURCES AND SINKS 6512 CROSSING THE HARDWARE/SOFTWARE BOUNDARY 652 TIMERS 66 CURRENT STATUS AND POSSIBLE EXTENSIONS PRACTICAL STRATEGIES FOR INTEGRATING FORMAL METHODS IN PROTOCOL DESIGN AND IMPLEMENTATION 71 OVERVIEW 72 AN INFORMAL SYSTEM-LEVEL SPECIFICATION 721 DELAY, BANDWIDTH AND RELIABILITY CONSTRAINTS 722 SYSTEM-LEVEL SERVICES FOR I/O SERVERS AND CLIENTS 73 DESIGNING THE DATA LINK PROTOCOL 74 PHYSICAL LAYER INTERFACE 7411 BIT-LEVEL SYNCHRONIZATION 7412 FRAME SYNCHRONIZATION 7413 DISCUSSION OF HEURISTICS AND DESIGN TRADEOFFS 7414 SIGNAL STRENGTH MEASUREMENTS & ANTENNA DIVERSITY 75 MEDIA ACCESS PROTOCOL FOR FREQUENCY-HOPPING MODEMS 7511 CHOOSING A HOPPING SEQUENCE FREQUENCY HOPPING FOR COARSE-GRAIN FREQUENCY DIVERSITY FREQUENCY HOPPING FOR UNREGULATED SYSTEMS SLOW FREQUENCY HOPPING CODE DIVISION MULTIPLE ACCESS 7512 SYNCHRONIZING THE TRANSMITTER AND RECEIVER 76 LINK MANAGEMENT PROTOCOLS 7611 OVERVIEW OF MESSAGE SEQUENCE CHARTS 762 ESTABLISHING THE LINK 763 MAINTAINING THE LINK 7631 HANDOFF BETWEEN CELLS 77 FORMAL DESCRIPTION AND VERIFICATION OF THE SYSTEM 771 MESSAGE SEQUENCE CHART SPECIFICATIONS 772 SDL SPECIFICATIONS 773 PROMELA CONCLUSIONS AND FUTURE WORK C H A P T E R I N T R O D U C T I O N 11 OVERVIEW DATA COMMUNICATIONS PROTOCOLS GOVERN THE WAY IN WHICH ELECTRONIC SYSTEMS EXCHANGE INFORMATION BY SPECIFYING A SET OF RULES THAT, WHEN FOLLOWED, PROVIDE A CONSISTENT, REPEATABLE, AND WELL-UNDERSTOOD DATA TRANSFER SERVICE IN DESIGNING COMMUNICATION PROTOCOLS AND THE SYSTEMS THAT IMPLEMENT THEM, ONE WOULD LIKE TO ENSURE THAT THE PROTOCOL IS CORRECT AND EFFICIENT CORRECTNESS MEANS THAT THE RULES OF EXCHANGE ARE INTERNALLY CONSISTENT AND UNAMBIGUOUSLY HANDLE ALL POSSIBLE EVENTS INFORMALLY, WE WISH TO KNOW THAT THE PROTOCOL IS FREE FROM UNWANTED BEHAVIOR, SUCH AS DEADLOCK, AND THAT IT CAN INDEFINITELY PROVIDE DATA TRANSFER SERVICE UNDER ANY INPUT SEQUENCE THESE CORRECTNESS PROPERTIES ARE ONLY PART OF THE DESIGN PROBLEM: IT IS EQUALLY IMPORTANT TO GUARANTEE THAT THE PROTOCOL IS EFFICIENT EFFICIENCY, USED HERE TO INDICATE HOW WELL A GIVEN PROTOCOL PERFORMS RELATIVE TO AN IMPLEMENTATION WITH UNCONSTRAINED COMPLEXITY, IS A MUCH MORE DIFFICULT PROPERTY TO QUANTIFY THE MEASURES OF EFFICIENCY ARE LARGELY DEPENDENT UPON THE CONTEXT IN WHICH THE PROTOCOL IS TO BE USED AND UPON THE SERVICES THAT THE PROTOCOL IS SUPPOSED TO PROVIDE THROUGHPUT, DELAY, CHANNEL UTILIZATION, SPECTRAL EFFICIENCY, AND END-TO-END DISTORTION ARE BUT A FEW OF THE MEASURES COMMONLY USED TO COMPARE ALTERNATIVES IN PROTOCOL DESIGN THE UNDERLYING QUESTION IS “ALL CONSTRAINTS CONSIDERED, IS THERE A BETTER APPROACH THAT PROVIDES THE SAME SERVICE?” IN PRACTICE, MOST NEW PROTOCOL DESIGNS ARE APPROACHED IN AN AD-HOC FASHION THAT RELIES HEAVILY ON SIMULATION TO ANSWER BOTH THE QUESTION OF CORRECTNESS AND EFFICIENCY FORMAL APPROACHES SUCH AS FORMAL SPECIFICATION AND FORMAL VERIFICATION ARE USUALLY RELEGATED TO THE DOMAIN OF THEORISTS THIS THESIS, IN CONTRAST, ADDRESSES THE PROBLEM OF INTEGRATING FORMAL METHODS WITHIN A COMPREHENSIVE DESIGN FLOW THE CONTEXT FOR THE PROTOCOL DESIGN METHODOLOGY IS LINK-LEVEL COMMUNICATION PROTOCOLS FOR WIRELESS NETWORKS THAT PROVIDE MULTIMEDIA SERVICES TO MOBILE USERS, SUCH AS THE ONE DESCRIBED IN EXAMPLE SYSTEM OF CHAPTER 2 (IN PARTICULAR, INFRASTRUCTURE-BASED NETWORKS THAT SUPPORT MOBILE CLIENTS ARE CONSIDERED; CHALLENGES SPECIFIC TO PEER-TO-PEER COMMUNICATION BETWEEN MOBILE HOSTS ARE NOT ADDRESSED) PORTABLE DEVICES, IN THIS CONTEXT, HAVE SEVERE CONSTRAINTS ON THE SIZE, THE POWER CONSUMPTION, AND THE COMMUNICATIONS BANDWIDTH AVAILABLE, AND ARE REQUIRED TO HANDLE MANY CLASSES OF DATA TRANSFER SERVICE OVER A LIMITED-BANDWIDTH WIRELESS CONNECTION, INCLUDING DELAY SENSITIVE, REAL-TIME TRAFFIC SUCH AS SPEECH AND VIDEO THIS COMBINATION OF LIMITED BANDWIDTH, HIGH ERROR RATES, AND DELAY-SENSITIVE DATA REQUIRES TIGHT INTEGRATION OF ALL SUBSYSTEMS IN THE DEVICE, INCLUDING AGGRESSIVE OPTIMIZATION OF THE COMMUNICATION PROTOCOLS TO SUIT THE INTENDED APPLICATION THE PROTOCOLS MUST BE ROBUST IN THE PRESENCE OF ERRORS; THEY MUST BE ABLE TO DIFFERENTIATE BETWEEN CLASSES OF DATA, GIVING EACH CLASS THE EXACT SERVICE IT REQUIRES; HANDS ON ZIGBEE: IMPLEMENTING 802154 WITH MICROCONTROLLERS AND THEY MUST HAVE AN IMPLEMENTATION SUITABLE FOR LOW-POWER PORTABLE ELECTRONIC DEVICES THERE ARE AT LEAST FOUR ASPECTS OF THIS PROTOCOL DESIGN PROBLEM THAT MAKE IT BOTH CHALLENGING AND INTERESTING THE FIRST IS COMMON TO ALL PROTOCOL DESIGNS: BECAUSE DESIGNING A PROTOCOL INVOLVES REASONING ABOUT A DISTRIBUTED SYSTEM, THE DESIGNER MUST BE ABLE TO CONCEPTUALIZE AND MODEL THE INTERACTION BETWEEN INDEPENDENT ACTORS WITHIN THE CONTEXT OF INFRASTRUCTURE-BASED MOBILE NETWORKING THE PROBLEMS ARE PARTICULARLY CHALLENGING BECAUSE DESPITE THE BEST INTENTIONS OF THE ACTORS, IT CANNOT BE ASSUMED THAT THE PHYSICAL LINK EVEN EXISTS! OBVIOUSLY, DESIGN LANGUAGE AND MODELING TOOLS MUST HANDLE CONCURRENCY, ASYNCHRONY, AND INTERPROCESS COMMUNICATION, YET THE BREADTH OF ONGOING WORK ON CONCURRENT SYSTEMS ATTESTS TO THE CHALLENGES THAT REMAIN TO BE SOLVED TO FIND THE “RIGHT” LANGUAGE FOR PROTOCOL DESIGN THE SECOND ASPECT IS THE PARTICULAR CLASS OF PROTOCOLS: DATA LINK PROTOCOLS DATA LINK PROTOCOLS ARE USUALLY DIVIDED INTO TWO MAIN FUNCTIONAL COMPONENTS, THE LOGICAL LINK CONTROL (LLC) AND THE MEDIA ACCESS CONTROL (MAC), THAT ARE RESPONSIBLE FOR PROVIDING (1) A POINT-TO-POINT PACKET TRANSFER SERVICE TO THE NETWORK, AND (2) A MEANS BY WHICH MULTIPLE USERS CAN SHARE THE SAME PHYSICAL TRANSMISSION MEDIUM SINCE IT MUST INTERACT BOTH WITH NETWORK-LEVEL SERVICES AND THE PHYSICAL TRANSMISSION MEDIUM, THE DATA LINK PROTOCOL SPANS SEVERAL LEVELS OF SERVICE ABSTRACTION AND SEVERAL ORDERS OF MAGNITUDE IN TIME GRANULARITY THIS COMPLICATES MODELING, SIMULATION, AND FORMAL ANALYSIS BECAUSE NO SINGLE DESIGN LANGUAGE IS CAPABLE OF WORKING WELL ACROSS SO MANY LEVELS OF ABSTRACTION AND ACROSS SO MANY LEVELS OF TIME SYNCHRONOUS LANGUAGES, SUCH AS ESTEREL AND SMV, ARE APPROPRIATE FOR DESIGNING AND VERIFYING IMPLEMENTATION-LEVEL STATE MACHINES, BUT ARE NOT ABLE TO HANDS ON ZIGBEE: IMPLEMENTING 802154 WITH MICROCONTROLLERS MODEL DISTRIBUTED SYSTEMS THAT EXCHANGE MESSAGES ASYNCHRONOUSLY FORMAL DESCRIPTION LANGUAGES LIKE SDL SOLVE THE PROBLEM OF DISTRIBUTED, ASYNCHRONOUS SYSTEMS, BUT ARE INADEQUATE FOR USE IN DESCRIBING DETAILED BEHAVIOR OF SYNCHRONOUS CIRCUITS THAT ARE TYPICAL IN MODEM INTERFACE HARDWARE THE THIRD DESIGN CHALLENGE IS THE DIFFICULTY OF OBTAINING PERFORMANCE ESTIMATES FOR MEDIA ACCESS AND PHYSICAL LAYER PROTOCOLS FOR WIRELESS NETWORKS BECAUSE THE USERS ARE MOBILE AND THE COMMUNICATIONS CHANNEL IS HIGHLY TIME-VARYING, ESTIMATES OF ERROR RATES AND CODING PERFORMANCE ARE LARGELY DEPENDENT UPON THE TRAFFIC PATTERNS OF OTHER USERS, THE MODULATION SCHEME USED, AND THE EXTENT TO WHICH THE CHANNEL CHANGES WITH TIME DEVELOPING REALISTIC STATISTICAL MODELS FOR TRAFFIC PATTERNS, CHANNEL NOISE AND INTERFERENCE, AND FOR THE TIME-VARYING WIRELESS CHANNEL ARE ESSENTIAL TO THE DESIGN OF GOOD PROTOCOLS OBTAINING EXPERIMENTAL DATA THAT GIVES THE DESIGNER INSIGHT ABOUT THE TIME-VARYING STATISTICS OF THE WIRELESS CHANNEL IS STILL A SUBJECT OF ACTIVE RESEARCH ONE APPROACH TO USING EXPERIMENTAL DATA TO CHARACTERIZE THE TIME STATISTICS OF AN INDOOR WIRELESS LINK IS PRESENTED IN APPENDIX A THE FOURTH ASPECT IS THE DESIGN CONTEXT ITSELF: THE COMBINATION OF WIRELESS COMMUNICATIONS AND PORTABLE DEVICES TAKEN IN ISOLATION, EACH OF THESE PRESENTS A RICH BASIS FOR NEW APPROACHES TO SOLVING MATURE PROBLEMS TAKEN TOGETHER, THEY OFFER THE CHANCE TO COMPLETELY RETHINK CLASSICAL APPROACHES TO COMMUNICATION, NETWORKING, COMPUTING, AND SYSTEM DESIGN IT IS THIS ASPECT WHICH PROVIDES THE GREATEST OPPORTUNITY FOR TECHNICAL CONTRIBUTIONS BECAUSE DESIGNS MUST BE APPROACHED WITH A HOLISTIC VIEW, RATHER THAN BY COMPOSITION OF INDIVIDUALLY OPTIMIZED SUBSYSTEMS HANDS ON ZIGBEE: IMPLEMENTING 802154 WITH MICROCONTROLLERS DATA COMMUNICATIONS NETWORKS HAVE HISTORICALLY BEEN LIMITED TO FIXED-WIRE NETWORKS: WIRELESS MEDIA WAS UTILIZED IN VERY SPECIALIZED APPLICATIONS, SUCH AS MILITARY TACTICAL NETWORKS OR COMMUNICATION WITH SATELLITES, WITH FEW REAL-TIME APPLICATIONS MOST PROTOCOL DESIGN METHODOLOGIES IMPLICITLY ASSUME AN ENVIRONMENT THAT IS STATIC, AND THUS RADICALLY DIFFERENT THAN WIRELESS IT IS ONLY IN THE LAST DECADE THAT WIRELESS COMMUNICATIONS HAS COMPLETELY PERVADED MODERN LIFE, AND IN DOING SO HAS MADE RELEVANT THE QUESTION OF A DESIGN METHODOLOGY THAT CONSIDERS THE PARTICULAR PROBLEMS AND OPPORTUNITIES THAT ARE PRESENT IN THIS CONTEXT THE PRIMARY GOAL OF THIS THESIS IS TO IDENTIFY HOW THE DEMANDING REQUIREMENTS FOR HIGH-BANDWIDTH, LOW-LATENCY WIRELESS COMMUNICATION FOR PORTABLE DEVICES REQUIRES A COMPLETE RETHINKING OF THE METHODOLOGY FOR DESIGNING THESE SYSTEMS; THE METHODOLOGY PRESENTS ONE APPROACH TO INTEGRATING SPECIFICATION, FORMAL VERIFICATION, PERFORMANCE SIMULATIONS, AND A PATH TO IMPLEMENTATION 12 DIMENSIONS OF THE PROBLEM SPACE: SPECIFICATION, VERIFICATION, PERFORMANCE ESTIMATION, AND IMPLEMENTATION AS DESCRIBED ABOVE, THE FOCUS OF THIS DISSERTATION IS ON SIMPLIFYING THE PROTOCOL DESIGN PROBLEM, WHICH HAS FOUR KEY ELEMENTS: SPECIFICATION, VERIFICATION, PERFORMANCE ESTIMATION, AND FINALLY, IMPLEMENTATION HISTORICALLY, THESE DIMENSIONS HAVE LARGELY BEEN SEPARATED TO GIVE THE READER A VIEW OF WHAT LIES AHEAD, THE APPROACH TAKEN HERE BEGINS WITH THE ASSUMPTION THAT PERFORMANCE ESTIMATION AND PROTOCOL VERIFICATION ARE EQUALLY IMPORTANT PROBLEMS THAT MUST BE ADDRESSED AT SOME POINT BEFORE IMPLEMENTATION THUS, WHAT IS NEEDED IS HANDS ON ZIGBEE: IMPLEMENTING 802154 WITH MICROCONTROLLERS • A LANGUAGE THAT IS FORMAL, YET HAS THE CAPABILITY TO BOTH ABSTRACT AND TO REFINE, AS NEEDED, THROUGHOUT THE DESIGN PROCESS THE LANGUAGE MUST PROVIDE A MEANS OF EXPRESSING PERFORMANCE CONSTRAINTS • A SET OF TOOLS THAT FACILITATE DESIGN EXPLORATION AND EVALUATING PERFORMANCE • CLEAR UNDERSTANDING OF THE RELATIONSHIPS OF KEY PARAMETERS IN THE PROTOCOL DESIGN, AND THE RELATIONSHIPS TO THE NETWORK LAYER AND PHYSICAL LAYER CHARACTERISTICS • A MEANS OF SEPARATING SIMULATION MODELS WHILE STILL CAPTURING ESSENTIAL INTERDEPENDENCIES – FOR EXAMPLE, SIMULATING BOTH THE BACKBONE NETWORK (PACKET-LEVEL ABSTRACTION) AND THE SIGNAL-SPACE MODULATION DETAILS IS PROHIBITIVELY EXPENSIVE AND PROVIDES LITTLE INTUITION ABOUT THE WAY THE SYSTEM SHOULD BE DESIGNED INSTEAD, ONE WOULD LIKE TO ABSTRACT WHERE POSSIBLE WITHOUT LOSING ESSENTIAL PERFORMANCE INFORMATION THUS, WHAT IS NEEDED IS A METHODOLOGY THAT ADDRESSES THE EXPLORATION PHASE, THE “STANDARDIZATION” PHASE1, AND THE IMPLEMENTATION PHASE 121 THE SPECIFICATION PROBLEM AS A STARTING POINT, WE TAKE THE WELL-KNOWN FACT THAT PROTOCOLS OF ANY SIGNIFICANCE ARE NOTORIOUSLY DIFFICULT TO DESIGN FIRST, THERE IS THE PROBLEM OF SAYING WHAT THE PROTOCOL DOES AND, WITHOUT CONSTRAINING THE IMPLEMENTATION, DETAILING THE SERVICES THAT IT PROVIDES THE SERVICES, LEGAL SEQUENCES OF MESSAGE EXCHANGES, AND THE BEHAVIOR UNDER ALL EXCEPTIONAL CONDITIONS MUST BE DEFINED IN SUCH A WAY THAT THERE CAN BE NO SEMANTIC AMBIGUITY THIS IS THE SPECIFICATION PROBLEM TO HAVE ANY HOPE OF APPLYING AUTOMATED METHODS OF FORMAL VERIFICATION TO THE PROBLEM, THE PROTOCOL MUST ITSELF BE DESCRIBED IN A LANGUAGE THAT HAS WELL-DEFINED HANDS ON ZIGBEE: IMPLEMENTING 802154 WITH MICROCONTROLLERS SEMANTICS AND AN UNDERLYING MATHEMATICAL MODEL OF THE SYSTEM BEING REPRESENTED CHAPTER 3 EXPLORES THE EXISTING FORMAL LANGUAGES USED TO DESCRIBE PROTOCOLS AND COMPARES THEIR MODELS OF COMPUTATION, CONCURRENCY, COMMUNICATION, AND OTHER FEATURES THAT EITHER AID OR HINDER THE INTEGRATION OF PERFORMANCE METRICS 122 THE VERIFICATION PROBLEM THE VERIFICATION PROBLEM DEALS WITH THE ISSUE OF PROVING CORRECTNESS PROPERTIES ABOUT A SYSTEM THESE PROPERTIES USUALLY FALL INTO TWO BROAD CLASSES: SAFETY, OR “INVARIANCE”, PROPERTIES AND LIVENESS, OR “EVENTUALLY”, PROPERTIES [OL82, PNU85, EME90] INTUITIVELY, A SAFETY PROPERTY ASSERTS THAT “NOTHING BAD HAPPENS,” WHILE LIVENESS PROPERTIES STATE THAT “SOMETHING GOOD EVENTUALLY HAPPENS” THOUGH IT WILL BE EXPLORED IN DETAIL IN LATER SECTIONS, IT IS INTRODUCED HERE WITH THE OBSERVATION THAT FORMAL VERIFICATION IS PERHAPS THE MOST CHALLENGING AND LEAST-UNDERSTOOD TECHNOLOGIES AVAILABLE TO SYSTEM DESIGNERS THE CHALLENGE FOR A DESIGNER LIES IN THE FACT THAT FORMALLY PROVING ANYTHING ABOUT A SYSTEM REQUIRES A PRECISE MATHEMATICAL MODEL OF THE SYSTEM FURTHER, FOR PRACTICAL SYSTEMS, PROVING THE SAFETY AND LIVENESS PROPERTIES IS COMPUTATIONALLY INTRACTABLE WITHOUT ABSTRACTING AWAY ALL BUT THE MOST RELEVANT DETAIL NEEDED TO PROVE THAT THE PROPERTIES HOLD, AND IN PRACTICE IS MORE AN ART THAN A SCIENCE THE ART OF ABSTRAC- TION REQUIRES A DEEP UNDERSTANDING OF THE PROTOCOL AS WELL AS KNOWLEDGE OF HOW THE REPRESENTATION OF A SYSTEM IMPACTS THE CAPABILITY TO PROVE PROPERTIES ABOUT IT 1 BY STANDARDIZATION, WE MEAN THE PROTOCOL MUST BE DESCRIBED IN AN IMPLEMENTATION- INDEPENDENT, UNAMBIGUOUS WAY HANDS ON ZIGBEE: IMPLEMENTING 802154 WITH MICROCONTROLLERS FORTUNATELY PROTOCOL SYSTEMS CAN BE MODELED AS FINITE AUTOMATA, GIVING US A STARTING POINT FOR THE MATHEMATICAL MODEL BUT REDUCING THE SIZE OF THE MODEL TO A POINT WHERE AN AUTOMATED FORMAL VERIFICATION SYSTEM BECOMES USEFUL REQUIRES A DEEP UNDERSTANDING OF OPERATION OF THE SYSTEM AND THE SUBTLE RELATIONSHIPS BETWEEN EACH SUBSYSTEM THIS STEP IS STILL THE LIMITING FACTOR THAT IMPEDES THE APPLICATION OF FORMAL VERIFICATION 123 “CORRECTNESS” AND PERFORMANCE TWO OTHER CRITICAL POINTS ABOUT FORMAL VERIFICATION TECHNIQUES ARE THAT 1) THEY ARE CAPABLE OF WORKING WITH THE POSSIBLE STATES THAT A SYSTEM MIGHT BE IN RATHER THAN THE PROBABILITY OF BEING IN A GIVEN STATE, AND 2) TIME IS ABSTRACTED TO THE POINT THAT IT IS ONLY POSSIBLE TO DISTINGUISH BETWEEN ORDERINGS OF EVENTS THUS, PROVING CORRECTNESS IS LIMITED TO PROVING PROPERTIES THAT ARE CONCERNED WITH THE ORDERING OF TWO EVENTS, RATHER THAN THE ABSOLUTE INTERVAL THAT SEPARATES THEM THUS IT IS POSSIBLE TO SAY THAT THE EVENT B FOLLOWS THE EVENT A OR OCCURS SIMULTANEOUSLY WITH EVENT A THIS IS A CRITICAL POINT BECAUSE THE THIRD DIMENSION OF INTEREST, PERFORMANCE MODELING, IS PARTICULARLY INTERESTED IN THE TIMES AND PROBABILITIES THE “CORRECTNESS” OF A PROTOCOL, FOR MANY APPLICATIONS, CANNOT BE EXPRESSED SOLELY IN TERMS OF SAFETY AND LIVENESS PROPERTIES DETERMINING THAT A GIVEN PROTOCOL SYSTEM MEETS A THROUGHPUT REQUIREMENT CAN BE AS IMPORTANT AS ANSWERING THE QUESTION OF FORMAL CORRECTNESS FOR EXAMPLE, FORMAL VERIFICATION CAN DETERMINE THAT IT IS POSSIBLE FOR A BUFFER TO OVERFLOW, BUT PROVIDES NO INFORMATION ABOUT HOW LIKELY THAT EVENT IS IN PRACTICE ONE WOULD LIKE TO OPTIMIZE FOR THE COMMON CASE – SIZING BUFFERS TO HANDLE TYPICAL OCCUPANCIES WITHOUT OVERFLOW – WHILE BEING ABLE TO RECOVER FROM THE CORNER CASES HANDS ON ZIGBEE: IMPLEMENTING 802154 WITH MICROCONTROLLERS (BUFFER OVERFLOW) AS ANOTHER EXAMPLE, THROUGHPUT AND DELAY ESTIMATES ARE TYPICALLY BASED ON STATISTICAL MODELS OF THE COMMUNICATIONS CHANNELS, THE NUMBER OF USERS, AND THE TRAFFIC PATTERNS FOR EACH USER THE MOST NATURAL SIMULATION DOMAIN FOR MODELING THESE PHENOMENA IS USING DISCRETE EVENT SIMULATION SYSTEMS THAT PROVIDE ESSENTIALLY UNRESTRICTED INPUT SPECIFICATIONS (EG, PTOLEMY, VHDL, AND BONES) DISCRETE EVENT SYSTEMS ARE IN GENERAL NOT FINITE-STATE [ELLS97] AND HENCE ARE INCOMPATIBLE WITH FORMAL VERIFICATION THUS, ALTHOUGH ANSWERING THE QUESTIONS IS A CRUCIAL PART OF SHOWING THAT A PROTOCOL IS “CORRECT,” THE DESIGN IS APPROACHED FROM TWO FUNDAMENTALLY DIFFERENT PARADIGMS BOTH SEEK TO ANSWER THE QUESTION THAT MUST PRECEDE IMPLEMENTATION EFFORTS – NAMELY, “DOES THE PROTOCOL PROVIDE, IN A FUNDAMENTAL WAY, THE DESIRED BEHAVIOR?” 124 RELATING ABSTRACT MODELS TO IMPLEMENTATION FINALLY, THE IMPLEMENTATION DOMAIN OF THE PROTOCOL ALSO HAS A SIGNIFICANT ABILITY TO IMPEDE AN INTEGRATED DESIGN APPROACH, ESPECIALLY WHEN THE IMPLEMENTATION CONTAINS A MIX OF HARDWARE AND SOFTWARE THE MEDIA ACCESS CONTROL LAYER, IN PARTICULAR, IS CLOSELY TIED TO THE UNDERLYING PHYSICAL LAYER AND CONTROL LOGIC MUST RESPOND TO EVENTS AT THE MICROSECOND LEVEL; FOR POWER EFFICIENCY, IT IS MOST EFFICIENT TO IMPLEMENT THIS CONTROL LOGIC IN HARDWARE PRODUCT DIFFERENTIATION, FIRMWARE UPGRADES, AND THE FLEXIBILITY OF A SOFTWARE-BASED APPROACH, ON THE OTHER HAND, PULL TOWARDS IMPLEMENTING AS MUCH AS POSSIBLE IN SOFTWARE IN PRACTICE, THE FINAL IMPLEMENTATION IS A MIX OF HARDWARE AND SOFTWARE THE PROBLEM OF DESIGNING THESE HYBRID SYSTEMS AND OBTAINING MEANINGFUL PERFORMANCE ESTIMATES IS AN AREA OF ACTIVE RESEARCH KNOWN AS “CO-DESIGN” (SEE [ELLS97] AND THE REFERENCES CITED THEREIN) AT THE HEART OF THE ISSUE IS THAT HANDS ON ZIGBEE: IMPLEMENTING 802154 WITH MICROCONTROLLERS HARDWARE AND SOFTWARE NATURALLY HAVE TWO VERY DIFFERENT TYPES OF CONCURRENCY – INTERLEAVED AND TRUE PARALLEL – AND SO DESIGN STYLES, REPRESENTATIONS, AND SIMULATION SEMANTICS ARE EXTREMELY DOMAIN-SPECIFIC WE WILL EXPLORE THESE ISSUES FURTHER IN CHAPTER 3 SUMMARIZING, WE ARE PRESENTED WITH CONFLICTING OBJECTIVES IN OUR SPECIFICATION LANGUAGES, IN OUR WAYS OF CHECKING “CORRECTNESS”, AND IT BECOMES DIFFICULT TO RELATE THESE VARIOUS CONCEPTUAL MODELS TO THE DOMAIN OF OUR IMPLEMENTATION FOR A PURE SPECIFICATION, SUCH AS A STANDARDS BODY MIGHT PRODUCE, ALL DETAIL MUST BE INCLUDED IN THE MODEL FOR PERFORMANCE MODELING, WE WOULD LIKE THE CAPABILITY TO MODEL MANY USERS, TO QUANTIFY THROUGHPUT, DELAY, AND BUFFER OCCUPANCY, ETC – WE NEED TO HAVE A HIGHER-LEVEL STATISTICAL MODEL OF THE SYSTEM WITH BOTH TIME AND PROBABILISTIC METRICS FOR VERIFICATION, WE WOULD LIKE TO COMPACT, ABSTRACT, AND REMOVE AS MUCH DETAIL AS POSSIBLE WITHOUT CHANGING THE PROTOCOL IT IS NOT SURPRISING THAT THE LANGUAGES USED TO DESCRIBE A PARTICULAR MODEL ARE STRONGLY INFLUENCED BY WHETHER THE MODEL IS TO BE USED FOR SPECIFICATION, FOR FORMAL VERIFICATION, FOR PERFORMANCE MODELING, OR FOR THE ACTUAL IMPLEMENTATION BEFORE PROCEEDING, IT IS BENEFICIAL TO TAKE A BRIEF LOOK AT THE HISTORY OF PROTOCOL DESIGN, PROTOCOL SPECIFICATION, AND THE VARIOUS TECHNICAL TOOLS THAT HAVE BEEN USED TO VERIFY CORRECTNESS AND ESTIMATE PERFORMANCE 13 ABSTRACT SERVICES AND THE OSI PROTOCOL “STACK” BECAUSE IT IS THE MOST COMMON DECOMPOSITION OF PROTOCOL SERVICES, A GOOD STARTING POINT FOR DISCUSSING COMMUNICATION PROTOCOLS IS THE OPEN SYSTEMS INTERCONNECTION (OSI) “PROTOCOL STACK” [DZ83] IN THE OSI MODEL, PROTOCOLS ARE CONCEPTUALLY HANDS ON ZIGBEE: IMPLEMENTING 802154 WITH MICROCONTROLLERS ORGANIZED AS A SERIES OF LAYERS, EACH ONE BUILT UPON ITS PREDECESSOR EACH LAYER OFFERS A SET OF SERVICES TO THE HIGHER LAYERS, HIDING THE DETAILS OF HOW THE SERVICES ARE IMPLEMENTED THE GOAL IS TO PRESENT THE ILLUSION TO LAYER N ON HOST A THAT THE MESSAGE EXCHANGE TAKES PLACE ATOMICALLY VIA LAYER N - 1 TO A LAYER N PEER ON HOST B, AS SHOWN IN FIGURE 1— 1 IN REALITY, EACH LAYER PASSES DATA AND CONTROL INFORMATION THE LAYER IMMEDIATELY BELOW IT, UNTIL THE LOWEST (PHYSICAL) LAYER IS REACHED THE FUNCTION OF EACH LAYER IS OUTLINED IN TABLE 1— 1 FIGURE 1— 1 OSI PROTOCOL LAYERS TWO DIMENSIONS OF ABSTRACTION ARE PRESENT IN THIS MODEL: SERVICE ABSTRACTION AND INTER-LAYER COMMUNICATION ABSTRACTION BETWEEN EACH PAIR OF ADJACENT LAYERS THERE IS AN INTERFACE THAT DEFINES THE PRIMITIVE OPERATIONS AND SERVICES PROVIDED BY THE LOWER LAYER USUALLY, A FOREMOST OBJECTIVE IS TO SPECIFY THE SET OF SERVICES THAT EACH LAYER OFFERS, WHILE ABSTRACTING THE DETAILS OF HOW THESE SERVICES ARE PROVIDED IMPLICITLY WITH THIS OBJECTIVE IS THE DESIRE TO LIMIT DEPENDENCIES BETWEEN EACH LAYER TO A SET OF INTERFACE PRIMITIVES KNOWN AS SERVICE ACCESS POINTS (SAPS) HANDS ON ZIGBEE: IMPLEMENTING 802154 WITH MICROCONTROLLERS THE RATIONALE BEHIND THIS OBJECTIVE IS THAT IT MAKES IT POSSIBLE, IN PRINCIPLE, TO REPLACE THE IMPLEMENTATION OF A PARTICULAR LAYER WITH ANOTHER IMPLEMENTATION, REQUIRING ONLY THAT EACH IMPLEMENTATION PROVIDE A CONSISTENT INTERFACE THAT OFFERS THE SAME SERVICES AND SERVICE ACCESS POINTS TO THE UPPER LAYER THUS, THE GOAL OF SERVICE ABSTRACTION IS MODULARITY AND FREEDOM TO CHOOSE THE IMPLEMENTATION THAT IS BEST SUITED FOR A PARTICULAR ENVIRONMENT DETAIL ABOUT INTER-LAYER COMMUNICATION, ON THE OTHER HAND, IS USUALLY CONSIDERED TO BE A CONCERN THAT IS ORTHOGONAL TO THE DESIGN OF THE PROTOCOL LAYER NUMBER LAYER NAME LAYER FUNCTION APPLICATION USER FUNCTIONS FOR EXAMPLE, FILE TRANSFER, DATABASE QUERY PRESENTATION DATA REPRESENTATION AND TRANSLATION SESSION CONVERSATION INITIATION, COORDINATION, AND BREAKDOWN A SESSION PROTOCOL CONTROLS WHICH PEER CAN TRANSMIT, PROVIDES SERVICES TO SYNCHRONIZE THE QUEUE BETWEEN PEERS, AND DEFINES HOW PROTOCOL DATA UNITS (PDUS) ARE RELATED FOR ERROR RECOVERY TRANSPORT RELIABLE END-TO-END DATA DELIVERY BETWEEN PEERS DEPENDING ON THE QUALITY OF SERVICE OFFERED BY THE NETWORK LAYER, TRANSPORT USUALLY PERFORMS ERROR CORRECTION AND FLOW CONTROL NETWORK HANDLES ROUTING BETWEEN PEERS, GLOBAL NAMING AND ADDRESSING, FRAGMENTATION AND RE-ASSEMBLY LOGICAL LINK CONTROL (LLC) DATA LINK MEDIUM ACCESS CONTROL (MAC) FOR POINT-TO-POINT CONNECTIONS, HANDLES FRAMING, STATION ADDRESSING, ERROR CONTROL AND FLOW CONTROL FOR NETWORKS WHERE TRANSMITTING STATIONS SHARE A COMMON MEDIUM, THE PROTOCOL GOVERNING ACCESS TO THE MEDIUM IS SEPARATED INTO A SUB-LAYER REFERRED TO IN THE IEEE STANDARDS AS THE MEDIA ACCESS CONTROL (MAC) LAYER PHYSICAL ELECTRICAL AND MECHANICAL ATTRIBUTES GOVERNING CONNECTION TO THE COMMUNICATION MEDIUM TABLE 1— 1 THE OSI SERVICE LAYERS HANDS ON ZIGBEE: IMPLEMENTING 802154 WITH MICROCONTROLLERS WHILE THIS MODEL PROVIDES AN EXCELLENT STARTING POINT FOR CONCEPTUALLY PARTITIONING A SET OF PROTOCOL SERVICES, IT MUST BE USED WITH CARE THIS MODEL HAS TWO IMPLICIT ASSUMPTIONS THAT FAIL TO HOLD IN MANY PRACTICAL CONTEXTS FIRST, THERE IS THE ASSUMPTION THAT COST OF ABSTRACTION AND SEPARATION IS NEGLIGIBLE COMPARED TO ADVANTAGE OF BEING ABLE TO INTERCHANGE LAYERS SECOND, THERE IS AN ASSUMPTION THAT INTERCHANGING LAYERS THAT PROVIDE THE SAME LOGICAL SERVICES – FOR EXAMPLE, A WIRED PHYSICAL LAYER AND A WIRELESS PHYSICAL LAYER – PROVIDE EQUIVALENT SERVICE SINCE IN WIRED NETWORKS THE POINT-TO-POINT NETWORK TOPOLOGY IS ESSENTIALLY STATIC, PHYSICAL-LAYER CHANNELS CAN BE MODELED AS TIME-INVARIANT SYSTEMS AND USER-TO-USER INTERFERENCE CAN BE MODELED AS A STATIONARY RANDOM PROCESS BOTH OF THESE PROPERTIES PROVIDE SIMPLE, UNDERSTANDABLE STATISTICAL MODELS FOR CHARACTERIZING THE PROBABILITY OF ERRORS, JUSTIFYING ABSTRACTIONS THAT ALLOW THE SERVICES PROVIDED TO BE PARTITIONED INTO ORTHOGONAL CONCERNS FOR EXAMPLE, A NETWORKED FILE SYSTEM PROVIDES THE ABSTRACTION THAT ALL FILES RESIDE ON A SINGLE LOGICAL FILE SYSTEM, GREATLY SIMPLIFYING THE DESIGN OF AN APPLICATION THAT READ AND WRITE FILES USING A STANDARD FILE I/O INTERFACE IN TURN, THE NETWORKED FILE SYSTEM IS SIMPLIFIED IF IT CAN ASSUME A BLACK BOX, RELIABLE PACKET DELIVERY SERVICE FROM THE LOWER-LEVEL NETWORK SERVICES THE DIFFICULTY IN APPLYING THIS LAYERING APPROACH LIES NOT IN DEFINING CLEAN SERVICE ACCESS POINTS AND ABSTRACTING LOWER LEVEL FUNCTIONALITY; THE REAL DIFFICULTY IS IN SEPARATING THE SEMANTICS OF THE SERVICE PRIMITIVES THIS IS A SUBTLE POINT, AND ONE WORTH FURTHER DISCUSSION THE SPECIFICATION FOR THE WIDELY USED ARPA TRANSMISSION CONTROL PROTOCOL (TCP), FOR EXAMPLE, CONTAINS NO EXPLICIT REFERENCE TO A PHYSICAL MEDIA OR TO ANY PARTICULAR STYLE OF IMPLEMENTATION INSTEAD, IT IS ASSUMED THAT THE IMPLEMENTATION HAS A MEANS OF PROVIDING A BEST-EFFORT DATAGRAM TRANSFER SERVICE BETWEEN ENDPOINTS, AND HANDS ON ZIGBEE: IMPLEMENTING 802154 WITH MICROCONTROLLERS THE TCP SPECIFICATION FOCUSES SOLELY UPON HIGHER LEVEL ISSUES SUCH AS SETTING UP A CONNECTION, MAINTAINING ORDER, AND SO ON INFORMALLY, THE SAPS TO THE LOWER LEVELS ARE PRIMITIVES TO SEND AND RECEIVE DATAGRAMS TCP MAINTAINS ITS OWN TIMER FOR DATAGRAMS THAT STILL REQUIRE AN ACKNOWLEDGEMENT, AND SINCE CORRUPTED PACKETS RECEIVED BY LOWER LAYERS ARE DISCARDED, TCP HAS NO WAY OF DISTINGUISHING BETWEEN A PACKET CORRUPTED BY BIT ERRORS FROM PACKETS THAT ARE LOST DUE TO CONGESTION IN THE NETWORK TCP HAS BEEN SUCCESSFULLY USED WITH A VARIETY OF LOWER-LEVEL MEDIA ACCESS PROTOCOLS SUCH AS CARRIER-SENSE MULTIPLE ACCESS (CSMA) AND TOKEN RING, AND ON A VARIETY OF PHYSICAL MEDIA, INCLUDING WIRELESS, OPTICAL FIBER, AND WIRED MEDIA ALTHOUGH THE TCP SPECIFICATION MAKES NO EXPLICIT REFERENCE TO THE CHARACTERISTICS OF THE LOWER LAYERS, IMPLICITLY IN THE TIMEOUT AND RETRANSMISSION MECHANISMS THERE ARE THE ASSUMPTION THAT THE ERROR RATE IS LOW, AND THAT LOST PACKETS OCCUR DUE TO NETWORK CONGESTION ACCORDINGLY, LOST PACKETS TRIGGER A CONGESTION-AVOIDANCE MECHANISM IN TCP THAT REDUCES THE RATE AT WHICH PACKETS ARE SENT THUS WHEN TCP IS USED OVER A WIRELESS LINK, A SLIGHT CHANGE IN THE PACKET ERROR RATE CAN MEAN THAT THE PERFORMANCE DROPS DRASTICALLY DUE TO THE COMPOUNDED EFFECT OF LOST PACKETS AND A RATE REDUCTION BY THE SENDER AN AGGREGATE THROUGHPUT OF 25% OF THE LINK CAPACITY IS TYPICAL OF TCP OVER WIRELESS [BPSK97] THE PROBLEM HERE ARISES DUE TO MISINTERPRETING THE SEMANTICS OF THE EVENT “LOST PACKET” THE APPROPRIATE BEHAVIOR FOR THE PROTOCOL DEPENDS STRONGLY ON THE SEMANTICS OF THIS EVENT, AND MISINTERPRETATION LEADS TO BEHAVIOR THAT, ALTHOUGH IT DOES NOT VIOLATE ANY SAFETY OR LIVENESS PROPERTIES, SEVERELY LIMITS THE USEFULNESS OF THE PROTOCOL HANDS ON ZIGBEE: IMPLEMENTING 802154 WITH MICROCONTROLLERS 14 AN APPROACH TO INTEGRATING PROTOCOL DESIGN DISCIPLINES THIS ABOVE EXAMPLE ATTESTS TO THE NEED TO TAILOR PROTOCOLS TO THE ENVIRONMENT THEY OPERATE IN, AND IS THE STRONGEST ARGUMENT FOR A DESIGN METHODOLOGY THAT INTEGRATES PERFORMANCE METRICS WITH FUNCTIONAL CORRECTNESS SEPARATING THE DESIGN OF THE PROTOCOL FROM THE CONTEXT IN WHICH IT EXISTS LEADS TO PERFORMANCE PENALTIES THAT ARE UNACCEPTABLE FOR WIRELESS, PORTABLE APPLICATIONS THE REMAINDER OF THIS DISSERTATION EXPLORES THE RELATIONSHIPS BETWEEN SPECIFICATION, VERIFICATION, PERFORMANCE ESTIMATION, AND IMPLEMENTATION THE SUMMARY OF THIS EXPLORATION IS PRESENTED HERE AS A GUIDE FOR THE READER THE FORMAL METHODS COMMUNITY HAS LONG ADVOCATED A METHODOLOGY THAT BEGINS WITH AN ABSTRACT, FORMAL DESCRIPTION OF THE SYSTEM FUNCTIONALITY THAT IS SUPPOSED TO BE THE BASIS FOR RIGOROUS FORMAL VERIFICATION AND ARCHITECTURAL EXPLORATION CONCEPTUALLY, THIS PROVIDES THE DESIGNER WITH AN IMPLEMENTATION-INDEPENDENT WAY OF EVALUATING A PROTOCOL OR AN ALGORITHM FURTHER, THIS METHODOLOGY PROPOSES THAT THE DESIGNER REFINE THIS ABSTRACT DESCRIPTION BY SUCCESSIVELY ADDING IMPLEMENTATION DETAILS, PROVING AT EACH STEP THAT THE REFINEMENT IS CONSISTENT WITH THE ORIGINAL SPECIFICATION IN PRACTICE FEW IF ANY FORMAL METHODS ARE EMPLOYED IN THE DESIGN COMMUNITY INFORMAL TEXT DOCUMENTS USUALLY SPECIFY THE SYSTEM REQUIREMENTS, AND THE TYPICAL DESIGN FLOW STARTS WITH SIMULATION MODELS BASED ON THESE INFORMAL DESCRIPTIONS SIMULATION IS THEN USED TO DRIVE THE BULK OF THE ALGORITHMIC EXPLORATION, AND THE RESULTS OF THESE SIMULATIONS ARE USED TO ELABORATE AND FINE-TUNE THE ORIGINAL DESIGN TYPICALLY, IT IS ONLY AFTER A PROTOTYPE OF THE SYSTEM HAS BEEN BUILT AND CHECKED VIA HANDS ON ZIGBEE: IMPLEMENTING 802154 WITH MICROCONTROLLERS BLACK-BOX CONFORMANCE TESTING [HOL92] THAT THE SYSTEM IS CHECKED AGAINST THE STANDARD FORMAL VERIFICATION (PROMELA) FORMAL SPEC (MESSAGE SEQUENCE CHARTS) HARDWARE DESIGN (SMV/ VERILOG) SOFTWARE DESIGN (C/C++/ASM) PERF ESTIMATION (DE SIMULATION) FUNCTIONAL REQT’S FORMAL MODEL (SDL) MAC LLC FIGURE 1— 2 MIXED FORMAL/INFORMAL DESIGN FLOW FOR DATA LINK PROTOCOLS THE PREMISE OF THIS THESIS IS THAT A MIX OF INFORMAL AND FORMAL SPECIFICATIONS AND MODELS ARE NEEDED IN ORDER TO FACILITATE THE DESIGN OF ROBUST PROTOCOLS THAT HAVE REASONABLE PERFORMANCE HOWEVER, IT IS ESSENTIAL TO UNDERSTAND WHERE EACH IS MOST APPROPRIATE IN THE DESIGN FLOW AS WELL AS THE RELATIONSHIPS BETWEEN FORMAL AND INFORMAL MODELS WITH THIS IN MIND, WE RECOMMEND THE FOLLOWING METHODOLOGY: 1) DEVELOP A SET OF FUNCTIONA