NMSL - User contributions [en-ca]

Private:psim

2009-03-13T17:47:41Z

Ysa57:

This page documents the development of a discrete event simulator for P2P video streaming applications. This simulator captures important features of data-driven video streaming systems. In particular, it is designed to evaluate: (i) the performance of various segment scheduling algorithms; (ii) the potential of network coding in multi-layer P2P video streaming systems.

== Implementations ==

=== Done Classes ===

=== Work-on-progress Classes ===
Event (ysa57)

= Class Diagrams =

* use long for time/offset in msec, which has a rollover time 24.85 days

<pre>

class Layer { // video layer, we divide each layer into fixed size blocks, we keep track of
// block size and no blocks here
int layer; // layer number it belongs to, set to zero for nonscalable frame
int blockSize; // blocks are fixed size, in bytes
int noBlocks; // how many block here
int dataSize; // aggregate size of all blocks
}

class Frame { // video frame, read from trace file
int no; // serial number
long deadlineOffset; // deadline offset compared to the start of the video, in msec
int totalSize; // total frame size in bytes, including all layers
}

class Segment { // packetized frames
int no; // serial number
Vector<Frame> frames; // reference to included frame
int totalSize; // aggregate size in bytes
Hashtable<Integer, Layer> layers; // reference to layers of this frame, key is the layer id
long getDeadline(); // returns the worst case deadline of this segment (first frame?)
}

class Video { // a media file, shared by a group of peers
String filename; // video trace file path and name
Hashtable<int, Frame> frameTrace; // frames read from the trace file
Hashtable<int, Segment> segmentTrace; // segments generated by the prepareSegments(...)
void prepareSegments(int noFrame); // packetize frames into segment,
// noFrame indicates how many frames should we put in one segment;
// we might implement other packtization schemes later.
}

Interface Node { // a network node, currently can be either a tracker or a peer
}

class Tracker implement Node { // holds a set of groups/videos
Vector<Group> groups; // all the video groups
void addPeer(Group group, Peer peer); // insert a peer into a video group
}

class Peer implements Node { // represent a running peer
int id; // sequential peer id
int ingressBW; // incoming bandwidth in bps
int egressBW; // outgoing bandwidth in bps
Hashtable<Video, Vector<Connection>> senders; // peers that we may send requests to
Hashtable<Video, Vector<Connection>> receivers; // peers that we may send data to
Connection tracker; // control connection to the tracker
Hashtable<Video, VideoBufMap> vBufMaps; // points to the video-level buffer map
void join(Video vide); // the peer joins a group
void leave(Video video); //the peer leaves the group
//here we should call a scheduling algorithm to do the scheduling
void start(Video video); // start downloading a video
void stop(Video video); // stop downloading
}

class Group { // peers that have downloaded or want to download a Video
Video video; // media shared among peers
Vector<Peer> peers; // peers in this group
Vector<Peer> join(Peer peer); // adding a new peer into this group, and return a list of senders
void leave(Peer peer); // removing a peer from this group
}

class Connection { // end to end network link between two peers
Peer peer1; // one end
Peer peer2; // the other
long delay; // transmission delay in msec
int e2eBW; // end-to-end bandwidth in bps
int estimateRate; // estimated rate (maybe historical)
}

class VideoBufMap {
Hashtable<Integer, SegBufMap> sBufMaps; // points to segment bufmap
}

class SegBufMap {
Hashtable<Integer, LayerBufMap> lBufMaps; // points to layer bufmap
}

class LayerBufMap {
boolean avail; // availability bit for this (video, segment, layer) tuple
NCBuf ncBuf; // network coding structure
}

class NCBuf {
boolean servCapibility; // Serving capability of each segment
// show whether this segment is capable of serving other peers(applicable in NC)
int noCodedBl; // No. of encoded blocks for this (video,segment,layer)
BufferedMatrix matrix; // coefficients and their corresponding encoded blocks up to now
}

class BufferedMatrix{ // save coefficients and their corresponding encoded blocks up to now
Vector<Vector<Integer>> coef; // coefficients of the corresponding encoded blocks
Vector <Integer>encodedValue; // encoded blocks
Vector<Integer> decode(); // perform decoding process and return the original blocks of a segment
void encode(); // perform encoding process on blocks of a segment

}

class SysParam{ // system parameters that can be changed in each iteration of the simulation
float portionServ; // after receiving this portion of coded blocks out of total number of blocks, the segment is capable
of serving to others [in case of network coding]
long skipSec; // time duration which is skipped from the current playback point for a new joined peer [in case of
network coding]
float portionEncoding; // a given peer peform encoding among this portion of encoded blocks out of the total coded
blocks that has been received so far
// blocks for encoding will be chosen randomly out of all received encoded blocks [in case of
network coding]
}

// the following classes implement the Galois field [in case of network coding]
// coefficients should be selected randomly from Galois field
class ExtendedGaloisField extends GaloisField { // extension of Galois field where you can create
//the field with a predefined base and power
GaloisPolynomial[] alfaPowers;
GaloisPolynomial moduloPoly;
char alfa;
GaloisField base;
int pwr;
}

public class GaloisField { // implementing the Galois field
}

class GaloisPolynomial { //working with Polynomials
private int[] coefs; // coefs are selected from Galois field
private char alfa;
private GaloisField field;
}

class GaloisException{
}

// XXX TODO XXX

class SlidingWindow{ // the sliding window which contains all the segments that the receiver is interested currently
// set it to a fixed size, for example 1 minute of videos
// the receiver first inform all its neighbors which part of the video it is interested currently,
// then its neighbors will send their bitmap of that part to the receiver for scheduling
int startOffset; //the offset of the starting segment compared with the start of the video
int endOffset; // the offset of the ending segment compared with the start of the video
double slidingWindowSize(); //get the size of the sliding window
}

class exchangeWindow{ // the exchange window is the front part of the sliding window.
//The unavailable segments in exchange window will be requested by the peer
//usually we set it to a fixed size, for example, 10 seconds of video
// the field of this class is similar to that of the SlidingWindow class
int startOffset;
int endOffset;
void move(); // move the exchange window forward afte a scheduling period and do a next scheduling
double getSlidingWindowSize()
}

interface Scheduler{ // any class wants to do scheduling should implement this interface
void schedule() throws simException; // the scheduling period is specified in the specific scheduling algorithm class
}

class resultItem{ //this class records a scheduling item
int peerID;
int segID;
long startTime; //start time of the peer to transmit this segment
}

class SchedulingResult{ // this class is used to record scheduling results and do some statistics,
// for example, calculate the average delivery rate
Vector<resultItem> item; // result item: <peerID, segID, startTime> (we may write this vector to a log file later)
long runningTime; //running time of the algorithm
long deliveryRatio; //Average delivery ratio

double getDeliveryRatio(); //get the actual average delivery ratio
double getRunningTime(); //get the running time
}

class SEFF implements Scheduler{ // the Serial Earliest Finish-time First scheduling algorithm
SchedulingResult result; // create a schedulingResult object to store the result

void schedule(); //implement the Scheduler interface
void writeResult(); //write scheduling result to the result object of one scheduling period
//including calculating the average delivery ratio and running time
}

class LRF implements Scheduler{ // the Local Rarest First algorithm
SchedulingResult result; // create a schedulingResult object to store the result

void schedule(); //implement the Scheduler interface
void writeResult(); //write scheduling result to the result object of one scheduling period
//including calculating the average delivery ratio and running time
}

class RndGen { // common random number/event generators, to deal with
// 1. event: add new receiver for a group/video
// 2. event: remove a receiver from a group/video
// 3. number: peer's bandwidth
}

class SimException {

}

Interface EventHandler {
void handle() throws SimException; // callback function
}

class Event {
long time; // when this event happens
Node src; // which peer generates this event
Node dst; // whom is destinate of this event
Vector<EventHandler> handlers; //process an event and update states accordingly
int type; // enum, see below
// 1. connectSent: peer 1 makes a connection to peer 2, and add each other into neighbors
// 2. connectArrived: the connect message is received by the peer 2
// 3. acceptSent: the potential sender reply with an accept message
// 4. acceptArrived: the accept message arrives at the connection originator
// 5. requestSent: a receiver sends a high-priority request message to a sender
// 6. requestArrived: a request message gets to a sender
// 7. dataSent: a sender sends a data segment
// 8. dataArrived: a data segment arrives to a receiver
// 9. joinSent: a join message to the tracker
// 10. joinArrived: a join message reaches the tracker
// 11. responseSent: a response message sent by the tracker
// 12. responseArrived: a response message reaches the receiver

// 13. scheduleStarted: a scheduling period started.
//14. bimapSyncSent: the receiver inform all its neighbors what part of the video it is interested currently
in order to get a small bitmap from them to do scheduleing, this message is sent
when the receiver: jumps to view another part of the video or a new neighbor joins.
//15. bitmapSyncArrived: the sender receives the bitmap Synchronization information

//commet: how should we do when a scheduling period expires?
//There are two situations: 1. all scheduled segments arrived; 2. some segments are still in transmission.

void addHandler(Interface EventHandler); // add an additional event handler
void rmvHandler(Interface EventHandler); // remove an additional event handler
}

class EventQueue {
SortedMap<Long, Event> queue; // events sorted on its time
void dispatch(Event event); // sequentially invoke even handlers
}

class Simulator {
long simTime; // elapsed simulation time in msec
EventQueue events; // pending events that will be processed
void dispatchEvent(); // forever loop to process the next event
}

Some comments:
*

</pre>

= Performance metrics for scheduling =

Here are some performance metrics:
<pre>
1. Average delivery ratio: number of on-time scheduled segments over total number of segments to be scheduled
2. Load balance among senders
3. Initial buffering time
4. Time and space complexity of the scheduling algorithm
</pre>

= Performance metrics for network coding =

Here are some performance metrics:
<pre>
1. Playback quality (PSNR)
2. Resilience to peer dynamics (ability of maintaning good streaming quality)
3. Required server capacity
</pre>

= How to install uml and svn tools in eclipse3.2.x =

<pre>
*. Install emul2
1. Go to "http://www.soyatec.com/euml2/installation/", download its free edition. (Select the right version according to your eclipse)
2. Unpack the zip file
3. Open your eclipse, and go to Help -> Software Updates -> Find and install ... -> Search for new features to install -> New local site
then find the unpakced file to install it.
4. How to use: after you creating a new java project, go to File -> New -> Other, select the "UML2 Class Diagram" under the eUML directory,
then you can create a class diagram for your project .

*. Install subclipse
1. Open your eclipse, and go to Help -> Software Updates -> Find and install ... -> Search for new features to install -> New Remote Site
2. Add "http://subclipse.tigris.org/update_1.4.x" to the URL field and add an arbitrary name to the Name field
3. Follow the instruction to install it.
4. If you encounter an error like "Subclipse Integration for Mylyn 3.x (Optional) (3.0.0) requires plug-in "org.eclipse.mylyn.tasks.core (3.0.0)"
don't worry, just deselect the "Integrations" item and continue to install.
5. Go to Window -> Preferences -> Team. If you can see SVN under the Team tab, congratulations, your installation is done.
6. How to use: right click the project you want to commit, select Tean -> Share project -> SVN, input the URL of
your svn server, then you can import your project to it.
7. For more details on how to use subclipse, please refer to
http://www.ibm.com/developerworks/opensource/library/os-ecl-subversion/
</pre>

= The project directory =
I've put the psim project to "https://cs-svn.cs.surrey.sfu.ca/svn/nsl/schedule/psim". You can check it out in eclipse with subclipse.

Private:psim

2009-03-11T22:25:29Z

Ysa57:

This page documents the development of a discrete event simulator for P2P video streaming applications. This simulator captures important features of data-driven video streaming systems. In particular, it is designed to evaluate: (i) the performance of various segment scheduling algorithms; (ii) the potential of network coding in multi-layer P2P video streaming systems.

= Class Diagrams =

* use long for time/offset in msec, which has a rollover time 24.85 days

<pre>

class Layer { // video layer, we divide each layer into fixed size blocks, we keep track of
// block size and no blocks here
int layer; // layer number it belongs to, set to zero for nonscalable frame
int blockSize; // blocks are fixed size, in bytes
int noBlocks; // how many block here
int dataSize; // aggregate size of all blocks
}

class Frame { // video frame, read from trace file
int no; // serial number
long deadlineOffset; // deadline offset compared to the start of the video, in msec
int totalSize; // total frame size in bytes, including all layers
}

class Segment { // packetized frames
int no; // serial number
Vector<Frame> frames; // reference to included frame
int totalSize; // aggregate size in bytes
Hashtable<Integer, Layer> layers; // reference to layers of this frame, key is the layer id
long getDeadline(); // returns the worst case deadline of this segment (first frame?)
}

class Video { // a media file, shared by a group of peers
String filename; // video trace file path and name
Hashtable<int, Frame> frameTrace; // frames read from the trace file
Hashtable<int, Segment> segmentTrace; // segments generated by the prepareSegments(...)
void prepareSegments(int noFrame); // packetize frames into segment,
// noFrame indicates how many frames should we put in one segment;
// we might implement other packtization schemes later.
}

Interface Node { // a network node, currently can be either a tracker or a peer
}

class Tracker implement Node { // holds a set of groups/videos
Vector<Group> groups; // all the video groups
void addPeer(Group group, Peer peer); // insert a peer into a video group
}

class Peer implements Node { // represent a running peer
int id; // sequential peer id
int ingressBW; // incoming bandwidth in bps
int egressBW; // outgoing bandwidth in bps
Hashtable<Video, Vector<Connection>> senders; // peers that we may send requests to
Hashtable<Video, Vector<Connection>> receivers; // peers that we may send data to
Connection tracker; // control connection to the tracker
Hashtable<Video, VideoBufMap> vBufMaps; // points to the video-level buffer map
void join(Video vide); // the peer joins a group
void leave(Video video); //the peer leaves the group
//here we should call a scheduling algorithm to do the scheduling
void start(Video video); // start downloading a video
void stop(Video video); // stop downloading
}

class Group { // peers that have downloaded or want to download a Video
Video video; // media shared among peers
Vector<Peer> peers; // peers in this group
Vector<Peer> join(Peer peer); // adding a new peer into this group, and return a list of senders
void leave(Peer peer); // removing a peer from this group
}

class Connection { // end to end network link between two peers
Peer peer1; // one end
Peer peer2; // the other
long delay; // transmission delay in msec
int e2eBW; // end-to-end bandwidth in bps
int estimateRate; // estimated rate (maybe historical)
}

class VideoBufMap {
Hashtable<Integer, SegBufMap> sBufMaps; // points to segment bufmap
}

class SegBufMap {
Hashtable<Integer, LayerBufMap> lBufMaps; // points to layer bufmap
}

class LayerBufMap {
boolean avail; // availability bit for this (video, segment, layer) tuple
NCBuf ncBuf; // network coding structure
}

class NCBuf {
boolean servCapibility; // Serving capability of each segment
// show whether this segment is capable of serving other peers(applicable in NC)
int noCodedBl; // No. of encoded blocks for this (video,segment,layer)
BufferedMatrix matrix; // coefficients and their corresponding encoded blocks up to now
}

class BufferedMatrix{ // save coefficients and their corresponding encoded blocks up to now
Vector<Vector<Integer>> coef; // coefficients of the corresponding encoded blocks
Vector <Integer>encodedValue; // encoded blocks
Vector<Integer> decode(); // perform decoding process and return the original blocks of a segment
void encode(); // perform encoding process on blocks of a segment

}

class SysParam{ // system parameters that can be changed in each iteration of the simulation
float portionServ; // after receiving this portion of coded blocks out of total number of blocks, the segment is capable
of serving to others [in case of network coding]
long skipSec; // time duration which is skipped from the current playback point for a new joined peer [in case of
network coding]
float portionEncoding; // a given peer peform encoding among this portion of encoded blocks out of the total coded
blocks that has been received so far
// blocks for encoding will be chosen randomly out of all received encoded blocks [in case of
network coding]
}

// the following classes implement the Galois field [in case of network coding]
// coefficients should be selected randomly from Galois field
class ExtendedGaloisField extends GaloisField { // extension of Galois field where you can create
//the field with a predefined base and power
GaloisPolynomial[] alfaPowers;
GaloisPolynomial moduloPoly;
char alfa;
GaloisField base;
int pwr;
}

public class GaloisField { // implementing the Galois field
}

class GaloisPolynomial { //working with Polynomials
private int[] coefs; // coefs are selected from Galois field
private char alfa;
private GaloisField field;
}

class GaloisException{
}

// XXX TODO XXX

class SlidingWindow{ // the sliding window which contains all the segments that the receiver is interested currently
// set it to a fixed size, for example 1 minute of videos
// the receiver first inform all its neighbors which part of the video it is interested currently,
// then its neighbors will send their bitmap of that part to the receiver for scheduling
int startOffset; //the offset of the starting segment compared with the start of the video
int endOffset; // the offset of the ending segment compared with the start of the video
double slidingWindowSize(); //get the size of the sliding window
}

class exchangeWindow{ // the exchange window is the front part of the sliding window.
//The unavailable segments in exchange window will be requested by the peer
//usually we set it to a fixed size, for example, 10 seconds of video
// the field of this class is similar to that of the SlidingWindow class
int startOffset;
int endOffset;
void move(); // move the exchange window forward afte a scheduling period and do a next scheduling
double getSlidingWindowSize()
}

