Private:psim

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