Transcript ************h****3***************************3***3***3** 3**!3**"3**#3

Information Science Institute of Sripatum University
CIS514
Computer Communication and Networks
ื่ สารคอมพิวเตอร์และเครือข่าย
การสอ
Asst.Dr.Surasak Mungsing
[email protected]
[email protected]
http://www.spu.ac.th/teacher/surasak.mu
Sripatum University
1
SPU
Switching and Routing
2
ื่ สารคอมพิวเตอร์และเครือข่าย
IS516 การสอ
Switching Techniques
3
Information Science Institute of Sripatum University
Switching Networks

Data sent to a long distant receiver through
switched nodes

Nodes are not interested in contents

Computer, terminal, phone, etc.

communications network

Data route assigned by switch from one node to
another
4
SPU
Information Science Institute of Sripatum University
Simple Switched Network
5
SPU
Information Science Institute of Sripatum University
Circuit Switching

Dedicated to communication channel to two
communication stations

3 phases of operation
•
•
•
Establish
Transfer
Disconnect

switching capacity and channel capacity for
connection establishment

Manage data route intelligently
6
SPU
Information Science Institute of Sripatum University
Circuit Switching - Applications

Inefficient
•
•
Dedicated channel
Still connected even no data communication

Connection establishment requires time

After the establishment, data communication
can be done as if the two communicator are
directly connected

Developed for voice communication
(telephone )
7
SPU
Information Science Institute of Sripatum University
Public Circuit Switched Network
8
SPU
Information Science Institute of Sripatum University
Telecomms Components

Subscriber


Subscriber line




Local Loop or Subscriber loop
Connection to network
Distance no longer than 10 KM
Exchange



Devices connected to network
Switching centers
End office - supports subscribers
Trunks


Branches between exchanges
Multiplexed
9
SPU
Information Science Institute of Sripatum University
Circuit Establishment
10
SPU
Information Science Institute of Sripatum University
Circuit Switch Elements
11
SPU
Information Science Institute of Sripatum University
Circuit Switching Concepts

Digital Switch

Network Interface

Control Unit



Establish connections
Maintain connection
Disconnect
12
SPU
Information Science Institute of Sripatum University
Blocking or Non-blocking

Blocking




Cannot connect if network capacity is fully utilized
Only available in blocking network
Use in voice communication system
 Occur during a short period of time
Non-blocking


Allow connection at any time
use for data communication
13
SPU
Information Science Institute of Sripatum University
Space Division Switching

Developed for analog
communication

Separate physical
communication paths

Crossbar switch
 Number of crosspoints



grows as square of number
of stations
Loss of crosspoint prevents
connection
Inefficient use of
crosspoints
 All stations connected,
only a few crosspoints
in use
Non-blocking
14
SPU
Information Science Institute of Sripatum University
Multistage Switch

Reduce number of
crosspoints

Many communication paths
in network

Complex control

May be blocking
Three-stage Space Division Switch
15
SPU
Information Science Institute of Sripatum University
Time Division Switching

Modern digital systems depend on intelligent
control of devices and time management

Time allocation technique required for establishing
and maintaining connection of virtual circuit

Partition low speed stream of bits and send each
portion with high speed stream of bits on the
common high speed channel
16
SPU
Information Science Institute of Sripatum University
Circuit-Switching Stages

Circuit establishment

Data transfer



point-to-point from endpoints to node
internal switching/multiplexing among nodes
Circuit disconnect
17
SPU
Information Science Institute of Sripatum University
Circuit Establishment

Station request connection to node

Node defines best data path then sends data
to the next link

each next node defines next data path

After connection establishment, test message
will be sent to test whether receiver is ready to
receive data
18
SPU
Information Science Institute of Sripatum University
Data Transfer

Point-to-point data sending from sender station to
node

Internal switching and multiplexed from node to
node

Point-to-point data sending from node to receiver
station

Normally is full-duplex during communication period
19
SPU
Information Science Institute of Sripatum University
Circuit Disconnect

A station disconnects when communication
ended

Must broadcast signal to all nodes involve
data communication to release resources
to the system
20
SPU
Information Science Institute of Sripatum University
Operation of Packet Switching

Data sent in small packets




Control info


