94.536 Fall 2002

Sample Solution to Assignment 2

1) GPRS (10 marks)

In a circuit switched connection in GSM, the ciphering is done between MS and BTS, but in GPRS the ciphering is done between MS and SGSN.

a) What do you think are possible reasons for this?

b) How does ciphering differ in GPRS from the ciphering in circuit switched case?

c) What happens if the ciphering is switched off (not used) in GPRS?

GPRS uses ciphering between MS and SGSN (4 marks)

· If ciphering/deciphering is done in BSS, the key management would be a big problem because the MS selects the cell quite "freely" and every packet may be sent via different BTS.

· GPRS can use variable radio coding without impacting ciphering.

· GPRS packets may be sent in out of sequence, LLC number is part of the frame, that RLC level does not understand.

· SGSN knows the history and can use that to make longer ciphering key input parameters. BSS can delete its context any time, thus the ciphering input could be very short. This would compromize the security or alternatively more data must be sent over the air.

· Ciphering algorithms can be changed without need to update all BSS elements. Or new radio can be used with same ciphering.

GPRS ciphering differs from GSM ciphering (3 marks)

· Uses different algorithm (output string is not generated using A5 algorithm.

· Done between MS and SGSN in LLC level (higher then in CS).

· Uses LLC blocks, not radio bursts.

· Ciphered data block is variable length.

· Has more parameters (Kc, INPUT, DIRECTION).

· Does not cipher the header (LLC header is used to derive INPUT value).

· Same channel carries packets of various mobiles, multiplexed using TLLI (identifying the MS that has send or received the packet).

· Packets are not necessarily arriving in sequence, hence the ciphering algorithm may be reset per every packet.

What happens if no ciphering is used in the radio? (3 marks)

· User data may be received by anyone. Anyone can see user's data.

· MS identity is revealed.

· Anyone may impersonate the subscriber. Every packet in GPRS is "authenticated" by using the ciphering. If no ciphering is used, anyone can send packets in the name of the user. This also means that a user needs to pay packets that are not hers.

2) MAC Protocols (20 marks)

a) The course notes contain two diagrams, explaining how multiple stations A to E compete for access to a shared channel in WaveLan (page 173) and under DCF for IEEE 802.11 (page 186). Draw similar diagrams for the same scenario under CDPD, PCF mode in IEEE 802.11, and Bluetooth. Use the following scenario:

· Five stations A, B, C, D, E plus one base station/access point/master where necessary

· All destinations are outside the cell/network/piconet

· A is transmitting to W (starting or in progress)

· A desires to transmit to X

· B desires to transmit to Y

· E desires to transmit Z

Answer (15 marks):

CDPD MAC: Up-link using DSMA/CD:

· Check for busy/idle flag (info in down-link info).

· If busy then skip RAND 60-bit slots.

· If still busy then skip 2 * RAND 60-bit slots.

· If clear then send.

· If last send resulted in collision (info in down-link info) then repeat above.

Note: The reason for station A's two transmission bursts (as opposed to one transmission burst with two FEC blocks) is due to the assumption that station A's send decisions are independent. Also, the data sent via the down-link is not shown as it is contention free and does not affect the diagram; however, it is the one that contains the busy/idle and collision info.

802.11 PCF MAC: Point Co-ordination Function - Contention Free Period

· Contention free period (CFP) is established via beacon from Access Point (AP)

· AP pools stations one at a time for data allowing transmission without contention

· Stations return data if available

· All stations differ access for maximum duration of CFP

· AP terminates CPF via CF-End message

Notes:

1. It is assumed that an ACK is required even if a station is pooled but has no data to send.

2. The pooling message from the AP may also contain data for the recipient station. If it does contain data, then the recipient station acknowledges using the returned ACK.

3. If messages were destined from and to local stations, then AP would send the data to the local station, which then returns an ACK.

BlueTooth MAC: ACL (Asynchronous Connectionless):