interface Scheduler{ // any class wants to do scheduling should implement this interface
void schedule() throws simException; // the scheduling period is specified in the specific scheduling algorithm class
}

class resultItem{ //this class records a scheduling item
int peerID;
int segID;
long startTime; //start time of the peer to transmit this segment
}

class SchedulingResult{ // this class is used to record scheduling results and do some statistics,
// for example, calculate the average delivery rate
Vector<resultItem> item; // result item: <peerID, segID, startTime> (we may write this vector to a log file later)
long runningTime; //running time of the algorithm
long deliveryRatio; //Average delivery ratio

double getDeliveryRatio(); //get the actual average delivery ratio
double getRunningTime(); //get the running time
}

class SEFF implements Scheduler{ // the Serial Earliest Finish-time First scheduling algorithm
SchedulingResult result; // create a schedulingResult object to store the result

void schedule(); //implement the Scheduler interface
void writeResult(); //write scheduling result to the result object of one scheduling period
//including calculating the average delivery ratio and running time
}

class LRF implements Scheduler{ // the Local Rarest First algorithm
SchedulingResult result; // create a schedulingResult object to store the result

void schedule(); //implement the Scheduler interface
void writeResult(); //write scheduling result to the result object of one scheduling period
//including calculating the average delivery ratio and running time
}

class RndGen { // common random number/event generators, to deal with
// 1. event: add new receiver for a group/video
// 2. event: remove a receiver from a group/video
// 3. number: peer's bandwidth
}

class SimException {

}

Interface EventHandler {
void handle() throws SimException; // callback function
}

class Event {
long time; // when this event happens
Node src; // which peer generates this event
Node dst; // whom is destinate of this event
Vector<EventHandler> handlers; //process an event and update states accordingly
int type; // enum, see below
// 1. connectSent: peer 1 makes a connection to peer 2, and add each other into neighbors
// 2. connectArrived: the connect message is received by the peer 2
// 3. acceptSent: the potential sender reply with an accept message
// 4. acceptArrived: the accept message arrives at the connection originator
// 5. requestSent: a receiver sends a high-priority request message to a sender
// 6. requestArrived: a request message gets to a sender
// 7. dataSent: a sender sends a data segment
// 8. dataArrived: a data segment arrives to a receiver
// 9. joinSent: a join message to the tracker
// 10. joinArrived: a join message reaches the tracker
// 11. responseSent: a response message sent by the tracker
// 12. responseArrived: a response message reaches the receiver

// 13. scheduleStarted: a scheduling period started.
//14. bimapSyncSent: the receiver inform all its neighbors what part of the video it is interested currently
in order to get a small bitmap from them to do scheduleing, this message is sent
when the receiver: jumps to view another part of the video or a new neighbor joins.
//15. bitmapSyncArrived: the sender receives the bitmap Synchronization information

//commet: how should we do when a scheduling period expires?
//There are two situations: 1. all scheduled segments arrived; 2. some segments are still in transmission.

void addHandler(Interface EventHandler); // add an additional event handler
void rmvHandler(Interface EventHandler); // remove an additional event handler
}

class EventQueue {
SortedMap<Long, Event> queue; // events sorted on its time
void dispatch(Event event); // sequentially invoke even handlers
}

class Simulator {
long simTime; // elapsed simulation time in msec
EventQueue events; // pending events that will be processed
void dispatchEvent(); // forever loop to process the next event
}

Some comments:
*

</pre>

= Performance metrics for scheduling =

Here are some performance metrics:
<pre>
1. Average delivery ratio: number of on-time scheduled segments over total number of segments to be scheduled
2. Load balance among senders
3. Initial buffering time
4. Time and space complexity of the scheduling algorithm
</pre>

= Performance metrics for network coding =

Here are some performance metrics:
<pre>
1. Playback quality (PSNR)
2. Resilience to peer dynamics (ability of maintaning good streaming quality)
3. Required server capacity
</pre>

= How to install uml and svn tools in eclipse3.2.x =

<pre>
*. Install emul2
1. Go to "http://www.soyatec.com/euml2/installation/", download its free edition. (Select the right version according to your eclipse)
2. Unpack the zip file
3. Open your eclipse, and go to Help -> Software Updates -> Find and install ... -> Search for new features to install -> New local site
then find the unpakced file to install it.
4. How to use: after you creating a new java project, go to File -> New -> Other, select the "UML2 Class Diagram" under the eUML directory,
then you can create a class diagram for your project .

*. Install subclipse
1. Open your eclipse, and go to Help -> Software Updates -> Find and install ... -> Search for new features to install -> New Remote Site
2. Add "http://subclipse.tigris.org/update_1.4.x" to the URL field and add an arbitrary name to the Name field
3. Follow the instruction to install it.
4. If you encounter an error like "Subclipse Integration for Mylyn 3.x (Optional) (3.0.0) requires plug-in "org.eclipse.mylyn.tasks.core (3.0.0)"
don't worry, just deselect the "Integrations" item and continue to install.
5. Go to Window -> Preferences -> Team. If you can see SVN under the Team tab, congratulations, your installation is done.
6. How to use: right click the project you want to commit, select Tean -> Share project -> SVN, input the URL of
your svn server, then you can import your project to it.
7. For more details on how to use subclipse, please refer to
http://www.ibm.com/developerworks/opensource/library/os-ecl-subversion/
</pre>

= The project directory =
I've put the psim project to "https://cs-svn.cs.surrey.sfu.ca/svn/nsl/schedule/psim". You can check it out in eclipse with subclipse.

Private:psim

2009-03-11T05:42:43Z

Ysa57:

This page documents the development of a discrete event simulator for P2P video streaming applications. This simulator captures important features of data-driven video streaming systems. In particular, it is designed to evaluate: (i) the performance of various segment scheduling algorithms; (ii) the potential of network coding in multi-layer P2P video streaming systems.

= Class Diagrams =

* use long for time/offset in msec, which has a rollover time 24.85 days

<pre>

class Layer { // video layer, we divide each layer into fixed size blocks, we keep track of
// block size and no blocks here
int layer; // layer number it belongs to, set to zero for nonscalable frame
int blockSize; // blocks are fixed size, in bytes
int noBlocks; // how many block here
int dataSize; // aggregate size of all blocks
}

class Frame { // video frame, read from trace file
int no; // serial number
long deadlineOffset; // deadline offset compared to the start of the video, in msec
int totalSize; // total frame size in bytes, including all layers
}

class Segment { // packetized frames
int no; // serial number
Vector<Frame> frames; // reference to included frame
int totalSize; // aggregate size in bytes
Hashtable<Integer, Layer> layers; // reference to layers of this frame, key is the layer id
long getDeadline(); // returns the worst case deadline of this segment (first frame?)
}

class Video { // a media file, shared by a group of peers
String filename; // video trace file path and name
Hashtable<int, Frame> frameTrace; // frames read from the trace file
Hashtable<int, Segment> segmentTrace; // segments generated by the prepareSegments(...)
void prepareSegments(int noFrame); // packetize frames into segment,
// noFrame indicates how many frames should we put in one segment;
// we might implement other packtization schemes later.
}

Interface Node { // a network node, currently can be either a tracker or a peer
}

class Tracker implement Node { // holds a set of groups/videos
Vector<Group> groups; // all the video groups
void addPeer(Group group, Peer peer); // insert a peer into a video group
}

class Peer implements Node { // represent a running peer
int id; // sequential peer id
int ingressBW; // incoming bandwidth in bps
int egressBW; // outgoing bandwidth in bps
Hashtable<Video, Vector<Connection>> senders; // peers that we may send requests to
Hashtable<Video, Vector<Connection>> receivers; // peers that we may send data to
Connection tracker; // control connection to the tracker
Hashtable<Video, VideoBufMap> vBufMaps; // points to the video-level buffer map
void join(Video vide); // the peer joins a group
void leave(Video video); //the peer leaves the group
//here we should call a scheduling algorithm to do the scheduling
void start(Video video); // start downloading a video
void stop(Video video); // stop downloading
}

class Group { // peers that have downloaded or want to download a Video
Video video; // media shared among peers
Vector<Peer> peers; // peers in this group
Vector<Peer> join(Peer peer); // adding a new peer into this group, and return a list of senders
void leave(Peer peer); // removing a peer from this group
}

class Connection { // end to end network link between two peers
Peer peer1; // one end
Peer peer2; // the other
long delay; // transmission delay in msec
int e2eBW; // end-to-end bandwidth in bps
int estimateRate; // estimated rate (maybe historical)
}

class VideoBufMap {
Hashtable<Integer, SegBufMap> sBufMaps; // points to segment bufmap
}

class SegBufMap {
Hashtable<Integer, LayerBufMap> lBufMaps; // points to layer bufmap
}

class LayerBufMap {
boolean avail; // availability bit for this (video, segment, layer) tuple
NCBuf ncBuf; // network coding structure
}

class NCBuf {
boolean servCapibility; // Serving capability of each segment
// show whether this segment is capable of serving other peers(applicable in NC)
int noCodedBl; // No. of encoded blocks for this (video,segment,layer)
BufferedMatrix matrix; // coefficients and their corresponding encoded blocks up to now
}

class BufferedMatrix{ // save coefficients and their corresponding encoded blocks up to now
Vector<Vector<Integer>> coef; // coefficients of the corresponding encoded blocks
Vector <Integer>encodedValue; // encoded blocks
Vector<Integer> decode(); // perform decoding process and return the original blocks of a segment
void encode(); // perform encoding process on blocks of a segment

}

class SysParam{ // system parameters that can be changed in each iteration of the simulation
float portionServ; // after receiving this portion of coded blocks out of total number of blocks, the segment is capable
of serving to others [in case of network coding]
long skipSec; // time duration which is skipped from the current playback point for a new joined peer [in case of
network coding]
float portionEncoding; // a given peer peform encoding among this portion of encoded blocks out of the total coded
blocks that has been received so far
// blocks for encoding will be chosen randomly out of all received encoded blocks [in case of
network coding]
}

// XXX TODO XXX

class SlidingWindow{ // the sliding window which contains all the segments that the receiver is interested currently
// set it to a fixed size, for example 1 minute of videos
// the receiver first inform all its neighbors which part of the video it is interested currently,
// then its neighbors will send their bitmap of that part to the receiver for scheduling
int startOffset; //the offset of the starting segment compared with the start of the video
int endOffset; // the offset of the ending segment compared with the start of the video
double slidingWindowSize(); //get the size of the sliding window
}

class exchangeWindow{ // the exchange window is the front part of the sliding window.
//The unavailable segments in exchange window will be requested by the peer
//usually we set it to a fixed size, for example, 10 seconds of video
// the field of this class is similar to that of the SlidingWindow class
int startOffset;
int endOffset;
void move(); // move the exchange window forward afte a scheduling period and do a next scheduling
double getSlidingWindowSize()
}

interface Scheduler{ // any class wants to do scheduling should implement this interface
void schedule() throws simException; // the scheduling period is specified in the specific scheduling algorithm class
}

class resultItem{ //this class records a scheduling item
int peerID;
int segID;
long startTime; //start time of the peer to transmit this segment
}

class SchedulingResult{ // this class is used to record scheduling results and do some statistics,
// for example, calculate the average delivery rate
Vector<resultItem> item; // result item: <peerID, segID, startTime> (we may write this vector to a log file later)
long runningTime; //running time of the algorithm
long deliveryRatio; //Average delivery ratio

double getDeliveryRatio(); //get the actual average delivery ratio
double getRunningTime(); //get the running time
}

class SEFF implements Scheduler{ // the Serial Earliest Finish-time First scheduling algorithm
SchedulingResult result; // create a schedulingResult object to store the result

void schedule(); //implement the Scheduler interface
void writeResult(); //write scheduling result to the result object of one scheduling period
//including calculating the average delivery ratio and running time
}

class LRF implements Scheduler{ // the Local Rarest First algorithm
SchedulingResult result; // create a schedulingResult object to store the result

void schedule(); //implement the Scheduler interface
void writeResult(); //write scheduling result to the result object of one scheduling period
//including calculating the average delivery ratio and running time
}

class RndGen { // common random number/event generators, to deal with
// 1. event: add new receiver for a group/video
// 2. event: remove a receiver from a group/video
// 3. number: peer's bandwidth
}

class SimException {

}

Interface EventHandler {
void handle() throws SimException; // callback function
}

class Event {
long time; // when this event happens
Node src; // which peer generates this event
Node dst; // whom is destinate of this event
Vector<EventHandler> handlers; //process an event and update states accordingly
int type; // enum, see below
// 1. connectSent: peer 1 makes a connection to peer 2, and add each other into neighbors
// 2. connectArrived: the connect message is received by the peer 2
// 3. acceptSent: the potential sender reply with an accept message
// 4. acceptArrived: the accept message arrives at the connection originator
// 5. requestSent: a receiver sends a high-priority request message to a sender
// 6. requestArrived: a request message gets to a sender
// 7. dataSent: a sender sends a data segment
// 8. dataArrived: a data segment arrives to a receiver
// 9. joinSent: a join message to the tracker
// 10. joinArrived: a join message reaches the tracker
// 11. responseSent: a response message sent by the tracker
// 12. responseArrived: a response message reaches the receiver

// 13. scheduleStarted: a scheduling period started.
//14. bimapSyncSent: the receiver inform all its neighbors what part of the video it is interested currently
in order to get a small bitmap from them to do scheduleing, this message is sent
when the receiver: jumps to view another part of the video or a new neighbor joins.
//15. bitmapSyncArrived: the sender receives the bitmap Synchronization information

//commet: how should we do when a scheduling period expires?
//There are two situations: 1. all scheduled segments arrived; 2. some segments are still in transmission.

void addHandler(Interface EventHandler); // add an additional event handler
void rmvHandler(Interface EventHandler); // remove an additional event handler
}

class EventQueue {
SortedMap<Long, Event> queue; // events sorted on its time
void dispatch(Event event); // sequentially invoke even handlers
}

class Simulator {
long simTime; // elapsed simulation time in msec
EventQueue events; // pending events that will be processed
void dispatchEvent(); // forever loop to process the next event
}

Some comments:
*

</pre>

= Performance metrics for scheduling =

Here are some performance metrics:
<pre>
1. Average delivery ratio: number of on-time scheduled segments over total number of segments to be scheduled
2. Load balance among senders
3. Initial buffering time
4. Time and space complexity of the scheduling algorithm
</pre>

= How to install uml and svn tools in eclipse3.2.x =

<pre>
*. Install emul2
1. Go to http://www.soyatec.com/euml2/installation/, download its free edition. (Select the right version according to your eclipse)
2. Unpack the zip file
3. Open your eclipse, and go to Help -> Software Updates -> Find and install ... -> Search for new features to install -> New local site
then find the unpakced file to install it.
4. How to use: after you creating a new java project, go to File -> New -> Other, select the "UML2 Class Diagram" under the eUML directory,
then you can create a class diagram for your project .

*. Install subclipse
1. Open your eclipse, and go to Help -> Software Updates -> Find and install ... -> Search for new features to install -> New Remote Site
2. Add http://subclipse.tigris.org/update_1.4.x to the URL field and add an arbitrary name to the Name field
3. Follow the instruction to install it.
4. If you encounter an error like "Subclipse Integration for Mylyn 3.x (Optional) (3.0.0) requires plug-in "org.eclipse.mylyn.tasks.core (3.0.0)"
don't worry, just deselect the "Integrations" item and continue to install.
5. Go to Window -> Preferences -> Team. If you can see SVN under the Team tab, congratulations, your installation is done.
6. How to use: right click the project you want to commit, select Tean -> Share project -> SVN, input the URL of
your svn server, then you can import your project to it.
</pre>

Private:psim

2009-03-11T05:42:09Z

Ysa57:

This page documents the development of a discrete event simulator for P2P video streaming applications. This simulator captures important features of data-driven video streaming systems. In particular, it is designed to evaluate: (i) the performance of various segment scheduling algorithms; (ii) the potential of network coding in multi-layer P2P video streaming systems.

= Class Diagrams =

* use long for time/offset in msec, which has a rollover time 24.85 days

<pre>

class Layer { // video layer, we divide each layer into fixed size blocks, we keep track of
// block size and no blocks here
int layer; // layer number it belongs to, set to zero for nonscalable frame
int blockSize; // blocks are fixed size, in bytes
int noBlocks; // how many block here
int dataSize; // aggregate size of all blocks
}

class Frame { // video frame, read from trace file
int no; // serial number
long deadlineOffset; // deadline offset compared to the start of the video, in msec
int totalSize; // total frame size in bytes, including all layers
}

class Segment { // packetized frames
int no; // serial number
Vector<Frame> frames; // reference to included frame
int totalSize; // aggregate size in bytes
Hashtable<Integer, Layer> layers; // reference to layers of this frame, key is the layer id
long getDeadline(); // returns the worst case deadline of this segment (first frame?)
}

class Video { // a media file, shared by a group of peers
String filename; // video trace file path and name
Hashtable<int, Frame> frameTrace; // frames read from the trace file
Hashtable<int, Segment> segmentTrace; // segments generated by the prepareSegments(...)
void prepareSegments(int noFrame); // packetize frames into segment,
// noFrame indicates how many frames should we put in one segment;
// we might implement other packtization schemes later.
}