Normal packet size is 1000 octets
Long message will be divide in to packets
Each packet consists of user data and control
data
Routing information (network addresses)
Store and forward
21
SPU
Information Science Institute of Sripatum University
Use of Packets
22
SPU
Information Science Institute of Sripatum University
Advantages of Packet Switching

Better Line efficiency

Data rate conversion

All packets will be received even toght the network is
busy
 data rate may be lower

Capable of prioritizing data
23
SPU
Information Science Institute of Sripatum University
Packet Switching Technique

Long message divided into small packets

Packets are sent one by one through network

Two types of packet sending


Datagram
Virtual circuit
24
SPU
Information Science Institute of Sripatum University
Datagram

Each packets sent independently

Packets takes any route to destination

Packets may reach destination not in order

Packets may be lost along the way

Receiver reordering packets arrived and mannage
to solve lost packet problem
25
SPU
Information Science Institute of Sripatum University
Datagram
Diagram
26
SPU
Information Science Institute of Sripatum University
Virtual Circuit

Established prepared connection path before
sending packets

Perform handshaking

Each packet has virtual circuit identifier

No decision on selecting data path

Cancellation of request and circuit

Not a dedicated path
27
SPU
Information Science Institute of Sripatum University
Virtual
Circuit
Diagram
28
SPU
Information Science Institute of Sripatum University
Virtual Circuits vs Datagram

Virtual circuits




Maintain ordering of packets and error control
Sending packets fast
 No decision making on data path
Low reliablity
 If a node along the path fails, all path include that
node will fail
Datagram


No connection establishment process
 Better performance for small amount of packets
More flexible
 Routing path avoids heavy data traffic portion of
network
29
SPU
Information Science Institute of Sripatum University
Packet Size
30
SPU
Information Science Institute of Sripatum University
Circuit vs Packet Switching

Performance



Propagation delay
Transmission time
Node delay
31
SPU
Information Science Institute of Sripatum University
Event Timing
32
SPU
Information Science Institute of Sripatum University
Packet-Switched Congestion Control

If line utilization is more than 80% of its capacity,
queue length increase quickly

Limitation of queue length used for congestion
problem

Congestion status exchanged between nodes

Used flow control as of X.25
33
SPU
Information Science Institute of Sripatum University
34
SPU
Routing Algorithms
35
Information Science Institute of Sripatum University
Store-and-Forward Packet Switching


Packet is stored until it completely arrived
Router examine for correctness before forwarding to
next router
The environment of the network layer protocols.
36
SPU
Information Science Institute of Sripatum University
Connectionless and Connectionoriented Services

Two types of services in network layer
 Connectionless Service
• Each packet has independent route
• Data unit is datagram
• Subnetwork is called datagram subnet
 Connection-oriented Service
• Data path from source router to destination
router must be prepared
• Establish connection as virtual circuit
• Subnetwork is called virtual circuit subnet
37
SPU
Information Science Institute of Sripatum University
Implementation of Connectionless Service
Routing within a diagram subnet
38
SPU
Information Science Institute of Sripatum University
Implementation of Connection-Oriented Service
Routing within a virtual-circuit subnet
39
SPU
Information Science Institute of Sripatum University
Comparison of Virtual-Circuit and
Datagram Subnets
5-4
40
SPU
Information Science Institute of Sripatum University
Routing Algorithms
•
Shortest Path Routing
•
Flooding
•
Distance Vector Routing
•
Link State Routing
•
Hierarchical Routing
•
Broadcast Routing
•
Multicast Routing
•
Routing for Mobile Hosts
•
Routing in Ad Hoc Networks
41
SPU
Information Science Institute of Sripatum University
Routing Algorithms (2)
If amount of data transfer from A to A’ , from B to
B’ and from C to C’ are large enough then the
horizontal bus may be saturate and data transfer
from X และ X’ must be suspended for the network
to work efficiently
Conflict between fairness and optimality.
42
SPU
Information Science Institute of Sripatum University
Shortest Path Routing

้
ั้
Dijkstra (1959) ได ้นาเสนอ algorithm สาหรับการค ้นหาเสนทางที
ส
่ น
ทีส
่ ด
ุ ระหว่างจุด 2 จุด
The first 5 steps used in computing the shortest path from A to D.
The arrows indicate the working node.
43
SPU
Information Science Institute of Sripatum University
Flooding

