Published on May 23, 2009
The Network Layer : The Network Layer Network Layer Task : Network Layer Task The network layer concerns with getting packets from the source all the way to the destination which may require many hops through intermediate routers. This contrasts with the data link layer, which just moves frames from one end of a wire to another. To achieve its goals the network layer must know about the topology of the communication subnet ( the set of all routers) and choose appropriate paths through it. It must take care to choose routers to avoid overloading some of the lines and routers while leaving others idle. When source and destination are in different networks, it has to deal with the differences. Services to transport layer : Services to transport layer The network layer services to the transport layer have been designed with the following goals: The services should be independent of the router technology The transport layer should be shielded from the number, type and topology of the subnets present. The network addresses made available to the transport layer should use a uniform numbering plan acros LAN’s and WAN’s The Internet community argues that a subnet is inherently unreliable, the hosts should do error control and flow control. The service should thus be connectionless, but as reliable as possible, and the complexity is placed on the hosts. The telephone companies argue that the subnet should provide a reliable, connection-oriented service, placing the complexity in their subnets. Implementation of Connectionless Service : Implementation of Connectionless Service Implementation of Connection-Oriented Service : Implementation of Connection-Oriented Service For VC's, a route from the source to destination is chosen as part of the connection setup. Once a connection is setup, it gets an unique VC number. Each router along the chosen path puts an entry in a table, linking the VC number to an outgoing line. Comparison of Virtual-Circuit and Datagram Subnets : Comparison of Virtual-Circuit and Datagram Subnets Routing Algorithms : Routing Algorithms The following properties are desirable in a routing algorithm: correctness and simplicity. robustness, against software and hardware failures, traffic changes and topology changes for very long periods. stability, some algorithms never converge to an equilibrium. fairness and optimality, which are conflicting goals. static or adaptive The Optimality Principle : The Optimality Principle The optimality principle states that if router J is on the optimal path from router I to router K, then the optimal path from J to K also falls along the same route. What is to be optimized are positive values! As a consequence, the set of optimal routes from all sources to a given destination form a tree ( a sink tree) routed at the destination. Shortest Path Routing : Shortest Path Routing Dijkstra's (or another) algorithm is used to compute the path with the shortest length between any two nodes. Several metrics of length are possible. When using the number of hops as a measure, each arc as a length of 1, as was used in the figure above. If physical distance was taken as a measure, M would go over L. In general the labels on the arcs can be computed as a function of distance, bandwidth, average traffic, communication costs, mean queue length, measured delay, etc. Subnet as an undirected graph node: a router arc: a communication link. Each arc is labeled with a length. Flooding : Flooding Another static algorithm is flooding, in which every incoming packet is sent out on every outgoing line except the one it arrived on. It generates a vast number of duplicate packets, an infinite number unless some measures are taken to damp the process. E.g. a hop counter in the header of each packet, which is decremented at each hop, and the packet is discarded when the counter reaches 0. In selective flooding the packets are only sent out on those lines that are going approximately in the right direction. Flooding might be usable in military applications, large numbers of routers may be blown to pieces at any instant, as it is very robust. Also during initialization of routers. Distance Vector Routing : Distance Vector Routing A routing table in each router contains for each router the preferred outgoing line for that router and an estimate for the “cost” to that destination. The cost metric might be number of hops, queue length, time delay, etc. Time delay is measured by periodically sending ECHO packets. Once every T msec each router sends to its neighbors a list of estimated “costs” to each destination. Link State Routing : Link State Routing Distance vector routing reacts slowly on bad news, e.g. break down of a link (count to infinity problem). The core of the problem is that when X tells Y that it has a path somewhere, Y has no way of knowing whether it itself is on the path. Link State Routing: each router sends costs to neighbors to all other routers. Each router must: Discover its neighbors, learn their network address. Measure the delay or cost to each of its neighbors. Construct a packet telling all it has just learned. Send this packet to all other routers. Compute the shortest path to every other router. Link State Packets : Link State Packets The trickiest part is distributing the link state packages reliably, to assure that each router has basically the same view of the subnet. A 32 bit sequence number (sufficient for 137 years, if it is updated every second) is used. An age field is decremented every second and at every send and the packet is discarded if the age reaches 0. All link state packets are acknowledged. Hierarchical Routing : Hierarchical Routing Broadcast Routing : Broadcast Routing Router I has to send a message to all other routers. A sink tree (b) is the fastest, e.g. 4 hops and 14 messages send. But all routers must know the sink tree. Reverse path forwarding: when a router receives a broadcast packet, it checks whether it arrives on the line the router uses for sending packets to the source of the broadcast. If so, send out over all other links, else discard. 5 hops and 24 packets. Routing for Mobile Hosts : Routing for Mobile Hosts Each mobile host has a fixed Home agent. When it moves it registers at a foreign agent, which sends its information to the home agent. Routing for Mobile Hosts (2) : Routing for Mobile Hosts (2) Congestion : Congestion The reason congestion and flow control are often confused is that some congestion control algorithm operate by sending messages back to various sources, telling them to "slow down". Thus a host can get a "slow down" message either because the receiver on the direct link cannot handle the load or because the network cannot handle it. When too many packets are present, buffers get full, packets are discarded, more retransmissions and less packets delivered. Congestion thus tends to feed upon itself and become worse, leading to collapse of the system. General Principles of Congestion Control : General Principles of Congestion Control Congestion Prevention Policies : Congestion Prevention Policies Congestion Control in VC Subnets : Congestion Control in VC Subnets With admission control once congestion has been signaled, no more virtual circuits are set up until the problem has gone away. This is a crude approach, but it is simple and easy to implement. Another way is to route new connections around the problem area. The subnet is "redrawn" leaving congested routers and all their lines out and then determine the best route for a new connection in that subnet. A step further is to try to avoid routers that are directly connected to the congested routers. Hop-by-Hop Choke Packets : 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. Quality of Service Requirements : Quality of Service Requirements Jitter Control : Jitter Control For applications such as audio and video streaming, it does not matter much if the packets take 20 or 30 msec to be delivered, as long as the transit time is constant. The jitter should be small. In some applications, like video on demand, jitter can be compensated for by buffering at the receiver. For others, like Internet telephony or videoconferencing, the delay inherent in buffering is not acceptable. Buffering : Buffering Constant bit rate (e.g. telephony), attempts to simulate a wire, providing uniform bandwidth and delay. Variable bit rate (e.g. compressed videoconferencing), images must arrive in time independent on how much they could be compressed. Non-real-time variable bit rate (e.g. watching a movie over internet), a lot of buffering at the receiver is allowed. Available bit rate (e.g. file transfer), not sensitive to jitter or delay. The Leaky Bucket Algorithm : The Leaky Bucket Algorithm (a) A leaky bucket with water. (b) a leaky bucket with packets. The Token Bucket Algorithm : The Token Bucket Algorithm (a) Before. (b) After. 5-34 Internetworking: Connecting Networks : Internetworking: Connecting Networks How Networks Differ : How Networks Differ How Networks Can Be Connected : How Networks Can Be Connected Concatenated Virtual Circuits : Concatenated Virtual Circuits Connectionless Internetworking : Connectionless Internetworking Tunneling : Tunneling Internetwork Routing : Internetwork Routing This is similar to routing within a single subnet with some additional complications. Routers might prefer routes with no protocol conversions over ones that use tunneling over ones that need protocol conversions, even if those routes are longer. Subnets might be run by different carriers and have different charging algorithm, so routing might be based on cost. When international boundaries are crossed the various laws and political issues come into play. Fragmentation : Fragmentation Transparent and non-transparant fragmentation. Design Principles for Internet : Design Principles for Internet Make sure it works. Keep it simple. Make clear choices. Exploit modularity. Expect heterogeneity. Avoid static options and parameters. Look for a good design; it need not be perfect. Be strict when sending and tolerant when receiving. Think about scalability. Consider performance and cost. Collection of Subnetworks : Collection of Subnetworks At the network layer, the Internet can be viewed as a collection of subnetworks or Autonomous Systems (AS). There is no real structure, but several mayor backbones exist, constructed from high bandwidth lines and fast routers. The IPv4 Protocol : The IPv4 Protocol The IHL field tells how long the header is, in 32 bit words. The Type of Service field contains a 3 bit Precedence field, used for the priority from 0 (normal) to 7 (network control packet), and 3 flags Delay, Throughput and Reliability, to specify what is most important for the packet. In practice, current routers mostly ignore the TOS field. The situation is changing. Some options for IPv4 : Some options for IPv4 The Time to Live field is a counter to limit packet lifetimes, it must be decremented at each hop. The packet is discarded when TOL hits 0. The Protocol field tells the receiving host which transport process (TCP, UDP or other) the packet should be given to. The Header checksum verifies the header only, useful for detecting errors by bad memory bytes or corrupted software inside a router. It must be recomputed at each hop, because the TOL changes. IP Addresses : IP Addresses The class A, B resp. C formats allow for 126, 16382 resp. 2 million networks with 16 million, 64K resp. 254 hosts. Network addresses were given to organizations, leading to many unused host numbers. Special IP Addresses : Special IP Addresses IP addresses of the form 10.x.y.z (and onther one) are intended for use within a LAN (compagny or home nowadays). They are not intended to go on the public internet. Subnets : Subnets Same network number but internal subnets for departments. CIDR – Classless InterDomain Routing : CIDR – Classless InterDomain Routing Class A and B networks were all given out, Class C networks are often too small. A basic idea is to allocate the remaining class C networks (more than 2 million) in variable sized blocks, a site needing 8000 addresses then gets 32 contiguous class C networks. The world was divided up into 4 zones. A site outside Europe, that gets a packet destinated for 194... or 195... can just send it to its standard European gateway. In effect 32 million addresses have now been compressed into one routing table entry. NAT – Network Address Translation : NAT – Network Address Translation NAT makes the IP network in fact connection-oriented as it maintains information on each connection passing through it. A crash of the NAT box terminates every TCP connection. Some protocols send IP numbers (and port numbers) in data, to be used by the other side. They have been adapted or other ways are used. Internet Control Message Protocol : Internet Control Message Protocol When something unexpected occurs in a router or host, this event is reported by ICMP. The most important messages are in the table. It is also used by routers to test the internet or to obtain information to be use in routing decisions. Each ICMP message is encapsulated in an IP packet. ARP– The Address Resolution Protocol : ARP– The Address Resolution Protocol IP addresses must be linked to data link layer addresses, like Ethernet addresses or other types. With ARP the host broadcast a frame asking who owns a certain IP address, like E1 asking for 220.127.116.11. Host E2 alone will answer with a broadcast frame telling its IP and ethernet number. Entries in the ARP cache time out to allow for hardware changes. Dynamic Host Configuration Protocol : Dynamic Host Configuration Protocol If a computer boots ups, what is it IP address? It could be a fixed number, which is in the computer. But this requires administrative procedures, which cost time and is error prone. DHCP (Dynamic Host Configuration Protocol) assigns IP addresses dynamically. Older protocols for this are RARP and BOOTP. OSPF and BGP : OSPF and BGP The Internet is made up of a large number of autonomous systems (AS). Each AS can use its own routing algorithm (called an interior gateway protocol) inside. The OSPF (Open Shortest Path First) algorithm became a standard in 1990. It support 3 kinds of connections and networks: point-to-point lines multi-access networks with broadcasting (most LAN's) and without broadcasting (most packet-switched WANs). OSPF : OSPF 5-66 OSPF distinguishes 4 classes of routers: internal routers, area border routers, backbone routers and AS boundary routers. The classes may overlap, e.g. all the border routers are backbone routers.Type of service is handled by having 3 graphs, labeled with costs when delay, throughput or reliability are the metric. OSPF uses raw IP packets between adjacent routers. It is inefficient to have every router on a LAN talk to every other router on that LAN. Instead one router is elected as the designated router, which is adjacent to the other routers. A backup designated router is kept up to date in case the primary designated router crash. Another interior gateway protocol is IS-IS. BGP – Exterior Gateway Routing Protocol : BGP – Exterior Gateway Routing Protocol BGP (Border Gateway Protocol) routers have to worry about politics like: no transit traffic through certain AS'es, never put Iraq on a route starting from Pentagon, etc. These policies are manually configured into each BGP router. BGP is basically a distance vector routing, but instead of maintaining just the cost to each possible destination, each BGP router keeps track of the exact path used and send this information periodically to its neighbors. IPv6 : IPv6 The major goals of the new IPv6 protocol were: Support billions of hosts, even with inefficient address space allocation Reduce the size of the routing tables Simplify the protocol, to allow routers to process packets faster Provide better security (authentication and privacy) Pay more attention to type of service, particularly for real time data Aid multicasting by allowing scopes to be specified Make it possible for a host to roam without changing its address Allow the protocol to evolve in the future Permit the old and the new protocols to coexist for years The Main IPv6 Header : The Main IPv6 Header The flow label is also still experimental but will be used to allow a source and destination to set up a pseudoconnection with particular properties and requirements. Traffic class, is used to distinguish between packets whose sources can be flow controlled, values between 0 and 7, or not, values between 8 and 15. Extension Headers : Extension Headers The use of jumbograms is important for supercomputer applications that must transfer gigabytes efficiently across the Internet.The routing header list up to 24 routers that must be visited on the way to the destination. Both strict (the full path is supplied) and loose (only selected routers are supplied) are available, and they can be combined. Adresses : Adresses In addition to multicast, also anycast is supported. The destination is a group of addresses, but it is tried to deliver the packet to just 1 of them, usually the nearest one. This can be used for example to contact a group of cooperating file servers. The 16 byte addresses are written as 8 groups of 4 hexadecimal digits with colons between the groups, leading 0's can be left out and 1 or more groups of 16 0's can be replaced by a pair of colons.: 8000::123:4567:89AB:CDEF.