Mihály Orosz

PhD Gábor Hosszú
email: hosszu@nimrud.eet.bme.hu

Responsible Source Multicasting

Keywords: IP multicast, Routing, ASM, SSM, Multicast, dynamic address allocation mechanism

There is no effective method to support IP level Internet wide multisource multicast sessions, that can be easily used from almost every ISP There are several protocols implementing the necessary functionality, but the penetration of them is really low recently. The most obvious work all-round is using SSM -Source Specific Multicasting, in which, the IP multicast session is identified by the multicast group address and the source's unicast IP address. SSM allows using all the SSM address range for every source IP addresses and limits the address allocation problem inside the host of the source; however, its significant drawback is that the SSM has no native support to create multicast sessions with more than one source; it uses separate source specific distribution trees for every single source therefore it needs more resources on the router side. The alternative solution for supporting multisource multicast session is the ASM -Any Source Multicasting. However, its significant drawback is the lack of Internet wide dynamic address allocation. To address the recent problems of the Internet wide multisource multicast session a novel IP multicast service model, the Responsible Source Multicasting -RSM is introduced in this paper. RSM uses shared distribution trees like ASM; however, builds a reverse path tree towards an appropriate well-known unicast IP address like SSM. The paper demonstrates that this novel multicast routing protocol handles Internet wide multisource multicast sessions. The paper also shortly presents the DAMA -Dynamic Address Allocation of Multicast Addresses protocol for dynamic multicast IP address allocation, which works in a strong collaboration with the RSM.

Introduction

This paper describes RSM, a new IP level multicasting service model. This service model consists of two components; a Dynamic Address Allocation of Multicast Addresses (DAMA) session management protocol and the Responsible Source Multicast (RSM) routing protocol [START_REF] Orosz | Global Address Allocation for Wide Area IP-Multicasting" chapter in book[END_REF]. The RSM routing protocol can be implemented as an extension to the most commonly used Sparse-Mode Protocol Independent Multicast (PIM-SM) protocol [START_REF] Fenner | Protocol Independent Multicast -Sparse Mode (PIM-SM): Protocol Specification (Revised), Internet Engineering Task Force, Network Working Group, Request for Comments[END_REF]. Although RSM routing may use the underlying unicast routing to provide reverse-path information for multicast tree building, it is not dependent on any particular unicast routing protocol.

To highlight the problem needs to be addressed if Internet wide sessions are needed, we compare the unicast and multicast sessions from service registration to data exchange aspects [START_REF] Zappala | The Multicast Address Allocation Problem: Theory and Practice[END_REF]. Most of the unicast services on the Internet are registered in the Domain Name System (DNS). This service directory is based on the unicast address of the host offering the service. In order to join to a service running on a server only the unicast IP address of the server is required by the underlying IP subsystem. The routing is done automatically using the unicast IP addresses. However, there is no commonly used (operating system supported) service registration mechanism for global multisource multicast services that provides the necessary information for the multicast routing protocol as well.

In order to examine more deeply the possible solution of the global multicast address allocation, we should consider separately the two main groups of the multicast service model, namely the Source-Specific Multicast (SSM) [START_REF] Holbrook | Source-Specific Multicast for IP[END_REF] and the Any-Source Multicast (ASM) [START_REF] Hosszú | Az internetes kommunikáció informatikai alapjai, Első kiadás[END_REF].

Multicast routing background

The problem behind the Internet-wide penetration of ASM infrastructure is the lack of simple, useful dynamic address allocation mechanism, that lets the short range of multicast IP addresses available for the applications. Beside some solutions are developed recent years, the problem is still unresolved Internet-wide [START_REF] Savola | Overview of the Internet Multicast Addressing Architecture[END_REF]. The wellknown solutions can be divided into two groups. One uses real dynamic address allocation (dynamic allocation group), the other tries to avoid dynamic allocation (limited or static allocation group). Dynamic Allocation Group. Most important representatives of the dynamic allocation group are PIM-SM/MBGP/MSDP architecture, and Multicast Address Allocation Architecture (MAAA). The elements of the PIM-SM/MBGP/MSDP architecture are the following: (i) improved BGP inter-domain routing protocol, Multiprotocol BGP (MBGP) that can handle not only unicast, but also multicast interdomain routing [START_REF] Hosszú | Current Multicast Technology[END_REF]; (ii) PIM-SM intra-domain multicast routing protocol [START_REF] Kim | Anycast Rendezvous Point (RP) mechanism using Protocol Independent Multicast (PIM) and Multicast Source Discovery Protocol (MSDP)[END_REF], [START_REF] Orosz | DNS-Based Allocation of Multicast Addresses" chapter in book, Encyclopedia of Internet Technologies and Applications[END_REF]; and (iii) Multicast Source Discovery Protocol (MSDP) that links PIM-SM and MBGP to enable Internet-wide ASM routing [START_REF] Mcbride | Source Discovery Protocol (MSDP) Deployment Scenarios[END_REF].

The idea behind the use of the MBGP for multicast routing was to use hierarchical multicast routing based on hierarchical unicast routing [START_REF] Savola | Overview of the Internet Multicast Routing Architecture[END_REF]. MBGP uses peering mechanism to exchange multicast routing information between MBGP routers (between domains). Every MGBP peer links connects two MBGP routers via TCP protocol, and the peers cover all the Autonomous Systems (AS). Using MBGP routers does not need to know all the other routers, but the directly connected ones. Obviously every MBGP router has to participate in the intra domain routing for the domain it belongs to. MBGP handles unicast and multicast inter-domain routings as well; however, it uses different peer connections between domains for unicast and multicast routing [START_REF] Meyer | GLOP Addressing in 233/8[END_REF].

One of the most relevant members of the dynamic allocation group is MAAA [START_REF] Mockapetris | Domain names -implementation and specification, STD 13[END_REF], [START_REF] Orosz | Global Address Allocation for Wide Area IP-Multicasting" chapter in book[END_REF]. MAAA uses three-level hierarchy for address allocation; domain, intra-domain, and host-to-network levels. The Address Allocation Protocol (AAP) is used for intradomain address allocation, and the Multicast Address Dynamic Client Allocation Protocol (MADCAP) is used by hosts to obtain multicast addresses from a Multicast Address Allocation Server (MAAS). It is noteworthy that the MAAA infrastructure is quite complex, and this disadvantage makes hard to implement the system Internetwide. Static Allocation Group. GLOP is a typical member of the static allocation group. It uses static (limited) assignment of multicast addresses based on AS numbers [START_REF] Rajvaidya | Analysis of routing characteristics in the multicast infrastructure[END_REF]. The AS number is hardcoded into GLOP address arrays. GLOP uses the 233/8 (233.0.0.0... 233.255.255.255) address range only. Every AS has 233.X.Y/24 multicast address range, where X and Y are related to the sequence number of a specific AS. Besides its simplicity, GLOP has two major disadvantages. First, every AS has only 255 multicast addresses, and there is no possibility to extend the range, if it is not enough inside the AS. Second, GLOP has not any method to allocate the multicast addresses inside the ASs. SSM is another good example for the limited (static) allocation group [START_REF] Kumar | The MASC/BGMP Architecture for Interdomain Multicast Routing in ACM SIGCOMM[END_REF], [START_REF] Savola | Lightweight Multicast Address Discovery Problem Space[END_REF]. SSM reuses every multicast address in every host having unicast address as well, because the SSM session is identified by the multicast group address and the unicast address of the source at the same time (S, G states in routers). Although SSM is a creative solution for the limited multicast address range, it has hard limitations. SSM uses different distribution trees for every source, and in addition every listener (drain) has to join every distribution tree in a multisource environment [START_REF] Bhattacharyya | An Overview of Source-Specific Multicast (SSM)[END_REF]. Therefore, it is necessary to use an application level protocol to identify the sources related to a specific multicast session.