Non adaptive technique to system

Router sends packets to all of its connected routers
except the router that it receives packets from

This technique quickly creates large amount of
same data in network

Requires technique to avoid creating huge amount
of data in network
•
•
Counter included in header
Keep record of packets received so that they will not be
sent to same router again
44
SPU
Information Science Institute of Sripatum University
Distance Vector Routing

algorithm for dynamic route selection

Router must have routing table of distance best
route for forwarding packets to other routers

Always updating routing table by exchange
information between adjacent routers

Measures are number of routers in the route,
amount of packets waiting for forwarding, and time
to wait along the route, etc.
45
SPU
Information Science Institute of Sripatum University
Distance Vector Routing
่ ข้อมูลไปย ัง Router G: 1) สง
่ ข้อมูล
ถ้า Router J ต้องการคานวนเวลาสง
ผ่าน Router Aใชเ้ วลา 8 มิลลิวน
ิ าที 2) จาก A ไปย ัง G ใชเ้ วลา 18 มิลลิวน
ิ า
่ ผ่าน I, H,
ที่ เวลารวม = 8+18=28 มิลลิวน
ิ าที ในทานองเดียวก ัน ถ้าสง
และ K จะใชเ้ วลารวม (10+31=41), (12+6=18), และ (6+31=37)
ตามลาด ับ เวลาทีด
่ ท
ี ส
ี่ ด
ุ คือ18 ด ังนน
ั้ J บ ันทึกเวลา18 ผ่าน H
46
(a) A subnet. (b) Input from A, I, H, K, and the new routing table for
J.
SPU
Information Science Institute of Sripatum University
Link State Routing

Dynamic algorithm for high speed transmission line

Each router must do the followings
•
•
•
•
•
Learn to know adjacent routers and their network addresses
Compute waiting time or cost in communicating with
adjacent routers
Create packets for sending its own routing information
Send packets of routing information to all routers
Compute shortest distance for each router communication
47
SPU
Information Science Institute of Sripatum University
Hierarchical Routing

Consequence of having more and more routers in
network

Algorithm use for partitioning routers into small
group, called region

Routers in the same region knows routes for
communication to each other, but have no
information of routers in other reegion
48
SPU
Information Science Institute of Sripatum University
Hierarchical Routing
ต ัวอย่างการจ ัดแบ่งกลุม
่ ข้อมูลออกเป็น 2 ระด ับ ประกอบด้วย 5 region: การจ ัด
แบบเดิม router 1A ต้องมีขอ
้ มูลถึง 17 รายการ เมือ
่ จ ัดแบบ 2 ระด ับ router 1A
้ เท่าใด
จะมีรายการเหลือเพียง 7 รายการ ด ังนนเมื
ั้
อ
่ จานวน router เพิม
่ มากขึน
่ ยลดจานวนรายการในตารางข้อมูลได้มากยิง่ ขึน
้ ะชว
้
วิธก
ี ารนีจ
Hierarchical
routing.
49
SPU
Information Science Institute of Sripatum University
Broadcast Routing
Same messages are sent to many or all hosts in the
system




Direct sending
• Create copies of packets as many as number of in the
system
• Each copy of packets defines address of each node
Send by Flooding - there will ne large amount of copies
of packets hence reduce the overall performance of the
Send by Multi-destination routing
• Each packet contains all destination addresses intended
to send to
• Router examines all receiver list to select transmission
line to be used and duplicates packets as many as
number of selected transmission lines then update each
pakets with correct destination address
Apply sink tree and spanning tree
50
SPU
Information Science Institute of Sripatum University
Broadcast Routing
Reverse path forwarding. (a) A subnet. (b) a Sink tree. (c) The tree built by
reverse path forwarding.
51
SPU
Information Science Institute of Sripatum University
Multicast Routing

Setup group receiver– create, destroy, join, resign
membership to be used for routing consideration

Each router build its own spanning tree

When packets are distributed to group receiver,
the first router that receives message examines
spanning tree. All unable to contact hosts will be
ignored.
52
SPU
Information Science Institute of Sripatum University
Multicast Routing