Interface Node { // a network node, currently can be either a tracker or a peer
}

class Tracker implement Node { // holds a set of groups/videos
Vector<Group> groups; // all the video groups
void addPeer(Group group, Peer peer); // insert a peer into a video group
}

class Peer implements Node { // represent a running peer
int id; // sequential peer id
int ingressBW; // incoming bandwidth in bps
int egressBW; // outgoing bandwidth in bps
Hashtable<Video, Vector<Connection>> senders; // peers that we may send requests to
Hashtable<Video, Vector<Connection>> receivers; // peers that we may send data to
Connection tracker; // control connection to the tracker
Hashtable<Video, VideoBufMap> vBufMaps; // points to the video-level buffer map
void join(Video vide); // the peer joins a group
void leave(Video video); //the peer leaves the group
//here we should call a scheduling algorithm to do the scheduling
void start(Video video); // start downloading a video
void stop(Video video); // stop downloading
}

class Group { // peers that have downloaded or want to download a Video
Video video; // media shared among peers
Vector<Peer> peers; // peers in this group
Vector<Peer> join(Peer peer); // adding a new peer into this group, and return a list of senders
void leave(Peer peer); // removing a peer from this group
}

class Connection { // end to end network link between two peers
Peer peer1; // one end
Peer peer2; // the other
long delay; // transmission delay in msec
int e2eBW; // end-to-end bandwidth in bps
int estimateRate; // estimated rate (maybe historical)
}

class VideoBufMap {
Hashtable<Integer, SegBufMap> sBufMaps; // points to segment bufmap
}

class SegBufMap {
Hashtable<Integer, LayerBufMap> lBufMaps; // points to layer bufmap
}

class LayerBufMap {
boolean avail; // availability bit for this (video, segment, layer) tuple
NCBuf ncBuf; // network coding structure
}

class NCBuf {
boolean servCapibility; // Serving capability of each segment
// show whether this segment is capable of serving other peers(applicable in NC)
int noCodedBl; // No. of encoded blocks for this (video,segment,layer)
BufferedMatrix matrix; // coefficients and their corresponding encoded blocks up to now
}

class BufferedMatrix{ // save coefficients and their corresponding encoded blocks up to now
Vector<Vector<Integer>> coef; // coefficients of the corresponding encoded blocks
Vector <Integer>encodedValue; // encoded blocks
Vector<Integer> decode(); // perform decoding process and return the original blocks of a segment
void encode(); // perform encoding process on blocks of a segment

}

class SysParam{ // system parameters that can be changed in each iteration of the simulation
float portionServ; // after receiving this portion of coded blocks out of total number of blocks, the segment is capable
of serving to others [in case of network coding]
long skipSec; // time duration which is skipped from the current playback point for a new joined peer [in case of
network coding]
float portionEncoding; // a given peer peform encoding among this portion of encoded blocks out of the total coded
blocks that has been received so far
// blocks for encoding will be chosen randomly out of all received encoded blocks [in case of
network coding]
}

// XXX TODO XXX

class SlidingWindow{ // the sliding window which contains all the segments that the receiver is interested currently
// set it to a fixed size, for example 1 minute of videos
// the receiver first inform all its neighbors which part of the video it is interested currently,
// then its neighbors will send their bitmap of that part to the receiver for scheduling
int startOffset; //the offset of the starting segment compared with the start of the video
int endOffset; // the offset of the ending segment compared with the start of the video
double slidingWindowSize(); //get the size of the sliding window
}

class exchangeWindow{ // the exchange window is the front part of the sliding window.
//The unavailable segments in exchange window will be requested by the peer
//usually we set it to a fixed size, for example, 10 seconds of video
// the field of this class is similar to that of the SlidingWindow class
int startOffset;
int endOffset;
void move(); // move the exchange window forward afte a scheduling period and do a next scheduling
double getSlidingWindowSize()
}

interface Scheduler{ // any class wants to do scheduling should implement this interface
void schedule() throws simException; // the scheduling period is specified in the specific scheduling algorithm class
}

class resultItem{ //this class records a scheduling item
int peerID;
int segID;
long startTime; //start time of the peer to transmit this segment
}

class SchedulingResult{ // this class is used to record scheduling results and do some statistics,
// for example, calculate the average delivery rate
Vector<resultItem> item; // result item: <peerID, segID, startTime> (we may write this vector to a log file later)
long runningTime; //running time of the algorithm
long deliveryRatio; //Average delivery ratio

double getDeliveryRatio(); //get the actual average delivery ratio
double getRunningTime(); //get the running time
}

class SEFF implements Scheduler{ // the Serial Earliest Finish-time First scheduling algorithm
SchedulingResult result; // create a schedulingResult object to store the result

void schedule(); //implement the Scheduler interface
void writeResult(); //write scheduling result to the result object of one scheduling period
//including calculating the average delivery ratio and running time
}

class LRF implements Scheduler{ // the Local Rarest First algorithm
SchedulingResult result; // create a schedulingResult object to store the result

void schedule(); //implement the Scheduler interface
void writeResult(); //write scheduling result to the result object of one scheduling period
//including calculating the average delivery ratio and running time
}

class RndGen { // common random number/event generators, to deal with
// 1. event: add new receiver for a group/video
// 2. event: remove a receiver from a group/video
// 3. number: peer's bandwidth
}

class SimException {

}

Interface EventHandler {
void handle() throws SimException; // callback function
}

class Event {
long time; // when this event happens
Node src; // which peer generates this event
Node dst; // whom is destinate of this event
Vector<EventHandler> handlers; //process an event and update states accordingly
int type; // enum, see below
// 1. connectSent: peer 1 makes a connection to peer 2, and add each other into neighbors
// 2. connectArrived: the connect message is received by the peer 2
// 3. acceptSent: the potential sender reply with an accept message
// 4. acceptArrived: the accept message arrives at the connection originator
// 5. requestSent: a receiver sends a high-priority request message to a sender
// 6. requestArrived: a request message gets to a sender
// 7. dataSent: a sender sends a data segment
// 8. dataArrived: a data segment arrives to a receiver
// 9. joinSent: a join message to the tracker
// 10. joinArrived: a join message reaches the tracker
// 11. responseSent: a response message sent by the tracker
// 12. responseArrived: a response message reaches the receiver

// 13. scheduleStarted: a scheduling period started.
//14. bimapSyncSent: the receiver inform all its neighbors what part of the video it is interested currently
in order to get a small bitmap from them to do scheduleing, this message is sent
when the receiver: jumps to view another part of the video or a new neighbor joins.
//15. bitmapSyncArrived: the sender receives the bitmap Synchronization information

//commet: how should we do when a scheduling period expires?
//There are two situations: 1. all scheduled segments arrived; 2. some segments are still in transmission.

void addHandler(Interface EventHandler); // add an additional event handler
void rmvHandler(Interface EventHandler); // remove an additional event handler
}

class EventQueue {
SortedMap<Long, Event> queue; // events sorted on its time
void dispatch(Event event); // sequentially invoke even handlers
}

class Simulator {
long simTime; // elapsed simulation time in msec
EventQueue events; // pending events that will be processed
void dispatchEvent(); // forever loop to process the next event
}

Some comments:
*

</pre>

= Performance metrics for scheduling =

Here are some performance metrics:
<pre>
1. Average delivery ratio: number of on-time scheduled segments over total number of segments to be scheduled
2. Load balance among senders
3. Initial buffering time
4. Time and space complexity of the scheduling algorithm
</pre>

= How to install uml and svn tools in eclipse3.2.x =

<pre>
*. Install emul2
1. Go to http://www.soyatec.com/euml2/installation/, download its free edition. (Select the right version according to your eclipse)
2. Unpack the zip file
3. Open your eclipse, and go to Help -> Software Updates -> Find and install ... -> Search for new features to install -> New local site
then find the unpakced file to install it.
4. How to use: after you create a new java project, go to File -> New -> Other, select the "UML2 Class Diagram" under the eUML directory,
then you can create a class diagram for your project .

*. Install subclipse
1. Open your eclipse, and go to Help -> Software Updates -> Find and install ... -> Search for new features to install -> New Remote Site
2. Add http://subclipse.tigris.org/update_1.4.x to the URL field and add an arbitrary name to the Name field
3. Follow the instruction to install it.
4. If you encounter an error like "Subclipse Integration for Mylyn 3.x (Optional) (3.0.0) requires plug-in "org.eclipse.mylyn.tasks.core (3.0.0)"
don't worry, just deselect the "Integrations" item and continue to install.
5. Go to Window -> Preferences -> Team. If you can see SVN under the Team tab, congratulations, your installation is done.
6. How to use: right click the project you want to commit, select Tean -> Share project -> SVN, input the URL of
your svn server, then you can import your project to it.
</pre>

Private:psim

2009-03-11T05:33:42Z

Ysa57:

This page documents the development of a discrete event simulator for P2P video streaming applications. This simulator captures important features of data-driven video streaming systems. In particular, it is designed to evaluate: (i) the performance of various segment scheduling algorithms; (ii) the potential of network coding in multi-layer P2P video streaming systems.

= Class Diagrams =

* use long for time/offset in msec, which has a rollover time 24.85 days

<pre>

class Layer { // video layer, we divide each layer into fixed size blocks, we keep track of
// block size and no blocks here
int layer; // layer number it belongs to, set to zero for nonscalable frame
int blockSize; // blocks are fixed size, in bytes
int noBlocks; // how many block here
int dataSize; // aggregate size of all blocks
}

class Frame { // video frame, read from trace file
int no; // serial number
long deadlineOffset; // deadline offset compared to the start of the video, in msec
int totalSize; // total frame size in bytes, including all layers
}

class Segment { // packetized frames
int no; // serial number
Vector<Frame> frames; // reference to included frame
int totalSize; // aggregate size in bytes
Hashtable<Integer, Layer> layers; // reference to layers of this frame, key is the layer id
long getDeadline(); // returns the worst case deadline of this segment (first frame?)
}

class Video { // a media file, shared by a group of peers
String filename; // video trace file path and name
Hashtable<int, Frame> frameTrace; // frames read from the trace file
Hashtable<int, Segment> segmentTrace; // segments generated by the prepareSegments(...)
void prepareSegments(int noFrame); // packetize frames into segment,
// noFrame indicates how many frames should we put in one segment;
// we might implement other packtization schemes later.
}

Interface Node { // a network node, currently can be either a tracker or a peer
}

class Tracker implement Node { // holds a set of groups/videos
Vector<Group> groups; // all the video groups
void addPeer(Group group, Peer peer); // insert a peer into a video group
}

class Peer implements Node { // represent a running peer
int id; // sequential peer id
int ingressBW; // incoming bandwidth in bps
int egressBW; // outgoing bandwidth in bps
Hashtable<Video, Vector<Connection>> senders; // peers that we may send requests to
Hashtable<Video, Vector<Connection>> receivers; // peers that we may send data to
Connection tracker; // control connection to the tracker
Hashtable<Video, VideoBufMap> vBufMaps; // points to the video-level buffer map
void join(Video vide); // the peer joins a group
void leave(Video video); //the peer leaves the group
//here we should call a scheduling algorithm to do the scheduling
void start(Video video); // start downloading a video
void stop(Video video); // stop downloading
}

class Group { // peers that have downloaded or want to download a Video
Video video; // media shared among peers
Vector<Peer> peers; // peers in this group
Vector<Peer> join(Peer peer); // adding a new peer into this group, and return a list of senders
void leave(Peer peer); // removing a peer from this group
}

class Connection { // end to end network link between two peers
Peer peer1; // one end
Peer peer2; // the other
long delay; // transmission delay in msec
int e2eBW; // end-to-end bandwidth in bps
int estimateRate; // estimated rate (maybe historical)
}

class VideoBufMap {
Hashtable<Integer, SegBufMap> sBufMaps; // points to segment bufmap
}

class SegBufMap {
Hashtable<Integer, LayerBufMap> lBufMaps; // points to layer bufmap
}

class LayerBufMap {
boolean avail; // availability bit for this (video, segment, layer) tuple
NCBuf ncBuf; // network coding structure
}

class NCBuf {
boolean servCapibility; // Serving capability of each segment
// show whether this segment is capable of serving other peers(applicable in NC)
int noCodedBl; // No. of encoded blocks for this (video,segment,layer)
BufferedMatrix matrix; // coefficients and their corresponding encoded blocks up to now
}

class BufferedMatrix{ // save coefficients and their corresponding encoded blocks up to now
Vector<Vector<Integer>> coef; // coefficients of the corresponding encoded blocks
Vector <Integer>encodedValue; // encoded blocks
Vector<Integer> decode(); // perform decoding process and return the original blocks of a segment
void encode(); // perform encoding process on blocks of a segment

}

class SysParam{ // system parameters that can be changed in each iteration of the simulation
float portionServ; // after receiving this portion of coded blocks out of total number of blocks, the segment is capable
of serving to others [in case of network coding]
long skipSec; // time duration which is skipped from the current playback point for a new joined peer [in case of
network coding]
float portionEncoding; // a given peer peform encoding among this portion of encoded blocks out of the total coded
blocks that has been received so far
// blocks for encoding will be chosen randomly out of all received encoded blocks [in case of
network coding]
}

// XXX TODO XXX

class SlidingWindow{ // the sliding window which contains all the segments that the receiver is interested currently
// set it to a fixed size, for example 1 minute of videos
// the receiver first inform all its neighbors which part of the video it is interested currently,
// then its neighbors will send their bitmap of that part to the receiver for scheduling
int startOffset; //the offset of the starting segment compared with the start of the video
int endOffset; // the offset of the ending segment compared with the start of the video
double slidingWindowSize(); //get the size of the sliding window
}

class exchangeWindow{ // the exchange window is the front part of the sliding window.
//The unavailable segments in exchange window will be requested by the peer
//usually we set it to a fixed size, for example, 10 seconds of video
// the field of this class is similar to that of the SlidingWindow class
int startOffset;
int endOffset;
void move(); // move the exchange window forward afte a scheduling period and do a next scheduling
double getSlidingWindowSize()
}

interface Scheduler{ // any class wants to do scheduling should implement this interface
void schedule() throws simException; // the scheduling period is specified in the specific scheduling algorithm class
}

class resultItem{ //this class records a scheduling item
int peerID;
int segID;
long startTime; //start time of the peer to transmit this segment
}

class SchedulingResult{ // this class is used to record scheduling results and do some statistics,
// for example, calculate the average delivery rate
Vector<resultItem> item; // result item: <peerID, segID, startTime> (we may write this vector to a log file later)
long runningTime; //running time of the algorithm
long deliveryRatio; //Average delivery ratio

double getDeliveryRatio(); //get the actual average delivery ratio
double getRunningTime(); //get the running time
}

class SEFF implements Scheduler{ // the Serial Earliest Finish-time First scheduling algorithm
SchedulingResult result; // create a schedulingResult object to store the result

void schedule(); //implement the Scheduler interface
void writeResult(); //write scheduling result to the result object of one scheduling period
//including calculating the average delivery ratio and running time
}

class LRF implements Scheduler{ // the Local Rarest First algorithm
SchedulingResult result; // create a schedulingResult object to store the result

void schedule(); //implement the Scheduler interface
void writeResult(); //write scheduling result to the result object of one scheduling period
//including calculating the average delivery ratio and running time
}

class RndGen { // common random number/event generators, to deal with
// 1. event: add new receiver for a group/video
// 2. event: remove a receiver from a group/video
// 3. number: peer's bandwidth
}

class SimException {

}

Interface EventHandler {
void handle() throws SimException; // callback function
}

class Event {
long time; // when this event happens
Node src; // which peer generates this event
Node dst; // whom is destinate of this event
Vector<EventHandler> handlers; //process an event and update states accordingly
int type; // enum, see below
// 1. connectSent: peer 1 makes a connection to peer 2, and add each other into neighbors
// 2. connectArrived: the connect message is received by the peer 2
// 3. acceptSent: the potential sender reply with an accept message
// 4. acceptArrived: the accept message arrives at the connection originator
// 5. requestSent: a receiver sends a high-priority request message to a sender
// 6. requestArrived: a request message gets to a sender
// 7. dataSent: a sender sends a data segment
// 8. dataArrived: a data segment arrives to a receiver
// 9. joinSent: a join message to the tracker
// 10. joinArrived: a join message reaches the tracker
// 11. responseSent: a response message sent by the tracker
// 12. responseArrived: a response message reaches the receiver

// 13. scheduleStarted: a scheduling period started.
//14. bimapSyncSent: the receiver inform all its neighbors what part of the video it is interested currently
in order to get a small bitmap from them to do scheduleing, this message is sent
when the receiver: jumps to view another part of the video or a new neighbor joins.
//15. bitmapSyncArrived: the sender receives the bitmap Synchronization information

//commet: how should we do when a scheduling period expires?
//There are two situations: 1. all scheduled segments arrived; 2. some segments are still in transmission.

void addHandler(Interface EventHandler); // add an additional event handler
void rmvHandler(Interface EventHandler); // remove an additional event handler
}

class EventQueue {
SortedMap<Long, Event> queue; // events sorted on its time
void dispatch(Event event); // sequentially invoke even handlers
}

class Simulator {
long simTime; // elapsed simulation time in msec
EventQueue events; // pending events that will be processed
void dispatchEvent(); // forever loop to process the next event
}

