Selected Topics in Network Design

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Selected Topics in Network Design

Course Objectives

• To provide a broad overview of some advanced wireless networks including their architectures and design issues pertaining to link layer and network layer
• To develop mathematical skills to analyze some of the network design issues
• To develop design fundamentals which can help students to take up projects in wireless networking

Selected Topics in Network Design

Course Outcomes

• Understand the fundamentals of wireless networks
• Design simple protocols for wireless networks
• Apply link access technique according to the network architecture
• Analyze the design issues in wireless networks
• Develop ideas for pursuing student projects in wireless networking domain

Selected Topics in Network Design

Course Content

Unit 1 - Introduction

1. Wireless channel characteristics, Wireless networking fundamentals, Wireless network architectures, Wireless networking standards
2. Wireless protocols: Link layer, Network layer and Transport layer.

Selected Topics in Network Design

Course Content

Unit 2 - Network Design and Analysis

1. Defining system model: Decision variables, constants, objectives and constraints; Simulating data packet arrivals and random variables for various propagation models, Problem formulation/algorithm
2. Fundamentals of Markov chains, Analysis using Markov chains,
3. Basics of Optimization

Selected Topics in Network Design

Course Content

Unit 3 -  Cognitive Radio Networks

1. Concepts, Spectrum sensing, Cooperative spectrum sensing, Dynamic spectrum access, Network architectures: Centralized and distributed, multichannel allocation problem, multihop communication, QoS; Design and analysis examples.

Selected Topics in Network Design

Course Content

Unit 4 – Next Generation Wireless Networks

1. LTE and LTE-A fundamentals, Radio specifications, Frame format, Design and analysis of LTE-A Resource Allocation Problems;
2. Overview of 5G networks: Cloud RAN, Small scale heterogeneous networks (HetNets), Wireless backhaul networks;
3. Design and Analysis of 5G Resource Allocation Problems.

Selected Topics in Network Design

Course Content

Unit 5 - Other Ad hoc Networks

1. Sensor networks: Applications, Challenges, Network architecture, Link layer and routing issues
2. VANETs: Applications, IEEE 802.11p standard, Link layer issues, WAVE specification, Design and analysis examples: MAC protocols for VANETs
3. Wireless personal area networks (Bluetooth and Zigbee): PHY, MAC and message format

Selected Topics in Network Design

Introduction

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

What is a wireless spectrum?

• Wireless radio spectrum ranges from 900 MHz to 5 GHz

​

​

​

​

​

• Wireless radio spectrum is classified as licensed and unlicensed bands
• Licensed bands are bought by private operators (e.g., cellular operators, FM station) or authorized by the government (e.g., military, public safety, satellite)

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

What is a wireless spectrum?

• Spectrum usage guidelines are given by International Telecommunication Union Radiocommunication (ITU-R)
• Govt. bodies give recommendations for wireless spectrum usage in a given region based on the ITU-R guidelines
• Examples: India (TRAI), US (FCC), UK (OFCOM)
• Some international bodies are involved in standardizing the spectrum usage and wireless device design
• Examples: IEEE, ETSI, WiFi Alliance, etc.
• Wireless communication is more challenging compared to wired communication as the transmitted signal undergoes scattering, reflection and diffraction.

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

What is a wireless channel?

• Wireless channel refers to a logical communication path between a sender and a receiver over a to a band of frequencies
• Wireless channel capacity (throughput) depends on the bandwidth, operating frequency, transmit power, distance, obstacles, environment, time of use, number of contenders
• The amplitude and phase of the received signal are affected by the above factors
• The received signal exhibits random characteristics which can be described statistically

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

How are wireless channels accessed?

• Wireless channels can be shared or exclusively assigned

​

​

​

​

• Wireless channels are shared using link layer protocols (i.e., channel sensing and random access)
• Wireless channels are exclusively assigned using central controller (i.e., scheduled using base station)
• Exclusive access is achieved by multiple access techniques

Selected Topics in Network Design

Introduction – Wireless Channel Characteristics

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

What is free space path loss?

• In an ideal environment, the received power varies according to the wavelength and the distance between the transmitter and the receiver

​

​

• Here, d₀ is between 1-10 m indoors or 10-100 m outdoors
• In the above scenario, the difference between the transmit power (dB) and received power (dB) is referred to as free space path loss (denoted by K).

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

What is free space path loss?

• Received power due to general path loss, factoring different settings (e.g., urban, without LOS, etc.) is given by

​

​

• Here, ϒ is called path loss exponent

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

Free space path loss: Example #1

• If a unity gain antenna transmits 50 W power at 900 MHz carrier frequency, find the received power (dBm) at a reference distance of 100 m from the transmitter. Compare received power with transmit power. What is the received power at 10 km?
• Solution:
• Here, d₀ = 100 m

​

​

• Expressed in dBm, we get

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

Free space path loss: Example #1

• Solution:
• Here, d = 10 km and ϒ = 2

​

​

​

• Note that

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

What is range?

• Let S_min denote the receiver sensitivity (minimum detectable signal strength), then using Frii’s equation we get the range d_max

​

​

• Coverage area (range) is defined as the percentage of area in a cell which has the SNR above some minimum.

​

​

​

• Here, kT₀B is referred to as thermal noise of ideal receiver
• B is bandwidth and NF is noise figure

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

What is fading?

• Obstacles between the transmitter and receiver cause scattering, reflection and diffraction of the transmitted signal
• Reflected signals take longer path than line-of-sight (LOS) signal.
• Hence, the reflected signals arrive after delays
• The delayed copies of the transmitted signal arrive either in phase or out of phase with one another.
• This causes the received signal strength to fluctuate. This is referred to as fading.

​

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

What is fading?

• In a mobile-radio environment, each reflected signal has its own Doppler shift, time delay, and path attenuation, and multipath propagation results in a time-varying signal as the mobile moves position
• Such a channel is linear, but time-varying
• Doppler shift means changes (increases or decreases) in the carrier frequency
• The number of multipath signals received in a given time slot will vary
• The inter-arrival times between multipath signals can also vary

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

What is fading?

• The Doppler shift is given by

​

​

​

• Here, v is velocity and 𝜃 is angle of incidence of the received signal
• Different types of fading occur based on the direction of motion and area over which the motion occurs
• Next, we see small scale fading (or multipath fading) followed by large scale fading (or shadowing)

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

What is small scale fading (multipath fading)?

• Small scale fading refers to the rapid changes of the amplitude and phase of a radio signal over a short period of time (on the order of seconds) or a short distance (a few wavelengths)
• When no LOS is involved, the statistics of the channel fluctuations follows Rayleigh distribution
• When LOS is involved, the statistics of the channel fluctuations follows Rician distribution
• Multipath fading can be classified as flat (wide band) or frequency selective (narrow band) depending on the observed statistics over the channel bandwidth and over the bandwidth occupied by the transmitted signal

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

What is small scale fading (multipath fading)?

• Multipath fading can be classified as fast or slow depending on the observed statistics over the symbol period of the transmitted signal
• The classifications based on statistics observed over time and bandwidth are independent

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

What is large scale fading (shadowing)?

• It represents the average signal-power attenuation (i.e., path loss) due to motion over large distances (several 100s or 1000s of meters)
• It is impacted by terrain configuration between the transmitter and receiver
• Examination of the power over such a distance reveals that the power fluctuates around a mean value and these fluctuations have a rather long period.
• The statistics of large-scale fading are log-normally distributed with 𝜎 of 4-13 dB for outdoor channels

​

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

Effect due to path loss, multipath fading and shadowing

​

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

Effect due to path loss, multipath fading and shadowing

​

Wireless Channel Characteristics

SELECTED TOPICS IN NETWORK DESIGN

Achievable data rate

• Capacity or achievable data rate (C) is expressed by Shannon formula
• When wireless channels are orthogonally assigned, no interference occurs
• When wireless channels are shared, interference occurs

Selected Topics in Network Design

Introduction – Networking Fundamentals

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Networking Fundamentals

SELECTED TOPICS IN NETWORK DESIGN

What is wireless networking?

• Wireless networking deals with data transmission over wireless medium

Networking Fundamentals

SELECTED TOPICS IN NETWORK DESIGN

What is wireless networking?

• Wireless networking deals with data transmission over wireless medium

Networking Fundamentals

SELECTED TOPICS IN NETWORK DESIGN

What is wireless networking?

• Partly or entirely, the communication path between the sender-receiver pair consists of wireless links and switches/routers
• Wireless medium affects each sub-task under the data communication process
• A typical data communication process is depicted logically into a set of layers referred to as the TCP/IP protocol stack
• Thus, the operations of the upper layers must be adapted in response to the unreliable wireless medium

Networking Fundamentals

SELECTED TOPICS IN NETWORK DESIGN

Recap of TCP/IP protocol stack

• Data is generated and formatted by the application layer
• Transport layer deals with segmentation and reassembly of large data packets. Can supports reliable data transfer (QoS)
• Network layer deals with moving the data packets towards the destination using IP
• Link layer deals with delivering packets across each link by overcoming packet collision
• Physical layer encodes the data to minimize bit errors at the destination node.
• Sender and receiver follow top down and bottom up approach respectively

