9/22/23, 9:49 AM CS425: Computer Networks: Lecture 01

Computer Networks (CS425)

Instructor: Dr. Dheeraj Sanghi

Prev | Next | Index

ISO-OSI 7-Layer Network Architecture

This lecture introduces the ISO-OSI layered architecture of Networks. According to the ISO standards, networks have been divided
into 7 layers depending on the complexity of the fucntionality each of these layers provide. The detailed description of each of
these layers is given in the notes below. We will first list the layers as defined by the standard in the increasing order of function
complexity:

1. Physical Layer
2. Data Link Layer
3. Network Layer
4. Transport Layer
5. Session Layer
6. Presentation Layer
7. Application Layer

Physical Layer
This layer is the lowest layer in the OSI model. It helps in the transmission of data between two machines that are communicating
through a physical medium, which can be optical fibres,copper wire or wireless etc. The following are the main functions of the
physical layer:

1. Hardware Specification: The details of the physical cables, network interface cards, wireless radios, etc are a part of this
layer.

Coaxial Cable Hybrid Cable Wireless Card Network Card

2. Encoding and Signalling: How are the bits encoded in the medium is also decided by this layer. For example, on the coppar
wire medium, we can use differnet voltage levels for a certain time interval to represent '0' and '1'. We may use +5mV for
1nsec to represent '1' and -5mV for 1nsec to represent '0'. All the issues of modulation is dealt with in this layer. eg, we may
use Binary phase shift keying for the representation of '1' and '0' rather than using different volatage levels if we have to
transfer in RF waves.

Binary Phase Shift Keying

3. Data Transmission and Reception: The transfer of each bit of data is the responsibility of this layer. This layer assures the
transmissoin of each bit with a high probability. The transmission of the bits is not completely reliable as their is no error
correction in this layer.
4. Topology and Network Design: The network design is the integral part of the physical layer. Which part of the network is
the router going to be placed, where the switches will be used, where we will put the hubs, how many machines is each

[Link] 1/5
9/22/23, 9:49 AM CS425: Computer Networks: Lecture 01
switch going to handle, what server is going to be placed where, and many such concerns are to be taken care of by the
physical layer. The variosu kinds of netopologies that we decide to use may be ring, bus, star or a hybrid of these topologies
depending on our requirements.

Data Link Layer

This layer provides reliable transmission of a packet by using the services of the physical layer which transmits bits over the
medium in an unreliable fashion. This layer is concerned with :

1. Framing : Breaking input data into frames (typically a few hundred bytes) and caring about the frame boundaries and the
size of each frame.
2. Acknowledgment : Sent by the receiving end to inform the source that the frame was received without any error.
3. Sequence Numbering : To acknowledge which frame was received.
4. Error Detection : The frames may be damaged, lost or duplicated leading to [Link] error control is on link to link basis.
5. Retransmission : The packet is retransmitted if the source fails to receive acknowledgment.
6. Flow Control : Necessary for a fast transmitter to keep pace with a slow receiver.

Data Link Layer

Network Layer

Its basic functions are routing and congestion control.

Routing: This deals with determining how packets will be routed (transferred) from source to destination. It can be of three types :

[Link] 2/5
9/22/23, 9:49 AM CS425: Computer Networks: Lecture 01
Static : Routes are based on static tables that are "wired into" the network and are rarely changed.
Dynamic : All packets of one application can follow different routes depending upon the topology of the network, the
shortest path and the current network load.
Semi-Dynamic : A route is chosen at the start of each conversation and then all the packets of the application follow the
same route.

Routing

The services provided by the network can be of two types :

Connection less service: Each packet of an application is treated as an independent entity. On each packet of the application
the destination address is provided and the packet is routed.
Connection oriented service: Here, first a connection is established and then all packets of the application follow the same
route. To understand the above concept, we can also draw an analogy from the real life. Connection oriented service is
modeled after the telephone system. All voice packets go on the same path after the connection is established till the
connection is hung up. It acts like a tube ; the sender pushes the objects in at one end and the receiver takes them out in the
same order at the other end. Connection less service is modeled after the postal system. Each letter carries the destination
address and is routed independent of all the others. Here, it is possible that the letter sent first is delayed so that the second
letter reaches the destination before the first letter.

Congestion Control: A router can be connected to 4-5 networks. If all the networks send packet at the same time with maximum
rate possible then the router may not be able to handle all the packets and may drop some/all packets. In this context the dropping
of the packets should be minimized and the source whose packet was dropped should be informed. The control of such congestion
is also a function of the network layer. Other issues related with this layer are transmitting time, delays, jittering.

Internetworking: Internetworks are multiple networks that are connected in such a way that they act as one large network,
connecting multiple office or department networks. Internetworks are connected by networking hardware such as routers, switches,
and [Link] is a solution born of three networking problems: isolated LANs, duplication of resources, and the lack
of a centralized network management system. With connected LANs, companies no longer have to duplicate programs or resources
on each network. This in turn gives way to managing the network from one central location instead of trying to manage each
separate LAN. We should be able to transmit any packet from one network to any other network even if they follow different
protocols or use different addressing modes.

[Link] 3/5
9/22/23, 9:49 AM CS425: Computer Networks: Lecture 01

Inter-Networking

Network Layer does not guarantee that the packet will reach its intended destination. There are no reliability guarantees.

Transport Layer
Its functions are :

Multiplexing / Demultiplexing : Normally the transport layer will create distinct network connection for each transport
connection required by the session layer. The transport layer may either create multiple network connections (to improve
throughput) or it may multiplex several transport connections onto the same network connection (because creating and
maintaining networks may be expensive). In the latter case, demultiplexing will be required at the receiving end. A point to
note here is that communication is always carried out between two processes and not between two machines. This is also
known as process-to-process communication.
Fragmentation and Re-assembly : The data accepted by the transport layer from the session layer is split up into smaller
units (fragmentation) if needed and then passed to the network layer. Correspondingly, the data provided by the network
layer to the transport layer on the receiving side is re-assembled.

Fragmentation Reassembly

Types of service : The transport layer also decides the type of service that should be provided to the session layer. The
service may be perfectly reliable, or may be reliable within certain tolerances or may not be reliable at all. The message may
or may not be received in the order in which it was sent. The decision regarding the type of service to be provided is taken at
the time when the connection is established.
Error Control : If reliable service is provided then error detection and error recovery operations are also performed. It
provides error control mechanism on end to end basis.
Flow Control : A fast host cannot keep pace with a slow one. Hence, this is a mechanism to regulate the flow of
information.
Connection Establishment / Release : The transport layer also establishes and releases the connection across the network.
This requires some sort of naming mechanism so that a process on one machine can indicate with whom it wants to
communicate.

References of Images

[Link] pci_combo_card_sm.jpg
[Link] 4/5
9/22/23, 9:49 AM CS425: Computer Networks: Lecture 01
[Link]
[Link] images/[Link] hybrid cable
[Link]
[Link]
[Link]
[Link] data_link_layer.gif
[Link]
[Link]
[Link] thesis_report/[Link]
[Link]
[Link]

back to top
Prev | Next | Index

[Link] 5/5
9/22/23, 9:49 AM CS425: Computer Networks: Lecture 02

Computer Networks (CS425)

Instructor: Dr. Dheeraj Sanghi

Prev | Next | Index

Session Layer

It deals with the concept of Sessions i.e. when a user logins to a remote server he should be authenticated
before getting access to the files and application programs. Another job of session layer is to establish and
maintain sessions. If during the transfer of data between two machines the session breaks down, it is the
session layer which re-establishes the connection. It also ensures that the data transfer starts from where it
breaks keeping it transparent to the end user. e.g. In case of a session with a database server, this layer
introduces check points at various places so that in case the connectoin is broken and reestablished, the
transition running on the database is not lost even if the user has not committed. This activity is called
Synchronization. Another function of this layer is Dialogue Control which determines whose turn is it to
speak in a session. It is useful in video conferencing.

Presentation Layer

This layer is concerned with the syntax and semantics of the information transmitted. In order to make it
possible for computers with different data representations to communicate data structures to be exchanged
can be defined in abstract way alongwith standard encoding. It also manages these abstract data structres and
allows higher level of data structres to be defined an exchange. It encodes the data in standard agreed
way(network format). Suppose there are two machines A and B one follows 'Big Endian' and other 'Little
Endian' for data representation. This layer ensures that the data transmitted by one gets converted in the form
compatibale to othe machine. This layer is concerned with the syntax and semantics of the information
[Link] order to make it possible for computers with different data representations to communicate
data structures to be exchanged canbe defined in abstract way alongwith standard encoding. It also manages
these abstract data structres and allows higher level of data structres to be defined an exchange. Other
functions include compression, encryption etc.

Application Layer
The seventh layer contains the application protocols with which the user gains access to the network. The
choice of which specific protocols and their associated functions are to be used at the application level is up
to the individual user. Thus the boundary between the presentation layer and the application layer represents
a separation of the protocols imposed by the network designers from those being selected and implemented
by the network [Link] example commonly used protocols are HTTP(for web browsing), FTP(for file
transfer) etc.

Network Layers as in Practice

In most of the networks today, we do not follow the OSI model of seven layers. What is actually
implemented is as follows. The functionality of Application layer and Presentation layer is merged into one
and is called as the Application Layer. Functionalities of Session Layer is not implemented in most networks
today. Also, the Data Link layer is split theoretically into MAC (Medium Access Control) Layer and LLC
(Link Layer Control). But again in practice, the LLC layer is not implemented by most networks. So as of
today, the network architecture is of 5 layers only.

[Link] 1/5
9/22/23, 9:49 AM CS425: Computer Networks: Lecture 02

Network Layers in Internet Today

Some Related Links on OSI Model and TCP Model

[Link]
[Link]
[Link]
[Link]
[Link]

Physical Layer
Physical layer is concerned with transmitting raw bits over a communication channel. The design issues have
to do with making sure that when one side sends a 1 bit, it is recieved by the other side as 1 bit and not as 0
bit. In physical layer we deal with the communication medium used for transmission.

Types of Medium

Medium can be classified into 2 categories.

1. Guided Media : Guided media means that signals is guided by the prescence of physical media i.e.
signals are under control and remains in the physical wire. For eg. copper wire.
2. Unguided Media : Unguided Media means that there is no physical path for the signal to propogate.
Unguided media are essentially electro-magnetic waves. There is no control on flow of signal. For eg.
radio waves.

Communication Links

In a nework nodes are connected through links. The communication through links can be classified as

1. Simplex : Communication can take place only in one direction. eg. T.V broadcasting.
2. Half-duplex : Communication can take place in one direction at a time. Suppose node A and B are
connected then half-duplex communication means that at a time data can flow from A to B or from B

[Link] 2/5
9/22/23, 9:49 AM CS425: Computer Networks: Lecture 02

to A but not simultaneously. eg. two persons talking to each other such that when speaks the other
listens and vice versa.
3. Full-duplex : Communication can take place simultaneously in both directions. eg. A discussion in a
group without discipline.

Links can be further classified as

1. Point to Point : In this communication only two nodes are connected to each other. When a node
sends a packet then it can be recieved only by the node on the other side and none else.
2. Multipoint : It is a kind of sharing communication, in which signal can be recieved by all nodes. This
is also called broadcast.

Generally two kind of problems are associated in transmission of signals.

1. Attenuation : When a signal transmitts in a network then the quality of signal degrades as the signal
travels longer distances in the wire. This is called attenuation. To improve quality of signal amplifiers
are used at regular distances.
2. Noise : In a communication channel many signals transmits simultaneously, certain random signals are
also present in the medium. Due to interference of these signals our signal gets disrupted a bit.

Bandwidth
Bandwidth simply means how many bits can be transmitted per second in the communication channel. In
technical terms it indicates the width of frequency spectrum.

Transmission Media

Guided Transmission Media

In Guided transmission media generally two kind of materials are used.

1. Copper
Coaxial Cable
Twisted Pair
2. Optical Fiber

