Transcript A Hybrid Adaptation Protocol for Layered Multicast and Its

Research and Publications:
A Personal Perspective
Bo Li
Hong Kong University of Science and Technology
Microsoft Research Asia
2015/7/18
p. 1
Outline





What about research?
How much does one have to learn?
PhD research
What is procedure of publications?
How to write technical papers?
2015/7/18
p. 2
Research is easy!



2015/7/18
You have done this many times in course
projects
Take a known problem, and apply a known
technique
Obtain results, and write a report
p. 3
Research is difficult!






2015/7/18
Is it technically correct?
Does it make intuitively sense?
Is it publishable, where and why?
Does it offer some insights beyond what
we have known?
Does it have any impact?
…
p. 4
Research
There are basically four types of research
works:





2015/7/18
New problem and new solution
New problem and old solution
Old problem and new solution
Old problem and old solution
p. 5
Research
Case I comes rarely, perhaps something you
could only wish, once a life-time experience

Shannon theory

Cases II and III are the ones that you
should target for



Packet scheduling: weighted fair queuing
Geographical routing in ad hoc networks
Case IV is where you can start


2015/7/18
Plenty of out there under the category of “Yet
another paper on … “
p. 6
Where do ideas come from?


Drink a beer, relax,
ideas will come to
you
The ideas fall from
the sky!
2015/7/18

Understanding the
existing works, build
upon that
incrementally
p. 7
Where do ideas come from?
Ideas in most cases come from the deep
understanding of a subject, and possess of
broad knowledge





2015/7/18
This is not a technical training, i.e., this is not about
solving a bipartite graph, or differential equations
This is about relating them to real world problems
This is about providing new insight beyond known
This is about your creativity!
p. 8
Research: What is it?
Research = Re (repeat) + search




2015/7/18
Much of the research has been built upon
existing works, therefore a thorough
understanding of those is the basis
Too many smart people in each area, so if an
idea seems to be too good to be true, it likely
is -> rethink that again
Each idea needs iterations: what is it? why
has it not been done? what is the logical
connection with the existing approaches?
p. 9
Research: Engineering Problem
Each solution to an engineering problem is only a
trade-off; it is not a cure for all, it definitely
has side-effect.

Networking coding



Potential capacity gain under loaded system
Is it really? Is there any alternative? What is the
penalty for doing so? Can we handle that in system
design?
P2P



2015/7/18
Facilitate the voluntary file sharing
Can this be extended beyond that?
p. 10
Case I: Adaptive Video Multicast

The need for multicast - efficiency


Multiple-unicast
Multicast
Fundamental problem: users’ heterogeneity
and network dynamics
2015/7/18
p. 11
Case I: Adaptive Video Multicast


Layered video encoding and transmission
Cumulative layered coding (Scalable coding)


2015/7/18
Base layer: most important feature, low rate, low quality
Enhancement layers: progressively refine quality
p. 12
Case I: Adaptive Video Multicast

Existing solutions




Multiple multicast tree, each for a layer
Receiver adaptation: user’s joining and leaving
groups (receiver)
Adaptation is performed at receivers only: fixed
layer rates and limited num of layers
Fundamental Problem

2015/7/18
The mismatch between the fixed sending rate
and the dynamic and heterogeneous rate
requirement from receivers
p. 13
Case I: Adaptive Video Multicast
Layered Bit-stream
Layered Video
Coder
Rate
Controller
Layered
Rate
Calculator
Feedback
Collector
2015/7/18
Layered Bit-stream
Layer
Adapter
Bandwidth Report
Bandwidth
Estimator
1
Receiver
2
...
...
Bandwidth
Report
Sender
Receiver
Receiver
N
Multicast Network
Layered
Decoder
A Receiver
p. 14
Case I: Adaptive Video Multicast

End-to-end adaptive video multicast




2015/7/18
Optimal rate allocation for each layer:
formulation and solution
End-to-end transmission protocol and whether
TCP friendly
Complexity analysis
Practical issues: feedback explosion (sampling),
RTT estimation (open and closed loop)
p. 15
Sample References

B. Li and J. Liu, “Multi-Rate Video Multicast over the
Internet: An Overview,” IEEE Network, (17)1: 24-29,
January-February 2003.

J.-C. Liu, B. Li and Y.-Q. Zhang, “Adaptive Video
Multicast Over the Internet,” IEEE Multimedia, (10)1:
22-33, January-March 2003.