Some comments:
*

</pre>

= Performance metrics for scheduling =

Here are some performance metrics:
<pre>
1. Average delivery ratio: number of on-time scheduled segments over total number of segments to be scheduled
2. Load balance among senders
3. Initial buffering time
4. Time and space complexity of the scheduling algorithm
</pre>

= How to install uml and svn tools in eclipse3.2.x =

<pre>
*. Install emul2
1. Go to http://www.soyatec.com/euml2/installation/, download its free edition. (Select the right version according to your eclipse)
2. Unpack the zip file
3. Open your eclipse, and go to Help -> Software Updates -> Find and install ... -> Search for new features to install -> New local site
then find the unpakced file to install it.

*. Install subclipse
1. Open your eclipse, and go to Help -> Software Updates -> Find and install ... -> Search for new features to install -> New Remote Site
2. Add http://subclipse.tigris.org/update_1.4.x to the URL field and add an arbitrary name to the Name field
3. Follow the instruction to install it.
4. If you encounter an error like "Subclipse Integration for Mylyn 3.x (Optional) (3.0.0) requires plug-in "org.eclipse.mylyn.tasks.core (3.0.0)"
don't worry, just deselect the "Integrations" item and continue to install.
5. Go to Window -> Preferences -> Team. If you can see SVN under the Team tab, congratulations, your are done.

</pre>

Private:psim

2009-03-11T05:26:25Z

Ysa57:

This page documents the development of a discrete event simulator for P2P video streaming applications. This simulator captures important features of data-driven video streaming systems. In particular, it is designed to evaluate: (i) the performance of various segment scheduling algorithms; (ii) the potential of network coding in multi-layer P2P video streaming systems.

= Class Diagrams =

* use long for time/offset in msec, which has a rollover time 24.85 days

<pre>

class Layer { // video layer, we divide each layer into fixed size blocks, we keep track of
// block size and no blocks here
int layer; // layer number it belongs to, set to zero for nonscalable frame
int blockSize; // blocks are fixed size, in bytes
int noBlocks; // how many block here
int dataSize; // aggregate size of all blocks
}

class Frame { // video frame, read from trace file
int no; // serial number
long deadlineOffset; // deadline offset compared to the start of the video, in msec
int totalSize; // total frame size in bytes, including all layers
}

class Segment { // packetized frames
int no; // serial number
Vector<Frame> frames; // reference to included frame
int totalSize; // aggregate size in bytes
Hashtable<Integer, Layer> layers; // reference to layers of this frame, key is the layer id
long getDeadline(); // returns the worst case deadline of this segment (first frame?)
}

class Video { // a media file, shared by a group of peers
String filename; // video trace file path and name
Hashtable<int, Frame> frameTrace; // frames read from the trace file
Hashtable<int, Segment> segmentTrace; // segments generated by the prepareSegments(...)
void prepareSegments(int noFrame); // packetize frames into segment,
// noFrame indicates how many frames should we put in one segment;
// we might implement other packtization schemes later.
}

Interface Node { // a network node, currently can be either a tracker or a peer
}

class Tracker implement Node { // holds a set of groups/videos
Vector<Group> groups; // all the video groups
void addPeer(Group group, Peer peer); // insert a peer into a video group
}

class Peer implements Node { // represent a running peer
int id; // sequential peer id
int ingressBW; // incoming bandwidth in bps
int egressBW; // outgoing bandwidth in bps
Hashtable<Video, Vector<Connection>> senders; // peers that we may send requests to
Hashtable<Video, Vector<Connection>> receivers; // peers that we may send data to
Connection tracker; // control connection to the tracker
Hashtable<Video, VideoBufMap> vBufMaps; // points to the video-level buffer map
void join(Video vide); // the peer joins a group
void leave(Video video); //the peer leaves the group
//here we should call a scheduling algorithm to do the scheduling
void start(Video video); // start downloading a video
void stop(Video video); // stop downloading
}

class Group { // peers that have downloaded or want to download a Video
Video video; // media shared among peers
Vector<Peer> peers; // peers in this group
Vector<Peer> join(Peer peer); // adding a new peer into this group, and return a list of senders
void leave(Peer peer); // removing a peer from this group
}

class Connection { // end to end network link between two peers
Peer peer1; // one end
Peer peer2; // the other
long delay; // transmission delay in msec
int e2eBW; // end-to-end bandwidth in bps
int estimateRate; // estimated rate (maybe historical)
}

class VideoBufMap {
Hashtable<Integer, SegBufMap> sBufMaps; // points to segment bufmap
}

class SegBufMap {
Hashtable<Integer, LayerBufMap> lBufMaps; // points to layer bufmap
}

class LayerBufMap {
boolean avail; // availability bit for this (video, segment, layer) tuple
NCBuf ncBuf; // network coding structure
}

class NCBuf {
boolean servCapibility; // Serving capability of each segment
// show whether this segment is capable of serving other peers(applicable in NC)
int noCodedBl; // No. of encoded blocks for this (video,segment,layer)
BufferedMatrix matrix; // coefficients and their corresponding encoded blocks up to now
}

class BufferedMatrix{ // save coefficients and their corresponding encoded blocks up to now
Vector<Vector<Integer>> coef; // coefficients of the corresponding encoded blocks
Vector <Integer>encodedValue; // encoded blocks
Vector<Integer> decode(); // perform decoding process and return the original blocks of a segment
void encode(); // perform encoding process on blocks of a segment

}

class SysParam{ // system parameters that can be changed in each iteration of the simulation
float portionServ; // after receiving this portion of coded blocks out of total number of blocks, the segment is capable
of serving to others [in case of network coding]
long skipSec; // time duration which is skipped from the current playback point for a new joined peer [in case of
network coding]
float portionEncoding; // a given peer peform encoding among this portion of encoded blocks out of the total coded
blocks that has been received so far
// blocks for encoding will be chosen randomly out of all received encoded blocks [in case of
network coding]
}

// XXX TODO XXX

class SlidingWindow{ // the sliding window which contains all the segments that the receiver is interested currently
// set it to a fixed size, for example 1 minute of videos
// the receiver first inform all its neighbors which part of the video it is interested currently,
// then its neighbors will send their bitmap of that part to the receiver for scheduling
int startOffset; //the offset of the starting segment compared with the start of the video
int endOffset; // the offset of the ending segment compared with the start of the video
double slidingWindowSize(); //get the size of the sliding window
}

class exchangeWindow{ // the exchange window is the front part of the sliding window.
//The unavailable segments in exchange window will be requested by the peer
//usually we set it to a fixed size, for example, 10 seconds of video
// the field of this class is similar to that of the SlidingWindow class
int startOffset;
int endOffset;
void move(); // move the exchange window forward afte a scheduling period and do a next scheduling
double getSlidingWindowSize()
}

interface Scheduler{ // any class wants to do scheduling should implement this interface
void schedule() throws simException; // the scheduling period is specified in the specific scheduling algorithm class
}

class resultItem{ //this class records a scheduling item
int peerID;
int segID;
long startTime; //start time of the peer to transmit this segment
}

class SchedulingResult{ // this class is used to record scheduling results and do some statistics,
// for example, calculate the average delivery rate
Vector<resultItem> item; // result item: <peerID, segID, startTime> (we may write this vector to a log file later)
long runningTime; //running time of the algorithm
long deliveryRatio; //Average delivery ratio

double getDeliveryRatio(); //get the actual average delivery ratio
double getRunningTime(); //get the running time
}

class SEFF implements Scheduler{ // the Serial Earliest Finish-time First scheduling algorithm
SchedulingResult result; // create a schedulingResult object to store the result

void schedule(); //implement the Scheduler interface
void writeResult(); //write scheduling result to the result object of one scheduling period
//including calculating the average delivery ratio and running time
}

class LRF implements Scheduler{ // the Local Rarest First algorithm
SchedulingResult result; // create a schedulingResult object to store the result

void schedule(); //implement the Scheduler interface
void writeResult(); //write scheduling result to the result object of one scheduling period
//including calculating the average delivery ratio and running time
}

class RndGen { // common random number/event generators, to deal with
// 1. event: add new receiver for a group/video
// 2. event: remove a receiver from a group/video
// 3. number: peer's bandwidth
}

class SimException {

}

Interface EventHandler {
void handle() throws SimException; // callback function
}

class Event {
long time; // when this event happens
Node src; // which peer generates this event
Node dst; // whom is destinate of this event
Vector<EventHandler> handlers; //process an event and update states accordingly
int type; // enum, see below
// 1. connectSent: peer 1 makes a connection to peer 2, and add each other into neighbors
// 2. connectArrived: the connect message is received by the peer 2
// 3. acceptSent: the potential sender reply with an accept message
// 4. acceptArrived: the accept message arrives at the connection originator
// 5. requestSent: a receiver sends a high-priority request message to a sender
// 6. requestArrived: a request message gets to a sender
// 7. dataSent: a sender sends a data segment
// 8. dataArrived: a data segment arrives to a receiver
// 9. joinSent: a join message to the tracker
// 10. joinArrived: a join message reaches the tracker
// 11. responseSent: a response message sent by the tracker
// 12. responseArrived: a response message reaches the receiver

// 13. scheduleStarted: a scheduling period started.
//14. bimapSyncSent: the receiver inform all its neighbors what part of the video it is interested currently
in order to get a small bitmap from them to do scheduleing, this message is sent
when the receiver: jumps to view another part of the video or a new neighbor joins.
//15. bitmapSyncArrived: the sender receives the bitmap Synchronization information

//commet: how should we do when a scheduling period expires?
//There are two situations: 1. all scheduled segments arrived; 2. some segments are still in transmission.

void addHandler(Interface EventHandler); // add an additional event handler
void rmvHandler(Interface EventHandler); // remove an additional event handler
}

class EventQueue {
SortedMap<Long, Event> queue; // events sorted on its time
void dispatch(Event event); // sequentially invoke even handlers
}

class Simulator {
long simTime; // elapsed simulation time in msec
EventQueue events; // pending events that will be processed
void dispatchEvent(); // forever loop to process the next event
}

Some comments:
*

</pre>

= Performance metrics for scheduling =

Here are some performance metrics:
<pre>
1. Average delivery ratio: number of on-time scheduled segments over total number of segments to be scheduled
2. Load balance among senders
3. Initial buffering time
4. Time and space complexity of the scheduling algorithm
</pre>

= How to install uml and svn tools in eclipse3.2.x =

<pre>
*. Install emul2
1. Go to http://www.soyatec.com/euml2/installation/, download its free edition. (Select the right version according to your eclipse)
2. Unpack the zip file
3. Open your eclipse, and go to Help -> Software Updates -> Find and install ... -> Search for new features to install -> New local site
then find the unpakced file to install it.

*. Install subclipse
1. Open your eclipse, and go to Help -> Software Updates -> Find and install ... -> Search for new features to install -> New Remote Site
2. Add http://subclipse.tigris.org/update_1.4.x to the URL field and add an arbitrary name to the Name field
3. Follow the instruction to install it.
4. If you encounter an error like "Subclipse Integration for Mylyn 3.x (Optional) (3.0.0) requires plug-in "org.eclipse.mylyn.tasks.core (3.0.0)"
don't worry, just deselect the "Integrations" item and continue to install.

</pre>

Private:psim

2009-03-10T22:12:03Z

Ysa57:

This page documents the development of a discrete event simulator for P2P video streaming applications. This simulator captures important features of data-driven video streaming systems. In particular, it is designed to evaluate: (i) the performance of various segment scheduling algorithms; (ii) the potential of network coding in multi-layer P2P video streaming systems.

= Class Diagrams =

* use long for time/offset in msec, which has a rollover time 24.85 days

<pre>

class Layer { // video layer, we divide each layer into fixed size blocks, we keep track of
// block size and no blocks here
int layer; // layer number it belongs to, set to zero for nonscalable frame
int blockSize; // blocks are fixed size, in bytes
int noBlocks; // how many block here
int dataSize; // aggregate size of all blocks
}

class Frame { // video frame, read from trace file
int no; // serial number
long deadlineOffset; // deadline offset compared to the start of the video, in msec
int totalSize; // total frame size in bytes, including all layers
}

class Segment { // packetized frames
int no; // serial number
Vector<Frame> frames; // reference to included frame
int totalSize; // aggregate size in bytes
Hashtable<Integer, Layer> layers; // reference to layers of this frame, key is the layer id
long getDeadline(); // returns the worst case deadline of this segment (first frame?)
}

class Video { // a media file, shared by a group of peers
String filename; // video trace file path and name
Hashtable<int, Frame> frameTrace; // frames read from the trace file
Hashtable<int, Segment> segmentTrace; // segments generated by the prepareSegments(...)
void prepareSegments(int noFrame); // packetize frames into segment,
// noFrame indicates how many frames should we put in one segment;
// we might implement other packtization schemes later.
}

Interface Node { // a network node, currently can be either a tracker or a peer
}

class Tracker implement Node { // holds a set of groups/videos
Vector<Group> groups; // all the video groups
void addPeer(Group group, Peer peer); // insert a peer into a video group
}

class Peer implements Node { // represent a running peer
int id; // sequential peer id
int ingressBW; // incoming bandwidth in bps
int egressBW; // outgoing bandwidth in bps
Hashtable<Video, Vector<Connection>> senders; // peers that we may send requests to
Hashtable<Video, Vector<Connection>> receivers; // peers that we may send data to
Connection tracker; // control connection to the tracker
Hashtable<Video, VideoBufMap> vBufMaps; // points to the video-level buffer map
void join(Video vide); // the peer joins a group
void leave(Video video); //the peer leaves the group
//here we should call a scheduling algorithm to do the scheduling
void start(Video video); // start downloading a video
void stop(Video video); // stop downloading
}

class Group { // peers that have downloaded or want to download a Video
Video video; // media shared among peers
Vector<Peer> peers; // peers in this group
Vector<Peer> join(Peer peer); // adding a new peer into this group, and return a list of senders
void leave(Peer peer); // removing a peer from this group
}

class Connection { // end to end network link between two peers
Peer peer1; // one end
Peer peer2; // the other
long delay; // transmission delay in msec
int e2eBW; // end-to-end bandwidth in bps
int estimateRate; // estimated rate (maybe historical)
}

class VideoBufMap {
Hashtable<Integer, SegBufMap> sBufMaps; // points to segment bufmap
}

class SegBufMap {
Hashtable<Integer, LayerBufMap> lBufMaps; // points to layer bufmap
}

class LayerBufMap {
boolean avail; // availability bit for this (video, segment, layer) tuple
NCBuf ncBuf; // network coding structure
}

class NCBuf {
boolean servCapibility; // Serving capability of each segment
// show whether this segment is capable of serving other peers(applicable in NC)
int noCodedBl; // No. of encoded blocks for this (video,segment,layer)
BufferedMatrix matrix; // coefficients and their corresponding encoded blocks up to now
}

class BufferedMatrix{ // save coefficients and their corresponding encoded blocks up to now
Vector<Vector<Integer>> coef; // coefficients of the corresponding encoded blocks
Vector <Integer>encodedValue; // encoded blocks
Vector<Integer> decode(); // perform decoding process and return the original blocks of a segment
void encode(); // perform encoding process on blocks of a segment

}

class SysParam{ // system parameters that can be changed in each iteration of the simulation
float portionServ; // after receiving this portion of coded blocks out of total number of blocks, the segment is capable
// of serving to others [in case of network coding]
long skipSec; // time duration which is skipped from the current playback point for a new joined peer [in case of
// network coding]
}

// XXX TODO XXX

class SlidingWindow{ // the sliding window which contains all the segments that the receiver is interested currently
// set it to a fixed size, for example 1 minute of videos
// the receiver first inform all its neighbors which part of the video it is interested currently,
// then its neighbors will send their bitmap of that part to the receiver for scheduling
int startOffset; //the offset of the starting segment compared with the start of the video
int endOffset; // the offset of the ending segment compared with the start of the video
double slidingWindowSize(); //get the size of the sliding window
}

class exchangeWindow{ // the exchange window is the front part of the sliding window.
//The unavailable segments in exchange window will be requested by the peer
//usually we set it to a fixed size, for example, 10 seconds of video
// the field of this class is similar to that of the SlidingWindow class
int startOffset;
int endOffset;
void move(); // move the exchange window forward afte a scheduling period and do a next scheduling
double getSlidingWindowSize()
}

interface Scheduler{ // any class wants to do scheduling should implement this interface
void schedule() throws simException; // the scheduling period is specified in the specific scheduling algorithm class
}

class resultItem{ //this class records a scheduling item
int peerID;
int segID;
long startTime; //start time of the peer to transmit this segment
}

class SchedulingResult{ // this class is used to record scheduling results and do some statistics,
// for example, calculate the average delivery rate
Vector<resultItem> item; // result item: <peerID, segID, startTime> (we may write this vector to a log file later)
long runningTime; //running time of the algorithm
long deliveryRatio; //Average delivery ratio

double getDeliveryRatio(); //get the actual average delivery ratio
double getRunningTime(); //get the running time
}

class SEFF implements Scheduler{ // the Serial Earliest Finish-time First scheduling algorithm
SchedulingResult result; // create a schedulingResult object to store the result

void schedule(); //implement the Scheduler interface
void writeResult(); //write scheduling result to the result object of one scheduling period
//including calculating the average delivery ratio and running time
}

