Past & Present!Last time: pushing bits out of/into hardware– Link layer. How to: encode bits on wire (inc. antenna), parse bits into packets, arbitrate between senders, name receivers!Today: network layer (portable bit pushing) and end-to-end (useful bit pushing) layers!Network layer: given a packet, get it to the other side of a large (or HUGE) collection of networks.– Issue 1: Portability. Provide an interface that works across heterogeneous networks.– Issue 2: Scalability. Provide names and routing that works with billions of end hosts.Moving packet from a to b!Switch: interconnects links to form a larger network!Two parts:– Forwarding: Taking packets arriving on an input and sending them to the right output.– Routing: Collecting the information that tells you possible routes to destination (and thus which output link to send the packet on).switchT1T3Sts-1T3T1Two connection models!Connectionless (or “datagram”):– Each packet contains enough information that routers can decide how to get it to its final destination!Connection-oriented (or “virtual circuit”)– First set up a connection between two nodes.– Label it (called a virtual circuit identifier (VCI)).– All packets carry label.BAb bCBA1 1C1Virtual circuit switching (what ATM does)!Forming a circuit:– Send a connection request from A to B. Contains VCI + address of B.– Rule: VCI must be unique on the link its used on.– Switch creates an entry mapping input messages with VCI to output port.– Switch picks a new VCI unique between it and next switch.ab2521c121(Input link,VCI) (output link, new VCI)(2, 2) (3, 5)(2, 1) (3, 2)Virtual circuit forwarding!For each VCI switch has a table which maps input link to output link and gives the new VCI to use– If a’s messages come into switch 1 on link 2 and go out on link 3 then the table will be:ab2521c121Switch 1Switch 2Switch 3Virtual circuit issues!Good: easy to associate resources with flows– Can guarantee buffering and delay, which makes “quality of service” guarantees (QoS) easy to provide.– Also good: VCI small, making per-packet overhead small.!Bad: not good in the face of crashes– Doesn’t handle host crashes well: each connection has state strewn throughout network. to close connection, host must explicitly issue a “tear down.” – In general, to survive failure, want to make stuff as “stateless” as possible, trivially eliminating any storage management problems.– Doesn’t handle switch crashes well: have to teardown and reinitiate a new circuit.!Telephone network is connection-basedCS 140 - Summer 2008 - Lecture #23: Network and End-to-End layersDatagrams !Simple idea:– Don’t set up a connection, just make sure each packet contains enough information to get it to destination.– What is this? Complete destination address.– “In a connectionless network, you are always connected.” D. Cheriton!Forwarding: – Switch creates a “forwarding table”, mapping destinations to output port (ignores input ports).– When a packet with a destination address in the table arrives, it pushes it out on the appropriate output port.– When a packet with a destination address not in the table arrives, it must find out more routing information (next problem).Datagram example abc1d2200S1S2S3101Forwarding table for switch 1Destination switch porta 2c 1 b 1 d 0 Datagram Tradeoffs!Good: – No round-trip delay to setup connection.– Each packet forwarded independently of last: if switch or link fails, can be routed around it.– Resources allocated dynamically (adaptively) rather than statically bound at connection time.– Lets each “flow” achieve peak bandwidth of idle link.!Bad:– Busy link = unpredictable, wild service fluctuations.– Each packet carries full destination address, which makes per packet overhead higher.!Internet uses datagrams (“Internet Protocol” or IP)Some problems!Where do the forwarding tables come from?– Could hand-enter into a central table.– But this doesn’t work well if nodes crash, and as the number of nodes goes to infinity (internet).!And what about scale????– Recall: size of forwarding table grew O(hosts)– this... sucks.abc1d2200S1S2S3101Building routing tables!Routing = graph theory problem. The graph:– Nodes = switches or hosts– Edges = links, have an associated cost which approximates the desirability of sending traffic over the link– The routing problem: find the lowest-cost path between any two nodes where the cost of path = sum of all edges that make up the path.A B C D E 13126A simple centralized routing scheme!At creation time:– Have one central node K.– Have every switch send a vector containing (neighbor, cost) for each of its outgoing links to K.– From this information, K can compute a graph that gives the topology of the network and then whip out a graph theory algorithm to find shortest path.– K then sends this matrix to all switches.!Nice and simple!Problem: didn’t scale to large networks– Real networks were just too big. K got crushed.– CW: Centralization is the enemy of scalability, so good– routing protocols are distributed.!(Now: faster hardware? Centralized OK for Stanford?)Link state routing (sort of used in Internet)!Basic idea: – Every node knows how to reach its direct neighbors.– If this information can be disseminated to every node, then we will have enough information to good routes.!Relies on two mechanisms:– Reliable flooding of link-state information.– Calculation of routes from sum of all accumulated knowledge (uses a modified form of Dijkstra’s algorithm).!A link state packet:– [ ID of creating node, list of (neighbor, cost), sequence number, time to live].– Sequence number: monotonically increasing integer used to order link state packets.– Time-to-live: make sure packet doesn’t circulate forever.A node-level view of reliable floodingreceive(pkt) If already have a copy of LSP from pkt.ID if pkt’s sequence number <= copy’s discard pkt else decrement pkt.TTL replace copy with pkt forward pkt to all links besides the one that we received it on # done every 10 minutes or sogen_LSP() increment node’s sequence # by one recompute cost vector send created LSP to all neighborsScalable routing!Problem: our routing tables grow with the number of nodes. This is a real problem.– What was the cause? Our addresses are
View Full Document
Unlocking...