Transcript PPT

Video Splitting techniques for Inverse
Multiplexing over GPRS channels
Roll No: 2006-03-0031
M. Mudassar Nazar
Roadmap







2
Introduction
Video Splitting Techniques
Work accomplished
Challenges Faced
Future work
References
Questions
Introduction
Major Hurdle—Multimedia Apps.

Scarcity of Bandwidth
–

Situation in our country
–
–
–
3
Major hurdle in deployment of multimedia
applications
In our country, dialup is a major method to access
the internet
DSL is limited to specific areas
In rural area’s even dial up access is limited
Introduction— cont.
Telecom Revolution
4
Introduction— cont.
Problem Formulation
5

What can we do?

Idea is simple?
Introduction— cont.
Problem Formulation

What can we do?

Idea is simple?

Aggregate Bandwidth
–
6
also known as Inverse
Multiplexing
Introduction– cont.
Motivation

Telemedicine

Video lecturing
Video on demand

7
Introduction– cont.
Inverse Multiplexing
S
Input
i.e. video
8
A
M data
packets
B
N network
channels
M data
packets
Introduction– cont.
Inverse Multiplexing
S
Input
i.e. video
A
M data
packets
- Link Layer ML PPP[1]
- Transport Layer[2]
9
B
N network
channels
M data
packets
Introduction– cont.
Scheduling—is at core
A
M data
packets
Scheduling
10
B
N network
channels
M data
packets
Introduction– cont.
Scheduling—is at core
A
M data
packets
Scheduling
11
b
b
b
b
B
N network
channels
M data
packets
Introduction– cont.
Scheduling—is at core
A
M data
packets
Scheduling
12
b1
b2
b3
b4
N network
channels
B
M data
packets
Introduction– cont.
Inverse Multiplexing
S
Input
i.e. video
A
N network
channels
M data
packets
Scheduler
13
B
M data
packets
Introduction– cont.
Inverse Multiplexing
S
Input
i.e. video
14
A
N network
channels
M data
packets
Splitting
B
Scheduler
M data
packets
Video Splitting Techniques

MobiStream [4] explains four major video
splitting categories:
–
–
–
–
15
Partitioning of video frames into slices
Multiple Description Coding
Slice Structured Coding
Inter-frame/ intra-frame slice interleaving
Video Splitting Techniques
Block Interleaving

Different Block interleaving techniques are
proposed in [5] :
–
–
–
16
Triangular
Quadrant
Coefficient
Video Splitting Techniques
Triangular Interleaving



17
In this, a DCT block is divided into two groups. Lower
triangular region and the upper triangular region.
Then these groups from different blocks are
interleaved in such a way that if a lower portion of
the triangle is lost, then there is high probability that
higher portion is not lost and vice versa.
DC coefficients are grouped in a separate block and
can be transmitted on a reliable channel.
Video Splitting Techniques
Quadrant Interleaving



18
In this, a DCT block 8x8 is divided into four
groups instead of two namely, L, HD, VD,
and HI.
A macro block of 16x16 is made from above
blocks and number in a clock wise manner
from 0 to 3.
Select Li (i= 0,1,2,3) and HDi+1, HIi+2 and
UDi+3 from others to form new interleaved
8x8 blocks within the16x16 block.
Video Splitting Techniques
Coefficient Interleaving




19
This scheme treats each DCT coefficient as a group
Main idea is to shuffle the coefficients.
Lets say if we have 63 groups in a block. Then we
take first group from block 1, second from block 2 to
interleave.
This scheme works on the coefficient level. Although
this produces high degree of interleaving but this
also compromises on compression efficiency.
Work Accomplished


Experiments to check the behavior of real GPRS
channels (Warid)
Built an application layer that can:
–
–
–
Identify new GPRS devices and make connection with them
using Bluetooth
Maintains a list of available GPRS devices for scheduling
purpose.
Provide an interface to outer world to schedule packets.
Note: RR Scheduling being used in the layer.
20
Work Accomplished
Experiments
Different experiments for GPRS have been
performed in order measure:
 RTT
–

Using ping
Jitter
ji = │ti-ti-1- α│
Where
ji is the jitter for ith observation
ti is the receiver time stamp for ith packet
21
Work Accomplished
Experiments
ti-1 is the receiver time stamp for (i-1)th packet
and
α is the time spacing for generation of two
consecutive packets at sender.

