Transcript Compression

Traffic Characterization
• Specifies the traffic of a flow using parameters like
bandwidth, delay, delay jitter requirements
– for bursty traffic, bandwidth is normally specified in
terms of average packet rate, maximum packet rate,
burst duration
• Facilitates admission control
• Facilitates traffic policing
Traffic Shaping
• Technique to regulate a stream’s traffic into certain patterns
or shapes so that it is easy to describe and police.
• Leaky bucket
• (r,T)-Smooth
• Token bucket
• Traffic reshaping using regulators inside the network
Leaky Bucket Traffic Shaper
• Finite sized bucket, B
• Data leak out to the network at a constant rate, r
• Bucket size B limits the data built up in the bucket waiting
to be transmitted to the network
– determines how bursty the incoming traffic can be
– together with rate r determines the max data delay, B/r
• Leaking rate r is chosen such that the data discard rate is
small with a large buffer size (effective bandwidth)
Leaky Bucket (continued)
• Simple and easy to implement
– each flow’s traffic is managed by a simple FIFO buffer
with a timer set to go off every 1/r units time.
• A flow’s characteristic is described simply by the leaking
rate r
• The network delivers the required QoS by keeping sum of
the effective bandwidths of all streams below its capacity
• Limitation -- can’t be used to shape very bursty traffic
(r, T) -Smooth Traffic Shaper
• A flow is permitted to inject no more than r bits of data in a
time interval of T.
• T is fixed throughout the network; r varies on a per flow
basis.
Token Bucket Traffic Shaper
• Token placed a leaky bucket of size C at a constant rate s.
• Packets are placed in the data buffer and each is
transmitted for a token from the bucket.
• No token in the bucket, no transmission of packets.
• When token bucket is full, tokens are discarded
• Burstiness is bounded because the flow never sends more
than C + t/s packets in an interval t and the long term
transmission rate does not exceed s.
Queue-Scheduling Disciplines
• Decide which packet is served next and therefore, affects packet delay
and bandwidth of connections
• Work conserving -- the system may not be idle if there are packets in
the queue
• Non-work conserving -- each packet is assigned an eligibility time.
The system is idle when no packets in the queue are eligible for
transmission.
• Type of scheduling scheme determines buffer space requirements,
delay, delay jitter.
– Work conserving disciplines need less buffer and cause shorter delay but
cannot bound delay jitter tightly
– Non-work conserving schemes need larger buffer, cause longer delay but
can bound delay jitter tightly
Weighted Fair Queueing
• Fair queueing : if n active flows share an output link, each
flow gets 1/n of the link bandwidth
• In WFQ, connections are given different fractions of the
bandwidth based weights
• End-to-end delay is bounded if a flow shaped at the edge
of the network by a token bucket with leaky bucket rate
control passes through network nodes with WFQ
WFQ (Limitations)
• Finish number computation
• WFQ scheduler requires per connection scheduler state
and can be expensive for schedulers that serve large
numbers of connections
• Requires explicit sorting of the output queue
Virtual Clock
• Allocates each packet a virtual transmission time
• Emulates STDM to determine the virtual transmission time
(in STDM, a connection is allocated with periodical
transmission timeslots)
• VC can provide a deterministic bandwidth guarantee but
cannot provide a deterministic delay guarantee
Delay Earliest Due Date
• Extension of EDD that specifies the process by which the
scheduler assigns deadlines to packets.
• During call set up, each source negotiates a service
contract with the scheduler for a delay bound guarantee.
• Deadline assigned to a packet from a source is the
expected arrival time added to the delay bound at the
server. For example, if a client assures that it will send
packets every 0.2 s, and the delay bound at the server is 1
s, then the kth packet from the client will get a deadline of
0.2k+1.
Jitter Earliest Due Date
• Extends delay-EDD to provide delay jitter bounds (that is,
a bound on the maximum delay difference between two
packets).
• After a packet has been served at each server, a field in its
header is stamped with the difference between its deadline
and the actual finishing time. A regulator at the entrance of
the next server holds the packet for this period before it is
made eligible to be scheduled.
Priority Schemes
• Packet discard problem due to buffer overflow
• Two ways to assign packet priority:
– by application encoder
– by network traffic policing mechanism: when a flow
sends more data than the promised amount, the extra
data are tagged with low priority
Resource Reservation Protocols
• Resource management is key to providing QoS guarantees
to users
• Resource reservation protocol at the n/w layer
– performs no reservation of required resources itself; it
is only a vehicle to transfer info about resources
required and to negotiate QoS values users desire
• Reservation protocols rely on resource administration
functions in aeach subsystem to enforce and schedule
resource accesses during data transmission phase
Stream Transport Protocol (ST II)
• Experimental Internet protocol designed to transmit realtime data
• Provides connection oriented service, supports multicast
and QoS negotiation
• Data can only be sent after a stream has been established
successfully (one to many connection, equivalent to a
flow)
ST and SCMP
• A datagram forwarding protocol called ST
• A connection management protocol called ST Control
Message protocol (SCMP)
• ST forwards data packets down routing trees created by
SCMP
• SCMP has 17 different messages corresponding to
different flow management services (messages used to
establish a flow to one or more recipients, remove users or
add new users, change existing flow’s flow spec., eroor
recovery and status checks
ST II Connection Setup
• A flow’s distribution graph is source specific (one to
many) -- only one individual sender may use a particular
distribution tree
• Source ST agent generates a CONNECT packet listing the
flow spec. and initial set of participants
• Each intermediate ST agent processes the CONNECT
packet to determine the set of next hop subnets required to
reach all downstream receivers, installs multicast
forwarding state, reserves n/w level resources along each
next hop subnet
Connection Setup
• A receiver determines whether to join the group and
returns either ACCEPT or REFUSE message to the system
source. Flow Spec. may be updated along the way (may be
downgraded if a router determines (at each hop) it can’t
meet the requirements.
• Each router in turn examine the CONNECT message and
decide whether to accept and forward CONNECT message
to destinations they can reach. An intermediate router send
a REFUSE message if it can not reach a destination
Connection Setup
• Stream Source must wait for an ACCEPT or REFUSE
message reply from each initial receiver before beginning
data transmission.
• When flow spec. is modified and ACCEPT is received
from a receiver, the source must adapt to the low QoS for
the entire stream or reject the receiver in question by
sending it a DISCONNECT message
• Additions and deletions
– new users with lower QoS are denied access
– receiver sends a REFUSE message or source sends a
DISCONNECT message to delete an existing user
Evaluation
• Implementation complexity
• Complex state space
• Scalability to large multicast groups
– every destination must be explicitly listed in the
CONNECT message
– every destination must be acknowledge the CONNECT
message
– Sender may have to process hundreds of ACCEPT or
REFUSE messages
Streaming on the Web
• The contents of a compressed audio and/or video file are played out as
they are being received. A playout buffer helps to smooth the
variations in the time between each received packet in the stream
(delay jitter).
• Media player acts as the interface between the incoming compressed
media bitstream and the related sound and/or video output cards.
– For video, the browser first creates a window in the web page and passes
the coordinates of the window to the selected video media player.
•
– Video media player initializes the video card with the assigned coordinates
and decompresses the video bitstream from the playout buffer and passes
it to the video card for rendering
Media player consists of two parts : playout functions and control functions for
interactivity
Sequence
•
•
•
•
•
•
Browser sends a HTTP GET request to the web server
Web server responds by returning the contents of the meta file to the browser
Browser determines the media player to invoke from the “content type” field
and passes the contents of the meta file to the selected media player
Control part of the media player requests control part of the streaming server
to start a new session by sending RTSP SETUP request message (including the
port number allocated to RTP). In response the control part of the server
returns an RTSP accept message (with a unique session identifier)
Control part of the media player sends a RTSP PLAY request message; the
control part on the server side initiates the access and transmission of the
packet stream using the allocated port number of RTP in the header of each
UDP datagram
RTSP TEARDOWN request message is used when the user activates the
quit/end button
Session Initiation Protocol (SIP)
• Provides services for user location, call/session
establishment, and call participation management
• A simple request-response protocol -- both the request and
response are made through an application program called
the user agent (UA) which maps the request and its
response into the standard message format used by SIP
• Each UA comprises two parts, a UA Client (UAC), which
enables the user to send request messages (to initiate the
setting up of a call/session) and a UA server (UAS) which
generates the response message
Call/Session Set Up
• SIP name/address is similar to an email name/address. A single user
may have a number of alternative locations/addresses
• Calling host sends an INVITE request message to the local proxy
server (PS -A); the proxy server (PS-A) obtains the IP address of the
proxy server (PS-B) for the called host and the SIP in the proxy server
(PS-A) sends the INVITE request message to PS-B. PS -B determines
that the user is currently logged in (gets name/address from the SIP
message) and the IP address of the called host. If the called host can
accept the call, an INVITE response message is returned over the same
path. Receiving this the SIP in the calling host returns an ACK and the
two users/hosts start exchanging the info.
Session Description Protocol (SDP)
• To describe the different media streams involved in a
call/session
• Described in each SIP message body in text format:
– media streams (list of media types and format in each
SIP INVITE request message and a modified version of
that in the INVITE response message)
– stream addresses (destination address and UDP port
number for sending and/or receiving each stream)
– start and stop times (for broadcast sessions)
RTP
• The timing information required by the receiver to output
the received packet stream at the required rate is provided
by RTP
• RTCP is used to synchronize the two media streams prior
to carrying out the decoding the decoding operation
• RTP functions: (1) detecting missing packets and
compensating for lost packets as well as delay variations
(2) reconstructing bitstream (reordering the packets)
RTCP
• RTCP operates along side of RTP and shares information
with it
• Each RTCP has a different (UDP) port number associated
with it so that it can operate independently of RTP
• Periodic messages (RTCP packet) exchanged with the RTP
hosts/clients
– common system time clock for media synchronization
– QoS reports computed by the receiving RTPs
– participation reports
– participation details
IP Multicast
• A convention to identify a multicast address
• Each node must translate between an IP multicast address
and a list of networks that contain members of this group
• A router must translate between an IP multicast address
and a subnetwork multicast address to deliver a multicast
IP datagram on the destination network
• A mechanism for an individual host to inform routers (on
the same network as itself ) of its inclusion or exclusion
from a multicast group
IP Multicast (Contd.)
• Routers need to know which subnetworks include
members of a given multicast group.
• Routers need sufficient information to calculate the
shortest path to each network containing group members.
• A routing algorithm is needed to calculate shortest paths to
all group members.
• Each router must determine multicast routing paths on the
basis of both source and destination addresses.
IP Multicast (Contd.)
• IGMP (Internet Group Management Protocol) or ICMPv6 (Internet
Control Message Protocol) is used by hosts and routers to exchange
multicast group membership information
• MOSPF (Multicast Extension to Open Shortest Path First) enables
routing of IP multicast datagrams
• Each router attached to a LAN uses IGMP to maintain a current picture
of local group membership. Periodically each router floods group
membership information to all other routers in its area.
• Using Dijkstra’s algorithm, each router constructs the shortest-path
spanning tree from source network to all networks containing members
of multicast group (done only on demand).
• Unique spanning tree for a given source node
• Interarea multicasting