Wednesday, May 5, 2010

Additional GUTI and additional P-TMSI

The release 8 specifications talk about sending additional GUTI / additional P-TMSI in attach reqeusts and Tracking Area Update (TAU) or Routing Area Update (RAU) requests. So what exactly is the purpose of them?
As mentioned in the previous post, an EPS capable UE can have itself registered both in an MME and an S4-SGSN. In that case the UE's USIM will have a valid GUTI from the MME and P-TMSI and P-TMSI signature from the SGSN.
Whenever the UE does a new attach into an E-UTRAN network (or) UTRAN/GERAN network, it has two temporary identifiers. It informs one of them as an additional identifier to the MME / SGSN. Lets consider each of the cases

Attaching to MME
The UE has a valid GUTI and a valid P-TMSI. TIN = P-TMSI
In the attach request:
  • Old GUTI = GUTI mapped from P-TMSI.
  • Additional GUTI = GUTI. P-TMSI signature is also sent in this case
The UE has a valid GUTI and a valid P-TMSI. TIN = GUTI / RAT related TMSI
In the attach request:
  • Old GUTI = GUTI at UE. No additional GUTI is sent
So what is the purpose of sending the additional GUTI in the first case above?
Since the old GUTI received by the MME is a GUTI mapped from P-TMSI, ideally it has to query the UE's identity from an S4 SGSN. But why do it if is possible for the MME to locate the subscriber's context within itself? To locate the subscriber's context it needs a GUTI that it allocated to the UE. So the additional GUTI helps (provided that additional GUTI was allocated by this MME).

Attaching to S4-SGSN
The UE has a valid GUTI and a valid P-TMSI. TIN = GUTI
In attach request:
  • Old P-TMSI = P-TMSI mapped from GUTI.
  • Additional P-TMSI = P-TMSI
The UE has a valid GUTI and a valid P-TMSI. TIN = P-TMSI or RAT related TMSI
In attach request:
  • Old P-TMSI = P-TMSI.
  • Aditional P-TMSI is also = P-TMSI if TIN = P-TMSI. The P-TMSI signature is also sent.
The usage of additional P-TMSI in the first case to look up the subscriber's context locally at SGSN instead of going to MME.
The same logic applies to TAU and RAU procedures as well.

Idle Mode Signaling Reduction

For the call flows refer Annex J in TS 23.401. Also refer this spec for an introduction to some of the terminologies used here.

What is ISR?
ISR means Idle Mode Signaling Reduction. This is a feature that allows an EPS subscriber to roam between E-UTRAN and UTRAN/GERAN coverage while in IDLE state without updating Routing Area / Tracking Area to MME / SGSN.

ISR is mandatory to be supported in an EPS capable UE but can be optionally configured in the EPC core network (S4 SGSN and MME)

Why is it needed?
The deployment of E-UTRAN network will co-exist with existing UTRAN and GERAN networks. So it is possible that within the same are a subscriber moves between E-UTRAN and UTRAN/GERAN coverage. This should not generate unnecessary signalling with the core network when the UE is in IDLE state. So what is IDLE state? It means that the UE is not having a signaling connection towards the core network (SGSN / MME). When in IDLE state,
packet transfer will not happen.

When is ISR activated?
ISR is activated ONLY on the following cases:

CASE 1
  1. Subscriber is already registered in a MME (EMM-REGISTERED state at MME)
  2. Subscriber is in ECM-IDLE state in the UE.
  3. Subscriber does a RAU into UTRAN / GERAN. RAU request carries P-TMSI mapped from GUTI. SGSN checks if ISR is activated in the config. If yes, it returns the ISR active flag in RAU accept to UE
  4. UE sees that its current TIN is GUTI and hence sets its TIN to "RAT Related TMSI"
  5. SGSN sends Update Location to HSS / HLR. HLR / HSS does not send Cancel Location to MME. A release 8 HLR / HSS keeps an EPS subscriber registered at both MME and SGSN at the same time.
