Khóa luận Evaluation of existing algorithms scheduling for Real-Time service flows for WiMAX uplink

s. 2.2.2 Overview of Admission Control I express the need for the admission control in order to control the usage and allocation of bandwidth resources for various traffic classes requiring certain QoS guarantee. Admission control is a key component in determining whether a new request for a connection can be granted or not according to the current traffic load of the system. This assumes great significance when the BS needs to maintain a certain promised level of service for all the connections being admitted (served). If the admission control admits too few connections, it results in wastage of system resources. On the other hand. If too many connections are allowed to contend for resources, then the performance of the already admitted connections degrades rapidly in the presence of new connections. Therefore, judicious decision making mechanism for allocating bandwidth to different classes of service is needed. In IEEE 802.16, before an SS can initiate a new connection or changing or deleting an already admitted connection, it must first make a request to the BS. As mentioned earlier in chapter 1, four types of MAC layer services exist in IEEE 802.16. These service flows can be created, changed, or deleted through the issue of dynamic service addition (DSA), dynamic service creation (DSC) and dynamic service deletion (DSD) messages. Each of these actions can be initiated by the SS or the BS and are carried out through a two or three-way-handshake. 2.2.3 Admission Control Policy The task of admission controller is to accept or reject the arriving requests for a connection in order to maximize the channel utilization, by accepting as many connections as possible, while keeping the QoS level of all connections at the level specified in their traffic profile. In other words it ensures that already admitted connections QoS will not be affected by the decision made. Although it may seems to be very intuitive and simple procedure, it has great influence on QoS of the admitted connections. This issue have been studied and researched extensively in the context of wired and wireless networking. Although the focus of this research was not admission control, whenever it comes to IEEE 802.16, putting a well rounded introduction seems to be indispensable, thus we have concisely introduced some of the fundamental works that need to be done in this area as there is no defined procedure in IEEE 802.16. Admission control algorithms can be categorized into three classes of complete sharing, complete partitioning and hybrid policies which is a combination methods of the other two. Complete sharing (CS): allows all users equal access to the bandwidth available at all times. This strategy results in maximum utilization of the available bandwidth, specially in high traffic networks, which is what network providers aiming at. However, at the same time, it does not differentiate between connections of different priority that is a perverse outcome when connection of one class needs significantly less bandwidth than others. At this situations it might be desirable to reject calls of this type to increase the probability of future acceptance of a larger call. In other word it is not fair strategy to the wider bandwidth users as all request would be dealt with the same priority. Complete partitioning (CP): divides up the available bandwidth into non-overlapping pools of bandwidth in accordance with the type of user’s connection. Therefore, number of existing users in each class would be prohibited to a maximum number M which admission decision will be made upon. This policy allows for more control of the relative blocking probability at the expense of overall usage of the network. Hybrid policies: basically provide a compromise between the different policies by subdividing the available bandwidth into sections. Part of the bandwidth in completely shared and the other part is completely partitioned. Depending on the policy adopted, the partitioned division would be dedicated to some or all classes. This allows more live up to the QoS requirements of the different user type while maintaining higher network utilization. In the above mentioned admission control policies, CP and CS, have no complexities to be elaborated and decision making would be a matter of checking a single condition, though, the hybrid strategy is a more open ended problem. As an example, in the following we suggest an algorithm that could be considered as a hybrid method for admission control. 2.3 Services and service flows 2.3.1 Connections and service flow The CS provides any transformation or mapping of external network data received through the CS Service Access Point (SAP) into MAC SDUs received by the MAC Common Part Sublayer (CPS) through the MAC SAP (see Figure 1). This includes classifying external network Service Data Units (SDUs) and associating them with the proper MAC Service Flow Identifier (SFID) and Connection Identifier (CID). Classification and mapping are then based on two 802.16 MAC layer fundamental concepts Connection: A connection is a MAC Level connection between a BS and an SS (or MS) or inversely. It is a unidirectional mapping between a BS and an SS MAC peers for the purpose of transporting a service flow's traffic. A connection is only for one type of service (e.g. voice and email cannot be on the same MAC connection). A connection is identified by a CID (Connection IDentifier), an information coded on 16 bits. Service flow: A Service Flow (SF) is a MAC transport service that provides unidirectional transport of packets on the uplink or on the downlink. A service flow is identified by a 32-bit SFID (Service Flow IDentifier). The service flow defines the QoS parameters for the packets (PDUs) that are exchanged on the connection. Figure 2.2 shows the relation between the SFID and CID. The relation between the two is the following: only admitted and active service flows (see the definitions below) are mapped to a CID, i.e. a 16-bit CID. In other terms: Figure 2.2: Correspondence between the CID and SFID A SFID matches to zero (provisioned service flows) or to one CID (admitted or active service flow). A CID maps to a service flow identifier (SFID), which defines the QoS parameters of the service flow associated with that connection. The definitions of connection and service flow in the 802.16 standard allow different classes of QoS to be found easily for a given element (SS or BS), with different levels of activation (see Figure 2.3). More details will now be given about connections (and CIDs) and service flows. Figure 2.3: Illustration of service flows and connections 2.3.2 Connection Identifiers (CIDs) A Connection IDentifier (CID) identifies a connection where every MAC SDU of a given communication service is mapped into. The CID is a 16-bit value that identifies a unidirectional connection between equivalent peers in the MAC layers of a BS and an SS. All 802.16 traffic is carried on a connection. Then, the CID can be considered as a connection identifier even for nominally connectionless traffic like IP, since it serves as a pointer to destinations and context information. The use of a 16-bit CID permits a total of 64K connections within each downlink and uplink channel. There are several CIDs defined in the standard (see Table 1). Some CIDs have a specific meaning. Some of the procedures introduced in this table, such as ranging, basic, primary and secondary management. Table 1: CID ranges as defined in Reference IEEE 802.16-2004. CID Value Description Initial ranging 0 × 0000 Used by SS and BS during the initial ranging process Basic CID 0 × 0001 – m Each SS has a basic CID and has a short delay. The same CID value is assigned to both the downlink and uplink connections Primary management m + 1 − 2m The primary management connection is used to exchange longer, more delaytolerant MAC management messages Transport CIDs and secondary management CIDs 2m + 1 − 0 × FE9F Used for data transfer and for secondary management connection Multicast CIDs 0 × FE9F − 0 × FEFE For the downlink multicast service, the same value is assigned to all SSs on the same channel that participate in this connection AAS initial ranging CID 0 × FEFF A BS supporting AAS (Advanced Antenna System) uses this CID when allocating an AAS ranging period (using AAS_ Ranging_Allocation_IE) Multicast polling CIDs 0 × FFOO− 0 × FFF9 An SS may be included in one or moremulticast polling groups for the purposes of obtaining bandwidth via polling. These connections have no associated service flow Normal mode multicast CID 0 × FFFA Used in DL-MAP to denote bursts for transmission of downlink broadcast information to normal mode SS Sleep mode multicast CID 0 × FFFB Used in DL-MAP to denote bursts for transmission of downlink broadcast information to sleep mode SS. May also be used in MOB_TRF-INO messages Idle mode multicast CID 0 × FFFC Used in DL-MAP to denote bursts for transmission of downlink broadcast information to idle mode SS. May also be used in MOB_PAG-ADV messages Fragmentable broadcast CID 0 × FFFD Used by the BS for transmission of management broadcast information with fragmentation. The fragment subheader should use an II-bit long FSN on this connection Padding CID 0 × FFFE Used for transmission of padding information by the SS and BS Broadcast CID 0 × FFFF Used for broadcast information that is transmitted on a downlink to all SSs 2.3.3 Service Flows A Service Flow (SF) is a MAC transport service that provides unidirectional transport of packets on the uplink or on the downlink. It is identified by a 32-bit SFID (Service Flow IDentifier). A service flow is characterized by a set of QoS parameters. The QoS parameters include details of how the SS may request uplink bandwidth allocations and the expected behaviour of the BS uplink scheduler. 2.3.3.1 Service Flow Attributes A service flow is partially characterised by the following attributes: Service Flow ID. An SFID is assigned to each existing service flow. The SFID serves as the identifier for the service flow in the network. CID. Mapping a CID to an SFID exists only when the connection has an admitted or active service flow (see below). ProvisionedQoSParamSet. This defines a QoS parameter set that is provisioned via means that the standard assumes to be outside of its scope. The standard states that this could be part of the network management system. For example, the service (or QoS) class name is an attribute of the ProvisionedQoSParamSet. There are five QoS classes, the fifth having been added by the 802.16e amendment. AdmittedQoSParamSet. This defines a set of QoS parameters for which the BS, and possibly the SS, are reserved resources. The principal resource to be reserved is bandwidth, but this also includes any other memory or time-based resource required to subsequently activate the flow. ActiveQoSParamSet. This defines a set of QoS parameters defining the service actually being provided to the service flow. Only an active service flow may forward packets. The activation state of the service flow is determined by the ActiveQoSParamSet. If the ActiveQoSParamSet is null, then the service flow is inactive. Authorisation module. This is a logical function within the BS that approves or denies every change to QoS parameters and classifiers associated with a service flow. As such, it defines an ‘envelope’ that limits the possible values of the AdmittedQoSParamSet and ActiveQoSParamSet. 2.3.3.2 Types of Service Flow The standard has defined three types of service flow: Provisioned service flows. This type of service flow is known via provisioning by, for example, the network management system. Its AdmittedQoSParamSet and ActiveQoSParamSet are both null. Admitted service flow. The standard supports a two-phase activation model that is often used in telephony applications. In the two-phase activation model, the resources for a call are first ‘admitted’ and then, once the end-to-end negotiation is completed, the resources are ‘activated’. Active service flow. This type of service flow has resources committed by the BS for its ActiveQoSParamSet. Its ActiveQoSParamSet is non-null. 2.3.3.3 Classification and Mapping Classification is the process by which a MAC SDU is mapped on to a particular connection for transmission between MAC peers. The mapping process associates a MAC SDU with a connection, which also creates an association with the service flow characteristics of that connection. Classification and mapping mechanisms exist in the uplink and downlink. In the case of a downlink transmission, the classifier will be present in the BS and in the case of an uplink transmission it is present in the SS. A classifier is a set of matching criteria applied to each packet entering the WiMAX/802.16 network. The set of matching criteria consists of some protocol-specific packet matching criteria (a destination IP address, for example), a classifier priority and a reference to a CID. If a packet matches the specified packet matching criteria, it is then delivered to the SAP for delivery on the connection defined by the CID. The service flow characteristics of the connection provide the QoS for that packet. The classification mechanism is shown in figure 2.4. Payload Header Suppression (PHS) The packets delivered to OSI model layer 2 may have very large headers, sometimes as long as 120 bytes. This is the case for some RTP/UDP/IPv6 packets (RTP, Real-Time Protocol, UDP, User Datagram Protocol). This is very often repetitive (redundant) information and so should not be transmitted on a scarce resource such as a radio channel, which should be used for useful information. This process is known as header compression and decompression in 3G-cellular systems. In the 802.16 standard, the PHS process suppresses repetitive (redundant) parts of the payload header in the MAC SDU of the higher layer. Figure 2.4: Classification and CID mapping The receiving entity restores the suppressed parts. Implementation of the PHS capability is optional. Figure 2.5 shows the PHS mechanism at the sending entity. Suppression of parts of the header leads to a compressed header. The receiver has to restore the header before properly using the received packet (Figure 2.6) . Figure 2.5: Header suppression at the sending entity. Figure 2.6: Header suppression mechanism at the receiving entity. To indicate whether the PHS is present or not, the PHS support field is used. This parameter indicates the level of PHS support. The PHS support field is a field in some MAC management messages, Registration Request and Registration Response. Table 2 shows the possible values of the PHS support field. The default value is 0 (no PHS). Table 2: Possible values of the PHS support field Value Description 0 No PHS support 1 ATM PHS 2 Packet PHS 3 ATM and Packet PHS PHS Rules PHS rules application and signaling are different for the two defined CS specifications: ATM CS and packet CS: The ATM standard defines two modes: the VP-switched mode (Virtual Path) and the VC-switched mode (Virtual Channel). The same PHS operation is applied for the two modes; the only difference between them is the payload header size after suppression. When the PHS is turned off, no part of any ATM cell header including the Header Error Check (HEC) field is suppressed. In the Packet CS mode, if the PHS is enabled at the MAC connection, each MAC SDU starts with a Payload Header Suppression Index (PHSI), an 8-bit field that references which Payload Header Suppression Field (PHSF) to suppress. Once a PHSF has been assigned to a PHSI, it cannot be changed. To change the value of a PHSF on a service flow, a new PHS rule must be defined. Figure 2.7 shows the operation of the PHS in a Packet CS. It is the responsibility of the higher-layer service entity to generate a PHS rule that uniquely identifies the suppressed header within the service flow. It is also the responsibility of the higher-layer service entity to guarantee that the byte strings that are being suppressed are constant from packet to packet for the duration of the active service flow. Figure 2.7: Illustration of PHS operation. As already mentioned, the sending entity uses the classifier to map packets into a service flow. The classifier uniquely maps packets to the PHS rule associated with this service flow. The receiving entity uses the CID and the PHSI to restore the PHSF. The PHS has a Payload Header Suppression Valid (PHSV) option to verify the payload header before suppressing it. It also has a Payload Header Suppression Mask (PHSM) option to allow the choice of bytes that cannot be suppressed. The PHS rule provides PHSF, PHSI, PHSM, PHSS (Payload Header Suppression Size) and PHSV. PHS signaling PHS rules are created with DSA or Dynamic Service Change (DSC) MAC management messages. The BS defines the PHSI when the PHS rule is created. PHS rules are deleted with the DSC or Dynamic Service Deletion (DSD) MAC management messages. When a classifier is deleted, any associated PHS rule is also deleted. Figure 2.8 shows the use of a DSC message to signal the creation of a PHS rule and whether this rule is initiated by the BS or the SS. In this figure, the use of the following DSC MAC management messages is introduced: DSC-REQ. A DSC-REQ is sent by an SS or BS to dynamically change the parameters of an existing service flow. It can be used to create PHS rules. DSC-RSP. A DSC-RSP is generated in response to a received DSC-REQ. DSC-ACK. A DSC-ACK is generated in response to a received DSC-RSP. The main DSC message parameters are SFID (only for DSC-RSP and DSC-ACK), CID. service class name, CS specification[7]. Figure 2.8: DSC MAC management message used for the signaling of a PHS rule. 2.4 QoS architecture model The process of requesting and granting QoS in a network can be generally divided in two separate layers: application and network layers. The application layer, with the function of providing the end-user with a simplified and standardized view of the quality level that will be granted for a given service, is not aware of the technicalities of service requirements (such as bandwidth, delay, or jitter). Also, it does not depend on the technology-dependent issues associated to the actual networks that will be traversed (such as a fiber-optic, wireless, or xDSL). Meanwhile, the network layer deals with a set of technical QoS parameters. In details, the network layer maps these parameters on network-specific requirements that have to be fulfilled to provide the end-user with the negotiated quality level. This mapping is normally performed at the network layer in wired IP network. However, such an approach is hardly suitable for wireless networks, where there are a number of factors that influence with respect to wired networks, there is high variability of the network capacity due, for instance, to environmental conditions, the link quality experienced by different terminals is location-dependent. Consequently, the implementation of QoS provisioning at the MAC layer, as in IEEE 802.16, is often essential so as to gain a better insight of the present technology-dependent network status and to react as soon as possible to changes that might negatively affect QoS. In IEEE 802.16 the prominent QoS functions of network provisioning and admission control are logically located on the management plane. As already indicated, admission control is outside the scope of the IEEE 802.16, which only covers the data control plane, as illustrated in figure 2.9. Network provisioning, the process of approving a given type of service, by means of its network-layer set of QoS parameters that might be activated later, can be either static or dynamic. Specifically, it is said to be static if the full set of services that the BS supports is decided a priori. This model is intended for a service provider who want to specify the full set of services that its subscribers can request, by means of manual or semiautomatic configure of the BS’s management information base (MIB). Meanwhile, with dynamic network provisioning, each request to establish a new service is forwarded to an external policy server, which decides whether to approve or not. This model allows a higher degree of flexibility, in terms of the types of service that the provider is able to offer to its subscribers, but it requires a signaling protocol between the BS and the policy server, thus incurring additional communication overhead and increased complexity. Figure 2.9 Quality of Service model in IEEE 802.16 The admission control function, unlike the network provisioning function, which only deals with services that might be activated later, and that are therefore said deferred, is responsible for resource allocation. Thus, it will only accept a new service if it can provide the full set of QoS guarantees that it has requested, and the QoS level of all the services that have been already admitted would remain above the negotiated threshold. Admission control obviously works with a time scale smaller than that of network provisioning. This is motivated because network provisioning is much more complex than admission control, as shown in a recent study on an integrated end-to-end QoS reservation protocol in a heterogeneous environment, with IEEE 802.16 and IEEE 802.11e devices. Tested result demonstrated that the network provisioning latency of IEEE 802.16 equipments currently available in the market is in the order of several seconds, whereas the activation latency is in the order of milliseconds. In IEEE 802.16, the set of network parameters that entirely defines the QoS of a unidirectional flow of packets resides into a service flows (SF) specification. The state of each SF can be: provisioned, admitted, active. Provisioned SFs are not bound to any specific connection, because their intentional function is to serve as an indication of what types of service are available at the BS. Then, when an application on the end-user side starts, the state of the provisioned SF will become admitted, thus booking resources that will be shortly needed to fulfill the application requirements. When the SF state becomes admitted, then it is also assigned a connection identifier (CID) that will be used to classify the SDUs among those belonging to different SFs. However, in this phase, resources are still not completely activated; for instance, the connection is not granted bandwidth yet. This last step is performed during the activation of the SF, which happens just before SDUs from the application starts flowing through the network. Thus a two-phase model is used, where resources are booked before the application is started. At any time it is possible to “put on hold” the application by moving back the state of the SF from active to admitted. When the application stops the SF is set to either provisioned or deleted; in any case, the one-to-one mapping between the service flow identifier (SFID) and the CID is lost, and the CID can be reassigned for other purposes. The SF transition diagram is illustrated in Figure 2.9. Figure 2.10 shows the blueprint of the functional entities for QoS support, which logically reside within the MAC CPS of the BS and SSs. Figure 2.10 Service flow transition diagram. Each DL connections has a packet queue (or queue, for short) at the BS (represented with solid lines). In accordance with the set of QoS parameters and the status of the queues, the BS DL scheduler selects from the DL queues, on a frame basis, the next SDUs to be transmitted to SSs. On the other hand, UL connection queues resides at SSs. Bandwidth request are used on the BS for estimating the residual backlog of UL connections. In fact, based on the amount of bandwidth requested (and granted) so far, the BS UL scheduler estimates the residual backlog at each UL connection, and allocates future UL grant according to the respective set of QoS parameters and the (virtual) status of the queues. However, as already introduced, although bandwidth requests are per connection, the BS nevertheless grants UL capacity to each SS as a whole. Thus, when an SS receives an UL grant, it cannot deduce from the grant which of its connections it was intended for by the BS. Consequently, an SS scheduler must also be implemented within each SS MAC to redistribute the granted capacity to the SS’s connections (Figure 2.11)[8]. Figure 2.11 Medium Access Control architecture of the Base and Subscriber Station Chapter 3. Scheduling and Admission for Real-Ttime Traffic 3.1 Scheduling and admission for real-time traffic. The concept of scheduling a time-constrained job is central to both design and analysis of real-time systems, basing on the job characteristics to assign priorities to scheduling decisions.