15 441 Spring 06 Project 2 Network Layer Mike Cui Network Layer Gets data from host A to host B Global addressing uniquely identifies A and B Data finds its way to host B directly or indirectly Don t care how how they are connected as long as they are Where is host B and how to get there 1 Forwarding Finds host B by looking up in a forwarding table Dest IF 1 1 2 1 1 1 1 3 1 2 1 1 1 1 1 2 1 1 1 1 2 1 Dest IF 1 1 1 1 1 1 1 3 1 1 Dest IF 1 1 1 1 1 1 1 2 1 1 1 1 3 1 Who makes these forwarding tables 2 Routing Finds the paths to host B Fills in forwarding tables with the best path How Static Manually set it part 1 Dynamic Use a routing algorithm part 2 3 Your Mission Implement the network layer for a simulated operating system kernel IPv4 RFC 791 Relay bytes between transport and physical layers Forward packets between hosts Not required fragmentation and reassembly Implement a simple routing daemon Using OSPF protocol 4 IPv4 You must handle Checksum Header length Packet length Source and destination address Protocol number TTL IP version number Your implementation need not handle Fragmentation Options Multicast broadcast ToS 5 When You Are All Done routed Socket Host Transport Network Link Physical routed App Socket Host Transport Network Link Physical App routed Socket Host Transport Network Link Physical 6 7 Simulator Logical View App App Socket Host Transport Network Link Physical App App Socket Host Transport Network Link Physical App App Socket Host Transport Network Link Physical 8 Simulator Implementation App App Legend Shapes Unix Process Simulator Kernel Unix IPC App App App App Simulator Kernel Simulator Kernel 9 Simulator Full Picture Legend Colors Legend Shapes Unix Process Unix IPC Socket Transport Network Link Physical Socket Transport Network Link Physical User Kernel Network Stack Socket Transport Network Link Physical 10 Sending a Packet Transport Forwarding Table IP NOROUTE ip output Add IP header IP NOROUTE ifp if start Link Interface List 11 Receiving a Packet Transport udp receive Strip IP header Interface List Forwarding Table Yes ip forward For me ip input Modify IP header TTL checksum No Link ifp if start 12 pbuf Linked list of fixed size 512 byte buffers 512 512 512 512 Why Dynamic variable sized memory allocation is expensive Takes time function of size of heap Wastes space due to fragmentation 13 Inside a pbuf p next p nextpkt p data Next pbuf of this packet Next packet in list of packets First byte of data in this pbuf p len p type p dat p flags User defined There s room to grow Length of data in this pbuf 14 pbuf Chain sizeof struct pbuf p len is the length of a pbuf p pktlen is total length of data in the packet Packet 1 p nextpkt Packet 2 p next 15 IP Interface When ip input is called p data points to beginning of IP header Strip off IP header before passing onto transport layer When ip output is called p data points be beginning of IP payload Prepend an IP header before handing to link layer Can assume there s enough room to prepend a IP header Should not need to allocate more pbufs Helper functions in pbuf h p prepend p strip 16 Connecting to the Simulator include project2 include Socket h Use Socket API functions with first letter capitalized Socket Bind Connect Make sure to Close Simulator isn t an operating system it doesn t clean up after you 17 Testing Your Network Layer Use fdconfig to set up static routes Try UDP applications unreliable server unreliable client Your P1 TFTP server single client 18 Simulator Internals Multithreaded implementation System call interface User processes must register with simulator One thread to handle registration requests One thread per process to handle system calls Network devices One thread per network device Wakes up when packet arrives What does this mean for you Your code will be executed by multiple threads Your code must be re entrant 19 Concurrency Reminder What you think ticket next ticket 0 1 What really happens in general ticket temp next ticket 0 temp invisible to other threads next ticket temp 1 is visible 20 Murphy s Law Of Threading The world may arbitrarily interleave execution Multiprocessor N threads executing instructions at the same time Of course effects are interleaved Uniprocessor Only one thread running at a time But N threads runnable timer counting down toward zero The world will choose the most painful interleaving Once chance in a million happens every minute 21 Your Hope T0 T1 tkt tmp n tkt 0 tmp 1 n tkt tmp 1 Final Value 1 tkt tmp n tkt 1 tmp 2 n tkt tmp 2 2 22 Your Bad Luck T0 tkt tmp n tkt tmp T1 0 tkt tmp n tkt 0 tmp 1 n tkt tmp 1 1 n tkt tmp Final Value 1 1 1 Two threads have the same ticket 23 What To Do What you think MUTEX LOCK m ticket next ticket MUTEX UNLOCK m Now no other thread s execution of the critical section can be interleaved with yours 24 IP Dataflow Revisited Transport Two threads of execution Problem Link layer can only send out one packet at a time ip input ip output ip forward Link ifp if start 25 One at a Time Only one thread can send through a particular device at a time Otherwise the device will fail and cause kernel to panic Need mutual exclusion Use a mutex pthread mutex t for each device Declared in if h Mutex wrappers in systm h MUTEX LOCK ifp if mutex ifp start ippkt Critical section Mutex ensures that only one thread can enter at a time MUTEX UNLOCK ifp if mutex 26 IP Dataflow Revisited again App App Socket Socket Transport Transport ip output Link ifp if start Two threads can call ip output concurrently that should work Make sure it does Link ifp if start 27 Many at a Time More than one thread could invoke an IP layer function at the same time Each invocation has to be independent of one another Each invocation needs to have its own state Stack variables are independent global variables are shared Shared state needs to be protected 28 Debugging Multiple Threads Using gdb info thread lists all running threads thread n switches to a specific thread bt to get stack trace for the current thread Look for the function thread name in stack trace name of thread is in the argument link n i to k j device thread for interface i on node n to interface j on node k user pid system call handling thread for user process pid 29
View Full Document
Unlocking...