Transcript Slides

Announcements
• List [email protected]
• Lab is still under construction
• Next session we will have paper discussion,
assign papers, 3x15 min presentation
• first homework will be given next class
Review
• IP protocol
– Address formats IPv4, IPv6
– Address per interface
– Subnets, network mask, prefix len
• IP is connectionless, packet forwarding
– Packets follow independent paths to destination
• Based on destination address
– DNS to allow me to use symbolic names
Network layer vs. Link Layer
• Each link has also a link layer address that
is technology specific
– Ethernet MAC
– ATM etc …
• Network layer address (IP) is independent
of the networking technology
Sending to the subnet
• Nodes are “close” can reach them directly
in layer 2 - same “broadcast domain” !
• Need to know the MAC address
• Need to map IP to MAC address
• ARP, cache response, broadcast
• No need for any other mechanism, this is
not routing
• But I can not have everything in a single
subnet
What is routing/router
• Device with multiple ports of different networking
technologies
• Forward a packet between subnets
• Forwarding table
– Contains prefixes (and not addresses)
– Device
– Gateway
• Longest prefix match (LPM)
• Default route 0.0.0.0/0
Concept of ASes
• A set of systems under the same
administration
– Forth-net, EDET k.o.k
– Same rules, policies
• Different protocols inside and among the
domains
– Inside is relatively small
• Intra-domain
– Among is massively huge…
• Inter-domain
The Big picture
•
•
•
•
Multiple Ases talking to each other
PoPs
We will revisit later…
Some numbers
–
–
–
–
ASes: 23,400
Prefixes: 214,000
Average AS Path lengths: 3,6
Average Prefix length: 22,3
Hierarchy, what makes it all work
• Can aggregate multiple routing table entries
in large ones (less specific, larger prefix)
• Is convenient to allocate addresses
hierarchically
– Global provider, local ISPs, customers
• There are some problems though: multihoming
What is important
• Scale: can have tons of prefixes
• Speed: need to forward fast
• Resilience to faults: some link somewhere
is bound to fail
• Management and misconfigurations: there
are 23,400 entities that collaborate to make
all this work
Some generalities about routing
• Attempt to find a “good” path for the packet
• In reality, I just find the best “next-hop”
– Routing is packet-packet
• EXAMPLE
Cost in Routing
• Good can have multiple definitions
– Small delay
• Do not send the packet to athens through the US
–
–
–
–
Less loaded (related to delay)
Less expensive (real money)
Less cost (administrative cost)
Less hops
• In practice it is least cost routing today
• See example SPF: cost is set according to some
recipies/rules of thumb
ECMP
• May have multiple next-hops with the same
cost
– Why not use them all
– Router will load balance
– But have to be done carefully to avoid out-oforder packets
• ECMP, 8 or 16 in today;s routers
• EXAMPLE
Standards
• The role of standards
– Necessary if different boxes are to work together
– Standards bodies, IETF, ISO
• The role of IETF
– Democratic, collaborative
– Working groups
• Rough consensus and working code
• Requests for Comments
–
–
–
–
Standards
Proposed standards
Informational
Historical
The local view – Intra-domain
routing
• Link state routing
– The most commonly used today
• Basic concept:
– Each router has a complete view of the topology of the
network
– Pros: simple and fast convergence
– Cons: expensive to maintain reliably
• Flooding
– Compute SPF routes
• Link state routing allows me to do much-much more
What is important
• The view of each router about the network
has to agree
– Else routing loops
• TTL will catch it
• EXAMPLE
Basic Structures
• Each router has
– A list of neighbors
– The topology database that describes the
network
– And the routing table
Basic Operations
• Join the network
– Discover neighbors
– Forming adjacency
– Database exchange
• Monitor for faults and handle changes
– Monitor neighbor’s up status
– Reliable Flooding
• Route Computation
• Scaling
– Multiple areas
OSPF
• Open SPF, standard protocol today
– Not the only one though IS-IS is also strong
• Has all the elements:
– HELLO protocol for neighbor discovery and
health monitoring
– Database exchange for database syn on start
– Reliable flooding for propagating changes
Details
• Packets sent as an IP protocol (OSPF
protocol 89)
– Does not use TCP/UDP etc…
• 5 packet types: hello, LS-req, LS-upd, LSack and DD-desc
• LS-* packets carry link states
What is a LS
• Describes an object in the network
– Router, network, external prefix
• Is originated by a specific router, has an id and a
sequence number
– Each OSPF router has a unique router-id
• Routers exchange LS through flooding, build their
LS database and then compute routes
• EXAMPLE
• EXAMPLE for link failure
Flooding
• When receiving an update send it to all your
adjacencies except the one it came from
• It is reliable, each LS sent must be
acknowledged (with an LS-ack packet)
• Can receive duplicates
– Discard
• It is a bit expensive
Joining an OSPF network
• EXAMPLE
Route computation
• Build the shortest path tree rooted at the
computing node and derive the next hop
information for each destination
• EXAMPLE