class LRF implements Scheduler{ // the Local Rarest First algorithm
SchedulingResult result; // create a schedulingResult object to store the result

void schedule(); //implement the Scheduler interface
void writeResult(); //write scheduling result to the result object of one scheduling period
//including calculating the average delivery ratio and running time
}

class RndGen { // common random number/event generators, to deal with
// 1. event: add new receiver for a group/video
// 2. event: remove a receiver from a group/video
// 3. number: peer's bandwidth
}

class SimException {

}

Interface EventHandler {
void handle() throws SimException; // callback function
}

class Event {
long time; // when this event happens
Node src; // which peer generates this event
Node dst; // whom is destinate of this event
Vector<EventHandler> handlers; //process an event and update states accordingly
int type; // enum, see below
// 1. connectSent: peer 1 makes a connection to peer 2, and add each other into neighbors
// 2. connectArrived: the connect message is received by the peer 2
// 3. acceptSent: the potential sender reply with an accept message
// 4. acceptArrived: the accept message arrives at the connection originator
// 5. requestSent: a receiver sends a high-priority request message to a sender
// 6. requestArrived: a request message gets to a sender
// 7. dataSent: a sender sends a data segment
// 8. dataArrived: a data segment arrives to a receiver
// 9. joinSent: a join message to the tracker
// 10. joinArrived: a join message reaches the tracker
// 11. responseSent: a response message sent by the tracker
// 12. responseArrived: a response message reaches the receiver

// 13. scheduleStarted: a scheduling period started.
//14. bimapSyncSent: the receiver inform all its neighbors what part of the video it is interested currently
in order to get a small bitmap from them to do scheduleing, this message is sent
when the receiver: jumps to view another part of the video or a new neighbor joins.
//15. bitmapSyncArrived: the sender receives the bitmap Synchronization information

//commet: how should we do when a scheduling period expires?
//There are two situations: 1. all scheduled segments arrived; 2. some segments are still in transmission.

void addHandler(Interface EventHandler); // add an additional event handler
void rmvHandler(Interface EventHandler); // remove an additional event handler
}

class EventQueue {
SortedMap<Long, Event> queue; // events sorted on its time
void dispatch(Event event); // sequentially invoke even handlers
}

class Simulator {
long simTime; // elapsed simulation time in msec
EventQueue events; // pending events that will be processed
void dispatchEvent(); // forever loop to process the next event
}

Some comments:
*

</pre>

= Performance metrics for scheduling =

Here are some performance metrics:
<pre>
1. Average delivery ratio: number of on-time scheduled segments over total number of segments to be scheduled
2. Load balance among senders
3. Initial buffering time
4. Time and space complexity of the scheduling algorithm
</pre>

Private:psim

2009-03-10T21:47:44Z

Ysa57:

This page documents the development of a discrete event simulator for P2P video streaming applications. This simulator captures important features of data-driven video streaming systems. In particular, it is designed to evaluate: (i) the performance of various segment scheduling algorithms; (ii) the potential of network coding in multi-layer P2P video streaming systems.

= Class Diagrams =

* use long for time/offset in msec, which has a rollover time 24.85 days

<pre>

class Layer { // video layer, we divide each layer into fixed size blocks, we keep track of
// block size and no blocks here
int layer; // layer number it belongs to, set to zero for nonscalable frame
int blockSize; // blocks are fixed size, in bytes
int noBlocks; // how many block here
int dataSize; // aggregate size of all blocks
}

class Frame { // video frame, read from trace file
int no; // serial number
long deadlineOffset; // deadline offset compared to the start of the video, in msec
int totalSize; // total frame size in bytes, including all layers
}

class Segment { // packetized frames
int no; // serial number
Vector<Frame> frames; // reference to included frame
int totalSize; // aggregate size in bytes
Hashtable<Integer, Layer> layers; // reference to layers of this frame, key is the layer id
long getDeadline(); // returns the worst case deadline of this segment (first frame?)
}

class Video { // a media file, shared by a group of peers
String filename; // video trace file path and name
Hashtable<int, Frame> frameTrace; // frames read from the trace file
Hashtable<int, Segment> segmentTrace; // segments generated by the prepareSegments(...)
void prepareSegments(int noFrame); // packetize frames into segment,
// noFrame indicates how many frames should we put in one segment;
// we might implement other packtization schemes later.
}

Interface Node { // a network node, currently can be either a tracker or a peer
}

class Tracker implement Node { // holds a set of groups/videos
Vector<Group> groups; // all the video groups
void addPeer(Group group, Peer peer); // insert a peer into a video group
}

class Peer implement Node { // represent a running peer
int id; // sequential peer id
int ingressBW; // incoming bandwidth in bps
int egressBW; // outgoing bandwidth in bps
Hashtable<Video, Vector<Connection>> senders; // peers that we may send requests to
Hashtable<Video, Vector<Connection>> receivers; // peers that we may send data to
Connection tracker; // control connection to the tracker
Hashtable<Video, VideoBufMap> vBufMaps; // points to the video-level buffer map
void start(Video video); // start downloading a video
void stop(Video video); // stop downloading
}

class Group { // peers that have downloaded or want to download a Video
Video video; // media shared among peers
Vector<Peer> peers; // peers in this group
Vector<Peer> join(Peer peer); // adding a new peer into this group, and return a list of senders
void leave(Peer peer); // removing a peer from this group
}

class Connection { // end to end network link between two peers
Peer peer1; // one end
Peer peer2; // the other
long delay; // transmission delay in msec
int e2eBW; // end-to-end bandwidth in bps
int estimateRate; // estimated rate (maybe historical)
}

class VideoBufMap {
Hashtable<Integer, SegBufMap> sBufMaps; // points to segment bufmap
}

class SegBufMap {
Hashtable<Integer, LayerBufMap> lBufMaps; // points to layer bufmap
}

class LayerBufMap {
boolean avail; // availability bit for this (video, segment, layer) tuple
NCBuf ncBuf; // network coding structure
}

class NCBuf {
boolean servCapibility; // Serving capability of each segment
// show whether this segment is capable of serving other peers(applicable in NC)
int noCodedBl; // No. of encoded blocks for this (video,segment,layer)
BufferedMatrix matrix; // coefficients and their corresponding encoded blocks up to now
}

class BufferedMatrix{ // save coefficients and their corresponding encoded blocks up to now
Vector<Vector<Integer>> coef; // coefficients of the corresponding encoded blocks
Vector <Integer>encodedValue; // encoded blocks
Vector<Integer> decode(); // perform decoding process and return the original blocks of a segment
void encode(); // perform encoding process on blocks of a segment

}

class SysParam{ // system parameters that can be changed in each iteration of the simulation
float portionServ; // after receiving this portion of coded blocks out of total number of blocks, the segment is capable
// of serving to others [in case of network coding]
long skipSec; // time duration which is skipped from the current playback point for a new joined peer [in case of
// network coding]
}

// XXX TODO XXX

class SlidingWindow{ // the sliding window which contains all the segments that the receiver is interested currently
// set it to a fixed size, for example 1 minute of videos
// the receiver first inform all its neighbors which part of the video it is interested currently,
// then its neighbors will send their bitmap of that part to the receiver for scheduling
int startOffset; //the offset of the starting segment compared with the start of the video
int endOffset; // the offset of the ending segment compared with the start of the video
double slidingWindowSize(); //get the size of the sliding window
}

class exchangeWindow{ // the exchange window is the front part of the sliding window.
//The unavailable segments in exchange window will be requested by the peer
//usually we set it to a fixed size, for example, 10 seconds of video
// the field of this class is similar to that of the SlidingWindow class
int startOffset;
int endOffset;
void move(); // move the exchange window forward afte a scheduling period and do a next scheduling
double getSlidingWindowSize()
}

interface Scheduler{ // any class wants to do scheduling should implement this interface
void schedule() throws simException; // the scheduling period is specified in the specific scheduling algorithm class
}

class resultItem{ //this class records a scheduling item
int peerID;
int segID;
long startTime; //start time of the peer to transmit this segment
}

class SchedulingResult{ // this class is used to record scheduling results and do some statistics,
// for example, calculate the average delivery rate
Vector<resultItem> item; // result item: <peerID, segID, startTime> (we may write this vector to a log file later)
long runningTime; //running time of the algorithm
long deliveryRatio; //Average delivery ratio

double getDeliveryRatio(); //get the actual average delivery ratio
double getRunningTime(); //get the running time
}

class SEFF implements Scheduler{ // the Serial Earliest Finish-time First scheduling algorithm
SchedulingResult result; // create a schedulingResult object to store the result

void schedule(); //implement the Scheduler interface
void writeResult(SchedulingResult); //write scheduling result to the result object of one scheduling period
//including calculating the average delivery ratio and running time
}

class LRF implements Scheduler{ // the Local Rarest First algorithm
SchedulingResult result; // create a schedulingResult object to store the result

void schedule(); //implement the Scheduler interface
void writeResult(SchedulingResult); //write scheduling result to the result object of one scheduling period
//including calculating the average delivery ratio and running time
}

class RndGen { // common random number/event generators, to deal with
// 1. event: add new receiver for a group/video
// 2. event: remove a receiver from a group/video
// 3. number: peer's bandwidth
}

class SimException {

}

Interface EventHandler {
void handle() throws SimException; // callback function
}

class Event {
long time; // when this event happens
Node src; // which peer generates this event
Node dst; // whom is destinate of this event
Vector<EventHandler> handlers; //process an event and update states accordingly
int type; // enum, see below
// 1. connectSent: peer 1 makes a connection to peer 2, and add each other into neighbors
// 2. connectArrived: the connect message is received by the peer 2
// 3. acceptSent: the potential sender reply with an accept message
// 4. acceptArrived: the accept message arrives at the connection originator
// 5. requestSent: a receiver sends a high-priority request message to a sender
// 6. requestArrived: a request message gets to a sender
// 7. dataSent: a sender sends a data segment
// 8. dataArrived: a data segment arrives to a receiver
// 9. joinSent: a join message to the tracker
// 10. joinArrived: a join message reaches the tracker
// 11. responseSent: a response message sent by the tracker
// 12. responseArrived: a response message reaches the receiver

// 13. scheduleStarted: a scheduling period started.
//14. bimapSyncSent: the receiver inform all its neighbors what part of the video it is interested currently
in order to get a small bitmap from them to do scheduleing, this message is sent
when the receiver: jumps to view another part of the video or a new neighbor joins.
//15. bitmapSyncArrived: the sender receives the bitmap Synchronization information

//commet: how should we do when a scheduling period expires?
//There are two situations: 1. all scheduled segments arrived; 2. some segments are still in transmission.

void addHandler(Interface EventHandler); // add an additional event handler
void rmvHandler(Interface EventHandler); // remove an additional event handler
}

class EventQueue {
SortedMap<Long, Event> queue; // events sorted on its time
void dispatch(Event event); // sequentially invoke even handlers
}

class Simulator {
long simTime; // elapsed simulation time in msec
EventQueue events; // pending events that will be processed
void dispatchEvent(); // forever loop to process the next event
}

Some comments:
*

</pre>

= Performance metrics for scheduling =

Here are some performance metrics:
<pre>
1. Average delivery ratio: number of on-time scheduled segments over total number of segments to be scheduled
2. Load balance among senders
3. Initial buffering time
4. Time and space complexity of the scheduling algorithm
</pre>

Private:psim

2009-03-10T20:40:05Z

Ysa57:

This page documents the development of a discrete event simulator for P2P video streaming applications. This simulator captures important features of data-driven video streaming systems. In particular, it is designed to evaluate: (i) the performance of various segment scheduling algorithms; (ii) the potential of network coding in multi-layer P2P video streaming systems.

= Class Diagrams =

* use long for time/offset in msec, which has a rollover time 24.85 days

<pre>

class Layer { // video layer, we divide each layer into fixed size blocks, we keep track of
// block size and no blocks here
int layer; // layer number it belongs to, set to zero for nonscalable frame
int blockSize; // blocks are fixed size, in bytes
int noBlocks; // how many block here
int dataSize; // aggregate size of all blocks
}

class Frame { // video frame, read from trace file
int no; // serial number
long deadlineOffset; // deadline offset compared to the start of the video, in msec
int totalSize; // total frame size in bytes, including all layers
}

class Segment { // packetized frames
int no; // serial number
Vector<Frame> frames; // reference to included frame
int totalSize; // aggregate size in bytes
Hashtable<Integer, Layer> layers; // reference to layers of this frame, key is the layer id
long getDeadline(); // returns the worst case deadline of this segment (first frame?)
}

class Video { // a media file, shared by a group of peers
String filename; // video trace file path and name
Hashtable<int, Frame> frameTrace; // frames read from the trace file
Hashtable<int, Segment> segmentTrace; // segments generated by the prepareSegments(...)
void prepareSegments(int noFrame); // packetize frames into segment,
// noFrame indicates how many frames should we put in one segment;
// we might implement other packtization schemes later.
}

Interface Node { // a network node, currently can be either a tracker or a peer
}

class Tracker implement Node { // holds a set of groups/videos
Vector<Group> groups; // all the video groups
void addPeer(Group group, Peer peer); // insert a peer into a video group
}

class Peer implement Node { // represent a running peer
int id; // sequential peer id
int ingressBW; // incoming bandwidth in bps
int egressBW; // outgoing bandwidth in bps
Hashtable<Video, Vector<Connection>> senders; // peers that we may send requests to
Hashtable<Video, Vector<Connection>> receivers; // peers that we may send data to
Connection tracker; // control connection to the tracker
Hashtable<Video, VideoBufMap> vBufMaps; // points to the video-level buffer map
void start(Video video); // start downloading a video
void stop(Video video); // stop downloading
}

class Group { // peers that have downloaded or want to download a Video
Video video; // media shared among peers
Vector<Peer> peers; // peers in this group
Vector<Peer> join(Peer peer); // adding a new peer into this group, and return a list of senders
void leave(Peer peer); // removing a peer from this group
}

class Connection { // end to end network link between two peers
Peer peer1; // one end
Peer peer2; // the other
long delay; // transmission delay in msec
int e2eBW; // end-to-end bandwidth in bps
int estimateRate; // estimated rate (maybe historical)
}

class VideoBufMap {
Hashtable<Integer, SegBufMap> sBufMaps; // points to segment bufmap
}

class SegBufMap {
Hashtable<Integer, LayerBufMap> lBufMaps; // points to layer bufmap
}

class LayerBufMap {
boolean avail; // availability bit for this (video, segment, layer) tuple
NCBuf ncBuf; // network coding structure
}

class NCBuf {
boolean servCapibility; // Serving capability of each segment
// show whether this segment is capable of serving other peers(applicable in NC)
int noCodedBl; // No. of encoded blocks for this (video,segment,layer)
BufferedMatrix matrix; // coefficients and their corresponding encoded blocks up to now
}

class BufferedMatrix{ // save coefficients and their corresponding encoded blocks up to now
Vector<Vector<Integer>> coef; // coefficients of the corresponding encoded blocks
Vector <Integer>encodedValue; //encoded blocks

}

class SysParam{ // system parameters that can be changed in each iteration of the simulation
float portionServ; // after receiving this portion of coded blocks out of total number of blocks, the segment is capable
// of serving to others [in case of network coding]
long skipSec; // time duration which is skipped from the current playback point for a new joined peer [in case of
// network coding]
}

// XXX TODO XXX

class SlidingWindow{ // the sliding window which contains all the segments that the receiver is interested currently
// set it to a fixed size, for example 1 minute of videos
// the receiver first inform all its neighbors which part of the video it is interested currently,
// then its neighbors will send their bitmap of that part to the receiver for scheduling
int startOffset; //the offset of the starting segment compared with the start of the video
int endOffset; // the offset of the ending segment compared with the start of the video
double slidingWindowSize(); //get the size of the sliding window
}

class exchangeWindow{ // the exchange window is the front part of the sliding window.
//The unavailable segments in exchange window will be requested by the peer
//usually we set it to a fixed size, for example, 10 seconds of video
// the field of this class is similar to that of the SlidingWindow class
int startOffset;
int endOffset;
void move(); // move the exchange window forward afte a scheduling period and do a next scheduling
double getSlidingWindowSize()
}

interface Scheduler{ // any class wants to do scheduling should implement this interface
void schedule() throws simException; // the scheduling period is specified in the specific scheduling algorithm class
}

class SchedulingResult{ // this class is used to record scheduling results and do some statistics,
// for example, calculate the average delivery rate
Tuple<int, int, double> log; //log file of the results. Each item of the tuple specifies the peerID, segmentID and
// the starting time for the peer to transmit the segment
double getDeliveryRatio(); //calculate the average delivery ratio
}

class SEFF implements Scheduler{ // the Serial Earliest Finish-time First scheduling algorithm
int schedulingPeriod; // scheduling period, for example, 2 seconds
void schedule(); //implement the Scheduler interface
SchedulingResult result; // the scheduling results stored here

}

class LRF implements Scheduler{ // the Local Rarest First algorithm
int schedulingPeriod; // scheduling period, for example, 2 seconds
void schedule(); //implement the Scheduler interface
SchedulingResult result; // the scheduling results stored here
}

class RndGen { // common random number/event generators, to deal with
// 1. event: add new receiver for a group/video
// 2. event: remove a receiver from a group/video
// 3. number: peer's bandwidth
}