Evidently, there is no need for a complicated address allocation using SSM, but an effective, Internet wide address allocation mechanism is needed for ASM. In addition, the drawback of SSM comes from the one-way source rooted trees it uses, because the routers have to set up different distribution trees for every source in a multi-source session, and also an Application Level mechanism is needed to let receivers to get information about sources, and to join all the trees rooted at the sources.

Solution

A novel method called Responsible Source Multicasting (RSM) was developed to eliminate the drawbacks of existing SSM and ASM routing mechanisms, and to incorporate advantages of them.

Overview of RSM routing

The proposed routing mechanism, the RSM uses ASM routing, but it assigns a responsible source (RS) unicast IP address for every multicast session (multicast group). The assignment of unicast IP addresses enables to use the DNS system for registration of the dynamically allocated multicast IP addresses. Furthermore the RSM multicast routing protocol uses this unicast address of the RS to maintain routes in MRIB table. RSM routing uses information taken directly from the unicast routing table related to unicast address of the RS. MRIB is populated with the interface for a given RSM multicast group address that is the same interface from the unicast routing table for the unicast address of the RS related to the given multicast group. RSM routing can be implemented as an extension for PIM multicast routing. PIM relies on an underlying topology-gathering protocol to populate a routing table (MRIB) with routes. The routes in MRIB may be taken directly from the unicast routing table, or it may be different and provided by a separate routing protocol such as MBGP or RSM [START_REF] Mcbride | Source Discovery Protocol (MSDP) Deployment Scenarios[END_REF]. Regardless of how it is created, the primary role of the MRIB in the PIM protocol is to provide the next hop router along a multicast-capable path to each destination subnet. The MRIB is used to determine the next hop neighbor to which any PIM Join/Prune message is sent. Data flows along the reverse path of the PIM Join messages. Thus, in contrast to the unicast RIB, which specifies the next hop where a data packet would take to get to some subnet, the MRIB gives reverse-path information, and indicates the path that a multicast data packet would take from its origin subnet to the router that has the MRIB. Using RSM as a PIM extension eliminates the need of inter-domain routing mechanisms and usage of RPs, while provides the same functionality as ASM multicast routing has. Moreover, the participants can be sources and listeners at the same time in one single session, the sessions can be multi-source. Using source routed trees it provides the robustness of SSM.

The RSM is ready for easy Internet wide deployment, because only the new routing extension is needed at the router side and the rest (DAMA protocol) can be handled on the clients (as an operating system or application level standard library) that provides the followings: (i) simple (DNS based) service registration/discovery, (ii) dynamic address allocation, and (iii) fair allocation mechanism (network topology related). Fig. 2. Multisource RSM session.

Dependency on DAMA protocol

The Responsible Source Multicasting (RSM) uses Dynamic Address Allocation of Multicast Addresses (DAMA) protocol for dynamic address allocation, service registration, and service discovery. RSM inherits the favorable properties of DAMA like simple distribution and penetration, robustness and fairness. The RSM multicast routing uses Responsible Source Rooted Trees as distribution trees. Each Responsible Source Rooted Tree is identified by a multicast group address and a responsible source unicast address. The multicast routing can use simple Reverse Path Forwarding or Shortest Path Forwarding algorithms to make routing decisions, because the location of the root of the tree, (the responsible source) determined by its unicast IP address. This solution eliminates the need for complex hierarchical multicast routing.

For an RSM session the usage of the DAMA protocol is only necessary by the first member of the session for the registration of the Responsible Source. After this, any other member can easily join the RSM session using standard ICMP protocol or simply sending IP packets to the multicast group address.

Overview of DAMA protocol

In the DAMA project a protocol was constructed from the idea about using existing well-tried Domain Name System (DNS) for communication needs of multicast address allocation and service discovery. DAMA is an operating system software library for applications and a modified DNS server for the special DAMA top level domain implementing the address allocation and RS registry.

The applications use the operating system extension, the DAMA Library to allocate multicast address and for service discovery. The operating system extension offers the following services to the application: (i) obtaining new (free) RSM multicast address for the service; (ii) releasing unused multicast addresses after usage; (iii) finding services of given hosts; and (iv) finding sources of multicast sessions based on multicast address (querying RS unicast IP address).

The DAMA Library uses DAMA DNS server as distributed database system. DAMA uses standard DNS protocol [START_REF] Mockapetris | Domain names -implementation and specification, STD 13[END_REF] for communication between DAMA library at hosts and the DAMA DNS server. The database records for address allocation are stored in standard DNS Resource Records.

For starting an RSM multicast session (session initialization) a server needs a multicast address. It asks the DAMA library for it. Every host has IP-multicast address tables with 256 addresses for unicast addresses each. The DAMA library asks the DAMA name server to allocate an address based on its unicast address. If the DNS queries goes through network address translation NAT the altered unicast address; visible for DAMA name server will be used. If the name server has unmapped IP-multicast address, it maps to the unicast address of the host (in the host map every unicast address has 256 slots for multicast addresses). If there is an error or no more addresses available, then DAMA name server returns an error to the DAMA library. DAMA library allocates the offered address for the unicast address, and sends it to the applications, or signals the error. When the multicast session finishes (session termination) the application sends dispose message to the DAMA library, which sends unmap messages to the name server.

Every allocated and mapped address has timeout assigned. Within the timeout keep-alive message must arrive to renew the allocation (session holding). Every keepalive message must be acknowledged. If a keep-alive message had not been acknowledged or renewal refused, the application must finish sending to the related multicast address (session failure).

RSM protocol description

Responsible source (RS) is a unicast IP address of the host assigned as responsible source for a given RSM multicast address by DAMA protocol. This RSM multicast group address and RS unicast IP address assignment information is freely available using DAMA. RS is identified by the RSM multicast group address and its responsible IP address for the RSM multicast group address. Member is a host participating in the RSM multicast session and is different from RS. Fake source is an RS that is not participating in the RSM multicast session (not sending or receiving packets). Sender is a member or the RS that sends packets for the RSM multicast session. Receiver is a member or the RS that receives packets for the RSM multicast session. Basics of RS unicast address registration. The dynamic allocation of RSM multicast group addresses is handled by DAMA protocol. For the basic understanding it is necessary to highlight the address allocation process in general.

The DAMA process starts when a host wants to initiate a new RSM multicast session. It calls the DAMA registration function to ask for a new RSM multicast group address. It is noteworthy that RSM multicast group addresses planned to come from a dedicated RSM multicast group address range reserved by IANA in the future. DAMA protocol assigns the RS unicast address of the requester to a new RSM multicast group address and makes it available as a DNS zone entry under the dama.org zone. If a DNS "IN A" query initiated for the dama.org zone in DAMA format containing the RSM multicast group address the RS unicast address for the multicast group would be the response. If an RSM capable router needs to join the given RSM multicast group it initiates the DNS query mentioned above, and selects the interface from the unicast routing table related to the unicast IP address come as results for the query. This interface will be populated to MRIB for the (*,G) routing state, where the G is the multicast IP address of a multicast group.

As a result from the above procedure it is obvious that at least one host per RSM session has to be capable of using DAMA protocol to register its unicast IP address as the Responsible Source. It is advised for every participant to use DAMA as service registry anyhow.

Workflow

Initialization. One DAMA capable host in the RSM session obtains an available multicast group address and registers its unicast IP address as Responsible Source for that multicast session using DAMA protocol. In such a way, it becomes the RS. Maintenance. Any host can freely send packet to the given multicast group address implicitly joining the session or can explicitly join using IGMP protocol. These hosts become members. If a router receives a multicast packet from a directly connected source or receives an IGMP register message for a given group address (for the DAMA multicast address range) it uses PIM protocol for routing decisions. If an MRIB query is performed to find the RPF neighbor during PIM routing a DAMA formatted DNS query is made to insert the relevant entry to the MRIB. This entry is constructed regarding the unicast routing information related to unicast IP of the RS of the given multicast group. Any host can freely leave the session using IGMP explicitly or implicitly as a result of reaching PIM timeouts.

