Repositorio Institucional de Documentos

Repositorio de la Universidad de Zaragoza – Zaguan http://zaguan.unizar.es Proyecto Fin de Carrera Design and Implementation of Multicast Listener Discovery Protocol on constrained devices Autor Daniel Bailo Estallo Director Enrique Torres Moreno INGENIERÍA INFORMÁTICA 2013 Resumen Para la aplicación y apoyo del uso de IPv6 en 6LoWPANs (Low-power Wireless Personal Area Networks), ha habido numerosas investigaciones y se han desarrollado protocolos y mecanismos estandarizados. Sin embargo para la comunicación multicast en estas redes, el tema esta aún bastante abierto a la investigación. La comunicación multicast permite conectar routers con hosts preseleccionados por grupos. La comunicación multicast es muy beneficiosa para aplicaciones con dispositivos con recursos limitados ya que ahorra energía y ancho de banda. A continuación mostramos posibles ejemplos de estas aplicaciones, la iluminación de un edificio organizada por plantas, una red de sensores de temperatura organizados por áreas y un largo número de aplicaciones basadas en la comunicación de un punto a varios puntos preseleccionados. El grupo de investigación de la universidad de Aalto (Finlandia) llamado MAMMoTH (Massive Scale Machine-to-Machine Service) tiene como uno de sus objetivos construir un protocolo multicast para dispositivos con recursos limitados. Para el desarrollo de este protocolo, es necesario un protocolo de encaminamiento multicast y un protocolo de gestión de grupos multicast. Este último, es el protocolo que he desarrollado como “research assistant” para mi proyecto final de carrera. En este proyecto final de carrera, se ha diseñado, implementado y evaluado el protocolo MLD para dispositivos con recursos limitados. MLD permite a un router IPv6 gestionar grupos multicast. No obstante, el uso de MLD en LoWPANs tiene varios problemas como la definición del area local, el tamaño de los paquete y la complejidad del comportamiento del router. El protocolo ha sido implementado en Contiki, un sistema operativo para desarrollar para el “Internet of Things”. Contiki permite conectar sistemas pequeños de poco coste con poca potencia a Internet. Hemos ampliado la pila TCP/IP de Contiki para respaldar MLD. El protocolo ha sido evaluado y analizado sobre un simulador en diferentes topologías para validar el funcionamiento. Del mismo modo, también se ha verificado que el tamaño del objeto creado no ocupaba más memoria de la disponible en los dispositivos Z1 Zolertia. Indice 1.Memoria…………………………………………………………………….….…..1 1.1.Introducción………………...………………………………………………………………..…1 1.2. Desarrollo del trabajo…………………………………………………………………………2 1.3. Resultados………...……………..………………………..…………………………………..3 1.4. Conclusión……………………………………………………………………………………..4 2. Anexo. Memoria detallada en inglés 1 1. Memoria Este proyecto final de carrera se ha realizado en Aalto University (Finlandia). Por esta razón, la mayor parte de la memoria esta en inglés. La estructura de la memoria se podría dividir en dos partes, un breve resumen de lo realizado en castellano y la memoria más detallada explicada en inglés. La parte en castellano describe un resumen del proyecto final de carrera (PFC), para continuar con una introducción al tema donde se desarrolla el PFC. La siguiente subsección explica el desarrollo del proyecto. Luego, se comentan los resultados obtenidos y se finaliza con la conclusión. Como anexo, aparece la memoria detallada en inglés que ya hemos nombrado y allí se podrá ver con más detalle su estructura. 1.1. Introducción El “Internet of Things” (IoT) es un novedoso paradigma que esta ganando terreno en el mundo de las comunicaciones inalámbricas. Grandes compañías como Cisco o Ericsson afirman que en el 2020, habrá más de 50 mil millones de “things” conectadas a Internet. El IoT permite la comunicación entre dispositivos, haciendo posible que los dispositivos físicos puedan comunicarse y que la gente pueda saber cuál es su estado y su localización. Con esta idea, se pueden desarrollar muchas aplicaciones para mejorar el día a día de las personas como por ejemplo: monitorizar el estado de salud de una persona, una aplicación para el ahorro energético de los domicilios, una aplicación que ayude a gestionar el stock en un almacén y un largo etcétera. A pesar del exitoso futuro que se pronostica en este paradigma, hay ciertos problemas en el IoT. Los dispositivos que se interconectan suelen tener recursos limitados, pocos recursos computacionales, memorias reducidas y sistemas débiles de comunicación, no funcionan con los protocolos y mecanismos existentes. Dado este problema, muchas organizaciones están trabajando con un mismo objetivo, estandarizar tecnologías para el IoT. IPv6 esta siendo respaldado por el IETF (Internet Engineering Task Force) como la tecnología a nivel de red para conectar los dispositivos por su gran estandarización en las comunicaciones. Un grupo del IETF ha diseñado ya un protocolo IPv6 para LoWPANs (Low power Wireless Personal Area Networks) que permite a los dispositivos de poca potencia usar IPv6. El grupo ROLL ( Routing Over Low power and Lossy networks) del IETF ha diseñado un protocolo llamado RPL: IPv6 Routing Protocol for Low power and Lossy Networks. Una capa de aplicación esta siendo también desarrollada por otro grupo del IETF, el protocolo CoAP (Constrained Application Protocol). Como queda visto, se esta desarrollando mucho trabajo en el campo del IoT. Sin embargo, en el área de la comunicación multicast no se ha hecho mucho esfuerzo. Hasta donde nosotros sabemos, solo se han desarrollado dos ideas para comunicación multicast en dispositivos con recursos limitados. El protocolo MPL (Constrained Application Protocol) y el protocolo SMRF (Stateless Multicast forwarding with RPL). MPL es un protocolo que no tiene gestión de grupos multicast y no es eficiente hablando de consumo energético y tampoco fiable. SMRF solo permite transmisión de datos en una dirección. Muchas aplicaciones reales en redes de sensores necesitan comunicación multicast ya 2 que ayuda a ahorrar ancho de banda y energía porque evitamos envíos de paquetes repetidos y los dispositivos pueden estar más tiempo inactivos. 1.2. Desarrollo del proyecto Este proyecto final de carrera ha sido desarrollado en el departamento de “Data communications” de la Universidad de Aalto situada en Espoo (Finlandia). En concreto, en el grupo de investigación MAMMoTH (Massive Scale Machine-to-Machine Service). MAMMoTH esta financiado por entidades académicas como la universidad de Aalto y la universidad de Oulu (Finlandia), y por entidades de la industria como Ericsson (Nomadic Lab), Sensinode Oy, Renesas Mobile, There Corporation and Kajaani Data Center Operator. El grupo MAMMoTH esta trabajando en el campo del IoT de forma activa desde el 1 de Julio de 2011 y continuará hasta el 31 de Diciembre de 2013. Dentro del grupo de investigación, mi posición era de “research assistant” bajo la supervisión de Zhonghong Ou (Post-doc Researcher). Semanalmente había una reunión con el grupo para comentar que habíamos hecho cada uno, que problemas y dificultades habíamos encontrado y que tareas se iban a hacer la siguiente semana. El grupo estaba compuesto el profesor Antti Ylä-Jääski, dos “Post-Doc researchers”, Zhonghong Ou y Miika Komu, cuatro estudiantes de doctorado, Vilen Looga, Klaus Hartke, Yang Deng y Shichao Dong y dos “research assistants”, Ketan Devadiga y yo. Mi trabajo estaba centrado en el diseño e implementación del protocolo Multicast Listener Discovery en constrained devices y también realizaba otras tareas para el departamento. Comencé a trabajar en el grupo en Octubre del 2012 y más enfocado a mi proyecto final de carrera en Enero del 2013 supervisado por Antti Ylä-Jääski y Enrique Torres Moreno y como instructor Yang Deng. Con Enrique Torres Moreno, como supervisor de la universidad de Zaragoza, tenía reuniones on-line cada dos semanas y me ayudaba a centrar mis tareas hacia el proyecto final de carrera. Yang Deng como instructor en Aalto University seguía más mi día a día y los aspectos técnicos. A continuación, mostramos un diagrama de Gantt donde podemos ver como se han repartido las diferentes fases del proyecto a lo largo del tiempo. '2012' '2013' OCT NOV DIC ENE FEB MAR ABR MAY JUN JUL AGO Buscar y leer documentación Tareas en el grupo Diseño Implementación Validación Evaluación Escribir memoria 3 Cuando empecé a trabajar en mi proyecto final de carrera, mi primer objetivo era conseguir documentación útil para hacerme con el contexto de trabajo y entender correctamente todo lo relacionado con el tema. Una vez adquirida la idea sobre el protocolo, el campo en el que iba a trabajar, los trabajos relacionados existentes y más información relacionada, comencé a pensar en los problemas que había para aplicar MLD a los dispositivos con recursos limitados ya que no era posible la aplicación directa del protocolo especificado en el RFC 2710 MLDv1. Encontrados los problemas, busqué las soluciones y tras varias reuniones con mi instructor en la universidad de Aalto concluimos con un diseño que solucionaba el problema y se ajustaba a los dispositivos con recursos limitados. Para implementar el diseño tuve que estudiar el sistema operativo Contiki, leyendo ejemplos de código y simulando escenarios. Tras obtener los conocimientos necesarios de Contiki para la implementación de mi protocolo, comencé a desarrollarlo. Con el protocolo finalizado, comenzó el periodo de evaluación y de corregir fallos para conseguir el funcionamiento esperado propuesto en el diseño. Con la aprobación de mi instructor sobre el funcionamiento del protocolo, comencé a escribir la memoria para Aalto University. Durante el desarrollo de mi proyecto, tuve varias reuniones sobre el protocolo MLD con mi instructor Yang Deng y con Ketan Kevadiga que estaba desarrollando el protocolo PIM-SM con SSM para LoWPANs para formar en sinergia el protocolo multicast apto para dispositivos con recursos limitados. La duración del proyecto final de carrera ha sido desde mediados de Enero del 2013 hasta finales de Agosto del 2013. El número de horas trabajadas esta alrededor de 1000. En el departamento en la universidad de Aalto se trabajaba de lunes a viernes a tiempo completo. 1.3. Resultados Un protocolo de comunicación multicast necesita dos protocolos. Uno para el encaminamiento de los paquetes y otro para el mantenimiento de los grupos multicast. Varios estudios afirman que un protocolo eficiente sería usando PIM-SM (Protocol Independent MulticastSparse Mode) adaptado a SSM (Source Specific Multicast) como protocolo de encaminamiento y MLDv2 como protocolo para la gestión de grupos multicast. El objetivo del proyecto final de carrera ha consistido en diseñar e implementar el protocolo MLD (Multicast Listener Discovery) para LLNs (Low power and Lossy Networks) para en un futuro unirlo con una implementación de PIM-SM para dispositivos de recursos limitados y obtener un protocolo de comunicación multicast apto para LLNs. Para el diseño del protocolo apto para dispositivos con recursos limitados se ha partido de la base de la especificación del RFC 2710 del IETF donde se describe el protocolo general MLD. Como el objetivo final es obtener un protocolo multicast tras unirlo con PIMSM con SSM, nos hemos apoyado también en la especificación de MLDv2 en el RFC 3810 del IETF. La aplicación directa del protocolo en dispositivos con recursos limitados no es posible. Ya que nos encontramos con unos problemas de definición correcta de área local en LLNs, complejidad de comportamiento del router y tamaño de paquetes para implementar el 4 filtrado por fuente que se especifica en MLDv2. Hemos tenido que tomar ciertas decisiones en el diseño que se explican con más detalle en la memoria adjuntada en el anexo. La implementación del protocolo MLD apto para dispositivos con recursos limitados ha sido implementado en el sistema operativo para el IoT, Contiki. El código esta desarrollado en C y usa las librerías de Contiki. El protocolo ha sido testeado sobre el simulador ofrecido por Contiki llamado Cooja. Se han realizado varios escenarios con diferentes flujos de datos para validar el correcto funcionamiento y verificar también que el tamaño del objeto cabe en los dispositivos usados. De este modo, hemos conseguido una implementación del protocolo Multicast Listener Discovery para dispositivos con recursos limitados ya que realiza la gestión de grupos multicast necesaria para formar un protocolo multicast, ocupa poca memoria por lo tanto el dispositivo dispone de espacio suficiente para su funcionamiento. Durante este proyecto, no se han verificado los consumos energéticos de los dispositivos pero si que se han implementado métodos para tener que hacer menor gasto computacional. 1.4. Conclusión La tecnología multicast, a menudo es vista como el mecanismo de comunicación más prometedor para el uso de aplicaciones de intenet multiusuario, en tiempo real y multimedia. Los routers y hosts multicast, en redes basadas en IPv6, se comunican e intercambian sus competencias para la gestión de grupos multicast mediante el protocolo Multicast Listener Discovery. Este proyecto final de carrera se ha realizado el diseño y la implementación del protocolo MLD apto para dispositivos con recursos limitados. El diseño es lo suficientemente simple para poder gestionar los grupos multicast y no ocupar mucha memoria. La validación y evaluación de la implementación se ha realizado en el simulador Cooja Como hemos comentado anteriormente, la implementación de MLD adecuada para dispositivos con recursos limitados forma parte de un proyecto mayor del grupo MAMMoTH que es crear un protocolo multicast completo para este tipo de dispositivos. A continuación, se puede encontrar en el anexo la memoria realizada para la universidad de Aalto. Aalto University School of Science Degree Programme in Computer Science and Engineering Daniel Bailo Estallo Design and implementation of Multicast Listener Discovery on constrained devices Final project Espoo, September 2013 Supervisors: Professor Antti Yl¨a-J¨a¨aski, Aalto University Professor Enrique Fermin Torres Moreno, University of Zaragoza Advisor: Yang Deng M.Sc. (Tech.) Aalto University School of Science Degree Programme in Computer Science and Engineering ABSTRACT OF FINAL PROJECT Author: Daniel Bailo Estallo Title: Design and implementation of Multicast Listener Discovery on constrained devices Date: September 2013 Pages: 77 Major: Data Communication Software Code: T-110 Supervisors: Professor Antti Yl¨a-J¨a¨aski Professor Enrique Ferm´ın Torres Moreno Advisor: Yang Deng M.Sc. (Tech.) To enable and support IPv6 in Low-power Wireless Personal Area Networks (LoWPANs), there has been a significant research to contribute with protocols and mechanisms. Nonetheless, the area of multicast still remains an open research topic for LoWPANs. Multicast communication would be beneficial in different applications such as lightning in buildings by groups, temperature sensor networks organized by areas and so forth. The Multicast Listener Discovery (MLD) implementation for constrained devices has been done for a research group in Aalto University (Finland) called MAMMoTH (Massive Scale Machine-to-Machine Service). One of the goals of the group is to build a complete multicast protocol suitable for devices with constraint resources. Hence, the group needs a protocol for multicast routing and a protocol for managing the multicast groups. This last protocol is the developed in this final project. Then, both protocols will work together creating a multicast protocol suitable for constrained devices. In this final project, we design, implement and analyse a MLD protocol suitable for constrained devices. MLD allows an IPv6 router manage multicast groups. However, the use of classic MLD in LoWPANs has several problems such as linklocal area delimitations, packet size and complexity on the role of the routers. The protocol is implemented on Contiki OS, an operating system develop for the Internet of Things. Therefore, we have extended Contiki’s TCP / IP stack to support MLD. The protocol was tested and evaluated in different scenarios to check that it works as we designed. The library object size was analyse as well to be fitted in the Z1 device. Keywords: multicast communication, MLD, contiki, smart objects, Internet of Things Language: English 2 Chapter 2 Background In this section, a general view of the Final Project’s topic is given. First of all, a global vision of Internet of Things is presented focusing in the smart objects and the Wireless Sensor Networks. Then, it is introduced the IP Wireless Sensor Networks and the protocols and mechanisms which are used (IEEE 802.15.4, 6LowPAN and RPL). Eventually, the topic is centred in the IP multicasting explaining the protocols employed to build a multicast protocol in constrained devices (PIM and MLD). 2.1 Internet of Things The term “Internet of Things” (IoT) is difficult to define accurately and can have different facets depending on the perspective taken. There are many groups that have define it, and its first use was probably meant by Kevin Aston, an expert on digital innovation, in 1999. The main idea is that the information on the current Internet is taken by humans and in this next version of Internet the data should be created by things. In Aston words [6]: “If we had computers that knew everything there was to know about things - using data they gathered without any help from us - we would be able to track and count everything, and greatly reduce waste, loss and cost. We would know when things needed replacing, repairing or recalling, and whether they were fresh or past their best. ” Hence, the point of this concept is the pervasive presence around us of a variety of things or objects - such as Radio-Frequency IDentification (RFID) [46] tags, sensors, actuators, mobile phones, etc. -which, through unique addressing schemes, are able to interact with each other and cooperate with their neighbors to reach common goals [22]. “Internet of Things” semantically means “a world-wide network of in9 CHAPTER 2. BACKGROUND 10 terconnected objects uniquely addressable, based on standard communication protocols” [40]. As the authors explains in [7], there are different oriented visions for the concept, “Internet” oriented, “Things” oriented and “Semantic” oriented. The initial interpretation of IoT comes from a “Things” oriented perspective where the things were very simple elements, RFID tags. The terms “Internet of Things” is, in fact, attributed to The Auto-ID Labs [1] who are the leading global network of academic research laboratories in the field of networked RFID. These labs have been improving the object visibility since it is a fundamental key of the path to the full deployment of the IoT vision; but it is not the only one. In a ampler sense, IoT cannot be just a global system in which the only objects are RFIDs. IoT visions recognize that the term IoT implies a much broader vision than the idea of a mere objects identification. In this sense, comes the idea of smart objects that will have identities and virtual personalities operating in smart spaces using intelligent interfaces to connect and communicate within social, environment and user contexts. Making a union of the Internet and Things vision we get the idea of world where things can automatically communicate to computers and each other providing services to the benefit of the human kind. Related with the “Internet vision”, appears the vision of the IPSO (IP for Smart Objects) Alliance, a forum formed in September 2008 by 25 founding companies to promote the Internet Protocol as the network technology for connecting Smart Objects around the world. According to the IPSO vision, the IP stack is a light protocol that already connects a huge amount of communicating devices and runs on tiny and battery operated embedded devices. This guarantees that IP has all the qualities to make IoT a reality. By reading IPSO whitepapers, it seems that through a wise IP adaptation and by incorporating IEEE 802.15.4 into the IP architecture, in the view of 6LoWPAN, the full deployment of the IoT paradigm will be automatically enabled. “Semantic oriented” IoT visions is behind the idea of the items involved in the Future Internet will become extremely high. Therefore, issues related to how to represent, store, interconnect, search, and organize information generated by the IoT will become very challenging. In this context, semantic technologies could play a key role. In fact, these can exploit appropriate modeling solutions for things description, reasoning over data generated by IoT, semantic execution environments and architectures that accommodate IoT requirements and scalable storing and communication infrastructure [41]. For us, Internet of Things is the possibility of connect all kind of heterogeneous networks to the Internet. Every object can be connected to the Internet, no matter how it is the protocol or mechanism is using. The figure CHAPTER 2. BACKGROUND 11 2.1 gives a good vision about our idea in IoT. Figure 2.1: Internet of things vision We will focus our project in the Wireless Sensor Networks which will be connected to the Internet. Therefore, the WSN will be a part of the IoT. 2.2 Wireless Sensor Networks “Smart environments embody the following trace in building, utilities, industrial, home, shipboard and transportation systems automation. Sensor networks are the key to gather the information used by smart environments” [29]. Sensors integrated in these fields could provide extraordinary benefits to society. “The optimal wireless sensor is networked and scalable, consumes very little power, is smart and software programmable, capable of fast data acquisition, reliable and accurate over the long term, costs little to purchase and install, and requires no real maintenance. A Wireless Sensor Network (WSN) practically consist of a gateway that can communicate with a number of wireless sensors via a radio link. Data is collected at the wireless sensor node, compressed, and transmitted to the gateway or other nodes to forward data to the gateway” [43]. There are different topologies for radio communications networks: star network (Single Point-to-Multipoint) (Fig. 2.2), mesh network topology (Fig. 2.3) and hybrid star-mesh network (Fig. 2.4). Other important point is the election of the physical layer in WSN. The physical radio layer characterizes the operating frequency, modulation scheme, and harware interface of the radio to the system. There are many CHAPTER 2. BACKGROUND 12 Figure 2.2: Star network topology Figure 2.3: Mesh network topology CHAPTER 2. BACKGROUND 13 Figure 2.4: Hybrid star-mesh network topology low power propietary low power radio integrated circuits that are convenient choices for the radio layer in WSN, including those from companies such as Atmel, MicroChip, Micrel, Melexis, and ChipCon. It is appropiate to use a radio interface that is standards based since it allows interoperability among multiple companies [42]. Some of the existing radio standards -more information about them on the referencesare IEEE802.11x [12], Bluetooth (IEEE802.15.1 and .2) [24], IEEE802.15.4 [23] , Zigbee [4] and IEEE1451.5 [28]. 2.2.1 Smart objects “The technical definition for a smart object would be an item formed by a sensor or actuator, a tiny microprocessor, a communication device and a power source. Thus, the sensor or actuator provides the smart object to transform the data captured from the sensors, albeit at limited speed and complexity” [43]. The communication device gives the communication ability to send and receive data and the power source enables the smart object to do its work. In smart objects is unquestionably important the size, they are significantly smaller than cellphones and their size cannot outreach few cubic centimeters. Devices of this kind are generally referred to as ”motes”. A mote is an autonomous, compact device, a sensor unit that also has the capability of processing and communicating wirelessly. Even with the autonomy they present, the big strength of motes is that they can form wireless sensor networks and co-operate according to various models and architectures [5]. Despite the importance of the technical definition, we must define the CHAPTER 2. BACKGROUND 14 smart objects based on their behaviour, what they actually do, given their technical abilities. The behaviour completely depends on where and how it is used. The main behavioral properties are the interaction with the real world and communication. Smarts objects utilizes its sensors to sense physical properties ranging from simple and easy-to-measure properties such as light, temperature, and air humidity, to more complex properties such as air pollution, the presence of a car, or when an industrial machine is about to break down. Communication is fundamental to the behavior of smart objects, an smart object can be useful itself but the real power comes from the communication. The smart object that would previously switch on the door light is now able to communicate that the door was opened to every other nearby smart object. These smart objects may turn on other lights in the house, turn up the heat, and so forth [43]. 2.2.2 Categorization. Non IP-enabled sensor networks vs IP-enabled sensor networks Traditionally, sensors networks are not IP-enabled and for networking other mechanisms are used. The IP architecture was considered too heavy to use for low-power short-range networks. Therefore, several custom protocol stacks and architectures were developed. Their integration into IP-based Wide Area Network (WAN) infrastructures requires the deployment of proxies at the borders of both networking domains that transform between non-IP communication in the sensor network and IP communication in the Internet [32] . As you can see in Figure 2.5. The conversion is operated usually at application level. Hence, the proxy queries sensor nodes for sensor data via non-IP communication and stores the data in a local database. Eventually, the proxy is inquired via TCP/IP by the users in the Internet. It might be done also at network level, the proxy would perform a communication protocol transformation. Connecting sensor networks to the Internet via proxies is not ideal. Proxies escapes the end-toend principle of the internet and for deploying a non-IP network, there should be control and communication protocols standarized for IP communication. As example of protocol specifications could be named: ZigBee and ZWave. The ZigBee specification, developed by the ZigBee Alliance, is based on the IEEE 802.15.4 radio standard and provides a set of mechanisms for creating networks of nodes as well as the establishment of applications on top of the network. The ZigBee specification is owned by the ZigBee Alliance and vendors need to join the alliance to commercialize ZigBee technology [3]. ZWave is another specification for low-power communication in wireless smart CHAPTER 2. BACKGROUND 15 Figure 2.5: Non-IP enabled sensor network [32] object systems. It is patented and owned by the Z-Wave Alliance. Z-Wave specifies an entire network stack from the physical layer to the application layer. The application layers are tailored to specific market segments such as home automation or energy management [2]. Neither ZigBee nor Z-Wave are compatible with IP, which is a important problem for emerging systems that need to integrate with IP-based networks and services. By contrast, sensor networks with IP support would enable a seamless integration with WAN infrastructures since the IP-enabled sensor network would be just another part of the Internet figura con IP-enabled. Therefore, no special proxies are needed, taking out all the problems related to them. Evidently, gateways have to be deployed that interconnect WAN infrastructures and wireless sensor nodes but these can operate on IP level. As the Figure 2.6 represents. A lot of research has been performed in the IP world that could be reused in an IP-based wireless sensor networks, e.g, mechanisms, and protocols to support autoconfiguration, mobility, and security [32]. CHAPTER 2. BACKGROUND 16 Figure 2.6: IP enabled sensor network [32] 2.3 IP-based Wireless Sensor Networks ”IP is the future for smart object networks” according to Vasseur and Dunkels [43]. Smart objects present some challenges and IP helps to solve them. Here recap some of them. •Interoperability. IP runs over different link layers. Thus, IP network operates across both wired and wireless link layers without requiring any external systems. Smart object networks extend from low-power wireless nodes to high-power data coordination servers. Still, these systems need to comunicate with each other and IP provides interoperability without any special mechanism that connects the systems because of its layered architecture. IP is available in most operating systems. The all-presence of IP is clear in the ever-growing number of communication technologies that support IP. Standardization portrays a significant part in the success of IP’s interoperability. IP is standardized by an established standardization organization that provides mechanisms through which new standards are reviewed and vetted. This process puts a large amount of effort into ensuring that the mechanisms and protocols proposed as standards can be efficiently implemented. CHAPTER 2. BACKGROUND 17 •Evolvability. The IP architecture has proven to be evolvable due to the end-to-end protocol principle. IP was designed to allow evolve autonomously. The end-to-end principle specifies that application layer functionality should be treat in the end points of the network. Hence, the network does not contain any application-level intelligence and only transport data between the end points. The network does not know about the information is transporting, only the applications make sense of the data. •Scalability. The IP architecture has shown scalability through the use of IP over the public Internet. Ip has proven that it can be deployed over a large number of systems and it can run across huge amount of different implementations of its protocols. It is not necessary to be connected to the public Internet, large companies can span their networks with thousands of computers or servers. •Configuration and management. As a consequence of the IP wide adoption and large-scale deployment, IP has developed plentiful mechanisms and protocols for network configuration and management. For smart object networks, configuration, management, installation, and commissioning are an issue. Although traditional mechanisms cannot be directly applied to smart object networks, the ability to improve existing mechanisms and tools is important. •Small footprint. Low energy consumption, small physical size, and low cost are three of the node-level challenges of smart objects. These ideas means memory constraints and complexity on the nodes. IP was thought as a heavy protocol for its necessity of power and memory. A smart object has only few tens of kilobytes of memory, whereas existing IP implementations would need hundreds. That is why several non-IP stacks were developed. Later on, some lightweight implementations were developed keeping the essential mechanisms for IP. The challenges of low-power operation and the large scale of smart object networks have impulsed several years of research in the wireless sensor networks research community. Although wireless sensor networks are a subset of smart object networks, they share many of the properties such as the lowpower operation, the large scale of the networks, and the resource constraints. In the following subsections, we focus on the low-power wireless networks. Therefore, it is explained the communication mechanism in the LR-WPANs (IEEE 802.15.4), the adaptation layer for IPv6 in LowPANs and RPL (IPv6 Routing Protocol for Low-power and Lossy Networks). In the Figure 2.7, it CHAPTER 2. BACKGROUND 18 Figure 2.7: Protocol stack of an IP enabled sensor is showed the protocol stack of an IP enabled sensor, layer by layer. Now, we will go in detail with the two firsts layers, IEEE 802.15.4 and the 6LoWPAN adaptation layer. 2.3.1 IEEE 802.15.4 IEEE Std 802.15.4 [10, 23] defines the physical layer (PHY) and medium access control (MAC) sublayer specifications for low-data-rate wireless connectivity with fixed, portable, and moving devices with no battery or very limited battery consumption requirements typically operating in the personal operating space (POS) of 10 m. The standard has been developed within the 802.15 personal area network (PAN) Working Group within the Institute of Electrical and Electronic Engineers (IEEE). IEEE 802.15 has a maximum date rate of 250,000 bits/s and a maximum output power of 1mW. The maximum packet size in 802.15.4 is 127bytes. Two different device types can cooperate in an IEEE 802.15.4 network; a full-function device (FFD) and a reduced-function device (RFD). The FFD can work in three modes serving as a personal area network (PAN) coordinator, a coordinator, or a device. An FFD can talk to RFDs or other FFDs, while an RFD can talk only to an FFD. An RFD is intended for applications that are extremely simple, such as a light switch or a passive infrared sensor; they do not have the need to send large amounts of data and may only associate with a single FFD at a time. Consequently, the RFD can be implemented using minimal resources and memory capacity. The devices can form star and peer-to-peer network topologies. Each node in an 802.15.4 network has a 64-bit address that global uniquely identifies the device. 802.15.4 allows CHAPTER 3. DESIGN 25 On demand way, the router will be on a listening state waiting for potential reports from the interested nodes on the link-local area. Thus, the node is responsible for letting know to the router its interest. When a node want to join a multicast group has to send a report and then it will have a timer to send periodically a report to keep the multicast group router’s list updated. Therefore, the node has two transition states, no listening and delaying listener. In the no listening state, it will not receive any multicast data message and in the delaying listener, it will be receiving all multicast data messages from the groups it joined and it would be informing about the continue interest in those multicast addresses. Discovery way, this strategy is completely the opposite. The router holds the responsibility of its multicast addresses list’s maintenance. The router queries periodically based on a timer and when the node receives this message, starts a timer per address and when the timer expires, it sends a report message to show the interest of the multicast address that it wants to listen. This method add another state in the node since when a node receive a report for a multicast address that it is interested, it will stop the timer and it will be in an idle state until it gets another query. To compare and evaluate them, we will consider the node performance and the network traffic. In the on-demand way, the node has to be updating the router every time. Hence, when the node is listening, it always has to be running a timer for sending reports to the router. However, in the discovery way, the node only works when it receives a query. Until that moment, the node can be idle. The same idea comes up in the network traffic on the link local area, on-demand way every node sends a report thus the router handles all the reports from the nodes. On the contrary in the discovery strategy, the router receives only one report per multicast address if there are listeners. To sum up, the discovery way has lower node performance because there is no need of having a timer running all the time and it can be in an idle state and it congests less the network since only one node sends report per multicast group. Therefore, MLD and its discovery way is better for constrained devices. 3.3 Details of MLD suitable for constrained devices First of all, we have to consider that MLD will be used with PIM-SM with SSM to build a complete multicast protocol. Consequently, we have to design the source-filthering feature. In the MLDv2’s RFC, there is an explanation CHAPTER 3. DESIGN 26 about the source-filthering but it is a bit heavy-weight since it requires big messages and it is not suitable for constrained devices. The point is to simplify the idea of MLDv2, therefore the router will keep not only the multicast address group but a unique source address also. We accomplish the idea of SSM, and in every report message, done message or storage for multicast group list there will be the pair (Group adress, Source address). In the next section, we describe how MLD works based on the MLDv1’s RFC. 3.4 Protocol description Routers use MLD to learn which multicast addresses have listeners on their attached links. Each router has a list with the multicast addresses which has listeners and a timer associated with each of those addresses. The important part to consider is that the router only needs to know the existence of listeners per address, it does not need to know their identity (e.g. , unicast address). A router transmits all MLD packets on its link-local area. A router may has two possible roles: Querier and non Querier. All router starts as a Querier and if a router hears a Query message whose IPv6 Source Address is numerically lower than its own address for that link then, it must become a Non-querier for that link. A querier periodically sends a General query to ask for reports of all multicast addresses of interest of that link. General queries are delivered to the link-scope all-nodes multicast address (FF02::1). When a node receives a General Query, it sets a delay timer for each multicast address to which it is listening. Same behavior with the Specific-address query but only for the address required. When the timer expires, send a report to inform its interest. If a node receives a report from an interface for a multicast address while it has a timer delay running for that same address, it stops and does not send a Report for that address, therefore it avoids duplicate reports. When a router gets a report, if the reported address is not on the router’s list of multicast addresses, the reported address is added to the list. If a report is received for a multicast address that already exists, just set the timer. When the timer expires, it is assumed there is no more interested listeners on the link and the address is deleted from the list. When a node want to start listening to a multicast address, it should send an unsolicited report. When a node does not want to listen anymore, it should transmit a Done message for that address. When a router receives a Done, it makes sure that there are no more listeners for that address, sending a specific-query. CHAPTER 3. DESIGN 27 3.4.1 MLD message format and types MLD uses ICMPv6 message types. The ICMPv6 packet format is shown in Figure 3.1. All MLD messages are sent with a link-local IPv6 Source Address, an IPv6 Hop Limit of 1, and an IPv6 Router Alert option in a Hop-by-Hop Options header. Figure 3.1: ICMPv6 packet format There are three types of MLD messages: •Multicast Listener Query (ICMPv6 type = decimal 130). There are two subtypes: –General Query, used to learn which multicast addresses have listeners on a link. –Multicast-Address-Speficic Query, used to determine if a particular multicast address has any listeners. •Multicast Listener Report (ICMPv6 type = decimal 131) •Multicast Listener Done (ICMPv6 type = decimal 132) The code in all messages is set to 0. 3.4.2 Timers and default values The timers are configurable. Here explain the more important values to understand how works the MLD protocol. •Robustness variable allows tuning the expected packet loss on a link. The more possibilities to loss a packet, the bigger has to be the constant. The default value in the RFC is 2. •Query Interval is the interval between General Queries sent by the router. The default value is 125 seconds and it can be selected depending on the network needs. CHAPTER 3. DESIGN 28 •Query Response Interval is the time that the host has to reply since it gets the query from the router. Default value: 10 seconds. •Multicast Listener Interval is the amount of time that must pass before a router decide there are no more listeners. This value must be (the Robustness variable) times (the Query Interval)) plus (one Query Response Interval). •Last Listener Query Interval is the time that the host has to reply when it get a multicast specific address query from the router. Default value 1 second. 3.5 Host state transition diagram Host behavior is more specified by the state transition diagram in the figure 3.2 . A node may be in one of three possible states with respect to any single IPv6 multicast address on any single interface: Figure 3.2: Host state transition diagram – “Non-Listener” state, when the node is not listening to the address on the interface. This is the initial state for all multicast addresses on all interfaces; it requires no storage in the node. – “Delaying Listener” state, when the node is listening to the address on the interface and has a report delay timer running for that address. CHAPTER 3. DESIGN 29 – “Idle Listener” state, when the node is listening to the address on the interface and does not have a report delay timer running for that address. There are five significant events that can cause MLD state transitions: – “start listening” occurs when the node starts listening to the address on the interface. It may occur only in the Non-Listener state. – “stop listening” occurs when the node stops listening to the address on the interface. It may occur only in the Delaying Listener and Idle Listener states. – “query received” occurs when the node receives either a valid General Query message, or a valid Multicast-Address-Specific Query message. – “report received” occurs when the node receives a valid MLD Report message. It is ignored in the Non-Listener or Idle Listener state. – “timer expired” occurs when the report delay timer for the address on the interface expires. It may occur only in the Delaying Listener state. All other events, such as receiving invalid MLD messages or MLD message types other than Query or Report, are ignored in all states. There are seven possible actions that may be taken in response to the above events: – “send report”. The Report message is sent to the address being reported. – “send done” for the address on the interface. If the flag saying we were the last node to report is cleared, this action MAY be skipped. The Done message is sent to the link-scope all-routers address (FF02::2). – “set flag” that we were the last node to send a report for this address. – “clear flag” since we were not the last node to send a report for this address. – “start timer” for the address on the interface, using a delay value chosen uniformly from the interval [0, Maximum Response Delay], where Maximum Response Delay is specified in the Query. If this is an unsolicited Report, the timer is set to a delay value chosen uniformly from the interval [0, [Unsolicited Report Interval] ]. CHAPTER 3. DESIGN 30 – “reset timer” for the address on the interface to a new value, using a delay value chosen uniformly from the interval [0, Maximum Response Delay], as described in “start timer”. – “stop timer” for the address on the interface. In the following subsection, we explain the problem related with the definition of link-local area in constrained devices. We have represented a flow sequence over the topology drawn in the Figure 3.3 and study the solutions for them. 3.5.1 Link-local area Constrained devices works in Wireless Sensors Networks and the link-local areas are defined by the radio range of the routers. MLD explains clearly that all MLD messages are sent in the link-local area scenario. But how define link-local areas to make MLD work properly. Applying directly MLD in constrained devices, gives some undesired behaviors. To illustrate it the following example over the Figure 3.3. Figure 3.3: Example of scenario 1. N3 sends a report for (Group1, Source7) and reach R1 and R2 CHAPTER 3. DESIGN 31 2. R1 receives the report, start a timer for this pair (G,S) and notify the routing protocol to get the multicast packets from this group and source 3. R2 does the same actions like R1 4. Source 7 sends a multicast data packet in the group1. R1 and R2 has notified they have listeners so they receive the message and broadcast it in the link-local area. 5. N3 is reachable from R1 and R2 thus N3 receives the multicast data message twice. To solve this problem of reachability that the link-local areas define, the nodes send the report message with the pair (G,S) and also filtering the preferred parent for reachability. For instance, N3 should send a report with (Group1, Source7, R1) 3.6 Router state transition diagram Router behavior is more specified by the state transition diagram in the figure 3.4 . A router may be in one of three possible states with respect to any single IPv6 multicast address on any single attached link: Figure 3.4: Router state transition diagram CHAPTER 3. DESIGN 32 – “No Listeners Present” state, when there are no nodes on the link that have sent a Report for this multicast address. This is the initial state for all multicast addresses on the router. – “Listeners Present” state, when there is a node on the link that has sent a Report for this multicast address. – “Checking Listeners” state, when the router has received a Done message but has not yet heard a Report for the identified address. There are five significant events that can cause router state transitions: – “report received” occurs when the router receives a Report for the address from the link. – “done received” occurs when the router receives a Done message for the address from the link. This event is significant only in the“Listeners Present” state. – “multicast-address-specific query received” occurs when a router receives a Multicast-Address-Specific Query for the address from the link. This event is significant only in the ”Listeners Present” state. – “timer expired” occurs when the timer set for a multicast address expires. This event is significant only in the ”Listeners Present” or ”Checking Listeners” state. – “retransmit timer expired” occurs when the timer set to retransmit a Multicast-Address-Specific Query expires. This event is significant only in the ”Checking Listeners” state. There are seven possible actions that may be taken in response to the above events: – “start timer” for the address on the link - also resets the timer to its initial value if the timer is currently running. – “start timer*” for the address on the link - this alternate action sets the timer to the minimum of its current value and either [Last Listener Query Interval] * [Last Listener Query Count] if this router is a Querier, or the Maximum Response Delay in the Query message * [Last Listener Query Count] if this router is a non-Querier. – “start retransmit timer” for the address on the link [Last Listener Query Interval]. CHAPTER 3. DESIGN 33 – “clear retransmit timer” for the address on the link. – “send multicast-address-specific query” for the address on the link. The Multicast-Address-Specific Query is sent to the address being queried, and has a Maximum Response Delay of [Last Listener Query Interval]. – “notify routing +” internally notify the multicast routing protocol that there are listeners to this address on this link. – “notify routing -” internally notify the multicast routing protocol that there are no longer any listeners to this address on this link. The MLD has two modes for router: Querier and Non-Querier but we will not go on detail over them in this final project because for constrained devices, we will not use them. In the following subsection, we explain why we do not use the non-querier router mode. We have created a flow sequence in the topology showed in the Figure 3.3 to explain it. 3.6.1 Querier and Non-Querier mode The two modes of the router produces some undesired problems because of the definition of the link-local areas. Given the routers R1 and R2 and the nodes N1, N2, N3 and N4. Describe an undesired situation. Supposing that R1 and R2 are set up as Querier and the nodes has already done some unsolicited reports to join some multicast groups. 1. R1 sends a general query 2. N1, N2, N3 and R2 receive the query 3. N1, N2 and N3 start their delay timers for their multicast addresses 4. R2 handles the query and realizes the source IP address is numerically lower and change its role as Non-querier 5. N4 will not be queried anymore and will be idle 6. N4 sends a done that only receives R2 since N4 can’t reach R1 and R2 in Non-querier role ignores message CHAPTER 3. DESIGN 34 Hence, N4 could not drop out of the multicast group which sent in the done message. In conclusion, to solve this problem we take the measure of eliminate the non-querier role in the routers and the maintenance of the linklocal areas with the multicast groups will be assured. Without non-querier role, there will be more network traffic since all nodes will query but also improve the performance of the router thus it does not need a timer to keep control of being Querier or non-querier and it does neither need the handler for MLD query messages. CHAPTER 4. IMPLEMENTATION 41 struct ctimer timer; struct ctimer rtx_timer; }; typedef struct mcast_group mcast_group_t; static mcast_group_t mcast_group_table[MAX_NUM_OF_MCAST6_GROUPS]; The data type is called mcast group t. There are differents fields to keep the maintenance correctly. The field used is admin’s information and it is used to know if the multicast group is available and in use. If used is 0, you can overwrite the record with other multicast group. The two next fields mcast group and source belong to the tuple (Group, Source) that we need to store for multicast group. The field state is to control the possible states of the multicast group. They were explained in Section 4.3. Finally, the both timers, timer and rtx time. The first one, to know if there are no more listeners per group and the second one, to send the multicast specific query when the router want to check if there are more listeners. The following code is the structure that the host stores per listening multicast group. struct mld6_listen_group { int used; uint8_t mld_flag; /* Whether there is more listeners than you*/ uint8_t state; uip_ipaddr_t mcast_group; uip_ipaddr_t source; /* Source-filthering*/ uip_ipaddr_t preferred_parent; struct ctimer delay_timer; /* [0, Max.Respons.Delay] */ }; typedef struct mld6_listen_group mld6_listen_group_t; static mld6_listen_group_t listening_table[MAX_NUM_OF_MCAST_LISTENING]; The field used is for the same purpose as in the router’s structure. The fields mld flag and state works like specified in Section 3.5 and Section 4.3, respectively. The next three fields are the addresses necessary for the multicast group, the tuple (Group, Source, Parent), mcast group,source and preferred parent. Finally, the timer delay timer which is used to control when the host have to send a report to keep listening to the multicast group. CHAPTER 4. IMPLEMENTATION 42 Both structures have their functions to keep their maintenance such as add groups, erase groups, find groups or print them. For the mcast group table, we have implemented mcast group new() ,mcast group find () and print mld router table(). For the listening table, we have implemented new listener() ,find listener (),erase listener () and print mld host table(). These functions are also used for debugging and testing. About the timers, to implement the callbacks we have used the library ctimer.h. This library allows to dispatch callbacks when the timer expires. We have already talked about the callbacks in this chapter. To set the timer, you have to choose the timer, the time, the function which will be triggered and the parameters which will be used in the callback function. The parameters has to be referred as a void pointer. The next code present how to set the timer with the callback function. ctimer_set(&aux_mcast->timer, MCAST_LISTENER_INTERVAL *CLOCK_SECOND, timer_group_expired , &aux_mcast); There are some global constants in MLD protocol. All of them explained in the Chapter 3. #define ROBUSTNESS_VARIABLE 2 #define QUERY_INTERVAL 125 #define QUERY_RESPONSE_INTERVAL 10 #define MCAST_LISTENER_INTERVAL 260 #define LAST_LISTENER_QI 1 Chapter 5 Evaluation In this chapter we test and evaluate our protocol in some scenarios which uses the IPv6 stack in Contiki. Therefore, we want to show how MLD works integrated with other components in Contiki OS. We start by explaining the experimental environment. We follow with a description of the evaluation in the different scenarios to check if we achieve the behavior we designed. 5.1 Experimental environment In this section we describe the evaluation environment we use for evaluating our protocol. First of all, we explained which simulator we are using. The simular is Cooja, a tool included in Contiki OS. Then, we explain what modules we have implemented to send asynchronous messages via shell. 5.1.1 Cooja Cooja [38] is a Java-based simulator designed for simulating sensor networks on Contiki OS. The simulator is implemented in Java but the sensor node software is written in C. In Cooja is possible to simulate at different levels; Network level, Operating System level and Machine code level. Cooja supports simulation of nodes of mixed types as well. In the same time, Cooja simulates the radio medium using simple models. Overall, Cooja provides a very usable environment that visualizes radio events, captures packets, monitors variables, visualizes the network, shows nodes’ logs and supports scripting and test automations. The interface of Cooja is shown in Figure 5.1. It eases the development and evaluation of network protocols and embedded development by a great deal. In Cooja, we can develop a contiki application in C, test the code and 43 CHAPTER 5. EVALUATION 44 Figure 5.1: Cooja interface then use the same code to run the application on a real hardware. The code can be compiled to be used in the native configuration of Cooja or based on a specific hardware and Cooja will simulate it. In this final project, we have coded in C, compiled it for specific hardware, Zolertia Z1 1, and used the cooja simulator for testing. 5.1.2 Shell modules Contiki provides an optional command-line shell with a set of commands that are useful during development and debugging of Contiki systems. With Unix-style pipelines, shell commands can be combined in powerful ways. Applications can define their own shell commands that work together with existing commands. We have implemented two modules to have our own commands for the host and for the router. Therefore, we have developed the shell-mld-host and the shell-mld-router modules in the apps folder of Contiki OS. The first module allows to send unsolicited reports, to send done messages and to print the multicast groups that the host is listening. The second module allows the router to print its information about its multicast groups and their states. The commands are sent via serial port. Here, an example 1http://www.zolertia.com/ti CHAPTER 5. EVALUATION 45 about how to use the commands. send_report group source pref_parent send_done group source pref_parent print_host_table print_router_table 5.2 Experimental evaluation In this section, we describe the experiments we run to evaluate our MLD suitable for constrained devices. We have built three different scenarios in LLNs to generate all the possible behaviors of the routers and the hosts (normal working and corner cases). In the following subsections, we will explain each scenario, describing what we command via shell and what it should happen to agree with our protocol objectives. With this sequences, we want to show the proper working of the protocol. 5.2.1 Scenario 1: 1 router and 1 host This scenario is represented in the Figure 5.2. The green circle denotes the transmission range of node 1 while the gray circle denotes its collision with other radios. The size of the radio range can be adapted in the code. Figure 5.2: Scenario 1 First of all we create two multicast groups in the router via shell command. Once they are created -Figure 5.3-, we describe the flow diagram, step CHAPTER 5. EVALUATION 46 by step. Figure 5.3: Router shell with 2 multicast groups on its records The flow sequence continues in Figure Figure 5.4. We wait until the first General Query message from the router (1), the host will get it and it will not send any report back since it has no listener groups yet (2). We send via host shell, a send report 1 1 1 and the host will start a delay timer to send the next report(3). The router will get the report from the host and will notice that there are listeners for this multicast group state = 1 (5). The multicast group timer delay in the host expires and it sends a report(6). Figure 5.4: Scenario 1 Sequence 1 in router shell and host shell Now the sequence continues in Figure 5.5, the listener group in the host for that multicast group will be in idle state (state=1) and mld flag = 1, until it receives a query (7). We send an unsolicited done via shell, send done 1 1 1. No more reports to this multicast group, and we stop the delay timer for CHAPTER 5. EVALUATION 47 that multicast group(8). The router get the MLD done message and goes to CHECKING LISTENERS state (9). The router sends two MLD multicast address speficic queries (10). The host gets the queries (11) and it does not reply since it has already erased that address while sending the MLD done. And finally the router realizes that there is no more listeners when the timer expires and it can be shown with (12) (state=0). Figure 5.5: Scenario 1 Sequence 2 in router shell and host shell With this simulation, we have tested the vast majority of the possible reactions and behaviors of the nodes. We have checked the correct general query operation, to join and leave a group, the 3 possible states of a router, the 2 possible states of a host, and the functions implemented to work with the data structures. But still, we have to test the interaction withing two hosts and a router. Therefore, this one is the next scenario. 5.2.2 Scenario 2: 1 router and 2 hosts In this scenario, we are locating one router (node 1) and two hosts (node 2 and node 3) as it can be shown in Figure 5.6.We will check the interaction within 2 hosts when they join and leave a group. Our given scenario will have a multicast group created (1,1,1) in the router and the node 2 has already join that group. The sequence is in the Figure 5.7. In the figure, it does not appear the router console since it is not that relevant. We show that the listener group is DELAYING,state=0 and mld flag=1 since it is the only one listening the multicast group (1,1,1) (1). The node 3 receives the send report 1 1 1 from the node 2 and it does not do anything since it does not have that multicast group on its listener table(2). We command via shell in the node 3, send report 1 1 1 (3). And the router and the other host will get the message. They will do different proccesses, the router will restart its timer and the host will stop its timer, CHAPTER 5. EVALUATION 48 Figure 5.6: Scenario 2 go to IDLE state, state=0 and set its mld flag=0, noticing that it is not the only one listening that multicast group(4). Figure 5.7: Scenario 2 Sequence 1 two hosts The Figure 5.8 shows how follows the simulation. The sequence continue with an unsolicited send done 1 1 1 from the node 3 (1). The router get the MLD done message (2) and start in the CHECKING LISTENERS state, sending speficic queries (3). The node 2 get the query (4) and send a report to the multicast group got it in the query (5). The router get the MLD report (6) and continue the normal performing, knowing that there are still listeners. With this simulation, we have tested the interaction within hosts. How a host, get a report and check if it is for a multicast group that it has already to pass to idle. Therefore, it does not have to send a report. And, we have evaluated also how a router after getting a done, it checks if there are still listeners. CHAPTER 5. EVALUATION 49 Figure 5.8: Scenario 2 Sequence 1 2 two hosts 5.2.3 Scenario 3: 2 routers and 1 host With the both two earlier scenarios, we have tested most of the possible MLD protocol behaviors. But, we still need to test the preferred parent selection. Hence, we have built and scenario with two router and one host. The scenario is seen in the Figure 5.9. Node 1 and 2 are routers, and node 3 is a host. Figure 5.9: Scenario 3 In this sequence -Figure 5.10-, we command create group 1 1 in both routers(1). Hence, both have the same (G,S). The host send report 1 1 1 wanting to join the (G,S) = (1,1) but only expecting to receive packets from the node 1 (2). Both routers receive the MLD report from node 3, since MLD reports are sent to all link local nodes(3)(4). We can see how the node 1 has written down the existence of listeners (state=1)(5). But node 2 no, state=0 because in the MLD report the preferred parent was 1. The next sequence -Figure 5.11-. We evaluate same problem, the preferred parent addressing, but with MLD done. We command send done 1 CHAPTER 5. EVALUATION 50 Figure 5.10: Scenario 3 Sequence 1 1 1(1). The router 1 receive it and check that it is for itself (2). The router 2 get it but notices that it has another preferred parent address than its address(3). Finally, router 1 starts the process to handle the MLD done message, checking listeners(4). Figure 5.11: Scenario 3 Sequence 2 In this way, with these three scenarios we have tested and evaluated all the behaviors of the MLD protocol. Since we are working with constrained devices to check if the compiled object fits in the device memory is a key point. There is a tool to know the object’s size. The router and the host take up 4kb. Hence, they perfectly fit in our Z1 device which has more than 9kb on its memory. Finally, we can state that our protocol works as we design it and it achieves the space goal on contrained devices. BIBLIOGRAPHY 57 [46] Want, R. An introduction to rfid technology. Pervasive Computing, IEEE 5, 1 (2006), 25–33. [47] Winter, T. Rpl: Ipv6 routing protocol for low-power and lossy networks. Appendix A First appendix. MLD library code /** * \file * Multicast Listener Discovery protocol library * * \author Daniel Bailo <[email protected]> * \date 20/08/2013 * */ #ifndef __MLD6_H__ #define __MLD6_H__ #include "net/uip.h" #include "sys/clock.h" #ifndef MAX_NUM_OF_MCAST6_GROUPS #define MAX_NUM_OF_MCAST6_GROUPS 2 #endif #ifndef MAX_NUM_OF_MCAST_LISTENING #define MAX_NUM_OF_MCAST_LISTENING 4 #endif /*MLD constants*/ #define ROBUSTNESS_VARIABLE 2 #define QUERY_INTERVAL 125 /*seconds within periodical general queries*/ #define QUERY_RESPONSE_INTERVAL 10 #define MCAST_LISTENER_INTERVAL 260 58 APPENDIX A. FIRST APPENDIX. MLD LIBRARY CODE 59 /*(ROBUSTNESS_VARIABLE x QUERY_INTERVAL)+ QUERY_RESPONSE_INTERVAL*/ /* time to decide there is no more listeners for an address*/ #define START_QI 32 /* (QUERY_INTERVAL / 4) */ #define START_COUNT ROBUSTNESS_VARIABLE #define LAST_LISTENER_QI 5 #define COUNT_LAST_LISTENER ROBUSTNESS_VARIABLE #define UNSOLICITED REPORT INTERVAL 10 /* host States*/ #define DELAYING_LISTENER 0 #define IDLE_LISTENER 1 /* Router States*/ #define NO_LISTENERS 0 #define LISTENERS 1 #define CHECKING_LISTENERS 2 /* Struct for hosts*/ struct mld6_listen_group { int used; uint8_t mld_flag; /* Whether there is more listeners than you*/ uint8_t state; uip_ipaddr_t mcast_group; uip_ipaddr_t source; /* Source-filthering*/ uip_ipaddr_t preferred_parent; struct ctimer delay_timer; /* [0, Max.Respons.Delay] */ }; typedef struct mld6_listen_group mld6_listen_group_t; /* * List or array of mld6_groups, as structs as number * of mcast groups listening */ struct mcast_group { int used; uip_ipaddr_t mcast_group; APPENDIX A. FIRST APPENDIX. MLD LIBRARY CODE 60 uip_ipaddr_t source; uint8_t state; struct ctimer timer; struct ctimer rtx_timer; }; typedef struct mcast_group mcast_group_t; /* * Functions to send MLD packets */ void mld_gen_query(); void mld_mas_query(uip_ipaddr_t *group_addr, uip_ipaddr_t *source_addr); void mld_report(uip_ipaddr_t *group_addr, uip_ipaddr_t *source_addr, uip_ipaddr_t *preferred_parent); void mld_done(uip_ipaddr_t *group_addr, uip_ipaddr_t *source_addr, uip_ipaddr_t *preferred_parent); /* * Functions to work with Multicast groups in routers */ #ifdef UIP_CONF_ROUTER mcast_group_t *mcast_group_new(uip_ipaddr_t *group_addr, uip_ipaddr_t *source_addr); mcast_group_t *mcast_group_find (uip_ipaddr_t *group_addr, uip_ipaddr_t *source_addr); void print_mld_router_table(); #endif /* * Functions to work with listeners_group in hosts */ #ifdef RPL_CONF_LEAF_ONLY mld6_listen_group_t *new_listener(uip_ipaddr_t *group_addr, uip_ipaddr_t *source,uip_ipaddr_t *preferred_parent); mld6_listen_group_t *find_listener (uip_ipaddr_t *group_addr, uip_ipaddr_t *source); int erase_listener (uip_ipaddr_t *group_addr, uip_ipaddr_t *source, uip_ipaddr_t *preferred_parent); void print_mld_host_table(); APPENDIX A. FIRST APPENDIX. MLD LIBRARY CODE 61 #endif /* * Handlers for MLD messages */ void mld_query_in(); void mld_report_in(); void mld_done_in(); /* * Callbacks */ static void timer_host_expired (void *listen_group); static void rtxtimer_expired (void *mcast_group); static void timer_group_expired (void *mcast_group); #endif /* __MLD6_H__ */ /** * \file * Multicast Listener Discovery protocol library * * \author Daniel Bailo <[email protected]> * \date 25/08/2013 * */ #include "net/uip.h" #include "contiki-net.h" #include "net/uip-ds6.h" #include "net/uip-icmp6.h" #include "lib/random.h" #include "mld6.h" #include "sys/clock.h" #include "sys/ctimer.h" #define DEBUG 0 APPENDIX A. FIRST APPENDIX. MLD LIBRARY CODE 62 #include "net/uip-debug.h" #define UIP_IP_BUF ((struct uip_ip_hdr *)&uip_buf[UIP_LLH_LEN]) #define UIP_ICMP_BUF ((struct uip_icmp_hdr *)&uip_buf[uip_l2_l3_hdr_len]) #define UIP_ICMP_PAYLOAD ((unsigned char *)&uip_buf[uip_l2_l3_icmp_hdr_len]) #ifdef UIP_CONF_ROUTER static mcast_group_t mcast_group_table[MAX_NUM_OF_MCAST6_GROUPS]; #endif #ifdef RPL_CONF_LEAF_ONLY static mld6_listen_group_t listening_table[MAX_NUM_OF_MCAST_LISTENING]; #endif /* * return A pseudo-random number between 0 and MRD. */ unsigned short random_time (uint16_t MRD) { random_init(clock_time()); return (random_rand() %(MRD)) + 2; } /** * send a general query in MLD to all link local nodes */ void mld_gen_query() { uip_ipaddr_t dest_addr; uip_create_linklocal_allnodes_mcast(&dest_addr); PRINTF("MLD: GENERAL QUERY to "); PRINT6ADDR(&dest_addr); PRINTF("\n"); APPENDIX A. FIRST APPENDIX. MLD LIBRARY CODE 63 uip_icmp6_send(&dest_addr, ICMP6_MLD_QUERY, 0,0); } /** * send a multicast address specific query * in MLD to all link local nodes asking for group_addr * and source_addr */ void mld_mas_query(uip_ipaddr_t *group_addr, uip_ipaddr_t *source_addr) { uip_ipaddr_t dest_addr; int pos; unsigned char *buffer; uip_create_linklocal_allnodes_mcast(&dest_addr); PRINTF("MLD: MCAST SPECIFIC QUERY to "); PRINT6ADDR(&dest_addr); PRINTF(" asking for mcast group "); PRINT6ADDR(group_addr); PRINTF(" and source "); PRINT6ADDR(source_addr); PRINTF("\n"); buffer =UIP_ICMP_PAYLOAD; pos = 0; memcpy(buffer, group_addr, sizeof(uip_ipaddr_t)); pos += sizeof(uip_ipaddr_t); memcpy(buffer +pos, source_addr, sizeof(uip_ipaddr_t)); pos += sizeof(uip_ipaddr_t); uip_icmp6_send(&dest_addr, ICMP6_MLD_QUERY, 0, pos); } /** APPENDIX A. FIRST APPENDIX. MLD LIBRARY CODE 64 * send a report for listening the multicast group group_addr * and source source_addr specifying the preferred_parent */ void mld_report(uip_ipaddr_t *group_addr, uip_ipaddr_t *source_addr, uip_ipaddr_t *preferred_parent) { uip_ipaddr_t dest_addr; int pos; unsigned char *buffer; uip_create_linklocal_allnodes_mcast(&dest_addr); PRINTF("MLD: MCAST REPORT TO "); PRINT6ADDR(&dest_addr); PRINTF(" G="); PRINT6ADDR(group_addr); PRINTF(" S="); PRINT6ADDR(source_addr); PRINTF(" P= "); PRINT6ADDR(preferred_parent); PRINTF("\n"); buffer =UIP_ICMP_PAYLOAD; pos = 0; memcpy(buffer, group_addr, sizeof(uip_ipaddr_t)); pos += sizeof(uip_ipaddr_t); memcpy(buffer +pos, source_addr, sizeof(uip_ipaddr_t)); pos += sizeof(uip_ipaddr_t); memcpy(buffer +pos, preferred_parent, sizeof(uip_ipaddr_t)); pos += sizeof(uip_ipaddr_t); uip_icmp6_send(&dest_addr, ICMP6_MLD_REPORT, 0, pos); } /** * send a done message to the multicast group group_addr APPENDIX A. FIRST APPENDIX. MLD LIBRARY CODE 65 * and source source_addr specifying the preferred_parent */ void mld_done(uip_ipaddr_t *group_addr, uip_ipaddr_t *source_addr, uip_ipaddr_t *preferred_parent) { uip_ipaddr_t dest_addr; int pos; unsigned char *buffer; uip_create_linklocal_allrouters_mcast(&dest_addr); PRINTF("MLD: MCAST DONE TO "); PRINT6ADDR(&dest_addr); PRINTF(" G="); PRINT6ADDR(group_addr); PRINTF(" S="); PRINT6ADDR(source_addr); PRINTF(" P= "); PRINT6ADDR(preferred_parent); PRINTF("\n"); buffer =UIP_ICMP_PAYLOAD; pos = 0; memcpy(buffer, group_addr, sizeof(uip_ipaddr_t)); pos += sizeof(uip_ipaddr_t); memcpy(buffer +pos, source_addr, sizeof(uip_ipaddr_t)); pos += sizeof(uip_ipaddr_t); memcpy(buffer +pos, preferred_parent, sizeof(uip_ipaddr_t)); pos += sizeof(uip_ipaddr_t); uip_icmp6_send(&dest_addr, ICMP6_MLD_DONE, 0, pos); } /* * callback when timer in listener_group (host) expires */ static void APPENDIX A. FIRST APPENDIX. MLD LIBRARY CODE 66 timer_host_expired (void *listen_group) { mld6_listen_group_t *aux =listen_group; aux->mld_flag = 1;/*Set flag, we are the last host*/ PRINTF("Timer host expired send report G="); PRINT6ADDR(&aux->mcast_group); PRINTF("\n"); aux->state=IDLE_LISTENER; mld_report(&aux->mcast_group, &aux->source, &aux->preferred_parent); } /* * callback function when rtx timer expires in router */ static void rtxtimer_expired (void *mcast_group) { mcast_group_t *aux =mcast_group; PRINTF("Send m_a_s query\n"); mld_mas_query(&aux->mcast_group, &aux->source); ctimer_set(&aux->rtx_timer, LAST_LISTENER_QI *CLOCK_SECOND, rtxtimer_expired, aux); } /* * callback function when timer* expires in router */ static void timer_group_expired (void *mcast_group) { mcast_group_t *aux =mcast_group; //NOTIFY ROUTING - PRINTF("Timer group expired \n"); aux->state =NO_LISTENERS; ctimer_stop(&aux->rtx_timer); } /** APPENDIX A. FIRST APPENDIX. MLD LIBRARY CODE 73 { aux = &listening_table[i]; if (aux->used == 1) { aux->state =DELAYING_LISTENER; mrd=random_time(QUERY_RESPONSE_INTERVAL); PRINTF("Host group listener with delay %d \n",mrd); ctimer_set(&aux->delay_timer, mrd *CLOCK_SECOND, timer_host_expired , aux); } } } uip_len = 0; #endif /*RPL_CONF_LEAF_ONLY*/ } void mld_report_in() { uip_ipaddr_t group_addr, source, preferred_parent; mld6_listen_group_t *aux_listener; mcast_group_t *aux_mcast; unsigned char *buffer; uint8_t buffer_length; int pos; buffer =UIP_ICMP_PAYLOAD; buffer_length =uip_len -uip_l3_icmp_hdr_len; pos = 0; memcpy(&group_addr, buffer, sizeof(uip_ipaddr_t)); pos += sizeof(uip_ipaddr_t); memcpy(&source, buffer +pos, sizeof(uip_ipaddr_t)); pos += sizeof(uip_ipaddr_t); memcpy(&preferred_parent, buffer +pos, sizeof(uip_ipaddr_t)); pos += sizeof(uip_ipaddr_t); PRINTF("Received MLD report from "); PRINT6ADDR(&UIP_IP_BUF->srcipaddr); PRINTF("in host \n"); PRINTF(" G = "); APPENDIX A. FIRST APPENDIX. MLD LIBRARY CODE 74 PRINT6ADDR(&group_addr); PRINTF(" Source = "); PRINT6ADDR(&source); PRINTF("\n"); uip_len=0; #if UIP_CONF_ROUTER if(uip_ds6_is_my_addr(&preferred_parent)) { PRINTF("My router ip and the preferred parent are the same\n"); aux_mcast =mcast_group_find(&group_addr, &source); if (aux_mcast == NULL) {// Requested Group is not on the list of mcast group PRINTF("Report discard, no mcast group in router\n"); } else { PRINTF("Group found \n"); switch(aux_mcast->state) { case NO_LISTENERS: // notify routing + aux_mcast->state =LISTENERS; PRINTF("Timer group delay %d, no listeners\n", MCAST_LISTENER_INTERVAL); ctimer_set(&aux_mcast->timer, MCAST_LISTENER_INTERVAL *CLOCK_SECOND, timer_group_expired , &aux_mcast); break; case LISTENERS: PRINTF("Timer group delay %d, listeners\n", MCAST_LISTENER_INTERVAL); ctimer_set(&aux_mcast->timer, MCAST_LISTENER_INTERVAL *CLOCK_SECOND, timer_group_expired , &aux_mcast); break; case CHECKING_LISTENERS: aux_mcast->state =LISTENERS; ctimer_set(&aux_mcast->timer, MCAST_LISTENER_INTERVAL *CLOCK_SECOND, timer_group_expired , &aux_mcast); ctimer_stop(&aux_mcast->rtx_timer); break; default: APPENDIX A. FIRST APPENDIX. MLD LIBRARY CODE 75 PRINTF("Error in router’s state getting report message\n"); break; } } }else PRINTF("Report with preferred parent not my router ip\n"); #endif /*UIP_RPL_ROUTER*/ #if RPL_CONF_LEAF_ONLY PRINTF("REPORT in HOST \n"); aux_listener =find_listener(&group_addr, &source); if (aux_listener->state == DELAYING_LISTENER) { if (aux_listener->used) { ctimer_stop(&aux_listener->delay_timer); //Clear flag we were not the last host aux_listener->mld_flag = 0; aux_listener->state =IDLE_LISTENER; } } #endif /*RPL_CONF_LEAF_ONLY*/ uip_len=0; } void mld_done_in() { uip_ipaddr_t group_addr, source, preferred_parent; mcast_group_t *aux; unsigned char *buffer; uint8_t buffer_length; int pos; uip_len = 0; #if UIP_CONF_ROUTER buffer =UIP_ICMP_PAYLOAD; pos = 0; memcpy(&group_addr, buffer, sizeof(uip_ipaddr_t)); pos += sizeof(uip_ipaddr_t); memcpy(&source, buffer +pos, sizeof(uip_ipaddr_t)); pos += sizeof(uip_ipaddr_t); APPENDIX A. FIRST APPENDIX. MLD LIBRARY CODE 76 memcpy(&preferred_parent, buffer +pos, sizeof(uip_ipaddr_t)); pos += sizeof(uip_ipaddr_t); if(uip_ds6_is_my_addr(&preferred_parent)) { PRINTF("Received MLD done from "); PRINT6ADDR(&UIP_IP_BUF->srcipaddr); PRINTF(" in router \n"); PRINTF(" G = "); PRINT6ADDR(&group_addr); PRINTF(" Source = "); PRINT6ADDR(&source); PRINTF("\n"); aux=mcast_group_find(&group_addr, &source); if (aux == NULL) { // Requested Group is not in the list of mcast group PRINTF("Report discard, no this mcast group in router\n"); } else { switch(aux->state) { case LISTENERS: aux->state =CHECKING_LISTENERS; PRINTF("STATE CHECKING LISTENERS \n"); ctimer_set(&aux->timer, MCAST_LISTENER_INTERVAL *CLOCK_SECOND, timer_group_expired, aux); ctimer_set(&aux->rtx_timer, LAST_LISTENER_QI *CLOCK_SECOND, rtxtimer_expired, aux); break; default: PRINTF("Error in router’s state receiving mld_done\n"); break; } } }else printf("Done with other preferred_parent address\n"); #endif uip_len = 0; APPENDIX A. FIRST APPENDIX. MLD LIBRARY CODE 77 }