Transcript (switches) (1)

Τηλεπικοινωνιακα Δίκτυα Υψηλων
Ταχυτητων
Τηλεφωνικα Δικτυα, Ιντερνετ, ΑΤΜ (1-2 μαθήματα)
Προχωρημενα θεματα θεωριας αναμονης (2)
Οπτικες Τεχνολογιες (1)
Οπτικα Δίκτυα (2)
Μεταγωγεις (switches) (1)
Grid Computing (1)
QoS routing + Θεματα χρονοδρομολόγησης
(scheduling),δικαιοσυνης, κλπ (1)
8. Invited speaker topics (2-3)
1.
2.
3.
4.
5.
6.
7.
Α. Εργασια (term paper), B. Προφορικη εξέταση
Information economy

Today’s economy




manufacturing, distributing, and retailing items
but also: publishing, banking, CDs, film making, bills….
main ‘product’ is creation and dissemination of information
Future economy likely to be dominated by information

e.g. smart coffee machines, energy meters, wireless tags on
groceries

Can represent in two ways: analog (items) and digital (bits)

Digital is better



computers manipulate digital information
infinitely replicable
networks can move bits efficiently

We need ways to represent all types of information as bits

Ways to move lots of bits everywhere, cheaply, and with
quality of service
Common network technologies

Two successful computer networks



telephone network
Internet
What comes next? (“next-generation” Internet)

something like an ATM network or MPLS or IPv6 or?
The Telephone Network
Tηλεφωνικό δίκτυο
1920’s:
A: αναλογικοί σύνδεσμοι επικοινωνίας.
Η μεταγωγή (switching) γινόταν χειρωνακτικά.
1988: To φωνητικό δίκτυο είναι πλέον ένα ψηφιακό δίκτυο που προσπελαύνεται από
τοπικά αναλογικά loops.
A: αναλογικοί σύνδεσμοι επικοινωνίας.
D: ψηφιακοί σύνδεσμοι επικοινωνίας.
Η μεταγωγή γίνεται ηλεκτρονικά.
Is it a computer network?

Specialized to carry voice (also carries fax, modem calls)

Internally, uses digital samples

Switches and switch controllers are special purpose computers

Its design principles apply to more general computer networks
Concepts
Single
basic service: two-way voice
low
end-to-end delay
guarantee
Endpoints
signals
that an accepted call will run to completion
connected by a circuit
flow both ways (full duplex)
associated
with bandwidth and buffer resources

Fully connected core



simple routing
telephone number is a hint about how to route a call
hierarchically allocated telephone number space
The pieces
1. End systems
2. Transmission
3. Switching
4. Signaling
1. End-systems

Transducers

Dialer

Ringer

Switchhook
Since wires for reception and transmission are shared, the
received signal is also transmitted, leading to echo.
This is OK for short-distance calls, but for long distance
calls, we need to put in echo cancellors .
This is expensive and has other disadvantages
2. Transmission

Link characteristics




information carrying capacity (bandwidth)
propagation delay
 time for electromagnetic signal to reach other end
 light travels at 0.7c in fiber ~5 microseconds/km
 NY to SF => 20 ms; NY to London => 27 ms
attenuation
 degradation in signal quality with distance
 long lines need regenerators
dispersion
Multiplexing

Trunks between central offices carry 100s of conversations on the same wire

Frequency Division Multiplexing: bandlimit call to 3.4 KHz and frequency shift onto
higher bandwidth trunk; this is now obsolete

Time Division Multiplexing






first convert voice to samples
each sample is rounded to the nearest quantization level (256 quantization
levels, logarithmically spaced according to μ-law or A-law) => 1 sample = 8
bits of voice
8000 samples/sec => call = 64 Kbps
output interleaves samples from n input streams (each with a 1-byte buffer)
need to serve all inputs in the time it takes one sample to arrive => output
runs n times faster than input
overhead bits mark end of frame
Digital Signal Number of
Number
previous level
circuits
DS0
DS1
24
DS2
4
DS3
7
Number of voice Bandwidth
circuits
1
24
96
672
64 Kbps
1.544Mbps
6.312 Mbps
44.736 Mbps
Transmission: Link technologies

Many in use today






twisted pair
coax cable
terrestrial microwave
satellite microwave
optical fiber
Popular today: fiber, satellite
Cost
is in installation, not in link itself.
Builders can install twisted pair (CAT 5), fiber, and coax to every room.
Even if only one of them used, still saves money.

