cs428 Internetworking

Information about cs428 Internetworking

Published on December 30, 2007

Author: Freedom

Source: authorstream.com

Content

Internetworking:  Internetworking Internetworking:  Internetworking Connecting multiple point-to-point networks Two problems must be addressed heterogeneity connected point-to-point networks may use different technologies still other network types may exist in between scale consider the growth of the Internet algorithms must work for much larger networks than they are designed for Outline:  Outline Bridging interconnects LAN’s to produce an extended LAN limited in how well it deals with heterogeneity and scale Internet Protocol (IP) the Internet service model hierarchical addressing and routing Next Generation IP (IPv6) designed to fix the problems of IP Bridge:  Bridge Problem: suppose we want to connect two Ethernets together to form a bigger one repeater forwards signals from one Ethernet segment to the next recall max of 4 per Ethernet: limited scalability Bridge connected to both Ethernets accepts all transmissions on either network and forwards them onto the other two or more networks connected by one or more bridges form an extended LAN Why Bridges?:  Why Bridges? Autonomy of ownership of the separate LANs one dept. might want FDDI, another Ethernet they still want to interact Geography it may be cheaper to build separate LANs and connect them Splitting load with two connected LANs, contention is halved Distance between nodes Ethernet allows max distance of 1500m Reliability: a bridge may isolate problems Security with bridges, not all nodes necessarily see all traffic Learning Bridges:  Learning Bridges Why should the bridge forward packets sent from A to B onto network 2? If the bridge knew where the hosts resided, it could forward only those packets that needed to be forwarded creating and maintaining a table manually is unnecessary use the source address of incoming packets if a packet comes in from host D on port 2, then the bridge can deduce that host D resides on network Y build the table dynamically, flush entries periodically to deal with hosts moving from one network to the other Y Loops:  Loops Bridges 1, 2, and 3 form a loop could be there on purpose (redundancy) or by accident (no single person considers the global topology) packets can be forwarded forever Spanning Trees:  A spanning tree S of a graph G is a subset of G that contains all the vertices but no cycles if S has cycles, throw out some edges Bridges select the ports onto which they will forward packets Spanning Trees Spanning Tree Alg. Overview:  Spanning Tree Alg. Overview identify the bridge with the smallest identifier, and elect that bridge to be the root of the spanning tree the root always forwards all packets over all ports each bridge computes the shortest path to the root remembers which port is on that path all bridges connected to a LAN elect a single designated bridge for that LAN the designated bridge is the one with the shortest path to the root a bridge forwards frames on only those ports connected to networks for which the bridge is the designated bridge Spanning Tree Example:  Spanning Tree Example B3 B2 B4 B1 B6 B7 B5 A B K C D E G H I J Spanning Tree Example:  Spanning Tree Example B3 B2 B4 B1 B6 B7 B5 A B K C D E G H I J Root: (smallest id) F Spanning Tree Example:  Spanning Tree Example B3 B2 B4 B1 B6 B7 B5 A B K C D E G H I J Root: (smallest id) F Designated for A (closer to root than B3 is) Designated for B (5 < 7) (A, B, D) (C, E) (K, F) (H, I, J) Spanning Tree Example:  Spanning Tree Example B3 B2 B4 B1 B6 B7 B5 A B K C D E G H I J Root: (smallest id) F Designated for A (closer to root than B3 is) Designated for B (5 < 7) (A, B, D) (C, E) (K, F) (H, I, J) Spanning Tree Algorithm:  Spanning Tree Algorithm Bridges can’t see the full topology to apply the rules must exchange information and run an algorithm The algorithm Send configuration messages that contain: sender’s id id of who the sender thinks the root is distance in hops from sender to the root Each bridge remembers the “best” message it has seen on each of its ports “best” means lower root id, shorter distance, lower sender id, in that order when a bridge gets a better message, it discards old information Spanning Tree Algorithm:  Spanning Tree Algorithm When a bridge learns it is not the root, it stops generating configuration messages it just forwards configuration messages from other bridges after adding 1 to the distance field When a bridge receives a “better” configuration on some port, it stops sending on that port Stabilized system only the root is generates configuration packets other bridges are forwarding them over networks for which they are the designated bridge If a bridge fails downstream bridges won’t hear config msgs from root will timeout and declare themselves the root, triggering the algorithm Internetworking:  Internetworking internetwork network of networks logical network (as opposed to physical network, e.g. FDDI) Internet Protocol (IP):  Internet Protocol (IP) Internet Protocol (IP) the protocol that runs on all nodes of an internetwork, allowing them to become a single logical network The IP service model addressing scheme that uniquely identifies all hosts connectionless datagrams (best effort, no delivery guarantee) “runs over anything” IP Packet Header Format:  IP Packet Header Format Packet Header Fields:  Packet Header Fields Version (current version 4) indicates how the rest of the header is formatted Hlen indicates the length in words of the header usually 5 for IPv4 TOS: type of service, not really used Length total bytes in the datagram including the header (max 64K) Ident, flags, offset: for fragmentation and reassembly Packet Header Fields (cont.):  Packet Header Fields (cont.) TTL: time to live counts hops (decremented by each router), current default 64 Protocol identifies the higher level protocol (e.g. TCP=6, UDP=17) Checksum sums 16-byte words, takes 1’s complement of result any failed packet is discarded Source / Destination Address defines a global address space; the IP address of any host is unique across the entire network Options: rarely used Fragmentation and Reassembly:  Fragmentation and Reassembly Different networking technologies allow different sized frames Ethernet: 1500 bytes FDDI 4500 bytes ATM: 53 bytes maximum transmission units (MTU) an MTU is the size of the largest datagram that the physical network can contain in a frame IP packets can be up to 64K requires that they be broken up into smaller units on physical networks Fragmentation and Reassembly:  Fragmentation and Reassembly Fragmentation can occur in hosts or routers hosts generally break packets up to fit the local network routers fragment when a packet arrives that is too big for a network that it must be forwarded onto Transmission fragments of the same packet may take different paths Reassembly done at the destination, never at intermediate routers Fragmentation and Reassembly:  Fragmentation and Reassembly Details ident field is chosen to be unique for the original packet the flags contain a bit that indicates whether it is the last packet the offset field indicates the first byte in this packet (X, 0, 0) can become (X, 1, 0), (X, 1, 512), (X, 0, 1024) and then (X, 1, 0), (X, 1, 512), (X 1, 768), (X, 1, 1024), (X, 0, 1280) IP Addressing:  IP Addressing Hierarchical addresses parts of the address indicate a hierarchy in the system IP addresses network part, and a host part all hosts on the same network have the same network part variable sized parts, depending on the class of the address Hosts connected to multiple networks have multiple IP addresses dotted decimal notation 128.146.88.9 IP Address Classes:  IP Address Classes Class A starts with 0 7 bits network, 24 bits for the host Class B starts with 10 14 bits network, 16 bits host Class C starts with 110 21 bits for network, 8 bits for host Class D starts with 1110 for multicast IP addr 0 = “this host” IP addr -1 = “broadcast” 127.x.y.z = loopback host IP Datagram Forwarding:  IP Datagram Forwarding Source host compares destination address with the local network if there is a match, deliver directly to the destination ARP, more later if no match, send to a router select a router by consulting the forwarding table forwarding table entry: <Network Number, Next Hop> if no entry, use a designated default router Hierarchical aggregation forwarding tables contain network numbers, not host numbers much smaller Address Resolution:  Address Resolution Problem we have the IP address of a host or router we know the host or router is on our local network but the local network has its own type of address, not IP addr Each host maintains a table of <IP address, link level address> mappings hosts populate the table dynamically Address Resolution Protocol (ARP) the table is called an ARP cache or ARP table ARP:  ARP If a source host does not contain an ARP cache entry corresponding to some target IP address source broadcasts an ARP query includes <source IP, source PA> the target host responds with <target IP, target PA> adds <source IP, source PA> to its ARP cache other hosts “refresh” <source IP, source PA> entries, if they exist reset the timeout value do not add brand new entries: they may never need them! DHCP:  DHCP Problem what if we have a physical address, but need the IP address? booting a diskless workstation needs its own IP address! Dynamic Host Configuration Protocol (DHCP) new host broadcasts a packet announcing its physical address and asking for its IP address a DHCP server runs on each network responds with the IP address for the new machine the DHCP server must be configured first to expect the question ICMP:  ICMP Internet Control Message Protocol (ICMP) Defines error messages for the source of a packet destination unreachable reassembly failed bad info in header TTL expired (hop count reached zero) checksum failed control messages ICMP-Redirect tells the source there is a better way to a destination echo and timestamp request / reply Next…:  Next… Subnetting impose another level of hierarchy within IP addresses Intradomain routing RIP, OSPF Interdomain routing EGP, BGP IP Addresses:  IP Addresses IP addresses contain a network part and a host part different classes of addresses give different numbers of bits to each part. Class B: 14 bits network, 16 bits host Problem 1: wasted addresses small networks need at least a class C address designates a minimum of 255 addresses (8 bit host part) networks with just over 255 hosts would need a class B designates 64K addresses Problem 2: routing scalability lots of networks means lots of forwarding table entries Subnetting:  Subnetting The idea introduce another level of hierarchy into IP addresses use one network number for multiple physical networks assign each “subnet” a different prefix within the host part of the address Subnetting (cont.):  Subnetting (cont.) The network number identifies the network may contain multiple physical subnets hosts on different physical networks may have the same network number the subnet ID identifies the subnet (physical network) each host is given an IP address and a subnet mask the bitwise AND of the IP address with the subnet mask identifies the subnet IP addr. = 128.104.42.12, mask = 255.255.255.0 then subnet = 128.104.42.0 Sending:  Sending Problem recall the algorithm for deciding whether to deliver locally if network id’s match, deliver locally, otherwise deliver to router this no longer works with subnetting Solution must check to see if subnets match, not just network ids sender bitwise ANDs its own subnet mask with the destination IP address if the result matches the subnet of the sender, then deliver locally otherwise send to a router Routing:  Routing Problem routers need know how to send to all other networks and “local” hosts with subnetting, “local” means something different a destination host may have the same network part as the router, and the router may still not be able to deliver directly to the host Solution maintain <subnet number, subnet mask, next hop> maintain an entry for each subnet within a network check the subnet of the destination bitwise AND an entry’s subnet mask with the destination address if the result matches the subnet number, use this entry’s next hop Benefits of Subnetting:  Benefits of Subnetting Addresses are not used up as quickly subnets can be used to make better use of addresses, rather than requiring one network ID per physical network Routing tables shrink fewer network numbers all packets to subnets of the same network get routed (from outside the network) to a common place from that common place, they get routed within the local network add relatively few entries for subnets of the same network Autonomous Systems:  Autonomous Systems An Autonomous System (AS) is a network under the administrative control of a single entity Binghamton University is an AS IBM, Endicott is an AS An AS is also known as a routing domain intradomain routing getting packets to destinations within an AS accomplished by an interior gateway protocol interdomain routing getting packets to destinations outside of an AS accomplished by an exterior gateway protocol Intradomain Routing:  Intradomain Routing Routing Information Protocol (RIP) Bellman-Ford: distance vector routing advertises routes every 30 seconds measures link cost in terms of number of hops (1-16) Open Shortest Path First (OSPF) link state routing protocol “open” in that the algorithm is published by IETF even though an IGP need not be known outside its network OSPF Characteristics:  OSPF Characteristics Route authentication what if a host advertises a low cost to all networks? nearby routers will use this host for all packets represents a point of attack on a network OSPF supports an 8 byte password used when routing information is exchanged Domain areas OSPF allows a domain to be partitioned into areas routers need not know how to get to all subnets, just all areas each domain has a backbone area all other areas are connected to it OSPF:  OSPF Domain areas (continued) intra-area routing just send along shortest path to destination inter-area routing send to backbone, across the backbone, then out to the appropriate area Multiple routing metrics delay, throughput, reliability compute and maintain three different routes one per metric enables multiple types of service low latency, high reliability, etc. OSPF:  OSPF Load balancing allows more than one route to a destination multiple copies of routes with the same cost are maintained 2nd-best route may be chosen Packet format 0 32 16 Interdomain Routing:  Interdomain Routing Exterior Gateway Protocol (EGP) assumed (imposed) a tree-like structure in the Internet required routing over a designated backbone limited scalability Border Gateway Protocol (BGP) assumes an arbitrary topology of interconnected AS’s scales better used in the current Internet goal: reachability, not optimality Interdomain Routing:  Interdomain Routing The Problem different autonomous systems have different policies and goals may be willing to route any traffic, regardless of source and destination may not be willing to route traffic to/from foreign countries may not want traffic routed through a competitor’s AS etc. BGP:  BGP Two types of traffic, with respect to some AS local traffic: originates within or terminates at the AS transit traffic: passes through the AS Three types of autonomous systems stub one connection to one other AS multiconnected more than one connection to other AS’s refuse to carry transit traffic transit (backbones) more than one connection designed (and willing) to carry transit traffic BGP:  BGP Each BGP network elects a BGP speaker The speaker advertises reachability information stub and multiconnected networks advertise the networks contained within that AS transit networks also advertise networks they can reach Speakers advertise complete paths an enumeration of all AS’s used to get to each destination allows a flexible set of policies to be implemented at each AS e.g. if an untrusted AS is in a route, don’t select this route Problems with Internet Routing:  Problems with Internet Routing Scaling problems growth of forwarding tables with more and more networks exhausting the IP address space particularly class B networks Potential solutions work against each other e.g. assign multiple class C addresses instead of a class B better address utilization, but increases forwarding table size aggregate within a class B address forwarding tables shrink, addresses used up faster Subnetting helps Classless Interdomain Routing:  Classless Interdomain Routing Classless Interdomain Routing (CIDR) also called supernetting Goal: balance the competing concerns aggregate routes behind a single forwarding table entry hand out class C addresses in blocks e.g. hand out 192.54.16 through 192.54.31 all together they all share the first 20 bits of their address build routers and protocols that allow this to be useful let network numbers be <length, value> pairs essentially allows variably sized network parts: classless addresses incorporated into BGP version 4 IPv6:  IPv6 Next Generation IP (IPng) the massive growth of the Internet requires different solutions we’ll run out of addresses before 4 billion have been assigned 4 billion isn’t that large a number depending on what gets an IP address in the future Changing address size requires a new header format a new header requires a new version number if we’re changing the header, we might as well fix a lot of other stuff at the same time IPv6 Goals:  IPv6 Goals Support more (billions of) hosts Reduce routing table sizes Allow for efficient implementations Provide better security Implement type-of-service, especially real-time Enable multicasting Enable mobility of hosts Allow the protocol to change in the future Smooth transition period IPv6 addresses:  IPv6 addresses 128-bit address space allows 3.4 X 1038 different addresses 1500 per square foot of the earth’s surface should be enough Address notation colon-separated hexadecimal representation 49AB:4851:ABCD:9981:7439:AB12:0014:1111 IPv4 embedded in an IPv6 header ::00FF:128.99.42.11 IPv6 Addresses (cont.):  IPv6 Addresses (cont.) Address allocation classless, but prefix identifies the type of network address many prefixes set, but undefined e.g. 010 prefix contains provider-based unicast addresses, which encompasses the functionality of class A, B, and C addresses 100 prefix contains geography based unicast 11111111 is for multicast addresses (like IPv4 class D)

