Simon Duquennoy
email: simon.duquennoy@lifl.fr

Gilles Grimaud
email: gilles.grimaud@lifl.fr

Jean-Jacques Vandewalle
email: jean-jacques.vandewalle@gemalto.com

Serving Embedded Content via Web Applications: Model, Design and Experimentation

Keywords: C.2.1 [Computer-Communication Networks]: Network Architecture and Design-Network communications, C.2.4 [Computer-Communication Networks]: Distributed Systems-Network operating systems, C.2.6 [Computer-Communication Networks]: Internetworking Design, Experimentation, Measurement, Performance Modeling, Embedded Web server, Applicative model

Embedded systems such as smart cards or sensors are now widespread, but are often closed systems, only accessed via dedicated terminals. A new trend consists in embedding Web servers in small devices, making both access and application development easier. In this paper, we propose a TCP performance model in the context of embedded Web servers, and we introduce a taxonomy of the contents possibly served by Web applications. The main idea of this paper is to adapt the communication stack behavior to application contents properties. We propose a strategies set fitting with each type of content. The model allows to evaluate the benefits of our strategies in terms of time and memory charge. By implementing a real use case on a smart card, we measure the benefits of our proposals and validate our model. Our prototype, called Smews, makes a gap with state of the art solutions both in terms of performance and memory charge.

INTRODUCTION

Embedded systems around us such as smart cards or sensors are mainly closed systems, only able to communicate with dedicated terminals. A new trend called Web of Things [START_REF] Stirbu | Towards a restful plug and play experience in the web of things[END_REF][START_REF] Guinard | Towards physical mashups in the web of things[END_REF][START_REF] Guinard | Towards the web of things: Web mashups for embedded devices[END_REF] consists in embedding Web servers in highly constrained devices, allowing the service of dynamic Web applications. The device should embed a TCP/IP stack with the Web server in order to be as autonomous and accessible as possible. Such device can be accessed from any computer (or smart phone, PDA. . . ) simply using a standard Web browser, thus avoiding any client software development and deployment. This allows new usages, where personal devices and Internet services can easily interact. Furthermore, the development of Web applications is already widespread and well-known by companies and engineers. This makes more accessible the programming of tiny devices.

Smart cards are a great example of widespread devices: around 5 billions of devices have been released in 2008 1 (in comparison with 0.15 billion laptops2 ). Smart Card Web Server [22] is an industrial standard that allows the usage of Web servers in smart cards. With such an embedded Web server, one can access and manage its SIM card via a Web application thanks to the Web browser of its smart phone. By using Web mashup [START_REF] Liu | Towards service composition based on mashup[END_REF][START_REF] Guinard | Towards physical mashups in the web of things[END_REF][START_REF] Guinard | Towards the web of things: Web mashups for embedded devices[END_REF], private information stored on the SIM card (e.g., contacts book, last operations) may be merged with information that are only available on the Internet (e.g., telephone company special operations or various on-line service).

Providing a Web access to widespread devices is a great challenge for which we provide solutions in this paper. When working with highly-constrained devices (typical smart cards are based on an 8 bit CPU at a few MHz with a cryptographic co-processor, have around 1 kB of RAM and 16 kB of addressable EEPROM for code), usual solutions based on a Web server over an operating system (e.g., Apache/Linux, IIS/Windows) are almost impracticable. Using a Web server thought as the operating system itself is more suitable. This also makes possible dedicated cross-layer optimizations. The fact that such Web servers are only accessed by a few clients also contributes in making their usage possible.

The main idea of this paper is to fit the communication stack behavior with the properties of the Web contents being served. To achieve this objective, we describe a taxonomy of Web applicative contents, and we propose a set of strategies for each type of content. We evaluate the relevance of our strategies (i) by proposing a dedicated traffic model and metric and (ii) by conducing experiments on a smart card.

The paper is organized as follows: Section 2 presents a state of the arts of works about TCP/IP and Web servers for embedded systems. In Section 3, we introduce a dedicated TCP performance model and a metric for evaluating the cost of requests service. In Section 4, we propose a taxonomy of embedded Web contents, followed by a set of strategies for each kind of content. The strategies are designed and analyzed in relation with our model. In, Section 5, we experiment our propositions on smart cards, thus validating our model and strategies. We finally conclude in Section 6.

STATE OF THE ART

This section presents a state of the art of works related to TCP/IP stack and Web server design for embedded devices.

TCP/IP stacks for embedded systems

It has been shown with TinyTCP [START_REF] Cooper | Tinytcp[END_REF] and mIP [START_REF] Shon | Protocol implementations for web based control systems[END_REF] that by implementing a subset of TCP/IP RFCs, communication with common TCP/IP nodes remains possible.

Adam Dunkels proposed two embedded TCP/IP stacks [START_REF] Dunkels | Full tcp/ip for 8-bit architectures[END_REF]. LwIP is fully RCS-compliant and uses a layered protocol implementation (including IP, TCP, UDP and ICMP). uIP implements a subset of TCP/IP with a monolithic approach and it uses less memory than lwIP.

Because of the small size of uIP we selected this embedded TCP/IP stack as our first reference for the experiments conduced in Section 5 (uIP source code is provided including a small size Web server).

uIP is a tiny event-driven TCP/IP stack, which implementation is based on protothreads [START_REF] Dunkels | Protothreads: simplifying event-driven programming of memory-constrained embedded systems[END_REF]. Protothreads provide a blocking abstraction with extremely low memory requirements (2 or 3 bytes per protothread), without runtime stack allocation.

The Web server of uIP is able to serve static files as well as dynamic contents. Files are pre-processed then embedded with the server in the compilation phase. Dynamic contents generation is provided with JSP/ASP/PHP-like methodology: dedicated markers embedded in HTML files are substituted at runtime by the server.

Embedded Web servers

Numerous works [START_REF] Agranat | Engineering web technologies for embedded applications[END_REF][START_REF] Ju | An efficient and lightweight embedded web server for web-based network element management[END_REF][START_REF] Riihijarvi | Providing network connectivity for small appliances: a functionally minimized embedded web server[END_REF][START_REF] Shrikumar | Ipic -a match head sized webserver[END_REF][START_REF] Han | Webit: a minimum and efficient internet server for non-pc devices[END_REF][START_REF] Domingues | A simple architecture for embedded web servers[END_REF][START_REF] Lin | An embedded web server for equipments[END_REF][START_REF] Priyantha | Tiny web services: design and implementation of interoperable and evolvable sensor networks[END_REF] prove that it is possible to embed a Web server into constrained devices. Such Web servers are not executed in user-space over on operating system: they are designed as the operating system by itself. They use their own dedicated TCP/IP stack instead of usual OS abstractions (e.g., Berkeley sockets). As a consequence, they can be optimized at every software level of the system. Some of these servers provide a simple way to serve dynamic contents. Most of them make use of a dedicated tool in order to pre-process the Web contents to be served. These tools are build on a same scheme: from static files (HTML, CSS, Javascript, pictures, etc) and dynamic contents generators (c source code or enriched HTML), they produce c source files. These files are then compiled and linked with the Web server engine. The resulting binary file can directly be run by the device.

The proof-of-concept Miniweb server [START_REF] Dunkels | The proof-of-concept miniweb tcp/ip stack[END_REF] particularly drew our attention. Its goal is to provide a memory minimal Web server, simply able to serve a few static documents. It uses a monolithic implementation, i.e., with its own dedicated TCP/IP stack, tightly coupled with the Web server.

When Miniweb receives a packet, it computes incoming bytes and discards them as one goes along. Its device drivers can work with a buffer which size is independent of the TCP MSS 3 , or with no buffer. This helps Miniweb to reduce its memory consumption to only a few hundreds of bytes.

In Miniweb, IP packets are entirely pre-generated, including IP, TCP and HTTP headers and checksums. For each file to serve, a set of packets is ready to be sent in the proper order, including TCP handshakes. This allows huge simplifications in the TCP/IP stack, where the TCP state machine does not have to be implemented.

Because of its extremely low memory consumption and its interesting design choices, we choose this server as our second reference for the experiments conduced in Section 5. By using Miniweb and uIP as reference implementations, we will be able to compare respectively a monolithic HTTP/TCP/IP server with a Web server running over a TCP/IP stack.

A MODEL FOR LOCALLY ACCESSED AND CONSTRAINED WEB SERVERS

In this section, we present a model of TCP performance dedicated to embedded Web servers accessed on personal area networks. We first propose an analysis of the traffic embedded Web servers have to handle. Then, we describe a fine-grained model for TCP performance in relation with this analysis.

Preliminary remarks

We present here an analysis of HTTP, TCP and IP protocols when interacting for serving Web applications.

HTTP: a request-response model over TCP

HTTP is based on a request/response scheme where each request uses its own TCP connection (involving a three-ways handshake for opening and a four-ways handshake for closing, thus wasting 5 RTT4 ). In order to allow better interaction with TCP, HTTP 1.1 promotes the usage of keep-alive connections, allowing a Web browser to use the same connection for consecutive HTTP requests.

Impact of the TCP delayed acknowledgments

TCP delayed acknowledgments [START_REF] Braden | Rfc 1122: Requirements for internet hosts -communication layers[END_REF] is a policy used to reduce the traffic caused by void acknowledgments (with no payload). It is implemented by most of the desktop OS TCP/IP stacks (e.g., Windows and MacOS). A TCP host implementing TCP delayed ACKs only acknowledges a segment (i) 200 ms after having received it or (ii) when a second segment is received.