Networking Fundamentals

SELECTED TOPICS IN NETWORK DESIGN

Role of PHY layer in wireless networks

• Deals with
• Choice of modulation and coding scheme based on SNR measurements
• minimizing bit-error
• transmit power control
• usage of antennas

Networking Fundamentals

SELECTED TOPICS IN NETWORK DESIGN

Role of link layer in wireless networks

• Deals with
• Resource allocation
• Improving link utilization
• Interference management
• Link access techniques
• Frame format (control overhead and data)
• The above issues can be addressed using
• Innovative network architectures
• Scheduling algorithms
• Optimization / Machine learning / Game theory

Networking Fundamentals

SELECTED TOPICS IN NETWORK DESIGN

Role of network layer in wireless networks

• Deals with
• IP addressing in mobile environment
• Routing of packets in foreign (visited) network
• Route discovery and route reconfiguration in wireless ad hoc networks
• The above issues can be addressed using
• Mobile IP protocols
• Indirect routing
• Distance vector based routing protocols

Networking Fundamentals

SELECTED TOPICS IN NETWORK DESIGN

Role of transport layer in wireless networks

• Deals with
• Handoff and retransmissions caused by unreliable wireless medium
• Preserve end-to-end principle across wireless and wired medium
• The above issues can be addressed using
• Indirect TCP
• Snooping TCP
• Mobile TCP

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

Resource allocation in wireless networks

• Implemented either using guaranteed access techniques or random access techniques

What is guaranteed access?

• Information is collected from all end-users over a common control channel by a central controller
• Scheduling algorithm is implemented based on the available resources and end-users’ information
• Results of the scheduling algorithm are broadcast
• End-users access the wireless medium as per the results
• All the above steps are scheduled periodically (aka frame)
• Quality of service can be guaranteed

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

Examples of guaranteed access – TDMA

​

​

​

​

​

​

​

​

​

• Time is slotted and assigned to end-users

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

Examples of guaranteed access – TDMA (contd.)

• Information about slot assignment is broadcast periodically
• Size of the TDMA frame can be adjusted by the central controller to achieve QoS
• TDMA frame can be divided into uplink subframe and downlink subframe
• Synchronization in time domain is challenging
• Guard time needed to avoid multipath propagation

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

Examples of guaranteed access – FDMA

​

​

​

​

​

​

​

​

​

• Bandwidth is slotted and assigned to end-users

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

Examples of guaranteed access – FDMA (contd.)

• Information about slot assignment is broadcast periodically
• Frequency bands can be divided into uplink and downlink bands
• If separate uplink and downlink is assigned to a user per frame, it is referred to as full duplex
• Otherwise, it is referred to as half duplex
• Filtering in frequency domain is challenging
• Guard band needed to avoid inter-symbol interference

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

Examples of guaranteed access – CDMA

​

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

Other notable guaranteed access schemes:

• Polling; Token passing ring; Combining TDMA and FDMA (e.g., FHSS, OFDMA)

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

Random access schemes

• Link layer protocols (MAC protocols) are required for wireless channel access
• No control controller so end-users independently access the wireless channel
• Packet collisions occur due to simultaneous transmissions
• Link layer protocols address the hidden node and exposed node problems
• Hidden node problems reduce throughput due to packet collisions
• Exposed node problems reduce throughput due to loss of transmission opportunities

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

Carrier sense multiple access – CSMA

• Sender generates DATA and senses the wireless channel for transmission
• If channel is busy, sender performs backoff (i.e., defers sensing)
• If channel is idle, sender transmits DATA and waits for acknowledgement (ACK)
• If ACK is received, then sender had successful transmission
• If ACK is not received, then packet is assumed to be lost
• Packet loss occurs either due to simultaneous transmission (referred to as collision) or due to signal fade or receiver is busy

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

Hidden node problem

• Senders not in range of one another but have common receiver

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

Hidden node problem (contd.)

• A and C perform carrier sensing and detect an idle channel
• Both A and C transmit to B and this results in packet collision
• A and C are said to be hidden from each other
• CSMA can be altered to overcome hidden terminal problem by channel reservation via control messages

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

Exposed node problem

• F senses the channel and starts transmission to E after sensing it to be idle
• G wants to transmit to H but senses the channel busy due to F’s transmission
• G is said to be exposed to F’s transmission
• CSMA can be altered to overcome hidden terminal problem by channel reservation via control messages

Selected Topics in Network Design

Introduction – IEEE 802.11 Architecture, PHY and MAC

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11 – Architecture

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11 – Architecture (contd.)

• A basic service set (BSS) can be either operate in infrastructure mode or ad hoc mode
• A distribution system connects several BSSs via the AP to form a single network and thereby extends the wireless coverage area. This gives rise to extended BSS
• Stations can select an AP and associate with it
• The APs support roaming, the distribution system handles data transfer between the different APs.
• APs provide synchronization within a BSS, support power management, and can control medium access to support time-bounded service

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11 – Protocol architecture

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11 – PHY

• Channel allocation in IEEE 802.11
• 2.4 GHz to 2.485 GHz divided into 11 overlapping channels of 85MHz each.
• Channels 1, 6 and 11 are chosen for channel assignment
• Each WiFi access point is associated with one unique channel
• Either FHSS or DSSS or OFDMA is used on the channel

​

​

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11 – MAC

• First of all, it has to control medium access, but it can also offer support for roaming, authentication, and power conservation.
• The basic services provided by the MAC layer are the mandatory asynchronous data service and an optional time-bounded service.
• The asynchronous service supports broadcast and multi-cast packets, and packet exchange is based on a ‘best effort’ model, i.e., no delay bounds can be given for transmission

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11 – MAC (contd.)

• The asynchronous data service is called distributed coordination function (DCF) and the optional time bounded service is called point coordinated function (PCF)
• Only DCF is supported in ad hoc mode whereas both DCF and PCF are supported in infrastructure mode
• Together the DCF and the PCF are called distributed foundation wireless medium access control (DFWMAC).
• DCF is discussed under two schemes
• Basic access scheme (CSMA/CA)
• DCF with RTS/CTS

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11 – Basic access scheme (CSMA/CA)

​

​

​

​

​

​

​

• If channel is idle, wireless station waits for DIFS duration
• Transmit DATA packet
• If transmission was successful, the receiver sends an ACK after SIFS duration

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11 – Basic access scheme (contd.)

​

​

​

​

​

​

​

• If ACK is received then the transmission is considered successful by sending wireless station
• If collisions occur, then binary exponential backoff is initiated

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11 – Basic access scheme (contd.)

​

​

​

​

​

​

​

• Retransmission occurs after randomly chosen delay
• Probability of choosing a random delay decreases with collision

​

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11 – DCF with RTS/CTS

​

​

​

​

​

​

​

• If channel is idle then wait for DIFS interval
• Randomly choose a backoff value k and start decrementing it
• When k=0, transmit RTS and wait for CTS from receiver

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11 – DCF with RTS/CTS (contd.)

​

​

​

​

​

​

​

• If CTS is received after SIFS duration then transmit DATA
• Others defer their transmission based in NAV carried in RTS and CTS packet

​

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11 – DCF with RTS/CTS (contd.)

​

​

​

​

​

​

​

• If transmission was successful, receiver sends ACK after SIFS
• If ACK is received the sender has successfully transmitted

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

How hidden nodes resolved using DCF with RTS/CTS?

• Suppose A transmits RTS and B replies with CTS then C will receive the CTS of B and hence defers the transmission
• Suppose A and C transmit RTS simultaneously and so packet collision occurs.
• Binary exponential helps in reducing collision again

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

What should end-user experiencing packet collision do under DCF with RTS/CTS?

• They double their backoff window and choose a new backoff value. This is referred to as binary exponential backoff.

​

What should users not experiencing packet collision but waiting for transmission do?

• They simply freeze their backoff values till next DIFS idle time. Then, they resume decrementing their backoff value.

​

What does a sender do after successful transmission?

• A sender after successful transmission will reset its backoff window to initial size w and choose a new value of k.

Networking Fundamentals – Link Layer

SELECTED TOPICS IN NETWORK DESIGN

Example scenario of DCF with RTS/CTS

Selected Topics in Network Design

Introduction – IEEE 802.11

Frame structure, Network Admission & Roaming and Standards

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

IEEE 802.11 Frame Structure

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11: Frame structure

​

​

​

​

​

​

• Frame control: The first 2 bytes serve several purposes. It has several sub fields
• Protocol version: 2 bit field currently has value 00
• Type: The type field determines the function of a frame: management (=00), control (=01), or data (=10). The value 11 is reserved.

IEEE 802.11 Frame Structure

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11: Frame structure (contd.)

​

​

​

​

​

​

• Subtype:

IEEE 802.11 Frame Structure

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11: Frame structure (contd.)

​

​

​

​

​

​

