Geeky content...

Towards an "Evolved Packet Edge"

2012-02-07T02:51:00.000-08:00

There is a lot of discussion about the "Evolved Packet Core" in the telecom world these days. However, there is a lot of 'Evolution' happening on the edge of the mobile internet which gets lesser attention. In this article I shine some light on the evolution happening at the edge. There are 2 major themes driving this evolution of the network edge -

Small Cells (Include both the lower capacity base stations (3G/4G femtocells and picocells) and Wi-Fi access points in this category) - Given that spectrum is limited and too expensive, operators have realized they have to include a large number of these small cells as a part of their network. The inclusion of small cells in the network leads to a huge increase in the number of "RAN nodes" that the mobile core network needs to talk to, thus disrupting the scaling equations of their core network elements
A large part of the mobile data traffic is video and this traffic is very latency and jitter sensitive. So, the Content Delivery Networks (CDNs) are becoming more and more distributed to deliver content from a point nearest to the end user

Both of the above points call for a distributed architecture for the evolved packet core, in order to scale better as well as to provide a better end user experience. The SAE-EPC architecture allows for distributing the evolved packet core network elements and locating the S-GWs and P-GWs closer to the end users. However, most of these network elements are built on top of the same hardware platform used for SGSNs and GGSNs (3G core network elements). Also, in most cases multiple logical elements are physically co-located on the same box in order to reduce the amount of signaling messages between the different logical elements in the EPC network. For these reasons, most of the available EPC elements today are better suited for a centralized deployment model.

While the EPC elements may eventually become more distributed, it may not happen in a hurry. So, until then what are the options to deliver a better end user experience and scaling of the network? The answer seems to be to move towards a more distributed architecture using "Edge gateways" like the Femtocell Gateways and WiFi access gateways that are defined by 3GPP, as shown in the below diagram -

As shown in the above diagram, these 'Evolved packet edge' devices like the Femtocell Gateways and the WiFi access gateways can be more distributed, and could support "Selective" offloading of the internet traffic to the internet POP directly without routing this traffic to the packet core.

These edge devices will need to talk to the EPC elements for all the control plane signaling, for authenticating the users, for downloading the offload related policies etc. So, the EPC elements will still be fully in charge of the sessions, but then they could decide that a certain set of "Flows" need not be routed all the way to the core network, and decide to offload them away to the internet POP at the edge itself. To enable this selective offloading there are certain standard (SIPTO comes to mind) and a few non standard mechanisms.

So, in a nutshell, by employing these "Evolved packet edge" network elements and distributing them strategically, the operators can gain the the following benefits -

Reduce the load on their core network elements
Offer a better end user experience
Reduce cost by getting rid of routing inefficiencies caused by the centralized approach

Given the strategic position these edge devices are located in the network, they should be able to participate in the network in many innovative ways in the near future.

Handover problem with LTE Femtocells

2012-02-01T06:02:00.000-08:00

The 3GPP standards (36.413, the S1-AP specification in particular) lack support for inbound handovers to an LTE Femtocell (a.k.a HeNB), which is behind an HeNB Gateway. The problem comes while trying to route an S1 Handover Request from the MME to an HeNB, via the HeNB gateway.

The diagram below illustrates the scenario -

To initiate the S1 Handover procedure, the source eNB sends an "S1 Handover required" message to the MME. This message has the TAI (Tracking Area Identity) and the target eNB Id in it. Note that the target eNB ID in this case will be unknown to the MME, since that belongs to an HeNB that is "Hidden" from the MME by the HeNB gateway.
If there was no HeNB gateway hiding the target eNB, the MME would simply send an S1 Handover Request to the HeNB directly as indicated by the 'target eNB Id'. But since in this case the target eNB is an HeNB which is hidden behind the HeNB gw, the MME will have to send the S1 Handover request to the HeNB gateway instead
The MME could send the S1 Handover request to the HeNB gateway by using TAI (Which should map directly to the target HeNB gateway) OR alternatively, by using the target eNB Id and a "Subnet" concept. The subnet concept is one in which HeNB Ids contain the HeNB gateway ID also as a part of their ID, so that MME could find out the HeNB gateway ID corresponding to a particular HeNB using the high order bits and masking out the low order bits. So, there are a couple of ways for the MME to find out to which HeNB gateway the S1 Handover Request message should be routed to. So, there are a couple of ways by which the MME finds out which HeNB gateway to route the S1 Handover request to.
The problem arises when the "S1 Handover Request" reaches the HeNB gateway... This message doesn't have any target eNB ID in it!!!
So, how would the HeNB gateway route the S1 Handover Request message further down to the actual target HeNB? Unfortunately this is not handled by the 3gpp specifications as of today
The HeNB gateways will be able to route this message to the HeNB via a hack.
The HeNB gateways will have to peep inside the "Source to target transparent container" IE, to get the target cell id from inside it. This breaks layering and renders the "Transparency" of this IE ineffective.