Related presentations


Other presentations created by Freedom

Matter
15. 06. 2007
0 views

Matter

emerging diseases
10. 03. 2008
0 views

emerging diseases

Skoda Report
15. 11. 2007
0 views

Skoda Report

20070813181441372320
12. 10. 2007
0 views

20070813181441372320

Classification6
12. 10. 2007
0 views

Classification6

NMR SOLOMON Chap13
15. 10. 2007
0 views

NMR SOLOMON Chap13

Fiduciaire
17. 10. 2007
0 views

Fiduciaire

Burkert talk
15. 10. 2007
0 views

Burkert talk

EnhancedFujitaScale
05. 10. 2007
0 views

EnhancedFujitaScale

AncientChineseTangra ms
10. 10. 2007
0 views

AncientChineseTangra ms

meek
21. 08. 2007
0 views

meek

time series 2002
21. 08. 2007
0 views

time series 2002

taft hartley
21. 08. 2007
0 views

taft hartley

NLP
07. 11. 2007
0 views

NLP

ETHANOL
07. 11. 2007
0 views

ETHANOL

ALMA Paola FacultyApr07
13. 11. 2007
0 views

ALMA Paola FacultyApr07

Of Mice
17. 11. 2007
0 views

Of Mice

Basic Five Pargraph Essay
19. 11. 2007
0 views