• More fragments: Set to 1 if more segments are to follow
• Retry: Set to 1 if data is retransmitted
• Power Management: Set to 1 indicates if going to sleep mode; Set to 0 means active

​

IEEE 802.11 Frame Structure

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11: Frame structure (contd.)

​

​

​

​

​

​

• More data: To indicate a receiver that a sender has more data to send than the current frame. This can be used by an access point to indicate to a station in power-save mode that more packets are buffered.
• WEP: This field indicates that the standard security mechanism of 802.11 is applied

IEEE 802.11 Frame Structure

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11: Frame structure (contd.)

​

​

​

​

​

​

• Order: To indicate a receiver that frames are processed in strict order

IEEE 802.11 Frame Structure

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11: Frame structure (contd.)

​

​

​

​

​

​

• Duration: Indicates the time for which the medium will be busy due to data transmission
• Sequence control: Used to distinguish duplicate transmissions
• CRC: 32 bit code for error detection

IEEE 802.11 Frame Structure

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11: Frame structure (contd.)

​

​

​

​

​

​

• Address fields: Address 1 denotes receiver’s MAC address, Address 2 denotes sender’s MAC address, Address 3 and Address 4 are used for logical assignment of frames (logical sender, BSS identifier, logical receiver)

IEEE 802.11 Frame Structure

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11 Frame Structure

SELECTED TOPICS IN NETWORK DESIGN

IEEE 802.11: Frame structure – Control packets

​

IEEE 802.11 Network Admission and Roaming

SELECTED TOPICS IN NETWORK DESIGN

Network admission & roaming

• Connection setup between a wireless node and AP under IEEE 802.11 architecture
• Active scanning or passive scanning
• Authorization phase
• Association phase
• Data exchange phase

​

IEEE 802.11 Network Admission and Roaming

SELECTED TOPICS IN NETWORK DESIGN

Active and passive scanning

IEEE 802.11 Standards

SELECTED TOPICS IN NETWORK DESIGN

History and evolution

• First Wi-Fi standard called IEEE 802.11-1997
• IEEE 802.11b (1999) operated on 2.4 GHz, supported 11 Mbps, based on DSSS, cheaper router, susceptible to interference
• IEEE 802.11a (1999) operated on 5 GHz, supported 54 Mbps, introduced OFDM, not a commercial success
• IEEE 802.11g (2003) operated on 2.4 GHz, supported 54 Mbps, backward compatible with IEEE 802.11b
• IEEE 802.11n aka Wi-Fi 4 (2009) operated on both 2.4 GHz and 5 GHz, supports 300-450 Mbps, used MIMO

IEEE 802.11 Standards

SELECTED TOPICS IN NETWORK DESIGN

History and evolution (contd.)

• IEEE 802.11ac aka Wi-Fi 5 (2014) operated in 5 GHz, MU-MIMO, beamforming, 80 MHz bandwidth, supports 433 Mbps – 1 Gbps
• IEEE 802.11ax aka Wi-Fi 6 (2019) can operate in 2.4 GHz and 5 GHz, MU-MIMO 4×4 and 8×8, 9 Gbps, similar to 5G
• Useful links
• https://www.actiontec.com/wifihelp/evolution-wi-fi-standards-look-802-11abgnac/
• https://www.networkworld.com/article/3238664/80211-wi-fi-standards-and-speeds-explained.html
• https://ethw.org/IEEE_Standards_Association_History

Selected Topics in Network Design

Introduction – Network layer challenges and solutions – Part 1

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Challenges in WWAN due to mobility

• IP address is subnet dependent and usually assigned by DHCP
• Mobility can lead to a wireless device traversing multiple subnets
• Change of IP address causes service disruption
• Keeping initial IP address permanent during the mobility leads to routing issues
• Scalability is and important issue to be addressed

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Introduction

• A set of protocols to ensure IP addressing, routing and packet forwarding in WWAN
• Mobile IP simplifies the network layer challenges due to mobility
• No need to update all routers between the sender and mobile receiver
• No need to update the sender about the mobility of the receiver
• Components of Mobile IP
• Agent discovery for mobile users
• Registration of mobile user
• Indirect routing of datagrams

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Terminology

​

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Terminology (contd.)

• Mobile node (MN): An end-system or router that can change its point of attachment to the internet using mobile IP. The MN keeps its IP address and can continuously communicate from any location

​

• Correspondent node (CN): The partner node with which the MN communicates. The CN can be a fixed or mobile node.

​

​

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Terminology (contd.)

• Home network: It is the subnet the MN belongs to with respect to its IP address. No mobile IP support is needed within the home network.

​

• Foreign network: The foreign network is the current subnet the MN visits and which is not the home network.

​

• Home agent: A router on a mobile node’s home network which delivers datagrams to departed mobile nodes, and maintains current location information for each.

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Terminology (contd.)

• Foreign agent: A router on a mobile node’s visited network which cooperates with the home agent to complete the delivery of datagrams to the mobile node while it is away from home.

​

• Home address: An IP address that is assigned for an extended period of time to a mobile node. It remains unchanged regardless of where the node is attached to the Internet.

​

• Care-of-address: It is the address associated with the MN when it is away from its home network

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Operations

• Agent discovery
• Agent advertisement
• Agent solicitation
• Registration of care-of-address
• Routing of datagrams to mobile node

​

• Impact of the above operations:
• The above operations do not require update of routing tables across the internet
• The home agent is the most crucial part of the setting up and running the mobile IP protocols
• The CN is oblivious of the change of location of the MN

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Agent discovery – Agent advertisement

• Foreign agents and home agents advertise their presence periodically using special agent advertisement messages

​

ICMP message according to RFC 1256 + extended mobility

​

Shaded part is the advertisement

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Agent discovery – Agent advertisement

​

IP header values

TTL is set to 1

​

Destination IP address is either 224.0.0.1 (multicast) or 255.255.255.255 (broadcast)

​

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Agent discovery – Agent advertisement

​

ICMP part

Type = 9 / 16; Code = 0

​

#address gives no. of advertised addresses

​

Addresses are shown below

​

Lifetime tells valid time

​

Preference gives readiness of agent

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Agent discovery – Agent advertisement

​

Extended mobility part

Type = 16; length = 6 + 4 × (No. of COA)

​

sequence number gives the total number of advt. sent so far

​

registration lifetime gives max. time of a requested COA

​

COA: offered address

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Agent discovery – Agent advertisement

​

Extended mobility part

R: Agent reg. required even when using colocated COA

​

B: Agent busy to accept reg. requests

​

H: Home agent

​

F: Foreign agent

​

​

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Agent discovery – Agent advertisement

​

Extended mobility part

M and G: Minimal encapsulation or generic routing encapsulation

​

r: set to zero

​

T: Indicates reverse tunnelling by FA

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Agent discovery – Agent solicitation

• Agent solicitation message is sent by MN if it has not received an agent advt. or inter-arrival time is too high
• Typically, an MN can send out three solicitations, one per second, as soon as it enters a new network
• If an MN does not receive an answer to its solicitations it must decrease the rate of solicitations exponentially
• Once an MN receives the agent advt., it enters the registration phase.

​

Selected Topics in Network Design

Introduction – Network layer challenges and solutions – Part 2

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: COA registration process

• After performing the agent discovery, the MN receives the COA in the foreign network
• The next step is to inform the HA about the COA
• This will enable routing of packets to the MN using the COA
• Next we see the registration process

​

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: COA registration process (contd.)

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Registration request message

​

​

​

​

​

​

​

• The message is carried as UDP segment with port number 434
• The IP header source address is that of the MN, destination address is that of FA or HA

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Registration request message (contd.)

​

​

​

​

​

​

​

• Type is set to 1 for registration request
• S is used to indicate whether HA prior mobility bindings must be retained or not
• This allows simultaneous bindings

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Registration request message (contd.)

​

​

​

​

​

​

​

• S bit is used t indicate whether MN wants broadcasts in the home network
• Using D bit, MN can indicate whether it wants to manage encapsulation itself

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Registration reply message

​

​

​

​

​

​

• Lifetime indicates the validity of the registration in seconds
• The home address is the fixed IP address of the MN
• home agent is the IP address of the HA
• COA represents the tunnel endpoint.

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Registration reply message (contd.)

​

​

​

​

​

​

• 64 bit identification is generated by the MN to identify a request and match it with registration replies
• Extensions contain parameters for authentication
• Type = 3 and code indicate the result of the registration

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Registration reply message (contd.)

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Routing of datagrams

• Following the successful registration of the COA with the HA, the MN can start receiving datagrams
• The datagrams are encapsulated before delivery to the MN by the HA
• The FA / MN decapsulate the packet in the foreign network
• The MN simply replies back to the CN using the source address in the received packet and using its home address for the destination
• See triangle or indirect routing next

Network Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Mobile IP: Routing of datagrams

Selected Topics in Network Design

Introduction – Transport layer challenges and solutions

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Recap of TCP in fixed networks