Many embedded TCP/IP stacks do not support more than one in-flight TCP segment5 , because this allows very lightweight and simple TCP implementations. As mentioned in [START_REF] Dunkels | Full tcp/ip for 8-bit architectures[END_REF][START_REF] Priyantha | Tiny web services: design and implementation of interoperable and evolvable sensor networks[END_REF], with such a strategy, the 200ms delay will always be triggered, bounding the maximal sending rate to 5 packets per seconds.

Typical Web applications traffic

The widely used AJAX [START_REF] Garrett | Ajax: A new approach to web applications[END_REF] methodology allows to design highly interactive applications with an efficient task repartition between the client and the server. In a previous work [START_REF] Duquennoy | The web of things: interconnecting devices with high usability and performance[END_REF], we characterized the traffic produced by some widely used Internet AJAX applications.

During a first phase, the client (i.e., the browser) collects several static files, containing style sheets (CSS), contents (XHTML), and applicative code (JavaScript). Then, it executes the applicative code downloaded in the first phase, and interacts with the server by sending asynchronous requests, allowing the Web application to run in the client browser. We observed that static files are mainly bigger (average size about 8 kB) than dynamic content (average size about 0.6 kB).

A dedicated TCP/IP performance model

Great care has been given to TCP modeling in the literature. The objective is mainly to characterize the sending rate of a bulk TCP flow as a function of packet loss and RTT [START_REF] Altman | A stochastic model of tcp/ip with stationary random losses[END_REF][START_REF] Lakshman | The performance of tcp/ip for networks with high bandwidth-delay products and random loss[END_REF][START_REF] Mathis | The macroscopic behavior of the tcp congestion avoidance algorithm[END_REF][START_REF] Padhye | A stochastic model of tcp reno congestion avoidence and control[END_REF][START_REF] Padhye | Modeling tcp reno performance: a simple model and its empirical validation[END_REF]. The complexity of these models is due to the congestion control mechanism (Tahoe, Reno, etc. [START_REF] Stevens | Rfc 2001: Tcp slow start, congestion avoidance, fast retransmit, and fast recovery algorithms[END_REF][START_REF] Floyd | Rfc 2582: The newreno modification to tcp's fast recovery algorithm[END_REF]) and to the network congestion modeling. The most precise results have been reached in [START_REF] Altman | A stochastic model of tcp/ip with stationary random losses[END_REF], in which the authors describe a rich model for network congestion.

Model presentation

We propose a TCP/IP performance model adapted to embedded devices access through a local network. The granularity of our model is the byte, and, instead of approximating asymptotic sending rates (where data of an infinite size are sent), it estimates the time needed by a host to send a content of a bounded size.

In this context, we assume that the server will not cause any congestion, because it does not generate heavy traffics in comparison with the local network capacity. The output window is limited by the server-side memory, because each TCP in-flight segment has to be kept in memory. In practice, the advertised window announced by Windows and Linux is respectively around 8 kB and 5 kB, which is greater than the available RAM in many tiny devices.

We describe the case where the delayed acknowledgements policy is used (the most common situation, because both Windows and MacOS make use of this policy). We suppose the link layer to be half-duplex, what is the true for most of the protocols supported by embedded devices (e.g., USB, ZigBee, APDU, Wifi, Ethernet).

Model definition

Our model defines ST (cs, wnd, nmax) where ST is the sending time as function of cs (the size of the content to send), wnd (the maximal number of in-flight bytes) and nmax (the maximal number of in-flight segments). We note BW the maximal link bandwidth between the two hosts, while the round trip time is noted RT T .

We note t(n, s) the time needed to send s bytes in n TCP/IP packets. Both TCP and IP headers are of 20 bytes (when used without option, the most common case):

t(s, n) = 40 × n + s BW (1)
We note T the time spent for sending cs bytes in n TCP segments and for receiving every TCP acknowledgment. Be-cause of the delayed ACKs policy, the number of void acknowledgements received is ⌈ n 2 ⌉. If the number of segments is odd, the acknowledgement for the last segment will be delayed and sent 200 ms after the reception of the segment:

T (s, n) =  t(s, n) + t `0, ⌈ n 2 ⌉ ´+ RT T if n is even t(s, n) + t `0, ⌈ n 2 ⌉ ´+ RT T + 0.2 otherwise
(2) When a host sends a content of cs bytes, it first sends d times wnd bytes. wnd is the maximal number of sent but unacknowledged bytes (equals to the sum of in-flight segments sizes). The value of d is:

d = j cs wnd k (3)
These d × wnd bytes are sent in n packets. We suppose that, in order to avoid odd number of in-flight packets (for good interaction with delayed ACKs), the TCP stack chooses an even value for n, when possible. We define a function called toEven in order to simplify our formulas:

toEven(a) =  a if n is even a + 1 otherwise (4)
Let n be the number of TCP segments used to fill each window. M SS is the TCP Maximum Segment Size.

n1 = min " nmax, toEven "‰ wnd M SS ı«« (5)
Ones d × wnd bytes have been sent, r bytes remain to send:

r = cs mod wnd (6)
The r remaining bytes are sent in n2 TCP segments:

n2 = min " nmax, toEven "l r M SS m"" (7)
Finally, the sending time ST can be calculated as:

ST (cs, wnd, nmax) = d × T (wnd, n1) + T (r, n2) (8)
Figure 1 synthesizes ST by drawing the time needed to send a content of a given size. Each curve represents a different value for nmax. The MSS is set to 1460 bytes6 , the bandwidth is set to 100 kB/s, and the RTT to 50 ms.

The sending time evolves by step, because of the discretization involved by the notion of packets. The curves highlight that poor performances are obtained when having nmax = 1. Because of the delayed ACKs, all odd values for nmax provide very bad performance. For even values, the higher nmax is, the faster is the TCP sender.

Summary and analysis

Most of the software designed for embedded devices use event-driven approaches, thus fitting with highly constrained hardware. Indeed, threaded models waste many memory. Event-driven approaches are extremely efficient to implement stateless behaviors. Stateful behaviors are more complex to implement, requiring often multiple state storage and management. Both HTTP and IP are stateless protocols, while TCP is stateful (notions of connection, sequence numbers, acknowledgments). We synthesize this analysis by highlighting the three most important properties for the TCP stack of embedded Web servers: HTTP persistent-connections handling HTTP persistent connections provide better performance, but require to manage multiple TCP connections simultaneously. It is a stateful mechanism which implementation is expensive in term of RAM and code size.

Large TCP segments management The support of large TCP segments improves the sending rate (as showed by our model), but requires to manage packets, what is hard to do in memory constrained systems. This is a stateless property.

As many embedded TCP/IP stacks, uIP is limited to one in-flight segment. In Miniweb, all the packets are entirely built off-line. It does not store sent packets in RAM, so it handles several in-flight segments. This forces Miniweb to use a constant MSS, which value has to be as small as authorized by TCP (200 bytes) for TCP compliance reasons (when a connection is penned, the MSS is chosen as the smallest value proposed by the hosts). Finally, both uIP's Web server and Miniweb do not handle persistent connections for memory saving reasons.

DEDICATING THE COMMUNICATION STACK BEHAVIOR TO APPLICATIVE PROPERTIES

In this section, we show how the communication stack behavior can be dynamically adapted to applicative content properties. We first describe a taxonomy of the contents needed by Web applications. Then we introduce a new metric in order to evaluate the cost involved on a server when serving a request. Based on this metric, we propose communication stack strategies dedicated to each kind of contents. We finally describe a software architecture able to use the strategies we proposed depending on the properties of the Web content being served.

A taxonomy of Web contents

In order to design efficient solutions for serving Web contents, we introduce a taxonomy of the different kinds of contents embedded Web applications may produce. We identified two classification criterions for contents a Web server may produce. The first criterion (noted A) of our taxonomy is the content size. It is based on two sets: A1 -Small output Contents that are smaller than the TCP output window (noted wnd in Section 3).

A2 -Large output Contents that are larger than wnd.

The second criterion (noted B) is the output persistence. We identified five sets for this criterion: B5 -Idempotent contents generators Idempotent functions are deterministic and have no side effect (inspired from Untrusted Deterministic Functions [START_REF] Kaashoek | Application performance and flexibility on exokernel systems[END_REF]). Given a context, they can be called as many times as needed, always returning the same result with no context modification. Functions that make a calculation on an input are an example of this set.

B1 -Pre-

The memory charge: a metric for request service cost

In order to evaluate various strategies for Web contents service, we introduce a new metric, called memory charge, which aim is to synthesize the cost involved on a server when serving a request.

We take the example of a popular embedded TCP/IP stack, uIP [START_REF] Dunkels | Full tcp/ip for 8-bit architectures[END_REF]. It is limited to a single in-flight segment which size is bounded by the negotiated MSS.

When serving a static content with the Web server of uIP, the memory consumption is null. In case of a packet loss, the data can be reaccessed from its persistent memory and sent again. The time needed by uIP to send a content of cs bytes is (see Section 3.2):

Ts = ST (cs, M SS, 1) (9)
When serving a dynamic content with the Web server of uIP, all in-flight segments are kept in RAM. During a first phase (a), sent segments have the size of the MSS. During a second phase (b), the remaining part of the data is sent (cs mod M SS bytes). The total time needed to serve a content of cs bytes is:

T da = ST (cs -cs mod M SS, M SS, 1) (10)
T d b = ST (cs mod M SS, M SS, 1) (11)
T d = T da + T d b = ST (cs, M SS, 1) (12)
These two examples show that the sending time is not a sufficient metric to evaluate a strategy. The amount of memory required while the transmission process carries out is also a critical criterion, but it is harder to evaluate.

We introduce the notion of memory charge in order to synthesize information about the memory usage over the time. The memory charge for a given service is the integration of the consumed memory during the sending time. It is expressed in bytes.seconds (B.s). It represents the server-side charge involved by a request on a given Web content. With a small memory charge, an embedded Web server is able to run in more constrained (and cheaper) devices, and is more scalable (it will probably not be accessed by thousands of clients, but scalability issues may appear with only a few connections).

When serving a static content with the Web server of uIP, the memory charge (noted Cs) is null because sent segments are never kept into memory. In the second example, the memory charge is:

C d = T da × M SS + T d b × (cs mod M SS) (13)

Handling the contents taxonomy

Here, we show how to serve Web contents efficiently with a cross layer perspective, from the Web application to HTTP, TCP and IP. The goal is to improve the server performance and to reduce its resources consumption. Depending on each set of our taxonomy, we identified five different strategies.

The associations between the nature of contents and the strategy we propose are presented in Table 1. We describe here all the strategies. This strategy is applied to static contents (B1, B2) embedded in persistent memory (or a cheap read only memory). Their TCP checksums are pre-calculated only once. Data are directly accessed and sent from memory. The current part of the file to be served is retrieved from the current TCP sequence number. In case of packet losses, data to retransmit can be easily re-accessed thanks to the sequence number of the lost segment.

B1 B2 B3 B4 B5 A1 S0 S0 S1 S2 S1,S2 A2 S0 S0 S3 S4 S3,S4
This strategy allows to have no limitation on the number of in-flight packets. The memory charge is null with this strategy. The service time is:

T0 = ST (cs, ∞, ∞) (14)
Let α be ⌈ cs M SS ⌉. The speed ratio between the uIP approach and this strategy, thanks to trivial calculations, can be approximated by:

Ts T0 ≈ 80 + M SS + BW × (RT T + 0.2) 60 + M SS + BW × RT T α (15)
Because cs, M SS, BW and RT T are positive integers, this ratio is always greater than 1, and grows with α, i.e., when the content size is growing or when the MSS is decreasing.

When serving a content of 8 kB (the average content size in the AJAX loading phase, measured in Section 3.1.3) with the reference network settings used in Section 3 (bandwidth of 10000 B/s, RTT of 50 ms, MSS of 1460 bytes), this speed ratio is of 11.2.

S1 strategy: "wait-for-ACK buffer".

This strategy is used for small persistent contents generators (A1/B3). The server engine calls the generator function (written by the application developer), which uses a outc routine to send data. It stores data to be sent into a buffer and calculates TCP checksums on-the-fly. When the generator ends its execution, the whole HTTP response is sent and kept in the buffer until it has been acknowledged, thus allowing possible retransmissions.

The usage of a common shared buffer is possible, allowing to serve simultaneously multiple A1/B3 contents while the amount of memory available is sufficient. If not, HTTP requests are suspended until acknowledgments are received.

With S1, the time to send the data is:

T1 = ST (cs, cs, ∞) (16)
The speed ratio between the uIP approach and S1:

T d T1 = 80 + cs + BW × (RT T + 0.2) 120 + cs + BW × RT T ( 17
)
This ratio is greater than one as soon as we have 40 < BW × 0.2, i.e., when the bandwidth is greater than 200 bytes/s. When serving a content of 600 bytes (the average content size in the AJAX running phase) with our reference network settings, this speed ratio is of 4.5. Like the uIP approach, S1 consumes cs bytes during the service. Its memory charge is:

C1 = cs × T 1 (18)
Note that the ratio between C d and C1 is equal to the ratio between T d and T1.

S2 strategy: "volatile buffer".

This strategy is used for small volatile generators (A1/B4). As for S1, the generator function written by the application developer uses outc to generate data. When the function ends, the HTTP response is sent and discarded from memory. In case of TCP retransmissions, the engine regenerates the contents by calling again the generator function in order to resend it. This strategy is as fast as S1, so it is faster than uIP approach and its memory charge is null.

S3 strategy: "stateful generators".

This strategy is used for large persistent generators (A2/B3). The generator function (written using the blocking outc routine) has to be executed only once per HTTP request. Once the buffer is full (or filled with more than one MSS), the blocking routine gives back the hand to the TCP stack, which sends one segment (or two, in order to avoid odd in-flight segments number) and continues working normally. The generator function is awaken by the engine as soon as possible, and continues its execution.

Let M be the memory allocated for one S3 service. The total time needed with S3 is:

T3 = ST (cs, M, ∞) (19)
The uIP approach uses a single buffer which size if equals to the MSS. To allow a fair comparison between uIP and S3, we set M = M SS. The speed ratio between uIP and S3 can be approximated by:

T d T3 ≈ 80 + M SS + BW × (RT T + 0.2) 120 + M SS + BW × RT T (20)
As for the S1 strategy, the performance ratio between S3 and uIP is greater than 1 as soon as the bandwidth is greater than 200 bytes/s. When serving a content of 8 kB with our reference network settings, this speed ratio is of 4.1.

Thanks to trivial calculations, the ratio between C d and C3 can be approximated by the ratio between T d and T3. S3 allows a lower memory charge than uIP.

A short analysis shows that T3 is not proportional to M : it grows slower than this last one. By using a greater value for M , the service is faster, but the memory charge degrades. With a physical bandwidth of 10 kB/s and a RTT of 50 ms, this strategy is as fast as uIP when its buffer is of only 300 bytes (compared to the 1460 bytes used by the uIP), making its memory charge sensibly smaller.

S4 strategy: "stateless generators".

This strategy is used for large volatile contents generators (A2/B4). In such situation, the generator function takes as parameters the current relative sequence number (index of the first byte to generate) and a maximal amount of data to generate. It is able to generate any part of the response at any time.

This approach fits well with volatile functions because they can be called and recalled several times with any parameters. Thereby, the connection can have many in-flight packets during the service, whatever the amount of memory available.

This strategy is as fast as S0 (it has no other limitation on in-flight segments than the output window), so it is sensibly faster than uIP, but, unlike it, its memory charge is null.

Note that when using either S2 or S4 strategy, resent segments may be different from original ones. This behavior does not fits exactly original TCP semantics, but it does not spawn any undesirable effect on TCP communications in practice.

Idempotent generators

Idempotent contents (B5) let the TCP stack choose the most efficient behavior in case of retransmission. Data can be re-generated when needed (S4), or stored in a buffer while unacknowledged (S3).

In most cases, S4 is more efficient, both in terms of memory charge and of service time. However, in some particular cases, where the generator makes heavy processing (e.g., cryptographic encryption), applying S3 will be more interesting in terms of time, memory charge, and, as a consequence, of energy. As an example, the choice between these two strategies could be based on the measured computation time of the generator routine.

HTTP content length

When serving static (B1 or B2) or small contents (A1), the engine knows the HTTP contents-length field of the response when it sends the first segment. In S3 and S4, it must use another way to identify the end of the response: it can use HTTP/1.1 chunks encoding [START_REF] Fielding | Hypertext transfer protocol[END_REF] instead of closing the connection to notify the end of the HTTP response.

Supporting the service strategies

We propose a software architecture able to handle the strategies set described in Section 4. The engine is fully event-driven and uses a cross-layer design in which HTTP and TCP/IP stack are tightly coupled. Applications are made of static and dynamic content. Dynamic content generators are written using an dedicated API allowing the engine to be aware of applicative content properties, and to apply our service strategies.

Kernel engine description

The granularity of the event-driven engine is IP packets. In the kernel, IP, TCP and HTTP are processed at the same level. Several simultaneous connections can be handled, but never more than one packet is processed at a time. Coupled with our strategies, this engine makes only use of a few (and reasonably sized) shared buffers. The input buffer can be of any size (possibly smaller than the packet sizes) if incoming data are processed rapidly enough.

The way we design TCP connections is very different from the well-known Berkeley sockets. The data structure used to store connections states does not include any buffer, making it really small (around 40 bytes). This makes possible to handle the three key points we identified in Section 3.3:

Support of multiple in-flight packets.

Our strategies allow to have no limitation on in-flight packets for most of the contents it serves (static pages, volatile and idempotent generators). In other situations, the number of in-flight segments is limited by the available memory.

HTTP persistent-connections handling.

Because our connection data structure is quite small, it is possible to support multiple simultaneous connections with low memory costs. This enables HTTP persistent connections support.

Large TCP MSS handling.

In input as output, our engine and strategies allow to handle large-sized packets even with small-sized buffers. This makes easy large MSS handling.

An API for contents generators

As described in Section 4.3, most of our strategies make use of an routine called outc, without caring for the current TCP stack state. Depending on the persistence of the generator, calls to outc involve a different behavior in the kernel engine.

Persistent generators implementation.

Both S1 and S3 strategies require a blocking outc abstraction, because they are used for persistent functions, which have to be executed only once. We propose to use protothreads [START_REF] Dunkels | Protothreads: simplifying event-driven programming of memory-constrained embedded systems[END_REF], because it is a lightweight blocking abstraction for event-driven architectures. We call PT OUTC the protothreaded outc routine.

Data: i a static integer input: samples a table to send, nb samples its size P T BEGIN preprocess samples(samples, 0, nb samples) for i=0 to nb samples do P T OU T C(samples[i]) end f lush samples(samples, 0, nb samples) P T EN D Algorithm 1: Stateful generator implemented with protothreads Algorithm 1 is an example of persistent generator function. It is written for a sensor. It pre-processes a set of sampled values, and sends them as an HTTP response. Because it has side effects, it will be handled by either S1 or S3 strategy, depending on the amount of samples. PT OUTC calls blocks until data are effectively sent and acknowledged.

Volatile generators implementation.

As S1 and S3, S2 and S4 strategies use a outc routine. Unlike persistent generators, volatile ones are executed in a given context (a sequence index and the size of the output to generate) that is provided by the TCP stack. Such a function can be written by an expert developer with no blocking abstraction. Data: start, end, i local integers input: samples a table to send, nb samples its size input: sequence index the index of the first byte to send input: buf f er length the current available buffer size start ← sequence index end ← min(start + buf f er length, nb samples) for i=start to end do outc(samples[i]) end Algorithm 2: Volatile generator implemented by an "expert" developer The generator function presented in Algorithm 2 is an example of volatile generator. It sends a set of samples, without any side effect. This function is stateless and can be called several times with any parameters (to serve or retransmit any subset of the samples). Depending on the amount of samples, it will be handled by either S2 or S4 strategy.

We propose an alternative to this "best effort" approach, using an extension of protothreads. As mentioned by their authors [START_REF] Dunkels | Protothreads: simplifying event-driven programming of memory-constrained embedded systems[END_REF], a state object can be used with protothreads for local variables storage. By holding multiple continuations and state objects per generator, the engine is able to re-run any part of generators code at any time. In fact, one couple continuation/state object is kept for each in-flight segments, allowing segments reconstruction when needed, while keeping a drastically low memory usage. In a more general context, this approach of multiple couples continuation/state objects per protothread is an interesting way to implement rerun points.

Data: start, end, i local integers input: samples a table to send, nb samples its size input: state the current state P T BEGIN for state.i=0 to nb samples do P T OU T C CT X(samples[state.i], state) end P T EN D Algorithm 3: Volatile generator implemented with our extended protothreads Algorithm 3 has the same behavior as Algorithm 2, but is written thanks to our extended protothreads. It has no explicit indexes calculation, so it is simpler to write. Here, the state object only contains the iterator.

EXPERIMENTS ON A REAL USE-CASE

In order to put to the test our proposals, we implemented a prototype, called Smews. It is built in adequacy with the software architecture described in Section 4.4.

Thanks to our prototype, we compare our proposals to the two reference embedded Web servers (uIP's one and Miniweb) when serving the same application.

To make our experiments reproducible, we made Smews source code available 7 . The source code is provided with the application example used in this paper (see Section 5.1). We choose to illustrate a complete example here, rather than micro-benchmarks.

Application description

We take the example described in Section 1. The Web server is embedded in a smart card and runs a Web application able to manage a personal contacts book.

The embedded Web application is made of four static files and three dynamic contents generators.

script.js the client-side scripts, including numerous AJAX interactions, of 3613 bytes;

cb extract idempotent generator used to retrieve the list of all contacts;

cb get idempotent generator that returns information about a given contact (specified by URLs arguments); cb add persistent generator that adds a new contacts and returns a status code.

We implemented a simplified version of the application for uIP, because it does not handle the advanced typing of Web contents. Regarding Miniweb, it is only able to serve the static files of the application. This application can be entirely supported by Smews, because it handles static and dynamic contents, as well as URL arguments. The nature of dynamic contents (persistent, volatile or idempotent) is provided by the Web application designer, via XML annotations in the c source code of dynamic content generators. It is took into account by the Smews engine at runtime.

It is important to note that in the current implementation of Smews, the choice of the strategy for serving idempotent content is not done dynamically at runtime. In our experiments, both cb extract and cb get are handled as volatile content (in-flight segments are not kept in memory).

In practice, it would be necessary to perform dynamic memory allocation for an efficient support of the S3 strategy. In our experiments, the buffer for serving persistent content has a fixed size (32 bytes for our experiments).

In other words, Smews is able to serve dynamic persistent content of any size (multiple small segments are sent), but in case of multiple concurrent requests, the output will slow down because a single buffer is shared by all the connections.

In most situations, this is not an issue because large generated content are rare (see Section 3.1.3). The most often, they simply contain some server-side informations (like cb extract), and are rarely persistent, so they do not monopolize the buffer for long durations.

Experiments configuration

For our experiments, we use a workstation using Windows XP as operating system, and Internet Explorer 6 as Web browser, the most common configuration used by clients for World Wide Web accesses 8 . It is important to remember that Windows TCP/IP stack implements the TCP delayed ACKs strategy.

To allow fair comparisons, we ported uIP, Miniweb and Smews to the same smart card, called Funcard. It uses a 8 bits AVR microcontroller at 8 MHz with 8 kB of RAM and 16 kB of EEPROM. The Funcard network interface is a serial line, with a bandwidth of 10 kB/s. Its latency involves a TCP RTT of at least 5 ms.

We presented in [START_REF] Duquennoy | The web of things: interconnecting devices with high usability and performance[END_REF] an analysis of the memory footprint of the three servers on the Funcard. uIP and its Web server require around 3 kB of RAM and 12 kB of EEPROM. Smews only needs 200 bytes of RAM and 8 kB of EEPROM. Miniweb only used 100 bytes of RAM and 4 kB of EEPROM (its functionalities are quite simple: it is unable to serve dynamic content, to handle multiple connections or a variable MSS, and does not parse HTTP requests).

Experimental results

We compare the performance and memory charge of the three embedded Web servers on the contacts book application. The procedure of our benchmark is in two steps. The first step is the initial connection of the Web browser to the smart card. The four static files are served during this phase, and the list of contacts is retrieved, thanks to a request to cb extract. During the second phase, we put to the test small contents generators: contacts are added cb add, and contacts informations are retrieved via cb get.

Performance

Table 2 shows the time spent by the three Web servers for each request on the Web application. The measurements are made using tcpdump, and compared to theoretical values computed by our model. Both measurements and theoretical values take into account the request and response transmission, including HTTP headers. As an example, uIP's Web server sends each HTTP header in two TCP segments before the content. This specific behavior is also taken into account in our calculations.

uIP's Web server and Miniweb do not handle HTTP persistent connections. To allow fair comparisons with Smews, connection establishment and closure times are only included in the global service time of the whole page. That is why for uIP and Miniweb, the time measured to send the whole Web page is sensibly greater than the sum of individual requests times.

First, our measurements highlight the performance gap between uIP and Miniweb/Smews (8.2 s for the whole page, against 2.6 or 1.8 s using Smews). This is mainly due to the limitation of uIP to a single in-flight packet. Miniweb is faster (10 %) than Smews only for the two smallest static files. This is because (i) its HTTP response contains a simplified header and (ii) it starts sending its response before having received the entire request 9 . In other cases, Smews is a faster than Miniweb (40 % for the whole page), and supports entirely the Web application (Miniweb is only able to serve the static files).

Secondly, these measurements show that our model is precise (maximal error is 11 %). On both Miniweb and Smews, the value computed by the model is always under-estimated. This is simply because it does not take into account unpredictable execution overheads in both server and client sides. Furthermore, even in our local network configuration, the TCP stack of the client has other applications and traffics to manage than those of the experiments.

Concerning uIP, the measurements are lower than the model estimations. This is because of the the particular TCP delayed ACKs implementation in Windows: in fact, the 200 ms delay is not triggered when a packet is fully received (as in our model), but when its first byte has been received.

Memory charge

Thanks to the traffic dumps we made and to the access to the servers source codes, we have been able to estimate the memory charge involved by each request on dynamic contents (for the three servers, static contents involve a null memory charge). This shows that our model is precise not only for performance evaluation, but also for memory charge. Here, the maximal error is of 11 %. We also notice that Smews allows drastically low memory charges: idempotent contents (cb extract and cb get) involve a null charge (remember that in is this example, they are served as volatile contents), while cb add sends its response (of 2 bytes) with a charge of 1.5 B.s, against 24 B.s for uIP. This shows that the strategies we proposed in Section 4.3 are efficient in terms of memory as well as of performance. When serving large generated contents, uIP has a big memory charge.

These experiments prove the efficiency of the architecture and strategies we proposed. They also show that the finegrained model proposed in Section 3 is very precise, with a maximal observed error of 11 %. Our prototype, Smews, makes a gap with the state of the art embedded TCP/IP stack and Web server both in terms of speed and memory charge. Furthermore, Smews provides a support for fullyfledged embedded Web application: it handles simultaneous HTTP persistent connections, uses a fine description of its contents generators (via our taxonomy), decodes URLs arguments, and more.

CONCLUSIONS

Most embedded devices are closed systems only able to communicate with dedicated terminals. These ad hoc solutions allow to reach the best compromises between cost and performance, but do not allow a generalized interaction between users, various devices and networks as the Internet. By working on embedded Web servers solutions, we showed that it was possible to use an already widespread applicative model in embedded devices, while keeping low hardware requirements and cost.

We established and validated a traffic model for small systems serving data over TCP. We proposed to measure the cost of each request service by integrating the server memory consumption over the sending time. The service strategies a TCP listening port for each of its Web pages.

we propose for this model allow to serve any kind of Web content efficiently and with a low memory charge. By caring simultaneously for the transport layer and applicative contents, these strategies make possible the usage of a high level applicative model in the most constrained devices. Our prototype, Smews, confirms the efficiency of our strategies in this context in comparison with state of the art solutions.

As a future work, we will focus on the usage of Web servers on sensor networks. In such context, multi-hop communications and high loss-rates invalidate a part of the initial hypothesis for our model, and introduce new open issues. We will also study the impact of secure connections support on our service strategies.

Figure 1 :

 1 Figure 1: Sending time as a function of the content size. Each curve represents a different maximal number of in-flight segments.

3 .

 3 As shown in Figure 2, it is made of two parts: a kernel engine and a set of Web applications, which are preprocessed and compiled together before being embedded in a device.

Figure 2 :

 2 Figure 2: The Web server software architecture

  defined static contents These contents are fixed off-line. Static files embedded with the server are a good example of this set. Typically, tiny Web servers are only able to serve B1 contents. B2 -Runtime static contents These contents are fixed only once at runtime, even if sent several times. A good example of such content is a SIM card that manages contacts information: each time a contact is added, new static contents are created. B3 -Persistent contents generators These contents are generated depending on the current device state (hardware state or software variables). A second call on its generator function will produce a different output or have side effects. Examples of this set are: configuration function, update of a client session, etc.

B4 -Volatile contents generators These contents must be generated as late as possible before they are received by the client. Functions used to send a value sampled from a sensor or a current device state are good example of this set.

Table 1 :

 1 Strategies applied for each kind of content of our taxonomy

S0 strategy: "pre-processed contents".

Table 2 :

 2 Table 3 synthesizes these measurements, and compares them to our model. Measured performances compared to the model (in seconds) The time needed to serve each content of the application has been measured for each Web server. The error done by the model is given as a percentage of the measurement. The speed ratio between Smews and the two reference Web servers are given.

	Content		uIP model measure	Miniweb diff. model measure	Smews diff. model measure	diff.	Speed factor uIP M iniweb Smews Smews
	Content		uIP model measure model measure Smews
	cb extract 1915 B	666	603	0	0
	cb get	28 B	29	30	0	0
	cb add	2 B	25	24	1.3	1.5

Table 3 :

 3 Measured memory charges compared to the model (in bytes.seconds)

http://www.researchandmarkets.com/

http://www.idctracker.com/

MSS stands for TCP Maximal Segment Size

RTT stands for Round Trip Time

In-flight segments are segments which have been sent but have not yet been acknowledged

1460 bytes is the most common TCP MSS, because the MTU of Ethernet is 1500 bytes

Smews source code available at: http://www2.lifl.fr/ ~duquenno/Research/Smews

World Wide Web browsers statistics available at http:// www.w3schools.com/browsers/

Miniweb does not decode HTTP requests. It simply affects


Index Terms-Analog-to-digital conversion, hybrid filter banks, wide-band, band-pass, versatility, software radio, cognitive radio.

I. INTRODUCTION

Future wireless systems will represent a real challenge as well as an outstanding opportunity over the next 10-20 years. A trend of using higher data rates (up to 1 Gb/s for instance) and high working frequencies can be noticed.

Moreover, next generation mobile communications will have to deal with a wide range of different wireless access systems (e.g. various standards, applications). So-called "software radio" introduced in 1992 [START_REF] Mitola | Software radios-survey, critical evaluation and future directions[END_REF] comes from this need for versatile multi-standard terminals or base stations. Then the idea of cognitive radio was initiated [START_REF] Mitola | Cognitive Radio: Making Software Radios More Personal[END_REF] where the terminal explore the radio spectrum and determine the portion of the frequency band that may be used for the communication link.

To achieve software radio needs, several flexible receivers appeared [START_REF] Abidi | The path to the software-defined radio receiver[END_REF] [START_REF] Chan | Design and complexity optimization of a new digital if for software radio receivers with prescribed output accuracy[END_REF]. In these receivers, a first stage downconverts the appropriate communication channel.

The signal is then converted in the digital domain through a classical A/D converter and finally digitally processed. These receivers are a step forward compared to traditional circuits that are individually customized.

They receive one channel at arbitrary frequency with any modulation. But this solution does not make it possible to perform radio spectrum sensing which is required in cognitive radio systems. In these systems, the A/D converter should be placed ideally directly in RF without any frequency translation. Also, the A/D converter should be wide-band. As an example, the set of standards GSM, UMTS, GPS and WiFi implies the conversion of the frequency band from 880 MHz to 2.5 GHz. Regarding the required resolution, a 14-bit resolution is required for the GSM standard since a 9bit resolution is sufficient for the WiFi standard. It is obvious that, considering the highest constraints, a 14 bit, 5 GS/s A/D converter is not realistic. Even if we knew In order to satisfy the cognitive radio requirements, one interesting idea could be versatile A/D converters.

Indeed, converting the whole band with a maximum resolution is certainly not necessary and would be a waste of energy. For example, the A/D converter could digitize the whole band at a rather low resolution. Once the software has explored the spectrum and found a band corresponding to pre-determined criteria, it could change the A/D converter parameters to improve the resolution in that particular band (Figure 1). We call this "frequency focusing".

In bandwidth. An HFB is said to be a "perfect reconstruction HFB" if its transfer function is a pure delay. But in reality, perfect reconstruction is not possible. So an HFB must be designed to approximate perfect reconstruction as closely as possible.

In the literature, some methods synthesize jointly the analog part and the digital part [START_REF] Velazquez | Design of hybrid filter banks for analog/digital conversion[END_REF], [START_REF] Oliaei | Asymptotically perfect reconstruction in hybrid filter banks[END_REF] and [START_REF] Löwenborg | Two-channel digital and hybrid analog/digital multirate filter banks with very low-complexity analysis or synthesis filters[END_REF].

These methods require the realization of given analog transfer functions which becomes increasingly difficult as monolithic integration dimensions decrease. Another class of synthesis methods starts from the knowledge of the analysis filter frequency responses and synthesizes the best digital part. Assuming that a calibration process makes it possible to know the analysis filter frequency responses, this technique relaxes the constraints upon the realization of the analog part. In [START_REF] Velazquez | Hybrid filter banks for analog/digital conversion[END_REF], the author finds the synthesis filters by calculating the inverse FFT of the ideal synthesis filters frequency responses but this method doesn't offer to perform any tradeoff between frequencies.

In this article, we propose global least mean square synthesis methods that start from the knowledge of the analog frequency responses. Minimizing a criterion describing the near perfect reconstruction of the HFB, these methods can take account of the knowledge of the input signal and also a possible tradeoff between performance characteristics, all of which relax constraints upon the digital part.

As above, software radio applications will lead to the conversion of high frequency band-pass signals.

So band-pass sampling should be studied in order to minimize the sampling frequency. Classical band-pass theory is here extended to the HFB case. Also, HFB synthesis methods are extended to the band-pass case.

Concerning versatility, the frequency focusing idea may be achieved in HFBs. Global least mean square synthesis methods have been adapted in order to synthesize digital filters so that the resolution is improved in a October 9, 2009 DRAFT In Section II, the well-known perfect reconstruction equations are given. The main characteristics of HFBs are defined; i.e. distortion and aliasing. HFB design methods aimed at relaxing the analog design constraints are presented. Section III presents HFB adaptation to software/cognitive radio needs. First, the band-pass sampling for HFBs is presented and followed by the synthesis method to perform frequency focusing. Finally, robustness regarding analog versus digital mismatch is studied. Section II and III are illustrated with simulation results.

M M M q M q 2 q 1 z ( ) (z (n) (n) (n) (s) (s) (s) (n) (t) F 2 ( ) z H 2 F 1 F M H 1 MT MT MT Analysis bank Synthesis bank + x 2d 1 H M x x Md d x ) y T

II. HFB A/D CONVERTERS THEORY AND DESIGN METHODS

A. Review of HFB theory

Figure 2 shows a maximally decimated HFB of M channels. x(t) is the real input signal to be digitized at 1/T rate and y(n) is the digital output of the HFB. H m (s) are the continuous-time analysis filter transfer functions and F m (z) are the discrete-time synthesis filters transfer functions, with m ∈ {1, 2, ..., M }. The blocks q 1 , ..., q M are the branch quantizers. After analog filtering, the branch signals x m (t) are sampled at a rate of 1/M T . Ignoring the quantizers, the Fourier transform of the HFB output signal y(n) is [START_REF] Velazquez | A hybrid filter bank approach to analog to digital conversion[END_REF], [START_REF] Löwenborg | On the frequency response of M-channel mixed analog and digital maximally decimated filter banks[END_REF]:

Y (e jω ) = 1 T ∞ p=-∞ T p (e jω )X jΩ -j 2πp M T (1)
with

T p (e jω ) = 1 M M m=1 F m (e jω )H m jΩ -j 2πp M T , (2)
ω = Ω T,
where X(jΩ ) is the Fourier transform of x(t), Ω the pulsation and ω the normalized pulsation.

It is assumed that the input signal is strictly bandlimited to B. In this case, the Nyquist criterion for sampling with an effective sampling frequency of 1/T = 2B

without aliasing is fulfilled. (1) can then be rewritten as follows:

Y (e jω ) = 1 T M -1 p=-(M -1) T p (e jω )X jΩ -j 2πp M T (3)
because, for -π < ω ≤ π, only 2M -1 terms have non zero contributions [START_REF] Löwenborg | On the frequency response of M-channel mixed analog and digital maximally decimated filter banks[END_REF]. Perfect reconstruction means that the output y(n) is only a scaled, delayed and sampled version of the input. Therefore, perfect reconstruction conditions will be [START_REF] Velazquez | A hybrid filter bank approach to analog to digital conversion[END_REF], [START_REF] Löwenborg | On the frequency response of M-channel mixed analog and digital maximally decimated filter banks[END_REF]:

T p (e jω ) =    ce -jωρ , p = 0, ρ ∈ R + * , c ∈ R * 0 , p ∈ P. ( 4
)
October 9, 2009 DRAFT where ρ is the overall HFB's delay, c is the scale factor and P = {-(M -1), ... -1, 1, ..., M -1}.

B. HFB performance evaluation

The perfect reconstruction conditions cannot be achieved [START_REF] Velazquez | Design of hybrid filter banks for analog/digital conversion[END_REF]. The HFB output signal consists of the input signal whose magnitude and phase are damaged, and additive parasitic aliasing signals, all of which limit the resolution of the system. As a remark, in this work, analog filters and A/D converters are supposed linear. So, we don't take into consideration nonlinear distortion like intermodulation (except quantization when precised).

We define two major performances to characterize the HFB quality reconstruction: the distortion function R(ω)

given in ( 5) and the aliasing functions T p (e jω ), p ∈ P.

R(ω) = T 0 (e jω ) ce -jωρ (5)
This distortion function has ideally a magnitude equal to

T otalAliasing(ω) = p∈P T p (e jω ) 2 (6)

C. HFB implementation constraints

HFB design needs analog filters, elementary A/D converters and digital filters.

The digital part performances are essentially limited by the processing power and the calculation accuracy.

Fortunately, technological progress will make it possible to push back these limitations. It will always be necessary, however, to minimize the size of the digital part in order to minimize both cost and power consumption.

A/D converters limitations are essentially the sampling frequency, the resolution and the input bandwidth. In the case of a direct RF conversion, the input bandwidth requirement is stronger than for an IF conversion. This is a technological aspect that concerns the sample and hold part of A/D converters.

Regarding the analog part, high frequency analog filter integration is tricky. The design of the analog part becomes increasingly difficult as the filter order or the quality factor become higher. And above all, manufacturing errors of passive components may be up to 20% and even more. Moreover, these errors change depending on ageing and temperature. Tuning is a possible solution to approach the desired analog filters transfer functions but this is a costly solution. Paragraph III-C1 shows that these phenomena affect HFB performance a lot.

Therefore the chosen strategy here is to maximally relax the realization of the analog part. To do that, the presented methods start from the knowledge of the frequency responses of the analog filters and calculate the corresponding digital filters in order to minimize the aliasing and the distortion. Thus, easily feasible bandpass analog filters can be chosen.

D. HFB design methods relaxing implementation constraints

The following methods calculate FIR synthesis filters.

Therefore, their transfer functions are:

F m (z) = N -1 n=0 f m (n)z -n , m ∈ {1, 2, ..., M }. ( 7
)
October 9, 2009 DRAFT where f m (n) are the coefficients of the impulse response of digital filters. In this case, the synthesis problem is linear. So the coefficients may be found in a least square sense.

Eight-channel HFBs have been designed with the following methods. Paragraph II-E gives the results and compares the methods.

1) Least mean square local approximation HFB synthesis method (LMSLA):

This method was first applied in [START_REF] Lelandais-Perrault | Synthesis of hybrid filter banks for A/D conversion with implementation constraints -direct approach[END_REF]. We consider more general synthesis filter frequency responses F m (ω).

(2) becomes:

T p (e jω ) = 1 M M m=1 F m (e jω )H m jΩ -j 2πp M T , (8)
Perfect reconstruction are:

T p (e jω ) =    ce -jωρ , p = 0, ρ ∈ R + * , c ∈ R * 0 , p ∈ P. ( 9
)
where ρ is the overall HFB's delay, c is the scale factor Noting f m the vector of coefficients for the m-th synthesis filter:

f m = [f m (0), ..., f m (N -1)] (10)
For each branch m, the best filter coefficients values of f m are obtained so that the actual frequency response fits the desired K-point values in the square error sense.

The optimization algorithm is the standard Matlab one (namely Gauss-Newton). Paragraph II-E shows that the results are not satisfactory and can be much better using the global approximation methods that follow.

2) Least mean square global approximation HFB synthesis method -Discrete-frequency criterion (LMSGAD):