To solve this problem, the 3gpp S1-AP specifications will need to be updated to include the target eNB Id as part of the "S1 Handover Request" message. Until then the HeNB gateways will need to do with the above workaround.

Trouble over-riding libc calloc/malloc/free etc

2008-03-20T02:29:00.000-07:00

Ever tried over-riding the libc allocator functions? I did and the journey was not as smooth as I'd anticipated it to be. My reasoning was that if I implemented the overriding functions malloc/realloc/calloc/memalign/valloc/free etc in my application, then they would get picked ahead of the libc functions by the dynamic linker, since they lie in the main application code itself and the whole program would use these versions instead of the libc functions. My thinking was almost right (The dynamic linker put my versions AHEAD of the libc versions and all dynamic symbol resolution led to my functions getting called - in fact even the libc strdup function that called malloc, ended up calling my version of malloc instead of the libc malloc itself).

However, there was an exception. One particular function _dl_tls_setup (Implemented in the libdl library) ended up calling the libc-calloc!!! This led to a crash at process shutdown time. At process shutdown, _dl_deallocate_tls tried to free up that memory, but then it called my version of free!!! However, my version of free expected a different header than what libc had put in that chunk and thus crashed the code.

Why did this happen? Why didn't the libdl library not consult the dynamic linker for resolving the calloc/free symbols? When faced with such questions, its best to study the running code using GDB. I attached GDB to the running process and did the following -

(You could refer to my GDB log file as you read the steps below)

1> dis-assembled the function _dl_tls_setup
2> Figured that the call to calloc was consulting the PLT (Procedure linkage table) entries for the libdl library
3> I then dis-assembled the PLT entries at the address mentioned in the previous step
4> That led me to the GOT (Global offset table) by the libdl library
5> Note that each shared library has its own PLT and GOT entries that has mapping information for each and every dynamic symbol that it uses that is defined by some other library
6> The GOT contained the address of the calloc function that was being referenced by _dl_tls_setup
7> I then did a 'info sharedlibraries' call in GDB which showed the memory mapping information of the entire program
8> From that I could see that the calloc address fell within the address bounds of the LIBC function
9> Doing a similar exercise (Steps 1-8) for the _dl_deallocate_tls function that was calling the 'free', I realized it was calling the free defined by my application code

Upon posting some questions to 'Linux Dynamic linker' gurus, I finally got the following answer -

"The libdl library is very special. Since it has to do some allocations before all of its dynamic linker structures are setup, it maps to libc-calloc at startup time without really going through the dynamic symbol resolution step. However, only calloc is called during the phase when the dynamic linker symbol resolution mechanisms are NOT YET set up. By the time it calls 'free' all the dynamic symbol resolution mechanisms are setup already and it ends up picking the 'free' from your application"

Aaha! So, how did I get around this issue? For now, I have gone for a simple hack - If the process is 'Shutting down' then if 'free' finds some header mismatch, simply return from the function ignoring this chunk. Well, never mind if this memory leaks, since anyways, the whole heap used by the process will be released upon process exit in any case. I'm almost certain that except during the process shutdown period (When the _dl_deallocate_tls gets called) this scenario will never occur.

Does anyone have a better idea? Or some more gyaan about this topic? It would be interesting to hear from you.

ESC India 2007

2007-10-18T03:08:00.000-07:00

The 'Embedded Systems Conference' was held for the first time in Bangalore this year. It was a great success considering that it was being held here for the first time. Industry stalwart Jack Ganssle kicked off a series of interesting technical presentations. I hosted 2 classes this year - 1> C++ Templates and STL and 2> Concurrency design patterns.

In my past experience I have observed that engineers in the embedded domain shy away from templates for many reasons. So, in my class I explored the many myths surrounding C++ templates and also talked about some real issues with templates and the workarounds for those issues. Then I went on to extol the virtues of generic programming by taking the example of the design of the STL.

In the other talk, I spoke about the various design patterns in the domain of concurrent software. Much of the material was collected from my past experience in developing highly concurrent networked software for telecom/datacomm products. I talked about the C++ free and open source toolkit called ACE that implemented many concurrency design patterns with some examples of the patterns taken from the toolkit.