J. Liu, B. Li, and Y.-Q. Zhang, “An End-to-End Adaptation
Protocol for Layered Video Multicast Using Optimal Rate
Allocation, IEEE Transactions on Multimedia, (6)7: 87102, February 2004.
2015/7/18
p. 16
Summary
 Identify a general category of problems
 The idea should be intuitively simple
 Publications can be “easier”
2015/7/18
p. 17
Outline





What about research?
How much does one have to learn?
PhD research
What is procedure of publications?
How to write technical papers?
2015/7/18
p. 18
How much does one have to learn?

I have learnt all the mathematics, and I am
loaded



Discrete algorithms, partial differential
equations, dynamic control, probabilistic
modeling, information theory and etc.
I still don’t have a clue what to do in
research.
Where in the world is research topic?
2015/7/18
p. 19
How much does one have to learn?


I have read all papers out there from
journals and conferences
Can I do research now?


2015/7/18
There is no way you can cope with all of them
Majority of the published works are junks, and
can cause brain damage and can be misleading
p. 20
The minimum needed for research


Logical thinking, after all we are in
engineering world
Basic skills


You have to know the Dijstra algorithm in order
to understand the OSFP (?)
the ability to learn

2015/7/18
Life long learning process, esp. in CS
p. 21
The minimum needed for research

Abstraction. Take a problem, you have to
know





What is/are the fundamental problem(s)
You have to see both “forest and trees”
What have been done, why?
What are seemingly undoable?
Understand your strength and weakness
2015/7/18
p. 22
The minimum needed for research

Open mind



We are not dealing with math problem in that there
exists perfect solutions
Engineering solutions are subject to argument and
debate, i.e., each solution is a trade-off, and it only works
in a constrained environment
Critical mind


2015/7/18
When you read others, it is equally important to
understand what circumstance that it does not work as in
which it works
If you can not identify such scenario, you are not
understanding the problem
p. 23
Case II: Proxy Placement

How to place the proxy (mirror sites) in the
internet


2015/7/18
B. Li et al., “On the Optimal Placement of Web Proxies in
the Internet,” Proc. IEEE Infocom'99
ACM Communications Review (2001) cited as the 1st ever
work on this topic
p. 24
Case II: Proxy Placement




Formulation: graph theory problem, k-median
problem: given N nodes, how to select K nodes to
place the content so certain optimal criterion can
be met
For general graph, this is NP-hard
For tree, we solved this using a known dynamic
programming technique
This turns out to be the fundamental problem for
object replication in DB, which has been cited over
300 times since then
2015/7/18
p. 25
Sample References



J.-L. Xu, B. Li and D. Lee, “Placement Problems for
Transparent Data Replication Proxy Services,”
IEEE Journal Selected Areas in Communications,
20(7): 1383-1398, 2002
A. Vigneron, L. Gao, M. Golin, G. Italiano and B. Li,
“An Algorithm for Finding a k-Median in a Directed
Tree,” Information Processing Letter, 74(1-2): 8188, 2000
B. Li, “Content Replication in a Distributed and
Controlled Environment,” Journal of Parallel and
Distributed Computing, 59(2), pp. 1-21, Nov. 1999
2015/7/18
p. 26
Summary
 Finding a problem is more important, and
difficult than solving a problem
 You need out-of-box thinking
2015/7/18
p. 27
Outline





What about research?
How much does one have to learn?
PhD research
What is procedure of publications?
How to write technical papers?
2015/7/18
p. 28
PhD Research


Make a plan earlier, for 3-4 years
The research topics must be of current interest,
and state-of-the-art



Don’t work on packet scheduling, and IEEE 802.11 MAC
protocol 
Beating the performance of Ethernet is like kicking a
dead horse!
It has to be something that within your capability


2015/7/18
You need to understand your strength and weakness, and
be realistic (don’t shoot stars)
You should know your interest, self-motivation is one of
the single most important factors
p. 29
PhD Research



Read top 10 or 20 papers in the area
Understand the basics, fundamental
problems, and open issues
Think and read


Start from a small yet concrete problem


Put all papers into perspective
Build you skill and confidence
Discussions generates ideas
2015/7/18
p. 30
Reading

Top conference or workshop first



Second tier conference only for reference


IEEE Globecom, ICC
Avoid bad conferences


ACM Sigcomm, ACM Mobicom, IEEE Infocom
IEEE ICNP, IWQoS, MobiHoc
Regional, and less reputable ones
Read journal papers only it has not been published
else where, or when it contains more detailed and
complete treatment
2015/7/18
p. 31
PhD Research

Focus!





Don’t over-estimate your ability
Don’t diversify too much
Start with small idea(s), publish in an easy
conference in the 2nd year
Working plan: target at 2 conferences (20 or less
acceptance rate) and one journal paper per year
(in 2-3 years)
The thesis is a collection of the papers