class SimException {

}

Interface EventHandler {
void handle() throws SimException; // callback function
}

class Event {
long time; // when this event happens
Node src; // which peer generates this event
Node dst; // whom is destinate of this event
Vector<EventHandler> handlers; //process an event and update states accordingly
int type; // enum, see below
// 1. connectSent: peer 1 makes a connection to peer 2, and add each other into neighbors
// 2. connectArrived: the connect message is received by the peer 2
// 3. acceptSent: the potential sender reply with an accept message
// 4. acceptArrived: the accept message arrives at the connection originator
// 5. requestSent: a receiver sends a high-priority request message to a sender
// 6. requestArrived: a request message gets to a sender
// 7. dataSent: a sender sends a data segment
// 8. dataArrived: a data segment arrives to a receiver
// 9. joinSent: a join message to the tracker
// 10. joinArrived: a join message reaches the tracker
// 11. responseSent: a response message sent by the tracker
// 12. responseArrived: a response message reaches the receiver

// 13. scheduleStarted: a scheduling period started.
//14. bimapSyncSent: the receiver inform all its neighbors what part of the video it is interested currently
in order to get a small bitmap from them to do scheduleing, this message is sent
when the receiver: jumps to view another part of the video or a new neighbor joins.
//15. bitmapSyncArrived: the sender receives the bitmap Synchronization information

//commet: how should we do when a scheduling period expires?
//There are two situations: 1. all scheduled segments arrived; 2. some segments are still in transmission.

void addHandler(Interface EventHandler); // add an additional event handler
void rmvHandler(Interface EventHandler); // remove an additional event handler
}

class EventQueue {
SortedMap<Long, Event> queue; // events sorted on its time
void dispatch(Event event); // sequentially invoke even handlers
}

class Simulator {
long simTime; // elapsed simulation time in msec
EventQueue events; // pending events that will be processed
void dispatchEvent(); // forever loop to process the next event
}

Some comments:
*

</pre>

= Performance metrics for scheduling =

Here are some performance metrics:
<pre>
1. Average delivery ratio: number of on-time scheduled segments over total number of segments to be scheduled
2. Load balance among senders
3. Initial buffering time
4. Time and space complexity of the scheduling algorithm
</pre>

Private:psim

2009-03-10T20:38:37Z

Ysa57:

This page documents the development of a discrete event simulator for P2P video streaming applications. This simulator captures important features of data-driven video streaming systems. In particular, it is designed to evaluate: (i) the performance of various segment scheduling algorithms; (ii) the potential of network coding in multi-layer P2P video streaming systems.

= Class Diagrams =

* use long for time/offset in msec, which has a rollover time 24.85 days

<pre>

class Layer { // video layer, we divide each layer into fixed size blocks, we keep track of
// block size and no blocks here
int layer; // layer number it belongs to, set to zero for nonscalable frame
int blockSize; // blocks are fixed size, in bytes
int noBlocks; // how many block here
int dataSize; // aggregate size of all blocks
}

class Frame { // video frame, read from trace file
int no; // serial number
long deadlineOffset; // deadline offset compared to the start of the video, in msec
int totalSize; // total frame size in bytes, including all layers
}

class Segment { // packetized frames
int no; // serial number
Vector<Frame> frames; // reference to included frame
int totalSize; // aggregate size in bytes
Hashtable<Integer, Layer> layers; // reference to layers of this frame, key is the layer id
long getDeadline(); // returns the worst case deadline of this segment (first frame?)
}

class Video { // a media file, shared by a group of peers
String filename; // video trace file path and name
Hashtable<int, Frame> frameTrace; // frames read from the trace file
Hashtable<int, Segment> segmentTrace; // segments generated by the prepareSegments(...)
void prepareSegments(int noFrame); // packetize frames into segment,
// noFrame indicates how many frames should we put in one segment;
// we might implement other packtization schemes later.
}

Interface Node { // a network node, currently can be either a tracker or a peer
}

class Tracker implement Node { // holds a set of groups/videos
Vector<Group> groups; // all the video groups
void addPeer(Group group, Peer peer); // insert a peer into a video group
}

class Peer implement Node { // represent a running peer
int id; // sequential peer id
int ingressBW; // incoming bandwidth in bps
int egressBW; // outgoing bandwidth in bps
Hashtable<Video, Vector<Connection>> senders; // peers that we may send requests to
Hashtable<Video, Vector<Connection>> receivers; // peers that we may send data to
Connection tracker; // control connection to the tracker
Hashtable<Video, VideoBufMap> vBufMaps; // points to the video-level buffer map
void start(Video video); // start downloading a video
void stop(Video video); // stop downloading
}

class Group { // peers that have downloaded or want to download a Video
Video video; // media shared among peers
Vector<Peer> peers; // peers in this group
Vector<Peer> join(Peer peer); // adding a new peer into this group, and return a list of senders
void leave(Peer peer); // removing a peer from this group
}

class Connection { // end to end network link between two peers
Peer peer1; // one end
Peer peer2; // the other
long delay; // transmission delay in msec
int e2eBW; // end-to-end bandwidth in bps
int estimateRate; // estimated rate (maybe historical)
}

class VideoBufMap {
Hashtable<Integer, SegBufMap> sBufMaps; // points to segment bufmap
}

class SegBufMap {
Hashtable<Integer, LayerBufMap> lBufMaps; // points to layer bufmap
}

class LayerBufMap {
boolean avail; // availability bit for this (video, segment, layer) tuple
NCBuf ncBuf; // network coding structure
}

class NCBuf {
boolean servCapibility; // Serving capability of each segment
// show whether this segment is capable of serving other peers(applicable in NC)
int noCodedBl; // No. of encoded blocks for this (video,segment,layer)
BufferedMatrix matrix; // coefficients and their corresponding encoded blocks up to now
}

class BufferedMatrix{ // save coefficients and their corresponding encoded blocks up to now
Vector<Vector<Integer>> coef; // coefficients of the corresponding encoded blocks
Vector <Integer>encodedValue; //encoded blocks

}

class SysParam{ // system parameters that can be changed in each iteration of the simulation
float portionServ; // after receiving this portion of coded blocks out of total number of blocks, the segment is capable
// of serving to others [in case of network coding]
long skipSec; // time duration which is skipped from the current playback point for a new joined peer [in case of
// network coding]
}

// XXX TODO XXX

class SlidingWindow{ // the sliding window which contains all the segments that the receiver is interested currently
// set it to a fixed size, for example 1 minute of videos
// the receiver first inform all its neighbors which part of the video it is interested currently,
// then its neighbors will send their bitmap of that part to the receiver for scheduling
int startOffset; //the offset of the starting segment compared with the start of the video
int endOffset; // the offset of the ending segment compared with the start of the video
double slidingWindowSize(); //get the size of the sliding window
}

class exchangeWindow{ // the exchange window is the front part of the sliding window.
//The unavailable segments in exchange window will be requested by the peer
//usually we set it to a fixed size, for example, 10 seconds of video
// the field of this class is similar to that of the SlidingWindow class
int startOffset;
int endOffset;
void move(); // move the exchange window forward afte a scheduling period and do a next scheduling
double getSlidingWindowSize()
}

interface Scheduler{ // any class wants to do scheduling should implement this interface
void schedule() throws simException; // the scheduling period is specified in the specific scheduling algorithm class
}

class SchedulingResult{ // this class is used to record scheduling results and do some statistics,
// for example, calculate the average delivery rate
Tuple<int, int, double> log; //log file of the results. Each item of the tuple specifies the peerID, segmentID and
// the starting time for the peer to transmit the segment
double getDeliveryRatio(); //calculate the average delivery ratio
}

class SEFF implements Scheduler{ // the Serial Earliest Finish-time First scheduling algorithm
int schedulingPeriod; // scheduling period, for example, 2 seconds
void schedule(); //implement the Scheduler interface
SchedulingResult result; // the scheduling results stored here

}

class LRF implements Scheduler{ // the Local Rarest First algorithm
int schedulingPeriod; // scheduling period, for example, 2 seconds
void schedule(); //implement the Scheduler interface
SchedulingResult result; // the scheduling results stored here
}

class RndGen { // common random number/event generators, to deal with
// 1. event: add new receiver for a group/video
// 2. event: remove a receiver from a group/video
// 3. number: peer's bandwidth
}

class SimException {

}

Interface EventHandler {
void handle() throws SimException; // callback function
}

class Event {
long time; // when this event happens
Node src; // which peer generates this event
Node dst; // whom is destinate of this event
Vector<EventHandler> handlers; //process an event and update states accordingly
int type; // enum, see below
// 1. connectSent: peer 1 makes a connection to peer 2, and add each other into neighbors
// 2. connectArrived: the connect message is received by the peer 2
// 3. acceptSent: the potential sender reply with an accept message
// 4. acceptArrived: the accept message arrives at the connection originator
// 5. requestSent: a receiver sends a high-priority request message to a sender
// 6. requestArrived: a request message gets to a sender
// 7. dataSent: a sender sends a data segment
// 8. dataArrived: a data segment arrives to a receiver
// 9. joinSent: a join message to the tracker
// 10. joinArrived: a join message reaches the tracker
// 11. responseSent: a response message sent by the tracker
// 12. responseArrived: a response message reaches the receiver

// 13. scheduleStarted: a scheduling period started.
//14. bimapSyncSent: the receiver inform all its neighbors what part of the video it is interested currently
in order to get a small bitmap from them to do scheduleing, this message is sent
when the receiver: jumps to view another part of the video or a new neighbor joins.
//15. bitmapSyncArrived: the sender receives the bitmap Synchronization information

//commet: how should we do when a scheduling period expires?
//There are two situations: 1. all scheduled segments arrived; 2. some segments are still in transmission.

void addHandler(Interface EventHandler); // add an additional event handler
void rmvHandler(Interface EventHandler); // remove an additional event handler
}

class EventQueue {
SortedMap<Long, Event> queue; // events sorted on its time
void dispatch(Event event); // sequentially invoke even handlers
}

class Simulator {
long simTime; // elapsed simulation time in msec
EventQueue events; // pending events that will be processed
void dispatchEvent(); // forever loop to process the next event
}

Some comments:
*

</pre>

= Performance metrics for scheduling =

Here are some performance metrics:
<pre>
1. Average delivery ratio: number of on-time scheduled segments over total number of segments to be scheduled
2. Load balance among senders
3. Initial playback delay
4. Time and space complexity of the scheduling algorithm
</pre>

Private:psim

2009-03-10T20:37:04Z

Ysa57:

This page documents the development of a discrete event simulator for P2P video streaming applications. This simulator captures important features of data-driven video streaming systems. In particular, it is designed to evaluate: (i) the performance of various segment scheduling algorithms; (ii) the potential of network coding in multi-layer P2P video streaming systems.

= Class Diagrams =

* use long for time/offset in msec, which has a rollover time 24.85 days

<pre>

class Layer { // video layer, we divide each layer into fixed size blocks, we keep track of
// block size and no blocks here
int layer; // layer number it belongs to, set to zero for nonscalable frame
int blockSize; // blocks are fixed size, in bytes
int noBlocks; // how many block here
int dataSize; // aggregate size of all blocks
}

class Frame { // video frame, read from trace file
int no; // serial number
long deadlineOffset; // deadline offset compared to the start of the video, in msec
int totalSize; // total frame size in bytes, including all layers
}

class Segment { // packetized frames
int no; // serial number
Vector<Frame> frames; // reference to included frame
int totalSize; // aggregate size in bytes
Hashtable<Integer, Layer> layers; // reference to layers of this frame, key is the layer id
long getDeadline(); // returns the worst case deadline of this segment (first frame?)
}

class Video { // a media file, shared by a group of peers
String filename; // video trace file path and name
Hashtable<int, Frame> frameTrace; // frames read from the trace file
Hashtable<int, Segment> segmentTrace; // segments generated by the prepareSegments(...)
void prepareSegments(int noFrame); // packetize frames into segment,
// noFrame indicates how many frames should we put in one segment;
// we might implement other packtization schemes later.
}

Interface Node { // a network node, currently can be either a tracker or a peer
}

class Tracker implement Node { // holds a set of groups/videos
Vector<Group> groups; // all the video groups
void addPeer(Group group, Peer peer); // insert a peer into a video group
}

class Peer implement Node { // represent a running peer
int id; // sequential peer id
int ingressBW; // incoming bandwidth in bps
int egressBW; // outgoing bandwidth in bps
Hashtable<Video, Vector<Connection>> senders; // peers that we may send requests to
Hashtable<Video, Vector<Connection>> receivers; // peers that we may send data to
Connection tracker; // control connection to the tracker
Hashtable<Video, VideoBufMap> vBufMaps; // points to the video-level buffer map
void start(Video video); // start downloading a video
void stop(Video video); // stop downloading
}

class Group { // peers that have downloaded or want to download a Video
Video video; // media shared among peers
Vector<Peer> peers; // peers in this group
Vector<Peer> join(Peer peer); // adding a new peer into this group, and return a list of senders
void leave(Peer peer); // removing a peer from this group
}

class Connection { // end to end network link between two peers
Peer peer1; // one end
Peer peer2; // the other
long delay; // transmission delay in msec
int e2eBW; // end-to-end bandwidth in bps
int estimateRate; // estimated rate (maybe historical)
}

class VideoBufMap {
Hashtable<Integer, SegBufMap> sBufMaps; // points to segment bufmap
}

class SegBufMap {
Hashtable<Integer, LayerBufMap> lBufMaps; // points to layer bufmap
}

class LayerBufMap {
boolean avail; // availability bit for this (video, segment, layer) tuple
NCBuf ncBuf; // network coding structure
}

class NCBuf {
boolean servCapibility; // Serving capability of each segment
// show whether this segment is capable of serving other peers(applicable in NC)
int noCodedBl; // No. of encoded blocks for this (video,segment,layer)
BufferedMatrix matrix; // coefficients and their corresponding encoded blocks up to now
}

class BufferedMatrix{ // save coefficients and their corresponding encoded blocks up to now
Vector<Vector<Integer>> coef; // coefficients of the corresponding encoded blocks
Vector <Integer>encodedValue; //encoded blocks

}

class SysParam{ // system parameters that can be changed in each iteration of the simulation
float portionServ; // after receiving this portion of coded blocks out of total number of blocks, the segment is capable
// of serving to others [in case of network coding]
long skipSec; // time duration which is skipped from the current playback point for a new joined peer [in case of
// network coding]
}

// XXX TODO XXX

class SlidingWindow{ // the sliding window which contains all the segments that the receiver is interested currently
// set it to a fixed size, for example 1 minute of videos
// the receiver first inform all its neighbors which part of the video it is interested currently,
// then its neighbors will send their bitmap of that part to the receiver for scheduling
int startOffset; //the offset of the starting segment compared with the start of the video
int endOffset; // the offset of the ending segment compared with the start of the video
double slidingWindowSize(); //get the size of the sliding window
}

class exchangeWindow{ // the exchange window is the front part of the sliding window.
//The unavailable segments in exchange window will be requested by the peer
//usually we set it to a fixed size, for example, 10 seconds of video
// the field of this class is similar to that of the SlidingWindow class
int startOffset;
int endOffset;
void move(); // move the exchange window forward afte a scheduling period and do a next scheduling
double getSlidingWindowSize()
}

interface Scheduler{ // any class wants to do scheduling should implement this interface
void schedule() throws simException; // the scheduling period is specified in the specific scheduling algorithm class
}

class SchedulingResult{ // this class is used to record scheduling results and do some statistics,
// for example, calculate the average delivery rate
Tuple<int, int, double> log; //log file of the results. Each item of the tuple specifies the peerID, segmentID and
// the starting time for the peer to transmit the segment
double getDeliveryRatio(); //calculate the average delivery ratio
}

class SEFF implements Scheduler{ // the Serial Earliest Finish-time First scheduling algorithm
int schedulingPeriod; // scheduling period, for example, 2 seconds
void schedule(); //implement the Scheduler interface
SchedulingResult result; // the scheduling results stored here

}

class LRF implements Scheduler{ // the Local Rarest First algorithm
int schedulingPeriod; // scheduling period, for example, 2 seconds
void schedule(); //implement the Scheduler interface
SchedulingResult result; // the scheduling results stored here
}

class RndGen { // common random number/event generators, to deal with
// 1. event: add new receiver for a group/video
// 2. event: remove a receiver from a group/video
// 3. number: peer's bandwidth
}

class SimException {

}

Interface EventHandler {
void handle() throws SimException; // callback function
}

class Event {
long time; // when this event happens
Node src; // which peer generates this event
Node dst; // whom is destinate of this event
Vector<EventHandler> handlers; //process an event and update states accordingly
int type; // enum, see below
// 1. connectSent: peer 1 makes a connection to peer 2, and add each other into neighbors
// 2. connectArrived: the connect message is received by the peer 2
// 3. acceptSent: the potential sender reply with an accept message
// 4. acceptArrived: the accept message arrives at the connection originator
// 5. requestSent: a receiver sends a high-priority request message to a sender
// 6. requestArrived: a request message gets to a sender
// 7. dataSent: a sender sends a data segment
// 8. dataArrived: a data segment arrives to a receiver
// 9. joinSent: a join message to the tracker
// 10. joinArrived: a join message reaches the tracker
// 11. responseSent: a response message sent by the tracker
// 12. responseArrived: a response message reaches the receiver

// 13. scheduleStarted: a scheduling period started.
//14. bimapSyncSent: the receiver inform all its neighbors what part of the video it is interested currently
in order to get a small bitmap from them to do scheduleing, this message is sent
when the receiver: jumps to view another part of the video or a new neighbor joins.
//15. bitmapSyncArrived: the sender receives the bitmap Synchronization information

//commet: how should we do when a scheduling period expires?
//There are two situations: 1. all scheduled segments arrived; 2. some segments are still in transmission.

void addHandler(Interface EventHandler); // add an additional event handler
void rmvHandler(Interface EventHandler); // remove an additional event handler
}