(a) A network. (b) A spanning tree for the leftmost router.
(c) A multicast tree for group 1. (d) A multicast tree for group 2.
53
SPU
Congestion Control
54
Information Science Institute of Sripatum University
Congestion Control Algorithms
•
General Principles of Congestion Control
•
Congestion Prevention Policies
•
Congestion Control in Virtual-Circuit Subnets
•
Congestion Control in Datagram Subnets
•
Load Shedding
•
Jitter Control
55
SPU
Information Science Institute of Sripatum University
Congestion
When too much traffic is offered, congestion sets in
and performance degrades sharply.
56
SPU
Information Science Institute of Sripatum University
General Principles of Congestion Control

Monitoring system for congestion problem

Send message to department that is responsible for
congestion problem solving

Reconfigure working operation to solve the problem
57
SPU
Information Science Institute of Sripatum University
Policies that affect congestion
5-26
58
SPU
Information Science Institute of Sripatum University
Congestion Control in Virtual-Circuit Subnets
(a) A congested subnet. (b) A redrawn subnet, eliminates
congestion and a virtual circuit from A to B.
59
SPU
Information Science Institute of Sripatum University
Hop-by-Hop Choke
Packets
(a) A choke packet that affects
only the source.
(b) A choke packet that affects
each hop it passes through.
60
SPU
Information Science Institute of Sripatum University
Jitter Control
Jitter: delay of packet delivery
(a) High jitter.
(b) Low jitter.
61
SPU
Quality of Service
62
Information Science Institute of Sripatum University
Quality of Service
•
Requirements
•
Techniques for Achieving Good Quality of
Service
•
Integrated Services
•
Differentiated Services
•
Label Switching and MPLS
63
SPU
Information Science Institute of Sripatum University
Requirements
5-30
How stringent the quality-of-service requirements are.
64
SPU
Information Science Institute of Sripatum University
Buffering
่ แพ็กเกตราบรืน
การทาให้การนาสง
่ ด้วยการใช ้ Buffer
65
SPU
Information Science Institute of Sripatum University
The Leaky Bucket Algorithm
(a) A leaky bucket with water (b) a leaky bucket with packets
66
SPU
Information Science Institute of Sripatum University
The Token Bucket Algorithm
5-34
(a) Before
67
(b) After
SPU
Information Science Institute of Sripatum University
Admission Control
5-34
An example of flow specification.
68
SPU
Information Science Institute of Sripatum University
Packet Scheduling
(a) A router with five packets queued for line O.
(b) Finishing times for the five packets.
69
SPU
Information Science Institute of Sripatum University
Integrated Services

Architecture that support multimedia data stream

Flow-based algorithm

Use for both unicast and Multicast applications

Resource reServation Protocol (RSVP)
• Developed by Zhang et al., 1993
• Many senders can send data to many receivers
• Each receiver can switch to receive data from
any sender
• Efficient use of bandwidth while trying to
eliminate congestion problem
70
SPU
Information Science Institute of Sripatum University
RSVP-The ReSerVation Protocol
(a) A network (b) The multicast spanning tree for host 1
(c) The multicast spanning tree for host 2
71
SPU
Information Science Institute of Sripatum University
RSVP-The ReSerVation Protocol (2)
(a) Host 3 requests a channel to host 1 (b) Host 3 then requests a
second channel, to host 2 (c) Host 5 requests a channel to host 1
72
SPU
Information Science Institute of Sripatum University
Expedited Forwarding
การจัดสง่ ข ้อมูลเร่งด่วน (มาตรฐาน RFC 3246) กาหนดโดย IETF
Expedited packets experience a traffic-free network.
73
SPU
Information Science Institute of Sripatum University
Assured Forwarding
A possible implementation of the data flow for assured forwarding
74
SPU
Information Science Institute of Sripatum University
Label Switching and MPLS



Developed by a group of router manufacturers
Label, instead of receiver address, is added to the front of header
and quickly compute data route by information from the label.
Resources are reserved for the whole data route
Transmitting a TCP segment using IP, MPLS, and PPP
75
SPU
Information Science Institute of Sripatum University
Next Lecture:
Switching and Routing
76
SPU