2015/7/18
So you need to have a focus!
p. 32
Research Topics


Theoretical vs. practical
Can this be related to a real world problem


It should have a clear boundary


Engineering approach
Focus on what can or/and can not be done
Don’t lose the bigger picture


2015/7/18
Tree and the forest
How does it help to solve one or more pieces in
the bigger problem
p. 33
PhD Research

System works





System work usually involves team efforts
Building from scratch is a dangerous thing
The prototype has to demonstrate significance in that
either this is a proof of a concept, or demonstrate the
feasibility
Less than 5% chance being useful, yet worth the
investment for technical break through
Theoretical works


2015/7/18
Theoretical work usually provides an elegant solution to a
generalized problem
The significance can be greatly enhanced if practical
insight can be drawn
p. 34
Advisor/Mentor

Choosing an advisor could be the single most
important factor for your research


Understanding the general problem, the ability to
identify the significance and yet another
Personal and professional relationship





2015/7/18
Junior vs. senior, hands-on or hands-off
Regular guidance vs. direction
Independent and close collaboration
Group or individual effort
Time, efforts and experience
p. 35
You really need an Advisor/Mentor

Can a rabbit eat a dog, fox and wolf?
2015/7/18
p. 36
You really need an Advisor/Mentor

Punch line
It really does not matter what the topic is, and
what you are doing, all it matters is who your
advisor is
2015/7/18
p. 37
Example I: My PhD research
What you need is a jump start for confidence
building

A. Ganz and B. Li “Performance of Packet Networks in
Satellite Clusters,” IEEE Journal on Selected Areas in
Communications, (10)6: 1012-1019, August 1992

Be objective, don’t lose the bigger picture




2015/7/18
The research topics are both important and not so
important
The research works in PhD study is simply a training process,
be realistic.
Usually the most productive period for one’s career is within
the 5 years’ after one’s PhD
p. 38
Example II: My student
Jiangchuan Liu





2015/7/18
Who has written close to 20 top journal papers since 1999,
largely on video multicast
Assistant Professor at Simon Fraser Univ., former with
Chinese Univ. of Hong Kong.
Won the prestigious Hong Kong Young Scientist award in
2003, given to one individual annually by Hong Kong Institute
of Science (HKIS)
Sometime direction is all a student needs
p. 39
Collaborations leads to Productivity
Working with the right people

Skill complementary
Same interests



Working with smart people
2015/7/18
p. 40
Case III: Cellular Networks
Number of cells per cluster:
7
3
N  i 2  ij  j 2
1
6
1
4
4
5
2
7
3
7
3
1
6
1
4
Frequency Reuse Factor, 1 / N
5
1
6
4
5
2
2
7
1
3
1
6
4
If total of S channels available,
Each cell can be assigned k channel
k S/N
If M clusters within the system,
the total system capacity:
C  MkN  MS
Frequency Reuse Pattern for N=7
2015/7/18
p. 41
Case III: Cellular Network

There were several fundamental problems in
cellular network when moving to multiservice environment



2015/7/18
Bandwidth within a cell have to be shared
Erlang assumption (Poisson arrival and
exponential sojourn time and exponential call
duration time) fails due to data traffic
Gaussian approximation for a cell capacity fails
given the cell is small …
p. 42
Case III: Cellular Network

Relaxing Erlang, by considering heavy tail
long range dependency LRD) distribution,
i.e., Pareto distribution

2015/7/18
Failed since 1997
p. 43
Case III: Cellular Network
Gaussian approximation



2015/7/18
Particle movement and diffusion equation
S. Wu, K. Y. M. Wong and B. Li, “A Dynamic Call
Admission Policy with Precision QoS Guarantee
Using Stochastic Control for Mobile Wireless
Networks,” IEEE/ACM Transactions on
Networking, (10)2: 257-271, April 2002.
p. 44
Summary
 Working on hard and open problems
 Persistence pays off
2015/7/18
p. 45
Summary
 The idea has to be simple, this is a hard
lessen we have learn
 10 years of research on ATM are pretty
much a waste


2015/7/18
Internet
POTS or PSTN
p. 46
Outline





What about research?
How much does one have to learn?
PhD research
What is procedure of publications?
How to write technical papers?
2015/7/18
p. 47
Conference Paper




Start earlier for a conference submission
Deadline is the best drive for making progress
What make a good paper: content and writing!
Clear, convincing, simple and good English


This is a never-ending optimization process, do this
within the time and page limits
Review process 5/30 rule