• Timeout indicates congestion in the network
• Packets can get corrupted during switching operation
• TCP reacts to timeout by retransmitting the old packet
• Transmission rate is deflated upon experiencing timeout
• Throughput suffers due to congestion
• Transmission rate increases with successful acknowledgements
• Congestion control algorithm uses slow start, congestion avoidance and fast retransmit (optional) to improve the throughput

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Implications of mobility on TCP

• Slow start is not suited for wireless and mobile environments mobility
• Wireless medium can cause packets to become corrupted
• Timeouts can occur due to signal fading
• Link layer also reacts to frequent disruptions
• Timeouts can occur during handoff between foreign agents
• Foreign agents may not buffer packets and exchange them during handoff
• All the above issues can lead to TCP retransmissions

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Solutions – Indirect TCP

​

​

​

​

​

​

​

• Two separate TCP connections: one on wired and the other on wireless
• Access point acts as proxy for the mobile host

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Solutions – Indirect TCP (contd.)

​

​

​

​

​

​

​

• Other possibility for partitioning TCP is the foreign agent of the mobile IP which controls mobility
• Access point buffers and detects packet loss on wired and wireless separately

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Solutions – Indirect TCP (contd.)

​

​

​

​

​

​

​

• Access point acknowledges successful transmissions and retransmits lost packets separately on wired and wireless
• Access point isolates packet loss on wireless from wired

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Solutions – Indirect TCP Handoff

​

​

​

​

​

​

​

• When mobile host performs handoff, the old access point transfers all buffered data and TCP parameters with respect to both wired and wireless to the new access point
• Fixed host does not know about the mobility

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Solutions – Indirect TCP Advantages

• No changes in TCP algorithms
• Transmission errors on wireless not propagated into wired
• Testing of new TCP solutions easy
• Different protocols or different optimization can be applied on wired and wireless (e.g., data compression)
• Round trip in wireless is assumed very small

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Solutions – Indirect TCP Disadvantages

• Violates TCP end-to-end principle
• Latency during handoff (higher transmission delay)
• Foreign agent must be trusted entity. If transport layer security is applied then I-TCP will not work

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Solutions – Snooping TCP

​

​

​

​

​

​

• Best place to enhance TCP is at the foreign agent of mobile IP
• The foreign agent buffers all packets with destination mobile host

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Solutions – Snooping TCP (contd.)

​

​

​

​

​

​

• Additionally snoops the ongoing TCP transmissions in both directions
• Foreign agent can perform fast retransmission to mobile host when packet loss / duplicate ACKs are detected on the wireless

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Solutions – Snooping TCP (contd.)

​

​

​

​

​

​

• Foreign agent does not acknowledge the correspondent host
• Foreign agent can avoid unnecessary retransmissions by mobile host by removing duplicate ACKs from wired side

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Solutions – Snooping TCP (contd.)

​

​

​

​

​

​

• If packet loss is detected in the transmissions to correspondent host then NACK is sent by foreign agent to the mobile host
• Reordering of packets is done by mobile host automatically

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Solutions – Snooping TCP Advantages

• End-to-end semantics are preserved
• The correspondent host does not need to be changed; most of the enhancements are in the foreign agent
• The correspondent host does not need to be changed; most of the enhancements are in the foreign agent

​

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Solutions – Snooping TCP Disadvantages

• Errors from wireless propagate into wired part
• NACK usage requires additional requirements for mobile host
• All efforts at snooping and buffering are useless if TCP header encryption is used.

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Solutions – Mobile TCP

​

​

​

​

• For handling of lengthy and/or frequent disconnections
• I-TCP + S-TCP + adapt to lengthy/frequent disconnections
• Unmodified TCP between SH and CH and adaptive (optimized) TCP between MH and SH
• SH monitors the transmissions but does not buffer data

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Solutions – Mobile TCP (contd.)

​

​

​

​

• SH monitors all packets sent to the MH and all ACKs sent by the MH
• If ACKs are not detected then SH assumes disconnection of MH
• Sender is choked upon detecting disconnection of MH
• Sender window goes to zero

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Solutions – Mobile TCP (contd.)

​

​

​

​

• Upon detecting reconnection with MH, the sender window is restored to old value
• So no slow start due to disconnection
• Other issues of TCP remain unaffected
• Retransmissions are carried out by original sender

Transport Layer Challenges and Solutions

SELECTED TOPICS IN NETWORK DESIGN

Solutions – Mobile TCP Advantages

• Maintains end-to-end semantics of TCP
• If the MH is disconnected, it avoids useless retransmissions, slow starts or breaking connections
• No buffering of data and transfer during handoff

​

Solutions – Mobile TCP Disadvantages

• Assumes low bit error rate on wireless link
• SH does not act as proxy for MH so errors from wireless propagates into wired
• Upgrade of MH software to be adaptive

Selected Topics in Network Design

Introduction – Wireless Network Architectures and Standards

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Wireless Network Architectures and Standards

SELECTED TOPICS IN NETWORK DESIGN

Wireless networks

• Composed of wireless devices (terminals, access points, switches, routers, etc.) connected by wireless links
• Can consist of fixed wired terminals
• Wireless networks can be classified based on the topology, span, architecture, link access method and application
• Network design issues depend on the above classification
• Some common objectives of network design are:
• maximizing throughput, minimizing access delay, maximizing energy efficiency, maximizing spectral efficiency, etc.

Wireless Network Architectures and Standards

SELECTED TOPICS IN NETWORK DESIGN

Wireless networks – Examples

• WiFi
• Bluetooth and Zigbee
• WiMAX
• Cellular network (3G, 4G, 5G)
• Satellite communication network
• Vehicular network
• Heterogeneous network

Wireless Network Architectures and Standards

SELECTED TOPICS IN NETWORK DESIGN

Wireless networks - Topologies

• Network topology refers to the physical configuration of links between the wireless devices (e.g., terminals, switches, routers)
• Examples: Star, bus, mesh, ring, tree, ad hoc, etc.

Star topology is seen in WiMAX, Bluetooth, Zigbee, WiFi, etc.

Wireless Network Architectures and Standards

SELECTED TOPICS IN NETWORK DESIGN

Wireless networks – Topologies (contd.)

Mesh networks, also known as mobile ad hoc networks (MANETs), are local or metropolitan area networks in which nodes are mobile and communicate directly with adjacent nodes without the need for central controlling devices

Wireless Network Architectures and Standards

SELECTED TOPICS IN NETWORK DESIGN

Wireless networks – Topologies (contd.)

Wireless Network Architectures and Standards

SELECTED TOPICS IN NETWORK DESIGN

Wireless networks – Topologies (contd.)

Wireless Network Architectures and Standards

SELECTED TOPICS IN NETWORK DESIGN

Wireless networks – Span

• Based on the range and application of the wireless network, we have
• WBAN
• WPAN
• WLAN
• WWAN
• WMAN
• Coverage area or range is also called cell
• Alternative names given based on cell size
• Femtocell
• Picocell
• Microcell
• Macrocell

Wireless Network Architectures and Standards

SELECTED TOPICS IN NETWORK DESIGN

Wireless networks – Architecture

• It defines the order or the hierarchy in the wireless devices/terminals
• Wireless link access depends on the network architecture
• Objective of network design determine the network architecture
• Network architecture can be classified as centralized, distributed and hybrid
• Centralized networks have fixed infrastructure and central controller
• Distributed networks do not have fixed infrastructure or central controller

​

Wireless Network Architectures and Standards

SELECTED TOPICS IN NETWORK DESIGN

Wireless networks – Centralized architecture

• Examples: Cellular networks, WiMAX, Bluetooth (master-slave) etc.
• Consists of a base station/central controller who schedules/allocates resources to the wireless hosts
• Base station implements a scheduling algorithm
• Typically follow multiple access schemes
• Multichannel resource allocation is followed
• Contiguous or discontiguous chunks of bandwidth
• QoS support guaranteed: Throughput; fairness; load balancing; delay guarantees

Wireless Network Architectures and Standards

SELECTED TOPICS IN NETWORK DESIGN

Wireless networks – Distributed architecture

• Examples: Wireless LANs, Wireless sensor networks, ad hoc networks, Bluetooth (peer-peer), etc.
• Require MAC protocols for coordination
• Wireless hosts compete for resources using random access techniques
• Multichannel access is difficult to implement
• QoS support not guaranteed
• Scalability and fairness are not an issue
• Fewer control overhead compared to centralized architecture

Wireless Network Architectures and Standards

SELECTED TOPICS IN NETWORK DESIGN

Wireless networks – Hybrid architecture

• Examples: 5G networks, Cooperative networks, MANETs, VANETs, etc.
• Combination of centralized and distributed network architectures
• Requires a combination of protocols and algorithms
• Coexistence of different networks should be guaranteed
• No unique architecture exists
• QoS support: Latency; fairness; throughput; scalability

Wireless Network Architectures and Standards

SELECTED TOPICS IN NETWORK DESIGN

Wireless networks – Comparison

​

Wireless Network Architectures and Standards

SELECTED TOPICS IN NETWORK DESIGN

Wireless networks – Standards