Basic Five Pargraph Essay

lect2
23. 11. 2007
0 views

lect2

Flower
17. 12. 2007
0 views

Flower

05 Pro Waltz
23. 12. 2007
0 views

05 Pro Waltz

ICAI 2004 presentation
31. 12. 2007
0 views

ICAI 2004 presentation

AIMS Prey predator Models
01. 01. 2008
0 views

AIMS Prey predator Models

Romantic
11. 08. 2007
0 views

Romantic

personality testing
11. 08. 2007
0 views

personality testing

040617 GALLAS E talk
29. 09. 2007
0 views

040617 GALLAS E talk

PhaseTransformations
05. 01. 2008
0 views

PhaseTransformations

DiscardRoutes
07. 10. 2007
0 views

DiscardRoutes

Cold War marshall plan
28. 12. 2007
0 views

Cold War marshall plan

tort crime puzzle
07. 01. 2008
0 views

tort crime puzzle

22801
26. 11. 2007
0 views

22801

Beloved Beware
02. 08. 2007
0 views

Beloved Beware

meinshausen
21. 10. 2007
0 views

meinshausen

en ann041230
16. 10. 2007
0 views

en ann041230

solidwas
11. 12. 2007
0 views

solidwas

religiosity sexualbehaiviors
11. 08. 2007
0 views