Disposal. On request from the RS for disposal or on reach of session timeout the dynamically allocated RSM multicast address is freed in DAMA and become reusable. Depending on PIM MRIB entry timeouts the freed multicast group addresses can be alive for a short period, so immediate allocation of disposed addresses should be avoided in DAMA protocol.

Performance issues of RSM

The main issues of RSM are the consequences of using DNS system. Routing decisions have to be made quickly, but if a protocol used during the routing mechanism is an application level network protocol like DAMA significant delay can occur. Therefore instead of waiting for the result of the DAMA DNS query, RSM drops or delays the packet after a new DAMA query initiated. When the DAMA response arrives, the necessary information for the (*,G) session is populated to MRIB and upcoming multicast packets for the given multicast group can be routed as normalbased on the PIM-SM protocol. This asynchrony behavior between the initialization of collecting the necessary information for MRIB during routing decision and MRIB updates on arrival of information can cause significant delays between a new member starts joining process and technically joins the session (receives packets). This delay occurs on every router between the joining member and the distribution tree, as every router has to query the RS IP address using DAMA. This delay can be reduced significantly if PIM JOIN message contains the RS IP address and eliminates the uses of DAMA at intermediate routers.

Another performance related problem is that RSM can have only a limited address range from the available multicast group address ranges. All the RSM session over the Internet shares this address range. If the number of RSM session needed are higher than the size of the available address range no more sessions can be started until one of the existing sessions closes. The address allocation takes place in order of the arrival of the allocation requests; therefore Denial of Service (DOS) attacks can be easily made against RSM. To reduce the negative effect of DOS attacks and to provide low level fairness, DAMA divides the available address range based on IP address classes. This limits effects of DOS attacks to C class subnetworks and shared the address range equally between these networks. To make address allocation more effective and allow the allocation of whole available address range even when the requirements are coming from a limited set of sub networks, some improvements on temporary address range handover and forced takeover must be implemented in DAMA.

Additional performance improvement can be realized taking into account that a responsible source distribution tree can be suboptimal for multiple sources. In RSM always the RS is the root of the tree regardless of the link properties and utilization and the characteristics of the traffic. An application layer protocol can be used to select the RS from the participants of the session prior RSM initialization. This protocol can take into account the given application specific traffic pattern and expected topology for the RS selection making the distribution tree optimal.

Multisource sessions can suffer from overloading low bandwidth members when high bandwidth sources and other high bandwidth members are exists. If an application can handle receiving from limited set of source to take care of low bandwidth members the high bandwidth members and sources can share high bandwidth traffic while low bandwidth members still be part of the session and receives lower bandwidth traffic. Some minor improvements can be added for handling the denial of some sources due to this bandwidth limitation. This can be achieved by maintaining exclusion list for sources and RSM multicast groups for interfaces (like SSM does in its membership database) at router side.

Conclusions

The proposed novel service model, Responsible Source Multicasting (RSM) lets fast penetration of multisource multicast application became reality. The most significant advantage of RSM in penetration point of view is that there is no need for complex setup either at intra domain or at local network level. The PIM RSM Extension is planned to be submitted as Internet-Draft. On its acceptance, future PIM implementations and routers sold will support it. It will make possible for a user having a modern RSM capable router to easily join to RSM sessions without complex network and routing configuration tasks.

While RSM model incorporates the advantages of the different multicast address allocations and routing protocols, eliminates their disadvantages having been blocking their penetration. However, further simulations and experimental measurements are necessary to validate the model and to provide performance measures.

Besides the RSM lets multicasting penetration Internet-wide, it is far away to start deployment. The standardization of the underlying DAMA protocol is needed first, and then an RSM protocol implementation and standardization is necessary in order to let deployment begin. Finally routers need to be upgraded with RSM PIM extension to get RSM work. Beside this process looks quite complex, it is far simpler than processes necessary for the deployment of any other solutions.

A novel method for IP level multisource multicast routing was developed to address the problem of slow penetration of multisource multicasting capable routing protocols. The new method called Responsible Source Multicasting (RSM) can be easily deployed Internet wide not having dependencies on non-widely used complex application level protocols that have to be maintained both intra domain and inter domain scopes like MAA but providing the same functionality as ASM. RSM routing is implemented as PIM extension and depends only on DNS that makes its penetration simple. The delay caused by the Dynamic Address Allocation of Multicast Addresses (DAMA) protocol at routers can be reduced significantly if PIM JOIN message contains the RS IP address and eliminates the uses of DAMA at intermediate routers. This PIM JOIN extension with RS IP address in case of RSM group address range is given planned to be implemented shortly.

RSM service model planned to be applied to Mobile Ad-Hoc Networks (MANET) [START_REF] Badameh | Multicast Routing Protocols in Mobile Ad Hoc Networks: A Comparative Survey and Taxonomy[END_REF] and can significantly reduce the multicast routing protocol overhead that is necessary for tree building in MANET Multicast routing protocols. Multicast OLSR (MOLSR) [START_REF] Laouiti | Multicast Optimized Link State Routing[END_REF] protocol uses SOURCE CLAIM message to identify the multicast source for a given multicast group and use the information from this message to build a source rooted tree. The SOURCE CLAIM messages are flooded over the MANET regularly resulting large routing overhead. RSM service model planned to be applied for MOLSR where SOURCE CLAIM messages will be replaced by DAMA registration messages. The RSM for MOLSR uses RS as "Originator Address" defined in the protocol.

The DAMA fairness, DOS prevention mechanism and temporary address handover/takeover mechanisms are going to improved, implemented in the next phase of the DAMA project.

Fig. 1 .

 1 Fig. 1. Multisource SSM session.

Acknowledgement

The work reported in the paper has been developed in the framework of the project "Talent care and cultivation in the scientific workshops of BME". This project is supported by the grant TÁMOP -4.2.2.B-10/1-2010-0009.


Volker Richter
email: richter@ifn.et.tu-dresden.de

Rico Radeke

Ralf Lehnert

A two Layer Guaranteed and Sustained Rate based Scheduler for IEEE 802.16-2009 based WiMAX Networks

Keywords: WiMAX, IEEE 802.16, QoS, Scheduling, Traffic Shaping

Worldwide Interoperability for Microwave Access (WiMAX) based on the IEEE 802.16-2009 standard is a serious competitor of Long Term Evolution (LTE) for cellular networks providing high data rates to mobile users. To support various multimedia applications the Quality of Service (QoS) support is a crucial function. While the IEEE 802.16-2009 standard defines five service classes to support the QoS requirements of various multimedia applications, the algorithms and especially the scheduling algorithms to enforce these requirements have not been specified for vendor differentiation. We propose a scheduling algorithm allocating resources according to the guaranteed and sustained rates of each connection, in contrast to common two layer scheduling approaches differentiating between service classes. Simulation results show that our scheduler is able to fulfill the QoS requirements of connections defined by the IEEE 802.16 standard.

Introduction

The IEEE 802.16 standard family allows different vendors to build WiMAX systems compatible with each other. Since the introduction of the standard amendment IEEE 802.16e [START_REF]2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands and Corrigendum 1[END_REF] the physical layer WirelessMAN-OFDMA allows the deployment of cellular networks supporting mobile users with high data rates. Therefore, WiMAX is a serious competitor to Long Term Evolution (LTE), if no existing 3GPP infrastructure is present.

On top of different variants of the physical layer, the standard defines a mostly common Medium Access Control (MAC) layer, which is responsible for functions such as connection management and resource allocation. One substantial property of this MAC layer is the All-Internet Protocol approach. All services like Voice over Internet Protocol (VoIP), video streaming or web surfing are provided through Internet Protocol (IP) connections. In order to ensure the functionality of diverse applications, the IEEE 802.16-2009 standard provides a QoS concept consisting of various QoS parameters including five service classes.