Going by the amount of questions I got from the audience, both during the talk and what followed via e-mail conversations, I think both talks were highly useful to the audience. It was a very satisfying experience for me. Looking forward to ESC India 2008.

C++ Pointers and Memory Management

2007-09-01T07:33:00.000-07:00

Pointers and memory management form the most error prone area in C++. Thorough knowledge of pointer related pitfalls and traps is a valuable asset for any programmer. The fundamental issue with pointers is that there is no strong coupling between the pointer and what it points to. Pointers could be freely assigned to random memory areas, copied etc, without doing anything about the objects these point to. So, its very easy to end up with memory leaks and corruption. One way we can make pointers safer is to build a strong coupling between pointers and the objects they point to. A popular technique for doing that is called the 'Smart pointer' idiom in C++. Smart pointer based techniques such as scoped pointers, reference counting and copy on write, go a long way in making pointer related code more robust and efficient. I recently gave a talk on this very topic. You can find the slides of this talk at this slideshare link.

Static and Dynamic polymorphism in C++

2007-09-01T01:07:00.000-07:00

C++ supports polymorphism of 2 kinds - polymorphism of types (Templates) and polymorphism of behavior (Virtual methods and inheritance). Sometimes one could simulate polymorphism of types using inheritance (Deriving all types from a common base class and implementing generic algorithms to use base class pointers) and also do polymorphism of behavior using templates (Policy based design). Doing polymorphism of types using inheritance is a highly flawed approach where one loses speed, type safety and convenience. This is done only by users who are too scared to use templates. However, doing polymorphism of behavior using templates, can be a good thing sometimes. Since templates lead to faster and safer code (The abstract - concrete binding happens at compile time instead of at runtime, so faster, and more type safe), one must actively seek to simulate both forms of polymorphism (Types and Behavior) using templates. Of course, there are certain things which absolutely require inheritance and virtual methods. One example is that while designing OO frameworks, often the implementation would need to have 'Heterogeneous containers', and this is not possible using templates. So, in such cases, of course we'd have to employ inheritance and virtual functions. But in many other cases, templates could be employed to simulate both forms of polymorphism and actually leads to faster and safer code. I recently gave a small talk that compared the 2 forms of polymorphism in C++. You can find the slides at this slideshare page

C++: Finding Fibonacci sequence number in ZERO time

2007-08-08T09:14:00.000-07:00