religiosity sexualbehaiviors

Geog3225 Globalization2
22. 10. 2007
0 views

Geog3225 Globalization2

parmon
26. 10. 2007
0 views

parmon

DaisyModellingUk1
04. 01. 2008
0 views

DaisyModellingUk1

chapter6ile
02. 08. 2007
0 views

chapter6ile

Inland Empire
21. 08. 2007
0 views

Inland Empire

AIDS Ed 3 5 03 Murphy
02. 08. 2007
0 views

AIDS Ed 3 5 03 Murphy

Coulombe CND VIP 26Oct05
01. 11. 2007
0 views

Coulombe CND VIP 26Oct05

Ch6CP
16. 02. 2008
0 views

Ch6CP

plato
11. 08. 2007
0 views

plato

ImmPres
24. 02. 2008
0 views

ImmPres

Smita Gupta
24. 02. 2008
0 views

Smita Gupta

psy230 eysencks theory 06
11. 08. 2007
0 views

psy230 eysencks theory 06

JimGill
28. 02. 2008
0 views

JimGill

color
06. 03. 2008
0 views

color

impacto ampliacion
25. 10. 2007
0 views

impacto ampliacion

This Changed Life
07. 03. 2008
0 views

This Changed Life

Ken singapore
13. 03. 2008
0 views