CASE 2
  1. Subscriber is already attached in a SGSN
  2. Subscriber is in PMM-IDLE state in the UE.
  3. Subscriber does a TAU into E-UTRAN. TAU request carries GUTI mapped from P-TMSI. MME checks if ISR is activated in the config. If yes, it returns the ISR active flag in TAU accept to UE
  4. UE sees that its current TIN is P-TMSI and hence sets its TIN to "RAT Related TMSI"
  5. MME sends Update Location to HSS / HLR. HLR / HSS does not send Cancel Location to MME.
How does the UE know that ISR is activated and hence it need not do RAU / TAU while roaming within the TAI list / RAI in IDLE mode?
If TIN is set to "RAT Related TMSI" then UE knows that ISR is activated.

When does ISR get deactivated in UE?
ISR is deactivated in following scenarios
  1. TIN = "RAT Related TMSI" and RAU / TAU into a new RA / TA outside of the stored TAI list / RAI. Upon successful completion of the new RAU, TIN will be set to P-TMSI. Upon successful completion of new TAU, TIN will be set to GUTI.
  2. TIN = "RAT Related TMSI", periodic RAU timer expires (probably lost radio coverage in UTRAN), starts deactivate ISR timer and the deactivate ISR timer also expires. TIN will be set to GUTI
  3. TIN = "RAT Related TMSI", periodic TAU timer expires (probably lost radio coverage in E-UTRAN), starts deactivate ISR timer and the deactivate ISR timer also expires. TIN will be set to P-TMSI
Will ISR be activated if current TIN is same as the temporary identifier of the RAT to which UE is doing an update procedure?
No. For example if TIN = P-TMSI, and UE does a RAU into a new RA, the SGSN returns a new P-TMSI. The context transfer is between two RAs in the same radio technology. So even if the SGSN includes the "ISR Activated" flag in RAU accept, UE should set its TIN to P-TMSI only.

How is a downlink packet delivered to the UE when it is registered with both MME and SGSN and the UE is in IDLE state?
S-GW sees that it has an active GTP-C v2 tunnel with an S4-SGSN and MME and hence it sends downlink data indication to both of them. Both SGSN and MME initiate paging. The UE responds to one of them with a service request.
Once the radio bearer establishment is completed and service request procedure is completed, the S-GW sends a stop paging request to the other RAN from which service request was not received. For example if the UE latched onto E-UTRAN,
stop paging will be sent to SGSN.

Is ISR done when roaming from MME to a Gn/Gp SGSN?
No. ISR is applicable only between MME and S4 SGSN.


Updates:

Found the book

"SAE and the Evolved Packet Core: Driving the Mobile Broadband Revolution"

covering this topic in good detail. Preview of it is available in Google books. The ISR chapter, luckily is there for preview


Back with posts on 4G to 3G/2G packet switched mobility

I have been going through the 3GPP release 8 specifications on the aspects of E-UTRAN to UTRAN/GERAN mobility. Though there are few blogs that discuss a lot about the LTE packet core (here and here), I couldnt find a blog that discusses the scenarios with respect to E-UTRAN to UTRAN/GERAN mobility.

I will start a series of blogs on the same shortly. Few interesting scenarios that are not very clear from a quick read of the specs are

  1. Idle mode signaling reduction
  2. S4-SGSN to S4-SGSN handoff of a EPS subscriber
  3. E-UTRAN to UTRAN SRNS relocation with indirect data forwarding
The upcoming blogs will discuss about each of the above and also about GTP V2. Stay tuned.

Monday, November 2, 2009

Solving the carpentry problem by dynamic programming