C++ template meta-programming allows us to write many recursive programs that have ZERO runtime cost (Obviously it can't get any faster than that!!). Well, the secret here is that all the work is done at compile time, using template techniques (non-type parameters and template specialization). Check out the small program below that finds the fibonacci sequence number for an input index -

template < int N >
class Fibonacci
{

public:

enum {value = (Fibonacci<N-1>

::value + Fibonacci

<N-2>

::value)};
};

template <>
class Fibonacci<1>
{

public:

enum {value = 1};
};

template <>
class Fibonacci<0>
{

public:

enum {value = 1};
};

Now, in your programs, you just have to say - Fibonacci<20>, Fibonacci<15> etc and you shall get the answer in a jiffy (actually, in no time at all!).

This is just an example program, try out more experiments yourself to explore the power of template meta-programming. Of course, the flip side to zero runtime cost, is the larger code size, longer compile times etc...but hey! You got to give some to get some.

Packet Processor Lookup design

2007-07-21T07:49:00.000-07:00

In software based packet routers, there is a separation of data plane and control plane. While the control plane is responsible for setting up and tearing down packet data sessions using some end-to-end signaling with end devices, the data plane is responsible for routing/forwarding packets.

The control plane sets up the session data structures which has to be looked up by the data plane during packet processing. This data has to be shared between the control plane and the data plane in a thread-safe manner, while keeping the lookup times short.

I came up with a design that aims to minimize the lock contention and to shrink the search space to enable fast and safe lookups of the data. You can find the design in this document.

How I sold OO design to a team of C programmers

2007-07-18T23:39:00.000-07:00

I was recently faced with the challenge of selling OO design to a group of 'Hardcore C programmers'. Before I could begin, the room was full of - 'What does all that overhead buy us anyways', 'It sure can't be more efficient that C programming' etc. I began by giving them a list of what I thought were the top 5 benefits of OO design -

Benefits of OO design -

OO Design is more intuitive (Talk about how we deal with abstractions around us every where in the real world consisting of entities that have both behavior and attributes, give an example of how a person could be 'Abstracted' out to be 'An employee' at work, 'A spouse' at home, a 'Tennis player' at the club etc). Just as we make sense and deal with the world around us through 'Abstractions' it's natural to do so with software design
OO design supports code reuse through - a> Classes b> Inheritance c> Polymorphism and d> Composition. Talk about how OO design supports - 'Reuse of design' as opposed to just 'Reuse of code'. 'Reuse of design' is supported via frameworks that use polymorphism where high level logic 'The Brains' could be embedded in a framework and reused. An example of a 'Socket event loop' could help here. As an aside, you could also talk about 'Templates' and how they enable reuse, but mention that templates aren't part of OO design, but generic design, nevertheless supported by C++.
OO design leads to flexible software that can be easily modified or extended. This should be the "Clincher". Explain how via OO design one could have 'OLD code call NEW code' through polymorphism and how that would lead to easily extensible code. Also talk about how OO design leads to 'Loose coupling' (Enabled by the technique of Encapsulation) and 'Tight Cohesion' (Enabled by classes), thus leading to code that could be easily modified without causing 'Ripple' or 'Spaghetti' effect on the whole of the application. I gave an example of a Telecom switch software that was first designed for the PSTN (SS7 based) network and later evolved to IP based interfaces very easily, since it was designed to work with abstractions.
OO Design enables 'Fast prototyping' and an 'Iterative development'. This one should get the program managers interested quickly. Tell them, that in OO design, for the initial prototype of a product, designers need not get bogged down with finding out the best implementation detail, but can go with a simple implementation, suitable abstracted out. At a later stage, this simple implementation could be replaced with a more complex, most optimal one, very easily in a plug-n-play manner.
OO design allows for late cycle performance tuning. This one should get the 'C' coder who is gunning for you by now, thinking - Aaah! but what about the cost? Explain that software performance tuning is best done after the software is written and tested and the "Hotspots" identified. With OO design, making such late cycle changes will be easy to do, since changes are localized because of loosely coupled code.

Once, I was done with that, the amount of resistance dramatically reduced in the room. But then, some chaps were not convinced - 'Hey! But what about code bloat that C++ brings in' they said. I then went on to explain that 'Code bloat' is not caused by C++ as such, but by ignorant programmers and/or bad compilers. I said that if they used a good compiler and stuck to certain principles, they would end up with an executable size equal to their C code, but with a much more elegant body of software. The principles to avoid code bloat that I laid out were -

To avoid code bloat -

Disable 'Exception handling' and stick to C style checking of the return codes
Disable RTTI and don't use dynamic_casts, type_id etc
When using templates, use the following techniques

Move all common code that doesn't depend upon the type to a common base class and use inline template wrappers to get to this implementation. That way, you preserve type safety and automatic code generation of templates, while avoiding code bloat by using a void* based implementation internally
Use 'Template specialization' to avoid cases such as Stack and Stack generating different bodies of code, even though they are binary identical.
Do not inline all template methods. Just because the implementation needs to be in the header, doesn't mean they have to be inline. non-inline method definitions in the header file is allowed for templates
Use a toolchain that offers template optimizations - Eg: Generates only those methods that are ever user in the program, rather than all of them

Avoid using iostreams, stick to printfs instead

It was either the sheer strain of listening to all this stuff in one helluva long session, or it really made sense. But everyone seemed convinced. Try this at your workplace when someone says - OO design is all hype and doesn't make sense in embedded software products.

Token bucket implementation

2007-05-03T21:46:00.000-07:00

The 'Token bucket' algorithm is commonly used for doing rate limiting of packets in routers. The concept is real simple - A bucket is filled periodically with some tokens equal to the 'Allowed packet rate', each arriving packet consumes available tokens and passes through the bucket. If an arriving packet doesn't find any tokens available when it reaches the router, then obviously the packet rate has exceeded the allowed rate and it has to be dropped. Now, this is real simple. One alteration to this simple scheme is to add 'Burst handling' ability. This is very easily done by setting the 'Bucket size' to some value higher than the packet rate. So, if say 10000 bytes per second is the rate allowed, then if you make the bucket size as 30000, then the tokens can accumulate to 30000 tokens, when the arrival rate is lesser than 10K and these accumulated tokens allow 'Bursts' of up to 30KBps. This evens out between bursty and lean cycles.

A naive implementation of the token bucket algorithm would be to use timers to fill the buckets with tokens at regular intervals. But, if we need to do per-user rate limiting, this will not be a scalable solution. At each timer pop (Frequent pops) the timer handler will have to walk through so many buckets (1000s of them) and fill the ones that need filling at that particular pop.

A better solution will not employ timers and will scale easily to any number of token buckets and rates. I have proposed a simple solution here. Let me know if you've got any comments or ideas on this.