Subject: RE: [mobile-ip] Analysis of Jitter in Bicasting

From: "Gary Kenward" <[email-masked]>
Date: Wed, 25 Jul 2001 15:32:29 -0400

James:

   Good description. Some comments/questions inserted.

Gary

> -----Original Message-----
> From: James Kempf [mailto:[email-masked]]
> Sent: July 25, 2001 13:32
> To: [email-masked]
> Subject: [mobile-ip] Analysis of Jitter in Bicasting
> 
> 
> Hongyi's note about jitter and bicasting spurred a bit of pondering
> about how to get a better idea of the problem, similiar to the
> bounds on buffering in draft-kempf-beth-ipv6-01.txt. The following is
> an analysis, not as mathematically based as the buffering bounds, but
> still perhaps useful. It seems to me that jitter is one technical
> problem that the proponents of bicasting need to address in order
> to have a convincing solution.

There are working solutions based upon bicast/mutlicast that have been 
used for decades. Most use base station (access point) synchronization
and duplicate removal at the base station. There are tradeoffs involved.

Indeed, if you look at CDMA as a frame based subnetwork, diversity is 
essentially the same as bicasting/mutlicasting (and you probably are
aware of the complexities involved). CDMA subnets certainly do not look 
like an IP routed network (by "CDMA subnets" I am, of course, referring
to the cellular version of CDMA).

> 
> Consider the following sequence of packets from the CN:
> 
> 	CN packet stream: x,x+1,x+2,x+3,x+4,x+5...
> 	
> where x is the sequence number when bicasting begins. 
> 
> There are two possible cases where jitter could cause duplication
> or dropped packets:
> 
> 1) A packet is delayed on the bicast link to the new AR due to network
> congestion between the source of the bicast and the new AR:
> 
> 	old L2 packet stream: x,x+1,x+2,x+3,x+4,x+5...
> 	new AR packet stream: x,x+1,...,x+2,x+3,x+4,x+5...
> 	
> In this case, the MN gets a duplicate packet when it appears on the
> new L2. For example, if the MN hands off at x+3, it gets a duplicate
> x+4 packet.
> 
> 2) A packet is delayed on the old L2 link due to deterioration in the
> radio conditions approaching handoff:
> 
> 	old L2 packet stream: x,x+1,...,x+2,x+3,x+4,x+5,...
> 	new AR packet stream: x,x+1,x+2,x+3,x+4,x+5,...
> 	
> In this case, a packet is dropped. For example, if the MN hands off
> at x+3, it will miss x+4.

This problem are not strictly a problem with bicasting. If the MN doesn't
receive x+2 on the old L2 because of poor radio channel conditions, the
same problem occurs with both re-routed and tunnelled approaches - namely,
how does the handover solution know that x+2 has been lost, and how does
it reinsert x+2?

There are methods that can be used to address this problem with bicast, that
I suspect
are simpler then the other approaches (but someone may have a better
approach).
It involves purposely off-setting the stream at new AR from old L2. The
offset
should be equal to the number of possible packet losses (hopefully, no more
then 1 packet). This introduces duplicates as a result (possibly with every
handover), but a duplicate is easier to recover from then a loss,
particularly
when the duplicates are received within one or two packet durations.

> 
> In the case of 1, the probability of a duplicate packet has nothing
> whatsoever to do with the radio link. It is purely a matter of traffic
> engineering in the wired network. So the probability of a duplicate
> packet can be reduced by properly engineering the wired network. In
> addition, the probability is likely to increase with the topological
> distance between the new AR and the source of the bicast (simply
> because, the more network a packet has to traverse, the more likely
> it is that a congestion event may cause delay). Since engineering
> of the wired network is largely under the network operator's control,
> this problem is fairly straightforward to solve, though it may
> require measures such as over provisioning.

Well, it takes more then over provisioning. You need to ensure
the same number of hops between the bicasting source (the traffic
bifurcation
point if you will), and you also need to provide some guaranteed bounds on
the delay at each hop after the bicasting source. *if* you want to ensure no
duplicates
at all at the receiver. This may seem like a definition of EF, but
consider that the constraint is much more severe then that of EF. With
EF the bound is on inter-packet delay and delay jitter for a single stream.
With bicasting, the bound is on the arrival delay of two copies of the
same packet that traverse different paths through N hops. The maximum
delay difference, I believe, is one packet duration, T. Thus, the delay 
difference bound at each hop must roughly be T/N (the relationship is
not linear, but this gives a rough approximation). If the source of
the delay is from queuing, then this would imply that there can be
no other traffic following the same path. E.g. if a bicasted packet
arrives at an AR and is queued behind a packet that is being served
(note: served, not queued), from a different packet stream, then
it receives a delay of roughly T/2.

One obvious approach to this delay problem is to have only one hop
after the bicasting source - the AR itself. This would seem to 
impose serious constraints on the network engineering, and I believe
would pose serious handover problems between bicasting sources.

