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
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)