1. Coaxial Cable: Coaxial cable consists of an inner conductor and an outer conductor which are
seperated by an insulator. The inner conductor is usually copper. The outer conductor is covered by a
plastic jacket. It is named coaxial because the two conductors are coaxial. Typical diameter of coaxial
cable lies between 0.4 inch to 1 inch. The most application of coaxial cable is cable T.V. The coaxial
cable has high bandwidth, attenuation is less.

2. Twisted Pair: A Twisted pair consists of two insulated copper wires, typically 1mm thick. The wires
are twisted togather in a helical form the purpose of twisting is to reduce cross talk interference
between several pairs. Twisted Pair is much cheaper then coaxial cable but it is susceptible to noise
and electromagnetic interference and attenuation is large.

[Link] 3/5
9/22/23, 9:49 AM CS425: Computer Networks: Lecture 02

Twisted Pair can be further classified in two categories:

Unshielded twisted pair: In this no insulation is provided, hence they are susceptible to interference.
Shielded twisted pair: In this a protective thick insulation is provided but shielded twisted pair is
expensive and not commonly used.

The most common application of twisted pair is the telephone system. Nearly all telephones are
connected to the telephone company office by a twisted pair. Twisted pair can run several kilometers
without amplification, but for longer distances repeaters are needed. Twisted pairs can be used for both
analog and digital transmission. The bandwidth depends on the thickness of wire and the distance
travelled. Twisted pairs are generally limited in distance, bandwidth and data rate.
3. Optical Fiber: In optical fiber light is used to send data. In general terms prescence of light is taken as
bit 1 and its absence as bit 0. Optical fiber consists of inner core of either glass or plastic. Core is
surrounded by cladding of the same material but of different refrective index. This cladding is
surrounded by a plastic jacket which prevents optical fiber from electromagnetic interferrence and
harshy environments. It uses the principle of total internal reflection to transfer data over optical fibers.
Optical fiber is much better in bandwidth as compared to copper wire, since there is hardly any
attenuation or electromagnetic interference in optical wires. Hence there is less requirement to improve
quality of signal, in long distance transmission. Disadvantage of optical fiber is that end points are
fairly expensive. (eg. switches)

Differences between different kinds of optical fibers:

1. Depending on material
Made of glass
Made of plastic.
2. Depending on radius
Thin optical fiber
Thick optical fiber
3. Depending on light source
LED (for low bandwidth)
Injection lased diode (for high bandwidth)

Wireless Transmission
1. Radio: Radio is a general term that is used for any kind of frequency. But higher frequencies are
usually termed as microwave and the lower frequency band comes under radio frequency. There are
many application of radio. For eg. cordless keyboard, wireless LAN, wireless ethernet. but it is limited
in range to only a few hundred meters. Depending on frequency radio offers different bandwidths.
2. Terrestrial microwave: In terrestrial microwave two antennas are used for communication. A focused
beam emerges from an antenna and is recieved by the other antenna, provided that antennas should be
facing each other with no obstacle in between. For this reason antennas are situated on high towers.
Due to curvature of earth terristial microwave can be used for long distance communication with high
bandwidth. Telecom department is also using this for long distance communication. An advantage of
wireless communication is that it is not required to lay down wires in the city hence no permissions are
required.
[Link] 4/5
9/22/23, 9:49 AM CS425: Computer Networks: Lecture 02

3. Satellite communication: Satellite acts as a switch in sky. On earth VSAT(Very Small Aperture
Terminal) are used to transmit and recieve data from satellite. Generally one station on earth transmitts
signal to satellite and it is recieved by many stations on earth. Satellite communication is generally
used in those places where it is very difficult to obtain line of sight i.e. in highly irregular terristial
regions. In terms of noise wireless media is not as good as the wired media. There are frequency band
in wireless communication and two stations should not be allowed to transmit simultaneously in a
frequency band. The most promising advantage of satellite is broadcasting. If satellites are used for
point to point communication then they are expensive as compared to wired media.

References of Images
[Link]
[Link]
[Link]
[Link]

back to top
Prev | Next | Index

[Link] 5/5
9/22/23, 9:50 AM CS425: Computer Networks: Lecture 03

Computer Networks (CS425)

Instructor: Dr. Dheeraj Sanghi

Prev| Next| Index

Data Encoding
Digital data to analog signals

A modem (modulator-demodulator) converts digital data to analog signal. There are 3 ways to modulate a
digital signal on an analog carrier signal.

1. Amplitude shift keying (ASK): is a form of modulation which represents digital data as variations in
the amplitude of a carrier wave. Two different amplitudes of carrier frequency represent '0' , '1'.

2. Frequency shift keying (FSK): In Frequency Shift Keying, the change in frequency define different
digits. Two different frequencies near carrier frequency represent '0' ,''1'.

3. Phase shift keying (PSK): The phase of the carrier is discretely varied in relation either to a reference
phase or to the phase of the immediately preceding signal element, in accordance with data being
transmitted. Phase of carrier signal is shifted to represent '0' , '1'.

[Link] 1/6
9/22/23, 9:50 AM CS425: Computer Networks: Lecture 03

Digital data to digital signals

A digital signal is sequence of discrete , discontinuous voltage pulses. Each pulses a signal element.
Encoding scheme is an important factor in how successfully the receiver interprets the incoming signal.

Encoding Techniques

Following are several ways to map data bits to signal elements.

Non return to zero(NRZ) NRZ codes share the property that voltage level is constant during a bit
interval. High level voltage = bit 1 and Low level voltage = bit 0. A problem arises when there is a
long sequence of 0s or 1s and the volatage level is maintained at the same value for a long time. This
creates a problem on the recieving end because now, the clock synchronization is lost due to lack of
any transitions and hence, it is difficult to determine the exact number of 0s or 1s in this sequence.

The two variations are as follows:

1. NRZ-Level: In NRZ-L encoding, the polarity of the signal changes only when the incoming
signal changes from a 1 to a 0 or from a 0 to a 1. NRZ-L method looks just like the NRZ
method, except for the first input one data bit. This is because NRZ does not consider the first
data bit to be a polarity change, where NRZ-L does.
2. NRZ-Inverted: Transition at the beginning of bit interval = bit 1 and No Transition at beginning
of bit interval = bit 0 or vicecersa. This technique is known as differential encoding.

NRZ-I has an advantage over NRZ-L. Consider the situation when two data wires are wrongly
connected in each other's [Link] NRZ-L all bit sequences will get reversed (B'coz voltage levels get
swapped).Whereas in NAZ-I since bits are recognized by transition the bits will be correctly
interpreted. A disadvantage in NRZ codes is that a string of 0's or 1's will prevent synchronization of
transmitter clock with receiver clock and a separate clock line need to be provided.

Biphase encoding: It has following characteristics:

1. Modulation rate twice that of NRZ and bandwidth correspondingly greater. (Modulation is the
rate at which signal level is changed).

[Link] 2/6
9/22/23, 9:50 AM CS425: Computer Networks: Lecture 03

2. Because there is predictable transition during each bit time,the receiver can synchronize on that
transition i.e. clock is extracted from the signal itself.
3. Since there can be transition at the beginning as well as in the middle of the bit interval the clock
operates at twice the data transfer rate.
Types of Encoding -->
Biphase-manchester: Transition from high to low in middle of interval = 1 and Transition from
low to high in middle of interval = 0
Differential-manchester: Always a transition in middle of interval. No transition at beginning
of interval=1 and Transition at beginning of interval = 0

4B/5B Encoding: In Manchester encoding scheme , there is a transition after every bit. It means
that we must have clocks with double the speed to send same amount of data as in NRZ
encodings. In other words, we may say that only 50% of the data is sent. This performance
factor can be significantly improved if we use a better encoding scheme. This scheme may have
a transition after fixed number of bits instead of every other bit. Like if we have a transition after
every four bits, then we will be sending 80% data of actual capacity. This is a significant
improvement in the performance.

This scheme is known as 4B/5B. So here we convert 4-bits to 5-bits, ensuring at least one
transition in them. The basic idea here is that 5-bit code selected must have :

one leading 0
no more than two trailing 0s
Thus it is ensured that we can never have more than three consecutive 0s. Now these 5-bit codes
are transmitted using NRZI coding thus problem of consecutive 1s is solved.

The exact transformation is as follows :

4-bit Data 5-bit code 4-bit Data 5-bit code

0000 11110 1000 10010
0001 01001 1001 10011
0010 10100 1010 10110
0011 10101 1011 10111
0100 01010 1100 11010
0101 01011 1101 11011
0110 01110 1110 11100
[Link] 3/6
9/22/23, 9:50 AM CS425: Computer Networks: Lecture 03

0111 01111 1111 11101

Of the remaining 16 codes, 7 are invalid and others are used to send some control information
like line idle(11111), line dead(00000), Halt(00100) etc.

There are other variants for this scheme viz. 5B/6B, 8B/10B etc. These have self suggesting
names.

8B/6T Encoding: In the above schemes, we have used two/three voltage levels for a signal. But
we may altogether use more than three voltage levels so that more than one-bit could be send
over a single signal. Like if we use six voltage levels and we use 8-bits then the scheme is called
8B/6T. Clearly here we have 729(3^6) combinations for signal and 256(2^8) combinations for
bits.
Bipolar AIM: Here we have 3 voltage levels: middle,upper,lower
Representation 1: Middle level =0 Upper,Lower level =1 such that successive 1's will be
represented alternately on upper and lower levels.
Representation 2 (pseudoternary): Middle level =1 Upper,Lower level=0

Analog data to digital signal:

The process is called digitization. Sampling frequency must be at least twice that of highest frequency
present in the the signal so that it may be fairly regenerated. Quantization - Max. and Min values of
amplitude in the sample are noted. Depending on number of bits (say n) we use we divide the interval
(min,max) into 2(^n) number of levels. The amplitude is then approximated to the nearest level by a 'n' bit
integer. The digital signal thus consists of blocks of n [Link] reception the process is reversed to produce
analog signal. But a lot of data can be lost if fewer bits are used or sampling frequency not so high.

Pulse code modulation(PCM): Here intervals are equally spaced. 8 bit PCB uses 256 different levels
of amplitude. In non-linear encoding levels may be unequally spaced.
Delta Modulation(DM): Since successive samples do not differ very much we send the differences
between previous and present sample. It requires fewer bits than in PCM.

Digital Data Communication Techniques:

For two devices linked by a transmission medium to exchange data ,a high degree of co-operation is
required. Typically data is transmitted one bit at a time. The timing (rate, duration,spacing) of these bits must
be same for transmitter and receiver. There are two options for transmission of bits.

1. Parallel All bits of a byte are transferred simultaneously on separate parallel wires. Synchronization
between multiple bits is required which becomes difficult over large distance. Gives large band width
but expensive. Practical only for devices close to each other.
2. Serial Bits transferred serially one after [Link] less bandwidth but cheaper. Suitable for
transmission over long distances.

Transmission Techniques:

1. Asynchronous: Small blocks of bits(generally bytes) are sent at a time without any time relation
between consecutive bytes .when no transmission occurs a default state is maintained corresponding to
bit 1. Due to arbitrary delay between consecutive bytes,the time occurrences of the clock pulses at the
receiving end need to be synchronized for each byte. This is achieved by providing 2 extra bits start
and stop.

Start bit: It is prefixed to each byte and equals 0. Thus it ensures a transition from 1 to 0 at onset of
transmission of [Link] leading edge of start bit is used as a reference for generating clock pulses at
required sampling instants. Thus each onset of a byte results in resynchronization of receiver clock.

[Link] 4/6
9/22/23, 9:50 AM CS425: Computer Networks: Lecture 03

Stop bit: To ensure that transition from 1 to 0 is always present at beginning of a byte it is necessary
that default state be 1. But there may be two bytes one immediately following the other and if last bit
of first byte is 0, transition from 1 to 0 will not occur . Therefore a stop bit is suffixed to each byte
equaling 1. It's duration is usually 1,1.5,2 bits.

Asynchronous transmission is simple and cheap but requires an overhead of 3 bits i.e. for 7 bit code 2
(start ,stop bits)+1 parity bit implying 30% [Link] % can be reduced by sending larger
blocks of data but then timing errors between receiver and sender can not be tolerated beyond [50/no.
of bits in block] % (assuming sampling is done at middle of bit interval). It will not only result in
incorrect sampling but also misaligned bit count i.e. a data bit can be mistaken for stop bit if receiver's
clock is faster.