• Wireless standards are defined by IEEE, IETF, ETSI, IEC, etc.
• Standards usually specify the PHY and MAC
• In some cases, they may specify the upper layers
• Some IEEE Standards are given below:
• IEEE 802.11
• IEEE 802.15
• IEEE 802.16
• IEEE 802.3
• IEEE 1900

Wireless Network Architectures and Standards

SELECTED TOPICS IN NETWORK DESIGN

Wireless networks – Standards

• Some 3GPP/ETSI standards include
• GSM
• cdma2000
• UMTS
• E-UTRA
• DECT
• Some IEC standards
• IEC 61850
• IEC 62645

Selected Topics in Network Design

Wireless Network Design Requirements – Part I

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Wireless Network Design – Part I

SELECTED TOPICS IN NETWORK DESIGN

Network design – Basics

• Network design deals with identifying a suitable network architecture to satisfy a given design objective
• Network design also involves defining the characteristics of the network when it becomes operational
• Typical operational characteristics
• Link access
• Frame structure
• Overheads
• Power consumption
• Achievable data rates
• Network design is motivated by the application and the number of end-users to be supported

Wireless Network Design – Part I

SELECTED TOPICS IN NETWORK DESIGN

Network design – Basics (contd.)

• Typically, network can be viewed as a set of nodes partially or fully connected by links
• Networks composed of terminal nodes and resource nodes
• Terminal nodes run application which generates packets
• Resource nodes provide connectivity and other services
• Network design issues in centralized or distributed cases are very different

Wireless Network Design – Part I

SELECTED TOPICS IN NETWORK DESIGN

Wireless network design requirements

• Define the roles of the nodes
• Define the interaction between the nodes
• Define the data required for the network design
• Define the notations/symbols to be used
• Define the objective of the network design
• Define mathematical model for the network design
• Define an algorithm for optimizing the objective
• Define criteria for analyzing the network design

Wireless Network Design – Part I

SELECTED TOPICS IN NETWORK DESIGN

Defining the roles of the nodes

• Terminal nodes and resource nodes have different roles in different network architectures
• In centralized network architecture, resource nodes are hubs, base stations or access points
• In distributed networks, the resource nodes could be the same as the terminal nodes
• Resource nodes generally collect information from terminal nodes or other resource nodes
• Resource nodes act as relays and/or schedulers
• Terminal nodes send and receive data

Wireless Network Design – Part I

SELECTED TOPICS IN NETWORK DESIGN

Defining the roles of the nodes (contd.)

• Roles should be defined in the hierarchy

Selected Topics in Network Design

Wireless Network Design Requirements – Part II

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Wireless Network Design – Part II

SELECTED TOPICS IN NETWORK DESIGN

Defining the interaction between the nodes

• Nodes interact based on the network architecture using frames
• A frame is a timeline for exchange of control information and data between pairs (or groups) of nodes
• Frame facilitates coordination between the nodes
• In centralized network architecture, the frame is defined and periodically scheduled by the central controller
• Here, frame is meant for coordination of all nodes
• Scheduling algorithm determines the status and the meaning of the information within a frame
• Central controller specifies the duration and schedule for data transmissions

Wireless Network Design – Part II

SELECTED TOPICS IN NETWORK DESIGN

Defining the interaction between the nodes (contd.)

• In the distributed architecture, frames are meant for coordination between sender and receiver
• Here, frame is scheduled randomly and may suffer from interference (i.e., collision)
• Frame comprises of synchronization bits, sender and receiver identity, header for the data and the data
• Different types of frames are deployed for different purposes
• Examples: RIP messages in ad hoc networks, IEEE 802.11 frame under DCF with RTS/CTS

Wireless Network Design – Part II

SELECTED TOPICS IN NETWORK DESIGN

Defining the interaction between the nodes (contd.)

• In multihop communication, relay nodes play an important role

Wireless Network Design – Part II

SELECTED TOPICS IN NETWORK DESIGN

Case study of node interaction: Centralized (WiMAX)

• First, the network architecture is described and then the interaction is described

​

Wireless Network Design – Part II

SELECTED TOPICS IN NETWORK DESIGN

Case study of node interaction: Centralized (WiMAX)

• An 802.16 wireless service provides a communications path between a subscriber site and the core network

Wireless Network Design – Part II

SELECTED TOPICS IN NETWORK DESIGN

Case study of node interaction: Centralized (WiMAX)

• Referred to as IEEE 802.16
• For more information http://www.wimaxforum.org/
• WiMAX operates in both licensed (2.5 GHz and 3.5 GHz) and unlicensed bands (2.4 GHz and 5 GHz).
• IEEE 802.16e PHY is based on OFDMA with TDD or FDD
• Both uplink and downlink transmissions are scheduled by the WiMAX base station
• Uplink means transmissions from mobile users to base station
• Downlink means transmissions from base station to mobile users

Wireless Network Design – Part II

SELECTED TOPICS IN NETWORK DESIGN

Case study of node interaction: Centralized (WiMAX)

​

​

​

​

Wireless Network Design – Part II

SELECTED TOPICS IN NETWORK DESIGN

Case study of node interaction: Centralized (WiMAX)

​

​

​

​

Wireless Network Design – Part II

SELECTED TOPICS IN NETWORK DESIGN

Case study of node interaction: Centralized (WiMAX)

• The frame size and allocations are determined by the scheduler
• The scheduler is located at the base station
• The channel conditions are obtained from every terminal over the CQICH
• For DL, using the QoS of each service flow and the channel conditions, the correct modulation and coding are selected
• For UL, the bandwidth requests and QoS requirement of each service flow are collected on the UL ranging
• The best subcarriers per service flow are mapped and broadcast in the UL MAP and DL MAP

Wireless Network Design – Part II

SELECTED TOPICS IN NETWORK DESIGN

Case study of node interaction: Centralized (WiMAX)

• Other operations managed by the base station
• Handoff
• Power management
• Security

Selected Topics in Network Design

Wireless Network Design Requirements – Part III

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Network design requires data (information) about terminal nodes, resource nodes and wireless links
• The data can be local or global
• The data can be constants or random variables
• If the data is comprised of random variables, then it must be generated
• Time of occurrence of data and the process of data sharing must be specified

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Simulation of large scale fading

​

​

• First two terms on the RHS are constants
• For third term, generate Gaussian random variables

, here is between 8-13 dB

• The channel gain can be expressed as

y[n] = g[n] s[n] + x[n]

where x[n] is AWGN, s[n] is transmitted signal and g[n] is path loss

• Note, for discrete samples we can replace t by n

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Simulation of large scale fading with temporal correlation
• Suppose the correlation decays over m samples by a factor β

​

​

​

• Here, v[n] and d[n] are velocity and distance in the n-th slot, and 0 < ε_D < 1
• Thus, the n-th sample of the received signal can be expressed as y[n] = a y[n-1] + x[n]

where x[n] is AWGN and

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Simulation of small scale fading
• Impulse response of the channel is expressed as

h[n] = a_n e^j𝜃n𝛿[n]

• The phase θ_n follows uniform distribution [0,2π]
• In MATLAB, use function rand and adjust for variance
• In Python, use numpy.random.rand and adjust for variance
• For amplitude a_n we can generate according to the presence or absence of the LOS

​

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Simulation of small scale fading (contd.)
• For the case with no LOS, a_n follows Rayleigh distribution

​

​

​

​

​

• Draw two Gaussian random variables u and v with mean zero and variance 𝜎²
• Then, the random variable a_n is given by (u² + v²)^0.5

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Simulation of small scale fading (contd.)
• For the case with strong LOS, a_n follows Rice distribution

​

​

​

​

• The mean and variance are given by

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Simulation of small scale fading (contd.)
• Draw two independent Gaussian RVs u ~ N(μcosθ, σ²) and v ~ N(μsinθ, σ²)
• The Rice distributed random variable a_n is given by

(u² + v²)^0.5

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Simulation of packet events
• Packet arrivals generally are assumed to follow Poisson process or Bernoulli process
• Poisson process can be generated as follows:
1. Generate exponential random number (e.g., y=numpy.random.exponential (1/a))
2. If no. of arrivals = 0 then store x[0] = y
3. If no. of arrivals is >0 then store x[n] = x[n-1] + y
4. Go to step 1

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Simulation of packet events
• For any general distribution, we use the Monte Carlo method to generate the random process
• Let x₁,...,x_m denote the random variables occurring with probabilities p₁,...,p_m respectively
1. Generate uniform random number U

(e.g., U=numpy.random.uniform() in Python)

• Set X = x_j if

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the decisions for network design

• Decisions refer to the unknowns which have to be found to satisfy the design objective(s)
• Examples: Assignment of spectrum blocks to end-users; Transmit power assigned to downlink channel; Flow rate across a link
• Decisions and data are combined to express the constraints in the mathematical model
• Examples of constraints: SINR calculated through transmit power should be above minimum SINR target

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the decisions for network design (contd.)

• Decisions can also be local or global
• The order of occurrence of the data and decisions must be specified
• The time scale over which the decisions are taken must be specified
• Example:
• Consider a static multihop wireless network in which the wireless terminals want to exchange data with one another. What will be the data, decisions and order of occurrence? Which data is local or global? Which decision is local or global?

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the notations/symbols

