7
Chapter 1
Introduction
AccesstotheInternetisbecomingmoreandmoreimportantforalotofjobs,
for educational purposes, for entertainment and for a lot of other reasons
related to the large amount of information that can be found in the global
network, and the ability to put in contact places which are geographically
far away, without too much effort. One of the challenges that are of major
interest is providing everyone with Internet access, no matter where he
is: schools, museums, coffee bars and airports are only some examples of
places in which an Internet access may be required or at least desired by
people. “Fast connectivity” is usually provided through cabled networks
(optical and *DSL for example), which are able to reach very high speeds,
while“everywhereconnectivity”isbeingrealizedthroughothertechnologies,
which may involve satellite communications, cellular networks and 802.11
wireless networks.
Satellites’ networks can be useful to provide connectivity in isolated
places (like desert or war fields), without the need of building any
infrastructure on the ground.
Cellular networks, such as GPRS or UMTS, can provide Internet
access almost in any place where there are populated areas (the needed
infrastructure is quite costly and it can not be deployed where there is not
a sufficient amount of users) but, at present, high costs and low bit-rates
prevented them from being used by the majority of people for this purpose.
Wireless networks based on the IEEE 802.11 Standard [1, 2] are useful
tograntInternetaccessinplaceswhereyoudonotwantoryoucannotbuild
cabled networks, because of reasons related to their cost or to the difficulty
of realizing them. They are low-cost and can reach high speeds (not as
cabled networks however, which can be two orders of magnitude faster). A
wireless hot-spot, i.e. a place where wireless connectivity is available, can
be provided quite easily once you have granted Internet connectivity to the
Access Point, which acts as a bridge between the wireless devices and the
Internet gateway.
8 Chapter 1: Introduction
Local Area Networks (LANs) based on the IEEE 802.11 Standard are
cellular networks: each cell, called Basic Service Set (BSS), is served by an
Access Point (AP) to which one or more Stations can be connected. Small
wireless hot-spots are made of a single BSS, but bigger Wireless Local Area
Networks (WLANs) as the ones that cover entire campuses (as the Faculty
of Science of the University of Trento, for example) are usually made of
multipleBSSs,connectedonetoeachotherthroughasortofbackbone called
Distribution Service(DS),whichisusuallyEthernet-based. AlltheBSSsand
the DS are seen as a unique802.11 network which is called Extended Service
Set. Along with this AP-based architecture, called Infrastructured Network,
802.11 defines also an Ad Hoc Network architecture, which can be used to
build a wireless network among wireless devices without an AP or other
infrastructures and that allows to establish peer-to-peer communications
among the different devices.
The 802.11 standard defines two distinct mechanisms that can be used
in a BSS to regulate the access to the wireless medium, the Distributed
Coordination Function (DCF) andthe Point Coordination Function (PCF).
DCF is a contention-based channel access mechanism: each station must
contend forchannel access with theother stations each time itneedsto send
dataonthewirelessmedium. Thismechanismisabsolutelynotabletogrant
Quality of Service (QoS) and can provide only a best effort service to the
stations. PFC, instead, was developed with the purpose of granting QoS to
someofthestationsoftheBSSbyintroducingapolling-based channel access
mechanism controlled by a Point Coordinator (PC) (collocated inside the
AP) which grants to the different stations of the BSS the right to transmit.
Due to some limitations in its design it failed its purpose and almost all of
the 802.11 wireless devices support only the DCF mechanism.
The problem of introducing quality of service awareness inside the
networks has been taken into consideration by the Internet Engineering
Task Force (IETF) which defined two QoS models, the Integrated Services
(IntServ) and the Differentiated Services (DiffServ): the first one requires
the introduction of end-to-end signaling mechanisms for the negotiation of
the QoS requirements of the different traffic streams, while the second one
aims to group the different traffic streams into some known classes of traffic
which have particular QoS requirements. IntServ is more powerful than
DiffServ because of its finer-grained traffic streams characterization, but it
is also more expensive to introduce and less scalable due to the necessity
to introduce the support to the signaling mechanism in each element of the
network. In order to be able to meet the quality of service requirements of
a communication, it is necessary that every network which is crossed by the
data that belongs to the communication itself is QoS-aware.
As we previously said, 802.11 wireless networks lack the QoS support,
whose introduction has been taken into consideration by the 802.11e
amendment [3] to the main standard, released in November 2005. It
9
added some functionalities to the 802.11 Medium Access Control (MAC)
layer and a new coordination function, the Hybrid Coordination Function
(HCF), which alternates between two new channel access mechanisms, the
Enhanced Distributed Channel Access (EDCA) and the HCF Controlled
Channel Access (HCCA). EDCA is a contention-based protocol that is able
to differentiate traffic streams and to group them into traffic categories, as
in the DiffServ QoS model. HCCA is a contention-free protocol that grants
QoS requirementsto the single trafficstreams through apolling mechanism:
as in PCF, it requires a central entity, the Hybrid Coordinator (HC) that
resides in the AP and that has the duty to grant channel access to the
stations of the QoS-aware BSS (QBSS). It aims to solve the problems that
determined the failure of PCF and requires QoS signaling between stations
and the access point for negotiating QoS parameters, being somewhat
inspired to the IntServ QoS model (in this case the scalability and costs
issues are not a concern, since QoS signaling is limited to the BSS).
802.11e compliant hardware devices are not yet on the market, and a lot
ofstudiesontheperformanceandthetuningoftheparametersofEDCAand
HCCA have been made on existing 802.11 simulators [4, 5, 6, 7] extended
withthesenewchannelaccessmechanisms. AdifferentwayoftestingEDCA
has been experimented by the Host QS Project [8] which introduced EDCA
traffic differentiation mechanisms over the standard 802.11 MAC layer.
They used the Host AP WLAN driver (which allows a normal computer
with a standard wireless card with an Intersil Prism 2/2.5/3 chipset to
become an 802.11 access point), to build a Linux-based BSS and then they
modified the WLAN driver of the AP and the stations in order to redirect
the flow of outgoing packets, directed to the wireless card for transmission,
to a kernel module developed by them. Then, they used this module to
manage the dispatching of the outgoing packets as it would be done under
the rules of EDCA. Host QS allowed them to test different configurations of
the EDCA parameters in a real wireless LAN.
We considered this approach interesting, since it is the only way to
test 802.11e traffic differentiation mechanisms in a real setting, given that
modifying the standard 802.11 MAC layer can be extremely difficult and
can not be afforded by us due to the high costs of hardware development
kits.
The objective of this thesis is to follow a similar approach to introduce
the 802.11e controlled access mechanism, HCCA, over the 802.11 MAC
layer (focusing on the 802.11b [9] amendment, which raises the maximum
transmission rate of 802.11) through the realization of a Linux kernel
module, called Host HCF.
In Chapter 2 we discuss Linux Kernel Development: we explain the
limitations and issues related to kernel development and the main concepts
that a kernel developer must know. Then, we describe some important
topics such as concurrency and locking and kernel debugging techniques.
10 Chapter 1: Introduction
In Chapter 3 we get in touch with the concept of quality of service
and with the 802.11e standard: we discuss what is QoS and what are
the parameters that are used to define QoS requirements and we describe
the DiffServ and IntServ QoS models. Then we discuss the 802.11 DCF
and PCF channel access mechanisms, in order to put in evidence the
enhancements of EDCA and HCCA and later we examine into the details
of the Hybrid Coordination Function (HCF): we describe how EDCA and
HCCAwork, discussingtraffic specifications, QoS information signaling and
the connection admission control procedures, which are fundamental for
granting QoS. We conclude the chapter with a discussion on the 802.11e
Sample Scheduler: the HCCA scheduler is the component that determines
how the hybrid coordinator polls the stations of the QoS BSS and 802.11e
do not impose the utilization of a particular scheduler. 802.11e just
suggests a simple implementation, called Sample Scheduler. This makes
the implementation of the scheduler one of the main issues on which the
research on HCCA is focused.
In Chapter 4 we discuss our project, Host HCF: we describe the general
architecture of the system and then we go on with the implementation
details. We explain what we implemented of 802.11e and how we solved the
issues related to kernel programming that we faced duringthe development.
We concludethechapterwiththedescriptionofourHCCAscheduler, called
Basic Scheduler,whichhasbeendevelopedwiththepurposeofgrantingQoS
to interactive voice streams, to preserve them from being damaged by best
effort traffic.
Then, in Chapter 5 we discuss the tests we made with Host HCF to
justifysomeoftheimplementationchoiceswemade,todescribethebehavior
of Host HCF in different contexts and to show that it is able to preserve the
quality ofVoIP calls even in presence ofhigh-load besteffort trafficstreams.
11
Chapter 2
Linux Kernel Development
In this chapter we discuss the issues related to the development of Linux
kernel code [10, 11]. This introduction is necessary to fully understand the
problems we faced developing our project, which as already said consists of
a kernel module.We focus our discussion on 2.6 kernel series, which is the
one we worked with (more precisely, we used a 2.6.15 kernel).
2.1 Limitations and New Issues
Developing kernel code is different from the “usual” application develop-
ment: you must deal with a totally different environment, which provides
less functionalities, emphasizes some problems and introduces some new
issues and restrictions. Here we briefly discuss some of the peculiarities of
kernel development:
• No libc: Kernel does not have access to the C Library. This is due to
the fact that the C Library is too big and inefficient to be used by the
kernel, even if only a subset of the most used functionalities is taken
out from it. This means that a lot of functionalities that we can use
whenprogramming user-level application are missingwhen working in
the kernel (some of the libc functions, such as those related to string
manipulation, have been implemented also in the kernelsources). One
of the most used C functions that are missing is printf: its work
is done by printk, which is used in a similar way, apart from the
fact that the messages that it prints out have a particular log level
that is used to give different importance to them. printk does not
prints the messages directly on the active console or terminal, but it
sends them to the kernel log buffer, a circular buffer: this buffer is
then read by programs like syslog, which shows them to the user.
The particularity of printk is that it has been implemented in such
a way that it is possible to call it from every point in the kernel, even
12 Chapter 2: Linux Kernel Development
in interrupt handlers (Section 2.3), which makes it really useful for
debugging purposes (Section 2.8);
• No memory protection: Memory protection is active for user
applications because the kernel itself forbids illegal accesses and takes
care of what each application does. If an illegal access is caused
by a user application, kernel catches it and sends a SIGSEGV signal
which causes a feared segmentation fault error that terminates the
applicationandpreventsdamagingmemorycontent. Kernellackssuch
aprotectionbecausethereisnooneelsethatlooksafterthekernel: ifa
memoryviolation happens,it resultsinakerneloops, whichisamajor
error that can halt the entire system (if the violation is generated by
kernel code that runsinprocess context (Section 2.3) the system could
alsosurvivetheoops,althoughprobablyinanothealthystatebecause
some important data has been corrupted);
• Non pageable memory: Every byte of memory allocated by the
kernel is never paged and consumes a byte of physical memory. This
must be kept in mind if developing for machines or embedded systems
with few available physical memory;
• Noeasyuseoffloatingpoint: Itisnotpossibletodofloatingpoint
computation in the kernel, and usually it is not really needed, without
doing complex things such as directly interacting with floating point
registers;
• Small fixed-size stack: User processes can allocate high amount of
data on the stack since it can grow dynamically in size, while this is
not possible for the kernel. In fact, it has a small 2 pages stack (8
kb on x86 architecture) and so kernel developers should avoid static
allocation of high amounts of data or big structures;
• Concurrency and race conditions: This is one of the major
concerns for a kernel developer. Concurrency issues are bigger than
the ones a developer must face when programming a user application,
even if multi-threaded: symmetric multi-processing (SMP), kernel-
preemption and asynchronous interrupt delivery make protecting
shared data an issue that requires a lot of care. We will discuss all
this issues in the following sections.
2.2 Kernel-space and User-space
The kernel is the innermost component of the operating system and it
is responsible for managing system resources, dealing with the hardware,
sharing processor time among the different processes, and a lot of other
2.2 Kernel-space and User-space 13
HARDWARE
Device Drivers (ex: ipw2200 wireless driver)
System Call Interface (ex: sys_open)
Application Application Application
kernel-space
Kernel Subsystems (ex: Networking Subsystem)
user-space
Figure 2.1: User-space, kernel-space and hardware interaction.
low-level activities like Inter Process Communication. The Linux Kernel, as
the majority of the modern operating systems, runs in a privileged state in
comparison with user applications: it has its own protected memory space
and a full access to the hardware. This particular state is referred to as
kernel-space while the user applications run in user-space: they can not
directly access the hardware or system resources for example and they must
often interact with the kernel which doesthe low level systemoperations for
them. Whentheoperatingsystemisexecutingthekernelitisinkernel-space
and it is executing in kernel-mode; duringnormalapplication execution, the
system is in user-space and is executing in user-mode.
Each application, or better each process (in the rest of the document
processes will be called also tasks, as it is the name that is used inside the
kernel), does not live only in user-space: as it can be seen in Figure 2.1,
processes can enter the kernel-space, thus interacting with the kernel and
asking for doing some work, and they can do that through the system call
interface. Usually applications call some library function, like open, which
in turn invokes a system call (sys open, for example): the system call
invocation instructs the kernel to do some work for the process and the
kernel is said to be executing on behalf of the application and in process
context.
14 Chapter 2: Linux Kernel Development
2.3 Process and Interrupt Contexts
Aswementioned before, whenthekernelisexecuting onbehalfofaprocess,
it is said to be in process context. There is another context in which
the kernel may be executed, the interrupt context, which is active when
processing interrupts generated by hardware. Before discussing these two
different contexts, let us explain what are interrupts and how they are
generated.
One of the major concerns of the kernel is dealing with the hardware of
the machine on which it is running. Hardware may need to communicate
data to the kernel at any time but the kernel can not continuously poll
every device and piece of hardware for data, since it would be extremely
inefficient. The way in which modern systems manage this asynchronous
communication between the hardware and the kernel of the operating
system is based on the generation of hardware interrupts: each time a
piece of hardware needs to communicate with the kernel, it generates an
electrical signal that reaches the interrupt controller and carries a specific
IRQ number. If the interrupt line related to that IRQ number is active (it
can be masked out in order to disable the delivery of specific interrupts),
the interrupt controller signals the processor (if it has not globally disabled
hardware interrupts) which immediately stops whatever it is executing,
regardless of being in user or kernel modes. Then, it starts executing code
relatedtothespecificinterruptline(whichcanbefoundataspecificlocation
in memory) which in turn executes all theinterrupthandlersthat have been
registered on that line
1
. After having finished processing interrupts, the
kernel continues the execution of the code that was interrupted
2
.
When the kernel is executing in process context, the current macro
points to the data structure that describes the process that was being
executed before switching into kernel-mode to perform some task in behalf
of the process. When kernel is in process context it is able to sleep, since it
will be possible to reschedule the process for which it was working and then
resume the execution of the kernel code after it has been woken up. When
the kernel is in interrupt context we can say that it is running in behalf of
the hardware and there is no backing process. Due to this fact, interrupt
handlers are not capable of sleeping because their execution would never be
resumed (there is no associated process to reschedule). At first sight this
limitation may not appear so big, but due to it, it is not possible to execute
1
Interrupt lines can be shared among different interrupt handlers. Since all the
interrupt handlers registered on a line for a specific IRQ number are executed one after
the other, each of them must understand if the interrupt was generated by the piece of
hardware they are meant for.
2
This is not completely true since preemption (Section 2.6) may happen or bottom
half processing (Section 2.5) may start in place of going on with the execution of the
interrupted code.
2.4 Kernel Threads 15
any function that may involve sleeping, such as waiting on semaphores or
doing some file-system related operations (which may need to wait for data
being retrieved from the disks), for example.
Not only interrupt handlers run in interrupt context with such limita-
tions, but also softirqs and tasklets (since they are built on top of softirqs).
WewilldiscusssoftirqsandtaskletsinSection2.5sincetheyarealsoinvolved
with the processing of information received from the hardware along with
interrupt handlers. They can be used also for different purposes and in
general they are used for deferring kernel work to sometimes
3
in the future.
2.4 Kernel Threads
After having introduced the concepts of kernel-space and process context,
we briefly describe what are the kernel threads.
The kernel may need to accomplish some tasks in the background and
kernel threads are used for this purpose. For example, when kernel accesses
somefile,entirepages
4
ofdatabelongingtothatfilearecachedintomemory,
for speeding up further read/write accesses at the same portion of the file;
if there is the need to write some data to a portion of the file which is in
the page-cache, kernel modifies the data in the cache without immediately
writing the data on the disk. When a page in the cache contains newer data
than the correspondent page on the disk, the page is called dirty. The task
of writing the dirty pages back on the disk (when physical memory is low
or when the dirty data is very old) is accomplished by pdflush, a kernel
thread that works silently in background.
The peculiarity of kernel threads is that they are standard processes
that run only in kernel-space (they never context-switch to user-space). By
running in process context, they are capable of sleeping (this is one of the
characteristics that made them useful for our project, as it will be shown in
Chapter 4) since they can be scheduled again for execution.
2.5 Bottom Halves
As we said in Section 2.3, interrupt handlers are responsible for dealing
with interrupts generated by hardware and thus for communicating with
the hardware itself (retrieving data, for example). Since interrupts are
asynchronous events which interrupt whatever else the kernel is doing, they
must accomplish their task and then return as soon as they can. For this
reason, the work that must be done after receiving an interrupt is usually
dividedintwohalves: thetophalfandthebottomhalf. Thetophalfconsists
of the interrupt handler, which usually retrieves the data and acknowledges
3
What does “sometimes” mean will be clarified in Section 2.5.
4
A page is made of 4 kb of data on a x86 architecture.
Ricevi informazioni sui nostri servizi, sulle offerte e non perdere news e consigli su università e lavoro.