· Master unit controls link bandwidth

· Slaves are polled before transmitting

· Slots are wasted if no data is to be transferred

Notes:

1. The above diagram is for an ACL link and not SCO.

2. It is assumed that all data is being routed from the slaves to the master then to the INTERNET.

3. If data was to be sent from one station to another, then the slaves would have to become masters themselves in order for them to request and receive the data directly as oppose to the data being forwarded to the master and then back to the destination slave.

b) Could the Bluetooth MAC protocol have been chosen as basis for the DCF mode of the IEEE 802.11 standard? Explain your answer!

Answer (5 marks): Ony with great difficulty, and not really….

The reason for this is that the 802.11 DCF MAC is based on the following premises:

· There is no need for a single point of co-ordination, as all units are equal.

· There is no concept of a master unit.

· Stations can send data directly to each other without having to become master

· Protocol must support contention resolution.

· Stations can go to sleep during collision (saves battery life).

· Coverage area and number of stations in the net is relatively larger.

This is in contradiction to the BlueTooth MAC, which is based on the following premises:

· A master station must pool all the other slaves (stations) to coordinate the transmission.

· The protocol is designed to be contention free.

· Slaves have to become the master of the pico-net to support direct communication with another slave.

· Only one master is allowed per pico-net.

· Coverage area and number of stations in the net is relatively smaller.

3) Mobile IP (20 marks)

a) CDPD allows an end-user to run TCP/IP applications in a cellular network, roaming between cells and/or service providers. Summarize the main similarities and differences in the mobility management for MobileIP and CDPD. Will the end-user see/experience any difference?

b) MobileIP suffers from the problem of triangular routing. To overcome this disadvantage, a route optimization draft exists that allows correspondent hosts to basically keep a cache of “care-of” addresses for mobile hosts they are communicating with. Outline a route optimization proposal that does not cache addresses at the correspondent hosts. What are its advantages/disadvantages compared to the proposed route optimization protocol? (Hint: avoiding caching “care-of” addresses at the correspondent hosts does not mean that such addresses should not/can not be cached at all…)

c) MobileIP, as proposed, requires updates at the home agent every time the point-of-attachment to the wired network changes. Outline a proposal to reduce the number of these update messages. (Hint: think about organizing the foreign/home agents in a hierarchical manner).

For parts b) and c), describe both the suggested architecture and its operation. That is, describe:

· what functional entities do you add to the network

· where in the network do you add them

· what information do these entities contain/maintain

· how is this information updated as mobile hosts move

· how are these entities used in delivering data packets to mobile hosts.

Answers:

a) Both solutions use the notion of Home and Visiting Location/Agent. However, in CDPD, a node keeps its (single) IP address while roaming in a CDPD network, mobility is managed independently from the IP layer, and provides optimized location management in case a mobile node stays within a domain/subarea. In Mobile IP, a node has more than one IP address, the care-of-address changes with each visited IP network, resulting in a registration message back to the Home Agent and potentially its correspondent nodes. The user, working above the IP layer, will, to a first approximation, not see any differences.

To facilitate detailing the similarities/differences of the mobility management in MobileIP and CDPD, the following terms will be used:

Mobile Unit (MU): The M-ES in CDPD and Mobile Node (MN) in MobileIP

Router (RT): The MD-IS in CDPD and the Agent in MobileIP

Home Router (HR): The Home MD-IS in CDPD, and the Home Agent in MobileIP

Serving Router (SR): The Serving MD-IS in CDPD, and the Foreign Agent in MobileIP

Cell: In CDPD multiple cells, MDBS, belong to the same MD-IS. In MobileIP, the cell is the Home/Serving Agent itself.

1. Registration: When does an MU registers itself with an RT

· CDPD: MU investigates possible registration after a channel hop. Decision is based on relevant parameters on previous RF channel and current RF channel. Registration is only required if change resulted in cell transfers between cells belonging to the same or different RTs.

