PhD Orals of Pankaj Gupta

Links on this page:

Original text of orals announcement 


           Special University Ph.D. Oral Examination
   
    Algorithms for Routing Lookups and Packet Classification

                        Pankaj Gupta

                Department of Computer Science
                     Stanford University

             1:00-2:00PM, Tuesday, October 3, 2000
                         Packard Bldg, Rm 204
                (Refreshments served at 12:45pm)

Abstract:

Computers on the Internet communicate using the Internet 
Protocol (IP). IP packets travel from the source machine 
to the first router, then over links from one router to 
the next on their way towards the final destination. Each 
router along the way looks up a forwarding table based on 
the destination address of a packet to determine the next-hop 
that the packet should be sent to. Increases in link speed 
and the size of forwarding tables have made routing lookups 
a bottleneck in the IP routers that form the core of the 
Internet. In the first part of my talk, I will describe fast 
and efficient routing lookup algorithms that attempt to 
overcome this bottleneck. 

In the second part of my talk, I will describe packet 
classification algorithms that enable routers to 
distinguish and isolate traffic among different flows. Today, 
the Internet provides only "best-effort" service, treating 
all packets going to the same destination identically. 
However, Internet service providers are seeking ways to provide 
differentiated services to different packet flows, requiring 
routers to classify each packet and determine the flow it 
belongs to. Packet classification is, in general, harder than 
making a forwarding decision because it may be based on an 
arbitrary number of fields in the packet header. I will highlight 
some of the issues in designing fast packet classification 
algorithms, and describe new algorithms that enable routers to 
perform packet classification on multiple fields.

Directions to Stanford Parking I near Packard Bldg from Highway 101

Take the Embarcadero Road exit off US 101, following the signs to Stanford University. Follow Embarcadero until you cross El Camino Real, at which point you will enter the Stanford campus (Embarcadero becomes Galvez Street). Stay in the left lane, and turn right at Campus Drive (first stop sign), continue past Palm Drive, then turn left at Quarry Road into Parking Structure 1, where you can park in metered spaces on the first level (one quarter lasts 15 minutes).

Directions to Stanford Parking I near Packard Bldg from Highway 280

Take the Alpine Road exit east off Interstate 280. Follow Alpine Road for about 3/4 mile, then turn right onto Junipero Serra Blvd at the first traffic light. Turn left at the next light onto Campus Drive West, which will take you into Stanford University. Follow Campus Drive (this will wind a bit) until Quarry Road, at which you should turn right into Parking Structure 1, where you can park in metered spaces on the first level (one quarter lasts 15 minutes).

Directions to Packard Bldg from Stanford Parking

To reach Packard Building, walk through the parking structure in the same direction you entered and continue past the Mudd Chemistry Building on your right, the Stauffer Buildings on your left, and the Gates Building on your right. The Packard Electrical Engineering Building is just across Serra Mall. Packard building is approximately 0.2 miles from the parking structure.
Last Updated September 25, 2000
Pankaj Gupta
pankaj@cs.stanford.edu