This method has been presented in [START_REF] Petrescu | Synthesis of hybrid filter banks by global frequency domain least square solving[END_REF]. Perfect reconstruction conditions (4) are written for each of the K pulsation values equally distributed in [-π, π] interval, using (2) for T p (e jω ) and ( 7) for F m (e jω ):

T p (e jω k ) =    ce -jω k ρ , p = 0, ρ ∈ R + * , c ∈ R * 0 , p ∈ P (11)
k ∈ {1, 2, ..., K}, where:

T p (e jω k ) = 1 M M m=1 F m (e jω k )H m jΩ k -j 2πp M T . ( 12
)
with

ω k = Ω k T.
For a given ω k , (11) is a system of 2M -1 complex equations or, equivalently, 2 × (2M -1) real equations.

Hence, a linear system of 2×(2M -1)×K real equations and M ×N unknown variables results. For a matrix form of the above equation system, the definitions of different vectors follow:

e(ω) = 1 e -jω • • • e -j(N -1)ω ( 13
)
The vector of the FIR filter coefficients is:

f = f 1 • • • f M T ( 14
)
where A T denotes the transpose of the matrix A. The matrix of the shifted versions of all the analog filters H m (jΩ ) with the elementary delays of the synthesis filters contribution is:

H K =         H(ω 1 )
H(ω 2 ) . . .

