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
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 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 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 end Offset;
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 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
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:
* 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)