For long distance, there is overprovision by up to ten times
Transmission: fiber optic links

Advantages: lots of capacity, nearly error free, very little
attenuation, hard to tap.
Three
types
step
index (multimode)
graded
single
index (multimode)
mode
Multimode: cheap, use LEDs, for short distances (up to a few
kilometers)
Single
mode: more expensive, use lasers, for longer distances (up to
hundreds of kilometers)
Transmission: satellites

Long distances at high bandwidth

Geosynchronous





36,000 km in the sky
up-down propagation delay of 250 ms
bad for interactive communication
slots in space limited
Nongeosynchronous (Low Earth Orbit or Medium Earth Orbit)



appear to move in the sky
we need more of them
handoff is complicated
3. Switching: what does a switch do?

Transfers data from an input to an output



many ports (up to 200,000 simultaneous calls)`
need high speeds
Some ways to switch:


space division
time division (time slot interchange or TSI)

If inputs are multiplexed, we need a
schedule

To build larger switches we combine
space and time division switching
elements
4. Signaling

Switching systems establish temporary circuits, and they have a
switch and a switch controller.

Switch controller is in the control plane (it does not touch voice samples).

Manages the network: call routing (including call forwarding), billing (including collect
calls), alarms (ring bell at receiver), directory lookup (for 800/888 calls)
Switch
controllers are special purpose computers, linked by their own
internal computer network [the Common Channel Interoffice Signaling (CCIS)
network]. Messages on CCIS conform to Signaling System 7 (SS7) spec.

The switch controller keeps track of the state of every call
through a state transition diagram
Challenges for the telephone network

Multimedia


simultaneously transmit voice/data/video over the network
people want it but existing network can’t handle it
 bandwidth requirements
 burstiness in traffic (TSI can’t skip input)

Flexibility

Backward compatibility of new services (huge existing
infrastructure)

Regulation/Competition (future telephone networks are no longer
monopolies; how to manage the transition?)
The Internet
What does it look like?

The Internet has doubled in size every year since 1969

Soon, everyone who has a phone will also have an email account

Loose collection of networks organized into a multilevel hierarchy
10-100
machines connected to a hub or a router
service
or
providers also provide direct dialup access
over a wireless link
10s
of routers on a department backbone
10s
of department backbones connected to campus backbone
10s
of campus backbones connected to regional service providers
100s
10s
of regional service providers connected by national backbone
of national backbones connected by international trunks
Example of message routing
# traceroute henna.iitd.ernet.in
traceroute to henna.iitd.ernet.in (202.141.64.30), 30 hops max, 40 byte packets
1
UPSON2-NP.CIT.CORNELL.EDU (128.84.154.1)
1 ms
1 ms
2
HOL1-MSS.CIT.CORNELL.EDU (132.236.230.189)
3
CORE1-MSS.CIT.CORNELL.EDU (128.253.222.1)
4
CORNELLNET1.CIT.CORNELL.EDU (132.236.100.10)
4 ms
3 ms
4 ms
5
ny-ith-1-H1/0-T3.nysernet.net (169.130.61.9)
5 ms
5 ms
4 ms
6
ny-ith-2-F0/0.nysernet.net (169.130.60.2)
7
ny-pen-1-H3/0-T3.nysernet.net (169.130.1.121)
8
sl-pen-21-F6/0/0.sprintlink.net (144.228.60.21)
9
core4-hssi5-0.WestOrange.mci.net (206.157.77.105)
2 ms
2 ms
3 ms
4 ms
21 ms
21 ms
border7-fddi-0.WestOrange.mci.net (204.70.64.51)
12
vsnl-poone-512k.WestOrange.mci.net (204.70.71.90)
13
202.54.13.170 (202.54.13.170)
14
144.16.60.2 (144.16.60.2)
15
henna.iitd.ernet.in (202.141.64.30)
1349 ms
1380 ms
3 ms
19 ms
16 ms
11
1375 ms
2 ms
4 ms
core2.WestOrange.mci.net (204.70.4.185)
629 ms
2 ms
2 ms
10
628 ms
1 ms
16 ms
40 ms
20 ms
34 ms
20 ms
24 ms
26 ms
21 ms
21 ms
623 ms
21 ms
639 ms
628 ms
1343 ms
1405 ms
36 ms
1368 ms
621 ms
What lies at the heart:
Packets

Self-descriptive data (packet = data + header)

Packets vs. samples (as in circuit switching)

samples are not self descriptive; to forward a sample, we have to know where
it came from and when; we can’t store it!
Store and forward

Headers allows us to forward packets when we want (e.g. letters
at a post office)

Efficient use of critical resources

Three problems: a) hard to control delay within network, b) switches
need buffers c) convergence of flows can lead to congestion.
Τι κρατάει το Internet μαζί?
1. Η διευθυνσοποίηση (addressing): πως δηλ. aναφερόμαστε
σε μια μηχανή στο δίκτυο
2. Η δρομολόγηση (routing): πως να φτάσουμε εκεί.
3. To Internet Protocol (IP): πως να μιλάμε μεταξύ μας ώστε
να καταλαβαινόμαστε.
Για να μπείς στο Internet πρέπει να πάρεις μια διεύθυνση από τον
administrator. Αν έχεις μόνο έναν σύνδεσμο στο δίκτυο τότε ΟΚ,
αλλιώς χρειάζεσαι αλγόριθμο δρομολόγησης.Τα πακέτα σου
πρέπει να τα φορμάρεις σύμφωνα με το IP πρωτόκολλο για
να ξέρουν οι routers τι να τα κάνουν.
Κλάσεις ΙΡ διευθύνσεων
Το prefix δίνει τον αριθμό δικτύου, και το suffix δίνει τον αριθμό του υπολογιστή.
Ο αριθμός δικτύου απαιτεί διεθνή συνεννόηση, αλλά ο αριθμός υπολογιστή δίδεται τοπικά.
Η διεύθυνση που έχει όλα 1, είναι για limited broadcast.
Eνας router είναι ένας κόμβος μεταξύ δικτύων. Οι routers
έχουν μιά IP διεύθυνση για κάθε δίκτυο στο οποίο ανήκουν.
Αυτήν την στιγμή υπάρχουν πάνω απο 80000 δίκτυα.
Πρόβλημα: αν θέλεις να βάλεις πάνω από 256 μηχανές, χρειάζεσαι δίκτυο
τύπου Β, το οποίο επιτρέπει μέχρι και 64K μηχανές => wasted address space
Eπικεφαλίδα ενός IP datagram
Δρομολόγηση ενός IP datagram
Τι τύπου διεύθυνση είναι η 135.104.53.100?
Πως τα LANs χρησιμοποιούν hardware (ή physical) addresses
για να φιλτράρουν τα πακέτα
Π.χ. Ethernet (τα πεδία είναι σε bytes; οι διευθύνσεις στα πλαίσια είναι hardware διευθύνσεις)
Αddress Resolution Techniques
H IP διεύθυνση πρέπει να μετατραπεί σε hardware διεύθυνση για
να σταλεί το πακέτο στο LAN.
1. Table Lookup:
2. Closed-Form Computation: Είναι δυνατή όταν οι hardware
διευθύνσεις είναι δυναμικές. Π.χ. hardware_address = ip_address & 0xff
3. Address Resolution με ανταλλαγή μηνυμάτων
Π.χ. Το ΑRP πρωτόκολλο
Το address resolution γίνεται κάθε φορά τοπικά για ένα δίκτυο.
Μορφή ARP μηνύματος
Εναλλακτικά μπορεί αν χρησιμοποιηθεί κάποιος server για Address Resolution.
Επίσης μπορεί να χρησιμοποιείται caching για μείωση του αριθμού των
μηνυμάτων που στέλνονται.
Επικεφαλλίδα για την επόμενη γενιά του ΙΡ πρωτοκόλλου (IPv6)
Routing

How to get to a destination given its IP address?
Strictly
speaking, you need next hop information for every node in the network (10’s
of millions).
With
hierarchical design, we need next hop information for the nodes in the same
sub-network (that’s OK), and also next hop information for every network in the
Internet (> 80,000 now)
Instead,
keep detailed routes only for local neighborhood; for unknown destinations,
use a default router
Reduces
size of routing tables at the expense of non-optimal paths
Endpoint control

Key design philosophy




Layer above IP compensates for network defects


do as much as possible at the endpoint
relatively dumb/unreliable network
exactly the opposite philosophy of telephone network
Transmission Control Protocol (TCP)
Can run over any available link technology


but no quality of service
modification to TCP requires a change at every endpoint
Challenges

IP address space shortage




Decentralization







because of free distribution of inefficient Class B addresses
decentralized control => hard to recover addresses, once handed out
even small devices will soon need an IP address
allows scaling, but makes reliability next to impossible
cannot guarantee delay, bandwidth or buffer resources
hard to guarantee security: there is no control over who can join! encryption is a
partial solution, but who manages keys?
no uniform solution for accounting and billing (can’t even reliably identify users)
no equivalent of yellow pages (hard to reliably discover a user’s email address)
nonoptimal routing
Multimedia


requires network to support quality of service of some sort (hard to integrate
into current architecture; store-and-forward => shared buffers => traffic
interaction => hard to provide service quality)
requires user to signal to the network what it wants
 but Internet does not have a simple way to identify streams of packets
 nor are routers required to cooperate in providing quality
 and there is no pricing!
ATM Networks
Why ATM networks?

Different information types require different QoS

Telephone networks support a single QoS (and at a high cost)

Internet supports no QoS (but it is flexible and cheap)

ATM networks are meant to support a range of service
qualities at a reasonable cost. Potentially can replace both the
telephone network and the Internet
Design goals

Providing end-to-end QoS

High bandwidth

Scalability

Cost-effective
How far along are we?

Basic architecture has been defined

But delays have resulting in ceding desktop to IP

We may never see end-to-end ATM



but its ideas continue to powerfully influence design of nextgeneration Internet
Internet technology + ATM philosophy
Note--two standardization bodies


ATM Forum
International Telecommunications Union-Telecommunications
Standardization Sector (ITU-T)
Concepts
1. Virtual circuits
2. Fixed-size packets (cells)
3. Small packet size
4. Statistical multiplexing
5. Integrated services
Together
can carry multiple types of traffic
with end-to-end quality of service
1. Virtual circuits

Telephone network operates in synchronous transmission mode



the destination of a sample depends on where it comes from, and
when it came
idle users consume bandwidth
links are shared with a fixed cyclical schedule => quantization of link
capacity (can’t ‘dial’ bandwidth)

ATM uses packets (header indicates destination =>arbitrary
schedule and no wasted bandwidth)

Two ways to use packets


carry entire destination address in header
carry only an identifier
Data
Sample
VCI
Addr.
Data
ATM cell
Data
Datagram
Virtual circuits (contd.)

VC id’s save on header space

But need to be pre-established

We also need to switch Ids at intermediate points

Need translation table and connection setup
Features of virtual circuits

All packets must follow the same path

Switches store per-VCI state

can store QoS information

Signaling => separation of data and control

Small Ids can be looked up quickly in hardware


Setup must precede data transfer



harder to do this with IP addresses
delays short messages
Switched vs. Permanent virtual circuits
Ways to reduce setup latency



preallocate a range of VCIs along a path (Virtual Path)
send data cell along with setup packet
dedicate a VCI to carry datagrams, reassembled at each hop
2. Fixed-size packets

Advantages




Simpler buffer hardware
Simpler line scheduling
Easier to build large parallel packet switches
Disadvantages


segmentation and reassembly cost
last unfilled cell after segmentation wastes bandwidth
3. Small packet size

At 8KHz, each byte is 125 microseconds

The smaller the cell, the less an end user has to wait to fill it

packetization delay
The smaller the packet, the larger the header overhead


Standards body balanced the two to prescribe 48 bytes + 5 byte
header = 53 bytes

=> maximal efficiency of 90.57%
4. Statistical multiplexing

Suppose cells arrive in bursts


each burst has 10 cells evenly spaced 1 second apart
gap between bursts = 100 seconds

Average cell rate=0.09 cells/sec. Peak cell rate=1 cell/sec

What should be service rate of output line?
We can trade off worst-case delay against speed of output trunk

Statistical Multiplexing Gain (SMG)= sum of peak input / output rate

Whenever long term average rate differs from peak, we can trade off
service rate for delay
5. Integrated service

Traditionally, voice, video, and data traffic on separate networks

How do ATM networks allow for integrated service?


lots of bandwidth: hardware-oriented switching
support for different traffic types
 Signaling and resource reservation
 admission control
 easier scheduling
Challenges

Quality of service (defined, but not used)

Scaling (little experience)

Standardization (political and slow)

IP


a vast, fast-growing, non-ATM infrastructure
interoperation is difficult, because of fundamentally different
design philosophies
 connectionless vs. connection-oriented
 resource reservation vs. best-effort