Figure 1 illustrates the WiMAX resource allocation process according to our studies of the standard document [START_REF]IEEE Standard for Local and metropolitan area networks Part 16: Air Interface for Broadband Wireless Access Systems. IEEE Std[END_REF]. In the first step, packets from higher layers All header information such as the IP source and destination addresses and the port numbers can be used for packet classification. Afterwards, packets belonging to one connection are stored in a queue. To enforce QoS parameters as the maximum data rate, negotiated during connection establishment, a traffic shaping algorithm is applied on each connection. Our traffic shaping algorithm has been described in detail in [START_REF] Richter | 2009 compliant Traffic Shaping Algorithms for WiMAX Networks[END_REF] and will be summarized in section 3.1. Based on the results of the traffic shaping, the current queue size and the QoS parameters the scheduling algorithm distributes the available radio resources to all connections in the fourth process step of figure 1. Packets are segmented and concatenated to MAC Protocol Data Units (PDUs) to fit into assigned radio resources. Finally, the transmitted data volume is fed back to the traffic shaping algorithm in order to calculate the correct data rates for the next frame. However, the IEEE 802.16-2009 standard neither defines the scheduling nor the traffic shaping algorithm to ensure the adherence to the admitted QoS parameters. Therefore, various scheduling algorithms have been proposed for WiMAX.

Resource Allocation in WiMAX

One class of scheduling algorithms for WiMAX are optimization approaches. For example, the authors of [START_REF] Ermini | Realtime Traffic Scheduling for Missed Deadline Minimization in Point-to-Multipoint OFDMA Systems[END_REF] and [START_REF] Song | A Cross-Layer WiMAX Scheduling Algorithm Based on Genetic Algorithm[END_REF] define a objective function for the scheduling problem and solve it by applying heuristic methods. Another common approach is to divide the scheduling problem into two layers. The first layer sched-uler distributes the available resources to groups of connections belonging to one service class. The second layer schedulers allocate these resources to specific connections. An overview of this scheduler class can be found in [START_REF] Dhrona | A performance study of scheduling algorithms in Point-to-Multipoint WiMAX networks[END_REF]. The author of [START_REF] Chen | A Service Flow Management Strategy for IEEE 802.16 Broadband Wireless Access Systems in TDD Mode[END_REF] uses a Deficit Fair Priority Queue Scheduler for the first layer scheduling. For the second layer scheduling the algorithms Earliest Deadline First (EDF), Weighted Fair Queuing (WFQ) and Round Robin (RR) are applied according to the delay requirements of the service classes.

In contrast to the common two layer scheduling, our proposed scheduler does not differentiate between service classes. It only differentiates between guaranteed and sustained rates defined for each connection in the standard. Simulation results show that our scheduler is able to fulfill the QoS requirements of connections defined by the IEEE 802.16-2009 standard [START_REF]IEEE Standard for Local and metropolitan area networks Part 16: Air Interface for Broadband Wireless Access Systems. IEEE Std[END_REF].

In the first section, the IEEE 802.16-2009 QoS concept is introduced based on our studies of the current standard document [START_REF]IEEE Standard for Local and metropolitan area networks Part 16: Air Interface for Broadband Wireless Access Systems. IEEE Std[END_REF]. Subsequently, we describe our proposal for the WiMAX resource allocation including a summary of our traffic shaping approach, which is closely related to the proposed scheduling algorithm. The focus of this paper lies on our Two Rate based Scheduling algorithm, which will be described in detail. These algorithms have been implemented in a network simulator ns-2 based WiMAX model. Our simulation results are presented in section 4. Finally, we conclude our paper and give an outlook on future work.

The IEEE 802.16-2009 QoS Concept

The central element of the IEEE 802.16-2009 connection oriented MAC layer is the Service Flow (SF). To each SF belongs a QoS parameter set. When a SF is activated a transport connection is assigned to it ( [START_REF]IEEE Standard for Local and metropolitan area networks Part 16: Air Interface for Broadband Wireless Access Systems. IEEE Std[END_REF], p. 366).

As mentioned before, the standard defines five service classes, which are part of the QoS parameter set. For the Downlink (DL) transmission they are denoted as Data Delivery Services ( [START_REF]IEEE Standard for Local and metropolitan area networks Part 16: Air Interface for Broadband Wireless Access Systems. IEEE Std[END_REF], p. 422). In contrary, the service classes are named Scheduling Services for the Uplink (UL) channel. They provide different UL bandwidth grant and request mechanisms optimized to specific traffic characteristics and requirements.

The service class Unsolicited Grant Service (UGS) supports real time connections with fixed interarrival times and packet sizes. Typically VoIP without silence suppression generates such a traffic pattern. Currently, VoIP with silence suppression is used by many applications. To adapt to the different packet size in active and silence periods, the service class Extended Real-Time Variable Rate (ERT-VR) has been introduced with the IEEE 802.16e standard [START_REF]2: Physical and Medium Access Control Layers for Combined Fixed and Mobile Operation in Licensed Bands and Corrigendum 1[END_REF]. Another realtime service class represents Real-Time Variable Rate (RT-VR). It is designed for video transmissions with variable interarrival times and packet sizes. Non realtime service classes are Non Real-Time Variable Rate (NRT-VR) and Best Effort (BE). BE does not provide any guarantees for connections. In contrast to BE, NRT-VR includes a minimum data rate, which is necessary to avoid time outs of File Transfer Protocol (FTP) connections.

The IEEE 802.16-2009 standard defines for each service class a set of mandatory QoS parameters. The most important in terms of data rates are the Maximum Sustained Traffic Rate (MSTR) and Minimum Reserved Traffic Rate (MRTR). The MSTR defines the average maximum data rate which can be allocated for the corresponding connection. It is measured in bit per second, excluding MAC and physical overhead ([2], p. 1285). This parameter allows the network operator to limit the connection to a certain speed, often used for mobile data flat rate offers. On the other hand, the MRTR describes the average minimum data rate which must be allocated for connections. Also, it is expressed in bit per second without MAC and physical overhead ([2], p. 1285). This parameter guarantees the functionality of user applications, also in cases of a highly loaded cell. Furthermore, it is defined by the standard, that only resources should be assigned for data currently stored in the queues. Therefore, it is possible, that a connection receives less resources than the MRTR allows. resources up to the MSTR boundary. Since the MSTR is defined as an average over time, unused data volumes can be used later to exceed this limit. If the system is in an overloaded state, the resource allocation process has primarily to fulfill the guaranteed data rate. Therefore, firstly data volumes are assigned to reach the MRTR. Also, the MRTR is specified as an average over time, which permits a short overshot of the average value. In order to configure the time interval used for calculation of the averaged rate, the IEEE 802.16-2009 standard specifies the QoS parameter Time Base (TB) given in ms ([2], p. 1306). The combination of TB and MSTR or respectively MRTR defines the amount of data sending permissions, which can be shifted from idle to busy periods of a connection.

Table 1 summarizes the service classes for DL and UL including their mandatory QoS parameters. Since the service class UGS was designed for connections with a constant data rate, only the MRTR and TB parameters are present. In contrast, BE does not provide any guarantees. Therefore, the MRTR is zero or absent. All other service classes include both data rate QoS parameters to support fluctuating data rates.

Service classes DL

UGS ERT-VR RT-VR NRT-VR BE

Service classes UL

UGS ertPS rtPS nrtPS BE MSTR X X X X MRTR X X X X TB X X X X X
Table 1. Service classes and their mandatory (X) QoS parameters

WiMAX Resource Allocation