· MobileIP: MU must perform a registration whenever the RT advertisement lifetime expires or when the network pre-fix found in the RT advertisement differs from the one in the MU’s care-of address.

2. Registration: How does an MU registers itself with an RT

· CDPD: If cells are within same RT, MU sends link-layer receive ready to RT which acknowledges and updates its MU physical layer association. If cells are from different SRs, the procedure starts as before, then MU sends ESH message to new SR, new SR informs HR of new MU location, HR acknowledges, new SR confirms ack to MU, then HR flushes old SR indicating MU has moved.

· MobileIP: MU sends Registration Request to HR (relayed through SR). HR creates and modifies mobility bindings for MU with new lifetime. HR sends Registration Reply to MU (relayed through SR).

3. Discovery: How does an MU finds new internet attachment

· CDPD: The cells broadcast adjacent cells RF parameters on the beacon channel. MU picks up the RF parameters after a channel hop (or at initial connection) and performs registration if required.

· MobileIP: RTs transmit agent advertisements every second, serving as beacons. If no advertisement is received, MU’s can issue agent solicitation message. These messages are used to determine if a registration is required.

4. Tunnelling (Routing): How does an MU receives packets when it is away from its HR

· CDPD: Any packets destined for the MU is sent to the HR then forwarded to the SR then to the MU. (Triangular routing)

· MobileIP: Same as CDPD (Triangular routing), except when a route optimization scheme is used. The care-of addresses are used to route packets directly to the SR unless the MU has moved. If the MU has moved (registration expired), then the SR may forwards the packets back to the HR which then forwards them to the new SR and then to the MU.

5. Routing: How does an MU sends packets to a target mobile/stationary location

· CDPD: Any packets sent by an MU are sent to the SR and then follow the standard IP routing. They need NOT be sent to the MU’s HR. (Direct routing).

· MobileIP: Same as CDPD (Direct routing).

Conclusion: The end-user would not experience any difference in the mobility management as both CDPD and MobileIP offer seamless mobility. From the TCP/IP perspective, there is no difference in functionality.

b) High-level overview: Instead of caching care-of-addresses with each correspondent node, they could be cached with a few routers in the Internet. As these routers forward packets, they would have to check whether an entry exists for this destination IP address, and if so, forward it to the care-of-address rather than the static IP address. This reduces the number of locations that may need to be updated, but does not result necessarily in optimal routes either (depending on how close these “mobility-aware” routers are to the correspondent nodes).

In more detail: Since we can not cache the care-of address at the correspondent node, and triangular routing can only be avoided if the correspondent node somehow reaches the mobile node through its current care-of address, then the care-of address must be cached somewhere else close to the correspondent node. This can be accomplished by caching the care-of address in a gateway router (Correspondent Router) in the Correspondent Node network.

This can be illustrated using the following diagrams:

The proposal is to enhance routers to cache care-of addresses on behalf of the Correspondent (mobile or stationary) Node of the correspondent sub-net. It would work as follows:

· Home Agent is responsible for providing binding updates to any concerned Correspondent Router.

· Home Agent sends authenticated binding updates.

· Binding warning message may be sent to the Home Agent indicating that a particular Correspondent Router does not have an up-to-date care-of address.

· Mobile Node transmits binding update warnings.

· Binding acknowledgement may be requested.

· Bindings have a lifetime, after-which, they can either be purged or updated.

The following details the impact of implementing this solution:

1. Packet Transfers (Mobile to Correspondent)

The packet routing from Mobile to Correspondent is not affected by this solution.

2. Initial Packet Transfer (Correspondent to Mobile)

When a Corespondent Node sends a data packet to a Mobile Node whose care-of address is NOT cached at the Correspondent Router, the router forwards the packet to the Home Agent. The packet is tunneled to the Mobile Node. The Home Agent determines that the Correspondent Router needs a binding of the Mobile Node care-of address. The Home Agent can either directly send a Binding Update to the Correspondent Router or waits for a binding warning and then sends the binding update.