• Data is specified in uppercase
• Decisions are specified in lowercase
• Single letter or symbol is preferred for notation
• Indexes are given in subscripts while labels (e.g., min) are given in superscript
• Vectors and matrices are expressed in boldface
• Examples of notations:
• Flow rate across a link (i,j) can be denoted as f_ij
• Minimum bit rate required by receiver j can be denoted as R_j^min

​

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the notations/symbols (contd.)

• Sets for the indexes can be specified in uppercase stylized fonts

​

• Size of such a set can be denoted as

​

• Functions are also given subscripts or superscripts according to their dependent parameters

​

​

• Examples of notations to be avoided

​

Selected Topics in Network Design

Wireless Network Design Requirements – Part III

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Network design requires data (information) about terminal nodes, resource nodes and wireless links
• The data can be local or global
• The data can be constants or random variables
• If the data is comprised of random variables, then it must be generated
• Time of occurrence of data and the process of data sharing must be specified

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Simulation of large scale fading

​

​

• First two terms on the RHS are constants
• For third term, generate Gaussian random variables

, here is between 8-13 dB

• The n-th sample of the received signal can be expressed as

y[n] = g[n] s[n] + x[n]

where x[n] is AWGN, s[n] is transmitted signal and g[n] is path loss

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Simulation of large scale fading with temporal correlation
• Suppose the correlation decays over m samples by a factor β

​

​

​

• Here, v[n] and d[n] are velocity and distance in the n-th slot, and 0 < ε_D < 1
• Thus, the n-th sample of the received signal can be expressed as y[n] = a y[n-1] + x[n]

where x[n] is AWGN and

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Simulation of small scale fading
• Impulse response of the channel is expressed as

h[n] = a_n e^j𝜃n𝛿[n]

• The phase θ_n follows uniform distribution [0,2π]
• In MATLAB, use function rand and adjust for variance
• In Python, use numpy.random.rand and adjust for variance
• For amplitude a_n we can generate according to the presence or absence of the LOS

​

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Simulation of small scale fading (contd.)
• For the case with no LOS, a_n follows Rayleigh distribution

​

​

​

​

​

• Draw two Gaussian random variables u and v with mean zero and variance 𝜎²
• Then, the random variable a_n is given by (u² + v²)^0.5

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Simulation of small scale fading (contd.)
• For the case with strong LOS, a_n follows Rice distribution

​

​

​

​

• The mean and variance are given by

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Simulation of small scale fading (contd.)
• Draw two independent Gaussian RVs u ~ N(μcosθ, σ²) and v ~ N(μsinθ, σ²)
• The Rice distributed random variable a_n is given by

(u² + v²)^0.5

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Simulation of packet events
• Packet arrivals generally are assumed to follow Poisson process or Bernoulli process
• Poisson process can be generated as follows:
1. Generate exponential random number (e.g., y=numpy.random.exponential (1/a))
2. If no. of arrivals = 0 then store x[0] = y
3. If no. of arrivals is >0 then store x[n] = x[n-1] + y
4. Go to step 1

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the data for network design

• Simulation of packet events
• For any general distribution, we use the Monte Carlo method to generate the random process
• Let x₁,...,x_m denote the random variables occurring with probabilities p₁,...,p_m respectively
1. Generate uniform random number U

(e.g., U=numpy.random.uniform() in Python)

• Set X = x_j if

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the decisions for network design

• Decisions refer to the unknowns which have to be found to satisfy the design objective(s)
• Examples: Assignment of spectrum blocks to end-users; Transmit power assigned to downlink channel; Flow rate across a link
• Decisions and data are combined to express the constraints in the mathematical model
• Examples of constraints: SINR calculated through transmit power should be above minimum SINR target

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the decisions for network design (contd.)

• Decisions can also be local or global
• The order of occurrence of the data and decisions must be specified
• The time scale over which the decisions are taken must be specified

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the notations/symbols

• Data is specified in uppercase
• Decisions are specified in lowercase
• Single letter or symbol is preferred for notation
• Indexes are given in subscripts while labels (e.g., min) are given in superscript
• Vectors and matrices are expressed in boldface
• Examples of notations:
• Flow rate across a link (i,j) can be denoted as f_ij
• Minimum bit rate required by receiver j can be denoted as R_j^min

​

Wireless Network Design – Part III

SELECTED TOPICS IN NETWORK DESIGN

Defining the notations/symbols (contd.)

• Sets for the indexes can be specified in uppercase stylized fonts

​

• Size of such a set can be denoted as

​

• Functions are also given subscripts or superscripts according to their dependent parameters

​

​

• Examples of notations to be avoided

​

Selected Topics in Network Design

Wireless Network Design Requirements – Part IV

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Wireless Network Design – Part IV

SELECTED TOPICS IN NETWORK DESIGN

Defining the objective of the network design

• The goal of network is to achieve the desired objective in terms of the decisions
• Objectives can be defined from standpoint of end-users or network operator or application
• Objectives also depend on the network architecture
• Examples of objectives
• Maximize sum data rate of all links
• Maximize energy efficiency
• Minimize the system delay
• Minimize operating costs
• Minimize capital costs and expected operating costs
• Maximize revenue of network operator

Wireless Network Design – Part IV

SELECTED TOPICS IN NETWORK DESIGN

Defining the objective of the network design

• Mathematically, the objective is referred to as objective function
• The objective function returns a scalar value with respect to the decisions
• The best value of the decisions is called optimal solution and the best value of the objective function is called optimal value

Wireless Network Design – Part IV

SELECTED TOPICS IN NETWORK DESIGN

Defining the objective of the network design

• Example of objective function
• Let (i,j) denote a pair of nodes (i.e., link) in the network
• Let the links share the spectrum blocks of bandwidth B_j
• Let the transmit power on link (i,j) be denoted as p_i
• The power received by node j is p_iG_ij where G_ij is channel gain of link (i,j)
• State the objective function as maximizing sum data rate across all links

Wireless Network Design – Part IV

SELECTED TOPICS IN NETWORK DESIGN

Defining the mathematical model for network design

• We define the a set of rules/equations that relate the data and the decisions which are referred to as constraints
• Combining the objective function and the constraints makes the network design problem mathematical
• The best decisions are found by solving the mathematical model using iterative algorithms
• These algorithms can be either based on the optimization techniques or heuristic algorithms

​

Wireless Network Design – Part IV

SELECTED TOPICS IN NETWORK DESIGN

Defining the mathematical model for network design

• Case study – Orthogonal link access in centralized network architecture:
• Let m denote the index of the base station
• Let i ∈ {1,..,N} denote the terminal nodes which await transmissions from the base station
• Consider downlink scheduling by the base station using the frequency channels k ∈ {1,..,K}

Wireless Network Design – Part IV

SELECTED TOPICS IN NETWORK DESIGN

Defining the mathematical model for network design

• Case study – Orthogonal link access in centralized network architecture:
• Let G_mik denote the path loss (channel gain) estimated by the terminal node i on the channel k
• Let B_k denote the bandwidth of each channel k
• Let N₀ denote the noise power density
• Let I denote the inter-cell interference
• Let P^max denote the maximum transmit power of the base station

Wireless Network Design – Part IV

SELECTED TOPICS IN NETWORK DESIGN

Defining the mathematical model for network design

• Case study – Orthogonal link access in centralized network architecture:
• Let p_mik denote the transmit power from base station to node i on the channel k
• Let a_ik denote the assignment of downlink transmission on channel k to node i
• Consider the objective is to maximize the sum data rate of all assigned wireless links

Wireless Network Design – Part IV

SELECTED TOPICS IN NETWORK DESIGN

Defining the mathematical model for network design

• Case study – Orthogonal link access in centralized network architecture:
• Constraint 1: Each terminal node i must be assigned a unique channel

​

• Constraint 2: Minimum rata rate requirement must be met for each terminal node

Wireless Network Design – Part IV

SELECTED TOPICS IN NETWORK DESIGN

Defining the mathematical model for network design

• Case study – Orthogonal link access in centralized network architecture:
• Constraint 3: Base station should not transmit beyond the maximum available power

​

• Constraint 4: Transmission allowed only on assigned links

​

• Constraint 5: Integrality condition

Selected Topics in Network Design

Wireless Network Design Requirements – Part V

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Wireless Network Design – Part V

SELECTED TOPICS IN NETWORK DESIGN

Modeling – Shared resource allocation

• Consider a heterogeneous cell where same bandwidth-time slots (i.e., channels) are shared across multiple cells
• Within each cell (femto or macro), the channels are orthogonally assigned
• Consider scheduling of downlink transmissions in all cells
• Consider M femtocells, so m ∈ {1,...,M} where m is index of femto base station (BS)
• Each femto BS talks to one femto user m’ ∈ U_m
• Let n and n’ ∈ {1,...,N}\n denote the macro BS and the macro users respectively
• Let k ∈ {1,...,K} denote the channel index