2. Synchronous - Larger blocks of bits are successfully [Link] of data are either treated as
sequence of bits or bytes. To prevent timing drift clocks at two ends need to be [Link] can
done in two ways:
1. Provide a separate clock line between receiver and transmitter. OR
2. Clocking information is embedded in data signal i.e. biphase coding for digital signals.
Still another level of synchronization is required so that receiver determines beginning or end of block
of data. Hence each block begins with a start code and ends with a stop [Link] are in general same
known as flag that is unique sequence of fixed no. of [Link] addition some control characters
encompass data within these flags. Data+control information is called a frame. Since any arbitrary
bit pattern can be transmitted there is no assurance that bit pattern for flag will not appear inside the
frame thus destroying frame level synchronization. So to avoid this we use bit stuffing

Bit Stuffing: Suppose our flag bits are 01111110 (six 1's). So the transmitter will always insert an
extra 0 bit after each occurrence of five 1's (except for flags). After detecting a starting flag the
receiver monitors the bit stream . If pattern of five 1's appear, the sixth is examined and if it is 0 it
isdeleted else if it is 1 and next is 0 the combination is accepted as a flag. Similarly byte stuffing is
used for byte oriented [Link] we use an escape sequence to prefix a byte similar to flag and
2 escape sequences if byte is itself a escape sequence.

Image References:

[Link] 5/6
9/22/23, 9:50 AM CS425: Computer Networks: Lecture 03

[Link]
[Link]
[Link]
[Link]

back to top
Prev| Next | Index

[Link] 6/6
9/22/23, 9:50 AM CS425: Computer Networks: Lecture 04

Computer Networks (CS425)

Instructor: Dr. Dheeraj Sanghi

Prev| Next| Index

Multiplexing

When two communicating nodes are connected through a media, it generally happens that bandwidth of media is several
times greater than that of the communicating nodes. Transfer of a single signal at a time is both slow and expensive. The
whole capacity of the link is not being utilized in this case. This link can be further exploited by sending several signals
combined into one. This combining of signals into one is called multiplexing.

1. Frequency Division Multiplexing (FDM): This is possible in the case where transmission media has a bandwidth
than the required bandwidth of signals to be transmitted. A number of signals can be transmitted at the same time.
Each source is allotted a frequency range in which it can transfer it's signals, and a suitable frequency gap is given
between two adjescent signals to avoid overlapping. This is type of multiplexing is commonly seen in the cable TV
networks.

2. Time Division Multiplexing (TDM): This is possible when data transmission rate of the media is much higher than
that of the data rate of the source. Multiple signals can be transmitted if each signal is allowed to be transmitted for a
definite amount of time. These time slots are so small that all transmissions appear to be in parallel.
1. Synchronous TDM: Time slots are preassigned and are fixed. Each source is given it's time slot at every turn
due to it. This turn may be once per cycle, or several turns per cycle ,if it has a high data transfer rate, or may
be once in a no. of cycles if it is slow. This slot is given even if the source is not ready with data. So this slot is
transmitted empty.

[Link] 1/7
9/22/23, 9:50 AM CS425: Computer Networks: Lecture 04

2. Asynchronous TDM: In this method, slots are not fixed. They are allotted dynamically depending on speed of
sources, and whether they are ready for transmission.

Network Topologies
A network topology is the basic design of a computer network. It is very much like a map of a road. It details how key
network components such as nodes and links are interconnected. A network's topology is comparable to the blueprints of a
new home in which components such as the electrical system, heating and air conditioning system, and plumbing are
integrated into the overall design. Taken from the Greek work "Topos" meaning "Place," Topology, in relation to
networking, describes the configuration of the network; including the location of the workstations and wiring connections.
Basically it provides a definition of the components of a Local Area Network (LAN). A topology, which is a pattern of
interconnections among nodes, influences a network's cost and performance. There are three primary types of network
topologies which refer to the physical and logical layout of the Network cabling. They are:

1. Star Topology: All devices connected with a Star setup communicate through a central Hub by cable segments.
Signals are transmitted and received through the Hub. It is the simplest and the oldest and all the telephone switches
are based on this. In a star topology, each network device has a home run of cabling back to a network hub, giving
each device a separate connection to the network. So, there can be multiple connections in parallel.

[Link] 2/7
9/22/23, 9:50 AM CS425: Computer Networks: Lecture 04

Advantages

Network administration and error detection is easier because problem is isolated to central node
Networks runs even if one host fails
Expansion becomes easier and scalability of the network increases
More suited for larger networks

Disadvantages

Broadcasting and multicasting is not easy because some extra functionality needs to be provided to the central
hub
If the central node fails, the whole network goes down; thus making the switch some kind of a bottleneck
Installation costs are high because each node needs to be connected to the central switch
2. Bus Topology: The simplest and one of the most common of all topologies, Bus consists of a single cable, called a
Backbone, that connects all workstations on the network using a single line. All transmissions must pass through
each of the connected devices to complete the desired request. Each workstation has its own individual signal that
identifies it and allows for the requested data to be returned to the correct originator. In the Bus Network, messages
are sent in both directions from a single point and are read by the node (computer or peripheral on the network)
identified by the code with the message. Most Local Area Networks (LANs) are Bus Networks because the network
will continue to function even if one computer is down. This topology works equally well for either peer to peer or
client server.

The purpose of the terminators at either end of the network is to stop the signal being reflected back.

Advantages

Broadcasting and multicasting is much simpler

Network is redundant in the sense that failure of one node doesn't effect the network. The other part may still
function properly
Least expensive since less amount of cabling is required and no network switches are required
Good for smaller networks not requiring higher speeds

Disadvantages

Trouble shooting and error detection becomes a problem because, logically, all nodes are equal
Less secure because sniffing is easier
Limited in size and speed

[Link] 3/7
9/22/23, 9:50 AM CS425: Computer Networks: Lecture 04

3. Ring Topology: All the nodes in a Ring Network are connected in a closed circle of cable. Messages that are
transmitted travel around the ring until they reach the computer that they are addressed to, the signal being refreshed
by each node. In a ring topology, the network signal is passed through each network card of each device and passed
on to the next device. Each device processes and retransmits the signal, so it is capable of supporting many devices
in a somewhat slow but very orderly fashion. There is a very nice feature that everybody gets a chance to send a
packet and it is guaranteed that every node gets to send a packet in a finite amount of time.

Advantages

Broadcasting and multicasting is simple since you just need to send out one message
Less expensive since less cable footage is required
It is guaranteed that each host will be able to transmit within a finite time interval
Very orderly network where every device has access to the token and the opportunity to transmit
Performs better than a star network under heavy network load

Disadvantages

Failure of one node brings the whole network down

Error detection and network administration becomes difficult
Moves, adds and changes of devices can effect the network
It is slower than star topology under normal load

Generally, a BUS architecture is preferred over the other topologies - ofcourse, this is a very subjective opinion and the
final design depends on the requirements of the network more than anything else. Lately, most networks are shifting
towards the STAR topology. Ideally we would like to design networks, which physically resemble the STAR topology, but
behave like BUS or RING topology.

Data Link Layer

Data link layer can be characterized by two types of layers:

1. Medium Access Layer (MAL)

2. Logical Link Layer

Aloha Protocols

History

The Aloha protocol was designed as part of a project at the University of Hawaii. It provided data transmission between
computers on several of the Hawaiian Islands using radio transmissions.

Communications was typically between remote stations and a central sited named Menehune or vice versa.
All message to the Menehune were sent using the same frequency.
When it received a message intact, the Menehune would broadcast an ack on a distinct outgoing frequency.
The outgoing frequency was also used for messages from the central site to remote computers.
All stations listened for message on this second frequency.

Pure Aloha

[Link] 4/7
9/22/23, 9:50 AM CS425: Computer Networks: Lecture 04

Pure Aloha is an unslotted, fully-decentralized protocol. It is extremely simple and trivial to implement. The ground rule is
- "when you want to talk, just talk!". So, a node which wants to transmits, will go ahead and send the packet on its
broadcast channel, with no consideration whatsoever as to anybody else is transmitting or not.

One serious drawback here is that, you dont know whether what you are sending has been received properly or not (so as to
say, "whether you've been heard and understood?"). To resolve this, in Pure Aloha, when one node finishes speaking, it
expects an acknowledgement in a finite amount of time - otherwise it simply retransmits the data. This scheme works well
in small networks where the load is not high. But in large, load intensive networks where many nodes may want to transmit
at the same time, this scheme fails miserably. This led to the development of Slotted Aloha.

Slotted Aloha

This is quite similar to Pure Aloha, differing only in the way transmissions take place. Instead of transmitting right at
demand time, the sender waits for some time. This delay is specified as follows - the timeline is divided into equal slots and
then it is required that transmission should take place only at slot boundaries. To be more precise, the slotted-Aloha makes
the following assumptions:

All frames consist of exactly L bits.

Time is divided into slots of size L/R seconds (i.e., a slot equals the time to transmit one frame).
Nodes start to transmit frames only at the beginnings of slots.
The nodes are synchronized so that each node knows when the slots begin.
If two or more frames collide in a slot, then all the nodes detect the collision event before the slot ends.

In this way, the number of collisions that can possibly take place is reduced by a huge margin. And hence, the performance
become much better compared to Pure Aloha. collisions may only take place with nodes that are ready to speak at the same
time. But nevertheless, this is a substantial reduction.

Carrier Sense Mutiple Access Protocols

In both slotted and pure ALOHA, a node's decision to transmit is made independently of the activity of the other nodes
attached to the broadcast channel. In particular, a node neither pays attention to whether another node happens to be
transmitting when it begins to transmit, nor stops transmitting if another node begins to interfere with its transmission. As
humans, we have human protocols that allow allows us to not only behave with more civility, but also to decrease the
[Link] 5/7
9/22/23, 9:50 AM CS425: Computer Networks: Lecture 04

amount of time spent "colliding" with each other in conversation and consequently increasing the amount of data we
exchange in our conversations. Specifically, there are two important rules for polite human conversation:

1. Listen before speaking: If someone else is speaking, wait until they are done. In the networking world, this is
termed carrier sensing - a node listens to the channel before transmitting. If a frame from another node is currently
being transmitted into the channel, a node then waits ("backs off") a random amount of time and then again senses
the channel. If the channel is sensed to be idle, the node then begins frame transmission. Otherwise, the node waits
another random amount of time and repeats this process.
2. If someone else begins talking at the same time, stop talking. In the networking world, this is termed collision
detection - a transmitting node listens to the channel while it is transmitting. If it detects that another node is
transmitting an interfering frame, it stops transmitting and uses some protocol to determine when it should next
attempt to transmit.

It is evident that the end-to-end channel propagation delay of a broadcast channel - the time it takes for a signal to
propagate from one of the the channel to another - will play a crucial role in determining its performance. The longer this
propagation delay, the larger the chance that a carrier-sensing node is not yet able to sense a transmission that has already
begun at another node in the network.

CSMA- Carrier Sense Multiple Access

This is the simplest version CSMA protocol as described above. It does not specify any collision detection or handling. So
collisions might and WILL occur and clearly then, this is not a very good protocol for large, load intensive networks.

So, we need an improvement over CSMA - this led to the development of CSMA/CD.

CSMA/CD- CSMA with Collision Detection

In this protocol, while transmitting the data, the sender simultaneously tries to receive it. So, as soon as it detects a
collission (it doesn't receive its own data) it stops transmitting. Thereafter, the node waits for some time interval before
attempting to transmit again. Simply put, "listen while you talk". But, how long should one wait for the carrier to be
freed? There are three schemes to handle this:

1. 1-Persistent: In this scheme, transmission proceeds immediately if the carrier is idle. However, if the carrier is busy,
then sender continues to sense the carrier until it becomes idle. The main problem here is that, if more than one
transmitters are ready to send, a collision is GUARANTEED!!
2. Non-Persistent: In this scheme, the broadcast channel is not monitored continuously. The sender polls it at random
time intervals and transmits whenever the carrier is idle. This decreases the probability of collisions. But, it is not
efficient in a low load situation, where number of collisions are anyway small. The problems it entails are:
If back-off time is too long, the idle time of carrier is wasted in some sense
It may result in long access delays
3. p-Persistent: Even if a sender finds the carrier to be idle, it uses a probabilistic distribution to determine whether to
transmit or not. Put simply, "toss a coin to decide". If the carrier is idle, then transmission takes place with a
probability p and the sender waits with a probability 1-p. This scheme is a good trade off between the Non-persistent
and 1-persistent schemes. So, for low load situations, p is high (example: 1-persistent); and for high load situations, p
may be lower. Clearly, the value of p plays an important role in determining the performance of this protocol. Also
the same p is likely to provide different performance at different loads.

CSMA/CD doesn't work in some wireless scenarios called "hidden node" problems. Consider a situation, where there are
3 nodes - A, B and C communicating with each other using a wireless protocol. Morover, B can communicate with both A
and C, but A and C lie outside each other's range and hence can't communicate directly with each other. Now, suppose both
A and C want to communicate with B simultaneously. They both will sense the carrier to be idle and hence will begin
transmission, and even if there is a collision, neither A nor C will ever detect it. B on the other hand will receive 2 packets
at the same time and might not be able to understand either of them. To get around this problem, a better version called
CSMA/CA was developed, specially for wireless applications.

Image References:

[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link]
[Link] 6/7
9/22/23, 9:50 AM CS425: Computer Networks: Lecture 04

[Link]

back to top
Prev| Next | Index

[Link] 7/7
9/22/23, 9:50 AM CS425: Computer Networks: Lecture 05

Computer Networks (CS425)

Instructor: Dr. Dheeraj Sanghi

Prev| Next| Index

CSMA with Collision Avoidance

We have observed that CSMA/CD would break down in wireless networks because of hidden node and
exposed nodes problems. We will have a quick recap of these two problems through examples.

Hidden Node Problem

In the case of wireless network it is possible that A is sending a message to B, but C is out of its range and
hence while "listening" on the network it will find the network to be free and might try to send packets to B
at the same time as A. So, there will be a collision at B. The problem can be looked upon as if A and C are
hidden from each other. Hence it is called the "hidden node problem".

Exposed Node Problem

If C is transmitting a message to D and B wants to transmit a message to A, B will find the network to be
busy as B hears C trnasmitting. Even if B would have transmitted to A, it would not have been a problem at
A or D. CSMA/CD would not allow it to transmit message to A, while the two transmissions could have
gone in parallel.

Addressing hidden node problem (CSMA/CA)

Consider the figure [Link] A wants to send a packet to B. Then it will first send a small packet to B
called "Request to Send" (RTS). In response, B sends a small packet to A called "Clear to Send" (CTS).
Only after A receives a CTS, it transmits the actual data. Now, any of the nodes which can hear either CTS or
RTS assume the network to be busy. Hence even if some other node which is out of range of both A and B
sends an RTS to C (which can hear at least one of the RTS or CTS between A and B), C would not send a
CTS to it and hence the communication would not be established between C and D.

One issue that needs to be addressed is how long the rest of the nodes should wait before they can transmit
data over the network. The answer is that the RTS and CTS would carry some information about the size of
the data that B intends to transfer. So, they can calculate time that would be required for the transmission to
be over and assume the network to be free after [Link] interesting issue is what a node should do if it
hears RTS but not a corresponding CTS. One possibility is that it assumes the recipient node has not
responded and hence no transmission is going on, but there is a catch in this. It is possible that the node
hearing RTS is just on the boundary of the node sending CTS. Hence, it does hear CTS but the signal is so

[Link] 1/4
9/22/23, 9:50 AM CS425: Computer Networks: Lecture 05

deteriorated that it fails to recognize it as a CTS. Hence to be on the safer side, a node will not start
transmission if it hears either of an RTS or a CTS.

The assumption made in this whole discussion is that if a node X can send packets to a node Y, it can also
receive a packet from Y, which is a fair enough assumption given the fact that we are talking of a local
network where standard instruments would be used. If that is not the case additional complexities would get
introduced in the system.

Does CSMA/CD work universally in the wired networks ?

The problem of range is there in wired networks as well in the form of deterioration of signals. Normally to
counter this, we use repeaters, which can regenerate the original signal from a deteriorated one. But does that
mean that we can build as long networks as we want with repeaters. The answer, unfortunately, is NO! The
reason is the beyond a certain length CSMA/CD will break down.

The mechanism of collision detection which CSMA/CD follows is through listening while talking. What this
means is so long as a node is transmitting the packet, it is listening on the cable. If the data it listens to is
different from the data it is transmitting it assumes a collision. Once it has stopped transmitting the packet,
and has not detected collision while transmission was going on, it assumes that the transmission was
successful. The problem arises when the distance between the two nodes is too large. Suppose A wants to
transmit some packet to B which is at a very large distance from B. Data can travel on cable only at a finite
speed (usually 2/3c, c being the speed of light). So, it is possible that the packet has been transmitted by A
onto the cable but the first bit of the packet has not yet reached B. In that case, if a collision occurs, A would
be unaware of it occurring. Therefore there is problem in too long a network.

Let us try to parametrize the above problem. Suppose "t" is the time taken for the node A to transmit the
packet on the cable and "T" is the time , the packet takes to reach from A to B. Suppose transmission at A
starts at time t0. In the worst case the collision takes place just when the first packet is to reach B. Say it is at
t0+T-e (e being very small). Then the collision information will take T-e time to propagate back to A. So, at
t0+2(T-e) A should still be transmitting. Hence, for the correct detection of collision (ignoring e)

t > 2T

t increases with the number of bits to be transferred and decreases with the rate of transfer (bits per second).
T increases with the distance between the nodes and decreases with the speed of the signal (usually 2/3c). We
need to either keep t large enough or T as small. We do not want to live with lower rate of bit transfer and
hence slow networks. We can not do anything about the speed of the signal. So what we can rely on is the
minimum size of the packet and the distance between the two nodes. Therefore, we fix some minimum size
of the packet and if the size is smaller than that, we put in some extra bits to make it reach the minimum size.
Accordingly we fix the maximum distance between the nodes. Here too, there is a tradeoff to be made. We
do not want the minimum size of the packets to be too large since that wastes lots of resources on cable. At
the same time we do not want the distance between the nodes to be too small. Typical minimum packet size
is 64 bytes and the corresponding distance is 2-5 kilometers.

Collision Free Protocols

Although collisions do not occur with CSMA/CD once a station has unambigously seized the channel, they
can still occur during the contention period. These collisions adversely affect the efficiency of transmission.
Hence some protocols have been developed which are contention free.

Bit-Map Method

In this method, there N slots. If node 0 has a frame to send, it transmit a 1 bit during the first slot. No other
node is allowed to transmit during this period. Next node 1 gets a chance to transmit 1 bit if it has something
to send, regardless of what node 0 had transmitted. This is done for all the nodes. In general node j may
declare the fact that it has a frsme to send by inserting a 1 into slot j. Hence after all nodes have passed, each

[Link] 2/4
9/22/23, 9:50 AM CS425: Computer Networks: Lecture 05

node has complete knowledge of who wants to send a frame. Now they begin transmitting in numerical
order. Since everyone knows who is transmitting and when, there could never be any collision.

The basic problem with this protocol is its inefficiency during low load. If a node has to transmit and no
other node needs to do so, even then it has to wait for the bitmap to finish. Hence the bitmap will be repeated
over and over again if very few nodes want to send wasting valuable bandwidth.

Binary Countdown
In this protocol, a node which wants to signal that it has a frame to send does so by writing its address into
the header as a binary number. The arbitration is such that as soon as a node sees that a higher bit position
that is 0 in its address has been overwritten with a 1, it gives up. The final result is the address of the node
which is allowed to send. After the node has transmitted the whole process is repeated all over again. Given
below is an example situation.
Nodes Addresses
A 0010
B 0101
C 1010
D 1001
----
1010
Node C having higher priority gets to transmit. The problem with this protocol is that the nodes with higher
address always wins. Hence this creates a priority which is highly unfair and hence undesirable.

Limited Contention Protocols

Both the type of protocols described above - Contention based and Contention - free has their own problems.
Under conditions of light load, contention is preferable due to its low delay. As the load increases, contention
becomes increasingly less attractive, because the overload associated with channel arbitration becomes
greater. Just the reverse is true for contention - free protocols. At low load, they have high delay, but as the
load increases , the channel efficiency improves rather than getting worse as it does for contention protocols.

Obviously it would be better if one could combine the best properties of the contention and contention - free
protocols, that is, protocol which used contention at low loads to provide low delay, but used a cotention-free
technique at high load to provide good channel efficiency. Such protocols do exist and are called Limited
contention protocols.

It is obvious that the probablity of some station aquiring the channel could only be increased by decreasing
the amount of competition. The limited contention protocols do exactly that. They first divide the stations up
into ( not necessarily disjoint ) groups. Only the members of group 0 are permitted to compete for slot 0. The
competition for aquiring the slot within a group is contention based. If one of the members of that group
succeeds, it aquires the channel and transmits a frame. If there is collision or no node of a particular group
wants to send then the members of the next group compete for the next slot. The probablity of a particular
node is set to a particular value ( optimum ).

Adaptive Tree Walk Protocol

The following is the method of adaptive tree protocol. Initially all the nodes are allowed to try to aquire the
channel. If it is able to aquire the channel, it sends its frame. If there is collision then the nodes are divided
into two equal groups and only one of these groups compete for slot 1. If one of its member aquires the
channel then the next slot is reserved for the other group. On the other hand, if there is a collision then that
group is again subdivided and the same process is followed. This can be better understood if the nodes are
thought of as being organised in a binary tree as shown in the following figure.

[Link] 3/4
9/22/23, 9:50 AM CS425: Computer Networks: Lecture 05

Many improvements could be made to the algorithm. For example, consider the case of nodes G and H being
the only ones wanting to transmit. At slot 1 a collision will be detected and so 2 will be tried and it will be
found to be idle. Hence it is pointless to probe 3 and one should directly go to 6,7.

Image References:
[Link]

back to top
Prev| Next | Index

[Link] 4/4
9/22/23, 9:51 AM CS425: Computer Networks: Lecture 06

Computer Networks (CS425)

Instructor: Dr. Dheeraj Sanghi

Prev| Next| Index

IEEE 802.3 and Ethernet

Very popular LAN standard.
Ethernet and IEEE 802.3 are distinct standards but as they are very similar to one another these words are used interchangeably.
A standard for a 1-persistent CSMA/CD LAN.
It covers the physical layer and MAC sublayer protocol.

Ethernet Physical Layer

A Comparison of Various Ethernet and IEEE 802.3 Physical-Layer Specifications

Characteristic Ethernet Value IEEE 802.3 Values

10Base5 10Base2 10BaseT 10BaseF 10 Base -TX 100Base
Data rate (Mbps) 10 10 10 10 10 100 100
Signaling method Baseband Baseband Baseband Baseband Baseband Baseband Baseban
Maximum segment length (m) 500 500 185 100 2,000 100 100
Media 50-ohm coax (thick) 50-ohm coax (thick) 50-ohm coax (thin) Unshielded twisted-pair cable Fiber-optic Cat 5 UTP Unshield
Nodes/segment 100 100 30 1024 1024
Topology Bus Bus Bus Star Point-to-point Bus Bus

10Base5 means it operates at 10 Mbps, uses baseband signaling and can support segments of up to 500 meters. The 10Base5 cabling is popularly called the Thick
Ethernet. Vampire taps are used for their connections where a pin is carefully forced halfway into the co-axial cable's core as shown in the figure below. The
10Base2 or Thin Ethernet bends easily and is connected using standard BNC connectors to form T junctions (shown in the figure below). In the 10Base-T scheme a
different kind of wiring pattern is followed in which all stations have a twisted-pair cable running to a central hub (see below). The difference between the different
physical connections is shown below:

(a) 10Base5 (b)10Base2 (c)10Base-T

All 802.3 baseband systems use Manchester encoding , which is a way for receivers to unambiguously determine the start, end or middle of each bit without
reference to an external clock. There is a restriction on the minimum node spacing (segment length between two nodes) in 10Base5 and 10Base2 and that is 2.5
meter and 0.5 meter respectively. The reason is that if two nodes are closer than the specified limit then there will be very high current which may cause trouble in
detection of signal at the receiver end. Connections from station to cable of 10Base5 (i.e. Thick Ethernet) are generally made using vampire taps and to 10Base2 (i.e.
Thin Ethernet) are made using industry standard BNC connectors to form T junctions. To allow larger networks, multiple segments can be connected by repeaters as
shown. A repeater is a physical layer device. It receives, amplifies and retransmits signals in either direction.

Note: To connect multiple segments, amplifier is not used because amplifier also amplifies the noise in the signal, whereas repeater regenerates signal after
removing the noise.

IEEE 802.3 Frame Structure

Preamble Start of Frame Delimiter Dest. Address Source Address Length 802.2 Header+Data Frame Checksum
(7 bytes) (1 byte) (2/6 bytes) (2/6 bytes) (2 bytes) (46-1500 bytes) (4 bytes)

A brief description of each of the fields

Preamble :Each frame starts with a preamble of 7 bytes, each byte containing the bit pattern 10101010. Manchester encoding is employed here and this
enables the receiver's clock to synchronize with the sender's and initialise itself.
Start of Frame Delimiter :This field containing a byte sequence 10101011 denotes the start of the frame itself.
Dest. Address :The standard allows 2-byte and 6-byte addresses. Note that the 2-byte addresses are always local addresses while the 6-byte ones can be local
or global.

[Link] 1/3
9/22/23, 9:51 AM CS425: Computer Networks: Lecture 06

2-Byte Address - Manually assigned address

Individual(0)/Group(1) Address of the machine
(1 bit) (15 bits)

6-Byte Address - Every Ethernet card with globally unique address

Individual(0)/Group(1) Universal(0)/Local(1) Address of the machine
(1 bit) (1 bit) (46 bits)

Multicast : Sending to group of stations. This is ensured by setting the first bit in either 2-byte/6-byte addresses to 1.
Broadcast : Sending to all stations. This can be done by setting all bits in the address field to [Link] Ethernet cards(Nodes) are a member of this group.
Source Address :Refer to Dest. Address. Same holds true over here.
Length : The Length field tells how many bytes are present in the data field, from a minimum of 0 to a maximum of 1500. The Data and padding together can
be from 46bytes to 1500 bytes as the valid frames must be at least 64 bytes long, thus if data is less than 46 bytes the amount of padding can be found out by
length field.
Data :Actually this field can be split up into two parts - Data(0-1500 bytes) and Padding(0-46 bytes).
Reasons for having a minimum length frame :
1. To prevent a station from completing the transmission of a short frame before the first bit has even reached the far end of the cable, where it may collide
with another frame. Note that the transmission time ought to be greater than twice the propagation time between two farthest nodes.
transmission time for frame > 2*propagation time between two farthest nodes
2. When a transceiver detects a collision, it truncates the current frame, which implies that stray bits and pieces of frames appear on the cable all the time.
Hence to distinguish between valid frames from garbage, 802.3 states that the minimum length of valid frames ought to be 64 bytes (from Dest. Address
to Frame Checksum).
Frame Checksum : It is a 32-bit hash code of the data. If some bits are erroneously received by the destination (due to noise on the cable), the checksum
computed by the destination wouldn't match with the checksum sent and therefore the error will be detected. The checksum algorithm is a cyclic redundancy
checksum (CRC) kind. The checksum includes the packet from Dest. Address to Data field.

Ethernet Frame Structure

Preamble Dest. Address Source Address Type Data Frame Checksum

(8 bytes) (2/6 bytes) (2/6 bytes) (2 bytes) (46-1500 bytes) (4 bytes)

A brief description of the fields which differ from IEEE 802.3

Preamble :The Preamble and Start of Frame Delimiter are merged into one in Ethernet standard. However, the contents of the first 8 bytes remains the same
in both.
Type :The length field of IEEE 802.3 is replaced by Type field, which denotes the type of packet being sent viz. IP, ARP, RARP, etc. If the field indicates a
value less than 1500 bytes then it is length field of 802.3 else it is the type field of Ethernet packet.

Truncated Binary Exponential Back off

In case of collision the node transmitting backs off by a random number of slots , each slot time being equal to transmission time of 512 bits (64 Byte- minimum size
of a packet) in the following fashion:

No of Collision Random No of slots

1st 0-1

2nd 0-3

3rd 0-7

| |

| |

10th 0-1023

---------------------------------------------

11th 0-1023

12th 0-1023

| |

16th 0-1023

In general after i collisions a random number between 0-2^i-1 is chosen , and that number of slots is skipped. However, after 10 collisions have been reached the
randomization interval is frozen at maximum of 1023 slots. After 16 collisions the controller reports failure back to the computer.

5-4-3 Rule

Each version of 802.3 has a maximum cable length per segment because long propagation time leads to difficulty in collision detection. To compensate for this the
transmission time has to be increased which can be achieved by slowing down the transmission rate or increasing the packet size, neither of which is desirable.
Hence to allow for large networks, multiple cables are connected via repeaters. Between any two nodes on an Ethernet network, there can be at most five segments,
four repeaters and three populated segments (non-populated segments are those which do not have any machine connected between the two repeaters). This is known
as the 5-4-3 Rule.

Image References:
[Link]

[Link] 2/3
9/22/23, 9:51 AM CS425: Computer Networks: Lecture 06
back to top
Prev| Next | Index

[Link] 3/3
9/22/23, 9:51 AM CS425: Computer Networks: Lecture 07

Computer Networks (CS425)

Instructor: Dr. Dheeraj Sanghi

Prev| Next| Index

IEEE 802.5: Token Ring Network

Token Ring is formed by the nodes connected in ring format as shown in the diagram below. The
principle used in the token ring network is that a token is circulating in the ring and whichever node
grabs that token will have right to transmit the data.
Whenever a station wants to transmit a frame it inverts a single bit of the 3-byte token which
instantaneously changes it into a normal data packet. Because there is only one token, there can atmost
be one transmission at a time.
Since the token rotates in the ring it is guarenteed that every node gets the token with in some specified
time. So there is an upper bound on the time of waiting to grab the token so that starvation is avoided.
There is also an upper limit of 250 on the number of nodes in the network.
To distinguish the normal data packets from token (control packet) a special sequence is assigned to
the token packet. When any node gets the token it first sends the data it wants to send, then recirculates
the token.

If a node transmits the token and nobody wants to send the data the token comes back to the sender. If the
first bit of the token reaches the sender before the transmission of the last bit, then error situation araises. So
to avoid this we should have:

propogation delay + transmission of n-bits (1-bit delay in each node ) > transmission of the token time

A station may hold the token for the token-holding time. which is 10 ms unless the installation sets a
different value. If there is enough time left after the first frame has been transmitted to send more frames,
then these frames may be sent as well. After all pending frames have been transmitted or the transmission
frame would exceed the token-holding time, the station regenerates the 3-byte token frame and puts it back
on the ring.

Modes of Operation
1. Listen Mode: In this mode the node listens to the data and transmits the data to the next node. In this
mode there is a one-bit delay associated with the transmission.

[Link] 1/7
9/22/23, 9:51 AM CS425: Computer Networks: Lecture 07

2. Transmit Mode: In this mode the node just discards the any data and puts the data onto the network.

3. By-pass Mode: In this mode reached when the node is down. Any data is just bypassed. There is no
one-bit delay in this mode.

Token Ring Using Ring Concentrator

[Link] 2/7
9/22/23, 9:51 AM CS425: Computer Networks: Lecture 07

One problem with a ring network is that if the cable breaks somewhere, the ring dies. This problem is
elegantly addressed by using a ring concentrator. A Token Ring concentrator simply changes the topology
from a physical ring to a star wired ring. But the network still remains a ring logically. Physically, each
station is connected to the ring concentrator (wire center) by a cable containing at least two twisted pairs, one
for data to the station and one for data from the station. The Token still circulates around the network and is
still controlled in the same manner, however, using a hub or a switch greatly improves reliability because the
hub can automatically bypass any ports that are disconnected or have a cabling fault. This is done by having
bypass relays inside the concentrator that are energized by current from the stations. If the ring breaks or
station goes down, loss of the drive current will release the relay and bypass the station. The ring can then
continue operation with the bad segment bypassed.

Who should remove the packet from the ring ?

There are 3 possibilities-

1. The source itself removes the packet after one full round in the ring.
2. The destination removes it after accepting it: This has two potential problems. Firstly, the solution
won't work for broadcast or multicast, and secondly, there would be no way to acknowledge the sender
about the receipt of the packet.
3. Have a specialized node only to discard packets: This is a bad solution as the specialized node
would know that the packet has been received by the destination only when it receives the packet the
second time and by that time the packet may have actually made about one and half (or almost two in
the worst case) rounds in the ring.

Thus the first solution is adopted with the source itself removing the packet from the ring after a full one
round. With this scheme, broadcasting and multicasting can be handled as well as the destination can
acknowledge the source about the receipt of the packet (or can tell the source about some error).

Token Format

The token is the shortest frame transmitted (24 bit)

MSB (Most Significant Bit) is always transmitted first - as opposed to Ethernet

SD AC ED

SD = Starting Delimiter (1 Octet)

AC = Access Control (1 Octet)
ED = Ending Delimiter (1 Octet)

Starting Delimiter Format:

JKOJKOOO

[Link] 3/7
9/22/23, 9:51 AM CS425: Computer Networks: Lecture 07

J = Code Violation
K = Code Violation

Access Control Format:

PPPTMRRR

T=Token
T = 0 for Token
T = 1 for Frame
When a station with a Frame to transmit detects a token which has a priority equal to or less than
the Frame to be transmitted, it may change the token to a start-of-frame sequence and transmit
the Frame

P = Priority
Priority Bits indicate tokens priority, and therefore, which stations are allowed to use it. Station
can transmit if its priority as at least as high as that of the token.

M = Monitor
The monitor bit is used to prevent a token whose priority is greater than 0 or any frame from
continuously circulating on the ring. If an active monitor detects a frame or a high priority token
with the monitor bit equal to 1, the frame or token is aborted. This bit shall be transmitted as 0 in
all frame and tokens. The active monitor inspects and modifies this bit. All other stations shall
repeat this bit as received.

R = Reserved bits
The reserved bits allow station with high priority Frames to request that the next token be issued
at the requested priority.

Ending Delimiter Format:

JK1JK11E

J = Code Violation
K = Code Violation
I = Intermediate Frame Bit
E = Error Detected Bit

Frame Format:

MSB (Most Significant Bit) is always transmitted first - as opposed to Ethernet

SD AC FC DA SA DATA CRC ED FS

SD=Starting Delimiter(1 octet)

AC=Access Control(1 octet)
FC = Frame Control (1 Octet)
DA = Destination Address (2 or 6 Octets)
SA = Source Address (2 or 6 Octets)
DATA = Information 0 or more octets up to 4027
CRC = Checksum(4 Octets)
ED = Ending Delimiter (1 Octet)
FS=Frame Status

[Link] 4/7
9/22/23, 9:51 AM CS425: Computer Networks: Lecture 07

Starting Delimiter Format:

JK0JK000

J = Code Violation
K = Code Violation

Access Control Format:

PPPTMRRR

T=Token

T = “0” for Token,

T = “1” for Frame.

When a station with a Frame to transmit detects a token which has a priority equal to or less than
the Frame to be transmitted, it may change the token to a start-of-frame sequence and transmit
the Frame.

P = Priority
Bits Priority Bits indicate tokens priority, and therefore, which stations are allowed to use it.
Station can transmit if its priority as at least as high as that of the token.

M = Monitor
The monitor bit is used to prevent a token whose priority is greater than 0 or any frame from
continuously circulating on the ring. if an active monitor detects a frame or a high priority token
with the monitor bit equal to 1, the frame or token is aborted. This bit shall be transmitted as 0 in
all frame and tokens. The active monitor inspects and modifies this bit. All other stations shall
repeat this bit as received.

R = Reserved bits the reserved bits allow station with high priority Frames to request that the
next token be issued at the requested priority

Frame Control Format:

F F CONTROL BITS (6 BITS)

FF= Type of Packet-Regular data packet or MAC layer packet

Control Bits= Used if the packet is for MAC layer protocol itself

Source and Destination Address Format:

The addresses can be of 2 bytes (local address) or 6 bytes (global address).

local address format:

I/G (1 BIT) NODE ADDRESS (15 BITS)

alternatively
I/G (1 BIT) RING ADDRESS (7 BITS) NODE ADDRESS (8 BITS)

The first bit specifies individual or group address.

[Link] 5/7
9/22/23, 9:51 AM CS425: Computer Networks: Lecture 07

universal (global) address format:

I/G (1 BIT) L/U (1 BIT) RING ADDRESS (14 BITS) NODE ADDRESS (32 BITS)

The first bit specifies individual or group address.

The second bit specifies local or global (universal) address.

local group addresses (16 bits):

I/G (1 BIT) T/B(1 BIT) GROUP ADDRESS (14 BITS)

The first bit specifies an individual or group address.

The second bit specifies traditional or bit signature group address.

Traditional Group Address: 2Exp14 groups can be defined.

Bit Signature Group Address: 14 grtoups are defined. A host can be a member of none or any
number of them. For multicasting, those group bits are set to which the packet should go. For
broadcasting, all 14 bits are set. A host receives a packet only if it is a member of a group whose
corresponding bit is set to 1.

universal group addresses (16 bits):

I/G (1 BIT) RING NUMBER T/B (1 BIT) GROUP ADDRESS (14 BITS)

The description is similar to as above.

Data Format:

No upper limit on amount of data as such, but it is limited by the token holding time.

Checksum:

The source computes and sets this value. Destination too calculates this value. If the two are
different, it indicates an error, otherwise the data may be correct.

Frame Status:

It contains the A and C bits.

A bit set to 1: destination recognized the packet.

C bit set to 1: destination accepted the packet.

This arrangement provides an automatic acknowledgement for each frame. The A and C bits are
present twice in the Frame Status to increase reliability in as much as they are not covered by the
checksum.

Ending Delimiter Format:

JK1JK1IE

J = Code Violation
K = Code Violation
I = Intermediate Frame Bit
If this bit is set to 1, it indicates that this packet is an intermediate part of a bigger packet, the

[Link] 6/7
9/22/23, 9:51 AM CS425: Computer Networks: Lecture 07

last packet would have this bit set to 0.

E = Error Detected Bit
This bit is set if any interface detects an error.

This concludes our description of the token ring frame format.

Image References:
[Link]
[Link]

back to top
Prev| Next | Index

[Link] 7/7
9/22/23, 9:51 AM CS425: Computer Networks: Lecture 08

Computer Networks (CS425)

Instructor: Dr. Dheeraj Sanghi

Prev| Next| Index

Token Ring Network (Contd...)

Phase Jitter Compensation :

In a token ring the source starts discarding all it's previously transmitted bits as soon as they circumnavigate
the ring and reach the source. Hence, it's not desirable that while a token is being sent some bits of the token
which have already been sent become available at the incoming end of the source. This behavior though is
desirable in case of data packets which ought to be drained from the ring once they have gone around the
ring. To achieve the aforesaid behavior with respect to tokens, we would like the ring to hold at least 24 bits
at a time. How do we ensure this?

Each node in a ring introduces a 1 bit delay. So, one approach might be to set the minimum limit on the
number of nodes in a ring as 24. But, this is not a viable option. The actual solution is as follows. We have
one node in the ring designated as "monitor". The monitor maintains a 24 bits buffer with help of which it
introduces a 24 bit delay. The catch here is what if the clocks of nodes following the source are faster than
the source? In this case the 24 bit delay of the monitor would be less than the 24 bit delay desired by the
host. To avoid this situation the monitor maintains 3 extra bits to compensate for the faster bits. The 3 extra
bits suffice even if bits are 10 % faster. This compensation is called Phase Jitter Compensation.

Handling multiple priority frames

Each node or packet has a priority level. We don't concern ourselves with how this priority is decided. The
first 3 bits of the Access Control byte in the token are for priority and the last 3 are for reservation.

P P P TM R R R

Initially the reservation bits are set to 000. When a node wants to transmit a priority n frame, it must wait
until it can capture a token whose priority is less than or equal to n. Furthermore, when a data frame goes by,
a station can try to reserve the next token by writing the priority of the frame it wants to send into the frame's
Reservation bits. However, if a higher priority has already been reserved there, the station cannot make a
reservation. When the current frame is finished, the next token is generated at the priority that has been
reserved.

A slight problem with the above reservation procedure is that the reservation priority keeps on increasing. To
solve this problem, the station raising the priority remembers the reservation priority that it replaces and
when it is done it reduces the priority to the previous priority.

Note that in a token ring, low priority frames may starve.

Ring Maintenance

Each token ring has a monitor that oversees the ring. Among the monitor's responsibilities are seeing that the
token is not lost, taking action when the ring breaks, cleaning the ring when garbled frames appear and
watching out for orphan frames. An orphan frame occurs when a station transmits a short frame in it's
entirety onto a long ring and then crashes or is powered down before the frame can be removed. If nothing is
done, the frame circulates indefinitely.

[Link] 1/6
9/22/23, 9:51 AM CS425: Computer Networks: Lecture 08

Detection of orphan frames: The monitor detects orphan frames by setting the monitor bit in the
Access Control byte whenever it passes through. If an incoming frame has this bit set, something is
wrong since the same frame has passed the monitor twice. Evidently it was not removed by the source,
so the monitor drains it.

Lost Tokens: The monitor has a timer that is set to the longest possible tokenless interval : when each
node transmits for the full token holding time. If this timer goes off, the monitor drains the ring and
issues a fresh token.

Garbled frames: The monitor can detect such frames by their invalid format or checksum, drain the
ring and issue a fresh token.

The token ring control frames for maintenance are:

Control
Name Meaning
field
Duplicate address
00000000 Test if two stations have the same address
test
00000010 Beacon Used to locate breaks in the ring
00000011 Claim token Attempt to become monitor
00000100 Purge Reinitialize the ring
Active monitor
00000101 Issued periodically by the monitor
present
Standby monitor
00000110 Announces the presence of potential monitors
present

The monitor periodically issues a message "Active Monitor Present" informing all nodes of its presence.
When this message is not received for a specific time interval, the nodes detect a monitor failure. Each node
that believes it can function as a monitor broadcasts a "Standby Monitor Present" message at regular
intervals, indicating that it is ready to take on the monitor's job. Any node that detects failure of a monitor
issues a "Claim" token. There are 3 possible outcomes :

1. If the issuing node gets back its own claim token, then it becomes the monitor.
2. If a packet different from a claim token is received, apparently a wrong guess of monitor failure was
made. In this case on receipt of our own claim token, we discard it. Note that our claim token may
have been removed by some other node which has detected this error.
3. If some other node has also issued a claim token, then the node with the larger address becomes the
monitor.

In order to resolve errors of duplicate addresses, whenever a node comes up it sends a "Duplicate Address
Detection" message (with the destination = source) across the network. If the address recognize bit has been
set on receipt of the message, the issuing node realizes a duplicate address and goes to standby mode. A node
informs other nodes of removal of a packet from the ring through a "Purge" message. One maintenance
function that the monitor cannot handle is locating breaks in the ring. If there is no activity detected in the
ring (e.g. Failure of monitor to issue the Active Monitor Present token...) , the usual procedures of sending
a claim token are followed. If the claim token itself is not received besides packets of any other kind, the
node then sends "Beacons" at regular intervals until a message is received indicating that the broken ring
has been repaired.

Other Ring Networks

The problem with the token ring system is that large rings cause large delays. It must be made possible for
multiple packets to be in the ring simultaneously. The following ring networks resolve this problem to some
extent :-

[Link] 2/6
9/22/23, 9:51 AM CS425: Computer Networks: Lecture 08

Slotted Ring :

In this system, the ring is slotted into a number of fixed size frames which are continuously moving around
the ring. This makes it necessary that there be enough number of nodes (large ring size) to ensure that all the
bits can stay on the ring at the same time. The frame header contains information as to whether the slots are
empty or full. The usual disadvantages of overhead/wastage associated with fixed size frames are present.

Register Insertion Rings :

This is an improvement over slotted ring architecture. The network interface consists of two registers : a shift
register and an output buffer. At startup, the input pointer points to the rightmost bit position in the input shift
register .When a bit arrives it is in the rightmost empty position (the one indicated by the input pointer). After
the node has detected that the frame is not addressed to it, the bits are transmitted one at time (by shifting).
As new bits come in, they are inserted at the position indicated by the pointer and then the contents are
shifted. Thus the pointer is not moved. Once the shift register has pushed out the last bit of a frame, it checks
to see if it has an output frame waiting. In case yes, then it checks that if the number of empty slots in the
shift register is at least equal to the number of bits in the output frame. After this the output connection is
switched to this second register and after the register has emptied its contents, the output line is switched
back to the shift register. Thus, no single node can hog the bandwidth. In a loaded system, a node can
transmit a k-bit frame only if it has saved up a k-bits of inter frame gaps.

[Link] 3/6
9/22/23, 9:51 AM CS425: Computer Networks: Lecture 08

Two major disadvantages of this topology are complicated hardware and difficulty in the detection of
start/end of packets.

Contention Ring

The token ring has primarily two problems:

On light loads, huge overhead is incurred for token passing.

Nodes with low priority data may starve if there is always a node with high priority data.

A contention ring attempts to address these problems. In a contention ring, if there is no communication in
the ring for a while, a sender node will send its data immediately, followed by a token. If the token comes
back to the sender without any data packet in between, the sender removes it from the ring. However under
heavy load the behavior is that of a normal token ring. In case a collision, each of the sending nodes will
remove the others' data packet from the ring, back off for a random period of time and then resend their data.

IEEE 802.4: Token Bus Network

In this system, the nodes are physically connected as a bus, but logically form a ring with tokens passed
around to determine the turns for sending. It has the robustness of the 802.3 broadcast cable and the known
worst case behavior of a ring. The structure of a token bus network is as follows:

Frame Structure

A 802.4 frame has the following fields:

Preamble: The Preamble is used to synchronize the receiver's clock.

Starting Delimiter (SD) and End Delimiter (ED): The Starting Delimiter and Ending Delimiter fields
are used to mark frame boundaries. Both of them contain analog encoding of symbols other than 1 or 0
so that they cannot occur accidentally in the user data. Hence no length field is needed.
Frame Control (FC): This field is used to distinguish data frames from control frames. For data frames,
it carries the frame's priority as well as a bit which the destination can set as an acknowledgement. For
control frames, the Frame Control field is used to specify the frame type. The allowed types include
token passing and various ring maintenance frames.

[Link] 4/6
9/22/23, 9:51 AM CS425: Computer Networks: Lecture 08

Destination and Source Address: The Destination and Source address fields may be 2 bytes (for a local
address) or 6 bytes (for a global address).
Data: The Data field carries the actual data and it may be 8182 bytes when 2 byte addresses are used
and 8174 bytes for 6 byte addresses.
Checksum: A 4-byte checksum calculated for the data. Used in error detection.

Ring Maintenance:

Mechanism:

When the first node on the token bus comes up, it sends a Claim_token packet to initialize the ring. If more
than one station send this packet at the same time, there is a collision. Collision is resolved by a contention
mechanism, in which the contending nodes send random data for 1, 2, 3 and 4 units of time depending on the
first two bits of their address. The node sending data for the longest time wins. If two nodes have the same
first two bits in their addresses, then contention is done again based on the next two bits of their address and
so on.

After the ring is set up, new nodes which are powered up may wish to join the ring. For this a node sends
Solicit_successor_1 packets from time to time, inviting bids from new nodes to join the ring. This packet
contains the address of the current node and its current successor, and asks for nodes in between these two
addresses to reply. If more than one nodes respond, there will be collision. The node then sends a
Resolve_contention packet, and the contention is resolved using a similar mechanism as described
previously. Thus at a time only one node gets to enter the ring. The last node in the ring will send a
Solicit_successor_2 packet containing the addresses of it and its successor. This packet asks nodes not
having addresses in between these two addresses to respond.

A question arises that how frequently should a node send a Solicit_successor packet? If it is sent too
frequently, then overhead will be too high. Again if it is sent too rarely, nodes will have to wait for a long
time before joining the ring. If the channel is not busy, a node will send a Solicit_successor packet after a
fixed number of token rotations. This number can be configured by the network administrator. However if
there is heavy traffic in the network, then a node would defer the sending of bids for successors to join in.

There may be problems in the logical ring due to sudden failure of a node. What happens when a node goes
down along with the token? After passing the token, a node, say node A, listens to the channel to see if its
successor either transmits the token or passes a frame. If neither happens, it resends a token. Still if nothing
happens, A sends a Who_follows packet, containing the address of the down node. The successor of the
down node, say node C, will now respond with a Set_successor packet, containing its own address. This
causes A to set its successor node to C, and the logical ring is restored. However, if two successive nodes go
down suddenly, the ring will be dead and will have to be built afresh, starting from a Claim_token packet.

When a node wants to shutdown normally, it sends a Set_successor packet to its predecessor, naming its own
successor. The ring then continues unbroken, and the node goes out of the ring.

The various control frames used for ring maintenance are shown below:

Frame Control Field Name Meaning

Claim token during ring

00000000 Claim_token
maintenance
00000001 Solicit_successor_1 Allow stations to enter the ring
00000010 Solicit_successor_2 Allow stations to enter the ring
00000011 Who_follows Recover from lost token
Used when multiple stations want
00000100 Resolve_contention
to enter
00001000 Token Pass the token
[Link] 5/6
9/22/23, 9:51 AM CS425: Computer Networks: Lecture 08

00001100 Set_successor Allow the stations leave the ring

Priority Scheme:
Token bus supports four distinct priority levels: 0, 2, 4 and 6.

0 is the lowest priority level and 6 the highest. The following times are defined by the token bus:

THT: Token Holding Time. A node holding the token can send priority 6 data for a maximum of this
amount of time.
TRT_4: Token Rotation Time for class 4 data. This is the maximum time a token can take to circulate
and still allow transmission of class 4 data.

TRT_2 and TRT_0: Similar to TRT_4.

When a station receives data, it proceeds in the following manner:

It transmits priority 6 data for at most THT time, or as long as it has data.
Now if the time for the token to come back to it is less than TRT_4, it will transmit priority 4 data, and
for the amount of time allowed by TRT_4. Therefore the maximum time for which it can send priority
4 data is= Actual TRT - THT - TRT_4
Similarly for priority 2 and priority 0 data.

This mechanism ensures that priority 6 data is always sent, making the system suitable for real time data
transmission. In fact this was one of the primary aims in the design of token bus.

Image References:

[Link]
[Link]
[Link]

back to top
Prev| Next | Index

[Link] 6/6
TCP/IP Overview
Document ID: 13769

Contents
Introduction
TCP/IP Technology
TCP
IP
Routing in IP Environments
Interior Routing Protocols
RIP
IGRP
EIGRP
OSPF
Integrated IS−IS
Exterior Routing Protocols
EGP
BGP
Cisco's TCP/IP Implementation
Access Restrictions
Tunneling
IP Multicast
Suppressing Network Information
Administrative Distance
Routing Protocol Redistribution
Serverless Network Support
Network Monitoring and Debugging
Summary
Related Information
Introduction
In the two decades since their invention, the heterogeneity of networks has expanded further with the
deployment of Ethernet, Token Ring, Fiber Distributed Data Interface (FDDI), X.25, Frame Relay, Switched
Multimegabit Data Service (SMDS), Integrated Services Digital Network (ISDN), and most recently,
Asynchronous Transfer Mode (ATM). The Internet protocols are the best proven approach to internetworking
this diverse range of LAN and WAN technologies.

The Internet Protocol suite includes not only lower−level specifications, such as Transmission Control
Protocol (TCP) and Internet Protocol (IP), but specifications for such common applications as electronic mail,
terminal emulation, and file transfer. Figure 1 shows the TCP/IP protocol suite in relation to the OSI
Reference model. Figure 2 shows some of the important Internet protocols and their relationship to the OSI
Reference Model. For information on the OSI Reference model and the role of each layer, please refer to the
document Internetworking Basics.

The Internet protocols are the most widely implemented multivendor protocol suite in use today. Support for
at least part of the Internet Protocol suite is available from virtually every computer vendor.
TCP/IP Technology
This section describes technical aspects of TCP, IP, related protocols, and the environments in which these
protocols operate. Because the primary focus of this document is routing (a layer 3 function), the discussion of
TCP (a layer 4 protocol) will be relatively brief.

TCP
TCP is a connection−oriented transport protocol that sends data as an unstructured stream of bytes. By using
sequence numbers and acknowledgment messages, TCP can provide a sending node with delivery information
about packets transmitted to a destination node. Where data has been lost in transit from source to destination,
TCP can retransmit the data until either a timeout condition is reached or until successful delivery has been
achieved. TCP can also recognize duplicate messages and will discard them appropriately. If the sending
computer is transmitting too fast for the receiving computer, TCP can employ flow control mechanisms to
slow data transfer. TCP can also communicates delivery information to the upper−layer protocols and
applications it supports. All these characteristics makes TCP an end−to−end reliable transport protocol. TCP
is specified in RFC 793 .

Figure 1 TCP/IP Protocol Suite in Relation to the OSI Reference Model

Figure 2 Important Internet Protocols in Relation to the OSI Reference Model

Refer to the TCP section of Internet Protocols for more information.

IP
IP is the primary Layer 3 protocol in the Internet suite. In addition to internetwork routing, IP provides error
reporting and fragmentation and reassembly of information units called datagrams for transmission over
networks with different maximum data unit sizes. IP represents the heart of the Internet Protocol suite.

Note: The term IP in the section refers to IPv4 unless otherwise stated explicitly.

IP addresses are globally unique, 32−bit numbers assigned by the Network Information Center. Globally
unique addresses permit IP networks anywhere in the world to communicate with each other.

An IP address is divided into two parts. The first part designates the network address while the second part
designates the host address.

The IP address space is divided into different network classes. Class A networks are intended mainly for use
with a few very large networks, because they provide only 8 bits for the network address field. Class B
networks allocate 16 bits, and Class C networks allocate 24 bits for the network address field. Class C
networks only provide 8 bits for the host field, however, so the number of hosts per network may be a limiting
factor. In all three cases, the left most bit(s) indicate the network class. IP addresses are written in dotted
decimal format; for example, [Link]. Figure 3 shows the address formats for Class A, B, and C IP networks.

Figure 3 Address Formats for Class A, B, and C IP Networks

IP networks also can be divided into smaller units called subnetworks or "subnets." Subnets provide extra
flexibility for the network administrator. For example, assume that a network has been assigned a Class A
address and all the nodes on the network use a Class A address. Further assume that the dotted decimal
representation of this network's address is [Link]. (All zeros in the host field of an address specify the entire
network.) The administrator can subdivide the network using subnetting. This is done by "borrowing" bits
from the host portion of the address and using them as a subnet field, as depicted in Figure 4.

Figure 4 "Borrowing" Bits

If the network administrator has chosen to use 8 bits of subnetting, the second octet of a Class A IP address
provides the subnet number. In our example, address [Link] refers to network 34, subnet 1; address [Link]
refers to network 34, subnet 2, and so on.

The number of bits that can be borrowed for the subnet address varies. To specify how many bits are used to
represent the network and the subnet portion of the address, IP provides subnet masks. Subnet masks use the
same format and representation technique as IP addresses. Subnet masks have ones in all bits except those that
specify the host field. For example, the subnet mask that specifies 8 bits of subnetting for Class A address
[Link] is [Link]. The subnet mask that specifies 16 bits of subnetting for Class A address [Link] is
[Link]. Both of these subnet masks are pictured in Figure 5. Subnet masks can be passed through a
network on demand so that new nodes can learn how many bits of subnetting are being used on their network.

Figure 5 Subnet Masks

Traditionally, all subnets of the same network number used the same subnet mask. In other words, a network
manager would choose an eight−bit mask for all subnets in the network. This strategy is easy to manage for
both network administrators and routing protocols. However, this practice wastes address space in some
networks. Some subnets have many hosts and some have only a few, but each consumes an entire subnet
number. Serial lines are the most extreme example, because each has only two hosts that can be connected via
a serial line subnet.

As IP subnets have grown, administrators have looked for ways to use their address space more efficiently.
One of the techniques that has resulted is called Variable Length Subnet Masks (VLSM). With VLSM, a
network administrator can use a long mask on networks with few hosts and a short mask on subnets with
many hosts. However, this technique is more complex than making them all one size, and addresses must be
assigned carefully.
Of course in order to use VLSM, a network administrator must use a routing protocol that supports it. Cisco
routers support VLSM with Open Shortest Path First (OSPF), Integrated Intermediate System to Intermediate
System (Integrated IS−IS), Enhanced Interior Gateway Routing Protocol (Enhanced IGRP), and static routing.
Refer to IP Addressing and Subnetting for New Users for more information about IP addressing and
subnetting.

On some media, such as IEEE 802 LANs, IP addresses are dynamically discovered through the use of two
other members of the Internet protocol suite: Address Resolution Protocol (ARP) and Reverse Address
Resolution Protocol (RARP). ARP uses broadcast messages to determine the hardware (MAC layer) address
corresponding to a particular network−layer address. ARP is sufficiently generic to allow use of IP with
virtually any type of underlying media access mechanism. RARP uses broadcast messages to determine the
network−layer address associated with a particular hardware address. RARP is especially important to
diskless nodes, for which network−layer addresses usually are unknown at boot time.

Routing in IP Environments
An "internet" is a group of interconnected networks. The Internet, on the other hand, is the collection of
networks that permits communication between most research institutions, universities, and many other
organizations around the world. Routers within the Internet are organized hierarchically. Some routers are
used to move information through one particular group of networks under the same administrative authority
and control. (Such an entity is called an autonomous system.) Routers used for information exchange within
autonomous systems are called interior routers, and they use a variety of interior gateway protocols (IGPs) to
accomplish this end. Routers that move information between autonomous systems are called exterior routers;
they use the Exterior Gateway Protocol (EGP) or Border Gateway Protocol (BGP). Figure 6 shows the
Internet architecture.

Figure 6 Representation of the Internet Architecture

Routing protocols used with IP are dynamic in nature. Dynamic routing requires the software in the routing
devices to calculate routes. Dynamic routing algorithms adapt to changes in the network and automatically
select the best routes. In contrast with dynamic routing, static routing calls for routes to be established by the
network administrator. Static routes do not change until the network administrator changes them.

IP routing tables consist of destination address/next hop pairs. This sample routing table from a Cisco router
shows that the first entry is interpreted as meaning "to get to network [Link] (subnet 1 on network 34), the
next stop is the node at address [Link]":

R6−2500# show ip route

Codes: C − connected, S − static, I − IGRP, R − RIP, M − mobile, B − BGP
D − EIGRP, EX − EIGRP external, O − OSPF, IA − OSPF inter area
N1 − OSPF NSSA external type 1, N2 − OSPF NSSA external type 2
E1 − OSPF external type 1, E2 − OSPF external type 2, E − EGP
i − IS−IS, su − IS−IS summary, L1 − IS−IS level−1, L2 − IS−IS level−2
ia − IS−IS inter area, * − candidate default, U − per−user static route
o − ODR, P − periodic downloaded static route
Gateway of last resort is not set
[Link]/16 is subnetted, 1 subnets
O [Link] [110/65] via [Link], 00:00:51, Serial0
[Link]/24 is subnetted, 1 subnets
C [Link] is directly connected, Serial0
R6−2500#

As we have seen, IP routing specifies that IP datagrams travel through an internetwork one router hop at a
time. The entire route is not known at the outset of the journey. Instead, at each stop, the next router hop is
determined by matching the destination address within the datagram with an entry in the current node's
routing table. Each node's involvement in the routing process consists only of forwarding packets based on
internal information. IP does not provide for error reporting back to the source when routing anomalies occur.
This task is left to another Internet protocolthe Internet Control Message Protocol (ICMP).

ICMP performs a number of tasks within an IP internetwork. In addition to the principal reason for which it
was created (reporting routing failures back to the source), ICMP provides a method for testing node
reachability across an internet (the ICMP Echo and Reply messages), a method for increasing routing
efficiency (the ICMP Redirect message), a method for informing sources that a datagram has exceeded its
allocated time to exist within an internet (the ICMP Time Exceeded message), and other helpful messages. All
in all, ICMP is an integral part of any IP implementation, particularly those that run in routers. See the Related
Information section of this document for more information on ICMP.

Interior Routing Protocols

Interior Routing Protocols (IGPs) operate within autonomous systems. The following sections provide brief
descriptions of several IGPs that are currently popular in TCP/IP networks. For additional information on
these protocols, please refer to the links in the Related Information section below.

RIP
A discussion of routing protocols within an IP environment must begin with the Routing Information Protocol
(RIP). RIP was developed by Xerox Corporation in the early 1980s for use in Xerox Network Systems (XNS)
networks. Today, many PC networks use routing protocols based on RIP.

RIP works well in small environments but has serious limitations when used in larger internetworks. For
example, RIP limits the number of router hops between any two hosts in an internet to 16. RIP is also slow to
converge, meaning that it takes a relatively long time for network changes to become known to all routers.
Finally, RIP determines the best path through an internet by looking only at the number of hops between the
two end nodes. This technique ignores differences in line speed, line utilization, and all other metrics, many of
which can be important factors in choosing the best path between two nodes. For this reason, many companies
with large internetworks are migrating away from RIP to more sophisticated routing protocols.

IGRP
With the creation of the Interior Gateway Routing Protocol (IGRP) in the early 1980s, Cisco Systems was the
first company to solve the problems associated with using RIP to route datagrams between interior routers.
IGRP determines the best path through an internet by examining the bandwidth and delay of the networks
between routers. IGRP converges faster than RIP, thereby avoiding the routing loops caused by disagreement
over the next routing hop to be taken. Further, IGRP does not share RIP's hop count limitation. As a result of
these and other improvements over RIP, IGRP enabled many large, complex, topologically diverse
internetworks to be deployed.

EIGRP
Cisco has enhanced IGRP to handle the increasingly large, mission−critical networks being designed today.
This enhanced version of IGRP is called Enhanced IGRP. Enhanced IGRP combines the ease of use of
traditional distance vector routing protocols with the fast rerouting capabilities of the newer link state routing
protocols.

Enhanced IGRP consumes significantly less bandwidth than IGRP because it is able to limit the exchange of
routing information to include only the changed information. In addition, Enhanced IGRP is capable of
handling AppleTalk and Novell IPX routing information, as well as IP routing information.

OSPF
OSPF was developed by the Internet Engineering Task Force (IETF) as a replacement for RIP. OSPF is based
on work started by John McQuillan in the late 1970s and continued by Radia Perlman and Digital Equipment
Corporation (DEC) in the mid−1980s. Every major IP routing vendor supports OSPF.

OSPF is an intradomain, link state, hierarchical routing protocol. OSPF supports hierarchical routing within
an autonomous system. Autonomous systems can be divided into routing areas. A routing area is typically a
collection of one or more subnets that are closely related. All areas must connect to the backbone area.

OSPF provides fast rerouting and supports variable length subnet masks.

Integrated IS−IS
ISO 10589 (IS−IS) is an intradomain, link state, hierarchical routing protocol used as the DECnet Phase V
routing algorithm. It is similar in many ways to OSPF. IS−IS can operate over a variety of subnetworks,
including broadcast LANs, WANs, and point−to−point links.

Integrated IS−IS is an implementation of IS−IS for more than just OSI protocols. Today, Integrated IS−IS
supports both OSI and IP protocols.

Like all integrated routing protocols, Integrated IS−IS calls for all routers to run a single routing algorithm.
Link state advertisements sent by routers running Integrated IS−IS include all destinations running either IP or
OSI network−layer protocols. Protocols such as ARP and ICMP for IP and End System−to−Intermediate
System (ES−IS) for OSI must still be supported by routers running Integrated IS−IS.
Exterior Routing Protocols
EGPs provide routing between autonomous systems. The two most popular EGPs in the TCP/IP community
are discussed in this section.

EGP
The first widespread exterior routing protocol was the Exterior Gateway Protocol. EGP provides dynamic
connectivity but assumes that all autonomous systems are connected in a tree topology. This was true in the
early Internet but is no longer true.

Although EGP is a dynamic routing protocol, it uses a very simple design. It does not use metrics and
therefore cannot make true intelligent routing decisions. EGP routing updates contain network reachability
information. In other words, they specify that certain networks are reachable through certain routers. Because
of its limitations with regard to today's complex internetworks, EGP is being phased out in favor of routing
protocols such as BGP.

BGP
BGP represents an attempt to address the most serious of EGP's problems. Like EGP, BGP is an interdomain
routing protocol created for use in the Internet core routers. Unlike EGP, BGP was designed to prevent
routing loops in arbitrary topologies and to allow policy−based route selection.

BGP was co−authored by a Cisco founder, and Cisco continues to be very involved in BGP development. The
latest revision of BGP, BGP4, was designed to handle the scaling problems of the growing Internet.

Cisco's TCP/IP Implementation

In addition to IP and TCP, the Cisco TCP/IP implementation supports ARP, RARP, ICMP, Proxy ARP (in
which the router acts as an ARP server on behalf of another device), Echo, Discard, and Probe (an address
resolution protocol developed by Hewlett−Packard Company and used on IEEE 802.3 networks). Cisco
routers also can be configured to use the Domain Name System (DNS) when host name−to−address mappings
are needed.

IP hosts need to know how to reach a router. There are several ways this can be done:

• Add a static route in the host pointing to a router.

• Run RIP or some other IGP on the host.
• Run the ICMP Router Discovery Protocol (IRDP) in the host.
• Run Proxy ARP on the router.

Cisco routers support all of these methods.

Cisco provides many TCP/IP value−added features that enhance applications availability and reduce the total
cost of internetwork ownership. The most important of these features are described in the following section.

Access Restrictions
Most networks have reasonably straightforward access requirements. To address these issues, Cisco
implements access lists, a scheme that prevents certain packets from entering or leaving particular networks.
An access list is a sequential list of instructions to either permit or deny access through a router interface
based on IP address or other criteria. For example, an access list could be created to deny access to a particular
resource from all computers on one network segment but permit access from all other segments. Another
access list could be used to permit TCP connections from any host on a local segment to any host in the
Internet but to deny all connections from the Internet into the local net except for electronic mail connections
to a particular designated mail host. Access lists are extremely flexible, powerful security measures and are
available not only for IP, but for many other protocols supported by Cisco routers.

Other access restrictions are provided by the Department of Defense−specified security extensions to IP.
Cisco supports both the Basic and the Extended security options as described in RFC 1108 of the IP
Security Option (IPSO). Support of both access lists and the IPSO makes Cisco a good choice for networks
where security is an issue.

Tunneling
Cisco's TCP/IP implementation includes several schemes that allow foreign protocols to be tunneled through
an IP network. Tunneling allows network administrators to extend the size of AppleTalk and Novell IPX
networks beyond the size that their native protocols can handle.

IP Multicast
The applications that use the TCP/IP protocol suite continue to evolve. The next set of applications on which a
lot of work is being done include those that use video and audio information. Cisco continues to be actively
involved with the Internet Engineering Task Force (IETF) in defining standards that will enable network
administrators to add audio and video applications to their existing networks. Cisco supports the Protocol
Independent Multicast (PIM) standard. In addition, Cisco's implementation provides interoperability with the
MBONE, a research multicast backbone that exists today.

IP multicasting (the ability to send IP datagrams to multiple nodes in a logical group) is an important building
block for applications such as video. Video teleconferencing, for example, requires the ability to send video
information to multiple teleconference sites. If one IP multicast datagram containing video information can be
sent to multiple teleconference sites, network bandwidth is saved and time synchronization is closer to
optimal.

Suppressing Network Information

In some cases, it may be useful to suppress information about certain networks. Cisco routers provide an
extensive set of configuration options that allow an administrator to tailor the exchange of routing information
within a particular routing protocol. Both incoming and outgoing information can be controlled using a set of
commands designed for this purpose. For example, networks can be excluded from routing advertisements,
routing updates can be prevented from reaching certain networks, and other similar actions can be taken.

Administrative Distance
In large networks, some routers and routing protocols are more reliable sources of routing information than
others. Cisco IP routing software permits the reliability of information sources to be quantified by the network
administrator with the administrative distance metric. When administrative distance is specified, the router
can select between sources of routing information based on the reliability of the source. For example, if a
router uses both IGRP and RIP, one might set the administrative distances to reflect greater confidence in the
IGRP information. The router would then use IGRP information when available. If the source of IGRP
information failed, the router automatically would use RIP information as a backup until the IGRP source
became available again.
Routing Protocol Redistribution
Translation between two environments using different routing protocols requires that routes generated by one
protocol be redistributed into the second routing protocol environment. Route redistribution gives a company
the ability to run different routing protocols in workgroups or areas where each is particularly effective. By
not restricting customers to using only a single routing protocol, Cisco's route redistribution feature minimizes
cost while maximizing technical advantage through diversity.

Cisco permits routing protocol redistribution between any of its supported routing protocols. Static route
information can also be redistributed. Further, defaults can be assigned so that one routing protocol can use
the same metric for all redistributed routes, thereby simplifying the routing redistribution mechanism.

Serverless Network Support

Cisco pioneered the mechanisms that allow network administrators to build serverless networks. Helper
addresses, RARP, and BOOTP allow network administrators to place servers far away from the workstations
that depend on them, thereby easing network design constraints.

Network Monitoring and Debugging

With today's complex, diverse network topologies, a router's ability to aid the monitoring and debugging
process is critical. As the junction point for multiple segments, a router sees more of the complete network
than most other devices. Many problems can be detected and/or solved using information that routinely passes
through the router.

The Cisco IP routing implementation provides commands that display:

• The current state of the routing table, including the routing protocol that derived the route, the
reliability of the source, the next IP address to send to, the router interface to use, whether the network
is subnetted, whether the network in question is directly connected, and any routing metrics.
• The current state of the active routing protocol process, including its update interval, metric weights
(if applicable), active networks for which the routing process is functioning, and routing information
sources.
• The active accounting database, including the number of packets and bytes exchanged between
particular sources and destinations.
• The contents of the IP cache, including the destination IP address, the interface through which that
destination is reached, the encapsulation method used, and the hardware address found at that
destination.

IP−related interface parameters, including whether the interface and interface physical layer hardware
are up, whether certain protocols (such as ICMP and Proxy ARP) are enabled, and the current security
level.
• IP−related protocol statistics, including the number of packets and number of errors received and sent
by the following protocols: IP, TCP, User Datagram Protocol (UDP), EGP, IGRP, Enhanced IGRP,
OSPF, IS−IS, ARP, and Probe.
• Logging of all BGP, EGP, ICMP, IGRP, Enhanced IGRP, OSPF, IS−IS, RIP, TCP, and UDP
transactions.
• The number of intermediate hops taken as a packet traverses the network.
• Reachability information between nodes.
Summary
IP is one of over 20 protocols that can be simultaneously routed and bridged by any Cisco routers. Cisco has
added features to its IP implementation that optimize the performance of Cisco routers in larger,
enterprise−wide internetworks.

Related Information
• Troubleshooting TCP/IP
• IP Routed Protocols Support Page
• IP Routing Support Page
• Technical Support − Cisco Systems

Contacts & Feedback | Help | Site Map

© 2014 − 2015 Cisco Systems, Inc. All rights reserved. Terms & Conditions | Privacy Statement | Cookie Policy | Trademarks of
Cisco Systems, Inc.

Updated: Aug 10, 2005 Document ID: 13769