H(ω K )         . ( 15
)
The matrix H(ω) may be seen in ( 16) for typographic constraints. H

H (p) m (jΩ ) = H m jΩ -j 2πp M T . ( 17
)
With the following notation:

t K =         t(ω 1 ) t(ω 2 ) . . . t(ω K )         (18)
where

t(ω) = cM e -jωρ 0 • • • 0 T ( 19
)
H R =   Re {H K } Im {H K }   (20)
and

t R =   Re {t K } Im {t K }   , (21)
the matrix form of the perfect reconstruction conditions written for the given set of frequency values is:

H R f = t R . ( 22
)
Re {A} and Im {A} denote respectively the real and the imaginary part of the matrix A.

In the general case, the system ( 22) is overdetermined and inconsistent. However, a least square solution can be found [START_REF] Strang | Linear algebra and its applications[END_REF]:

f = (H R T H R ) -1 H R T t R (23)
which minimizes the square sum of the error vector (the error vector's Euclidean norm):

∆ = H R f -t R 2 . ( 24
)
3) Least mean square global approximation HFB synthesis method -Continuous-frequency criterion (LMS-GAC): Approach the perfect reconstruction for a given pulsation consists in minimizing the following criteria:

J(ω) = H(ω)f -t(ω) 2 (25)
where H(ω), f and t(ω) are defined above. ( 25) is equivalent to:

J(ω) = (H(ω)f -t(ω)) † (H(ω)f -t(ω)) = f † H(ω) † H(ω)f -f † H(ω) † t(ω) -t(ω) † H(ω)f + t(ω) † t(ω) (26)
where A † denotes the conjugate transpose of A. The integration of J(ω) over the whole band [0, π] gives the global criterion J:

J = f † Σf -f † α -α † f + r ( 27
)
where:

Σ = π 0 H(ω) † H(ω)dω (28)
H(ω)=                  H (0) 1 (jΩ )e(ω) H (0) 2 (jΩ )e(ω) • • • H (0) M (jΩ )e(ω) H (1) 1 (jΩ )e(ω) H (1) 2 (jΩ )e(ω) • • • H (1)
M (jΩ )e(ω) . . . . . . . . .

H (M -1) 1 (jΩ )e(ω) H (M -1) 2 (jΩ )e(ω) • • • H (M -1) M (jΩ )e(ω) H (-1) 1 (jΩ )e(ω) H (-1) 2 (jΩ )e(ω) • • • H (-1)
M (jΩ )e(ω) . . . . . . . . .

H (-(M -1)) 1 (jΩ )e(ω) H (-(M -1)) 2 (jΩ )e(ω) • • • H (-(M -1)) M (jΩ )e(ω)                  (16)
October 9, 2009 DRAFT