Ken singapore

Portal mobile
20. 03. 2008
0 views

Portal mobile

turismo
22. 10. 2007
0 views

turismo

Kievan Russia
26. 10. 2007
0 views

Kievan Russia

4 Buku yang baik
14. 11. 2007
0 views

4 Buku yang baik

The Final Project Education
21. 08. 2007
0 views

The Final Project Education

41 xslt
01. 12. 2007
0 views

41 xslt

Crete
10. 04. 2008
0 views

Crete

2006911201819960
13. 04. 2008
0 views

2006911201819960

Milov Carnegie Feb 1 2005 eng
16. 04. 2008
0 views

Milov Carnegie Feb 1 2005 eng

PANCEA ovrvw URGE2 02 v1
17. 04. 2008
0 views

PANCEA ovrvw URGE2 02 v1

24081
02. 08. 2007
0 views

24081

Business 2007
12. 03. 2008
0 views

Business 2007

MercuryWeiler
18. 04. 2008
0 views

MercuryWeiler

Presentation Overall 7 26 07
22. 04. 2008
0 views

Presentation Overall 7 26 07

ompi tm cas 04 8
24. 10. 2007
0 views

ompi tm cas 04 8

6apng mongolia
30. 03. 2008
0 views

6apng mongolia

4a
28. 04. 2008
0 views

