Chapter 4.1 Multiplexing
Physical layer
Deals with sharing of transmission systems by several connections or information flows
Capacity of transmission system is the Bandwidth
Hertz is for analog; bits/sec is for digital
Use multiplexing when individual connection BW use is much smaller than available BW
Frequency Domain Multiplexing
BW is divided into a number of frequency slots that can accommodate the signal of an individual connection
BW for each user is BW/m
Guardband reduces the number of users in a BW
The combines signal is a group
Supergroup – combined group
Mastergroup – combined super group
Time domain Multplexing
High speed line that uses temporal interleaving
Connection generates a signal that produces one unit of information every mT seconds
Transmitted bits are organized into frames that are divided into equal sized slots
Signal can send one unit of information every T second
Transmission line speed is determined by (framing bit + # of slots) x #frames/sec
Slot size and repetition rate determine the bit rate
Framing bit allows the receiver to determine the beginning and end of frames
To fix synchronization problems, TDM have been designed to operate at a speed slightly higher than combined speed of inputs
Wavelength Division Multiplexing
Optical domain version of FDM
Major difference WDM has much larger gaurdbands
Various optical devices such as prisms and diffraction grating used to combine and split color signals
Send a number of wavelengths at a certain data rate
SONET
Frame structure
Section – span of fiber between 2 adjacent devices
Line – span between 2 adjacent multiplexers (encompasses several sections)
Path – Span between 2 SONET terminals at the endpoints of the system encompass one or more lines
Frame consists of byte (8bits) arrays of 9 rows x 90 columns, so if frame rate is 8000 times per second then the overall bit rate is
8 bits x 9 rows x 90 columns x 8000 frame/sec = 51.84 Mbps
The first three 3 columns are section and line overhead
Section overhead – interpreted and modified at every section termination, used for providing framing, error monitoring, and other section management functions
A1, A2 – overhead for indicating beginning of frame
B1 – carries parity checks
The last 3 bytes provide data communication between regenerators
Line overhead – is interpreted and modified at every line termination, is used for synchronization and multiplexing
H1,H2,H3 – 1st three bytes play a crucial role in multiplexing
B2 – used to monitor bit error rates in a line
K1,K2 – used to trigger recovery in case of faults
Inforamation payload – the last 87 columns x 9rows of the arry contain one column of path info
This path info is not strictly aligned, the first 2 bytes of line overhead are a pointer to indicate where the byte payload begins, so SPE can spread over multiple frame, and provided multiplexors with add and drop capability
It is used to monitor path performance and indicates content and status of end to end transfer
Spe byte array of 9 rows 87 columns of payload
For STS-n you have 9 rows with 3n section/line overhead, 87n payload columns
Mapping of SONET Frames
In each SPE 84 columns are set aside and divided into 7 groups of 12 columns so each gourp can be divided as 12 columns x 9 rows x 8 bit/byte x 8000 samples/sec = 6.912 Mbps
Each 12 x 9 space has 108 individual voice channels since a voice channel is equal to 8x8000 bits/second
Each mapping is developed so it can accommodate 4 T-1 carrier signals (4x24 = 96 < 108) or 3 CEPT-1 (3x32 = 96 < 108)
SPE can frame can handle a max of 7number or groups x 4 number of T-1 carrier signals = 28 T-1 carrier signals
4-3 Transport Networks
-provide high bit rate connections to clients at different locations
-SONET contribution to networks add-drop multiplexors, got rid of need to Demux and mux for tributary removal or insertion
Chapter 5 Peer to Peer Protocols
Quality of Service
Specifies a level of performance
Reliability in terms of probability of error, loss, incorrect delivery
May address delay (1) constant xfer value (2) some limit value its not to exceed
Best effort service – effort is made in delivery but no guarantees are made
Services
-Arbitrary message size or structure
-Sequencing
-Reliability
-Timing
-Pacing
-Flow Control
-Multiplexing
-Privacy, integrity and authentication
Hop by hop
-handled by the lower levels of the OSI model
-the DLL takes packets from the network and encapsulate them into frames and xfers across the link
-frames arrive in order with small delay
-Used when errors are frequent
-Nodes do error checking, ACK statements
-initiates error recovery quicker and give more reliable service
-processing at each node is more complicated
End to End
-the xport layer accepts messages from higher level and xfers these messages across the network
-exchange of segments is accomplished by using network layer services
-removes error control from intermediate nodes
-when errors are infrequent
TCP is an end to end mechanism
Datagram mode – packets from the same end systems are routed independently, packet can take different routes and arrive out of order
For PDU’s
Layer n + 1 is packets
Layer n is frames
Stop and Wait
-Delivered correct w/o errors, duplication or gap
Slast = 0, Rnext =0
Xmitter
RDY waits for upper layer request
If (RQ) FRM prepared hasHDR, SEQ # Slast, the pkt, and CRC, TMR started, state = WAIT
State = WAIT until ACK or timeout, accepts no pkts of upper layer
If(TO)FRM retransmitted, TMR reset, State = WAIT
If(ACK) Ignores all other ACK’s when the correct one is sent, Rnext = (Slast + 1) mod 2 send is updated to following value xmit is back to ready state
Rcvr
always in ready state
when frame arrives the receiver accepts and checks for errors
if slast = rnext and no errors the receive sequence # is updated to Rnext + 1 mod 2
if error is found or wrong sequence # no action taken
Works well in channel with low propagation delay
Inefficient if prop delay > time to xmit
Line efficiency = amount of data sent/amount of data possible to send
Delay BW Product = product of hit rate and the delay that elapse before action takes place
Tprop – time first bit is introduced into the channel and then sent
Tframe – time after the first bit is received until the end of frame is received
Tproc – time to prepare ACK
Tack –transmission time in SW protocol
So the to for SW is 2tprop + 2tproc + tACK + tframe = 2(tprop +tproc) + nf/R + na/R
Nf = # bits in frame na = #bits in ACK R is the bit rate of xmission channel
The effective info transmission rate is nf – no/to = number of information bits delivered/ total time to deliver
The xmission efficiency is given by the ratio of Reff to R
Gammao = nf-no/to/R; 2(tprop + tproc) R is the delay BW product or reaction time
Probability
Suppose 1 in 10 frames gets through ok the (1-Pf) = 0.1 then on average rames will have to be xmitted 10 times to get through, we have 1/(1-Pf) are required for a general value of Pf in frame xmission if the frame xmission errors are independent
SW requires tsw = to/1-Pf
Therefore the efficiency is defined by gammaSW = nf-no/tsw/R
1-Pf = (1-BER)nf
Go Back N
Has a window size, kept larger than the delay bandwidth product to ensure channel or pipe is kept full
-when an error occurs the receiver ignores frame errored and all subsequent frames eventually xmitter reaches max outstanding frames & is forced to GB – n frames and begin retransmitting
given a timer for bursty xfic
-Slast – last xmitted frame not ACK
Srecent – # of most recentlyxmitted frame
-must buffer frames w/o an ACK
-the sending window has the size of Slast being the lower end value and Slast + Ws -1 being the upper end
-the window is not allowed to move forward until the send window slides forward with the receipt of a new acknowledgemnt
-the receiver maintains a receive window of 1 frame
-the receiver can sned an out of order ACK if it has correctly received it prior frames
-if error free ACK is received w/ Rnextin the range between Slast and Srecent
Slast <= R next
Rnext <= Srecent
Protocol
It is initialized by the window size being set to {0,1,…Ws-1} and Slast = 0 the receiverwindow is set to {0} & Rnext
Xmitter
-when the sned window is now empty the xmitter isin the ready state waiting for the request from the higher layer
-frame is prepared that consistes of a header, sequence number S recent set to the available number in send window the packet and CRC if Srecent = Slast + Ws-1 then send window is empty and goes into blocking mode
-If an ACK is received w/ Rnext in range of Slast to Srecent then the window slides forward by setting Slast = Rnext and the window is set to Slast + Ws -1
-If ACk is received outside that range frame is discarded
-If the timer expires resend Slast and all subsequent frames and resets the timer for each frame
Receiver
-The receiver is always in ready state waiting for notification of ariveing frame
-If no errors & received sequence # (Rnext) the frame is accepted and the sequence # incremented
-If frame is wrong or has sequence number errors it is discarded
SW and GBN same complexity
Bidirectional Links
-frame errors are ignored
-subsequent frames that are out of sequence but error free are discarded after the ACK has been examined, R next is used to update the local Slast
-I-frame timeout should be selected so that it exceeds normal frame ACK
Tout = 2tprop + 2tmax frme + tproc, tmax frame – max length of xmission time
Performance Issues
The total avg time to xmit w/ GBN is tGBN = tf + Pf(Wstf/1-Pf)
Gamma GBN = nf-no/tGBN / R
Selective ARQ
-receive window is larger than 1 frame to allow out of order
-only individual frames retransmitted
Receive window has the size Rnext + Wr -1 were Wr is the maximum # of frames the receiver is willing to accept
Unlike GBN the receive value can be advanced several frames
The max window size is Wr = 2^m-1
Protocol <Ws = 0..Ws-1, Slast = 0. Wr =0..Wr -1,Rnext =0>
Xmitter
Ws = 0 ready
-when a frame is sent Srecent is set to lowest available # in send window, CRC, header and timer started
-If Srecent = Slast + Ws -1 then the send window is set to zero and put in blocking state otherwise in ready state
-If an error free ACK is received w/ Rnext between Slast and Srecent then the sned window slides forward by setign Slast = Rnext & the max send window set to Slast + Ws-1
If NAK is received the Slast & upper boundthen frame with that sequence is resent the slide window can advance by setting Slast = Rnext & the max window Slast + Ws-1
If Ack not in range is received no action taken
If timer expires the xmitter resneds the frame and timer resets
If in blocking state if an error free NAK is received w/ Rnext in range b/n Slast and Srecent then frame w/ the sequence # Rnext is retransmitted, and if appropriate the window slides forward setting Slast = Rnext and reseting max window size
RCVR
-always in ready state
-when a frame arrives the receiver chackes the frames for errors
-If no errors are detected and Wr range the the frame is accepted and buffered and ACK is sent
-If the receive sequence number is Rnext & rnext + 1 –Rnext + k-1 have all ready been received then the receive sequence # is incremented to Rnext + k the window slides forward
-If the frame has no errors but is outside the range the frame is discard and ACK sent sequence # Rnext
-If the frame has errors no action is taken
Perfromance most efficient
Tsr = tf/(1-Pf) <snet independently of other frames>
Efficiency is gamma sr = nf – no/tsr/R only valid is Ws is larger than the delay BW product
Then the xmitter can runnout of sequence numbers
If you neglect header & CRC then the efficiency of 3 protocols
Gammasr = (1-Pf) gammaGBN = (1-Pf)/(1+LPf) gammaSW = (1-Pf)/(1+L) where L = 2(tptop+tproc)R/nf
Chapter 7.1
Connection oriented service
-setup procedure
initialize state information
-connection release removes the state information and releases resources allocated to connection
-suitable for stream of information
Connectionless
Not connection setup procedure
Self contained blocks of information are transmitted and delivered using appropriate address information
-information blocks transmitted independently
-reliable xfer done with ACK
Out of order xfer can happen
Connectionless service
-only the 2 basic interactions b/n transport layer (user of service) and NW (provider of service): req. to the NWL to send a pkt or the notification for NWL that the pkt arrived
-the user does not need to inform ahead of time it wants to send a pkt
-Puts the total responsibility for error control sequencing and flow control on end system transport layer
Connection Oriented
-the xport layer cannot request transmission until a connection has been setup
-NWL must be informed about the flow
-During connection setup parameter related to usage and Qos are negotiated an new resources allocated to ensure user flow handled as required
-Connection release procedure
-Entails greater complexity
Reasons for keeping network services to minimum
1)End to end argument – NW service should provide minimum functionality to meet application performance
2)Scalability – adding only necessary complexity enhances scalability
NWL – functions that route and forward pkt
-handle functions that happen at every node: + Priority and scheduling to ensure Qos
+congestion control
+independent of underlying transmission system
Section 7.3
-a message switch operates instore forward fashion
-message is completely stored before it is sent forward
-Each switch performs an error check if no error detected the switch examines header to determine the next stop in the path if errors are detected a retransmission is requested
-can achieve high utilization
-loss of messages occur when a switch has insufficient buffering, end to end mechanisms are required to recover from losses
-if retransmission rate and propagation delay are the same then it is tau + T for every hop, so for 3 hops 3tau+ 3T
long messages are not desirablefor lines with noisy transmissions or interactive applications because delay of long messages holds up progress of whole system
Packet switch
Better for interactive applications
Termed Datagram Connectionless Packt Swtiching
Each packet is routed independently of the network
-each Packet has an attached header the provides all info required to route packet to its destination
-each packet routed independently
Minimum delay of message in pkts is P = T/3 since each pkt is a third in size to transmit assuming tau and T are equal each hop is equal to tau + P or tau + T/3, so the final result with 3 hops is 3tau + 3P + 2P
In general if path following a sequence of packets consists of hops with identical propagation delays and transmission speeds then the delay incurred in k packets given by Ltau + LP + (k-1)P the delay by message switching is Ltau + LT = Ltau + LkP
Virtual Pkt switching
-involves establishment of a fixed path b/n source and destination prior to transfer of packets
-setup procedure takes place before any packets can flow through the network
-virtual circuits reside at the network layer
-> minimum delay similar to pkt switch with the addition of setup
->virtual circuit guarantees order
-> abbreviated headers
VCI – virtual circuit identifier, the input of every switch is used to access the table, can also setup priority
Virtual circuits can do table look up through direct indexing
-resource allocated during call setup ensure path can handle traffic
Disadvantages
-switches in the network need to maintain information the flows that pass the switches, this stat information can grow rapidly
-if a faulty connection occurs all the connection must be re set up
cut through pkt switching
minimum delay of sum of tau + one T, assumes line are instantly available for retransmission
cut through desirable in speech or virtually error free network
Chapter 7.4 Routign in Packet networks
Concerned with determining feasibility paths or routes for packets
-a routing algorithm must have global knowledge
-Goals of the routing algotirhm
1) Rapid accurate delivery of packets
2) Apadtability to changes in topology or failures
3) Varying to source destination traffic loads
4) ability to route away from congested links
5) ability to determine connectivity of network(reachability info)
6) ability to avoid routing loops
7) Low overhead-obtains connectivity information by exchanging control messages with other routing systems
Static Routing
-pre-computed placed in routing table remained fixed for some time
-good in small network with little variance in traffic or network topology fixed
-Has problems if network size increases, xffic load changes
-Biggest disadvantage in ability to react to changes in NW
Dyanmic
-continuously learns the state of the network
-each node computes best path information
-disadvantage increases complexity of each node
Centralized – a network control center computes all paths and then uploads info to nodes
Distributed – nodes cooperate by sending messages
Usually scales better
Produces inconsistent results can lead to loop
Once a virtual circuit is set up all packets go along that path
Datagram each path is detemined independently
Local VCI vrs Global
-In local more VCI can be assigned
-only have to guarantee uniqueness onlocal link
Hieracrchal Routign
-size of routing table reduced
Flodding
-calls for incoming packet may be sent to every packet expect the on e that sent it
-effective at startup or when survivability is an issue, or broadcast to all nodes needs to be sent
Problems: swamp the NW
Solution: TTL, or adding an identifier
Deflection Routing
-each node tries to send packet to preferred part, if it is busy it is deflected to another part
-works well in regular topology
-advantage – nodes can be bufferless
-disadvantage – no gaurantess in ordering of deleivery
Shortest path routing
Cost ~ 1/capacity – higher cost for lower capacity links
Cost~ packet delay – cost proportional to packet delay
Cost~ congestion – cost propagation to congestion
Chapter 8
IP Packet – 20 bytes can be up to 40 bytes sent in network order