Transcript Principles of Network Algorithms - Mazin S. Al

University of Technology
Computer Science Department
Network Administration Branch
First Class
Resource:
The University California, San Diego
Computer Science and Engineering
Lecture Notes of Professor George Varghese
http://www-cse.ucsd.edu /~varghese
2
Lecture1:
Introduction and Principles of Network Algorithms
Contents:
1. Algorithm (Definition)
2. Computer Network (Definition)
3. Network Components (NIC, Access Point, Repeater, HUB,
Bridge, Switch, Router, BRouter, GATEWAY)
4. Network Bandwidth (Definition)
5. Network Algorithms
6. Routing (Routing Protocols, Routing Table, Routing Configuration)
7. Capacity of Router
8. History of big Routers (Short History)
3
Lecture 2:
Lookup and Router Architecture
Contents:
1. Short Review
2. Routing Table Lookup
3. Router Architecture (Input Port Processing, Switching Fabrics,
Routing Processing, Output Port Processing)
4
Lecture 3:
Searching Routing-Table Algorithms
Contents:
1. Searching Algorithm (Definition)
2. Searching Routing Table (Definition)
3. Searching Routing Table Algorithms
3.1. Binary Search.
3.2. Hash Table.
3.3. Tire based Algorithms:
3.3.1. 1-Bit Trie (BMP) Algorithm
3.3.2. Multi-Bit Tire (VST) Algorithm
3.3.3. Compressed Tries
4. Tire based Algorithm for Strings
5
Lecture 4:
Searching Routing-Table Algorithms
Contents:
1. Searching Algorithm
2. Searching Routing Table
3. Searching Routing Table Algorithms
3.1. Binary Search.
3.2. Hash Table.
3.3. Tire based Algorithms:
3.3.1. 1-Bit Trie (BMP) Algorithm
3.3.2. Multi-Bit Tire (VST) Algorithm
3.3.3. Compressed Tries
4. Tire based Algorithm for Strings
6
Lecture 5:
Packet Classification
Contents:
1. Network Reference Models
2. TCP/IP Reference Model (IP Protocol Stack)
2.1. The Application Layer
2.2. The Transport Layer (Host-to-Host) (End-to-End)
2.3. Internet Layer
2.4. Network Layer (Host-To-Network) (Link)
3. ICMP and OSPF Core Protocols
4. IP v4 and IP v6 Packets
5. TCP and UDP Packets
6. Simplified Network Packet Format
7. Screening Router
7
Lecture 6:
Packet Classification (Cont.)
Contents:
1. Network Reference Models
2. TCP/IP Reference Model (IP Protocol Stack)
2.1. The Application Layer
2.2. The Transport Layer (Host-to-Host) (End-to-End)
2.3. Internet Layer
2.4. Network Layer (Host-To-Network) (Link)
3. ICMP and OSPF Core Protocols
4. IP v4 and IP v6 Packets
5. TCP and UDP Packets
6. Simplified Network Packet Format
7. Screening Router
8
Lecture 7:
Switching Theory
Contents:
1. Short Reviewing
2. Switching Theory
3. Crossbar Switch Architecture
4. Crossbar Switch Models
IQ Switch
OQ Switch
CIOQ Switch
9
Lecture 8:
Switching Theory (Cont.)
Contents:
1. Review
2. Speed Up and Delay Control in CIOQ
3. Stable Marriage Algorithms for CIOQ
Gale-Shapley Algorithm (GSA)
4. Scheduling Algorithms for CIOQ
First In First Out Scheduling Algorithm (FIFO)
Most Urgent Cell First Scheduling Algorithm (MUCF)
Randomized Switch Scheduling
10
Lecture 9:
Bandwidth Partitioning
Contents:
1. Review
2. Network Bandwidth
2.1. Network Bandwidth – Network Centric Approach
2.2. Network Bandwidth – User Centric Approach
11
Lecture 10:
IP Addressing
Contents:
1. IPv4 Addresses
2. Classful IPv4 Addressing Scheme
3. Public and Private IP Addresses
4. Reserved IP Addresses
5. Subnetting / Netmask
6. NAT (Network Address Translation)
12
University of Technology
Computer Science Department
Network Administration Branch
First Class
Lecture1:
Introduction and Principles of Network Algorithms
Contents:
1. Algorithm (Definition)
2. Computer Network (Definition)
3. Network Components (NIC, Access Point, Repeater, HUB,
Bridge, Switch, Router, BRouter, GATEWAY)
4. Network Bandwidth (Definition)
5. Network Algorithms
6. Routing (Routing Protocols, Routing Table, Routing Configuration)
7. Capacity of Router
8. History of big Routers (Short History)
14
1. Algorithm (from Algoritmi, the Latin form of Al-Khwārizmī) in
computer science is a step-by-step procedure for calculations,
data processing, and automated reasoning to solve a specific
problem.
The algorithm should be starting from an
initial state and initial input, then should be
transition from one state to the next to
execute the instructions (which describe a
computation that), eventually producing
"output" and terminating at a final ending
state.
initial state
exec. state
exec. state
exec. state
final state
15
2. Computer Network, often simply referred to as a network, is an
interconnected collection of hardware components and
autonomous computers interconnected by communication
channels that allow to exchange information and share the
resources.
A network consists of a set of devices like:
Hosts , host is individual computer connected to the computer
network, which can offer information resources, services, and
applications to users or other nodes on the network.
Nodes , node is any device that is attached to a network,
either a redistribution point (capable of sending, receiving or
forwarding information over a communications channel),
or a communication endpoint (some terminal equipment).
16
17
3. Network Components are used to connect computing
devices together in different networks, and to connect multiple
networks or subnets together, these includes:
NIC: (Network Interface Card) is network device used to
enable a network device (such as a computer or other network
wired
equipment) to connect to a network.
network
Access Point: is a network device
that allows wireless devices to
connect to a wired network.
Repeater: is a network device that
connects two or more network
segments and retransmits any
incoming signal to all other
segments.
18
Access Point
Segment A
Segment B
Repeater
HUB / Switch: is a central network device that connects all
nodes in a star topology. Also it is concentrator (a device that
can have multiple inputs and outputs all active at one time).
HUB
Switch
Difference
between
HUB and Switch
19
Bridge: is a network device that sends information between
two LANs.
20
Router: is a network device that direct traffic between hosts.
A router is connects two or more different networks.
BRouter: is a network device that acts as a Bridge in one
circumstance and as a Router in another.
GATEWAY: The term gateway refers to a software or hardware
interface that enables two different types of networked systems
or software to communicate.
Network Components:
NIC , Access Point , Repeater , HUB , Bridge ,
Switch , Router , BRouter , GATEWAY
21
The difference between Switch and Router
Connection to other
Networks
22
4. Network Bandwidth
Network Bandwidth (bit rate, channel capacity, or throughput)
is a measure of communication channel usage (available or
consumed of communication path) in bits/second “pbs” or
multiples of it (kilobits/s “Kbps”, megabits/s “Mbps”, etc.).
23
24
5. Network Algorithms are the algorithms
to select the paths in network along which
(network traffic routes) to send network
traffic “also called Routing”, and to process
the network bottlenecks at servers, routers,
or other networking devices.
There are many network algorithms like
Trie based Algorithm, Multibit Trie
Algorithm, etc.
25
6. Routing is the process of selecting paths in network along
which (network traffic routes) to send network traffic.
There are two main routing protocols:
• Distance-Vector (DV) Routing Protocol (Simple
and efficient in
small networks and require little management, but it have count-to-infinity
problem).
• Link-State (LS) Routing Protocol (More scalable for
networks, but more complex).
use in large
There are other protocols like; Optimized Link State Routing
Protocol (OLSR) (which used for routing mobile ad-hoc networks), and
Path Vector Routing Protocol (PV) (which used for routing between
autonomous network systems).
26
Each of these routing protocols are applying a “Routing Table”
to multiple routes to select the best route.
The routing table (routing metrics, or routing distances)
contains information about the topology of the network
immediately around the router.
The routing table consists of at least three information fields:
• Network ID.
• Cost (cost or length of path through).
• Next Hop (the address of the next station to which the packet is to be sent).
Network ID
27
Cost
Next Hop
There are two main routing configuration ways:
• Static Routing: The network administrator adds the routes
(fixed paths) to the routing table manually. But when there
is a change in the network or a failure occurs between two
nodes, traffic will waiting for repairing the failure (not be
rerouted), or the static route to be updated by the
administrator before restarting its journey.
• Dynamic Routing (Adaptive Routing): The system adds
routs to the routing table automatically, the adaptation is
allow to rerouting the routing table when automatically.
28
7. Capacity of Router
Capacity of Router = N x R
(measured by packets per second)
N = number of linecards (Typically 8 - 32 per chassis)
R = line-rate (1Gb/s, 2.5Gb/s, 10Gb/s, 40Gb/s, 100Gb/s)
29
8. History of big Routers
In the original 1960s, the general-purpose computers served
as routers.
The general-purpose computers with extra hardware added to
accelerate both common routing functions and specialized
functions such as encryption functions.
Other changes also improve reliability, such as using battery
rather than mains power, and using solid storage (hard disk)
rather than magnetic storage.
The
first
modern
(dedicated,
standalone) router were the Fuzzball
router (with capacity: 56kbps).
30
Cisco GSR 12816
Capacity: 640Gb/s
31
Juniper T640
Capacity: 320Gb/s
Mikrotik
3Com
D-Link
32
Cisco Series
Cisco 2811
33
There are several manufacturers of routers including:
• 3Com (www.3com.com)
• Cisco Systems (www.cisco.com)
• D-Link Systems (www.dlink.com)
• Juniper Networks (www.juniper.net)
• Linksys (www.linksys.com)
• Mikrotik (www.mikrotik.com)
• NETGEAR (www.netgear.com)
34
University of Technology
Computer Science Department
Network Administration Branch
First Class
Q&A
Principles of Network Algorithms
Second Semester – 2012
Prepare by: Dr. Mazin S. Ali
available at: www.uotechnology.edu.iq/dep-cs
University of Technology
Computer Science Department
Network Administration Branch
First Class
Lecture 2:
Lookup and Router Architecture
Contents:
1. Short Review
2. Routing Table Lookup
3. Router Architecture (Input Port Processing, Switching Fabrics,
Routing Processing, Output Port Processing)
37
1. Review:
Router: (as sown in the pervious lecture) is a network device that direct
traffic between hosts.
A router is connects two or more different networks.
GATEWAY: The term gateway refers to a software or hardware
interface that enables two different types of networked systems
or software to communicate.
Routing Table: (Routing Metrics, or Routing Distances)
contains information about the topology of the network
immediately around the router, the router are applying a
“Routing Table” to multiple routes to select the best route.
38
2. Routing Table Lookup:
The Routing Table Lookup is search through the routing
table, looking for a destination entry that best matches the
destination network address of the packet, or a default route
if the destination entry is missing
The most important complicating factor is that backbone
routers must operate at high speeds, being capable of
performing millions of lookups per second.
It is best for the input port processing to be able to proceed
at line speed, that is, that a lookup can be done in less than
the amount of time needed to receive a packet at the input
port. In this case, input processing of a received packet can
be completed before the next receive operation is complete.
39
3. Router Architecture
A high-level view of Router Architecture is shown below.
Input Ports:
Terminating
an incoming
link to a
router, data
link
processing,
and
performs a
lookup and
forwarding
functions
Input Ports
Output Ports
Switching Fabric
Output ports:
Stores the
packets (that
have been
forwarded to it
through the
switching fabric)
and then
transmits the
packets on the
outgoing link
Routing Processor
Switching Fabric:
Connects the
router's input ports
to its output ports
40
Routing Processor: Executes the Routing Protocols,
Maintains the Routing Tables, and performs Network
Management functions, within the router
Input Port
Line
Termination
Function
Data Link
Processing
Lookup,
Forwarding,
Queuing
41
Switching Fabric
3.A. Input Port Processing
Terminating an incoming link to a router, data link processing,
and performs a lookup and forwarding functions.
3.A. Input Port Processing
Inside Input Port… the router determines the output port to
which an arriving packet will be forwarded via the switching
fabric.
((The choice of the output port is made using the information
contained in the routing table)).
A shadow copy (local copy) of the routing table is stored at
each input port and updated (as needed) by the routing
processor.
With shadow copies (local copies) of the routing table, the
switching decision can be made locally,
at each input port, without invoking
the centralized routing processor.
Decentralized
Switching
42
3.A. Input Port Processing
As an old fashioned: When a computer works as a router;
Here, the input port is just a NIC (with
limited processing capabilities), so the
input port simply forward the packet to
the centralized routing processor (the
computer's CPU) which will perform the
routing table lookup and forward the
packet to the appropriate output port.
Centralized
Switching
43
3.B. Switching Fabrics
The switching fabric is at the heart of a router. Through it the
packets are actually moved from an input port to an output
port.
Switching can be accomplished in a number of ways:
44
3.B. Switching Fabrics / Switching via Memory
The input port receives the packets.
The packet was copied from the
input port into memory of the routing
processor (on the input port).
The routing processor extracted the
destination address from the header,
looked up the appropriate output
port in the routing table, and copied
the packet to the output port's
buffers.
45
3.B. Switching Fabrics / Switching via Bus
The input ports transfer a packet
directly to the output port over a
shared bus, without intervention by
the routing processor.
But only one packet at a time can be
transferred over the bus.
A packet arriving at an input port (and finding the bus busy
with the transfer of another packet) is blocked from passing
through the switching fabric and is queued at the input port.
Because every packet must cross the single bus, the
switching bandwidth of the router is limited to the bus speed.
46
3.B. Switching Fabrics / Switching via Crossbar
One way to overcome the bandwidth
limitation of a single, shared bus is to
use a crossbar.
A crossbar switch is an interconnection
network consisting of 2N busses that
connect N input ports to N output ports.
A packet arriving at an input port travels along the horizontal
bus attached to the input port until it intersects with the
vertical bus leading to the desired output port.
If the vertical bus is free, the packet is transferred to the
output port. If the vertical bus is being used to transfer a
packet from another input port to this same output port, the
arriving packet is blocked and must be queued at the input
port.
47
3.C. Routing Processing
Routing Processing is the “Routing Table Lookup” for search
through the routing table, looking for a destination entry that
best matches the destination network address of the packet,
or a default route if the destination entry is missing
The most important complicating factor is that backbone
routers must operate at high speeds, being capable of
performing millions of lookups per second, so we have several
algorithms to accomplish that, like:
• Tire based Algorithm,
• Multibit Tire Algorithm,
• Compressed Tries,
• Binary Search.
3.D. Output Ports Processing
It takes the packets which stored in the output port's memory
and transmits them over the outgoing link.
The data link processing and line termination are interact with
the input port on the other end of the outgoing link.
Switching Fabric
The queuing and buffer management functionality are needed
when the switch fabric delivers packets to the output port at a
rate that exceeds the output link rate.
49
Output Port
Queuing
Data Link
Processing
Line
Termination
Function
University of Technology
Computer Science Department
Network Administration Branch
First Class
Q&A
Principles of Network Algorithms
Second Semester – 2012
Prepare by: Dr. Mazin S. Ali
available at: www.uotechnology.edu.iq/dep-cs
University of Technology
Computer Science Department
Network Administration Branch
First Class
Lecture 3:
Searching Routing-Table Algorithms
Contents:
1. Searching Algorithm (Definition)
2. Searching Routing Table (Definition)
3. Searching Routing Table Algorithms
3.1. Binary Search.
3.2. Hash Table.
3.3. Tire based Algorithms:
3.3.1. 1-Bit Trie (BMP) Algorithm
3.3.2. Multi-Bit Tire (VST) Algorithm
3.3.3. Compressed Tries
4. Tire based Algorithm for Strings
52
1. Searching Algorithm:
Search Algorithm: is an algorithm for
finding a specific item among a
collection of items.
Search Example:
5
3
8
2
4
6
9
1
-
-
-
-
7
-
10
To find item(5) “search key” we need to only 1 step to find it,
to find item(10) we need to 15 steps to find it,
to find other item like item(9) we need to 7 steps to find it,
and so on.
So..
The best case is when we find the item at the first location (1 time),
while worst case is when we find the item at the last location (n times),
and the average case is (best-case + worst-case)/2.
53
2. Searching Routing Table:
The most important complicating factor is that “backbone
routers“ must operate at high speeds, being capable of
performing millions of lookups per second.
So the lookup operations should be searching a destination
through the Routing Table at high speeds.
The linear search suffered from a problem with its worst case
cost, its proportional to the number of items in the list.
So the linear search is not suitable for lookups routing table,
and we need to the faster searching algorithm.
54
3. Searching Routing Table Algorithms:
The worst case cost of Linear Search is proportional to the
number of items in the list … this is the big problem with linear
search algorithm.
Therefore, there are other algorithms will be faster, but they
also impose additional requirements.
There are several Searching Algorithms to optimize the work of
lookup inside routing table like:• Binary Search Tree
• Tire based Algorithm,
• Multibit Tire Algorithm,
• Compressed Trie Algorithms.
55
3.1. Binary Search:
Binary Tree: is a tree that is characterized by that any node
can have at most two branches. A binary may be empty or
consist of a root and two disjoint binary tree called the left
subtree and the right subtree .
Binary Tree Search: is a
binary tree in which the left
child (if there is) of any node
contains a smaller value
than does the parent node
and the right child (if there is)
contains a larger value than
the parent node.
Its a fast way to search a list of items.
56
3.1. Binary Search (cont.):
The idea is to look at the item in the middle. If the key is
equal to that, the search is finished. If the key is less than
the middle element, do a binary search on the left half. If it's
greater, do a binary search of the right half.
5
3
2
1
57
8
4
9
6
7
10
3.1. Binary Search (cont.):
The advantage of a binary search over a linear search is a
very good for large-number of items.
58
3.2. Hash Table:
Hash Table: is a random access data structure (like an
array), and uses a mapping function (called a hash function),
to allow for O(1) searches or constant searching time.
The Hash Function provides a way for assigning numbers
to the input data such that the data can then be stored at the
array index corresponding to the assigned number.
59
3.2. Hash Table (cont.):
Example: We has a hash table array of strings with size=11.
0
Steve
1
2
3
Simple Hash Function
hash(“
“,11)
:
yields
3
4
5
6
7
8
9
10
60
Steve
3.2. Hash Table (cont.):
0
Spark
1
2
3
Simple Hash Function
hash(“
“,11)
:
yields
6
4
5
6
7
8
9
10
61
Steve
Spark
3.2. Hash Table (cont.):
0
Notes
1
2
3
Simple Hash Function
hash(“
“,11)
:
yields
10
Steve
4
5
6
Spark
7
8
9
10
62
Notes
3.2. Hash Table (cont.):
0
Pad
1
2
3
Simple Hash Function
hash(“
“,11)
:
yields
3
Steve
4
5
6
Spark
7
8
9
10
63
Notes
Collision
A collision occurs
when two data
items are hashed
to the same value.
3.2. Hash Table (cont.):
Separate chaining is a method for
dealing with collisions.
Array of Linked Lists
0
1
The hash table is an array of
linked lists.
Data items that hash to the same
value are stored in a linked list
originating
from
the
index
equivalent of their hash value.
2
3
4
5
6
7
8
9
10
64
3.2. Hash Table (cont.):
Hash Table with Separate Chaining to avoid the collision.
0
1
2
3
Simple Hash Function
hash(“
“,11)
:
yields
Steve : 3
4
5
6
Spark : 6
7
Notes: 10
8
Pad: 3
Spark
9
10
65
Steve
Notes
Pad
3.2. Hash Table (cont.):
A search follows the same steps as doing an insertion.
i.e. the search key is “Notes”
0
Notes
1
2
3
Simple Hash Function
hash(“
“,11)
10 yields
:
Steve
4
5
6
Spark
7
The number of steps
is O(1)
66
8
9
10
Notes
Pad
3.2. Hash Table (cont.):
Separate Chaining allows us to solve the problem of collision.
The drawback is, all items inserted at the same place in the
array (and this is impossible).
In that case, we'd really be doing a straight linear search on a
linked list, which means that our search operation is back to
being O(n) .
The worst case search time for a hash table is O(n).
67
University of Technology
Computer Science Department
Network Administration Branch
First Class
Q&A
Principles of Network Algorithms
Second Semester – 2012
Prepare by: Dr. Mazin S. Ali
available at: www.uotechnology.edu.iq/dep-cs
University of Technology
Computer Science Department
Network Administration Branch
First Class
Lecture 4:
Searching Routing-Table Algorithms
Contents:
1. Searching Algorithm
2. Searching Routing Table
3. Searching Routing Table Algorithms
3.1. Binary Search.
3.2. Hash Table.
3.3. Tire based Algorithms:
3.3.1. 1-Bit Trie (BMP) Algorithm
3.3.2. Multi-Bit Tire (VST) Algorithm
3.3.3. Compressed Tries
4. Tire based Algorithm for Strings
70
3.3. Tire based Algorithms:
“The term trie comes from retrieval”.
In general, a trie tree (or prefix tree), is an ordered tree
data structure that is used to store a list (where the keys are
usually strings).
No node in the trie tree stores the key associated with that
node; instead, its position in the tree defines the key with
which it is associated.
The root is associated with the empty string, and the values
are normally not associated with every node, only with
leaves.
3.3. Tire based Algorithms (Cont.):
3.3.1. 1-Bit Trie Algorithm (Tire based Algorithm):
1-Bit Trie (or Best Matching Prefix (BMP)) is a binary treebased data structure that uses prefix bits to direct branching,
the search guided by bits.
At each level, proceed left or right based on the next address
bit, on visiting a node marked as prefix, the search ends
when there are no more branches to take.
The search guided by bits, these means that the sequential
prefix search by length (Look at length-1 prefixes first, then
length-2 prefixes, …).
Note that each step reduces the search space.
3.3. Tire based Algorithms (Cont.):
3.3.1. 1-Bit Trie Algorithm(Cont.):
Example 1:
Prefixes:
a : 0*
b : 01000*
c : 011*
d : 1*
e : 100*
f : 1100*
g : 1101*
h : 1110*
i : 1111*
d
a
c
e
f
b
g
h
Each step reduces the
search space
i
3.3. Tire based Algorithms (Cont.):
3.3.1. 1-Bit Trie Algorithm(Cont.):
Example 2:
P5
P1
P2
P6
P3
P4
3.3. Tire based Algorithms (Cont.):
3.3.1. 1-Bit Trie Algorithm (Cont.):
The 1-Bit Trie algorithm is a classical solution to allow a good
representation of length prefixes, but these way may involve
long sequences of one-child nodes.
These requires bit inspection and these allow to increase
lookup time.
drawback
have long sequences
of one-child nodes
3.3. Tire based Algorithms (Cont.):
3.3.2. Multi-Bit Trie Algorithm (VST):
The basic idea is to speedup search by examining multiple
bits at a time, for example, examine 4 bits.
The number of bits examined in each step called “Stride”, so
the algorithm also called Variable-Stride Trie (VST).
Its complex algorithm to calculate, but should notes that, the
nodes at the same level may have different strides.
For example; the stride for the root of some tree is 2; that for
the left child of the root is 5; and that for the root’s right child
is 3.
3.3. Tire based Algorithms (Cont.):
3.3.2. Multi-Bit Trie Algorithm (VST) (Cont.):
Example:
00
Prefixes:
P1 : 10*
P2 : 11*
P3 : 11001* 00000
P4 : 1*
00001
P5 : 0*
P6 : 1000000* 00010
01
10
11
P5
P4
P1
P2
P6
001
010
011
00011
:
000
:
11111
Assume that the stride for the root of some tree is 2;
And that for the root’s left child is 5;
And that for the root’s right child is 3.
100
101
110
111
P3
3.3. Tire based Algorithms (Cont.):
3.3.3. Compressed Tries:
The “Compressed Tries” (or Path Compressed Tries) attempt
to reduce space and time performance of the tow Trie
algorithms:
• 1-Bit Trie algorithm (BMP), and
• Mulit-Bit Trie algorithm.
3.3. Tire based Algorithms (Cont.):
3.3.3.A. Compressed Tries with 1-Bit Trie Algorithm:
The “Path Compressed Tries” attempt to reduce space and
time performance of 1-Bit Trie algorithm (BMP), by the
following:
1- Collapse one-way branch nodes.
2- Jump directly to the bit used for decision.
Prefixes:
a : 0*
b : 01000*
c : 011*
d : 1*
e : 100*
f : 1100*
g : 1101*
h : 1110*
i : 1111*
d
a
c
e
f
b
g
h
i
d
a
Collapse
Jump
c
e
f
b
g
h
i
d
a
c
Collapse
Jump
b
e
f
g
h
i
d
a
Collapse
Jump
b
c
e
f
g
h
i
d
a
Collapse
b
c
Jump
e
f
g
h
i
d
a
b
c
e
f
g
h
i
d
a
b
1-Bit Trie / Prefixes:
a : 0*
b : 01000*
c : 011*
d : 1*
e : 100*
f : 1100*
g : 1101*
h : 1110*
i : 1111*
c
e
Compressed 1-Bit Trie/ Prefixes:
a : 0*
b : 00*
01000*
c : 01*
011*
f
g
d : 1*
e : 10*
100*
f : 1100*
g : 1101*
h : 1110*
i : 1111*
h
i
1-Bit Trie Prefixes:
a : 0*
b : 01000* Compressed
c : 011*
1-Bit Trie Prefixes:
d : 1*
a : 0*
e : 100*
b : 00*
f : 1100*
c : 01*
g : 1101*
d : 1*
h : 1110*
e : 10*
i : 1111*
f : 1100*
g : 1101*
h : 1110*
i : 1111*
1-Bit Trie Algorithm
Path Compressed Tries
( Collapse and Jump )
Each step reduces the
search space
Compressed
1-Bit Trie Algorithm
3.3. Tire based Algorithms (Cont.):
3.3.3.B. Compressed Tries with Multi-Bit Trie Algorithm:
The Compression Scheme is:
• Compress repeated occurrences of BMPs.
• Compression is same across sub-trie.
• Compression is not optimal – but access is simpler and
efficient.
4. Tire based Algorithm for Strings:
Example 1:
A 1-Bit Trie tree for keys "A", "to", "tea", "ted", "ten", "i", "in",
and "inn“ is display here:
t
A
i
n
e
o
a
d
n
n
4. Tire based Algorithm for Strings (Cont.):
Example 1 (Cont.):
A Compressed tree for the 1-Bit Trie tree is display here:
t
A
i
Collapse
n
e
o
Jump
a
d
n
n
n
4. Tire based Algorithm for Strings (Cont.):
Example 1 (Cont.):
A Compressed tree for the 1-Bit Trie tree is display here:
t
A
i
nn
e
o
a
d
n
4. Tire based Algorithm for Strings (Cont.):
Example 1 (Cont.):
A Compressed tree for the 1-Bit Trie tree is display here:
t
A
i
nn
nn
e
o
a
d
n
4. Tire based Algorithm for Strings (Cont.):
Example 1 (Cont.):
A Compressed tree for the 1-Bit Trie tree is display here:
t
A
inn
e
o
a
d
n
4. Tire based Algorithm for Strings (Cont.):
Example 2:
Construct the 1-Bit Trie tree for the following keys: “bear",
“bell", “bid", "ted", “bull", “buy", “sell", “stock", and “stop“.
Then construct the Compressed 1-Bit Trie tree for it.
Solution:
Compressed 1-Bit Trie Tree
1-Bit Trie Tree
4. Tire based Algorithm for Strings (Cont.):
Example 3:
Construct the 1-Bit Trie tree for the following keys: “yahoo",
“yamal", “google", “gomee", “gomer", “facebook", “facetime",
“fact", and “facetik“. Then construct the Compressed 1-Bit
Trie tree for it.
Solution:
?
?
1-Bit Trie Tree
Compressed 1-Bit Trie Tree
Must be
remember
that …
Router
Input Links
Switch
Output Links
a
a
b
b
c
c
Processor
Forwarding Table
f
i
Prefix
0
00
01
1
10
1100
1101
1110
1111
Output Link
a
b
c
d
e
f
g
h
i
f
i
Router
Prefix Output Link
0
a
00
b
01
c
1
d
10
e
1100
f
1101
g
1110
h
1111
i
Compressed
1-Bit Trie Algorithm
Router
Switch
Input Links
a
1100
Output Links
a
b
b
c
c
Processor
1100
Forwarding Table
f
f
Compressed
1-Bit Trie Algorithm
i
Prefix
0
00
01
1
10
1100
1101
1110
1111
Output Link
a
b
c
d
e
f
g
h
i
f
i
Router
Switch
Input Links
1100
a
Output Links
a
b
b
c
c
Processor
Forwarding Table
f
Centralized
Switching
i
Prefix
0
00
01
1
10
1100
1101
1110
1111
Output Link
a
b
c
d
e
f
g
h
i
f
i
Router
Switch
Input Links
Output Links
a
a
b
b
c
c
Processor
Forwarding Table
f
00
Decentralized
Switching
i
Prefix
0
00
01
1
10
1100
1101
1110
1111
Output Link
a
b
c
d
e
f
g
h
i
f
i
University of Technology
Computer Science Department
Network Administration Branch
First Class
Q&A
Principles of Network Algorithms
Second Semester – 2012
Prepare by: Dr. Mazin S. Ali
available at: www.uotechnology.edu.iq/dep-cs
University of Technology
Computer Science Department
Network Administration Branch
First Class
Lecture 5:
Packet Classification
Contents:
1. Network Reference Models
2. TCP/IP Reference Model (IP Protocol Stack)
2.1. The Application Layer
2.2. The Transport Layer (Host-to-Host) (End-to-End)
2.3. Internet Layer
2.4. Network Layer (Host-To-Network) (Link)
3. ICMP and OSPF Core Protocols
4. IP v4 and IP v6 Packets
5. TCP and UDP Packets
6. Simplified Network Packet Format
7. Screening Router
104
1. Network Reference Models:
With “1st Class - Principles of Network & Application Subject”,
we have discussed the two important network reference
models, the OSI reference model and the TCP/IP reference
model.
But with “1st Class - Principles of Network Algorithms
Subject“, we focusing only on ‘TCP/IP Reference Model’ from
Routing side of view.
TCP : Transmission Control Protocol
IP : Internet Protocol
2. TCP/IP Reference Model :
TCP/IP protocol (also called IP Protocol Stack)
is a set of communication protocols used for
the Internet and other similar networks.
It is commonly known as TCP/IP, because of
its most important protocols TCP and IP,
which were the first networking protocols
defined in this standard.
TCP/IP protocol have 4 layers:
1. Application Layer
2. Transport Layer
3. Internet Layer
4. Network Interface Layer
Application Layer
Transport
Layer
HTTP
FTP
SMTP
DNS
RTP
TCP
BGP
UDP
Internet
Layer
OSPF
IP
Network
Layer
ICMP
Network Interface
RIP
2. TCP/IP Reference Model (Cont.):
2.1. The Application Layer:
The Application Layer is a top TCP/IP layer, it’s contains all
the higher-level protocols which involve user interaction, like
HTTP , FTP , SMTP , RTP , DNS , BGP , RIP , and other
protocols.
HTTP
FTP
SMTP
FTP (File Transfer
Protocol):
It’s an application
protocol which
provides a way to move
data efficiently from
one machine to
another.
HTTP (Hyper Text
Transfer Protocol):
It’s an application
protocol for transfer
hypertext,
hypermedia, over
web information
systems
SMTP (Simple Mail
Transfer Protocol):
It’s an application
protocol for e-mail
transmission between
devices.
RTP
DNS
RTP (Realtime
Transport Protocol):
It’s an application
protocol to
delivering audio and
video over networks
DNS (Domain
Name System):
It’s an application
protocol to
translates domain
name to IP address
BGP
RIP
BGP (Border Gateway
Protocol):
It’s an application
protocol to backing the
core routing decisions
on the Internet
RIP (Routing Information
Protocol):
It’s an application protocol to
adds routs to the routing table
automatically (based DistanceVector Routing Algorithm)
Application Layer
HTTP
FTP
SMTP
RTP
DNS
BGP
RIP
Network Certification
Application Layer
HTTP
ICMP
FTP
SMTP
RTP
DNS
BGP
RIP
OSPF
2. TCP/IP Reference Model (Cont.):
2.2. The Transport Layer (Host-to-Host) (End-to-End):
The Transport Layer is located above the Internet Layer in
the TCP/IP model, it’s allow peer entities on the source and
destination hosts to carryon a conversation, and provides the
port number.
It’s used to exchange data between systems.
There are two Transport Layer (Host-to-Host) (End-to-End)
core protocols:
1. TCP (Transmission Control Protocol)
2. UDP (User Datagram Protocol)
Application Layer
Transport
Layer
HTTP
FTP
TCP
TCP is a reliable connectionoriented protocol, that offers error
correction when deliver the stream
originating on one machine to the
other machine in the network.
SMTP
DNS
RTP
BGP
RIP
UDP
UDP is an unreliable connectionless
protocol, that deliver stream
originating on one machine to the
other machine in the network
based one-shot philosophy.
2. TCP/IP Reference Model (Cont.):
2.2. The Transport Layer (Host-to-Host) (End-to-End):
TCP (Transmission Control Protocol) is a reliable
connection-oriented protocol, that offers error correction
when deliver the stream originating on one machine to the
other machine in the network.
It used to send important data such as webpages, database
information, etc;
UDP (User Datagram Protocol) is an unreliable
connectionless protocol, that deliver stream originating on
one machine to the other machine in the network based oneshot philosophy.
It used to send streaming audio and video (like Windows
Media audio files (.WMA) , Real Player (.RM)).
2. TCP/IP Reference Model (Cont.):
2.2. The Transport Layer (Host-to-Host) (End-to-End):
The UDP is faster than TCP (UDP offers speed).
The reason UDP is faster than TCP is because there is no
traffic-of ‘flow control’ or ‘error correction’ used (unreliable
connectionless protocol).
The data sent over the network is affected by collisions, and
errors will be present. So the TCP uses ‘flow control’ or ‘error
correction’
traffic (reliable connection-oriented protocol)
which need more time to finish the data sending, while UDP
not doing that.
UDP is only concerned with speed.
This is the main reason why streaming
media is not high quality.
2. TCP/IP Reference Model (Cont.):
2.3. Internet Layer:
The Internet Layer is located above the Transport Layer in
the TCP/IP model, it’s defines an official packet format and
provides the IP Addressing (using core IP Protocol), to deliver
after that independently through the network between the
sender and receiver.
The Internet Layer delivers “IP packets” (where they are
supposed here) as is avoiding congestion.
For these reasons…
The TCP/IP Internet Layer is very similar in
functionality to the OSI Network Layer.
Remember that the
Lecture Title is
Packet Classification
Application Layer
Transport
Layer
Internet
Layer
HTTP
FTP
SMTP
DNS
RTP
TCP
BGP
UDP
IP
IP defines an official
packet format and
provides IP Addresses
RIP
2. TCP/IP Reference Model (Cont.):
2.4. Network Layer (Host-To-Network) (Link):
The Host-to-Network Layer interfaces the TCP/IP protocol
stack to the physical network.
It’s a point out connect to the network using TCP/IP protocol,
so it can send IP packets over it.
Internet
Layer
IP
Network
Layer
Transport
Layer
Application Layer
HTTP
FTP
SMTP
RTP
TCP
Network Interface
DNS
UDP
BGP
RIP
University of Technology
Computer Science Department
Network Administration Branch
First Class
Q&A
Principles of Network Algorithms
Second Semester – 2012
Prepare by: Dr. Mazin S. Ali
available at: www.uotechnology.edu.iq/dep-cs
University of Technology
Computer Science Department
Network Administration Branch
First Class
Lecture 6:
Packet Classification (Cont.)
Contents:
1. Network Reference Models
2. TCP/IP Reference Model (IP Protocol Stack)
2.1. The Application Layer
2.2. The Transport Layer (Host-to-Host) (End-to-End)
2.3. Internet Layer
2.4. Network Layer (Host-To-Network) (Link)
3. ICMP and OSPF Core Protocols
4. IP v4 and IP v6 Packets
5. TCP and UDP Packets
6. Simplified Network Packet Format
7. Screening Router
122
3. ICMP and OSPF Core Protocols:
There are another important core protocols (which works
inside TCP/IP protocol) like:
• ICMP (Internet Control Message Protocol)
• OSPF (Open Shortest Path First )
ICMP is used by the
computer operating systems
to send error messages
indicating, for example, that
a requested service is not
available or that a host or
router could not be reached.
OSPF is one of group of interior
routing protocols, it’s an
adaptive
network
routing
protocol which operating within
a single autonomous system .
Application Layer
Transport
Layer
HTTP
FTP
SMTP
TCP
Internet
Layer
BGP
RIP
UDP
ICMP
Network
Layer
DNS
RTP
OSPF
IP
It’s used by the
computer Oss to
send error
messages indicating
Network Interface
It’s an adaptive network
routing protocol which
operating within a single
autonomous system
Transport
Layer
Application
Layer
Ping is a useful tool for testing, it’s dealing with
ICMP to test the reachability of a host on a network
and to measure the round-trip time for messages
sent from the host to a destination computer.
Internet
Layer
IP
Network
Layer
ICMP
Network Interface
On any machines running Windows x, ping can be accessed
via a DOS prompt.
Select "Run..." from the Start menu and type command "cmd". Once
you're at the DOS prompt, type "ping Host-Address".
ping yahoo.com
# ping yahoo.com
PING yahoo.com (204.71.202.160): 56 data bytes
64 bytes from 204.71.202.160: icmp_seq=0 ttl=246 time=108.0 ms
64 bytes from 204.71.202.160: icmp_seq=1 ttl=246 time=102.3 ms
64 bytes from 204.71.202.160: icmp_seq=2 ttl=246 time=102.6 ms
64 bytes from 204.71.202.160: icmp_seq=3 ttl=246 time=105.5 ms
64 bytes from 204.71.202.160: icmp_seq=4 ttl=246 time=103.9 ms
--- yahoo.com ping statistics --5 packets transmitted, 5 packets received, 0% packet loss
round-trip min/avg/max = 102.3/104.4/108.0 ms
Yahoo Server
Application
Layer
Transport
Layer
HTTP
FTP
SMTP
TCP
Internet
Layer
BGP
UDP
ICMP
Network
Layer
DNS
RTP
OSPF
IP
2 Well-Known
Utility-Application Protocols
DNS , ICMP
Network Interface
3 Well-Known
Routing Protocols
BGP , RIP , OSPF
RIP
4. IP v4 and IP v6:
The Internet Layer defines an official packet format (using
core IP Protocol), to deliver after that independently through
the network between the sender and receiver.
Application Layer
HTTP , FTP , SMTP , RTP , DNS ,
BGP , RIP , …
Transport Layer
TCP , UDP
Internet Layer
IPv6
v4 IP
32, OSPF
bits
ICMP,,ICMP
,ICMP
… ,,……
IP
128
bits,,,OSPF
OSPF
Network Layer
There are two types of core
IP protocol, IP v4 (version 4) (32 bits)
and IP v6 (version 6) (128 bits).
Application
Layer
FTP
Transport
Layer
HTTP
SMTP
TCP
Internet
Layer
BGP
RIP
UDP
ICMP
Network
Layer
DNS
RTP
OSPF
IP
IP defines an official
packet format and
provides IP
Addresses
There are 2 Types:
IP v4 - 32bits
IP v6 - 128 bits
Network Interface
4. IP v4 and IP v6 (Cont.):
IP v4 Packet Format:
Consists of 32 bits, so can distribute approximately 4.2 billion
IPs around the world. Its developed in 1970s.
4. IP v4 and IP v6 (Cont.):
Since the 4.2 billion IPs of IPv4 will not be enough in the near
future with the development and the rapid increase of users of
computer, phones, gaming consoles and many other devices which
connected to Internet.
This has been the development of the IPv6, which can distribute
approximately 6 trillion IPs.
4. IP v4 and IP v6 (Cont.):
IP v6 Packet Format:
Consists of 128 bits, so can distribute approximately 6 trillion
IPs around the world. Its developed in 1993.
4. IP v4 and IP v6 (Cont.):
While IPv6 use and management is similar to IPv4, but its not
backwards compatible.
It will eventually replace IPv4, but the transition could take
long time to complete. Full IPv6 adoption has been slower
than anticipated.
In the meantime, all of Servers must
be available over both IPv4 and
IPv6, and much of Internet devices
will run IPv4 and IPv6 simultaneously
(this called Dual-Stack approach).
Application Layer
HTTP , FTP , SMTP , RTP , DNS ,
BGP , RIP , …
Transport Layer
TCP , UDP
Internet Layer
IPv4 / IPv6 , OSPF , ICMP , …
Network Layer
4. IP v4 and IP v6 (Cont.):
IP v4 Packet Format:
X
IP v6 Packet Format:
To learn more, plz visit the following pages:
- www.networkset.net/2010/05/05/ipv4-vs-ipv6/
- www.youtube.com/watch?v=-oQ4JYBjhVc&feature=related
5. TCP and UDP Packets:
TCP and UDP protocols are most communication over the
Internet.
TCP Packet Format:
5. TCP and UDP Packets (Cont.):
TCP and UDP protocols are most communication over the
Internet.
UDP Packet Format:
6. Simplified Network Packet Format:
In simply, each network packet consist of the 5 important
parts, which used as a keys for packet classification.
3
8 bits
2
IP Source
32 bits
Protocol
1
IP Destination
32 bits
According to “IP Des/Sou”
we can classify the packet
either IP v4/ v6, and the
addressing schema.
According to “Protocol Type” we
can classify the packet either
unreliable / reliable protocol
(UDP / TCP).
4
Des. Port
16 bits
5
Sour. Port
16 bits
Data
According to “Des/Sou Port” we
can classify the packet based on
Application Layer Protocols
(HTTP , FTP , SMTP , RTP , DNS ,
BGP , RIP , …).
7. Screening Router:
Screening Router: it’s a router that performs packet filtering
to see whether a packet is part of an existing stream of
traffic. Also, it can filters each packet based only on
information contained in the packet itself.
Each router do packet
classification, when the
packet addressed to it.
A
Screening
Router
B
C
7. Screening Router (Cont.):
Screening Router: it’s a router that performs packet filtering
to see whether a packet is part of an existing stream of
traffic. Also, it can filters each packet based only on
information contained in the packet itself.
TO: B
TCP: Web
A
TO: A
UDP: Video
Screening
Router
B
TO: A
UDP: #bxsa?t^q1
C
In some cases a
screening router
may be used as
perimeter
protection for the
internal network as
a filtering solution
University of Technology
Computer Science Department
Network Administration Branch
First Class
Q&A
Principles of Network Algorithms
Second Semester – 2012
Prepare by: Dr. Mazin S. Ali
available at: www.uotechnology.edu.iq/dep-cs
University of Technology
Computer Science Department
Network Administration Branch
First Class
Lecture 7:
Switching Theory
Contents:
1. Short Reviewing
2. Switching Theory
3. Crossbar Switch Architecture
4. Crossbar Switch Models
IQ Switch
OQ Switch
CIOQ Switch
143
Review
Review
Review
1. Short Reviewing:
Switch Device: is a central network device that connects all
nodes in a star topology.
Also it is concentrator (a device that can have multiple
inputs and outputs all active at one time).
Interconnection Switching Fabric: is a fabric which connects
the router's input ports to its output ports.
Router - Switching can be accomplished in a number of
ways (Switching via Memory , Switching via Bus , and
Switching via Crossbar).
Router
Input Links
Switch
Output Links
a
a
b
b
c
c
Processor
Forwarding Table
f
i
Prefix
0
00
01
1
10
1100
1101
1110
1111
Output Link
a
b
c
d
e
f
g
h
i
f
i
Router
Prefix Output Link
0
a
00
b
01
c
1
d
10
e
1100
f
1101
g
1110
h
1111
i
Compressed
1-Bit Trie Algorithm
Router
Switch
Input Links
a
1100
Output Links
a
b
b
c
c
Processor
1100
Forwarding Table
f
f
Compressed
1-Bit Trie Algorithm
i
Prefix
0
00
01
1
10
1100
1101
1110
1111
Output Link
a
b
c
d
e
f
g
h
i
f
i
Router
Switch
Input Links
1100
a
Output Links
a
b
b
c
c
Processor
Forwarding Table
f
Centralized
Switching
i
Prefix
0
00
01
1
10
1100
1101
1110
1111
Output Link
a
b
c
d
e
f
g
h
i
f
i
Router
Switch
Input Links
Output Links
a
a
b
b
c
c
Processor
Forwarding Table
f
00
Decentralized
Switching
i
Prefix
0
00
01
1
10
1100
1101
1110
1111
Output Link
a
b
c
d
e
f
g
h
i
f
i
Router
100
111110
Switch
001100
1010
101100
011001
11010
110011
11010
Processor
1000100
0001100
11100
101010
110011
Forwarding Table
110011
101100
010100
Prefix
0
00
01
1
10
1100
1101
1110
1111
Output Link
a
b
c
d
e
f
g
h
i
1100111
110010
101100
Switching
100
111110
Switch
1010
001100
101100
011001
11010
1000100
0001100
11100
101010
110011
1100111
110011
101100
010100
110010
101100
2. Switching Theory:
Switching theory is the mathematical study of the properties
of networks of idealized switches.
Switch design is mainly influenced by “Cost” and “Heat”.
Key technological factors affecting cost and heat
– Memory bandwidth (not the size of memory, but its
speed)
– Complexity of algorithms
– Number of off-chip operations (this affects speed)
3. Crossbar Switch Architecture
One way to overcome the bandwidth
limitation of a single, shared bus is to
use a crossbar.
A crossbar switch is an interconnection
network consisting of 2N busses that
connect N input ports to N output ports.
A packet arriving at an input port travels along the horizontal
bus attached to the input port until it intersects with the
vertical bus leading to the desired output port.
153
4. Crossbar Switch Models
There are three Crossbar Switch Models, these are:
IQ Switch Model
OQ Switch Model
CIOQ Switch Model
4. Crossbar Switch Models (Cont.)
If the vertical bus is being used to transfer
a packet from another input port to this
same output port, the arriving packet is
blocked and must be queued at the
input port, to enhance the performance.
Input Port
Line
Termination
Function
Data Link
Processing
Lookup,
Forwarding,
Queuing
155
Switching Fabric
If the vertical bus is free, the packet is
transferred to the output port.
4. Crossbar Switch Models (Cont.)
If the vertical bus is being used to transfer
a packet from another input port to this
same output port, the arriving packet is
blocked and must be queued at the
input port, to enhance the performance.
Input Port
Line
Termination
Function
Data Link
Processing
Lookup,
Forwarding,
Queuing
156
Switching Fabric
If the vertical bus is free, the packet is
transferred to the output port.
4. Crossbar Switch Models (Cont.)
Also we can use the same strategy at the output port, so
we can queued at the output port, to enhance the
performance.
Output Port
Queuing
Data Link
Processing
157
Line
Termination
Function
4. Crossbar Switch Models (Cont.)
Input Ports
Output Ports
Switching Fabric
Routing Processor
Queuing
OQ
Queuing
IQ
158
Combined Input and Output Queued
(CIOQ) Crossbar Switches
4. Crossbar Switch Architecture (Cont.)
We use Combined Input and Output Queued (CIOQ)
Crossbar Switches to get great performance.
When the vertical bus (in
switch fabric) is being
used to transfer a packet.
It’s not free it’s busy. We
will
useful
from
IQ
Crossbar Switch model
When the backbound
network traffic was slower
than the traffic on the
switch fabric. We will
useful from OQ Crossbar
Switch model
Combined Input and Output Queued
(CIOQ) Crossbar Switch Model
University of Technology
Computer Science Department
Network Administration Branch
First Class
Q&A
Principles of Network Algorithms
Second Semester – 2012
Prepare by: Dr. Mazin S. Ali
available at: www.uotechnology.edu.iq/dep-cs
University of Technology
Computer Science Department
Network Administration Branch
First Class
Lecture 8:
Switching Theory (Cont.)
Contents:
1. Review
2. Speed Up and Delay Control in CIOQ
3. Stable Marriage Algorithms for CIOQ
Gale-Shapley Algorithm (GSA)
4. Scheduling Algorithms for CIOQ
First In First Out Scheduling Algorithm (FIFO)
Most Urgent Cell First Scheduling Algorithm (MUCF)
Randomized Switch Scheduling
162
1. Review
Input Links
Switch
Output Links
a
a
b
b
c
c
Processor
Forwarding Table
f
i
Prefix
0
00
01
1
10
1100
1101
1110
1111
Output Link
a
b
c
d
e
f
g
h
i
f
i
Router
Prefix Output Link
0
a
00
b
01
c
1
d
10
e
1100
f
1101
g
1110
h
1111
i
Compressed
1-Bit Trie Algorithm
Router
Switch
Input Links
Output Links
a
a
b
b
c
c
Processor
Forwarding Table
f
00
Decentralized
Switching
i
Prefix
0
00
01
1
10
1100
1101
1110
1111
Output Link
a
b
c
d
e
f
g
h
i
f
i
2. Speed Up and Delay Control in CIOQ Switch:
The fabric speedup for an IQ switch equals 1
The fabric speedup for an OQ switch equals N
Suppose we consider switches with fabric speedup of S, so
the fabric speedup for CIOQ equles 1 < S ≪ N
The Probabilisitc Analyses (Assume trafic model) and the
Numerical Methods (Use simulated and actual traffic traces)
approaches showed that switches which use a speedup of
between 2 and 5 achieve the same mean delay and
throughput.
1. Speed Up and Delay Control in CIOQ Switch:
The fabric speedup for an IQ switch equals 1
The fabric speedup for an OQ switch equals N
Suppose we consider switches with fabric speedup of S, so
the fabric speedup for CIOQ equles 1 < S ≪ N
IQ
CIOQ
OQ
Speedup = 1
Inexpensive
Speedup = 2--5 ?
Inexpensive
Speedup = N
Expensive
Poor performance
Good performance
Great performance
3. Stable Marriage Algorithms for CIOQ:
Most, if not all, switch scheduling algorithms use stable
marriage algorithms (SMAs) like “Gale-Shapley Algorithm
(GSA)”.
This is because of the following equivalence:- request = proposal
- grant and accept = engagement
- final matching = marriage
3. Scheduling Algorithms for CIOQ:
The CIOQ schedule his queued work by the scheduling
algorithm like:
1. Queuing the packets as packet-by-packet under a stable
FIFO (First In First Out) schedule algorithm.
2. Queuing the packets based their most urgent packets
under a unstable MUCF (Most Urgent Cell First)
schedule algorithm.
3. Scheduling Algorithms for CIOQ:
The CIOQ schedule his queued work by the scheduling
algorithm like:
1. Queuing the packets as packet-by-packet under a stable
FIFO (First In First Out) schedule algorithm.
2. Queuing the packets based their most urgent packets
under a unstable MUCF (Most Urgent Cell First)
schedule algorithm.
3. Randomized Switch schedule algorithm, base
decisions upon a small, randomly chosen sample of the
inputs, instead of the complete inputs.
University of Technology
Computer Science Department
Network Administration Branch
First Class
Q&A
Principles of Network Algorithms
Second Semester – 2012
Prepare by: Dr. Mazin S. Ali
available at: www.uotechnology.edu.iq/dep-cs
University of Technology
Computer Science Department
Network Administration Branch
First Class
Lecture 9:
Bandwidth Partitioning
Contents:
1. Review
2. Network Bandwidth
2.1. Network Bandwidth – Network Centric Approach
2.2. Network Bandwidth – User Centric Approach
173
1. Review:
Network Bandwidth (bit rate, channel capacity, or
throughput) is a measure of communication channel usage
(available or consumed of communication path) in
bits/second “pbs” or multiples of it (kilobits/s “Kbps”,
megabits/s “Mbps”, etc.).
174
How to congested network
with many users?
175
2. Network Bandwidth:
The basic idea is how to congested network with many
users.
So there are 2 problems will be appears:
- How can allocate bandwidth fairly between the users
- How can control queue size and hence delay
To solve the problems we need to partitioning the
bandwidth, however we have 2 approaches, can select any
one of them:
- Approach 1: Network-Centric
- Approach 2: User-Centric
Bandwidth
Partitioning
2. Network Bandwidth (Cont.):
The basic idea is how to congested network with many
users.
S1
D1
10Mpbs
10Mpbs
D1
S1
1Mpbs
D1
S1
:
:
D1
S1
D1
2.1. Network Bandwidth – Network Centric Approach
We can divide the bandwidth depending on number of users
(frequency division).
Switch
2.1. Network Bandwidth – Network Centric Approach
We can divide the bandwidth depending on number of users
(frequency division).
Switch
In this approach we partitioning the bandwidth depend on
the number of users.
This approach perfect fairness, but its responsive to number
of users.
2.1. Network Bandwidth – User Centric Approach
We can divide the bandwidth depending on time (time
division).
Switch
In this approach we partitioning the bandwidth depend on
the time of packet arrival, as a FIFO.
This approach also fairness, but its responsive to
congestion.
University of Technology
Computer Science Department
Network Administration Branch
First Class
Q&A
Principles of Network Algorithms
Second Semester – 2012
Prepare by: Dr. Mazin S. Ali
available at: www.uotechnology.edu.iq/dep-cs
University of Technology
Computer Science Department
Network Administration Branch
First Class
Lecture 10:
IP Addressing
Contents:
1. IPv4 Addresses
2. Classful IPv4 Addressing Scheme
3. Public and Private IP Addresses
4. Reserved IP Addresses
5. Subnetting / Netmask
6. NAT (Network Address Translation)
183
1. IPv4 Addresses:
IP Address (Internet Protocol address) is a numerical.
label assigned to each device (e.g., computer, printer)
participating in a computer network.
With IPv4, it's 32bits long and unique; and with IPv6, it’s
128bits long and also unique.
The IPv4 Address has two parts:
The Network Part(netid)(also called IP prefix) and Host Part(hostid)
to identify the host on that network
to identify the network to which host is attached
184
1. IPv4 Addresses (Cont.):
192 . 168 . 0 . x
185
1. IPv4 Addresses (Cont.):
32bits IP address divides into 4 group of 8bits.
0
0 … 255
8
16
0 … 255
8
2 = 256
24
0 … 255
32
0 … 255
(0 … 255)
To provide the flexibility to support different sized
networks, with each network containing different number
of hosts.
32
IP address space of 2
addresses was divided into three
different classes for networks and hosts, as Class A,
Class B, Class C, and Class D.
186
2. Classful IPv4 Addressing Scheme:
Classful IPv4 Addressing Scheme
187
2. Classful IPv4 Addressing Scheme (Cont.):
Classful IP Addressing Scheme
0
Class A
8
0 2 7 = 128
0
Class B
Class C
Class D
188
16
10
32
224= 16 777 216
8
16
1416 384
2=
24
32
216 = 65 536
0
8
110
= 22 21
097 152
0
8
1110
24
16
16
24
32
2 8 = 256
24
32
Multicast Address
A host can use a , multicast address as the
destination address for packet generated to indicate
the packet is meant for any hosts on the Interne
2. Classful IPv4 Addressing Scheme (Cont.):
Classful IP Addressing Scheme
0
Class A
0
8
16
128
Class B
189
hostid
8
16
24
32
10
16 384
65 536
10
netid
hostid
0
Class C
32
16 777 216
0 netid
0
24
8
16
24
32
110
2 097 152
256
110
netid
hostid
3. Public and Private IP Addresses:
Imagine, if we had a company has 1000 Computers, It is
illogical to buy 1000 IP addresses, this exploitation of the
amount of IP addresses. So we can buy 1 or 2 IP addresses
(as a Public IP Addresses) and distributed them (using NAT)
between the computers (as a Private IP Addresses).
Private IP Addresses
Class A
10 . 0 . 0 . 0
-
Class B
Class C
172 . 16 . 0 . 0 192 . 168 . 0 . 0 -
10 . 255 . 255 . 255
172 . 31 . 255 . 255
192 . 168 . 255 . 255
These addresses are commonly used for homes, offices,
and enterprise LANs.
190
3. Public and Private IP Addresses (Cont.):
Private IP Addresses
Class A
10 . 0 . 0 . 0
-
Class B
Class C
172 . 16 . 0 . 0 192 . 168 . 0 . 0 -
10 . 255 . 255 . 255
172 . 31 . 255 . 255
192 . 168 . 255 . 255
Just for speed observation (for Private or Public IP Addresses):
each class started with specific range as shown
Class A : 1 - 126
Class B: 128 - 190
Class C: 191 - 223
191
4. Reserved IP Addresses:
There are certain IP addresses are reserved by the IANA for
special use.
IP
0.0.0.0 0 . 255.255.255
255.255.255.255
127.0.0.0 127.255.255.255
Host : All 0’s
Host: All 255’s
Started 224 - 255
192
Reserved for
broadcast messages to the
current network
the "limited broadcast"
destination address
loopback addresses to the local
host (troubleshooting)
Network ID
broadcast
future use
5. Subnetting / Netmask:
A Subnet is a logically subdivision of an IP network. The
practice of dividing a network into two or more networks is
called Subnetting.
Class C
For example:
192 . 168 . 40 . 3 IP Address
255 . 255 . 255 . 0 Subnet Mask (/24)
11000000 10101000 00101000 00000011
11 111111 11111 111 111111 11 00000000
AND
11000000 10101000 00101000 00000000
192 . 168 . 40 . 0 Gateway
193
5. Subnetting / Netmask (Cont.):
Class A
10 . 0 . 0 . 2
IP Address
255 . 0 . 0 . 0
Subnet Mask (/8)
AND
10 . 0 . 0 . 0
194
Gateway
6. NAT (Network Address Translation):
NAT (Network Address Translation) is the process of
modifying IP address information in IP packet headers while
in transit across a traffic routing device.
It’s use to translate the Private IP to Public IP and vice versa.
68.143.77.15
NAT
yahoo.com
195
Private IP
Request
Public IP
:
:
:
192.168.0.7
yahoo.com
68.143.77.15
:
:
:
6. NAT (Network Address Translation) (Cont.):
There are three types of NAT:
1- Static NAT
2- Dynamic NAT
3- Overloading NAT
68.143.77.15
68.143.77.16
68.143.77.17
196
University of Technology
Computer Science Department
Network Administration Branch
First Class
Q&A
Principles of Network Algorithms
Second Semester – 2012
Prepare by: Dr. Mazin S. Ali
available at: www.uotechnology.edu.iq/dep-cs