4a

approx matches
02. 08. 2007
0 views

approx matches

5 QM06 JHLee
11. 10. 2007
0 views

5 QM06 JHLee

march 01
07. 01. 2008
0 views

march 01

CG in ophthalmology
30. 04. 2008
0 views

CG in ophthalmology

Concordia KV
02. 08. 2007
0 views

Concordia KV

ammos
15. 10. 2007
0 views

ammos

ANS 217Poultry Genetics
02. 08. 2007
0 views

ANS 217Poultry Genetics

18 Hergott Shepard Residence
21. 08. 2007
0 views

18 Hergott Shepard Residence

06WorldDataSheet presentation
02. 08. 2007
0 views

06WorldDataSheet presentation

Neil Lerner
21. 08. 2007
0 views

Neil Lerner

One Stop worker presentation
18. 06. 2007
0 views

One Stop worker presentation

Paternalism
13. 10. 2007
0 views

Paternalism

Learn-Mean Median Mode Range
15. 06. 2007
0 views

Learn-Mean Median Mode Range

Learn Math Flash Measurement
15. 06. 2007
0 views

Learn Math Flash Measurement

Learning Multiplication
15. 06. 2007
0 views

Learning Multiplication

Moths and Butterflies
15. 06. 2007
0 views

Moths and Butterflies

Mock Election
15. 06. 2007
0 views

Mock Election

YaronArielAoIR5
21. 08. 2007
0 views

YaronArielAoIR5

DAMA Overview
29. 10. 2007
0 views

DAMA Overview

5 MerrillCross
19. 11. 2007
0 views

5 MerrillCross

chol ncep
02. 08. 2007
0 views

chol ncep

PoriesPres
11. 08. 2007
0 views

PoriesPres

CLIL Issues
21. 10. 2007
0 views

CLIL Issues

abby
02. 08. 2007
0 views

abby

evenson k4dev 031014
04. 10. 2007
0 views

evenson k4dev 031014

Bazelon 11 14 06 final
29. 10. 2007
0 views

Bazelon 11 14 06 final

7 3 iyer
26. 02. 2008
0 views

7 3 iyer

ahm poster gridblast 2004
28. 12. 2007
0 views

ahm poster gridblast 2004

week five
24. 10. 2007
0 views

week five

facts figures bpc2006
27. 09. 2007
0 views

facts figures bpc2006

JLA Overview
04. 01. 2008
0 views

JLA Overview

MOB7566Intro2006
17. 10. 2007
0 views

MOB7566Intro2006