The Binding Update message contains (among other things) the following:

· The lifetime of the binding

· The Mobile Node home address

· The Mobile Node current care-of address

· Identification (used in acknowledgment)

3. Subsequent Packet Transfers (Correspondent to Mobile)

If the Correspondent Router determines that the binding will or has expired, it issues a Binding Request to the Home Agent. The Correspondent Router can sent a Binding Acknowledgement to acknowledge reception of binding message.

The Binding Request message contains (among other things) the following:

· The Mobile Node home address

· Identification (used in acknowledgment)

4. Mobile Care-Of Address Change

When the Mobile Node receives a new care-of address or receives packets that have been routed indirectly (tunneled from the Home Agent or an old Foreign Agent), it sends a Binding Warning to the Home Agent indicating that the Correspondent Router should update its bindings.

The Binding Warning message contains (among other things) the following:

· The Mobile Node home address

· The target Router address

Conclusions: The solution we have described above is exactly the same as the original triangular routing problem rout optimization solution with the exception of storing the care-of address bindings at the Correspondent Router instead of the Correspondent Node itself.

· Advantages: Same as the ones outlined in the original route optimization scheme, plus the added advantage of not having to change the correspondent node TCP/IP layer, rather, the change is pushed to the router layer. This makes the solution deployment a bit easier.

· Disadvantage: Same as the ones outlined in the original route optimization scheme, plus the added disadvantage of requiring the correspondent router to be aware of care-of addresses.

c) High-level overview: Basically all the micro-mobility protocols under discussion within the IETF address this problem. One of them is Hierarchical Mobile IP, where foreign agents are organized in a 2-level hierarchy. Regional foreign agents manage global mobility, local foreign agents provide services in each IP network (same as the foreign agent in traditional Mobile IP). The home agent (and potentially correspondent nodes) only know the regional agent’s care-of-address. As long as a mobile roams within the area covered by a regional agent, it will register new care-of-addresses with this regional agent only. In case a mobile node changes into a new region, it will update its home agent and, if necessary, its correspondent nodes. This is not unlike the difference of inter- and intra-domain mobility in CDPD.

In more detail: One proposal to reduce the number of update messages to the Home Agent is known as the Regionalized Registration proposal, where Foreign Agents are organized in a hierarchical manner. The registration message needs only be routed to the lowest common ancestor in the routing/hierarchical path. This is very similar to the method used in GSM where the hand-over message is routed up to the switching point MSC as oppose to the home MSC.

The proposal works as follows:

· Foreign Agents are organized hierarchically and maintain this hierarchy.

· Foreign Agents must describe the hierarchical lineage using Agent advertisement.

· The care-of address of the Mobile Node is stored at each Agent in the path and simply points to the next Foreign Agent address in the path

· Packets sent by Correspondent Node to the Mobile Node are tunneled from the Home Agent to the Foreign Agents according to the lineage hierarchical path.

· Packets sent by Mobile Node to Correspondent Node follow usual path (unaffected).

Now, when the Mobile Node changes Foreign Agents, then the old hierarchical lineage is compared with the new one. The Mobile Node will cause the hierarchical registration to propagate all the way to the lowest common ancestor of the two paths.

This can be illustrated using the following diagram:

When the Mobile Node moves from FA₇ to FA₈, the registration is only propagated to FA₄. When the Mobile Node moves from FA₈ to FA₉, the registration is propagated to FA₁.

Although it may seem that this proposal forces packets to flow from the Home Agents all the way to the Mobile Node through each of the Foreign Agents in the hierarchy, there is really no added overhead here. The reason being is that the hierarchy should be based on the optimal path for packet transfers from the Home Agent to the end Foreign Agent. If however, the hierarchy is not based on this optimal path, then there will be some degradation in packet delivery speed due to the additional routing points (tunneling through each Foreign Agent in the path).