Last week I was discussing about dynamic programming technique with a friend. We were discussing about the carpenter problem given here (http://parasol.tamu.edu/~amato/Courses/311/exam3.review.html - problem 4). The following is an attempt to solve the problem. Comments are welcome. Note: I am not approaching this problem through a mathematical recurrence relation. I am simply trying to solve this problem by plain common sense. However let me make an attempt to write the recurrence relation at the end (atleast let me see how much I remember my B.E classes :-))

At the outset the problem is a divide and conquer problem. The solution is
  1. Make the first cut at a point that is near the half way mark. The cost of making this cut is the length of the wood (L)
  2. Then we will have two halves with lengths L1 and L2. Apply the step 1 recursively for each of these pieces till we have made the cut at all the marked points.
Now to apply dynamic programming to this problem, we have to store the result of each portion calculated. The result shall be stored in the followig way
  • A hash table mapping the length L and list of points (a1, a2, ... an) to cut on the wood, as the key, and the cost of making such cuts as the value.
So as we recursively calculate the cost of cutting each piece of wood of length L at points (a1, a2, .. an) store the result in memory. If some other half of the wood has the same length and cutting pattern, then the result is readily available in memory. It need not be cut again.

For example, consider a wood of length 10 metres to be cut at points a1 = 1 metre, a2 = 4 metre, a3 = 6 metre and a4 = 9 metre. Here are the steps.
  • Make the first cut at a point near the half way (5 metre mark). In the above example points a2 and a3 are equidistant from centre. So lets choose a2. Now we have two woods of length 4 metre and 6 metre. After this cut the hash table will have an entry.
Value(10#1#4#6#9) = 10 ; Where 10#1#4#6#9 is the key; 10 = length of the wood, 1,4,6,9 are the points at which cut has to be made .
  • Now apply the above rule for the two wooden parts we have now. Applying it on the first one, we have
Value(4#1) = 4
  • Applying the rule on the second part, we have
Value(6#2#5) = 6 + value(4#3). Note that in the key 6#2#5, 6 = length of the wood, 2 = point of first cut (Point a3 (6 metres) - 4), 5 = point of second cut. This wood of length 6 has to be cut at point closer to its centre. That is the point at 2 metres. The cost of making this cut is 6. Now we have two parts from this cut. The first part doesnt need any more cuts. The second part needs to be cut at point 3 metres (5 - 2) from its begining. The cost for making this cut will be stored in the hash table as

Value(4#3) = 4


So value of (6#2#5) = 6 + 4 = 10.

Now the total cost = 10 + 4 + 10 = 24

In the example chosen above, we didnt have any cut patterns that repeated. So that the costs stored for the cut patterns in the memory were never used.

Now consider this example, wood of length = 10 metres, points a1 = 1 metre, a2 = 3 metres, a3 = 5 metres, a4=6 metres, a5=8 metres

In this example, once we cut the wood at a3=5 metres, we have two woods of the same cut pattern. The pattern is (5#1#3). So it is enough if we calculated the cost for one part. For the other part we can straight away take the cost from the memory.

Now to the recurrence relation,

C(L, a1, a2, ... an) = C(L) + C(L1, a1, a2, ... aL1) + C({L-L1}, {aL1+1 - aL1}, {aL1+2 - aL1}, ... {an - aL1})

where C = Cost

  • L = Length of the initial piece of wood. C(L) = L
  • a1... an = Points at which the wood has to be cut
  • L1 = Point nearest to L/2 where the first cut is made.
  • aL1 = Point of cut at length L1
  • aL1+1 = The next point after aL1 that is marked for a cut.

I will try to write a C program for the above problem and post it later. Open for comments on the way the solution is explained and if there are other better solutions for this.

Tuesday, August 11, 2009

What India needs is self discipline to contain any viral outbreak

All the impractical advises that the government gives to contain Swine flu from spreading look meaningless in India. How can you contain people from going in Trains, especially in a City like Mumbai?

Swine flu in India can be contained only through self discipline. Instead of giving impractical suggestions, government can create an awareness about the problems caused by spitting and urinating in public. In India the educated and the uneducated behave the same in this regard. What India needs is a "Stop Spitting"! campaign.

Sunday, August 9, 2009

Element Management Systems Architecture

Every telecommunication equipment vendor has to supply some level of manageability for the equipment. The management software supplied with the network element can be a propreitary software interoperating with the vendor's element management system or it can be a standards based management agent so that it can interoperate with both the vendor's element management system and other third party network management systems. In this article I will cover various aspects to consider in the architecture of a management solution for network elements, especially those based on ATCA platform.

What is element management?

Managing a network element involves the following

  1. Configuration of the network element. The configurations can be initial provisioning (which remain static as long as the network element is operational) and run time configurations (which are dynamically added / modified / deleted at run time)

  2. Collection of fault notifications from the network element.

  3. Collection of statistics and call counters from the network element.

What is an element management system?

An element management system provides some mechanism, in the form of GUI or command line utilities, to manage the network element. The GUI or command line utilities will have fields / commands to configure the device, view alarms and statistics. Typical element management architectures are

  • GUI is a web based. Network element runs an HTTP server with CGI scripts which communicate with back end APIs in the network element to configure the device and collect alarms. The advantage here is that, GUI can be made extremely interactive if AJAX is employed. Since most of the browsers now support JavaScript, portability doesn't become an issue. The disadvantage is that it doesnt use any standard protocol for management. If a customer wants to integrate a third party network management system (explained later) with the network element, it is not possible unless the third party NMS understands how to invoke the CGI scripts on the network element. Figure 1 provides a conceptual view of this architecture.

Figure 1

  • GUI is a stand alone JAVA GUI which uses SNMP PDUs to communicate with the network element. Network element runs an SNMP agent which interprets the PDUs and provides configuration and fault management facilities. The advantage of this solution is that it is standards based. Any third party network management system can be integrated with the network element. The SNMP MIB serves as the contract between the NMS and the network element. The disadvantage is that, Java based GUI require separate installation and are generally less interactive (compared to AJAX based web interface). Figure 2 provides a conceptual view of this architecture.
Figure 2

  • GUI is web based. Network element runs CGI scripts which communicate with local SNMP agent using SNMP. This approach combines the best of (1) and (2) above. Figure 3 provides a conceptual view of this architecture.
Figure 3

What is a Network Management System (NMS)?

Network management systems are standards based management systems that can control and monitor a variety of network elements within a network. A network can comprise multiple devices from multiple vendors. Hence it becomes imperative for the network management system to talk the same language to all the devices it manages. Hence a standard protocol for management becomes mandatory. SNMP is used as the standard protocol to configure various network elements.

Steps to do to make a network element provide stadards compliant management interface:

The following are the steps involved in making a device standards compliant for integration with any NMS.

  1. Define an information model for managing the device. The information model should not depend on how it is going to be managed from an EMS or NMS. That is, the model should care only about what should be managed and not how it should be managed. If some attributes / fields are added in the model just to satisfy some ease of use of use from the NMS / EMS it breaks this goal. If th model takes this path, then it becomes extremely difficult to integrate the network element's instrumentation of the model (the SNMP agent part) with the NMS (the SNMP manager part).

  2. While defining the tables in the information model, normalize the tables using database normalization techniques. This calls for expertise in database design.

  3. Capture the information model as an SNMP MIB.

  4. Implement the instrumentation for the MIB as an SNMP agent at the network element. Instrumentation means, for example if a SET request is given for a particular attribute, the agent should handle propagating that information to the appropriate module in the network element that handles that attribute.

How SNMP based network management systems function?

The function of an NMS can be split into the following

  1. Setting the configuration on a network element (uses SNMP SET). These operations should follow the ACID properties (Atomicity, Consistency, Integrity and Durability). To ensure atomicity of these operations, configuration set requests from NMS are typically blocking calls.

  2. Querying the existing configuration from a network element. This happens when a new network element is added into the NMS (or) when NMS loses connectivity with the network element for sometime and then comes back. The query can be on a single attribute or it can on the complete database. Though many NMS implement both these operations as blocking calls, it makes sense to implement bulk queries as asynchronous operations. This requires the SNMP manager module in the NMS to buffer the sent request so that it can match the responses with the request.

  3. Listening for asynchronous events from the network element. These events include alarms and statistics.

Issues with Synchronous SNMP towards network elements with multiple process architecture

Most of the NMS employ synchronous (blocking call) SNMP towards the SNMP agent for configuration query and apply. This provides a simple implementation for network elements where the entire application along with management agent (SNMP agent) are compiled as a single image and loaded. This is the case with propreitary hardware based solutions.

However, next generation network elements (PDG, AAA servers, e-PDG, MME) running on standards based ATCA chassis environment are architected with multiple UNIX processes for high availability. Such network elements will have each process catering to a separate functionality. For example in a AAA server, one process could be catering to the RADIUS / DIAMETER interface towards the PDG or other NAS, while another process could be interfacing towards the traditional HLR through an SS7 interface. This SS7 process could run on a separate blade, having an SS7 card. In such an architecture, synchronous SNMP adds to lot of delay. Consider the example given in the figure below


Figure 4


As shown in the above figure, in multi cluster HA architectures some of the configuration data need to be set in every cluster. If the SNMP agent blocks for response from all of them it adds to a significant delay. Sometimes some of the clusters may be busy in data plane or control plane processing. It may process the configuration message after some delay. If the NMS which gave the configuration request is set to timeout say, 2 seconds, it may timeout while the request is still in processing at the network element. This leads to momentary data inconsistency between the configuration data available in the NMS and the configuration processed in the hardware.

There are two ways to address this problem

  1. Make the SNMP command request and response asynchronous. This means the NMS will never block once it sends out an SNMP SET request. It may receive the SET response later. But it has to maintain a window of requests sent, so that it can match the response to the request.

  2. Use synchronous SNMP from NMS to SNMP agent. The SNMP agent should return immediately after verifying the validity of the message. It should then process the configuration request in a separate thread and once it configures the data in all the clusters it should send a success / failure notification back to the NMS as an unsolicited message (TRAP or INFORM REQUEST PDU). In this approach the NMS need not maintain any window of requests. It should commit the configured value into the database, only after it receives the success notification from the agent. The notification will carry the OID of the attribute that was configured, the value set and its status.

Conclusion:

In summary, to make a network element provide a standard management interface and be interoperable with any NMS the following need to be done:

  1. The SNMP MIB, should model only what should be managed and not how it should be managed. The model should be well normalized. Make sure that the MIB defines events for notifying success or failure of configuration requests.

  2. Make the mode of operation of SNMP agent (synchronous / asynchronous) configurable (or) a compile time option. If the agent is configured to operate in asynchronous mode, then it can use the asynchronous events to signal the success or failure of operation to the NMS.

Tuesday, August 4, 2009

Facts about STL

This is an excerpt from an advanced C++ training that I gave at my office couple of months back.

Most of our text books give a feeling that the standard template library (STL) in C++ is implemented as a shared library that is linked with your code by the C++ compiler / linker automatically. Templates by declaration dont hold any memory for its definition unless a specific instance of the template needs to be expanded by the compiler. For example a List class is defined to contain elements of a templated type, then a separate class will be created by the compiler for each of the instantiation of the class. That is, if an integer list is declared, then the tempplated List class will be expanded into List class containing integer data. If a string list is declared then the compiler will expand the templated List class into another List class containing string data.

So if the STL implementation is a dynamically linked library with your code, then how is it possible for the STL library writer to have defined an instantiation for all possible data types for all the STL classes. For example if you want to declare a list of your own data structure, you declare it as

std::list yourlist;

When this piece of code is hit by the compiler, it will create a new class called yourstruct_list by expanding the templated declaration of std::list class. But if the STL were to be a predefined shared library it is not possible to have the author of std::list class to have compiled it for the symbol yourstruct_list since, the author has no way of knowing how user defined data structures will look like. If the complete STL were a pre-compiled .so library and if you simply link it then the .so will never have the class instantiations for your data types.

So how is this problem solved by STL?

In STL only the basic functionalities which are independent of templates are compiled as libstdc++.so library. All the STL templated classes like list, vector, map etc.,. are coded in the header files which we include. For example
/usr/include/c++//vector -->includes /usr/include/c++//bits/vector.tcc. The *.tcc files have the complete definition of the templated classes. When your C++ code uses STL the following is what happens

1. You define an instantiation of a templated class (eg: vector) for your data type
2. Compiler gets the blue print of the vector class from the included vector-->/usr/include/c++//bits/vector.tcc file
3. Compiler creates an instance of the vector class for your data type as per the definition of its blue print in /usr/include/c++//bits/vector.tcc

For a better understanding of the STL classes look at the source code in /usr/include/c++//bits/*.tcc files.