In the following section, we will firstly summarize our traffic shaping algorithm, which was presented in [START_REF] Richter | 2009 compliant Traffic Shaping Algorithms for WiMAX Networks[END_REF]. This algorithm is applied on both the MSTR and MRTR of each connection in order to calculate the data volume necessary in the next frame to obtain these rates within the current Time Base (TB) interval.

Based on these values, our scheduling algorithm distributes the radio resources. This scheduling algorithm will be presented in section 3.2.

WiMAX Traffic Shaping Algorithm

The traffic shaping will be described for the MSTR calculation denoted as R M S .

It is equivalent for the MRTR calculation. The data volume S, which has to be transmitted to reach the R M S within the interval T B is:

S = R M S • T B (1)
This data volume has to be transmitted within all frames n belonging to one

T B . n = T B T F (2)
Here, T F denotes the frame duration, which is typically 5 ms [START_REF][END_REF]. To calculate the maximum schedulable data volume S k of the next frame k, all previous transmitted data volumes S i within the current T B period have to be subtracted from S. Therefore, all allocations made in frames from k -n + 1 to k -1 have to be considered. This can be expressed as:

S k = R M S • T B - k-1 i=k-n+1 S i (3)
S k is the maximum data volume which can be scheduled to satisfy R M S . In the next execution of the algorithm, to calculate the data volume S k+1 for the following frame k + 1, the considered time interval T B is shifted by one frame duration T F . Therefore, allocations made in the frames from k -n + 2 to k are subtracted.

As described in section 2, the IEEE 802.16-2009 standard requires that only resources for available data in the queues shall be assigned. Therefore, a minimum function between S k and the current queue size S Q of a connection is introduced resulting in maximum schedulable data volume S k .

S k = min( S k , S Q ) (4)
Based on the current system state and further QoS parameters such as maximum latency and jitter, the scheduler assigns radio resources to transmit the data volume S k in the corresponding frame.

0 ≤ S k ≤ S k (5)
In conclusion, our traffic shaping algorithm fulfills the requirements of the IEEE 802.16-2009 standard in an exact manner and can be described with the following equation:

S k ≤ S k = min S Q , R M S • T B - k-1 i=k-n+1 S i (6)
As mentioned before, the traffic shaping algorithm calculates the schedulable data volumes based on MSTR and MRTR, which will be denoted as S k M S and S k M R in the following.

WiMAX Rate Based Scheduling

The aim of our scheduling algorithm is to primarily provide the agreed QoS parameter by giving strict priority to guaranteed MRTR based data volumes S k M R before allocating MSTR based demands S k M S . Secondary, a Min-Max fairness [START_REF] Boudec | Rate adaptation, Congestion Control and Fairness: A Tutorial[END_REF] based on radio resources is realized in order to balance between the two opposite goals of fairness based on user throughput and maximum cell throughput. Therefore, we equally increment the radio resource assignments of each connection with MRTR or respectively MSTR demands until the desired data volume is reached. When designing a WiMAX DL scheduling algorithm, the WirelessMAN-OFDMA frame format has to be taken into consideration. OFDMA permits to distribute the radio resources in time and frequency domain. The time domain is counted in OFDM symbols, while the frequency domain is divided into subchannels consisting of 28 subcarriers ([2], p. 938). In the mandatory Partial Usage of Subchannels (PUSC) frame structure, the minimum allocation unit called slot comprises 2 OFDM symbols on 1 subchannel. In one slot from 6 Byte to 27 Byte can be transmitted, dependent on the used modulation and coding scheme.

Figure 3 shows a simplified flowchart of our Two Rate based Scheduling algorithm. N F describes the number of free slots. N C denotes the maximum number of slots which can be assigned to a connection in the current iteration of the connection list. At the beginning of the scheduling algorithm, a list of all connections with S k M R > 0 is created. These connection can receive allocations to fulfill their MRTR requirements. If this list is not empty and the number of free slots N F is greater than zero, the maximum number of slots for each connection N C is calculated according to equation 7.

N C = max N F N L , 1 (7)
Here, N L denotes the number of connections in the list. If the number of connections in the list N L is higher than the number of free slots N F , one slot will be assigned. N C is added to previous assignments for the corresponding connection. When the transmission capacity of all assigned slots exceeds the permitted data volume S k M R according to the current modulation and coding scheme, the number of added slots is reduced to the necessary number of slots fulfilling S k M R . If S k M R has been reached the connection is removed from the list for the next iteration. Finally, the number N F of free slots is decreased by the number of newly assigned slots and the next connection of the current list iteration is processed. After all connections of the current iteration have been served and there are still demands and free slots the next iteration of the connection list begins with an updated N C value. Once, all MRTR based demands are served, a list of MSTR connections with S k M S > 0 is prepared and the assignment is conducted is the same manner. Because S k M S is always greater than or equal to S k M R , all previously assigned slots are included in the comparison with the maximum permitted data volume S k M S .

With this equal filling approach, we achieve our goal of a Min-Max fairness based on radio resources. Furthermore, we obtain a fair allocation in case of a high number of connections, when only one slot is assigned per iteration. We always start the assignment process with the first connection not being served in the last execution of the scheduler for the previous frame.

Simulation Results

The scheduling as well as the traffic shaping algorithm have been implemented in our WiMAX simulation environment. It consists of the network simulator ns-2 and an improved version of the WiMAX Add-On for ns-2 [START_REF]WiMAX Forum -Application Working Group: NS-2 MAC + PHY Add-On for WiMAX[END_REF], which was originally developed by the Application Working Group of the WiMAX Forum.

To investigate the behavior of our algorithm, we built up a scenario with two Mobile Stations (MSs) placed next to a Base Station (BS). Therefore, the highest modulation and coding scheme QAM 64 3/4 was used without transmission errors. We used typical system parameters deduced from [START_REF][END_REF]. A WirelessMAN-OFDMA TDD system was simulated with 10 M hz channel bandwidth and a cyclic prefix of 1/8. The applied 5 ms long frame consisted of 47 OFDM symbols, after subtracting the gap periods [START_REF][END_REF]. The DL subframe comprises 27 OFDM symbols including preample.

A Constant Bit Rate (CBR) foreground traffic of different service classes and data rates was sent to the first Mobile Station (MS1). For the second Mobile Station (MS2) a 25 M bit/s CBR background traffic was offered, which is higher than the overall link capacity. Both traffic sources generated packets with a size of 576 Byte. The MSTR and MRTR were set to 14 M Bit/s and 10 M Bit/s in order to stay below the system capacity of approximately 17 M bit/s. To focus on the scheduling algorithm and not on the traffic shaping algorithm, we configured the TB with 20 ms or respectively 4 frame durations. Therefore, the influence of the averaging of the data rates during the traffic shaping remains low.

We implemented six test cases, where the offered foreground traffic alternates in all possible relations around the MSTR and MRTR boundaries. Figure 4 shows the achieved goodput of Mobile Station (MS) 1 over time without traffic shaping and background traffic. Therefore, the goodput corresponds to the offered traffic. This sequence has been also used in all following simulations.

Figure 5 gives the simulation result of BE foreground traffic sent to MS1. It is represented by the dark gray curve. Because the service class BE does not provide any data rate guarantees, the MRTR limit is absent. It can be seen, that background traffic always uses the remaining resources from the foreground traffic. The system goodput depicted with the black line reaches always 17 M Bit/s. If only MS2 is active, the system goodput is slightly higher, due to the less signaling overhead for one station. This proves, that the system capacity is always used by our scheduler. The equilibrium between foreground and background traffic at a goodput of 8.5 M Bit/s shows, that the scheduler distributes the resources fairly.