Wireless Network Design – Part V

SELECTED TOPICS IN NETWORK DESIGN

Modeling – Shared resource allocation (Soln.)

• Let I_n’, and I_m’ denote the interference thresholds of the receivers n’ and m’
• Let G_mm’k and G_nn’k denote the channel gain measured by receiver m’ and n’ with respect to m (femto BS) and n (macro BS)

​

Wireless Network Design – Part V

SELECTED TOPICS IN NETWORK DESIGN

Modeling – Shared resource allocation (Soln.)

• Let G_nm’k and G_mn’k denote the channel gain measured by receiver m’ and n’ due to interference from n and m respectively
• Interference between femto cells is negligible as they are non-overlapping

Wireless Network Design – Part V

SELECTED TOPICS IN NETWORK DESIGN

Modeling – Shared resource allocation (Soln.)

• Let P_m and P_n denote the maximum transmit powers of femto BS m and macro BS n
• Let p_mm’k and p_nn’k denote the transmit powers from femto BS and macro BS to respective receivers m’ and n’ on channel k
• Let a_n’k denote the binary variable to orthogonally assign channel k ∈ {1,...,K} to respective macro cell users

​

Wireless Network Design – Part V

SELECTED TOPICS IN NETWORK DESIGN

Modeling – Shared resource allocation (Soln.)

• Implement of shared resource allocation depends on network architecture
• Centralized architecture: A central controller collects information from both types of cells (via the BSs) and broadcast the decisions
• Distributed architecture:
• Femto BSs determine decisions locally and broadcast their results to macro BS
• Macro BS determines its decisions and broadcasts its results to all femto BSs
• The above steps repeat as data rates are maximized while the interference conditions are not violated

Wireless Network Design – Part V

SELECTED TOPICS IN NETWORK DESIGN

Modeling – Shared resource allocation (Soln.)

• Centralized architecture:

​

​

​

​

• TDM/OFDM slots for control and data messages
• Distributed architecture:

​

​

​

​

• Femto BS and macro BS can transmit control messages in iterative manner or pseudorandom manner

Wireless Network Design – Part V

SELECTED TOPICS IN NETWORK DESIGN

Modeling – Shared resource allocation (Soln.)

• The objective is to maximize the sum data rate of all transmissions in the heterogeneous cell

​

Here, p_nm’k is same for all femto users . It is given by

Wireless Network Design – Part V

SELECTED TOPICS IN NETWORK DESIGN

Modeling – Shared resource allocation (Soln.)

• Constraint 1: Interference experienced by femto user m’ must not exceed the corresponding interference threshold

​

​

• Constraint 2: Interference experienced by macro user n’ must not exceed the corresponding interference threshold

​

​

• Constraint 3: Orthogonal assignment of channels for macro cell users

​

Wireless Network Design – Part V

SELECTED TOPICS IN NETWORK DESIGN

Modeling – Shared resource allocation (Soln.)

• Constraint 4: Total transmit power constraint for femto BS

​

​

​

• Constraint 5: Total transmit power constraint for macro BS

​

​

​

• Constraint 6: Transmit power assignment per channel for macro BS and femto BS

​

Wireless Network Design – Part V

SELECTED TOPICS IN NETWORK DESIGN

Defining criteria for analyzing network design

• Network designs can be analyzed using experiments
• Each experimental run involves fresh dataset
• Analysis allows the decision maker to modify the design
• Analysis allows the decision maker to understand limitations of the network design
• Analysis reveals scalability, computation complexity and accuracy of the decisions
• Markov chains have been extensively applied to analyze network designs
• Optimization techniques have also been expensively applied to analyze network designs

Wireless Network Design – Part V

SELECTED TOPICS IN NETWORK DESIGN

Analysis –Shared resource allocation

• Best objective (sum data rates) can be analyzed by varying
• No. of channels K
• No. of femto cells M
• Interference threshold I_n’ or I_m’
• Variance of the channel gains
• No. of active macro cell users N
• Stability of the design (e.g., outage events, congestion)
• Analyze the convergence time and tradeoffs
• Analyze impact of overheads and link rates

Selected Topics in Network Design

Markov Chains – Basics and Applications

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Markov chains – Basics and applications

SELECTED TOPICS IN NETWORK DESIGN

Introduction

• When the best decisions are taken by scheduling problems (i.e., link access problems) the resources are best utilized
• It is important to know whether, the available resources are sufficient
• Packet arrivals, bandwidth requests, link rates, nodal processing delays, handoffs, etc. are random in nature
• Hence, stability of the system and resource utilization are of prime importance in network design
• In other words, we must determine the performance of the system under random events

Markov chains – Basics and applications

SELECTED TOPICS IN NETWORK DESIGN

Introduction (contd.)

• Markov chains represent the evolution of the available resources in the network due to the decisions
• Examples:
• Evolution of busy bandwidth-time slots (i.e., channels) due to random requests
• Evolution of nodal processing rate due to random packet arrivals
• More specifically, the Markov chains represent evolution of random processes which have the following properties
• Orderliness
• Independence
• Stationarity

Markov chains – Basics and applications

SELECTED TOPICS IN NETWORK DESIGN

Introduction (contd.)

• Examples of random process modelled as Markov chains include Poisson process, Bernoulli process, etc.
• Markov chains are said to follow Markov property (aka memoryless property)
• Packet arrivals or bandwidth/service requests in wireless networks generally follow memoryless property
• Markov chains (MC) are used to study performance of scheduling policy/mathematical model/protocols
• The following analysis can be performed using MC
• Throughput analysis
• Delay analysis
• Outage analysis

Markov chains – Basics and applications

SELECTED TOPICS IN NETWORK DESIGN

Introduction (contd.)

• Other applications of Markov chains
• Telecommunication network design
• Systems scheduling and control
• Highway design
• City planning
• Hospital management
• Airport design
• Reliability engineering

Markov chains – Basics and applications

SELECTED TOPICS IN NETWORK DESIGN

Markov chains – Math representation

• Markov chains are represented as follows
• Set of finite states (S)
• Transition rates (Q) / Transition probabilities (P)
• Stationary probability distribution of the states (π)
• Types of Markov chains
• Discrete time Markov chain (DTMC) – Meant for describing discrete time random process
• Examples: Centralized networks with synchronous requests
• Continuous time Markov chains (CTMC) – Meant for describing continuous time random process
• Examples: Distributed networks with synchronous or asynchronous requests

Markov chains – Basics and applications

SELECTED TOPICS IN NETWORK DESIGN

Markov chains – Math representation – DTMC

• Let S₀, S₁, ..., S_n, S_n+1,... denote a memoryless random process occurring at discrete time instants 0,1,...,n,n+1,...

​

• The Markov property or memoryless property is given by

P(S_n+1 | S_n,..., S₀) = P(S_n+1 | S_n) = P(S₁ | S₀)

​

• P(S_n+1 | S_n) is referred to as transition probability

​

• Suppose the set of states is given by 𝒮 = {s₁,s₂,...,s_N} then we can define an N × N transition probability matrix P

Markov chains – Basics and applications

SELECTED TOPICS IN NETWORK DESIGN

Markov chains – Math representation – DTMC (contd.)

​

​

​

​

• A realization of the random process is obtained by choosing an initial state S₀ = s₁ and choosing the next state randomly based on the transition probabilities

P(S₁ = s_j | S₀ = s₁) or P(S_n+1| S_n = s₁) with n = 0

• Use Monte Carlo method
• Next, we increment n and choose new state based on P

Markov chains – Basics and applications

SELECTED TOPICS IN NETWORK DESIGN

Markov chains – Math representation – DTMC (contd.)

• Choose the next state randomly based on the transition probabilities

P(S_n+1 = s_k | S_n = s_j) where j = 1,...,N and k = 1,...,N

• Increment n and repeat above step

Some observations:

• Note that all state transitions may not be possible
• When every state can be visited from every other state then we call the Markov chain as irreducible
• We can calculate the mean recurrence time for different states in an irreducible Markov chain

Markov chains – Basics and applications

SELECTED TOPICS IN NETWORK DESIGN

Markov chains – Math representation – DTMC (contd.)

• In order to find the steady state distribution (π), define the initial distribution π₀ = [π_1,0, π_2,0,..., π_N,0]^†
• Here, the state probability π_j,n = P(S_n = s_j) where j = 1,...,N
• The state probability in the next state (i.e., in step n+1) is given by

​

Markov chains – Basics and applications

SELECTED TOPICS IN NETWORK DESIGN

Markov chains – Math representation – DTMC (contd.)

• The steady state probability (π) can be written as

​

​

​

​

​

• Normalization equation :

​

Markov chains – Basics and applications

SELECTED TOPICS IN NETWORK DESIGN

Markov chains – Math representation – DTMC Example

• According to Kemeny et al.¹, the Land of Oz is blessed by many things, but not by good weather. They never have two nice days in a row. If they have a nice day, they are just as likely to have snow as rain the next day. If they have snow or rain, they have an even chance of having the same the next day. If there is change from snow or rain, only half of the time is this a change to a nice day.
• Find the steady state distribution
• Given that today is a nice day, what is the probability that the 4^th day will be rainy?