α = π 0 H(ω) † t(ω)dω (29) r = π 0 t(ω) † t(ω)dω (30)
Σ is a M × N -by-M × N matrix. α is a M -by -N -length column vector and r is a scalar. Moreover, because of the Hermitian characteristic of the matrix Σ and because the digital filter coefficients are real, this leads to:

f † Σf = f T Re(Σ)f (31)
Also, f T α = α T f , then:

J = f T Re(Σ)f -f T α -f T α * + r (32)
The minimum value of this criterion is found by derivating J and by cancelling this function:

∂J ∂f = 2Re(Σ)f -α -α * = 0 (33)
The solution can be found by solving the following system:

Re(Σ)f = Re(α). ( 34
)
The solution in a mean square sense is: For a given HFB, oversampling of the input signal improves its performances (see paragraph II-E). But, the performances would be significantly improved if the oversampling is taken into account in the design method.

f = (Re(Σ) T Re(Σ)) -1 Re(Σ) T Re(α) (35
To do that, let's consider the following weighting function.

W (jΩ ) =    1 , -η π T < Ω < η π T , otherwise (36)
where ∈ R + * , << 1. Therefore perfect reconstruction conditions will be:

T W p (e jω ) =    ce -jωρ W (jΩ ) , p = 0, ρ ∈ R + * , c ∈ R * 0 , p ∈ P ( 37
)
where

T W p (e jω ) = 1 M M m=1 F m (e jω )H m jΩ -j 2 πp MT W jΩ -j 2 πp MT ( 38
)
with ω = ΩT .

If [START_REF] Lelandais-Perrault | Band-pass hybrid filter bank A/D converters with software-controlled bandwidth and resolution[END_REF] and [START_REF] Löwenborg | Analysis of gain and timeskew errors in filter bank based A/D converters[END_REF] are respectively rewritten as follows:

H (p) m (jΩ ) = H m jΩ -j 2πp M T W jΩ -j 2 πp MT , ( 39
)
t(ω) = cM e -jωρ W (jΩ ) 0 • • • 0 T , (40)
(23) or (35) give synthesis filters that take into account the input signal oversampling.

E. Simulation results of HFBs with FIR synthesis filters

Several eight-channel HFBs have been designed from a given analysis filter bank. Considered analysis filter frequency responses are shown in Figure 3. They correspond to the frequency responses of pure resonators whose transfer function is: where Ω m is the resonator frequency and Q m its quality factor. Also, a first order low-pass filter is considered for the lowest frequencies. Its transfer function is:

H m (s) = Ω m Q m s s 2 + Ω m Q m s + Ω 2 m ( 41
H 1 (s) = Ω 1 s + Ω 1 , Ω 1 = 1 R 1 C 1 , ( 42
)
where Ω 1 is the cut-off frequency of the filter. Each synthesis filter has 128 coefficients.

For each synthesis, K = 512 pulsation values have been considered for the calculations in [-π, π] interval.

Concerning the LMSGAC method, the integral terms have been calculated by using a rectangular approximation performed on the same points as for the other methods.

Table I gives the main characteristics of all synthesized

HFBs. Figure 4 shows the distortion and the total aliasing magnitudes throughout the band for some HFBs. The maximum equivalent resolution expressed in bit may be evaluated by considering the classic 6 dB/bit formula [START_REF] Walden | Analog-to-Digital Converter Survey and Analysis[END_REF]. LMSLA HFB has a mean equivalent resolution assuming that the signal is slightly oversampled by 2%, the mean equivalent resolution is 11 bit and even 16 bit with an oversampling of 3%. So the LMSGAD method is better than the LMSLA one especially because the input signal oversampling can be taken into account in the LMSGAD method. Compared to LMSGAD, the LMSGAC method gives the same results. However, the LMSGAC method is a little bit more demanding than LMSGAD regarding calculations.

In the next sections, only the LMSGAD method is used.

III. HFB ADAPTATION TO SOFTWARE/COGNITIVE RADIO APPLICATION

In order to give a rough idea of the frequency need, let's imagine a software radio application example that would process GSM, UMTS, WiFi and GPS standards with a single device. To do this, the digitization system should convert the bandwidth [880 MHz, 2. sampling frequency. To do this, band-pass conversion is one solution.

A. Band-pass HFB

In classical receiver, the A/D conversion is preceded by a downconversion performed by analog mixers. Also, some parallel structures [START_REF] Mazlouman | A frequency-translating hybrid architecture for wide-band analog-to-digital converters[END_REF] use an analog downconversion. In our work, one of the objectives is to make the analog part as simple as possible, partly by suppressing the downconversion stages. To do that, we chose to make band-pass sampling.

1) Band-pass signal conversion:

For a wide-band band-pass signal x(t) bandlimited between f max -B and f max , it is possible to sample at a frequency lower than 2f max without aliasing. At the same time, it makes it possible to recover the signal in baseband.

Among the infinite number of terms of (1), we note p + the index of the term that corresponds to the signal translated to baseband by the sampling (for positive frequencies). The value of p + depends on the input signal band position and on the number of channels M .

The Fourier transform of the HFB output is then:

Y (e jω ) = 1 T p++(M/2-1) p=p + -(M -1)
T p (e jω )X jΩ -j 2πp M T

+ -p + +(M -1) p=-p+-(M/2-1)
T p (e jω )X jΩ -j 2πp M T .

(

) 43
Perfect reconstruction conditions become:

T p (e jω ) =    ce -jωρ , p ∈ {p + , -p + } 0 , p ∈ P . ( 44
) P = {p + -(M -1), ...p + +(M/2-1)}\{p + } {-p + - (M/2 -1), ..., -p + + (M -1)}\{-p + }.
The minimum sampling rate depends on f max with the relation given in [START_REF] Vaughan | The theory of bandpass sampling[END_REF]:

f (min) s = 2f max n ( 45
)
where n is the floor value of f max /B. This relation is applicable for a single-rate A/D conversion. In the HFB case, on each channel, an overlapping occurs every 2π/M T (see ( 1)). So, the minimum sampling frequency is:

f (min) s = f max M n ( 46
)
where n is the floor value of f max M/(2B). The HFB design methods described in Section II-D can easily be adapted for a band-pass sampling as explained in [START_REF] Lelandais-Perrault | Band-pass hybrid filter bank A/D converters with software-controlled bandwidth and resolution[END_REF]. Table II shows detailed performances of an HFB synthesized with the LMSGAD method with an oversampling of 3%. Figure 7 shows the total aliasing and the distortion magnitudes. The total aliasing mean level is equivalent to a resolution of 11 bit.

B. Frequency focusing

Let's suppose that an HFB A/D converter converts a wide band signal at a resolution that could be rather low but sufficient to give a rough idea of the communication channel to be chosen. After the choice of the appropriate communication channel, a higher resolution (together with a narrower bandwidth) might be required. coefficients to improve the performances in the selected frequency band as illustrated in Figure 1. We present below a method to synthesize synthesis filters adapted to a narrower frequency band [START_REF] Lelandais-Perrault | Band-pass hybrid filter bank A/D converters with software-controlled bandwidth and resolution[END_REF].

1) Synthesis method:

In the following, B f is the selected frequency band. To synthesize a focused HFB, the main idea is to weight differently the values of the LMSGAD criterion in B f . This leads to the weighted criterion ∆ W f .

∆ W f = diag(w f )(H R f -t R ) 2 (47)
where:

w f = w d w r • • • w r T ( 48
)
with:

w d = 1 1 • • • 1 (49) w r = W r (ω 1 ) W r (ω 2 ) • • • W r (ω K ) (50)
In (47), w d is applied to the distortion term, and w r is applied to each aliasing term. W r (ω) is a window function is equal to 1 where the frequency focusing is desired and a lower value outside that band, it makes it possible to relax constraints in this area and to improve the performances in the selected band. Also, if W r (ω) is equal to a value higher than 1 in the selected area, it relaxes constraints upon distortion and therefore, improves aliasing in this area.

2) Simulation results of frequency focusing:

The band-pass analysis filter bank in Figure 6

C. HFB robustness

The HFB principle is very attractive to enlarge conversion bandwidth. But to become a realistic solution for wide-band applications, HFBs should be robust enough.

So, it is necessary to study the HFB sensitivity to imperfections. The first type of imperfections is analog filters errors. Indeed, manufacturing causes errors which make the frequency responses different from the expected ones. The second type of imperfections is caused by the mismatch between A/D converters. This mismatch can be characterized by gain, offset and phase mismatches which are studied in [START_REF] Petraglia | High speed A/D conversion incorporating a QMF bank[END_REF], [START_REF] Velazquez | Hybrid filter banks for analog/digital conversion[END_REF] and [START_REF] Löwenborg | Analysis of gain and timeskew errors in filter bank based A/D converters[END_REF]. The third type of imperfections is digital filtering errors. This consists of errors caused by the quantization of the signal [START_REF] Löwenborg | Quantization noise in filter bank analog-to-digital converters[END_REF] and the quantization of coefficients of the digital filters.

In this work, we study the effect of analog component errors and also the effects of the quantization of digital filter coefficients.

1) Effects of analog components realization errors:

This section studies one of the most important drawbacks

H m (s) = Ωm Qm (1 + ∆ 1m )s s 2 + Ωm Qm (1 + ∆ 1m )s + Ω 2 m (1 + ∆ 2m ) , ( 51
) m ∈ {2, ..., M }, H 1 (s) = Ω 1 (1 + ∆ 11 ) s + Ω 1 (1 + ∆ 11 ) . ( 52
)
In ( 51) and (52) ∆ 1m and ∆ 11 are the relative errors of the coefficients of the analog filters:

∆ 1m = ε Rm ε Cm + ε Cm + ε Rm 1 + ε Rm ε Cm + ε Cm + ε Rm , ( 53
)
∆ 2m = ε L m ε C m + ε C m + ε L m 1 + ε L m ε C m + ε C m + ε L m , ( 54
)
where m ∈ {1, ..., M } and ε Rm , ε Cm , ε Lm are the relative realization errors of the analog components of the resonators. In order to evaluate the error effects on the distortion and aliasing functions, a Monte Carlo simulation with 1000 trials was performed using (53) Other filter structures were studied. Higher order Butterworth filters were also considered since they are used as analysis filters in some previous HFB designs [START_REF] Velazquez | Design of hybrid filter banks for analog/digital conversion[END_REF].

Third order Butterworth filters were taken into account for this study. Again, a Monte Carlo simulation with 1000 trials was performed for a four-channel hybrid filter bank with 128-length FIR synthesis filters. The results are shown in table V. The aliasing is 51 dB higher than in the case without errors, which means a 8 bit resolution loss.

Even with a 1% error on analog components (which is quite optimistic in high frequency technology), the distortion and aliasing functions are degraded so that the equivalent resolution looses at least 8 bit.