In the second simulation result depicted in figure 6 the service class UGS was chosen for the foreground traffic. Therefore, the MRTR is 14 M Bit/s and equal to the MSTR. Similar to figure 5 Fig. 6. Goodput of MS1 using Service Class Unsolicited Grant Service (UGS) flows. Therefore, the system goodput is almost constant. When the offered UGS foreground traffic exceeds the MRTR threshold of 14 M Bit/s shown in the test cases 3, 5 and 6, the traffic shaping permits only the transmission up to the MRTR. In contrast, the offered UGS traffic is entirely transmitted, when it is below this boundary. Especially in test case 5, it can be seen, that the duration of the high data period is longer than compared to the offered traffic in figure 4. This effect results from packets stored in the queue, which are transmitted after 75 s simulation time.

The realtime service class RT-VR is designed for video streaming using both QoS parameters MRTR and MSTR. Therefore, the influence of both boundaries can be studied in the simulation result presented in figure 7. The figure shows, that the offed RT-VR traffic is not influenced up to the MRTR limit. In the test cases 3, 5 and 6, when the foreground traffic is high, an equilibrium of 13.5 M Bit/s can be observed. Due to the strict priority of MRTR assignments before MSTR allocations, a data volume of 10 M Bit/s is given to the RT-VR data flow. The remaining resource of 7 M Bit/s is fairly distributed between both flows resulting in a goodput of 13.5 M Bit/s of the foreground traffic and respectively 3.5 M Bit/s of the background traffic.

Conclusion and Future Work

In this paper we proposed a new Two Rate based Scheduling algorithm, which does not differentiate between service classes, but between guaranteed and sustained data rates. In combination with our traffic shaping algorithm, this resource allocation approach corresponds to the requirements of the IEEE 802.16-2009 standard. The simulation results prove that our algorithm is able to provide different service classes with their required QoS constraints. Future work includes the investigation of the algorithms under more complex scenarios and more realistic traffic models. Special interest will be given to the influence of our algorithm on other metrics such as delay and jitter. Furthermore, the algorithms will be compared with widely used scheduling algorithms applied in mobile networks to determine their practical relevance.

Fig. 1 .

 1 Fig. 1. WiMAX Resource Allocation

Figure 2 Fig. 2 .

 22 Fig. 2. System behavior in idle and overload state

Fig. 7 .

 7 Fig. 7. Goodput of MS1 using Service Class Real-Time Variable Rate (RT-VR)

  , all resources are used by both data

		20 20								Sum of Cell BE MS2
										UGS MS1
			1. 1.		2. 2.	3. 3.		4. 4.	5. 5.		6. 6.
		15 15	MRTR MRTR
	Goodput / Mbit/s Goodput / Mbit/s	10 10
		5 5
		0 0
		0 0	10 10	20 20	30 30	40 40	50 50	60 60	70 70	80 80	90 90	100 100
							Time / s Time / s

Acknowledgments We would like to thank our project partner Detecon Consulting, Germany for sponsoring this work. Special thanks are devoted to Dr. Petry and Dr. Knospe from Detecon Bonn for their great support.


Pavel Čeleda

Radek Krejčí

Vojtěch Krmíček

Flow-based Security Issue Detection in Building Automation and Control Networks

Keywords: network, security, attack, intrusion detection, entropy, flow, BACnetFlow, BACnet, building, automation

The interconnection of building automation and control system networks to public networks has exposed them to a wide range of security problems. This paper provides an overview of the flow data usability to detect security issue in these networks. The flow-based monitoring inside automation and control networks is a novel approach. In this paper, we describe several use cases in which flow monitoring provides information on network activities in building automation and control systems. We demonstrate a detection of Telnet brute force attacks, access control validation and targeted attacks on building automation system network.

Introduction

Internet and public networks in general have become a wild place. We have to protect our networks and connected devices against viruses, worms and hackers trying to compromise them. However, the network security is not just about these networks. We are facing similar security threats in sensor networks, Building Automation and Control Systems (BACS) networks or in Supervisory Control And Data Acquisition (SCADA) networks. The majority of new buildings or industrial facilities include intelligent networks, that are capable of controlling and monitoring the building's mechanical and electrical equipment. Although ordinary network provides hacker with a higher number of possible targets, industrial and automation networks become more and more interesting for some attackers [START_REF] Byres | The Myths and Facts Behind Cyber Security Risks for Industrial Control Systems[END_REF]. These types of networks represent an interesting environment especially for more targeted attacks with possible high impact on basic functions of a company or a society. This type of attack is predicted to grow significantly in the near future [START_REF]Security Predictions 2012&2013 -The Emerging Security Threat[END_REF].

Besides increasing passive security of the systems and networks, we need to detect intrusions and other security threats to minimize possible damages. In comparison to ordinary IP networks, security of the automation networks is still underestimated. With experiences from high-speed IP networks we believe that detailed information about what is exactly happening in the network is crucial for the BACS network security.

The more and more BACS networks are being moved to the Ethernet/IP networks. It makes them possible to be operated using the existing network infrastructure. Today's BACS devices feature command-line and browser-based control allowing them to be accessed from anywhere in the world. The flowbased network security monitoring in BACS networks is still in an early stage. In this context, this paper investigates several use cases, answering the following research question:

What are the advantages of flow-based monitoring in BACS networks and how can it help to detect security issue in these networks?

The paper is organized as follows: After a short introduction and related work, we describe the flow-based monitoring system for BACS networks. Then we describe entropy based anomaly detection and BACS targeted attacks. We present detected issues from large BACS network deployment. Finally, we conclude by summarizing impacts of flow data on BACS network security and propose future work.

Related Work

First ideas of using network traffic flow information for monitoring BACS (namely SCADA) networks appeared in [START_REF] Barbosa | Intrusion detection in SCADA networks[END_REF]. However, this work and its results published in [START_REF] Barbosa | Difficulties in Modeling SCADA Traffic: A Comparative Analysis[END_REF] rely on the traditional IP flow measurement. In our work, we focus on the specific BACS networks based on Building Automation and Control Networking protocol (BACnet) [START_REF]Refrigerating and Air-Conditioning Engineers: Standard 135-2010 -BACnet A Data Communication Protocol for Building Automation and Control Networks[END_REF]. The original IP flow definition was modified to follow specifics of the BACnet and we introduced the BACnetFlow in [START_REF] Krejčí | Traffic Measurement and Analysis of Building Automation and Control Networks[END_REF]. This approach enables to retrieve more accurate information about BACS network traffic.

Flow-based monitoring was originally proposed exclusively for IP networks. There is an extensive work in the area of network traffic monitoring in common IP networks. Today BACnet networks are monitored only by a Deep Packet Inspection (DPI) or by Simple Network Management Protocol (SNMP) queries to the network devices. DPI is used for example by BACnet Firewall Router (BFR) [START_REF] Holmberg | Using the BACnet Firewall Router[END_REF]. SNMP statistics are used for example in [START_REF] Yang | Anomaly-Based Intrusion Detection for SCADA Systems[END_REF] as supplementary information to the resource (CPU, memory, etc.) usage statistics retrieved from the monitored devices.

The security of the BACnet protocol was underestimated in the first protocol specifications. In 2003, Holmberg provided a report [START_REF] Holmberg | BACnet wide area network security threat assessment[END_REF] on possible security threats to BACnet networks. Based on this document, American Society of Heating, Refrigerating and Air Conditioning Engineers (ASHRAE) prepared BACnet security update in a form of the protocol specification addendum 135-2008g [START_REF]ANSI/ASHRAE: Addendum g to BACnet Standard 135-2008[END_REF].

Building Automation and Control Systems

BACS refer to systems providing services to achieve human comfort and safety, energy and economy savings and last, but not least, security of the controlled building. They interconnect all involved systems to form an intelligent building. BACS are currently deployed mainly as a part of large functional buildings as hospitals, office buildings or university campuses.

BACS networks usually combine a LAN infrastructure with some industrial network protocols. This approach allows utilisation of existing network infrastructure to interconnect BACS components. Furthermore, IP-based network makes remote control and maintenance easier. On the other hand, it increases the security risks.

