|
|
|
2. Simulation Results In this section we analyze the handoff performance of Cellular IP access net-works. We quantify the performance penalty associated with the Cellular IP handoff scheme which trades performance (e.g., packet loss and delay) for simplicity. Furthermore, we investigate the "cost" of mobility management. for routing and paging in Cellular IP access networks. Determining the mobility management cost is important because different cellular system installations (e.g., pico-cellular and macro-cellular access networks) will operate under different mobility conditions. The Cellular IP protocol is implemented as extensions to the ns simulator [10] which is widely used by the networking community to analyze IP networks. The Cellular IP simulation environment used for the reported results is shown in Figure 1; note that the simulator supports Cellular IP access networks of arbitrary topology. The assumptions and limitations of the Cellular IP ns simulation environment are as follows. First, an "ideal wireless interface" is used; that is, packets transmitted over the wireless interface encounter no delay, bit error or loss and congestion over the air interface is not modeled. Next, the beacon messages transmitted by a Cellular IP gateway are not modeled. The network is configured when the simulation session is initiated and the topology remains constant for the duration of the simulation. Finally, wireless cells are assumed to overlap and mobile hosts move from one cell to another in zero time. This does not limit the ns simulator’s ability to study packet loss during handoff because such packet loss is mainly a product of misrouted packets. The design of a fast and efficient handoff algorithm is central to the performance of a cellular access network especially in the case of networks that are comprised of small wireless cells with fast moving mobile hosts. One of the de-sign goals of Cellular IP is to operate efficiently at very high handoff frequencies. In accordance with this design goal, the Cellular IP handoff algorithm avoids explicit signaling messages (used for example in cellular telephony and Mobile IP systems) and buffering or forwarding of packets [5] [6]. As a result Cellular IP packets may be lost during handoffs. In such cases we assume that packet loss is dealt with by higher layer protocols (e.g., TCP). In this section we analyze the performance of Cellular IP handoff to determine the performance penalty we pay for our simple approach to host mobility. 2.2.1 Delay The impact of handoff on ongoing sessions is commonly characterized by the handoff delay. Handoff delay is usually defined as the time taken to resume. normal traffic flow after a mobile host performs handoff. Though this does not fully determine the performance seen by applications, it is a good indication of the handoff performance. In [11] handoff delay is decomposed as rendezvous and protocol time. Rendezvous time refers to the time taken for a mobile host to attach to a new base station after it leaves the old base station. This time is related to wireless link characteristics, particularly to the inter-arrival time of beacons transmitted by base stations. Protocol time refers to the time taken to restore traffic flows/sessions once a mobile host has received a beacon from the new base station. In the following analysis we assume that the rendezvous time is small and handoff performance is determined by the protocol time. Rather than adopting the notations proposed in [11], we define the handoff delay as the time it takes a mobile host to receive the first packet through the new base station after it moved from the old to the new base station, which, as discussed earlier, we assume to take zero time. In Cellular IP, handoff delay and packet loss are consequences of the time it takes for the distributed routing state to follow host mobility. As described in Section 2, immediately after handoff, mobile hosts transmit a route-update packet to reduce this time to a minimum. The route-update packet travels from the new base station to the gateway configuring the new soft-state downlink route toward the mobile host’s new point of attachment. The old and new down-link routes both originate at the gateway but while the former routes packets to the old base station, the latter leads to the base station the host has just moved to. 2.2.2 Packet Loss In addition to handoff delay, application level service
quality is also related to packet loss during handoff. To
determine handoff packet loss, let us assume that a
periodic stream of packets is being transmitted from the Internet to a mobile
host. Before a handoff is initiated packets are routed along the old route. In
the following calculation, we will assume that the cross-over
node knows in advance which of the stream’s packets will be the last one to
reach the mobile host at the old location. Let us assume
that the cross-over node marks this packet. Upon receiving
the marked packet, the mobile host performs a handoff and
immediately transmits a route-update packet through the new base station.
Downlink packets routed by the cross-over node after the marked
packet but before the arrival of the route-update packet
are routed to the old base station and are lost. This time
interval is equal to the sum of the time taken for the marked
packet to propagate from the cross-over node to the mobile host and the time
taken for the route-update packet to reach the cross-over node. The loss of
packets at handoff is related to the "handoff loop
time" which is defined as the transmission time from
the cross-over node to the mobile host’s old location plus
the transmission time from the mobile host’s new location to the cross-over
node. Specifically, the number of lost packets at handoff nloss
is equal to the number of packets
arriving at the cross-over node during the handoff loop time
TL, that is nloss
= wTL (1) where
w handoff can equally be
calculated using the handoff delay. In what follows we do
not differentiate between these two values. Handoff packet
loss for a Constant Bit Rate (CBR) source using our simulation environment
is plotted in Figure 2. The curve represents the average number
of packets lost during handoff against down link packet inter-arrival time
in seconds. The three curves correspond to 0.2 seconds, respectively (twice the
link delay shown in Figure 2). The simulation results
closely match the calculations presented above. These results are
achieved with neither mobile hosts nor base stations having special states
associated with handoff. In exchange for this simplicity,
however, handoff performance is dependent upon the traffic
conditions. In a highly loaded network the handoff delay
and packet loss will be higher. Real time Internet
applications (e.g., voice over IP) are sensitive to packet delay
and cannot typically tolerate the delay associated with the retransmission
of lost packets. For these applications, the number of lost
packets characterizes handoff performance. Other
applications, however, use end-to-end flow control to
respond to network and traffic conditions and retransmit packets and/or reduce
transmission rate if errors occur. In what follows, we focus on TCP performance
in the presence of handoff. TCP represents the most typical
traffic type over today’s Internet which carries World
Wide Web, file transfer, remote
Figure 2: Packet Loss vs. CBR Packet Inter Arrival Time login and other applications. Investigating TCP performance is important because its flow control has been shown to operate sub-optimally in wireless environments. 2.2.3 TCP Behavior We will first use simulation to look at the behavior of a TCP session during handoff. In the first example TCP is used to download data to a mobile host. The TCP packet size is 1000 bytes and a mobile user has up to 5 Mbps downlink bandwidth, that is, the downlink packet rate w is 625 packets/sec. Packet transmission time between nodes in the simulated configuration is 2 ms, resulting in a handoff delay of 4 ms. Figure 3 shows the sequence numbers of downlink data packets and up-link acknowledgments observed at the gateway during handoff; note that TCP Tahoe flow control is operational throughout. Handoff is initiated by the mo-bile host at 4 seconds into the simulation. In accordance with Equation 1 three consecutive packets get lost as indicated by the three consecutive missing acknowledgments. After the handoff delay packets continue to arrive at the mo-bile host. These packets are, however, out of sequence and cause the receiver to generate duplicate acknowledgments as indicated by the horizontal line of
Figure 3: TCP Sequence Numbers at Handoff (Downlink Case) acknowledgment sequence numbers. The duplicate acknowledgments inform the TCP transmitter about the losses and cause it to retransmit the lost packets. The first retransmitted packet arrives approximately 20 ms after the handoff (see Figure 3). Using Tahoe flow control, the transmitter remains silent until this packet is acknowledged and increases its transmission window size as further acknowledgments arrive. The full TCP rate is regained at 4.07 sec into the simulation as shown in Figure 3. The figure represents TCP sequence numbers at the client side transmitter for both packets and acknowledgements against time in seconds. Cellular IP handoff is interpreted by a transmitter in the wired IP network as congestion which causes it to reduce its transmission rate. Using Tahoe flow control the handoff triggers slow-start which increases the performance impact of handoff packet loss. From the simulation results we observe that normal operation is resumed approximately 70 ms after handoff is initiated as shown in Figure 3. In the next experiment TCP is used to carry data from the mobile host. In this case handoff packet loss affects acknowledgments instead of data packets. Figure 4 shows simulation results for a configuration that is identical to the previous one. Before handoff is initiated the TCP sender at the mobile host uses its maximum window size of 20 packets which is reflected in the difference between data packet and acknowledgment sequence numbers. At
Figure 4: TCP Sequence Numbers during Handoff for the Uplink Case 4 sec (simulated time) the mobile host performs a handoff and stops receiving acknowledgments for a period of approximately 4 ms, which represents the handoff delay. During the handoff delay the sender does not transmit any packets since its window size is used up and it needs incoming acknowledgments to advance its transmission window. In the next experiment (as shown in Figure 4) handoff is initiated when the TCP session is in a stabilized phase and acknowledgments keep arriving at the mobile host in a paced and continuous manner. After the handoff de-lay, acknowledgments are routed to the mobile host’s new location. Due to the cumulative nature of TCP acknowledgments, the first acknowledgment that arrives at the mobile host after handoff informs the sender that all its transmitted packets have arrived at the receiver (up to the sequence number shown in the acknowledgment). This causes the transmitter to advance its transmission window and continue transmitting at the maximum available data rate. In the simulation example this rate is slightly higher than the rate dictated by TCP flow control which represents the long term average capacity. This results in a curve of data packet sequence numbers that is somewhat steeper during hand-off. As observed in Figure 4, normal operation is resumed quickly with the result that handoff has little impact on the active data session. We observe that the behavior is different if handoff occurs when a TCP session is in its initial slow start phase and acknowledgments are not regularly. arriving at the mobile host. In this case the new downlink route is established after the handoff delay but no acknowledgments arrive to the sender. If at this point the sender has used up all its transmission window and is waiting for acknowledgments then TCP can suffer a delay equal to the sender’s retransmission timer. Mechanisms to avoid this problem are for further study. 2.3.1 Route Maintenance Overhead The network operator will typically set the route-timeout to
be a small multiple of the route-update time. This ensures
that the mobile host’s routing cache mappings remain
valid even if a few route-update packets are lost. Let Tru
denote the route-update time and aTru
the
route-timeout where is a small integer. To choose an
optimal value for Tru, the following
trade-off should time,
packets addressed to this host continue to be delivered to the old base station
increasing the network load and reducing network performance. A
small value of Tru
should
be used to minimize this condition. On the other hand, an active
host that has no data to send must transmit route-update packets at a rate
of 1/Tru. This load
increases with decreasing Tru. Let
the cost of carrying a packet to or from the mobile host
be defined as the size of the packet in bits. This model
neglects differences in uplink and downlink cost due to different traffic
conditions but is sufficient to characterize the Tru
trade-off.
Consider a mobile host that is receiving data at a
constant rate r p denote
the fraction of the time when it is not sending packets and is forced
to transmit route-update packets instead. (We note that in some typical IP
applications downlink traffic is considerably higher than uplink traffic. This,
however, does not necessarily cause p to
be high if acknowledgments are transmitted over the uplink.) The cost of
transmitting route-update packets during rupT/Tru
where Rru is the size of a route-update
packet in bits. During this time the mobile performs T/TH handoffs
where TH (dwell time) is
the mean time spent in a cell. After each handoff, the old route remains active
for at most aTru, the
exact value depending on when it was last updated before
handoff. Hence the mean cost of sending packets along the old route after
handoff is rTru(a-1/2)
and the total cost of misrouted packets during time
T is rTTru(a-1/2)
/TH The optimal route-update time
Figure 5: Location Management Cost vs. Tru (Dotted Lines Represent Simulation Measurements)
This theoretical result is plotted in Figure 5. The mobile host performs handoffs every 30 seconds while it is receiving data at a rate of 128 kbps. The size of route-update packets is 102 bytes, is 3 and p associated with the mobility of an active host and is calculated as
This cost is not proportional to the migration frequency but to its square root. In keeping with the original design goals, this shows Cellular IP’s efficiency in supporting highly mobile hosts. Note that the mobility cost increases with increasing user data rate. This property applies to most mobility schemes (e.g., when data must be forwarded from one base station to another after handoff) but is more apparent in Cellular IP. This is related to the soft-state nature of Cellular IP. Since there is no explicit signaling during handoff, which makes handoff transparent to the base stations, the base station is unaware that mobile hosts move into or out of its cell. Transmitting data to mobile hosts that have left the cell adds to the cost of mobility. 2.3.2 Paging Overhead The paging-update time Tpu is
subject to a similar trade-off as Tru.
A selected value that is too small will result in very
frequent paging-update packets being sent by idle mobile
hosts. On the other hand, considering that the paging-timeout is
a small multiple of the paging-update time, increasing Tpu
will result in an increase in the
number of cells that an idle mobile host is paged in. Paging
is initiated when a new data session starts by a downlink packet, for instance
a TCP connection is initiated to the
mobile host. Let lP denote the
arrival rate of such sessions and RP the
mean amount of traffic (bits) sent in paging packets. The
paging packets are delivered to all the cells to which the mobile
host has valid paging cache mappings. Let us first assume that all base stations
have paging caches and that the probability of immediately revisiting a
cell is negligible. Paging occurs in the ‘primary’ cell that the target
mobile host resides in plus any other ‘secondary’
cells where the mobile host has valid paging cache
mappings. Secondary cells represent cells that the mobile host has
recently visited and that have valid paging cache for the target mobile host.
Paging secondary cells is a waste of transmission resources and
reflects the cost of our paging scheme. The mean number of
secondary cells paged is (b
-1/2)Tpu/TH
where b
is the ratio between the paging-timeout and the paging-update time. The optimal
paging-update value is the one that minimizes the sum of paging-update traffic and
where Rpu is the size of paging-update packets in bits. Using this optimal paging-update time, the total cost Ci associated with the mobility of an idle host is
These results take a similar form to those obtained for the route-update time. However, the downlink data rate r lP RP which is the rate at which data arrives at the mobile host in paging packets. This rate depends largely on the application but will be in most cases orders of magnitude lower than r also accounts for the fact that the cost Ci associated with the mobility of idle hosts is significantly lower than the mobility cost of active users which is the basis of passive connectivity. 2.4 Conclusion In this paper we have presented an analysis of the Cellular IP protocol. Cellular IP represents a new approach to IP host mobility that incorporates a number of important cellular system features but remains firmly based on IP design principles. A fundamental design objective of Cellular IP is implementational and functional simplicity. To reduce complexity, we omitted explicit location registrations and replaced them by implicit inband signaling. As a result, nodes in a Cellular IP access network need not be aware of the network topology or of the mobility of hosts in the service area. This design choice deliberately trades off performance for simplicity. As a result packets may be lost at handoff rather than explicitly buffered and redirected to mobile hosts as they move. Our analysis has focused on the performance of the Cellular IP hard handoff algorithm and on the network traffic overhead imposed by mobility management. We have found that a simple approach can offer fairly good service quality. We have presented an analytical and empirical study of protocol parameters that can be set to configure a Cellular IP access network to match local mobility and traffic characteristics. Future work is addressing new mechanisms to pro-vide quality of service support while maintaining the same simple lightweight protocol approach to host mobility and wireless access to the Internet. References [1] Charles Perkins, editor, "IP Mobility Support," Internet RFC 2002, October 1996. [2] Pravin Bhagwat, Charles Perkins, Satish Tripathi, "Network Layer Mobility: an Architecture and Survey," IEEE Personal Communications Magazine, Vol. 3, No. 3, pp. 54-64, June 1996. [3] M. Mouly, M-B. Pautet, "The GSM System for Mobile Communications," pub-lished by the authors, ISBN 2-9507190-0-7, 1992. [4] Charles Perkins, "Mobile-IP Local Registration with Hierarchical Foreign Agents," Internet Draft, draft-perkins-mobileip-hierfa-00.txt, Work in Progress, February 1996. [5] H. Balakrishnan, S. Seshan, R. Katz, "Improving Reliable Transport and Hand-off Performance in Cellular Wireless Networks," ACM Wireless Networks 1(4), December 1995. [6] John Ioannidis, Dan Duchamp, Gerald Q. Maguire Jr., "IP-Based Protocols for Mobile Internetworking," Proc. ACM Sigcomm’91, pp. 234-245, September 1991. [7] David B. Johnson, Charles Perkins, "Route Optimization in Mobile IP," Internet Draft, draft-ietf-mobileip-optim-07.txt, November 1998, Work in Progress. [8] Andras G. Valko, "Cellular IP: A New Approach to Internet Host Mobility," ACM Computer Communication Review, January 1999. [9] A. Valko, A. Campbell, J. Gomez, "Cellular IP," Internet Draft, draft-valko-cellularip-00.txt, Work in Progress, November 1998. [10] "Network Simulator - ns (version 2)", ns home page, http://www-mash.cs.berkeley.edu/ns/ns.html. [11] Ramon C´ aceres, Venkata N. Padmanabhan, "Fast and Scalable Handoffs for Wireless Internetworks," in Proc. ACM Mobicom, 1996. |
|
Copyright© Comet Group in Columbia
University 1999 |