class EventQueue {
SortedMap<Long, Event> queue; // events sorted on its time
void dispatch(Event event); // sequentially invoke even handlers
}

class Simulator {
long simTime; // elapsed simulation time in msec
EventQueue events; // pending events that will be processed
void dispatchEvent(); // forever loop to process the next event
}

Some comments:
*

</pre>

= Performance metrics for scheduling =

<pre>
Here are some performance metrics:
1. Average delivery ratio: number of on-time scheduled segments over total number of segments to be scheduled
2. Load balance among senders
3. Initial playback delay
4. Time and space complexity of the scheduling algorithm
</pre>

Private:psim

2009-03-10T20:36:20Z

Ysa57:

This page documents the development of a discrete event simulator for P2P video streaming applications. This simulator captures important features of data-driven video streaming systems. In particular, it is designed to evaluate: (i) the performance of various segment scheduling algorithms; (ii) the potential of network coding in multi-layer P2P video streaming systems.

= Class Diagrams =

* use long for time/offset in msec, which has a rollover time 24.85 days

<pre>

class Layer { // video layer, we divide each layer into fixed size blocks, we keep track of
// block size and no blocks here
int layer; // layer number it belongs to, set to zero for nonscalable frame
int blockSize; // blocks are fixed size, in bytes
int noBlocks; // how many block here
int dataSize; // aggregate size of all blocks
}

class Frame { // video frame, read from trace file
int no; // serial number
long deadlineOffset; // deadline offset compared to the start of the video, in msec
int totalSize; // total frame size in bytes, including all layers
}

class Segment { // packetized frames
int no; // serial number
Vector<Frame> frames; // reference to included frame
int totalSize; // aggregate size in bytes
Hashtable<Integer, Layer> layers; // reference to layers of this frame, key is the layer id
long getDeadline(); // returns the worst case deadline of this segment (first frame?)
}

class Video { // a media file, shared by a group of peers
String filename; // video trace file path and name
Hashtable<int, Frame> frameTrace; // frames read from the trace file
Hashtable<int, Segment> segmentTrace; // segments generated by the prepareSegments(...)
void prepareSegments(int noFrame); // packetize frames into segment,
// noFrame indicates how many frames should we put in one segment;
// we might implement other packtization schemes later.
}

Interface Node { // a network node, currently can be either a tracker or a peer
}

class Tracker implement Node { // holds a set of groups/videos
Vector<Group> groups; // all the video groups
void addPeer(Group group, Peer peer); // insert a peer into a video group
}

class Peer implement Node { // represent a running peer
int id; // sequential peer id
int ingressBW; // incoming bandwidth in bps
int egressBW; // outgoing bandwidth in bps
Hashtable<Video, Vector<Connection>> senders; // peers that we may send requests to
Hashtable<Video, Vector<Connection>> receivers; // peers that we may send data to
Connection tracker; // control connection to the tracker
Hashtable<Video, VideoBufMap> vBufMaps; // points to the video-level buffer map
void start(Video video); // start downloading a video
void stop(Video video); // stop downloading
}

class Group { // peers that have downloaded or want to download a Video
Video video; // media shared among peers
Vector<Peer> peers; // peers in this group
Vector<Peer> join(Peer peer); // adding a new peer into this group, and return a list of senders
void leave(Peer peer); // removing a peer from this group
}

class Connection { // end to end network link between two peers
Peer peer1; // one end
Peer peer2; // the other
long delay; // transmission delay in msec
int e2eBW; // end-to-end bandwidth in bps
int estimateRate; // estimated rate (maybe historical)
}

class VideoBufMap {
Hashtable<Integer, SegBufMap> sBufMaps; // points to segment bufmap
}

class SegBufMap {
Hashtable<Integer, LayerBufMap> lBufMaps; // points to layer bufmap
}

class LayerBufMap {
boolean avail; // availability bit for this (video, segment, layer) tuple
NCBuf ncBuf; // network coding structure
}

class NCBuf {
boolean servCapibility; // Serving capability of each segment
// show whether this segment is capable of serving other peers(applicable in NC)
int noCodedBl; // No. of encoded blocks for this (video,segment,layer)
BufferedMatrix matrix; // coefficients and their corresponding encoded blocks up to now
}

class BufferedMatrix{ // save coefficients and their corresponding encoded blocks up to now
Vector<Vector<Integer>> coef; // coefficients of the corresponding encoded blocks
Vector <Integer>encodedValue; //encoded blocks

}

class SysParam{ // system parameters that can be changed in each iteration of the simulation
float portionServ; // after receiving this portion of coded blocks out of total number of blocks, the segment is capable
// of serving to others [in case of network coding]
long skipSec; // time duration which is skipped from the current playback point for a new joined peer [in case of
// network coding]
}

// XXX TODO XXX

class SlidingWindow{ // the sliding window which contains all the segments that the receiver is interested currently
// set it to a fixed size, for example 1 minute of videos
// the receiver first inform all its neighbors which part of the video it is interested currently,
// then its neighbors will send their bitmap of that part to the receiver for scheduling
int startOffset; //the offset of the starting segment compared with the start of the video
int endOffset; // the offset of the ending segment compared with the start of the video
double slidingWindowSize(); //get the size of the sliding window
}

class exchangeWindow{ // the exchange window is the front part of the sliding window.
//The unavailable segments in exchange window will be requested by the peer
//usually we set it to a fixed size, for example, 10 seconds of video
// the field of this class is similar to that of the SlidingWindow class
int startOffset;
int endOffset;
void move(); // move the exchange window forward afte a scheduling period and do a next scheduling
double getSlidingWindowSize()
}

interface Scheduler{ // any class wants to do scheduling should implement this interface
void schedule() throws simException; // the scheduling period is specified in the specific scheduling algorithm class
}

class SchedulingResult{ // this class is used to record scheduling results and do some statistics,
// for example, calculate the average delivery rate
Tuple<int, int, double> log; //log file of the results. Each item of the tuple specifies the peerID, segmentID and
// the starting time for the peer to transmit the segment
double getDeliveryRatio(); //calculate the average delivery ratio
}

class SEFF implements Scheduler{ // the Serial Earliest Finish-time First scheduling algorithm
int schedulingPeriod; // scheduling period, for example, 2 seconds
void schedule(); //implement the Scheduler interface
SchedulingResult result; // the scheduling results stored here

}

class LRF implements Scheduler{ // the Local Rarest First algorithm
int schedulingPeriod; // scheduling period, for example, 2 seconds
void schedule(); //implement the Scheduler interface
SchedulingResult result; // the scheduling results stored here
}

class RndGen { // common random number/event generators, to deal with
// 1. event: add new receiver for a group/video
// 2. event: remove a receiver from a group/video
// 3. number: peer's bandwidth
}

class SimException {

}

Interface EventHandler {
void handle() throws SimException; // callback function
}

class Event {
long time; // when this event happens
Node src; // which peer generates this event
Node dst; // whom is destinate of this event
Vector<EventHandler> handlers; //process an event and update states accordingly
int type; // enum, see below
// 1. connectSent: peer 1 makes a connection to peer 2, and add each other into neighbors
// 2. connectArrived: the connect message is received by the peer 2
// 3. acceptSent: the potential sender reply with an accept message
// 4. acceptArrived: the accept message arrives at the connection originator
// 5. requestSent: a receiver sends a high-priority request message to a sender
// 6. requestArrived: a request message gets to a sender
// 7. dataSent: a sender sends a data segment
// 8. dataArrived: a data segment arrives to a receiver
// 9. joinSent: a join message to the tracker
// 10. joinArrived: a join message reaches the tracker
// 11. responseSent: a response message sent by the tracker
// 12. responseArrived: a response message reaches the receiver

// 13. scheduleStarted: a scheduling period started.
//14. bimapSyncSent: the receiver inform all its neighbors what part of the video it is interested currently
in order to get a small bitmap from them to do scheduleing, this message is sent
when the receiver: jumps to view another part of the video or a new neighbor joins.
//15. bitmapSyncArrived: the sender receives the bitmap Synchronization information

//commet: how should we do when a scheduling period expires?
//There are two situations: 1. all scheduled segments arrived; 2. some segments are still in transmission.

void addHandler(Interface EventHandler); // add an additional event handler
void rmvHandler(Interface EventHandler); // remove an additional event handler
}

class EventQueue {
SortedMap<Long, Event> queue; // events sorted on its time
void dispatch(Event event); // sequentially invoke even handlers
}

class Simulator {
long simTime; // elapsed simulation time in msec
EventQueue events; // pending events that will be processed
void dispatchEvent(); // forever loop to process the next event
}

Some comments:
*

</pre>

== Performance metrics for scheduling ==

</pre>
Here are some performance metrics:
1. Average delivery ratio: number of on-time scheduled segments over total number of segments to be scheduled
2. Load balance among senders
3. Initial playback delay
4. Time and space complexity of the scheduling algorithm
</pre>

Private:psim

2009-03-10T20:35:28Z

Ysa57:

This page documents the development of a discrete event simulator for P2P video streaming applications. This simulator captures important features of data-driven video streaming systems. In particular, it is designed to evaluate: (i) the performance of various segment scheduling algorithms; (ii) the potential of network coding in multi-layer P2P video streaming systems.

= Class Diagrams =

* use long for time/offset in msec, which has a rollover time 24.85 days

<pre>

class Layer { // video layer, we divide each layer into fixed size blocks, we keep track of
// block size and no blocks here
int layer; // layer number it belongs to, set to zero for nonscalable frame
int blockSize; // blocks are fixed size, in bytes
int noBlocks; // how many block here
int dataSize; // aggregate size of all blocks
}

class Frame { // video frame, read from trace file
int no; // serial number
long deadlineOffset; // deadline offset compared to the start of the video, in msec
int totalSize; // total frame size in bytes, including all layers
}

class Segment { // packetized frames
int no; // serial number
Vector<Frame> frames; // reference to included frame
int totalSize; // aggregate size in bytes
Hashtable<Integer, Layer> layers; // reference to layers of this frame, key is the layer id
long getDeadline(); // returns the worst case deadline of this segment (first frame?)
}

class Video { // a media file, shared by a group of peers
String filename; // video trace file path and name
Hashtable<int, Frame> frameTrace; // frames read from the trace file
Hashtable<int, Segment> segmentTrace; // segments generated by the prepareSegments(...)
void prepareSegments(int noFrame); // packetize frames into segment,
// noFrame indicates how many frames should we put in one segment;
// we might implement other packtization schemes later.
}

Interface Node { // a network node, currently can be either a tracker or a peer
}

class Tracker implement Node { // holds a set of groups/videos
Vector<Group> groups; // all the video groups
void addPeer(Group group, Peer peer); // insert a peer into a video group
}

class Peer implement Node { // represent a running peer
int id; // sequential peer id
int ingressBW; // incoming bandwidth in bps
int egressBW; // outgoing bandwidth in bps
Hashtable<Video, Vector<Connection>> senders; // peers that we may send requests to
Hashtable<Video, Vector<Connection>> receivers; // peers that we may send data to
Connection tracker; // control connection to the tracker
Hashtable<Video, VideoBufMap> vBufMaps; // points to the video-level buffer map
void start(Video video); // start downloading a video
void stop(Video video); // stop downloading
}

class Group { // peers that have downloaded or want to download a Video
Video video; // media shared among peers
Vector<Peer> peers; // peers in this group
Vector<Peer> join(Peer peer); // adding a new peer into this group, and return a list of senders
void leave(Peer peer); // removing a peer from this group
}

class Connection { // end to end network link between two peers
Peer peer1; // one end
Peer peer2; // the other
long delay; // transmission delay in msec
int e2eBW; // end-to-end bandwidth in bps
int estimateRate; // estimated rate (maybe historical)
}

class VideoBufMap {
Hashtable<Integer, SegBufMap> sBufMaps; // points to segment bufmap
}

class SegBufMap {
Hashtable<Integer, LayerBufMap> lBufMaps; // points to layer bufmap
}

class LayerBufMap {
boolean avail; // availability bit for this (video, segment, layer) tuple
NCBuf ncBuf; // network coding structure
}

class NCBuf {
boolean servCapibility; // Serving capability of each segment
// show whether this segment is capable of serving other peers(applicable in NC)
int noCodedBl; // No. of encoded blocks for this (video,segment,layer)
BufferedMatrix matrix; // coefficients and their corresponding encoded blocks up to now
}

class BufferedMatrix{ // save coefficients and their corresponding encoded blocks up to now
Vector<Vector<Integer>> coef; // coefficients of the corresponding encoded blocks
Vector <Integer>encodedValue; //encoded blocks

}

class SysParam{ // system parameters that can be changed in each iteration of the simulation
float portionServ; // after receiving this portion of coded blocks out of total number of blocks, the segment is capable
// of serving to others [in case of network coding]
long skipSec; // time duration which is skipped from the current playback point for a new joined peer [in case of
// network coding]
}

// XXX TODO XXX

class SlidingWindow{ // the sliding window which contains all the segments that the receiver is interested currently
// set it to a fixed size, for example 1 minute of videos
// the receiver first inform all its neighbors which part of the video it is interested currently,
// then its neighbors will send their bitmap of that part to the receiver for scheduling
int startOffset; //the offset of the starting segment compared with the start of the video
int endOffset; // the offset of the ending segment compared with the start of the video
double slidingWindowSize(); //get the size of the sliding window
}

class exchangeWindow{ // the exchange window is the front part of the sliding window.
//The unavailable segments in exchange window will be requested by the peer
//usually we set it to a fixed size, for example, 10 seconds of video
// the field of this class is similar to that of the SlidingWindow class
int startOffset;
int endOffset;
void move(); // move the exchange window forward afte a scheduling period and do a next scheduling
double getSlidingWindowSize()
}

interface Scheduler{ // any class wants to do scheduling should implement this interface
void schedule() throws simException; // the scheduling period is specified in the specific scheduling algorithm class
}

class SchedulingResult{ // this class is used to record scheduling results and do some statistics,
// for example, calculate the average delivery rate
Tuple<int, int, double> log; //log file of the results. Each item of the tuple specifies the peerID, segmentID and
// the starting time for the peer to transmit the segment
double getDeliveryRatio(); //calculate the average delivery ratio
}

class SEFF implements Scheduler{ // the Serial Earliest Finish-time First scheduling algorithm
int schedulingPeriod; // scheduling period, for example, 2 seconds
void schedule(); //implement the Scheduler interface
SchedulingResult result; // the scheduling results stored here

}

class LRF implements Scheduler{ // the Local Rarest First algorithm
int schedulingPeriod; // scheduling period, for example, 2 seconds
void schedule(); //implement the Scheduler interface
SchedulingResult result; // the scheduling results stored here
}

class RndGen { // common random number/event generators, to deal with
// 1. event: add new receiver for a group/video
// 2. event: remove a receiver from a group/video
// 3. number: peer's bandwidth
}

class SimException {

}

Interface EventHandler {
void handle() throws SimException; // callback function
}

class Event {
long time; // when this event happens
Node src; // which peer generates this event
Node dst; // whom is destinate of this event
Vector<EventHandler> handlers; //process an event and update states accordingly
int type; // enum, see below
// 1. connectSent: peer 1 makes a connection to peer 2, and add each other into neighbors
// 2. connectArrived: the connect message is received by the peer 2
// 3. acceptSent: the potential sender reply with an accept message
// 4. acceptArrived: the accept message arrives at the connection originator
// 5. requestSent: a receiver sends a high-priority request message to a sender
// 6. requestArrived: a request message gets to a sender
// 7. dataSent: a sender sends a data segment
// 8. dataArrived: a data segment arrives to a receiver
// 9. joinSent: a join message to the tracker
// 10. joinArrived: a join message reaches the tracker
// 11. responseSent: a response message sent by the tracker
// 12. responseArrived: a response message reaches the receiver

// 13. scheduleStarted: a scheduling period started.
//14. bimapSyncSent: the receiver inform all its neighbors what part of the video it is interested currently
in order to get a small bitmap from them to do scheduleing, this message is sent
when the receiver: jumps to view another part of the video or a new neighbor joins.
//15. bitmapSyncArrived: the sender receives the bitmap Synchronization information

//commet: how should we do when a scheduling period expires?
//There are two situations: 1. all scheduled segments arrived; 2. some segments are still in transmission.

void addHandler(Interface EventHandler); // add an additional event handler
void rmvHandler(Interface EventHandler); // remove an additional event handler
}

class EventQueue {
SortedMap<Long, Event> queue; // events sorted on its time
void dispatch(Event event); // sequentially invoke even handlers
}

class Simulator {
long simTime; // elapsed simulation time in msec
EventQueue events; // pending events that will be processed
void dispatchEvent(); // forever loop to process the next event
}