In this paper we focus on BACS networks based on the BACnet protocol, especially BACnet over Ethernet and BACnet over IP variants. BACnet is an ASHRAE, ANSI, and ISO standard protocol developed to address specific needs of BACS networks.

The BACnet network topology consists of isolated BACnet networks interconnected by BACnet routers. Device addressing in such environment is provided by a combination of the BACnet network address and the local device address, which is specific to the link layer medium. BACnet defines several messages to discover the network or to share BACnet routing information. BACnet represents BACS functionality of each device as a set of objects with a collection of properties storing status or configuration data. The properties are available for other devices via BACnet service messages to read/write data from/to the property.

Flow-based BACnet Network Monitoring

BACnet is able to utilise various protocols (Ethernet, IP, LonTalk, PTP) as its data link layer. However, current network traffic flow monitoring tools are limited to IP networks. Furthermore, even if IP is used as BACnet's data link layer, the BACnet messages are often broadcasted across the whole IP network and it is not possible to identify communication participants. To identify and describe network traffic flows related to the BACnet protocol, we introduced the BACnetFlow [START_REF] Krejčí | Traffic Measurement and Analysis of Building Automation and Control Networks[END_REF]. If the BACnet traffic is detected in the monitored Ethernet/IP network, BACnet headers are parsed and stored in BACnetFlow record. BAC-netFlow record is depicted in Figure 1. In this paper we extended the original BACnetFlow record to support Application Layer Protocol Data Unit (APDU) data, e.g., BACnet services.

Our monitoring system is deployed at the Masaryk University Campus BACS network. The system passively observes network traffic passing through the main switches of the BACS network and its management servers. Another part of our monitoring system observes network traffic at the university network border. We generate and analyse non-sampled NetFlow and BACnetFlow statistics.

BACS Anomaly Detection

There is a wide spectrum of flow based anomaly detection methods targeted to IP networks [START_REF] Sperotto | An Overview of IP Flow-based Intrusion Detection[END_REF]. In this paper, we decided to compare simple volume based approaches to detection of network anomalies with an entropy based approach, providing another way how to analyse and disclose possible anomalies in network traffic. We applied this approach used in IP networks to the BACS networks environment.

Entropy represents a measure of the randomness of data. In this context, the term usually refers to the Shannon entropy [START_REF] Shannon | A Mathematical Theory of Communication[END_REF], which quantifies the expected value of the information contained in a message, usually in units such as bits. Entropy H(X) according to Shannon and used in our measurements is estimated as follows: Let's have an empirical histogram X = {n i , i = 1, ..., N } meaning that feature i occurs n i times in the data. Then the entropy is defined as:

H(X) = - N i=1 n i S • log 2 n i S (1)
where S = N i=1 n i is the total number of feature observations in the histogram.

BACnet Targeted Attacks

IP network is widely used as a backbone network that interconnects isolated BACnet networks. This backbone network can be the corporate LAN or even the Internet. BACnet traffic transported through the public networks can be an easy subject of eavesdropping or disruptions. To avoid this issue, the BACnet routers connecting BACnet network to the backbone network should add a security layer (VPN, IPsec, etc.) to the transported data.

Following list of threats presumes a physical break-in or a remotely accessible compromised device inside the BACnet network. BACnet provides addendum 135-2008g [START_REF]ANSI/ASHRAE: Addendum g to BACnet Standard 135-2008[END_REF] to secure the protocol. These security extensions can prevent the following attacks, originally described in [START_REF] Holmberg | BACnet wide area network security threat assessment[END_REF]. However, the extensions are optional and not widely implemented and deployed.

BACnet spoofing is equivalent to the similar attack in Address Resolution Protocol (ARP) [START_REF] Whalen | An Introduction to ARP Spoofing[END_REF] or to an advertisement spoofing in IPv6 [14, sec. 4.1.1]. Compromised device generates BACnets' I-Am-Router-To-Network messages with the fake content and forces other devices to send their messages via the attacker's device. Furthermore, compromised device can claim to be any other device using the I-Am service messages.

Denial of Service attack by flooding the BACnet network. Attacker (repeatedly) broadcasts Who-Is service requests without specifying device instance range limits. Then, all devices across all available BACnet networks respond with the I-Am message and flood the network. Another approach is to broadcast a confirmed service request with the source address set to the network broadcast address. The receiving device will broadcast a response.

Write-Property attack changing present value of the BACnet object's property. Result of such action can vary according to meanings of the affected object and its property. It can cause switching off/on the equipment, allowing access into the restricted area or disrupting the whole BACS.

Disabling network connection can be done using several BACnet services. BACnet network routing tables can be broken by the compromised device which shares defective routing information. Furthermore, communication can be disrupted by fake Router-Busy-To-Network messages.

BACS Security Use-Cases

In this section, we evaluate detected issues to demonstrate the capabilities of flow-based monitoring in BACS network. The results are organized in three categories. First, we present remote attacks from BACnet over IP devices carried over Internet against Masaryk University network. The second category of results shows how the devices behave in BACS network with strict access control and how strict it is. Last, we look for attacks specific for the BACnet devices.

Intrusion Detection

Massive Telnet scans were detected against university computers on December 4th, 2011. Tracing back to a source, we have identified infected devices world wide. The first remote device we were able to analyse [START_REF] Čeleda | Revealing and Analysing Modem Malware[END_REF] was a Modular automation station with BACnet over IP and web server. Other infected devices ranged from firewalls, routers, modems, VoIP appliances to consumer electronics, including satellite receivers, IPTV boxes, etc. This confirmed utmost importance of network security monitoring of any network and any device.

The source of attacks was a new Aidra botnet. The Aidra botnet is an open source IRC-based mass router scanner/exploiter publicly available for download from Internet [START_REF] Fazzi | Lightaidra -IRC-based mass router scanner/exploiter[END_REF]. The novelty of this botnet lies in supporting multiple hardware platforms of vulnerable devices. Equivalent versions for six different hardware architectures (ARM, MIPS, MIPSEL, PPC, SH4, x86) were observed until now. Aidra includes several types of scanners searching for other vulnerable devices using the Telnet protocol. According to attacker's commands, the bots are able to perform Denial of Service (DoS) attacks against specified targets. We noticed DoS attack against www.whitehouse.gov. Attacker is also able to execute any system command on infected devices. Aidra bots can be automatically upgraded and new functions can be added.

Figure 2 shows Telnet traffic observed on Tuesday 6th and Wednesday 7th December. We can see four graphs representing the Telnet traffic as the amount of kilobits/s, packets/s, flows/s and entropy of destination IP addresses.

(1)

(1) (1)
(1)

(1) (1)
(2)

(1) (1) (1)

Fig. 2: Telnet attacks against Masaryk University network.

There is some basic level of a regular Telnet traffic observable all the time (very low amount, about 0 to 5 kb/s). Beside this, we can see three types of attacks using the Telnet protocol. The most significant attacks are marked as (1), representing massive horizontal scans against B class subnet of campus network and probing all machines in this subnet for open Telnet ports. These attacks are very intensive, about 60 to 130 thousand flows and last only very short period, 15 minutes at maximum. Source of these attacks are Linux network devices (SYN packet size is 60 B) infected by Aidra botnet. We can notice attack spikes very well in all four graphs.

Second type (2) of attacks is similar -it is again a massive horizontal scan against B class subnet, caused by hosts infected by Aidra botnet. The difference is the intensity of the attacks -they are performed during longer time window (60 minutes). Again, we can notice them in all types of graphs, although the spikes in first three graphs are not so significant as in the graph with entropy.

Third type of Telnet attacks (3) represents a different class of attackers. In this case, the attackers are not infected devices like modems and routers, but ordinary computers with Microsoft Windows (SYN packet size is 48, 52 B). These attacks were performed with much slower rate, against C class subnet only. Therefore, we are not able to notice them in the case of traffic/packets/flows graphs, where they are hidden inside regular traffic. The role of the entropy (destination IP address entropy) is crucial for revealing such kind of attacks. This measure is able to distinguish attack scans from regular traffic due to the different amount of randomness in the data. Therefore we can see clear spikes (marked as (3)) in last graph.

