Data Communication and NetworksCommon Issues in DesignData from Two Sources:Slide 4Slide 5Slide 6Slide 7Slide 8Slide 9Ring Buffer Spec (1 of 3)Ring Buffer Spec (2 of 3)Ring Buffer Spec (3 of 3)Ring Buffer: Making it thread-safeRing Buffer CharacteristicsQueueQueue (Singly Linked)Queue (Doubly Linked)Queue OperationsQueue CharacteristicsQueue or Ring Buffer?What is a FSM?FSM ElementsMachine TypesState DiagramFrom State Diagram to FSMData Communication and NetworksLecture 2bADTs in Protocol Design(Ring Buffer, Queue, FSM)September 22, 2005Common Issues in Design1. How to handle data that arrives from two independent sources.a) Down from the higher layerb) Up from the lower layer2. How to implement the protocolWhen building protocol software, there are two common problems that you’ll face:Data from Two Sources:•Down from the Higher Layer (HL)–Higher layer (HL) sends requests (control and data)–Cannot always process the request immediately, so we need a place to hold the request.–We may get “many” HL users (e.g., many TCP, only one IP)–Requests may need to be processed out of order (out of band, QOS, etc).Data from Two Sources:•Up from the Lower Layer (LL)–Lower layer sends data and indications.–Data must be separated from indications.–Read requests from HL may use different data boundaries than LL.–LL may be providing data at same time as HL wants to read it....012N-1Ring Buffer of Size N Inititial State Input: 0Output: 0...012N-1Ring Buffer of Size N New Element Arrives Input: 1Output: 0Element 0...012N-1Ring Buffer of Size N New Element Arrives Input: 2Output: 0Element 0Element 1...012N-1Ring Buffer of Size NRead next (element 0) Input: 2Output: 1Element 0Element 1 Read next (element 1) Input: 2Output: 2...012N-1Ring Buffer of Size NAfter Nth input: Input: 0Output: 2Element 0Element 1How many more input elements can we accept?Element 2Element N-1Ring Buffer Spec(1 of 3)Let B be a buffer.Let S be the size of the buffer B in bytes.Let I be an index into the buffer where the producer will store the next new byte of data.Let O be the index of the next byte that the consumer should remove from the buffer.Let N be the number of unconsumed bytes in the buffer.Define % as the modulus operator.Initially, I = O = N = 0.The buffer is full (has no room for new data) when N == S.The available space (for new data) A = S - NRing Buffer Spec(2 of 3)To Add m bytes of data from buffer D to the buffer B the producer will: (1) Check that m <= A (if not an error has occurred)(2) put bytes into the buffer using this model: int j = I; I = (I+m)%S N += m; for (int q = 0; q < m; q++) B[(j+q)%S] = D[q]Ring Buffer Spec(3 of 3)To remove r bytes from the buffer B to buffer D, the consumer will:(1) Check that r <= N. If not, adjust r (r = N) or signal error.(2) take bytes from the buffer using this model: int j = O; O = (O+r)%S N -= r for (int q = 0; q < r; q++) D[q] = B[(j+q)%S]Ring Buffer:Making it thread-safeSo, you see that the idea is that the input (I) and output (O) pointers change continuously from the beginning of the buffer to the end and then wrap around back to the beginning again. Conceptually, it appears as if the end of the buffer is connected back the front of the buffer as if to form a ring (or circle). We enforce that the input pointer never tries to overtake the output pointer! To make these two methods thread safe, we need only to protect the 3 lines of code that update the class variables O, N, I: NOT the loops that move data! This is a better real-time approach than serializing access to the loop itself, or worse, the entire object.Ring Buffer Characteristics•Elements are all same size and type–Elements are typically primitives (byte, int, etc) but can be pointers or even structures.•Finite–Fixed space must be allocated a priori•Low overhead–No “per element” costs like we have in a Queue•Elements MUST be processed in order.Queue•Elements are linked together in a list.•List can be single (forward) or double (forward and backward) linked.•Queue Control Block contains (as a minimum) pointer to first element (head) and last element (tail)•Queues are almost always used as FIFOs, but can support iteration, random access, and reverse (LIFO) processingQueue(Singly Linked)headtailQueue Control Blockazb z nullelement a element b element zForward linkPayloadPayload can be ANY object or structure. Elements need not contain similar payloads.Queue(Doubly Linked)headtailQueue Control Blockazb z nullelement a element b element zbanullForward linkPayloadBackward linkQueue Operations•Required Operations–Put (add to tail)–Get (get from head)•Nice to Have Operations–Remove (remove specific element)–Insert (add element after a specific element)•Deluxe Operations–Peek (non-destructive Get)–Put to head–Get from tail–Iterate (head to tail or tail to head)Queue Characteristics•Not fixed in length (“unlimited” in length)•Does not require pre-allocated memory•Allows processing of elements in arbitrary order•Can accommodate elements of different type•Additional per element cost (links)Queue or Ring Buffer?•Stream data: Use a ring buffer–Arriving elements are primitives that make up a data “stream” (no record boundaries). TCP data is an example.•Service requests: Use a queue–Arriving elements are requests from a user layer (or clients) and must be processed individually.What is a FSM?•Let’s define the idea of a “machine”–organism (real or synthetic) that responds to a countable (finite) set of stimuli (events) by generating predictable responses (outputs) based on a history of prior events (current state). •A finite state machine (fsm) is a computational model of a machine.FSM Elements•States represent the particular configurations that our machine can assume.•Events define the various inputs that a machine will recognize•Transitions represent a change of state from a current state to another (possibly the same) state that is dependent upon a specific event. •The Start State is the state of the machine before is has received any eventsMachine Types•Mealy machine–one that generates an output for each transition, •Moore machine –one that generates an output for each state.•Moore machines can do anything a Mealy machine can do (and vice versa).•In my experience, Mealy machines are more useful for implementing communications protocols.•The fsm