ε C m = 0.01

2) Effects of digital filter coefficient quantization:

In this section, only the errors caused by the quantization of the digital filter coefficients are considered. A fixed arithmetic representation for filter coefficients is supposed to be used and no analog realization errors are taken into account. The error that the quantization of the coefficients produces in the transfer function can be easily evaluated. If the desired transfer function is:

F m (e jω ) = N -1 n=0 f m (n)e -jωn , m ∈ {1, 2, ..., M } (55)
then the implemented one is:

F m (e jω ) = N -1 n=0 f m (n)e -jωn . ( 56
)
The error introduced by coefficient quantization is:

E m (e jω ) = F m (e jω ) -F m (e jω ) = N -1 n=0 m (n)e -jnω , (57)
where

m (n) = f m (n) -f m (n). If a rounding quantiza- tion is used, then m (n) ∈ -∆ 2 , ∆ 2
, with ∆ = 2 -B q and B q is the length of the digital word and: The error appearing in the distortion and aliasing functions can be written as: bit in order to limit the aliasing so that the required resolution is obtained. In the given example, if a mean 14-bit resolution is needed, a 16-bit quantization of the digital coefficients is sufficient. Concerning the analog errors, the sensitivity is much more important. A solution could be to measure the analysis filter frequency responses and to calculate the synthesis filters with the LMSGAD method. This could be done by a calibration process or blind estimation. Some results are given in [START_REF] Asemani | Digital estimation of analog imperfections using blind equalization[END_REF], [START_REF]Modelling the imperfections of analog circuits using second-order statistics[END_REF] and [START_REF] Asemani | Subband architecture for hybrid filter bank a/d converters[END_REF]. [START_REF] Pinheiro | Improving the near-perfect hybrid filter bank performance in the presence of realization errors[END_REF] proposes an other solution that minimizes reconstruction and realization error energies.

E m (e jω ) ≤ N -1 n=0 | m (n)| = N ∆ 2 . ( 58
E T p (e jω ) = T p (e jω ) -T p (e jω ). (60

IV. CONCLUSION

In the context of software/cognitive radio applications, HFBs A/D converters are an attractive solution for future A/D conversion systems. First, HFBs make it possible to enlarge the conversion bandwidth. Bandpass HFBs can also be useful to minimize the sampling frequency. This aspect is particularly interesting in the ideal desired scheme of a direct RF conversion. Finally, HFBs offer software controlled versatility. The presented "frequency October 9, 2009 DRAFT focusing" functionality is a way to improve the resolution in a narrower bandwidth by reprogramming the digital part. This is useful if the system needs to perform alternately spectrum sensing and communication.

However, the main drawback of these structures is

  Wide-band, band-pass and versatile Hybrid Filter Bank A/D conversion for software radio Caroline Lelandais-Perrault, Tudor Petrescu, Daniel Poulton, Pierre Duhamel and Jacques Oksman Abstract-This paper deals with analog-to-digital (A/D) conversion for future software/cognitive radio systems. For these applications, A/D converters should convert wideband signals and offer high resolutions. In order to achieve this and to overcome technological limitations, the A/D conversion systems should be versatile, i.e. it should be possible to adapt the conversion characteristics (resolution and bandwidth) by software. This work studies and adapts Hybrid Filter Banks (HFBs) in this context. First, HFBs, which can provide large conversion bandwidth, are extended to band-pass sampling, thus minimizing the sampling frequency. Then, we provide efficient ways of improving the HFB resolution in a smaller frequency band, only by reprogramming the digital part. Moreover, this study takes into account the main drawback of HFBs which is their very high sensitivity to analog imperfections. Simulation results are presented to demonstrate the performance of HFBs.

Fig. 1 .

 1 Fig. 1. Illustration of future A/D conversion versatility: frequency focusing

  this work, we propose to study the Hybrid Filter Bank A/D converters and adapt them to the cognitive radio needs. The HFBs are multi-rate systems that use a 3-stage process: analog frequency band decomposition through an analysis filter bank; A/D conversion; and finally, digital reconstruction through a synthesis filter bank. HFBs are interesting because from a given sampling rate on each channel, it enlarges the conversion

Fig. 2 .

 2 Fig. 2. Maximally decimated hybrid filter bank structure

1 and a phase equal to 0 .

 0 Concerning aliasing, each T p (e jω ), p ∈ P, defines an aliasing transfer function for which it is possible to calculate mean and maximum values throughout the band. This leads to 2M -2 values and complicates the comparison between two HFBs. We propose to calculate a synthesis of all aliasing functions. Considering aliasing terms as decorrelated noises, the total aliasing function consists in summing the powers of aliasing functions:

  and P = {-(M -1), ... -1, 1, ..., M -1}. Considering K pulsation values ω k equally distributed in [-π, π], F m (ω k ) may be calculated by resolving the perfect reconstruction system. Then, each F m (ω) frequency response is approximated by a FIR filter F m (e jω ) frequency response.

  (p) m (jΩ ) is the 2πp/M T shifted version of October 9, 2009 DRAFT H m (jΩ ):

) 4 )

 4 Slight oversampling of the input signal: We will show that the performance is better if the input signal is slightly oversampled. Indeed, assuming that the input signal is band-limited to B, the design of an HFB reconstructing a signal sampled at 2B may lead to discontinuities of the ideal synthesis filters frequency responses. With a limited number of coefficients of the synthesis filters, aliasing will be much more important around pulsations 2πp/M T (p ∈ {-M, ..., M }). To decrease aliasing in these areas, we may sample the signal with a slightly higher rate of 2B/η, 0 < η < 1, with η close to 1.Regarding design methods, this is equivalent to assuming that the input signal is limited to the frequency band [-η/T, η/T ]. (1/η -1) corresponds to the oversampling ratio.

Fig. 3 .

 3 Fig. 3. Analysis filter bank magnitude responses

of 6 0 9 Fig. 4 .

 694 Fig. 4. Total aliasing and distortion magnitudes of HFBs synthesized with the LMSLA and LMSGA methods

Figure 5 showsFig. 5 .

 55 Fig. 5. Minimum sampling frequency for a band-pass signal with fourchannel (dashed line) and eight-channel (full line) HFB compared to the Nyquist frequency criterion (dotted line)

2 )Fig. 6 . 4 Maximum magnitude distortion (dB) 2 . 7 • 10 - 2 6 Maximum phase distortion (radian) 3 . 4 • 10 - 3 (

 26427102634103 Fig. 6. Analysis filter bank magnitude responses

0

  Fig. 7. Band-pass HFB total aliasing (full line) and distortion (dashed line) magnitudes

0Fig. 8 .

 8 Fig. 8. Band-pass HFB total aliasing (full line) and distortion (dashed line) magnitudes with frequency focusing in B f = [0.1/T, 0.2/T ] band

  is considered. The previously described synthesis method is used for a frequency focusing on B f = [0.1/T, 0.2/T ]. The function W r (ω) is equal to 10 in B f and 0.001 outside.

Figure 8

 8 Figure8shows the total aliasing and the distortion magnitudes of the resulting HFB. TableIIIshows that a 48 dB improvement in aliasing characteristics may be achieved within the reduced band B f (the distortion being almost the same).

Finally, without 7 • 10 - 6

 7106 focusing, the best possible equivalent resolution is 8 bit throughout the B band which may be sufficient for the spectrum sensing mode. With frequency focusing on B f , the possible resolution becomes 15 bit in B f which is sufficient for GSM standard. Maximum phase distortion (radian) 3.7 • 10 -4 1.9 • 10 -3

  of implementing A/D converters in HFB structures: the degradation of the HFB performances in the presence of analog components realization errors.In order to study the influence of realization errors, a realistic example has been chosen. Very simple Gm-LC

Fig. 9 .

 9 Fig. 9. (a): Resonator filter structure, (b): Low-pass filter structure

  and (57), the implemented aliasing and distortion functions are:T p (e jω ) = T p (e jω )+ 1 M M m=1 E m (e jω )H m jΩ -j 2πp M T , (59)p ∈ {-(M -1), ... -1, 0, 1, ..., (M -1)}.

)

  Let us assume |H m (e jω )| ≤ 1 and consider a uniform distribution of the analog filter frequency responses in the working frequency band (e.g. resonators with equally spaced central frequencies). In the passband of each analysis filter, the other filters present important attenuations.Hence:E T p (e jω) max ≈ is useful after the design phase to decide the necessary number of bit for the FIR coefficient quantization. The error introduced by coefficient quantization (61) must be smaller than the aliasing and distortion errors obtained in the design process. An eight-channel HFB was considered. Equally spaced, constant band resonators were used as analysis filters. Tests were made for different fixed point formats for coefficient quantization. No deterioration was noticed in the case of the 32-bit fixed point compared to the reference floating point. When 16-bit quantized coefficients are used, (61) results in a predicted error value of -78 dB in the aliasing functions. The same result was obtained in the simulation: the aliasing peak deteriorated from the initial -112 dB to -78 dB due to 16-bit quantization. The simulation results are summarized in

  their sensitivity to the mismatch between the analog and digital parts. The presented HFB design methods optimize the digital filters based on the knowledge of the analog filter frequency responses. This makes it possible to maximally relax constraints on the realization of the analog part. It is clear that an estimation of the analysis filter frequency responses is necessary. A complete study of a calibration method or other solutions such as blind estimation is a topic for further work.

Table VI .

 VI Concerning the digital coefficient quantization, it is possible therefore to determine a minimum number of

October 9, 2009 DRAFT