Beyond common botnets' activities, we identified mass Telnet scan from a large-scale embedded device vulnerability scanner1 on November 14th, 2011. In that way Cui et al. [START_REF] Cui | A Quantitative Analysis of the Insecurity of Embedded Network Devices: Results of a Wide-Area Scan[END_REF] found over 540,000 publicly accessible devices, configured with factory default root passwords.

Access Control

The first task in securing any network is to ensure that unauthorised entities do not gain entry into the network. Most BACS networks are connected to the outside corporate/university network or the Internet through a gateway (see Figure 3). The previously held belief that the control networks are protected by an "air gap" is no longer true [START_REF] Byres | #1 ICS and SCADA Security Myth: Protection by Air Gap[END_REF]. We present week-long access control validation results for the BACS network. Week-long statistics were chosen in order to take into account time-of-day and day-of-week variations. Figure 4 shows worldwide attempts to establish a connection to monitored BACS network. We use SURFmap [START_REF] Hofstede | SURFmap: A Network Monitoring Tool Based on the Google Maps API[END_REF], a network monitoring tool based on the Google Maps API, to visualize IP connections.

BACS network

University Internet gateways have liberal access policies and the most traffic can pass through. We observed attempts to establish connections to hosts Fig. 4: Worldwide attempts to establish a connection to BACS network. in the address range of BACS network. Attackers' primary interests were following services -SSH(22), Telnet(23), HTTP(80), HTTPS(443), MS-SMB(445), MSSQL(1433), MSRDP(3389) and RADMIN(4899). All these unauthorized connections were denied by the BACS firewall and were not observed in the BACS network.

Table 1 shows foreign traffic observed inside BACS network. Incoming UDP and TCP connections are denied by default. ICMP messages are permitted. However, we did not observe any malicious or abnormal ICMP traffic. We found out that the outgoing UDP traffic was caused by incorrectly set DNS servers. Some of the devices used preconfigured foreign or public DNS servers as Google Public DNS2 (IP address 8.8.8.8).

Foreign TCP traffic was caused by the BACS management servers placed in "demilitarized zone" (DMZ). Some of these servers are allowed to establish remote connections, e.g., to download Microsoft Windows updates. Furthermore, we detected a feature called Network Connectivity Status Indicator (NCSI) [START_REF]Network Connectivity Status Indicator[END_REF] present in Windows Vista and later versions. This service enables networkinteracting programs to change their behavior based on how the computer is connected to the network. Windows machine tries to (i) download http://www. msftncsi.com/ncsi.txt file and (ii) resolve DNS name dns.msftncsi.com.

BACnet Attacks

We verified the occurrence of the security threats described in Section 5 in the Masaryk University Campus BACS network. To be able to detect BACnet targeted attacks we added support for the BACnet application data to the BAC-netFlow record.

Firstly, we analyzed the presence of BACnet router spoofing attack. We selected flows with the I-Am-Router-To-Network and I-Could-Be-Router-To-Network messages. In that way we could filter out the traffic from the legitimate routers and detect spoofing device. We did not detect such rogue device in our network. Figure 5 shows the BACnet over IP routers announcing their routing capabilities every 30 minutes. This kind of automatically generated traffic is prevalent in BACS networks [START_REF] Barbosa | Difficulties in Modeling SCADA Traffic: A Comparative Analysis[END_REF], but it is not the only type, as shown in Figures 6 and7. The same approach can be used to detect fake Router-Busy-To-Network messages. Secondly, we analyzed the BACnet device discovery DoS attack. This attack is based on flooding the network by I-Am messages generated by Who-Is requests without limited device range. Figure 6a shows amount of I-Am responses related to the Who-Is requests. While level of the Who-Is requests is constant, there are several spikes of I-Am responses. In this case, they are caused by Who-Is requests broadcasted to all BACnet networks. However, all these requests contain device range limits so the I-Am responses are sent only by requested devices. DoS attack would generate even higher spikes of I-Am messages and would be seen in this type of graph even more clearly. We did not detect other kinds of BACnet flooding attacks that use broadcasted confirmed service requests without a source address.

Figure 6b shows Who-Is/I-Am statistics during one week. We observed diurnal pattern of the I-Am responses to Who-Is requests broadcasted to all net- works during busy hours. This traffic is probably related to some operational staff activities in the university campus. Thirdly, we analyzed the BACnet write-property attack. This attack uses Write-Property service to harmfully change any property, e.g. turn off/on equipment. Figure 7 shows the statistics of Read-Property and Write-Property services. We observed distinct diurnal and weekly pattern for Read-Property service. The Write-Property service does not exhibit a clear pattern. Figure 7a shows very low number of write flows. We observed between 1 and 2 long-pending flows exported every 5 minutes (flow cache active timeout). This corresponds to constant Write-Property traffic shown in Figure 7b. The write-property attack can even succeed by using only one or a few well-targeted packets. The design of a flow/packet detection method is subject of our further research.

Summary

On the three use-cases described in Section 6, we demonstrated advantages of using flow monitoring to detect security threats in the BACnet network. The first use-case reported on Aidra botnet infected devices. Beyond standard small office/home office (SoHo) devices we detected foreign BACnet over IP devices scanning entire university network. There does not exist an anti-virus or an anti-malware for these devices. Most users would not suspect that any embedded device can threaten their computers. Flow information is essential to reveal such rogue activities.

The second use-case showed how the BACS gateway prevents unauthorised access to automation and control devices. BACS firewall misconfiguration can facilitate an attack against BACnet devices as mentioned in the first use-case (publicly accessible BACnet devices using default credentials). We presented extrusion detection results using the flow representation of outbound traffic to highlight this security threat. The third use-case showed a novel approach to detection of BACnet targetted attacks. We added support for BACnet application data into the BACnetFlow to be able to detect these attacks. We analyzed the traffic to detect router spoofing attack, device discovery DoS attack and application service attack. According to our best knowledge, we provided the first flow-based detection results for BACnet targetted attacks.

As future work, we intend to extend our detection towards a malfunction and a security misconfiguration detection of BACnet devices. We consider to investigate the attacks launched from within the BACS network and trusted internal networks.

Fig. 1 :

 1 Fig.1: BACnetFlow record consists of key fields extracted from the protocol headers and non-key fields with additional information.

Fig. 3 :

 3 Fig. 3: University LAN infrastructure with dedicated BACS network. Deployed monitoring system provides flow information from (a) entire university network and (b) building automation and control systems network.

Fig. 5 :

 5 Fig. 5: BACnet over IP routers broadcasting I-Am-Router-To-Network and I-Could-Be-Router-To-Network messages to the campus BACS network.

Fig. 6 :

 6 Fig. 6: BACnet device discovery -relation between Who-Is and I-Am messages during (a) a single day -March 16, 2012, (b) a week -March 13 -20, 2012.

Fig. 7 :

 7 Fig. 7: BACnet data sharing -Read-Property and Write-Property services.

Table 1 :

 1 Week-long remote communication statistics to/from BACS network.

	PROTO	DIR	Bytes	Packets	Flows	DIR	Bytes	Packets	Flows
	TCP		2217553	23122	323		15248736	33267	287
	UDP	In	0	0	0	Out	2068299	27396	13113
	ICMP		6812	100	96		4202	65	65

http://www.hacktory.cs.columbia.edu

http://code.google.com/speed/public-dns/

Acknowledgments. This material is based upon work supported by the Czech Ministry of Defence under Contract No. SMO02008PR980-OVMASUN200801 and also supported by the "CESNET Large Infrastructure" project LM2010005 funded by the Ministry of Education, Youth and Sports of the Czech Republic.