2015/7/18
5 minutes - Abstract, introduction, figure and conclusion
30 minutes – understand 90% of the paper
p. 48
Journal Paper





A good conference paper (10%-25% acceptance
rate) can be submitted to a journal, with 30% new
results
Report more complete and focused results
Give yourself a deadline
Be patient with the long review and re-review
At the earlier stage of one’s career, don’t quit if
asked for major revision

2015/7/18
But don’t do seemingly impossible
p. 49
What does a reviewer look for








New problem or new solution?
Are the main results significant?
Is the paper technically correct?
Does the paper provide a fair assessment of its
strength and limitation?
Is the paper clearly written, thus accessible to
general readers?
Are the references adequate?
Is the paper appropriate for conference/journal?
…
2015/7/18
p. 50
Outline





What about research?
How much does one have to learn?
PhD research
What is procedure of publications?
How to write technical papers?
2015/7/18
p. 51
Writing

Writing is a process of self-clarification


There are plenty of books teaching you how
to write



Habit of writing, notes, random thoughts
Imitation might be the best way to start
Writing is part of the work
Writing can be difficult and painful for all
of us, there is no short cut, it improves
along the process
2015/7/18
p. 52
Writing




Iterative refinement, outlines – 3-5 times
Start with existing work, introduction, your own
work, experiment
Abstract and summary (many hours’ work)
Revise many times, ask others to read





Lots of efforts for small improvement
Is there a better way to say, a better word to use?
Is the paper logically connected?
What are the questions reviewers might have?
Never ending optimization subject to time and
page limit
2015/7/18
p. 53
Review Process


Low acceptance rate
Reviewers are potential competitors


Reviewers are very busy



Convincing but less critical
Try to make their job easier
English is not our strength
Don’t try your luck, it won’t work!
2015/7/18
p. 54
Problem I



Reviewers have to understand me
Only you know your work well, not
reviewers
Make it easier to understand





2015/7/18
Motivation and rationales
Control the level of details
Make connection throughout the paper
Use examples, graph, flow chat whenever
needed
Pose questions, and answer them
p. 55
Problem II

Formality leads to elegance




I am good at math, formal is high class, I have
20 definitions and 15 theorems
Keep it simple, perhaps stupid
Start with motivations and rationales
Avoid unnecessary formality
2015/7/18
p. 56
Problem III

I have 10 contributions


Focus in the key




Reviewers should see this is a masterpiece
One problem, one solution in a conference paper
One problem, more complete solutions in a journal paper
Thorough and deep
Emphasize but not exaggerate your contributions


2015/7/18
Say it is “significant” only if it is, and justify it
If it is the first time, say “This is, to the best of our
knowledge, the first time … “
p. 57
Problem IV



It is ok to be informal as long as understandable
Technical writing is formal
Avoid casual writing






“believe me, this is really a good work”
Don’t use long sentences, break them
Flow and logic is much more important, proof
reading does not help you with that
Top-down organization and outlining
Use good papers as sample – imitate!
Write down your mistakes and eliminate them
2015/7/18
p. 58
Problem V

Reviewers are evil




They reject paper so their papers can be accepted
They reject my paper, so to steal my ideas
Reviewers are critical
You have to be a good salesman to convince them
2015/7/18
p. 59
Closing Thoughts



Research needs creativity, patience, hard working,
persistence
Writing is a self-improving process
Understanding the process of publication, in
particular review process helps
KEYS


Balance the search and re-development and outof-box thinking
Working with smart people
2015/7/18
p. 60
Closing Thoughts



We have done so much for networking!
10 years ago: IP vs. ATM
Since then





2015/7/18
QoS, network Calculi, intServ, diffServ,
CNDs, DDoS, VoIP, SIP, multicast
TPC, closed-loop control, measurement,
LRD traffic, power laws,
Streaming, WWW protocols, caching
p. 61
Closing Thoughts

Yet this conversation happened in a major
research lab (NJ) 
Q: given the traffic and network topology, how do we
optimize the routes?
A1: “Uh ….”
A2: “We don’t really think it that way … “
A3: “We don’t know the traffic, we don’t know the
topology, the routers do not automatically adapt to
traffic, and we don’t know how to optimize the
route configuration. BUT, other than that, we are
all set!”
2015/7/18
p. 62
Closing Thoughts


Don’t believe anything you read, esp., those
obviously correct ones!
Challenge the fundamental!
2015/7/18
p. 63
Acknowledgement


Students, collaborators, and MSRA
Charles X. Ling (Univ. of Western Ontario), Qiang
Yang (HKUST), Jim Kurose (UMass at Amherst)
2015/7/18
p. 64