1) Character count: • This framing method uses a field in the header to specify the number of characters in the frame
Computer and Data Networks, 3 Date Link Layer Framing – Character count (b) Four examples of byte sequences before and after stuffing
Computer Communication Networks Lecture No 6 Computer Network Lectures 1- Data link Layer:- For example, if the character count of 5 in the second
24 jui 2021 · 1 Implementing the data link layer framing methods i Character count 2 Character Stuffing and destuffing 3 Bit Stuffing
When the data link layer at the destination sees the character count, it knows how many characters follow and hence where the end of the frame is This
To provide service to the network layer, the data link layer must use the service example, if the character count of 5 in the second frame of Fig
The trouble with this algorithm is that the count can be garbled by a transmission error For example, if the character count of 5 in the second frame of fig (b)
If ETX appears in the data introduce a special character DLE (Data No bit or byte stuffing ? Example: ? Synchronous Optical Network (SONET)
23 nov 2021 · Include the character count in the header of the frame Example: the byte-oriented Digital Data Communications
Character count with some other mechanisms 4 Physical Layer Coding Violation A Flag Byte or Byte Stuffing: Examples ® “To stop input please enter X and
Computer Network Lectures To provide service to the network layer, the data link layer must use the For example, if the character count of 5 in the second
Computer and Data Networks, 3 Date Link Layer 1 Framing – Character count A character (b) Four examples of byte sequences before and after stuffing
COMPUTER NETWORKS FOURTH (b) Four examples of byte sequences before and after stuffing embedding the character code length in the framing
CSE 123: Computer Networks Same as bit stuffing, except at byte (character) level ♢ Kind of like Phy-layer signaling: sample at specific intervals ♢
◆#Arbitrate which nodes can send frames at any point in time ◆#Not always necessary; e.g. point-to-point duplex links
◆#Multiplexing◆#Determine appropriate destination for a given frame ◆#Also not always required; again, point-to-point
◆#Multiple senders and/or receivers can time multiplex the link ◆#Each frame can be separately addressed
◆#Provides manageable unit for error handling ◆#Easy to determine whether something went wrong ◆#And perhaps even to fix it if desired◆#Wraps payload up with some additional information ◆#Header usually contains addressing information ◆#Maybe includes a trailer (w/checksumÑnext lecture)
◆#Basic unit of reception◆#Link either delivers entire frame payload, or none of it ◆#Typically some maximum transmission unit (MTU)
◆#Some link layers require absence of frames as well ◆#I.e., minimum gaps between frames CSE 123 Ð Lecture 4: Framing"5 Payload Header Trailer◆#Fixed length (bits) frames ◆#Fixed duration (seconds) frames ◆#Explicit delimiters indicate start and/or end of each frame
È#Alternatively, just start and a length field ◆#Misidentifying frame start and end leads to errors ◆#Topic for next lecture◆◆#May waste space (padding) for small payloads ◆#Larger payloads need to be fragmented across many frames
◆#Requires explicit design tradeoff ◆#ATM uses 53-byte frames (cells) ◆#Why 53? 48 + 5. Why 48? Average of 32 and 64.◆#To avoid overhead, weÕd like variable length frames ◆#Each frame declares how long it is ◆#E.g. DECNet DDCMP
◆#Why not explicitly include a length field? ◆#Must correctly read the length field◆#Could be a special byte/bit patter in header/trailer ◆#Unique (non-data) physical-layer symbol
◆#Reserving physical layer symbols reduces efficiency ◆#CanÕt use that symbol to transmit data◆ ◆#But using bits/bytes in data stream is problematic ◆#What if sentinel happens to appear in the data?◆#Insert bytes/bits into data stream to make sure that sentinel (flag) does not appear in payload
◆#Avoid sentinel bit pattern in payload data ◆#Commonly, sentinel is bit pattern 01111110 (0x7E) ◆#Invented for SDLC/HDLC, now standard pattern
◆#Any time five ones appear in outgoing data, sender inserts a zero, resulting in 01111101 ◆#Any time receiver sees five ones, it removes next zero◆#If there is no zero, there will either be six ones (flag) or ◆#It declares an error condition◆ ◆#Note bit pattern that cannot appear is 01111111 (0x7F)
◆#WeÕre adding extra non-data bits to the stream ◆#Not using full capacity of physical layer
◆#Suppose we use flag 01 n◆#We need to stuff anytime we get (n-1) 1s ◆#Assuming uniform bit distribution, happens L/2
n times in frame of length L ◆#Tradeoff in flag length◆#Long packets want long flags (less likely to stuff) ◆#Short packets want short flags (always need to add flag) ◆#Overhead for n=6, long packet: L + L/2
6 + higher order terms = L + L/64 = 1.015L; 1/1.015 = approximately 98.5% efficient ◆#Real problem is bit stream is now variable length◆◆#Same as bit stuffing, except at byte (character) level ◆#Generally have two different flags, STX and ETX ◆#Found in PPP, DDCMP, BISYNC, etc.
◆#Need to stuff if either appears in the payload◆#Have another special character, DLE (data-link escape) ◆#New problem: what if DLE appears?
◆#Stuff DLE with DLE◆ ◆#Could be as bad as 50% efficient to send all DLEs◆#Control expansion of payload size due to stuffing ◆#Important for low-bandwidth links or fixed-size buffers
◆#Idea is to use 0x00 as flag, and replace all zeros with distance to next 0x00. ◆#Break frame up into runs without zeros, encode by pre- pending each run with length ◆#Pretend frame ends in 0x00. Max run is 254; if no zeros pre- pend with 255 (0xFF)◆#So far, weÕve based framing on whatÕs on the wire ◆#Any bit errors may throw off our framing ◆#What happens with missed flag? Spurious flag?
◆#An alternative is to base framing on external clock◆#Kind of like Phy-layer signaling: sample at specific intervals ◆#This is what SONET does, among others
◆#Significant engineering tradeoffs◆#No extra bits needed in the data stream itself, but◆ ◆#Need tight clock synchronization between sender and receiver
◆#Can synch clock just like PLLÑlook for periodic signal bits ◆#No need to stuff; signal pattern is unlikely, so wonÕt be
periodic in data ◆#Keep sync within frames with transitions◆#Encoded using NRZ, but ◆#Data is XORed with special 127-bit pattern ◆#Creates lots of transitions, makes signal pattern unlikely
◆#Frame contains 9 rows of 90 bytes each (810 bytes) ◆#First 3 bytes of each row are header
È#2-byte sync patter, one byte for ÒflagsÓ◆#SONET actually defines networking functionality ◆#Conflates layers; weÕll talk more in future lectures ◆#Thinks about how to move frames between links
◆#Higher-speed links are multiples of STS-1 frames ◆#E.g., STS-3 is three times as fast as STS-1 ◆#Frames are byte-wise interleaved ◆#Ensures pace of embedded STS-1 frames remains same CSE 123 Ð Lecture 4: Framing"18 STS-1 FH STS-1 FH STS-1 FH STS-3 FH A B C A A B C◆#STS-n can send n independent frames ◆#Effectively n parallel links sharing same physical media
◆#Alternatively, can concatenate into one jumbo frame ◆#STS-nc: one link whose bandwidth is n times STS-1 ◆#Each SONET frame takes same time to arrive; Why?not too difficult to synchronize clocks such that first byte of all incoming flows arrives just before sending first 3 bytes of outgoing flow
◆#Clock drift may confuse frame boundaries ◆#Read the end of one frame and beginning of the next
◆#What happens if there are bit errors on channel? ◆#We might misinterpret flags as data or vice versa ◆#What will the frames look like? ◆#In general, need some way to make sure weÕre OK ◆#Error detection (and perhaps correction) topic for next time◆#Data Link Layer provides four basic services ◆#Framing, multiplexing, error handling, and MAC
◆#Framing determines when payload starts/stops ◆#Lots of different ways to do it, various efficiencies ◆#Sentinel-based framing requires stuffing ◆#Increases the size of the packet ◆#Alternatives include fixed size frames ◆#SONET uses timing-based framing ◆#Gets complicated when trying to switch links