> 
> The same is not true of 2. Radio conditions at handover are 
> not entirely
> controllable through network engineering. They change based on dynamic
> factors such as what types of objects (like big trucks) sit 
> between the MN and 
> the radio AP, in addition to more static factors. So a more 
> likely source
> of problems due to jitter is a dropped packet due to delay of a packet
> on the radio link.
> 
> Before drilling down on this problem, I'd like to consider 
> two different
> kinds of bicasting that have been proposed, since I think they have
> very different properties with regard to a solution. The differences
> may not be clear in people's minds, though there have been illusions
> to them in the email. They are:
> 
> 	1) Simultaneous bindings, in which an agent 
> (HA/RegReg/MAP, etc.)
> 	back in the network is bicasting simultaneously to the old AR
> 	and new AR (reference: 
> draft-elmalki-mobileip-bicasting-v6-00.txt).
> 	
> 	2) Edge tunnels, in which the old AR is bicasting to the new AR
> 	(references: draft-kempf-beth-ipv6-01.txt, 
> 	 draft-ietf-mobileip-lowlatency-handoffs-ipv4-01.txt,  
> and implied
> 	 in draft-ietf-mobileip-fast-mipv6-01.txt if the old CoA is
> 	 used on the new AR).
> 	 
> In 1), signalling from the MN establishes simultaneous bindings for
> old and new CoA. In 2), the routers (or FAs for MIPv4) bicast without
> the MN becoming involved.
> 
> The delay of a packet on the radio link usually happens because radio
> conditions deteriorate. Bit error rates around handover can escalate
> to 10**-3 or 10**-2, something unheard of on wired networks. 
> At 10**-3,
> one could expect a bit error on every Ethernet-sized (1500 byte)
> packet. To counter this, most radio protocols have relatively small
> L2 frame sizes, and perform retransmit on a frame basis. So a bit
> error in a single radio frame doesn't require the entire packet to
> drop.
> 
> The net effect of increased bit error rate and retransmit is that
> the MN begins to see a decrease in the IP data rate as radio 
> conditions
> become worse during handover. If the rate near the center of the cell
> is 9.6 kbps, maybe it drops to 5 kbps as handover approaches. Of
> course, if the MN doesn't handover, it drops to 0 kbps and 
> the connection
> is severed.
> 
> If we assume that the wired network provides a data rate 
> considerably higher
> (like 2-3 orders of magnitude) than the radio network, one way to
> solve this problem is to clock the bicast data rate to the radio link
> rate. So if the radio link slows down to 5 kbps, the bicast link going
> out from the source does too. If this is done, the bicast source can
> delay sending a packet out over the bicast stream until it is finished
> sending on the radio link. This assures that the packet does not
> get to the new AR (where it will be dropped if the MN hasn't
> arrived yet) before it gets to the MN. Or, it can even *not* 
> send the packet 
> since the bicast source knows the MN has go it, and only send 
> packets when
> the MN actually disappears due to L2 handover. 
> 
> In any event, with the simultaneous binding approach, the 
> HA/RegReg/MAP
> agent is too far away from the radio link to be able to fine tune
> bicasting in this way without additional help. One could 
> imagine further
> protocol support for getting this information to the agent, but since
> there would be a delay due to  the transport time, it 
> probably wouldn't
> help, as there could be hysteresis as the agent tried to catch up
> to the varying quality of the radio link.
> 
> With the edge tunnel approach, since the tunnel runs from the old
> AR, the AR is in a position to obtain timely and accurate information
> on the dynamically changing data rate over the radio link. Examples
> here are the PDSN and GGSN for cdma2000 and wCDMA (resp.). For
> WLAN protocols, the AR might not be directly connected to the radio
> link, the radio link may rather be available via a radio AP
> that acts as a transparent bridge. These cases are harder to 
> solve, since they 
> have the same problem as the simultaneous bindings approach, 
> namely the 
> information on radio link data rate is not available at the 
> AR. Again, protocol
> support for transferring the L2 information from the AP to 
> the AR might
> help, and the delay is likely to be less because the AP is on link
> with the AR, but there is nevertheless the potential. 
> 
> So, in sum, the solution to jitter in bicasting is to tightly couple
> bicasting with the performance of the radio link, so that the bicast
> stream accurately reflects what the MN has received. This is not
> as strong a coupling as the synchronization used in CDMA, but it
> should work to reduce or eliminate packet drop for the most 
> common case.
> In addition, the wired network must be properly provisioned to
> avoid congestion and thus duplicate packets on the bicast link.
> 
> Comments? Did I miss anything?

You have covered a lot. I  think the bottom line is that if you
want to use bicasting, and avoid all duplicates at the receiver, you
have to synchronize the traffic flows very carefully, which contradicts
the principle of a hop-by-hop IP forwarding network. 

The other idea is to consider the impact of duplicates, and look for
reasonable comprimise between delay/loss compensation and duplicate
removal over one to two packet durations.

Cheers,
Gary

---

From: Michael Thomas <[email-masked]>
Date: Thu, 26 Jul 2001 10:34:12 -0700 (PDT)

> it receives a delay of roughly T/2.

I am very, very confused by all of this. Bicasting
at the IP layer would merely result in duplicates
which the transport/application layer would need
to deal with. In fact, it already needs to deal
with dups because IP packets are fairly regularly
duplicated anyway. While it may require some
specific tweaks to TCP (which I assume EIFEL
attempts to provide), I see no reason why one
would want to shield the receiver from this in the
network, nor do I see any reason why it requires a
difference in the per hop behavior in the tunneled
traffic to AR new, or any consideration of number
of hops, etc. The beauty of the end to end principal is
that the receiver just adapts *regardless* of
where the source of the jitter/loss/duplication/etc
came from. Trying to deal with jitter hop-by-hop is akin
to the general X.25 approach to transport which
is if nothing else against the general IP
philosphy of end to end transport. More
pragmatically, dealing with jitter in the network
will almost certainly yield a worse end to end
delay as a single jitter buffer on the receiver.

	 Mike