​

• J. G. Kemeny, J. L. Snell, G. L. Thompson, Introduction to Finite Mathematics, 3rd ed. (Englewood Cliffs, NJ: Prentice-Hall, 1974).

Markov chains – Basics and applications

SELECTED TOPICS IN NETWORK DESIGN

Markov chains – Math representation – DTMC Example

• Let the set of states be defined as 𝒮 = {s_R, s_N, s_S}
• Step 1: Finding transition probability matrix
• They never have two nice days in a row.

P(S_n+1 = N|S_n = N) = 0

​

• If they have a nice day, they are just as likely to have snow as rain the next day.

P(S_n+1 = S|S_n = N) = P(S_n+1 = R|S_n = N)

​

P(S_n+1 = N|S_n = N) + P(S_n+1 = R|S_n = N) + P(S_n+1 = S|S_n = N) = 1

​

🡪 P(S_n+1 = S|S_n = N) = P(S_n+1 = R|S_n = N) = 0.5

Markov chains – Basics and applications

SELECTED TOPICS IN NETWORK DESIGN

Markov chains – Math representation – DTMC Example

• If they have snow or rain, they have an even chance of having the same the next day.

P(S_n+1 = S|S_n = S) + P(S_n+1 = R or N|S_n = S) = 1

🡪 P(S_n+1 = S|S_n = S) = 0.5

P(S_n+1 = R|S_n = R) +P(S_n+1 = S or N|S_n = R) = 1

• P(S_n+1 = R|S_n = R) = 0.5

​

• If there is change from snow or rain, only half of the time is this a change to a nice day.

P(S_n+1 = N|S_n = S) = 0.25 (i.e., half of 0.5)

P(S_n+1 = N|S_n = R) = 0.25 (i.e., half of 0.5)

Markov chains – Basics and applications

SELECTED TOPICS IN NETWORK DESIGN

Markov chains – Math representation – DTMC Example

• So P(S_n+1 = R|S_n = S) = 0.25 and P(S_n+1 = S|S_n = R) = 0.25

​

• Then P is defined as 3 × 3 transition probability matrix

​

​

​

​

​

• Let initial distribution be denoted as π₀ = [π_R,0, π_N,0, π_S,0]^†
• Assume some arbitrary values for π_j,0 where j ∈{R,N,S} while normalization condition is satisfied
• Say, π₀ = [0, 1, 0]^†

Markov chains – Basics and applications

SELECTED TOPICS IN NETWORK DESIGN

Markov chains – Math representation – DTMC Example

• Steady state is given by repeating π_n+1 = Pπ_n where n = 0,1,...

​

Markov chains – Basics and applications

SELECTED TOPICS IN NETWORK DESIGN

Markov chains – Math representation – DTMC Example

• Convergence happens by 8^th iteration to give

π = [0.4, 0.2, 0.4]^†

• Given day 0 is nice, P(4^th day being rainy) = π_R,3 = 0.40625

​

Selected Topics in Network Design

Markov Chains – Applications to Queuing Theory

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Markov Chains – Applications to Queuing Theory

SELECTED TOPICS IN NETWORK DESIGN

Introduction

• Network design can be viewed as management of interconnected queues
• Queue status in the nodes vary with arrivals and departure of packets/requests
• Arrival events and resource availability can be random
• Link access methods determine the departure events
• Mismanagement of queues leads to congestion and loss of packets/requests (i.e., outage events)
• Hence, study of queues (aka queuing theory) becomes very important
• Markov chains have been extensively applied to queuing theory

Markov Chains – Applications to Queuing Theory

SELECTED TOPICS IN NETWORK DESIGN

Basics of queuing theory

• Queues in a network are managed either by increasing the resources or redirecting the packets/requests elsewhere
• Let’s visualize a single node in a wireless/wired network as a queuing model

Markov Chains – Applications to Queuing Theory

SELECTED TOPICS IN NETWORK DESIGN

Basics of queuing theory (contd.)

• In order to visualize the node as Markovian model the arrivals and/or departures must be memoryless
• The queue status can be treated as the state of the MC
• The state transition probability matrix P must be defined
• The steady state distribution of the queue must be found
• Using the steady state distribution we can find
• Mean queue size
• Throughput of the node

​

Markov Chains – Applications to Queuing Theory

SELECTED TOPICS IN NETWORK DESIGN

Basics of queuing theory

• Similar to single node queuing model, we also have multi-server queuing models

Markov Chains – Applications to Queuing Theory

SELECTED TOPICS IN NETWORK DESIGN

DTMC example: Queuing model

• Suppose a resource node is storing and forwarding packets according to the probability distributions given below.

​

​

​

​

​

​

Suppose the total buffer size (B) is 3 packets.

​

• Find the mean number of packets in the buffer.
• Find the probability of dropping the packets.

Markov Chains – Applications to Queuing Theory

SELECTED TOPICS IN NETWORK DESIGN

DTMC example: Queuing model (contd.)

• Let q_n denote the state (queue status) of the MC
• So q_n ∈ {0,...,B} where B = 3 packets and n = 0,1,2,...
• The state evolves with arrivals and departures in n

​

​

• Assume departures occur first followed by arrivals
• So the transition probabilities are given by

​

• Note that a_n = i based on P(a_n = i) where i ∈ {0,...,3}
• Similarly d_n depends on q_n and the departure process

q_n+1 = q_n – d_n + a_n

P(q_n+1 = k’|q_n = k) where k, k’ ∈ {0,...,B}

Markov Chains – Applications to Queuing Theory

SELECTED TOPICS IN NETWORK DESIGN

DTMC example: Queuing model (contd.)

• d_n = min(q_n, j) = min(k, j) where k ∈ {0,...,B} and j ∈ {0,1,2}

which occurs with P(#departure = j)

​

• Therefore, q_n+1 = k’ can be expressed as

​

​

• As k’ ∈ {0,...,B}, we rewrite the transition function as

​

​

• So the transition probabilities are given by

k’ = k – min(k, j) + i

k’ = min(B, max(k – min(k, j) + i, 0))

Markov Chains – Applications to Queuing Theory

SELECTED TOPICS IN NETWORK DESIGN

DTMC example: Queuing model (contd.)

• Size of transition probability matrix P is (B+1) × (B+1)
• Apply the recursive formula π_n+1 = Pπ_n for n = 0,1,....
• Here, π_n = [π_0,n ,...., π_B,n] where π_k,n = P(q_n = k)
• The steady state probability is given by π
• Mean queue size and blocking probability are given by

​

Markov Chains – Applications to Queuing Theory

SELECTED TOPICS IN NETWORK DESIGN

DTMC example: Queuing model (contd.)

• Numerical values

​

Markov Chains – Applications to Queuing Theory

SELECTED TOPICS IN NETWORK DESIGN

Markov chains – Some notations

Markov Chains – Applications to Queuing Theory

SELECTED TOPICS IN NETWORK DESIGN

Markov chains – Some important definitions

• Consider system having multiple servers m
• System utilization: Ratio of time a server is busy to the time it is available

​

• Traffic Intensity: Product of mean arrival rate and the mean service time

​

• Little’s theorem: Mean queue size equals the product of mean arrival rate and mean waiting time

​

Markov Chains – Applications to Queuing Theory

SELECTED TOPICS IN NETWORK DESIGN

Markov chains – Some important definitions

• Flow conservation principle: For a lossless system what goes into the system is equal to what comes out of the system

Markov Chains – Applications to Queuing Theory

SELECTED TOPICS IN NETWORK DESIGN

Markov chains – Example

• For the example derive the relation between all arrival rates using the flow conservation principle
• Derive the utilization for each server

Markov Chains – Applications to Queuing Theory

SELECTED TOPICS IN NETWORK DESIGN

Markov chains – Example (contd.)

• At CPU, we have incoming and outgoing rate as
• As some packets are diverted to the disk with probability P we have λ_DISK = P λ_CPU
• The incoming rate and outgoing rate of the entire system is λ, we have λ = (1-P) λ_CPU
• By flow conservation we have λ_DISK = λ + λ_CPU
• The utilization of resources are given by

Selected Topics in Network Design

Markov Chains – CTMC

Vamsi Krishna Tumuluru

Department of Electronics and Comm. Engineering

Markov Chains – CTMC

SELECTED TOPICS IN NETWORK DESIGN

CTMC – Math representation

• Suppose the set of states is given by 𝒮 = {s₁,s₂,...,s_N}
• Suppose, a random process {X_t} taking random values from 𝒮 for t > 0
• The Markov property can be stated as

​

​

​

• Suppose a state X_t = i occurs. Then S–1 random timers are chosen based on the their respective exponential distributions with mean 1/Q_ij where j ∈ 𝒮\i
• Once a timer expires, the state X_t+s occurs taking the corresponding value from 𝒮

Markov Chains – CTMC

SELECTED TOPICS IN NETWORK DESIGN

CTMC – Math representation

• The transition rate Q_ii is given by