and bandwidth estimation
–
22
Using pathload (a bandwidth measurement
tool)[3]
Work Accomplished
Experiments—RTT Variation
Figure 1
2500
RTT(ms)
2000
1500
1000
500
0
1
75
149 223 297 371 445 519 593 667 741 815 889 963
Time
23
Work Accomplished
Experiments—Jitter (α=1s)
Figure 2
Jitter(ms)
2000
1500
1000
500
0
0
200
400
600
Time
24
800
1000
Work Accomplished
Experiments—Jitter (α=2s)
Figure 3
1600
1400
Jitter(ms)
1200
1000
800
600
400
200
0
0
200
400
600
Time
25
800
1000
1200
Work Accomplished
Experiments—statistics
26
Experiments Mean
RTT
588
Jitter(1s)
333
Dev. Max.
353 2367
289 1830
Min.
204
0
Loss
5%
2.6%
Jitter(2s)
208
0
2.2%
149
1390
Work Accomplished
Experiments—Bandwidth

Using pathload[3], we have measured the
available bandwidth around 5 times. It was
ranging from 2kbps to 4kbps depending on
the time it was measured.
–
27
Horde [2] measurement shows: that it was around
19kbps during day and 25kbps at night—validate
it (a real point to be noted)
Work Accomplished
Experiments—concluding remarks



High variability is giving us a clue that whatever is
the architecture of inverse multiplexer, we need a
sophisticated scheduling scheme for the best
performance. And we need video splitting technique
that is resilient to losses.
Different levels of jitter is experienced for different
values of α.
The bandwidth estimation gap between our and
Horde is pointing us towards:
–
–
28
Either our measurement methodology has problems or
We need to work on the feasibility of Inverse Multiplexing in
Pakistan.
Work Accomplished
Scheduling layer

This layer provides:
–
–
–
29
Provide an interface to outer world in order to
schedule packets
Identify new GPRS devices and make connection
with them using Bluetooth
Maintains a list of available GPRS devices for
scheduling purpose.
Work Accomplished
Scheduling layer—Main Components

Device Discoverer
Channel Manager
Scheduler

Shell Scripts


–
30
Used by the main components
Work Accomplished
Scheduling layer—Device Discoverer

Its responsibilities are
–
–
–
–
31
To search new devices after periodic intervals
To make connection with them
To create a new routing table and rule for this
particular interface
And adding them to devices list
Work Accomplished
Scheduling layer—Channel Manager


Its responsibility is synchronize the device list
to actual available channels
It handles:
–
–
32
Removal of devices from the device list that
disappeared
Addition of some missing Blue channels
Work Accomplished
Scheduling layer—Scheduler
Its responsibility is
 to queue the data transfer requests from
above layer
 and schedule them to the available blue
channels in a round robin fashion.
33
Work Accomplished
Scheduling layer—Scripts

These scripts are used by other components
to perform various tasks:
–
makeConnection.sh


–
getLastInterfaceDetails.sh

34
To make connection with the device just discovered.
This is used by the Device Discoverer
This scripts also releases the unused rfcomm devices
To get the IP and other parameters of the current device
we have made connection with. This is also used by the
Device Discoverer
Work Accomplished
Scheduling layer—Scripts cont.
–
getPPPInterfaces.sh

–
init_alternate_route.sh

–
This is also used by both, the Device Discoverer and
Channel Manager, to create a separate routing table and
rule for a blue channel.
init_route.sh

35
This is used by the Channel Manager in order get all
available blue channels at this particular time.
This is called at start of the program in order to initialize
routing table for Ethernet interface (if any)
Challenges Faced
Following are some the challenges faced during the
implementation of above layer:
 How to make a GPRS connection using API. API selection,
understanding it and using it for our purpose.
–

How to use multiple default routes. As we have different links to
internet.
–
36
I have used avetana Bluetooth stack and pppd to make a
connection over rfcomm.
This is accomplished using ip utility in Linux. The idea is simple
that we create a separate routing table for each interface and then
make a rule to use that table if data originates from that particular
interface.
Future Work
Following areas can be explored:
 Experimenting with different video splitting
techniques described above using the simple
scheduling layer implemented above.
 Defining a better scheduling scheme that
maximizes the performance of the inverse
multiplexer. This include the rate control on
different links to reduce packet loss
37
References




38
[1] Alex C. Snoeren, “Adaptive Inverse Multiplexing for
wide-area wireless networks”, Proceedings of IEEE
GlobeCom’99
[2] Qureshi A. and Guttag J., “Horde: Separating Network
Striping Policy from Mechanism”, ACM MOBISYS’05
[3] Manish Jain, Constantinos Dovrolis, “Pathload: A
Measurement Tool for End-to-End Available Bandwidth”,
in Proceedings of 3rd Passive and Active Measurements
Workshop, Fort Collins, March 2002.
[4] Rajiv Chakravorty, Suman Banerjee, Samrat Ganguly,
“MobiStream: Error-Resilient Video Streaming in Wireless
WANs using Virtual Channels”, Proceedings of IEEE
Infocom 2006
Question—if you still have any
39