Some comments:
*

</pre>

= Performance metrics for scheduling =

</pre>
Here are some performance metrics:
1. Average delivery ratio: number of on-time scheduled segments over total number of segments to be scheduled
2. Load balance among senders
3. Initial playback delay
4. Time and space complexity of the scheduling algorithm
</pre>

Private:psim

2009-03-10T20:23:14Z

Ysa57:

Private:psim

2009-03-10T19:53:17Z

Ysa57:

Private:psim

2009-03-10T19:49:59Z

Ysa57:

Private:psim

2009-03-10T19:37:12Z

Ysa57:

Private:psim

2009-03-10T04:48:31Z

Ysa57:

This page documents the development of a discrete event simulator for P2P video streaming applications. This simulator captures important features of data-driven video streaming systems. In particular, it is designed to evaluate: (i) the performance of various segment scheduling algorithms; (ii) the potential of network coding in multi-layer P2P video streaming systems.

= Class Diagrams =

* use long for time/offset in msec, which has a rollover time 24.85 days

<pre>

class Layer { // video layer, we divide each layer into fixed size blocks, we keep track of
// block size and no blocks here
int layer; // layer number it belongs to, set to zero for nonscalable frame
int blockSize; // blocks are fixed size, in bytes
int noBlocks; // how many block here
int dataSize; // aggregate size of all blocks
}

class Frame { // video frame, read from trace file
int no; // serial number
long deadlineOffset; // deadline offset compared to the start of the video, in msec
int totalSize; // total frame size in bytes, including all layers
Hashtable<Integer, Layer> layers; // reference to layers of this frame, key is the layer id
}

class Segment { // packetized frames
int no; // serial number
Vector<Frame> frames; // reference to included frame
int totalSize; // aggregate size in bytes
}

class Video { // a media file, shared by a group of peers
String filename; // video trace file path and name
Hashtable<int, Frame> frameTrace; // frames read from the trace file
Hashtable<int, Segment> segmentTrace; // segments generated by the prepareSegments(...)
void prepareSegments(int noFrame); // packetize frames into segment,
// noFrame indicates how many frames should we put in one segment;
// we might implement other packtization schemes later.
}

class Neighbor { // keep track of what my neighbor has done
Peer peer; // peer instance, for accessing availability info
int estimateRate; // estimated rate (maybe historical)
Connection conn; // e2e connection between us and another neighboring peer
}

class Tracker { // holds a set of groups/videos
Vector<Group> groups; // all the video groups
}

class Peer { // represent a running peer
int ingressBW; // incoming bandwidth in bps
int egressBW; // outgoing bandwidth in bps
Vector<Neighbor> neighbors; // peers that we may send requests to
BufferedMatrix matrix; // matrix of coefficients and encoded values up to now
NoEncodedBlocks noCodedBl; // keep track of No. of encoded blocks in each segment
Connection tracker; // control connection to the tracker
Hashtable<Video, VideoBufMap> vBufMaps; // points to the video-level buffer map
}

class Group { // peers that have downloaded or want to download a Video
Video video; // media shared among peers
Vector<Peer> peers; // peers in this group
Vector<Peer> join(Peer peer); // adding a new peer into this group, and return a list of senders
void leave(Peer peer); // removing a peer from this group
}

class Connection { // end to end network link between two peers
Peer peer1; // one end
Peer peer2; // the other
long delay; // transmission delay in msec
int e2eBW; // end-to-end bandwidth in bps
}

class VideoBufMap {
Hashtable<Integer, SegBufMap> sBufMaps; // points to segment bufmap
}

class SegBufMap {
Hashtable<Integer, LayerBufMap> lBufMaps; // points to layer bufmap
}

class LayerBufMap {
boolean avail; // availability bit for this (video, segment, layer) tuple
NCBuf ncBuf; // network coding structure
}

class NCBuf {
boolean servCapibility; // Serving capability of each segment
// show whether this segment is capable of serving other peers(applicable in NC)
int noCodedBl; // growable 2 dimensional array corresponding to segments and layers
// each element in this vector keep the No. of encoded blocks in the
// corresponding segment
BufferedMatrix marix; // coefficients and their corresponding encoded blocks up to now
}

class BufferedMatrix{ // save coefficients and their corresponding encoded blocks up to now
Vector<Vector<Integer>> coef; // coefficients of the corresponding encoded blocks
Vector <Integer>encodedValue; //encoded blocks
}

// XXX TODO XXX

class SlidingWindow{ // the sliding window which contains all the up-to-date segments at the peer
// set it to a fixed size, for example 1 minute of videos
int startOffset; //the offset of the starting frame compared with the start of the video
int endOffset; // the offset of the ending frame compared with the start of the video
double slideSpeed; // the speed of sliding. The window goes forward continuously (or periodically?) at
// the speed of the streaming rate.
void getSlidingWindowSize(); //get the size of the sliding window
}

class exchangeWindow{ // the exchange window is the front part of the sliding window.
//The unavailable segments in exchange window will be requested by the peer
//usually we set it to a fixed size, for example, 10 seconds of video
// the field of this class is similar to that of the SlidingWindow class
int startOffset;
int end Offset;
double slideSpeed;
void getSlidingWindowSize()
}

interface Scheduler{ // any class wants to do scheduling should implement this interface
void schedule() throws scheduleException; // the scheduling period is specified in the specific scheduling algorithm class
}

class scheduleException{

}

class SchedulingResult{ // this class is used to record scheduling results and do some statistics,
// for example, calculate the average delivery rate
Tuple<int, int, double> log; //log file of the results. Each item of the tuple specifies the peerID, segmentID and
// the starting time for the peer to transmit the segment
double getDeliveryRatio(); //calculate the average delivery ratio
}

class SEFF implements Scheduler{ // the Serial Earliest Finish-time First scheduling algorithm
int schedulingPeriod; // scheduling period, for example, 2 seconds
void schedule(); //implement the Scheduler interface
SchedulingResult result; // the scheduling results stored here

}

class LRF implements Scheduler{ // the Local Rarest First algorithm
int schedulingPeriod; // scheduling period, for example, 2 seconds
void schedule(); //implement the Scheduler interface
SchedulingResult result; // the scheduling results stored here
}

class RndGen { // common random number/event generators, to deal with
// 1. event: add new receiver for a group/video
// 2. event: remove a receiver from a group/video
// 3. number: peer's bandwidth
}

class SimException {

}

Interface EventHandler {
void handle() throws SimException; // callback function
}

class Event {
long time; // when this event happens
Peer src; // which peer generates this event
Peer dst; // whom is destinate of this event
Vector<EventHandler> handlers; //process an event and update states accordingly
int type; // enum, see below
// 1. connect: peer 1 makes a connection to peer 2, and add each other into neighbors
// 2. requestSent: a receiver sends a high-priority request message to a sender
// 3. requestArrived: a request message gets to a sender
// 4. dataSent: a sender sends a data segment
// 5. dataArrived: a data segment arrives to a receiver
// 6. joinSent: a join message to the tracker
// 7. joinArrived: a join message reaches the tracker
// 8. responseSent: a response message sent by the tracker
// 9. responseArrived: a response message reaches the receiver

//10. scheduleStarted: a scheduling period started.
// 11. scheduleEnded: a scheduling period ended.

//commet: how should we do when a scheduling period expires?
//There are two situations: 1. all scheduled segments arrived; 2. some segments are still in transmission.

void addHandler(Interface EventHandler); // add an additional event handler
void rmvHandler(Interface EventHandler); // remove an additional event handler
}

class EventQueue {
SortedMap<Long, Event> queue; // events sorted on its time
void dispatch(Event event); // sequentially invoke even handlers
}

class Simulator {
long simTime; // elapsed simulation time in msec
EventQueue events; // pending events that will be processed
void dispatchEvent(); // forever loop to process the next event
}

Some comments:
1. At the beginning, we should have a peer publish a video (or a trace file).
2. The join() and leave() methods in the Group class may be moved to the Peer class and each peer
should has a bitmap field.
3. We may add a Tracker class:
Class Tracker
{
URL url; //peers use this url to find the tracker
Vector<Peer> peers; //maintain a peer list to be quired by peers
Vector<InetAddress> SelectPeers(); //when a peer joins a group at the first time, it quires other peers from the
//tracker, then the tracker invokes SelectPeers() and returns
//a list of neighbors to that peer
void recordPeer(); //record information of a peer when it first connects the tracker or update it when some old
//information is already stored
//the information exchanged between a tracker and a peer may be <peerID, videoName>
// or <peerID, videoName, ip_Address, port> if we want to do simulation on different machines
}
4. If we really want to send video files between peers, we may need a Storage class to operate with files
5. We may design a superclass of all peers, trackers, and neighbors, as a typical networking server to deal with
network connections
6. In case of Network Coding when a peer joins a group it will receive segments that are 'n' seconds after the current
playback point. ('n' is a tunable parameter)

</pre>

Private:psim

2009-03-10T04:46:02Z

Ysa57:

This page documents the development of a discrete event simulator for P2P video streaming applications. This simulator captures important features of data-driven video streaming systems. In particular, it is designed to evaluate: (i) the performance of various segment scheduling algorithms; (ii) the potential of network coding in multi-layer P2P video streaming systems.

= Class Diagrams =

* use long for time/offset in msec, which has a rollover time 24.85 days

<pre>

class Layer { // video layer, we divide each layer into fixed size blocks, we keep track of
// block size and no blocks here
int layer; // layer number it belongs to, set to zero for nonscalable frame
int blockSize; // blocks are fixed size, in bytes
int noBlocks; // how many block here
int dataSize; // aggregate size of all blocks
}

class Frame { // video frame, read from trace file
int no; // serial number
long deadlineOffset; // deadline offset compared to the start of the video, in msec
int totalSize; // total frame size in bytes, including all layers
Hashtable<Integer, Layer> layers; // reference to layers of this frame, key is the layer id
}

class Segment { // packetized frames
int no; // serial number
Vector<Frame> frames; // reference to included frame
int totalSize; // aggregate size in bytes
}

class Video { // a media file, shared by a group of peers
String filename; // video trace file path and name
Hashtable<int, Frame> frameTrace; // frames read from the trace file
Hashtable<int, Segment> segmentTrace; // segments generated by the prepareSegments(...)
void prepareSegments(int noFrame); // packetize frames into segment,
// noFrame indicates how many frames should we put in one segment;
// we might implement other packtization schemes later.
}

class Neighbor { // keep track of what my neighbor has done
Peer peer; // peer instance, for accessing availability info
int estimateRate; // estimated rate (maybe historical)
Connection conn; // e2e connection between us and another neighboring peer
}

class Tracker { // holds a set of groups/videos
Vector<Group> groups; // all the video groups
}

class Peer { // represent a running peer
int ingressBW; // incoming bandwidth in bps
int egressBW; // outgoing bandwidth in bps
Vector<Neighbor> neighbors; // peers that we may send requests to
BufferedMatrix matrix; // matrix of coefficients and encoded values up to now
NoEncodedBlocks noCodedBl; // keep track of No. of encoded blocks in each segment
Connection tracker; // control connection to the tracker
Hashtable<Video, VideoBufMap> vBufMaps; // points to the video-level buffer map
}

class Group { // peers that have downloaded or want to download a Video
Video video; // media shared among peers
Vector<Peer> peers; // peers in this group
Vector<Peer> join(Peer peer); // adding a new peer into this group, and return a list of senders
void leave(Peer peer); // removing a peer from this group
}

class Connection { // end to end network link between two peers
Peer peer1; // one end
Peer peer2; // the other
long delay; // transmission delay in msec
int e2eBW; // end-to-end bandwidth in bps
}

class VideoBufMap {
Hashtable<Integer, SegBufMap> sBufMaps; // points to segment bufmap
}

class SegBufMap {
Hashtable<Integer, LayerBufMap> lBufMaps; // points to layer bufmap
}

class LayerBufMap {
boolean avail; // availability bit for this (video, segment, layer) tuple
NCBuf ncBuf; // network coding structure
}

class NCBuf {
boolean servCapibility; // Serving capability of each segment
// show whether this segment is capable of serving other peers(applicable in NC)
int noCodedBl; // growable 2 dimensional array corresponding to segments and layers
// each element in this vector keep the No. of encoded blocks in the
// corresponding segment
BufferedMatrix marix; // coefficients and their corresponding encoded blocks up to now
}

class BufferedMatrix{ // save coefficients and their corresponding encoded blocks up to now
Vector<Vector<Integer>> coef; // coefficients of the corresponding encoded blocks
Vector <Integer>encodedValue; //encoded blocks
}

// XXX TODO XXX

class SlidingWindow{ // the sliding window which contains all the up-to-date segments at the peer
// set it to a fixed size, for example 1 minute of videos
int startOffset; //the offset of the starting frame compared with the start of the video
int endOffset; // the offset of the ending frame compared with the start of the video
double slideSpeed; // the speed of sliding. The window goes forward continuously (or periodically?) at
// the speed of the streaming rate.
void getSlidingWindowSize(); //get the size of the sliding window
}

class exchangeWindow{ // the exchange window is the front part of the sliding window.
//The unavailable segments in exchange window will be requested by the peer
//usually we set it to a fixed size, for example, 10 seconds of video
// the field of this class is similar to that of the SlidingWindow class
int startOffset;
int end Offset;
double slideSpeed;
void getSlidingWindowSize()
}

interface Scheduler{ // any class wants to do scheduling should implement this interface
void schedule() throws scheduleException; // the scheduling period is specified in the specific scheduling algorithm class
}

class scheduleException{

}

class SchedulingResult{ // this class is used to record scheduling results and do some statistics,
// for example, calculate the average delivery rate
Tuple<int, int, double> log; //log file of the results. Each item of the tuple specifies the peerID, segmentID and
// the starting time for the peer to transmit the segment
double getDeliveryRatio(); //calculate the average delivery ratio
// should add more detail here
}

class SEFF implements Scheduler{ // the Serial Earliest Finish-time First scheduling algorithm
int schedulingPeriod; // scheduling period, for example, 2 seconds
void schedule(); //implement the Scheduler interface
SchedulingResult result; // the scheduling results stored here

}

class LRF implements Scheduler{ // the Local Rarest First algorithm
int schedulingPeriod; // scheduling period, for example, 2 seconds
void schedule(); //implement the Scheduler interface
SchedulingResult result; // the scheduling results stored here
}

class RndGen { // common random number/event generators, to deal with
// 1. event: add new receiver for a group/video
// 2. event: remove a receiver from a group/video
// 3. number: peer's bandwidth
}

class SimException {

}

Interface EventHandler {
void handle() throws SimException; // callback function
}

class Event {
long time; // when this event happens
Peer src; // which peer generates this event
Peer dst; // whom is destinate of this event
Vector<EventHandler> handlers; //process an event and update states accordingly
int type; // enum, see below
// 1. connect: peer 1 makes a connection to peer 2, and add each other into neighbors
// 2. requestSent: a receiver sends a high-priority request message to a sender
// 3. requestArrived: a request message gets to a sender
// 4. dataSent: a sender sends a data segment
// 5. dataArrived: a data segment arrives to a receiver
// 6. joinSent: a join message to the tracker
// 7. joinArrived: a join message reaches the tracker
// 8. responseSent: a response message sent by the tracker
// 9. responseArrived: a response message reaches the receiver

//10. scheduleStarted: a scheduling period started.
// 11. scheduleEnded: a scheduling period ended.

//commet: how should we do when a scheduling period expires?
//There are two situations: 1. all scheduled segments arrived; 2. some segments are still in transmission.

void addHandler(Interface EventHandler); // add an additional event handler
void rmvHandler(Interface EventHandler); // remove an additional event handler
}

class EventQueue {
SortedMap<Long, Event> queue; // events sorted on its time
void dispatch(Event event); // sequentially invoke even handlers
}

class Simulator {
long simTime; // elapsed simulation time in msec
EventQueue events; // pending events that will be processed
void dispatchEvent(); // forever loop to process the next event
}

Some comments:
1. At the beginning, we should have a peer publish a video (or a trace file).
2. The join() and leave() methods in the Group class may be moved to the Peer class and each peer
should has a bitmap field.
3. We may add a Tracker class:
Class Tracker
{
URL url; //peers use this url to find the tracker
Vector<Peer> peers; //maintain a peer list to be quired by peers
Vector<InetAddress> SelectPeers(); //when a peer joins a group at the first time, it quires other peers from the
//tracker, then the tracker invokes SelectPeers() and returns
//a list of neighbors to that peer
void recordPeer(); //record information of a peer when it first connects the tracker or update it when some old
//information is already stored
//the information exchanged between a tracker and a peer may be <peerID, videoName>
// or <peerID, videoName, ip_Address, port> if we want to do simulation on different machines
}
4. If we really want to send video files between peers, we may need a Storage class to operate with files
5. We may design a superclass of all peers, trackers, and neighbors, as a typical networking server to deal with
network connections
6. In case of Network Coding when a peer joins a group it will receive segments that are 'n' seconds after the current
playback point. ('n' is a tunable parameter)

</pre>

Private:psim

2009-03-10T01:09:19Z

Ysa57:

Private:psim

2009-03-05T22:22:55Z

Ysa57:

Private:psim

2009-03-05T20:28:27Z

Ysa57: